基于AFL的覆盖引导模糊测试优化技术研究（论文）

目 录
摘 要 I
Abstract III
目 录 VII
图 录 XI
表 录 XII
第一章 绪论 1
1.1 研究背景与意义 1
1.2 研究现状 2
1.3 研究内容 3
1.4 章节安排 5
第二章 覆盖引导模糊测试技术介绍及相关研究 7
2.1 覆盖引导模糊测试 7
2.2 相关研究 10
2.2.1 预处理 10
2.2.2 种子选择 11
2.2.3 确定变异 12
2.2.4 随机变异 13
2.2.5 执行追踪 14
2.2.6 反馈指导 15
2.3 存在的问题 18
2.4 本章小结 18
第三章 基于强化学习的随机变异调度策略 19
3.1 概述 19
3.2 种子自适应变异调度策略 20
3.3 位置自适应变异调度策略 21
3.3.1 自定义双层多臂老虎机 21
3.3.2 强化学习算法 23
3.4 PAMSSAFL 25
3.5 实验评估 27
3.5.1 实验设置 27
3.5.2 bug发现能力 27
3.5.3 覆盖能力 29
3.6 本章小结 31
第四章 轻量级自适应敏感区域确定变异技术 33
4.1 概述 33
4.2 研究动机 34
4.3 自适应敏感区域变异算法 35
4.3.1 形式化定义 35
4.3.2 算法流程 37
4.3.3 基于敏感区域的种子选择策略 37
4.3.4 基于敏感区域的修剪策略 37
4.4 SMAFL 38
4.5 实验评估 39
4.5.1 实验设置 39
4.5.2 实验结果 40
4.6 本章小结 45
第五章 基于位运算的覆盖信息记录方案 47
5.1 概述 47
5.2 背景知识介绍 48
5.2.1 哈希冲突 48
5.2.2 局部冲突与全局冲突 49
5.3 冲突情况剖析 50
5.4 基于位运算的覆盖信息记录方案 51
5.4.1 朴素的解决方案 51
5.4.2 位运算和再哈希法 51
5.4.3 存储过程 52
5.5 BitAFL 53
5.5.1 整体流程 53
5.5.2 实现细节 54
5.6 实验评估 55
5.6.1 实验设置 55
5.6.2 实验结果 55
5.7 本章小结 58
第六章 覆盖引导模糊测试器SmartCGF 59
6.1 系统流程 59
6.2 实验评估 60
6.2.1 实验设置 60
6.2.2 漏洞挖掘能力 61
6.2.3 覆盖能力 63
6.2.4 吞吐量 66
6.3 本章小结 67
第七章 总结与展望 69
7.1 本文工作总结 69
7.2 下一步工作展望 70
致 谢 错误!未定义书签。
参考文献 71
（1）基于强化学习的随机变异调度策略。通过一种自定义的双层多臂老虎机模型为变异位置和变异算子建立联系，并采用置信区间上界算法解决模糊测试场景中的多臂老虎机问题，达到为种子的不同变异位置选取最有效的变异算子的目的。将基于强化学习的随机变异调度策略集成到AFL上实现位置自适应的模糊测试器PAMSSAFL。
（2）轻量级自适应敏感区域确定变异技术。提出一种自适应敏感区域变异算法，该算法将变异后执行新路径的字节标记为敏感字节，并基于敏感字节延展形成敏感区域，将后续变异限制在敏感区域内，并根据执行结果实时调整敏感区域，从而减少无效变异。基于敏感区域提出新的种子选择和修剪策略。将自适应敏感区域变异算法以及新的种子选择和修剪策略集成到AFL上实现SMAFL。
（3）基于位运算的覆盖信息记录方案。系统地分类讨论了造成哈希冲突的几种情况并定量分析各种情况造成哈希冲突的概率，在定量分析的基础上将目标程序分为小型程序和大型程序并设计不同的解决方案，对小型程序采用位运算完全消除哈希冲突，对大型程序采用再哈希法大幅度减少哈希冲突。将基于位运算的覆盖信息记录方案集成到AFL上实现BitAFL。
（4）覆盖引导模糊测试器SmartCGF。将基于强化学习的随机变异调度策略、轻量级自适应敏感区域确定变异技术和基于位运算的覆盖信息记录方案进行有机融合，实现了新的覆盖引导模糊测试器SmartCGF。实验结果表明，在可接受的额外开销的前提下，SmartCGF的漏洞挖掘能力和覆盖能力提升显著。