Automatic error elimination by horizontal code transfer across multiple applications

Abstract

We present Code Phage (CP), a system for automatically transferring correct code from donor applications into recipient applications that process the same inputs to successfully eliminate errors in the recipient. Experimental results using seven donor applications to eliminate ten errors in seven recipient applications highlight the ability of CP to transfer code across applications to eliminate out of bounds access, integer overflow, and divide by zero errors. Because CP works with binary donors with no need for source code or symbolic information, it supports a wide range of use cases. To the best of our knowledge, CP is the first system to automatically transfer code across multiple applications.

References

1. Cwebp. https://developers.google.com/speed/webp/ docs/cwebp.
2. Dillo. http://www.dillo.org/.
3. Feh - a fast and light Imlib2-based image viewer. http://feh. finalrewind.org/.
4. Hachoir. http://bitbucket.org/haypo/hachoir/wiki/ Home.
5. Imagemagick. http://www.imagemagick.org/script/ index.php.
6. Peach fuzzing platform. http://peachfuzzer.com/.
7. Swfdec. http://swfdec.freedesktop.org/wiki/.
8. Viewnoir - the elegant image viewer. http://xsisqox.github. io/Viewnior/.
9. Libtiff. http://www.remotesensing.org/libtiff/.
10. Gnu gnash. https://www.gnu.org/software/gnash/.
11. The jasper project home page. http://www.ece.uvic.ca/ ~frodo/jasper/.
12. mtpaint. http://mtpaint.sourceforge.net/.
13. Openjpeg. http://www.openjpeg.org.
14. Wireshark. https://www.wireshark.org/.
15. M. Alkhalaf, A. Aydin, and T. Bultan. Semantic differential repair for input validation and sanitization. In International Symposium on Software Testing and Analysis, ISSTA ’14, San Jose, CA, USA - July 21 - 26, 2014, pages 225–236, 2014.
16. K. Ambrose, A. Koppenhofer, and F. Belanger. Horizontal gene transfer of a bacterial insect toxin gene into the epichloe fungal symbionts of grasses. Scientific Reports, 4, July 2014.
17. M. Barlow. What Antimicrobial Resistance Has Taught Us About Horizontal Gene Transfer. Methods in Molecular Biology, 532: 397–411, 2009.
18. . URL http://dx.doi.org/10.1007/ 978-1-60327-853-9_23.
19. E. D. Berger and B. G. Zorn. Diehard: Probabilistic memory safety for unsafe languages. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’06’, pages 158–168. ACM, 2006. ISBN 1-59593-320-4.. URL http://doi.acm.org/10.1145/1133981.1134000.
20. M. Carbin, S. Misailovic, M. Kling, and M. C. Rinard. Detecting and escaping infinite loops with jolt. ECOOP’11, 2011.
21. A. Carzaniga, A. Gorla, A. Mattavelli, N. Perino, and M. Pezzè. Automatic recovery from runtime failures. In Proceedings of the 2013 International Conference on Software Engineering, pages 782–791.
22. L. Chen and A. Avizienis. N-version programming: A Fault-tolerance approach to reliability of software operation. In The Twenty-Fifth International Symposium on Fault-Tolerant Computing Highlights from Twenty-Five Years. IEEE, 1995.
23. O. Crameri, N. Knezevic, D. Kostic, R. Bianchini, and W. Zwaenepoel. Staged deployment in mirage, an integrated software upgrade testing and distribution system. In ACM SIGOPS Operating Systems Review, volume 41, pages 221–236. ACM, 2007.
24. Y. h. Eom and B. Demsky. Self-stabilizing java. In Proceedings of the 33rd ACM SIGPLAN conference on Programming Language Design and Implementation, PLDI ’12’, pages 287–298. ACM, 2012. ISBN 978-1-4503-1205-9.. URL http://doi.acm.org/10.1145/ 2254064.2254099.
25. M. Gabel, J. Yang, Y. Yu, M. Goldszmidt, and Z. Su. Scalable and systematic detection of buggy inconsistencies in source code. In Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2010, October 17-21, 2010, Reno/Tahoe, Nevada, USA, pages 175–190, 2010.
26. V. Ganesh, T. Leek, and M. Rinard. Taint-based directed whitebox fuzzing. In ICSE ’09: Proceedings of the 31st International Conference on Software Engineering. IEEE Computer Society, 2009. ISBN 978-1- 4244-3453-4..
27. L. Jiang, Z. Su, and E. Chiu. Context-based detection of clone-related bugs. In Proceedings of the 6th joint meeting of the European Software Engineering Conference, 2007, Dubrovnik, Croatia, September 3-7, 2007, pages 55–64, 2007.
28. G. Jin, W. Zhang, D. Deng, B. Liblit, and S. Lu. Automated concurrencybug fixing. In OSDI, volume 12, pages 221–236, 2012.
29. M. A. Kay, J. C. Glorioso, and L. Naldini. Viral vectors for gene therapy: the art of turning infectious agents into vehicles of therapeutics. Nat Med, 7(1):33–40, Jan. 2001.. URL http://dx.doi.org/10.1038/ 83324.
30. P. J. Keeling and J. D. Palmer. Horizontal gene transfer in eukaryotic evolution. Nature Reviews Genetics, 9(8), 8 2008.
31. Y. Khmelevsky, M. Rinard, and S. Sidiroglou. A source-to-source transformation tool for error fixing. CASCON, 2013.
32. M. Kling, S. Misailovic, M. Carbin, and M. Rinard. Bolt: on-demand infinite loop escape in unmodified binaries. In Proceedings of the ACM international conference on Object oriented programming systems languages and applications, OOPSLA ’12’, pages 431–450. ACM, 2012. ISBN 978-1-4503-1561-6.. URL http://doi.acm.org/ 10.1145/2384616.2384648.
33. J. C. Knight and N. G. Leveson. An experimental evaluation of the assumption of independence in multi-version programming. IEEE Transactions on Software Engineering, 12:96–109, 1986.
34. T. Kremenek, P. Twohey, G. Back, A. Ng, and D. Engler. From uncertainty to belief: Inferring the specification within. In Proceedings of the 7th symposium on Operating systems design and implementation, pages 161–176. USENIX Association, 2006.
35. C. Le Goues, M. Dewey-Vogt, S. Forrest, and W. Weimer. A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each. ICSE 2012, 2012.
36. Z. Li, S. Lu, S. Myagmar, and Y. Zhou. Cp-miner: A tool for finding copy-paste and related bugs in operating system code. In 6th Symposium on Operating System Design and Implementation (OSDI 2004), San Francisco, California, USA, December 6-8, 2004, pages 289–302, 2004.
37. F. Logozzo and T. Ball. Modular and verified automatic program repair. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA ’12’, pages 133–146, New York, NY, USA, 2012. ACM. ISBN 978-1-4503- 1561-6.. URL http://doi.acm.org/10.1145/2384616.
38. 2384626.
39. F. Long and M. Rinard. Staged Program Repair in SPR. Technical Report MIT-CSAIL-TR-2015-008, 2015. URL http://hdl.handle. net/1721.1/95970.
40. F. Long, V. Ganesh, M. Carbin, S. Sidiroglou, and M. Rinard. Automatic input rectification. ICSE ’12, 2012.
41. F. Long, S. Sidiroglou-Douskos, D. Kim, and M. Rinard. Sound input filter generation for integer overflow errors. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’14’, pages 439–452, New York, NY, USA, 2014.
42. ACM. ISBN 978-1-4503-2544-8.. URL http://doi.acm.org/ 10.1145/2535838.2535888.
43. F. Long, S. Sidiroglou-Douskos, and M. Rinard. Automatic runtime error repair and containment via error shepherding. In Proceedings of the 35th ACM SIGPLAN conference on Programming Language Design and Implementation, PLDI ’14’. ACM, 2014.
44. N. Meng, M. Kim, and K. S. McKinley. Sydit: creating and applying a program transformation from an example. In SIGSOFT/FSE’11, pages 440–443, 2011.
45. N. Meng, M. Kim, and K. S. McKinley. LASE: locating and applying systematic edits by learning from examples. In 35th International Conference on Software Engineering, ICSE ’13, San Francisco, CA, USA, May 18-26, 2013, pages 502–511, 2013.
46. S. Misailovic, D. Kim, and M. Rinard. Parallelizing sequential programs with statistical accuracy tests. Technical Report MIT-CSAIL-TR-2010- 038, 2010. URL http://hdl.handle.net/1721.1/57475.
47. S. Misailovic, D. Kim, and M. C. Rinard. Parallelizing sequential programs with statistical accuracy tests. ACM Trans. Embedded Comput. Syst., 12(2s):88, 2013.
48. V. Nagarajan, D. Jeffrey, and R. Gupta. Self-recovery in server programs. ISMM ’09’, 2009.
49. N. Nethercote and J. Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. PLDI ’07, 2007.
50. G. Novark, E. D. Berger, and B. G. Zorn. Exterminator: automatically correcting memory errors with high probability. ACM SIGPLAN Notices, 42(6):1–11, 2007.
51. J. H. Perkins, S. Kim, S. Larsen, S. Amarasinghe, J. Bachrach, M. Carbin, C. Pacheco, F. Sherwood, S. Sidiroglou, G. Sullivan, W.-F. Wong, Y. Zibin, M. D. Ernst, and M. Rinard. Automatically patching errors in deployed software. SOSP ’09. ACM, 2009.
52. Z. Qi, F. Long, S. Achour, and M. Rinard. An analysis of patch plausibility and correctness for generate-and-validate patch generation systems. Technical Report MIT-CSAIL-TR-2010-038, 2015. URL http://dspace.mit.edu/handle/1721.1/94337.
53. F. Qin, J. Tucek, Y. Zhou, and J. Sundaresan. Rx: Treating bugs as allergies–a safe method to survive software failures. ACM Trans. Comput. Syst., 2007.
54. M. Rinard, C. Cadar, D. Dumitran, D. M. Roy, T. Leu, and W. S. Beebee. Enhancing server availability and security through failure-oblivious computing. In OSDI, pages 303–316, 2004.
55. H. Samimi, M. Schäfer, S. Artzi, T. D. Millstein, F. Tip, and L. J. Hendren. Automated repair of HTML generation errors in PHP applications using string constraint solving. In ICSE 2012, June 2-9, 2012, Zurich, Switzerland, pages 277–287, 2012.
56. S. Sidiroglou, M. E. Locasto, S. W. Boyd, and A. D. Keromytis. Building a reactive immune system for software services. In Proceedings of the general track, 2005 USENIX annual technical conference: April 10-15, 2005, Anaheim, CA, USA, pages 149–161. USENIX, 2005.
57. S. Sidiroglou, O. Laadan, C. Perez, N. Viennot, J. Nieh, and A. D. Keromytis. Assure: Automatic software self-healing using rescue points. In ASPLOS, pages 37–48, 2009. ISBN 978-1-60558-406-5.. URL http://doi.acm.org/10.1145/1508244.1508250.
58. S. Sidiroglou, E. Lahtinen, N. Rittenhouse, P. Piselli, F. Long, D. Kim, and M. Rinard. Automatic Integer Overflow Discovery Using Goal-Directed Conditional Branch Enforcement. In ASPLOS, 2015.
59. S. Sidiroglou-Douskos, E. Lahtinen, F. Long, and M. Rinard. Automatic error elimination by multi-application code transfer. Technical Report MIT-CSAIL-TR-2014-024, Aug. 2014. URL http://dspace.mit. edu/handle/1721.1/91148.
60. S. Sidiroglou-Douskos, E. Davis, and M. Rinard. Horizontal code transfer via program fracture and recombination. Technical Report MITCSAIL-TR-2015-012, 2015. URL http://dspace.mit.edu/ handle/1721.1/96585.
61. S. Sidiroglou-Douskos, E. Lahtinen, F. Long, and M. Rinard. Automatic error elimination by multi-application code transfer. Technical Report MIT-CSAIL-TR-2015-013, 2015. URL http://hdl.handle. net/1721.1/96625.
62. S. Son, K. S. McKinley, and V. Shmatikov. Rolecast: finding missing security checks when you do not know what checks are. ACM SIGPLAN Notices, 46(10):1069–1084, 2011.
63. S. Son, K. S. McKinley, and V. Shmatikov. Fix me up: Repairing accesscontrol bugs in web applications. In NDSS, 2013.
64. M. Sutton, A. Greene, and P. Amini. Fuzzing: Brute Force Vulnerability Discovery. Pearson Education, 2007.
65. M. Toomim, A. Begel, and S. L. Graham. Managing duplicated code with linked editing. In Visual Languages and Human Centric Computing, 2004 IEEE Symposium on, pages 173–180. IEEE, 2004.
66. W. Weimer, Z. P. Fry, and S. Forrest. Leveraging program equivalence for adaptive program repair: Models and first results. In Automated Software Engineering (ASE), 2013.
67. W. Weimer, T. Nguyen, C. Le Goues, and S. Forrest. Automatically finding patches using genetic programming. In Proceedings of the 31st International Conference on Software Engineering, ICSE ’09’, 2009.

Index Terms

• Social and professional topics

  • Professional topics

    • Management of computing and information systems

      • Software management

        • Software maintenance

• Software and its engineering

  • Software creation and management

    • Software post-development issues

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging