一句话：提出 QuDi，将 Gremlin 查询拆解为语义等价的原子遍历序列，以自动检测图数据库逻辑缺陷。
图数据库系统（GDBs）广泛使用 Gremlin 查询语言，开发者通过组合一系列 Gremlin API 形成复杂查询。但 GDB 的错误实现和优化会引入逻辑缺陷，导致查询返回错误结果，例如遗漏顶点。本文提出查询拆解技术 QuDi：给定 Gremlin 查询 Q，将其拆解为共享等价执行语义的原子图遍历序列 TList；若 Q 与 TList 的执行结果不同，则表明目标 GDB 存在逻辑缺陷。作者在六个流行 GDB 上评估 QuDi，发现 25 个逻辑缺陷，其中 10 个被开发者确认为此前未知的缺陷。
Graph Database Systems (GDBs) support efficiently storing and retrieving graph data, and have become a critical component in many important applications. Many widely-used GDBs utilize the Gremlin query language to create, modify, and retrieve data in graph databases, in which developers can assemble a sequence of Gremlin APIs to perform a complex query. However, incorrect implementations and optimizations of GDBs can introduce logic bugs, which can cause Gremlin queries to return incorrect query results, e.g., omitting vertices in a graph database. In this paper, we propose Query Di sassembling (QuDi), an effective testing technique to automatically detect logic bugs in Gremlin-based GDBs. Given a Gremlin query Q, QuDi disassembles Q into a sequence of atomic graph traversals TList, which shares the equivalent execution semantics with Q. If the execution results of Q and TList are different, a logic bug is revealed in the target GDB. We evaluate QuDi on six popular GDBs, and have found 25 logic bugs in these GDBs, 10 of which have been confirmed as previously-unknown bugs by GDB developers.
@inproceedings{paperbot8486,
title = {Testing Gremlin-Based Graph Database Systems via Query Disassembling},
author = {Yingying Zheng and Wensheng Dou and Lei Tang and Ziyu Cui and Yu Gao and Jiansen Song and Liang Xu and Jiaxin Zhu and Wei Wang and Jun Wei and Hua Zhong and Tao Huang},
booktitle = {ISSTA},
year = {2024},
doi = {10.1145/3650212.3680392}
}