文章快速检索  
  高级检索
一种多阶段交互式线索驱动的设计模式识别方法
肖卓宇1, 何锫2,3,4, 余波1     
1. 中南林业科技大学 涉外学院, 长沙 410200;
2. 广州大学 计算机科学与教育软件学院, 广州 510006;
3. 北京大学 高可信软件技术教育部重点实验室, 北京 100871;
4. 长沙理工大学 计算机与通信工程学院, 长沙 410114
摘要: 针对传统设计模式自动检测不够精确及不易于扩展的问题,为提高设计模式实例恢复的精确性,提出一种多阶段交互式线索驱动的设计模式识别方法。在传统基于约束满足问题(CSP)的设计模式检测思想基础上引入了线索的思想,旨在经过调研对专家经验知识进行反馈,并将筛选后有价值的线索表示为CSP形式的信息,进而依据信息特征将线索分类,通过在设计模式检测过程中逐步增加线索,直至设计模式实例候选参与者集产生。实验结果表明,本文方法不仅分阶段筛选了设计模式检测实例的假阴性与假阳性结果,还解决了设计模式识别的重叠问题,通过与其他主流检测方法的F-score指标值对比,取得了较好的检测效果。
关键词: 设计模式     设计模式识别     线索驱动     知识反馈     模式实例重叠    
A multi-stage approach based on interactive clues driven for design pattern identification
XIAO Zhuoyu1, HE Pei2,3,4, YU Bo1     
1. Swan College, Central South University of Forestry and Technology, Changsha 410200, China;
2. School of Computer Science & Education Software, Guangzhou University, Guangzhou 510006, China;
3. Key Laboratory of High Confidence Software Technologies of Ministry of Education, Peking University, Beijing 100871, China;
4. School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410114, China
Received: 2016-09-20; Accepted: 2016-12-09; Published online: 2016-12-26 17:07
Foundation item: National Natural Science Foundation of China (61170199); Project Number 1068 Supported by Circular of Hunan Provincial Education Department in 2016 No.400; Natural Science Foundation of Guangdong Province (2015A030313501); Construction Project of Innovation Team in Universities in Guangdong Province (2015KCXTD014)
Corresponding author. XIAO Zhuoyu, E-mail:xzyxzy0770@126.com
Abstract: Aimed at inaccuracy and difficulty to extend the traditional design pattern automatic detection method, and in order to improve the accuracy of the design pattern instance recovery, an interactive clue-driven approach for design pattern detection was presented. Concept of clue was introduced based on the constraint satisfaction problem (CSP) of traditional design pattern detection, and expert experience feedback mechanism was proposed by investigation. The significant clues were converted into the information based on CSP in the refining stage, the clues were classified by information characteristics, and the clues were added in design pattern detection process until the candidate sets of design pattern instance were produced. Experimental results show that the proposed method can gradually reduce the false negative results and the false positive results of design pattern detection instance, and further more, the novel method can solve design pattern overlap problem. Compared to the F-score index of other well-known algorithms, the proposed method shows better detection effect.
Key words: design pattern     design pattern identification     clue-driven     knowledge feedback     pattern instance overlap    

Gamma总结了经典的软件设计框架,归纳为结构型、创建型及行为型3类共23个设计模式,并被广大IT从业人员所推崇。而设计模式检测有利于软件的维护与再工程,是当前程序理解领域研究的热点[1]。当前,众多学者在设计模式恢复的技术、方法等方面做出了贡献[2-4]。Fontana等[5-6]将设计模式参与者信息表示为不同的Clues、EDP等微结构,进而匹配这些微结构来实现设计模式实例的识别。文献[7-9]通过机器学习对特征信息进行训练,并结合各种聚类与分类方法提升设计模式检测的精确率。Yu等[10-11]提出一种基于子模式及方法签名的设计模式实例恢复方法,思路是将设计模式中的特征信息表示为ICA、CI等15种子模式,并通过子模式的近似匹配来检测设计模式。文献[12-13]引入权值与子图同构的思想,以邻接矩阵的形式来表示参与者及其关系,进而识别设计模式实例。Sabo和Porubän[14]提出对设计模式中参与者的特征信息进行注释,以提高检测结果的精确率。Rasool等[15-16]归纳了47类设计模式参与者特征信息,支持多种程序语言的识别,并辅以注释,通过F.T工具对设计模式进行检测。Garlan等[17]使用抽象的形式化语言来表示设计模式,其文法描述和代码过于分离,以至于实例很难被自动识别。Guéhéneuc和Antoniol[18]采用多阶段策略恢复设计模式,旨在缩小搜索空间,并筛选候选参与者,进而减少设计模式检测的假阳性与假阴性结果。Petterson等[19]提出精确率、召回率及F-Score是影响设计模式检测精确性的重要指标。文献[20]对设计模式角色间存在的附加关系进行了分析,并制定了附加关系检测规则。

综上所述,传统设计模式实例恢复方法存在以下主要问题:① 没有采用交互式机制来获取更多有价值的专家反馈线索,从而导致大量假阳性与假阴性结果;② 采用全自动方法进行检测,制约条件过多,且不易于扩展;③ 大部分检测方法对结构型设计模式识别效果较好,而对行为型与创建型设计模式检测效果不够理想;④ 较难解决设计模式实例恢复的重叠问题。为此本文在Guéhéneuc等[21]提出基于约束满足问题(Constraint Satisfaction Problem, CSP)设计模式检测方法基础上提出一种基于多阶段交互式线索驱动的设计模式半自动检测方法,以调查表形式收集专家反馈知识,再将之按特征进行筛选与分类,形成3类不同的线索,而后通过在不同设计模式检测阶段增加线索来实现对检测结果的逐步求精,并通过4个开源项目对方法的识别效果进行了实验评估。

本文主要贡献为:① 提出一种多阶段可交互的设计模式半自动检测方法;② 依据专家知识的反馈,提出了线索概念;③ 按特征将线索分为静态线索、动态线索、专家经验线索3类,并将之转换为可执行的约束信息,有利于检测结果求精;④ 给出了方法的具体实现;⑤ 通过开源系统分阶段对检测结果进行了评估。

1 设计模式实例识别方法框架

图 1为设计模式实例识别流程。本文实现步骤分为线索表示及线索筛选2个主要阶段。其中,线索表示阶段依据Guéhéneuc等[21]提出CSP表示形式进行后续工作的开展,第2节中将对设计模式的CSP表示形式进行详细描述。线索筛选阶段主要对CSP描述的设计模式实例候选者分静态线索阶段、动态线索阶段及专家经验线索阶段依次进行筛选,直至最终的设计模式实例识别成功。

图 1 设计模式实例识别流程 Fig. 1 Design pattern instance identification flowchart
1.1 线索表示阶段

线索表示阶段又分为Guéhéneuc等[21]提出的传统CSP表示及本文方法获取的交互式线索驱动表示。

1) 传统方法CSP表示:① 通过工具DEMIMA[18]对目标源码进行抽取;② 将其结果通过工具Z3[22]转换为CSP的表示形式。

2) 基于交互式线索驱动方法表示:① 以调查表、问卷等形式获取有价值的线索;② 对反馈的线索进行筛选;③ 线索通过工具Z3[22]转换为CSP表示形式。

1.2 线索筛选阶段

将线索表示阶段获得的CSP形式,依据静态线索、动态线索、专家经验线索特点进行分类,并通过逐步增加这3类线索对设计模式检测结果进行筛选,直至取得最终的设计模式候选者集。

2 基于CSP的设计模式表示

Guéhéneuc等[21]提出基于CSP的设计模式检测方法,该方法以约束集形式表示设计模式实例的抽象模型,抽象模型可由类、方法、属性及其之间的关系元素构成。约束集解析器以源码分析的结果作为输入,通过处理后的输出结果与设计模式约束集进行匹配,从而得到设计模式实例的候选参与者。

从基于传统CSP表示的设计模式实例检测角度考虑,抽象模型集分为3类,依次为变量集(Variables)、约束集(Constraints)、域集(Domain)。

2.1 变量集

变量集包括不同设计模式中的类、接口等角色。

图 2(a)为一个标准的Abstract Factory模式,其变量集V可表示为式(1), 而图 2(b)为State模式,其变量集V可表示为式(2)。

图 2 Abstract Factory模式与State模式类图 Fig. 2 Class diagram of Abstract Factory pattern and State pattern
(1)
(2)
2.2 约束集

约束集C可以发现变量集V中不同角色间的关系,进而构成设计模式实例的抽象模型。本文以Guéhéneuc等[21]表 1中提出的约束集符号定义为基础,表 2描述了State模式的约束集。依据表 1的符号描述说明,表 2中02行表示存在一个超类扮演state角色,03行表示一个具体类与state类存在继承关系,04行~08行依次对约束集进行表示,详见注释,最终形成了标准的State模式约束集。

表 1 约束集符号类型[21] Table 1 Constraint set notation classes[21]
符号 描述
super-class() 表示超类
sub-class() 表示子类
has-method(c1, m2) 类c1中有方法m2
abst-class(c1) 类c1是一个抽象类
abst-method(m1) 方法m1是一个抽象的方法
Interface(c1) c1接口的方法都是抽象方法
protected-method(m2) 表示一个可保护的方法m2
final-method(m1) 方法m1是最终方法
par-Declared(c1, par1) 在c1类中申明数据类型par1
par-Parent(c2, par1) 数据类型par1的类型是c2
same-Signature(m1, m2) 方法m1与方法m2同名
dominate(m1, m2) 调用方法m2前须先调用m1
inh(c2, c1) 类c2 inherit类c1
aggre(c1, c2) 类c1与类c2存在聚合关系
invoke(m1, m2) 方法m1调用方法m2
asso(c1, c2) 类c1与类c2存在关联关系
override(c2, m1) 类c2的m1方法被重写

表 2 State模式约束集表示 Table 2 Constraint set representation of State pattern
01 State Design Pattern:
02 super-class(state-role)//存在超类
03 inh(concrete-class-role, state-role)//继承关系
04 aggre(context-class-role, state-role)//角色间聚合关系
05 has-method(state-role, abstr-method)//类中存在方法
06 abst-method(abstr-method)//类中存在抽象方法
07 override(concrete-class-role, abstr-method)//方法重写
08 Not(state-role==context-class-role)//角色是否一致比较

2.3 域集

域集D是源码元素及其关系的集合,可通过解析源码的抽取结果获得。图 3给出一个用例类图,通过约束解析器处理的结果见表 3

图 3 用例类图 Fig. 3 Example class diagram
表 3 基于CSP的实例域集表示 Table 3 Domain set representation of an example by CSP
01 has-method(Tool, method1)//Tool类中存在方法method1
02 has-method(Tool, method2)//Tool类中存在方法method2
03 abst-class(selectAbstractTool)//selectAbstractTool是抽象类
04 inh(Tool, createTool)//createTool与Tool类存在继承关系
05 inh(Tool, cancelTool)//cancelTool与Tool类存在继承关系
06 inh(Tool, selectAbstractTool)
07 inh(Tool, cancelTool)
08 inh(selectAbstractTool, ConcreteTool1)
09 inh(selectAbstractTool, ConcreteTool2)
10 inh(selectAbstractTool, ConcreteTool1)
11 inh(selectAbstractTool, ConcreteTool2)
12 has-method(createTool, createTool.method1)
13 has-method(createTool, createTool.method2)
14 has-method(cancelTool, cancelTool.method1)
15 has-method(cancelTool, cancelTool.method2)
16 has-method(selectAbstractTool, selectAbstractTool.method1)
17 has-method(selectAbstractTool, selectAbstractTool.method2)
18 has-method(ConcreteTool1, ConcreteTool1.method1)
19 has-method(ConcreteTool1, ConcreteTool1.method2)
20 has-method(ConcreteTool2, ConcreteTool2.method1)
21 has-method(ConcreteTool2, ConcreteTool2.method2)
22 has-method(receiver, receiver.operation)
23 same-Signature(createTool.method1, Tool.method1)
24 same-Signature(createTool.method2, Tool.method2)
25 same-Signature(cancelTool.method1, Tool.method1)
26 same-Signature(cancelTool.method2, Tool.method2)
27 same-Signature(selectAbstractTool.method1, Tool.method1)
28 same-Signature(selectAbstractTool.method2, Tool.method2)
29 aggre(DrawControl, Tool)
30 asso(Toolclient, selectAbstractTool)
31 asso(createTool, receiver)
32 invoke(createTool.method2, receiver.operation)

表 3中,01行与02行表示工具Tool类中存在2个不同的方法method1与method2,03行表示存在一个selectAbstractTool的抽象类,而04行~11行表示角色间存在继承关系,12~22行表示各个类中存在不同方法,23行~28行表示存在同名的方法,29行~32行依次表示角色间存在聚合、关联、方法调用等关系。

2.4 候选者集

CSP约束集映射域集D中的元素及关系成为参与者角色,表 4描述了图 3中参与者与设计模式的映射关系。例如,候选者DrawControl扮演了State模式中的Context角色,候选者Tool扮演了State模式中的State角色,而候选者createTool、cancelTool、selectAbstractTool都扮演了State模式中的ConcreteState角色。然而这些候选者集中仍可能存在假阳性结果。为此本文在Guéhéneuc等[21]提出基于CSP设计模式检测方法基础上,通过增加线索对传统CSP方法取得的候选者集做进一步的筛选。

表 4 基于CSP的实例候选者集表示 Table 4 Candidate set representation of an example by CSP
(1) State模式:
Context: DrawControl
State: Tool
ConcreteState: createTool, cancelTool, selectAbstractTool
(2) Abstract Factory模式:
AbstractFactory: selectAbstractTool
ConcreteFactory: ConcreteTool1, ConcreteTool2
Client: Toolclient

3 基于线索的设计模式实例表示

针对传统CSP方法检测结果精确性不高的问题,本文提出一种融入专家经验的线索概念。线索实质是对设计模式参与者角色及其关系进行条件约束,侧重专家经验的反馈,该过程有助于发现自动检测方法难以挖掘的有效信息,并有助于对传统CSP方法检测结果的进一步求精。

3.1 线索的形成

当获取了专家的反馈信息后,研究者依据共性结果的占有率进行筛选,优先选择占有率较高的,并转换为CSP形式的线索,线索可以是简单的静态约束信息,也可以是难以挖掘的动态约束信息等。本文中挖掘线索的过程是可迭代的,这有利于积累更多有用的约束信息,从而引导约束解析器取得更精确的结果。

3.2 线索的分类

本文按功能将线索分为3类。

1) 静态线索

静态线索指设计模式实例中的类、方法、属性及继承关系等信息。静态线索能为用户提供更多构建不同设计模式的角色信息,并有助于减少设计模式的候选者集。传统的设计模式识别工具只能检测基本的设计模式静态信息,而一些专家反馈的复杂线索很难被挖掘,这类线索需要通过对表 1中给出的符号定义进行组合,并通过工具Z3[22]编译后实现,表 5给出了部分静态线索。

表 5 静态线索 Table 5 Static clues
序号 线索描述 操作步骤
S-Clue1 类A是类B的子类,且A中的方法m1能重写类B中的同名方法m abst-class(B)
abst-method(m)
has-method(B, m)
has-method(A, m1)
inh(A, B)
override(A, m)
same-Signature(m, m1)
S-Clue2 类A是一个抽象类或接口 class(A)=abst-class(A)∨
Interface(A)
S-Clue3 同一个类A中的方法m1调用另外一种方法m2 class(A)
has-method(A, m1)
has-method(A, m2)
invoke(m1, m2)

图 3为例,selectAbstractTool类为抽象类,该类中的方法method1与method2也为抽象方法,具体的实现需要通过ConcreteTool1与ConcreteTool2类中的方法method1与method2完成,传统的检测方法仅考虑类的继承关系,而没有进一步考虑类中方法是否为抽象方法?方法之间的调用先后顺序如何?依据表 5中的静态线索S-Clue1,故selectAbstractTool类不适合扮演State模式中的ConcreteState角色,进而筛选掉该不合适的候选参与者。

2) 动态线索

动态线索侧重设计模式角色间方法调用的顺序、参数传递等。动态线索难以通过源码验证,这些动态线索也可以通过增加约束信息来实现。表 6给出了部分动态线索。

表 6 动态线索 Table 6 Dynamic clues
序号 线索描述 操作步骤
D-Clue1 在执行方法m2之前需要调用方法m1 dominate(m1, m2)
D-Clue2 方法m1被方法m2调用,且必须在非同一个类中的方法m2终止运行之前 class(A)
class(B)
has-method(A, m1)
has-method(B, m2)
invoke(m1, m2)
dominate(m1, m2)
D-Clue3 类A中的方法m1在调用类B中的方法m2之前,必须先让类B中的方法m2调用类C的方法m3 class(A)
class(B)
class(C)
has-method(A, m1)
has-method(B, m2)
has-method(C, m3)
dominate(m2, m3)
dominate(m2, m1)
invoke(m1, m2)
invoke(m2, m3)

图 3为例,要实现类Tool中方法method2需依赖createTool类中的method2方法,但该方法需createTool类中的method2方法调用receiver类的operation方法之后才能实现,而传统的方法没有考虑不同类之间方法调用的顺序,依据表 6中动态线索D-Clue3, 故createTool类也不适合扮演State模式中的ConcreteState角色,从而进一步筛选掉静态线索阶段不能排除的候选参与者。

3) 专家经验线索

用户可以增加除静态线索与动态线索之外的专家经验线索,这些线索一般依靠专家的经验知识与直觉产生,没有固定的规律,专家经验线索也有助于用户识别或筛选不合适的设计模式候选参与者,表 7描述了部分专家经验线索。

表 7 专家经验线索 Table 7 Expert experience clues
序号 线索描述 操作步骤
E-Clue1 子类中的方法不能重写父类中的重名方法 class(A)
has-method(m1)
classes(A1, …, An)
inh(A1, …, An, A)
Not(override(A1, …, An, m1))
has-method(A1, …, An, m2)
Not (same-Signature(m1, m2))

在依次经过3类线索分阶段逐步筛选后,图 3中的设计模式候选者集如表 8所示。createTool、cancelTool、selectAbstractTool 3个候选参与者只有cancelTool适合扮演ConcreteState角色,最终图 3恢复了一个State模式与一个Abstract Factory模式。

表 8 优化后的设计模式候选者 Table 8 Optimized design pattern candidates
(1) State模式候选者:
Context: DrawControl
State: Tool
ConcreteState: cancelTool
(2) Abstract Factory模式候选者:
AbstractFactory: selectAbstractTool
ConcreteFactory: ConcreteTool1, ConcreteTool2
Client: Toolclient

4 专家知识获取

实验研究证明,软件设计者习惯于对目标工作进行科学的概念假设,而这些假设问题融入具体的软件设计方案后将带来积极的效果,一个合适策略的选择主要依赖于研究的目的及调查的条件[23]。为此本文中线索的获取以纸质调查表的形式进行。为了收集更有意义的调研反馈信息,选取了Apache ant v1.6.2、JhotDraw 6.0b1、QuickUML2001、Junit v3.8 4个开源系统中的4个方案,每个方案有3个基础选项,包括联系方式、调查对象的职业与对设计模式的熟悉程度。此外,每个方案中有6个专业选项题,而每个专业选项题可为一个线索的候选者,调查表如图 4所示。

图 4 调查表 Fig. 4 Questionnaire

这次调查共回收调查表512份,经统计有效结果共452份,具体结果如表 9所示。表中:VN(Very Negative)、N(Negative)、NS(Not Significant)、P(Positive)、VP(Very Positive)依次表示选择调查表中的5种选择结果。线索名由方案序列、线索序列及是否为阳性或阴性结果标识位共3部分组成。如表 9中线索名S1-C1-P,S表示方案(Scheme),S1即为方案1,C1中的C表示方案S1中的线索(Clue),C1表示为线索1,P表示阳性结果,N表示阴性结果。通过评议将4个方案中的24条线索依据阳性结果与阴性结果进行分类,并各有12条,此后将VP与P相加的结果按照降序进行排序,并选择保留阳性结果排名前8的线索。例如第1行S1-C1-P线索,由于该线索名的第3部分是“P”,即阳性线索,故只需计算其P与VP结果之和,其中P占比为40.5%,VP占比为29%,累加结果为69.5%。同理将表 9中VN与N的阴性结果相加进行排序,选择按降序排名前8的阴性结果作为线索。例如线索S1-C2-N,由于该线索名的第3部分为“N”,故只需计算其N与VN的阴性结果之和,其中N占比为54.2%, VN占比为22.4%,累加结果为76.6%。表 9中加粗的线索名表示筛选后有价值的线索。“排序”列中P1~P8表示阳性线索筛选结果降序前8名;同理,“排序”列中的N1~N8表示阴性线索筛选结果降序前8名。为此对共计16条线索进行了基于CSP的符号表示,这些线索已通过工具Z3[22]编译。

表 9 线索的选择 Table 9 Selection of clues
线索名 VN占比/% N占比/% NS占比/% P占比/% VP占比/% 排序
S1-C1-P 0 10.2 20.3 40.5 29 P8
S1-C2-N 22.4 54.2 10.4 10.6 2.4 N5
S1-C3-N 41.3 26.7 21.4 10.6 0
S1-C4-P 0.9 6.1 40.3 31.5 21.2
S1-C5-P 4.1 9.6 23.2 41.5 21.6
S1-C6-P 1.2 3.1 19 44.6 32.1 P4
S2-C1-P 8.2 8.9 30.9 26.6 25.4
S2-C2-P 1 3.1 10.2 49.6 36.1 P2
S2-C3-N 36.8 29.5 28 3.7 2
S2-C4-N 29.5 41.8 19 7.2 2.5 N8
S2-C5-N 37.1 46.3 8 6.6 2 N3
S2-C6-P 0 11 19 48.7 21.3 P7
S3-C1-N 37.8 48.4 12.3 1.4 0.1 N2
S3-C2-N 22 47.6 16.3 8.1 6
S3-C3-N 29.6 49.4 17.6 3.1 0.3 N4
S3-C4-P 0.2 2.1 19.1 57.3 21.3 P3
S3-C5-P 3 7.3 18.6 51.9 19.2 P5
S3-C6-P 0.8 7.9 20.2 61.3 9.8 P6
S4-C1-P 4.1 12.6 19.7 42.3 21.3
S4-C2-N 35.6 52.6 9 2.3 0.5 N1
S4-C3-P 6.6 12.6 18.8 46 16
S4-C4-N 41.6 34.9 9.9 9.2 4.4 N6
S4-C5-P 0.2 0.2 1 49.6 49 P1
S4-C6-N 22.9 49.8 21.5 4.2 1.6 N7

5 实验设计与分析

为评估本文的有效性,选用Junit v3.8等4个开源系统进行了设计模式检测实验。表 10描述了这些开源系统的特征参数,而选择这些开源软件系统的依据是:① 系统采用了不同的设计模式进行开发,使得待检测的模式实例具备多样性;② 众多科研工作者皆以此为例进行设计模式检测实验,并存在一个或多个相似的基准例子,方便结果比较;③ 这些系统是开源的项目,可以免费进行设计模式识别,从而降低成本;④ 这些系统有典型的差异性,因此更具代表性。执行实验的操作系统采用Windows XP,CPU为AMD速龙Ⅱ X4 650, 主频3.2 GHz,内存16 G。

表 10 开源系统特征参数 Table 10 Characteristic parameters of open source system
系统名称 类数 千行代码的数目
JhotDraw 6.0b1 300 19
Junit v3.8 56 4
Apache ant v1.6.2 79 566 895
QuickUML2001 8 792 203

5.1 实验指标

实验评估采用精确率(Pr)、召回率(R)、F-score(F)等指标。此外,也应意识到当待测试系统规模较大时,假阳性FP(False Positive)、假阴性FN(False Negative)的检测结果易产生误差。精确率Pr和召回率R的检测结果决定本文方法的效果,而精确率和召回率又依赖真阳性TP(True Positive)、假阳性FP和假阴性FN 3个重要指标。

1) 真阳性TP:表示正确模式实例检测结果为正确。

2) 假阳性FP:表示错误模式实例检测结果为正确。

3) 假阴性FN:表示正确模式实例检测结果为错误。

(3)
(4)

Petterson等[19]提出了融合精确率Pr与召回率R的F-score指标,式(5) 中W为权值,其值给定为2.8,F-score值与设计模式实例恢复的效果成正比。

(5)
5.2 开源系统设计模式指标值

为方便检测结果的交叉比较,并考虑到设计模式的创建型、行为型及结构型分类[2],依据参考文献[12, 18-19]的结果,项目组成员在此基础上以人工的形式对表 10中4个开源系统的Adapter等4种具有代表性的3类设计模式进行了复核,并通过多次同行评议后给出了表 11的基准结果。

表 11 开源系统中设计模式基准 Table 11 Benchmark of design patterns in open source systems
系统名称 设计模式 模式实例数
Apache ant v1.6.2 Adapter 65
State 4
Command 4
Singleton 3
JhotDraw 6.0b1 Adapter 35
State 3
Command 2
Singleton 2
QuickUML2001 Adapter 38
State 2
Command 1
Singleton 1
Junit v3.8 Adapter 14
State 0
Command 0
Singleton 2

5.3 3类线索分阶段检测实验

本文旨在检测设计模式实例抽取过程中线索对结果的影响。实验将在原有的CSP检测结果基础上分静态线索、动态线索及专家经验线索阶段逐步进行检测实验,为取得最佳效果,实验允许每个阶段增加线索的过程可迭代。

分析表 12的结果发现,传统的CSP识别技术对State与Singleton模式的识别效果不够理想,2种模式的F指标平均值皆为0%,而Command模式F指标平均值也仅为23%,值得注意的是,Adapter模式的识别效果相对较好,虽然4个开源系统检测后的Adapter模式F指标平均值达到74%,但仍然存在大量的假阳性结果FP与假阴性结果FN。

表 12 传统CSP方法检测与静态线索阶段检测结果 Table 12 Detection results of design pattern in traditional CSP method and static clue stage
设计模式 测试系统 传统CSP方法阶段 静态线索阶段
TP个数 FP个数 FN个数 Pr/% R/% F/% TP个数 FP个数 FN个数 Pr/% R/% F/%
Adapter Apache ant v1.6.2 46 22 18 68 72 72 60 16 4 79 94 92
JhotDraw 6.0b1 30 12 5 71 86 84 33 10 2 77 94 92
QuickUML2001 27 15 11 64 71 70 30 12 8 71 79 78
Junit v3.8 10 6 4 63 71 70 11 5 3 69 79 78
平均值 66.5 75 74 74 86.5 85
State ]Apache ant v1.6.2 0 22 4 0 0 0 18 4 0 0
JhotDraw 6.0b1 0 18 3 0 0 1 16 2 6 33 22
QuickUML2001 0 13 2 0 0 0 6 2 0 0
Junit v3.8 0 0 0 0 4 0 0
平均值 0 0 0 1.5 11 22
Command Apache ant v1.6.2 1 6 3 14 25 23 1 4 3 20 25 24
JhotDraw 6.0b1 0 4 2 0 0 0 1 2 0 0
QuickUML2001 0 4 1 0 0 0 3 1 0 0
Junit v3.8 0 6 0 0 0 3 0 0
平均值 3.5 8.3 23 5 6.3 24
Singleton Apache ant v1.6.2 0 8 3 0 0 0 1 4 2 20 33 31
JhotDraw 6.0b1 0 6 2 0 0 0 0 3 2 0 0
QuickUML2001 0 4 1 0 0 0 0 3 1 0 0
Junit v3.8 0 4 2 0 0 0 1 3 1 25 50 45
平均值 0 0 0 11.3 20.8 38

为解决上述问题,本文在静态线索阶段增加了源码结构类、属性、方法、继承关系等线索,从而使检测结果的正确性有所提高。例如,静态线索阶段Adapter模式的F指标平均值由原来的74%上升到85%,而State、Command、Singleton模式的识别效果F指标平均值依次为22%、24%、38%,较传统基于CSP的检测方法有所提高。

为进一步提高检测结果的精确率,本文继续在表 13动态线索阶段增加涉及源码角色间方法调用、参数传递等约束信息的线索引入,从而使得该阶段4个设计模式的平均精确率Pr及平均F值较静态线索阶段有质的提高。分析表 12表 13的结果发现,动态线索阶段Adapter模式的F指标平均值由静态线索的85%上升到95%,而其精确率Pr指标平均值也由原来静态阶段的74%上升到85%,而State、Command、Singleton模式的识别指标F值较静态线索阶段也有所提高,依次提升为63%、82.3%、88%,该阶段假阳性结果FP与假阴性结果FN显著降低。

表 13 动态线索阶段与专家经验线索阶段检测结果 Table 13 Detection results of design pattern in dynamic clue stage and expert experience clue stage
设计模式 测试系统 动态线索阶段 专家经验线索阶段
TP个数 FP个数 FN个数 Pr/% R/% F/% TP个数 FP个数 FN个数 Pr/% R/% F/%
Adapter Apache ant v1.6.2 63 12 1 84 98 96 64 0 1 100 98 98
JhotDraw 6.0b1 34 7 1 83 97 95 35 0 0 100 100 100
QuickUML2001 38 6 0 86 100 98 38 0 0 100 100 100
Junit v3.8 13 2 1 87 93 92 14 0 0 100 100 100
平均值 85 97 95 100 99.5 99.5
State Apache ant v1.6.2 3 12 1 20 75 57 3 0 1 100 75 77
JhotDraw 6.0b1 3 3 0 50 100 90 3 0 0 100 100 100
QuickUML2001 1 4 1 20 50 43 2 0 0 100 100 100
Junit v3.8 0 2 0 0 0 0 0
平均值 22.5 75 63 100 91.7 92.3
Command Apache ant v1.6.2 3 3 1 50 75 71 4 0 0 100 100 100
JhotDraw 6.0b1 2 1 0 67 100 95 2 0 0 100 100 100
QuickUML2001 1 2 0 33 100 81 1 0 0 100 100 100
Junit v3.8 0 2 0 0 0 0 0
平均值 37.5 91.7 82.3 100 100 100
Singleton Apache ant v1.6.2 2 1 1 67 67 67 3 0 0 100 100 100
JhotDraw 6.0b1 2 1 0 67 100 95 2 0 0 100 100 100
QuickUML2001 1 1 0 50 100 90 1 0 0 100 100 100
Junit v3.8 2 0 0 100 100 100 2 0 0 100 100 100
平均值 71 91.75 88 100 100 100

专家经验线索阶段主要依据专家经验和直觉将一些动态线索与静态线索难以发现的常用知识引入,该阶段进一步排除了假阳性结果FP与假阴性结果FN,识别结果也更加精确,此阶段后Adapter、State、Command、Singleton 4种模式的F指标平均值依次为99.5%、92.3%、100%、100%。

综合表 12表 13数据发现以下2个问题:

1) 传统的CSP检测方法对4个测试系统中Adapter模式的检测效果较好,而对State、Command、Singleton模式的检测结果不理想。分析原因发现,Adapter属于结构型模式,State、Command属于行为型模式,Singleton属于创建型模式。Gamma将设计模式分为结构型、行为型、创建型3类[1],分析3类设计模式特征发现,行为型模式存在难以追踪的复杂控制流、方法调用机制及参数传递方式等,而创建型模式存在委托等难以复用的关系,以至于很难被共享,可理解为较难发生设计模式实例识别中的重叠问题,而结构型模式使用组合类及对象的方式获得详细的信息,并采用继承机制组合接口,这种方式使其结构具有更强的可扩展性,也更容易被检测。

2) 表 13中,Apache ant v1.6.2系统中在专家经验线索阶段Adapter模式的平均F值为99.5%,经研究发现,该模式在此阶段的FN值为1,即存在一个假阴性结果。经深入研究后发现,由于Adapter与Command模式结构较为相似, 致使Adapter模式被错误识别为Command模式。此外,表 13中,Apache ant v1.6.2系统中在专家经验线索阶段State模式的F值为77%,经研究发现,该模式在此阶段的FN值为1,即也存在一个假阴性结果。由于State与Strategy[1]模式结构较为相似, 致使State模式被错误识别为Strategy模式。

综上所述,上述问题归因于:① 相近设计模式实例之间角色的重叠原因;② 设计模式变体的影响;③ 缺乏对源码中动态数据流的及时分析,导致缺乏对方法调用、参数传递等操作的跟踪与识别。虽然本文方法能够一定程度上解决设计模式实例的重叠问题,但仍不能完全避免假阳性结果与假阴性结果,下一步工作将在上述问题基础上继续深入研究,并发现更多有价值的线索,以取得更好的识别效果。

表 14描述了Apache ant v1.6.2等4个测试系统中Adapter等4个模式实例存在重叠问题的数目,而最后一行统计了4个测试系统中不同设计模式实例发生重叠的总数, 4个测试系统总共识别的Adapter、State、Command及Singleton重叠实例数依次为11、2、3、1。图 5描述了表 14中4种设计模式重叠实例被成功识别的百分比。其中,Adapter模式的实例重叠情况较明显为65%,而深入思考发现Adapter模式属于结构型模式,结构型模式依据组合类及对象以获得更复杂的结构信息,并采用继承机制来组合接口或实现,这样的特点使其结构具有更大的可扩展性,也更容易被识别。

表 14 4个系统设计模式实例重叠统计 Table 14 Design pattern instance overlap statistics in four systems
测试系统 重叠实例数
Adapter State Command Singleton
Apache ant v1.6.2 4 1 1 1
JhotDraw 6.0b1 2 1 1 0
QuickUML2001 4 0 1 0
Junit v3.8 1 0 0 0
结果统计 11 2 3 1

图 5 4种模式重叠实例识别所占百分比 Fig. 5 Identification percentage of four types of pattern overlapping instances

表 15给出了部分表 14中共享了设计模式的实例。例如,State模式实例与Stratgey[1]模式实例存在重叠,而CH.ifa.draw.framework.DrawingView同时扮演State模式中的Context角色与Stratgey[1]模式中的Context角色,CH.ifa.draw.framework.Painter也同时扮演State模式中的State角色以及Stratgey[1]模式中的Stratgey角色,这属于设计模式中部分角色共享模式实例的情况。此外,Command模式实例属于角色完全共享模式实例的情况,因为Command模式实例与Adapter模式实例发生了完全重叠,其中CH.ifa.draw.util.Command同时扮演了Command模式中Command角色及Adapter模式中Target角色,CH.ifa.draw.framework.DrawingView扮演了Command模式中的Receiver角色及Adapter模式中的Target角色,CH.ifa.draw.util.CommandButton扮演了Command模式中的Invoke角色及Adapter模式中的Adaptee角色。

表 15 JhotDraw中共享了模式的实例 Table 15 Instances of shared pattern in JhotDraw
(1) State模式实例: //共享部分实例角色
Context: CH.ifa.draw.framework.DrawingView
State: CH.ifa.draw.framework.Painter
(2) Comand模式实例: //共享全部实例角色
Command: CH.ifa.draw.util.Command
Receiver:CH.ifa.draw.framework.DrawingView
Invoke: CH.ifa.draw.util.CommandButton

5.4 比较实验设计

5.3节中将本文方法与基于CSP的检测方法通过精确率、召回率、F-score指标分阶段进行了比较实验,为进一步检验本文方法,还增加了参考文献[8, 12-13, 15, 18]中提出的方法进行F-score比较实验。

由于在传统的CSP方法基础上融入了交互式线索,并分3个阶段逐步消除假阴性与假阳性结果,由表 16 F-score值可以看出本文方法取得了较好的效果。

表 16 F-score指标比较 Table 16 F-score index comparison
检测方法 精确率平均值/% 召回率平均值/% F-score平均值/%
本文方法 100 97.8 97.95
文献[8] 93.8 62.1 64.57
文献[12] 91.14 67.21 69.27
文献[13] 67.76 82.11 80.19
文献[15] 93.65 71.82 73.77
文献[18] 38.74 100 84.83

6 结论

针对传统设计模式实例恢复结果不够精确及不易于扩展等问题,本文提出一种多阶段交互式线索驱动的设计模式识别方法。

1) 在抽取Guéhéneuc等[21]提出约束满足问题(CSP)方法结果的基础上,将调研取得的专家经验进行反馈,并进一步形成可自定义的线索,避免了不易扩展的问题。

2) 通过线索的约束作用,以迭代的形式分阶段对检测结果进行筛选,避免设计模式实例识别的假阴性与假阳性结果,使得精确率显著提高。

3) 在设计模式实例重叠问题检测方面取得了较好的效果,使得设计模式识别结果进一步优化。

在下一步工作中将对专家经验知识的采样、筛选及如何将演化计算等技术融入设计模式检测展开研究。此外,为了检验本文研究的效果, 将通过更多的开源系统进行验证。

参考文献
[1] 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. DOI:10.1109/TSE.2011.79
[2] 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.
[3] AMPATZOGLOU A, FRANTZESKOU G, STAMELOS I. A methodology to assess the impact of design patterns on software quality[J]. Information and Software Technology, 2012, 54 (4): 331–346. DOI:10.1016/j.infsof.2011.10.006
[4] 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. DOI:10.1016/j.jss.2013.03.063
[5] 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. DOI:10.1002/smr.v25.1
[6] 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. DOI:10.1016/j.jss.2011.07.006
[7] 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.
[8] 肖卓宇, 何锫, 余波, 等. 基于FCA与CBR的设计模式检测[J]. 山东大学学报(工学版), 2016, 46 (2): 22–28.
XIAO Z Y, HE P, YU B, et al. Design patterns detection based on FCA and CBR[J]. Journal of Shandong University (Engineering Science), 2016, 46 (2): 22–28. DOI:10.6040/j.issn.1672-3961.1.2015.046 (in Chinese)
[9] CHIHADA A, JALILI S, HASHEMINEJAD S M H, et al. Source code and design conformance, design pattern detection from source code by classification approach[J]. Applied Soft Computing, 2015, 26 (1): 357–367.
[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] YU D, ZHANG Y, GE J, et al.From sub-patterns to patterns:An approach to the detection of structural design pattern instances by subgraph mining and merging[C]//2013 IEEE 37th Annual Computer Software and Applications Conference (COMPSAC).Piscataway, NJ:IEEE Press, 2013:579-588.
[12] DONG J, ZHAO J, SUN Y. A matrix based approach to recovering design patterns[J]. IEEE Transactions on Systems, Man and Cybernatics, 2009, 39 (6): 1271–1282. DOI:10.1109/TSMCA.2009.2028012
[13] BERNARDI M L, CIMITILE M, DI LUCCA G. Design pattern detection using a DSL-driven graph matching approach[J]. Journal of Software:Evolution and Process, 2014, 26 (12): 1233–1266. DOI:10.1002/smr.v26.12
[14] SABO M, PORUBÄN J. Preserving design patterns using source code annotations[J]. Journal of Computer Science and Control Systems, 2009, 32 (2): 53–56.
[15] RASOOL G, PHILIPPOW I, MADER P. Design pattern recovery based on annotations[J]. International Journal of Advances in Engineering Software, 2010, 41 (4): 519–526. DOI:10.1016/j.advengsoft.2009.10.014
[16] RASOOL G, MÄDER P. A customizable approach to design patterns recognition based on feature types[J]. Arabian Journal for Science and Engineering, 2014, 39 (12): 8851–8873. DOI:10.1007/s13369-014-1449-0
[17] GARLAN D, MONROE R, WILE D.ACME:An architecture description interchange language[C]//CASCON'97 Proceedings of the 1997 Conference of the Centre for Advanced Studies on Collaborative Research, 2010:159-173.
[18] GUÉHÉNEUC Y G, ANTONIOL G. DeMIMA:A multilayered approach for design pattern identification[J]. IEEE Transactions on Software Engineering, 2008, 34 (5): 667–684. DOI:10.1109/TSE.2008.48
[19] PETTERSON N, LÖWE W, NIVRE J. Evaluation of accuracy in design pattern occurrence detection[J]. IEEE Transactions on Software Engineering, 2010, 36 (4): 575–590. DOI:10.1109/TSE.2009.92
[20] 肖卓宇, 何锫, 黎妍. 基于设计模式角色的附加关系检测研究[J]. 计算机应用研究, 2015, 32 (7): 2042–2045.
XIAO Z Y, HE P, LI Y. Study on the additional relationships based on design pattens's roles[J]. Application Research of Computers, 2015, 32 (7): 2042–2045. (in Chinese)
[21] GUÉHÉNEUC Y G, GUYOMARC'H J Y, SAHRAOUI H. Improving design-pattern identification:A new approach and an exploratory study[J]. Software Quality Journal, 2010, 18 (1): 145–174. DOI:10.1007/s11219-009-9082-y
[22] KITCHENHAM B A, PFLEEGER S L, PICKARD L M, et al. Preliminary guidelines for empirical research in software engineering[J]. IEEE Transactions on Software Engineering, 2002, 28 (8): 721–734. DOI:10.1109/TSE.2002.1027796
[23] MERA S, BJØRNER N.DKAL and Z3:A logic embedding experiment[M]//BLASS A, DERSHOWITZ N, REISIG W.Fields of logic and computation.Berlin:Springer, 2010:504-528.
http://dx.doi.org/10.13700/j.bh.1001-5965.2016.0750
北京航空航天大学主办。
0

文章信息

肖卓宇, 何锫, 余波
XIAO Zhuoyu, HE Pei, YU Bo
一种多阶段交互式线索驱动的设计模式识别方法
A multi-stage approach based on interactive clues driven for design pattern identification
北京航空航天大学学报, 2017, 43(9): 1746-1756
Journal of Beijing University of Aeronautics and Astronsutics, 2017, 43(9): 1746-1756
http://dx.doi.org/10.13700/j.bh.1001-5965.2016.0750

文章历史

收稿日期: 2016-09-20
录用日期: 2016-12-09
网络出版时间: 2016-12-26 17:07

相关文章

工作空间