University of Hull logo

Using program data-state scarcity to guide automatic test data generation

Alshraideh, Mohammad; Bottaci, Leonardo; Mahafzah, Basel A.

Authors

Mohammad Alshraideh

Dr Leonardo Bottaci L.Bottaci@hull.ac.uk
Senior Lecturer and Programme Leader for Computer Science Software Engineering and Software Development

Basel A. Mahafzah

Abstract

Finding test data to cover structural test coverage criteria such as branch coverage is largely a manual and hence expensive activity. A potential low cost alternative is to generate the required test data automatically. Search-based test data generation is one approach that has attracted recent interest. This approach is based on the definition of an evaluation or cost function that is able to discriminate between candidate test cases with respect to achieving a given test goal. The cost function is implemented by appropriate instrumentation of the program under test. The candidate test is then executed on the instrumented program. This provides an evaluation of the candidate test in terms of the "distance'' between the computation achieved by the candidate test and the computation required to achieve the test goal. Providing the cost function is able to discriminate reliably between candidate tests that are close or far from covering the test goal and the goal is feasible, a search process is able to converge to a solution, i.e., a test case that satisfies the coverage goal. For some programs, however, an informative cost function is difficult to define. The operations performed by these programs are such that the cost function returns a constant value for a very wide range of inputs. A typical example of this problem arises in the instrumentation of branch predicates that depend on the value of a Boolean-valued (flag) variable although the problem is not limited to programs that contain flag variables. Although methods are known for overcoming the problems of flag variables in particular cases, the more general problem of a near constant cost function has not been tackled. This paper presents a new heuristic for directing the search when the cost function at a test goal is not able to differentiate between candidate test inputs. The heuristic directs the search toward test cases that produce rare or scarce data states. Scarce inputs for the cost function are more likely to produce new cost values. The proposed method is evaluated empirically for a number of example programs for which existing methods are inadequate.

Journal Article Type Article
Publication Date 2010-02
Journal SOFTWARE QUALITY JOURNAL
Print ISSN 0963-9314
Electronic ISSN 1573-1367
Publisher Springer Verlag
Peer Reviewed Peer Reviewed
Volume 18
Issue 1
Pages 109-144
Institution Citation Alshraideh, M., Bottaci, L., & Mahafzah, B. A. (2010). Using program data-state scarcity to guide automatic test data generation. Software quality journal, 18(1), 109-144. doi:10.1007/s11219-009-9083-x
DOI https://doi.org/10.1007/s11219-009-9083-x
Keywords Software; Safety, Risk, Reliability and Quality

You might also like


Downloadable Citations