The Remarkable Role of Similarity in Redundancy-based Program Repair

Recently, there have been original attempts to use the concept of "code similarity" in program repair, suggesting that similarity analysis has an important role in the repair process. However, there is no dedicated work to characterize and quantify the role of similarity in redundancy-based program repair, where the patch is composed from source code taken from somewhere else. This is where our paper makes a major contribution: we perform a deep and systematic analysis of the role of code similarity during the exploration of the repair search space. We define and set up a large-scale experiment based on four code similarity metrics that capture different similarities: character, token, semantic and structure similarity. Overall, we have computed 56 million similarity score over 15 million source code components. We show that with similarity analysis, at least 90% of search space can be ignored to find the correct patch. Code similarity is capable of ranking the correct repair ingredient first in 4 - 33 % of the considered cases.