Crash-avoid Program Repair

汇报内容

文章概述

这篇论文《Crash-Avoiding Program Repair》提出了一种集成的方法，用于检测和过滤可能导致程序崩溃的补丁。传统的程序修复工具可能生成通过现有测试但仍然存在崩溃风险的补丁。这篇文章的创新点在于将测试生成和补丁生成融合到一个过程中，利用模糊测试（fuzzing）策略来优先生成能够区分补丁行为的新测试用例。

主要贡献

  1. 集成测试与修复：

    • 将测试生成和补丁生成融合到一个过程中，通过生成新的测试用例来区分补丁的行为，从而减少补丁过拟合的风险。

  2. 补丁分区与分离性：

    • 定义了“补丁分区”（patch partitions），通过价值等价测试（value-based test equivalence）将补丁分组。
    • 提出了“分离性”（separability）的概念，用于衡量测试用例区分补丁行为的能力。

  3. 工具实现与评估：

    • 实现了一个名为 Fix2Fit 的工具，并在来自 Google 的 OSS-Fuzz 基础设施中的真实世界漏洞和开源项目上进行了评估。
    • 结果表明，Fix2Fit 能够生成避免崩溃的补丁，并且在减少补丁候选空间方面效果显著。

关键技术点

  1. 补丁分区：

    • 通过价值等价测试将补丁分组，形成补丁分区，从而减少需要单独考虑的补丁对数量。

  2. 分离性：

    • 用于衡量测试用例区分补丁行为的能力，帮助生成更有区分性的测试用例。

  3. 模糊测试策略：

    • 优先生成那些能够区分补丁行为的新测试用例，从而减少补丁过拟合的风险。

  4. 断言过滤：

    • 利用编译时插入的断言（sanitizers）来进一步过滤掉可能引入安全漏洞的补丁，增加方法的可靠性。

实验与评估

  1. 实验设置：

    • 使用来自 Google 的 OSS-Fuzz 基础设施中的真实世界漏洞和开源项目进行评估。
    • 比较了 Fix2Fit 与 AFL 和 AFLGo 的效果。

  2. 实验结果：

    • Fix2Fit 在减少补丁候选空间和生成避免崩溃的补丁方面表现优异。
    • 通过交叉验证，证明了生成的补丁在未见过的测试用例上具有较高的 crash-free 性。

威胁到有效性

  1. 单行修复：

    • 当前实验主要针对单行修复，未来可能需要扩展到多行修复的情况。

  2. 工具比较：

    • 由于工具实现的差异，无法直接与其他 Java 程序修复工具进行比较。

结论

这篇文章提供了一个新颖的集成测试和修复的方法，有效地减少了生成补丁的过拟合问题，并且通过实验证明了其有效性。未来可以进一步探索多行修复的情况，并考虑更广泛的工具比较。

2. 技术方案概述

文章的核心思想是将测试生成和补丁生成融合到一个过程中，通过模糊测试（fuzzing）策略来生成能够区分补丁行为的新测试用例。具体来说，技术方案包括以下几个关键步骤：

  1. 补丁生成：
    • 生成一组候选补丁（plausible patches），这些补丁能够通过现有的测试用例。
    • 补丁的生成基于预定义的变换规则，例如修改赋值语句、条件语句或添加条件保护。
  2. 补丁分区（Patch Partitioning）：
    • 通过价值等价测试（value-based test equivalence）将补丁分组，形成补丁分区。
    • 补丁分区的定义是：如果两个补丁在所有现有测试用例上的行为相同（即它们的表达式在运行时生成相同的值），则它们属于同一个分区。
  3. 测试生成与补丁区分：
    • 生成新的测试用例，目标是区分不同补丁的行为。
    • 通过模糊测试（fuzzing）策略，优先生成那些能够细化补丁分区的测试用例，即能够将现有分区进一步拆分为更小的分区。
    • 这种测试生成策略被称为补丁感知的模糊测试（patch-aware fuzzing）。
  4. 补丁过滤：
    • 使用新生成的测试用例来过滤掉那些会导致程序崩溃的补丁。
    • 通过运行补丁程序并检查是否崩溃，逐步缩小补丁候选空间。
  5. 断言（Sanitizers）作为验证工具：
    • 使用编译时插入的断言（如 AddressSanitizer 和 UndefinedBehaviorSanitizer）来检测内存错误和未定义行为。
    • 这些断言可以帮助进一步过滤掉可能导致安全漏洞的补丁。

3. 关键技术细节

3.1 补丁分区与价值等价测试

  • 补丁分区：将补丁分组，使得同一分区内的补丁在所有现有测试用例上的行为相同。
  • 价值等价测试：通过动态分析，比较补丁表达式在运行时的值，判断两个补丁是否等价。

3.2 补丁感知的模糊测试

  • 模糊测试策略：
    • 使用 AFLGo（一种定向模糊测试工具）作为基础，结合补丁感知的测试生成策略。
    • 模糊测试的目标是生成能够区分补丁行为的测试用例，而不是仅仅提高代码覆盖率。
  • 分离性（Separability）：
    • 定义了一个新的指标，称为“分离性”，用于衡量一个测试用例区分补丁行为的能力。
    • 分离性越高，测试用例越能细化补丁分区。
  • 能量分配（Energy Assignment）：
    • 在模糊测试中，为每个测试用例分配“能量”，决定对其进行多少次变异。
    • 分离性高的测试用例会被分配更多能量，从而生成更多能够区分补丁行为的测试用例。

3.3 断言（Sanitizers）的使用

  • AddressSanitizer (ASan)：用于检测内存错误，如缓冲区溢出、使用已释放的内存等。
  • UndefinedBehaviorSanitizer (UBSan)：用于检测未定义行为，如空指针解引用、整数溢出等。
  • 这些断言工具将潜在的安全漏洞转换为程序崩溃，从而帮助过滤掉不安全的补丁。

1. 定义补丁搜索空间

  • Fix2Fit首先定义了一个补丁搜索空间，这个空间包含了所有可能的补丁候选。这些补丁候选是通过对程序中的表达式进行修改生成的。Fix2Fit支持的补丁生成操作包括：
    • 修改赋值语句：例如，将 x = e 修改为 x = e'，其中 e 和 e' 是不同的表达式。
    • 修改条件语句：例如，将 if (e) 修改为 if (e')。
    • 添加条件保护：例如，在某个语句前添加一个条件判断 if (e)，以确保该语句只在特定条件下执行。

这些操作是基于预定义的转换模式，Fix2Fit通过这些模式生成大量的候选补丁。

2. 生成候选补丁

  • Fix2Fit通过生成与验证（Generate and Validate）的方法生成候选补丁。具体来说：
    • 生成：根据预定义的转换模式，生成所有可能的补丁候选。
    • 验证：使用现有的测试用例（包括通过测试和失败测试）来验证这些补丁候选。只有那些能够通过所有测试的补丁才会被保留，这些补丁被称为合理补丁（Plausible Patches）。

3. 补丁分区

  • 为了减少搜索空间，Fix2Fit将生成的合理补丁根据它们在现有测试用例上的行为进行分区。具体来说：
    • 测试等价性：如果两个补丁在所有现有测试用例上的行为完全相同（即它们的输出相同），那么它们属于同一个补丁分区。
    • 值等价性：Fix2Fit使用基于值的测试等价性来判断两个补丁是否等价。如果两个补丁在某个测试用例上的表达式值相同，那么它们在该测试用例上是等价的。

通过这种方式，Fix2Fit将补丁划分为多个分区，每个分区中的补丁在现有测试用例上的行为是相同的。

4. 动态生成补丁

  • 为了高效地生成和验证补丁，Fix2Fit在运行时动态生成补丁。具体来说：
    • 元程序生成：Fix2Fit会生成一个元程序，该元程序在运行时能够动态替换程序中的表达式，从而模拟不同的补丁行为。
    • 运行时补丁枚举：在程序运行时，Fix2Fit会枚举所有可能的补丁，并通过动态替换表达式来模拟这些补丁的行为。这样，Fix2Fit可以在一次运行中生成并验证多个补丁。

5. 补丁过滤

  • 在生成补丁后，Fix2Fit会通过模糊测试和sanitizers来过滤掉那些会导致程序崩溃或引入安全漏洞的补丁。具体来说：
    • 模糊测试：Fix2Fit生成新的测试用例，这些测试用例能够触发程序的不同行为，从而帮助区分不同的补丁。
    • Sanitizers：通过使用如AddressSanitizer（ASan）和UndefinedBehaviorSanitizer（UBSan）等工具，Fix2Fit可以检测并过滤掉那些会导致内存错误或未定义行为的补丁。

6. 补丁分区细化

  • 随着新的测试用例的生成，Fix2Fit会进一步细化补丁分区。具体来说：
    • 分区细化：如果一个新的测试用例能够区分同一个分区中的两个补丁（即它们在该测试用例上的行为不同），那么Fix2Fit会将这个分区细化为多个子分区。
    • 补丁过滤：如果某个补丁在新的测试用例上导致程序崩溃，那么它会被过滤掉。

7. 输出最终补丁

  • 经过多次测试生成和补丁过滤后，Fix2Fit会输出那些通过了所有测试且没有引入崩溃或漏洞的补丁。这些补丁被认为是崩溃避免补丁（Crash-Avoiding Patches）。