基于全局超级块支配图的动态符号执行方法

摘要

本发明提供了一种基于全局超级块支配图的动态符号执行方法及其装置，属于计算机软件测试和软件安全领域。方法如下：获取被测可执行程序的控制流图，按支配关系相关理论转化为超级块支配图。对图中每个节点标“权”，并在每次符号执行前更新，“权”表示执行该节点最少能覆盖的基本块个数。在一次动态符号执行结束后，从超级块支配图中选择“权”值最大的节点，并生成对应的预测路径约束条件，然后用求解器求解生成新测试用例，驱动下次执行。本方案与已有技术相比，能够以最少的测试用例尽可能覆盖更多的代码块，有效提高代码覆盖率增长速度，缓解路径爆炸问题。本发明对提高动态符号执行测试大型应用软件的性能有重大的意义。

主权项

一种基于全局超级块支配图的动态符号执行方法，其特征在于包括以下步骤：1）、获得程序的控制流图和函数调用关系图； 2）、利用Boost图形库提供的支配树算法获得被测程序的立即前、立即后支配树；3）、合并立即前、立即后支配树形成函数基本块支配图；4）、合并函数基本块支配图中的强连通分量形成函数超级块支配图；5）、利用函数调用关系图将所有函数超级块支配图合并，形成全局超级块支配图，并为全局超级块支配图中的各节点设置初始权值，并标记为“未执行”状态；6）、为被测程序提供初始输入，并对被测程序插装，将被测试程序运行起来；7）、检测程序执行路径上是否有潜在的漏洞，并自动搜集路径约束条件；8）、利用执行过程中的基本块覆盖信息更新超级块支配图各节点的权值和执行状态；9）、根据超级块支配图的权值，从已执行路径上的所有分支中选择权值最大的分支节点；10）、从路径约束条件中找出第9）步选择出的分支节点对应的条件表达式，将该表达式取反，保留该表达式之前的约束条件，删除之后的，形成预测路径约束条件；11）、利用求解器求解预测路径约束条件，生成新测试用例，如果无解，则回到第9）步，重新选择分支；12）、如果还有新的测试用例生成，则代替初始测试用例回到第6）步续执行，否则表示所有的可执行路径分支都已被执行，则测试结束；所述步骤4）中所述合并基本块支配图中的强连通分量形成超级块支配图包括以下步骤：31）、从entry基本块开始到exit结束，如果相邻基本块节点相互支配，则合并为超级块节点，并删除两条相互指向的边，其他边保持不变；32）、如果新生成的超级块还有相互支配的相邻基本块，则根据31）的方法继续合并；将支配图中的所有强连通分量的节点合并成一个节点；33）、合并同向边，若相邻节点之间有两条以上同向边，则只保留一条；所述步骤8）具体包括以下步骤：41）、根据基本块覆盖信息文件，将已被执行的超级块全部标记为“已执行”状态；42）、从根节点开始以递归方式依次为各节点设置新权值，设置方式如下：如果当前超级块已被执行，则其权值=父节点的权值和；否则权值=父节点的权值和+本节点基本块的个数。