💻 computer science

Graph-Aware Fuzzing for Graph Database Management Systems

GRAF 是一个针对图数据库管理系统的黑盒模糊测试框架，它利用大语言模型驱动的、具备图上下文感知的查询生成技术以及执行状态引导的变异技术，克服了现有测试方法的局限性，最终实现了显著更高的代码覆盖率，并在多个系统中发现了数十个此前未知的漏洞。

原作者： Yu Li, Qiang Hu, Yao Zhang, Junjie Wang, Hao Liu, Rui Wang, Yongqiang Lyu

发布于 2026-07-07

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Yu Li, Qiang Hu, Yao Zhang, Junjie Wang, Hao Liu, Rui Wang, Yongqiang Lyu

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，将图数据库（Graph Database）想象成一张巨大的、活生生的城市地图。与标准的电子表格（它像是一个僵化的行与列的网格）不同，这座城市是由节点（人、地点、事物）和连接它们的道路（关系）组成的。在这座城市里，你可以提出这样的问题：“找出所有住在巴黎且在面包店工作的鲍勃的朋友的朋友。”

为了测试这个城市的导航系统（数据库引擎）是否安全可靠，你需要向它发送数千个棘手的提问。如果系统崩溃或陷入死循环，那就是一个 Bug。

本文介绍了一种名为 GRAF 的新型“机器人测试员”，它是专门为破坏这些图数据库而设计的。以下是它的工作原理，通过简单的解释说明：

问题所在：为什么旧的测试工具会失败

之前的测试工具就像两种不同类型的笨拙游客：

“复读机”游客： 他们向五个不同的城市询问同一个问题，以观察答案是否一致。如果答案不匹配，他们就找到了 Bug。但这种方法仅在问题简单到可以同时在五个城市中提出的情况下才有效。它错过了当你在一个单一城市中提出一个非常复杂的问题时所发生的深层、诡异的崩溃。
“随机打字员”： 他们只是胡乱敲击按键来生成随机句子。但图数据库是非常挑剔的。如果你说“鲍勃认识爱丽丝”，但鲍勃和爱丽丝在城市中并不存在，系统会立即拒绝这个问题。这个随机打字员 99% 的时间都在问那些系统根本不会读取的问题。

解决方案：GRAF（聪明的游客）

GRAF 是一个“黑盒”测试器，这意味着它不需要看到数据库的内部代码。它只需发送问题并观察结果。它通过两个巧妙的技巧解决了上述两个主要问题：

1. “骨架与血肉”技巧（生成有效的提问）

想象一下你想盖一座房子。

旧方法： 你尝试通过向墙壁随机投掷砖块来建造房子。大多数情况下，墙会倒塌，因为砖块并不匹配。
GRAF 的方法：
- 步骤 A（骨架）： GRAF 使用一个超级智能的 AI（大语言模型）来绘制一份蓝图。这份蓝图在特定细节处留有空白，比如“在此插入 [姓名]”或“在此连接到 [街道]”。
- 步骤 B（血肉）： 在将蓝图发送给城市之前，GRAF 会查看实际的城市地图。它看到“鲍伯”存在，且“巴黎”也存在。它用符合该城市规则的真实、有效的数据填补空白。
- 结果： GRAF 发送的每个问题都保证在语法上是正确的，并且在逻辑上在该特定城市内是可能的。它绝不会在会被系统拒绝的问题上浪费时间。

2. “交通警察”技巧（引导探索）

一旦 GRAF 开始发送问题，它就会观察城市的反应。它利用三种信号来决定下一步该做什么：

时间： 问题花费了多长时间？
大小： 答案有多大？
状态： 系统是崩溃了、卡死了，还是正常结束了？

如何利用这些信息：

如果答案为空： GRAF 会认为：“这个问题太严格了。”它会放宽规则（例如，“也许鲍勃不必非要住在巴黎”）并再次尝试。
如果答案耗时过长（超时）： GRAF 会认为：“这个负担太重了。”它会停止让问题变得更深，而是尝试另一个角度，以避免陷入停滞。
如果系统崩溃： GRAF 会庆祝！它会保存那个特定的问题，对其进行微调，并尝试再次引发崩溃，以证明这是一个真实的 Bug。

结果：破坏系统

研究人员在六个流行的图数据库（如 Neo4j 和 Memgraph）上测试了 GRAF，并将其与现有的最佳测试工具进行了对比。

覆盖率： GRAF 探索的数据库内部逻辑比次优的测试工具多出 31% 到 41%。它找到了其他工具错过的深层、隐藏的角落。
发现的 Bug： 仅在 12 小时内，GRAF 就独立发现了 25 个独特的 Bug。而其他三个测试工具加起来仅发现了 6 个。
现实世界的影响： GRAF 发现了 34 个此前未知的 Bug。开发者确认了其中的 32 个，其中 23 个获得了官方的“CVE”编号（安全警报），这意味着它们严重到需要立即修复。

核心总结

GRAF 就像一位名侦探，他知道如何向城市的导航系统提出最令人困惑、最复杂的问题，同时又绝不会被拒绝。通过将问题的结构与其中的数据分离，并根据系统的反应进行监听，它能找到其他工具根本无法看到的崩溃和错误。

技术摘要：GRAF - 面向图数据库管理系统的图感知模糊测试

1. 问题陈述

图数据库管理系统（GDBMS）是管理互联数据的关键基础设施，然而与关系型数据库相比，其测试领域仍处于探索不足的状态。现有的测试方法主要依赖于差异测试（differential testing）和蜕变测试（metamorphic testing），这些方法依赖于结果一致性的预言（oracles）。这些方法将输入限制在可在不同引擎间进行比较或在语义上可转换的查询上，从而缩小了输入空间，使其仅限于定义良好的、能产生结果的查询。因此，针对引擎特定的运行时故障——如崩溃、内存损坏和资源耗尽——仍未得到充分探索。

开发专门针对 GDBMS 的模糊测试工具面临两个特定挑战：

生成有效且结构多样化的查询： 有效的 Cypher 查询必须满足复杂的、相互依赖的语法和语义约束（例如，变量作用域、类型兼容性和图模式一致性）。通用的字节级模糊测试会破坏语法，而基于语法的生成器生成的查询往往结构过于简单，无法触及深层的引擎逻辑。
在拓扑依赖执行下的探索引导： 传统的覆盖率反馈捕捉的是控制流，但无法捕捉拓扑依赖的数据流行为。图查询执行对中心节点（hubs）、环路和遍历深度高度敏感；微小的参数变化可能导致指数级的资源激增（例如，执行时间增加 320 倍），而不会改变控制流路径。现有方法缺乏有效的反馈机制来区分无意义的空结果、高成本遍历以及异常失败。

2. 方法论：GRAF 框架

作者提出了 GRAF，一个旨在解决上述挑战的黑盒、反馈驱动型模糊测试框架。GRAF 完全作为黑盒运行，依靠外部可见的结果而非传统的代码覆盖率来进行引导。

A. 图上下文感知查询生成

GRAF 将抽象查询结构与具体图数据解耦，以确保有效性的同时保持多样性。

骨架生成（Skeleton Generation）： 大语言模型（LLM）合成了一组参数化的 Cypher 骨架池，这些骨架具有多样化的子句组合和遍历模式。这些骨架使用标准化的标识符和占位符，但不包含具体数值。
级联依赖解析（Cascading Dependency Resolution）： GRAF 并非进行随机实例化，而是通过三个级联阶段根据活跃的图状态解析占位符：
1. 拓扑解析： 根据模式元数据采样节点标签和关系类型（例如，如果源标签是 Customer，则仅选择有效的传出关系，如 Order）。
2. 属性与数值解析： 绑定属性键并生成与实体类型兼容的具体数值（包括观测值、边界值或异常值）。
3. 全局参数对齐： 根据图的规模按比例调整全局参数（例如 LIMIT 或遍历边界），以防止立即发生超时。
  该过程在执行前消除了语法和语义违规，确保查询能够进入优化和执行逻辑。

B. 基于执行状态引导的查询变异

GRAF 使用动态反馈向量 $F = \langle t, |R|, s \rangle$ ，其中 $t$ 是执行时间， $|R|$ 是结果大小， $s$ 是系统状态。该反馈引导五种图特定的变异算子：

拓扑变异： 插入、删除或重新连接模式。
深度与容量变异： 调节路径边界和 LIMIT 配置。
谓词变异： 操作 WHERE 表达式以改变选择性。
子句插入： 注入流水线组件（例如 WITH、聚合操作）。
数值变异： 用边界值或异常值替换字面量。

反馈策略：

空结果： 如果查询快速返回且无结果，GRAF 会放宽谓词或调整拓扑，以确保数据物化。
高成本/超时： 对于接近超时的查询，GRAF 会惩罚深度扩张并倾向于有界的缩减，以避免无效探索。
异常终止： 崩溃或 OOM（内存溢出）会触发优先级分析和局部变异，以隔离故障原因。

3. 核心贡献

本文声称具有以下贡献：

GRAF 框架： 一个使用执行反馈而非代码覆盖率来测试多样化 GDBMS 引擎的黑盒模糊测试器。
解耦生成策略： 一种将抽象结构（通过 LLM 生成）与具体数据（通过级联依赖解析）分离的新颖方法，从而能够生成复杂的有效查询。
状态引导变异： 一种根据执行时间、结果大小和系统状态自适应调整算子的变异策略，旨在引导探索向深层引擎逻辑靠拢。
实证验证： 在六个流行的 GDBMS 上进行的广泛评估表明，其在覆盖率和漏洞发现方面具有显著提升。

4. 实验结果

作者在六个 GDBMS（Memgraph, FalkorDB, Neo4j, KuzuDB, NebulaGraph, 和 RedisGraph）上将 GRAF 与三个基准工具（Dinkel, BUZZBEE, 和 AFL++）进行了对比评估。

代码覆盖率： 在每个目标系统上，GRAF 相比最强的基准工具，始终将行覆盖率提高了 31.6% 至 41.1%。它覆盖了更多独特的代码行，特别是在深层实现区域，而基准工具大多集中在前端解析逻辑上。
查询有效性： GRAF 保持了 61.8% 至 76.7% 的有效查询率，显著高于 AFL++ (~~2%) 和 BUZZBEE (~~50-60%)，但略低于保守的 Dinkel。
漏洞发现：
- GRAF 在这六个系统中发现了 34 个此前未知的漏洞。
- 其中 32 个漏洞被开发者确认，23 个被分配了 CVE 编号。
- 在受控的 12 小时评估中，GRAF 触发了 25 个独特漏洞，而三个基准工具合计仅触发了 6 个。
- 这些漏洞涵盖了关键组件，包括模式匹配、路径扩展、聚合和事务管理，漏洞类型包括段错误（segmentation faults）、释放后使用（use-after-free）、栈溢出（stack overflows）和内存溢出（out-of-memory errors）。

5. 重要性与结论

本文断言，GRAF 证明了将查询结构与运行时上下文解耦以及利用外部执行反馈来测试复杂数据库引擎的有效性。通过解决图拓扑和语义约束的特定挑战，GRAF 成功绕过了前端验证，从而对后端执行逻辑进行压力测试。结果表明，传统的覆盖率指标对于图数据库是不充分的，执行状态信号（时间、大小、状态）对于引导模糊测试走向深层、潜在的缺陷至关重要。作者总结道，其方法提供了一种稳健的方法，用于发现差异测试和蜕变测试无法发现的运行时故障。