薛明富，胡愛群，王　箭

(1.南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇南京 210016； 2.東南大學(xué)信息科學(xué)與工程學(xué)院，江蘇南京 210096；3.中國民航大學(xué)中國民航信息技術(shù)科研基地，天津 300300;4.軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，江蘇南京 210023)

?

基于探索式分區(qū)和測試向量生成的硬件木馬檢測方法

薛明富1,2,3,4，胡愛群2，王箭1,4

(1.南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇南京 210016； 2.東南大學(xué)信息科學(xué)與工程學(xué)院，江蘇南京 210096；3.中國民航大學(xué)中國民航信息技術(shù)科研基地，天津 300300;4.軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，江蘇南京 210023)

本文提出基于分區(qū)和最優(yōu)測試向量生成的硬件木馬檢測方法.首先，采用基于掃描細(xì)胞分布的分區(qū)算法將電路劃分為多個區(qū)域.然后，提出測試向量重組算法，對各區(qū)域依據(jù)其自身結(jié)構(gòu)生成近似最優(yōu)的測試向量.最后，進(jìn)行分區(qū)激活和功耗分析以檢測木馬，并采用信號校正技術(shù)消減制造變異和噪聲的影響.優(yōu)點是成倍提高了檢測精度，克服了制造變異的影響，解決了面對大電路的擴(kuò)展性問題，并可以定位木馬.在基準(zhǔn)電路上的驗證實驗表明檢測性能有較大的提升.

硬件安全；硬件木馬檢測；探索式分區(qū)；最優(yōu)測試向量生成

1　引言

硬件行業(yè)全球化的生產(chǎn)模式，使得集成電路(Integrated circuits，IC)容易受到惡意修改的威脅[1～7]，俗稱為硬件木馬(Hardware Trojan，HT)，它可以在特定條件或時刻觸發(fā)，然后破壞、關(guān)閉、控制芯片/系統(tǒng)，或者泄露機(jī)密信息.硬件所面臨的安全威脅和巨額經(jīng)濟(jì)損失已經(jīng)引起了工業(yè)界和敏感部門的高度重視，亟待研究解決.

文獻(xiàn)[8]通過多次觸發(fā)電路內(nèi)部節(jié)點的稀有邏輯條件去增加邏輯測試的檢測機(jī)率.邏輯測試法很難觸發(fā)有著復(fù)雜觸發(fā)條件的木馬.基于旁道參數(shù)分析的硬件木馬檢測方法被證實可以通過觀測電路的時延、功耗、電流等來檢測出木馬[9,10].然而，原旁道參數(shù)分析法不足以克服制造變異(process variation,PV)和噪聲的影響.在現(xiàn)代納米工藝下，制造變異對IC的影響不斷增加，能完全覆蓋掉木馬對電路的影響[1～7].另外，這種觀測電路全局信號的方式，面對大電路時不具有擴(kuò)展性.因此，一些區(qū)域化激活的方法被用來放大木馬的影響[11～13]，然而，這些方法都是采用大量的隨機(jī)向量盲目地測試，或者輔以計算復(fù)雜度很高或者很耗時的測試向量訓(xùn)練過程，其檢測靈敏度并不理想.文獻(xiàn)[14]提出信號校正技術(shù)消減PV的影響，然而，該方法沒有考慮到測試向量的影響，測試向量引起的電路中其他元件的翻轉(zhuǎn)活動也會覆蓋掉木馬對電路引入的異常.

已有工作大多假設(shè)可以通過可信的方式獲得干凈樣本芯片，由樣本芯片提供參考以檢測木馬.這成為當(dāng)下研究方法的普遍瓶頸.已有少量工作開始探索如何不依賴于參考芯片去檢測木馬[15～17].這些探索均有一定的局限性，常見的代價是需要昂貴的計算量、復(fù)雜的PV模型，面對大規(guī)模芯片時為了確保精確度需要大量反復(fù)測試.

本文提出基于分區(qū)和最優(yōu)測試向量生成的硬件木馬檢測方法.首先，采用基于掃描細(xì)胞分布的探索式分區(qū)算法將電路虛擬劃分為由掃描鏈控制的各個區(qū)域.然后，針對已有工作均采用大量隨機(jī)向量盲目測試的問題，基于權(quán)重翻轉(zhuǎn)(Weighted Transition，WT)指標(biāo)，提出了測試向量重組算法(Test Vector Ordering，TVO)，該算法基于電路結(jié)構(gòu)生成近似最優(yōu)的測試向量，可以最大程度地觸發(fā)目標(biāo)區(qū)域.然后，在各個區(qū)域中間放置功耗管腳進(jìn)行局域化的功耗測量分析以檢測木馬.最后，采用信號校正技術(shù)[14]消減制造變異和噪聲的影響.相比已有工作，優(yōu)點是成倍提升了檢測精度，解決了面向大電路的擴(kuò)展性問題，克服了制造變異的影響，并可以定位木馬的位置.在ISCAS89基準(zhǔn)電路上驗證了本方案，并與已有檢測方法[9,13,14]進(jìn)行了比較，結(jié)果表明檢測性能得到較大提升.

2　問題建模

電路中的功耗由靜態(tài)功耗和動態(tài)功耗組成[18].靜態(tài)功耗Pst是由泄漏電流引起，動態(tài)功耗包括切換瞬態(tài)電流引起的功耗Psc和負(fù)載功放充放電引起的功耗Pd.因此，總功耗為：

Ptotal=Pst+Pd+Psc

(1)

與Pd相比，Pst和Psc是可以忽略的[18].Pd約為：

(2)

其中，C是電容，NG是門的輸出翻轉(zhuǎn)的總數(shù)目，VDD是供應(yīng)電壓，f是工作頻率.因此，功耗與翻轉(zhuǎn)次數(shù)成正比.掃描鏈測試結(jié)構(gòu)是時序電路常用的結(jié)構(gòu)，可以近似地認(rèn)為掃描鏈控制電路的翻轉(zhuǎn)活動.在掃描測試時，功耗正比于掃描鏈上的翻轉(zhuǎn)數(shù)目.

本文定義評估木馬檢測能力的指標(biāo)——功耗差異百分比(PercentageDifferenceBetweenPowerConsumption，PDPC).假設(shè)電路分為M個區(qū)域，區(qū)域x的PDPC定義如下：

(3)其中，PCUA(x)是待測電路(CircuitUnderAuthentication,CUA)中區(qū)域x的功耗，PG(x)是樣本芯片中區(qū)域x的功耗.

3　整體方案框架

本方案步驟如下.首先，采用基于掃描細(xì)胞分布的分區(qū)算法將電路劃分為多個區(qū)域.然后，連接同一個區(qū)域內(nèi)的掃描細(xì)胞形成掃描鏈，電路就被劃分為由掃描鏈控制的各個區(qū)域.然后，執(zhí)行測試向量生成算法以最大化目標(biāo)區(qū)域的翻轉(zhuǎn)活動.最后，在每個區(qū)域中間放置電源管腳，插入小規(guī)模的校正電路[14]用于建模PV和噪聲的信息.

如圖1所示(N為功耗管腳數(shù)目)，在檢測階段，首先執(zhí)行校正測試去收集校正數(shù)據(jù)和構(gòu)建轉(zhuǎn)換矩陣.然后，用TVO向量輸入到目標(biāo)區(qū)域的掃描鏈，其他區(qū)域的掃描鏈輸入持續(xù)的0向量以保持背景活動是沉寂的.此時，首先比較CUA與干凈電路的輸出是否一致，如果不一致，則檢測出了木馬，如果一致，則進(jìn)入下一步.然后，測量多個功耗管腳的瞬態(tài)電流，并進(jìn)行信號校正.最后，分析局域化IDDT(動態(tài)電流)數(shù)據(jù)用于木馬檢測.

4　基于掃描細(xì)胞分布的分區(qū)算法

4.1分區(qū)算法

本文將文獻(xiàn)[19]的聚類算法進(jìn)行了修改應(yīng)用于木馬檢測，偽代碼如算法1所示.首先，計算電路切割的數(shù)目.然后，提取各掃描細(xì)胞的物理位置信息，移除掃描細(xì)胞之間已有的連接.然后，將掃描細(xì)胞的物理信息表征為橫縱坐標(biāo)(X、Y).然后，將一個區(qū)域遞歸式的切割為掃描細(xì)胞數(shù)目相等的兩個區(qū)域.然后，重新連接同一區(qū)域內(nèi)的掃描細(xì)胞，于是每個區(qū)域形成了一條掃描鏈.接下來，優(yōu)化掃描鏈布線以避免擁塞.最后，在每個區(qū)域中間放置功耗管腳用于IDDT分析.圖2給出了在ISCAS89基準(zhǔn)電路s953上實現(xiàn)的分區(qū)算法示意圖.

4.2時間復(fù)雜度分析及測試實驗

表1　區(qū)域組合激活和獨立激活的PDPC值

5　最優(yōu)測試向量生成算法

本文采用WT指標(biāo)[20]去預(yù)測掃描測試時測試序列引起的功耗.WT如下計算：

WT=∑(k-PT)

(4)

其中，WT是翻轉(zhuǎn)的數(shù)目，k是掃描鏈的長度，PT是發(fā)生翻轉(zhuǎn)的位置.對于輸入向量和輸出向量，PT的值是相反的.當(dāng)輸入向量的第一比特與上一個輸出向量的最后一個比特不同時，會產(chǎn)生額外的翻轉(zhuǎn)，該翻轉(zhuǎn)會傳過整個掃描鏈.

TVO算法的偽碼如算法2所示.算法的輸入是一組測試向量及其輸出向量，算法的輸出是重組過的測試向量集.下面以圖3(a)的樣例序列介紹算法流程.首先，計算每兩位之間的比特差異數(shù)目.然后，利用比特差異數(shù)目構(gòu)建無向加權(quán)圖，如圖3(b)所示，圖中，每個頂點表示一位，每條邊上的權(quán)重反映了這兩位連接在一起時會產(chǎn)生的翻轉(zhuǎn)數(shù)目.然后，為了找到最大翻轉(zhuǎn)順序，將圖中的權(quán)重改為其倒數(shù)，去使得這個問題等價于旅行商問題(TravelingSalesmanProblem，TSP).因為TSP是NP-hard的問題[21]，本文采用遺傳算法來解決這個問題，可以在很短時間內(nèi)找到近似最優(yōu)解.本文的遺傳算法中，將可能的比特順序作為個體，采用部分映射交叉[22]和點突變算子[23]作為交叉算子和變異算子，用WT作為適應(yīng)函數(shù).將上述步驟得到的比特位順序表示為定向循環(huán)圖，如圖3(c)所示.然后，根據(jù)WT值評估k種可能的情況，并選擇擁有最大WT值的順序.最后，基于上述結(jié)果順序執(zhí)行測試向量重組，結(jié)果如圖3(d)所示.

6　驗證實驗

6.1實驗設(shè)置

本節(jié)給出驗證實驗，并與已有的代表性方法進(jìn)行對比，包括原旁道參數(shù)分析法[9]、分區(qū)隨機(jī)向量激活法[13]和信號校正法[14].評估的性能包括：定位、檢測靈敏度、測試向量的影響、面臨大電路的擴(kuò)展性和信號校正的效果.設(shè)計了兩個組合木馬(T1、T2)和一個時序木馬(T3)插入到ISCAS89基準(zhǔn)電路中，如圖4所示，這些木馬不具有真實的惡意功能，僅是對電路的微小改動用于評估本方案的檢測能力.

6.2實驗結(jié)果

區(qū)域激活實驗顯示電路活動主要局限在目標(biāo)區(qū)域，而其他區(qū)域只有微弱的翻轉(zhuǎn)活動.圖5給出了電路s15850、s35932和s38417的分區(qū)激活檢測效果.結(jié)果表明，當(dāng)激活了木馬所在的區(qū)域時，木馬引入的差異得到了大幅放大.結(jié)果表征了木馬所在的位置，因為有著較高PDPC值的區(qū)域最有可能是木馬所在區(qū)域.

表2給出了檢測靈敏度分析與對比.首先對比本方法與原旁道參數(shù)檢測方法[9]，即第9列對比第3列，很明顯，經(jīng)過分區(qū)、優(yōu)化測試向量和信號校正之后，檢測精度放大高達(dá)37倍(0.4641673%/0.0125487%).如果不采用信號校正，即第6列對比第3列，可以看出，經(jīng)過分區(qū)、優(yōu)化測試向量后，檢測精度放大高達(dá)33.66倍.圖6給出了原旁道參數(shù)分析法[9](全局測量)和分區(qū)數(shù)目分別為4、16和32時分區(qū)激活方案的檢測結(jié)果.由圖可知，分區(qū)數(shù)目越高，檢測精度也越高.

表2　硬件木馬檢測靈敏度分析(PDPC值)

圖7給出了使用隨機(jī)向量[13，14]和本文的TVO向量進(jìn)行分區(qū)激活的檢測效果對比，并繪出了原旁道參數(shù)法的檢測結(jié)果用于參照.可知，TVO向量能夠比隨機(jī)向量取得更高的檢測精度.表2的第6列和第5列也給出了TVO向量和隨機(jī)向量的比較，TVO向量比隨機(jī)向量的檢測靈敏度提升高達(dá)41.05%.

原旁道參數(shù)分析法[9]是監(jiān)測全局信號，不能夠擴(kuò)展到大電路.圖8給出了擴(kuò)展性對比，可知，原旁道參數(shù)法僅能夠檢測到s5378中的T3，隨著電路規(guī)模的增大，其檢測靈敏度不斷衰減.本方案可以有效地放大木馬的影響，檢測到所有基準(zhǔn)電路中的T3.對于規(guī)模較大的電路，只需采用更多的分區(qū)數(shù)目即可保證檢測精度，具有較好的擴(kuò)展性.

表2的最后一列給出了采用信號校正后的檢測結(jié)果，可以看出，使用信號校正技術(shù)之后，木馬檢測靈敏度有了明顯增加.這個校正一定程度地消減了PV和噪聲的影響，從而凸顯了木馬引入的異常.

7　小結(jié)

硬件木馬已成為信息安全一個緊迫的新興威脅.本文提出了基于分區(qū)和測試向量生成的局域化IDDT分析方法檢測硬件木馬.局域化分析可以放大檢測靈敏度，確保面對大電路時的擴(kuò)展性，并可定位木馬的位置.本文還提出了優(yōu)化向量生成方法，可以解決已有工作采用大量隨機(jī)向量盲目測試的問題.實驗顯示所提方案可以大幅提升檢測靈敏度.以后的工作將研究不需要樣本芯片的硬件木馬檢測方案.

[1]Jeyavijayan Rajendran,Ozgur Sinanoglu,Ramesh Karri.Regaining trust in VLSI design:Design-for-trust techniques[J].Proceedings of the IEEE,2014,102(8):1266-1282.

[2]Swarup Bhunia,Michael S.Hsiao,Mainak Banga,Seetharam Narasimhan.Hardware trojan attacks:Threat analysis and countermeasures[J].Proceedings of the IEEE,2014,102(8):1229-1247.

[3]Masoud Rostami,Farinaz Koushanfar,Ramesh Karri.A primer on hardware security:models,methods,and metrics[J].Proceedings of the IEEE,2014,102(8):1283-1295.

[4]M Rostami,F Koushanfar,J Rajendran,R Karri.Hardware security:Threat models and metrics[A].Proc.Int.Conf.Comput.-Aided Design (ICCAD)[C].San Jose,CA,Nov.2013.819-823.

[5]S Bhunia,et al.Protection against hardware Trojan attacks:Towards a comprehensive solution[J].IEEE Design Test Comput.,2013,30(3):6-17.

[6]Mohammad Tehranipoor,Farinaz Koushanfar.A survey of hardware trojan taxonomy and detection[J].IEEE design & test of computers,2010,27(1):10-25.

[7]Rajat Subhra Chakraborty,Seetharam Narasimhan,Swarup Bhunia.Hardware trojan:threats and emerging solutions[A].IEEE International High Level Design Validation and Test Workshop (HLDVT)[C].San Francisco,CA,Nov.2009.166-171.

[8]Rajat Subhra Chakraborty,Francis Wolff,Somnath Paul,et al.MERO:A statistical approach for hardware trojan detection[A].Workshop on Cryptographic Hardware and Embedded Systems (CHES)[C].Lausanne,Switzerland,Sep.2009.396-410.

[9]Dakshi Agrawal,Selcuk Baktlr,Deniz Karakoyunlu,et al.Trojan detection using IC fingerprinting[A].Proceedings of IEEE Symposium on Security and Privacy (SP07)[C].Berkeley,CA,May 2007.296-310.

[10]Y Jin,Y Makris.Hardware trojan detection using path delay fingerprint[A].Proceedings of IEEE International Hardware-Oriented Security and Trust (HOST08)[C].Anaheim,CA,June 2008.51-57.

[11]M Banga,M Hsiao.A region based approach for the identification of hardware trojans[A].Proceedings of IEEE International Workshop on Hardware-Oriented Security and Trust (HOST2008)[C].Anaheim,CA,June 2008.40-47.

[12]Sheng Wei,Miodrag Potkonjak.Scalable hardware trojan diagnosis[J].IEEE Transactions on very large scale integration (VLSI) systems,2012,20(6):1049-1057.

[13]Hassan Salmani,Mohammad Tehranipoor.Layout-aware switching activity localization to enhance hardware trojan detection[J].IEEE Transactions on Information Forensics and Security,2012,7(1):76-87.

[14]Jim Aarestad,Dhruva Acharyya,Reza Rad,et al.Detecting trojans through leakage current analysis using multiple supply pad IDDQs[J].IEEE Transactions on information forensics and security,2010,5(4):893-904.

[15]Sheng Wei,Miodrag Potkonjak.Self-consistency and consistency-based detection and diagnosis of malicious circuitry[J].IEEE Transactions on Very Large Scale Integration (VLSI) systems,2014,22(9):1845-1853.

[16]Azadeh Davoodi,Min Li,Mohammad Tehranipoor.A sensor-assisted self-authentication framework for hardware trojan detection[J].IEEE Design and Test,2013,30(5):74-82.

[17]Kan Xiao,Domenic Forte,Mohammed Tehranipoor.A novel built-in self-authentication technique to prevent inserting hardware trojans[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2014,33(12):1778-1791.

[18]Vinay Dabholkar,Sreejit Chakravarty,Irith Pomeranz,et al.Techniques for minimizing power dissipation in scan and combinational circuits during test application[J].IEEE Transactions on computer-aided design of integrated circuits and systems,1998,17(12):1325-1333.

[19]Y Bonhomme,P Girard,L Guiller,et al.Design of routing-constrained low power scan chains[A].Proceedings of the Second IEEE International Workshop on Electronic Design,Test and Applications (DELTA 2004)[C].Perth,WA,Australia,Jan.2004.287-292.

[20]Y Bonhomme,P Girard,C Landrault,et al.Power driven chaining of flip-flops in scan architectures[A].IEEE International Test Conference (ITC)[C].Baltimore,MD,USA,Oct.2002.796-803.

[21]P Larranaga,C M H Kuijpers,R H Murga,et al.Genetic algorithms for the travelling salesman problem:A review of representations and operators[J].Artificial Intelligence Review,1999(13):129-170.

[22]Goldberg D E,Robert Lingle Jr Alleles.Loci and the TSP[A].In Grefenstette,J.J.(ed.) Proceedings of the First International Conference on Genetic Algorithms and Their Applications[C].Hillsdale,New Jersey,Lawrence Erlbaum,1985.154-159.

[23]Ambati B K,Ambati J,Mokhtar M M.Heuristic combinatorial optimization by simulated darwinian evolution:A polynomial time algorithm for the traveling salesman problem[J].Biological Cybernetics,1991,65(1):31-35.

薛明富(通信作者)男，1986年12月出生，江蘇南京人.2014年于東南大學(xué)獲工學(xué)博士學(xué)位，2011-2012年于新加坡南洋理工大學(xué)聯(lián)合培養(yǎng)，現(xiàn)為南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院講師，主要從事硬件安全、硬件木馬檢測、硬件IP保護(hù)方面的研究.

E-mail:mingfu.xue@nuaa.edu.cn

胡愛群男，1965年出生，東南大學(xué)信息科學(xué)與工程學(xué)院教授、博士生導(dǎo)師，東南大學(xué)信息安全研究中心主任，主要從事無線通信安全與移動終端安全方面的研究工作.1987年6月獲南京工學(xué)院無線電技術(shù)專業(yè)學(xué)士學(xué)位，1990年4月獲東南大學(xué)信號電路與系統(tǒng)專業(yè)碩士學(xué)位，1993年4月獲東南大學(xué)信號與信息處理專業(yè)博士學(xué)位，1997.11-1998.10在香港大學(xué)電機(jī)電子工程系從事博士后研究.

E-mail:aqhu@seu.edu.cn

A Novel Hardware Trojan Detection Technique Using Heuristic Partition and Test Pattern Generation

XUE Ming-fu1,2,3，4,HU Ai-qun2,WANG Jian1，4

(1.CollegeofComputerScienceandTechnology,NanjingUniversityofAeronauticsandAstronautics,Nanjing,Jiangsu210016,China;2.SchoolofInformationScienceandEngineering,SoutheastUniversity,Nanjing,Jiangsu210096,China;3.InformationTechnologyResearchBaseofCivilAviationAdministrationofChina,CivilAviationUniversityofChina,Tianjin300300,China; 4.CollaborativeInnovationCenterofNovelSoftwareTechnologyandIndustrialization,Nanjing,Jiangsu210023,China)

A novel hardware Trojan detection method based on heuristic partition and optimal test pattern generation is proposed.First,we use a scan cell distribution based heuristic partition to divide the circuit into regions.Then,we propose a test vector ordering algorithm to generate near-optimal test patterns based on the circuit’s structure.Lastly,we activate each region separately and perform localizedIDDTanalysis to detect hardware Trojans while a signal calibration technique is used to eliminate the effect of process variations and noises.The benefits of this approach are that it can magnify detection sensitivity,eliminate the effects of process variations and noises,ensure the scalability of hardware Trojan detection facing large scale ICs,and determine Trojan’s location.We evaluate our approach on benchmark circuits and the experiment results show that the detection sensitivity is greatly improved.

hardware security;hardware Trojan detection;heuristic partition;optimal test pattern generation

2014-10-23;

2015-05-22；責(zé)任編輯：馬蘭英

江蘇省自然科學(xué)基金青年基金(No.BK20150758)；中國博士后科學(xué)基金面上資助(No.2014M561644)；江蘇省博士后基金科研資助(No.1402034C)；中國民航信息技術(shù)科研基地開放課題基金(No.CAAC-ITRB-201405)；中央高校基本科研業(yè)務(wù)費專項資金資助(No.NS2016096)

TP309

A

0372-2112 (2016)05-1132-07

電子學(xué)報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.017