翟 曄, 劉志國, 王春暉

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

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

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

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

1 相關(guān)工作

1.1 程序依賴圖

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

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

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

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

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

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

1.2 聚類技術(shù)

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

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

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

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

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

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

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

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

2.1 程序依賴圖的自動(dòng)生成

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

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

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

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

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

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

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

2.2 程序依賴圖的特征

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

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

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

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

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

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

(2) 隨機(jī)選擇初始中心向量Pi,作為每個(gè)簇的中心點(diǎn)。

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

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

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

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

3 實(shí)驗(yàn)與分析

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

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

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

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

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

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

(1)

(2)

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

4 結(jié)語

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

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

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