【网络安全研究进展系列】EcoFuzz:通过基于对抗式多臂老虎机的变异式模型而建模的自适应能量节约型模糊测试技术

admin 2022年11月2日10:12:20评论144 views字数 5463阅读18分12秒阅读模式

编者按

2022年5月,由网络安全研究国际学术论坛(InForSec)汇编的《网络安全国际学术研究进展》一书正式出版。全书立足网络空间安全理论与实践前沿,主要介绍网络和系统安全领域华人学者在国际学术领域优秀的研究成果,内容覆盖创新研究方法及伦理问题、软件与系统安全、基于模糊测试的漏洞挖掘、网络安全和物联网安全等方向。全书汇总并邀请了近40篇近两年在网络安全国际顶级学术议上发表的论文(一作为华人),联系近百位作者对研究的内容及成果进行综述性的介绍。从即日起,我们将陆续分享《网络安全国际学术研究进展》的精彩内容。


本文根据论文原文“EcoFuzz: Adaptive energy-saving greybox fuzzing as a variant of the adversarial multi-armed bandit”整理撰写,原文发表于USENIX Security 2020。作者在完成原文工作时,为国防科技大学在读博士研究生。本文较原文有所删改,详细内容可参考原文。

01

介绍

模糊测试是一种高效挖掘软件漏洞的自动化软件测试技术,于1989年被Miller等人率先提出。自此之后,模糊测试技术得到了快速的发展。其中,覆盖率引导的灰盒模糊测试技术(CGF)作为一种十分有效的漏洞挖掘技术,得到了诸多研究者的青睐。CGF通过插桩技术来获取程序运行时路径覆盖率信息,并通过遗传算法来挑选出优质的种子进行测试。


American Fuzzy Lop(简称AFL)是一款非常流行和经典的CGF。作为一款针对文件型应用的模糊测试器,AFL已经发现了相当多的高危漏洞。然而,当使用AFL对真实世界程序进行测试时,AFL仍然存在一些不足。主要问题在于,AFL产生的大量测试用例会执行一些高频路径,从而造成了大量能量的浪费(这里,我们定义能量为对种子进行变异而产生并执行的测试用例的数量)。特别是到了模糊测试后期,这些执行高频路径的种子已经很难产生执行新路径的测试用例。然而,AFL现有的调度算法却不能对种子分配适当的能量值。一个典型场景就是AFL在这些执行高频路径的种子上分配了太多的能量。这些问题充分反映了AFL调度算法的性能不足。更重要的是,AFL的调度算法并非是建立在一个科学的理论模型之上。


对此,研究人员提出了一些方法用于提升CGF调度算法的效率。AFLFast通过马尔可夫链进行建模,用转移概率来描述对种子进行变异产生执行其他路径的测试用例的概率。之后,AFLFast实施了一种单调递增型的能量调度算法来分配能量。这使得其分配的能量值可以快速地接近发现一条新路径所需要的最小能量。然而,AFLFast并不能在模糊测试过程中灵活调整能量分配的策略,进而增加了发现新路径的平均能量成本。此外,尽管AFLFast提出了转移概率并根据此确定了分配能量的方法,AFLFast却没有对转移概率进行进一步的详细分析,而且从一条已知路径到未知路径的转移概率是无法计算的。在这种情况下,挑选下一个种子并分配能量是博弈论中经典的“探索与利用”之间的权衡问题,而不是简单的概率问题。


本文提出了一种基于对抗式多臂老虎机的变异式模型(VAMAB)来对CGF的调度过程进行建模。我们的模型将种子看作老虎机,提出了获胜概率的概念用于描述种子变异产生执行新路径的测试用例的能力,并借此解释了CGF调度过程中探索与利用之间的权衡。与AFLFast所提出的单纯从概率论角度出发的马尔可夫链模型不同,我们的模型从博弈论的角度出发对CGF的调度过程进行解释,这也更加有助于理解调度过程中的挑战。根据VAMAB模型,我们提出了一种基于平均成本的自适应能量调度算法(AAPS)以及一种基于自转移频率的种子获胜概率评估方法(SPEM),并基于此在AFL基础上设计了一款自适应能量节约型灰盒模糊测试器——EcoFuzz。与AFL和AFLFast的调度算法相比,EcoFuzz实现了一种自适应能量调度机制,可以有效减少能量的浪费,在有限的执行次数内最大化路径覆盖率。本文对EcoFuzz在14个真实世界的软件上进行了测试,并与6个AFL类模糊测试器(包括AFLFast、FairFuzz和MOPT等)进行了比较,对EcoFuzz探索路径、节约能量、漏洞挖掘的能力进行了评估,并对能量调度和搜索策略算法的效率进行了细致全面的评估。实验结果表明,与AFL、FidgetyAFL、AFLFast.new相比,EcoFuzz能够分别在减少32%、35%、35%的测试用例情况下达到214%、110%、98%的路径覆盖率,有效地降低了平均成本。此外,EcoFuzz的能量利用率和有效挑选频率要远远高于FidgetyAFL和AFLFast.new。EcoFuzz还在多个开源软件中发现了13个未知漏洞,其中2个已经申请到了CVE编号。我们已经将EcoFuzz在GitHub上发布。


02

背景

1.AFL


AFL是由谷歌研究人员Michal Zalewski于2014年公布的一款面向文件类型的基于变异的灰盒模糊测试器。AFL以快速高效轻便著称,已经在诸多软件中发现了上百个漏洞,受到了诸多研究人员的关注与喜爱。AFL主要以覆盖率进行引导,通过轻量级的插桩技术来捕捉程序运行时的基本块信息,从而得到测试用例所执行的程序路径,并通过遗传算法来发现可能会覆盖新的代码路径的测试用例。AFL的效率主要受如下因素影响。


(1) 种子的搜索策略。AFL在运行时维护一个种子队列,按照种子在队列中的顺序依次循环挑选种子进行测试。为了提高测试效率,当有新种子加入队列时,AFL将执行速度快、字节长度短的新种子标记为“favored”。在测试种子时,AFL会优先测试被标记为“favored”的种子。这样的挑选策略使得AFL会在第一轮遍历种子队列时偏向于测试执行速度快的种子,以在初始阶段加快测试速度,提高测试效率。


(2) 变异策略及能量调度算法。AFL实施两种类型的变异策略:确定性变异策略和随机性变异策略。确定性策略主要包含比特级和字节级的翻转、算术加减、插入等操作。AFL在实施每一个确定性策略时,会依次遍历种子的每个比特或字节并实施策略。因此,当种子确定时,确定性策略所实施的变异次数是确定的,只与种子长度相关,所变异产生的测试用例集合也是唯一确定的。


在实施确定性策略之后,AFL会实施随机性策略,包括havoc和splice。在实施havoc时,AFL会随机选择变异策略并组合,通过随机数程序在随机位置实施这些变异策略,如此算作一次随机性策略的实施。splice策略与havoc策略类似,不同的是,splice策略先从种子队列中随机挑选出两个不同的种子,拼接产生一个新的种子,之后对新的种子执行多次havoc策略。如此,经过一次随机性策略的变异,AFL很可能会产生一个与种子相差很大的测试用例。随机性策略的执行次数则是由AFL根据种子的执行速度、长度等信息计算得出,一般来说,AFL会给执行速度快、长度短的种子分配更多的能量。特别地,一旦在随机性策略实施时,种子产生的测试用例执行了新的路径,本轮分配给该种子的能量便会翻倍。


总的来说,AFL执行速度快、可扩展性强、适用性广,适合在其之上进行性能优化,因此AFL受到了诸多研究人员的青睐。然而,AFL在测试效率方面也存在一定的局限性。AFL无法在能量分配过程中动态地自适应地调整策略,往往会对一些种子分配的能量高于种子发现新路径所需要的最小能量,造成了大量能量浪费。此外,AFL的搜索策略效率比较低,导致AFL需要花费更多的轮数来挑选到有价值的种子。此外,在通常情况下,相较于随机性策略,AFL确定性策略的效率比较低。


2.基于马尔可夫链的覆盖率引导的灰盒模糊测试技术


Böhme等人提出了用马尔可夫链对覆盖率引导的灰盒模糊测试进行建模的马尔可夫模型,并提出了CGF中的转移概率这一重要概念。


给定种子集合TS+为已经发现的路径,即T中种子所经历的路径S-为未被发现的路径。马尔可夫链状态空间被定义为所有路径的集合,即满足:


S=S+S-

特别地,对于路径iS+,转移概率pij被定义为由路径i所对应的种子ti变异产生出执行路径j的测试用例的概率,其中tiT


基于此模型,Böhme等人提出,一个更高效的CGF应当能够以较少的能量去发现那些尚未探索出的状态。由此,定义E[Xij为种子ti产生发现新路径j的测试用例的最小能量期望。为了探索路径j,高效的CGF应该能够挑选出E[Xij最小的种子ti进行测试,并分配能量值为E[Xij。特别地,Böhme等人推导出:

【网络安全研究进展系列】EcoFuzz:通过基于对抗式多臂老虎机的变异式模型而建模的自适应能量节约型模糊测试技术


然而,当测试真实程序时,精确计算从现有种子发现一条新路径的转移概率是不可能的。因此,通过精确计算转移概率来挑选下一个种子并分配能量的方法是不可行的。Böhme等人设计了单调递增型的能量调度方式,即在最初挑选种子ti时赋予较低的能量值,此后每次挑选到ti时,逐步增加分配的能量值,使得分配的能量值能逐步向E[Xij逼近,以此来减少能量开销,加快种子队列迭代速度,提高测试效率。在此基础上,Böhme等人设计并发布了AFLFast。AFLFast建议将队列中被选择次数最少的种子和执行的路径频率最低的种子标记为下一个favored的种子进行优先选择。然而,这种搜索策略的效率取决于所有种子的信息。如果有一个种子队列Q,其中一些来自Q的种子已经被模糊,而另一些则没有,那么对于没有被模糊的种子,我们获取到的信息很少。因此,为了更好地选择下一个执行路径概率最小的种子ti,需要对没有被模糊的种子进行测试来获取信息,这是一个经典的“探索与利用”之间的权衡问题。


3.多臂老虎机


多臂老虎机问题也称为MAB问题,是博弈论、组合学习、强化学习等领域中的一种常见问题。它的背景是玩家需要在N个老虎机中进行有限次尝试,每次尝试一个老虎机会有一定概率获得收益,玩家对于每个老虎机获得收益的概率和期望并不了解,需要在有限次数获得最大收益。


图1为MAB问题的说明图,其中,灰色的部分代表已经被尝试过的老虎机。在图1中,有N个老虎机,将它们依次进行编号。对这些老虎机,玩家每次会挑选且只能挑选一个老虎机进行尝试,对于任意老虎机i,它在玩家进行第t次挑选时的状态为

x(t),此时它所对应的获得收益的概率为R(x(t))。玩家的目标是需要在m次尝试中获得最大收益。特别地,当任意老虎机i获得收益的概率始终不变,即R(x(t))始终不变时,此时的MAB问题被称为经典的MAB问题。

【网络安全研究进展系列】EcoFuzz:通过基于对抗式多臂老虎机的变异式模型而建模的自适应能量节约型模糊测试技术

 图1


对经典的MAB问题来说,玩家所面临的最大困难是玩家事先并不知晓每个老虎机获得收益的概率Ri(xi(t)),因此无法直接挑选出获得收益概率最高的老虎机,只能通过在不断尝试中获得更多关于每个老虎机的信息,进而通过频率估算概率的方式来评估每个老虎机获得收益的概率,从中挑选出所评估的收益概率最高的老虎机进行反复尝试。一般来说,玩家对于某个老虎机i尝试的次数越多,他所能得到的老虎机i获得收益的频率就越接近于其真实概率Ri(xi(t)),这个过程称之为探索。如果玩家已经通过尝试评估了一些老虎机获得收益的概率,为了最大化收益,玩家可能会从中挑选玩家所评估的获得收益概率最高的老虎机进行尝试,这个过程称之为利用。


MAB问题的核心就是要处理探索和利用之间的博弈平衡。由于尝试的次数是有限的,如果玩家分配过多的次数在探索过程中,虽然会获得更多更准确的关于老虎机收益概率的信息,但也会使得分配过多尝试次数在低收益的老虎机上,使得总的收益降低;反之,如果玩家分配过多的次数在利用过程中,可能会使得玩家对于老虎机收益概率的信息掌握不全面、不准确,仅仅局限在掌握部分老虎机上,只关注获得信息中的最优解,没有对整体的信息进行探索,导致玩家可能会错过收益概率更高的老虎机,也限制了总的收益。因此,解决MAB问题需要根据现有信息调整好探索和利用之间的博弈平衡。


注意,在经典MAB问题中,我们假设每个老虎机的状态是与试验次数无关的,即它们获得收益的概率是恒定的,且老虎机的数量是恒定的。然而在实际中,随着问题条件的变化,往往会出现一些经典MAB问题的变体,例如对抗式多臂老虎机AMAB问题。


AMAB问题与经典的MAB问题不同,AMAB问题中所假定的老虎机在不同时刻的状态是可变的,即它们获得收益的概率是可变的。特别地,常见的AMAB问题中,每个老虎机的获胜概率是会随着获取收益次数的增加而减少的。而这一点也恰恰与灰盒模糊测试类似,随着测试时间的增长,每个种子发现新路径的可能性也越来越小。因此,本文考虑在AMAB问题的基础上对CGF的调度问题进行建模。


(本文选取了文章部分章节,更多精彩内容请阅读《网络安全国际学术研究进展》一书。)

作者简介

乐泰,国防科技大学计算机学院在读博士研究生。他的主要研究方向为模糊测试技术, 研究成果发表于USENIX Security等国际会议与期刊。


版权声明:本书由网络安全研究国际学术论坛(InForSec)汇编,人民邮电出版社出版,版权属于双方共有,并受法律保护。转载、摘编或利用其它方式使用本研究报告文字或者观点的,应注明来源。


【网络安全研究进展系列】EcoFuzz:通过基于对抗式多臂老虎机的变异式模型而建模的自适应能量节约型模糊测试技术

本报告数量有限,关注公众号私信我们可以享受六折优惠,欢迎订阅!

【网络安全研究进展系列】EcoFuzz:通过基于对抗式多臂老虎机的变异式模型而建模的自适应能量节约型模糊测试技术


原文始发于微信公众号(网安国际):【网络安全研究进展系列】EcoFuzz:通过基于对抗式多臂老虎机的变异式模型而建模的自适应能量节约型模糊测试技术

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年11月2日10:12:20
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   【网络安全研究进展系列】EcoFuzz:通过基于对抗式多臂老虎机的变异式模型而建模的自适应能量节约型模糊测试技术http://cn-sec.com/archives/1383126.html

发表评论

匿名网友 填写信息