R. Barbudo, A. Ramírez, F. Servant and J.R. Romero*. "GEML: A grammar-based evolutionary machine learning approach for design-pattern detection". Journal of Systems and Software, 110919. 2021.

Design patterns (DPs) are recognised as a good practice in software development. However, the lack of appropriate documentation often hampers traceability, and their benefits are blurred among thousands of lines of code. Automatic methods for DP detection have become relevant but are usually based on the rigid analysis of either software metrics or specific properties of the source code. We propose GEML, a novel detection approach based on evolutionary machine learning using software properties of diverse nature. Firstly, GEML makes use of an evolutionary algorithm to extract those characteristics that better describe the DP, formulated in terms of human-readable rules, whose syntax is conformant with a context-free grammar. Secondly, a rule-based classifier is built to predict whether new code contains a hidden DP implementation. GEML has been validated over five DPs taken from a public repository recurrently adopted by machine learning studies. A second experiment increases this number up to 15 diverse DPs, showing its effectiveness and robustness in terms of detection capability. An initial parameter study served to tune a parameter setup whose performance guarantees the general applicability of this approach without the need to adjust complex parameters to a specific pattern. Finally, a demonstration tool is also provided.

Analysis of coverage threshold (ZIP, 27KB)

Analysis of support, confidence and classification strategy:

• Adapted grammar (ZIP, 65KB)
• Full grammar (ZIP, 64KB)

Analysis of full grammar vs. adapted grammar (ZIP, 35KB)

For this experiment, a repository has been built for training. It contains implementations of 15 design patterns, as well as negative samples. Here we describe how the samples are generated:

Positive samples

1. Instances available from the P-Mart repository (v1.2) are added, since they have been peer-reviewed.
2. Pieces of code for which both SSA and Ptidej tools agree in that they implement a design pattern are identified. The code belongs to the same Java projects considered in P-Mart.
3. Instances from step 2 are automatically processed and manually revised to match roles, since each tool provides different information and level of granularity.

Negative samples

1. The VF2 algorithm, available in the VFLib graph matching library, is executed to find group of classes that are structurally similar to the design pattern.
2. For each design pattern, we define heuristics to filter out instances. This process is required because the VF2 algorithm might return a high number of results. The heuristics check the type of relationship between classes playing roles, which is not taken into account in the previous step.
3. For each positive sample, a maximum of three negative samples are randomly selected from the project in which the positive sample was found.

The resulting repository is available for reproducibility purposes. It is provided for each design pattern separately:

• Abstract factory
• Adapter
• Bridge
• Command
• Composite
• Decorator
• Factory method
• Iterator
• Observer
• Proxy
• Singleton
• State
• Strategy
• Template method
• Visitor

The following files contain the detection rules for each design pattern. These rules correspond to the best detection model generated by the G3P algorithm after applying the pruning method (database coverage).

• Abstract factory
• Adapter
• Bridge
• Command
• Composite
• Decorator
• Factory method
• Iterator
• Observer
• Proxy
• Singleton
• State
• Strategy
• Template method
• Visitor

The next table shows the number of design pattern implementations found by each tool for the project DPExample. For each design pattern and tool, a file with the information of the implementations can be downloaded by clicking on the cell number. Symbol '-' stands for non-supported design patterns.

Note: For SSA and Ptidej, the number of DP implementations might not coincide with the number of raw results in the corresponding file. The reason is that each tool follows a different strategy to group the classes that implement each role. More specifically, we observe that SSA defines one instance for each combination of roles (only one class per role), while Ptidej puts together all classes implementing a multiple role (e.g. subclasses in a hierarchy).

1. Download the demonstration tool (ZIP, 31.7 MB)
   • Note: This tool has been tested for Java 8, in both Ubuntu 18.04 and Windows 10.
   • The full set of DP samples used in the experimentation are contained in the /data folder.
2. Unzip the file.
   • Note: Please do not write special characters or white spaces in the location path. Their use is restricted by the third-party library ckjm.
3. Download the VFLib graph matching library (ZIP, 216 KB)
   • Note: This tool uses the C++ implementation of the VF2 algorithm to generate the candidates. This folder should be located in the root folder of the tool. Follow the next steps to compile the library:
   • Run make
   • Execute g++ -c -I include/ designPattern.cc
   • Execute g++ -o designPattern designPattern.o -L lib -lvf -lstdc++ -lm
4. Download the example repository (ZIP, 70.9 MB)
   • These projects can be directly downloaded from the MARPLE website or the P-Mart repository (with the exception of DPExample).
   • Unzip the file into the /repo folder.
5. (Optionally) In case you want to skip Step 1 (Generation of candidates) and 2 (Learning of the detection model), please download the set of candidates, computed metrics and generated rules of the running example (ZIP, 26.4kB)
   • Note: Unzip this file into the root folder of the GEML application.

1. Execute the launch script.
   • Note: Depending on your OS, please run dpdtool.bat for Windows, or dpdtool.sh for GNU/Linux
2. Move to the "DP Candidates (project path)" tab:
   1. Under the "Set a new project path" label, select the Singleton pattern and click the button.
   2. Set the path of the target project, i.e., the project for which you want to detect the Singleton pattern instances.
      • Note: For this example, please select JRefactory, which is part of the DPB repository. It should be noted that the project folder requires a specific structure: (1) a /bin folder containing the ".class" files; (2) a /src folder containing the ".java" files; and (3) a /lib directory containing any external dependency in form of ".jar" files.
   3. GEML will automatically generate the list of candidates potentially implementing the Singleton pattern. This step depends on an external library (ckjm) and can take a few minutes, especially if you are running on Windows. When finished, the number of candidates will be reported.
      • Note: Click the button to save the set of pattern candidates and the computed software metrics, respectively. For reproducibility, notice that both files could be loaded later by clicking the button located under the label "Load an existing set of candidates".
3. Move to the "DPD Model (repository)" tab:
   1. Click the button, located under the label "Learn set of detection rules", to load the singleton.xml file, which contains the full parametrisation of the G3P4DPD algorithm.
      • Note: For those interested, notice that this file could be modified to set the values of some additional, internal-specific parameters. Nevertheless, the GUI allows the user to set the values of the support and confidence thresholds after loading this file.
   2. Click the button and deselect the JRefactory project to indicate that you are not interested in using it anymore for the generation of the DPD detection model. Click then Apply and Close.
   3. Select the set of properties to be used to characterise the design pattern implementations.
      • Note: In this example, select the common properties describing the Singleton pattern (explained in Section 6.2 of the paper): isFinal, isSubclass, controlledExcep, controlledInit, conglomeration, returns, receives, createObject, ctorVisibility, aggregation, redirectInFamily, NOM, NOC, DIT and RFC.
   4. Click to launch the G3P4DPD algorithm. When finished, the rules composing the detection model will be reported.
      • Note: Click to save the detection rules. For reproducibility, notice that this file could be loaded later by clicking the button, located under the label "Load an existing set of detection rules".
4. Select a classification strategy and click , located to the right of the label "Detection strategy".
   • Note: For this example, please select the DFML_lap.
5. Finally, after completing the execution, the detected design patterns will be reported.

DPB samples (positives and negatives) for the Singleton pattern (ZIP, 5.5kB). This file contains 9 XML files, one per project, including both positive and negative samples of the Singleton pattern, as used for the experimentation.

1. Unzip the DPB samples in the root folder of the GEML project.
2. Load the file containing the Singleton samples of the project we are interested in.
   • Note: For this example, please select jrefactory.xml file, which contains 10 samples (6 positives and 4 negatives).
3. Load the file /data/metrics.csv containing the metrics of all the projects from the DPB repository.
4. Generate a detection model for the Singleton pattern excluding the JRefactory project.
5. Execute the detection process selecting any classification strategy.