基于SAT的分離制造攻擊方法

劉佳琳，陸 昆，嚴(yán)昌浩，周 海，周 電，曾 璇

(復(fù)旦大學(xué) 專用集成電路與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，上海 201203)

目前，集成電路(Integrated Circuit， IC)在人們?nèi)粘Ｉ詈凸ぷ髦袩o(wú)處不在.隨著集成電路的發(fā)展，人們對(duì)知識(shí)產(chǎn)權(quán)保護(hù)日益重視、安全意識(shí)水平不斷提高，芯片設(shè)計(jì)的安全性得到越來(lái)越廣泛關(guān)注.近幾年來(lái)，在芯片硬件安全領(lǐng)域，不斷有學(xué)者提出新的攻擊和防御算法.

分離制造作為一種保護(hù)芯片設(shè)計(jì)版圖的安全手段被提出，引發(fā)了廣大學(xué)者的研究興趣.對(duì)分離制造的安全性以及對(duì)其進(jìn)行攻擊的難易、成本等問(wèn)題的研究具有重要意義.

1 背景介紹

隨著集成電路工藝節(jié)點(diǎn)邁向納米尺度，集成電路產(chǎn)業(yè)維持最先進(jìn)代工廠的成本非常高昂[1].越來(lái)越多的設(shè)計(jì)公司將其芯片制造外包給專門(mén)的芯片代工廠代為生產(chǎn).集成電路生產(chǎn)流程的全球化節(jié)省了昂貴生產(chǎn)設(shè)備的維護(hù)成本，但卻可能引入硬件安全漏洞[2].逆向工程[3]、IP盜版、非法過(guò)量生產(chǎn)和硬件木馬插入[4]等攻擊可發(fā)生在供應(yīng)鏈的任何一環(huán)，這些安全問(wèn)題每年給半導(dǎo)體行業(yè)造成數(shù)十億美元的損失[5].

美國(guó)情報(bào)高級(jí)研究計(jì)劃局(Intelligence Advanced Research Projects Activity， IARPA)提出了分離制造技術(shù)[6]作為抵擋這些攻擊的防御手段.設(shè)計(jì)公司將設(shè)計(jì)出來(lái)的最終結(jié)果，即準(zhǔn)備流片的GDS版圖文件分為兩部分： 前端部分(Front-End-Of-Line， FEOL)或稱下層部分由晶體管和底部密集的金屬層組成，這一部分通常具有比較小的線寬而必需采用先進(jìn)工藝生產(chǎn)；后端部分(Back-End-Of-Line， BEOL)或稱上層部分是由頂部金屬層構(gòu)成，它具有相對(duì)較大的線寬，無(wú)需特別先進(jìn)的制造工藝，可以由規(guī)模較小、工藝落后但受信任的芯片代工廠生產(chǎn)[7].Hill等[8]實(shí)現(xiàn)了一個(gè)1300萬(wàn)晶體管規(guī)模的復(fù)雜數(shù)字集成電路在單一代工廠的標(biāo)準(zhǔn)制造和在不同代工廠的分離制造.

分離制造通常有兩種情況[9]： 1) 制造FEOL和BEOL的兩個(gè)代工廠均是不被信任的，他們制造出的部分芯片需由受信任的集成設(shè)備來(lái)集成；2) FEOL部分由先進(jìn)而不受信任的代工廠制造，然后交付至工藝較落后但是受信任的代工廠來(lái)完成BEOL部分的制造.設(shè)計(jì)人員將GDS版圖文件分成兩部分分別交付給不同的代工廠生產(chǎn)制造，由此增強(qiáng)了芯片的安全性.分離制造使單獨(dú)一個(gè)代工廠失去了對(duì)完整芯片的掌控，代工廠在沒(méi)有完整芯片電路信息的情況下，無(wú)法準(zhǔn)確定位插入木馬的“安全”地點(diǎn)，或是隨意盜版生產(chǎn)整個(gè)芯片電路[10].在本文中，與大多數(shù)研究者一樣，著重研究第2種情況.

分離制造的示意圖如圖1所示.假設(shè)多層芯片版圖由圖1(a)中的粗實(shí)線分割開(kāi)，則BEOL部分位于粗實(shí)線上方，F(xiàn)EOL部分位于粗實(shí)線下方，分離所產(chǎn)生的切割點(diǎn)可能是通孔(via)，例如圖1(d)中缺失連線的斷點(diǎn)x1、x2、x3處于通孔處且連接至器件的輸入引腳，斷點(diǎn)y1和y2，處于通孔處且連接至器件的輸出引腳.同時(shí)，分離所產(chǎn)生的切割點(diǎn)也可能是電路原始引腳(Pin)，例如圖1(d)中左下角的斷點(diǎn)Pin1.分離制造雖然一定程度上加強(qiáng)了芯片的安全性，但是惡意代工廠仍然可以利用一些啟發(fā)式的算法來(lái)恢復(fù)整個(gè)電路.作為一個(gè)攻擊者，在制造FEOL部分的代工廠(如圖1(b)所示)可以訪問(wèn)工藝庫(kù)文件，在現(xiàn)有逆向工程工具[3]的幫助下，可獲得不完整的門(mén)級(jí)網(wǎng)表(Incomplete Gate-level Netlist, IGN)，該網(wǎng)表丟失了由BEOL決定的一些連線，如圖1(d)所示.攻擊者的目標(biāo)就是恢復(fù)這些缺失的BEOL連線，以獲得完整的電路設(shè)計(jì)，如圖1(c)所示.

圖1 分離制造示意圖Fig.1 Demonstration of split manufacturing

針對(duì)分離制造的攻擊方法，Rajendran等[10]提出了一種啟發(fā)式的攻擊方法，可以正確連接96%的BEOL連線，但他們僅在一個(gè)小測(cè)例上實(shí)現(xiàn)了100%的正確連接.Vaidyanathan等[11]證明，在第一層金屬層(Metal 1)進(jìn)行分離制造可以隱藏所有邏輯門(mén)之間的連線，并且這種做法的開(kāi)銷也小到可以忽略，但他們的測(cè)試芯片采用130 nm CMOS設(shè)計(jì)，在更先進(jìn)的工藝節(jié)點(diǎn)下，可制造性設(shè)計(jì)(Design for Manufacturing， DFM)問(wèn)題可能導(dǎo)致良率波動(dòng)極大，因此對(duì)低層金屬(如第一層金屬)的切割應(yīng)更為慎重.Mag?na等[7]研究了不同的鄰近攻擊以確定每條缺失連線的候選者，并指出僅靠鄰近攻擊無(wú)法恢復(fù)整個(gè)電路所有連線.Wang等提出的鄰近攻擊[12]以整體方式綜合利用布局、布線階段的經(jīng)驗(yàn)信息，并使用網(wǎng)絡(luò)流模型來(lái)推斷連接；試驗(yàn)結(jié)果表明，基于網(wǎng)絡(luò)流的攻擊僅在c880和c5315 2個(gè)電路上得到了100%的連線正確率，其他7個(gè)電路均未達(dá)到100%[12].從實(shí)用的觀點(diǎn)來(lái)看，只有當(dāng)恢復(fù)出的電路與原始電路完全一樣，即對(duì)于任何輸入向量都能產(chǎn)生相同的輸出向量時(shí)，才可認(rèn)為攻擊是成功的.換句話說(shuō)，凡是小于100%的連線正確率，在攻擊成功率上都可以看做是零.

Chow等[13-14]提出用與金屬端不相連的通孔設(shè)計(jì)來(lái)抵御芯片的逆向工程(如芯片拍照)，這種通孔稱為假通孔(dummy via)，可有效誤導(dǎo)逆向工程者認(rèn)為實(shí)際上下斷開(kāi)的金屬層之間是相連的，若有t個(gè)假通孔，通過(guò)精心設(shè)計(jì)這些假通孔在電路中的擺放位置，可將破解真假通孔問(wèn)題的復(fù)雜度提升至指數(shù)復(fù)雜度O(2t)[15]，其中任何一個(gè)判斷失誤都可能導(dǎo)致整個(gè)攻擊的失敗.而基于SAT的軟件攻擊算法可不受此類偽裝手段的誤導(dǎo)，且能保證破解出來(lái)的電路功能與原電路完全相同.此外，直接進(jìn)行逆向工程的成本一般也遠(yuǎn)遠(yuǎn)高于基于SAT的軟件攻擊算法.

本文提出并實(shí)現(xiàn)了一種名為SplitSAT的攻擊方法來(lái)攻擊基于分離制造的芯片，針對(duì)缺失連線的建模過(guò)程，建立了從分離制造攻擊到邏輯解密的橋梁.由于該模型引入環(huán)路到原始的無(wú)環(huán)電路中，因此我們采用更先進(jìn)的CycSAT算法[16]，該算法有效地解決了帶環(huán)電路的布爾可滿足性問(wèn)題(Boolean Satisfiability Problem， 簡(jiǎn)稱SAT問(wèn)題)求解.在此基礎(chǔ)上，利用幾何信息為每個(gè)待連接的輸入點(diǎn)構(gòu)建候選列表，減少SAT求解空間，極大提高了SplitSAT的求解效率.

2 問(wèn)題模型定義

分離制造攻擊模型中，假設(shè)先進(jìn)而不可信的代工廠制造FEOL部分，可信代工廠制造BEOL部分.前者為攻擊者，其目標(biāo)是利用工藝文件和FEOL信息來(lái)試圖恢復(fù)缺失的BEOL連線.

2.1 基于網(wǎng)絡(luò)流算法攻擊分離制造電路

Wang等[12]提出了一種基于網(wǎng)絡(luò)流的攻擊方法，該方法考慮了源自傳統(tǒng)物理設(shè)計(jì)布局/布線階段常用的一些基本結(jié)論，即物理距離、無(wú)環(huán)組合邏輯、負(fù)載電容約束、懸掛線的方向以及時(shí)序約束等.但文獻(xiàn)[12]假設(shè)攻擊者無(wú)法獲知原始電路的具體功能.如圖2所示，文獻(xiàn)[12]將不完整的門(mén)級(jí)網(wǎng)表(圖2(a))的連接問(wèn)題建模為網(wǎng)絡(luò)流問(wèn)題(圖2(b))，Eoi是從輸出點(diǎn)(yi)到輸入點(diǎn)(xj)的邊集合.通過(guò)邊(yi，xj)∈Eoi上的流量來(lái)推斷點(diǎn)yi和點(diǎn)xj之間的連線與否.

圖2 基于網(wǎng)絡(luò)流的攻擊Fig.2 Network-flow based attack

2.2 基于SAT算法攻擊邏輯加密電路

圖3 邏輯加密示意圖Fig.3 Demonstration of logic encryption

抵御芯片硬件攻擊的另一組技術(shù)稱為邏輯加密[17-20].邏輯加密的示意圖如圖3所示，其主要思想是通過(guò)插入額外的門(mén)或修改原始IC設(shè)計(jì)，引入額外的輸入，即密鑰.當(dāng)且僅當(dāng)設(shè)置了正確的密鑰k*，電路才能正常工作；否則，對(duì)于給定的輸入，電路將產(chǎn)生與預(yù)計(jì)不符的錯(cuò)誤輸出.

Subramanyan等[21]提出了一種基于可滿足性問(wèn)題的攻擊邏輯加密電路的算法，他們對(duì)每個(gè)測(cè)試電路分別施以6種邏輯加密算法來(lái)形成加密電路，實(shí)驗(yàn)結(jié)果表明SAT幾乎可以全部解密成功.該算法核心步驟是，給加密電路的兩個(gè)副本施以相同的輸入向量，但分別給予不同的、受一定條件約束的密鑰，然后檢查它們是否產(chǎn)生不同的輸出.能夠產(chǎn)生不同輸出的輸入向量稱為有分辨力的輸入模式(Differentiating Input Patterns， DIP)，DIP可以用來(lái)排除錯(cuò)誤的密鑰，并進(jìn)一步約束接下來(lái)所考慮的密鑰.圖4給出了基于SAT算法攻擊邏輯加密電路的示意圖.f(x)是原始電路的黑盒布爾函數(shù)，給定輸入模式x，得到輸出為f(x).g(x,k)是邏輯加密電路的布爾函數(shù).

2.3 SplitSAT攻擊問(wèn)題定義

以前，大多數(shù)研究工作均假設(shè)攻擊者無(wú)法獲得功能正常的目標(biāo)芯片[10,22-24].在本文中，同Xie等[25]的研究工作一樣，放寬Wang等[12]假定原始芯片的輸入-輸出對(duì)不可獲得的限制條件，假設(shè)攻擊者可以獲得原始IC的輸入-輸出對(duì).

事實(shí)上，上述假設(shè)一般是符合實(shí)際情形的.第一，雖然市場(chǎng)上沒(méi)有目標(biāo)芯片，但其功能往往可以從公開(kāi)系列產(chǎn)品的低端型號(hào)產(chǎn)品中猜測(cè)或獲取.因?yàn)楫a(chǎn)品通常是連續(xù)的，新一代的功能可以從舊產(chǎn)品中獲得.其次，若目標(biāo)芯片可以直接從市場(chǎng)上買(mǎi)到，直接進(jìn)行逆向工程的成本一般遠(yuǎn)遠(yuǎn)高于基于SAT的軟件攻擊算法.甚至有些芯片在其金屬層中運(yùn)用了一定的偽裝手段以抵御逆向工程，例如，金屬層到金屬層之間具有間隙的假通孔可以欺騙拍照逆向工程者得到錯(cuò)誤的連接[13-15,26]，而基于SAT的軟件攻擊算法可以不受這些欺騙的誤導(dǎo).

基于這一假設(shè)，分離制造攻擊問(wèn)題的完整表述如下：

給定分離后的版圖布局(FEOL信息)和相應(yīng)的工藝庫(kù)以及對(duì)原始正確電路的黑盒訪問(wèn)，找到缺失的BEOL連線，使恢復(fù)的電路可以完全(100%)像原始電路一樣正常工作.

為了解決以上電路連接關(guān)系的確認(rèn)問(wèn)題，本文采用多路復(fù)用器引入模擬加密電路，將恢復(fù)電路連線的問(wèn)題轉(zhuǎn)化為邏輯加密電路的可滿足性問(wèn)題，即將恢復(fù)缺失BEOL連線的問(wèn)題轉(zhuǎn)化為邏輯加密電路密鑰求解的問(wèn)題.

邏輯加密電路中，密鑰的作用實(shí)際上就是在多種可能性當(dāng)中選擇正確的那一種，例如利用一位密鑰選擇某個(gè)混淆的器件是與非門(mén)還是或非門(mén)，0代表與非門(mén)，1代表或非門(mén).這種機(jī)制啟發(fā)我們用多路選擇器來(lái)把恢復(fù)缺失BEOL連線的問(wèn)題建模到邏輯解密問(wèn)題.換句話說(shuō)，對(duì)不完整的FEOL電路用選擇器進(jìn)行模擬加密，將正確的選擇信號(hào)看做密鑰，全部的選擇信號(hào)即代表一種電路連接，找到了密鑰即代表恢復(fù)了正確連接.

3 SplitSAT攻擊算法

SplitSAT攻擊算法采用計(jì)算機(jī)理論中的可滿足性理論進(jìn)行電路連接關(guān)系的建模，以實(shí)現(xiàn)電路的恢復(fù).本節(jié)將介紹SplitSAT算法對(duì)分離制造的攻擊流程，使用多路復(fù)用器將分離制造攻擊問(wèn)題轉(zhuǎn)化為邏輯解密問(wèn)題的具體建模方法以及運(yùn)用幾何信息和物理設(shè)計(jì)工具特點(diǎn)的解空間縮減方法.

3.1 SplitSAT攻擊流程

分割層(split layer)的定義： 發(fā)生BEOL和FEOL分離的金屬層.例如，若設(shè)計(jì)者選擇Metal 5作為分割層，則意味著制造FEOL部分的代工廠無(wú)法獲得Metal 5及其以上金屬層的信息.注意，Via4(即Metal 4和Metal 5之間的通孔層)是攻擊者能看到的[12,18].

整個(gè)SplitSAT算法的攻擊流程如圖5(見(jiàn)第700頁(yè))所示.先進(jìn)而不受信任的代工廠即攻擊者，從FEOL信息和工藝庫(kù)開(kāi)始，首先要逆向出不完整的門(mén)級(jí)網(wǎng)表，然后使用多路選擇器(mux)對(duì)缺失連線進(jìn)行建模，生成邏輯加密電路g(x,k).給定原始電路的黑盒函數(shù)f(x)，若CycSAT求解出密鑰k*，則表示攻擊成功，該密鑰k*就蘊(yùn)含了目標(biāo)電路FEOL部分所缺失的BEOL連線信息.

一旦發(fā)生分離制造，就會(huì)產(chǎn)生一些金屬線的缺失，進(jìn)而產(chǎn)生攻擊者待連接的切割點(diǎn).如圖6(見(jiàn)第700頁(yè))所示，假設(shè)分割層是Metal 5，那么攻擊者需要連接4個(gè)切割點(diǎn)： via1，via2，via3，和Pin1.先記錄下所有切割點(diǎn)的坐標(biāo)，然后可將它們分為輸入和輸出兩組，通過(guò)追溯每個(gè)切割點(diǎn)的路徑來(lái)判斷其所屬的集合.一組是輸出點(diǎn)集，包括電路的原始輸入和中間邏輯門(mén)的輸出，在圖6中，Pin1和via2屬于輸出點(diǎn)集.另一組是輸入點(diǎn)集，包括電路的原始輸出和中間邏輯門(mén)的輸入，這里的via1和via3屬于輸入點(diǎn)集.

則問(wèn)題轉(zhuǎn)化為： 對(duì)于輸入點(diǎn)集中的每一個(gè)點(diǎn)，找到其信號(hào)來(lái)自于哪一個(gè)輸出點(diǎn)，并進(jìn)行連線.注意，一個(gè)輸出點(diǎn)可以連接到許多輸入點(diǎn)，而一個(gè)輸入點(diǎn)只能來(lái)自于一個(gè)輸出點(diǎn).

3.2 SplitSAT攻擊方法的建模

有了所有待連接的點(diǎn)，就可將原分離制造攻擊問(wèn)題建模為邏輯解密問(wèn)題.每一個(gè)輸入點(diǎn)，利用多路選擇器從所有輸出點(diǎn)中選出它自己的源信號(hào)，可選到其真實(shí)源信的各選擇信號(hào)值，構(gòu)成一個(gè)局部密鑰.所有輸入點(diǎn)形成的局部密鑰合并則構(gòu)成整個(gè)電路的密鑰.

圖5 SplitSAT攻擊流程圖Fig.5 SplitSAT attack flow

圖6 找到待連接點(diǎn)： (a)分離之前；(b)分離之后Fig.6 Find the points to be connected (a) before split and (b) after split

圖7給出了一個(gè)由分離制造攻擊到邏輯解密問(wèn)題建模的具體例子，其中圖7(a)是要實(shí)施攻擊的代工廠由下層部分信息所得到的不完整電路，綠色虛線表示該電路上層部分的連接信息，攻擊者不可見(jiàn)；圖7(b)是對(duì)應(yīng)的邏輯加密模型.對(duì)于每一個(gè)輸入點(diǎn)xi，有3個(gè)輸出點(diǎn)y1、y2和Pin1作為其可能的信號(hào)源，因此每個(gè)輸入點(diǎn)需要2個(gè)二路選擇器.具體來(lái)說(shuō)，keyinput0在y1和y2之間選擇，選擇結(jié)果為w1，然后keyinput1在w1和Pin1之間選擇，最終得到x1.在此示例中，正確的keyinput0和keyinput1的值都是0，即x1形成的局部密鑰為00.x2和x3以類似的方式建模，則整個(gè)電路的密鑰長(zhǎng)度為6.對(duì)于圖7中的電路，正確的密鑰是0010x1，其中x表示0和1都可以.

圖7 用選擇器模擬邏輯加密Fig.7 Using mux to simulate the logic encryption

圖8 建模時(shí)環(huán)路的引入Fig.8 Cycle introducing when modeling

在用選擇器對(duì)缺失連線進(jìn)行建模的過(guò)程中幾乎不可避免的會(huì)引入環(huán)路.如圖8所示，輸入點(diǎn)x1需要在輸出點(diǎn)y1和y2之間進(jìn)行選擇，而y2又依賴于信號(hào)x1，因此，形成一個(gè)循環(huán).注意，與圖7(a)相比，這里為了簡(jiǎn)明清晰，僅顯示了x1的相關(guān)部分.

Shamsi等[27]聲稱基于SAT的算法無(wú)法解決循環(huán)邏輯加密，即存在反饋環(huán)路的電路.事實(shí)上，Xie等[25]提出的基于SAT的攻擊方法，結(jié)果中出現(xiàn)很多“TO(time out occurs at 10 hours)”情況，分析其原因，是傳統(tǒng)SAT求解器無(wú)法解決帶環(huán)的電路而導(dǎo)致的失敗.

本文引入先進(jìn)的CycSAT算法[16]來(lái)解決環(huán)路問(wèn)題.CycSAT的偽代碼在表1中給出，其主要思想是： 找到表示“在密鑰k下沒(méi)有循環(huán)(No Cycle， NC)”的情況的合取范式(Conjunctive Normal Form， CNF)，并將該CNF加入到原本應(yīng)用SAT算法時(shí)的CNF中去[17].

表1 結(jié)構(gòu)化CycSAT算法偽代碼

只要得到正確的密鑰k*，使得對(duì)于任何輸入模式x，都有g(shù)(x,k*)≡f(x)，就意味著找到了所有缺失的連線，以此復(fù)原的電路便能夠完全像原始電路一樣正常工作.

3.3 解空間縮減

假設(shè)現(xiàn)有M個(gè)輸出點(diǎn)和n個(gè)輸入點(diǎn)等待連接，如果將所有輸出點(diǎn)都視為每個(gè)輸入點(diǎn)的候選者，則一個(gè)輸入點(diǎn)的連接關(guān)系就需要(M-1)個(gè)二路選擇器在M個(gè)輸出點(diǎn)中進(jìn)行選擇，整個(gè)電路共需要n(M-1)位的密鑰.由于SAT算法可以求解的問(wèn)題規(guī)模有限，減少問(wèn)題規(guī)模可提升可破解芯片的規(guī)模.

眾所周知，IC通常是通過(guò)傳統(tǒng)的物理設(shè)計(jì)(布局、布線)工具設(shè)計(jì)的[10,12].因此，有理由認(rèn)為一個(gè)引腳不太可能連接到距其太遠(yuǎn)的引腳，否則，它可能導(dǎo)致高成本或時(shí)序收斂問(wèn)題.基于這個(gè)限定條件，可以為每個(gè)輸入點(diǎn)依據(jù)距離，構(gòu)建一個(gè)候選列表，以便從中選擇它的信號(hào)源，而不是從所有輸出列表中選取.這里有兩種候選者，即通孔-通孔(via-via)候選者和通孔-引腳(via-pin)候選者.

3.3.1 通孔-通孔(via-via)候選者

對(duì)于目標(biāo)輸入點(diǎn)，例如圖9(a)中的通孔a，尋找最近的m個(gè)輸出通孔添加到其候選列表中.為了與布局布線工具兼容，本文選擇曼哈頓距離來(lái)表示兩點(diǎn)之間的距離.在版圖布局中，通孔a(p1,q1)和b(p2,q2)之間的距離dab由dab=|p1-p2|+|q1-q2|來(lái)表示.如圖9(a)所示，對(duì)于目標(biāo)輸入點(diǎn)a，如果設(shè)置m=2，則b和c同時(shí)被添加到a的候選列表中；如果設(shè)置m=1，則a的候選列表將只含有c而不包括b，因?yàn)閐ac小于dab.使用合理的參數(shù)m，實(shí)際連接到目標(biāo)輸入點(diǎn)的輸出點(diǎn)將被包含在相應(yīng)的候選列表中，否則若候選列表中不包含正確解，SAT求解器將無(wú)法給出正確密鑰.

3.3.2 通孔-引腳(via-pin)候選者

另一方面，版圖布局周圍的原始引腳也可能直接連接到芯片內(nèi)部較遠(yuǎn)的某個(gè)通孔，因此它們之間的距離可能相對(duì)較大，也應(yīng)將它們添加到對(duì)應(yīng)的候選列表中.出于這種考慮，將整個(gè)版圖布局劃分為3×3的網(wǎng)格，如圖9(b)所示.如果目標(biāo)輸入點(diǎn)位于布局的中心區(qū)域Z中，例如通孔b，則將版圖布局四周的所有引腳都加入其候選列表.如果目標(biāo)輸入點(diǎn)位于4個(gè)角區(qū)C1、C2、C3或C4中，那么將版圖該角落對(duì)應(yīng)的2個(gè)1/2邊緣上的引腳加入其候選列表，例如，如圖9(b)中左上角外圍紅色虛線所示，上邊界的左半部分和左邊界的上半部分含有的引腳，將被加入?yún)^(qū)域C1中的通孔a的候選列表.對(duì)于其他4個(gè)區(qū)域的目標(biāo)輸入點(diǎn)，其候選列表將包括相應(yīng)位置整條邊界上的引腳，例如，圖9(b)中右邊界上的8個(gè)引腳都將被加入目標(biāo)點(diǎn)c的候選列表，由藍(lán)色表示.

圖9 候選點(diǎn)(a) 通孔的通孔候選點(diǎn)和(b) 通孔的引腳候選點(diǎn)Fig.9 Candidates (a) via-candidates for vias and (b) pin-candidates for vias

表2 SplitSAT算法偽代碼

通過(guò)上述兩個(gè)候選者原則，可以構(gòu)建所有目標(biāo)輸入點(diǎn)的候選列表，這樣減少了問(wèn)題的規(guī)模，有利于基于CycSAT的算法來(lái)求解.對(duì)于一個(gè)攻擊問(wèn)題，首先嘗試使用完整模型的原始CycSAT；如果規(guī)模太大導(dǎo)致求解失敗，則嘗試使用via-via候選列表方法減少問(wèn)題規(guī)模后求解；最后，同時(shí)考慮via-via和via-pin候選者，進(jìn)行求解.表2給出了具有解空間縮減方法的整個(gè)過(guò)程的偽代碼.一旦得到密鑰k*，就相當(dāng)于獲得了缺失的BEOL連接，即恢復(fù)出了目標(biāo)攻擊電路.

4 結(jié)果及分析

表3 原始測(cè)試電路信息

使用ISCAS-85標(biāo)準(zhǔn)測(cè)試算例中最大的5個(gè)電路和ITC-99標(biāo)準(zhǔn)測(cè)試算例中最大的7個(gè)電路來(lái)評(píng)估SplitSAT對(duì)分離制造的攻擊，這些測(cè)例與文獻(xiàn)[28]中完全相同.表3中列出了原始電路基本信息，第1列為電路名稱，其余列分別為相應(yīng)電路的輸入、輸出、器件和線網(wǎng)的數(shù)量.這些電路由Synopsys Design Compiler工具綜合，原始的版圖布局是使用Nangate 45nm開(kāi)放式單元庫(kù)(http：∥www.nangate.com/?pageid=2325)和Cadence SoC Encounter工具生成的.算法由C++實(shí)現(xiàn)，所有試驗(yàn)的運(yùn)行環(huán)境為Intel Xeon X5650 CPU，主頻為2.67GHz，內(nèi)存為48GB.

Wang等[12]通過(guò)計(jì)算所能恢復(fù)的正確連線的數(shù)量來(lái)評(píng)估其攻擊模型的有效性，因?yàn)榧僭O(shè)攻擊者總是試圖恢復(fù)盡可能多的連線.但攻擊者的最終目標(biāo)是獲得一個(gè)與原始設(shè)計(jì)完全一樣的電路，因此，本文將100%正確率作為攻擊有效性的評(píng)估標(biāo)準(zhǔn).換句話說(shuō)，如果可以從FEOL信息中完全復(fù)原出功能正常的原始電路，則認(rèn)為攻擊是成功的，否則就是攻擊失敗.

表4是SplitSAT與基于網(wǎng)絡(luò)流的鄰近攻擊[1]的試驗(yàn)結(jié)果對(duì)比，所有試驗(yàn)所處設(shè)備環(huán)境相同.第1列表示不同電路，其余6列表示對(duì)應(yīng)電路的分割層.“Δ”表示電路沒(méi)有相應(yīng)的金屬層.一般而言，對(duì)于同一個(gè)電路，分離發(fā)生的金屬層數(shù)越低，切割到的連線越多，產(chǎn)生的斷點(diǎn)數(shù)也越多，問(wèn)題規(guī)模越大，求解越困難.

表4 SplitSAT與基于網(wǎng)絡(luò)流的攻擊結(jié)果對(duì)比

注： “—”表示未進(jìn)行實(shí)驗(yàn)；“*”表示62h仍未得出結(jié)果;“Δ”表示電路沒(méi)有該層金屬層.

表4內(nèi)數(shù)據(jù)表示該測(cè)例缺失的連線數(shù)量以及文獻(xiàn)[1]網(wǎng)絡(luò)流攻擊的連線正確率.缺失的連線數(shù)量可以大致衡量問(wèn)題的規(guī)模.灰色陰影表示SplitSAT可以100%攻擊成功，其中： 淺灰色表示使用CycSAT成功破解，深灰色表示進(jìn)一步采用文章3.3節(jié)中提出的經(jīng)驗(yàn)式候選列表方法成功破解.

由表4可以看出，網(wǎng)絡(luò)流攻擊[12]能100%破解的測(cè)例，SplitSAT均能100%破解；對(duì)于網(wǎng)絡(luò)流攻擊[12]未能100%破解的測(cè)例，SplitSAT仍能部分成功破解.事實(shí)上，網(wǎng)絡(luò)流攻擊[12]能100%破解的測(cè)例中缺失連線數(shù)最大為56(c5315在Metal 6分離)；而SplitSAT最大可完全破解缺失226條連線的測(cè)例(b_14_1_C在Metal 6分離)，能破解問(wèn)題規(guī)模大約是網(wǎng)絡(luò)流攻擊[12]的4倍.SplitSAT算法中，僅使用CycSAT成功破解的缺失連線數(shù)最大為76，而采用文章3.3節(jié)中提出的解空間縮減方法后，將缺失連線數(shù)擴(kuò)展至最大226條，該結(jié)果證實(shí)了解空間縮減方法的有效性.

表5列出了本文提出的SplitSAT攻擊方法能100%破解的各測(cè)例與Wang等基于網(wǎng)絡(luò)流的鄰近攻擊方法[12]的詳細(xì)數(shù)據(jù)對(duì)比.第1列表示每個(gè)電路以及對(duì)應(yīng)的分割層；第2～4列為網(wǎng)絡(luò)流攻擊方法[12]的結(jié)果，包括分離過(guò)程中產(chǎn)生的總切割點(diǎn)數(shù)，運(yùn)行時(shí)間和恢復(fù)連線的正確率；最后6列是SplitSAT方法的攻擊結(jié)果，包括切割到的引腳數(shù)，通孔數(shù)量，CNF的規(guī)模，算法運(yùn)行的迭代次數(shù)和時(shí)間.特別地是，當(dāng)SplitSAT攻擊成功時(shí)，其連線正確率為100%.

Wang等基于網(wǎng)絡(luò)流的鄰近攻擊[12]和本文提出SplitSAT攻擊的算法復(fù)雜度是不同的.基于網(wǎng)絡(luò)流的鄰近攻擊[12]中，在切割產(chǎn)生的輸出點(diǎn)集和輸入點(diǎn)集之間模擬建立最大流網(wǎng)絡(luò)，可在多項(xiàng)式時(shí)間內(nèi)求解，當(dāng)該網(wǎng)絡(luò)有u個(gè)點(diǎn)和v個(gè)有向邊時(shí)，最壞時(shí)間復(fù)雜度為O(uv2)；而本文提出的基于SAT問(wèn)題求解方法的復(fù)雜度是NP-完全問(wèn)題.對(duì)于芯片攻擊而言，芯片攻擊的成功率是第一位考慮的，本文中將破解所需時(shí)間放在相對(duì)次要的地位.

由表5結(jié)果可以看到，測(cè)例電路c2670在Metal 5分離時(shí)，基于網(wǎng)絡(luò)流的鄰近攻擊雖然耗時(shí)只有0.8s，但連接正確率僅為73%，這對(duì)于破解電路這一最終目標(biāo)而言，意義不大.而SplitSAT雖然耗時(shí)36.82s，卻可以100%恢復(fù)連線，完全破解.針對(duì)部分問(wèn)題規(guī)模很小的測(cè)例，SplitSAT的效率可能更高，例如電路c3540在Metal 6分離時(shí)，僅缺失17條連線，SplitSAT僅需要1.16s就能100%破解，比基于網(wǎng)絡(luò)流的鄰近攻擊(5.28s)耗時(shí)更短.

表5 基于網(wǎng)絡(luò)流的方法與SplitSAT攻擊細(xì)節(jié)對(duì)比

注： “—”表示該測(cè)例太小以至于無(wú)需使用選擇器模型.

除了分離產(chǎn)生的斷點(diǎn)數(shù)量之外，電路本身的規(guī)模也會(huì)影響運(yùn)行時(shí)間，電路規(guī)模越大，恢復(fù)原始設(shè)計(jì)所需要的時(shí)間則越長(zhǎng).例如，同樣以Metal 5為分割層，SplitSAT攻擊c2670電路需要36.82s，而攻擊c7552電路則需要282.35s，這兩個(gè)測(cè)例切割點(diǎn)的數(shù)目相當(dāng)，c2670引腳和通孔數(shù)為198個(gè)(96+102)，c7552引腳和通孔數(shù)208個(gè)(93+115)，但c7552電路規(guī)模大于c2670電路.當(dāng)原始電路本身規(guī)模較大時(shí)，CycSAT求解器必須花費(fèi)更多的時(shí)間來(lái)驗(yàn)證輸入-輸出對(duì)，且CNF更長(zhǎng)，所以時(shí)間開(kāi)銷也更大.對(duì)于切割層位置太低或電路規(guī)模太大的情況，SpliSAT的能力仍然受到一定程度的限制，未來(lái)還有待進(jìn)一步研究.

5 結(jié) 論

針對(duì)分離制造攻擊問(wèn)題，本文提出了基于SAT算法的攻擊方法SplitSAT，引入先進(jìn)的CycSAT算法處理建模過(guò)程中引入環(huán)路的問(wèn)題，利用物理信息構(gòu)建切割點(diǎn)的候選列表的方法來(lái)減少問(wèn)題規(guī)模.與最新基于網(wǎng)絡(luò)流的鄰近攻擊[12]的結(jié)果相比，SplitSAT可以在更多、更大規(guī)模的測(cè)例中實(shí)現(xiàn)100%的正確率.