徐 力， 吳新春， 周 彬， 葉文霞

(1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都611756；2.哈爾濱工業(yè)大學(xué) 空間基礎(chǔ)科學(xué)研究中心，哈爾濱 150001)

加速硬件木馬檢測(cè)方法研究

徐 力1， 吳新春1， 周 彬2， 葉文霞1

(1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都611756；2.哈爾濱工業(yè)大學(xué) 空間基礎(chǔ)科學(xué)研究中心，哈爾濱 150001)

為有效檢測(cè)出芯片在設(shè)計(jì)和外包制造過程中是否被插入硬件木馬電路, 提出一種在芯片設(shè)計(jì)階段插入二選一數(shù)據(jù)選擇器(MUX)來提高電路節(jié)點(diǎn)轉(zhuǎn)移概率的方法. 即在電路中轉(zhuǎn)移概率低于轉(zhuǎn)移概率閾值的候選節(jié)點(diǎn)的主要輸入端插入MUX來提高相關(guān)節(jié)點(diǎn)的轉(zhuǎn)移概率, 從而實(shí)現(xiàn)加速電路中硬件木馬的檢測(cè). 通過對(duì)扇出錐和電路邏輯拓?fù)浣Y(jié)構(gòu)的分析，選擇對(duì)整個(gè)電路轉(zhuǎn)移概率影響最大的節(jié)點(diǎn)作為候選節(jié)點(diǎn)，實(shí)現(xiàn)對(duì)MUX插入算法的優(yōu)化，從而減少M(fèi)UX的插入數(shù)量. 同時(shí)增加關(guān)鍵路徑延時(shí)限制，避免電路關(guān)鍵路徑延遲超過預(yù)先設(shè)定的閾值. 將預(yù)先設(shè)計(jì)的硬件木馬電路的輸入端插入在電路中轉(zhuǎn)移概率較小的節(jié)點(diǎn)，并向電路輸入端輸入激勵(lì)信號(hào)，分析計(jì)算在MUX插入前后電路轉(zhuǎn)移概率變化以及硬件木馬電路的激活概率. ISCAS'89基準(zhǔn)電路的實(shí)驗(yàn)結(jié)果表明：在插入MUX之后，電路整體轉(zhuǎn)移概率顯著提高，電路中轉(zhuǎn)移概率小于轉(zhuǎn)移概率閾值的節(jié)點(diǎn)數(shù)明顯降低；被插入在電路中的硬件木馬被激活的概率顯著提高；電路關(guān)鍵路徑延時(shí)增加百分比控制在預(yù)先設(shè)定的比例因子之內(nèi).

二選一數(shù)據(jù)選擇器；硬件木馬；轉(zhuǎn)移概率；路徑延時(shí)

硬件木馬也被稱之為惡意電路，是在第三方IP或者制造過程中插入到電路中的微小電路模塊. 一般情況下在電路系統(tǒng)中并不發(fā)揮作用，但在特定情況下會(huì)被激活. 一旦激活后可能改變電路功能、損壞電路甚至泄露電路信息，從而達(dá)到插入者的目的，危害可想而知[1]. 硬件木馬模塊相對(duì)于整個(gè)電路結(jié)構(gòu)而言十分微小，激活前并不改變電路功能，使得硬件木馬的檢測(cè)變得十分困難.

除此之外，硬件木馬可連接到電路網(wǎng)表的任何節(jié)點(diǎn)上，尤其是那些轉(zhuǎn)移概率相對(duì)較低的節(jié)點(diǎn). 傳統(tǒng)自動(dòng)測(cè)試矢量生成算法(ATPG)并不能有效的激活和檢測(cè)硬件木馬. 尤其當(dāng)硬件木馬的輸入端連接到轉(zhuǎn)移概率相對(duì)較小的節(jié)點(diǎn)后，邏輯測(cè)試將變得十分困難. 并且硬件木馬電路對(duì)整個(gè)電路的功耗和延時(shí)的影響較小，通過時(shí)序和功耗檢測(cè)的方法也收效甚微. 近年來，硬件木馬的檢測(cè)技術(shù)得到了明顯的發(fā)展. 硬件木馬的檢測(cè)方法主要分為以下三種：基于失效性分析、邏輯測(cè)試和旁路信號(hào)分析[1].

基于失效性分析是最早用于硬件木馬的檢測(cè)方法，它主要依賴于高精度設(shè)備，諸如光學(xué)顯微鏡、電子顯微鏡等進(jìn)行掃描分析[2]. 通過高精度設(shè)備掃描和重構(gòu)原始電路，將反向設(shè)計(jì)和原始電路設(shè)計(jì)進(jìn)行比對(duì)來判斷電路中是否被插入硬件木馬[2-4]. 這種測(cè)試方法對(duì)于小規(guī)模集成電路有一定的實(shí)用性. 但是隨著大規(guī)模集成電路的發(fā)展，芯片的集成度越來越高，晶體管尺寸已經(jīng)達(dá)到了納米級(jí)，這種檢測(cè)方法已經(jīng)不能滿足檢測(cè)要求.

基于旁路信號(hào)的檢測(cè)方法是目前一種有效的測(cè)量方法[5-12]，通過測(cè)量和分析原始電路的信息，諸如延時(shí)[7-9]和功耗[5-6,10,12]等；得到原始電路的功耗或延時(shí)的特性曲線，也被稱之為“IC指紋”[1]. 再通過同樣的方法得到待測(cè)芯片的特性曲線，然后與之前的特性曲線相比較，去判斷待測(cè)電路中是否存在硬件木馬[2]. 此種測(cè)量方法易受到外界環(huán)境和工藝差別的影響，當(dāng)硬件木馬的影響較小而環(huán)境和工藝噪聲較大時(shí)，硬件木馬很難被檢測(cè)出來[1].

基于邏輯測(cè)試的檢測(cè)方法通過向電路輸入端輸入激勵(lì)信號(hào)，盡可能的激活電路中的硬件木馬，通過比對(duì)電路的響應(yīng)和正確的輸出結(jié)果來判斷電路中是否存在硬件木馬[13-17]. 邏輯測(cè)試不受工藝噪聲和環(huán)境的影響，能有效檢測(cè)一些結(jié)構(gòu)較小的木馬[1]. 但是如果硬件木馬的輸入端連接到電路中轉(zhuǎn)移概率很小的節(jié)點(diǎn)，這樣以來硬件木馬的活性大大降低，窮舉測(cè)試就會(huì)變得十分耗時(shí).

針對(duì)邏輯測(cè)試方法中硬件木馬難以激活的問題，可通過插入二選一數(shù)據(jù)選擇器(MUX)來提高電路整體節(jié)點(diǎn)的轉(zhuǎn)移概率，從而提高硬件木馬的激活概率的方法[18]. 本文在此基礎(chǔ)上提出新的插入選擇算法，同時(shí)通過設(shè)置最大延時(shí)比例來保證電路的最大延時(shí)在一定范圍之內(nèi)，避免因插入點(diǎn)的增加而引起關(guān)鍵路徑延時(shí)過大的問題.

1 提出方法

當(dāng)MUX的選擇信號(hào)為‘0’時(shí)，電路工作在正常模式下；當(dāng)選擇信號(hào)為‘1’時(shí)，電路工作在測(cè)試模式，該模式下可直接在原電路內(nèi)部節(jié)點(diǎn)輸入測(cè)試信號(hào)，提高節(jié)點(diǎn)的轉(zhuǎn)移概率，從而提高硬件木馬的激活與檢測(cè)概率. 隨著插入節(jié)點(diǎn)的增多，電路的功耗、面積、延時(shí)等參數(shù)會(huì)有所增加. 通過優(yōu)化算法，使得MUX的插入數(shù)量減小. 同時(shí)設(shè)置最大延時(shí)比例來控制電路關(guān)鍵路徑的延時(shí).

1.1分析插入MUX對(duì)轉(zhuǎn)移概率的提高

節(jié)點(diǎn)的轉(zhuǎn)移概率是指節(jié)點(diǎn)的跳變概率. 轉(zhuǎn)移概率越高的節(jié)點(diǎn)在測(cè)試中跳變的次數(shù)就越高，所以提高整個(gè)電路節(jié)點(diǎn)的轉(zhuǎn)移概率能有效的提高硬件木馬激活和被檢測(cè)的概率. 基礎(chǔ)邏輯門的轉(zhuǎn)移概率計(jì)算方法見表1.

表1 邏輯門轉(zhuǎn)移概率計(jì)算規(guī)則

假定該邏輯門第j個(gè)輸入端為‘1’的信號(hào)概率最小，則在該輸入端插入二選一數(shù)據(jù)選擇器. 插入之后該邏輯門輸出端節(jié)點(diǎn)信號(hào)為‘1’的概率為

對(duì)于一個(gè)邏輯門而言，轉(zhuǎn)移概率小于Tth可分為以下兩種情況：

分析可知，在輸入端插入MUX可提高與門的轉(zhuǎn)移概率. 其他類型的邏輯門也可通過類似的方法進(jìn)行分析討論.

圖1 被插入MUX的邏輯門

1.2插入點(diǎn)選擇算法

具體插入算法見圖2. 流程所需要的輸入為電路網(wǎng)表、人為設(shè)定的Tth、最大延時(shí)系數(shù)R以及提供電路物理特性的庫(kù)文件. 計(jì)算每個(gè)節(jié)點(diǎn)的邏輯深度Ld和扇出錐的節(jié)點(diǎn)數(shù)量Ncone，通過給所有輸入端賦邏輯值為“1”的概率為0.5的輸入向量，可得到各個(gè)節(jié)點(diǎn)信號(hào)概率s，通過計(jì)算得到每個(gè)節(jié)點(diǎn)的轉(zhuǎn)移概率tp. 插入之前計(jì)算原始電路關(guān)鍵路徑延時(shí)記為Cdelay. 所有tp

表2候選節(jié)點(diǎn)最小概率的輸入節(jié)點(diǎn)選擇方法

Tab.2 Input node selection method for minimum signal probability of candidate node

邏輯門選擇方法與門/與非門為‘1’概率最小的輸入節(jié)點(diǎn)或門/或非門為‘0’概率最小的輸入節(jié)點(diǎn)

2 實(shí)驗(yàn)結(jié)果分析

本實(shí)驗(yàn)以ISCAS’89基準(zhǔn)電路作為實(shí)驗(yàn)對(duì)象，使用STM65納米標(biāo)準(zhǔn)單元庫(kù)計(jì)算電路信息. 采用C語(yǔ)言搭建實(shí)驗(yàn)平臺(tái)進(jìn)行電路仿真. 在仿真測(cè)試過程中，主要輸入端都賦予信號(hào)為‘1’的概率為0.5的信號(hào)，來計(jì)算電路的整體信息.

2.1轉(zhuǎn)移概率提高

在此實(shí)驗(yàn)當(dāng)中，以S9234和S5378電路作為基準(zhǔn)電路進(jìn)行測(cè)試. 比較在插入前后電路所有節(jié)點(diǎn)的轉(zhuǎn)移概率的變化. 通過圖3、4、5、6可看出，在插入MUX之前電路中有大量轉(zhuǎn)移概率小于轉(zhuǎn)移概率閾值0.05的節(jié)點(diǎn)，其中還有不少tp<10-4的節(jié)點(diǎn). 通過本文提出的方法，將轉(zhuǎn)移概率閾值設(shè)置為0.05. 在插入MUX之后，整體的轉(zhuǎn)移概率提高，S5378電路中tp<0.05的節(jié)點(diǎn)數(shù)為9個(gè)，S9234電路中這一數(shù)字為84個(gè)，并且都沒有tp<0.01的節(jié)點(diǎn). 整體看來通過插入MUX之后，轉(zhuǎn)移概率的提高十分明顯.

圖2 選擇算法

圖3 S5378電路插入MUX前電路轉(zhuǎn)移概率

圖4 S5378電路插入MUX后電路轉(zhuǎn)移概率

圖5 S9234電路插入MUX前電路轉(zhuǎn)移概率

圖6 S9234電路插入MUX后電路轉(zhuǎn)移概率

2.2面積、功耗和延時(shí)的增加

通過插入MUX來提高整體電路的轉(zhuǎn)移概率，隨著插入數(shù)量的不斷增加，勢(shì)必會(huì)引起功耗、面積和延時(shí)增加. 特別是關(guān)鍵路延時(shí)的增加會(huì)給整個(gè)電路帶來嚴(yán)重的影響. 通過設(shè)置最大延時(shí)比例，可將關(guān)鍵路徑延時(shí)控制在可接受范圍之內(nèi).

表3中為S5378電路的仿真結(jié)果，當(dāng)Tth分別為0.05、 0.1，最大延時(shí)比例為1.03、 1.1時(shí)，最大延時(shí)分別增加1.66%、9.16%. 面積分別增加7.83%、15.44%. 功耗分別增加12.47%、19.63%.

表4中為S9234電路的仿真結(jié)果，當(dāng)Tth分別為0.05、 0.1，最大延時(shí)比例為1.03、 1.1時(shí)，最大延時(shí)分別增加2.1%、13.3%. 面積分別增加5%、9.29%. 功耗分別增加17.94%、24.69%.

表3 S5378電路插入MUX后帶來的影響

表4 S9234插入MUX后帶來的影響

2.3木馬電路的激活

如圖7所示，該硬件木馬由觸發(fā)器和負(fù)載兩部分構(gòu)成. 與門和非門構(gòu)成觸發(fā)器部分，異或門構(gòu)成負(fù)載部分. TJ1、TJ2、TJ3、TJ4和TJ5作為觸發(fā)器的5個(gè)輸入節(jié)點(diǎn)可被插入到目標(biāo)電路的任意節(jié)點(diǎn)，當(dāng)目標(biāo)電路節(jié)點(diǎn)達(dá)到一定的邏輯值，木馬電路的觸發(fā)部分將被觸發(fā)，電路的功能將被改變. 而當(dāng)木馬電路沒有被觸發(fā)時(shí)，電路的功能將不被改變.

圖7 一種5輸入的硬件木馬實(shí)例

通過表5可知，如果硬件木馬的輸入端連接在S5378電路中轉(zhuǎn)移概率相對(duì)較小的節(jié)點(diǎn)，那么硬件木馬的激活將變得十分困難. 如圖7所示的一個(gè)5輸入組合邏輯的硬件木馬，其輸入端分別連接到S5378電路的n219gat、n89gat、n110gat、n22gat和n200gat節(jié)點(diǎn)上，在插入MUX之前，硬件木馬的激活概率為2.24710-13，要用邏輯測(cè)試的方法將其檢測(cè)出來是一件十分困難的事. 轉(zhuǎn)移概率閾值Tth設(shè)置為0.05后由圖4可知，絕大多數(shù)的節(jié)點(diǎn)的轉(zhuǎn)移概率都大于了0.05. 通過表5可看出當(dāng)Tth=0.05時(shí)，插入MUX之后木馬的激活概率增加到2.21610-03，在這樣的激活概率下可有效的檢測(cè)出硬件木馬. 適當(dāng)?shù)貙⑥D(zhuǎn)移概率閾值Tth提高為0.1，硬件木馬的激活概率增加到8.57410-03.

表5 S5378電路硬件木馬激活信息

表6 S9234電路硬件木馬激活信息

在S9234中插入圖7所示的硬件木馬，在插入MUX之前，硬件木馬的激活概率為4.49010-09，當(dāng)轉(zhuǎn)移概率閾值分別設(shè)置為0.05和0.1之后，硬件木馬的激活概率分別增加到了7.06910-04和3.41010-03. 硬件木馬激活概率的提高十分明顯.

2.4最大延時(shí)比例系數(shù)對(duì)結(jié)果的影響

在表7中以S5378電路為例，如果轉(zhuǎn)移概率閾值設(shè)置較大，如Tth=0.15，電路中tp

表7 最大延時(shí)比例系數(shù)對(duì)插入結(jié)果的影響

3 結(jié) 論

在本文中，提出一種通過在轉(zhuǎn)移概率較低節(jié)點(diǎn)的輸入端插入二選一數(shù)據(jù)選擇器的方法實(shí)現(xiàn)對(duì)電路節(jié)點(diǎn)轉(zhuǎn)移概率的提高，從而實(shí)現(xiàn)加速硬件木馬檢測(cè). 通過對(duì)扇出錐和電路邏輯拓?fù)浣Y(jié)構(gòu)分析選擇對(duì)整個(gè)電路影響最大的候選節(jié)點(diǎn)，通過分析候選節(jié)點(diǎn)的邏輯門類型和輸入信號(hào)概率選擇最佳的插入點(diǎn)，從而減少M(fèi)UX的插入數(shù)量，實(shí)現(xiàn)對(duì)插入算法的優(yōu)化. 同時(shí)引入最大延時(shí)比例系數(shù)用以控制電路關(guān)鍵路徑延時(shí)，使電路關(guān)鍵路徑延時(shí)控制在可接受的范圍內(nèi). 通過實(shí)驗(yàn)分析，電路的轉(zhuǎn)移概率得到整體提升，可有效防止硬件木馬的插入. 被插入在電路中硬件木馬的激活概率得到明顯提高，可有效實(shí)現(xiàn)對(duì)硬件木馬的檢測(cè). 同時(shí)，關(guān)鍵路徑延時(shí)也得到有效控制.

[1] 劉華鋒, 羅宏偉, 王力緯. 硬件木馬綜述[J]. 微電子學(xué), 2011, 41(5):709-713.

LIU Huafeng, LUO Hongwei, WANG Liwei.Survey on Hardware Trojan Horse[J]. Microelectronics, 2011, 41(5):709-713.

[2] AGRAWAL D, BAKTIR S, KARAKOYUNLU D, et al. Trojan detection using IC fingerprinting[C]// Proceedings of the IEEE Symposium on Security and Privacy. Berkeley: IEEE Computer Society, 2007:296-310. DOI: 10.1109/SP.2007.36.

[3] WANG Xiaoxiao, TEHRANIPOOR M, PLUSQUELLIC J. Detecting malicious inclusions in secure hardware: challenges and solutions[C]// Proceedings of the IEEE International Workshop on Hardware-Oriented Security and Trust. Anaheim: IEEE, 2008:15-19.DOI: 10.1109/HST.2008.4559039.

[4] JIN Y, KUPP N, MAKRIS Y. Experiences in hardware Trojan design and implementation[C]// Proceedings of the IEEE International Workshop on Hardware-Oriented Security and Trust. Francisco: IEEE Computer Society, 2009:50-57.DOI: 10.1109/HST.2009.5224971.

[5] SALMANI H, TEHRANIPOOR M. Layout-aware switching activity localization to enhance hardware Trojan detection [J]. IEEE Transactions on Information Forensics & Security, 2012, 7(1):76-87. DOI: 10.1109/TIFS.2011.2164908.

[6] RAD R, PLUSQUELLIC J, TEHRANIPOOR M. Sensitivity analysis to hardware Trojans using power supply transient signals[C]// Proceedings of the IEEE International Workshop on Hardware-Oriented Security and Trust. Anaheim: IEEE, 2008:3-7.DOI:10.1109/HST.2008.4559037.

[7] CHA B, GUPTA S K. Trojan detection via delay measurements: a new approach to select paths and vectors to maximize effectiveness and minimize cost[C]// Proceedings of the Design, Automation & Test in Europe Conference & Exhibition. Grenoble: IEEE, 2013:1265-1270. DOI: 10.7873/DATE.2013.262.

[8] JIN Y, MAKRIS Y. Hardware Trojan detection using path delay fingerprint[C]// Proceedings of the IEEE International Workshop on Hardware-Oriented Security and Trust. Anaheim: IEEE, 2008:51-57. DOI: 10.1109/HST.2008.4559049.

[9]XIAO Kan, ZHANG Xuehui, TEHRANIPOOR M. A clock sweeping technique for detecting hardware trojans impacting circuits delay[J]. IEEE Design & Test, 2013, 30(2):26-34. DOI: 10.1109/MDAT.2013.2249555.

[10]BANGA M, HSIAO M S. A novel sustained vector technique for the detection of hardware Trojans[C]// Proceedings of the International Conference on Vlsi Design. New Delhi: IEEE Computer Society, 2009:327-332. DOI: 10.1109/VLSI.Design.2009.22.

[11]趙崇征, 鄧高明,趙強(qiáng). 基于旁路分析的集成電路芯片硬件木馬檢測(cè)[J]. 微電子學(xué)與計(jì)算機(jī), 2011, 28(11):5-9.

ZHAO Chongzheng, DENG Gaoming, ZHAO Qiang. Detecting hardware Trojans in IC chips with side channel analysis[J]. Microelectronics & Computer, 2011, 28(11):5-9.

[12]王力緯, 羅宏偉, 姚若河. 基于旁路分析的硬件木馬檢測(cè)方法[J]. 華南理工大學(xué)學(xué)報(bào):自然科學(xué)版, 2012, 40(6):6-10.

WANG Liwei, LUO Hongwei, YAO Ruohe. Hardware Trojan detection method based on side channel analysis[J]. Journal of South China University of Technology(Natural Science Edition), 2012, 40(6):6-10.

[13]SALMANI H, TEHRANIPOOR M, PLUSQUELLIC J. A novel technique for improving hardware trojan detection and reducing trojan activation time[J]. IEEE Transactions on Very Large Scale Integration Systems, 2012, 20(1):112-125. DOI: 10.1109/TVLSI.2010.2093547.

[14]CHAKRABORTY R S, PAUL S, BHUNIA S. On-demand transparency for improving hardware Trojan detectability[C]// Proceedings of the IEEE International Workshop on Hardware-Oriented Security and Trust. Anaheim: IEEE, 2008:48-50. DOI: 10.1109/HST.2008.4559048.

[15]WOLFF F, PAPACHRISTOU C, BHUNIA S, et al. Towards Trojan-free trusted ICs: problem analysis and detection scheme[C]// Proceedings of the Design, Automation & Test in Europe. Munich: IEEE, 2008:1362-1365. DOI: 10.1109/DATE.2008.4484928.

[16]CHAKRABORTY R S, WOLFF F, PAUL S, et al. MERO: a statistical approach for hardware Trojan detection[M]. Berlin: Springer-Verlag, 2009:51-57.

[17]XUE Mingfu, HU Aiqun, HUANG Yi, et al. Monte Carlo based test pattern generation for hardware trojan detection[C]// Proceedings of the IEEE International Conference on Dependable, Autonomic and Secure Computing. Chengdu: IEEE Computer Society, 2013:131-136. DOI: 10.1109/DASC.2013.50.

[18]ZHOU Bin, ZHANG Wei, SRIKANTHAN T, et al. Cost-efficient acceleration of hardware Trojan detection through fan-out cone analysis and weighted random pattern technique[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015, 35(5):1-1. DOI: 10.1109/TCAD.2015.2460551.

StudyonaccelerationofhardwareTrojandetection

XU Li1, WU Xinchun1, ZHOU Bin2, YE Wenxia1

(1.The School of Information Science and Technology, Southwest Jiao Tong University, Chengdu 611756, China; 2.Research Center of Basic Space Science, Harbin Institute of Technology, Harbin 150001, China)

In order to effectively detect whether the chip is inserted into the hardware Trojan circuit during the design and manufacturing process, a method is proposed to increase the transition probability of the circuit nodes by inserting 2-to-1 MUXs in the chip design stage. The main input of the candidate node whose transition probability is lower than the transition probability threshold is inserted into the MUX to improve the transition probability of the relevant nodes, so as to realize acceleration of hardware Trojan detection in the circuit. The optimization of the insertion algorithm is realized by analyzing the fan-out cone and logic topology, and the node with the greatest influence on the transition probability of the whole circuit is selected as the candidate node, thus the number of MUXs insertion is reduced. Meanwhile, the critical path delay limit is increased to avoid the critical path delay of the circuit exceeding the preset threshold. The input terminals of the pre-designed hardware Trojan circuit are inserted into the nodes with small transition probability in the circuit, and the excitation signal is inputted to the input terminals of the circuit to analyze the change of the circuit’s transition probability and the activation probability of the hardware Trojan circuit before and after the MUX insertion. The experimental results of the ISCAS’89 reference circuit show that the number of nodes whose transition probability is less than the transition probability threshold in the circuit is significantly lower; the probability of the inserted hardware Trojan being activated is significantly improved; the increased percentage of circuit critical path delay is controlled within a preset scale factor.

2-to-1 MUX; hardware Trojan; transition probability; path delay

10.11918/j.issn.0367-6234.201611138

TN407

A

0367-6234(2017)11-0137-06

2016-11-29

國(guó)家自然科學(xué)基金(61100031)

徐 力(1992—)，男，碩士研究生

周 彬，zbhit@hit.edu.cn

(編輯苗秀芝)