Search-Based Software Engineering, Combinatorial Interaction Testing and Genetic Improvement
Lecturer:
Justyna Petke
(University College London).
About the lecturer | Course Summary | Slides: 1 2 3 | Assignment
About the lecturer:
Justyna Petke has a DPhil in Computer Science from University of Oxford. She is now at the Centre for Research on Evolution, Search and Testing (CREST) in University College London. Her interests include the connections between constraint satisfaction and search-based software engineering. Her work on constraints in combinatorial interaction testing won the best presentation award at the Search-Based Software Testing Workshop 2015, while her work on genetic improvement was awarded a Silver Humie (awarded for human-competitive results produced by genetic and evolutionary computation) and an ACM SIGSOFT Distinguished Paper Award at the International Symposium on Software Testing and Analysis 2015. Among her research activities are organisation of the Genetic Improvement Workshop 2015 and the Doctoral Program at the International Conference on Principles and Practice of Constraint Programming 2014. She is the guest editor for the Special Issue on Genetic Improvement of the Genetic Programming and Evolvable Machines journal. She has also served as a reviewer for a number of international conferences and workshops.
Course summary: This course will cover three areas of software engineering. No previous knowledge of the three areas is assumed.
Software engineering problems can often be reformulated as search problems. One seeks to find an optimal or near optimal solution in a wide range of candidate solutions, guided by a fitness function that distinguishes between good and bad solutions. Areas of software engineering that benefit from search-based problem formulation include: software testing, requirements engineering, refactoring, project planning, and many others. Example questions that a software engineer might ask are:
- What is the smallest number of test cases that will cover all the statements in my program?
- What is the set of requirements that will balance software development cost and customer satisfaction?
- What is the best sequence of refactoring steps to be applied to this system?
- What is the best way of allocating resources in this software project?
Subsequently the course's focus will shift to Combinatorial Interaction Testing (CIT), a relatively mature area of software testing, that benefited from SBSE techniques. CIT is a black-box testing method that has been extensively used in testing highly configurable software. In practice it's usually infeasible to test all possible parameter combinations of such systems. Empirical studies have shown that CIT provides a way of reducing the test suite size whilst still maintaining high fault detection rates [2]. SBSE techniques have been successfully applied to the CIT test suite generation problem which will be presented in detail during the course.
Another exciting area of research that will be covered is Genetic Improvement (GI). This is a new field of SBSE research. Genetic improvement uses computational search to improve existing software with respect to a user-defined objective function, while retaining some existing behaviour captured by testing. Work on genetic improvement has already resulted in several awards. This includes work on automatic bug fixing [3]. GI has been used, for instance, to automate the process of software specialisation, optimise program efficiency, and to minimise memory and energy consumption. More recently, GI has been applied in the award-winning work on automated software transplantation [4]. This course will give an overview of the genetic improvement area and present key components of a GI framework.
References:
[1] Mark Harman, Phil McMinn, Jerffeson Teixeira de Souza and Shin Yoo; 'Search Based Software Engineering: Techniques, Taxonomy, Tutorial'; LASER Summer School on Software Engineering, 2010.[2] Justyna Petke, Myra B. Cohen, Mark Harman and Shin Yoo; 'Practical Combinatorial Interaction Testing: Empirical Findings on Efficiency and Early Fault Detection'; IEEE Transactions on Software Engineering, 2015.
[3] Stephanie Forrest, ThanhVu Nguyen, Westley Weimer and Claire Le Goues; 'A Genetic Programming Approach to Automated Software Repair'; Genetic and Evolutionary Computation Conference (GECCO), 2009. Gold 'Humie' Winner.
[4] Earl T. Barr, Mark Harman, Yue Jia, Alexandru Marginean, Justyna Petke; 'Automated software transplantation'; International Symposium on Software Testing and Analysis (ISSTA), 2015. ACM SIGSOFT Distinguished Paper Award Winner. Slides:
Assignment: You can find the problem set here. Please send the solutions to the address provided on the problem sheet by Friday, January 15.