Testing Gremlin-Based Graph Database Systems via Query Disassembling
Read the paper · doi:10.1145/3650212.3680392
What this paper does with SQLancer
Query partitioning is the technique QuDi positions itself against, reached through GDBMeter, which the paper describes as adopting TLP to derive a graph query into three disjoint sub-queries and so focusing on predicate-related bugs. The comparison is run: the authors check whether GDBMeter's query partitioning can detect the 25 bugs QuDi found. The conclusion is complementarity rather than replacement -- query partitioning cannot stop the system's optimisations from kicking in and so cannot expose assembly issues, and the paper says the two are complementary. SQLancer itself is explicitly not compared against, since QuDi targets Gremlin and SQLancer targets SQL.
QuDi tests Gremlin-based graph databases by disassembling a traversal into its atomic steps and checking that reassembling them reproduces the original result. The bugs it targets are in how a system implements and optimises the assembly of traversals, which a predicate-based oracle cannot reach because it varies the predicate rather than the traversal structure. It found 25 logic bugs across Gremlin-based systems.
How it was classified
uses infrastructure — no
M5 states QuDi and SQLancer target different database systems with different query languages, and that no comparison with SQLancer was run; nothing indicates reuse of its code either.
extends technique — no
Query disassembling operates on the structure of a traversal rather than on a predicate, and M9 calls it complementary to query partitioning rather than a development of it.
compares with — yes
M3 and M6 name GDBMeter among the tools QuDi is compared with, and M10 states the authors verified whether its query partitioning could detect the 25 bugs QuDi found. The comparison reaches TLP through GDBMeter, which M4 identifies as a TLP-based tool.
Ternary Logic Partitioning (TLP)
,Grand[ 64],GDsmith[ 39],RD2[62], and GDBMeter [ 42], can /f_ind bugs in GDBs.
Comparison with query partitioning.
We /f_irst verify whether query partitioning in GDBMeter can detect the 25 logic bugs detected by QuDi.
describes as state of the art — no
The techniques are described by what they do and where they fall short; no state-of-the-art claim is made.
SQLancer publications it cites (6)
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 |
|---|---|---|
| 27 | Jinsheng Ba and Manuel Rigger. 2023. Testing Database Engines via Query Plan Guidance. In Proceedings of IEEE/ACM International Conference on Software Engineering (ICSE). 2060–2071. https://doi.org/10.1109/ICSE48619.2... | sqlancer publication · QPG |
| 40 | Yuancheng Jiang, Jiahao Liu, Jinsheng Ba, Roland H. C. Yap, Zhenkai Liang, and Manuel Rigger. 2024. Detecting Logic Bugs in Graph Database Management SystemsviaInjectiveandSurjectiveGraphQueryTransformation.In Proceed... | project authored |
| 42 | Matteo Kamm, Manuel Rigger, Chengyu Zhang, and Zhendong Su. 2023. Testing Graph Database Engines via Query Partitioning. In Proceedings of ACMSIGSOFT InternationalSymposiumonSoftwareTestingandAnalysis(ISSTA) .https://... | project authored |
| 51 | ManuelRiggerandZhendongSu.2020. DetectingOptimizationBugsinDatabase EnginesviaNon-OptimizingReferenceEngineConstruction.In Proceedingsof ACM Joint European Software Engineering Conference and Symposium on the Foundati... | sqlancer publication · NOREC |
| 52 | ManuelRiggerandZhendongSu.2020. FindingBugsinDatabaseSystemsvia QueryPartitioning. 4,Article211(2020), 30pages. | sqlancer publication · TLP |
| 53 | ManuelRiggerandZhendongSu.2020. TestingDatabaseEnginesviaPivoted Query Synthesis. In Proceedings of USENIX Symposium on Operating Systems Designand Implementation(OSDI). 667–682. | sqlancer publication · PQS |
Every place it refers to SQLancer (18)
18 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 | GDBMeter[ 42] adopts Ternary LogicPartitioning (TLP)[52]toderiveagraphqueryintothreedisjointsub-queries based on a randomly generated predicate, and only focuses on detecting predicate-related bugs. |
technique |
1 Introduction page 2 |
| M2 | Furthermore, some testing approaches [ 27,30,37,51–53,56,57] have proposed new test oracles to effectively /f_ind logic bugs in an individual relational database system. |
citation marker |
1 Introduction page 2 |
| M3 | ,Grand[ 64],GDsmith[ 39],RD2[62], and GDBMeter [ 42], can /f_ind bugs in GDBs. |
citation marker project authored |
4.3 Comparingwith ExistingApproaches page 9 |
| M4 | GDBMeter utilizes Ternary Logic Partitioning (TLP), an invariant of query partitioning [52], toreveallogicbugsinatarget GDB. |
technique |
4.3 Comparingwith ExistingApproaches page 9 |
| M5 | ,SQLancer [51–53],sinceQuDiandSQLancertargetdifferenttypesofdatabase systems, which utilize different query languages (Gremlin vs. |
name |
4.3 Comparingwith ExistingApproaches page 9 |
| M6 | Comparison with query partitioning. |
technique |
4.3 Comparingwith ExistingApproaches page 9 |
| M7 | In query partitioning (e. |
technique |
4.3 Comparingwith ExistingApproaches page 9 |
| M8 | , /u1D444′ /u1D45D=/u1D447/u1D445/u1D448/u1D438,/u1D444′ /u1D45D=/u1D439/u1D434/u1D43F/u1D446/u1D438, and/u1D444′ /u1D45D /u1D456/u1D460 /u1D441/u1D448/u1D43F/u1D43Fbased on a random predicate /u1D45Din TLP). |
technique |
4.3 Comparingwith ExistingApproaches page 9 |
| M9 | However,querypartitioningcannotprevent GDBoptimizationsfrom kickinginandrevealassemblyissuesin GDBs,sothatitcanhardly detect logic bugs that are caused by incorrect implementations and optimizationsoftheassemblyofatomic graphtraversals,andour query disassembling iscomplementary to query partitioning. |
technique |
4.3 Comparingwith ExistingApproaches page 9 |
| M10 | We /f_irst verify whether query partitioning in GDBMeter can detect the 25 logic bugs detected by QuDi. |
technique |
4.3 Comparingwith ExistingApproaches page 9 |
| M11 | , query partitioning and query disassembling). |
technique |
4.3 Comparingwith ExistingApproaches page 9 |
| M12 | Somemetamorphictestingapproaches [37,51,52,56,57]for/f_indingbugsinrelationaldatabasesystems have beenproposed. |
citation marker |
5 Discussion page 11 |
| M13 | For example,query partitioning[ 52]derives a given querytomultiple disjointsub-queries,in whichtheresult of the given query is the same as the combination result of disjoint sub-queries. |
technique |
5 Discussion page 11 |
| M14 | NoREC [ 51] transforms an optimized SQL query toanon-optimized SQLquery,andcan/f_indoptimizationbugsin relational database systems. |
technique |
5 Discussion page 11 |
| M15 | TotestGDBs,GDBMeter[ 42]derivesagraphqueryintothree disjoint sub-queries by randomly generating a predicate, which mainly focuses on predicate-related bugs. |
citation marker project authored |
5 Discussion page 11 |
| M16 | Given a graph query /u1D444, GraphGenie [ 40] derives a mutated graphquerywhosequeryresultsetiseithersemanticallyequivalent totheresultsetof /u1D444orconstitutesasubsetorsupersetoftheresult set of/u1D444, dependingon the mutationapplied. |
citation marker project authored |
5 Discussion page 11 |
| M17 | PQS[ 53]teststhecorrectness ofrelationaldatabasesystemsbyrandomlyselectingapivotrow and generating random SQL queries that contain the selected row. |
technique |
5 Discussion page 11 |
| M18 | QPG [27] can improve testing efficiency by exploring a variety ofuniquequeryplans. |
technique |
5 Discussion page 11 |