Adaptive Random Testing

T.Y. Chen1,
, H. Leung2 , and I.K. Mak3

1

School of Information Technology, Swinburne University of Technology,

Hawthorn, Victoria 3122, Australia
tchen@[Link]
2
Department of Computer Science, New Mexico State University,
Las Cruces, NM 88003, U.S.A.
hleung@[Link]
3
School of Professional and Continuing Education,
The University of Hong Kong, Pokfulam Road, Hong Kong
[Link]@[Link]

Abstract. In this paper, we introduce an enhanced form of random

testing called Adaptive Random Testing. Adaptive random testing seeks
to distribute test cases more evenly within the input space. It is based on
the intuition that for non-point types of failure patterns, an even spread
of test cases is more likely to detect failures using fewer test cases than
ordinary random testing. Experiments are performed using published
programs. Results show that adaptive random testing does outperform
ordinary random testing signicantly (by up to as much as 50%) for
the set of programs under study. These results are very encouraging,
providing evidences that our intuition is likely to be useful in improving
the eectiveness of random testing.

Introduction

There are basically two approaches towards the selection of test cases, namely
the white box and the black box approach. Among the black box techniques,
random selection of test cases is generally regarded as not only a simple but also
an intuitively appealing technique (e.g. see White [1]). In random testing, test
cases may be randomly chosen based on a uniform distribution or according to
the operational prole. As pointed out by Hamlet [2], the main merits of random
testing include the availability of ecient algorithms to generate its test cases,
and its ability to infer reliability and statistical estimates.
In all random testing studies, only the rate of failure-causing inputs (hereafter
referred to as the failure rates) is used in the measurement of eectiveness. For
example, the expected number of failures detected and the probability of detecting at least one failure are all dened as functions of the failure rates. However,
in a recent study by Chan et al. [3], it has been found that the performance of
a partition testing strategy depends not only on the failure rate, but also on the

Corresponding author.

M.J. Maher (Ed.): ASIAN 2004, LNCS 3321, pp. 320329, 2004.
c Springer-Verlag Berlin Heidelberg 2004

Adaptive Random Testing

321

geometric pattern of the failure-causing inputs. This has prompted us to investigate whether the performance of random testing can be improved by taking the
patterns of failure-causing inputs into consideration. We have developed a new
type of random testing, namely adaptive random testing. Our studies show that
the eectiveness of random testing can be signicantly improved without incurring signicant overheads. We observe that adaptive random testing outperforms
ordinary random testing in general.

Preliminaries

In this study, we assume that the random selection of test cases is based on
a uniform distribution and without replacement. As a reminder, most of the
analytical studies of random testing assume that selections are with replacement
[4]. The assumption of selection with replacement has long been criticised by
practitioners, because in reality, test cases should not be repeated. It has been
used mainly because it has a simpler mathematical model and hence of easier
analysis. Thus, the model of our study reects the reality more closely.
We basically follow the notation used by Chen and Yu [4]. Elements of an
input domain are known as failure-causing inputs, if they produce incorrect
outputs. For an input domain D, we use d, m and n to denote the size, number
of failure-causing inputs and number of test cases, respectively. The sampling
n
m
rate and failure rate are dened as
and , respectively.
d
d
In previous studies of random testing, the two most popular eectiveness
metrics are: the probability of detecting at least one failure (referred to as the
P-measure) and the expected number of failures detected (referred to as the
E-measure). There have been some criticisms on these two metrics despite their
popularity. The main criticism of using the E-measure is that higher E-measures
do not necessarily imply more faults or more distinct failures; and the main
disadvantage of using the P-measure is that there is no distinction between
cases of detecting dierent number of failures. Although these two measures are
not ideal, they have been used extensively in the literature.
In this paper, rather than using the P-measure and the E-measure as the
eectiveness metrics as done in previous studies, we propose another eectiveness metric. We use the expected number of test cases required to detect the
rst failure (referred to as the F-measure), as the eectiveness metric. For random selection of test cases with replacement, the F-measure, denoted by F , is
1
d
equal to , or equivalently . Intuitively speaking, the F-measure reects the

m
eectiveness of a testing strategy more naturally and directly, as the lower the
F-measure the more eective the testing strategy because fewer test cases are
required to reveal the rst failure. In practice, when a failure is detected, testing
is normally stopped and debugging starts. The testing phase would normally be
resumed only after xing of the fault. Hence, the F-measure is not only more
intuitively appealing but also more realistic from a practical perspective.

322

T.Y. Chen, H. Leung, and I.K. Mak

In a recent study, Chan et al. [3] have observed that the performance of
some partition testing strategies varies with the patterns of failure-causing inputs
(hereafter referred to as the failure patterns). They have classied the patterns
of failure-causing inputs into three categories: point, strip and block patterns.
To illustrate this, let us assume that the input domain has two dimensions.
Figures 1-3 show the point, strip and block patterns, respectively. The outer
boundaries represent the borders of the input domain and the lled regions denote the failure-causing inputs, that is the failure patterns, in each of the gures.
q
q
q
q
q
q
q

q
q
q
q
q
q
q

q
q
q
q
q
q
q

q
q
q
q
q
q
q

q
q
q
q
q
q
q

q
q
q
q
q
q
q

Fig. 1. Point Pattern

Fig. 2. Strip Pattern

Fig. 3. Block Pattern

The main characteristic of the point pattern is that either the failure-causing
inputs are stand alone points, or they form regions of a very small size which are
scattered over the whole domain. For the strip pattern, the failure-causing inputs
form the shape of a narrow strip. A typical example of this failure pattern is White
and Cohens [5] domain errors. For the block pattern, the main characteristic is
that the failure-causing inputs are concentrated in either one or a few regions.

Adaptive Random Testing

With ordinary random testing, the chances of hitting the failure patterns, that is
selecting failure-causing inputs as test cases, depends solely on the magnitude of
the failure rate. However, a closer inspection shows that for non-point patterns
which include both the strip and block patterns, the failure detection capability
can be signicantly improved by slightly modifying the ordinary random testing
technique. Let us use an example to illustrate the intuition behind our modied
random testing.
Consider an input domain D. Suppose D has a regular geometry, that is,
we assume that it is easy to generate inputs randomly from D. Let there be a
fault in the program. For example, let the input in D be consisting of values x
and y where 0 x, y 10. Suppose the fault lies in a conditional expression
x+y >3
at a program statement while the correct expression should have been
x+y >4

Adaptive Random Testing

323

Specically, the domain D is a square {(x, y) | 0 x, y 10}. The fault

corresponds to a failure region {(x, y) | 3 < x + y 4}, which is a strip of
width 1 across the square domain D.
We consider applying random testing to the program. Suppose we generate
one test case (2.2,2.2). Since 2.2+2.2 is larger than 4, the fault is not revealed.
Let the next test case generated be (2.1,2.1). Should we know in advance that
the error region is a strip of width 1, we could argue that the choice of the second
test case is too humble. The test set should better be more spaced out such
that two neighbouring test cases are kept apart by a distance of length at least 1.
Thus, we propose to modify random testing as follows. To generate a new
test case, we need to make sure that the new test case should not be too close
to any of the previously generated ones. One way to achieve this is to generate a
number of random test cases and then choose the best one among them. That
is, we try to distribute the selected test cases as spaced out as possible.
To summarize, we conjecture that test cases should be as evenly spread over
the entire input domain as possible in order to achieve a small F-measure. This
forms the basis of our new method of random testing, namely Adaptive Random
Testing.
An implementation of Adaptive Random Testing is as follows: Adaptive random testing makes use of two sets of test cases, namely the executed set and the
candidate set which are disjoint. The executed set is the set of distinct test cases
that have been executed but without revealing any failure; while the candidate
set is a set of test cases that are randomly selected without replacement. The
executed set is initially empty and the rst test case is randomly chosen from the
input domain. The executed set is then incrementally updated with the selected
element from the candidate set until a failure is revealed. From the candidate
set, an element that is farthest away from all executed test cases, is selected as
the next test case.
Obviously, there are various approaches to implement the intuition of farthest away. In this paper the criterion for implementing this intuition is dened
as follows. Let T = {t1 , t2 , , tn } be the executed set and C = {c1 , c2 , , ck }
be the candidate set such that C T = . The criterion is to choose the element
ch such that for all j {1, 2, , k},
n

i=1

i=1

min dist(ch , ti ) min dist(cj , ti )

where dist is dened as the Euclidean distance.
In other words, in an m-dimensional

input

domain, for inputs
n
2
a = (a1 , a2 , , am ) and b = (b1 , b2 , , bm ), dist(a, b) =
i=1 (ai bi ) . The
rationale of this criterion is to evenly spread the test case through maximising
the minimum distance between the next test case and the already executed test
cases.
It should be noted that there are also various ways to construct the candidate
set giving rise to various versions of adaptive random testing. It will be quite
dicult, if not impossible, to carry out an analytical study for the performance

324

T.Y. Chen, H. Leung, and I.K. Mak

Table 1. Program name, dimension (D), input domain, seeded error types, and total
number of errors for each of the error-seeded programs. The error types are: arithmetic
operator replacement (AOR); relational operator replacement (ROR); scalar variable
replacement (SVR) and constant replacement (CR)
Prog
Name
airy
bessj
bessj0
cel
el2
erfcc
gammq
golden

plgndr
probks
sncndn
tanh

Input Domain
Error Type
Total Failure
D
From
To
AOR ROR SVR CR Errors Rate
1
(5000.0)
(5000.0)
1
4
0.000716
2 (2.0, 1000.0) (300.0, 15000.0) 2
1
1
4
0.001298
1 (300000.0)
(300000.0)
2
1
1
1
5
0.001373
4 (0.001, 0.001,
(1.0, 300.0,
1
1
1
3
0.000332
0.001, 0.001) 10000.0, 1000.0)
4
(0.0, 0.0,
(250.0, 250.0,
1
3
2
3
9
0.000690
0.0, 0.0)
250.0, 250.0)
1 (30000.0)
(30000.0)
1
1
1
1
4
0.000574
2
(0.0, 0.0)
(1700.0, 40.0)
3
1
4
0.000830
3
(100.0,
(60.0,
3
1
1
5
0.000550
100.0,
60.0,
100.0)
60.0)
3
(10.0, 0.0,
(500.0, 11.0,
1
2
2
5
0.000368
0.0)
1.0)
1 (50000.0)
(50000.0)
1
1
1
1
4
0.000387
2
(5000.0,
(5000.0,
4
1
5
0.001623
5000.0)
5000.0)
1
(500.0)
(500.0)
1
1
1
1
4
0.001817

of the adaptive random testing in comparison with the ordinary random testing
with respect to the F-measure. Therefore, we conduct an empirical study in this
paper.

An Empirical Study on Adaptive Random Testing

In this section, an empirical investigation was conducted to compare the performance between adaptive random testing and ordinary random testing, using the
F-measure as the eectiveness metric, which is dened as the expected number
of test cases required to detect the rst failure. In this paper, Fa and Fr are used
to denote the F-measures for the adaptive random testing and ordinary random
testing, respectively. Unless otherwise specied, ordinary random testing would
be abbreviated as random testing or RT.
In this empirical study, we use a set of 12 error-seeded programs. They are
all published programs ([6, 7]), which are written in Fortran, Pascal or C with
program sizes ranging from 30 to 200 statements. All of them involve numerical
computations and have been converted into C++ programs. Table 1 lists details
of the failure rate, type and number of seeded errors for each program.
The candidate set is of constant size and a new candidate set is constructed
each time a test case is selected. Let us refer it as the Fixed Size Candidate Set
Version of the Adaptive Random Testing (abbreviated as the FSCS). Algorithm
1 describes how to generate a candidate set and select a test case for this version
of adaptive random testing.

Adaptive Random Testing

325

Firstly, we conducted a preliminary study to see how the size of the candidate set would aect the performance of the adaptive random testing for our
sample of 12 programs. The range of the size of the candidate set, k, was set
to vary from 2 to 10 with an increment of 2 and then from 10 to 100 with an
increment of 10. We have observed that in general, the larger the k, the smaller
the number of test cases required to detect the rst failure. Furthermore, for
k 10, there not much dierence in the number of test cases required to detect the rst failure in our sample of programs. Hence, we set k = 10 in our
experiment.
Algorithm 1:
/*
selected set := { test data already selected };
candidate set := {};
total number of candidates := 10;
*/
function Select The Best Test Data(selected set, candidate set,
total number of candidates);
best distance := 1.0;
for i := 1 to total number of candidates do
candidate := randomly generate one test data from the program
input domain, the test data cannot be in
candidate set nor in selected set;
candidate set := candidate set + { candidate };
min candidate distance := Max Integer;
foreach j in selected set do
min candidate distance := Minimum(min candidate distance,
Euclidean Distance(j, candidate));
end foreach
if (best distance < min candidate distance) then
best data := candidate;
best distance := min candidate distance;
end if
end for
return best data;
end function

For each program, we applied both FSCS and RT with the same rst randomly selected test case. We obtained a pair of numbers (ua , ur ), where ua
and ur were the numbers of test cases required to detect the rst failure, using
FSCS (Algorithm 2) and RT, respectively. We called such a pair of numbers
a sample. Obviously, (ua , ur ) depends on the rst test case. Hence, the process was repeated with various randomly selected inputs as the rst test case.
The central limit theorem [8] was used to determine the size of the sample
set S = {(ua1 , ur1 ), (ua2 , ur2 ), }, that is, to determine when the process could
be stopped so that we have enough samples in S to provide reliable statistic
estimates.

326

T.Y. Chen, H. Leung, and I.K. Mak

Algorithm 2:
initial test data := randomly generate a test data from the input domain;
selected set := { initial test data };
counter := 1;
total number of candidates := 10;
use initial test data to test the program;
if (program output is incorrect) then
reveal failure := true;
else
reveal failure := false;
end if
while (not reveal failure) do
candidate set := {};
test data := Select The Best Test Data(selected set, candidate set,
total number of candidates);
use test data to test the program;
if (program output is incorrect) then
reveal failure := true;
else
selected set := selected set + { test data };
counter := counter + 1;
end if
end while
output counter;

Suppose we want to estimate the mean of the number of test cases required
to reveal the rst failure, that is, the F-measure, for FSCS with an accuracy of
r% and a condence level of (1 ) 100%, where 1 is the condence
coecient. According to the central limit theorem, the size of S required to
achieve this goal should be at least as

2
100 z a
|S| =
(1)
r a
where z is the normal variate of the desired condence level, a is the population
mean and a is the population standard deviation. Similarly, for RT,

2
100 z r
|S| =
(2)
r r
where r and r are the population mean and standard deviation, respectively.
To ensure the size of S satisfying both FSCS and RT, we take the maximum
value of equations (1) and (2), that is

2 
2 
100 z a
100 z r
(3)
|S| = max
,
r a
r r
Obviously, the larger the sample size |S|, the higher the associated condence
z, or the smaller the accuracy range r. However, larger samples mean more eort

Adaptive Random Testing

327

and resources. In our experiment, the condence level was set to 95% and r was
set to 5%. In other words, we collect samples until the sample mean is accurate
within 5% of its value at 95% condence. From the statistical tables, we know
that for 95% condence, z = 1.96. Moreover, since a , r , a and r are unknown,
estimators
a , u
r , sa and sr were used instead, respectively, where
their
nu
n
a
u
ur
r = i=1 i , sa is the standard deviation of {ua1 , ua2 , , uan },
u
a = i=1 i , u
n
n
sr is the standard deviation of {ur1 , ur2 , , urn } and n is the current size of S.
Thus, equation (3) becomes

2 
2 
100 1.96 sr
100 1.96 sa
(4)
,
|S| = max
5u
a
5u
r
The above equation was used to decide when the process of collecting (uai , uri )
could be stopped.
As shown in Table 2, the sizes of S vary with programs, but less than 3000.
In this experiment, we have chosen 3000 as the sample size for all programs to
calculate the means and standard deviations for both FSCS and RT.
Table 2. Mean Comparison Summary
Pg ID
AIRY
BESSJ
BESSJ0
CEL
EL2
ERFCC
GAMMQ
GOLDEN
PLGNDR
PROBKS
SNCNDN
TANH

k
10
10
10
10
10
10
10
10
10
10
10
10

|S|
1506
1598
1567
1550
1650
1543
1557
1569
1438
1480
1617
1469

Fa
799.29
466.66
423.93
1607.80
686.48
1004.68
1081.43
1829.74
1806.94
1442.50
628.68
306.86

95% CI of Fa
(779.43, 819.15)
(451.95, 481.38)
(412.55, 435.30)
(1552.49, 1663.11)
(661.78, 711.17)
(980.34, 1029.02)
(1044.35, 1118.51)
(1765.68, 1893.80)
(1754.47, 1859.41)
(1407.24, 1477.76)
(606.16, 651.20)
(299.21, 314.51)

Fr
1381.44
802.17
733.96
3065.25
1430.76
1803.62
1220.28
1860.81
2741.66
2634.86
636.19
557.96

95% CI of Fr
(1332.51, 1430.37)
(722.90, 831.44)
(707.44, 760.48)
(2955.10, 3175.40)
(1377.71, 1483.81)
(1738.94, 1868.30)
(1176.32, 1264.24)
(1793.52, 1928.10)
(2646.75, 2836.57)
(2542.32, 2727.40)
(612.83, 659.54)
(538.43, 577.48)

where
Pg ID
k
|S|
Fa
95% CI of Fa
Fr
95% CI of Fr

Program ID
Size of the candidate set
Size of the sample set
Mean of {ua1 , ua2 , , ua|S| }
95% Condence Interval of FSCS mean
Mean of {ur1 , ur2 , , ur|S| }
95% Condence Interval of RT mean

Table 2 lists the sample means within an accuracy of 5% and a condence level
of 95%, for all 12 programs. Also included are their 95% condence interval (CI).

328

T.Y. Chen, H. Leung, and I.K. Mak

Table 2 shows that in all 12 programs the Fa s are smaller than the corresponding Fr s, that is, on the average, FSCS required fewer test cases than RT
to reveal the rst failure. Furthermore, in 10 programs (AIRY, BESSJ, BESSJ0,
CEL, EL2, ERFCC, GAMMQ, PLGNDR, PROBKS and TANH), the corresponding FSCSs and RTs 95% condence intervals do not overlap each other.
This implies that Fa is smaller than Fr with a probability of (0.95)2 at least.
For the remaining 2 programs (GOLDEN and SNCNDN), the 95% condence
intervals of Fa and Fr overlap each other.
To calculate the performance improvement, we use the following formula:
Fr Fa
100
(5)
Fr
Table 3 shows that the performance
improvement for FSCS over RT ranges
from the best end of 52.02% to the worst end of 1.18%. Nine programs (AIRY,
BESSJ, BESSJ0, CEL, EL2, ERFCC, PLGNDR, PROBKS and TANH) show
a very signicant improvement; one program (GAMMQ) shows a moderate improvement; two programs (GOLDEN and SNCNDN) show small improvement.
In summary, FSCS has a considerably smaller F-measure than RT. The experimental results show that FSCS has a good chance at outperforming RT by a
very signicant margin, which can be as high as 50%. On the other hand, FSCS
needs more resources to select the next test case from the candidate set than RT
does. Let n be the value of the F-measure and k be the size of the candidate set
in FSCS. The selection overheads is of the order kn2 .

Conclusion

Random testing is simple in concept and is easy to be implemented. Besides, it

can infer reliability and statistical estimates. Hence, it has been used by many
testers. Since random testing does not make use of any information to generate
test cases, it may not be a powerful testing method and its performance is solely
dependent on the magnitude of failure rates.
Table 3. Improvement of the F-measure of FSCS over RT
Pg ID
Improvement in %
AIRY
42.14
BESSJ
41.83
BESSJ0
42.24
CEL
47.55
EL2
52.02
ERFCC
44.30
GAMMQ
11.38
GOLDEN
1.67
PLGNDR
34.09
PROBKS
45.25
SNCNDN
1.18
TANH
45.00

Adaptive Random Testing

329

A recent study has shown that failure patterns may be classied as point, strip
or block failure patterns. Intuitively speaking, when the failure pattern is not a
point pattern, more evenly spread test cases have a better chance of hitting the
failure patterns. Based on this intuition, we propose a modied version of random
testing called adaptive random testing. An empirical analysis of 12 published
programs has shown that adaptive random testing outperforms random testing
signicantly for most of the cases.
Our experimental results have been very encouraging, providing evidences
that our intuition of spreading test cases more evenly within the input space is
potentially very useful. Nevertheless, there are a number of issues of adaptive random testing that need to be considered, such as various criteria of evenly spreading of test cases, ways of dening the candidate sets. We anticipate that analysis
of these issues would further improve the eectiveness of adaptive random testing. In fact, we have already obtained some very interesting results [9, 10].

Acknowledgment
We would like to thank F. T. Chan, T. H. Tse and Z. Q. Zhou for their invaluable
discussions. We are also grateful to Dave Towey, who has converted the programs
used in the former experiment into C++ languages and rerun the experiment.
T. Y. Chen is particularly indebted to Jean-Louis Lassez for showing how to
be a model mentor, how to identify the incompleteness of an apparently complete
solution, and how to nd simple solutions.

References
1. White, L.J.: Software testing and verication. Advances in Computers 26 (1987)
335391
2. Hamlet, R.: Random testing. Encyclopedia of Software Engineering. Edited by
Marciniak, J. Wiley (1994)
3. Chan, F.T., Chen, T.Y., Mak, I.K., Yu, Y.T.: Proportional sampling strategy:
guidelines for software testing practitioners. Information and Software Technology
38 (1996) 775782
4. Chen, T.Y., Yu, Y.T.: On the relationship between partition and random testing.
IEEE Transactions on Software Engineering 20 (1994) 977980
5. White, L.J., Cohen, E.I.: A domain strategy for computer program testing. IEEE
Transactions on Software Engineering 6 (1980) 247257
6. Association for Computing Machinery: Collected Algorithms from ACM, Vol. I,
II, III. Association for Computing Machinery (1980)
7. Press, W.H., Flannery, B.P., Teukolsky, S.A., Vetterling, W.T.: Numerical Recipes.
Cambridge University Press (1986)
8. Freund, J.E.: Modern Elementary Statistics. Fifth edn. PrenticeHall (1979)
9. Chen, T.Y., Kuo, F.C., Merkel, R.G., Ng, S.P.: Mirror adaptive random testing.
Information and Software Technology (Accepted for publication)
10. Chen, T.Y., Eddy, G., Merkel, R., Wong, P.K.: Adaptive random testing through
dynamic partitioning. In: Proceedings of the 4th International Conference on Quality Software (QSIC 04), IEEE Computer Society Press (2004)