基于软件运行特征的故障检测方法研究

王正阳，王雅文,2

(1.北京邮电大学 网络与交换技术国家重点实验室，北京 100876；2.桂林电子科技大学 广西密码学与信息安全重点实验室，广西 桂林 541004)

0 引言

软件测试[1]是发现软件故障、提高软件可靠性的重要手段，源代码分析可以根据是否执行被测程序分为静态分析[2-4]和动态分析[5-7]两种方式。静态方法不需要执行被测程序，而是扫描被分析程序的源代码，通过使用符号执行技术进行静态路径分析、区间运算并根据设计的缺陷模式状态机检测代码中可能存在的非功能性故障。以静态分析工具HPFortify[8]为例，通过静态扫描得到的缺陷数量庞大，如表1所示，其中不可避免地包含了分析误报，程序通过静态分析出现的误报需要专业的测试人员进行人工缺陷确认，对于工程级别的代码，所需要人工确认的缺陷数量可能是十分庞大的，反而降低了静态分析的检测效率。

表1 Fortify扫描开源程序的结果[9]

动态分析技术主要通过动态测试工具执行被测程序，收集分析程序运行时信息进而发现或验证程序性质。一般是通过插装[10-11]的方式根据监测需求在程序中插入一些探针函数，在不改变程序原有逻辑正确性以及完整性的基础上，收集并分析程序运行时信息如变量值、程序运行路径以及程序运行时间等进而检验程序质量，然而传统动态测试工具的故障检测能力十分有限。

针对上述问题，本文提出一种基于软件运行特征的故障检测方法。核心思想是以动态测试的方式，通过在软件的执行过程中监控的程序状态、系统状态及执行时间等软件运行信息对相应故障模式进行识别。首先通过对故障模式的分析构建故障监控探针插装库。再通过静态分析识别故障监控点，结合相应的故障条件确定监控内容，在不改变原有代码逻辑的情况下，生成监控探针插入到源程序中。以动态测试的方式在程序运行过程中自动识别故障并在源程序中定位。该方法适用于逻辑复杂且可靠性要求高的软件，是静态方法的重要补充。

1 故障检测的现状

由于静态分析中对于复杂的程序语句以及对于操作系统和库函数调用的符号推理不够精确导致静态分析无法同时满足可靠性和完备性，业界通常在静态分析工具的效率与精度之间做出取舍，因此出现漏报的同时会出现大量的误报。目前现有的静态分析工具漏报率为9%～32% ，误报率为35%～91%[12]。

对于静态分析出现的大量误报问题，有很多针对误报消除[13]技术的研究，文献[14]提出了一种基于缺陷检测系统的警报自动聚类方法；文献[15]在区间抽象域基础上引入符号化三值逻辑抽象域，以支持表达变量间的逻辑关联；文献[16]提出了一种程序语义缺陷警报关联的方法，通过挖掘警报间的深层次关联信息建立警报关联。这些技术有助于提升人工确认的效率，但是仍然无法避免需要人工方式进行确认，因此开发人员开发软件时使用静态分析工具的意愿并不高。

动态测试在运行时所发现的代码漏洞一定是真实存在的，不存在误报情况[17]，传统的动态测试工具主要用于进行覆盖分析[18]，通过达到较高的测试覆盖率保证软件可靠性，然而对程序出现的故障没有进行分析确认。

对于故障检测技术的研究，无论是静态方法还是动态方法都已经相对成熟，单纯对静态检测方法或动态检测方法进行改进，没有太大的提升空间。但是，动静结合的漏洞分析技术可以弥补互相的优缺点，已经成为目前研究的热点。文献[9]针对静态分析报告的目标程序中内存泄漏的静态警报，基于警报制导信息对目标程序进行混合执行测试，结合动态执行的方式进行故障确认，然而该方法仍是通过静态分析方式识别故障，对于逻辑复杂的软件仍然难以避免误报率较高的问题，因此监测软件运行时故障特征从而在动态执行时识别故障是一种新的思路，能够有效弥补静态分析的误报问题。

2 检测软件故障的插装库设计

2.1 故障模式

程序中出现的故障可能会导致程序崩溃或出现不可预料的错误结果，大大降低软件可靠性甚至会产生严重后果。故障模式通常是由专业程序设计者以及专业测试人员总结出来经常出现且具有一定模式的故障[19]，可以成为出现故障时故障原因的分析依据，也可用于软件开发时可靠性设计的依据。本文所研究的故障模式是在代码上所体现出的一种错误形式，当具有某些特征的代码被执行时，会出现运行时故障。因此故障模式可从出错的状态上划分为3类8种，如下。

1)导致错误的程序状态：在程序执行过程中，表达式出现了非法的取值：

①空指针引用模式——被解引用的指针表达式的取值等于NULL；

②数组越界模式——数组下标表达式的取值超出上下界；

③非法计算模式——某些操作数或库函数参数出现非法取值；

④缓冲区溢出模式——对目标缓冲区的操作长度超出其界限等。

2)导致错误的系统状态：在程序执行过程中，分配到系统堆栈上的内存出现了不正常的状态：

⑤内存泄漏[20]模式——被分配到堆栈上的内存没有及时释放；

⑥资源泄漏模式——被分配到堆栈上的资源(文件、网络、数据库)没有及时释放。

3)执行时间异常：在程序执行过程中，某些比较复杂的循环或函数的执行时间超出预期：

⑦低效循环模式——循环结构的执行时间超出了预定的阈值；

⑧低效函数模式——函数调用的执行时间超出了预定的阈值。

能够体现故障模式出错时运行环境状态的代码特征信息称为故障特征，包括故障指令、故障对象和故障条件三部分。

1)故障指令：能够触发故障的程序指令，包括地址解引用操作、下标操作、部分算术运算操作符、以及部分内存或算术运算操作库函数。

2)故障对象：程序中直接与故障指令相关的对象，如一个变量或表达式。

3)故障条件：对故障对象的约束，如表达式的取值范围、内存地址上的成对操作、函数或循环的执行时间阈值。

2.2 扩展的插装库

程序插装技术最早是由文献[10]于1979年提出的，程序插装指的是在被测程序在保持原有代码逻辑不发生改变的情况下，在程序中插入一些探针函数，通过分析探针函数在程序运行时捕获的运行特征来获得程序的控制流以及数据流信息。程序插装的方式通常根据插装对象的不同分为源代码插装和目标代码插装。

源代码插装是最自然的插装方式，通过对程序源文件进行词法分析、语法分析后，根据探针函数的功能确定在源代码中的插装位置，目标代码插装技术不依赖程序源代码和编程语言，通常是对目标代码进行必要的分析以确定插装位置，由于目标代码一般是可执行的二进制程序，因此人工插入代码是很难实现的，一般通过调用对应插装工具提供的API实现对目标代码进行插装。

源代码插装的缺点主要是依赖源程序的编译语言，且对程序源代码分析工作量较大。但是由于对源文件进行了较为完整的静态分析，能够获得更多的语义信息，插装点较为准确，插入的探针在编译时也会被当作源代码进行编译优化，因此本文采用源代码插装。

传统的动态测试工具大多只是简单追求高测试覆盖率，其插装过程一般是按照所选取的覆盖准则根据获得的控制流图在程序中插入覆盖监控探针，根据输入的测试用例进行动态执行。在程序动态运行时，通过覆盖监控探针返回的信息统计测试覆盖率或是进行代码执行频度分析。本文的基于软件运行特征的故障检测方法除了支持传统的覆盖分析，为支持故障的动态检测，研究设计了能够检测故障的探针函数。

故障触发的条件是程序执行到故障点时，故障对象的取值满足故障条件的约束，因此检测故障的探针首先需要插入到程序中可能触发故障的位置，通过动态测试执行到插装点时收集程序执行到故障点时的相关运行特征，判断收集到的运行特征是否满足对应的故障约束条件从而达到识别故障并定位的功能。软件运行特征对于描述软件行为具有重要作用[21]。本文所涉及的软件运行特征可根据研究的故障模式大致分为程序状态、系统状态以及执行时间三类。程序状态包括程序中可见变量的类型和取值情况、函数调用情况等，系统状态主要为程序执行过程中的系统资源使用情况，执行时间包括函数执行时间、循环执行时间以及语句序列执行时间等。

基于前文故障模式与软件运行特征的研究具体设计如下八种相应的故障监控探针：

1)空指针引用故障监控探针：探针收集指针表达式和位置信息，约束指针表达式取值为非NULL，若该指针表达式出现等于NULL的状态时识别故障；

2)非法计算故障监控探针：探针收集敏感操作符或库函数名称、算术表达式和位置信息，针对传入敏感操作符或库函数名称，约束算术表达式的取值，若该算术表达式的取值与约束相悖则识别故障；

3)数组越界故障监控探针：探针收集被监控数组的数组下界、数组上界、数组下标的算术表达式和位置信息，约束数组下标算术表达式处于数组上下界之间，若数组下标算术表达式取值超出该范围则识别故障；

4)缓冲区溢出故障监控探针：探针收集目标缓冲区长度、源缓冲区地址和位置信息，约束源缓冲区地址长度不大于目标缓冲区长度，若超出该范围则识别故障；

5)内存泄漏故障监控探针：探针收集分配或释放操作标志、操作的内存地址和位置信息，在程序退出后，内存操作文件中对相同地址的操作应该配对，否则识别故障；

6)资源泄漏故障监控探针：探针收集分配或释放操作标志、操作的资源地址和位置信息，在程序退出后，内存操作文件中对相同地址的操作应该配对，否则识别故障；

7)低效循环故障监控探针：探针收集进入或退出循环标志、时间戳、限定时间和位置信息，在退出循环后，约束退出和进入循环的时间差应不大于限定时间，否则识别故障；

8)低效函数故障监控探针：探针收集进入或退出函数标志、时间戳、限定时间和位置信息，在退出函数后，约束退出和进入函数的时间差应不大于限定时间，否则识别故障。

3 基于故障特征的程序插装

故障监控探针需要通过程序插装技术插入在源程序中的相应监控位置，故障监控点的位置判定则首先需要通过对故障模式的分析构建故障模型库，包含相关故障指令、故障对象及故障条件等内容。其中，故障指令和故障对象可以用于定位监控点。之后对于识别到相应故障指令的监控点，需要结合对应故障对象以及故障条件，以插装库中的对应故障监控探针格式插入到源程序中。最后，故障监控探针在程序的执行过程中搜集程序状态、系统状态和执行时间等信息来识别故障，并定位于源程序中。

3.1 基于故障特征的程序插装设计

基于故障特征的程序插装主要分为如图1所示3个阶段：首先源程序进行静态分析，通过在静态分析过程中构建的如抽象语法树(Abstract Syntax Tree， AST)、控制流图以及符号表等程序抽象模型[22]中搜索故障触发指令，定位程序中所有与故障模式相关的位置。之后进行故障关联信息提取，从定位处提取故障模式相应关联对象。最后基于相应故障模式的触发条件，面向关联对象生成监控探针插入到源程序中。

图1 基于故障特征的程序插装流程

不同故障对应的故障监控探针插装设计如下：

1)空指针引用故障监控探针插装点位于空指针故障模式的触发指令之前，故障触发操作符包括对成员引用->、内容引用*、数组引用[]，故障触发库函数包括fclose、fopen、strcat、strcpy、strcmp等约束空参数的函数引用；

2)非法计算故障监控探针插装点位于非法计算故障模式的触发指令之前，故障触发操作符包括%、/、%=、/=等对右操作数有限制要求的，故障触发库函数包括asin、acos、atan、div、fmod、ldiv、log、log10、sqrt等对参数有限制要求的算术运算函数；

3)数组越界故障监控探针插装点位于数组成员引用操作之前，从检索到的故障触发指令对应的语句中提取故障关联对象，即数组下标表达式，同时从符号表中提取相关数组的上下界作为约束条件；

4)缓冲区溢出故障监控探针插装点位于strcat、strcpy、strncpy、strcmp、strncmp等对缓冲区进行操作的库函数之前，从检索到的故障触发指令对应的语句中提取故障关联对象，即源缓冲区地址，同时计算目标缓冲区的可用长度作为约束条件；

5)内存泄漏故障监控探针插装点位于malloc、calloc、realloc等具有内存分配特性的库函数之前，从检索到的故障触发指令对应的语句中提取故障关联对象，即被分配内存的地址标识符；其次，检索free、delete等具有内存释放特性的库函数并在这些函数调用前插入探针；

6)资源泄漏故障监控探针插装点位于fopen、socket、accept等资源分配函数之前，从检索到的故障触发指令对应的语句中提取故障关联对象，即被分配资源的地址标识符；其次，检索与分配资源对应的资源关闭函数并在这些函数调用前插入探针；

7)低效循环故障监控探针插装点位于while、for、do等循环结构开始之前以及循环结构结束位置之后；

8)低效函数故障监控探针插装点位于每个函数的入口处第一条语句之前和函数返回语句之前。

3.2 故障监控探针插装算法

针对本文研究的故障模式，根据对应故障触发指令定位其在程序中的插装点，主要通过遍历源程序静态分析生成的抽象语法树识别程序中的故障指令搜索故障监控探针插装点，并根据图1的插装流程提取需要监控的故障对象在源程序中生成探针函数得到插装后的程序，在程序执行过程中收集探针返回信息检测故障。

算法1:描述了故障监控探针插装点定位算法，该算法将源程序通过静态分析生成的抽象语法树的根节点root以及初始化为空的插装点集合instru_set作为输入，输出为确认后的故障监控探针插装点集合instru_set。

故障监控探针插装点定位算法中所用到的定义如下：

ASTNode：抽象语法树节点父类。

function_definition：函数体定义节点。

return_statement：return语句节点。

iteration_statement：循环体节点。

simple_statement：简单语句节点。

expression：表达式节点。

getType(node)：获得节点node的节点类型。

getChildrenNodes(node)：获得node节点的所有子节点。

addLEFIn(instru_set, node)：将函数入口处的低效函数故障监控探针插装点加入插装点集合instru_set中。

addLEFOut(instru_set, node)：将返回语句前的低效函数故障监控探针插装点加入插装点集合instru_set中。

addLEC(instru_set, node)：将循环体之前以及之后的低效循环故障监控探针插装点加入插装点集合instru_set中。

check(node)：检查简单语句节点node是否包含4种程序状态出错故障触发指令、内存分配或释放指令以及资源分配释或放指令。

checkExpression(node)：检查表达式节点node是否包含4种程序状态出错故障触发指令、内存分配或释放指令以及资源分配释或放指令。

addFault(instru_set, node)：根据节点node中包含的故障指令，确定故障监控探针类型并将对应故障监控探针插装点加入插装点集合instru_set中。

算法1：故障监控探针插装点定位算法

输入：root //源程序的抽象语法树根节点

输出：instru_set //故障监控探针插装点集合

1. instru (ASTNode node, List instru_set) {

2. if getType (node) == function_definition then

3. addLEFIn (instru_set, node);

4. if getType (node) == return_statement then

5. addLEFOut (instru_set, node);

6. if getType (node) == iteration_statement then

7. addLEC (instru_set, node);

8. if getType (node) == simple_statement then

9. if (check (node)) then

10. addFault (instru_set, node);

11. if getType (node) == expression then

12. if (checkExpression (node)) then

13. addFault (instru_set, node);

14. for each n getChildrenNodes (node)

15. instru (n, instru_set);

16. }

算法主要思想是通过深度优先遍历源程序抽象语法树，识别对应的故障指令确认故障插装位置。算法1～7行通过判断语法树节点类型识别函数体和循环体，定位低效函数和低效循环故障监控探针插装点；8～13行判断简单语句或者表达式中是否包含空指针引用、非法计算、数组越界、缓冲区溢出以及内存泄漏和资源泄漏的故障触发指令从而生成对应故障监控探针插装点。对于表达式节点需要拆分逻辑表达式，检查所有子表达式是否包含故障指令。14～15行遍历当前节点的子节点，对子节点进行故障监控探针插装点定位。

4 实验结果与分析

前文已经介绍了基于故障特征的程序插装技术，为验证本文提出的基于软件运行特征的故障检测方法故障检测能力，将该技术应用于代码测试系统[23](Code Testing System， CTS)中进行实验验证，实验环境为Ubuntu 12.04操作系统，配置AMD Ryzen 9 5900HX(3.30 GHz)处理器，8 GB内存以及512 GB SSD硬盘。

实验采用了CTS自带的 Norton 命令的 Unix 环境复制版开源项目deco，项目包含的10个C文件如表2所示。为验证本文提出的方法，对被测程序进行了故障注入。其次，为了能够有效触发故障，通过CTS中人工输入测试用例的方式进行实验。

表2 被测程序

为准确识别本文提及的两种执行时间异常故障，在程序中将进程挂起5秒。通过在程序执行后收集的故障监控探针函数返回信息可以得到故障检测结果，通常情况下，对于单次的测试用例生成是无法覆盖程序中所有路径，因此实验需要输入大量的测试用例从而达到覆盖所有触发故障的路径，但是可能会导致收集的信息包含了同一故障的多次记录。因此，在分析故障监控探针信息时，通过收集到的故障位置信息进行故障去重，将去重后的故障作为实验统计的最终结果。根据3种出错状态分别统计以本文方法检测出的故障，实验结果如表3所示。

表3 故障检测结果

实验结果表明本文所研究的八种故障模式均可通过该方法进行有效检测。根据实验所检测出的故障，在注入故障的程序中定位分析后发现所报故障均为真实存在且故障定位准确，不存在误报情况，该方法可有效弥补静态分析对于逻辑复杂软件进行故障检测时由于缺少运行时信息导致不精确的区间运算和符号执行产生的误报问题，大大减少了对于误报问题人工确认的成本。部分故障监控探针插装点位于程序中不可达路径上，无法通过生成测试用例执行覆盖到，已通过CTS自带的不可达路径[24]判断功能进行识别，实验符合预期。

5 结束语

本文针对静态分析出现大量误报的问题，结合静态分析和动态测试提出了一种基于软件运行特征的故障检测方法，通过研究按照出错状态划分为三类的八种故障模式，基于动态测试的插装技术，在传统用于覆盖分析的插装库中扩充了用于监控故障的探针函数。通过研究八种故障模式对应的故障特征，设计了相应的插装算法。该方法是对静态分析方法的重要补充，通过引入动态分析的方式在程序实际运行时收集程序路径上下文真实信息，避免了使用纯静态分析进行故障检测时完整路径上下文分析的组合爆炸[25]导致分析不准确的问题，有效弥补了静态分析高误报问题，可适用于逻辑较为复杂的程序。

该方法可通过收集触发故障对应的测试用例进行故障复现，帮助测试开发人员进行故障定位和修复。后续可以通过更精确的静态分析对故障监控探针插装点进行约简，但可能会导致插装性能下降，可以根据不同需求进行平衡。由于动态测试十分依赖输入的测试用例，不完备的测试用例会导致漏报[26]问题，因此触发故障导向的测试用例生成技术也将成为后续研究的方向。