基于指令級冗余的密碼流處理器并發(fā)錯誤檢測方法

戴 強 戴紫彬 王壽成 李功麗 李 偉

(中國人民解放軍信息工程大學(xué) 河南 鄭州 450001)

0 引 言

可重構(gòu)分組密碼流處理器RBCSP(Reconfigurable Block Cipher Stream Processor)[1]是一種新型的高效能分組密碼處理器，可在資源受限條件下實現(xiàn)多種分組密碼算法。然而，由環(huán)境因素引起的自然故障[2]與故障攻擊注入的惡意故障[3]，將極大降低RBCSP的可靠性，并可能導(dǎo)致密鑰泄露[4]。并發(fā)錯誤檢測能夠有效檢測自然故障[5]，也是抵抗故障攻擊的主要手段之一[4]，但錯誤檢測機制的引入不可避免會帶來硬件開銷增大、算法實現(xiàn)性能下降等消極影響。如何為RBCSP設(shè)計低開銷的并發(fā)錯誤檢測機制，使處理器具有較高的故障檢測能力，是亟待解決的問題。

RBCSP 基于流體系架構(gòu)實現(xiàn)，其核心級運算簇采用VLIW(Very Large Instruction Word)結(jié)構(gòu)。目前面向VLIW處理器的軟錯誤檢測方法多采用指令級冗余技術(shù)[6-10]實現(xiàn)。指令級冗余依靠軟件技術(shù)、以較少或零硬件開銷實現(xiàn)冗余執(zhí)行，其核心思想是以復(fù)制指令填充空閑槽(NOP指令)，可有效減少錯誤檢測帶來的性能損失。文獻[6]在指令執(zhí)行的當(dāng)前時鐘周期，利用VLIW處理器中空閑功能單元實現(xiàn)冗余操作，其性能開銷為0，但錯誤檢測能力較弱。文獻[7]在文獻[6]的基礎(chǔ)上提出通過降低指令級并行度實現(xiàn)自適應(yīng)的指令復(fù)制方法。相比文獻[6]，該方法可實現(xiàn)性能與錯誤檢測能力的折中。文獻[8]提出的指令復(fù)制算法，根據(jù)指令序列中指令出現(xiàn)的先后順序依次復(fù)制指令。文獻[9]通過修改譯碼級電路、調(diào)整指令格式，實現(xiàn)了指令的動態(tài)復(fù)制，有效減少了代碼規(guī)模。然而該方法的指令復(fù)制范圍僅限于指令當(dāng)前所在時鐘周期與下一時鐘周期，導(dǎo)致其性能開銷較文獻[9]有所增加。文獻[10]采用純軟件技術(shù)，在空閑槽插入復(fù)制指令與檢查指令實現(xiàn)錯誤檢測，其硬件開銷為0，但性能開銷較大。

上述針對VLIW處理器的指令復(fù)制方法，無法適配或者高效適配于RBCSP。因此，本文面向RBCSP，依據(jù)其架構(gòu)特征與代碼實現(xiàn)指令序列特點，提出了指令級冗余的并發(fā)錯誤檢測方法，并設(shè)計了脆弱性感知的指令復(fù)制算法，可在滿足性能約束條件下有效提高處理器對隨機故障與惡意故障的檢測能力。實驗證明，相比于同類型方法，在相同性能開銷條件下，采用本文方法后RBCSP對隨機故障與惡意故障的檢測率更高，且全指令復(fù)制后密碼算法實現(xiàn)性能開銷最低、面積能效比最高。

1 功能單元利用率分析

指令級冗余技術(shù)的核心思想是以冗余指令填充空閑槽，其實質(zhì)是利用空閑狀態(tài)功能單元實現(xiàn)冗余計算。為評估指令級冗余方法在RBCSP上的可行性與高效性，需對不同分組密碼算法實現(xiàn)時處理器功能單元，即可重構(gòu)并行處理單元RPU(Reconfigurable Parallel processing Unit)的利用率進行統(tǒng)計。RBCSP上RPU包括多種類型，如S盒運算單元、置換單元等，需分別進行統(tǒng)計。RBCSP上實現(xiàn)分組密碼算法，采用軟件流水技術(shù)挖掘輪函數(shù)中不同操作間的指令級并行度[5]，可使相鄰迭代的加密操作盡可能地重疊執(zhí)行。以CBC(Cipher Block Chaining)模式下AES-128算法實現(xiàn)為例，其軟件流水實現(xiàn)如圖1所示。

圖1 RBCSP上CBC模式AES算法實現(xiàn)

圖1中AES算法輪函數(shù)操作映射為4個32-bit數(shù)據(jù)分塊依次進行綁定前異或的S盒操作(X_S)、有限域乘法操作與四字置換選字輸出操作。整個軟件流水共分為3個階段：填充階段、循環(huán)核心階段和排空階段。通過軟件流水調(diào)度，單個數(shù)據(jù)分塊的輪函數(shù)操作仍是依次執(zhí)行，而分組內(nèi)不同數(shù)據(jù)分塊的輪函數(shù)操作能夠并行執(zhí)行，相比于圖1(a)所示順序執(zhí)行的實現(xiàn)方式，軟件流水方式大大縮短了加密周期。

通過觀察圖1(b)所示指令序列可知，指令中存在大量可利用的空閑域。設(shè)RPU利用率為rRPU，其等于算法程序運行過程中占用該RPU的時鐘周期數(shù)NusedRPU與總時鐘周期數(shù)Ntotal的比率，如公式所示：

(1)

分析軟件流水方式下不同算法實現(xiàn)代碼，各算法rRPU統(tǒng)計結(jié)果如圖2所示。

圖2 軟件流水工作模式下各算法RPU利用率

圖2中，除DES外，AES-128、SMS4、IDEA、Camellia和RC6算法的最大RPU利用率超過50%，但RPU平均利用率仍在40%左右。統(tǒng)計分析后可知RPU利用率仍有足夠大的提升空間，這意味著在各算法程序運行過程的多數(shù)時鐘周期中仍存在可利用的空閑RPU。通過有效利用這些空閑RPU執(zhí)行復(fù)制指令操作，可減少錯誤檢測帶來的性能開銷。

2 指令復(fù)制算法

2.1 復(fù)制指令調(diào)度范圍

本文RBCSP上分組密碼算法實現(xiàn)的指令序列視作一個二維調(diào)度表，行表示各RPU，列表示指令調(diào)度的時鐘周期。表中圓圈表示指令，箭頭表示指令間的數(shù)據(jù)相關(guān)性，空格表示該時鐘周期對應(yīng)的RPU空閑。指令i的復(fù)制范圍是指其冗余指令在調(diào)度表中可調(diào)度的時鐘周期范圍。指令復(fù)制范圍可簡單設(shè)置為指令i所在時鐘周期的下一個時鐘周期。若下一時鐘周期中無可利用的空閑RPU，則增加一個新的時鐘周期用以調(diào)度冗余指令。通過這種復(fù)制方法，可快速完成原始指令序列至復(fù)制后指令序列的轉(zhuǎn)變。

對于圖3(a)中的原始調(diào)度表，按該方法進行指令復(fù)制后，調(diào)度表變?yōu)閳D3(b)所示。圖3(b)中指令D需等待指令C的復(fù)制指令完成后才能執(zhí)行，而指令E與指令D存在數(shù)據(jù)相關(guān)，這導(dǎo)致指令E也需等待指令C的復(fù)制指令完成才可執(zhí)行。此時指令D的復(fù)制指令在時鐘周期4調(diào)度，而調(diào)度完所有復(fù)制指令所需的時鐘周期數(shù)為7。若等待占據(jù)同一RPU的連續(xù)指令完成后，再調(diào)度復(fù)制指令，此時完成所有指令復(fù)制所需時鐘周期數(shù)為6，如圖3(c)所示。由于調(diào)度表中存在多個連續(xù)占用某個RPU的指令，且后續(xù)指令與這些連續(xù)指令存在數(shù)據(jù)相關(guān)，導(dǎo)致圖3(b)所示的復(fù)制方法相比于圖3(c)，消耗時鐘周期數(shù)更多。

圖3 指令調(diào)度表

常見分組密碼算法的分組長度大多為64、128、256 bit，而RBCSP中RPC的數(shù)據(jù)位寬為32，這使得RBCSP上密碼算法實現(xiàn)的指令序列中，一個分組操作需要多個使用某類型RPU的連續(xù)指令實現(xiàn)。且分組密碼算法實現(xiàn)的指令序列中，前后指令的數(shù)據(jù)相關(guān)性較強，若采用圖3(b)所示的指令復(fù)制方法，則存在許多原始指令操作須等待之前指令的復(fù)制指令完成后才能執(zhí)行，這將極大降低算法實現(xiàn)性能。因此，本文選擇圖3(c)所示的指令復(fù)制方法。該方法中指令i的復(fù)制范圍由指令i所依賴的指令以及重寫指令i所讀取寄存器的指令確定。復(fù)制指令調(diào)度范圍如下：

? 最早調(diào)度時鐘周期：指令i的源操作數(shù)準(zhǔn)備完畢且指令i所使用RPU處于空閑的第一個時鐘周期。

? 最晚調(diào)度時鐘周期：指令i所需任何源操作數(shù)被重寫之前的最后一個時鐘周期。

2.2 指令復(fù)制算法描述

為在滿足性能約束條件下提高處理器的故障檢測能力，可優(yōu)先選擇復(fù)制脆弱性更高的指令。目前已有文獻中指令脆弱性主要包括指令的時間脆弱性、物理脆弱性[10]。指令的時間脆弱性ITV(Instruction Temporal Vulnerability)，可由該指令的總執(zhí)行次數(shù)表示。一般認為循環(huán)內(nèi)指令比其他指令執(zhí)行次數(shù)更多，因此具有更多機會發(fā)生軟錯誤[11]。指令的物理脆弱性IPV(Instruction Physical Vulnerability)，可由該指令所使用單元面積表示。這是因為單元面積越大，包含的晶體管數(shù)量越多，則它更多的暴露于高能粒子從而易于誘發(fā)軟錯誤[12]。與通用處理器不同，分組密碼流處理器專用于實現(xiàn)分組密碼算法，易受到惡意故障攻擊。因此在選擇指令復(fù)制時，本文將惡意故障注入位置、輪數(shù)納入考慮，提出指令的攻擊脆弱性IVV(Instruction Vulnerable Vulnerability)概念。

定義1指令易受到惡意故障攻擊的可能性，稱之為指令的攻擊脆弱性。

攻擊脆弱性越高的指令，越容易成為惡意攻擊的對象。惡意故障注入的位置、時間取決于具體的分組密碼算法及攻擊所采用的故障模型，因此不同算法實現(xiàn)的指令序列中，即使是相同指令，其攻擊脆弱性也可能不同。如針對AES-128算法的故障攻擊，多選擇在第7、8、9輪操作中注入惡意故障[13]，故相比于其他輪，算法實現(xiàn)指令序列中第7、8、9輪運算指令的攻擊脆弱性更高。

為了量化評估調(diào)度表中指令的脆弱性，本文分別對指令的時間脆弱性、物理脆弱性、相關(guān)脆弱性設(shè)置了如下量化規(guī)則。

規(guī)則1設(shè)指令序列中不循環(huán)執(zhí)行指令的時間脆弱性因子ITVF(Instruction Temporal Vulnerability Factor)為1；指令序列中循環(huán)執(zhí)行指令的ITVF為10。目前算法實現(xiàn)指令序列采用循環(huán)展開方式實現(xiàn)，則所有指令的ITVF均為1。

規(guī)則2設(shè)最小RPU單元面積為Amin，且使用該RPU指令的物理脆弱性因子IPVF(Instruction Physical Vulnerability Factor)為1，則對于指令i，若其使用RPU面積為Ai，則其IPVF=Ai/Amin。

規(guī)則3由所實現(xiàn)算法確定算法易受故障攻擊的輪數(shù)，選擇指令序列中對應(yīng)輪的指令，其指令攻擊脆弱性因子IVVF(Instruction Vulnerable Vulnerability Factor)設(shè)為1 000，其他指令的IVVF設(shè)為1。

按上述規(guī)則，計算得到調(diào)度表中各指令的ITVF、IPVF、IVVF，則指令的脆弱性因子IVF(Instruction Vulnerability Factor)可由式(2)計算得到:

IVF=ITVF×IPVF×IVVF

(2)

將所有指令按其IVF進行降序排列(IVF相同的指令按指令先后逆序排列)，可得到指令優(yōu)先級列表L。指令優(yōu)先級列表L中靠前的指令，脆弱性越高，將優(yōu)先選擇復(fù)制。根據(jù)復(fù)制指令優(yōu)先級列表L，設(shè)置時鐘周期增長上限，在計算得到的指令復(fù)制范圍內(nèi)調(diào)度復(fù)制指令。本文的脆弱性感知指令復(fù)制算法偽代碼如下：

輸入：VLIW代碼；時鐘周期增長上限cycle_increase_margin。

輸出：帶復(fù)制指令信息的VLIW代碼。

定義：代碼序列的區(qū)域圖G={N,E}，其中N={ni/ni表示一個代碼區(qū)域，通常為一個基本指令塊}，E={ei,j/ei,j表示存在控制流ni→nj}；

Nattack={nk/nk表示易受攻擊的指令塊}；優(yōu)先級指令列表L：按照脆弱性降序排列存儲的指令列表；max_sched_cycle：最大調(diào)度時鐘周期。

01:for(each instruction inst∈L)

02: dup_inst=create_dupl(inst);

//創(chuàng)建冗余指令

03: inst_cycle= get_sched_cycle(inst);

//獲得原始指令所在時鐘周期

04: etime=get_earliest_sched_time(inst);

//指令調(diào)度的最早時鐘周期

05: ltime = get_earliest_sched_time(inst);

//指令調(diào)度的最晚時鐘周期

06: stime=etime;

07:while!schedule(dup_inst, stime)do

//嘗試調(diào)度冗余指令

08: stime++;

09:if(stime>ltime)then

10:if(cycle_inc_margin>0)&&(check_dupl_dependence())then

11: shift_point=get_shift_start_point(inst,ltime,stime);

12: shift_down_sched_table(shift_point,max_sched_cycle);

13: update stime;

14: update ltime;

15: cycle_increase_margin--;

16: max_sched_cycle++;

17:else

18: delete dupl_inst;

19: break;

20:endif

21:endif

22:endwhile

23:endfor

表中循環(huán)(行01-23)按照已構(gòu)建的指令優(yōu)先級復(fù)制列表L中指令優(yōu)先級順序調(diào)度復(fù)制指令。對于列表L中每條指令，算法首先獲取指令復(fù)制所需信息(行02-06)，并在獲取的指令復(fù)制范圍stime至ltime中，嘗試調(diào)度復(fù)制指令。算法中schedule()嘗試調(diào)度冗余指令失敗的情況主要是指當(dāng)前時刻已存在超過RBCSP可支持的RPU并行執(zhí)行數(shù)。若調(diào)度失敗，而時鐘周期增加上限大于0且調(diào)度冗余指令不會導(dǎo)致指令間相關(guān)性違背，則嘗試向下移動調(diào)度表，以提供有效空間實現(xiàn)冗余指令調(diào)度(行09-16)。函數(shù)check_dupl_dependecne()判斷移動調(diào)度表放置復(fù)制指令是否會導(dǎo)致各指令間相關(guān)性違背。若不存在相關(guān)性違背，則存在一個合理方式移動調(diào)度表以放置冗余指令。函數(shù)get_shift_start_point()負責(zé)計算調(diào)度表移動起點。函數(shù)shift_down_sched_table()將部分調(diào)度表往下移動一個時鐘周期。若存在相關(guān)性違背或時鐘周期增加上限小于或等于0，則放棄復(fù)制該指令(行14-20)。重復(fù)上述過程對列表L中指令依次進行復(fù)制，直至所有指令復(fù)制調(diào)度結(jié)束或者時鐘周期增長上限為0，算法結(jié)束。

在不考慮性能約束時，采用該算法實現(xiàn)AES全指令復(fù)制時的指令序列如圖4所示。圖4中冗余指令充分利用了原始指令序列中的空閑槽，相比于原始指令序列，其增加的指令條數(shù)比約為25.6%。指令復(fù)制后處理器的故障檢測能力將在下節(jié)展示。

圖4 AES-CBC算法的全指令復(fù)制實現(xiàn)

3 實驗驗證

為減少性能開銷，對原RBCSP進行了部分硬件擴展與指令格式修改, 使原始指令與冗余指令的結(jié)果比較不需增加額外的比較指令。本文將擴展后的RBCSP稱之為增強型可重構(gòu)分組密碼流處理器ERBCSP(Enhanced Reconfigurable Block Cipher Stream Processor)。利用綜合工具基于65 nm CMOS工藝標(biāo)準(zhǔn)單元庫綜合獲取了RBCSP與ERBCSP原型系統(tǒng)的硬件資源信息，綜合結(jié)果如表1所示。根據(jù)綜合結(jié)果，RBCSP與ERBCSP原型系統(tǒng)的關(guān)鍵路徑長度均為2.0 ns(工作頻率為500 MHz)，而相比RBCSP，ERBCSP增加的硬件開銷比約為1.5%。

表1 ASIC綜合結(jié)果

3.1 故障檢測能力

為驗證錯誤檢測方法的有效性，分別被執(zhí)行了隨機故障注入實驗與惡意故障注入實驗。測試目標(biāo)RTL系統(tǒng)采用 ERBCSP的RTL設(shè)計與驗證環(huán)境。故障注入目標(biāo)模塊選取RPU，注入故障類型為瞬態(tài)故障。仿真實驗均以AES算法為測試基準(zhǔn)，并以如下方式生成測試負載執(zhí)行仿真：一是設(shè)定不同時鐘周期增長上限(即性能開銷約束)，分別按本文、文獻[9]、文獻[10]的指令復(fù)制算法復(fù)制指令后得到相應(yīng)代碼，作為測試負載。

3.1.1 隨機故障檢測

仿真時在測試負載執(zhí)行過程的隨機時間改變RPU的任意信號值，持續(xù)時間為一個時鐘周期。測試程序每運行一次，僅注入一個隨機故障，共運行300 000次。測試負載運行過程中，記錄錯誤指示信號變化次數(shù)，獲得異常檢測數(shù)量Nexp，則故障檢測率FDR(Fault Detection Rate)為(Nexp/300 000)×100%。圖5展示了不同時鐘周期增長上限下的隨機故障檢測率。

圖5 隨機故障檢測率對比

由于許多注入的隨機故障并不會影響密碼運算結(jié)果，因而相比于故障注入總數(shù)，產(chǎn)生計算錯誤的次數(shù)并不高，故圖5中全指令復(fù)制后各方案的故障檢測率約為49%。但由圖5可知，相同性能約束下，本文方法的隨機故障檢測率明顯高于文獻[9]，略高于文獻[8]。

3.1.2 惡意故障檢測

為模擬故障攻擊，選擇經(jīng)典的單字節(jié)故障模型[14]，在AES算法第9輪列混淆輸入處注入1字節(jié)惡意故障。實驗時，在第9輪四字置換原始計算結(jié)束時刻，強制改變保存原始計算結(jié)果的DCR，程序每運行一次，隨機改變1字節(jié)值，共運行4 096次。圖6展示了不同時鐘周期增長上限下各文獻方案的惡意故障檢測率。

圖6 惡意故障檢測率對比

由圖6可知，當(dāng)時鐘周期增長數(shù)量大于等于6時，本文方案的惡意故障檢測率已為100%，而文獻[8]、文獻[9]方案的惡意故障檢測率為50%或0。由圖6可知，在相同性能約束下，相比于文獻[8]、文獻[9]，采用本文方法后RBCSP對惡意故障具有更高的檢測率。

3.2 性能開銷對比

本文選取AES-128、SMS4和IDEA算法作為SP、Feistel和L-M三種結(jié)構(gòu)的代表算法，以CBC模式作為算法工作模式，分別在ERBCSP上進行全指令復(fù)制的算法實現(xiàn)，算法實現(xiàn)性能結(jié)果如表2所示。

表2 密碼算法實現(xiàn)性能

由表2可知復(fù)制全部指令后，AES-128、SMS4、IDEA的性能開銷比分別為25.6%、17.9%、15.7%。為說明性能開銷較低的原因，統(tǒng)計了復(fù)制全部指令前后各算法的RPU利用率。如圖7(a)所示，復(fù)制指令前，AES-128、SMS4、IDEA算法的最大RPU利用率超過50 %，RPU平均利用率在40 %左右。如圖7(b)所示，復(fù)制指令后，AES-128、SMS4、IDEA的RPU利用率得到了巨大提升，RPU最大利用率可達到90 %以上，平均利用率在70 %左右。這是因為一方面復(fù)制指令算法有效利用運行時刻處于空閑狀態(tài)的RPU實現(xiàn)再計算，另一方面軟件流水技術(shù)使原始指令與復(fù)制指令盡可能多的并行執(zhí)行，在極大提高RPU利用率的同時，有效減少了性能開銷。

圖7 指令復(fù)制前后RPU利用率

文獻[6-10]均采用指令復(fù)制實現(xiàn)錯誤檢測，但各文獻基于的處理器架構(gòu)存在差異且選用的測試基準(zhǔn)不同，因此無法直接使用文獻內(nèi)數(shù)據(jù)進行對比。由圖5與圖6可知全指令復(fù)制時不同文獻方案的故障檢測能力相似，為有效對比不同文獻方法在RBCSP上實現(xiàn)所帶來開銷，本文將各文獻方法在RBCSP上進行適配后，得到處理器面積與全指令復(fù)制實現(xiàn)的性能開銷結(jié)果，如表3所示。表3中增加了帶錯誤檢測后AES算法實現(xiàn)的面積能效比，更直觀地對比各方法在RBCSP上實現(xiàn)的優(yōu)劣。

表3 開銷對比

表3中DMR(Dual Modular Redundancy)并非復(fù)制整個RBCSP，而僅復(fù)制其核心部件(可重構(gòu)并行處理簇)，因此面積開銷小于100%，僅為53.2%。文獻[6]與文獻[7]方法無法適配于ERBCSP，因此表中未列出其數(shù)據(jù)。由表4中數(shù)據(jù)可知，DMR的性能開銷為0，但面積開銷最大。文獻[9]的面積開銷最小，但性能開銷最大。而由本文方法復(fù)制全部指令后，相比于文獻[9]、文獻[10]，各密碼算法實現(xiàn)性能開銷最低；相比于DMR、文獻[9]、文獻[10]，各密碼算法實現(xiàn)的面積能效比最高。由文獻[8]指令復(fù)制算法實現(xiàn)全指令復(fù)制時，其性能開銷與本文相等，因此表中未列出，但由圖5可知，在相同性能開銷約束下，文獻[8]的故障檢測能力低于本文方法。因此，綜合考慮故障檢測能力、性能開銷等因素，本文方法優(yōu)于DMR、文獻[8]、文獻[9]、文獻[10]。

4 結(jié) 語

本文面向分組密碼流處理器，提出了基于指令復(fù)制的低開銷并發(fā)錯誤檢測方法?？紤]惡意故障注入時間、位置的傾向性，提出了指令攻擊脆弱性概念，并結(jié)合指令的時間脆弱性、物理脆弱性，設(shè)計了脆弱性感知的指令復(fù)制算法，可在性能開銷約束下，有效提高處理器對隨機故障與惡意故障的檢測能力。實驗證明，本文方法增加的面積開銷僅占原處理器面積的1.5%；在錯誤檢測能力上，相比于同類方法，采用本文方法后處理器可更有效地檢測隨機故障與惡意故障；在性能開銷上，采用本文指令復(fù)制算法實現(xiàn)全部指令復(fù)制后，典型SP(AES-128)、Feistel(SMS4)、LM(IDEA)結(jié)構(gòu)算法實現(xiàn)性能開銷分別為25.6%、17.9%、15.7%，相比于同類型方法，采用本文方法實現(xiàn)全指令復(fù)制后密碼算法實現(xiàn)性能開銷最低，面積能效比最高。由于實現(xiàn)指令復(fù)制后代碼規(guī)模增大，下一步將考慮通過動態(tài)復(fù)制指令以減小代碼規(guī)模、降低存儲開銷。