A Comprehensive Survey on Database Management System Fuzzing: Techniques, Taxonomy and Experimental Comparison
Read the paper · arXiv:2311.06728
What this paper does with SQLancer
SQLancer's oracles are a fixed point of the survey's taxonomy. NoREC, TLP and PQS are introduced together as the new fuzzing methods Rigger and Su proposed, and distinguished by kind: NoREC and TLP apply metamorphic testing to the database domain so that a single DBMS can be fuzzed against itself, while PQS is a constraint-solving method whose oracle needs only that the result contain the solved row. They recur throughout as reference points -- in the comparison of test case generators, in the discussion of random database instances, and in the account of why bounding statement complexity matters. Intramorphic testing is cited separately as replacing a component to test between two versions of a system.
A survey of DBMS fuzzing that builds a taxonomy of the field -- generator type, generation strategy, feedback, and how the database instance is obtained -- and runs an experimental comparison of the tools within it. It covers logic, crash and performance bugs, and traces the line from RAGS in 1998 to the coverage-guided and oracle-based tools that followed.
How it was classified
uses infrastructure — no
A survey describes tools rather than building on them; nothing here reports reusing SQLancer's code, generator or workload.
extends technique — no
No technique is proposed or extended; the oracles are classified within the taxonomy.
compares with — yes
M8 is the survey's own comparison of test case generators, tabulating generator type, strategy, feedback and database instance across the tools including SQLancer's. This is a comparison the survey conducts rather than one it reports from elsewhere.
Non-optimizing Reference Engine Construction (NoREC)Ternary Logic Partitioning (TLP)Pivoted Query Synthesis (PQS)
Comparison of Test Case Generators Fuzzer YearGenerator TypeGenerator StrategyFeedbackDatabase Instance RAGS[89] 1998 Generation-based AST Model (Static Configuration) No Feedback (Black-Box)Existing Databases SQLsmith[5] 2015 APOLLO[51] 2019 AST Model (Dynamic Configuration) AMOEBA[62] 2022 Go-Randgen[81] 2019 AST Model (Static Configuration) Random DatabasesSQLancer[86] 2020 Artemis[71] 2021 DT2[31] 2022 DQE[90] 2023 Troc[32] 2023 TQS[94] 2023AST Model (Dynamic Configuration) ADUSA[16] 2010 Alloy Model GARan[19] 2007 Mutation-based SQL Structure MutationFeedback from internal status (Grey-Box)Existing Databases Squirrel[109] 2020 Random DatabasesSquill[101] 2023 SQLRight[60] 2022 DynSQL[49] 2023 Eqsql[107] 2021 No Feedback (Black-Box) MutaSQL[28] 2020 LEGO[59] 2023SQL Sequence MutationFeedback from internal status (Grey-Box) Griffin[33] 2022No Feedback (Black-Box) QPG[18] 2023DBMS State MutationFeedback from external interface (Black-Box) 3.
describes as state of the art — no
The oracles are described by mechanism and placed in a taxonomy; the survey makes no claim that they are the state of the art.
SQLancer publications it cites (5)
Bibliography entries that resolved to a SQLancer publication, or to a paper by one of the project's authors. A sentence citing one of these numbers is a reference to SQLancer even when it never writes the name.
| # | Entry | Matched as |
|---|---|---|
| 18 | Jinsheng Ba and Manuel Rigger. 2023. Testing Database Engines via Query Plan Guidance. In International Conference on Software Engineering. ACM, 2060–2071. | sqlancer publication · QPG |
| 84 | Manuel Rigger and Zhendong Su. 2020. Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction. In Joint Meeting on European Software Engineering Conference and Symposium on the ... | sqlancer publication · NOREC |
| 85 | Manuel Rigger and Zhendong Su. 2020. Finding Bugs in Database Systems via Query Partitioning. Programming Languages 4, OOPSLA (2020), 1–30. | sqlancer publication · TLP |
| 86 | Manuel Rigger and Zhendong Su. 2020. Testing Database Engines via Pivoted Query Synthesis. In USENIX Symposium on Operating Systems Design and Implementation. USENIX Association, 667–682. | sqlancer publication · PQS |
| 87 | Manuel Rigger and Zhendong Su. 2022. Intramorphic Testing: A New Approach to the Test Oracle Problem. In International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software. ACM, 128–136. | project authored |
Every place it refers to SQLancer (56)
56 sentences, each stored verbatim from the extracted text with where it was found and how. “Citation marker” means the sentence names no tool at all and was reached through a reference number that resolved to a SQLancer publication.
| Id | Sentence | Found by | Where |
|---|---|---|---|
| M1 | proposed several new fuzzing methods, including NoREC [ 84], TLP [ 85] and PQS [ 86]. |
technique |
1 INTRODUCTION page 2 |
| M2 | NoREC and TLP apply metamorphic testing to the database domain, enabling fuzzing on a single DBMS. |
technique |
1 INTRODUCTION page 2 |
| M3 | PQS is a constraint-solving testing method, and its oracle only requires that the execution result contain one row of the solving outcome, thereby accelerating the solving process Manuscript submitted to ACM A Comprehensive Survey on Database Management System Fuzzing: Techniques, Taxonomy and Experimental Compariso... |
technique |
1 INTRODUCTION page 2 |
| M4 | Performance bugs manifest themselves as significant differences in the execution time of the same query in different versions of DBMS, or large performance gaps between a query and its equivalent [ 34,35,38,41,86]. |
citation marker |
2.2 Basic Definitions page 4 |
| M5 | For example, intramorphic testing [ 87] works by replacing a specific component in the system to get another version and then testing between the two versions to detect bugs in that component. |
citation marker project authored |
2.2 Basic Definitions page 5 |
| M6 | On the other hand, fuzzers based on random databases [ 16,31– 33,62,71,81,85,86,90,94,101,109] create random database instances from scratch. |
citation marker |
3.1 Test Case Generator page 7 |
| M7 | A common practice is to first create tables, indexes and views randomly and then populate them with data using INSERT, UPDATE, and DELETE statements [ 84]. |
citation marker |
3.1 Test Case Generator page 7 |
| M8 | Comparison of Test Case Generators Fuzzer YearGenerator TypeGenerator StrategyFeedbackDatabase Instance RAGS[89] 1998 Generation-based AST Model (Static Configuration) No Feedback (Black-Box)Existing Databases SQLsmith[5] 2015 APOLLO[51] 2019 AST Model (Dynamic Configuration) AMOEBA[62] 2022 Go-Randgen[81] 2019 AST ... |
technique |
3.1 Test Case Generator page 8 |
| M9 | Without this limitation, numerous complex SQL statements would be generated, which may expand the search space but reduce the overall efficiency of bug detection [31, 32, 84–86, 90]. |
citation marker |
3.1 Test Case Generator page 9 |
| M10 | Mutation-based generators can be divided into three major categories: SQL structure mutation [ 19,28,49,60,101, 107,109], SQL sequence mutation [ 33,59], and DBMS state mutation [ 18]. | citation marker | 3.1 Test Case Generator page 12 |
| M11 | Comparison of Oracles Fuzzer Oracle Type Feature Test Scope Squirrel[109] Crash Database Crashes Crash BugsSquill[101] Griffin[33] LEGO[59] DynSQL[49] RAGS[89] DifferentialDifferent Databases Logic BugsSQLsmith[5] Go-Randgen[81] GARan[19] DT2[31] APOLLO[51] Different Versions of A Same DatabasePerformance BugsAMOEBA... | technique | 3.1 Test Case Generator page 13 |
| M12 | To avoid the drawbacks of the differential oracle, many fuzzing methods [ 28,60,62,84,85, 90,107] use the metamorphic oracle to detect logic bugs or performance bugs. | citation marker | 3.2 Oracle-based Comparator page 14 |
| M13 | Expression Rewriting refers to the process of rewriting logical or arithmetic expressions, such as adding predicates that always hold true to the WHERE clause or changing the string comparison operator from ‘=’ to ‘LIKE’, which will not affect the result of the expression [ 28,62,84,107]. | citation marker | 3.2 Oracle-based Comparator page 14 |
| M14 | •Query Partition: Query partition refers to dividing an original SQL query into multiple partitions, and the merged results of the partitioned queries should be consistent with the results of the original query [ 85]. | citation marker | 3.2 Oracle-based Comparator page 15 |
| M15 | Constraint-solving fuzzing methods [ 16,71,86,94] generally relies on forward or backward solving to derive the ground truth of the execution results. | citation marker | 3.2 Oracle-based Comparator page 15 |
| M16 | Comparison of Fuzzer Execution Feedbacks Fuzzer Metamorphic Validation Coverage Query Plan Syntax & Semantics Error APOLLO[51] ✗ ✓ ✗ ✗ ✗ Squirrel[109] ✗ ✗ ✓ ✗ ✗ LEGO[59] ✗ ✗ ✓ ✗ ✗ SQLRight[60] ✗ ✗ ✓ ✗ ✗ QPG[18] ✗ ✗ ✗ ✓ ✗ AMOEBA[62] ✓ ✓ ✗ ✗ ✗ GARan[19] ✗ ✗ ✓ ✗ ✗ DynSQL[49] ✗ ✗ ✓ ✗ ✓ Squill[101] ✗ ✓ ✓ ✗ ✓ In this proc... | technique | 3.2 Oracle-based Comparator page 16 |
| M17 | •Backward Solving: Backward solving entails initially selecting some tuples as ground truth at random and then using an SAT solver to work backward and obtain a statement whose execution results include these tuples [ 86]. | citation marker | 3.2 Oracle-based Comparator page 16 |
| M18 | Query plan feedback [ 18] uses the emergence of new query plans to guide subsequent query generation. | citation marker | 3.3 Execution Feedback page 17 |
| M19 | Reducing expressions [ 19,28,86,89] and deleting clauses refer to the process of reducing queries by simplifying WHERE clauses, arithmetic expressions, or logical expressions. | citation marker | 3.4 Query Reducer page 17 |
| M20 | Comparison of Fuzzer Query Reducers Fuzzer Reduce Expression Delete Clause Delete Subquery Delete IR Node Semantics Preservation RAGS[89] ✓ ✓ ✗ ✗ ✗ SQLancer[86] ✓ ✓ ✗ ✗ ✗ MutaSQL[28] ✓ ✓ ✗ ✗ ✗ GARan[19] ✓ ✓ ✗ ✗ ✗ SQLRight[60] ✗ ✗ ✗ ✓ ✓ APOLLO[51] ✓ ✓ ✓ ✗ ✓ DynSQL[49] ✓ ✓ ✓ ✗ ✓ cannot guarantee semantic correctness a... | name | 3.4 Query Reducer page 18 |
| M21 | PQS [ 86] begins by randomly generating a pivot row as the ground truth and then constructs an SQL query that includes this pivot row in its result. | technique | 4.1 Overall Fuzzing page 19 |
| M22 | Figure 11 illustrates the entire PQS pipeline. | technique | 4.1 Overall Fuzzing page 19 |
| M23 | The main challenge of PQS is how to generate an SQL query whose execution result contains a known pivot row. | technique | 4.1 Overall Fuzzing page 19 |
| M24 | The solution to PQS is to first create predicates randomly and then use the AST interpreter to evaluate whether the pivot row satisfies the predicate conditions. | technique | 4.1 Overall Fuzzing page 19 |
| M25 | By employing the above method, PQS ensures that any random predicate can produce a satisfactory SQL query after being queried. | technique | 4.1 Overall Fuzzing page 19 |
| M26 | Pipeline of PQS. | technique | 4.1 Overall Fuzzing page 19 |
| M27 | The core idea of TLP [ 85] is that the result of the predicate evaluation always falls within the values of True, False and NULL. | technique | 4.1 Overall Fuzzing page 19 |
| M28 | Figure 12 illustrates the main process of TLP. | technique | 4.1 Overall Fuzzing page 19 |
| M29 | Using a generator similar to PQS, the original query is split into three equivalent partitioned queries, and metamorphic oracles are employed for result verification to detect logic bugs. | technique | 4.1 Overall Fuzzing page 19 |
| M30 | Neither PQS nor TLP adopts feedback but performs a random search throughout the state space. | technique | 4.1 Overall Fuzzing page 19 |
| M31 | QPG [ 18] mutates the state of the database to generate more unique query plans, as shown in Figure 13. | technique | 4.1 Overall Fuzzing page 19 |
| M32 | QPG implements a generation-based generator based on PQS, TLP, and NoREC. | technique | 4.1 Overall Fuzzing page 19 |
| M33 | QPG also utilizes TLP and NoREC to validate query execution results. | technique | 4.1 Overall Fuzzing page 19 |
| M34 | Pipeline of TLP. | technique | 4.1 Overall Fuzzing page 20 |
| M35 | Since different query plans represent different execution paths, QPG can enhance the code coverage of DBMS. | technique | 4.1 Overall Fuzzing page 20 |
| M36 | Pipeline of QPG. | technique | 4.1 Overall Fuzzing page 20 |
| M37 | The NoREC pipeline [ 84] is illustrated in Figure 17. | technique | 4.3 Optimizer Testing page 22 |
| M38 | NoREC uses an AST model-based generator to generate queries with WHERE clauses and obtains the unoptimized query by moving the conditions from the WHERE clause to the Manuscript submitted to ACM A Comprehensive Survey on Database Management System Fuzzing: Techniques, Taxonomy and Experimental Comparison 23 Figure 17. | technique | 4.3 Optimizer Testing page 22 |
| M39 | Pipeline of NoREC. | technique | 4.3 Optimizer Testing page 23 |
| M40 | Source Code of Related Fuzzers Fuzzer Supported DBMS Link SQLancer[86] (PQS[86], NoREC[84], TLP[85], QPG[18])SQLite, MySQL, TiDB MariaDB, CockroachDB, OceanBasehttps://github. | name | 5.3 Evaluation Metrics page 25 |
| M41 | com/sqlancer/sqlancer DQE[90]SQLite, MySQL, MariaDB TiDB, CockroachDBhttps://github. | name | 5.3 Evaluation Metrics page 25 |
| M42 | For logic bug detection, we conducted comparative experiments on five fuzzers, including PQS, NoREC, TLP, QPG, and DQE. | technique | 5.4 Logic Bugs Detection Comparison page 25 |
| M43 | Among them, TLP and QPG only differ in feedback, and the other modules are consistent. | technique | 5.4 Logic Bugs Detection Comparison page 25 |
| M44 | Comparision of oracles for detecting logic bugs As can be seen from Figure 19 (a), (b) and (c), in SQLite, PQS exhibits the lowest semantic validity and valid cases per second, but it demonstrated the highest bug detection efficiency, finding 276 bugs in only 240 minutes. | technique | 5.4 Logic Bugs Detection Comparison page 26 |
| M45 | While NoREC stands out by using a strategy that transforms one statement into another, as opposed to the other methods that require transforming one statement into multiple ones [ 90]. | technique | 5.4 Logic Bugs Detection Comparison page 26 |
| M46 | Consequently, NoRec executes more valid cases per second, resulting in slightly faster bug detection efficiency as well. | technique | 5.4 Logic Bugs Detection Comparison page 26 |
| M47 | Since NoREC does not support MySQL, we only compared the other tools. | technique | 5.4 Logic Bugs Detection Comparison page 26 |
| M48 | It can be observed that TLP and QPG are quite exceptional, as they quickly detected bugs in MySQL. | technique | 5.4 Logic Bugs Detection Comparison page 26 |
| M49 | It is worth noting that PQS does not perform as well on MySQL as it does on SQLite. | technique | 5.4 Logic Bugs Detection Comparison page 26 |
| M50 | Secondly, the architecture of PQS speeds up the validation of each test case, but it is not a full comparison, only checking one of its query results. | technique | 5.4 Logic Bugs Detection Comparison page 27 |
| M51 | We conducted comparative experiments in SQLite using TLP, QPG, and SQLRight. | technique | 5.4 Logic Bugs Detection Comparison page 27 |
| M52 | They all use the same oracle, but TLP does not have feedback, QPG uses query plan feedback, and SQLRight utilizes coverage feedback. | technique | 5.4 Logic Bugs Detection Comparison page 27 |
| M53 | Among them, TLP and QPG employ the same generation-based generator. | technique | 5.4 Logic Bugs Detection Comparison page 27 |
| M54 | As can be seen in Figure 20, QPG detected bugs more efficiently than TLP within 240 minutes, and the number of bugs gradually equalized in the later period. | technique | 5.4 Logic Bugs Detection Comparison page 27 |
| M55 | •White-box Component Fuzzing: Recent research [ 87] has introduced white-box fuzzing in software testing. | citation marker project authored | 6.2 Component-oriented Fuzzing page 29 |
| M56 | Existing work [ 18] uses query plan feedback to maximize exploration of the query space, which is not achievable at the code level alone. | citation marker | 6.4 Improved Space Exploration Capabilities page 30 |