0 引言

    我國(guó)的《中華人民共和國(guó)反不正當(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é)任,。也就是說(shuō),，集成電路受該法律保護(hù)的實(shí)質(zhì)要件是布圖設(shè)計(jì)的“獨(dú)創(chuàng)性”部分。而要在布圖設(shè)計(jì)侵權(quán)的司法鑒定過(guò)程中獲得獨(dú)創(chuàng)性部分的布圖設(shè)計(jì),，需要使用反向工程進(jìn)行分析,。我國(guó)《關(guān)于審理不正當(dāng)競(jìng)爭(zhēng)民事案件應(yīng)用法律若干問(wèn)題的解釋》第十二條對(duì)合法的反向工程作了如下定義：“通過(guò)技術(shù)手段對(duì)從公開(kāi)渠道取得的產(chǎn)品進(jìn)行拆卸、測(cè)繪,、分析等而獲得該產(chǎn)品的有關(guān)技術(shù)信息”,，即反向工程需付出重要?jiǎng)趧?dòng)、技術(shù)或資金投入,。也就是說(shuō),，以評(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)尚沒(méi)有統(tǒng)一的執(zhí)行標(biāo)準(zhǔn),，且司法實(shí)踐中也鮮有案例可供借鑒,，這給司法工作者帶來(lái)了判斷和執(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)過(guò)于微觀復(fù)雜,，必須要借助前述的反向工程獲得芯片各層次的照片才能對(duì)芯片的布圖進(jìn)行分析,。然而，僅對(duì)登記的樣品芯片的照片和侵權(quán)芯片的照片進(jìn)行判斷,，過(guò)于依賴判斷者的主觀經(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ù)用來(lái)表示這兩個(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é)果，引入“集成電路版圖在單射下的最大相似度”定義,，用來(lái)找到一個(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ì)算出來(lái)的相似度不斷變大，圖4給出了不同平移變換下根據(jù)重疊量計(jì)算出來(lái)的相似度,，可以看到：這兩個(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ì)算出來(lái)的相似度不斷變大，圖6給出了不同平移變換下根據(jù)重疊量計(jì)算出來(lái)的相似度，可以看到：這兩個(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ì)算出來(lái)的相似度不斷變大,，最后計(jì)算結(jié)果：這兩個(gè)MOS管的最大相似度為96.7%,。

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

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

    (1)上述集成電路版圖相似度模型并沒(méi)有考慮版圖中不同版圖圖元的權(quán)重問(wè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ù)子集均不是“合理的”集成電路版圖,。上述模型沒(méi)有將這些約束考慮在內(nèi),，其直接后果是計(jì)算出來(lái)的相似度結(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)移除掉無(wú)用的版圖圖形（LOGO、dummy等）,。

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

    當(dāng)版圖數(shù)據(jù)量很大時(shí),，不可能用手工的方式來(lái)應(yīng)用上述版圖相似度模型,，必須開(kāi)發(fā)軟件工具來(lái)自動(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ù)增長(zhǎng)。在實(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ì)算不同變換下的平移。具體流程見(jiàn)圖8,。

6 結(jié)論

    HxComparator是根據(jù)本文模型研發(fā)的集成電路版圖相似度判定軟件,。考慮到計(jì)算復(fù)雜性等方面的約束,，HxComparator在計(jì)算不同單射下和不同變換下的最大相似度時(shí),，采用了性能優(yōu)化措施，從而使算法計(jì)算量顯著減低,。該性能優(yōu)化可能使計(jì)算出來(lái)的相似度系統(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)問(wèn)題探析[J].中國(guó)集成電路，2010(11)：87-91.

[3] 郭禾.中國(guó)集成電路布圖設(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].中國(guó)人民大學(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].北京：中國(guó)科學(xué)技術(shù)出版社,，2011.

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

[10] 吳漢東.中國(guó)知識(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].長(zhǎng)沙：湖南師范大學(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ù)條例.國(guó)務(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ì)則.國(guó)家知識(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)