GDBMeter

GDBMeter (Graph Database Metamorphic Tester) is a tool that automatically tests Graph Database Management Systems (GDBMS). It tries to find bugs that cause the GDBMS to fetch an incorrect result set.

Getting Started

Required Software:

• JDK 11
• Gradle 8.0.2 which we provide bundled with our source code
• The graph database you want to test (Neo4J and JanusGraph are both embedded into the JAR for ease of use)
  • We recommend testing RedisGraph via a Docker container

The following commands clone the repository, build a JAR file and start GDBMeter:

./gradlew clean shadowJar
cd build/libs
java -jar gdbmeter-*.jar -db neo4j -o partition -v

When running GDBMeter in verbose mode (-v) the queries that were executed are printed periodically. If GDBMeter does not find any bugs, it executes infinitely. To see all available options one can use the -h option.

Testing Approach

Our testing approach, called Predicate Partitioning, is based on the idea that we can partition a result set through a predicate into disjoint subsets. Combining these subsets should again give the complete original result set. This approach has been successfully applied to SQL databases and has been termed Ternary Logic Partitioning (TLP).

Supported GDBMS

GDBMS	Tested Version	Status	Description
Neo4J	5.1.0	Working	Reference implementation for other GDBMS. This implementation is based on the common Cypher logic.
RedisGraph	2.8.13	Working	This implementation is based on the common Cypher logic. Running this implementation will most likely uncover more unreported logic bugs.
JanusGraph	0.6.2	Working	Supports a (small) subset of the Gremlin query language. Currently, only the inmemory version with the lucene index backend are tested.

To test the RedisGraph database, an external server has to be started. To do this we recommend the following docker command which starts the server in the appropriate version:

docker run -p 6379:6379 -it --rm redis/redis-stack-server:6.2.2-v5

Using GDBMeter

Logs

GDBMeter generates logs in the logs folder. Every individual query is logged and for JanusGraph the schema is serialized as part of the log. If GDBMeter finds a bug, the log can be used to reproduce the bug.

Reproducing a Bug

To reproduce a bug simply find the last logged message of the form Finished iteration, closing database. And remove everything above it. This leaves only the queries that were run during the latest iteration. Place these in a file called replay in the logs folder. Re-running GDBMeter with the option --replay or -r then runs only those queries that are present in replay. At this point a manual reduction is necessary. Usually, the best way to do this is to remove part of the queries and see if the bug still occurs. Continue this until a minimal example is left. We plan on adding support for an automatic reduction test based on Delta Debugging.

Found Bugs

In case you found a bug using GDBMeter we would appreciate it if you mention our project when reporting the bug. We would, of course, be very happy if you use GDBMeter or if you would like to contribute.

Alternative Testing Approaches

GDBMeter also supports other, less successful, testing approaches:

Name	Description
Empty Result	A query that has an empty result set should return an empty result whenever no new nodes are added.
Non-Empty Result	A query that has a non-empty result set should remain unchanged as long as we don't remove any nodes of said result set.
Refinement	Matching on (a subset of) the exact values of a previous query should return (a superset of) the previous result set.