2016 IEEE Symposium on Security and Privacy (SP)
这篇文章作者将目前的二进制分析技术做了全面的介绍，同时针对这些二进制分析技术实现并开源了二进制分析框架 angr，供之后的安全研究者们使用。
作者首先发现，尽管现在有大量的二进制分析技术，但是这些二进制分析技术没有一个统一可用的实现，大部分技术仅仅只在原型系统层面实现，这使得后面的研究人员如果想要验证该技术的有效性，只能从头开始实现，很浪费时间。此外，由于这些技术没有相对统一的实现，无法较好地比较这些技术的效果。基于这一点，作者实现并开源了二进制分析工具 angr。
作者首先讲述了二进制分析的一些棘手的难题。由于二进制程序分析技术是一个非常深奥的领域，通常为了所提出的技术具有高的实用性，而在各种理论上需要做出权衡。比如，对于静态分析所发现的漏洞，可能需要考虑其可复现性的问题：一些二进制程序分析技术考虑了整个程序，对整个程序进行分析，因此该技术所发现的漏洞不存在不可复现的问题；而一些二进制分析技术仅仅考虑部分模块，因此这种分析发现的漏洞可能由于函数等信息的变化，导致不可复现。此外，动态分析可以直观地触发目标程序的漏洞，但是可能无法较好地提供一个目标程序的语义理解信息；而静态分析可以较好地确定输入对目标程序的影响。静态分析通常可以获得比较高的代码覆盖率，对代码的各部分都能分析到，但是可能准确率不高；而动态分析由于实际执行了程序，可以具有较高准确性，但是可能不能覆盖到较深的程序路径。
接下来作者分别简要介绍了静态分析技术与动态分析技术的概念、特点和用处。静态分析技术就是在不运行目标程序的情况下对目标程序进行分析，但是静态分析可能存在分析得到的漏洞无法复现，需要手动分析以及无法得到目标程序太准确的语义信息导致漏报率高等问题。
作者将静态分析分成两个类别：基于图（CFG）的分析以及基于数据的分析（DFG）。作者简要介绍了一下 CFG 的恢复技术，CFG 是几乎所有静态分析技术的前提，通常使用递归算法进行分析和恢复。CFG 恢复的一个难题是间接跳转（通过计算得到跳转地址、函数指针传递进来的回调、面向对象语言的虚表等），通常由于间接跳转的地址无法计算而导致 CFG 恢复的不完整。因此 CFG 恢复的目标是尽可能多地解析出这种间接调用。
在得到 CFG 之后，可以使用基于流模型的方式或者基于数据模型的方式对漏洞进行检测。前一种方法倾向于构建一个模型来检测漏洞，更类似于对代码进行检索，然后根据已知漏洞的规则进行匹配；后一种方法倾向于对内存以及寄存器中的数据进行抽象，使用诸如 VSA 这样的方法来对内存的值进行检测，可以用来发现诸如内存溢出等错误。但是这种方式可能会造成由于 Over-Approximate 而导致的准确率下降。
动态分析通过实际执行目标程序来对程序进行分析，可以通过在真实环境中执行或者在仿真环境中执行来对其分析。动态分析可以分成真实执行和符号执行两个部分。动态真实执行需要提供一些测试用例，最常见的就是 Fuzzing。作者将 Fuzzing 分成基于代码覆盖率的 Fuzzing 以及基于输入污点的 Fuzzing。代码覆盖率的 Fuzzing 的目的是加大对目标程序的执行路径的覆盖率，其基本思想是更大的覆盖率可以得到更高的漏洞挖掘的概率，但是这种 Fuzzing 无法很好地对目标程序的执行与输入的关系进行理解。基于输入污点的 Fuzzing 通过污点分析找到输入会对分支影响的部分，从而对测试用例更有针对性地进行突变。
另一个动态分析的方法是动态符号执行，基本思想是将目标程序在仿真环境中执行，模拟寄存器和内存的状态，并使用符号值对一些内存或者寄存器中的值进行模拟，当执行到某个分支上时，将分支条件作为约束进行存储。这种方式可以对目标程序达到较高的程序语义理解。传统的动态符号执行技术可以直接用于漏洞挖掘，通过定义漏洞状态，然后对到达该状态的输入进行约束求解，从而实现漏洞挖掘。但是这种方法存在路径爆炸的问题，也有一些工作针对路径爆炸对动态符号执行进行优化，然而路径爆炸仍然是一个比较严重的问题。符号辅助 Fuzzing将符号执行与 Fuzzing 结合，通过对程序更好地理解，指导 Fuzzing 朝着更有效的方向突变。还有一种约束不足的符号执行，不对整个程序执行路径的约束进行追踪，而仅仅执行程序的某一部分，这种方式虽然可以缓解路径爆炸的问题，但是会导致很高的误报率。
在使用程序分析技术发现相应的 Crash 之后，通常需要对 Crash 的可复现行进行评估。在程序分析阶段，为了更好地分析目标程序，可能会对一些随机值进行具体化，从而减少程序执行过程中的随机性。但是在这种情况下发现的 Crash 可能存在无法被复现的问题，主要是由于数据的去随机化或者无法得到程序中处理的数据与输入之间的关系这两个原因。有部分程序分析技术用于解决这方面的问题。在确定 Crash 可重用之后，需要确定目标程序的可利用性，目前有一些工作基于导致 Crash 的输入以及程序的状态对漏洞自动生成利用。在可以完成自动控制流劫持的基础上，由于现代操作系统的缓解机制，还需要利用可以对这些缓解机制进行绕过，因此程序分析技术还可以用于漏洞利用强化，例如自动构建 ROP 链等。
作者提到 angr 可以支持多个架构、跨平台、支持多种二进制分析技术、以及结合 Python 的易用性。
angr 分为多个子模块来实现：
- IR（中间表示形式）：
angr将架构相关的指令码翻译成中间表示形式，并基于中间表示形式完成二进制分析； - 二进制加载：
angr使用 CLE 对目标二进制程序进行加载（加载到仿真系统），同时解析相应的符号地址等信息，以用作后续的分析； - 程序状态表示和修改：
angr使用 SimuVEX 模块对程序的状态进行抽象，包括内存状态和寄存器状态。SimuVEX 提供了很多插件（plugins）来对当前程序的状态进行抽象。 - 数据模型：
angr使用 Claripy 模块将所有的值抽象成表达式，然后跟踪所有对该表达式的操作，表达式的值可以转化成数据域用于 VSA，也可以转化成符号域用于符号执行求解。 - 全程序分析：
angr使用 Project 对目标程序进行加载，同时在 Analyses 模块实现了多个对程序进行完整分析的方式，例如 CFG 恢复等。
angr 使用强制执行、反向切片、符号执行等技术完成 CFG 恢复，从程序的入口基本块开始，不断迭代解析得到下一个基本块，直到完成全部的分析。但是这种方式实现的效率很低，因此 angr 同时实现了第二种恢复基本块的方式，使用启发式的方法，定位到函数以及提取函数内部的 CFG，然后定位到基本块之间的跳转。这种方式虽然速度快，但是准确率很低。基于上述两个算法，angr 分别实现了 CFGAccurate 和 CFGFast。
为了加快 CFGAccurate 的解析速度，angr 在实现时做了如下假设：
- 所有代码都能被划分到某一个函数中
- 所有的函数都会被显示的 call 指令调用或者被尾调用
- 每个函数的栈清理行为都是可预测的，无论是从哪儿调用的
作者还提到，其他 CFG 恢复技术中，也使用了其他的假设，但是这些假设对于二进制程序来说并不是能满足的。
angr 实现一个集合 C，由应用程序入口基本块进行初始化；一个列表 Lj，包含间接跳转指令，这些间接跳转的目标暂时还没有被解析，然后迭代强制执行、反向切片、符号执行这三个技术对间接跳转的值进行解析。
- 强制执行：可以确保在每个分支的两个方向都执行一遍
- 符号执行：遇到分支后反向遍历基本块，找到基本块的合并点，然后执行前向符号执行，再使用约束求解得到可能的目标值
- 反向切片：从未解决的分支点开始，反向切片到调用该基本块的函数的基本块的开头，然后使用符号执行计算间接跳转的值
CFGFast 则使用比较轻量的技术，以及函数开头的特征指纹都方法，对 CFG 快速解析。
VSA 是一种记录当前指令所影响的内存以及寄存器值的静态分析方法，可以通过 VSA 得到某一指令可能的机器状态范围（内存的值以及寄存器的值）。为了提高 VSA 的精度，作者不在遇到多个值的情况下立即合并取值范围，而是使用离散的值，当离散的值的个数到达一个阈值之后，再对这些值进行合并。
作者同时通过追踪分支约束，结合路径谓词，将内存的值限制在一个更小的范围内，从而更进一步提高了 VSA 的精度。
在通过 VSA 分析了目标程序之后，可以通过判断目标程序指令之间对内存的读写的范围是否有重叠，从而可以发现一些内存越界的漏洞。
作者在 angr 中实现了动态符号执行，同时使用了之前提到的那些内存模型，并使用多种缓解路径爆炸的策略。
angr 为了加快动态符号执行，使用了约束不足的符号执行，这种符号执行的思想就是在每个函数上下文单独地执行符号执行，但是这种符号执行分析得到的漏洞是不一定可复现的，误报率较高。
为了缓解误报率高的问题，angr 也做了很多工作，其将确实的上下文信息标记为受控制状态，当一些违反安全约束的行为发生的时候，会将涉及的值跟这个受控制的状态进行比较，进一步检查其是否违反了安全约束。
此外，angr 不分析那些路径数量多的函数，最后，作者在其中添加了一些误报过滤器，对误报的样例进行过滤，从而提升了准确率。
将符号执行与 Fuzzing 执行，可以结合 Fuzzing 的速度快以及符号执行精准找到路径这两个有点，从而提升程序中漏洞挖掘的效率。
通过 Fuzzing 样本中精确的值，作者可以缓解符号执行所带来的路径爆炸的问题。
angr 同时实现了对 Crash 的重现功能，该功能基于符号执行来完成。该算法将生成的输入，目标程序，初始状态以及崩溃状态作为输入，生成在真实环境中程序执行到崩溃时的约束，然后对约束进行求解，从而得到真实环境中可以导致目标程序 Crash 的输入，对目标 Crash 的可重现性进行验证。
对于利用生成，作者使用了符号执行对程序的状态进行求解，同时借助污点分析的方式可以较好地生成漏洞的利用。由于现在的自动化利用生成技术的效果并不是很理想，因此这里仅提供一个思路，可以对未来的研究提供思考。
对于利用增强，作者主要借鉴了 Q （一个 ROP 自动生成的工作）的思想，来实现了一套对应与目标二进制程序的 ROP 生成算法。