一句话：提出首个面向 Cypher 图数据库引擎的随机测试方法，通过图引导和数据引导生成复杂查询以检测错误结果缺陷。
图数据库引擎在关联数据处理中应用广泛，其质量保障需要自动测试生成，但随机测试难以生成复杂属性图与查询，导致查询结果为空，难以发现错误结果类缺陷。本文提出 GDsmith，首个面向 Cypher 图数据库引擎的测试方法，确保随机生成的查询满足语义要求，并引入图引导的复杂模式组合生成与数据引导的复杂条件生成两项技术，提高生成非空结果复杂查询的概率。评估表明，GDsmith 能高效生成可返回非空结果的复杂查询，显著优于基线；在三个流行开源图数据库引擎的发布版本上成功检测到 28 个缺陷，并获得开发者积极反馈。
Graph database engines stand out in the era of big data for their efficiency of modeling and processing linked data. To assure high quality of graph database engines, it is highly critical to conduct automatic test generation for graph database engines, e.g., random test generation, the most commonly adopted approach in practice. However, random test generation faces the challenge of generating complex inputs (i.e., property graphs and queries) for producing non-empty query results; generating such type of inputs is important especially for detecting wrong-result bugs. To address this challenge, in this paper, we propose GDsmith, the first approach for testing Cypher graph database engines. GDsmith ensures that each randomly generated query satisfies the semantic requirements. To increase the probability of producing complex queries that return non-empty results, GDsmith includes two new techniques: graph-guided generation of complex pattern combinations and data-guided generation of complex conditions. Our evaluation results demonstrate that GDsmith is effective and efficient for producing complex queries that return non-empty results for bug detection, and substantially outperforms the baselines. GDsmith successfully detects 28 bugs on the released versions of three highly popular open-source graph database engines and receives positive feedback from their developers.
@inproceedings{paperbot8053,
title = {GDsmith: Detecting Bugs in Cypher Graph Database Engines},
author = {Ziyue Hua and Wei Lin and Luyao Ren and Zongyang Li and Lu Zhang and Wenpin Jiao and Tao Xie},
booktitle = {ISSTA},
year = {2023},
doi = {10.1145/3597926.3598046}
}