可调节跳变概率硬件木马检测方法①

卢新元 许 超 陈华军 章隆兵** 王 玥*

(*计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京100190)

(**中国科学院计算技术研究所 北京100190)

(***中国科学院大学 北京100049)

(****龙芯中科技术有限公司 北京100190)

(*****黑龙江省公安厅 黑龙江150008)

0 引言

随着芯片设计和制造的全球化,芯片供应链上的各个阶段由不同的工厂或机构分工完成,在实现芯片产业高速发展的同时,也为攻击者植入硬件木马电路[1]提供了机会,芯片正面临着日趋严重的安全威胁。硬件木马隐藏在原始电路中,在特定条件下触发并造成信息泄露或停止服务等严重问题,同时很难被传统的测试方法检测,因此如何有效地防范和检测硬件木马,成为近年来芯片安全领域研究的重点。根据硬件木马种类和电路规模的不同,研究人员提出了多种硬件木马检测方法[2-3],其中非破坏性检测方法可分为侧信道分析技术和逻辑测试技术。侧信道分析技术[4-6]通过分析木马电路被激活或部分激活后导致的功耗、时序、电磁等侧信道信息异常来检测待测电路中是否存在硬件木马,适合大规模电路,但木马检测的准度容易受工艺偏差和测量噪声等因素的影响。逻辑测试技术[7-11]利用可测试性技术对电路施加信号激励,通过对比输出结果与期望值来判断电路中是否被植入木马,有效地避免了工艺偏差和测量噪声等因素的影响。逻辑测试技术是目前最直接有效的木马检测方法,但通常需要生成大量的测试向量来激活硬件木马,只适合小规模电路。

针对逻辑测试技术中硬件木马难以激活的问题,文献[12-16]提出了基于跳变概率提高的加速硬件木马检测方法,通过在电路中添加加速木马检测结构,提高了稀有节点到达稀有值状态的概率,增加了木马的激活概率,减少了木马激活时间。文献[12]通过在电路稀有节点处插入与或门和虚拟扫描触发器(dummy scan flflip-flflop,DSFF)结构,有效地缩短了木马激活时间,但该方法存在较大的面积、延迟及功耗开销。文献[13]用二路选择器(2-to-1 multiplexer,MUX)代替与或门,并优化插入选择算法,减少了插入点个数,但该结构依然存在一定程度的面积开销,且算法的时间复杂度较高,不适用于较大规模电路。文献[14]同样通过插入二路选择器提高稀有节点的跳变概率,选择将电路中部分节点的值替换为常值0 或1,但该方法缺乏插入点选择过程的优化,只是通过降低阈值来满足预设定的面积开销。文献[15]提出了权值随机向量的方法,有效地提高了稀有节点的跳变概率,但权值随机向量生成和选择过程进一步增加了面积和测试时间开销。文献[16]提出了基于最大布尔可满足性加速木马检测的方法,该方法能够最大化稀有节点的跳变概率,但无法检测到非稀有节点作为触发节点之一的木马。文献[13,14]中加速木马检测结构的概率替换方式较为单一,可以一定程度上提高稀有节点的跳变概率,但针对复杂的电路拓扑结构,无法最大化稀有节点的跳变概率,并且存在较大的面积开销。

针对以上方法存在的问题,本文提出一种可调节跳变概率的加速硬件木马检测方法,通过在芯片设计阶段插入特殊的二路选择器来提高稀有节点的跳变概率,加速硬件木马检测。该方法根据电路的拓扑结构分析稀有节点的扇入扇出,采用权值替换策略动态选择最优的插入点顺序,最大化电路中稀有节点的跳变概率,降低木马激活时间,且面积和时间开销可忽略不计。此外,该方法适用于较大规模电路。

1 背景介绍

1.1 硬件木马原理

硬件木马电路由触发模块和负载模块组成,其中触发模块负责激活木马电路,负载模块则是在木马激活后负责攻击的电路模块。触发模块分为数字触发和模拟触发,本文主要讨论和研究数字触发的硬件木马电路问题。攻击者通常会选取电路中的稀有值状态作为木马触发模块的条件,以文献[12]中展示的电路结构为例,电路输入端口的激励值默认完全随机,即输入端口值为0 或1的概率都为0.5,电路中各个节点状态值的概率通过概率分析计算后如图1 所示。

图1 电路中各节点状态值的概率

图中节点T值为1的概率为1/256,满足稀有值的条件,因此攻击者通常会选取该节点T作为木马触发模块的输入,当节点T满足稀有值状态1 时,木马被激活。文献[12]将节点值为0的概率P0 与值为1的概率P1的乘积定义为该节点的跳变概率TP,并将电路中跳变概率小于阈值的节点定义为稀有节点。节点的跳变概率越低表明该节点从非稀有值状态跳变为稀有值状态所需的时钟周期数越长,由该节点作为输入触发木马被激活所需的时间越长,因此提高稀有节点的跳变概率可以有效地降低木马电路激活所需时间,加速硬件木马检测。

1.2 经典的加速木马检测结构

旨在提高跳变概率的加速硬件木马检测方法是在稀有节点处插入特殊的电路结构,将电路中稀有节点的跳变概率提高到阈值以上,通过缩短稀有节点到达稀有值状态的时钟周期数来降低硬件木马触发节点激活所需时间。文献[13]提出的加速木马检测结构如图2 所示。

图2 文献[13]中的加速结构

图中目标节点i的跳变概率小于阈值,满足稀有节点条件,根据插入算法选择在目标节点i扇入门的输入节点j处插入加速木马检测结构。该结构由1 个2-to-1 MUX 和1 个DSFF 组成,MUX的输入端分别连接输入节点j以及扫描触发器的输出端Q,MUX的输出端同目标门相连,MUX的选择信号由使能信号TE控制。TE为0 时,电路处在功能模式下,选择节点j作为MUX 输出,电路的原有逻辑保持不变。当TE切换为1 后,电路进入测试模式,此时MUX 输出结果同扫描触发器DSFF的值保持一致,节点j′值为0 和1的概率(Pj′0,Pj′1)被替换为(0.5,0.5)。该结构可以保证在功能模式下,电路的功能逻辑不受影响,且在测试模式下,替换节点的状态值由扫描触发器进行控制,从而提高目标节点的跳变概率。

1.3 权值替换分析

文献[13]选择将所有需替换节点的概率统一替换为(0.5,0.5),但这并不是适合所有情况的最优权值替换选择,以图3 中3 种不同的情况为例进行说明。

图3 不同情况下的权值替换分析

图3(a)中三输入与门输出节点d的跳变概率可计算为0.0384,假定跳变概率阈值设为0.1,则需要提高输出节点d的跳变概率,使其满足阈值要求。根据文献[13]中的方法,选取该与门所有输入中值为1的概率最低的节点a进行加速木马检测结构插入,将节点a状态值的概率替换为(0.5,0.5),输出节点d的跳变概率被提高为0.09,但依然小于阈值,则需要进一步在节点b处插入加速木马检测结构,这显然增加了插入点的数量。由跳变概率计算公式可知,若使得输出节点d值为1的概率大于0.113,则可以保证d的跳变概率满足阈值,即输入节点a在替换后值为1的概率应大于0.563。例如将节点a的概率(Pa0,Pa1) 替换为(0.8,0.2),则节点d的跳变概率为0.1344,大于阈值。

图3(b)中两输入门的输出节点c的跳变概率计算为0.09,阈值设定为0.1,同样需要在输入节点a处插入加速木马检测结构。在这种情况下将概率替换为(0.5,0.5)或(0.8,0.2)都可以满足输出节点c的跳变概率大于阈值,但替换为(0.8,0.2)是更优的选择,因为跳变概率越大,木马触发节点被激活所需的时钟周期数越短。

但并非所有的情况下将输入节点的概率值取反都是最优的权值替换选择,例如图3(c)中的结构。同样地,将节点a的概率替换为(0.5,0.5)或(0.8,0.2),节点c的跳变概率都能大于阈值,但同时会影响节点d的跳变概率,计算后发现需要用(0.5,0.5)替换才可以满足节点d的跳变概率大于阈值,为减少插入点数量,降低加速木马检测结构的面积开销,这种情况下将输入节点a的概率修改为(0.5,0.5)是最优的权值替换选择。

2 可调节跳变概率的加速木马检测方法

本文提出了一种可调节跳变概率的加速木马检测结构,并设计了相应的权值选择和插入点选择算法,根据电路的拓扑结构选择合适的插入结构,并动态规划插入点顺序。

2.1 可调节跳变概率的结构实现

可调节跳变概率的加速木马检测结构如图4(a)和4(b)所示,当替换节点net的概率满足Pnet1＞＞Pnet0 时,选择插入图4(a)中结构;当替换节点net的概率满足Pnet0＞＞Pnet1 时,则选择图4(b)中结构进行插入。图4(a)中结构由一个扫描触发器和一个2-to-1 MUX 组成,触发器的Q连接MUX的一个输入,测试模式控制信号TE则和MUX的另外一个输入端相连。MUX的选择信号由电路中替换节点net控制,MUX的输出则作为替换后的节点net′,图4(b)中结构是在图4(a)中结构的基础上额外添加了2 个反相器。根据图4(a)和4(b)中的加速木马检测结构,替换后节点net′的概率计算公式如表1所示。

图4 本文提出的加速木马检测结构

以替换节点net值的概率Pnet1＞＞Pnet0的情况为例,替换后节点net′的概率计算公式如表1 中式(1.1)和(1.2)所示。当电路处在功能模式下,使能信号TE为0,则可简化为式(1.3)和(1.4),将扫描触发器的值置为1并保持不变,此时替换后节点net′的值同节点net的值完全一致,该结构可以保证电路的功能逻辑不受影响。因此,在电路进入功能模式之前,工程师需要通过复位信号DOTESTn将新增扫描触发器的值全部置1,来保证功能模式下电路的功能逻辑不变。当电路进入测试模式时,使能信号TE为1,替换后节点net′的概率计算公式可简化为式(1.5)和(1.6),若扫描触发器Q端值的概率(PFF1,PFF0)满足(0.5,0.5),则替换后节点net′的概率(Pnet′0,Pnet′1)趋近于(0.5,0.5);若扫描触发器Q端值的概率(PFF1,PFF0)满足(0,1),即保持为常值0,则替换后节点net′值的概率满足(Pnet′1,Pnet′0)=(Pnet0,Pnet1)。因此,该加速木马检测结构既可以将替换节点net值的概率修改为(0.5,0.5),也可以修改为节点net值的概率取反后的值,需要根据电路的拓扑结构进行判断,选择最优的修改方式,在保证提高稀有节点跳变概率的前提下,最大化减少插入点的数量,降低面积开销。

表1 替换后节点net′的概率计算公式

当选择用替换节点概率值取反的方式进行修改时,可以将该加速木马检测结构进一步优化,优化后的结构如图4(c)所示。同图4(a)和4(b)中结构相比,图4(c)中选择用反相器代替扫描触发器,反相器会将TE值取反并同2-to-1 MUX 输入端相连。该优化后的结构既可以保证测试模式下将替换节点处的概率值修改为取反后的值,又可以保证功能模式下电路的功能逻辑不变,并且一定程度上减少了需要添加扫描触发器的数量,进一步降低了面积开销。

根据图4(a)和4(b)中结构可知,当扫描触发器Q端值的概率(PFF1,PFF0)满足(0.5,0.5)时,节点net′概率并非为(0.5,0.5),实际概率为通过式(1.5)、(1.6)、(2.5)和(2.6)计算后所得。为了便于描述,本文定义:

(1) 采用图4(a)和4(b)中结构修改后得到的概率值称为平均权值,该替换方式称为平均权值替换。此时扫描触发器Q端值的概率(PFF1,PFF0)需满足(0.5,0.5)。

(2) 采用图4(c)中结构修改后得到的概率值称为反向权值,该替换方式称为反向权值替换。

2.2 权值选择算法

为了保证在替换节点处能够选择最优的加速检测木马结构进行替换,需要对电路中稀有节点的扇出情况进行分析,为此本文提出如算法1 所示的权值选择算法。本文定义:节点的扇出路径上同该节点相连的门定义为该节点的扇出门;节点的扇入路径上同该节点相连的门定义为该节点的扇入门。节点所有扇出门的输出端口定义为该节点的扇出节点;节点扇入门的所有输入端口定义为该节点的扇入节点。

算法1的输入为稀有节点NETrare,插完扫描链[17]的门级网表以及预先设定的跳变概率阈值TPth,输出则为最优的替换权值WSP。首先需要获取该稀有节点的扇入节点集合FIN、扇出节点集合FOUT以及扇入门类型,可以通过电子设计自动化(electronic design automatic,EDA)综合工具从门级网表中提取。然后根据扇入门类型从扇入集合FIN中选取一个扇入节点作为最优的替换节点。选取替换节点的原则是:当扇入门为与门或与非门时,选择扇入节点中值为1的概率最小的且未被替换过的节点作为替换节点;当扇入门为或门或或非门时,则选择扇入节点中值为0的概率最小的且未被替换过的节点作为替换节点。该选取原则的目的是最大化稀有节点的跳变概率。选定替换节点后,用平均权值和反向权值这两种权值进行替换,重新计算并得到稀有节点的跳变概率满足阈值且小于阈值时,选择平均权值作为更优的替换权值;反之,则选择反向权值作为替换权值。若都满足阈值,则需要进一步计算该稀有节点的所有扇出节点的跳变概率,并统计扇出节点中跳变概率满足阈值的总个数,选择使得总数更大的权值作为替换权值。若满足阈值的扇出节点的总数依然相同,则选择使得稀有节点跳变概率更大的权值,这是因为更大的跳变概率代表该节点被激活到稀有值状态所需时钟周期数更少。若替换完成后,该稀有节点的跳变概率依然小于阈值,则需要在它的扇入节点中,按照相同的原则继续选择最优的替换节点,直到该稀有节点的跳变概率大于阈值。

2.3 插入点选择算法

电路中节点的跳变概率由它扇入路径上的所有节点共同决定,因此为了最小化插入点个数,节点扇入路径上的所有稀有节点都应优先于该节点进行加速结构的插入,对于不存在扇入扇出关系的稀有节点,它们的插入顺序则不会相互影响。为了最小化跳变概率的计算次数,节点的跳变概率计算只需要在它扇入路径上的所有节点加速结构插入完成后计算,为此本文提出了如算法2 所示的插入点选择算法。本文将节点的全部扇入节点的个数定义为该节点的扇入度,显然电路中输入端口的扇入度均为0。

算法2的输入是插入扫描链后的门级网表以及预先设定的跳变概率阈值,输出为插入加速木马检测结构后的网表UpdateNetlist。首先从门级网表中提取电路中各个节点NET的扇入门类型集合GNET、扇入节点集合FINNET和扇出节点集合FOUTNET。通过统计每个节点对应的扇入节点集合中节点个数可以得到该节点的扇入度DNET,然后将扇入度为0的节点放入集合A中,剩余节点都放入集合B中。循环开始后,每次从集合A中取出一个节点,根据该节点扇入门类型计算其跳变概率,并判断是否大于阈值。若该节点为稀有节点,则根据算法1 选择替换节点并判断采用哪种权值进行替换,在替换节点处插入对应的加速木马检测结构,然后将该替换节点标记为已替换。将该节点i的所有扇出节点的扇入度减1,更新集合A和B,将扇入度为0的扇出节点从集合B移出,并放入集合A中,重复此循环,直到集合B为空,最终返回加速木马检测结构全部插入完成后的网表。

以图5 为例介绍完整的权值选择和插入点选择过程。图5(a)中所示为初始电路,设定电路输入端口值为0 和1的概率均为0.5,电路中各节点为1 和0的概率如图中所示,设定跳变概率阈值为0.14。为了更好地理解权值选择和插入点选择过程,将图5(a)中初始电路简化为图6(a)中所示的拓扑结构,带有箭头的线所示为稀有节点。根据插入点选择算法,首先将电路中所有扇入度为0的节点放入集合A中,即A={G0,G1,G2,G3,G4,G5},如图6(a)中虚线所示节点,剩余节点放入集合B中。依次从集合A中取出节点G5、G4、G3,并更新集合B中对应扇出节点的扇入度。当G3 从集合A中取出后,B中节点G7的扇入度变为0,此时更新集合A={G0,G1,G2,G7},如图6(b)所示。继续从A中取出节点G7,由扇入门类型计算可知,G7的跳变概率大于阈值。更新G8 和G9的扇入度,并将扇入度为0的G9放入集合A中,如图6(c)所示,随后取出G9 并计算其跳变概率,G9的跳变概率同样大于阈值。更新节点G11的扇入度,此时集合B中没有节点满足扇入度为0,集合A和B保持不变。继续从集合A中取出节点G2,更新节点G8 扇入度,随后将G8 放入集合A中,如图6(d)所示。接着取出G8,并计算可知其跳变概率小于阈值,根据权值选择算法选取值为1 概率更小的节点G7 为替换节点,计算两种权值替换下G8的跳变概率。计算可知,两种权值替换下G8的跳变概率都大于阈值,则需要进一步计算G8所有扇出节点的跳变概率,即G10 和G11。计算可知,当采用反向权值替换后,即G7的概率值修改为(0.75,0.25),此时G10的跳变概率小于阈值,而采用平均权值替换后,G10 和G11的跳变概率均大于阈值,因此选择平均权值,并在G7 处插入如图5(b)左下角中虚线框内的加速木马检测结构,此时G11变为如图6(e)中所示的虚线。随后依次从集合A中取出节点G11、G2、G1、G6、G10、G12,每取出一个节点后,判断其跳变概率是否大于阈值,并将更新后集合B中扇入度为0的节点放入集合A中,分别如图6(e)、6(f)、6(g)、6(h)所示。计算可知G12的跳变概率小于阈值,同样根据权值选择算法将G11作为替换节点,带入两种替换权值计算后可知,G12的跳变概率均满足阈值,但反向权值使得G12的跳变概率更大,因此选择反向权值为替换权值,并插入对应的加速结构。需要特别强调的是,由于节点G9 先于G8 从集合A中取出,为了不影响G9 及其扇出路径上节点的跳变概率,加速结构只会添加在门AND1 和AND2 之间。最终当集合B为空时,插入点选择过程结束,此时电路中全部节点的跳变概率满足阈值要求,插入加速结构后的电路如图5(b)所示。

图5 示例电路

图6 拓扑结构图

3 加速硬件木马检测流程

综上所示,本文提出的可调节跳变概率的加速硬件木马检测流程如图7 所示。

图7 加速硬件木马检测流程图

首先,分析和统计电路中各个节点的扇入扇出节点集合及扇出门类型。其次,根据扇入扇出结构和权值选择规则,查找稀有节点并判断需插入的加速木马检测结构类型,并根据插入点选择规则,动态规划稀有节点的优化顺序。最后,根据稀有节点及对应的加速结构类型,在替换节点处插入对应的加速木马检测结构直至满足程序设定的结束条件。加速木马检测结构插入完成后,需将新增的扫描触发器全部放到扫描链上,保证功能模式下电路逻辑不变,测试模式下实现加速木马检测。

4 实验结果及分析

为了评估本文所提可调节跳变概率的加速木马检测方法对降低木马激活时间及面积开销的效果,本实验选取ISCSA’89 基准电路作为评估对象,并使用DC 工具基于STM 65 nm 工艺进行综合、可测试性设计和加速木马检测结构插入,生成最终的网表。实验通过perl 语言搭建算法执行环境,并使用VCS 进行随机向量仿真验证。上述的电子EDA 工具都在Linux 环境下运行,服务器的CPU 为Intel Xeon Platinum 8176,主频为2.1 GHz,内存容量为64 GB。在仿真测试过程中,电路所有输入端口值为0 和1的概率均设定为0.5。

本文从跳变概率、木马激活周期数及面积开销3 个方面进行分析和评估,实验结果如下。

4.1 跳变概率

考虑到实验的适用性和完备性,本文分别在4种阈值条件下,选择ISCSA’89 基准电路中的5 个基准电路进行实验。同初始电路以及文献[13]中经典方法相比,稀有节点的平均跳变概率统计结果如表2 所示。

由表中结果可知,根据本文方法插入加速木马检测结构后,5 种基准电路中稀有节点的平均跳变概率均显著提高,且远大于阈值。当阈值设定为1.0E-1时,同初始电路相比,稀有节点的平均跳变概率提高了约4～6 倍;当阈值设定为1.0E-4 时,稀有节点的平均跳变概率则提高了约几百到几千倍。

表2的最后1 列是本文方法同文献[13]中方法在4 种阈值情况下的实验对比结果。从结果来看,5 种基准电路在采用本文方法后稀有节点的平均跳变概率都在文献[13]中方法的基础上有了明显提高。其中,在电路s5378 和s38417 上的优化效果最为明显,尤其是s38417 中稀有节点的平均跳变概率提高了约50%。

表2 稀有节点平均跳变概率统计

4.2 木马激活验证

为了直接验证本文方法能否有效地加速硬件木马检测,实验选择对初始电路s5378 和已插入加速木马检测结构的电路分别植入相同的硬件木马电路,选择10 000 条随机向量进行仿真,统计并比较木马激活次数。考虑到硬件木马规模的多样性,实验采用文献[13]中设计的2 种硬件木马电路,分别如图8(a)和8(b)所示。图中虚线框内是木马激活模块,当木马输入端口分别满足1101 和110 101 时,硬件木马电路被激活。实验设定跳变概率阈值为1.0E-1,并从电路s5378的稀有节点中随机选择节点作为2 种硬件木马的输入端口,并分别随机生成1000 组木马电路。随机向量仿真完成后,木马电路的平均激活次数统计如表3 所示。数据表明,对于未插入任何加速木马检测结构的初始电路,木马电路HT1 和HT2 几乎无法被激活。采用本文方法和文献[13]的方法后,两种木马电路都能被成功激活。相比于文献[13]方法,本文方法将木马平均激活次数分别提高至86.3 和10.8 次,这说明木马被激活所需的时间周期数更短,木马检测速度的提升效果明显。

表3 木马平均激活次数对比

图8 两种木马电路

4.3 时间及面积开销评估

4.3.1 时间开销分析

本文方法同经典加速木马检测方法相比,时间复杂度对比如表4 所示。其中n表示电路中节点的个数,w表示文献[15]中权值的数量,r和d分别表示文献[16]中稀有节点的个数和电路逻辑深度,g表示电路中门的个数。

表4 几种经典方法的时间复杂度对比

同文献[12,13,15]中方法相比,本文方法的时间复杂度更低,更适合较大规模电路。

4.3.2 面积开销分析

实验分别在3 种阈值条件下,对文献[13]中方法和本文方法的基准电路新增面积开销进行评估,结果如表5 所示。表中第3 列和第4 列分别对应的是文献[13]中方法和本文方法相比初始网表的面积增加比例。从实验结果可以看出,本文方法的新增面积开销占比约为0.7%～12.1%,面积开销很小,且面积开销占比随着阈值的减少而逐渐降低。设计者可以根据实际的面积开销要求设定适合的跳变概率阈值。表5 中最后1 列是本文方法同文献[13]中方法相比,新增面积开销降低的百分比。显然,3 种阈值条件下,5 种基准电路在采用本文方法后新增面积开销都在文献[13]方法的基础上有了明显降低。其中,在电路s5378 和s13207 上的优化效果最为明显,尤其是s5378 中新增面积开销平均优化了68.9%。

表5 新增面积开销统计

5 结论

硬件木马检测一直是业内研究的热点。本文在调研相关技术的基础上提出了可调节跳变概率的加速硬件木马检测方法。该方法从芯片的门级网表中准确提取出稀有节点的拓扑结构,分析其结构得到最优的权值替换策略,依据插入点选择规则动态规划稀有节点的修改优先级,提高稀有节点的跳变概率;并根据权值类型,优化插入的加速木马检测结构,降低硬件开销,最小化加速木马检测结构对芯片性能带来的影响,同时保证功能模式下原有电路逻辑不变。实验结果表明,采用本文所提的加速硬件木马检测方法后,电路中稀有节点的跳变概率明显提高,木马激活时间大幅降低。同经典加速木马检测方法相比,本方法在电路规模较大时效果更为明显,设计者可以根据实际需求,设定合适的跳变概率阈值,从而达到加速检测的同时降低面积开销的目的。