IT评测·应用市场-qidao123.com

标题: GDsmith：Detecting Bugs in Graph Database Engines 论文笔记 [打印本页]

作者: tsx81428 时间: 2024-12-26 07:27
标题: GDsmith：Detecting Bugs in Graph Database Engines 论文笔记
一、引言

图数据库引擎的重要性与检测漏洞的必要性：在大数据时代，图数据库引擎对链接数据的建模和处理效率高，被广泛应用于知识推理系统、推荐系统等多个领域。比方，Neo4j 作为市场向导者，被众多企业客户使用，包罗大部分《财富》100 强公司。然而，图数据库引擎的底层代码复杂，容易出现错误，检测其漏洞至关重要。比方，Neo4j 版本 4.3.10 有超过 684K 非注释行的 Java 代码，Memgraph 版本 2.1.1 有超过 103K 非注释行的 C/C++ 代码。此外，与有漏洞的图数据库引擎交互的应用程序可能会出现意外的故障行为，导致潜在风险。
GDsmith：首个用于测试图数据库引擎的黑盒方法：GDsmith 是首个用于测试图数据库引擎的黑盒方法，它办理了随机测试面临的语义有效性、非空结果和行为多样性挑战。为了办理这些挑战，GDsmith 采用了骨架天生和补全技能确保随机天生的 Cypher 查询满意语义要求，利用三种结构变异计谋增加返回非空结果的 Cypher 查询的概率，并根据属性键的先前频率动态选择属性键以提高天生的 Cypher 查询的行为多样性。我们的评估结果表明，GDsmith 在自动查询天生方面有效且高效，大大优于基线方法。GDsmith 乐成地在三个流行的开源图数据库引擎的发布版本上检测到 27 个先前未知的漏洞，并收到了开发者的积极反馈。

二、背景

1. 测试的图数据库引擎

Neo4j：Neo4j 是图数据库领域的市场向导者，是图数据库种别创造者，也是市场上摆设最广泛的图数据平台。它是一个高性能的图存储，具有成熟和妥当数据库所盼望的全部功能。
RedisGraph：RedisGraph 是首个使用稀疏矩阵表现毗邻矩阵并使用线性代数查询的图数据库。它是 Redis 的一个查询属性图数据库模块，通过将数据表现为稀疏矩阵，并利用 GraphBLAS 的功能，提供了一种快速且高效的存储、管理和处理图的方式。RedisGraph 支持 Cypher 查询语言，将用户提供的 Cypher 查询语句转换为对矩阵的利用，只需要几步简单的矩阵运算，就可以实现很复杂的图查询利用，速度提升了不止一个数目级。
Memgraph：Memgraph 是一个流式图应用平台，采用内存优先架构。它使现代应用程序开发职员可以轻松构建流式图应用程序，具备复制和流式数据处理功能，可应对不停增长的数据量，提供身份验证和授权机制，保障数据的安全，可在多种平台上安装，也有 Docker 镜像方便摆设，还提供了在线的 Playground，让用户可以在欣赏器中直接试用。

2. Cypher 语言

Cypher 是最广泛采用的、完全指定的、开放的图数据库查询语言。它是一种声明式查询语言，让用户只需表达要检索的数据，底层引擎完成任务，无需了解实现细节。Cypher 允许用户简单地表达要检索的数据，而无需理解数据库的底层实现。它可以轻松地表达复杂的数据库查询，而且是创建尺度图查询语言（GQL）的关键灵感泉源。此外，另有从 Cypher 到其他图查询语言的翻译工具。在每个 Cypher 查询中，子句相互链接，并在它们之间转达中心结果集。比方，一个 MATCH 子句中的匹配变量将成为下一个子句存在的上下文。
3. 历史漏洞统计

为了更好地了解图数据库引擎中的漏洞，作者分析了官方 Neo4j、RedisGraph 和 Memgraph GitHub 存储库中的问题和拉取请求。作者将带有漏洞标签的问题和拉取请求视为已陈诉的漏洞，因为这三个图数据库引擎的官方存储库恰好包含漏洞标签。经过统计，这些引擎中带有漏洞标签的问题和拉取请求约占全部问题和拉取请求的 15%。
作者起首按月份统计了 Neo4j、RedisGraph 和 Memgraph 中带有漏洞标签的问题和拉取请求的数目，并绘制了增长曲线。Neo4j、RedisGraph 和 Memgraph 分别有 920、218 和 5 个带有漏洞标签的问题。此外，Neo4j、RedisGraph 和 Memgraph 分别有 937、268 和 15 个带有漏洞标签的拉取请求。Neo4j 最早的问题出现在 2012 年 11 月，对应 Neo4j 版本 1.85。自发布以来，带有漏洞标签的问题数目渐渐增加。第一个带有漏洞标签的拉取请求出现在 2013 年 12 月，此后带有漏洞标签的拉取请求数目开始增长。拉取请求的增长趋势一直持续到 2018 年，之后没有新的漏洞标签添加。
然后，作者统计了有多少带有漏洞标签的问题包含 Cypher 查询。作者搜刮问题内容中的 Markdown 代码片段，并确定今世码片段包含特定的 Cypher 语法关键字（如 MATCH 和 UNWIND）时，代码片段包含 Cypher 查询。经过统计，Neo4j、RedisGraph 和 Memgraph 分别有 358、133 和 3 个带有漏洞标签的问题包含 Cypher 查询。这表明很多图数据库引擎中的漏洞可以通过执行 Cypher 查询触发。在全部已关闭的问题中，包含 Cypher 查询的问题的均匀漏洞存在时间为 192 天，而其他问题的均匀漏洞存在时间为 298 天（少 36%）。进一步分析发现，在 25% 的中位数上没有差异，但在 50% 和 75% 的中位数上分别少 48% 和 57%。这些结果表明，在问题中提供揭示漏洞的 Cypher 查询对于在调试过程中加快办理困难漏洞具有潜在的重要性。
三、方法

1. 总体算法

GDsmith 通过四步迭代天生测试输入，详细如下：

起首，GDsmith 随机天生数据库状态，并初始化设置变量。在每次迭代中，GDsmith 会先随机天生属性图模式，这一模式界说了标签、关系范例和属性。比方，GDsmith 会天生一个有限的标签聚集，为每个标签确定一个唯一的名称和一组属性。同时，也会天生有限的关系范例聚集，为每个关系范例确定一个唯一的名称和实用的标签对聚集。天生属性图模式有助于引导属性图和 Cypher 查询的有效天生。
接着，GDsmith 通过随机天生或变异的方式产生语义有效的 Cypher 查询。为了办理语义有效性挑战，GDsmith 采用了基于骨架的完成技能。详细来说，GDsmith 先随机天生一个 Cypher 骨架，这个骨架是由带有未实例化部分（如模式和表达式）的子句序列构成，每个未实例化部分用 “□” 符号表现。比方，对于一个特定的 Cypher 查询，其对应的骨架可能是 “MATCH □ WHERE □ RETURN □”。随机天生 Cypher 查询分为两步，起首随机天生骨架，然后添补骨架中的未实例化部分。在添补过程中，GDsmith 会计算并维护每个子句的上下文。上下文包罗局部环境和事实两方面信息。局部环境是指下一个子句中可用的变量聚集，对于不同范例的子句，局部环境的确定方式不同。比方，对于 MATCH 子句，局部环境包罗前一个子句的局部环境中的变量以及节点模式和关系模式中新界说的实体变量。事实则是从变量界说中网络的信息，包含每个变量的数据范例以及节点的标签约束和关系的范例约束等。基于丰富的语义信息，GDsmith 可以或许使天生的未实例化部分满意变量作用域正确性、利用数范例安全和属性键安全三个语义要求。
然后，GDsmith 在每个引擎实例上执行天生的查询。
最后，GDsmith 保存返回非空结果的 Cypher 查询，并利用属性键频率的反馈天生新的具有高行为多样性的 Cypher 查询。如果一个查询返回非空结果，GDsmith 会将其保存到查询池中，这些保存的查询将用于在后续阶段通过结构变异计谋天生新的查询，从而增加新变异查询返回非空结果的概率。同时，GDsmith 会根据属性键的先前频率动态选择属性键来完成新的骨架，以提高天生的 Cypher 查询的行为多样性。其目的是覆盖不同的属性值，从而提高随机天生查询的行为多样性。

2. 模式和图天生

GDsmith 起首随机天生属性图模式。属性图模式界说了标签、关系范例和属性。比方，为每个标签确定一个唯一的名称和一组属性，为每个关系范例确定一个唯一的名称和实用的标签对聚集。天生属性图模式有助于引导属性图和 Cypher 查询的有效天生。
然后，GDsmith 基于天生的属性图模式随机天生属性图，并将其插入到每个测试的引擎实例中。GDsmith 指定属性图中的节点和关系的数目，然后根据天生的属性图模式依次天生每个节点或关系中的属性值。天生属性图后，GDsmith 还会为全部引擎实例创建相同的随机索引。

3. 骨架及其完成

GDsmith 采用基于骨架的完成技能天生 Cypher 查询，以确保满意变量作用域正确性、利用数范例安全和属性键安全三个语义要求：

变量作用域正确性：一个变量只有在包含在子句的局部环境中时才华在该子句中被引用。
利用数范例安全：每个表达式的利用数范例必须满意表达式的范例要求，而且利用数的组合必须保证表达式的输出范例在运行时可推断。
属性键安全：从实体中获取的全部属性键在运行时必须存在于属性图模式中。

为了确保这三个语义要求，GDsmith 在添补未实例化部分时采用了特定的计谋。如果当前子句需要一个模式元组，GDsmith 会动态天生一系列模式。每个模式由实体变量描述的子图构建而成。起首，GDsmith 天生子图的形状，比方一个带有指向另一个节点的关系的节点。对于形状中所需的每个变量，GDsmith 要么选择前一个子句局部环境中已界说的变量，要么为其界说一个新变量。然后，GDsmith 随机为这些变量添加新标签或范例。最后，根据属性图模式和相关事实，GDsmith 随机为这些变量添加属性。
如果当前子句需要一个具有特定命据范例的表达式，GDsmith 使用自顶向下的计谋天生表达式。表达式是一个树结构，每个树节点是一个子表达式。对于需要子表达式的每个利用数，GDsmith 随机选择一个满意范例要求的表达式，并递归地天生整个子树。对于需要字面量值的每个利用数，GDsmith 随机天生所需范例的字面量值。对于需要变量引用的每个利用数，GDsmith 从上下文中搜刮具有所需范例的变量。如果找不到符合的变量，GDsmith 将扬弃当前子树并重新天生。表达式天生过程会一直持续，直到当前表达式树的全部利用数都被添补或到达最大深度。
在添补完一个子句中的全部未实例化部分后，GDsmith 会根据该子句的界说计算上下文，以指导下一个子句的完成。
4. 结构变异计谋

为了办理非空结果挑战，GDsmith 利用三种结构变异计谋增加天生返回非空结果的 Cypher 查询的概率：

DelayReturn 计谋：起首将子句序列末尾的 RETURN 子句改为 WITH 子句，然后天生一个新的子句序列并将其添加到末尾，形成一个完整的 Cypher 查询。在完成未实例化部分时，它采用与算法 2 相同的计谋，只是将原始序列末尾的上下文作为初始上下文。比方，对于一个选定的查询，经过此计谋处理后，可能会天生一个新的查询，这个新查询更有可能返回非空结果，相比于随机天生一个具有相同查询长度的新查询。
AdvanceReturn 计谋：随机选择原始 Cypher 查询中的一个 WITH 子句，并将其转换为 RETURN 子句，然后扬弃新创建的 RETURN 子句之后的全部子句。当用 RETURN 更换 WITH 时，如果 WITH 子句包含 WHERE 子句，将其删除。此计谋使变异后的查询返回原始查询的中心结果集，大大增加了获取非空结果的概率。
RemoveCondition 计谋：随机从 MATCH、OPTIONAL MATCH 或 WITH 子句中删除 WHERE 条件，本质上增加了获取非空结果的概率。

GDsmith 保存每个返回非空结果的天生查询，并将其用于在后续阶段通过这些结构变异计谋天生新的查询。同时，GDsmith 要求保存的查询中的子句数目在一个适当的范围内，以均衡查询的多样性和效率。
5. 行为多样性

为了办理行为多样性挑战，GDsmith 根据属性键的先前频率动态选择属性键，以提高天生的 Cypher 查询的行为多样性。GDsmith 维护一个属性键频率列表作为反馈。在每次天生属性图模式后，全部属性键的频率都被设置为零。当一个新查询在其子句中包含属性键并返回非空结果时，频率列表会自动更新。
属性键的选择概率公式为，此中是第个可用属性键的选择概率，是第个可用属性键的频率，是可用属性键的总数。这个公式表明，在从全部可用属性键列表中指定属性键以添补未实例化部分时，GDsmith 优先选择频率较低的属性键，以使每个属性键在返回非空结果的 Cypher 查询集中的出现可能性均匀化。其目的是覆盖不同的属性值，从而提高随机天生查询的行为多样性。
与传统的反馈引导随机测试方法不同，GDsmith 不使用代码覆盖率作为反馈，因为代码覆盖率在测试图数据库引擎时存在一些问题。起首，即使执行了大量不同的查询，代码覆盖率也可能很低，因为 GDsmith 只关注与数据中央的 Cypher 查询相关的引擎组件，其他组件如交互式控制台不是测试的对象。其次，GDsmith 希望成为一个黑盒方法，以增强其兼容性。如果图数据库引擎的源代码不可用或存在语言肴杂，很难进行代码插桩以获取代码覆盖率等运行时信息。
四、评估

1. 用五个指标评估 GDsmith 的有效性和效率，结果表明 GDsmith 大幅优于基线。

GDsmith 的有效性和效率通过五个指标进行评估，包罗语义有效性率、焦点语法覆盖率、非空结果率、图变异分数和错误检测效率。

语义有效性率：三种方法（GDsmith、GDsmith_m 和 GDsmith_f）的语义有效性率均为 100%，这表明 GDsmith 计划的骨架完成技能可以或许有效地满意语义要求，使天生的查询可以或许到达图数据库引擎的焦点部分。
焦点语法覆盖率：三种方法的焦点语法覆盖率都收敛到 98%，这意味着 GDsmith 在实现范围内没有丢失任何可能的子句序列和参数，可以或许覆盖多样的 Cypher 特征。
非空结果率：在不同查询长度下，GDsmith 可以或许比 GDsmith_m 多产生 24% 至 40% 的返回非空结果的 Cypher 查询，比 GDsmith_f 多产生 1% 至 5% 的返回非空结果的查询。这表明结构变异计谋对提高非空结果率贡献最大。
图变异分数：在天生 50 个图变异时，GDsmith 的图变异分数比 GDsmith_m 低 10%，但比 GDsmith_f 高 73%。这说明属性键频率的反馈有助于提高行为多样性，但结构变异计谋在肯定水平上断送了变异查询的一些行为多样性，以提高返回非空结果的概率。
错误检测效率：在 30 分钟内，GDsmith 天生了六个错误陈诉，淘汰为两个独特的错误结果漏洞和一个错误漏洞；GDsmith_m 天生了两个错误陈诉，仅为一个错误漏洞；GDsmith_f 天生了三个错误陈诉，包罗一个错误结果漏洞和一个错误漏洞。这表明结构变异计谋和属性键频率的反馈都有助于 GDsmith 在图数据库引擎中检测到更多的错误结果漏洞。

与基线方法（GDsmith_a）相比，GDsmith 在有效性和效率方面表现出色。GDsmith_a 天生的查询语义有效性率仅为 16%，且缺乏反馈指导，无法天生高质量的查询用于测试。而 GDsmith 可以或许有效地满意语义要求，增加返回非空结果的查询概率，提高天生查询的行为多样性，从而在检测图数据库引擎中的漏洞方面具有更高的有效性和效率。
2. 在三个流行的开源图数据库引擎中检测到 27 个先前未知的漏洞，得到了开发者的积极反馈。

GDsmith 在三个流行的开源图数据库引擎（Neo4j、RedisGraph 和 Memgraph）中检测到了 27 个先前未知的漏洞。此中，14 个漏洞已被相应引擎的开发者确认，7 个漏洞已被修复。

检测到的漏洞范例：GDsmith 检测到的漏洞包罗错误漏洞和错误结果漏洞。比方，在 Neo4j 版本 4.3.6 中，发现了一个由于 “OPTIONAL MATCH (n) MATCH (n) OPTIONAL MATCH (n)” 序列导致的错误漏洞；在 Neo4j 版本 4.3.10 中，发现了一个由于查询优化问题导致返回结果未按预期排序的错误结果漏洞；在 RedisGraph 版本 2.4.11 中，发现了一个由于 “MATCH (n) OPTIONAL MATCH (n) WHERE (arbitrary branches)” 序列错误地删除了节点 n，导致查询应返回 1 行但现实返回空结果集的错误结果漏洞；在 Memgraph 版本 2.1.1 中，发现了一个由于实现与 Cypher 语言尺度语义不同等，导致查询应返回 1 行但现实返回空结果集的错误结果漏洞。
开发者的反馈：在向相应的社区陈诉检测到的漏洞后，三个图数据库引擎的开发者给予了积极的反馈。Neo4j 的焦点开发者对 GDsmith 天生的查询表现感兴趣，并对其天生器表现好奇和赞赏；RedisGraph 的焦点开发者对 GDsmith 的结果感到惊讶，并表现希望在 GitHub 上分享该工具；Memgraph 的焦点开发者确认了漏洞的存在，并表现应该修复不同等的行为。这些反馈表明 GDsmith 检测到的漏洞对图数据库引擎至关重要，也证明白 GDsmith 在测试现实世界图数据库引擎方面的实用性和可以或许检测关键漏洞的本领。

五、结论

GDsmith 是首个用于检测图数据库引擎漏洞的方法，有效且实用，为图数据库引擎的测试提供了新的途径。未来可进一步改进和扩展该方法。

GDsmith 作为首个黑盒方法用于测试图数据库引擎，乐成地办理了随机测试面临的语义有效性、非空结果和行为多样性挑战。通过骨架天生和补全技能、结构变异计谋以及根据属性键频率动态选择属性键等创新方法，GDsmith 在自动查询天生方面表现出了高效性和有效性，大大优于基线方法。同时，GDsmith 在三个流行的开源图数据库引擎中检测到了 27 个先前未知的漏洞，并收到了开发者的积极反馈，证明白其在现实应用中的实用性。
然而，就像其他漏洞检测方法一样，GDsmith 也有进一步改进和扩展的空间。比方，可以借鉴其他领域的漏洞检测技能，如软件测试学术顶会中提到的基于机器学习的漏洞检测、大型语言模型在软件安全中的应用等热门研究方向，探索将这些技能应用于图数据库引擎漏洞检测的可能性。另外，还可以进一步提高 GDsmith 的自动化水平，淘汰人工干预，提高漏洞检测的效率和准确性。同时，也可以加强对不同范例图数据库引擎的兼容性测试，扩大其应用范围。
总之，GDsmith 为图数据库引擎的测试提供了一个新的出发点，未来可以通过不停改进和扩展，为图数据库引擎的安全性和稳定性提供更有力的保障。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)