SQLaser: Detecting DBMS Logic Bugs with Clause-Guided Fuzzing
Read the paper · arXiv:2407.04294
What this paper does with SQLancer
SQLancer's oracles are what SQLaser runs and what bounds it. It implements five oracles, two of them NoREC and TLP, which it describes as differential-testing oracles, and reports coverage for each. PQS it explicitly does not implement -- it is a non-differential oracle and does not fit the design -- and the paper is unusually candid about the cost: 13 of the 15 known MySQL bugs were found by PQS, which it gives as the reason SQLaser finds comparatively few there. The bug corpus it mines is itself drawn from SQLancer's reported bugs.
SQLaser fuzzes for logic bugs by targeting clause combinations. From 144 known logic bugs across SQLite, MySQL, PostgreSQL and TiDB it identifies the SQL clause combinations that recur in them, then guides fuzzing towards those combinations rather than exploring the grammar uniformly.
How it was classified
uses infrastructure — yes (unclear)
M13 states SQLaser's five oracles include NoREC and TLP, and M20 that bugs detected by PQS oracles were included in its analysis and their call chains instrumented. The oracles are used as they are, but the paper does not say whether they are invoked through SQLancer or reimplemented, so the form of the reuse is unclear.
The five oracles include: 1) the NoREC oracle, which rewrites an optimized query containing a WHERE clause to a SELECT query statement without the WHERE optimization; 2) the TLP oracle, which partitions a given query into multiple equivalent queries, and their results can be combined to obtain the same results as the original query; 3) the INDEX oracle, which 14 Wei et al.
However, in the process of statistically analyzing existing logic bugs, we include the bugs detected by PQS oracles and instrument their call chains.
extends technique — no
NoREC and TLP are used unchanged; what SQLaser contributes is clause-guided fuzzing that decides which test cases to generate, not what makes a result wrong.
compares with — yes
M17 and M18 report code coverage for SQLaser against SQLRight and WindRanger under the NoREC and TLP oracles, and M15 compares SQLaser's yield on MySQL against PQS's, which found 13 of the 15 known bugs there.
Non-optimizing Reference Engine Construction (NoREC)Ternary Logic Partitioning (TLP)Pivoted Query Synthesis (PQS)
/ SQLaser: Detecting DBMS Logic Bugs with Clause-Guided Fuzzing out of the 15 existing bugs we summarize for MySQL, 13 are detected by the PQS oracle, explaining the comparatively lower number of bug found by SQLaser for MySQL.
Code coverage of SQLaser, SQLRight and WindRanger for NoREC oracle.
Code coverage of SQLaser, SQLRight and WindRanger to trigger bugs for TLP oracle.
describes as state of the art — no
The oracles are described by mechanism and by their limits; no state-of-the-art claim is made for them.
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 |
|---|---|---|
| 38 | M. Rigger and Z. 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 and Sympo... | sqlancer publication · NOREC |
| 39 | M. Rigger and Z. Su, Finding bugs in database systems via query partitioning, in: Proceedings of the ACM on Programming Languages, V ol. 4, ACM New York, NY, USA, 2020, pp. 1–30. | sqlancer publication · TLP |
| 40 | M. Rigger and Z. Su, Testing database engines via pivoted query synthesis, in: Proceedings of 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), 2020, pp. 667–682. | sqlancer publication · PQS |
| 60 | Bugs Found in Database Management Systems. https://www.manuelrigger.at/dbms-bugs/. | project authored |
| 71 | SQLancer. https://github.com/sqlancer/sqlancer. | sqlancer publication |
Every place it refers to SQLancer (28)
28 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 | / SQLaser: Detecting DBMS Logic Bugs with Clause-Guided Fuzzing code and are particularly common, can cause a variety of serious issues, such as incorrect query results, exposure of sensitive data, unauthorized access, and data corruption [28, 38–40]. |
citation marker |
1 Introduction page 2 |
| M2 | For example, the Non-Optimizing Reference Engine Construction (NoREC) oracle [38] and the Ternary Logic Partitioning (TLP) oracle [39] are two oracles employing the concept of differential testing [32]. |
technique |
1 Introduction page 2 |
| M3 | Pivoted Query Synthesis (PQS) oracle [40] does not employ the concept of differential testing; instead, it automatically generates queries for which they ensure fetching a specific row, called the pivot row. |
technique |
1 Introduction page 2 |
| M4 | SQLancer [60, 71] that implements these oracles discovers logic bugs in various DBMSs. |
name |
1 Introduction page 2 |
| M5 | However, as SQLancer generates SQL queries based on specific rules, it may constrain the exploration of broader code paths. |
name |
1 Introduction page 2 |
| M6 | For instance, the Non-Optimizing Reference Engine Construction (NoREC) oracle [38] translates an optimized query containing a WHERE clause into an unoptimized version with identical semantics. |
technique |
2.2 Logic Bug Testing Oracles and Differential Testing page 5 |
| M7 | Ternary Logic Partitioning (TLP) oracle [39] composes several sub-queries to collectively achieve the semantics of the original query. |
technique |
2.2 Logic Bug Testing Oracles and Differential Testing page 5 |
| M8 | It is worth noting that the Pivoted Query Synthesis (PQS) oracles [40] proposed by Manuel Rigger et al. |
technique |
2.2 Logic Bug Testing Oracles and Differential Testing page 5 |
| M9 | As of now, we have not deployed PQS oracles into SQLaser. |
technique |
2.2 Logic Bug Testing Oracles and Differential Testing page 5 |
| M10 | In particular, we analyze a total of 144 existing logic bugs, including 102 in SQLite, 15 in MySQL, 1 in PostgreSQL, and 26 in TiDB [28, 60]. |
citation marker project authored |
3 Analysis of Existing Logic Bug Patterns page 6 |
| M11 | In the case of PostgreSQL, only one logic bug was found, specifically related to the PRIMARY KEY and GROUP BY clauses [71]. |
citation marker |
3 Analysis of Existing Logic Bug Patterns page 7 |
| M12 | DBMS SQL-level Bug Pattern (SQL Clause Combination) Number Bug Example SQLite [43]INDEX, PRIMARY KEY, WITHOUT ROWID, NOCASE 1 1b1dd4d4 [74] partial INDEX, LIKELY, ISFAIL 11 5351e920 [76] WITHOUT ROWID, PRIMARY KEYDESC 2 f65c929 [87] column value, CAST, LIKELY, UNLIKELY, GLOB 26 f9c6426 [89] column value, MIN 3 faaaa... |
citation marker |
4 SQLaser page 8 |
| M13 | The five oracles include: 1) the NoREC oracle, which rewrites an optimized query containing a WHERE clause to a SELECT query statement without the WHERE optimization; 2) the TLP oracle, which partitions a given query into multiple equivalent queries, and their results can be combined to obtain the same results as th... |
technique |
4.3.2 Testing Oracles page 13 |
| M14 | For instance, some bugs are identified by the PQS oracle [40] proposed by Manuel Rigger et al. |
technique |
6.1 Finding Bugs in DBMSs page 17 |
| M15 | / SQLaser: Detecting DBMS Logic Bugs with Clause-Guided Fuzzing out of the 15 existing bugs we summarize for MySQL, 13 are detected by the PQS oracle, explaining the comparatively lower number of bug found by SQLaser for MySQL. |
technique |
6.1 Finding Bugs in DBMSs page 18 |
| M16 | For NoREC and TLP oracles, they are implemented Wei et al. |
technique |
6.2.2 Code Coverage page 18 |
| M17 | Code coverage of SQLaser, SQLRight and WindRanger for NoREC oracle. |
technique |
6.2.2 Code Coverage page 19 |
| M18 | Code coverage of SQLaser, SQLRight and WindRanger to trigger bugs for TLP oracle. |
technique |
6.2.2 Code Coverage page 19 |
| M19 | Currently, SQLaser only supports differential testingbased oracles and does not accommodate other types of oracles, such as PQS oracle [40], which detects logic bugs through non-differential testing. |
technique |
7.1 Completeness of Testing Oracles page 21 |
| M20 | However, in the process of statistically analyzing existing logic bugs, we include the bugs detected by PQS oracles and instrument their call chains. |
technique |
7.1 Completeness of Testing Oracles page 21 |
| M21 | As SQLaser does not currently support PQS oracles, this may result in its inability to identify logic bugs detectable solely by PQS oracles. |
technique |
7.1 Completeness of Testing Oracles page 21 |
| M22 | Additionally, to the best of our knowledge, existing research has not extensively investigated the completeness of these five oracles (NoREC, TLP, INDEX, ROWID and LIKELY) in addressing logic bugs in real-world scenarios. |
technique |
7.1 Completeness of Testing Oracles page 21 |
| M23 | SQLancer [71] is a rulebased tool that successfully identifies numerous logic bugs. | name | 8 Related Work page 21 |
| M24 | It employs three distinct methods for detecting logic bugs: PQS [40], NoREC [38], and TLP [39]. | technique | 8 Related Work page 21 |
| M25 | PQS focuses on generating queries that fetch a 22 Wei et al. | technique | 8 Related Work page 21 |
| M26 | NoREC, on the other hand, translates an optimized query into an unoptimized version with identical semantics. | technique | 8 Related Work page 22 |
| M27 | Lastly, TLP partitions a query into several sub-queries, which are composed to have the same semantics as the original query. | technique | 8 Related Work page 22 |
| M28 | While SQLancer relies on a rule-based generator to detect logic bugs, limiting its exploration of input samples. | name | 8 Related Work page 22 |