Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Hill Climbing
Life Cycle
Random Search
Search Algorithm
Software Development
Software Testing
Test Data Generation
Related Publications
(1)
Runtime analysis of (1+l) EA on computing unique input output sequences
Subscribe
Academic
Publications
Theoretical Runtime Analyses of Search Algorithms on the Test Data Generation for the Triangle Classification Problem
Theoretical Runtime Analyses of Search Algorithms on the Test Data Generation for the Triangle Classification Problem,Andrea Arcuri,Per Kristian Lehre
Edit
Theoretical Runtime Analyses of Search Algorithms on the Test Data Generation for the Triangle Classification Problem
(
Citations: 7
)
BibTex

RIS

RefWorks
Download
Andrea Arcuri
,
Per Kristian Lehre
,
Xin Yao
Software Testing
plays an important role in the
life cycle
of software development. Because
software testing
is very costly and tedious, many techniques have been proposed to automate it. One technique that has achieved good results is the use of Search Algorithms. Because most previous work on search algorithms has been of an empirical nature, there is a need for theoretical results that confirm the feasibility of search algorithms applied to software testing. Such theoret ical results might shed light on the limitations and benefits of search algorithms applied in this context. In this paper, we formally analyse the expected runtime of three different search algorithms on the problem of
Test Data Generation
for an instance of the Triangle Classiøcation program. The search algorithms that we analyse are Random Search,
Hill Climbing
and Alternating Variable Method. We believe that this is a necessary first step that will lead and help the Soft ware Engineering community to better understand the role of Search Based Techniques applied to software testing.
Published in 2009.
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.cs.bham.ac.uk
)
(
www.cercia.co.uk
)
(
www.cercia.ac.uk
)
(
www.cercia.ac.uk
)
(
www.cs.bham.ac.uk
)
More »
Citation Context
(4)
...Because the expected runtime of RS can be calculated by dividing the number of all solutions by the number of global optima (see for example [
2
]), that necessarily means that for longer sequences there are in proportion more optimal solutions...
...optimal solution in less than 100 iterations (see [
2
])...
Andrea Arcuri
.
Longer is Better: On the Role of Test Sequence Length in Software Test...
...We are aware of only few results, that are on computing unique input/output sequences for finite state machines [12, 11], the application of the Royal Road theory to evolutionary testing [7], and testing the triangle classification problem [
2
, 1]. Unfortunately, theoretical analyses are difficult to carry out, and that has limited their scope so far to only small problems...
...Given 1008 global optima in a search space of 105,413,504 solutions, we can use the theorems in our previous work [
2
] to calculate the exact expected time for RS. Very simply, we can just divide the total number of solutions by the number of global optima...
...The restarts of HC can be theoretically modelled like a random search process [
2
]...
Andrea Arcuri
.
Insight knowledge in search based software testing
...The only exceptions we are aware of are on computing unique input/output sequences for finite state machines [13, 12], the application of the Royal Road theory to evolutionary testing [7], and our previous work on test data generation for the Triangle Classification (TC) problem [
1
]...
...In our previous work [
1
], we proved runtimes for three different search algorithms on the coverage of one branch of the TC problem...
...The runtime analysis will therefore seek to estimate properties of the distribution of random variable TA,F (n), in particular the expected runtime E [TA,F (n)] and the success probability Pr [TA,F (n) ≤ t(n)] for a given time bound t(n). More details can be found in [
1
]...
...Proof. If we consider only the starting point, the AVM behaves as a random search, in which the probability of finding a global optimum is bigger than k. That can be described as a Bernoulli process (see our theorems on random search in [
1
]), with expected number of restarts that is lower or equal than 1/k...
...Proof. This theorem has been proved in our previous work [
1
]...
...Instead of analysing it directly, we prove the runtime by a comparison with the behaviour of AVM on the branch ID 8 (that is more complex and we already proved it in our previous work [
1
])...
...In the case for example of a runtime Θ(n2) (e.g., Random Search [
1
]), running so many...
Andrea Arcuri
,
et al.
Full Theoretical Runtime Analysis of Alternating Variable Method on th...
...The only exceptions we are aware of are on computing unique input/output sequences for finite state machines [32, 31], the application of the Royal Road theory to evolutionary testing [22], and the first versions of our work [
2
, 1]...
Andrea Arcuri
,
et al.
Theoretical Runtime Analysis in Search Based Software Engineering
References
(19)
Formulating software engineering as a search problem
(
Citations: 111
)
John A. Clark
,
José Javier Dolado
,
Robert M. Hierons
,
Bryan F. Jones
,
M. Lumkin
,
Brian S. Mitchell
,
Spiros Mancoridis
,
K. Rees
,
Marc Roper
,
Martin J. Shepperd
Journal:
Iet Software/iee Proceedings  Software
, vol. 150, no. 3, pp. 161175, 2003
Hints on Test Data Selection: Help for the Practicing Programmer
(
Citations: 645
)
R. A. DeMillo
,
R. J. Lipton
,
F. G. Sayward
Journal:
IEEE Computer  COMPUTER
, vol. 11, no. 4, pp. 3441, 1978
On the analysis of the (1+1) evolutionary algorithm
(
Citations: 281
)
Stefan Droste
,
Thomas Jansen
,
Ingo Wegener
Journal:
Theoretical Computer Science  TCS
, vol. 276, no. 12, pp. 5181, 2002
Upper and Lower Bounds for Randomized Search Heuristics in BlackBox Optimization
(
Citations: 60
)
Stefan Droste
,
Thomas Jansen
,
Ingo Wegener
Journal:
Electronic Colloquium on Computational Complexity  ECCC
, no. 048, 2003
A theoretical & empirical znalysis of evolutionary testing and hill climbing for structural test data generation
(
Citations: 15
)
Mark Harman
,
Phil Mcminn
Conference:
International Symposium on Software Testing and Analysis  ISSTA
, pp. 7383, 2007
Sort by:
Citations
(7)
Evolutionary repair of faulty software
(
Citations: 2
)
Andrea Arcuri
Journal:
Applied Soft Computing  ASC
, vol. 11, no. 4, pp. 34943514, 2011
Longer is Better: On the Role of Test Sequence Length in Software Testing
(
Citations: 10
)
Andrea Arcuri
Conference:
International Conference on Software Testing, Verification, and Validation  ICST
, pp. 469478, 2010
Insight knowledge in search based software testing
(
Citations: 4
)
Andrea Arcuri
Conference:
Genetic and Evolutionary Computation Conference  GECCO
, pp. 16491656, 2009
Full Theoretical Runtime Analysis of Alternating Variable Method on the Triangle Classification Problem
(
Citations: 4
)
Andrea Arcuri
,
Birmingham B
Conference:
International Symposium on Search Based Software Engineering  SSBSE
, 2009
Theoretical Analysis of Local Search in Software Testing
(
Citations: 1
)
Andrea Arcuri
Conference:
Stochastic Algorithms  SAGA
, pp. 156168, 2009