如何使用程序分析技术缓解漏洞修复的过拟合问题
作者简介
高祥，北京航空航天大学软件学院副教授。研究领域：程序分析、软件自动修复、软件安全。
高效快速地修复软件漏洞是增强软件安全性的关键。然而，据统计，一个漏洞从发现到修复平均需要 60 天，这会让软件系统长期暴露在风险中。自动程序修复是辅助开发人员修复程序缺陷的技术。现有的修复方法通常以通过给定的测试用例作为修复目标。但是，测试用例驱动的修复技术易于产生“过拟合”的补丁，即修复后的程序在给定的测试用例上表现正确，但是在测试用例之外的输入上仍然有错误。我将介绍如何使用程序分析技术缓解漏洞修复的过拟合问题。主要采用测试用例生成和形式化方法来增强程序规约，进而提升自动化生成补丁的质量。
以下为正文。
我们每个月都会发现很多的安全漏洞，然而安全漏洞的修复速度却非常慢。据统计，一个安全漏洞从被发现到被修复，大概要花费 70 天的时间，即便是针对一些特别严重的安全漏洞，也需要花费大概 50 天的时间来修复。
这种缓慢的修复速度会让软件长期暴露在安全的隐患中，我们的工作就是希望能够自动化地生成程序漏洞的补丁，从而帮助开发人员尽快修复程序中缺陷。
对于人工修复来说，程序的修复往往需要定位异常、分析、修复这样的过程。
人工程序修复
对于自动修复来说，我们希望把这个过程自动化。即给定一个程序的正确性规约 specification，以及一个带缺陷的程序，通过程序的自动修复系统来生成正确的程序。
自动化程序修复
# 程序修复方法
## 基于搜索的方法
现有的最简单的程序修复方式之一是基于搜索的方法。
search-based approach
首先定义程序的转换规则，给定一个有错误的程序。利用给定的转换规则，生成候选补丁的搜索空间。给定一组程序的正确性规约（假设是以 test case 的形式给定）。程序修复的目标是使得修复后的程序能够通过所有的 test case。
修复的过程是在搜索空间中通过某种搜索算法找到一个补丁，能够通过所有的 test case。
## 过拟合问题
基于搜索的方法最大的局限在于过拟合 overfitting 问题。
overfitting
给定一组 test case，这组 test case 表示的程序的正确性规约可能是不完善的，修复后的程序可能在给定的 test case 上表现是正确的，但它没有办法泛化到其他的 test case 上。
下面是一个简单的例子，给定一个错误的测试用例，当输入是 1 的时候，期待的返回值是 1，但是在这个程序里面返回值是 0。那么如何用自动化的方式来生成一个正确的补丁？首先按照给定的转换规则，对潜在的有错误的语句做转换，比如 x - 1 > 0 → x - 2 > 0，x - 1 > 0 → x - 1 >= 0 等。
overfitting
通过这种方式生成的程序，可能可以通过给定的 test case，但它不一定能够泛化到其他的 test case 上。
# 如何缓解程序过拟合问题 #
下面介绍如何缓解在修复安全漏洞时的过拟合问题。主要是通过增强程序的正确性规约，并进一步通过程序分析方法来推断开发人员或用户的意图。我们用到的方法包括测试用例生成、基于逻辑推理的方法等。
研究如何缓解程序过拟合问题
今天我会介绍三个近期的工作。
# 生成测试用例
第一个工作是通过生成更多的测试样例来缓解程序的过拟合问题。
既然过拟合的补丁无法泛化到其他的测试用例 test case 上，那么我们是否可以通过自动算法来生成更多的测试用例，再使用修复系统生成修复后的程序呢？
已有的用例生成工具主要以提升程序覆盖率为目的，这类工具并不了解补丁的语义。因此目前的用例生成技术，在我们的场景下其表现效果不是特别好。
test generation to alleviate overfitting
下图中，假设最大的圈表示所有的补丁空间 search space，在补丁空间中有一些 plausible patches，这些 patches 能够通过给定的测试用例，但它们不一定是正确的。在 plausible patches 里，可能只有一小部分是 correct patches。
distinguish crashing and crash-free patches (practical)
我们的主要想法是通过测试用例生成，来区分出 plausible patches 里正确的和不正确的补丁。
在介绍具体的技术之前，我们先补充一下灰盒测试的背景。灰盒模糊测试 grey-box fuzzing 以一组种子 seed (即测试用例) 作为输入，测试引擎会基于给定的种子不断修改来生成新的测试用例，并在程序上运行这些新的测试用例，同时判断新的测试用例是不是 isinteresting 的。在传统的场景下，灰盒测试会判断新测试用例是否提升了代码的覆盖率，如果有提升，就将其加入到 input queue 里，进行进一步的变异。但这种判断方法对于补丁的语义是没有任何理解的。
grey-box fuzzing
为了解决这个问题，我们希望在用例判断的过程中加入补丁的语义信息。例如，生成新测试用例时，先判断测试用例有没有发现候选补丁行为的差异，如果新测试用例发现了补丁之间行为的差异，则把该用例加到 input queue 里进行变异。这样做的最终目标是通过不断发现补丁之间行为的差异，从而区分出哪些补丁是正确的，哪些补丁是错误的。
crash-avoiding program repair
## 举个例子
下面介绍一个缓存溢出和数据泄露的例子。
如下代码示例中，给定一个测试用例 s=foo, t=, n=4，运行会触发缓冲区溢出错误。
// copy the first n characters of s to tchar* strncpy(char* s, char* t, int n) { for (int i=0; i我们假设通过转换规则生成了一系列候选补丁。
id patch
p1 i < n - 1
p2 i < 3
p3 i < n && i n
...... ......
我们将补丁空间划分为 plausible partition 和 incorrect patch (plausible partition 即能够通过给定测试用例的补丁，incorrect patch 指仍然会触发异常的补丁)。其中，plausible partition 又可以划分为 crashing partition 和 crash-free patch (crashing partition 指虽然能够通过给定的测试用例，但在一些其他的测试用例上仍然会触发异常的补丁；crash-free patch 是指正确的补丁)。
为了对 plausible partition 进行进一步的划分，可以通过测试用例生成的方法，对原有的测试用例进行修改和变异。
id patch
p1 i < n - 1
p2 i < 3
p3 i < n && i < strlen(s)
若新生成的测试用例能够发现补丁之间行为的差异，那么就认为基于此测试用例的进一步变异，有更高的概率继续发现补丁之间行为的差异。通过不断生成测试用例，不断划分补丁分区，最终找到正确的补丁。
## 实现方法
下面介绍具体的实现方法。
我们定义了 ，用以表示一个新生成的测试用例是否能够发现补丁之间行为的差异：
separability 有两个作用，一是判断一个新生成的测试用例是否是 isinteresting 的 (即 non-zero separability)，若是，那么就进行进一步的变异。
第二是使用 separability 来定义种子的能量值 energy。能量值 energy 指对一个种子进行变异的次数。假设我们通过变异某个种子生成了 4 个新的测试用例，则其能量值为 4。拥有更高 separability 的种子会被分配更高的能量值。
不同时间和不同 separability 下能量值不同。
## 工具与实验：fix2fit
基于上述方法，我们实现了一个开源工具 fix2fit，并与 afl、aflgo 进行了对比。可以看到，fix2fit 相比 afl 和 aflgo 过滤掉了更多错误的补丁。
percentage of plausible patches that are ruled out
更多 fix2fit 信息：
github 地址：https://github.com/gaoxiang9430/fix2fit
相关论文：crash-avoiding program repair xiang gao, sergey mechtaev, abhik roychoudhury. acm sigsoft international symposium on software testing and analysis (issta) 2019.
## 思考：如何进一步排除补丁
上述方法可以过滤掉 crashing patch，但实际上还有一些没有引发安全隐患 (crash-free patch) 但依然是错误的补丁。怎样去区分这部分补丁 (下图中红色部分) 和正确补丁呢？这需要开发者参与进来。
我们假设通过一个测试用例，发现了两个补丁的差异行为，那么在程序确定的前提下，其中只有一个补丁会是正确的，那么此时我们就需要人的反馈来过滤掉不正确的补丁。需要强调的是，我们的研究工作不是为了取代人，而是为了帮助开发者生成一些推荐，使开发者能够更高效地修复问题。
如下所示，我们的实验中，如果有 5-10 次的人的参与反馈，那么我们可以从众多的 plausible patches 中筛选到 10 个左右。
number of plausible patches that can be ruled out if a few tests are empowered with more human oracles
# 程序状态变异
我们发现，如果从程序的入口处 entry point 开始对程序输入进行变异，会浪费掉大量的资源，要到达 patch location 是一件非常困难的事情。为了解决这个问题，我们提出，是否可以在补丁的位置直接进行变异呢？我们叫这种在 patch location 进行变异的方法为 state-level (snapshot) fuzzing，即对程序的状态进行变异。
snapshot fuzzing for repair
具体的方法是：
第一步，生成一些程序入口处的 test input ，针对每一个程序输入，收集它在 patch location 的程序状态 ；
第二步，根据程序状态 推断程序补丁 ；
第三步，通过 snapshot fuzzing，对程序状态进行修改，生成一个新的状态 ，去测试推断的补丁是否正确，同时也把新的状态加入到状态集合中 ；
返回第二步或者直接结束。
snapshot fuzzing 和传统 test generation 最大的区别在于，snapshot fuzzing 不是从程序的入口处对程序的输入状态进行变异，而是在 patch location 直接变异。这是一个不断循环的过程，最终的目标就是不断生成新的程序状态，同时不断优化程序的补丁。
## 实现方法
patch inference
那么，如何根据生成的程序状态推断一个补丁呢？这里用到了程序合成技术。
在程序状态 s 中，存在正样本和负样本。正样本是指不能触发安全事件的程序状态，负样本是指能够触发安全事件的程序状态。最终的目标是推断出一个程序补丁，使其在正样本上原有的程序执行保持不变，在负样本上，需要对程序的状态进行修改，从而把漏洞状态给关闭掉。
patch generation
生成程序补丁有两种方式。一种是加入到原有的 if/for/while 中，另一种是插入一个 if-guard 关闭错误的程序状态。
## 思考：infeasible states
这里存在一个问题，虽然我们用直接修改的方式在程序中间生成了一个程序状态，但是这个程序状态在真实的场景中不一定存在，即不一定是合法的。
针对这个问题我们也做了分析。如下图所示，通过 snapshot fuzzing 生成的程序状态，可能是 infeasible state，但即使生成了 infeasible state，对于 disable vulnerable state 是没有什么影响的。这主要因为，虚线表示的椭圆有可能也 disable 了一些 infeasible state，但它对于最终的目标是没有任何影响的。
snapshot mutation can generate infeasible states
## 工具与实验：vulnfix
在本个实验中，我们使用了 asiaccs'21 的数据集，其中包含 39 个真实世界的安全漏洞。我们设置了 30 分钟的超时机制。实验结果表明，vulnfix 可以成功修复其中的 19 个 漏洞，在已有的工具基础上有了明显的提升。
vulnfix generated more correct patches than cpr and senx.
# 语义分析与推理
前面介绍的两个工作，主要是基于 fuzzing 的方式来缓解过拟合问题。虽然能够在一定程度上缓解，但仍然没有办法保证生成的补丁能够修复所有错误的 test case。
为了解决这个问题，我们提出了一种 基于语义分析与推理方式修复 的方案。当一个安全漏洞被发现时，通常会有一个能够触发安全漏洞的 exploit (failing test)，如果仅以修复 exploit 作为目标，很容易产生过拟合问题。
除了 exploit 之外，可能还存在很多其他能触发缺陷的程序输入。那么，能否通过一种抽象的方式，将具体的 exploit 抽象成一种针对所有 failing input 的表示？在这个场景下，我们使用抽象的条件约束 constraints 来表示一个缺陷，这样修复的目标就不再是使其通过测试用例，而是使其满足给定的条件约束。
## 实现方法
生成条件约束
我们定义了一些模板，用以生成条件约束。比如，
buffer overflow：access(buffer) < base(buffer) + size(buffer)
integer overflow/underflow (a op b)：min ≤ a op b ≤ max (over z)
下面是一个的 buffer overflow 的例子。假设 rows 声明的长度是 256，访问时的 nrows 也是 256。根据约束 access(buffer) 5。这时候要从第 2 行进行程序的符号执行，发现两条程序执行路径，我们可以计算出第 6 行 cfc -> (y>5) 在第 2 行的最弱前提条件 cfc' -> (x>4 ⋀ i>0) ⋁ (x>6 ⋀ i≤0)。
patch synthesis
最后一步就是需要在 fix location 生成一个补丁。生成补丁之后，cfc' 一定是被满足的。这里其实是一个程序合成的问题，需要合成一个表达式，应用了表达式之后，cfc' 一定是满足的。具体的技术细节不展开了。
## 工具与实验：extractfix
关于实验，我们实现了工具 extractfix。在 30 个现实的 cve 中，我们的工具能够生成 24 个补丁，其中有 16 个和开发人员生成的补丁是一样的。
experiments with existing cves
更多 extractfix 信息：
网站：https://extractfix.github.io/
论文：beyond tests: program vulnerability repair via crash constraint extraction. xiang gao, bo wang, gregory j. duck, ruyi ji, yingfei xiong, abhik roychoudhury. transactions on software engineering and methodology (tosem), 2020.
# 总结 #
总结一下，今天主要介绍了三个缓解安全漏洞修复时过拟合问题的方法。包括 test case generation、snapshot fuzzing、以及语义分析与推理。
还是需要强调一下，由于程序 oracle (期待的程序行为) 的缺失，这些方法并没有彻底地解决过拟合的问题。因此我们只是提出了一些方法去缓解，最终的目标也是帮助开发人员更高效的修复程序缺陷。
以上。
# 相关论文 #
crash-avoiding program repair xiang gao, sergey mechtaev, abhik roychoudhury. acm sigsoft international symposium on software testing and analysis (issta) 2019.
beyond tests: program vulnerability repair via crash constraint extraction. xiang gao, bo wang, gregory j. duck, ruyi ji, yingfei xiong, abhik roychoudhury. transactions on software engineering and methodology (tosem), 2020.
双离合的种类以及优缺点
关于提升射频功率放大器的效率方法介绍
异步电机中的转子条数的定义、影响
变压器差动保护中电流互感器TA及其联接组的若干问题探讨
看到这个，你还把钱放到余额宝吗？你们有人放余额宝没？放多少呢
如何使用程序分析技术缓解漏洞修复的过拟合问题
VR技术与垂直行业的应用结合度将不断提升
你真的需要放弃4G套餐，来个消费升级吗
华为彭中阳发表了“构建数字新范式，共创行业新价值”的主题演讲
华为目前推迟了Mate系列的量产计划？
多屏显示卡
全桥移相ZVS控制器LTC3722-X的工作原理与如何实现自适应延时控制
YD/T 1595.1-2012 2GHz WCDMA标准：用户设备及其辅助设备
中广核岱山4#海上风电项目50台风机基础沉桩正式收官！
在物联网趋势下，安防前端设备技术如何切入到行业应用中
诺基亚拟发力汽车网络连接设备服务市场
新阶段工业互联网平台演进及其数字化技术分析
医学中AI工具和机器学习系统的研究和部署的八项安全伦理原则
随着人工智能技术的入注 安防行业将迎来变革
带热敷功能的无刷无感筋膜枪方案
高祥，北京航空航天大学软件学院副教授。研究领域：程序分析、软件自动修复、软件安全。
高效快速地修复软件漏洞是增强软件安全性的关键。然而，据统计，一个漏洞从发现到修复平均需要 60 天，这会让软件系统长期暴露在风险中。自动程序修复是辅助开发人员修复程序缺陷的技术。现有的修复方法通常以通过给定的测试用例作为修复目标。但是，测试用例驱动的修复技术易于产生“过拟合”的补丁，即修复后的程序在给定的测试用例上表现正确，但是在测试用例之外的输入上仍然有错误。我将介绍如何使用程序分析技术缓解漏洞修复的过拟合问题。主要采用测试用例生成和形式化方法来增强程序规约，进而提升自动化生成补丁的质量。
以下为正文。
我们每个月都会发现很多的安全漏洞，然而安全漏洞的修复速度却非常慢。据统计，一个安全漏洞从被发现到被修复，大概要花费 70 天的时间，即便是针对一些特别严重的安全漏洞，也需要花费大概 50 天的时间来修复。
这种缓慢的修复速度会让软件长期暴露在安全的隐患中，我们的工作就是希望能够自动化地生成程序漏洞的补丁，从而帮助开发人员尽快修复程序中缺陷。
对于人工修复来说，程序的修复往往需要定位异常、分析、修复这样的过程。
人工程序修复
对于自动修复来说，我们希望把这个过程自动化。即给定一个程序的正确性规约 specification，以及一个带缺陷的程序，通过程序的自动修复系统来生成正确的程序。
自动化程序修复
# 程序修复方法
## 基于搜索的方法
现有的最简单的程序修复方式之一是基于搜索的方法。
search-based approach
首先定义程序的转换规则，给定一个有错误的程序。利用给定的转换规则，生成候选补丁的搜索空间。给定一组程序的正确性规约（假设是以 test case 的形式给定）。程序修复的目标是使得修复后的程序能够通过所有的 test case。
修复的过程是在搜索空间中通过某种搜索算法找到一个补丁，能够通过所有的 test case。
## 过拟合问题
基于搜索的方法最大的局限在于过拟合 overfitting 问题。
overfitting
给定一组 test case，这组 test case 表示的程序的正确性规约可能是不完善的，修复后的程序可能在给定的 test case 上表现是正确的，但它没有办法泛化到其他的 test case 上。
下面是一个简单的例子，给定一个错误的测试用例，当输入是 1 的时候，期待的返回值是 1，但是在这个程序里面返回值是 0。那么如何用自动化的方式来生成一个正确的补丁？首先按照给定的转换规则，对潜在的有错误的语句做转换，比如 x - 1 > 0 → x - 2 > 0，x - 1 > 0 → x - 1 >= 0 等。
overfitting
通过这种方式生成的程序，可能可以通过给定的 test case，但它不一定能够泛化到其他的 test case 上。
# 如何缓解程序过拟合问题 #
下面介绍如何缓解在修复安全漏洞时的过拟合问题。主要是通过增强程序的正确性规约，并进一步通过程序分析方法来推断开发人员或用户的意图。我们用到的方法包括测试用例生成、基于逻辑推理的方法等。
研究如何缓解程序过拟合问题
今天我会介绍三个近期的工作。
# 生成测试用例
第一个工作是通过生成更多的测试样例来缓解程序的过拟合问题。
既然过拟合的补丁无法泛化到其他的测试用例 test case 上，那么我们是否可以通过自动算法来生成更多的测试用例，再使用修复系统生成修复后的程序呢？
已有的用例生成工具主要以提升程序覆盖率为目的，这类工具并不了解补丁的语义。因此目前的用例生成技术，在我们的场景下其表现效果不是特别好。
test generation to alleviate overfitting
下图中，假设最大的圈表示所有的补丁空间 search space，在补丁空间中有一些 plausible patches，这些 patches 能够通过给定的测试用例，但它们不一定是正确的。在 plausible patches 里，可能只有一小部分是 correct patches。
distinguish crashing and crash-free patches (practical)
我们的主要想法是通过测试用例生成，来区分出 plausible patches 里正确的和不正确的补丁。
在介绍具体的技术之前，我们先补充一下灰盒测试的背景。灰盒模糊测试 grey-box fuzzing 以一组种子 seed (即测试用例) 作为输入，测试引擎会基于给定的种子不断修改来生成新的测试用例，并在程序上运行这些新的测试用例，同时判断新的测试用例是不是 isinteresting 的。在传统的场景下，灰盒测试会判断新测试用例是否提升了代码的覆盖率，如果有提升，就将其加入到 input queue 里，进行进一步的变异。但这种判断方法对于补丁的语义是没有任何理解的。
grey-box fuzzing
为了解决这个问题，我们希望在用例判断的过程中加入补丁的语义信息。例如，生成新测试用例时，先判断测试用例有没有发现候选补丁行为的差异，如果新测试用例发现了补丁之间行为的差异，则把该用例加到 input queue 里进行变异。这样做的最终目标是通过不断发现补丁之间行为的差异，从而区分出哪些补丁是正确的，哪些补丁是错误的。
crash-avoiding program repair
## 举个例子
下面介绍一个缓存溢出和数据泄露的例子。
如下代码示例中，给定一个测试用例 s=foo, t=, n=4，运行会触发缓冲区溢出错误。
// copy the first n characters of s to tchar* strncpy(char* s, char* t, int n) { for (int i=0; i
id patch
p1 i < n - 1
p2 i < 3
p3 i < n && i n
...... ......
我们将补丁空间划分为 plausible partition 和 incorrect patch (plausible partition 即能够通过给定测试用例的补丁，incorrect patch 指仍然会触发异常的补丁)。其中，plausible partition 又可以划分为 crashing partition 和 crash-free patch (crashing partition 指虽然能够通过给定的测试用例，但在一些其他的测试用例上仍然会触发异常的补丁；crash-free patch 是指正确的补丁)。
为了对 plausible partition 进行进一步的划分，可以通过测试用例生成的方法，对原有的测试用例进行修改和变异。
id patch
p1 i < n - 1
p2 i < 3
p3 i < n && i < strlen(s)
若新生成的测试用例能够发现补丁之间行为的差异，那么就认为基于此测试用例的进一步变异，有更高的概率继续发现补丁之间行为的差异。通过不断生成测试用例，不断划分补丁分区，最终找到正确的补丁。
## 实现方法
下面介绍具体的实现方法。
我们定义了 ，用以表示一个新生成的测试用例是否能够发现补丁之间行为的差异：
separability 有两个作用，一是判断一个新生成的测试用例是否是 isinteresting 的 (即 non-zero separability)，若是，那么就进行进一步的变异。
第二是使用 separability 来定义种子的能量值 energy。能量值 energy 指对一个种子进行变异的次数。假设我们通过变异某个种子生成了 4 个新的测试用例，则其能量值为 4。拥有更高 separability 的种子会被分配更高的能量值。
不同时间和不同 separability 下能量值不同。
## 工具与实验：fix2fit
基于上述方法，我们实现了一个开源工具 fix2fit，并与 afl、aflgo 进行了对比。可以看到，fix2fit 相比 afl 和 aflgo 过滤掉了更多错误的补丁。
percentage of plausible patches that are ruled out
更多 fix2fit 信息：
github 地址：https://github.com/gaoxiang9430/fix2fit
相关论文：crash-avoiding program repair xiang gao, sergey mechtaev, abhik roychoudhury. acm sigsoft international symposium on software testing and analysis (issta) 2019.
## 思考：如何进一步排除补丁
上述方法可以过滤掉 crashing patch，但实际上还有一些没有引发安全隐患 (crash-free patch) 但依然是错误的补丁。怎样去区分这部分补丁 (下图中红色部分) 和正确补丁呢？这需要开发者参与进来。
我们假设通过一个测试用例，发现了两个补丁的差异行为，那么在程序确定的前提下，其中只有一个补丁会是正确的，那么此时我们就需要人的反馈来过滤掉不正确的补丁。需要强调的是，我们的研究工作不是为了取代人，而是为了帮助开发者生成一些推荐，使开发者能够更高效地修复问题。
如下所示，我们的实验中，如果有 5-10 次的人的参与反馈，那么我们可以从众多的 plausible patches 中筛选到 10 个左右。
number of plausible patches that can be ruled out if a few tests are empowered with more human oracles
# 程序状态变异
我们发现，如果从程序的入口处 entry point 开始对程序输入进行变异，会浪费掉大量的资源，要到达 patch location 是一件非常困难的事情。为了解决这个问题，我们提出，是否可以在补丁的位置直接进行变异呢？我们叫这种在 patch location 进行变异的方法为 state-level (snapshot) fuzzing，即对程序的状态进行变异。
snapshot fuzzing for repair
具体的方法是：
第一步，生成一些程序入口处的 test input ，针对每一个程序输入，收集它在 patch location 的程序状态 ；
第二步，根据程序状态 推断程序补丁 ；
第三步，通过 snapshot fuzzing，对程序状态进行修改，生成一个新的状态 ，去测试推断的补丁是否正确，同时也把新的状态加入到状态集合中 ；
返回第二步或者直接结束。
snapshot fuzzing 和传统 test generation 最大的区别在于，snapshot fuzzing 不是从程序的入口处对程序的输入状态进行变异，而是在 patch location 直接变异。这是一个不断循环的过程，最终的目标就是不断生成新的程序状态，同时不断优化程序的补丁。
## 实现方法
patch inference
那么，如何根据生成的程序状态推断一个补丁呢？这里用到了程序合成技术。
在程序状态 s 中，存在正样本和负样本。正样本是指不能触发安全事件的程序状态，负样本是指能够触发安全事件的程序状态。最终的目标是推断出一个程序补丁，使其在正样本上原有的程序执行保持不变，在负样本上，需要对程序的状态进行修改，从而把漏洞状态给关闭掉。
patch generation
生成程序补丁有两种方式。一种是加入到原有的 if/for/while 中，另一种是插入一个 if-guard 关闭错误的程序状态。
## 思考：infeasible states
这里存在一个问题，虽然我们用直接修改的方式在程序中间生成了一个程序状态，但是这个程序状态在真实的场景中不一定存在，即不一定是合法的。
针对这个问题我们也做了分析。如下图所示，通过 snapshot fuzzing 生成的程序状态，可能是 infeasible state，但即使生成了 infeasible state，对于 disable vulnerable state 是没有什么影响的。这主要因为，虚线表示的椭圆有可能也 disable 了一些 infeasible state，但它对于最终的目标是没有任何影响的。
snapshot mutation can generate infeasible states
## 工具与实验：vulnfix
在本个实验中，我们使用了 asiaccs'21 的数据集，其中包含 39 个真实世界的安全漏洞。我们设置了 30 分钟的超时机制。实验结果表明，vulnfix 可以成功修复其中的 19 个 漏洞，在已有的工具基础上有了明显的提升。
vulnfix generated more correct patches than cpr and senx.
# 语义分析与推理
前面介绍的两个工作，主要是基于 fuzzing 的方式来缓解过拟合问题。虽然能够在一定程度上缓解，但仍然没有办法保证生成的补丁能够修复所有错误的 test case。
为了解决这个问题，我们提出了一种 基于语义分析与推理方式修复 的方案。当一个安全漏洞被发现时，通常会有一个能够触发安全漏洞的 exploit (failing test)，如果仅以修复 exploit 作为目标，很容易产生过拟合问题。
除了 exploit 之外，可能还存在很多其他能触发缺陷的程序输入。那么，能否通过一种抽象的方式，将具体的 exploit 抽象成一种针对所有 failing input 的表示？在这个场景下，我们使用抽象的条件约束 constraints 来表示一个缺陷，这样修复的目标就不再是使其通过测试用例，而是使其满足给定的条件约束。
## 实现方法
生成条件约束
我们定义了一些模板，用以生成条件约束。比如，
buffer overflow：access(buffer) < base(buffer) + size(buffer)
integer overflow/underflow (a op b)：min ≤ a op b ≤ max (over z)
下面是一个的 buffer overflow 的例子。假设 rows 声明的长度是 256，访问时的 nrows 也是 256。根据约束 access(buffer) 5。这时候要从第 2 行进行程序的符号执行，发现两条程序执行路径，我们可以计算出第 6 行 cfc -> (y>5) 在第 2 行的最弱前提条件 cfc' -> (x>4 ⋀ i>0) ⋁ (x>6 ⋀ i≤0)。
patch synthesis
最后一步就是需要在 fix location 生成一个补丁。生成补丁之后，cfc' 一定是被满足的。这里其实是一个程序合成的问题，需要合成一个表达式，应用了表达式之后，cfc' 一定是满足的。具体的技术细节不展开了。
## 工具与实验：extractfix
关于实验，我们实现了工具 extractfix。在 30 个现实的 cve 中，我们的工具能够生成 24 个补丁，其中有 16 个和开发人员生成的补丁是一样的。
experiments with existing cves
更多 extractfix 信息：
网站：https://extractfix.github.io/
论文：beyond tests: program vulnerability repair via crash constraint extraction. xiang gao, bo wang, gregory j. duck, ruyi ji, yingfei xiong, abhik roychoudhury. transactions on software engineering and methodology (tosem), 2020.
# 总结 #
总结一下，今天主要介绍了三个缓解安全漏洞修复时过拟合问题的方法。包括 test case generation、snapshot fuzzing、以及语义分析与推理。
还是需要强调一下，由于程序 oracle (期待的程序行为) 的缺失，这些方法并没有彻底地解决过拟合的问题。因此我们只是提出了一些方法去缓解，最终的目标也是帮助开发人员更高效的修复程序缺陷。
以上。
# 相关论文 #
crash-avoiding program repair xiang gao, sergey mechtaev, abhik roychoudhury. acm sigsoft international symposium on software testing and analysis (issta) 2019.
beyond tests: program vulnerability repair via crash constraint extraction. xiang gao, bo wang, gregory j. duck, ruyi ji, yingfei xiong, abhik roychoudhury. transactions on software engineering and methodology (tosem), 2020.
双离合的种类以及优缺点
关于提升射频功率放大器的效率方法介绍
异步电机中的转子条数的定义、影响
变压器差动保护中电流互感器TA及其联接组的若干问题探讨
看到这个，你还把钱放到余额宝吗？你们有人放余额宝没？放多少呢
如何使用程序分析技术缓解漏洞修复的过拟合问题
VR技术与垂直行业的应用结合度将不断提升
你真的需要放弃4G套餐，来个消费升级吗
华为彭中阳发表了“构建数字新范式，共创行业新价值”的主题演讲
华为目前推迟了Mate系列的量产计划？
多屏显示卡
全桥移相ZVS控制器LTC3722-X的工作原理与如何实现自适应延时控制
YD/T 1595.1-2012 2GHz WCDMA标准：用户设备及其辅助设备
中广核岱山4#海上风电项目50台风机基础沉桩正式收官！
在物联网趋势下，安防前端设备技术如何切入到行业应用中
诺基亚拟发力汽车网络连接设备服务市场
新阶段工业互联网平台演进及其数字化技术分析
医学中AI工具和机器学习系统的研究和部署的八项安全伦理原则
随着人工智能技术的入注 安防行业将迎来变革
带热敷功能的无刷无感筋膜枪方案