Survey of evolutionary kernel fuzzing

Yan SHI; Weizhong QIANG; Deqing ZOU; Hai JIN

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

您当前的位置：

首页 >

文章列表页 >

Survey of evolutionary kernel fuzzing

Comprehensive Review | 更新时间：2024-06-03

- Survey of evolutionary kernel fuzzing
- Chinese Journal of Network and Information Security Vol. 10, Issue 1, Pages: 1-21(2024)
- 作者机构：
  
  1. 大数据技术与系统国家地方联合工程研究中心服务计算技术与系统教育部重点实验室，湖北武汉 430074
  2. 分布式系统安全湖北省重点实验室，湖北武汉 430074
  3. 华中科技大学网络空间安全学院，湖北武汉 430074
  4. 华中科技大学计算机科学与技术学院，湖北武汉 430074
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2024001
  CLC： TP393
- Online First：2024-02，
  
  Published：25 February 2024
- 稿件说明：
移动端阅览
Yan SHI, Weizhong QIANG, Deqing ZOU, et al. Survey of evolutionary kernel fuzzing[J]. Chinese Journal of Network and Information Security, 2024, 10(1): 1-21.
DOI：

Yan SHI, Weizhong QIANG, Deqing ZOU, et al. Survey of evolutionary kernel fuzzing[J]. Chinese Journal of Network and Information Security, 2024, 10(1): 1-21. DOI： 10.11959/j.issn.2096-109x.2024001.

摘要

模糊测试是一种通过生成随机、异常或无效的测试样例来检测软件或系统中潜在漏洞和错误的技术方法。内核作为一种高度复杂的软件系统，由众多互相关联的模块、子系统和驱动程序所构成，相比用户态应用程序，将模糊测试应用于内核面临着代码庞大、接口复杂、运行时不确定等具有挑战性的问题。传统的模糊测试方法生成的输入只能简单地满足接口规范和显式调用依赖，难以深入探索内核。进化内核模糊测试借助于启发式的进化策略，在反馈机制的引导下动态地调整测试样例的生成和选择，从而迭代式地生成质量更高的测试用例。对现有的进化内核模糊测试工作开展研究，阐述了进化内核模糊测试的概念并总结了进化内核模糊测试的通用框架，根据反馈机制类型对进化内核模糊测试工作进行分类和对比，从反馈机制在运行时信息的收集、分析和利用等方面剖析反馈机制引导进化的原理，对进化内核模糊测试的发展方向进行展望。

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.

关键词

Keywords

references

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 .

任泽众 , 郑晗 , 张嘉元 , 等 . 模糊测试技术综述 [J ] . 计算机研究与发展 , 2021 , 58 ( 5 ): 944 - 963 .

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 .

GODEFROID P , LEVIN M Y , MOLNAR D A . Automated whitebox fuzz testing [C ] // Proceedings of NDSS . 2008 : 151 - 166 .

LIANG H , PEI X , JIA X , et al . Fuzzing:state of the art [J ] . IEEE Transactions on Reliability , 2018 , 67 ( 3 ): 1199 - 1218 .

FUZZING I W . SAGE:whitebox fuzzing for security testing [J ] . SAGE , 2012 , 10 ( 1 ).

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 .

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 .

李贺 , 张超 , 杨鑫 , 等 . 操作系统内核模糊测试技术综述 [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 .

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 .

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 .

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 .

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 .

LI Y , JI S , LYU C , et al . V-fuzz:vulnerability-oriented evolutionary fuzzing [J ] . arXiv preprint arXiv:1901.01142 , 2019 .

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 .

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 .

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 .

PRAMANIK A , TAYADE A . Study and comparison of general purpose fuzzers [R ] . University of Wisconsin-Madison , 2017 .

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 .

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 .

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 .

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 .

LI J , ZHAO B , ZHANG C . Fuzzing:a survey [J ] . Cybersecurity , 2018 , 1 ( 1 ): 1 - 13 .

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 .

KIM K , JEONG D R , KIM C H , et al . HFL:hybrid fuzzing on the linux kernel [C ] // Proceedings of NDSS . 2020 .

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 .

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 .

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 .

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 .

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 .

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 .

OEHLERT P . Violating assumptions with fuzzing [J ] . IEEE Security＆ Privacy , 2005 , 3 ( 2 ): 58 - 62 .

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 .

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 .

杨鑫 , 张超 , 李贺 , 等 . 基于系统调用依赖的 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 .

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 .

NOSSUM V , CASASNOVAS Q . Filesystem fuzzing with american fuzzy lop [C ] // Proceedings of Vault Linux Storage and File Systems Conference . 2016 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

FIORALDI A . Program state abstraction for feedback-driven fuzz testing using likely invariants [J ] . arXiv preprint arXiv:2012.11182 , 2020 .

NATELLA R . Stateafl:greybox fuzzing for stateful network servers [J ] . Empirical Software Engineering , 2022 , 27 ( 7 ): 191 .

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 .

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 .

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 .

杨克 , 贺也平 , 马恒太 , 等 . 有效覆盖引导的定向灰盒模糊测试 [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 .

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 .

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 .

Views

330

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Self-adaptive fuzzing optimization method based on distribution divergence

Design and implementation of hardware-based dynamic instruction set randomization framework

Research and implementation of fuzzing testing based on HTTP proxy

Related Author

XU Hang

JI Jiangan

MA Zheyu

ZHANG Chao

San DU

Hui SHU

Fei KANG

Xin SUN

Related Institution

Key Laboratory of Cyberspace Security, Ministry of Education

Institute for Network Sciences and Cyberspace, Tsinghua University

⁰