为了有效地解决基于Gremlin的GDB中发现的逻辑错误，我们提出了两个特定的挑战。首先，为了生成语法正确且有效的Gremlin查询，该查询能够以高概率返回非空查询结果，我们采用了基于模型的查询生成方法。具体来说，我们总结了不同遍历类型的Gremlin遍历API。然后，我们提出了一个Gremlin遍历模型，该模型表达了不同遍历API之间的转换，以生成正确有效的Gremlin查询。第二，为了从不同的GDB中获得统一的查询结果，我们使用数据映射方法来获得不同GDB中的统一查询结果。因此，我们的方法可以将查询结果与不同GDB返回的不同格式进行比较。
一、方法
在本文中，我们提出了一种随机差分测试方法Grand，用于自动查找基于Gremlin的GDB中的逻辑错误。图5显示了Grand的概述。Grand包括三个阶段，即图形数据库生成、查询生成和GDB的差异测试。在图数据库生成阶段，Grand 首先随机生成图模式以定义顶点和边的类型，包括图数据库中顶点和边的标签和属性(1). 然后，可以根据生成的图模式随机生成详细的顶点和边(2). 生成的数据库将写入目标GDB(3). 在Gremlin查询生成阶段，我们使用基于模型的查询生成方法来生成语法正确和有效的Gremlin请求。具体来说，我们首先为Gremlin API构建了一个遍历模型（4), 然后基于构造的遍历模型和生成的图数据库生成Gremlin查询(5). 最后，Grand执行生成的Gremlin查询(6)并通过差异测试验证查询结果。详细地说，对于每个目标GDB，每个查询的结果将被记录，然后在映射信息(7)的帮助下被转换为统一查询结果. 然后，Grand检查这些未发现的结果，以确定是否存在差异(8).如果某些GDB表现出不同的输出，则可能会发现潜在的错误。
Grand为目标GDB生成随机数据库状态，即图模式和图数据，用于构造Gremlin查询。
图形架构生成。图模式定义标记属性图中的顶点类型和边类型。顶点包含一个标签和一组属性。设verType=<label，property*>表示顶点类型，其中label和property*分别表示其标签名称和属性类型。边包含输入顶点、输出顶点、标签和一组属性。让edgeType=<IntType、outType、label、property∗ > 表示边类型，其中IntType和outType表示输入和输出顶点的类型，以及label和property∗ 分别表示标签名称和属性类型。每个属性都包含属性名称及其值类型。让property=<name，type>表示属性类型，其中name和type分别表示属性名称及其数据类型。
我们通过以下算法生成一组顶点类型VTSet。对于每个顶点类型，我们首先随机生成其标签名称，然后生成一组属性类型。对于每个属性类型，我们从整数、字符串、双精度、布尔、浮点和长整型中分配一个随机数据类型。请注意，我们要求所有顶点类型都具有不同的标签名称，并且顶点类型中的所有属性类型具有不同的属性名称，但不同的顶点类型可能包含相同的属性类型。然后，我们通过以下算法生成一组边缘类型ETSet。为了生成边类型，我们首先从VTSet中随机选择两种顶点类型，分别作为其输入顶点和输出顶点。然后，我们使用与顶点类型生成相同的方法生成其标签名称和属性类型。请注意，我们要求所有边类型具有不同的标签名称，并且边类型中的所有特性类型具有不同特性名称，但不同的边类型可能包含相同的特性类型。
图形数据生成。根据生成的图形模式，Grand进一步生成可存储在GDB中的图形数据。基本上，我们随机生成一些符合图模式的顶点和边。然后，这些生成的顶点和边被写入GDB。算法1说明了如何生成顶点和边
对于顶点生成（第1-8行），我们首先从上面生成的顶点类型VTSet中随机获得顶点类型verType。我们根据顶点类型verType生成顶点顶点。注意，我们随机选择verType属性类型的子集，并生成verType属性（第5-6行）。这样，我们可以创建缺少某些属性的顶点。对于每个选定属性，我们根据其数据类型随机生成其值（第23行）。对于边缘生成（第9-18行），我们fjrst从上面生成的边缘类型ETSet中随机获取边缘类型edgeType。我们根据边缘类型edgeType生成边缘边缘。边生成的属性与顶点生成的属性相同。对于edge edge的传入/传出顶点，我们随机选择一个符合边的传入/传出顶点类型的顶点（第15-16行）。请注意，对于任何两个顶点，我们只添加一条具有相同类型的边。
注意，图数据库中顶点类型、边类型、属性类型、顶点和边的最大数量可以由GDB测试人员指定。在我们的实验中，我们为图形数据库生成最多10个顶点类型、20个边类型、20种属性类型、100个顶点和200条边。
1.2 基于模型的查询生成
随机查询生成是测试数据库的常用方法。然而，GDB测试的有效性在很大程度上依赖于查询生成的质量。Gremlin具有灵活的编程接口，它由一系列（可能嵌套的）Gremlin API调用组成，这些调用作用于图形遍历源q. 尽管我们可以使用自动化工具（例如，JCrasher）在Gremlin API中提取语法约束，但基于Gremlin api语法的完全随机的Gremlin查询生成可能会导致两个问题。首先，我们可以很容易地生成语法正确但无意义的查询，例如g.V().V().V()。第二，从Gremlin语法，我们无法知道Gremlin API及其参数的语义。例如在g.V().outE('read')，我们无法知道outE（）的参数应该是一个标签。如果没有这些语义，几乎所有生成的Gremlin查询都返回空结果，这不能用于在差异测试中比较返回结果。这两个问题会极大地影响GDB测试的有效性。为了解决上述两个问题，我们首先在Gremlin中构造一个遍历模型，该模型可以准确理解Gremlin API及其语义。基于这种遍历模型，Grand可以正确链接Gremlin API，并生成语法正确且有意义的查询。此外，Grand可以利用这些语义并设计各种策略来生成有效的Gremlin查询，它可以以高概率返回非空查询结果。注意，我们只关注用于查询生成的Gremlin查询API，而忽略了用于构建和更新图形数据库的更新API。
1.2.1、Gremlin中的遍历模型
Gremlin查询由一系列Gremlin API调用组成，这些调用正确地链接在一起。然而，在如何链接Gremlin API方面存在限制。通常，查询中的Gremlin API的输入类型应该与其之前的GremlinAPI的输出类型相匹配。否则，Gremlin查询将是非法的。
为了构造语法正确且有意义的Gremlin查询，我们需要为Gremlin API构建精确的遍历模型。通过仔细研究Gremlin API，我们构建了一个遍历模型来表示Gremlin查询API之间的合法转换，如图6所示。我们的遍历模型包含三种类型的实体（即Vertex, Edge, 和Value), 三种类型的操作（即Filter, Predicate, 和Aggregate), 和Constant. 图6正式表示了实体的转换和详细的Gremlin API。基于这种遍历模型，可以很容易地遵循相邻Gremlin API之间的合法转换。
1.2.2查询生成
基于上述遍历模型，我们首先生成语法正确的Gremlin查询，然后在生成的Gremlin查询中生成参数值。
查询语句构造。在第3.2.1节中的遍历模型的指导下，我们逐步迭代生成语法正确的Gremlin查询。算法2概述了该生成过程。最初，将query设置为一个小图遍历源g（第1行），并将前一个遍历步骤preStep初始化为开始，即遍历源g，第2行。Grand随机选择下一个Gremlin步骤，直到达到最大查询长度MaxLength或满足Exit条件（例如，步骤类型为常数值）（第4-21行）。注意，根据我们的遍历模型，选择的下一步必须与preStep兼容。新生成的步骤被添加到query的末尾。
我们进一步使用算法3来引入Filter步骤的生成。Grand可以在图6中创建各种Filter操作。我们首先在遍历模型中随机选择一个Filter操作（第2行）。在该算法中，我们仅使用HasPredicate来解释如何生成HasPredicate Filter步骤（第3-11行）。可以类似地生成其他过滤步骤。如果输入类型为顶点，则从生成的顶点属性（第4-5行）。否则，随机选择边缘属性（第6-7行）。根据所选属性的数据类型，我们创建一个谓词操作（第9行）predicate. 现在，我们可以根据属性名创建一个属性HasPredicate包括p.name和predicate（第10行）。最后，我们将filter的类型设置为其上一步的类型（第11行）。因此，算法2可以根据filter的类型进一步生成以下步骤。
为Gremlin API生成参数值。一些Gremlin API需要某些参数，我们采用两种策略来生成这些参数值。首先，我们根据图数据库内容随机选择值，以增加返回非空结果的概率。其次，我们使用随机函数根据常量类型生成参数值。
Gremlin查询生成的示例。如图7所示，算法2随机生成三个遍历步骤，例如映射步骤(V()在1中), Filter步骤(where()在2), 和一个property步骤(values()在(6). 特别是，筛选步骤包括一个嵌套的子查询，它由属性API组成(values()在3) 和Filter API(is()在4). 由于映射步骤的输出是顶点（1），Filter步骤（2）的嵌套子查询中的属性名称, 从生成的顶点属性中随机选择，或使用我们的随机函数随机创建。此外，谓词API的属性值(eq()在5) 以及 Property API(values()在6) 可以按照相同的方式生成
1.3 GDB的差异测试
我们使用差异测试来检测GDB中的逻辑错误。具体来说，我们首先将相同的图形数据写入一组目标GDB，然后对它们执行相同的Gremlin查询。通过比较不同GDB的返回结果，我们将差异识别为这些GDB中的潜在缺陷。Gremlin查询的返回结果可以是一个值或顶点、边或属性的列表。如果返回的结果是一个值或属性列表，则比较不同GDB的值或属性是很简单的。当查询结果是顶点或边的列表时，来自不同GDB的返回结果的格式可能不同。这是因为在不同的GDB中使用不同的ID生成策略。在图8所示的差异测试中需要5个步骤, Grand 首先在目标GDB中执行它(1), 并获得查询结果。然后，对于每个GDB，Grand提取查询结果中每个顶点或边的ID，以获得表示查询结果的实际顶点ID或边ID的列表(2). 例如，如图8所示，Grand获得JanuGraph的顶点ID列表[415241364216]。接下来，根据映射表(3), Grand将实际查询结果转换为统一查询结果（4）. 最后，Grand检查目标GDB的统一查询结果是否相同(5). 如果相同，返回True，否则，返回False；
二、实验
Grand在将图形写入目标GDB之前建立与目标GDB的连接。对于Neo4j、OrientDB、JanusGraph、TinkerGraph和ArcadeDB，Grand使用GraphTraversalSource远程连接GDB服务器，调用GraphTraverSource提供的API直接将每个顶点和边写入GDB并附加属性. 之后Grand使用Gremlin客户端提交生成的查询并获得查询结果.
三、评价
为了证明Grand的有效性，我们在六个广泛使用的GDB上评估Grand，并检测其中的真实逻辑错误
3.1 方法论
GDB的目标。我们在六个GDB上评估Grand，即Neo4j、OrientDB、JanusGraph、HugeGraph、TinkerGraph和ArcadeDB。表1显示了图DBMS的数据库引擎排名、GitHub启动和初始发布日期。我们可以看到这一点它们是最流行和最广泛使用的GDB之一。
测试方法。我们使用脚本来确认测试相关参数，例如生成的查询数（在我们的实验中为1000），以及生成相关参数的图形数据库，即每个查询的最大长度（在我们实验中为10），顶点类型、边类型、顶点和边的最大数量（分别为10、20、100、200）。我们配置Grand运行15轮。在每一轮开始时，Grand 首先随机为目标GDB构建测试图数据库，然后对目标GDB应用1000个随机生成的Gremlin查询，以执行差异测试。每个报告的差异都记录为潜在的逻辑错误。对于Grand报告的每个错误，我们手动复制并分析它，以验证它是否是真正的逻辑错误。具体而言，需要以下三个步骤。首先，Grand可能会生成一个复杂的查询来揭示差异，这使得识别其根本原因变得非常困难。因此，我们手动将查询简化为一个简单的查询，这可以触发相同的差异。
第二，Grand中的差异无法区分哪些GDB有问题。因此，我们手动调查差异中查询的预期结果，然后确定哪些GDB有缺陷。第三，Grand报告同一错误的不同差异。
3.2 总体错误检查
我们获得了709个（每轮47个）差异，这可能是潜在的错误。我们仔细复制和分析这些709个差异，并确认所有这些都是真实的差异。然而，经过深入分析，我们发现一些差异是由相同的错误引起的。在仔细分析709个差异之后，我们在六个测试的基于Gremlin的GDB中获得了21个逻辑错误。表2显示了我们发现的逻辑错误的统计数据。我们已经将这些错误提交给GitHub上的相应社区。在撰写本文时，开发人员已经确认了18个错误，所有这些都是以前未知的错误。开发人员已经修复了七个错误。这21个错误对这些GDB造成了严重后果。其中，18个错误返回了有效查询的意外异常，而它们不应该返回。在这种情况下，用户无法正确获得预期结果。请注意，所有这些错误都返回常用的异常，例如，IllegalArgumentException、NumberFormatException，NoIndexException和IllegalStateException。这些异常也可以通过无效查询返回。其余3个错误可能导致错误的查询结果。在下面，我们将解释在每个GDB中发现的这些错误。
