基于向量優化的硬件木馬檢測技術研究

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

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

0 引言

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

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

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

1 基于稀有節點的硬件木馬檢測方法

基于邏輯測試檢測方法是一種重要的硬件木馬檢測方法，其核心思想就是激活硬件木馬。由于芯片規模不斷增大，其輸入輸出端口數也不斷增多，增加了邏輯測試的難度。為了解決此問題，可采用侵入式或非侵入式邏輯測試方法。侵入式邏輯測試是在原始電路加入額外電路方便測試，更容易控制內部觸發器，使硬件木馬被激活的概率增加，減少硬件木馬被植入的風險。非侵入式邏輯測試是基于自動測試向量生成技術來生成大量的測試向量，并對其進行優化，然后選擇優化后的向量集來測試電路。而稀有節點是電路中翻轉概率低于閾值θ的節點，不同的電路需要選擇不同的閾值?；谙∮泄濣c的檢測方法的目的就是通過提前分析電路信息，找出電路中的稀有節點，以更高的激活稀有節點轉換概率為目標進行對測試向量進行優化，減小測試向量容量。

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

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

2 向量優化算法

測試向量生成主要依靠自動測試向量生成技術，采用優化算法將隨機產生的測試向量集 T1轉換成效率更高的測試向量集T2，如圖1所示。測試向量直接作用是將稀有節點邏輯值改變，向量優化的目標是將硬件木馬激活。

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

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

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

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

由公式（3）推導，在由n個節點作為硬件木馬觸發邏輯的輸入節點時，并且激活邏輯全由與門組成，則硬件木馬激活概率為：

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

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

硬件木馬的激活次數S為：

引入變量 ns，表示在所有的稀有節點中激活次數最少的稀有節點，即ns稀有節點的激活概率最小

稀有節點數目確定時，p0/1(ni)也為確定值，Ni與向量集 T2中的向量數T成正比，Ns也與T成正比，由公式（2）和（7）可推導出 S和 Ns的關系，

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

通過式（10），優化算法有了新的優化目標，從隨機向量集T1出發，算法需要將每條向量進行修改，保證最后的向量集T2能夠讓每個稀有節點的激活次數至少達到Ns。

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

圖3 稀有節點向量優化算法流程圖Fig. 3 flow chart of rare node vector optimization algorithm

3 仿真與分析

3.1 硬件木馬設計與植入

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

表1 木馬輸入節點翻轉概率情況Tab.1 turnover probability of Trojan horse input node

設計的觸發邏輯為最壞情況，所有節點之間選擇與門的設計，如圖4所示。

圖4 木馬觸發邏輯Fig. 4 Trojan horse trigger logic

選擇負載影響的節點 G727，其轉移概率為0.1923496304115702，節點為1的概率為0.25989-50862884521，節點為 0的概率為 0.7401049137-115479。負載邏輯如圖5所示，當ht為0時，G727的邏輯值不發生變化；當ht為1時，G727輸出的邏輯值發生翻轉。硬件木馬選擇在S1423電路的RTL階段插入。

圖5 木馬負載邏輯Fig. 5 Trojan horse load logic

3.2 優化算法參數確定

為了驗證優化算法是否有效，可以根據硬件木馬的情況對優化算法的參數進行確定。

（1）Ns確定

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

（2）閾值θ確定

由于選擇的硬件木馬翻轉概率在0.12以下，為了減少稀有節點的數量，縮短優化時間，對于特定電路，稀有節點的翻轉概率閾值θ設置為0.12。通過對稀有節點翻轉概率的統計，翻轉概率小于0.12的節點數為95，占總數749的12.68%。

（3）優化后向量數T確定

由公式（2）可知，當 Ns至少為 473時，對隨機向量集T1的向量數量有一個下限值4 296，而優化后的向量集向量數則不會有該限制，本文將T值確定為5 000。

3.3 實驗結果分析

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

表2 實驗結果Tab.2 exp erimental results

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

從實驗結果來看，優化后的向量集T2相對隨機向量集T1，向量數減少為原來的1/10，仿真時間縮短為1/10，而激活次數提高了32.56倍。

4 結論

本文提出了基于稀有節點的向量優化算法，達到采用較少的測試向量能夠激活硬件木馬的目的。完成了向量優化算法的仿真以及向量的測試。仿真表明，能夠將隨機向量進行優化，使得激活次數提高了 32.56倍，向量數量縮短為 1/10。優化后的向量檢測木馬效率更高，基于稀有節點向量優化算法效果較好。