[發明專利]一種基于抽象內存模型的數據流分析方法

有效

• 申請號: 201910832877.X
• 申請日: 2019-09-04
• 公開（公告）號: CN110633212B
• 公開（公告）日: 2022-07-26
• 發明（設計）人: 董玉坤;尹文靜;龐善臣;劉浩;張莉
• 申請（專利權）人: 中國石油大學（華東）
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 北京慕達星云知識產權代理事務所(特殊普通合伙) 11465
• 代理人: 曹鵬飛

本發明公開一種面向C程序順序存儲結構靜態分析的抽象內存模型，對于經過預處理后的C程序，采用區間運算與指針分析技術分析C程序中指針訪問順序存儲結構操作的過程，包括：A、對順序存儲結構進行適用于數據流分析的建模，描述順序存儲結構在內存中的抽象表示及指向順序存儲結構的指針變量的指向區域與偏移；B、定義通過指針訪問順序存儲結構的遷移操作，提出安全范圍判別保證操作安全性；C、定義通過指針訪問順序存儲結構的謂詞操作。本發明可實現對順序存儲結構上發生偏移的性質進行有效刻畫，同時通過定義的遷移操作及謂詞操作可準確描述指針訪問順序存儲結構的過程，并保證操作的安全性。

技術領域

本發明屬于程序語義缺陷修復方法技術領域，更具體的說是涉及一種基于抽象內存模型的數據流分析方法。

背景技術

數據流分析一直是軟件測試領域關注的重要問題。它是程序分析中的關鍵技術，通過分析程序狀態信息在控制流圖中的傳播來計算每個靜態程序點(語句)在運行時可能出現的狀態。通過數據流分析，測試人員可以不必實際運行程序就能夠發現程序運行時的行為。數據流分析結果可用于測試用例生成、缺陷檢測等軟件測試領域的重要工作。

數組、malloc動態分配后的連續內存等順序存儲結構在C程序中被大量使用，其結構的復雜性使得無法利用傳統的數據流分析方法對其進行準確分析。傳統的數據流分析方法基于分析和效率折中的考慮，沒有對順序存儲結構進行建模；其次，在程序利用指針訪問順序存儲結構時，大多數現有的數據流分析方法基本只維護了指針的指向信息，沒有討論指針在連續內存中可能發生偏移的數值性質，更未考慮發生偏移時可能存在越界的不安全問題。因此，對C語言中的順序存儲結構進行有效刻畫與描述是數據流分析領域的難點。

因此，如何提供一種基于抽象內存模型的數據流分析方法成為了本領域技術人員亟需解決的問題。

發明內容

有鑒于此，本發明提供了一種基于抽象內存模型的數據流分析方法，主要目的在于通過實現對順序存儲結構的抽象建模，歸納總結C程序中通過指針訪問順序存儲結構的各種操作過程。

為了實現上述目的，本發明采用如下技術方案：

一種基于抽象內存模型的數據流分析方法，包括以下幾個步驟：

A、對順序存儲結構進行適用于數據流分析的建模，描述順序存儲結構在內存中的抽象表示及指向順序存儲結構的指針變量的指向區域與偏移；

B、定義通過指針訪問順序存儲結構的遷移操作，提出安全范圍判別保證操作安全性；

C、定義通過指針訪問順序存儲結構的謂詞操作。

優選的，所述步驟A對順序存儲結構進行適用于數據流分析的建模過程如下：

對于C程序中的一個變量p，當p為數組變量時，其模型表示為Var,Region,Domain，此時取值區間為各數組元素區域信息，其中由某個數組元素索引與其對應區域構成；當p為指針變量時，Domain＝{d₁,d₂,…,d_n}為p指向區域與對應偏移的集合，其中d_i＝＜PtRegion,Offset＞，PtRegion為指針變量p指向的內存對象Var對應區域，且Offset是一個整型表達式，表示偏離指向基址的偏移量對應的整型區間。

優選的，所述步驟B中通過指針訪問順序存儲結構的遷移操作的過程如下：

安全范圍判別是指在執行遷移操作前，對指針變量指向區域偏移將發生的增大或縮小進行預先判定，若超出順序存儲結構的索引下界或上界，則提示out of bounds警告。

優選的，指針訪問順序存儲結構的操作包括值訪問與地址訪問兩種。

優選的，地址訪問的遷移操作分析過程如下：

判斷該操作是否是指針自加或自減操作，