一种基于相似度评分的设计模式识别方法

王雷　宋慧娜　王文发

摘   要：使用软件工具自动识别UML（Unified Modeling Language）模型中包含的设计模式，可以帮助软件开发人员理解、维护和重构大型软件项目. 现有设计模式识别方法大多是将所考虑的若干个特征分别进行匹配，准确率和时间性能不高. 为此，提出了一种基于相似度评分的设计模式识别方法. 首先，给出该方法的基本流程;然后，提出一种基于有向图/矩阵的设计模式和系统的表示;接着，详细讨论了基于相似度评分的模式实例搜索算法;最后，实现了该方法的支撑工具，并使用该工具对一个开源项目进行了设计模式的识别.该方法不是将所考虑的若干个特征分别进行匹配，而是使用总特征矩阵进行匹配. 实验结果表明，相对于将所考虑的若干个特征分别进行匹配的方法，该方法的识别准确率和时间性能更高.

关键词：设计模式识别;准确率;时间性能;有向图;软件逆向工程

中图分类号：TP311.5 文献标志码：A

A Design Pattern Detection Method Based on Similarity Scoring

WANG Lei1，2?，SONG Huina1，WANG Wenfa1

（1.College of Mathematics and Computer Science，Yan′an University，Yan′an 716000，China;

2.School of Mechanical Electronic and Information Engineering，China University of Mining

and Technology （Beijing），Beijing  100083，China）

Abstract：Detecting design pattern instances in UML models by using software tools can help software developers to understand，maintain and reconstruct the large-scale software projects. Most of the existing methods for automatic design pattern detection let the several considered features match separately，so that the accuracy rate and time performance are not high enough. Therefore，a design pattern detection method based on similarity scoring was proposed. First，the basic process of this method was given; then，a representation of system and patterns based on directed graph/matrix was proposed; the pattern instance search algorithm based on similarity scoring was discussed in detail; finally，a supporting tool for this method was implemented，and design patterns in an open source project were detected by using this tool. This method does not let the several considered features match separately，but uses the integral feature matrixes to match. The experimental results show that，compared with the design pattern detection methods which let the several considered features match separately，the detection accuracy rate and time performance of this method are higher.

Key words：design pattern detection;accuracy;time performance;directed graph;software re-engineering

设计模式使人们可以更加简单方便地利用成功的设计和体系结构，其在大型软件项目的开发中得到了广泛的应用. 从源代码或统一建模语言（UML，unified modeling language）模型中自动识别出相应的设计模式，可以为面向设计模式的软件理解、维护和重构等活动提供自动化支持[1].因此，设计模式的自动识别成为目前逆向软件工程领域的一个研究热点.

近年来，国内外的相关文献已经提出很多设计模式自动识别的方法.许涵斌等[2]、Yu等[3]、Bernardi等[4-6]将系统和设计模式以有向图的形式呈现，通过图同构判定算法在系统图中寻找模式子图;Dong等[7-8]将泛化、关联、抽象、不同的调用方式等8个设计特征编码到有向图/矩阵中，并将8个矩阵组合成一个矩阵，使用模板匹配算法计算系统和设计模式之间的互相关值来寻找系统中存在的模式实例;Tsantalis等[9]将源代码和设计模式的关联、泛化、抽象类、对象创建、抽象方法调用等信息均表示为一个单独的有向图/矩阵，使用相似度评分算法[10]计算各子系统与设计模式之间的相似度矩阵来寻找子系统中的模式实例;Costagliola等[11-12]和 Lucia等[13-14]将可缩放矢量图形（SVG，scalable vector graphics）格式用于源代码的中间表示，而设计模式用视觉語言表示，通过将每种模式的视觉语言语法与系统的SVG表示进行映射来恢复模式;Balanyi等[15]使用一种基于XML的语言进行设计模式描述，用Columbus框架分析C ++源代码并从中构建抽象语义图（ASG，abstract semantic graph），通过将模式与ASG匹配来寻找模式实例;Bernardi等[16-18]将设计模式的行为属性表示为选择性μ演算公式，将文献[4-6]得到的候选实例（Java文件或字节码）转换为时序规范语言（LOTOS，Language of Temporal Ordering Specification）模型，使用模型检测工具CADP验证候选实例是否满足μ演算公式来判断候选实例是否为模式实例;与Bernardi等[16-18]方法类似，Lucia 等[19]使用工具SPIN验证文献[11-14]得到的候选实例是否满足设计模式的行为属性转换得到的线性时态逻辑（LTL，Linear Temporal Logic）公式，来判断候选实例是否为模式实例;Wendehals等[20]将行为型模式的行为特征转换为有限自动机，并将候选实例的方法调用与有限自动机进行匹配，以此来判断候选实例是否为模式实例;Zhu等[21]使用LAMBDES系统将待识别系统的UML图转换为一组一阶逻辑（FOL，first order logic）语句，借助定理证明器SPASS验证设计是否符合用FOL描述设计模式的结构特征和行为特征[22-24];苗康等[25]借用关系演算语言UTP描述系统和设计模式，通过关系演算算法检查系统是否满足模式的属性;Kim等[26]计算系统每个类的面向对象度量、结构型度量和过程型度量3 种产品度量，并将这些度量与支撑工具中嵌入的模式签名进行比较，根据匹配程度判断是否模式实例;Hayashi等[27]将从待识别系统中抽取到的信息表示为Prolog中的事实，执行定义为Prolog中的规则的检测条件，来推断满足设计模式条件的类结构的存在;类似工作，Luitel等[28]将待识别系统的类图和序列图表示为ASP中的事实，使用ASP求解器输出分别遵循描述结构模式和行为模式的规则的结构和行为元素.

综上所述，国内外的相关文献已经将图论算

法[2-9]、视觉语言解析技术[11-14]、XML匹配[15]、形式化验证技术[16-21，25]、软件度量的匹配[26]、逻辑推理[27-28]等多种匹配技术引入到设计模式的搜索中来. 这些方法大多是将所考虑的若干个特征分别进行匹配. 单个特征的匹配并不能保证整体匹配，反之亦然. 此外，多次匹配需要耗费大量的时间，因此识别准确率和时间性能并不高.

本文提出一种基于相似度评分的设计模式识别方法，并实现了该方法的支撑工具. 该方法将所考虑的7个特征对应的矩阵组合成一个总特征矩阵，并使用总特征矩阵进行匹配，具有更高的识别准确率和时间性能.

1   基本流程

本文将关联、泛化、依赖、聚合、抽象类、对象创建、抽象方法调用等特征对应的矩阵组合成一个总特征矩阵，通过计算子系统和设计模式的总特征矩阵之间的相似度矩阵来寻找子系统中的模式实例. 基本流程如图1所示.

2   系统和设计模式的表示

本文使用相似度评分算法计算系统和设计模式之间的相似度矩阵来寻找系统中存在的模式实例，因此需要将系统和设计模式表示为有向图/矩阵形式. 本文考虑关联、泛化、依赖、聚合、抽象类、对象创建、抽象方法调用7个特征. 设系统和设计模式的类图为G，类图G中的类为 c1，c2，…，cn，下面给出系统和设计模式的矩阵表示的一种形式化定义.

定义1  类图G的关联关系矩阵定义为：

c1   c2   …   cj  …  cn

MAss

G    =

rij                    （1）

其中

rij = 1，类ci到cj之间存在关联关系

0，类ci到cj之间不存在关联关系

类似地可以定义类图G的泛化关系矩阵MGen

G    、依赖关系矩阵MGep

G    、聚合关系矩阵MAgg

G    和抽象方法调用矩阵MInv

G    .

定义2   类图G的抽象类矩阵定义为：

c1   c2   …   cj  …  cn

MAbs

G    =

rij                     （2）

其中

rij = 1，i = j且类ci为抽象类

0，其他

定义3   类图G的对象创建矩阵定义为：

c1   c2   …   cj  …  cn

MCre

G   =

rij                     （3）

其中

rij = 1，i = j且类ci为抽象类

0，其他

为提高识别的准确率和时间性能，本文借鉴Dong等人[7-8]的方法，将所考虑的7个特征对应的7个有向图/矩阵组合成一个有向图/矩阵. 我们给每个矩阵一个不同素数的根值，然后将每个矩阵的单元值（x）更改为新值，新值为其根（root）的旧单元值次幂（rootx）. 总特征矩阵的每个单元的值为这7个新矩阵中相应单元值的乘积. 这里，对于每种模式，我们根据模式中涉及到每种特征的类的个数将7个特征进行排序，并按照顺序将7个特征的根值分别设为素数2、3、5、7、9、11和13. 例如，對于装饰模式，有2个类涉及到关联关系，有4个类涉及到泛化关系，有0个类涉及到依赖关系和聚合关系，有3个类涉及到抽象方法调用，有2个类涉及到抽象类，2个类涉及到对象创建，则将关联、泛化、依赖、聚合、抽象方法调用、抽象类、对象创建的根值分别设为素数9、13、3、2、11、7和5. 由此可得类图G关于模式p的总特征矩阵定义如下.

定义4   设 分别为关联、泛化、依赖、聚合、抽象方法调用、抽象类、对象创建的关于p的根值，则类图G的关于模式p的总特征矩阵定义为：

c1   c2   …   cj  …  cn

MInteg

G，p    =

rij                     （4）

其中

rij = root1·root2·root3·root4·

root5·root6·root7

以装饰模式和开源项目JHotDraw 5.2为例说明设计模式和系统的表示. 为了便于说明问题，仅考虑JHotDraw 5.2的一个子系统（见3.1节），记为s. 装饰模式和子系统s的UML类图描述分别如图2和图3所示.

Component、 ConcreteComponent、 Decorator和ConcreteDecorator分别为c1、c2、c3和c4，根据结构特征矩阵的定义，可得：

c1   c2   c3   c4

MAss

decorator  = 0    0    0    0

0    0    0    0

1    0    0    0

0    0    0    0      （5）

c1   c2   c3   c4

MGen

decorator    = 0    0    0    0

1    0    0    0

1    0    0    0

0    0    1    0      （6）

MDep

decorator    = Aggdecorator = 0     （7）

c1   c2   c3   c4

MInv

decorator    = 0    0    0    0

0    0    0    0

1    0    0    0

0    0    1    1      （8）

c1   c2   c3   c4

MAbs

decorator    = 1    0    0    0

0    0    0    0

0    0    1    0

0    0    0    0      （9）

c1   c2   c3   c4

MCre

decorator    = 0    0    0    0

0    0    0    0

1    0    0    0

0    0    0    0      （10）

根據总特征矩阵的定义，可得：

类似地，记Storable、Figure、AbstractFigure、CompositeFigure、DecoratorFigure、GroupFigure和BorderDecorator分别为C1、C2、C3、C4、C5、C6和C7，可以得到子系统s的总特征矩阵为

（12）

3   设计模式的自动识别

3.1   子系统的划分

为从系统中搜索模式实例，需要将待考查系统划分为若干子系统. 根据待识别的设计模式所含继承层的个数，划分子系统有以下两种方法.

1）如果设计模式不包含继承层或只包含一个继承层，则将待考查系统的每个继承层划分为一个独立的子系统. 此时，子系统的个数和系统的继承层个数相等. 该类设计模式包括15种设计模式：生成器、原型、单例、组合、装饰、享元、代理、职责链、命令、解释器、备忘录、状态、策略、模板方法和访问者.

2）如果设计模式包含两个继承层，则每次从所有的继承层中选择两个划分为一个子系统. 此时，子系统的个数为，其中m为系统中继承层的个数. 该类设计模式包括8种设计模式：抽象工厂、工厂方法、适配器、桥接、外观、迭代器、中介者和观察者.

3.2   相似度矩阵的计算

对于每种设计模式，首先根据其所含继承层的个数，将待考查系统划分为m或个子系统（m为系统中继承层的个数）. 然后依次计算各子系统的关于该模式的总特征矩阵和设计模式总特征矩阵之间的相似度矩阵.

以装饰模式和子系统s为例来说明相似度评分的计算. 经计算可得（函数Similarity（）对应文献[7]第3.1节中的相似度评分算法），子系统s和装饰模式之间的相似度矩阵为：

MSimilarity

s，decorator   = Similarity（MInteg

decorator，decorator，MInteg

s，decorator）=

c1               c2              c3              c4

0.000 0     0.000 0     0.000 0     0.000 0

0.996 6     0.000 2     0.001 2     0.000 2

0.000 3     0.000 0     0.000 3     0.000 0

0.000 0     0.002 0     0.000 0     0.000 0

0.001 2     0.000 0     0.998 4     0.000 2

0.000 0     0.000 0     0.000 0     0.000 0

0.000 0     0.000 0     0.000 0     0.000 1 （13）

3.3   基于相似度矩阵的设计模式识别

获取子系统和某种设计模式之间的相似度矩阵 MSimilarity

s，p          后，就可以根据相似度矩阵找出系统中包含的该种设计模式的实例.

通常情况下，对于每种设计模式，每个子系统只包含该设计模式的一个实例，此时每个模式角色关联子系统中的一个类[29].提出的方法目前只考慮子系统包含待识别模式的一个实例的情况，多个实例的情况将在后续的研究中进行讨论.

相似度矩阵MSimilarity

s，p          的元素表示两个类之间的相似度得分. 所以，需要选择一个值，当相似度得分大于该值时，就认为这两个类匹配.将该值称为匹配临界值，记为v.

根据子系统和某种设计模式之间的相似度矩阵识别该种设计模式的算法如下：

步骤1   依次判断MSimilarity

s，p          的每列，若至少存在一列中的某个元素的值大于等于匹配临界值v，则说明该子系统包含模式p;否则不包含.

步骤2   若包含模式p，则需要找到该模式的每个角色在子系统s中关联的类. 依次考查MSimilarity

s，p          的每列，从中找出值最大的元素，则该列对应的设计模式角色关联该元素所在行对应的子系统类.

若临界值v选取过大，则可能会遗漏掉某些包含的设计模式实例;而若v选取过小则可能会出现误判的情况. 根据经验，这里取v = 0.9.

这里继续以装饰模式和子系统s为例来说明基于相似度矩阵的设计模式识别. 易见MSimilarity

s，p          的第1列第2行元素的值大于等于匹配临界值v = 0.9，则说明该子系统包含装饰模式实例.

在c1对应的列中，数值最大的元素对应C1行，则说明子系统中的类C1关联装饰模式的角色类c2. 类似地，可以得到子系统中的类C4、C5、C7分别关联装饰模式的角色类c2、c3、c4. 在图3中，灰色填充的类关联装饰模式的角色.

4   实验及结果分析

目前本文方法的支撑工具EasyDetector 1.0已经实现. 该工具采用MFC开发，输入UML类图模型，输出识别结果. 为说明本文方法的有效性，使用文献[26]方法、文献[9]方法和本文方法对开源项目JHotDraw 5.2、JRefactory 2.6.24和JUnit 3.7进行了设计模式的识别.

表1～3和表4～6分别列出了文献[26]方法、文献[9]方法和本文方法的支撑工具对JHotDraw 5.2进行设计模式识别的识别准确率和CPU时间花费.

表1 ～ 表3中准确率的评估是基于以下术语进行的：

1）真阳性（TP，true positive）; 2）假阳性（FP，false positive）;3）假阴性（FN，false negative）;4）精确率（precision）;5）召回率（recall）.

以上术语的定义详见文献[1].

现有方法大多是将所考虑的若干个特征分别进行匹配，识别准确率和时间性能不高.

由表1、表2和表3可知，文献[26]方法和

文献[9]方法的JHotDraw 5.2平均精确率和召回率分别为68.9%/71.3%、74.9%/96.2%，JRefactory 2.6.24平均精确率和召回率分别为54.3%/76.0%、79.4%/88.1%，JUnit 3.7平均精确率和召回率分别为52.8%/81.9%、60.0%/100.0%. 而本文方法使用总特征矩阵进行匹配，使得平均精确率和召回率较之文献[26]方法和文献[9]方法更高，JHotDraw 5.2平均精确率和召回率达到83.1%97.9%，JRefactory 2.6.24达到85.0%/92.6%，JUnit 3.7达到75.8%/100.0%.

由表4、表5和表6可知，对于JHotDraw 5.2，文献[26]方法和文献[9]方法分别花费8 884ms和7 658 ms，而本文方法仅用5 953 ms;对于JRefactory 2.6.24，文献[26]方法和文献[9]方法分别花费35 534 ms和29 777 ms，而本文方法仅用24 407 ms;对于JUnit 3.7，文献[26]方法和文献[9]方法分别5 774 ms和4 799 ms，而本文方法仅用3 572 ms. 可以看出，计算总特征矩阵花费了额外的时间，使得本文方法的预处理阶段花费了更多时间. 然而通过计算总特征矩阵，本文只需要进行一次匹配，使得与文献[26]方法和文献[9]方法相比本文的设计模式识别阶段节省大量时间.

根据以上分析可知，本文方法可以对设计模式进行识别，且准确率和时间性能更高.

5   结   论

现有设计模式识别方法大多是将所考虑的若干个特征分别进行匹配，限制了其准确率和时间性能. 本文方法将所考虑的7个特征对应的矩阵组合成一个总特征矩阵，并使用总特征矩阵进行匹配，改善了识别准确率和时间性能.

目前该方法仍存在一些缺陷和不足.今后的主要工作如下：

1）目前所考虑的7个特征均是静态特征，后期将研究如何结合静态结构与设计模式的动态特征综合进行识别.

2）提出的方法目前仅考虑子系统包含待识别模式的一个实例的情况，多个实例的情况将在后续的研究中进行讨论.

3）本文目前的识别规则均是从设计模式的理论描述中获取的，后期将使用机器学习从实际软件系统中获取识别规则.

参考文献

[1]    RASOOL G，STREITFDERT D. A survey on design pattern recovery techniques [J]. International Journal of Computer Science Issues，2011，8（6）：251—260.

[2]    許涵斌，张学林，郑晓梅，等. 一种基于结构查询的UML设计模式识别方法[J]. 计算机科学，2014，41（11）：50—55.

XU H B，ZHANG X L，ZHENG X M，et al. UML design pattern recognition method based on structured query [J].Computer Science，2014，41（11）：50—55. （In Chinese）

[3]    YU D，ZHANG Y，CHEN Z. A comprehensive approach to the recovery of design pattern instances based on sub-patterns and method signatures [J]. Journal of Systems & Software，2015，103：1—16.

[4]    BERNARDI M L，LUCCA G A D. Model-driven detection of design patterns [C]// IEEE International Conference on Software Maintenance. Timisoara：IEEE Computer Society，2010：1—5.

[5]    BeRNARDI M L，CIMITILE M，LUCCA G A D. A model-driven graph-matching approach for design pattern detection [C]// Working Conference on Reverse Engineering. Beverly：IEEE，2013：172—181.

[6]    BERNARDI M L，CIMITILE M，LUCCA G D. Design pattern detection using a DSL‐driven graph matching approach [J]. Journal of Software Evolution & Process，2014，26（12）：1233—1266.

[7]    DONG J，SUN Y，ZHAO Y. Design pattern detection by template matching [C]// The 23rd Annual ACM Symposium on Applied Computing. Fortaleza：DBLP，2008：765—769.

[8]    DONG J，ZHAO Y，SUN Y. A matrix-based approach to recovering design patterns [J]. IEEE Transactions on Systems，Man，and Cybernetics - Part A：Systems and Humans，2009，39（6）：1271—1282.

[9]    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.

[10]  BLONDEL V D，GAJARDO A，HEYMANS M，et al. A measure of similarity between graph vertices：applications to synonym extraction and web searching [J]. SIAM Review，2004，46（4）：647—666.

[11]  COSTAGLIOLA G，LUCIA A D，DEUFEMIA V，et al. Design pattern recovery by visual language parsing [C]// European Conference on Software Maintenance and Reengineering. Manchester：IEEE，2005：102—111.

[12]  COSTAGLIOLA G，LUCIA A D，DEUFEMIA V，et al. Case studies of visual language based design patterns recovery[C]// European Conference on Software Maintenance & Reengineering. Los Alamitos：IEEE，2006：1—10.

[13]  LUCIA A D，DEUFEMIA V，GRAVINO C，et al. Behavioral pattern identification through visual language parsing and code instrumentation[C]// European Conference on Software Maintenance & Reengineering. Kaiserslautern：IEEE，2009：99—108.

[14]  LUCIA A D，DEUFEMIA V，GRAVINO C，et al. Design pattern recovery through visual language parsing and source code analysis [J]. Journal of Systems & Software，2009，82（7）：1177—1193.

[15]  BALANYI Z，FERENC R. Mining design patterns from C++ source code [C]// Proc International Conference on Software Maintenance. Amsterdam：IEEE，2003：305—314.

[16]  BERNARDI M L，CIMITILE M，RUVO G D，et al. Improving design patterns finder precision using a model checking approach [C]// The 27th International Conference on Advanced Information Systems Engineering. Stockholm：Springer-Verlag，2015：1—8.

[17]  BERNARDI M L，CIMITILE M，RUVO G D，et al. Integrating model driven and model checking to mine design patterns [M]. Berlin：Springer International Publishing，2015：1—8.

[18]  BERNARDI M L，CIMITILE M，RUVO G D，et al. Model checking to improve precision of design pattern instances identification in OO systems[C]// International Joint Conference on Software Technologies. Lisbon：IEEE，2016：53—63.

[19]  LUCIA A D，DEUFEMIA V，GRAVINO C，et al. Improving behavioral design pattern detection through model checking [C]// European Conference on Software Maintenance and Reengineering. Oldenburg：IEEE，2011：176—185.

[20] WENDEHALS L，ORSO A. Recognizing behavioral patterns at runtime using finite automata [C]// Proceedings of the 2006 International Workshop on Dynamic Analysis. Shanghai：ACM，2006：33—40.

[21]  ZHU H，BAYLEY I，SHAN L，et al. Tool support for design pattern recognition at model level [C]// The 33rd Annual IEEE International Computer Software and Applications Conference. Seatle：IEEE，2009：228—233.

[22]  BAYLEY I，ZHU H. Formalising design patterns in predicate logic [C]// IEEE International Conference on Software Engineering and Formal Methods. IEEE，2007：25—36.

[23]  BAYLEY I，ZHU H. Specifying behavioural features of design patterns in first order logic [C]// The 32nd Annual IEEE International Computer Software and Applications Conference. Turku：IEEE Computer Society，2008：203—210.

[24]  BAYLEY I，ZHU H . Formal specification of the variants and behavioural features of design patterns [J]. Journal of Systems & Software，2010，83（2）：209—221.

[25]  苗康，余嘯，赵吉，等. 基于关系演算的Java模式识别[J]. 计算机应用研究，2010，27（9）：3425—3430.

MIAO K ，YU X ，ZHAO J ，et al. Java design pattern recognition based on relational calculus [J]. Application Research of Computers，2010，27（9）：3425—3430. （In Chinese）

[26]  KIM H，BOLDYREFF C. A method to recover design patterns using software product metrics [C]// International Conference on Software Reuse：Advances in Software Reusability. Vienna：Springer-Verlag，2000：318—335.

[27]  HAYASHI S，KATADA J，SAKAMOTO R，et al. Design pattern detection by using meta patterns [J]. IEICE Transactions on Information & Systems，2008，E91-D （4）：933—944.

[28]  LUITEL G，STEPHAN M，INCLEZAN D. Model level design pattern instance detection using answer set programming [C]// International Workshop on Modeling in Software Engineering. Austin：ACM，2016：13—19.

[29]  SCANNIELLO G，GRAVINO C，RISI M，et al. Documenting design-pattern instances：a family of experiments on source-code comprehensibility [J].ACM Transactions on Software Engineering and Methodology，2015，24（3）：1—35.