Computer Science

Computer Science ›› 2026, Vol. 53 ›› Issue (9): 421-431.doi: 10.11896/jsjkx.250700127

• Information Security • Previous Articles     Next Articles

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 Online:2026-09-15 Published: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)

127

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

CLC Number: 

  • 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/.
[1] WEI Qing, ZHANG Yupeng, LIU Shaoxun, ZHANG Jinfeng, ZHANG Yuezhong, CHEN Haoyang. Fuzzing Driver Generation Based on Large Language Models [J]. Computer Science, 2026, 53(6A): 250400113-8.
[2] WEI Zihan, MA Rongkuan, LI Beibei, YANG Yahui, LI Zhuo, SONG Yunkai. Firmware Recovery Based Emulation and Testing Method for Industrial Gateway [J]. Computer Science, 2025, 52(12): 411-418.
[3] LU Bo, LYU Xiao. Detection of Web Command Injection Vulnerabilities on IOS-XE Based on Static Analysis-drivenApproach [J]. Computer Science, 2025, 52(12): 419-427.
[4] YIN Jiale, CHEN Zhe. Dynamic Analysis Based Fuzz Testing for Memory Safety Vulnerabilities [J]. Computer Science, 2025, 52(11): 382-389.
[5] MA Yingzi, CHEN Zhe, YIN Jiale, MAO Ruiqi. Memory Security Vulnerability Detection Combining Fuzzy Testing and Dynamic Analysis [J]. Computer Science, 2024, 51(2): 352-358.
[6] LIN Jiahan, RAN Meng, PENG Jianshan. SSFuzz:State-sensitive Greybox Fuzzing for Network Protocol Services [J]. Computer Science, 2024, 51(12): 71-78.
[7] DING Duo, SUN Cong, ZHENG Tao. Robust Binary Program Debloating [J]. Computer Science, 2024, 51(10): 208-217.
[8] ZHUANG Yuan, CAO Wenfang, SUN Guokai, SUN Jianguo, SHEN Linshan, YOU Yang, WANG Xiaopeng, ZHANG Yunhai. Network Protocol Vulnerability Mining Method Based on the Combination of Generative AdversarialNetwork and Mutation Strategy [J]. Computer Science, 2023, 50(9): 44-51.
[9] ZHAO Mingmin, YANG Qiuhui, HONG Mei, CAI Chuang. Smart Contract Fuzzing Based on Deep Learning and Information Feedback [J]. Computer Science, 2023, 50(9): 117-122.
[10] DU Hao, WANG Yunchao, YAN Chenyu, LI Xingwei. Test Cases Generation Techniques for Root Cause Location of Fault [J]. Computer Science, 2023, 50(7): 10-17.
[11] YANG Yahui, MA Rongkuan, GENG Yangyang, WEI Qiang, JIA Yan. Black-box Fuzzing Method Based on Reverse-engineering for Proprietary Industrial Control Protocol [J]. Computer Science, 2023, 50(4): 323-332.
[12] HE Jie, CAI Ruijie, YIN Xiaokang, LU Xuanting, LIU Shengli. Detection of Web Command Injection Vulnerability for Cisco IOS-XE [J]. Computer Science, 2023, 50(4): 343-350.
[13] XU Wei, WU Zehui, WANG Zimu, LU Li. Protocol Fuzzing Based on Testcases Automated Generation [J]. Computer Science, 2023, 50(12): 58-65.
[14] HUANG Song, DU Jin-hu, WANG Xing-ya, SUN Jin-lei. Survey of Ethereum Smart Contract Fuzzing Technology Research [J]. Computer Science, 2022, 49(8): 294-305.
[15] HU Zhi-hao, PAN Zu-lie. Testcase Filtering Method Based on QRNN for Network Protocol Fuzzing [J]. Computer Science, 2022, 49(5): 318-324.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.