Patching Patches through Genetic Search

Printer-friendly version
  • Interest in programming languages
  • Interest in search-based software engineering techniques, like genetic search
Open-source projects are often forked or branched, which allows developers to freely experiment with changing the project's code without affecting the original project.
However, it frequently occurs that a change in one fork/branch of the project should be carried over to other versions as well. For instance, a patch that solves a bug or adds a feature in one branch should also be applied to the other branches of the project.

Currently, patches have to be ported manually, which is a tedious and error-prone process. It requires investigating how the patch will change the project, but also investigating how the originating variant of the project differs from the target variant to which the patch should be adapted. Tool support is therefore in order.

Goal & Research Activities: 

The goal of this thesis is to investigate a tool that will recommend the modifications that a patch requires in order to be ported to the target variant of the system. We will formulate the problem as a genetic search algorithm that explores modifications to the patch such that it becomes applicable to the target variant.
Genetic search algorithms mimic evolutionary processes in nature: the search starts from an initial population of individuals, patches in our case, which are randomly mutated until there is one individual that scores well on a fitness function.

Your research will focus on a) devising and evaluating potential fitness functions (which compute to what extent a patch has been successfully) ported and b) devising and evaluating a set of potential patch mutation operations (e.g.., renaming methods referred to in the patch).
The patches themselves will be executed by the Ekeko/X tool, which has been implemented in Clojure. Ekeko/X is a program search and transformation tool for Java projects, where transformations/patches are specified in terms of source code templates. As a starting point, we have already employed a genetic search algorithm in Ekeko/X to tackle the problem of automatically generalizing multiple code snippets into one code template.