設(shè)計(jì)模式檢測(cè)工具有效性評(píng)估策略*

肖卓宇，黃 海，何 锫，李 港，楊道武，彭逸凡，董澤民

1.中南林業(yè)科技大學(xué) 涉外學(xué)院，長(zhǎng)沙 410200

2.廣東第二師范學(xué)院 計(jì)算機(jī)科學(xué)系，廣州 510303

3.北京大學(xué) 高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100871

4.廣州大學(xué) 計(jì)算機(jī)科學(xué)與教育軟件學(xué)院，廣州 510006

1 引言

設(shè)計(jì)模式常用于構(gòu)建可復(fù)用的解決方案，而自動(dòng)檢測(cè)設(shè)計(jì)模式有助于研發(fā)人員在缺乏文檔支撐的情況下提高軟件質(zhì)量[1]。目前在程序理解、維護(hù)、重構(gòu)、逆向工程與再工程領(lǐng)域，設(shè)計(jì)模式檢測(cè)工具的應(yīng)用被廣大研發(fā)人員所關(guān)注，但如何選擇合適的檢測(cè)工具成為困擾軟件從業(yè)人員的一個(gè)難題[2-3]。

Bernardi等人[4]提出通過圖形映射參與者，并以DSL匹配方法來檢測(cè)設(shè)計(jì)模式。Fontana等人[5-6]將設(shè)計(jì)模式的特征信息以EDP（elemental design pattern）、Clues等微結(jié)構(gòu)的形式表示，并通過這些微結(jié)構(gòu)來識(shí)別設(shè)計(jì)模式。Zanoni[7]與Chihada[8]等人將機(jī)器學(xué)習(xí)引入到設(shè)計(jì)模式檢測(cè)領(lǐng)域，二者皆側(cè)重特征值的訓(xùn)練。許涵斌等人[9]提出通過查詢與匹配UML模型中的特征信息來恢復(fù)設(shè)計(jì)模式。古輝等人[10]通過鄰接表與聯(lián)通分量縮小搜索空間來優(yōu)化特征信息，進(jìn)而識(shí)別設(shè)計(jì)模式。肖卓宇等人[11]結(jié)合形式概念分析與實(shí)例推理技術(shù)，通過余弦理論來優(yōu)化設(shè)計(jì)模式檢測(cè)結(jié)果。文獻(xiàn)[12]提出一種基于矩陣積分評(píng)估的設(shè)計(jì)模式檢測(cè)方法，旨在通過子圖同構(gòu)的方法來提升設(shè)計(jì)模式檢測(cè)效果。Ampatzoglou等人[13-14]通過實(shí)驗(yàn)評(píng)估了部分主流檢測(cè)工具的模式實(shí)例基準(zhǔn)庫。Petterson等人[15]提出設(shè)計(jì)模式變體、模式基準(zhǔn)、測(cè)試用例選擇及F-score指標(biāo)等是影響設(shè)計(jì)模式精確率的主要因素。

綜上所述，設(shè)計(jì)模式檢測(cè)領(lǐng)域現(xiàn)有工作主要存在以下幾個(gè)問題：（1）現(xiàn)有檢測(cè)方法與工具較少考慮設(shè)計(jì)模式變體；（2）缺乏對(duì)設(shè)計(jì)模式參與者角色共享實(shí)例的關(guān)注；（3）大部分檢測(cè)工具未公開，導(dǎo)致設(shè)計(jì)模式檢測(cè)結(jié)果無法驗(yàn)證；（4）相似工具或低效工具重復(fù)開發(fā)；（5）待檢測(cè)系統(tǒng)規(guī)模較小；（6）待檢測(cè)系統(tǒng)設(shè)計(jì)模式實(shí)例基準(zhǔn)缺乏或不夠完善；（7）較少有文獻(xiàn)對(duì)設(shè)計(jì)模式檢測(cè)工具的有效性進(jìn)行詳細(xì)評(píng)估。

為此，本文給出一種評(píng)估設(shè)計(jì)模式檢測(cè)工具有效性的解決方案，比較并篩選了檢測(cè)工具與待檢測(cè)系統(tǒng)，完善了經(jīng)典開源系統(tǒng)設(shè)計(jì)模式實(shí)例基準(zhǔn)數(shù)，側(cè)重關(guān)注設(shè)計(jì)模式變體、實(shí)例共享等指標(biāo)，對(duì)8種主流檢測(cè)工具與9個(gè)開源系統(tǒng)進(jìn)行了評(píng)估實(shí)驗(yàn)，并以此為依據(jù)，總結(jié)了影響設(shè)計(jì)模式檢測(cè)結(jié)果精確性的有效性威脅，給出了合理性建議。

本文主要貢獻(xiàn)如下：（1）按特征屬性概述了現(xiàn)有主流設(shè)計(jì)模式檢測(cè)工具；（2）為便于交叉比較，篩選并歸納了具有代表性的檢測(cè)工具與待測(cè)試系統(tǒng)；（3）完善了主要開源系統(tǒng)的設(shè)計(jì)模式實(shí)例基準(zhǔn)；（4）通過變體、實(shí)例共享等指標(biāo)評(píng)估了現(xiàn)有工具；（5）總結(jié)了影響設(shè)計(jì)模式檢測(cè)精確率的有效性威脅，給出了合理性建議，避免相似工具重復(fù)開發(fā)。

本文組織結(jié)構(gòu)如下：第2章概述了現(xiàn)有設(shè)計(jì)模式檢測(cè)工具；第3章選擇評(píng)估實(shí)驗(yàn)所需的檢測(cè)工具；第4章描述了待檢測(cè)開源系統(tǒng)的特征；第5章依據(jù)指標(biāo)進(jìn)行評(píng)估實(shí)驗(yàn)；第6章總結(jié)了有效性威脅；第7章給出了合理化建議；第8章對(duì)全文工作進(jìn)行了總結(jié)，并對(duì)未來工作進(jìn)行了展望。

2 設(shè)計(jì)模式檢測(cè)工具概述與分類

自1995年Gamma等人[1]首次提出23種經(jīng)典的設(shè)計(jì)模式后，眾多研發(fā)人員將其應(yīng)用到MIS（management information system）系統(tǒng)中，并取得了較好的效果，但如何復(fù)用這些設(shè)計(jì)模式成為困擾研究人員的難題。設(shè)計(jì)模式檢測(cè)工具有助于輔助軟件設(shè)計(jì)師借鑒經(jīng)典的設(shè)計(jì)框架，并以較低的成本、較好的效果完成軟件項(xiàng)目設(shè)計(jì)，進(jìn)而為軟件項(xiàng)目重構(gòu)奠定堅(jiān)實(shí)的基礎(chǔ)。

近20年來，眾多研究人員在設(shè)計(jì)模式檢測(cè)工具領(lǐng)域做出了貢獻(xiàn)，并宣稱取得了較好的檢測(cè)效果，事實(shí)上，大部分工具檢測(cè)結(jié)果的精確性與可靠性仍值得商榷。為此，本文收集了1996年至2015年以來近40種檢測(cè)工具的相關(guān)信息，并分析與整理了具有代表性的22種工具[16-37]。表1描述了主流工具的相關(guān)參數(shù)，涉及工具名、作者、發(fā)布日期、支持語言、表示形式、分析方法、測(cè)試系統(tǒng)、精確率、召回率等信息。其中分析方法包括靜態(tài)分析（static analysis，SA）、動(dòng)態(tài)分析（dynamic analysis，DA）、語義分析（semantic analysis，SEA）。此外，由表1的編程語言字段可知，現(xiàn)有工具主要支持Java語言與C++語言，而分析表示形式字段發(fā)現(xiàn)眾多工具的輸入與輸出形式幾乎各不相同，這意味著較難實(shí)現(xiàn)工具間的兼容。綜上所述，本文總結(jié)了導(dǎo)致設(shè)計(jì)模式檢測(cè)工具差異的主要因素：（1）采用的檢測(cè)技術(shù)與方法；（2）檢測(cè)結(jié)果的評(píng)價(jià)指標(biāo)；（3）待檢測(cè)源碼的輸入與輸出格式。由此可見，評(píng)估現(xiàn)有設(shè)計(jì)模式檢測(cè)工具是一項(xiàng)重要的工作，有助于避免同類型工具的重復(fù)研發(fā)，降低成本。

設(shè)計(jì)模式檢測(cè)工具按如下方法進(jìn)行分類：

（1）基于相似度評(píng)分的設(shè)計(jì)模式檢測(cè)工具

該類工具傾向于將設(shè)計(jì)模式類圖轉(zhuǎn)換為矩陣形式，通過圖形理論計(jì)算設(shè)計(jì)模式矩陣與目標(biāo)矩陣的歸一化聯(lián)系，能夠較好地檢測(cè)二者間完全匹配與完全不匹配的情形，通過閾值設(shè)定也能一定程度上檢測(cè)存在結(jié)構(gòu)差異的不完全匹配的情形，但對(duì)結(jié)構(gòu)相似的Composite/Decorator模式、Strategy/State模式等識(shí)別效果不理想。該類工具以DPIDT[16]、DP-Miner[25]、DPD[28]等為典型代表，對(duì)結(jié)構(gòu)型設(shè)計(jì)模式檢測(cè)效果較好，而對(duì)行為型與創(chuàng)建型設(shè)計(jì)模式的檢測(cè)效果略顯不足，能一定程度上識(shí)別多層結(jié)構(gòu)及設(shè)計(jì)模式實(shí)例共享問題，但難以識(shí)別設(shè)計(jì)模式變體。

（2）基于邏輯推理的設(shè)計(jì)模式檢測(cè)工具

該類工具側(cè)重邏輯演算的形式化和特征信息的謂詞表示。基于邏輯推理的工具能一定程度上識(shí)別行為型與創(chuàng)建型設(shè)計(jì)模式，但識(shí)別精確率有待改進(jìn)，易出現(xiàn)假陽性與假陰性結(jié)果，對(duì)設(shè)計(jì)模式變體問題幾乎無法檢測(cè)。此外，由于邏輯推理工具需依賴制定規(guī)則，導(dǎo)致該類工具不易于擴(kuò)展。該類工具以FUJABA[34]、Pat[35]等為代表。

（3）基于機(jī)器學(xué)習(xí)的設(shè)計(jì)模式檢測(cè)工具

該類工具有較好的學(xué)習(xí)能力，能夠?qū)μ囟ǖ膶?shí)例進(jìn)行訓(xùn)練，從而獲取特征信息，并通過積累達(dá)到較好的檢測(cè)效果。相比基于邏輯推理與相似評(píng)分的工具，基于機(jī)器學(xué)習(xí)的工具能較好檢測(cè)不完整的設(shè)計(jì)模式實(shí)例，即設(shè)計(jì)模式與目標(biāo)實(shí)例的部分匹配。但該類檢測(cè)工具需要通過人工形式進(jìn)行調(diào)查分析，過度依賴專家經(jīng)驗(yàn)。此外，還需對(duì)專家調(diào)查分析結(jié)果進(jìn)行反饋，并對(duì)此不斷進(jìn)行訓(xùn)練，成本相對(duì)較高，且只對(duì)幾種特定的設(shè)計(jì)模式檢測(cè)效果較好，相比相似度評(píng)分工具，該類檢測(cè)工具能夠檢測(cè)某類特定的設(shè)計(jì)模式變體與設(shè)計(jì)模式實(shí)例共享實(shí)例。該類工具以DeMIMA[22]、JAPADET[24]、MARPLE[26]等為代表。

3 設(shè)計(jì)模式檢測(cè)工具選擇

導(dǎo)致設(shè)計(jì)模式檢測(cè)工具識(shí)別結(jié)果差異的原因是本文進(jìn)行評(píng)估比較的動(dòng)機(jī)。研究發(fā)現(xiàn)近似或精確匹配方法、算法，變體、實(shí)例共享、基準(zhǔn)等是檢測(cè)結(jié)果差異的主要因素。故選擇合適的設(shè)計(jì)模式檢測(cè)工具進(jìn)行實(shí)驗(yàn)是有意義的，這有助于評(píng)估設(shè)計(jì)模式的檢測(cè)效果，并為設(shè)計(jì)模式復(fù)用奠定堅(jiān)實(shí)的基礎(chǔ)。

Table 1 Overview of design pattern detection tools表1 設(shè)計(jì)模式檢測(cè)工具概述

本文篩選表1中設(shè)計(jì)模式檢測(cè)工具主要考慮到以下幾點(diǎn)：（1）眾多工具是否公開，未公開則不利于設(shè)計(jì)模式檢測(cè)結(jié)果的驗(yàn)證；（2）檢測(cè)工具待識(shí)別的測(cè)試系統(tǒng)規(guī)模是否偏小，即是否只存在少量的設(shè)計(jì)模式實(shí)例；（3）工具是否僅能檢測(cè)個(gè)別設(shè)計(jì)模式，不具有多樣性；（4）工具是否需要將源碼通過第三方工具轉(zhuǎn)換成中間表示形式，然后使用插件技術(shù)來實(shí)現(xiàn)設(shè)計(jì)模式的恢復(fù)；（5）因現(xiàn)有的檢測(cè)工具主要支持Java與C++語言，為方便交叉比較，極少數(shù)支持Smalltalk、C等語言的工具暫不考慮。基于上述幾點(diǎn)，本文最終選中的設(shè)計(jì)模式檢測(cè)工具見表2。表2總結(jié)了檢測(cè)工具的主要參數(shù)，如支持語言、平臺(tái)、是否開源、是否可移植等信息。

4 測(cè)試系統(tǒng)選擇

Pettersson等人[15]提出選擇合適的測(cè)試系統(tǒng)將有助于獲得精確有效且可信的設(shè)計(jì)模式檢測(cè)結(jié)果。考慮到現(xiàn)有工具對(duì)源碼支持的局限性，本文分別選擇支持Java語言與C++語言的經(jīng)典開源系統(tǒng)進(jìn)行評(píng)估實(shí)驗(yàn)。表3描述了支持Java語言開源系統(tǒng)的相關(guān)參數(shù)，涉及網(wǎng)址、文件大小、LOC（line of code）、空格數(shù)等信息。相似的支持C++語言開源系統(tǒng)的相關(guān)參數(shù)見表4。選擇待檢測(cè)開源系統(tǒng)的依據(jù)如下：（1）測(cè)試系統(tǒng)支持Java或C++語言且使用頻率較高；（2）測(cè)試系統(tǒng)常用于主流檢測(cè)工具恢復(fù)實(shí)驗(yàn)，便于比較與其他檢測(cè)工具的差異；（3）測(cè)試系統(tǒng)大小各異且存在多種設(shè)計(jì)模式，以便于檢測(cè)結(jié)果的多樣性比較；（4）先前工作已獲得不同類型設(shè)計(jì)模式基準(zhǔn)數(shù)的開源系統(tǒng)。

5 評(píng)估實(shí)驗(yàn)設(shè)計(jì)與分析

評(píng)估選用表2中的6種Java及2種C++設(shè)計(jì)模式檢測(cè)工具，并分別對(duì)表3中的5種Java開源系統(tǒng)與表4中的4種C++開源系統(tǒng)進(jìn)行實(shí)驗(yàn)。Pettersson等人[15]提出設(shè)計(jì)模式變體、實(shí)例共享、基準(zhǔn)等是影響檢測(cè)效率的重要因素。為此，本實(shí)驗(yàn)側(cè)重關(guān)注標(biāo)準(zhǔn)設(shè)計(jì)模式數(shù)、設(shè)計(jì)模式變體數(shù)、設(shè)計(jì)模式實(shí)例共享數(shù)3個(gè)指標(biāo)。3個(gè)實(shí)驗(yàn)環(huán)境CPU為IntelCorei7-6700，主頻4.0 GHz；內(nèi)存為DDR4 16 GB；操作系統(tǒng)選用Windows7。

Table 2 Features of experimental tools表2 檢測(cè)工具特征表

Table 3 Open source system parameters based on Java表3 Java語言開源系統(tǒng)參數(shù)

Table 4 Open source system parameters based on C++表4 C++語言開源系統(tǒng)參數(shù)

5.1 評(píng)估設(shè)計(jì)模式實(shí)例

設(shè)計(jì)模式實(shí)例基準(zhǔn)有助于研發(fā)人員對(duì)設(shè)計(jì)模式檢測(cè)結(jié)果進(jìn)行交叉比較，是評(píng)估設(shè)計(jì)模式檢測(cè)工具優(yōu)劣的重要指標(biāo)。為此，評(píng)估各種檢測(cè)工具的優(yōu)缺點(diǎn)需以基準(zhǔn)、檢測(cè)結(jié)果的正確性等指標(biāo)作為依據(jù)，但目前尚未有研究給出所有測(cè)試系統(tǒng)中設(shè)計(jì)模式實(shí)例的基準(zhǔn)數(shù)及實(shí)例目錄所在位置。一些較小的測(cè)試系統(tǒng)能以手工的形式進(jìn)行檢查，但對(duì)于較大的系統(tǒng)幾乎無法實(shí)現(xiàn)，為此需要將先前成果的基準(zhǔn)作為候選基準(zhǔn)，通過進(jìn)一步的實(shí)驗(yàn)來逐步完善，Pettersson等人[15]提出了這種思想，并定義為黃金標(biāo)準(zhǔn)。本文在同行學(xué)者先前研究成果基礎(chǔ)上，結(jié)合各個(gè)開源系統(tǒng)的設(shè)計(jì)模式實(shí)例基準(zhǔn)[4,13,15-16,23]，并輔助以手工的形式來完善基準(zhǔn)。表5與表6分別給出了Java與C++開源系統(tǒng)通過不同檢測(cè)工具評(píng)估的結(jié)果，加粗字體表示被檢測(cè)開源系統(tǒng)中設(shè)計(jì)模式實(shí)例的基準(zhǔn)數(shù)。

GOF[1]將設(shè)計(jì)模式分為結(jié)構(gòu)型、行為型、創(chuàng)建型3類。表 5 中工具 DPD[28]、DeMIMA[22]、FT[18]檢測(cè)開源系統(tǒng)QuickUML2001中結(jié)構(gòu)型模式Adapter的結(jié)果依次為11、0、8，通過與Adapter的基準(zhǔn)數(shù)10比較可知，不同工具檢測(cè)結(jié)果存在較大差異。而對(duì)于開源系統(tǒng)ApacheAnt 1.6.2的行為型模式Command，工具DPD[28]、PINOT[27]、MARPLE[26]檢測(cè)結(jié)果都為0，相對(duì)Command的基準(zhǔn)10而言，這不是偶然的現(xiàn)象，因?yàn)檫@3種工具不具備動(dòng)態(tài)分析機(jī)制。此外，對(duì)于開源系統(tǒng)ApacheAnt 1.6.2的創(chuàng)建型模式Prototype，工具DPD[28]、PINOT[27]、MARPLE[26]檢測(cè)結(jié)果皆為0，由于創(chuàng)建型模式識(shí)別需涉及時(shí)序問題，也需涉及動(dòng)態(tài)機(jī)制，故檢測(cè)效果也不理想。此外，DPIDT[16]工具檢測(cè)JHotDraw5.1系統(tǒng)的Adapter等模式時(shí)，其檢測(cè)結(jié)果遠(yuǎn)大于基準(zhǔn)數(shù)，如Adapter基準(zhǔn)為19，其檢測(cè)結(jié)果為35。為此，作者以手工的形式分析后發(fā)現(xiàn)，檢測(cè)結(jié)果存在較多假陽性結(jié)果。

綜上所述，檢測(cè)工具對(duì)Adapter等結(jié)構(gòu)型設(shè)計(jì)模式的識(shí)別效果相對(duì)較好，而對(duì)行為型與創(chuàng)建型模式的識(shí)別不夠理想。究其原因發(fā)現(xiàn)，結(jié)構(gòu)型模式使用繼承等靜態(tài)機(jī)制來組合類，而靜態(tài)機(jī)制能夠在編譯時(shí)確定，故結(jié)構(gòu)型模式相對(duì)容易被識(shí)別。行為型類模式使用繼承描述算法和控制流，而行為型對(duì)象模式則描述一組對(duì)象怎樣協(xié)作完成單個(gè)對(duì)象所無法完成的任務(wù)，二者都需涉及部分動(dòng)態(tài)機(jī)制，故行為型模式識(shí)別難度高于結(jié)構(gòu)型模式[1]。創(chuàng)建型類模式將對(duì)象的部分創(chuàng)建工作延遲到子類，而創(chuàng)建型對(duì)象模式則將它延遲到另一個(gè)對(duì)象中，這導(dǎo)致除靜態(tài)與動(dòng)態(tài)機(jī)制外，創(chuàng)建型模式還要涉及時(shí)序與語義機(jī)制，故識(shí)別難度較大[1]。

Table 5 Design pattern detection results of open source system based on Java表5 Java開源系統(tǒng)設(shè)計(jì)模式檢測(cè)結(jié)果

Table 6 Design pattern detection results of open source system based on C++表6 C++開源系統(tǒng)設(shè)計(jì)模式檢測(cè)結(jié)果

除檢測(cè)Java語言開源系統(tǒng)，本文還針對(duì)Galb++(2.4)等C++語言開源系統(tǒng)進(jìn)行檢測(cè)。由表6可知，在檢測(cè)Galb++(2.4)系統(tǒng)的Adapter模式時(shí)，不同工具存在較明顯的差異，DPRE[36]與DPR[37]檢測(cè)結(jié)果數(shù)分別為6與4，相似的檢測(cè)Socket(1.10)系統(tǒng)的Bridge模式時(shí)，DPRE[36]與DPR[37]檢測(cè)結(jié)果數(shù)分別為0與1。究其原因發(fā)現(xiàn)，不同檢測(cè)方法對(duì)檢測(cè)結(jié)果的影響起著重要作用。此外，不能單純看到工具對(duì)某種設(shè)計(jì)模式檢測(cè)結(jié)果的正確率為100%則認(rèn)定該檢測(cè)工具很優(yōu)秀，如Socket(1.10)系統(tǒng)的Adapter模式，這些檢測(cè)結(jié)果由于基準(zhǔn)數(shù)較小，即使是100%的精確率也不具有代表性。事實(shí)上，當(dāng)將其應(yīng)用到遺產(chǎn)系統(tǒng)中仍可能出現(xiàn)較大的偏差。Libg++(2.7.2)系統(tǒng)的Bridge模式中DPRE[36]與DPR[37]檢測(cè)結(jié)果數(shù)分別為1與3，DPR[37]取得結(jié)果多于基準(zhǔn)數(shù)。為此，作者以人工的形式檢查結(jié)果，發(fā)現(xiàn)存在2個(gè)假陽性結(jié)果。

此外，應(yīng)關(guān)注到現(xiàn)有設(shè)計(jì)模式檢測(cè)工具對(duì)于C++開源系統(tǒng)的檢測(cè)存在局限性：（1）結(jié)合表1可見，現(xiàn)有設(shè)計(jì)模式檢測(cè)工具對(duì)C++語言的支持程度不及Java語言；（2）待檢測(cè)C++開源系統(tǒng)僅存在Adapter等5種設(shè)計(jì)模式，且數(shù)目較小，缺乏多樣性；（3）待檢測(cè)C++開源系統(tǒng)皆屬于中小型系統(tǒng)，檢測(cè)結(jié)果不具有代表性。

5.2 評(píng)估設(shè)計(jì)模式變體

設(shè)計(jì)模式變體易導(dǎo)致不精確的檢測(cè)結(jié)果，而傳統(tǒng)設(shè)計(jì)模式檢測(cè)工具較難識(shí)別設(shè)計(jì)模式變體，為此，設(shè)計(jì)模式變體檢測(cè)結(jié)果的精確率成為當(dāng)前領(lǐng)域研究的熱點(diǎn)，也是衡量檢測(cè)工具是否優(yōu)異的重要指標(biāo)。

Gamma等人[1]提出了23種經(jīng)典的設(shè)計(jì)模式，近20年來，研發(fā)人員應(yīng)用這些設(shè)計(jì)模式到MIS系統(tǒng)中，并取得了較好的效果。但為了滿足客戶的個(gè)性化需求，現(xiàn)有的23種設(shè)計(jì)模式已經(jīng)力不從心，因此，近些年來，研發(fā)人員在不改變?cè)O(shè)計(jì)意圖的前提下對(duì)23種經(jīng)典的設(shè)計(jì)模式進(jìn)行了修改。Pettersson等人[15]對(duì)此給出了新的定義，即設(shè)計(jì)模式“變體”。變體的識(shí)別效果影響設(shè)計(jì)模式檢測(cè)的精確率，也是目前領(lǐng)域內(nèi)研究的難點(diǎn)。目前國(guó)內(nèi)外對(duì)設(shè)計(jì)模式變體的研究尚處于理論階段，較少有可借鑒的文獻(xiàn)，為此，本文以人工的形式驗(yàn)證QuickUML2001等4個(gè)Java開源系統(tǒng)中Adapter等11個(gè)模式的變體基準(zhǔn)。表7中加粗字體表示每個(gè)待檢測(cè)系統(tǒng)的變體基準(zhǔn)（variants benchmark，VBK）。

設(shè)計(jì)模式變體由標(biāo)準(zhǔn)GOF設(shè)計(jì)模式演化形成，其參與者角色或角色間聯(lián)系發(fā)生了一定形式的改變，但設(shè)計(jì)意圖未發(fā)生改變，故難以檢測(cè)設(shè)計(jì)模式變體。由表7可見，檢測(cè)工具對(duì)開源系統(tǒng)設(shè)計(jì)模式變體的識(shí)別效果不夠理想，如QuickUML2001中Command模式基準(zhǔn)為2，而工具DPD[28]、PINOT[27]、FT[18]識(shí)別的結(jié)果依次為0、0、1。表8描述了QuickUML2001中這2個(gè)Command模式目錄位置，如第1個(gè)變體中扮演Command模式中Command角色的目錄位置位于diagram.SelectionModel.java，而 扮 演 ConcreteCommand角色的目錄位置位于diagram.AbstractSelection-Model.java，F(xiàn)T[18]能識(shí)別表8中的變體1。相似的是目前較少有工具支持C++語言開源系統(tǒng)，故在同行學(xué)者先前研究基礎(chǔ)上[33,36-37]，再以手工的形式驗(yàn)證后給出表9中開源系統(tǒng)的變體基準(zhǔn)。由表9中Galb++(2.4)系統(tǒng)的Adapter模式可知，DPRE[36]與DPR[37]變體檢測(cè)結(jié)果分別為6與4，與其基準(zhǔn)數(shù)9存在較大的偏差。相似的DPRE[36]與DPR[37]工具檢測(cè)Libg++(2.7.2)系統(tǒng)的Decorator模式結(jié)果為12與12，與其基準(zhǔn)21也存在較大偏差。究其原因發(fā)現(xiàn)Adapter與Decorator模式屬于GOF[2]設(shè)計(jì)模式分類中的結(jié)構(gòu)型模式，這類模式在不改變?cè)O(shè)計(jì)意圖的前提下易于修改，并能解決客戶的個(gè)性化需求。但目前眾多設(shè)計(jì)模式檢測(cè)工具開發(fā)者尚未關(guān)注到這個(gè)問題，以至于變體識(shí)別效果不理想。

5.3 評(píng)估設(shè)計(jì)模式實(shí)例共享

設(shè)計(jì)模式實(shí)例共享因?yàn)樯婕皡⑴c者角色扮演多個(gè)設(shè)計(jì)模式角色的問題且類層次較復(fù)雜，故傳統(tǒng)設(shè)計(jì)模式檢測(cè)工具也較難識(shí)別設(shè)計(jì)模式共享實(shí)例。為此，設(shè)計(jì)模式共享實(shí)例檢測(cè)結(jié)果的精確率也成為當(dāng)前領(lǐng)域研究的難點(diǎn)，也是衡量檢測(cè)工具是否優(yōu)異的重要指標(biāo)。本文分析現(xiàn)有工具檢測(cè)結(jié)果發(fā)現(xiàn)，存在設(shè)計(jì)模式參與者同時(shí)扮演2個(gè)或多個(gè)設(shè)計(jì)模式角色的情況，即設(shè)計(jì)模式參與者角色共享設(shè)計(jì)模式，這類問題易導(dǎo)致結(jié)果誤差。本文在同行學(xué)者研究基礎(chǔ)上[4,15-16,23]，以手工形式進(jìn)行驗(yàn)證，確定實(shí)例共享基準(zhǔn)（sharing instance benchmark，SBK）。

Table 7 Design pattern variants detection results of open source system based on Java表7 Java開源系統(tǒng)變體檢測(cè)結(jié)果

Table 8 Variant directory of command pattern表8command變體目錄

分析表10發(fā)現(xiàn)，4種工具檢測(cè)的結(jié)果與各自SBK基準(zhǔn)數(shù)之間普遍存在差異，如JHotDraw5.1中Adapter與Command模式的共享實(shí)例基準(zhǔn)是19與8，但通過工具DPD[28]發(fā)現(xiàn)共享實(shí)例的Adapter與Command模式分別為4與2。此外，深入研究后發(fā)現(xiàn)被檢測(cè)出的4個(gè)Adapter模式中的2個(gè)與全部2個(gè)Command模式存在參與者角色共享設(shè)計(jì)模式的情況，詳見表11。如CH.ifa.draw.Standard.CreationTool角色同時(shí)扮演了Adapter模式中的adapter角色及Command模式中的command角色，相似的CH.ifa.draw.Standard.Handle-Tracke角色也同時(shí)扮演了Adapter模式中的adaptee角色及Command模式中的concretecommand角色。研究發(fā)現(xiàn)State與Strategy模式等也存在較多參與者角色共享設(shè)計(jì)模式的問題。為此，本文深入研究后發(fā)現(xiàn)，共享實(shí)例的設(shè)計(jì)模式普遍存在結(jié)構(gòu)相似的現(xiàn)象，后續(xù)工作中考慮將這些結(jié)構(gòu)相似的設(shè)計(jì)模式作為整體進(jìn)行識(shí)別。

此外，本文也對(duì)C++開源系統(tǒng)的設(shè)計(jì)模式實(shí)例共享問題進(jìn)行了評(píng)估實(shí)驗(yàn)。由表12可見，設(shè)計(jì)模式參與者角色共享不同設(shè)計(jì)模式實(shí)例的情況也不容樂觀，如Galb++(2.4)系統(tǒng)中Adapter的基準(zhǔn)為5，工具DPRE[36]與DPR[37]的檢測(cè)結(jié)果為2與1，成功率分別為40%與20%。而工具DPRE[36]與DPR[37]對(duì)于Libg++(2.7.2)系統(tǒng)中Decorator模式的識(shí)別結(jié)果分別6與4，精確率分別為60%與40%，通過手工驗(yàn)證發(fā)現(xiàn)了假陽性結(jié)果。其余設(shè)計(jì)模式檢測(cè)結(jié)果數(shù)量的基數(shù)過小，存在偶然性，故其結(jié)果不具有代表性。

Table 9 Design pattern variants detection results of open source system based on C++表9 C++開源系統(tǒng)變體檢測(cè)結(jié)果

Table 10 Shared design pattern instances in Java open source system表10 Java開源系統(tǒng)共享設(shè)計(jì)模式實(shí)例情況表

Table 11 Analysis of shared instances forAdapter/Command表11Adapter與Command共享實(shí)例分析

Table 12 Shared design pattern instances in C++open source system表12 C++開源系統(tǒng)共享設(shè)計(jì)模式實(shí)例情況表

6 有效性分析

近些年來研究人員圍繞設(shè)計(jì)模式檢測(cè)工具開展了大量的工作，并取得了一定的成果，但同樣存在較多問題。為此，本文將設(shè)計(jì)模式檢測(cè)工具缺點(diǎn)與影響恢復(fù)結(jié)果精確率的注意事項(xiàng)總結(jié)為以下方面：（1）現(xiàn)有的大部分工具在檢測(cè)設(shè)計(jì)模式時(shí)選用不同系統(tǒng)作為實(shí)驗(yàn)對(duì)象，故缺乏用于比較的基準(zhǔn)系統(tǒng)，不利于檢測(cè)結(jié)果的比較；（2）檢測(cè)工具僅適合特定的程序語言，如Java、C++等，不具備通用性；（3）大部分工具僅檢測(cè)了部分結(jié)構(gòu)型設(shè)計(jì)模式，而回避了檢測(cè)難度較大的行為型及創(chuàng)建型模式；（4）大部分研究人員通過工具進(jìn)行設(shè)計(jì)模式檢測(cè)時(shí)僅提供最終的精確率與召回率結(jié)果，沒有給出檢測(cè)結(jié)果所在具體位置及扮演何種角色等重要信息，不便于其他學(xué)者驗(yàn)證；（5）大部分工具對(duì)設(shè)計(jì)模式變體缺乏關(guān)注；（6）檢測(cè)結(jié)果存在大量的假陽性及假陰性結(jié)果；（7）設(shè)計(jì)模式參與者角色共享模式實(shí)例情況難以檢測(cè)；（8）缺乏統(tǒng)一的輸入輸出形式，兼容性差，不利于結(jié)果的評(píng)估比較；（9）現(xiàn)有檢測(cè)工具較少能從語義的角度對(duì)具有相似結(jié)構(gòu)的設(shè)計(jì)模式進(jìn)行區(qū)分；（10）現(xiàn)有工具大多固定檢測(cè)幾個(gè)例子，無法與其他方法的檢測(cè)結(jié)果進(jìn)行交叉驗(yàn)證；（11）部分檢測(cè)工具需要通過第三方工具將源碼轉(zhuǎn)換成中間表示形式，而后再使用插件技術(shù)來實(shí)現(xiàn)設(shè)計(jì)模式的恢復(fù)，這將導(dǎo)致檢測(cè)結(jié)果的精確率依賴于第三方工具的抽取能力。

7 建議

綜上所述，給出以下建議：（1）檢測(cè)工具應(yīng)能夠通過標(biāo)準(zhǔn)的中間表示形式與其他檢測(cè)工具兼容；（2）檢測(cè)工具應(yīng)具有可擴(kuò)展性與靈活性；（3）檢測(cè)工具應(yīng)該能夠支持多種編程語言；（4）檢測(cè)工具不能僅僅局限于開源系統(tǒng)的檢測(cè)，遺產(chǎn)系統(tǒng)也需關(guān)注；（5）檢測(cè)工具應(yīng)該關(guān)注變體[38]及附加關(guān)系[39]導(dǎo)致的假陽性與假陰性結(jié)果；（6）對(duì)特征信息不易挖掘的情形，可依據(jù)專家經(jīng)驗(yàn)進(jìn)行調(diào)查，通過設(shè)計(jì)模式檢測(cè)工具以半自動(dòng)的形式識(shí)別[40]；（7）可考慮結(jié)合圖論原理[41]與語義解決領(lǐng)域內(nèi)動(dòng)態(tài)分析、時(shí)序等難以檢測(cè)的問題。

8 結(jié)束語

本文提出了一種評(píng)估設(shè)計(jì)模式檢測(cè)工具的策略，篩選了主流檢測(cè)工具及實(shí)驗(yàn)測(cè)試系統(tǒng)，完善了基準(zhǔn)數(shù)據(jù)，側(cè)重關(guān)注設(shè)計(jì)模式變體及實(shí)例共享等指標(biāo)，并通過多種主流工具與開源系統(tǒng)進(jìn)行評(píng)估實(shí)驗(yàn)，總結(jié)了影響檢測(cè)結(jié)果精確率的有效性威脅，給出了合理性建議，有助于避免同類型設(shè)計(jì)模式檢測(cè)工具的重復(fù)研發(fā)，節(jié)約成本。未來工作將致力于重要指標(biāo)的研究及檢測(cè)工具比較基準(zhǔn)的完善，改進(jìn)變體與模式實(shí)例共享檢測(cè)的精確率，完善基準(zhǔn)庫的建設(shè)，并從多角度分類探討更多設(shè)計(jì)模式檢測(cè)工具的優(yōu)缺點(diǎn)，為后續(xù)工具開發(fā)奠定堅(jiān)實(shí)的基礎(chǔ)。

[1]Gamma E,Helm R,Johnson R,et al.Design pattern:elements of reusable object-oriented software[M].Boston:Addison-Wesley Longman Publishing Co,Inc,1995:1-22.

[2]Xiao Zhuoyu,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.

[3]Scanniello G,Gravino C,Risi M,et al.Documenting designpattern instances:a family of experiments on source-code comprehensibility[J].ACM Transactions on Software Engineering and Methodology,2015,24(3):1-35.

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

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

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

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

[9]Xu Hanbin,Zhang Xuelin,Zhen Xiaomei,et al.Method of software design patterns identification based on correlation and feature constraints[J].Computer Science,2014,41(11):50-55.

[10]Gu Hui,Zhang Weixing,Jin Peng,et al.Method of software design patterns identification based on correlation and feature constraints[J].Computer Science,2015,42(2):173-176.

[11]Xiao Zhuoyu,He Pei,Yu Bo,et al.Design patterns detection based on FCA and CBR[J].Journal of Shandong University:Engineering Science,2016,46(2):22-28.

[12]Xiao Zhuoyu,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.

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

[15]Pettersson 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.

[16]Yu Dongjin,Zhang Yanyan,Chen Zhenli.A comprehensive approach to the recovery of design pattern instances based on sub-patterns and method signatures[J].Journal of Systems and Software,2015,103(C):1-16.

[17]Binun A,Kniesel G.DPJF-design pattern detection with high accuracy[C]//Proceedings of the 16th European Conference on Software Maintenance and Reengineering,Szeged,Mar 27-30,2012.Washington:IEEE Computer Society,2012:245-254.

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

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

[20]Alnusair A,Zhao Tian.Towards a model-driven approach for reverse engineering design patterns[C]//Proceedings of the 2nd International Workshop on Transforming and Weaving Ontologies in Model Driven Engineering，Denver,Oct 4-9,2009.Piscataway:IEEE,2009:531-545.

[21]Stencel K,Wegrzynowicz P.Detection of diverse design pattern variants[C]//Proceedings of the 15th Asia-Pacific Software Engineering Conference,Beijing,Dec 3-5,2008.Washington:IEEE Computer Society,2008:25-32.

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

[23]Sartipi K,Hu Lei.Behavior-driven design pattern recovery[C]//Proceedings of the 12th International Conference on Software Engineering and Applications,Orlando,Nov 16-18,2008:179-185.

[24]Arcelli F,Perin F,Raibulet C,et al.Behavioral design pattern detection through dynamic analysis,TUD-SERG-2008-036[R].2008:11-16.

[25]Dong Jing,Lad D S,Zhao Yajing.DP-Miner:design pattern discovery using matrix[C]//Proceedings of the 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems,Tucson,Mar 6-29,2007.Washington:IEEE Computer Society,2007:371-380.

[26]Arcelli F,Christina L.Enhancing software evolution through design pattern detection[C]//Proceedings of the 3rd International IEEE Workshop on Software Evolvability,Paris,Oct 1,2007.Piscataway:IEEE,2007:7-14.

[27]Shi N,Olsson R A.Reverse engineering of design patterns from Java source code[C]//Proceedings of the 21st IEEE/ACM International Conference on Automated Software Engineering,Tokyo,Sep 18-22,2006.Washington:IEEE Computer Society,2006:123-134.

[28]Tsantalis N,Chatzigeorgiou A,Stephanides G,et al.Design pattern detection using similarity scoring[J].IEEE Transactions on Software Engineering,2006,32(11):896-909.

[29]Ferenc R,Beszédes A,Fül?p L,et al.Design pattern mining enhanced by machine learning[C]//Proceedings of the 21st IEEE International Conference on Software Maintenance,Budapest,Sep 25-30,2005.Washington:IEEE Computer Society,2005:295-304.

[30]Philippow I,Streitferdt D,Riebisch M,et al.An approach for reverse engineering of design patterns[J].Software&Systems Modeling,2005,4(1):55-70.

[31]Wang Wei,Tzerpos V.Design pattern detection in Eiffel systems[C]//Proceedings of the 12th Working Conference on Reverse Engineering,Pittsburgh,Nov 7-11,2005.Washington:IEEE Computer Society,2005:165-174.

[32]Kirasi? D,Basch D.Ontology-based design pattern recognition[C]//LNCS 5177:Proceedings of the 12th International Conference on Knowledge-Based Intelligent Information and Engineering Systems,Zagreb,Sep 3-5,2008.Berlin,Heidelberg:Springer,2008:384-393.

[33]Smith J M,Stotts D.SPQR:flexible automated design pattern extraction from source code[C]//Proceedings of the 18th IEEE International Conference on Automated Software Engineering,Montreal,Oct 6-10,2003.Washington:IEEE Computer Society,2003:215-224.

[34]Niere J,Sch?fer W,Wadsack J P,et al.Towards patternbased design recovery[C]//Proceedings of the 24th International Conference on Software Engineering,Orlando,May 19-25,2002.New York:ACM,2002:338-348.

[35]Kramer C,Prechelt L.Design recovery by automated search for structural design patterns in object-oriented software[C]//Proceedings of the 20th Working Conference on Reverse Engineering,Monterey,Nov 8-10,1996.Washington:IEEE Computer Society,1996:208-215.

[36]Costagliola G,De Lucia A,Deufemia V,et al.Case studies of visual language based design patterns recovery[C]//Proceedings of the 10th European Conference on Software Maintenance and Reengineering,Mar 22-24,2006.Washington:IEEE Computer Society,2006:165-174.

[37]Antoniol G,Casazza G,Di Penta M,et al.Object-oriented design patterns recovery[J].Journal of Systems and Software,2001,59(2):181-196.

[38]Xiao Zhuoyu,He Pei,Yang Xinwei,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.

[39]Xiao Zhuoyu,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.

[40]Xiao Zhuoyu,He Pei,Yu Bo.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.

[41]Mayvan B B,Rasoolzadegan A.Design pattern detection based on the graph theory[J].Knowledge-Based Systems,2017,120:211-225.

附中文參考文獻(xiàn)：

[2]肖卓宇,何锫,余波,等.一種形式化上下無關(guān)文法關(guān)系驅(qū)動(dòng)的設(shè)計(jì)模式檢測(cè)方法[J].工程科學(xué)學(xué)報(bào),2016,38(10):1499-1508.

[9]許涵斌,張學(xué)林,鄭曉梅,等.一種基于結(jié)構(gòu)查詢的UML設(shè)計(jì)模式識(shí)別方法[J].計(jì)算機(jī)科學(xué),2014,41(11):50-55.

[10]古輝,張煒星,金鵬,等.基于關(guān)聯(lián)度和特征約束的軟件設(shè)計(jì)模式識(shí)別方法[J].計(jì)算機(jī)科學(xué),2015,42(2):173-176.

[11]肖卓宇,何锫,余波,等.基于FCA與CBR的設(shè)計(jì)模式檢測(cè)[J].山東大學(xué)學(xué)報(bào):工學(xué)版,2016,46(2):22-28.

[12]肖卓宇,黎妍,何锫,等.基于矩陣積分評(píng)估的設(shè)計(jì)模式檢測(cè)研究[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(7):1428-1433.

[38]肖卓宇,何锫,楊鑫維,等.基于文法產(chǎn)生式優(yōu)化的設(shè)計(jì)模式識(shí)別方法[J].電子科技大學(xué)學(xué)報(bào),2017,46(3):569-576.

[39]肖卓宇,何锫,黎妍.基于設(shè)計(jì)模式角色的附加關(guān)系檢測(cè)研究[J].計(jì)算機(jī)應(yīng)用研究,2015,32(7):2042-2045.

[40]肖卓宇,何锫,余波.一種多階段交互式線索驅(qū)動(dòng)的設(shè)計(jì)模式識(shí)別方法[J].北京航空航天大學(xué)學(xué)報(bào),2017,43(9):1746-1756.