控制流污点信息导向的符号执行范文

《中国科学技术大学学报》2016年第一期

摘要：

以快速生成能够覆盖可能存在缺陷程序点的测试用例为目标，结合基于生成的Fuzzing技术、静态程序控制流分析、静态污点分析等手段，提出一种导向式动态符号计算方法．通过Fuzzing生成能够到达包含缺陷程序点的函数的测试用例，作为种子输入驱动符号执行快速到达缺陷函数；在缺陷函数内利用静态控制流分析、静态污点分析计算出控制流污点可达程序切片，基于该切片进行朝向缺陷点的多路径动态符号执行．实验验证了方法能够有效减轻符号执行应用中广泛存在的路径爆炸问题，并且能生成触发目标缺陷的测试用例．

关键词：

控制流分析；污点分析；导向式符号执行

随着机器计算能力和约束求解能力的不断提升，近年来动态符号执行技术发展迅速．在整数、位向量理论的表达范围内描述程序的操作语义，以关于输入变元约束等价类的形式刻画程序的路径空间，符号执行技术能够实现对目标程序的精确分析、路径空间的高效覆盖，已成为面向大规模预的二进制软件缺陷发掘的最佳选择之一［1－3］．符号执行往往关注于目标程序的全部路径空间，然而该空间并不总能被完全覆盖［4］．适度的搜索空间约减是使该技术实际可行的关键．尽管当前相关的研究（包括限制循环次数［5－6］、选择式符号执行［7］、符号执行并行化［8］等）在某些场景中被证明为有效，基于符号执行的缺陷发现技术依然不足以在实际应用中为大型程序的安全性分析提供支撑．缺陷挖掘过程中常常关注于这样的应用场景：给定缺陷程序点θ，求解能到达θ并触发目标缺陷的输入实例．在这一情况下，分析引擎可以不关注于完整的路径空间，仅仅针对那些能够到达θ的路径集合进行安全分析．由此，本文提出一种结合基于生成的Fuzzing测试［9］、静态控制流分析、静态污点分析、动态符号执行等技术的程序分析方法，通过有导向性的路径分析确定出目标程序点的污点控制流依赖关系，自动生成能够到达目标程序点并触发对应缺陷的输入实例．

1系统框架

系统框架如图1所示，包括6个部件：良构输入生成器、执行监视器、静态控制流分析引擎、静态污点分析引擎、动态符号执行引擎和缺陷验证器．在给定目标程序P和P中已知的缺陷程序点θ、程序良构输入对应的协议规约τ的情况下，良构输入生成器应用基于生成的Fuzzing技术生成满足τ的良构种子输入，交由执行监视器监视其在P中的执行轨迹，从中筛选出能够到达θ点所在函数f的良构输入集合Inputs；静态控制流分析引擎计算出函数f到程序点θ的所有静态可达的控制流路径集合CFGslc．静态污点分析引擎基于CFGslc，结合动态污点分析得到的函数f入口点的污点状态，应用流敏感的控制流污点分析，筛选出能将污点输传播到θ程序点处敏感操作数的路径集合CFGt－slc．动态符号执行引擎综合Inputs执行轨迹和CFGt－slc蕴含的路径信息，引导符号执行进行朝向θ的安全分析．缺陷验证器最终对获取的输入实例进行测试，确认是否能触发θ点处的目标缺陷．

2控制流污点信息计算

静态控制流污点信息计算包括两个部分：控制流信息计算和污点信息计算．这部分工作实现基于Binnavi二进制分析平台［10］．

2．1静态控制流分析给定目标程序P和脆弱程序点θ，本文的静态控制流分析首先确定出包含θ的函数f．对包含θ的模块M，构造过程调用图CG和由每个函数funci的过程内控制流图cfgi构成的集合CFG．其间对于M中存在的间接跳转、间接调用等情况，本文采用跳转表识别、具体输入执行记录分析等手段补足控制流信息。

2．2污点信息计算上节的算法能够计算出目标函数f入口点到目标程序点θ的静态控制流可达切片CFGslc．然而，并非沿着该切片执行的所有路径都能够将外部输入相关信息（污点信息）传播到θ处的敏感操作数λ．需要计算出能够将污点传播到λ的基本块序列．静态污点分析［11］一般以外部输入的读取位置（诸如Linux系统下的read函数调用点）作为污点引入点，将相关的读取缓冲区内容标记为污点操作数，沿着程序控制流图（一般就单个可执行程序模块而言）计算污点数据流信息，考察关键程序点（sink）处敏感操作数的污点状态．然而在二进制分析背景下，污点数据的读取位置可能不在包含目标函数f的模块内，导致无法在对该模块的数据流分析中引入污点信息．本文采用了一种动态污点分析和静态污点分析结合的方法．首先由动态污点分析，以基于生成的Fuzzing筛选出的能够到达函数f的良构输入集合Inputs为种子输入，计算出在函数f入口点处的污点程序状态（包括寄存器、内存等）Statef，静态污点分析引擎随之将2．1节中计算出的目标函数f入口点到目标程序点θ的控制流可达切片CFGslc标准化（确保CFGslc中入口点entry只有一个入口边，出口点exit只有一个出口边），提升所有二进制指令为vine中间语言，并转换为静态单赋值形式，在图4所示的控制流污点格上进行流敏感的正向数据流分析．

3导向式符号执行

大型程序路径状态空间庞大，能到达目标程序点的路径数量则相对较小．在限定计算资源的情况下分析引擎对这部分路径的覆盖概率较低．导向式符号执行首先基于目标程序的控制流图计算出目标程序点控制流可达路径，仅仅对这部分路径进行分析．由此确保了在资源限定的情况下，可以生成能够到达目标程序点的输入实例．然而，在二进制程序分析背景下，当前导向式符号执行存在如下问题：（Ⅰ）二进制程序运行时包含多个可执行模块，计算程序路径所需要的完整的控制流图往往并不可得，一般只能关注于可执行程序自身模块的控制流计算．对于目标程序点在其它动态可加载模块的情况并适用；（Ⅱ）程序的执行路径不仅与程序的控制流相关，同时也与其数据流相关．为便于计算可达路径，当前控制流分析一般将控制流图中循环结构的回边、调用图中递归结构的回边略去．由此导致那些能够到达目标程序点同时触发缺陷的程序路径，由于在对循环等关键程序结构的遍历中并不遵从分析假定的简单模式而被丢弃．图5导向式符号执行Figure5Directedsymbolicexecution针对上述问题，结合“缺陷程序点所在函数往往包含在良构输入的处理路径中”这一启发式原则［13］，本文提出一种单路径具体－符号混合分析和多路径符号分析相结合的方法．如图5所示（图5中实线表征符号执行实际分析的程序路径，虚线表示控制流可达而符号执行并未进行分析的程序路径），以包含目标程序点θ的函数f为界，在程序入口点到函数f入口点之间，利用基于生成的Fuzzing技术构造的能够到达函数f的良构种子输入I驱动符号执行引擎进行“严格遵循I执行轨迹”单路径符号执行，记录f入口点的程序机器状态（包含具体机器状态和符号机器状态）SCStatef；在函数f入口点到目标程序点θ之间，则以SCStatef为初始状态，基于第3节中计算出的控制流污点可达切片进行“忽略不相关路径”的导向式多路径符号执行.

4实验分析

基于Fuzzing平台Peach［14］、二进制静态分析平台BinNavi和全系统动态符号执行平台S2E［15］，本文构建了面向缺陷程序点的导向式二进制程序符号执行原型系统，以WindowsXPProfessional版本2002ServicePack3操作系统平台下实际公开的程序缺陷为数据源对方法有效性进行了验证实验，其中缺陷程序点通过人工分析缺陷成因确定．缺陷的主要信息如下：对上述给定缺陷，利用基于生成的Fuzzing技术构造出能够到达bug函数的种子输入，驱动符号执行沿单路径快速到达bug函数，进而在bug函数内朝向bug程序点进行导向式路径分析，成功生成能够到达缺陷程序点的测试用例．本文从基本块约减、路径约减两方面对提出的“忽略不相关路径”的导向式多路径符号执行的计算性能进行分析．表2给出了目标函数内基本块约减情况．其中PreBlocks表征约减分析前目标函数内联基本块的数目，PostBlocks表征约减分析后目标函数内联基本块的数目．

5结论

本文对面向给定程序点的测试用例快速生成技术进行了研究，提出了一种导向式动态符号执行方法．主要工作包括：应用基于生成的Fuzzing技术生成种子输入，导向单路径符号执行快速到达脆弱函数；结合静态控制流分析和静态污点分析计算出脆弱函数到脆弱程序点的静态可达路径集合，导引多路径动态符号执行引擎仅仅关注于这些路径的符号分析．实验验证了方法作为路径爆炸问题减轻手段的有效性．下一步的工作包括：多线程计算环境下程序缺陷的分析建模；将该方法与静态程序分析工具相结合，进而降低静态分析中广泛存在的误报率较高问题等．

作者：黄晖 陆余良 刘林涛 赵军 单位：合肥电子工程学院网络系