A novel approach to optimize clone refactoring activity

ABSTRACT

Software evolution and software quality are ever changing phenomena. As software evolves, evolution impacts software quality. On the other hand, software quality needs may drive software evolution strategies.This paper presents an approach to schedule quality improvement under constraints and priority. The general problem of scheduling quality improvement has been instantiated into the concrete problem of planning duplicated code removal in a geographical information system developed in C throughout the last 20 years. Priority and constraints arise from development team and from the adopted development process. The developer team long term goal is to get rid of duplicated code, improve software structure, decrease coupling, and improve cohesion.We present our problem formulation, the adopted approach, including a model of clone removal effort and preliminary results obtained on a real world application.

REFERENCES

• 1: Giuliano Antoniol , Aniello Cimitile , Giuseppe A. Di Lucca , Massimiliano Di Penta, Assessing Staffing Needs for a Software Maintenance Project through Queuing Simulation, IEEE Transactions on Software Engineering, v.30 n.1, p.43-58, January 2004 [doi>10.1109/TSE.2004.1265735]
• 2: G. Antoniol, U. Villano, E. Merlo, and M. Di Penta. Analyzing cloning evolution in the linux kernel. Information and Software Technology, 44:755--765, October 2002.
• 3: B. S. Baker, On finding duplication and near-duplication in large software systems, Proceedings of the Second Working Conference on Reverse Engineering, p.86, July 14-16, 1995
• 4: 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
• 5: E. Buss , R. De Mori , W. M. Gentleman , J. Henshaw , H. Johnson , K. Kontogiannis , E. Merlo , H. A. Müller , J. Mylopoulos , S. Paul , A. Prakash , M. Stanley , S. R. Tilley , J. Troster , K. Wong, Investigating reverse engineering technologies for the CAS program understanding project, IBM Systems Journal, v.33 n.3, p.477-500, July 1994
• 6: P. C. Chu , J. E. Beasley, Constraint Handling in Genetic Algorithms: The Set Partitioning Problem, Journal of Heuristics, v.4 n.4, p.323-357, December 1998 [doi>10.1023/A:1008668508685 ]
• 7: P. C. Chu , J. E. Beasley, A Genetic Algorithm for the Multidimensional Knapsack Problem, Journal of Heuristics, v.4 n.1, p.63-86, June 1998 [doi>10.1023/A:1009642405419 ]
• 8: J. A. Clark, J. J. Dolado, M. Harman, R. M. Hierons, B. Jones, M. Lumkin, B. S. Mitchell, S. Mancoridis, K. Rees, M. Roper, and M. J. Shepperd. Formulating software engineering as a search problem. IEE Proceedings - Software, 150(3):161--175, 2003.
• 9: E. J. Coffman, M. Garey, and D. Johnson. Approximation algorithms for bin-packing. In Algorithm Design for Computer System Design, 1984.
• 10: Lawrence Davis, Job Shop Scheduling with Genetic Algorithms, Proceedings of the 1st International Conference on Genetic Algorithms, p.136-140, July 01, 1985
• 11: Emanuel Falkenauer, Genetic Algorithms and Grouping Problems, John Wiley & Sons, Inc., New York, NY, 1998
• 12: Emanuel Falkenauer, Genetic Algorithms and Grouping Problems, John Wiley & Sons, Inc., New York, NY, 1998
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 15: D. Greer and G. Ruhe. Software release planning: an evolutionary and iterative approach. Information and Software Technology, 46(4):243--253, 2004.
• 16: E. Hart, D. Corne, and P. Ross. The state of the art in evolutionary scheduling. Genetic Programming and Evolvable Machines, 2004 (to appear).
• 17: 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
• 18: J. Karlsson, C. Wohlin, and B. Regnell. An evaluation of methods for priorizing software requirements. Information and Software Technology, 39:939--947, 1998.
• 19: Colin Kirsopp , Martin J. Shepperd , John Hart, Search Heuristics, Case-based Reasoning And Software Project Effort Prediction, Proceedings of the Genetic and Evolutionary Computation Conference, p.1367-1374, July 09-13, 2002
• 20: K. Kontogiannis, R. D. Mori, R. Bernstein, M. Galler, and E. Merlo. Pattern matching for clone and concept detection. Journal of Automated Software Engineering, March 1996.
• 21: Jean Mayrand , Claude Leblanc , Ettore Merlo, Experiment on the Automatic Detection of Function Clones in a Software System Using Metrics, Proceedings of the 1996 International Conference on Software Maintenance, p.244, November 04-08, 1996
• 22: T. J. McCabe. Reverse engineering reusability redundancy: the connection. American Programmer, 3:8--13, October 1990.
• 23: E. Merlo , G. Antoniol , M. Di Penta , V. F. Rollo, Linear Complexity Object-Oriented Similarity for Clone Detection and Software Evolution Analyses, Proceedings of the 20th IEEE International Conference on Software Maintenance, p.412-416, September 11-14, 2004
• 24: M. Neteler, editor. GRASS 6.1 Programmer's Manual. Geographic Resources Analysis Support System. ITC-irst, Italy, http://grass.itc.it/devel/, 2005.
• 25: G. R. Raidl. An improved genetic algorithm for the multiconstrained 0-1 knapsack problem. In Proceedings of International Conference on Evolutionary Computation, pages 207--211, 1998.
• 26: J. David Schaffer, Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, Proceedings of the 1st International Conference on Genetic Algorithms, p.93-100, July 01, 1985
• 27: E. Talbi. Métaheuristiques pour l'optimisation combinatoire muli-objectif : État de l'art. TR 98-757.33, Laboratoire d'Informatique Fondamentale de Lille, Université des Sciences et Technologies de Lille, 2001.

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, Measurement

Keywords:
effort prediction, evolution modeling, genetic algorithms, multi-objective optimization, refactoring effort, software quality improvement