Abstract - lic thesis Niklas Pettersson

Towards Pattern Detection in Software

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

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

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 application and the number of found
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. We also provide a
simple heuristic method that always gives a planar graph, but may
effect accuracy. In our evaluation, it leaves accuracy unaffected or
increased in two 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 analyis, i.e., an application gaining from
design pattern knowledge. Such client analysis include anti-pattern
detection to report quality flaws, and detecting best-practice
patterns in large software to assure consistency between design
decisions and the implementation.



Travel reports

Licentiate seminars


Courses Spring 2016


Last modified on April 2006 by Anne Moe