  Graph database engines stand out in the era of big data for their efficiency
of modeling and processing linked data. There is a strong need of testing graph
database engines. However, random testing, the most practical way of automated
test generation, faces the challenges of semantic validity, non-empty result,
and behavior diversity to detect bugs in graph database engines. To address
these challenges, in this paper, we propose GDsmith, the first black-box
approach for testing graph database engines. It ensures that each randomly
generated Cypher query satisfies the semantic requirements via skeleton
generation and completion. GDsmith includes our technique to increase the
probability of producing Cypher queries that return non-empty results by
leveraging three types of structural mutation strategies. GDsmith also includes
our technique to improve the behavior diversity of the generated Cypher queries
by selecting property keys according to their previous frequencies when
generating new queries. Our evaluation results demonstrate that GDsmith is
effective and efficient for automated query generation and substantially
outperforms the baseline. GDsmith successfully detects 27 previously unknown
bugs on the released versions of three popular open-source graph database
engines and receive positive feedback from their developers.
