\documentstyle[11pt]{article}
\textwidth=6.5in
\textheight=9in
\evensidemargin=0in
\oddsidemargin=0in
\topmargin=-0.3in
\topskip=0pt
\baselineskip=12pt
\parskip=0pt 
\parindent=0em
\begin{document}
\bibliographystyle{plain}
\title{Data Diversity: A Search For Direction \thanks{This work was partially supported by NASA Langley Research Center under grant NAG-1-1024}}
\author{ Frederick C. Harris, Jr.}
%\author{ Frederick C. Harris, Jr.\\
%\\
%Department of Computer Science \\
%Clemson University \\
%Clemson, South Carolina \\
%USA 29634-1906 \\
%phone: 803-656-5887 \\
%fax: 803-656-0145 \\
%email: frederh@hubcap.clemson.edu
%}
\date{\quad}
\maketitle

\begin{abstract}

	A method for enhancing the reliability of $N$-version software is 
	proposed. A pilot study presents experimental results on data 
	diversity, in which retry with a mutation-directed variation in 
	input is attempted after system failure.  These results suggest 
	that mutation analysis could be valuable in the design of 
	fault-tolerant software systems.

\parskip=12pt
\parindent=0pt
{\bf keywords:} software reliability, mutation analysis, data diversity
\end{abstract}

\baselineskip=24pt
\parindent=3em
\section{Introduction.}

	Two of the leading methods proposed in the literature to enhance the
	reliability of critical software systems such as those used in 
	aircraft and spacecraft flight control, are $N$-version programming 
	and recovery blocks.  
	$N$-version programming is defined \cite{avizi:nvafts} to be multiple,
	independent implementations of the same program, where the
	implementations were coded from the same specifications.  When the
	system is put together, each implementation is given the same input,
	and it is hopeful that they generate the same output.  If they do 
	not, a majority voting scheme goes into effect to determine what the
	system's response will be.
	Recovery Blocks are built on the premise of an acceptance tester that
	can be used in conjunction with multiple implementations of the code.  
	The first implementation is given the system input, and its output is 
	passed to the acceptance test.  If the output is rejected, the system 
	is rolled back, and the input is passed to the next implementation.
	
	Ammann and Knight \cite{ammann:ddasft} observed that both of
	these methods are built on the concept of {\it design diversity},
	which is the use of multiple implementations of the same code.  
	They proposed an alternative concept called {\it data diversity},
	which is based on the premise that if software fails a minor change 
	of the input might allow it to succeed.  Minor changes in input can 
	be justified in an environment where the input sensors are noisy or
	have a very limited precision.  Their work took data diversity and 
	applied it to a recovery block structure called a retry block,
	which randomly changes the input for one implementation of the code.  
	They suggest that {\it data diversity} is a fault-tolerant strategy 
	that complements {\it design diversity}. The major shortcoming of 
	their work was the lack of suggested direction for data variation
	within the retry block. 

	This paper presents the results of a pilot study using a retry
	block equipped with {\it data diversity} to enhance the reliability 
	of an $N$-version system. A direction for the data variation 
	is taken from a gradient approximation of a multi-dimensional surface
	generated using the {\it kill score} from mutational analysis, 
	described in section \ref{sec:mutation}.
	The basic structure of this system is presented in figure 
	\ref{fig:model}.
	\begin{figure}[ht]
		\centering
		\input{figures/picture.tex}
		\caption{\label{fig:model}System Model}
	\end{figure}

	In section \ref{sec:code} a small experiment in $N$-version programming
	is described. Coding is based upon the specifications of NASA's 
	planetary lander control software.  Section 
	\ref{sec:mutation} gives a brief introduction to mutation analysis
	and describes a surface that is created using it, and section 
	\ref{sec:retry} presents three approachs to a retry block 
	which are based on the gradient-approximation of that multi-dimensional 
	surface. 
	Results from the study are presented in section \ref{sec:results}, 
	and the conclusions follow in section \ref{sec:conclusions}.

\section{\label{sec:code}A Sample Module}

	Several graduate students were selected in the fall of 1989 to 
	participate in a seminar to study errors that programmers make in
	Fortran-77 programs.  These students were presented with specifications
	for small, ``straightforward'' procedures to be completed during the
	course.  The specifications were provided by NASA as
	part of their Guidance Control Software and were quite detailed. 
	They included a description of the parameters and a specification 
	of the operations in each module \cite{withe:srgcsds}.

	The code for this course was developed in a controlled environment
	on a series of Sun 3/50's.  Whenever a module was compiled the 
	development environment placed a copy of the code in a controlled
	directory elsewhere on the system.  This allowed us to monitor the
	development of, and corrections to the modules throughout the course.
	Access to the code also allowed us to determine how well the students 
	were testing their work.

	The accelerometer sensor processing module was one of the required 
	procedures, and its specifications are summarized in figure 
	\ref{fig:specs}.  
	\parindent=0pt
	\baselineskip=12pt
	\begin{figure}[ht]
	\fbox{ \parbox{6.25in}{ \small
	Transforming accelerometer data (A\_COUNTER) into
	vehicle accelerations
	(A\_ACCELERATION) requires the following steps:
		\begin{enumerate}
		\item A\_GAIN := A\_GAIN\_0 + (G1 * ATMOSPHERIC\_TEMP) +
		(G2 * $\makebox{ATMOSPHERIC\_TEMP}^{2}$)
		\item A\_ACCELERATION\_M := A\_BIAS + A\_GAIN * A\_COUNTER
		\item Shift A\_STATUS and A\_ACCELERATION right by 1 column.
		\item A\_ACCELERATION := ALPHA\_MATRIX * A\_ACCELERATION\_M
		\item For each row of A\_STATUS and A\_ACCELERATION:
		If any of the previous three values of A\_STATUS is 
		{\it unhealthy}, set A\_STATUS(i,0) to {\it healthy}.  
		Otherwise, for each of the three dimensions in A\_ACCELERATION 
		calculate the mean ($\mu$) and the standard deviation 
		($\sigma$).  If $|\mu$ - A\_ACCELERATION(i,0)$| > $ 
		A\_SCALE*$\sigma$, then set A\_ACCELERATION(i,0) to $\mu$ and
		set A\_STATUS(i,0) to {\it unhealthy}.
		\end{enumerate} } }
	\caption{\label{fig:specs} ASP Specification Summary.}
	\end{figure}
	\parindent=3em
	\baselineskip=24pt
	This module takes input from the acclerometer sensor
	(A\_COUNTER), removes its natural electrical and temperature bias
	(steps 1 and 2), and then produces actual accelerations in the x, y and 
	z directions.

	The Guidance Control Software  was designed to operate in an
	$N$-version environment, with a typical voting scheme for control
	of the landing vehicle.  With this in mind, five implementations  
	of the procedure were taken from the course and combined into such 
	a system.   Initial system test data was generated using 
	Godzilla \cite{Offutt:Diss}, a software test case generator that 
	is based on mutation analysis

\section{\label{sec:mutation}Mutation Analysis}

	Mutation analysis \cite{Budd:Diss} is a software testing technique
	which is similar to  fault injection experiments in circuit design.  
	A collection of mutation operators are applied to the original code,  
	and each yields executable variations of the code called 
	mutants.  Some operators explicitly require that the test data meet 
	statement and (extended) branch coverage criteria, extremal values 
	criteria, and domain perturbation; the mutation operators also 
	directly model many types of faults.  Some of these mutants are 
	{\it equivalent} mutants because they are logically equivalent to 
	the original code.

	A mutant is said to be {\it killed} if its output can be made to 
	differ from that of the original code.  The goal is to obtain a 
	set of test cases that will ``kill'' all non-equivalent mutants.  
	The effectiveness of this approach to software testing is based 
	upon a fundamental premise: if the software contains a fault, it 
	is likely that there is a mutant that can only be killed by a test 
	case that also reveals the fault.

	Mutation analysis has been implemented in many testing systems, 
	the most recent of which is called Mothra \cite{MothraOverview}.
	Mothra was written by students and faculty at Georgia Tech 
	and Purdue and is a testing environment that uses
	mutation analysis as its underlying method.  This system 
	has many integrated modules that allow the user to interactively
	test Fortran-77 code throughout the development cycle. 
	Mothra allows a tester to examine remaining live mutants and 
	design tests that kill them.  The mutation operators used by 
	Mothra \cite{F77mut} represent more than 10 years of refinement 
	through several mutation systems.

	Unfortunately, generating mutation-adequate tests can be a 
	labor-intensive task.  To solve this problem, Offutt \cite{CBT} 
	devised an adequacy-based scheme for automatically generating test 
	data through a Constraint-Based Testing (CBT) system.
	In constraint-based testing, we represent the conditions under which 
	each mutant will die as mathematical constraints on the inputs,
	and then generate a test case that satisfies the constraint system.
	An implementation of this technique, Godzilla, has been integrated 
	with Mothra.

	Godzilla \cite{Offutt:Diss} is one of the most beneficial modules 
	in Mothra for a software tester.  Initial modules in Mothra parse 
	the Fortran-77 code and set up path-constraints on the input which 
	are necessary 
	to reach each line of code.  Godzilla then generates test data by 
	posing the question, ``What properties must the program inputs have 
	to kill each mutant?'' The inputs must cause the mutant to have an 
	incorrect program state after some execution of the mutated statement.
	Godzilla uses the same syntactic information that Mothra uses
	to force the syntactic change represented by the mutation
	into making a semantic difference during execution.
	Since faults are modeled as simple faults on single statements, an initial
	condition is that the mutated statement must be reached (reachability).
	A further condition is that once the mutated statement is executed,
	the test case must cause the mutant to behave erroneously, i.e. the
	fault that is being injected must result in a failure in the 
	program's output.

	Godzilla describes these conditions on the test cases as mathematical 
	systems of constraints.  The reachability condition is described by a 
	system of constraints called a {\it path expression}.  For each 
	statement in the program, the path expression contains a constraint 
	system that describes each execution path through the program that 
	will reach that statement.

	The condition that the test case must cause an erroneous state is 
	described by a constraint that is specific to the mutation operator.
	In general, this {\it necessity constraint} requires that the computation
	performed by the mutated statement create an incorrect intermediate 
	program state.  Although an incorrect intermediate program state 
	is necessary for fault detection, it is clearly not sufficient to 
	guarantee detection.  In order to detect the fault, the test case must 
	cause the mutant to produce incorrect output, in which case the final 
	state of the mutant differs from that of the original program.
	Although deriving a test case that meets this {\it sufficiency condition}
	is certainly desirable, it is impractical.  Determining the 
	sufficiency condition implies knowing the complete path that the 
	program will take, which is intractable.  Thus, the partial solution 
	of relying on the necessity condition is used.

	To generate the test cases, Godzilla solves the conjunction of the path
	expression constraint with the necessity constraint to create a
	test case consisting of values for the input variables that will make
	the constraints true.  Godzilla consistently generates test cases 
	that kill over 95\% of the mutants \cite{OffuttPort}.

	Mothra generated $3,778$ non-equivalent mutants when presented with
	one implementation of the Accelerometer Sensor Processing module.  
	Godzilla then generated $30$ test cases which killed all $3,778$ 
	non-equivalent mutants.  One test case was particularly troublesome 
	because 4 of the 5 implementations were determined to be incorrect 
	by an oracle module, whose correctness on the 30 cases was verified 
	by hand.

	The Accelerometer module has over 50 input variables which is
	too many for a pilot study.  Therefore, the particularly troublesome
	test case previously described was selected as a starting point
	for our data diversity experiment.  All input variables were fixed 
	at the values of the troublesome case except G1 and G2, which both 
	have an input domain of $[-5.0, +5.0]$.  This was done so that the 
	data gathered could be easily visualized, and because G1 and G2 
	are launch time constants yet to be determined.

	Using the code discussed in section \ref{sec:code}, we constructed 
	a surface $M$ of mutation kill scores.  $M(G1,G2)$ was calculated 
	by feeding the selected input (G1, G2) to the mutation system and 
	finding out how many mutants were killed by that particular input.
	We used $1,681$ input values evenly spaced through the G1, G2 domain
	and found output values of M ranged from 1924 to 2092.
	A digitized image of this surface is shown in figure \ref{fig:surface}.
	%A digitized image of this surface is shown in figure \ref{fig:surface},
	\begin{figure}[t]
		\centering
		\vspace{4.5in}
		% now load in the PostScript image
		% 2.5 6.0 translations
		\special{psfile=figures/surface.ps}
		\caption{\label{fig:surface} Digitized image of G1 and G2 surface}
	\end{figure}
	%and an overlay of it is provided on the following blank page.
	%in \ref{fig:surface2}
	%\begin{figure}[ht]
	%	\centering
	%	\vspace{4.5in}
	%	\caption{\label{fig:surface2} Transparency of Digitized 
	%	image of G1 and G2 surface}
	%\end{figure}

\section{\label{sec:retry}Retry Block}

	A retry block is a modification of the recovery block structure
	that uses data diversity instead of design diversity \cite{ammann:ddasft}.
	After the code has executed, a typical voting scheme determines whether
	three or more of the five implementations agree. If they do, the 
	system is assumed to be correct, and the retry block is finished.
	If the output is incorrect, then the retry block must change the input
	data and re-execute all versions of the code.

	The changing of the input data for this pilot study was based on 
	the concept of a gradient.  From basic calculus we know that a 
	gradient of a function $\nabla M$ is a vector orthogonal to the 
	level curves of $M$, i.e. pointing in the ``uphill'' direction when
	$M$ is regarded as a terrain map.
	The gradient is defined only on a smooth surface; therefore, 
	when function evaluation at a finite number of points is our only tool,
	the gradient must be approximated.
	
	This approximation was done in a simple, straight-forward way.
	Consider the three points in our lattice of evaluated points, 
	closest to the system failure point in the
	G1, G2 plane. These three along with their $M$ values are placed 
	into an array which is row-reduced to find the equation of the
	plane, which is of the form $Ax + By + Cz = 1$.   From this 
	equation the gradient for the plane is a simple combination of 
	coefficients, $\nabla M = (-A/C, -B/C)$.

	With the pseudo-gradient determined, four retry blocks were designed.
	The first was designed to change the data in a random direction
	as it was done in Ammann and Knight's experiment \cite{ammann:ddasft}.
	The next three blocks were based on the pseudo-gradient of the 
	surface at the failure location and changed the data in 3 directions: 
	the direction of the pseudo-gradient (up the surface), the direction of 
	the negative pseudo-gradient (down the surface), and orthogonal 
	to the pseudo-gradient (level with respect to the surface).
	It was conjectured that regions of lower M score would contain less
	data sensitivity and hence offer higher probability of success on retry.

\newpage
\section{\label{sec:results}Results}

	Using the restricted (G1, G2) input space described in Section 
	\ref{sec:mutation},
	random values in that space were given as input to the 5-version 
	\begin{figure}[htb]
		\centering
		\input{figures/failure.tex} 
	%	\input{figures/failure2.tex}  % just has box outline w/o data
		\caption{\label{fig:failures}Failure points in (G1,G2) space.}
	\end{figure}
	system, and the system output was checked for correctness using a 
	majority voting scheme. If fewer than 3 of the 5 implementations agreed,
	the system was ruled to be incorrect.
	This testing continued until 15,000 system failure points were 
	generated.  A graph of the points at which the failures occurred
	is in figure \ref{fig:failures}.
	It is interesting to note the differences between this graph and 
	corresponding graphs in the literature.  The failures that Ammann 
	and Knight present are in ``failure regions'' where points inside
	that region cause the system to fail and points outside that region
	cause the system to execute properly.  Figure \ref{fig:failures}  
	suggests that our failure regions may be more closely approximated 
	by hyperplanes in the input space.

	Empirical results were obtained from the implementation of the
	various retry blocks discussed in the section \ref{sec:retry}. 
	Each block was given all 15,000 system failure points.  These 
	failure points, as input, were modified accordingly, and the data 
	was then passed back to the $5$-version system to be re-executed.
	Figure \ref{fig:retry} shows the number of failures surviving the 
	retry as a function of the distance moved.  
	\begin{figure}[htb]
		\centering
		\input{figures/retry.tex}
	%	\input{figures/retry2.tex} % just has box outline w/o data
		\caption{\label{fig:retry}Failures surviving retry.}
	\end{figure}
	The random retry block corrected over $90\%$ of the original errors,
	which is quite significant.  Yet it is obvious that movement in 
	any particular direction of the gradient is much better than a
	random retry.  

\section{\label{sec:conclusions}Conclusions.}

	In this pilot study it has been shown that a data diversity approach 
	to software fault tolerance in which input data movement is determined 
	by the pseudo-gradient of the mutation surface yields much better 
	results than movement in a random direction.  It is interesting
	that retry orthogonal to the gradient (level) is usually
	better than going up or down.  This could be due to the fact that
	the mutation kill score surface is an imperfect indicator of 
	failure regions and is crisscrossed with ravines making
	movement along the surface in any direction difficult.  Such 
	information would be useful in future modifications of the mutation 
	operators.

	Further study is definitely needed on this topic.  
	The constraints placed on this pilot study need to be removed by
	not fixing input variables. It is not clear whether the kill score 
	surface M would differ substantially if the mutation generator were 
	presented with the restricted, two-input code module.  Also the effect 
	of multiple retries, subject to real-time constraints, should be 
	explored.
	

\quad
\baselineskip=12pt
\parindent=0pt
\bibliography{/home/phd/fredh/papers/bibdir/data-diversity,/home/phd/fredh/papers/bibdir/reliable}
\end{document}
