Automated software transplantation

ABSTRACT

Automated transplantation would open many exciting avenues for software development: suppose we could autotransplant code from one system into another, entirely unrelated, system. This paper introduces a theory, an algorithm, and a tool that achieve this. Leveraging lightweight annotation, program analysis identifies an organ (interesting behavior to transplant); testing validates that the organ exhibits the desired behavior during its extraction and after its implantation into a host. While we do not claim automated transplantation is now a solved problem, our results are encouraging: we report that in 12 of 15 experiments, involving 5 donors and 3 hosts (all popular real-world systems), we successfully autotransplanted new functionality and passed all regression tests. Autotransplantation is also already useful: in 26 hours computation time we successfully autotransplanted the H.264 video encoding functionality from the x264 system to the VLC media player; compare this to upgrading x264 within VLC, a task that we estimate, from VLC's version history, took human programmers an average of 20 days of elapsed, as opposed to dedicated, time.

References

1. A. Arcuri and X. Yao. A Novel Co-evolutionary Approach to Automatic Software Bug Fixing. In CEC, pages 162–168, 2008.
2. H. P. Barendregt. Handbook of logic in computer science (vol. 2). chapter Lambda Calculi with Types, pages 117– 309. Oxford University Press, Inc., New York, NY, USA, 1992.
3. J. Beck and D. Eichmann. Program and interface slicing for reverse engineering. In IEEE/ACM 15th Conference on Software Engineering (ICSE’93), pages 509–518, Los Alamitos, California, USA, 1993. IEEE Computer Society Press.
4. B. Beizer. Software Testing Techniques. Van Nostrand Reinhold, New York, 1990.
5. S. Bellon, R. Koschke, G. Antoniol, J. Krinke, and E. Merlo. Comparison and evaluation of clone detection tools. IEEE Transactions on Software Engineering, 33(9):577–591, 2007.
6. A. Beszédes and T. Gyimóthy. Union slices for the approximation of the precise slice. In IEEE International Conference on Software Maintenance, pages 12–20, Los Alamitos, California, USA, Oct. 2002. IEEE Computer Society Press.
7. D. Binkley and K. B. Gallagher. Program slicing. In M. Zelkowitz, editor, Advances in Computing, Volume 43, pages 1–50. Academic Press, 1996.
8. D. Binkley, N. Gold, M. Harman, S. Islam, J. Krinke, and S. Yoo. ORBS: Language-independent program slicing. In 22nd ACM SIGSOFT International Symposium on the Foundations of Software Engineering (FSE 2014), pages 109–120, Hong Kong, China, November 2014.
9. D. Binkley, N. Gold, M. Harman, J. Krinke, and S. Yoo. Observation-based slicing. Technical Report RN/13/13, Computer Sciences Department, University College London (UCL), UK, June 20th 2013.
10. D. Binkley and M. Harman. A survey of empirical results on program slicing. Advances in Computers, 62:105–178, 2004.
11. G. Canfora, A. Cimitile, and A. De Lucia. Conditioned program slicing. Information and Software Technology Special Issue on Program Slicing, 40(11 and 12):595–607, 1998.
12. G. Canfora, A. Cimitile, A. De Lucia, and G. A. D. Lucca. Software salvaging based on conditions. In International Conference on Software Maintenance, pages 424–433, Los Alamitos, California, USA, Sept. 1994.
13. IEEE Computer Society Press.
14. G. Canfora, A. Cimitile, A. De Lucia, and G. A. D. Lucca. Decomposing legacy programs: A first step towards migrating to client–server platforms. In 6th IEEE International Workshop on Program Comprehension, pages 136–144, Los Alamitos, California, USA, June 1998. IEEE Computer Society Press.
15. G. Canfora, A. De Lucia, and M. Munro. An integrated environment for reuse reengineering C code. Journal of Systems and Software, 42:153–164, 1998.
16. G. Canfora and M. Di Penta. New frontiers in reverse engineering. In L. Briand and A. Wolf, editors, Future of Software Engineering 2007, pages 326–341, Los Alamitos, California, USA, 2007. IEEE Computer Society Press. This volume.
17. A. Cimitile, A. R. Fasolino, and P. Marascea. Reuse reengineering and validation via concept assignment. In International Conference on Software Maintenance (ICSE 1993), pages 216–225. IEEE Computer Society Press, Sept. 1993.
18. J. R. Cordy. The TXL source transformation language. Science of Computer Programming, 61(3):190–210, 2006.
19. T. Eisenbarth, R. Koschke, and D. Simon. Locating features in source code. IEEE Transactions on Software Engineering, 29(3):210–224, 2003. Special issue on ICSM 2001.
20. J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9(3):319–349, July 1987.
21. C. Fox, S. Danicic, M. Harman, and R. M. Hierons. ConSIT: a fully automated conditioned program slicer. Software—Practice and Experience, 34:15–46, 2004. Published online 26th November 2003.
22. S. Gulwani. Automating string processing in spreadsheets using input-output examples. ACM SIGPLAN Notices, 46(1):317–330, Jan. 2011.
23. R. J. Hall. Automatic extraction of executable program subsets by simultaneous dynamic program slicing. Automated Software Engineering, 2(1):33–53, Mar. 1995.
24. M. Harman, D. Binkley, and S. Danicic. Amorphous program slicing. Journal of Systems and Software, 68(1):45– 64, Oct. 2003.
25. M. Harman, N. Gold, R. M. Hierons, and D. Binkley. Code extraction algorithms which unify slicing and concept assignment. In IEEE Working Conference on Reverse Engineering (WCRE 2002), pages 11 – 21, Los Alamitos, California, USA, Oct. 2002. IEEE Computer Society Press.
26. M. Harman and R. M. Hierons. An overview of program slicing. Software Focus, 2(3):85–92, 2001.
27. M. Harman, W. B. Langdon, and Y. Jia. Babel pidgin: SBSE can grow and graft entirely new functionality into a real world system. In 6th Symposium on Search Based Software Engineering (SSBSE 2014), pages 247–252, Fortaleza, Brazil, August 2014. Springer LNCS.
28. M. Harman, W. B. Langdon, Y. Jia, D. R. White, A. Arcuri, and J. A. Clark. The GISMOE challenge: Constructing the pareto program surface using genetic programming to find better programs (keynote paper). In 27th IEEE/ACM International Conference on Automated Software Engineering (ASE 2012), pages 1–14, Essen, Germany, September 2012.
29. M. Harman, W. B. Langdon, and W. Weimer. Genetic programming for reverse engineering (keynote paper). In R. Oliveto and R. Robbes, editors, 20th Working Conference on Reverse Engineering (WCRE 2013), pages 1–10, Koblenz, Germany, 14-17 October 2013. IEEE.
30. M. J. Harrold and N. Ci. Reuse-driven interprocedural slicing. In 20th International Conference on Software Engineering (ICSE ’98), pages 74–83. IEEE Computer Society Press, Apr. 1998.
31. S. Horwitz, T. Reps, and D. Binkley. Interprocedural slicing using dependence graphs. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 25–46, Atlanta, Georgia, June 1988. Proceedings in SIGPLAN Notices, 23(7), pp.35–46, 1988.
32. L. Inozemtseva and R. Holmes. Coverage is not strongly correlated with test suite effectiveness. In Proceedings of the International Conference on Software Engineering, pages 435–445. ACM, 2014.
33. T. Kamiya, S. Kusumoto, and K. Inoue. CCFinder: A multi-linguistic token-based code clone detection system for large scale source code. IEEE Transactions on Software Engineering, 28(6):654–670, 2002.
34. R. Komondoor and S. Horwitz. Semantics-preserving procedure extraction. In 27th Symposium on Principles of Programming Languages (POPL-00), pages 155–169, N.Y., Jan. 19–21 2000. ACM Press.
35. B. Korel and J. Laski. Dynamic program slicing. Information Processing Letters, 29(3):155–163, Oct. 1988.
36. J. Krinke. Barrier slicing and chopping. In IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2003), pages 81–87, Los Alamitos, California, USA, Sept. 2003. IEEE Computer Society Press.
37. J. Krinke. Is cloned code older than non-cloned code? In J. R. Cordy, K. Inoue, S. Jarzabek, and R. Koschke, editors, 5th ICSE International Workshop on Software Clones, IWSC 2011, pages 28–33, Waikiki, Honolulu, HI, USA, 2011. ACM.
38. K. Lakhotia, P. McMinn, and M. Harman. Automated test data generation for coverage: Haven’t we solved this problem yet? In 4th Testing Academia and Industry Conference — Practice And Research Techniques (TAIC PART’09), pages 95–104, Windsor, UK, 4th–6th September 2009.
39. W. B. Langdon and M. Harman. Evolving a CUDA kernel from an nVidia template. In IEEE Congress on Evolutionary Computation, pages 1–8. IEEE, 2010.
40. W. B. Langdon and M. Harman. Evolving a CUDA kernel from an nVidia template. In P. Sobrevilla, editor, 2010 IEEE World Congress on Computational Intelligence, pages 2376–2383, Barcelona, 18-23 July 2010.
41. IEEE.
42. W. B. Langdon and M. Harman. Genetically improved CUDA C++ software. In 17th European Conference on Genetic Programming (EuroGP), pages 87–99, Granada, Spain, April 2014. Springer.
43. W. B. Langdon and M. Harman. Optimising existing software with genetic programming. IEEE Transactions on Evolutionary Computation (TEVC), pages 118–135, 2014.
44. W. B. Langdon, M. Modat, J. Petke, and M. Harman. Improving 3d medical image registration cuda software with genetic programming. In Proceedings of the 2014 Conference on Genetic and Evolutionary Computation, GECCO ’14, pages 951–958, New York, NY, USA, 2014. ACM.
45. C. Le Goues, S. Forrest, and W. Weimer. Current challenges in automatic software repair. Software Quality Journal, 21(3):421–443, 2013.
46. F. Lianubile and G. Visaggio. Extracting reusable functions by flow graph-based program slicing. IEEE Transactions on Software Engineering, 23(4):246–259, 1997.
47. Z. Manna and R. J. Waldinger. Toward automatic program synthesis. Communications of the ACM, 14(3):151– 164, 1971.
48. C. Miles, A. Lakhotia, and A. Walenstein. In situ reuse of logically extracted functional components. Journal in Computer Virology, 8(3):73–84, 2012.
49. M. Orlov and M. Sipper. Flight of the FINCH through the java wilderness. IEEE Transactions Evolutionary Computation, 15(2):166–182, 2011.
50. J. Petke, M. Harman, W. B. Langdon, and W. Weimer. Using genetic improvement & code transplants to specialise a C++ program to a problem class. In 17th European Conference on Genetic Programming (EuroGP), Granada, Spain, April 2014. To Appear.
51. Z. Qi, F. Long, S. Achour, and M. Rinard. Efficient automatic patch generation and defect identification in kali. In International Symposium on Software Testing and Analysis (ISSTA), July 2015. To appear.
52. B. Ray, M. Kim, S. Person, and N. Rungta. Detecting and characterizing semantic inconsistencies in ported code. In Automated Software Engineering (ASE 2013)), pages 367–377, Palo Alto, California, 2013.
53. S. Sidiroglou-Douskos, E. Lahtinen, F. Long, P. Piselli, and M. Rinard. Automatic error elimination by multiapplication code transfer. In 36nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2015), Portland, Oregon, June 2015.
54. To appear.
55. S. Sidiroglou-Douskos, S. Misailovic, H. Hoffmann, and M. C. Rinard. Managing performance vs. accuracy trade-offs with loop perforation. In FSE, pages 124–134, 2011.
56. J. Silva. A vocabulary of program slicing-based techniques. ACM Computing Surveys, 44(3):12:1 – 12:48, June 2012.
57. P. Sitthi-amorn, N. Modly, W. Weimer, and J. Lawrence. Genetic programming for shader simplification. ACM Transactions on Graphics, 30(6):152:1–152:11, 2011.
58. J. E. Stoy. Denotational semantics: The Scott–Strachey approach to programming language theory. MIT Press, 1985. Third edition.
59. J. Swan, M. G. Epitropakis, and J. R. Woodward. Geno-fix: An embeddable framework for dynamic adaptive genetic improvement programming. Technical Report CSM-195, Computing Science and Mathematics, University of Stirling, 2014.
60. F. Tip. A survey of program slicing techniques. Journal of Programming Languages, 3(3):121–189, Sept. 1995.
61. A. van Deursen and T. Kuipers. Identifying objects using cluster and concept analysis. Technical Report SEN-R9814, Centrum voor Wiskunde en Informatica (CWI), Sept. 1998.
62. G. A. Venkatesh. The semantic approach to program slicing. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 26–28, Toronto, Canada, June 1991. Proceedings in SIGPLAN Notices, 26(6), pp.107–119, 1991.
63. T. Wang, M. Harman, Y. Jia, and J. Krinke. Searching for better configurations: a rigorous approach to clone evaluation. In European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE’13, pages 455–465, Saint Petersburg, Russian Federation, August 2013. ACM.
64. W. Weimer, T. V. Nguyen, C. L. Goues, and S. Forrest. Automatically finding patches using genetic programming. In International Conference on Software Engineering (ICSE 2009), pages 364–374, Vancouver, Canada, 2009.
65. M. Weiser. Program slices: Formal, psychological, and practical investigations of an automatic program abstraction method. PhD thesis, University of Michigan, Ann Arbor, MI, 1979.
66. M. Weiser. Program slicing. IEEE Transactions on Software Engineering, 10(4):352–357, 1984.
67. D. R. White, A. Arcuri, and J. A. Clark. Evolutionary improvement of programs. IEEE Transactions on Evolutionary Computation (TEVC), 15(4):515–538, 2011.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software development techniques

      • Reusability

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

  • Software notations and tools

    • Software libraries and repositories