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

近年来, 国内外的相关文献已经提出很多设计模式自动识别的方法, 例如, 许等^[2]从类的属性、类间关系和整个模型3个角度出发对设计模式进行识别；周等^[3]主要考虑从源代码中识别设计模式中的聚集关系；Pradhan等^[4]提出了一种基于图同构和归一化互相关的设计模式识别方法；Bernardi等^[5-7]使用图形匹配技术对设计模式进行识别.然而, 这些方法大多只考虑了设计模式的结构特征, 因此识别的准确率并不高, 尤其是对于结构特征不够明显或与其他模式具有相似结构的模式更是如此. Dong等^[8]考虑了8个设计模式的特征并将它们集成在一个特征矩阵中, 可以较为精确地实现设计模式识别.但该方法所考虑的8个特征仍然全部都是结构特征.

针对以上问题, 提出一种考虑多种特征因素的设计模式自动识别方法, 并实现了该方法的支撑工具.该方法基于相似度评分算法, 在设计模式自动识别过程中考虑了设计模式的3种因素：结构特征、命名特征和图形特征, 具有较高的识别准确率.对于结构特征不够明显或者与其他模式具有相似结构特征的设计模式, 效果尤其明显.

1 相似度评分算法

提出的设计模式自动识别方法基于相似度评分算法.下面对该算法进行简单介绍.

该算法由Blondel等^[9]提出, 用来计算两个矩阵的相似度.设A、B分别为有向图G_A和G_B的邻接矩阵, n_A和n_B分别为A和B的阶数, Z₀为一个n_B×n_A的矩阵, 其元素全为1.相似度矩阵S定义为一个n_B×n_A的矩阵, 其元素s_ij称为顶点j(在G_A中)和顶点i(在G_B中)之间的相似度得分, 表示这两个顶点的相似程度.

计算S的详细算法见文献[9].

2 系统和设计模式的形式化描述方法

要实现设计模式的自动识别, 首先要解决的问题是待考查系统和设计模式的形式化描述^[10].通过计算待考查系统和设计模式之间的相似度矩阵来实现设计模式的识别, 因此需要将系统和设计模式表示为矩阵形式.为提高识别的准确率, 考虑设计模式的3种特征因素：结构特征、命名特征和图形特征.下面给出结构特征矩阵、命名特征矩阵和图形特征矩阵的定义.

2.1 结构特征矩阵

结构特征矩阵共包含关联关系矩阵等4个矩阵.

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

$ \mathit{\boldsymbol{M}}_G^{{\rm{Ass}}} = \begin{array}{*{20}{c}} {}&{\begin{array}{*{20}{c}} {{c_1}}&{{c_2}}& \cdots &{{c_{\rm{j}}}}& \cdots &{{c_n}} \end{array}}\\ {\begin{array}{*{20}{c}} {{c_1}}\\ {{c_2}}\\ \vdots \\ {{c_i}}\\ \vdots \\ {{c_n}} \end{array}}&{\left[ {\begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{}\\ {}&{}&{}&{}&{}&{}\\ {}&{}&{}&{{r_{ij}}}&{}&{}\\ {}&{}&{}&{}&{}&{}\\ {}&{}&{}&{}&{}&{}\\ {}&{}&{}&{}&{}&{} \end{array}} \right]} \end{array} $

(1)

其中

$ {r_{ij}} = \left\{ \begin{array}{l} 1\;\;\;\;类\;{c_i}\;到\;{c_j}\;之间存在关联关系\\ 0\;\;\;\;类\;{c_i}\;和\;{c_j}\;之间不存在关联关系 \end{array} \right. $

类似地可以定义类图G的泛化关系矩阵M_G^Gen、依赖关系矩阵M_G^Dep和聚合关系矩阵M_G^Agg.

2.2 命名特征矩阵

为了增强模型的可读性和可维护性, 不同设计模式的UML表示具有不同的命名特征, 如表 1所示.

定义2  类图G的关于设计模式pattern的命名矩阵定义为

$ \mathit{\boldsymbol{M}}_{G,{\rm{pattern}}}^{{\rm{Name}}} = \begin{array}{*{20}{c}} {}&{\begin{array}{*{20}{c}} {{c_1}}&{{c_2}}& \cdots &{{c_{\rm{j}}}}& \cdots &{{c_n}} \end{array}}\\ {\begin{array}{*{20}{c}} {{c_1}}\\ {{c_2}}\\ \vdots \\ {{c_i}}\\ \vdots \\ {{c_n}} \end{array}}&{\left[ {\begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{}\\ {}&{}&{}&{}&{}&{}\\ {}&{}&{}&{{r_{ij}}}&{}&{}\\ {}&{}&{}&{}&{}&{}\\ {}&{}&{}&{}&{}&{}\\ {}&{}&{}&{}&{}&{} \end{array}} \right]} \end{array} $

(2)

其中

$ {r_{ij}} = \left\{ \begin{array}{l} 1\;\;\;\;i = j\;且类\;{c_i}\;包含模式\;{\rm{pattern}}\;命名特征字符串\\ 0\;\;\;\;其他 \end{array} \right. $

2.3 图形特征矩阵

另外, 不同设计模式的UML表示具有不同的图形特征.例如, 在观察者、抽象工厂、工厂方法、外观、享元、解释器、迭代器、中介者模式的UML表示中, 类的关系会形成一个环状.

定义3  类图G的图形特征矩阵定义为

$ \mathit{\boldsymbol{M}}_G^{{\rm{Graph}}} = \begin{array}{*{20}{c}} {}&{\begin{array}{*{20}{c}} {{c_1}}&{{c_2}}& \cdots &{{c_{\rm{j}}}}& \cdots &{{c_n}} \end{array}}\\ {\begin{array}{*{20}{c}} {{c_1}}\\ {{c_2}}\\ \vdots \\ {{c_i}}\\ \vdots \\ {{c_n}} \end{array}}&{\left[ {\begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{}\\ {}&{}&{}&{}&{}&{}\\ {}&{}&{}&{{r_{ij}}}&{}&{}\\ {}&{}&{}&{}&{}&{}\\ {}&{}&{}&{}&{}&{}\\ {}&{}&{}&{}&{}&{} \end{array}} \right]} \end{array} $

(3)

其中

$ {r_{ij}} = \left\{ \begin{array}{l} 1\;\;\;\;存在从类\;{c_i}\;到\;{c_j}\;的关联、泛化或依赖关系\\ 0\;\;\;\;类\;{c_i}\;和\;{c_j}\;之间不存在关系 \end{array} \right. $

3 设计模式的自动识别 3.1 基本流程

UML模型的矩阵描述包含了原模型的结构特征、命名特征和图形特征信息.在本文中, 将待考查系统划分为若干个子系统, 通过计算子系统的特征矩阵和设计模式特征矩阵之间的相似度矩阵来实现设计模式的识别.基于相似度评分的设计模式自动识别流程如图 1所示.

3.2 23种设计模式的形式化描述

根据上述流程可知, 需要提前获取23种设计模式的特征矩阵, 并存储起来.

装饰模式的UML类图描述如图 2所示.

记Component、ConcreteComponent、Decorator和ConcreteDecorator分别为c₁、c₂、c₃和c₄.根据结构特征矩阵的定义, 可得

$ \mathit{\boldsymbol{M}}_{{\rm{decorator}}}^{{\rm{Ass}}} = \begin{array}{*{20}{c}} {}&{\begin{array}{*{20}{c}} {{c_1}}&{{c_2}}&{{c_3}}&{{c_4}} \end{array}}\\ {\begin{array}{*{20}{c}} {{c_1}}\\ {{c_2}}\\ {{c_3}}\\ {{c_4}} \end{array}}&{\left[ {\begin{array}{*{20}{c}} 0&0&0&0\\ 0&0&0&0\\ 1&0&0&0\\ 0&0&0&0 \end{array}} \right]} \end{array} $

(4a)

$ \mathit{\boldsymbol{M}}_{{\rm{decorator}}}^{{\rm{Gen}}} = \begin{array}{*{20}{c}} {}&{\begin{array}{*{20}{c}} {{c_1}}&{{c_2}}&{{c_3}}&{{c_4}} \end{array}}\\ {\begin{array}{*{20}{c}} {{c_1}}\\ {{c_2}}\\ {{c_3}}\\ {{c_4}} \end{array}}&{\left[ {\begin{array}{*{20}{c}} 0&1&1&0\\ 0&0&0&0\\ 0&0&0&1\\ 0&0&0&0 \end{array}} \right]} \end{array} $

(4b)

$ \mathit{\boldsymbol{M}}_{{\rm{decorator}}}^{{\rm{Dep}}} = \mathit{\boldsymbol{M}}_{{\rm{decorator}}}^{{\rm{Agg}}} = {\bf{0}} $

(4c)

根据命名特征矩阵的定义, 可得

$ \mathit{\boldsymbol{M}}_{{\rm{decorator}},{\rm{decorator}}}^{{\rm{Name}}} = \begin{array}{*{20}{c}} {}&{\begin{array}{*{20}{c}} {{c_1}}&{{c_2}}&{{c_3}}&{{c_4}} \end{array}}\\ {\begin{array}{*{20}{c}} {{c_1}}\\ {{c_2}}\\ {{c_3}}\\ {{c_4}} \end{array}}&{\left[ {\begin{array}{*{20}{c}} 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{array}} \right]} \end{array} $

(5)

根据图形特征矩阵的定义, 可得

$ \mathit{\boldsymbol{M}}_{{\rm{decorator}}}^{{\rm{Graph}}} = \begin{array}{*{20}{c}} {}&{\begin{array}{*{20}{c}} {{c_1}}&{{c_2}}&{{c_3}}&{{c_4}} \end{array}}\\ {\begin{array}{*{20}{c}} {{c_1}}\\ {{c_2}}\\ {{c_3}}\\ {{c_4}} \end{array}}&{\left[ {\begin{array}{*{20}{c}} 0&1&1&0\\ 0&0&0&0\\ 1&0&0&1\\ 0&0&0&0 \end{array}} \right]} \end{array} $

(6)

类似地, 可以得到其他22种设计模式的特征矩阵.

3.3 子系统的划分

为提高识别的准确率, 提升算法执行的性能, 需要将待考查系统划分为若干子系统^[11].

根据待识别的设计模式所含继承层的个数, 划分子系统有以下两种方法：

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

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

3.4 子系统与设计模式相似度矩阵的计算

对于每种设计模式, 首先根据其所含继承层的个数, 将待考查系统划分为 $\frac{{m(m - 1)}}{2}$ 个子系统(m为系统中继承层的个数).然后依次计算各子系统的特征矩阵和设计模式特征矩阵之间的相似度矩阵.

计算某个子系统subSystem和某种设计模式pattern之间的相似度矩阵S_{subSystem, pattern}的算法如下(函数Similarity()对应第2节中的相似度评分算法)：

步骤1  计算subSystem和pattern之间的结构特征相似度矩阵

$ \begin{array}{*{20}{c}} {\mathit{\boldsymbol{S}}_{{\rm{subSystem,pattern}}}^{{\rm{Structure}}} = {\rm{Similarity}}\;\left( {\mathit{\boldsymbol{M}}_{{\rm{pattern}}}^{{\rm{Ass}}},\mathit{\boldsymbol{M}}_{{\rm{subSystem}}}^{{\rm{Ass}}}} \right) + }\\ {{\rm{Similarity}}\;\left( {\mathit{\boldsymbol{M}}_{{\rm{pattern}}}^{{\rm{Gen}}},\mathit{\boldsymbol{M}}_{{\rm{subSystem}}}^{{\rm{Gen}}}} \right) + }\\ {{\rm{Similarity}}\;\left( {\mathit{\boldsymbol{M}}_{{\rm{pattern}}}^{{\rm{Dep}}},\mathit{\boldsymbol{M}}_{{\rm{subSystem}}}^{{\rm{Dep}}}} \right) + }\\ {{\rm{Similarity}}\;\left( {\mathit{\boldsymbol{M}}_{{\rm{pattern}}}^{{\rm{Agg}}},\mathit{\boldsymbol{M}}_{{\rm{subSystem}}}^{{\rm{Agg}}}} \right)} \end{array} $

(7)

步骤2  计算subSystem和pattern之间的命名特征相似度矩阵

$ \mathit{\boldsymbol{S}}_{{\rm{subSystem,pattern}}}^{{\rm{Name}}} = {\rm{Similarity}}\;\left( {\mathit{\boldsymbol{M}}_{{\rm{pattern,pattern}}}^{{\rm{Name}}},\mathit{\boldsymbol{M}}_{{\rm{subSystem,pattern}}}^{{\rm{Name}}}} \right) $

(8)

步骤3  计算subSystem和pattern之间的图形特征相似度矩阵

$ \mathit{\boldsymbol{S}}_{{\rm{subSystem,pattern}}}^{{\rm{Graph}}} = {\rm{Similarity}}\;\left( {\mathit{\boldsymbol{M}}_{{\rm{pattern}}}^{{\rm{Graph}}},\mathit{\boldsymbol{M}}_{{\rm{subSystem}}}^{{\rm{Graph}}}} \right) $

(9)

步骤4  计算总相似度矩阵

$ \begin{array}{l} {\mathit{\boldsymbol{S}}_{{\rm{subSystem,pattern}}}} = \mathit{\boldsymbol{S}}_{{\rm{subSystem,pattern}}}^{{\rm{Strcture}}} + \mathit{\boldsymbol{S}}_{{\rm{subSystem,pattern}}}^{{\rm{Name}}} + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\mathit{\boldsymbol{S}}_{{\rm{subSystem,pattern}}}^{{\rm{Graph}}} \end{array} $

(10)

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

获取子系统和某种设计模式之间的相似度矩阵S_{subSystem, pattern}后, 就可以根据相似度矩阵找出系统中包含的该种设计模式的实例.

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

相似度矩阵S_{subSystem, pattern}的元素表示两个类之间的相似度得分.所以, 需要选择一个值, 当相似度得分大于该值时, 就认为这两个类匹配.将该值称为匹配临界值, 记为v.

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

步骤1  依次判断S_{subSystem, pattern}的每列, 若所有的列均有至少一个元素的值大于等于匹配临界值v, 则说明该子系统包含模式pattern；否则不包含.

步骤2  若包含模式pattern, 则需要找到该模式的每个角色在子系统subSystem中关联的类.依次考查S_{subSystem, pattern}的每列, 从中找出值最大的元素, 则该列对应的设计模式角色关联该元素所在行对应的子系统类.

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

4 实验及结果分析

目前提出方法的支撑工具已经实现.该工具采用MFC开发, 输入UML类图模型, 输出识别结果.为说明该工具的有效性, 对开源项目C++图像处理库ImageProcessor进行了设计模式识别.下面给出其中的一个识别实例, 然后对该项目的识别结果进行分析和对比.

4.1 识别实例

在对该项目进行设计模式识别之前, 使用Microsoft Visio逆向工程将源码转化为UML类图模型^[12].这里以装饰模式的识别为例, 首先将待考查系统划分为m个子系统(m为系统中继承层的个数). 图 3为其中的一个子系统, 记为subsystem.

记Component、View、Director、TextView、Decorator、ImageBuilder、BorderDecorator和ImageProduct分别为C₁、C₂、C₃、C₄、C₅、C₆、C₇和C₈.经计算可得子系统subsystem和装饰模式之间的相似度矩阵为

$ \begin{array}{*{20}{c}} {{\mathit{\boldsymbol{S}}_{{\rm{subSystem,decorator}}}} = }\\ \begin{array}{l} \;\;\;\;\;\;\;\;\;\;{c_1}\;\;\;\;\;\;\;\;\;\;{c_2}\;\;\;\;\;\;\;\;\;\;\;{c_3}\;\;\;\;\;\;\;\;\;\;{c_4}\\ \begin{array}{*{20}{c}} {{C_1}}\\ {{C_2}}\\ {{C_3}}\\ {{C_4}}\\ {{C_5}}\\ {{C_6}}\\ {{C_7}}\\ {{C_8}} \end{array}\left[ {\begin{array}{*{20}{c}} {1.0016}&{0.4026}&{0.5016}&{0.4026}\\ {0.8481}&{0.0565}&{0.2385}&{0.0565}\\ {0.0858}&0&{0.5858}&0\\ {0.6468}&{0.8038}&{0.6468}&{0.1089}\\ {0.5396}&{0.4993}&{1.5396}&{0.4134}\\ {0.0636}&{0.0493}&{0.0636}&{0.2205}\\ {0.0426}&{0.4026}&{0.4026}&{0.6738}\\ {0.0214}&{0.0214}&{0.0214}&{0.0214} \end{array}} \right] \end{array} \end{array} $

(11)

易见S_{subSystem, decorator}的每列均有至少一个元素的值大于等于匹配临界值v=0.6, 则说明该子系统包含装饰模式实例.

在c₁对应的列中, 值最大的元素对应C₁行, 则说明子系统中的类C₁关联装饰模式的角色类c₁.类似地, 可得类C₄、C₅、C₇分别关联装饰模式的角色类c₂、c₃、c₄.同理可得该子系统中包含生成器模式实例.在图 4中, 加粗的类关联装饰模式的角色, 虚线的类关联生成器模式的角色, 灰色填充的类为两个设计模式实例共用的类.

需要注意的是, 该子系统包含的装饰模式实例是一个变形的装饰模式(装饰模式角色所关联的类component和decorator中间增加了一个类view), 如果只考虑结构特征, 可能会错误地得到子系统中的类View关联装饰模式的角色Component的结论.但是通过综合考虑结构特征、命名特征和图形特征3种因素, 避免了这种情况的出现.

4.2 结果分析

为将该方法与其他方法进行定量对比, 给出成功识别个数、错误识别个数、遗漏识别个数和识别准确率的一种严格定义.

成功识别个数是指系统中确实包含的并且被正确识别出的设计模式实例个数, 记为N_S；错误识别个数是指系统中不包含, 却被误判为包含的设计模式实例个数, 记为N_W；遗漏识别个数是指系统中包含, 却未正确识别出的设计模式实例个数, 记为N_O.显然, 系统中实际包含的设计模式实例总数为N_S+N_O.

定义4  识别准确率定义为

$ {R_{\rm{A}}} = \frac{{{N_{\rm{S}}} - {N_{\rm{W}}}}}{{{N_{\rm{S}}} + {N_{\rm{O}}}}} \times 100\% $

(12)

笔者进一步完善了文献[4-6]方法的支撑工具. 表 2列出了采用这些工具和提出方法的支撑工具对开源项目C++图像处理库ImageProcessor进行设计模式识别的结果.

由表 1可知, 文献[4-6]的方法的平均识别准确率分别为15.27%、11.67%和21.44%.而提出方法的平均准确率达到了49.48%.模板方法模式的结构特征不够明显, 仅包含一个继承关系.对于模板方法模式, 文献[4]方法和文献[5]方法的准确率为0, 文献[6]方法的准确率也仅为33.33%, 而提出的方法通过模板方法模式的命名特征使得识别的准确率达到了100%.状态模式和策略模式具有相似的结构特征, 仅依靠结构特征来区分这两种模式非常困难.对于状态模式与策略模式, 文献[4-6]提出的方法均无法准确地区分这两种设计模式, 使得识别准确率很低, 而提出的方法这两种模式的准确率分别达到60.00%和57.14%.

根据以上分析可知, 该方法可以实现设计模式的自动识别, 且准确率较高.尤其是当设计模式的结构特征不够明显或者与其他模式具有相似的结构特征时, 识别准确率明显提升.

5 结束语

现有的设计模式自动识别方法大多只考虑设计模式的结构特征, 因此识别的准确率并不高.提出的方法在对设计模式进行自动识别的过程中借助了相似度评分算法, 考虑了设计模式的结构特征、命名特征和图形特征3个因素, 增大了识别的准确率.该方法尤其适用于结构特征不够明显或者与其他模式具有相似结构特征的设计模式.

目前该方法在设计模式的识别中考虑了其结构特征、命名特征和图形特征.今后的主要工作如下：

1) 目前所考虑的3个特征因素均是静态特征, 后期将研究如何结合静态结构与设计模式的动态特征综合进行识别；

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

3) 如何对子系统的划分和相似度矩阵的计算算法进行优化以提高算法的时间性能也是下一步研究的重点.