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

1西安交通大學 智能網絡與網絡安全教育部重點實驗室 西安 中國 7100492賓夕法尼亞州立大學帕克分校 計算機科學與工程系 美國 168023賓夕法尼亞州立大學帕克分校 信息科學與技術學院 美國 168024中國科學院信息工程研究所 北京 中國100093

軟件抄襲檢測研究綜述

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

1西安交通大學 智能網絡與網絡安全教育部重點實驗室 西安 中國 7100492賓夕法尼亞州立大學帕克分校 計算機科學與工程系 美國 168023賓夕法尼亞州立大學帕克分校 信息科學與技術學院 美國 168024中國科學院信息工程研究所 北京 中國100093

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

知識產權保護; 軟件保護; 軟件抄襲; 軟件抄襲檢測; 軟件胎記; 代碼相似性分析; 軟件水印; 代碼混淆

1 引言

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

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

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

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

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

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

2 軟件抄襲檢測的關鍵問題

2.1 理解軟件抄襲和抄襲檢測

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

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

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

C1)Q是P的直接拷貝;

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

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

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

C5)Q是通過對P反復應用上述修改得來的。

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

因此, 軟件抄襲檢測需要解決以下幾個關鍵問題:

1) 如何實現(xiàn)檢測過程的自動化或較少的人工參與;

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

3) 如何應對各式各樣的代碼混淆技術;

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

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

2.2 代碼混淆

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

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

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

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

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

2.3 軟件抄襲檢測技術分類

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

2.3.1 源碼抄襲檢測技術

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

2.3.2 基于軟件水印的抄襲檢測技術

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

2.3.3 基于軟件胎記的抄襲檢測技術

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

3 源碼抄襲檢測技術

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

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

其次, 克隆和抄襲所產生的相似代碼的尺寸不同: 克隆片段通常較小, 而抄襲代碼則通常是原代碼的大規(guī)模或全部重用; 同時, 克隆檢測旨在實現(xiàn)軟件自身代碼重復片段的檢測, 返回的是大量候選克隆片段, 而抄襲檢測則是軟件間的相似性比較,其要給出軟件抄襲與否的判定。

再次, 克隆檢測和抄襲檢測的關注點也不一致:克隆檢測更重視準確率, 因為太多的誤報會引入過多的候選, 時間及人力開銷不允許; 而抄襲檢測更看重召回率, 特別是對于商業(yè)軟件而言, 法律訴訟過程漫長, 證據(jù)收集的越全面越好。

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

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

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

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

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

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

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

3.2 基于結構分析的抄襲檢測

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

3.2.1 基于token的檢測

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

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

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

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

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

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

3.2.2 基于樹的檢測

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

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

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

3.2.3 基于圖的檢測

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

3.3 源碼抄襲檢測技術分析比較

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

表1 各類源碼抄襲檢測技術的比較

4 基于軟件水印的抄襲檢測技術

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

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

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

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

4.1.1 代碼替換法

圖1 軟件水印技術的基本原理

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

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

4.1.2 代碼重排法

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

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

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

4.1.3 寄存器分配法

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

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

4.1.4 靜態(tài)圖法

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

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

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

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

4.1.6 抽象解釋法

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

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

圖2 GTW水印植入示意圖

4.2 動態(tài)水印技術

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

4.2.1 數(shù)據(jù)結構法

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

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

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

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

圖3 CT動態(tài)水印技術的基本流程

圖4 水印的圖編碼

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

4.2.2 條件分支法

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

4.2.3 線程爭用法

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

4.2.4 運算法

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

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

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

4.3 基于軟件水印的抄襲檢測技術分析比較

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

5 基于軟件胎記的抄襲檢測技術

軟件水印技術通過識別事先植入的水印來檢測抄襲, 然而水印的植入不僅會引入額外的時空開銷,導致程序性能下降, 甚至會引入新的軟件缺陷和漏洞, 影響軟件的正確性和安全性。此外, 當前的水印技術對語義保留的代碼混淆攻擊的抵抗力都較弱,經過適當?shù)呐粽呤冀K可以破壞任何水印[122]。為解決上述問題, 研究者提出了基于軟件胎記的抄襲檢測技術。

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

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

表2 各種軟件水印技術的比較分析

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

5.1.1 屬性分析法

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

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

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

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

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

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

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

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

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

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

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

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

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

5.2 動態(tài)胎記技術

5.2.1 軌跡元素法

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

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

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

5.2.2 依賴分析法

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

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

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

5.2.3 語義分析法

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

5.3 基于軟件胎記的抄襲檢測技術分析比較

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

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

表3 基于軟件胎記的抄襲檢測技術對比

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

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

6.1 新平臺下的抄襲檢測研究

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

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

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

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

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

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

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

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

6.2 多線程程序的抄襲檢測研究

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

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

圖6 TAB框架

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

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

6.3 部分抄襲問題

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

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

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

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

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

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

7 結束語

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

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

[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. (李舟軍, 熊浩, 晏海華, “代碼相似性檢測技術: 研究綜述”,計算機科學, 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. (金茂忠, 趙長海, 晏海華, “基于編譯優(yōu)化和反匯編的程序相似性檢測方法”, 北京航空航天大學學報, 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. (張立和, 楊義先, 紐心忻, 牛少彰“軟件水印綜述”,軟件學報,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. (楊威, 肖旭生, 李鄧鋒, 李豁然, 劉譞哲, 王浩宇, 郭耀, 謝濤,“移動應用安全解析學: 成果與挑戰(zhàn)”,信息安全學報, 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年在西安交通大學計算機專業(yè)獲得工學學士學位?，F(xiàn)在西安交通大學計算機專業(yè)攻讀博士學位。研究領域為可信軟件。研究興趣包括: 軟件動態(tài)行為分析、軟件抄襲檢測、惡意軟件分析。Email: zztian@stu.xjtu.edu.cn

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

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

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

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

佟菲菲于2015年在西安交通大學計算機科學與技術專業(yè)獲得工學學士學位。現(xiàn)在西安交通大學計算機科學與技術專業(yè)攻讀碩士學位。研究領域為可信軟件。研究興趣包括: 軟件抄襲檢測、軟件分析。Email: tongfeifei@stu.xjtu.edu.cn

朱森存于2004年在喬治梅森大學信息技術專業(yè)獲得博士學位, 現(xiàn)任賓夕法尼亞州立大學副教授。研究領域為安全與隱私, 研究興趣包括: 傳感器網絡安全、智能手機及蜂窩網絡安全、軟件安全、在線隱私和安全。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號 10.19363/j.cnki.cn10-1380/tn.2016.03.005

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

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

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