Program element matching for multi-version program analyses

ABSTRACT

Multi-version program analyses require that elements of one version of a program be mapped to the elements of other versions of that program. Matching program elements between two versions of a program is a fundamental building block for multi-version program analyses and other software evolution research such as profile propagation, regression testing, and software version merging.In this paper, we survey matching techniques that can be used for multi-version program analyses and evaluate them based on hypothetical change scenarios. This paper also lists challenges of the matching problem, identifies open problems, and proposes future directions.

REFERENCES

• 1: subversion.tigris.org.
• 2: www.cvshome.org
• 3: A. Aiken. A system for detecting software plagiarism.
• 4: Giuliano Antoniol , Massimiliano Di Penta , Ettore Merlo, An Automatic Approach to identify Class Evolution Discontinuities, Proceedings of the Principles of Software Evolution, 7th International Workshop on (IWPSE'04), p.31-40, September 06-07, 2004 [doi>10.1109/IWPSE.2004.4]
• 5: Taweesup Apiwattanapong , Alessandro Orso , Mary Jean Harrold, A Differencing Algorithm for Object-Oriented Programs, Proceedings of the 19th IEEE international conference on Automated software engineering, p.2-13, September 20-24, 2004 [doi>10.1109/ASE.2004.5]
• 6: Taweesup Apiwattanapong , Alessandro Orso , Mary Jean Harrold, Efficient and precise dynamic impact analysis using execute-after sequences, Proceedings of the 27th international conference on Software engineering, p.432-441, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062534]
• 7: Alberto Apostolico , Zvi Galil, Pattern matching algorithms, Oxford University Press, Oxford, 1997
• 8: B. S. Baker. A program for identifying duplicated code. Computing Science and Statistics, 24:49--57, 1992.
• 9: Ira D. Baxter , Andrew Yahin , Leonardo Moura , Marcelo Sant'Anna , Lorraine Bier, Clone Detection Using Abstract Syntax Trees, Proceedings of the International Conference on Software Maintenance, p.368, March 16-19, 1998
• 10: Jennifer Bevan , E. James Whitehead, Jr. , Sunghun Kim , Michael Godfrey, Facilitating software evolution research with kenyon, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 11: Jennifer Bevan , E. James Whitehead, Jr., Identification of Software Instabilities, Proceedings of the 10th Working Conference on Reverse Engineering, p.134, November 13-17, 2003
• 12: David Binkley , Susan Horwitz , Thomas Reps, Program integration for languages with procedure calls, ACM Transactions on Software Engineering and Methodology (TOSEM), v.4 n.1, p.3-35, Jan. 1995 [doi>10.1145/201055.201056]
• 13: James R. Cordy, Comprehending Reality " Practical Barriers to Industrial Adoption of Software Maintenance Automation, Proceedings of the 11th IEEE International Workshop on Program Comprehension, p.196, May 10-11, 2003
• 14: Serge Demeyer , Stéphane Ducasse , Oscar Nierstrasz, Finding refactorings via change metrics, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.166-177, October 2000, Minneapolis, Minnesota, United States
• 15: Stephen G. Eick , Todd L. Graves , Alan F. Karr , J. S. Marron , Audris Mockus, Does Code Decay? Assessing the Evidence from Change Management Data, IEEE Transactions on Software Engineering, v.27 n.1, p.1-12, January 2001 [doi>10.1109/32.895984 ]
• 16: Michael Dean Ernst , David Notkin, Dynamically discovering likely program invariants, 2000
• 17: Harald Gall , Karin Hajek , Mehdi Jazayeri, Detection of Logical Coupling Based on Product Release History, Proceedings of the International Conference on Software Maintenance, p.190, March 16-19, 1998
• 18: C. Görg and P. Weißgerber. Error detection by refactoring reconstruction. In MSR '05, pages 29--35.
• 19: Carsten Gorg , Peter Weisgerber, Detecting and Visualizing Refactorings from Software Archives, Proceedings of the 13th International Workshop on Program Comprehension, p.205-214, May 15-16, 2005 [doi>10.1109/WPC.2005.18]
• 20: Todd L. Graves , Alan F. Karr , J. S. Marron , Harvey Siy, Predicting Fault Incidence Using Software Change History, IEEE Transactions on Software Engineering, v.26 n.7, p.653-661, July 2000 [doi>10.1109/32.859533 ]
• 21: Mary Jean Harrold , James A. Jones , Tongyu Li , Donglin Liang , Alessandro Orso , Maikel Pennings , Saurabh Sinha , S. Alexander Spoon , Ashish Gujarathi, Regression test selection for Java software, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.312-326, October 14-18, 2001, Tampa Bay, FL, USA
• 22: Johannes Henkel , Amer Diwan, CatchUp!: capturing and replaying refactorings to support API evolution, Proceedings of the 27th international conference on Software engineering, p.274-283, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062512]
• 23: Susan Horwitz, Identifying the semantic and textual differences between two versions of a program, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.234-245, June 1990, White Plains, New York, United States
• 24: Extensible Language-Aware Merging, Proceedings of the International Conference on Software Maintenance (ICSM'02), p.511, October 03-06, 2002
• 25: James W. Hunt , Thomas G. Szymanski, A fast algorithm for computing longest common subsequences, Communications of the ACM, v.20 n.5, p.350-353, May 1977 [doi>10.1145/359581.359603]
• 26: Daniel Jackson , David A. Ladd, Semantic Diff: A Tool for Summarizing the Effects of Modifications, Proceedings of the International Conference on Software Maintenance, p.243-252, September 01, 1994
• 27: J. Howard Johnson, Identifying redundancy in source code using fingerprints, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: software engineering, October 24-28, 1993, Toronto, Ontario, Canada
• 28: Toshihiro Kamiya , Shinji Kusumoto , Katsuro Inoue, CCFinder: a multilinguistic token-based code clone detection system for large scale source code, IEEE Transactions on Software Engineering, v.28 n.7, p.654-670, July 2002 [doi>10.1109/TSE.2002.1019480 ]
• 29: Miryung Kim , Vibha Sazawal , David Notkin , Gail Murphy, An empirical study of code clone genealogies, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 30: Sunghun Kim , Kai Pan , E. James Whitehead, Jr., When Functions Change Their Names: Automatic Detection of Origin Relationships, Proceedings of the 12th Working Conference on Reverse Engineering, p.143-152, November 07-11, 2005 [doi>10.1109/WCRE.2005.33]
• 31: Sunghun Kim , E. James Whitehead , Jennifer Bevan, Analysis of signature change patterns, Proceedings of the 2005 international workshop on Mining software repositories, p.1-5, May 17-17, 2005, St. Louis, Missouri
• 32: Raghavan Komondoor , Susan Horwitz, Using Slicing to Identify Duplication in Source Code, Proceedings of the 8th International Symposium on Static Analysis, p.40-56, July 16-18, 2001
• 33: J. Laski and W. Szermer. Identification of program modifications and its applications in software maintenance. In ICSM, 1992.
• 34: Ernst Lippe , Norbert van Oosterom, Operation-based merging, Proceedings of the fifth ACM SIGSOFT symposium on Software development environments, p.78-87, December 09-11, 1992, Tyson's Corner, Virginia, United States
• 35: Guido Malpohl , James J. Hunt , Walter F. Tichy, Renaming Detection, Automated Software Engineering, v.10 n.2, p.183-202, April 2003 [doi>10.1023/A:1022968013020 ]
• 36: T. Mens, A State-of-the-Art Survey on Software Merging, IEEE Transactions on Software Engineering, v.28 n.5, p.449-462, May 2002 [doi>10.1109/TSE.2002.1000449 ]
• 37: Nachiappan Nagappan , Thomas Ball, Use of relative code churn measures to predict system defect density, Proceedings of the 27th international conference on Software engineering, p.284-292, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062514]
• 38: Iulian Neamtiu , Jeffrey S. Foster , Michael Hicks, Understanding source code evolution using abstract syntax tree matching, Proceedings of the 2005 international workshop on Mining software repositories, p.1-5, May 17-17, 2005, St. Louis, Missouri
• 39: George C. Necula, Translation validation for an optimizing compiler, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.83-94, June 18-21, 2000, Vancouver, British Columbia, Canada
• 40: Alessandro Orso , Nanjuan Shi , Mary Jean Harrold, Scaling regression testing to large software systems, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 41: D. L. Parnas, On the criteria to be used in decomposing systems into modules, Communications of the ACM, v.15 n.12, p.1053-1058, Dec. 1972 [doi>10.1145/361598.361623]
• 42: Gregg Rothermel , Mary Jean Harrold, A safe, efficient regression test selection technique, ACM Transactions on Software Engineering and Methodology (TOSEM), v.6 n.2, p.173-210, April 1997 [doi>10.1145/248233.248262]
• 43: Jacek Śliwerski , Thomas Zimmermann , Andreas Zeller, When do changes induce fixes?, Proceedings of the 2005 international workshop on Mining software repositories, p.1-5, May 17-17, 2005, St. Louis, Missouri
• 44: Amitabh Srivastava , Jay Thiagarajan, Effectively prioritizing tests in development environment, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 45: Walter F. Tichy, The string-to-string correction problem with block moves, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.309-321, Nov. 1984 [doi>10.1145/357401.357404]
• 46: Z. Wang, K. Pierce, and S. McFarling. BMAT - a binary matching tool for stale profile propagation. J. Instruction-Level Parallelism, 2, 2000.
• 47: Wuu Yang, Identifying syntactic differences between two programs, Software—Practice & Experience, v.21 n.7, p.739-755, July 1991 [doi>10.1002/spe.4380210706]
• 48: Annie T. T. Ying , Gail C. Murphy , Raymond Ng , Mark C. Chu-Carroll, Predicting Source Code Changes by Mining Change History, IEEE Transactions on Software Engineering, v.30 n.9, p.574-586, September 2004 [doi>10.1109/TSE.2004.52]
• 49: Xiangyu Zhang , Rajiv Gupta, Matching execution histories of program versions, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 50: T. Zimmermann and P. Weißgerber. Preprocessing CVS data for fine-grained analysis. In MSR'04, pages 2--6.
• 51: Thomas Zimmermann , Peter Weissgerber , Stephan Diehl , Andreas Zeller, Mining Version Histories to Guide Software Changes, IEEE Transactions on Software Engineering, v.31 n.6, p.429-445, June 2005 [doi>10.1109/TSE.2005.72]
• 52: Michael W. Godfrey , Lijie Zou, Using Origin Analysis to Detect Merging and Splitting of Source Code Entities, IEEE Transactions on Software Engineering, v.31 n.2, p.166-181, February 2005 [doi>10.1109/TSE.2005.28]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering

General Terms:
Algorithms, Documentation

Keywords:
matching, multi-version analysis, software evolution