[發明專利]一種基于重構控制流圖的控制流錯誤檢測優化方法

無效

• 申請號: 201010504386.1
• 申請日: 2010-10-12
• 公開（公告）號: CN101944064A
• 公開（公告）日: 2011-01-12
• 發明（設計）人: 譚慶平;李建立;寧洪;徐建軍;周會平;譚蘭芳;徐錫山
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

技術領域

本發明涉及一種控制流錯誤檢測的優化方法，尤其是在空間輻射環境下對由于單粒子效應引起的程序控制流錯誤進行檢測的優化方法。

背景技術

空間探測活動投入大、風險高，對可靠性有著極高的要求。太空中影響空間探測器安全的主要因素是宇宙射線的輻射，因為這些宇宙射線中的高能帶電粒子流會使電子器件出現硬件故障。空間輻射環境對電子器件的影響主要表現為單粒子效應。

普通計算機所使用的芯片一般是商用微處理器COTS（Commercial?Off-the-Shelf），在空間環境中，為了防止空間輻射的影響，一般使用經過特殊工藝設計與加工的微處理器芯片，即抗輻照器件。抗輻照器件主要通過硬件冗余實現容錯，具有很高的可靠性。但是由于其設計非常復雜，研制周期很長，產業規模和產量都很小，價格非常昂貴。由于硬件的冗余，抗輻照器件的芯片面積通常成倍增加，這不僅使芯片成品率下降，也帶來了功耗的迅速增長。而且按照這種方式生產出來的抗輻照器件的性能通常落后于同時代的COTS很多代。COTS由于產量很大且使用廣泛、經過充分的市場競爭，所以一般性能很高，價格相對較低，且任何國家都無法對其進行封鎖和禁運。其缺點是對空間環境比較敏感，容易產生單粒子效應。

計算機發展的歷史表明，很多原本用硬件實現的技術同樣可以用軟件來實現，在COTS上進行面向硬件故障的軟件容錯可以彌補COTS在容錯能力方面的不足。國內外已開展很多實驗探討在空間環境中能否使用以及如何使用COTS。實驗結果表明：在COTS上面向硬件故障的軟件容錯方法所實現的性能，可以比基于抗輻照器件的空間計算機高一個數量級；面向硬件故障的軟件容錯方法可以有效提高基于COTS的空間計算機的可靠性，能夠很好地應對空間輻射的影響，同時還能夠使成本降低。

通過與采用抗輻照器件的硬件容錯方法比較可以發現，基于COTS的軟件容錯方法除可靠性方面比硬件容錯方法略低之外，在性能、成本、功耗和靈活性方面都擁有巨大的優勢。軟件容錯方法包括故障檢測、定位、恢復等過程，其中，故障檢測是故障定位及恢復的基礎。空間輻射環境中的單粒子效應可能導致星載計算機上的寄存器、存儲器、緩存等存儲部位出現故障，也可能導致總線、算術邏輯運算單元、指令譯碼器等功能部件出現故障。這些故障可能致使計算機中的指令序列出現執行順序錯誤或者數據錯誤，前者又稱控制流錯誤。針對數據錯誤和控制流錯誤，現有的軟件容錯方法一般采用不同的故障檢測策略分別對其檢測。現有的針對控制流錯誤的軟件檢測方法大多是采用標簽分析的方法，這類方法的基本步驟是：

第一步，為程序構造控制流圖。構造控制流圖前需要先將程序劃分為基本塊，基本塊是程序中能夠順序執行的指令序列的最大集合，這組指令只有一個入口和一個出口，入口就是第一條指令，出口就是最后一條指令，基本塊中除了最后一條指令可能是跳轉指令外，其它指令都不能是跳轉指令。控制流圖是以基本塊為結點，以基本塊之間存在的跳轉關系為邊的有向圖。劃分出基本塊后即可根據基本塊間固有的控制流關系直接得出控制流圖，因此劃分基本塊是構造控制流圖的關鍵。這一步的具體步驟是：

1.1將程序劃分為基本塊，構建基本塊表。基本塊表存放每個基本塊的信息，包括基本塊編號、入口指令地址和出口指令地址。具體過程為：

1.1.1確定各個基本塊的入口指令，它們是：

l??????程序的第一條指令；或者

l??????條件轉移指令或無條件轉移指令跳轉到的指令；或者

l??????緊跟在條件轉移指令或函數調用后面的指令；或者

l??????被調用函數的第一條指令。

1.1.2?對每個入口指令，確定其對應的出口指令，它們是：

l??????入口指令后除當前入口指令外的第一個入口指令前的指令；或者

l??????入口指令后的第一個轉移指令或函數調用指令；或者

l??????程序的結束指令。

1.1.3?分別將每個入口指令和其對應的出口指令之間的程序塊劃分為一個基本塊。為每個基本塊分配一個基本塊編號，并將基本塊編號和入口指令地址、出口指令地址存入基本塊表。