基于向量優(yōu)化的硬件木馬檢測技術(shù)研究

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

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

0 引言

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

硬件木馬檢測領(lǐng)域主要集中在基于反向剖析的檢測方法、基于旁路信號分析的檢測方法、基于邏輯測試的檢測方法等。Potkonjac等人提出了采用基于線性規(guī)劃和奇異值分解的門級特征公式來檢測木馬[1]，并對延遲和靜態(tài)功耗進(jìn)行測量，通過約束方程分析進(jìn)行木馬檢測。Nasr. A等人提出了一種高效的面向梯度的逆向工程硬件木馬檢測方法[2]，提出了物理檢測三步實(shí)現(xiàn)自動化的底層電路版圖識別方法。Chakraborty R S等人提出了MERO硬件木馬向量優(yōu)化檢測方法[3]，它是一種基于內(nèi)部節(jié)點(diǎn)稀有邏輯條件多重激勵的測試模式生成技術(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è)計過程中插入二選一數(shù)據(jù)選擇器，從而提高電路節(jié)點(diǎn)翻轉(zhuǎn)概率的方法。將電路功耗作為旁路信號，利用旁路信號分析方法進(jìn)行硬件木馬檢測[9]。駱揚(yáng)等人提出了一種具有可操作性的檢測物理型硬件木馬的方法[10]。馮秋麗等人提出了一種基于節(jié)點(diǎn)活性的硬件木馬檢測方法，以AES為目標(biāo)電路并植入硬件木馬，進(jìn)行仿真及FPGA實(shí)驗(yàn)[11]。劉志強(qiáng)等人提出了一種深度學(xué)習(xí)的非電信號硬件木馬檢測算法[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)險。非侵入式邏輯測試是基于自動測試向量生成技術(shù)來生成大量的測試向量，并對其進(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)行對測試向量進(jìn)行優(yōu)化，減小測試向量容量。

基于稀有節(jié)點(diǎn)的硬件木馬檢測方法如圖 1所示。該方法包括了三個部分，稀有節(jié)點(diǎn)查找、向量優(yōu)化以及木馬檢測。稀有節(jié)點(diǎn)查找時，如果選擇較小的閾值θ（θ≦0.25），選擇到的節(jié)點(diǎn)數(shù)量太少，會遺漏一些木馬植入節(jié)點(diǎn)，如果選擇較大的閾值θ，選擇到的節(jié)點(diǎn)數(shù)量太多，效果不好。為了能讓設(shè)置的閾值θ效果較好，閾值θ設(shè)置在能區(qū)分30%左右節(jié)點(diǎn)較為合適。另外，需要剔除掉錯誤節(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)化算法

測試向量生成主要依靠自動測試向量生成技術(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個節(jié)點(diǎn)作為硬件木馬觸發(fā)邏輯的輸入節(jié)點(diǎn)時，并且激活邏輯全由與門組成，則硬件木馬激活概率為：

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

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

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

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

稀有節(jié)點(diǎn)數(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能夠讓每個稀有節(jié)點(diǎn)的激活次數(shù)至少達(dá)到Ns。

通過對優(yōu)化目標(biāo)的重新選擇，從而設(shè)計出基于稀有節(jié)點(diǎn)的測試向量優(yōu)化算法，如圖3所示。優(yōu)化算法需要輸入的信息包括稀有節(jié)點(diǎn)數(shù)目，稀有節(jié)點(diǎn)對應(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)計各條向量下有多少稀有節(jié)點(diǎn)被激活，以及向量集激活稀有節(jié)點(diǎn)的次數(shù)。將向量依據(jù)激活的節(jié)點(diǎn)個數(shù)從少到多排序。選擇T條激活稀有節(jié)點(diǎn)個數(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)個數(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è)計與植入

為了能在硬件木馬被激活時快速的判斷出硬件木馬對電路邏輯功能的修改，硬件木馬的負(fù)載邏輯直接作用在電路的輸出節(jié)點(diǎn)，通過觀察輸出節(jié)點(diǎn)的邏輯來判斷木馬是否已被激活。本文選擇的待測電路是學(xué)術(shù)界公認(rèn)的 ISCAS’89基準(zhǔn)電路中的S1423電路。選擇以下四個節(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è)計的觸發(fā)邏輯為最壞情況，所有節(jié)點(diǎn)之間選擇與門的設(shè)計，如圖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時，G727的邏輯值不發(fā)生變化；當(dāng)ht為1時，G727輸出的邏輯值發(fā)生翻轉(zhuǎn)。硬件木馬選擇在S1423電路的RTL階段插入。

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

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

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

（1）Ns確定

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

（2）閾值θ確定

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

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

由公式（2）可知，當(dāng) Ns至少為 473時，對隨機(jī)向量集T1的向量數(shù)量有一個下限值4 296，而優(yōu)化后的向量集向量數(shù)則不會有該限制，本文將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ī)向量做激勵時，木馬被激活的次數(shù)為14.5次，而實(shí)際仿真出的木馬激活次數(shù)大致與計算的激活次數(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相對隨機(jī)向量集T1，向量數(shù)減少為原來的1/10，仿真時間縮短為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)化算法效果較好。