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

有效

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

1.一種基于抽象內存模型的數據流分析方法，具體用于面向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中指針訪問順序存儲結構的遷移操作包括地址訪問，所述地址訪問的遷移操作分析過程如下：

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

若是，則確定自加或自減符號，根據變量指向區域與偏移確定后一個或前一個對象x；

若否，則判斷是否為數組變量或指針變量或數組元素取地址與整型表達式的加減操作；若否，分析結束；若是，則確定整型表達式的值，根據數組變量或指針變量或數組元素取地址確定右端對象x；

判斷對象x是否存在，

若不存在，則提示out of bounds警告后，分析結束；

若存在，則判斷對象x是否已經抽象表示；若是，則左端更新符合表達式、基址、指向區域、偏移區間后，分析結束；若否，則先對對象x進行抽象建模，再左端更新符合表達式、基址、指向區域、偏移區間后，分析結束。

2.根據權利要求1所述的一種基于抽象內存模型的數據流分析方法，其特征在于，所述步驟B中通過指針訪問順序存儲結構的遷移操作的過程如下：

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

3.根據權利要求1所述的一種基于抽象內存模型的數據流分析方法，其特征在于，指針訪問順序存儲結構的遷移操作還包括值訪問。

4.根據權利要求3所述的一種基于抽象內存模型的數據流分析方法，其特征在于，值訪問的遷移操作分析過程如下：

判斷該操作是否為指針引用順序存儲結構元素操作，

若否，則先確定指針變量當前指向區域對應對象，然后對指針變量指向對象的取值區間進行區間并操作，再將生成的新區間賦值給左端變量后，分析結束；

若是，則先確定指針變量當前指向區域與偏移，然后引用順序存儲結構元素，再判斷x是否存在；

若不存在，則提示out of bounds警告后，分析結束；

若存在，則判斷對象x是否已經抽象表示；若是，則將生成的新區間賦值給左端變量后，分析結束；若否，則先對x進行抽象建模，再將生成的新區間賦值給左端變量后，分析結束。

5.根據權利要求1所述的一種基于抽象內存模型的數據流分析方法，其特征在于，謂詞操作分析過程如下：

先確定關系符號左右兩端對象x、y，再判斷x、y是否都存在，

若否，則分析結束；

若是，則判斷x、y是否存在共同基址，

若不存在，則分析結束；

若存在，則先取出滿足兩端存在共同基址的部分m、n，對相應的指針變量進行指向區域和偏移區間的更新，再判斷m、n的偏移區間是否全部或部分滿足關系；

若否，則分析結束；

若是，則取出此時指針變量對應的指向區域與偏移區間后，分析結束。