DIRT: Database-Integrated Random Testing
Read the paper · doi:10.1145/3810991.3811632 · arXiv:2604.16373
What this paper does with SQLancer
DIRT takes SQLancer as both its point of departure and its baseline: three of its five oracles are reimplementations of SQLancer's, expressed as generation actions, and it explicitly declines to modify SQLancer itself, arguing that integrating a new DBMS into it is too laborious for a system under active development. It is careful to say that outperforming SQLancer on Turso does not mean it has better generators or oracles.
DIRT argues that testing tools built for mature databases fit early-stage systems badly, and integrates the testing framework into the DBMS itself so that random testing evolves with the system and false positives are reduced by construction. It introduces generation actions, an abstraction that lets database developers rather than testing experts state correctness properties, and defines five oracles as sequences of them. Evaluated on Turso, an actively developed SQLite-compatible engine, it found 23 unique confirmed bugs.
How it was classified
uses infrastructure — no
The opposite of reuse is the paper's argument: M17 says that rather than expecting developers to modify SQLancer, DIRT offers its own framework, and M14 and M15 give integrating a DBMS into SQLancer as the cost being avoided. The oracles are reimplemented, not imported.
extends technique — yes
Three SQLancer oracles, PQS and TLP among them, are re-expressed as sequences of generation actions, and the paper then uses that abstraction to state properties SQLancer cannot express. Generalising the oracles into a new form is part of what the paper contributes, not a baseline it runs.
Pivoted Query Synthesis (PQS)Ternary Logic Partitioning (TLP)
1 Definitions of Oracles in DIRT In this subsection, we go over definitions of five different oracles written as sequences of generation actions, three of which are reimplementations of existing oracles in SQLancer.
We start by defining the first of the three SQLancer oracles we implemented, Pivoted Query Synthesis (PQS) [ 23], as a universally quantified proposition in Fig.
2b presents the GA for WHERE Extended case of Ternary Logic Partitioning (TLP) [ 21] oracle from SQLancer.
We can express other properties that are not present in SQLancer, including those fundamental to key-value stores such asDeleted rows should not be in the tablepresented in Fig.
compares with — yes
DIRT is evaluated against off-the-shelf SQLancer variants on Turso and reports a better true positive rate and more useful reports, while noting the comparison does not show its generators or oracles are better.
We evaluate DIRTon Turso, an actively developed SQLite-compatible OLTP engine, and show that it finds 23 unique, confirmed bugs–significantly outperforming off-the-shelf SQLancer variants in terms of true positive rate and usefulness of bug reports.
This does not mean that DIRThas better generators or oracles than SQLancer.
We compare the performance of DIRT for Turso against SQLancer with minimal modifications, which begets some questions worth discussing.
describes as state of the art — yes
M4 singles SQLancer out among prior work for its specialised oracles and says it has proven extremely successful at finding bugs.
Within prior work, SQLancer is distinguished by using specialized test oracles that reveal logic bugs in DBMSs, and it has proven extremely successful at finding bugs in mature databases.
Where this differs from the pattern checks
The regular expressions that scan for these relationships are advisory. Where the reading above contradicts one, the reason is recorded.
Every place it refers to SQLancer (63)
63 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 | Traditional testing tools like SQLancer and SQLSmith are highly effective for mature databases, but they struggle with high false positive rates and low actionability when applied to evolving systems. |
name |
page 1 |
| M2 | We evaluate DIRTon Turso, an actively developed SQLite-compatible OLTP engine, and show that it finds 23 unique, confirmed bugs–significantly outperforming off-the-shelf SQLancer variants in terms of true positive rate and usefulness of bug reports. |
name |
page 1 |
| M3 | To discover bugs, DBMSs have historically used random testing, with approaches ranging from binary fuzzing with AFL [ 6] to structured query generation in SQLSmith [ 24], and to the powerful test oracles of SQLancer [ 22]. |
name |
1 Introduction page 1 |
| M4 | Within prior work, SQLancer is distinguished by using specialized test oracles that reveal logic bugs in DBMSs, and it has proven extremely successful at finding bugs in mature databases. |
name |
1 Introduction page 1 |
| M5 | 5% with only one new bug, and running SQLancerTurso, an existing independently developed SQLancer integration for Turso, without modifications led to a false positive rate of 58% with six newly discovered bugs. |
name |
1 Introduction page 1 |
| M6 | 2 Background and Related Work We begin by providing background: first on coverage-guided fuzzing and property-based testing at a high level, and then focusing on SQLancer, the prominent framework for testing databases. |
name |
1 Introduction page 1 |
| M7 | Such approaches have been tried recently with great success [ 14,18], and in the context of database testing, both SQLancer and DIRTfollow such a hybrid viewpoint. |
name |
2.1 Fuzzing and Property-Based Testing page 2 |
| M8 | 2 SQLancer SQLancer is a multi-year research project by Rigger et. |
name |
2.2 SQLancer page 2 |
| M9 | Within the last five years, SQLancer has not only grown with respect to the breadth of databases it supports, but it has also widened its arsenal of oracles. |
name |
2.2 SQLancer page 2 |
| M10 | It started with Pivoted Query Synthesis (PQS) [ 23], a rather "simple" containment property over databases that has found at least 121 unique logic bugs in production databases. | technique | 2.2 SQLancer page 2 |
| M11 | Two metamorphic oracles followed: Non-Optimizing Reference Engine Construction (NoREC) [ 20], which found 51 optimization bugs, and Ternary Logic Partitioning (TLP) [21], which discovered 77 novel logic bugs. | technique | 2.2 SQLancer page 2 |
| M12 | SQLancer currently supports Query Plan Guidance (QPG) [ 1] for feedback-guided generation, Cardinality Estimation Restriction Testing (CERT) [ 2] for finding performance bugs in DBMSs, Differential Query Plans (DQP) [ 3] for detecting bugs in join optimizations, and Constant Optimization Driven Database System Testi... |
name |
2.2 SQLancer page 2 |
| M13 | As SQLancer focuses on testing large classes of behaviors across a variety of databases, each oracle amounts to a significant research contribution in a new research paper. |
name |
2.2 SQLancer page 2 |
| M14 | Integrating a new DBMS to SQLancer is a time-consuming process. |
name |
2.2 SQLancer page 2 |
| M15 | At a minimum, SQLancer integration requires implementing AST connectors, generation APIs for the relevant queries, and the oracles to use for detecting bugs. |
name |
2.2 SQLancer page 2 |
| M16 | SQLancer also has a notion ofexpected errors, bugs that the users can deem as expected, so SQLancer does not report them as errors and continues testing. |
name |
2.2 SQLancer page 2 |
| M17 | 3 Specifying Correctness Oracles Rather than expecting database developers to modify SQLancer to suit their particular needs, we instead wanted to offer them flexible and extensible abstractions so that they test their database throughout its development. |
name |
2.2 SQLancer page 2 |
| M18 | assert(r in RS) Figure 1: Pivoted Query Synthesis as a universally quantified property (left) and as a generation action (right). | technique | 3 Specifying Correctness Oracles page 3 |
| M19 | 1 Definitions of Oracles in DIRT In this subsection, we go over definitions of five different oracles written as sequences of generation actions, three of which are reimplementations of existing oracles in SQLancer. |
name |
3.1 Definitions of Oracles in DIRT page 3 |
| M20 | We start by defining the first of the three SQLancer oracles we implemented, Pivoted Query Synthesis (PQS) [ 23], as a universally quantified proposition in Fig. |
name |
3.1 Definitions of Oracles in DIRT page 3 |
| M21 | PQS states that given a set of tables in the database, SELECT ing for a row constructed from the contents of those tables should contain the row. | technique | 3.1 Definitions of Oracles in DIRT page 3 |
| M22 | 1 shows two formulations of PQS side by side, the propositional formulation with universally quantified variables that define what PQS is on the left and a GA formulation of PQS with two tables/columns as generation actions that definehow PQS is tested on the right, modeling the implementation of PQS that tests Turs... | technique | 3.1 Definitions of Oracles in DIRT page 3 |
| M23 | 2, we provide definitions of SQLancer oracles as GAs in addition to the other oracles we implemented for DIRT. |
name |
3.1 Definitions of Oracles in DIRT page 3 |
| M24 | 2a demonstrates how to write Non-Optimizing Reference Engine Construction Generation (NoREC) [ 20] as a GA. | technique | 3.1 Definitions of Oracles in DIRT page 3 |
| M25 | 2b presents the GA for WHERE Extended case of Ternary Logic Partitioning (TLP) [ 21] oracle from SQLancer. |
name |
3.1 Definitions of Oracles in DIRT page 3 |
| M26 | We can express other properties that are not present in SQLancer, including those fundamental to key-value stores such asDeleted rows should not be in the tablepresented in Fig. |
name |
3.1 Definitions of Oracles in DIRT page 3 |
| M27 | count(1)) (a) Non-Optimizing Reference Engine Construction (NoREC)gen property db: t←pick db. | technique | 3.2 Query Generation page 4 |
| M28 | count(1)) (b) Ternary Logic Partitioning (TLP) WHERE Extended gen property db: t←pick db. | technique | 3.2 Query Generation page 4 |
| M29 | SQLancer does not keep a separate state [ 23], but instead uses the database APIs for querying the current state, such as the table names in sqlite_master, due to the implementation effort for the shadow model. | name | 3.2 Query Generation page 4 |
| M30 | The bug was discovered as a result of our the PQS implementation in Turso augmented with validity preserving queries between the INSERT and SELECT statements. | technique | 4.1 RQ1: DoesDIRTfind bugs in Turso? page 4 |
| M31 | This resulted in triggering a crash failure in the core B-tree data structure that could result in data DIRT: Database-Integrated Random Testing Conference’17, July 2017, Washington, DC, USA Bug Id Description Oracle Module 466 TRUE not accepted as catch-all predicate No Error Query Compiler 548 Infinite loop when c... | technique | 4.1 RQ1: DoesDIRTfind bugs in Turso? page 4 |
| M32 | 2 RQ2: How does DIRTcompare to SQLancer? | name | 4.2 RQ2: How does DIRTcompare to SQLancer? page 5 |
| M33 | We answer RQ2 by comparing the rate of true positives and false positives reports from three different random testing configurations:DIRT, the default SQLite3 integration of SQLancer with pragmas disabled (denoted SQLancer-SQLite), and the fork of a work-in-progress Turso integration of SQLancer by a Turso contribut... | name | 4.2 RQ2: How does DIRTcompare to SQLancer? page 5 |
| M34 | Pragmas had to be removed for SQLancer-SQLite because most of them were unimplemented in Turso, causing all reported bugs to be false positives in our testing. | name | 4.2 RQ2: How does DIRTcompare to SQLancer? page 5 |
| M35 | The bugs span over 20 Turso commits, 6 of which do not provide Java bindings necessary for connecting with SQLancer. | name | 4.2 RQ2: How does DIRTcompare to SQLancer? page 5 |
| M36 | SQLancer-SQLite achieves a true positive rate below 10% across all 14 commits. | name | 4.2 RQ2: How does DIRTcompare to SQLancer? page 5 |
| M37 | SQLancer-Turso performs better, with a 42% true positive rate, but still yields many more false positives than DIRT(58% vs. | name | 4.2 RQ2: How does DIRTcompare to SQLancer? page 5 |
| M38 | DIRTalso finds substantially more actionable bugs: 25 unique bugs, compared with six found by the two SQLancer configurations combined (§A. | name | 4.2 RQ2: How does DIRTcompare to SQLancer? page 5 |
| M39 | This does not mean that DIRThas better generators or oracles than SQLancer. |
name |
4.2 RQ2: How does DIRTcompare to SQLancer? page 5 |
| M40 | We compare the performance of DIRT for Turso against SQLancer with minimal modifications, which begets some questions worth discussing. |
name |
5 Discussion page 5 |
| M41 | Why not integrate SQLancer to the development process instead of developing a random testing framework from scratch? | name | 5 Discussion page 5 |
| M42 | As we briefly discussed earlier, SQLancer is not designed for the constant evolution of the random testing infrastructure along with the project. | name | 5 Discussion page 5 |
| M43 | It is a project with its own trajectory, development, new algorithms, Conference’17, July 2017, Washington, DC, USA Alperen Keles, Ethan Chou, Harrison Goldstein, and Leonidas Lampropoulos Commit 0%10%20%30%40%50%60%70%80%90%100%% of Tests09b341c6a62313c30e45324273ae3e489606b967731e675b868ac0994262b0971e2d8dLimbo SQ... | name | 5 Discussion page 5 |
| M44 | There are additional practical barriers; Java bindings for Turso are not complete at the moment, so we had to fix bugs in the SQLancer-Turso integration implemented by one of the Turso developers that relied on incomplete features that silently failed, panics in Turso caused SQLancer to terminate, so it was not poss... | name | 5 Discussion page 6 |
| M45 | Given that SQLancer supports expected errors for reducing false positives, could we use expected errors for known bugs and false positives we found to discover more bugs? | name | 5 Discussion page 6 |
| M46 | In terms of any static evaluation target, tweaking SQLancer by progressively finding more bugs as found ones are marked as expected, it is always possible to make SQLancer find more bugs. | name | 5 Discussion page 6 |
| M47 | The point, however, is that constant modification is not the expected and supported mode of operation when using SQLancer. | name | 5 Discussion page 6 |
| M48 | We have shown that a project with a much smaller scope can adopt the ideas of input generation and oracles in SQLancer as well as other related work on database testing such as Apollo [ 13] or Thanos [ 8] and demonstrated that database developers can turn their domain expertise into writing properties as presented i... | name | 5 Discussion page 6 |
| M49 | Such assertions do not replace SQLancer oracles or Turso properties because they do not have the ability to follow values through execution in a holistic way as properties do, so they can only reason about local invariants. | name | 5 Discussion page 6 |
| M50 | The SQLancer-Turso integration was almost entirely developed by one contributor, which we have used in our evaluations with small changes to their code. | name | 5 Discussion page 6 |
| M51 | Although we compared DIRTmainly against SQLancer as the basis of our oracles, other systems such as SQLRight [ 17], Griffin [ 7], and SQLancer++ [ 27] also adapt testing to DBMS behavior. |
name |
5 Discussion page 6 |
| M52 | By tightly integrating the testing infrastructure with the DBMS itself,DIRT avoids many of the limitations that off-the-shelf testing frameworks DIRT: Database-Integrated Random Testing Conference’17, July 2017, Washington, DC, USA like SQLancer face when applied to rapidly evolving systems with incomplete feature s... | name | 6 Conclusion and Future Work page 6 |
| M53 | In the same setting, SQLancer-based baselines produced substantially more false positives and fewer actionable reports. | name | 6 Conclusion and Future Work page 7 |
| M54 | 1 Bugs Found by SQLancer •(UPDATE t SET (c0, c0)=(0, 0) ): This expression results in a "Column specified more than once" error that has not been fixed at the time of our submission. | name | 6 Conclusion and Future Work page 7 |
| M55 | •(SELECT (0x0) ): There was a parsing error for hexadecimals that resulted in an "invalid float literal" error that has since been fixed before our experiments with SQLancer. | name | 6 Conclusion and Future Work page 7 |
| M56 | SQLancer discovered the bug when the initial table thad a NOT NULL clause for the column c0, which promptly failed after executing the statement. | name | 6 Conclusion and Future Work page 7 |
| M57 | Testing database engines via query plan guidance. | technique | 6 Conclusion and Future Work page 7 |
| M58 | Cert: Finding performance issues in database systems through the lens of cardinality estimation. | technique | 6 Conclusion and Future Work page 7 |
| M59 | Detecting optimization bugs in database engines via non-optimizing reference engine construction. | technique | 6 Conclusion and Future Work page 7 |
| M60 | Finding bugs in database systems via query partitioning. | technique | 6 Conclusion and Future Work page 7 |
| M61 | Testing database engines via pivoted query synthesis. | technique | 6 Conclusion and Future Work page 7 |
| M62 | Testing database engines via pivoted query synthesis. | technique | 6 Conclusion and Future Work page 7 |
| M63 | Constant optimization driven database system testing. | technique | 6 Conclusion and Future Work page 8 |