[發(fā)明專利]多重循環(huán)的數(shù)據(jù)流分析方法、系統(tǒng)、設(shè)備及存儲介質(zhì)

在審

• 申請?zhí)枺?/td>: 202011595969.X
• 申請日: 2020-12-30
• 公開（公告）號: CN112286831A
• 公開（公告）日: 2021-01-29
• 發(fā)明（設(shè)計）人: 朱宏杰;周亮;方帥;王杰;宋小芹;左海峰
• 申請（專利權(quán)）人: 中國電力科學研究院有限公司
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06F16/901
• 代理公司: 北京中巡通大知識產(chǎn)權(quán)代理有限公司 11703
• 代理人: 文驪鹍

本發(fā)明公開了一種多重循環(huán)的數(shù)據(jù)流分析方法、系統(tǒng)、設(shè)備及存儲介質(zhì)，包括：對待分析數(shù)據(jù)流的值依賴圖進行全局循環(huán)摘要提取；以提取的全局循環(huán)摘要為基礎(chǔ)構(gòu)建狀態(tài)圖；根據(jù)狀態(tài)圖求解待分析數(shù)據(jù)流的循環(huán)執(zhí)行次數(shù)，該方法、系統(tǒng)、設(shè)備及存儲介質(zhì)能夠準確求解數(shù)據(jù)流的循環(huán)執(zhí)行次數(shù)。

技術(shù)領(lǐng)域

本發(fā)明屬于軟件分析中的靜態(tài)分析領(lǐng)域，涉及一種多重循環(huán)的數(shù)據(jù)流分析方法、系統(tǒng)、設(shè)備及存儲介質(zhì)。

背景技術(shù)

數(shù)據(jù)流分析指在控制流圖的基礎(chǔ)上通過迭代分析得到感興趣的數(shù)據(jù)流結(jié)果，包括可達定義分析、活躍變量分析、可用表達式分析等。這些分析是建立在劃分好基本塊和流圖的基礎(chǔ)上，通過在控制流圖中的迭代、傳遞和合并完成對流圖中不動點狀態(tài)的計算。

Stanford大學的YichenXie及其合作者關(guān)于溢出漏洞檢測中循環(huán)次數(shù)求解問題，提出了模擬運行的方案。在處理循環(huán)時，程序模擬運行被檢測程序的循環(huán)內(nèi)代碼，在循環(huán)變量符合循環(huán)終止條件時停止運行循環(huán)，統(tǒng)計循環(huán)運行次數(shù)，其缺點在于：采用模擬執(zhí)行的方式計算循環(huán)不動點，效率十分低，大部分循環(huán)的執(zhí)行狀況在進行程序靜態(tài)分析時無法被模擬執(zhí)行完全。以此方案進行的缺陷檢測，無法解決含有較復雜循環(huán)的緩沖區(qū)溢出漏洞檢測問題，檢測時間長、精度差、缺陷漏報率高。

另外，Marple中對每個循環(huán)都設(shè)置一個固定的迭代次數(shù)，簡單推測循環(huán)可能的執(zhí)行次數(shù)，這種方法計算速度非常快，解決了模擬運行會陷入死循環(huán)的問題。其缺點在于：指定循環(huán)次數(shù)僅能滿足效率需求，錯誤率非常高，給循環(huán)內(nèi)變量取值計算引入很多的誤差。

使用靜態(tài)分析技術(shù)檢測緩沖區(qū)溢出漏洞一般遵循以下步驟：(1) 選取合適的分析模型對目標代碼進行建模 (2) 在模型中尋找脆弱性結(jié)點（可能發(fā)生溢出漏洞的結(jié)點）(3)在結(jié)點附近作進一步分析，提取信息生成判斷約束，使用約束求解工具 判斷溢出是否發(fā)生。生成判斷溢出是否發(fā)生的約束需要進行區(qū)間的結(jié)果。

在值依賴圖上進行的區(qū)間分析可以很好地處理流敏感信息，對不含跳轉(zhuǎn)的程序得出精確的結(jié)果。在實際程序中，大部分運行過程是在循環(huán)中完成的，以上區(qū)間分析過程無法對循環(huán)進行處理。現(xiàn)有的數(shù)據(jù)流區(qū)間分析方法處理循環(huán)是困難的，一般只能跳過或者模擬一定次數(shù)的運算。對于多重嵌套的循環(huán)，此類近似方法也失去了效果，其主要問題在于無法準確求解循環(huán)的執(zhí)行次數(shù)。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服上述現(xiàn)有技術(shù)的缺點，提供了一種多重循環(huán)的數(shù)據(jù)流分析方法、系統(tǒng)、設(shè)備及存儲介質(zhì)，該方法、系統(tǒng)、設(shè)備及存儲介質(zhì)能夠準確求解數(shù)據(jù)流的循環(huán)執(zhí)行次數(shù)，實現(xiàn)數(shù)據(jù)流分析。

為達到上述目的，本發(fā)明所述的多重循環(huán)的數(shù)據(jù)流分析方法包括：

對待分析數(shù)據(jù)流的值依賴圖進行全局循環(huán)摘要提取；

以提取的全局循環(huán)摘要為基礎(chǔ)構(gòu)建狀態(tài)圖；

根據(jù)狀態(tài)圖求解待分析數(shù)據(jù)流的循環(huán)執(zhí)行次數(shù)，根據(jù)待分析數(shù)據(jù)流的循環(huán)執(zhí)行次數(shù)進行數(shù)據(jù)流分析。

提取的全局循環(huán)摘要包括值依賴圖的值依賴條件中所有條件變量以及與條件變量相關(guān)的節(jié)點與邊形成的約束條件。

所述狀態(tài)圖中記錄有循環(huán)層層數(shù)變化進行狀態(tài)轉(zhuǎn)移時的約束條件、觸發(fā)條件以及條件變量在狀態(tài)轉(zhuǎn)移后的賦值。

對待分析數(shù)據(jù)流的值依賴圖進行全局循環(huán)摘要提取之前還包括：獲取對待分析數(shù)據(jù)流的值依賴圖，對待分析數(shù)據(jù)流的值依賴圖進行簡化。

對值依賴圖進行簡化的具體過程為：

對值依賴圖中的所有條件變量篩選，僅保留與值依賴條件中條件變量相關(guān)的節(jié)點及邊，刪除與值依賴條件中條件變量無關(guān)的節(jié)點及邊。

以提取的全局循環(huán)摘要為基礎(chǔ)構(gòu)建狀態(tài)圖的具體過程為：

提取全局循環(huán)摘要中記錄的所有循環(huán)變量值轉(zhuǎn)化路徑，以各條循環(huán)變量值轉(zhuǎn)化路徑作為狀態(tài)節(jié)點構(gòu)建狀態(tài)圖。