论文笔记：Geneva、Themis、SymTCP、TCP-Fuzz
【CCS 19】Geneva
论文名称：Geneva：Evolving Censorship Evasion Strategie
研究问题
通常都是研究人员人工分析出规避审查策略，然后网络审查人员再完善审查系统，而人工分析规避审查策略需要研究人员熟悉审查系统中的协议实现，十分费时费力。因此本文提出了一种遗传算法 Geneva，能针对国家级的审查系统，自动生成基于修改数据包的审查规避策略。
研究算法
Geneva 生成的规避策略都基于四种操作原语：drop、tamper headers、duplicate、fragment。通过对这四种操作原语进行组合、变异和演化，生成复杂的规避策略。
具体而言，Geneva 是基于遗传算法而设计的，而遗传算法由三个关键部分组成：构建块 (building block)、适应函数 (fitness function)、变异生成函数 (mutation and crossover)。论文提出使用 (trigger, action tree) 表示规避策略，如果发现数据包中存在匹配的 trigger，则执行 action tree 中的一系列数据包修改操作，然后计算生成的数据包的适应度，将适应度高的数据包对应的规避策略留下，作为下一轮迭代演化的种子策略。
构建块是表示规避策略 (Strategy) 的基本单元，论文给出了 trigger 的编码语法以及 action tree 的表示方式（利用四种 Actions 原语构建二叉树 Action Trees），由两组 (trigger, action tree) 构成一个策略（两组分别表示为 Inbound 和 Outbound）。
针对适应函数，论文选择将生成数据包直接输入至目标审查系统，根据网络连接是否被审查，返回策略的适应度。再通过一些选择算法保留一部分策略进入下一次迭代演化。
针对变异生成函数，变异从四个方面进行：trigger 变异、Action 变异、Action Tree 结构变异、Strategy Inbound和Outbound变异。生成则是交换两个不同 Strategy 的Inbound和Outbound。
具体实现中还有一些细节优化，可参见论文。
研究结果
- 有效
针对中国、印度、哈萨克斯坦的审查系统都能发现不少新的规避策略，也能推导出几乎所有先前工作公布的规避策略。 - 快速
推导出所有的规避策略仅需要几小时的时间。
创新点
- 与已有工作相比，Geneva 能够在客户端独立运行，并自己生成规避策略，而无需审查系统等外部信息。
- 平衡了遗传算法中搜索深度和算法效率的冲突关系：
受模块化设计的启发，论文首先提出四种基本的数据包操作原语，然后将 Geneva 的搜索空间限制在四种原语的变异，组合及演化的范围内。 - 实验测试了三个真实国家的审查系统（中国 GFW、印度 ISP审查、哈萨克斯坦 HTTPS拦截），并且发现了多个新的规避策略。
【CCS 21】Themis
论文名称：Themis：Ambiguity-Aware Network Intrusion Detection based on Symbolic Model Comparison
研究问题
由于网络终端主机与NIDS在网络协议实现上存在一些差异，攻击者可以利用这些差异精心设计网络数据包，以此绕过NIDS的检测。
为了防范这种攻击，本文提出一个轻量级系统，THEMIS，使NIDS具有识别差异的能力，并且当遇到具有“歧义”的数据包时能有效地 fork 连接状态，通过分析所有连接状态，确保其中存在一个连接状态与终端主机的状态相同。
研究算法
Themis模型包括两个阶段：离线阶段和在线阶段。离线阶段的主要任务是对比分析各种TCP协议实现的差异。在线阶段的主要任务是构建能识别这些差异的 NIDS。
- 离线阶段包含三个步骤：模型提取、模型比较、差异分析。
- 模型提取，指利用符号执行技术详细分析各种TCP协议的实现，提取出能详细反映TCP数据包处理等行为信息的模型。这一步骤需要解决两个挑战：
- TCP实现中的不确定性会使符号执行每次的路径不同，从而导致误报差异。为此，Themis 提出从两个方面消除 TCP 实现中的不确定性，即针对符号执行期间产生的随机数，以及针对每次符号执行消耗的不同时间。
- 如何缓解符号执行中的路径爆炸问题，实现Scalability。为此，Themis 提出状态合并的方法。由于过于激进的状态合并会导致极难进行符号求解，因此 Themis 还提出了一种启发式方法来确定状态合并的候选区间。
- 模型比较，即比较两个符号模型，并自动生成能触发两者差异的输入样本。实现的思路是给定相同的临界状态，然后比较两个模型到达该临界状态的输入之间的差异。
- 模型分析，即根据输入样本的执行路径，人工分析导致差异的根本原因（Root Cause）。这一步骤涉及将二进制级的程序执行路径转换为源代码级的执行路径，利用执行路径确定临界状态分叉点，再将临界状态分叉点表示为符号公式，返回至 模型比较 阶段，以排除已经发现的差异。
- 模型提取，指利用符号执行技术详细分析各种TCP协议的实现，提取出能详细反映TCP数据包处理等行为信息的模型。这一步骤需要解决两个挑战：
- 在线阶段 的主要目标是构建基于 NFA 的NIDS，主要思路就是将多个确定的 DFA 合并为一个 NFA，但普通的合并算法存在空间复杂度较高的问题，因此 Themis 提出了改进的合并算法，即利用相邻版本的 TCP 协议实现具有行为上的连贯性，将算法复杂度从指数增长降低至线性增长。
研究结果
- 能检测所有已知的绕过攻击，并且开销极低
- 发现了新的协议实现差异，能被利用于绕过NIDS
创新点
- 解决了符号执行中的路径爆炸问题，首次成功使用符号执行为现实世界中的 TCP 协议实现建模。
- 使用约束求解器自动分析不同模型之间的差异，而不需要人工参与分析。
- 设计并实现了基于 NFA 的 NIDS 模型，该模型能有效帮助 NIDS 识别并应对绕过攻击，同时额外开销可以忽略不计。
【ASE 17】Learn&Fuzz
论文名称：Learn&Fuzz: Machine Learning for Input Fuzzing
研究问题
基于语法的模糊测试（Grammar-based Fuzzing）是当今对复杂的结构化输入程序的最有效的模糊测试方法。与其他全自动的模糊测试技术相比，基于语法的 Fuzzing 需要人工制定待测程序能够接收的输入格式规范。但是人为编写规范带来了巨大的人工操作负担，十分耗时并且容易出错。
因此本文研究了如何将机器学习结合至模糊测试中，来自动化生成测试用例。具体来说，本文研究了利用神经网络学习非二进制的 PDF object 的语法，用于指导fuzzing 中生成测试用例，并讨论了 learning 和 fuzzing 之间的冲突关系。
工作内容
- 针对 PDF 和 Microsoft Edge 内嵌的 PDF 解析器，进行了详细的案例研究。目的是分析复杂输入语法中哪些语法才是 Machine Learning 应该学习且适合学习的部分（PDF objects 相对独立且高度结构化，而 cross-reference table 和 trailer 则涉及地址、计数器、指针等约束）。
- 通过一系列实验，讨论了 learning & fuzzing 挑战：如何学习并生成各种格式良好的测试用例以最大化代码覆盖率，同时能引入足够格式错误的测试用例以测试异常处理代码和意料之外的程序执行路径。
具体而言，论文首先利用 PDF objects 训练不同 epochs 下的 Char-RNN 模型，然后使用两种不同的采样策略（Sample、SampleSpace 策略）进行对比，说明了代码覆盖率（Coverage）和输入通过率（Pass Rate）之间存在冲突关系，再利用 Random 算法与 SampleFuzz 算法进行对比，说明论文提出的 SampleFuzz 算法能实现较好的平衡关系。 - 提出了一种新颖的 SampleFuzz 算法解决上述挑战，即利用学习到的输入概率分布来指导 fuzzing 生成输入。其关键思想是：通过变异 RNN 模型认为具有高置信度的字符来引入异常，以此达到更高的代码覆盖率。
研究结果
- 实验说明了 Machine Learning 和 Fuzzing 在目标导向上的冲突关系，为今后结合 Machine Learning 和 Fuzzing 提供了参考。
- SampleFuzz 算法在代码覆盖率（Coverage）和输入通过率（Pass Rate）上都有不错表现，是实验对比策略中将两者关系平衡最好的算法。
创新点
- 首次尝试使用深度学习解决 Fuzzing 中测试用例生成问题。
- 详细分析和讨论了结合 Machine Learning 和 Fuzzing 所面临的挑战。
- 提出了 SampleFuzz 算法能有效解决上述挑战。
【USENIX 20】FuzzGuard
论文名称：FuzzGuard: Filtering out Unreachable Inputs in Directed Grey-box Fuzzing through Deep Learning
研究问题
DGF（directed grey-box fuzzing）用于测试可能存在漏洞的代码是否真的存在漏洞。如果大部分测试样本不能执行到目标代码，测试的效率将会十分低下。
本文研究了如何在不执行目标程序的情况下，利用 CNN 预测输入样本能否执行至目标代码，帮助DGF过滤无用的样本输入，以此提高 fuzzing 的效率。
研究方法
FuzzGuard 算法包含三个步骤：模型初始化（model initialization, MI）、模型预测（model prediction, MP）、模型更新（model updating, MU）。
MI 阶段，首先使用 DFG fuzzer 生成大量输入，并用待测程序（PUT）执行，FuzzGuard 会观察并记录输入的程序执行路径。然后，使用 step-forwarding 方法将目标代码执行路径拆分成一步一步的前置执行路径，并使用前置执行路径作为中间阶段的目标代码，以缓解数据集不均衡的问题。当收集到足够平衡的前置执行路径的数据集后训练 CNN 模型。
MP 阶段，FuzzGuard 使用 CNN 模型预测 Fuzzer 新生成的输入能否执行至中间阶段的目标代码，如果 CNN 输出 True，则让 PUT 执行输入，同时 FuzzGuard 记录输入的程序执行路径以用于后续的模型更新。这个过程中，FuzzGuard 使用了representative data selection 方法根据 fuzzer 的 seed 和 mutate strategy 筛选不同的输入来进行预测，从而减少不必要的模型预测和程序执行时间。
MU阶段，当 FuzzGuard 在 MP 阶段收集到了进一步的前置执行路径的平衡数据集，则使用 incremental learning 更新模型。之后迭代 MI、MP、MU，直到执行路径到达最终的目标代码。
研究结果
在45个真实漏洞的检测上，FuzzGuard 能平均加快 AFLGo 的检测速度 17.1 倍。并且在实验中还偶然发现了新的漏洞，并已获得了 CVE 号。
创新点
- 本文设计并实现一种基于深度学习的能识别并过滤 fuzzing 中无效输入的方法 FuzzGuard，其中核心技术在于 step-forwarding 技术和 representative data selection 技术，能解决深度学习模型训练及预测过程中遇到的挑战。
- 本文设计了一种验证 FuzzGuard 模型所学习的特征的方法，并发现模型特征与目标程序的代码分支之间存在联系。模型和程序之间的联系能帮助解释深度学习模型，并帮助进一步改进 FuzzGuard。