From: 2024-01-17 11:15 to 12:00
Place: E:2116
Contact: birger [dot] swahn [at] cs [dot] lth [dot] se

One Computer Science MSc thesis to be presented on 17 January

Wednesday, 17 January there will be a master thesis presentation in Computer Science at Lund University, Faculty of Engineering.

The presentation will take place in E:2116.

Note to potential opponents: Register as an opponent to the presentation of your choice by sending an email to the examiner for that presentation (firstname.lastname@cs.lth.se. Do not forget to specify the presentation you register for! Note that the number of opponents may be limited (often to two), so you might be forced to choose another presentation if you register too late. Registrations are individual, just as the oppositions are! More instructions are found on this page.)

11:15-12:00 in E:2116

Presenters: Theodor Åstrand, Joel Bergstrand
Title: Randomly generating execution plans for bug detection in Neo4j
Examiner: Görel Hedin
Supervisors: Niklas Fors (LTH), Love Leifland (Neo4j)

In recent years the usage of Graph Database Management Systems(GDBMS) has increased in popularity for a large number of use cases, such as, search engine optimization and fraud detection. One of the most popular GDBMS is Neo4j. Neo4j is queried using Cypher, a query language developed by Neo4j. Before a Cypher query can be executed it is further processed and optimized within Neo4j into intermediate structures. The last structure is an execution plan, this can be executed and generates the result to be returned to the user. With the increasing use of GDBMS in many business critical applications the need for testing Neo4j and its competitors has grown in importance. One common practice for identifying bugs in a database system is the use of randomly generated data, known as fuzz testing. Previously, this has been done by randomly generating queries, and there are a number of tools currently available.

In this thesis, we propose a novel approach to fuzz testing GDBMS by randomly generating execution plans, an intermediate structure. Our testing tool utilizes differential testing between different Neo4j runtimes. This allows for it to identify incorrect result returned from one or more of the runtimes. These types of bugs are commonly referred to as logic bugs. The testing suite was able to identify 18 bugs within the Neo4j, of which 9 were logic bugs. This approach to fuzz testing has proven useful at identifying errors within the Neo4j runtimes which previously has received insufficient coverage by query fuzz testing. The approach proposed in this thesis can be applied to other database management systems that utilizes execution plans, not only graph based databases. The main drawbacks of this new approach is that it is not portable between different GDBMS as well as it requires access to the query processing source code.

Link to popular science summary: To be uploaded