Multiple Targets Directed Greybox Fuzzing
简介
定向模糊测试可以快速地发现和复现程序中的bugs。然而，由于他们静态的状态的区分和粗粒度的能量调度，现有的DGF在面对多目标的时候，表现很差。
本文提出了多目标定向灰盒测试，目的是探索程序的多个目标位置。具体来说，提出了一种新的策略来交互exploration和exploitation，以及一种考虑种子和目标位置关系的能量调度策略。
并将以上方法实现为一个工具，叫做LeoFuzz，并评估其在crash reproduction，true positive verification，vulnerability exposure的表现。实验结果表示，LeoFuzz优于现有的六个模糊测试，QYSM，AFLGo，Lolly，Berry，Beacon和WindRanger。而且，在真实程序中发现了23个新的漏洞，其中11个获取了CVE ID。
背景
一个程序中通常会有多个漏洞存在。这种情况要用定向模糊测试找的话，有两种方法。
- 开n个fuzzing的进程，然后给一个target，让定向模糊测试跑。
- 给多个目标，直接给模糊测试跑。
本文的目标是增强第二种方法的有效性和效率。
现有定向模糊测试在处理多目标的时候，表现很差，原因在于两点：粗粒度的能量调度和静态化的状态划分。
能量调度策略是用来控制种子变异的次数。在DGF中，调度策略会逐渐添加能量到距离目标更近的种子上，能够更快地触发目标位置。比如，AFLGo，给更多的能量到离所有目标近的种子，虽然这种策略使得AFLGo忽视了局部最优。
问题1：为了覆盖更多的目标，就会追求对所有target的全局最优，而忽视了对于一些target的局部最优，从而导致一些目标很难到达。设计一种合理的能量调度算法，能够在有限的时间到达更多的target又是另外一个问题。
DGF分为两个阶段运行，探索（exploration）和利用（exploitation）。在探索阶段，fuzzer通过种子变异来尽可能获取更大的代码覆盖率。在利用阶段，fuzzer变异并执行种子来使得种子离目标位置更近。比如，AFLGo从探索阶段开始，随机变异初始种子去生成新的输入，来增加代码覆盖率。在利用阶段生成更多新的输入离目标更近。然而，区分利用和探索的阶段是静态确定的。比如说，AFLGo设定用20小时去探索，然后用4小时去利用。这种静态切换的策略忽视了动态的运行信息，并且会影响AFLGo的性能。
问题2：更少的探索会提供更少的覆盖率信息用来利用，使得在利用阶段更难生成高质量的种子。然而，过多的探索会消耗过多的资源，而且减少了利用的时间，缺少了定向性。因此，怎么动态地平衡二者的关系是一个挑战。
方法
静态分析
静态分析分为两个部分：目标序列生成以及静态插桩。
目标序列生成主要是给定一个target，生成target必经的序列。然后再由静态插桩，将对至少有一个target的基本块进行插桩。这样在运行时不仅可以获取覆盖率信息，也可以获取执行轨迹信息。
目标序列生成类似Berry和Lolly。都是基于Dominator Tree生成。
比如下面这个例子，给定目标点g，先通过调用图的支配树找到到达点g所在函数的必经调用链，然后在函数G里，再找必经基本块。最后串起来是：main1->A1->entry->a->f->g
动态分析
总体算法思路挺清晰易懂的。首先根据stageCoord函数先确定是exploration还是exploitation。如果是exploration就从覆盖率队列取种子，反之从另外一个队列取种子。然后给种子赋予能量。在执行种子的过程中，如果发生崩溃，就送到崩溃种子集合里。反之，检查两个覆盖率的情况。如果目标序列的覆盖率增加了，就将变异后的种子加入到DQ序列，并更新dsc，csc和ndc的值。如果代码覆盖率增加了，就将变异后的种子加到CQ序列中，更新csc，ndc的值。如果都没增加就增加ndc的值。直到时间结束。
然后是状态切换的算法，如果是exploration状态，检查下csc/(csc+dsc)是否大于某个值，大于就切换到exploitation阶段。csc表示覆盖率队列的长度，dsc表示定向队列的长度。这个条件说明当fuzzer有了足够多的覆盖率信息，就可以切换到利用状态了。如果一开始的话，是不是就直接切换到exploitation阶段了？当然作者马上给出了阶段，将初始的dsc设置为10，以防一开始就切换到exploitation阶段。另外这里的Rate的计算也是动态更新的。rate越大，在探索阶段的时间越大。为了平衡exploration和exploitation，使用下面的公式去更新Rate的值。cdsc/根号t的值越大说明在利用阶段产生的种子越多，并且当前的代码覆盖率足够到达目标，需要更快切换到exploitation阶段。另外随着时间的增加，找到定向种子的概率也会变小，所以用epoch参数来调整这个影响。
如果是exploitation阶段，计算阈值th，如果ndc大于阈值th就切换到exploration状态。阈值的计算是看后两轮的exploitation阶段的ndc的值加起来乘以开根号的epoc再乘以1/2.为啥这么算呢？作者认为ndc小于这个阈值的时候，就说明fuzzer的利用能力很弱了，需要切换到exploration阶段发现更多的路径。阈值这么设计是因为找到一个新的定向种子的可能性会在fuzzing的过程中下降，所以需要在每轮epoc中增加阈值的大小，来保证fuzzer能够在利用阶段更久一些。
接下来是介绍种子能力调度的模块。
对于一个种子和多个目标来说，LeoFuzz会在静态分析阶段生成所有的目标序列，并且在fuzzing阶段获取种子。文中考虑了三类种子和目标序列的关系。
目标序列的优先级。能够说明目标序列和其他序列的相似性。LCS表示两个序列的最长公共子串。Max返回两个序列的最大长度。优先级越高表示有更多的机会可以通过变异到达多个目标。他的优先级是根据序列的简单程度来判断的。
目标序列的最大覆盖率。它表示任何执行轨迹的最大覆盖率。能够估计覆盖目标序列的难度，并且随着动态分析进行更新。
种子序列覆盖率。它用来衡量种子执行轨迹和目标序列的相似度。
基于上面三个指标，合成为一个指标CF，来用于后续的种子能量分配。
同样也是用模拟退火算法来寻找CF的全局最优。后面的思路基本类似AFLGo。
另外，由于模糊测试通过变异难以到达较深的程序路径。为了解决这个问题，同样引入了concolic executor。利用concolic executor跑一遍种子，然后生成新的种子。种子主要是从DQ队列中取。
结果
主要讨论这六个问题：
Leofuzz在一个target的时候效果如何？
- 连单一的target的效果都好。这个target怎么设定的，存在疑惑。
在crash reproduction这个应用效果如何？
多个target的时候效果咋样？
- 多个target怎么来的没说。
true positive的验证效果如何？
- 用的libming 来做实验。target来源于clang static analyzer
- 基本时间在一个小时以内。只验证了libming？不知道其他的效果如何？
能否发现未知漏洞
- 在cxxfilt 2.36，SWFTools 和 libredwg里发现了11个0 day漏洞。
哪些设计影响了最后效果?
主要考虑了四个决策对最后结果的影响。
- target sequence enhancement
- exploration exploitation coordination
- fine-grained energy scheduling strategy
- concolic execution
最后贡献度排名是：MES>CEE>target sequence enhancement > concolic execution
concolic execution提升小反而是没想到的。
相关工作
AFLGo是第一个定向模糊测试，它的模拟退火能量调度策略会分配更多能量给离目标位置近的种子。基于AFLGo，Hawkeye支持间接调用，并调整了AFLGo的种子选择，能量调度和变异策略。然而AFLGo和Hawkeye都不支持多目标。同样，基于AFLGo，RDFuzz通过结合到目标点的距离以及路径的频率，并使用静态调度模块来协调exploration和exploitation。
也有一些定向模糊测试使用sanitizer的输出来指导fuzzing。SAVIOR使用了UBSan的输出作为目标点。然后基于种子遇到的新分支和在这些分支上的目标点和求解分支约束的难易度来计算种子的能量。ParmeSan利用多个sanitizers报告的error和warning来作为目标点，并且用种子到目标的距离来指导模糊测试。LeoFuzz也可以使用sanitizers的结果作为target。
另外一些定向模糊测试使用数据流分析。CAFL目标是满足一序列的约束条件，然后优先选择最适合这些条件的种子。它定义了一个单一目标点的约束条件以及一些可选的数据条件。CAFL需要额外的信息源，比如内存检测器的crash dump或者补丁的changelogs。WindRanger使用基本块的deviation和他们的数据流信息来计算种子的距离。他也会动态的在exploration和exploitation切换。Beacon使用静态的方法提前识别出不可达的路径。
总结
从这篇文章看得出来，作者用了很多他自己以前工作的东西。比如dominator tree，LCS，混合测试等等。
实验做的很充分。还发现了许多0day漏洞。从时间来看，在2021年就挖到了不少cve，22年的6月投稿TDSC。看得出来工作量蛮大的。
作者前面几篇发的论文berry和lolly也用在本次的对比试验了。作者这个技术路线还是挺清晰的，值得学习。