- author = "Alexandru Marginean",
- title = "Automated Software Transplantation",
- school = "University College London",
- year = "2021",
- address = "UK",
- month = "8 " # nov,
- note = "{ACM SIGEVO Award for the best dissertation of the year}",
- keywords = "genetic algorithms, genetic programming, genetic improvement, SBSE, Autotransplantation, Automated program repair, APR, SAPFIX, muSCALPEL",
-
URL = "
https://discovery.ucl.ac.uk/id/eprint/10137954/",
-
URL = "
https://discovery.ucl.ac.uk/id/eprint/10137954/1/Marginean_10137954_thesis_redacted.pdf",
- size = "240 pages",
-
abstract = "Automated program repair has excited researchers for
more than a decade, yet it has yet to find full scale
deployment in industry. We report our experience with
SAPFIX: the first deployment of automated end-to-end
fault fixing, from test case design through to deployed
repairs in production code. We have used SAPFIX at
Facebook to repair 6 production systems, each
consisting of tens of millions of lines of code, and
which are collectively used by hundreds of millions of
people worldwide. In its first three months of
operation,SAPFIX produced 55 repair candidates for 57
crashes reported to SAPFIX, of which 27 have been deem
as correct by developers and 14 have been landed into
production automatically by SAPFIX. SAPFIX has thus
demonstrated the potential of the search-based repair
research agenda by deploying, to hundreds of millions
of users world wide, software systems that have been
automatically tested and repaired.
Automated software transplantation (autotransplantation) is a form of automated software engineering, where we use search based software engineering to be able to automatically move a functionality of interest from a donor program that implements it into a host program that lacks it. Autotransplantation is a kind of automated program repair where we repair the host program by augmenting it with the missing functionality. Automated software transplantation would open many exciting avenues for software development: suppose we could auto-transplant code from one system into another, entirely unrelated, system, potentially written in a different programming language.
Being able to do so might greatly enhance the software engineering practice, while reducing the costs. Automated software transplantation manifests in two different flavours: monolingual, when the languages of the host and donor programs is the same, or multilingual when the languages differ. This thesis introduces a theory of automated software transplantation, and two algorithms implemented in two tools that achieve this: uSCALPEL for monolingual software transplantation and rSCALPEL for multilingual software transplantation. Leveraging lightweight annotation, program analysis identifies an organ (interesting behaviour to transplant); testing validates that the organ exhibits the desired behavior during its extraction and after its implantation into a host.
We report encouraging results: in 14 of 17 monolingual transplantation experiments involving 6 donors and 4 hosts, popular real-world systems, we successfully autotransplanted 6 new functionalities; and in 10 out of 10 multlingual transplantation experiments involving 10 donors and 10 hosts, popular real-world systems written in 4 different programming languages, we successfully autotransplanted 10 new functionalities. That is, we have passed all the test suites that validates the new functionalities behaviour and the fact that the initial program behaviour is preserved. Additionally, we have manually checked the behaviour exercised by the organ. Autotransplantation is also very useful: in just 26 hours computation time we successfully autotransplanted the H.264 video encoding functionality from the x264 system to the VLC media player, a task that is currently done manually by the developers of VLC, since 12 years ago. We autotransplanted call graph generation and indentation for C programs into Kate, (a popular KDE based test editor used as an IDE by a lot of C developers) two features currently missing from Kate, but requested by the users of Kate. Autotransplantation is also efficient: the total run-time across 15 monolingual transplants is 5 hours and a half; the total runtime across 10 multilingual transplants is 33 hours",
