基于警報(bào)關(guān)聯(lián)摘要的過程間警報(bào)關(guān)聯(lián)分析

張 莉 董玉坤 劉 浩 尹文靜

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

1 引言

隨著信息技術(shù)行業(yè)的蓬勃發(fā)展，軟件的規(guī)模與復(fù)雜度也呈現(xiàn)遞增式增長。軟件中存在缺陷難以避免，其中，程序語義缺陷是一類典型的軟件缺陷，程序語義缺陷會導(dǎo)致程序運(yùn)行時(shí)出現(xiàn)系統(tǒng)癱瘓、運(yùn)算結(jié)果不正確、性能降低等問題。

靜態(tài)分析技術(shù)是檢測語義缺陷的一種有效方法，但由于在數(shù)據(jù)流分析與缺陷檢測過程中的某些保守處理，檢測出的警報(bào)只是可能是缺陷，其中可能會存在誤報(bào)，根據(jù)相關(guān)數(shù)據(jù)統(tǒng)計(jì)，目前存在的靜態(tài)分析［17］工具檢測出警報(bào)的誤報(bào)率大概在35%～91%之間［1］。而這些誤報(bào)的存在導(dǎo)致缺陷檢測結(jié)果必須由人工進(jìn)行仔細(xì)的判定，對檢測出的警報(bào)的判定需要投入大量的人力，這不但降低了缺陷檢測的效率，也會增加缺陷檢測的成本。

通過對大量程序進(jìn)行靜態(tài)缺陷檢測［12～13］到的警報(bào)進(jìn)行人工分析，其結(jié)果表明警報(bào)與警報(bào)之間存在著關(guān)聯(lián)關(guān)系，將具有關(guān)聯(lián)關(guān)系的警報(bào)聚為一類，只需要對一類中的一個(gè)或多個(gè)警報(bào)的結(jié)果進(jìn)行判定，即可得出該類警報(bào)的判定結(jié)果，從而提高人工判定警報(bào)的效率。

目前，在軟件的開發(fā)過程中模塊化開發(fā)的體現(xiàn)即為大量的函數(shù)及函數(shù)調(diào)用。大量函數(shù)調(diào)用這種交互行為使得函數(shù)之間的警報(bào)存在著關(guān)聯(lián)關(guān)系，稱為過程間警報(bào)關(guān)聯(lián)［2～7］。根據(jù)相關(guān)數(shù)據(jù)分析表明，過程間警報(bào)關(guān)聯(lián)的數(shù)量占總警報(bào)關(guān)聯(lián)總數(shù)的比重為31.7%，當(dāng)代碼量巨大時(shí)，過程間警報(bào)關(guān)聯(lián)的數(shù)量也是非常巨大的。

鑒于上述現(xiàn)象，本文提出了一種基于警報(bào)關(guān)聯(lián)摘要的過程間警報(bào)關(guān)聯(lián)分析方法，使用該方法可以在更高效率、更方便地識別出過程間的警報(bào)關(guān)聯(lián)，進(jìn)而更多地減輕人工判定警報(bào)的工作量。本研究的貢獻(xiàn)可以概括為以下方面。

1）通過定義警報(bào)關(guān)聯(lián)摘要，獲得每個(gè)函數(shù)的警報(bào)關(guān)聯(lián)摘要，并利用該摘要實(shí)現(xiàn)過程間警報(bào)關(guān)聯(lián)，內(nèi)存開銷相對比較低；

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

2 程序語義警報(bào)概述與表示

警報(bào)關(guān)聯(lián)技術(shù)是一種能夠有效減輕警報(bào)判定負(fù)擔(dān)的警報(bào)優(yōu)化技術(shù)［8，14～16］。本小節(jié)給出警報(bào)相關(guān)問題的具體分析與說明。

2.1 程序語義缺陷

程序語義缺陷是導(dǎo)致軟件故障及漏洞的重要原因之一，對語義缺陷分析可以幫助解決軟件故障和漏洞。在程序中，將一類缺陷表現(xiàn)出的共同存在的語義特征稱為語義缺陷模式，語義缺陷模式又可分為故障類缺陷和安全類缺陷［9］，本文中主要針對故障類缺陷，常見的故障類缺陷有空指針引用類型、內(nèi)存泄露類型、數(shù)組越界類型等。

我們將真實(shí)缺陷與誤報(bào)統(tǒng)稱為程序語義警報(bào)，其具體定義如下，本文之后不再進(jìn)行說明。

定義（程序語義警報(bào)）。假定在程序點(diǎn)l處，如果Ab(l)∩Er(l)≠?，其中Ab代表程序抽象語義，Er代表程序點(diǎn)的錯(cuò)誤狀態(tài)，則說明在程序點(diǎn)l處存在警報(bào)，否則，在程序點(diǎn)l處不存在警報(bào)。

2.2 程序語義警報(bào)的表示

為了能夠在程序中準(zhǔn)確得到并表示警報(bào)，本文將結(jié)合符號表達(dá)式和區(qū)間集通過數(shù)據(jù)流兩次映射將警報(bào)轉(zhuǎn)化為其對應(yīng)的取值區(qū)間。兩次映射如下：首先，將警報(bào)變量映射為對應(yīng)的符號表達(dá)式［10］，Var→SExp；其次，將符號映射為對應(yīng)的取值區(qū)間［11］，Symbol→Domain。這樣就將得到了警報(bào)的取值區(qū)間。

對于任意的兩個(gè)警報(bào)am和an，假定?Exp(am)表示警報(bào)am的相關(guān)變量對應(yīng)的符號表達(dá)式，?Exp(an)表示警報(bào)an的相關(guān)變量對應(yīng)的符號表達(dá)式。警報(bào)與警報(bào)之間具有恒等、非、或、與等關(guān)聯(lián)，這些關(guān)聯(lián)信息是人工判定過程中警報(bào)確認(rèn)的前提［18］。

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

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)系。

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

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

3 過程間警報(bào)傳遞類型

函數(shù)間調(diào)用往往是引起過程間存在警報(bào)關(guān)聯(lián)的一個(gè)重要因素，因此，在分析過程間警報(bào)關(guān)聯(lián)時(shí)，需要對程序中的函數(shù)調(diào)用過程進(jìn)行分析。在本文中，具體的函數(shù)間的調(diào)用關(guān)系用程序函數(shù)調(diào)用圖［8］（Program Function Call Graph，PFCG）來表示。

若警報(bào)通過函數(shù)調(diào)用引發(fā)新的警報(bào)，導(dǎo)致存在過程間警報(bào)關(guān)聯(lián)。通過分析函數(shù)間的調(diào)用方式，過程間警報(bào)傳遞類型又可以分為鏈?zhǔn)叫蛡鬟f關(guān)系、匯聚型傳遞關(guān)系和發(fā)散型傳遞關(guān)系三種類型，下面將對這三種類型進(jìn)行說明。

3.1 鏈?zhǔn)叫蛡鬟f關(guān)系

若函數(shù)f1中存在警報(bào)a，函數(shù)f1調(diào)用函數(shù)f2，導(dǎo)致因?yàn)榫瘓?bào)a的傳遞引發(fā)警報(bào)b的產(chǎn)生；同時(shí)函數(shù)f2又調(diào)用函數(shù)f3，同樣導(dǎo)致警報(bào)b的傳遞引發(fā)警報(bào)c的產(chǎn)生，則警報(bào)a、警報(bào)b和警報(bào)c存在著關(guān)聯(lián)關(guān)系，稱這種為鏈?zhǔn)叫蛡鬟f關(guān)系（Chain Type Transfer Relationship，ChTR），如圖1所示。

圖1 鏈?zhǔn)叫蛡鬟f關(guān)系圖

3.2 匯聚型傳遞關(guān)系

若存在多個(gè)函數(shù)g2，g3，…，gn調(diào)用同一個(gè)函數(shù)g1，并且函數(shù)g1存在警報(bào)a，由于函數(shù)g2，…，gn調(diào)用函數(shù)g1引發(fā)新的警報(bào)b，c，d等，則警報(bào)b，c，d和警報(bào)a存在關(guān)聯(lián)關(guān)系，稱這種關(guān)聯(lián)關(guān)系為匯聚型傳遞關(guān) 系（Convergent Type Transfer Relationship，Co-TR），如圖2所示。

圖2 匯聚型傳遞關(guān)系圖

3.3 發(fā)散型傳遞關(guān)系

若函數(shù)q1中存在警報(bào)a，函數(shù)q1調(diào)用了多個(gè)函數(shù)q2，q3，…，qn，導(dǎo)致因?yàn)榫瘓?bào)a的傳遞引發(fā)警報(bào)b，c，d等的產(chǎn)生，則警報(bào)a與警報(bào)b，c，d存在著關(guān)聯(lián)關(guān)系，稱這種關(guān)聯(lián)為發(fā)散型傳遞關(guān)系（Divergence Type Transfer Relationship，DTTR），如圖3所示。

圖3 發(fā)散型傳遞關(guān)系圖

4 警報(bào)關(guān)聯(lián)摘要

對函數(shù)間交互行為的分析稱為過程間分析。本文對過程間分析采用了函數(shù)摘要的方式，函數(shù)摘要是一種目前被普遍采用的方法，根據(jù)函數(shù)內(nèi)分析結(jié)果生成被調(diào)函數(shù)的摘要信息，用摘要信息再分析過程中替代其展開。接下來介紹了關(guān)于缺陷的函數(shù)摘要模型。

針對過程間警報(bào)關(guān)聯(lián)識別問題，本文提出對存在警報(bào)的函數(shù)生成對應(yīng)的警報(bào)關(guān)聯(lián)摘要的方法，然后生成被調(diào)函數(shù)的警報(bào)關(guān)聯(lián)摘要信息，用摘要信息替代其函數(shù)調(diào)用的展開。

在函數(shù)調(diào)用過程中，產(chǎn)生的警報(bào)可能向其調(diào)用者進(jìn)一步傳遞警報(bào)狀態(tài)，可能會對調(diào)用該函數(shù)的上下文信息產(chǎn)生影響，導(dǎo)致調(diào)用點(diǎn)上下文環(huán)境遷移：1）實(shí)參；2）函數(shù)返回值；3）全局變量。

針對上述三種類型的影響，本文給出了警報(bào)關(guān)聯(lián)摘要模型（Warnings Correlation Summary Model，WCSM）來描述，警報(bào)關(guān)聯(lián)摘要模型盡可能詳細(xì)地捕獲了所有與警報(bào)相關(guān)的函數(shù)行為，警報(bào)關(guān)聯(lián)摘要模型可以分為前置約束信息Pre-constraint、后置約束信息Post-constraint兩部分。用符號表示為WCSM=｛Pre-constraint，Post-constraint｝，其中前置約束信息Pre-constraint表示函數(shù)調(diào)用前應(yīng)滿足的約束信息，后置約束信息Post-constraint表示函數(shù)調(diào)用后所帶來副作用影響。

1）前置約束信息

前置約束信息Pre-constraint表示跟警報(bào)相關(guān)的一類信息，不同缺陷模式對應(yīng)的警報(bào)會對應(yīng)不同的前置約束信息。前置約束信息表示如式（2）。

Pre-constraint={＜var，SExp，con＞}表示主調(diào)函數(shù)調(diào)用被調(diào)函數(shù)時(shí)應(yīng)滿足的前置約束信息集合，＜var，SExp，con＞代表變量var對應(yīng)的符號表達(dá)式SExp的取值必須包含在約束條件con中。

其中，con表示被調(diào)函數(shù)在調(diào)用點(diǎn)處需要滿足的條件，不同類型的缺陷需要滿足不同的條件。

2）后置約束信息

后置約束信息Post-constraint主要針對分析函數(shù)返回值RetVal和全局變量GloVar兩種類型的影響。后置約束信息表示如式（3）。

RetVal=SExp表示函數(shù)返回值的符號表達(dá)式，GloVar={(var，SExp)}表示由受副作用影響的變量var和其對應(yīng)的符號表達(dá)式SExp兩個(gè)元素組成的集合。

5 警報(bào)關(guān)聯(lián)摘要生成及實(shí)例化

警報(bào)關(guān)聯(lián)摘要生成步驟如下。首先，得出程序中數(shù)據(jù)流分析結(jié)果calDomain，計(jì)算函數(shù)返回語句RetVal的符號表達(dá)式SExp作為后置約束信息的函數(shù)返回值部分，獲取程序中全局變量GloVar的對應(yīng)的變量var和其符合表達(dá)式SExp作為后置約束信息的全局變量部分；對于函數(shù)內(nèi)無法確定的缺陷狀態(tài)，構(gòu)造其變量、符合表達(dá)式和其約束信息作為前置約束信息，并向上層調(diào)用者傳遞。下面將給出警報(bào)關(guān)聯(lián)摘要的生成算法。

算法1.警報(bào)關(guān)聯(lián)摘要生成算法。

當(dāng)函數(shù)間存在調(diào)用關(guān)系時(shí)，這時(shí)就需要用到警報(bào)關(guān)聯(lián)摘要實(shí)例化。警報(bào)關(guān)聯(lián)摘要實(shí)例化步驟如下。首先，獲取被調(diào)用函數(shù)已經(jīng)生成的警報(bào)關(guān)聯(lián)摘要；其次，根據(jù)數(shù)據(jù)流分析結(jié)果對警報(bào)關(guān)聯(lián)摘要更新，如果警報(bào)關(guān)聯(lián)摘要有變化，則將前置約束信息和后置約束信息對應(yīng)的取值信息用調(diào)用點(diǎn)處的信息更新，否則，不更新；如果存在多級函數(shù)調(diào)用的情況，則需要從下到上依次進(jìn)行實(shí)例化。

6 過程間警報(bào)關(guān)聯(lián)算法實(shí)現(xiàn)與分析

在本節(jié)中我們將介紹過程間警報(bào)關(guān)聯(lián)的算法與實(shí)現(xiàn)，下面是其詳細(xì)描述。過程間警報(bào)關(guān)聯(lián)算法步驟如下。

1）從警報(bào)特征信息SV中得出存在警報(bào)的函數(shù)，得出存在警報(bào)的函數(shù)集合SF；

2）通過分析函數(shù)集合SF中函數(shù)間的關(guān)系，生成對應(yīng)的函數(shù)調(diào)用子圖PFCG'；

3）依次判定生成的每一個(gè)函數(shù)調(diào)用子圖PFCG'的類型，根據(jù)函數(shù)調(diào)用子圖的調(diào)用類型可以分為以下三種實(shí)例化更新的方法。

當(dāng)某個(gè)函數(shù)調(diào)用該存在警報(bào)的函數(shù)，根據(jù)上下文信息進(jìn)行實(shí)例化，如果存在警報(bào)關(guān)聯(lián)摘要對應(yīng)的值不一致的情況，進(jìn)行更新，否則，不更新。

（1）針對鏈?zhǔn)叫蛡鬟f關(guān)系

若存在警報(bào)的函數(shù)間是鏈?zhǔn)叫蛡鬟f關(guān)系類型（ChTR），即函數(shù)存在多級調(diào)用的情況，則從調(diào)用者到被調(diào)用者依次更新警報(bào)關(guān)聯(lián)摘要。更新完畢后，根據(jù)過程內(nèi)警報(bào)關(guān)聯(lián)算法［18］繼續(xù)判定警報(bào)間的關(guān)聯(lián)關(guān)系。

（2）針對匯聚型傳遞關(guān)系

若存在警報(bào)的函數(shù)間是匯聚型傳遞關(guān)系（Co-TR），則需要每個(gè)主調(diào)函數(shù)依次對被調(diào)函數(shù)進(jìn)行警報(bào)關(guān)聯(lián)摘要更新，并需要分開判斷。

（3）針對發(fā)散型傳遞關(guān)系

若存在警報(bào)的函數(shù)間是發(fā)散型傳遞關(guān)系（DTTR），即一個(gè)函數(shù)調(diào)用了多個(gè)函數(shù)的情況，則同樣由主調(diào)函數(shù)對每一個(gè)被調(diào)函數(shù)進(jìn)行警報(bào)關(guān)聯(lián)摘要更新。更新完畢后，同樣根據(jù)過程內(nèi)警報(bào)關(guān)聯(lián)方式繼續(xù)判定警報(bào)間的關(guān)聯(lián)關(guān)系。

算法2.過程間警報(bào)關(guān)聯(lián)算法。

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

本節(jié)分別介紹了實(shí)驗(yàn)平臺DTSC_Corr及其處理流程，并對實(shí)驗(yàn)結(jié)果中的數(shù)據(jù)進(jìn)行分析與說明。

7.1 實(shí)驗(yàn)平臺

本文的實(shí)驗(yàn)平臺是在原型工具DTSC_RSTVL［14］的基礎(chǔ)上進(jìn)行改進(jìn)，并得到了工具DTSC_Corr，通過該工具可以實(shí)現(xiàn)對典型語義缺陷的充分檢測，并在缺陷檢測階段對警報(bào)進(jìn)行關(guān)聯(lián)與排序。圖4表示DTSC_Corr處理流程的基本框架。

圖4 DTSC_Corr工具處理流程圖

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

本節(jié)將通過實(shí)驗(yàn)來進(jìn)行驗(yàn)證本文所提的過程間警報(bào)關(guān)聯(lián)算法的應(yīng)用效果。本實(shí)驗(yàn)選擇了3種常見的缺陷模式空指針解引用（NPD）、數(shù)組越界（OOB）、非法計(jì)算操作（IAO）作為檢測故障對象，使用標(biāo)準(zhǔn)性能評估組織SPEC（Standard Performance Evaluation Corporation）提供的公共測試集SPEC2000/2006中5個(gè)開源C工程Barcode-1.07、Antiword-0.37、Sphinxbase-0.3、Spell-1.0、Uucp-1.07作為被測對象，5個(gè)工程共計(jì)125809行代碼，其中程序中的函數(shù)個(gè)數(shù)為2414個(gè)，調(diào)用函數(shù)的次數(shù)為9017個(gè)。其過程間警報(bào)關(guān)聯(lián)數(shù)據(jù)統(tǒng)計(jì)如表1所示。

表1 過程間警報(bào)關(guān)聯(lián)數(shù)據(jù)統(tǒng)計(jì)

通過對實(shí)驗(yàn)結(jié)果分析，過程間警報(bào)關(guān)聯(lián)的各種關(guān)聯(lián)分布與過程內(nèi)警報(bào)關(guān)聯(lián)的關(guān)聯(lián)分布類似，同樣是存在恒等關(guān)聯(lián)的警報(bào)最多，其數(shù)量占警報(bào)數(shù)量總數(shù)的56.19%；其次是存在非關(guān)聯(lián)的警報(bào)，其數(shù)量占警報(bào)數(shù)量總數(shù)的18.13%；然后是存在與關(guān)聯(lián)的警報(bào)，其數(shù)量占警報(bào)數(shù)量總數(shù)的9.97%；最后是非關(guān)聯(lián)關(guān)系，占比為0。

通過對實(shí)驗(yàn)數(shù)據(jù)分析得出，該方法可以有效識別過程間警報(bào)關(guān)聯(lián)，幫助提高人工判定警報(bào)效率約35.12%。該方法的優(yōu)點(diǎn)是在函數(shù)調(diào)用點(diǎn)處，使用警報(bào)關(guān)聯(lián)摘要的方法可以避免重復(fù)分析函數(shù)的行為，能夠提升函數(shù)的分析效率；但該方法同時(shí)存在缺點(diǎn)，即所提的過程間的警報(bào)關(guān)聯(lián)只適用于結(jié)構(gòu)簡單的函數(shù)調(diào)用關(guān)系，對于存在復(fù)雜的函數(shù)調(diào)用關(guān)聯(lián)的警報(bào)，該過程間警報(bào)關(guān)聯(lián)方式并不一定能夠準(zhǔn)確識別出來。

8 結(jié)語

本節(jié)針對過程間存在警報(bào)關(guān)聯(lián)的問題，提出了一種基于警報(bào)關(guān)聯(lián)摘要的過程間警報(bào)關(guān)聯(lián)分析的方法，該方法通過首先對被測程序生成函數(shù)調(diào)用關(guān)系圖，并根據(jù)生成的函數(shù)調(diào)用圖得出函數(shù)體分析順序；接著對函數(shù)生成對應(yīng)的警報(bào)關(guān)聯(lián)摘要；然后對存在函數(shù)調(diào)用關(guān)系進(jìn)行實(shí)例化更新，對存在變化的警報(bào)的符號表達(dá)式進(jìn)行更新；符號表達(dá)式更新完畢后，根據(jù)過程內(nèi)警報(bào)關(guān)聯(lián)方式繼續(xù)進(jìn)行警報(bào)關(guān)聯(lián)判定；最后通過實(shí)驗(yàn)驗(yàn)證本文所提方法可以有效識別過程間警報(bào)關(guān)聯(lián)，該方法可以減少35.12%的人工判定警報(bào)工作量。