进化内核模糊测试研究综述

doi:10.11959/j.issn.2096-109x.2024001

Abstract

Abstract:

Fuzzing is a technique that was used to detect potential vulnerabilities and errors in software or systems by generating random, abnormal, or invalid test cases.When applying fuzzing to the kernel, more complex and challenging obstacles were encountered compared to user-space applications.The kernel, being a highly intricate software system, consists of numerous interconnected modules, subsystems, and device drivers, which presented challenges such as a massive codebase, complex interfaces, and runtime uncertainty.Traditional fuzzing methods could only generate inputs that simply satisfied interface specifications and explicit call dependencies, making it difficult to thoroughly explore the kernel.In contrast, evolutionary kernel fuzzing employed heuristic evolutionary strategies to dynamically adjust the generation and selection of test cases, guided by feedback mechanisms.This iterative process aimed to generate higher-quality test cases.Existing work on evolutionary kernel fuzzing was examined.The concept of evolutionary kernel fuzzing was explained, and its general framework was summarized.The existing work on evolutionary kernel fuzzing was classified and compared based on the type of feedback mechanism utilized.The principles of how feedback mechanisms guided evolution were analyzed from the perspectives of collecting, analyzing, and utilizing runtime information.Additionally, the development direction of evolutionary kernel fuzzing was discussed.

Key words: kernel, fuzzing, evolutionary, feedback

CLC Number:

TP393

Yan SHI, Weizhong QIANG, Deqing ZOU, Hai JIN. Survey of evolutionary kernel fuzzing[J]. Chinese Journal of Network and Information Security, 2024, 10(1): 1-21.

Figures/Tables 8

研究工作	测试用例生成	变异策略	反馈机制	反馈机制实现方式
Syzkaller	系统调用序列的生成与变异	插入、删除系统调用/系统调用参数变异	代码覆盖率反馈	KCOV
TriforceAFL	文件中读取+变异	AFL变异策略	代码覆盖率反馈	QEMU Trace
TLSF	系统调用序列变异	系统调用参数变异/系统调用序列拼接	代码覆盖率反馈	QEMU Trace
kAFL	Linux下以ext4 映像作为初始输入+变异	AFL变异策略	代码覆盖率反馈	Intel PT
HFL	系统调用序列的生成与变异+S2E符号执行	只变异系统调用的入口点	代码覆盖率反馈系统调用序列有效顺序反馈	KCOV SVF+S2E
KOOBE	Linux堆越界写PoC+变异双队列语料库，概率选择	插入、删除系统调用/系统调用参数变异	代码覆盖率反馈能力引导	KCOV S2E的QEMU插桩
StateFuzz	3层语料库，概率选择	插入、删除系统调用/系统调用参数变异	代码覆盖率反馈状态变量值域反馈极值反馈	KCOV LLVM Sancov+SVF
RAZZER	单线程：系统调用序列的生成与变异多线程：P_{s t}-＞P _mt/P _mt变异	插入、删除系统调用/系统调用参数变异	代码覆盖率反馈	KCOV
DR.Fuzz	语义通知机制	字节优先级变异	代码覆盖率反馈错误状态反馈	KCOV+Intel PT LLVM
FuzzUSB	状态机+变异规则生成	多信道/多反馈变异策略	代码覆盖率反馈状态覆盖反馈转换覆盖反馈	KCOV dg llvm slicer+KLEE
X-AFL	被动：hook系统调用并改变参数主动：模型生成	系统调用参数变异	代码覆盖率反馈序列覆盖反馈	KCOV
JANUS	文件系统映像的元数据变异系统调用序列的生成与变异	映像：元数据变异文件操作：参数变异/末端插入新系统调用	代码覆盖率反馈状态反馈	GCC wrapper 文件对象状态推断
HYDRA	文件系统映像的元数据变异系统调用序列的生成与变异	映像：元数据变异文件操作：参数变异/末端插入新系统调用	代码覆盖率反馈检查器定义的信号	GCC wrapper 检查器插件
USBFuzz	设备/配置描述符作为种子+随机数据生成	AFL变异策略	代码覆盖率反馈	KCOV
Unicorefuzz	人工设置	AFL变异策略	代码覆盖率反馈	Unicorn
VaultFuzzer	系统调用序列的生成与变异	插入、删除系统调用/系统调用参数变异	代码覆盖率反馈状态反馈PC权重定向	KCOV CLANG/LLVM
SemFuzz	提取 CVE/git 日志生成系统调用序列+变异	粗糙级别/细粒度变异	漏洞函数和补丁代码定向	修改的GCC+KCOV
GREBE	内核错误报告的PoC+变异	Syzkaller策略+系统调用分组/参数值保留	内核对象定向	GCC plugin
Conzzer	并发调用对+程序输入	邻接定向变异+断点控制方法	并发调用对覆盖率线程交错定向	CLANG/LLVM
KRACE	单个系统调用生成与变异+线程调度生成	插入、删除系统调用/系统调用参数变异/主次列表洗牌	代码覆盖率反馈别名指令对覆盖率	LLVM

References 61

[2]	REN Z Z , ZHENG H , ZHANG JY ,et al. A review of fuzzing techniques[J]. Journal of Computer Research and Development, 2021,58(5): 944-963.
[3]	GODEFROID P , LEVIN M Y , MOLNAR D A . Automated whitebox fuzz testing[C]// Proceedings of NDSS. 2008: 151-166.
[4]	LIANG H , PEI X , JIA X ,et al. Fuzzing:state of the art[J]. IEEE Transactions on Reliability, 2018,67(3): 1199-1218.
[5]	FUZZING I W . SAGE:whitebox fuzzing for security testing[J]. SAGE, 2012,10(1).
[6]	PHAM V T , B?HME M , SANTOSA A E ,et al. Smart greybox fuzzing[J]. IEEE Transactions on Software Engineering, 2019,47(9): 1980-1997.
[7]	B?HME M , PHAM V T , NGUYEN M D ,et al. Directed greybox fuzzing[C]// Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 2329-2344.
[8]	李贺, 张超, 杨鑫 ,等. 操作系统内核模糊测试技术综述[J]. 小型微型计算机系统, 2019,40(9): 6.
	LI H , ZHANG C , YANG X ,et al. Survey of OS Kernel fuzzing[J]. Journal of Chinese Computer Systems. 2019,40(9): 6.
[9]	PRAKASH A , VENKATARAMANI E , YIN H ,et al. Manipulating semantic values in kernel data structures:attack assessments and implications[C]// Proceedings of 2013 43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 2013: 1-12.
[10]	HAO Y , ZHANG H , LI G ,et al. Demystifying the dependency challenge in kernel fuzzing[C]// Proceedings of the 44th International Conference on Software Engineering. 2022: 659-671.
[11]	HAN H S , CHA S K . IMF:inferred model-based fuzzer[C]// Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 2345-2358.
[12]	PAILOOR S , ADAY A , JANA S . MoonShine:optimizing OS fuzzer seed selection with trace distillation[C]// Proceedings of 27th USENIX Security Symposium (USENIX Security 18). 2018: 729-743.
[13]	LI Y , JI S , LYU C ,et al. V-fuzz:vulnerability-oriented evolutionary fuzzing[J]. arXiv preprint arXiv:1901.01142, 2019.
[14]	CORINA J , MACHIRY A , SALLS C ,et al. Difuze:Interface aware fuzzing for kernel drivers[C]// Proceedings of 24th ACM SIGSAC Conference on Computer and Communications Security(CCS 2017). 2017: 2123-2138.
[15]	WANG Y , JIA X , LIU Y ,et al. Not all coverage measurements are equal:fuzzing by coverage accounting for input prioritization[C]// Proceedings of NDSS. 2020.
[16]	FIORALDI A , MAIER D , EI?FELDT H , et al . AFL++:combining incremental steps of fuzzing research[C]// Proceedings of 14th USENIX Workshop on Offensive Technologies (WOOT 20). 2020.
[17]	PRAMANIK A , TAYADE A . Study and comparison of general purpose fuzzers[R]. University of Wisconsin-Madison, 2017.
[18]	HINDS N , LARSON P , FRANKE H ,et al. Using code coverage tools in the Linux kernel[C]// ACM SIGSOFT Software Engineering Notes (ACM’04). 2014: 70-81.
[19]	DEL FRATE F , GARG P , MATHUR A P ,et al. On the correlation between code coverage and software reliability[C]// Proceedings of Sixth International Symposium on Software Reliability Engineering(ISSRE'95). 1995: 124-132.
[20]	BRIAND L , PFAHL D . Using simulation for assessing the real impact of test coverage on defect coverage[C]// Proceedings 10th International Symposium on Software Reliability Engineering. 1999: 148-157.
[21]	CAI X , LYU M R . The effect of code coverage on fault detection under different testing profiles[C]// Proceedings of the 1st International Workshop on Advances in Model-based Testing. 2005: 1-7.
[22]	LI J , ZHAO B , ZHANG C . Fuzzing:a survey[J]. Cybersecurity, 2018,1(1): 1-13.
[23]	SHU G , HSU Y , LEE D . Detecting communication protocol security flaws by formal fuzz testing and machine learning[C]// Proceedings of 28th IFIP WG 6.1 International Conference Tokyo on Formal Techniques for Networked and Distributed Systems–FORTE 2008. 2008: 299-304.
[24]	KIM K , JEONG D R , KIM C H ,et al. HFL:hybrid fuzzing on the linux kernel[C]// Proceedings of NDSS. 2020.
[25]	XU W , MOON H , KASHYAP S ,et al. Fuzzing file systems via two-dimensional input space exploration[C]// Proceedings of 2019 IEEE Symposium on Security and Privacy (SP). 2019: 818-834.
[26]	KIM K , KIM T , WARRAICH E ,et al. FuzzUSB:hybrid stateful fuzzing of usb gadget stacks[C]// Proceedings of 2022 IEEE Symposium on Security and Privacy (SP). 2022: 2212-2229.
[27]	ZHAO B , LI Z , QIN S ,et al. StateFuzz:system call-based state-aware Linux driver fuzzing[C]// Proceedings of 31st USENIX Security Symposium (USENIX Security 22). 2022: 3273-3289.
[28]	XU M , KASHYAP S , ZHAO H ,et al. KRACE:data race fuzzing for kernel file systems[C]// Proceedings of 2020 IEEE Symposium on Security and Privacy (SP). 2020: 1643-1660.
[29]	JIANG Z M , BAI J J , LU K ,et al. Context-sensitive and directional concurrency fuzzing for data-race detection[C]// Proceedings of Network and Distributed Systems Security (NDSS) Symposium. 2022.
[30]	TAN Z , LU H . A systemic review of kernel fuzzing[C]// Proceedings of the 2020 International Conference on Cyberspace Innovation of Advanced Technologies. 2020: 283-289.
[31]	OEHLERT P . Violating assumptions with fuzzing[J]. IEEE Security＆ Privacy, 2005,3(2): 58-62.
[32]	ZHANG K , XIAO X , ZHU X ,et al. Path transitions tell more:optimizing fuzzing schedules via runtime program states[C]// Proceedings of the 44th International Conference on Software Engineering. 2022: 1658-1668.
[33]	SUN H , SHEN Y , WANG C ,et al. Healer:relation learning guided kernel fuzzing[C]// Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles. 2021: 344-358.
[34]	杨鑫, 张超, 李贺 ,等. 基于系统调用依赖的 Linux 内核模糊测试技术研究[J]. 网络安全技术与应用, 2019(11): 13-16.
	YANG X , ZHANG C , LI H ,et al. Research on Linux kernel fuzzing technology based on system call dependency[J]. Network Security Technology ＆ Application, 2019(11): 13-16.
[35]	WANG D , ZHANG Z , ZHANG H ,et al. SyzVegas:beating kernel fuzzing odds with reinforcement learning[C]// Proceedings of 30th USENIX Security Symposium (USENIX Security 21). 2021: 2741-2758.
[36]	NOSSUM V , CASASNOVAS Q . Filesystem fuzzing with american fuzzy lop[C]// Proceedings of Vault Linux Storage and File Systems Conference. 2016.
[37]	CHEN W , ZOU X , LI G ,et al. KOOBE:towards facilitating exploit generation of kernel out-of-bounds write vulnerabilities[C]// Proceedings of 29th USENIX Security Symposium (USENIX Security 20). 2020: 1093-1110.
[38]	JEONG D R , KIM K , SHIVAKUMAR B ,et al. Razzer:finding kernel race bugs through fuzzing[C]// Proceedings of 2019 IEEE Symposium on Security and Privacy (SP). 2019: 754-768.
[39]	ZHAO W , LU K , WU Q ,et al. Semantic-informed driver fuzzing without both the hardware devices and the emulators[C]// Proceedings of Network and Distributed Systems Security (NDSS) Symposium. 2022.
[40]	CHIPOUNOV V , KUZNETSOV V , CANDEA G . S2E:a platform for in-vivo multi-path analysis of software systems[J]. ACM Sigplan Notices, 2011,46(3): 265-278.
[41]	KIM K , KIM T , WARRAICH E ,et al. Fuzzusb:hybrid stateful fuzzing of usb gadget stacks[C]// Proceedings of 2022 IEEE Symposium on Security and Privacy (SP). 2022: 2212-2229.
[42]	WU W , CHEN Y , XU J ,et al. FUZE:towards facilitating exploit generation for kernel use-after-free vulnerabilities[C]// Proceedings of 27th USENIX Security Symposium. 2018: 781-797.
[43]	LIANG H , CHEN Y , XIE Z ,et al. X-afl:a kernel fuzzer combining passive and active fuzzing[C]// Proceedings of the 13th European workshop on Systems Security. 2020: 13-18.
[44]	KIM S , XU M , KASHYAP S ,et al. Finding semantic bugs in file systems with an extensible fuzzing framework[C]// Proceedings of the 27th ACM Symposium on Operating Systems Principles. 2019: 147-161.
[45]	PENG H , PAYER M . USBFuzz:a framework for fuzzing USB drivers by device emulation[C]// Proceedings of 29th USENIX Security Symposium (USENIX Security 20). 2020: 2559-2575.
[46]	MAIER D , RADTKE B , HARREN B . Unicorefuzz:on the viability of emulation for kernel space fuzzing[C]// Proceedings of 13th USENIX Workshop on Offensive Technologies (WOOT 19). 2019.
[47]	SONG D , HETZELT F , KIM J ,et al. Agamotto:accelerating kernel driver fuzzing with lightweight virtual machine checkpoints[C]// Proceedings of 29th USENIX Security Symposium. 2020: 2541-2557.
[48]	CHO M , JIN H , AN D ,et al. Evaluating code coverage for kernel fuzzers via function call graph[J]. IEEE Access, 2021,9: 157267-157277.
[49]	KIM S , JEONG S , CHO M ,et al. Poster:evaluating code coverage for system call fuzzers[C]// Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019: 2689-2691.
[50]	DING R , KIM Y , SANG F ,et al. Hardware support to improve fuzzing performance and precision[C]// Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021: 2214-2228.
[51]	MACHIRY A , SPENSKY C , CORINA J ,et al. DR.CHECKER:a soundy analysis for linux kernel drivers[C]// 26th USENIX Security Symposium (USENIX Security 17). 2017: 1007-1024.
[52]	ASCHERMANN C , SCHUMILO S , ABBASI A ,et al. Ijon:exploring deep state spaces via fuzzing[C]// 2020 IEEE Symposium on Security and Privacy (SP). 2020: 1597-1612.
[53]	PHAM V T , B?HME M , ROYCHOUDHURY A . AFLNet:a greybox fuzzer for network protocols[C]// Proceedings of 2020 IEEE 13th International Conference on Software Testing,Validation and Verification (ICST). 2020: 460-465.
[54]	FIORALDI A . Program state abstraction for feedback-driven fuzz testing using likely invariants[J]. arXiv preprint arXiv:2012.11182, 2020.
[1]	SCHUMILO S , ASCHERMANN C , GAWLIK R ,et al. kAFL:hardware-assisted feedback fuzzing for OS kernels[C]// 26th USENIX Security Symposium (USENIX Security 17). 2017: 167-182.
[2]	任泽众, 郑晗, 张嘉元 ,等. 模糊测试技术综述[J]. 计算机研究与发展, 2021,58(5): 944-963.
[55]	NATELLA R . Stateafl:greybox fuzzing for stateful network servers[J]. Empirical Software Engineering, 2022,27(7): 191.
[56]	CHEN H , XUE Y , LI Y ,et al. Hawkeye:towards a desired directed grey-box fuzzer[C]// Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018: 2095-2108.
[57]	YE J , LI R , ZHANG B . RDFuzz:accelerating directed fuzzing with intertwined schedule and optimized mutation[J]. Mathematical Problems in Engineering, 2020,2020: 1-12.
[58]	HUANG H , GUO Y , SHI Q ,et al. Beacon:directed grey-box fuzzing with provable path pruning[C]// Proceedings of 2022 IEEE Symposium on Security and Privacy (SP). 2022: 36-50.
[59]	杨克, 贺也平, 马恒太 ,等. 有效覆盖引导的定向灰盒模糊测试[J]. 软件学报, 2021,33(11): 3967-3982.
	YANG K , HE Y P , MA H T ,et al. Guiding irectedd grey-box fuzzing by target-oriented valid coverage[J]. Journal of Software, 2022,33(11): 3967-3982.
[60]	YOU W , ZONG P , CHEN K ,et al. SemFuzz:semantics-based automatic generation of proof-of-concept exploits[C]// Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 2139-2154.
[61]	LIN Z , CHEN Y , WU Y ,et al. GREBE:Unveiling exploitation potential for Linux kernel bugs[C]// 2022 IEEE Symposium on Security and Privacy (SP). 2022: 2078-2095.

Metrics

Recommended 0

No Suggested Reading articles found!

基本工作	研究工作	研究内容	新发现的漏洞数
	Syzkaller	代码覆盖率引导的结构感知的进化内核模糊测试	—
	HFL	结合符号执行技术的混合模糊测试	24
	KOOBE	Linux堆越界写漏洞的自动化利用	—
Syzkaller	StateFuzz	Linux驱动程序的多维度反馈模糊测试	18
	RAZZER	动静态分析结合的数据竞争漏洞挖掘	16
	DR.Fuzz	基于语义通知机制的驱动程序测试	46
	FuzzUSB	USB gadget栈的模糊测试	34
	FUZE	Linux内核中UAF漏洞可利用性的评估	—
	TriforceAFL	基于QEMU的全系统仿真的内核模糊测试	—
	kAFL	Intel硬件辅助的与OS无关的模糊测试框架	8
	X-AFL	主动模糊测试和被动模糊测试结合	—
AFL^[23]	JANUS	二维输入空间的文件系统模糊测试	62
	HYDRA	可扩展的文件系统模糊测试框架	91
	USBFuzz	USB驱动程序的模糊测试框架	26
	Unicorefuzz	基于CPU模拟的内核模糊测试	—
Both	Agamotto	基于动态虚拟机检查点原语实现模糊测试的性能优化	—

研究工作	状态表示	状态转换的原因
JANUS	文件对象	文件操作执行
FUZZUSB	I/O操作	I/O操作执行
DR.Fuzz	函数返回值	驱动程序初始化出现错误
StateFuzz	状态变量	驱动程序运行
VaultFuzzer	触发bug的状态	子系统运行

研究工作	定向目标	距离指标
SemFuzz	漏洞函数和补丁代码	函数距离和基本块距离
GREBE	内核对象	关键变量相关覆盖率
CONZZER	线程交错	—
VaultFuzzer	目标函数	PC值的权重

研究工作	特殊反馈机制	目标问题
HFL	系统调用序列的有效顺序	生成符合预期语义的系统调用序列
KOOBE	能力引导	探索OOB能力
HYDRA	检查器信号	挖掘不同类型的文件系统错误
KRACE	别名指令对覆盖	探索并发维度
CONZZER	并发指令对覆盖	上下文敏感地探索并发维度

Survey of evolutionary kernel fuzzing

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 61

Related Articles 8

Metrics

Recommended 0

[1]	Shuting LIU, Yinghua MA, Xiuzhen CHEN. Evolutionary game model of information management mechanism for public opinion governance [J]. Chinese Journal of Network and Information Security, 2023, 9(6): 102-115.
[2]	Tian XIAO, Zhihao JIANG, Peng TANG, Zheng HUANG, Jie GUO, Weidong QIU. High-performance directional fuzzing scheme based on deep reinforcement learning [J]. Chinese Journal of Network and Information Security, 2023, 9(2): 132-142.
[3]	Xian ZHANG, Jianming ZHU, Zhiyuan SUI, Shengzhi MING. Analysis on anonymity and regulation of digital currency transactions based on game theory [J]. Chinese Journal of Network and Information Security, 2022, 8(5): 150-157.
[4]	Yingying LYU,Yunfei GUO,Zhenpeng WANG,Guozhen CHENG,Yawen WANG. Negative feedback scheduling algorithm based on historical information in SDN [J]. Chinese Journal of Network and Information Security, 2018, 4(6): 45-51.
[5]	Peng-fei LI. Construction of diffusion layers based on cipher structures [J]. Chinese Journal of Network and Information Security, 2017, 3(6): 65-76.
[6]	San DU,Hui SHU,Fei KANG. Design and implementation of hardware-based dynamic instruction set randomization framework [J]. Chinese Journal of Network and Information Security, 2017, 3(11): 29-39.
[7]	Ming-sheng WANG,Zai-liang TANG. Linear transformation shift register sequences [J]. Chinese Journal of Network and Information Security, 2016, 2(5): 11-15.
[8]	Xin SUN,Yi-yang YAO,Xin-dai LU,Xue-jiao LIU,Yong-han WU. Research and implementation of fuzzing testing based on HTTP proxy [J]. Chinese Journal of Network and Information Security, 2016, 2(2): 75-86.