G.O.S.S.I.P 阅读推荐 2022-11-01 Alphuzz

admin
admin
admin
101113
文章
87
评论
2023年1月30日19:05:57评论77 views字数 1829阅读6分5秒阅读模式
十一月的第一篇论文推荐是来自武汉大学赵磊老师团队和加州大学河滨分校尹恒研究组合作并投稿的关于种子调度的最新研究工作Alphuzz: Monte Carlo Search on Seed-Mutation Tree for Coverage-Guided Fuzzing，目前该工作已经被ACSAC 2022录用。
G.O.S.S.I.P 阅读推荐 2022-11-01 Alphuzz
研究背景
种子调度，即在种子池中选择出一个种子作为后续种子变异的基础的这一过程，在基于代码覆盖率的模糊测试中十分重要。其重要性主要体现在选择出的这个种子决定了模糊测试探索程序状态的方向。具体而言，种子调度选出一个种子后，模糊测试沿着它覆盖的路径，通过种子变异尝试覆盖其邻接的未覆盖路径。不同的路径引导模糊测试探索不同的程序代码区域。
研究人员提出了很多种子调度策略，通过设定的指标来衡量种子的价值，并且选择最优的种子。比如：AFL倾向于选择小的、执行时间短的种子；FairFuzz优先选择覆盖低频分支的种子；AFLFast给覆盖低频路径的种子更多的能量，EcoFuzz优先选择新生成的种子以及变异过的贡献高的种子。
然而，已有的种子调度策略往往只关注单个种子的特征，忽略了种子之间的关系对模糊测试的影响。在这篇文章中，作者论证了种子之间的变异关系对种子调度的影响，并基于种子之间的变异关系提出了一种新的种子调度策略。
提出的方法
1. 种子变异树
在这篇文章中，作者发现种子之间的变异关系对种子调度十分重要。正如前面所说，种子变异可以视为沿着种子覆盖的路径探索其邻接的未覆盖路径。因此变异关系可以体现种子覆盖的路径之间的关系。作者利用种子之间的变异关系，构建一个“种子变异树”。树上的每一个节点表示一个种子，每一条边表示变异关系。如种子t1经过变异生成种子t2，那么在树中，t1就是t2的父节点。这样构建出的种子变异树可以视为程序执行树的一个近似。在同一个子树下的种子代表了程序执行的一个方向，不同的子树代表程序执行的不同方向。图2展示了不同的种子调度策略的示意图。
G.O.S.S.I.P 阅读推荐 2022-11-01 Alphuzz
在种子变异树中内部节点有两个角色，一方面表示一个种子，另一方面表示以它为根节点的子树。因此，作者将内部节点按角色拆分，在内部节点下加一个变体子节点，即该子节点代表原有的种子，而内部节点表示一个子树。树型结构如下：
G.O.S.S.I.P 阅读推荐 2022-11-01 Alphuzz
2. 种子调度策略
种子变异树上的种子代表了程序执行的不同方向，如何在不断增长的种子变异树中快速搜索出最优的种子、如何随着模糊测试的演化更新种子变异树、如何平衡种子调度的探索和开发是种子调度面临的挑战。
作者提出了一个基于蒙特卡洛树搜索的种子调度策略，并设计了基于UBT算法的种子分数计算方法。种子调度的整体流程如图4所示：每轮从根节点开始向下搜索，计算当前节点的子节点的分数，选择分数最高的子节点继续向下搜索，每次选择分数最高的节点，直到选中的节点为叶子节点，本轮种子调度结束。选中的种子经过变异生成的有趣测试用例根据种子变异关系增加到种子变异树中，然后从新添加的节点到根节点的反向路径上的所有父节点更新被选中的次数以及覆盖的分支，以指导下一次种子调度。
G.O.S.S.I.P 阅读推荐 2022-11-01 Alphuzz
3. 种子分数计算方法
作者基于UCT算法设计的种子分数计算方法如下。公式的左边表示种子已有的平均收益，公式右边表示种子的潜在收益。具体而言，   是种子或者一个子树中所有节点覆盖的所有分支或者一个叶子节点覆盖的所有分支，  是种子选中的次数，  是父节点选中的次数。
G.O.S.S.I.P 阅读推荐 2022-11-01 Alphuzz
实验评估
作者分别在AFL和AFL++的基础上实现了两个方法原型工具Alphuzz和Alphuzz++，并且在三个数据集（CGC，UniFuzz以及12个real-world程序）上开展实验。实验中用于比较工具有两组，一组是基于AFL的工具，包括AFL，AFLFast，FairFuzz，EcoFuzz，另一组是基于AFL++的工具，包括AFL++和AFL++-HIER。
作者从代码覆盖率、漏洞发现数量、吞吐量、参数k的影响等方面开展实验。部分实验结果如下：
G.O.S.S.I.P 阅读推荐 2022-11-01 Alphuzz
G.O.S.S.I.P 阅读推荐 2022-11-01 Alphuzz
G.O.S.S.I.P 阅读推荐 2022-11-01 Alphuzz
G.O.S.S.I.P 阅读推荐 2022-11-01 Alphuzz
总结和讨论
Alphuzz和Alphuzz++在代码覆盖率、漏洞发现数量方面相比已有工具都有提升，并且对吞吐量和参数k进行了讨论。此外还发现了三个新的CVE。但是实验部分对于参数k的讨论不够全面，还需考虑不同的运行时间、程序特点、测试目标等因素。

论文获取请联系武汉大学赵易如同学
联系邮箱：[email protected]

原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2022-11-01 Alphuzz

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2023年1月30日19:05:57
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                   G.O.S.S.I.P 阅读推荐 2022-11-01 Alphuzzhttps://cn-sec.com/archives/1385248.html

发表评论

匿名网友 填写信息