基于行為motifs的多線程程序抄襲檢測方法

田振洲 王寧寧 王 清 高 聰 劉 烴 鄭慶華

1(西安郵電大學計算機學院 西安 710121)2(陜西省網絡數據分析與智能處理重點實驗室(西安郵電大學) 西安 710121)3(西安交通大學電信學院 西安 710049)

開源軟件社區以及社交編程網站如GitHub，CodeShare等的蓬勃發展，帶來了軟件工業的繁榮.然而，伴隨而來的軟件抄襲問題亦日趨嚴重，濫用他人代碼的情況屢見不鮮.2009年，全球最大軟件商微軟的MSN(Microsoft service network)聚酷被Plurk指責抄襲了其80%的代碼；同年，國內“綠壩”被曝抄襲CyberSitter的大量代碼；2015年，APICloud涉嫌抄襲數字天堂的DCloud，鑒定報告證實其不僅直接挪用了DCloud的dll文件，還抄襲了DCloud的真機運行等功能的大量源碼.2018年8月的“紅芯風波”更是鬧得沸沸揚揚，宣稱自主研發國產內核的紅芯瀏覽器被爆僅僅是換殼谷歌Chrome.近年來，移動應用的抄襲更是愈演愈烈，如手游《巨龍之怒》抄襲藍港代碼的訴訟案件、iOS平臺PP助手抄襲事件，以及普遍存在的重打包的安卓應用這類新形式的抄襲[1].

軟件胎記[2-3](software birthmark)是從軟件代碼或其執行過程中抽取出的一些不易改變且可唯一地對軟件身份進行標識的特征.胎記技術通過衡量胎記相似性判斷軟件間可能存在的抄襲，是實現軟件抄襲檢測的一種行之有效的手段.其中，動態胎記技術[4-6]具體地執行軟件并從捕獲的執行軌跡中構建胎記，因能更精準地刻畫軟件的行為和語義，比靜態胎記技術往往表現出更優秀的抗混淆能力和檢測效果.然而，線程交織的不確定性使得多線程程序的行為也表現出很大的不確定性，這給動態胎記技術帶來不可忽視的影響[7-8].例如，在相同輸入下對同一個多線程程序執行多次，從這些執行軌跡中單獨構建的動態胎記往往會體現出很大的不同，甚至會判定同一個程序與其自身不存在抄襲關系[9].

針對這個問題，本文方法的基本思路是：通過動態監控捕獲一個多線程程序在同一輸入下的多條執行軌跡，識別出軌跡間的相似部分，并從中抽象出具有一定差異容忍能力且頻繁出現的行為模式(稱之為行為motifs)，建模該多線程程序的行為，以期降低線程交織不確定性的影響.

本文的主要貢獻有3方面:

1) 提出了一種新的多線程程序行為表示方法及提取方法，即利用抽象自多線程程序執行軌跡間相似部分的行為motifs，建模多線程程序的行為；這些行為motifs具體是通過對執行軌跡進行修剪、精確匹配以及擴展和抽象得到的.

2) 在行為motifs基礎上，提出了一種新的線程感知胎記——motifs胎記；參照軟件胎記技術的基本流程，設計了基于motifs胎記的多線程程序抄襲檢測方法，并實現了原型系統MotifPD.

3) 在一個公開的軟件抄襲樣本集上驗證了方法的有效性.實驗表明，motifs胎記是一種可靠的線程感知胎記；MotifPD不僅可有效對抗主流的代碼混淆技術，檢測性能也優于現有的2種多線程程序抄襲檢測方法：線程相關系統調用胎記(thread-related system call birthmark, TreSB)和線程切片胎記(thread-oblivious birthmark, TOB).

1 相關工作

本文工作圍繞源碼缺失情境下多線程程序的抄襲檢測展開，提出的方法屬于軟件動態胎記技術的范疇.2004年，Tamada等人[2]首次提出了軟件胎記的概念，開啟了基于軟件胎記的抄襲檢測研究的先河，隨后涌現出一系列優秀的靜態[10-11]和動態[5-6,12]的軟件胎記技術，具體可以查閱綜述性文獻[4]中對現有的軟件抄襲檢測方法，以及動靜態軟件胎記技術的系統介紹.

通過對程序執行過程進行分析抽取動態胎記,在對抗代碼混淆方面表現出更大的優勢，獲得了研究者的青睞[4,8].然而，線程交織的不確定性使動態胎記技術在檢測多線程程序抄襲方面的性能大打折扣.

Tian等人[7]首次提出了多線程程序的抄襲檢測問題，引入了線程感知胎記的概念；并提出了TOB框架[9]，基于“切片-合并”的基本思想，擴展傳統動態胎記以支持多線程程序的抄襲檢測.他們利用TOB框架改良了3種經典的動態胎記：動態關鍵指令序列胎記(dynamic key instruction sequence birthmark, DYKIS)[5]、系統調用短序列胎記(system call short sequence birthmark, SCSSB)[13]、JBirth[14]進行了改良；實驗結果表明，原胎記經改良后均可提升檢測多線程程序抄襲的能力.然而，該項工作的基本假設“每個線程內發生的事件相對穩定”并不總是滿足，線程間的交互和相互影響可能會導致每個線程內發生的事件產生變化.此外，通過線程切片并為每個線程單獨構建胎記確實很大程度上可以減小交織的影響，但也使得胎記難以捕捉程序的整體行為，在分析線程間交互特別復雜的程序時難免會產生一定的漏報.

后來，Tian等人[15]又基于線程相關的系統調用，提出了一種新的線程感知胎記TreSB，其利用對線程交織實施影響和控制的線程相關系統調用，建模多線程程序交互過程體現出的行為特性.該方法在通用性方面不及TOB，其僅是針對多線程程序設計的具體線程感知胎記方法；因其主要利用了與線程操作相關的特征，故只能用于多線程程序的抄襲檢測，且在線程交互較少的情況下并不適用.

2 motifs提取

傳統動態胎記技術不適用于檢測多線程程序抄襲的根本原因在于，線程交織的不確定性最終引起程序執行軌跡的變化，而從中構建動態胎記時它們對這些變化的容忍不足.因而，保證方法有效性的關鍵在于，從多變的執行軌跡中提取的特征須具備一定的差異容忍能力，以降低線程交織不確定性的影響.

現有的2種線程感知胎記方法TOB和TreSB，無論是采用“切片-合并”還是“利用特定元素(即線程相關系統調用)”的思想，均是從一條執行軌跡中抽取不易被線程交織干擾的特征.在DNA序列分析領域，motif(模體，也稱基序.本文中當指代單個模體或修飾模體識別技術時用單數形式motif，其他情況下均用其復數形式motifs)識別從一組DNA序列中探測共有的序列模式，這組DNA序列往往比較相似，但因為變異的存在不會完全一致；同時，識別出來的motifs往往不會原樣出現在所有序列中.對于多線程程序而言，多數情況下同一輸入意味著同一程序功能的執行，同時并非所有的程序部分都會涉及交織，因而其在同一輸入下的多條執行軌跡往往比較相似.受到DNA序列分析中motif識別的啟發，本文嘗試從多線程程序在同一輸入下的多條相似的執行軌跡中識別行為motifs(定義1)，并用其建模該多線程程序的行為.

定義1.多線程程序的行為motifs.給定多線程程序P在同一輸入I下的多條執行軌跡，設計算法α從中提取出一系列模式，這些模式捕捉了存在差異的執行軌跡間的相似部分，且算法α提供抽象策略保證提取的模式具備一定的差異容忍能力，按照這種方式提取的模式，稱作多線程程序的行為motifs，也稱多線程程序的行為模式.

圖1描述了提取motifs的基本流程.具體地，以程序的同一輸入下多次運行捕獲的多條執行軌跡為輸入，經過軌跡修剪、gram匹配、擴展抽象3個階段，提取出行為motifs.

Fig. 1 Basic process of extracting motifs
圖1 motifs提取基本流程

2.1 軌跡修剪

系統調用序列刻畫了軟件與操作系統的交互過程，被廣泛用于建模程序行為.同時，作為操作系統的最小功能單元，系統調用是用戶態應用程序請求操作系統內核服務的唯一手段，較難被刪除和篡改，因而諸多胎記技術如SCSSB[13]，SCDG(system call dependency graph birthmark)[16]，TOB[9]，TreSB[15]等均利用系統調用構建胎記以提升對抗代碼混淆[17]的能力.本文的執行軌跡也是指由系統調用構成的序列，通過動態插樁監控程序執行得到.

原始的執行軌跡并不適用于直接提取motifs.首先，失敗的系統調用不能正確地反映程序行為[11,13]，比如程序中的打開文件操作，可能會出現打開失敗的情況，相應的系統調用open會被執行多次，失敗的那些將被視作噪聲過濾掉.其次，部分系統調用具有先天的隨機性，如系統調用futex提供了一種方式使線程保持阻塞直到滿足特定的條件，且只有當預計阻塞時間較長時才會被調用，因而其出現次數在不同次執行時體現出固有的隨機性，應當被作為噪聲過濾掉.另一類是負責內存管理的系統調用，如mmap和brk等.前者在涉及到特別大塊的內存分配時才被調用，后者則依據實際需要調整堆尺寸的大小.一般來說，malloc函數被調用時會攫取大塊的內存空間，然后依據實際需要將其分割成較小的內存塊，這就導致并非每次malloc都會有對應的系統調用被執行.因而，所有負責內存管理的系統調用也被視作噪聲過濾掉.

2.2 gram匹配

motifs抽象自多條執行軌跡的相似部分，對此算法首先識別執行軌跡間所有的精確匹配區間，然后以它們為基礎進行雙向的擴展和抽象.

對于精確匹配區間的識別，本文算法目前是在計算k-gram[18]基礎上經過搜索和嚴格匹配得到，故識別出來的匹配區間都是固定長度的，長度均為k.

假定s=(e1,e2,…,en)為多線程程序P在某輸入下某次運行時捕獲且經過了修剪的執行軌跡.

首先，利用k-gram算法將其切分成一系列長度為k的gram：grams(s,k)={gi|gi=(ei,ei+1,…,ei+k-1)}，1≤i≤n-k+1.

然后，?gi∈grams(s,k)，在其他執行軌跡中查找所有與之精確匹配的子序列，這些子序列的起止范圍就定義了gi的所有精確匹配區間.

例1.給定2條修剪過的執行軌跡s=ABCDE和t=ABCFDMABCFE,當k=2時，對于s中的gram BC，t中有2處與其匹配，即BC在t中的精確匹配區間為[2,3]和[7,8].

2.3 擴展和抽象

對gram及其精確匹配區間進行進一步的擴展和抽象，以對抗線程交織不確定性引入的差異.進行擴展時，gram及其精確匹配分別以自身為中心，以步長為1在各自的執行軌跡上雙向交替進行.

例1中的gram BC經3輪擴展后變為ABCDE，其精確匹配區間擴展后對應的匹配序列分別為ABCFD和ABCFE.顯然，擴展引入了非精確匹配關系，即每次擴展均可能使gram與其匹配區間對應的序列不再完全一致.

對此，對擴展后的gram及其非精確匹配，利用Smith-Waterman算法[19]求取二者匹配度最高的子序列.Smith-Waterman算法基于2序列中元素間的相似性計算1個得分矩陣，然后從矩陣中得分最高元素開始回溯求得最佳匹配.得分矩陣的計算依賴于匹配得分、失配得分以及插入或刪除引入的空位罰分.

具體地，得分矩陣計算為

(1)

其中，c[i,j]為矩陣中第i行、j列的元素.sc為匹配或失配得分，2系統調用相同時為匹配，sc取正值；否則為失配，sc取負值.gap為空位罰分，取負值，表示對采取刪除或插入操作的處罰.

例2.擴展得到的非精確匹配對ABCDE和ABCFD，經Smith-Waterman比對，可得最佳匹配ABC-D和ABCFD，其中“-”表示插入空位.對另一個非精確匹配對ABCDE和ABCFE，Smith-Waterman識別出ABCDE和ABCFE為最佳匹配.

最后，對Smith-Waterman識別的匹配序列進行抽象.具體地，將匹配序列中對應位置不一致的元素全部用“-”替代，并將生成的短序列記作一個行為motif.比如，從例2的匹配對ABC-D和ABCFD中將抽象出行為motif ABC-D；從另一匹配對ABCDE和ABCFE中可抽象ABC-E.利用“-”替代不一致的元素，使得提取的行為motifs可以容忍執行軌跡中的細微差異，從而降低線程交織不確定性的影響.

算法1描述了從2條執行軌跡中提取motifs的完整過程.

算法1.行為motifs提取算法.

輸入：修剪過的執行軌跡s和t、k-gram的參數k、迭代終止閾值γ；

輸出：motifs及其頻數構成的鍵值對集合M.

①M←?；

② 利用k-gram切分s為短序列集grams(s,k)；

③ forg∈grams(s,k) do

④E←findExactMatch(g,t)；

⑤ forr∈EMdo

⑥d←1；*擴展方向標記*

⑦g′←g,canExpand←TRUE；

len(t)-1 then

⑨canExpand←FALSE；

⑩ end if

len(t)-1 then

算法1中，行④中函數findExactMatch返回指定gram在另一條軌跡中的所有精確匹配區間，行⑧～⑩以及～判斷是否可以繼續擴展，行～實現沿軌跡指定方向的擴展，行中smith-Waterman函數比對擴展后的非精確匹配對，行中函數abstract從比對識別的最佳匹配序列中抽象出motif,行～更新M中的鍵值對.另外，對每對精確匹配迭代地進行擴展、比對和抽象時，算法1中行～會按照式(2)計算懲罰因子pf，當pf≥γ時，提前終止迭代，以提高motifs提取的效率.

pf=len(η)len(ζ)，

(2)

其中，len(η)和len(ζ)分別表示擴展得到的非精確匹配序列以及提取出來的motif的長度.

算法1的時間復雜度為O(n3)，其中n為經過修剪的執行軌跡的長度，最壞情形發生在執行軌跡s和t完全一致，且每條執行軌跡中均只包含重復單一元素的情況下.在實際情況下，程序的執行軌跡往往由一系列不同的系統調用組成，同時多線程程序在同一輸入下的執行軌跡盡管比較相似，但一般不會完全一致，因而最壞情況基本不會發生.

算法1中最耗時的部分在于擴展-比對-抽象的操作，該操作的迭代次數越多時間開銷越大.具體地，該操作的迭代次數取決于2個參數，一是懲罰因子的閾值γ，該閾值越大迭代終止條件越不容易滿足，迭代次數越多.本文認為γ=2是一個合理的選擇，即當擴展后的非精確匹配對的長度為從中提取出的motif長度的2倍以上時，認為繼續擴展的意義不大而終止迭代，因為繼續迭代提取出的motifs有極大可能會與之前一致.k值是另外一個影響迭代次數的因子，因為擴展-比對-抽象操作是在精確匹配對基礎上展開的，而k值決定了精確匹配對的數量.k值越小，長度為k的子序列完全匹配的可能性就越大，即精確匹配對數量越多，導致總的迭代次數越多，時間開銷越大.當然，可以通過增大k值或減小γ值來加速迭代的終止，但可能會導致某些有代表性的motifs提取不出來，即會降低motifs的多樣性.本文4.4節具體分析了k值對方法的檢測效果和效率的影響.

3 基于motifs的軟件抄襲檢測

迭代利用算法1處理多線程程序在同一輸入下的執行軌跡集，基于提取的行為motifs構建motifs胎記，并通過衡量motifs胎記的相似性，實現多線程程序間潛在抄襲的檢測.

3.1 motifs胎記

3.2 胎記相似性計算

motifs胎記是鍵值對集合的形式，與線程感知胎記TreSB和TOB一樣，在余弦相似度基礎上引入參數θ，以將motifs的頻數相似性考慮進來.

首先，計算二者鍵集合的并集，有：

其中，

最終，2個motifs胎記的相似性為

3.3 抄襲判定

最終，依據式(3)給出判定結果.

(3)

其中，ε為可調節的檢測閾值.

3.4 系統實現

基于本文所提方法實現了多線程程序抄襲檢測系統MotifPD，由動態監控模塊、胎記生成模塊，以及相似性計算和抄襲判定模塊組成.

動態監控模塊負責監控程序執行，記錄運行過程中調用的系統調用.該模塊基于Pin動態插樁框架[20]實現，利用接口函數PIN_AddSyscallEntry-Function和PIN_AddSyscallExitFunction，分別在系統調用執行前后插入監控和分析代碼，以捕獲系統調用的相關信息.圖2給出了捕捉的執行軌跡的片段，每行對應一條具體的系統調用，形式為“調用發生時所在線程的ID#系統調用號#系統調用名#具體參數#返回值”.胎記生成模塊處理監控模塊記錄的執行軌跡，經預處理、gram匹配和擴展抽象，實現motifs胎記的提取.相似性計算和抄襲判定模塊具體實現了3.2節和3.3節的算法，不再贅述.

Fig. 2 Trace snippet captured by the dynamic monitoring module圖2 動態監控模塊捕獲的執行軌跡片段

4 實驗分析

4.1 實驗對象及參數設置

在一個公共的軟件抄襲樣本集[21]上驗證了MotifPD的有效性，并與TreSB和TOB進行了對比分析.該樣本集共計包含234個不同版本的多線程程序，由35個涉及不同領域的多線程程序在一系列混淆策略下衍生而來.采取的混淆策略包括：

S1. 利用不同的編譯器及優化選項(llvm，gcc，o0-os)這類相對較弱的混淆手段生成目標代碼.

S2. 應用專業的混淆工具，包括SandMark，Zelix KlassMaster，Allatori，DashO，JShrink，Pro-Guard，RetroGuard，構造強力混淆副本.

S3. 利用加殼混淆工具UPX(the ultimate packer for executables)處理目標代碼.

表1給出了該數據集包含軟件名稱(“Name”列)、版本號(“Version”列)在內的一些基本信息.“#Ver”列給出了每個軟件(含原始程序在內)的抄襲副本總數，以及采用各混淆手段生成的抄襲副本個數；“Size of Program”列則標出了每個軟件的所有副本中最大副本的尺寸.關于該數據集的其他信息，網站[21]和文獻[15]中都作了詳細介紹，此處不再贅述.

Table 1 Outline of the Multi-threaded Program Plagiarism Benchmark表1 多線程程序抄襲樣本集基本信息

Notes: Each value in the “Total” column gives the number of total versions of the corresponding program. It equals to the number of plagiarism copies (generated with obfuscation strategy S1, S2 and S3) plus one original version.

此外，MotifPD的效果依賴于一些參數，如無特別說明下文實驗中各參數的默認設置為：gram匹配階段k=3，擴展抽象階段γ=2，生成motifs胎記時閾值Φ=10；另外，每個程序均提供多個輸入，同一輸入均驅動程序執行4次.

4.2 胎記的彈性和可信性評估

軟件胎記的品質高低由其彈性(resilience)和可信性(credibility)來衡量[4].這里引用Collberg等人[3]對這2個基本特性的描述.

1) 彈性.假定程序Q是通過對程序P應用語義保留的代碼混淆τ生成的抄襲版本，利用胎記技術計算二者的相似性SIM(P,Q)，如果SIM(P,Q)≥1-ε，則認為該胎記技術對于τ而言具備彈性.

2) 可信性.對于2個獨立開發的軟件P和Q，利用胎記技術計算二者的相似性SIM(P,Q),如果SIM(P,Q)<ε，則認為該胎記技術具備可信性.

更直觀地講，彈性刻畫了胎記技術識別抄襲的能力，即要保證胎記能對抗各類語義保留的代碼混淆，混淆后利用胎記依然可以識別出原程序與其混淆版本的同源性；可信性則要求從獨立實現的軟件中抽取出的胎記總不相似，刻畫了胎記技術區分獨立開發軟件的能力.

為了評估motifs胎記的彈性，將公共數據集中各程序的原始版本作為原告，采用各種混淆策略的衍生版本作為被告，構成一系列的原告-被告比較對，并利用MotifPD計算這些比較對的相似性.圖3給出了各種混淆策略下比較對的相似性的分布情況，其中縱軸刻畫了計算得到的相似值落入到圖例所示各區間的比例.可以看到幾乎所有比較對的相似度都在0.9以上，表明motifs胎記對該公共數據集中涉及到的混淆手段均具備很好的抵抗效果.

為了評估motifs胎記的可信性，選用數據集中相互獨立開發的軟件作為實驗對象，具體包括6個多線程壓縮解壓縮軟件、10個Web瀏覽器以及5個音頻播放軟件，并利用MotifPD計算它們之間的相似性.圖4統計了同類軟件間和不同軟件間的相似性的分布情況.可以看到，不同類軟件間的相似性普遍很低，都在0.1以下.同類軟件由于在功能上具有較大的一致性，它們之間的相似性略高，但絕大多數依然落入到較低的相似區間.其中有少數幾個比較對的相似性在0.2甚至0.4以上.通過人工檢查發現，采用了相同算法或共同依賴于某些功能模塊，是導致MotifPD在處理這些比較對時得出較高相似性的原因.比如壓縮解壓縮pbzip2和lbzip2的相似性為0.25，因為它們都是基于Burrows-Wheeler壓縮算法實現的并行版本；瀏覽器arora，Dooble，epiphany，luakit，midori均采用了WebKit布局引擎，MotifPD在計算它們之間相似性時也得到較高的值.

Fig. 3 Resilience evaluation of motifs birthmark圖3 motifs胎記的彈性評估

Fig. 4 Credibility evaluation of motifs birthmark圖4 motifs胎記的可信性評估

4.3 與其他胎記技術的對比分析

本節將MotifPD與其他2種線程感知胎記技術TreSB和TOB(1)TOB是一個線程感知胎記框架，提供了2種模型SA和SS，改良傳統動態胎記以支持多線程程序的抄襲檢測.對比實驗中的TOB指的是改良的SCSSB，并用TOBSA和TOBSS區分其在改良SCSSB時具體用的是何種模型.以及同樣基于系統調用的動態胎記技術SCSSB[13]的總體性能進行系統地比較.

4.3.1 檢測效果的對比分析

各胎記技術檢測效果的評估采用TreSB[15]和TOB[9]這2篇文獻中使用的3種指標，包括URC[22](union of resilience and credibility)，F-Measure，MCC[23](Matthews correlation coefficient).其中URC是為了綜合考量胎記彈性和可信性而專門設計的指標，但存在偏愛更大閾值的不足[5]；F-Measure和MCC則是信息檢索與數據挖掘領域常用的綜合性指標.

為方便描述，定義下列符號.

1)EP.由存在抄襲關系的比較對構成的集合，即?(P,Q)∈EP，都有程序Q抄襲自程序P.

2)JP.由被抄襲檢測系統判定為抄襲的比較對構成的集合，即?(P,Q)∈JP，程序Q被判定為抄襲了程序P.

3)EI.由相互獨立的比較對構成的集合，即?(P,Q)∈EI，程序Q與程序P相互獨立.

4)JI.由被抄襲檢測系統判定為相互獨立的比較對構成的集合，即?(P,Q)∈JI，程序Q被判定為與程序P相互獨立.

基于上述符號約定，URC可表示為

(4)

對于F-Measure，采用最常用的F1，其是準確率(Precision)和召回率(Recall)的調和平均數.

(5)

其中，

MCC綜合考慮了真正、真負、假正和假負，在正負類樣本不均衡的情況下也可以對檢測效果做出合理的評估.本文實驗樣本中，抄襲對的數量要遠高于非抄襲對的數量，即正負類樣本不均衡，因而MCC的評估結果相比F1更加可信.

(6)

其中，TP=|EP∩JP|，FN=|EP∩JI|，FP=|EI∩JP|，TN=|EI∩JI|.

對于每種度量指標而言，在同一閾值下其值越高，表明方法的檢測性能越好.圖5(a)～5(c)分別給出不同閾值下(2)URC是基于式(3)定義的指標，要求必須有1-ε≥ε，故ε的有效范圍為0～0.5.而為了采用F-Measure和MCC，TOB和TreSB通過移除“無法判定”部分，將抄襲檢測描述為一個二分類問題(當SIM(P,Q)≥ε時判定為抄襲，否則判定為不存在抄襲)，故采用這2種指標時ε的有效取值范圍為0～1.各胎記技術相對于3種度量標準的對比結果.可以看到，對于任意一種度量，MotifPD對應的曲線在整個x軸上幾乎總在其他曲線之上，表明在任意閾值下MotifPD的檢測性能幾乎總優于其他幾種胎記技術.

Fig. 5 Overall performance evaluation with respect to three different metrics圖5 相對于3種不同度量標準的總體性能比較

為了更直觀地量化比較各胎記技術的應用效果，性能增益PerGain[9]是基于各曲線下的面積AUC(area under the curve)并以SCSSB作為基準得到，刻畫了各線程感知胎記技術相對于傳統動態胎記SCSSB的性能提升程度.

(7)

其中，X可取{MotifPD,TOBSA,TOBSS,TreSB}中的任意1種，AUCX和AUCSCSSB分別表示線程感知胎記和SCSSB的AUC值.

表2給出了各線程感知胎記技術相對于3種度量標準的PerGain值.可以看到MotifPD的性能增益始終是最高的，表明MotifPD可以更好地應對多線程程序的抄襲.

Table 2 Comparative Quantification of the Thread-oblivious Birthmarks Based on PerGain表2 各線程感知胎記技術基于PerGain的量化比較

4.3.2 時間開銷的對比分析

MotifPD與其他3種動態胎記技術均主要包含3個階段：執行軌跡捕獲、胎記生成以及相似性計算.對于執行軌跡的捕獲，均利用Pin動態插樁監控程序執行來實現，動態監控帶來的負載平均為3倍左右；因為本文實驗均基于相同的執行軌跡集，在該階段各方法的開銷一致.因而，本節重點對比MotifPD與其他方法在后2個階段的時間開銷.

表3給出了各胎記技術在胎記生成階段(Phase Ⅱ)以及相似性計算階段(Phase Ⅲ)的平均時間開銷.在胎記生成階段，MotifPD生成胎記的平均時間顯著高于其他方法，約為其他方法的84倍；其他方法因為均是直接利用k-gram生成胎記，它們的胎記生成開銷十分接近.在相似性計算階段，各方法的時間開銷區別不大，只有TOBSS因為需要利用最大帶權二分圖匹配實現相似性計算，開銷略高，比較1對胎記平均需要20 ms.可以看到，MotifPD生成胎記的過程比較耗時，在檢測效率方面要低于其他動態胎記技術，但對于抄襲檢測而言，檢測的準確性相比檢測效率更加重要，后續計劃優化擴展-抽象的迭代過程，提升motifs胎記的提取效率.

Table 3 Average Time Cost of Each Birthmarking Method in Phase Ⅱ and Phase Ⅲ Respectively表3 各胎記技術在Phase Ⅱ和Phase Ⅲ的平均時間開銷 ms

4.4 k值的影響分析

精確匹配階段k值的選擇，直接影響著motifs提取的效率以及提取出的motifs的多樣性，從而會對整個方法的檢測效果和檢測效率產生影響，本節結合實驗具體分析k值的選擇問題.

圖6給出了不同k值下MotifPD相對于3種度量指標的檢測效果.可以看出，當k=1或k>10時，檢測效果不佳；取值在2～10之間時，檢測效果的差異不大.當k=1時，從圖7中可以看出識別出的精確匹配對數量會非常多，導致即使對于非抄襲對而言，也會存在不少motifs一致，從而引起誤報；隨著k值的增大，識別出的精確匹配對的數量會不斷減少，結合圖8可以看出這將導致提取出的motifs的數量和多樣性減少，當減少到一定程度，如k>10時，會使得計算抄襲對的相似性時得到較低值，從而引發漏報.比如，k=15時，有192對抄襲對的相似性在0.9以下；k=10時，相似性在0.9以下的抄襲對僅有28對.

Fig. 8 Impact of k on motifs diversity圖8 k值對motifs多樣性的影響

通過2.3節的分析，可以知道k值還影響著motifs提取的效率.圖7給出了取不同k值時生成motifs胎記的平均時間開銷，可以看出隨著k值的增大，時間開銷逐漸下降，特別是在k值由1增大為3的過程中，時間開銷顯著下降.因此，綜合對檢測效果和檢測效率的影響，k=3是一個較為合理的選擇.

5 方法的局限性討論

MotifPD從程序在同一輸入下多次運行對應的多條執行軌跡中提取motifs來降低線程交織不確定性的影響.因而在處理單線程程序時，MotifPD將表現出與傳統動態胎記技術基本一致的檢測效果；同時在以下2種情況下，MotifPD將退化至傳統動態胎記技術的水平.

1) 處理線程間交織程度特別高的程序時.提取motifs的前提是程序在同一輸入下的多條執行軌跡中存在相似部分，線程間高度的交織顯然會導致捕獲的軌跡極不相似，使得提取的motifs過少甚至無法提取.然而，時序約束使得某些功能模塊必須順次執行，用于共享資源安全訪問而設置的各種鎖也會大大減少交織度，因而現實中絕大多數多線程程序的交織程度不會過于復雜.

2) 混淆導致原告和被告程序執行軌跡差異很大的情況下.動態胎記技術本質上是通過衡量原告和被告程序的執行行為的相似性檢測抄襲，如果存在某些混淆手段使得原被告程序在相同輸入的執行軌跡出現很大差異，跟傳統動態胎記技術一樣MotifPD將無法檢測出抄襲.MotifPD采用的是由系統調用構成的執行軌跡，對系統調用進行刪除、修改或替換的混淆方式會挫敗本文檢測方法.然而，系統調用作為用戶態應用程序請求操作系統內核服務的唯一手段，較難被刪除和篡改，因而實施此類混淆的代價很高，特別對于多線程程序而言，隨機或刻意的修改很容易引入微妙的并行問題.

6 總 結

本文提出了一種新的線程感知胎記技術以解決多線程程序的抄襲檢測問題.該方法從程序在同一輸入下多次運行所捕獲的執行軌跡中，經軌跡修剪、gram匹配和擴展抽象，識別軌跡間的相似部分并抽象出可以抵抗線程交織干擾的motifs；在此基礎上構建motifs胎記，并通過衡量motifs胎記的相似性檢測程序間潛在的抄襲.基于本文方法實現了抄襲檢測工具MotifPD，在公共數據集上開展的實驗表明，其能有效對抗當下主流的代碼混淆手段，比多線程程序抄襲檢測方法TreSB和TOB表現出更優秀的檢測能力.不過，motifs胎記的構建時間開銷要高于TreSB和TOB，對此接下來計劃優化擴展-抽象的迭代過程.