Parser Knows Best: Testing DBMS with Coverage-Guided Grammar-Rule Traversal
Read the paper · arXiv:2503.03893
What this paper does with SQLancer
SQLancer, including its QPG configuration, is the generation-based tool ParserFuzz argues against: because SQLancer restricts itself to queries matching its oracles' patterns, the paper says it lacks the diversity needed to reach memory corruption bugs, which is the gap grammar-rule traversal fills.
ParserFuzz generates SQL by extracting grammar rules directly from a DBMS's own built-in syntax definition files. The motivation is that existing tools exercise only a small subset of the syntax elements in DBMS-specific dialects, leaving many features untested. Without any input corpus, ParserFuzz saturates the grammar features of the system under test and uses code coverage as feedback to guide mutation and combine features from different rules. It found 81 previously unknown bugs across five popular DBMSs, all confirmed and 34 fixed.
How it was classified
uses infrastructure — no
SQLancer is described as a tool of a different kind; nothing shown says ParserFuzz builds on it.
extends technique — no
Grammar-rule traversal is presented as an alternative to oracle-pattern generation, not an extension of it.
compares with — uncertain
The paper's abstract claims to outperform existing tools, but the mentions read describe SQLancer's design rather than reporting a head-to-head result.
describes as state of the art — uncertain
A pattern fired on M12, which was outside the mentions read; those read call SQLancer+QPG a representative generation-based tool.
What could not be determined
- Whether a head-to-head comparison against SQLancer is reported: the evaluation mentions were not among those read.
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 |
|---|---|---|
| 2 | Jinsheng Ba and Manuel Rigger. Testing database engines via query plan guidance. In Proceedings of International Conference on Software Engineering (ICSE), 2023. | sqlancer publication · QPG |
| 24 | Manuel Rigger. SQLancer. https://github.com/sqlancer/sqla ncer. (visited in October 2023). | sqlancer publication |
| 32 | Manuel Rigger and Zhendong Su. Detecting Optimization Bugs in Database Engines via Non-optimizing Reference Engine Construction. In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference... | sqlancer publication · NOREC |
| 33 | Manuel Rigger and Zhendong Su. Finding Bugs in Database Systems via Query Partitioning. Proceedings of the ACM on Programming Languages, 4(OOPSLA):1–30, 2020. | sqlancer publication · TLP |
| 34 | Manuel Rigger and Zhendong Su. Testing Database Engines via Pivoted Query Synthesis. In Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI), Virtual, 2020. | sqlancer publication · PQS |
Every place it refers to SQLancer (21)
21 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 | Recent efforts on DBMS testing [2, 14, 47, 67] can be classified into two categories: generation-based testing and mutation-based grey-box fuzzing. |
citation marker |
1 Introduction page 1 |
| M2 | Another representative generation-based tool is SQLancer +QPG,where QPGrepresents query plan guidance [2]. |
name |
1 Introduction page 1 |
| M3 | SQLancer +QPG adopts DBMS query plan information as the feedback to guide the query generation process, and is designed to detect logic errors from the DBMS code. |
name |
1 Introduction page 1 |
| M4 | Similar to SQLsmith, SQLancer +QPGalso generates query sequences based on predefined SQL templates. |
name |
1 Introduction page 1 |
| M5 | There is another generation-based DBMS testing tool called SQLancer [24], that focuses on detecting DBMS logic errors from DBMS systems [32 –34]. |
citation marker |
2.2 Generation-based DBMS Testing Tools page 3 |
| M6 | Unlike tools that detect memory errors, SQLancer doesn’t generate arbitrary types of random queries for fuzzing. |
name |
2.2 Generation-based DBMS Testing Tools page 3 |
| M7 | In essence, SQLancer prefers to generate multiple syntactically different, but functionally equivalence queries, and verify their results to ensure the query execution correctness. |
name |
2.2 Generation-based DBMS Testing Tools page 3 |
| M8 | SQLancer introduces a few SQL oracles for this purpose such as NoREC ,TLPandPQS, where each shares a distinct SQL pattern to match [32 –34]. |
name |
2.2 Generation-based DBMS Testing Tools page 3 |
| M9 | With its latest configuration SQLancer +QPG[2], it uses the DBMS query plan to guide its query generation in order to stress test the DBMS query optimization logic. |
name |
2.2 Generation-based DBMS Testing Tools page 3 |
| M10 | However, because SQLancer and SQLancer +QPGrestricted themselves to generate queries that align with the oracles’ patterns, they lack the query diversity needed to explore all the grammar features provided by the DBMSs. |
name |
2.2 Generation-based DBMS Testing Tools page 3 |
| M11 | Therefore, neither SQLancer nor SQLancer +QPGare suitable to detect DBMS memory corruption bugs that are arise from interesting but rarely tested syntax features. |
name |
2.2 Generation-based DBMS Testing Tools page 3 |
| M12 | In addition, to understand the memory error detecting capability for DBMS logic bug detectors, we compareParserFuzz to state-of-the-art logic bug testing tool SQLancer +QPG. | name | 3.3 Query Mutation with Coverage Feedback page 8 |
| M13 | SQLancer +QPG supports testing with SQLite, CockroachDB andTiDB, and outperforms all other logic bug detectors including SQLRight [2, 21]. | name | 3.3 Query Mutation with Coverage Feedback page 8 |
| M14 | We use NoREC oracle for SQLancer +QPGwhen testing with SQLite andCockroachDB. | technique | 3.3 Query Mutation with Coverage Feedback page 8 |
| M15 | BecauseNoREC oracle is claimed to be a better performer overall compared to TLPoracle [2]. | citation marker | 3.3 Query Mutation with Coverage Feedback page 8 |
| M16 | But we fallback to use TLP when testing TiDB, because SQLancer +QPGhasn’t supported testingTiDB withNoREC oracle yet. | name | 3.3 Query Mutation with Coverage Feedback page 8 |
| M17 | Although SQLancer +QPGcan detect multiple logic bugs in TiDB in Figure 2i, it detects less memory errors thanParserFuzz in all SQLite ,CockroachDB andTiDB testings. | name | 5.2 Comparison with Existing Tools page 9 |
| M18 | All baselines tools except SQLancer +QPGdo not detect any issues in SQLite evaluation as shown in Figure 2q, where ParserFuzz detects 2 bugs within the set time frame. | name | 5.2 Comparison with Existing Tools page 9 |
| M19 | 52 ParserFuzz ParserFuzz−cov Squirrel AFL++ SQLSmith SQLancer+QPG 0 10 20 30 40 501. | name | 5.2 Comparison with Existing Tools page 11 |
| M20 | For example, SQLancer +QPG,SQLsmith GandSQLsmith all achieve high query validity in their own tests, with SQLsmith Cbeing an exception. | name | 5.2 Comparison with Existing Tools page 11 |
| M21 | SQLancer +QPGcan detect 11 out of 50. | name | 5.4 Contribution of Diverse Syntax Features page 12 |