Customizable Feature-Based Design Pattern Recognition Integrated Techniques

Introduction and Motivation for Design Pattern Recovery

• Definition of Design Patterns: A design pattern offers guidelines on when, how, and why an implementation can be created to solve a general problem in a particular context, based on the Gang of Four (GoF) definitions.

• Applications of Design Patterns: They are utilized across software architectures, interfaces, security, and services. Implementing design patterns can lead to a productivity increase of approximately $25\%-40\%$.

• Need for Recovery: Design pattern recovery is essential for various software engineering tasks, including:

  • Software maintenance.

  • Re-documentation.

  • Reverse engineering.

  • Reengineering.

• Goals for Accuracy: The primary goal is to achieve high accuracy in pattern detection despite various challenges.

Challenges in Current Pattern Detection

• Variation Challenges: Detection is complicated by structural and implementation variants.

• Disparity in Results: Different results arise due to varied pattern specifications and multiple ways to implement different relations.

• Limitations of Techniques: Current methods often struggle with detecting overlapping patterns and providing multi-language support (recovering patterns from different programming languages).

• Singleton Variations Example:

  • Inaccurate Identification: A pattern might be inaccurately recognized as a Singleton if the getInstance() method simply returns a new instance every time: return new Singleton();.

  • Correct Identification: A correctly identified Singleton involves checking if (instance == NULL) instance = new Singleton(); return instance;.

• Overlapping Examples: Real software systems often contain overlapping patterns, such as an object acting as part of an Adapter, a Proxy, and a Bridge simultaneously.

State of the Art: Classification and Techniques

• Structural Analysis Based Techniques: These focus on extracting structural relationships between classes.

• Behavioral Analysis Based Techniques: These involve dynamic analysis, machine learning, and static program analysis to understand the runtime interactions.

• Structural and Behavioral Analysis Based Techniques: These combine both methods to reduce the search space and improve recovery accuracy.

• Structural, Behavioral, and Semantic Analysis Based Techniques: These aim to further improve accuracy by detecting false negatives using semantic information.

Representative Current Approaches and Tools

• Gueheneuc et al. (PTIDEJ): Uses a constraint solver and numerical signature for Java. Patterns targeted include SI, FM, AD, DE, CP, CD, VR, OB, TM, ST/SR, BU, AF. Precision: $57\%$.

• Pettersson et al. (CrocoPat): Uses database queries for Java (SWT, Swing). Targets SI, OB. Precision: $75\%$.

• Lucia et al. (DPRE): Uses XPG formalism and LR parsing for Java (JHotDraw, Quick UML). Targets AD, PR, BR, DE, CM, FA, FL. Precision: $62\%-97\%$.

• Gueheneuc et al. (DeMIMA): Uses a constraint solver for Java. Precision: $37\%$.

• Dong et al. (DP-Miner): Uses matrix and weight techniques for Java. Precision: $95\%$.

• Stencel et al. (D³): Uses database queries for Java. Precision: Not Mentions (NM).

• Tsantalis et al. (DPD): Uses a similarity matrix for Java. Precision: $100\%$.

• Shi and Olsson (PINOT): Uses data/control flow analysis for Java. Precision: NM.

• Nierre et al. (FUJABA): Uses fuzzy logic and dynamic analysis for Java. Precision: NM.

• Smith and Scot (SPQR): Uses Rho-Calculus for C++. Precision: NM.

Critical Review and Requirement Elicitation

• Critical Review Findings:

  • Significant problems with variations and wide disparity in results.

  • Experiments are often performed on very few patterns.

  • Overlapping and composition of patterns are frequently missed.

  • Most tools only support a single language (primarily Java or C++).

• Requirements for the Approach (Req1-Req5):

  • Req1: Improving accuracy.

  • Req2: Variant handling.

  • Req3: Overlapping detection.

  • Req4: Evaluation of the approach.

  • Req5: Multiple language support.

Concept of Approach: Multiple Integrated Techniques

• Key Concepts:

  • Integration of multiple searching techniques and analysis methods.

  • Customizable pattern definitions to enable variants detection.

  • Experiments conducted on all types of Gang of Four (GoF) patterns.

  • Overlapping detection limited to structural design patterns.

  • Creation of an intermediate representation using the Enterprise Architect Modeling Tool.

• Phase I: Creating Pattern Definitions:

  • Uses customizable and comprehensible "Feature types" to create pattern definitions.

• Phase II: Pattern Recognition:

  • Based on integrated searching techniques including SQL, Source code parsers, and Regular Expressions (RegEx).

Feature Types and Pattern Definition Process

• Feature Type Parameters: Each feature type is defined by specific parameters:

  • Name.

  • Query.

  • Parameter.

  • Count of previous result.

  • Search method.

  • Report result.

• Negative Feature Types: Used specifically to filter out false positives during the detection process.

• Reusing Features (Examples):

  • Object Adapter: Uses features like F1 (Get All Classes), F2 (Has Inheritance), F3 (Has Common Operation), F5 (Has Delegation), F7 (Has No Inheritance), F8 (Has No Direct Access).

  • Class Adapter: Shares many features with Object Adapter but adds specifically labeled inheritance (e.g., F2: Has Inheritance (C2, C3)).

  • Proxy: Uses a combination of features like F1, F2, F4 (Has Association), F5, F6, and F8.

Pattern Recovery Technique: Static Architecture

• The Architecture View:

  • Source code is reverse-engineered into a source code model.

  • This is converted into an SQL model for structural analysis.

  • A "Recognition Controller" iterates through feature types of a pattern definition.

  • It applies recognition technologies depending on the feature type (RegEx matcher, Source code parser, Annotation analyzer, or SQL query).

  • Results are pruned and expanded to identify candidate patterns.

• Searching Technologies:

  • SQL: Extracts structural information from the database model; customizable but requires internal knowledge of the data structure.

  • Regular Expressions (RegEx): Extracts information not available in the model directly from source code (limitations in nested information extraction).

  • Source Code Parsers: Based on static program analysis; used to extract behavioral information. Requires additional effort for every new language.

Parser Module and Semantic Annotations

• Architecture of Parser Module:

  • Input: Grammar Files.

  • Tool: Coco/R Parser Generator.

  • Output: Specific scanners and parsers for Java, C#, and C++.

  • Components include Delegation Parser, Aggregation Parser, Method Return Type Parser, and Method Invocation Parser.

• Annotations for Semantic Information:

  • Optional in the recognition process but useful for extracting semantic intent.

  • Helps reduce the search space for pattern detection.

  • Examples:

    • @compose {object} from {different_objects | related_objects}

    • @decouple {receiver} from {sender}

    • @provide {handlers} for {requests | expressions}

    • @traverse {object_list | composite_list}

Prototyping Tool: EA Add-In

• Tool Features:

  • Developed as an Add-In for the Enterprise Architect (EA) Modeling Tool.

  • Utilizes the concepts of customizable feature types and pattern definitions.

  • Scalable and flexible for extension to multi-language and other pattern types.

  • Presentation module visualizes identification results and overlaps (Class view, table view, and report view).

• Abstract Architecture:

  • Data Module: Handles SQL queries via EA.

  • Code Module: Handles RegX and Source Code Parsers (SCP) via Visual Studio .Net framework.

  • Presentation Module: Displays the Pattern Matcher results as identified roles and verified properties.

Evaluation Methodology

• Benchmarks Selection Criteria:

  • Available publicly and implemented using known design patterns.

  • Varied sizes from small to very large.

  • Examples across multiple languages (Java, C++, C#).

• Accuracy Metrics:

  • Precision ($P$): $\frac{TP}{TP + FP}$, assuming Precision is $100\%$ if $|TP| = |FP| = 0$.

  • Recall ($R$): $\frac{TP}{TP + FN}$.

  • F-Score: $\frac{(1 + w^2) \times P \times R}{w^2 \times P + R}$, where $w = 2\sqrt{2} \approx 2.8$.

Experimental Setup and Statistical Results

• Selected Systems Data:

  • Junit 3.7 (Java): $1.46\,MB$, $78$ files, $43$ classes.

  • JHotDraw 5.1 (Java): $4.85\,MB$, $144$ files, $136$ classes.

  • JRefactory 2.6.24 (Java): $12.5\,MB$, $569$ files, $562$ classes.

  • QuickUML 2001 (Java): $3.39\,MB$, $152$ files, $204$ classes.

  • Apache Ant 1.6.2 (Java): $26.6\,MB$, $687$ files, $883\,classes$.

  • Galb++ 2.4 (C++): $1.17\,MB$, $135$ files, $98$ classes.

  • Libg++ 2.7.2 (C++): $8.86\,MB$, $99$ files, $208$ classes.

• Extracted Results (Junit 3.7 Adapter):

  • Patterns identified: $6(6, 0)$.

  • Precision ($P$): $1.0$.

  • Recall ($R$): $1.0$.

• Performance Comparison against P-Mart:

  • Junit 3.7: P-Mart Precision ($44\%\rightarrow 98\%$), Recall ($100\%\rightarrow 100\%$), F-score ($87\%\rightarrow 99\%$).

  • Overall Improvement: The research shows an overall improvement of approximately $10\%-22\%$ over existing methodologies like P-Mart.

Conclusions and Future Work

• Conclusions:

  • Successfully integrated multiple search techniques to improve precision, recall, and F-Score.

  • Customization of definitions effectively detects both structural and implementation variants.

  • Detecting overlaps aids in software comprehension and maintenance.

  • Support for multiple languages has been established.

• Future Directions:

  • Extend detection to architectural and J2EE patterns.

  • Further extension for diverse programming languages.

  • Enhance visualization of compositions and overlaps.

  • Automate the translation of UML structures into pattern definitions.

  • Develop refined annotation mechanisms for deep semantic analysis.

  • Integrate prototyping tool output formats with other software engineering tools.