AUSTIN: An open source tool for search based software testing of C programs

https://doi.org/10.1016/j.infsof.2012.03.009Get rights and content

Abstract

Context

Despite the large number of publications on Search-Based Software Testing (SBST), there remain few publicly available tools. This paper introduces AUSTIN, a publicly available open source SBST tool for the C language.1 The paper is an extension of previous work [1]. It includes a new hill climb algorithm implemented in AUSTIN and an investigation into the effectiveness and efficiency of different pointer handling techniques implemented by AUSTIN’s test data generation algorithms.

Objective

To evaluate the different search algorithms implemented within AUSTIN on open source systems with respect to effectiveness and efficiency in achieving branch coverage. Further, to compare AUSTIN against a non-publicly available, state-of-the-art Evolutionary Testing Framework (ETF).

Method

First, we use example functions from open source benchmarks as well as common data structure implementations to check if the decision procedure for pointer inputs, introduced in this paper, differs in terms of effectiveness and efficiency compared to a simpler alternative that generates random memory graphs. A second empirical study formulates two alternate hypotheses regarding the effectiveness and efficiency of AUSTIN compared to the ETF. These hypotheses are tested using a paired Wilcoxon test.

Results and Conclusion

The first study highlights some practical problems with the decision procedure for pointer inputs described in this paper. In particular, if the code under test contains insufficient guard statements to enforce constraints over pointers, then using a constraint solver for pointer inputs may be suboptimal compared to a method that generates random memory graphs. The programs used in the second study do not require any constraint solving for pointer inputs and consist of eight non-trivial, real-world C functions drawn from three embedded automotive software modules. For these functions, AUSTIN is competitive compared to the ETF, achieving an equal or higher branch coverage for six of the functions. In addition, for functions where AUSTIN’s branch coverage is equal or higher, AUSTIN is more efficient than the ETF.

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)

  • E. Alba et al.

    Observations in using parallel and sequential evolutionary algorithms for automatic software testing

    Computers & Operations Research

    (2008)
  • E. Díaz et al.

    A Tabu search algorithm for structural software testing

    Computers & Operations Research

    (2008)
  • J. Wegener 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...
  • W. Miller 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...
  • B. Korel

    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...
  • M. Harman et al.

    Metrics are fitness functions too

  • P. McMinn

    Search-based software test data generation: a survey

    Software Testing, Verification and Reliability

    (2004)
  • E. Alba et al.

    Software testing with evolutionary strategies

  • R. Sagarna et al.

    Estimation of distribution algorithms for testing object oriented software

  • R. Blanco et al.

    A scatter search approach for automated branch coverage in software testing

    International Journal of Engineering Intelligent Systems (EIS)

    (2007)
  • R. Sagarna, An optimization approach for software test data generation: applications of estimation of distribution...
  • R. Lefticaru et al.

    Functional search-based testing from state machines

  • Cited by (0)

    View full text