基于警报关联摘要的过程间警报关联分析

张 莉 董玉坤 刘 浩 尹文静

（中国石油大学（华东）计算机科学与技术学院 青岛 266580）

1 引言

随着信息技术行业的蓬勃发展，软件的规模与复杂度也呈现递增式增长。软件中存在缺陷难以避免，其中，程序语义缺陷是一类典型的软件缺陷，程序语义缺陷会导致程序运行时出现系统瘫痪、运算结果不正确、性能降低等问题。

静态分析技术是检测语义缺陷的一种有效方法，但由于在数据流分析与缺陷检测过程中的某些保守处理，检测出的警报只是可能是缺陷，其中可能会存在误报，根据相关数据统计，目前存在的静态分析［17］工具检测出警报的误报率大概在35%～91%之间［1］。而这些误报的存在导致缺陷检测结果必须由人工进行仔细的判定，对检测出的警报的判定需要投入大量的人力，这不但降低了缺陷检测的效率，也会增加缺陷检测的成本。

通过对大量程序进行静态缺陷检测［12～13］到的警报进行人工分析，其结果表明警报与警报之间存在着关联关系，将具有关联关系的警报聚为一类，只需要对一类中的一个或多个警报的结果进行判定，即可得出该类警报的判定结果，从而提高人工判定警报的效率。

目前，在软件的开发过程中模块化开发的体现即为大量的函数及函数调用。大量函数调用这种交互行为使得函数之间的警报存在着关联关系，称为过程间警报关联［2～7］。根据相关数据分析表明，过程间警报关联的数量占总警报关联总数的比重为31.7%，当代码量巨大时，过程间警报关联的数量也是非常巨大的。

鉴于上述现象，本文提出了一种基于警报关联摘要的过程间警报关联分析方法，使用该方法可以在更高效率、更方便地识别出过程间的警报关联，进而更多地减轻人工判定警报的工作量。本研究的贡献可以概括为以下方面。

1）通过定义警报关联摘要，获得每个函数的警报关联摘要，并利用该摘要实现过程间警报关联，内存开销相对比较低；

2）实验验证了本文所提方法的有效性，减轻了人工判定警报的工作量，提高了人工判定警报工作的效率。

2 程序语义警报概述与表示

警报关联技术是一种能够有效减轻警报判定负担的警报优化技术［8，14～16］。本小节给出警报相关问题的具体分析与说明。

2.1 程序语义缺陷

程序语义缺陷是导致软件故障及漏洞的重要原因之一，对语义缺陷分析可以帮助解决软件故障和漏洞。在程序中，将一类缺陷表现出的共同存在的语义特征称为语义缺陷模式，语义缺陷模式又可分为故障类缺陷和安全类缺陷［9］，本文中主要针对故障类缺陷，常见的故障类缺陷有空指针引用类型、内存泄露类型、数组越界类型等。

我们将真实缺陷与误报统称为程序语义警报，其具体定义如下，本文之后不再进行说明。

定义（程序语义警报）。假定在程序点l处，如果Ab(l)∩Er(l)≠∅，其中Ab代表程序抽象语义，Er代表程序点的错误状态，则说明在程序点l处存在警报，否则，在程序点l处不存在警报。

2.2 程序语义警报的表示

为了能够在程序中准确得到并表示警报，本文将结合符号表达式和区间集通过数据流两次映射将警报转化为其对应的取值区间。两次映射如下：首先，将警报变量映射为对应的符号表达式［10］，Var→SExp；其次，将符号映射为对应的取值区间［11］，Symbol→Domain。这样就将得到了警报的取值区间。

对于任意的两个警报am和an，假定ϑExp(am)表示警报am的相关变量对应的符号表达式，ϑExp(an)表示警报an的相关变量对应的符号表达式。警报与警报之间具有恒等、非、或、与等关联，这些关联信息是人工判定过程中警报确认的前提［18］。

1）恒等关联：如果ϑExp(am)=ϑExp(an)，若警报am和an同为误报或真实缺陷，则警报am和警报an存在恒等关系。

2）非关联：如果ϑExp(am)=¬ϑExp(an)，若其中一个为误报，则另一个为真实缺陷，则警报am和警报an存在非关联关系。

3）或关联：如果ϑExp(am)=ϑExp(an)‖ϑExp(a)，其中ϑExp(a)表示任意警报对应的一个符号表达式，称警报am与警报an存在或关联关系。

4）与关联：如果ϑExp(am)=ϑExp(an)&&ϑExp(a)，其中ϑExp(a)表示任意警报对应的一个符号表达式，称警报am与警报an存在与关联关系。

3 过程间警报传递类型

函数间调用往往是引起过程间存在警报关联的一个重要因素，因此，在分析过程间警报关联时，需要对程序中的函数调用过程进行分析。在本文中，具体的函数间的调用关系用程序函数调用图［8］（Program Function Call Graph，PFCG）来表示。

若警报通过函数调用引发新的警报，导致存在过程间警报关联。通过分析函数间的调用方式，过程间警报传递类型又可以分为链式型传递关系、汇聚型传递关系和发散型传递关系三种类型，下面将对这三种类型进行说明。

3.1 链式型传递关系

若函数f1中存在警报a，函数f1调用函数f2，导致因为警报a的传递引发警报b的产生；同时函数f2又调用函数f3，同样导致警报b的传递引发警报c的产生，则警报a、警报b和警报c存在着关联关系，称这种为链式型传递关系（Chain Type Transfer Relationship，ChTR），如图1所示。

图1 链式型传递关系图

3.2 汇聚型传递关系

若存在多个函数g2，g3，…，gn调用同一个函数g1，并且函数g1存在警报a，由于函数g2，…，gn调用函数g1引发新的警报b，c，d等，则警报b，c，d和警报a存在关联关系，称这种关联关系为汇聚型传递关 系（Convergent Type Transfer Relationship，Co-TR），如图2所示。

图2 汇聚型传递关系图

3.3 发散型传递关系

若函数q1中存在警报a，函数q1调用了多个函数q2，q3，…，qn，导致因为警报a的传递引发警报b，c，d等的产生，则警报a与警报b，c，d存在着关联关系，称这种关联为发散型传递关系（Divergence Type Transfer Relationship，DTTR），如图3所示。

图3 发散型传递关系图

4 警报关联摘要

对函数间交互行为的分析称为过程间分析。本文对过程间分析采用了函数摘要的方式，函数摘要是一种目前被普遍采用的方法，根据函数内分析结果生成被调函数的摘要信息，用摘要信息再分析过程中替代其展开。接下来介绍了关于缺陷的函数摘要模型。

针对过程间警报关联识别问题，本文提出对存在警报的函数生成对应的警报关联摘要的方法，然后生成被调函数的警报关联摘要信息，用摘要信息替代其函数调用的展开。

在函数调用过程中，产生的警报可能向其调用者进一步传递警报状态，可能会对调用该函数的上下文信息产生影响，导致调用点上下文环境迁移：1）实参；2）函数返回值；3）全局变量。

针对上述三种类型的影响，本文给出了警报关联摘要模型（Warnings Correlation Summary Model，WCSM）来描述，警报关联摘要模型尽可能详细地捕获了所有与警报相关的函数行为，警报关联摘要模型可以分为前置约束信息Pre-constraint、后置约束信息Post-constraint两部分。用符号表示为WCSM=｛Pre-constraint，Post-constraint｝，其中前置约束信息Pre-constraint表示函数调用前应满足的约束信息，后置约束信息Post-constraint表示函数调用后所带来副作用影响。

1）前置约束信息

前置约束信息Pre-constraint表示跟警报相关的一类信息，不同缺陷模式对应的警报会对应不同的前置约束信息。前置约束信息表示如式（2）。

Pre-constraint={＜var，SExp，con＞}表示主调函数调用被调函数时应满足的前置约束信息集合，＜var，SExp，con＞代表变量var对应的符号表达式SExp的取值必须包含在约束条件con中。

其中，con表示被调函数在调用点处需要满足的条件，不同类型的缺陷需要满足不同的条件。

2）后置约束信息

后置约束信息Post-constraint主要针对分析函数返回值RetVal和全局变量GloVar两种类型的影响。后置约束信息表示如式（3）。

RetVal=SExp表示函数返回值的符号表达式，GloVar={(var，SExp)}表示由受副作用影响的变量var和其对应的符号表达式SExp两个元素组成的集合。

5 警报关联摘要生成及实例化

警报关联摘要生成步骤如下。首先，得出程序中数据流分析结果calDomain，计算函数返回语句RetVal的符号表达式SExp作为后置约束信息的函数返回值部分，获取程序中全局变量GloVar的对应的变量var和其符合表达式SExp作为后置约束信息的全局变量部分；对于函数内无法确定的缺陷状态，构造其变量、符合表达式和其约束信息作为前置约束信息，并向上层调用者传递。下面将给出警报关联摘要的生成算法。

算法1.警报关联摘要生成算法。

当函数间存在调用关系时，这时就需要用到警报关联摘要实例化。警报关联摘要实例化步骤如下。首先，获取被调用函数已经生成的警报关联摘要；其次，根据数据流分析结果对警报关联摘要更新，如果警报关联摘要有变化，则将前置约束信息和后置约束信息对应的取值信息用调用点处的信息更新，否则，不更新；如果存在多级函数调用的情况，则需要从下到上依次进行实例化。

6 过程间警报关联算法实现与分析

在本节中我们将介绍过程间警报关联的算法与实现，下面是其详细描述。过程间警报关联算法步骤如下。

1）从警报特征信息SV中得出存在警报的函数，得出存在警报的函数集合SF；

2）通过分析函数集合SF中函数间的关系，生成对应的函数调用子图PFCG'；

3）依次判定生成的每一个函数调用子图PFCG'的类型，根据函数调用子图的调用类型可以分为以下三种实例化更新的方法。

当某个函数调用该存在警报的函数，根据上下文信息进行实例化，如果存在警报关联摘要对应的值不一致的情况，进行更新，否则，不更新。

（1）针对链式型传递关系

若存在警报的函数间是链式型传递关系类型（ChTR），即函数存在多级调用的情况，则从调用者到被调用者依次更新警报关联摘要。更新完毕后，根据过程内警报关联算法［18］继续判定警报间的关联关系。

（2）针对汇聚型传递关系

若存在警报的函数间是汇聚型传递关系（Co-TR），则需要每个主调函数依次对被调函数进行警报关联摘要更新，并需要分开判断。

（3）针对发散型传递关系

若存在警报的函数间是发散型传递关系（DTTR），即一个函数调用了多个函数的情况，则同样由主调函数对每一个被调函数进行警报关联摘要更新。更新完毕后，同样根据过程内警报关联方式继续判定警报间的关联关系。

算法2.过程间警报关联算法。

7 实验验证

本节分别介绍了实验平台DTSC_Corr及其处理流程，并对实验结果中的数据进行分析与说明。

7.1 实验平台

本文的实验平台是在原型工具DTSC_RSTVL［14］的基础上进行改进，并得到了工具DTSC_Corr，通过该工具可以实现对典型语义缺陷的充分检测，并在缺陷检测阶段对警报进行关联与排序。图4表示DTSC_Corr处理流程的基本框架。

图4 DTSC_Corr工具处理流程图

7.2 实验结果及分析

本节将通过实验来进行验证本文所提的过程间警报关联算法的应用效果。本实验选择了3种常见的缺陷模式空指针解引用（NPD）、数组越界（OOB）、非法计算操作（IAO）作为检测故障对象，使用标准性能评估组织SPEC（Standard Performance Evaluation Corporation）提供的公共测试集SPEC2000/2006中5个开源C工程Barcode-1.07、Antiword-0.37、Sphinxbase-0.3、Spell-1.0、Uucp-1.07作为被测对象，5个工程共计125809行代码，其中程序中的函数个数为2414个，调用函数的次数为9017个。其过程间警报关联数据统计如表1所示。

表1 过程间警报关联数据统计

通过对实验结果分析，过程间警报关联的各种关联分布与过程内警报关联的关联分布类似，同样是存在恒等关联的警报最多，其数量占警报数量总数的56.19%；其次是存在非关联的警报，其数量占警报数量总数的18.13%；然后是存在与关联的警报，其数量占警报数量总数的9.97%；最后是非关联关系，占比为0。

通过对实验数据分析得出，该方法可以有效识别过程间警报关联，帮助提高人工判定警报效率约35.12%。该方法的优点是在函数调用点处，使用警报关联摘要的方法可以避免重复分析函数的行为，能够提升函数的分析效率；但该方法同时存在缺点，即所提的过程间的警报关联只适用于结构简单的函数调用关系，对于存在复杂的函数调用关联的警报，该过程间警报关联方式并不一定能够准确识别出来。

8 结语

本节针对过程间存在警报关联的问题，提出了一种基于警报关联摘要的过程间警报关联分析的方法，该方法通过首先对被测程序生成函数调用关系图，并根据生成的函数调用图得出函数体分析顺序；接着对函数生成对应的警报关联摘要；然后对存在函数调用关系进行实例化更新，对存在变化的警报的符号表达式进行更新；符号表达式更新完毕后，根据过程内警报关联方式继续进行警报关联判定；最后通过实验验证本文所提方法可以有效识别过程间警报关联，该方法可以减少35.12%的人工判定警报工作量。