0 引言

    我國的《中華人民共和國反不正當(dāng)競(jìng)爭(zhēng)法》和《集成電路布圖設(shè)計(jì)保護(hù)條例》對(duì)集成電路布圖設(shè)計(jì)進(jìn)行了不同程度的保護(hù)^[1]。集成電路布圖設(shè)計(jì)專有權(quán)作為芯片領(lǐng)域的一種專有知識(shí)產(chǎn)權(quán)保護(hù)形式，因其獲權(quán)方式較專利權(quán)相對(duì)簡(jiǎn)單，從而成為芯片設(shè)計(jì)公司較普遍擁有的一項(xiàng)知識(shí)產(chǎn)權(quán)?！都呻娐凡紙D設(shè)計(jì)保護(hù)條例》的第三十條明確規(guī)定，復(fù)制受保護(hù)的布圖設(shè)計(jì)的全部或者其中任何具有獨(dú)創(chuàng)性的部分的行為都認(rèn)定為侵權(quán)行為，并應(yīng)承擔(dān)相應(yīng)的賠償責(zé)任。也就是說，集成電路受該法律保護(hù)的實(shí)質(zhì)要件是布圖設(shè)計(jì)的“獨(dú)創(chuàng)性”部分。而要在布圖設(shè)計(jì)侵權(quán)的司法鑒定過程中獲得獨(dú)創(chuàng)性部分的布圖設(shè)計(jì)，需要使用反向工程進(jìn)行分析。我國《關(guān)于審理不正當(dāng)競(jìng)爭(zhēng)民事案件應(yīng)用法律若干問題的解釋》第十二條對(duì)合法的反向工程作了如下定義：“通過技術(shù)手段對(duì)從公開渠道取得的產(chǎn)品進(jìn)行拆卸、測(cè)繪、分析等而獲得該產(chǎn)品的有關(guān)技術(shù)信息”，即反向工程需付出重要?jiǎng)趧?dòng)、技術(shù)或資金投入。也就是說，以評(píng)價(jià)、分析、研究、教學(xué)為目的的反向分析是法律許可的行為，不視為侵權(quán)^[2]。

    布圖設(shè)計(jì)侵權(quán)的司法鑒定包括兩個(gè)步驟：布圖設(shè)計(jì)獨(dú)創(chuàng)性鑒定和布圖設(shè)計(jì)獨(dú)創(chuàng)性區(qū)域的相似度鑒定。目前，集成電路布圖設(shè)計(jì)相似度鑒定在行業(yè)內(nèi)尚沒有統(tǒng)一的執(zhí)行標(biāo)準(zhǔn)，且司法實(shí)踐中也鮮有案例可供借鑒，這給司法工作者帶來了判斷和執(zhí)行的困難，甚至導(dǎo)致布圖設(shè)計(jì)條例很難發(fā)揮應(yīng)有的作用。北京芯愿景軟件技術(shù)有限公司探索了一種較為可行的方法，即在考慮芯片工藝和相關(guān)領(lǐng)域后，根據(jù)版圖元素耦合度大小進(jìn)行模塊劃分，再對(duì)各模塊進(jìn)行相似度的比較，然后根據(jù)每個(gè)模塊的重要性給出模塊的權(quán)重，最后按照加權(quán)法給出整體的相似度。這種相似度的判定方法稱為“版圖細(xì)分加權(quán)法”。

1 版圖細(xì)分加權(quán)法概述

    《集成電路布圖設(shè)計(jì)保護(hù)條例》第二條第二款規(guī)定了集成電路布圖設(shè)計(jì)有兩種表現(xiàn)形態(tài)：集成電路和為制造集成電路的三維配置。集成電路芯片是制造廠商根據(jù)集成電路版圖對(duì)晶圓進(jìn)行掩膜光照生產(chǎn)獲得的最終產(chǎn)品。而集成電路版圖是為制造集成電路而準(zhǔn)備的三維配置，因此集成電路版圖是布圖設(shè)計(jì)的一種重要表現(xiàn)形式。

    當(dāng)侵權(quán)行為發(fā)生時(shí)，將布圖登記時(shí)提交的樣品芯片和侵權(quán)芯片進(jìn)行對(duì)比是判定是否侵權(quán)的一個(gè)重要依據(jù)。由于集成電路芯片結(jié)構(gòu)過于微觀復(fù)雜，必須要借助前述的反向工程獲得芯片各層次的照片才能對(duì)芯片的布圖進(jìn)行分析。然而，僅對(duì)登記的樣品芯片的照片和侵權(quán)芯片的照片進(jìn)行判斷，過于依賴判斷者的主觀經(jīng)驗(yàn)。本文提出了基于芯片提取得到的集成電路版圖的對(duì)比方法，由于集成電路版圖是為生產(chǎn)芯片準(zhǔn)備的三維配置，因此采用集成電路版圖（以下簡(jiǎn)稱版圖）的對(duì)比更加客觀。

    采用“版圖細(xì)分加權(quán)法”的原因有如下幾個(gè)方面。首先，版圖相似度判定涉及制造工藝、面積、各層圖元等多方面的因素；其次，版圖設(shè)計(jì)通常會(huì)采用按照功能模塊進(jìn)行布局的方法，因此版圖存在按模塊劃分布局的可行性；再次，版圖采用分層布圖方式，相似度判定需要考慮各版圖層差異，按層次細(xì)分符合設(shè)計(jì)習(xí)慣和通用規(guī)則；最后，版圖細(xì)分后的各部分存在重要性的差異。

    “版圖細(xì)分加權(quán)法”中的版圖有三個(gè)要素需要考慮，分別為：芯片工藝、頂層模塊布局和模塊內(nèi)部布局。每個(gè)版圖要素需要進(jìn)行細(xì)分，再進(jìn)行相似度判定。芯片工藝細(xì)分為：制造工藝、金屬和多晶層數(shù)、特征尺寸、芯片面積四個(gè)因素；芯片頂層模塊布局細(xì)分為：模塊數(shù)量、模塊相對(duì)位置兩個(gè)因素；影響模塊內(nèi)部布局相似度的原因比較復(fù)雜，涉及圖元面積、圖元層次、圖元形狀、圖元相對(duì)位置及圖元數(shù)量等方面，判定方法不同于其他兩個(gè)要素。圖1為版圖要素細(xì)分圖。根據(jù)本文描述的集成電路版圖相似度模型，將模塊內(nèi)部布局定義為版圖圖元集合。本文詳細(xì)闡述了關(guān)于版圖圖元集合相似度判定的方法。

2 集成電路版圖的相似度

    集成電路版圖(簡(jiǎn)稱“版圖”)是由版圖圖元(layout element)構(gòu)成的，任何一個(gè)版圖圖元是一個(gè)在特定版圖層上的多邊形。記P為所有多邊形構(gòu)成的集合，L為所有版圖層構(gòu)成的集合。

    定義1(版圖圖元)：一個(gè)集成電路版圖的圖元e是一個(gè)二元組(p，l)，其中p∈P表示這個(gè)圖元的多邊形，l∈L表示圖元所在的版圖層。

    將所有的版圖圖元構(gòu)成了的全圖元集合記作E。若一個(gè)版圖圖元的多邊形面積為0，稱這個(gè)版圖圖元為空版圖圖元；反之，若一個(gè)版圖圖元的多邊形面積不為0，稱這個(gè)版圖圖元為非空版圖圖元。一個(gè)集成電路版圖包含了若干個(gè)版圖圖元，因此有如下定義。

    定義2(集成電路版圖)：一個(gè)集成電路版圖L是全圖元集合E的一個(gè)子集，并且滿足如下條件：對(duì)L中在同一個(gè)版圖層上的任何兩個(gè)圖元e₁=(p₁，l)和e₂=(p₂，l)，p₁與p₂不相交。

    定義3(版圖層相似度函數(shù))：對(duì)任意的兩個(gè)版圖層l₁∈L和l₂∈L，版圖層相似度函數(shù)d(l₁，l₂)是一個(gè)返回值為0~1之間實(shí)數(shù)的函數(shù)：L∈L→[0，1]，對(duì)任意的l∈L，有d(l，l)=1。

    版圖層相似度函數(shù)用來表示這兩個(gè)版圖層之間的相似程度。在實(shí)際應(yīng)用中，一種簡(jiǎn)單的相似度函數(shù)可以定義為：版圖層相同時(shí)返回值為1，版圖層不同時(shí)返回值為0。

    定義4(版圖圖元的相似度函數(shù))：兩個(gè)非空版圖圖元e₁=(p₁，l₁)和e₂=(p₂，l₂)的相似度函數(shù)s(e₁，e₂)=area(intersect(p₁，p₂))/max(area(p₁)，area(p₂))×d(l₁，l₂)。其中：intersect(p₁，p₂)表示多邊形p₁和p₂的相交多邊形；area(p)表示多邊形p的面積；d(l₁，l₂)是版圖層相似度函數(shù)。

    根據(jù)上述定義，如果兩個(gè)版圖圖元e₁和e₂之間的相交區(qū)域越大，s(e₁，e₂)就越接近為1。并且，對(duì)任意的版圖圖元e，有s(e，e)=1。為了方便，若版圖圖元e₁和e₂之間至少有一個(gè)為空版圖圖元，那么定義s(e₁，e₂)=0。

    定義5(集成電路版圖在單射f下的相似度)：L₁和L₂是兩個(gè)集成電路版圖，其中|L₁|≤|L₂|，映射f是指從整數(shù)集合{n|1≤n≤|L₁|}到整數(shù)集合{n|1≤n≤|L₂|}的一個(gè)單射，L₁和L₂在單射f下的相似度S_f(L₁，L₂)定義如下：S_f(L₁，L₂)=∑s(e_i，e_f(i))/|L2|，其中i=1，2，…，|L₁|。當(dāng)|L₁|>|L₂|時(shí)，S_f(L₁，L₂)=S_f(L₂，L₁)。

    上述定義給出了兩個(gè)集成電路版圖相似度的一個(gè)比較方法，即建立兩個(gè)集成電路版圖圖元之間的一一對(duì)應(yīng)關(guān)系，并且計(jì)算相對(duì)應(yīng)的版圖圖元的相似度。以圖2為例，兩個(gè)版圖L₁和L₂分別包含n和m個(gè)圖元，并且n≤m。版圖L₁中的n個(gè)圖元一一映射到L₂中，每對(duì)映射的圖元的相似度為s₁，s₂，s₃，…，s_n，那么這兩個(gè)版圖在該單射下的相似度為：S_f(L₁，L₂)=(s₁+s₂+s₃+…+s_n)/m。

    考慮到不同的單射會(huì)得到不同的相似度結(jié)果，引入“集成電路版圖在單射下的最大相似度”定義，用來找到一個(gè)單射，使兩個(gè)版圖在該單射下的相似度值最大化。

    定義6(集成電路版圖在單射下的最大相似度)：L₁和L₂是兩個(gè)集成電路版圖，它們?cè)趩紊湎碌淖畲笙嗨贫萐(L₁，L₂)=sup({S_f(L₁，L₂)|f∈F})，其中F是版圖L₁到L₂的所有單射函數(shù)的集合，sup是表示集合上確界函數(shù)。

    根據(jù)上述定義，對(duì)任何一個(gè)非空集成電路版圖L，有S(L，L)=1，S(L，φ)=0。

    在比較兩個(gè)集成電路版圖時(shí)，要考慮兩個(gè)版圖的坐標(biāo)平移和坐標(biāo)翻轉(zhuǎn)的情況。坐標(biāo)翻轉(zhuǎn)是指R0、R90、R180、R270、MX、MY、MXR90、MYR90八種情況。

    定義7(集成電路版圖的變換)：針對(duì)一個(gè)集成電路版圖L，對(duì)L中的每一個(gè)版圖圖元應(yīng)用一次或者多次的坐標(biāo)平移或者坐標(biāo)翻轉(zhuǎn)，得到變換后的版圖為t(L)。

    根據(jù)上述定義，有如下定理：

    定理1(集成電路版圖單射下的最大相似度在變換下的不變性)：兩個(gè)集成電路版圖L₁和L₂，對(duì)任意的變換t，S(L₁，L₂)=S(t(L₁)，t(L₂))。

    證明(略)。

    定義8(集成電路版圖的最大相似度)：兩個(gè)集成電路版圖L₁和L₂，它們的相似度A(L₁，L₂)=sup({S(t(L₁)，L₂)|t∈T})，其中T是所有集成電路版圖變換的集合。

    根據(jù)上述定義，對(duì)任何一個(gè)非空集成電路版圖L，有A(L，L)=1，A(L，φ)=0。

    定理2(集成電路版圖的相似度函數(shù)的可交換性)：兩個(gè)任意的兩個(gè)集成電路版圖L₁和L₂，有A(L₁，L₂)=A(L₂，L₁)。

    證明(略)

3 應(yīng)用實(shí)例

    本文首先考慮將上述版圖相似度模型應(yīng)用于簡(jiǎn)單多邊形的情形。

    圖3為兩個(gè)簡(jiǎn)單多邊形(實(shí)際上是矩形)，多邊形A的大小為10×10，多邊形B的大小為11×9。當(dāng)對(duì)多邊形A不斷應(yīng)用平移變換時(shí)，兩個(gè)多邊形的重疊量將不斷變大，從而計(jì)算出來的相似度不斷變大，圖4給出了不同平移變換下根據(jù)重疊量計(jì)算出來的相似度，可以看到：這兩個(gè)多邊形的最大相似度為90%。

    MOS管是CMOS集成電路版圖中使用最多的器件，下面將本文第2節(jié)中的版圖相似度模型應(yīng)用于MOS管的版圖。

    圖5給出了兩個(gè)MOS管的版圖示意圖。構(gòu)成這兩個(gè)MOS管的多邊形數(shù)量相等，并且擺放位置類似。MOS管A的多晶寬度為2.0，孔大小為2.0×2.0；MOS管B的多晶寬度為1.8，孔大小為1.8×1.8。兩個(gè)MOS管的孔間距及孔與多晶的間距也略有不同。當(dāng)對(duì)MOS管A不斷應(yīng)用平移變換時(shí)，兩個(gè)MOS管相對(duì)應(yīng)多邊形的重疊量將不斷變大，從而根據(jù)定義5計(jì)算出來的相似度不斷變大，圖6給出了不同平移變換下根據(jù)重疊量計(jì)算出來的相似度，可以看到：這兩個(gè)MOS管的最大相似度為84.5%。

    圖7(a)和圖7(b)為兩個(gè)相似度極高的比較器布圖設(shè)計(jì)示意圖。構(gòu)成這兩個(gè)比較器的多邊形數(shù)量相等，擺放位置相同。比較器A和比較器B的多晶寬度相同，孔大小相同，只是孔的數(shù)量和密度不同。當(dāng)對(duì)比較器A不斷應(yīng)用平移變換時(shí)，兩個(gè)比較器相對(duì)應(yīng)多邊形的重疊量將不斷變大，從而根據(jù)定義5計(jì)算出來的相似度不斷變大，最后計(jì)算結(jié)果：這兩個(gè)MOS管的最大相似度為96.7%。

4 版圖相似度模型的局限性

    上述版圖相似度模型存在如下一些局限性：

    (1)上述集成電路版圖相似度模型并沒有考慮版圖中不同版圖圖元的權(quán)重問題。在不同領(lǐng)域的版圖設(shè)計(jì)中，一些版圖圖元傾向于比另一些版圖圖元顯得更為重要。為體現(xiàn)版圖圖元的不同重要性，可以對(duì)定義5中的公式進(jìn)行調(diào)整，引入權(quán)重因子。

    (2)集成電路版圖中經(jīng)常包括啞元（dummy）填充圖形，這些啞元填充圖形應(yīng)當(dāng)首先排除掉，然后再應(yīng)用上述的相似度模型。

    (3)在上述模型中，將集成電路版圖簡(jiǎn)單地定義為全圖元集合E的一個(gè)子集，但是集成電路版圖受到工藝規(guī)則的約束，并且版圖圖元要構(gòu)成一個(gè)有意義、能工作的芯片，還有很多約束規(guī)則要滿足。因此，全圖元集合E的絕大多數(shù)子集均不是“合理的”集成電路版圖。上述模型沒有將這些約束考慮在內(nèi)，其直接后果是計(jì)算出來的相似度結(jié)果可能系統(tǒng)性偏高。以本文第3節(jié)中“MOS管的相似度比較”為例，任何兩個(gè)單柵并且柵兩邊均有三個(gè)接觸孔的MOS管版圖可能都具有較高的相似度，盡管兩個(gè)MOS管版圖的設(shè)計(jì)是完全獨(dú)立完成的。產(chǎn)生這種較高相似度的原因是約束條件、習(xí)慣性的版圖設(shè)計(jì)方式等。由于這些因素難以形式化嚴(yán)格定義，因此本模型只能將其忽略。

    (4)本模型實(shí)際上適用于兩個(gè)集成電路模塊的比較。當(dāng)集成電路版圖包含多個(gè)模塊時(shí)，要考慮將整個(gè)版圖先細(xì)分為模塊，然后對(duì)模塊應(yīng)用本模型進(jìn)行相似度比較。

5 版圖相似度判定軟件工具

    在實(shí)際應(yīng)用本文版圖相似度模型時(shí)，首先要對(duì)版圖數(shù)據(jù)進(jìn)行預(yù)處理，將版圖數(shù)據(jù)規(guī)范化：

    (1)一個(gè)GDSII版圖文件通常包括矩形、多邊形、等寬線等不同形式的版圖圖元，為了后繼相似度判定的方便，需要將各種版圖圖元全部轉(zhuǎn)化為多邊形的表示。

    (2)集成電路版圖一般采用層次化設(shè)計(jì)，需要將版圖打平，形成完全打平的版圖。

    (3)將同一層相交的多邊形合并，以滿足定義2中多邊形不得相交的要求。

    (4)移除掉無用的版圖圖形（LOGO、dummy等）。

    版圖數(shù)據(jù)的規(guī)范化預(yù)處理可以使用Dracula、Calibre等版圖驗(yàn)證軟件完成。Dracula、Calibre等軟件具備完善的多邊形批處理功能，是理想的預(yù)處理工具。

    當(dāng)版圖數(shù)據(jù)量很大時(shí)，不可能用手工的方式來應(yīng)用上述版圖相似度模型，必須開發(fā)軟件工具來自動(dòng)計(jì)算兩個(gè)版圖的相似度。有如下一些考慮：

    (1)計(jì)算集成電路版圖在單射下的最大相似度是一個(gè)具有NP復(fù)雜度的算法。對(duì)兩個(gè)集成電路版圖L₁和L₂，假設(shè)|L₁|≤|L₂|，則L₁集合到L₂集合的單射函數(shù)的數(shù)量會(huì)達(dá)到O(|L₂|!×(|L₂|-|L₁|)!)。隨著L₁和L₂集合的增加，單射函數(shù)的數(shù)量會(huì)成幾何級(jí)數(shù)增長。在實(shí)際應(yīng)用時(shí)，可采用貪心算法(greedy algorithm)：對(duì)版圖L₁中的每一個(gè)圖元，在L₂集合中找到與其重疊比例最大的同層圖元，并在這兩個(gè)圖元之間建立映射關(guān)系。采用貪心算法，可以將計(jì)算單射下的最大相似度的復(fù)雜度降低到O(|L₂|×|L₁|)。貪心算法常常不能得到整體最優(yōu)解，但對(duì)大多數(shù)版圖，可以得到整體最優(yōu)解的近似解。

    (2)再計(jì)算不同變換下的平移。具體流程見圖8。

6 結(jié)論

    HxComparator是根據(jù)本文模型研發(fā)的集成電路版圖相似度判定軟件?？紤]到計(jì)算復(fù)雜性等方面的約束，HxComparator在計(jì)算不同單射下和不同變換下的最大相似度時(shí)，采用了性能優(yōu)化措施，從而使算法計(jì)算量顯著減低。該性能優(yōu)化可能使計(jì)算出來的相似度系統(tǒng)性偏低，在絕大多數(shù)情況下，該系統(tǒng)性偏低在可以忍受的誤差范圍內(nèi)。

參考文獻(xiàn)

[1] 鄭勝利.集成電路布圖設(shè)計(jì)保護(hù)法比較研究[J].北大知識(shí)產(chǎn)權(quán)評(píng)論，2001(1)：185-193.

[2] 于鵬，杜嬌，游濤，等.集成電路反向工程知識(shí)產(chǎn)權(quán)問題探析[J].中國集成電路，2010(11)：87-91.

[3] 郭禾.中國集成電路布圖設(shè)計(jì)權(quán)保護(hù)評(píng)述[J].知識(shí)產(chǎn)權(quán)，2005(1)：9-15.

[4] 郭禾.半導(dǎo)體集成電路知識(shí)產(chǎn)權(quán)的法律保護(hù)[J].中國人民大學(xué)學(xué)報(bào)，2004(1)：102-110.

[5] ZHAO X，XIAO C，LIN X M，et al.Efficient processing of graph similarity queries with edit distance constraints[J].The VLDB Journal，2013(22)：727-752.

[6] ANTIL H，F(xiàn)IELD S E，HERRMANN F，et al.Two-step greedy algorithm for reduced order quadratures[J].Journal of Scientific Computing，2013(57)：604-637.

[7] 韓鄭生.半導(dǎo)體制造技術(shù)[M].北京：電子工業(yè)出版社，2005.

[8] 丁柯，蔣衛(wèi)軍，張軍.集成電路反向分析技術(shù)[M].北京：中國科學(xué)技術(shù)出版社，2011.

[9] 吳漢東,知識(shí)產(chǎn)權(quán)法[M].北京：北京大學(xué)出版社，2007.

[10] 吳漢東.中國知識(shí)產(chǎn)權(quán)制度評(píng)價(jià)與立法建議[M].北京：知識(shí)產(chǎn)權(quán)出版社，2008.

[11] SALMANI H，TEHRANIPOOR M，PLUSQUELLIC J.A layoutaware approach for improving localized switching to detect hardware Trojans integrated circuits[C].2010-IEEE.10.1109/WIFS.2010.5711438.

[12] YUAN Z H，SUN S L，WANG G F.Recognizing geometric path from polygon-based integrated circuit layout[C].2008-IEEE.10.1109/SEC.2008.22.

[13] 徐象麟.鉅泉訴銳能微侵犯集成電路布圖設(shè)計(jì)專有權(quán)案研究[D].長沙：湖南師范大學(xué)，2015.

[14] 賀永興.集成電路布圖設(shè)計(jì)獨(dú)創(chuàng)性判斷研究[D].湘潭：湘潭大學(xué)，2012.

[15] 黃晶晶.集成電路布圖設(shè)計(jì)獨(dú)創(chuàng)性的認(rèn)定[D].上海：華東政法大學(xué)，2014.

[16] [廣東省高級(jí)人民法院(2014)粵高法民三終字第1231號(hào)]南京微盟電子有限公司與泉芯電子技術(shù)(深圳)有限公司侵害集成電路布圖設(shè)計(jì)專有權(quán)糾紛二審民事判決書[Z].[2015-11-13].https：//www.tianyancha.com/lawsuit/e036c0135a174851907427dfe5fee95e.

[17] 集成電路布圖設(shè)計(jì)保護(hù)條例.國務(wù)院令第300號(hào)[DB/OL].[2001-03-28].https：//baike.baidu.com/item/集成電路布圖設(shè)計(jì)保護(hù)條例/4996643?fr=aladdin.

[18] 集成電路布圖設(shè)計(jì)保護(hù)條例實(shí)施細(xì)則.國家知識(shí)產(chǎn)權(quán)局令第11號(hào)[DB/OL].[2001-10-01].https：//baike.baidu.com/item/集成電路布圖設(shè)計(jì)保護(hù)條例實(shí)施細(xì)則/7992664.

作者信息:

丁  柯，張  軍，蔣衛(wèi)軍

(北京芯愿景軟件技術(shù)有限公司，北京100095)