MathJax.Hub.Config({tex2jax: {inlineMath: [['$', '$'], ['\\(', '\\)']]}});
  哈尔滨工业大学学报  2017, Vol. 49 Issue (11): 137-142  DOI: 10.11918/j.issn.0367-6234.201611138
0

引用本文 

徐力, 吴新春, 周彬, 叶文霞. 加速硬件木马检测方法研究[J]. 哈尔滨工业大学学报, 2017, 49(11): 137-142. DOI: 10.11918/j.issn.0367-6234.201611138.
XU Li, WU Xinchun, ZHOU Bin, YE Wenxia. Study on acceleration of hardware Trojan detection[J]. Journal of Harbin Institute of Technology, 2017, 49(11): 137-142. DOI: 10.11918/j.issn.0367-6234.201611138.

基金项目

国家自然科学基金(61100031)

作者简介

徐力(1992—),男,硕士研究生

通信作者

周彬, zbhit@hit.edu.cn

文章历史

收稿日期: 2016-11-29
加速硬件木马检测方法研究
徐力1, 吴新春1, 周彬2, 叶文霞1     
1. 西南交通大学 信息科学与技术学院,成都 611756;
2. 哈尔滨工业大学 空间基础科学研究中心,哈尔滨 150001
摘要: 为有效检测出芯片在设计和外包制造过程中是否被插入硬件木马电路, 提出一种在芯片设计阶段插入二选一数据选择器(MUX)来提高电路节点转移概率的方法.即在电路中转移概率低于转移概率阈值的候选节点的主要输入端插入MUX来提高相关节点的转移概率, 从而实现加速电路中硬件木马的检测.通过对扇出锥和电路逻辑拓扑结构的分析,选择对整个电路转移概率影响最大的节点作为候选节点,实现对MUX插入算法的优化,从而减少MUX的插入数量.同时增加关键路径延时限制,避免电路关键路径延迟超过预先设定的阈值.将预先设计的硬件木马电路的输入端插入在电路中转移概率较小的节点,并向电路输入端输入激励信号,分析计算在MUX插入前后电路转移概率变化以及硬件木马电路的激活概率. ISCAS'89基准电路的实验结果表明:在插入MUX之后,电路整体转移概率显著提高,电路中转移概率小于转移概率阈值的节点数明显降低;被插入在电路中的硬件木马被激活的概率显著提高;电路关键路径延时增加百分比控制在预先设定的比例因子之内.
关键词: 二选一数据选择器     硬件木马     转移概率     路径延时    
Study on acceleration of hardware Trojan detection
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
Abstract: 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.
Key words: 2-to-1 MUX     hardware Trojan     transition probability     path delay    

硬件木马也被称之为恶意电路,是在第三方IP或者制造过程中插入到电路中的微小电路模块.一般情况下在电路系统中并不发挥作用,但在特定情况下会被激活.一旦激活后可能改变电路功能、损坏电路甚至泄露电路信息,从而达到插入者的目的,危害可想而知[1].硬件木马模块相对于整个电路结构而言十分微小,激活前并不改变电路功能,使得硬件木马的检测变得十分困难.

除此之外,硬件木马可连接到电路网表的任何节点上,尤其是那些转移概率相对较低的节点.传统自动测试矢量生成算法(ATPG)并不能有效的激活和检测硬件木马.尤其当硬件木马的输入端连接到转移概率相对较小的节点后,逻辑测试将变得十分困难.并且硬件木马电路对整个电路的功耗和延时的影响较小,通过时序和功耗检测的方法也收效甚微.近年来,硬件木马的检测技术得到了明显的发展.硬件木马的检测方法主要分为以下三种:基于失效性分析、逻辑测试和旁路信号分析[1].

基于失效性分析是最早用于硬件木马的检测方法,它主要依赖于高精度设备,诸如光学显微镜、电子显微镜等进行扫描分析[2].通过高精度设备扫描和重构原始电路,将反向设计和原始电路设计进行比对来判断电路中是否被插入硬件木马[2-4].这种测试方法对于小规模集成电路有一定的实用性.但是随着大规模集成电路的发展,芯片的集成度越来越高,晶体管尺寸已经达到了纳米级,这种检测方法已经不能满足检测要求.

基于旁路信号的检测方法是目前一种有效的测量方法[5-12],通过测量和分析原始电路的信息,诸如延时[7-9]和功耗[5-6, 10, 12]等;得到原始电路的功耗或延时的特性曲线,也被称之为“IC指纹”[1].再通过同样的方法得到待测芯片的特性曲线,然后与之前的特性曲线相比较,去判断待测电路中是否存在硬件木马[2].此种测量方法易受到外界环境和工艺差别的影响,当硬件木马的影响较小而环境和工艺噪声较大时,硬件木马很难被检测出来[1].

基于逻辑测试的检测方法通过向电路输入端输入激励信号,尽可能的激活电路中的硬件木马,通过比对电路的响应和正确的输出结果来判断电路中是否存在硬件木马[13-17].逻辑测试不受工艺噪声和环境的影响,能有效检测一些结构较小的木马[1].但是如果硬件木马的输入端连接到电路中转移概率很小的节点,这样以来硬件木马的活性大大降低,穷举测试就会变得十分耗时.

针对逻辑测试方法中硬件木马难以激活的问题,可通过插入二选一数据选择器(MUX)来提高电路整体节点的转移概率,从而提高硬件木马的激活概率的方法[18].本文在此基础上提出新的插入选择算法,同时通过设置最大延时比例来保证电路的最大延时在一定范围之内,避免因插入点的增加而引起关键路径延时过大的问题.

1 提出方法

当MUX的选择信号为‘0’时,电路工作在正常模式下;当选择信号为‘1’时,电路工作在测试模式,该模式下可直接在原电路内部节点输入测试信号,提高节点的转移概率,从而提高硬件木马的激活与检测概率.随着插入节点的增多,电路的功耗、面积、延时等参数会有所增加.通过优化算法,使得MUX的插入数量减小.同时设置最大延时比例来控制电路关键路径的延时.

1.1 分析插入MUX对转移概率的提高

节点的转移概率是指节点的跳变概率.转移概率越高的节点在测试中跳变的次数就越高,所以提高整个电路节点的转移概率能有效的提高硬件木马激活和被检测的概率.基础逻辑门的转移概率计算方法见表 1.

表 1 逻辑门转移概率计算规则 Table 1 Calculation rule of transition probability of logic gate

表 1tpout为该逻辑门输出端节点的转移概率;sxini为逻辑门第i个输入端信号为x的概率,x取‘0’或‘1’;sxout为逻辑门输出端节点信号为x的概率,x取‘0’或‘1’.

通过n输入与门分析插入MUX对逻辑门转移概率的提高作用,其他类型的逻辑门可通过类似过程分析.如图 1所示,NET i为候选节点,它的转移概率小于转移概率阈值Tth. NET j为逻辑门的第j个输入端.由数学知识可知,当且仅当一个节点信号为‘0’和为‘1’的概率相等,即s1 = s0 =0.5时该节点的转移概率取最大值0.25. NET i的转移概率小于Tth的原因是由于s1s0的差值过大引起的.假设该与门的第k个输入端信号为‘0’和‘1’的概率为s0ks1k,则该逻辑门输出端节点在插入MUX前的信号为‘1’的概率为

$ s_{1}^{i}=\prod\limits_{k=1}^{n}{s_{1}^{k}}. $
图 1 被插入MUX的逻辑门 Figure 1 A logic gate inserted MUX

假定该逻辑门第j个输入端为‘1’的信号概率最小,则在该输入端插入二选一数据选择器.插入之后该逻辑门输出端节点信号为‘1’的概率为

$ s_{1}^{{{i}'}}=s_{1}^{{\mathit{{j}'}}}\prod\limits_{k\ne \mathit{j}}^{n}{s_{1}^{k}}. $

对于一个逻辑门而言,转移概率小于Tth可分为以下两种情况:

1) s1is0i.这表明与门的所有输入端信号为‘1’的概率全部大于0.5,即s1k>0.5,也表明s1js1j.这样,s1i的值比原来减小,s0i的值比原来大,候选节点的转移概率得以增加.

2) s1is0i.这表明存在某个输入节点,它得信号为‘1’的概率小于0.5.即s1j<0.5.则s1js1j.这样,s1i的值比原来增大,s0i的值比原减小,候选节点的转移概率得以增加.

分析可知,在输入端插入MUX可提高与门的转移概率.其他类型的逻辑门也可通过类似的方法进行分析讨论.

1.2 插入点选择算法

具体插入算法见图 2.流程所需要的输入为电路网表、人为设定的Tth、最大延时系数R以及提供电路物理特性的库文件.计算每个节点的逻辑深度Ld和扇出锥的节点数量Ncone,通过给所有输入端赋逻辑值为“1”的概率为0.5的输入向量,可得到各个节点信号概率s,通过计算得到每个节点的转移概率tp.插入之前计算原始电路关键路径延时记为Cdelay.所有tpTth并且可被插入的节点记为N1N1中节点数记为N,如果N=0,说明电路中没有tpTth或可被插入的节点,结束操作.每个N1的输入节点中拥有一个s最小的节点,选择方法见表 2,记为n0,所有的N1中节点的n0构成N2.将N2中的所有节点按照逻辑深度(到输入端)从小到大排序,相同逻辑深度按照扇出锥的节点数量排序,记为N3.依次将N3中的节点作为插入点进行插入操作,每次插入之后计算电路关键路径延时记为Tdelay.判断Tdelay是否满足要求?若满足,此次成功插入并更新电路重新计算电路的sLdNconetp,并再次进行插入点的选择直到结束;若不满足,删除最近一次插入的MUX后更新电路,继续执行插入操作.若此次N3中的所有节点均不满足时序要求,结束操作.

图 2 选择算法 Figure 2 Proposed selection algorithm
表 2 候选节点最小概率的输入节点选择方法 Table 2 Input node selection method for minimum signal probability of candidate node
2 实验结果分析

本实验以ISCAS’89基准电路作为实验对象,使用STM65纳米标准单元库计算电路信息.采用C语言搭建实验平台进行电路仿真.在仿真测试过程中,主要输入端都赋予信号为‘1’的概率为0.5的信号,来计算电路的整体信息.

2.1 转移概率提高

在此实验当中,以S9234和S5378电路作为基准电路进行测试.比较在插入前后电路所有节点的转移概率的变化.通过图 3456可看出,在插入MUX之前电路中有大量转移概率小于转移概率阈值0.05的节点,其中还有不少tp<10-4的节点.通过本文提出的方法,将转移概率阈值设置为0.05.在插入MUX之后,整体的转移概率提高,S5378电路中tp<0.05的节点数为9个,S9234电路中这一数字为84个,并且都没有tp<0.01的节点.整体看来通过插入MUX之后,转移概率的提高十分明显.

图 3 S5378电路插入MUX前电路转移概率 Figure 3 Transition probability of S5378 circuit before inserting MUX
图 4 S5378电路插入MUX后电路转移概率 Figure 4 Transition probability of S9234 circuit after inserting MUX
图 5 S9234电路插入MUX前电路转移概率 Figure 5 Transition probability of S5378 circuit before inserting MUX
图 6 S9234电路插入MUX后电路转移概率 Figure 6 Transition probability of S5378 circuit after inserting MUX
2.2 面积、功耗和延时的增加

通过插入MUX来提高整体电路的转移概率,随着插入数量的不断增加,势必会引起功耗、面积和延时增加.特别是关键路延时的增加会给整个电路带来严重的影响.通过设置最大延时比例,可将关键路径延时控制在可接受范围之内.

表 3中为S5378电路的仿真结果,当Tth分别为0.05、0.1,最大延时比例为1.03、1.1时,最大延时分别增加1.66%、9.16%.面积分别增加7.83%、15.44%.功耗分别增加12.47%、19.63%.

表 3 S5378电路插入MUX后带来的影响 Table 3 The impact of inserting MUX into S5378 circuit

表 4中为S9234电路的仿真结果,当Tth分别为0.05、0.1,最大延时比例为1.03、1.1时,最大延时分别增加2.1%、13.3%.面积分别增加5%、9.29%.功耗分别增加17.94%、24.69%.

表 4 S9234插入MUX后带来的影响 Table 4 The impact of inserting MUX into S9234 circuit
2.3 木马电路的激活

图 7所示,该硬件木马由触发器和负载两部分构成.与门和非门构成触发器部分,异或门构成负载部分. TJ1、TJ2、TJ3、TJ4和TJ5作为触发器的5个输入节点可被插入到目标电路的任意节点,当目标电路节点达到一定的逻辑值,木马电路的触发部分将被触发,电路的功能将被改变.而当木马电路没有被触发时,电路的功能将不被改变.

图 7 一种5输入的硬件木马实例 Figure 7 An example of hardware Trojan with 5 inputs

通过表 5可知,如果硬件木马的输入端连接在S5378电路中转移概率相对较小的节点,那么硬件木马的激活将变得十分困难.如图 7所示的一个5输入组合逻辑的硬件木马,其输入端分别连接到S5378电路的n219gat、n89gat、n110gat、n22gat和n200gat节点上,在插入MUX之前,硬件木马的激活概率为2.247×10-13,要用逻辑测试的方法将其检测出来是一件十分困难的事.转移概率阈值Tth设置为0.05后由图 4可知,绝大多数的节点的转移概率都大于了0.05.通过表 5可看出当Tth= 0.05时,插入MUX之后木马的激活概率增加到2.216×10-03,在这样的激活概率下可有效的检测出硬件木马.适当地将转移概率阈值Tth提高为0.1,硬件木马的激活概率增加到8.574×10-03.

表 5 S5378电路硬件木马激活信息 Table 5 Information of hardware Trojan activation in S5378 circuit
表 6 S9234电路硬件木马激活信息 Table 6 Information of hardware Trojan activation in S9234 circuit

在S9234中插入图 7所示的硬件木马,在插入MUX之前,硬件木马的激活概率为4.490×10-09,当转移概率阈值分别设置为0.05和0.1之后,硬件木马的激活概率分别增加到了7.069×10-04和3.410×10-03.硬件木马激活概率的提高十分明显.

2.4 最大延时比例系数对结果的影响

表 7中以S5378电路为例,如果转移概率阈值设置较大,如Tth=0.15,电路中tpTth的节点数量将会增加,此时随着MUX的不断插入,电路的关键路径延时会不断增加.如表 7所示,当Tth= 0.15而文献[18]中不对关键路径延时加以限制的话,关键路径延时将会增加41.68%,这将会严重影响电路性能.可根据电路性能要求设置一定的最大延时比例系数,当最大延时比例系数设置为1.1时延时,关键路径延时增加为9.87%,由于插入MUX数量的减少,插入完成后tpTth的节点有所增加.当最大延时比例为1.2和1.3时,关键路径延时增量分别为19.00%和29.29%,插入完成之后tpTth的节点分别比不设置最大延时比例时减小了38个和1个.

表 7 最大延时比例系数对插入结果的影响 Table 7 Influence of maximum delay proportional coefficient on insertion
3 结论

在本文中,提出一种通过在转移概率较低节点的输入端插入二选一数据选择器的方法实现对电路节点转移概率的提高,从而实现加速硬件木马检测.通过对扇出锥和电路逻辑拓扑结构分析选择对整个电路影响最大的候选节点,通过分析候选节点的逻辑门类型和输入信号概率选择最佳的插入点,从而减少MUX的插入数量,实现对插入算法的优化.同时引入最大延时比例系数用以控制电路关键路径延时,使电路关键路径延时控制在可接受的范围内.通过实验分析,电路的转移概率得到整体提升,可有效防止硬件木马的插入.被插入在电路中硬件木马的激活概率得到明显提高,可有效实现对硬件木马的检测.同时,关键路径延时也得到有效控制.

参考文献
[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