軟件實現(xiàn)的軟差錯檢測和恢復技術

饒盛原

摘要：軟差錯被認為是現(xiàn)代微處理器可靠性所面臨的最主要的挑戰(zhàn)，由于軟件實現(xiàn)的軟差錯檢測和恢復技術不需要額外的物理資源并能適用于現(xiàn)在已存在的處理器，因此受到了眾多科研人員的關注。該文按照不同的實現(xiàn)層級對現(xiàn)有的一些經(jīng)典技術方案進行了收集，簡要介紹其原理與實驗效果，并在文末對不同層級技術的優(yōu)缺點進行了比較分析。

關鍵詞： 軟差錯； 軟件容錯； 檢測和恢復

中圖分類號：TP3 文獻標識碼：A 文章編號：1009-3044（2019）04-0080-04

1概述

隨著芯片密度的不斷增加，現(xiàn)代微處理器更容易受到各種干擾而產(chǎn)生軟差錯，雖然沒有造成硬件的永久性故障，但是軟差錯的發(fā)生很有可能會影響到程序的正常運行。針對軟差錯的檢測和恢復研究已開展了很多年，也產(chǎn)生了很多可用的技術，這些技術按照實現(xiàn)方式可以分為硬件實現(xiàn)的和軟件實現(xiàn)的兩類。由于硬件實現(xiàn)的技術需要對硬件的設計進行修改或增加特殊的檢測和恢復設備，需要較高的實現(xiàn)成本。而軟件實現(xiàn)的方式不需要額外設備，并且能較好地支持現(xiàn)有處理器等優(yōu)點，吸引了眾多學者對其進行研究。

本文主要對近20年來經(jīng)典的軟件實現(xiàn)的軟差錯檢測和恢復技術進行了總結，并按照不同的實現(xiàn)層級，分為指令級、源代碼級、線程級和進程級等幾大類

2 指令級冗余實現(xiàn)的軟差錯檢測和恢復

經(jīng)過數(shù)十年的研究，眾多學者提出了多項通過指令冗余實現(xiàn)的軟差錯檢測和恢復技術，其中Stanford大學CRC（Center for Reliable Computing）中心于2002年提出的針對軟差錯造成的數(shù)據(jù)流錯誤的EDDI（Error Detection by Duplicated Instructions）[1]方法和針對軟差錯造成的控制流錯誤的CFCSS（Control Flow Checking by Software Signatures） [2]方法是其中的典型代表；在此之后Princeton大學的Reis G A等人結合EDDI和CFCSS方法提出了同時具有檢測數(shù)據(jù)流錯誤和控制流錯誤的SWIFT（Software Implemented Fault Tolerance） [3]方法；為了能夠對檢測到的軟差錯進行恢復，Reis G A等人又在SWIFT的基礎上實現(xiàn)了SWIFT-R[4]方法。最近兩年，Didehban M等人針對SWIFT和SWIFT-R中存在的一些缺陷進行優(yōu)化，分別實現(xiàn)了nZDC[5]方法和NEMESIS[6]方法。這些方法的發(fā)展過程如圖1所示，下面將對這些方法進行介紹。

2.1 EDDI

EDDI是在程序編譯時對程序的指令進行復制，將原程序的每條指令（Master Instruction， MI）都復制成一個副本指令（Shadow Instruction， SI）加入原程序當中，然后在存儲和分支指令之前加入比較指令（Comparison Instruction， CI），用以比較MI和SI的執(zhí)行結果，如果執(zhí)行結果不一致即表示檢測到程序數(shù)據(jù)流錯誤。一段經(jīng)EDDI處理的加法指令示例如圖2所示。

通過注入單粒子翻轉故障，將未經(jīng)過EDDI方法處理過的原程序和經(jīng)過EDDI方法處理后的程序進行了比較，發(fā)現(xiàn)經(jīng)過EDDI方法處理后的程序，將程序的平均出錯率由20%降到了1.5%。同時EDDI也使得處理后的程序由于程序類型的不同，執(zhí)行時間增加了13%～105.9%，程序的大小增加了44%～113%。

2.2 CFCSS

CFCSS是在程序編譯時，根據(jù)每一個基本塊中除最后一條指令外，塊內順序執(zhí)行指令這一原則，將程序劃分為多個基本塊，為每一個基本塊生成一個唯一的數(shù)字標簽S（Signature），并且在每個基本塊的開始的地方加入兩條特殊指令。其中一條指令負責根據(jù)剛剛執(zhí)行完的基本塊和下一個要執(zhí)行的基本塊的S生成新的動態(tài)標簽G，并由一個名為GSR（General Signature Register）的寄存器進行保存，另一條指令負責將G與當前基本塊的S進行比較，如果不一致則表示檢測到程序控制流的錯誤。

CFCSS是一種比較高效的檢測方法，只需要在原程序中插入較少的檢測指令就可以檢測到軟差錯引起的控制流錯誤。但是CFCSS方法的主要缺陷在于不能檢測出基本塊內部發(fā)生的控制流錯誤，同時由于動態(tài)標簽G的生成算法在生成過程中可能會導致G與錯誤基本塊的S一致，從而發(fā)生檢測混淆和檢測出錯的現(xiàn)象，這也是CFCSS算法的一個缺點（針對這一缺點，一些學者提出了ICFCSS等方法對其進行改進）。故障注入實驗的結果表明：在未經(jīng)過CFCSS方法處理的程序中，33.7%的分支故障會導致程序出錯，經(jīng)過CFCSS方法處理后的程序則只有3.1%的分支故障會導致程序出錯。同時CFCSS也使得處理后的程序由于程序類型的不同，執(zhí)行時間增加了16%～69%，程序大小增加了26%～64%。

2.3 SWIFT

EDDI與CFCSS結合能夠檢測到軟差錯導致的數(shù)據(jù)流錯誤和控制流錯誤，SWIFT將EDDI和CFCSS進行了整合，并對這兩種方法進行了優(yōu)化。其中最主要的改進在于SWIFT認為存儲器已經(jīng)通過ECC或奇偶校驗碼等機制進行了保護，從而不考慮內存發(fā)生故障的情況。因此，SWIFT將從內存讀取出的數(shù)據(jù)復制一份，然后與EDDI一樣插入副本指令進行冗余計算，再在存儲指令之前將所存數(shù)據(jù)進行一致性的檢測。和EDDI相比，SWIFT只使用了一半的內存，訪問內存的操作也減少了一般，因此對性能有了很大的提升。針對控制流的錯誤，SWIFT采用的方法與CFCSS類似，不同之處在于SWIFT使用了一個專門的寄存器“sigoff”來保存在生成G過程中產(chǎn)生的中間值。但是SWIFT同樣沒有解決無法檢測出基本塊內部的控制流錯誤這一缺點。

通過注入單粒子翻轉故障，將通過SWIFT方法處理后的程序和經(jīng)過EDDI+ECC+CFE方法處理后的程序進行了比較，發(fā)現(xiàn)經(jīng)過SWIFT方法處理后的程序能夠檢測到70%的故障，同時程序大小平均比采用EDDI+ECC+CFE方法的程序小15%，執(zhí)行時間也比采用EDDI+ECC+CFE的程序少51%。

2.4 SWIFT-R

SWIFT方法只具有軟差錯的檢測能力，而SWIFT-R在SWIFT的基礎上使其具備了恢復能力。SWIFT-R將指令的冗余變成了三份，然后對三個版本指令的執(zhí)行結果進行比較，出現(xiàn)兩份或以上一致的結果則判斷為正確的結果，然后對錯誤副本的指令執(zhí)行結果進行恢復。

通過注入單粒子翻轉故障，發(fā)現(xiàn)SWIFT-R方法能夠減少89.4%的故障，同時將程序的執(zhí)行時間增加了99%。

3 源代碼級冗余實現(xiàn)的軟差錯檢測和恢復

由于源代碼級冗余實現(xiàn)軟差錯檢測和恢復會產(chǎn)生過多冗余代碼，并且使得性能損失嚴重，通過此方法實現(xiàn)的軟差錯檢測和恢復的研究并不多。典型性的方法有意大利都靈理工大學的A Benso等人于2000年提出的RECOO[8]、M Rebaudengo等人于2001年提出的ThOR[7]以及Stanford大學CRC實驗室于2002提出的ED4I[9]。這些方法的發(fā)展過程如圖4所示，下面將對這些方法進行介紹。

3.1 ThOR

ThOR在源程序預編譯時復制源程序中每一條語句，然后加入將計算結果進行比較的語句，用于判斷是否出現(xiàn)錯誤。ThOR的基本轉換規(guī)則如下：1.對每一個變量都進行復制；2.每一個對于變量的讀、寫等操作同樣需要在副本上進行；3.在對變量進行讀、寫之后需要將其與副本進行比較來檢測它的正確性。此外，原程序中的函數(shù)調用參數(shù)和返回值也要進行冗余備份。

通過注入單粒子翻轉故障，發(fā)現(xiàn)經(jīng)過ThOR方法處理的程序，能夠檢測到64.4%的數(shù)據(jù)流錯誤。與未經(jīng)過ThOR方法處理的程序相比，程序的執(zhí)行時間平均延長了3.62倍，程序的大小平均增加了3.89倍。

3.2 RECOO

RECOO是一個針對C和C++程序的編譯工具，其目標是檢測發(fā)生在內存、寄存器等存儲部件中的數(shù)據(jù)錯誤。該工具的基本思想是通過復制變量來實現(xiàn)錯誤的檢測：變量每次被賦予新值的時候均會產(chǎn)生其副本變量，然后在對每一個變量進行讀操作的時候或者該變量不再使用時，將變量與其副本進行比較。在對變量進行復制的時候，可以考慮根據(jù)考慮變量的存在時間和對其他變量對其的依賴性計算其可靠性權重，然后可以根據(jù)可靠性權重決定是否對該變量進行復制，以減少程序的大小和縮短程序執(zhí)行的時間。

故障注入實驗的結果表明：當使用RECOO復制程序中30%的變量時，能減少68%的FSVs（Fail-Silent Violations），復制70%的變量時，能減少89%的FSVs。同時，復制30%變量時，程序的執(zhí)行時間增加6%，程序的大小增加18%；復制所有變量時，程序的執(zhí)行時間增加16%，程序的大小增加37%。

3.3 ED4I

ED4I利用了數(shù)據(jù)多樣性來檢測程序錯誤。其通過將程序中的變量和常量同時乘以一個相同的多樣性因子k，使其轉換為具有相同功能的不同程序，由另一個同時運行的程序比較他們的結果或是在程序執(zhí)行結束時比較兩個版本的程序輸出結果之間是否相差k倍。k的取值對ED4I的效果產(chǎn)生很大的影響，實驗證明當k取-2 時取得了較為理想的效果。

4 線程級冗余實現(xiàn)的軟差錯檢測和恢復

隨著多核平臺的迅猛發(fā)展，出現(xiàn)了一些多核平臺下基于軟件或硬件實現(xiàn)的軟差錯檢測和恢復方法，軟件實現(xiàn)的方法中具有典型性的有Intel公司于2007年提出的SRMT（Software-based Redundant Multi-Threading） [10]和Princeton大學的Yun Zhang等人于2012年提出的DAFT（Decoupled Acyclic Fault Tolerance） [11]。這些方法的發(fā)展過程如圖7所示，下面將對這些方法進行介紹。

4.1 SRMT

SRMT是在編譯的過程中為程序生成一個主線程（leading thread）和一個伴隨線程（trailing thread），兩個線程執(zhí)行的計算操作相同。同時，主線程除了執(zhí)行原有的計算操作之外，還需要與伴隨線程進行通信；而伴隨線程除了重復執(zhí)行主線程的計算操作之外，還需要在某些恰當?shù)奈恢脤蓚€線程的執(zhí)行結果進行比較。對于訪問共享內存和執(zhí)行I/O操作的系統(tǒng)調用等不可重復的計算全部都有主線程完成，但是這種操作執(zhí)行之前需要獲知伴隨線程的比較結果，從而保證此時線程狀態(tài)的正確性。經(jīng)SRMT處理后的程序執(zhí)行過程如圖8所示。

通過注入單粒子翻轉故障，發(fā)現(xiàn)SRMT對于基準程序集SPEC2000中的整型和浮點程序的故障覆蓋率為99.98%和99.6%，具有非常高的覆蓋率。但是由于主線程和伴隨線程需要大量的通信，使用多核處理器的硬件通信隊列將使得程序執(zhí)行的時間增加19%，使用軟件實現(xiàn)的通信隊列將使得程序執(zhí)行的時間增加186%。

4.2 DAFT

DAFT的基本思路與SRMT相同，但是DAFT中采用了許多消除線程間進行同步檢查的操作，如采用特殊的異常處理機制區(qū)分異常和軟差錯、對IO的內存映射地址著重保護等方法減少主線程的等待，使主線程能夠順暢運行，從而降低了程序運行時間。

通過注入單粒子翻轉故障，發(fā)現(xiàn)經(jīng)DAFT處理后的程序在SPEC2000和SPEC2006進行實驗時，運行時間平均增加了38%，程序大小平均變?yōu)樵瓉淼?.4倍，同時還有99.93%的故障覆蓋率。

5 進程級冗余實現(xiàn)的軟差錯檢測和恢復

在多核平臺下，還可以在進程級實現(xiàn)軟差錯的檢測和恢復。A Shye等人于2009年提出的方法PLR[12]就是一種典型的進程級冗余實現(xiàn)的軟差錯檢測和恢復方法。PLR的整體結構如圖9所示。PLR方法在程序被執(zhí)行前創(chuàng)建一個監(jiān)控（Monitor）進程，然后把應用進程復制n次（n為2時進行故障檢測，n等于3時可以進行故障的檢測和修復），其中一個為主進程（Master Process），其他為從屬進程（Slave Processes）。在實際運行過程中，只有主線程能夠通過syscall emulation層執(zhí)行真正的系統(tǒng)調用，從屬進程執(zhí)行仿真的系統(tǒng)調用。syscall emulation層還實現(xiàn)錯誤檢測和恢復，所有的系統(tǒng)調用參數(shù)都需要進行比較以確保正確，系統(tǒng)調用的返回結果要被復制給每一個從屬進程。在將進程進行復制之后，原進程就成了一個名義進程（Figurehead Process），它不執(zhí)行實際的程序，只是在等待冗余進程執(zhí)行結束，或者是在monitor的幫助下將收到的外部信號廣播給冗余的進程。

針對軟差錯的檢測，PLR是通過以下三種方式：1）在syscall emulation層，通過比較輸出結果，將會檢測到軟差錯導致的不正確的輸出。2）通過Watchdog超時檢測控制流出錯誤，如軟差錯導致的控制流錯誤，調用了錯誤的系統(tǒng)調用，在syscall emulation層中，通過與其他進程進行比較便能發(fā)現(xiàn)出現(xiàn)錯誤；或是軟差錯導致其中一個進程進入死循環(huán)等進程掛起情況。在下一個系統(tǒng)調用期間，除了掛起進程之外的所有進程都將結果傳送至syscall emulation層中，最終會導致超時。3）軟差錯導致非法指令、總線錯誤等故障導致的程序失效，這些程序失效產(chǎn)生的外部信號將會由名義進程進行檢測。故障注入實驗的結果表明，PLR的軟差錯檢測和恢復能力都能達到硬件容錯技術的水平，對于四路的對稱多處理器（SMP），PLR只導致程序運行的時間增加了16.9%。

6 軟件實現(xiàn)的軟差錯檢測和恢復技術比較

根據(jù)對軟件實現(xiàn)的軟差錯檢測和恢復技術的介紹，我們分別從能處理的錯誤類型、針對軟差錯的檢測和恢復能力，還有其對性能的影響等方面對上述方法進行比較。

指令級冗余實現(xiàn)的軟差錯檢測和恢復技術大多都具有較強的檢錯能力，并且這種方法的性能開銷相對適中。由于這類方法進行的是指令級的冗余，因此該方法能夠對軟錯誤進行精確定位，進而以細粒度的方式來進行軟錯誤恢復。這些優(yōu)點也是此類方法被廣泛研究的原因。

源代碼冗余實現(xiàn)的軟差錯檢測和恢復技術的檢錯能力較為一般。同時，由于這類方法進行冗余的粒度較大，因此性能開銷也比較大，并且不能精確定位軟差錯的發(fā)生，不過該方法是在源代碼級別上進行的冗余，因此其實現(xiàn)也相對較為容易。

線程級冗余實現(xiàn)的軟差錯檢測和恢復技術的故障覆蓋率較高，但是這種方法需要多核處理器的支持，因此只能應用與多核平臺。此外由于這類方法中主線程和伴隨線程需要頻繁進行通信，因此對系統(tǒng)的性能有較大的影響。同時，由于這類方法是在線程級別進行軟差錯的檢驗，因此在考慮對此類方法的添加軟差錯恢復能力的時候，只能通過粗粒度的方法進行錯誤恢復。

進程級冗余實現(xiàn)的軟差錯檢測和恢復技術的故障覆蓋率也比較高，但是這種方法同樣只能應用與多核平臺。同時，這類方法針對軟差錯的恢復，也只能在進程級別進行恢復。

參考文獻：

[1] Oh N， Shirvani P P， Mccluskey E J. Error detection by duplicated instructions in super-scalar processors[J]. IEEE Transactions on Reliability， 2002， 51（1）：63-75.

[2] Oh N， Shirvani P P， Mccluskey E J. Control-flow checking by software signatures[J]. IEEE Transactions on Reliability， 2002， 51（1）：111-122.

[3] Reis G A， Chang J， Vachharajani N， et al. SWIFT： software implemented fault tolerance[C]// International Symposium on Code Generation and Optimization. IEEE， 2005.

[4] Chang J， Reis G A， August D I. Automatic Instruction-Level Software-Only Recovery[J]. IEEE Micro， 2007， 27（1）：83-92.

[5] Didehban M， Shrivastava A. nZDC： a compiler technique for near zero silent data corruption[C]// Design Automation Conference. IEEE， 2016.

[6] Didehban M， Shrivastava A， Lokam S R D. NEMESIS： A software approach for computing in presence of soft errors[C]// 2017 IEEE/ACM International Conference on Computer-Aided Design （ICCAD）. ACM， 2017.

[7] Rebaudengo M， Reorda M S， Torchiano M， et al. A source-to-source compiler for generating dependable software[C]// IEEE International Workshop on Source Code Analysis & Manipulation. IEEE， 2001.

[8] Benso A， Chiusano S， Prinetto P， et al. A C/C++ Source-to-Source compiler for dependable applications[C]// International Conference on Dependable Systems & Networks. IEEE， 2000.

[9] Oh N， Mitra S， Mccluskey E J. ED4I： Error detection by diverse data and duplicated instructions[J]. IEEE Transactions on Computers， 2002， 51（2）：180-199.

[10] Wang C， Kim H S， Wu Y， et al. Compiler-Managed Software-based Redundant Multi-Threading for Transient Fault Detection[C]// International Symposium on Code Generation & Optimization. IEEE Computer Society， 2007.

[11] Zhang Y， Lee J W， Johnson N P， et al. DAFT： Decoupled Acyclic Fault Tolerance[C]// International Conference on Parallel Architectures & Compilation Techniques. IEEE， 2010.

[12] Shye A， Blomstedt J， Moseley T， et al. PLR： A Software Approach to Transient Fault Tolerance for Multicore Architectures[J]. IEEE Transactions on Dependable and Secure Computing， 2009， 6（2）：135-148.

【通聯(lián)編輯：梁書】