GECCO '19- Proceedings of the Genetic and Evolutionary Computation ConferenceFull Citation in the ACM Digital Library
SESSION: Search-based software engineering
SQL data generation to enhance search-based system testing
Automated system test generation for web/enterprise systems requires either a sequence of actions on a GUI (e.g., clicking on HTML links), or direct HTTP calls when dealing with web services (e.g., REST and SOAP). However, web/enterprise systems do often interact with a database. To obtain higher coverage and find new faults, the state of the databases needs to be taken into account when generating white-box tests. In this work, we present a novel heuristic to enhance search-based software testing of web/enterprise systems, which takes into account the state of the accessed databases. Furthermore, we enable the generation of SQL data directly from the test cases. This is useful for when it is too difficult or time consuming to generate the right sequence of events to put the database in the right state. And it is also useful when dealing with databases that are ''read-only'' for the system under test, and the actual data is generated by other services. We implemented our technique as an extension of EvoMaster, where system tests are generated in the JUnit format. Experiments on five RESTful APIs show that our novel technique improves code coverage significantly (up to +18%).
Footprints of fitness functions in search-based software testing
Testing is technically and economically crucial for ensuring software quality. One of the most challenging testing tasks is to create test suites that will reveal potential defects in software. However, as the size and complexity of software systems increase, the task becomes more labour-intensive and manual test data generation becomes infeasible. To address this issue, researchers have proposed different approaches to automate the process of generating test data using search techniques; an area that is known as Search-Based Software Testing (SBST).
SBST methods require a fitness function to guide the search to promising areas of the solution space. Over the years, a plethora of fitness functions have been proposed. Some methods use control information, others focus on goals. Deciding on what fitness function to use is not easy, as it depends on the software system under test. This work investigates the impact of software features on the effectiveness of different fitness functions. We propose the Mapping the Effectiveness of Test Automation (META) Framework which analyses the footprint of different fitness functions and creates a decision tree that enables the selection of the appropriate function based on software features.
Why train-and-select when you can use them all?: ensemble model for fault localisation
Learn-to-rank techniques have been successfully applied to fault localisation to produce ranking models that place faulty program elements at or near the top. Genetic Programming has been successfully used as a learning mechanism to produce highly effective ranking models for fault localisation. However, the inherent stochastic nature of GP forces its users to learn multiple ranking models and choose the best performing one for the actual use. This train-and-select approach means that the absolute majority of the computational resources that go into the evolution of ranking models are eventually wasted. We introduce Ensemble Model for Fault Localisation (EMF), which is a learn-to-rank fault localisation technique that utilises all trained models to improve the accuracy of localisation even further. EMF ranks program elements using a lightweight, voting-based ensemble of ranking models. We evaluate EMF using 389 real-world faults in Defects4J benchmark. EMF can place 30.1% more faults at the top when compared to the best performing individual model from the train-and-select approach. We also apply Genetic Algorithm (GA) to construct the best performing ensemble. Compared to naively using all ranking models, GA generated ensembles can localise further 9.2% more faults at the top on average.
A hybrid evolutionary system for automatic software repair
This paper presents an automatic software repair system that combines the characteristic components of several typical evolutionary computation based repair approaches into a unified repair framework so as to take advantage of their respective component strengths. We exploit both the redundancy assumption and repair templates to create a search space of candidate repairs. Then we employ a multi-objective evolutionary algorithm with a low-granularity patch representation to explore this search space, in order to find simple patches. In order to further reduce the search space and alleviate patch overfitting we introduce replacement similarity and insertion relevance to select more related statements as promising fix ingredients, and we adopt anti-patterns to customize the available operation types for each likely-buggy statement. We evaluate our system on 224 real bugs from the Defects4J dataset in comparison with the state-of-the-art repair approaches. The evaluation results show that the proposed system can fix 111 out of those 224 bugs in terms of passing all test cases, achieving substantial performance improvements over the state-of-the-art. Additionally, we demonstrate the ability of ARJA-e to fix multi-location bugs that are unlikely to be addressed by most of existing repair approaches.
Resource-based test case generation for RESTful web services
Nowadays, RESTful web services are widely used for building enterprise applications. In this paper, we propose an enhanced search-based method for automated system test generation for RESTful web services. This method exploits domain knowledge on the handling of HTTP resources, and it is integrated in the Many Independent Objectives (MIO) search algorithm. MIO is an evolutionary algorithm specialized for system test case generation with the aim of maximizing code coverage and fault finding. Our approach builds on top of the MIO by implementing a set of effective templates to structure test actions, based on the semantics of HTTP methods, used to manipulate the web services' resources. We propose four novel sampling strategies for the test cases that can use one or more of these test actions. The strategies are further supported with a set of new, specialized mutation operators that take into account the use of these resources in the generated test cases. We implemented our approach as an extension to the EvoMaster tool, and evaluated it on seven open-source RESTful web services. The results of our empirical study show that our novel, resource-based sampling strategies obtain a significant improvement in performance over the baseline MIO (up to +42% coverage).
Improving search-based software testing by constraint-based genetic operators
Search-based software testing (SBST) has achieved great attention as an effective technique to automate test data generation. The testing problem is converted into a search problem, and a meta-heuristic algorithm is used to search for the test data in SBST. Genetic Algorithm (GA) is the most popular meta-heuristic algorithm used in SBST and the genetic operators are the key parts in GA. Much work has been done to improve SBST while little research has concentrated on the genetic operators. Due to the blindness and randomness of classic genetic operators, SBST is ineffective in many cases. In this paper, we focus on improving the genetic operators by constraint-based software testing. Compared with classic genetic operators, our improved genetic operators are more purposeful. For the selection operator, we use symbolic execution technique to help us select the test cases which have more useful heuristic information. Then, the constraint-based crossover operator recombines the test cases which have more probability to create better offspring individuals. Finally, the constraint-based mutation operator is used to improve the test cases in order to satisfy some specific constraints. We applied our constraint-based genetic operators in several benchmarks and the experiments reveal the promising results of our proposal.