軟件抄襲檢測(cè)研究綜述

田振洲, 劉 烴, 鄭慶華, 佟菲菲, 吳定豪, 朱森存,, 陳 愷

1西安交通大學(xué) 智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點(diǎn)實(shí)驗(yàn)室 西安 中國(guó) 7100492賓夕法尼亞州立大學(xué)帕克分校 計(jì)算機(jī)科學(xué)與工程系 美國(guó) 168023賓夕法尼亞州立大學(xué)帕克分校 信息科學(xué)與技術(shù)學(xué)院 美國(guó) 168024中國(guó)科學(xué)院信息工程研究所 北京 中國(guó)100093

軟件抄襲檢測(cè)研究綜述

田振洲1, 劉 烴1, 鄭慶華1, 佟菲菲1, 吳定豪2, 朱森存2,3, 陳 愷4

1西安交通大學(xué) 智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點(diǎn)實(shí)驗(yàn)室 西安 中國(guó) 7100492賓夕法尼亞州立大學(xué)帕克分校 計(jì)算機(jī)科學(xué)與工程系 美國(guó) 168023賓夕法尼亞州立大學(xué)帕克分校 信息科學(xué)與技術(shù)學(xué)院 美國(guó) 168024中國(guó)科學(xué)院信息工程研究所 北京 中國(guó)100093

隨著開源軟件項(xiàng)目的蓬勃發(fā)展, 軟件抄襲儼然已成為軟件生態(tài)環(huán)境健康發(fā)展的威脅之一, 其得到越來越多的研究人員、教育人員、開源社區(qū)及軟件企業(yè)的關(guān)注, 軟件抄襲檢測(cè)對(duì)于軟件知識(shí)產(chǎn)權(quán)保護(hù)具有重要意義。本文對(duì)軟件抄襲檢測(cè)的研究現(xiàn)狀和進(jìn)展進(jìn)行綜述。首先介紹軟件抄襲檢測(cè)的意義和威脅模型; 然后, 根據(jù)應(yīng)用場(chǎng)景和技術(shù)手段, 從源代碼抄襲檢測(cè)、無源碼場(chǎng)景下基于軟件水印和基于軟件胎記的抄襲檢測(cè)三個(gè)方面, 對(duì)現(xiàn)有軟件抄襲檢測(cè)技術(shù)進(jìn)行闡述和比較; 最后, 通過分析軟件抄襲檢測(cè)研究存在的問題及其面臨的挑戰(zhàn)和實(shí)際需求, 對(duì)未來研究方向進(jìn)行了展望。

知識(shí)產(chǎn)權(quán)保護(hù); 軟件保護(hù); 軟件抄襲; 軟件抄襲檢測(cè); 軟件胎記; 代碼相似性分析; 軟件水印; 代碼混淆

1 引言

軟件抄襲是一種為達(dá)到特定目的而非法拷貝并使用他人代碼的行為, 從學(xué)生上機(jī)作業(yè)的抄襲到軟件產(chǎn)品的抄襲、移動(dòng)端App的重打包, 都屬于軟件抄襲的范疇。軟件抄襲在教育界一直飽為詬病, 學(xué)生上機(jī)作業(yè)的抄襲非常普遍, 這嚴(yán)重影響學(xué)生能力的培養(yǎng)和計(jì)算機(jī)教學(xué)的效果。國(guó)外最近的一項(xiàng)調(diào)研中約有33%學(xué)生承認(rèn)曾經(jīng)抄襲[1]; 另一項(xiàng)研究中, 教學(xué)人員對(duì)學(xué)生從1993到2006年的4門編程作業(yè)進(jìn)行分析,發(fā)現(xiàn)1%-10%比例的抄襲, 而且呈逐年增長(zhǎng)趨勢(shì)[2];另外, MOSS(一款軟件抄襲檢測(cè)服務(wù))的統(tǒng)計(jì)結(jié)果顯示, 提交其檢測(cè)的所有學(xué)生作業(yè)都會(huì)有10%左右的抄襲比例, 而且這還是在學(xué)生提前被告知其上機(jī)作業(yè)會(huì)被檢查的情況下的結(jié)果[3]。

近些年, 軟件抄襲也已成為正規(guī)的軟件公司和開源軟件組織所迫切關(guān)心的問題, 其對(duì)軟件知識(shí)產(chǎn)權(quán)的保護(hù)構(gòu)成了嚴(yán)重威脅?，F(xiàn)在有非常多的開源軟件項(xiàng)目和社區(qū), 比如SourceForge.net上有43萬個(gè)開源項(xiàng)目, 平均每天有高于480萬的下載量。開源項(xiàng)目的蓬勃發(fā)展一方面促進(jìn)了軟件行業(yè)的繁榮, 同時(shí)也給不法的抄襲者提供了更多以及更便捷的抄襲他人代碼的機(jī)會(huì), 因?yàn)樵创a相比可執(zhí)行的二進(jìn)制代碼而言更容易理解和修改, 抄襲者還可能會(huì)利用自動(dòng)化的混淆工具進(jìn)行簡(jiǎn)單包裝來盜用全部代碼。通常這些開源項(xiàng)目允許用戶在遵守特定的License(如眾所周知的GPL、BSD等)的前提下使用、修改以及對(duì)其進(jìn)行重新發(fā)布, 然而受經(jīng)濟(jì)利益的驅(qū)使, 有些軟件公司或個(gè)人會(huì)在其產(chǎn)品中集成第三方代碼而不遵守相應(yīng)的License。另外, 很多下游公司會(huì)將其軟件項(xiàng)目的部分功能模塊外包給上游小公司, 通常這些模塊會(huì)以二進(jìn)制代碼的形式交付, 上游公司無從得知這些模塊是否存在抄襲的情況。這些有意或無意的抄襲也導(dǎo)致了很多案件的發(fā)生[4,5], 比如電信巨頭Verzion曾因在其FIOS無線路由器中使用Busybox的代碼而被自由軟件基金會(huì)起訴, 而問題模塊是Actiontec Electronics交付的; 再比如Skype曾因違背Joltid的條款險(xiǎn)些被迫終止其voice-over-IP服務(wù)。

此外, 隨著智能手機(jī)的普及和手機(jī)應(yīng)用的涌現(xiàn),移動(dòng)端App的抄襲問題也得到工業(yè)界和學(xué)術(shù)界越來越多的重視[6]。抄襲者通過重打包(將App進(jìn)行拆卸,對(duì)其代碼、數(shù)據(jù)等進(jìn)行增刪改或不進(jìn)行任何改動(dòng), 然后重新組裝打包成新App的行為)修改軟件的擁有者、植入廣告達(dá)到非法獲取經(jīng)濟(jì)利益的目的。研究者對(duì)多個(gè)第三方App市場(chǎng)的研究表明, 5%-13%的App是重打包發(fā)布而來的[7]; 甚至Google Play自身中有1.2%的App是重打包的[8]。此外, 通過重打包植入惡意payloads可以快速生成并傳播大量惡意軟件, 對(duì)App市場(chǎng)生態(tài)環(huán)境構(gòu)成嚴(yán)重威脅。最近一項(xiàng)研究顯示[8], 來自33個(gè)Android市場(chǎng)共計(jì)120萬個(gè)App中有10.93%是可疑的, 即使Google Play中也有7.61%的應(yīng)用是惡意的, 而且其中有些應(yīng)用已被安裝100萬次以上; 另一項(xiàng)研究表明[7], Android惡意軟件中約有86%是通過對(duì)合法軟件進(jìn)行重打包而來的。

軟件抄襲檢測(cè)的研究工作已經(jīng)有40多年歷史,最初研究主要集中在學(xué)生上機(jī)作業(yè)的抄襲檢測(cè), 應(yīng)用在源碼存在這種場(chǎng)景; 后來隨著工業(yè)界對(duì)軟件知識(shí)產(chǎn)權(quán)保護(hù)的重視, 很大一部分關(guān)注點(diǎn)轉(zhuǎn)移到商業(yè)產(chǎn)品的抄襲檢測(cè)上, 提出了基于軟件水印和軟件胎記的檢測(cè)方法, 這些方法可用于源碼不存在的場(chǎng)景;后來隨著手機(jī)應(yīng)用市場(chǎng)的繁榮, 移動(dòng)應(yīng)用的抄襲檢測(cè)研究也獲得越來越多的關(guān)注, 主要還是結(jié)合手機(jī)應(yīng)用的自身特點(diǎn), 利用軟件水印或軟件胎記技術(shù)實(shí)現(xiàn)抄襲檢測(cè)。

軟件抄襲檢測(cè)的研究成果也在許多頂級(jí)的國(guó)際會(huì)議和期刊上進(jìn)行了發(fā)表, 如ICSE會(huì)議[9,10]、CCS會(huì)議[11]、FSE會(huì)議[12]、ASE會(huì)議[13,14]、POPL會(huì)議[15]、ACSAC會(huì)議[16,17]、ISSTA會(huì)議[18,19]、TSE期刊[20-22]、TOC期刊[23,24]、KDD會(huì)議[25,26]、TIFS期刊[27]等。目前并沒有系統(tǒng)性的工作對(duì)軟件抄襲檢測(cè)技術(shù)進(jìn)行綜述, 比較相關(guān)的是2010年發(fā)表在《計(jì)算機(jī)科學(xué)》上熊浩等關(guān)于代碼相似性檢測(cè)技術(shù)的綜述[28]以及2003年發(fā)表在《軟件學(xué)報(bào)》上張立和等關(guān)于軟件水印的綜述[87]。前者僅對(duì)源碼存在情況下的抄襲檢測(cè)技術(shù)進(jìn)行了總結(jié); 后者介紹了當(dāng)時(shí)的幾種水印技術(shù)和水印的攻擊方法, 而至今水印技術(shù)已取得非常多的進(jìn)展, 需要重新歸納總結(jié)。本文綜述了軟件抄襲檢測(cè)研究的最新進(jìn)展, 不僅囊括了最新的源碼抄襲檢測(cè)技術(shù)和軟件水印技術(shù), 還對(duì)軟件胎記這類主流技術(shù)進(jìn)行了歸納, 同時(shí)介紹了移動(dòng)端抄襲檢測(cè)的研究進(jìn)展, 全面比較和分析了不同技術(shù)的優(yōu)缺點(diǎn)及適用場(chǎng)景, 并結(jié)合我們自身在這方面的研究基礎(chǔ)對(duì)未來的研究方向和面臨的挑戰(zhàn)進(jìn)行了探討。

本文結(jié)構(gòu)如下: 第2節(jié)對(duì)軟件抄襲檢測(cè)的一些關(guān)鍵問題進(jìn)行介紹, 包括對(duì)抄襲問題的描述、威脅模型以及抄襲檢測(cè)技術(shù)的歸類法; 第3節(jié)介紹針對(duì)源碼的抄襲檢測(cè)技術(shù); 第4節(jié)和第5節(jié)分別介紹了無源碼場(chǎng)景下基于軟件水印和軟件胎記的抄襲檢測(cè)技術(shù);第6節(jié)探討抄襲檢測(cè)研究的一些新問題、面臨的挑戰(zhàn)和未來的研究方向; 最后總結(jié)全文。

2 軟件抄襲檢測(cè)的關(guān)鍵問題

2.1 理解軟件抄襲和抄襲檢測(cè)

對(duì)于軟件抄襲, 各個(gè)領(lǐng)域有不同的定義。綜合其他文獻(xiàn)的描述, 廣義而言本文將其描述為一種非法使用他人軟件的各種基本要素的行為, 其中非法是指未得到軟件擁有者的允許或未能遵守既定的條款規(guī)約, 軟件基本要素包括軟件代碼、設(shè)計(jì)思想、用戶界面、軟件文檔、輸入數(shù)據(jù)等, 這種行為可以是有意的也可以的無意的。這樣的描述相當(dāng)寬泛, 簡(jiǎn)單的軟件拷貝再發(fā)布屬于抄襲, 花費(fèi)大量時(shí)間和精力逆向分析出他人代碼的核心思想然后用其他語言實(shí)現(xiàn)也屬于抄襲, 而且很多時(shí)候抄襲與否難以界定。2012年的一項(xiàng)研究顯示[1], 大學(xué)教學(xué)人員和學(xué)生對(duì)軟件抄襲的界定就存在很大差異, 比如76%的教學(xué)人員認(rèn)為用戶界面的抄襲屬于軟件抄襲, 而僅有53%的學(xué)生持相同觀點(diǎn)。

鑒于此, 本文對(duì)要解決的抄襲問題進(jìn)行限定,將其定義為攻擊者(抄襲者)在對(duì)軟件沒有任何或很少了解的情況下花費(fèi)很少的精力對(duì)軟件代碼實(shí)施的抄襲; 也就說抄襲者不會(huì)花時(shí)間破解或理解代碼,甚至完全沒有任何代碼知識(shí), 而是通過專業(yè)工具或者很少的人工修改實(shí)施抄襲, 這也是目前研究人員關(guān)注的抄襲問題。為了準(zhǔn)確描述本文討論的軟件抄襲(如無特別說明, 下文的軟件抄襲均限定在此范疇,不再贅述), 下面給出其形式化定義。

定義1. 軟件抄襲。對(duì)于兩個(gè)程序P和Q, 只要滿足以下任一條件, 就說Q抄襲了P:

C1)Q是P的直接拷貝;

C2)Q是攻擊者通過對(duì)P應(yīng)用語義保留的代碼變換T(如標(biāo)識(shí)符修改、優(yōu)化、混淆)生成的;

C3)Q集成了程序P的所有代碼;

C4)Q集成了程序P的部分代碼;

C5)Q是通過對(duì)P反復(fù)應(yīng)用上述修改得來的。

定義1描述了攻擊者實(shí)施軟件抄襲的手段。C1最為直觀, 攻擊者對(duì)整個(gè)軟件實(shí)施完整的拷貝, 通過直接發(fā)布或簡(jiǎn)單修改軟件所有者信息后再發(fā)布的方式完成抄襲, 這種方式實(shí)施的抄襲非常普遍同時(shí)相較其他方式也更易檢測(cè)。C2是攻擊者利用自動(dòng)化的代碼變換技術(shù)(如采用不同的編譯器及編譯優(yōu)化選項(xiàng)、單獨(dú)的優(yōu)化器、各種混淆工具、加殼工具等)或者較少的人工修改(如修改標(biāo)識(shí)符、增減注釋、代碼重布局等), 可以說目前絕大部分的檢測(cè)技術(shù)都是針對(duì)這種抄襲方式的。C3是攻擊者在原程序P(為方便描述, 下文將原程序P稱為原告, 將抄襲生成的程序Q稱為被告)的基礎(chǔ)上通過添加新的功能模塊來實(shí)施抄襲, 這種抄襲方式在Android平臺(tái)最為常見, 攻擊者從市場(chǎng)抓取已發(fā)布的原告P, 通過重打包技術(shù)在P中植入廣告或惡意模塊, 然后再次發(fā)布到該應(yīng)用市場(chǎng)或其他市場(chǎng)。C4是攻擊者只是利用原告P的部分代碼(如某個(gè)功能庫(kù)), 在此基礎(chǔ)上進(jìn)行再次開發(fā)的方式, 有可能被告Q中只包含P很小一部分代碼。C5是綜合運(yùn)用C1-C4的手段實(shí)施的抄襲, 比如Android平臺(tái)App的抄襲, 攻擊者可以在重打包植入惡意代碼的同時(shí)對(duì)原代碼及惡意代碼實(shí)施混淆, 進(jìn)一步使被告Q與原告P的區(qū)別增大。此外, 很多情況下被告Q的源代碼是無法獲取的, 攻擊者為躲避檢測(cè), 其抄襲生成的程序Q通常會(huì)以二進(jìn)制或Java字節(jié)碼等形式發(fā)布, 這使得軟件抄襲檢測(cè)難度大大增加, 因?yàn)榭蓤?zhí)行程序的分析要比源代碼分析難得多。

因此, 軟件抄襲檢測(cè)需要解決以下幾個(gè)關(guān)鍵問題:

1) 如何實(shí)現(xiàn)檢測(cè)過程的自動(dòng)化或較少的人工參與;

2) 源碼缺失情況下, 如何開展分析;

3) 如何應(yīng)對(duì)各式各樣的代碼混淆技術(shù);

4) 如何解決部分抄襲檢測(cè)的問題。

目前的軟件抄襲檢測(cè)研究都以自動(dòng)化檢測(cè)為目標(biāo), 提出了很多以二進(jìn)制代碼為分析對(duì)象的動(dòng)靜態(tài)檢測(cè)技術(shù), 同時(shí)通過融合語義分析也提出了不少對(duì)代碼混淆具備很好抵抗力的方法。然而對(duì)于部分抄襲, 盡管這類問題在實(shí)際情況下非常普遍, 但因?yàn)楦鄷r(shí)候需要人為參與審查, 而研究者主要還是關(guān)注自動(dòng)化的檢測(cè)技術(shù), 因此目前的研究涉及極少,這也是軟件抄襲檢測(cè)亟待解決的關(guān)鍵問題。

2.2 代碼混淆

軟件抄襲屬于主機(jī)攻擊(host attack)范疇, 也就是在不計(jì)代價(jià)和開銷的情況下, 抄襲者可以利用任何當(dāng)下可行的技術(shù)和計(jì)算資源達(dá)到抄襲的目的; 因而, 實(shí)現(xiàn)軟件抄襲的手段不勝枚舉。下面著重介紹一下通過代碼混淆實(shí)現(xiàn)抄襲的手段, 也是目前幾乎所有抄襲檢測(cè)研究關(guān)注的重點(diǎn)。

代碼混淆是通過的特定代碼變換手段將程序P轉(zhuǎn)換成另一個(gè)程序P’的一種技術(shù), 并且P與P’至少在可觀測(cè)行為上保持語義等價(jià), 其目的是有意地隱藏程序邏輯, 使混淆后的程序P’更加難以理解和分析。代碼混淆被廣泛用于增加逆向分析的難度, 保護(hù)核心代碼; 但類似于惡意軟件制造者用其隱藏惡意代碼, 抄襲者同樣利用代碼混淆來隱藏抄襲的意圖,加大分析難度以躲避檢測(cè)。

代碼混淆可以在源代碼、字節(jié)碼或者機(jī)器碼上進(jìn)行, 通過人工或采用自動(dòng)化的混淆器實(shí)現(xiàn), 后者需要實(shí)現(xiàn)特定的代碼混淆技術(shù), 但比人工混淆能夠產(chǎn)生更不容易出錯(cuò)同時(shí)更加晦澀難懂的代碼。簡(jiǎn)單而言, 可以將現(xiàn)有的混淆技術(shù)分為外形混淆、控制混淆、數(shù)據(jù)混淆三類。

外形混淆主要通過詞法變換手段, 如標(biāo)識(shí)符重命名、注釋刪除、格式及布局調(diào)整等, 降低代碼的可讀性; 此類混淆技術(shù)實(shí)現(xiàn)容易, 同時(shí)不會(huì)給程序帶來額外開銷, 但混淆程度較弱, 僅可以對(duì)抗部分基于文本和詞法分析的檢測(cè)技術(shù)。控制混淆是通過改變程序的控制流結(jié)構(gòu)進(jìn)行的代碼變換, 如代碼內(nèi)聯(lián)和外聯(lián)、循環(huán)條件擴(kuò)充、基于不透明謂詞的死碼及垃圾代碼植入、控制流扁平化等; 控制混淆會(huì)對(duì)程序的控制流結(jié)構(gòu)造成較大改變, 因而基于控制流分析的某些檢測(cè)技術(shù)可能會(huì)失效。數(shù)據(jù)混淆是對(duì)程序的數(shù)據(jù)結(jié)構(gòu)進(jìn)行改變的代碼變換, 常采用的手段包括變量分割、參數(shù)重排、標(biāo)量合并、數(shù)組重構(gòu)等; 數(shù)據(jù)混淆會(huì)影響數(shù)據(jù)的存儲(chǔ)、編碼等, 因而會(huì)干擾單純基于數(shù)據(jù)流分析的抄襲檢測(cè)技術(shù)。

現(xiàn)有代碼混淆工具也有很多, 典型的如Sandmark[29]、ZelixKlassmaster[30]、DashO[31]、DexGuard[32]、Loco[33]、Upx[34]、ProGuard[35]等。代碼混淆技術(shù)本身是一個(gè)非?；钴S也很重要的研究話題, 這里不再做深入探討, 感興趣的讀者可參閱文獻(xiàn)[21, 36-38]。

2.3 軟件抄襲檢測(cè)技術(shù)分類

本文按照應(yīng)用場(chǎng)景和技術(shù)手段的不同, 將現(xiàn)有的軟件抄襲檢測(cè)方法歸為三類: 源碼抄襲檢測(cè)技術(shù)、基于軟件水印的抄襲檢測(cè)技術(shù)以及基于軟件胎記的抄襲檢測(cè)技術(shù)。

2.3.1 源碼抄襲檢測(cè)技術(shù)

這類抄襲檢測(cè)技術(shù)適用于被告源碼能夠獲取的場(chǎng)景, 其通過衡量原告與被告源代碼的相似性來判斷是否存在抄襲。通常這類技術(shù)是將代碼當(dāng)做純文本進(jìn)行分析或者采用簡(jiǎn)單的詞法語法分析, 很少涉及語義分析, 因而抗混淆能力較弱。不過在特定的場(chǎng)景, 如學(xué)生上機(jī)作業(yè)的抄襲檢測(cè), 大多數(shù)情況下學(xué)生是采用直接地人工修改(如修改變量名、操作符變換等)的方式實(shí)現(xiàn)抄襲, 抄襲手段不會(huì)太復(fù)雜, 因而也出現(xiàn)了不少實(shí)用的檢測(cè)工具諸如MOSS[39]、JPlag[40]、Sherlock[41]等, 并在不少國(guó)外高校得到推廣應(yīng)用。

2.3.2 基于軟件水印的抄襲檢測(cè)技術(shù)

很多情況下被告的源碼是無法獲取的, 特別是商業(yè)軟件的抄襲, 被告通常以可執(zhí)行文件的形式發(fā)布, 在搜集到足夠證據(jù)之前, 抄襲者不太可能給出其源碼。軟件水印技術(shù)就是針對(duì)這種情況設(shè)計(jì)的, 并被很多軟件公司所采用。該類技術(shù)的基本原理是在軟件發(fā)布之前, 在代碼中植入一個(gè)特殊的標(biāo)識(shí)符(水印), 來標(biāo)識(shí)軟件的所有者; 該水印事后可以通過特殊的提取器被識(shí)別或抽取出來, 其可以作為證據(jù)達(dá)到檢測(cè)的目的。因?yàn)檫@類技術(shù)需要在代碼中植入額外的數(shù)據(jù)(或代碼), 水印算法過于復(fù)雜會(huì)影響程序的性能和穩(wěn)定性, 過于簡(jiǎn)單又影響其隱蔽性, 因此在設(shè)計(jì)水印算法時(shí)需要綜合考量其性能、花銷、隱蔽性、抗毀性等。

2.3.3 基于軟件胎記的抄襲檢測(cè)技術(shù)

不管是靜態(tài)還是動(dòng)態(tài)的軟件水印技術(shù), 都較容易被語義保留的代碼混淆破壞掉, 研究者進(jìn)一步提出了軟件胎記方法。不同于水印技術(shù), 軟件胎記技術(shù)是靜態(tài)或動(dòng)態(tài)地從軟件中抽取出一些不易改變的特征(胎記), 這些特征可以唯一地對(duì)該軟件進(jìn)行標(biāo)識(shí),然后基于胎記的相似性判斷抄襲是否存在。由于不需要事先植入額外信息, 胎記技術(shù)不會(huì)對(duì)程序引入額外的負(fù)載; 然而該類技術(shù)的檢測(cè)效果很大程度上依賴于高質(zhì)量的軟件胎記的抽取, 軟件胎記越貼近程序語義檢測(cè)效果越好。已有的研究表明, 融合了語義分析的軟件胎記技術(shù)特別是動(dòng)態(tài)胎記技術(shù)對(duì)代碼混淆具備非常好的抵抗力。

3 源碼抄襲檢測(cè)技術(shù)

提及源碼抄襲檢測(cè), 人們最容易聯(lián)想到同時(shí)也容易混為一談的是代碼克隆檢測(cè)問題, 盡管克隆和抄襲都會(huì)產(chǎn)生高度相似的代碼, 但二者有著本質(zhì)不同。

首先, 目的和基本假設(shè)不完全一致: 代碼克隆之所以產(chǎn)生是因?yàn)榇a本身不可以或不方便直接重用, 比如難以滿足程序員想要的功能, 需要稍微修改, 克隆代碼的行為與原代碼完全一致或略有差異,并且程序員需要理解被克隆代碼片段的語義行為;而抄襲則是攻擊者為了獲取個(gè)人利益, 其通常是在不理解代碼的前提下, 企圖對(duì)代碼進(jìn)行大量以及各種各樣的轉(zhuǎn)換、偽裝以減少被檢測(cè)的可能性, 同時(shí)要盡可能保證程序語義不被改變, 因?yàn)槭怯幸獾膫窝b,其比代碼克隆更難檢測(cè)。

其次, 克隆和抄襲所產(chǎn)生的相似代碼的尺寸不同: 克隆片段通常較小, 而抄襲代碼則通常是原代碼的大規(guī)?；蛉恐赜? 同時(shí), 克隆檢測(cè)旨在實(shí)現(xiàn)軟件自身代碼重復(fù)片段的檢測(cè), 返回的是大量候選克隆片段, 而抄襲檢測(cè)則是軟件間的相似性比較,其要給出軟件抄襲與否的判定。

再次, 克隆檢測(cè)和抄襲檢測(cè)的關(guān)注點(diǎn)也不一致:克隆檢測(cè)更重視準(zhǔn)確率, 因?yàn)樘嗟恼`報(bào)會(huì)引入過多的候選, 時(shí)間及人力開銷不允許; 而抄襲檢測(cè)更看重召回率, 特別是對(duì)于商業(yè)軟件而言, 法律訴訟過程漫長(zhǎng), 證據(jù)收集的越全面越好。

當(dāng)然, 克隆檢測(cè)和源碼抄襲檢測(cè)之間也存在一定關(guān)聯(lián), 有研究[42-45]將克隆檢測(cè)技術(shù)進(jìn)行擴(kuò)展用于抄襲檢測(cè), 但通常需要引入深層次的轉(zhuǎn)換和歸一化處理, 這容易導(dǎo)致過多的誤報(bào), 比如CCFinder[43]曾用于代碼抄襲檢測(cè), 但其實(shí)際效果還需進(jìn)一步驗(yàn)證。

源碼抄襲檢測(cè)技術(shù)成功應(yīng)用的前提是被告源碼可獲取, 而很多情況下如商業(yè)軟件的源碼是不公開的, 所以源碼抄襲檢測(cè)研究的一個(gè)典型應(yīng)用場(chǎng)景是高校學(xué)生上機(jī)作業(yè)的抄襲。由于學(xué)生群體的特殊性,這類抄襲通常是以人工修改方式來實(shí)現(xiàn), 而且通常不會(huì)進(jìn)行大量復(fù)雜的修改。一般來講, 抄襲手段限定在詞法、語法、語義三方面的變換, 而且大部分學(xué)生作業(yè)的抄襲集中在前兩種[46-48]。源碼抄襲檢測(cè)技術(shù)由于語義分析的復(fù)雜性, 同時(shí)考慮到效率問題(通常要分析上千份的編程作業(yè)), 很少涉及語義分析, 學(xué)生作業(yè)抄襲手段簡(jiǎn)單直接的特點(diǎn)使得源碼抄襲檢測(cè)技術(shù)在這類抄襲問題上得到了普遍應(yīng)用。

簡(jiǎn)單而言, 源碼抄襲檢測(cè)技術(shù)通過匹配相似代碼判定抄襲, 其將程序代碼當(dāng)做純文本分析或?qū)Υa采用簡(jiǎn)單的詞法、語法分析, 為方便相似匹配同時(shí)提高檢測(cè)效果, 通常還會(huì)對(duì)代碼進(jìn)行抽象。依據(jù)抽象方式的不同, 本文將現(xiàn)有的源碼抄襲檢測(cè)技術(shù)分為基于屬性統(tǒng)計(jì)和基于結(jié)構(gòu)分析兩大類。

3.1 基于屬性統(tǒng)計(jì)的抄襲檢測(cè)

基于屬性統(tǒng)計(jì)(Attribute-Counting)的抄襲檢測(cè)[49]是最早一批出現(xiàn)的檢測(cè)方法, 其基本思想是通過對(duì)軟件代碼的各項(xiàng)度量指標(biāo)進(jìn)行統(tǒng)計(jì), 將軟件轉(zhuǎn)換成一個(gè)n維向量, 每個(gè)維度指定了軟件的一項(xiàng)度量指標(biāo), 從而將其映射成n維笛卡爾空間中的一個(gè)點(diǎn), 最后基于該空間中不同點(diǎn)(軟件)間的距離實(shí)現(xiàn)抄襲的判定。

最初的方法[50]只使用了基本的Halstead度量指標(biāo)[51,52], 包括不同操作符個(gè)數(shù)n1、不同操作數(shù)個(gè)數(shù)n2、操作符總數(shù)N1和操作數(shù)總數(shù)N2四個(gè)度量指標(biāo),從而將程序P抽象成一個(gè)四元組(n1, n2, N1, N2), 并且當(dāng)且僅當(dāng)兩個(gè)程序的四元組一致的時(shí)候才認(rèn)為它們存在抄襲。顯然這種方法會(huì)產(chǎn)生很多漏報(bào), 為此后續(xù)工作[48,53-55]中引入了更多的度量指標(biāo), 同時(shí)加入了對(duì)于度量指標(biāo)相似性的衡量, 以期待有更好的檢測(cè)效果。Grier等[54]在分析Fortran程序時(shí)引入了變量總數(shù)、輸入語句、條件語句、循環(huán)語句、賦值語句及調(diào)用個(gè)數(shù)等度量指標(biāo); Faidhi等[48]引入了一個(gè)含有23個(gè)不同度量指標(biāo)的最小集, 這些度量指標(biāo)間不存在任何關(guān)聯(lián), 所用指標(biāo)包括平均標(biāo)識(shí)符長(zhǎng)度、保留字個(gè)數(shù)、條件語句比例, 以及更復(fù)雜的結(jié)構(gòu)性指標(biāo)如McCabe圈復(fù)雜度、扇入扇出系數(shù)等。然而這些努力收效甚微, 屬性統(tǒng)計(jì)的檢測(cè)方法因是對(duì)整個(gè)軟件的度量, 其抽象過程拋棄了太多的軟件結(jié)構(gòu)信息, 單純地增加屬性的維度并不會(huì)有實(shí)質(zhì)性的提升[56], 所以這樣的檢測(cè)系統(tǒng)要么非常不靈敏要么過度靈敏,會(huì)存在很多的漏報(bào)和誤報(bào), 簡(jiǎn)單的代碼混淆就可以躲避檢測(cè)。

此外, 也有一些研究[57-61]通過使用其他領(lǐng)域(如數(shù)據(jù)挖掘、人工智能)的技術(shù)或結(jié)合其他抄襲檢測(cè)技術(shù)來加強(qiáng)基于屬性統(tǒng)計(jì)的抄襲檢測(cè)方法的效果。Moussiades等[58]利用學(xué)生編程作業(yè)抄襲時(shí)呈現(xiàn)出簇的特點(diǎn), 提出使用聚類方法來改善基于屬性統(tǒng)計(jì)的抄襲檢測(cè)效果。他們首先使用傳統(tǒng)的基于屬性統(tǒng)計(jì)的檢測(cè)方法計(jì)算程序的兩兩相似性, 并基于一個(gè)閾值給出抄襲與否的判定, 存在抄襲的兩個(gè)程序形成一個(gè)抄襲對(duì); 然后將所有的抄襲對(duì)轉(zhuǎn)換成一個(gè)無向帶權(quán)圖, 圖中頂點(diǎn)代表每一個(gè)程序, 邊代表程序間的相似性; 最后通過聚類識(shí)別出抄襲簇, 原本看似無聯(lián)系的兩個(gè)程序聚類后有可能會(huì)劃歸到同一個(gè)簇中, 從而檢測(cè)潛在的抄襲。Plague Doctor[57]采用群體學(xué)習(xí)的思想, 在軟件度量指標(biāo)基礎(chǔ)上將其他檢測(cè)技術(shù)(如將要提到的基于token的檢測(cè)方法)的分析結(jié)果考慮進(jìn)來, 將它們作為BP神經(jīng)網(wǎng)絡(luò)的輸入訓(xùn)練分類器達(dá)到檢測(cè)的目的。但該方法限定條件較多, 如需要專業(yè)人員事先標(biāo)定大量的訓(xùn)練數(shù)據(jù), 且存在數(shù)據(jù)稀疏性問題。

3.2 基于結(jié)構(gòu)分析的抄襲檢測(cè)

軟件結(jié)構(gòu)分析需要將代碼結(jié)構(gòu)用其他可比較的形式表達(dá)出來, 依據(jù)表達(dá)形式的不同, 將其分為基于token、基于樹和基于圖的檢測(cè)方法來總結(jié)。這類技術(shù)相比基于屬性統(tǒng)計(jì)的檢測(cè)方法而言檢測(cè)效果更好, 也出現(xiàn)很多實(shí)用的檢測(cè)工具[39-41]。

3.2.1 基于token的檢測(cè)

這類方法是將軟件代碼轉(zhuǎn)換成一系列token, 然后通過token比較衡量代碼相似性。token可以是編程語言無關(guān)的字符串, 也可以是編程語言中的基本元素。

前者是將程序代碼當(dāng)做文本進(jìn)行分析, 典型代表是MOSS(Measure of Software Similarity)[39]工具。它利用字符串匹配算法將程序代碼劃分為一系列k-gram, 每個(gè)k-gram是一個(gè)長(zhǎng)度為k的子串(也就是token); 然后對(duì)每個(gè)k-gram進(jìn)行Hash運(yùn)算, 通過Winnowing算法篩選出部分Hash值作為程序指紋,兩個(gè)程序共享的指紋越多就越有可能存在抄襲。Brixtel等[42]提出分段思想將代碼首先按行進(jìn)行切分,構(gòu)建兩個(gè)程序文檔的段相似性矩陣, 然后用Munkres算法查找段相似性的最大匹配以構(gòu)建匹配矩陣, 最后通過計(jì)算文檔間距離來衡量相似性。不同于MOSS和Brixtel對(duì)程序代碼進(jìn)行兩兩比較的方法, Cosma等[23]將一批程序作為分析對(duì)象, 他們基于所有代碼文件構(gòu)建項(xiàng)-文檔矩陣, 其中項(xiàng)是在從代碼文件中構(gòu)造的一系列token, 然后利用LSA(Latent Semantic Analysis)計(jì)算文檔間的相似性以實(shí)現(xiàn)抄襲檢測(cè); 此外, 他們還提出PGQT, 將代碼段轉(zhuǎn)換為token序列后構(gòu)造查詢, 計(jì)算該代碼段與項(xiàng)-文檔矩陣中所有文檔的相似性, 進(jìn)而依據(jù)相似性的分布規(guī)律, 評(píng)估該代碼段作為抄襲證據(jù)的貢獻(xiàn)度。將程序當(dāng)做文本分析的一個(gè)好處是不受制于分析對(duì)象所使用的編程語言, 但也正因?yàn)槠錄]有考慮代碼的語言特性, 這類方法對(duì)代碼混淆的抵抗力普遍較弱。

另一類技術(shù)[43,62-64]在對(duì)代碼token化時(shí)考慮了編程語言的基本特性, 其基本思路是對(duì)代碼進(jìn)行詞法掃描構(gòu)建token字串, 然后通過token字串的比較決定程序?qū)Φ南嗨菩浴＿@類方法的關(guān)鍵在于token的選擇和比較算法的設(shè)計(jì), 篩選的token應(yīng)當(dāng)盡可能不太容易被簡(jiǎn)單的代碼混淆破壞掉。YAP3[65]將程序轉(zhuǎn)換成token字串, 并使用RKR-GST(Running-Karp -Rabin Greedy-String-Tilling)[66]字串匹配算法實(shí)現(xiàn)token字串的最大非重疊匹配; 為提高應(yīng)對(duì)代碼混淆的能力, 其在token化時(shí)采取了一系列優(yōu)化, 包括移除字符串常量和注釋、將字符全部轉(zhuǎn)為小寫、將函數(shù)映射成等價(jià)形式(比如strncmp統(tǒng)一為strcmp)等。Sim[67]通過flex詞法分析器, 將程序解析成token序列, 然后應(yīng)用字串對(duì)齊算法并設(shè)計(jì)對(duì)齊得分機(jī)制實(shí)現(xiàn)相似性計(jì)算; 其token由預(yù)定義的關(guān)鍵字、特殊符號(hào)以及動(dòng)態(tài)指定的標(biāo)識(shí)符組成, token流的對(duì)齊采用分段思想按程序模塊實(shí)施。JPlag[68]是另一款比較著名的檢測(cè)系統(tǒng), 其使用了與YAP3同樣的字串匹配算法, 但與前兩者不同其被設(shè)計(jì)成基于web服務(wù)的檢測(cè)系統(tǒng)。此外, 為減少偶然相似, JPlag會(huì)將特定的程序結(jié)構(gòu)轉(zhuǎn)換成token, 比如其使用“BEGIN_METHOD”這個(gè)token表示一個(gè)方法的開始大括號(hào), 而用“OPEN_ BRACE”表示其他的開始大括號(hào)。

JPlag等需要針對(duì)每門編程語言單獨(dú)設(shè)計(jì)前端以實(shí)現(xiàn)代碼的解析和token化, 為此有研究[69-71]將代碼轉(zhuǎn)換成中間代碼再進(jìn)行分析。XPlag[69]利用GCC編譯套件將軟件代碼轉(zhuǎn)換成RTL(Register Transfer Language)中間代碼, 在中間代碼上進(jìn)行token化; 同時(shí)為提高檢測(cè)效率, 其將所有代碼token化后應(yīng)用倒排索引實(shí)現(xiàn)token信息的存儲(chǔ), 并通過構(gòu)造查詢, 利用搜索引擎查找最相似的程序; 此外不同的編程語言轉(zhuǎn)換成中間代碼后會(huì)具有相同形式, 其在Java和C程序上的實(shí)驗(yàn)初步表明XPlag可以檢測(cè)跨語言的抄襲。該方法很大程度上依賴于編譯套件的可靠性,同時(shí)跨語言抄襲檢測(cè)也主要在小部分Java和C程序上進(jìn)行了驗(yàn)證, 其實(shí)用性有待進(jìn)一步研究。

對(duì)于token流的比較, 除了普遍采用的字符串匹配、比較或?qū)R算法外, 也有研究[59,61,72,73]結(jié)合其他領(lǐng)域知識(shí)實(shí)現(xiàn)token流相似性的衡量。Chen等[72]從信息論的角度, 提出一項(xiàng)具有Kolmogorov復(fù)雜度[74]的普適性距離度量指標(biāo)來衡量?jī)蓚€(gè)token流的信息共享量, 并基于歸一化后的信息共享量判定抄襲。而Kolmogorov復(fù)雜度具有不可計(jì)算性, 為此設(shè)計(jì)SID (Software Integrity Diagnosis system), 通過啟發(fā)式的壓縮算法來逼近這個(gè)度量。Zhang等[59]也提出了一項(xiàng)具有Kolmogorov復(fù)雜度的普適性信息距離度量指標(biāo),并基于LZ77壓縮算法解決Kolmogorov復(fù)雜度的不可計(jì)算問題; 此外通過對(duì)學(xué)生作業(yè)多對(duì)多分析得到相似性矩陣后, 他們利用Shared Near Neighbors聚類算法[24]進(jìn)行抄襲群體的挖掘。Ciesielski等[61]則從演化計(jì)算的角度, 將粒子群算法用于改善已有的token流相似性度量方法, 同時(shí)基于遺傳算法提出了更優(yōu)的token流相似性度量方法。

基于token的抄襲檢測(cè)方法通過文本結(jié)構(gòu)分析和詞法分析度量程序代碼的相似性, 時(shí)空復(fù)雜度較低,適用于大規(guī)模軟件代碼的抄襲檢測(cè)或代碼的批量檢測(cè)。此外其對(duì)代碼混淆如輕微的代碼重排、變量重命名等具備一定的抵抗力, 但仍舊難以應(yīng)對(duì)稍微復(fù)雜的代碼變換, 如冗余代碼植入、控制流混淆等。

3.2.2 基于樹的檢測(cè)

這類技術(shù)是將軟件代碼轉(zhuǎn)換成樹型結(jié)構(gòu)[75]進(jìn)行分析。Son等[76]利用ANTLR將軟件代碼轉(zhuǎn)換為解析樹, 通過子樹劃分及頻數(shù)統(tǒng)計(jì)構(gòu)造解析樹內(nèi)核, 并基于解析樹內(nèi)核的內(nèi)積運(yùn)算和歸一化實(shí)現(xiàn)相似性計(jì)算。解析樹通常包含過多的冗余節(jié)點(diǎn), 為此很多研究[77,78]在解析樹基礎(chǔ)上進(jìn)一步通過約減, 構(gòu)建程序的抽象語法樹(Abstract Syntax Tree, AST)。AST可以有不同的形式, 其比較方法也有很多種。Guo等[79]借助lex和yacc構(gòu)造程序的AST, 通過自底向上的累積運(yùn)算和AST遍歷為每個(gè)節(jié)點(diǎn)計(jì)算一個(gè)Hash值, 并通過節(jié)點(diǎn)的Hash值匹配和匹配的節(jié)點(diǎn)比例衡量相似性。這種子樹搜索或節(jié)點(diǎn)間匹配的方法難以應(yīng)對(duì)代碼重排及控制流混淆, 為此更多的研究是將AST轉(zhuǎn)換成token序列或字符串來處理。

BUAA_AntiPlagiarism[80]在構(gòu)建AST后, 通過線性化處理將AST轉(zhuǎn)換成token序列比較; 其用節(jié)點(diǎn)名稱標(biāo)識(shí)每個(gè)節(jié)點(diǎn), 通過前序遍歷將AST轉(zhuǎn)換成字符串, 并利用k-gram算法切分成一系列token, 最后利用Jaccard系數(shù)計(jì)算相似性。此外, 該方法對(duì)AST進(jìn)行了一系列優(yōu)化, 比如將代碼轉(zhuǎn)換成CIL中間代碼后再生成AST來簡(jiǎn)化分析, 通過冗余及無關(guān)節(jié)點(diǎn)的移除、關(guān)聯(lián)節(jié)點(diǎn)的合并來提高檢測(cè)效果。Resmi等[81]在構(gòu)造AST時(shí)使用了修改的語法, 他們對(duì)AST進(jìn)行前序遍歷生成節(jié)點(diǎn)序列, 然后通過Needleman-Wunsch算法和最長(zhǎng)公共子序列算法衡量相似性。Ji等[82]則提出PST(Program Static Tracing)方法, 其通過詞法語法分析構(gòu)造程序的解析樹和符號(hào)表, 進(jìn)行程序語法層面的靜態(tài)執(zhí)行, 按照函數(shù)的執(zhí)行次序?qū)︻A(yù)定義關(guān)鍵字進(jìn)行抽取, 將解析樹轉(zhuǎn)換成token序列,最后利用自適應(yīng)局部對(duì)齊算法實(shí)現(xiàn)相似性計(jì)算。

XPDec[83]則是首先將代碼轉(zhuǎn)換成XML文檔形式,然后通過特定的映射關(guān)系提取XML的樹結(jié)構(gòu)以構(gòu)造類型矩陣(Decimal Frame Matrix, DFM), 并通過對(duì)XML執(zhí)行XQuery查詢構(gòu)造控制矩陣(Decimal Control Matrix, DCM), 最后通過矩陣運(yùn)算計(jì)算相似性。EXPDec[84]是該方法的擴(kuò)展, 它克服了XPDec難以處理迭代的控制結(jié)構(gòu)的短板, 并且使用Levenshtein距離實(shí)現(xiàn)相似性計(jì)算。利用XML的樹形結(jié)構(gòu)建模程序語法, 可以有效應(yīng)對(duì)代碼重排, 然而因其要求編程語言具備較好的結(jié)構(gòu), 目前只能有效建模C或Pascal之類的過程化語言。

3.2.3 基于圖的檢測(cè)

基于圖的抄襲檢測(cè)方法[25,85]相對(duì)較少, GPLAG[25]從軟件代碼中構(gòu)造程序依賴圖(Program Dependency Graph, PDG), 通過子圖同構(gòu)匹配實(shí)現(xiàn)相似性計(jì)算; 此外, 為提高檢測(cè)效率, 文章提出有損過濾機(jī)制和基于G-test假設(shè)檢驗(yàn)的過濾機(jī)制約減子圖搜索空間。PDG由于捕獲了程序的數(shù)據(jù)和控制依賴關(guān)系、編碼了程序邏輯, 抄襲者很難在不理解代碼的前提下對(duì)PDG作出修改, 實(shí)驗(yàn)證實(shí)其相比其他方法能更有效應(yīng)對(duì)多種人工混淆手段。然而自動(dòng)化混淆工具的混淆能力更強(qiáng), 抄襲隱藏手段更高明; 此外, PDG的構(gòu)建過程代價(jià)很高, 而且子圖匹配是NP問題, 難以分析較大規(guī)模的軟件?？偟膩碚f, GPLAG是從學(xué)術(shù)抄襲到軟件產(chǎn)品抄襲的初步實(shí)踐,它考慮了較為復(fù)雜的人工混淆手段, 但它對(duì)源碼的需求及較高的時(shí)空花銷, 使其不足以應(yīng)對(duì)軟件產(chǎn)品的抄襲。

3.3 源碼抄襲檢測(cè)技術(shù)分析比較

本節(jié)對(duì)各類源碼抄襲檢測(cè)技術(shù)進(jìn)行總結(jié)和比較,見表1. 從表中可以看出, 每類技術(shù)都有各自的技術(shù)特點(diǎn)及優(yōu)缺點(diǎn), 在檢測(cè)精確性、抗混淆能力、計(jì)算的時(shí)空復(fù)雜度等方面有不同的表現(xiàn), 特別的基于token的檢測(cè)方法出現(xiàn)很多實(shí)用化的工具和系統(tǒng), 如Moss、JPlag、YAP3等, 是目前實(shí)際應(yīng)用中被普遍采用的方法。不過總體而言, 目前源碼抄襲檢測(cè)技術(shù)對(duì)代碼混淆的抵抗力不夠, 特別是難以對(duì)抗自動(dòng)化的語義保留的代碼混淆, 同時(shí)對(duì)源碼的依賴使其難以用于軟件產(chǎn)品的抄襲檢測(cè)。

表1 各類源碼抄襲檢測(cè)技術(shù)的比較

4 基于軟件水印的抄襲檢測(cè)技術(shù)

很多情況下被告是以可執(zhí)行文件的形式存在,在搜集到足夠證據(jù)前, 抄襲者不太可能給出其源碼。軟件水印技術(shù)可以處理這種情況, 其基本原理是在軟件發(fā)布之前, 在代碼中植入一個(gè)特殊的標(biāo)識(shí)符(水印), 該水印可以承載軟件作者、版權(quán)等信息, 事后可以通過特殊的提取器將其從被告軟件中識(shí)別或抽取出來作為證據(jù)以達(dá)到檢測(cè)的目的。軟件水印技術(shù)的基本原理如圖1所示。

已有研究對(duì)軟件水印技術(shù)的分類法很多, Collberg等[86]按照水印功能的不同劃分為身份水印、指紋水印、校驗(yàn)水印及許可水印四類, 張等[87]按照水印加入位置的不同將其分為代碼水印和數(shù)據(jù)水印, 其他研究[88]也有按照水印強(qiáng)弱、是否可見等進(jìn)行劃分。考慮到水印技術(shù)的關(guān)鍵在于植入和提取兩個(gè)階段,本文按照提取技術(shù)的不同劃分為靜態(tài)和動(dòng)態(tài)水印,進(jìn)而依據(jù)具體植入方法的不同分類總結(jié)。

4.1 靜態(tài)水印技術(shù)

靜態(tài)水印技術(shù)[89]是將水印植入到可執(zhí)行程序的代碼或數(shù)據(jù)中, 其提取過程不需要運(yùn)行程序, 通過靜態(tài)分析完成識(shí)別或提取。下面依據(jù)植入策略的不同對(duì)靜態(tài)水印技術(shù)分類介紹。

4.1.1 代碼替換法

圖1 軟件水印技術(shù)的基本原理

這類方法[90-95]的基本思路是將程序中特定的代碼或數(shù)據(jù)片段用軟件水印進(jìn)行替換, 從而嵌入水印。DMI[92]是這類技術(shù)的代表, 其通過在虛假函數(shù)中替換字節(jié)碼指令從而在Java程序中植入水印, 其中虛假函數(shù)是人為在代碼中添加的, 同時(shí)利用不透明謂詞保證這些虛假函數(shù)永不會(huì)被執(zhí)行。DMI首先將水印信息先轉(zhuǎn)換為bit序列, 并為特定的字節(jié)碼指令分配對(duì)應(yīng)的bit碼, 從而將水印用字節(jié)碼指令編碼出來,最后用這些字節(jié)碼指令替換虛假函數(shù)中原有的指令完成水印的植入。提取水印時(shí), 只要知道字節(jié)碼指令與bit碼的對(duì)應(yīng)關(guān)系, 以及bit碼跟水印信息的對(duì)應(yīng)關(guān)系, 采用與水印植入逆向的流程即可。DMISM[96]是DMI的改進(jìn)版, 其虛假函數(shù)構(gòu)建過程實(shí)現(xiàn)了自動(dòng)化。然而, 它們都容易遭受合謀攻擊, 也就是攻擊者通過對(duì)多份植入水印的程序進(jìn)行統(tǒng)計(jì)分析就可以定位水印的位置, 因?yàn)檫@種方法難以生成與原程序相同的代碼。

為此, Fukushima等[93]將DMI跟混淆技術(shù)相結(jié)合,他們?cè)趯?duì)植入水印后會(huì)對(duì)每份軟件再單獨(dú)進(jìn)行混淆,攻擊者在實(shí)施共謀攻擊時(shí), 就會(huì)發(fā)現(xiàn)軟件中呈現(xiàn)出多處差異, 從而難以定位水印位置。但總體而言, 代碼替換法植入的水印隱蔽性不好, 而且簡(jiǎn)單的代碼混淆就可以將水印破壞掉。

4.1.2 代碼重排法

這類方法[91,96]的基本原理是將水印轉(zhuǎn)換成數(shù)字,然后通過代碼重排編碼這個(gè)數(shù)字。DM算法[96]利用基本塊重排植入水印, 其首先將水印轉(zhuǎn)換成一個(gè)數(shù)字w, 對(duì)某個(gè)(或某些)方法的控制流圖(Control Flow Graph, CFG)中的基本塊集合B作w次排列形成新的基本塊集合B′, 然后將B′的基本塊重新鏈接到原程序中從而替換掉原有基本塊B。水印的提取過程則是通過比較原有基本塊的次序和'B的次序來獲取排列次數(shù)w, 然后將w轉(zhuǎn)換回水印。Anckaert等[97]實(shí)現(xiàn)了DM算法的一個(gè)變種, 不同于DM是對(duì)多個(gè)基本塊進(jìn)行重排, 他們是對(duì)多個(gè)基本塊鏈進(jìn)行重排, 這使得其植入的水印比DM算法植入的水印具備更好的隱蔽性。

除了利用基本塊重排植入水印外, Shirali-Shahreza[98]提出基于數(shù)學(xué)方程式中對(duì)稱的數(shù)學(xué)運(yùn)算進(jìn)行重排, Sha等[99]利用操作數(shù)系數(shù)重排來編碼水印, Gong等[100]則利用Java程序常量池的特點(diǎn), 通過對(duì)Java類中常量池的重排植入水印。以DM為代表的這類方法植入的水印對(duì)代碼混淆的抗毀性很弱, 一旦攻擊者實(shí)施混淆, DM就難以找到植入了水印的方法, 而水印提取的前提是必須找到實(shí)施了重排的基本塊所在的方法。一種可能的方案是檢查原始程序和植入水印后程序的所有方法對(duì), 但這一方面會(huì)導(dǎo)致過高的開銷, 另一方面會(huì)導(dǎo)致水印提取程序生成很多錯(cuò)誤的水印。

VEP[101]將程序當(dāng)做一個(gè)完整的統(tǒng)計(jì)對(duì)象, 對(duì)指令組進(jìn)行統(tǒng)計(jì)分析構(gòu)建特征向量C, 將水印構(gòu)造成同維特征向量W, 并利用指令重排對(duì)程序進(jìn)行受控的修改, 使得修改后程序的統(tǒng)計(jì)特征向量C~滿足CCW=+~。VEP植入的水印無法提取, 只能驗(yàn)證水印是否存在。

4.1.3 寄存器分配法

寄存器分配技術(shù)[102]是實(shí)現(xiàn)軟件水印植入的另一類技術(shù), QP算法[103]構(gòu)建程序的沖突圖(Interference Graph), 并依據(jù)水印轉(zhuǎn)換成的bit碼值向沖突圖中相應(yīng)節(jié)點(diǎn)間追加虛邊, 然后利用圖著色(Graph Coloring, GC)技術(shù)對(duì)沖突圖著色以實(shí)現(xiàn)寄存器分配。不過QP算法有一個(gè)最大問題是植入的水印并不總是可以提取的, 不同的水印植入后也可能會(huì)生成完全相同的沖突圖。Myles等對(duì)QP進(jìn)一步改進(jìn)提出QPS算法[104],它查找沖突圖中的Triples(不影響其他頂點(diǎn)且相對(duì)孤立的頂點(diǎn)三元組), 并保證植入水印時(shí)只會(huì)對(duì)這些Triples頂點(diǎn)添加虛邊。實(shí)驗(yàn)表明, QPS算法植入的水印具備更優(yōu)的隱蔽性和可提取性, 然而由于它只能利用部分頂點(diǎn), 植入的水印的信息量有限, Thomborson等通過對(duì)虛邊添加過程進(jìn)一步優(yōu)化提出了QPI算法[105]。

除了對(duì)沖突圖進(jìn)行改變外, CC(Color Change)和CP(Color Permutation)[106]算法則設(shè)計(jì)著色函數(shù), 可以不改變沖突圖結(jié)構(gòu)而是只改變頂點(diǎn)顏色, 這使得它們相比QPS以及QPI能夠植入更大的水印。SCC[107](Selected Color Change)進(jìn)一步優(yōu)化了CC算法的效率, 其只有當(dāng)bit碼為1時(shí)才改變顏色。

4.1.4 靜態(tài)圖法

GTW[108](Graph Theoretic Watermarking)將水印編碼到程序CFG的拓?fù)浣Y(jié)構(gòu)中, 其基本思想是將水印值用一個(gè)控制流圖G(簡(jiǎn)便起見稱作水印圖G)表示出來, 然后將水印圖G合并到原程序P的CFG中;為保證水印的隱蔽性, 水印圖G應(yīng)該盡可能接近真實(shí)的CFG, 此外GTW通過隨機(jī)游走在圖G節(jié)點(diǎn)和原程序P的節(jié)點(diǎn)間添加虛假邊使G與P緊耦合, 從而進(jìn)一步提高水印的隱蔽性。為了事后能夠提取GTW植入的水印, 需對(duì)水印圖G的節(jié)點(diǎn)進(jìn)行標(biāo)記, 以從水印圖G還原出水印信息。

圖2 給出了GTW方法的示意圖。Collberg等對(duì)GTW在Java字節(jié)碼上進(jìn)行了實(shí)現(xiàn), 稱作GTWSM[109,110]。GTWSM提供了兩種算法將水印進(jìn)行分割從而可以編碼到多個(gè)圖G中, 然后自動(dòng)地為每個(gè)圖G生成相應(yīng)代碼并合并到原有程序中。實(shí)驗(yàn)表明GTWSM可以編碼任意大的水印, 但植入水印后程序尺寸增大了40%-75%, 性能下降了0%-36%; GTWSM編碼水印用的是RPG(Reducible Permutation Graph), 盡管RPG跟程序真實(shí)的CFG非常相似, 但攻擊者還是比較容易找到這些RPG圖, 因而隱蔽性并不好, 同時(shí)簡(jiǎn)單的混淆攻擊如基本塊劃分等就可以破壞水印, 導(dǎo)致水印無法提取。

4.1.5 不透明謂詞法不透明謂詞是諸如x2≥0, -3y2-1==x2這類結(jié)果已知的一種謂詞, 它們較難通過自動(dòng)化分析識(shí)別出來, 前邊提到的MON算法就是利用不透明謂詞向代碼中添加虛假函數(shù)來提高水印的隱蔽性。Arboit[111]

提出了兩種基于不透明謂詞的水印技術(shù), 其基本思想是將水印編碼到不透明謂詞中, 然后在特定的分支點(diǎn)將這些謂詞添加到原程序代碼中。為了能夠編碼較大的水印, 兩種方法均將水印值切分成k個(gè)整數(shù), 然后用不透明謂詞中的常量值分別對(duì)這k個(gè)整數(shù)進(jìn)行編碼, 比如-3y2-1==x2編碼了整數(shù)4; 兩種方法的區(qū)別是一個(gè)采用不透明謂詞編碼水印(稱作GA1), 一個(gè)則采用不透明函數(shù)進(jìn)行編碼(稱作GA2)。對(duì)于水印的提取, 需要查找所有不透明謂詞/方法,然后解碼成水印。Myles等[112]對(duì)這兩種方法進(jìn)行了實(shí)現(xiàn)和評(píng)估, 發(fā)現(xiàn)GA1在性能、抗毀性、隱蔽性方面均優(yōu)于GA2, 但兩種方法植入的水印還是較容易被混淆攻擊破壞掉。

4.1.6 抽象解釋法

Patrick等[113]提出了基于抽象解釋的軟件水印技術(shù), 其原理是使得植入的水印只有在知曉所采用的具體抽象及抽取策略前提下進(jìn)行的抽象解釋才能提取。具體而言, 該方法將水印分割以編碼成簡(jiǎn)短的代碼段, 然后緊密植入到程序原有函數(shù)的聲明、初始化及函數(shù)體代碼中; 提取時(shí)則采用了常量傳播分析的抽象解釋方法來提取水印。此外, 該方法還結(jié)合混淆及參數(shù)抽象手段進(jìn)一步提高水印的隱蔽性。

綜上所述, 靜態(tài)水印技術(shù)是關(guān)注如何將水印隱藏到程序代碼或數(shù)據(jù)中, 同時(shí)保證通過靜態(tài)分析能提取出來。對(duì)于上述水印技術(shù), 按照植入原理的不同可以進(jìn)一步概括為兩類: 通過代碼排序植入(代碼重排法)和通過追加代碼植入(代碼替換、寄存器分配、圖水印、不透明謂詞、抽象解釋法)。

圖2 GTW水印植入示意圖

4.2 動(dòng)態(tài)水印技術(shù)

動(dòng)態(tài)水印技術(shù)[114]是將水印植入到程序的執(zhí)行過程或運(yùn)行狀態(tài)中, 也就是說其并不是直接植入水印本身, 而是植入編碼了水印信息的額外代碼或數(shù)據(jù),在軟件執(zhí)行過程中可以將水印動(dòng)態(tài)表達(dá)或構(gòu)建出來。本文將現(xiàn)有主流動(dòng)態(tài)水印技術(shù)歸納為以下幾類。

4.2.1 數(shù)據(jù)結(jié)構(gòu)法

Collberg等提出CT算法[15,115,116], 將水印植入到動(dòng)態(tài)構(gòu)建的圖結(jié)構(gòu)中。具體流程如圖3所示, 首先將水印編碼到一個(gè)圖G中, 為提高隱蔽性切分成多個(gè)子圖, 然后在程序的某條路徑上插入能夠動(dòng)態(tài)構(gòu)建這些子圖的代碼; 水印的抽取則是給定特定輸入執(zhí)行該路徑時(shí), 圖G會(huì)從堆數(shù)據(jù)中被構(gòu)建出來, 最后再轉(zhuǎn)換回水印。

對(duì)于水印到圖G的編碼方式, CT提出了三種[117]:枚舉圖、基數(shù)圖和排列圖。

枚舉編碼是將水印值W編碼成圖G(在某個(gè)可枚舉圖結(jié)構(gòu)中)對(duì)應(yīng)的索引值, 具體的可枚舉圖結(jié)構(gòu)可以使用有向父指針樹(Directed Parent-Pointer Tree, DPPT)、平面立體種植樹(Plantted Planar Cubic Tree, PPCT)等。圖4(a)給出了7個(gè)節(jié)點(diǎn)的DPPT的第1、2、22及48次枚舉樹, 假定要編碼的水印值為22, 則將能動(dòng)態(tài)構(gòu)造第22次枚舉樹的代碼植入原程序即可。Zhu等[118]提出了兩種改進(jìn)的枚舉圖結(jié)構(gòu)PIPPCT及MIPPCT, 其水印植入相比PPCT具有更好的性能。

基數(shù)編碼同樣利用了循環(huán)鏈表, 具體而言每個(gè)節(jié)點(diǎn)的右指針指向下一個(gè)節(jié)點(diǎn), 左指針指向節(jié)點(diǎn)到該節(jié)點(diǎn)的距離則編碼了基數(shù)為k的整數(shù), 這樣長(zhǎng)度為k的鏈表可以編碼的任意整數(shù), 這種方式生成的圖稱作基數(shù)圖。圖4(c)所示的基數(shù)6編碼圖編碼了水印值為4453的水印?；鶖?shù)圖的左指針指向相比排列圖的指針具備更好的靈活性, 所以基數(shù)編碼植入的水印會(huì)具備較弱的糾錯(cuò)能力, 但會(huì)擁有更高的碼率。此外, 也有研究[120]將基數(shù)圖轉(zhuǎn)換成類似于PPCT的結(jié)構(gòu)以改善糾錯(cuò)能力。

圖3 CT動(dòng)態(tài)水印技術(shù)的基本流程

圖4 水印的圖編碼

除了利用堆數(shù)據(jù)結(jié)構(gòu)以外, Kamel等[121]提出利用基于磁盤的數(shù)據(jù)結(jié)構(gòu)R-tree編碼水印, 其利用R-tree節(jié)點(diǎn)內(nèi)詞條存在冗余及無序限制的特點(diǎn), 通過節(jié)點(diǎn)內(nèi)詞條的重排編碼水印值。

4.2.2 條件分支法

CBW[122]將水印編碼到程序的動(dòng)態(tài)分支結(jié)構(gòu)中,其基本思路是用條件分支的動(dòng)態(tài)行為(取False或Ture分支)編碼水印值, 捕獲程序在特定輸入(或輸入序列)下的執(zhí)行軌跡, 并在該軌跡的恰當(dāng)位置植入編碼了水印值的條件分支語句; 水印提取過程則是用相同的特定輸入(或輸入序列)執(zhí)行程序, 捕獲編碼了水印值的執(zhí)行軌跡, 通過分析其條件分支的動(dòng)態(tài)行為識(shí)別出水印。為提高隱蔽性和效率, Collberg采取了一系列優(yōu)化措施, 如利用中國(guó)剩余定理(Chinese Remainder Theorem)將水印值分解為多份散布到程序多個(gè)位置植入, 通過軌跡分析將條件分支語句植入到非頻繁執(zhí)行點(diǎn)等。Myles等[123]結(jié)合代碼混淆和防篡改技術(shù)的部分思想, 將非條件分支和條件分支均轉(zhuǎn)換成分支函數(shù), 分支函數(shù)一方面實(shí)現(xiàn)原有控制轉(zhuǎn)移功能, 另一方面負(fù)責(zé)水印編碼。

4.2.3 線程爭(zhēng)用法

TCW[124]是基于線程競(jìng)爭(zhēng)實(shí)現(xiàn)的水印技術(shù), 其在原程序中的單線程部分引入新的線程, 并使用鎖機(jī)制保證線程切換始終受控, 從而將水印編碼到線程切換行為中。比如對(duì)于線程化部分被執(zhí)行的兩個(gè)基本塊, 如果是在不同線程中被執(zhí)行, 則用這種行為編碼比特0; 如果是在相同線程被執(zhí)行, 則用這種行為編碼比特1。通過將水印轉(zhuǎn)換成比特碼, 就可以編碼到基本塊序列中。此外, 對(duì)于線程化部分的選擇, Thomborson等通過動(dòng)態(tài)軌跡追蹤避開頻繁執(zhí)行代碼,同時(shí)對(duì)于水印的植入也只選用不會(huì)被頻繁執(zhí)行的基本塊進(jìn)行編碼, 這樣可以大大減少水印植入所帶來的性能開銷。但新引入的線程代碼需要進(jìn)行非常精心的設(shè)計(jì)以保證程序正確性, 此外初步試驗(yàn)表明植入水印后軟件的性能下降2～8倍, 尺寸也相比原來有很大的增加。

4.2.4 運(yùn)算法

前幾類方法需要先將水印用圖結(jié)構(gòu)或者指令模式等進(jìn)行編碼, 然后向原程序中添加能夠動(dòng)態(tài)生成這些圖或指令模式的代碼。運(yùn)算法與之不同, 其忽略了將水印轉(zhuǎn)化為其他結(jié)構(gòu)或模式這一過程, 而是直接向原程序中添加代碼, 這些代碼在特定輸入下通過運(yùn)算直接將水印輸出。

LSW[125]利用循環(huán)結(jié)構(gòu)植入水印, 其在既有循環(huán)體代碼語義分析基礎(chǔ)上增加額外代碼, 這些代碼對(duì)原循環(huán)體代碼存在數(shù)據(jù)或控制依賴關(guān)系, 且在特定輸入(對(duì)應(yīng)特定的循環(huán)展開)下會(huì)計(jì)算出水印值。HFW[126]通過構(gòu)造Hash函數(shù)對(duì)水印值進(jìn)行編碼, 并通過替換特定輸入下執(zhí)行路徑上的常量將Hash函數(shù)添加到到原代碼中, 當(dāng)執(zhí)行相同的特定輸入時(shí), Hash函數(shù)就會(huì)被執(zhí)行并輸出水印值。ROPW[127]利用ROP(Return-Oriented Programming)技術(shù)從既有代碼中構(gòu)造水印代碼, 鏈接到ROP的執(zhí)行路徑同時(shí)隱藏到數(shù)據(jù)區(qū)中; 只有在特定輸入下才會(huì)動(dòng)態(tài)地恢復(fù)出隱藏在堆數(shù)據(jù)中的ROP執(zhí)行路徑, ROP路徑的執(zhí)行最終輸出水印。ROPW采用數(shù)據(jù)區(qū)而非代碼區(qū)隱藏水印, 使其具備非常好的隱蔽性。

運(yùn)算法由于不使用第三方表示編碼水印, 其在植入較大水印的同時(shí)帶來的性能開銷要低于其他方法; 然而正是由于忽略水印編碼的過程, 這類技術(shù)在設(shè)計(jì)時(shí)必須使水印代碼跟原代碼緊密耦合以保證隱蔽性。

4.3 基于軟件水印的抄襲檢測(cè)技術(shù)分析比較

本文從隱蔽性、抗毀性、碼率及性能開銷四個(gè)維度對(duì)各類水印技術(shù)進(jìn)行對(duì)比分析(見表2)。隱蔽性刻畫了水印躲避攻擊者識(shí)別和定位的能力; 抗毀性刻畫了水印對(duì)各種攻擊如代碼混淆等的抵抗能力,也就是要保證在各種攻擊下水印不會(huì)被破壞, 依舊可以可靠地識(shí)別和提取; 碼率刻畫了水印技術(shù)植入大型水印的能力; 性能開銷刻畫了水印技術(shù)植入和提取水印的復(fù)雜程度, 以及水印植入后所帶來的性能降級(jí)、尺寸增加的程度。四個(gè)特性間通常存在矛盾關(guān)系, 任何水印技術(shù)都需要根據(jù)實(shí)際需求對(duì)四個(gè)特性進(jìn)行權(quán)衡。

5 基于軟件胎記的抄襲檢測(cè)技術(shù)

軟件水印技術(shù)通過識(shí)別事先植入的水印來檢測(cè)抄襲, 然而水印的植入不僅會(huì)引入額外的時(shí)空開銷,導(dǎo)致程序性能下降, 甚至?xí)胄碌能浖毕莺吐┒? 影響軟件的正確性和安全性。此外, 當(dāng)前的水印技術(shù)對(duì)語義保留的代碼混淆攻擊的抵抗力都較弱,經(jīng)過適當(dāng)?shù)呐粽呤冀K可以破壞任何水印[122]。為解決上述問題, 研究者提出了基于軟件胎記的抄襲檢測(cè)技術(shù)。

相比水印是事先植入到軟件中的額外數(shù)據(jù), 軟件胎記是指從軟件中可提取的一系列特征, 這些特征刻畫了軟件自身的固有屬性, 并且可以唯一地標(biāo)識(shí)這個(gè)軟件。給定待檢測(cè)的被告軟件, 胎記技術(shù)通過判斷其與原告軟件的胎記是否一致判定抄襲。然而真實(shí)的情況是, 即使軟件Q抄襲了P, 它們的胎記也并不一定會(huì)完全一致; 因?yàn)檐浖ビ浭莻€(gè)理想化的概念, 實(shí)際中很難保證抽取的胎記切實(shí)地刻畫軟件自身固有的難以改變的屬性。為此, 在實(shí)際應(yīng)用時(shí),胎記技術(shù)是通過衡量胎記的相似性實(shí)現(xiàn)抄襲的判定,這類似于源碼抄襲檢測(cè)技術(shù), 但胎記技術(shù)的操作情景是默認(rèn)被告源碼無法獲取, 同時(shí)應(yīng)對(duì)的是更復(fù)雜更苛刻的抄襲手段。圖5給出了胎記技術(shù)的基本流程。

軟件胎記技術(shù)的關(guān)鍵在于軟件胎記的抽取和胎記相似性的衡量。為構(gòu)造高質(zhì)量胎記, 應(yīng)使抽取的胎記盡可能接近程序的語義行為, 從而不容易被代碼混淆破壞掉, 按照胎記抽取是否需要程序運(yùn)行, 現(xiàn)有的軟件胎記可以歸納為靜態(tài)胎記和動(dòng)態(tài)胎記兩類;胎記相似性的衡量主要依賴于胎記的具體形式, 可以劃分為序列、集合和圖形式胎記。本文將根據(jù)胎記構(gòu)建方法的不同對(duì)其進(jìn)行分類介紹。

表2 各種軟件水印技術(shù)的比較分析

5.1 靜態(tài)胎記技術(shù)

5.1.1 屬性分析法

最初的軟件胎記主要是通過分析軟件的詞法及結(jié)構(gòu)特性抽取出來的, 其利用構(gòu)成軟件的基本要素如指令、API、系統(tǒng)調(diào)用等, 而較少考慮語法語義信息。

Tamada等[128,129]率先提出軟件胎記的概念, 并針對(duì)Java程序?qū)崿F(xiàn)了四種不同的靜態(tài)胎記, 包括CVFV, SMC, IS以及UC; 它們分別從類常量字段、標(biāo)準(zhǔn)API、繼承結(jié)構(gòu)以及標(biāo)準(zhǔn)類的使用情況四個(gè)角度對(duì)Java類進(jìn)行特征化, 將每種胎記表示成對(duì)應(yīng)基本屬性的序列, 比如某個(gè)類的UC胎記就是由該類所使用的所有標(biāo)準(zhǔn)類按字母序排列成的序列。Myles等[130]則使用整個(gè)指令序列標(biāo)識(shí)軟件, 鑒于序列太長(zhǎng)難以直接比較, 其利用k-gram算法對(duì)軟件指令序列進(jìn)行切分, 然后將所有g(shù)ram構(gòu)成的集合作為胎記, 原告與被告胎記通過Containment集合運(yùn)算實(shí)現(xiàn)相似性度量。Myles的胎記沒有考慮gram的頻率特性, Xie等[131]在此基礎(chǔ)上將gram的頻率引入胎記生成中,提出了帶權(quán)k-gram胎記, 但檢測(cè)效果的提升幅度并不明顯。

圖5 基于軟件胎記的抄襲檢測(cè)方法的基本流程

AVSB[132]使用函數(shù)參數(shù)及局部變量個(gè)數(shù)作為函數(shù)胎記, 然后將所有函數(shù)胎記構(gòu)成的序列作為程序胎記; AVSB使用半全局比對(duì)(semi-global alignment)算法衡量序列的相似性, 或者將序列轉(zhuǎn)換成k-gram后基于集合運(yùn)算實(shí)現(xiàn)胎記的相似性計(jì)算。Choi等[133,134]提出了基于系統(tǒng)調(diào)用的靜態(tài)胎記WSCB, 其構(gòu)建程序的調(diào)用圖, 然后將每個(gè)函數(shù)中使用的以及調(diào)用圖中距離該函數(shù)深度k步以內(nèi)的函數(shù)中使用的所有系統(tǒng)調(diào)用構(gòu)成的集合作為該函數(shù)的胎記, 并將所有函數(shù)胎記的并集作為軟件胎記WSCB; Jaccard系數(shù)被用來衡量函數(shù)胎記的相似性, 最后通過最大雙邊圖匹配實(shí)現(xiàn)WSCB胎記相似性的計(jì)算。

此類胎記技術(shù)單純利用構(gòu)成程序且較難改變的基本元素, 拋棄了過多的語法語義信息, 因此難以對(duì)抗甚至十分簡(jiǎn)單的代碼混淆, 如指令重排、替換、垃圾代碼植入、函數(shù)內(nèi)聯(lián)外聯(lián)等。

5.1.2 靜態(tài)控制流法

Taisook等[135-140]提出了一系列基于控制流分析的靜態(tài)胎記, 其基本思想是在控制流分析引導(dǎo)下盡可能模擬軟件真實(shí)的運(yùn)行時(shí)行為, 以使生成的胎記更貼近軟件的行為特征, 從而不容易被混淆等破壞掉。

FPB[135](Flow Path Birthmark)構(gòu)建每個(gè)方法的CFG, 其定義一條Flow Path為CFG中從任意節(jié)點(diǎn)出發(fā)k步可達(dá)的基本塊構(gòu)成的路徑, 將從程序所有方法中提取出的所有Flow Path構(gòu)成的集合作為該程序的FPB胎記; 對(duì)于FPB的相似性計(jì)算, 其用某Flow Path上所有指令構(gòu)成的序列表示該Flow Path的行為,并利用用半全局比對(duì)算法實(shí)現(xiàn)Flow Path行為的比較,得到原告與被告所有Flow Path的兩兩相似性矩陣,最后基于雙邊圖匹配實(shí)現(xiàn)原告與被告FPB的相似性計(jì)算。CFEB[136]則將CFG中所有控制流邊構(gòu)成的集合作為胎記, 并用每條邊所連接的兩個(gè)基本塊中所有指令構(gòu)成的序列刻畫該控制流邊的行為; CFEB采用了最長(zhǎng)公共子序列LCS衡量控制流邊行為的相似性, 并采用雙邊圖匹配實(shí)現(xiàn)原告與被告軟件CFEB胎記的相似性計(jì)算。

SFB[137]是模擬Java程序操作數(shù)棧的運(yùn)行情況提出的靜態(tài)胎記, 其基于CFG掃描所有可能的執(zhí)行路徑, 然后對(duì)于每條路徑, 分析該路徑上每條指令執(zhí)行前后的操作數(shù)棧的狀態(tài)(棧深度), 將指令及其執(zhí)行后的棧狀態(tài)共同構(gòu)成的序列稱作一條Stack Flow, 并將所有Stack Flow的集合作為軟件胎記; SFB也是利用半全局比對(duì)獲得Stack Flow的兩兩相似性矩陣,再利用最大雙邊圖匹配計(jì)算原告與被告SFB的相似性。WSPB[138]也是模擬Java操作數(shù)棧的運(yùn)行情況, 其將整個(gè)指令序列按照棧深為0切分成一系列Stack Pattern, 同時(shí)其并不平等對(duì)待Stack Pattern中的所有指令, 而是利用TF-IDF計(jì)算每條指令的權(quán)值, 并將所有的帶權(quán)Stack Pattern構(gòu)成的集合作為軟件胎記。

WSPB為不同指令賦權(quán)的思想體現(xiàn)了不同指令對(duì)于刻畫程序行為貢獻(xiàn)度不一的問題, OTB[139]僅利用Java程序中與對(duì)象操作相關(guān)的11條特定指令生成胎記, OTB在CFG基礎(chǔ)上通過移除所有與對(duì)象操作無關(guān)的指令構(gòu)建對(duì)象流圖(Object Flow Graph, OFG),其挖掘OFG中所有長(zhǎng)度為k的序列, 并將整個(gè)程序中挖掘出的所有序列作為軟件胎記; OTB采用局部比對(duì)實(shí)現(xiàn)序列的兩兩比較, 并同樣采用雙邊圖匹配實(shí)現(xiàn)原告與被告胎記的相似性計(jì)算。除了考慮指令對(duì)于刻畫軟件行為貢獻(xiàn)不一外, SMPB[140]只考慮可以反映程序行為且較難修改的關(guān)鍵路徑, 其分析構(gòu)成CFG的各項(xiàng)分支、循環(huán)等結(jié)構(gòu), 尋找最可能的執(zhí)行路徑, 并將該執(zhí)行路徑中出現(xiàn)的所有系統(tǒng)調(diào)用構(gòu)成的序列作為軟件胎記; SMPB的相似性計(jì)算采用Smith-Waterman序列對(duì)齊算法。

5.1.3 靜態(tài)語義分析法

Taisook提出的這些基于控制流分析的靜態(tài)胎記,通過CFG蘊(yùn)含的指令流、操作符棧狀態(tài)流、標(biāo)準(zhǔn)API流等從不同角度刻畫程序行為, 本質(zhì)上都是通過盡可能模擬程序真實(shí)的運(yùn)行狀態(tài)以保證抽取的胎記與程序的語義行為更貼近, 從而提高胎記的抗毀性;然而, 這些基于控制流分析的靜態(tài)胎記仍然容易被簡(jiǎn)單的代碼混淆手段如不透明分支植入、基本塊拆分、垃圾指令植入等破壞掉。

Cop[12]是目前唯一一種基于嚴(yán)格語義分析的靜態(tài)胎記技術(shù), 其基于CFG獲取所有的線性獨(dú)立路徑,并用路徑上蘊(yùn)含的基本塊序列刻畫程序行為; 對(duì)于每個(gè)基本塊, Cop通過符號(hào)執(zhí)行將其表示成蘊(yùn)含了輸入輸出關(guān)系的一系列邏輯公式, 并利用自動(dòng)定理證明器來衡量?jī)蓚€(gè)基本塊的語義相似性, 然后基于最長(zhǎng)語義等價(jià)基本塊子序列衡量原告與被告中任意兩條線性獨(dú)立路徑的相似性, 進(jìn)一步實(shí)現(xiàn)整個(gè)軟件胎記的相似性計(jì)算。Cop方法采取了嚴(yán)格的語義分析,因而相比其他靜態(tài)胎記而言對(duì)各類語義保留的代碼混淆技術(shù)具備很好的抵抗力。然而符號(hào)執(zhí)行及理論證明引入的巨大開銷使Cop難以處理大規(guī)模的軟件,同時(shí)Cop也受制于目前理論證明在處理不透明謂詞、未解決猜想等方面的局限性; 此外Cop作為靜態(tài)胎記的一種, 其受制于靜態(tài)分析難以處理間接分支等的局限性。

5.2 動(dòng)態(tài)胎記技術(shù)

5.2.1 軌跡元素法

動(dòng)態(tài)胎記是通過分析軟件的執(zhí)行過程提取出來的胎記, 相比靜態(tài)胎記其能更好地刻畫程序的語義和行為特征, 目前研究也普遍認(rèn)為其相比靜態(tài)胎記能更有效地應(yīng)對(duì)各類代碼混淆攻擊。

Myles等[141]首次提出動(dòng)態(tài)胎記的概念, 并通過分析程序的動(dòng)態(tài)控制流路徑實(shí)現(xiàn)了一種胎記WPP(Whole Program Path), 不過其很容易被循環(huán)展開、函數(shù)內(nèi)聯(lián)等混淆破壞掉。Tamda等[142,143]提出了兩種適用于Windows程序的動(dòng)態(tài)胎記EXESEQ和EXEFREQ, 它們利用API序列及其頻率分布特性來刻畫軟件行為, 并分別利用最長(zhǎng)子序列和Cosine距離計(jì)算胎記相似性。Schuler[13]則利用Java標(biāo)準(zhǔn)API的動(dòng)態(tài)調(diào)用序列生成胎記, 以檢測(cè)Java軟件的抄襲?；贏PI的胎記只適用于特定的編程語言, Wang等[16]提出基于系統(tǒng)調(diào)用的兩種胎記SCSSB和IDSCSB解決這個(gè)問題。

除此之外, DIB[144]及ISB[145]使用構(gòu)成執(zhí)行軌跡的指令生成胎記, 然而整個(gè)指令序列過于龐大, 難以分析大規(guī)模軟件, 而且采用所有指令會(huì)包含很多噪聲, 難以抵抗代碼混淆。對(duì)此, Tian等[20,146]結(jié)合動(dòng)態(tài)污點(diǎn)分析技術(shù)識(shí)別與程序語義行為緊密相關(guān)的關(guān)鍵指令序列, 利用k-gram算法生成DYKIS胎記并基于Cosine距離衡量相似性。Jhi[9]則利用動(dòng)態(tài)數(shù)據(jù)流分析識(shí)別程序執(zhí)行過程中難以更改且與程序語義緊密相關(guān)的核心值, 提出核心值胎記CVB并基于LCS計(jì)算相似性。

5.2.2 依賴分析法

單純利用軟件執(zhí)行軌跡所體現(xiàn)的基本元素生成胎記, 會(huì)拋棄了較多的語法語義信息, 難以對(duì)抗復(fù)雜的混淆手段; 為此不少研究通過挖掘執(zhí)行軌跡中基本元素間的依賴關(guān)系構(gòu)造胎記, 以進(jìn)一步提高對(duì)代碼混淆的抵抗力。

Wang等[11]挖掘系統(tǒng)調(diào)用間的數(shù)據(jù)依賴和控制依賴關(guān)系, 提出系統(tǒng)調(diào)用依賴圖胎記SCDGB; Patrick[27,147]通過對(duì)JavaScript程序的動(dòng)態(tài)堆數(shù)據(jù)進(jìn)行分析, 構(gòu)建基于堆圖的動(dòng)態(tài)胎記HGB刻畫程序行為。SCDGB和HGB均采用子圖同構(gòu)實(shí)現(xiàn)相似性計(jì)算,然而子圖同構(gòu)是NP問題, 在實(shí)際應(yīng)用時(shí)面臨計(jì)算復(fù)雜度過高的局限性。

為此對(duì)于圖形式的胎記, 有研究將圖轉(zhuǎn)換成序列或向量形式進(jìn)行運(yùn)算。DAAV[148,149]構(gòu)建程序的動(dòng)態(tài)調(diào)用圖(包含系統(tǒng)調(diào)用及自身函數(shù))DACG, 利用隨機(jī)游走為圖中每個(gè)API計(jì)算一個(gè)權(quán)威值, 進(jìn)而將DACG轉(zhuǎn)換成向量形式, 利用Cosine距離衡量胎記相似性。SUPB[150]基于程序執(zhí)行軌跡構(gòu)建動(dòng)態(tài)調(diào)用序列圖DCSG, DCSG的邊反映了函數(shù)調(diào)用關(guān)系, 同時(shí)記錄了函數(shù)調(diào)用后的棧深度, SUPB通過將DCSG轉(zhuǎn)換成棧深淺變化序列后利用LCS衡量相似性。Jhi[22]在核心值胎記CVB[9]基礎(chǔ)上, 通過分析核心值之間的數(shù)據(jù)依賴關(guān)系, 提出核心值依賴圖胎記VDGB; VDGB搜索VDG中存在偏序依賴的代表性路徑, 通過衡量原告代表性路徑在被告中所占的比例實(shí)現(xiàn)相似性計(jì)算, VDGB相比CVB能更有效應(yīng)對(duì)指令重排混淆。

5.2.3 語義分析法

相比已有動(dòng)態(tài)胎記通過分析軟件運(yùn)行時(shí)信息和狀態(tài)來盡可能貼切地描述程序語義行為, LoPD[155,156]采用嚴(yán)格的形式化邏輯分析捕捉程序語義行為; 此外, 不同于已有胎記技術(shù)通過衡量原告與被告相似性判定抄襲, LoPD通過查找二者可能存在的任何不相似來檢測(cè)抄襲。LoPD利用最弱前置條件推理將程序執(zhí)行路徑轉(zhuǎn)換成邏輯公式, 并利用約束求解判斷原告及被告執(zhí)行路徑的等價(jià)性; 符號(hào)執(zhí)行被用來產(chǎn)生新的輸入和驅(qū)動(dòng)新路徑的執(zhí)行, 路徑背離檢測(cè)技術(shù)被用來加速抄襲的檢測(cè)過程。LoPD由于采用嚴(yán)格的語義等價(jià)性證明判定抄襲, 能有效抵抗各種語義保留的代碼混淆; 然而其要求存在抄襲的軟件具備完全一致的語義, 這極大地限制了LoPD的應(yīng)用范圍,因?yàn)檎Z義上絲毫的改變就會(huì)使LoPD判定為不存在抄襲。此外, LoPD受制于符號(hào)執(zhí)行和約束求解的局限性及其帶來的巨大開銷, 難以處理大規(guī)模軟件。

5.3 基于軟件胎記的抄襲檢測(cè)技術(shù)分析比較

一種軟件胎記技術(shù)的優(yōu)劣是通過以下兩方面進(jìn)行衡量: 一是識(shí)別抄襲的能力, 也就是胎記抵抗各類語義保留的代碼混淆的能力, 要保證混淆前后通過胎記依然可以識(shí)別出原程序及混淆版本的同源性,稱之為彈性或抗毀性; 二是區(qū)分獨(dú)立開發(fā)軟件的能力, 要保證其能有效地將功能相似但獨(dú)立實(shí)現(xiàn)的軟件區(qū)分開來, 稱之為可靠性。

表3對(duì)各類胎記技術(shù)進(jìn)行總結(jié)和比較。從表中可以看出, 現(xiàn)有胎記技術(shù)普遍具備較高的可靠性,而在彈性及性能開銷上存在較大差異。靜態(tài)胎記普遍彈性較低, 但具備開銷小的優(yōu)點(diǎn); 動(dòng)態(tài)胎記彈性普遍較高, 但面臨開銷較大的問題。特別是基于語義分析的軟件胎記具備非常高的彈性, 但其帶來的巨額開銷給其實(shí)際應(yīng)用帶來很大局限性?；谲浖ビ浀某u檢測(cè)研究仍處于起始階段, 有很多挑戰(zhàn)性問題需要進(jìn)一步解決, 也是未來研究的重點(diǎn)。此外, 盡管性能問題一直不是胎記技術(shù)關(guān)注的重點(diǎn),但如何在提高彈性的同時(shí)盡可能降低性能開銷,是將來設(shè)計(jì)并開發(fā)實(shí)用化工具或系統(tǒng)應(yīng)當(dāng)遵守的原則。

表3 基于軟件胎記的抄襲檢測(cè)技術(shù)對(duì)比

6 抄襲檢測(cè)面臨的挑戰(zhàn)及未來研究方向

前文對(duì)當(dāng)下主流的軟件抄襲檢測(cè)研究進(jìn)行了總結(jié), 可以看出盡管軟件抄襲檢測(cè)的研究工作取得了很大的進(jìn)展, 但現(xiàn)有方法在抗混淆能力、性能等方面依然存在很大的局限性, 不少技術(shù)還處于理論研究階段, 難以在實(shí)際中得到推廣應(yīng)用; 此外新平臺(tái)(如移動(dòng)平臺(tái)、云平臺(tái))的出現(xiàn)、軟件發(fā)展趨勢(shì)的變化(多線程編程)等, 也給抄襲檢測(cè)帶來新的問題和挑戰(zhàn)。本節(jié)對(duì)這些問題進(jìn)行梳理, 并對(duì)未來的研究方向進(jìn)行展望。

6.1 新平臺(tái)下的抄襲檢測(cè)研究

隨著移動(dòng)應(yīng)用市場(chǎng)的繁榮, 移動(dòng)應(yīng)用的抄襲問題日益嚴(yán)峻, 特別是Android平臺(tái), 其應(yīng)用程序數(shù)量眾多, 難以一一人工核查; 此外App存在易被反編譯的問題, 加之各種成熟的混淆工具的存在, 抄襲者可以很容易獲得其代碼, 通過重打包等方式修改持有者名字或植入廣告再發(fā)布的方式達(dá)到盈利目的。研究者對(duì)多個(gè)第三方App市場(chǎng)的研究表明, 5%-13%的App是重打包發(fā)布而來的[7]; 甚至Google Play自身中有1.2%的App是重打包的[8]。此外, 通過重打包植入惡意payloads可以快速生成并傳播大量惡意軟件[157]。最近一項(xiàng)研究[8]顯示, 來自33個(gè)Android市場(chǎng)共計(jì)120萬個(gè)App中有10.93%是可疑的, 即使Google Play中也有7.61%的應(yīng)用是惡意的, 而且其中有些應(yīng)用已被安裝100萬次以上; 另一項(xiàng)研究[7]表明, Android惡意軟件中大約有86%是通過對(duì)合法軟件進(jìn)行重打包而來的。因而, 移動(dòng)應(yīng)用的抄襲檢測(cè)研究也獲得越來越多的關(guān)注, 主流的技術(shù)還是通過結(jié)合移動(dòng)應(yīng)用的自身特點(diǎn), 設(shè)計(jì)適用于移動(dòng)端App的軟件水印或胎記技術(shù)。

目前針對(duì)移動(dòng)App的水印技術(shù)研究非常少, AppInk[158]簡(jiǎn)單地將傳統(tǒng)的動(dòng)態(tài)圖水印技術(shù)用于移動(dòng)端App中, 其采用排列圖實(shí)現(xiàn)水印的編碼和植入。Ren等[14]設(shè)計(jì)了一種針對(duì)移動(dòng)平臺(tái)的水印技術(shù)Droidmarking, 其利用自加密代碼(Self-Decrypting Code, SDC)段植入水印; SDC可以使得水印跟原代碼間存在緊耦合關(guān)系, 簡(jiǎn)單的解耦會(huì)破壞程序完整性而導(dǎo)致無法運(yùn)行。這樣的好處在于不必再關(guān)注水印的隱蔽性, 同時(shí)SDC植入的水印提取開銷不大,使得Droidmarking可以部署到應(yīng)用市場(chǎng)或用戶終端上進(jìn)行實(shí)時(shí)在線的檢測(cè)。

移動(dòng)端App具有數(shù)量龐大, 更新速度快等特點(diǎn),類似于AppInk將傳統(tǒng)的水印技術(shù)簡(jiǎn)單移植到App上的方法顯然并不能滿足移動(dòng)平臺(tái)對(duì)其在抗毀性、泛化能力以及性能等方面的需求; Droidmarking結(jié)合移動(dòng)平臺(tái)的特點(diǎn)作出了初步的嘗試, 但其目前要求Dalvik虛擬機(jī)運(yùn)行在非優(yōu)化模式以保證SDC段的格式不會(huì)發(fā)生改變, 此外其應(yīng)對(duì)動(dòng)態(tài)攻擊的能力一般,并且水印植入給原程序帶來的開銷也需要進(jìn)一步優(yōu)化。因此, 綜合考慮移動(dòng)平臺(tái)的特點(diǎn), 通過對(duì)傳統(tǒng)的動(dòng)靜態(tài)水印技術(shù)進(jìn)行擴(kuò)展, 或者設(shè)計(jì)專門的水印技術(shù), 來滿足移動(dòng)平臺(tái)的需求將會(huì)是一個(gè)非常重要的研究方向。

對(duì)于移動(dòng)平臺(tái), 現(xiàn)有方法大部分是利用胎記技術(shù)實(shí)現(xiàn)App的抄襲檢測(cè)[7, 10, 17, 19, 159-168], 主要是通過分析App的詞法、語法及結(jié)構(gòu)特征來構(gòu)造胎記。DroidMoss[7]通過反編譯獲取App的字節(jié)碼, 利用模糊哈希技術(shù)將字節(jié)碼序列切分成不等長(zhǎng)片段并計(jì)算Hash值, 將所有片段的Hash值作為軟件胎記, 最后通過計(jì)算胎記間的編輯距離衡量相似性。同樣地利用字節(jié)碼序列, Ko等[159]將整個(gè)序列切分成一系列k-gram作為胎記, Juxapp[160]則以基本塊為單位利用k-gram及特征哈希構(gòu)造胎記, Juxapp還借助Hadoop框架提高檢測(cè)效率。WuKong[19]提出了兩階段的抄襲檢測(cè)應(yīng)對(duì)時(shí)間復(fù)雜度高的問題, 其首先構(gòu)造粗粒度的API胎記篩選出相似性較高的可疑程序, 然后再進(jìn)行細(xì)粒度的指令級(jí)分析。不難理解, 這些基于詞法分析的胎記很容易被簡(jiǎn)單的代碼混淆如垃圾指令植入、代碼重排破壞掉。

Potharaju[161]構(gòu)造方法的抽象語法樹, 將樹中所有的水平及縱向路徑作為胎記; 該方法考慮更多的語法及結(jié)構(gòu)特征, 但依然難以抵御復(fù)雜的混淆手段。通過挖掘控制及數(shù)據(jù)依賴關(guān)系, 也出現(xiàn)一些基于圖的軟件胎記[10,17,162-165]。DroidSim[162]通過分析API間的控制流依賴關(guān)系, 構(gòu)建基于組件的控制流圖胎記CB-CFG并通過子圖同構(gòu)實(shí)現(xiàn)相似性計(jì)算; Chen等[10]為CFG中每個(gè)頂點(diǎn)定義一個(gè)坐標(biāo), 將CFG視作幾何圖形, 提出基于幾何特征的胎記, 該方法極大地提高相似性計(jì)算效率, 可以應(yīng)用于大規(guī)模的抄襲檢測(cè)。這兩種基于CFG的方法可以有效地檢測(cè)語法相似的程序, 但難以應(yīng)對(duì)諸如方法拆分、內(nèi)聯(lián)、控制流混淆等代碼變換手段。DNADroid[163]使用基于程序依賴圖PDG的軟件胎記提高抗混淆能力, 并利用子圖同構(gòu)實(shí)現(xiàn)相似性計(jì)算, 但性能開銷導(dǎo)致其難以大規(guī)模應(yīng)用; AnDarwin[164]對(duì)其在性能上進(jìn)行了優(yōu)化,將PDG轉(zhuǎn)成語義向量并借助LSH實(shí)現(xiàn)相似性計(jì)算?；赑DG的胎記方法可以有效地應(yīng)對(duì)控制流混淆、垃圾指令植入等手段, 但采用特定的數(shù)據(jù)混淆可以躲避檢測(cè)。

除了采用經(jīng)典的CFG和PDG外, 也有研究[17,165,169-171]利用App用戶界面及其交互豐富的特點(diǎn), 通過分析UI接口及其布局特點(diǎn)等設(shè)計(jì)新的軟件胎記。Yang等[170]提出Attribute UI Graph(AUIG)胎記并通過子圖同構(gòu)計(jì)算相似性。ViewDroid[165]通過分析可操作的用戶接口及接口間的跳轉(zhuǎn)關(guān)系構(gòu)建View Graph, 進(jìn)行特征抽取提出FVG(Feature View Graph)胎記; ResDroid[17]除了利用用戶接口的跳轉(zhuǎn)關(guān)系外, 還利用接口的布局信息來構(gòu)建胎記。不同于前面的方法, DVFB[169]通過動(dòng)態(tài)執(zhí)行App實(shí)現(xiàn)View信息的收集和胎記構(gòu)建, 其采用LSH和最大雙邊匹配實(shí)現(xiàn)相似性衡量, 是目前唯一已知的針對(duì)移動(dòng)應(yīng)用抄襲檢測(cè)的動(dòng)態(tài)胎記?；赨I接口的胎記不容易被代碼混淆破壞掉, 但抄襲者可以通過虛擬視圖植入改變FVG的結(jié)構(gòu), 同時(shí)這些胎記不適用于視圖較少的App。

可以看出, 盡管目前也出現(xiàn)了許多基于胎記的App抄襲檢測(cè)方法, 但都還處于起始階段。大部分方法停留在詞法及語法分析層面, 對(duì)代碼混淆的抵抗力不強(qiáng); 少數(shù)方法盡管可以具備較高的抗混淆能力,但胎記構(gòu)建及比較所帶來的時(shí)間及性能開銷導(dǎo)致是其難以得到大規(guī)模應(yīng)用。此外, 鑒于移動(dòng)平臺(tái)App數(shù)量非常龐大, 目前幾乎所有方法均采用靜態(tài)分析,以犧牲抗混淆能力為代價(jià)換取可擴(kuò)展性。然而靜態(tài)胎記存在先天的局限性, 比如難以應(yīng)對(duì)諸如加殼、采用動(dòng)態(tài)加載技術(shù)等的混淆手段; 動(dòng)態(tài)胎記可以處理這些情況, 然而又面臨時(shí)空開銷大的問題。因而, 如何在保證可擴(kuò)展性的同時(shí), 結(jié)合動(dòng)靜態(tài)分析的優(yōu)勢(shì)設(shè)計(jì)抗混淆能力更強(qiáng)的胎記技術(shù), 將會(huì)是非常重要同時(shí)也非常有趣的研究方向。

此外, 隨著云平臺(tái)的興起, 有研究[172,173]開始關(guān)注云平臺(tái)上的軟件抄襲問題, Yu等[173]給出了云端軟件抄襲的威脅模型, 并提出了一種適用于云架構(gòu)的水印技術(shù), 其依然采用傳統(tǒng)的水印算法, 但利用Hadoop的MapReduce編程框架實(shí)現(xiàn)并行的水印植入和檢測(cè)。該研究還比較初步, 但云平臺(tái)上的軟件抄襲檢測(cè)不失為一個(gè)非常有趣的研究點(diǎn)。

6.2 多線程程序的抄襲檢測(cè)研究

從個(gè)人PC到智能手機(jī)再到服務(wù)器, 普遍都采用多核處理器, 為了更充分地利用多核帶來的性能提升, 運(yùn)行的軟件也必須是多線程的; 多線程編程變得越來越流行, 也必然是將來軟件的發(fā)展趨勢(shì)。前面提到動(dòng)態(tài)軟件胎記技術(shù)是實(shí)現(xiàn)抄襲檢測(cè)的一種行之有效的方法, 其相比靜態(tài)胎記而言能更有效地應(yīng)對(duì)代碼混淆攻擊; 然而動(dòng)態(tài)胎記技術(shù)本質(zhì)上是基于程序執(zhí)行行為的相似性判定抄襲, 而多線程程序線程交織的不確定性會(huì)使得執(zhí)行行為發(fā)生很大的改變,比如對(duì)于一個(gè)具有n個(gè)線程, 每個(gè)線程執(zhí)行k步的程序, 其線程交織的可能性高達(dá)種,這必然會(huì)大大影響傳統(tǒng)動(dòng)態(tài)胎記的檢測(cè)效果。Tian等[174]的研究工作也證實(shí)即使對(duì)于同一個(gè)多線程程序,用相同輸入執(zhí)行多次, 采用傳統(tǒng)的動(dòng)態(tài)胎記技術(shù)如SCSSB、DYKIS等為每次執(zhí)行抽取胎記并進(jìn)行比較,會(huì)將同一個(gè)程序判定為不存在抄襲。

為此, Tian等[174]提出了線程感知胎記(Thread-Aware Birthmark)的概念, 并提出TAB框架減小線程交織對(duì)傳統(tǒng)動(dòng)態(tài)胎記的影響。他們的基本假設(shè)是盡管線程交織可以非常復(fù)雜, 但每個(gè)線程內(nèi)部事件(指令、API調(diào)用等等)發(fā)生的次序是相對(duì)固定有序的。圖6簡(jiǎn)要描述了 TAB 框架: 給定一條執(zhí)行軌跡, TAB 首先將該軌跡中的每一個(gè)事件按照其所在線程進(jìn)行投影, 形成一系列的線程切片(一個(gè)切片就是一條子序列); 然后為每個(gè)線程切片單獨(dú)構(gòu)建切片胎記, 再將所有的切片胎記進(jìn)行融合以構(gòu)建軟件胎記。對(duì)于切片胎記的構(gòu)建, 可以沿用其他經(jīng)典的動(dòng)態(tài)胎記算法; 對(duì)于切片胎記的融合, TAB提供了切片聚合(Slice Aggregation, SA)和切片集(Slice Set, SS)模型生成線程感知胎記。

圖6 TAB框架

這樣的好處在于, TAB作為一個(gè)框架, 可以很容易地將傳統(tǒng)動(dòng)態(tài)胎記擴(kuò)展成線程感知胎記。Tian等利用TAB框架對(duì)SCSSB、DYKIS及JBirth進(jìn)行了擴(kuò)展, 實(shí)驗(yàn)表明擴(kuò)展后的胎記在處理多線程程序時(shí)相比原來檢測(cè)效果得到大幅度提升。隨后, Tian等又提出TreSB[175]和TreCxtB[176], 其利用線程相關(guān)的系統(tǒng)調(diào)用構(gòu)造胎記; 其基本假設(shè)是線程相關(guān)的系統(tǒng)調(diào)用是實(shí)施及影響程序交織行為而非被影響的元素, 因而利用這些系統(tǒng)調(diào)用構(gòu)建的胎記也更不易被交織影響, 實(shí)驗(yàn)表明TreSB及TreCxtB的檢測(cè)效果均優(yōu)于SCSSB及TAB擴(kuò)展后的SCSSB。

然而目前的方法還比較初步。TAB的假設(shè)不完全正確, 線程間的交互和相互影響可能會(huì)導(dǎo)致每個(gè)線程內(nèi)發(fā)生的事件產(chǎn)生變化; 此外, 進(jìn)行線程切片盡管可以減小交織帶來的影響, 但同時(shí)使得胎記難以捕捉程序的整體行為, 特別是對(duì)于線程間交互特別復(fù)雜的程序?qū)?huì)產(chǎn)生很多漏報(bào)。TreSB及TreCxtB對(duì)當(dāng)下主流的代碼混淆具備很強(qiáng)的抵抗力, 但不難通過諸如隨機(jī)植入lock/unlock或增加單獨(dú)線程引入額外線程相關(guān)系統(tǒng)調(diào)用等方式挫敗TreSB和TreCxtB。目前沒有專門針對(duì)多線程程序設(shè)計(jì)的混淆手段, 然而一旦類似TAB、TreSB以及TreCxtB的線程感知胎記得到關(guān)注, 必然會(huì)出現(xiàn)針對(duì)性的混淆手段。多線程編程必然是未來軟件開發(fā)的主流, 多線程程序的抄襲檢測(cè)也必然是未來非常重要的一個(gè)研究方向。

6.3 部分抄襲問題

目前絕大多數(shù)的抄襲檢測(cè)研究都是針對(duì)整體抄襲問題, 也就是抄襲者花費(fèi)很少的精力通過直接拷貝、自動(dòng)化混淆或較少人工修改將他人軟件擁為己有的情況。整體抄襲很常見也是非常重要的問題, 比如學(xué)生作業(yè)的抄襲、Android重打包等均屬于整體抄襲的范疇。

然而, 另一種普遍存在的情況是抄襲者僅僅將其他軟件的一部分如某個(gè)模塊或庫(kù)代碼集成到自己軟件中, 也就是部分抄襲問題。對(duì)于部分抄襲問題,最先想到的會(huì)是采取靜態(tài)分析來實(shí)現(xiàn), 因?yàn)殪o態(tài)分析可以隨意地提取可疑的程序部分展開分析; 水印技術(shù)顯然并不適用, 現(xiàn)有源碼抄襲檢測(cè)技術(shù)以及靜態(tài)胎記技術(shù)中有不少針對(duì)函數(shù)層面的分析方法, 可適用于程序局部模塊的分析, 通過適當(dāng)調(diào)整應(yīng)當(dāng)可以很容易用于部分抄襲檢測(cè)。不過正如前文提到的靜態(tài)分析存在不少局限性, 如不抗混淆、難以處理加殼程序等。

那么另一種選擇是采用動(dòng)態(tài)胎記技術(shù), 然而應(yīng)用動(dòng)態(tài)分析的一個(gè)難點(diǎn)在于很難單獨(dú)抽取出原告以及被告可疑的部分, 因?yàn)閯?dòng)態(tài)分析需要運(yùn)行程序,而很多情況下可疑模塊無法有效地從程序中簡(jiǎn)單剝離出來單獨(dú)運(yùn)行。SCDG[11]及HGB[27]這兩個(gè)動(dòng)態(tài)胎記技術(shù)做了初步嘗試, 盡管可以實(shí)現(xiàn)部分抄襲檢測(cè),但需要較大的人為參與, 比如需要人為地事先從原告代碼中抽取出可疑部分并構(gòu)造成可執(zhí)行程序, 或者通過標(biāo)定來人為地選擇監(jiān)控程序的特定部分。因而, 實(shí)現(xiàn)部分抄襲檢測(cè), 特別是抗混淆、自動(dòng)化的部分抄襲檢測(cè)依然是一個(gè)非常具有挑戰(zhàn)性的問題。

6.4 抄襲定位及證據(jù)生成研究

現(xiàn)有抄襲檢測(cè)研究普遍忽視的另一個(gè)重要問題是抄襲的定位問題, 相比于簡(jiǎn)單地輸出原告及被告的相似值或事先植入的水印信息, 終端用戶更加關(guān)心的是原告及被告中哪些部分存在抄襲以及存在抄襲部分之間的的對(duì)應(yīng)關(guān)系。源碼抄襲檢測(cè)中基于token方法的JPlag[68]和Moss[39]除了給出原告及被告的相似性外, 還可以將相似的對(duì)應(yīng)代碼塊的匹配關(guān)系展示給用戶; 然而基于token的方法難以有效對(duì)抗混淆攻擊, 因而如何對(duì)其進(jìn)行有效地借鑒, 使其他抄襲檢測(cè)方法特別是高度抗混淆的動(dòng)態(tài)胎記技術(shù)也能實(shí)現(xiàn)原告及被告匹配模塊的對(duì)照將會(huì)是非常有趣也很重要的研究?jī)?nèi)容。

一個(gè)更具挑戰(zhàn)性的問題是抄襲證據(jù)的生成。抄襲檢測(cè)技術(shù)原本設(shè)計(jì)的目的就是搜集并提供盡可能多的證據(jù), 從而在進(jìn)行法律訴訟時(shí)提供充分的技術(shù)支持。然而將水印或胎記作為抄襲證據(jù)粒度過粗, 即使像JPlag和Moss給出相似代碼塊的匹配關(guān)系, 也不足以到達(dá)作為證據(jù)的要求。Cosma等[23]提出的PGQT方法通過衡量匹配的代碼塊對(duì)最終判定抄襲的關(guān)鍵程度, 評(píng)估其作為證據(jù)的貢獻(xiàn)度, 這是證據(jù)生成的一個(gè)很好思路, 起到了拋磚引玉的作用。此外,在定位給出匹配的代碼塊基礎(chǔ)上, 對(duì)高貢獻(xiàn)度的代碼塊如能證明其語義等價(jià)性, 甚至通過分析能夠挖掘出原告代碼塊到被告代碼塊的變換手段, 實(shí)現(xiàn)變換過程的重放, 將會(huì)是非常強(qiáng)有力的證據(jù), 當(dāng)然這將會(huì)是一項(xiàng)非常有挑戰(zhàn)性的研究, 但也是抄襲檢測(cè)技術(shù)得到實(shí)際應(yīng)用必須要面臨和解決的問題。

7 結(jié)束語

軟件抄襲作為一種非法拷貝并使用他人代碼的行為, 已然對(duì)軟件生態(tài)環(huán)境的健康發(fā)展構(gòu)成嚴(yán)重威脅, 其得到越來越多的研究人員、教育者、開源社區(qū)以及軟件企業(yè)等的學(xué)術(shù)界和工業(yè)界的普遍關(guān)注, 也必然會(huì)得到包括知識(shí)產(chǎn)權(quán)局等在內(nèi)的政府監(jiān)管部門的重視。目前, 已提出了大量的軟件抄襲檢測(cè)技術(shù),并出現(xiàn)了一些相對(duì)成熟的檢測(cè)工具和系統(tǒng)。本文對(duì)該領(lǐng)域的研究成果進(jìn)行回顧: 首先介紹了軟件抄襲檢測(cè)的一些關(guān)鍵問題; 然后依據(jù)應(yīng)用場(chǎng)景和具體技術(shù)的不同, 將主流的抄襲檢測(cè)分為三類分別進(jìn)行總結(jié), 詳細(xì)介紹了針對(duì)源碼的抄襲檢測(cè)技術(shù), 以及無源碼場(chǎng)景下基于軟件水印和軟件胎記的抄襲檢測(cè)技術(shù), 并對(duì)各類抄襲檢測(cè)技術(shù)進(jìn)行了系統(tǒng)的比較和分析。最后, 梳理了隨著新平臺(tái)的出現(xiàn)、軟件發(fā)展趨勢(shì)的變化等, 抄襲檢測(cè)面臨的新問題和挑戰(zhàn), 探討了可能的應(yīng)對(duì)之策, 并對(duì)未來的研究方向進(jìn)行了展望。

軟件抄襲檢測(cè)是一個(gè)比較復(fù)雜的問題, 其涉及教育學(xué)、法律學(xué)和技術(shù)等多個(gè)方面。檢測(cè)技術(shù)僅僅是從技術(shù)的角度輔助決策者作出決策, 比如通過預(yù)篩選存在潛在抄襲的學(xué)生作業(yè), 減輕教育人員對(duì)上機(jī)作業(yè)的人工審查壓力, 提高教學(xué)效果; 識(shí)別存在潛在抄襲的移動(dòng)App, 減輕移動(dòng)平臺(tái)審查員的審查工作, 提升移動(dòng)平臺(tái)App的質(zhì)量和安全性; 從技術(shù)角度盡可能地搜集證據(jù), 為抄襲案件的法律訴訟提供技術(shù)支持等?？傮w而言, 目前的抄襲檢測(cè)研究還比較初步, 在應(yīng)對(duì)復(fù)雜多樣的抄襲手段及實(shí)際應(yīng)用方面還存在很大的局限性, 同時(shí)軟件發(fā)展的新趨勢(shì)如移動(dòng)及云平臺(tái)軟件開發(fā)、多線程編程等也給抄襲檢測(cè)研究帶來新的問題和挑戰(zhàn)。因此, 迫切需要學(xué)術(shù)界、企業(yè)界乃至社會(huì)監(jiān)管部門一起對(duì)抄襲問題進(jìn)行深入的理解和探討, 這是幫助軟件抄襲檢測(cè)技術(shù)得到更好地發(fā)展與成功應(yīng)用的關(guān)鍵。

[1] D. Chuda, P. Navrat, B. Kovacova, and P. Humay, "The Issue of (Software) Plagiarism: A Student View, "IEEE Transactions on Education, vol. 55, no. 1, pp. 22-28, 2012.

[2] F. Rosales, A. Garcia, S. Rodriguez, J.L. Pedraza, R. Mendez, and M.M. Nieto, "Detection of Plagiarism in Programming Assignments, "IEEE Transactions on Education, vol. 51, no. 2, pp. 174-183, 2008.

[3] T. Lancaster and F. Culwin, "A Comparison of Source Code Plagiarism Detection Engines, " Computer Science Education, vol. 14, no. 2, pp. 101-112, 2004.

[4] "Lawsuits On Open Source, " http://sourceauditor.com/blog/opensource- compliance-trend/.

[5] "Skype-Jotlid Dispute, " http://www.martinsuter.net/blog/2009/08/ skype- joltidlicensing-dispute-epic-ma-screwup.html.

[6] L.N. Luo, F. Yu, D.H. Wu, S.C. Zhu, and P. Liu, "Repackage-Proofing Android Apps, " inThe IEEE/IFIP International Conference on Dependable Systems and Networks (DSN'16).

[7] W. Zhou, Y. J. Zhou, X.X. Jiang, and P. Ning, "Detecting Repackaged Smartphone Applications in Third-Party Android Marketplaces, " inProceedings of the second ACM conference on Data and Application Security and Privacy (CODASPY '12), pp. 317-326, 2012.

[8] K. Chen, P. Wang, Y. Lee, X.F. Wang, N. Zhang, H.Q. Huang, W. Zou, and P. Liu, "Finding Unknown Malice in 10 Seconds: Mass Vetting for New Threats at the Google-Play Scale, " inUSENIX Security Symposium (USENIX Security'15), pp. 659-674, 2015.

[9] Y.-C. Jhi, X.R. Wang, X.Q. Jia, S.C. Zhu, P. Liu, and D.H. Wu, "Value-Based Program Characterization and its Application to Software Plagiarism Detection, " inProc. Int. Conf. Softw. Eng. (ICSE'11), pp. 756-765, 2011.

[10] K. Chen, P. Liu, and Y. Zhang, "Achieving Accuracy and Scalability Simultaneously in Detecting Application Clones On Android Markets, " inProc. Int. Conf. Sof. Eng.(ICSE'14), pp. 175-186, 2014.

[11] X. R. Wang, Y.-C. Jhi, S.C. Zhu, and P. Liu, "Behavior Based Software Theft Detection, " inProc. ACM Conf. Computer and Communications Security (CCS'09), pp. 280-290, 2009.

[12] L.N. Luo, J. Ming, D.H. Wu, P. Liu, and S.C. Zhu, "Semantics-Based Obfuscation-Resilient Binary Code Similarity Comparison with Applications to Software Plagiarism Detection, " inProc. ACM SIGSOFT Symp. Found. Softw. Eng. (FSE'14), pp. 389-400, 2014.

[13] D. Schuler, V. Dallmeier, and C. Lindig, "A Dynamic Birthmark for Java, " inProc. IEEE/ACM Int. Conf. Automated Software Engineering (ASE'07), pp. 274-283, 2007.

[14] C.G. Ren, K. Chen, and P. Liu, "Droidmarking: Resilient Software Watermarking for Impeding Android Application Repackaging, " inProceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering (ASE'14), pp. 635-646, 2014.

[15] C. Collberg and C. Thomborson, "Software Watermarking: Models and Dynamic Embeddings, " inACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'99), pp. 311-324, 1999.

[16] X.R. Wang, Y.-C. Jhi, S.C. Zhu, and P. Liu, "Detecting Software Theft Via System Call Based Birthmarks, " inAnnual Computer Security Applications Conference (ACSAC'09), pp. 149-158, 2009. [17] Y.R. Shao, X.P. Luo, C.X. Qian, P.F. Zhu, and L. Zhang, "Towards a Scalable Resource-Driven Approach for Detecting Repackaged Android Applications, " inAnnual Computer Security Applications Conference (ACSAC'14), pp. 56-65, 2014.

[18] F.F. Zhang, Y.-C. Jhi, D.H. Wu, P. Liu, and S.C. Zhu, "A First Step Towards Algorithm Plagiarism Detection, " inProc. Int. Symp. Software Testing and Analysis (ISSTA'12), pp. 111-121, 2012.

[19] H.Y. Wang, Y. Guo, Z. Ma, and X.Q. Chen, "WuKong: A Scalable and Accurate Two-Phase Approach to Android App Clone Detection, " inProceedings of the 2015 International Symposium on Software Testing and Analysis (ISSTA'15), pp. 71-82, 2015.

[20] Z.Z. Tian, Q.H. Zheng, T. Liu, M. Fan, E.Y. Zhuang, and Z.J. Yang, "Software Plagiarism Detection with Birthmarks Based On Dynamic Key Instruction Sequences, "IEEE Trans. Software Engineering, vol. PP, no. 99, pp. 1, 2015.

[21] C.S. Collberg and C. Thomborson, "Watermarking, Tamper-Proofing, and Obfuscation-Tools for Software Protection, "IEEE Trans. Software Engineering, vol. 28, no. 8, pp. 735-746, 2002.

[22] Y.-C. Jhi, X.Q. Jia, X.R. Wang, S.C. Zhu, P. Liu, and D.H. Wu, "Program Characterization Using Runtime Values and its Application to Software Plagiarism Detection, " IEEE Trans. Software Engineering, vol. 41, no. 9, pp. 925-943, 2015.

[23] G. Cosma and M. Joy, "An Approach to Source-Code Plagiarism Detection and Investigation Using Latent Semantic Analysis, "IEEE Trans. Computers, vol. 61, pp. 379-394, 2012.

[24] R.A. Jarvis and E.A. Patrick, "Clustering Using a Similarity Measure Based On Shared Near Neighbors, "IEEE Trans. Computers, vol. 100, no. 11, pp. 1025-1034, 1973.

[25] C. Liu, C. Chen, J.W. Han, and P.S. Yu, "GPLAG: Detection of Software Plagiarism by Program Dependence Graph Analysis, " inProc. ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD'06), pp. 872-881, 2006.

[26] S. Chaki, C. Cohen, and A. Gurfinkel, "Supervised Learning forProvenance-Similarity of Binaries, " inProc. ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD '11), pp. 15-23, 2011.

[27] P.P.F. Chan, L.C.K. Hui, and S.M. Yiu, "Heap Graph Based Software Theft Detection, "IEEE Trans. Information Forensics and Security, vol. 8, no. 1, pp. 101-110, 2013.

[28] H. Xiong, H.H. Yan, T. Guo, Y.G. Huang, Y.L. Hao, and Z.J. Li, "Code Similarity Detection: A Survey, "Computer Science, vol. 37, no. 8, pp. 9-14, 2010. (李舟軍, 熊浩, 晏海華, “代碼相似性檢測(cè)技術(shù): 研究綜述”,計(jì)算機(jī)科學(xué), 2010, 37(08): 9-14。)

[29] "Sandmark, " http: //sandmark.cs.arizona.edu/.

[30] "Zelix Klassmaster, " http: //www.zelix.com/klassmaster/.

[31] "DashO, " https: //www.preemptive.com/products/dasho.

[32] "DexGuard, " https: //www.guardsquare.com/dexguard.

[33] M. Madou, L. Van Put, and K. De Bosschere, "LOCO: An Interactive Code (De)Obfuscation Tool, " inProc. ACM SIGPLAN Symp. Partial Evaluation and Semantics-based Program Manipulation (PEPM'06), pp. 140-144, 2006.

[34] "Upx, " http: //upx.sourceforge.net/.

[35] "ProGuard, " http: //proguard.sourceforge.net/.

[36] C. Collberg, C. Thomborson, and D. Low, "A Taxonomy of Obfuscating Transformations, " Technical Report #148, Department of Computer Science, University of Auckland, 1997.

[37] Z. Wu, S. Gianvecchio, M. Xie, and H. Wang, "Mimimorphism: A New Approach to Binary Code Obfuscation, " inProc. ACM Conf. Computer and Communications Security (CCS'10), pp. 536-546, 2010.

[38] K.A. Roundy and B.P. Miller, "Binary-Code Obfuscations in Prevalent Packer Tools, "ACM Computing Surveys, vol. 46, no. 4, 2013.

[39] "Moss-a System for Detecting Software Plagiarism, " http://theory. stan ford.edu/～aiken/moss/.

[40] "Jplag, " https: //jplag.ipd.kit.edu/.

[41] "Sherlock, " http://www2.warwick.ac.uk/fac/sci/dcs/research/ias/ software/ sherlock/.

[42] R. Brixtel, M. Fontaine, B. Lesner, C. Bazin, and R. Robbes, "Language-Independent Clone Detection Applied to Plagiarism Detection, " inIEEE Working Conference on Source Code Analysis and Manipulation (SCAM'10), pp. 77-86, 2010.

[43] T. Kamiya, S. Kusumoto, and K. Inoue, "CCFinder: A Multilinguistic Token-Based Code Clone Detection System for Large Scale Source Code, "IEEE Trans. Software Engineering, vol. 28, no. 7, pp. 654-670, 2002.

[44] H.J. Kim, Y.B. Jung, S.H. Kim, and K.K. Yi, "MeCC: Memory Comparison-Based Clone Detector, " inProc. Int. Conf. Softw. Eng. (ICSE'11), pp. 301-310, 2011.

[45] C.K. Roy and J.R. Cordy, "A Survey On Software Clone Detection Research, " SCHOOL OF COMPUTING TR 2007-541, QUEEN'S UNIVERSITY, vol. 115, 2007.

[46] G. Whale, "Plague: Plagiarism Detection Using Program Structure, " Comput. Sci., Univ. New South, 1988.

[47] E.L. Jones, "Metrics Based Plagiarism Monitoring, "Journal of Computing Sciences in Colleges, vol. 16, no. 4, pp. 253-261, 2001. [48] J.A.W. Faidhi and S.K. Robinson, "An Empirical Approach for Detecting Program Similarity and Plagiarism within a University Programming Environment, "Computers & Education, vol. 11, no. 1, 1987.

[49] G. Whale, "Software Metrics and Plagiarism Detection, "Journal of Systems and Software, vol. 13, no. 2, pp. 131-138, 1990.

[50] K.J. Ottenstein, "An Algorithmic Approach to the Detection and Prevention of Plagiarism, "ACM Sigcse Bulletin, vol. 8, no. 4, pp. 30-41, 1976.

[51] M.H. Halstead, "Elements of Software Science, " Elsevier New York, 1977.

[52] M.H. Halstead, "Natural Laws Controlling Algorithm Structure?"ACM Sigplan Notices, vol. 7, no. 2, pp. 19-26, 1972.

[53] A.L.P.H. John L Donaldson, "A Plagiarism Detection System, "Computer Science Education, vol. 13, no. 1, pp. 21-25, 1981.

[54] S.L. Grier, "A Tool that Detects Plagiarism in Pascal Programs, "Computer Science Education, vol. 13, no. 1, pp. 15-20, 1981.

[55] H. Berghel and D.L. Sallach, "Measurements of Program Similarity in Identical Task Environments, "Sigplan Notices, pp. 65-76, 1984.

[56] M.J.W. Kristina L Verco, "Software for Detecting Suspected Plagiarism: Comparing Structure and Attribute-Counting Systems, "inAustralasian Conference on Computer Science Education (ACSE'96), pp. 81-88, 1996.

[57] S. Engels, V. Lakshmanan, and M. Craig, "Plagiarism Detection Using Feature-Based Neural Networks, " inSIGCSE Technical Symposium on Computer Science Education (SICCSE'07), pp. 34-38, 2007.

[58] L. Moussiades and A. Vakali, "PDetect: A Clustering Approach for Detecting Plagiarism in Source Code Datasets, "The Computer Journal, vol. 48, no. 6, pp. 651-661, 2005.

[59] L. Zhang, Y.T. Zhuang, and Z.M. Yuan, "A Program Plagiarism Detection Model Based On Information Distance and Clustering, " inInternational Conference on Intelligent Pervasive Computing (IPC'07), pp. 431-436, 2007.

[60] E. Merlo, "Detection of Plagiarism in University Projects Using Metrics-Based Spectral Similarity, " inDagstuhl Seminar Proceedings (DSP'07), 2007.

[61] V. Ciesielski, N. Wu, and S. Tahaghoghi, "Evolving Similarity Functions for Code Plagiarism Detection, " inProceedings of the10th Annual Conference on Genetic and Evolutionary Computation (GECCO'08), pp. 1453-1460, 2008.

[62] M. Joy and M. Luck, "Plagiarism in Programming Assignments, "IEEE Transactions on Education, vol. 42, no. 2, pp. 129-133, 1999.

[63] G. Whale, "Identification of Program Similarity in Large Populations, "The Computer Journal, vol. 33, no. 2, pp. 140-146, 1990.

[64] M.J. Wise, "Detection of Similarities in Student Programs: YAP'ing May be Preferable to Plague'ing, " inSIGCSE Technical Symposium on Computer Science Education (SIGCSE'92), pp. 268-271, 1992.

[65] M.J. Wise, "YAP3: Improved Detection of Similarities in Computer Program and Other Texts, " inSIGCSE Technical Symposium on Computer Science Education (SIGCSE'96), pp. 130-134, 1996. [66] R.M. Karp and M.O. Rabin, "Efficient Randomized Pattern-Matching Algorithms, "IBM Journal of Research and Development, vol. 31, no. 2, pp. 249-260, 1987.

[67] D. Gitchell and N. Tran, "SIM: A Utility for Detecting Similarity in Computer Programs, " inSIGCSE technical symposium on Computer science education (SIGCSE'99), pp. 266-270, 1999.

[68] L. Prechelt, G. Malpohl, and M. Philippsen, "Finding Plagiarisms Among a Set of Programs with Jplag, "Journal of Universal Computer Science, vol. 8, no. 11, pp. 1016-1038, 2002.

[69] C.H. Zhao, H.H. Yan, and M.Z. Jin, "Approach based on Compiling Optimization and Disassembling to Detect Program Similarity, "Journal of Beijing University of Aeronautics and Astronautics, vol. 32, no. 6, pp. 711-715, 2008. (金茂忠, 趙長(zhǎng)海, 晏海華, “基于編譯優(yōu)化和反匯編的程序相似性檢測(cè)方法”, 北京航空航天大學(xué)學(xué)報(bào), 2008, 32(06): 711-715。)

[70] C. Arwin and S.M. Tahaghoghi, "Plagiarism Detection Across Programming Languages, " inProceedings of the 29th Australasian Computer Science Conference (ACSC'06), pp. 277-286, 2006.

[71] V. Juricic, "Detecting Source Code Similarity Using Low-Level Languages, " inInternational Conference on Information Technology Interfaces (ITI'11), pp. 597-602, 2011.

[72] X. Chen, B. Francia, and M. Li, "Shared Information and Program Plagiarism Detection, "IEEE Transactions on Information Theory, vol. 50, no. 7, pp. 1545-1551, 2004.

[73] K.L. Pandey, S. Agarwal, S. Misra, and R. Prasad, "Plagiarism Detection in Software Using Efficient String Matching, " inInternational Conference on Computational Science and Its Applications (ICCSA'12), pp. 147-156, 2012.

[74] M. Li and P. Vitanyi, "An Introduction to Kolmogorov Complexity and its Applications, "Springer-Verlag New York, 1997.

[75] J.W. Son, T.G. Noh, H.J. Song, and S.B. Park, "An Application for Plagiarized Source Code Detection Based On a Parse Tree Kernel, "Engineering Applications of Artificial Intelligence, vol. 26, no. 8, pp. 1911-1918, 2013.

[76] J.W. Son, S.B. Park, and S.Y. Park, "Program Plagiarism Detection Using Parse Tree Kernels, " inPacific Rim international conference on Artificial intelligence (PRICAI'06), pp. 1000-1004, 2006.

[77] C.L. Liu, S.Y. Jia, L.P. Zhang, and D.S. Liu, "AST-Based Plagiarism Detection Method, "Computer Engineering and Design, vol. 33, no. 4, pp. 1660-1664, 2012.

[78] H. Kikuchi, T. Goto, M. Wakatsuki, and T. Nishino, "A Source Code Plagiarism Detecting Method Using Alignment with Abstract Syntax Tree Elements, " inIEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD'14), pp. 1-6, 2014.

[79] T. Guo, G.W. Dong, H. Qin, and B.J. Cui, "Improved Plagiarism Detection Algorithm Based On Abstract Syntax Tree, " inInternational Conference on Emerging Intelligent Data and Web Technologies (EIDWT'13), pp. 714-719, 2013.

[80] H. Xiong, H.H. Yan, Z.J. Li, and H. Li, "BuAA_AntiPlagiarism: A System to Detect Plagiarism for C Source Code, " inInternational Conference on Computational Intelligence and Software Engineering (CiSE'09), pp. 1-5, 2009.

[81] N.G. Resmi and K.P. Soman, "Abstract Syntax Tree Generation Using Modified Grammar for Source Code Plagiarism Detection, "International Journal of Computing and Technology, vol. 1, no. 6, 2014.

[82] J.H. Ji, G. Woo, and H.G. Cho, "A Source Code Linearization Technique for Detecting Plagiarized Programs, " inProceedings of the Annual SIGCSE Conference on Innovation and Technology in Computer Science Education (ITiCSE'07), pp. 73-77, 2007.

[83] S.Y. Noh, "An Xml Plagiarism Detection Model for Procedural Programming Languages, " Iowa State University: Technical Report TR03-14, 2003.

[84] S.Y. Noh, S.W. Kim, and C.Y. Jung, "A Lightweight Program Similarity Detection Model Using Xml and Levenshtein Distance, " inInternational Conference on Frontiers in Education: Computer Science & Computer Engineering (ICFE-CSCE'06), pp. 3-9, 2006. [85] J. Krinke, "Identifying Similar Code with Program Dependence Graphs, " inWorking Conference on Reverse Engineering (WCRE'01), pp. 301-309, 2001.

[86] J. Nagra, C. Thomborson, and C. Collberg, "A Functional Taxonomy for Software Watermarking, " in Proceedings of the Australasian Conference on Computer Science (ACSC'02), pp. 177-186, 2002.

[87] L.H. Zhang, Y.X. Yang, X.X. Niu, and S.Z. Niu, "A Survey on Software Watermarking, "Journal of Software, vol. 14, no. 2, pp. 268-277, 2003. (張立和, 楊義先, 紐心忻, 牛少彰“軟件水印綜述”,軟件學(xué)報(bào),2003, 14(02): 268-277。)

[88] W. Zhu, C. Thomborson, and F.Y. Wang, "A Survey of Software Watermarking, " inIEEE International Conference on Intelligence and Security Informatics (ISI'05), 2005.

[89] J. Hamilton and S. Danicic, "A Survey of Static Software Watermarking, " inWorld Congress on Internet Security (WorldCIS'11), pp. 100-107, 2011.

[90] P.R. Samson, "Apparatus and Method for Serializing and Validating Copies of Computer Software, " no. US 07/938, 278 1994.

[91] R.I. Davidson and N. Myhrvold, "Method and System for Generating and Auditing a Signature for a Computer Program, " no. US 08/268, 967 1996.

[92] A. Monden, H. Iida, K.I. Matsumoto, K. Inoue, and K. Torii, "A Practical Method for Watermarking Java Programs, " inthe IEEE Computer Society International Conference on Computers, Software & Applications (COMPSAC'00), pp. 191-197, 2000.

[93] K. Fukushima and K. Sakurai, "A Software Fingerprinting Scheme for Java Using Classfiles Obfuscation, "Springer, 2003.

[94] S. Thaker, "Software Watermarking Via Assembly Code Transformations [Ph.D.dissertation], " San Jose State University, 2004.

[95] C. Collberg and T.R. Sahoo, "Software Watermarking in the Frequency Domain: Implementation, Analysis, and Attacks, "Journal of Computer Security, vol. 13, no. 5, pp. 721-755, 2005.

[96] G. Myles, C. Collberg, Z. Heidepriem, and A. Navabi, "The Evaluation of Two Software Watermarking Algorithms, "Software: Practice and Experience, vol. 35, no. 10, pp. 923-938, 2005.

[97] B. Anckaert, B. De Sutter, and K. De Bosschere, "Covert Communication through Executables, " pp. 83-85.

[98] M. Shirali-Shahreza and S. Shirali-Shahreza, "Software Watermarking by Equation Reordering, " inInternational Conference on Information and Communication Technologies: From Theory to Applications (ICTTA'08), pp. 1-4, 2008.

[99] Z.L. Sha, H. Jiang, and A.C. Xuan, "Software Watermarking Algorithm by Coefficients of Equation, " inInternational Conference on Genetic and Evolutionary Computing (WGEC'09), pp. 410-413, 2009.

[100] D.F. Gong, F.L. Liu, B. Lu, P. Wang, and L. Ding, "Hiding Information in Java Class File, " inComputer Science and Computational Technology (ISCSCT'08), pp. 160-164, 2008.

[101] J.P. Stern, G. Hachez, F. Koeune, and J. Quisquater, "Robust Object Watermarking: Application to Code, " inInformation Hiding (IH'99), pp. 368-378, 1999.

[102] F. Koushanfar, G. Qu, and M. Potkonjak, "Intellectual Property Metering, " inInformation Hiding (IH'01), 2001.

[103] G. Qu and M. Potkonjak, "Hiding Signatures in Graph Coloring Solutions, " inInformation Hiding (IH'99), pp. 348-367, 1999.

[104] G. Myles and C. Collberg, "Software Watermarking through Register Allocation: Implementation, Analysis, and Attacks, " inConference: Information Security and Cryptology (ICISC '03), pp. 274-293, 2003.

[105] W. Zhu and C. Thomborson, "Algorithms to Watermark Software through Register Allocation, " inInternatinal Conference on Digital Rights Management: Technologies, Issues, Challenges and Systems (DRMTICS'05), pp. 180-191, 2005.

[106] H. Lee and K. Kaneko, "New Approaches for Software Watermarking by Register Allocation, " inACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD'08), pp. 63-68, 2008.

[107] X.C. Lu and Z.M. Chen, "Software Watermarking Algorithm Based On Register Allocation, " inInternational Symposium on Distributed Computing and Applications to Business Engineering and Science (DCABES'10), pp. 539-543, 2010.

[108] R. Venkatesan, V. Vazirani, and S. Sinha, "A Graph Theoretic Approach to Software Watermarking, " inInformation Hiding (IH'01), pp. 157-168, 2001.

[109] C. Collberg, A. Huntwork, E. Carter, and G. Townsend, "Graph Theoretic Software Watermarks: Implementation, Analysis, and Attacks, " inInformation Hiding (IH'04), pp. 192-207, 2004.

[110] C. Collberg, A. Huntwork, E. Carter, G. Townsend, and M. Stepp, "More On Graph Theoretic Software Watermarks: Implementation, Analysis, and Attacks, "Information and Software Technology,vol. 51, no. 1, pp. 56-67, 2009.

[111] G. Arboit, "A Method for Watermarking Java Programs Via Opaque Predicates, " inthe Fifth International Conference on Electronic Commerce Research (ICECR'02), pp. 102-110, 2002.

[112] G. Myles and C. Collberg, "Software Watermarking Via Opaque Predicates: Implementation, Analysis, and Attacks, "ELECTRONIC COMMERCE RESEARCH, vol. 6, no. 2, pp. 155-171, 2006.

[113] P. Cousot and R. Cousot, "An Abstract Interpretation-Based Framework for Software Watermarking, " inProceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'04), pp. 173-185, 2004.

[114] J. Palsberg, S. Krishnaswamy, M. Kwon, D. Ma, Q.Y. Shao, and Y. Zhang, "Experience with Software Watermarking, " inAnnual Conference on Computer Security Applications (ACSAC'00), pp. 308-316, 2000.

[115] C. Collberg, S. Kobourov, E. Carter, and C. Thomborson, "Error-Correcting Graphs for Software Watermarking, " inWorkshop on Graph Theoretic Concepts in Computer Science (WGTCCS'03), pp. 156-167, 2003.

[116] C.S. Collberg, C. Thomborson, and G.M. Townsend, "Dynamic Graph-Based Software Fingerprinting, "ACM Transactions on Programming Languages and Systems, vol. 29, no. 6, pp. 35, 2007.

[117] C. Collberg, C. Thomborson, and G.M. Townsend, "Dynamic Graph-Based Software Watermarking, " TR04-08, Department of Computer Science, 2004.

[118] J.Q. Zhu, Y.H. Liu, and K.X. Yin, "A Novel Planar Ippct Tree Structure and Characteristics Analysis, "Journal of Software, vol. 5, no. 3, pp. 344-351, 2010.

[119] R. Venkatesan and V. Vazirani, "Technique for Producing through Watermarking Highly Tamper-Resistant Executable Code and Resulting “Watermarked” Code so Formed, " no. US 10/970, 425 2006.

[120] P. Zhou, X. Chen, and X.G. Yang, "The Software Watermarking for Tamper Resistant Radix Dynamic Graph Coding, "Information Technology Journal, vol. 9, no. 6, pp. 1236-1240, 2010.

[121] I. Kamel and Q. Albluwi, "A Robust Software Watermarking for Copyright Protection, "Computers & Security, vol. 28, no. 6, pp. 395-409, 2009.

[122] C.S. Collberg, E. Carter, S.K. Debray, A. Huntwork, J.D. Kececioglu, C. Linn, and M. Stepp, "Dynamic Path-Based Software Watermarking, " inProc. ACM SIGPLAN Conf. Programming Language Design and Implementation (PLDI'04), pp. 107-118, 2004.

[123] G. Myles and H.X. Jin, "Self-Validating Branch-Based Software Watermarking, " inInformation Hiding (IH'05), pp. 342-356, 2005. [124] J. Nagra and C. Thomborson, "Threading Software Watermarks, " inInformation Hiding (IH'04), pp. 208-223, 2004.

[125] M. Dalla Preda, R. Giacobazzi, and E. Visentini, "Hiding Software Watermarks in Loop Structures, " inInternational Symposium on Static Analysis (SAS'08), pp. 174-188, 2008.

[126] X.S. Zhang, F.L. He, and W.L. Zuo, "Hash Function Based Software Watermarking, " inAdvanced Software Engineering and Its Applications (ASEA'08), pp. 95-98, 2008.

[127] H.Y. Ma, K.J. Lu, X.J. Ma, H.N. Zhang, C.F. Jia, and D.B. Gao, "Software Watermarking Using Return-Oriented Programming, " inProceedings of the 10th ACM Symposium on Information, Computer and Communications Security (ASIA CCS'15), 2015.

[128] H. Tamada, M. Nakamura, and A. Monden, "Design and Evaluation of Birthmarks for Detecting Theft of Java Programs, " inIASTED Conf. on Software Engineering (IASTEDSE'04), pp. 569-574, 2004.

[129] H. Tamada, M. Nakamura, A. Monden, and K.I. Matsumoto, "Java Birthmarks--Detecting the Software Theft--, "IEICE Transactions on Information and Systems, vol. 88, no. 9, pp. 2148-2158, 2005.

[130] G. Myles and C. Collberg, "K-Gram Based Software Birthmarks, " inProc. ACM Symp. Applied Computing (SAC'05), pp. 314-318, 2005.

[131] X. Xie, F.L. Liu, B. Lu, and L. Chen, "A Software Birthmark Based On Weighted K-Gram, " inIEEE Int. Conf. IntelligentComputing and Intelligent Systems (ICIS'10), pp. 400-405, 2010.

[132] D.J. Kim, S.J. Cho, S.C. Han, M. Park, and I. You, "Open Source Software Detection Using Function-Level Static Software Birthmark, "Journal of Internet Services and Information Security (JISIS), vol. 4, no. 4, pp. 25-37, 2014.

[133] S. Choi, H. Park, H.I. Lim, and T. Han, "A Static API Birthmark for Windows Binary Executables, "Journal of Systems and Software, vol. 82, no. 5, pp. 862-873, 2009.

[134] S. Choi, H. Park, H. Lim, and T. Han, "A Static Birthmark of Binary Executables Based On API Call Structure, " inProceedings of the Asian Computing Science Conference on Advances in Computer Science: Computer and Network Security (ASIAN'07), pp. 2-16, 2007.

[135] H. Lim, H. Park, S. Choi, and T. Han, "A Method for Detecting the Theft of Java Programs through Analysis of the Control Flow Information, "Information and Software Technology, vol. 51, no. 9, pp. 1338-1350, 2009.

[136] H.I. Lim, H. Park, S. Choi, and T. Han, "A Static Java Birthmark Based On Control Flow Edges, " inAnnual IEEE International Computer Software and Applications Conference, (COMPSAC'09), pp. 413-420, 2009.

[137] H.I. Lim and T. Han, "Analyzing Stack Flows to Compare Java Programs, "IEICE Trans. Information and Systems, vol. 95-D, no. 2, pp. 565-576, 2012.

[138] H.I. Lim, P. Heewan, and H. Taisook, "Detecting Theft of Java Applications Via a Static Birthmark Based On Weighted Stack Patterns, "IEICE Transactions on Information and Systems, vol. 91, no. 9, pp. 2323-2332, 2008.

[139] H. Park, H.I. Lim, S. Choi, and T. Han, "Detecting Common Modules in Java Packages Based On Static Object Trace Birthmark, "Computer Journal, vol. 54, no. 1, pp. 108-124, 2011.

[140] S. Park, H. Kim, J. Kim, and H. Han, "Detecting Binary Theft Via Static Major-Path Birthmarks, " inProceedings of the 2014 Conference on Research in Adaptive and Convergent Systems (RACS'14), pp. 224-229, 2014.

[141] G. Myles and C. Collberg, "Detecting Software Theft Via Whole Program Path Birthmarks, " inProc. Int. Conf. Information Security (ISC'04), pp. 404-415, 2004.

[142] H. Tamada, K. Okamoto, M. Nakamura, A. Monden, and K.I. Matsumoto, "Dynamic Software Birthmarks to Detect the Theft of Windows Applications, " inInt. Symp. Future Software Technology (ISFST'04), 2004.

[143] H. Tamada, K. Okamoto, M. Nakamura, A. Monden, and K. Ichi Matsumoto, "Design and Evaluation of Dynamic Software Birthmarks Based On API Calls, " Nara Institute of Science & Technology, pp. 1751-1763, 2007.

[144] B. Lu, F. Liu, X. Ge, B. Liu, and X. Luo, "A Software BirthmarkBased On Dynamic Opcode N-Gram, " inInternational Conference on Semantic Computing (ICSC'07), pp. 37-44, 2007.

[145] Y.M. Bai, X.M. Sun, G. Sun, X.H. Deng, and X.M. Zhou, "Dynamic K-Gram Based Software Birthmark, " inAustralian Conference on Software Engineering (ASWEC'08), pp. 644-649, 2008. [146] Z.Z. Tian, Q.H. Zheng, T. Liu, and M. Fan, "DKISB: Dynamic Key Instruction Sequence Birthmark for Software Plagiarism Detection, " inIEEE Int. Conf. High Performance Computing and Communications (HPCC'13), pp. 619-627, 2013.

[147] P.P. Chan, L.C. Hui, and S.M. Yiu, "JSBiRTH: Dynamic Javascript Birthmark Based On the Run-Time Heap, " inIEEE Annual Computer Software and Applications Conference (COMPSAC'11), pp. 407-412, 2011.

[148] D. Chae, S. Kim, S. Cho, and Y. Kim, "DAAV: Dynamic Api Authority Vectors for Detecting Software Theft, " inACM International on Conference on Information and Knowledge Management (CIKM'15), pp. 1819-1822, 2015.

[149] D.K. Chae, S.W. Kim, S.J. Cho, and Y. Kim, "Effective and Efficient Detection of Software Theft Via Dynamic API Authority Vectors, "Journal of Systems and Software, vol. 110, pp. 1-9, 2015.

[150] J. Park, D. Son, D. Kang, J. Choi, and G. Jeon, "Software Similarity Analysis Based On Dynamic Stack Usage Patterns, " inConference on Research in Adaptive and Convergent Systems (RACS'15), pp. 285-290, 2015.

[151] "Stigmata, " http: //stigmata.osdn.jp/implementation.html.

[152] "JBirth, " https: //www.st.cs.uni-saarland.de/birthmarking/.

[153] "DBPD, " Z.Z. Tian, http://labs.xjtudlc.com/labs/wlaq/dbpd/site.

[154] "TAB-PD, " http://labs.xjtudlc.com/labs/wlaq/TAB-PD/site/index. html.

[155] J. Ming, F.F. Zhang, D.H. Wu, P. Liu, and S.C. Zhu, "Deviation-Based Obfuscation-Resilient Program Equivalence Checking with Application to Software Plagiarism Detection, "IEEE Trans. Reliability, 2016.

[156] F.F. Zhang, D.H. Wu, P. Liu, and S.C. Zhu, "Program Logic Based Software Plagiarism Detection, " inIEEE Int. Symp. Software Reliability Engineering (ISSRE'14), pp. 66-77, 2014.

[157] W. Yang, X.S. Xiao, D.F. Li, H.R. Li, H.Y. Wang, Y. Guo and T. Xie, "Security Analytics for Mobile Apps: Achievements and Challenges,"Journal of Cyber Security, vol. 1, no. 2, pp. 1-14, 2016. (楊威, 肖旭生, 李鄧鋒, 李豁然, 劉譞哲, 王浩宇, 郭耀, 謝濤,“移動(dòng)應(yīng)用安全解析學(xué): 成果與挑戰(zhàn)”,信息安全學(xué)報(bào), 2016, 1(2): 1-14。)

[158] W. Zhou, X.W. Zhang, and X.X. Jiang, "AppInk: Watermarking Android Apps for Repackaging Deterrence, " inProceedings of ACM SIGSAC Symposium on Information, Computer and Communications Security (ASIA CCS'13), pp. 1-12, 2013.

[159] J. Ko, H.J. Shim, D.J. Kim, Y.S. Jeong, S.J. Cho, M. Park, S. Han, and S.B. Kim, "Measuring Similarity of Android Applications Via Reversing and K-Gram Birthmarking, " inProceedings of the 2013 Research in Adaptive and Convergent Systems (RACS'13), pp. 336-341, 2013.

[160] S. Hanna, L. Huang, E. Wu, S. Li, C. Chen, and D. Song, "Juxtapp: A Scalable System for Detecting Code Reuse Among Android Applications, " inInternational Conference on Detection of Intrusions and Malware, and Vulnerability Assessment (DIMVA'12), pp. 62-81, 2012.

[161] R. Potharaju, A. Newell, C. Nita-Rotaru, and X. Zhang, "Plagiarizing Smartphone Applications: Attack Strategies and Defense Techniques, " inInternational Conference on Engineering Secure Software and Systems (ESSoS'12), pp. 106-120, 2012.

[162] X. Sun, Y. Zhongyang, Z. Xin, B. Mao, and L. Xie, "Detecting Code Reuse in Android Applications Using Component-Based Control Flow Graph, " inIFIP Advances in Information and Communication Technology (IFIP AICT'14), pp. 142-155, 2014.

[163] J. Crussell, C. Gibler, and H. Chen, "Attack of the Clones: Detecting Cloned Applications On Android Markets, " inEuropean Symposium on Research in Computer Security (ESORICS'13), pp. 37-54, 2012.

[164] J. Crussell, C. Gibler, and H. Chen, "AnDarwin: Scalable Detection of Semantically Similar Android Applications, " inEuropean Symposium on Research in Computer Security (ESORICS'13), pp. 182-199, 2013.

[165] F.F. Zhang, H.Q. Huang, S.C. Zhu, D.H. Wu, and P. Liu, "View-Droid: Towards Obfuscation-Resilient Mobile Application Repackaging Detection, " inProc. ACM Conf. Security and Privacy in Wireless and Mobile Networks (WiSec'14), pp. 25-36, 2014.

[166] H.Q. Huang, S.C. Zhu, P. Liu, and D.H. Wu, "A Framework for Evaluating Mobile App Repackaging Detection Algorithms, " inInternational Conference on Trust & Trustwor-thy Computing (TRUST'13), pp. 169-186, 2013.

[167] Q.L. Guan, H.Q. Huang, W.Q. Luo, and S.C. Zhu, "Semantics-Based Repackaging Detection for Mobile Apps, " Springer International Publishing, 2016.

[168] I. Gurulian, K. Markantonakis, L. Cavalaro, and K. Mayes, "You Can't Touch this: Consumer-Centric Android Application Repackaging Detection, "Future Generation Computer Systems, vol. 65, pp. 1-9, 2016.

[169] C. Soh, H.B.K. Tan, Y.L. Arnatovich, and L.P. Wang, "Detecting Clones in Android Applications through Analyzing User Interfaces, "inInternational Conference on Program Comprehension (ICPC'15), pp. 163-173, 2015.

[170] C.X. Yang, C.S. Zuo, S.Q. Guo, C.Y. Hu, and L.Z. Cui, "UI Ripping in Android: Reverse Engineering of Graphical User Interfacesand its Application, " inIEEE Conference on Collaboration and Internet Computing (CCIC'15), pp. 160-167, 2015.

[171] M. Sun, M. Li, and J.C.S. Lui, "DroidEagle: Seamless Detection of Visually Similar Android Apps, " inProceedings of the 8th ACM Conference on Security & Privacy in Wireless and Mobile Networks (WiSec'15), pp. 1-9, 2015.

[172] C.W. Wang, M.C.Y. Cho, C.W. Wang, and S.W. Shieh, "Combating Software Piracy in Public Clouds, "Computer, vol. 48, no. 10, pp. 88-91, 2015.

[173] Z.W. Yu, C.K. Wang, C. Thomborson, J.M. Wang, S.G. Lian, and A.V. Vasilakos, "A Novel Watermarking Method for Software Protection in the Cloud, "Software: Practice and Experience, vol. 42, no. 4, pp. 409-430, 2012.

[174] Z.Z. Tian, Q.H. Zheng, T. Liu, M. Fan, X.D. Zhang, and Z.J. Yang, "Plagiarism Detection for Multithreaded Software Based On Thread-Aware Software Birthmarks, " inProc. Int. Conf. Program Comprehension (ICPC'14), pp. 304-313, 2014.

[175] Z.Z. Tian, T. Liu, Q.H. Zheng, F.F. Tong, M. Fan, and Z.J. Yang, "A New Thread-Aware Birthmark for Plagiarism Detection of Multithreaded Programs, " inProceedings of the 38th International Conference on Software Engineering Companion (ICSE'16), pp. 734-736, 2016.

[176] Z.Z. Tian, T. Liu, Q.H. Zheng, M. Fan, E.Y. Zhuang, and Z.J. Yang, "Exploiting Thread-Related System Calls for Plagiarism Detection of Multithreaded Programs, "Journal of Systems and Software, 2016.

田振洲于2010年在西安交通大學(xué)計(jì)算機(jī)專業(yè)獲得工學(xué)學(xué)士學(xué)位?，F(xiàn)在西安交通大學(xué)計(jì)算機(jī)專業(yè)攻讀博士學(xué)位。研究領(lǐng)域?yàn)榭尚跑浖?。研究興趣包括: 軟件動(dòng)態(tài)行為分析、軟件抄襲檢測(cè)、惡意軟件分析。Email: zztian@stu.xjtu.edu.cn

劉烴于2010年在西安交通大學(xué)系統(tǒng)工程專業(yè)獲得博士學(xué)位。現(xiàn)任西安交通大學(xué)系統(tǒng)工程研究所副教授。研究領(lǐng)域包括: 網(wǎng)絡(luò)安全、智能電網(wǎng)、可信軟件。研究興趣包括: 智能電網(wǎng)漏洞挖掘與入侵檢測(cè)、軟件行為建模及分析。Email: tingliu@mail.xjtu.edu.cn

鄭慶華于1997年在西安交通大學(xué)系統(tǒng)工程專業(yè)獲得博士學(xué)位?，F(xiàn)任西安交通大學(xué)副校長(zhǎng)、計(jì)算機(jī)系主任。為國(guó)家杰出青年基金獲得者, 教育部長(zhǎng)江學(xué)者特聘教授,國(guó)家“新世紀(jì)百千萬人才工程”人選, 首批“萬人計(jì)劃”科技創(chuàng)新領(lǐng)軍人才, 教育部科技創(chuàng)新團(tuán)隊(duì)、陜西省重點(diǎn)科技創(chuàng)新團(tuán)隊(duì)負(fù)責(zé)人。研究領(lǐng)域包括: 計(jì)算機(jī)網(wǎng)絡(luò)安全、智能e-Learning環(huán)境的理論與技術(shù)、網(wǎng)絡(luò)輿情及有害信息監(jiān)控、可信軟件。Email: qhzheng@xjtu.edu.cn

吳定豪于2005年在普林斯頓大學(xué)計(jì)算機(jī)專業(yè)獲得博士學(xué)位, 現(xiàn)任賓夕法尼亞州立大學(xué)信息科學(xué)與技術(shù)學(xué)院助理教授, 研究興趣包括: 軟件安全、程序分析與驗(yàn)證、軟件工程和程序設(shè)計(jì)語言。Email: dwu@ist.psu.edu

陳愷于2010年在中國(guó)科學(xué)院大學(xué)獲得博士學(xué)位, 現(xiàn)在中國(guó)科學(xué)院信息工程研究所擔(dān)任研究員, 研究興趣包括軟件分析與測(cè)試、智能手機(jī)、隱私安全。Email: chenkai@ iie.ac.cn

佟菲菲于2015年在西安交通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)獲得工學(xué)學(xué)士學(xué)位。現(xiàn)在西安交通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)攻讀碩士學(xué)位。研究領(lǐng)域?yàn)榭尚跑浖?。研究興趣包括: 軟件抄襲檢測(cè)、軟件分析。Email: tongfeifei@stu.xjtu.edu.cn

朱森存于2004年在喬治梅森大學(xué)信息技術(shù)專業(yè)獲得博士學(xué)位, 現(xiàn)任賓夕法尼亞州立大學(xué)副教授。研究領(lǐng)域?yàn)榘踩c隱私, 研究興趣包括: 傳感器網(wǎng)絡(luò)安全、智能手機(jī)及蜂窩網(wǎng)絡(luò)安全、軟件安全、在線隱私和安全。Email: szhu@cse.psu.edu

Software Plagiarism Detection: A Survey

TIAN Zhenzhou1, LIU Ting1, ZHENG Qinghua1, TONG Feifei1, WU Dinghao2, ZHU Sencun2,3, CHEN Kai4

1Ministry of Education Key Lab For Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an 710049, China2Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA 16802, USA3College of Information Sciences and Technology, Pennsylvania State University, University Park, PA 16802, USA4Institute of Information Engineering, Chinese Academy of Science, Beijing 100093, China

With the burst of free and open source software projects, software plagiarism has become a serious threat to the healthy development of the software ecosystem. Researchers, educators, open source developers, and software company managers are paying more and more attention to the problem. Software plagiarism detection is critical to the protection of software intellectual property. This paper provides a review of the state-of-the-art software plagiarism detection techniques. First, the significance and threat models of plagiarism detection are presented, followed by the description and comparison of existing techniques on plagiarism detection. We classify the existing methods into three major categories, including source-code plagiarism detection, software watermark based plagiarism detection and software birthmark based plagiarism detection, according to the scenarios they are designed for and applicable to as well as different principles adopted. Finally, through analyzing the limitations of the existing plagiarism detection techniques, the emerging challenges and practical requirements, we discuss several possible future research directions.

intellectual property protection; software protection; software plagiarism; software plagiarism detection; software birthmark; code similarity analysis; software watermarking; code obfuscation

TP309.2 DOI號(hào) 10.19363/j.cnki.cn10-1380/tn.2016.03.005

劉烴, 博士, 副教授, Email: tingliu@mail.xjtu.edu.cn。

本課題得到國(guó)家自然科學(xué)基金(91118005, 91218301, 61221063, 61428206, 61203174, 91418205, 61472318, 1500365); 教育部創(chuàng)新團(tuán)隊(duì)(IRT13035); 國(guó)家科技支撐計(jì)劃( 2013BAK09B01)資助。

2016-06-26; 修改日期: 2016-07-07; 定稿日期: 2016-07-08