Semantic patch inference

ABSTRACT

We propose a tool for inferring transformation specifications from a few examples of original and updated code. These transformation specifications may contain multiple code fragments from within a single function, all of which must be present for the transformation to apply. This makes the inferred transformations context sensitive. Our algorithm is based on depth-first search, with pruning. Because it is applied locally to a collection of functions that contain related changes, it is efficient in practice. We illustrate the approach on an example drawn from recent changes to the Linux kernel.

References

1. J. Andersen and J. L. Lawall. Generic patch inference. In 23rd IEEE/ACM International Conference on Automated Software Engineering, pages 337–346, L’Aquila, Italy, sep 2008. IEEE.
2. S. S. Chawathe, A. Rajaraman, H. Garcia-Molina, and J. Widom. Change detection in hierarchically structured information. In SIGMOD ’96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data, pages 493–504, New York, NY, USA, 1996. ACM.
3. B. Fluri, M. Wursch, M. Pinzger, and H. C. Gall. Change distilling: Tree differencing for fine-grained source code change extraction. Software Engineering, IEEE Transactions on, 33(11):725–743, November 2007.
4. M. Gabel, L. Jiang, and Z. Su. Scalable detection of semantic clones. In Proceedings of the 30th international conference on Software engineering (ICSE’08), pages 321–330, Leipzig, Germany, 2008.
5. L. Z. Hao Zhong and H. Mei. Inferring specifications of object oriented APIs from API source code. In Proceedings of 15th Asia-Pacific Software Engineering Conference (APSEC’08), pages 221–228, 2008.
6. L. Jiang, G. Misherghi, Z. Su, and S. Glondu. DECKARD: Scalable and accurate tree-based detection of code clones. In Proceedings of the 29th international conference on Software Engineering (ICSE’07), pages 96–105, Minneapolis, MN, May 2007.
7. T. Kamiya, S. Kusumoto, and K. Inoue. CCFinder: a multilinguistic token-based code clone detection system for large scale source code. IEEE Transactions on Software Engineering, 28(7):654–670, 2002.
8. H. Li and S. Thompson. Clone detection and removal for Erlang/OTP within a refactoring environment. In PEPM’09, pages 169–178, Savannah, GA, USA, 2009.
9. 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 OSDI’04: Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, pages 20––20, Berkeley, CA, USA, 2004. USENIX Association.
10. D. Lo, S. C. Khoo, and C. Liu. Efficient mining of iterative patterns for software specification discovery. In KDD’07, pages 460–469, San Jose, California, USA, 2007.
11. D. MacKenzie, P. Eggert, and R. Stallman. Comparing and Merging Files With Gnu Diff and Patch. Network Theory Ltd, Jan. 2003. Unified Format section, http://www.gnu.org/software/ diffutils/manual/html_node/Unified-Format.html.
12. N. Meng, M. Kim, and K. S. McKinley. Systematic editing: generating program transformations from an example. In PLDI’11, pages 329–342, San Jose, CA, USA, June 2011.
13. I. Neamtiu, J. S. Foster, and M. Hicks. Understanding source code evolution using abstract syntax tree matching. SIGSOFT Softw. Eng. Notes, 30(4):1–5, 2005.
14. Y. Padioleau, J. Lawall, R. R. Hansen, and G. Muller. Documenting and automating collateral evolutions in Linux device drivers. In Eurosys 2008, pages 247–260, Glasgow, Scotland, Mar. 2008.
15. Y. Padioleau, J. L. Lawall, and G. Muller. Understanding collateral evolution in Linux device drivers. In The first ACM SIGOPS EuroSys conference (EuroSys 2006), pages 59–71, Leuven, Belgium, Apr. 2006.
16. H. Safyallah and K. Sartipi. Dynamic analysis of software systems using execution pattern mining. In ICPC’06, pages 84–88, 2006.

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