[發(fā)明專利]數(shù)據(jù)變更影響域分析方法

有效

• 申請?zhí)枺?/td>: 201810225165.7
• 申請日: 2018-03-19
• 公開（公告）號: CN108536585B
• 公開（公告）日: 2022-01-11
• 發(fā)明（設(shè)計）人: 牟永敏
• 申請（專利權(quán)）人: 北京信息科技大學(xué)
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 北京東方盛凡知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11562
• 代理人: 宋平

1.一種數(shù)據(jù)變更影響域分析方法，其特征在于，包括如下步驟：

S1，比較變更前后的程序，提取變化函數(shù)以及所述變化函數(shù)內(nèi)的變化數(shù)據(jù)；

S2，根據(jù)所述變化數(shù)據(jù)，獲得關(guān)鍵函數(shù)集合，其中，所述關(guān)鍵函數(shù)集合包括所述變化函數(shù)和受所述變化函數(shù)影響的函數(shù)；

S3，根據(jù)所述關(guān)鍵函數(shù)集合，提取變更函數(shù)調(diào)用路徑；

S4，根據(jù)所述變更函數(shù)調(diào)用路徑，提取全局影響基本路徑集，獲得數(shù)據(jù)變更影響域，其中，所述變更函數(shù)調(diào)用路徑上的函數(shù)包括關(guān)鍵函數(shù)和變更無關(guān)性函數(shù)，對所述關(guān)鍵函數(shù)的局部影響基本路徑集和所述變更無關(guān)性函數(shù)的處理語句進(jìn)行拼接處理，生成程序的全局影響基本路徑集，所述全局影響基本路徑集即為所述數(shù)據(jù)變更影響域，基本路徑集滿足以下性質(zhì)：每條路徑都至少包含一條其他路徑未包含的邊；程序中所有的邊都被基本路徑集中的路徑訪問；程序中的所有的、不屬于基本路徑集的路徑都能夠由基本路徑集中的路徑經(jīng)過線性運算得到；

對所述關(guān)鍵函數(shù)進(jìn)行如下處理，以獲得所述關(guān)鍵函數(shù)的局部影響基本路徑集：

根據(jù)控制流圖自動生成算法生成所述關(guān)鍵函數(shù)的控制流圖；

優(yōu)先遍歷所述關(guān)鍵函數(shù)的所述控制流圖，生成關(guān)鍵函數(shù)的基本路徑集；

對所述關(guān)鍵函數(shù)的基本路徑集進(jìn)行處理，提取覆蓋所述變化數(shù)據(jù)和受所述變化數(shù)據(jù)影響的數(shù)據(jù)的基本路徑集，即所述局部影響基本路徑集；其中，所述步驟S2包括如下步驟：

S21，根據(jù)所述變化數(shù)據(jù)，通過數(shù)據(jù)信息流規(guī)則得到受變化數(shù)據(jù)影響的數(shù)據(jù)，所述步驟S21的具體步驟如下：

數(shù)據(jù)信息流是所要識別的對象集中數(shù)據(jù)的二元關(guān)系，將識別對象集重新劃分為賦值語句、分支語句、循環(huán)語句和函數(shù)調(diào)用語句，這些語句假設(shè)為stmt；則所述數(shù)據(jù)信息流規(guī)則DIFR的表達(dá)式為：

DIFR＝{v0→v1|v0∈stmt,v1∈stmt}

表示語句stmt中的變量v1受變量v0的影響；

賦值語句：

規(guī)則1：v0＝v1；(v0和v1不是指針變量){v1→v0}

規(guī)則2：v0＝v1；(v0和v1是指針變量){v0→v1，v1→v0}

規(guī)則3：v0＝v1；{v0→v1，v1→v0}

規(guī)則4：v0＝⊙(v1,v2…vn)；{v1→v0，v2→v0...vn→v0}

分支語句：

規(guī)則5：if(v0＝＝m){v1＝a}；

else{v2＝b}；{v0→v1，v0→v2}

規(guī)則6：switch(v0){case a:v1＝c；…}，{v0→v1}

循環(huán)語句：

規(guī)則7：while(v0＝＝n){v1＝d；}，{v0→v1}

函數(shù)調(diào)用語句：

規(guī)則8：v0＝fun(v1,v2…vn)；{v1→v0，v2→v0...vn→v0}；

S22，根據(jù)受變化數(shù)據(jù)影響的數(shù)據(jù)，得到受所述變化函數(shù)影響的函數(shù)，所述步驟S22包括：

關(guān)鍵函數(shù)的提取需要分析變化函數(shù)內(nèi)部程序語句；分兩種情況進(jìn)行分析：

1)簡單語句：簡單的函數(shù)調(diào)用語句，提取被調(diào)用函數(shù)的參數(shù)集PS(Parameter Set),若其中，表示空集，CVS表示變更變量集；則把此函數(shù)添加到變化函數(shù)的影響函數(shù)集合中；

2)復(fù)雜語句：即包括選擇結(jié)構(gòu)或循環(huán)結(jié)構(gòu)的程序基本塊，首先提取分支條件或循環(huán)條件中的變量集VS，若此復(fù)雜語句中包含函數(shù)調(diào)用，且其中，表示空集；則把此函數(shù)添加到變化函數(shù)的影響函數(shù)集合中；

所述步驟S3包括：在所述關(guān)鍵函數(shù)集合的基礎(chǔ)上，根據(jù)程序函數(shù)調(diào)用路徑圖提取所述變更函數(shù)調(diào)用路徑。

2.根據(jù)權(quán)利要求1所述的數(shù)據(jù)變更影響域分析方法，其特征在于，通過文本比較工具Beyound Compare進(jìn)行所述步驟S1。

3.根據(jù)權(quán)利要求1所述的數(shù)據(jù)變更影響域分析方法，其特征在于，使用一條語句“int函數(shù)名_v＝常量；”來代替所述變更無關(guān)性函數(shù)，以形成所述變更無關(guān)性函數(shù)的處理語句。