InfoTestSS: Information theory and Test Suite Selection

Lead Research Organisation: Brunel University
Department Name: Computer Science


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.


10 25 50
publication icon
Patel K (2019) A partial oracle for uniformity statistics in Software Quality Journal

publication icon
Menéndez HD (2019) Mimicking Anti-Viruses with Machine Learning and Entropy Profiles. in Entropy (Basel, Switzerland)

publication icon
Clark D (2019) Normalised Squeeziness and Failed Error Propagation in Information Processing Letters

publication icon
Ibias A (2019) Using Squeeziness to test component-based systems defined as Finite State Machines in Information and Software Technology

Related Projects

Project Reference Relationship Related To Start End Award Value
EP/P006116/1 01/01/2017 01/09/2018 £440,393
EP/P006116/2 Transfer EP/P006116/1 02/09/2018 29/06/2021 £294,170
Description Please see the Key Findings of EPSRC Grant EP/P005888/1
Exploitation Route Please see the Key Findings of EPSRC Grant EP/P005888/1
Sectors Aerospace, Defence and Marine,Digital/Communication/Information Technologies (including Software),Financial Services, and Management Consultancy,Transport

Description Please see the Impact summary of EPSRC Grant EP/P005888/1