Source-linked AI summary
Testing Database Engines via Pivoted Query Synthesis
Manuel Rigger, Zhendong Su
TL;DR
DBMS testing has largely addressed crashes rather than incorrect query results, while SQL dialect differences limit differential testing. The paper introduces Pivoted Query Synthesis, which checks whether generated queries contain a selected pivot row, and implements it in SQLancer. SQLancer found 99 bugs across SQLite, MySQL, and PostgreSQL, supporting the approach’s effectiveness and generality within its tested scope.
Problem
Logic bugs in DBMS are difficult to detect automatically, and dialect differences limit differential testing across systems.
Method
Pivoted Query Synthesis generates queries guaranteed to contain a randomly selected pivot row, implemented in SQLancer for three DBMS.
Results
99 bugs were found across SQLite, MySQL, and PostgreSQL, supporting the approach as effective and general.
Takeaways & Limitations
The approach found bugs that fuzzers were designed not to detect and can be applied across multiple DBMS.
Takeaways & Limitations
SQLancer tested less than 50% of the code in each DBMS and lacked support for many common features.
Abstract
from arXiv · showhide
Relational databases are used ubiquitously. They are managed by database management systems (DBMS), which allow inserting, modifying, and querying data using a domain-specific language called Structured Query Language (SQL). Popular DBMS have been extensively tested by fuzzers, which have been successful in finding crash bugs. However, approaches to finding logic bugs, such as when a DBMS computes an incorrect result set, have remained mostly untackled. Differential testing is an effective technique to test systems that support a common language by comparing the outputs of these systems. However, this technique is ineffective for DBMS, because each DBMS typically supports its own SQL dialect. To this end, we devised a novel and general approach that we have termed Pivoted Query Synthesis. The core idea of this approach is to automatically generate queries for which we ensure that they fetch a specific, randomly selected row, called the pivot row. If the DBMS fails to fetch the pivot row, the likely cause is a bug in the DBMS. We tested our approach on three widely-used and mature DBMS, namely SQLite, MySQL, and PostgreSQL. In total, we reported 123 bugs in these DBMS, 99 of which have been fixed or verified, demonstrating that the approach is highly effective and general. We expect that the wide applicability and simplicity of our approach will enable the improvement of robustness of many DBMS.
1. INTRODUCTION
Existing DBMS testing finds crashes but struggles with logic bugs because differential testing is limited by DBMS-specific SQL dialects. Pivoted Query Synthesis addresses this by generating queries guaranteed to contain a selected pivot row, and SQLancer found 99 bugs across three DBMS.
- Motivation: Logic bugs return incorrect query results without crashing, but existing fuzzers are effective mainly at finding crash-inducing queries.Automatic detection is difficult because it requires an effective test oracle.
- Motivation: Differential testing is limited because DBMS extensions and semantic differences reduce the common SQL core, while matching outputs can still share bugs.These limitations make cross-DBMS result comparison unreliable as a general oracle.
- Approach: Pivoted Query Synthesis generates a query guaranteed to return a randomly selected pivot row, reducing correctness checking to single-row containment.The approach was implemented in SQLancer.
- Evaluation: 99 bugs were found across SQLite, MySQL, and PostgreSQL: 65 in SQLite, 25 in MySQL, and 9 in PostgreSQL.The approach also found database-internal errors and four crashes, including a MySQL security vulnerability.
- Evaluation: The evaluation supports Pivoted Query Synthesis as a general and effective approach for detecting DBMS bugs overlooked by fuzzers.The reported bugs include logic bugs, internal errors, and crashes.
2. BACKGROUND
Relational DBMS organize data in tables and use SQL for defining, modifying, and querying it. The background emphasizes that dialect differences and DBMS-specific features complicate differential testing across popular systems.
- Relational DBMS: Relational DBMS organize data as tables of rows and columns, with domains commonly represented as data types.The relational model represents a relation as a mathematical product of domains.
- SQL: SQL is used to create tables, insert and modify rows, and retrieve data, but DBMS deviate from the standard and support different functionality.These differences make differential testing difficult.
- Tested DBMS: The tested systems were popular, complex, and long-developed DBMS: SQLite, MySQL, and PostgreSQL.SQLite is commonly used for local or embedded storage, whereas MySQL and PostgreSQL provide server-based systems with broader feature sets.
- Tested DBMS: SQLite favors compactness and flexible type handling, while MySQL and PostgreSQL provide richer features and high-level data types.SQLite permits omitted column types and implicit conversions; MySQL and PostgreSQL support features such as arrays and JSON.
- Test Oracles: Differential testing compares outputs from multiple systems, but DBMS-specific SQL behavior limits its applicability as an automatic oracle.An effective automatic test oracle is crucial for comprehensive DBMS testing.
3. Pivoted Query Synthesis
Pivoted Query Synthesis generates queries designed to contain a randomly selected pivot row, then checks whether the DBMS returns that row. SQLancer builds random database states and expressions, rectifies conditions to TRUE for the pivot row, and uses containment and error oracles to detect bugs.
- Pivoted Query Synthesis: SQLancer selects a random row as the pivot row and generates expressions guaranteed to evaluate to TRUE for it.Expressions are generated from the database schema and evaluated with an AST interpreter using the pivot row’s values.
- Query Generation: The generated expressions are placed in WHERE and JOIN clauses to construct targeted queries expected to fetch the pivot row.The queries may include randomly selected SQL keywords and can return the pivot row among other rows.
- Checking Containment: If the DBMS result omits the expected pivot row, SQLancer likely detects a logic bug through its containment oracle.Containment checking is embedded in the generated query using operators such as IN or INTERSECT.
- Expression Rectification: Expression rectification converts randomly generated conditions to TRUE for the pivot row, accounting for SQL’s TRUE, FALSE, and NULL logic.The rectification algorithm uses operations such as ISNULL or a preceding NOT, and can be adapted to other logic systems.
- Error Handling: SQLancer also uses an error oracle that treats unexpected DBMS errors, including database corruption messages, as bug indicators.Expected statement errors are ignored, while unexpected errors such as SQLite’s malformed database disk image are flagged.
- Expressions on Columns: The approach was extended to test whether expressions on columns produce expected result values, not only whether the pivot row is contained.The query may return randomly generated expressions based on column references, whose values are checked against the pivot row.
4. EVALUATION
The evaluation reported 99 true bugs across SQLite, MySQL, and PostgreSQL, including database corruptions and crashes. The cases typically required short SQL tests and exposed bugs involving constraints, indexes, optimizations, dialect features, and storage engines.
- Bug outcomes: 99 bugs were considered true after 123 reports, based on code fixes, documentation fixes, or developer confirmation.The remaining 24 reports were classified as false bugs or duplicates.
- Bug outcomes: 14 SQLite bugs were Critical, 8 Severe, and 14 Important, although severity assignments were inconsistent and unavailable for the other DBMS.The authors treat these classifications as evidence that many reported bugs were serious.
- SQL test cases: Test cases averaged 3.71 LOC, and 13 bugs were reproducible with a single line.The reported cases were reduced before submission, so these figures describe minimized test cases.
- SQL test cases: 90.0% of bug reports used one table, while CREATE TABLE, INSERT, SELECT, and CREATE INDEX statements appeared frequently.The statement distribution may be skewed because the simplest among multiple failing test cases was selected.
- SQL test cases: UNIQUE constraints appeared in 22.2% of test cases, PRIMARY KEY columns in 17.2%, explicit indexes in 28.3%, and FOREIGN KEYs in 1.0%.Explicit indexes were more common than indexes created implicitly for UNIQUE and PRIMARY KEY constraints.
- Test oracles: 17 bugs were found with the error oracle, including 4 cases of database corruption, while REINDEX exposed 6 constraint-related bugs.The error oracle also detected malformed database schemas and other internal errors.
5. DISCUSSION
The discussion examines SQLancer’s breadth, implementation trade-offs, and testing scope. The authors argue that the approach found bugs despite limited coverage and required manageable DBMS-specific effort, while remaining applicable beyond relational systems.
- Findings: 99 bugs were found across SQLite, MySQL, and PostgreSQL, although the total depended on testing focus and DBMS-specific factors.SQLite received the most attention because its developers quickly fixed bugs, and its flexible dialect exposed additional issues.
- Findings: Existing DBMS test suites are extensive, but SQLancer complements them by targeting data-centric SQL logic beyond crash-oriented testing.SQLite, for example, has hundreds of times more test code than source code and millions of test instances.
- Generality: The approach could extend to non-relational systems such as document-oriented DBMS by selecting random data within their data model.The authors specifically identify MongoDB as a possible target for adaptation.
- Implementation effort: SQLancer requires DBMS-specific components because SQL dialects differ, but avoids implementing query planners, concurrency, and extensive optimizations.The approach evaluates literal expressions and does not need to consider multiple rows, reducing implementation complexity.
- Scope: Checking one pivot row simplifies oracle construction and is mostly as effective as checking all rows, but cannot detect bugs that produce duplicate rows.The same generated SQL statements can, in principle, be applied to each row, albeit over multiple steps.
6. RELATED WORK
Prior DBMS testing approaches use differential testing, fuzzing, constraint-based generation, or performance-oriented benchmarks. Pivoted Query Synthesis addresses DBMS oracle difficulties by checking whether a specific query fetches a designated row.
- Testing of Software Systems: Pivoted Query Synthesis checks whether a DBMS correctly handles a specific query and row, offering a novel way to address the oracle problem.The approach is presented as a DBMS-testing method related to differential and metamorphic testing.
- Differential Testing of DBMS: Differential testing compares outputs from multiple systems implementing a common language, but DBMS dialect extensions and semantic deviations limit its applicability.Differences include NULL handling, character handling, and numeric type coercions.
- Database Fuzzing: Random query generators and general-purpose fuzzers have found many DBMS bugs, but they cannot detect logic bugs that produce incorrect query results.SQLsmith has found over 100 bugs in popular DBMS since 2015, yet logic bugs remain outside its detection capability.
- DBMS testing based on constraint solving: Constraint-based approaches generate database data, queries, or test oracles, but prior work reproduced known or injected bugs and discovered only one new bug.These methods use SAT-based solving to enumerate fetched rows and construct a test oracle.
- Performance Testing: Performance-testing approaches generate benchmark queries or quantify optimizer accuracy rather than directly improving DBMS correctness.One study found significant optimizer-accuracy differences across multiple commercial database systems.
7. CONCLUSION
The paper presents SQLancer as an effective DBMS bug-finding tool, despite implementing only a small subset of current DBMS features. It identifies future directions for uncovering additional bugs.
- 7. CONCLUSION: SQLancer found over 99 bugs in three popular and widely-used DBMS using a simple approach with limited feature coverage.The authors describe the approach's effectiveness as surprising and identify additional bug discovery as future work.