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

Theoretical Runtime Analyses of Search Algorithms on the Test Data Generation for the Triangle Classification Problem   (Citations: 7)
BibTex | RIS | RefWorks Download
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.
    • ...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 Arcuriet 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 Arcuriet al. Theoretical Runtime Analysis in Search Based Software Engineering

Sort by: