Griffin : Grammar-Free DBMS Fuzzing
Read the paper · doi:10.1145/3551349.3560431
What this paper does with SQLancer
SQLancer is Griffin's baseline and its motivating example of the cost it avoids: the paper counts the lines of code SQLancer needs to support each DBMS -- over 8,000 for PostgreSQL -- as the adaptation burden a grammar-free approach removes, and reports finding 27 more bugs than SQLancer in 12 hours.
Griffin fuzzes DBMSs without depending on a grammar. Grammars make fuzzing efficient because DBMSs validate inputs strictly, but they differ so much between systems that adapting a fuzzer to each is laborious, leaving many systems untested. Griffin instead summarises the DBMS's state into a metadata graph: it tracks the metadata of statements in built-in test cases as they execute, builds a graph of dependencies between metadata and statements, then reshuffles statements and applies metadata-guided substitution to fix semantic errors. It found 55 previously unknown bugs, 13 with CVEs.
How it was classified
uses infrastructure — no
SQLancer appears as a baseline and as the example of per-DBMS adaptation cost.
extends technique — no
The metadata graph is Griffin's own; no SQLancer technique is generalised.
compares with — yes
SQLancer is one of three fuzzers chosen for comparison, with branch coverage and 27 more bugs in 12 hours reported against it.
11% more branches, and finds 27, 27, and 22 more bugs in 12 hours than SQLancer, SQLsmith, and Sqirrel, respectively.
11% more branches, and finds 27, 27, and 22 more bugs in 12 hours than SQLancer, SQLsmith, and Sqirrel, respectively.
To evaluate the effectiveness of Griffin, we choose SQLsmith, SQLancer, and Sqirrel, which are widely used in industry and academia, for performance comparison.
describes as state of the art — no
M9 calls the baselines widely used in industry and academia rather than the state of the art.
SQLancer publications it cites (1)
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 |
|---|---|---|
| 32 | Manuel Rigger and Zhendong Su. 2020. Testing database engines via pivoted query synthesis. In 14th USENIX Symposium on Operating Systems Design and Implementation OSDI 20). 667–682. | sqlancer publication · PQS |
Every place it refers to SQLancer (23)
23 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 | 11% more branches, and finds 27, 27, and 22 more bugs in 12 hours than SQLancer, SQLsmith, and Sqirrel, respectively. |
name |
page 1 |
| M2 | l Many popular works are generationbased [ 32,33]. |
citation marker |
page 1 |
| M3 | For example, SQLancer [ 32] extracts the basic information about the database such as database objects and files and then utilize AST to generate valid INSERT or SELECT statements. |
name |
page 1 |
| M4 | 11% more branches, and finds 27, 27, and 22 more bugs in 12 hours than SQLancer, SQLsmith, and Sqirrel, respectively. |
name |
page 2 |
| M5 | Table 2 shows the lines of extra code of SQLsmith, SQLancer, andSqirrel to adapt SQLite, PostgreSQL, MariaDB, and DuckDB. |
name |
page 3 |
| M6 | For example, SQLancer uses over 8000 lines of code to build the SQL generation model for PostgreSQL. |
name |
page 3 |
| M7 | Table 2: The lines of code of SQLsmith, SQLancer, and Sqirrelto adapt for SQLite, PostgreSQL, MariaDB, and DuckDB. |
name |
page 3 |
| M8 | LoC SQLsmith SQLancer Sqirrel SQLite 1375 10020 5248 PostgreSQL 1466 8012 7515 MariaDB-2085 9050 DuckDB 1325 2597 More importantly, there are 391 different DBMSs on the market, most of which use different grammar. |
name |
page 3 |
| M9 | To evaluate the effectiveness of Griffin, we choose SQLsmith, SQLancer, and Sqirrel, which are widely used in industry and academia, for performance comparison. |
name |
page 7 |
| M10 | SQLancer and SQLsmith are generated-based DBMS fuzzers. |
name |
page 7 |
| M11 | For SQLancer and SQLsmith, ASE ’22, October 10–14, 2022, Rochester, MI, USA Jingzhou Fu, Jie Liang, Zhiyong Wu, Mingzhe Wang, and Yu Jiang Table 3: Statistics of previously unknown bugs detected by Griffin, 55 confirmed with 13 CVEs assigned. |
name |
page 7 |
| M12 | In addition, SQLancer, SQLsmith, and Sqirrel have not found this bug, although they have been fuzzing SQLite for a few years. | name | page 8 |
| M13 | SQLsmith can only generate SELECT statements, while SQLancer can not generate DELETE statements, because their generation models are based on the limited SQL grammar. | name | page 8 |
| M14 | 2 Comparison with Existing Fuzzers To evaluate the performance, we perform fuzzing with Griffin, SQLsmith, SQLancer, and Sqirrel on each test DBMS for 12 hours. | name | page 8 |
| M15 | 100101102103104 (a) SQLite5k8k10k12k15k18k20k22k 100101102103104 (b) DuckDB5k10k15k20k25k30k 100101102103104 (c) MariaDB0k20k40k60k80k100k120k 100101102103104 (d) PostgreSQL0k20k40k60k80k100k120k Number of Branches SQLsmith SQLancer GRIFFIN SQUIRREL Figure 7: The growing trend of the number of branches covered by di... | name | page 9 |
| M16 | 11% more branches than SQLancer, SQLsmith, and Sqirrel after fuzzing 12 hours, respectively. | name | page 9 |
| M17 | The two generation-based fuzzers, SQLancer and SQLsmith, can only generate SQL statements based on their predefined models, which cover only a portion of the entire SQL grammar of the DBMS. | name | page 9 |
| M18 | Therefore, SQL queries that conform to the SQL grammar of the DBMS but are not built in the predefined model cannot be generated by SQLsmith and SQLancer. | name | page 9 |
| M19 | Specifically, Griffin found 27, 27, and 22 more unique crashes than SQLsmith, SQLancer, and Sqirrel in 12 hours, respectively. | name | page 9 |
| M20 | SQLsmith SQLancer Sqirrel Griffin SQLite 0 0 0 1 DuckDB 0 0 - 9 MariaDB-0 5 15 PostgreSQL 0 0 0 2 Based on the improved coverage and mutated abundant kinds of SQL statements, Griffin can trigger more various behaviors of DBMS. | name | page 9 |
| M21 | 0000005 1 1 SQLancer SQLite 0. | name | page 10 |
| M22 | SQLancer [ 32] synthesizes two kinds of different SQL queries which are the same in semantics but evaluated by an optimizing and a non-optimizing version of DBMS for execution. | name | page 11 |
| M23 | Compared with SQLancer, SQLsmith, and Sqirrel ,Griffincovered 73. | name | page 11 |