
% $Id:$

\section{Covering the Option Space }

As mentioned previously, a model with 20 binary choices has more than a million possible configurations.  
For the ANTARES system it is anticipated that, in normal practice, the number of parameters to vary will greatly exceed 100, 
which results in an exponentially larger number of possible configurations.  Worse yet, when dealing 
with simulations of physical systems, the input parameters are often real values, making choices 
non-discrete and the possible configurations infinite.  So guaranteeing coverage of the option 
space is a non-trivial problem.

\subsection{Approach}
We have explored two approaches toward covering the option space, a standard Monte Carlo and a 
3-factor combinatorial technique.  The standard Monte Carlo approach is simplest.  It generates 
parameters for a simulation run by randomly selecting from user defined probability distributions,
such as Gaussian or uniform.  The main drawback from this approach is a lack of any coverage 
guarantee, resulting in a need to run a large number of simulations to attain 
a given level of user confidence.
Unlike the standard Monte Carlo approach, the combinatorial approach makes a coverage guarantee 
while attempting to perform a minimal number of simulations.  In the case of an n-factor 
combinatorial, the guarantee is that any setting of any n discrete parameters appears in 
at least one of the simulations.  For instance, a 2-factor combinatorial test 
suite for 20 binary parameters is shown in Figure~\ref{fig:binary}.  
Note that there are only 11 tests, much less than the million tests needed to exhaustively cover every combination.   The 3-factor case only increases the number of tests to 26, still minuscule when compared to a million.

\begin{figure}
\begin{center}
{\small
\begin{verbatim}
1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 1 0
0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1
1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0
0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 1
0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 0 0
1 1 0 1 0 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0
1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0
0 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1
\end{verbatim}
}
\end{center}
\caption{\label{fig:binary}A 2-factor combinatorial test suite for 20 binary parameters}
\end{figure}

While the number of tests performed using the combinatorial approach is minuscule compared to exhaustive testing, anecdotal evidence suggests that this small number of tests is enough to catch most coding errors 
\cite{Cohen96, Dunietz97, Wallace01}.  The underlying premise behind the combinatorial approach
 can be captured in the following four statements.
\bi
 \item The simplest bugs in a program are triggered by a single input parameter.
 \item The next simplest bugs are triggered by an interaction of two input parameters.
 \item Progressively more obscure bugs involve interactions between more parameters.
 \item Exhaustive testing involves trying all combinations of all inputs.
\ei
So errors can be grouped into families depending on how many parameters need specific settings to exercise the error.  The n-factor combinatorial approach guarantees that all errors involving the specific setting of n or fewer parameters will be exercised by at least one test.
Applying an n-factor combinatorial approach to testing ANTARES involved characterizing each real-valued parameter as a partition of discrete ranges.  When turning a computed test into a simulation run, each range is replaced by a real value chosen from a uniform distribution across that range.  The result is a multidimensional space of simulation runs that projects down to a uniform distribution on any plane of input parameters, which facilitates visualization like that shown in Figure~\ref{fig:inp_par}.

\subsection{Implementation}

To generate 2-factor combinatorial test suites there are a number of algorithms in the literature
\cite{Grindal05}. Our algorithm is a generalization of IPO \cite{Tai02} to facilitate 
generating n-factor combinatorial test suites in addition to a number of features that 
a real world test suite generator would need \cite{Czerwonka06}.  These 
features include the ability to explicitly include particular combinations,
explicitly exclude particular combinations, require n-factor combinatorial 
coverage of specific subsets of parameters, and
tie the existence of particular parameters to the setting of another parameter. 

The resulting algorithm is 1041 lines of documented Java code with an 
example output that appears in Figure~\ref{fig:binary}.  Even with 
these extra capabilities the algorithm generates test suites that are 
comparable to those generated by the more restricted systems in the literature.  As shown in Table~\ref{tab:perf} the code generates quality solutions very 
rapidly on a 400MHz Windows laptop.  In the problem sizes, the $X^Y$ syntax 
means that there are $Y$ $X$-valued parameters.  
\begin{table}
\begin{center}
%VAR 1\begin{tabular}{rrr}
\begin{tabular}{|r|r|r|}
\hline
Problem Sizes   & Number of Tests     &  Time\\ 
\hline\hline
$3^{4}$      & 9             &   $\ll$ 1 sec\\
$3^{13}$     & 19            &   $\ll$ 1 sec\\
$4^{15}\times 3^{17}\times 2^{29}$      &  35      &         $<$ 1 sec\\
$4^{1}\times 3^{39}\times 2^{35}$       &  29       &        $<$ 1 sec\\
$10^{20}$   &  216           &   1 sec\\
$3^{1000}$  &  48            &   22 sec\\
\hline\hline
\end{tabular}
\end{center}
\caption{\label{tab:perf}Performance of test suite generator on 2-factor combinatorial problems}
\end{table}

