C程序代碼結(jié)構(gòu)自動審查方法研究

張曉欣， 孫偉杰

（中國人民解放軍61081部隊，北京 100094）

0 引言

自從1976年Michael Fagan首次提出代碼審查（Code Inspection）以來，代碼審查一直被認為是一種重要而且有效的改進軟件質(zhì)量的方法。經(jīng)驗表明，代碼審查能發(fā)現(xiàn)軟件中 30%～70%的設(shè)計和編碼缺陷[1]。但隨著軟件規(guī)模的不斷增大，人工代碼審查耗時、成本巨大且需要知識和經(jīng)驗積累的問題也越來越引起人們的關(guān)注。因此，人們開始研究自動代碼審查技術(shù)，開發(fā)相應(yīng)的工具支持代碼審查，以提高審查效率和準確性。

自動化代碼審查技術(shù)主要通過利用計算機實現(xiàn)對源代碼的靜態(tài)分析，找出代碼中潛在的代碼缺陷，為代碼審查中討論和確定這個缺陷提供依據(jù)。因此，自動化代碼審查技術(shù)為顯著提高軟件質(zhì)量和可維護性提供了有力的支持。

1 目前的研究現(xiàn)狀

目前的代碼審查工具對程序結(jié)構(gòu)的審查，其審查對象主要為函數(shù)調(diào)用圖、數(shù)據(jù)流圖等，其審查目的主要是對程序結(jié)構(gòu)的度量，如計算程序的圈復(fù)雜度量[2]值是否過大、結(jié)構(gòu)復(fù)雜性度量和 halstead方法[3]度量值等是否顯著偏離合理范圍。

上述方法一定程度上忽視了程序是否符合設(shè)計的功能模塊劃分，程序結(jié)構(gòu)是否合理的檢驗。特別是一些遺留系統(tǒng)，要么缺少設(shè)計文檔，要么由于代碼的持續(xù)演化導(dǎo)致其已經(jīng)明顯偏離原設(shè)計等，因此很難準確有效的幫助測試人員進行軟件結(jié)構(gòu)的審查。

因此，代碼結(jié)構(gòu)自動審查技術(shù)主要是對文件的組織形式進行審查，目的是通過對源碼的靜態(tài)分析，分析程序的邏輯聯(lián)接關(guān)系和語義相似度關(guān)系，提取程序的合理模塊劃分，通過與設(shè)計文檔的比較，判斷程序的結(jié)構(gòu)是否合理。

2 C語言程序結(jié)構(gòu)基本規(guī)則的研究

對于所有程序（除了最小的程序）來說，將整個程序都置于單個文件中既不明智也不實用。首先，每次修改了程序的任何一部分，都必須重新編譯整個程序。其次，不能在另一個程序中重用這個程序的任何一部分，除非把源代碼拷貝[4]給另一個文件。第三，這種結(jié)構(gòu)不利于程序的維護。

根據(jù)編程實踐中提出的合理組織方式的基礎(chǔ)上，總結(jié)出一些程序結(jié)構(gòu)應(yīng)該遵循的基本原則：

1）主程序文件：通常為主函數(shù)單獨建立一個文件，其中也可以包含少數(shù)與之關(guān)系密切的公共變量的定義和被主函數(shù)調(diào)用的函數(shù)。

2）對于全局變量和用戶定義類型，應(yīng)根據(jù)誰用誰管的歸屬原則，分別在不同的源文件里定義。

3）考慮把程序所需的功能劃分為若干部分，每部分中定義的程序?qū)嶓w互相之間應(yīng)有較密切的邏輯聯(lián)系，這樣形成一種整體性，可以考慮放在一起建立一個程序文件。

4）一個設(shè)計適當?shù)墓δ軇澐挚梢宰鳛橐粋€單一的單位從系統(tǒng)中提出來，不必重寫任何代碼就可以在另一個系統(tǒng)中有效地重用。

5）公共程序?qū)嶓w，即在程序中可被廣泛使用的程序?qū)嶓w（數(shù)據(jù)結(jié)構(gòu)、公共函數(shù)等），這些實體的特點是程序中被眾多的其它實體使用，因此與程序中不同模塊的實體之間都有著比較密切的關(guān)聯(lián)。這些公共實體應(yīng)當被單獨劃分為公共模塊。

6）程序中變量、函數(shù)的命名應(yīng)符合命名規(guī)范，且使用能夠清楚說明其功能的詞匯（單詞或詞組）或適當?shù)目s寫。

3 C程序代碼結(jié)構(gòu)自動審查方法研究

自動化代碼結(jié)構(gòu)審查技術(shù)主要通過靜態(tài)分析的方法對被審查程序的源代碼進行結(jié)構(gòu)分析[5]，提取程序?qū)嶓w間邏輯聯(lián)接關(guān)系和語義相似度關(guān)系，通過聚類的方法根據(jù)程序高內(nèi)聚、低耦合的原則提取出程序組織，與被審查程序文件組織結(jié)構(gòu)的比對，為被審查程序的重組提供依據(jù)，從而提高代碼的維護性和可讀性，并且方便代碼的復(fù)用。

3.1 程序?qū)嶓w間邏輯聯(lián)接關(guān)系的研究

在程序中，函數(shù)、用戶自定義結(jié)構(gòu)類型及全局變量這3種程序?qū)嶓w之間的邏輯連接關(guān)系可歸納為如圖1所示關(guān)系。

圖1 程序?qū)嶓w間邏輯關(guān)系

（1）函數(shù)間關(guān)系

calls：一個函數(shù)調(diào)用另外一個函數(shù)。

（2）用戶自定義結(jié)構(gòu)類型間關(guān)系

is-part-of-utype：一個typedef struct用于另外一個typedef struct的定義中，如：

（3）函數(shù)與全局變量間關(guān)系

actual-parameter：全局變量作為函數(shù)的實際參數(shù)使用。

var-access：函數(shù)訪問全局變量：函數(shù)賦予全局變量一個新值，或函數(shù)讀取全局變量數(shù)值，或函數(shù)使用全局變量地址。

（4）用戶自定義結(jié)構(gòu)類型與全局變量間關(guān)系

var-of-utype：全局變量被聲明為用戶自定義結(jié)構(gòu)類型。

（5）函數(shù)與用戶自定義結(jié)構(gòu)類型間關(guān)系

return-utype：函數(shù)的返回值類型為用戶自定義結(jié)構(gòu)類型。

access-fields：函數(shù)訪問由用戶自定義結(jié)構(gòu)類型聲明的變量，以“.”或“->”的方式進行訪問。

local-var-of-utype：函數(shù)中的局部變量由用戶自定義結(jié)構(gòu)類型聲明。

parameter-of-utype：函數(shù)聲明列表中的形參由用戶自定義結(jié)構(gòu)類型聲明。

上述5類9種連接關(guān)系基本上反映了函數(shù)、用戶自定義結(jié)構(gòu)類型及全局變量3種程序?qū)嶓w之間的邏輯連接關(guān)系，通過靜態(tài)分析得到這3種程序?qū)嶓w的各體及其相互間邏輯關(guān)系，為邏輯連接關(guān)系度量提供了基礎(chǔ)。

3.2 程序?qū)嶓w間語義相似度度量算法

程序中變量、函數(shù)的命名應(yīng)符合命名規(guī)則，并在在一定程度上說明該變量或函數(shù)所能完成的功能。因此，規(guī)范的變量、函數(shù)命名包含豐富的語義信息，針對語義信息的相似度度量有助于對程序劃分的提取工作。

但是，要獲取程序?qū)嶓w名字之間的語義相似性，并據(jù)此來發(fā)現(xiàn)元素之間的聚類關(guān)系，必須采用適當?shù)姆椒▉硗瓿沙绦驅(qū)嶓w名稱之間的語義相似度度量。

目前較為常用的字符串間相似度度量算法包括：

（1）編輯距離

俄國科學(xué)家 Vladimir Levenshtein提出的編輯距離方法可以用來判斷字符串的相似度。編輯距離，又稱Levenshtein距離，是指兩個字串之間，由一個轉(zhuǎn)成另一個所需的最少編輯操作次數(shù)。編輯距離法允許的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。試驗證明，兩個字符串間的編輯距離越小，則其相似度越高。

（2）最長公共子串

最長公共子串(LCS，Longest Common Subsequence)方法可以用來計算字符串之間的相似度。LCS的解法是用一個矩陣來記錄兩個字符串中所有位置上的兩個字符之間的匹配情況，若是匹配則為1，否則為0。然后求出對角線最長的“1序列”，其對應(yīng)的位置就是最長匹配子串的位置。試驗證明，兩個字符串間的最長公共子串越長，則其相似度越高。究其原因，主要是由于變量、函數(shù)的命名通常是由有意義的英文單詞或獨立或聯(lián)合構(gòu)成，其相似性更加適合使用最長公共子串法來進行計算。

3.3 C程序代碼結(jié)構(gòu)自動審查方法

4 結(jié)語

通過對程序結(jié)構(gòu)審查方式的研究，對C程序組織結(jié)構(gòu)的基本規(guī)則進行了總結(jié)，研究了C程序?qū)嶓w之間的邏輯聯(lián)接關(guān)系，并對實體之間的語義相似度的度量方式進行了闡述，提出了聯(lián)合邏輯連接關(guān)系度量和語義相似度度量的程序代碼結(jié)構(gòu)自動審查方法，用于完成代碼結(jié)構(gòu)的檢測。

在對于語義相似度度量采用最長公共子串算法后，取得了一定效果[8]，但當變量名稱由多個單詞構(gòu)成時，如sendheartbeatmsg和sendswitchmsg時，由于send和msg之間包含信息不同而效果不佳，如能采用分詞技術(shù)，通過對于變量名分詞再進行相似度度量，其度量效果應(yīng)更好。

[1]周濤.航天型號軟件測試[M].北京:宇航出版社,1999.

[2]KAN S H.軟件質(zhì)量工程的度量與模型[M].吳明暉,應(yīng)晶,譯.北京:電子工業(yè)出版社,2004:54-223.

[3]PRESSMNA R S.Sowtfaer Engineering a Pacrtitioner’s Apporach[M].北京:清華大學(xué)出版社,2006:429-454

[4]陳志云,薛質(zhì).基于Win32 API調(diào)用監(jiān)控的惡意代碼檢測技術(shù)研究[J].信息安全與通信保密,2009(07):73-75.

[5]孫莉.基于構(gòu)件的軟件測試中測試用例分配優(yōu)化研究[J].通信技術(shù),2008,41(10):193-195.

[6]李琴,曾凡平,王立民.程序的分層靜態(tài)分析模型HSAM[J].信息安全與通信保密,2007(02):73-74,77.

[7]喬勇誠.探討軟件測試“誤區(qū)”[J].通信技術(shù),2011,44(08):149-151.

[8]曾曦,陳軍.下一代網(wǎng)絡(luò)軟件技術(shù)的發(fā)展趨勢[J].通信技術(shù),2007,40(11):223-224,232.