Topology analysis of software dependencies

ABSTRACT

Before performing a modification task, a developer usually has to investigate the source code of a system to understand how to carry out the task. Discovering the code relevant to a change task is costly because it is a human activity whose success depends on a large number of unpredictable factors, such as intuition and luck. Although studies have shown that effective developers tend to explore a program by following structural dependencies, no methodology is available to guide their navigation through the thousands of dependency paths found in a nontrivial program. We describe a technique to automatically propose and rank program elements that are potentially interesting to a developer investigating source code. Our technique is based on an analysis of the topology of structural dependencies in a program. It takes as input a set of program elements of interest to a developer and produces a fuzzy set describing other elements of potential interest. Empirical evaluation of our technique indicates that it can help developers quickly select program elements worthy of investigation while avoiding less interesting ones.

REFERENCES

• 1: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.246-256, June 1990, White Plains, New York, United States
• 2: Aho, A. V. 1980. Pattern matching in strings. In Formal Language Theory: Perspectives and Open Problems, R. V. Book, Ed. Academic Press, 325--347.
• 3: Paul D. Allison, Logistic Regression Using the SAS System: Theory and Application, SAS Publishing, 1999
• 4: G. Antoniol , G. Canfora , A. de Lucia , E. Merlo, Recovering Code to Documentation Links in OO System, Proceedings of the Sixth Working Conference on Reverse Engineering, p.136, October 06-08, 1999
• 5: Giuliano Antoniol , Yann-Gael Gueheneuc, Feature Identification: A Novel Approach and a Case Study, Proceedings of the 21st IEEE International Conference on Software Maintenance, p.357-366, September 25-30, 2005 [doi>10.1109/ICSM.2005.48]
• 6: B. W. Boehm, Software Engineering, IEEE Transactions on Computers, v.25 n.12, p.1226-1241, December 1976 [doi>10.1109/TC.1976.1674590]
• 7: Yih-Farn Chen , Michael Y. Nishimoto , C. V. Ramamoorthy, The C Information Abstraction System, IEEE Transactions on Software Engineering, v.16 n.3, p.325-334, March 1990 [doi>10.1109/32.48940]
• 8: Thomas Eisenbarth , Rainer Koschke , Daniel Simon, Locating Features in Source Code, IEEE Transactions on Software Engineering, v.29 n.3, p.210-224, March 2003 [doi>10.1109/TSE.2003.1183929]
• 9: Andrew David Eisenberg , Kris De Volder, Dynamic Feature Traces: Finding Features in Unfamiliar Code, Proceedings of the 21st IEEE International Conference on Software Maintenance, p.337-346, September 25-30, 2005 [doi>10.1109/ICSM.2005.42]
• 10: Keith Gallagher, Visual Impact Analysis, Proceedings of the 1996 International Conference on Software Maintenance, p.52-58, November 04-08, 1996
• 11: Keith Brian Gallagher , James R. Lyle, Using Program Slicing in Software Maintenance, IEEE Transactions on Software Engineering, v.17 n.8, p.751-761, August 1991 [doi>10.1109/32.83912]
• 12: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 13: Adele Goldberg, SMALLTALK-80: the interactive programming environment, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 14: Tibor Gyimóthy , Árpád Beszédes , Istán Forgács, An efficient relevant slicing method for debugging, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.303-321, September 06-10, 1999, Toulouse, France
• 15: Daniel Jackson , Eugene J. Rollins, A new model of program dependences for reverse engineering, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.2-10, December 06-09, 1994, New Orleans, Louisiana, United States
• 16: Doug Janzen , Kris De Volder, Navigating and querying code without getting lost, Proceedings of the 2nd international conference on Aspect-oriented software development, p.178-187, March 17-21, 2003, Boston, Massachusetts [doi>10.1145/643603.643622]
• 17: Mik Kersten , Gail C. Murphy, Mylar: a degree-of-interest model for IDEs, Proceedings of the 4th international conference on Aspect-oriented software development, p.159-168, March 14-18, 2005, Chicago, Illinois [doi>10.1145/1052898.1052912]
• 18: Philippe Kruchten, The Rational Unified Process: An Introduction, Second Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 19: Moises Lejter , Scott Meyers , Steven P. Reiss, Support for Maintaining Object-Oriented Programs, IEEE Transactions on Software Engineering, v.18 n.12, p.1045-1052, December 1992 [doi>10.1109/32.184759]
• 20: Andrian Marcus , Andrey Sergeyev , Vaclav Rajlich , Jonathan I. Maletic, An Information Retrieval Approach to Concept Location in Source Code, Proceedings of the 11th Working Conference on Reverse Engineering, p.214-223, November 08-12, 2004
• 21: Object Technology International, Inc. 2001. Eclipse platform technical overview. White Paper.
• 22: Alessandro Orso , Taweesup Apiwattanapong , James Law , Gregg Rothermel , Mary Jean Harrold, An Empirical Comparison of Dynamic Impact Analysis Algorithms, Proceedings of the 26th International Conference on Software Engineering, p.491-500, May 23-28, 2004
• 23: Incremental Slicing Based on Data-Dependences Types, Proceedings of the IEEE International Conference on Software Maintenance (ICSM'01), p.158, November 07-09, 2001
• 24: Martin P. Robillard , Frédéric Weigand-Warr, ConcernMapper: simple view-based separation of scattered concerns, Proceedings of the 2005 OOPSLA workshop on Eclipse technology eXchange, p.65-69, October 16-17, 2005, San Diego, California [doi>10.1145/1117696.1117710]
• 25: Martin P. Robillard, Automatic generation of suggestions for program investigation, 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
• 26: Martin P. Robillard, Tracking Concerns in Evolving Source Code: An Empirical Study, Proceedings of the 22nd IEEE International Conference on Software Maintenance, p.479-482, September 24-27, 2006 [doi>10.1109/ICSM.2006.70]
• 27: Martin P. Robillard , Wesley Coelho , Gail C. Murphy, How Effective Developers Investigate Source Code: An Exploratory Study, IEEE Transactions on Software Engineering, v.30 n.12, p.889-903, December 2004 [doi>10.1109/TSE.2004.101]
• 28: Maher Salah , Spiros Mancoridis, A Hierarchy of Dynamic Software Views: From Object-Interactions to Feature-Interactions, Proceedings of the 20th IEEE International Conference on Software Maintenance, p.72-81, September 11-14, 2004
• 29: Sanella, M. 1983. The Interlisp-D Reference Manual. Xerox Corporation.
• 30: Jonathan Sillito , Gail C. Murphy , Kris De Volder, Questions programmers ask during software evolution tasks, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181779]
• 31: Gregor Snelting, Concept analysis—a new framework for program understanding, Proceedings of the 1998 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.1-10, June 16-16, 1998, Montreal, Quebec, Canada
• 32: Tip, F. 1995. A survey of program slicing techniques. J. Program. Lang. 3, 3, 121--189.
• 33: P. Tonella , G. Antoniol , R. Fiutem , E. Merlo, Variable Precision Reaching Definitions Analysis for Software Maintenance, Proceedings of the 1st Euromicro Working Conference on Software Maintenance and Reengineering (CSMR '97), p.60, March 17-19, 1997
• 34: Frederic Weigand Warr , Martin P. Robillard, Suade: Topology-Based Searches for Software Investigation, Proceedings of the 29th international conference on Software Engineering, p.780-783, May 20-26, 2007 [doi>10.1109/ICSE.2007.80]
• 35: Weiser, M. 1984. Program slicing. IEEE Trans. Softw. Engin. 10, 4, 352--357.
• 36: Norman Wilde , Michael C. Scully, Software reconnaissance: mapping program features to code, Journal of Software Maintenance: Research and Practice, v.7 n.1, p.49-62, Jan.-Feb. 1995 [doi>10.1002/smr.4360070105]
• 37: W. Eric Wong , Joseph R. Horgan , Swapna S. Gokhale , Kishor S. Trivedi, Locating Program Features using Execution Slices, Proceedings of the 1999 IEEE Symposium on Application - Specific Systems and Software Engineering and Technology, p.194, March 24-27, 1999
• 38: Yin, R. K. 1989. Case Study Research: Design and Method 2nd Ed. Applied Social Research Methods Series, vol. 5. Sage Publications Ltd., UK.
• 39: 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]
• 40: Wei Zhao , Lu Zhang , Yin Liu , Jiasu Sun , Fuqing Yang, SNIAFL: Towards a Static Non-Interactive Approach to Feature Location, Proceedings of the 26th International Conference on Software Engineering, p.293-303, May 23-28, 2004
• 41: H.-J. Zimmermann, Fuzzy set theory—and its applications (3rd ed.), Kluwer Academic Publishers, Norwell, MA, 1996
• 42: Thomas Zimmermann , Peter Weisgerber , Stephan Diehl , Andreas Zeller, Mining Version Histories to Guide Software Changes, Proceedings of the 26th International Conference on Software Engineering, p.563-572, May 23-28, 2004

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement

General Terms:
Algorithms, Experimentation, Human Factors

Keywords:
Software evolution, feature location, program understanding, separation of concerns, software change, software navigation, static analysis