在软件开发及维护过程中, 人工进行程序缺陷修复极大消耗和降低软件开发人员的精力和效率. 空指针引用作为程序缺陷中一类隐蔽缺陷的存在, 不易察觉和修复. 据研究表明空指针引用在缺陷数量中所占比例超过20%, 且修复平均时间达到20 min. 为了提高修复效率、降低修复成本, 自从2009年开始, 程序自动修复技术^[1-4]成为研究热点, 根据总结分析已有的程序自动修复技术可分为基于启发式搜索、基于人工模板、基于语义约束和基于统计分析的修复技术^[5]. 基于启发式搜索^[6]和基于统计分析^[7]的技术常被用来多类缺陷的通用修复策略的生成, 基于人工模板^[8]的修复技术适用于特定缺陷的补丁生成, 基于语义约束修复策略^[9]皆适用于两种情况. 但是由于造成程序缺陷的原因以及缺陷的影响范围存在不同, 对多类缺陷采取统一的修复策略可能会降低候选补丁的准确率, 所以针对某一特定的缺陷的修复更为有效.

为了实现空指针引用自动修复, 需要充分掌握程序间的依赖关系, 从而准确识别缺陷的修复位置, 采纳合理的修复方案. 而程序依赖图^{[10, 11]}包含数据依赖和控制依赖两个不同层次的依赖关系的融合, 可以充分掌握程序中的依赖关系. 但是数据依赖是由程序语句中的定义使用关系来识别, 这就忽略了语义本身所赋予的依赖关系. 例如, (1) x=a+a; (2) z=y+x%2, 根据语法中的定义和使用关系, z数据依赖于{y,x}, 然而x%2≡0, 在(1)的前提下, x的取值并不会影响表达式x%2的值, 也就是说, 实际上z并不取决于x的值. 从语义上来说y+x%2中的y是唯一与z相关的变量, 程序依赖图从语法上分析可能并不能计算出精确的依赖集, 因此并不能排除这种虚假依赖. 这就表明程序依赖图所识别的数据依赖关系超过了所需的依赖关系, 需要考虑真正的依赖关系及其传播.

本文做出了以下贡献.

(1) 提出了基于抽象语义的程序依赖图的空指针引用分析方法. 利用对抽象语义关联性的衡量, 忽略所有与抽象属性的不关联的语句节点进一步优化程序依赖图, 获取空指针引用的数据和控制依赖关系, 为选取修复位置及修复策略提供所需信息.

(2) 提出赋值、约束、规避、转移4种修复策略. 根据不同空指针引用的引发原因及缺陷所影响的代码集合, 依靠上下文信息选择4种修复策略实现修复.

(3) 提出基于语义距离的候选补丁排序方法. 通过计算不同候选补丁与原程序之间语义距离, 比较不同补丁对原程序的影响, 把所获得的候选补丁按照语义距离由小到大排列, 推荐最优补丁.

本文的其余部分组织如下: 第1节阐述基于抽象语义的程序依赖图的构建; 第2节介绍空指针引用的4种修复策略; 第3节解释如何通过语义距离对候选补丁的排序; 第4节展开了一系列的实验对比讨论, 评估本文方法的有效性; 第5节对本文工作进行总结, 同时展望下一步的研究工作.

1 基于抽象语义的程序依赖图

研究表明, 数据依赖关系和控制依赖关系可以获取程序上下文详细信息, 然而程序依赖图中数据依赖关系的分析通过变量的定义使用链仅分析变量语法上之间的关系, 并不能识别变量之间是否真正具有语义之间的关联. 具体语义的关联性的计算繁琐且耗时, 并且在程序修复过程中往往只关注所需某一种语义属性. 基于抽象语义的程序依赖图恰恰可以采用抽象属性对程序依赖图进行简化, 将虚假的数据依赖关系筛除, 准确分析与空指针或空对象相关的数据和控制依赖关系. 并且在下文的空指针引用的4种修复策略中, 可利用优化后的数据和控制依赖关系精确识别程序上下文完成修复. 在此过程中, 需采取某种抽象属性的语义关联性对特定的语义相关度进行近似计算, 而这也是将程序依赖图转换为基于抽象语义的程序依赖图^[12-14]的关键. 以下是基于抽象语义的程序依赖图的相关概念.

定义1. 控制依赖关系. 给定控制流图 ${{G}} = < N, E, Entry, Exit >$ , $\exists {n_1}, {n_2} \in N.$ P为G中从 ${n_1}$ 到 ${n_2}$ 的执行路径, 在P中除了 ${n_1}$ 和 ${n_2}$ 其他所有的节点都被 ${n_2}$ 后向支配, 并且 ${n_1}$ 并不被 ${n_2}$ 后向支配, 则 ${n_2}$ 控制依赖于 ${n_1}$ , 被定义为 ${n_1}\xrightarrow{{CD}}{n_2}$ .

定义2. 数据依赖关系. 给定控制流图 ${{G}} = < N, E, Entry, Exit >$ , $\exists {n_1}, {n_2} \in N,$ P为G中从 ${n_1}$ 到 ${n_2}$ 的执行路径. 节点 ${n_1}$ 定义变量v在节点 ${n_2}$ 中被使用, 且在P中不存在对v的重定义, 则 ${n_2}$ 数据依赖于 ${n_1}$ , 也就是 $ {n_1}\xrightarrow{{DD}}{n_2} $ .

定义3. 程序依赖图. 给定一个有向图 ${{G}} = < N, E >$ , $ E = \{ < {n_i}, {n_j} > \;|{n_i} \in N, {n_j} \in N, {n_i}\xrightarrow{{DD}} $ $ {n_j}\;or\;{n_i}\xrightarrow{{CD}}{n_j}\} $ , 即所有的边均为控制依赖边或数据依赖边则称为程序依赖图.

定义4. 抽象属性的数据依赖关系. 给定一个程序依赖图 ${{G}} = < N, E >$ , 语句节点 ${n_{{a}}}$ 和抽象属性ρ, 当 ${n_{{a}}}$ 在抽象状态 $ \sigma $ 上执行时, 若抽象属性ρ的状态发生了改变, 则表明 ${n_{{a}}}$ 与ρ语义相关. 此时, ${n_{{a}}}$ 所连接的数据依赖边才可保留. 抽象数据依赖边可表示为 ${E_{DD*}} = \{ e \in < {n_{{a}}}, {n_b} > \;|{n_a}, {n_b} \in N, {n_a}\xrightarrow{{DD}}{n_b}\; \cap \;$ $ \;{\sigma ^\rho } \ne \;\;\sigma _a^\rho \} $ , 其中 $ {\sigma ^\rho } $ 表示当前语句关于ρ的抽象状态, $ \sigma _a^\rho $ 表示执行完 ${n_{{a}}}$ 后关于ρ的抽象状态.

把抽象语义代替具体语义分析程序语句关联性时, 可以将程序依赖图中包含的控制依赖关系和数据依赖关系进一步精炼, 获得基于抽象语义的程序依赖图 $ {G_{pdg}} = < {N_{pdg}}, {E_{pdg}} > $ , $ {N_{pdg}} $ 表示语句的节点集合, $ {E_{pdg}} $ 是表示节点间控制依赖边或抽象数据依赖边. 为了识别空指针引用的精确依赖, 将把识别空指针的相关信息作为抽象属性来进一步优化程序依赖图.

根据修复空指针引用的分析可知, 判定一个赋值语句或者方法调用中的所获得值是否是空值是追踪空指针的关键因素, 故设定抽象属性 ${\rho _{\text{1}}} = \left\{ v = e\;| e \in Exp, \right. \left. v\xleftarrow{{{\rm{null}}}}e \right\}$ , ${\rho _2} = \{ m(\overrightarrow r )\;|\;\overrightarrow r \leftarrow {\rm{null}}\}$ . 在 $ {\rho _{\text{1}}} $ 中, v为变量, e为表达式, 表示在语句v=e中, e中传递的值为null. 在 $ \;{\rho _2} $ 中 $ m(\overrightarrow r ) $ 为方法调用表达式, 且参数 $ \overrightarrow r $ 为一个空值. 通过利用抽象属性的关联性梳理程序依赖图中的语句节点是否具有空指针传递的数据依赖关系, 删除虚假的数据依赖, 获取抽象数据依赖边.

例如, 示例1代表一个存在空指针引用的缺陷程序, cond为false, 且通过指针的传递在L7中造成空指针引用. 对于程序依赖图而言, 可以通过数据依赖边和控制依赖边构建出来如图1所示. 但是在分析过程中可以发现, 语句节点2、4、5和6并没有涉及空值的传递, 因此这4个语句节点与抽象属性 $ \;{\rho _{\text{1}}} $ 和 $ \;{\rho _2} $ 是语义无关的, 可将语句节点2、4、5和6及其数据依赖边和控制依赖边剪枝, 通过抽象数据依赖边的规则进一步识别精确的依赖关系, 最终获得基于抽象语义的程序依赖图(图2).

示例1. 存在空指针引用的缺陷程序

L1　public Mode analyzeAction(Boolean cond, Parser p, Mode type){

L2　　ConstructParser construct = new ConstructParser();

L3　　Action action = p.getAction();

L4　　if (cond) {

L5　　　　Parser parser = construct.getParser(type);

L6　　　　action = parser.changeAction(); }

L7　　Mode mode = action.mode;

L8　　return mode;

L9　}

为了获得关于抽象属性 $ {\rho _{\text{1}}} $ 和 $ {\rho _{\text{2}}} $ 的程序依赖图, 首先将分析抽象状态是否在程序中的赋值语句以及方法调用语句的语句点上发生变化, 忽略与抽象属性语义无关的赋值语句或者方法调用语句. 之后将对优化后的控制语句分为3类对其进行算法1所示的操作. 第1类是while语句, 在L4中 $bl{k_{{\rm{control}}}}$ 与抽象属性语义无关可忽略. 第2类是if语句, 在L6中 $bl{k_{{\rm{if}}}}$ 若与抽象属性语义无关可忽略. 第3类是if…else…语句, 在L9–L14中将分情况讨论, 在L9–L10中, 若 $bl{k_{{\rm{if}}}}$ 和 $bl{k_{{\rm{else}}}}$ 与抽象属性语义无关皆可忽略, 在L11–L12中, 若 $bl{k_{{\rm{else}}}}$ 与抽象属性语义无关则仅忽略 $bl{k_{{\rm{else}}}}$ , 在L13–L14中, 若 $bl{k_{{\rm{if}}}}$ 与抽象属性语义无关则仅忽略 $bl{k_{{\rm{if}}}}$ . 最后依据所保留的与抽象语义相关的语句构建基于抽象语义的程序依赖图.

算法1. 构建基于抽象语义的程序依赖图的方法

1: $\scriptstyle{\bf{for}}\;{ }s\;\; \in \;\;{s_{{\rm{control}}}}$

2:　 $\scriptstyle {\bf{case1}}:\;{\text{while }}\;{(}cond{) }\;{\text{then }}\;bl{k_{{\rm{control}}}}$

3:　　 $\scriptstyle{\bf{if}}{\; }\sigma {(}bl{k_{{\rm{control}}}}{)(}\rho {) = }\sigma {(}bl{k_{{\rm{control}}}}{')}$

4:　　　 $\scriptstyle{\text{while}}\;{(}cond{) }\;{\text{then}}{ }\;bl{k_{{\rm{control}}}} \leftarrow {\text{while}}\;{(}cond)\;{\text{then}}{ }\;skip$

5:　 $\scriptstyle {\bf{case2}}:\;{\text{if}}\;{(}cond{) }\;{\text{then}}\;{ }bl{k_{\rm if}}$

6:　　 $\scriptstyle {\bf{if}}\;{ }\sigma {(}bl{k_{\rm if}}{)(}\rho {) = }\sigma {(}bl{k_{\rm if}}{') }$

7:　　　 $\scriptstyle {\text{if}}\;{(}cond{) }\;{\text{then}}\;{ }bl{k_{\rm if}}{ }\; \leftarrow \phi$

8:　 $\scriptstyle {\bf{case3}}:\;{\text{if}}\;{(}cond{) }\;{\text{then}}\;{ }bl{k_{\rm if}}{ }\;{\text{else}}\;{ }bl{k_{{\rm{else}}}}$

9:　　 $\scriptstyle {\bf{case3a}}{: }\; \sigma {(}bl{k_{\rm if}}{)(}\rho {) = }\sigma {(}bl{k_{\rm if}}{')} \cap \sigma {(}bl{k_{{\rm{else}}}}{)(}\rho {) = }\sigma {(}bl{k_{{\rm{else}}}}{')}$

10:　　 $\scriptstyle {\text{if}}\;{(}cond{) }\;{\text{then}}\;{ }bl{k_{\rm if}}{ }\;{\text{else}}\;{ }bl{k_{{\rm{else}}}} \leftarrow \phi$

11:　 $\scriptstyle {\bf{case3b}}{: }\; \sigma {(}bl{k_{{\rm{else}}}}{)(}\rho {) = }\sigma {(}bl{k_{{\rm{else}}}}{')}$

12:　　 $\scriptstyle {\text{if}}\;{(}cond{)}\;{\text{ then}}\;{ }bl{k_{{\rm{if}}}}{ }\;{\text{else }}\;bl{k_{{\rm{else}}}} \leftarrow {\text{if}}\;{(}cond{) }\;{\text{then}}\;{ }bl{k_{{\rm{if}}}}$

13:　 $\scriptstyle {\bf{case3c}}{: }\; \sigma {(}bl{k_{{\rm{if}}}}{)(}\rho {) = }\sigma {(}bl{k_{{\rm{if}}}}{')}$

14:　　 $\scriptstyle {\text{if}}\;{(}cond{) }\;{\text{then}}\;{ }bl{k_{{\rm{if}}}}{ }\;{\text{else}}\;{ }bl{k_{{\rm{else}}}} \leftarrow$

　　　　　　　　 $\scriptstyle {\text{if}}\;{(}cond{) }\;{\text{then}}\;{ }skip{ }\;{\text{else}}\;{ }bl{k_{{\rm{else}}}}$

15: $\scriptstyle{\bf{end\;for}}$

2 空指针引用的修复

通过基于抽象语义的程序依赖图获取程序内精确的依赖关系后, 将结合空指针引用修复策略进行修复. 为了避免对程序其他功能造成隐患, 减小缺陷修复所带来的副作用, 本文尽力在最小的程序代码范围内实现精确修复, 因此在修复过程中把对程序执行路径的影响程度作为评价标准, 根据其影响程度由小到大依次提出了赋值策略、约束策略、规避策略和转移策略4种修复策略.

2.1 赋值策略

赋值策略主要是对缺陷变量通过类型适配进行赋值, 其修复方式分为两类: 第1类, 寻找缺陷变量的定义位置, 在定义位置上利用非空的值替换错误赋值; 第2类, 在缺陷变量使用之前, 预先进行判断缺陷变量是否为空, 若是则进行恰当赋值操作. 式(1)和式(2)分别代表这两类修复方式:

$ \frac{{DU({l_{{\rm{def}}}}, {l_{{\rm{use}}}}, v)\;\;{l_{{\rm{def}}}}:v = \_\;\;l:v = new\_value\;;}}{{{l_{{\rm{def}}}} \to l}} $

(1)

$ \frac{{DU({l_{{\rm{def}}}}, {l_{{\rm{use}}}}, v)\;\;c:v = = {\rm{null}}\;\;l:v = new\_value\;;}}{{{l_{{\rm{use}}}} \to {\text{if}}(c)\{ l\} \;{l_{{\rm{use}}}}}} $

(2)

其中, $DU({l_{{\rm{def}}}}, {l_{{\rm{use}}}}, v)$ 代表变量v的定义使用关系, ${l_{{\rm{use}}}}$ 表示变量v的使用的语句, ${l_{{\rm{def}}}}$ 表示变量v的定义的语句. c表示if语句中的条件表达式, l表示需要插入的语句. 式(1)则借助依赖关系寻找到缺陷变量的定义位置 ${l_{{\rm{def}}}}$ 重新赋值. 在式(2)中将在缺陷变量使用语句 ${l_{{\rm{use}}}}$ 之前增加if判断及重新赋值语句l.

替换缺陷变量的值new_value的选取分为4种: 第1种, 若缺陷点存在与返回值类型相同的活跃变量, new_value为该活跃变量; 第2种, 若v的类型为第三方API库, 则将修复位置的活跃变量与构造方法的形式参数的类型相比较, 选取最佳的构造方法的实例对象作为new_value; 第3种, 若v的类型为自定义类型且只有一个构造方法, 则new_value为当前构造方法实例对象, 若有多个构造方法, 则可以根据当前程序点的活跃变量与构造方法的参数匹配选择最佳构造方法的实例对象; 第4种, 若v 为有子类的自定义类型. 根据变量名与子类名之间相似度选择最佳匹配, 则该子类实例对象被选择为new_value.

2.2 约束策略

约束策略是通过对缺陷变量的提前进行条件判断来约束后续程序的执行, 其修复方式分为两类: 第1类, 将受到缺陷变量影响的代码集合预先放入条件判断中, 保证在缺陷变量不为空的情况下代码集合才可执行; 第2类, 将受到缺陷变量影响的代码集合放入try语句中, 在缺陷变量出现异常时抛出空指针异常. 式(3)和式(4)分别表示这两类情况:

$ \frac{{DU({l_{{\rm{def}}}}, {l_{{\rm{use}}}}, v)\;\;c:v! = {\rm{null}}\;\;ds(v) = \{ {l_1}, {l_2}, \cdots, {l_n}\} }}{{{l_{{\rm{use}}}} \to {\text{if}}(c)\{ ds(v)\} }} $

(3)

$ \frac{\begin{gathered} \;\;\;\;\;\;DU({l_{{\rm{def}}}}, {l_{{\rm{use}}}}, v)\;\;ds(v) = \{ {l_1}, {l_2}, \cdots, {l_n}\} \\ l:{\text{try}}\{ ds(v)\} \;\;{\text{catch}}({\text{NullPointerException}}\;\;e)\{ \cdots\} \\ \end{gathered} }{{{l_{{\rm{use}}}} \to l}} $

(4)

其中, ds(v)代表由缺陷点传递的错误信息影响之后执行的语句集合, 可通过基于抽象语义的程序依赖图所获取的依赖关系识别出缺陷变量的影响语句集合.

2.3 规避策略

规避策略根据不同情况添加适当中断语句, 转移当前方法的执行来避免空指针引用触发, 其修复方式可分为3类: 第1类, 若被缺陷变量所影响的代码集中包含return语句, 为了避免约束受影响代码集合时出现无返回值的情况, 则需在空条件判断中增加恰当返回值; 第2类, 若被缺陷变量所影响的代码集合中包含return语句, 也可将代码块放入try语句中, 将在catch 语句中增加适当返回值; 第3类, 若缺陷变量在循环的某次循环过程中出现, 可添加continue提前结束当前这次异常循环过程的执行. 其中恰当的返回值 $valu{e_{{\rm{return}}}}$ 分为5种, 第1种, 若返回值类型为基本数据类型, $valu{e_{{\rm{return}}}}$ 为基本数据类型的默认值; 其余4种与new_value获取方式相同. 式(5)–式(7)分别表示这3类修复方式:

$ \frac{\begin{gathered} \;\;\;\;\;\;\;DU({l_{{\rm{def}}}}, {l_{{\rm{use}}}}, v)\;\;c:v = = {\rm{null}} \\ ds(v) = \{ {l_1}, {l_2}, \cdots, {l_n}\} \;\;l:{\text{return}}\;\;valu{e_{{\rm{return}}}}; \\ \end{gathered} }{{{l_{{\rm{use}}}}\xrightarrow{{{\rm{type}}({l_1} \sim {l_n})\; \in \;{\text{return}}}}{\text{if}}(c)\{ l\} \;{l_{{\rm{use}}}}}} $

(5)

$ \frac{\begin{gathered} DU({l_{{\rm{def}}}}, {l_{{\rm{use}}}}, v)\;\;ds(v) = \{ {l_1}, {l_2}, \cdots, {l_n}\} \;\;l:{\text{try}}\{ ds(v)\} \; \\ {\text{catch}}({\text{NullPointerException}}\;e)\{ {\text{return}}\;valu{e_{{\rm{return}}}};\} \\ \end{gathered} }{{{l_{{\rm{use}}}}\xrightarrow{{{\rm{type}}({l_1} \sim {l_n})\; \in \;{\text{return}}}}l}} $

(6)

$ \frac{{DU({l_{{\rm{def}}}}, {l_{{\rm{use}}}}, v)\;\;c:v = = {\rm{null}}\;}}{{{l_{{\rm{use}}}}\xrightarrow{{{\rm{type}}(d\_dep(v))\; \in \;{\text{loop}}}}{\text{if}}(c)\{ {\rm{continue}}\;;\} \;{l_{{\rm{use}}}}}} $

(7)

其中, $ d\_dep(v) $ 表示缺陷变量v数据依赖的代码集合, $ {\text{type}}(d\_dep(v)) \in {\text{loop}} $ 表示 $ d\_dep(v) $ 的语句类型是否包含循环语句类型. 式(5)和式(6)分别采用了if和try对缺陷变量影响的代码集合进行约束, 并在出现空对象时将恰当的返回值返回. 式(7)首先判断缺陷对象的数据依赖代码集合中是否包含循环语句, 若是则添加continue结束本次循环, 进入下次循环.

2.4 转移策略

若空指针的来源作为参数传递进入方法中, 转移策略通过在空指针被引用之前添加判断条件, 在判断条件为真时将空指针异常抛给外部调用方法处理. 式(8)在缺陷变量为空时添加l语句将异常抛出, 由外部调用方法捕获处理.

$ \frac{\begin{gathered} DU({l_{{\rm{def}}}}, {l_{{\rm{use}}}}, v)\;\;c:v! = {\rm{null}}\;\;ds(v) = \{ {l_1}, {l_2}, \cdots, {l_n}\} \; \\ \;\;\;l:{\text{throw}}\;{\text{new}}\;{\text{NullPointerException(}}\cdots{\text{)}}\;;\;\; \\ \end{gathered} }{{{l_{{\rm{use}}}} \to {\text{if}}(c)\{ ds(v)\} \;{\text{else}}\{ \;l\;\} }} $

(8)

2.5 修复策略的匹配

考虑修复程序需在最小范围内的改动来消除空指针引用, 提出算法2来描述4种修复策略的匹配方法. Step 1获取当前程序缺陷的上下文信息, 之后判定是否满足修复策略所需条件并应用对应的修复操作. 因赋值策略的修复是从根本上改变缺陷变量的值完成修复, 所以首先在Step 4中判断的赋值策略的条件是否满足. 在此之后为了避免空指针的触发, Steps 5−6通过提取特定的条件选取约束策略或规避策略. 当之前3种策略均不可获得正确补丁时, Step 7判定是否满足转移策略的修复条件, 实施对应的修复操作. 最后在Step 10中验证获得的补丁是否通过所有的测试用例获取候选补丁.

算法2. 4种修改策略的匹配方法

输入: G: semantic-based abstract program dependency graph

输出: $\scriptstyle{p_{{\rm{can}}}}$ : the candidate patches; bugs: the information of defects; repair_oper (m): the repair operation

Begin

1.　 $\scriptstyle bugs \leftarrow extract\_{\textit{infor}}\_{\textit{for}}\_bugs\left( G \right)$

2.　　 $\scriptstyle{p_{{\rm{app}}}}, {p_{{\rm{can}}}} \leftarrow \phi$

3.　 $\scriptstyle {\bf{for}}\;{ }bugs\_{\textit{infor}}\;\; \in \;\;bugs\;{{{\bf{do}}}}$

4.　　 $\scriptstyle{\mathbf{case}}{{ }}{{{\bf{1}}}}{{: }}\;assignment\_infor \subset bug\_infor\;{\mathbf{then}}$

　　　　　 $\scriptstyle {p_{{\rm{app}}}} \leftarrow repair\_oper\left( {assignment} \right)$

5.　　 $\scriptstyle {\mathbf{case}}{{ {\bf{2}}: }}\;evading\_infor \subset bug\_infor\;{\mathbf{then}}$

　　　　　 $\scriptstyle{p_{{\rm{app}}}} \leftarrow repair\_oper\left( {evading} \right)$

6.　　 $\scriptstyle{\mathbf{case}}{{ {\bf{3}}: }}\;restraint\_infor \subset bug\_infor\;{\mathbf{then}}$

　　　　　 $\scriptstyle {p_{{\rm{app}}}} \leftarrow repair\_oper\left( {restraint} \right)$

7.　　 $\scriptstyle{\mathbf{case}}{{ {\bf{4}}: }}\;transfer\_infor \subset bug\_infor\;{\mathbf{then}}$

　　　　　 $\scriptstyle{p_{{\rm{app}}}} \leftarrow repair\_oper\left( {transfer} \right)$

8.　 $\scriptstyle {\bf{end}}\;{\bf{for}}$

9.　 $\scriptstyle{\bf{for}}\;{ }p\; \in \;{p_{{\rm{app}}}}\;{\bf{do}}$

10.　　 $\scriptstyle{\bf{if}}\;{ }p\;\;passes\;test\;cases$

11.　　　　 $\scriptstyle {p_{{\rm{can}}}} \leftarrow p$

12.　　 $\scriptstyle {\bf{end}}\;{\bf{if}}$

13.　 $\scriptstyle{\bf{end}}\;{\bf{for}}$

14.　 $\scriptstyle {\bf{return}}\;\;{p_{{\rm{can}}}}$

END

3 基于语义距离的补丁排序

经过匹配修复模板实施修复操作之后, 为了优先获取高质量的候选补丁, 将定义一些的评判规则对补丁进行排序. 在基于静态分析的补丁评价规则中一般分为语义距离^[15]和语法距离两种^[16]. 但是由于基于修复模板的缺陷修复本身就是通过不同的修复方式总结出的不同修复策略^[17], 通过语法距离评判修复补丁并不具有客观性, 因此在本文中选择基于语义距离对候选补丁进行排序.

补丁程序P'是对缺陷程序P进行有限的程序修改获得的, 在 ${T_{{\rm{sat}}}} \subseteq T$ 包含P和P'满足的所有的测试用例的执行过程中, 给定一个 $t \subseteq {T_{{\rm{sat}}}}$ , $ \pi (t) = ({\eta _0}, {\eta _1}, \cdots, {\eta _n}) $ 和 $ \pi ' (t) = (\eta {'_0}, \eta {'_1}, \cdots, \eta {'_n}) $ 分别表示P和P'在t的执行, 其中 $ {\eta _n} $ 是 $ ({l_n}, {v_n}) $ 形式的元组, $ {l_n} $ 为语句位置, $ {v_n} $ 为相应的变量取值, 则P和P'二者的语义距离可定义为:

$ \begin{split} &{d_\zeta }(P, P', T) =\\ &\quad \left\{ {\begin{array}{*{20}{c}} {\infty, \;\;\;\;{\text{if}}\;\forall LOC:P' \notin {R_{LOC}}(P)\;{\rm{or}}\;{T_{\rm sat}}\;{\rm{is}}\;{\rm{empty}}} \\ {\displaystyle \sum\limits_{t \in {T_{{\rm{sat}}}}} {(\left| {M - K} \right| + \sum\nolimits_{h = 0}^{min} {{\textit{diff}}({\eta _n}, \eta {'_n})\;),\;\;} } {\rm{otherwise}}} \end{array}} \right. \end{split}$

(9)

其中, M和K分别表示程序P和P'在T上执行路径的长度, $ min $ 表示M和K中的较小值, ${\textit{diff}}({\eta _h}, \eta {'_h})$ 表示在两次执行中比较执行位置和变量值, 如果 $ {\eta _h} = \eta {'_h} $ , ${\textit{diff}}({\eta _h}, \eta {'_h})$ 的值为0, 否则为1.

候选补丁P'和候选补丁P''为示例1的两个候选补丁, 分别代表两种不同的修复方式. 表1记录了一次测试用例中原程序与两个候选补丁的语义距离计算, 假设cond=true , p=p, type=type为输入参数, 因为参数和construct的值未改变, 故并未将其添加到表1中. 其中, loc为执行位置, 其余均为程序内变量. 从表1可以看出, 在示例1缺陷程序P中action和mode分别在代码行3和7被定义且赋值, 且action在代码行6中被重新赋值. 根据候选补丁P'和候选补丁P''中的代码来标记action和mode定义和赋值情况. 通过比较执行位置loc和程序变量状态的一致性, 在 ${\textit{diff}}(P, P')$ 中可以发现Steps 6−8这3列中P和P'程序变量状态并不一致标记为1, 同理, 在 ${\textit{diff}}(P, P'')$ 中Steps 3−5中P和P''程序变量状态也不一致, 因此, $\displaystyle \sum {{\textit{diff}}(P, P')}$ = $\displaystyle\sum {{\textit{diff}} {\left(P,\right.}} {\left. P''\right)}$ = 3. 但在表1中Steps 9−10, 候选补丁P'比P的执行距离多2步. 综上, 根据式(9), $ {d_\zeta }(P, P', T) $ =3+2=5, ${d_\zeta }(P, P'{{'}}, T)$ =3. 因此可以判定候选补丁P''为更加高质量的补丁.

代码1. 候选补丁P'

L1　public Mode analyzeAction(Boolean cond, Parser p, Mode type){L2　　ConstructParser construct = new ConstructParser();

L3　　Action action = p.getAction();L4　　if (cond) {L5　　　　Parser parser = construct.getParser(type);L6　　　　action = parser.changeAction(); }L7(+) if (acyion == null) {L8(+) 　action = new Action(t); }L9　　Mode mode= action.modeL10　　return mode;L11　}

代码2. 候选补丁P''

L1　public Mode analyzeAction(Boolean cond, Parser p, Mode type){L2　　 ConstructParser construct = new ConstructParser();L3(−) 　　Action action = p.getAction();L3(+) 　　Action action = new Action (t);L4　　 if (cond) {L5　　　　Parser parser = construct.getParser(type);L6　　　　action = parser.changeAction(); }L7　　 Mode mode = action.mode;L8　　 return mode;L9　}

4 实验

基于本文方法, 我们实现了一个缺陷自动修复工具DTSFix, 图3为其界面展示. 为了验证该工具在空指针引用的有效性, 实验1在公开数据集Defects4J^[18]中空指针引用上设计了相关实验, 与其他工具的修复效果进行对比. 实验结果表明DTSFix多修复9个缺陷, 平均节省人工修复时间180 min. 实验2则通过在开源的数据库管理工具DBeaver的修复过程中成功修复了67%的空指针引用, 成功证明在DTSFix在实际工程上的修复能力.

4.1 与其他修复工具的对比

在实验1中, 将DTSFix与同样专门针对空指针引用的工具NPEFix^[19]进行对比, 所采用数据集为Defects4J中空指针引用如表2所示, 其中Chart包含7个, Lang包含5个, Math包含3个. 通过表3中的实验结果中可以看出NPEFix仅能正确修复2个缺陷, 而DTSFix正确修复11个缺陷修复成功率为73.3%, 共产生候选补丁19个, 正确补丁个数为14个, 准确率为73.7%.

为了更好地获得正确补丁, 在DTSFix中加入了候选补丁的排序算法. 在表3中的CAP和COP_F分别为DTSFix中候选补丁的数量和候选补丁中第一个正确补丁的排名, 从COP_F中可以看出, 通过经过对候选补丁的进行语义距离排序后, 在已修复的12个缺陷中, 其中10个正确补丁位于候选补丁的排名第一位. 在含有多个候选补丁的5个缺陷中, 4个正确补丁经过排序后排名上升, 这表明基于语义距离的候选补丁排序能够较好地区分正确补丁与错误补丁, 从而有助于开发人员选择正确的补丁.

4.2 在实际工程上验证DTSFix的修复能力

为了验证DTSFix对实际Java工程中空指针引用缺陷的修复能力, 我们选取免费开源的数据库管理工具DBeaver进行实验. DBeaver可支持任何具有JDBC驱动程序数据库, 为开发人员和数据库管理人员提供支持. DTSJava^[3]作为检测工具对DBeaver进行缺陷检测, 其中含有9个空指针引用缺陷. 给定COP为正确补丁的数量, CAP为候选补丁的数量, DEN为缺陷数量. 从表4可以看出, DTSFix成功修复了6个缺陷, 其中约束策略修复4个, 规避策略修复2个. 未修复的3个缺陷中其中2个缺陷并未成功获得候选补丁, 原因在于修复模板提出的不够充分, 需要进一步细化空指针引用缺陷的修复模板, 但DTSFix对DBeaver的修复结果仍然可以确定DTSFix对于实际应用软件具有非常有效的修复能力.

代码3展示了其中一个空指针引用修复示例, 经过缺陷检测后缺陷开始行为224行, 缺陷发生行为226行, 缺陷变量为forTable. 经过基于抽象语义的程序依赖图分析forTable的缺陷影响的代码集合为{225, 226, 227, 228}, 其中228为return语句. forTable来源于外部参数通过赋值策略无法获取合适的值, 且缺陷感染域中包含return语句不满足约束策略的使用条件, 最后通过规避策略, 寻找方法中含有与返回值同类型同名变量的值, 增添修复语句如代码4进行修复, 并通过DTSJava进行回归测试结果证明缺陷已被成功修复.

代码3. DBeave缺陷程序示例

…223　protected JDBCStatement prepareChildrenStatement(@NotNull JDBCSession session,224　@NotNull OceanbaseMySQLCatalog owner, @Nullable MySQLTableBase forTable) throws SQLException { 225　　　　if (forTable instanceof OceanbaseMySQLView) {226　　　　　　　JDBCPreparedStatement dbStat = session227　　　　　　　　　.prepareStatement("desc" + owner.getName() + "." + forTable.getName());228　　　　　　　return dbStat; }…

代码4. DBeave缺陷示例修复补丁

…223　protected JDBCStatement prepareChildrenStatement(@NotNull JDBCSession session,224　@NotNull OceanbaseMySQLCatalog owner, @Nullable MySQLTableBase forTable) throws SQLException { +　　　　　　if (forTable==null){+　　　　　　　　　　return (JDBCPreparedStatement)session.prepareStatement(sql.toString());+　　　　　　　}225　　　　　if (forTable instanceof OceanbaseMySQLView) {226　　　　　　　　JDBCPreparedStatement dbStat = session227　　　　　　　　　.prepareStatement("desc" + owner.getName() + "." + forTable.getName());228　　　　　　　　return dbStat; }…

5 结论与展望

本文提出了一种基于抽象语义的程序依赖图的空指针引用的自动修复方法. 通过抽象属性对程序依赖图的剪枝构建一种基于抽象语义的程序依赖图, 在其掌握精确的控制依赖关系和基于抽象语义的数据依赖关系的基础上, 采用总结出来的赋值策略、约束策略、规避策略和转移策略4种策略完成修复. 最后利用基于语义距离的排序方法对候选补丁进行排序, 将高质量的候选补丁优先排列. 实验证明基于抽象语义的程序依赖图的空指针引用的自动修复方法针对空指针引用的修复能够保证在较好的准确率的情况下提供正确的修复补丁, 并且在实际工程中具有非常有效修复能力. 在未来的工作中, 将在基于抽象语义的程序依赖图的分析上进一步总结空指针引用的修复模板, 提升空指针引用的修复精度.