自适应推导下的统一化调试加速技术-娄一翎，张令明，郝丹，张皓天，张路.pdf

上善若水

204

20页

0次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software, 2022,33(2):377396 [doi: 10.13328/j.cnki.jos.006347] http://www.jos.org.cn

自适应推导下的统一化调试加速技术



娄一翎

1,2

张令明

郝

丹

1,2

张皓天

张

路

1,2

(高可信软件技术教育部重点实验室(北京大学), 北京 100871)

(北京大学信息科学技术学院, 北京 100871)

(Department of Computer Science, University of Illinois at Urbana-Champaign, Illinois 61822, USA)

(蚂蚁金融服务集团, 浙江杭州 310099)

通信作者: 郝丹, E-mail: haodan@pku.edu.cn

摘要: 在传统调试过程中, 缺陷定位通常作为程序修复的前置步骤. 最近, 一种新型调试框架(统一化调试)被提

出. 不同于传统调试中缺陷定位和程序修复的单向连接方式, 统一化调试首次建立了定位与修复之间的双向连接

机制, 从而达到同时提升两个领域的效果. 作为首个统一化调试技术, ProFL 利用程序修复过程中伴随产生的大量

补丁执行信息逆向地提升已有缺陷定位技术的效果. 统一化调试技术不仅修复了可被修复的缺陷, 而且也为不能

被自动修复技术修复的缺陷提供了有效的调试线索. 虽然统一化调试是一个很有前景的研究方向, 但其在补丁验

证过程中涉及到了大量的测试用例执行(比如百万量级的测试执行), 因此时间开销问题严重. 提出一种针对于统

一化调试框架的加速技术(AUDE), 该技术通过减少对缺陷定位效果无提升的测试执行, 以提升统一化调试的效

率. 具体来说, AUDE 首先通过马尔可夫链蒙特卡洛采样方法构建补丁执行的初始序列, 随后在补丁执行过程中

将已执行的补丁信息作为反馈信息, 自适应性地估计每一个未执行补丁可能提供有效反馈信息的概率. 在广泛使

用的数据集 Defects4J 上对该技术进行了验证, 发现 AUDE 在显著加速 ProFL 的同时, 并没有降低其在缺陷定位和

程序修复的效果. 例如: 在减少了 ProFL 中 70.29%的测试执行的同时, AUDE 仍在 Top-1/Top-3/Top-5 指标上与

ProFL 保持了相同的定位效果.

关键词: 软件质量保障; 软件测试; 软件调试; 缺陷定位; 缺陷修复

中图法分类号

: TP311

中文引用格式: 娄一翎, 张令明, 郝丹, 张皓天, 张路. 自适应推导下的统一化调试加速技术. 软件学报, 2022, 33(2):

377–396. http://www.jos.org.cn/1000-9825/6347.ht m

英文引用格式: Lou YL, Zhang LM, Hao D, Zhang HT, Zhang L. Accelerating Unified Debugging via Adaptive Inference. Ruan

Jian Xue Bao/Journal of Software, 2022, 33(2): 377396 (in Chinese). http://www.jos.org.cn/1000-9825/6347.htm

Accelerating U nified Deb ugging via Adaptive Inference

LOU Yi-Ling

1,2

, ZHANG L ing- Ming

, HAO Dan

1,2

, ZHANG Hao-Tian

, ZHANG Lu

1,2

(Key Laboratory of High Confidence Software Technologies of Ministry of Education (Peking University), Beijing 100871, China)

(School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China)

(Department of Computer S cience, Universit y of I llinois at Urb ana-Cha mpaign, Illinois 61822, US A)

(Ant Financial Services Group, Hangzhou 310099, China)

Abstra ct : Fault localization and program repair techniques have been extensively studied for over decades; their only connection is that

fault localization serves as a supplier diagnosing potential buggy code for automated program repair. Recently, unified debugging has

been proposed to unify fault localization and program repair in the other direction for the first time to boost both areas. ProFL, the first

work on unified debugging, opens a new dimension that the large volume of patch execution information during program repair in turn

 基金项目: 国家重点研发计划(2017YFB1001803); 国家自然科学基金(61872008)

收稿时间: 2020-10-14; 修改时间: 2020-11-27, 2021-01-14; 采用时间: 2 021-04-12; jo s 在线出版时间: 2021 -05-20

378

软件学报 2022 年第 33 卷第 2 期

can help boost state-of-the-art f ault localization. Note th at even st ate-of-the-art program repair t echniques can only fix a s mall ratio of real

bugs (e.g., <20% for Defects4J) and simply abort for the vast majority of unfixed bugs. In contrast, unified debugging not only directly

fixes bugs when possible, but also provides debugging hints for bugs that cannot be automatically fixed (e.g., the patch execution

information from such unsuccessful repair can still help boost fault localization for manual repair). Although demonstrated to be a

promising direction, unified debugging relies on massive test executions (i.e., million test executions) and can cost hours for execution.

This work proposes AUDE to accelerate unified debugging by reducing test executions that provide little helpful feedback for improving

fault localization. Specifically, AUDE first constructs an initial execution order of patches guided by Markov ch ain Monte Carlo sampling

strategy, and then adaptively estimates th e likelihood of each patch being infor mative during patch execution on-th e-fly. The result s o n t he

widely-used Defejcts4J benchmark show that AUDE significantly accelerates ProFL by reducing 70.29% of test executions with

negligible effectiveness drop in both fault localization and program repair, e.g., AUDE can localize the same number of bug methods at

Top-1/ Top-3/Top-5 as ProFL.

Key words: software quality assurance; soft ware testing; software d ebugging; f ault lo calization; progr am r epair

软件缺陷(software bug)普遍存在于软件系统中, 而软件缺陷调试(deb uggi ng)往往代价巨大且具有挑战性.

因此, 为了降低软件缺陷调试过程中的人工代价, 软件缺陷自动调试领域受到了非常广泛的关注. 其中, 最主

要的两个核心问题就是缺陷定位和程序修复. 缺陷定位技术, 通过静态或者动态的程序分析技术来识别程序

中可能出错的代码元素. 比较常见的缺陷定位技术包括基于频谱

[110]

、基于变异

[1113]

和基于程序切片

[10]

等.

给定一个含有缺陷的程序, 缺陷定位技术通常会产生一个依照出错可能性(通常被称为可疑度)降序排序的程

序元素列表. 随后, 开发者可通过从头遍历该列表, 依次检查程序元素, 从而加速人工修复的过程. 程序自动

修复技术

[1426]

旨在没有人工干预的情况下, 自动化地修复程序中的缺陷. 通常来说, 程序自动修复技术往往

会先应用已有的缺陷定位技术来识别可能出错的代码元素, 然后在此基础上进行后续的补丁生成. 例如, 很

多近期的程序自动修复技术

[2729]

的第 1 步即是应用基于频谱的缺陷定位技术 Ochiai

[30]

来识别出错的代码元

素. 缺陷定位和程序修复这两个领域自提出以来已被研究了很多年, 在传统的调试场景下, 缺陷定位和程序

修复通常以这种单向的方式进行连接. 但是, 目前无论是缺陷定位还是程序修复技术在实际中都仍未得到广

泛的应用

[31,32]

: 已有的缺陷定位技术在实际中的效果表现仍然非常有限

[33,34]

, 而已有的程序自动修复技术只

能修复很小的一部分(在数据集上 Defects4J

[35]

不到 20%)真实缺陷

[2729,3 6,3 7]

或者某一类特定的程序缺陷

[34]

最近, 一种双向连接缺陷定位和程序修复的统一化调试方法

[31,32]

被提了出来. 作为首个统一化调试方法,

ProFL

[31,32]

利用了大量修复过程中产生的补丁执行信息来逆向提升已有缺陷定位技术的效果. 该技术不仅将

程序自动修复的适用范围拓展到了所有缺陷(不仅仅是原来小部分可以被自动修复技术成功解决的缺陷), 而

且也大幅度提升了已有缺陷定位技术的效果. 例如, ProFL 通过利用修复工具 PraPR

[27]

在修复过程中产生的补

丁信息, 不仅比主流的基于频谱和基于变异的缺陷定位技术至少多将 37.6%的缺陷代码元素排到可疑度列表

第一位, 而且在效果上也超越主流的基于学习的非监督和监督缺陷定位技术

[38,39]

虽然颇具前景, 但统一化调试方法中仍存在着不容忽视的效率问题. ProFL 工作提到了其中存在的效率问

题, 并且提出了只使用部分补丁执行矩阵信息来辅助提升缺陷定位的建议. 例如: 优先执行之前失败的测试

用例然后再执行之前通过的测试用例, 并且一旦有任意测试用例在当前补丁上执行失败就终止当前补丁的执

行. 尽管应用了上述效率优化策略, 但对于 Def ect s4J 中的大型项目(例如 Closure), ProFL 仍然要花费很多个小

时来收集必须的补丁执行信息

[31,32,4 0]

. 这个过程往往涉及到了百万级别的测试用例执行(值得注意的是: 对于

每一个补丁执行, 往往存在多个测试执行).

考虑到统一化调试所依赖的大量测试执行已成为其实际应用中的一大难题, 在本文中, 我们提出了一种

统一化调试加速技术, 旨在更好地平衡统一化调试的效率和效果. 我们的基本思想是: 在海量需要被执行的

补丁中, 存在着很多对提升缺陷定位没有帮助因此也没有必要被执行的补丁. 在本文中, 我们将这一类补丁

称为无信息性补丁. 相应地, 对于那些可以提供改善定位效果的反馈信息的补丁, 我们则称其为信息性补丁.

基于这一思想, 提出了 AUDE (accele rating unified debugging), 一种基于补丁是否具有信息性以优化补丁执行

的统一化调试加速技术. AUDE 主要分成两个部分, 包括初始优化和补丁执行过程中的自适应性推导: 在初始

of 20

免费下载

软件学报计算机技术

关注

评论