Automatic, Evolutionary Test Data Generation for Dynamic Software Testing

Abstract:

This paper proposes a dynamic test data generation framework based on genetic algorithms. The framework houses a Program Analyser and a Test Case Generator, which intercommunicate to automatically generate test cases. The Program Analyser extracts statements and variables, isolates code paths and creates control ﬂow graphs. The Test Case Generator utilises two optimisation algorithms, the Batch-Optimistic (BO) and the Close-Up (CU), and produces a near to optimum set of test cases with respect to the edge/condition coverage criterion. The eﬃcacy of the proposed approach is assessed on a number of programs and the empirical results indicate that its performance is signiﬁcantly better compared to existing dynamic test data generation methods. . 2008 Elsevier Inc. All rights reserved.

Introduction:

Computers and programs have been expanded in many sections of our life, such as in electronic transactions, media, transportation, medication and health. Software and hardware reliability are very important issues since various aspects of our everyday working activities, or even our own lives, depend on it. Software testing is a way for verifying the correctness and appropriateness of a software system, or, alternatively, for ensuring that a program meets its speciﬁcations (Bertolino, 2007; Kaner and Falk, 1999). While software testing is very signiﬁcant, it is also very expensive as it should take place throughout the software cycle. The time and eﬀort usually spent on software testing may be greater than the overall system implementation cost.

During the last decade automatic software testing has been investigated in greater detail, aiming at providing faster and cheaper testing, eliminating the need for increased human resources, oﬀering more eﬃcient and accurate testing without requiring special skills or knowledge, freeing the testing activities from cognitive bias and producing less process errors during testing. This work focuses on automatic structural (white-box) testing, and more speciﬁcally on test data generation, and proposes a dynamic test data generation framework. The framework comprises a program analyser and a test case generation system; the former parses source code, creates control ﬂow graph representations, extracts paths and variables, and evaluates automatically and visually the coverage achieved by the test cases on control ﬂow graphs. The test case generation system accommodates two algorithms that use the features of the program analyser to generate a near to optimum set of test cases in relation to control ﬂow coverage criteria. The ﬁrst algorithm evolves sets of test cases, whereas the second algorithm targets speciﬁcs paths to exercise uncovered statements and conditions.

The major contributions of this paper are two. The ﬁrst is that it proposes a complete solution for automatic software testing, which not only it generates test cases but it integrates program analysis features, such as code coverage, CFG creation and test case evaluation with code coverage and visual interaction. The second contribution is the novel test case generation approach, a fusion of a batch-optimistic algorithm and a close-up algorithm, which outperforms similar approaches in terms of testing quality coverage rate. The higher testing quality is partly justiﬁed by the fact that the framework produces test cases to provide edge/decision coverage. The latter, although it oﬀers better testing coverage than edge, statement and condition coverage, has not been used widely so far in the literature mostly due to its complexity. On the other hand, the high testing coverage rate of the proposed testing approach demonstrated through experiments, which, additionally, prove its superiority when compared to other approaches, even if most of them use lower in hierarchy coverage criteria.

The rest of the paper is organized as follows: Section 2 presents a short taxonomy of structural software test data generation, and discusses and compares related work. Section 3 describes the proposed testing framework. Section 4 evaluates the eﬃcacy of our testing approach and provides experimental results on a number of sample programs, as well as some commonly known programs that are used as benchmarks for comparison purposes. Finally, Section 5 concludes the paper and suggests future research steps.

Conclusions and Future Work:

This paper presented a complete framework for dynamically generating test cases. The framework integrates a basic program analyser (BPAS) and a test generation system (ATCGS). BPAS is capable of analysing JAVA programs, creating control ﬂow graphs, determining code covered by test cases and visualising the results on the control ﬂow graphs. On the other hand, ATCGS retrieves program data by utilising BPAS, searches the input space and determines a near to optimum set of test cases with respect to the edge/decision criterion. ATCGS comprises the Batch Optimistic (BO) and the Close-Up (CU) algorithms. The former, utilises a specially designed genetic algorithm to evolve sets of test cases with the aid of the complete control ﬂow graph. Each gene encodes a test case, such as the values of input parameters and the exercised statements, and each chromosome encodes a set of test cases. The CU algorithm, which runs after the BO algorithm, focuses on speciﬁc paths in order to ﬁnd test cases for the unreachable elements. Given an unreachable element, the CU runs on each path containing the element separately using control ﬂow graph transformation.

The major contributions of this work are the complete test case generation framework and the novel testing approach, which, according to the empirical results, outperforms similar approaches. First, the framework can generate test data for the edge/condition decision criterion, which is higher in the testing hierarchy than edge, statement and condition used by similar approaches. Second, the framework combines many-to-many test cases generation (batch-optimistic) and one-to-one path oriented test cases generation (close-up). The former enables fast extraction of most or all of the test cases, whereas the latter focuses on targets and paths for overcoming obstacles, such as the ﬁtness landscape caused by the path problem, and generating test cases for the hard-to-test parts of the code. Third, the framework illustrates its ability to generate test cases achieving higher coverage when compared to similar approaches with standard and randomly generated programs.

The paper describes four sets of experiments carried out to evaluate the framework. The ﬁrst set involved a number of sample programs written in Java varying in terms of complexity and size, for which test inputs were generated under the edge/condition coverage criterion. The results showed that our algorithms achieved remarkably high percentage coverage, even for large programs of 1000–2000 lines of code, with many nested-IFs and more than two predicates in decision nodes. The second set of experiments utilised ﬁve widely known programs as benchmarks and compared our algorithms with other alternative test data generation methods, such as the random, gradient descent, standard genetic and diﬀerential genetic (diﬀGA) (Michael et al., 2001) algorithms. The comparison suggested the superiority of the proposed scheme over the rest of the algorithms and indicated its ability to overcome known limitations related to the type of conditions present in the code. Our arguments were further enhanced by the third category of experiments, which, using the triangle classiﬁ- cation case, attempted to analyse the behaviour of the pproposed algorithms in comparison with that of the diﬀGA approach by focusing on those ‘‘diﬃcult” conditions that may lower coverage success and showing how these are handled by our approach. Finally, the last category compared the random, gradient descent, standard genetic and our algorithms using the three most complex sample programs reported in the ﬁrst set of experiments. This comparison was also in favour of the proposed testing approach.

Commenting on the length of the programs our proposition is able to handle, we should note here that the program analyser runs on a unit basis, i.e. creates a control ﬂow graph for each method of the program under testing. This allows the test case generation system to test arbitrarily large programs by isolating smaller, independent parts (units) and applying the testing process described previously. Essentially, the framework initiates a new testing process for each unit (method) of the program under testing, i.e. a new control ﬂow graph and a new required set of test cases for each method. As a result, in unit testing, the complexity for testing a program of n methods is practically equal to that of testing n programs, each comprising only one method; this is why test case generation systems assess testing eﬃciency in relation to the maximum LOC of the method(s) involved and not to the whole program. To demonstrate the eﬃciency of our framework, we reported programs that included methods of up to 2000 lines of code (LOC), far beyond the limit posed by industrial standards so as to preserve the ease of understanding and promote future maintenance. Extending this concept, the framework may be easily applied on software applications of any size as regards number of code statements, with only one additional step, that of identifying and isolating the application’s independent units.

Another part of this work that is worthy of discussing is the limitations faced by BPAS (Basic Program Analysis System) in dealing with some characteristics of the object oriented approach. While BPAS is able to identify every object oriented (O–O) feature including class-based features, such as inheritance and static initialisation within the class, the control ﬂow graph, due to its nature, can depict only method-based features, such as calls to other methods, control ﬂow in a method and declaration, local initialisation and usage of variables (e.g. objects, arrays, primitive types) within the method, etc. This control ﬂow graph limitation, i.e. the inability to describe class-based features, enables the use of the control ﬂow graph only for representing methods’ details, whereas method calls may be shown as links to other, independent control ﬂow graphs. Likewise, the code coverage system, which runs on the control ﬂow graph, is limited on what is captured by the control ﬂow graph, i.e. method-based features. Nevertheless, the test case generator is not bounded to the structure of programs since it only uses the code coverage results to adapt its behaviour. Thus, by modifying and extending the notions of the classic control ﬂow graph with O–O features, the proposed framework will be able to perform test case generation by considering complete classes as units. Currently we are working on modelling these class-based features, i.e. inheritance and global initialisations, in a multilayer Object Oriented Control Flow Graph (OOCFG); the OOCFG will combine features from the conventional control ﬂow graph and UML and will be able to represent diﬀerent methods called in a layered structure, where control will ﬂow from the calling layer to the called and back. Further to this, runtime object oriented features, such as polymorphism and dynamic (late) binding, cannot be depicted on static code representations, such as the control ﬂow graph, as the correct method is called at runtime. Again, using the multilayer object oriented graph, we will be able to show the non-runtime binding on the control ﬂow graph (possible bindings) and determine the actual binding (late binding) during program execution.

The layered architecture and the independency between the various modules of the proposed testing framework provide ample room for future work. In this context we plan to utilize the architecture in two further research steps. The ﬁrst will attempt to generate test data for solving all the equations present on a certain path of the CFG. More speciﬁcally, we intend to traverse each path by creating an associated set of equations either in the form of variables assignment or conditions included in decision points. After a short pre-processing of these equations and substitution of variables (wherever possible) to reduce them in number, a new genetic algorithm will be designed to evolve test data that will satisfy (i.e. solve) each of these equations. The ﬁnal set of test data (optimal) will be deﬁned as the one that will satisfy every equation in the paths extracted via the CFG. The second attempt will focus on dataﬂow coverage. Following a similar approach we will construct the data- ﬂow graph and using the associated criteria (e.g. all_du paths) we will develop a dedicated genetic algorithm to produce automatically test data for satisfying the selected dataﬂow criterion. This will require special forms of ﬁtness functions to reﬂect dataﬂow instead of control ﬂow based evolutions. Both research steps will provide results so that a comparative study with those reported in this paper becomes feasible.