内容来源于ACM CCS 2018：Revery: From Proof-of-Concept to Exploitable(One Step towards Automatic Exploit Generation)
第一作者：中科院信工所王琰文章地址：https://www.researchgate.net/publication/328321653_Revery_From_Proof-of-Concept_to_Exploitable
随着模糊测试技术的发展，现有工具已经能通过黑盒测试的方法在程序中找到大量的BUG，例如谷歌的OSS-Fuzz平台采用了几种最先进的模糊测试器来对开源的应用程序进行持续测试，在五个月中，他们发现了超过1000个BUG。然而，评估这些BUG的威胁程度如何，是否是可利用的，却需要投入大量的人力。这就产生了自动评估漏洞严重性并确定修补优先级的需求。为了解决这个问题，现有的思路分为两种：
一种是基于模糊测试产生的崩溃输入触发程序崩溃，并在崩溃点捕获导致崩溃和安全违规的指令，进一步地，根据已有的利用模式来评估当前状态是否可利用，并最终给出一个数值评分。这种方法依赖于已有的模式，常常不够准确，也不能为程序生成真正的利用输入来证明可利用性。
另一种评估方法是生成一个有效的利用。主要流程是先用崩溃输入执行程序，动态分析崩溃路径，寻找可利用的路径，然后利用符号执行收集抵达该路径的约束条件（包括触发漏洞的约束和建立利用的约束），最终求解约束得到利用输入。目前，这样的方案还只能解决极少一部分的问题。主要因为以下的原因：①、利用可导出性问题：崩溃输入可能将程序引导成不可利用的状态，基于此状态无法导出利用；②、符号执行瓶颈：符号执行固有的问题难以解决，可能会出现路径爆炸问题，也可能会直接漏掉可利用的情况；③、堆漏洞难题：堆管理功能复杂，现有的程序分析技术难以分析，而且堆管理函数对堆的损坏有着一系列的安全检查。
本文重点研究了给定PoC输入的基于堆的漏洞的可利用性评估。作者提出了一个框架——Revery，不仅可以在崩溃路径中搜索可利用的状态，还可以在发散的路径中搜索可利用的状态，并在可能的情况下生成有效的控制流劫持攻击。
补充一个认识：原论文认为当程序经过一些违规操作后，会进入脆弱状态，但是崩溃与利用不会当即发生，而是在后续的过程中生效，为了节约篇幅，我在此处没有详述这方面的认识，但在后文中，大量使用“脆弱”这个关键词，是为了与漏洞作区分，尽量准确表达作者的意思。
图1：revery的整体框架
如图1，Revery整体分为三个模块：脆弱分析模块，发散路径探索模块，利用合成模块。
首先，像现有的自动利用生成方案一样，Revery基于崩溃路径收集一些动态信息。除了变量的污点属性外，它还检查损坏的内存对象（异常对象）和可用于定位异常对象的对象。在路径中，它还检索创建了这些对象并建立起指针与对象间指向关系的布局贡献指令。基于这些指令和对象，Revery创建布局贡献有向图来描述内存状态和贡献指令。
随后，Revery在发散的路径中寻找可利用的状态。它使用布局导向模糊测试而不是符号执行来探索发散的路径。和导向型模糊测试一样，Revery也驱使模糊测试器向着一个具体的方向演进，即，和崩溃路径一致的方向。当然，Revery的目标并不是完全与崩溃路径一致，它忽略了崩溃路径上大部分的指令，仅仅以那些对内存布局造成影响的指令为导向，因此，能与崩溃路径产生大致相似的内存布局。在内存布局相似的情况下，模糊测试探索大量的发散路径，能更有机会发现可利用的状态。
最后，Revery将能触发崩溃的PoC输入和通过模糊测试达到利用状态的输入结合起来，使用一种被称为控制流缝合的解决方案，在仅只用轻量级符号执行的情况下生成利用输入。以下，将逐个模块进行深入介绍。
要利用脆弱，需要定位脆弱点和程序状态。此外，为了解决漏洞的可导出性问题，需要搜索脆弱状态周围的可利用状态。因此Revery通过脆弱识别来定位脆弱，通过布局分析来表征脆弱状态。
3.1 脆弱识别
给定PoC输入，首先需要识别其对应的脆弱点，Revery采取了一种被称作内存标签（也被称作内存着色，内存污染）来定位脆弱。Revery使用一个影子内存来无干扰地跟踪指针和堆对象的标签。它还跟踪堆对象的状态，有效检测时间（use-after-free）和空间（堆溢出）上的脆弱。原则上，指针只应该访问具有正确状态标签的堆对象，否则，将被定义成违反安全规则。图2给出了一个违反安全规则的例子。
图2：每个堆对象和指针都有一个内存标签。每个内存对象都有一个状态位。
3.1.1 内存标签
每个堆对象和指针都有一个内存标签，表示其沿袭关系。创建对象时，将生成唯一的标签，并传播到对象的指针和其他相关指针上。此外，每个堆对象都有一个状态，即uninitialized、busy或free，分别对应于已分配但未初始化、已初始化且正在使用或已释放。值得注意的是，一个释放的内存区域可以分配给新的对象，它的内存状态和标记将根据对象的不同而变化。
在某些特殊情况下，开发人员可以使用一个对象的指针来获取另一个对象的指针，并进行算术运算。它将错误地将第一个对象的标记传播到第二个指针。幸运的是，这种情况在堆对象中很少见，因为堆对象之间的偏移量不固定。唯一的例外是堆管理函数，它可以以这种方式检查相邻对象，不管这些对象具有什么语义。因此Revery将禁用这些特殊函数的标签传播和验证。值得注意的是，这种优化仅用于跨对象指针派生。Revery支持对象内指针派生。
3.1.2 安全规则
对于每个堆内存访问指令(即，加载和保存)，能得到指针的标签tag_ptr和目标内存区域的标签tag_obj和状态status_obj。内存访问不能违背以下安全规则：
V1：访问对应对象：指令只能访问对应的对象，即tag_obj=tag_ptr。
V2：读忙碌对象：加载指令不能访问被释放或者未被初始化的内存，即status_obj=busy。
V3：写活跃对象：保存指令不能访问被释放的内存，即status_obj≠free。
任何违背上述规则的都将导致脆弱。例如，缓冲区溢出违背了V1，未初始化变量漏洞违背了V2，use-after-free漏洞可能违背了V1,V2,V3等。
3.2 布局分析
Revery进一步分析对象布局来描述脆弱状态并检索对此状态有贡献的指令。
3.2.1 脆弱相关对象布局
每个基于堆的脆弱(包括堆溢出和UAF)都与一个异常对象相关，该异常对象的内容因为脆弱点而损坏（或将被脆弱损坏）。对这些对象的进一步操作可能会导致程序进入可利用的状态。
假设脆弱点使用带有标记tag_ptr的指针访问带有标记tag_obj的目标对象。如果是写访问，那么带有tag_obj标签的对象就是异常对象，它将被这个写访问所破坏。如果是读访问，而这个脆弱是UAF，那么带有tag_ptr标签的对象就是异常对象，它将被占用相同内存的新对象分配所破坏。Revery目前不支持其他类型的读访问冲突。
此外，Revery还跟踪所有可用于定位异常对象的索引对象。这些异常对象和索引对象由指向关系相连接。作为一个结果，Revery可以得到对象的有向图，表示为布局有向图
这种布局有向图在一定程度上表征了脆弱状态。图3(b)显示了一个布局有向图示例。
图3：一个布局贡献有向图的例子。假设35行创建的是一个异常对象，它能被第22行和第5行创建的堆对象索引，并最终由全局指针ptr指向。
3.2.2 脆弱相关代码
如上所述，这个程序必须进入某个特定的初始状态，包括脆弱状态。因此，无论是在发散路径还是利用路径上，都有必要准备一个与发生脆弱相似的对象布局。因此，对布局作出贡献的指令非常重要。
可以看到，以下两种类型的操作可以影响对象布局:(1)创建新对象的内存分配，以及(2)为一个对象字段分配一个指向另一个对象的指针的存储操作。Revery可以检索所有这样的操作，这些操作影响着布局有向图中的对象，并基于此，生成一个布局贡献有向图。
更具体地说，这个有向图中的每个节点都是一个异常对象或索引对象，具有对象创建者指令和内存标签的属性。有向图中的每条边都表示两个对象之间的指向关系，并带有指针赋值指令的属性。给定一个目标异常对象，可以使用逆向切片来构造这个有向图。图3(c)显示了一个示例布局贡献有向图。这个有向图有一个更简单的形式，称为布局贡献切片，它是按执行顺序排列的贡献指令序列。
为了解决利用可导出性问题，有必要探索发散路径并在其中搜索可利用状态。本节将介绍Revery如何探索发散路径。
4.1 布局导向模糊测试
Revery只利用模糊测试来探索发散路径和寻找可利用的状态。脆弱性发现表明，在探索路径和程序状态时，模糊测试比符号执行更有效。因此，模糊测试很可能也能帮助更快地发现发散路径和利用状态。
Revery在布局贡献有向图的指导下，采用了一种新的布局导向的模糊测试解决方案，来探索构建了与脆弱点相似内存布局的发散路径。
4.1.1 设计
Revery扩展了流行的覆盖引导模糊测试工具AFL进行模糊测试。Revery不只是依靠代码覆盖率来指导路径探索，而是使用布局贡献有向图作为指导来调整探索和突变的方向。类似于导向型模糊测试，Revery驱动模糊器探索接近崩溃路径的路径。它只针对匹配布局贡献切片中的指令，而忽略崩溃路径中的其他指令。设计的选择是基于以下三个直觉：
直觉1：按与引导片相同的顺序命中所有布局贡献指令的输入，可以构造与脆弱点类似的内存布局。
直觉2：命中引导片较长子序列的输入更有可能演变成命中全部引导片的输入。
直觉3：命中更少布局贡献指令的输入将为进一步利用引入更少麻烦。换句话来说，两个输入在引导片中命中了相同长度的子序列，那个指令更长的输入会增加生成利用的难度，而那个更加简单的的输入更可靠。
4.1.2 实施细节
图4：Revery中模糊测试的实施图解
Revery扩展了流行的模糊测试工具AFL。如图4所示，AFL应用一个连续循环来探索路径。它保持一个好的测试用例队列，即种子；接着从队列中选择种子；然后修改种子以获得一堆新的测试用例，继而在QEMU中用生成的测试用例执行程序，并跟踪覆盖率，最后根据覆盖信息评价种子。Revery从两个方面改造了AFL：跟踪引导片的命中次数，调优引导模糊测试的方向。
4.2 发散输入过滤
通过面向布局贡献有向图的模糊测试，Revery可以发现能触发与PoC输入相同的布局贡献指令序列的发散路径。然而，与布局贡献有向图不同的是，布局共享指令切片中缺少数据流约束。因此，发散输入产生的内存布局有时不匹配从崩溃路径构建的目标内存布局。因此Revery采取了额外的步骤来过滤出能够匹配目标布局贡献有向图的发散输入。
通常，它首先将发散路径与崩溃路径对齐，并定位负责创建异常对象的指令。然后，以与崩溃路径相同的方式，通过逆向切片从发散路径构造异常对象的一个新的布图贡献有向图。最后，通过比较两个有向图中每个节点的内存标记及其创建者指令的地址，将这个新的有向图与目标有向图匹配，如图5所示。
图5：将发散路径的布局与目标崩溃路径匹配，并在匹配时对它们进行对齐，进行过滤
如果这两个有向图不匹配，那么这个发散输入将被丢弃，否则将被保留。进一步的，这两个有向图的节点(即，堆对象)以及所有节点的内存标签将相应地对齐。因此，可以推断出每个对象在发散路径和崩溃路径之间的对应关系，从而对这两条路径进行进一步的分析。
4.3 利用状态搜索
尽管发散路径的布局与脆弱状态相似，也不是所有路径都可以利用。Revery进一步删除了不具有可利用状态的分叉路径。
4.3.1 可利用状态
异常对象可能影响其他对象，有时会直接或间接地用于某些敏感操作。由这些敏感操作产生的程序状态被表示为可利用状态。本文主要考虑两种类型的敏感(可利用的)操作，即，内存写和间接调用。例如，如果一个内存写的目标地址受到异常对象的影响，那么攻击者可能控制在哪里写并导致AAW(任意地址写)，即，一种在实践中常用的可利用状态。如果攻击者能够影响间接调用的目标，包括虚拟函数调用和间接jmp指令等，则可以劫持控制流。此外,Revery为漏洞分析人员提供了一个模板来扩展可利用点的防御，例如，发起断开链接攻击的操作。
4.3.2 利用状态搜索
基于4.3.1中的认识，这个问题就变成了识别操作数受异常对象影响的敏感指令。污染分析是一个简单的解决方案。Revery将每个对象创建操作标记为污染源，并为其附加一个唯一的污染标签。每个操作将所有源操作数的污染标签传播到目标。在每条敏感指令(即，内存写和函数调用)，如果目标地址的污染标签包含异常对象的污染标签，则将检查目标地址的污染标签。如果是，那么这个敏感指令是可利用的。
本节将介绍如何从PoC输入和发散输入合成新的利用。
一旦在路径中找到可利用状态，现有的AEG解决方案通常通过求解路径、漏洞和利用约束来产生利用。然而，正如第4.1节所讨论的，单独的符号执行在漏洞生成中效果并不好。因此，Revery尽可能少地使用符号执行。它使用一个轻量级符号执行作为连接，将崩溃路径和发散路径缝合在一起，并重用PoC输入和发散输入，进一步减少复杂的约束，使符号执行更实用。
图6：利用合成的工作流程
图6显示了利用合成的一般工作流程。在实际应用中，首先识别拼接点，然后探索拼接点和综合利用路径之间的子路径，最后求解相关约束条件，生成有效利用。
5.1 识别拼接点
首先介绍在崩溃路径和发散路径上，理想的拼接点是如何识别的。
5.1.1 崩溃路径上的拼接点
为了成功地利用目标程序，必须首先触发其漏洞，导致一些异常对象被损坏。因此，Revery选择异常对象在崩溃路径中损坏的位置作为拼接点。
如3.2.1节所述，在崩溃路径中，每次写访问冲突都会破坏一个异常对象，因此它是一个候选拼接点。对于UAF漏洞中的每个读访问冲突，异常对象是已释放但仍然由悬空指针指向的对象。这个异常对象的内存区域将被另一个内存分配占用。Revery将新的内存分配操作作为一个候选拼接点。
因为在一个崩溃路径中存在多处违反安全规则的情况，所以也可能有多个缝合点。Revery将尝试用发散路径来缝合它们。
5.1.2 发散路径上的拼接点
为了成功地利用目标程序，生成有效利用必须基于损坏的异常对象或附属对象。
什么是好的缝合点?每条指令都可以作为拼接点使用。但并不是所有的都是好的。一个合适的缝合点应符合以下几个标准:
不要太靠近入口点。否则，将执行许多和崩溃路径重复的操作。由于重复的操作(例如，对象初始化)不会在合法的控制流中发生，所以不可能找到一条路径来连接这个拼接点和崩溃路径中的对应点。
不要太接近可利用的点。否则，需要更长的路径来连接这个缝合点和对应的缝合点，需要更多的符号执行开销。缝合点可以在某些操作之前设置，例如，初始化可利用点的操作数，以节制符号执行的工作量。
最小数据依赖性。发散路径上的拼接点后的数据流与崩溃路径上的拼接点前的数据流相交较少。
如何找到拼接点?在高层次上，Revery匹配发散路径的数据依赖关系和崩溃路径的数据依赖关系，并定位差异。然后用产生发散路径差异的指令作为拼接点。
首先，Revery在发散路径中构建可利用操作的操作数的布局贡献有向图。然后它将这个有向图与崩溃路径中异常对象的有向图匹配。如果前者是后者的子图，则意味着崩溃路径已经为可利用的操作设置了所有数据依赖项。然后，发散路径中的指令在最后一次对可利用操作的操作数进行写访问之后，选择该操作数作为缝合点。
否则，发散路径有向图中存在不同的节点或边，即，发散路径改变了可利用操作之间的依赖关系。在这种情况下，Revery选择发散路径中最早的指令(对象创建或写入)作为拼接点，这条指令导致了有向图的差异。
5.2 控制流拼接
为了将崩溃路径和发散路径缝合在一起，Revery探索了连接这些路径中的缝合点的潜在子路径。通常，它依赖于符号执行来探索路径。然而，Revery利用几种启发式来有效地指导符号执行。首先，Revery使用函数调用堆栈来引导路径探索。它分别在两个缝合点检查调用堆栈，并找出差异。其次，Revery通过重用现有路径进一步减少了子路径探索。例如，如果在发散路径或崩溃路径中已经有一个子路径连接两个中间目标，Revery将重用该子路径。这样，Revery在探索连接拼接点的子路径时，大大减少了符号执行的负担。
5.3 利用生成
一旦找到连接两个缝合点的子路径，就可以构造一个候选的利用路径。Revery也可以求解漏洞约束、路径约束和漏洞约束生成最后的利用样本。然而，这是不够的。
5.3.1 利用状态约束
简单地求解利用路径的约束可能不会触发与发散路径相同的利用状态。因此Revery向利用路径添加了几个额外的数据约束，确保程序状态仍然是可利用的。
5.3.2 有效载荷约束
在某些情况下，Revery能够直接生成有效的利用。在可利用点，Revery可以构造有效载荷约束，从而导致控制流劫持。然而，并不总能保证成功。
现有的AEG解决方案面临着利用可导出性问题、符号执行瓶颈和基于堆的漏洞的挑战。本文提出了一种新的面向布图的模糊和控制流拼接解决方案，能够在发散路径而不是崩溃路径中搜索可利用状态。它可能触发大部分脆弱应用程序的漏洞和可利用状态，还可以成功地为某些漏洞生成利用，向实际的AEG迈进了一步，但是还有很长的路要走。
关于 天 方 夜 “谈”
天方夜谈原意讲不切实际的东西，而这里想要 “脚踏实地”真正弄懂并感受一篇文章的思想。
方班人有自己的浪漫，
我们探讨知识，谈论理想，
采摘科研的繁星，
脚下是星辰大海。
天：代表我们的理想犹如天空般浩荡
方：代表方班
夜：代表代码人的冷静与静谧
谈：代表方班愿与您，就领域内的经典思想和前沿成果“秉烛夜谈”
