基于堆疊泛化的設(shè)計(jì)模式檢測(cè)方法*

馮 鐵 , 靳 樂 , 張家晨 , 王洪媛

1(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,吉林 長(zhǎng)春 130012)2(吉林大學(xué) 軟件學(xué)院,吉林 長(zhǎng)春 130012)3(符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué)),吉林 長(zhǎng)春 130012)

設(shè)計(jì)模式通過標(biāo)識(shí)對(duì)象、對(duì)象間的合作及責(zé)任分配來揭示設(shè)計(jì)機(jī)理,表明基于某種經(jīng)驗(yàn)的、在特定的上下文中解決一個(gè)普遍設(shè)計(jì)問題的可復(fù)用體系結(jié)構(gòu)[1,2].設(shè)計(jì)模式已經(jīng)被廣泛地應(yīng)用在各種軟件和工具庫(kù)的設(shè)計(jì)與實(shí)現(xiàn)中.設(shè)計(jì)模式檢測(cè)旨在從現(xiàn)有的軟件設(shè)計(jì)文檔或源代碼當(dāng)中識(shí)別所使用的設(shè)計(jì)模式實(shí)例,它不僅對(duì)于幫助維護(hù)人員理解軟件系統(tǒng)的設(shè)計(jì)動(dòng)機(jī)和原理、恢復(fù)軟件設(shè)計(jì)和改善軟件的可維護(hù)性具有重要意義,而且有助于軟件體系結(jié)構(gòu)的恢復(fù)和發(fā)現(xiàn),同時(shí)也是評(píng)估軟件質(zhì)量的一個(gè)重要依據(jù).

由于設(shè)計(jì)模式的應(yīng)用大多是基于意圖的,并未嚴(yán)格限制模式的具體實(shí)現(xiàn),加之不同開發(fā)者對(duì)于設(shè)計(jì)模式的理解不一,這使得模式的實(shí)現(xiàn)千變?nèi)f化.目前,設(shè)計(jì)模式檢測(cè)主要存在以下問題:(1) 變體的檢測(cè)效果不理想;(2) 結(jié)構(gòu)相同意圖不同的模式難以區(qū)分;(3) 行為型設(shè)計(jì)模式的檢測(cè)復(fù)雜;(4) 組合爆炸問題依然突出.正是因?yàn)檫@些問題的存在,設(shè)計(jì)模式檢測(cè)仍然是軟件工程領(lǐng)域的一個(gè)重要的研究?jī)?nèi)容.

機(jī)器學(xué)習(xí)是人工智能領(lǐng)域的重要分支,它是使用經(jīng)驗(yàn)來提高計(jì)算性能或做出準(zhǔn)確預(yù)測(cè)的計(jì)算方法[3].機(jī)器學(xué)習(xí)技術(shù)適用于設(shè)計(jì)模式檢測(cè)的原因如下:首先,設(shè)計(jì)模式檢測(cè)活動(dòng)本身就是對(duì)眾多候選模式實(shí)例進(jìn)行預(yù)測(cè)的過程,這符合機(jī)器學(xué)習(xí)的應(yīng)用背景;其次,設(shè)計(jì)模式變體的檢測(cè)與機(jī)器學(xué)習(xí)無需硬編碼的特點(diǎn)相適應(yīng);最后,機(jī)器學(xué)習(xí)對(duì)語義信息的描述,有助于區(qū)分結(jié)構(gòu)相同而意圖不同的模式.

對(duì)于行為型設(shè)計(jì)模式的檢測(cè),目前主要的方法是借助于動(dòng)態(tài)分析[4-6],但是動(dòng)態(tài)分析一般要求目標(biāo)項(xiàng)目完整可運(yùn)行,這在實(shí)際中有時(shí)候是不可行的;另外,監(jiān)控候選模式實(shí)例的運(yùn)行需要生成相應(yīng)的測(cè)試用例,如果手工生成,必然費(fèi)時(shí)費(fèi)力,如果自動(dòng)生成,又難以做到有效的路徑覆蓋.如果能夠充分利用靜態(tài)代碼分析技術(shù),將對(duì)模式的檢測(cè)研究深入到方法內(nèi)部,并嘗試用機(jī)器學(xué)習(xí)的方式去刻畫模式的行為特征,就可以較大程度地降低行為型設(shè)計(jì)模式檢測(cè)的難度.

本文提出一種新的設(shè)計(jì)模式檢測(cè)方法,結(jié)合面向?qū)ο蠖攘亢湍Ｊ轿⒔Y(jié)構(gòu)(以下簡(jiǎn)稱度量和微結(jié)構(gòu))并使用典型的機(jī)器學(xué)習(xí)算法來實(shí)現(xiàn)設(shè)計(jì)模式的檢測(cè).針對(duì)每種設(shè)計(jì)模式,本文分別用度量和微結(jié)構(gòu)(micro-structure,簡(jiǎn)稱MS)訓(xùn)練出一個(gè)分類器,然后采用模型堆疊的方式訓(xùn)練出最終的分類器,從而實(shí)現(xiàn)對(duì)該設(shè)計(jì)模式的檢測(cè).

本文的主要貢獻(xiàn)如下:(1) 提出了用多視圖(設(shè)計(jì)模式度量視圖和設(shè)計(jì)模式微結(jié)構(gòu)視圖)堆疊泛化的方法來解決設(shè)計(jì)模式檢測(cè)問題;(2) 定義了模式必備微結(jié)構(gòu)來縮減搜索空間,從而避免組合爆炸問題;(3) 對(duì)于檢測(cè)出的模式實(shí)例,除給出角色映射外,還能給出具體的方法映射.最終實(shí)驗(yàn)表明,本文提出的方法在變體的識(shí)別、行為型設(shè)計(jì)模式的檢測(cè)以及組合爆炸問題的解決等方面均有明顯提升.

本文第1 節(jié)介紹本文相關(guān)工作.第2 節(jié)定義度量和微結(jié)構(gòu)以及相關(guān)的基本概念與原理.第3 節(jié)詳細(xì)介紹基于堆疊泛化的設(shè)計(jì)模式檢測(cè)方法.第4 節(jié)在5 種設(shè)計(jì)模式上進(jìn)行實(shí)驗(yàn),通過實(shí)驗(yàn)數(shù)據(jù)的對(duì)比分析,驗(yàn)證所提方法的有效性.第5 節(jié)對(duì)本文的工作進(jìn)行總結(jié)并對(duì)未來工作展望.

1 相關(guān)工作

自從GoF 等人提出軟件設(shè)計(jì)模式概念以來[1],許多學(xué)者對(duì)設(shè)計(jì)模式的自動(dòng)化檢測(cè)進(jìn)行了研究,提出了很多種設(shè)計(jì)模式檢測(cè)方法.這些方法在所用技術(shù)、分析類型、所面向的源代碼或模式的中間表示、是否精確匹配、是否完全自動(dòng)化、是否面向特定模式、實(shí)驗(yàn)的信息項(xiàng)和指標(biāo)等方面各不相同.接下來,本文從所用技術(shù)方面對(duì)一些具有代表性的方法進(jìn)行歸納和介紹.

有些設(shè)計(jì)模式檢測(cè)方法是基于相似度計(jì)算的[7,8].例如,Tsantalis 等人利用圖的相似性算法實(shí)現(xiàn)了設(shè)計(jì)模式的檢測(cè)[7],該方法不僅能夠識(shí)別模式變體,而且還能夠有效地解決模式檢測(cè)過程中的組合爆炸問題(利用了設(shè)計(jì)模式大都包含繼承層次這一事實(shí)).簡(jiǎn)單來說,該方法將設(shè)計(jì)模式角色之間的各種關(guān)系用鄰接矩陣來表示,然后從源碼中提取所有的繼承層次,接著在模式查找階段,用繼承層次中的類去映射設(shè)計(jì)模式的各個(gè)角色,然后提取出這些角色類之間的各種關(guān)系矩陣,最后利用矩陣之間的相似性算法得到一個(gè)最終的相似度,如果相似度超過了事先選擇的閾值,那么就找到了一個(gè)設(shè)計(jì)模式實(shí)例.該方法的缺點(diǎn)是對(duì)某些行為型設(shè)計(jì)模式的檢測(cè)效果不好,同時(shí)空間復(fù)雜度也很高.

有些設(shè)計(jì)模式檢測(cè)方法是基于圖理論的[9-11].例如,Yu 等人從設(shè)計(jì)模式的子模式出發(fā),將設(shè)計(jì)模式檢測(cè)問題映射為圖論中的圖同構(gòu)問題[9].他們定義了十幾種能夠表示設(shè)計(jì)模式結(jié)構(gòu)特征的子模式.對(duì)于一個(gè)待檢測(cè)系統(tǒng),他們首先將系統(tǒng)源碼和子模式用類關(guān)系有向圖來表示,然后從系統(tǒng)源碼的類關(guān)系有向圖中找到和子模式的類關(guān)系有向圖同構(gòu)的子圖,通過參照設(shè)計(jì)模式結(jié)構(gòu)特征模型來組合這些子圖,從而得到候選模式實(shí)例.為了追蹤設(shè)計(jì)模式行為方面的特征,他們使用方法簽名模板來過濾不符合條件的候選模式實(shí)例.他們方法的缺點(diǎn)是沒有對(duì)子模式進(jìn)行過濾,從而子模式挖掘和子模式組合的時(shí)間復(fù)雜度很高.另外,他們僅僅使用方法簽名來追蹤設(shè)計(jì)模式的行為特征,這顯然是不夠的.

還有一些設(shè)計(jì)模式檢測(cè)方法是基于本體的[12-14].例如,Dietrich 等人使用Web 本體語言(OWL)來形式化地定義設(shè)計(jì)模式和其相關(guān)概念[12].他們開發(fā)了一款原型工具,該工具以設(shè)計(jì)模式的形式化描述和待檢測(cè)的Java 項(xiàng)目為輸入,輸出待檢測(cè)項(xiàng)目中該設(shè)計(jì)模式的實(shí)例.由于該方法采用的是準(zhǔn)確匹配,因此很難對(duì)設(shè)計(jì)模式的變體進(jìn)行檢測(cè).最后,他們提出可以去掉或弱化某些約束,從而實(shí)現(xiàn)模糊匹配,但是他們并未針對(duì)具體模式說明哪些約束可以被去掉或弱化.

最后,基于機(jī)器學(xué)習(xí)的設(shè)計(jì)模式檢測(cè)方法也有很多[15-17],其中具有代表性的檢測(cè)方法是下面3 個(gè):

Alhusain 等人首次嘗試了只使用機(jī)器學(xué)習(xí)的方法來實(shí)現(xiàn)設(shè)計(jì)模式的檢測(cè)[15].他們的訓(xùn)練數(shù)據(jù)集是由MARPLE[18],SSA[7],WOP[12],FINDER[19]等4 種模式檢測(cè)工具投票產(chǎn)生的.他們的模式檢測(cè)方案包括兩個(gè)階段:在第1 階段,他們通過特征選擇算法為每個(gè)模式角色選擇一個(gè)特征子集,然后根據(jù)該特征子集和相應(yīng)的分類模型來確定每個(gè)模式角色的候選類,從而減小了模式的搜索空間;在第2 階段,每種設(shè)計(jì)模式都有一個(gè)單獨(dú)的分類器,該分類器使用表示角色類之間關(guān)系的特征作為輸入.最后他們?cè)贘HotDraw 項(xiàng)目上進(jìn)行了實(shí)驗(yàn),但是結(jié)果并不是很理想.

Zanoni 等人也將機(jī)器學(xué)習(xí)技術(shù)應(yīng)用到了設(shè)計(jì)模式檢測(cè)當(dāng)中,他們開發(fā)了一個(gè)名叫MARPLE 的Eclipse 插件,該插件可以從Java 源代碼當(dāng)中抽取設(shè)計(jì)模式[16].MARPLE 插件包括3 個(gè)主要模塊:(1) 信息檢測(cè)引擎,負(fù)責(zé)構(gòu)建系統(tǒng)模型;(2) Joiner,負(fù)責(zé)從系統(tǒng)模型里面抽取設(shè)計(jì)模式候選實(shí)例;(3) Classifier,負(fù)責(zé)分類Joiner 的結(jié)果,把候選實(shí)例分類為正確的模式實(shí)例和錯(cuò)誤的模式實(shí)例.他們?yōu)槊糠N設(shè)計(jì)模式都找到了最佳的聚類算法和分類算法.他們方法的缺點(diǎn)是訓(xùn)練數(shù)據(jù)集需要人工產(chǎn)生,而人工產(chǎn)生數(shù)據(jù)集會(huì)受主觀因素影響;Joiner 的召回率并不是100%;有效性和訓(xùn)練集大小的關(guān)系有待進(jìn)一步驗(yàn)證;并未考慮系統(tǒng)庫(kù)和第三方庫(kù)中的代碼.

Chihada 等人從面向?qū)ο蠖攘康慕嵌冉o出了設(shè)計(jì)模式的檢測(cè)方法[17].他們的檢測(cè)方法分為兩個(gè)階段:設(shè)計(jì)模式組織階段和設(shè)計(jì)模式檢測(cè)階段.在設(shè)計(jì)模式組織階段,他們從專家那里獲取設(shè)計(jì)模式實(shí)例,然后通過實(shí)例計(jì)算特征向量,最終生成訓(xùn)練數(shù)據(jù)集,并學(xué)習(xí)出分類器.在設(shè)計(jì)模式檢測(cè)階段,它們首先補(bǔ)充源碼圖(由類圖轉(zhuǎn)化而來),也即讓子類繼承父類的各種關(guān)系,然后從源碼圖中枚舉出候選實(shí)例,并從中過濾掉不包含抽象類或接口類的實(shí)例,然后用第1 階段的分類器進(jìn)行分類,從而判斷候選實(shí)例是不是真正的模式實(shí)例.該方法的缺點(diǎn)是只考慮了設(shè)計(jì)模式的度量信息.

總體來講,上述工作在一定程度上解決了設(shè)計(jì)模式檢測(cè)問題,但或多或少存在前面提到的4 個(gè)問題.因此本文從這些問題出發(fā),結(jié)合度量和微結(jié)構(gòu),提出了一種新的機(jī)器學(xué)習(xí)檢測(cè)方法.該方法不僅能夠提高變體的檢測(cè)效果,而且對(duì)組合爆炸問題的解決也有很大貢獻(xiàn).同時(shí),該方法嘗試從微結(jié)構(gòu)的角度去刻畫模式的行為特征,對(duì)于行為型設(shè)計(jì)模式的檢測(cè)效果也有明顯提升.

2 面向?qū)ο蠖攘颗c微結(jié)構(gòu)

本節(jié)給出基于堆疊泛化的設(shè)計(jì)模式檢測(cè)方法相關(guān)的兩個(gè)概念(面向?qū)ο蠖攘亢臀⒔Y(jié)構(gòu))的定義及表示方式,并列出了本文所使用的度量列表和微結(jié)構(gòu)列表,著重定義了5 種方法類微結(jié)構(gòu)以及相應(yīng)的檢測(cè)方法.

2.1 面向?qū)ο蠖攘?/h3>

通過有效的特征選擇算法為每種設(shè)計(jì)模式找到合適的面向?qū)ο蠖攘刻卣骷?是基于堆疊泛化的設(shè)計(jì)模式檢測(cè)方法的重要步驟之一.面向?qū)ο蠖攘客ㄟ^定量地估算面向?qū)ο笙到y(tǒng)的設(shè)計(jì)特性,如類的繼承深度、對(duì)象間耦合、方法內(nèi)聚程度等,來預(yù)測(cè)測(cè)試的復(fù)雜性、發(fā)現(xiàn)系統(tǒng)中的錯(cuò)誤和促進(jìn)軟件的模塊化,它在一定程度上衡量了軟件的設(shè)計(jì)質(zhì)量.另一方面,設(shè)計(jì)模式是設(shè)計(jì)經(jīng)驗(yàn)的總結(jié)和提煉,設(shè)計(jì)模式實(shí)例的應(yīng)用是改善設(shè)計(jì)質(zhì)量的一個(gè)有效手段,從而針對(duì)設(shè)計(jì)模式實(shí)例的相關(guān)度量值也會(huì)呈現(xiàn)出一定的規(guī)律性.目前已經(jīng)有許多學(xué)者利用面向?qū)ο蠖攘窟M(jìn)行了設(shè)計(jì)模式的檢測(cè)研究[17,20-22],這些度量包括C&K 度量[23]、Lorenz 度量[24]、Tegarden 度量[25]、Hitz&Montazeri 度量[26]以及Briand 度量[27]等.面向?qū)ο蠖攘靠梢苑譃閷傩约?jí)別的度量、方法級(jí)別的度量、類級(jí)別的度量(以下簡(jiǎn)稱類度量)和系統(tǒng)級(jí)別的度量,用于設(shè)計(jì)模式檢測(cè)的主要是類級(jí)別的度量.

通過對(duì)GoF 的23 個(gè)設(shè)計(jì)模式的觀察和理解,表1 所示的面向?qū)ο蠖攘吭诳坍嫼蜆?biāo)識(shí)設(shè)計(jì)模式實(shí)例方面具有重要作用,因此本文選擇表1 所示的69 種類度量并通過POM Tests 工具[21]來計(jì)算相應(yīng)度量值.

Table 1 Metrics used in this paper表1 本文選取的度量列表

舉例來講,AID 表示一個(gè)類的平均繼承深度(考慮多繼承),它可以用來衡量一個(gè)類的抽象程度.一般而言,設(shè)計(jì)模式中的抽象角色類都具有較小的AID 值.CBO 表示一個(gè)類和其他類之間的耦合程度,CBOin 表示入耦合,CBOout 表示出耦合,設(shè)計(jì)模式是設(shè)計(jì)經(jīng)驗(yàn)的總結(jié)和提煉,它的角色類之間一般不會(huì)有太高的耦合程度.NOC表示一個(gè)類的直接子類個(gè)數(shù),NOC 越大,則代碼的重用越好,但是抽象性減弱.

定義 1(類度量表示(class metric representation),簡(jiǎn)稱 CMR).類度量表示由一個(gè)三元組構(gòu)成:CMR=(classA,metric,value).其中,classA表示某個(gè)具體的類,metric表示某個(gè)類度量,value表示classA的metric度量值.

2.2 微結(jié)構(gòu)

設(shè)計(jì)模式微結(jié)構(gòu)是指類或?qū)ο笾g的靜態(tài)或動(dòng)態(tài)關(guān)系,作為設(shè)計(jì)模式的組成部分,它具有更小的粒度,每個(gè)設(shè)計(jì)模式的意圖可以通過組合微結(jié)構(gòu)的意圖進(jìn)行表達(dá).定義合理的特征選擇算法為每種設(shè)計(jì)模式找到微結(jié)構(gòu)特征集,是基于堆疊泛化的設(shè)計(jì)模式檢測(cè)方法的另一個(gè)重要步驟.Fontana 等人認(rèn)為,子模式[28]、元素模式[29]、微模式[30]以及他們自己所提出的設(shè)計(jì)模式線索[31]都屬于設(shè)計(jì)模式微結(jié)構(gòu)范疇,并且也證實(shí)了微結(jié)構(gòu)和設(shè)計(jì)模式檢測(cè)之間的密切關(guān)系[32].隨后,他們基于微結(jié)構(gòu)給出了一種新的設(shè)計(jì)模式檢測(cè)方法[16].不過,雖然提出了微結(jié)構(gòu)這一術(shù)語,但卻沒有給出明確的定義.同時(shí),他們也認(rèn)為現(xiàn)有的微結(jié)構(gòu)對(duì)設(shè)計(jì)模式檢測(cè)來講并不是完備的.本文將對(duì)微結(jié)構(gòu)進(jìn)行了明確定義,并提出幾種新的微結(jié)構(gòu).

微結(jié)構(gòu)可以分為兩種:方法類微結(jié)構(gòu)和非方法類微結(jié)構(gòu).其中:方法類微結(jié)構(gòu)描述設(shè)計(jì)模式中包含的方法方面的信息,比如子模式中的Overriding Method[28]、元素模式中的Create Object[29]以及設(shè)計(jì)模式線索中的Multiple Redirections in Family[31]等;而非方法類微結(jié)構(gòu)描述設(shè)計(jì)模式的角色類以及相關(guān)屬性方面的信息,如Association,Inheritance,Private Self Instance 等.

定義2(微結(jié)構(gòu)).表示類或?qū)ο笾g的靜態(tài)或動(dòng)態(tài)的關(guān)系,每個(gè)微結(jié)構(gòu)由三元組表示:MS=(classA/instance,classB/instance,relationalMask).其中,classA/instance和classB/instance表示該微結(jié)構(gòu)的兩個(gè)參與類或?qū)ο?而relationalMask表示它們之間的關(guān)系Mask值.對(duì)于方法類微結(jié)構(gòu),它是一個(gè)對(duì)應(yīng)于classA/instance的比特向量,如果classA/instance的第n個(gè)方法和classB/instance之間體現(xiàn)了這種微結(jié)構(gòu)關(guān)系,那么relationalMask的相應(yīng)位置置1;對(duì)于非方法類微結(jié)構(gòu),若classA/instance和classB/instance存在這種微結(jié)構(gòu)關(guān)系,則relationalMask置1.

為解決目前大多數(shù)基于機(jī)器學(xué)習(xí)的設(shè)計(jì)模式檢測(cè)方法只能給出角色映射,而不能給出具體方法映射的問題,在定義方法類微結(jié)構(gòu)時(shí),本文采用比特向量記錄相關(guān)微結(jié)構(gòu)出現(xiàn)的位置和數(shù)目.一旦找到一個(gè)設(shè)計(jì)模式實(shí)例,就可以通過相關(guān)微結(jié)構(gòu)元組中的比特向量以及它們之間的位運(yùn)算來找到對(duì)應(yīng)的方法映射.

圖1 所示的Java 代碼中包含了一個(gè)對(duì)象適配器模式的實(shí)例,其中,Contact 接口類扮演對(duì)象適配器模式的Target 角色,Employee 類扮演對(duì)象適配器模式的Adaptee 角色,ContactAdapter 類扮演對(duì)象適配器模式的Adapter角色.該模式實(shí)例中存在一個(gè) Overriding Method 微結(jié)構(gòu)(ContactAdapter,Contact,01011).其中,01011 表示ContactAdapter 的第2、第4 和第5 個(gè)方法是對(duì)Contact 的覆寫.該模式實(shí)例中還存在另一個(gè)Delegation 微結(jié)構(gòu)(ContactAdapter,Employee,01010).其中,01010 表示ContactAdapter 的第2 和第4 個(gè)方法是對(duì)Employee 的委托.通過對(duì)這兩個(gè)微結(jié)構(gòu)中的比特向量做與運(yùn)算,也即01011&01010=01010,就能找到該對(duì)象適配器模式的方法映射.與運(yùn)算值01010 表示ContactAdapter 的第2 和第4 個(gè)方法對(duì)應(yīng)對(duì)象適配器模式的Request(·)方法.

Fig.1 An instance of object adapter pattern圖1 一個(gè)對(duì)象適配器模式的實(shí)例

定義3(微結(jié)構(gòu)的維度(dimension of micro-structure)).指定微結(jié)構(gòu)所關(guān)聯(lián)的類或?qū)ο蟮膫€(gè)數(shù).對(duì)于定義2所定義的微結(jié)構(gòu),如果classA/instance與classB/instance相同,則稱該微結(jié)構(gòu)的維度為1;否則,稱該微結(jié)構(gòu)的維度為2.

定義4(返回類型微結(jié)構(gòu)(return type)).如果類A中存在一個(gè)方法m,m的返回類型為類B,則稱類A到類B存在返回類型微結(jié)構(gòu).返回類型微結(jié)構(gòu)可以表示為三元組(classA,classB,ReturnTypeMask),其中,ReturnTypeMask是對(duì)應(yīng)于classA的比特向量,如果classA的第n個(gè)方法的返回類型為classB,那么ReturnTypeMask的相應(yīng)位置置1.顯然,比特向量ReturnTypeMask的基數(shù)就是classA到classB的返回類型微結(jié)構(gòu)的數(shù)目.

定義5(多通知微結(jié)構(gòu)(multi-notify)).如果類A中存在某個(gè)包含循環(huán)的方法m,并且循環(huán)體內(nèi)存在對(duì)類B的返回類型為空的方法的調(diào)用,則稱類A到類B存在多通知微結(jié)構(gòu).多通知微結(jié)構(gòu)可以表示為三元組(classA,classB,MultiNotifyMask),其中,MultiNotifyMask是對(duì)應(yīng)于classA的比特向量.如果classA的第n個(gè)方法的內(nèi)部有一個(gè)循環(huán),并且循環(huán)體內(nèi)有對(duì)classB的返回類型為空的方法的調(diào)用,那么MultiNotifyMask的相應(yīng)位置置1.

定義6(參數(shù)化通知微結(jié)構(gòu)(parameterized notify)).如果類A的某個(gè)方法m內(nèi)存在對(duì)類B的帶參數(shù)且返回類型為空的方法的調(diào)用,則稱類A到類B存在參數(shù)化通知微結(jié)構(gòu).參數(shù)化通知微結(jié)構(gòu)可以表示為三元組(classA,classB,ParameterizedNotifyMask),其中,ParameterizedNotifyMask是對(duì)應(yīng)于classA的比特向量.如果classA的第n個(gè)方法內(nèi)有對(duì)類B的帶參數(shù)且返回類型為空的方法的調(diào)用,那么ParameterizedNotifyMask的相應(yīng)位置置1.

定義7(參數(shù)依賴微結(jié)構(gòu)(parameter dependence)).如果類A存在某個(gè)方法m,m的參數(shù)表中包含類型為類B的參數(shù),則稱類A到類B存在參數(shù)依賴微結(jié)構(gòu).參數(shù)依賴微結(jié)構(gòu)表示為三元組:

其中,ParameterDependenceMask是對(duì)應(yīng)于classA的比特向量,如果classA的第n個(gè)方法的參數(shù)表中包含classB類型的參數(shù),那么ParameterDependenceMask的相應(yīng)位置置1.

定義8(返回靜態(tài)自身實(shí)例微結(jié)構(gòu)(static self instance returned)).如果類A存在某個(gè)方法m,m的返回類型為staticclassA,則稱類A 存在返回靜態(tài)自身實(shí)例微結(jié)構(gòu).顯然,該微結(jié)構(gòu)是針對(duì)單個(gè)類而言的1 維微結(jié)構(gòu).返回靜態(tài)自身實(shí)例可以表示為三元組:

其中,StaticSelfInstanceReturnedMask是對(duì)應(yīng)于classA的比特向量.如果classA的第n個(gè)方法的返回類型為static classA,那么StaticSelfInstanceReturnedMask的相應(yīng)位置置1.

為了在工廠方法模式、單例模式、對(duì)象適配器模式、組合模式以及觀察者模式上進(jìn)行實(shí)驗(yàn),本文初步選用了16 種微結(jié)構(gòu),具體情況見表2.

Table 2 Micro-structures used in this paper表2 本文選取的微結(jié)構(gòu)列表

需要說明的是:本文微結(jié)構(gòu)的檢測(cè)是在Java 字節(jié)碼級(jí)別上進(jìn)行的,檢測(cè)工具使用了ASM 框架(一個(gè)Java 字節(jié)碼操作和分析框架).

3 設(shè)計(jì)模式檢測(cè)方法

本節(jié)首先給出該方法的總體框架,接著定義一些基本概念,然后利用定義好的概念對(duì)設(shè)計(jì)模式檢測(cè)過程中的算法進(jìn)行形式化描述,最后提出一種新的組合爆炸問題的解決方法.

3.1 設(shè)計(jì)模式檢測(cè)框架

如圖2 流程所示(圖中某些概念見第3.2 節(jié)),設(shè)計(jì)模式檢測(cè)方法分為兩個(gè)階段:第1 個(gè)階段是模型訓(xùn)練階段,第2 個(gè)階段是模式識(shí)別階段.基本思想是,結(jié)合度量和微結(jié)構(gòu)進(jìn)行設(shè)計(jì)模式檢測(cè).通過為每種設(shè)計(jì)模式找到合適的度量分類器和微結(jié)構(gòu)分類器,進(jìn)而訓(xùn)練出堆疊分類器,然后用這些分類器對(duì)一個(gè)候選的模式實(shí)例進(jìn)行分類,從而預(yù)測(cè)候選的模式實(shí)例是不是真正的模式實(shí)例.

設(shè)計(jì)模式檢測(cè)相關(guān)的度量和微結(jié)構(gòu)是設(shè)計(jì)模式的兩個(gè)獨(dú)立視圖,目前還無人提出同時(shí)考慮這兩個(gè)視圖的檢測(cè)方法.另外,因?yàn)槊總€(gè)視圖最適合的分類器可能不同,如果簡(jiǎn)單地將兩個(gè)視圖的特征混合到一起之后再訓(xùn)練出一個(gè)分類器,那么就有可能丟失這種差異性.因此,本文針對(duì)每個(gè)視圖單獨(dú)訓(xùn)練分類器,然后再進(jìn)行模型堆疊.

Fig.2 Design pattern detection method based on metrics and micro-structures圖2 度量和微結(jié)構(gòu)相結(jié)合的設(shè)計(jì)模式檢測(cè)方法

3.2 基本概念定義

為了方便描述模型訓(xùn)練算法和模式檢測(cè)算法,本文給出如下符號(hào)和定義:

設(shè)計(jì)模式(design pattern,簡(jiǎn)稱DP).DP 是23 種基本的設(shè)計(jì)模式之一或未來出現(xiàn)的其他設(shè)計(jì)模式.后續(xù)算法將采用此標(biāo)記.

定義9(角色映射(role map),簡(jiǎn)稱RM).角色映射是一個(gè)設(shè)計(jì)模式角色和角色類之間的對(duì)應(yīng)關(guān)系,可以表示為二元組RM=(Role,Class).

舉例來講,對(duì)于QuickUML2001 項(xiàng)目中存在的一個(gè)工廠方法模式實(shí)例,存在以下4 個(gè)角色映射:

定義10(模式實(shí)例(pattern instance),簡(jiǎn)稱PI).模式實(shí)例包括角色映射集合RoleMaps和該實(shí)例的類別標(biāo)簽Label,可以表示為PI=(RoleMaps,Label).其中,Label∈{CORRECT,INCORRECT}.Label=CORRECT表示該實(shí)例是一個(gè)正確的模式實(shí)例,或稱為正實(shí)例;Label=INCORRECT表示該實(shí)例不是一個(gè)正確的模式實(shí)例,或稱為負(fù)實(shí)例.

定義11(正負(fù)模式實(shí)例庫(kù)(positive and negative pattern instances repository),簡(jiǎn)稱PNPIR).正負(fù)模式實(shí)例庫(kù)包括該實(shí)例庫(kù)對(duì)應(yīng)的設(shè)計(jì)模式DP和該設(shè)計(jì)模式的正負(fù)實(shí)例的集合,可以表示為二元組:

定義12(度量知識(shí)庫(kù)(metrics repository),簡(jiǎn)稱MR).度量知識(shí)庫(kù)是一個(gè)面向?qū)ο蠖攘康募?

舉例來講,本文采用的度量知識(shí)庫(kù)MR={ACAIC,ACMIC,AID,…,connectivity}(完整列表見表1).需要說明的是,度量知識(shí)庫(kù)并不是一成不變的,可以根據(jù)模式檢測(cè)的需要進(jìn)行不斷地更新.

定義13(微結(jié)構(gòu)知識(shí)庫(kù)(micro-structure repository),簡(jiǎn)稱MSR).微結(jié)構(gòu)知識(shí)庫(kù)是一個(gè)設(shè)計(jì)模式微結(jié)構(gòu)的集合.

舉例來講,本文采用的微結(jié)構(gòu)知識(shí)庫(kù)MSR={Overriding Method,Create Object,Return Type,…,Static Self Instance Returned}(完整列表見表2).需要說明的是,之所以選擇這么少的微結(jié)構(gòu),是因?yàn)楸疚南胂仍? 種設(shè)計(jì)模式上進(jìn)行實(shí)驗(yàn),以驗(yàn)證所提方法的有效性.未來為了檢測(cè)其他的設(shè)計(jì)模式,這個(gè)微結(jié)構(gòu)知識(shí)庫(kù)肯定會(huì)包括更多的內(nèi)容.

定義14(設(shè)計(jì)模式度量特征(design pattern metric feature),簡(jiǎn)稱DPMF).設(shè)計(jì)模式度量特征是一個(gè)三元組,可以表示為DPMF=(Role,Metric,Value).其中:Role是設(shè)計(jì)模式的某個(gè)角色;Metric是度量知識(shí)庫(kù)中的某個(gè)度量;Value是該度量特征的具體數(shù)值,它等于角色Role對(duì)應(yīng)的角色類的Metric度量值.

定義15(設(shè)計(jì)模式微結(jié)構(gòu)特征(design pattern micro-structure feature),簡(jiǎn)稱DPMSF).設(shè)計(jì)模式微結(jié)構(gòu)特征是一個(gè)四元組,可以表示為DPMSF=(Role1,Role2,Microstructure,Value).其中:Role1 和Role2 是設(shè)計(jì)模式的的兩個(gè)角色;Microstructure是微結(jié)構(gòu)知識(shí)庫(kù)中的某個(gè)微結(jié)構(gòu);Value是該微結(jié)構(gòu)特征的具體數(shù)值,它等于Role1 對(duì)應(yīng)的角色類→Role2 對(duì)應(yīng)的角色類的Microstructure微結(jié)構(gòu)的數(shù)目.

另外,本文是在Weka 平臺(tái)上進(jìn)行實(shí)驗(yàn)的,用到的特征選擇算法有CfsSubsetEval,CorrelationAttributeEval,InfoGainAttributeEval,PrincipalComponents 和ReliefFAttributeEval,用一個(gè)集合來表示:FSASet={CfsSubsetEval,CorrelationAttributeEval,InfoGainAttributeEval,PrincipalComponents,ReliefFAttributeEval}.

同時(shí),采用RandomForest,LibSVM,J48 等15 種常見的有監(jiān)督學(xué)習(xí)算法,用一個(gè)集合來表示:

3.3 3個(gè)模型訓(xùn)練算法

在模型訓(xùn)練階段,相關(guān)分類器的訓(xùn)練算法可以描述如下.

度量分類器訓(xùn)練算法以度量知識(shí)庫(kù)、某種設(shè)計(jì)模式以及相應(yīng)的正負(fù)模式實(shí)例庫(kù)為輸入,通過為實(shí)例庫(kù)中的每個(gè)實(shí)例計(jì)算所有的度量特征,從而生成該設(shè)計(jì)模式的度量分類器的訓(xùn)練數(shù)據(jù)集.最后,通過遍歷特征選擇算法和分類算法找到最適合該設(shè)計(jì)模式的度量特征集和度量分類器.具體算法見表3.

Table 3 Metric classifier train algorithm表3 度量分類器訓(xùn)練算法

本文為設(shè)計(jì)模式dp的所有角色類計(jì)算所有的度量值.假設(shè)設(shè)計(jì)模式dp有n個(gè)角色,度量知識(shí)庫(kù)mr有m個(gè)度量,那么訓(xùn)練數(shù)據(jù)集就有n×m個(gè)特征,外加一個(gè)分類標(biāo)簽.CMeFV 以設(shè)計(jì)模式的角色類和度量為輸入,計(jì)算該角色類的相應(yīng)度量特征值.第15 行的循環(huán)條件表示遍歷FSASet 和CASet,從而找到使得分類效果最好的特征選擇算法和有監(jiān)督學(xué)習(xí)算法.其中,algo1 和algo3 分別表示某種特征選擇算法,它們以訓(xùn)練數(shù)據(jù)集為輸入,通過在訓(xùn)練數(shù)據(jù)集上進(jìn)行特征選擇,輸出選擇的特征子集;algo2 和algo4 分別表示某種分類算法,它們以訓(xùn)練數(shù)據(jù)集和特征子集為輸入,通過訓(xùn)練,輸出相應(yīng)的分類器.

f1Measureof(*)表示括號(hào)內(nèi)分類器在CORRECT 類別上的F1-Measure值.

微結(jié)構(gòu)分類器訓(xùn)練算法以微結(jié)構(gòu)知識(shí)庫(kù)、某種設(shè)計(jì)模式以及相應(yīng)的正負(fù)模式實(shí)例庫(kù)為輸入,通過為實(shí)例庫(kù)中的每個(gè)實(shí)例計(jì)算所有的微結(jié)構(gòu)特征,從而生成該設(shè)計(jì)模式的微結(jié)構(gòu)分類器的訓(xùn)練數(shù)據(jù)集.最后,同樣通過遍歷特征選擇算法和分類算法找到最適合該設(shè)計(jì)模式的微結(jié)構(gòu)特征集和微結(jié)構(gòu)分類器.具體算法見表4.

Table 4 Micro-structure classifier train algorithm表4 微結(jié)構(gòu)分類器訓(xùn)練算法

CMsFV 以設(shè)計(jì)模式的兩個(gè)角色類和微結(jié)構(gòu)為輸入,計(jì)算這兩個(gè)角色類的相應(yīng)微結(jié)構(gòu)特征值.第18 行省略的部分同表3 的第14 行～第19 行.

堆疊分類器訓(xùn)練算法以某種設(shè)計(jì)模式以及相應(yīng)的正負(fù)模式實(shí)例庫(kù)、度量特征集、度量分類器、微結(jié)構(gòu)特征集和微結(jié)構(gòu)分類器為輸入,通過為實(shí)例庫(kù)中的每個(gè)實(shí)例計(jì)算相關(guān)的度量特征和微結(jié)構(gòu)特征,從而生成該設(shè)計(jì)模式的堆疊分類器的初始訓(xùn)練數(shù)據(jù)集;然后,通過十折交叉的方法計(jì)算每個(gè)樣本的度量分類器預(yù)測(cè)值和微結(jié)構(gòu)分類器預(yù)測(cè)值,并將這兩個(gè)值作為新的特征添加到樣本當(dāng)中;最后,通過遍歷分類算法找到最適合該設(shè)計(jì)模式的堆疊分類器.具體算法見表5.

Table 5 Stacked classifier train algorithm表5 堆疊分類器訓(xùn)練算法

Table 5 Stacked classifier train algorithm (Continued)表5 堆疊分類器訓(xùn)練算法(續(xù))

CMeF 以設(shè)計(jì)模式的實(shí)例和度量特征為輸入,計(jì)算相應(yīng)的設(shè)計(jì)模式度量特征;CMsF 以設(shè)計(jì)模式的實(shí)例和微結(jié)構(gòu)特征為輸入,計(jì)算相應(yīng)的設(shè)計(jì)模式微結(jié)構(gòu)特征;RandDiv 以折數(shù)10 和訓(xùn)練數(shù)據(jù)集為輸入,輸出隨機(jī)劃分的10個(gè)訓(xùn)練數(shù)據(jù)子集;ReTrainClassifier 以度量/微結(jié)構(gòu)特征集、度量/微結(jié)構(gòu)分類器以及重新訓(xùn)練用的數(shù)據(jù)集為輸入,利用度量/微結(jié)構(gòu)分類器的分類算法重新訓(xùn)練分類器;classify 以某個(gè)分類器和將要分類的樣本的特征向量為輸入,輸出相應(yīng)樣本的類別標(biāo)簽,也即CORRECT 或INCORRECT.第28 行省略的部分代表遍歷CASet,從而找到最適合設(shè)計(jì)模式dp的堆疊分類器classifier.

3.4 設(shè)計(jì)模式檢測(cè)算法

在模式識(shí)別階段,本文的設(shè)計(jì)模式檢測(cè)算法可以描述如下.

設(shè)計(jì)模式檢測(cè)算法以待檢測(cè)系統(tǒng)的所有類(包括接口)、待檢測(cè)的設(shè)計(jì)模式以及相應(yīng)的度量特征集、度量分類器、微結(jié)構(gòu)特征集、微結(jié)構(gòu)分類器、堆疊分類器為輸入,首先計(jì)算系統(tǒng)所有類的度量信息和微結(jié)構(gòu)信息,然后生成候選實(shí)例,接著對(duì)每個(gè)候選實(shí)例計(jì)算度量特征和微結(jié)構(gòu)特征,然后分別用度量分類器和微結(jié)構(gòu)分類器進(jìn)行分類,最后將兩個(gè)分類器的預(yù)測(cè)結(jié)果作為新的特征再用堆疊分類器進(jìn)行分類,從而預(yù)測(cè)候選實(shí)例是不是真正的模式實(shí)例.具體算法見表6.

CalcMe 以待檢測(cè)系統(tǒng)的所有類和設(shè)計(jì)模式的度量特征集為輸入,為每個(gè)類計(jì)算度量特征集中所涉及到的所有度量,輸出待檢測(cè)系統(tǒng)的度量信息,它可以看作是類度量表示(CMR)的集合;DetectMs 以待檢測(cè)系統(tǒng)的所有類和設(shè)計(jì)模式的微結(jié)構(gòu)特征集為輸入,檢測(cè)微結(jié)構(gòu)特征集中所涉及到的所有微結(jié)構(gòu),輸出待檢測(cè)系統(tǒng)的微結(jié)構(gòu)信息,它可以看作是微結(jié)構(gòu)的集合;GenCandIns 以待檢測(cè)系統(tǒng)的所有類以及待檢測(cè)的設(shè)計(jì)模式為輸入,通過執(zhí)行本文的候選實(shí)例生成算法,輸出待檢測(cè)系統(tǒng)中相應(yīng)設(shè)計(jì)模式的候選實(shí)例的集合;CMeF2/CMsF2 以候選實(shí)例、將要計(jì)算的度量特征/微結(jié)構(gòu)特征以及待檢測(cè)系統(tǒng)的度量信息/微結(jié)構(gòu)信息為輸入,通過簡(jiǎn)單檢索,輸出相應(yīng)候選實(shí)例的相應(yīng)度量特征/微結(jié)構(gòu)特征.

需要說明的是:為了避免組合爆炸,本文的候選實(shí)例生成算法在考慮設(shè)計(jì)模式繼承層次信息的基礎(chǔ)之上加入了一些自己的考量,它的過程可以簡(jiǎn)單描述如下:(1) 從待檢測(cè)系統(tǒng)中檢測(cè)出所有的繼承層次;(2) 根據(jù)設(shè)計(jì)模式所包含的繼承層次信息,從待檢測(cè)系統(tǒng)中枚舉出候選模式實(shí)例;(3) 過濾掉那些不包含設(shè)計(jì)模式之必備微結(jié)構(gòu)的候選實(shí)例(模式必備微結(jié)構(gòu)是指正確模式實(shí)例必須具備的微結(jié)構(gòu),它是候選實(shí)例被評(píng)估為正確實(shí)例的必要非充分條件).本文是依據(jù)GoF 等人給出的定義以及經(jīng)驗(yàn)數(shù)據(jù)來定義模式必備微結(jié)構(gòu)的,不會(huì)對(duì)設(shè)計(jì)模式檢測(cè)的正確率與召回率產(chǎn)生影響.舉例來講,對(duì)于工廠方法模式,GoF 等人給出的定義是,“定義一個(gè)用于創(chuàng)建對(duì)象的接口,讓子類決定實(shí)例化哪一個(gè)類.”[1].顯然,ConcreteCreator 對(duì) Creator 的 Overriding Method 微結(jié)構(gòu)和ConcreteCreator 對(duì)Product 類別的Create Object 微結(jié)構(gòu)就是兩個(gè)必要的微結(jié)構(gòu),因?yàn)樗鼈兪枪S方法模式定義的隱含信息.

Table 6 Design pattern detection algorithm表6 設(shè)計(jì)模式檢測(cè)算法

以上便是本文所提方法的全部.為了豐富正負(fù)模式實(shí)例庫(kù),可以對(duì)堆疊分類器的分類結(jié)果進(jìn)行人工檢測(cè),并把相應(yīng)的實(shí)例添加到正負(fù)模式實(shí)例庫(kù)中.

4 實(shí)驗(yàn)評(píng)估

為了評(píng)估所提方法的有效性,本文進(jìn)行了相關(guān)實(shí)驗(yàn):在模型訓(xùn)練階段,為實(shí)驗(yàn)的每個(gè)設(shè)計(jì)模式找到了合適的度量特征集和微結(jié)構(gòu)特征集,并在此基礎(chǔ)上訓(xùn)練出了度量分類器、微結(jié)構(gòu)分類器和堆疊分類器;在模式識(shí)別階段,在7 個(gè)開源項(xiàng)目上進(jìn)行了實(shí)驗(yàn),并且和現(xiàn)有的兩種工具進(jìn)行了對(duì)比分析.

4.1 模型訓(xùn)練評(píng)估

目前可用的度量和微結(jié)構(gòu)有很多,可以使用的分類算法也有很多.對(duì)于設(shè)計(jì)模式檢測(cè)這一問題,本文的思路是:盡可能生成更多的候選度量特征和候選微結(jié)構(gòu)特征,然后再進(jìn)行特征選擇和分類算法選擇,通過遍歷特征選擇算法和分類算法,從而為每種設(shè)計(jì)模式找到合適的特征集和分類器.現(xiàn)階段可用的模式實(shí)例庫(kù)主要包括P-MARt[33],DPB[34]和Percerons[35]等,本文通過抽取MARPLE 項(xiàng)目[16]中的訓(xùn)練樣本和網(wǎng)絡(luò)搜集的一些訓(xùn)練樣本構(gòu)造正負(fù)模式實(shí)例庫(kù).具體情況見表7.

Table 7 PNPIR used in this paper表7 本文用到的正負(fù)模式實(shí)例庫(kù)的情況

在表7 中,正的模式實(shí)例數(shù)是指正確的模式實(shí)例個(gè)數(shù),即正樣本的個(gè)數(shù);負(fù)的模式實(shí)例數(shù)是指不正確的模式實(shí)例個(gè)數(shù),即負(fù)樣本的個(gè)數(shù).對(duì)于設(shè)計(jì)模式檢測(cè)來講,什么樣的正負(fù)樣本比例最合適,并沒有先驗(yàn)的知識(shí).本文正負(fù)模式實(shí)例的比例初步控制在1:3 以內(nèi).

Fig.3 Observer pattern[1]圖3 觀察者模式[1]

下面以觀察者模式為例,介紹特征選擇和算法選擇的結(jié)果.觀察者模式的類圖如圖3 所示.從圖3 中可以看出:觀察者模式應(yīng)該有4 個(gè)角色,分別是Subject,ConcreteSubject,Observer,ConcreteObserver.但是在實(shí)際應(yīng)用中,經(jīng)常存在ConcreteSubject/ConcreteObserver 角色缺失或和相應(yīng)的父類合并的情況.不過,無論如何總會(huì)有一個(gè)Subject 類別的角色和一個(gè)Observer 類別的角色,因此對(duì)于觀察者模式的檢測(cè)而言,可以只考慮一個(gè)Subject 類別的角色和一個(gè)Observer 類別的角色,從而如果找到了這樣一個(gè)組合,那么剩下缺失或合并的角色很容易就能通過檢查它們所在的繼承層次來發(fā)現(xiàn).

表8～表10(只顯示前5 項(xiàng)數(shù)據(jù))是觀察者模式3 個(gè)分類器的訓(xùn)練結(jié)果.

從表8 可以看出:不進(jìn)行特征選擇,并且使用RandomForest 算法進(jìn)行模型訓(xùn)練時(shí),所取得的F1-Measure 最高.從表9 可以看出:使用ReliefFAttributeEval 進(jìn)行特征選擇,并且使用RandomCommittee 算法進(jìn)行模型訓(xùn)練時(shí),所取得的F1-Measure 最高.從表10 可以看出,觀察者模式的堆疊分類器應(yīng)該采用RandomForest 算法.

Table 8 Training results of observer pattern’s metric classifier表8 觀察者模式度量分類器的訓(xùn)練結(jié)果

Table 9 Training results of observer pattern’s micro-structure classifier表9 觀察者模式微結(jié)構(gòu)分類器的訓(xùn)練結(jié)果

Table 10 Training results of observer pattern’s stacked classifier表10 觀察者模式堆疊分類器的訓(xùn)練結(jié)果

表11 顯示了觀察者模式的微結(jié)構(gòu)特征列表,它是對(duì)觀察者的候選微結(jié)構(gòu)特征進(jìn)行特征選擇的結(jié)果.另外,因?yàn)閺谋? 可以看出:在訓(xùn)練度量分類器的時(shí)候,不進(jìn)行特征選擇并且使用RandomForest 算法訓(xùn)練時(shí)就已經(jīng)取得了最好的分類效果,而且好于用CorrelationAttributeEval 進(jìn)行特征選擇后再訓(xùn)練的結(jié)果,所以這里并沒有給出觀察者的度量特征列表.從表11 可以看出:對(duì)于觀察者模式,它的微結(jié)構(gòu)特征集包括14 個(gè)特征(表中的1 表示相應(yīng)位置的微結(jié)構(gòu)特征被選中).需要說明的是:在使用ReliefFAttributeEval 進(jìn)行特征選擇時(shí),本文使用0 作為ReliefF 評(píng)估值的閾值.另外,從表11 還可以看出:本文新提出的5 種方法類微結(jié)構(gòu)中,有4 種與觀察者模式的檢測(cè)有關(guān).

Table 11 List of micro-structure features of observer pattern表11 觀察者模式的微結(jié)構(gòu)特征列表

4.2 模式識(shí)別評(píng)估

在模式識(shí)別階段:首先,對(duì)待檢測(cè)的系統(tǒng)進(jìn)行預(yù)處理,也即計(jì)算待檢測(cè)系統(tǒng)的度量信息和抽取待檢測(cè)系統(tǒng)的所有微結(jié)構(gòu);其次,根據(jù)微結(jié)構(gòu)信息生成候選實(shí)例;再次,計(jì)算候選實(shí)例的度量特征和微結(jié)構(gòu)特征;最后,用相應(yīng)的度量分類器、微結(jié)構(gòu)分類器和堆疊分類器進(jìn)行分類,從而預(yù)測(cè)一個(gè)候選實(shí)例是否為真正的模式實(shí)例.

本文首先在JHotDraw v5.1,JRefactory v2.6.24 和JUnit v3.7 這3 個(gè)開源項(xiàng)目上進(jìn)行了實(shí)驗(yàn),正如第3 節(jié)所述,為了避免組合爆炸,本文在考慮設(shè)計(jì)模式繼承層次信息的基礎(chǔ)之上,加入了設(shè)計(jì)模式必備微結(jié)構(gòu)的考量.對(duì)于工廠方法模式,具體情況見表12.

Table 12 Candidate instances of factory method pattern表12 工廠方法模式的候選實(shí)例的組合情況

假設(shè)待檢測(cè)項(xiàng)目有n個(gè)類,那么對(duì)于k個(gè)角色的設(shè)計(jì)模式,默認(rèn)情況下,它總共有A(n,k)個(gè)候選實(shí)例.其中,A(n,k)的計(jì)算公式如下:

舉例來講,對(duì)于表12 中JhotDraw v5.1,它共有155 個(gè)類(不考慮內(nèi)部匿名類),如果從中產(chǎn)生工廠方法模式(k=4)的候選實(shí)例,那么候選實(shí)例的個(gè)數(shù)=A(155,4)=555120720.可以看出:默認(rèn)情況下,工廠方法模式的候選實(shí)例的數(shù)量非常大.在考慮工廠方法模式的繼承層次信息后,候選實(shí)例的數(shù)量減少到322 624,縮減了99%以上(具體過程見Tsantalis 等人的論文[7]);如果再考慮工廠方法模式的必備微結(jié)構(gòu)信息(參見第3.4 節(jié)),那么候選實(shí)例的數(shù)量又會(huì)進(jìn)一步縮減90%以上(最終只剩下4 301 個(gè)候選實(shí)例).

通常,每種設(shè)計(jì)模式都對(duì)應(yīng)一個(gè)堆疊分類器.對(duì)于實(shí)驗(yàn)的5 種設(shè)計(jì)模式,由于它們?cè)诮Y(jié)構(gòu)上各不相同,因此都分別對(duì)應(yīng)一個(gè)堆疊分類器(對(duì)于結(jié)構(gòu)相同的設(shè)計(jì)模式,比如State 模式和Strategy 模式,未來我們準(zhǔn)備讓它們共用一個(gè)堆疊分類器,訓(xùn)練的方法和前面提到的差不多,稍加修改即可).模式檢測(cè)的過程也就是將一個(gè)個(gè)候選模式實(shí)例分類為CORRECT 或INCORRECT 的過程,因此是二分類問題,對(duì)應(yīng)的混淆矩陣如下.

其中,a+b+c+d等于候選模式實(shí)例的個(gè)數(shù).由于本文的目的是檢測(cè)出正確的模式實(shí)例,因此選擇CORRECT類別的準(zhǔn)確率作為第一個(gè)度量指標(biāo),記準(zhǔn)確率Precision=a/(a+c),相應(yīng)的召回率Recall=a/(a+b)本應(yīng)該作為第2個(gè)度量指標(biāo),但是考慮到生成的候選模式實(shí)例并不一定涵蓋所有正確的模式實(shí)例,同時(shí)也為了能夠在不同的設(shè)計(jì)模式檢測(cè)方法之間進(jìn)行比較(基于機(jī)器學(xué)習(xí)的方法和非基于機(jī)器學(xué)習(xí)的方法),因此第2 個(gè)度量指標(biāo)召回率Recall應(yīng)該等于a/所有檢測(cè)方法檢測(cè)到的正確的模式實(shí)例個(gè)數(shù).最后一個(gè)度量指標(biāo):

根據(jù)前面所提出的設(shè)計(jì)模式檢測(cè)方法,本文開發(fā)了設(shè)計(jì)模式檢測(cè)工具OOSdpd 的原型,并且在JHotDraw v5.1,JRefactory v2.6.24 和JUnit v3.7 這3 個(gè)開源項(xiàng)目上進(jìn)行了實(shí)驗(yàn).之所以選擇這些項(xiàng)目,是因?yàn)檫@些項(xiàng)目大量使用了設(shè)計(jì)模式,特別是JHotDraw,同時(shí)很多設(shè)計(jì)模式檢測(cè)方法也都是以這3 個(gè)項(xiàng)目為例進(jìn)行實(shí)驗(yàn)的,這樣一來就比較容易對(duì)比分析.雖然目前有很多種設(shè)計(jì)模式檢測(cè)方法,但是提供檢測(cè)工具的卻很少,本文在P-MARt[33],SSA[7]和所提出的方法之間進(jìn)行比較,具體實(shí)驗(yàn)數(shù)據(jù)見表13～表15.

Table 13 Experimental data of the JHotDraw project表13 JHotDraw 項(xiàng)目的實(shí)驗(yàn)數(shù)據(jù)

Table 14 Experimental data of the JRefactory project表14 JRefactory 項(xiàng)目的實(shí)驗(yàn)數(shù)據(jù)

Table 15 Experimental data of the JUnit project表15 JUnit 項(xiàng)目的實(shí)驗(yàn)數(shù)據(jù)

一般來講,不同的設(shè)計(jì)模式檢測(cè)方法針對(duì)同一項(xiàng)目、同一設(shè)計(jì)模式的檢測(cè)結(jié)果也不同,除了方法上的原因之外,還有一個(gè)重要的原因,那就是它們選擇的模式出現(xiàn)類型不同[36],也即計(jì)數(shù)模式實(shí)例的方法不同.因此,為了在不同的方法之間進(jìn)行比較,本文使用如下模式出現(xiàn)類型:FactoryMethod:(Creator,Product),Singleton:(Singleton),Adapter:(Target,Adapter),Composite:(Component,Composite),Observer:(Subject,Observer).另外需要說明的是:P-MARt 和SSA 這兩種檢測(cè)方法并不是基于機(jī)器學(xué)習(xí)的,它們的準(zhǔn)確率Precision=檢測(cè)出的實(shí)例中正確的個(gè)數(shù)/檢測(cè)出的實(shí)例的總個(gè)數(shù),召回率Recall=檢測(cè)出的實(shí)例中正確的個(gè)數(shù)/所有檢測(cè)方法檢測(cè)到的正確的模式實(shí)例個(gè)數(shù),F1-Measure=2×Precision×Recall/(Precision+Recall).

從表13～表15 的實(shí)驗(yàn)數(shù)據(jù)來看,本文的方法多數(shù)情況下具有較高的準(zhǔn)確率和召回率,其中,總數(shù)指的是所有檢測(cè)方法檢測(cè)到的正確的模式實(shí)例個(gè)數(shù).從圖4 可以看出:對(duì)于工廠方法模式、單例模式和對(duì)象適配器模式,本文的方法具有更高的F1-Measure(該值是3 個(gè)項(xiàng)目的平均值).對(duì)于組合模式,3 種方法的檢測(cè)結(jié)果一樣,因此它們的F1-Measure 也一樣.這是因?yàn)閷?shí)驗(yàn)的項(xiàng)目中,組合模式的實(shí)例很少,每個(gè)項(xiàng)目最多只有一個(gè),3 種方法都能輕松應(yīng)對(duì).對(duì)于觀察者模式,本文的方法的F1-Measure 高于SSA,但是比P-MARt 稍低,這主要是因?yàn)楸疚牡姆椒壳吧胁恢С植糠纸巧惔嬖谟诘谌綆?kù)中的情況.另外,P-MARt 和SSA 的準(zhǔn)確率也并非總是100%的.舉例來講,對(duì)于JHotDraw v5.1 中的單例模式,P-MARt 和SSA 都檢測(cè)出了兩個(gè)單例模式實(shí)例CH.ifa.draw.util.Clipboard 和CH.ifa.draw.util.Iconkit,但是本文的方法只檢測(cè)到了一個(gè)模式實(shí)例 CH.ifa.draw.util.Clipboard.實(shí)際上,雖然CH.ifa.draw.util.Iconkit 很像單例模式,但它并不是,因?yàn)樗幸粋€(gè)訪問權(quán)限為public 的構(gòu)造函數(shù),因此它不符合單例模式的要求.

Fig.4 Comparison of detection results on different design patterns圖4 不同設(shè)計(jì)模式檢測(cè)效果對(duì)比

圖5 顯示了不同檢測(cè)方法針對(duì)不同開源項(xiàng)目的檢測(cè)效果.需要說明的是:這里的AverageF1-Measure代表對(duì)于某個(gè)開源項(xiàng)目,5 種設(shè)計(jì)模式檢測(cè)結(jié)果的F1-Measure的平均值.從中可以看出:本文的方法多數(shù)情況下檢測(cè)效果最好,只有在JUnit v3.7 項(xiàng)目上弱于P-MARt.其主要原因還是上面提過的,觀察者模式的檢測(cè)效果不如P-MARt.另外,對(duì)于SSA 和本文的方法,JHotDraw v5.1 的檢測(cè)效果最好,可能的原因有兩個(gè):(1) JHotDraw v5.1 的模式實(shí)例占比(模式實(shí)例數(shù)/項(xiàng)目總類數(shù))更高;(2) JHotDraw 起源于Gamma 的一個(gè)教學(xué)實(shí)例,而他是軟件設(shè)計(jì)模式概念的提出者之一.最后,從檢測(cè)效果的穩(wěn)定性來看,SSA 和本文的方法更加穩(wěn)定,而P-MARt 針對(duì)不同項(xiàng)目的檢測(cè)效果差別很大.

Fig.5 Comparison of detection results on different open source projects圖5 不同開源項(xiàng)目檢測(cè)效果對(duì)比

上面實(shí)驗(yàn)的項(xiàng)目規(guī)模都比較小,而且目前大部分設(shè)計(jì)模式的檢測(cè)研究都集中在這3 個(gè)項(xiàng)目上.為了驗(yàn)證本文的方法在其他項(xiàng)目上的有效性,以及觀察有效性隨著項(xiàng)目規(guī)模的變化情況,本文又在ASM v1.4.2(59 個(gè)類),Dom4j v1.6.1(189 個(gè)類),Guice v3.0(425 個(gè)類)和Struts v2.5.14.1(2 742 個(gè)類)等4 個(gè)開源項(xiàng)目上進(jìn)行了實(shí)驗(yàn).其中,ASM 是常用的Java 字節(jié)碼操作框架,Dom4j 是十分優(yōu)秀的XML 解析包,Guice 是幫助代碼實(shí)現(xiàn)控制反轉(zhuǎn)的函數(shù)庫(kù),Struts 是基于MVC 的Web 框架.具體實(shí)驗(yàn)數(shù)據(jù)見表16～表19.

由于P-MARt 實(shí)際上是人工標(biāo)注的實(shí)例庫(kù),并沒有提供可用的檢測(cè)工具,因此本文的方法只和SSA 工具進(jìn)行對(duì)比.需要說明的是:為了統(tǒng)計(jì)方便,對(duì)象適配器模式采用了Adapter:(Adapter)模式出現(xiàn)類型.

Table 16 Experimental data of the ASM project表16 ASM 項(xiàng)目的實(shí)驗(yàn)數(shù)據(jù)

Table 17 Experimental data of the Dom4j project表17 Dom4j 項(xiàng)目的實(shí)驗(yàn)數(shù)據(jù)

Table 18 Experimental data of the Guice project表18 Guice 項(xiàng)目的實(shí)驗(yàn)數(shù)據(jù)

Table 19 Experimental data of the Struts project表19 Struts 項(xiàng)目的實(shí)驗(yàn)數(shù)據(jù)

從表16 可以看出,本文的方法只在單例模式上弱于SSA.從表17 可以看出,本文的方法在實(shí)驗(yàn)的5 種設(shè)計(jì)模式上均好于SSA.從表18 可以看出,本文的方法在工廠方法模式上明顯弱于SSA.這主要是因?yàn)镚uice v3.0 項(xiàng)目中包含了很多內(nèi)部類實(shí)現(xiàn)的工廠方法模式,而本文的方法用的POM Tests 度量計(jì)算工具并不支持內(nèi)部類,因此許多實(shí)例沒有檢測(cè)出來;另外,對(duì)于單例模式,和SSA 相比,本文的方法準(zhǔn)確率高,但是召回率低,不過兩者的F1-Measure非常接近.從表19 可以看出,本文的方法在所有模式上均好于SSA.

圖6 顯示的是每種設(shè)計(jì)模式的平均檢測(cè)效果,從中可以看出:本文的方法只在單例模式上弱于SSA,但是差距并不明顯;在組合模式和觀察者模式上,本文的方法明顯好于SSA,這主要是因?yàn)楸疚牡姆椒ㄊ褂昧烁嗄軌蝮w現(xiàn)模式結(jié)構(gòu)和行為特征的微結(jié)構(gòu)信息.圖7 顯示的是針對(duì)不同項(xiàng)目規(guī)模,SSA 和本文的方法在5 種設(shè)計(jì)模式上的平均檢測(cè)效果對(duì)比,從中可以看出:對(duì)于不同規(guī)模的項(xiàng)目,本文方法的檢測(cè)效果和SSA 的檢測(cè)效果都有一定的波動(dòng),但是本文方法的檢測(cè)效果更加穩(wěn)定.另外,對(duì)于規(guī)模比較小的項(xiàng)目(ASM v1.4.2 和Guice v3.0),本文的方法和SSA 相比優(yōu)勢(shì)并不明顯;但是對(duì)于規(guī)模比較大的項(xiàng)目(Struts v2.5.14.1),本文的方法要明顯好于SSA.因此,從實(shí)驗(yàn)數(shù)據(jù)來看,本文的方法更加適合規(guī)模比較大的項(xiàng)目.

Fig.6 Comparison of detection results on different design patterns圖6 不同設(shè)計(jì)模式檢測(cè)效果對(duì)比

Fig.7 Comparison of detection results on different project scale圖7 不同項(xiàng)目規(guī)模檢測(cè)效果對(duì)比

通過以上兩組對(duì)比實(shí)驗(yàn)可以看出,本文的方法和P-MARt 以及SSA 相比,多數(shù)情況下具有更高的識(shí)別準(zhǔn)確率和召回率.對(duì)于單例模式,本文的方法還需要進(jìn)一步改進(jìn).對(duì)于觀察者模式,本文的方法的檢測(cè)效果要明顯好于單純基于結(jié)構(gòu)相似度計(jì)算的SSA.

雖然目前有很多種基于機(jī)器學(xué)習(xí)的設(shè)計(jì)模式檢測(cè)方法,但是我們沒能找到任何一款可用的檢測(cè)工具,而且這些方法多數(shù)也沒有指明所采用的模式出現(xiàn)類型,因此很難以拿本文的方法與它們進(jìn)行比較.

4.3 有效性分析

影響外部有效性的因素主要有以下3 點(diǎn).

1)與其他基于機(jī)器學(xué)習(xí)的檢測(cè)方法一樣,本文的訓(xùn)練數(shù)據(jù)集也是由人工產(chǎn)生的,這就會(huì)受到主觀因素的影響.因此,需要找到一個(gè)廣泛認(rèn)可的設(shè)計(jì)模式實(shí)例庫(kù)作為訓(xùn)練數(shù)據(jù)集的來源;

2)本文以工廠方法模式為例,定義了它的兩個(gè)必備微結(jié)構(gòu),從而顯著地縮減了候選實(shí)例的搜索空間,避免了組合爆炸.但是對(duì)于其他設(shè)計(jì)模式,定義模式必備微結(jié)構(gòu)對(duì)避免組合爆炸的有效程度還需要進(jìn)一步研究;

3)雖然本文在觀察者模式上取得了更好的檢測(cè)效果,但是對(duì)于其他行為型設(shè)計(jì)模式的檢測(cè)效果還需要進(jìn)一步驗(yàn)證.

影響內(nèi)部有效性的因素主要有以下兩點(diǎn):(1) 由于訓(xùn)練樣本不夠豐富以及所采用的度量知識(shí)庫(kù)和微結(jié)構(gòu)知識(shí)庫(kù)不夠完備,本文提出的方法對(duì)單例模式的檢測(cè)效果還不夠理想,不足以驗(yàn)證所提方法的有效性;(2) 如果模式實(shí)例中含有部分存在于第三方庫(kù)中角色類,本文的方法無法準(zhǔn)確檢測(cè),需要進(jìn)一步研究如何將第三方庫(kù)中的有效信息加載到檢測(cè)目標(biāo)項(xiàng)目中.

5 總結(jié)與展望

針對(duì)目前設(shè)計(jì)模式檢測(cè)方法的研究中存在的若干問題,本文提出了一種基于機(jī)器學(xué)習(xí)的設(shè)計(jì)模式檢測(cè)方法.首先,針對(duì)模式實(shí)例變體檢測(cè)效果不理想的問題,本文利用面向?qū)ο蠖攘刻卣骱臀⒔Y(jié)構(gòu)特征進(jìn)行基于堆疊泛化的學(xué)習(xí),實(shí)驗(yàn)結(jié)果表明,對(duì)變體的檢測(cè)效果有較大改善;其次,針對(duì)行為型設(shè)計(jì)模式的檢測(cè)復(fù)雜和難以實(shí)現(xiàn)的問題,本文從微結(jié)構(gòu)的角度追蹤行為型設(shè)計(jì)模式的行為特征,對(duì)于觀察者模式,相較于SSA 等經(jīng)典方法取得了更高的F1-Measure值;再次,針對(duì)設(shè)計(jì)模式檢測(cè)中的發(fā)生的組合爆炸問題,本文在考慮設(shè)計(jì)模式繼承層次信息的基礎(chǔ)之上,加入特定的設(shè)計(jì)模式微結(jié)構(gòu)的考量,從而進(jìn)一步縮減了模式的搜索空間.

具體地講,本文采用機(jī)器學(xué)習(xí)的方式分別從度量和微結(jié)構(gòu)兩個(gè)視圖訓(xùn)練分類器,然后采用模型堆疊的方式訓(xùn)練出最終的分類器.在幾個(gè)開源項(xiàng)目上的實(shí)驗(yàn)表明:本文的方法相對(duì)于P-MARt 和SSA 來講,具有更好的模式檢測(cè)效果.

在未來工作中,本文將從如下幾個(gè)方面進(jìn)行改進(jìn)和擴(kuò)展.

(1) 本文應(yīng)用比特向量表示方法類微結(jié)構(gòu)的位置和數(shù)目,并通過比特向量及其位運(yùn)算識(shí)別設(shè)計(jì)模式的方法映射.在未來工作中我們會(huì)將這些位置信息也輸入分類器,更充分地利用微結(jié)構(gòu)的位置信息,從而更加準(zhǔn)確地追蹤設(shè)計(jì)模式的行為特征;

(2) 找到更為廣泛認(rèn)可的設(shè)計(jì)模式實(shí)例庫(kù)作為訓(xùn)練數(shù)據(jù)集的來源,從而提高設(shè)計(jì)模式檢測(cè)的準(zhǔn)確率;

(3) 進(jìn)一步研究將第三方庫(kù)中的有效信息加載到檢測(cè)目標(biāo)項(xiàng)目中的方法并完善度量知識(shí)庫(kù)和微結(jié)構(gòu)知識(shí)庫(kù),從而提高設(shè)計(jì)模式檢測(cè)方法的可用性.