Not All Coverage Measurements Are Equal:Fuzzing by Coverage Accounting for Input Prioritization

总结：

现有的以覆盖率引导为基础的fuzz技术被广泛应用在实战漏洞挖掘中。然而这些fuzz技术因为如下理由仍旧是不够高效的：

1. 现有的技术不足以在一个合理的时间量内达到完全的覆盖率。
2. 漏洞挖掘者希望能够尽早发现漏洞以便迅速修复。
3. 现有的fuzzing tools也被目标程序里内置的反fuzz手段降低了效率。

本文在分析了既有的fuzz技术后提出了一个现有fuzz技术都有的一个共性问题：这些工具都将fuzz过程中产生的每一条边（edge）视为相同重要的边，尽管一些边的终点在漏洞挖掘的角度上并不是那么有价值。这会导致那些更没有可能触发漏洞的代码跟更有可能触发漏洞的代码含有相同的权重。

基于这点改进，本文提出了一种名为Coverage Accounting的技术。Coverage Accounting技术的设计出发点有以下几点：

1. 在边的表达（edge representaton）上添加额外信息的工作对反fuzz手段的缓解没有作用。
2. 内存破坏的漏洞通常与内存操作更相关，而内存操作又可以从敏感函数调用，循环和基础块（basic block）这三个粒度来分析。于是为了更高效地发现内存破坏的漏洞，我们更应该关注那些会有敏感内存操作的代码。

故Coverage Accounting通过为代码路径赋予不同的权重来优先处理可能与安全相关性更高的路径。自然地，它的覆盖度量标准也就由以下三个维度构成：

1. 函数级别：根据函数的历史记录来判断是否涉及已知的安全问题。
2. 循环级别：检测循环结构，因为循环可能会导致缓冲区溢出等内存错误。
3. 基本块级别：考虑基本块内的指令是否涉及内存操作。

在具体的算法实现上，基于coverage accounting的工具TortoiseFuzz对原有的AFL做了如下改进：

• 定义安全敏感边缘：通过设置一个保守的阈值（例如，只要某个度量值大于0，则认为该边缘具有潜在的安全敏感性）。
• 输入优先级排序：更多地命中安全敏感边的输入被认为更有可能触发漏洞，因此会被优先考虑。
• **剪枝（Queue Culling )**：由TopAccounting记录的权重最高的几个参与者（candidates）可以覆盖到目前为止所有安全敏感的边。但要提高fuzz效率，则要通过剪枝来避免重复处理相同或相似的边缘覆盖情况。

在反fuzz技术上，基于在错误处理代码中增加时延和对代码进行混淆的反fuzz技术并不会影响基于Coverage Accounting技术的Tortoise Fuzz，因为Coverage Accounting并不需要做污点分析和符号执行，故代码混淆会失效，而错误处理代码一般不涉及主动内存操作，故在Coverage Accounting的评估下它会拥有更少的权重，工具会避免执行这样并非安全敏感的代码。甚至对于假分支（fake branch），TortoiseFuzz也是很健壮的，因为其中含有的pop和ret指令并不会被认为是安全敏感的操作，故也不会让访问假分支的输入被优先处理。

Coverage Accounting技术的提出，改善了本文先前提出的fuzz技术的几个问题，且与其它六个主流的fuzz工具相比，TortoiseFuzz比其中五个都挖掘出了更多的漏洞，且与QSYM相比，内存占用平均下来仅仅是前者的2%。