Fig. 1 The example of a FSM
图1 有穷状态机示例
崔晓通 邹敏辉 吴剀劼
(信息物理社会可信服务计算教育部重点实验室(重庆大学) 重庆 400044)(重庆大学计算机学院 重庆 400044)(xiaotong.sd@gmail.com)
摘 要： 集成电路设计和制造的全球化趋势使得木马电路可以在集成电路设计制造的任何阶段被插入，这引发了对硬件安全的广泛关注.从防御者的角度出发，木马电路在宿主电路使用过程中绝大多数时间是静默无害的，但是一旦被激活就会造成如信息泄露、功能异常或系统崩溃等严重危害;从攻击者的角度出发，避免木马电路被“误触发”是其最重要的一个设计目标之一.普遍认为，电路中那些具有较低状态翻转概率的惰性节点最有可能成为木马电路的插入点.因此目前检测的主要手段之一是试图寻找到这些惰性点，以便有针对性地尝试以激活木马电路.然而，目前的方法仅专注于寻找被测电路在测试模式下的惰性点.提出了一种寻找被测电路在工作模式下的惰性点的方法.从攻击者的角度出发，两者的交集将是木马电路的最佳插入点——可以较好地避免其插入的木马电路在宿主电路的测试阶段以及试运行阶段被“误触发”.因此从防御者的角度出发，找到测试模式和工作模式下共有的惰性节点并对其进行检测，有助于有效提高检测效率.
关键词： 木马电路；工作模式；惰性节点；状态翻转概率；总状态
集成电路设计和制造的全球化使得集成电路的安全课题成为了重要的研究领域，这是因为，为了节约成本，集成电路在设计和制造过程中将部分任务分包给第三方制造商或者设计公司完成，这使得硬件木马电路的植入成为可能 [1-5] .
硬件木马电路可以在规范说明阶段、设计阶段、制造阶段和测试阶段在内的各个阶段被插入 [6] ；其通常由2部分组成：触发电路和负载电路.当触发电路在特定条件下被激活后，负载电路按照木马设计者的意愿发挥作用，如通过旁信道泄露信息，或直接改变宿主电路的输出，或为攻击者提供远程控制等 [7] .存在于关键性系统(如经济、军事、医疗等)中的木马电路毫无疑问将会带来重大安全隐患，因此木马电路的检测是一项十分重要的工作.
根据木马电路的性质，通常对其检测的方法有包括功耗、时间分析在内的旁道检测技术 [8] ，和通过有目的地产生测试向量以激活木马电路的检测技术 [9] ，也可能是两者的结合.
从攻击者(即木马电路设计者)的角度出发，“误触发”带来的后果是灾难性的，不仅没有实现其破坏目的，且将给其代表的利益集团带来经济声誉上的重大损失.木马电路的“误触发”指的是其设计的木马电路在非最佳场景下被激活并对宿主电路造成影响.由于这种影响通常大而明显，很容易被宿主电路的监测机制捕获，因此木马电路通常只有一次机会对宿主电路造成危害，这使得避免木马电路的误触发成为木马电路设计的一个重要内容.
不难预见的一个经常会导致木马电路误触发的情景是针对木马电路的测试模式.在测试模式下，测试者通过向被测电路提供特定的测试向量以试图激活被测电路中的木马电路.另外一个重要的误触发场景是电路的工作模式——在电路的试运行过程或是正常工作过程中由于电路的正常输入而误触发了木马电路.虽然木马电路的设计本意即是在工作状态中激活并对宿主电路造成影响，但是必须考虑到木马电路危害的一次性，在非最佳场景时被激活并不是木马电路设计的初衷.首先，几乎所有的关键任务一般多会有试运行阶段.试运行的设计毫无疑问将会尽量模拟真实工作的各种情况.在试运行阶段误触发木马电路依然会暴露攻击者的意图但并没有达到最佳攻击意图.其次，在电路的正常工作状态下，未到达攻击者最理想的工作场景(如特定的时间等)的情况下触发木马电路虽然会对系统造成一定的损害，但不一定是决定性的，因此也是误触发的一种.
为了避免误触发，木马电路的设计者通常会利用宿主电路中的惰性节点来构建其木马电路的触发电路.电路的惰性节点是那些拥有较低的状态翻转概率的电路节点.因此，寻找惰性节点也是目前检测木马电路的一个主要方法.然而目前的工作仅考虑了测试模式下的惰性节点，如文献[10].而在工作模式下的惰性节点却被忽略.根据上述原因，我们认为，那些在2种模式下翻转概率都比较低的惰性节点最有可能被利用来构建木马电路的触发电路.然而，如第1节所示，工作模式下电路节点状态翻转概率的计算完全不同于测试模式下的计算方法，因此准确地计算工作模式下节点的翻转概率进而确定惰性节点是非常必要的.本文的主要工作是通过准确计算工作模式下电路节点的翻转概率，结合测试模式的检测结果，确定真正的电路惰性节点.
根据引言的描述我们知道，可以对电路节点的状态翻转概率进行计算进而可以判断可能被攻击者选中的木马电路植入点.通常状态翻转概率低的电路节点具有更大的可能性成为植入点——将有效地降低木马电路的误触发概率.因此，准确地计算电路节点的状态翻转概率对于木马电路的检测具有重要意义.文献[10]研究了在测试模式下对电路节点的转移概率进行计算进而确定电路中的惰性节点——那些在测试过程中状态翻转概率明显较低的电路节点.在测试模式下，被测试电路中所有的寄存器通过扫描链组织，和测试电路的输入一起受测试者的直接控制.因而每个寄存器和每个输入的值均有同等概率为1或0，即50%为状态1，50%为状态0.不难看出，这样的方式不仅没有区分在工作模式时电路的常用和非常用输入，而且更严重的是没有区分被测试电路的非法状态和合法状态，以及状态之间的非法和合法跳转，因而测试模式下得到的惰性节点并不一定是工作模式下的惰性节点.下面通过示例来进一步说明这个问题.我们从一个有穷状态自动机(finite state machine, FSM)开始，如图1所示，其描述的是具有一个输入和一个输出的电路，当且仅当输入的字符串为10101时，输出为1，否则输出为0.
以这样一个有穷状态机为基础，接下来便是对状态的编码以及电路的设计与实现.从图1可知，该状态机除了初始状态 S 0 外还有 S 1 , S 2 , S 3 , S 4 共4种状态，考虑到设计和修改的简单性以及易于检测非法状态，我们采用“一位热码编码”(one-hot encoding)的方式对状态进行编码，并将 S 0 ， S 1 ， S 2 ， S 3 ， S 4 分别编码为0000,0001,0010,0100,1000，进而设计了带有4个寄存器的电路，如图2所示.
Fig. 1 The example of a FSM
图1 有穷状态机示例
Fig. 2 The example circuit according to the FSM
图2 根据有穷状态机设计的电路示例
按照文献[10]中的计算方法，如果节点 N 的状态翻转概率为 Pt ( N :0→1)= Pt ( N :1→0)，节点 N 为0或1的概率分别为 P ( N =0)和 P ( N =1)，那么 Pt ( N :0→1)= Pt ( N :1→0)= P ( N =0)× P ( N =1).在文献[10]中，如果节点 N 为电路的输入(primary input)，那 P ( N =0)= P ( N =1)=0.5.如果该节点为某个逻辑门的输出，那么根据逻辑门的种类，该节点为0或1的概率可以总结如下(假定该逻辑门的输入为 A 和 B )：
1) N 为反向器输出
P ( N =1)= P ( A =0)， P ( N =0)= P ( A =1)；
2) N 为与门输出
P ( N =1)= P ( A =1)× P ( B =1)， P ( N =0)=1- P ( N =1)；
3) N 为与非门输出
P ( N =0)= P ( A =1)× P ( B =1)， P ( N =1)=1- P ( N =0)；
4) N 为或门输出
P ( N =0)= P ( A =0)× P ( B =0)， P ( N =1)=1- P ( N =0)；
5) N 为或非门输出
P ( N =1)= P ( A =0)× P ( B =0)， P ( N =0)=1- P ( N =1).
根据这些来自文献[10]的计算法则，图3展示了图2中部分电路节点的状态概率.在图3中，节点 N 的状态概率以( P ( N =0)， P ( N =1))表示.节点的状态翻转概率因此可以简单计算出来.如， Pt ( D 4)=7 
8×1 8=7 64.图2示例电路中所有节点的状态翻转概率都可以通过这种方式计算得到，计算结果如表1第1行.
Fig. 3 The cone of the net D 4
图3 节点D 4 的结构
然而，文献[10]中的计算方法只适用于测试模式下电路节点状态翻转概率的计算.当电路在工作模式下，电路的状态以及状态跳转并非是随机的.因此，电路节点状态翻转概率的计算在工作模式下与在测试模式下是完全不同的.为了验证我们的想法，我们以成千上万比特的随机输入序列对电路的运行模式进行了模拟，统计了各节点的状态翻转概率并列于表1的第2行.
从表1中可以看出2个结论:1)2种模式下的同样节点的转移概率在大多数情况下有很大的区别，如 I 1 ， D 1 ， Z 等;2)电路节点间的相对活跃程度在2个模式下是不一致的.如在测试模式下 Pt ( D 2 )> Pt ( D 3 )，而在工作模式下 Pt ( D 2 )< Pt ( D 3 ).因此并非所有的测试模式下的惰性节点都是木马电路候选者，还要参考工作模式下电路节点的状态翻转概率，这也是本文的动机.
Table 1 Pt Comparison between Test Mode [10] and Function Mode Simulation
表1 工作模式下模拟结果和测试模式下节点状态翻转概率的比较
在本节我们提出了一种准确计算工作模式下电路节点状态翻转概率的方法，可以结合测试模式下各节点的状态翻转概率，更好地实现对木马电路插入点的预测.
2.1 节点状态翻转概率的计算
根据图1的有穷状态机，我们可以得到其状态转移表，如表2所示：
Table 2 State Transition Table of the Example Circuit
表2 示例电路的状态转移表
以图3中 D 4 节点为例，作为一个三输入与门的输出， D 4 从1转换为0的概率是所有的输入( X , I 1 , I 2 )在当前状态下都为1，且在下一个状态有至少一个输入变为0的概率.更进一步地，跟踪所有决定 D 4 的电路输入和寄存器{ G 1, G 3, X }， D 4 从1转换为0的概率相当于{ G 1, G 3, X }从{0,0,1}转换到{0,0,0}，{0,1,0}，{1,0,0}，{1,1,0}，{0,1,1}，{1,0,1}，{1,1,1}中的一种概率之和.其中 G 1和 G 3来自状态寄存器， X 是电路的输入.也就是说， D 4 从1转换到0的概率 Pt ( D 4 :1→0)为下面所有概率之和：
Pt ( D 4 :1→0)=
Pt ({ G 1, G 3, X }:001→000)+
Pt ({ G 1, G 3, X }:001→010)+
Pt ({ G 1, G 3, X }:001→011)+
Pt ({ G 1, G 3, X }:001→100)+
Pt ({ G 1, G 3, X }:001→101)+
Pt ({ G 1, G 3, X }:001→110)+
Pt ({ G 1, G 3, X }:001→111).
以 Pt ({ G 1, G 3, X }:001→000)为例， D 4 从1转换到0的条件发生于：
1) 在转换之前{ G 1, G 3}={0,0}， X =1；
2) 在转换之后{ G 1, G 3}={0,0}， X =0.
因此可以知道，计算节点的状态翻转概率需要电路的状态和输入的共同信息.因此，我们用state input表示一个电路的总状态 TS (total state)，那么 Pt ( TS : S 1 i 1 → S 2 i 2 )表示了电路在总状态 TS = S 1 i 1 和总状态 TS = S 2 i 2 之间的转移概率.根据电路的有穷状态机且假设随机的电路输入 X ，即 P ( X =0)= P ( X =1)=0.5，可以推出其总状态转移概率矩阵 M ，如图4所示：
Fig. 4 Total state transition matrix M of the example circuit
图4 示例的总状态转移概率矩阵M
显而易见，节点的状态翻转概率将和电路的总状态的转移概率相关.根据表2和图4，可以得到：
Pt ({ G 1, G 3, X }:001→000)=
Pt ( TS : S 0 1→ S 1 0)+ Pt ( TS : S 1 1→ S 1 0)+
Pt ( TS : S 3 1→ S 4 0)=
Pt ( TS = S 0 1)×0.5+ P ( TS = S 1 1)×0.5+
P ( TS = S 3 1)×0.5=( P ( TS = S 0 1)+
P ( TS = S 1 1)+ P ( TS = S 3 1))×0.5.
因此 Pt ({ G 1, G 3, X }:001→000)的概率依赖于 P ( TS = S 0 1)， P ( TS = S 1 1)和 P ( TS = S 3 1).下面介绍电路的总状态的概率计算方法.
2.2 电路中各个总状态概率的计算
在工作模式下，电路的状态由其有穷状态自动机决定.有穷状态自动机和输入序列将共同控制到达各个状态的概率，不断增加的输入最终将使各个状态趋于一个稳定状态 [11] ，即到达各个状态的概率将趋于一个稳定的值.因此我们用
V =( v 1= P ( TS = S 0 0), v 2= P ( TS = S 0 1)，
v 3= P ( TS = S 1 0), v 4= P ( TS = S 1 1)，
v 5= P ( TS = S 2 0), v 6= P ( TS = S 2 1)，
v 7= P ( TS = S 3 0), v 8= P ( TS = S 3 1)，
v 9= P ( TS = S 4 0), v 10= P ( TS = S 4 1))
来表示示例中稳定状态的概率向量，假设总状态总数为 S ，则：
(1)
根据稳定状态的特性有：
V × M = V .
(2)
根据式(1)(2)，可以求得 V =(0.125,0.125,0.187 5,0.187 5,0.093 75,0.093 75,0.062 5,0.062 5,0.031 25,0.031 25).
进而我们可以得到(2.1节中)：
Pt ({ G 1, G 3, X }:001→000)=
( P ( TS = S 0 1)+ P ( TS = S 1 1)+
P ( TS = S 3 1))×0.5=0.187 5；
Pt ({ G 1, G 3, X }:001→010)=0；
Pt ({ G 1, G 3, X }:001→011)=0；
Pt ({ G 1, G 3, X }:001→100)=0；
Pt ({ G 1, G 3, X }:001→101)=0；
Pt ({ G 1, G 3, X }:001→110)=0；
Pt ({ G 1, G 3, X }:001→111)=0.
将以上所有的概率加起来，我们得到 D 4 在工作模式下的状态转移概率 Pt ( D 4 :1→0)=0.187 5.用同样的方式，我们可以得到示例电路工作模式下所有节点的状态转移概率，将它们与电路工作模式下模拟得到的结果(表1第2行)相比，如表3所示：
Table 3 Pt Comparison between Simulation and our Method of the Example Circuit
表3 示例电路工作模式下计算所得和模拟所得节点状态翻转概率的比较
运用高斯消除法 [12] 根据式(1)(2)计算稳定状态向量时间复杂度为 O ( N 2 )，其中 N 为状态总数.然而对于大规模的电路，总的状态数目随着输入和状态的比特数呈指数增长，构造一个完整的状态转移概率矩阵 M 或者稳定状态向量 V 是不可行的.在我们的方法中，我们提出通过尽可能多的大量输入并记录所有状态及状态转移，运用统计的方法推断出 M 和 V .比如， M 中的某一个值可以通过统计所得的转移次数与总时钟节拍数的比率来求得，稳定状态下各个状态的概率也可以用类似的方法得到.没有监测到的状态转移以及其稳定状态的概率被设为0.由于我们求取 M 和 V 的初衷就是观察工作模式下状态转移的频繁程度，因此这种统计的方法有非常好的效果.
我们的算法目的是为了找到所有电路内部节点的状态翻转概率.如果某节点是寄存器，其状态翻转概率可以从总状态转移概率矩阵 M 来决定.因此这里我们将集中讨论那些非寄存器的内部节点，即那些由组合逻辑门直接输出的电路节点，如示例电路中 I 1 ， I 2 ， I 3 等节点.如果将电路的所有总状态的集合定义为 TSet ，对于节点 i ， TSet 可以分为2个子集 Set 1( i )和 Set 0( i )，它们分别表示可以使该节点的输出为1和0的总状态集合.它们之间有如下关系：
Set 1( i )∪ Set 0( i )= TSet ，
且:
Set 1( i )∩ Set 0( i )=∅，
Set 1( i )和 Set 0( i )可以由 i 驱动门的类型和驱动门各输入的 Set 0和 Set 1来决定.
算法1. 寻找 Set 1( i )和 Set 0( i ).
① 初始化所有的 Set 1 and Set 0为NULL；
② Find_Sets ( i ){
③ if i 是一个主输入then
④ return Set 1( i ) and Set 0( i ); *请看算法描述*
⑤ end if
⑥ for节点 i 的驱动门的每个输入 j
⑦ Find_ Sets ( j )；
⑧ end for
⑨ 计算 Set 1( i )和 Set 0( i )；
⑩ return Set 0( i )和 Set 1( i ).}
算法1以节点 i 以及其所有输入为输入，输出 Set 1( i )和 Set 0( i ).算法1行①初始化所有节点的 Set 1( i )和 Set 0( i )为空；行②～⑩调用函数 Find_Sets ( i )；行③～⑤，如果节点 i 是一个电路输入或寄存器，则它的 Set 1( Set 0)是除了其本身为1(0)其余输入和寄存器位为任意项；行⑥～⑧，对于节点 i 的每项输入 j ，递归调用 Find_Sets ( j )；行⑨当找到节点 i 的驱动门的所有输入状态集合之后， Set 1( i )和 Set 0( i )可以通过以下规则进行计算：
1) 如果 i 的驱动门是只有一个输入 j 的反相器，则：
Set 1( i )= Set 0( j );
Set 0( i )= Set 1( j )；
2) 如果 i 的驱动门是一个输入为 j k ( k >1)的与门，则：
Set 1( i )=∩ Set 1( j k );
Set 0( i )= TSet - Set 1( i )；
3) 如果 i 的驱动门是一个输入为 j k ( k >1)的与非门，则：
Set 0( i )=∩ Set 1( j k );
Set 1( i )= TSet - Set 0( i )；
4) 如果 i 的驱动门是一个输入为 j k ( k >1)的或门，则：
Set 0( i )=∩ Set 0( j k );
Set 1( i )= TSet - Set 0( i )；
5) 如果 i 是一个输入为 j k ( k >1)的或非门，则：
Set 1( i )=∩ Set 0( j k );
Set 0( i )= TSet - Set 1( i ).
最后行⑩返回得到 Set 0( i )和 Set 1( i ).
算法2. 计算 SP ( i ).
① Pt ( i )=0；
② for Set 1( i )中的每个总状态
③ for Set 0( i )中的每个总状态
④ 在矩阵 M 中找到对应的翻转概率 P ；
⑤ 在向量 V 中找到对应的 v ；
⑥ Pt ( i )+= P × v ；
⑦ end for
⑧ end for
算法2是计算节点 i 的状态翻转概率 SP ( i ).节点 i 的状态发生翻转的充要条件是电路从 Set 1( i )中的某个总状态转移到 Set 0( i )中的某个总状态，或者从 Set 0( i )中的某个总状态转移到 Set 1( i )中的某个总状态.因此，节点 i 的状态翻转概率的计算原理是计算从 Set 1( i )中的每个总状态转移到 Set 0( i )中的每个总状态的概率之和.首先,行①将节点 i 的翻转概率 Pt ( i )赋值为0；行②～⑧，对于 Set 1( i )中每个总状态到 Set 0( i )中的每个总状态的转移在总状态转移矩阵中找到对应的转移概率 P ，并和稳定状态概率 v 中对应的概率 P 相乘，累加到 Pt ( i ).
我们用 N net , N pri , N dff 分别代表一个电路的节点个数、主要输入个数和状态寄存器的个数.
算法1的时间复杂度：考虑最坏的情况，计算节点 i 需要递归遍历到所有节点，每个节点有 N 个输入，每个输入都和所有的主要输入和状态寄存器相关，则算法1的时间复杂度为 N net ×2 n ×( N pri+ N dff) .
算法2的时间复杂度：假设最坏的情况，节点 i 的 Set 1( i )和 Set 0( i )中各有2 N dff+ N pri 个总状态，则算法2的时间复杂度为2 2( N dff+ N pri) .
我们对7组基准测试程序作了实验，它们都来自于ISCAS89电路基准测试程序 [13] .对于每组基准测试程序，我们都用文献[10]中测试模式的计算方法、工作模式下我们的方法计算所有节点的状态翻转概率，并报告状态翻转概率小于5%的节点的交集，实验结果表4所示：
Table 4 Inactive Nets in both Test Mode and Function Mode
表4 工作模式和测试模式下的惰性节点 %
Continued (Table 4)
Continued (Table 4)
集成电路设计和制造的全球化趋势使得木马电路可以在集成电路设计制造的任何阶段被插入，这引发了对硬件安全的广泛关注.从防御者的角度出发，木马电路在宿主电路使用过程中绝大多数时间是静默无害的，但是一旦被激活就会造成如信息泄露、功能异常或系统崩溃等严重危害.从攻击者的角度出发，避免其插入的木马电路被“误触发”是其最重要的一个设计目标之一.普遍认为，电路中那些具有较低状态翻转概率的惰性节点最有可能成为木马电路的插入点.因此目前检测的主要手段之一是试图寻找到这些惰性点，以便有针对性地尝试以激活木马电路.然而，目前的方法仅专注于寻找被测电路在测试模式下的惰性点.本文提出了一种寻找被测电路在工作模式下的惰性点的方法.从攻击者的角度出发，两者的交集将是木马电路的最佳插入点——可以避免其插入的木马电路在宿主电路的测试阶段和试运行阶段被“误触发”;从防御者的角度出发，两者的交集将大大降低需要检测的电路节点，有助于提高检测效率.在文章的最后，我们报告了7组来自于ISCAS89的电路基准测试程序在测试模式和工作模式下具有状态翻转概率小于5%的节点的交集.
进一步工作为：算法1和算法2的时间复杂度并非是多项式时间内可以完成的，尤其在电路规模比较大的时候，其计算时间随寄存器以及电路输入的位数呈指数增长，只能解决小到中规模的电路(如仅有几十个输入和状态寄存器).并且在计算构造一个完整的状态转移概率矩阵 M 和稳定状态向量 V 时需要大量的随机输入，某些非惰性节点会被误判成惰性节点.我们观察到，在实际的电路中，只有一些状态寄存器对电路输入敏感(造成电路状态跳转)，很多状态寄存器对电路输入不敏感(不造成电路状态跳转).因此我们进一步的工作将致力于电路工作模式下节点翻转概率计算的启发式算法的研究，利用某些状态寄存器对电路输入不敏感这个重要的观察，以使得在基本保持计算精度的条件下极大地减少计算开销.
参考文献：
[1]Abramovici M, Bradley P. Integrated circuit security—New threats and solutions[C] 
Proc of the 5th Annual Workshop on Cyber Security and Information Intelligence Research: Cyber Security and Information Intelligence Challenges and Strategies. New York: ACM, 2009: 55：1-55：3
[2]Chakraborty R S, Narasimhan S, Bhunia S. Hardware Trojan—Threats and emerging solutions[C] Proc of High Level Design Validation and Test Workshop. Piscataway, NJ: IEEE, 2009: 166-171
[3]Jin Y, Kupp N, Makris Y. Experiences in hardware Trojan design and implementation[C] Proc of IEEE Int Workshop on Hardware-Oriented Security and Trust. Piscataway, NJ: IEEE, 2009: 50-57
[4]Cui Xiaotong, Ma Kun, Shi Liang, et al. High-level synthesis for run-time hardware Trojan detection and recovery[C] Proc of the 51st Annual Design Automation Conf. Piscataway, NJ: IEEE, 2014: 1-6
[5]Tehranipoor M, Koushanfar F. A survey of hardware Trojan taxonomy and Detection[J]. IEEE Design & Test Computers, 2010, 27(1): 10-25
[6]Karri R, Rajendran J, Tehranipoor M. Trustworthy hardware: Identifying and classifying hardware Trojans[J]. Computer, 2010, 43(10): 39-46
[7]Bhunia S, Abramovici M, Agrawal D, et al. Protection against hardware Trojan attacks: Towards a comprehensive solution[J]. IEEE Design & Test, 2013, 30(3): 6-17
[8]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] Proc of Design, Automation & Test in Europe Conf & Exhibition (DATE). Piscataway, NJ: IEEE, 2013: 1265-1270
[9]Fang Lei, Li Lei, Li Zhen. A practical test patterns generation technique for hardware Trojan detection[J]. Elektrotehniki Vestnik, 2013, 80(5): 266-270
[10]Salmani H, Tehranipoor M, Plusquellic J. A novel technique for improving hardware Trojan detection and reducing Trojan activation time[J]. IEEE Trans on Very Large Scale Integration Systems, 2012, 20(1): 112-125
[11]Wikipedia. Markov chain[EB OL]. [2015-09-27]. http: en.wikipedia.org wiki Markov_chain
[12]Wikipedia. Gaussian elimination[EB OL]. [2015-09-27]. http: en.wikipedia.org wiki Gaussian_elimination
[13]Wikipedia. ISCAS89 sequential benchmark circuits[EB OL]. [2015-09-27]. https: filebox.ece.vt.edu ～mhsiao iscas89.html
Cui Xiaotong, born in 1991. Received his BS degree in computer science and technology from Chongqing University, China, in 2013. PhD candidate in computer science and technology at the College of Computer Science, Chongqing University. His main research interests include real-time task scheduling and hardware security.
Zou Minhui, born in 1989. Received his BS degree in computer science and technology from Chongqing University, China, in 2013. PhD candidate in computer science and technology at the College of Computer Science, Chongqing University. His main research interests include security of cryptographic system and side-channel attacks.
Wu Kaijie, born in 1974. Received his BE degree from Xidian University, Xian, China, in 1996, his MS degree from the University of Science and Technology of China, Hefei, China, in 1999, and his PhD degree in electrical engineering from Polytechnic University (Now Polytechnic Institute of New York University), Brooklyn, New York, in 2004. He then joined University of Illinois, Chicago, USA as an assistant professor. Since 2013, he becomes a professor at the College of Computer Science, Chongqing University, China. Member of the IEEE and CCF. His main research interests inchlude the big area of trustworthy computing with special interest on dependable computing and hardware security.
Cui Xiaotong, Zou Minhui, and Wu Kaijie
( Key Laboratory of Dependable Service Computing in Cyber Physical Society ( Chongqing University ), Ministry of Education , Chongqing 400044)( College of Computer Science , Chongqing University , Chongqing 400044)
Abstract： The globalization trend of design and manufacture of IC raises serious concerns about hardware security since there is possibility that in each phase of design and manufacture hardware Trojan can be inserted. From the defender’s perspective, hardware Trojan in the host circuit may stay inactive for most of time but will result in disastrous consequences once activated, such as information leakage, false output, system crash, etc. As far as an attacker concerned, one of important design criteria is to prevent the Trojan circuit from being accidently activated. It is believed that inactive nets with lower switching probabilities in the circuit are more likely to be selected as the trigger signals of Trojan circuits. Hence finding these inactive nets is one of the existing countermeasures. However, current techniques only focus on finding inactive nets in test mode of the circuit. This paper proposes a method that can find inactive nets in function mode of the testing circuit. From an attacker’s point of view, the nets that are inactive in both test mode and function mode are the best candidates for Trojan triggers—it will result in the lowest probability of accidental activation of Trojan circuits in both modes. Hence for a defender, focusing on these nets will improve the efficiency of Trojan detection significantly.
Key words： hardware Trojan; function mode; inactive nets; switching probabilities of states; total states
收稿日期： 2015-10-27；
修回日期： 2016-03-22
基金项目： 国家自然科学基金项目(61472052)；国家“八六三”高技术研究发展计划基金项目(2015AA015304,2013AA013202) This work was supported by the National Natural Science Foundation of China (61472052) and the National High Technology Research and Development Program of China (863 Program)(2015AA015304, 2013AA013202).
中图法分类号： TP331.1