Computing dynamic clusters

ABSTRACT

When trying to reverse engineer software, execution trace analysis is increasingly used. Though, by using this technique we are quickly faced with an enormous amount of data that we must process. While many solutions have been proposed that consist of summarizing, filtering or compressing the trace, the lossless techniques are seldom able to cope with millions of events. Then, we developed a dynamic clustering technique, based on the segmentation of the execution trace that can losslessly process such a large quantity of data. In order to compute the clusters of classes we use a maximal clique computing algorithm. After having presented our technology we show experimental results highlighting that it is robust with respect to the segmentation parameters. Finally we present the tool we developed to compute dynamic clusters from execution traces.

REFERENCES

• 1: Bergey J., Smith D., Weiderman N., Woods S. 1999. Options Analysis for Reengineering (OAR): Issues and Conceptual Approach. Software Engineering Institute, Tech. Note CMU/SEI-99-TN-014, 1999.
• 2: Kazman R., O'Brien L., Verhoef C. 2003. Architecture Reconstruction Guidelines, 3rd edition. Software Engineering Institute, Tech. Report CMU/SEI-2002-TR-034, 2003.
• 3: Scott R. Tilley , Dennis B. Smith , Santanu Paul, Towards a Framework for Program Understanding, Proceedings of the 4th International Workshop on Program Comprehension (WPC '96), p.19, March 29-31, 1996
• 4: Ted J. Biggerstaff , Bharat G. Mitbander , Dallas E. Webster, Program understanding and the concept assignment problem, Communications of the ACM, v.37 n.5, p.72-82, May 1994 [doi>10.1145/175290.175300]
• 5: Gély, A. 2005. Algorithmique Combinatoire: Cliques, Bicycles et Systèmes Implicatifs. PhD thesis. Univ. de Clermont-Ferrand II, 2005.
• 6: Meyer M., Wendehals L. 2005. Selective Tracing for Dynamic Analyses. Proceedings of the 1st International Workshop on Program Comprehension through Dynamic Analysis (PCODA'05).
• 7: Hamou-Lhadj A. 2005. The Concept of Trace Summarization. Proceedings of the 1st International Workshop on Program Comprehension through Dynamic Analysis (PCODA'05).
• 8: Vasconcelos A., Cepêda R., Werner C. 2005. An Approach to Program Comprehension through Reverse Engineering of Complementary Software Views. Proceedings of the 1st International Workshop on Program Comprehension through Dynamic Analysis (PCODA'05).
• 9: Sartipi K., Safyallah H. 2006. An Environment for Pattern based Dynamic Analysis of Software Systems. Proceedings of the 2nd International Workshop on Program Comprehension through Dynamic Analysis (PCODA'06).
• 10: Dugerdil Ph., Jossi S. 2008. Empirical Assessment of Execution Trace Segmentation in Reverse-Engineering. ICSOFT 2008.
• 11: Andrian Marcus, Semantic Driven Program Analysis, Proceedings of the 20th IEEE International Conference on Software Maintenance, p.469-473, September 11-14, 2004
• 12: Verbaere M. 2003. Program Slicing for Refactoring. MS Thesis, Oxford University. 2003
• 13: Michael Siff , Thomas Reps, Identifying Modules via Concept Analysis, IEEE Transactions on Software Engineering, v.25 n.6, p.749-768, November 1999 [doi>10.1109/32.824377]
• 14: M. Harman , N. Gold , R. Hierons , D. Binkley, Code Extraction Algorithms which Unify Slicing and Concept Assignment, Proceedings of the Ninth Working Conference on Reverse Engineering (WCRE'02), p.11, October 29-November 01, 2002
• 15: Paolo Tonella, Using a Concept Lattice of Decomposition Slices for Program Understanding and Impact Analysis, IEEE Transactions on Software Engineering, v.29 n.6, p.495-509, June 2003 [doi>10.1109/TSE.2003.1205178]
• 16: T. A. Wiggerts, Using Clustering Algorithms in Legacy Systems Remodularization, Proceedings of the Fourth Working Conference on Reverse Engineering (WCRE '97), p.33, October 06-08, 1997
• 17: Müller H.A., Orgun M.A., Tilley S., Uhl J.S. 1993. A Reverse Engineering Approach To Subsystem Structure Identification. Software Maintenance: Research and Practice 5(4), John Wiley & Sons. 1993
• 18: Periklis Andritsos , Vassilios Tzerpos, Software Clustering based on Information Loss Minimization, Proceedings of the 10th Working Conference on Reverse Engineering, p.334, November 13-17, 2003
• 19: Periklis Andritsos , Vassilios Tzerpos, Information-Theoretic Software Clustering, IEEE Transactions on Software Engineering, v.31 n.2, p.150-165, February 2005 [doi>10.1109/TSE.2005.25]
• 20: Paolo Tonella, Concept Analysis for Module Restructuring, IEEE Transactions on Software Engineering, v.27 n.4, p.351-363, April 2001 [doi>10.1109/32.917524]
• 21: Brian S. Mitchell, A Heuristic Approach to Solving the Software Clustering Problem, Proceedings of the International Conference on Software Maintenance, p.285, September 22-26, 2003
• 22: Andy Zaidman , Serge Demeyer, Managing Trace Data Volume through a Heuristical Clustering Process Based on Event Execution Frequency, Proceedings of the Eighth Euromicro Working Conference on Software Maintenance and Reengineering (CSMR'04), p.329, March 24-26, 2004
• 23: Chenchen Xiao , Vassilios Tzerpos, Software Clustering Based on Dynamic Dependencies, Proceedings of the Ninth European Conference on Software Maintenance and Reengineering, p.124-133, March 21-23, 2005 [doi>10.1109/CSMR.2005.49]
• 24: Andrew Chan , Reid Holmes , Gail C. Murphy , Annie T. T. Ying, Scaling an Object-Oriented System Execution Visualizer through Sampling, Proceedings of the 11th IEEE International Workshop on Program Comprehension, p.237, May 10-11, 2003
• 25: Abdelwahab Hamou-Lhadj , Timothy C. Lethbridge, Compression Techniques to Simplify the Analysis of Large Execution Traces, Proceedings of the 10th International Workshop on Program Comprehension, p.159, June 27-29, 2002
• 26: Philippe Dugerdil, Using trace sampling techniques to identify dynamic clusters of classes, Proceedings of the 2007 conference of the center for advanced studies on Collaborative research, October 22-25, 2007, Richmond Hill, Ontario, Canada [doi>10.1145/1321211.1321254]
• 27: Dugerdil Ph., Jossi S. 2007. Role based clustering of software modules: an industrial experiment. Proc. ICSOFT 2007.
• 28: Ivar Jacobson , Grady Booch , James Rumbaugh, The unified software development process, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 29: Abdelwahab Hamou-Lhadj , Timothy Lethbridge, Summarizing the Content of Large Traces to Facilitate the Understanding of the Behaviour of a Software System, Proceedings of the 14th IEEE International Conference on Program Comprehension, p.181-190, June 14-16, 2006 [doi>10.1109/ICPC.2006.45]
• 30: http://www.graphviz.org/

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, Design, Experimentation

Keywords:
dynamic analysis, reverse-engineering, software architecture, software clustering