AUSTIN: An open source tool for search based software testing of C programs
Introduction
Search-Based Software Testing (SBST) was the first Software Engineering problem to be attacked using optimization [2] and also the first to which a search-based optimization technique was applied [3]. Recent years have witnessed a dramatic rise in the growth of work on SBST and in particular on techniques for generating test data that meets structural coverage criteria. Yet, despite an increasing interest in SBST and, in particular, in structural coverage using SBST, there remains a lack of publicly available tools that provide researchers with facilities to perform search-based structural testing.
This paper introduces such a tool, AUSTIN, and reports our experience with it. AUSTIN supports three search algorithms: A random search, a hill climber, and a hill climb algorithm augmented with symbolic execution. The hill climb algorithms are a variant of Korel’s ‘Alternating Variable Method’ (AVM) [4].
AUSTIN can handle a large subset of C, though there are some limitations. Most notably AUSTIN cannot generate meaningful inputs for strings, void and function pointers, as well as union constructs. Despite these limitations, AUSTIN has been applied ‘out of the box’ to real industrial code from the automotive industry [1] as well as a number of open source programs [5].
This paper presents an evaluation of the different search algorithms implemented within AUSTIN on functions taken from open source programs as well as data structure implementations. Then, the hill climb algorithms in AUSTIN are compared to a closed source, state-of-the-art Evolutionary Testing Framework (ETF). The ETF was developed as part of the EvoTest project [6] and has itself been applied to case studies from the automotive and communications industry.
For the comparison we chose three case studies from the automotive industry, provided by Berner & Mattner Systemtechnik GmbH. They form the benchmark against which AUSTIN was compared for effectiveness and efficiency when generating branch adequate test data. Automotive code was chosen as the benchmark because the automotive industry is subject to testing standards that mandate structural coverage criteria [7] and so the developers of production code for automotive systems are a natural target for automated test data generation techniques, such as those provided by AUSTIN.
The rest of the paper is organised as follows: Section 2 provides background information on the field of search-based testing and gives an overview of related work. Section 3 introduces AUSTIN and describes the different test data generation techniques it implements. These techniques are evaluated in Section 4. Section 5 then presents an empirical study that compares AUSTIN’s hill climber against the ETF and discusses any threats to validity. Section 6 concludes.
Section snippets
Background
Test data generation is a natural choice for Search-Based Software Engineering (SBSE) researchers because the search space is clearly defined (it is the space of inputs to the program) and tools often provide existing infrastructures for representing candidate inputs and for instrumenting and recording their effect. Similarly, the test adequacy criterion is usually well defined and is also widely accepted as a metric worthy of study by the testing community, making it an excellent candidate for
AUSTIN
AUgmented Search-based TestINg (AUSTIN) is a structural test data generation tool for unit testing C programs. AUSTIN considers a unit to be a function under test and all the functions reachable from within that function. It supports three test data generation techniques: A random search, a hill climber (AVM) and a hill climber augmented with symbolic execution (AVM+).
AUSTIN can be used to generate a set of input data for a given function which achieve (some level of) branch coverage for that
Comparing AVM and AVM+
The aim of this section is to investigate what difference the constraint solver in the AVM+ makes in practice, compared to constructing random memory graphs in the AVM. We therefore compared the three search algorithms in AUSTIN, the random search, AVM and AVM+, on a mix of open source programs. Table 1 summarizes the programs and functions tested. The random search was simply used as a sanity check.
The experiments were performed on 628 branches, drawn from two different C programs
Comparing AUSTIN against state-of-the-art
The objective of this section is to investigate the effectiveness and efficiency of AUSTIN’s hill climbers compared to a state-of-the art Evolutionary Testing Framework (ETF). The ETF was developed as part of the multidisciplinary European Union-funded research project EvoTest [6] (IST-33472), applying evolutionary algorithms to the problem of testing software systems. It supports both black-box and white-box testing and represents the state-of-the-art for automated evolutionary structural
Conclusion
This paper has introduced and evaluated the open source, search-based testing tool named AUSTIN. It supports a random search, a hill climber in the form of the Alternating Variable Method, and a hill climber augmented with symbolic execution to handle constraints over pointer inputs to a function. Test data is generated by AUSTIN to achieve branch coverage for C functions.
We first evaluated a decision procedure for dealing with pointer inputs, introduced in this paper, on a set of functions
Acknowledgments
We would like to thank Bill Langdon for his helpful comments and Arthur Baars for his advice on the Evolutionary Testing Framework. Zhang kindly provided the two figures on growth trends in publications on SBST used in this paper. Kiran Lakhotia is funded through the European Union Project FITTEST (ICT-2009.1.2 no 257574). Mark Harman is supported by EPSRC Grants EP/G060525/1, EP/D050863, GR/S93684 & GR/T22872 and also by the kind support of Daimler Berlin, BMS and Vizuri Ltd., London.
References (35)
- et al.
Observations in using parallel and sequential evolutionary algorithms for automatic software testing
Computers & Operations Research
(2008) - et al.
A Tabu search algorithm for structural software testing
Computers & Operations Research
(2008) - et al.
Evolutionary test environment for automatic structural testing
Information and Software Technology
(2001) - K. Lakhotia, M. Harman, H. Gross, Austin: a tool for search based software testing for the C language and its...
- et al.
Automatic generation of floating-point test data
IEEE Transactions on Software Engineering
(1976) - S. Xanthakis, C. Ellis, C. Skourlas, A. Le Gall, S. Katsikas, K. Karapoulios, Application of genetic algorithms to...
Automated software test data generation
IEEE Transactions on Software Engineering
(1990)- K. Lakhotia, P. McMinn, M. Harman, Automated test data generation for coverage: haven’t we solved this problem yet? in:...
- H. Gross, P.M. Kruse, J. Wegener, T. Vos, Evolutionary white-box software test with the evotest framework: a progress...
- Radio Technical Commission for Aeronautics, RTCA DO178-B software considerations in airborne systems and equipment...