Detection of design pattern occurrences is part of several solutions to software engineering problems, and high accuracy ofdetection is important to help solve the actual problems. The improvement in accuracy of design pattern occurrence detection requiressome way of evaluating various approaches. Currently, there are several different methods used in the community to evaluateaccuracy. We show that these differences may greatly influence the accuracy results, which makes it nearly impossible to compare thequality of different techniques. We propose a benchmark suite to improve the situation and a community effort to contribute to, andevolve, the benchmark suite. Also, we propose fine-grained metrics assessing the accuracy of various approaches in the benchmarksuite. This allows comparing the detection techniques and helps improve the accuracy of detecting design pattern occurrences.

Pattern detection in software systems is one of several collaborating techniques for reverse engineering and program comprehension. Unfortunately, it is a hard problem in both theory and practice. A recent method to increase efficiency is based on conservatively filtering edges of a software system's structure graph, i.e., only removing edges guaranteed not to be part of any pattern instance. This leads to planar graphs in many cases allowing for efficient matching algorithms. This paper shows the feasibility of a non-conservative filtering approach, where even edges possibly part of a pattern instance can be removed to reach planarity. We show theoretically that not only decreased accuracy is possible due to non-conservative filtering, but also increased accuracy. We also perform an experimental evaluation supporting this statement. The paper complements the safe filtering method and together the two approaches allow for efficient pattern detection for all systems and patterns.

Pattern detection is part of many solutions to software engineering

problems. Unfortunately, it is a hard problem in itself in both theory and practice. Both exact and approximative approaches have been used earlier to increase efficiency. We propose a novel method to improve the performance of pattern detection, which is in many cases both exact and efficient. It is based on the idea of filtering information from the program representation (graphs),

which is unnecessary for detecting a particular pattern. This makes the remaining program representation graph planar, in many cases, thus allowing for linear pattern detection. We evaluate our approach experimentally: we detect six design patterns in six software systems. Filtering leads to planar program representation graphs in 14 out of 36 cases. For most of the remaining graphs, filtering makes the graphs almost planar and gives a significant reduction of the graph size, which speeds up existing heuristics.

Pattern detection is part of many solutions to software engineering problems and high accuracy of detection is important to help solve the actual problems. The improvement in accuracy of design pattern detection approaches requires some way of evaluating competing approaches. Currently, there are slightly different methods used in the design pattern detection community to evaluate accuracy. We show that these differences may greatly influence the accuracy results, which makes it nearly impossible to compare the quality of different pattern detectors. We do not propose a uniform solution, but rather a description framework, which can be used to improve the situation. We also propose a community effort to create a standard benchmark suit for evaluations.

This thesis investigates methods to improve the detection of design patterns in software systems. Design pattern detection may be used to aid other tasks, such as architectural recovery of systems with poor documentation, measurement of software quality, and optimization of software systems.

A design pattern can be implemented in several different ways, i.e., by different idioms (or patterns). Such idioms are characterized by their structure and behavior. Therefore, a pattern detector should compare the structure of a

pattern with the structure of the software system to find possible candidates. It should also compare the behavior of the pattern with the behavior of the software system to find run-time candidates. The pattern instances fulfilling both the structural and behavioral properties of the pattern should be reported as matches. Some design patterns are harder to detect than others with high

accuracy because their implementations are neither unique nor distinctive.

The analysis of software is either static or dynamic. While static analysis uses the source code as input, dynamic analysis use data produced at run-time instead. We perform the detection of structure using static analysis, and the

detection of behavior using dynamic analysis.

There are two main contributions of this licentiate. First, we structure and present the problems and the existing partial solutions. We also identify areas of improvement, e.g., immature methods to measure accuracy and efficiency of static analysis.

Second, we address the efficiency problem by developing a process to reduce program graphs to planar graphs, which allows static analysis in linear time (in the size of the program and the number of pattern instances) using existing

techniques from theoretical computer science. However, the developed method does not give planar graphs for any combination of patterns and software systems. In our evaluation, it succeeds in half the cases. We also provide a simple heuristic that always gives a planar graph, but may effect accuracy.

In our evaluation, it leaves accuracy unaffected or increased in two out of three cases.

To finish the dissertation, we will improve the methods used to evaluate accuracy. We will also improve the detection itself by refining our developed methods for analysis of structure, adding static analysis of

behavior, and improving dynamic analysis.

We will also contribute to client analysis, i.e., an application gaining from design pattern knowledge. Such client analysis include anti-pattern detection to report quality flaws, and detecting patterns in software to assure consistency between the design and the implementation.