\documentclass{sig-alternate}
\usepackage{alltt,times}
\usepackage{url}
\usepackage{dblfloatfix}
\usepackage{cite}
\newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
\newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\tion}[1]{\S\ref{tion:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
   \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}
\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}

\begin{document}
%
% --- Author Metadata here ---
\conferenceinfo{PROMISE}{'09 Vancouver,  Canada USA}
%\CopyrightYear{2007} % Allows default copyright year (200X) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---

\title{On the Value of Combining Feature Subset Selection with Genetic Algorithms: Faster Learning of Coverage Models }
\numberofauthors{2} %  in this sample file, there are a *total*
\author{
\alignauthor
James H.\ Andrews \\
 \affaddr{University of Western Ontario}\\
 \affaddr{ Department of Computer Science}\\
       \affaddr{London, Ont., Canada, N6A 2B7}\\
       \email{andrews@csd.uwo.ca}
% 2nd. author
\alignauthor
Tim Menzies\\
       \affaddr{Lane Department of CS \& EE}\\
       \affaddr{West Virginia University}\\
       \affaddr{Morgantown, WV, USA}\\
       \email{tim@menzies.us}
}
\date{today}
\maketitle
\begin{abstract}
The next challenge for the PROMISE community is scaling up and
speeding up model generation to meet the size and time
constraints of modern software development projects.
% When learning complex models from large hyper-agile teams,
%the code base changes so rapidly that our current tools may not run
%fast enough. 
There will always be a trade-off between completeness and
runtime speed. Here we explore that trade-off in the context of
using genetic algorithms to learn {\em coverage models};
i.e.\ biases in the control structures for randomized test
generators.  After applying feature subset selection  to logs of
the GA output, we find we can generate the coverage model and
run the resulting test suite ten times faster while only
losing 6\% of the test case coverage.
\end{abstract}

% A category with the (minimum) three required fields
\category{B.4.8}{Programming techniques}{Performance}{Modeling and prediction}
\category{I.6.4}{Computing Methodologies }{Model Validation and Analysis}
%A category including the fourth, optional field follows...
\category{G.3}{General}{Probability and Statistics}[statistical computing]


\keywords{Software testing, genetic algorithms, feature subset selection}

% note the % following the last \IEEEmembership and also the first \thanks -
% these prevent an unwanted space from occurring between the last author name
% and the end of the author line. i.e., if you had this:
%
% \author{....lastname \thanks{...} \thanks{...} }
%                     ^------------^------------^----Do not want these spaces!
%
% a space would be appended to the last name and could cause every name on that
% line to be shifted left slightly. This is one of those "LaTeX things". For
% instance, "A\textbf{} \textbf{}B" will typeset as "A B" not "AB". If you want
% "AB" then you have to do: "A\textbf{}\textbf{}B"
% \thanks is no different in this regard, so shield the last } of each \thanks
% that ends a line with a % and do not let a space in before the next \thanks.
% Spaces after \IEEEmembership other than the last one are OK (and needed) as
% you are supposed to have spaces between the names. For what it is worth,
% this is a minor point as most people would not even notice if the said evil
% space somehow managed to creep in.
%

\section{Introduction}
\input{oldresults}
In his famous paper on the {\em Essence and Accidents of Software Engineering}~\cite{brooks87}, Frederick Brooks 
identifies complexity as one of the essential properties of software.  \begin{quote}
{\em Software entities are more complex 
for their size than perhaps any other human construct\ldots The complexity of software is an essential 
property, not an accidental one.\ldots [D]escriptions of a software entity that abstract away its complexity 
often abstract away its essence.}\end{quote}
Representing 
all properties of software entities (their developers, their development method, the artifacts they produce)
is a complex task.   Such complexity places 
comprehension of large scale software above the abilities of individuals; hence, analysis tools are needed to 
support developers in such tasks.  

Data mining research in software engineering has  managed to avoid this complexity by focusing on very simple models and very
simple learning methods. For example, previously~\cite{me07b},  we have employed Naive Bayes classifiers to find defect patterns
from static code attributes.  None of the algorithms used in that work were slow:
code attributes can be extracted in linear time, and Naive Bayes classifiers  use 
very little computational resources (linear time training and tiny memory requirements).

However, just the fact that our prior work ran fast enough
does not offer much confidence for the future.
In October 2008, we visited Google to report some the results we'd obtained from the PROMISE 
datasets\footnote{\url{http://www.youtube.com/watch?v=vrvRsZsoMp8}}. 
The alarming conclusion from that site visit was that it was now an open and urgent question to optimize our
data mining methods.
Google developers work within an architecture that delivers many small applications to the web.
Each of these smaller applications are 
developed by hyper-agile teams. Every one to two weeks, these teams update their code but the teams do not
synchronize their update schedules. That is, at any moment, the
live Google code base can change.  To help software engineers in
these conditions of extreme agility, we need data mining
analyses that run in minutes, not hours.

Given the commercial success and prominence of Google, we expect
Google's development practices to be copied.
That is, in the very near future, it will be necessary that our
data mining methods continually update their models for
large code bases.
For certain classes of model learning, our current technology is
too slow to keep up with such a high rate of change.
For example,
consider the task of constructing {\em coverage models}:
\bi
\item
Unit testing
is  the testing of a group $M$ of {\em target methods}.
\item
{\em Coverage models} control unit tests
and select the sequence of calls to the target methods,
the parameters of each call
and the receiver\footnote{
  We use the word ``receiver'' to refer to the object that
  a method is called on.  For instance, in the Java method
  call ``{\tt t.add(3)}'', the receiver is {\tt t}.
} of each call.
\item
Each call may be 
preceded by code that sets up the arguments 
and may be followed by code that
stores and checks results. 
\ei
{\em Randomized unit testing} uses coverage models that contain
a bias on the random variables
which select for the
target method call sequence and/or 
arguments to the method calls. 
Many researchers~\cite{doong-frankl-tosem94,antoy-hamlet-tse-jan2000,%
claessen-hughes-quickcheck,pacheco-etal-icse2007}
have built such randomized coverage models, sometimes combined with 
other tools such as model checkers. 

However, these coverage models can also be learned.
Previously~\cite{andrews07}, we have developed Nighthawk, a genetic algorithm (GA)  for learning randomized coverage models.
Nighthawk is a ``wrapper'' system that automates the construction of test scripts.
Wrapper-based unit test generators are simpler to implement than
(say) test generators that use model checkers~\cite{visser-etal-issta06} 
or static code analysis since these
require access to a robust and complex parser
and source code analyzers.
These complex tools are not often
provided by language providers and, if they are, they may not be
updated to reflect recent changes
in the source language.  
Nighthawk, on the other hand, 
does not require source code or bytecode analysis,
instead depending only on the robust Java reflection mechanism
and commonly-available coverage tools.
For instance, our code was
initially written with Java 1.4 in mind, but worked seamlessly
on the Java 1.5 versions of the {\tt java.util} classes, despite
the fact that the source code of many of the units had been
heavily modified to introduce templates.  

Nighthawk meets, and surpasses, the {\em Cornett threshold}~\cite{cornett-minimum-coverage}; i.e.
 ``code coverage of 70-80\% 
is a reasonable goal for system test of most projects with most coverage metrics''. 
Using a novel {\em value-pool} approach to coverage models, and running over the
Java classes of \fig{results0}a, Nighthawk: 
\bi
\item Achieves median coverage of 93\% (measured in line coverage, see \fig{results0}b).
\item Achieves  much higher coverage  than  other GA methods 
that ignore value pools~\cite{michael-etal-ga-tcg} 
(measured in terms of condition/decision coverage);
\item Achieves similar coverage to other test coverage generators that use symbolic execution~\cite{andrews07}.
\ei
Hence, we prefer Nighthawk's wrappers to symbolic methods since wrappers
can be adapted to new languages faster than symbolic
execution methods.

Even though Nighthawk is a successful tool, it is still too
slow to handle large code bases developed in an agile manner.
As shown in \fig{results0}c, Nighthawk's runtimes are usually in the order to $10^2$ seconds per class.
The goal of our current work  is to speed up Nighthawk by two orders of magnitude\footnote{Of course, even faster
would be even better but given our current case study library (\fig{results0}a), any speed up beyond $10^2$ 
would become hard to detect. Before exploring $10^3$ speedups,
we would need to switch to much larger case studies.}.

The rest of this paper discusses experiments with feature subset selection (FSS) and genetic algorithms (GAs). We will show that
the RELIEF feature subset selector~\cite{Kononenko97} consistently rejects 60\% of our mutator
operators over all the cases studies of \fig{results0}a. This results
in a {\em much larger} speedup than 60\% since the search space of a genetic
algorithm is exponential on the number of mutators. 
%When we compare the runtimes and coverage achieved using all our mutators
%or just the 40\% selected by RELIEF, we find that the reduced mutation set
%
Empirically we find that 
when we just use
the mutators selected by RELIEF, we can usually (in 12 cases of 16) reach
94\% of the coverage  seen with all mutators, ten times as quickly.
The {\em Future Work} section
of this paper proposes an incremental feature subset selection method
that might win us another order of magnitude speed improvement (but this
has yet to be tested).
That is, we can report good progress in our goal
to achieving a speed up of $10^2$. 

The rest of this paper is structured as followed.  Section 2
discusses related work.  Section 3 describes the Nighthawk test
input generation system. Section 4 describes how we applied
feature subset selection (FSS) to data collected from Nighthawk
in order to determine how best to optimize it.  Section 5 explores
future work; Section 6 concludes.

Note one digression before continuing.
To enhance availability of the software,
Nighthawk uses the popular open-source coverage tool Cobertura
\cite{cobertura-website} to measure coverage.  Cobertura can measure
only line coverage (each coverage point corresponds to a source
code line, and is covered if any code on the line is executed)\footnote{
  Cobertura (v.\ 1.8) also reports what it calls ``decision coverage'',
  but this is coverage of lines containing decisions.
}.
However, Nighthawk's algorithm is not specific to this measure;
indeed, our other empirical studies~\cite{andrews07} show that Nighthawk
performs well when using other coverage measures.


\input{related}


\begin{figure}[tp]
\centering
%\includegraphics[width=2.5in]{myfigure.eps}
\includegraphics[width=3in]{xyPlot.pdf}
\caption{Spiky search space: the region $x=y$ is very narrow. }
\label{spiky-search-space-fig}
\end{figure}

\begin{figure}[tp]
\centering
%\includegraphics[width=2.5in]{myfigure.eps}
\includegraphics[width=3in]{lohiPlot.pdf}
\caption{Smooth search space resulting from value pools.}
\label{smooth-search-space-fig}
\end{figure}

\begin{figure}[tp]
\begin{alltt}\scriptsize
     Without value pools         With value pools
     -------------------         ----------------
     a = f1();                   a = f1();
     b = f2();                   x = f4(a);
     c = f3();                   y = f5(x);
     x = f4(a);                  z = f6(y);
     y = f5(b);
     z = f6(c);
\end{alltt}
\caption{Unit tests without value pools (left) and with value pools (right).}\label{fig:pools}
\end{figure}

\section{Nighthawk}
This section describes how the results in \fig{results0}
were generated using Nighthawk.  We first discuss the notion of
``value pool'', which Nighthawk uses to maintain candidate data
for test cases.  We then describe the genetic algorithm (GA)
used by Nighthawk, and finally the algorithm used to randomly
generate test data, which is based on the model discovered by
the GA.

% The next section discusses how we apply feature subsection
%selection to a log of Nighthawk's behaviour to learn
%what parts of the Nighthawk architecture can be discarded.

\newpage
\subsection{Value Pools}
The core innovation in Nighthawk is that of {\em value pools}.
Value pools are a space of variables shared between methods in a unit test.
The sharing of variables has an interesting effect on the viability of 
randomized unit test generators like Nighthawk. 

To understand this effect,
consider the problem of generating two input values
$x$ and $y$ that will cover the true direction of the decision
``$x=y$''.  If we cast the problem as a search for the
two values themselves, and the score as whether we have found
two equal values, the search space is shaped as in
Figure \ref{spiky-search-space-fig}: a flat plain
of zero score
with spikes along the diagonal.  Most approaches
to GA white-box test data generation attempt to address this
problem by proposing fitness functions that detect ``how close''
the target decision is to being true, often using analysis-based
techniques.  For instance, Michael et al.\ \cite{michael-etal-ga-tcg}
use fitness functions that specifically take account of such
conditions by measuring how close {\tt x} and {\tt y} are.
Watkins and Hufnagel \cite{watkins-hufnagel-fitness} enumerate
and compare fitness functions proposed for GA-based test case
generation.

Now consider a random search for values satisfying $x=y$ when
$x$ and $y$ are calculated using value pools, where each value
pool contains variables between the values $lo$ and $hi$. The reuse of
variables for a shared pool increases the probability of a
choosing the same value for $x$ and $y$, resulting in a
search space more like Figure \ref{smooth-search-space-fig}.

Generalizing this to method calls in general, without value
pools, every value on the unit test on the left-hand side of
\fig{pools} comes from a different source.
With value pools, we create fewer and share more variables. In
the right-hand side revision of the unit test of \fig{pools},
the arguments to each function have a higher probability of
coming from the results of prior function calls.  Note that now
there is a dependency between $x$ and $z$ (via $y$).
Our search space is therefore more like Figure
\ref{smooth-search-space-fig} and there is an increasing
chance that random search will stumble on the sequence of
calls that will achieve high coverage of the methods under test.

\begin{figure*}[tp]
\scriptsize
\begin{center}
\begin{tabular}{|l|l|c|l|}
Gene type & Occurrence & Type & Description \\
\hline
\parbox[t]{1.4in}{\tt numberOfCalls}
  & \parbox[t]{2in}{One for whole chromosome}
  & int
  & \parbox[t]{2in}{the number $n$ of method calls
                    to be made\vspace{1mm}} \\
% that
%                 {\sf constructRunTestCase} is to run} \\
\hline
\parbox[t]{1.4in}{\tt methodWeight}
  & \parbox[t]{2in}{One for each method $m \in I_M$}
  & int
  & \parbox[t]{2in}{The relative weight of the method, i.e.\ the
                    likelihood that it will be chosen\vspace{1mm}} \\
%                at step 4(a)
%                of {\sf constructRunTestCase}} \\
\hline
\parbox[t]{1.4in}{\tt numberOfValuePools}
  & \parbox[t]{2in}{One for each type $t \in C_M$}
  & int
  & \parbox[t]{2in}{The number of value pools for that type\vspace{1mm}} \\
\hline
\parbox[t]{1.4in}{\tt numberOfValues}
  & \parbox[t]{2in}{One for each value pool of each type $t \in C_M$
                 except for {\tt boolean}\vspace{1mm}}
  & int
  & \parbox[t]{2in}{The number of values in the pool} \\
\hline
\parbox[t]{1.4in}{\tt chanceOfTrue}
  & \parbox[t]{2in}{One for each value pool of type {\tt boolean}}
  & int
  & \parbox[t]{2in}{The percentage chance that the value {\it true} will be
                 chosen from the value pool\vspace{1mm}} \\
\hline
\parbox[t]{1.4in}{\tt lowerBound, upperBound}
  & \parbox[t]{2in}{One for each value pool of each
                 range primitive type $t \in C_M$}
  & \parbox[t]{0.5in}{int or float}
  & \parbox[t]{2in}{The lower and upper bounds on values in the pool;
                 initial values are drawn uniformly from this range\vspace{1mm}} \\
\hline
\parbox[t]{1.4in}{\tt chanceOfNull}
  & \parbox[t]{2in}{One for each argument position of non-primitive type
                 of each method $m \in I_M$}
  & int
  & \parbox[t]{2in}{The percentage chance that {\tt null} will be chosen
                 as the argument\vspace{1mm}} \\
\hline
\parbox[t]{1.4in}{\tt candidateBitSet}
  & \parbox[t]{2in}{One for each parameter and quasi-parameter of
                    each method $m \in I_M$}
  & BitSet
  & \parbox[t]{2in}{Each bit represents one candidate type, and signifies
                 whether the argument will be of that type\vspace{1mm}} \\
\hline
\parbox[t]{1.4in}{\tt valuePoolActivityBitSet}
  & \parbox[t]{2in}{One for each candidate type of each parameter
                    and quasi-parameter of each method $m \in I_M$}
  & BitSet
  & \parbox[t]{2in}{Each bit represents one value pool, and signifies
                 whether the argument will be drawn from that value
                 pool\vspace{1mm}} \\
\hline
\end{tabular}
\end{center}

\caption{Nighthawk gene types.}
\label{fig:gene-types-fig}
\end{figure*}

\subsection{Genetic Algorithm}

Nighthawk is given a set $M$ of target methods, and finds values
for genes that control randomized test data creation.
% We refer to $M$ as the set of ``target methods''.
We define the
set $I_M$ of {\it types of interest} corresponding to $M$ as the
union of the following sets of types\footnote{
  In this paper, the word ``type'' refers to any primitive type,
  interface, or abstract or concrete class.
}:
\bi
\item All types of receivers, parameters and return values of methods in $M$.
\item All primitive types that are the types of parameters
  to constructors of other types of interest.
\ei
Each type $t \in I_M$
is associated with an array of {\it value pools}, and each
value pool for $t$ contains an array of values of type $t$. 
Each value pool for a range primitive type (a primitive type
other than {\tt boolean} and {\tt void}) has bounds on
the values that can appear in it.  The number of value pools,
number of values in each value pool, and the range primitive
type bounds are specified by genes.

We define a constructor to be a {\it reinitializer} if it has no
parameters, or if all its parameters are of types in $I_M$.
We define the set $C_M$ of {\it callable methods} to be the
methods in $M$ plus the reinitializers of the types in $I_M$.
The callable methods are the ones that Nighthawk calls directly.

Nighthawk's genetic algorithm finds values for genes of various
types; each gene type corresponds to zero or more genes of that
type.  One type of gene 
represents $n$ (the number of method calls in
this unit test) while another type selects the number of
value pools for each datatype in $I_M$.
Yet another gene type selects the size of value pool
for each datatype.
The number of genes of each type thus varies according to the
properties of the software unit under test.
For example, \fig{gene-types-fig} shows that the
{\em methodWeight} gene type is repeated for each method in $M$. 

The vector of all genes and their values is the {\em chromosome}
used by Nighthawk.
Our GA operates on this chromosome via the usual steps of chromosome
evaluation, fitness selection, mutation and recombination.
The GA first derives an
initial template chromosome appropriate to $M$, constructs
an initial population of size $p$ as clones of this chromosome, and
mutates the population.  It then performs a loop, for
the desired number $g$ of generations, of evaluating each
chromosome's fitness, retaining the fittest chromosomes,
discarding the rest, cloning the fit chromosomes, and mutating
the genes of the clones with probability $m$\% using point mutations and
crossover (exchange of genes between chromosomes).
The {\it fitness function} for a chromosome is calculated using the 
Cobertura coverage tool (discussed in the introduction):
generally, chromosomes that cause the generation of test cases
that achieve higher coverage are evaluated as being more fit.
%; that is, as
%\begin{center}
%(number of coverage points covered) $*$ (coverage factor) \\
% $-$ (number of method calls)
%\end{center}

%It is recognized that the design of genetic algorithms is a
%``black art'' \cite{ga-blackart}, and that very little is known
%about why GAs work when they do work and why they do not work
%when they do not.
Nighthawk uses default settings of
$p=20, g=50, m=20$. These settings are different from those
taken as standard in GA literature \cite{dejong-spears-genetic},
and are motivated by a need to do as few chromosome evaluations
as possible (the primary cost driver of the system).  The
settings of other variables, such as the retention percentage,
are consistent with the literature.

% XXX have to say coverage models
\subsection{Nighthawk}

Here we present a simplified description of
Nighthawk's coverage-model-based test case generation.
The algorithm takes two
parameters:  a set $M$ of Java methods, and a GA
chromosome $c$ appropriate to $M$.  The chromosome controls
aspects of the algorithm's behaviour, such as the number of
method calls to be made, as described in the previous subsection.

The algorithm first chooses initial values for primitive type
pools, and then moves on to non-primitive type pools.
A {\it call description} is an object representing one method
call that has been constructed and run.  It consists of the
method name, an indication of whether the method call succeeded,
failed or threw an exception, and one {\it object description}
for each of the receiver, the parameters and the
result (if any).
%The object description of an object of primitive type or a
%string consists of the object itself.  The object description of
%other objects consists of the class of interest, the value pool
%number and the value number associated with the object; this is
%the source from which the object came (for receivers and
%parameters) or the place where the value was put (for results).
A {\it test case} is a sequence of call descriptions, together
with an indication of whether the test case succeeded or failed.

\begin{figure}[tp]
\scriptsize
Input:  a set $M$ of target methods; a chromosome $c$. \\
Output:  a test case. \\
Steps:
\be
\item For each element of each value pool of each primitive
  type in $I_M$, choose an initial value that is within the bounds
  for that value pool.
\item For each element of each value pool of each other type $t$
  in $I_M$:
  \be
  \item If $t$ has no initializers, then set the element to {\tt null}.
  \item Otherwise, choose an initializer method $i$ of $t$, call
    {\sf tryRunMethod}$(i, c)$, and place the result in the
    destination element.
   \ee
\item Initialize test case $k$ to the empty test case.
\item Repeat $n$ times, where $n$ is the number of method calls to
  perform:
   \be
  \item Choose a target method $m \in C_M$.
  \item Run algorithm {\sf tryRunMethod}$(m, c)$, and
        add the call description returned to $k$.
  \item If {\sf tryRunMethod} returns a method call failure
    indication, return $k$ with a failure indication.
  \ee
\item Return $k$ with a success indication.
\ee

\caption{Algorithm {\sf constructRunTestCase}.}
\label{constructRunTestCase-fig}
\end{figure}

\begin{figure}[tp]
\scriptsize
Input:  a method $m$; a chromosome $c$. \\
Output:  a call description. \\
Steps:
\be
\item If $m$ is non-static and not a constructor:
    \be
  \item Choose a type $t \in I_M$ which is a subtype of the receiver of $m$.  
  \item Choose a value pool $p$ for $t$.
  \item Choose one value $recv$ from $p$ to
    act as a receiver for the method call.
   \ee
\item For each argument position to $m$:
   \be
  \item Choose a type $t \in I_M$ which is a subtype of the argument type.
  \item Choose a value pool $p$ for $t$.
  \item Choose one value $v$ from $p$ to act as the argument.
   \ee
\item If the method is a constructor or is static, call it with
  the chosen arguments.  Otherwise, call it on $recv$ with the
  chosen arguments.
\item If the method call threw an {\tt AssertionError},
  return a call description with a failure indication.
\item Otherwise, if the method call threw some other exception,
  return a call description with an exception indication.
\item Otherwise, if the method return type is not {\tt void},
  and the return value $ret$ is non-null:
   \be
  \item Choose a type $t \in I_M$ which is a supertype of the
    type of the return value.
  \item Choose a value pool $p$ for $t$.
  \item If $t$ is not a primitive type, or if $t$ is a primitive
    type and $ret$ does not violate the bounds on
    $p$, then choose an element of $p$ and
    replace it by $ret$.
  \item Return a call description with a success indication.
   \ee
\ee

\caption{Algorithm {\sf tryRunMethod}.}
\label{tryRunMethod-fig}
\end{figure}

Nighthawk's randomized testing algorithm is referred to as
{\sf constructRunTestCase}, and is described in Figure
\ref{constructRunTestCase-fig}.  It takes a set $M$ of target
methods and a chromosome $c$ as inputs.  It begins by
initializing value pools, and then constructs and runs a
test case, and returns the test case.  It uses an auxiliary
method called {\sf tryRunMethod}, described in Figure
\ref{tryRunMethod-fig}, which takes a method as input,
calls the method and returns a call description.
In the algorithm descriptions, the word ``choose'' is always used
to mean specifically a random choice which may partly depend on
the chromosome $c$.

{\sf tryRunMethod} considers a method call to fail if and only
if it throws an {\tt AssertionError}.  It does not consider
other exceptions to be failures, since they might be correct
responses to bad input parameters.  A separate mechanism
is used for detecting precondition violations and checking
correctness of return values and exceptions.
% XXX reference now broken
%; see
%Section \ref{test-wrappers-section}.

%For conciseness, the algorithm descriptions omit some details
%which we now fill in.  These concern the treatment of nulls, the
%treatment of {\tt String}, and the treatment of {\tt Object}.
%
%The receiver of a method call cannot be null, and no parameter
%can be null unless {\sf tryRunMethod} chooses it to be.  If
%{\sf tryRunMethod} fails to find a non-null value when it is
%looking for one, it reports failure of the {\it attempt} to call the
%method.  {\sf constructRunTestCase} tolerates a certain number
%of these attempt failures before terminating the
%test case generation process.
%
%{\tt java.lang.String} is treated as if it is a primitive type,
%the values in the value pools being initialized with ``seed
%strings''.  Some default seed strings are supplied by the
%system, and the user can supply more.
%
%\label{object-section}
%Formal parameters of type {\tt java.lang.Object} stand
%for some arbitrary object, but it is usually sufficient
%to use a small number of specific
%types as actual parameters;
%Nighthawk uses only {\tt int} and {\tt String} by default.
%A notable exception to this rule is the parameter to the {\tt equals()}
%method, which can be treated specially by Nighthawk's test wrapper objects.
%% XXX reference now broken
%%(see Section \ref{test-wrappers-section}).

\subsection{Generation of Results}

We ran Nighthawk on each of the subject units in \fig{results0}a,
all taken from the standard {\tt java.util} library, version 1.5.
The amount of coverage achieved by the ``winning'' chromosome
on the units is graphed against unit SLOC in \fig{results0}b,
and the amount of time taken to achieve highest coverage is
graphed against unit SLOC in \fig{results0}c.  Note that there
is no particular pattern in the runtimes.  For more details,
see Andrews et al.\ \cite{andrews07}.

This concludes our notes on how \fig{results0} was generated.
The rest of this paper concerns how to optimize the above process.

\section{Feature Subset Selection}

Here we describe the work that we have done to optimize
Nighthawk's GA and test case generation using feature subset
selection (FSS).  We first give some motivation, and then describe
the data collection and initial FSS
analysis of Nighthawk.  We then describe the efficiency study
that we carried out based on the information from FSS,
with respect to both coverage and time.

\subsection{Motivation}

The size of the search space of a GA is the product of all
possible values for all parts of a chromosome.
The run time cost to find the best possible chromosome
is therefore proportional to
this value times the evaluation cost of each chromosome:
\begin{equation}\label{eq:cost}
cost = R^L * eval
\end{equation}
That is, a chromosome of length $L=20$ with binary choices
(so the range of each choice is $R=2$)
takes $2^{10}>1,000$ times longer to run than a chromosome of
length 10 to achieve the same quality of result.
Nighthawk's chromosomes store information related to the gene
types of \fig{gene-types-fig}.
If we could discard some of those gene types, then the above reasoning
suggests that this
would lead to an exponential improvement in Nighthawk's runtimes.

One tool for removing needless information is {\em feature
subset selection} (FSS).
A repeated result in the data mining community is that simpler
models with  equivalent or higher performance can be built via FSS,
algorithms that intelligently
prune useless features \cite{hall03}. Features may be pruned for
several reasons: 
\bi
\item They may be noisy, i.e. contain spurious signals unrelated
  to the target class; 
\item They may be uninformative, e.g. contain mostly one value,
  or no repeating values;
\item They may be correlated to other variables; i.e.
  they can be pruned since their signal is also present in other
  variables.
\ei

The reduced feature set has many advantages:
\bi
\item Miller has shown that models generally containing fewer
  variables have less variance in their outputs \cite{miller02}.
\item The smaller the model, the fewer are the demands on
  interfaces  (sensors and actuators) to the external environment.
  Hence, systems designed around  small models are easier to use
  (less to do) and cheaper to build.
\item
  As argued above, for GAs a {\em linear} decrease in the number of
  chromosomes could lead to an exponential decrease in runtimes.
% Nighthawk chromosomes could theoretically lead to
% an exponential decrease in the Nighthawk runtimes.
\ei

The literature lists many feature subset selectors.  
In the WRAPPER method, a {\em target learner} is augmented with a
pre-processor that uses a heuristic search to grow subsets of the
available features. At each step in the growth, the target learner
is called  to find the accuracy of the model learned from the
current subset. Subset growth is stopped when the addition of new
features does not improve the accuracy. 
Kohavi and John \cite{kohavi97} report experiments with WRAPPER
where 83\% (on average) of the measures in a domain could be
ignored with only a minimal loss of accuracy.

The advantage of the WRAPPER approach is that, if some target
learner is already implemented, then the WRAPPER is simple to
implement. The disadvantage of the wrapper method is that each
step in the heuristic search requires another call to the target
learner. Since there are many steps in such a search ($N$
features have $2^N$ subsets), WRAPPERs may be too slow.

Another feature subset selector is RELIEF.  
This is an instance based learning scheme \cite{Kir92,Kon94}
that works by randomly sampling one instance within the data. It
then locates the nearest neighbors for that instance from not
only the same class but the opposite class as well. The values
of the nearest neighbor features are  then compared to that of
the sampled instance and the feature scores are maintained and
updated based on this. This process is specified for some
user-specified $M$ number of instances. RELIEF can handle noisy
data and other data anomalies by averaging the values for $K$
nearest neighbors of the same and opposite class for each
instance \cite{Kon94}. For data sets with multiple classes, the
nearest neighbors for each class that is different from that of the
current sampled instance are selected and the contributions are 
determined by using the class probabilities of the class in the dataset.

The experiments of Hall and Holmes \cite{hall03} reject numerous
feature subset selection methods.  WRAPPER is their preferred
option, but only for small data sets.  For larger data sets, the
stochastic nature of RELIEF makes it a natural choice.

%Another reason to prefer RELIEF is that it can take advantage
%of Nighthawk's stochastic search.  Currently, RELIEF is a
%batch process that is executed after data generation is
%completed.  However, it may not be necessary to wait till the end
%of data generation to gain insights into which features are most
%relevant.  Given the stochastic nature of the algorithm, we can
%see feature work where RELIEF and a genetic algorithm work in
%tandem.  Consider the random selection process at the core of
%RELIEF: a genetic algorithm exploring mutations of the current
%set of parents is an excellent stochastic source of data.  In
%the future, we plan to apply RELIEF incrementally and in
%parallel to our GAs.
%

\subsection{Initial FSS Analysis of Nighthawk}

We instrumented Nighthawk so that every time a chromosome was
evaluated, it printed the current value of every gene and the
final fitness function score.  (For the two BitSet gene types,
we printed only the cardinality of the set.)
For each of the 16 Collection and Map classes from {\tt java.util},
we ran Nighthawk for 40 generations.  Each class therefore
yielded 800 observations, each consisting of a gene value vector
and the chromosome score.

%RELIEF assumes continuous data and Nighthawk's performance
RELIEF assumes discrete data and Nighthawk's performance
scores are continuous.  To enable feature subset selection, we
first discretized Nighthawk's output. A repeated pattern
across all our experiments is that the Nighthawk scores fall
into three regions:
\bi
\item The 65\% majority of the scores are within 30\% of the top
  score for any experiment. We call this the {\em high plateau}.
\item A 10\%  minority of scores are less than 10\% of the maximum
  score.  We call this region {\em the hole}.
\item After the high plateau there is a  {\em slope} of
  increasing gradient that falls into {\em the hole}. This {\em
  slope} accounds for 25\% of the results.
\ei
Accordingly, to select our features, we sorted the results and
divided them into three classes: bottom 10\%, next 25\%, remaining
65\%. RELIEF then found the subset of features that distinguished
these three regions.  

Using the above discretization policy, we ran RELIEF 10 times in a 10-way
cross-validation study.
The data set was divided
into $10$ buckets. Each bucket was (temporarily) removed and RELIEF was
run on the remaining data. This produced a list of ``merit'' figures for
each feature (this ``merit'' value is an internal heuristic measure
generated from RELIEF, and reflects the difference ratio of neighboring
instances that have different regions).  We therefore got
a merit score for each of the ten runs for every gene corresponding
to every subject unit.  Each run therefore yielded a ranked list
$R$ of all genes, where gene 1 had the highest merit for this
run, gene 2 had the second highest merit, and so on.

We then calculated various summary statistics in order to come
up with rankings of the various gene types (recall that each
gene type $t$ corresponds to zero or more genes, depending on the
unit under test).
\begin{itemize}
\item $avgMerit(g,u)$ is the average RELIEF merit score, across all
  10 runs of the cross-validation study, of gene $g$ derived
  from unit $u$.
\item $avgRank(g,u)$ is the average rank in $R$, across all
  10 runs of the cross-validation study, of gene $g$ derived
  from unit $u$.
\item $bestMerit(t)$ is the maximum, over all genes $g$ of
  type $t$ and all subject units $u$, of $avgMerit(g,u)$.
\item $bestRank(t)$ is the maximum, over all genes $g$ of
  type $t$ and all subject units $u$, of $avgRank(g,u)$.
\end{itemize}
We took these summary numbers as indications of the possible
relative expendibility of the various different gene types.
For example, \fig{genes-merit-fig} shows the ten gene types from
\fig{gene-types-fig}, ranked in terms of their best merit as
defined above.  This ranking places {\tt candidateBitSet} at
the top, meaning that it considers genes of that type to be the
most valuable; it also places {\tt lowerBound} at the bottom,
meaning that it considers genes of that type to be the most
expendible.

% We took the maximum merit ($Max$)
%and generated a {\it Selected} list. A feature was {\it Selected} if its merit
%$m$ was $m> \alpha Max$ (e.g. at $\alpha=0.5$ then we selected all
%features that score at least half the maximum merit).
%
%We 
%
%The features in a Nighthawk chromosome come from the different
%gene types of  \fig{gene-types-fig}.
%We ranked and sorted each gene type using the maximum RELIEF
%merit score seen for any of its features.
%This resulted in the sort order of  \fig{genes-merit-fig}.

\begin{figure}[tp]
\scriptsize
\begin{center}
\begin{tabular}{r|rl}
Rank &Gene type $t$  & $bestMerit(t)$ \\
\hline
1&{\tt candidateBitSet}			& 0.373 \\
2&{\tt upperBound}			& 0.267 \\
3&{\tt valuePoolActivityBitSet}		& 0.267 \\
4&{\tt numberOfCalls}			& 0.195 \\
5&{\tt numberOfValuePools}		& 0.186 \\
6&{\tt chanceOfNull}			& 0.166 \\
7&{\tt numberOfValues}			& 0.160 \\
8&{\tt chanceOfTrue}			& 0.150 \\
9&{\tt methodWeight}			& 0.144 \\
10&{\tt lowerBound}			& 0.129 \\
\end{tabular}
\end{center}

\caption{
Nighthawk gene types, sorted by the maximum RELIEF merit of any of its features.
}
\label{fig:genes-merit-fig}
\end{figure}

\subsection{Efficiency Study}

After ranking the gene types by the various ranking metrics, we
proceeded to study whether eliminating gene types on the basis
of the RELIEF results sped up Nighthawk without sacrificing
the quality of the results.

First, we instrumented the source code so that we could
selectively replace the parts of Nighthawk's code controlled by
each gene type by code that assumed a constant value for each
gene of that type.  This allowed us to ``turn off'' all genes of
a given type.

We then ran Nighthawk using the top ranked
$1 \le i \le 10$ gene types according to two rankings: the
ranking by $bestMerit$ shown in \fig{genes-merit-fig}, and the
ranking by $bestRank$.  For example, in the following
experiments, if we say ``number of gene types = 2'' for the
$bestMerit$ ranking, then we are
using only {\tt candidateBitSet} and {\tt upperBound}, and
all other gene types are turned off.

%
%\begin{figure}[!t]\begin{center}\includegraphics[width=2.5in]{Properties_rankedByMerit.pdf}
%\end{center}\caption{Properties}\label{fig:properties}
%\end{figure}

\begin{figure}[tp]
\begin{center}\includegraphics[width=3.5in]{Hashtable_rankedByMerit.pdf}
\end{center}\caption{
  Nighthawk on Hashtable unit, eliminating gene types according
  to $bestMerit$ ranking.
}
\label{fig:hashtable}
\end{figure}

\begin{figure}[tp]
\begin{center}\includegraphics[width=3.5in]{Hashtable_rankedByAvgRank.pdf}
\end{center}\caption{
  Nighthawk on Hashtable unit, eliminating gene types according
  to $bestRank$ ranking.
}
\label{fig:hashtable-bestRank}
\end{figure}

%\begin{figure}\begin{center}\includegraphics[width=2.5in]{EnumMap_rankedByMerit.pdf}
%\end{center}\caption{EnumMap}\label{fig:enummap}
%\end{figure}
%

\subsubsection{Coverage Analysis}

In the following, the result of each run is always compared to
the runtime and coverage seen using all ten gene types and
running for $g=50$ generations.  \fig{hashtable} shows how the
coverage changed over one of the case studies of \fig{results0},
using the $bestMerit$ ranking; the results for this subject unit
are typical.  The y-axis of that figure is defined such that
the point (50,1) represents the coverage reached by using all 10
gene types after 50 generations.  The thick black curve on those
figures shows the performance of Nighthawk using all ten gene
types. The other curves show results from using $1 \le i \le 9$
gene types.   The corresponding plot for the $bestRank$ ranking
is shown in \fig{hashtable-bestRank}.

A performance measure of interest in \fig{hashtable} is the area
under the curves.  This area is maximal when Nighthawk converges
to maximum coverage in only a few generations.  Note that due to
the random nature of the GA and the randomized test data
generation, some of the curves are sometimes higher than the
$i=10$ line.


\begin{figure}[tp]
\scriptsize
\begin{center}
\begin{tabular}{r@{~}r@{~}r@{~}r@{~}r@{~}r@{~}r@{~}r@{~}r@{~}r|l}
\multicolumn{9}{c}{Number of used gene types}\\\cline{1-10}
1    &  2   &   3 &   4   &  5   & 6    & 7    & 8    &  9  & 10    & class being tested\\\hline

 .91 &  .92 &  .92 & 1.00 & 1.01 & 1.01 & 1.01 & 1.01 & 1.00 & 1.00 & Hashtable\\
 .89 &  .89 &  .90 & 1.01 & 1.01 & 1.00 &  .99 & 1.01 & 1.01 & 1.00 & ArrayList\\
1.21 & 1.11 & 1.19 & 1.20 & 1.21 & 1.57 & 1.13 & 1.32 & 1.29 & 1.00 & EnumMap\\
 .83 &  .86 &  .85 &  .98 &  .99 & 1.00 & 1.00 & 1.00 &  .98 & 1.00 & HashMap\\
 .92 &  .91 &  .92 & 1.01 &  .99 & 1.00 & 1.01 & 1.00 &  .99 & 1.00 & HashSet\\
 .86 &  .88 &  .89 & 1.01 & 1.00 & 1.01 & 1.02 & . 99 &  .99 & 1.00 & IdentityHashMap\\
 .84 &  .86 &  .84 & 1.02 & 1.01 & 1.01 & 1.01 & 1.00 & 1.02 & 1.00 & LinkedHashMap\\
 .93 &  .93 &  .94 & 1.01 & 1.01 & 1.01 & 1.01 & 1.01 & 1.01 & 1.00 & LinkedHashSet\\
 .93 &  .92 &  .92 & 1.01 & 1.00 & 1.01 & 1.00 & 1.00 & 1.01 & 1.00 & LinkedList\\
 .87 &  .87 &  .88 & 1.02 & 1.00 & 1.01 & 1.02 & 1.05 & 1.05 & 1.00 & PriorityQueue\\
 .99 &  .97 &  .99 & 1.00 & 1.00 & 1.01 & 1.00 & 1.00 & 1.00 & 1.00 & Properties\\
 .94 &  .93 &  .93 & 1.01 & 1.01 & 1.01 & 1.00 & 1.01 & 1.01 & 1.00 & Stack\\
 .75 &  .78 &  .77 &  .98 &  .98 &  .99 & 0.90 & 1.00 &  .98 & 1.00 & TreeMap\\
 .82 &  .81 &  .82 & 1.01 &  .99 & 1.03 & 1.02 & 1.01 & 1.00 & 1.00 & TreeSet\\
 .77 &  .82 &  .77 & 1.01 & 1.00 & 1.04 & 1.02 & 1.03 & 1.01 & 1.00 & Vector\\
 .87 &  .89 &  .87 & 1.01 & 1.00 & 1.03 & 1.00 &  .99 & 1.01 & 1.00 & WeakHashMap\\\hline
 .90 &  .90 &  .90 & 1.02 & 1.01 & 1.05 & 1.01 & 1.03 & 1.02 & 1.00& mean
\end{tabular}
\end{center}
\caption{Coverage found using the top $1i$ ranked gene types for $0 \le i \le 9$
Coverages expressed as a ratio of the coverages found using all gene types
}\label{fig:coverage}
\end{figure}

If we calculate the ratio of the area under
a curve with the area under the thick
black curve, then we can summarize all the curves of
\fig{hashtable} as the first row of \fig{coverage}. In that
figure, each column shows how many gene types were used in  a
particular run (and when $used=10$, we are ignoring the FSS
results and using all gene types). Also, the number 1.00 informs
us that we achieved 100\% of the coverage reached by using all
ten gene types.

\fig{coverage} summarizes \fig{hashtable} as well as results
from all other cases studied in \fig{results0}a.  The coverage
is less than one for columns (1,2,3) but predominantly equal to
or greater than one for columns (4-10). From this observation,
we conclude that Nighthawk's GA need only use the top four
ranked gene types of \fig{genes-merit-fig}.  The results for
the $bestRank$ ranking are less useful, as suggested by
\fig{hashtable-bestRank}:  by that ranking, the top six gene
types are needed for performance that comes close to all ten
gene types.

We note that in both the study using the $bestMerit$ ranking and
that using the $bestRank$ ranking, the coverage achieved after
50 generations dropped off significantly at the point that we
turned off the {\tt numberOfCalls} gene.  This suggests that the
{\tt numberOfCalls} gene may be more important than is suggested
by either the $bestMerit$ ranking or the $bestRank$ ranking.  We
plan in the future to consider other rankings of genes, in an
attempt to find a ranking that best identifies the most useful
gene types.

\subsubsection{Time Analysis}

\begin{figure*}[tp]
\begin{center}
\includegraphics[width=5in]{timereport.pdf}
\end{center}
\caption{Time results, 4 vs 10.}\label{fig:timereport100}
\end{figure*}

In order to determine whether eliminating gene types from
Nighthawk's GA is cost-effective, we must consider not only the
coverage achievable, but also the time taken to achieve that
coverage.  We therefore made two runs of Nighthawk on all the
subject units, run
(a) using all the gene types and run (b) using just the top four gene
types ranked by $bestMerit$.
We then divided the runtime and coverage results
from (b) by the (a) values seen after 50
generations, and plotted the results.

\fig{timereport100} shows the results, with time percentage on
the X axis and coverage percentage on the Y axis.
For example, the graph shows that in the Vector
results, using four gene types achieved 100\% of the coverage
found using all types, but took approximately 100\% longer to do so.
Note the point indicated by the arrow in \fig{timereport100}.
This point shows that it is usually
(in $\frac{12}{16}$ cases) possible to achieve 94\% of the
coverage in under 10\% of the time required to run all gene
types for 50 generations.

The two anomalous subject units in \fig{timereport100} are
{\tt EnumMap} and {\tt Vector}.  {\tt EnumMap} looks like a
success story, since we were able to achieve 140\% of the
original coverage.  In fact, this is simply noise, since we
could achieve only 3\% coverage of {\tt EnumMap} using
Nighthawk and generic test wrappers \cite{andrews07}, and
the graph shows an improvement to less than 5\%.  To understand
the {\tt Vector} results, note that \eq{cost} has two
components: number of options and the evaluation cost of each
option. In the case of {\tt Vector}, even though we reduced the
chromosome search space size, we made choices that greatly
increased the runtime cost.

What do all these numbers mean to the Nighthawk system?
In a nutshell, they mean that the original Nighthawk was doing
much work that did not pay off by achieving much better results.
Consider the six gene types ranked the lowest in the $bestMerit$
ranking.  Maintaining all the genes associated with these gene
types meant that the original Nighthawk was spending time
mutating these genes and extracting information from the current
values of the genes; it also meant that the original Nighthawk
was using up memory storing the representations of these genes,
for each chromosome in each generation, with a concomitant
time expense.  When these less useful genes were eliminated,
no large loss of coverage was observed, but a great increase
in efficiency was observed.


\section{Implications for Future Work}

We see implications of this work on three levels, each of which
we would like to explore:  on the tool level, the metaheuristic
level, and the theory-formation level.

On the {\it tool level}, this work shows that it is viable to
use feature subset selection as a postprocessing step in order
to improve the performance of a metaheuristic tool.
Metaheuristic tools (such as genetic algorithms and simulated
annealers) typically mutate some aspect of a candidate solution
and evaluate the results.  If the effect of mutating each aspect
is recorded, then each aspect can be considered a feature and
is amenable to the FSS processing described here.  Another
impact on the tool level is to suggest stopping criteria for
metaheuristic algorithms; for instance, \fig{timereport100}
suggests that for Nighthawk's GA, ending the algorithm when a
time limit is reached or when the fitness function has remained
constant for several generations will usually result in a good
cost-effectiveness tradeoff.

On the {\it metaheuristic level}, this work suggests that it may
be useful to integrate FSS directly into metaheuristic
algorithms.  Such an integration would enable the automatic
reporting of the merits of individual features, and the
automatic or semi-automatic selection of features.  If the
results of this paper extend to other domains, this would lead
to metaheuristic algorithms that improve themselves
automatically each time they are run.  We also speculate that
this is a promising direction to look at for a further order
of magnitude improvement in performance.

Finally, on the {\it theory-formation level}, this work opens
up the possibility of rapid turnover of the theoretical
foundations underlying present tools, as aspects of heuristic
and meta-heuristic approaches are shown to be consistently
valuable or expendible.  In the framework of a self-monitoring
metaheuristic algorithm, new strategies, heuristics, and
gene and mutator types can be introduced as theories evolve, and
can be evaluated efficiently by the algorithms themselves.

As an example of this latter point, the
{\tt chanceOfNull} gene type in Nighthawk determines how likely
(in percent) Nighthawk's random test data generation is to
choose a {\tt null} as a parameter in a given parameter
position.  That gene type was ranked as expendible by both
rankings explored here.  This suggests that it is not worthwhile
to search for different values for this percentage, and that the
default value (3\%) is sufficient.  Given sufficient
corroboration from other case studies and systems, this in turn
suggests that the value of generating test data with nulls is a
relatively settled problem, and that we can turn toward other
aspects of test data generation for future improvements.

\section{Conclusion}

We applied feature subset selection (FSS) to a metaheuristic
algorithm used to learn coverage models for randomized unit test
generation.  FSS allowed us to cut down on the number of gene
types we used, without a noticeable loss of coverage.  Since
each gene type corresponded to runtime cost, this also allowed
us to cut down on the time and memory taken for the algorithm.

These are preliminary results only, but are suggestive.  In the
future, we wish to study the use of FSS to speed up other
heuristic and metaheuristic software engineering tools.  We also
wish to explore the impact of FSS on all three of the
levels noted above (tool, metaheuristic, and theory-formation).






%bigger coverage models take longer to generate. these results raise the possibility that a time-bounded
%coverage venerator could work nearly as well as our current tool but an order of mangiture faster 

%two future directions
%\bi
%\item 
%early stopping rules. how to exploit this effect?
%\item
%currently, our FSS is a post-processor. since we are finding stable sets of ``best'' gene types, we would
%recommend disengaing it and using the four types recognized in this study (since our FSS results are stable: note that the same ordering using in fig 10 and no lose K=4 to k=10). However, could we win another order
%of magnitude imporvement is we increamntally applied FSS? Then, the mutation space of the GA could
%be reduced balah blah blah
%can we win another order of magnit
%\item
%Jamie's idea: try more gene types
%\ei
% Cinherent complexity
%
%The next great challenge for automatically building predictor models will
%the optimizing model generation.
%While simple models can be built rapidly, more complex models are
%much slower to build.
%
%Software testing involves running a piece of software (the
%software under test, or SUT) on selected input data, and
%checking the outputs for correctness.  The goals of software
%testing are to force failures of the SUT, and to be thorough.
%The more thoroughly we have tested an SUT without forcing
%failures, the more sure we are of the reliability of the SUT.
%
%Randomized testing is the practice of using randomization for
%some aspects of test input data selection.
%% A software unit is a
%% method, group of methods, module or class; a unit test is
%% usually built upon a sequence of method calls.
%Several independent studies
%\cite{miller-fuzz-cacm,andrews-etal-rute-rt,%
%pacheco-etal-icse2007,groce-etal-icse2007}
%have found that randomized
%testing of software units is effective at forcing failures in
%even well-tested units.  However, there remains a question of
%whether randomized testing can be thorough enough.  Using
%various code coverage measures to measure thoroughness,
%researchers have come to varying conclusions about the ability
%of randomized testing to be thorough
%\cite{michael-etal-ga-tcg,visser-etal-issta06,andrews-etal-rute-rt}.
%
%The thoroughness of randomized unit testing is highly dependent
%on parameters that control when and how randomization is
%applied.  These parameters include the number of method calls
%to make, the relative frequency with which different methods are
%called, and the ranges from which numeric arguments are chosen.
%The manner in which previously-used arguments or
%previously-returned values are used in new method calls,
%which we refer to as the {\it value reuse policy}, is also
%a crucial factor.  It is often difficult to work out the optimal
%values of the parameters and the optimal value reuse policy by hand.
%
%In this paper, we describe Nighthawk, a system for generating
%unit test data.  The system can be viewed as consisting of two
%levels.  The lower level is a randomized unit testing engine
%which tests a set of methods according to parameter values
%specified as genes in a chromosome, including parameters that
%encode a value reuse policy.  The upper level is a genetic
%algorithm (GA) which uses fitness evaluation, selection,
%mutation and recombination of chromosomes to find good values
%for the genes.  Goodness is evaluated on the basis of test
%coverage and number of method calls performed.
%
%Users can use Nighthawk to find good parameters, and then
%perform randomized unit testing based on those parameters.  The
%randomized testing can quickly generate many new test cases that
%achieve high coverage, and can continue to do so for as long as
%users wish to run it.
%
%% XXXX why this is great
%
%\subsection{Randomized Unit Testing}
%
%Unit testing is variously defined as the
%testing of a single method, a group of methods, a module or a
%class.  We will use it in this paper to mean the testing of a
%group $M$ of methods, called the {\it target methods}.  A unit
%test is a sequence of calls to the target methods, with each
%call possibly preceded by code that sets up the arguments and
%the receiverand
%on
%{\it Randomized unit testing} is unit testing where there is
%some randomization in the selection of the target
%method call sequence and/or arguments to the
%method calls.  Many researchers
%\cite{doong-frankl-tosem94,antoy-hamlet-tse-jan2000,%
%claessen-hughes-quickcheck,pacheco-etal-icse2007}
%%sen-etal-cute,visser-etal-issta06}
%have performed randomized unit testing,
%sometimes combined with other tools such as model
%checkers.
%
%A key concept in randomized unit testing is that of {\it value
%reuse}.  We use this term to refer to how the
%testing engine reuses the receiver, arguments or return values
%of past method calls when making new method calls.  In previous
%research, value reuse has mostly taken the form of making a
%sequence of method calls all on the same receiver object.
%
%In our previous research, we developed a GUI-based randomized
%unit testing engine called RUTE-J \cite{andrews-etal-rute-rt}.
%To use RUTE-J, users write their own customized test wrapper
%classes, hand-coding such parameters as relative frequencies of
%method calls.  Users also hand-code a value reuse policy by
%drawing receiver and argument values from value pools, and
%placing return values back in value pools.  Finding good
%parameters quickly, however, requires experience with the tool.
%
%The Nighthawk system described in this paper significantly
%builds on this work by automatically determining good parameters.
%The lower, randomized-testing,
%level of Nighthawk initializes and maintains one or more value
%pools for all relevant types, and draws and replaces values in
%the pools according to a policy specified in a chromosome.
%The chromosome also specifies relative frequencies of methods,
%method parameter ranges, and other testing parameters.
%The upper, genetic-algorithm, level performs a search for the
%parameter setting that causes the lower level to achieve a high
%value of a coverage-related measure.  Nighthawk uses only the
%Java reflection facility to gather information about the SUT,
%making its general approach robust and adaptable to other languages.
%
%Designing a GA means making decisions about what features are
%worthy of modeling and mutating.  For example, much of the effort
%on this project was a laborious trial-and-error process of
%trying different chromosomes.  To simplify that process, we
%describe experiments here with automatic feature subset
%selection (FSS). First, we try a very large and elaborate set of
%chromosomes. Next, we filter that set using automatic feature
%subset selection. The filtered set ran over 40\% more quickly, with
%no loss of coverage.  We therefore propose that automatic
%feature subset selection should be a routine part of the design
%of any large GA system.
%
%\subsection{Contributions and Paper Organization}
%
%The main contributions of this paper are as follows.
%\begin{enumerate}
%\item We describe the implementation of a novel two-level
%  genetic-random testing system, Nighthawk.  In particular,
%  we describe how we encode a value reuse policy in a manner
%  amenable to meta-heuristic search.
%\item We compare Nighthawk to other systems described in
%  previous research, showing that it can achieve the same
%  coverage levels.
%\item We describe the results of a case study carried out on
%  real-world units (the Java 1.5.0 Collection and
%  Map classes) to determine the effects of different option
%  settings on the basic algorithm.  We show that Nighthawk can
%  achieve high coverage automatically on these units.
%\item We describe how we optimized Nighthawk by using FSS to
%  systematically analyze which genes have the greatest effect on
%  the fitness
%  of a chromosome, and eliminating genes that we found to have
%  little effect.  We show that the optimized system achieved
%  the same good results in significantly less time, demonstrating
%  the utility of augmenting GAs with automatic feature subset
%  selection.
%\end{enumerate}
%
%We discuss related work in section 2.
%In section 3, we describe the results of an exploratory study
%that suggested that a genetic-random approach was feasible and
%could find useful parameter settings.  In section 4, we describe
%the design and use of Nighthawk.  Section 5 contains our
%comparison to previous work, and section 6 our case study;
%section 7 contains a discussion of the threats to validity
%of the empirical work in the paper.  The procedure and results
%of our optimization are in Section 8.
%
%\section{Related Work}
%
%\subsection{Randomized Unit Testing}
%
%``Random'' or ``randomized'' testing has a long history, being
%mentioned as far back as 1973 \cite{hetzel-book-1973};
%Hamlet \cite{Hamlet94randomtesting} gives a good survey.
%The key benefit of randomized testing is the ability to generate
%many distinct test inputs in a short time, including test inputs
%that may not be selected by test engineers but which may
%nevertheless force failures.  There are, however, two main
%problems with randomized testing:  the oracle problem and
%and the question of thoroughness.
%
%Since randomized testing depends on the generation of many
%inputs, it is infeasible to get a human to check all test
%outputs; an automated test oracle \cite{weyuker-oracles} is
%needed.  There are two main approaches to the oracle problem.
%The first
%is to use general-purpose, ``high-pass'' oracles that pass many
%executions but check properties that should be true of most
%software.  For instance, Miller et al.\ \cite{miller-fuzz-cacm}
%judge a randomly-generated GUI test case as failing only if the
%software crashes or hangs; Csallner and
%Smaragdakis \cite{jcrasher-spe} judge a randomly-generated unit
%test case as failing if it throws an exception; and Pacheco
%et al.\ \cite{pacheco-etal-icse2007} check general-purpose
%contracts for units, such as one that states that a method
%should not throw a ``null pointer'' exception unless one of its
%arguments is null.  Despite the use of high-pass oracles,
%all these authors found randomized testing to be effective in
%forcing failures.
%
%The second approach to the oracle problem for randomized testing
%is to write oracles in order to check properties specific to the
%software \cite{andrews-etal-rute-rt,ciupa-etal-icse2008}.
%These oracles, like all formal unit specifications,
%are non-trivial to write; tools such as Daikon for automatically
%deriving likely invariants \cite{ernst-daikon} could help here.
%
%Since randomized unit testing does not use any intelligence to
%guide its search for test cases, there has always been
%justifiable concern about how thorough it can be, given various
%measures of thoroughness, such as coverage and fault-finding
%ability.
%%
%Michael et al.\ \cite{michael-etal-ga-tcg} performed randomized testing
%on the well-known Triangle program; this program accepts three
%integers as arguments, interprets them as sides of a triangle,
%and reports whether the triangle is equilateral, isosceles,
%scalene, or not a triangle at all.  They concluded that
%randomized testing could not achieve 50\% condition/decision
%coverage of the code, even after 1000 runs.
%%
%Visser et al.\ \cite{visser-etal-issta06}
%compared randomized unit testing with various model-checking
%approaches and found that while randomized testing was good at
%achieving block coverage, it failed to achieve optimal coverage
%for stronger coverage measures, such as a measure derived from
%Ball's predicate coverage \cite{ball-pred-coverage}.
%
%Other researchers, however, have found that the thoroughness of
%randomized unit testing depends on how exactly it is implemented.
%%
%Doong and Frankl \cite{doong-frankl-tosem94} tested several
%units using randomized sequences of method calls, and found that
%by varying some parameters of the randomized testing, they could
%greatly increase or decrease the likelihood of finding injected
%faults.  The parameters included number of operations performed,
%ranges of integer arguments, and the relative frequencies of
%some of the methods in the call sequence.
%%
%Antoy and Hamlet \cite{antoy-hamlet-tse-jan2000}, who checked
%the Java {\tt Vector} class against a formal specification
%using random input, similarly found that if they avoided calling
%some of the methods (essentially setting their relative
%frequencies to zero), they could cover more code in the class.
%%
%Andrews and Zhang \cite{andrews-zhang-tse2003}, performing
%randomized unit testing on C data structures, found that varying
%the ranges from which integer key and data parameters were
%chosen increased the fault-finding ability of the random testing.
%
%Finally, the aforementioned research by Pacheco
%et al.\ \cite{pacheco-etal-icse2007} enhances the thoroughness
%of randomized testing by doing a partial randomized
%breadth-first search of the search space of possible test cases,
%pruning branches that lead to redundant or illegal values which
%would cause the system to waste time on unproductive test cases.
%
%Of the cited approaches, the approach described in this paper
%is most similar to Pacheco et al.'s.  The primary difference
%is that we achieve thoroughness by generating long sequences of
%method calls on different receivers, while they do so by
%deducing shorter sequences of method calls on a smaller set of
%receivers.
%%
%The focus of our research is also different.
%Pacheco et al.\ focus on identifying contracts for units and
%finding test cases that violate them.  In contrast, we focus on
%maximizing code coverage; coverage is an objective measure of
%thoroughness that applies regardless of whether failures have
%been found, for instance in situations in which most bugs have
%been eliminated from a unit.
%
%\subsection{Analysis-Based Test Data Generation Approaches}
%
%Approaches to test data generation via symbolic execution have
%existed as far back as 1976
%\cite{clarke-76-testdata,king-symbolic-1976}.
%Such approaches typically attempt to generate a thorough set of
%test cases by deducing which combinations of inputs will cause
%the software to follow given paths.
%Korel's TESTGEN system \cite{korel-testgen}, for example,
%transforms each condition in the program to one of the form
%$e < 0$ or $e \leq 0$, and then searches for values that minimize
%(resp.\ maximize) $e$, thus causing the condition to become true (resp.\ false).
%
%Other source code analysis-based approaches have used such
%methods as iterative relaxation of a set of constraints on
%input data \cite{gupta-etal-gen-test-data} and generation
%of call sequences using goal-directed
%reasoning \cite{leow-etal-icse2004}.  Some recent approaches use
%model checkers such as Java Pathfinder \cite{visser-etal-issta04}.
%These approaches are sometimes augmented with ``lossy''
%randomized search for paths, as in
%the DART and CUTE systems \cite{godefroid-etal-dart,sen-etal-cute},
%the Lurch system \cite{owen-menzies-lurch},
%and the Java Pathfinder-based
%research of Visser et al.\ \cite{visser-etal-issta06}.
%
%Some analysis-based approaches are limited in the range of
%different conditions they consider; for instance, TESTGEN's
%minimization strategy \cite{korel-testgen} cannot be applied
%usefully to conditions involving pointers.  In addition, most
%analysis-based approaches incur heavy memory and processing time
%costs, and are as yet infeasible except for small software
%units.  These limitations are the primary reason why researchers
%have explored the use of heuristic and metaheuristic approaches
%to test case generation.
%
%\subsection{Genetic Algorithms for Testing}
%
%Genetic algorithms (GAs) were first described by Holland
%\cite{holland-ga-book}.  GAs typically represent a solution to a
%problem as a ``chromosome'', with various aspects of the
%solution to the problem represented as ``genes'' in the
%chromosomes.  The possible chromosomes form a search space and
%are associated with a fitness function, which typically
%represents how good a solution the chromosome encodes.  Search
%proceeds by evaluating the fitness of each of a population of
%chromosomes, and then performing point mutations and
%recombination on the most successful chromosomes.
%GAs have been found to be superior to
%purely random search in finding solutions to many complex
%problems. Goldberg \cite{goldberg-ga-book} argues that their
%power stems from being able to engage in ``discovery and
%recombination of building blocks'' for solutions in a solution space.
%
%Meta-heuristic search methods such as GAs have often been
%applied to the problem of test suite generation.
%In Rela's review of 122 applications of meta-heuristic search
%in software engineering \cite{rela04}, 44\% of the
%applications related to testing.  Approaches to GA test suite
%generation can be black-box (requirements-based) or white-box
%(code-based); here we focus on four representative white-box
%approaches, since our approach is coverage-based and therefore
%also white-box.
%
%Pargas et al.\ \cite{pargas-etal-ga-tcg} represent a set of
%test data as a chromosome, in which each gene encodes one
%input value to the software.
%Michael et al.\ \cite{michael-etal-ga-tcg} represent test data
%similarly, and conduct experiments comparing various strategies
%for augmenting the GA search.  Both of these approaches
%evaluate the fitness of a chromosome by measuring
%how close the input is to covering some desired statement or
%condition direction.
%Guo et al.\ \cite{guo-etal-genetic} generate unique input-output
%(UIO) sequences for protocol testing using a genetic algorithm;
%the sequence of genes represents a sequence of inputs to a
%protocol agent, and the fitness function computes a measure
%related to the coverage of the possible states and transitions
%of the agent.  Finally, Tonella's approach to class testing
%\cite{tonella-issta04}
%represents the sequence of method calls in a unit test as a
%chromosome; the approach features mutation operators customized
%to the problem, such as one that inserts method invocations.
%
%\subsection{Analytic Comparison of Approaches}
%
%Once a large community starts
%comparatively evaluating some technique, then
%{\em evaluation methods} for different methods become just as
%important as the {\em generation of new methods}.
%To place this comment in an historical perspective, we note that
%evaluation bias is an active research area in the field of data
%mining \cite{bouck03,demsar06}.
%Much of our future work should hence focus on a meta-level
%analysis of the advantages and
%disadvantages of different assessment criteria.
%Currently, there are no clear conventions on how this
%type of work should be assessed.  However, we can attempt some
%analytic comparisons.
%
%It is clear that there are situations in which a source code
%analysis-based approach such as symbolic evaluation or model
%checking will be superior to any randomized
%approach.  For instance, for an {\tt if} statement decision
%of the form {\tt (x==742 \verb/&&/ y==113)}, random search of
%the space of all possible {\tt x,y} pairs is unlikely to
%produce a test case that executes the decision in the true
%direction, while a simple analysis of the source code will be
%successful.  The question is how often these situations
%arise in real-world programs.  The system Nighthawk of this
%paper cannot guess at constants like 742, but is still able
%to cover the true direction of decisions of the form
%{\tt x==y} because the value reuse policies it discovers will
%often choose {\tt x} and {\tt y} from the same value pool.
%
%It is therefore likely that randomized testing and
%analysis-based approaches have complementary strengths.
%Groce et al.\ \cite{groce-etal-icse2007} conclude that
%randomized testing is a good first step, before model checking,
%in achieving high quality software, especially where the
%existence of a reference implementation allows differential
%randomized testing \cite{mckeeman-differential}.
%
%
%
%%\begin{itemize}
%%\item Static code analysis can direct the generation of the test
%%  cases.  Our method, on the other hand, generates test cases at
%%  random, so it is possible that we cover some code more than is
%%  necessary, and that parts of our value pools are  useless.
%%  Our view is that this is not a major issue since our
%%  runtimes, on real-world systems, are quite impressive.
%%  Nevertheless, there needs to be more discussion on how to
%%  assess test suite generation; i.e.\ runtimes versus
%%  superfluous tests versus any other criteria.
%%\end{itemize}
%
%
%Genetic algorithms do not perform well when the search space is
%mostly flat, with steep jumps in fitness score.
%In all the approaches to GA-based test input generation that
%we are aware of, each run of the GA results in a single
%test case, which is meant to reach a particular target.  A test
%suite is built up by aiming the GA at different targets, resulting
%in a minimal test suite that achieves coverage of all targets.
%Herein lies a potential disadvantage of such approaches.
%Rothermel et al. \cite{rothermel-etal-effects-minimization}
%have shown that reducing a test suite to a minimal subset that
%achieves the same coverage can significantly reduce its fault
%detection capability.  The GA can be re-run to generate
%more test cases, but there is a potential performance penalty
%since each run of the GA generates only one new test case.
%In contrast, in our approach, each run of the GA results in a
%setting for parameters for randomized testing, which can be
%applied cheaply many times to generate many distinct
%high-coverage test cases.
%
%%\begin{center}
%%\begin{tabular}{c|ccccccc|ccccc}
%%$x|y$ & 1 & 2 & 3 & 4 & 5 & ~~~ &
%%$lo|hi$ & 1 & 2 & 3 & 4 & 5 \\
%%\cline{1-6} \cline{8-13}
%%1 & 1.0 & .00 & .00 & .00 & .00 & &
%%1 & 1.0 & .50 & .33 & .25 & .20 \\
%%2 & .00 & 1.0 & .00 & .00 & .00 & &
%%2 & .00 & 1.0 & .50 & .33 & .25 \\
%%3 & .00 & .00 & 1.0 & .00 & .00 & &
%%3 & .00 & .00 & 1.0 & .50 & .33 \\
%%4 & .00 & .00 & .00 & 1.0 & .00 & &
%%4 & .00 & .00 & .00 & 1.0 & .50 \\
%%5 & .00 & .00 & .00 & .00 & 1.0 & &
%%5 & .00 & .00 & .00 & .00 & 1.0 \\
%%\end{tabular}
%%\end{center}
%%
%%\caption{Chance of selecting two identical integers $x$ and $y$.
%%(left) Search space as space of $(x,y)$ pairs.
%%(right) Search space as space of lower and upper bounds
%%for random generation of $x$ and $y$.}
%%\label{search-space-fig}
%%\end{figure*}
%
%% Look up Baresel paper BSS02!!
%
%%We also generalize the problem domain from the heuristic to the
%%meta-heuristic by adding the GA level.
%
%\section{Exploratory Study}
%\label{exploratory-section}
%
%To find out whether there was any merit in the idea of a
%genetic-random system, we conducted an exploratory study.
%In this section, we describe the prototype software we developed,
%the design of the study and its results.
%
%\subsection{Software Developed}
%
%Using code from RUTE-J (see above) and the open-source genetic
%algorithm package JDEAL \cite{jdeal}, we constructed a prototype
%two-level genetic-random unit testing system that took Java
%classes as its testing units.  For each unit under test (UUT) with
%$n$ methods to call, the GA level constructed a chromosome with
%$2+n$ integer genes; these genes represented
%the number of method calls to make in each
%test case, the number of test cases to generate, and the
%relative weights (calling frequencies) of the $n$ methods.  All
%other randomized testing parameters
%were hard-coded in the test wrappers.
%
%The evaluation of the fitness of each chromosome $c$ proceeded as
%follows.  We got the random testing level to generate the number
%of test cases of the length specified in $c$, using
%the method weights specified in $c$.  We then
%measured the number of coverage points covered using
%Cobertura \cite{cobertura-website},
%which measures line coverage.  If we had based the
%fitness function {\it only} on coverage, however, then any chromosome
%would have benefitted from having a larger number of
%method calls and test cases, since every new method call has the
%potential of covering more code.
%We therefore built in a brake to prevent these values from
%getting unfeasibly high.  We calculated the fitness function
%as:
%\begin{center}
%(number of coverage points covered) $*$ (coverage factor) \\
% $-$ (number of method calls performed overall)
%\end{center}
%We set the coverage factor to 1000, meaning that we were willing
%to make 1000 more method calls (but not more) if that meant
%covering one more coverage point.
%
%\subsection{Experiment Design}
%
%We chose as our subject programs three units taken from the Java
%1.4.2 edition of {\tt java.util}: {\tt BitSet}, {\tt HashMap}
%and {\tt TreeMap}.  These units were clearly in wide use,
%and {\tt TreeMap} had been used as the basis of earlier
%experiments by other researchers \cite{visser-etal-issta04}.
%For each UUT, we wrote a
%test wrapper class containing methods that called selected
%target methods of the UUT (16 methods for BitSet, 8 for HashMap
%and 9 for TreeMap).
%Each wrapper contained a simple oracle for checking correctness.
%We instrumented each UUT using Cobertura.
%
%We ran the two-level algorithm 30 times on each of the three
%test wrappers, and recorded the amount of time taken and the
%parameters in the final chromosome.
%To test whether the weights in the chromosomes were
%useful given the length and number of method calls, for each
%final chromosome $c$ we created a variant chromosome $c'$
%with the same length and number of method calls but with all
%weights equal.  We then compared the coverage achieved by
%$c$ and $c'$ on 30 paired trials.  Full results from the
%experiment are available in \cite{cli-msc}.
%
%\subsection{Results}
%
%We performed two statistical tests to evaluate whether the
%system was converging on a reasonable solution.  First, we
%ordered the average weights discovered for each method in each
%class, and performed a $t$ test
%with Bonferroni correction between each pair of
%adjacent columns.
%We found that for the {\tt HashMap} and {\tt TreeMap} units, the
%{\tt clear} method (which removes all data from the map) had a
%statistically significantly lower weight than the other methods,
%indicating that the algorithm was consistently converging on a
%solution in which it had a lower weight.
%This is because much of the code in these
%units can be executed only when there is a large amount of data
%in the container objects.  Since the {\tt clear} method clears
%out all the data, executing it infrequently ensured that
%the objects would get large enough.
%
%We also found that for the {\tt TreeMap} unit, the {\tt remove}
%and {\tt put} methods had a statistically significantly higher
%weight than the other methods.  This is explainable by the large
%amount of complex code in these methods and the private methods
%that they call; it takes more calls to
%cover this code than it does for the simpler code of
%the other methods.  Another reason is that sequences of {\it put}
%and {\it remove} were needed to create data structures through
%which code in some of the other methods was accessible.
%
%The second statistical test we performed tested
%whether the weights found by the GA were efficient.
%For this, we used the 30 trials comparing the discovered
%chromosome $c$ and the equal-weight variant $c'$.  We found that
%for all three units, the equal-weight chromosome covered less
%code than the
%original, to a statistically significant level (as measured by a
%$t$ test with $\alpha=0.05$).  This can be interpreted as
%meaning that the GA was correctly choosing a good {\it combination}
%of parameters.
%
%In the course of the experiment, we found a bug in the Java
%1.4.2 version of {\tt BitSet}:  when a call to {\tt set()} is
%performed on a range of bits of length 0, the unit could later
%return an incorrect ``length'' for the {\tt BitSet}.
%We found that a bug report for this bug
%had already been submitted to Sun's bug database.  It has been
%corrected in the Java 1.5.0 version of the library.
%
%In summary, the experiment indicated that the two-level
%algorithm was potentially useful, and was consistently
%converging on similar solutions that were more optimal than
%calling all methods equally often.
%
%\section{Nighthawk:  System Description}
%
%The results of our exploratory study encouraged us to expand
%the scope of the GA to include method parameter ranges, value
%reuse policy and other randomized testing parameters.  The
%result was the Nighthawk system.
%
%In this section, we first outline the lower, randomized-testing,
%level of Nighthawk, and then describe the chromosome that
%controls its operation.  We then describe the
%genetic-algorithm level and the
%end user interface.  Finally, we describe the use
%of automatically-generated test wrappers for precondition
%checking, result evaluation and coverage enhancement.
%
%\subsection{Randomized Testing Level}
%\subsection{Chromosomes}
%
%Aspects of the test case execution algorithms are controlled
%by the genetic algorithm chromosome given as an argument.  A
%{\it chromosome} is composed of a finite number of {\it genes}.
%Each gene is a pair consisting of a name
%and an integer, floating-point, or {\tt BitSet} value.
%Figure \ref{gene-types-fig} summarizes the different types of
%genes that can occur in a chromosome.
%We refer to the receiver (if any) and the return value
%(if non-{\tt void}) of a method call
%as {\it quasi-parameters} of the method call.  Parameters and
%quasi-parameters have {\it candidate types}:
%\begin{itemize}
%\item A type is a candidate type for a receiver if it is a
%  subtype of the type of the receiver.  These are the types
%  from whose value pools the receiver can be drawn.
%\item A type is a candidate type for a parameter if it is a
%  subtype of the type of the parameter.  These are the types
%  from whose value pools the parameter can be drawn.
%\item A type is a candidate type for a return value if it is a
%  supertype of the type of the return value.  These are the
%  types into whose value pools the return value can be placed.
%\end{itemize}
%Note that the gene types
%{\tt candidateBitSet} and {\tt valuePoolActivityBitSet}
%essentially encode a value reuse policy by determining the
%pattern in which receivers, arguments and return values are
%drawn from and placed into value pools.
%
%%Every Nighthawk chromosome contains a gene specifying the number
%%$n$ of method calls that {\sf constructRunTestCase} is to
%%run.  In addition, a chromosome appropriate to a set $M$
%%of target methods contains the following genes:
%%\begin{itemize}
%%%\item The number $n$ of method calls to perform.
%%\item For each method in $C_M$, the relative weight of the
%%  method, i.e.\ the likelihood that it will be chosen at step
%%  4(a) of {\sf constructRunTestCase}.
%%\item For each type of interest in $I_M$, the number of value
%%  pools for that type.
%%\item For each value pool, the number of values in the pool.
%%\item For each value pool of a range primitive type, the upper
%%  and lower bounds on values in the pool.  Initial values are
%%  drawn from this range with a uniform distribution.
%%\item For each method in $C_M$ and every argument position, the
%%  chance that {\tt null} will be chosen as an argument.
%%\item For each method in $C_M$, the types of interest that will
%%  be chosen from to find a receiver, and, for each of those
%%  types, the value pools that will be chosen from.
%%\item For each method in $C_M$ and every argument position, the
%%  types of interest that will be chosen from to find an
%%  argument, and, for each of those types, the value pools
%%  that will be chosen from.
%%\item For each method in $C_M$, the types of interest that will
%%  be chosen from to find an element that will be replaced by
%%  the return value,
%%  and, for each of those types, the value pools that will be
%%  chosen from.
%%\end{itemize}
%%The last three kinds of genes are expressed as bit vectors;
%%each bit stands for one of the types of interest that is a
%%subtype of the declared type (resp.\ one of the value pools).
%%These bit vectors thus encode the value reuse policy
%%expressed by the chromosome.
%
%It is clear that different gene values in the chromosome may
%cause dramatically different behaviour of the algorithm on the
%methods.  We illustrate this point with two concrete examples.
%
%Consider the ``triangle'' unit from \cite{michael-etal-ga-tcg}.
%If the chromosome specifies
%that all three parameter values are to be taken from a value
%pool of 65536 values in the range -32768 to 32767, then the
%chance that the algorithm will ever choose two
%or three identical values for the parameters (needed for the
%``isosceles'' and ``equilateral'' cases) is very low.  If,
%on the other hand, the value pool contains only 30 integers
%each chosen from the range 2 to 5, then the chance rises
%dramatically due to reuse of previously-used values.  The amount
%of additional coverage this would give would vary depending on
%the UUT, but is probably nonzero.
%
%Consider further a container class with {\tt put} and
%{\tt remove} methods, each taking an integer key as its only
%parameter.  If the parameters to the two methods are taken from
%two different value pools of 30 values in the range 0 to 1000,
%there is little chance that a key that has been put into the
%container will be successfully removed.  If, however, the
%parameters are taken from a single value pool of 30 values in
%the range 0 to 1000, then the chance is very good that added
%keys will be removed, again due to value reuse.  A {\tt remove}
%method for a typical data structure executes different
%code for a successful removal than it does for a failing one.
%
%\subsection{Genetic Algorithm Level}
%
%\subsection{Top-Level Application}
%
%\label{deep-section}
%The Nighthawk application takes several switches and a set
%of class names as command-line parameters.  The default
%behaviour is to consider the command-line class names as a set
%of ``target classes''.  If, however, the ``{\tt --deep}'' switch
%is given to Nighthawk, the public declared methods of the
%command-line classes are explored, and all non-primitive types
%of parameters and return values of those methods are added to
%the set of target classes.  The set $M$ of target {\it methods}
%is computed as all public declared methods of the target
%{\it classes}.  Intuitively, therefore, the {\tt --deep} switch
%performs a ``deep target analysis'' by getting Nighthawk to call
%methods in the layer of classes surrounding the command-line
%classes.
%
%Nighthawk runs the GA, monitoring the
%chromosomes and retaining the most fit
%chromosome ever encountered.  This most
%fit chromosome is the final output of the program.
%
%\label{run-chromosome-sec}
%After finding the most fit chromosome, a test engineer can
%perform the randomized testing that it specifies.
%To do this, they run a separate program, RunChromosome, which
%takes the chromosome description as input and runs test cases
%based on it for a user-specified number of times.  Randomized
%unit testing generates new test cases with new data every time
%it is run, so if Nighthawk finds a parameter setting that
%achieves high coverage, a test engineer can automatically
%generate a large number of distinct, high-coverage test cases with
%RunChromosome.
%
%
%\subsection{Test WRAPPERs}
%\label{test-wrappers-section}
%
%We provide a utility program that, given a class name, generates
%the Java source file of a ``test wrapper'' class for the class.
%Running Nighthawk on an unmodified test wrapper is the same
%as running it on the target class; however, test wrappers can be
%customized for precondition checking, result checking or
%coverage enhancement.
%
%A test wrapper for class X is a class that contains one private
%field of class X (the ``wrapped object''), and one public method
%with an identical declaration for each public declared method of
%class X.  Each wrapper method simply passes the call on to the
%wrapped object.
%
%To customize a test wrapper for precondition checking, the user
%can insert a check in the wrapper method before the target
%method call.  If the precondition is violated, the wrapper
%method can simply return.
%To customize a test wrapper for test result checking, the user
%can insert any result-checking code after the target method
%call; examples include normal Java assertions and JML
%\cite{jml-overview} contracts.
%%For instance, a user can choose to customize a wrapper method so
%%that it throws an {\tt AssertionError} (signalling test case failure)
%%whenever the target method throws an {\tt ArrayOutOfBoundsException}.
%We provide switches to the test wrapper generation program that
%cause the wrapper to
%check commonly-desired properties, such as that a method throws
%no {\tt NullPointerException} unless one of its arguments is
%null.  The switch \verb/--pleb/ generates a wrapper that checks
%all the Java Exception and Object contracts from
%Pacheco et al.\ \cite{pacheco-etal-icse2007}.
%
%To customize a test wrapper for coverage enhancement,
%the user can insert extra methods that cause extra code to be
%executed.  We provide two switches
%for commonly-desired enhancements.  The switch \verb/--checkTypedEquals/
%adds a method to the test wrapper for class X that takes one
%argument of type X and passes it to the {\tt equals} method
%of the wrapped object.  This is distinct from the normal wrapper
%method that calls {\tt equals}, which has an argument of type
%{\tt Object} and would therefore by default receive arguments
%only of type {\tt int} or {\tt String} (see Section \ref{object-section}).
%For classes X that implement their own {\tt equals} method, the
%typed-equals method is likely to execute more code.
%
%Tailored serialization is accomplished in Java via
%specially-named private methods that are inaccessible to
%Nighthawk.  The test wrapper generation program switch
%\verb/--checkSerialization/ adds a
%method to the test wrapper that writes the object to a byte
%array and reads it again from the byte array.
%This causes Nighthawk to be able to execute the code in the
%private serialization methods.
%
%\section{Comparison with Previous Results}
%
%We compared Nighthawk with two well-documented systems in the
%literature by running it on the same software and measuring
%the results.
%
%\subsection{Pure GA Approach}
%
%To compare the results of our genetic-random approach with those
%of the purely genetic approach of
%Michael et al.\ \cite{michael-etal-ga-tcg}, we adapted their
%published C code for the Triangle program to Java, transforming
%each decision so that each condition and decision direction
%corresponded to an executable line of code measurable by
%Cobertura.  We then ran Nighthawk 10 separate times on the
%resulting class.
%
%%6782 gen 8
%%6914 gen 10
%%6527 gen 10
%%5008 gen 7
%%3346 gen 5
%%1790 gen 2
%%2486 gen 5
%%7945 gen 13
%%18363 gen 21
%%2509 gen 4
%
%We found that Nighthawk reached 100\% of feasible
%condition/decision coverage on average after 8.5 generations, in
%an average of 6.2 seconds of clock time \footnote{
%All empirical studies in this paper were performed on a Sun
%UltraSPARC-IIIi running SunOS 5.10 and Java 1.5.0\_11.
%}.
%%There were 22 decisions having a total of 28 condition
%%and decision directions.
%%All condition and decision directions were coverable
%%except the false direction of the last ``if'' statement; Michael
%%et al.\ found that their best method also achieved 95\% coverage.
%%
%Michael et al.\ had found that a purely random approach could
%not achieve even 50\% condition/decision coverage.  The
%discrepancy between the results may be due to
%Nighthawk being able to find a setting of the randomized testing
%parameters that is more optimal than the one Michael et al.\ were
%using.  Inspection revealed that the chromosomes encoded value
%reuse policies that guaranteed frequent selection of the same
%values.
%
%\subsection{Model-Checking and Feedback-Directed Randomization}
%
%To compare our results with those of the model-checking approach
%of Visser et al.\ \cite{visser-etal-issta06} and the
%feedback-directed random testing of
%Pacheco et al.\ \cite{pacheco-etal-icse2007},
%we downloaded the four data structure units used in those
%studies.  The units had been hand-instrumented to record
%coverage of the deepest basic blocks in the code.
%
%We first wrote restricted test wrapper classes that called only
%the methods called by the previous researchers.  We ran
%Nighthawk giving these test wrapper classes as command-line
%classes, and observed the number of instrumented basic blocks
%covered, and the number of lines covered as measured by
%Cobertura.
%
%\begin{figure}
%\scriptsize
%\begin{center}
%\begin{tabular}{|c|c|c|c|c|c|c|}
%\hline
%		& \multicolumn{3}{c|}{Instr Blk Cov}
%				  & Time
%					  & \multicolumn{2}{c|}{Line Cov} \\
%UUT		& JPF & RP  & NH  & (sec) & Restr & Full \\
%\hline
%BinTree		& .78 & .78 & .78 &  .58  & .84   &   1  \\
%\hline
%BHeap		& .95 & .95 & .95 &  4.1  & .88   &  .92 \\
%\hline
%FibHeap		&  1  &  1  &  1  &  5.1  & .74   &  .92 \\
%\hline
%TreeMap		& .72 & .72 & .72 &  5.4  & .76   &  .90 \\
%\hline
%\end{tabular}
%\end{center}
%
%\caption{Comparison of results on the JPF subject units.}
%\label{jpf-results-fig}
%\end{figure}
%
%Figure \ref{jpf-results-fig} shows the results of the comparison.
%We show the block coverage ratio achieved
%by the best Java-Pathfinder-based technique from Visser et
%al.\ (JPF), by Pacheco et al.'s tool Randoop (RP), and
%by Nighthawk using the restricted test wrappers. 
%Nighthawk was able to achieve the same coverage as the previous
%tools.  The Time column shows the clock time in seconds needed by
%Nighthawk to achieve its greatest coverage.
%For BHeap and FibHeap, Nighthawk runs more quickly than JPF, but for
%the other two units it runs more slowly than both JPF and Randoop.
%This difference in run times may be in part because
%Nighthawk relies on general-purpose Cobertura instrumentation,
%which slows down programs, rather than the efficient, but
%application-specific, hand instrumentation that the other
%methods used.  It may also be in part due to
%the fact that our experiments were run on a different
%machine architecture than that of Pacheco et al.
%
%We then ran Nighthawk giving the target classes themselves as
%command-line classes (bypassing the test wrappers), and observed
%the number of lines covered.  The ``Line Cov'' columns show the
%line coverage ratio achieved when using the restricted wrappers
%and on the full target classes.  When using the full target
%classes, Nighthawk was able to cover significantly more lines of
%code, including all the blocks covered by the previous studies.
%
%\begin{figure}
%
%%\begin{center}
%%\begin{tabular}{|c|c|c|c|}
%%\hline
%%		& \multicolumn{3}{c|}{Number of cond value combinations} \\
%%UUT		& Total & Unreached & Rch/Uncov \\
%%\hline
%%BinTree		&  34   &     6     &    0 \\
%%\hline
%%BHeap		&  75   &     0     &    5 \\
%%\hline
%%FibHeap		&  57   &    10     &    3 \\
%%\hline
%%TreeMap		&  157  &    31     &    19 \\
%%\hline
%%\end{tabular}
%%\end{center}
%\scriptsize
%\begin{center}
%\begin{tabular}{|c|c|c|c|}
%\hline
%		& \multicolumn{3}{c|}{Number of cond value combinations} \\
%UUT		& Total & Reachable & Covered \\
%\hline
%BinTree		&  34   &    28     & 28 (.82, 1.0) \\
%\hline
%BHeap		&  75   &    75     & 70 (.93, .93) \\
%\hline
%FibHeap		&  57   &    47     & 44 (.77, .94) \\
%\hline
%TreeMap		&  157  &   126     & 107 (.68, .85) \\
%\hline
%\end{tabular}
%\end{center}
%
%\caption{Multiple condition coverage of the subject units.}
%\label{jpf-mcc-results-fig}
%\end{figure}
%
%Visser et al.\ and Pacheco et al.\ also studied a form of
%predicate coverage \cite{ball-pred-coverage} whose
%implementation is linked to the underlying Java Pathfinder code,
%and is difficult for Nighthawk to access.
%While this predicate coverage is an interesting assessment
%criterion, there is no consensus in the literature on the
%connection of this criterion to other measures.
%For comparison, we
%therefore studied multiple condition coverage (MCC), a standard
%coverage metric which is, like predicate coverage, intermediate
%in strength between decision/condition and path coverage.
%We instrumented the source code so that every combination of
%values of conditions in every decision caused a separate line of
%code to be executed.  We then ran Nighthawk on the test
%wrappers, thus effectively causing it to optimize MCC rather
%than just line coverage.
%
%The results are in Figure \ref{jpf-mcc-results-fig}.  We list
%the total number of valid condition value combinations in all
%the code, and the number that were in decisions reachable by
%calling only the methods called by the other research groups.
%We also list the number of combinations covered by Nighthawk,
%both as a raw total and as a fraction of the total combinations
%and the reachable combinations.
%Nighthawk achieved between 68\% and 93\% of
%MCC, or between 85\% and 100\% when only reachable condition
%combinations were considered.  These results are very good,
%since ``code coverage of 70-80\% is a reasonable goal for system
%test of most projects with most coverage metrics''
%\cite{cornett-minimum-coverage}.
%
%In summary, the comparison suggests that
%Nighthawk was achieving good coverage with respect to the
%results achieved by previous researchers, even when strong
%coverage measures such as decision/condition and MCC were taken
%into consideration.
%
%\section{Case Study}
%
%In order to study the effects of different test wrapper
%generation and command-line switches to Nighthawk, we studied
%the Java 1.5.0 Collection and Map classes; these are the 16
%concrete classes with public constructors in {\tt java.util}
%that inherit from the {\tt Collection} or {\tt Map}
%interface.  The source files total 12137 LOC, and Cobertura
%reports that 3512 of those LOC contain executable code.  These
%units are ideal subjects because they are heavily used and
%contain complex code, including templates and inner classes.
%
%For each unit,
%we generated test wrappers of two kinds:  plain test wrappers
%(P), and enriched wrappers (E) generated with the
%{\tt --checkTypedEquals} and {\tt --checkSerializable} switches
%(see Section \ref{test-wrappers-section}).
%We studied two different option sets for Nighthawk: with no
%command-line switches (N), and with the {\tt --deep} switch
%(see Section \ref{deep-section}) turned on (D).
%For each $\langle$UUT, test wrapper, option set$\rangle$ triple, we
%ran Nighthawk for 50 generations and saved the best chromosome it found.
%For each triple, we then executed RunChromosome (see Section
%\ref{run-chromosome-sec}) specifying that it generate 10 test
%cases with the given chromosome, and we measured the coverage
%achieved.
%
%\begin{figure}
%\scriptsize
%\begin{center}
%\begin{tabular}{|l|c|c|c|c|c|}
%Source file	& SLOC	& PN	& EN	& PD	& ED \\
%\hline
%ArrayList	& 150	& 111	& 140	& 109	& 140 (.93) \\
%\hline
%EnumMap		& 239	& 7	& 9	& 10	& 7 (.03) \\
%\hline
%HashMap		& 360	& 238	& 265	& 305	& 347 (.96) \\
%\hline
%HashSet		& 46	& 24	& 40	& 26	& 44 (.96) \\
%\hline
%Hashtable	& 355	& 205	& 253	& 252	& 325 (.92) \\
%\hline
%IHashMap	& 392	& 156	& 196	& 283	& 333 (.85) \\
%\hline
%LHashMap	& 103	& 27	& 37	& 28	& 96 (.93) \\
%\hline
%LHashSet	& 9	& 6	& 6	& 7	& 9 (1.0) \\
%\hline
%LinkedList	& 227	& 156	& 173	& 196	& 225 (.99) \\
%\hline
%PQueue		& 203	& 98	& 123	& 140	& 155 (.76) \\
%\hline
%Properties	& 249	& 101	& 102	& 102	& 102 (.41) \\
%\hline
%Stack		& 17	& 17	& 17	& 17	& 17 (1.0) \\
%\hline
%TreeMap		& 562	& 392	& 415	& 510	& 526 (.94) \\
%\hline
%TreeSet		& 62	& 44	& 59	& 41	& 59 (.95) \\
%\hline
%Vector		& 200	& 183	& 184	& 187	& 195 (.98) \\
%\hline
%WHashMap	& 338	& 149	& 175	& 274	& 300 (.89) \\
%\hline
%\hline
%Total		& 3512	& 1914	& 2194	& 2487	& 2880 \\
%\hline
%Ratio		& 	& .54	& .62	& .71	& .82  \\
%\hline
%\end{tabular}
%\end{center}
%
%\caption{
%  Coverage achieved by configurations of Nighthawk
%  on the {\tt java.util} Collection and Map classes.
%}
%\label{collection-map-cov}
%\end{figure}
%
%\begin{figure}
%\scriptsize
%\begin{center}
%\begin{tabular}{|l|c|c|c|c|c|c|}
%Source file	& PN	& EN	& PD	& ED	& RC \\
%\hline
%ArrayList	& 75	& 91	& 29	& 48	& 15 \\
%\hline
%EnumMap		& 3	& 9	& 6	& 5	& 8 \\
%\hline
%HashMap		& 63	& 37	& 136	& 176	& 30 \\
%\hline
%HashSet		& 25	& 29	& 27	& 39	& 22 \\
%\hline
%Hashtable	& 8	& 110	& 110	& 157	& 25 \\
%\hline
%IHashMap	& 31	& 41	& 59	& 134	& 34 \\
%\hline
%LHashMap	& 1	& 5	& 4	& 129	& 25 \\
%\hline
%LHashSet	& 1	& 4	& 6	& 24	& 16 \\
%\hline
%LinkedList	& 32	& 61	& 41	& 53	& 17 \\
%\hline
%PQueue		& 23	& 40	& 242	& 103	& 13 \\
%\hline
%Properties	& 104	& 19	& 49	& 47	& 18 \\
%\hline
%Stack		& 5	& 10	& 5	& 26	& 8 \\
%\hline
%TreeMap		& 80	& 131	& 231	& 106	& 26 \\
%\hline
%TreeSet		& 110	& 93	& 98	& 186	& 26 \\
%\hline
%Vector		& 106	& 83	& 156	& 176	& 20 \\
%\hline
%WHashMap	& 37	& 35	& 92	& 110	& 21 \\
%\hline
%\hline
%Total		& 704	& 798	& 1291	& 1519	& 324 \\
%\hline
%\end{tabular}
%\end{center}
%
%\caption{
%  Time in seconds taken by configurations of Nighthawk
%  to achieve highest coverage
%  on the {\tt java.util} Collection and Map classes.
%}
%\label{collection-times}
%\end{figure}
%
%Figure \ref{collection-map-cov} shows the results of this study.
%The column labelled SLOC shows the total number of source lines
%of code reported by Cobertura (including inner classes) in the
%source file associated with the class.  Column PN shows the
%SLOC covered by Nighthawk with the plain test wrappers and
%no Nighthawk switches; columns EN, PD and ED show the other
%combinations, and column ED also shows the coverage ratio with
%respect to total SLOC.
%% EN shows the effect of using the
%%enriched wrappers, and column PD the effect of using deep target
%%class analysis with the plain wrappers; column ED shows the effect of
%%using both the enriched wrappers and deep target class analysis.
%The second last line shows the totals for each column, and
%the last line shows the coverage ratio attained.
%
%With enriched test wrappers and deep target class analysis,
%Nighthawk performs well, achieving over 90\% coverage on 11 out
%of the 16 classes, and
%82\% coverage overall.
%Paired $t$ tests with Bonferroni
%correction (corrected $\alpha = .00833$) on each pair of columns
%in the table
%indicate that there are statistically significant differences
%between every pair except the (EN, PD) pair.
%
%Nighthawk performed poorly on the {\tt EnumMap}
%class because
%the main constructor to {\tt EnumMap} expects
%an enumerated type as one of the parameters.
%Nighthawk had no facility for supplying such a type, and so
%only a few lines of error code in constructors were executed.
%When we customized the test wrapper class so that it used a
%fixed enumerated type, Nighthawk with the ED configuration covered
%204 lines of code (coverage ratio .85), raising the total
%coverage ratio for all classes to .88.
%
%%It also performed poorly on the {\tt Properties} class, due to
%%the fact that it could not automatically generate a useful
%%{\tt InputStream} argument for several of the methods.
%%We expect that these deficiencies could be at least partially
%%addressed by hand-customizing the test wrappers for the classes.
%
%Table \ref{collection-times} shows the amount of time taken by
%Nighthawk on the various configurations.  In columns PN-ED, we
%report the number
%of seconds of clock time taken for Nighthawk to first achieve
%its best coverage.  $t$ tests
%showed that the only pairs of
%columns that were different to a statistically significant level
%were (PN, ED) and (EN, ED).  This suggests that generating the
%enriched wrappers allowed Nighthawk to
%cover significantly more code without running significantly
%longer;  the deep target class analysis
%also caused Nighthawk to cover
%significantly more code, but took significantly longer
%(though still less than 100 seconds per unit on average).
%
%In column RC of Table \ref{collection-times}, we report the
%number of CPU seconds needed for the RunChromosome program to
%create and run the 10 new test cases with the parameters chosen
%by Nighthawk in the ED configuration.
%This time includes JVM startup time.  The results show that
%with the parameters chosen by Nighthawk, RunChromosome can
%automatically generate many new test cases that achieve high
%coverage, in an average of approximately 2 seconds per test
%case.
%
%\section{Threats to Validity}
%
%Here we discuss the threats to validity of the empirical results
%in this paper.
%
%The representativeness of the units under test is the major
%threat to external validity.  We studied Java collection
%classes because these are complex, heavily-used units that have
%high quality requirements.  However, other units might
%have characteristics that cause Nighthawk to perform poorly.
%Randomized unit testing schemes in general require many test
%cases to be executed, so they perform poorly on methods that do
%a significant amount of disk I/O or thread generation.
%%  They also
%%perform poorly on methods expecting string inputs that are
%%sentences in a grammar; we expect Nighthawk to do the same
%%unless it is given valid sentences as seed strings.
%
%Nighthawk uses Cobertura, which measures line coverage, a weak
%coverage measure.  The results that we obtained may not extend
%to stronger coverage measures.  However, the Nighthawk algorithm
%%treats the coverage measurement as a black-box integer, and
%does
%not perform special checks particular to line coverage.  The
%comparison studies suggest that it still performs well when
%decision/condition coverage and MCC are simulated.
%The question of whether code coverage measures are a good
%indication of the thoroughness of testing is still, however, an
%area of active debate in the software testing community, making
%this a threat to construct validity.
%
%Time measurement is also a threat to construct validity. 
%We measured time using Java's {\tt systemTimeInMillis}, which
%gives total wall clock time rather than CPU time.  This may give
%run time numbers that do not reflect the actual cost to the user
%of the testing.
%
%\section{Data Mining-Based Optimization}
%
%It is recognized that the design of genetic algorithms is a
%``black art'' \cite{ga-blackart}, and that very little is known
%about why GAs work when they do work and why they do not work
%when they do not.  In the initial design of Nighthawk, we got
%the GA to control many aspects of the randomized testing
%algorithm, as reflected by the ten gene types listed in Figure
%\ref{gene-types-fig}.  This was the result of our expectation
%that any of them might turn out to be crucial to the success
%of the system, and our inability to predict which.
%
%However, for a genetic algorithm, every gene that is not useful
%results in time wasted:  time is spent mutating genes that do
%not lead to better solutions, and time is also spent extracting
%values from genes instead of simply using constant values.
%This effect is especially pronounced for Nighthawk, since some
%genes control code inside the innermost loops of the randomized
%testing algorithm.  We were therefore motivated to find whether
%we could speed up Nighthawk by eliminating gene types that did
%not lead to better performance.
%
%In this section, we describe how we used feature subset
%selection (FSS) to analyze data from Nighthawk runs, in order to
%systematically examine the usefulness of each gene type.
%We also describe how we optimized the system by eliminating the
%least useful genes, resulting in a system that achieved the same
%quality of results in less time.
%
%\subsection{Feature Subset Selection}
%
%
%Since our goal was to identify gene types that were not useful and
%that could therefore possibly be eliminated from chromosomes, we
%tabulated the properties of each of the different types of genes.
%Figure \ref{genes-merit-fig} shows the result.  The three most
%useful types of genes for the software under test were clearly
%{\tt candidateBitSet},
%{\tt valuePoolActivityBitSet}, and
%{\tt upperBound},
%since genes of these types sometimes had merit 90\% or more of
%the maximum merit, often were ranked first or second in merit,
%and were the only gene types such that some genes of that type
%had merit greater than $0.2$ on some runs.  This result confirms
%our intuition that changing the value reuse policy encoded in
%the genes of type 
%{\tt candidateBitSet} and
%{\tt valuePoolActivityBitSet}
%is an important way of improving the performance of a Nighthawk
%chromosome.
%The good performance of {\tt upperBound} is attributable to the
%fact that for all the hash table-related units, adjusting this
%parameter caused a ``load factor'' parameter in some of the
%constructors to be able to take on values that led to the table
%being reallocated frequently.
%
%Just as clearly, the two least useful gene types for the
%software under test were
%{\tt chanceOfNull} and
%{\tt numberOfValuePools}, since neither were ranked better than
%than 14th in merit for any run.
%This does not indicate that null values and multiple value pools
%for each type were not important, only that changing the default
%values of these genes (3\% chance of choosing null, and two
%value pools) did not usually result in improved performance.
%
%\subsection{Optimization and Performance Comparison}
%
%In order to see whether our analysis was useful, we optimized
%the Nighthawk code.
%We decided to retain the four gene types with
%the highest maximum merit
%({\tt candidateBitSet},
%{\tt valuePoolActivityBitSet},
%{\tt upperBound}, and {\tt numberOfCalls}),
%and also two other gene types:
%{\tt lowerBound}, because it was paired with 
%{\tt upperBound}; and
%{\tt numberOfValues}, because it had the highest maximum
%merit of the remaining well-ranked gene types.
%
%
%Accordingly, we adjusted Nighthawk's code to delete all
%references to the other four gene types
%({\tt chanceOfNull},
%{\tt numberOfValuePools},
%{\tt chanceOfTrue}, and
%{\tt methodWeight}).  We changed the code that depended on the
%values stored for such genes in the current chromosome, so that
%it instead used the default initial values for those gene types.
% 
%On each of the 16 Collection and Map classes,
%we performed one run of the original Nighthawk,
%and one run of the new, optimized version.
%For each version of Nighthawk, we then
%performed the same analysis that is reflected in Figures
%\ref{collection-map-cov} and
%\ref{collection-times};
%that is, we asked RunChromosome to run 10 test cases with the
%winning chromosome and measured the coverage, and we calculated
%the clock time taken by Nighthawk to achieve the highest
%coverage it achieved.  We then compared the original and
%optimized Nighthawk.
%
%The chromosomes resulting from the optimized Nighthawk achieved
%slightly higher coverage than those from the original, though a
%$t$ test concluded that the difference was not statistically
%significant ($p=0.058$).  However, the optimized Nighthawk was
%faster to a statistically significant degree ($p=0.010$).  The
%time ratio between the original and optimized systems
%was 1.46, i.e.\ the
%optimized system was 46\% faster.  We can therefore say that
%the process of analyzing the usefulness of the genes resulted
%in a system that ran substantially more quickly but achieved the
%same high coverage of the SUT.
%
%\subsection{Discussion}
%
%The feature subset selection and optimization procedure worked
%well for us when we collected data from a set of classes and
%then optimized Nighthawk for those classes.  This does not mean
%that the optimized Nighthawk would necessarily work
%well for other classes.  For instance, for some classes there
%might be a great deal of code that is accessible only by giving
%null pointers as parameters; we could expect our newly optimized
%version of Nighthawk to perform poorly on such classes, since
%there would be a fixed 3\% chance of choosing null.
%
%However, the results of the optimization exercise indicate that
%FSS-based analysis is a valuable adjunct to the GA in this
%application.  It is for this reason that we envision in the
%future integrating FSS into a genetic-random testing algorithm,
%so that the algorithm can improve its performance dynamically,
%while GA mutation and recombination is going on.
%\section{Conclusions and Future Work}
%
%Randomized unit testing is a promising technology that has been
%shown to be effective, but whose thoroughness depends on the
%settings of test algorithm parameters.  In this paper, we have
%described Nighthawk, a system in which an upper-level genetic
%algorithm automatically derives good parameter values for a
%lower-level randomized unit test algorithm.  We have shown that
%Nighthawk is able to achieve the same coverage as earlier
%studies, and high coverage of complex, real-world Java units,
%while retaining the most desirable feature of randomized
%testing: the ability to generate many new high-coverage test
%cases quickly.
%We have also shown that we were able to simplify the design
%of the GA system and improve its runtime using automatic
%feature subset selection.
%
%Future work includes the integration into Nighthawk of useful
%facilities from past systems, such as failure-preserving or
%coverage-preserving test case minimization, and further
%experiments on the effect of program options on coverage and
%efficiency.  We also wish to integrate a feature subset
%selection learner into the GA level of the Nighthawk algorithm
%for dynamic optimization of the GA.
%
%%\begin{itemize}
%%\item While the predicate coverage proposed by Visser et al.\ is
%%  an interesting assessment criteria, there is no consensus in the
%%  literature on the connection of this criteria to other measures.
%%\item Static code analysis can direct the generation of the test
%%  cases.  Our method, on the other hand, generates test cases at
%%  random, so it is possible that we cover some code more than is
%%  necessary, and that parts of our value pools are
%%  useless.  Our view is that this is not a major issue since our
%%  runtimes, on real-world systems, are quite impressive. 
%%  Nevertheless, there needs to be more discussion on how to
%%  assess test suite generation; i.e.\ runtimes versus
%%  superfluous tests versus any other criteria.
%%\end{itemize}
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% Reminder: the "draftcls", not "draft", class option should be used if
%% it is desired that the figures are to be displayed while in draft mode.
%
%% An example of a floating figure using the graphicx package.
%% Note that \label must occur AFTER (or within) \caption.
%% For figures, \caption should occur after the \includegraphics.
%%
%%\begin{figure}
%%\centering
%%\includegraphics[width=2.5in]{myfigure.eps}
%%\caption{Simulation Results}
%%\label{fig_sim}
%%\end{figure}
%
%
%% An example of a double column floating figure using two subfigures.
%% (The subfigure.sty package must be loaded for this to work.)
%% The subfigure \label commands are set within each subfigure command, the
%% \label for the overall fgure must come after \caption.
%% \hfil must be used as a separator to get equal spacing
%%
%%\begin{figure*}
%%\centerline{\subfigure[Case I]{\includegraphics[width=2.5in]{subfigcase1.eps}
%%\label{fig_first_case}}
%%\hfil
%%\subfigure[Case II]{\includegraphics[width=2.5in]{subfigcase2.eps}
%%\label{fig_second_case}}}
%%\caption{Simulation results}
%%\label{fig_sim}
%%\end{figure*}
%
%
%
%% An example of a floating table. Note that, for IEEE style tables, the
%% \caption command should come BEFORE the table. Table text will default to
%% \footnotesize as IEEE normally uses this smaller font for tables.
%% The \label must come after \caption as always.
%%
%%\begin{table}
%%% increase table row spacing, adjust to taste
%%\renewcommand{\arraystretch}{1.3}
%%\caption{An Example of a Table}
%%\label{table_example}
%%\centering
%%% The array package and the MDW tools package offers better commands
%%% for making tables than plain LaTeX2e's tabular which is used here.
%%\begin{tabular}{|c||c|}
%%\hline
%%One & Two\\
%%\hline
%%Three & Four\\
%%\hline
%%\end{tabular}
%%\end{table}
%
%
%% if have a single appendix:
%%\appendix[Proof of the Zonklar Equations]
%% or
%%\appendix  % for no appendix heading
%% do not use \section anymore after \appendix, only \section*
%% is possibly needed
%
%% use appendices with more than one appendix
%% then use \section to start each appendix
%% you must declare a \section before using any
%% \subsection or using \label (\appendices by itself
%% starts a section numbered zero.)
%%
%% Use this command to get the appendices' numbers in "A", "B" instead of the
%% default capitalized Roman numerals ("I", "II", etc.).
%% However, the capital letter form may result in awkward subsection numbers
%% (such as "A-A"). Capitalized Roman numerals are the default.
%%\useRomanappendicesfalse
%%
%% you can choose not to have a title for an appendix
%% if you want by leaving the argument blank
%%\section{}
%%Appendix two text goes here.
%
% use section* for acknowledgement

\section*{Acknowledgment}
% optional entry into table of contents (if used)
%\addcontentsline{toc}{section}{Acknowledgment}
%Thanks to Willem Visser for making the source code of the Java
%Pathfinder subject units available, and to the JDEAL development
%team for their tool package.
%Thanks also for interesting
Thanks for interesting
comments and discussions to Rob Hierons, Charles Ling, Bob
Mercer and Andy Podgurski. 
This research is supported by the first author's grant from the
Natural Sciences and Research Council of Canada (NSERC).


% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section
% NOTE: BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/

% if you will not have a photo
%\begin{biographynophoto}{John Doe}
%Biography text here.
%\end{biographynophoto}

% insert where needed to balance the two columns on the last page
%\newpage

%\begin{biographynophoto}{Jane Doe}
%Biography text here.
%\end{biographynophoto}

% You can push biographies down or up by placing
% a \vfill before or after them. The appropriate
% use of \vfill depends on what kind of text is
% on the last page and whether or not the columns
% are being equalized.

%\vfill

% Can be used to pull up biographies so that the bottom of the last one
% is flush with the other column.
%\enlargethispage{-5in}

% that's all folks
\bibliographystyle{abbrv}
\bibliography{my,refs}
\end{document}

