張藝倫 嚴(yán)迎建 李軍偉

(信息工程大學(xué) 河南 鄭州 450001)

0 引 言

隨著集成電路的高速發(fā)展以及各種芯片的廣泛應(yīng)用，硬件木馬可以在芯片設(shè)計(jì)的各個(gè)階段被插入，包括電路網(wǎng)表設(shè)計(jì)、芯片制造等，對(duì)芯片產(chǎn)業(yè)會(huì)造成極大的危害。硬件木馬從結(jié)構(gòu)上可以分為觸發(fā)器和有效載荷[1]。木馬攻擊者一般會(huì)選擇隱蔽的節(jié)點(diǎn)使得硬件木馬難以觸發(fā)，這種隱蔽的節(jié)點(diǎn)可以通過節(jié)點(diǎn)的翻轉(zhuǎn)概率或者可測(cè)性來衡量。文獻(xiàn)[2]對(duì)尋找這些木馬節(jié)點(diǎn)進(jìn)行了詳細(xì)的研究，指出低翻轉(zhuǎn)概率的節(jié)點(diǎn)可能有非常高的可測(cè)性，從側(cè)面說明了節(jié)點(diǎn)的翻轉(zhuǎn)概率與可測(cè)性并不相同。文獻(xiàn)[3]提出了基于可控性與可觀察性的硬件木馬檢測(cè)方法，通過機(jī)器學(xué)習(xí)的方法篩選出可控性與可觀察性較低的節(jié)點(diǎn)并作為可能的木馬節(jié)點(diǎn)。文獻(xiàn)[4]提出了稀有節(jié)點(diǎn)的篩選方法，考慮了可測(cè)性與翻轉(zhuǎn)概率等因素。然而這些方法并未從木馬觸發(fā)器的角度深入分析，選取的節(jié)點(diǎn)可能達(dá)不到攻擊者選擇其觸發(fā)木馬的理想情況。對(duì)于木馬觸發(fā)器設(shè)計(jì)來說，關(guān)鍵在于組成的觸發(fā)節(jié)點(diǎn)難以被激活，從而增強(qiáng)了硬件木馬的隱蔽性。本文針對(duì)硬件木馬的觸發(fā)器特點(diǎn)，提出了基于翻轉(zhuǎn)概率分析與可測(cè)性的稀有度指標(biāo)，可以最大程度篩選出那些潛在的木馬節(jié)點(diǎn)。

為了增強(qiáng)電路的安全，硬件木馬防護(hù)方法可以通過在電路中增加防護(hù)電路以混淆木馬攻擊者的視野，使其難以對(duì)混淆的硬件電路攻擊。電路混淆技術(shù)[5]主要包括基于組合電路的邏輯加密技術(shù)以及基于狀態(tài)機(jī)的時(shí)序型電路混淆設(shè)計(jì)[6-7]。本文主要選擇電路混淆中基于組合電路的邏輯加密技術(shù)。邏輯加密技術(shù)[8-9]通過在電路中插入密鑰門使電路的功能產(chǎn)生混淆，輸入正確的密鑰解鎖電路。

由于電路中存在的翻轉(zhuǎn)概率較低的節(jié)點(diǎn)容易被硬件木馬攻擊者所利用，因此對(duì)于硬件木馬防護(hù)來說，基于邏輯加密的硬件木馬方法關(guān)鍵在于消除電路存在的稀有節(jié)點(diǎn)，使得攻擊者無(wú)法輕易獲取電路的低概率節(jié)點(diǎn)即稀有節(jié)點(diǎn)。文獻(xiàn)[8-10]提出了利用AND/OR、XOR/XNOR加密門來改變節(jié)點(diǎn)的概率，提高了電路的混淆程度。然而這些方法針對(duì)抗可滿足性攻擊并沒有提出解決措施，導(dǎo)致自身的安全性較弱。基于可滿足性(SAT)的攻擊方法[11]能夠在幾個(gè)小時(shí)內(nèi)有效破解大多數(shù)的邏輯加密方法，通過選取合適的差分輸入向量，在同一個(gè)輸入向量中，選取至少兩個(gè)不同的密鑰，當(dāng)輸出結(jié)果不同時(shí)，則說明至少存在一個(gè)密鑰錯(cuò)誤。因此，邏輯加密方法的安全性能受到極大的威脅。SAT攻擊需要兩個(gè)條件：

(1) 獲取加密設(shè)計(jì)的網(wǎng)表；

(2) 市場(chǎng)上黑盒狀態(tài)下激活的功能IC。

對(duì)于邏輯加密方法，本文分析了提高硬件木馬防護(hù)的關(guān)鍵因素，從加密門的插入位置與加密門的類型考慮，提出基于樹形加密結(jié)構(gòu)[12]的改進(jìn)型邏輯加密算法，可以有效消除稀有節(jié)點(diǎn)的翻轉(zhuǎn)概率，并提升抗SAT攻擊性能。相比已有工作，優(yōu)點(diǎn)是提高了篩選潛在的木馬觸發(fā)器節(jié)點(diǎn)的有效性，同時(shí)，增強(qiáng)了木馬防護(hù)方法自身的抗SAT攻擊能力，并有效消除了稀有節(jié)點(diǎn)，達(dá)到混淆硬件電路的效果。

1 稀有節(jié)點(diǎn)篩選方法

稀有節(jié)點(diǎn)作為硬件木馬的植入點(diǎn)之一，可以構(gòu)成觸發(fā)器和有效載荷。由于有效載荷的設(shè)計(jì)還需要考慮到功能影響因素，這樣減小了稀有節(jié)點(diǎn)作為有效載荷的可能性，本文著重對(duì)組成觸發(fā)器的節(jié)點(diǎn)進(jìn)行篩選。

1.1 節(jié)點(diǎn)的翻轉(zhuǎn)概率分析

為了構(gòu)成硬件木馬的觸發(fā)器，可以選擇內(nèi)部節(jié)點(diǎn)觸發(fā)信號(hào)或者外部輸入。外部輸入對(duì)于設(shè)計(jì)者而言更加簡(jiǎn)單，通過部分輸入可以形成特定的觸發(fā)組合，本文主要研究?jī)?nèi)部節(jié)點(diǎn)觸發(fā)信號(hào)，為了表示潛在的觸發(fā)信號(hào)，定義了電路中節(jié)點(diǎn)為0的概率P0，為1的概率P1及翻轉(zhuǎn)概率P。翻轉(zhuǎn)概率P可以表示為P0和P1的乘積，當(dāng)翻轉(zhuǎn)概率P小于閾值時(shí)，這個(gè)節(jié)點(diǎn)為低翻轉(zhuǎn)概率節(jié)點(diǎn)[13]。

P=P0P1

(1)

1.2 節(jié)點(diǎn)的可測(cè)性分析

為了進(jìn)一步分析硬件木馬的特征，本文通過可測(cè)性來衡量硬件木馬的觸發(fā)器和有效載荷。假設(shè)電路節(jié)點(diǎn)N為低0節(jié)點(diǎn)，此時(shí)為了進(jìn)一步確定該節(jié)點(diǎn)是否為稀有節(jié)點(diǎn)，應(yīng)該考慮三個(gè)參數(shù)CC1、CC0、CO。當(dāng)節(jié)點(diǎn)N的參數(shù)CO值較高時(shí)，說明該節(jié)點(diǎn)能夠傳播到輸出的可能性較低。此時(shí)假設(shè)該節(jié)點(diǎn)作為硬件木馬觸發(fā)器的節(jié)點(diǎn)，那么只是通過該節(jié)點(diǎn)組合觸發(fā)有效載荷，即使傳播到輸出也并未受影響。因此，可控性參數(shù)CO可以用來判斷節(jié)點(diǎn)作為有效載荷的指標(biāo)，評(píng)估硬件木馬的傳播及隱蔽性。

可控性參數(shù)CC1、CC0分別表示想要賦值給該節(jié)點(diǎn)為1、0所需要對(duì)相關(guān)節(jié)點(diǎn)進(jìn)行賦值的最小次數(shù)，表明了該節(jié)點(diǎn)邏輯值的控制難度。盡管可控性CC0與CC1可能相互影響，但是它們的低可控性值的區(qū)間范圍會(huì)有所不同。當(dāng)節(jié)點(diǎn)N的稀有值為0，檢測(cè)的難度取決于檢測(cè)該節(jié)點(diǎn)邏輯值為0的控制難度，與該節(jié)點(diǎn)的可控性CC1值無(wú)關(guān)。因此，我們可以省略對(duì)CC1參數(shù)的影響。

1.3 稀有節(jié)點(diǎn)的篩選

硬件木馬觸發(fā)器的主要因素在于可控性與翻轉(zhuǎn)概率分析，節(jié)點(diǎn)的可控性概率定義為節(jié)點(diǎn)的可控性值占可控性最大值的比率。

(2)

為了篩選出低可控性節(jié)點(diǎn)，本文將節(jié)點(diǎn)可控性概率的閾值設(shè)定為β(0<β<1)，那么對(duì)于可控性1值來說，它的閾值為βCC1max，可控性0值的閾值為βCC0max。通過設(shè)定節(jié)點(diǎn)的可控性閾值，提取出大于閾值概率的節(jié)點(diǎn)，這些節(jié)點(diǎn)相對(duì)具有低可控性。

由于每個(gè)電路中節(jié)點(diǎn)的可控性值分布情況不同，可能存在一些尖峰情況，只有極少數(shù)非常低的可控性節(jié)點(diǎn)，因此，對(duì)于這種電路，可以根據(jù)電路的實(shí)際情況篩選低可控性節(jié)點(diǎn)，選定電路中可控性值較高的節(jié)點(diǎn)，占節(jié)點(diǎn)總數(shù)的5%。這樣可以有效針對(duì)電路的實(shí)際情況篩選出相對(duì)較難激活的節(jié)點(diǎn)。

通過進(jìn)一步分析，本文將節(jié)點(diǎn)的稀有度定義為可控性概率與翻轉(zhuǎn)概率之和。由于節(jié)點(diǎn)可控性0值與可控性1值的最大值不同，因此，稀有度可以分為兩種情況：

R1=(1-PC1)+P1R0=(1-PC0)+P0

(3)

R1、R0分別表示該節(jié)點(diǎn)為1、0時(shí)的稀有度，P1、P0分別表示該點(diǎn)為1、0的概率。當(dāng)節(jié)點(diǎn)的可控性值越大時(shí)，則說明該節(jié)點(diǎn)的低可控性越明顯，其可控性的難度越大，這與節(jié)點(diǎn)的翻轉(zhuǎn)概率變化趨勢(shì)有所不同，因此，為了統(tǒng)一描述，本文對(duì)稀有度中的可控性概率作以調(diào)整。當(dāng)節(jié)點(diǎn)的稀有度值較低時(shí)，則說明該節(jié)點(diǎn)為觸發(fā)器節(jié)點(diǎn)的可能性較大，并且應(yīng)該同時(shí)具有低可控性與低翻轉(zhuǎn)概率的特征。綜上所述，本文從構(gòu)成硬件木馬的觸發(fā)器角度分析稀有節(jié)點(diǎn)，為了進(jìn)一步提高篩選的精度和對(duì)其分析的精度，本文通過稀有度的指標(biāo)進(jìn)一步縮小節(jié)點(diǎn)范圍，減小節(jié)點(diǎn)作為硬件木馬觸發(fā)器的誤判率。

2 基于抗SAT的邏輯加密方法

2.1 密鑰門插入分析

如圖1(a)所示，N表示電路中需要加密的節(jié)點(diǎn)，而Key表示插入的密鑰，通過密鑰門gate,最終將節(jié)點(diǎn)N轉(zhuǎn)化為Ng。值得注意的是，改變節(jié)點(diǎn)N的途徑有兩種：一種是通過不同類型的密鑰門，另一種是通過密鑰數(shù)量。通過概率分析，我們可以發(fā)現(xiàn)AND/OR相比其他的門改變節(jié)點(diǎn)概率的效果更佳。而通過多重密鑰可以迅速改變概率，例如雙重密鑰門的效果比單密鑰的效果增加了近0.25。

(a) 密鑰插入模型 (b) “與非”加密門圖1 密鑰門插入模型

為了達(dá)到盡快消除稀有節(jié)點(diǎn)的理想效果，本文需要考慮密鑰門的插入位置，假設(shè)在稀有節(jié)點(diǎn)N上直接插入密鑰門g1，盡管將該節(jié)點(diǎn)轉(zhuǎn)變?yōu)镹g，但節(jié)點(diǎn)N的低概率值依舊存在，因此需要在電路稀有節(jié)點(diǎn)的前級(jí)選擇插入位置。

稀有節(jié)點(diǎn)的稀有值影響因素包括三個(gè)方面：稀有節(jié)點(diǎn)的輸入門類型、稀有節(jié)點(diǎn)的輸入節(jié)點(diǎn)概率以及稀有節(jié)點(diǎn)的輸入節(jié)點(diǎn)數(shù)量。當(dāng)稀有節(jié)點(diǎn)的輸入節(jié)點(diǎn)數(shù)量增多時(shí)，所需要針對(duì)的每個(gè)輸入節(jié)點(diǎn)的提升概率效果應(yīng)該更加明顯才能有效消除稀有節(jié)點(diǎn)。當(dāng)稀有節(jié)點(diǎn)的前級(jí)輸入節(jié)點(diǎn)概率與0.5的差值越小時(shí)，提升幅度越大，其影響效果更加明顯。當(dāng)稀有節(jié)點(diǎn)的輸入門類型不再是簡(jiǎn)單的“與”、 “或”門時(shí)，我們應(yīng)該對(duì)其進(jìn)行分類討論。

θ>PA1PB1

(4)

可以看出，為了產(chǎn)生低0稀有節(jié)點(diǎn)Ng，A、B節(jié)點(diǎn)中至少存在一個(gè)低1節(jié)點(diǎn)使得輸出節(jié)點(diǎn)的概率P1小于閾值θ。當(dāng)Ng為低1節(jié)點(diǎn)，稀有值的閾值為θ，構(gòu)造稀有節(jié)點(diǎn)的條件為：

θ>1-PA1PB1

(5)

可以看出，當(dāng)Ng為低1節(jié)點(diǎn)時(shí)，稀有值的閾值為θ，A、B節(jié)點(diǎn)為1的概率P1都很高，才能滿足構(gòu)造稀有節(jié)點(diǎn)的要求。通過“與非”門可以看出，消除電路中的稀有節(jié)點(diǎn)不一定按照該稀有節(jié)點(diǎn)的概率進(jìn)行插入，有可能需要提高相反概率的節(jié)點(diǎn)。因此，節(jié)點(diǎn)的概率不僅僅受邏輯門關(guān)系的影響，同時(shí)，還與輸入節(jié)點(diǎn)的概率相關(guān)。

在邏輯加密的設(shè)計(jì)過程中，本文圍繞提高電路中稀有節(jié)點(diǎn)的稀有值的概率，考慮該節(jié)點(diǎn)的前置門的類型以及該節(jié)點(diǎn)的稀有值，選擇合適的密鑰門。然后，針對(duì)稀有節(jié)點(diǎn)的稀有值，增加其密鑰門提升密鑰的效果，以提高基于邏輯加密的硬件木馬防護(hù)能力。

2.2 基于樹形加密模型的邏輯加密

為了增強(qiáng)邏輯加密對(duì)SAT攻擊的阻抗性，本文首先選取基于“與”、“或”加密門的加密電路進(jìn)行分析。如圖2所示，本文通過原始電路和加密電路的真值表分析原有基于AND/OR門的加密電路抗SAT攻擊的脆弱性。

(a) 原始電路

(b) 加密電路圖2 SAT攻擊分析

通過真值表分析，假設(shè)攻擊者選擇110、011、101三組輸入向量進(jìn)行密鑰比較，可以篩選出正確密鑰。本文在單節(jié)點(diǎn)上使用AND/OR密鑰門進(jìn)行加密與XOR密鑰門的抗SAT效果在迭代次數(shù)上相差不大?？梢钥闯?，盡管一些輸入對(duì)于不同的密鑰結(jié)果相同，增加了攻擊的冗余性，但假如選擇了如上方案，最少迭代次數(shù)為3。為了逐步增加SAT攻擊的難度，文獻(xiàn)[14]和文獻(xiàn)[15]分別提出了Anti-SAT與SAR模塊可以有效增加SAT攻擊的迭代次數(shù)，使得每一次迭代至多只有一個(gè)錯(cuò)誤密鑰呈現(xiàn)。但是，Anti-SAT加密結(jié)構(gòu)由于本身的單點(diǎn)函數(shù)構(gòu)造很容易引起概率偏斜攻擊[16]，SAR的結(jié)構(gòu)復(fù)雜難以迅速解決消除稀有節(jié)點(diǎn)問題，本文考慮第三種方法，基于樹形的抗SAT加密結(jié)構(gòu)來進(jìn)行邏輯加密方案。

文獻(xiàn)[12]提出了樹形加密方案，由于其結(jié)構(gòu)的特殊性，每次迭代攻擊最多只能排除1個(gè)錯(cuò)誤密鑰。如圖3所示，樹形加密結(jié)構(gòu)通過XOR門構(gòu)造相同結(jié)構(gòu)的復(fù)刻門，然后通過相反門輸出，該結(jié)構(gòu)可以極大增加SAT攻擊所需要的迭代次數(shù)，并提升抗SAT攻擊效果。盡管之前的樹形加密方案構(gòu)造了抗SAT攻擊模塊，但并未考慮到如何防止硬件木馬插入。

圖3 樹形加密模型

3 改進(jìn)型邏輯加密技術(shù)

本文主要對(duì)增強(qiáng)木馬防護(hù)能力與抗SAT攻擊能力兩方面對(duì)基于樹形加密的邏輯加密方法進(jìn)行改進(jìn)。為了加強(qiáng)對(duì)硬件木馬的防護(hù)能力，基于2.1節(jié)的密鑰門插入分析，考慮樹形加密門插入電路中改變節(jié)點(diǎn)的概率。為了有效消除稀有節(jié)點(diǎn)，本文將樹形加密應(yīng)用于稀有節(jié)點(diǎn)的前級(jí)節(jié)點(diǎn)概率改變。由于樹形加密門的原始門數(shù)至少為2，因此存在兩種改變方式：第一種可以將需要改變的節(jié)點(diǎn)作為樹形加密門中原始門輸入的一部分；另外一種是將需要改變的節(jié)點(diǎn)輸入作為原始門輸入的一部分。

3.1 消除稀有節(jié)點(diǎn)分析

本文從第一種情況進(jìn)行考慮，為了在該節(jié)點(diǎn)上構(gòu)造小型的樹形加密模塊，選取兩輸入“與”門作為原始門，并將原始門的輸入設(shè)置需要改變的節(jié)點(diǎn)N以及節(jié)點(diǎn)K，如圖4所示。值得注意的是，當(dāng)節(jié)點(diǎn)N為低1節(jié)點(diǎn)時(shí)，原始門設(shè)置成“或”門；當(dāng)節(jié)點(diǎn)N為低0節(jié)點(diǎn)時(shí)，原始門設(shè)置成“與”門。

圖4 單點(diǎn)加密門

由于樹形加密門至少需要兩輸入作為“與”、“或”門樹，因此本文考慮通過節(jié)點(diǎn)K設(shè)置為密鑰來替代原來電路中的另一個(gè)輸入。如表1所示，當(dāng)不考慮密鑰K的影響時(shí)，至少需要3次才能將所有錯(cuò)誤密鑰排除。對(duì)于加密模塊來說，此方法增加了抗SAT攻擊的迭代次數(shù)。當(dāng)需要將密鑰K納入?yún)^(qū)分輸入向量時(shí)，為了構(gòu)成單密鑰門，本文考慮控制值為1的密鑰門，因此選擇“或”門作為密鑰K的替代門。本文通過“或”門將節(jié)點(diǎn)K轉(zhuǎn)換為由于密鑰與節(jié)點(diǎn)T共同控制的輸入，如圖5所示，這樣保持了樹形加密門的結(jié)構(gòu)，并且由于“或”門的影響并未減小加密模塊的迭代次數(shù)。

表1 單點(diǎn)加密門真值表

圖5 替代門

當(dāng)選擇樹形加密模塊時(shí)，考慮其概率改變效果，通過節(jié)點(diǎn)Ng的概率說明加密節(jié)點(diǎn)N的概率變化，兩個(gè)“異或”門作為樹形加密模塊的輸入，然后連接復(fù)刻門g1。

假設(shè)K為輸入的隱形密鑰時(shí)，我們可以發(fā)現(xiàn)它的概率提升接近0.375，如式(6)所示。而當(dāng)K作為另一個(gè)密鑰門的輸入時(shí)，概率改變的效果受節(jié)點(diǎn)T的影響。由于節(jié)點(diǎn)N的概率x較低，因此概率效果不如前者，如式(7)所示。

(6)

(7)

第二種情況為樹形加密門的原始門輸入由前級(jí)節(jié)點(diǎn)的輸入組成，當(dāng)節(jié)點(diǎn)的邏輯0值較低時(shí)，原始門一般為“與”門，該節(jié)點(diǎn)N的概率x改變?yōu)?.75x，與第一種情況相比，盡管可能減小一定的資源，但是難以消除稀有節(jié)點(diǎn)。對(duì)于兩種情況而言，盡管樹形加密模塊一定程度上增加了需要改變的節(jié)點(diǎn)概率，但與其他加密門的效果相比，很難達(dá)到改變概率的理想情況。因此，本文考慮在加入樹形加密門時(shí)，提前對(duì)節(jié)點(diǎn)N作出改變。我們將密鑰分成了兩類，一類作為抗SAT攻擊，另一類作為密鑰門混淆及消除稀有節(jié)點(diǎn)。在節(jié)點(diǎn)N處插入密鑰門以迅速改變?cè)摴?jié)點(diǎn)的概率，當(dāng)原始門的輸入概率都提升至0.5時(shí)，該節(jié)點(diǎn)為0的概率值為0.562 5。因此，該樹形加密門和“與”、“或”加密門改變節(jié)點(diǎn)概率效果相似。

3.2 改進(jìn)型邏輯加密算法

基于3.1節(jié)的分析，本文對(duì)基于樹形加密的邏輯加密方法在消除概率上進(jìn)行改進(jìn)。由于樹形加密門的插入位置等影響，本文繼續(xù)對(duì)抗SAT攻擊進(jìn)行分析，以獲得最大化的安全防護(hù)效果。對(duì)于整個(gè)邏輯加密算法來說，如果加密門置于電路中的一部分，即便這個(gè)邏輯加密模塊本身具有較好的抗SAT攻擊能力，由于電路的輸出前后的邏輯關(guān)系，樹形加密結(jié)構(gòu)并不能保證每次差分輸入最多檢測(cè)出一個(gè)錯(cuò)誤密鑰。造成這樣的原因在于兩方面：一是原始門的輸入概率不均；二是輸出的結(jié)果并不一定能傳播到輸出，因此，抗SAT攻擊的效果會(huì)相對(duì)減弱。

為此，我們從兩方面解決這個(gè)問題：一是考慮樹形加密模塊的插入位置，選擇樹形加密門中原始輸入門的輸入及輸出以增加樹形加密模塊的傳播能力；二是考慮整體的加密效果與SAT攻擊之間的相互關(guān)系。

為了盡量減少電路的邏輯關(guān)系對(duì)樹形加密模塊造成干擾，本文提出在稀有節(jié)點(diǎn)的輸入傳輸端插入樹形加密模塊，將圖4的N、K替換成稀有節(jié)點(diǎn)的輸入A、B并作為原始門的兩個(gè)輸入端，如圖6所示。這樣可以避免因?yàn)橄粋€(gè)稀有節(jié)點(diǎn)而多次插入密鑰門，造成樹形加密門的結(jié)果傳播至輸出會(huì)受到其他節(jié)點(diǎn)的影響。

圖6 改進(jìn)型加密結(jié)構(gòu)

由于電路中稀有節(jié)點(diǎn)的輸入門類型以及輸入節(jié)點(diǎn)很多，當(dāng)選取由兩輸入的“與”門構(gòu)成的低1節(jié)點(diǎn)時(shí)，假設(shè)節(jié)點(diǎn)A的概率為a,節(jié)點(diǎn)B的概率為b,通過式(8)、式(9)得到N、g1、Ng三個(gè)節(jié)點(diǎn)的概率。節(jié)點(diǎn)Ng的概率為稀有節(jié)點(diǎn)改變后的概率值，當(dāng)節(jié)點(diǎn)的概率越大時(shí)，節(jié)點(diǎn)Ng的概率值更大。因此，在進(jìn)行邏輯加密設(shè)計(jì)時(shí)，綜合考慮樹形加密門的抗SAT攻擊效果，將稀有節(jié)點(diǎn)的輸入節(jié)點(diǎn)A、B概率設(shè)置約為0.5，那么樹形加密門輸出的節(jié)點(diǎn)概率即稀有節(jié)點(diǎn)概率改變?yōu)?.437 5。由“或”門構(gòu)成的低0節(jié)點(diǎn)邏輯表達(dá)式與式(8)、式(9)類似，并且當(dāng)輸入節(jié)點(diǎn)數(shù)量逐漸增大時(shí)，樹形加密門改變稀有節(jié)點(diǎn)的效果更加明顯。

(8)

(9)

為了增加整體的抗SAT效果，經(jīng)過文獻(xiàn)[17]分析與不同加密門的抗SAT效果得知，“異或”門可以有效提升抗SAT攻擊的迭代一次難度，在此基礎(chǔ)上本文選取電路中概率改變需求較小的節(jié)點(diǎn)插入“異或”門來干擾SAT攻擊。

為了詳細(xì)說明邏輯加密過程，本文通過改進(jìn)型邏輯加密算法詳細(xì)介紹該流程，以分析電路中的稀有節(jié)點(diǎn)為基礎(chǔ)，提出了基于樹形結(jié)構(gòu)的改進(jìn)型邏輯加密算法，增加基于邏輯加密的硬件木馬防護(hù)性能。算法的基本思想是以消除稀有節(jié)點(diǎn)和增加抗SAT攻擊難度為目標(biāo)，通過稀有節(jié)點(diǎn)的概率排序逐個(gè)插入密鑰門以消除節(jié)點(diǎn)的稀有值，并且根據(jù)需要增加混淆門。具體代碼如下：

1: Input:rare node(R),probability of net(Pn),

2: orignal circuit netlist(Oc),number of key(nk)

3: Output:Locked circuit netlist(Lc)

4: for all rare node in R do

5: select the least probabilityPlin p

6: if(Pl>Pr) then

7: for input i in input of nodenl

8: if(PTi<(0.5-Pn)) then

9: if(num_input≤3)

10: set and-gate as key gate

11: else if(num_input>3)

12: set double-and-gate as key gate

13: else if(PTi>(Pn+0.5)) then

14: if(num_input≤3)

15: set or-gate as key gate

16: else if(num_input>3)

17: set double-or-gate as key gate

18: end for

19: Insert the tree-type key gate with Nk-T

20: else if(Pl>Pr) then

21: Insert the xor key gate in the node

22: end if

23: end for

24: Update the locked netlist LC, Count the Rare node in LC

25: if (R≠?) then

26: return to Line 4

27: else

28: skip to line 29

29: end

基于樹形結(jié)構(gòu)的改進(jìn)型邏輯加密算法總體上可以分為兩個(gè)部分：一是初始化部分，即第1至3行的內(nèi)容(提出輸入輸出參數(shù))；二是插入密鑰門的部分，即第4至29行的內(nèi)容。

首先對(duì)于電路中的稀有節(jié)點(diǎn)進(jìn)行概率排序找到最低的概率節(jié)點(diǎn)nl，確定需要改變的節(jié)點(diǎn)，判斷該節(jié)點(diǎn)的概率是否小于中間概率值Pr。當(dāng)節(jié)點(diǎn)概率較小時(shí)，選擇插入樹形加密門，當(dāng)節(jié)點(diǎn)概率大于中間概率值Pr時(shí)，選擇插入“異或”門增加抗SAT攻擊迭代一次的難度。當(dāng)選擇樹形加密門時(shí)，找出該節(jié)點(diǎn)的前級(jí)門。通過對(duì)該節(jié)點(diǎn)的前級(jí)門進(jìn)行分析，尋找相對(duì)差值較小的節(jié)點(diǎn)。相對(duì)差值為該節(jié)點(diǎn)為1的概率與0.5的差值。當(dāng)該節(jié)點(diǎn)為1的概率較小時(shí)，插入“或”門增加該節(jié)點(diǎn)為1的概率；當(dāng)該節(jié)點(diǎn)為0的概率較小時(shí)，插入“與”門減小該節(jié)點(diǎn)為1的概率。與此同時(shí)，判斷輸入節(jié)點(diǎn)的數(shù)量，當(dāng)數(shù)量超過3時(shí)，需要對(duì)節(jié)點(diǎn)插入雙密鑰門，即連續(xù)插入兩個(gè)密鑰門，以增加節(jié)點(diǎn)的概率改變效果。值得注意的是，對(duì)于插入樹形加密結(jié)構(gòu)后的稀有節(jié)點(diǎn)如果還未能達(dá)到普通節(jié)點(diǎn)的要求，那么應(yīng)該在電路中插入相應(yīng)的門以消除其稀有節(jié)點(diǎn)。然后，更新電路的節(jié)點(diǎn)概率分布情況，在原有的稀有節(jié)點(diǎn)集中確定節(jié)點(diǎn)概率值最低的稀有節(jié)點(diǎn)進(jìn)行插入，直到稀有節(jié)點(diǎn)集為Φ。

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

本文通過modelsim軟件與C語(yǔ)言搭建實(shí)驗(yàn)平臺(tái)，將ISCAS’85基準(zhǔn)電路作為載體電路，主要對(duì)電路稀有節(jié)點(diǎn)進(jìn)行分析并且通過提出的邏輯加密算法對(duì)電路進(jìn)行加密。

首先對(duì)電路的稀有節(jié)點(diǎn)進(jìn)行分析，實(shí)驗(yàn)對(duì)象為c880電路，其節(jié)點(diǎn)數(shù)為443，通過modelsim軟件對(duì)電路進(jìn)行隨機(jī)向量仿真篩選出低翻轉(zhuǎn)概率節(jié)點(diǎn)，設(shè)定翻轉(zhuǎn)概率閾值為0.2，則低0節(jié)點(diǎn)與低1節(jié)點(diǎn)的稀有值概率約為0.28。然后，通過SCOAP算法[18]分別統(tǒng)計(jì)電路中低可控性0節(jié)點(diǎn)與低可控性1節(jié)點(diǎn)。將c880電路的可控性概率設(shè)置為0.4，通過統(tǒng)計(jì)節(jié)點(diǎn)的可控性情況，將可控性0值與可控性1值的閾值分別設(shè)置為11.2和14.8，最終將該電路的稀有度閾值設(shè)置為0.8。由于電路節(jié)點(diǎn)數(shù)與可控性值分布情況的不同，因此，需要根據(jù)電路的實(shí)際情況設(shè)置不同的可控性概率來選取部分較高的可控性值作為低可控性節(jié)點(diǎn)的判斷標(biāo)準(zhǔn)。本文提出的稀有度指標(biāo)主要在于從低可控性節(jié)點(diǎn)與低概率節(jié)點(diǎn)兩方面對(duì)稀有節(jié)點(diǎn)的范圍進(jìn)行約束，以選取難以測(cè)試的潛在觸發(fā)器節(jié)點(diǎn)。

最后，本文經(jīng)過篩選分別統(tǒng)計(jì)出電路中的低0稀有節(jié)點(diǎn)與低1稀有節(jié)點(diǎn)。如圖7所示，在c880電路中，分別篩選出4個(gè)低0節(jié)點(diǎn)與5個(gè)低1節(jié)點(diǎn)，極大地縮小了稀有節(jié)點(diǎn)的范圍，同時(shí)增加了檢測(cè)硬件木馬的可靠性。

(a) 低0節(jié)點(diǎn)篩選

(b) 低1節(jié)點(diǎn)篩選圖7 稀有節(jié)點(diǎn)篩選

為了進(jìn)一步比較該方法的篩選效率，本文通過分析ISCAS電路的節(jié)點(diǎn)分布情況，與前人的方法生成的稀有節(jié)點(diǎn)作比較。從表2中可以看出，本文提出的稀有節(jié)點(diǎn)篩選方法篩選出的低0節(jié)點(diǎn)與低1節(jié)點(diǎn)明顯較小，能夠得到真正具有威脅性的節(jié)點(diǎn)。經(jīng)統(tǒng)計(jì)，該方法相對(duì)于分別基于低翻轉(zhuǎn)概率節(jié)點(diǎn)與可控性節(jié)點(diǎn)的篩選方法，平均能提高64.82%、77.62%的篩選效果。

表2 節(jié)點(diǎn)篩選對(duì)比情況

然后，本文對(duì)ISCAS’85組合電路進(jìn)行邏輯加密，以c7552電路為例，如圖8所示，將電路中原有的稀有節(jié)點(diǎn)轉(zhuǎn)化為普通節(jié)點(diǎn)，原有稀有節(jié)點(diǎn)的翻轉(zhuǎn)概率閾值最低可以達(dá)到10e-13，而改變之后的節(jié)點(diǎn)翻轉(zhuǎn)概率可以達(dá)到0.1以上。

圖8 消除稀有節(jié)點(diǎn)分析

與此同時(shí)，本文對(duì)邏輯加密算法中消除稀有節(jié)點(diǎn)的效果進(jìn)行具體分析并與前人的工作進(jìn)行對(duì)比。以c7552電路為例，隨機(jī)選取電路中的四個(gè)稀有節(jié)點(diǎn)，通過不同的邏輯加密方法加密電路得到關(guān)于稀有節(jié)點(diǎn)的變化情況，如表3所示。相比文獻(xiàn)[8-9]的方法，本文方法進(jìn)一步提升了加密后的稀有節(jié)點(diǎn)概率值。本文對(duì)于隨機(jī)選取的節(jié)點(diǎn)平均提高的原因在于隨著稀有節(jié)點(diǎn)的輸入節(jié)點(diǎn)數(shù)增大。本文方法不僅僅可以改善輸入節(jié)點(diǎn)數(shù)的概率，同時(shí)能夠改善稀有節(jié)點(diǎn)的輸入門的概率影響，因此可以獲得更好的概率改變效果。

表3 節(jié)點(diǎn)概率改變效果

最后，本文對(duì)邏輯加密方法的抗SAT攻擊性能進(jìn)行比較，通過所需要的差分輸入向量DIP數(shù)量以及所需要的時(shí)間T(秒)可以判斷其安全防護(hù)能力。如表4所示，NA表示為至少1個(gè)小時(shí)難以被破解，在密鑰百分?jǐn)?shù)為50%時(shí)，分別與文獻(xiàn)[8-9]的方法進(jìn)行比較，可以發(fā)現(xiàn)本文的邏輯加密方法在保持原有樹形加密的抗SAT效果的基礎(chǔ)上，提高了SAT攻擊的迭代次數(shù)，并且增加了邏輯解密的時(shí)間。

表4 抗SAT攻擊對(duì)比情況

5 結(jié) 語(yǔ)

本文提出一種基于稀有度與邏輯加密的硬件木馬防護(hù)方法，有效篩選出電路中隱蔽的稀有節(jié)點(diǎn)，在有效消除稀有節(jié)點(diǎn)的前提下，能夠增加抗SAT攻擊的防護(hù)能力。通過實(shí)驗(yàn)驗(yàn)證，本文提出的硬件木馬防護(hù)方法具有可行性。下一步工作將在此基礎(chǔ)上對(duì)時(shí)序電路的硬件木馬防護(hù)方法展開研究。