A multi-stage approach based on interactive clues driven for design pattern identification
-
摘要:
针对传统设计模式自动检测不够精确及不易于扩展的问题，为提高设计模式实例恢复的精确性，提出一种多阶段交互式线索驱动的设计模式识别方法。在传统基于约束满足问题（CSP）的设计模式检测思想基础上引入了线索的思想，旨在经过调研对专家经验知识进行反馈，并将筛选后有价值的线索表示为CSP形式的信息，进而依据信息特征将线索分类，通过在设计模式检测过程中逐步增加线索，直至设计模式实例候选参与者集产生。实验结果表明，本文方法不仅分阶段筛选了设计模式检测实例的假阴性与假阳性结果，还解决了设计模式识别的重叠问题，通过与其他主流检测方法的F-score指标值对比，取得了较好的检测效果。
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.
-
图 2 Abstract Factory模式与State模式类图
Figure 2. Class diagram of Abstract Factory pattern and State pattern
图 5 4种模式重叠实例识别所占百分比
Figure 5. Identification percentage of four types of pattern overlapping instances
符号 描述 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
-
[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.046XIAO 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.htmXIAO 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. -
下载:
点击查看大图
计量
- 文章访问数: 813
- HTML全文浏览量: 148
- PDF下载量: 377
- 被引次数: 0
