基于函數(shù)調(diào)用序列模式和函數(shù)調(diào)用圖的程序缺陷檢測方法*

崔展齊

(北京信息科技大學(xué) 計算機學(xué)院，北京 100101)

程序中通常會隱含大量編程規(guī)則，由于受到開發(fā)時間和進(jìn)度的限制，且此類規(guī)則數(shù)量眾多，軟件工程師很少使用規(guī)范的文檔來描述這些規(guī)則.部分編程規(guī)則隱藏較深，軟件工程師甚至并未意識到其存在，采用傳統(tǒng)的代碼評審方法不能發(fā)現(xiàn)違反此類規(guī)則的缺陷.若程序員在編程過程中忽視或違反這些規(guī)則，則有可能會引發(fā)軟件缺陷.軟件缺陷挖掘是自動識別程序隱含規(guī)則的有效手段，其通過分析軟件代碼、文檔等相關(guān)數(shù)據(jù)，以識別隱含的缺陷模式或編程規(guī)則，并據(jù)此來自動發(fā)現(xiàn)軟件缺陷[1].軟件缺陷挖掘能有效檢測程序缺陷，且能在很大程度上實現(xiàn)自動化，人力成本開銷較小[2-6].我們在此前的工作中，在一組開源項目上進(jìn)行了實驗，結(jié)果表明通過函數(shù)調(diào)用序列模式挖掘能有效發(fā)現(xiàn)程序中的相關(guān)缺陷，并降低誤報的疑似缺陷數(shù)[7].

然而，現(xiàn)有技術(shù)方案仍存在誤報率較高，待檢測疑似缺陷數(shù)量較大的問題.通常情況下，使用數(shù)據(jù)挖掘技術(shù)識別出的隱式編程規(guī)則數(shù)量比較多，導(dǎo)致所檢測出的違反隱式編程規(guī)則的疑似缺陷數(shù)量更大.對疑似缺陷進(jìn)行確認(rèn)通常需要工程師在理解相關(guān)代碼片段的基礎(chǔ)上，根據(jù)自身經(jīng)驗和專業(yè)能力進(jìn)行判斷，極有可能引入誤判，且難以自動化.人工確認(rèn)疑似缺陷過程枯燥且需要耗費大量時間和精力.例如，在我們此前的工作中，僅對內(nèi)存數(shù)據(jù)庫Redis的源程序進(jìn)行挖掘，就發(fā)現(xiàn)了8條函數(shù)調(diào)用序列模式和16個疑似缺陷.然而，經(jīng)人工確認(rèn)之后，其中僅有1個是確認(rèn)的缺陷.

通過分析發(fā)現(xiàn)，在之前的工作中，只使用了函數(shù)內(nèi)部的路徑，缺少函數(shù)調(diào)用關(guān)系的全局信息，導(dǎo)致產(chǎn)生大量誤報疑似缺陷.例如，根據(jù)挖掘Redis源程序發(fā)現(xiàn)的序列模式，檢測到hashTypeInitIterator()方法中只調(diào)用了dictGetIterator()方法，未調(diào)用dictReleaseIterator()方法，因此將其作為一個疑似缺陷報告.我們對源程序進(jìn)行分析發(fā)現(xiàn)，hashTypeInitIterator()僅在hashTypeConvertZiplist()和genericHgetallCommand()兩個方法中被調(diào)用，每次調(diào)用之后都會調(diào)用hashTypeReleaseIterator()方法，而在hashTypeReleaseIterator()方法中即調(diào)用了dictReleaseIterator().因此，上述疑似缺陷為誤報，誤報產(chǎn)生的原因是未能有效利用函數(shù)調(diào)用關(guān)系全局信息.

1 基于函數(shù)調(diào)用序列模式和函數(shù)調(diào)用圖的缺陷檢測方法

針對上述問題，本文提出了一種基于函數(shù)調(diào)用序列模式和函數(shù)調(diào)用圖的缺陷檢測方法.首先，通過文獻(xiàn)[7]提出的方法，挖掘過程內(nèi)函數(shù)調(diào)用序列集，獲取程序中隱含的函數(shù)調(diào)用序列模式；然后，通過分析待檢測程序，生成過程間函數(shù)調(diào)用圖；最后，結(jié)合函數(shù)調(diào)用序列模式和函數(shù)調(diào)用圖，檢測程序中違反序列模式的疑似缺陷.方法框架如圖1所示.

1.1 函數(shù)調(diào)用序列模式挖掘

函數(shù)定義體中一般會包含多處函數(shù)調(diào)用語句，在PR-Miner[3]等方法中，通常將一個函數(shù)內(nèi)的函數(shù)調(diào)用語句作為一個事務(wù)，在程序所有函數(shù)定義所組成的事務(wù)集上使用頻繁項集挖掘算法[8-10]進(jìn)行挖掘，以找出函數(shù)調(diào)用關(guān)聯(lián)規(guī)則，再用于檢測違反關(guān)聯(lián)規(guī)則的疑似缺陷.這類方法在挖掘過程中忽視了程序中函數(shù)調(diào)用的先后順序信息，導(dǎo)致缺陷檢測的精度降低.

針對這一問題，我們在文獻(xiàn)[7]中提出了基于函數(shù)調(diào)用序列模式挖掘的缺陷檢測方法.序列模式挖掘是一種常用的數(shù)據(jù)挖掘方法[11]，文獻(xiàn)[7]中采用了GSP算法[12].該方法的詳細(xì)過程，在此不再贅述，僅給出幾個后續(xù)步驟要使用的概念.

在函數(shù)調(diào)用序列模式挖掘中，待檢測程序中每條程序調(diào)用語句即為項，若干項組成的集合為項集，序列則是若干項集組成的有序列表.序列的長度指序列中包含項集的個數(shù)，長度為K的序列記為K-序列.如果序列t中每個項集都是序列s中一個項集的子集，則稱t是s的子序列，或稱s包含t.一個序列s的支持度計數(shù)(supCount)是指在整個序列數(shù)據(jù)集中包含s的序列個數(shù)，給定一個最小支持度閾值minSupCount，如果序列s的支持度計數(shù)不小于minSupCount，則稱序列s為序列數(shù)據(jù)集中的頻繁序列或序列模式.不采用支持度低于minSupCount的序列模式，即不關(guān)注在函數(shù)調(diào)用序列集中出現(xiàn)次數(shù)過少的序列模式.此外，GSP算法中還增加了最小/最大時間約束(minGap/maxGap)，兩個事件的間隔不大于maxGap且不小于minGap，才被認(rèn)為在同一個序列中.在函數(shù)調(diào)用序列模式挖掘中，當(dāng)兩個函數(shù)調(diào)用語句間隔較遠(yuǎn)時，其存在調(diào)用模式的可能性也較低.

挖掘函數(shù)調(diào)用序列模式，即根據(jù)minSupCount和maxGap對函數(shù)調(diào)用序列模式進(jìn)行篩選，找出所有序列模式集合FS的過程.

1.2 函數(shù)調(diào)用圖

分析上述函數(shù)調(diào)用序列模式挖掘過程發(fā)現(xiàn)，每一條函數(shù)調(diào)用序列均來自于一個函數(shù)定義內(nèi)部.因此，只使用了過程內(nèi)函數(shù)調(diào)用信息，缺少過程間函數(shù)調(diào)用的上下文信息.

為保存函數(shù)間相互調(diào)用的邏輯關(guān)系，本文使用了過程間函數(shù)調(diào)用圖.將過程間函數(shù)調(diào)用圖定義如下：

定義1過程間函數(shù)調(diào)用圖(inter-procedural function call graph，IFCG)是一個2元組(N,E)，其中：N={n1,n2, …,ni}，是一個有窮的節(jié)點集合，其中n∈N是一個函數(shù)定義；E={e1,e2, …,ej}，是一個有窮的有向邊集合，(nl,nm)?(N×N)表示函數(shù)nl中對函數(shù)nm進(jìn)行了調(diào)用.

算法1生成過程間函數(shù)調(diào)用圖

1 輸入: 程序P={fd1,fd2, …,fdn}

2 輸出: 過程間函數(shù)調(diào)用圖(IFCG)

3 方法: GenerateIFCG(P,IFCG)

4 forfdiinP//遍歷P中的所有函數(shù)定義fdi

5ni=new node(fdi,FCi)//為fdi建立一個節(jié)點

6 IFCG.N.Push(ni)//將創(chuàng)建節(jié)點加入N

7 forniin IFCG.N//遍歷N所有節(jié)點

8 forfcjinni.FC//遍歷所有函數(shù)調(diào)用語句

9 獲取fcj的函數(shù)定義對應(yīng)的結(jié)點nj

10 if edge(ni,nj) not inE//E中沒有對應(yīng)邊

11eij=new edge(ni,nj)//建立一條邊

12 IFCG.E.Push(eij)

13 return IFCG

Caller和Callee分別是獲取指定節(jié)點的調(diào)用函數(shù)和被調(diào)用函數(shù)的兩個函數(shù)，對每個元素n∈N，Caller(n)={nk|nk∈N∧(nk,n)∈E}，Callee(n)={nk|nk∈N∧(n,nk)∈E}.

算法1為過程間函數(shù)調(diào)用圖的生成過程.算法輸入程序P由n個函數(shù)定義組成，表示為集合P={fd1,fd2, …,fdn}，其中，一個函數(shù)定義fdi中包含的函數(shù)調(diào)用所組成的序列為FCi=.算法輸出為程序的過程間函數(shù)調(diào)用圖(IFCG)=(N,E)，N為節(jié)點集合，節(jié)點ni=(fdi,FCi)，E為邊集合，邊eij=(ni,nj).算法首先遍歷P中的所有函數(shù)定義fdi，為每個函數(shù)定義建立一個節(jié)點ni，并將其加入N；然后遍歷N中所有節(jié)點ni，再嵌套遍歷ni.FCi中包含的調(diào)用語句序列，對于FCi中的每個fcj，獲取fcj的函數(shù)定義對應(yīng)的結(jié)點nj，檢查是否存在從ni指向nj的一條邊，若不存在，則建立一條邊eij，并將其加入E.

1.3 缺陷檢測

在生成序列模式集合FS和函數(shù)調(diào)用圖后，需要對源程序進(jìn)行分析，以檢測疑似缺陷，即程序中函數(shù)調(diào)用方式違反函數(shù)調(diào)用序列模式的位置.對長度為k的函數(shù)調(diào)用序列模式α=，支持計數(shù)supCount(α)為FS中包含α的所有序列的計數(shù).這種計算方式只考慮了在一個函數(shù)體內(nèi)部的函數(shù)調(diào)用語句.為利用函數(shù)調(diào)用圖中的上下文關(guān)系信息，將支持計數(shù)計算擴展為supCount(α,d)，其中，d表示函數(shù)調(diào)用序列向上和向下擴展的層數(shù)，supCount(α,d)為將FS中的序列擴展d層之后，包含α的所有序列的計數(shù).α的最大前綴為長度為k-1的序列β=，若函數(shù)定義fdi對應(yīng)的函數(shù)調(diào)用序列FCi在擴展d層后，包含β，但不包含α，則稱fdi存在違反序列模式α的函數(shù)定義，懷疑度(suspicious)定義為：

通常情況下，可以認(rèn)為程序員只是偶爾會犯錯，程序中大多數(shù)函數(shù)調(diào)用順序是正確的，因此，只將懷疑度超過最小懷疑度(minSus)的缺陷作為疑似缺陷報告.

為檢測疑似缺陷，可對源程序P進(jìn)行掃描，逐條檢查是否存在違反集合FS中序列模式的函數(shù)定義.

算法2 疑似缺陷檢測1234567891011121314151617181920輸入：序列模式集合FS，過程間函數(shù)調(diào)用圖IFCG，擴展層數(shù)d輸出：疑似缺陷列表(bugList)方法：FindBugs(FS，IFCG，d)forfcsiinFS//遍歷序列模式集合 βi=fcsi的最大前綴 forniinIFCG．N//遍歷所有函數(shù)序列 if(ni．FCi包含βi) supCount＿βi++//βi支持度遞增if(Contain(ni，fcsi，d)==true) supCount＿fcsi++//fcsi支持度遞增else//加入疑似bug臨時列表 tempbugList．a(chǎn)dd(fdi) //若懷疑度大于最小懷疑度 if(minSus

算法3 基于函數(shù)調(diào)用圖的函數(shù)調(diào)用序列匹配檢測12345678910輸入：初始節(jié)點n，函數(shù)調(diào)用序列fcs，擴展層數(shù)d輸出：是否包含函數(shù)調(diào)用序列方法：Contain(n，fcs，d)N=upTraverse({n}，d)N=downTraverse(N，d)foreachninN if(n．FC包含fcs) returnfalsereturntrue11121314151617181920212223242526272829方法：upTraverse(N，d)//向上擴展N’=NforeachninNi=dwhile(i--大于0)N’．remove(n)foreachniinCaller(n)將ni中調(diào)用n后的子序列拼接到n．FC后N’．a(chǎn)dd(n．FC)N’=upTraverse(N’，i)returnN’方法：downTraverse(N，d)//向下擴展while(i--大于0)foreachninNfornjinn．FCtempFC=nullfornkinCallee(nj)tempFC．a(chǎn)ppend(nk．FCk)將nj替換為tempFCreturnN

算法2為疑似缺陷檢測過程.算法輸入為序列模式集合FS, 過程間函數(shù)調(diào)用圖為IFCG，擴展層數(shù)為d，算法的輸出疑似缺陷列表為bugList.第6～19行為對序列模式集合FS逐條遍歷.首先，獲取序列模式fcsi的前綴βi，并在第8～14行中使用過程間函數(shù)調(diào)用圖對程序進(jìn)行遍歷，將檢測到違反序列模式的疑似缺陷加入臨時缺陷列表中.然后在遍歷完整個程序后，將計算出的序列模式fcsi懷疑度與最小懷疑度(minSus)進(jìn)行比較，若大于(minSus)且小于1，則將臨時缺陷列表加入缺陷列表中.最后在完成程序掃描后，第20行返回疑似缺陷列表.

算法2中使用到的函數(shù)調(diào)用序列匹配方法在算法3中描述.第4～10行定義Contain方法，該方法通過upTraverse方法將函數(shù)調(diào)用序列逐層向上擴展，再通過downTraverse方法將函數(shù)調(diào)用序列逐層向下擴展，然后將擴展后的函數(shù)調(diào)用序列與序列模式fcs進(jìn)行比較，并返回比較結(jié)果.向上擴展時，由于函數(shù)可能會在多處被調(diào)用，所以可能會擴展為多個函數(shù)調(diào)用序列，其中任意一個函數(shù)調(diào)用序列不包含指定序列則都將會返回false.

2 實驗與結(jié)果

在上述基于程序調(diào)用序列模式和函數(shù)調(diào)用圖的缺陷檢測方法的基礎(chǔ)上，我們實現(xiàn)了一項原型工具，并進(jìn)行了一組實驗以驗證所提出方法的有效性.實驗平臺為Intel i7 2.3 GHz處理器、8 GB內(nèi)存計算機，軟件環(huán)境為Ubuntu16.04、Python3.4.

2.1 實驗設(shè)計

為合理評估所提出方法的有效性，便于與已有方法進(jìn)行對比，我們使用了文獻(xiàn)[7]的3個開源項目實驗對象，即內(nèi)存數(shù)據(jù)庫Redis，跨平臺腳本語言Lua和嵌入式系統(tǒng)數(shù)據(jù)庫Sqlite.實驗對象基本情況如表1所示.在實驗中，函數(shù)調(diào)用序列模式挖掘算法使用的參數(shù)為：最小支持度0.01，最大時間間隔10.使用函數(shù)調(diào)用圖進(jìn)行缺陷檢測時，所使用最小懷疑度為0.9，擴展層數(shù)為1.

在實驗中，生成的函數(shù)調(diào)用序列經(jīng)預(yù)處理后使用數(shù)據(jù)挖掘工具Rapidminer 7.2.1進(jìn)行序列模式挖掘，再根據(jù)挖掘出的函數(shù)序列模式和生成的全局函數(shù)調(diào)用圖掃描程序，識別出違反函數(shù)調(diào)用序列模式的位置，作為疑似缺陷報告.

表1 實驗對象基本情況[7]

表2 時間開銷統(tǒng)計

2.2 實驗結(jié)果分析

表3 疑似缺陷報告及確認(rèn)情況

表2對兩種方法檢測疑似缺陷的運行時間開銷進(jìn)行了比較.其中，進(jìn)行序列模式挖掘和人工驗證的時間沒有統(tǒng)計在內(nèi).從結(jié)果可以看出，本文所提出方法所需的運行時間大于文獻(xiàn)[7]的方法，3個實驗對象累計耗時1 750.5 ms，比文獻(xiàn)[7]方法累計耗時759.0 ms增加了1.3倍.但是，疑似缺陷檢測是完全自動化的，并不會增加額外的人力成本開銷，而缺陷自動檢測技術(shù)的關(guān)鍵在于盡可能降低人工確認(rèn)疑似缺陷的開銷.

為驗證基于函數(shù)調(diào)用序列模式和函數(shù)調(diào)用圖的缺陷檢測方法減少誤報和發(fā)現(xiàn)缺陷的能力.表3將兩種方法的缺陷檢測及確認(rèn)情況進(jìn)行了統(tǒng)計.我們將缺陷檢測結(jié)果分為：疑似缺陷數(shù)、確認(rèn)缺陷數(shù)和確認(rèn)為誤報的缺陷數(shù)3類.從表3中可以看出，本文所提出方法所報告的疑似缺陷數(shù)明顯減少，有效減少了缺陷誤報，共報告了10個疑似缺陷，與文獻(xiàn)[7]方法報告的26個疑似缺陷相比，減少了61.5%.同時，兩種方法都檢測到了同樣的確認(rèn)缺陷.上述實驗結(jié)果表明，本文所提出方法報告疑似缺陷數(shù)明顯減少，且能與文獻(xiàn)[7]中的方法發(fā)現(xiàn)同樣多的真實缺陷.因此，該方法將能有效降低疑似缺陷的人工確認(rèn)開銷.

3 結(jié) 論

針對現(xiàn)有的基于函數(shù)調(diào)用序列模式挖掘的缺陷檢測方法所檢測出的疑似缺陷數(shù)量較大，對疑似缺陷進(jìn)行人工確認(rèn)需要耗費大量時間和精力，且極有可能引入誤判的問題，本文提出通過使用函數(shù)調(diào)用圖，充分利用函數(shù)調(diào)用上下文信息，對疑似缺陷進(jìn)行自動過濾.實驗結(jié)果表明，在不影響缺陷檢測率的前提下，該方法有效降低了需要人工確認(rèn)的疑似缺陷數(shù)量.在本文研究的基礎(chǔ)上，我們計劃通過使用程序歷史版本等更多信息和更加有針對性的程序編程規(guī)則挖掘算法，進(jìn)一步提高缺陷檢測精度.

參考文獻(xiàn)

[1] 黎銘, 霍軒. 半監(jiān)督軟件缺陷挖掘研究綜述[J]. 數(shù)據(jù)采集與處理, 2016, 31(01):56-64.

[2] LI Z, LU S, MYAGMAR S, et al. CP-Miner: a tool for finding copy-Paste and related bugs in operating system code[C]// The Proceedings of Conference on Symposium on Operating Systems Design and Implementation，2004: 289-302.

[3] LI Z, ZHOU Y. PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code[C]// The Proceedings of European Software Engineering Conference Held Jointly with, ACM Sigsoft International Symposium on Foundations of Software Engineering, 2005, Lisbon, Portugal, September，2005:306-315.

[4] LU S, PARK S, HU C, et al. MUVI: automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs[C]// The Proceedings of ACM Symposium on Operating Systems Principles 2007,Stevenson, Washington, USA, October，2010: 103-116.

[5] XIE T, PEI J. MAPO: mining API usages from open source repositories[C]// The Proceedings of International Workshop on Mining Software Repositories, Shanghai, China, May，2006: 54-57.

[6] QU W, JIA Y, JIANG M. Pattern mining of cloned codes in software systems[J]. Information Sciences, 2014, 259(3): 544-554.

[7] 崔展齊, 牟永敏, 張志華,等. 基于函數(shù)調(diào)用序列模式挖掘的程序缺陷檢測[J]. 計算機科學(xué), 2017, 44(11): 226-231.

[8] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules in large databases[C]// The Proceedings of International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc，1994: 487-499.

[9] HAN J. Mining frequent patterns without candidate generation[J]. ACM Sigmod Record, 2000, 29(2): 1-12.

[10] 黨紅恩,趙爾平,劉煒,等.利用數(shù)據(jù)變換與并行運算的閉頻繁項集挖掘方法[J].湘潭大學(xué)自然科學(xué)學(xué)報,2018,40(1):119-122.

[11] 潘力, 黃繼海, 王磊. 基于分層有限狀態(tài)機的時間序列數(shù)據(jù)挖掘與預(yù)測方法[J]. 湘潭大學(xué)自然科學(xué)學(xué)報, 2017,39(4): 18-21.

[12] SRIKANT R, AGRAWAL R. Mining sequential patterns: generalizations and performance improvements[C]// The Proceedings of International Conference on Extending Database Technology: Advances in Database Technology. Springer-Verlag, 1996: 1-17.