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

在審

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

技術領域

本發明涉及純軟件錯誤檢測技術領域，具體的說是一種表驅動的簽名錯誤檢測算法(EDSS)，應用于合法的分支、不合法的分支以及帶有兩個共享分支扇入節點的非法分支等的錯誤檢測。

背景技術

隨著技術的發展，微處理器性能的改善將越來越依賴于體積更小、速度更快的晶體管，并同時實現低閾值電壓和更加嚴格的噪聲余量。然而，這種對改善性能、降低功耗的常規需求卻常常導致很多可靠性問題的出現。不同于制造與設計性錯誤等頻繁產生的錯誤，臨時性錯誤（也常被稱作軟錯誤），源于諸如電磁干擾、電壓毛刺或高能量粒子等的環境影響，常常會導致不可預測的行為。最典型的軟錯誤是單粒子翻轉（SEU），該錯誤指的是發生在順序邏輯以及單粒子瞬變（SET）中的位翻轉，容忍這些錯誤最首要和最重要的步驟就是檢測出這些錯誤，目前已有相當多的錯誤檢測技術。

錯誤檢測可以通過純硬件方式、軟硬件結合方式以及純軟件方式得以實現。一種常用的純硬件檢錯方式運用了看門狗協處理器，該處理器通過監測外部總線和主處理器的行為，實現并發的系統級錯誤檢測，但卻導致了時間和面積開銷的增大，并且隨著具有內部高速緩存和現代流水線技術的微處理器的廣泛應用，這種純硬件檢錯方式已經顯得不必要了。現在用于錯誤檢測的軟硬件混合型的檢錯方式也有很多，例如Argus和CRAFT。Argus基于馮諾依曼型處理器核，可檢測出核中除輸入輸出、異常、中斷部分的其他錯誤。然而，包括通過純軟件簽名的控制流檢測（CFCSS）、通過斷言的控制流檢測（ACFC）、運用斷言的增強型的控制流檢測（ECCA）、通過冗余指令的錯誤檢測（EDDI）等在內的純軟件處理方法，比上述這兩種概念運用的更加廣泛，因為這些純軟件檢錯方式不要求特定的硬件設備提供支持。ACFC在執行過程中賦予每一個基本塊一個奇偶校驗位，可檢測出奇偶性錯誤；EDDI通過復制指令，并通過插入合適的檢測指令進行驗證，但這種方法易導致代碼容量增加近100%以及性能方面的損失。

發明內容

本發明的目的是提供一種表驅動的簽名錯誤檢測算法EDSS，該算法運用CFID表能檢測出控制流圖中非法跳轉錯誤，對二維表使用的要求也較為簡單。當出現非法跳轉時，通過檢測賦予變量Reg的簽名和表中存儲的目標節點的簽名，控制流錯誤能被可靠檢測出。根據這種方法，共享多于兩個扇入節點導致的非法指令跳轉錯誤也可由該算法得以檢測。該算法良好的解決了合法的分支、不合法的分支以及帶有兩個共享分支扇入節點的非法分支等的錯誤檢測問題。

本發明的目的是這樣實現的：

一種表驅動的簽名錯誤檢測算法，特點是該檢測算法包括以下具體步驟：

步驟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）在基本塊的初始位置插入一條判斷指令，“if SSi≠CFID[Reg,SSi] error else Reg=SSi”，即判斷SSi與CFID[Reg,SSi]是否相等，如果相等，則將SSi賦值給Reg，如果不相等，則報錯。

所述二維表是一個二維數組，對應i行j列位置上的數值即為CFID[i,j]，代表控制流中的位置標識和跳轉路徑；行數值i表示前驅節點的標識號，列數值j表示當前節點的標識號；

所述基本塊指的是一串連續的指令，程序從基本塊中的第一條指令開始執行，在執行完最后一條指令后離開基本塊；除了基本塊中的最后一條指令不做要求外，基本塊中的其余指令均不允許為分支指令、跳轉指令或者調用指令。