Explorative Test Oracle Generation

Testing is a crucial part of any software development process. Testing is also very expensive: Common estimations list the effort of software testing at 50% of the average budget. Our society increasingly depends on a working information infrastructure for more and more aspects of civic, commercial, and social life, while software at the same time becomes ever more complex. For example, a modern car has up to 100 million lines of software code, and software errors can easily lead to fatal consequences. Improving techniques to identify errors in software is therefore of utmost importance.

Manual testing is common practice in software development. As manually testing a program is a laborious and error prone task, automation is desirable. However, automation requires the user to specify the correct behaviour up-front in terms of a specification, or later by adding test oracles to automatically generated tests - both alternatives are difficult. This problem is obliterated as test quality is usually measured with oracle-agnostic code coverage metrics. In truth, however, a test without a good oracle cannot find software bugs. This is the oracle problem, one of the longest standing and greatest remaining challenges in software testing.

As both writing specifications and writing test oracles is difficult and needs to be done manually, this proposal aims to push automation further by exploring the middle ground: The novel concept of an oracle template allows to specify what should be tested and checked, but crucially, it does not require specifying the expected behaviour. Instead, automated test generation instantiates user-specified oracle templates to concrete tests with oracles, and the developer decides case by case about correctness. Thus, programs can be tested without the developer needing to write a specification or having to suffer through seemingly purposeless generated tests. Because test generation is driven by oracles, all tests have a purpose and the essential oracles required to be effective at finding software bugs.

The novel concept of oracle templates requires extension of the current state of the art in test generation, as current techniques either assume the existence of an automated oracle (e.g. a specification) or focus exclusively on the code. This creates three challenges, which will be addressed in this project:

-- Existing code-based testing techniques focus on reaching points in the code. This project will define the concept of oracle templates, and will explore test generation based on oracle templates as a search problem. Given an oracle template, search-based testing techniques will automatically create instances, which are test cases with oracles.

-- Systematic testing is traditionally driven by the idea that a good test set covers all the code, which completely ignores the test oracle problem. This project will define systematic criteria and corresponding search-based test generation techniques to thoroughly test programs based on oracle templates. These criteria will ensure coverage of oracle templates, but will also ensure that the code is executed and checked by oracles (e.g. by applying mutation and data-flow analysis).

-- It is impossible to take the human out of the software testing loop completely. Oracle templates are an attempt at minimizing the human effort, but the task of writing oracle templates still requires manual effort. Therefore, this project will explore strategies to automatically synthesise oracle templates based on standard testing patterns and usage examples. Ultimately, a developer would have all tests and oracles generated automatically on the click of a button, leaving only the task of confirming correctness of the produced examples.

The success in addressing these challenges will be measured using automated experiments, controlled studies with student subjects, and industrial case studies at Google and Microsoft.

This project has major potential impact in software testing research and practice, as it proposes a significant change in how the human is included in the testing process. The impact of this project spans four main areas:

-- Economy

Software testing is one of the major cost factors in software engineering, commonly estimated at around 50% of the average budget. However, missing a software bug can have an even higher economic impact, as regularly demonstrated by bugs resulting in product recalls (e.g. Toyota), system downtimes (e.g. NatWest), or even accidents (e.g. Therac 25, Ariane 5). With increasing software complexity and increasing pervasiveness of software systems, this economic influence is likely to grow even further in the future.

Improving software testing methods therefore promises significant economic impact. Maintaining software quality is also essential to maintain the UK's strong position on the software market: In 2006, the UK software industry had a turnover of more than 50 billion GBP and employed around 430,000. Yet recent trends show that the UK's share of European venture capital investment has been in decline in recent years. Improving software testing, as the EXOGEN project aims to do, is thus also a key factor to a healthy economy in the UK.


-- Society

Software is getting ever more important and pervasive, as our society increasingly depends on a working information infrastructure for more and more aspects of civic, commercial, and social life. However, at the same time software becomes ever more complex, and there is no reason to expect this trend to stop in the near future. Yet, techniques to ensure software quality are struggling to keep up with this pace of growth. Improving such techniques, as is the objective of the EXOGEN project, is therefore of utmost societal importance.


-- Knowledge

This proposal will advance the state of the art in software testing as follows:

1) It will allow a higher degree of test automation than previously possible.

2) It will make it easier to apply automated testing techniques in scenarios where there are no formal specifications.

3) It provides a viable solution to the test oracle problem, one of the longest standing problems in the field of software testing.

4) It will lead to better test cases, as current test automation techniques are often driven by oracle-agnostic coverage metrics that can lead to tests that are not good at finding software bugs.

These advances are of immediate practical value, as automated test generation in practice is almost only applied if there are specifications. These advances will also attract attention of software testing researchers; the research community is currently actively seeking for solutions to the oracle problem, as for example witnessed by the recent gathering of the leading software testing researchers at a CREST Open Workshop at UCL, London, dedicated to the oracle problem.


-- People

The project will have a positive impact on the careers of the PI and RA, who will both gain additional experience in test generation and specification elicitation. In addition, the PI will gain additional experience in empirical software engineering in the context of performing controlled experiments to evaluate the project outcome, and the RA will benefit by improving his knowledge by collaborating on important publications. It will also provide greater exposure for the team members, thereby allowing the PI to consolidate his position as a new lecturer and raise his profile nationally and internationally in software engineering and testing circles. This EPSRC first grant would be the first UK based project and first UK funded project for the PI, thus representing an essential step in the PI's academic career and objective of establishing himself as one of the leading software testing researchers in the UK and worldwide.