纪检监察网站建设的意义,用那个程序做网站收录好,怎么制作属于自己的app,上传网站程序是什么文章目录 前言PathAFL#xff1a;Path-Coverage Assisted Fuzzing1、解决的问题和目标2、技术路线2.1、如何识别 h − p a t h h-path h−path#xff1f;2.2、如何减少 h − p a t h h-path h−path的数量#xff1f;2.3、哪些h-path将被添加到种子队列#xff1f;2.4、种… 文章目录 前言PathAFLPath-Coverage Assisted Fuzzing1、解决的问题和目标2、技术路线2.1、如何识别 h − p a t h h-path h−path2.2、如何减少 h − p a t h h-path h−path的数量2.3、哪些h-path将被添加到种子队列2.4、种子选择算法2.5、资源调度 3、达到的效果3.1、一个简单例子的结果RQ13.2、代码覆盖率和崩溃测量RQ23.3、LAVA-M数据集RQ3的结果3.4、发现现实世界中的漏洞RQ3 4、结论 总结 前言 此博客为PathAFLPath-Coverage Assisted Fuzzing论文的阅读笔记本篇论文提出了一种新的跟踪执行路径的方法、路径过滤算法和追踪执行路径的方法以提高Fuzz的准确性以及Fuzz性能。本文将会从解决的问题和目标、技术路线、达到的效果和结论四个角度来分析本篇论文。以下就是本文的全部内容。 PathAFLPath-Coverage Assisted Fuzzing
1、解决的问题和目标 现有的覆盖引导fuzzer通常使用所探索的基本块或边的数量来测量代码覆盖路径覆盖可以提供比基本块和边缘覆盖更准确的覆盖信息。然而路径的数量随着程序大小的增加而呈指数级增长几乎不可能追踪真实世界应用程序的所有路径这也是本文亟待解决的问题。针对此问题本文完成了以下几个目标
作者提出了一种新的跟踪执行路径的方法并在跟踪路径覆盖粒度和fuzzing性能之间进行了权衡。研究发现作者可以用很少的开销来追踪重要的路径作者设计了一种路径过滤算法它对新的路径做出了快速的判断。只有那些满足特定条件并具有高权重的路径才会添加到种子队列中作者提出了一种追踪执行路径的新方法并在追踪路径覆盖的细粒度和模糊性能之间进行了权衡。研究发现作者可以在几乎没有额外开销的情况下追踪重要路径作者开发了PathAFL的开源实现并将其作为AFL的分支发布在Github上
2、技术路线 关于PathAFL的工作过程如下图所示紫色的组件显示了作者对原始AFL的改进 由上图可知PathAFL是在AFL的基础上进行改进的而AFL的整个工作流程如下所示
对目标应用插桩向种子队列提供初始输入选择种子。AFL根据种子选择算法从种子队列中选择一个种子该算法更喜欢更快、更小的种子。种子选择算法采用贪婪算法实现如下图所示 变异种子。该步骤使用多种变异算法对种子文件进行变异并在循环中生成大量测试用例测试和跟踪。此步骤以测试用例为输入执行并跟踪插桩指令的目标应用程序报告崩溃。如果发现崩溃则可能触发了潜在的漏洞识别种子。如果发现新的边缘覆盖状态则将测试用例添加到下一个循环的种子队列中如果该种子的fuzzing结束则转到步骤(3)否则转到步骤(4) 需要注意的是整个fuzzing处理过程是一个无限循环只有在手动终止时才会结束循环。此外因为AFL使用哈希计算来存储边缘覆盖信息需要通过在每个BBL中插入一个BID随机数来进行哈希计算不过这样会存在哈希冲突的问题哈希冲突率通常在30%~70%范围内浮动。为了解决这个问题AFL又发展为了CollAFLCollAFL使用新的哈希计算来存储边缘覆盖信息这样可以让哈希冲突降低到接近0%不过CollAFL只使用了边缘覆盖。此外CollAFL还遵循以下三个新的种子选择策略
具有更多未受影响的相邻分支的种子将优先进行fuzzing处理更喜欢有更多未受影响的邻居后代的种子更喜欢具有更多内存访问操作的种子 现在我们对AFL和CollAFL已经有了较深的理解不过上面提到的这两种技术的覆盖率信息又是什么东西呢覆盖率信息可以看作是评判fuzzer的能力的一项指标覆盖率越高说明fuzzer探索到的路径越多故越有可能发现漏洞反之则说明覆盖率越低说明fuzzer探索到的路径越少故越没有可能发现漏洞。目前测量代码覆盖率的方法主要有三种 B B L BBL BBL覆盖率基本块覆盖率 B B L BBL BBL是一个有一个入口和一个出口点的代码片段BBL中的指令将按顺序执行并且只执行一次。 B B L BBL BBL是程序执行的最小相干单元可以通过第一条指令的地址来识别。通过代码插入和静态分析可以很容易地提取BBL信息。由于这些优点 B B L BBL BBL覆盖信息被fuzzer广泛使用。而典型的基于 B B L BBL BBL的覆盖引导fuzzer只跟踪每个块是否被击中而不跟踪fuzzing过程中哪些块被击中的顺序因此详细信息会丢失。如下图所示在fuzzing过程中如果首先执行程序路径 1 A B C D 1ABCD 1ABCD则与程序路径 2 A B D 2ABD 2ABD相关联的测试用例将永远不会添加到种子队列中因为路径 2 2 2没有命中新的 B B L BBL BBL因此边缘 B D BD BD的信息将丢失。 边缘覆盖率为了解决 B B L BBL BBL覆盖的缺点边缘覆盖跟踪每条边缘是否被击中。在上图的例子中如果首先执行程序路径 1 A B C D 1ABCD 1ABCDfuzzer将记录边缘 A B AB AB、 B C BC BC和 C D CD CD当执行路径 2 A 、 B 、 D 2A、B、D 2A、B、D时将记录新的边缘 B D BD BD因此与路径 2 2 2相关的测试用例现在将添加到种子队列中。然而边缘覆盖并不能追踪边缘被命中的顺序因此一些详细信息可能会丢失。我们使用下图中的简单程序和其控制流图来说明这个问题该程序以 8 8 8个字符作为输入。当输入为abcd**‼$或**cdef!!时程序将崩溃。 路径覆盖率基于路径覆盖的方法跟踪整个执行路径包括命中的顺序边缘从而记录最丰富的信息。几乎不可能为真实世界的应用程序实现路径覆盖因为程序中有太多的循环和条件路径的数量会激增。海量路径将带来较大的运行时开销并可能降低模糊处理的效率。为了克服这个问题作者将新探索的路径分为两类 对于之前未触及的边作者将其表示为 e − p a t h e-path e−path。 “ e − ” “e-” “e−”表示路径有新的边所有边都已接触的路径作者将其表示为 h − p a t h h-path h−path。 “ h − ” “h-” “h−”表示路径有一个新的哈希 关键问题是如何处理大量的 h − p a t h h-path h−path作者的解决方案是不将所有的 h − p a t h h-path h−path添加到种子队列而只将那些高权重的 h − p a t h h-path h−path增加到种子队列。这是一种效率和追踪粒度之间的权衡。 根据上文分析可以发现目前主要的挑战是路径的数量随着程序大小的增加而呈指数级增长。因此建议只向种子队列添加重要路径。根据这一思想作者总结了路径覆盖辅助fuzzer的三个关键问题
如何识别 h − p a t h h-path h−path如何减少 h − p a t h h-path h−path的数量?哪些 h − p a t h h-path h−path将被添加到种子队列
2.1、如何识别 h − p a t h h-path h−path 静态插桩。AFL在编译时对目标程序进行插桩。插桩代码计算边缘哈希并更新边缘覆盖记录到共享内存中。PathAFL维护一个类似AFL的全局哈希表。表索引表示路径哈希值表示路径是否被覆盖。PathAFL以类似的方式对目标程序进行插桩。它只在AFL原始插桩代码中插入了一小段代码来计算路径哈希。此外PathAFL扩展了原始共享内存以存储路径哈希值的4个字节。在程序执行期间执行路径的哈希值会实时计算并追加到共享内存中。当程序运行完成时执行路径哈希可用于确定是否已探索新路径。与AFL相比PathAFL只在插入代码中添加了哈希计算函数导致开销增加很少。
2.2、如何减少 h − p a t h h-path h−path的数量 PathAFL采用两种方法来降低执行路径的跟踪粒度以便模糊器可以限制新 h − p a t h h-path h−path的数量 选择性插桩AFL默认情况下对目标程序中的所有边缘进行检测使我们能够跟踪几乎所有的执行路径。为了减少路径PathAFL必须降低跟踪粒度只检测部分 B B L BBL BBL并跟踪到达新BBL或触发新错误的概率更高的路径。为了实现这个目的PathAFL仅对一些函数进行执行路径的插桩。提出以下四个策略来选择关键函数根据以下策略可以有效地减少新发现的 h − p a t h h-path h−path的数量 插桩较大的函数默认为最大的 20 20% 20。因此可以找到许多通过这些函数的 h − p a t h h-path h−path插桩具有内存操作的函数例如函数名包含alloc/free的函数忽略太小的函数。类似于第一个策略函数越小代码越少对其他函数的 10 10% 10进行插桩 哈希算法作者采用了一个非常简单的方案直接使用全加运算作为路径哈希算法并以粗粒度的方式区分执行路径。哈希算法如下 p p p表示执行路径。 B S BS BS表示所有插桩的基本块的执行序列。只需在现有的插桩代码中插入一个add汇编指令对测试程序的运行效率几乎没有影响。哈希表的大小与AFL中的位图相同。请注意此方法仅用于计算路径哈希不影响 AFL 的原始边缘哈希计算。
2.3、哪些h-path将被添加到种子队列 为了进一步减少添加到种子队列的 h − p a t h h-path h−path的数量设计了一种策略来确定是否向种子队列添加 h − p a t h h-path h−path
效率是一个关键因素 e − p a t h e-path e−path比 h − p a t h h-path h−path更重要应该选择变异后更有可能接触到新边缘的 h − p a t h h-path h−path 正如以下算法所示作者设计了一种快速过滤算法来满足这些要求。
2.4、种子选择算法 在AFL的原始种子选择算法中存在一个小问题。它虽然确保 F F F受青睐的种子集覆盖所有探测到的边但它并不能确保在一个fuzzing测试循环中测试的受青睐的种子涵盖所有已发现的边此问题正如下面的算法所示。 针对此问题作者提出了一个新的种子选择算法如下图所示。它修复了上述提到的缺陷确保在一个模糊测试周期中测试的受青睐的种子将覆盖所有已发现的边。
2.5、资源调度 PathAFL根据路径的权重实现新的资源调度并将更多的资源分配给更高权重的路径。具体来说它将所有路径按权重划分为六部分每一部分都分配了不同的资源。
3、达到的效果 作者使用IDA进行静态分析。编写IDAPython脚本来自动分析程序结构获得边缘信息并为目标程序生成数据文件。该文件记录所有边缘信息作为PathAFL的输入以计算路径权重。下表展现了关于静态分析的时间开销。
3.1、一个简单例子的结果RQ1 此部分的实验用于回答RQ1即“跟踪执行路径对于fuzzing是否可行”。作者以第1.3节中讨论的例子作为测试用例对其所有边进行了插装以在使用PathAFL进行测试时计算路径哈希。结果显示在下表中。AFL和CollAFL-x在7天内未能触发崩溃而PathAFL和PathAFL-np仅用了一个小时就触发了。此外PathAFL和PathAFL-np分别在一天内触发了6次和8次崩溃。 这个实验表明PathAFL能够有效地识别 h − p a t h h-path h−path并且使用 h − p a t h h-path h−path引导模糊测试是可行的。
3.2、代码覆盖率和崩溃测量RQ2 此部分的实验用于回答RQ1即“PathAFL的代码覆盖率有多好”。在本次实验中作者选择了如下几个流行的应用程序进行测试。 下表显示了四个模糊测试工具探索的路径和边的数量。 以上实验表明PathAFL和PathAFL-np探索的路径数量几乎相同但PathAFL探索的边的数量比PathAFL-np多。故认为PathAFL更好可能触及更多的新代码分支。 下图显示了10个实验中不同fuzzer随时间的增长的代码覆盖率的增长。 这再次表明作者的解决方案是有效的。 下表统计了触发的唯一崩溃的平均数量。 此结果表明PathAFL在找到程序中存在的不同崩溃方面表现出色。 总之PathAFL在路径和边缘发现方面优于AFL和CollAFL-x。而且最好使用资源调度。这些实验证明所提出的解决方案可以帮助提高路径和边缘覆盖率并引发更多的崩溃。
3.3、LAVA-M数据集RQ3的结果 此部分的实验用于回答RQ1即“PathAFL的错误检测能力有多好”。作者在LAVA-M数据集上对AFL和PathAFL进行了为期7天的评估。且对每个实验都进行了五次并对所有发现的bug进行了计数。评估结果如下表所示。 结果表明与AFL相比PathAFL发现了更多的错误。具体来说PathAFL发现了AFL发现的所有错误。此外PathAFL发现了base64中注入的所有漏洞甚至发现了LAVA-M的作者没有列出的四个新漏洞。
3.4、发现现实世界中的漏洞RQ3 作者选择了binutils、libav和libtiff进行实验并使用PathAFL发现了许多严重的漏洞和几个bug如下表所示。 所有的错误和漏洞以前都没有报告可能会带来一些安全风险。作者联系了这些工具的开发人员并提交了错误详细信息。
4、结论 在本文中作者辅助fuzzer进行路径覆盖讨论了其中的一些挑战并最终实现了一个名为PathAFL的新fuzzing系统。它采用了粗粒度的路径跟踪和快速过滤算法可以有效地选择更高权重的 h − p a t h h-path h−path大大增加了路径覆盖的数量。此外作者还设计了一种基于路径权重的种子选择算法和资源调度。作者在几个不同的实验中对其进行了评估结果证明 PathAFL 在改善边缘覆盖和发现更多唯一崩溃方面比AFL和CollAFL更为有效。在经过充分测试的程序中PathAFL 发现了8个新的安全漏洞分配了6个CVE编号。 总结 以上就是本篇论文阅读笔记的全部内容了读完这篇论文后相信各位读者朋友也会认为本篇论文写的相当不错当然有些地方笔者可能也理解不深欢迎各位读者朋友与我积极讨论。后面如果有时间我会分享阅读本篇论文的心得体会
