论文阅读-EMS: History-Driven Mutation for Coverage-based Fuzzing(2022)模糊测试

一、背景

        本文研究了基于覆盖率的模糊测试中的历史驱动变异技术。之前的研究主要采用自适应变异策略集成约束求解技术来探索触发独特路径和崩溃的测试用例,但它们缺乏对模糊测试历史的细粒度重用,即它们在不同的模糊测试试验之间很大程度上未能正确利用模糊测试历史。

        本文提出了一种轻量级且高效的 概 率 字 节 定 向 模 型(PBOM),以捕获来自试验历史的字节级变异策略,并因此有效地触发独特路径和崩溃。

        本文还提出了一种新的历史驱动变异框架EMS,用于加速基于覆盖率的模糊测试中的路径和漏洞发现。它将PBOM作为变异算子之一(包括 intra-PBOM和inter-PBOM),根据输入字节值概率性地提供所需的变异字节值。即EMS将PBOM作为附加变异操作符,根据输入字节值和长度概率性地提供所需变异字节值和类型。

PBOM是为了实现下面的目的:

从 内 部 和 内 部 历 史 中 捕 获 触 发 独 特 路 径 和 崩 溃 的 突 变 策 略 。 换 句 话 说 , 给 定 来 自 种 子 测 试 用 例 的 输 入 字 节 值 , 学 习 到 的 突 变 策 略 模 型 应 该 能 够 输 出 相 应 的 突 变 值 和 导 致 测 试 用 例 触 发 今天唯 一 路 径 或 崩 溃 的 突 变 类 型 。

实验结果表明,EMS在9个真实世界程序上比AFL、QSYM、MO PT、MO PT-dict、EcoFuzz和AFL++等最先进的模糊测试工具发现了多达4.91倍的独特漏洞,并在大多数程序上发现了更多的覆盖。

本文的创新动机在于:利用模糊测试历史来加速发现新的路径和崩溃。

二. INTRODUCTION

A. Mutation-based Fuzzing

变异测试的流程包括:1)准备初始种子集并构建队列;2)从队列中选择种子测试用例并随机变异;3)使用变异后的测试用例测试目标程序,并将触发新执行路径或异常行为的有趣测试用例添加到种子队列中;4)回到步骤2)继续模糊测试。

大多数变异测试工具使用简单的逻辑来变异测试用例,如AFL使用三个阶段的变异操作:

  • 确定性阶段:AFL利 用 位 或 字 节 级 突 变 操 作 符 , 例 如 位 翻 转 、 字 节 翻 转 和 字 节 插 入 , 来 改 变 种 子 测 试 用 例 的 每 个 位 或 字 节
  • 混沌阶段:AFL多 次 随 机 选 择 操 作 符 , 并 在 种 子 测 试 用 例 的 随 机 位 置 使 用 所 有 操 作 符 进 行 突 变
  • 拼接阶段:AFL首 先 将 两 个 种 子 测 试 用 例 的 部 分 剪 接 在 一 起 , 生 成 一 个 新 的 用 例 , 然 后 进 入 破 坏 阶 段 ,使 用 进 一 步 的 突 变 算 子

传 统 的 基 于 突 变 的 fuzzers没 有 分 析 如 何 解 决 路 径 约 束 ,而 是 利 用 随 机 突 变 的 测 试 用 例 来 测 试 程 序 , 盲 目 地 探 索 新 的 执 行 路 径 。 由 于 逻 辑 直 接 , 基 于 突 变 的 fuzzers的 执 行 速 度 很 快 , 导 致 了 有 效 的 漏 洞 探 索 。 但 是 , 直 接 的 逻 辑 无 法 解 决 复 杂 的 路 径 约 束 , 限 制 了 模 糊 的 效 率 。 因 此 , 大 量 的 工 作 集 中 在 提 高 路 径 覆 盖 上 , 并 在 基 于 突 变 的 模 糊 之 上 发 展 基 于 覆 盖 的 模 糊。

B. Coverage-based Fuzzing

为 了 解 决 上 述 基 于 突 变 的 模 糊 测 试 的 局 限 性 , 研 究 人 员 提 出 利用覆盖率信息作为反馈来指导模糊测试过程,以提高模糊测试的性能。


法一:一些工作采用自适应策略来改进基于覆盖率的模糊测试

        例如AFLFast和EcoFuzz,它们分别使用马尔可夫链模型和对抗多臂老虎机模型来评估每个测试用例触发唯一分支行为的潜力,然后分配更多时间来变异有潜力的测试用例。

        MOPT提 出 突 变 算 子 的 最 优 选 择 概 率 分 布 在 不 同 的 目 标 程 序上 是 不 同 的。提出了一种迭代调度策略,根据发现唯一路径和崩溃的效率自适应调整每个变异操作符的选择概率分布。

法二:将基于突变的模糊与约束求解技术(如 concolic execution)相结合  

为 了 解 决 路 径 约 束 , 这 些 技 术 应 该 首 先 利 用 强 大 的 仪 器 来 编 译程 序 来 跟 踪 和 收 集 路 径 约 束 。 然 后 , 约 束 求 解 技 术 需 要 执行 昂 贵 的 过 程 , 包 括 模 拟 路 径 约 束 , 跟 踪 影 响 目 标 约 束 的数 据 字 段 , 以 及 计 算 可 以 触 发 约 束 不 同 状 态 的 数 据 字 段 的数 值 区 间 。因 此 , 约 束 的 收 集 和 求 解 都 可 能 是 昂 贵 的 。 使 用 约 束 求 解 技 术 来 求 解 路 径 约 束 通 常 需 要 大 量 的 计 算 成 本 和 时 间 , 这 可 能 会 降 低 模 糊 的 性 能。为了克 服 这 些 挑 战 , 一 些 研 究 通 过 选 择 性 地 将 困 难 路 径 分 配 给concolic执 行 来 提 高 模 糊 性 能 

这一部分介绍了基于覆盖率的模糊测试的发展方向。一种方向是将变异模糊测试与约束求解技术相结合,以解决路径约束问题。另一种方向是利用机器学习技术发现种子测试用例中有价值的字节位置。然而,现有的模糊测试工具缺乏充分利用试验内部和试验间的历史信息来指导有效的模糊测试。因此,本文提出了一种利用历史信息指导模糊测试的方法。

三.DESIGN OF EMS

EMS框架和提出的概率字节方向模型(PBOM)的设计。PBOM旨在提高EMS的性能。


A. Why Intra- and Inter-Trial History Matters

为什么程序的内部历史(定义:当 前 模 糊 过 程 中 的 历 史 )很重要:现有的fuzzers包含了自适应策略。然而,它们主要集中在从历史内获得的高层次启发式来指导种子选择和生成过程,缺乏对所采用的突变策略的细粒度重用,从而有效地触发唯一路径或崩溃。并且程序的不同执行路径可能在路径约束中具有相同的特定值,同一程序的模糊测试历史可以指导解决已解决的路径约束。

为什么程序的外部历史 (定义;来 自 先 前 模 糊 过 程 的 历 史 , 可 以 来 自 相 同 或 不 同 的 程 序)很重要:首先,同一程序的审间模糊历史审内历史有类似的贡献。然后,它可以指导模糊解决已经解决的同一程序的路径约束,例如,具有更好的路径覆盖的初始种子集可以提高模糊性能。此外,来自不同程序的试验间模糊历史也可能有用。因为为了提高程序开发的质量和效率,许多软件平台提供了统一的开发框架和底层库,同样由于共享库的存在,在不同的程序中可能存在相同的路径约束。

B. Framework of EMS

EMS构建了内部和外部PBOM来学习和利用内部和外部测试历史。

EMS通过上图中的Inter-PBOM Initialization构建外部PBOM,通过PBOM Operator来变异测试用例,通过Operator Analysis和Data Collection来收集内部测试历史,并定期调用Intra-PBOM Update来更新内部PBOM。

C. Probabilistic Byte Orientation Model (概率字节方向模型PBOM)

这一部分描述了PBOM的数据结构和概率算法。为了防止fuzzer的执行速度下降,我们使用两个哈希映射构建了inter-PBOM和intra-PBOM。

(下图中第一排蓝色的)输入索引节点的定义:利用输入字节值的唯一哈希作为哈希映射的索引。

每一个蓝色的输入索引节点竖着看)作者为每个唯一输入索引节点构建一个链表:用于存储相应的输出变异策略T链表中每个变异节点存储了:一个唯一的变异操作符(包含输出字节值和变异类型)以及变异操作符(out,type)在该输入下的频率F和选择概率P。为了添加新的变异节点,EMS定位相应输入的索引节点,并将新的变异节点添加到该输入的链表的末尾。

为了构建inter-PBOM,EMS首先使用常规fuzzer(如AFL和MOPT)收集inter-trial历史。然后,EMS构建了如图4所示的数据结构,并更新了每个节点在输入的链表中的选择概率P。根据每个(out,type,F,P)∈T的频率F,以下公式计算了概率分布P,其中p是计算P的(out,type)的权重。


​​​​​​​

根 据 公 式 1,inter-PBOM赋 予 频 率 f较 少 的 (out, type)较 高的 选 择 概 率 P, 然 后 构 建 MO的 选 择 概 率 分 布 P,该 选 择 概率 分 布 更 频 繁 地 选 择 较 少 的 (out, type)来 覆 盖 、 删 除 或插入种子测试用例 。

Q :为什么赋 予 频 率 f较 少 的 (out, type)较 高的 选 择 概 率 P

因为:

        由 于 在 收 集 试 验 间 历 史 时 , 有 效 的 突 变 策 略 是 由 普 通fuzzers的 传 统 突 变 算 子 触 发 的 , 因 此 其 中 许 多 是 由 简 单 的算 子 生 成 的 , 例 如 翻 转 一 个 位 , 或 者 在 一 个 字 节 的 值 上 增加 1。 而 且 , 突 变 策 略 可 以 从 多 个 不 同 的 程 序 中 收 集 , 并且 可 以 长 时 间 收 集 。 综 上 所 述 , 收 集 到 的 突 变 策 略 数 量 可以 很 大 , 而 且 大 多 数 策 略 都 是 由 简 单 的 操 作 符 触 发 的 ,所以简单的突变操作符被大量使用。(即频率高)

        因 此 , (out, type)的 频 率 F越 高 , 基 于 突 变 的 fuzzers就越 容 易 在 试 验 间 历 史 中 使 用 传 统 的 突 变 算 子 从 in生 成 (out,type)。 相 反 , 低 频 (out, type)则 可 以 通 过 罕 见 的 突 变 算 子 来构 造 , 例 如 , 将 特 定 的 字 节 值 插 入 到 种 子 测 试 用 例 中 。 如果 inter-PBOM总 是 再 现 简 单 的 操 作 符 , 那 么 它 就 不 那 么 有用 了 。 因 此 , inter-PBOM将 更 多 的 选 择 概 率 P分 配 给 出 现频 率 较 低 的 (out, type)。

四.IMPLEMENTATION OF EMS

介绍了一种基于MO PT构建的测试用例生成工具EMS,它在确定性和混沌阶段中实现了PBOM算子以利用高效的变异策略。EMS使用InterPBOM初始化来构建Inter-PBOM并更新每个唯一输入的选择概率分布(利用上图中的公式1)。EMS在确定性阶段和混沌阶段中分别调用PBOM算子,以便在不同的方式中使用学习到的变异策略。EMS还记录使用的变异策略,并在触发新的唯一路径或崩溃时将其存储在训练集中以更新Intra-PBOM。

EMS的具体实现包括三个步骤:

(1)计算哈希映射的索引

(2)搜索匹配的节点并添加新节点、更新选择概率

(3)继续模糊测试。

五.EVALUATION

EMS设计中,模糊测试历史主要用于提取有效的变异策略来变异种子测试用例。同时,变异位置也可以由模糊测试历史来指导。作者利用历史信息来概率性地选择记录的位置,以产生有趣的测试用例。根据过去的模糊测试结果,可以分析变异位置对某些特定分支行为的影响,从而得出更细粒度的变异位置信息。

六.CONCLUSION

本文发现了内部和跨试验模糊历史都包含了关键变异策略的丰富知识,这些变异策略隐含着部分路径约束解决方案,可以用于加速发现具有相似部分路径约束的新路径或崩溃。基于这一洞见,提出了轻量级高效的PBOM模型,用于捕捉从内部和跨试验历史中触发独特路径和崩溃的变异策略。提出了一种新的基于历史的变异框架EMS,其中PBOM是变异操作符之一,根据输入的字节值和变异类型以概率方式提供所需的变异字节值和变异类型。在9个真实世界程序上评估EMS与AFL、QSYM、MO PT、MO PT-dict、EcoFuzz和AFL++的性能。结果表明,EMS在大多数程序上发现了更多的独特漏洞,并具有更高的行覆盖率。EMS在标准化基准FuzzBench上也实现了优越的覆盖性能,并在发现不同类型的漏洞时具有不同的初始种子集。此外,进行了进一步的分析,证明了EMS的有效性和低开销。EMS在不同的跨PBOMs上的性能表现,展示了跨同一供应商的不同程序对跨试验模糊历史的贡献。总体而言,EMS可以作为改进基于变异的模糊器的覆盖率和漏洞发现的新方向。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/259158.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Vue2学习第二天

Vue2 学习第二天 1. 数据绑定 Vue 中有 2 种数据绑定的方式: 单向绑定(v-bind):数据只能从 data 流向页面。双向绑定(v-model):数据不仅能从 data 流向页面,还可以从页面流向 data。 备注: 双向绑定一般都应用在表单…

javaweb学习day03(JS+DOM)

一、javascript入门 1 官方文档 地址: https://www.w3school.com.cn/js/index.asp离线文档: W3School 离线手册(2017.03.11 版).chm 2 基本说明 JavaScript 能改变 HTML 内容,能改变 HTML 属性,能改变 HTML 样式 (CSS),能完成 页面的数据…

基于Java SSM框架实现疫情防控系统项目【项目源码】

基于java的SSM框架实现疫情防控系统演示 Java技术 Java技术它是一个容易让人学会和使用的一门服务器语言。它在编程的过程当中只需要很少的知识就能建立起一个真正的交互站点。对于这个教程来说它并不需要你完全去了解这种语言,只要能快速融入web站点就可以&#x…

2024春日营销三大内容趋势,种草爆文轻松get丨小红书数据分析

春季是市场迎来消费焕活的新周期,也是新一年品牌实现生意高速起步的必争节点。一年之“计”在于春,春日营销,吹响品牌营销第一声号角。那么,春日营销在小红书上有何内容趋势,跟着小编的脚步一起来看看~ 内容趋势 1、亲…

34461A 数字万用表,六位半,Truevolt DMM

01 34461A 数字万用表,六位半 产品综述: 34461A 六位半万用表是替代 Keysight 34401A 数字万用表(此前为 Agilent 34401A)的新一代产品。 34461A 拥有 Truevolt 系列数字万用表的全新图形显示界面、先进的分析模式和内置数学函…

JAVA JDK1.8下载安装

1、官网下载地址Java Downloads | Oracle 2、双击运行该文件 3、 4、 5、 6、安装完成后,现在来设置 环境变量 7、新建系统变量 8、修改Path变量 9、配置完成安装完成

6.s081 学习实验记录(九)lock parallelism

文章目录 一、Memory allocator简介提示实验代码实验结果 二、Buffer cache简介提示实验代码实验结果 该实验将重构某些代码以提高并发度。 首先切换到lock分支: git fetchgit checkout lockmake clean 一、Memory allocator 简介 user/kalloctest 这个程序会对…

Unity 2D Spine 外发光实现思路

Unity 2D Spine 外发光实现思路 前言 对于3D骨骼,要做外发光可以之间通过向法线方向延申来实现。 但是对于2D骨骼,各顶点的法线没有向3D骨骼那样拥有垂直于面的特性,那我们如何做2D骨骼的外发光效果呢? 理论基础 我们要知道&a…

Spring Boot 笔记 010 创建接口_更新用户头像

1.1.1 usercontroller中添加updateAvatar,校验是否为url PatchMapping("updateAvatar")public Result updateAvatar(RequestParam URL String avatarUrl) {userService.updateAvatar(avatarUrl);return Result.success();} 1.1.2 userservice //更新头像…

2.18通过字符设备驱动分步注册过程实现LED驱动的编写,编写应用程序测试

应用程序&#xff1a; #include<stdlib.h> #include<stdio.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include<unistd.h> #include<string.h> #include<sys/ioctl.h> #include"myled.h&quo…

JVM-JVM调优基础(理论)

申明&#xff1a;文章内容是本人学习极客时间课程所写&#xff0c;作为笔记进行记录&#xff0c;文字和图片基本来源于课程资料&#xff0c;在某些地方会插入一点自己的理解&#xff0c;未用于商业用途&#xff0c;侵删。 原资料地址&#xff1a;课程资料 JVM参数 标准参数 …

蓝桥杯:C++排序

排序 排序和排列是算法题目常见的基本算法。几乎每次蓝桥杯软件类大赛都有题目会用到排序或排列。常见的排序算法如下。 第(3)种排序算法不是基于比较的&#xff0c;而是对数值按位划分&#xff0c;按照以空间换取时间的思路来排序。看起来它们的复杂度更好&#xff0c;但实际…

ADC--模拟量转换成数字量

目录 一、ADC硬件组成七大部分&#xff1a; 二、单次转换&#xff0c;连续转换&#xff0c;不连续采样模式&#xff0c;扫描模式区别 1、举例(5种组合情况) 2、模拟看门狗中断的作用&#xff1a; 三、MCU使用ADC步骤 一、ADC硬件组成七大部分&#xff1a; ①输入电压&#…

Java数字孪生智慧工地数据大屏APP项目源码

目录 智慧工地云平台核心功能 1.劳务管理 2.视频监控 3.安全教育 4.进度管理 5.环境监测 6.塔吊监控 7.升降机监控 8.工地广播 9.深基坑高支模 10.AI识别 11.安全质量 智慧工地建设的价值和意义 危大工程管理 智慧工地聚焦施工现场一线生产活动&#xff0c;利用物…

使用Python生成二维码的完整指南

无边落木萧萧下&#xff0c;不如跟着可莉一起游~ 可莉将这篇博客收录在了&#xff1a;《Python》 可莉推荐的优质博主首页&#xff1a;Kevin ’ s blog 本文将介绍如何使用Python中的qrcode库来生成二维码。通过简单的代码示例和详细解释&#xff0c;读者将学习如何在Python中轻…

数据结构-双指针法

介绍 双指针法是一种可以在O&#xff08;n&#xff09;时间复杂度内解决数组、链表、字符串等数据结构相关的问题的方法。核心思想为使用两个指针在不同位置遍历数组或链表&#xff0c;从而实现特定操作。 常见的双指针法有 1.快慢指针&#xff1a;快指针每次移动两步&…

单测的思路

文章目录 单测的分类方法的单测生成工具的对比生成步骤 接口的单测mock步骤部分依赖mock的方式 场景的单测参考 单测的分类 单元测试&#xff08;Unit Testing&#xff09;是一种软件开发中的测试方法&#xff0c;它的主要目的是确保软件中的最小可测试单元&#xff08;通常是…

(07)Hive——窗口函数详解

一、 窗口函数知识点 1.1 窗户函数的定义 窗口函数可以拆分为【窗口函数】。窗口函数官网指路&#xff1a; LanguageManual WindowingAndAnalytics - Apache Hive - Apache Software Foundationhttps://cwiki.apache.org/confluence/display/Hive/LanguageManual%20Windowing…

英文论文(sci)解读复现【NO.21】一种基于空间坐标的轻量级目标检测器无人机航空图像的自注意

此前出了目标检测算法改进专栏&#xff0c;但是对于应用于什么场景&#xff0c;需要什么改进方法对应与自己的应用场景有效果&#xff0c;并且多少改进点能发什么水平的文章&#xff0c;为解决大家的困惑&#xff0c;此系列文章旨在给大家解读发表高水平学术期刊中的 SCI论文&a…

红队笔记Day3-->隧道上线不出网机器

昨天讲了通过代理的形式&#xff08;端口转发&#xff09;实现了上线不出网的机器&#xff0c;那么今天就来讲一下如何通过隧道上线不出网机器 目录 1.网络拓扑 2.开始做隧道&#xff1f;No&#xff01;&#xff01;&#xff01; 3.icmp隧道 4.HTTP隧道 5.SSH隧道 1.什么…