Dinkel: State-Aware and Granular Framework for Validating Graph Databases
Read the paper · doi:10.14778/3797919.3797928 · arXiv:2408.07525
What this paper does with SQLancer
SQLancer's techniques appear as the relational background against which graph testing is measured. GDBMeter is one of the existing approaches Dinkel is compared with, and the paper identifies its oracle as query partitioning -- decomposing a query's predicate and checking the decomposed queries agree with the original. PQS is cited as the relational counterpart that synthesises queries fetching specific rows. The paper's own contribution is generation rather than an oracle, and it observes that relational testing is the more mature field, with both query generation and test-oracle construction well researched there.
Dinkel generates Cypher queries for graph database systems while tracking the state a query builds up, so that later clauses can refer correctly to variables bound earlier. That state-awareness lets it emit far more of the Cypher language than the existing generators, which restrict themselves to shapes their transformation rules can handle. On Neo4j, RedisGraph and Memgraph it found bugs none of the existing approaches had reported.
How it was classified
uses infrastructure — no
Dinkel implements its own state-aware Cypher generator; nothing describes reuse of SQLancer's code.
extends technique — no
Dinkel contributes query generation rather than an oracle, and no SQLancer technique is carried forward or generalised.
compares with — yes
M5 compares Dinkel's Cypher clause coverage against the existing approaches including GDBMeter, and M9 argues the bug comparison is fair because all of them have extensively tested the same systems. M13 identifies GDBMeter's oracle as query partitioning. The comparison is with the tool rather than a direct run of TLP.
Ternary Logic Partitioning (TLP)
As shown in Table 4, Dinkel supports more Cypher clauses than existing approaches [ 13,14,20,27,51].
This comparison is reasonable and objective because: (1) none of the bugs found by Dinkel are marked as duplicated by developers, meaning that no approach found these bugs until Dinkel found them; and (2) all existing approaches have extensively tested Neo4j and RedisGraph [ 13,14,20,27,51], meaning that in these two GDBMSs, no approach found the long-latent bugs found by Dinkel during their evaluation.
describes as state of the art — no
Relational testing is called the more mature field, which is not a claim that any particular technique is the state of the art.
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 |
|---|---|---|
| 14 | Yuancheng Jiang, Jiahao Liu, Jinsheng Ba, Roland Hock Chuan Yap, Zhenkai Liang, and Manuel Rigger. 2023. Detecting Logic Bugs in Graph Database Management Systems via Injective and Surjective Graph Query Transformatio... | project authored |
| 17 | Zu-Ming Jiang, Si Liu, Manuel Rigger, and Zhendong Su. 2023. Detecting Transactional Bugs in Database Engines via Graph-Based Oracle Construction. In Proceedings of the 17th USENIX Symposium on Operating Systems Desig... | project authored |
| 20 | Matteo Kamm, Manuel Rigger, Chengyu Zhang, and Zhendong Su. 2023. Testing Graph Database Engines via Query Partitioning. InProceedings of the 2023 International Symposium on Software Testing and Analysis (ISSTA). 140–... | project authored |
| 37 | 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 |
| 38 | Manuel Rigger and Zhendong Su. 2020. Finding Bugs in Database Systems via Query Partitioning. InProceedings of the 2020 International Conference on Object Oriented Programming Systems Languages and Applications (OOPSL... | sqlancer publication · TLP |
| 39 | Manuel Rigger and Zhendong Su. 2020. Testing Database Engines via Pivoted Query Synthesis. InProceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 667–682. | sqlancer publication · PQS |
Every place it refers to SQLancer (16)
16 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 | To improve GDBMS reliability, testing approaches [ 13,14,20,51] have been proposed to find bugs by generating queries in Cypher, the most widely-adopted graph query language [ 34]. |
citation marker project authored |
1 INTRODUCTION page 1 |
| M2 | In DBMSs, many bugs can only be triggered by complex queries [ 16–18]. |
citation marker project authored |
1 INTRODUCTION page 1 |
| M3 | For example, GraphGenie [ 14] requires the predicate in MATCH clauses to satisfy the preconditions of their transformation rules (e. |
citation marker project authored |
1 INTRODUCTION page 2 |
| M4 | The most widely used graph model is thelabeled property graph model[ 14], which stores interconnected data using nodes connected via relationships (i. |
citation marker project authored |
2 BACKGROUND page 3 |
| M5 | As shown in Table 4, Dinkel supports more Cypher clauses than existing approaches [ 13,14,20,27,51]. |
citation marker project authored |
4 IMPLEMENTATION page 7 |
| M6 | 1 Experimental Setup We evaluated Dinkel on Neo4j [ 32], RedisGraph [ 35], and Memgraph [ 29], which are popular and extensively tested by existing approaches [ 13,14,20,27,51]. |
citation marker project authored |
5.1 Experimental Setup page 7 |
| M7 | 2, because all the bugtriggering queries are reduced, while the generated queries inevitably contain many redundant parts [17, 25, 36]. |
citation marker project authored |
5.3 Query Generation page 9 |
| M8 | We believe the current throughput is practical considering (1) GDBMS testing typically lasts for several months [ 14,20], and thus a sufficient number of test cases can be executed; and (2) setting up multiple Dinkel instances can significantly improve the test efficiency. |
citation marker project authored |
5.3 Query Generation page 10 |
| M9 | This comparison is reasonable and objective because: (1) none of the bugs found by Dinkel are marked as duplicated by developers, meaning that no approach found these bugs until Dinkel found them; and (2) all existing approaches have extensively tested Neo4j and RedisGraph [ 13,14,20,27,51], meaning that in these tw... |
citation marker project authored |
5.5 Comparison page 11 |
| M10 | GDsmith [ 13], GDBMeter [ 20], GraphGenie [ 14], and GAMERA [ 51] were published in 2023, and GRev [ 27] was published in 2024. |
citation marker project authored |
5.5 Comparison page 11 |
| M11 | GDBMS testing is an emerging research field, where several approaches [ 13,14,20,27,49,51] have been proposed. |
citation marker project authored |
5.5 Comparison page 12 |
| M12 | Several approaches [ 13,14,20,27,51] support GDBMSs using Cypher. |
citation marker project authored |
5.5 Comparison page 12 |
| M13 | GDBMeter [ 20] leverages query partitioning [ 38], which decomposes the predicate of a query and checks if the queries with the decomposed predicates produce consistent results with the original query. |
technique |
5.5 Comparison page 12 |
| M14 | GraphGenie [ 14] modifies the graph patterns used in a query and checks if the query with modified graph patterns satisfies the expected relationship (i. |
citation marker project authored |
5.5 Comparison page 12 |
| M15 | Compared to GDBMS testing, testing relational database management systems (RDBMSs) is more mature, where both query generation [ 11,16,22,42,50] and test-oracle construction [ 12,18,37–40,43] are well-researched. |
citation marker |
5.5 Comparison page 12 |
| M16 | To find logic bugs in RDBMSs, PQS [ 39] synthesizes customized queries that fetch specific rows of tables. |
technique |
5.5 Comparison page 12 |