Testing is a difficult and costly activity in the development of object-oriented programs. The challenge is to come up with a sufficient set of test scenarios, out of the typically huge volume of possible test cases, to demonstrate correct behavior and acceptable quality of the software. This can be reformulated as a search problem to be solved by sophisticated heuristic search techniques such as evolutionary algorithms. The goal is to find an optimal set of test cases to achieve a given test coverage criterion. This chapter introduces and evaluates genetic programming as a heuristic search algorithm which is suitable to evolve object-oriented test programs automatically to achieve high coverage of a class. It outlines why the object paradigm is different to the procedural paradigm with respect to testing, and why a genetic programming approach might be better suited than the genetic algorithms typically used for testing procedural code. The evaluation of our implementation of a genetic programming approach, augmented with program analysis techniques for better performance, indicates that object-oriented software testing with genetic programming is feasible in principle. However, having many adjustable parameters, evolutionary search heuristics have to be fined-tuned to the optimization problem at hand for optimal performance, and, therefore, represent a difficult optimization problem in their own right.
TopIntroduction
Testing is the most widely used and accepted technique for verification and validation of software systems. It is applied to measure to which extent a software system is conforming to its original requirements specification and to demonstrate its correct operation (IEEE, 1999). Testing is a search problem that involves the identification of a limited number of good tests out of a shear, nearly unlimited number of possible test scenarios. “Good tests” are those runtime scenarios that are likely to uncover failures, or demonstrate correctness of the system under test (SUT). Identifying good test cases typically follows predefined testing criteria, such as code coverage criteria (Beizer, 1990). This is based on the assumption that only the execution of a distinct feature, or its coverage, can reveal failures that are associated with this feature.
Because the primary activities of testing, test case identification and design, are typical search problems, they can be tackled by typical search heuristics. One of the most important search heuristics for software testing is known to be random testing. This is also one of the most commonly used testing strategies in industry today. Currently, also more advanced heuristic search techniques are applied to software testing. These are based on evolutionary algorithms, and they have also made their ways into industry (Baresel, 2003; Buehler & Wegener, 2003) since their performance in devising test cases was found to be at least as good as random testing, but usually much better (Gross, 2003; Tracey, Clarke & Mander, 1998). The group of these testing techniques is referred to as evolutionary testing (ET) according to Wegener and Grochtmann (1998).
ET is an automatic test case generation technique based on the application of evolution strategies (Schwefel & Männer, 1990), genetic algorithms (Goldberg, 1989; Holland, 1975), genetic programming (Koza, 1992), or simulated annealing (von Laarhoven & Aarts, 1987). ET searches for optimal test parameter combinations that satisfy a predefined test criterion. This test criterion is represented through a “cost function” that measures how well each of the automatically generated optimization parameters satisfies the given test criterion. For a test, various test criteria a perceivable, according to the goal of the test, such as how well a test case covers a piece of code, in the case of structural testing (Jones et al., 1996; Pargas et al, 1999), or how well a test case violates a (safety) requirement (Tracey et al, 1999), for example.
Evolutionary testing has initially only been applied to traditional procedural software. Here, ET is used to generate input parameter combinations for test cases automatically that achieve, i.e., high coverage, if the test target relates to some code coverage criterion. However, also object-oriented software testing with genetic algorithms has been tackled by researchers, e.g., Gross and Mayer (2002, 2003), Tonella (2004), and applying genetic programming approaches, e.g., Seesing and Gross (2006), Ribeiro, Zenha-Rela and de Vega (2008), and Gupta and Rohil (2008).