留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种多阶段交互式线索驱动的设计模式识别方法

肖卓宇 何锫 余波

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

一种多阶段交互式线索驱动的设计模式识别方法

doi: 10.13700/j.bh.1001-5965.2016.0750
基金项目: 

国家自然科学基金 61170199

湖南省教学改革研究立项项目 湘教通[2016]400号1068

广东省自然科学基金 2015A030313501

广东省普通高校创新团队建设项目 2015KCXTD014

详细信息
    作者简介:

    肖卓宇   男, 副教授, 高级工程师; 主要研究方向:程序理解、逆向工程、软件演化

    通讯作者:

    肖卓宇, E-mail:xzyxzy0770@126.com

  • 中图分类号: TP311

A multi-stage approach based on interactive clues driven for design pattern identification

Funds: 

National Natural Science Foundation of China 61170199

Project Number 1068 Supported by Circular of Hunan Provincial Education Department in 2016 No.400 湘教通[2016]400号1068

Natural Science Foundation of Guangdong Province 2015A030313501

Construction Project of Innovation Team in Universities in Guangdong Province 2015KCXTD014

More Information
  • 摘要:

    针对传统设计模式自动检测不够精确及不易于扩展的问题,为提高设计模式实例恢复的精确性,提出一种多阶段交互式线索驱动的设计模式识别方法。在传统基于约束满足问题(CSP)的设计模式检测思想基础上引入了线索的思想,旨在经过调研对专家经验知识进行反馈,并将筛选后有价值的线索表示为CSP形式的信息,进而依据信息特征将线索分类,通过在设计模式检测过程中逐步增加线索,直至设计模式实例候选参与者集产生。实验结果表明,本文方法不仅分阶段筛选了设计模式检测实例的假阴性与假阳性结果,还解决了设计模式识别的重叠问题,通过与其他主流检测方法的F-score指标值对比,取得了较好的检测效果。

     

  • 图 1  设计模式实例识别流程

    Figure 1.  Design pattern instance identification flowchart

    图 2  Abstract Factory模式与State模式类图

    Figure 2.  Class diagram of Abstract Factory pattern and State pattern

    图 3  用例类图

    Figure 3.  Example class diagram

    图 4  调查表

    Figure 4.  Questionnaire

    图 5  4种模式重叠实例识别所占百分比

    Figure 5.  Identification percentage of four types of pattern overlapping instances

    表  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方法被重写
    下载: 导出CSV

    表  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)//角色是否一致比较
    下载: 导出CSV

    表  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)
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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)
    下载: 导出CSV

    表  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)
    下载: 导出CSV

    表  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))
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV
  • [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. http://www.academia.edu/22417252/Documenting_Design-Pattern_Instances_a_Family_of_Experiments_on_Source_Code_Comprehensibility
    [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. http://dl.acm.org/citation.cfm?id=2902376.2902591
    [8] 肖卓宇, 何锫, 余波, 等.基于FCA与CBR的设计模式检测[J].山东大学学报(工学版), 2016, 46(2):22-28. doi: 10.6040/j.issn.1672-3961.1.2015.046

    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(in Chinese). doi: 10.6040/j.issn.1672-3961.1.2015.046
    [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. http://www.sciencedirect.com/science/article/pii/S1568494614005389
    [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. http://www.sciencedirect.com/science/article/pii/S016412121500014X
    [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. http://www.oalib.com/paper/2779809
    [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. http://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201507032.htm

    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). http://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201507032.htm
    [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.
  • 加载中
图(5) / 表(16)
计量
  • 文章访问数:  721
  • HTML全文浏览量:  117
  • PDF下载量:  375
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-09-20
  • 录用日期:  2016-12-09
  • 网络出版日期:  2017-09-20

目录

    /

    返回文章
    返回
    常见问答