一种软件脆弱性自动分析定位的方法

王同磊，陈朝晖

0 引 言

由于软件本身存在脆弱性，成为系统可靠性、安全性受到威胁的根本原因.软件脆弱性本质上是软件中存在的弱点、缺陷，被激活利用后会致使软件违反安全性需求或是违背预期功能，导致信息的丢失、系统价值和可用性的降低，致使软件发生安全性故障[1].对于航空航天领域中使用的多种嵌入式软件，其安全性Safety——软件运行时不引起危险、灾难的能力，尤为重要.此类嵌入式软件多数与硬件捆绑试飞，由于研制周期短、经费不足、测试不充分等因素，致使许多软件缺陷考核不到，安全隐患被保留下来，而一旦在某种极端条件或环境下，软件脆弱性被激活导致安全性故障，则会造成严重的后果.由此，设计一种软件脆弱性自动分析定位的方法具有重要意义.

CHRIST等[2]提出了一种控制流敏感的定位方法.该方法使用控制流信息来识别失败执行轨迹中不相关条件分支，判断失败相关的条件分支真值，生成更有意义的失败解释来进行定位.SUN等[3]提出了一种根据代码优先级策略和程序切片技术进行定位的启发式方法.ZHANG等[4]提出了一种基于动态切片的定位方法.在明确程序输出的前提下定义切片准则，从而计算数据切片、全切片和相关切片，进而使用程序切片有效分离出错误相关语句来进行定位.国防科大的YAN等[5]提出了一种使用改进的后向切片算法进行定位的方法.使用一种类似动态后向切片算法来平衡问题规模与精度，并结合统计分析方法以改善定位效率.JIANG等[6]基于程序切片、动态信息和静态信息相结合，提出了一种空指针异常的定位方法.该方法在实时堆栈的指导下进行程序切片，在切片后的程序上进行空指针和别名分析，解决了空指针异常的定位问题.

在众多定位方法中，基于程序谱的定位方法是一种很有前途的定位方法[5]，是当前程序定位领域最热门的研究点之一，其原因主要有两点：一是，程序谱易于存储，方便操作；二是，该定位技术已经被证明有较高的效率.该方法通常通过执行测试用例动态收集覆盖信息及测试结果并据此构造程序谱，然后选用适当的统计量根据程序谱计算语句的可疑度，最后对各语句进行可疑度大小排序来进行定位.

程序切片[7]技术利用程序语句的数据依赖和控制依赖关系将关注点聚焦于程序语句的一个子集，该子集内语句的执行会影响程序的输出，由于使用了数据依赖和控制依赖关系，对于程序语句与程序失败的关系的理解上，程序切片要强于覆盖信息，研究表明[8]，程序切片在识别导致错误输出的语句子集方面有较高的效率.

综上，本文面向航空航天等领域的C语言嵌入式软件，基于程序谱的整体定位思路，对现有的基于静态依赖分析的前向计算动态切片方法进行改进，设计了一种软件脆弱性自动分析定位的方法.

1 软件脆弱性定位思路

给定待检测程序P和测试用例集T, 本文设计的软件脆弱性自动分析定位的实现流程如下：

1)将运行时验证的监控器计算出的违背正确性属性的程序输出语句n及其引用变量v作为计算程序切片的输入之一，即程序切片的切片准则；

2)运行测试用例Ti(Ti∈T),计算以为切片准则的动态程序切片，并标注测试用例Ti是否暴露了软件脆弱性；

3)根据计算出的程序切片构造程序切片谱；

4)选取统计量，统计计算程序语句的脆弱性可疑度，并按可疑度值降序排序，生成脆弱性定位分析报告.

2 程序切片计算

程序切片是由M WEISER[7]提出的一种重要的程序分析理解方法.给定程序P、程序点s和变量v，其程序切片为当程序执行到s时，P中所有直接或间接对变量v有影响的语句集合.其中称作切片标准.

程序切片分为两种：动态切片和静态切片.静态切片技术是指在计算程序切片时使用的是静态的数据流和控制流分析方法.通常，静态切片相对保守，很多时候，静态切片几乎与整个程序相当，所以使用静态切片进行软件脆弱性定位效率不高.动态切片技术由在特定输入下影响兴趣点处的兴趣变量的语句构成.相对于静态切片，动态切片只针对特定的输入，每个特定的输入下，动态切片的规模更小，精度更高，更加有利于软件脆弱性定位.

动态切片的概念被提出之后即被深入研究，执行切片由此产生.程序的执行切片，即在特定输入下执行覆盖的语句集合，其优点是在构造时计算资源消耗很少，同样也存在明显的缺点，即语句间的依赖关系考虑不足.执行切片常用来与其他切片方法组合构成混合切片，如文献[5]中将执行切片与静态切片取交集构成一种新的混合动态切片.

通常计算动态切片需要追踪程序的执行，以建立程序动态依赖关系，其执行代价较高，因此需要在不降低精确度的情况下减小其代价.提高动态切片效率的一个有效方法是利用静态信息以减少程序执行时的动态追踪量.基于静态依赖分析的前向计算动态切片方法的最大优点是不需要计算程序的动态依赖图，且切片结果精确[9].这种方法的基本思想如下：

1)构造程序静态依赖图PDG；

2)每执行一条语句，即遍历PDG，匹配执行轨迹，计算到当前语句为止的动态切片；

3)执行完切片准则语句后，即得到所需的动态切片.

上述基于静态依赖分析的前向计算动态切片算法存在以下几个问题：

1)大型程序，其依赖图很庞大，需要很大的存储空间；

2)静态依赖图的建立时间消耗大；

3)计算切片时遍历静态依赖图时间消耗大.

以上问题将很大程度上影响动态切片计算方法的性能，本文针对以上几个问题，对基于静态依赖分析的前向计算动态切片的算法进行了改进.

易见的，程序依赖图中很大一部分是数据依赖，对于上述基于静态依赖分析的前向计算动态切片的方法，在数据依赖方面，我们需要存储各变量的最新定义语句，以及当前执行语句引用了哪些变量，本文通过一个自定义结构体数组来避开程序静态依赖图中的数据依赖图的遍历，该结构体有两个属性，第一个是变量名称，第二个是最新定义该变量的执行历史记录(execution history, EH)序号.该结构体定义如下：

public struct strtVarDef

{

public string strVarName;

public int iEHNo;

}

根据执行历史记录，若当前执行语句定义了新的变量，则将定义的变量名称及其执行历史记录的序号添加到该结构体数组中；若当前执行语句定义的变量已经记录在该结构体数组中，则更新其执行历史记录序号.

下面给出一个具体的程序示例.

图1 示例程序Fig.1 Program code

对于图1所示的源程序，图2给出了算法改进前后的程序依赖图对比，左边部分为算法改进前的程序静态依赖图，右边部分为算法改进后的程序控制依赖图及给定动态切片准则下各变量的最新定义执行记录序号.图中可以很明显的看出，改进后的依赖图变得非常“轻便”，这是因为，程序的静态依赖图包含控制依赖图和数据依赖图，而数据依赖图中存储的是程序中全部的数据依赖关系，包括程序执行过程中的一些历史数据依赖关系，而在计算程序动态切片时，只需要知道当前程序中某一变量的最新定义语句即可，据此，对原有算法进行改进，只存储较为简单的控制依赖关系，数据依赖关系采用自定义的结构体数组来存储，该数组中只存储某一变量的最新定义语句，不存储其过程定义语句.图2 中可以看出，改进后的算法，大大降低了存储空间，减少了程序依赖图的建立及遍历时间消耗，从而提高了计算程序动态切片的效率.

算法1给出了改进后的前向计算动态切片方法.算法以源程序及动态切片准则为输入，输出程序的动态切片.算法主体通过一个“do-while”循环来完成动态切片的计算，首先将获取到的新的执行记录的程序语句(语句01)添加到当前切片集中(语句02)，然后将当前执行记录中全部引用变量的最新定义执行记录的动态切片添加到当前动态切片集合中(语句06至语句08)，其中函数getDef(v)的功能为获取变量v的最新定义执行历史记录序号，DS(s_Def,Ti)为变量的最新定义执行历史记录的动态切片，最后，将当前执行记录的程序语句的控制依赖语句的动态切片添加到当前动态切片集合中(语句11、12).循环中对动态切片准则中的语句进行了特殊处理(语句03至语句05)，语句09、10为自定义结构体数组strtVarDef的跟新部分.

对于图1的示例程序，给定程序的动态切片准则<18,z,(1,2,0,3)>，表1展示了使用改进后的算法前向计算程序动态切片的详细过程.最终计算得到的动态切片为语句子集{1,2,3,4,5,6,9,10,11}，该切片准则下的执行切片为语句子集{1,2,3,4,5,6,9,10,11,17}；静态切片为语句子集{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}，可以看出使用改进后的算法计算得到的程序动态切片最为精确.

图2 算法改进前后依赖图对比Fig.2 Comparison of the dependence graph between the original algorithm and the improved one

EHStLinestrtVarDef[]Ref(s)/vCD(s)slice_current11{(N,1),(a,1),(b,1),(c,1)}——122{(N,1),(a,1),(b,1),(c,1),(i,2)}——233{(N,1),(a,1),(b,1),(c,1),(i,2),(z,3)}——344{(N,1),(a,1),(b,1),(c,1),(i,2),(z,3)}i,N—4,2,155{(N,1),(a,1),(b,1),(c,1),(i,2),(z,3)}i45,2,4,166{(N,1),(a,1),(b,1),(c,1),(i,2),(z,3)}i,b56,2,1,5,479{(N,1),(a,1),(b,1),(c,1),(i,2),(z,3),(x,7)}i69,2,6,1,5,4810{(N,1),(a,1),(b,1),(c,1),(i,2),(z,3),(x,7),(y,8)}a,x610,1,9,2,6,5,4911{(N,1),(a,1),(b,1),(c,1),(i,2),(z,9),(x,7),(y,8)}x,y,z511,9,2,6,1,5,4,10,31017{(N,1),(a,1),(b,1),(c,1),(i,10),(z,9),(x,7),(y,8)}i417,2,4,1114{(N,1),(a,1),(b,1),(c,1),(i,10),(z,9),(x,7),(y,8)}i,N—4,17,2,11218z—11,9,2,6,1,5,4,10,3

基于以上改进后的算法，本文设计了切片工具，利用图1中的示例程序(xyz_f)以及Siemens测试套件中的print_tokens程序进行了实验.其中“xyz_f”程序共56行代码，“print_tokens”程序共609行代码.详细实验对比数据见图3，其中横坐标为执行记录数，纵坐标为使用改进后的算法计算动态切片相比改进前所用时间缩短的百分比.从图3可以看出，改进后的切片计算时间缩短了10%到20%左右，并且随着程序规模(代码行数及执行记录数)的增大，时间缩短的比例更大.

3 软件脆弱性定位

在得到程序动态切片后，即可构造程序切片谱.程序谱定义如下：

图3 改进后切片计算时间缩短比例Fig.3 Percentage of the time reduced

若程序P有n条语句，测试用例集T=TF∪TP={T1,T2,…,Tm}，其中TF={T1,…,Ts)表示失败测试集合，TP={Ts+1,…,Tm)表示成功测试集合，则程序谱是一个二维矩阵，如下：

程序切片谱是对程序谱的优化，它将程序谱中元素限制在程序切片中，一方面降低了矩阵规模提高效率，另一方面加入了程序实体之间依赖关系的考虑提高了定位的准确度.对程序切片谱进行统计分析，对于切片谱矩阵中的每个程序语句s定义以下4个统计量：

1)a00(s)表示未经过语句s也未导致脆弱性暴露的测试用例的个数；

2)a01(s)表示未经过语句s但却导致脆弱性暴

露的测试用例的个数；

3)a10(s)表示经过了语句s但未导致脆弱性暴露的测试用例的个数；

4)a11(s)表示经过了语句s并且导致脆弱性暴露的测试用例的个数；

采用如下公式计算语句的脆弱性可疑度.该公式由NAISH等[10]提出并被后续研究者XIE等[11]通过理论分析证明了其定位效果最优，公式如下：

(1)

对各语句的脆弱性可疑度值降序排序，可疑度值最大的语句即为软件脆弱性根源所在.

4 实例验证分析

基于上述定位方法，设计开发了一套软件脆弱性自动分析定位的工具.对图1所示的示例程序，人工注入一条错误，即语句10：y=a*4*x，正确应为y=a*x，该错误将导致在语句18处发现软件脆弱性征兆.设计如下测试用例，未暴露程序脆弱性的测试用例为：(3,2,5,6)、(4,3,7,9)、(6,5,10,3)、(5,2,9,4)、(13,4,24,7)、(5,6,7,8)；暴露程序脆弱性的测试用例为：(8,3,2,6)、(7,5,3,1)、(9,6,5,2)、(9,7,3,8).

使用设计开发的定位工具对问题程序进行脆弱性自动分析定位.定位工具支持对包含多个源代码文件的程序进行脆弱性定位，图1示例程序中的函数“read(N,a,b,c)”、“f1(x,y,z)”、“f2(x,z)”均在单独的函数功能实现文件中，变量N设定为全局变量.使用定位工具进行脆弱性分析最终得到的定位报告如图4所示，图中可以看到，可疑度值最大的语句中包含问题语句“y=a*4*x”，即使用该工具定位到了导致脆弱性的根源所在.

图4 脆弱性定位报告Fig.4 The report of localization

5 结 论

本文设计了一种软件脆弱性自动分析定位的方法，该方法基于程序动态切片技术，对现有的前向计算动态切片的算法进行改进，并通过实验验证了提升计算效率的有效性，以计算得到的切片集合构造程序切片谱，统计分析切片谱进行脆弱性定位分析.最后，通过实例验证，本文设计的软件脆弱性定位工具支持包含多个C语言源代码文件的项目，经前述的各个步骤之后，最终可以定位到导致软件脆弱性的根源所在，验证了该方法的有效性.

参 考 文 献

[1] 黄明, 曾庆凯. 软件脆弱性分类属性研究. 计算机工程, 2010, 36(1):184-186.

HUANG M, ZENG Q K. Research on classification attributes of software vulnerability[J]. Computer Engineering, 2010, 36(1):184-186.

[2] CHRIST J, ERMIS E, SCHAF M, et al. Flow-sensitive fault localization[J]. Verification, Model Checking and Abstract Interpretation Lecture Notes in Computer Science, 2013, 7737:189-208.

[3] SUN J, LI Z, NI J, et al．Software fault localization based on testing requirement and program slice[C]//International Conference on Networking, Architecture, and Storage. New York: IEEE, 2007:168-176.

[4] ZHANG X, HE H, GUPTA N, et al. Experimental evaluation of using dynamic slices for fault location[C]//The 6thinternational symposium on Automated analysis-driven debugging. Monterey, California, USA, 2005:33-42.

[5] LEI Y, MAO X G, DAI Z Y, et al. Effective statistical fault localization using program slices[C]//The 36thAnnual Int Computer Software and Applications Conf. Los Alamitos, CA: IEEE Computer Society. New York: IEEE,2012.

[6] JIANG S, LI W, LI H, et a1. Fault localization for null pointer exception based on stack trace and program slicing[C]//The 12thInternational Conference on Quality Software. New York: IEEE, 2012：9-12.

[7] WEISER M. Program Slicing[C]//In Proceeding of ICSE’81 of the 5thInternational Conference on Software Engineering, 1981.

[8] ZHANG X, GUPTA N, GUPTA R. A study of effectiveness of dynamic slicing in locating real faults[J]. Empirical Software Engineering, 2007,12: 143-160.

[9] ZHANG X, TALLAM S, GUPTA N, et al. Towards locating execution omission errors[J]. Acm Sigplan Notices, 2007, 42(6):415-424.

[10] NAISH L, LEE H J, RAMAMOHANARAO K. A model for spectra-based software diagnosis[J]. ACM Transactions on Software Engineering and Methodology, ACM, 2011, 20.

[11] XIE X, CHEN T Y, KUO F C, et al. A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization[J]. ACM Trans on Software Engineering and Methodology, 2013, 22(4)：1-40.