饒盛原

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

關(guān)鍵詞： 軟差錯(cuò)； 軟件容錯(cuò)； 檢測和恢復(fù)

中圖分類號：TP3 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2019）04-0080-04

1概述

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

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

2 指令級冗余實(shí)現(xiàn)的軟差錯(cuò)檢測和恢復(fù)

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

2.1 EDDI

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

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

2.2 CFCSS

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

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

2.3 SWIFT

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

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

2.4 SWIFT-R

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

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

3 源代碼級冗余實(shí)現(xiàn)的軟差錯(cuò)檢測和恢復(fù)

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

3.1 ThOR

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

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

3.2 RECOO

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

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

3.3 ED4I

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

4 線程級冗余實(shí)現(xiàn)的軟差錯(cuò)檢測和恢復(fù)

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

4.1 SRMT

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

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

4.2 DAFT

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

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

5 進(jìn)程級冗余實(shí)現(xiàn)的軟差錯(cuò)檢測和恢復(fù)

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

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

6 軟件實(shí)現(xiàn)的軟差錯(cuò)檢測和恢復(fù)技術(shù)比較

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

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

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

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

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

參考文獻(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)編輯：梁書】