原论文：Automatic Software Repair: A Survey
原作者：Luca Gazzola, IEEE会员 Daniela Micucci, IEEE高级会员 Leonardo Mariani
2017年10月发表在IEEE Transactions on Software Engineering
原文链接：https://ieeexplore.ieee.org/document/8089448
译者：ClarkC.
此翻译已经原作者授权，翻译内容的准确性与原作者无关，引用请注明出处
感谢原文作者Leonardo Mariani教授提供翻译授权。鉴于原文很长，该翻译将分为七次上传。本次包含原文第6.2节的内容。原文中的参考文献可至附在开头与结尾的原文链接查看。
6.2 语义驱动的修复
语义驱动技术对问题
进行形式化的编码，例如显式编码为一个公式，其解对应于被修复程序的可能修复，或者隐式编码为一个分析过程，其结果就是一个修复。因此，当可以找到一个解
时，问题就可以保证有解，因此不需要对进行验证。
请注意，虽然解决方案可以保证解决，但它不能保证其完全满足开发人员的要求。是要解决的实际问题的近似表示，由于中可能有未表示到的方面，其解决方案可能有问题。例如，可以表示程序中存在的并发问题，的实际解决方案可能在修复并发问题的同时引入其他问题，例如安全或功能问题。因此，自动生成的解决方案仍然需要进行手动或自动的验证，以决定最终是否接受它们。
语义驱动技术的一般过程如图7所示。这个过程由三个主要的顺序活动组成。行为分析活动分析要修复的程序，以提取有关程序正确和错误行为的语义信息。为此，行为分析可以利用许多源代码，例如可用的测试用例、规范（specification）和被分析程序的源代码。行为分析通常利用这些资源的一个子集。例如，它可以关注运行测试套件能提取的动态信息，或者静态分析程序源代码能获得的信息。在前一种情况下，提取的信息可以采用输入输出对的形式，对程序中可能存在缺陷的代码片段应如何正确运行进行编码。在后一种情况下，提取的信息可以表示要从正在修复的程序中删除或修改的行为，以使其正确运行。
|
图7：语义驱动的修复过程 |
问题生成活动利用行为分析收集的信息，显式或隐式地生成修复问题的形式表示，其解决方案是表示实际修复的代码更改。
修复生成活动尝试解决在上一步中生成的问题，要么识别可能修复程序的代码更改，要么在修复问题的解决方案不存在或在合理的时间内找不到的情况下不生成解决方案。
在某些情况下，修复目标在程序中不同的位置，可能会反复进行问题生成和修复生成活动。修复生成过程还可能涉及隐式定义和遍历由修复问题的特定公式驱动的修复空间。
语义驱动技术通常处理特定的缺陷类，而不是一般的缺陷类。这是因为当考虑到正在修复的程序的特定特性（例如，锁定规程）时，找到问题的形式化表示要比试图生成修复问题的完全综合形式化表示更容易。表3显示了可以用现有语义驱动技术（“缺陷模型”列）解决的缺陷类别、试图修复缺陷时操作的代码元素（“更改模型“列）以及相应的修复技术（“技术”列）。“章节”列表示本文中讨论相应行中列出的技术的部分。接下来，我们首先简要介绍了几种语义驱动技术所使用的程序合成，然后讨论了每一类技术。
|
表3：语义驱动技术
|
6.2.1 程序合成
程序合成是实现语义驱动技术（尤其是那些具有普遍和错误的条件以及缺少先决条件的缺陷模型的技术）的关键，它被用来有效地构造修复。这些语义驱动技术使用的特定程序合成方法是预期结果引导的基于组件的程序合成[127]。我们将在下文中简要介绍这种形式的合成。
合成过程时将合成后的程序必须满足的一组输入输出对和一组可以重新组合以生成程序的基本组件（例如，运算符、常量和函数）作为输入，并输出满足每一对的函数（或程序）。
作为综合程序语句的一部分使用时，每个基本组件定义一个变量并使用一个或多个变量，这些变量可以由其他基本组件定义（例如，+基本组件使用两个变量，这两个变量是要求和的两个数，并生成一个变量，即求和）。合成过程通过识别变量和组件之间的一组合适的连接来生成所需的程序。此问题通常被编码为一阶逻辑约束问题，并使用可满足性模理论（Satisfiability Modulo Theory，SMT）求解器解决。
例如，如果我们假设提供一个合成算法，其包含两个输入变量x和y，基本组件C={+、sqr、sqr}和一组输入输出对I = {{(0,0), 0}, {(1,0), 1}, {(1,1), 4}、{(2,2), 36}}，那么合成算法将尝试以满足每个输入输出对的方式来连接这些组件。图8显示了一个可以通过合成创建的示例程序，以及一个通过连接输入变量和组件来生成程序的可视化说明。图中，用矩形表示组件并用位置号标识（标签“loc”），边表示如何将在给定位置生成的值用作在另一位置的输入（与每个位置关联的标签“input”）。SMT解算器用于查找这些连接，即为与每个位置关联的变量输入找到适当的值。
根据所使用的基本组件集，可以生成各种复杂度的程序。
|
图8：由程序综合创建的示例程序 |
6.2.2 通用技术
SemFix[21]合成由单个更改语句组成的修复。因此，需要在代码的多个位置进行更改的修复超出了此技术的范围。为了识别需要更改的语句，SemFix使用基于频谱的故障定位，并从最可疑的语句开始，按照可疑度顺序考虑。每次考虑语句时，SemFix都试图通过修改分支谓词来合成修复，即将条件 (
(...)) 更改为条件 (f (…))，或更改赋值的右侧，即将x = (…) 更改为x = f (…)。
在实践中，SemFix用一个符号表达式替换正在修复的程序中的表达式，该符号表达式要么表示一般条件，要么表示变量值的一般赋值。当执行可用的测试用例时，程序被具体地执行到修改后的语句，然后采用符号执行。这些执行用于在程序中引入的符号表达式上生成一组约束；约束对符号表达式必须满足的条件进行编码，以使程序通过所有可用的测试用例。
这些约束和一组基本组件一起用于解决程序合成任务。为了使生成的表达式尽可能简单，将提供给合成算法的基本组件划分为多个级别，然后逐步提供给合成过程。例如，当合成条件语句时，首先使用的基本成分是常量，然后该算法会逐步添加比较运算符，逻辑运算符，算术运算符等。
如果我们考虑算法5中的有缺陷的程序，SemFix将考虑根据可疑度来更改程序语句。让我们假设SemFix在某个点指向第1行的语句。SemFix尝试生成形式为if( f (...) ) 的新语句，其中f是输入变量和程序变量的函数。因为在程序的该点只定义了两个变量a和b，所以f必定是布尔值f(a，b)。假设可用测试用例的执行产生了以下约束f(10,15) = false，f(0,10) = true，f(0,15) = true，必须要满足这些约束才能通过测试套件。这个综合问题的一个可能的解决方案是a == 0。因此，可以用if(a == 0) 替换第1行的if条件来进行修复。
DirectFix [128]使用技术上类似于SemFix的整体方法修复程序中的错误表达式。DirectFix将有缺陷的程序转换为对行为进行编码的跟踪公式f，然后将失败的测试用例集转换为如果与跟踪公式结合使用将无法满足的一组预期约束O。因此，修复过程的目标是试图修改f中的表达式，使f ∧ O是可满足的。通过将问题简化为部分MaxSAT问题的实例来完成：提取f中的基本表达式，与原始公式结合，然后用占位符替换，生成所谓的修复条件；然后使用部分MaxSMT求解器生成满足f′ ∧ O的新公式f′。如果找到解决方案，则将公式级别的更改应用到代码中。
当同一有缺陷的表达式可能有多个修复时，DirectFix会选择最简单的修复，其基本假设是简单的修复不太可能引起回归问题。
与SemFix相比，DirectFix旨在降低修复表达式的复杂性并提高修复的可接受性。
Angelix [95]是一种语义驱动的修复技术，旨在保持可伸缩性的同时合成多行修补程序；DirectFix可以生成多行修补程序，但伸缩性不佳； SemFix具有可伸缩性，但只能进行单行修复。为了生成多行修复而不牺牲可伸缩性，Angelix利用了天使路径（angelic path）和天使森林（angelic forest）的概念。天使路径将修复问题的一部分编码为一组三元组，每个三元组包含一个可疑表达式的实例（由基于频谱的故障定位标识），其天使值（该表达式应返回以通过测试的值）和它的天使状态（在表达式位置可见的一组变量）。天使路径是使用符号执行提取的。天使森林将修复问题完全编码为一组天使路径。天使森林被提供给一个修复合成引擎来产生多行修复。
SearchRepair [44]利用编码为SMT公式的人工编写的补丁数据库。这样就形成了一个SMT公式数据库，该数据库对能在各种情况下修复缺陷的更改进行编码。当需要修复程序时，SearchRepair使用基于频谱的缺陷定位来确定可能有缺陷的代码片段，而失败和通过的测试用例用于生成输入输出约束，该约束描述了对每个可能有缺陷的代码片段的预期行为。然后搜索SMT公式的数据库，以寻找可能使目标片段产生预期输入输出行为的更改。如果找到，则在要修复的程序中执行数据库中表示的更改。对于每个已选择的区域，系统地重复此过程。 以这种方式获得的候选修复将通过可用的测试套件进行验证。
示例
SemFix，Angelix和DirectFix可以修复算法2、3和5中的错误程序。SearchRepair修复错误示例算法的能力取决于数据库包含的修复样本：如果提供了合适的代码片段，则可以修复任何错误。
6.2.3 条件错误和前置条件缺失
本节中介绍的技术针对条件错误（在分支或循环语句中）和前置条件缺失。尽管每种技术都使用了特定的机制，但它们共有的高级过程包括使用定位算法来识别程序中最可疑的条件，收集可疑条件作用域内可用的变量，以及形成程序合成问题，其解决方案就是修复后的条件。
NOPOL[23]，[129] 生成包括在条件和循环语句中的单一条件更改的修复。 NOPOL使用基于频谱的故障定位技术来识别包括条件的可疑语句，并使用天使修复定位技术来确认潜在修复位置的存在（见第5节）。实践中, 天使修复定位技术可以确定，对失败的测试用例，将其所选条件的真值取反能够修复程序。
NOPOL运行测试用例，并收集有关目标条件为通过所有测试用例所要返回的真值的证据，以及在可能需要修复的有缺陷的条件作用域内的变量值。目标条件必须返回的真值可以表示为集合
，其值表示在第n个测试用例执行过程中对它进行第m次评估时在程序位置l处该条件的预期结果。l作用域内的变量的值由集合
表示，其值表示在第n个测试用例的第m次执行期间在位置l处收集的变量值。修复合成问题因此可以编码为找到表达式exp，满足：
通过组合简单的算术表达式和程序变量，可以获得exp的可能值。
如果将其应用于算法5中所示有缺陷的程序，天使修复定位可以轻松地将第1行的语句标识为要修改的语句，以使程序通过所有可用的测试用例。测试用例的执行产生了一组观测值
= (a = 10，b = 15)，
= (a = 0，b = 10) . . . 
= (a = 0，b = 15) 和相应的预期结果（
= false，
= true, . . . , 
= true） 用作程序合成过程的输入。此合成问题的解决方案是表达式a == 0，该表达式通过替换程序的语句1中的条件来修复程序。
Dynamoth [130]是NOPOL的新型合成引擎。由于NOPOL无法合成包括方法调用的条件，因此Dynamoth扩展了NOPOL的功能，使其能够收集可疑条件运行时的上下文（包括方法调用的参数，变量，字段和返回值），并将这些元素组合为新合成的条件。
Infinitel[26]类似于NOPOL，但专门针对无限循环类缺陷，因此它的修复过程是针对性的，改变循环条件使循环运行有限次，同时使程序产生预期输出。
如果一个循环被执行超过一百万次，那么Infinitel就假设它是错误的。利用在天使修复定位中实现的相同策略，Infinitel确定能使测试用例通过的循环执行次数（如果有的话）。这个数字叫做天使记录。与NOPOL类似，Infinitel生成一组约束，强制循环的新条件在迭代次数小于天使记录时取值为true，并在到达天使记录时取值为false。给定这组约束后，新条件的合成工作与NOPOL相同。
我们考虑算法3所示的错误程序。当执行测试输入（a = 10，b = 0）时，程序在第4行的循环语句上无限循环。Infinitel分析执行情况，发现失败的测试用例可以在天使记录为0的时候通过测试，也就是说没有执行循环。这个证据和从其他测试用例中收集到的数据一起，被用作程序合成过程的输入，其解就是程序的正确条件。
示例
NOPOL和Dynamoth针对由于条件错误所导致的缺陷，因此它们只能修复算法2和5中的错误程序，而Infinitel的目标是无限循环错误，因此它可以修复算法3中的错误代码。
6.2.4 并发缺陷
本节中介绍的技术针对并发缺陷，例如原子性冲突，死锁，活锁和安全策略违规。解决并发缺陷的一般方法是对系统进行分析，发现可能导致并发缺陷的弱代码区，然后通过添加适当的检查和同步机制来增强这些代码区，从而防止并发问题。
AFix [82]可以修复单个变量的原子性冲突缺陷，即由于操作被认为相对于变量而言是原子性的缺陷，但事实证明它们可能与访问同一变量的其他操作交错。
作为行为分析的一部分，AFix使用CTrigger[83]来监视正常的程序执行并发现原子性冲突。原子性冲突被表示为三元组（p，c，r），其中p和c是在同一线程上对变量x顺序执行操作的指令，r是在p和c之间发生的对x的远程修改或读取。
在这些情况下，AFix通过解决将p和c置于关键区域中，并将r置于由同一锁控制的另一个关键区域中以使两个区域互斥的简单问题来生成修复。对于已发现的所有原子性冲突的错误，都多次应用此过程。AFix包括最后一步，删除多余的补丁，合并重叠的补丁。
CFix[131]被设计成比AFix具有更多的通用修复功能，AFix只能通过使用互斥锁原语来解决原子性冲突。CFix通过将并发bug分解为互斥和排序问题的组合来解决并发bug。AFix同样考虑互斥问题，而CFix引入了排序问题。
从错误报告开始，CFix首先使用多种错误检测器来检测并发缺陷，以发现导致故障的执行时序，并将发现的错误映射到特定的互斥或顺序问题。 然后，CFix使用静态分析来确定在何处使用锁和条件变量来同步程序操作并可能修复该错误。 根据问题的类型，CFix使用AFix强制执行互斥或使用一种称为OFix的新技术保证执行的顺序关系。 由于某些类型的故障可以使用多种修复策略，因此CFix可以为同一并发问题识别一些修复程序。 对这些修复程序进行了性能和简单性测试，然后选择最佳修复程序。 最后，合并为多个错误生成的修复程序，以在修复的程序中引入最少数量的同步变量和操作。
HFix [132]是CFix的扩展，它通过仅添加锁操作和条件变量来解决并发性错误的问题，在某些情况下不必要地增加了修复的复杂性。 这两种方法都旨在解决从程序分析中发现的执行顺序问题。 HFix通过大量重用程序中已经存在的代码而不是生成新代码来生成更简单的修复程序。 该技术包含两种错误修复方法：
和
。可以通过插入强制执行正确操作顺序的连接操作来修复涉及两个线程的顺序冲突缺陷。可以通过重新安排与联接操作有关的操作顺序（如果需要，将操作移至新线程）来修复顺序违规缺陷，也可以通过移动锁和解锁操作以建立适当的关键区域来解决原子性违规缺陷。
Surendran等人[133]提出了一种技术，旨在修复用结构化并行语言编写的程序中的数据竞争，特别是针对这些语言用于实现并行化的两种结构的使用：异步和完成（分别用于创建和终止任务）。该技术以一个未同步或部分同步的程序和一个测试用例作为输入，使用ESP-bags算法[134]来检测数据竞争，并确定在何处插入额外的finish语句，这些语句结合修复问题形式化过程中用到的动态分析和静态分析技术来避免产生数据竞争。
Axis[135]解决了原子性违规问题，但假设已经通过其他某种方式识别了涉及原子性违规的语句，也就是说，它未实现行为分析活动。 Axis创建程序的Petri Net模型，并将软件的正确行为编码为控制约束条件，可以用数学方法解决该约束条件，以获得新的Petri Net模型，该模型消除了原子性违规而不会引入任何死锁。
生成的Petri Net模型中引入的新锁已添加到程序的源代码中，以修复并发缺陷。
Grail [136]是一项扩展Axis的技术，它具有生成不仅正确而且在特定意义上最优的修正的能力，使得互斥仅应用于可能出现错误的那些场景。 Grail产生的修复程序也比Axis产生的修补程序更有效，因为Grail同时考虑了可能暴露并发故障的多个运行时配置以及线程的同步行为。 该分析仍基于Petri网模型。
Lin等人[137]提出了一种可以修复死锁，活锁和称为饿死锁的第三种饥饿缺陷的技术，这是一种微妙的阻塞情况，即两个线程都在等待锁而被阻塞，并且线程试图获取锁。这种修复技术使用的方法是首先识别程序中循环相关语句的集合以及所有lock和trylock语句。 然后，它将所需的程序行为编码为加权的部分MaxSAT公式，求解该公式以寻找最小化修复程序大小的解决方案。 如果找到解决方案，则会对原始程序进行相应的修改，例如用trylock替换锁，并删除trylock操作的false分支。
DFixer [53]可以修复死锁，而不会引入新的死锁。该技术首先分析程序，以通过反向获取资源来识别线程对可以在何处造成死锁。利用该信息来构造程序行为和要解决的修复问题的表示。当发现有问题的情况时，DFixer将选择死锁中涉及的两个线程之一，并将该线程执行的第一个锁操作替换为同时获取第二个锁的操作。例如，如果线程1尝试使用acquire(r) 和acquire(s) 操作连续获取两个不同资源r和s上的两个锁，而线程2尝试以相反的顺序获取相同的资源，则可能的修复方法是将线程1中的acquire(r) 和acquire(s) 替换为acquire(r, s)。
6.2.5 HTML生成缺陷
HTML生成使得互斥仅应用于可能出现错误的那些场景是html生成代码中的使得互斥仅应用于可能出现错误的那些场景。 PHPQuickFix是一种简单的技术，可以检测和修复使用不正确的html代码打印文字的打印语句[138]。
更有趣的是，PHPRepair可以解决由多个常量打印语句的交互导致的错误，例如动态构造的HTML表中缺少</td>标记[138]。PHPRepair首先运行可用的测试用例，并将测试执行描述为常量打印序列。然后根据测试用例将这些打印语句与预期输出进行比较。这将生成修复问题的编码，该编码由字符串约束解算器求解，该解算器标识正确的打印流。最后，PHPRepair在原始程序中添加、修改和删除常量打印语句，以匹配预期的行为。
6.2.6 字符串清理
字符串清理技术修复在Web应用程序中错误地检查输入字符串有效性的例程。
SemRep [139]可以通过自动添加其他验证函数中存在但目标函数中缺少的检查，来修复Web应用程序中存在的部分输入验证函数。 其思想是，相似的验证函数可能存在于同一应用程序和不同的应用程序中，并且可以通过将检查从一个函数转移到另一个函数来利用它们修复不完整的验证函数。 该技术使用正向和反向符号字符串分析来描述修复问题，并转移验证、长度和清理检查。
Yu等人[52]，[140]提出了一种为Web应用程序中的输入清理函数生成修复程序的技术。该技术从破坏应用程序并在两个阶段生成修复程序的输入模式和攻击模式（指定为正则表达式）开始。第一阶段，清理签名生成，自动识别良性输入字符串的签名。它首先使用符号字符串分析来计算每个可能到达安全敏感函数的字符串的过近似值，该近似值一旦与攻击模式相交，便表示其可能是攻击字符串集。然后使用反向符号可达性分析来识别可能产生这些攻击字符串的恶意用户输入。安全输入集（即清除签名）由不在恶意用户输入集中且可以用应用程序构造的输入给出。
第二阶段，最佳清理合成，生成一个清理程序，该清理程序会自动将恶性输入字符串转换为良性字符串，同时根据编辑距离将对输入的干预程度降至最低。
6.2.7 访问控制违规
FixMeUp [42]专门针对PHP Web应用程序中的访问控制冲突缺陷。 该技术通过检测易受攻击的程序位置，然后使用访问控制模板转换缺少适当访问控制的程序段来工作。
FixMeUp需要一个规范，指明哪些敏感操作必须通过访问控制检查来保护，然后它对程序的调用、数据和控制依赖关系图使用过程间程序切片来识别需要由访问控制检查保护的语句。
FixMeUp检查每个敏感操作和每个调用上下文，只有被允许执行敏感信息的用户角色才能执行。如果发现冲突，则使用适当的模板通过插入缺少的访问控制检查来修复程序。
最后，为了检测修复可能带来的副作用，重复进行分析以发现违反访问控制规则的行为，以检查问题是否已消失。如果问题尚未解决，则放弃更改。对于程序中的每个问题点都会重复此过程。
6.2.8 内存泄漏
LeakFix [54]针对C程序中的内存泄漏。 它分析内存分配语句并确保执行路径中没有泄漏。 这是通过首先识别分配、使用和释放内存的地方，然后使用包含有关分配、使用和释放的信息的控制流程图抽象程序。 如果检测到泄漏，则将free( ) 语句添加到程序的适当位置以释放不再使用的内存。
（未完待续）
若发现翻译问题，可直接评论或与我联系：cheng.yifan@qq.com
原文链接：https://ieeexplore.ieee.org/document/8089448
译者：ClarkC.
此翻译已经原作者授权，翻译内容的准确性与原作者无关，引用请注明出处