Metamorphic testing of version control systems

Abstract

Currently, no approach exists to automatically and systematically test the implementation of version control systems (VCS). VCS are widely used in the software development industry, where a lot of people rely on these systems to perform as specified and not to lose any data. However, problems with the implementations of such systems are found frequently which causes risks and inconveniences to the users. The oracle problem renders traditional testing impractical. In this thesis, we present an approach to automatically test the implementation of VCS using metamorphic testing. Metamorphic testing is an approach to mitigate the oracle problem by splitting it up into smaller parts. Instead of knowing the expected behavior of a program for a specific input, this approach uses the knowledge of how a certain change of the program input will be reflected in its output. We develop such transformations of inputs of VCS and the corresponding relations of the outputs. Since this requires initial inputs to work with, we also develop a random input test generator. We combine these two components into an automated testing tool. As inputs, we use bash-scripts containing commands to interact with the VCS and the file system. As outputs, we use the files in the working directory after executing the input scripts. Additionally, we develop a test minimizer to reduce the number of commands in the inputs when a relation gets violated. This eases the manual analysis later. Since git is complex and currently the most popular VCS, it makes a good first target to test our approach. We find five real-world bugs in the implementation of git and archive a precision of 90.79%. Additionally, we are able to minimize the test inputs to 15 of the original size on average.

Derzeit gibt es keinen Ansatz, um Versionskontrollsysteme (VCS) systematisch und automatisiert zu testen. VCS sind weitverbreitet in der Softwareentwicklung, wo sich viele Leute darauf verlassen, dass diese Systeme wie beschrieben funktionieren und nicht zu Datenverlust führen. Dennoch werden immer wieder Fehler in den Implementierungen von VCS entdeckt, was Risiken und Unannehmlichkeiten für die Nutzer bedeutet. Aufgrund des Orakel-Problems ist konventionelles Testen dieser Systeme nicht praktikabel. In dieser Thesis stellen wir einen Ansatz zum Testen der Implementierungen der VCS mithilfe von metamorphischem Testen vor. Metamorphisches Testen vereinfacht das Orakel-Problem, indem das Problem in kleinere Teilprobleme aufgeteilt wird. Anstatt das erwartete Verhalten des Programms auf eine bestimmte Eingabe kennen zu müssen, wird bei diesem Ansatz das Wissen darüber verwendet, wie sich eine bestimmte Änderung der Eingabe auf die Ausgabe des Programms auswirkt. Wir entwickeln solche Transformationen für die Eingaben von VCS, sowie die erwarteten Beziehungen der Ausgaben. Da wir initiale Eingaben benötigen, um diese transformieren zu können, entwickeln wir auch einen Zufallseingaben-Generator. Ebenso entwickeln wir auch ein Verfahren, welches die Test-Eingaben minimiert, wenn eine Relation verletzt wird, um die manuelle Auswertung hinterher zu vereinfachen. Wir verwenden git, um unseren Ansatz zu testen, da es komplex und das derzeit meist genutzte VCS ist. Wir finden fünf Bugs in der Implementierung von git und erreichen eine Präzision von 90,70%. Zusätzlich haben wir die Test-Eingaben im Durchschnitt auf 15 der ursprünglichen Größe reduziert.