(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111546029.6 (22)申请日 2021.12.16 (71)申请人 杭州电子科技大 学 地址 310018 浙江省杭州市下沙高教园区2 号大街 (72)发明人 曾英佩　吴铤　申延昭　郑秋华　 (74)专利代理 机构 杭州君度专利代理事务所 (特殊普通 合伙) 33240 代理人 杨舟涛 (51)Int.Cl. G06F 11/36(2006.01) G06N 5/04(2006.01) G06N 20/00(2019.01) (54)发明名称 一种模糊测试种子 变异强度优化方法 (57)摘要 本发明公开了一种模糊测试种子变异强度 优化方法。 本发明先选择一个最优的变异强度； 接着对种子执行所选择变异强度次数的变异； 最 后将变异种子后得到的内容作为输入提供给程 序做一次模糊测试； 测试完成后这些内容将废 弃， 重新在该种子基础上生成下一个输入； 这里 变异强度指的是生成新输入时对种子的叠加变 异次数。 本申请提出将多种变异强度的选择建模 为强化学习中多臂赌博机的手臂的选择， 从而利 用现有的多臂赌博机算法来选取任意时刻 的最 优的变异强度， 实现更高的模糊测试效率。 权利要求书1页 说明书4页 附图1页 CN 114185802 A 2022.03.15 CN 114185802 A 1.一种模糊测试种子变异强度优化方法， 其特 征在于， 该 方法具体如下： 步骤一， 选择一个最优的变异强度； 步骤二， 对种子执 行所选择变异强度次数的变异； 步骤三： 将变异种子后得到的内容作为输入提供给程序做一次模糊测试； 测试完成后 这些内容将 废弃， 重新在该种子基础上生成下一个输入； 所述的选择一个最优的变异强度， 具体方法为： 步骤①： 判断是否之前已经为该种子选择了最优变异强度， 并且所选择的变异强度还 有效， 如果有效则直接返回该变异强度； 步骤②： 判断是否是之前已经选择过最优变异强度且已经失效的情况， 如果是， 则需要 将这期间的收益进行计算后， 更新到多臂赌 博机对应的数据结构中； 步骤③： 如果之前尚未选择过变异强度或者已经失效， 均需要选择种子对应的多臂赌 博机并运行其多臂赌 博机算法来选择最优变异强度。 2.根据权利要求1所述的一种 模糊测试种子变异强度优化方法， 其特征在于： 所的收益 则是在生成给定数量输入或者执行给定时间的模糊测试后， 根据新发现的代码覆盖、 唯一 崩溃数目、 唯一漏洞数目进行计算； 其中的代码覆盖是边覆盖、 行覆盖或路径 覆盖。 3.根据权利要求1所述的一种 模糊测试种子变异强度优化方法， 其特征在于： 所述的变 异强度为 为2r， 1≤r≤7， 且r为整数， 且不是在这些离 散值中随机、 均匀地进行选择。 4.根据权利要求1所述的一种 模糊测试种子变异强度优化方法， 其特征在于： 所述的的 多臂赌博机是假设收益会变化、 但仍具有随机性的非静态多臂赌博机， 假设收益会变化、 且 不具有随机性的对抗式多臂赌博机， 经典的假设收益不变而仅具备随机性的多臂赌博机中 的一种。 5.根据权利要求1所述的一种 模糊测试种子变异强度优化方法， 其特征在于： 所述的将 变异种子后得到的内容作为输入提供给程序 做一次模糊测试后， 模糊测试效率的计算依据 新发现的代码覆盖、 崩溃数目、 漏洞数目进行。 6.根据权利要求4所述的一种 模糊测试种子变异强度优化方法， 其特征在于： 所述的非 静态多臂赌 博机为Discounted  UCB或者Sl iding‑Window UCB算法。 7.根据权利要求4所述的一种 模糊测试种子变异强度优化方法， 其特征在于： 所述的对 抗式多臂赌 博机可以选择Exp3系列算法。 8.根据权利要求4所述的一种 模糊测试种子变异强度优化方法， 其特征在于： 所述的经 典的假设收益 不变而仅具 备随机性的多臂赌 博机为UCB系列算法。权　利　要　求　书 1/1 页 2 CN 114185802 A 2一种模糊测试种子变异强度优化方 法 技术领域 [0001]本申请涉及软件安全领域， 尤其涉及一种对软件进行 更高效模糊测试的方法。 背景技术 [0002]模糊测试是目前流行的软件漏洞发现方法， 其可以大致分为三类： 黑盒模糊测试、 灰盒模糊测试、 和白盒模糊测试。 其中， 黑盒测试基本不对被测程序进行了解， 而是随机地 产生输入进行测试。 灰盒测试会对被测试程序进行插桩来获取一些运行时信息， 如AFL (American  Fuzzy Lop)会通过对插桩了解代码覆盖， 并通过当前输入的执行反馈调整下一 步输入。 白盒测试会获取程序 代码的更多相关信息来针对性地产生输入， 如通过符号执行、 污点追踪来指导产生输入。 这三类方法亦各有所长： 黑盒模糊测试虽然单次测试执行速度 快， 但是输入的质量一般不高； 白盒模糊测试的输入质量很好， 但是其执行速度较慢； 灰盒 模糊测试介于黑盒和白盒之间， 其输入质量较好， 也有较好的执 行速度。 [0003]这三类模糊测试方法 中， 以AFL为代表的灰盒模糊测试， 因为其在发现软件漏洞上 的极高效率， 成为了目前十 分流行的模糊测试技术， 在工业界和学术界都产生了较大影响。 本申请主要关注的即是灰盒模糊测试， 同时所提出方法也能应用在结合了灰盒和白盒模糊 测试混合(Hybrid)模糊测试系统中(如Dri ller、 QSYM)。 [0004]AFL类的灰盒模糊测试的测试过程大概如下。 它将所有种子 维护在一个队列中， 从 头到尾遍历该队列选取种子进行模糊测试。 每选取一个种子后， 将对它进行变异来获得新 输入， 并将新输入提供给被测试程序看是否会造成崩溃(Crash)。 如果找到一个崩溃则意味 着发现一个软件Bug。 如果没有崩溃但是发现了新的代码覆盖(Co de Coverage)， 如新的边 覆盖(Edge  Coverage)或称新路径(Path)， 则会将该输入保存为新种子。 因为AFL这类模糊 测试方法以代码覆盖制导， 所以也常被称为覆盖制导模糊测试(Coverage ‑guided  Fuzzing,CGF)或基于覆盖的模糊测试。 [0005]从上段介绍中可以看出， 如何对种子进行变异是很关键 的一个问题。 目前对种子 的变异包括确定性(Deterministic)阶段和非确定性(Non ‑determini stic)阶段。 确定性阶 段是可以选择跳过的， 它主要是用一系列确定的变异操作来改动种子作为新输入(如逐个 反转比特)， 过程会比较耗时。 而非确定性阶段目前分为两个子阶段， 一是大破坏(Havoc)阶 段， 一个是绞接(Splice)阶段。 其中大破坏阶段会生成多个新输入， 每个新输入都是通过对 该种子进行2r次叠加变异来生成的(r是在1至7 中随机选择的整数， 包括1和7)。 我们 称叠加 变异次数为变异强度(Mutation  Intensity)。 而绞接阶段则是先将该种子与一个随机选择 的其它种子在中间随机位置进行拼接生成一个新种子后， 再 执行大破坏阶段。 [0006]目前AFL类灰盒模糊测试系统(包括libFuzzer)中， 每次生成输入选择的变异强度 都是在一个离散强度列表中随机、 均匀地选择的(如前面提到的2r， r为1至7)， 这使得选择 的变异强度并不一定是其最优的变异强度。 实际上， (1)不同的变异强度下， 发现新路径的 效率可能并不一样， (2)不同类的种子， 其变异强度与发现新路径效率的对应关系也可能不 一样， (3)在不同时刻， 变异强度与发现新路径的效率可能不一样， 即变异强度的对应模糊说　明　书 1/4 页 3 CN 114185802 A 3