可調(diào)節(jié)跳變概率硬件木馬檢測(cè)方法①

盧新元 許 超 陳華軍 章隆兵** 王 玥*

(*計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院計(jì)算技術(shù)研究所) 北京100190)

(**中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京100190)

(***中國(guó)科學(xué)院大學(xué) 北京100049)

(****龍芯中科技術(shù)有限公司 北京100190)

(*****黑龍江省公安廳 黑龍江150008)

0 引言

隨著芯片設(shè)計(jì)和制造的全球化,芯片供應(yīng)鏈上的各個(gè)階段由不同的工廠或機(jī)構(gòu)分工完成,在實(shí)現(xiàn)芯片產(chǎn)業(yè)高速發(fā)展的同時(shí),也為攻擊者植入硬件木馬電路[1]提供了機(jī)會(huì),芯片正面臨著日趨嚴(yán)重的安全威脅。硬件木馬隱藏在原始電路中,在特定條件下觸發(fā)并造成信息泄露或停止服務(wù)等嚴(yán)重問題,同時(shí)很難被傳統(tǒng)的測(cè)試方法檢測(cè),因此如何有效地防范和檢測(cè)硬件木馬,成為近年來芯片安全領(lǐng)域研究的重點(diǎn)。根據(jù)硬件木馬種類和電路規(guī)模的不同,研究人員提出了多種硬件木馬檢測(cè)方法[2-3],其中非破壞性檢測(cè)方法可分為側(cè)信道分析技術(shù)和邏輯測(cè)試技術(shù)。側(cè)信道分析技術(shù)[4-6]通過分析木馬電路被激活或部分激活后導(dǎo)致的功耗、時(shí)序、電磁等側(cè)信道信息異常來檢測(cè)待測(cè)電路中是否存在硬件木馬,適合大規(guī)模電路,但木馬檢測(cè)的準(zhǔn)度容易受工藝偏差和測(cè)量噪聲等因素的影響。邏輯測(cè)試技術(shù)[7-11]利用可測(cè)試性技術(shù)對(duì)電路施加信號(hào)激勵(lì),通過對(duì)比輸出結(jié)果與期望值來判斷電路中是否被植入木馬,有效地避免了工藝偏差和測(cè)量噪聲等因素的影響。邏輯測(cè)試技術(shù)是目前最直接有效的木馬檢測(cè)方法,但通常需要生成大量的測(cè)試向量來激活硬件木馬,只適合小規(guī)模電路。

針對(duì)邏輯測(cè)試技術(shù)中硬件木馬難以激活的問題,文獻(xiàn)[12-16]提出了基于跳變概率提高的加速硬件木馬檢測(cè)方法,通過在電路中添加加速木馬檢測(cè)結(jié)構(gòu),提高了稀有節(jié)點(diǎn)到達(dá)稀有值狀態(tài)的概率,增加了木馬的激活概率,減少了木馬激活時(shí)間。文獻(xiàn)[12]通過在電路稀有節(jié)點(diǎn)處插入與或門和虛擬掃描觸發(fā)器(dummy scan flflip-flflop,DSFF)結(jié)構(gòu),有效地縮短了木馬激活時(shí)間,但該方法存在較大的面積、延遲及功耗開銷。文獻(xiàn)[13]用二路選擇器(2-to-1 multiplexer,MUX)代替與或門,并優(yōu)化插入選擇算法,減少了插入點(diǎn)個(gè)數(shù),但該結(jié)構(gòu)依然存在一定程度的面積開銷,且算法的時(shí)間復(fù)雜度較高,不適用于較大規(guī)模電路。文獻(xiàn)[14]同樣通過插入二路選擇器提高稀有節(jié)點(diǎn)的跳變概率,選擇將電路中部分節(jié)點(diǎn)的值替換為常值0 或1,但該方法缺乏插入點(diǎn)選擇過程的優(yōu)化,只是通過降低閾值來滿足預(yù)設(shè)定的面積開銷。文獻(xiàn)[15]提出了權(quán)值隨機(jī)向量的方法,有效地提高了稀有節(jié)點(diǎn)的跳變概率,但權(quán)值隨機(jī)向量生成和選擇過程進(jìn)一步增加了面積和測(cè)試時(shí)間開銷。文獻(xiàn)[16]提出了基于最大布爾可滿足性加速木馬檢測(cè)的方法,該方法能夠最大化稀有節(jié)點(diǎn)的跳變概率,但無法檢測(cè)到非稀有節(jié)點(diǎn)作為觸發(fā)節(jié)點(diǎn)之一的木馬。文獻(xiàn)[13,14]中加速木馬檢測(cè)結(jié)構(gòu)的概率替換方式較為單一,可以一定程度上提高稀有節(jié)點(diǎn)的跳變概率,但針對(duì)復(fù)雜的電路拓?fù)浣Y(jié)構(gòu),無法最大化稀有節(jié)點(diǎn)的跳變概率,并且存在較大的面積開銷。

針對(duì)以上方法存在的問題,本文提出一種可調(diào)節(jié)跳變概率的加速硬件木馬檢測(cè)方法,通過在芯片設(shè)計(jì)階段插入特殊的二路選擇器來提高稀有節(jié)點(diǎn)的跳變概率,加速硬件木馬檢測(cè)。該方法根據(jù)電路的拓?fù)浣Y(jié)構(gòu)分析稀有節(jié)點(diǎn)的扇入扇出,采用權(quán)值替換策略動(dòng)態(tài)選擇最優(yōu)的插入點(diǎn)順序,最大化電路中稀有節(jié)點(diǎn)的跳變概率,降低木馬激活時(shí)間,且面積和時(shí)間開銷可忽略不計(jì)。此外,該方法適用于較大規(guī)模電路。

1 背景介紹

1.1 硬件木馬原理

硬件木馬電路由觸發(fā)模塊和負(fù)載模塊組成,其中觸發(fā)模塊負(fù)責(zé)激活木馬電路,負(fù)載模塊則是在木馬激活后負(fù)責(zé)攻擊的電路模塊。觸發(fā)模塊分為數(shù)字觸發(fā)和模擬觸發(fā),本文主要討論和研究數(shù)字觸發(fā)的硬件木馬電路問題。攻擊者通常會(huì)選取電路中的稀有值狀態(tài)作為木馬觸發(fā)模塊的條件,以文獻(xiàn)[12]中展示的電路結(jié)構(gòu)為例,電路輸入端口的激勵(lì)值默認(rèn)完全隨機(jī),即輸入端口值為0 或1的概率都為0.5,電路中各個(gè)節(jié)點(diǎn)狀態(tài)值的概率通過概率分析計(jì)算后如圖1 所示。

圖1 電路中各節(jié)點(diǎn)狀態(tài)值的概率

圖中節(jié)點(diǎn)T值為1的概率為1/256,滿足稀有值的條件,因此攻擊者通常會(huì)選取該節(jié)點(diǎn)T作為木馬觸發(fā)模塊的輸入,當(dāng)節(jié)點(diǎn)T滿足稀有值狀態(tài)1 時(shí),木馬被激活。文獻(xiàn)[12]將節(jié)點(diǎn)值為0的概率P0 與值為1的概率P1的乘積定義為該節(jié)點(diǎn)的跳變概率TP,并將電路中跳變概率小于閾值的節(jié)點(diǎn)定義為稀有節(jié)點(diǎn)。節(jié)點(diǎn)的跳變概率越低表明該節(jié)點(diǎn)從非稀有值狀態(tài)跳變?yōu)橄∮兄禒顟B(tài)所需的時(shí)鐘周期數(shù)越長(zhǎng),由該節(jié)點(diǎn)作為輸入觸發(fā)木馬被激活所需的時(shí)間越長(zhǎng),因此提高稀有節(jié)點(diǎn)的跳變概率可以有效地降低木馬電路激活所需時(shí)間,加速硬件木馬檢測(cè)。

1.2 經(jīng)典的加速木馬檢測(cè)結(jié)構(gòu)

旨在提高跳變概率的加速硬件木馬檢測(cè)方法是在稀有節(jié)點(diǎn)處插入特殊的電路結(jié)構(gòu),將電路中稀有節(jié)點(diǎn)的跳變概率提高到閾值以上,通過縮短稀有節(jié)點(diǎn)到達(dá)稀有值狀態(tài)的時(shí)鐘周期數(shù)來降低硬件木馬觸發(fā)節(jié)點(diǎn)激活所需時(shí)間。文獻(xiàn)[13]提出的加速木馬檢測(cè)結(jié)構(gòu)如圖2 所示。

圖2 文獻(xiàn)[13]中的加速結(jié)構(gòu)

圖中目標(biāo)節(jié)點(diǎn)i的跳變概率小于閾值,滿足稀有節(jié)點(diǎn)條件,根據(jù)插入算法選擇在目標(biāo)節(jié)點(diǎn)i扇入門的輸入節(jié)點(diǎn)j處插入加速木馬檢測(cè)結(jié)構(gòu)。該結(jié)構(gòu)由1 個(gè)2-to-1 MUX 和1 個(gè)DSFF 組成,MUX的輸入端分別連接輸入節(jié)點(diǎn)j以及掃描觸發(fā)器的輸出端Q,MUX的輸出端同目標(biāo)門相連,MUX的選擇信號(hào)由使能信號(hào)TE控制。TE為0 時(shí),電路處在功能模式下,選擇節(jié)點(diǎn)j作為MUX 輸出,電路的原有邏輯保持不變。當(dāng)TE切換為1 后,電路進(jìn)入測(cè)試模式,此時(shí)MUX 輸出結(jié)果同掃描觸發(fā)器DSFF的值保持一致,節(jié)點(diǎn)j′值為0 和1的概率(Pj′0,Pj′1)被替換為(0.5,0.5)。該結(jié)構(gòu)可以保證在功能模式下,電路的功能邏輯不受影響,且在測(cè)試模式下,替換節(jié)點(diǎn)的狀態(tài)值由掃描觸發(fā)器進(jìn)行控制,從而提高目標(biāo)節(jié)點(diǎn)的跳變概率。

1.3 權(quán)值替換分析

文獻(xiàn)[13]選擇將所有需替換節(jié)點(diǎn)的概率統(tǒng)一替換為(0.5,0.5),但這并不是適合所有情況的最優(yōu)權(quán)值替換選擇,以圖3 中3 種不同的情況為例進(jìn)行說明。

圖3 不同情況下的權(quán)值替換分析

圖3(a)中三輸入與門輸出節(jié)點(diǎn)d的跳變概率可計(jì)算為0.0384,假定跳變概率閾值設(shè)為0.1,則需要提高輸出節(jié)點(diǎn)d的跳變概率,使其滿足閾值要求。根據(jù)文獻(xiàn)[13]中的方法,選取該與門所有輸入中值為1的概率最低的節(jié)點(diǎn)a進(jìn)行加速木馬檢測(cè)結(jié)構(gòu)插入,將節(jié)點(diǎn)a狀態(tài)值的概率替換為(0.5,0.5),輸出節(jié)點(diǎn)d的跳變概率被提高為0.09,但依然小于閾值,則需要進(jìn)一步在節(jié)點(diǎn)b處插入加速木馬檢測(cè)結(jié)構(gòu),這顯然增加了插入點(diǎn)的數(shù)量。由跳變概率計(jì)算公式可知,若使得輸出節(jié)點(diǎn)d值為1的概率大于0.113,則可以保證d的跳變概率滿足閾值,即輸入節(jié)點(diǎn)a在替換后值為1的概率應(yīng)大于0.563。例如將節(jié)點(diǎn)a的概率(Pa0,Pa1) 替換為(0.8,0.2),則節(jié)點(diǎn)d的跳變概率為0.1344,大于閾值。

圖3(b)中兩輸入門的輸出節(jié)點(diǎn)c的跳變概率計(jì)算為0.09,閾值設(shè)定為0.1,同樣需要在輸入節(jié)點(diǎn)a處插入加速木馬檢測(cè)結(jié)構(gòu)。在這種情況下將概率替換為(0.5,0.5)或(0.8,0.2)都可以滿足輸出節(jié)點(diǎn)c的跳變概率大于閾值,但替換為(0.8,0.2)是更優(yōu)的選擇,因?yàn)樘兏怕试酱?木馬觸發(fā)節(jié)點(diǎn)被激活所需的時(shí)鐘周期數(shù)越短。

但并非所有的情況下將輸入節(jié)點(diǎn)的概率值取反都是最優(yōu)的權(quán)值替換選擇,例如圖3(c)中的結(jié)構(gòu)。同樣地,將節(jié)點(diǎn)a的概率替換為(0.5,0.5)或(0.8,0.2),節(jié)點(diǎn)c的跳變概率都能大于閾值,但同時(shí)會(huì)影響節(jié)點(diǎn)d的跳變概率,計(jì)算后發(fā)現(xiàn)需要用(0.5,0.5)替換才可以滿足節(jié)點(diǎn)d的跳變概率大于閾值,為減少插入點(diǎn)數(shù)量,降低加速木馬檢測(cè)結(jié)構(gòu)的面積開銷,這種情況下將輸入節(jié)點(diǎn)a的概率修改為(0.5,0.5)是最優(yōu)的權(quán)值替換選擇。

2 可調(diào)節(jié)跳變概率的加速木馬檢測(cè)方法

本文提出了一種可調(diào)節(jié)跳變概率的加速木馬檢測(cè)結(jié)構(gòu),并設(shè)計(jì)了相應(yīng)的權(quán)值選擇和插入點(diǎn)選擇算法,根據(jù)電路的拓?fù)浣Y(jié)構(gòu)選擇合適的插入結(jié)構(gòu),并動(dòng)態(tài)規(guī)劃插入點(diǎn)順序。

2.1 可調(diào)節(jié)跳變概率的結(jié)構(gòu)實(shí)現(xiàn)

可調(diào)節(jié)跳變概率的加速木馬檢測(cè)結(jié)構(gòu)如圖4(a)和4(b)所示,當(dāng)替換節(jié)點(diǎn)net的概率滿足Pnet1＞＞Pnet0 時(shí),選擇插入圖4(a)中結(jié)構(gòu);當(dāng)替換節(jié)點(diǎn)net的概率滿足Pnet0＞＞Pnet1 時(shí),則選擇圖4(b)中結(jié)構(gòu)進(jìn)行插入。圖4(a)中結(jié)構(gòu)由一個(gè)掃描觸發(fā)器和一個(gè)2-to-1 MUX 組成,觸發(fā)器的Q連接MUX的一個(gè)輸入,測(cè)試模式控制信號(hào)TE則和MUX的另外一個(gè)輸入端相連。MUX的選擇信號(hào)由電路中替換節(jié)點(diǎn)net控制,MUX的輸出則作為替換后的節(jié)點(diǎn)net′,圖4(b)中結(jié)構(gòu)是在圖4(a)中結(jié)構(gòu)的基礎(chǔ)上額外添加了2 個(gè)反相器。根據(jù)圖4(a)和4(b)中的加速木馬檢測(cè)結(jié)構(gòu),替換后節(jié)點(diǎn)net′的概率計(jì)算公式如表1所示。

圖4 本文提出的加速木馬檢測(cè)結(jié)構(gòu)

以替換節(jié)點(diǎn)net值的概率Pnet1＞＞Pnet0的情況為例,替換后節(jié)點(diǎn)net′的概率計(jì)算公式如表1 中式(1.1)和(1.2)所示。當(dāng)電路處在功能模式下,使能信號(hào)TE為0,則可簡(jiǎn)化為式(1.3)和(1.4),將掃描觸發(fā)器的值置為1并保持不變,此時(shí)替換后節(jié)點(diǎn)net′的值同節(jié)點(diǎn)net的值完全一致,該結(jié)構(gòu)可以保證電路的功能邏輯不受影響。因此,在電路進(jìn)入功能模式之前,工程師需要通過復(fù)位信號(hào)DOTESTn將新增掃描觸發(fā)器的值全部置1,來保證功能模式下電路的功能邏輯不變。當(dāng)電路進(jìn)入測(cè)試模式時(shí),使能信號(hào)TE為1,替換后節(jié)點(diǎn)net′的概率計(jì)算公式可簡(jiǎn)化為式(1.5)和(1.6),若掃描觸發(fā)器Q端值的概率(PFF1,PFF0)滿足(0.5,0.5),則替換后節(jié)點(diǎn)net′的概率(Pnet′0,Pnet′1)趨近于(0.5,0.5);若掃描觸發(fā)器Q端值的概率(PFF1,PFF0)滿足(0,1),即保持為常值0,則替換后節(jié)點(diǎn)net′值的概率滿足(Pnet′1,Pnet′0)=(Pnet0,Pnet1)。因此,該加速木馬檢測(cè)結(jié)構(gòu)既可以將替換節(jié)點(diǎn)net值的概率修改為(0.5,0.5),也可以修改為節(jié)點(diǎn)net值的概率取反后的值,需要根據(jù)電路的拓?fù)浣Y(jié)構(gòu)進(jìn)行判斷,選擇最優(yōu)的修改方式,在保證提高稀有節(jié)點(diǎn)跳變概率的前提下,最大化減少插入點(diǎn)的數(shù)量,降低面積開銷。

表1 替換后節(jié)點(diǎn)net′的概率計(jì)算公式

當(dāng)選擇用替換節(jié)點(diǎn)概率值取反的方式進(jìn)行修改時(shí),可以將該加速木馬檢測(cè)結(jié)構(gòu)進(jìn)一步優(yōu)化,優(yōu)化后的結(jié)構(gòu)如圖4(c)所示。同圖4(a)和4(b)中結(jié)構(gòu)相比,圖4(c)中選擇用反相器代替掃描觸發(fā)器,反相器會(huì)將TE值取反并同2-to-1 MUX 輸入端相連。該優(yōu)化后的結(jié)構(gòu)既可以保證測(cè)試模式下將替換節(jié)點(diǎn)處的概率值修改為取反后的值,又可以保證功能模式下電路的功能邏輯不變,并且一定程度上減少了需要添加掃描觸發(fā)器的數(shù)量,進(jìn)一步降低了面積開銷。

根據(jù)圖4(a)和4(b)中結(jié)構(gòu)可知,當(dāng)掃描觸發(fā)器Q端值的概率(PFF1,PFF0)滿足(0.5,0.5)時(shí),節(jié)點(diǎn)net′概率并非為(0.5,0.5),實(shí)際概率為通過式(1.5)、(1.6)、(2.5)和(2.6)計(jì)算后所得。為了便于描述,本文定義:

(1) 采用圖4(a)和4(b)中結(jié)構(gòu)修改后得到的概率值稱為平均權(quán)值,該替換方式稱為平均權(quán)值替換。此時(shí)掃描觸發(fā)器Q端值的概率(PFF1,PFF0)需滿足(0.5,0.5)。

(2) 采用圖4(c)中結(jié)構(gòu)修改后得到的概率值稱為反向權(quán)值,該替換方式稱為反向權(quán)值替換。

2.2 權(quán)值選擇算法

為了保證在替換節(jié)點(diǎn)處能夠選擇最優(yōu)的加速檢測(cè)木馬結(jié)構(gòu)進(jìn)行替換,需要對(duì)電路中稀有節(jié)點(diǎn)的扇出情況進(jìn)行分析,為此本文提出如算法1 所示的權(quán)值選擇算法。本文定義:節(jié)點(diǎn)的扇出路徑上同該節(jié)點(diǎn)相連的門定義為該節(jié)點(diǎn)的扇出門;節(jié)點(diǎn)的扇入路徑上同該節(jié)點(diǎn)相連的門定義為該節(jié)點(diǎn)的扇入門。節(jié)點(diǎn)所有扇出門的輸出端口定義為該節(jié)點(diǎn)的扇出節(jié)點(diǎn);節(jié)點(diǎn)扇入門的所有輸入端口定義為該節(jié)點(diǎn)的扇入節(jié)點(diǎn)。

算法1的輸入為稀有節(jié)點(diǎn)NETrare,插完掃描鏈[17]的門級(jí)網(wǎng)表以及預(yù)先設(shè)定的跳變概率閾值TPth,輸出則為最優(yōu)的替換權(quán)值WSP。首先需要獲取該稀有節(jié)點(diǎn)的扇入節(jié)點(diǎn)集合FIN、扇出節(jié)點(diǎn)集合FOUT以及扇入門類型,可以通過電子設(shè)計(jì)自動(dòng)化(electronic design automatic,EDA)綜合工具從門級(jí)網(wǎng)表中提取。然后根據(jù)扇入門類型從扇入集合FIN中選取一個(gè)扇入節(jié)點(diǎn)作為最優(yōu)的替換節(jié)點(diǎn)。選取替換節(jié)點(diǎn)的原則是:當(dāng)扇入門為與門或與非門時(shí),選擇扇入節(jié)點(diǎn)中值為1的概率最小的且未被替換過的節(jié)點(diǎn)作為替換節(jié)點(diǎn);當(dāng)扇入門為或門或或非門時(shí),則選擇扇入節(jié)點(diǎn)中值為0的概率最小的且未被替換過的節(jié)點(diǎn)作為替換節(jié)點(diǎn)。該選取原則的目的是最大化稀有節(jié)點(diǎn)的跳變概率。選定替換節(jié)點(diǎn)后,用平均權(quán)值和反向權(quán)值這兩種權(quán)值進(jìn)行替換,重新計(jì)算并得到稀有節(jié)點(diǎn)的跳變概率滿足閾值且小于閾值時(shí),選擇平均權(quán)值作為更優(yōu)的替換權(quán)值;反之,則選擇反向權(quán)值作為替換權(quán)值。若都滿足閾值,則需要進(jìn)一步計(jì)算該稀有節(jié)點(diǎn)的所有扇出節(jié)點(diǎn)的跳變概率,并統(tǒng)計(jì)扇出節(jié)點(diǎn)中跳變概率滿足閾值的總個(gè)數(shù),選擇使得總數(shù)更大的權(quán)值作為替換權(quán)值。若滿足閾值的扇出節(jié)點(diǎn)的總數(shù)依然相同,則選擇使得稀有節(jié)點(diǎn)跳變概率更大的權(quán)值,這是因?yàn)楦蟮奶兏怕蚀碓摴?jié)點(diǎn)被激活到稀有值狀態(tài)所需時(shí)鐘周期數(shù)更少。若替換完成后,該稀有節(jié)點(diǎn)的跳變概率依然小于閾值,則需要在它的扇入節(jié)點(diǎn)中,按照相同的原則繼續(xù)選擇最優(yōu)的替換節(jié)點(diǎn),直到該稀有節(jié)點(diǎn)的跳變概率大于閾值。

2.3 插入點(diǎn)選擇算法

電路中節(jié)點(diǎn)的跳變概率由它扇入路徑上的所有節(jié)點(diǎn)共同決定,因此為了最小化插入點(diǎn)個(gè)數(shù),節(jié)點(diǎn)扇入路徑上的所有稀有節(jié)點(diǎn)都應(yīng)優(yōu)先于該節(jié)點(diǎn)進(jìn)行加速結(jié)構(gòu)的插入,對(duì)于不存在扇入扇出關(guān)系的稀有節(jié)點(diǎn),它們的插入順序則不會(huì)相互影響。為了最小化跳變概率的計(jì)算次數(shù),節(jié)點(diǎn)的跳變概率計(jì)算只需要在它扇入路徑上的所有節(jié)點(diǎn)加速結(jié)構(gòu)插入完成后計(jì)算,為此本文提出了如算法2 所示的插入點(diǎn)選擇算法。本文將節(jié)點(diǎn)的全部扇入節(jié)點(diǎn)的個(gè)數(shù)定義為該節(jié)點(diǎn)的扇入度,顯然電路中輸入端口的扇入度均為0。

算法2的輸入是插入掃描鏈后的門級(jí)網(wǎng)表以及預(yù)先設(shè)定的跳變概率閾值,輸出為插入加速木馬檢測(cè)結(jié)構(gòu)后的網(wǎng)表UpdateNetlist。首先從門級(jí)網(wǎng)表中提取電路中各個(gè)節(jié)點(diǎn)NET的扇入門類型集合GNET、扇入節(jié)點(diǎn)集合FINNET和扇出節(jié)點(diǎn)集合FOUTNET。通過統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的扇入節(jié)點(diǎn)集合中節(jié)點(diǎn)個(gè)數(shù)可以得到該節(jié)點(diǎn)的扇入度DNET,然后將扇入度為0的節(jié)點(diǎn)放入集合A中,剩余節(jié)點(diǎn)都放入集合B中。循環(huán)開始后,每次從集合A中取出一個(gè)節(jié)點(diǎn),根據(jù)該節(jié)點(diǎn)扇入門類型計(jì)算其跳變概率,并判斷是否大于閾值。若該節(jié)點(diǎn)為稀有節(jié)點(diǎn),則根據(jù)算法1 選擇替換節(jié)點(diǎn)并判斷采用哪種權(quán)值進(jìn)行替換,在替換節(jié)點(diǎn)處插入對(duì)應(yīng)的加速木馬檢測(cè)結(jié)構(gòu),然后將該替換節(jié)點(diǎn)標(biāo)記為已替換。將該節(jié)點(diǎn)i的所有扇出節(jié)點(diǎn)的扇入度減1,更新集合A和B,將扇入度為0的扇出節(jié)點(diǎn)從集合B移出,并放入集合A中,重復(fù)此循環(huán),直到集合B為空,最終返回加速木馬檢測(cè)結(jié)構(gòu)全部插入完成后的網(wǎng)表。

以圖5 為例介紹完整的權(quán)值選擇和插入點(diǎn)選擇過程。圖5(a)中所示為初始電路,設(shè)定電路輸入端口值為0 和1的概率均為0.5,電路中各節(jié)點(diǎn)為1 和0的概率如圖中所示,設(shè)定跳變概率閾值為0.14。為了更好地理解權(quán)值選擇和插入點(diǎn)選擇過程,將圖5(a)中初始電路簡(jiǎn)化為圖6(a)中所示的拓?fù)浣Y(jié)構(gòu),帶有箭頭的線所示為稀有節(jié)點(diǎn)。根據(jù)插入點(diǎn)選擇算法,首先將電路中所有扇入度為0的節(jié)點(diǎn)放入集合A中,即A={G0,G1,G2,G3,G4,G5},如圖6(a)中虛線所示節(jié)點(diǎn),剩余節(jié)點(diǎn)放入集合B中。依次從集合A中取出節(jié)點(diǎn)G5、G4、G3,并更新集合B中對(duì)應(yīng)扇出節(jié)點(diǎn)的扇入度。當(dāng)G3 從集合A中取出后,B中節(jié)點(diǎn)G7的扇入度變?yōu)?,此時(shí)更新集合A={G0,G1,G2,G7},如圖6(b)所示。繼續(xù)從A中取出節(jié)點(diǎn)G7,由扇入門類型計(jì)算可知,G7的跳變概率大于閾值。更新G8 和G9的扇入度,并將扇入度為0的G9放入集合A中,如圖6(c)所示,隨后取出G9 并計(jì)算其跳變概率,G9的跳變概率同樣大于閾值。更新節(jié)點(diǎn)G11的扇入度,此時(shí)集合B中沒有節(jié)點(diǎn)滿足扇入度為0,集合A和B保持不變。繼續(xù)從集合A中取出節(jié)點(diǎn)G2,更新節(jié)點(diǎn)G8 扇入度,隨后將G8 放入集合A中,如圖6(d)所示。接著取出G8,并計(jì)算可知其跳變概率小于閾值,根據(jù)權(quán)值選擇算法選取值為1 概率更小的節(jié)點(diǎn)G7 為替換節(jié)點(diǎn),計(jì)算兩種權(quán)值替換下G8的跳變概率。計(jì)算可知,兩種權(quán)值替換下G8的跳變概率都大于閾值,則需要進(jìn)一步計(jì)算G8所有扇出節(jié)點(diǎn)的跳變概率,即G10 和G11。計(jì)算可知,當(dāng)采用反向權(quán)值替換后,即G7的概率值修改為(0.75,0.25),此時(shí)G10的跳變概率小于閾值,而采用平均權(quán)值替換后,G10 和G11的跳變概率均大于閾值,因此選擇平均權(quán)值,并在G7 處插入如圖5(b)左下角中虛線框內(nèi)的加速木馬檢測(cè)結(jié)構(gòu),此時(shí)G11變?yōu)槿鐖D6(e)中所示的虛線。隨后依次從集合A中取出節(jié)點(diǎn)G11、G2、G1、G6、G10、G12,每取出一個(gè)節(jié)點(diǎn)后,判斷其跳變概率是否大于閾值,并將更新后集合B中扇入度為0的節(jié)點(diǎn)放入集合A中,分別如圖6(e)、6(f)、6(g)、6(h)所示。計(jì)算可知G12的跳變概率小于閾值,同樣根據(jù)權(quán)值選擇算法將G11作為替換節(jié)點(diǎn),帶入兩種替換權(quán)值計(jì)算后可知,G12的跳變概率均滿足閾值,但反向權(quán)值使得G12的跳變概率更大,因此選擇反向權(quán)值為替換權(quán)值,并插入對(duì)應(yīng)的加速結(jié)構(gòu)。需要特別強(qiáng)調(diào)的是,由于節(jié)點(diǎn)G9 先于G8 從集合A中取出,為了不影響G9 及其扇出路徑上節(jié)點(diǎn)的跳變概率,加速結(jié)構(gòu)只會(huì)添加在門AND1 和AND2 之間。最終當(dāng)集合B為空時(shí),插入點(diǎn)選擇過程結(jié)束,此時(shí)電路中全部節(jié)點(diǎn)的跳變概率滿足閾值要求,插入加速結(jié)構(gòu)后的電路如圖5(b)所示。

圖5 示例電路

圖6 拓?fù)浣Y(jié)構(gòu)圖

3 加速硬件木馬檢測(cè)流程

綜上所示,本文提出的可調(diào)節(jié)跳變概率的加速硬件木馬檢測(cè)流程如圖7 所示。

圖7 加速硬件木馬檢測(cè)流程圖

首先,分析和統(tǒng)計(jì)電路中各個(gè)節(jié)點(diǎn)的扇入扇出節(jié)點(diǎn)集合及扇出門類型。其次,根據(jù)扇入扇出結(jié)構(gòu)和權(quán)值選擇規(guī)則,查找稀有節(jié)點(diǎn)并判斷需插入的加速木馬檢測(cè)結(jié)構(gòu)類型,并根據(jù)插入點(diǎn)選擇規(guī)則,動(dòng)態(tài)規(guī)劃稀有節(jié)點(diǎn)的優(yōu)化順序。最后,根據(jù)稀有節(jié)點(diǎn)及對(duì)應(yīng)的加速結(jié)構(gòu)類型,在替換節(jié)點(diǎn)處插入對(duì)應(yīng)的加速木馬檢測(cè)結(jié)構(gòu)直至滿足程序設(shè)定的結(jié)束條件。加速木馬檢測(cè)結(jié)構(gòu)插入完成后,需將新增的掃描觸發(fā)器全部放到掃描鏈上,保證功能模式下電路邏輯不變,測(cè)試模式下實(shí)現(xiàn)加速木馬檢測(cè)。

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

為了評(píng)估本文所提可調(diào)節(jié)跳變概率的加速木馬檢測(cè)方法對(duì)降低木馬激活時(shí)間及面積開銷的效果,本實(shí)驗(yàn)選取ISCSA’89 基準(zhǔn)電路作為評(píng)估對(duì)象,并使用DC 工具基于STM 65 nm 工藝進(jìn)行綜合、可測(cè)試性設(shè)計(jì)和加速木馬檢測(cè)結(jié)構(gòu)插入,生成最終的網(wǎng)表。實(shí)驗(yàn)通過perl 語言搭建算法執(zhí)行環(huán)境,并使用VCS 進(jìn)行隨機(jī)向量仿真驗(yàn)證。上述的電子EDA 工具都在Linux 環(huán)境下運(yùn)行,服務(wù)器的CPU 為Intel Xeon Platinum 8176,主頻為2.1 GHz,內(nèi)存容量為64 GB。在仿真測(cè)試過程中,電路所有輸入端口值為0 和1的概率均設(shè)定為0.5。

本文從跳變概率、木馬激活周期數(shù)及面積開銷3 個(gè)方面進(jìn)行分析和評(píng)估,實(shí)驗(yàn)結(jié)果如下。

4.1 跳變概率

考慮到實(shí)驗(yàn)的適用性和完備性,本文分別在4種閾值條件下,選擇ISCSA’89 基準(zhǔn)電路中的5 個(gè)基準(zhǔn)電路進(jìn)行實(shí)驗(yàn)。同初始電路以及文獻(xiàn)[13]中經(jīng)典方法相比,稀有節(jié)點(diǎn)的平均跳變概率統(tǒng)計(jì)結(jié)果如表2 所示。

由表中結(jié)果可知,根據(jù)本文方法插入加速木馬檢測(cè)結(jié)構(gòu)后,5 種基準(zhǔn)電路中稀有節(jié)點(diǎn)的平均跳變概率均顯著提高,且遠(yuǎn)大于閾值。當(dāng)閾值設(shè)定為1.0E-1時(shí),同初始電路相比,稀有節(jié)點(diǎn)的平均跳變概率提高了約4～6 倍;當(dāng)閾值設(shè)定為1.0E-4 時(shí),稀有節(jié)點(diǎn)的平均跳變概率則提高了約幾百到幾千倍。

表2的最后1 列是本文方法同文獻(xiàn)[13]中方法在4 種閾值情況下的實(shí)驗(yàn)對(duì)比結(jié)果。從結(jié)果來看,5 種基準(zhǔn)電路在采用本文方法后稀有節(jié)點(diǎn)的平均跳變概率都在文獻(xiàn)[13]中方法的基礎(chǔ)上有了明顯提高。其中,在電路s5378 和s38417 上的優(yōu)化效果最為明顯,尤其是s38417 中稀有節(jié)點(diǎn)的平均跳變概率提高了約50%。

表2 稀有節(jié)點(diǎn)平均跳變概率統(tǒng)計(jì)

4.2 木馬激活驗(yàn)證

為了直接驗(yàn)證本文方法能否有效地加速硬件木馬檢測(cè),實(shí)驗(yàn)選擇對(duì)初始電路s5378 和已插入加速木馬檢測(cè)結(jié)構(gòu)的電路分別植入相同的硬件木馬電路,選擇10 000 條隨機(jī)向量進(jìn)行仿真,統(tǒng)計(jì)并比較木馬激活次數(shù)。考慮到硬件木馬規(guī)模的多樣性,實(shí)驗(yàn)采用文獻(xiàn)[13]中設(shè)計(jì)的2 種硬件木馬電路,分別如圖8(a)和8(b)所示。圖中虛線框內(nèi)是木馬激活模塊,當(dāng)木馬輸入端口分別滿足1101 和110 101 時(shí),硬件木馬電路被激活。實(shí)驗(yàn)設(shè)定跳變概率閾值為1.0E-1,并從電路s5378的稀有節(jié)點(diǎn)中隨機(jī)選擇節(jié)點(diǎn)作為2 種硬件木馬的輸入端口,并分別隨機(jī)生成1000 組木馬電路。隨機(jī)向量仿真完成后,木馬電路的平均激活次數(shù)統(tǒng)計(jì)如表3 所示。數(shù)據(jù)表明,對(duì)于未插入任何加速木馬檢測(cè)結(jié)構(gòu)的初始電路,木馬電路HT1 和HT2 幾乎無法被激活。采用本文方法和文獻(xiàn)[13]的方法后,兩種木馬電路都能被成功激活。相比于文獻(xiàn)[13]方法,本文方法將木馬平均激活次數(shù)分別提高至86.3 和10.8 次,這說明木馬被激活所需的時(shí)間周期數(shù)更短,木馬檢測(cè)速度的提升效果明顯。

表3 木馬平均激活次數(shù)對(duì)比

圖8 兩種木馬電路

4.3 時(shí)間及面積開銷評(píng)估

4.3.1 時(shí)間開銷分析

本文方法同經(jīng)典加速木馬檢測(cè)方法相比,時(shí)間復(fù)雜度對(duì)比如表4 所示。其中n表示電路中節(jié)點(diǎn)的個(gè)數(shù),w表示文獻(xiàn)[15]中權(quán)值的數(shù)量,r和d分別表示文獻(xiàn)[16]中稀有節(jié)點(diǎn)的個(gè)數(shù)和電路邏輯深度,g表示電路中門的個(gè)數(shù)。

表4 幾種經(jīng)典方法的時(shí)間復(fù)雜度對(duì)比

同文獻(xiàn)[12,13,15]中方法相比,本文方法的時(shí)間復(fù)雜度更低,更適合較大規(guī)模電路。

4.3.2 面積開銷分析

實(shí)驗(yàn)分別在3 種閾值條件下,對(duì)文獻(xiàn)[13]中方法和本文方法的基準(zhǔn)電路新增面積開銷進(jìn)行評(píng)估,結(jié)果如表5 所示。表中第3 列和第4 列分別對(duì)應(yīng)的是文獻(xiàn)[13]中方法和本文方法相比初始網(wǎng)表的面積增加比例。從實(shí)驗(yàn)結(jié)果可以看出,本文方法的新增面積開銷占比約為0.7%～12.1%,面積開銷很小,且面積開銷占比隨著閾值的減少而逐漸降低。設(shè)計(jì)者可以根據(jù)實(shí)際的面積開銷要求設(shè)定適合的跳變概率閾值。表5 中最后1 列是本文方法同文獻(xiàn)[13]中方法相比,新增面積開銷降低的百分比。顯然,3 種閾值條件下,5 種基準(zhǔn)電路在采用本文方法后新增面積開銷都在文獻(xiàn)[13]方法的基礎(chǔ)上有了明顯降低。其中,在電路s5378 和s13207 上的優(yōu)化效果最為明顯,尤其是s5378 中新增面積開銷平均優(yōu)化了68.9%。

表5 新增面積開銷統(tǒng)計(jì)

5 結(jié)論

硬件木馬檢測(cè)一直是業(yè)內(nèi)研究的熱點(diǎn)。本文在調(diào)研相關(guān)技術(shù)的基礎(chǔ)上提出了可調(diào)節(jié)跳變概率的加速硬件木馬檢測(cè)方法。該方法從芯片的門級(jí)網(wǎng)表中準(zhǔn)確提取出稀有節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu),分析其結(jié)構(gòu)得到最優(yōu)的權(quán)值替換策略,依據(jù)插入點(diǎn)選擇規(guī)則動(dòng)態(tài)規(guī)劃稀有節(jié)點(diǎn)的修改優(yōu)先級(jí),提高稀有節(jié)點(diǎn)的跳變概率;并根據(jù)權(quán)值類型,優(yōu)化插入的加速木馬檢測(cè)結(jié)構(gòu),降低硬件開銷,最小化加速木馬檢測(cè)結(jié)構(gòu)對(duì)芯片性能帶來的影響,同時(shí)保證功能模式下原有電路邏輯不變。實(shí)驗(yàn)結(jié)果表明,采用本文所提的加速硬件木馬檢測(cè)方法后,電路中稀有節(jié)點(diǎn)的跳變概率明顯提高,木馬激活時(shí)間大幅降低。同經(jīng)典加速木馬檢測(cè)方法相比,本方法在電路規(guī)模較大時(shí)效果更為明顯,設(shè)計(jì)者可以根據(jù)實(shí)際需求,設(shè)定合適的跳變概率閾值,從而達(dá)到加速檢測(cè)的同時(shí)降低面積開銷的目的。