一種基于程序依賴圖的代碼聚類方法

翟 曄, 劉志國, 王春暉

(1.內(nèi)蒙古師范大學(xué) 計算機科學(xué)技術(shù)學(xué)院,內(nèi)蒙古 呼和浩特 010022; 2.內(nèi)蒙古師范大學(xué) 應(yīng)用數(shù)學(xué)中心,內(nèi)蒙古 呼和浩特 010022)

程序設(shè)計的學(xué)習(xí)一直是計算機科學(xué)及相關(guān)專業(yè)學(xué)習(xí)者面臨的重大挑戰(zhàn),學(xué)生程序作業(yè)的批改和反饋需要花費教師大量的時間。隨著MOOC教學(xué)方式在程序設(shè)計類課程的廣泛應(yīng)用,教師為每一位學(xué)生的程序作業(yè)給予及時反饋和答疑幾乎已經(jīng)成為不可能的事情。目前,現(xiàn)有的程序設(shè)計類輔助教學(xué)平臺會根據(jù)測試用例檢查程序的正確性,進而得到程序是否完全通過或部分通過測試的反饋。這些反饋信息對于學(xué)生調(diào)試程序和判斷求解方法的正確性是非常有用的。然而,對于一些學(xué)生(特別是初學(xué)者),他們可能需要一些更細微的引導(dǎo)(如提供標準案例,或者找出錯誤)。

目前的代碼分類方法主要基于代碼相似性檢測技術(shù)。代碼相似度檢測主要集中在兩個方面：文本相似度檢測和程序邏輯相似度檢測。文本相似性將代碼看成文本,一些學(xué)者采用TF-IDF建立文本特征[1-3],也有學(xué)者通過語義詞權(quán)重法對文本進行分類和識別[4-5]。程序邏輯相似性[6]將代碼轉(zhuǎn)化為某種中間表示,然后量化相似性。一些研究者將代碼表達成抽象語法樹(AST)或檢測程序依賴圖(PDG),然后將動態(tài)文本匹配算法與后綴樹算法相結(jié)合,對源文件中的相似代碼進行編碼[7]。有研究者將代碼表示成函數(shù)調(diào)用圖,從函數(shù)級別檢測到源代碼的相似性[8]。還有一些研究[9-10]根據(jù)內(nèi)部操作指令的相似性確定了兩個功能的相似性,并最終獲得了兩個應(yīng)用程序的相似性。

本文提出一種基于程序依賴圖(program dependence graph,PDG)的學(xué)生程序聚類方法。該方法針對求解同一問題的一組程序,表示和識別程序的結(jié)構(gòu)特征,進一步采用聚類算法將求解方案相同的程序聚類,而將求解方案不相同的程序劃分到不同的類。首先采用語法分析和語義分析技術(shù)將學(xué)生C程序代碼轉(zhuǎn)換成程序依賴圖；然后提取結(jié)構(gòu)特征,表達成特征向量；最后采用k-means聚類算法實現(xiàn)基于語義特征的程序聚類。本文針對一個統(tǒng)計求和的編程問題,對38個學(xué)生程序開展實驗研究,結(jié)果表明該分類方法的有效性。

1 相關(guān)工作

1.1 程序依賴圖

程序依賴圖(PDG)一般以表達式語句(計算表達式或謂詞表達式)為節(jié)點,節(jié)點之間的邊代表節(jié)點計算表達所依賴的數(shù)據(jù)關(guān)系(數(shù)據(jù)依賴),或節(jié)點執(zhí)行所依賴的控件關(guān)系(控制依賴)[11]。與其他代碼表達形式(如源碼、AST或控制流圖CFG)相比,程序依賴圖顯示描述了程序語句及其關(guān)系,同時隱去對程序執(zhí)行不產(chǎn)生影響的部分,蘊含了還原程序執(zhí)行過程所必需的信息,具有更強的表達能力[12]。

表1 PDG中節(jié)點類型與對應(yīng)語句Tab.1 Node types and corresponding sentences in PDG

本文程序依賴圖的節(jié)點對應(yīng)到程序中的某個基本語句,如聲明語句、賦值語句等,還包含表達程序入口的入口節(jié)點。程序依賴圖中每個節(jié)點都是有類型的,主要表達函數(shù)粒度的代碼、表達的類型TV見表1。

程序依賴圖中的邊由程序節(jié)點之間的依賴關(guān)系確定。依賴關(guān)系主要有控制依賴與數(shù)據(jù)依賴?？刂埔蕾嚸枋龀绦蛘Z句執(zhí)行過程產(chǎn)生的依賴關(guān)系,數(shù)據(jù)依賴描述程序語句對變量的使用與賦值時產(chǎn)生的數(shù)據(jù)流關(guān)系。

以“統(tǒng)計10以內(nèi)加法”的編程問題為例,圖1展示了其中求解該問題的一個源代碼,該代碼對應(yīng)的程序依賴圖。

圖1 程序依賴圖表示Fig.1 PDG representation

1.2 聚類技術(shù)

聚類是指對于一個給定集合的點(數(shù)據(jù)對象),把它們分成幾個子集,其中每個子集稱為一個組或類簇。一個類簇中的點彼此相似；不同的類簇的點彼此不相似。通常,點處在一個高維空間中,相似性可以使用歐式距離、余弦相似度等方法度量。

聚類方法是一種非監(jiān)督的學(xué)習(xí)算法,不需要對輸入數(shù)據(jù)進行標注。常用的聚類方法有基于劃分的方法、基于層次分析方法、基于密度方法等。基于劃分的方法使用相似度計算方法,將距離近的相似的點聚為一類,而類之間的點都相距較遠,如k-means聚類算法?；趯哟尉垲惖姆椒ㄔ噲D在不同層次對數(shù)據(jù)集進行劃分,從而形成樹型的聚類結(jié)構(gòu),如AGNES聚類算法?；诿芏鹊木垲惙椒僭O(shè)聚類結(jié)構(gòu)可以通過樣本分布的緊密程度確定,如DBSCAN密度聚類算法。

2 基于程序依賴圖的代碼聚類方法

本文以一組解決同一個問題的C程序作為輸入,使用聚類方法將這些程序自動分成若干個子集,每個子集都被認為是語義上相似的代碼。具體包括三個步驟,如圖2所示。

(1) 生成程序依賴圖: 將每個輸入程序代碼分別轉(zhuǎn)換成其對應(yīng)的程序依賴圖表示。

(2) 提取關(guān)鍵特征: 讀取程序依賴圖的語句類型、關(guān)系類型等特征,使用特征向量表示每個程序依賴圖。

(3) 程序聚類: 使用基于k-means的聚類算法,對一組程序聚類,得到k個聚類的子集。

圖2 基于聚類方法的代碼分類Fig.2 Code classification flowchart based on clustering method

2.1 程序依賴圖的自動生成

程序依賴圖用點和邊表達代碼語義。點源自語句,邊源自語句之間的關(guān)系。為得到程序依賴圖,現(xiàn)有方法一般先得到代碼的抽象語法樹,然后進行控制流分析,得到控制流圖(CFG)。隨后,在控制流圖的基礎(chǔ)上,結(jié)合抽象語法樹,進行數(shù)據(jù)流分析,進而得到程序依賴圖[13-14]。主要步驟如下：

(1) 對程序進行預(yù)處理,包括: (a) 對特殊形式的語句(如++,+=)等進行規(guī)范化; (b) 將for循環(huán)等價替換成while循環(huán); (c) 將聲明并賦值的初始化語句拆分為聲明語句和賦值語句; (d) 如果一條聲明語句中同時聲明多個變量,則拆分成每條聲明語句僅聲明一個變量; (e) 去掉注釋和空行。

(2) 對程序代碼進行詞法、語法分析,獲得程序?qū)?yīng)的抽象語法樹。

(3) 在抽象語法樹上,進行控制流分析,獲得程序?qū)?yīng)的控制流圖(CFG)。同時,為每一條程序語句生成一個節(jié)點,這些節(jié)點最終成為程序依賴圖中的節(jié)點。

(4) 在CFG上,進行數(shù)據(jù)流分析。具體通過定義-使用分析與基于程序控制流的到達-定義分析,得到節(jié)點之間的數(shù)據(jù)依賴關(guān)系,將這些數(shù)據(jù)依賴關(guān)系添加到CFG上。

(5) 根據(jù)數(shù)據(jù)流分析結(jié)果,獲得變量定義與使用的關(guān)系,進而得到聲明依賴關(guān)系。

本文基于上述步驟,利用C程序分析的開源工具Pycparse作為詞法分析工具,實現(xiàn)了一個將C語言源程序轉(zhuǎn)換成依賴圖的生成工具,以方便下一步的分類工作。

2.2 程序依賴圖的特征

表2 程序依賴圖特征信息及描述Tab.2 Features and description of PDG

為了得到一組程序依賴圖的分類,具體包括兩個關(guān)鍵問題需要解決,一是特征抽取,二是聚類方法實現(xiàn)。

2.2.1 程序依賴圖特征選取與表示 參考基于Metric克隆代碼檢測方法中對特征的定義[15-16],從PDG中提取表征程序語義信息的特征。具體選取的特征信息見表2。

2.2.2 k-means聚類算法 k-means算法是典型的基于距離的非層次聚類方法,在最小化誤差函數(shù)的基礎(chǔ)上將數(shù)據(jù)劃分為預(yù)定的類數(shù)K,采用距離作為相似性的評價指標,即認為兩個實例的距離越近,其特征相似度就越大[17-18]。

算法輸入為程序依賴圖特征集合C,輸出為簇的集合S。其中集合S={S1,S2,…,Sk},Si集合為第i個簇的集合,其簇心記為Pi。第t次迭代產(chǎn)生的簇的集合記為S(t) (t=0,1,2,…),算法過程如下:

(1) 初始化聚類的集合數(shù)k,并輸入實例個數(shù)n值,輸入程序依賴圖特征集合C。

(2) 隨機選擇初始中心向量Pi,作為每個簇的中心點。

(3) 每個實例特征向量與每個簇的中心點向量計算距離值,并選擇距離最小的分配到相應(yīng)類中。

(4) 根據(jù)上一步的分類結(jié)果,計算對應(yīng)類中的所有向量的平均值,取這個平均值作為簇的新中心點ki。

(5) 反復(fù)執(zhí)行步驟(3)和(4),直到中心點不再發(fā)生改變,聚類完成。

根據(jù)算法的描述,k-means聚類算法的時間復(fù)雜度是O(nkt)。其中n為實例數(shù)量,k為聚類的個數(shù),t是聚類過程迭代執(zhí)行的次數(shù)。

3 實驗與分析

圖3 使用拐點法確定合適的K值Tab.3 Inflection point method to determine the appropriate K value

為驗證分類方法的有效性,從一次學(xué)生C程序作業(yè)提交的源代碼集合中選擇38個程序,這些程序解決同一個編程任務(wù),該編程任務(wù)的描述如下:

給定一個正整數(shù)K,計算一個最小的n,使得當(dāng)n足夠大的時,

Sn=1+1/2+1/3+…+1/n>k。

用本文提出的方法對這38個程序進行聚類。在k-mean算法中,需要設(shè)置參數(shù)k和迭代次數(shù)。將迭代次數(shù)iteration設(shè)為500。從k=2～10作為預(yù)先K值。使用拐點(inflection point)法確定合適的K值。如圖3所示,該問題中,k=5為合適的K值。

為檢查算法自動聚類的效果,用文獻 [19]中提出的基于子類內(nèi)部對(intra pair)的方法計算準確率和召回率。準確率表示算法反饋的正確分類的占比; 召回率表示算法反饋的人工確認正確分類的占比。

(1)

(2)

先對實驗數(shù)據(jù)集中的38個程序進行人工分組。首先將這些程序分成5類,然后對聚類算法當(dāng)k=5時的分類結(jié)果進行分析。結(jié)果發(fā)現(xiàn),在一個聚類子集中有2個程序可以劃分到另外兩個子類中。最后計算準確率和召回率,結(jié)果分別是98%和87%。該結(jié)果表明自動分類算法對該程序代碼集具有較好的分類效果。

4 結(jié)語

程序依賴圖與其他表示程序的方法相比具有更明確的語義特征,是程序精確語義分析與相似性判別的常用方法。對于大量的具有相似語義的程序代碼,根據(jù)程序依賴圖語義進行代碼分類對減少軟件維護代價起重要作用。

本文結(jié)合自動化的程序依賴圖生成、特征提取以及基于k-means的分類方法,對一組存在相似語義的代碼集合進行聚類。結(jié)果表明,該方法能夠?qū)崿F(xiàn)基于程序依賴圖的特征聚類。

程序依賴圖在表達程序語義方法具有明確的信息,本文僅使用了部分特征信息。未來將在特征選取上開展深入研究,同時應(yīng)用在更多數(shù)據(jù)集上,以實現(xiàn)更理想的分類效果。