基于相似度計算的UML圖匹配算法設(shè)計模式檢測技術(shù)研究

魏金津 任女爾 蔡建軍

摘要：現(xiàn)在軟件項目越來越龐大，歷史項目也因文檔缺失，結(jié)構(gòu)不清晰等原因很難被開發(fā)者理解。為了能讓軟件開發(fā)者深入了解系統(tǒng)結(jié)構(gòu)，增強開發(fā)者軟件重構(gòu)、復(fù)用的能力，我們研發(fā)設(shè)計模式檢測技術(shù)并作為插件集成進SonarQube，和代碼質(zhì)量檢測、代碼克隆檢測、解耦檢測等一起作為技術(shù)債務(wù)進行管理，對軟件開發(fā)過程具有重要的工程意義與實踐指導(dǎo)作用。

關(guān)鍵詞：UML圖 圖論；設(shè)計模式檢測；相似度算法

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2018）28-0165-03

1 概述

現(xiàn)在汽車行業(yè)軟件系統(tǒng)越來越復(fù)雜龐大，識別系統(tǒng)所用到的設(shè)計模式對于軟件設(shè)計者理解系統(tǒng)架構(gòu)非常重要，為進一步改進系統(tǒng)結(jié)構(gòu)，軟件復(fù)用提供基礎(chǔ)。普通的設(shè)計模式檢測算法只能識別基本模式而不能識別基本模式上的改進模式，并且系統(tǒng)過于龐大時效率也不高，使用相似度算法可以識別改進模式并且提高效率。

軟件行業(yè)內(nèi)常將Sonar作為技術(shù)債務(wù)【1】管控的主流工具，Sonar插件式模式，方便自身被其他平臺所引入，且有利于擴展第三方插件。我們可以開發(fā)插件對檢測結(jié)果進行再加工處理，除了增強代碼質(zhì)量檢測粒度，還可以在設(shè)計上對代碼進行設(shè)計模式、解耦等檢測。

自動檢測系統(tǒng)設(shè)計模式的過程叫作設(shè)計模式檢測，是從設(shè)計級別檢測軟件質(zhì)量，實現(xiàn)基于Sonar的設(shè)計模式自動檢測技術(shù)，有利于軟件開發(fā)與設(shè)計人員理解系統(tǒng)設(shè)計，指導(dǎo)軟件項目設(shè)計改進。

系統(tǒng)類之間的關(guān)系可以由UML類圖表示，類圖本質(zhì)上是有向圖，可以對應(yīng)到鄰接矩陣。我們基于相似度計算的UML圖匹配算法研發(fā)設(shè)計模式檢測技術(shù)，計算待檢測系統(tǒng)和設(shè)計模式所表示矩陣的相似度，生成檢測到的模式實例的列表。

我們將設(shè)計模式檢測軟件以插件的形式集成到SonarQube中，與其他技術(shù)債務(wù)一起進行掃描，并將實時測試結(jié)果反映給開發(fā)人員，從而提高系統(tǒng)設(shè)計的質(zhì)量。

2 圖論和UML圖

圖（Graph）可以定義為一組稱為頂點（vertex）的對象，由稱為邊（edge）的鏈接所連接。圖幾乎可以用來表現(xiàn)所有類型的結(jié)構(gòu)和系統(tǒng)，從交通、通信網(wǎng)絡(luò)，社交、生物網(wǎng)絡(luò)到計算機科學(xué)中都有廣闊的用武之地。

圖論（Graph Theory）【2】是數(shù)學(xué)的一個分支，主要研究圖的屬性，對圖形屬性的研究對于理解底層軟件系統(tǒng)的特性在許多方面都很有價值。

面向?qū)ο笙到y(tǒng)使用類作為模塊分析，設(shè)計和實現(xiàn)系統(tǒng)，其體系結(jié)構(gòu)可以由一個或多個UML圖所表示。

UML（Unified Model Language） 【3】，中文叫作統(tǒng)一建模語言，可以用來對面向?qū)ο笙到y(tǒng)進行可視化的說明、描述。包括用例圖、類圖、對象圖、序列圖、協(xié)作圖等等，其中最常見的是類圖，UML類圖不僅可以對系統(tǒng)中所有類的屬性和方法進行描述，最重要的是能描述類之間的關(guān)系，常見的有依賴、泛化、關(guān)聯(lián)、聚合、組合、實現(xiàn)等關(guān)系。

UML類圖可以完美地映射到圖論的圖，圖的頂點（vertice）代表類，邊（edge）可以對應(yīng)到關(guān)聯(lián)、泛化、組合等UML類圖關(guān)系。

有向圖G=（V， E）可以表示面向?qū)ο笙到y(tǒng)的類圖，頂點集（V）對應(yīng)于系統(tǒng)中的所有類集合，邊集（E）對應(yīng)于這些類之間關(guān)系的集合，比如有向邊（p， q）∈E表示類p與q的關(guān)聯(lián)關(guān)系方向是從p到q。類的所有關(guān)系（包括泛化、關(guān)聯(lián)、組合）都可以表示成類圖，下圖是張簡單的類圖：

我們可以用矩陣來完全地描述任何有向圖，這就是有向圖的鄰接矩陣，如下圖：

3 設(shè)計模式檢測

設(shè)計模式（Design Pattern）是特定情境下特定問題的一般解決方案。使用設(shè)計模式，可以建立一個結(jié)構(gòu)良好、可維護和可重用的軟件系統(tǒng)。現(xiàn)在汽車行業(yè)的軟件系統(tǒng)架構(gòu)非常復(fù)雜并且包含大量的組件，歷史項目也因文檔不齊以及結(jié)構(gòu)不清晰等問題，很難理解這些系統(tǒng)的軟件結(jié)構(gòu)。設(shè)計模式檢測【4】有益于理解這些系統(tǒng)的設(shè)計，并為進一步的改進提供基礎(chǔ)。

在設(shè)計模式檢測之前，我們需要對待檢測系統(tǒng)和設(shè)計模式結(jié)構(gòu)進行建模，因為類圖是一種可以被完美映射到矩陣的有向圖，并且對矩陣的操縱也很容易，所以我們選擇矩陣對面向?qū)ο笤O(shè)計的類之間的關(guān)系進行建模。

GoF提出了23種經(jīng)典的設(shè)計模式，如觀察者模式，代理模式，單例模式，抽象工廠模式等等，這些基本設(shè)計模式都有其基本結(jié)構(gòu)，但是在實際軟件開發(fā)中，設(shè)計模式并不經(jīng)常遵循于基本結(jié)構(gòu)（有時還會定義自己的設(shè)計模式），可以稱為改進型設(shè)計模式。所以我們引入基于相似度計算的UML圖匹配算法（Graph Similarity Algorithm），將待檢測系統(tǒng)和模式圖作為輸入以計算其鄰接矩陣的相似度得分。這種方式的主要優(yōu)勢是不僅能檢測基本設(shè)計模式還能檢測在基本設(shè)計模式上改進過的設(shè)計模式。

要表示的系統(tǒng)實體的關(guān)系或?qū)傩匀Q于設(shè)計者想檢測的模式的具體特征，我們想表示的有關(guān)聯(lián)，泛化，抽象類，抽象方法調(diào)用，對象創(chuàng)建。然而相似度算法并不取決于所使用的特定類型的矩陣，只要能將系統(tǒng)或模式描述為矩陣設(shè)計者可以將輸入?yún)?shù)設(shè)為任何類型。

我們使用Java語言開發(fā)了一個檢測程序，使用前需要選擇待檢測系統(tǒng)的classes文件根路徑和待檢測的設(shè)計模式，便可自動化的使用上面提到的設(shè)計模式檢測算法（下面會說明），生成檢測到的模式實例的列表。該檢測程序以Sonar插件形式開發(fā)并集成進SonarQube和代碼質(zhì)量、代碼克隆等技術(shù)債務(wù)一起進行掃描檢測。

4 計算兩圖之間的相似度算法

1）兩個有向圖GA和GB分別具有NA和NB頂點，GA描述設(shè)計模式，GB描述系統(tǒng)。定義相似度矩陣S為一個NB*NA矩陣。S的每個元素s（i，j）表示的是GB中頂點i和GA中頂點j的相似度。

2）計算S的算法公式如下：

（1） 設(shè)Z0為一個元素均為1的NB*NA矩陣。

（2） 迭代：[Ζk+1=BZkAT+BTZkA∥BZkAT+BTZkA∥1]

其中，有向圖GA、GB的鄰接矩陣表示為A、B；分母表示矩陣的1-范式（矩陣的1范數(shù)，即：矩陣的每一列上的元素絕對值先求和，再從中取個最大的，（列和最大））；迭代的終止條件是矩陣Z收斂。[knAnBeAnA+eBnB]

3）算法復(fù)雜度：ea、eb代表的是有向圖的邊的數(shù)量。

4）選擇該算法的原因：在設(shè)計模式檢測的情景下，這個圖相似度計算算法，可以用來檢測圖GA和圖GB的頂點之間的相似度。為了保證最后檢測結(jié)果的準確性，最后將矩陣歸一化來表示相似度（相似度取值范圍[0，1]）。

5 圖匹配算法

精確圖匹配算法（Exact Graph Matching Algorithm）：該算法就是尋找同構(gòu)圖，即具有相同節(jié)點數(shù)，相關(guān)邊緣也要一一對應(yīng)的圖。兩個同構(gòu)的圖其鄰接矩陣也相同。運用設(shè)計模式檢測，就是檢測系統(tǒng)圖的所有和待檢測模式具有相同數(shù)量頂點的子圖。這是理想狀態(tài)下的算法，在實際軟件開發(fā)中，完全復(fù)制設(shè)計模式是不現(xiàn)實的，總要根據(jù)實際情況來進行修改適應(yīng)，所以精確圖匹配算法在設(shè)計模式檢測領(lǐng)域并不適用。

非精確圖匹配算法（Inexact Graph Matching Algorithm）：當(dāng)無法找到兩個圖之間的同構(gòu)時可以應(yīng)用模糊匹配，即非精確圖匹配算法。該算法通過圖的編輯距離來計算圖與圖之間的相似程度。圖的編輯距離，大致可以理解為對匹配圖進行多少次點、邊的操作可以與目標圖一致。在設(shè)計模式匹配場景下，檢測結(jié)果將不準確，如圖4。

SS1明顯是SS3設(shè)計模式的一種變種，但是編輯距離來講，SS2更小。

相似度算法（Similarity Scoring Algorithm）：以上兩種算法都不適用，所以我們使用基于相似度計算的UML圖匹配算法，該算法計算圖的鄰接矩陣的相似度。將UML圖拆分為泛化圖（Generalization Graph）和關(guān)聯(lián)圖（Association Graph），以下簡稱g圖和a圖。g圖表示各類之間的繼承關(guān)系，a圖展示的是各類之間的聚集關(guān)系（如類A中有一個B類的實體，此時，a圖中A指向B）。

首先將上面圖3的UML按照a圖和g圖拆分開來：

然后分別計算出他們的鄰接矩陣：

之后將這個矩陣代入到1中的算法公式中，分別迭代獲得兩個片段的a/g圖對于待測設(shè)計模式的a/g圖的相似度：

[Genpattern，seg1=Similarity（Genpattern，Genseg1）=0.500.50.500.5]

[Assocpattern，seg1=Similarity（Assocpattern，Assocseg1）=100001]

[Genpattern，seg2=Similarity（Genpattern，Genseg2）=1001]

[Assocpattern，seg2=Similarity（Assocpattern，Assocseg2）=0000]

之后分別將每個片段的兩個相似度矩陣進行相加，并且進行歸一化，可以得到最終的相似度矩陣：

[NormScorespattern，seg2=Sumpattern，seg2?1k1001k2=1001?120012=0.5000.5]

[NormScorespattern，seg1=（Genpattern，seg1+Assocpattern，seg1）?1k1001k2=0.7500.250.2500.75]

之后我們可以看到，片段2中a，b兩個類（結(jié)點）和待測設(shè)計模式中的兩個類（結(jié)點）相似度均為0.5，在相對片段1中，A/C兩類的相似性和待測設(shè)計模式的相似性為0.75，所以得出結(jié)論，片段1相比片段2與待測設(shè)計模式的相似度更高。

6 設(shè)計模式檢測算法步驟

1）假設(shè)待檢測系統(tǒng)有數(shù)量為n的類，需要將系統(tǒng)的每個特性（如前文提到的a/g圖等等）都表示為一個獨立的n * n特征描述矩陣。

2）檢測繼承結(jié)構(gòu)。這里將每個繼承結(jié)構(gòu)抽象成一棵樹，特別地，如果某個類有多個父節(jié)點，那么該類會同時出現(xiàn)在多棵樹中，如下圖所示的C，C1，C2既屬于層次結(jié)構(gòu)1，也屬于層次結(jié)構(gòu)2。

3）構(gòu)建子系統(tǒng)矩陣。依據(jù)目標設(shè)計模式來劃分子系統(tǒng)，如果目標設(shè)計模式有且僅有單。

獨的繼承樹，那么步驟2中劃分出來的每一棵繼承樹都被視為一個子系統(tǒng)。如果目標設(shè)計模式有多棵繼承樹組成，那么子系統(tǒng)將是步驟2中劃分出來的繼承樹的組合數(shù)。如：某設(shè)計模式有2棵繼承樹，待測項目供有m棵繼承樹，那么子系統(tǒng)的數(shù)量就是m（m-1）/2。

4）相似度算法的計算。此處計算每個子系統(tǒng)矩陣與待測設(shè)計模式的相似度，大致計算過程在第4節(jié)有描述，不再贅述。

5）降序排序相似度計算結(jié)果。每一個待測設(shè)計模式都會得到一個列表，根據(jù)這個列表里得分最高的類來提取設(shè)計模式檢測結(jié)果。

6）閾值選取問題。選取有一個假設(shè)：給定一個設(shè)計模式的實例，那么這個實例里，經(jīng)過修改的特征不會超過一個。所以假設(shè)某設(shè)計模式有x個特征，閾值就為（x-1）/x。

7 檢測結(jié)果

8 總結(jié)

基于相似度計算的UML圖匹配算法比傳統(tǒng)圖匹配算法的設(shè)計模式檢測效果更好，效率更高。使用該算法開發(fā)設(shè)計模式檢測軟件，可以作為插件集成進SonarQube，和其他技術(shù)債務(wù)一起掃描。開發(fā)者根據(jù)掃描結(jié)果識別到系統(tǒng)哪些地方運用了設(shè)計模式，可以更好地理解系統(tǒng)結(jié)構(gòu)，并對系統(tǒng)進行優(yōu)化和重構(gòu)，提高汽車行業(yè)軟件系統(tǒng)架構(gòu)的質(zhì)量。

參考文獻：

[1] 劉亞珺，李兵，李增揚，等.吳閩泉軟件集成開發(fā)環(huán)境的技術(shù)債務(wù)管理研究[J].計算機科學(xué)，2017，44（11）：15-21.

[2] 程彩鳳，林德樹.數(shù)據(jù)結(jié)構(gòu)中圖論算法動態(tài)智能演示的研究[J].現(xiàn)代電子技術(shù)，2017，40（18）：40-42.

[3] 傅明麗.UML建模技術(shù)在軟件開發(fā)中的應(yīng)用[J].科技展望，2015（18）.

[4] 肖卓宇，黎妍，何锫，等.基于矩陣積分評估的設(shè)計模式檢測研究[J].小型微型計算機系統(tǒng)，2016（7）：1428-1433.

【通聯(lián)編輯：朱寶貴】