電路工作模式下惰性節(jié)點(diǎn)的確定

崔曉通 鄒敏輝 吳剴劼

(信息物理社會(huì)可信服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室(重慶大學(xué)) 重慶 400044)(重慶大學(xué)計(jì)算機(jī)學(xué)院 重慶 400044)(xiaotong.sd@gmail.com)

電路工作模式下惰性節(jié)點(diǎn)的確定

崔曉通 鄒敏輝 吳剴劼

(信息物理社會(huì)可信服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室(重慶大學(xué)) 重慶 400044)(重慶大學(xué)計(jì)算機(jī)學(xué)院 重慶 400044)(xiaotong.sd@gmail.com)

集成電路設(shè)計(jì)和制造的全球化趨勢(shì)使得木馬電路可以在集成電路設(shè)計(jì)制造的任何階段被插入，這引發(fā)了對(duì)硬件安全的廣泛關(guān)注.從防御者的角度出發(fā)，木馬電路在宿主電路使用過程中絕大多數(shù)時(shí)間是靜默無害的，但是一旦被激活就會(huì)造成如信息泄露、功能異常或系統(tǒng)崩潰等嚴(yán)重危害;從攻擊者的角度出發(fā)，避免木馬電路被“誤觸發(fā)”是其最重要的一個(gè)設(shè)計(jì)目標(biāo)之一.普遍認(rèn)為，電路中那些具有較低狀態(tài)翻轉(zhuǎn)概率的惰性節(jié)點(diǎn)最有可能成為木馬電路的插入點(diǎn).因此目前檢測(cè)的主要手段之一是試圖尋找到這些惰性點(diǎn)，以便有針對(duì)性地嘗試以激活木馬電路.然而，目前的方法僅專注于尋找被測(cè)電路在測(cè)試模式下的惰性點(diǎn).提出了一種尋找被測(cè)電路在工作模式下的惰性點(diǎn)的方法.從攻擊者的角度出發(fā)，兩者的交集將是木馬電路的最佳插入點(diǎn)——可以較好地避免其插入的木馬電路在宿主電路的測(cè)試階段以及試運(yùn)行階段被“誤觸發(fā)”.因此從防御者的角度出發(fā)，找到測(cè)試模式和工作模式下共有的惰性節(jié)點(diǎn)并對(duì)其進(jìn)行檢測(cè)，有助于有效提高檢測(cè)效率.

木馬電路；工作模式；惰性節(jié)點(diǎn)；狀態(tài)翻轉(zhuǎn)概率；總狀態(tài)

集成電路設(shè)計(jì)和制造的全球化使得集成電路的安全課題成為了重要的研究領(lǐng)域，這是因?yàn)?，為了?jié)約成本，集成電路在設(shè)計(jì)和制造過程中將部分任務(wù)分包給第三方制造商或者設(shè)計(jì)公司完成，這使得硬件木馬電路的植入成為可能[1-5].

硬件木馬電路可以在規(guī)范說明階段、設(shè)計(jì)階段、制造階段和測(cè)試階段在內(nèi)的各個(gè)階段被插入[6]；其通常由2部分組成：觸發(fā)電路和負(fù)載電路.當(dāng)觸發(fā)電路在特定條件下被激活后，負(fù)載電路按照木馬設(shè)計(jì)者的意愿發(fā)揮作用，如通過旁信道泄露信息，或直接改變宿主電路的輸出，或?yàn)楣粽咛峁┻h(yuǎn)程控制等[7].存在于關(guān)鍵性系統(tǒng)(如經(jīng)濟(jì)、軍事、醫(yī)療等)中的木馬電路毫無疑問將會(huì)帶來重大安全隱患，因此木馬電路的檢測(cè)是一項(xiàng)十分重要的工作.

根據(jù)木馬電路的性質(zhì)，通常對(duì)其檢測(cè)的方法有包括功耗、時(shí)間分析在內(nèi)的旁道檢測(cè)技術(shù)[8]，和通過有目的地產(chǎn)生測(cè)試向量以激活木馬電路的檢測(cè)技術(shù)[9]，也可能是兩者的結(jié)合.

從攻擊者(即木馬電路設(shè)計(jì)者)的角度出發(fā)，“誤觸發(fā)”帶來的后果是災(zāi)難性的，不僅沒有實(shí)現(xiàn)其破壞目的，且將給其代表的利益集團(tuán)帶來經(jīng)濟(jì)聲譽(yù)上的重大損失.木馬電路的“誤觸發(fā)”指的是其設(shè)計(jì)的木馬電路在非最佳場(chǎng)景下被激活并對(duì)宿主電路造成影響.由于這種影響通常大而明顯，很容易被宿主電路的監(jiān)測(cè)機(jī)制捕獲，因此木馬電路通常只有一次機(jī)會(huì)對(duì)宿主電路造成危害，這使得避免木馬電路的誤觸發(fā)成為木馬電路設(shè)計(jì)的一個(gè)重要內(nèi)容.

不難預(yù)見的一個(gè)經(jīng)常會(huì)導(dǎo)致木馬電路誤觸發(fā)的情景是針對(duì)木馬電路的測(cè)試模式.在測(cè)試模式下，測(cè)試者通過向被測(cè)電路提供特定的測(cè)試向量以試圖激活被測(cè)電路中的木馬電路.另外一個(gè)重要的誤觸發(fā)場(chǎng)景是電路的工作模式——在電路的試運(yùn)行過程或是正常工作過程中由于電路的正常輸入而誤觸發(fā)了木馬電路.雖然木馬電路的設(shè)計(jì)本意即是在工作狀態(tài)中激活并對(duì)宿主電路造成影響，但是必須考慮到木馬電路危害的一次性，在非最佳場(chǎng)景時(shí)被激活并不是木馬電路設(shè)計(jì)的初衷.首先，幾乎所有的關(guān)鍵任務(wù)一般多會(huì)有試運(yùn)行階段.試運(yùn)行的設(shè)計(jì)毫無疑問將會(huì)盡量模擬真實(shí)工作的各種情況.在試運(yùn)行階段誤觸發(fā)木馬電路依然會(huì)暴露攻擊者的意圖但并沒有達(dá)到最佳攻擊意圖.其次，在電路的正常工作狀態(tài)下，未到達(dá)攻擊者最理想的工作場(chǎng)景(如特定的時(shí)間等)的情況下觸發(fā)木馬電路雖然會(huì)對(duì)系統(tǒng)造成一定的損害，但不一定是決定性的，因此也是誤觸發(fā)的一種.

為了避免誤觸發(fā)，木馬電路的設(shè)計(jì)者通常會(huì)利用宿主電路中的惰性節(jié)點(diǎn)來構(gòu)建其木馬電路的觸發(fā)電路.電路的惰性節(jié)點(diǎn)是那些擁有較低的狀態(tài)翻轉(zhuǎn)概率的電路節(jié)點(diǎn).因此，尋找惰性節(jié)點(diǎn)也是目前檢測(cè)木馬電路的一個(gè)主要方法.然而目前的工作僅考慮了測(cè)試模式下的惰性節(jié)點(diǎn)，如文獻(xiàn)[10].而在工作模式下的惰性節(jié)點(diǎn)卻被忽略.根據(jù)上述原因，我們認(rèn)為，那些在2種模式下翻轉(zhuǎn)概率都比較低的惰性節(jié)點(diǎn)最有可能被利用來構(gòu)建木馬電路的觸發(fā)電路.然而，如第1節(jié)所示，工作模式下電路節(jié)點(diǎn)狀態(tài)翻轉(zhuǎn)概率的計(jì)算完全不同于測(cè)試模式下的計(jì)算方法，因此準(zhǔn)確地計(jì)算工作模式下節(jié)點(diǎn)的翻轉(zhuǎn)概率進(jìn)而確定惰性節(jié)點(diǎn)是非常必要的.本文的主要工作是通過準(zhǔn)確計(jì)算工作模式下電路節(jié)點(diǎn)的翻轉(zhuǎn)概率，結(jié)合測(cè)試模式的檢測(cè)結(jié)果，確定真正的電路惰性節(jié)點(diǎn).

1 動(dòng)機(jī)及示例

根據(jù)引言的描述我們知道，可以對(duì)電路節(jié)點(diǎn)的狀態(tài)翻轉(zhuǎn)概率進(jìn)行計(jì)算進(jìn)而可以判斷可能被攻擊者選中的木馬電路植入點(diǎn).通常狀態(tài)翻轉(zhuǎn)概率低的電路節(jié)點(diǎn)具有更大的可能性成為植入點(diǎn)——將有效地降低木馬電路的誤觸發(fā)概率.因此，準(zhǔn)確地計(jì)算電路節(jié)點(diǎn)的狀態(tài)翻轉(zhuǎn)概率對(duì)于木馬電路的檢測(cè)具有重要意義.文獻(xiàn)[10]研究了在測(cè)試模式下對(duì)電路節(jié)點(diǎn)的轉(zhuǎn)移概率進(jìn)行計(jì)算進(jìn)而確定電路中的惰性節(jié)點(diǎn)——那些在測(cè)試過程中狀態(tài)翻轉(zhuǎn)概率明顯較低的電路節(jié)點(diǎn).在測(cè)試模式下，被測(cè)試電路中所有的寄存器通過掃描鏈組織，和測(cè)試電路的輸入一起受測(cè)試者的直接控制.因而每個(gè)寄存器和每個(gè)輸入的值均有同等概率為1或0，即50%為狀態(tài)1，50%為狀態(tài)0.不難看出，這樣的方式不僅沒有區(qū)分在工作模式時(shí)電路的常用和非常用輸入，而且更嚴(yán)重的是沒有區(qū)分被測(cè)試電路的非法狀態(tài)和合法狀態(tài)，以及狀態(tài)之間的非法和合法跳轉(zhuǎn)，因而測(cè)試模式下得到的惰性節(jié)點(diǎn)并不一定是工作模式下的惰性節(jié)點(diǎn).下面通過示例來進(jìn)一步說明這個(gè)問題.我們從一個(gè)有窮狀態(tài)自動(dòng)機(jī)(finite state machine, FSM)開始，如圖1所示，其描述的是具有一個(gè)輸入和一個(gè)輸出的電路，當(dāng)且僅當(dāng)輸入的字符串為10101時(shí)，輸出為1，否則輸出為0.

以這樣一個(gè)有窮狀態(tài)機(jī)為基礎(chǔ)，接下來便是對(duì)狀態(tài)的編碼以及電路的設(shè)計(jì)與實(shí)現(xiàn).從圖1可知，該狀態(tài)機(jī)除了初始狀態(tài)S0外還有S1,S2,S3,S4共4種狀態(tài)，考慮到設(shè)計(jì)和修改的簡(jiǎn)單性以及易于檢測(cè)非法狀態(tài)，我們采用“一位熱碼編碼”(one-hot encoding)的方式對(duì)狀態(tài)進(jìn)行編碼，并將S0，S1，S2，S3，S4分別編碼為0000,0001,0010,0100,1000，進(jìn)而設(shè)計(jì)了帶有4個(gè)寄存器的電路，如圖2所示.

Fig. 1 The example of a FSM圖1 有窮狀態(tài)機(jī)示例

Fig. 2 The example circuit according to the FSM圖2 根據(jù)有窮狀態(tài)機(jī)設(shè)計(jì)的電路示例

按照文獻(xiàn)[10]中的計(jì)算方法，如果節(jié)點(diǎn)N的狀態(tài)翻轉(zhuǎn)概率為Pt(N:0→1)=Pt(N:1→0)，節(jié)點(diǎn)N為0或1的概率分別為P(N=0)和P(N=1)，那么Pt(N:0→1)=Pt(N:1→0)=P(N=0)×P(N=1).在文獻(xiàn)[10]中，如果節(jié)點(diǎn)N為電路的輸入(primary input)，那P(N=0)=P(N=1)=0.5.如果該節(jié)點(diǎn)為某個(gè)邏輯門的輸出，那么根據(jù)邏輯門的種類，該節(jié)點(diǎn)為0或1的概率可以總結(jié)如下(假定該邏輯門的輸入為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).

根據(jù)這些來自文獻(xiàn)[10]的計(jì)算法則，圖3展示了圖2中部分電路節(jié)點(diǎn)的狀態(tài)概率.在圖3中，節(jié)點(diǎn)N的狀態(tài)概率以(P(N=0)，P(N=1))表示.節(jié)點(diǎn)的狀態(tài)翻轉(zhuǎn)概率因此可以簡(jiǎn)單計(jì)算出來.如，Pt(D4)=78×18=764.圖2示例電路中所有節(jié)點(diǎn)的狀態(tài)翻轉(zhuǎn)概率都可以通過這種方式計(jì)算得到，計(jì)算結(jié)果如表1第1行.

Fig. 3 The cone of the net D4圖3 節(jié)點(diǎn)D4的結(jié)構(gòu)

然而，文獻(xiàn)[10]中的計(jì)算方法只適用于測(cè)試模式下電路節(jié)點(diǎn)狀態(tài)翻轉(zhuǎn)概率的計(jì)算.當(dāng)電路在工作模式下，電路的狀態(tài)以及狀態(tài)跳轉(zhuǎn)并非是隨機(jī)的.因此，電路節(jié)點(diǎn)狀態(tài)翻轉(zhuǎn)概率的計(jì)算在工作模式下與在測(cè)試模式下是完全不同的.為了驗(yàn)證我們的想法，我們以成千上萬比特的隨機(jī)輸入序列對(duì)電路的運(yùn)行模式進(jìn)行了模擬，統(tǒng)計(jì)了各節(jié)點(diǎn)的狀態(tài)翻轉(zhuǎn)概率并列于表1的第2行.

從表1中可以看出2個(gè)結(jié)論:1)2種模式下的同樣節(jié)點(diǎn)的轉(zhuǎn)移概率在大多數(shù)情況下有很大的區(qū)別，如I1，D1，Z等;2)電路節(jié)點(diǎn)間的相對(duì)活躍程度在2個(gè)模式下是不一致的.如在測(cè)試模式下Pt(D2)>Pt(D3)，而在工作模式下Pt(D2)

Table 1 Pt Comparison between Test Mode[10] and Function Mode Simulation

2 工作模式下電路節(jié)點(diǎn)狀態(tài)翻轉(zhuǎn)概率的計(jì)算

在本節(jié)我們提出了一種準(zhǔn)確計(jì)算工作模式下電路節(jié)點(diǎn)狀態(tài)翻轉(zhuǎn)概率的方法，可以結(jié)合測(cè)試模式下各節(jié)點(diǎn)的狀態(tài)翻轉(zhuǎn)概率，更好地實(shí)現(xiàn)對(duì)木馬電路插入點(diǎn)的預(yù)測(cè).

2.1 節(jié)點(diǎn)狀態(tài)翻轉(zhuǎn)概率的計(jì)算

根據(jù)圖1的有窮狀態(tài)機(jī)，我們可以得到其狀態(tài)轉(zhuǎn)移表，如表2所示：

Table 2 State Transition Table of the Example Circuit

以圖3中D4節(jié)點(diǎn)為例，作為一個(gè)三輸入與門的輸出，D4從1轉(zhuǎn)換為0的概率是所有的輸入(X,I1,I2)在當(dāng)前狀態(tài)下都為1，且在下一個(gè)狀態(tài)有至少一個(gè)輸入變?yōu)?的概率.更進(jìn)一步地，跟蹤所有決定D4的電路輸入和寄存器{G1,G3,X}，D4從1轉(zhuǎn)換為0的概率相當(dāng)于{G1,G3,X}從{0,0,1}轉(zhuǎn)換到{0,0,0}，{0,1,0}，{1,0,0}，{1,1,0}，{0,1,1}，{1,0,1}，{1,1,1}中的一種概率之和.其中G1和G3來自狀態(tài)寄存器，X是電路的輸入.也就是說，D4從1轉(zhuǎn)換到0的概率Pt(D4:1→0)為下面所有概率之和：

Pt(D4:1→0)=

Pt({G1,G3,X}:001→000)+

Pt({G1,G3,X}:001→010)+

Pt({G1,G3,X}:001→011)+

Pt({G1,G3,X}:001→100)+

Pt({G1,G3,X}:001→101)+

Pt({G1,G3,X}:001→110)+

Pt({G1,G3,X}:001→111).

以Pt({G1,G3,X}:001→000)為例，D4從1轉(zhuǎn)換到0的條件發(fā)生于：

1) 在轉(zhuǎn)換之前{G1,G3}={0,0}，X=1；

2) 在轉(zhuǎn)換之后{G1,G3}={0,0}，X=0.

因此可以知道，計(jì)算節(jié)點(diǎn)的狀態(tài)翻轉(zhuǎn)概率需要電路的狀態(tài)和輸入的共同信息.因此，我們用stateinput表示一個(gè)電路的總狀態(tài)TS(total state)，那么Pt(TS:S1i1→S2i2)表示了電路在總狀態(tài)TS=S1i1和總狀態(tài)TS=S2i2之間的轉(zhuǎn)移概率.根據(jù)電路的有窮狀態(tài)機(jī)且假設(shè)隨機(jī)的電路輸入X，即P(X=0)=P(X=1)=0.5，可以推出其總狀態(tài)轉(zhuǎn)移概率矩陣M，如圖4所示：

S0∕0S0∕1S1∕0S1∕1S2∕0S2∕1S3∕0S3∕1S4∕0S4∕1S0∕00．50．500000000S0∕1000．50．5000000S1∕0000．50．5000000S1∕100000．50．50000S2∕00．50．500000000S2∕10000000．50．500S3∕0000．50．5000000S3∕1000000000．50．5S4∕00．50．500000000S4∕10000000．50．500

Fig. 4 Total state transition matrix M of the example circuit
圖4 示例的總狀態(tài)轉(zhuǎn)移概率矩陣M

顯而易見，節(jié)點(diǎn)的狀態(tài)翻轉(zhuǎn)概率將和電路的總狀態(tài)的轉(zhuǎn)移概率相關(guān).根據(jù)表2和圖4，可以得到：

Pt({G1,G3,X}:001→000)=

Pt(TS:S01→S10)+Pt(TS:S11→S10)+

Pt(TS:S31→S40)=

Pt(TS=S01)×0.5+P(TS=S11)×0.5+

P(TS=S31)×0.5=(P(TS=S01)+

P(TS=S11)+P(TS=S31))×0.5.

因此Pt({G1,G3,X}:001→000)的概率依賴于P(TS=S01)，P(TS=S11)和P(TS=S31).下面介紹電路的總狀態(tài)的概率計(jì)算方法.

2.2 電路中各個(gè)總狀態(tài)概率的計(jì)算

在工作模式下，電路的狀態(tài)由其有窮狀態(tài)自動(dòng)機(jī)決定.有窮狀態(tài)自動(dòng)機(jī)和輸入序列將共同控制到達(dá)各個(gè)狀態(tài)的概率，不斷增加的輸入最終將使各個(gè)狀態(tài)趨于一個(gè)穩(wěn)定狀態(tài)[11]，即到達(dá)各個(gè)狀態(tài)的概率將趨于一個(gè)穩(wěn)定的值.因此我們用

V=(v1=P(TS=S00),v2=P(TS=S01)，

v3=P(TS=S10),v4=P(TS=S11)，

v5=P(TS=S20),v6=P(TS=S21)，

v7=P(TS=S30),v8=P(TS=S31)，

v9=P(TS=S40),v10=P(TS=S41))

來表示示例中穩(wěn)定狀態(tài)的概率向量，假設(shè)總狀態(tài)總數(shù)為S，則：

(1)

根據(jù)穩(wěn)定狀態(tài)的特性有：

V×M=V.

(2)

根據(jù)式(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).

進(jìn)而我們可以得到(2.1節(jié)中)：

Pt({G1,G3,X}:001→000)=

(P(TS=S01)+P(TS=S11)+

P(TS=S31))×0.5=0.187 5；

Pt({G1,G3,X}:001→010)=0；

Pt({G1,G3,X}:001→011)=0；

Pt({G1,G3,X}:001→100)=0；

Pt({G1,G3,X}:001→101)=0；

Pt({G1,G3,X}:001→110)=0；

Pt({G1,G3,X}:001→111)=0.

將以上所有的概率加起來，我們得到D4在工作模式下的狀態(tài)轉(zhuǎn)移概率Pt(D4:1→0)=0.187 5.用同樣的方式，我們可以得到示例電路工作模式下所有節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移概率，將它們與電路工作模式下模擬得到的結(jié)果(表1第2行)相比，如表3所示：

Table 3 Pt Comparison between Simulation and our Method of the Example Circuit

運(yùn)用高斯消除法[12]根據(jù)式(1)(2)計(jì)算穩(wěn)定狀態(tài)向量時(shí)間復(fù)雜度為O(N2)，其中N為狀態(tài)總數(shù).然而對(duì)于大規(guī)模的電路，總的狀態(tài)數(shù)目隨著輸入和狀態(tài)的比特?cái)?shù)呈指數(shù)增長(zhǎng)，構(gòu)造一個(gè)完整的狀態(tài)轉(zhuǎn)移概率矩陣M或者穩(wěn)定狀態(tài)向量V是不可行的.在我們的方法中，我們提出通過盡可能多的大量輸入并記錄所有狀態(tài)及狀態(tài)轉(zhuǎn)移，運(yùn)用統(tǒng)計(jì)的方法推斷出M和V.比如，M中的某一個(gè)值可以通過統(tǒng)計(jì)所得的轉(zhuǎn)移次數(shù)與總時(shí)鐘節(jié)拍數(shù)的比率來求得，穩(wěn)定狀態(tài)下各個(gè)狀態(tài)的概率也可以用類似的方法得到.沒有監(jiān)測(cè)到的狀態(tài)轉(zhuǎn)移以及其穩(wěn)定狀態(tài)的概率被設(shè)為0.由于我們求取M和V的初衷就是觀察工作模式下狀態(tài)轉(zhuǎn)移的頻繁程度，因此這種統(tǒng)計(jì)的方法有非常好的效果.

3 算法及其復(fù)雜度

我們的算法目的是為了找到所有電路內(nèi)部節(jié)點(diǎn)的狀態(tài)翻轉(zhuǎn)概率.如果某節(jié)點(diǎn)是寄存器，其狀態(tài)翻轉(zhuǎn)概率可以從總狀態(tài)轉(zhuǎn)移概率矩陣M來決定.因此這里我們將集中討論那些非寄存器的內(nèi)部節(jié)點(diǎn)，即那些由組合邏輯門直接輸出的電路節(jié)點(diǎn)，如示例電路中I1，I2，I3等節(jié)點(diǎn).如果將電路的所有總狀態(tài)的集合定義為TSet，對(duì)于節(jié)點(diǎn)i，TSet可以分為2個(gè)子集Set1(i)和Set0(i)，它們分別表示可以使該節(jié)點(diǎn)的輸出為1和0的總狀態(tài)集合.它們之間有如下關(guān)系：

Set1(i)∪Set0(i)=TSet，

且:

Set1(i)∩Set0(i)=?，

Set1(i)和Set0(i)可以由i驅(qū)動(dòng)門的類型和驅(qū)動(dòng)門各輸入的Set0和Set1來決定.

算法1. 尋找Set1(i)和Set0(i).

① 初始化所有的Set1 andSet0為NULL；

②Find_Sets(i){

③ ifi是一個(gè)主輸入then

④ returnSet1(i) andSet0(i);*請(qǐng)看算法描述*

⑤ end if

⑥ for節(jié)點(diǎn)i的驅(qū)動(dòng)門的每個(gè)輸入j

⑦Find_Sets(j)；

⑧ end for

⑨ 計(jì)算Set1(i)和Set0(i)；

⑩ returnSet0(i)和Set1(i).}

算法1以節(jié)點(diǎn)i以及其所有輸入為輸入，輸出Set1(i)和Set0(i).算法1行①初始化所有節(jié)點(diǎn)的Set1(i)和Set0(i)為空；行②～⑩調(diào)用函數(shù)Find_Sets(i)；行③～⑤，如果節(jié)點(diǎn)i是一個(gè)電路輸入或寄存器，則它的Set1(Set0)是除了其本身為1(0)其余輸入和寄存器位為任意項(xiàng)；行⑥～⑧，對(duì)于節(jié)點(diǎn)i的每項(xiàng)輸入j，遞歸調(diào)用Find_Sets(j)；行⑨當(dāng)找到節(jié)點(diǎn)i的驅(qū)動(dòng)門的所有輸入狀態(tài)集合之后，Set1(i)和Set0(i)可以通過以下規(guī)則進(jìn)行計(jì)算：

1) 如果i的驅(qū)動(dòng)門是只有一個(gè)輸入j的反相器，則：

Set1(i)=Set0(j);

Set0(i)=Set1(j)；

2) 如果i的驅(qū)動(dòng)門是一個(gè)輸入為jk(k>1)的與門，則：

Set1(i)=∩Set1(jk);

Set0(i)=TSet-Set1(i)；

3) 如果i的驅(qū)動(dòng)門是一個(gè)輸入為jk(k>1)的與非門，則：

Set0(i)=∩Set1(jk);

Set1(i)=TSet-Set0(i)；

4) 如果i的驅(qū)動(dòng)門是一個(gè)輸入為jk(k>1)的或門，則：

Set0(i)=∩Set0(jk);

Set1(i)=TSet-Set0(i)；

5) 如果i是一個(gè)輸入為jk(k>1)的或非門，則：

Set1(i)=∩Set0(jk);

Set0(i)=TSet-Set1(i).

最后行⑩返回得到Set0(i)和Set1(i).

算法2. 計(jì)算SP(i).

①Pt(i)=0；

② forSet1(i)中的每個(gè)總狀態(tài)

③ forSet0(i)中的每個(gè)總狀態(tài)

④ 在矩陣M中找到對(duì)應(yīng)的翻轉(zhuǎn)概率P；

⑤ 在向量V中找到對(duì)應(yīng)的v；

⑥Pt(i)+=P×v；

⑦ end for

⑧ end for

算法2是計(jì)算節(jié)點(diǎn)i的狀態(tài)翻轉(zhuǎn)概率SP(i).節(jié)點(diǎn)i的狀態(tài)發(fā)生翻轉(zhuǎn)的充要條件是電路從Set1(i)中的某個(gè)總狀態(tài)轉(zhuǎn)移到Set0(i)中的某個(gè)總狀態(tài)，或者從Set0(i)中的某個(gè)總狀態(tài)轉(zhuǎn)移到Set1(i)中的某個(gè)總狀態(tài).因此，節(jié)點(diǎn)i的狀態(tài)翻轉(zhuǎn)概率的計(jì)算原理是計(jì)算從Set1(i)中的每個(gè)總狀態(tài)轉(zhuǎn)移到Set0(i)中的每個(gè)總狀態(tài)的概率之和.首先,行①將節(jié)點(diǎn)i的翻轉(zhuǎn)概率Pt(i)賦值為0；行②～⑧，對(duì)于Set1(i)中每個(gè)總狀態(tài)到Set0(i)中的每個(gè)總狀態(tài)的轉(zhuǎn)移在總狀態(tài)轉(zhuǎn)移矩陣中找到對(duì)應(yīng)的轉(zhuǎn)移概率P，并和穩(wěn)定狀態(tài)概率v中對(duì)應(yīng)的概率P相乘，累加到Pt(i).

我們用Nnet,Npri,Ndff分別代表一個(gè)電路的節(jié)點(diǎn)個(gè)數(shù)、主要輸入個(gè)數(shù)和狀態(tài)寄存器的個(gè)數(shù).

算法1的時(shí)間復(fù)雜度：考慮最壞的情況，計(jì)算節(jié)點(diǎn)i需要遞歸遍歷到所有節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有N個(gè)輸入，每個(gè)輸入都和所有的主要輸入和狀態(tài)寄存器相關(guān)，則算法1的時(shí)間復(fù)雜度為Nnet×2n×(Npri+Ndff).

算法2的時(shí)間復(fù)雜度：假設(shè)最壞的情況，節(jié)點(diǎn)i的Set1(i)和Set0(i)中各有2Ndff+Npri個(gè)總狀態(tài)，則算法2的時(shí)間復(fù)雜度為22(Ndff+Npri).

4 實(shí) 驗(yàn)

我們對(duì)7組基準(zhǔn)測(cè)試程序作了實(shí)驗(yàn)，它們都來自于ISCAS89電路基準(zhǔn)測(cè)試程序[13].對(duì)于每組基準(zhǔn)測(cè)試程序，我們都用文獻(xiàn)[10]中測(cè)試模式的計(jì)算方法、工作模式下我們的方法計(jì)算所有節(jié)點(diǎn)的狀態(tài)翻轉(zhuǎn)概率，并報(bào)告狀態(tài)翻轉(zhuǎn)概率小于5%的節(jié)點(diǎn)的交集，實(shí)驗(yàn)結(jié)果表4所示：

Table 4 Inactive Nets in both Test Mode and Function Mode

Continued (Table 4)

Continued (Table 4)

5 結(jié)論及進(jìn)一步工作

集成電路設(shè)計(jì)和制造的全球化趨勢(shì)使得木馬電路可以在集成電路設(shè)計(jì)制造的任何階段被插入，這引發(fā)了對(duì)硬件安全的廣泛關(guān)注.從防御者的角度出發(fā)，木馬電路在宿主電路使用過程中絕大多數(shù)時(shí)間是靜默無害的，但是一旦被激活就會(huì)造成如信息泄露、功能異?；蛳到y(tǒng)崩潰等嚴(yán)重危害.從攻擊者的角度出發(fā)，避免其插入的木馬電路被“誤觸發(fā)”是其最重要的一個(gè)設(shè)計(jì)目標(biāo)之一.普遍認(rèn)為，電路中那些具有較低狀態(tài)翻轉(zhuǎn)概率的惰性節(jié)點(diǎn)最有可能成為木馬電路的插入點(diǎn).因此目前檢測(cè)的主要手段之一是試圖尋找到這些惰性點(diǎn)，以便有針對(duì)性地嘗試以激活木馬電路.然而，目前的方法僅專注于尋找被測(cè)電路在測(cè)試模式下的惰性點(diǎn).本文提出了一種尋找被測(cè)電路在工作模式下的惰性點(diǎn)的方法.從攻擊者的角度出發(fā)，兩者的交集將是木馬電路的最佳插入點(diǎn)——可以避免其插入的木馬電路在宿主電路的測(cè)試階段和試運(yùn)行階段被“誤觸發(fā)”;從防御者的角度出發(fā)，兩者的交集將大大降低需要檢測(cè)的電路節(jié)點(diǎn)，有助于提高檢測(cè)效率.在文章的最后，我們報(bào)告了7組來自于ISCAS89的電路基準(zhǔn)測(cè)試程序在測(cè)試模式和工作模式下具有狀態(tài)翻轉(zhuǎn)概率小于5%的節(jié)點(diǎn)的交集.

進(jìn)一步工作為：算法1和算法2的時(shí)間復(fù)雜度并非是多項(xiàng)式時(shí)間內(nèi)可以完成的，尤其在電路規(guī)模比較大的時(shí)候，其計(jì)算時(shí)間隨寄存器以及電路輸入的位數(shù)呈指數(shù)增長(zhǎng)，只能解決小到中規(guī)模的電路(如僅有幾十個(gè)輸入和狀態(tài)寄存器).并且在計(jì)算構(gòu)造一個(gè)完整的狀態(tài)轉(zhuǎn)移概率矩陣M和穩(wěn)定狀態(tài)向量V時(shí)需要大量的隨機(jī)輸入，某些非惰性節(jié)點(diǎn)會(huì)被誤判成惰性節(jié)點(diǎn).我們觀察到，在實(shí)際的電路中，只有一些狀態(tài)寄存器對(duì)電路輸入敏感(造成電路狀態(tài)跳轉(zhuǎn))，很多狀態(tài)寄存器對(duì)電路輸入不敏感(不造成電路狀態(tài)跳轉(zhuǎn)).因此我們進(jìn)一步的工作將致力于電路工作模式下節(jié)點(diǎn)翻轉(zhuǎn)概率計(jì)算的啟發(fā)式算法的研究，利用某些狀態(tài)寄存器對(duì)電路輸入不敏感這個(gè)重要的觀察，以使得在基本保持計(jì)算精度的條件下極大地減少計(jì)算開銷.

[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[EBOL]. [2015-09-27]. http:en.wikipedia.orgwikiMarkov_chain

[12]Wikipedia. Gaussian elimination[EBOL]. [2015-09-27]. http:en.wikipedia.orgwikiGaussian_elimination

[13]Wikipedia. ISCAS89 sequential benchmark circuits[EBOL]. [2015-09-27]. https:filebox.ece.vt.edu～mhsiaoiscas89.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.

Identifying Inactive Nets in Function Mode of Circuits

Cui Xiaotong, Zou Minhui, and Wu Kaijie

(KeyLaboratoryofDependableServiceComputinginCyberPhysicalSociety(ChongqingUniversity),MinistryofEducation,Chongqing400044)(CollegeofComputerScience,ChongqingUniversity,Chongqing400044)

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.

hardware Trojan; function mode; inactive nets; switching probabilities of states; total states

2015-10-27；

2016-03-22

國家自然科學(xué)基金項(xiàng)目(61472052)；國家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(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