Testing Graph Database Systems with Graph-State Persistence Oracle

Shuang Liu, Junhao Lan, Xiaoning Du, Jiyuan Li, Wei Lu, Jiajun Jiang, Xiaoyong Du. 2024. International Symposium on Software Testing and Analysis.

Read the paper · doi:10.1145/3650212.3680311

What this paper does with SQLancer

TLP reaches this paper as the technique GDBMeter carried into graph databases -- the paper describes GDBMeter as the first metamorphic approach to apply TLP from relational DBMSs to graph DBMSs, finding 40 previously unknown bugs, and notes elsewhere that TLP was first proposed for relational systems and has since been applied to graph ones. PQS and NoREC are described alongside as the relational approaches, with PQS called general and highly effective. GraspDB's own baselines are GDsmith and GraphGenie rather than GDBMeter, on the stated grounds that GraphGenie has shown state-of-the-art performance and outperforms GDBMeter. GraspDB tests graph database systems with a graph-state persistence oracle: mutation rules transform a query in ways whose effect on the graph state is known, so the expected relationship between the two results is known even when the result sets differ. That distinguishes it from the existing metamorphic graph testers, whose oracles treat only identical result sets as correct and are therefore confined to transformations that preserve results exactly. Written by claude-opus-5 from the 14 places this paper refers to SQLancer. The quotations below are the paper's own words, stored verbatim when the text was extracted.

How it was classified

uses infrastructure — no

Nothing describes reuse of SQLancer's code; GraspDB implements its own mutation rules and oracle.

extends technique — no

The graph-state persistence oracle admits transformations whose result sets differ, which M5 gives as the departure from the existing approaches rather than a development of TLP.

compares with — no

M6 states the comparison is with GDsmith and GraphGenie, and M7 explains GDBMeter was left out because GraphGenie outperforms it. Neither TLP nor a TLP-based tool is run against GraspDB.

describes as state of the art — yes

M12 calls PQS a general and highly-effective approach to finding bugs in DBMSs. The state-of-the-art claim in M7 attaches to GraphGenie, not to a SQLancer technique.

(PQS) isageneralandhighly-eﬀectiveapproachto/f_indingbugsinDBMS. M12 · 5.5 Threatsto Validity · page 11

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
21	Yuancheng Jiang, Jiahao Liu, Jinsheng Ba, Roland Hock Chuan Yap, Zhenkai Liang,andManuel Rigger.2023. Detecting LogicBugsin GraphDatabaseManagementSystemsviaInjectiveandSurjectiveGraphQueryTransformation.In 2024IEEE/A...	project authored
29	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
30	Manuel Rigger and Zhendong Su. 2020. Finding bugs in database systems via querypartitioning. ProceedingsoftheACMonProgrammingLanguages 4,OOPSLA(2020), 1–30. https://doi.org/10.1145/3428279	sqlancer publication · TLP
31	Manuel Rigger and Zhendong Su. 2020. Testing database engines via pivoted query synthesis. In 14th USENIX Symposium on Operating Systems Design and Implementation(OSDI 20). 667–682. https://doi.org/10.5555/3488766.348...	sqlancer publication · PQS

Every place it refers to SQLancer (14)

14 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	Recognizing this challenge, the software testing community has devoted increasing attention to uncovering bugsin DBMS, with a particular focus on GDBMSs [ 20–22,41].	citation marker project authored background	1 Introduction page 2
M2	As a countermeasure, diﬀerential testing [ 20,41] and metamorphic testing [21,22,25,42] play an crucial role in existing works on GDBMStesting.	citation marker project authored background	1 Introduction page 2
M3	Failing to carefullyverifywhethertwoimplementationsadheretothesame speci/f_ication alsoresult infalse alarms [ 21].	citation marker project authored background	1 Introduction page 2
M4	In contrast, metamorphic testing approaches oﬀer more precise oracles for testing GDBMSs, and a body of works surge in this line, including GDBMeter [ 22], GraphGenie [ 21], and GRev [ 25].	citation marker project authored background	1 Introduction page 2
M5	Note that diﬀerent from existing approaches on testing GDBMS [ 21,25], where only identical result setsareregardedascorrect,ourmutationrulesmaygeneratequery pairswhichresultindiﬀerentresultsets(e.	citation marker project authored motivation	4.3 Oracle page 7
M6	We compare GraspDB with GDSmith [ 20] and GraphGenie[21].	citation marker project authored baseline	5.1 EvaluationSetup page 7
M7	GraphGeniehasshownstate-of-the-artperformanceindetectingbugs in GDBMS [ 21]and outperformsother metamorphic testingapproachessuchas GDBMeter[ 22].	citation marker project authored background	5.1 EvaluationSetup page 8
M8	This is a common limitation for diﬀerential testing approaches andsimilar /f_indings is also reported by GraphGenie [ 21].	citation marker project authored background	5.4.1 DetectedUniqueBugs. Table7showsthecomparisonresults page 9
M9	GDBMeter [ 22] is the /f_irst metamorphic testing approach which applied the TLP [ 30] from relational DBMS to graph DBMS and found 40 unique, previously unknown bugs.	technique definition	5.5 Threatsto Validity page 11
M10	GraphGenie [ 21] proposes injective and surjective Graph Query Transformation (GQT) to detect logic bugs.	citation marker project authored definition	5.5 Threatsto Validity page 11
M11	Ternary Logic Partitioning (TLP) [30], a metamorphic testing approach /f_irst proposed for testing RDBMSs,has alsobeenappliedtotest GDBMS[ 22].	technique definition	5.5 Threatsto Validity page 11
M12	(PQS) isageneralandhighly-eﬀectiveapproachto/f_indingbugsinDBMS.	technique state of the art	5.5 Threatsto Validity page 11
M13	The core idea of PQS [ 31] is to automatically synthesize queries which guarantees to fetch a speci/f_ic, randomly selected row, called the pivot row.	technique definition	5.5 Threatsto Validity page 11
M14	Non-optimizing Reference Engine Construction (NoREC) [ 29] is another widely-known metamorphic testing approach to test RDBMS.	technique definition	5.5 Threatsto Validity page 11

This page is rendered from _data/papers/paper_doi_10_1145_3650212_3680311.json, extracted from supplied pdf. 12 pages, 42 references parsed.