Database Systems

Generating diverse database isolation level test cases with fuzzy testing

  • Xiyu LU ,
  • Wei LIU ,
  • Siyang WENG ,
  • Keqiang LI ,
  • Rong ZHANG
Expand
  • 1. School of Data Science and Engineering, East China Normal University, Shanghai 200062, China
    2. The Fifth Electronics Research Institute of the Ministry of Industry and Information Technology, Guangzhou 511300, China

Received date: 2023-06-29

  Online published: 2023-09-20

Abstract

Database management systems play a vital role in modern information systems. Isolation level testing is important for database management systems to ensure the isolation of concurrent operations and data consistency to prevent data corruption, inconsistency and security risks, and to provide reliable data access to users. Fuzzy testing is a method widely used in software and system testing. By searching the test space and generating diverse test cases, it explores the boundary conditions, anomalies and potential problems of the system to find possible vulnerabilities. This article introduces SilverBlade, a tool for fuzzy testing of database isolation levels, that aims to improve the diversity of generated test cases and explore the isolation level test space in depth-wise. To effectively search the huge test space, this study designed a structured test input that splits the test space into two subspaces of concurrent transaction combination and execution interaction modes for searching. To test the isolation-level core implementation test space more comprehensively, an adaptive search method based on depth and breadth was also designed for effective mutation test cases. The experimental results show that SilverBlade is able to generate diverse test cases and provide broader coverage of the core implementation code of the database isolation level in the popular database management system PostgreSQL. Compared to similar tools, SilverBlade performed better at improving test coverage in critical areas of the isolation level.

Cite this article

Xiyu LU , Wei LIU , Siyang WENG , Keqiang LI , Rong ZHANG . Generating diverse database isolation level test cases with fuzzy testing[J]. Journal of East China Normal University(Natural Science), 2023 , 2023(5) : 51 -64 . DOI: 10.3969/j.issn.1000-5641.2023.05.005

References

1 SILBERSCHATZ A, KORTH H F, SUDARSHAN S. Database System Concepts [M]. 6th ed. New York: McGraw-Hill Education, 2010.
2 BERENSON H, BERNSTEIN P, GRAY J, et al.. A critique of ANSI SQL isolation levels. ACM SIGMOD Record, 1995, 24 (2): 1- 10.
3 GRAY J, REUTER A. Transaction Processing: Concepts and Techniques [M]. London: Elsevier, 1992.
4 WU Y, ARULRAJ J, LIN J, et al.. An empirical evaluation of in-memory multi-version concurrency control. Proceedings of the VLDB Endowment, 2017, 10 (7): 781- 792.
5 BERNSTEIN P A, HADZILACOS V, GOODMAN N. Concurrency Control and Recovery in Database Systems [M]. Boston: Addison-Wesley, 1987.
6 李海翔. 数据库事务处理的艺术: 事务管理与并发控制 [M]. 北京: 机械工业出版社, 2017.
7 BEIZER B. Black-box Testing: Techniques for Functional Testing of Software and Systems [M]. Hoboken: Wiley, 1995.
8 ZHU H, HALL P A V, MAY J H R.. Software unit test coverage and adequacy. ACM Computing Surveys, 1997, 29 (4): 366- 427.
9 ZHU X, WEN S, CAMTEPE S, et al.. Fuzzing: A survey for roadmap. ACM Computing Surveys, 2022, 54 (11s): 230.
10 GODEFROID P.. Fuzzing: Hack, art, and science. Communications of the ACM, 2020, 63 (2): 70- 76.
11 LIANG H, PEI X, JIA X, et al.. Fuzzing: State of the art. IEEE Transactions on Reliability, 2018, 67 (3): 1199- 1218.
12 MANèS V J M, HAN H S, HAN C, et al.. The art, science, and engineering of fuzzing: A survey. IEEE Transactions on Software Engineering, 2019, 47 (11): 2312- 2331.
13 ZHANG Y, ZHANG J, ZHANG D, et al. Survey of directed fuzzy technology [C]// Proceedings of the 2018 IEEE 9th International Conference on Software Engineering and Service Science. 2018: 696-699.
14 LI J, ZHAO B, ZHANG C.. Fuzzing: A survey. Cybersecurity, 2018, (1): 6.
15 ZHONG R, CHEN Y, HU H, et al. Squirrel: Testing database management systems with language validity and coverage feedback [C]// Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. 2020: 955-970.
16 WANG M, WU Z, XU X, et al. 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. 2021: 328-337.
17 LIANG Y, LIU S, HU H. Detecting logical bugs of DBMS with coverage-based guidance [C]// Proceedings of the 31st USENIX Security Symposium. 2022: 4309-4326.
18 SLUTZ D R. Massive stochastic testing of SQL [C]// Proceedings of the 24th International Conference on Very Large Data Bases. 1998: 618-622.
19 ANDREAS S. SQLSmith [EB/OL]. (2022-03-03)[2023-05-15].https://github.com/anse1/sqlsmith.
20 RIGGER M, SU Z. Testing database engines via pivoted query synthesis [C]// Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation. 2020: 667-682.
21 PORTS D R K, GRITTNER K.. Serializable snapshot isolation in postgreSQL. Proceedings of the VLDB Endowment, 2012, 5 (12): 1850- 1861.
22 彭智勇, 彭煜玮. PostgreSQL数据库内核分析 [M]. 北京: 机械工业出版社, 2012.
23 张树杰. PostgreSQL技术内幕: 事务处理深度探索 [M]. 北京: 电子工业出版社, 2021.
24 CORDELLA L P, FOGGIA P, SANSONE C, et al.. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26 (10): 1367- 1372.
25 ULLMANN J R.. An algorithm for subgraph isomorphism. Journal of the ACM, 1976, 23 (1): 31- 42.
Outlines

/