Материал: + An Orchestrated Survey on Automated Software TestCase Generation

IPlease cite this paper as follows: Saswat Anand et al., 20xx, An Orchestrated Survey on Automated Software Test Case Generation, Antonia Bertolino, J. Jenny Li and Hong Zhu (Editor/Orchestrators), Journal of Systems and Software x(y), xxCyy

1See, for example, the Proceedings of IEEE/ACM Workshops on Automation of Software Test (AST’06 – AST’12). URL for AST’13: http: //tech.brookes.ac.uk/AST2013/

niques for test case generation start gradually to be adopted by the IT industry in software testing practice, there still exists a big gap between real software application systems and practical usability of test case generation techniques proposed by research. We believe that for researchers in software test automation it is highly desirable to critically review the existing techniques, recognizing the open problems and putting forward a perspective on the future of test case generation.

Towards such aim, this paper o ers a critical review covering a number of prominent test case generation techniques and does so by taking a novel approach that we call an orchestrated survey. This consists of a collaborative work collecting selfstanding sections, each focusing on a key surveyed topic, in our case a test generation technique, and independently authored by world-renowned active researcher(s) of the topic. The surveyed topics have been selected (and orchestrated) by the editors.

Generally speaking, test cases, as an important software artifact, must be generated from some information, that is some other types of software artifacts. The types of artifacts that have been used as the reference input to the generation of test cases not exhaustively include: the program structure and/or source code; the software specifications and/or design models; information about the input/output data space, and information dynamically obtained from program execution. Thus, the techniques we consider in this paper include:

1. symbolic execution and program structural coverage testing;

2. model-based test case generation;

3. combinatorial testing;Accepted 4. adaptive random testing as a variant of random testing;

5. search-based testing.

Of course, automatic test case generation techniques may exploit more than one type of software artifacts as the input, thus combining the above techniques to achieve better e ectiveness and e ciency. It is worth noting that there are many other automatic or semi-automatic test case generation techniques not covered in this paper, for example, mutation testing, fuzzing and data mutation testing, specification-based testing, metamorphic testing, etc. For keeping this paper within reasonable size, we limited our selection to five most prominent approaches; future endeavors could be devoted to complement this set with further reviews: orchestrated surveys can in fact be easily augmented with more sections.

Hence, after a brief report in the next section about the process that we followed in conducting the survey, the paper is organized as follows. In Section 3, Saswat Anand and Mary Jean Harrold review typical program-based test case generation techniques using symbolic execution. In Section 4, Wolfgang Grieskamp focuses on model-based test case generation, which is closely related to the currently active research area of modeldriven software development methodology. Sections 5 and 6 focus on data-centric test case generation techniques, i.e., combinatorial testing reviewed by Myra B. Cohen, and random test and its variant of adaptive random testing reviewed by Tsong Yueh Chen, respectively. Finally, in Section 7, Mark Harman,

2

Phil McMinn, John Clark, and Edmund Burke review searchbased approaches to test case generation.

2. About the Process of Orchestrated Survey

The idea behind this ”orchestrated” survey, as we call it, originatedManuscriptfrom the desire of producing a comprehensive survey paper on automatic test generation within the short timeframe of

this special section devoted to the Automation of Software Test (AST). There are already several outstanding textbooks and survey papers on software testing. However, the field of software testing is today so vast and specialized that no single author could yield the expertise of all di erent approaches and could be informed of the latest advances in every technique. So, typically surveys are necessarily focusing on some specific kind of approach. We wanted a review that could somehow stand out from the existing literature by o ering a broad and up-to-date coverage of techniques, yet without renouncing to depth and authoritativeness in dealing with each addressed technique. Thus we came out with this idea of selecting a set of techniques and invited renowned experts of each technique to contribute with an independent section.

For each of the included section, the review consists of a brief description of the basic ideas underlying the technique, a survey of the current state of art in the research and practical use of the technique, a discussion of the remaining problems for further research, and a perspective of the future development in the approach. While these reviews are assembled together to form a coherent paper, each section remains an independently readable and referable article.

For those authors who accepted our invitation, the submitted sections have not been automatically accepted. Each section underwent a separate peer-review process by at least two (often three) reviewers, following the same standards of this journal reviewing process, and some of them were subject to extensive revision and a second review round before being accepted. The five finally accepted sections were then edited in their format and collated by us into this survey paper, which we proudly o er as an authoritative source both to get a quick introduction to research in automatic test case generation and as a starting point for researchers willing to pursue some further direction.

3. Test Data Generation by Symbolic Execution

By Saswat Anand and Mary Jean Harrold 2

2Acknowledgements: This research was supported in part by NSF CCF0541049, CCF-0725202, and CCF-1116210, and IBM Software Quality Innovation Award to Georgia Tech.

Symbolic execution is a program analysis technique that analyzes a program’s code to automatically generate test data for the program. A large body of work exists that demonstrates the technique’s usefulness in a wide range of software engineering problems, including test data generation. However, the technique su ers from at least three fundamental problems that limit its e ectiveness on real world software. This section provides a brief introduction to symbolic execution, a description of the three fundamental problems, and a summary of existing well known techniques that address those problems.

3.1. Introduction to Symbolic Execution

In contrast to black box test data generation approaches, which generate test data for a program without considering the program itself, white box approaches analyze a program’s source or binary code to generate test data. One such white box approach, which has received much attention from researchers in recent years, uses a program analysis technique called symbolic execution. Symbolic execution (King, 1975) uses symbolic values, instead of concrete values, as program inputs, and represents the values of program variables as symbolic expressions of those inputs. At any point during symbolic execution, the state of a symbolically executed program includes the symbolic values of program variables at that point, a path constraint on the symbolic values to reach that point, and a program counter. The path constraint (PC) is a boolean formula over the symbolic inputs, which is an accumulation of the constraints that the inputs must satisfy for an execution to follow that path. At each branch point during symbolic execution, the PC is updated with constraints on the inputs such that (1) if the PC becomes unsatisfiable, the corresponding program path is infeasible, and symbolic execution does not continue further along that path and (2) if the PC is satisfiable, any solution of the PC is a program input that executes the corresponding path. The program counter identifies the next statement to be executed.

(b)

Figure 1: (a) Code that swaps two integers, (b) the corresponding symbolic execution tree, and (c) test data and path constraints corresponding to di erent program paths.

3

To illustrate, consider the code fragment3 in Figure 1(a) that swaps the values of integer variables x and y, when the initial value of x is greater than the initial value of y; we reference statements in the figure by their line numbers. Figure 1(b) shows the symbolic execution tree for the code fragment. A symbolic execution tree is a compact representation of the execution paths followed during the symbolic execution of a program. In the tree, nodes represent program states, and edges

represent transitions between states. The numbers shown at the upperManuscriptright corners of nodes represent values of program counters. Before execution of statement 1, the PC is initialized to

true because statement 1 is executed for any program input, and x and y are given symbolic values X and Y, respectively. The PC is updated appropriately after execution of if statements 1 and 5. The table in Figure 1(c) shows the PC’s and their solutions (if they exist) that correspond to three program paths through the code fragment. For example, the PC of path (1,2,3,4,5,8) is X > Y&Y X <= 0. Thus, a program input that causes the program to take that path is obtained by solving the PC. One such program input is X = 2, Y = 1. For another example, the PC of path (1,2,3,4,5,6) is an unsatisfiable constraint X > Y&Y X > 0, which means that there is no program input for which the program will take that (infeasible) path.

Although the symbolic execution technique was first proposed in the mid seventies, the technique has received much attention recently from researchers for two reasons. First, the application of symbolic execution on large, real world programs requires solving complex and large constraints. During the last decade, many powerful constraint solvers (e.g., Z3 (de Moura and Bjørner, 2008), Yices (Dutertre and de Moura, 2006), STP (Ganesh and Dill, 2007)) have been developed. Use of those constraint solvers has enabled the application of symbolic execution to a larger and a wider range of programs. Second, symbolic execution is computationally more expensive than other program analyses. The limited computational capability of older generation computers made it impossible to symbolically execute large programs. However, today’s commodity computers are arguably more powerful than the supercomputers (e.g., Cray) of the eighties. Thus, today, the barrier to applying symbolic execution to large, real world programs is significantly lower than it was a decade ago. However, the e ectiveness of symbolic execution on real world programs is still limited because the technique su ers from three fundamental problems—path explosion, path divergence, and complex constraints—as described in Section 3.2. Those three problems need to be addressed before the technique can be useful in real world software development and testing.

Although symbolic execution has been used to generate test data for many di erent goals, the most well known use of this approach is to generate test data to improve code coverage and expose software bugs (e.g., (Cadar et al., 2008; Godefroid et al., 2008b; Khurshid et al., 2003)). Other uses of this approach include privacy preserving error reporting (e.g., (Castro et al., 2008)), automatic generation of security exploits (e.g., (Brum-

3This example, which we use to illustrate symbolic execution, is taken from Reference (Khurshid et al., 2003).

ley et al., 2008)), load testing (e.g., (Zhang et al., 2011)), fault localization (e.g., (Qi et al., 2009)), regression testing (e.g., (Santelices et al., 2008)), robustness testing (e.g., (Majumdar and Saha, 2009)), data anonymization for testing of database-based applications (e.g., (Grechanik et al., 2010)), and testing of graphical user interfaces (e.g., (Ganov et al., 2008)),

For example, Castro, Costa and Martin (2008) use symbolic execution to generate test data that can reproduce, at the developer’s site, a software failure that occurs at a user’s site, without compromising the privacy of the user. Zhang, Elbaum and Dwyer (2011) generate test data that leads to a significant increase in program’s response time and resource usage. Qi et al. (2009) generate test data that are similar to a given program input that causes the software to fail, but that do not cause failure. Such newly generated test data are then used to localize the cause of the failure. Santelices et al. (2008) generate test data that exposes di erence in program’s behaviors between two versions of an evolving software. Majumdar and Saha (2009) use symbolic execution to generate test data whose slight perturbation causes a significant di erence in a program’s

bolic Pathfinder (Pasareanu and Rungta, 2010), JCUTE (Sen and Agha, 2006), JFuzz (Jayaraman et al., 2009), and LCT (Kahk¨onen¨ et al., 2011). CUTE (Sen et al., 2005), Klee (Cadar et al., 2008), S2E (Chipounov et al., 2011),

and Crest4 target C language. Finally, Pex (Tillmann and de Halleux, 2008) is a symbolicAcceptedexecution tool for .NET lan-

guages. Some tools that are not currently publicly available, but have been shown to be e ective on real world programs include SAGE (Godefroid et al., 2008b) and Cinger (Anand and Harrold, 2011).

3.2. Fundamental Open Problems

A symbolic execution system can be e ectively applied to large, real world programs if it has at least the two features:

(1) e ciency and (2) automation. First, in most applications of symbolic execution based test data generation (e.g., to improve code coverage or expose bugs), ideally, the goal is to discover all feasible program paths. For example, to expose bugs e ectively, it is necessary to discover a large subset of all feasible paths, and show that either each of those paths is bug free or many of them expose bugs. Thus, the system must be able discover as many distinct feasible program paths as possible in the available time limit. Second, the required manual e ort for applying symbolic execution to any program should be acceptable to the user.

To build a symbolic execution system that is both e cient and automatic, three fundamental problems of the technique must be addressed. Other problems5 arise in specific applica-

tions of symbolic execution, but they are not fundamental to the technique. Although a rich body of prior research6 on symbolic execution exists, these three problems have been only partially addressed.

Path explosion. It is di cult to symbolically execute a significantly large subset of all program paths because (1) most real world software have an extremely large number of paths, and (2) symbolic execution of each program path can incur high

computational overhead. Thus, in reasonable time, only a small subsetManuscriptof all paths can be symbolically executed. The goal of discovering a large number of feasible program paths is further

jeopardized because the typical ratio of the number of infeasible paths to the number of feasible paths is high (Ngo and Tan, 2007). This problem needs to be addressed for e ciency of a symbolic execution system.

Path divergence. Real world programs frequently use multiple programming languages or parts of them may be available only in binary form. Computing precise constraints for those programs either requires an overwhelming amount of e ort in implementing and engineering a large and complex infrastructure or models for the problematic parts provided by the user. The inability to compute precise path constraints leads to path divergence: the path that the program takes for the generated test data diverges from the path for which test data is generated. Because of the path divergence problem, a symbolic execution system either may fail to discover a significant number of feasible program paths or, if the user is required to provide models, will be less automated.

Complex constraints. It may not always be possible to solve path constraints because solving the general class of constraints is undecidable. Thus, it is possible that the computed path constraints become too complex (e.g., constraints involving nonlinear operations such as multiplication and division and mathematical functions such as sin and log), and thus, cannot be solved using available constraint solvers. The inability to solve path constraints reduces the number of distinct feasible paths a symbolic execution system can discover.

3.3. Existing Solutions

Although the three problems described in the previous section have not been fully solved, many techniques have been proposed to partially address them. In the following, we briefly describe some of those techniques.

3.3.1. Techniques for Path Explosion Problem

Many techniques have been proposed to alleviate the path explosion problem, and they can be classified into five broad classes. Techniques in the first class avoid exploring paths through certain parts of a program by using a specification of how those parts a ect symbolic execution. Some techniques (Anand et al., 2008; Godefroid, 2007) automatically

4Burnim and Sen, CREST: Auomatic test generation tool for C, URL: http://code.google.com/p/crest/

5For example, when symbolic execution is applied to open programs (i.e., parts of the program are missing), a problem arises in maintaining symbolic values corresponding to reference type variables that store abstract data types.

6A partial bibliography of papers published in the last decade on symbolic execution and its applications can be found at http://sites.google. com/site/symexbib/; Cadar et al. (2011) and Pasareanu and Visser (2009) provide an overview of prior research on symbolic execution.

4