一种基于异常控制流的错误程序行为分析方法

江建慧， 吴捷程， 孙 亚

(同济大学 软件学院， 上海 201804)

错误程序行为(erroneous program behavior, EPB) 分析主要是获取程序差错及其对程序行为的影响，包括差错类型、差错发生位置、差错发生时机，以及各个差错在程序中的表象.

软件故障注入技术通过人为地对软件或计算机等目标系统注入软件故障来加速其失效，从而实现目标系统的容错机制有效性验证、可靠性评估[1-2].然而，如何得到真实的软件故障或差错数据是该技术实现的前提[1-4].

具有代表性的软件差错数据获取需要分析软件的功能特性及其在某个故障/缺陷被激活后所表现出的错误行为[2-3,5]，工作量很大，且分析周期很长[1,3].常见的正交缺陷分类(orthogonal defect classification, ODC)所属故障被激活后所产生的程序差错形式随程序实现的不同而不同[1]，可能以返回码或共享变量的形式存在于应用程序与其使用的库函数之间[2,6]，也可能以异常的形式在程序中进行传播[5-6]，或以跳转指令的组合形式出现[7].

在具有异常处理机制的程序中，故障激活后所产生的差错若被异常处理机制侦测，则异常发生[8-9].若对该异常处理不当，则可引起程序失效[9].这一过程将形成“故障-差错-异常-失效”链.

通过对程序异常控制流(exception control flow，ECF)的分析可收集能够引起异常的差错信息，包括：由异常类型获取差错内容；由异常引发点获取差错被侦测时的物理位置；由异常传播路径获取差错的影响范围；由异常捕捉情况获取差错是否得到修正的信息.这些信息可指导软件故障注入方案生成所需的差错类型、注入位置、注入时机的选择[4-5,10-11].该过程通过源代码的静态分析，可在相对较短的时间内完成.

本文的主要工作是通过故障注入实验分析程序的“故障-差错-异常”的传播机理；结合函数级ECF(function-level ECF，FECF)的描述，分析了同一差错与多个程序ECF之间的关系，利用ECF对程序中潜在可引起异常的差错进行分析，建立了EPB模型；实现了一个自动分析工具软件，并以OpenStack的核心组件为对象进行了实验验证.

1 相关工作

Christmansson等[3]认为只有注入具有代表性的差错才能有效地模拟真实故障的发生，有效地验证软件的容错机制.考虑应用程序和函数库之间的潜在错误的故障注入工具LFI(库文件故障注入器)改善了应用程序的健壮性测试技术[2].基于穷尽异常模拟模式的测试方法结合异常发生的时序特点在异常引发点注入异常，简化了异常处理结构有效性验证的过程[5].上述工作强调了故障/差错数据的有效性，讨论了如何利用差错数据进行软件容错机制的验证，但其尚未涉及如何有效地收集合理的差错数据.

关于软件故障激活后的传播过程及证明故障激活后能否转化为差错的研究，有基于“故障-差错-失效”的传播关系选择具有代表性的差错集合的方法[5].通过代码内部的故障注入和接口差错注入的实验研究结果表明，两者对程序的影响存在一定的差异[4].代码故障激活后的差错不仅能以返回值、错误码、传入/传出参数的方式进行传播，还能以共享内存数据为载体对程序造成影响[11].应从多维度对故障注入后的EPB进行收集、分析、归类，从而使得各层次的EPB研究可得到相关数据的支撑，实验表明，故障激活后所产生的差错能以返回值或异常形式进行传播，且该差错被侦测的情况和是否引起程序失效取决于程序的实现[6].这些工作均未深入研究具有异常处理机制的程序中的“故障-差错-异常”过程.

大多数与程序ECF相关的研究工作主要聚焦在它对程序分析、开发、测试的影响上.如基于异常传播分析的C++程序数据流分析方法[12]、依赖性分析方法[13].Harrold等[14-15]在对异常处理机制的测试标准进行研究时,考虑了异常处理机制和异常传播对程序控制流、数据流、控制依赖性等分析技术的影响.用于程序开发、维护、测试的系统化方法通过分析显式ECF，总结了与异常处理结构实现相关的编程错误模式，可指导开发者如何有效地避免异常处理机制的错误使用[16].面向切面机制在一些情景下会使异常处理结构的实现复杂化，从而降低系统的可靠性[17].Jo等[18]提出了一种基于集合分析的函数级别上的Java未捕捉异常分析方法.结合运行时异常的静态测试方法通过交替执行缺陷检测及控制流扩展，提高了测试充分度，还分析了运行时异常对软件静态测试的影响[19].这些与程序ECF相关的研究工作并未考虑到异常本身就是程序错误的一种表象，所以没有利用异常相关的信息来分析潜在的EPB.

2 程序“故障-差错-异常”机理分析

2.1 ODC故障注入实验分析

异常处理机制(exception handling mechanism，EHM)是程序错误处理的常用手段之一.当程序中EHM侦测到差错且引发异常之后，程序的“故障-差错-异常/失效”过程如图1所示.

对Android上约800个应用组件所进行的600万次基于外界输入的健壮性测试实验数据表明，约10%的应用组件发生了崩溃且均由未捕捉到的异常所造成[6].

本文以分布式网络基准程序Ipbench和OpenStack中的核心组件nova为对象，结合ODC故障类型及其分布数据，以代码变异的方式实施故障注入实验，实验结果见表1(表中的E表示可引起异常的故障数量).

在Ipbench中共注入348个故障，其中255个故障导致了程序崩溃，且249次崩溃是由未捕捉异常引起.

在nova中共注入1 018个故障，未出现程序崩溃现象.由表1可知，419个故障激活后的差错得到程序的修正，可能的原因有：① 有差错的数据在被使用之前重新得到初始化；② 有差错程序的执行结果与无差错程序的执行结果一致；③ 差错引起异常且被捕获，异常处理例程提供了正确的服务.

表1 故障注入实验结果Tab.1 Results of fault-injection experiments

2.2 传播机理分析

以nova的_validate_cell函数为例，程序的“故障-差错-异常”传播过程分析如下：

(1) 故障激活所发生的差错直接引发异常.如图2所示，故障激活后的差错直接在当前函数内使raise语句得到执行，从而引发异常.同时，图2中场景a)与b)的故障激活后均引起了同一异常，说明程序中故障与异常存在多对一关系，即多个故障激活后的差错最终均以同一异常在程序中进行传播.

(2) 故障激活所发生的差错经过传播后引发异常.图3所示的故障激活后的差错通过数据流影响控制流，最终使得raise语句得到执行，引发异常.

(3) 在程序无故障的情况下，外界输入或外界资源违反软件规约而导致异常发生.

因此，可从“异常”层次出发，分析程序中可引起异常的差错信息及其对程序行为的影响，达到分析与异常相关的EPB的目的.

图2 差错直接引起异常例子Fig.2 Example of an error raises exception directly

3 基于ECF的EPB分析

为了获取可引起异常的差错的信息，本文方法并不需要构建带有程序ECF的完整过程间控制流[20]，而只需获取独立的ECF信息，包括：ECF起始与中止位置信息；ECF对应的异常类型；异常是否被捕捉；ECF所影响到的函数；ECF所影响到的程序功能或服务.这是一种基于源代码静态分析的方法，如何选择起始函数作为分析的起始点，则直接影响到了分析结果的有效性.

3.1 函数级ECF的描述

图4所示的是函数级异常传播过程，其中nk(1≤k≤m，m≥1)表示函数，其他符号的意思在图中已经加以说明.以函数为粒度的异常传播过程可分为A，B和C三类.

(1) 过程A：异常在当前函数nm被引发，而且被捕捉.

(2) 过程B：异常在当前函数nm被引发，且沿着函数调用栈经过m-k逆向传播后在函数nk中被捕捉，1≤k≤m.

(3) 过程C：异常在当前函数nm被引发，且沿着函数调用栈经过m-1次逆向传播，变成未捕捉异常.

图3差错经过传播而引起异常的例子

Fig.3Exampleofanerrorraisesexceptionwithcertainpropagation

图4 函数级的异常传播过程Fig.4 Exception propagation process at function level

定义1程序P中由raise/throw语句显式引起的FECF可表示为5元组Ψ=，其中:

(1)ol=(n,lo)为Ψ的起始位置，表示Ψ由函数no中代码行号为lo的raise/throw语句所引发.

(2)t为Ψ所对应的异常类型.

(3)z=(nz,lz)为Ψ的终止位置.若Ψ属于过程A或B，则nz为Ψ被捕捉时所在的函数，其对应的异常捕捉语句的行号为lz；若Ψ属于过程C，则Ψ在程序P的函数nz处终止且传播出去，lz为Ψ进入函数nz时的异常入口所对应的语句的代码行号.

(4)π以路径的形式给出了Ψ的传播过程.若Ψ属于过程A或B，则π为no→nm→…→n1→nz，其中no，nz，nk(k=1,2,…,m，m≥1)为Ψ所影响到的函数；若Ψ属于过程C，则π为no→nm→…→n1→nz→nout，其中nout为占位符，表示该路径对应的ECF未被捕捉.

(5)e为Ψ被引发时程序P的栈底函数，表示被Ψ影响到的程序功能或服务.

与文献[4, 20]一致，本文也将入口函数(entry function, EF)作为函数调用链的分析起点，计算程序中所有潜在的FECF.

3.2 利用程序ECF表示EPB

同一差错可引起不同的FECF.这些FECF组成的集合称为FECF簇，对于其中的任意Ψi与Ψj，它们具有相同的o与t值.

根据“故障-差错-异常”传播机理，若故障激活后的差错引起异常，则该故障对程序带来的影响完全可由相应的FECF簇表示.所以，可通过分析各FECF簇，反向推导程序中可引起异常的各个差错及其对程序行为的影响，从“异常”层次分析与异常相关的EPB，收集可引起异常的差错集合.

3.3 基于程序ECF的EPB分析

(3)w为一权值，即：

(1)

观察1w值越大，则EPB对程序可靠性造成危害的风险越大.

异常传播过程B与C的发生会使程序的过程间控制流中产生潜在的非返回调用[15]，它的数量(即w值)越大，就意味着异常的传播范围越大，所以程序的控制流、数据流在错误状态下受到的影响越大.

算法Gen_FECF: 计算一个FECF实例

输入s: 函数m中的raise/throw语句

m: 语句s所位于的函数

输出Ψ: 一个FECF实例

声明 callstack: 遍历分析函数调用链时所维护的函数调用栈

CTS(m): 函数m的调用者(caller)调用函数m时所使用的函数调用语句

开始 Gen_FECF(s,m)

1. 新建Ψ实例并设置其属性:o←(m,s的行号),t←s对应的异常类型,π设置为m,e←callstack的栈底函数;

2. If SLEGS(s)存在c可捕捉由s引发的异常 then

3.z←(m,c的代码行号),m加入π:m→m;

4. returnΨ;

5. else then //当前函数m无法捕捉该异常

6. temp_stack为callstack的副本;

7.send←s; //用于暂存Ψ终止时的语句

8. While temp_stack不为空:

9.mtop←temp_stack.top();

10. temp_stack.pop();

11. if m!=mtopthen 将mtop加入πendif

12. if temp_stack is empty: //未捕捉异常

13.z←(mtop,send的行号);

14. ifm!=mtopthen

15. 将nout加入π;

16. else

17. 将m→nout加入π;

18. endif

19. returnΨ;

20. else if SLEGS(CTS(mtop))有c可捕捉then

21.z←(temp_stack.top(),c的行号)；

22. 将temp_stack.top()加入π;

23. returnΨ;

24. endif

25.send←CTS(mtop) ;

26. endwhile

27. endif

结束Gen_FECF

在计算所有FECF时，e可用于表示FECF所影响到的程序功能或服务.

若在函数递归过程中出现异常，则异常在该部分的传播路径呈现一定的模式.所以，可根据该模式制定合理的裁剪规则，对递归部分的调用链进行裁剪，使得分析过程能够有效地继续执行下去.

在算法Gen_FECF中，函数调用栈是根据函数调用链生成的.由于调用链经过了递归调用链裁减处理，并且调用链中所有函数都属于程序P，函数调用栈的深度最多为2·|FDS(P)|-2，其中FDS(P)为定义于程序P中且在程序P中实现的函数集合.算法Gen_FECF在最好情况下的时间复杂度为O(1)，在最坏情况下为O(|FDS(P)|).

根据EHM的性质[14]，对于异常的传播及其处理过程，异常保护区z(try语句所保护的代码块)的异常保护序列EGS(z)指的是z对应的异常处理例程所组成的有序序列(c1,c2,…,cn)，n≥1，其顺序由z对应的异常处理例程的顺序决定.假如zj嵌套于zi之中，那么传播到zj中的异常首先会被EGS(zj)中的异常处理例程尝试捕捉处理，若该异常未被捕捉，则EGS(zi)再尝试对其捕捉处理，则LEGS(zj)=(cj1,cj2,…,cjn,ci1,ci2,…,cim)，若zi不嵌套于任何异常保护区中，则LEGS(zi)=EGS(zi)=(ci1,ci2,…,cim)，m≥1，n≥1.若语句s位于z中，则语句s受到LEGS(z)的保护，记为SLEGS(z).若有异常在s(raise/throw语句)处被抛出或异常传播至s(函数调用语句)处，若SLEGS(s)能捕捉该异常，则该异常在s语句所在的函数中被捕捉，否则该异常从当前函数传播出去且沿着函数调用栈逆向传播.

在形如(m1,m2, …,mn-1,mn)所表示的调用栈中，m1表示栈底，mn表示栈顶，n≥1.suc(mi)是mi的后继mi+1，n≥i≥1，suc(mn)=null.CTS(suc(mk))为函数mk中调用函数suc(mk)时的函数调用语句，且CTS(null) =null.为不失一般性，调用链的递归裁剪遵循如下规则.

规则1设当前函数调用栈具有以下形式：(mbottom, …,M1,M2, …,Mn,M11,M12, …,M1n, …,Mk1,Mk2, …,Mkn, …,Mq1,Mq2, …,Mqp,mother, …)，其中，Mkn表示函数Mn的第k次递归调用，k≥1.Mqp表示函数Mp第q次递归调用,q>k,n≥p≥0.若∀i,j,k≥i,j≥1，式(2)得到满足，则调用栈可裁剪为(mbottom, …,M1,M2, …,Mn,Mq1,Mq2, …,Mqp,mother, …)，且FECF的o、t、z、e属性值保持不变，π中受到FECF影响的函数及其顺序不变.

SLEGS(CTS(Mi1))=SLEGS(CTS(Mj1))=SLEGS(CTS(Mq1))

SLEGS(CTS(Mi2))=SLEGS(CTS(Mj2))=SLEGS(CTS(M2))

(2)

SLEGS(CTS(Min))=SLEGS(CTS(Mjn))=SLEGS(CTS(Mn))

证明.

情形一：若在Mkn中无异常发生，n≥1，则无FECF的生成受到裁剪动作的影响.

情形二：假如异常x在函数Mkn中由raise/throw语句引发，k≥1，n≥1：① 若x在Mkn中捕捉，则会有与异常x相同的异常在函数Mn中由相同的raise/throw语句引发且被相同catch/except语句捕捉，因为Mkn与Mn为相同函数.② 若x从Mkn传播出去，则会有与异常x相同的异常在函数Mn中由相同的raise/throw语句引发且从相同的异常出口从Mn传播出去，因为Mkn与Mn为相同函数.

情形三：假如异常x通过CTS(suc(Mkn))语句从suc(Mkn)函数传播至Mkn中，k≥1，n≥1：① 若x在Mkn中捕捉，则会有与异常x相同的异常y通过CTS(suc(Mn))语句从suc(Mn)传播至Mn，且在Mn中由相同的catch/except语句捕捉.因为suc(Mn)与suc(Mkn)为相同函数，CTS(suc(Mn))与CTS(suc(Mkn))为同一函数调用语句，且SLEGS(CTS(suc(Mn))) =SLEGS(CTS(suc(Mkn))).② 若x从Mkn中传播出去，则会有异常x相同的异常y从Mn中的相同异常出口传播出去.因为suc(Mn)与suc(Mkn)为相同函数，CTS(suc(Mn))与CTS(suc(Mkn))为同一函数调用语句，且SLEGS(CTS(suc(Mn))) =SLEGS(CTS(suc(Mkn))).

2. 将调用栈callStack初始化为空;

3. Traverse_Invocation_Chain(m);

4. endfor

/*遍历以m开始的函数调用链，用Gen_FECF算法生成FECF实例*/

声明 Traverse_Invocation_Chain (m)

1. callstack.push(m); //维护调用栈，m入栈

2. for each 语句sinmthen

3. ifs是raise/throw语句then

4.Ψ←Gen_FECF(s,m);

6. else ifs是调用函数mcallee的语句then

7. ifmcallee在callstack出现过两次and

8. SLEGS(CTS(mcallee))=SLEGS(s) then

9. continue; //满足要求，裁剪

10. else then //继续分析调用链

11. Traverse_Invocation_Chain (mcallee);

12. endif

13. endif

14. end for

15. Callstack.pop(m) //维护调用栈，m出栈

2. existEPB← null

4. IfΨ.o=Ω.oandΨ.t=Ω.tthen

5. existEPB ←Ω; break;

6. endif

7. endfor

8. if null = existEPB then //暂无相应FECF簇

13. else then //将Ψ加入对应簇的EPB实例

14. existEPB.w← existEPB.w+φ(Ψ);

17. endif

18. endfor

4 基于Understand的自动分析工具

4.1 EPB自动分析工具的结构

采用本文提出的方法，用Python语言编写了一个基于Understand的EPB自动分析工具，其架构如图5所示.Understand是一款代码审核工具，提供了可操作源代码相关数据的API，如词法、语法、函数调用关系等信息.

图5 EPB自动分析工具架构Fig.5 Structure of automatic analysis tool of EPB

分析控制器:控制整个分析过程，包括:调用链的遍历分析、局部视图数据生成、FECF数据生成、EPB数据生成、函数调用栈的维护等.

局部视图生成器: 函数代码中与FECF生成相关的数据以文件形式存储，内容包括： ① raise/throw语句的位置、对应的异常类型；② 在当前函数被引发的异常捕捉情况，记录捕捉该异常的catch/except语句的位置及其对应的异常类型；③ 当前函数的函数调用关系信息；④ 当前函数中的函数调用语句是否处于异常保护区中，若是，则记录相应的catch/except语句位置及其对应的异常类型.

FECF生成器：当异常以raise/throw形式被引发时，结合相应的局部视图数据，根据Gen_FECF算法生成相应FECF数据.

4.2 EPB自动分析工具的使用步骤

自动分析工具进行EPB分析的主要步骤如下：

(1) 以源代码为输入，使用Understand软件生成程序的词法、语法、函数调用关系等数据.

(2) 以s为分析起点，s∈SEF，迭代分析其函数调用链，检查函数内是否有被raise/throw语句引发的异常.若存在异常，则转(3)；否则，继续按照(2)分析函数调用链中未被分析的函数，直到所有调用链分析完毕，转(4).

5 实验及其分析

为了验证本文方法及所开发的程序EPB自动分析工具的合理性和有效性，以OpenStack的核心组件作为对象进行了实验.

5.1 实验环境

实验在虚拟机上进行，操作系统为内核版本2.6.32的32位Linux，硬件配置为1GB内存，Intel(R) Core(TM) i3-3217U@1.80GHz单核CPU.实验负载为OpenStack(G 版本)中的5个核心组件，该软件用Python语言编写，各组件的SEF数据均根据相应的应用程序编程接口(application programming interface, API)文档人工收集而得.

5.2 实验结果与分析

对27 876行OpenStack组件的错误行为的实验结果见表2，其中duser=10 000表示用户指定的阈值.

表2 OpenStack组件错误行为分析结果Tab.2 Analysis results of erroneous OpenStack component behavior

调用链中函数调用点总量与函数数量的比值为10 408/1 426=7.3，说明每个函数平均被调用了7.3次，若差错在函数中引起异常，则该异常可潜在引起由7个不同ECF组成的FECF簇，表明从异常角度对差错及其对程序行为影响进行分析是可行的.

图6 nova组件中以w排序的前十个EPB实例数据Fig.6 Top ten EPB Ω ordered by w in nova components

6 结束语

本文通过故障注入实验研究了具有EHM的程序的软件故障、差错、异常之间的传播机理.结合FECF的描述，说明了如何利用ECF收集与异常相关的差错信息，建立了基于ECF的EPB模型，开发了基于该模型的EPB自动分析工具，并用该工具对OpenStack核心组件进行了错误行为分析，结果表明了基于ECF的EPB分析的合理性和有效性.该方法及其工具为具有EHM的大规模程序的EPB自动分析，指导程序异常处理结构的重构，使程序可精确捕捉异常，提高程序可靠性，并为构造合理的外部激励精确激活差错，缩短故障注入实验周期提供了有效手段.