空指针引用缺陷分类假阳性识别方法

王曙燕,权雅菲,孙家泽

(西安邮电大学 计算机学院,西安 710061) (*通信作者电子邮箱wsylxj@126.com)

空指针引用缺陷分类假阳性识别方法

王曙燕*,权雅菲,孙家泽

(西安邮电大学 计算机学院,西安 710061) (*通信作者电子邮箱wsylxj@126.com)

针对静态测试中空指针引用缺陷假阳性问题,提出一种空指针引用缺陷分类假阳性识别方法。挖掘空指针引用缺陷知识,对空指针引用缺陷知识进行预处理,生成空指针引用缺陷数据集;通过基于粗糙集理论属性重要性的ID3算法分类空指针引用缺陷数据集,分类结果有假阳性空指针引用缺陷实例和真实空指针引用缺陷实例两种;根据分类结果对静态测试中的空指针引用缺陷进行假阳性识别,确认真实的空指针引用缺陷。该方法对十个基准程序和基于主流静态测试工具FindBugs的空指针引用缺陷检测方法相比,空指针引用缺陷假阳性降低率平均为25%,减少了24%的空指针引用缺陷确认。实验结果表明,该方法在静态测试方面能有效降低缺陷确认开销,提高空指针引用缺陷检测效率和稳定性。

静态测试;空指针引用缺陷;假阳性识别;缺陷分类;缺陷确认

0 引言

软件缺陷由不合理的设计和软件开发人员的疏忽引起[1-2],软件缺陷导致软件运行时失效,软件缺陷频发会带来极大危害。面向代码缺陷的软件静态测试技术正逐渐受到软件业界的青睐[3],包括静态缺陷检测和缺陷确认两个阶段。当前软件行业越来越依赖自动化缺陷检测工具检测软件缺陷[4],自动化缺陷检测工具在静态缺陷检测效率方面很有优势,但会报告大量缺陷,而验证这些缺陷的正确性时主要的缺陷确认工作仍由人工完成[5],高耗时耗力的缺陷审查工作会降低该工具在软件开发流程中的可用性。静态测试优化技术试图在静态缺陷检测工具运行后进行缺陷报告优化,降低缺陷确认负担,从另一个角度提升工具的检测效率和精度[5]。

据中国国家信息安全漏洞库统计,由空指针引用(Null Pointer Dereference, NPD)缺陷造成的安全漏洞引发了许多严重的安全问题。目前的缺陷检测方法有动态检测和静态检测、动态检测输入样例很难构造；静态检测则在代码覆盖率方面有优势,检测缺陷时更有针对性。所以,基于NPD缺陷知识在静态测试后进行NPD缺陷假阳性识别,能有效降低缺陷确认开销,进而提升软件测试整体效率。

在现有的静态缺陷检测方法中,Zhang等[6]通过分析缺陷报告优化缺陷检测结果,但未考虑噪声报告对优化结果的影响。梁广泰等[7]挖掘受检程序中的新缺陷模式并以“缺陷模式描述模板”半自动扩充原缺陷模式库,扩充静态测试工具NPD缺陷检测能力,但未考虑到分析技术和规则挖掘技术对缺陷检测的影响。杨睿等[8]结合空指针故障模型和控制流图进行数据流分析,根据分析结果尽可能多地识别出那些可能不是缺陷的项来降低空指针故障误报率,但忽略了区间运算和函数摘要的计算能力。

针对上述问题,张大林等[5]通过缺陷关联分析分组静态测试工具报告的缺陷,若组内主导NPD缺陷被证是误报,其他NPD缺陷也是误报,能有效降低缺陷确认负担;但分组缺陷时缺陷关联抽象域计算能力的不足,会导致关联误报。

因此,针对静态测试中的假阳性NPD缺陷,本文研究采用基于粗糙集理论属性重要性的ID3(ID3 Based Rough Set, RSID3)算法结合NPD缺陷知识进行NPD缺陷假阳性识别,挖掘静态缺陷报告与软件历史仓库中代码修改中的NPD缺陷知识,预处理后生成NPD缺陷数据集,通过RSID3分类NPD缺陷实例,避免了分组缺陷时缺陷关联的抽象域计算,根据分类结果识别假阳性NPD缺陷,以期快速确认真实NPD缺陷。

1 静态测试NPD缺陷检测技术

1.1 NPD静态检测

静态测试不执行程序从语法或语义层面分析程序文本,推导其语法或语义性质进行潜在缺陷检测,30%～ 70% 的代码逻辑设计和编码缺陷能通过静态测试检测并修复。基于缺陷模式的软件测试技术[9]将代码中已有缺陷总结成缺陷模式,在静态测试过程中通过模式匹配算法判断待测程序中是否存在匹配缺陷模式的代码段,对受检代码进行缺陷检测。

NPD缺陷在程序运行时发生,编译阶段无法发现,动态测试方法难以达到全面覆盖的效果。若先进行空指针静态检测来查找程序中所有可能为空的对象,能弥补动态测试无法检测程序中不确定执行路径的NPD缺陷的不足。使用静态测试方法检测NPD缺陷是近年来NPD检测方法研究的重点[8]。

1.2 基本概念

定义1 NPD缺陷假阳性。NPD缺陷检测可转为求解问题D={P,M,A}, 其中：p是待测程序；M是与P对应的NPD缺陷模式集；A={ρ(L,X),ψ,R}是NPD缺陷检测算法,ρ是P执行到L处变量X取值信息,ψ是P执行到L处实时堆栈中被调方法摘要信息,R是P中所有可达路径。通过静态测试方法检测NPD缺陷时,需分析p中所有可达路径上出现的指针引用的相关指针在运行时的指向状态,则NPD缺陷假阳性为:

∃x,x∈{ρ(L,X)|R}∧～D={P,M,A} ⟹FP(X)

其中:～D={P,M,A}指变量X取值为x时不会引发NPD缺陷；FP(X)是X引发NPD缺陷的假阳性现象。

2 NPD缺陷分类假阳性识别方法

2.1 NPD缺陷数据集生成

如何利用已有缺陷知识确认程序潜在缺陷是静态缺陷检测的关键[10]。Zhang等[6]通过分析缺陷报告快速确认真实缺陷;Kim等[10]提出挖掘软件修改历史能快速识别出真正的缺陷代码。所以,本文挖掘静态缺陷报告与软件代码修改历史中的NPD缺陷知识,基于NPD缺陷知识生成NPD缺陷数据集,对其分类后进行NPD缺陷假阳性识别。

静态缺陷报告用元素标记描述数据,所有元素都有文本属性和离散属性,以开始标记和结束标记限定元素描述缺陷内容的范围,解析包含NPD缺陷内容的元素属性,提取属性及属性值作为缺陷报告中的NPD缺陷知识。分析软件历史仓库中的版本控制系统,提取所有代码修改,修改日志含有多条记录,每条记录包含修复NPD缺陷相关属性,通过从修改日志匹配修复NPD缺陷的关键词,能从所有代码修改中识别出修复NPD缺陷的代码修改,通过分析源程序中引发NPD缺陷的程序点L处第1次到第n-1次代码修改历史,从修复NPD缺陷的第n次代码修改的修改日志中提取修复NPD缺陷记录,提取上述记录的属性及属性值作为软件历史中仓库代码修改中的NPD缺陷知识。

缺陷模式有助于快速识别程序中的缺陷,程序P对应M中的NPD缺陷模式[11]用有限状态机表示为:

MNPD=〈S,T,C〉

(1)

其中:S={Sstart,Snot,Spossible,Snpddefect,Send}是可达状态集;Sstart是始态;Snot是非空状态;Spossible是可能为空状态;Snpddefect是引发NPD缺陷时的状态,与NPD缺陷模式有关;Send是末态;T={〈ni,nj〉|ni,nj∈S}是状态迁移集,指从状态ni迁移到状态nj,T:S×C→S,C是迁移条件,引发NPD缺陷是指对象O从Sstart经一系列状态迁移到达Snpddefect。

通过式(1)形式化描述特定模式的NPD缺陷,根据程序P中引发NPD缺陷的程序点L处指针的指向状态,包括空、可能为空和非空三种,前两种指向状态与引发NPD缺陷有关。对每个被引用指针构造MNPD实例,MNPD实例状态迁移如图1所示,图1中的NPD缺陷状态迁移关系如表1所示。在MNPD上进行状态迁移时需分析L处程序状态信息ρ和ψ,根据引发NPD缺陷的对象O在MNPD上迁移过程得到NPD缺陷模式集:

图1 NPD缺陷有限状态机实例状态迁移图

如图1所示,给定状态集S={t1,t2,t3,t4,t5},t1至t5依次代表状态Sstart、Snot、Spossible、Snpddefect、Send,通过表1 NPD缺陷状态迁移集描述各NPD缺陷模式,其T和C结合上述程序状态信息分析设定。

表1 NPD缺陷状态迁移集

从表1可知，引发NPD缺陷的对象O到达Snpddefect的状态迁移不同,识别各NPD缺陷模式下的NPD缺陷需要满足的条件,即NPD缺陷引发条件DCNPD不同,根据表1中的T和C提取NPD缺陷模式集中各模式对应的DCNPD,则

DCNPD=(Vlocal=nullMay)‖(Vglobal=nullMay)‖

(FPfunction=nullMay)‖(APfunction=null)‖

(RVmethod=nullMay)

经上述预处理, 通过NPD缺陷模式提取NPD缺陷引发条件后, 对比NPD缺陷知识与NPD缺陷引发条件,确定一组包含NPD缺陷引发条件的属性,即NPD缺陷关联属性组(type, priority, role, category, is-fixed, is-true),各属性依次指定NPD缺陷引发原因、优先级、引发条件、类别、是否修复、真实性,其一组取值为一个NPD缺陷实例,一个NPD缺陷实例对应P在静态测试中报告的某个NPD缺陷,累积P中所有NPD缺陷实例,以NPD缺陷关联属性和NPD缺陷实例为基本分量,构造描述NPD缺陷关联属性间关系的NPD缺陷数据集,作为RSID3算法的输入。

2.2 基于粗糙集理论属性重要性的ID3算法

提高ID3算法分类精度的关键在于划分属性的选择。划分NPD缺陷数据集时,很难根据经验选择当前NPD缺陷数据集的划分属性，且划分属性选择存在多值偏向,本文提出的RSID3通过考虑属性ai∈A对划分属性的重要性[12]来指导划分属性选择。首先,调整当前划分属性Ak对当前属性集A的依赖度k(A,Ak);然后,确定所有属性ai∈A对Ak的重要性γ(A);最后,在寻找信息增益最大的属性时,通过遍历为T和A建立的索引数组,基于索引搜索A中信息增益最大的属性作为当前划分属性,作用于RSID3算法输入。信息增益方程为:

Gain(A)=I(s1,s2,…,sm)-

1)若k(A,Ak)=0时,则认为Ak完全不依赖于A;

2)若0lt;k(A,Ak)lt;1时,则认为Ak部分依赖于A;

3)若k(A,Ak)=1时,Ak完全依赖于A。

通过k(A,Ak)的调整方案自适应调整γ(ai),确定γ(A):

k(A,Ak)-k(A-{ai},Ak)

其中:R=C∪Ak。

2.3 实例分析

下面通过例子来进一步阐述RSID3算法的划分属性选择过程和效果。下述程序片段展示了静态测试工具在检测Java开源项目Weka-3-6时报告的两个NPD缺陷,分别为：第192行变量contents.length可能为空指针并在192行解引用;第193行contents[i]可能为空指针并在193行解引用。

190: public static void loadProperties() {

191: File[] contents= piuginDir.listFiles();

192: for(int i=0;ilt;contents.length;i++){

193: if(contents[i].isDirectory()amp;amp;contents[i].listFiles().

lengthgt;0){…

202: File anyJars[]=contents[i].listFiles();

228:…}}}

根据2.1节内容对示例代码段的完整文件报告的所有NPD缺陷生成NPD缺陷数据集,如表2所示,以二维表格式展示。

从表2可知,属性集A={a1,a2,a3,a4,a5},Card(T)=3,d为初始划分属性,则Ak={d},从任意属性a3开始, 首先计算d对A的依赖度,显然0lt;k(A,d)=0.67lt;1,d部分依赖于A,其中,posA(d)={1,2};然后计算a3对d的重要性γ(a3,A,d)=0.33,即将a3从A中去除后被分类错误的概率。同理γ(a5)=0.26,γ(ai)值越大表示ai对A分类质量影响越大,应优先挑选,所以选择划分属性时优先考虑a3。

2.4 NPD缺陷分类假阳性识别模型

NPD缺陷分类假阳性识别模型分为缺陷报告、NPD缺陷数据集生成和假阳性识别三个模块,如图2所示。

图2中:缺陷报告模块是模型基础,用于生成静态缺陷报告;NPD缺陷数据集生成是核心模块,解析缺陷报告,挖掘解析后的缺陷报告与软件历史仓库代码修改中的NPD缺陷知识,预处理NPD缺陷知识,确定NPD缺陷关联属性组,结合其取值构造NPD缺陷数据集;假阳性识别模块在模型中起桥梁作用,通过接收NPD缺陷数据集分类NPD缺陷实例,分类结果有真实NPD缺陷实例和假阳性NPD缺陷实例两种,根据分类结果进行NPD缺陷假阳性识别,输出真实NPD缺陷并评估NPD缺陷确认效率。

表2 NPD缺陷数据集

图2 NPD缺陷分类假阳性识别模型

2.5 算法步骤

假设含有NPD缺陷程序P的NPD缺陷数据集为T,候选属性集为A,NPD缺陷分类模型为Mtree,基于RSID3算法的NPD缺陷分类假阳性识别方法的步骤如下。

输入 含有NPD缺陷程序P的NPD缺陷数据集T,候选属性集A,即Generate_model(T,A)。

输出 NPD缺陷分类模型Mtree。

步骤1 分别为T和A建立索引数组,利用式(2)计算A中所有属性信息增益,创建初始节点N。

步骤2 通过索引数组遍历T和A,如果T∈同类C,则返回N为叶子,标记为类C,转步骤6。

步骤3 从任意Ai开始遍历其索引数组,搜索当前信息增益最大的属性索引,确定该索引指向的属性为当前划分属性,记N为Ak,删除该索引并更新索引数组。

步骤4 将T按Ak划分, 对每个Ak的取值ai,由N长出分枝Ak=ai,在Ak处取值相同的实例归为同一子集Si。

步骤5 如果Si=null,则转步骤2;否则，对Si递归调用Generate_model(Si,A)生成Si上的决策树，转步骤3,自顶向下递归划分。

步骤6 算法结束,输出NPD缺陷分类模型Mtree。

3 实验与分析

3.1 实验设置

为验证本文方法的有效性,选取10个典型的开源Java项目[8]为基准程序进行静态NPD缺陷检测对比实验来验证本文方法的有效性,其中后5个Java项目为MegaMek项目连续版本,上述开源项目文档规范且得到持续维护,其相关信息如表3所示。

表3 基准程序相关信息

在实验过程中,通过FindBugs-3.0.1工具生成静态测试缺陷报告,ant_1.8.2工具获取静态测试缺陷报告,NPD缺陷数据集为.arff格式,所有程序均用Java语言编写,使用jdk-1.7.0_06,Windows 7,计算机主频为2.00 GHz,内存2 GB。

3.2 实验结果

基于以上实验设置,选择基于目前代表性静态测试工具FindBugs[3]的静态NPD缺陷检测方法和本文方法进行对比,在相同条件下对基准程序进行静态NPD缺陷检测,记录不同方法的报告的总缺陷、耗时和NPD缺陷数,NPD缺陷假阳性降低率为通过本文方法识别出的假阳性NPD缺陷在FindBugs报告的全部NPD缺陷中的比例,是衡量静态测试方法有效性的重要指标[8],实验结果如表4所示。

表4 不同方法检测NPD缺陷结果对比

对表4的10个基准程序进行缺陷检测,FindBugs共报告1 909个缺陷,466个NPD缺陷,而本文方法共报告1 800个缺陷,357个NPD缺陷,在NPD缺陷分类假阳性识别过程中其假阳性降低率平均为25%,最高为35.5%，且在MegaMek连续版本中稳定在35%,通过本文方法减少NPD缺陷确认共109个,有效减少24%的NPD缺陷确认工作,假阳性NPD缺陷识别效果好,降低了缺陷确认开销,提高了静态NPD缺陷检测效率。在表4中,以Weka-3-6为例,在不同项目中通过本文方法最高可以减少(32-24)/32×100%=25%的假阳性NPD缺陷;对于Jstock报告的NPD缺陷基数较小,NPD缺陷变化不大。对于MegaMek0.32.2,因其丢失其类信息造成部分源文件编译不能通过,使生成的中间代码不全导致其NPD缺陷假阳性降低率较低。通过表4求得两种方法检测时间标准差分别为32.70和22.19,检测的NPD缺陷标准差分别为23.21和19.74,说明本文方法稳定性更好。

缺陷确认效率可以反映静态测试方法的有效性,从降低的缺陷确认数量可以间接估计该测试方法缺陷确认效率[5],将NPD缺陷确认效率近似为除不需要再进行确认的NPD缺陷,其余缺陷占FindBugs报告的全部缺陷的比例,比较各方法对基准程序静态测试后的NPD缺陷确认效率如图3所示,本文方法在NPD缺陷确认效率方面优势明显且在MegaMek连续版本中NPD缺陷确认效率更稳定。

图3 各方法检测NPD缺陷在基准程序上的缺陷确认效率

所以,对于基准程序,本文提出的NPD分类假阳性识别方法在充分利用静态缺陷报告与软件历史仓库中代码修改中的NPD缺陷知识的基础上结合数据挖掘分类算法,以较小的代价更稳定地进行缺陷确认,提高了NPD缺陷检测效率。

4 结语

在面向代码缺陷的静态测试NPD分类假阳性识别方法中,如何充分利用已有NPD缺陷知识快速确认真实NPD缺陷是提高NPD缺陷检测效率的关键。本文提出了一种空指针引用缺陷分类假阳性识别方法,该方法通过对多个基准程序进行测试并与基于主流静态测试工具FindBugs的NPD缺陷检测方法进行比较,实验结果表明,本文方法有效降低了静态测试缺陷确认开销,在NPD缺陷检测效率和稳定性上都有明显提高。

在NPD缺陷分类假阳性识别过程中,基于软件静态缺陷报告与软件历史仓库代码修改中的NPD缺陷知识结合RSID3算法在缺陷确认之前先进行NPD缺陷假阳性识别,虽在一定程度上提高了静态NPD缺陷检测效率和稳定性,使缺陷确认开销降低,但对于实际中的复杂软件,检测软件NPD缺陷和缺陷确认所需缺陷关联知识的充分性仍需提高。

References)

[1] 陈翔, 顾庆, 刘望舒, 等.静态软件缺陷预测方法研究[J]. 软件学报, 2016, 27(1): 1-25. (CHEN X, GU Q, LIU W S, et al. Survey of static software defect prediction [J]. Journal of Software, 2016, 27(1): 1-25.)

[2] 李舟军, 张俊贤, 廖湘科, 等.软件安全漏洞检测技术[J]. 计算机学报, 2015, 38(4): 717-732. (LI Z J, ZHANG J X, LIAO X K, et al. Survey of software vulnerability detection techniques[J]. Chinese Journal of Computers, 2015, 38(4): 717-732.)

[3] 金大海, 宫云战, 杨朝红, 等.运行时异常对软件静态测试的影响研究[J]. 计算机学报, 2011, 34(6): 1090-1099. (JIN D H, GONG Y Z, YANG Z H, et al. Research on the effect of runtime exception in software static testing[J]. Chinese Journal of Computers, 2011, 34(6): 1090-1099.)

[4] DAS M, LERNER S, SEIGLE M. ESP: path-sensitive program verification in polynomial time[J]. ACM SIGPLAN Notices, 2002, 37(5): 57-68.

[5] 张大林, 金大海, 宫云战, 等.基于缺陷关联的静态分析优化[J]. 软件学报, 2014, 25(2): 386-399. (ZHANG D L, JIN D H, GONG Y Z, et al. Optimization static analysis based on defect correlations[J]. Journal of Software, 2014, 25(2): 386-399.)[6] ZHANG J, WANG X, HAO D, et al. A survey on bug-report analysis[J]. Science China Information Sciences, 2015, 58(2): 24-48.

[7] 梁广泰, 孟娜, 李进辉, 等.一个可半自动化扩展的静态代码缺陷分析工具[J]. 计算机学报, 2011, 34(6): 1114-1125. (LIANG G T, MENG N, LI J H, et al. A semi-automatic extensible static defect analysis tool[J]. Chinese Journal of Computers, 2011, 34(6): 1114-1125.)

[8] 杨睿, 金大海, 宫云战, 等.Java中空指针引用故障的静态检测方法[J]. 清华大学学报, 2011, 52 (增刊1): 1509-1514. (YANG R, JIN D H, GONG Y Z, et al. Static analysis method for detecting null pointer dereference in Java[J]. Journal of Tsinghua University, 2011, 52 (Supp1): 1509-1514.)

[9] QUINLAN D J, VUDUC R W, MISHERGHI G. Techniques for specifying bug pattern[C]// PADTAD 2007: Proceedings of the 2007 ACM Workshop on Parallel and Distributed Systems: Testing and Debugging. New York: ACM, 2007: 27-35.

[10] KIM S, WHITEHEAD E J, Jr, ZHANG Y, et al. Classifying software changes: clean or buggy?[J]. IEEE Transactions on Software Engineering, 2008, 34(2): 181-196.

[11] RUTER N, ALMAZAN C B, FOSTER J S. A comparison of bug finding tools for Java[C]// ISSRE 2004: Proceedings of the 15th International Symposium on Software Reliability Engineering. Piscataway, NJ: IEEE, 2004: 269-270.

[12] 韩松来, 张辉, 周华平, 等.决策树算法中多值偏向问题的理论分析[C]// 2005全国自动化新技术学术交流会论文集. 南京: 中国金属学会, 2005: 138-145. (HAN S L, ZHANG H, ZHOU H P, et al. Theoretical analysis for variety bias of decision tree algorithm[C]// Proceedings of the 2005 Chinese Symposium on New Technologies for Automation. Nanjing: Chinese Society of Metals, 2005: 138-145.)

[13] 朱颢东.ID3算法的改进和简化[J]. 上海交通大学学报, 2010, 44(7): 883-891. (ZHU H D. Research on improvement and simplification of ID3 algorithm[J]. Journal of Shanghai Jiaotong University, 2010, 44(7): 883-891.)

Falsepositiverecognitionmethodbasedonclassificationfornullpointerdereferencedefects

WANG Shuyan*, QUAN Yafei, SUN Jiaze

(SchoolofComputerScienceamp;Technology,Xi’anUniversityofPostsandTelecommunications,Xi’anShaanxi710061,China)

Focusing on the false positive problem of null pointer dereference (NPD) defect in static testing, a new false positive recognition method for null pointer reference defect based on classification was proposed. The knowledge of NPD defect was mined and preprocessed to generate data set of the defects. Then the data set of NPD defects was classified via ID3 classification algorithm based on rough set theory, and there were two kinds of classification results, one was false positive null pointer reference defect instances, the other was real null pointer reference defect instances. The real NPD defects were confirmed according to the classification results of the defect instances by recognizing the false positive NPD defects. The method was tested on ten benchmark programs and compared to the NPD defect detection method based on the mainstream static testing tool FindBugs, the false positive rate was reduced by 25%, and the confirmation amount was reduced by 24% for NPD defects. The experimental result shows that the proposed method can effectively reduce defect confirmation overhead and improve the detection efficiency and stability for NPD defects in static testing.

static testing; Null Pointer Dereference (NPD) defect; false positive recognition; defect classification; defect confirmation

2017- 04- 28;

2017- 06- 05。

陕西省工业攻关项目(2016GY-089);陕西省教育厅自然科学基金资助项目(15JK1672)。

王曙燕(1964—),女,河南南阳人,教授,博士,CCF会员,主要研究方向:软件测试、数据挖掘、智能信息处理; 权雅菲(1991—),女,陕西西安人,硕士研究生,主要研究方向:软件设计与测试、数据挖掘; 孙家泽(1980—),男,河南南阳人,副教授,博士,CCF会员,主要研究方向:软件测试、数据挖掘、智能信息处理。

1001- 9081(2017)10- 2968- 05

10.11772/j.issn.1001- 9081.2017.10.2968

TP311.5

A

This work is partially supported by the Industrial Research and Development Program of Shaanxi Province (2016GY-089), the Natural Science Foundation of the Ministry of Education of Shaanxi Province (15JK1672).

WANGShuyan, born in 1964, Ph. D., professor. Her research interests include software testing, data mining, intelligent information processing.

QUANYafei, born in 1991, M. S. candidate. Her research interests include software design and testing, data mining.

SUNJiaze, born in 1980, Ph. D., associate professor. His research interests include software testing, data mining, intelligent information processing.