InfoTestSS: Information theory and Test Suite Selection

软件测试是软件开发过程的重要组成部分，但通常是手动的，昂贵的，并且容易出错。这引起了人们对自动测试生成（和执行）算法的极大兴趣，这些算法有可能导致更便宜，更高质量的软件。尽管对自动化测试的部分感兴趣，但仍然存在重大挑战，自动化测试被认为是EPSRC在软件工程中的优先事项。该项目将建立在PI的初步工作的基础上，这些工作已经证明了测试的一个重要方面可以用量化信息流来表示。具体来说，PI以前会查看失败的错误传播（FEP），有时称为巧合正确性。在FEP中，测试执行通过软件的错误部分，这会导致被视为损坏的程序状态（即错误有影响），但最终输出是正确的。虽然研究表明，FEP可以显着降低测试的有效性，但缺乏解决FEP的实用技术。PI的观察结果是FEP对应于信息从软件中的故障流向输出的失败：信息通过将程序状态的不同值（正确值和错误值）映射到相同的输出而丢失。PI已经展示了FEP如何根据信息理论概念表示：量化信息流（QIF）。实验结果非常有希望，在软件中观察到的FEP频率与基于QIF的度量之间的秩相关性超过0.95。这个非常强的结果为设计出生成不太可能遭受FEP的测试用例的技术提供了可能性。此外，我们相信，有可能使用信息论来表示其他重要的测试概念，特别是：一条路的“可行性”（我们不希望测试自动化在尝试触发不可行路径方面浪费精力），测试套件的多样性（证据表明，不同的测试套件是有效的），以及添加到代码中的探针/预言机的有效性。该项目将开发新的方法，基于信息论，用于对上述因素（FEP、可行性、多样性和神谕）进行推理。在这样做的过程中，它将开发信息理论的措施，可以帮助测试自动化，以克服相关的问题。它还将开发评估这些措施的方法，将这些评估整合到自动化测试生成中，并评估开源软件和我们的工业合作伙伴提供的软件的结果。其结果将是一个新的软件测试理论，基于信息论，和一套技术，使用这个理论，使软件测试更有效。

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.