Differential Optimization Testing of Gremlin-Based Graph Database Systems
Read the paper · doi:10.1109/icst60714.2024.00012
What this paper does with SQLancer
SQLancer's techniques frame the paper twice over. NoREC is the direct inspiration and the direct obstacle: DOT targets the same class of optimisation bugs, but the paper explains at length why NoREC's rewriting cannot be applied to Gremlin's procedural queries, which is what forces the different mechanism. Query partitioning is the comparison, reached through GDBMeter, one of four existing approaches for finding logic bugs in graph databases; the paper compares DOT with differential testing and with query partitioning as the two families that can find these bugs.
DOT tests Gremlin-based graph databases for optimisation bugs by running a traversal with the system's optimisations enabled and disabled and comparing the results. The paper's starting point is that NoREC's idea does not carry across: a Gremlin traversal is procedural and cannot be rewritten into a non-optimising equivalent the way a declarative SQL query can, so the equivalent must be obtained by controlling the optimiser instead of by rewriting the query.
How it was classified
uses infrastructure — no
Nothing describes DOT's implementation as reusing SQLancer's code; GDBMeter is run as a comparison target.
extends technique — no
M4 and M5 set out why NoREC's rewriting cannot be applied to Gremlin at all, which is the reason DOT controls the optimiser instead. Sharing a target bug class with NoREC is not extending it.
compares with — yes
M8 identifies GDBMeter among the four existing approaches, M10 states DOT is compared with differential testing and query partitioning, and M11 heads that comparison. M9 and M12 identify GDBMeter as the query-partitioning tool.
Ternary Logic Partitioning (TLP)
Comparison with Existing Approaches To the best of our knowledge, four existing approaches [13]– [16] can detect logic bugs in GDBs.
Therefore, we compare DOT with differential testing and query partitioning.
Comparison with query partitioning.
describes as state of the art — no
The approaches are described by mechanism and by applicability; no state-of-the-art claim is made.
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 |
|---|---|---|
| 14 | M. Kamm, M. Rigger, C. Zhang, and Z. Su, “Testing graph database engines via query partitioning,” in Proceedings of ACMSIGSOFT International Symposium on Software Testing and Analysis (ISSTA), 2023. | project authored |
| 20 | M. Rigger and Z. Su, “Finding bugs in database systems via query partitioning,” in Proceedings of ACM Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), 2020, pp. 211:1–30. | sqlancer publication · TLP |
| 21 | ——, “Detecting optimization bugs in database engines via nonoptimizing reference engine construction,” in Proceedings of ACM Joint European Software Engineering Conference and Symposium on the F oundations of Software... | sqlancer publication · NOREC |
| 22 | ——, “Testing database engines via pivoted query synthesis,” in Proceedings of USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2020, pp. 667–682. | sqlancer publication · PQS |
| 24 | J. Ba and M. Rigger, “Testing database engines via query plan guidance,” inProceedings of International Conference on Software Engineering (ICSE), 2023, pp. 2060–2071. | sqlancer publication · QPG |
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 | Recently, several approaches [13]–[16] have been proposed to find logic bugs in GDBs. |
citation marker project authored |
I INTRODUCTION page 2 |
| M2 | Many testing approaches [17]–[26] (e. |
citation marker |
I INTRODUCTION page 2 |
| M3 | , TLP [20], NoREC [21], and DQE [25]) have been proposed to test relational database systems. |
technique |
I INTRODUCTION page 2 |
| M4 | Among these approaches, NoREC [21] can detect optimization bugs in relational database systems by rewriting an optimized SQL query into a nonoptimizing SQL query. |
technique |
I INTRODUCTION page 2 |
| M5 | However, a Gremlin query cannot be rewritten into a non-optimizing Gremlin query by using the idea in NoREC because the procedural Gremlin queries in Gremlin-based GDBs adopt different query patterns from that of the declarative SQL queries in relational database systems. |
technique |
I INTRODUCTION page 2 |
| M6 | , Grand [13]) and query partitioning (i. |
technique |
I INTRODUCTION page 2 |
| M7 | , GDBMeter [14]). |
citation marker project authored |
I INTRODUCTION page 2 |
| M8 | Comparison with Existing Approaches To the best of our knowledge, four existing approaches [13]– [16] can detect logic bugs in GDBs. |
citation marker project authored |
D Comparison with Existing Approaches page 9 |
| M9 | , GDBMeter [14]) uses query partitioning. |
technique |
D Comparison with Existing Approaches page 9 |
| M10 | Therefore, we compare DOT with differential testing and query partitioning. |
technique |
D Comparison with Existing Approaches page 9 |
| M11 | Comparison with query partitioning. |
technique |
D Comparison with Existing Approaches page 9 |
| M12 | GDBMeter applies query partitioning [20] to test GDBs. |
technique |
D Comparison with Existing Approaches page 9 |
| M13 | Recently, many works [13]–[16] have been proposed to test the correctness of GDBs. |
citation marker project authored |
VII RELA TED WORK page 10 |
| M14 | Grand [13], RD2[15], and GDsmith [16] detect logic bugs in multiple GDBs by utilizing differential testing [46]– [48], while GDBMeter [14] utilize metamorphic testing [49] to find logic bugs in an individual GDB. |
citation marker project authored |
VII RELA TED WORK page 10 |
| M15 | Researchers have developed various testing approaches on relational DBMSs [17]–[25], [50]–[56]. |
citation marker |
VII RELA TED WORK page 10 |
| M16 | Some approaches [20], [21], [25] (e. |
citation marker |
VII RELA TED WORK page 10 |
| M17 | , NoREC [21]) utilizes metamorphic testing for finding logic bugs in relational DBMSs. |
technique |
VII RELA TED WORK page 10 |