软件安全性分析面临大量非开源二进制程序，而面向二进制的程序分析不依赖程序的源代码，能够发现编译阶段引入的程序漏洞，具有重要的实用价值. 控制流图是二进制程序分析的基础数据，许多程序分析技术，如数据流分析^[1-2]、污点分析^[3]、符号执行技术^[4]和二进制代码比对技术^[5]等都需要在控制流图的基础上进行. 通过对程序控制流图进行检查和分析，能够达到程序验证^[6-8]、自动化生成测试用例^[9]和发现软件漏洞^[10-11]等目的. 因此，面向二进制程序，构建完备、精确的控制流图具有重要意义.

构建二进制程序控制流图的方法可以分为静态分析、动态分析和混合分析方法. 静态分析方法^[12-15]不需要动态执行程序，通过反汇编获得程序的汇编代码，对汇编指令进行解析构建程序控制流图. 静态分析的典型工具包括IDA Pro^[12]，BINCOA^[13]，Jakstab^[14-15]，能分析整个二进制程序的汇编指令，具有较高的代码覆盖率，但静态分析无法获得间接跳转地址，所以利用该方法构建的控制流图不完备. 动态分析方法^[16]利用测试用例集具体执行程序，通过记录程序执行的控制流信息，构建程序控制流图. 该方法精确度高，并且可以获得间接调用信息，但是路径覆盖率较低. 为了提高动态分析的路径覆盖率，FEX^[16]基于强制执行技术构建控制流图，通过动态跟踪程序执行，记录程序每个分支及对应状态，采用状态保存及恢复方法强制覆盖分支路径. FEX有效提高了动态分析的路径覆盖，但是状态保存及恢复消耗大量资源，导致该方法效率较低，不适用于大型程序分析. 混合分析方法^[17-18]综合利用静态和动态分析的结果构建控制流图. 文献[17]、[18]采用混合分析方法分别基于汇编代码和中间代码构建二进制程序的控制流图. 混合方法均采用静态符号执行技术生成动态分析所需的测试用例，提高了路径覆盖率，但在面对大规模程序时该方法存在路径爆炸的问题，并且依赖求解器^[19]能力，约束求解复杂，开销大、效率低，所以该方法不适用于构建大规模程序的控制流图.

综合考虑静态和动态分析的特点，提出基于混合分析的二进制程序控制流图构建方法. 讨论构建二进制程序控制流图所面临的处理间接跳转的难题；介绍基于混合分析构建二进制程序控制流图的过程. 为了避免静态符号执行和强制执行等高开销技术，选择使用模糊测试技术生成测试用例，通过动态二进制插桩技术获得间接跳转地址，融合静态和动态分析结果生成控制流图，设计并实现了控制流图构建工具CFGConstructor. 通过实验验证所提出方法的有效性和效率.

C/C++高级语言中的虚函数调用、函数指针调用等特性，经编译后，在二进制程序层就表现为间接函数跳转^[20]. 间接跳转地址是在运行时决定的，很难通过静态分析获得这些函数的跳转关系^[21]，从而无法获得完备的控制流图，导致基于该控制流图的安全分析不能发现某些潜在漏洞.

虚函数是C++实现多态的方法，虚函数调用会在程序中引起间接跳转. 如图1所示为手工构造的虚函数引起间接跳转的示例程序virtual_function的源代码和汇编代码.

在示例程序中定义了基类Base及其派生类Derive，在基类和派生类中都定义了虚函数foo，并且派生类中的foo中存在安全缺陷BUG. 基类指针p指向派生类对象derive，在通过指针p调用函数foo时，将动态地从derive的虚函数表中定位被调函数foo，并调用派生类的foo函数. 可以看出指针p调用foo经过编译表现为间接调用call rax，通过静态分析构建控制流图很难获得间接调用rax中的函数地址，无法发现该间接跳转关系. 如果对该程序进行静态的污点分析，设func中a为污点源，BUG（a）为sink点，通过基于静态分析构建的控制流图无法获得从func到Derive::foo的调用关系，则污点信息不能传播到函数Derive::foo中，导致不能发现Derive::foo中存在的bug.

函数指针调用是C/C++常用的函数调用方法，使用函数指针调用也会引起间接跳转. 如图2所示为函数指针调用的示例程序function_pointer的源代码和汇编代码. 根据输入变量a、b大小的不同，函数指针foo可能指向add或者sub，调用foo经编译后表现为间接跳转call eax，跳转地址在动态执行时决定. 通过静态分析很难获得该间接跳转关系，不能构建完备的控制流图，可能导致基于该控制流图的安全分析无法发现被调函数中存在的漏洞.

为了构建更加完备的控制流图，提出基于混合分析的二进制程序控制流图构建方法，并实现了控制流图构建工具CFGConstructor，工具架构如图3所示. CFGConstructor主要包括2个组件：静态分析组件和动态分析组件. 静态分析组件的主要功能是对二进制程序进行反汇编生成汇编代码，并通过静态分析方法生成基本的控制流图. 动态分析组件的主要功能是利用测试用例集引导二进制程序具体执行，通过插桩间接跳转指令确定跳转地址，完善静态分析构建的控制流图.

CFGConstructor构建控制流图的主要步骤如下：1）二进制程序经过静态分析组件反汇编生成汇编代码，并通过基本块划分、连接基本块生成基本控制流图；2）采用基于遗传算法的模糊测试技术生成测试用例集，引导二进制程序具体执行，利用动态插桩方法监控间接跳转指令，确定跳转地址；3）融合静态分析和动态分析结果，将间接跳转的目标基本块添加到控制流图中，生成最终的控制流图.

静态分析构建控制流图包括3个步骤：反汇编二进制代码生成汇编代码；根据汇编代码划分基本块；根据跳转关系连接基本块.

1）二进制代码静态反汇编. 对二进制代码的静态反汇编算法包括线性遍历算法和递归遍历算法. 线性遍历算法是指从程序入口开始顺序遍历程序二进制代码，反汇编每条指令，当遇到非法指令则停止. 该方法不能区分代码和数据，反汇编结果不准确，且会造成后续反汇编错误. 本研究选择递归遍历算法进行反汇编，该方法使用控制流指令引导反汇编过程，从程序入口开始进行反汇编，当遇到非跳转类指令时，则顺序进行反汇编；当遇到改变控制流的跳转类指令时，则跳转到目标地址继续进行反汇编. 该方法以控制流为指导，可以识别并跳过代码中嵌套的数据部分，反汇编结果较准确.

2）划分基本块. 基本块^[22]是组成控制流图的原子节点，每个基本块包含一组顺序执行的语句序列，有且仅有1个入口指令和出口指令. 控制流只能从入口指令进入基本块，从出口指令离开基本块，不会在中间结束或者跳转.

划分基本块首先需要确定每个基本块的入口指令. 确定基本块入口指令的规则如下：a. 每个函数入口的第1条指令；b. 所有非间接跳转指令的目标指令；c. 在汇编代码顺序中，紧跟在跳转指令后的指令.

通过静态分析无法获得间接跳转指令的目标指令，所以不使用间接跳转指令划分基本块. 为了构建函数间的控制流图，认为call指令属于无条件的跳转指令. 利用入口指令将汇编代码划分成为基本块，每个入口指令对应的基本块包括从它开始，到下一个入口指令或程序结束指令之间的所有指令.

3）连接基本块. 控制流图中的边表示基本块之间可能存在的跳转关系，当基本块block_i和block_j之间满足以下任一关系，则添加1条从block_i到block_j的边：a. 有从block_i结尾跳转到到block_j开头的跳转指令；b. 在原汇编代码顺序中，block_j紧跟在block_i之后，且block_i不存在无条件跳转语句.

针对静态分析不能处理间接跳转的问题，采用动态分析确定间接跳转地址. 使用模糊测试技术生成测试用例集，然后具体执行目标程序，采用动态二进制插桩获得间接跳转关系.

1）生成测试用例集. 文献[17]、[18]采用静态符号执行生成测试用例进行动态分析，该方法依赖于求解器的求解能力，对于大型程序存在约束复杂，求解耗时长甚至不能求解的问题. 为了能够适用于大型程序，避免使用静态符号执行等高开销的分析方法，采用模糊测试技术生成测试用例集.

CFGConstructor选择当前最流行的模糊测试工具AFL^[23]生成测试用例. AFL是低开销的模糊测试工具，以路径覆盖率为导向，采用遗传算法生成测试用例. AFL通过轻量级插桩监控程序执行状态，检查输入是否能发现新的路径，并反馈评估输入的优劣，保留任何可以发现新路径的输入，并且将其进一步变异生成下一代输入. CFGConstructor使用人工生成的方法构造模糊测试的种子输入，采用AFL中以路径覆盖为导向的变异策略生成测试用例. 为了避免在后续插桩分析时重复执行具有相同路径的测试用例，CFGConstructor仅收集能够发现新路径的输入，并将其加入到测试用例集中.

2）获得间接跳转地址. 利用上述生成的测试用例集引导目标程序具体执行，并监控程序执行状态，确定间接跳转地址. CFGConstructor采用插桩工具Pin对程序执行过程进行监控，对每个间接跳转指令进行插桩，在动态执行间接跳转时，记录跳转的目的地址，从而获取间接跳转关系. 由于间接跳转指令的数量在整个程序中所占比例较低，CFGConstructor仅需要进行少量插桩，不会引起大量的额外开销，保证CFGConstructor可以对大型程序进行分析.

CFGConstructor融合静态分析和动态分析结果，将动态识别的间接跳转关系添加到静态获得的控制流图中，获得更加完备的控制流图. 静态分析和动态分析结果的融合过程如算法1所示. 算法遍历控制流图中所有基本块中的每条指令，对存在间接跳转指令的基本块进行处理，将间接跳转关系添加到控制流图中.

算法1：融合静态分析、动态分析结果

输入：静态分析获得的控制流图staticCFG、动态分析获得的间接跳转地址

输出：包含间接跳转的控制流图CFG

1 copy staticCFG to CFG.

2 for bb in CFG.basicblocks：

3 　for ins in bb.instructions：

4 　　if ins is INDIRECT_BRANCH：

5 　　　 tbs = getTargetBlock（ins）. //可能存在多个目标基本块

6 　　　if ins is not the end of bb：

7　　　　（b1, b2） = split（bb，ins）.

8 　　　　add block b1, b2 to CFG.

9 　　　　connect all bb.predecessors to b1.

10 　　　　for tb in tbs：

11 　　　　　connect b1 to tb.

12 　　　　　connect tb to b2.

13 　　　　connect b2 to all bb.successors.

14 　　　　delete bb.

15 　　　else

16 　　　　disconnect bb to all bb.successors.

17 　　　　for tb in tbs：

18 　　　　　connect bb to tb.

19 　　　　　connect tb to all bb.successors.

20 return CFG

如图4所示，根据间接跳转指令在基本块中位置的不同，添加间接跳转关系存在2种情况. 情况1如图4（a）所示，如果间接跳转指令不是基本块的最后一条指令，根据该间接跳转指令将原基本块block分割成为2个新的基本块block1、block2；分别将原基本块的入边和出边重定向到blcok1、block2；根据动态分析获得的间接跳转关系确定该间接跳转指令的目标基本块，并添加block1到目标基本块、添加目标基本块到block2的边. 情况2如图4（b）所示，如果间接跳转指令是基本块的最后一条指令，则不需要分割基本块，添加block到目标基本块的边，并将block所有出边的起点重定向到目标基本块.

如算法1第5行所示，间接跳转指令可能存在多个目标基本块. 如算法第10、18行所示，当存在多个目标基本块时，分别添加每个基本块为间接跳转指令的后继基本块，表示该跳转指令存在多个候选执行分支.

设计实验评估CFGConstructor的有效性和性能. 实验平台为Ubuntu 14.04LTS 32位操作系统，处理器为Intel Core i7-4702HQ @2.2 GHz，内存为DDR3 4 GB. 为了验证工具的有效性，与静态分析工具IDA Pro进行对比. 首先对2个手工构造的示例程序进行分析；然后对美国国防部高级研究计划局（DARPA）举办的网络安全挑战赛（CGC）^[24]中部分测试集进行测试.

作为反汇编工具，IDA没有直接提供函数间的控制流图，为了与IDA进行比较，使用IDAPython在IDA Pro 6.8中实现插件IDA CFG. 该插件基于IDA反汇编结果构建函数间的控制流图，图中的边依赖于IDA识别的跳转关系. 分别使用IDA CFG和CFGConstructor对2.1节中构造的2个程序进行分析，构造程序控制流图如图5所示. 为了便于说明，图中仅显示包含间接调用的关键部分，其中矩形表示基本块，实线表示基本块间的直接跳转关系，是IDA CFG和CFGConstructor构造控制流图的公共部分；虚线表示间接跳转关系，仅包含在CFGConstructor构造的控制流图中.

如图5（a）所示为实例程序virtual_function的控制流图，函数func的基本块0x4006D4中包含间接跳转指令call rax. 静态分析工具IDA无法发现rax的具体值，不能判断该指令跳转的目标地址. CFGConstructor通过动态二进制插桩该指令，获得具体执行时的eax=0x400730，说明程序将跳转执行Derive::foo函数，从而发现基本块0x4006D4到0x400730的跳转关系，以及当函数返回时从基本块0x400730到0x4006F4的跳转关系.

如图5（b）所示为实例程序function_pointer的控制流图，函数func的基本块0x48480中包含间接跳转指令call eax. 与示例virtual_function不同的是，该跳转目标地址eax在实际执行中存在多个可能取值，CFGConstructor通过模糊测试生成的测试用例集覆盖多个路径分支，从而发现这些取值. 当测试用例中a>b时，eax=0x4844D，程序跳转到sub函数执行；当测试用例中b<a时，eax=0x4845C，程序跳转到add函数执行. 因此，能够发现从基本块0x48480分别到0x4844D、0x4845C的跳转关系.

实验结果表明，基于静态分析的IDA仅能处理直接跳转关系而不能识别间接跳转关系，从而不能获得某些基本块的可达路径，导致无法发现一些潜在漏洞. 基于混合分析的CFGConstructor不仅能发现直接跳转关系，而且能够识别间接跳转关系，并且可以处理多目标地址间接跳转的情况，该工具能够针对二进制程序构建更加完备的控制流图.

在二进制程序分析中，如污点分析、符号执行生成测试用例等，通常更关心“从程序入口可达”的代码. 统计IDA、CFGConstructor构建控制流图中可达代码情况，结果如表1所示. 其中，F_i、V_i、E_i分别为在IDA构建的控制流图中，从程序入口可达的函数集合、基本块集合和连接集合；F_c、V_c、E_c分别为在CFGConstructor构建的控制流图中，从程序入口可达的函数集合、基本块集合和连接集合；I为CFGConstructor识别间接跳转的数量.可以看出，相较于IDA，CFGConstructor通过识别间接调用关系，能够发现一些静态分析不能到达的函数，进而发现更多的可达基本块. 值得注意的是，在构造2个示例程序时，分别人工引入了1个和2个间接跳转，而CFGConstructor则分别发现了2个和3个间接跳转，额外发现了更多的跳转关系. 这是因为在对源代码进行编译时，为了生成完整的可执行文件，编译器会自动添加一些额外代码，在这个过程中也会引入间接跳转，CFGConstructor能够发现这部分间接跳转关系. 综上所述，CFGConstructor能够有效识别间接跳转，发现更多可达基本块，构建更加完备的控制流图.

为了进一步评估CFGConstructor构建程序控制流图的性能，实验从CGC标准测试集中选择了6个不同大小的二进制程序进行实验. 分别使用IDA、CFGConstructor对所有程序构建控制流图，分析结果如表2所示. 其中，S为二进制程序大小， ${F_{\rm{c}}} - {F_{\rm{i}}}$ 为CFGConstructor能够发现但IDA不能发现的可达函数集合，类似地， ${V_{\rm{c}}} - {V_{\rm{i}}}$、 ${E_{\rm{c}}} - {E_{\rm{i}}}$ 分别为CFGConstructor能够发现但IDA不能发现的可达基本块和连接的集合. 可以看出，在二进制程序中普遍存在间接跳转关系，而基于静态分析的IDA无法发现通过间接跳转到达的基本块. CFGConstructor可以识别间接跳转关系，发现间接跳转的目标基本块，并将间接跳转目标基本块及其后继基本块均标记为可达基本块，从而发现更多的程序入口可达代码. 在测试集中，CFGConstructor平均能够比IDA多发现12.62%的可达函数、24.72%的可达基本块和33.38%的连接. 结果表明，相较于静态分析方法，基于混合分析的CFGConstructor能够构建更加完备的控制流图.

对CFGConstructor的分析效率进行评估，利用CFGConstructor对不同大小的程序进行分析，记录分析所消耗时间. 相较于动态分析，静态分析时间较短，所以实验不考虑静态分析的时间开销. 实验使用AFL对所有测试程序分别进行2 h的分析，生成测试用例集合，利用AFL生成的测试用例集对每个测试程序进行动态分析，重复3次并记录分析时间，结果如表3所示. 其中，t为动态分析所需时间；T为生成测试用例的数量，由于程序路径复杂性不同，生成的测试用例数目存在差异. 可以看出，为了能够覆盖更多的路径，针对越复杂的目标程序，AFL生成的测试用例越多. CFGConstructor仅保留AFL中能够发现新路径的测试用例，避免盲目执行大量测试用例.

由表3可以看出，CFGConstructor能够在较短时间内完成对目标程序的分析，例如，大小为727 KB的目标程序pwn300中包含453个可达函数、19 193个可达基本块和28 473条连接，利用CFGConstructor构建该程序控制流图需执行321个测试用例，时间开销仅为82.42 s. 如果采用文献[16]提出的强制执行方法对该程序进行分析，每个路径分支点都需要保存、恢复虚拟机快照，将消耗大量时间；如采用文献[17]、[18]中基于静态符号执行方法生成的测试用例集，将面临路径爆炸、约束困难、开销大等问题，不能满足实际分析需求. 综上所述，相比于其他方法，基于混合分析的CFGConstructor消耗较少时间就能构建程序的控制流图，具有较高的实用价值.

提出动静结合的二进制程序控制流构建方法，使用动态分析识别程序间接跳转关系，结合静态分析结果生成较完备的控制流图，并实现工具CFGConstructor. 实验表明，相比于静态分析，该方法构造的控制流图更加完备，在测试集上平均能多发现24.72%的可达基本块和33.38%的跳转关系. 该方法避免使用强制执行、静态符号执行等高开销分析方法，提高了针对大规模程序的分析能力. 研究成果为进一步开展二进制程序分析，发现潜在漏洞提供了基础支撑.

所提出的方法仍存在局限性，其发现间接跳转的能力依赖于AFL生成测试用例集的质量，如果某些间接跳转指令没有被测试用例覆盖，则该方法无法获得该间接跳转关系. 在未来工作中，将以覆盖间接跳转为导向改进AFL，生成更加适用于CFGConstructor的测试用例集，构建更加完备的二进制程序控制流图.