基于警報關聯摘要的過程間警報關聯分析

張 莉 董玉坤 劉 浩 尹文靜

（中國石油大學（華東）計算機科學與技術學院 青島 266580）

1 引言

隨著信息技術行業的蓬勃發展，軟件的規模與復雜度也呈現遞增式增長。軟件中存在缺陷難以避免，其中，程序語義缺陷是一類典型的軟件缺陷，程序語義缺陷會導致程序運行時出現系統癱瘓、運算結果不正確、性能降低等問題。

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

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

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

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

1）通過定義警報關聯摘要，獲得每個函數的警報關聯摘要，并利用該摘要實現過程間警報關聯，內存開銷相對比較低；

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

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

警報關聯技術是一種能夠有效減輕警報判定負擔的警報優化技術［8，14～16］。本小節給出警報相關問題的具體分析與說明。

2.1 程序語義缺陷

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

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

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

2.2 程序語義警報的表示

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

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

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

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

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

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

3 過程間警報傳遞類型

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

若警報通過函數調用引發新的警報，導致存在過程間警報關聯。通過分析函數間的調用方式，過程間警報傳遞類型又可以分為鏈式型傳遞關系、匯聚型傳遞關系和發散型傳遞關系三種類型，下面將對這三種類型進行說明。

3.1 鏈式型傳遞關系

若函數f1中存在警報a，函數f1調用函數f2，導致因為警報a的傳遞引發警報b的產生；同時函數f2又調用函數f3，同樣導致警報b的傳遞引發警報c的產生，則警報a、警報b和警報c存在著關聯關系，稱這種為鏈式型傳遞關系（Chain Type Transfer Relationship，ChTR），如圖1所示。

圖1 鏈式型傳遞關系圖

3.2 匯聚型傳遞關系

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

圖2 匯聚型傳遞關系圖

3.3 發散型傳遞關系

若函數q1中存在警報a，函數q1調用了多個函數q2，q3，…，qn，導致因為警報a的傳遞引發警報b，c，d等的產生，則警報a與警報b，c，d存在著關聯關系，稱這種關聯為發散型傳遞關系（Divergence Type Transfer Relationship，DTTR），如圖3所示。

圖3 發散型傳遞關系圖

4 警報關聯摘要

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

針對過程間警報關聯識別問題，本文提出對存在警報的函數生成對應的警報關聯摘要的方法，然后生成被調函數的警報關聯摘要信息，用摘要信息替代其函數調用的展開。

在函數調用過程中，產生的警報可能向其調用者進一步傳遞警報狀態，可能會對調用該函數的上下文信息產生影響，導致調用點上下文環境遷移：1）實參；2）函數返回值；3）全局變量。

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

1）前置約束信息

前置約束信息Pre-constraint表示跟警報相關的一類信息，不同缺陷模式對應的警報會對應不同的前置約束信息。前置約束信息表示如式（2）。

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

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

2）后置約束信息

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

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

5 警報關聯摘要生成及實例化

警報關聯摘要生成步驟如下。首先，得出程序中數據流分析結果calDomain，計算函數返回語句RetVal的符號表達式SExp作為后置約束信息的函數返回值部分，獲取程序中全局變量GloVar的對應的變量var和其符合表達式SExp作為后置約束信息的全局變量部分；對于函數內無法確定的缺陷狀態，構造其變量、符合表達式和其約束信息作為前置約束信息，并向上層調用者傳遞。下面將給出警報關聯摘要的生成算法。

算法1.警報關聯摘要生成算法。

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

6 過程間警報關聯算法實現與分析

在本節中我們將介紹過程間警報關聯的算法與實現，下面是其詳細描述。過程間警報關聯算法步驟如下。

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

2）通過分析函數集合SF中函數間的關系，生成對應的函數調用子圖PFCG'；

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

當某個函數調用該存在警報的函數，根據上下文信息進行實例化，如果存在警報關聯摘要對應的值不一致的情況，進行更新，否則，不更新。

（1）針對鏈式型傳遞關系

若存在警報的函數間是鏈式型傳遞關系類型（ChTR），即函數存在多級調用的情況，則從調用者到被調用者依次更新警報關聯摘要。更新完畢后，根據過程內警報關聯算法［18］繼續判定警報間的關聯關系。

（2）針對匯聚型傳遞關系

若存在警報的函數間是匯聚型傳遞關系（Co-TR），則需要每個主調函數依次對被調函數進行警報關聯摘要更新，并需要分開判斷。

（3）針對發散型傳遞關系

若存在警報的函數間是發散型傳遞關系（DTTR），即一個函數調用了多個函數的情況，則同樣由主調函數對每一個被調函數進行警報關聯摘要更新。更新完畢后，同樣根據過程內警報關聯方式繼續判定警報間的關聯關系。

算法2.過程間警報關聯算法。

7 實驗驗證

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

7.1 實驗平臺

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

圖4 DTSC_Corr工具處理流程圖

7.2 實驗結果及分析

本節將通過實驗來進行驗證本文所提的過程間警報關聯算法的應用效果。本實驗選擇了3種常見的缺陷模式空指針解引用（NPD）、數組越界（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行代碼，其中程序中的函數個數為2414個，調用函數的次數為9017個。其過程間警報關聯數據統計如表1所示。

表1 過程間警報關聯數據統計

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

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

8 結語

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