2 The Oracle Problem in Software Testing: A Survey

  • 引用：Barr E T, Harman M, McMinn P, et al. The oracle problem in software testing: A survey[J]. IEEE transactions on software engineering, 2014, 41(5): 507-525.
  • CCF A TSE
  • 链接

2.0 摘要

  • 本文提供了对测试预言问题的当前方法的全面调查，以及在这一重要的软件测试研究和实践领域的分析趋势。

  • 在软件测试的许多工作中，我们试图将测试过程尽可能地自动化，以使测试更快、更便宜和更可靠。为此，我们需要一个测试预言，这是一种能够区分被测系统（System under Testing SUT）的正确行为和错误行为的. 然而，目前程序自动化测试预言的问题关注的少

  • 如何利用测试预言（test oracle）来自动化地验证被测系统（SUT）的行为是否符合预期，有以下两种情况

    • 如果SUT的开发遵循了良好的测试设计原则，并且有详细正式的规范描述了预期行为，那么测试预言的成本问题可以通过自动化的测试语言解决，无需人工干预
    • 如果SUT没有完整的规范，但存在部分规范，可以构建一个部分测试预言来回答某些输入的问题。这种部分测试预言可以使用形态测试（metamorphic testing）来构建（基于已知的期望行为之间的关系），或者从执行或文档中推导出神谕信息。

  • 在工业界，普遍没有完整的规范，因此测试人员需要为所有测试用例手动检查系统行为，此时，自动化测试方法必须人工解决oracle成本问题。本文旨在通过提供对测试预言问题的现有文献的全面回顾和分析，帮助应对这一挑战。

  • 我们为解决测试预言问题的四个广泛类别的解决方案绘制了增长趋势，我们在第4、5、6和7节中对这些进行了调查。这四个类别包括：

    • 可以指定测试预言的方法（第4节）；
    • 可以派生测试预言的方法（第5节）；
    • 可以从隐性信息构建测试预言的方法（第6节）；以及
    • 没有可用的自动化预言，但仍然可以减少人类努力的情况（第7节）。
    • 最后，第8节以结束语作为结论。

2.1 重要内容

DERIVED TEST ORACLES 派生测试Oracle

  • 指通过各种工件（如，文档，系统运行）或 北侧系统的属性或其它版本的信息中区分系统的正确与错误行为。

System Executions 系统运行 & Invariant Detection

  • 系统执行跟踪可以用来派生测试oracle,或者通过将不正确的执行与预期执行对齐降低人工测试成本
  • 接下来讨论从系统运行跟踪中的两种技术： 不变量检测和规范挖掘
  • 不变量检测在计算上可能是昂贵的，因此采用了增量[22]、[171]和轻量级静态分析[39]、[63]。一份技术报告总结了各种动态分析技术[157]。模型推断[90]、[187]也可以被视为一种不变量生成的形式，其中不变量被表达为一个模型（通常是一个FSM）。Ratcliff等人使用基于搜索的软件工程(SBSE) [84]来寻找不变量，[153]由突变测试指导。

3 The use of likely invariants as feedback for fuzzers

  • 引用：Fioraldi A, D’Elia D C, Balzarotti D. The use of likely invariants as feedback for fuzzers[C], 30th USENIX Security Symposium (USENIX Security 21). 2021: 2829-2846.
  • CCF A USENIX Security
  • 链接
  • 代码

3.0 摘要&介绍

  • 模糊测试是发现软件错误的很有效的方法，一个主要限制是目前流行的基于覆盖率引导的模糊测试优化了对程序不同部分的访问，担当仅凭可达性不可以触发漏洞时，就会遇到困难。
  • 本文提出一种反馈机制，通过考虑程序变量之间的通常值和关系来增强代码覆盖。谓词，我们在基本块级别学习可能的不变量，并划分程序状态空间。我们的反馈机制可以区分输入何时违反了一个或多个不变量并对其进行建立，从而改进代码覆盖通常提供的程序状态相似。
  • 我们在一个名为INVSCOV的原型上使用了我们的技术，该原型基于LLVM和AFL++基础上进行开发。
  • 我们的实验表明，与使用纯代码覆盖反馈的模糊器相比，我们的方法可以发现更多且不同类型的错误。
  • 本文贡献：
    • 一种新的反馈机制，结合了控制流和从挖掘的不变量中抽象出的程序状态；
    • 基于LLVM和AFL++的我们方法的一个原型实现，名为INVSCOV；
    • 针对经典和上下文敏感的边覆盖率，对我们方法的有效性进行了评估。

3.1 主要内容

  • 我们从一组测试用例语料库开始，就像在实际情况下的真实应用程序一样，这些测试用例不能代表所有的应用状态，然后我们修改fuzzer使其对偏离初始语料库的不变量的行为更加敏感。

  • 我们这么做的直觉是：此时，不变量代表的是执行的属性，而不是程序本身的属性。

  • 设计三类不变量剪枝原则

      1. 舍弃不可能违反的不变量
      1. 舍弃结合了不相关变量的不变量
      1. 当不变量重叠时，舍弃更弱的不变量

3.2 实现

  • 使用LLVM [43]和DAIKON [25]可能不变式系统进行基于不变式的模糊测试。

  • 分为两个阶段

    • 学习阶段：记录进行不变量挖掘所需要的有关程序状态的信息，通过在增强的程序上运行输入来实现。输入可从集中方式获得（我们的实验中从24小时覆盖率引导的模糊测试会话生成的种子）。不变量挖掘使用Daikon，由于我们的技术应用于基本块级别，故不变量计算成本线性依赖于基本块的数量
    • 插桩阶段：随后将可能的不变式信息编码到程序函数中，以将它们暴露给覆盖率引导的模糊器。我们转换后的程序可以在任何基于AFL的模糊器上开箱即用。

  • 状态不变量学习：修改Daikon使用适配LLVM IR（有点工作）

5 Automated patch correctness assessment: How far are we

  • 引用：Wang S, Wen M, Lin B, et al. Automated patch correctness assessment: How far are we?[C], Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering. 2020: 968-980.
  • CCF A ASE
  • 链接

H. Ye, M. Martinez, T. Durieux, and M. Monperrus, “A comprehensive
study of automatic program repair on the quixbugs benchmark,” in Proc.
IEEE 1st Int. Workshop Intell. Bug Fixing, 2019, pp. 1–10

J. Yang, A. Zhikhartsev, Y. Liu, and L. Tan, “Better test cases for better
automated program repair,” inProc. 11th Joint Meeting Found. Softw. Eng.,
2017, pp. 831–841.

Gordon Fraser and Andrea Arcuri. 2011. Evosuite: automatic test suite generationfor object-oriented software. InESEC/FSE. 416–419.

Z. Y. Ding, Y. Lyu, C. Timperley, and C. L. Goues, “Leveraging program
invariants to promote population diversity in search-based automatic program repair

G. Yang, C. S. Pas˘ areanu, and S. Khurshid, “Memoized symbolic ˘
execution,” in Proceedings of the 2012 International Symposium on
Software Testing and Analysis, 2012, pp. 144–154.

D. Schuler, V. Dallmeier, and A. Zeller. EfficientMutation Testing by Checking Invariant Violations. InISSTA ’09, pages 69–80. ACM, 2009

Combined static and dynamic automated test generation

  • 引用：Zhang S, Saff D, Bu Y, et al. Combined static and dynamic automated test generation[C]//Proceedings of the 2011 international symposium on software testing and analysis. 2011: 353-363.
  • CCF A ISSTA
  • 链接

J. Zhang, J. Chen, D. Hao, Y. Xiong, B. Xie, L. Zhang, and H. Mei,
“Search-based inference of polynomial metamorphic relations,” in
Proceedings of the 29th ACM/IEEE International Conference on
Automated Software Engineering, ser. ASE ’14. New York, NY,
USA: Association for Computing Machinery, 2014, p. 701–712.
[Online]. Available: https://doi.org/10.1145/2642937.2642994

动态检测到的不变量还可以帮助删除无意义的测试（违反前提条件）并推断何时失败（违反后置条件）[23]
C. Pacheco, M.D. Ernst, Eclat: Automatic generation and classification of test inputs, ECOOP (2005) 504–527

S. Artzi, M. D. Ernst, A. Kiezun, C. Pacheco, and J. H. Perkins, _
“Finding the needles in the haystack: Generating legal test inputs
for object-oriented programs,” in Proc. 1st Workshop Model-Based
Testing Object-Oriented Syst., Oct. 23, 2006.

From Daikon

例如用于测试选择和优先级排序；更多的覆盖度量指标会产生更好的测试套件[21,22]

M. Harder, J. Mellen, M.D. Ernst, Improving test suites via operational abstraction, ICSE (2003) 60–71.
T. Xie, D. Notkin, Tool-assisted unit test selection based on operational violations, ASE (2003) 40–48.

A Survey on Automatic Test Data Generation 1999 8页

https://faculty.cc.gatech.edu/~harrold/6340/cs6340_fall2009/Readings/test.data.genration.survey.pdf