Towards Pattern Detection in Software

Sammanfattning: 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.