Sequence-Oriented DBMS Fuzzing
Read the paper · doi:10.1109/icde55515.2023.00057
What this paper does with SQLancer
SQLancer is one of the three fuzzers Lego is measured against, described as a state-of-the-art academic fuzzer that generates from custom rules mainly for SELECT statements. Lego reports covering 198% more branches than it, and notes that SQLancer found no bugs in their setting.
Lego generates SQL sequences with a wide range of statement types, addressing the problem that existing DBMS fuzzers reuse a limited set of predefined types and so cannot cover the hundreds of statement types in the SQL specification. Its key notion is type-affinity, the meaningful co-occurrence of statement type pairs such as INSERT and SELECT: each iteration explores statements of different types, analyses affinities using coverage feedback, and synthesises new sequences as affinities are discovered. Lego found 102 new vendor-confirmed vulnerabilities across four DBMSs, 22 with CVEs.
How it was classified
uses infrastructure — no
SQLancer appears only as a fuzzer run for comparison.
extends technique — no
Type-affinity sequence generation is Lego's own; no SQLancer technique is generalised.
compares with — yes
Lego is evaluated against SQLancer on four DBMSs, reporting 198% more branches covered and that SQLancer found no bugs in that setting.
We evaluate LEGO on PostgreSQL, MySQL, MariaDB, and Comdb2 against SQLancer, SQLsmith, and SQUIRREL.
We evaluate LEGO on the latest version of PostgreSQL, MySQL, MariaDB, and Comdb2 against SQLancer, SQLsmith, and SQUIRREL.
The sequence-oriented fuzzing helps LEGO cover 198%, 44%, and 120% more branches than SQLancer, SQLsmith, and SQUIRREL on average, respectively.
Specifically, SQLancer and SQLsmith did not find any bugs.
describes as state of the art — yes
M8 says the comparison was chosen to encompass as many state-of-the-art DBMS fuzzers as possible, naming SQLancer from the academic side.
To encompass as many state-of-the-art DBMS fuzzers as possible, we compared LEGO to popular fuzzer SQUIRREL and SQLancer from the academy and SQLsmith from the industry.
SQLancer publications it cites (4)
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. 2022. Bugs found in Database Management Systems. https://www .manuelrigger .at/dbms-bugs. Accessed: November 29, 2022. | project authored |
| 33 | Manuel Rigger and Zhendong Su. 2020. Detecting optimization bugs in database engines via non-optimizing reference engine construction. In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conf... | sqlancer publication · NOREC |
| 34 | Manuel Rigger and Zhendong Su. 2020. Finding bugs in database systems via query partitioning. Proc. ACM Program. Lang. 4, OOPSLA (2020), 211:1–211:30. https: //doi.org/10 .1145/3428279 | sqlancer publication · TLP |
| 35 | 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 (26)
26 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 | We evaluate LEGO on PostgreSQL, MySQL, MariaDB, and Comdb2 against SQLancer, SQLsmith, and SQUIRREL. |
name |
page 1 |
| M2 | Security vulnerabilities, especially memory bugs such as buffer overflow are particularly dangerous for DBMS because they might allow attackers to steal information, tamper data, crash systems, and bring heavy losses [4, 10, 32, 35, 51, 54]. |
citation marker |
I INTRODUCTION page 1 |
| M3 | To test logic and performance bugs, many representative schemes utilize differential testing [16, 35, 39]. |
citation marker |
I INTRODUCTION page 1 |
| M4 | In general, fuzzers could be divided into generation-based [35, 37] and mutation-based [15, 51, 54]. |
citation marker |
I INTRODUCTION page 1 |
| M5 | We evaluate LEGO on the latest version of PostgreSQL, MySQL, MariaDB, and Comdb2 against SQLancer, SQLsmith, and SQUIRREL. |
name |
I INTRODUCTION page 2 |
| M6 | The sequence-oriented fuzzing helps LEGO cover 198%, 44%, and 120% more branches than SQLancer, SQLsmith, and SQUIRREL on average, respectively. |
name |
I INTRODUCTION page 2 |
| M7 | , SQLsmith and SQLancer) generate seeds based on custom rules. |
name |
II SQL TYPE SEQUENCE page 3 |
| M8 | To encompass as many state-of-the-art DBMS fuzzers as possible, we compared LEGO to popular fuzzer SQUIRREL and SQLancer from the academy and SQLsmith from the industry. |
name |
A Evaluation Setup page 7 |
| M9 | Specifically, SQLancer and SQLsmith did not find any bugs. |
name |
B DBMS Vulnerability Detection page 8 |
| M10 | SQLancer generates test cases based on custom pattern rules mainly for SELECT statements, while only a limited number of SQL Type Sequences can be generated. |
name |
B DBMS Vulnerability Detection page 9 |
| M11 | The two metrics are used as the standard in fuzzing evaluation [8, 17, 44], and have been widely used in fuzzing works [35, 42, 54]. |
citation marker |
C Comparison with Other DBMS Fuzzers page 9 |
| M12 | To evaluate LEGO, we compared it against SQLancer, SQLsmith, and SQUIRREL. | name | C Comparison with Other DBMS Fuzzers page 9 |
| M13 | PostgreSQL MySQL MariaDB Comdb2020000400006000080000100000120000140000 Lego squirrel sqlancer sqlsmith Fig. | name | C Comparison with Other DBMS Fuzzers page 9 |
| M14 | Number of branches covered by LEGO, SQUIRREL, SQLancer, and SQLsmith on 4 DBMSs in 24 hours. | name | C Comparison with Other DBMS Fuzzers page 9 |
| M15 | Specifically, LEGO covered 198%, 44%, and 120% more branches than SQLancer, SQLsmith, and SQUIRREL on average, respectively. | name | C Comparison with Other DBMS Fuzzers page 9 |
| M16 | SQLancer and SQLsmith are two state-of-the-art DBMS fuzzers that generate test cases from rules. | name | C Comparison with Other DBMS Fuzzers page 10 |
| M17 | Specifically, SQLancer continuously generates test cases for fuzzing based on custom pattern rules, while only a limited number of SQL Type Sequences can be generated. | name | C Comparison with Other DBMS Fuzzers page 10 |
| M18 | Due to the coverage feedback and its efforts to improve syntactic and semantic correctness, SQUIRREL performs better than SQLancer in these DBMSs. | name | C Comparison with Other DBMS Fuzzers page 10 |
| M19 | TABLE IINUMBER OFTYPE-AFFINITIES GENERATED BYDIFFERENT FUZZERS DBMS SQLancer SQUIRREL LEGO PostgreSQL 474 34 2101 MySQL 50 21 643 MariaDB 119 28 734 Comdb2 127 36 229 Total 770 119 3707 Increment 2937 3588 – In contrast, LEGO is designed to increase the abundance of SQL Type Sequences. | name | C Comparison with Other DBMS Fuzzers page 10 |
| M20 | It shows that LEGO found 52, 52, and 41 more bugs than SQLancer, SQLsmith, and SQUIRREL, respectively. | name | C Comparison with Other DBMS Fuzzers page 10 |
| M21 | SQLancer focuses on detecting logic bugs in DBMSs, but the bug-finding process is limited by its predefined rules. | name | C Comparison with Other DBMS Fuzzers page 10 |
| M22 | TABLE IIINUMBER OFBUGS TRIGGERED IN 24HOURS DBMS SQLancer SQLsmith SQUIRREL LEGO PostgreSQL 0 0 0 2 MySQL 0 – 3 11 MariaDB 0 – 8 32 Comdb2 0 – 0 7 Total 0 0 11 52 Increment 52 52 41 – Consequently, it did not trigger bugs in the latest versions of these DBMSs. | name | C Comparison with Other DBMS Fuzzers page 10 |
| M23 | Thus, LEGO found more bugs than SQLancer, SQLsmith, and SQUIRREL. | name | C Comparison with Other DBMS Fuzzers page 10 |
| M24 | SQLancer [35] synthesizes queries to fetch a random row from existing tables in the target DBMS. | name | D Effectiveness of Sequence-Oriented Algorithms in LEGO page 12 |
| M25 | Its following works [34, 33] also apply similar strategies by building functionally equivalent queries. | citation marker | D Effectiveness of Sequence-Oriented Algorithms in LEGO page 12 |
| M26 | Generation-based fuzzers [25, 35, 37, 43] have been used to test DBMSs for decades. | citation marker | D Effectiveness of Sequence-Oriented Algorithms in LEGO page 12 |