Design Pattern Recognition Based on Similarity Scoring and Secondary Subsystems

doi:10.19678/j.issn.1000-3428.0063345

Abstract

Abstract: Most existing design pattern methods directly match the pattern of the original system and the design patterns to identify pattern instances in a system.This introduces numerous false positive or false negative instances, which limits their recall and precision.Therefore, based on previous studies, this study further investigates the design pattern detection method based on similarity scoring and secondary subsystems.According to the relevant information extracted from the system, the system and design patterns are expressed in the form of directed graph/matrix.Subsequently, the system to be identified is divided into several subsystems.The subsystems are further disassembled and reorganized into secondary subsystems with the same number of classes and roles in the pattern to be identified.The similarity scoring algorithm is used to assess whether a secondary subsystem is a pattern instance, and the obtained instances are further processed obtain the final pattern instances.Experiments are performed on the JHotDraw, JRefactory, and JUnit open-source projects, where average recall rate of 96.7%, 91.7% and 100%, average precision of 94.9%, 91.5%, and 92.5%, and CPU time costs of 5 408 ms, 22 280 ms, and 3 284 ms, respectively, are obtained. The result shows that the precision and time efficiency are improved while a high recall rate is maintained.

Key words: design pattern recognition, precision, directed graph, secondary subsystem, software reverse engineering

摘要： 为寻找系统中的模式实例，现有设计模式识别方法多直接将原系统与设计模式进行匹配，从而引入大量的假阳性实例或假阴性实例，导致召回率和精确率降低。为此，在前期研究的基础上，进一步探索基于相似度评分与二级子系统的设计模式识别方法。根据从系统中提取的相关信息，将系统和设计模式表示为有向图/矩阵形式。将待识别系统划分为若干个子系统，并进一步拆解和重组为类个数与待识别模式中角色个数相等的二级子系统。利用相似度评分算法判断二级子系统是否为模式实例，同时对获取的实例做进一步处理，以得到最终的模式实例。在JHotDraw、JRefactory和JUnit三个开源项目上的实验结果表明，该方法的平均召回率分别达到96.7%、91.7%和100%，平均精确率分别达到94.9%、91.5%和92.5%，而CPU时间花费分别为5 408 ms、22 280 ms和3 284 ms，在保持高召回率的前提下提升了精确率和时间效率。

关键词: 设计模式识别, 精确率, 有向图, 二级子系统, 软件逆向工程

CLC Number:

TP311.5

WANG Lei, WANG Wenfa, SONG Huina, ZHANG Shuai. Design Pattern Recognition Based on Similarity Scoring and Secondary Subsystems[J]. Computer Engineering, 2023, 49(1): 210-222.

王雷, 王文发, 宋慧娜, 张帅. 基于相似度评分与二级子系统的设计模式识别[J]. 计算机工程, 2023, 49(1): 210-222.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0063345

http://www.ecice06.com/EN/Y2023/V49/I1/210

Figures/Tables 19

References

[1] AMPATZOGLOU A, et al.Building and mining a repository of design pattern instances:practical and research benefits[J].Entertainment Computing, 2013, 4(2):131-142.
[2] FONTANA F A, MAGGIONI S, RAIBULET C.Design patterns:a survey on their micro-structures[J].Journal of Software:Evolution and Process, 2013, 25(1):27-52.
[3] GAMMA E, HELM R, JOHNSON R, et al.Design patterns:elements of reusable object-oriented software[M].Boston, USA:Addison-Wesley, 1995.
[4] 王雷, 姜久雷, 王晓峰.基于Petri网的设计模式形式化描述[J].计算机工程, 2016, 42(7):33-36, 48. WANG L, JIANG J L, WANG X F.Formal description of design pattern based on Petri net[J].Computer Engineering, 2016, 42(7):33-36, 48.(in Chinese)
[5] YARAHMADI H, HASHEMINEJAD S M H.Design pattern detection approaches:a systematic review of the literature[J].Artificial Intelligence Review, 2020, 53(8):5789-5846.
[6] KRAMER C, PRECHELT L.Design recovery by automated search for structural design patterns in object-oriented software[C]//Proceedings of the 4rd Working Conference on Reverse Engineering.Washington D.C., USA:IEEE Press, 1996:208-215.
[7] 王雷.基于相似度评分、FSM和机器学习的设计模式识别[D].北京:中国矿业大学(北京), 2019. WANG L.Design pattern detection based on similarity scoring, FSM and machine learning[D].Beijing:China University of Mining & Technology, 2019.(in Chinese)
[8] 王雷.设计模式自动识别——原理、方法和工具[M].武汉:汉斯出版社, 2020. WANG L.Automatic design pattern detection-principles, methods and tools[M].Wuhan:Hans Publishing House, 2020.(in Chinese)
[9] LUITEL G, STEPHAN M, INCLEZAN D.Model level design pattern instance detection using answer set programming[C]//Proceedings of the 8th International Workshop on Modeling in Software Engineering.Washington D.C., USA:IEEE Press, 2016:13-19.
[10] TSANTALIS N, CHATZIGEORGIOU A, STEPHANIDES G, et al.Design pattern detection using similarity scoring[J].IEEE Transactions on Software Engineering, 2006, 32(11):896-909.
[11] YU D J.Efficiently detecting structural design pattern instances based on ordered sequences[J].Journal of Systems and Software, 2018, 142:35-56.
[12] MAYVAN B B.Design pattern detection based on the graph theory[J].Knowledge-Based Systems, 2017, 120:211-225.
[13] FAWAREH H J, ALSHIRA'H M.Detection a design pattern through merge static and dynamic analysis using altova and lambdes tools[J].International Journal of Applied Engineering Research, 2017, 12(19):8518-8522.
[14] ZHANG P, YU D J, WANG J J.A degree-driven approach to design pattern mining based on graph matching[C]//Proceedings of the 24th Asia-Pacific Software Engineering Conference.Washington D.C., USA:IEEE Press, 2017:179-188.
[15] DI MARTINO B, ESPOSITO A.A rule-based procedure for automatic recognition of design patterns in UML diagrams[J].Software:Practice and Experience, 2016, 46(7):983-1007.
[16] AL-OBEIDALLAH M, PETRIDIS M, KAPETANAKIS S.MLDA:a multiple levels detection approach for design patterns recovery[C]//Proceedings of the International Conference on Compute and Data Analysis.New York, USA:ACM Press, 2017:33-40.
[17] SHI N, OLSSON R.A.Reverse engineering of design patterns from Java source code[C]//Proceedings of the 21st International Conference on Automated Software Engineering.Washington D.C., USA:IEEE Press, 2006:123-134.
[18] PANICH A, VATANAWOOD W.Detection of design patterns from class diagram and sequence diagrams using ontology[C]//Proceedings of the 15th International Conference on Computer and Information Science.Washington D.C., USA:IEEE Press, 2016:1-6.
[19] CHATURVEDI A, GUPTA M, KUMAR S.Design pattern detection using genetic algorithm for sub-graph isomorphism to enhance software reusability[J].International Journal of Computer Applications, 2016, 135(4):33-36.
[20] BERNARDI M L, CIMITILE M, DE RUVO G, et al.Model checking to improve precision of design pattern instances identification in OO systems[C]//Proceedings of the 10th International Joint Conference on Software Technologies.Washington D.C., USA:IEEE Press, 2015:1-10.
[21] ALADIB L, LEE S P.Pattern detection and design rationale traceability:an integrated approach to software design quality[J].IET Software, 2019, 13(4):249-259.
[22] AL-OBEIDALLAH M G, PETRIDIS M, KAPETANAKIS S.A structural rule-based approach for design patterns recovery[C]//Proceedings of International Conference on Software Engineering Research, Management and Applications.Berlin, Germany:Springer, 2018:107-124.
[23] 肖卓宇, 何锫.多阶段可松弛的设计模式变体检测方法[J].华中科技大学学报(自然科学版), 2018, 46(1):26-31. XIAO Z Y, HE P.Multistage relaxing detection method for variants of design pattern[J].Journal of Huazhong University of Science and Technology (Natural Science Edition), 2018, 46(1):26-31.(in Chinese)
[24] DONG J, SUN Y T, ZHAO Y J.Compound record clustering algorithm for design pattern detection by decision tree learning[C]//Proceedings of International Conference on Information Reuse and Integration.Washington D.C., USA:IEEE Press, 2008:226-231.
[25] ZANONI M.On applying machine learning techniques for design pattern detection[J].Journal of Systems and Software, 2015, 103:102-117.
[26] CHIHADA A, JALILI S, HASHEMINEJAD S, et al.Source code and design conformance, design pattern detection from source code by classification approach[J].Applied Soft Computing, 2015, 26:357-367.
[27] CHATURVEDI S, CHATURVEDI A, TIWARI A, et al.Design pattern detection using machine learning techniques[C]//Proceedings of the 7th International Conference on Reliability, Infocom Technologies and Optimization (Trends and Future Directions).Washington D.C., USA:IEEE Press, 2018:1-6.
[28] ALHUSAIN S, COUPLAND S, JOHN R, et al.Towards machine learning based design pattern recognition[C]//Proceedings of the 13th UK Workshop on Computational Intelligence.Washington D.C., USA:IEEE Press, 2013:244-251.
[29] UCHIYAMA S, KUBO A, WASHIZAKI H, et al.Design pattern detection using software metrics and machine learning[C]//Proceedings of the 1st International Workshop on Model-Driven Software Migration.Washington D.C., USA:IEEE Press, 2011:38-47.
[30] UCHIYAMA S, KUBO A, WASHIZAKI H, et al.Detecting design patterns in object-oriented program source code by using metrics and machine learning[J].Journal of Software Engineering and Applications, 2014, 7(12):983-998.
[31] BARBUDO R, RAMÍREZ A, SERVANT F, et al.GEML:a grammar-based evolutionary machine learning approach for design-pattern detection[J].Journal of Systems and Software, 2021, 175:1-24.
[32] THALLER H, LINSBAUER L, EGYED A.Feature maps:a comprehensible software representation for design pattern detection[C]//Proceedings of the 26th International Conference on Software Analysis, Evolution and Reengineering.Washington D.C., USA:IEEE Press, 2019:207-217.
[33] MHAWISH M Y, GUPTA M.Software metrics and tree-based machine learning algorithms for distinguishing and detecting similar structure design patterns[J].SN Applied Sciences, 2019, 2(1):1-10.
[34] 冯铁, 靳乐, 张家晨, 等.基于堆叠泛化的设计模式检测方法[J].软件学报, 2020, 31(6):1703-1722. FENG T, JIN L, ZHANG J C, et al.Design pattern detection approach based on stacked generalization[J].Journal of Software, 2020, 31(6):1703-1722.(in Chinese)

Please choose a citation manager

Content to export