Analysis and semi-automated detection of design-level similarity patterns in software

Abstract

Clones are similar program structures. Clones hamper software maintenance. Previous research focused on cloned code fragments, or simple clones, but clones occur at higher levels also. Recurring patterns of simple clones indicate high-level similarities, or structural clones. Detection of structural clones helps in program understanding, maintenance, reengineering, and unconventional forms of reuse. In this thesis, we first present an efficient token-based simple clone detection method, based on state-of-the-art string pattern matching techniques. A flexible tokenization process is introduced to customize clone detection. A novel data mining based technique is proposed to detect some useful structural clones. Analysis and visualization techniques for structural clones are also proposed. These clone detection techniques are implemented in a tool called Clone Miner. We validate Clone Miner output via experimentation, showing that it is useful, correct and scaleable. We finally discuss how the structural clonea??s concept extends the domain of program understanding and design recovery.