一种基于变更衍化与标识重构的软件缺陷修复方法

1.本发明是对软件质量与自动化领域中，基于模板修复的自动程序修复中准确率较低并且修复时间较长问题，而提出的一种新的软件缺陷修复方法，旨在使用该技术后，能够大大减少软件缺陷修复需要收集的变更数以及生成一个正确补丁之前产生的不正确的候选补丁数。


背景技术：

2.在软件开发的过程中，软件出现缺陷几乎是不可避免的。在开发软件的过程中，修复有缺陷的程序在软件周期中占了很大比重的时间。通过程序自动修复解决软件缺陷问题，有希望大大减少开发人员的开发时间，快速解决程序中出现的bug。
3.近些年，关于这方面的研究也有了很多成果，主要形成了四大类方法，基于启发式搜索、基于语义约束、基于统计分析和基于修复模板的这四大类方法。本文主要针对的是基于模板的修复方法。基于模板修复的方法目标性很强，并且不会产生一些晦涩难懂的修复补丁。因此是一种比较实用的软件缺陷修复方法。然而目前基于修复模板的方法，在准备修复模板的过程中，需要数以万计的修复模式以提取修复模板。在这些提取的修复模式中，只有小部分的修复模式被使用的概率很大，大部分的修复模式很少用到或者几乎用不到，更重要的是有的修复模板与bug修复很接近但又有一点差别，导致该修复模式并没有被使用，以至于和其它不相关的修复模式被视为同一种情况，事实上，只需要对该修复模式变化一个小的部分，比如变化某个字段或者变异某个运算符就能够达到正确修复模板的效果。


技术实现要素：

4.本发明提出了一种基于变更衍化与标识重构的软件缺陷修复方法，通过对使用频率比较高的变更进行衍化，生成更多相似的变更，同时丢弃掉那些几乎用不到的变更，在变更收集阶段大大减少变更的收集数量，同时通过度量变更与bug语句的相似度加速变更的检索过程，减少寻找对应修复模板的时间。在软件开发的过程中，具有良好编程习惯的开发人员往往都遵循着一定的开发规范，在实际开发中，经常需要定义变量、字段和字面量，常见的命名法则有帕斯卡命名法、下划线命名法、匈牙利命名法和驼峰命名法，以驼峰命名法更为常见。以驼峰为分割的每个单词都有它特殊的含义，通过对变量、字段等标识进行拆分，同时对拆分后的字面量进行同义替换，增加抽象变更具体化产生正确补丁的概率。这体现在我们变更具体化阶段，对抽象变更进行具体化的时候，不仅仅使用从源项目文件中收集到的变量、字段、字面量等，我们还对其中以驼峰命名的标识符按驼峰进行拆分，同时对拆分后的子标识进行重构，得到新的标识符，不仅增加具体化抽象变更时，标识符的选择数，而且在一定程度上减小了候选补丁与正确补丁的距离。
5.本发明方法具体包括以下步骤：
6.步骤1、从开源社区按照highest score、views、stars条件进行筛选提取到的高频历史变更以及变更对应的上下文；
7.通过按照开源社区访问热度，收集高频的变更数以及该变更所对应的上下文，避免收集到几乎用不到的变更修复模式。
8.步骤2、对收集到的变更进行上下文的识别，并且按照它们的上下文进行分类，把同一上下文的变更，放在同一变更集下；
9.步骤3、对变更池中的变更进行衍化，具体操作如下：
10.步骤3-1：将变更解析为抽象语法树
11.步骤3-2：遍历抽象语法树中的所有节点，通过关键节点规则集，识别抽象语法树中的关键节点；
12.关键节点规则集如下表(部分)：
[0013][0014]
识别上述节点为关键节点。
[0015]
步骤3-3：对识别到的关键节点按照衍化规则集对变更进行衍化；
[0016]
衍化规则集如下表(部分)：
[0017][0018]
步骤3-4：将衍化后的变更加入原始变更的上下文当中
[0019]
将步骤3-3中衍化得到的变更，建立与原始变更的属性联系，并加入到原始变更对应的上下文当中。
[0020]
衍化变更的原节点node:
[0021]
node{id:x1,nodetype:types,content:ctnts,attrs(attr1,attr2,
…
,attrn)}
[0022]
衍化变更生成的新节点node*:
[0023]
node*{id:x
t
,nodetype:type
t
,content
t
:ctnt,attr
t
(attr1*,attr2*,
…
,attrn*)}
[0024]
步骤4、对缺陷进行定位并识别缺陷的上下文
[0025]
用ochiai缺陷定位工具对缺陷进行定位，得到可疑分数从高到底的可疑语句排列，按顺序选取可疑语句。提取可疑语句的上下文，与补丁池中的变更上下文进行比较，找到最佳配对的上下文。
[0026]
步骤4-1：使用ochiai缺陷定位方法对缺陷进行定位，语句可疑度分数计算如下：
[0027][0028]
其中failed(s)表示覆盖了语句s的失败的测试用例数目，passed(s)表示覆盖了语句s的成功的测试用例数目，totalfailed表示失败的测试用例总数目。
[0029]
步骤4-2：识别定位可疑语句的上下文，并按上下文，在变更池中检测对应的变更序列集
[0030]
步骤5、对变更序列集通过度量相似性进行排序
[0031]
步骤5-1：根据抽象语法树的节点类型计算原始泛化的bug语句与变更集中变更的相似性分数
[0032][0033]
其中k表示原bug语句与变更集的ast类型总数，tns(i)表示原bug语句的节点类型，tnt(i)表示变更集中变更的节点类型。
[0034]
步骤5-2：计算原始泛化的bug语句与变更集中变更的最长公共子序列计算相似性
[0035][0036]
其中lss是原始变更的子序列，lst衍化变更的子序列
[0037]
步骤5-3：根据衍化变更对原始变更的修改大小进行计算被修复的大小,由于原始变更为本身，所以它具有最高的分数
[0038][0039]
其中mfs是原始变更的子序列，mft衍化变更的子序列
[0040]
步骤5-4：对前面5-1、5-2、5-3计算的相似性得分进行归一化，然后计算最终的相似性得分
[0041]
simi(ns,nt)＝f(tns,tnt)*f(lss,lst)*f(mfs,mft)
[0042]
步骤5-5：根据5-4计算的最终相似性对变更集进行排序
[0043]
rank_change
context
＝{changes,change1,change2,
…
,changen}，其中changes表示原始的变更；
[0044]
步骤6、对抽象变更进行具体化产生候选补丁
[0045]
步骤6-1：通过对本地项目的源码文件进行处理解析得到一个本地源码语料库的词库
[0046]
步骤6-2：对原始bug语句的标识符进行拆分重构(举例如下)，得到更多相似的标识符。
[0047]
orders.insertfirstitem()
[0048]
对原序列进行拆分得到：{orders,$insert$,$first$,$item$}
[0049]
查询同构词语料库：
[0050]
{$insert$:$delete$,$replace$；$first$:$second$,$last$}
[0051]
使用同构词，可以得到更多重组新的标识符。
[0052]
{insertfirstitem:insertseconditem,insertlastitem,deletefirstitem,deleteseconditem,deletelastitem,replacefirstitem,replaceseconditem,replace lastitem}
[0053]
步骤6-3：按照变更排名分数依次选取候选变更，对抽象变更进行具体化产生候选补丁，具体化描述如图5
[0054]
步骤6-4：采用以下四种策略选择标识符进行选择
[0055]
1、度量同构词与标识符的相似性，相似性越高的标识的重用的优先级越高
[0056]
2、在源项目中使用频率越高的标识符的优先级越高
[0057]
3、结合前面两种策略，在频率相同的情况下，相似度越高的标识符越有可能被重用
[0058]
步骤6-5：抽象变更具体化之后产生候选补丁
[0059]
步骤7、验证候选补丁，采用级联验证，只有前面一级验证通过后才进行下一级验证，以减少补丁验证时间。
[0060]
作为优选，所述的识别变更的上下文，根据上下文，对变更池中的变更进行分类，具体为：
[0061]
步骤2-1：对于上下文的定义，沿用已有的方法kim et al；通过定义节点类型和节点散列来表示上下文，其中节点类型可以表示抽象的上下文类型，节点哈希表示更独特上下文类；
[0062]
步骤2-2：节点类型定义
[0063]
假设r是变更子树的根节点，在r的上下文中使用的节点a的节点类型type(r,a)来表示上下文，其中type(r,a)的定义如下：
[0064][0065]
其中a.loc是a的语法位置；
[0066]
步骤2-3：节点散列定义
[0067]
假设节点a为例子：
[0068]
hash(a)＝{a.type{h(c1)，h(c2)，
…
，h(ck)}}
[0069]
其中c1,c2,
…
,ck是节点n的孩子节点
[0070]
步骤2-3：由节点类型和节点散列组成上下文表示
[0071]
上下文ctx是由三个组件c
p
，c
l
，cr组成；让c成为一个变更的根节点，具有一组节点s的每个组件cs是由节点n的节点类型t(n,c)或者节点散列h(n)串联组成；上下文的组成形式如下：
[0072]
ctx＝p：c
p
，l：c
l
，r：cr[0073]
按照上下文，对变更池中的变更进行分类，把相同上下文的变更加入到同一变更序列，同时对同一上下文中的变更依据频率进行排序，得到一个分类良好的变更池。
[0074]
作为优选，所述的级联验证，具体为：
[0075]
1)首先对候选补丁进行编译；2)如果编译通过则进行触发测试；3)如果触发测试通过则运行相关测试；4)如果相关测试通过则运行全部的测试；通过全部测试的补丁由于过拟合问题仍然可能不正确，需要进行人工检查，如果候选补丁在语法和语义上等价于人工补丁，则认为该补丁是一个正确的补丁。
[0076]
本发明的有益效果：
[0077]
1、通过变更衍化，增加模板应用成功的概率，同时减少前期变更收集的数量。
[0078]
2、对同一上下文中的变更集，通过计算三种类型的相似度得分，对变更进行排序，使得正确性越高的变更越早被使用，从而减少寻找最优变更所需要的时间。
[0079]
3、通过考虑开发过程的编程规范，以广泛使用的驼峰命名法对标识进行拆分，利用同构词语料库，对存在相近语义的子标识进行替换重构，从而组成新的标识，一方面对原有标识进行一个扩充，另一方面增加抽象补丁具体化得到正确补丁的概率。
附图说明
[0080]
图1基于变更衍化与标识重构软件缺陷修复方法整体流程图；
[0081]
图2关键节点识别图；
[0082]
图3变更衍化示例图；
[0083]
图4变更排序算法描述；
[0084]
图5变更具体化算法描述。
具体实施方式
[0085]
下面结合附图对本发明进行详细说明。本发明的整体流程如附图图1所示，具体步骤如下：
[0086]
步骤1：从开源社区按照highest score、views、stars条件进行筛选提取到的高频历史变更以及变更对应的上下文。
[0087]
步骤2：对提取的变更进行泛化，并根据它们的上下文构建一个分类良好变更池，具体为：步骤2-1：对于上下文的定义，沿用已有的方法kim et al；通过定义节点类型和节点散列来表示上下文，其中节点类型可以表示抽象的上下文类型，节点哈希表示更独特上下文类；
[0088]
步骤2-2：节点类型定义
[0089]
假设r是变更子树的根节点，在r的上下文中使用的节点a的节点类型type(r,a)来表示上下文，其中type(r,a)的定义如下：
[0090][0091]
其中a.loc是a的语法位置；
[0092]
步骤2-3：节点散列定义
[0093]
假设节点a为例子：
[0094]
hash(a)＝{a.type{h(c1)，h(c2)，
…
，h(ck)}}
[0095]
其中c1,c2,
…
,ck是节点n的孩子节点
[0096]
步骤2-3：由节点类型和节点散列组成上下文表示
[0097]
上下文ctx是由三个组件c
p
，c
l
，cr组成；让c成为一个变更的根节点，具有一组节点s的每个组件cs是由节点n的节点类型t(n,c)或者节点散列h(n)串联组成；
[0098]
上下文的组成形式如下：
[0099]
ctx＝p：c
p
，l：c
l
，r：cr[0100]
按照上下文，对变更池中的变更进行分类，把相同上下文的变更加入到同一变更序列，同时对同一上下文中的变更依据频率进行排序，得到一个分类良好的变更池。
[0101]
步骤3：对提取的变更解析成抽象语法树，根据关键节点规则集识别抽象语法树的关键节点，如图2所示；
[0102]
关键节点规则集如下表，
[0103][0104]
步骤4：对关键节点根据衍化规则集对变更进行衍化，并加入到变更池对应的上下
[0105]
文当中，如图3所示；衍化规则集如下表示；
[0106][0107]
将衍化得到的变更，建立与原始变更的属性联系，并加入到原始变更对应的上下文所在的变更集中；
[0108]
衍化变更的原节点node:
[0109]
node{id:x1,nodetype:types,content:ctnts,attrs(attr1,attr2,
…
,attrn)}
[0110]
衍化变更生成的新节点node*:
[0111]
node{id:x
t
,nodetype:type
t
,content
t
:ctnt,attr
t
(attr1*,attr2*,
…
,attrn*)}
[0112]
步骤5：首先使用ochiai缺陷定位工具得到一组按分数从高到底的可疑候选修复语句。根据候选修复语句的上下文找到变更池中的对应变更序列，对同一上下文中的变更系列进行三种相似性度量，计算变更集中每个衍化变更的相似度，根据相似度对变更进行排序，使得与原bug语句越相似的变更越早得到使用，如图4所示。
[0113]
步骤6：对步骤5的变更序列进行具体化产生具体候选补丁，具体化时采用三种具体化策略中的一种，产生候选补丁，如图5所示；具体为：
[0114]
步骤6-1：通过对本地项目的源码文件进行处理解析得到一个本地源码语料库的词库；
[0115]
步骤6-2：，对原始bug语句的标识符根据驼峰进行拆分重构，得到更多相似的标识符；
[0116]
步骤6-3：按照变更排名分数依次选取候选变更，并进行具体化产生候选补丁；
[0117]
具体为：
[0118]
步骤6-3-1：采用以下四种策略对标识符进行选择；
[0119]
①
度量同构词与标识符的相似性，相似性越高的标识的重用的优先级越高；
[0120]
②
在源项目中使用频率越高的标识符的优先级越高；
[0121]
③
结合前面两种策略，在频率相同的情况下，相似度越高的标识符越有可能被重用；
[0122]
步骤6-3-2：抽象变更根据步骤7-3-1选择的标识符进行具体化产生候选补丁；
[0123]
步骤7：对候选补丁并进行编译，触发测试、相关测试、全部测试的测试顺序，只有前面一级的测试通过了，才进行下面一级的测试，减少补丁验证的时间。重复前面的验证，直到找到一个通过所有测试的候选补丁或者验证超出时间限制。最后对似真补丁进行检查，是否与人工编写的补丁在语法和语义上是等价的。

技术特征：
1.一种基于变更衍化与标识重构的软件缺陷修复方法，其特征在于，该方法具体包括以下步骤：步骤1：从开源社区按照highest score、views、stars条件进行筛选提取到的高频历史变更以及变更对应的上下文；步骤2：识别变更的上下文，根据上下文，对变更池中的变更进行分类，把同一上下文的变更，放在同一变更集下；步骤3：将变更解析成抽象语法树，根据关键节点规则集识别语法树中的关键节点，关键节点规则集如下表，步骤4；对识别的关键节点根据衍化规则集对变更进行衍化，衍化规则集如下表示；将衍化得到的变更，建立与原始变更的属性联系，并加入到原始变更对应的上下文所在的变更集中；衍化变更的原节点node:node{id:x1,nodetype:type
s
,content:ctnt
s
,attr
s
(attr1,attr2,
…
,attr
n
)}衍化变更生成的新节点node
*
:node{id:x
t
,nodetype:type
t
,content
t
:ctnt,attr
t
(attr
1*
,attr
2*
,
…
,attr
n*
)}步骤5：对缺陷进行定位并识别缺陷的上下文，将可疑语句的上下文，与补丁池中的变更上下文进行比较，找到最佳配对的上下文；步骤6：对变更集通过度量相似性进行排序步骤6-1：根据抽象语法树的节点类型计算原始泛化的bug语句与变更集中变更的相似性分数
其中k表示原bug语句与变更集的抽象语法树类型总数，tns(i)表示原bug语句的节点类型，tnt(i)表示变更集中变更的节点类型；步骤6-2：计算原始泛化的bug语句与变更集中变更的最长公共子序列计算相似性其中lss是原始变更的公共子序列，lst演化变更的公共子序列步骤6-3：根据衍化变更对原始变更的修改大小进行计算被修复的大小,由于原始变更为本身，所以它具有最高的分数其中mfs是原始变更的子序列，mft演化变更的子序列步骤6-4：对前面6-1、6-2、6-3计算的相似性得分进行归一化，然后计算最终的相似性得分，即变更排名分数；simi(ns,nt)＝f(tns,tnt)*f(lss,lst)*f(mfs,mft)步骤6-5：根据6-4计算的最终相似性对变更集进行排序rank_change
context
＝{change
s
,change1,change2,
…
,change
n
}；其中change
s
,表示原始的变更；步骤7：对抽象变更进行具体化产生候选补丁步骤7-1：通过对本地项目的源码文件进行处理解析得到一个本地源码语料库的词库；步骤7-2：，对原始bug语句的标识符根据驼峰进行拆分重构，得到更多相似的标识符；步骤7-3：按照变更排名分数依次选取候选变更，并进行具体化产生候选补丁；具体为：步骤7-3-1：采用以下四种策略对标识符进行选择；
①
度量同构词与标识符的相似性，相似性越高的标识的重用的优先级越高；
②
在源项目中使用频率越高的标识符的优先级越高；
③
结合前面两种策略，在频率相同的情况下，相似度越高的标识符越有可能被重用；步骤7-3-2：抽象变更根据步骤7-3-1选择的标识符进行具体化产生候选补丁；步骤8、验证候选补丁。2.根据权利要求1所述的一种基于变更衍化与标识重构的软件缺陷修复方法，其特征在于：所述的识别变更的上下文，根据上下文，对变更池中的变更进行分类，具体为：步骤2-1：对于上下文的定义，沿用已有的方法(kim et al)；通过定义节点类型和节点散列来表示上下文，其中节点类型可以表示抽象的上下文类型，节点哈希表示更独特上下文类；步骤2-2：节点类型定义假设r是变更子树的根节点，在r的上下文中使用的节点a的节点类型type(r,a)来表示上下文，其中type(r,a)的定义如下：
其中a.loc是a的语法位置；步骤2-3：节点散列定义假设节点a为例子：hash(a)＝{a.type{h(c1)，h(c2)，
…
，h(c
k
)}}其中c1,c2,
…
,c
k
是节点n的孩子节点步骤2-3：由节点类型和节点散列组成上下文表示上下文ctx是由三个组件c
p
，c
l
，c
r
组成；让c成为一个变更的根节点，具有一组节点s的每个组件c
s
是由节点n的节点类型t(n,c)或者节点散列h(n)串联组成；上下文的组成形式如下：ctx＝p：c
p
，l：c
l
，r：c
r
按照上下文，对变更池中的变更进行分类，把相同上下文的变更加入到同一变更序列，同时对同一上下文中的变更依据频率进行排序，得到一个分类良好的变更池。3.根据权利要求1所述的一种基于变更衍化与标识重构的软件缺陷修复方法，其特征在于：所述的对缺陷进行定位使用ochiai缺陷定位方法。4.根据权利要求1所述的一种基于变更衍化与标识重构的软件缺陷修复方法，其特征在于：所述的对缺陷进行定位具体为：用ochiai缺陷定位工具对缺陷进行定位，得到可疑分数从高到底的可疑语句排列，按顺序选取可疑语句。5.根据权利要求1所述的一种基于变更衍化与标识重构的软件缺陷修复方法，其特征在于：所述的级联验证，具体为：1)首先对候选补丁进行编译；2)如果编译通过则进行触发测试；3)如果触发测试通过则运行相关测试；4)如果相关测试通过则运行全部的测试；通过全部测试的补丁由于过拟合问题仍然可能不正确，需要进行人工检查，如果候选补丁在语法和语义上等价于人工补丁，则认为该补丁是一个正确的补丁。

技术总结
本发明公开了一种基于变更衍化与标识重构的软件缺陷修复方法，本发明通过对使用频率比较高的变更进行衍化，生成更多相似的变更，同时丢弃掉那些几乎用不到的变更，在变更收集阶段大大减少变更的收集数量，同时通过度量变更与bug语句的相似度加速变更的检索过程，减少寻找对应修复模板的时间。本发明不仅仅使用从源项目文件中收集到的变量、字段、字面量等，还对其中以驼峰命名的标识符按驼峰进行拆分，同时对拆分后的子标识进行重构，得到新的标识符，不仅增加具体化抽象变更时，标识符的选择数，而且在一定程度上减小了候选补丁与正确补丁的距离。丁的距离。丁的距离。


技术研发人员：王兴起 秦辉亮 魏丹 方景龙 陈滨 吴启凯
受保护的技术使用者：杭州电子科技大学
技术研发日：2023.03.03
技术公布日：2023/7/22