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

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

加速硬件木馬檢測方法研究

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

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

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

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

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

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

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

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

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

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

1 提出方法

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

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

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

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

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

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

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

圖1 被插入MUX的邏輯門

1.2插入點選擇算法

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

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

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

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

2 實驗結(jié)果分析

本實驗以ISCAS’89基準電路作為實驗對象，使用STM65納米標準單元庫計算電路信息. 采用C語言搭建實驗平臺進行電路仿真. 在仿真測試過程中，主要輸入端都賦予信號為‘1’的概率為0.5的信號，來計算電路的整體信息.

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

在此實驗當中，以S9234和S5378電路作為基準電路進行測試. 比較在插入前后電路所有節(jié)點的轉(zhuǎn)移概率的變化. 通過圖3、4、5、6可看出，在插入MUX之前電路中有大量轉(zhuǎn)移概率小于轉(zhuǎn)移概率閾值0.05的節(jié)點，其中還有不少tp<10-4的節(jié)點. 通過本文提出的方法，將轉(zhuǎn)移概率閾值設(shè)置為0.05. 在插入MUX之后，整體的轉(zhuǎn)移概率提高，S5378電路中tp<0.05的節(jié)點數(shù)為9個，S9234電路中這一數(shù)字為84個，并且都沒有tp<0.01的節(jié)點. 整體看來通過插入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面積、功耗和延時的增加

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

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

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

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

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

2.3木馬電路的激活

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

圖7 一種5輸入的硬件木馬實例

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

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

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

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

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

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

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

3 結(jié) 論

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

[1] 劉華鋒, 羅宏偉, 王力緯. 硬件木馬綜述[J]. 微電子學, 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]趙崇征, 鄧高明,趙強. 基于旁路分析的集成電路芯片硬件木馬檢測[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]王力緯, 羅宏偉, 姚若河. 基于旁路分析的硬件木馬檢測方法[J]. 華南理工大學學報:自然科學版, 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

國家自然科學基金(61100031)

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

周 彬，zbhit@hit.edu.cn

(編輯苗秀芝)