State based models raise the level of abstraction at which systems are described from the program source code level to a more design-oriented level. The goal of this raised abstraction level is to allow larger-scale systems to be developed and managed with the same level of effort as smaller systems expressed at lower levels of abstraction. Many embedded systems, such as those developed by the SLIM project's industrial partners, are constructed from state based models. Unfortunately, as the scale of what can be handled increases, there is an inevitable commensurate increase in expectations and the demands placed upon the model. It is human nature to push systems and approaches to the bounds of what can be withstood. As an example of this size problem , one of the models for describing a phone system, currently used by the SLIM industrial project partner Motorola, runs to nearly 700 pages.The SLIM project will develop algorithms, methods and techniques for scaling down the size and complexity of a model using a techniques called slicing. Traditionally, slicing has only been applied to program source code, not to state based models. The SLIM project will reformulate slicing so that it can be used to scale down models, thereby addressing the model size problem. The research challenge is to develop new theories, methods and algorithms for program slicing to raise it to the state-based level of abstraction.

This proposal seeks relatively modest funding to provide partial financial support for the first international Symposium on Search Based Software Engineering (SBSE).This symposium will found a series of annual international events. EPSRC funding is sought to support the first of these, to be held in the UK. The UK has outstanding international leadership in this area of research. The PI for the project, Mark Harman, has extensive experience in successful management of similar events and has a long track record of publications and collaborations on SBSE with both industry and academia.

Software testing is an important part of the software development process but typically is manual, expensive, and error prone. This has led to significant interest in automated test generation (and execution) algorithms, with these having the potential to lead to cheaper, higher-quality software. Despite the interest in automating parts of testing, there are still significant challenges, with auto-testing being mentioned as an EPSRC priority within Software Engineering. This project will build on initial work by the PIs that has demonstrated that an important aspect of testing can be represented in terms of Quantified Information Flow. Specifically, the PIs previously looked at Failed Error Propagation (FEP), which is sometimes called coincidental correctness. In FEP, a test execution goes through a faulty part of the software, this leads to what would be regarded as a corrupted program state (i.e. the fault has an effect) but ultimately the output is correct. Although studies have shown that FEP can significantly reduce test effectiveness, there is a lack of practical techniques that address FEP. The observation made by the PIs is that FEP corresponds to a failure for information to flow from the fault in the software to output: information is lost through different values for the program state (correct and faulty values) being mapped to the same output. The PIs have shown how FEP can be represented in terms of an information theoretic notion: Quantified Information Flow (QIF). The results of experiments were highly promising, with there being a rank correlation of over 0.95 between the frequency with which FEP was observed in software and a QIF-based metric. This remarkably strong result opens up the possibility of devising techniques that generate test cases that are less likely to suffer from FEP. In addition, we believe that it is possible to represent other important testing concepts using information theory, specifically: the 'feasibility' of a path (we do not want test automation to waste effort in trying to trigger infeasible paths), the diversity of a test suite (evidence suggests that diverse test suites are effective), and also the effectiveness of probes/oracles added to the code. This project will develop new methods, based on information theory, for reasoning about the above factors (FEP, feasibility, diversity, and oracles). In doing so it will develop information theoretic measures that can help test automation to overcome the associated issues. It will also develop methods for estimating these measures, integrate these estimates into automated test generation, and evaluate the results on open source software and software provided by our industrial partners. The outcome will be a new theory for software testing, based on information theory, and a set of techniques that use this theory to make software testing more efficient and effective.

State based models raise the level of abstraction at which systems are described from the program source code level to a more design-oriented level. The goal of this raised abstraction level is to allow larger-scale systems to be developed and managed with the same level of effort as smaller systems expressed at lower levels of abstraction. Many embedded systems, such as those developed by the SLIM project's industrial partners, are constructed from state based models. Unfortunately, as the scale of what can be handled increases, there is an inevitable commensurate increase in expectations and the demands placed upon the model. It is human nature to push systems and approaches to the bounds of what can be withstood. As an example of this size problem , one of the models for describing a phone system, currently used by the SLIM industrial project partner Motorola, runs to nearly 700 pages.The SLIM project will develop algorithms, methods and techniques for scaling down the size and complexity of a model using a techniques called slicing. Traditionally, slicing has only been applied to program source code, not to state based models. The SLIM project will reformulate slicing so that it can be used to scale down models, thereby addressing the model size problem. The research challenge is to develop new theories, methods and algorithms for program slicing to raise it to the state-based level of abstraction.

Testing involves examining the behaviour of a system in order to discover potential faults. The problem of determining the desired correct behaviour for a given input is called the Oracle Problem. Since manual testing is expensive and time consuming there has been a great deal of work on automation and part automation of Software Testing. Unfortunately, it is often impossible to fully automate the process of determining whether the system behaves correctly. This must be performed by a human, and the cost of the effort expended is referred to as the Human Oracle Cost.RE-COST will develop Search-Based Optimisation techniques to attack the Human Oracle Cost problem quantitatively and qualitatively. The quantitative approach will develop methods and algorithms to both reduce the number of test cases and the evaluation effort per test case. The qualitative approach will develop methods and algorithms that will reduce test case cognition time.The RE-COST project seeks to transform the way that researchers and practitioners think about the problem of Software Test Data Generation. This has the potential to provide a breakthrough in Software Testing, dramatically increasing real world industrial uptake of automated techniques for Software Test Data Generation.