基于条件概率模型的缺陷定位方法-舒挺 , 黄明献 , 丁佐华 , 王磊 , 夏劲松.pdf

上善若水

113

14页

0次

2022-05-19

免费下载

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

Journal of Software,2018,29(6):1756−1769 [doi: 10.13328/j.cnki.jos.005287] http://www.jos.org.cn

基于条件概率模型的缺陷定位方法

∗

舒

挺

黄明献

丁佐华

王

磊

夏劲松

(浙江理工大学信息学院,浙江杭州 310018)

通讯作者: 舒挺, E-mail: shuting@zstu.edu.cn

摘要: 缺陷定位是软件调试的重要阶段,依赖程序频谱信息实现软件缺陷定位,是当前比较行之有效的方法.基

于频谱缺陷定位方法应用的前提是,程序频谱和执行结果之间存在的潜在关联.通过经验性分析两者之间的内在关

联,借助于统计学的条件概率思想,构建了用以量化分析两者关系强弱的 P 模型,并基于此提出了基于条件概率的缺

陷定位方法.以 Siemens 套件中的 7 个程序、Space 程序和 3 个 Unix 工具程序为基准评测对象,与已有的 15 种经典

缺陷定位方法进行了对比实验.实证研究结果表明,该方法总体上具有更好的缺陷定位效果.

关键词: 缺陷定位;程序频谱;条件概率;软件调试;测试例

中图法分类号: TP311

中文引用格式: 舒挺,黄明献,丁佐华,王磊,夏劲松.基于条件概率模型的缺陷定位方法.软件学报,2018,29(6):1756−1769. http:

//www.jos.org .cn/1000-9825 /5287.ht m

英文引用格式: Shu T, Huang MX, Ding ZH, Wang L, Xia JS. Fault localization method based on conditional probability model.

Ruan Jian Xue Bao/Journal of Software, 2018,29(6):1756−1769 (in Chinese). http://www.jos.org.cn/1000-9825/5287.htm

Fault Localization Me thod Based on Conditiona l Probability Model

SHU Ting, HUANG Ming-Xian, DING Zuo-Hua, WANG Lei, XIA Jin-Song

(School of Information Science and Technology, Zh ejiang Sci-Tech Univ ersity, Hangzhou 310018, Chin a)

Abstra ct : Fault localization is an essential step of software debugging, and spectrum-based fault localization (SFL) is currently amongst

the most effective methods. The fundamental premise u nderlying SFL is that there exists a potenti al relationship between program spectra

and the corresponding execution r esults. To formally describe and accurately quantify this relation, this p aper introduces the conception of

conditional probability to construct a P model by using the statisti cal analysis of experimental d ata. In addition, based on the presented P

model, a fault localization method is proposed to effectively locate the faulty statement of the program under test. Finally, taking seven

programs contained in the Si emens suite, Sp ace program and three real-life Unix utili ty programs as the ben chmark, a detailed experiment

is conducted to evaluate the effectiveness and efficiency of the proposed method. Compared with fift een classic fault localization methods,

the experimental results show that the presented approach is mor e promising.

Key words: fault localization; program sp ectrum; conditional prob abilit y; software d ebugging; test case

软件规模和复杂程度的与日俱增,给软件开发和调试技术带来了极大的挑战.面对软件开发过程中如影相

随的程序缺陷问题,软件测试成为了提升其质量和可靠性的重要技术手段.因此,人们在软件测试方面的投入逐

年增加.在软件测试过程中,当发生被测软件的行为与预期不一致(即失效)时,开发人员就需要随即开展软件调

试

[1]

.软件调试的首要任务是缺陷定位,它为后续错误代码修复工作提供了基础.

∗ 基金项目: 国家自然科学基金(61101111, 61572441); 浙江省自然科学基金(LY17F020033)

Foundation item: National Natural Science Foundation of China (61101111, 61572441); Natural Science Foundation of Zhejiang

Province (LY17F020033)

收稿时间:

2016-12-13; 修改时间: 2017-01-07, 2017-02-18; 采用时间: 2017-03-20; jos 在线出版时间: 2017-07-12

CNKI 网络优先出版: 2017-07-12 15:33:41, http://kns.cnki.net/kcms/d etail/11.2560.TP.20170712.1533.007.html

舒挺等:一种基于条件概率模型的缺陷定位方法

1757

缺陷定位旨在探测和查找引起软件失效的错误代码,是非常枯燥和耗时的活动.传统的手工设置断点的调

试方法,不仅断点位置选择困难,且时间开销巨大.因此,实现缺陷定位的自动化成为了软件学术界和工业界共

同追求的目标.近些年来,研究人员从不同的角度尝试提出了一系列辅助自动化缺陷定位的方法,包括基于切片

的方法

[2−4]

、基于程序不变量的方法

[5,6]

、模型检验方法

[7]

和基于程序频谱的方法

[8−12]

等.基于切片的缺陷定位

方法主要通过对程序的静态或动态分析,找出与给定变量相关联的语句,从而缩小错误查找范围.基于不变量的

方法则通过利用成功和失效测试执行中程序不变量之间的差异信息,辅助定位错误语句.模型检验方法则依赖

失效程序行为与期望模型行为的冲突来推导程序错误.相比而言,基于频谱的缺陷定位方法(spectrum- based

fault localization,简称 SFL)由于具有不需要考虑程序本身内部结构和执行开销小的特点,成为了一类比较行之

有效的重要方法.

程序频谱通常指程序运行时代码覆盖信息的集合,是程序动态行为特征的一种描述形式

[13]

.由于程序运行

失效时必定执行到了某条错误语句

[14]

,据此可以得出经验性的推断:当某条语句被更多的失效执行所覆盖,那么

它为错误语句的可能性就越高.因此,通过收集程序的频谱和执行结果两方面的信息来推导出程序缺陷位置成

为了可能.具体的,SFL 方法主要通过对比分析被测程序在成功执行和失效执行的程序频谱信息,构造相应的可

疑度计算公式来估测程序实体(如语句、谓词等)出错的可能性.最终,调试人员将程序实体按照可疑度大小降序

逐一排查错误.因此,可疑度值辅助缺陷定位的精确程度成为了衡量 SFL 方法优劣的主要性能指标.

通常,依赖基准测试对象(如 Siemens 套件和 Space 程序等)进行实验对比,是评价现有 SFL 方法的主要途径.

作为实验分析方法的补充,Naish 等人

[15]

首次基于模型和实验结合的评价方法来分类可疑度计算公式,并提出

了其实验环境条件下的 2 个最优化公式 Op1 和 Op 2. 随后,谢晓园

[13]

和 Tsong

[16]

等人在特定的假设条件下提出

了一套理论框架用以评价可疑度计算公式的优劣.然而,Shin 等人

[17]

通过理论分析已经证明,不存在绝对最优的

可疑度计算公式.针对特定的测试上下文,如错误类型和程序结构等,已有的各种方法各具优势.

程序频谱和执行结果之间存在的潜在关联是可疑度计算公式构造的基础.显然,充分地挖掘和利用这种潜

在关联蕴含的缺陷揭示信息,有助于提升可疑度计算公式缺陷定位的效用.本文通过经验性研究程序频谱和执

行结果两者之间的内在关联,引入统计学的条件概率思想,构建了用以评估两者关系强弱的量化模型.针对一些

经典的 SFL 方法,依赖提出的条件概率 P 模型来分析具体的可疑度计算公式,从而探究其缺陷定位精度和效率

差异的本质原因.基于此,提出了一种基于条件概率的缺陷定位新方法.为了验证新方法的有效性,实证研究以

Siemens 套件中的 7 个程序、Space 程序以及 3 个 Unix 工具程序为基准评测对象,与已有的 15 种经典缺陷定

位方法进行了对比实验.测试结果表明,新方法在缺陷定位效果上具有一定优势.

1 相关工作

在以往的研究中,人们已经提出了多种基于频谱的软件缺陷定位方法.Jones 等人

[9]

认为:被更多的失效测试

执行覆盖到的语句,是缺陷语句的可能性就越大.基于该前提,他们首次应用程序频谱来构造可疑度计算公式

Tarantula,从而辅助软件缺陷定位.Tarantula 公式中定义了 4 类因子用以描述语句频谱和执行结果之间的关系:

表示某条语句在失效测试中覆盖到的次数;a

表示某条语句在成功测试中覆盖到的次数;a

表示某条语句

在成功测试中未被覆盖到的次数;a

表示某条语句在失效测试中未被覆盖到的次数.后续提出的频谱方法基本

都沿用了这 4 个因子的定义.

Abreu 等人

[18]

随后受到分子生物学基因相似度公式和聚类分析思想的启发,分别提出了 Ochiai 和 Jaccard

[8]

方法.实证研究表明,Ochiai 和 Jaccard 的缺陷定位效果要优于 Tarantula.Wong 等人

[12]

认为:程序语句在测试例中

的执行轨迹具有模式可循,可以通过分析失效测试例中语句执行轨迹之间的相似信息来辅助缺陷定位.于是,他

们扩展了 Kulczy nski

[19]

频谱公式,提出了 Dstar 方法.Dstar 的缺陷定位效果要优于之前提出的 Tarantula,Ochiai

等一些经典的频谱公式.张震宇等人

[20]

提出了一种基于语句块链 KBC 和降噪规则的缺陷定位新框架.实验结果

表明,新框架可以整合到已有的方法提高其缺陷定位效果.丁晖等人

[11]

则将信息量的相关知识引入到程序频谱

中,提出了一种基于信息量的缺陷定位方法 SIQ.该方法应用事件信息量来降低测试数据集差异带来的缺陷定

of 14

免费下载

软件学报计算机技术

关注

评论