Authors’ Responses to Reviewers

Thank you for your thoughtful and thorough reviews. We have revised the paper and give our responses to your comments below.

0.1 Reviewer 1

The paper describes a system which uses a genetic algorithm to
find a good setup for a randomised unit testing framework.
One of the immediate concerns that come to mind is, how the
tuning of the GA compares to manually tuning the randomised
testing framework. The authors state that the randomised unit
testing framework requires expert knowledge of the framework in
order to make it effective. A GA typically also requires expert
knowledge, as there are so many parameters to tune, and by the
authors own admission, generally finding a good set of
parameters for a GA can be a bit of a "black art". The proposed
framework may be better suited for someone with good knowledge
of GAs, while the randomised unit testing framework without the
GA might be better suited for an expert in randomised unit
testing who has little or no knowledge of GAs. I feel this point
is not adequately addressed in the paper, and I would have liked
to see a study with independent experts, comparing RUTE-J and
Nighthawk.

The authors imply that one of the benefits of their approach
over an evolutionary testing based approach is that their method
does not produce minimal test suites. While it is true that a GA
is typically aimed at different targets in turn, this does not
automatically result in a minimal test suite. Consider the
following example for illustration of a point:
foo(int b){
   int cnt = 0;
   while( 1){
if(cnt >= b){
//target 1
goto while_break;
}else{
//target 2
}
cnt++;
   }
   while_break:
   if(cnt == 5)
//target 3
  else

//target 4
}
A minimal test suite to cover all targets would consist of 2
test cases. However, a "traditional" GA based strategy could
generate anything from 2-4 test cases, depending on order of
attempting targets, if you omit branches covered by previous
test cases (which you might not want to do),  etc.
Further, on Page 10 the authors make the point that a minimal
coverage preserving test set has reduced fault detection
capabilities. Yet, as future work, they plan to include
"...coverage-preserving test case minimisation..." ?
Section C - Page 12:
I am not sure whether the authors are measuring efficiency or
effectiveness of weights, because they report on the amount of
code covered (effectiveness), not the time it took to achieve
more or equal coverage (efficiency)
Section 4 A - Page 15:
Figure 4, step 6 c); what is the rationale for always replacing
an existing value with a returned value for non-primitive types
and valid primitive types? E.g. why not use some probabilistic
replacement strategy?
In Figure 3, step 2 b), if the method tryRunMethod returns a
failure or exception indication, the result is still placed in a
value pool? I think a little more detailed description of the
algorithm would help (maybe add a step 2 c) to Figure 3 )
Page 19:
"The fitness function for a chromosome is calculated in a
manner..." . You calculate the fitness of a chromosome, not the
fitness function :)

0.2 Reviewer 2

This manuscript discusses the use of a genetic algorithm to
derive good parameters for the randomised (unit) testing.
The topic is relevant and interesting, and the paper is well
written and - on the whole - easy to read and understand.
Compared to the earlier conference paper by the same authors,
there is additional empirical work on optimising the GA using a
data mining approach, and an expanded section on related work.

However, the experimental approach is not sound from a
statistical point of view, and the material additional to the
authors' conference paper may not be sufficiently substantial to
distinguish this article from the conference paper.  It is
important to note that the additional material on optimisation
of the GA is not as clearly explained as the rest of the
manuscript.

(Line numbers below refer to the 'ruler' added during the
submission process to the left hand margin of the manuscript
pages, and not the actual line numbers. Particularly important
comments are highlighted with '*'.)

Content
-------
General comments on content:
* (1) For what reason was a GA used as the 'upper-level' process
for finding optimal parameters for the randomised unit testing
'lower-level'.  For example, could a Design-of-Experiments
methodology be used, or a deterministic technique, such as
Operational Research methods, be applied.  It is unclear why
there is a motivation to use a GA for this purpose as opposed to
other, potentially more effective and efficient, techniques.
* (2) * p11 line 40 (and also acknowledged, but not addressed,
in the Threats to Validity) Using these three classes taken from
java.util is very unlikely to form a representative sample: they
are likely to be coded to similar standards and have the similar
high-level purposes.  Including code from a variety of sources,
used in very different circumstances, not just code from a
single JDK, would be more convincing.  (Similarly for the java
1.5.0 collection and map classes, p23 Section VI, etc.)
* (3) p12 line 14 (and elsewhere: p26, line 22; p32, line 23
etc.) Use of the t-test: the t-test assumes that the responses
are from a normal distribution (or in this context, that the
'stochastic noise') shows a normal distribution.  There is no
evidence presented that this is the case.  If the responses are
not from a normal distribution, such parametric tests can be
very unreliable.  A non-parametric test would be more suitable
in this case.
* (4) The comparison made in section VI between different
configurations of Nighthawk all used the same GA parameters (as
far as I can tell).  It's entirely possible that for different
settings of the GA, the comparison might have favoured different

configurations of Nighthawk, i.e. there might be interactions
between the GA setting and the best Nighthawk configuration.  A
more principled approach would be to 'tune' the GA for each of
the four configurations in an equivalent manner.  If the GA
parameters used where those that had been found (by trial and
error) to be best for one configuration (e.g. PN) in the
previous case study, then this might well have introduced a
significant bias in favour of PN.
* (5) Compared to the rest of the paper, I found the section on
Data Mining-Based Optimization, particularly difficult to read and
understand, such as:
  - p28, line 16, the introduction of the terminology "sensors"
    and "actuators"
  - p28, paragraphs beginning at lines 25, 38 and 45
  - p27, line 49, the terminology "class" and "opposite class"
    (which are different from the usage of "class" as an OO in the
    rest of the manuscript)
  - the discussion in subsection B starting, particularly the
    paragraph starting at p30, line 26
(6) It is not explicitly stated that the technique is used for
testing object-oriented software, although such terminology is
used throughout.  It would help to clarify what aspect, if any,
are particular to OO software, and whether the technique is
compatible with the testing of non-OO code.
Other comments:
p1, line 40 - index terms could include search-based
optimisation for software engineering or similar
p1, line 42 "Nighthawk uses only the Java reflection facility
... makings its general approach ... adaptable to other
languages."  It's not clear how the approach would be adaptable
if other languages did not provide an equivalent mechanism to
gather information about the SUT.
p4, line 20 "We compare Nighthawk to other systems ... showing
that it can achieve the same coverage levels." If this is the
case, what is the advantage in using Nighthawk.  Is it faster,
more efficient, more generally applicable, or does it in fact
achieve better coverage levels?
p6, section B - it's not clear how the discussion of analysis of
*white box, structural* test data generation techniques is
relevant to a manuscript on randomised unit testing.
* p9 Fig 1 (and 2?)  If x and y are integer values, then the
"spikes" at non-integer values are artifacts from arbitarily

joining the discrete points at integer values of x and y with an
arbitary 0 vertical axis value.  Instead of spike there are just
points at equal integer values of x and y.  (The argument still
holds - the points are a jump up from the plain - but the
diagram is misleading.   If x and y are real values, then there
are no spikes: there is only a ridge along the line x=y.
p10 line 4 "We further consider not only numeric data, but data
of any type."  It isn't explained here, or later, how the
concept of "lo" and "hi" bound, or a "range" can be achieved for
non-ordinal data types.
p11, line 50 "We ran the two-level algorithm 50 times" (and
elsewhere, e.g., p21, line 23): why 30 times?  Why not 50, 100
or 10?  For example, was any analysis performed to show that 30
produced statistically robust results?
p12, line 18 "statisticallly significant" - what significance
level was used?
p19, line 11 "Nighthawk uses ... settings ..."  Some
justification was made for these default values.  Was any work
done to show that the settings do indeed minimise the number of
chromosome evaluations as implied?
* p2 Fig 6 (and for all other results) - would be helpful to
give confidence intervals as well as mean values (where
appropriate) in order to give an indication of the variance in
the results
p22, line 38 "We than ran ..." It would be helpful to clarify
what hypothesis was being tested by the experiments described in
this paragraph, and what the results indicate.
p23, line 36 "... is a reasonable goal for system test ..."
Although the intended meaning of "system test" used in this
quote isn't clear, it's possible that it is referring to a much
higher level test than the types of *unit* test performed in
this manuscript
p26, line 18 "... we report the number of seconds ... taken ...
to first achieve its best coverage."  While this may be
appropriate for experimental work, it is not suitable to compare
the practicality of the technique.  In practice, the user (and
the tool) will not know what the best coverage is, and so it
will be run for a set period of time - which may be much longer
than time at which the best coverage was found - and the best
coverage over the entire period.  Therefore, it would be
particularly useful to report confidence intervals (or variance)
in this case.

p26, line 40, section VII - ideally, the Threats To Validity
section should come after the experimental work on feature
subset selection and encompass that work also.
p31, line 31 - it would be helpful to include in the discussion
of the good performance of "upperBound", some speculation on why
"lowerBound" does not demonstrate a similar good performance.

Typographical and Formatting —————————-

p9 Fig 1: is the vertical axis value in this case a probability, or just a fitness score?

0.3 Reviewer 3

Comments:
My main reason for requesting a major revision of this article
is its similarity with the already published paper (ASE'07).
Although the authors take pains to point out the differences,
these only constitute a broader literature review (to be
expected, given the constraints imposed by the length of
conference papers) and a small section on feature subset and
optimization which does not, in my opinion, bring the paper up
to TSE standard. The other results in the paper are identical to
those reported in ASE and hence the majority of the paper has
nothing new to report. There was an opportunity here to expand
on the experiments and also address some of the threats to
validity identified by considering a wider set of target programs.
There are also a number of more minor issues which the authors
should consider if they choose to submit a revised version of
the paper:
- One of the main motivations behind the work is the avoidance
of any deep analysis of programs, although the drawbacks of thos
approaches which employ source/bytecode anaysis are not
identified. Also it is pointed out that the use of a pool of
data can help solve some of the problems posed by equality
comparisons in predicates, but the construction of the pool, and
in particular the identification of the upper and lower bounds,
is not well explained. It is hard to imagine how these bounds
are identified in the general case.
- Another element of confusion is the "weight" of the methods.
This is explained as its calling frequency but again there is no
explanation of how this is derived. This is disappointing as
this is shown to be an important factor in some case and again
it is hard to speculate whether this could be derived
automatically or whether it is important domain information
supplied by the user.
- Small point at the foot of page 12 - a solution cannot be

"more optimal"
-In the description of the Nighthawk system it is unclear why
the return values of the methods are important.
-There is something strange about the classification of
constructors as initializers or reinitializers - it would appear
to be considered as both if it has no parameters. Perhaps this
is inteded...
- Regarding the algorithm descriptions, an example would be
useful to illustrate the contents of concepts such as the value
pool (the constructionof which is also unclear) and show how the
algorithms operates (also a one-sentence description of the aim
of each algorithm would help).
- How is the success or failure of a test case determined?
- The meanings of the parameters p, g and m should be explained
for those readers not familiar with the GA literature.
- The paper talks about "the most fit chromosome" (section
IV-D). Is there always only one?
- In section V it would again be useful to know what lower and
upper bounds were empoyed on the data and how these were
identified, as i'm sure that these are crucial in understanding
and explaining the results.
- In V-B please explain why Nighthawk was able to cover
significantly more lines of code when using the full target classes.
- The figure or 70-80% being a reasonable coverage goal quoted
at the end of section V-B is slightly misleading since it would
appear to relate to system test and these are unit tests that
are being carried out.
- The last paragraph of section VI is confusing. It is stated
that t-test showed some results to be significantly different,
and in the following sentence it is claimed that "enriched
wrappers allowed Nighthawk to cover significantly more code
without running significantly longer". You can't have it both ways!

0.4 Reviewer 4

This paper presents Nighthawk, a two-stage system where a
high-level genetic algorithm is used to compute parameter values
used by a lower-level random test generation algorithm with the
goal of maximizing test coverage for unit testing. Results of
experiments with several examples of Java programs are discussed.
Overall, I found the paper interesting and mostly well written.
The key focus of the genetic-algorithm techniques used in this
work seems to be in deriving proper sequences and parameters of
method calls for unit testing of object-oriented software. It is
therefore closely related to Randoop [3]. Although the
heuristics used in [3] are not described using genetic-algorithm
terminology, I wonder how the two approaches really differ. A

more detailed comparison with [3] than the short one on page 6
would be welcome.
A key originality of Nighthawk seems to be its two-stage
algorithm, where genetic algorihms are not used to generate
tests directly, but rather set parameters in another random test
generation algorithm.  Although I am familiar with the general
principles of genetic algorithms, I am not an expert and I have
not kept up with the numerous applications of those algorithms
in software engineering, so I cannot comment on the novelty of
the approach. (It definitely sounds new to me.)
The comparison with analysis-based test generation approaches is
slightly biased. First, it is not true that (page 7) these
approaches "are as yet infeasible except for small software
units": for instance, see [Automated Whitebox Fuzz Testing,
NDSS'2008]. Second, the argumentation made in section 2.D (page
8) about the complementarity of lighter-weight random testing
and heavier-weight analysis-based approaches makes sense only if
randomized testing remains lightweight.  For generating values
of inputs x and y satisfying "x==y", it seems cheaper to extract
this constraint and solve it directly once for all rather than
painfully converging (maybe -- no guarantees here) in a
convoluted way towards a solution through multiple iterations of
Nighthawk and many tests (see page 9). To illustrate the
complementarity of both approaches, the authors could use an
example where the effectiveness of analysis-based methods is
questionable, such as inferring proper sequences of method calls
given only the APIs (type signatures) of those methods.
Unfortunately, I cannot comment on the "data mining-based
optimization" part (section 8) of the paper.