InfoTestSS: Information theory and Test Suite Selection

Lead Research Organisation: University College London
Department Name: Computer Science

Abstract

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.

Planned Impact

Software increasingly underpins our contemporary world. This trend will continue for the foreseeable future. Software relies on testing to ensure that it behaves as required. Testing is perhaps less science than art and there are a number of known, persistent problems in software testing. The proposed research will address four classic problems in selecting a suitable set of test inputs; will show how solutions to these can improve two state-of-the-art approaches to selection; then will produce a prototype tool that automates the solutions. Furthermore, the research plans to do this by modelling the four classic problems using information theory, producing an underpinning theory that has the potential to develop into a general theory of software testing.

short-term impact
- Develop human capital by deepening and extending the understanding of software testing of the researchers and collaborators directly collaborating in the project, both from academia and industry.
- Within the academic software testing community, increase the understanding of software testing and the knowledge of novel techniques to solve problems within this domain; build a new research community in applications of information theory to software testing and to software engineering more generally; provide new lines of research and new research problems for both the QIF and the software testing communities.
- Improve the UK and European quality of life through cheaper, better quality software. This will, particularly and more immediately, benefit the sectors represented by our industrial partners, namely the banking and automotive sectors.
- Add to the number of options in choosing tools for automating testing.

medium-term impact
- Reduce software cost and improve time to market for all forms of software development.
- Improve the sophistication of software testing and the level of skill and knowledge of its practitioners.
- Lay foundations for an information theory based, coherent theory of software testing; make connections to a more general theory of software engineering based on the theory of information.
- Expand the connections between software testing and formal methods via information theory.
- Create a new venue for discussion, publication and dissemination of ideas about these topics.

long-term impact
- Contribute to providing laws, predictions, and an integrated theory for software testing in particular and software engineering in general.
- Improve society's confidence in software affecting many aspects of life.
 
Description Have developed an open source tool that enables programmers to test assertion oracles embedded in code to improve testing. Have developed a highly novel open source tool that uses output diversity to select test sets and has better error finding capabilities than conventional coverage or input diversity approaches. Have developed a tool that covers a selected point in a program with an input diverse set of tests. This latter is mostly a research tool but could be useful in regression testing as part of a continuous development cycle. Have developed a program transformation that is semantically invariant and when used with a feedback directed mutational fuzzer measurably improves the diversity of the generated tests and improves bug finding.
Exploitation Route Programmers in Java and C can download and use these tools to assist them in testing their programs. The new program transformation is not easily packaged into a tool but we are researching ways to automate it.
Sectors Aerospace, Defence and Marine,Agriculture, Food and Drink,Chemicals,Communities and Social Services/Policy,Construction,Creative Economy,Digital/Communication/Information Technologies (including Software),Education,Electronics,Energy,Environment,Financial Services, and Management Consultancy,Healthcare,Leisure Activities, including Sports, Recreation and Tourism,Government, Democracy and Justice,Manufacturing, including Industrial Biotechology,Culture, Heritage, Museums and Collections,Pharmace

 
Description ELVEN: Entropy Loss Via ExecutioN
Amount $100,000 (USD)
Organisation Facebook 
Sector Private
Country United States
Start  
 
Description Collaboration with Fondazione Bruno Keller, Trento, Italy 
Organisation Fondazione Bruno Kessler
Country Italy 
Sector Private 
PI Contribution I have co-authored a paper with Professor Paolo Tonella and we jointly supervise a PhD student. The student is supported by the grant funding from FBK.
Collaborator Contribution FBK have supplied the funding for a PhD student, Gunel Jahangirova, whom Professor Tonella and I jointly supervise. We have collaborated extensively, producing one paper so far.
Impact Gunel Jahangirova, David Clark, Mark Harman, Paolo Tonella: Test oracle assessment and improvement. ISSTA 2016: 247-258.
Start Year 2015
 
Title DFT: Diversified Focused Testing 
Description DFT supports focused testing, that is, it generates a set of test inputs sampled uniformly that cover a selected point in the software. 
Type Of Technology Software 
Year Produced 2019 
Open Source License? Yes  
Impact none as yet 
URL https://github.com/hdg7/DFT
 
Title OaSiS 
Description This software allows a programmer to improve assertions placed in the code via tests for false negatives and false positives with respect to the intended behaviour of the program. The result of the testing process is that the placed assertion will be sound and complete with respect to the software's intended behaviour. 
Type Of Technology Software 
Year Produced 2018 
Impact This has been used by other researchers in attempts to eliminate the necessity for a human in the loop and so to fully automate the method 
URL https://github.com/guneljahan/OASIs
 
Title OutGen: A white box method of automated test set generation using output diversity 
Description This is an automated test set generator for C language functions. It embodies a novel principle, namely optimising the channel capacity of the testing channel, allowing discovery of inputs that exercise rarer software behaviours 
Type Of Technology Software 
Year Produced 2019 
Open Source License? Yes  
Impact None as yet 
URL https://github.com/hdg7/OutGen
 
Description TAROT Summer School 2018 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact Summer School on research in software testing held at UCL. Organised by the InfoTestSS team at UCL and Brunel. David Clark presented a talk on InfoTestSS research. Took place over five days an involved many international experts.
Year(s) Of Engagement Activity 2018
URL https://wp.cs.ucl.ac.uk/tarot2018/
 
Description Talk at Leicester Computer Science Department External Seminar series, 7 December 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Regional
Primary Audience Professional Practitioners
Results and Impact Talk on information theory and testing.
Year(s) Of Engagement Activity 2018
URL https://www2.le.ac.uk/departments/informatics/news/researchevents/external/external-seminars-201819
 
Description Teaching course in Testing Software: University College MSc in Software Systems Engineering 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact I taught a five week course to MSc students and final year undergraduates. In the course of this I discussed results from InfoTestSS
Year(s) Of Engagement Activity 2021
URL https://rl.talis.com/3/ucl/lists/CE9E51CA-5518-8200-4888-81B08F02C216.html?lang=en-gb
 
Description The 57th CREST Open Workshop - Information Theory and Software Testing 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact This was a workshop designed to introduce the Information Theory for Test Set Selection project to academics and industry. Almost 50 people attended with 40 people formally registered. The audience was drawn from different countries with the majority of the participants being from the UK.
Year(s) Of Engagement Activity 2018
URL http://crest.cs.ucl.ac.uk/cow/57/
 
Description Workshop on Statistics, Learning, Genetic Improvement and Testing for Programs 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact The 61st CREST Open Workshop - Statistics, Learning, Genetic Improvement and Testing for Programs.

Date: 21st and 22nd October 2019

Venue: Friends House, 173-177 Euston Road, London, NW1 2BJ

Overview:

Software testing is expanding, growing, and finding new connections and uses like some strange mutant changeling. This workshop aims to reflect and celebrate this. To this end we want to attract software engineering researchers with interest and expertise in some of the following areas: applications of statistics to problems in SE, applications of machine learning to problems in SE, Genetic Improvement of Programs and, last but not least, Software Testing. We are interested in both the intersections and the unions of these areas and hope to find new research synergies beyond those that exist already. Examples of illustrative developments in this union from within CREST include Software Transplantation, novel approaches to testing machine learning systems, information theoretic models of failed error propagation and oracle improvement in software testing, the use of deep neural nets to create and reconfigure search landscapes in testing, the use of search in adversarial machine learning, and the use of testing in the application of GI to a long list of types of software improvement. To grow and deepen these connections, this workshop will present a list of talks in the union (and sometimes the intersections) of these areas.
Year(s) Of Engagement Activity 2019
URL http://crest.cs.ucl.ac.uk/cow/61/