White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Advanced Techniques for Search-Based Program Repair

Timperley, Christopher S (2017) Advanced Techniques for Search-Based Program Repair. PhD thesis, University of York.

This is the latest version of this item.

ctimperley-phd-thesis.pdf - Examined Thesis (PDF)
Available under License Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 UK: England & Wales.

Download (1643Kb) | Preview


Debugging and repairing software defects costs the global economy hundreds of billions of dollars annually, and accounts for as much as 50% of programmers' time. To tackle the burgeoning expense of repair, researchers have proposed the use of novel techniques to automatically localise and repair such defects. Collectively, these techniques are referred to as automated program repair. Despite promising, early results, recent studies have demonstrated that existing automated program repair techniques are considerably less effective than previously believed. Current approaches are limited either in terms of the number and kinds of bugs they can fix, the size of patches they can produce, or the programs to which they can be applied. To become economically viable, automated program repair needs to overcome all of these limitations. Search-based repair is the only approach to program repair which may be applied to any bug or program, without assuming the existence of formal specifications. Despite its generality, current search-based techniques are restricted; they are either efficient, or capable of fixing multiple-line bugs---no existing technique is both. Furthermore, most techniques rely on the assumption that the material necessary to craft a repair already exists within the faulty program. By using existing code to craft repairs, the size of the search space is vastly reduced, compared to generating code from scratch. However, recent results, which show that almost all repairs generated by a number of search-based techniques can be explained as deletion, lead us to question whether this assumption is valid. In this thesis, we identify the challenges facing search-based program repair, and demonstrate ways of tackling them. We explore if and how the knowledge of candidate patch evaluations can be used to locate the source of bugs. We use software repository mining techniques to discover the form of a better repair model capable of addressing a greater number of bugs. We conduct a theoretical and empirical analysis of existing search algorithms for repair, before demonstrating a more effective alternative, inspired by greedy algorithms. To ensure reproducibility, we propose and use a methodology for conducting high-quality automated program research. Finally, we assess our progress towards solving the challenges of search-based program repair, and reflect on the future of the field.

Item Type: Thesis (PhD)
Keywords: automated program repair; search-based software engineering; genetic improvement; fault localisation; software repository mining; GenProg; RepairBox;
Academic Units: The University of York > Computer Science (York)
Identification Number/EthosID: uk.bl.ethos.727341
Depositing User: Dr Christopher S Timperley
Date Deposited: 07 Nov 2017 13:29
Last Modified: 24 Jul 2018 15:23
URI: http://etheses.whiterose.ac.uk/id/eprint/18466

Available Versions of this Item

  • Advanced Techniques for Search-Based Program Repair. (deposited 07 Nov 2017 13:29) [Currently Displayed]

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)