張 莉 董玉坤 劉 浩 尹文靜

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

1 引言

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

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

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

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

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

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

2）實驗驗證了本文所提方法的有效性，減輕了人工判定警報的工作量，提高了人工判定警報工作的效率。

2 程序語義警報概述與表示

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

2.1 程序語義缺陷

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

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

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

2.2 程序語義警報的表示

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

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

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

2）非關(guān)聯(lián)：如果?Exp(am)=??Exp(an)，若其中一個為誤報，則另一個為真實缺陷，則警報am和警報an存在非關(guān)聯(lián)關(guān)系。

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

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

3 過程間警報傳遞類型

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

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

3.1 鏈式型傳遞關(guān)系

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

圖1 鏈式型傳遞關(guān)系圖

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

若存在多個函數(shù)g2，g3，…，gn調(diào)用同一個函數(shù)g1，并且函數(shù)g1存在警報a，由于函數(shù)g2，…，gn調(diào)用函數(shù)g1引發(fā)新的警報b，c，d等，則警報b，c，d和警報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中存在警報a，函數(shù)q1調(diào)用了多個函數(shù)q2，q3，…，qn，導(dǎo)致因為警報a的傳遞引發(fā)警報b，c，d等的產(chǎn)生，則警報a與警報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 警報關(guān)聯(lián)摘要

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

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

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

針對上述三種類型的影響，本文給出了警報關(guān)聯(lián)摘要模型（Warnings Correlation Summary Model，WCSM）來描述，警報關(guān)聯(lián)摘要模型盡可能詳細地捕獲了所有與警報相關(guān)的函數(shù)行為，警報關(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表示跟警報相關(guān)的一類信息，不同缺陷模式對應(yīng)的警報會對應(yīng)不同的前置約束信息。前置約束信息表示如式（2）。

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

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

2）后置約束信息

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

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

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

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

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

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

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

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

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

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

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

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

（1）針對鏈式型傳遞關(guān)系

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

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

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

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

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

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

7 實驗驗證

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

7.1 實驗平臺

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

圖4 DTSC_Corr工具處理流程圖

7.2 實驗結(jié)果及分析

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

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

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

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

8 結(jié)語

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