High Accuracy Design Pattern Detection

Occurrences of design patterns in existing code conveys important information to software developers about the intent of the original author. Therefore, automated design pattern detection is highly desirable when it comes to understanding unknown code. However, existing design pattern detection tools often deliver different results on the same code. Their precision and recall has so far been insufficient to make design pattern detection part of modern integrated development environments and development practices. In this context, this thesis provides several contributions to the state of art. First, it points out that the widely disparate results are rooted in the fact that various authors model design pattern structure and behavior using different, hard to compare concepts. A realistic comparison is additionally inhibited by the lack of common test sets that could serve as a reference for the evaluation of design pattern detection tools. Accordingly, the first contribution of my thesis is a common benchmark for design pattern detection. It consists of software repositories of varying size and complexity that include deviations from straightforward applications of design patterns, thus preventing overfitting to a particular scenario. The benchmark is the practical basis for meaningful and practice-oriented comparisons. The conceptual basis for a comparison is provided by a formalism that allows expressing structure and behavior of pattern implementation whereas covering the concepts supported by the reviewed tools. In this formalism, design pattern implementations are viewed as sets of roles played by software entities. The specific structure and behavior of pattern implementations is captured by a set of constraints specified in a first-order-logic language. These constraints express program analyses at a generic level that can be implemented by static or dynamic analysis techniques, or any combination thereof. The current thesis explores two different instantiations of the conceptual approach: - Data fusion combines the outputs of several pattern detection tools that partly use complementary techniques. The manual validation of this approach yielded better precision and recall than each of the evaluated tools. The first step towards the automation of this approach was the development of a common metamodel of the core concepts and results of design pattern detection tools and the specification of a common exchange format. However, the data fusion approach was not implemented since it would have required implementation of DPDX in tools developed by other research groups, making the progress of my thesis dependent on their schedules. In addition, data fusion would have also combined the weaknesses of the used tools (e.g. bugs or bad run-time performance). - Technique fusion combines the core ideas of various pattern detection techniques within one tool. The resulting pattern detection tool, DPJF (an acronym for Design Pattern detection by Joining Forces), achieves for all analyzed design patterns on all benchmark projects 100% precision and significant (partly many-fold) improvements of recall compared to each of the four other evaluated tools. Notably, these improvements are not bought at the expense of speed. The high detection quality is achieved by a well-balanced combination of existing structural and behavioral analysis techniques whereas the good performance is achieved by empirically validated simplifications of the pattern detection techniques that were combined. By its improvement of all relevant parameters, my approach makes design pattern detection for program comprehension suitable for routine application by professional developers