一句话：提出单射/满射图查询变换（GQT），通过变异查询并检验结果集间的等价、子集或超集关系来自动检测图数据库的逻辑缺陷。
图数据库管理系统（GDBMS）在社交网络、推荐系统和程序分析等应用中广泛使用，但其逻辑缺陷会导致计算结果错误并影响上层应用。本文提出单射与满射图查询变换（GQT）：给定查询 Q，依据有向边集之间的单射与满射映射系统地构造变异查询 Q'，使两者的结果集要么语义等价，要么按变异方向互为子集或超集。当实际结果不满足这一预期关系时，即判定 GDBMS 中存在逻辑缺陷。作者将该方法实现为工具 GraphGenie，并在 6 个主流且成熟的 GDBMS 上进行评估，共发现 25 个此前未知的缺陷，其中包括 16 个逻辑缺陷、3 个内部错误和 6 个性能问题，表明该方法在检测 GDBMS 逻辑缺陷方面具有实用性与有效性。
Graph Database Management Systems (GDBMSs) store graphs as data. They are used naturally in applications such as social networks, recommendation systems and program analysis. However, they can be affected by logic bugs, which cause the GDBMSs to compute incorrect results and subsequently affect the applications relying on them. In this work, we propose injective and surjective Graph Query Transformation (GQT) to detect logic bugs in GDBMSs. Given a query Q, we derive a mutated query Q', so that either their result sets are: (i) semantically equivalent; or (ii) variant based on the mutation to be either a subset or superset of each other. When the expected relationship between the results does not hold, a logic bug in the GDBMS is detected. The key insight to mutate Q is that the graph pattern in graph queries enables systematic query transformations derived from injective and surjective mappings of the directed edge sets between Q and Q'. We implemented injective and surjective Graph Query Transformation (GQT) as a tool called GraphGenie and evaluated it on 6 popular and mature GDBMSs. GraphGenie has found 25 unknown bugs, comprising 16 logic bugs, 3 internal errors, and 6 performance issues. Our results demonstrate the practicality and effectiveness of GraphGenie in detecting logic bugs in GDBMSs which has the potential for improving the reliability of applications relying on these GDBMSs.
@inproceedings{paperbot11249,
title = {Detecting Logic Bugs in Graph Database Management Systems via Injective and Surjective Graph Query Transformation},
author = {Yuancheng Jiang and Jiahao Liu and Jinsheng Ba and Roland H. C. Yap and Zhenkai Liang and Manuel Rigger},
booktitle = {ICSE},
year = {2024},
doi = {10.1145/3597503.3623307}
}