DepState: Detecting Synchronization Failure Bugs in Distributed Database Management Systems
Read the paper · doi:10.1145/3728965
What this paper does with SQLancer
SQLancer is one of five baselines and is called a state-of-the-art DBMS testing technique. Because it was built for single-node systems, the authors ran it against one SQL server of each cluster. The comparison is reported in both bugs and coverage of synchronization-related functions, and the paper's explanation for the gap is structural rather than dismissive: SQLancer, SQLsmith and Mozi only generate SQL queries, which cannot navigate the space of cluster states, so all three of SQLancer's bugs were ordinary ones and none was a synchronization failure.
DepState looks for synchronization failure bugs in distributed DBMSs -- cases where replicas diverge or a node fails to converge after a state change. It drives clusters through dependency-aware state transitions rather than only issuing queries, so it reaches synchronization code that query-level testing never executes. On MySQL NDB Cluster, MySQL InnoDB Cluster, MariaDB Galera Cluster and TiDB Cluster it found 14 synchronization failure bugs, where the five existing tools found none.
How it was classified
uses infrastructure — no
SQLancer is executed as a baseline on a single server of each cluster; DepState's own mechanism is dependency-aware state transitions across the cluster.
extends technique — no
No SQLancer oracle is carried forward. DepState's oracle is divergence between replicas, which the paper contrasts with query-level testing.
compares with — yes
M4 names SQLancer among the five tools DepState is compared with, M10 gives the per-cluster unique-bug table, and M11 reports SQLancer's three bugs against DepState's fourteen.
To evaluate the effectiveness of DepState in testing DDBMSs, we compare it with five state-of-the-art tools: Jepsen [ 17],Mallory [26], SQLsmith [ 2], SQLancer [ 33], andMozi [23].
Number of Unique Bugs Detected by Jepsen, Mallory, SQLsmith, SQLancer, Mozi, and DepState DDBMS Jepsen Mallory SQLsmith SQLancer Mozi DepState MySQL NDB Cluster 0 1 0 1 7 7 MySQL InnoDB Cluster 1 0 0 1 6 2 MariaDB Galera Cluster 1 1 0 1 0 2 TiDB Cluster 0 0 0 0 0 3 Total (Sync Failure Bugs) 2 (0) 2 (0) 0 (0) 3 (0) 13 (0) 14 (14) 24 hours, recording the number of detected bugs and covered synchronization-related functions as metrics.
In comparison, Jepsen, Mallory, SQLancer, and Mozi reported 2, 2, 3, and 13 bugs, respectively, while SQLsmith found no bugs.
describes as state of the art — yes
M4 calls the five comparison tools state-of-the-art, and M5 says specifically that SQLsmith, SQLancer and Mozi are three state-of-the-art DBMS testing techniques that have detected hundreds of bugs in practice.
To evaluate the effectiveness of DepState in testing DDBMSs, we compare it with five state-of-the-art tools: Jepsen [ 17],Mallory [26], SQLsmith [ 2], SQLancer [ 33], andMozi [23].
SQLsmith, SQLancer, and Mozi are three state-of-the-art DBMS testing techniques, which have detected hundreds of bugs in practice.
SQLancer publications it cites (2)
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. 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 |
| 33 | Manuel Rigger and Zhendong Su. 2020. Testing database engines via pivoted query synthesis. In Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation (OSDI’20). USENIX Association, USA... | sqlancer publication · PQS |
Every place it refers to SQLancer (17)
17 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 | 28% more lines in synchronization-related functions than Jepsen, Mallory, SQLsmith, SQLancer, and Mozi in 24 hours, respectively. |
name |
page 1 |
| M2 | In addition, we compare DepState with the state-of-the-art distributed system testing tool Jepsen and Mallory, and advanced database testing tools SQLsmith, SQLancer, and Mozi. |
name |
1 Introduction page 3 |
| M3 | 28% more lines in synchronization-related functions than Jepsen, Mallory, SQLsmith, SQLancer, and Mozi, respectively. |
name |
1 Introduction page 3 |
| M4 | To evaluate the effectiveness of DepState in testing DDBMSs, we compare it with five state-of-the-art tools: Jepsen [ 17],Mallory [26], SQLsmith [ 2], SQLancer [ 33], andMozi [23]. |
name |
5.1 Evaluation Setup page 14 |
| M5 | SQLsmith, SQLancer, and Mozi are three state-of-the-art DBMS testing techniques, which have detected hundreds of bugs in practice. |
name |
5.1 Evaluation Setup page 14 |
| M6 | For SQLsmith, SQLancer, and Mozi, since they were designed for testing traditional DBMS, we used them on a single SQL server of the DDBMS as a baseline. |
name |
5.1 Evaluation Setup page 14 |
| M7 | We selected traditional database testing tools, including SQLsmith, SQLancer, and Mozi, as benchmarks. |
name |
5.1 Evaluation Setup page 14 |
| M8 | 3 Comparison with Other Techniques To evaluate the effectiveness of our DepState, we conducted comparison experiments between DepState with Jepsen, Mallory, SQLsmith, SQLancer, and Mozi. |
name |
5.3 Comparison with Other Techniques page 16 |
| M9 | SQLsmith, SQLancer and Mozi are three popular DBMS testing methods. |
name |
5.3 Comparison with Other Techniques page 16 |
| M10 | Number of Unique Bugs Detected by Jepsen, Mallory, SQLsmith, SQLancer, Mozi, and DepState DDBMS Jepsen Mallory SQLsmith SQLancer Mozi DepState MySQL NDB Cluster 0 1 0 1 7 7 MySQL InnoDB Cluster 1 0 0 1 6 2 MariaDB Galera Cluster 1 1 0 1 0 2 TiDB Cluster 0 0 0 0 0 3 Total (Sync Failure Bugs) 2 (0) 2 (0) 0 (0) 3 (0) 1... |
name |
5.3 Comparison with Other Techniques page 17 |
| M11 | In comparison, Jepsen, Mallory, SQLancer, and Mozi reported 2, 2, 3, and 13 bugs, respectively, while SQLsmith found no bugs. |
name |
5.3 Comparison with Other Techniques page 17 |
| M12 | One of the main reasons that DepState discovered synchronization failure bugs is that DepState can cover more synchronization function logic and trigger more behaviors of DDBMSs compared to Jepsen, Mallory, SQLsmith, SQLancer, andMozi. |
name |
5.3 Comparison with Other Techniques page 17 |
| M13 | It demonstrates that DepState covers more synchronization-related function lines compared to Jepsen, Mallory, SQLsmith, SQLancer, and Mozi. |
name |
5.3 Comparison with Other Techniques page 17 |
| M14 | 28% more synchronizationrelated function lines compared to Jepsen, Mallory, SQLsmith, SQLancer, and Mozi, respectively. |
name |
5.3 Comparison with Other Techniques page 17 |
| M15 | Moreover, SQLsmith, SQLancer, and Mozi only generate SQL queries, hindering their ability to navigate the vast search space of distributed environments and detect cluster-state-induced bugs. |
name |
5.3 Comparison with Other Techniques page 17 |
| M16 | Lines of Synchronization-Related Functions Covered by Tested Tools in 24 Hours DDBMS Jepsen Mallory SQLsmith SQLancer Mozi DepState MySQL NDB Cluster 11,850 11,092 11,505 10,588 10,622 16,388 MySQL InnoDB Cluster 2,096 2,219 1,904 2,551 2,731 3,490 MariaDB Galera Cluster 1,241 1,257 1,147 1,185 1,191 1,706 TiDB Clus... |
name |
5.3 Comparison with Other Techniques page 17 |
| M17 | Furthermore, SQLancer [ 33] employs metamorphic testing methodologies [ 32] to detect logical bugs within DBMSs, proposing three distinct test oracles for the automatic detection of various correctness issues. |
name |
7.2 DBMS Testing page 20 |