傅子晗，吳新春，朱書霖，魏紅梅

(1. 西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院, 四川 成都 61 1756; 2. 寧波漢達(dá)信息科技有限公司, 浙江 寧波 315048)

0 引言

由于集成電路芯片的設(shè)計(jì)與制造過程非常復(fù)雜，每一個(gè)步驟都不是完全安全的，硬件木馬可能被植入，能夠監(jiān)控或改變原始電路的功能，嚴(yán)重影響了集成電路芯片的安全。我國集成電路行業(yè)起步較晚，大多數(shù)集成電路需要進(jìn)口，而不能百分百保證芯片沒有硬件木馬，因此，有必要對(duì)硬件木馬檢測進(jìn)行研究。

硬件木馬檢測領(lǐng)域主要集中在基于反向剖析的檢測方法、基于旁路信號(hào)分析的檢測方法、基于邏輯測試的檢測方法等。Potkonjac等人提出了采用基于線性規(guī)劃和奇異值分解的門級(jí)特征公式來檢測木馬[1]，并對(duì)延遲和靜態(tài)功耗進(jìn)行測量，通過約束方程分析進(jìn)行木馬檢測。Nasr. A等人提出了一種高效的面向梯度的逆向工程硬件木馬檢測方法[2]，提出了物理檢測三步實(shí)現(xiàn)自動(dòng)化的底層電路版圖識(shí)別方法。Chakraborty R S等人提出了MERO硬件木馬向量優(yōu)化檢測方法[3]，它是一種基于內(nèi)部節(jié)點(diǎn)稀有邏輯條件多重激勵(lì)的測試模式生成技術(shù)。Voyiatzis等人提出了基于組合測試的硬件木馬檢測方法[4-5]，其重點(diǎn)放在觸發(fā)硬件木馬的效率上。Hong Zhao等人提出了一種基于信息熵聚類的硬件木馬檢測方法，采用啟發(fā)式測試模式生成方法，利用互信息來增加硬件木馬邏輯的轉(zhuǎn)換。在電路基準(zhǔn)上的實(shí)驗(yàn)驗(yàn)證了硬件木馬檢測的有效性[6]。Chen Don g等人提出了一種結(jié)合主成分分析（PCA）和局部離群因子（LOF）算法的無監(jiān)督硬件木馬檢測方法PL-HTD[7]。

國內(nèi)在硬件木馬領(lǐng)域的研究起步就比較晚，直到2010年，與硬件木馬有關(guān)的論文才發(fā)表[8]。徐力等人提出一種在電路設(shè)計(jì)過程中插入二選一數(shù)據(jù)選擇器，從而提高電路節(jié)點(diǎn)翻轉(zhuǎn)概率的方法。將電路功耗作為旁路信號(hào)，利用旁路信號(hào)分析方法進(jìn)行硬件木馬檢測[9]。駱揚(yáng)等人提出了一種具有可操作性的檢測物理型硬件木馬的方法[10]。馮秋麗等人提出了一種基于節(jié)點(diǎn)活性的硬件木馬檢測方法，以AES為目標(biāo)電路并植入硬件木馬，進(jìn)行仿真及FPGA實(shí)驗(yàn)[11]。劉志強(qiáng)等人提出了一種深度學(xué)習(xí)的非電信號(hào)硬件木馬檢測算法[12]。李鑫等人提出了一種基于電路結(jié)構(gòu)分析的集成模型，將復(fù)雜繁瑣的電路圖轉(zhuǎn)化為向量數(shù)據(jù)格式，通過極限梯度提升樹和長短期記憶神經(jīng)網(wǎng)絡(luò)的集成模型來檢測硬件木馬[13]。

1 基于稀有節(jié)點(diǎn)的硬件木馬檢測方法

基于邏輯測試檢測方法是一種重要的硬件木馬檢測方法，其核心思想就是激活硬件木馬。由于芯片規(guī)模不斷增大，其輸入輸出端口數(shù)也不斷增多，增加了邏輯測試的難度。為了解決此問題，可采用侵入式或非侵入式邏輯測試方法。侵入式邏輯測試是在原始電路加入額外電路方便測試，更容易控制內(nèi)部觸發(fā)器，使硬件木馬被激活的概率增加，減少硬件木馬被植入的風(fēng)險(xiǎn)。非侵入式邏輯測試是基于自動(dòng)測試向量生成技術(shù)來生成大量的測試向量，并對(duì)其進(jìn)行優(yōu)化，然后選擇優(yōu)化后的向量集來測試電路。而稀有節(jié)點(diǎn)是電路中翻轉(zhuǎn)概率低于閾值θ的節(jié)點(diǎn)，不同的電路需要選擇不同的閾值。基于稀有節(jié)點(diǎn)的檢測方法的目的就是通過提前分析電路信息，找出電路中的稀有節(jié)點(diǎn)，以更高的激活稀有節(jié)點(diǎn)轉(zhuǎn)換概率為目標(biāo)進(jìn)行對(duì)測試向量進(jìn)行優(yōu)化，減小測試向量容量。

基于稀有節(jié)點(diǎn)的硬件木馬檢測方法如圖 1所示。該方法包括了三個(gè)部分，稀有節(jié)點(diǎn)查找、向量優(yōu)化以及木馬檢測。稀有節(jié)點(diǎn)查找時(shí)，如果選擇較小的閾值θ（θ≦0.25），選擇到的節(jié)點(diǎn)數(shù)量太少，會(huì)遺漏一些木馬植入節(jié)點(diǎn)，如果選擇較大的閾值θ，選擇到的節(jié)點(diǎn)數(shù)量太多，效果不好。為了能讓設(shè)置的閾值θ效果較好，閾值θ設(shè)置在能區(qū)分30%左右節(jié)點(diǎn)較為合適。另外，需要剔除掉錯(cuò)誤節(jié)點(diǎn)，即翻轉(zhuǎn)概率為0的節(jié)點(diǎn)，如GND和VDD。木馬檢測采用邏輯測試激活硬件木馬，從而判斷電路中是否存在硬件木馬。向量優(yōu)化將在下節(jié)詳細(xì)介紹。

圖1 基于稀有節(jié)點(diǎn)的硬件木馬檢測方法Fig. 1 hardware Trojan horse detection method based on rare nodes

2 向量優(yōu)化算法

測試向量生成主要依靠自動(dòng)測試向量生成技術(shù)，采用優(yōu)化算法將隨機(jī)產(chǎn)生的測試向量集 T1轉(zhuǎn)換成效率更高的測試向量集T2，如圖1所示。測試向量直接作用是將稀有節(jié)點(diǎn)邏輯值改變，向量優(yōu)化的目標(biāo)是將硬件木馬激活。

記稀有節(jié)點(diǎn) ni被激活的概率為 p0/1(ni)，p0/1(ni)代表ni節(jié)點(diǎn)為0或者1的概率，其中

例如 p0(n1)=0.25，p1(n1)=0.75，則 p0/1(n1)=0.25。把向量集T2中的向量條數(shù)記為T，采用向量集T2，稀有節(jié)點(diǎn)ni被激活的次數(shù)Ni定義為：

如圖 2所示，稀有節(jié)點(diǎn) n0的激活概率為 p0（n0）,稀有節(jié)點(diǎn) n1的激活概率為 p0（n1），稀有節(jié)點(diǎn)n2的激活概率為p1（n2），稀有節(jié)點(diǎn)n3的激活概率為 p1（n3）。在 np為邏輯 1的情況下，負(fù)載邏輯被激活。則np為1的概率即為硬件木馬被激活的概率，將木馬激活概率P記為：

圖2 硬件木馬激活邏輯Fig. 2 hardware Trojan activation logic

由公式（3）推導(dǎo)，在由n個(gè)節(jié)點(diǎn)作為硬件木馬觸發(fā)邏輯的輸入節(jié)點(diǎn)時(shí)，并且激活邏輯全由與門組成，則硬件木馬激活概率為：

由n個(gè)節(jié)點(diǎn)作為硬件木馬觸發(fā)邏輯的輸入節(jié)點(diǎn)，節(jié)點(diǎn)之間的激活邏輯全由或門組成時(shí)，硬件木馬的激活概率為：

從邏輯門的分析可以得出，當(dāng)激活邏輯全為與門時(shí)，硬件木馬的激活概率最?。划?dāng)激活邏輯全由或門時(shí)，硬件木馬的激活概率最大，即：

硬件木馬的激活次數(shù)S為：

引入變量 ns，表示在所有的稀有節(jié)點(diǎn)中激活次數(shù)最少的稀有節(jié)點(diǎn)，即ns稀有節(jié)點(diǎn)的激活概率最小

稀有節(jié)點(diǎn)數(shù)目確定時(shí)，p0/1(ni)也為確定值，Ni與向量集 T2中的向量數(shù)T成正比，Ns也與T成正比，由公式（2）和（7）可推導(dǎo)出 S和 Ns的關(guān)系，

如果硬件木馬被激活，S大于等于1即可，則：

通過式（10），優(yōu)化算法有了新的優(yōu)化目標(biāo)，從隨機(jī)向量集T1出發(fā)，算法需要將每條向量進(jìn)行修改，保證最后的向量集T2能夠讓每個(gè)稀有節(jié)點(diǎn)的激活次數(shù)至少達(dá)到Ns。

通過對(duì)優(yōu)化目標(biāo)的重新選擇，從而設(shè)計(jì)出基于稀有節(jié)點(diǎn)的測試向量優(yōu)化算法，如圖3所示。優(yōu)化算法需要輸入的信息包括稀有節(jié)點(diǎn)數(shù)目，稀有節(jié)點(diǎn)對(duì)應(yīng)的01概率，隨機(jī)向量集T1，并且需要優(yōu)化的目標(biāo)即稀有節(jié)點(diǎn)的最少激活次數(shù)Ns，以及優(yōu)化后向量集的向量數(shù)目 T，最重要的是需要知道待測電路的邏輯結(jié)構(gòu)。有了這些輸入信息后，首先將優(yōu)化向量集T2清零，各稀有節(jié)點(diǎn)已激活次數(shù)清零，然后從隨機(jī)向量集T1中讀取每條向量，將每條向量施加于待測電路，統(tǒng)計(jì)各條向量下有多少稀有節(jié)點(diǎn)被激活，以及向量集激活稀有節(jié)點(diǎn)的次數(shù)。將向量依據(jù)激活的節(jié)點(diǎn)個(gè)數(shù)從少到多排序。選擇T條激活稀有節(jié)點(diǎn)個(gè)數(shù)最多的向量，作為需要優(yōu)化的向量。然后選擇激活稀有節(jié)點(diǎn)最少的向量開始修改，修改向量的第一位。修改后的向量再次施加于待測電路，判斷該條向量激活的稀有節(jié)點(diǎn)數(shù)是否增加，如沒有增加意味著稀有節(jié)點(diǎn)的激活次數(shù)不達(dá)標(biāo)，拒絕此次修改，如果該條向量激活的稀有節(jié)點(diǎn)數(shù)增加，再判斷各稀有節(jié)點(diǎn)的激活次數(shù)是否達(dá)到最少激活次數(shù)Ns，如果達(dá)到，則優(yōu)化過程完成。如沒達(dá)到，接受該位修改，繼續(xù)修改下一位，直到改完該條向量。修改完一條向量之后，重新將向量依據(jù)激活的節(jié)點(diǎn)個(gè)數(shù)從少到多排序，再從激活稀有節(jié)點(diǎn)最少的向量開始修改，直到滿足最少激活次數(shù)Ns的目標(biāo)。經(jīng)過優(yōu)化算法能夠得出最終優(yōu)化的向量集T2。

圖3 稀有節(jié)點(diǎn)向量優(yōu)化算法流程圖Fig. 3 flow chart of rare node vector optimization algorithm

3 仿真與分析

3.1 硬件木馬設(shè)計(jì)與植入

為了能在硬件木馬被激活時(shí)快速的判斷出硬件木馬對(duì)電路邏輯功能的修改，硬件木馬的負(fù)載邏輯直接作用在電路的輸出節(jié)點(diǎn)，通過觀察輸出節(jié)點(diǎn)的邏輯來判斷木馬是否已被激活。本文選擇的待測電路是學(xué)術(shù)界公認(rèn)的 ISCAS’89基準(zhǔn)電路中的S1423電路。選擇以下四個(gè)節(jié)點(diǎn)作為觸發(fā)的稀有節(jié)點(diǎn)：G395、G169、G203、G419，其節(jié)點(diǎn)為1的概率和翻轉(zhuǎn)概率如表1所示。

表1 木馬輸入節(jié)點(diǎn)翻轉(zhuǎn)概率情況Tab.1 turnover probability of Trojan horse input node

設(shè)計(jì)的觸發(fā)邏輯為最壞情況，所有節(jié)點(diǎn)之間選擇與門的設(shè)計(jì)，如圖4所示。

圖4 木馬觸發(fā)邏輯Fig. 4 Trojan horse trigger logic

選擇負(fù)載影響的節(jié)點(diǎn) G727，其轉(zhuǎn)移概率為0.1923496304115702，節(jié)點(diǎn)為1的概率為0.25989-50862884521，節(jié)點(diǎn)為 0的概率為 0.7401049137-115479。負(fù)載邏輯如圖5所示，當(dāng)ht為0時(shí)，G727的邏輯值不發(fā)生變化；當(dāng)ht為1時(shí)，G727輸出的邏輯值發(fā)生翻轉(zhuǎn)。硬件木馬選擇在S1423電路的RTL階段插入。

圖5 木馬負(fù)載邏輯Fig. 5 Trojan horse load logic

3.2 優(yōu)化算法參數(shù)確定

為了驗(yàn)證優(yōu)化算法是否有效，可以根據(jù)硬件木馬的情況對(duì)優(yōu)化算法的參數(shù)進(jìn)行確定。

（1）Ns確定

由公式(10)，Ns可得出 Ns的值至少為 473，優(yōu)化向量至少能激活一次木馬。

（2）閾值θ確定

由于選擇的硬件木馬翻轉(zhuǎn)概率在0.12以下，為了減少稀有節(jié)點(diǎn)的數(shù)量，縮短優(yōu)化時(shí)間，對(duì)于特定電路，稀有節(jié)點(diǎn)的翻轉(zhuǎn)概率閾值θ設(shè)置為0.12。通過對(duì)稀有節(jié)點(diǎn)翻轉(zhuǎn)概率的統(tǒng)計(jì)，翻轉(zhuǎn)概率小于0.12的節(jié)點(diǎn)數(shù)為95，占總數(shù)749的12.68%。

（3）優(yōu)化后向量數(shù)T確定

由公式（2）可知，當(dāng) Ns至少為 473時(shí)，對(duì)隨機(jī)向量集T1的向量數(shù)量有一個(gè)下限值4 296，而優(yōu)化后的向量集向量數(shù)則不會(huì)有該限制，本文將T值確定為5 000。

3.3 實(shí)驗(yàn)結(jié)果分析

從表 2實(shí)驗(yàn)結(jié)果可以看出，隨機(jī)向量集 T1單純只是隨機(jī)的0/1序列，共有50 000條向量，向量的內(nèi)存有781KB，但是木馬的激活次數(shù)只有16次。由公式（7）可知，當(dāng)50 000條隨機(jī)向量做激勵(lì)時(shí)，木馬被激活的次數(shù)為14.5次，而實(shí)際仿真出的木馬激活次數(shù)大致與計(jì)算的激活次數(shù)相仿。優(yōu)化向量集T2由隨機(jī)向量集T1經(jīng)優(yōu)化算法精簡而來，如圖6所示，左邊為優(yōu)化前的向量集T1，右邊為優(yōu)化后的向量集。選擇Ns為434，θ=0.12，T=5 000的輸入?yún)?shù)，最終的向量的內(nèi)存為 78.1KB，為T1的1/10，而T2的最終得到的木馬激活次數(shù)為521次。

表2 實(shí)驗(yàn)結(jié)果Tab.2 exp erimental results

圖6 向量集T1與向量集T2Fig. 6 Vector set T1 and Vector set T2

從實(shí)驗(yàn)結(jié)果來看，優(yōu)化后的向量集T2相對(duì)隨機(jī)向量集T1，向量數(shù)減少為原來的1/10，仿真時(shí)間縮短為1/10，而激活次數(shù)提高了32.56倍。

4 結(jié)論

本文提出了基于稀有節(jié)點(diǎn)的向量優(yōu)化算法，達(dá)到采用較少的測試向量能夠激活硬件木馬的目的。完成了向量優(yōu)化算法的仿真以及向量的測試。仿真表明，能夠?qū)㈦S機(jī)向量進(jìn)行優(yōu)化，使得激活次數(shù)提高了 32.56倍，向量數(shù)量縮短為 1/10。優(yōu)化后的向量檢測木馬效率更高，基于稀有節(jié)點(diǎn)向量優(yōu)化算法效果較好。