基于探索式分区和测试向量生成的硬件木马检测方法

薛明富，胡爱群，王　箭

(1.南京航空航天大学计算机科学与技术学院，江苏南京 210016； 2.东南大学信息科学与工程学院，江苏南京 210096；3.中国民航大学中国民航信息技术科研基地，天津 300300;4.软件新技术与产业化协同创新中心，江苏南京 210023)



基于探索式分区和测试向量生成的硬件木马检测方法

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

(1.南京航空航天大学计算机科学与技术学院，江苏南京 210016； 2.东南大学信息科学与工程学院，江苏南京 210096；3.中国民航大学中国民航信息技术科研基地，天津 300300;4.软件新技术与产业化协同创新中心，江苏南京 210023)

本文提出基于分区和最优测试向量生成的硬件木马检测方法.首先，采用基于扫描细胞分布的分区算法将电路划分为多个区域.然后，提出测试向量重组算法，对各区域依据其自身结构生成近似最优的测试向量.最后，进行分区激活和功耗分析以检测木马，并采用信号校正技术消减制造变异和噪声的影响.优点是成倍提高了检测精度，克服了制造变异的影响，解决了面对大电路的扩展性问题，并可以定位木马.在基准电路上的验证实验表明检测性能有较大的提升.

硬件安全；硬件木马检测；探索式分区；最优测试向量生成

1　引言

硬件行业全球化的生产模式，使得集成电路(Integrated circuits，IC)容易受到恶意修改的威胁[1～7]，俗称为硬件木马(Hardware Trojan，HT)，它可以在特定条件或时刻触发，然后破坏、关闭、控制芯片/系统，或者泄露机密信息.硬件所面临的安全威胁和巨额经济损失已经引起了工业界和敏感部门的高度重视，亟待研究解决.

文献[8]通过多次触发电路内部节点的稀有逻辑条件去增加逻辑测试的检测机率.逻辑测试法很难触发有着复杂触发条件的木马.基于旁道参数分析的硬件木马检测方法被证实可以通过观测电路的时延、功耗、电流等来检测出木马[9,10].然而，原旁道参数分析法不足以克服制造变异(process variation,PV)和噪声的影响.在现代纳米工艺下，制造变异对IC的影响不断增加，能完全覆盖掉木马对电路的影响[1～7].另外，这种观测电路全局信号的方式，面对大电路时不具有扩展性.因此，一些区域化激活的方法被用来放大木马的影响[11～13]，然而，这些方法都是采用大量的随机向量盲目地测试，或者辅以计算复杂度很高或者很耗时的测试向量训练过程，其检测灵敏度并不理想.文献[14]提出信号校正技术消减PV的影响，然而，该方法没有考虑到测试向量的影响，测试向量引起的电路中其他元件的翻转活动也会覆盖掉木马对电路引入的异常.

已有工作大多假设可以通过可信的方式获得干净样本芯片，由样本芯片提供参考以检测木马.这成为当下研究方法的普遍瓶颈.已有少量工作开始探索如何不依赖于参考芯片去检测木马[15～17].这些探索均有一定的局限性，常见的代价是需要昂贵的计算量、复杂的PV模型，面对大规模芯片时为了确保精确度需要大量反复测试.

本文提出基于分区和最优测试向量生成的硬件木马检测方法.首先，采用基于扫描细胞分布的探索式分区算法将电路虚拟划分为由扫描链控制的各个区域.然后，针对已有工作均采用大量随机向量盲目测试的问题，基于权重翻转(Weighted Transition，WT)指标，提出了测试向量重组算法(Test Vector Ordering，TVO)，该算法基于电路结构生成近似最优的测试向量，可以最大程度地触发目标区域.然后，在各个区域中间放置功耗管脚进行局域化的功耗测量分析以检测木马.最后，采用信号校正技术[14]消减制造变异和噪声的影响.相比已有工作，优点是成倍提升了检测精度，解决了面向大电路的扩展性问题，克服了制造变异的影响，并可以定位木马的位置.在ISCAS89基准电路上验证了本方案，并与已有检测方法[9,13,14]进行了比较，结果表明检测性能得到较大提升.

2　问题建模

电路中的功耗由静态功耗和动态功耗组成[18].静态功耗Pst是由泄漏电流引起，动态功耗包括切换瞬态电流引起的功耗Psc和负载功放充放电引起的功耗Pd.因此，总功耗为：

Ptotal=Pst+Pd+Psc

(1)

与Pd相比，Pst和Psc是可以忽略的[18].Pd约为：

(2)

其中，C是电容，NG是门的输出翻转的总数目，VDD是供应电压，f是工作频率.因此，功耗与翻转次数成正比.扫描链测试结构是时序电路常用的结构，可以近似地认为扫描链控制电路的翻转活动.在扫描测试时，功耗正比于扫描链上的翻转数目.

本文定义评估木马检测能力的指标——功耗差异百分比(PercentageDifferenceBetweenPowerConsumption，PDPC).假设电路分为M个区域，区域x的PDPC定义如下：

(3)其中，PCUA(x)是待测电路(CircuitUnderAuthentication,CUA)中区域x的功耗，PG(x)是样本芯片中区域x的功耗.

3　整体方案框架

本方案步骤如下.首先，采用基于扫描细胞分布的分区算法将电路划分为多个区域.然后，连接同一个区域内的扫描细胞形成扫描链，电路就被划分为由扫描链控制的各个区域.然后，执行测试向量生成算法以最大化目标区域的翻转活动.最后，在每个区域中间放置电源管脚，插入小规模的校正电路[14]用于建模PV和噪声的信息.

如图1所示(N为功耗管脚数目)，在检测阶段，首先执行校正测试去收集校正数据和构建转换矩阵.然后，用TVO向量输入到目标区域的扫描链，其他区域的扫描链输入持续的0向量以保持背景活动是沉寂的.此时，首先比较CUA与干净电路的输出是否一致，如果不一致，则检测出了木马，如果一致，则进入下一步.然后，测量多个功耗管脚的瞬态电流，并进行信号校正.最后，分析局域化IDDT(动态电流)数据用于木马检测.

4　基于扫描细胞分布的分区算法

4.1分区算法

本文将文献[19]的聚类算法进行了修改应用于木马检测，伪代码如算法1所示.首先，计算电路切割的数目.然后，提取各扫描细胞的物理位置信息，移除扫描细胞之间已有的连接.然后，将扫描细胞的物理信息表征为横纵坐标(X、Y).然后，将一个区域递归式的切割为扫描细胞数目相等的两个区域.然后，重新连接同一区域内的扫描细胞，于是每个区域形成了一条扫描链.接下来，优化扫描链布线以避免拥塞.最后，在每个区域中间放置功耗管脚用于IDDT分析.图2给出了在ISCAS89基准电路s953上实现的分区算法示意图.

4.2时间复杂度分析及测试实验

表1　区域组合激活和独立激活的PDPC值

5　最优测试向量生成算法

本文采用WT指标[20]去预测扫描测试时测试序列引起的功耗.WT如下计算：

WT=∑(k-PT)

(4)

其中，WT是翻转的数目，k是扫描链的长度，PT是发生翻转的位置.对于输入向量和输出向量，PT的值是相反的.当输入向量的第一比特与上一个输出向量的最后一个比特不同时，会产生额外的翻转，该翻转会传过整个扫描链.

TVO算法的伪码如算法2所示.算法的输入是一组测试向量及其输出向量，算法的输出是重组过的测试向量集.下面以图3(a)的样例序列介绍算法流程.首先，计算每两位之间的比特差异数目.然后，利用比特差异数目构建无向加权图，如图3(b)所示，图中，每个顶点表示一位，每条边上的权重反映了这两位连接在一起时会产生的翻转数目.然后，为了找到最大翻转顺序，将图中的权重改为其倒数，去使得这个问题等价于旅行商问题(TravelingSalesmanProblem，TSP).因为TSP是NP-hard的问题[21]，本文采用遗传算法来解决这个问题，可以在很短时间内找到近似最优解.本文的遗传算法中，将可能的比特顺序作为个体，采用部分映射交叉[22]和点突变算子[23]作为交叉算子和变异算子，用WT作为适应函数.将上述步骤得到的比特位顺序表示为定向循环图，如图3(c)所示.然后，根据WT值评估k种可能的情况，并选择拥有最大WT值的顺序.最后，基于上述结果顺序执行测试向量重组，结果如图3(d)所示.

6　验证实验

6.1实验设置

本节给出验证实验，并与已有的代表性方法进行对比，包括原旁道参数分析法[9]、分区随机向量激活法[13]和信号校正法[14].评估的性能包括：定位、检测灵敏度、测试向量的影响、面临大电路的扩展性和信号校正的效果.设计了两个组合木马(T1、T2)和一个时序木马(T3)插入到ISCAS89基准电路中，如图4所示，这些木马不具有真实的恶意功能，仅是对电路的微小改动用于评估本方案的检测能力.

6.2实验结果

区域激活实验显示电路活动主要局限在目标区域，而其他区域只有微弱的翻转活动.图5给出了电路s15850、s35932和s38417的分区激活检测效果.结果表明，当激活了木马所在的区域时，木马引入的差异得到了大幅放大.结果表征了木马所在的位置，因为有着较高PDPC值的区域最有可能是木马所在区域.

表2给出了检测灵敏度分析与对比.首先对比本方法与原旁道参数检测方法[9]，即第9列对比第3列，很明显，经过分区、优化测试向量和信号校正之后，检测精度放大高达37倍(0.4641673%/0.0125487%).如果不采用信号校正，即第6列对比第3列，可以看出，经过分区、优化测试向量后，检测精度放大高达33.66倍.图6给出了原旁道参数分析法[9](全局测量)和分区数目分别为4、16和32时分区激活方案的检测结果.由图可知，分区数目越高，检测精度也越高.

表2　硬件木马检测灵敏度分析(PDPC值)

图7给出了使用随机向量[13，14]和本文的TVO向量进行分区激活的检测效果对比，并绘出了原旁道参数法的检测结果用于参照.可知，TVO向量能够比随机向量取得更高的检测精度.表2的第6列和第5列也给出了TVO向量和随机向量的比较，TVO向量比随机向量的检测灵敏度提升高达41.05%.

原旁道参数分析法[9]是监测全局信号，不能够扩展到大电路.图8给出了扩展性对比，可知，原旁道参数法仅能够检测到s5378中的T3，随着电路规模的增大，其检测灵敏度不断衰减.本方案可以有效地放大木马的影响，检测到所有基准电路中的T3.对于规模较大的电路，只需采用更多的分区数目即可保证检测精度，具有较好的扩展性.

表2的最后一列给出了采用信号校正后的检测结果，可以看出，使用信号校正技术之后，木马检测灵敏度有了明显增加.这个校正一定程度地消减了PV和噪声的影响，从而凸显了木马引入的异常.

7　小结

硬件木马已成为信息安全一个紧迫的新兴威胁.本文提出了基于分区和测试向量生成的局域化IDDT分析方法检测硬件木马.局域化分析可以放大检测灵敏度，确保面对大电路时的扩展性，并可定位木马的位置.本文还提出了优化向量生成方法，可以解决已有工作采用大量随机向量盲目测试的问题.实验显示所提方案可以大幅提升检测灵敏度.以后的工作将研究不需要样本芯片的硬件木马检测方案.

[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年于东南大学获工学博士学位，2011-2012年于新加坡南洋理工大学联合培养，现为南京航空航天大学计算机科学与技术学院讲师，主要从事硬件安全、硬件木马检测、硬件IP保护方面的研究.

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

胡爱群男，1965年出生，东南大学信息科学与工程学院教授、博士生导师，东南大学信息安全研究中心主任，主要从事无线通信安全与移动终端安全方面的研究工作.1987年6月获南京工学院无线电技术专业学士学位，1990年4月获东南大学信号电路与系统专业硕士学位，1993年4月获东南大学信号与信息处理专业博士学位，1997.11-1998.10在香港大学电机电子工程系从事博士后研究.

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；责任编辑：马兰英

江苏省自然科学基金青年基金(No.BK20150758)；中国博士后科学基金面上资助(No.2014M561644)；江苏省博士后基金科研资助(No.1402034C)；中国民航信息技术科研基地开放课题基金(No.CAAC-ITRB-201405)；中央高校基本科研业务费专项资金资助(No.NS2016096)

TP309

A

0372-2112 (2016)05-1132-07

电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.017