基于符号表达式的程序语义缺陷警报关联识别方法
2020-05-20王淑栋董玉坤陈红旗尹文静
王淑栋，刘 浩，董玉坤，陈红旗，张 莉，尹文静
(中国石油大学(华东)计算机科学与技术学院，青岛 266580)
静态分析技术是一种检测程序语义缺陷的有效技术，通过静态分析程序的语法与语义，并根据程序安全规则判断被测程序是否违反了程序安全属性[1-3]。目前，在静态测试领域，已经出现了一些相对成熟的工具，外国具有代表性的有Klocwork、PMD、Findbugs、Coverity等，中国有DTS(defect test system)[4-5]等静态缺陷检测工具。据统计，利用这些静态检测工具对程序编译与测试后，语义缺陷密度[6]大致是1个/KLOC[7]，这些存在的缺陷严重影响着软件质量，将直接导致程序运行时出现系统崩溃、运算结果异常、安全漏洞等情况。
由于静态分析技术对程序的非平凡属性分析不够精确，目前的静态分析工具与方法不可避免的会存在缺陷的漏报[8]与误报[9]。现有的静态分析工具漏报率为9%～32%，误报率为35%～91%[10]，这些检测出的真实缺陷和误报被称为警报。在图1中，函数f1第5行在没有进行判断指针p是否是空指针的情况下就直接进行了引用，会引起空指针解引用(null pointer dereference，NPD)警报；函数f1第6行在没有判断分母是否为0就进行了算术运算，引起非法计算操作(illegal arithmetic operand，IAO)警报。
随着软件的规模与复杂度递增式增长，静态检测工具报告的警报数量也急剧增加，这些检测出的警报需要警报判定人员逐一进行人工判定，大大降低了缺陷检测效率，也造成缺陷检测的成本大幅度增加，甚至已经导致软件开发和管理人员在软件开发过程中拒绝使用静态缺陷检测工具。
静态缺陷检测结果分析显示，大多数的警报与其他警报之间存在着关联关系。如图1所示，函数f1和函数f2分别报告了一个NPD警报，两处警报的触发原因都是因为在没有进行任何空指针判断的情况下就进行了变量引用，两处警报分别与变量p和变量q有关，两个变量引用了同一块内存地址，具有相同的符号表达式，表明这两个警报存在恒等关联关系。如果能够找到这些警报间的关联关系并对警报进行分组，在人工判定警报的时候，只需要对一组中的一个或几个警报进行判定，就可以大大缩短判定的时间。
图1 程序代码片段Fig.1 Program code fragment
关于警报关联[11]的相关技术已有大量报道。Lee等[12]提出一种基于静态分析的警报聚类的可靠方法，该方法首先判定一个警报的错误状态，然后通过观察这个错误状态的传播对其他警报的影响来判断警报间的关系。Zhang等[13]提出一种错误状态切片的警报关联方法，该方法首先在缺陷检测过程中去除警报的错误状态切片，同时生成一个新的状态切片作为外部约束，从而得到警报触发点的抽象求精语义，之后根据程序是否会触发警报进行关联计算。Heckman等[10]基于机器学习技术提出一种警报关联特征模型，利用该模型可以实现警报间的关联。该方法首先基于该模型构建评估框架，选取了警报的类型和代码位置等特征信息，并利用了15个机器学习算法建立警报关联模型。最后根据此模型对检测结果进行匹配，将具有相同特征的警报进行关联。以上大部分方法只对警报进行了简单的关联分析，并没有对警报关联的范围及准确性进行更深层次的深究。
鉴于上述现象，提出一种基于符号表达式的程序语义缺陷警报关联识别方法，使用该方法可以得到更高精度、可信度的警报关联关系，进而更多的减轻人工判定警报的工作量。研究的贡献可以概括如下。
(1)提出了一种警报关联识别方法，在缺陷检测阶段将检测出的每个警报由基于区域的符号化三值逻辑(region-based symbolic three valued logic，RSTVL)[14]的符号表达式表示，根据该警报的符号表达式与其他警报间的符号表达式的逻辑关系，总结得出恒等、非、或、与四种关联类型。
(2)不仅实现过程内警报关联，还通过符号化函数摘要实现过程间警报关联，进一步提高了识别警报关联的精度。
(3)实验验证了所提方法的有效性，减轻了人工判定警报的工作量，提高了人工判定警报工作的效率。
1 相关定义
一个程序P可以被表示为一个六元组P=
程序中警报的触发跟其变量的来源有着直接的关系，当该警报跟多个变量都有关系的时候，每一个变量的来源都可能对警报产生影响。
2 基于符号表达式的警报关联
2.1 符号表达式
采用基于区域的符号化三值逻辑(region-based symbolic three valued logic，RSTVL)来表示程序变量的抽象存储状态。
基于区域的符号化三值逻辑(RSTVL)定义为四元组，RSTVL=
定义8(符号表达式)符号表达式SExp由符号通过数学运算与关系操作构成，递归定义如式(1)所示：
(1)
式(1)中：符号表达式SExp由逻辑表达式RelExp通过关系操作构成；RelExp由数学表达式Exp通过逻辑操作构成；Exp由项Term通过加减运算组成；Term由多个因子Power通过乘除运算组成；每个Power由一个或多个原子Factor通过幂运算组成；原子Factor是符号表达式的最基本元素，它可以是一个数值常量Constant、符号变量Symbol或者符号表达式SExp。
董玉坤等[15]提出了符号化函数摘要，符号化函数摘要应用RSTVL描述符号化的函数摘要，将函数的行为通过符号化表示，在函数调用点基于过程内数据流分析的结果对函数摘要进行实例化，实现对调用点处抽象存储状态的更新，可实现过程间可靠的数据流分析，通过符号化函数摘要可以建立过程间警报关联。
每个警报可能存在n个相关变量，每个相关变量的符号表达式在程序生存周期内是唯一的，当其中任意两个相关变量的符号表达式不一致时，可以认定这是不同的相关变量。
例如在图1中，函数f1第5行在没有进行任何空指针判断的情况下进行了引用，在第7行调用函数f2将指针p的值传递过去，函数f2同样在没有进行任何空指针判断的情况下进行了引用。在第5行和第10行各报告了一个NPD警报，两个警报都对应着同一个取值区域，具有相同的符号表达式。
在程序点l上，∃Va,Vb,Vc∈Vl，Ω假定表示区间全集，假定VaExp、VbExp和VcExp分别表示变量Va、变量Vb和变量Vc对应的符号表达式，D[VaExp]、D[VbExp]、D[VcExp]分别表示变量Va、变量Vb和变量Vc对应的取值区间。
定义9(符号表达式的级数)符号表达式的级数(rank)表示符号表达式的复杂程度，根据符号表达式的个数将符号表达式分为n个级别，用符号ρ表示符号表达式的级数。假定单个符号表达式VaExp为1级，每增加一个逻辑运算符号或者符号表达式，相应的级数也增加1，例如符号表达式VaExp为2级，VaExp&&VbExp为3级，依次类推。
当变量间对应的符号表达式存在非、或、与三种关系时，其对应的取值区间运算存在以下规则。
非关系符号表达式的区间运算，如式(2)所示。
(2)
或关系符号表达式的区间运算，如式(3)所示：
(3)
与关系符号表达式的区间运算，如式(4)所示：
(4)
2.2 程序语义缺陷警报
将一类缺陷产生时程序所呈现的共同的语法或语义特征称为缺陷模式。常见的语义类缺陷模式包括空指针解引用(null pointer dereference，NPD)、数组越界(out of bound，OOB)、非法计算操作(illegal arithmetic operand，IAO)等类型。
程序中警报间具有相同的缺陷模式是警报关联的基础，两个警报只有属于同一个缺陷模式才可以进行关联；相反，如果两个警报来自不同的缺陷模式，即使警报的相关变量为同一个，也无法进行关联。
为了能够准确、全面地表示警报的数据信息，通过构建警报特征信息来进行描述。将警报特征信息定义为一个由结构信息、变量信息组成的二元组SV=
Struinfo表示警报的结构信息，由七元组Struinfo=
Varinfo表示警报的变量信息，由三元组Varinfo =
2.3 程序语义缺陷的警报关联推导规则
对于任意的两个警报am和an，假定ϑExp(am)表示警报am的相关变量对应的符号表达式，ϑExp(an)表示警报an的相关变量对应的符号表达式。如果警报间对应的符号表达式符合以下规则，则判定警报am和警报an存在关联关系。
警报与警报之间具有恒等、非、或、与等关联，这些关联信息是人工判定过程中警报确认的前提。
2.3.1 恒等关联
如果ϑExp(am)==ϑExp(an)，若警报am和an同为误报或真实缺陷，则警报am和an警报存在恒等关系。
2.3.2 非关联
如果ϑExp(am)==ϑExp(an)，若其中一个为误报，则另一个为真实缺陷，则警报am和警报an存在非关联关系。
2.3.3 或关联
如果ϑExp(am)==ϑExp(an)‖ϑExp(a)，其中ϑExp(a)表示任意警报对应的一个符号表达式，称警报am与警报an存在或关联关系。
2.3.4 与关联
如果ϑExp(am)==ϑExp(an)&&ϑExp(a)，其中ϑExp(a)表示任意警报对应的一个符号表达式，称警报am与警报an存在与关联关系。
假定存在警报a，与警报a存在关联的警报集合可以由四元组Corinfo=
3 程序语义缺陷的警报关联算法与实现
3.1 程序语义缺陷的警报关联算法
根据之前的警报关联推导规则，给出一个具体算法来计算警报关联，其警报关联算法如下。
算法1中输入为检测的全部警报；输出为警报与警报之间的关联关系。其中，Sw表示警报集合，Sr表示警报的级数集合，N表示警报的全部数量。
(1)首先判断所有警报对应的符号表达式的级数，然后按照警报的符号表达式级数从小到大进行排序，得出警报序列，接着人工判定符号表达式级数最小的警报。
(2)判定两个警报是否为同一类缺陷模式，若两个警报不属于同一类缺陷模式，则不存在任何关联，若两个警报属于同一类缺陷模式，再接着下一步。
(3)对警报集合中的警报进行两两比较，并将存在关联关系的警报加入到相应的关联集合中。若两个警报对应的符号表达式满足ϑExp(am)=ϑExp(an)，则两个警报存在恒等关联关系；若2个警报对应的符号表达式满足ϑExp(am)=ϑExp(an)，则两个警报存在非关联关系；若两个警报对应的符号表达式满足ϑExp(am)=ϑExp(an)‖ϑExp(a)，则两个警报存在或关联关系；若两个警报对应的符号表达式满足ϑExp(am)=ϑExp(an)&&ϑExp(a)，则两个警报存在与关联关系。如果这四种关联都不存在，则警报间不存在关联关系。
算法1程序语义缺陷的警报关联算法。
输入:检测的全部警报
输出:警报与警报间的关联关系
function WarningCorrelation(Sw)
for eacha∈Swdo
Sr←ρ(a);
Warning sort from small rank to large rank.
Manual determine each warninga∈Srthat Minimum rank of warning.
for(i=1;i≤N;i++)
for(j=i+1;j≤N;j++)
if(ai.Category!=aj.Category)
continue;
else
if(ϑExp(ai)==ϑExp(aj))then
ai.Con←aj;
aj.Con←ai;
else if(ϑExp(ai)==ϑExp(aj))then
ai.Not←aj;
aj.Not←ai;
else if(ϑExp(ai)==ϑExp(aj)‖ϑExp(a))then
ai.Or←aj;
aj.Or←ai;
else if(ϑExp(ai)==ϑExp(aj)&&ϑExp(a))then
ai.And←aj;
aj.And←ai;
else
No correlation;
通过警报关联算法后，如果警报间具有关联关系，则将这些警报的关联信息分别存储在警报关联文件Corinfo相应的Con、Not、Or、And集合中，方便以后人工判定警报的工作。
3.2 基于警报关联的人工警报判定
通过之前的警报关联算法已经得到了警报间的关联关系，这些警报可能是真实缺陷也可能是误报，还需要进一步人工判定警报的真实性。当人工判定一个警报后，警报判定系统会把跟这个警报相关的进行自动判定。
算法2的输入为警报及警报关联关系，输出为警报判定结果。其中，Sm表示人工重新判定集合。
首先人工判定警报集合中某警报是真实缺陷还是误报，然后依次判定警报a判定是否存在恒等、非、或、与关联关系。
若警报集合a.Con非空，表示警报a存在恒等关联的警报，判断存在关联的警报的判定标记Flag，如果Flag为0，则与警报a的判定结果相同，如果Flag为1，则判断已判定的类型是否与警报a的判定结果相同，如果不相同，则加入Sm集合；若警报集合a.Not非空，表示警报a存在非关联的警报，判断过程同上，只是判定结果与警报a相反；若警报集合a.Or非空，表示警报a存在或关联的警报，如果警报a的判定结果是真实缺陷，判定过程同恒等关联判定过程，如果警报a的判定结果是误报，则将与之关联的警报加入Sm集合；若警报集合a.And非空，表示警报a存在与关联的警报，如果警报a的判定结果是误报，判定过程同恒等关联判定过程，如果警报a的判定结果是真实缺陷，则将与之关联的警报加入Sm集合。最后，若集合Sm非空，则人工亲自判定集合Sm中的警报，人工判定完成警报后，算法结束。
算法2警报判定算法。
输入:警报及警报关联关系
输出:警报判定结果
function WarningDetermine(Sw，Corinfo)
for eacha∈Swdo
Manual determinea’s DeType;
if(a.Con!=Ø)then
for eachw∈a.Con do
call function Redet(w);
else if(a.Not!=Ø)then
for eachw∈a.Not do
if(w.Flag==0)then
else
if(w.DeType==a.DeType)then
Sm←w;
else if(a.Or!=Ø)then
for eachw∈a.Or do
if(a.DeType==defect)then
call function Redet(w);
else
Sm←w;
else if(a.And!=Ø)then
for eachw∈a.And do
if(a.DeType==false positive)then
call function Redet(w);
else
Sm←w;
if(Sm!=Ø)then
for eachw∈Smdo
Manual determinew;
function Redet(w)
if(w.Flag==0)then
w.DeType←a.DeType.
else
if(w.DeType!=a.DeType)then
Sm←w;
4 实验验证
在第4节中，已经介绍了警报关联算法和警报判定算法，为了证明上述方法能够实现警报关联及警报判定，将上述算法嵌入静态缺陷测试工具DTSC_RSTVL中进行实验。
4.1 实验平台
实验平台是在原型工具DTSC_RSTVL[14]的基础上进行改进，并得到了工具DTSC_Corr，通过该工具可以实现对典型语义缺陷的充分检测，并在缺陷检测阶段对警报进行关联与排序。图2所示为DTSC_Corr处理流程的基本框架，包括5个处理部分，分别为：输入部分、基本处理部分、数据流分析部分、自动检测部分、结果分析部分。
图2 DTSC_Corr工具处理流程图Fig.2 DTSC_Corr processing flow chart
4.2 实验结果及分析
选择3种常见的缺陷模式空指针解引用(NPD)、数组越界(OOB)、非法计算操作(IAO)作为DTSC_Corr的检测故障对象，并选择5个开源C工程Barcode、Sphinxbase、Uucp、Git、Httpd作为被测对象，5个工程共计1 232个文件447 250行代码，其中工程代码量最小的为3 409行，最大为204 229行。选择的这5个工程对于所用方法都具有一定的代表性，其包含大量复杂的指针操作和函数调用操作。
表1所示为在DTS平台测试5个C工程的警报详细信息。统计结果表明：5个工程共检测出914个警报，其中真实缺陷378个，误报536个。存在关联关系的警报总数占全部警报总数的61.71%，对警报的恒等、非、或、与关联统计，恒等关联占四种关联中的占比最多，为84.65%；其次是或关联占比13.30%，与关联占比2.05%，非关联没有匹配到，占比0，这是因为虽然非关联逻辑上是存在的，但是在真实的编程中却是很少使用，所以并没有检测到。在运行时间方面来看，采用警报关联后的DTS运行时间普遍略高于没有采用警报关联算法的时间。Barcode、Sphinxbase、Uucp、Git、Httpd 5个工程的处理时间分别增加9.38%、10.53%、6.86%、7.66%、12.40%，平均增加9.44%的程序处理时间。
利用警报关联方法可以减少345次警报判定工作，占警报总数的37.75%。其中，警报关联程度最高的工程是Git-1.8.2，通过警报关联算法可以减少46.26%的警报判定工作；警报关联程度最低的工程是Uucp-1.07，通过警报关联算法可以减少21.78%的警报判定工作。当工程规模更大时，警报数也将随之增加，通过警报关联算法可以减少的警报判定次数也会更多，人工判定减轻更大的负担。
图3为工程Barcode-0.98pcl.c中检测出的警报关联的实例，第65、第66、第67、第68行在没有进行任何空指针判断的情况下进行了引用，会引起NPD警报，该警报对应的相关变量为指针*ptr，4个NPD警报对应着相同的符号表达式，属于恒等关联关系。
图3 警报恒等关联示例Fig.3 Alarm identity association example
图4为Uucp-1.07/prot.c中检测出的另一个警报关联实例。第244行、第248行、第251行各报告了一个OOB警报，244行和248行因为潜在的存在分母为0的取值可能，第251行中drawWidth取值存在小于0的可能，违反了sqrt中参数必须大于等于0的规则，drawWidth的取值来源也是多个，这3个警报存在或关联。通过分析5个开源C工程的实验数据，发现所用警报关联方法在平均程序处理时间增加9.44%的情况下，可以减少21.78%～46.26%的警报判定工作。对于大型工程而言，这将在很大程度上减轻警报判定人员的工作量，从而可以提高整体的缺陷检测效率。
图4 警报或关联示例Fig.4 Alert or association example
表1 警报关联数据Table 1 Alert associated data
4.3 相关方法对比
基于警报关联的抽象解释优化试图通过警报间的关联性对静态分析报告的警报分类，对于存在关联关系的警报，只要确定其中一个警报即可完成与之相关联警报的判定。
本文方法与文献[12]、文献[13]的方法都是在抽象解释技术框架下，对检测到的警报进行警报关联。不同之处是，文献[12]借鉴反例求精思想方法，首先需要对被测程序生成一个超级控制流图进而进行完整的程序分析，这种分析无疑将需要大量的时间和空间开销，在大型程序的分析过程中无法实现；文献[13]采用程序切片技术的方法，首先给出了警报关联的定义，然后正式提出了警报错误状态切片，将警报的错误状态切片作为一种程序的外部输入约束，进而得到基于外部约束的程序求精语义。采用符号表达式的方法，基于警报对应符号表达式的逻辑关系推导出警报间的关联。本文方法与文献[12]、文献[13]方法主要有以下几方面区别。
4.3.1 警报关联精度
文献[12]方法主要是实现过程内警报间关联，无法实现过程间警报关联。文献[13]方法主要局限于警报错误状态切片过程中，对每一种警报类型生成对应的警报错误切片，由于符号化区间抽象域的表示及计算能力不足，并不能精确地利用现有静态分析工具所提供的抽象域切除其错误状态。对于警报间复杂的关联关系及语法类警报，不能准确地得到警报的关联关系。而本文方法利用符号表达式，通过警报对应的符号表达式间的逻辑关系，不仅可以实现过程内警报关联，同时可以实现过程间警报关联，且得出警报关联精度较高。
4.3.2 警报关联可信度
静态分析工具DTS在前期已经得到了大量求精与优化，肖庆等[5]通过使用变量取值信息来表达程序的路径状态，实现了DTS的路径敏感的分析；董玉坤等[15]在原有表达式区间抽象域的基础上引入了符号化三值逻辑区间抽象域，不但可以表示变量间的线性关联关系，还可以表达变量间的逻辑关联关系。在静态分析求精工作基础上进行研究，所得出的警报关联具有较高的可信度。
4.3.3 实验效果对比
表2为本文方法与文献[12]、文献[13]方法同时测试Barcode、Sphinxbase、Uucp、Git、Httpd 5个工程所得数据。从实验效果来看，主要可以分为减少警报确认数量和关联增加时间两大方面。由表2可知，从实验结果中减少警报确认数量来看，文献[12]方法的减少警报确认数量为23.42%，文献[13]方法的减少警报确认数量为28%，本文方法的平均关联比例为37.75%，本文方法在减少警报确认数量上均优于文献[12]、文献[13]的方法。当检测工程量很大时，对减轻人工判定工作具有更好效果。从表2的增加时间来看，本文方法的增加时间为9.44%，略低于文献[12]方法的增加时间15.06%，但高于文献[13]方法的增加时间8.81%。但目前的计算机处理性能都相对比较高效，时间上的增加也不是很多，属于在可以接受的范围内。
综合来看，本文方法可以在更高精度、可信度下识别出警报间的关联，从而可以更好地减轻人工判定工作的工作量。
表2 相关工作对比Table 2 Related work comparison
5 结论
提出了一种基于符号表达式的程序语义缺陷警报关联识别方法。首先提出警报关联的定义，然后通过警报相关变量对应的符号表达式之间的逻辑关系，总结出恒等、非、或、与四种类型的关联关系，其中通过符号化函数摘要实现了过程间警报关联，最后通过警报关联算法实现了过程内警报关联和过程间警报关联。通过实验验证得出，本文方法可以有效地实现警报间的关联，在程序处理时间略有升高的情况下，平均可以减少37.75%的人工判定警报工作量。
所做工作的局限性在于，研究主要集中在如何构建警报间的关联关系，因此在警报关联的结果中可能会存在误关联现象。如何改进警报间存在的误关联，进一步提高对实际工程的应用，仍然是下一步需要改进的方向。
