SQLaser: Detecting database management system (DBMS) logic bugs with clause-guided fuzzing
Read the paper · doi:10.1177/0926227x251370258 · arXiv:2407.04294
What this paper does with SQLancer
SQLaser adopts SQLancer's oracles rather than competing with them: NoREC and TLP are described as the oracles it works with, PQS is noted as not yet deployed in it, and its argument is that SQLancer's rule-based generation constrains the code paths reached. Several of the bug patterns it studies come from SQLancer's own reported bugs.
SQLaser is a directed fuzzer guided by SQL clauses. The authors argue rule-based detection is limited by how hard rules are to specify, while coverage-guided fuzzing explores many paths unlikely to hold logic bugs. From examining existing non-crashing logic bugs across four DBMSs they derive 35 patterns, expressed as clause combinations backed by function sequences, and model these as error-prone function chains driven by a directed fuzzer with a new path-to-path distance mechanism. On SQLite, MySQL, PostgreSQL and TiDB it cut detection time by about 60% and found 22 bugs, four zero-day.
How it was classified
uses infrastructure — uncertain
M9 says PQS oracles have not yet been deployed into SQLaser, which implies NoREC and TLP have been, but no mention read states that the codebase itself is reused rather than the oracles reimplemented.
extends technique — no
The contribution is clause-guided directed fuzzing; the oracles are used as they are.
compares with — uncertain
SQLancer's oracles are used within SQLaser rather than run against it in the mentions read.
describes as state of the art — no
The oracles are described by what they do rather than as the state of the art.
What could not be determined
- Whether NoREC and TLP are reimplemented or taken from SQLancer's code is not stated in the mentions 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 |
|---|---|---|
| 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 |