刘 杰，王嘉捷，任 栋，王清贤

(1.信息工程大学信息工程学院，河南郑州450002;2.中国信息安全测评中心，北京100085)

0 引言

符号执行［1］(symbolic execution)基本思想是用符号值代替程序的具体输入值，在模拟程序执行过程中计算路径的约束条件，求解约束条件并自动生成测试输入来遍历程序中的所有可行路径。

符号执行是一种路径敏感的分析方法，在遇到程序中分支语句、循环、嵌套调用等存在路径爆炸问题，产生的路径与程序内部判断分支的数量成指数级增长。为了缓解路径爆炸问题，提高测试覆盖率，研究人员提出了多种路径搜索策略。文献 ［2］采用了深度优先 (depth-first search，DFS)搜索方法，并试图在CFG上搜索与目标或未覆盖的分支的最短距离，该方法实际上程序目标代码覆盖率较低，而且这种静态搜索会生成不满足约束条件的不可达路径。为了快速覆盖到程序缺陷语句，需求驱动［3］(demand-driven)搜索方法首先选择一定的目标点，然后趋向于目标点的方向遍历生成执行树，如果发现执行的路径偏离目标点，则选择其它路径继续搜索。文献［4］提出混合符号执行 (hybrid concolic testing)思想，交互使用随机测试和符号执行以达到对程序状态空间的较深和较广的搜索，该算法适合于周期性的从运行环境中得到输入值的程序。SAGE［5］提出了代搜索 (generational search)策略，由种子文件驱动程序执行，在获取一条执行路径后离线分析程序路径约束并生成新一代测试用例，并采用覆盖率标准对测试用例的优先级排序，使得目标程序每一代的执行路径更加深入。文献 ［6］提出了最佳优先 (best-first search，BFS)搜索方法，采用启发式方法优先选取未覆盖的代码进行遍历，该方法提高了代码覆盖率但是仍缺乏遍历目标性。本文提出一种面向热点代码的路径搜索方法，研究单热点路径搜索方法的基础上，提出了多热点最短路径搜索优化策略，该方法生成覆盖热点代码的测试输入时效率高。

1 热点代码

当前软件安全测试领域的研究表明，程序热点代码(hot spot code)［7］中存在更多代码缺陷或安全漏洞，为了能够尽可能多的发现程序缺陷，软件安全测试更关心热点代码的执行情况。本文中热点代码是指程序中容易触发缺陷的代码块集合，热点代码主要有以下3种情况:

(1)圈复杂度 (cyclomatic complexity)［7］高的代码块:圈复杂度V(G)=E－N+2P，其中E表示控制流图边的数量，N表示节点数量，P表示控制流图连接子图数目 (通常为1)。较高的圈复杂度预示着难以理解的代码，很可能比较脆弱或存在缺陷。

(2)包含危险函数的代码块:处理外界环境引入的不可信输入数据，但是边界检查不严格的函数。如字符串处理函数strcpy，strcat等，包含危险函数的代码块容易触发缓冲区漏洞。

(3)包含危险指令的代码块:操作数被外界环境引入的不可信输入数据污染，包含可能触发程序异常甚至篡改执行顺序等操作的指令，如跳转 (jmp)、调用 (call，ret)以及数据转移的目的地址 (rep movs)等，包含危险操作的代码块容易引起程序异常甚至安全漏洞。

热点代码识别定位可通过程序静态分析方法实现。生成程序的控制流图，通过代码度量方法识别第1种热点代码;通过函数和指令扫描识别和定位第2、3种热点代码，热点代码记为集合

2 面向热点代码的路径搜索

识别程序的热点代码后，本文期望在路径搜索中优先生成能够覆盖热点代码的测试数据。为了便于描述路径搜索算法，给出定义如下:

给定程序P的输入向量I，则P的执行过程对应一条执行路径w。路径w是若干条顺序执行的语句组成的序列，记为:w={l1，l2，…，li|i∈N}。用 w［l0，ln］表示所有以 l0为起点，以ln为终点的路径。用w(l0，ln］表示所有以l0后继节点为起点，以ln为终点的路径，用w［l0，ln)表示所有以l0起点，以ln前驱节点为终点的路径，使用|w|表示路径长度。

符号执行的路径条件和路径之间有以下性质:对于任意程序路径w，给定输入向量I，程序P执行路径w当且仅当输入向量I满足w的路径约束φw。

2.1 DFS路径遍历

符号执行方法的路径遍历过程如下:给定初始输入生成一条初始路径，将执行路径上的分支语句的路径条件逐个取反生成新路径，求解新路径约束条件并生成能够引导程序执行进路径的输入数据，继续上述遍历过程直到所有的程序路径都至少覆盖一次结束。如图1所示的符号执行树，Entry节点是程序入口，w1为初始执行路径，路径约束为φw1={PC1∧PC2∧PC3}。将初始路径上的路径条件依次取反，那么相应的路径约束分别为:

图1 符号执行树遍历过程

DFS搜索方法每次将符号执行树上尽可能深的分支语句的路径条件取反，直到该分支遍历完毕后回溯到前一个分支继续遍历，通常对于一个有d个分支语句的程序，该方法生成2d条程序路径。由于DFS搜索方法生成的2d条路径中仅少部分路径能够覆盖热点代码;而且搜索策略会优先搜索路径w1(如图1)，直到w2及其后续路径遍历完成后才开始搜索可达热点代码的路径w3，因此该方法效果不理想。基于DFS等搜索方法用于热点代码覆盖测试时效率低，原因有以下三点:

(1)未考虑当前执行路径与热点代码之间的可达性，如果当前分支与热点代码之间没有可达路径，仍然会持续深度优先搜索并生成一系列无效测试用例;

(2)路径遍历过程中将当前节点的孩子节点或兄弟节点的路径条件取反生成新的执行路径，未考虑该执行路径上多个判断分支节点与热点代码之间的距离;

(3)路径遍历过程中每一轮将当前执行路径上的一个分支语句的路径条件取反，即在符号执行树上前进一个分支，路径搜索效率低。

2.2 热点代码最短路径搜索算法

在面向热点代码的覆盖测试中可通过基于程序控制流图的静态分析方法优化，文献［8］提出了基于控制流导向的路径搜索策略对DFS方法做了改进，但是静态搜索的路径可能在实际执行时不可达。本文通过在程序控制流图上搜索能够到达热点代码路径，并生成路径约束判断路径可达性，引导遍历过程快速覆盖热点代码。

程序控制流图 (control flow graph，CFG)可以用四元组G=(N，E，Entry，Exit)表示，其中N是节点集合，每个节点是一个具有唯一出口和唯一入的基本代码块，E是边的集合，每条边是一个有序节点对〈Ni，Nj〉，他表示从Ni到Nj可能存在控制转移，Entry表示程序的入口节点 (只有一个)，Exit表示出口节点 (可能不止一个)。在程序CFG上的热点代码最短路径搜索包括以下两个步骤:

(1)分支语句与热点代码之间的最短路径搜索。对于程序执行路径w，在程序CFG上搜索条件路径wc={c1，c2，…，ci|i∈N}中的分支语句与热点代码h之间的最短路径。该问题与单源最短路径问题类似，通过迪杰斯特拉算法求解。搜索结果为最短路径集合{w［ci，h］|i∈N}，并按照路径长度排序，如果没有可达路径则|w［ci，h］|=∞ 。

(2)最短路径的约束条件。从程序入口到热点代码的完整路径 w=w［l0，ci］∪w［ci，h］，由从程序入口到某分支语句的前段路径wp=w［l0，ci］和分支语句到热点代码的后段路径 ws=w［ci，h］两段路径组成。由于路径 w［l0，ci］是程序的真实执行路径，路径约束可满足;而w［ci，h］是静态分析得到的路径，路径约束可能不满足。通过符号执行方法计算φs的路径约束。完整的路径约束为φw=φp∧φs。

图2给出了面向热点代码的最短路径搜索算法，该算法采用多轮搜索方法，每轮选定当前路径与热点代码h的最短可达路径生成测试用例t驱动程序执行，最终返回能够覆盖热点代码h的程序路径w。

2.3 多热点代码路径搜索优化

对于程序中的热点代码集合H={h1，h2，…，hi|i∈N}，图2所示的算法可逐个对热点代码进行覆盖测试。由于搜索过程中存在多个热点代码被同一条执行路径覆盖的情况，或者多个热点代码的最短路径经过了当前执行路径w的同一个分支语句ci，即存在公共路径。为了减少冗余路径，更快的覆盖热点代码集合，对于多热点代码搜索问题有以下3种优化策略:

(1)多热点代码最短路径搜索。在程序CFG上搜索条件路径中的分支语句与热点代码集合之间的最短路径。类似于多源最短路径问题，采用弗洛伊德算法求解。

图2 面向热点代码的最短路径搜索算法

(2)测试用例t的选取:对于搜索到的热点代码最短路径集合{w［ci，hn］|i，n∈N}，优先选取能够覆盖多个热点代码的程序路径或者经过相同分支语句ci的测试用例t。如果发现wn执行路径能够覆盖热点代码hn，则将hn从热点代码集合H中删除，继续搜索其它热点代码的最短路径。

(3)不可达子路径消除。到达热点代码hm和hn之间存在公共子路径子路径的路径约束有以下性质:对于程序路径w的一个子路径w'，w'是连续的且w'∈w，如果φw约束可满足，那么对于约束可满足;反之，如果-w'，w'∈w，如果φw'约束不可满足，则必有φw约束不可满足。

图3所示不可达子路径消除的辅助算法，该算法输入当前条件路径wc和热点代码集合H，采用自动学习方式收集搜索过程的不可达的子路径，用于后续路径的可达性判断。根据子路径约束的性质，对于每轮搜索到的最短路径首先判断是否包含Θ中的某条不可达路径，如果是则不可达;该策略可省去计算的路径约束和约束求解的开销。算法最后输出到达热点代码的最短路径及其路径约束集合Wmin。

3 实验及分析

实现了一个基于微软的编译器架构Phonix［9］的路径搜索插件HotTrace，Phonix支持对高级语言编译器前端产生的代码中间表示进行分析、优化和测试，能够为外部插件提供丰富的分析代码库。HotTrace提取程序的控制流图CFG，根据静态分析结果在CFG标识热点代码位置;基于Phonix生成的中间表示IR上运行符号执行引擎，收集条件路径的约束条件;采用微软开发的Z3［10］求解器进行路径约束求解。

图3 不可达子路径消除算法

测试对象为Verisec Security Benchmark［11］集合 (Verisec 0.2，经典的缓冲区溢出缺陷测试代码集，收集了12个开源软件的发生缓冲区溢出缺陷的真实代码片段)中的4个程序，如表1所示。其中定位的热点代码为:WU-ftpd［linkpath-strcpy-strcat］、Sendmail［arr-chars-bad］、OpenSER［full-ptr-bad］、Apache［prefix-ptr-bad］。

实验过程:由于4个程序都是读取函数参数作为输入数据，首先给定初始参数;分别采用BFS［6］方法和HotTrace方法进行路径搜索，生成新的输入参数并驱动程序执行;程序执行过程中检测热点代码的覆盖情况。当BFS方法和HotTrace方法对热点代码的覆盖率超过90%时，终止测试过程。

测试结果见表1，与BFS方法相比，HotTrace在达到同样的热点代码覆盖率 (90%)时，需要遍历的执行路径数量减少了68.6%。路径搜索时间减少了近2/3。HotTrace方法对于热点代码覆盖效率有较大提高。对实验结果的进一步分析如下:

(1)实验过程中有少部分热点代码没有覆盖到，原因是HotTrace采用的最短路径搜索策略是一种贪心算法，搜索CFG得到的最短路径可能不可达，而实际可达路径却不是最短路径。实际情况下要求测试覆盖率达到100%是不可能，HotTrace的目标是快速覆盖代码热区。

(2)引入不可达子路径消除对于路径可达性分析有很大贡献，HotTrace在实验过程中收集了约1600条不可达子路径，利用这些路径在后续路径判断中直接排除5000多条路径。由于对程序路径的符号执行和约束求解运算相对耗时较多，该策略有效降低了分析时间。

(3)HotTrace通过分段路径约束方法生产的测试输入在程序实际执行未能覆盖预期的最短路径，实验中测试输入的失效率为42%，跟踪分析发现符号执行在遇到符号化地址和循环时运算不精确，导致最短路径采用静态符号执行分析计算路径约束时有较大误差，该问题是静态符号执行的固有问题，通过循环优化和指针推理方法优化路径约束计算。

表1 基准程序测试结果

4 结束语

热点代码 (hotspot)是程序缺陷的多发区。本文提出面向热点代码的路径搜索方法，结合了静态分析 (快速搜索最短可达路径)和动态分析 (判断路径约束条件进一步判断路径可达性)的优势，与BFS及引入随机搜索的启发式搜索方法相比更有针对性。本文提出了单热点搜索算法和多热点搜索优化策略，实验结果表明该方法达到相同热点代码覆盖率情形下能够有效减少生成的测试路径数量。

［1］Corina SW.Visser:A survey of new trends in symbolic execution for software testing and analysis［J］.International Journal on Software Tools for Technology Transfer，2009，11(4):339-353.

［2］Burnim J，Sen K.Heuristics for scalable dynamic test generation［C］//Proceedings of the 23th International Conference on Automated Software Engineering.L'Aquila，Italy，IEEE Computer Society Press，2008:443-446.

［3］Anand S，Godefroid P，Tillmann N.Demand-driven compositional symbolic execution［C］//Procee-dings of 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems.Berlin，Heidelberg:Springer-Verlag，2008:367-381.

［4］Majumdar R，Sen K.Hybrid Concolic testing［C］//Proceedings of 29th International Conference on Software Engineering.DC，USA:IEEE Computer Society Press，2007:416-426.

［5］Godefroid P，Levin M，Molnar D.Automated whitebox fuzz testing［C］//Proceedings of the 15th Annual Network and Distributed System Security Symposium.San Diego，CA:Internet Society Press，2008.

［6］Cadar C，Ganesh V，Pawlowski P M，et al.Exe:Automatically generating inputs of death［J］.ACM Transactions on Information and System Security，2008，12(2):1-38.

［7］Viet Hung Nguyen，Le Minh Sang Tran.Predicting vulnerable software components with dependency graphs［C］//Procee-dings of the6th International Workshop on Security Measurements and Metrics.Bolzano，Italy:ACM Press，2010.

［8］Saparya K，HSIAO S，Loganathan L.Strategies for scalable symbolic execution-driven test generation for programs［J］.Science China Information Sciences， September， 2011， 54 (9):1797-1812.

［9］Phoenix-Microsoft research［EB/OL］.［2010-10-04］.http://research.microsoft.com/en-us/collaboration/focus/cs/phoenix.aspx.

［10］Z3.An efficient SMT solver［EB/OL］.［2010-10-01］.http://research.microsoft.com/en-us/um/redmond/projects/z3/.

［11］Ku K，Hart T E，Chechik M，et al.A buffer overflow benchmark for software model checkers［C］//Proceedings of 22th International Conference on Automated Software Engineering.NY，USA:ACM Press，2007:389-392.