Detecting Logic Bugs in DBMSs via Equivalent Data Construction
Read the paper · doi:10.1145/3769779
What this paper does with SQLancer
TLP is one of EDC's three baselines, named as a state-of-the-art open-source tool for finding logic bugs alongside EET and Radar. The comparison is reported in detail and is unusually candid about where each wins: EDC found 38 bugs to TLP's 9, they overlap on 3 -- all SQL-function bugs -- and the 6 bugs only TLP found involve JOINs, which are outside EDC's scope because it tests single-table queries. NoREC, TLP and PQS are each also described in the related-work section as the query-level approaches EDC is positioned against.
EDC detects logic bugs by constructing a second database whose data is equivalent to the first under the query being tested, so that the two must return the same result. Where earlier oracles transform the query and hold the data fixed, EDC transforms the data and holds the query fixed, which reaches bugs in how values are stored, converted and compared. Across MySQL, MariaDB, Percona, PostgreSQL, TiDB, OceanBase and ClickHouse it found 38 unique bugs.
How it was classified
uses infrastructure — no
TLP is run as a baseline; nothing states that EDC's own implementation reuses the SQLancer codebase.
extends technique — no
EDC transforms the data rather than the query, which the paper presents as a different oracle from TLP and NoREC rather than a generalisation of either.
compares with — yes
M8 names TLP as one of the three tools EDC is compared against, and M11 and M12 report per-DBMS and total bug counts for both.
Ternary Logic Partitioning (TLP)
We compare EDCagainst 3 state-of-the-art open-source tools for finding logic bugs in DBMSs: TLP [ 37], EET [ 27], and Radar [ 45].
During the evaluation,EDCfound 8, 6, 6, 2, 5, 6, and 7 bugs in MySQL, MariaDB, Percona, PostgreSQL, TiDB, OceanBase, and ClickHouse, respectively, while TLP detected 3 bugs in MySQL, 2 in Percona, 4 in TiDB, and none in others.
Across the seven DBMSs,EDCdetected 38 unique bugs, while TLP, Radar, and EET identified 9, 7, and 5 bugs respectively, highlighting the complementary nature of their testing strategies.
describes as state of the art — yes
M8 calls TLP one of three state-of-the-art open-source tools for finding logic bugs in DBMSs.
We compare EDCagainst 3 state-of-the-art open-source tools for finding logic bugs in DBMSs: TLP [ 37], EET [ 27], and Radar [ 45].
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 |
|---|---|---|
| 36 | Manuel Rigger and Zhendong Su. 2020. Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction. InProceedings of the 28th ACM Joint Meeting on European Software Engineering Confe... | sqlancer publication · NOREC |
| 37 | Manuel Rigger and Zhendong Su. 2020. Finding Bugs in Database Systems via Query Partitioning.Proceedings of the ACM on Programming Languages4, OOPSLA (2020), 1–30. | sqlancer publication · TLP |
| 38 | Manuel Rigger and Zhendong Su. 2020. Testing Database Engines via Pivoted Query Synthesis. In14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 667–682. | sqlancer publication · PQS |
| 39 | Manuel Rigger and Zhendong Su. 2020. Testing Database Engines via Pivoted Query Synthesis. In14th USENIX Symposium on Operating Systems Design and Implementation OSDI 20). 667–682. | 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 | For instance, EET [ 27] targets expression-level transformations, TLP [ 37] partitions queries based on predicate logic, and NoREC [36] rewrites queries to disable DBMS optimizations. |
technique |
1 Introduction page 2 |
| M2 | , TLP [ 37], Radar [ 45], and EET [ 27]. |
technique |
1 Introduction page 3 |
| M3 | 2 Limitations of Existing Approaches Several approaches have been proposed to detect logic bugs in DBMSs [ 27,36–38,44,45], many of which operate at the query level and rely on various strategies to identify inconsistencies in query results. |
citation marker |
2.2 Limitations of Existing Approaches page 4 |
| M4 | , TLP [ 37], NoREC [ 36]), while others construct logically crafted SQL queries designed to return specific results in a controlled manner (e. |
technique |
2.2 Limitations of Existing Approaches page 4 |
| M5 | , PQS [ 38], DQE [ 44]). |
technique |
2.2 Limitations of Existing Approaches page 4 |
| M6 | NoREC aims to reveal bugs by transforming query semantics, but its approach is primarily focused on a specific pattern of predicate rewriting, which may limit its coverage. |
technique |
2.2 Limitations of Existing Approaches page 4 |
| M7 | These DBMSs have been extensively tested by many existing approaches [ 21,27,29,30,38,50]. |
citation marker |
5.1 Evaluation Setup page 12 |
| M8 | We compare EDCagainst 3 state-of-the-art open-source tools for finding logic bugs in DBMSs: TLP [ 37], EET [ 27], and Radar [ 45]. |
technique |
5.5 Comparison with Existing Techniques page 19 |
| M9 | TLP [ 37] generates randomized databases and SQL queries to uncover incorrect query results, flagging logic bugs when expected rows are not retrieved. |
technique |
5.5 Comparison with Existing Techniques page 19 |
| M10 | For TLP and Radar, we conducted experiments using the default configurations for each DBMS. |
technique |
5.5 Comparison with Existing Techniques page 19 |
| M11 | During the evaluation,EDCfound 8, 6, 6, 2, 5, 6, and 7 bugs in MySQL, MariaDB, Percona, PostgreSQL, TiDB, OceanBase, and ClickHouse, respectively, while TLP detected 3 bugs in MySQL, 2 in Percona, 4 in TiDB, and none in others. |
technique |
5.5 Comparison with Existing Techniques page 19 |
| M12 | Across the seven DBMSs,EDCdetected 38 unique bugs, while TLP, Radar, and EET identified 9, 7, and 5 bugs respectively, highlighting the complementary nature of their testing strategies. |
technique |
5.5 Comparison with Existing Techniques page 19 |
| M13 | Among these, 3 bugs overlap with TLP, while no overlap exists with Radar or EET. |
technique |
5.5 Comparison with Existing Techniques page 19 |
| M14 | EDCand TLP share 3 overlapping bugs, all related to SQL functions. |
technique |
5.5 Comparison with Existing Techniques page 19 |
| M15 | However,EDCdetects significantly more bugs related to SQL functions and extends its coverage to other data operations, such as predicate operations, which TLP might miss. |
technique |
5.5 Comparison with Existing Techniques page 19 |
| M16 | The 6 unique bugs detected by TLP involve JOIN operations, which are outside the scope of EDC, as it focuses on single-table queries. |
technique |
5.5 Comparison with Existing Techniques page 19 |
| M17 | Many works have proposed various methods for detecting logic bugs in DBMSs [ 21,23,27,36,37,39,43–46]. |
citation marker |
5.5 Comparison with Existing Techniques page 21 |
| M18 | NoREC [ 36] works by generating a query with a predicate and then transforming the query to one that DBMSs cannot optimize. |
technique |
5.5 Comparison with Existing Techniques page 21 |
| M19 | TLP [ 37] breaks down the original query 3, No. |
technique |
5.5 Comparison with Existing Techniques page 21 |
| M20 | PQS [ 39] generates queries that are designed to always return a specific row by utilizing a custom interpreter. |
technique |
5.5 Comparison with Existing Techniques page 22 |
| M21 | If the DBMS under test fails to retrieve this row, PQS identifies it as a logic bug. |
technique |
5.5 Comparison with Existing Techniques page 22 |