计算机科学

计算机科学 ›› 2026, Vol. 53 ›› Issue (9): 421-431.doi: 10.11896/jsjkx.250700127

• 信息安全 • 上一篇    下一篇

R2Fuzz:基于依赖图修复的键值型数据库管理系统的模糊测试框架

梁皓天1, 曹琰1,2   

  1. 1 郑州大学网络空间安全学院 郑州 50002
    2 嵩山实验室 郑州 450000
  • 收稿日期:2025-07-21 修回日期:2025-12-08 出版日期:2026-09-15 发布日期:2026-09-10
  • 通讯作者: 曹琰(ieycao@zzu.edu.cn)
  • 作者简介:(2558890540@qq.com)
  • 基金资助:
    嵩山实验室资助项目(232102210124,ZZK202403002-03);河南省科技攻关项目(232102210124)

R2Fuzz:Dependence Graph Repair Based Fuzzing Framework for Key-Value DBMS

LIANG Haotian1, CAO Yan1,2   

  1. 1 School of Cyberspace Security and Engineering,Zhengzhou University,Zhengzhou 450002,China
    2 Songshan Laboratory,Zhengzhou 450000,China
  • Received:2025-07-21 Revised:2025-12-08 Published:2026-09-15 Online:2026-09-10
  • About author:LIANG Haotian,born in 2001,postgraduate,is a member of CCF(No.P9807G).His main research interest is database vulnerability discovery.
    CAO Yan,born in 1983,associate professor,Ph.D supervisor,is a member of CCF(No.17447S).His main research interest is vulnerability discovery.
  • Supported by:
    Songshan Laboratory Funded Projects(232102210124,ZZK202403002-03) and Henan Province Science and Technology Research Project(232102210124).

PDF (PC)

247

摘要： 键值型数据库管理系统(Key-Value DBMS)因其高性能特性被广泛应用于云计算、物联网和分布式系统,但其数据库语言复杂性、多样性导致传统的模糊测试方法存在覆盖率低、语法语义正确率低等问题。为了实现键值型DBMS的安全测试,提出了基于依赖图修复的模糊测试方法。首先,基于状态快照的依赖感知,根据提供的初始测试用例队列的行为,从被测键值型DBMS中提取状态快照,创建测试用例的依赖图;其次,提出基于依赖图的语义修复和基于Token模型的变异策略来自动化生成测试用例集,根据DBMS的漏洞类型和覆盖率反馈,使得测试用例能够深入探索DBMS的安全边界,测试内存漏洞;最后,基于上述方法,实现了针对键值型DBMS的自动化模糊测试框架R2Fuzz。使用R2Fuzz对Redis,etcd和Memcached这3种主流键值型DBMS进行测试,实验结果验证了框架的有效性,其在语法语义正确率和覆盖率方面比其他框架效果更优。

关键词: 数据库安全测试, 键值型数据库管理系统, 依赖图, 模糊测试

Abstract: Key-Value database management system(Key-Value DBMS) is widely used in cloud computing,Internet of Things and distributed systems due to its high performance characteristics.However,the complexity and diversity of its database language lead to the low coverage and syntactic and semantic accuracy of traditional fuzzy testing methods.In order to implement the secu-rity testing of key-value DBMS,this paper proposes a fuzzing method based on dependency graph repair.Firstly,based on the dependency awareness of state snapshots,according to the behavior of the provided initial test case queue,the state snapshots are extracted from the key-value DBMS to create the dependency graph of the test case.Secondly,the semantic repair strategy based on dependency graph and the mutation strategy based on Token model are proposed to automatically generate test cases.Accor-ding to the DBMS vulnerability type and coverage feedback,the test cases could deeply explore the DBMS security boundary and test memory vulnerabilities.Finally,R2Fuzz,an automated fuzz testing framework for key-value DBMS,is implemented based on the above methods.R2Fuzz is used to test three mainstream key-value DBMSS,Redis,etcd and Memcached.Experimental results verify the effectiveness of the framework,and it is better than other frameworks in terms of syntactic and semantic accuracy and coverage.

Key words: Database security testing, Key-Value database management system, Dependence graph, Fuzzing

中图分类号: 

  • TP309
[1] PANDYA A,KULKARNI C,MALI K,et al.AnOpen SourceCloud-Based NoSQL and NewSQL Database Benchmarking Platform for IoT Data[C] //Benchmarking,Measuring,and Optimizing(Bench 2018).Cham:Springer,2019.
[2] DWIVEDI S,BALAJI R,AMPATT P,et al.A Survey on Security Threats and Mitigation Strategies for NoSQL Databases[C] //Information Systems Security(ICISS 2023).Cham:Springer,2023.
[3] MEMCACHED DOCUMENTATION.UDPDDoS[EB/OL].https://docs.memcached.org/advisories/ddos/.
[4] HUMAYUN M,JHANJHI N Z,ALSAYAT A,et al.Internet of things and ransomware:Evolution,mitigation and prevention[J].Egyptian Informatics Journal,2021,22(1):105-117.
[5] MANES V J M.The Art,Science,and Engineering of Fuzzing:A Survey[J].IEEE Transactions on Software Engineering,2021,47(11):2312-2331.
[6] FIORALDI A,MAIER D,EISSFELDT H,et al.AFL++:combining incremental steps of fuzzing research[C] //Proceedings of the 14th USENIX Conference on Offensive Technologies(WOOT’20).Berkeley:USENIX Association,2020.
[7] LLVM.libFuzzer－a library for coverage-guided fuzz testing[EB/OL].https://llvm.org/docs/LibFuzzer.html.
[8] GROSS T,SCHLEIER T,MULLER T.ReFuzz-StructureAware Fuzzing of the Resilient File System(ReFS)[C] //Procee-dings of the 2022 ACM on Asia Conference on Computer and Communications Security(ASIA CCS’22).New York:ACM,2022:589-601.
[9] WANG H P,WEI Z Y,ZHOU Q L,et al.Context-Aware Fuz-zing for RobustnessEnhancement of Deep Learning Models[J].ACM Transactions on Software Engineering and Methodology,2025,34(1):1-68.
[10] QIN S S,HU F,MA Z Y,et al.NSFuzz:Towards Efficient and State-Aware Network Service Fuzzing[J].ACM Transactions on Software Engineering and Methodology,2023,32(6):1-26.
[11] LEE W,HA J,HAN W S,et al.DoppelGanger++:Towards Fast Dependency Graph Generation for Database Replay[J].Proceedings of the ACM on Management of Data,2024,2(1):1-26.
[12] ZHONG R,CHEN Y H,HU H,et al.SQUIRREL:Testing Database Management Systems with Language Validity and Cove-rage Feedback[C] //Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security(CCS ’20).New York:ACM,2020:955-970.
[13] WANG M.Industry Practice of Coverage-Guided Enterprise-Level DBMS Fuzzing[C] //Proceedings of the 2021 IEEE/ACM 43rd International Conference on Software Engineering:Software Engineering in Practice(ICSE-SEIP).IEEE,2021:328-337.
[14] FU J Z,LIANG J,WU Z Y,et al.Griffin:Grammar-Free DBMS Fuzzing[C] //Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering(ASE’22).New York:ACM,2022:1-12.
[15] LIU S,TIAN C L,SUN J,et al.Semantic Conformance Testing of Relational DBMS[J].Proceedings of the VLDB Endowment,2024,18(3):850-862.
[16] LIANG J,WU Z Y,FU J Z,et al.WINGFUZZ:implementing continuous fuzzing for DBMSs[C] //Proceedings of the 2024 USENIX Conference on Usenix Annual Technical Conference(USENIX ATC’24).Berkeley:USENIX Association,2024:479-492.
[17] ZENG Y,ZHU F,ZHANG S,et al.DAFuzz:data-aware fuzzing of in-memory data stores[J].PeerJ Computer Science,2023,9:e1592.
[18] etcd.etcd Integrates Continuous Fuzzing[EB/OL].https://etcd.io/blog/2022/etcd-integrates-continuous-fuzzing/.
[19] YANG Y P,CHEN Y H,ZHONG R,et al.Towards generic database management system fuzzing[C] //Proceedings of the 33rd USENIX Conference on Security Symposium(SEC ’24).Berkeley:USENIX Association,2024:901-918.
[20] DUAN S H,KANNAN S,ARPACI-DUSSEAU A C,et al.PANGOLIN:a Comprehensive Testing Framework for Configuration-Rich Key-Value Stores[C] //Proceedings of the 18th ACM International Systems and Storage Conference(SYSTOR’25).New York:ACM,2025:202-215.
[21] DOURHRI A,HANINE M,OUAHMANE H.KVMod—A Novel Approach to Design Key-Value NoSQL Databases[J].Information,2023,14(5):563.
[22] LI L,WANG G,WU G,et al.A ComparativeStudy of Consistent Snapshot Algorithms for Main-Memory Database Systems[J].IEEE Transactions on Knowledge and Data Engineering,2021,33(2):316-330.
[23] TAIPALUS T.Database management system performance comparisons:A systematic literature review[J].Journal of Systems and Software,2024,208:111872.
[24] SONG J S,DOU W S,GAO Y,et al.Detecting Metadata-Related Logic Bugs in Database Systems via Raw Database Construction[J].Proceedings of the VLDB Endowment,2024,17(8):1884-1897.
[25] CUI Z Y,DOU W S,GAO Y,et al.Understanding Transaction Bugs in Database Systems[C] //Proceedings of the IEEE/ACM 46th International Conference on Software Engineering(ICSE’24).New York:ACM,2024:1-13.
[26] ZHANG L M,CHANG H Y,XU R T.Equal-Width Partitioning Roulette Wheel Selection in Genetic Algorithm[C] //Procee-dings of the 2012 Conference on Technologies and Applications of Artificial Intelligence(TAAI’12).Piscataway,NJ:IEEE Computer Society,2012:62-67.
[27] BUGDEN W,ALAHMAR A.Rust:The Programming Lan-guage for Safety and Performance[J].arXiv:2206.05503,2022.
[28] FIORALDI A,MANTOVANI A,MAIER D,et al.DissectingAmerican Fuzzy Lop:AFuzzBench Evaluation[J].ACM Tran-sactions on Software Engineering and Methodology,2023,32(2):1-26.
[29] NIST.CVE-2023-28425Detail[EB/OL].https://nvd.nist.gov/vuln/detail/CVE-2023-28425.
[30] Google.honggfuzz Security oriented software fuzzer[EB/OL].https://honggfuzz.dev/.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市两江新区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发