王淑棟，劉 浩，董玉坤，陳紅旗，張 莉，尹文靜

(中國(guó)石油大學(xué)(華東)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，青島 266580)

靜態(tài)分析技術(shù)是一種檢測(cè)程序語(yǔ)義缺陷的有效技術(shù)，通過(guò)靜態(tài)分析程序的語(yǔ)法與語(yǔ)義，并根據(jù)程序安全規(guī)則判斷被測(cè)程序是否違反了程序安全屬性[1-3]。目前，在靜態(tài)測(cè)試領(lǐng)域，已經(jīng)出現(xiàn)了一些相對(duì)成熟的工具，外國(guó)具有代表性的有Klocwork、PMD、Findbugs、Coverity等，中國(guó)有DTS(defect test system)[4-5]等靜態(tài)缺陷檢測(cè)工具。據(jù)統(tǒng)計(jì)，利用這些靜態(tài)檢測(cè)工具對(duì)程序編譯與測(cè)試后，語(yǔ)義缺陷密度[6]大致是1個(gè)/KLOC[7]，這些存在的缺陷嚴(yán)重影響著軟件質(zhì)量，將直接導(dǎo)致程序運(yùn)行時(shí)出現(xiàn)系統(tǒng)崩潰、運(yùn)算結(jié)果異常、安全漏洞等情況。

由于靜態(tài)分析技術(shù)對(duì)程序的非平凡屬性分析不夠精確，目前的靜態(tài)分析工具與方法不可避免的會(huì)存在缺陷的漏報(bào)[8]與誤報(bào)[9]?，F(xiàn)有的靜態(tài)分析工具漏報(bào)率為9%～32%，誤報(bào)率為35%～91%[10]，這些檢測(cè)出的真實(shí)缺陷和誤報(bào)被稱(chēng)為警報(bào)。在圖1中，函數(shù)f1第5行在沒(méi)有進(jìn)行判斷指針p是否是空指針的情況下就直接進(jìn)行了引用，會(huì)引起空指針解引用(null pointer dereference，NPD)警報(bào)；函數(shù)f1第6行在沒(méi)有判斷分母是否為0就進(jìn)行了算術(shù)運(yùn)算，引起非法計(jì)算操作(illegal arithmetic operand，IAO)警報(bào)。

隨著軟件的規(guī)模與復(fù)雜度遞增式增長(zhǎng)，靜態(tài)檢測(cè)工具報(bào)告的警報(bào)數(shù)量也急劇增加，這些檢測(cè)出的警報(bào)需要警報(bào)判定人員逐一進(jìn)行人工判定，大大降低了缺陷檢測(cè)效率，也造成缺陷檢測(cè)的成本大幅度增加，甚至已經(jīng)導(dǎo)致軟件開(kāi)發(fā)和管理人員在軟件開(kāi)發(fā)過(guò)程中拒絕使用靜態(tài)缺陷檢測(cè)工具。

靜態(tài)缺陷檢測(cè)結(jié)果分析顯示，大多數(shù)的警報(bào)與其他警報(bào)之間存在著關(guān)聯(lián)關(guān)系。如圖1所示，函數(shù)f1和函數(shù)f2分別報(bào)告了一個(gè)NPD警報(bào)，兩處警報(bào)的觸發(fā)原因都是因?yàn)樵跊](méi)有進(jìn)行任何空指針判斷的情況下就進(jìn)行了變量引用，兩處警報(bào)分別與變量p和變量q有關(guān)，兩個(gè)變量引用了同一塊內(nèi)存地址，具有相同的符號(hào)表達(dá)式，表明這兩個(gè)警報(bào)存在恒等關(guān)聯(lián)關(guān)系。如果能夠找到這些警報(bào)間的關(guān)聯(lián)關(guān)系并對(duì)警報(bào)進(jìn)行分組，在人工判定警報(bào)的時(shí)候，只需要對(duì)一組中的一個(gè)或幾個(gè)警報(bào)進(jìn)行判定，就可以大大縮短判定的時(shí)間。

圖1 程序代碼片段Fig.1 Program code fragment

關(guān)于警報(bào)關(guān)聯(lián)[11]的相關(guān)技術(shù)已有大量報(bào)道。Lee等[12]提出一種基于靜態(tài)分析的警報(bào)聚類(lèi)的可靠方法，該方法首先判定一個(gè)警報(bào)的錯(cuò)誤狀態(tài)，然后通過(guò)觀察這個(gè)錯(cuò)誤狀態(tài)的傳播對(duì)其他警報(bào)的影響來(lái)判斷警報(bào)間的關(guān)系。Zhang等[13]提出一種錯(cuò)誤狀態(tài)切片的警報(bào)關(guān)聯(lián)方法，該方法首先在缺陷檢測(cè)過(guò)程中去除警報(bào)的錯(cuò)誤狀態(tài)切片，同時(shí)生成一個(gè)新的狀態(tài)切片作為外部約束，從而得到警報(bào)觸發(fā)點(diǎn)的抽象求精語(yǔ)義，之后根據(jù)程序是否會(huì)觸發(fā)警報(bào)進(jìn)行關(guān)聯(lián)計(jì)算。Heckman等[10]基于機(jī)器學(xué)習(xí)技術(shù)提出一種警報(bào)關(guān)聯(lián)特征模型，利用該模型可以實(shí)現(xiàn)警報(bào)間的關(guān)聯(lián)。該方法首先基于該模型構(gòu)建評(píng)估框架，選取了警報(bào)的類(lèi)型和代碼位置等特征信息，并利用了15個(gè)機(jī)器學(xué)習(xí)算法建立警報(bào)關(guān)聯(lián)模型。最后根據(jù)此模型對(duì)檢測(cè)結(jié)果進(jìn)行匹配，將具有相同特征的警報(bào)進(jìn)行關(guān)聯(lián)。以上大部分方法只對(duì)警報(bào)進(jìn)行了簡(jiǎn)單的關(guān)聯(lián)分析，并沒(méi)有對(duì)警報(bào)關(guān)聯(lián)的范圍及準(zhǔn)確性進(jìn)行更深層次的深究。

鑒于上述現(xiàn)象，提出一種基于符號(hào)表達(dá)式的程序語(yǔ)義缺陷警報(bào)關(guān)聯(lián)識(shí)別方法，使用該方法可以得到更高精度、可信度的警報(bào)關(guān)聯(lián)關(guān)系，進(jìn)而更多的減輕人工判定警報(bào)的工作量。研究的貢獻(xiàn)可以概括如下。

(1)提出了一種警報(bào)關(guān)聯(lián)識(shí)別方法，在缺陷檢測(cè)階段將檢測(cè)出的每個(gè)警報(bào)由基于區(qū)域的符號(hào)化三值邏輯(region-based symbolic three valued logic，RSTVL)[14]的符號(hào)表達(dá)式表示，根據(jù)該警報(bào)的符號(hào)表達(dá)式與其他警報(bào)間的符號(hào)表達(dá)式的邏輯關(guān)系，總結(jié)得出恒等、非、或、與四種關(guān)聯(lián)類(lèi)型。

(2)不僅實(shí)現(xiàn)過(guò)程內(nèi)警報(bào)關(guān)聯(lián)，還通過(guò)符號(hào)化函數(shù)摘要實(shí)現(xiàn)過(guò)程間警報(bào)關(guān)聯(lián)，進(jìn)一步提高了識(shí)別警報(bào)關(guān)聯(lián)的精度。

(3)實(shí)驗(yàn)驗(yàn)證了所提方法的有效性，減輕了人工判定警報(bào)的工作量，提高了人工判定警報(bào)工作的效率。

1 相關(guān)定義

一個(gè)程序P可以被表示為一個(gè)六元組P=。其中V表示程序的變量集合，L表示程序點(diǎn)集合，S表示程序語(yǔ)句集合，τ?LSL表示一個(gè)遷移關(guān)系，init∈L表示程序的入口，end∈L表示程序的出口。

程序中警報(bào)的觸發(fā)跟其變量的來(lái)源有著直接的關(guān)系，當(dāng)該警報(bào)跟多個(gè)變量都有關(guān)系的時(shí)候，每一個(gè)變量的來(lái)源都可能對(duì)警報(bào)產(chǎn)生影響。

2 基于符號(hào)表達(dá)式的警報(bào)關(guān)聯(lián)

2.1 符號(hào)表達(dá)式

采用基于區(qū)域的符號(hào)化三值邏輯(region-based symbolic three valued logic，RSTVL)來(lái)表示程序變量的抽象存儲(chǔ)狀態(tài)。

基于區(qū)域的符號(hào)化三值邏輯(RSTVL)定義為四元組，RSTVL=，其中，Var表示內(nèi)存對(duì)象，Region表示區(qū)域，SExp表示符號(hào)表達(dá)式，Domain表示取值區(qū)間。

定義8(符號(hào)表達(dá)式)符號(hào)表達(dá)式SExp由符號(hào)通過(guò)數(shù)學(xué)運(yùn)算與關(guān)系操作構(gòu)成，遞歸定義如式(1)所示：

(1)

式(1)中：符號(hào)表達(dá)式SExp由邏輯表達(dá)式RelExp通過(guò)關(guān)系操作構(gòu)成；RelExp由數(shù)學(xué)表達(dá)式Exp通過(guò)邏輯操作構(gòu)成；Exp由項(xiàng)Term通過(guò)加減運(yùn)算組成；Term由多個(gè)因子Power通過(guò)乘除運(yùn)算組成；每個(gè)Power由一個(gè)或多個(gè)原子Factor通過(guò)冪運(yùn)算組成；原子Factor是符號(hào)表達(dá)式的最基本元素，它可以是一個(gè)數(shù)值常量Constant、符號(hào)變量Symbol或者符號(hào)表達(dá)式SExp。

董玉坤等[15]提出了符號(hào)化函數(shù)摘要，符號(hào)化函數(shù)摘要應(yīng)用RSTVL描述符號(hào)化的函數(shù)摘要，將函數(shù)的行為通過(guò)符號(hào)化表示，在函數(shù)調(diào)用點(diǎn)基于過(guò)程內(nèi)數(shù)據(jù)流分析的結(jié)果對(duì)函數(shù)摘要進(jìn)行實(shí)例化，實(shí)現(xiàn)對(duì)調(diào)用點(diǎn)處抽象存儲(chǔ)狀態(tài)的更新，可實(shí)現(xiàn)過(guò)程間可靠的數(shù)據(jù)流分析，通過(guò)符號(hào)化函數(shù)摘要可以建立過(guò)程間警報(bào)關(guān)聯(lián)。

每個(gè)警報(bào)可能存在n個(gè)相關(guān)變量，每個(gè)相關(guān)變量的符號(hào)表達(dá)式在程序生存周期內(nèi)是唯一的，當(dāng)其中任意兩個(gè)相關(guān)變量的符號(hào)表達(dá)式不一致時(shí)，可以認(rèn)定這是不同的相關(guān)變量。

例如在圖1中，函數(shù)f1第5行在沒(méi)有進(jìn)行任何空指針判斷的情況下進(jìn)行了引用，在第7行調(diào)用函數(shù)f2將指針p的值傳遞過(guò)去，函數(shù)f2同樣在沒(méi)有進(jìn)行任何空指針判斷的情況下進(jìn)行了引用。在第5行和第10行各報(bào)告了一個(gè)NPD警報(bào)，兩個(gè)警報(bào)都對(duì)應(yīng)著同一個(gè)取值區(qū)域，具有相同的符號(hào)表達(dá)式。

在程序點(diǎn)l上，?Va,Vb,Vc∈Vl，Ω假定表示區(qū)間全集，假定VaExp、VbExp和VcExp分別表示變量Va、變量Vb和變量Vc對(duì)應(yīng)的符號(hào)表達(dá)式，D[VaExp]、D[VbExp]、D[VcExp]分別表示變量Va、變量Vb和變量Vc對(duì)應(yīng)的取值區(qū)間。

定義9(符號(hào)表達(dá)式的級(jí)數(shù))符號(hào)表達(dá)式的級(jí)數(shù)(rank)表示符號(hào)表達(dá)式的復(fù)雜程度，根據(jù)符號(hào)表達(dá)式的個(gè)數(shù)將符號(hào)表達(dá)式分為n個(gè)級(jí)別，用符號(hào)ρ表示符號(hào)表達(dá)式的級(jí)數(shù)。假定單個(gè)符號(hào)表達(dá)式VaExp為1級(jí)，每增加一個(gè)邏輯運(yùn)算符號(hào)或者符號(hào)表達(dá)式，相應(yīng)的級(jí)數(shù)也增加1，例如符號(hào)表達(dá)式VaExp為2級(jí)，VaExp&&VbExp為3級(jí)，依次類(lèi)推。

當(dāng)變量間對(duì)應(yīng)的符號(hào)表達(dá)式存在非、或、與三種關(guān)系時(shí)，其對(duì)應(yīng)的取值區(qū)間運(yùn)算存在以下規(guī)則。

非關(guān)系符號(hào)表達(dá)式的區(qū)間運(yùn)算，如式(2)所示。

(2)

或關(guān)系符號(hào)表達(dá)式的區(qū)間運(yùn)算，如式(3)所示：

(3)

與關(guān)系符號(hào)表達(dá)式的區(qū)間運(yùn)算，如式(4)所示：

(4)

2.2 程序語(yǔ)義缺陷警報(bào)

將一類(lèi)缺陷產(chǎn)生時(shí)程序所呈現(xiàn)的共同的語(yǔ)法或語(yǔ)義特征稱(chēng)為缺陷模式。常見(jiàn)的語(yǔ)義類(lèi)缺陷模式包括空指針解引用(null pointer dereference，NPD)、數(shù)組越界(out of bound，OOB)、非法計(jì)算操作(illegal arithmetic operand，IAO)等類(lèi)型。

程序中警報(bào)間具有相同的缺陷模式是警報(bào)關(guān)聯(lián)的基礎(chǔ)，兩個(gè)警報(bào)只有屬于同一個(gè)缺陷模式才可以進(jìn)行關(guān)聯(lián)；相反，如果兩個(gè)警報(bào)來(lái)自不同的缺陷模式，即使警報(bào)的相關(guān)變量為同一個(gè)，也無(wú)法進(jìn)行關(guān)聯(lián)。

為了能夠準(zhǔn)確、全面地表示警報(bào)的數(shù)據(jù)信息，通過(guò)構(gòu)建警報(bào)特征信息來(lái)進(jìn)行描述。將警報(bào)特征信息定義為一個(gè)由結(jié)構(gòu)信息、變量信息組成的二元組SV=。

Struinfo表示警報(bào)的結(jié)構(gòu)信息，由七元組Struinfo=組成。其中，Num表示在警報(bào)文檔中該警報(bào)的編號(hào)，Category表示缺陷類(lèi)型，F(xiàn)ile表示被測(cè)工程，StartLine表示警報(bào)觸發(fā)位置所在工程代碼起始行號(hào)，IPLine表示警報(bào)觸發(fā)位置所在行號(hào)；DeType表示警報(bào)被判定為真實(shí)缺陷或誤報(bào)；Flag表示警報(bào)是否已經(jīng)被判定的標(biāo)記，當(dāng)Flag=0時(shí)，代表警報(bào)沒(méi)有被判定，當(dāng)Flag=1時(shí)，代表警報(bào)被判定。

Varinfo表示警報(bào)的變量信息，由三元組Varinfo =組成。其中，Var表示警報(bào)的相關(guān)變量名稱(chēng)，SExp表示警報(bào)相關(guān)變量對(duì)應(yīng)的符號(hào)表達(dá)式，Domain表示警報(bào)相關(guān)變量對(duì)應(yīng)的取值區(qū)間。

2.3 程序語(yǔ)義缺陷的警報(bào)關(guān)聯(lián)推導(dǎo)規(guī)則

對(duì)于任意的兩個(gè)警報(bào)am和an，假定?Exp(am)表示警報(bào)am的相關(guān)變量對(duì)應(yīng)的符號(hào)表達(dá)式，?Exp(an)表示警報(bào)an的相關(guān)變量對(duì)應(yīng)的符號(hào)表達(dá)式。如果警報(bào)間對(duì)應(yīng)的符號(hào)表達(dá)式符合以下規(guī)則，則判定警報(bào)am和警報(bào)an存在關(guān)聯(lián)關(guān)系。

警報(bào)與警報(bào)之間具有恒等、非、或、與等關(guān)聯(lián)，這些關(guān)聯(lián)信息是人工判定過(guò)程中警報(bào)確認(rèn)的前提。

2.3.1 恒等關(guān)聯(lián)

如果?Exp(am)==?Exp(an)，若警報(bào)am和an同為誤報(bào)或真實(shí)缺陷，則警報(bào)am和an警報(bào)存在恒等關(guān)系。

2.3.2 非關(guān)聯(lián)

如果?Exp(am)==?Exp(an)，若其中一個(gè)為誤報(bào)，則另一個(gè)為真實(shí)缺陷，則警報(bào)am和警報(bào)an存在非關(guān)聯(lián)關(guān)系。

2.3.3 或關(guān)聯(lián)

如果?Exp(am)==?Exp(an)‖?Exp(a)，其中?Exp(a)表示任意警報(bào)對(duì)應(yīng)的一個(gè)符號(hào)表達(dá)式，稱(chēng)警報(bào)am與警報(bào)an存在或關(guān)聯(lián)關(guān)系。

2.3.4 與關(guān)聯(lián)

如果?Exp(am)==?Exp(an)&&?Exp(a)，其中?Exp(a)表示任意警報(bào)對(duì)應(yīng)的一個(gè)符號(hào)表達(dá)式，稱(chēng)警報(bào)am與警報(bào)an存在與關(guān)聯(lián)關(guān)系。

假定存在警報(bào)a，與警報(bào)a存在關(guān)聯(lián)的警報(bào)集合可以由四元組Corinfo=表示。其中，Con表示與警報(bào)a存在恒等關(guān)聯(lián)的警報(bào)集合；Not表示與警報(bào)a存在非關(guān)聯(lián)的警報(bào)集合；Or表示與警報(bào)a存在或關(guān)聯(lián)的警報(bào)集合；And表示與警報(bào)a存在與關(guān)聯(lián)的警報(bào)集合。

3 程序語(yǔ)義缺陷的警報(bào)關(guān)聯(lián)算法與實(shí)現(xiàn)

3.1 程序語(yǔ)義缺陷的警報(bào)關(guān)聯(lián)算法

根據(jù)之前的警報(bào)關(guān)聯(lián)推導(dǎo)規(guī)則，給出一個(gè)具體算法來(lái)計(jì)算警報(bào)關(guān)聯(lián)，其警報(bào)關(guān)聯(lián)算法如下。

算法1中輸入為檢測(cè)的全部警報(bào)；輸出為警報(bào)與警報(bào)之間的關(guān)聯(lián)關(guān)系。其中，Sw表示警報(bào)集合，Sr表示警報(bào)的級(jí)數(shù)集合，N表示警報(bào)的全部數(shù)量。

(1)首先判斷所有警報(bào)對(duì)應(yīng)的符號(hào)表達(dá)式的級(jí)數(shù)，然后按照警報(bào)的符號(hào)表達(dá)式級(jí)數(shù)從小到大進(jìn)行排序，得出警報(bào)序列，接著人工判定符號(hào)表達(dá)式級(jí)數(shù)最小的警報(bào)。

(2)判定兩個(gè)警報(bào)是否為同一類(lèi)缺陷模式，若兩個(gè)警報(bào)不屬于同一類(lèi)缺陷模式，則不存在任何關(guān)聯(lián)，若兩個(gè)警報(bào)屬于同一類(lèi)缺陷模式，再接著下一步。

(3)對(duì)警報(bào)集合中的警報(bào)進(jìn)行兩兩比較，并將存在關(guān)聯(lián)關(guān)系的警報(bào)加入到相應(yīng)的關(guān)聯(lián)集合中。若兩個(gè)警報(bào)對(duì)應(yīng)的符號(hào)表達(dá)式滿(mǎn)足?Exp(am)=?Exp(an)，則兩個(gè)警報(bào)存在恒等關(guān)聯(lián)關(guān)系；若2個(gè)警報(bào)對(duì)應(yīng)的符號(hào)表達(dá)式滿(mǎn)足?Exp(am)=?Exp(an)，則兩個(gè)警報(bào)存在非關(guān)聯(lián)關(guān)系；若兩個(gè)警報(bào)對(duì)應(yīng)的符號(hào)表達(dá)式滿(mǎn)足?Exp(am)=?Exp(an)‖?Exp(a)，則兩個(gè)警報(bào)存在或關(guān)聯(lián)關(guān)系；若兩個(gè)警報(bào)對(duì)應(yīng)的符號(hào)表達(dá)式滿(mǎn)足?Exp(am)=?Exp(an)&&?Exp(a)，則兩個(gè)警報(bào)存在與關(guān)聯(lián)關(guān)系。如果這四種關(guān)聯(lián)都不存在，則警報(bào)間不存在關(guān)聯(lián)關(guān)系。

算法1程序語(yǔ)義缺陷的警報(bào)關(guān)聯(lián)算法。

輸入:檢測(cè)的全部警報(bào)

輸出:警報(bào)與警報(bào)間的關(guān)聯(lián)關(guān)系

function WarningCorrelation(Sw)

for eacha∈Swdo

Sr←ρ(a);

Warning sort from small rank to large rank.

Manual determine each warninga∈Srthat Minimum rank of warning.

for(i=1;i≤N;i++)

for(j=i+1;j≤N;j++)

if(ai.Category!=aj.Category)

continue;

else

if(?Exp(ai)==?Exp(aj))then

ai.Con←aj;

aj.Con←ai;

else if(?Exp(ai)==?Exp(aj))then

ai.Not←aj;

aj.Not←ai;

else if(?Exp(ai)==?Exp(aj)‖?Exp(a))then

ai.Or←aj;

aj.Or←ai;

else if(?Exp(ai)==?Exp(aj)&&?Exp(a))then

ai.And←aj;

aj.And←ai;

else

No correlation;

通過(guò)警報(bào)關(guān)聯(lián)算法后，如果警報(bào)間具有關(guān)聯(lián)關(guān)系，則將這些警報(bào)的關(guān)聯(lián)信息分別存儲(chǔ)在警報(bào)關(guān)聯(lián)文件Corinfo相應(yīng)的Con、Not、Or、And集合中，方便以后人工判定警報(bào)的工作。

3.2 基于警報(bào)關(guān)聯(lián)的人工警報(bào)判定

通過(guò)之前的警報(bào)關(guān)聯(lián)算法已經(jīng)得到了警報(bào)間的關(guān)聯(lián)關(guān)系，這些警報(bào)可能是真實(shí)缺陷也可能是誤報(bào)，還需要進(jìn)一步人工判定警報(bào)的真實(shí)性。當(dāng)人工判定一個(gè)警報(bào)后，警報(bào)判定系統(tǒng)會(huì)把跟這個(gè)警報(bào)相關(guān)的進(jìn)行自動(dòng)判定。

算法2的輸入為警報(bào)及警報(bào)關(guān)聯(lián)關(guān)系，輸出為警報(bào)判定結(jié)果。其中，Sm表示人工重新判定集合。

首先人工判定警報(bào)集合中某警報(bào)是真實(shí)缺陷還是誤報(bào)，然后依次判定警報(bào)a判定是否存在恒等、非、或、與關(guān)聯(lián)關(guān)系。

若警報(bào)集合a.Con非空，表示警報(bào)a存在恒等關(guān)聯(lián)的警報(bào)，判斷存在關(guān)聯(lián)的警報(bào)的判定標(biāo)記Flag，如果Flag為0，則與警報(bào)a的判定結(jié)果相同，如果Flag為1，則判斷已判定的類(lèi)型是否與警報(bào)a的判定結(jié)果相同，如果不相同，則加入Sm集合；若警報(bào)集合a.Not非空，表示警報(bào)a存在非關(guān)聯(lián)的警報(bào)，判斷過(guò)程同上，只是判定結(jié)果與警報(bào)a相反；若警報(bào)集合a.Or非空，表示警報(bào)a存在或關(guān)聯(lián)的警報(bào)，如果警報(bào)a的判定結(jié)果是真實(shí)缺陷，判定過(guò)程同恒等關(guān)聯(lián)判定過(guò)程，如果警報(bào)a的判定結(jié)果是誤報(bào)，則將與之關(guān)聯(lián)的警報(bào)加入Sm集合；若警報(bào)集合a.And非空，表示警報(bào)a存在與關(guān)聯(lián)的警報(bào)，如果警報(bào)a的判定結(jié)果是誤報(bào)，判定過(guò)程同恒等關(guān)聯(lián)判定過(guò)程，如果警報(bào)a的判定結(jié)果是真實(shí)缺陷，則將與之關(guān)聯(lián)的警報(bào)加入Sm集合。最后，若集合Sm非空，則人工親自判定集合Sm中的警報(bào)，人工判定完成警報(bào)后，算法結(jié)束。

算法2警報(bào)判定算法。

輸入:警報(bào)及警報(bào)關(guān)聯(lián)關(guān)系

輸出:警報(bào)判定結(jié)果

function WarningDetermine(Sw，Corinfo)

for eacha∈Swdo

Manual determinea’s DeType;

if(a.Con!=?)then

for eachw∈a.Con do

call function Redet(w);

else if(a.Not!=?)then

for eachw∈a.Not do

if(w.Flag==0)then

else

if(w.DeType==a.DeType)then

Sm←w;

else if(a.Or!=?)then

for eachw∈a.Or do

if(a.DeType==defect)then

call function Redet(w);

else

Sm←w;

else if(a.And!=?)then

for eachw∈a.And do

if(a.DeType==false positive)then

call function Redet(w);

else

Sm←w;

if(Sm!=?)then

for eachw∈Smdo

Manual determinew;

function Redet(w)

if(w.Flag==0)then

w.DeType←a.DeType.

else

if(w.DeType!=a.DeType)then

Sm←w;

4 實(shí)驗(yàn)驗(yàn)證

在第4節(jié)中，已經(jīng)介紹了警報(bào)關(guān)聯(lián)算法和警報(bào)判定算法，為了證明上述方法能夠?qū)崿F(xiàn)警報(bào)關(guān)聯(lián)及警報(bào)判定，將上述算法嵌入靜態(tài)缺陷測(cè)試工具DTSC_RSTVL中進(jìn)行實(shí)驗(yàn)。

4.1 實(shí)驗(yàn)平臺(tái)

實(shí)驗(yàn)平臺(tái)是在原型工具DTSC_RSTVL[14]的基礎(chǔ)上進(jìn)行改進(jìn)，并得到了工具DTSC_Corr，通過(guò)該工具可以實(shí)現(xiàn)對(duì)典型語(yǔ)義缺陷的充分檢測(cè)，并在缺陷檢測(cè)階段對(duì)警報(bào)進(jìn)行關(guān)聯(lián)與排序。圖2所示為DTSC_Corr處理流程的基本框架，包括5個(gè)處理部分，分別為：輸入部分、基本處理部分、數(shù)據(jù)流分析部分、自動(dòng)檢測(cè)部分、結(jié)果分析部分。

圖2 DTSC_Corr工具處理流程圖Fig.2 DTSC_Corr processing flow chart

4.2 實(shí)驗(yàn)結(jié)果及分析

選擇3種常見(jiàn)的缺陷模式空指針解引用(NPD)、數(shù)組越界(OOB)、非法計(jì)算操作(IAO)作為DTSC_Corr的檢測(cè)故障對(duì)象，并選擇5個(gè)開(kāi)源C工程Barcode、Sphinxbase、Uucp、Git、Httpd作為被測(cè)對(duì)象，5個(gè)工程共計(jì)1 232個(gè)文件447 250行代碼，其中工程代碼量最小的為3 409行，最大為204 229行。選擇的這5個(gè)工程對(duì)于所用方法都具有一定的代表性，其包含大量復(fù)雜的指針操作和函數(shù)調(diào)用操作。

表1所示為在DTS平臺(tái)測(cè)試5個(gè)C工程的警報(bào)詳細(xì)信息。統(tǒng)計(jì)結(jié)果表明：5個(gè)工程共檢測(cè)出914個(gè)警報(bào)，其中真實(shí)缺陷378個(gè)，誤報(bào)536個(gè)。存在關(guān)聯(lián)關(guān)系的警報(bào)總數(shù)占全部警報(bào)總數(shù)的61.71%，對(duì)警報(bào)的恒等、非、或、與關(guān)聯(lián)統(tǒng)計(jì)，恒等關(guān)聯(lián)占四種關(guān)聯(lián)中的占比最多，為84.65%；其次是或關(guān)聯(lián)占比13.30%，與關(guān)聯(lián)占比2.05%，非關(guān)聯(lián)沒(méi)有匹配到，占比0，這是因?yàn)殡m然非關(guān)聯(lián)邏輯上是存在的，但是在真實(shí)的編程中卻是很少使用，所以并沒(méi)有檢測(cè)到。在運(yùn)行時(shí)間方面來(lái)看，采用警報(bào)關(guān)聯(lián)后的DTS運(yùn)行時(shí)間普遍略高于沒(méi)有采用警報(bào)關(guān)聯(lián)算法的時(shí)間。Barcode、Sphinxbase、Uucp、Git、Httpd 5個(gè)工程的處理時(shí)間分別增加9.38%、10.53%、6.86%、7.66%、12.40%，平均增加9.44%的程序處理時(shí)間。

利用警報(bào)關(guān)聯(lián)方法可以減少345次警報(bào)判定工作，占警報(bào)總數(shù)的37.75%。其中，警報(bào)關(guān)聯(lián)程度最高的工程是Git-1.8.2，通過(guò)警報(bào)關(guān)聯(lián)算法可以減少46.26%的警報(bào)判定工作；警報(bào)關(guān)聯(lián)程度最低的工程是Uucp-1.07，通過(guò)警報(bào)關(guān)聯(lián)算法可以減少21.78%的警報(bào)判定工作。當(dāng)工程規(guī)模更大時(shí)，警報(bào)數(shù)也將隨之增加，通過(guò)警報(bào)關(guān)聯(lián)算法可以減少的警報(bào)判定次數(shù)也會(huì)更多，人工判定減輕更大的負(fù)擔(dān)。

圖3為工程Barcode-0.98pcl.c中檢測(cè)出的警報(bào)關(guān)聯(lián)的實(shí)例，第65、第66、第67、第68行在沒(méi)有進(jìn)行任何空指針判斷的情況下進(jìn)行了引用，會(huì)引起NPD警報(bào)，該警報(bào)對(duì)應(yīng)的相關(guān)變量為指針*ptr，4個(gè)NPD警報(bào)對(duì)應(yīng)著相同的符號(hào)表達(dá)式，屬于恒等關(guān)聯(lián)關(guān)系。

圖3 警報(bào)恒等關(guān)聯(lián)示例Fig.3 Alarm identity association example

圖4為Uucp-1.07/prot.c中檢測(cè)出的另一個(gè)警報(bào)關(guān)聯(lián)實(shí)例。第244行、第248行、第251行各報(bào)告了一個(gè)OOB警報(bào)，244行和248行因?yàn)闈撛诘拇嬖诜帜笧?的取值可能，第251行中drawWidth取值存在小于0的可能，違反了sqrt中參數(shù)必須大于等于0的規(guī)則，drawWidth的取值來(lái)源也是多個(gè)，這3個(gè)警報(bào)存在或關(guān)聯(lián)。通過(guò)分析5個(gè)開(kāi)源C工程的實(shí)驗(yàn)數(shù)據(jù)，發(fā)現(xiàn)所用警報(bào)關(guān)聯(lián)方法在平均程序處理時(shí)間增加9.44%的情況下，可以減少21.78%～46.26%的警報(bào)判定工作。對(duì)于大型工程而言，這將在很大程度上減輕警報(bào)判定人員的工作量，從而可以提高整體的缺陷檢測(cè)效率。

圖4 警報(bào)或關(guān)聯(lián)示例Fig.4 Alert or association example

表1 警報(bào)關(guān)聯(lián)數(shù)據(jù)Table 1 Alert associated data

4.3 相關(guān)方法對(duì)比

基于警報(bào)關(guān)聯(lián)的抽象解釋優(yōu)化試圖通過(guò)警報(bào)間的關(guān)聯(lián)性對(duì)靜態(tài)分析報(bào)告的警報(bào)分類(lèi)，對(duì)于存在關(guān)聯(lián)關(guān)系的警報(bào)，只要確定其中一個(gè)警報(bào)即可完成與之相關(guān)聯(lián)警報(bào)的判定。

本文方法與文獻(xiàn)[12]、文獻(xiàn)[13]的方法都是在抽象解釋技術(shù)框架下，對(duì)檢測(cè)到的警報(bào)進(jìn)行警報(bào)關(guān)聯(lián)。不同之處是，文獻(xiàn)[12]借鑒反例求精思想方法，首先需要對(duì)被測(cè)程序生成一個(gè)超級(jí)控制流圖進(jìn)而進(jìn)行完整的程序分析，這種分析無(wú)疑將需要大量的時(shí)間和空間開(kāi)銷(xiāo)，在大型程序的分析過(guò)程中無(wú)法實(shí)現(xiàn)；文獻(xiàn)[13]采用程序切片技術(shù)的方法，首先給出了警報(bào)關(guān)聯(lián)的定義，然后正式提出了警報(bào)錯(cuò)誤狀態(tài)切片，將警報(bào)的錯(cuò)誤狀態(tài)切片作為一種程序的外部輸入約束，進(jìn)而得到基于外部約束的程序求精語(yǔ)義。采用符號(hào)表達(dá)式的方法，基于警報(bào)對(duì)應(yīng)符號(hào)表達(dá)式的邏輯關(guān)系推導(dǎo)出警報(bào)間的關(guān)聯(lián)。本文方法與文獻(xiàn)[12]、文獻(xiàn)[13]方法主要有以下幾方面區(qū)別。

4.3.1 警報(bào)關(guān)聯(lián)精度

文獻(xiàn)[12]方法主要是實(shí)現(xiàn)過(guò)程內(nèi)警報(bào)間關(guān)聯(lián)，無(wú)法實(shí)現(xiàn)過(guò)程間警報(bào)關(guān)聯(lián)。文獻(xiàn)[13]方法主要局限于警報(bào)錯(cuò)誤狀態(tài)切片過(guò)程中，對(duì)每一種警報(bào)類(lèi)型生成對(duì)應(yīng)的警報(bào)錯(cuò)誤切片，由于符號(hào)化區(qū)間抽象域的表示及計(jì)算能力不足，并不能精確地利用現(xiàn)有靜態(tài)分析工具所提供的抽象域切除其錯(cuò)誤狀態(tài)。對(duì)于警報(bào)間復(fù)雜的關(guān)聯(lián)關(guān)系及語(yǔ)法類(lèi)警報(bào)，不能準(zhǔn)確地得到警報(bào)的關(guān)聯(lián)關(guān)系。而本文方法利用符號(hào)表達(dá)式，通過(guò)警報(bào)對(duì)應(yīng)的符號(hào)表達(dá)式間的邏輯關(guān)系，不僅可以實(shí)現(xiàn)過(guò)程內(nèi)警報(bào)關(guān)聯(lián)，同時(shí)可以實(shí)現(xiàn)過(guò)程間警報(bào)關(guān)聯(lián)，且得出警報(bào)關(guān)聯(lián)精度較高。

4.3.2 警報(bào)關(guān)聯(lián)可信度

靜態(tài)分析工具DTS在前期已經(jīng)得到了大量求精與優(yōu)化，肖慶等[5]通過(guò)使用變量取值信息來(lái)表達(dá)程序的路徑狀態(tài)，實(shí)現(xiàn)了DTS的路徑敏感的分析；董玉坤等[15]在原有表達(dá)式區(qū)間抽象域的基礎(chǔ)上引入了符號(hào)化三值邏輯區(qū)間抽象域，不但可以表示變量間的線(xiàn)性關(guān)聯(lián)關(guān)系，還可以表達(dá)變量間的邏輯關(guān)聯(lián)關(guān)系。在靜態(tài)分析求精工作基礎(chǔ)上進(jìn)行研究，所得出的警報(bào)關(guān)聯(lián)具有較高的可信度。

4.3.3 實(shí)驗(yàn)效果對(duì)比

表2為本文方法與文獻(xiàn)[12]、文獻(xiàn)[13]方法同時(shí)測(cè)試Barcode、Sphinxbase、Uucp、Git、Httpd 5個(gè)工程所得數(shù)據(jù)。從實(shí)驗(yàn)效果來(lái)看，主要可以分為減少警報(bào)確認(rèn)數(shù)量和關(guān)聯(lián)增加時(shí)間兩大方面。由表2可知，從實(shí)驗(yàn)結(jié)果中減少警報(bào)確認(rèn)數(shù)量來(lái)看，文獻(xiàn)[12]方法的減少警報(bào)確認(rèn)數(shù)量為23.42%，文獻(xiàn)[13]方法的減少警報(bào)確認(rèn)數(shù)量為28%，本文方法的平均關(guān)聯(lián)比例為37.75%，本文方法在減少警報(bào)確認(rèn)數(shù)量上均優(yōu)于文獻(xiàn)[12]、文獻(xiàn)[13]的方法。當(dāng)檢測(cè)工程量很大時(shí)，對(duì)減輕人工判定工作具有更好效果。從表2的增加時(shí)間來(lái)看，本文方法的增加時(shí)間為9.44%，略低于文獻(xiàn)[12]方法的增加時(shí)間15.06%，但高于文獻(xiàn)[13]方法的增加時(shí)間8.81%。但目前的計(jì)算機(jī)處理性能都相對(duì)比較高效，時(shí)間上的增加也不是很多，屬于在可以接受的范圍內(nèi)。

綜合來(lái)看，本文方法可以在更高精度、可信度下識(shí)別出警報(bào)間的關(guān)聯(lián)，從而可以更好地減輕人工判定工作的工作量。

表2 相關(guān)工作對(duì)比Table 2 Related work comparison

5 結(jié)論

提出了一種基于符號(hào)表達(dá)式的程序語(yǔ)義缺陷警報(bào)關(guān)聯(lián)識(shí)別方法。首先提出警報(bào)關(guān)聯(lián)的定義，然后通過(guò)警報(bào)相關(guān)變量對(duì)應(yīng)的符號(hào)表達(dá)式之間的邏輯關(guān)系，總結(jié)出恒等、非、或、與四種類(lèi)型的關(guān)聯(lián)關(guān)系，其中通過(guò)符號(hào)化函數(shù)摘要實(shí)現(xiàn)了過(guò)程間警報(bào)關(guān)聯(lián)，最后通過(guò)警報(bào)關(guān)聯(lián)算法實(shí)現(xiàn)了過(guò)程內(nèi)警報(bào)關(guān)聯(lián)和過(guò)程間警報(bào)關(guān)聯(lián)。通過(guò)實(shí)驗(yàn)驗(yàn)證得出，本文方法可以有效地實(shí)現(xiàn)警報(bào)間的關(guān)聯(lián)，在程序處理時(shí)間略有升高的情況下，平均可以減少37.75%的人工判定警報(bào)工作量。

所做工作的局限性在于，研究主要集中在如何構(gòu)建警報(bào)間的關(guān)聯(lián)關(guān)系，因此在警報(bào)關(guān)聯(lián)的結(jié)果中可能會(huì)存在誤關(guān)聯(lián)現(xiàn)象。如何改進(jìn)警報(bào)間存在的誤關(guān)聯(lián)，進(jìn)一步提高對(duì)實(shí)際工程的應(yīng)用，仍然是下一步需要改進(jìn)的方向。