注入间接线索的设计模式变体分类检测

肖卓宇，何 锫，李 港，杨道武，彭逸凡，董泽民

1(中南林业科技大学 涉外学院，长沙 410200)

2(广州大学 计算机科学与教育软件学院，广州 510006)

3(北京大学 高可信软件技术教育部重点实验室，北京 100871)

1 引 言

设计模式提供有效对象间关系的作用来实现某种设计意图，并有助于程序的理解与复用[1].设计模式恢复与软件系统的逆向工程与再工程联系紧密，有利于遗产系统的维护与重构[2，3].为此，众多学者围绕设计模式检测开展了大量的工作[4-7].

Fontana提出使用Design Pattern Clues、Micro Pattern、EDPS等微结构特征挖掘设计模式，从而实现对设计模式实例的识别[8，9].文献[10]通过定义23种设计模式的子图结构特征模型来实现对设计模式的挖掘.Rasool定义了47类特征信息，通过匹配特征信息来实现设计模式的恢复[11].文献[12,13]构建了设计模式实例规则库，并规范了模式库与用例之间的映射关系.文献[14]通过机器学习提升设计模式检测的精确率.许涵斌等[15]提出通过查询与匹配UML模型中的特征信息来恢复设计模式.Petterson提出影响设计模式恢复精度的几种主要因素，而变体是因素之一[16].文献[17] 提出一种形式化上下无关文法关系驱动的设计模式检测方法，该方法能够一定程度上减少设计模式参与者角色间附加关系导致的假阴性问题，并能较好的解决结构型模式的重叠问题.综上所述，传统的设计模式恢复方法存在5点问题：1) 较少考虑设计模式变体的影响，从而导致不精确的结果产生；2)对模式变体的挖掘没有从创建型、行为型、结构型三个方面分类进行深入研究，缺乏针对性；3)传统工作针对设计模式变体的理解侧重于抽象概念，较少涉及具体的实现；4)对于模式变体的识别较少有检测工具进行支撑；5)缺乏完整的设计模式变体知识库.

为此，本研究引入了Petterson[16]提出的设计模式变体概念，并在Scanniello[1]提出设计模式变体影响程序理解的思想基础上，提出一种注入间接线索的设计模式变体自动检测方法.依据GOF(Gang of four，GOF)[2]的设计模式分类原则，从创建型、行为型、结构型模式三种分类着手，以Proxy、Command及Factory Method模式为例，在不改变设计意图的前提下，分别给出了三者的模式变体实现，最后通过主流设计模式检测工具进行了变体检测实验.本文主要贡献为：1) 引入了设计模式变体的思想，提出一种可注入间接线索的设计模式变体自动识别方法.2) 从创建型、行为型、结构型模式三个角度出发对设计模式变体进行了研究与分析.3) 通过6种主流设计模式恢复工具与4种开源系统对设计模式变体的恢复结果进行了分析比较.

2 设计模式变体概念

GOF[2]依据不同的设计意图提出了23种经典的设计模式，而随着设计模式思想与技术的成熟化与规模化，23种设计模式已不能完全满足软件设计的需要.事实上，为解决大中型软件系统精准设计的需求，目前众多研发人员在不改变设计意图的前提下对23种经典设计模式进行了扩展，即设计模式变体[16].设计模式变体有利于软件研发效率的提升，并降低成本，另一方面，从逆向工程与再工程的角度研究发现设计模式变体同时也会使得生成可复用解决方案变得困难，因为现有的工具与方法较难检测出23种设计模式的变体.

3 自动注入线索的变体检测方法

本研究先前工作提出一种多阶段交互式线索驱动的设计模式检测方法，该方法取得较好的识别效果，但缺点在于人工干预太多，成本过高，并且对当前设计模式检测领域的一个难点，即设计模式变体的检测缺乏关注[13].本文先前工作对图1中的标准Proxy模式的检测效果较好，但对于Proxy模式变体的检测效果不理想.

为此，本研究在先前工作[3]基础上提出一种可注入间接线索的设计模式变体检测方法，旨在不改变设计模式变体的设计意图前提下，通过在标准设计模式中注入易被传统设计模式检测方法忽略的有价值间接关系来自动检测设计模式变体，从而提高检测结果的精确率.

3.1 注入间接线索的相关定义

定义1. 参与者角色及关系定义：

Rel：R×R，R∈{Interface，Class}.

Rel(R：R)={Ass，Dep，Agg，Inh...}.

R为模式实例参与者，可为接口Interface或类Class，Rel(R：R)表示设计模式参与者之间的联系，可为关联、依赖、继承、聚合等.

定义2. 存在多层继承的设计模式参与者角色关系定义：

∃Inh(RA：RB)∧∃Inh(RB：RC)→∃Inh(RA：RC).

设计模式参与角色RA如与RB存在继承关系，同时设计模式参与角色RB与RC也存在继承关系，则设计模式参与角色RA与RC之间存在可传递的继承关系.

定义3. 基于设计模式角色子继承的关联关系定义：

∃Dep=(RA：RB)∧∃Inh(RB：RC)→∃Dep(RA：RC).

设计模式参与角色RA如与RB存在依赖关系，同时设计模式参与角色RB与RC也存在继承关系，则设计模式参与角色RA与RC之间存在可传递的依赖关系.

3.2 注入间接线索的实例描述

先前工作[3]能检测到图1左侧的标准Proxy模式，但如果将该标准设计模式演化为图1右侧的Proxy模式变体，本研究先前工作及传统方法都难以检测实现.与标准Proxy模式相比图1右侧的Proxy模式变体层次更多，关系也更加复杂，如RealSuject类参与者并没有起到实质性作用，具体实现主要通过其子类RealSuject1与RealSuject2进行，而子类Re-alSuject1与RealSuject2虽未直接与Proxy类取得联系，但由于类RealSubject1、RealSubject2与RealSubject存在继承关系，依据3.1节定义3，故实质上RealSubject1可以通过图1中关系1与Proxy类建立依赖联系，并最终形成图2中Proxy变体1；同理RealSubject2可以通过图1中关系2与Proxy类建立依赖联系，最终形成图2中Proxy变体2.

图2 Proxy模式变体子图Fig.2 Subgraph variants of Proxy pattern

4 间接线索的CSP表示

Guéhéneuc将设计模式表示为CSP[5]形式的约束集特征值，笔者先前工作[3]对其进行了初步标准设计模式检测.表1描述了标准Proxy模式的CSP[5]表示形式，其中02行表示存在一个名为subject的超类，03行表示subject存在一个抽象方法，而04与05行表示Proxy类与Realsubject类都存在非抽象方法request，06行表示Proxy与subject类存在继承关系，07表示Realsubject与subject类存在继承关系，08行表示Proxy与Realsubject存在依赖关系.

表1 标准Proxy模式约束集Table 1 Constraints representation of standard Proxy pattern

表2 Proxy模式变体约束集Table 2 Constraints representation of variant Proxy pattern

图2中Proxy变体1的CSP[5]表示见表2.与表1标准设计模式相比，注入间接线索后，Proxy变体1增加了新的特征信息.第06行表示类Realsubject1类也存在request方法，第09行表示Realsubject1与Realsubject之间也存在继承关系，第11行表示Realsubject1子类与Proxy之间通过继承传递也存在依赖关系，第12行表示参与者角色扮演的一致性检验结果.

5 检测步骤

步骤1. 通过工具DEMIMA[4]对目标源码进行抽取.

步骤2. 遍历步骤1抽取的参与者集，发现间接线索.

步骤3. 以CSP[5]的形式特征形式表示步骤2的间接线索.

步骤4. 通过特征匹配取得模式检测结果.

6 基于GOF设计模式变体的分类

GOF[2]将23种经典的设计模式分为结构型、行为型、创建型三类，事实上，在软件设计过程中这三类设计模式将产生大量的变体.为此，在此分类基础上，以Proxy模式、Command模式及Factory Method模式为例对三类变体依次进行详细的研究与分析.

6.1 结构型-Proxy模式变体

Proxy模式需要避免使用某些重量级的设计模式对象，而轻量级对象实质是原对象的副本，二者共享同一个接口，其具体实现仅通过最低功能配置生成.此外，Proxy模式与Decorator模式结构上相近，但二者意图完全不同，故Proxy模式容易产生变体.图3描述了4种Proxy模式变体.

图3 四种Proxy模式变体Fig.3 Four variants of Proxy pattern

1)Proxy类与Subject类存在关联关系的变体.Proxy类变体(1)结构与Decorator模式非常相似，区别在于Decorator模式的角色是抽象的，而Proxy模式变体(1)的角色是具体的.Proxy模式初始化了Subject与RealSubject类间的关联关系，并实例化了Proxy类的构造函数.

2)Proxy类与RealSubject类间存在聚合关系的变体.该变体中Proxy类与RealSubject类之间存在聚合关系，这样的处理方式有利于RealSubject类的参数实例化.该过程可能出现使用某种特定远程对象类型的情况，而RealSubject类也将在构造函数级或方法级的层次上被初始化.

3)异构环境中的代理变体.这种变体中出现的Proxy类将方法调用委托给具体类，该过程引入代理线程，并可验证.

4)反向代理变体.一个被Proxy类代理的客户对象作为占位符进行反向的代理服务，该变体重定向了一个请求，并转发请求，此外，一些可复用的服务可作为监听器以确保需求透明.反向代理变体具备查询有价值请求的功能.

上述4种形式未改变Proxy模式的意图，可理解为典型的Proxy模式变体.

6.2 行为型-Command模式变体

Command模式提供一种框架，该框架内数据的修改通过控制机制进行管理，Command模式用于对象间关系、职责的管理，适合于复杂场景，图4描述了4种Command模式变体.

1)命令组合变体.该变体可使用多种命令进行远程调用.

2)命令复用变体.这种变体集合了多种功能，此外，该变体对象中的参数可在不同的场景中复用.此变体的意图是为了解决独立执行、参数化及消除耦合等问题.

3)分布式命令模式变体.该变体引入相同命令自动调用的机制，提供一种从互联系统调用命令的执行方式.该变体无需发送自定义消息来获得服务器端数据，故在未通知命令执行的前提下，客户端无需解析与发送消息.这种变体依据消息来获取需要的数据与行为，每条命令都是序列化的发送给其它系统.

4) 装饰模式命令变体.Facade 模式作为该变体的一个类被实现，并可通过用例的应用来发现相应的远程方法，Command模式通过使用Facade 模式的用例或方法类来实现.

图4 四种Command模式变体Fig.4 Four variants of Command pattern

6.3 创建型-Factory Method模式变体

Factory Method模式采用虚拟方法实现设计目标，该模式通过重写子类来隐藏方法的实例逻辑，旨在通过工厂方法创建相似的对象.Factory Method模式有着广泛的应用，如微软的MFC，COM等.为此，创建型模式以Factory Method模式为例研究其7种典型变体.图5描述了这7种Command模式变体.

1)参数工厂方法变体.这种变体侧重Factory Method模式接口的参数化，提供了用于返回多个类型产品的单一工厂方法，故多个该变体可使用单一的方法，单一的抽象Product实例由每一个具体产品来创建.

2)从工厂方法中委派产品构建的变体.该变体使用语言特征机制在运行时动态的创建不同类型实例，旨在通过对工厂类的方法进行重写来实现，并返回要创建的产品类型.如图3中变体2)的ClientConfigurator类用来在一个特定时间选择一个已注册的具体类型.

3)无具体工厂类的变体.该变体通过消除子类具体的创建功能来实设计目标，Factory Method模式实例的创建由product类生成，product仅在创建类时被加载，Factory Method模式用于返回选定的product类.

4)从存储库类型中使用委托机制创建产品的变体.这种变体中product类由具体的创建者类库生成，此外，需消除重写的工厂方法，该变体主要在具体类构造时发生.

5)一个具体的创造者变体.该变体是参数工厂方法Factory Method模式变体1)的扩展，区别在于减少单一创建者的数量.

6)工厂内部不同产品类型变体.这种变体旨在提供Factory Method模式的基本实现，其中一个单一的工厂方法用来创建同类Product.该方法实现了多种Product类使用不同的工厂方法创建或访问特定对象的功能，即模式的结构是相同的，但修改后的实现支持多个类型的Product.

7)默认产品实现变体.该变体扩展了Factory Method模式变体1)的不同产品类型，讨论了默认模式执行所提供的Product类型，这种变体中Factory类与默认的Product类间存在直接的关联关系.

7 设计模式变体评估实验

设计模式的变体虽能更具针对性的解决某些特定问题，但同时也会影响设计模式检测工具的精确性.为此，本实验为检测图3、 图4、 图5中的设计模式变体，选择主流设计模式恢复工具DeMIMA (Guéhéneuc，2008)[4]、PINOT(Shi and Olsson，2006)[19]、F.T.(Rasool，2011)[11]、DPRE(De Lucia et al.，2010)[20]、DPJF(Binun and Kniesel，2012)[18]进行了实验.

表3 设计模式检测工具参数表Table 3 Parameter table of design pattern detection tool

表3给出了设计模式检测工具的部分重要参数，其中T列表示technique，涉及静态分析(Static，S)与动态分析(Dynamic，D)，R列表示识别方式Recognition，包括近似识别A(Approx，A)与完整识别E(Exact，E).实验环境使用机操作系统为Windows 7，CPU为 Intel酷睿i5，主频3.2 GHz，内存8G.

7.1 三类模式变体检测实验

表4给出了图3至图5中4种结构性模式Proxy变体、4种行为型模式Comand变体、7种Factory Method模式变体通过表1描述的经典的设计模式检测工具依次检测后的结果.“√”表示检测到了模式变体，“×”表示未检测到的模式变体.分析表4后发现如下几个主要问题：

图5 7种Factory method模式变体Fig.5 Seven variants of factory method pattern

1)PINOT[19]及DeMIMA[4]工具不能识别任何一种行为型与创建型模式变体，深入研究后发现，这2种工具仅采用静态分析机制，缺乏对检测系统的动态分析.此外，由于PINOT工具对变体特征信息缺乏关注，从而导致任意的结构型Proxy模式变体都无法识别，而DeMIMA[4]工具虽然一定程度上关注了变体特征信息，但其关注范围存在局限性，也导致结构型Proxy模式变体1)与3)不能被检测到.

表4 设计模式变体实验识别结果Table 4 Result on variants of design pattern

2)DPJF[18]工具由于同时兼顾了静态分析与动态分析机制，一定程度上对结构性模式Proxy变体的检测效果较PINOT[19]与DeMIMA[4]工具有所改进，甚至能够识别部分行为型变体，如Command模式变体2)与4)，但对创建型模式Factory Method变体的识别效果不理想.深入研究后发现创建型模式存在委托等难以复制的机制，对于对象执行的及时性与处理优先级等都有较高的要求，故识别的难度较高.

3)F.T[11]与DPRE[20]工具采用静态与动态分析机制，并同时关注到了设计模式角色的附加关系[21]特征信息，故对于DPJF工具不能检测到的创建型模式Factory Method变体的识别效果有所改进，如F.T[11]工具能够识别Factory Method模式变体1)，而DPRE工具能够识别Factory Method模式变体2)与5).

4)本文工作兼顾了静态分析与动态分析机制，并考虑到了设计模式角色间附加关系[21]与间接线索联系的影响，故在设计模式变体检测，尤其是创建型Factory Method模式变体的识别上取得了较好的效果.由表2可知，本文工作检测出4种结构型Proxy变体、4种行为型Command模式变体及7种创建型Factory Method模式变体的精确率依次为100%、75%、57%，平均识别成功率达到73.3%，明显高于F.T[11]等5种检测工具的平均识别成功率26.67%.

5)由于GOF设计模式分类的意图不一，故三类模式变体检测成功的难易程度也不同，由表2结果可知创建型模式较难，行为型模式次之，结构型模式相对较易，三者平均识别率为16.67%、41.65%、58.33%.

7.2 开源系统变体检测实验

该实验中检测工具选用表3中识别设计模式变体效果相对较好的F.T[11]与DPRE[20]工具，考虑到同行学者多以表5中开源系统进行检测试验，为了方便检测结果交叉比较，故选择表5中四种开源系统进行进一步的设计模式变体检测实验.表5描述了四种开源系统的网址、大小、LOC等主要参数.

表5 开源系统参数Table 5 Open source systems parameters

表6描述了开源系统中的变体检测结果，实验除分类识别标准的GOF设计模式之外，还对三类模式的变体进行检测，如在QuickUML2001系统中，本文工作检测到3个标准的Proxy模式及1个Proxy模式变体.工具F.T[11]仅检测到3个标准的Proxy模式，但不能识别Proxy模式变体.DPRE[20]工具能正确识别出Proxy模式变体，但只能识别2个标准的Proxy模式.为此，笔者以人工形式查找发现DPRE[20]工具未能识别的标准Proxy模式实例存在实例共享的问题，即Proxy模式中的参与者同时扮演多个设计模式中的角色，由于DPRE[20]工具缺乏这类约束机制，以至于识别结果不精确，而本文工作兼顾了静态与动态分析，关注到了设计模式角色间的附加关系[21]与间接线索联系的影响，故在该实验中取得了较好的效果.

1www.sourceforge. net/projects/quj/

2www.jrefactory.sourceforge.net

3www.antapache.org

4www.jhotdraw.org

8 有效性威胁

依据GOF[2]的设计模式分类原则，第6节中将设计模式变体分为结构型、行为型、创建型三类.所有三类模式变体的意图需与基于GOF的标准设计模式意图一致.而实际应用中结构型与行为型变体应用相对较多，因为结构型与行为型变体能够通过细微的修改来实现针对性的目标，且不改变标准GOF模式的意图，故较容易形成成熟的解决方案.

从一个逆向的角度来看，设计模式检测工具也应敏锐的意识到这些变体，因为软件系统中可能广泛存在这样的变体，而开发人员也倾向于复用这样的变体以提高软件研发的效率.这是一种机遇，也是一种挑战，为此，总结了将设计模式变体转换为可复用解决方案应注意的8项事项.

1)因为模式变体的不同实现，使得目前缺乏一种变体识别标准.

2)当前一些研究人员对设计模式检测的用例基准进行了分析与评估，但对模式变体的定义与识别基准缺乏关注.

3)一些变体仅根据作者突然的灵感或随机场景偶然的应用产生，故缺乏归纳.

4)新的变体需要在已有的模式定义中通过增加特征实现，而这些特征的获取方式仍无基准.

5)即便当前主流的工具也不能检测所有的模式变体.

6)大多数检测工具仅限于特定的设计模式，或某种特定的编程语言.

7)参与者共享设计模式角色也是变体产生的一个主要因素.

8)设计模式变体的假阳性及假阴性结果影响解决方案复用的效率.

9 结束语

本研究引入Petterson[16]提出的设计模式变体思想，并结合Scanniello[1]提出设计模式变体影响程序理解的观点，提出一种注入间接线索的设计模式变体检测方法.依据设计模式变体与标准模式意图的一致性原则，对设计模式变体进行了分类研究与识别.

1)与传统设计模式变体侧重理论相比，本研究给出了具体的设计模式变体检测实践.

2)分类描述了创建型、行为型及结构型模式变体的多种实现，并依次分类归纳了多种经典的Proxy模式、Command模式及Factory Method模式变体.

3)通过多种经典检测工具对三类模式变体进行了检测比较，并分类归纳总结了影响三类设计模式变体检测结果精确率的原因.研究工作取得了一定的成效，具备较好的应用前景，基本达到了预期目标.但也要意识到设计模式变体研究是一项长期的过程，并值得进一步深入研究，未来工作将致力于设计模式变体的归纳、定义、恢复及模式变体库的完善.

：

[1] 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-41.

[2] Zhang C，Budgen D.What do we know about the effectiveness of software design patterns[J].IEEE Transactions on Software Engineering，2012，38(5)：1213-1231.

[3] Xiao Zhuo-yu，He Pei，Yu Bo.A multi-stage approach based on interactive clues for design pattern detection[J].Journal of Beijing University of Aeronautics and Astronautics，2017，43(9)：1746-1756.

[4] Gueheneuc Y G，Antoniol G.DeMIMA：a multilayered approach for design pattern identification[J].IEEE Transactions on Software Engineering，2008，34(5)：667-684.

[5] Gueheneuc Y G，Guyomarch J Y，Sahraoui H.Improving design-pattern identification：a new approach and an exploratory study[J].Software Quality Journal，2010，18(1)：145-174.

[6] Xiao Zhuo-yu，Li Yan，He Pei，et al.Research on matrix grade evaluation based on design pattern detection[J].Journal of Chinese Computer Systems，2016，37(7)：1428-1433.

[7] Xiao Zhuo-yu，He Pei，Yang Xin-wei，et al.An optimization method for design pattern identification based on the grammar production[J].Journal of University of Electronic Science and Technology of China，2017，46(3)：569-576.

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

[9] Fontana F A，Maggioni S，Raibulet C.Understanding the relevance of micro-structures for design patterns detection[J].Journal of Systems and Software，2011，84(12)：2334-2347.

[10] 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 and Software，2015，88(5)：1-16.

[11] Rasool G，Mader P.A customizable approach to design patterns recognition based on feature types[J].Arabian Journal for Science and Engineering，2014，39(12)：8851-8873.

[12] Ampatzoglou A，Charalampidou S，Stamelos I.Research state of the art on GoF design patterns：a mapping study[J].Journal of Systems and Software，2013，86(7)：1945-1964.

[13] Ampatzoglou A，Michou O，Stamelos I.Building and mining a repository of design pattern instances：practical and research benefits[J].Entertainment Computing，2013，4(2)：131-142.

[14] Zanoni M，Fontana F A，Stella F.On applying machine learning techniques for design pattern detection[J].Journal of Systems and Software，2015，88(5)：102-117.

[15] Xu Han-bin，Zhang Xue-lin，Zhen Xiao-mei，et al.Method of software design patterns identification based on correlation and feature constraints[J].Computer Science，2014，41(11)：50-55.

[16] Petterson N，Lowe W，Nivre J.Evaluation of accuracy in design pattern occurrence detection[J].IEEE Transactions on Software Engineering，2010，36(4)：575-590.

[17] Xiao Zhuo-yu，He Pei，Yu Bo，et al.An approach for design pattern detection based on the formal context-free grammar relation driver[J].Chinese Journal of Engineering，2016，38(10)：1499-1508.

[18] Binun A，Kniesel G.DPJF-design pattern detection with high accuracy[C].Software Maintenance and Reengineering (CSMR)，2012 16th European Conference on.Szeged：IEEE，2012：245-254.

[19] Shi N，Olsson R A.Reverse engineering of design patterns from java source code[C].Automated Software Engineering，ASE′06，21st IEEE/ACM International Conference on Automated Software Engineering (ASE′06)，Tokyo：IEEE，2006：123-134.

[20] De lucia A，Deufemia V，Gravino C，et al.An eclipse plug-in for the detection of design pattern instances through static and dynamic analysis[C].Software Maintenance (ICSM)，2010 IEEE International Conference on,Timisoara：IEEE，2010：1-6.

[21] Xiao Zhuo-yu，He Pei，Li Yan.Study on the additional relationships based on design pattens′s roles[J].Application Research of Computers，2015，32(7)：2042-2045.

附中文参考文献：

[3] 肖卓宇，何 锫，余 波.一种多阶段交互式线索驱动的设计模式识别方法[J].北京航空航天大学学报,2017，43(9)：1746-1756.

[6] 肖卓宇，黎 妍，何 锫，等.基于矩阵积分评估的设计模式检测研究[J].小型微型计算机系统，2016，37(7)：1428-1433.

[7] 肖卓宇，何 锫，杨鑫维，等.基于文法产生式优化的设计模式识别方法[J].电子科技大学学报，2017，46(3)：569-576.

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

[17] 肖卓宇，何 锫，余 波，等.一种形式化上下无关文法关系驱动的设计模式检测方法[J].工程科学学报，2016，38(10)：1499-1508.

[21] 肖卓宇，何 锫，黎 妍.基于设计模式角色的附加关系检测研究[J].计算机应用研究，2015，32(7)：2042-2045.