[發明專利]一種表驅動的簽名錯誤檢測算法

在審

• 申請號: 201710367340.1
• 申請日: 2017-05-23
• 公開（公告）號: CN107301123A
• 公開（公告）日: 2017-10-27
• 發明（設計）人: 沈瀟軍;姚一楊;戴波;陳建;孔曉昀;龔小剛;戚偉強;王以良;耿繼樸;陳可;邢雅菲;劉雄;侯麟;毛大鵬;吳翔;琚小明
• 申請（專利權）人: 國網浙江省電力公司信息通信分公司;華東師范大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 上海藍迪專利商標事務所(普通合伙)31215
• 代理人: 徐筱梅,張翔

1.一種表驅動的簽名錯誤檢測算法，其特征在于，該檢測算法包括以下具體步驟：

步驟1：確定所有基本塊，即節點，建立程序P的控制流圖，為每一個節點編號，即基本塊標識號，在控制流圖中以自然數開始，即vi, i=1, 2….N；

步驟2：對每一個節點vi都賦予一個簽名SSi，如果i≠j, 則SSi≠SSj，其中i,j=1,2,…N；每一個簽名 SSi 與相應的基本塊標識vi中的i相等；

步驟3：對每一個vi,i=1,2,3…，進行如下操作：

a）對每一個分支bri,j ，它的前驅節點為vi ，后繼節點為vj；這些分支由一個二維表表示，該二維表稱為CFID[i,j]；在該表中，行i表示前驅節點，列j表示后繼節點；

b）如果分支 bri,j在控制流圖中，將后繼節點的簽名SSj 填入CFID[i,j]對應的位置；否則CFID[i,j]位置應填入0值；

c）Reg寄存器中存儲的全局變量在基本塊每一次執行其檢測指令時都更新一次，以跟蹤程序執行過程中簽名的變化；

d）在基本塊的初始位置插入一條判斷指令，判斷SSi與CFID[Reg,SSi]是否相等，如果相等，則將SSi賦值給Reg，如果不相等，則報錯。

2.根據權利要求1所述的檢測算法，其特征在于，所述二維表是一個二維數組，對應i行j列位置上的數值即為CFID[i,j]，代表控制流中的位置標識和跳轉路徑；行數值i表示前驅節點的標識號，列數值j表示當前節點的標識號。

3.根據權利要求1所述的檢測算法，其特征在于，所述基本塊指的是一串連續的指令，程序從基本塊中的第一條指令開始執行，在執行完最后一條指令后離開基本塊；除了基本塊中的最后一條指令不做要求外，基本塊中的其余指令均不允許為分支指令、跳轉指令或者調用指令。

4.根據權利要求1所述的檢測算法，其特征在于，所述控制流圖由節點集合V={v1,v2,…,vi,…vn}和路徑集合E={e1,e2,…,ei,…,em}組成，控制流圖準確描述程序P的控制流，即程序P表示為P={V,E}；一個節點vi表示一個基本塊，其中i為正整數，表示基本塊在程序中的位置；一條路徑表示從vi到vj的分支bri,j；bri,j代表分支指令，跳轉指令、子程序調用指令或返回指令。