摘要：它在實(shí)踐中被成功地用于檢測學(xué)生程序提交中的剽竊行為。這項(xiàng)措施應(yīng)該反映原始程序中由比賽覆蓋的部分代幣。這個(gè)程序集根本不包含任何剽竊行為，因此將其命名為。在節(jié)目集中有個(gè)抄襲對。

摘要：JPlag是一個(gè)Web服務(wù)，可以在給定的集合中找到類似的程序?qū)Φ某绦?。它在?shí)踐中被成功地用于檢測學(xué)生Java程序提交中的剽竊行為。能支持的語言除了java之外,還有C、C++和Scheme。我們描述Jpalg架構(gòu)和jplag的比較算法，這個(gè)算法是基于名為“Greedy String Tiling”的已知算法。那么，這篇論文的貢獻(xiàn)主要有三個(gè)方面：首先，對JPlag在幾個(gè)不同的集合上的表現(xiàn)進(jìn)行評估的Java程序，證明抄襲很難通過JPlag的檢查。再一次測試中，在我們的各種基準(zhǔn)程序集中，77個(gè)剽竊者中有90％以上被可靠檢測到，其他人中的大多數(shù)都會引起懷疑。運(yùn)行時(shí)間僅為幾百秒，用于提交每個(gè)100個(gè)程序的100個(gè)程序。其次，參數(shù)研究表明，該方法在配置參數(shù)方面相當(dāng)穩(wěn)健。第三，我們研究了用于偽裝抄襲的種類，頻率和成功的種類。

關(guān)鍵詞：剽竊，相似性，搜索，令牌，字符串拼貼
類別：GT算法，GT性能，F(xiàn).2.2。 模式匹配，H.3.3，H.5.2。，
I.5.4。 文本處理，K.3.m.，K.5.1

檢測類似的程序
1.所有要比較的程序都被解析（或根據(jù)輸入進(jìn)行掃描）
語言）并轉(zhuǎn)換為令牌字符串。
2.將這些標(biāo)記字符串成對比較以確定相似性
每一對。

將程序轉(zhuǎn)換為令牌字符串的前端過程是JPlag中唯一依賴于語言的過程。 目前存在三種前端實(shí)現(xiàn)：Java和Scheme的實(shí)現(xiàn)都是實(shí)現(xiàn)完整的解析器。 C ++（或C）的第三個(gè)前端只包含一個(gè)掃描器。

作為一項(xiàng)規(guī)則，應(yīng)該選擇令牌，以便表征程序結(jié)構(gòu)的本質(zhì)（剽竊者難以改變），而不是表面方面。 JPlag忽略空白，注釋和標(biāo)識符的名稱。 此外，JPlag在可能的情況下將語義信息放入令牌中，以減少純粹偶然發(fā)生的虛假子串匹配。 例如，在Java中，我們使用Begin Method標(biāo)記而不是僅僅一個(gè)Open Brace標(biāo)記。 基于解析器的前端在這方面更勝一籌。 有關(guān)Java示例，請參見表1。 請參閱第4節(jié)以了解標(biāo)記化方法的基本原理。

我們在第3.4節(jié)中的評估表明，JPlag對令牌集的更改非常有效

 Greedy-String-Tiling(String A, String B) {
     tiles = {};
     do {
         maxmatch = M;
         matches = {};
         Forall unmarked tokens Aa in A {
             Forall unmarked tokens Bb in B {
                 j = 0;
                 while (Aa+j == Bb+j && unmarked(Aa+j) && unmarked(Bb+j))
                 j + +;
                 if (j == maxmatch)
                     matches = matches ⊕ match(a, b, j);
                 else if (j > maxmatch) {
                     matches = {match(a, b, j)};
                     maxmatch = j;
                 }
             }
         }
         Forall match(a, b, maxmatch) ∈ matches {
             For j = 0 ...(maxmatch ? 1) {
                 mark(Aa+j);
                 mark(Bb+j );
             }          
             tiles = tiles ∪ match(a, b, maxmatch);
         }
     } while (maxmatch > M);
         return tiles;
   }

表2：“貪婪字符串拼貼”算法[Wise，1993]。 第12行中的⊕運(yùn)算符在匹配集合中添加匹配項(xiàng)，當(dāng)且僅當(dāng)它與集合中已有的匹配項(xiàng)之一不重疊時(shí)。 三重匹配（a，b，l）表示A和B的相同子串之間的關(guān)聯(lián)，分別從位置Aa和Bb開始，長度為1。

用于比較兩個(gè)標(biāo)記字符串的算法本質(zhì)上是“貪婪字符串拼貼”[Wise，1993]。 比較兩個(gè)字符串A和B時(shí)，目標(biāo)是找到一組具有以下屬性的連續(xù)子字符串：每個(gè)子字符串都出現(xiàn)在A和B中，盡可能長并且不涵蓋已由其他某個(gè)其他字符覆蓋的標(biāo)記子。 為了避免虛假匹配，強(qiáng)制執(zhí)行最小匹配長度M.

最小匹配長度M被強(qiáng)制執(zhí)行?！柏澙纷址促N”是一種啟發(fā)式算法，因?yàn)楸ＷC找到的一組子字符串的最大值會使搜索過于昂貴。 這里是粗略的草圖（參見表2的偽代碼）。 該算法重復(fù)以下兩個(gè)步驟：

步驟1（第5-18行）：搜索兩個(gè)字符串以查找最大的連續(xù)匹配。 從概念上講，這是通過3個(gè)嵌套循環(huán)完成的：第一個(gè)循環(huán)遍歷A中的所有標(biāo)記，第二個(gè)將當(dāng)前標(biāo)記與B中的每個(gè)標(biāo)記進(jìn)行比較。如果它們相同，則最內(nèi)部循環(huán)搜索Prechelt L.，Malpohl G.，Philippsen M .: Finding Plagiarisms ... 1021比賽結(jié)束。 這些嵌套循環(huán)收集所有最長的公共子串集合

步驟2（第19-25行）：標(biāo)記步驟1中發(fā)現(xiàn)的所有最大長度的非重疊匹配。這意味著它們的所有標(biāo)記都被標(biāo)記，因此可能不會用于后續(xù)迭代步驟1中的進(jìn)一步匹配。 在Wise的術(shù)語中，通過標(biāo)記所有的標(biāo)記，匹配成為一個(gè)貼圖。

重復(fù)這兩個(gè)步驟直到找不到進(jìn)一步的匹配。 由于在每一步中標(biāo)記了更多的標(biāo)記，所以算法總是終止。 它返回我們需要計(jì)算相似性度量的瓦片列表。 這項(xiàng)措施應(yīng)該反映原始程序中由比賽覆蓋的部分代幣。 我們將其定義為sim（A，B）= 2·coverage（tiles）/（| A | + | B |）其中coverage（tiles）=？ 匹配（a，b，長度）∈tiles長度。

這種啟發(fā)式算法的運(yùn)行時(shí)復(fù)雜度仍然相當(dāng)高。 在最壞的情況下，所有三個(gè)嵌套循環(huán)都會執(zhí)行到最大限度。 盡管在后面的迭代中匹配長度遞減，但如果在每次迭代中只標(biāo)記一個(gè)最短的可設(shè)想的匹配，則這可能導(dǎo)致與Θ（（| A | + | B |）3）一樣大的步驟， 最后涵蓋了字符串[Wise，1993; Prechelt等，2000]。 在最好的情況下，根本不存在來自A的單個(gè)令牌，并且搜索需要Θ（（| A | + | B |）2）個(gè)步驟。

盡管最壞情況下的復(fù)雜度不能降低，但通過應(yīng)用Karp-Rabin模式匹配算法[Karp and Rabin，1987]的想法，實(shí)際情況下的平均復(fù)雜度可以提高到幾乎Θ（| A | + | B |。

通過使用哈希函數(shù)來處理更長的字符串（“文本”T）。 為此，所有長度為| P |的子串的哈希值 在T中計(jì)算。 這可以通過使用能夠根據(jù)h（Tt-1Tt ... Tt + | P | -1）的值計(jì)算h（TtTt + 1..Tt + | P | -1）的值的散列函數(shù)h以線性時(shí)間完成。 -2），Tt-1和Tt + | P | -1。 然后將所有散列值與P的值進(jìn)行比較。如果兩個(gè)值相同，則進(jìn)行字符對比以驗(yàn)證T中P的出現(xiàn)已被找到。 這種算法在實(shí)踐中的復(fù)雜性幾乎是線性的。

我們修改Wise的貪婪字符串拼貼以下列方式應(yīng)用Karp-Rabin匹配的基本思想：
1.對于時(shí)間Θ（| A | + | B |）中的所有長度為s的子串計(jì)算散列值。 JPlag使用s = M，Wise的算法如下所述調(diào)整s。
2.然后將來自A的每個(gè)散列值與來自B的每個(gè)散列值進(jìn)行比較。如果兩個(gè)值相同，則通過用令牌比較子串標(biāo)記來驗(yàn)證匹配。 然后該算法試圖將匹配盡可能地?cái)U(kuò)展到散列函數(shù)覆蓋的范圍之外。
3.使用散列表來定位來自B的具有與來自A的給定子字符串相同的散列值的子字符串。

這個(gè)算法的最壞情況下的復(fù)雜度仍然是Θ（（| A | + | B |）3），因?yàn)樗械淖幼址伎赡鼙仨毻ㄟ^令牌比較令牌，但實(shí)際上復(fù)雜度遠(yuǎn)低于Θ（（| A | + | B |）2）通常被觀察到。

JPlag預(yù)先執(zhí)行所有散列計(jì)算（兩個(gè)字符串的散列值加上字符串B的散列表），即在平鋪過程之前僅進(jìn)行一次散列計(jì)算。 當(dāng)找到匹配并且標(biāo)記了一個(gè)貼圖時(shí)，靜態(tài)哈希表中的相應(yīng)條目不再適用于后續(xù)迭代。 由于JPlag離開表中的受影響條目，所以驗(yàn)證子步驟（上面的編號2）變得稍微復(fù)雜一些。

相比之下，Wise會在每次迭代中重新計(jì)算所有散列值和散列表，以便找到的任何匹配都是有效的。
在這兩種方法中，我們發(fā)現(xiàn)靜態(tài)預(yù)計(jì)算加上稍微更昂貴的有效性檢查對于JPlag的默認(rèn)參數(shù)和典型的標(biāo)記字符串來說更快。

在本節(jié)中，我們將研究JPlag的歧視性能及其對程序結(jié)構(gòu)的敏感性，剽竊頻率以及JPlag算法的自由參數(shù)。 我們提出一個(gè)基于多套真實(shí)學(xué)生課程加上一些明確制作的剽竊的實(shí)證研究。

本節(jié)介紹了一組程序，用于量化結(jié)果的標(biāo)準(zhǔn)以及評估中考慮的自由參數(shù)集。

我們在研究中使用了四種不同的程序作為基準(zhǔn)。 其中三門是來自第二學(xué)期信息學(xué)課程的編程練習(xí)，第四門是從一門研究生高級程序設(shè)計(jì)課程，向有經(jīng)驗(yàn)的學(xué)生介紹Java和AWT。 有關(guān)概述，請參閱表3，現(xiàn)在忽略最右邊的兩列

“簡單”：最大化流量。 用于計(jì)算通過具有容量加權(quán)邊的有向圖的最大流量的算法。 該程序基于一個(gè)不包含在此處調(diào)查的源中的可重用GraphSearch類。 該程序集在程序長度和結(jié)構(gòu)上顯示出相當(dāng)大的變化性。 平均長度為236個(gè)非空的非注釋行代碼（LOC）。 它包括2個(gè)剽竊他人的程序（即4個(gè)程序構(gòu)成2個(gè)抄襲對）。 我們通過對所有程序進(jìn)行仔細(xì)的手動比較來確定這個(gè)程序集和其他程序集內(nèi)的抄襲對，即我們應(yīng)用了人類審查人員可以做的最好的檢查。 由于這些程序存在相當(dāng)大的結(jié)構(gòu)變化，我們認(rèn)為這個(gè)程序?yàn)镴Plag設(shè)置了一個(gè)相對簡單的任務(wù)，因此該程序的名稱為Simple。

“硬”：乘法排列。 將兩個(gè)置換表示為置換矩陣，由整數(shù)數(shù)組實(shí)現(xiàn)，指示每行的1的位置。 這是一個(gè)非常短的程序（平均長度43 LOC），具有相當(dāng)固定的結(jié)構(gòu)。 我們可能期望即使是獨(dú)立編寫的程序看起來也非常相似。 因此，這個(gè)程序集對于JPlag來說是一個(gè)非常嚴(yán)格的測試，因此將被命名為Hard。 在節(jié)目集中有12個(gè)節(jié)目形成6個(gè)抄襲對。

e命名為Hard。 在節(jié)目集中有12個(gè)節(jié)目形成6個(gè)抄襲對。 “清潔”：k-均值。 一維k均值聚類程序，使用絕對距離作為距離函數(shù)，并在數(shù)據(jù)范圍內(nèi)以等距方式進(jìn)行初始化。 平均節(jié)目長度是118 LOC。 這個(gè)程序集根本不包含任何剽竊行為，因此將其命名為Clean。

“大”：跳箱。 一個(gè)簡單的圖形游戲，玩家必須將鼠標(biāo)移動到屏幕上跳轉(zhuǎn)的方塊。 這套節(jié)目平均時(shí)間最長，也是節(jié)目設(shè)計(jì)中最大的節(jié)目; 平均節(jié)目長度是263 LOC。 在節(jié)目集中有4個(gè)抄襲對。 它還包含另外兩個(gè)具有很多相似性的對，但我們不認(rèn)為它們是實(shí)際的剽竊。 其中之一，這兩個(gè)程序員顯然在早期階段一起工作，但后來獨(dú)立完成了他們的程序。 另一方面，這兩個(gè)程序共享一個(gè)共同的分?jǐn)?shù)作為基礎(chǔ)，并從早期的AWT編程練習(xí)中獲得。

為了更仔細(xì)地調(diào)查JPlag的行為，我們的程序集中的實(shí)際剽竊數(shù)量不足。 因此，我們通過在網(wǎng)站上公開發(fā)布“尋求剽竊”并通過電子郵件收集意見書來收集進(jìn)一步的剽竊。 回答我們的電話的學(xué)生和其他程序員從我們的網(wǎng)頁下載了一個(gè)源程序，對其進(jìn)行了修改并將其發(fā)回。 他們被告知要像一個(gè)剽竊并試圖欺騙剽竊檢測計(jì)劃的學(xué)生行事，特別是不要花費(fèi)過多的時(shí)間。 中間80％的剽竊者最終使用了7到40分鐘的自我報(bào)告時(shí)間。

對于發(fā)布的12個(gè)原始程序（從硬件程序集6和大型程序集6中隨機(jī)選擇）中的每一個(gè)，我們因此收集了14個(gè)剽竊版本，導(dǎo)致多達(dá)105個(gè)額外的抄襲對?；谶@些額外的剽竊，我們?yōu)镴Plag的評估形成了額外的程序集（請參閱表3）：
Hard.all基于Hard和其他一系列剽竊行為的結(jié)合
收集它。
Hard.P基于Hard.all，但僅包含所有這些程序
也存在抄襲（原創(chuàng)或收集）。在這個(gè)程序集中，一個(gè)很大的
所有節(jié)目對中的一小部分是抄襲對。
Large.all和Large.P是基于Large和
為此收集了更多的剽竊品。

請注意，為了簡潔，Hard.all和Large.all將在3.2和3.3節(jié)中分別討論，但包含在3.4和3.5節(jié)中，其中我們還使用了Hard.all中的兩個(gè)較高抄襲內(nèi)容的較小子集和另外兩個(gè)來自Large.all

JPlag可以被視為一個(gè)具有固定查詢的信息檢索系統(tǒng)：給定一組程序?qū)?，檢索所有那些是剽竊的對，但沒有其他的。 對于這樣的操作模式，我們只需要通過應(yīng)用截止閾值將每對產(chǎn)生的相似度值轉(zhuǎn)化為是/否決策：具有高于閾值的相似度的所有對將被認(rèn)為是抄襲對。

為了表征JPlag輸出的正確性，我們可以使用通用信息檢索質(zhì)量度量“精度”（P）和“回憶”（R）。 這些措施的定義如下。 假設(shè)我們有一組n個(gè)節(jié)目，其中p = n·（n-1）/ 2對，這些對中的g是抄襲對，即一個(gè)節(jié)目從另一個(gè)抄襲或者兩個(gè)抄襲都是（直接或間接）抄襲 一些共同的祖先也是程序集的一部分。

現(xiàn)在假設(shè)JPlag返回f個(gè)標(biāo)記為剽竊對的程序?qū)Α?如果這些對中的t是真正的抄襲對，而其他的f - t不是，那么我們將精確度和回憶定義為P：= 100·t / f和R：= 100·t / g，即精度是 實(shí)際抄襲對和召回標(biāo)記對的百分比是實(shí)際標(biāo)記的所有抄襲對的百分比。

此外，我們將100·g / p定義為剽竊內(nèi)容，即所有抄襲對的分?jǐn)?shù)（見表3的“％”欄）。

如第2.2節(jié)所述，JPlag算法中有兩個(gè)自由參數(shù)：最小匹配長度M和使用的令牌集。 這兩種情況在我們的研究中也有所不同。

默認(rèn)標(biāo)記集“normal”包含描述主要程序結(jié)構(gòu)（變量聲明，類/方法的開始/結(jié)束等）和控制流（返回，中斷，繼續(xù)，拋出，if，while，等等的開始/結(jié)束）的標(biāo)記。 ），加上2個(gè)令牌（分配）和方法調(diào)用（應(yīng)用）。 它忽略了表達(dá)式（操作符，操作數(shù)）內(nèi)的所有結(jié)構(gòu)以及方法的標(biāo)識等。除了默認(rèn)的標(biāo)記集，我們還使用了一個(gè)相當(dāng)小的標(biāo)記集（稱為“struc”），其中只包含與控制流和程序塊結(jié)構(gòu)相關(guān)的標(biāo)記 但不包括變量聲明）。 此外，我們使用了包含所有可能令牌的最大令牌集（稱為“滿”）。
我們使用了最小匹配長度3，4，5，7，9，11，14，17，20，25，30和40. 9是默認(rèn)值。

為簡要總結(jié)JPlag的性能，我們將首先報(bào)告使用標(biāo)準(zhǔn)參數(shù)（最小匹配長度9，正常標(biāo)記集）和50％截止閾值時(shí)我們每個(gè)數(shù)據(jù)集的精度和召回率的值。 摘要顯示在表3最右邊的兩列中。

正如我們所看到的，JPlag的性能對于簡單，清潔和大型來說是完美的; 對于我們四個(gè)真實(shí)世界的數(shù)據(jù)集中有三個(gè)我們不但無一例外地獲得所有的抄襲對，而且輸出也完全沒有非抄襲對

對于困難的數(shù)據(jù)集Hard，我們錯(cuò)過了6個(gè)抄襲對中的2個(gè)（R = 0.67），并錯(cuò)誤地檢索了7個(gè)非抄襲對以及4個(gè)正確的抄襲對。 不完全召回當(dāng)然可以通過降低截止門限來改善，但這也會導(dǎo)致更多不正確的輸出。 這個(gè)折衷將在3.3節(jié)中分析。

具有高剽竊密度的人造數(shù)據(jù)集的結(jié)果也非常好：JPlag檢測到兩種病例（Large.P和Large.all）中所有剽竊對的92％，另外兩種（Hard.P 和Hard.all），除一個(gè)案例（Hard.all）外，結(jié)果完全沒有虛假輸出。

鑒于我們在第4節(jié)中介紹的程序設(shè)計(jì)者嘗試的各種偽裝嘗試，這些結(jié)果相當(dāng)令人印象深刻。

理想情況下，JPlag會報(bào)告任何非抄襲對的0％和任何抄襲對的100％的相似度。 但實(shí)際上，這種區(qū)別幾乎沒有那么清楚。 因此，為了判斷先前顯示的結(jié)果的穩(wěn)健性，我們現(xiàn)在回顧JPlag為抄襲對產(chǎn)生的相似性值的分布，并將其與非抄襲對的分布進(jìn)行比較。 如果兩個(gè)分布重疊，則一個(gè)或多個(gè)節(jié)目對將被錯(cuò)誤地判斷

簡單：“最大化流量”程序。 我們的第一個(gè)例子是程序集Simple。 結(jié)果顯示在圖2中。該程序集導(dǎo)致總共378個(gè)程序?qū)?，其中只?個(gè)是實(shí)際的抄襲對。 圖的上半部分顯示了376個(gè)非抄襲對的相似度值分布，即2個(gè)抄襲對的底部。

JPlag在相當(dāng)廣泛的截止門檻范圍內(nèi)將剽竊與其他節(jié)目完美區(qū)分開來。 圖3的左側(cè)部分顯示了當(dāng)我們逐漸增加截止閾值時(shí)回想如何改變：只有在相當(dāng)高的截止閾值時(shí)，我們才會錯(cuò)過任何剽竊行為。 精確度和召回率之間的折中結(jié)果顯示在圖的右側(cè)。 我們總是至少有完美的精確度或完美的召回率，對于適當(dāng)選擇的截止閾值，我們甚至可以同時(shí)得到兩者，即曲線到達(dá)曲線的右上角（100/100，理想點(diǎn)）。

總結(jié)起來，JPlag的行為對于這個(gè)程序集是完美的。
硬：“多重排列”計(jì)劃。 請記住，該算法的簡單性表明了一個(gè)有點(diǎn)規(guī)范的程序結(jié)構(gòu)。 因此我們可以期望這個(gè)程序?qū)Plag來說是一個(gè)非常困難的測試。

硬：“多重排列”計(jì)劃。請記住，該算法的簡單性表明了一個(gè)有點(diǎn)規(guī)范的程序結(jié)構(gòu)。因此我們可以期望這個(gè)程序?qū)Plag來說是一個(gè)非常困難的測試。圖4確實(shí)表明Hard程序集的行為不太理想：相似性值分布有相當(dāng)多的重疊。讓我們首先考慮一下，注意在絕對數(shù)量中，剽竊對的分布幾乎可以忽略不計(jì)，因?yàn)樨飧`的內(nèi)容只有0.3％。盡管存在困難，但非剽竊的相似度值的分布幾乎與Simple相同。另一方面，除了一個(gè)例外，Hard中的6個(gè)抄襲對僅表現(xiàn)出中等相似度，即使對于人類觀察者也是如此?？纯丛闯绦颍覀兊玫搅诉@樣的印象，即學(xué)生們大部分都在一起工作，但無論如何都可能獨(dú)立完成他們的程序。但是，鑒于節(jié)目規(guī)模較小，無法確定。所以人們可以說，這些根本不是剽竊。但是為了得到一種最壞的情況分析，讓我們假設(shè)這6對確實(shí)都是真正的剽竊。然后，精度/回憶權(quán)衡是遠(yuǎn)遠(yuǎn)不理想的（參見圖5底部），但中等截?cái)嚅撝等匀粚?dǎo)致合理的妥協(xié)，如前所述回收67例。

3.4令牌集合和最小匹配長度的影響

到目前為止所有的數(shù)據(jù)都使用了JPlag的默認(rèn)參數(shù)：“正常”標(biāo)記集和標(biāo)準(zhǔn)最小匹配長度為9.但是，我們也感興趣的是JPlag如何抵抗這些參數(shù)的變化以及這些變化如何與 程序集進(jìn)行分析。 因此，下面介紹性能測量，我們將研究JPlag的性能如何針對不同的最小匹配長度，截止閾值，令牌集和程序集進(jìn)行更改。

我們通過精確度和召回率的加權(quán)和來衡量JPlag的總抄襲鑒別性能。 我們選擇3的回憶（相對于精確度）的相對權(quán)重，因?yàn)閼土P假陰性（非檢測到的抄襲）遠(yuǎn)遠(yuǎn)大于誤報(bào)，這僅僅為人類用戶的最終判斷提供了更多的工作。 因此，績效指標(biāo)變?yōu)镻 + 3R。 確切的值3并不重要，重量為2或4的結(jié)果將是相似的。

我們將在這里省略分析的大量細(xì)節(jié)，僅提供結(jié)果; 更多的細(xì)節(jié)可以在[Prechelt et al。，2000]中找到。 當(dāng)分析使用“正?！睒?biāo)記集合和截止閾值50時(shí)最小匹配長度M與P + 3R量度之間的相關(guān)性時(shí)，我們做出以下觀察：

1. M的最佳值可能取決于所選擇的截止閾值。 這并不奇怪，因?yàn)檩^小的M會導(dǎo)致通常較高的相似性值。

2.因此，增加M的總體表現(xiàn)趨勢可能是向上，向下或山形。因此，任何固定的M都必須被認(rèn)為是妥協(xié)。

4.低的最小匹配長度往往會產(chǎn)生虛假匹配，從而降低精度。

5.高的最小匹配長度傾向于錯(cuò)過更多的抄襲區(qū)域，從而減少回憶，特別是對于抄襲內(nèi)容更高的人工程序集。

6.總體而言，除非所選擇的價(jià)值遠(yuǎn)離最優(yōu)價(jià)值，否則性能損失很小。

我們得出這樣的結(jié)論：JPlag對M的適度非最佳選擇是強(qiáng)有力的。

使用小型“struc”標(biāo)記集的相同分析發(fā)現(xiàn)，由于標(biāo)記字符串較短，較大??的M值不太可取。否則，結(jié)果與默認(rèn)令牌集的結(jié)果非常相似。

最后，對于最大可能的令牌集，稱為“完整”，我們發(fā)現(xiàn)由于較長的令牌字符串，更大的M可能更容易被容忍，但適度的值仍然傾向于優(yōu)越。否則，結(jié)果再次與缺省和縮減的標(biāo)記集相似。

我們得出這樣的結(jié)論：JPlag對于不同的令牌集合的選擇是高度可靠的。這很有用，因?yàn)樗砻鱆Plag對于許多其他編程語言也可以類似地工作，如果它們允許類似結(jié)構(gòu)的標(biāo)記集合。

此外，我們得出結(jié)論：默認(rèn)的標(biāo)記集合和默認(rèn)的最小匹配長度9是JPlag針對各種程序集的合理和可靠的參數(shù)選擇。

通常，我們會看JPlag找到的最相似的一對節(jié)目，并分別為每一對節(jié)目決定它是否是抄襲對。 人們將以這種方式朝著較低的相似度值前進(jìn)，直到人們確信發(fā)現(xiàn)了所有的剽竊行為。

然而，在某些情況下，基于相似性閾值的全自動決策是優(yōu)選的：具有該相似性或更高相似性的對將被視為剽竊，而具有較低相似性的對將被視為獨(dú)立。 我們稱這樣一個(gè)標(biāo)準(zhǔn)為截止標(biāo)準(zhǔn)。 截止標(biāo)準(zhǔn)接收相似值的向量s作為輸入，并且如上所述計(jì)算截止閾值T.

為了在全自動模式下評估JPlag，我們使用了許多不同的截止標(biāo)準(zhǔn)。 它們中的大多數(shù)適應(yīng)于正在調(diào)查的程序集的相似性分布。 從上面的討論中我們已經(jīng)知道在30到60范圍內(nèi)的截止閾值通常會產(chǎn)生最好的結(jié)果。 但是，目前還不清楚是否存在幾乎總是最佳的固定閾值。 考慮當(dāng)前相似度分布的適應(yīng)性標(biāo)準(zhǔn)可能會更成功。 這些是我們探索的截止標(biāo)準(zhǔn)：

脫粒。 截?cái)鄻?biāo)準(zhǔn)的threshT系列使用最簡單的方法：它根本不查看輸入矢量，而是應(yīng)用固定的截止門限來做出決定。 我們已經(jīng)使用了從30％到95％的各種閾值T，從而導(dǎo)致閾值thresh30到thresh95。

mplus。 mplusD家族的截止標(biāo)準(zhǔn)有點(diǎn)適應(yīng)于系統(tǒng)中較高或較低的s相似度值。 它返回向量中相似值的中值（50％分位數(shù)，q50）加上距中值到100的距離的D百分比：T = q50（s）+ D / 100 *（100-q50（s））。 與固定閾值相比，這些標(biāo)準(zhǔn)可以適應(yīng)不同的“基本相似性”; 他們認(rèn)為中位數(shù)相似度代表了一個(gè)典型的非抄襲對，因?yàn)檫h(yuǎn)遠(yuǎn)不到所有配對的一半都是抄襲對。 我們使用了mplus25，mplus50和mplus75。

qplus。 qplusD家族相當(dāng)于mplusD家族，除了偏移量的起點(diǎn)是第三個(gè)四分位數(shù)：T = q75（s）+ D / 100 *（100-q75（s））。 這個(gè)想法是q75可能代表一個(gè)更大的意外相似的情況，所以即使是小的D值也不應(yīng)該導(dǎo)致誤報(bào)。 我們使用了qplus25，qplus50和qplus75。

K均值。 kmeans截止標(biāo)準(zhǔn)使用一維k-均值聚類將矢量分成兩類。 具有較高相似性值的類將被視為抄襲對。

avginf。 avginf家族的截?cái)鄻?biāo)準(zhǔn)考慮具有大致相同的相似度值的對的信息內(nèi)容。這里的想法是，剽竊行為應(yīng)該是罕見的，因此表明剽竊行為的相似性值的范圍必須具有很高的信息含量（在信息理論意義上）。因此，我們選擇閾值T作為具有此相似度或更高相似度的對的平均信息內(nèi)容Cv≥T至少比整體平均值C高百分之P的最小閾值。為此，avginf標(biāo)準(zhǔn)將相似度值組合成重疊寬度為5％的類：給定所有對的相似度值的向量s，令Sv為s的值為v ... v + 5的相似度集合。然后，每個(gè)這樣的對的信息內(nèi)容為Cv：= - log2（| Sv | / | s |）和空類被定義為沒有信息內(nèi)容，即，如果Sv = C，則Cv：= 0?；谶@些值Cv，可以確定閾值。我們使用了avginf050，avginf100，avginf200和avginf400。

圖9比較了截止標(biāo)準(zhǔn)的性能分布，基于性能測量P + 3R。 對于原始程序集，最好的標(biāo)準(zhǔn)是thresh50，thresh60，qplus50和mplus50。 他們對于P + 3R的中位數(shù)都是400（即至少有一半的結(jié)果是完美的），平均值約為330，第一個(gè)四分位數(shù)約為280.對于人工程序集，沒有一個(gè)標(biāo)準(zhǔn)能夠達(dá)到。 最好的是thresh40，qplus25和mplus25。 這是一個(gè)好消息：出于實(shí)際目的（剽竊數(shù)量通常很?。?，像閾值這樣簡單的規(guī)則似乎會產(chǎn)生最好的結(jié)果。

我們還通過MOSS [Aiken，1998]運(yùn)行我們的基準(zhǔn)程序集，對結(jié)果進(jìn)行后處理，使用與JPlag相同的相似性度量，然后計(jì)算各種截止閾值的精度和召回率。 結(jié)果如表4所示。

表中的左邊部分假設(shè)了理想化的截止標(biāo)準(zhǔn)，在每種情況下都選擇最佳閾值。 請注意，MOSS通常會返回比JPlag相當(dāng)?shù)偷南嗨浦怠?正如我們所看到的，就簡單，清潔和大型（或其變體）而言，MOSS的性能與JPlag基本相同。 唯一的區(qū)別是MOSS必須比JPlag更強(qiáng)烈地依賴于截?cái)嚅撝档目勺冃浴?/p>

然而，對于Hard程序集的變體，JPlag顯然是優(yōu)越的：對于Hard.P和Hard.all，JPlag以更好的精度實(shí)現(xiàn)相同的召回。 請注意，對于Hard.all，當(dāng)t = 30時(shí)，JPlag達(dá)到P = 46，R = 88，但是這具有較低的P + 3R。 而且，對于原始程序集Hard，MOSS無法找到三分之一以上的抄襲對，即使使用最低截止閾值10時(shí)也是如此。

如果我們?yōu)槊總€(gè)系統(tǒng)選擇一個(gè)固定的閾值，就會出現(xiàn)類似的情況，如表格的右半部分所示：我們將JPlag的相似度降低了50％，MOSS降低了30％。 這些閾值是合理的，往往會平衡精確度和回憶。 結(jié)果表明，JPlag的精確度或召回率比MOSS差，但是其中很多情況下，MOSS明顯比JPlag更差 - 特別是對于hard程序集。 如前所述，沒有關(guān)于MOSS算法的書面描述。 因此，我們無法解釋結(jié)果.

如果我們?yōu)槊總€(gè)系統(tǒng)選擇一個(gè)固定的閾值，就會出現(xiàn)類似的情況，如表格的右半部分所示：我們將JPlag的相似度降低了50％，MOSS降低了30％。 這些閾值是合理的，往往會平衡精確度和回憶。 結(jié)果表明，JPlag的精確度或召回率比MOSS差，但是其中很多情況下，MOSS明顯比JPlag更差 - 特別是對于硬件程序集。 如前所述，沒有關(guān)于MOSS算法的書面描述。 因此，我們無法解釋結(jié)果

JPlag的運(yùn)行時(shí)間隨著程序集中程序數(shù)量的增加而呈二次曲線增長，并且與程序的大小略微超線性。

但是，由此產(chǎn)生的運(yùn)行時(shí)間通常很小。 我們最大的節(jié)目集Large.all包含99個(gè)節(jié)目，平均約250個(gè)LOC。 JPlag用于閱讀和解析這些程序以及執(zhí)行所有配對比較的總運(yùn)行時(shí)間是Pentium III上的掛鐘時(shí)間大約6秒

本節(jié)分析偽裝技術(shù)和我們在用于評估的計(jì)劃中看到的攻擊類型。 任何單一的攻擊事件最多都會導(dǎo)致我們稱之為JPlag的局部混亂。 考慮應(yīng)用偽裝技術(shù)所需的最短代碼段。 如果JPlag沒有確定原始代碼段和攻擊結(jié)果之間的任何相似性，我們說JPlag在本地是混亂的。 局部混淆關(guān)鍵取決于所使用的令牌集和最小匹配長度。

例如，如果將單行代碼（或單個(gè)令牌）插入到最小匹配長度的代碼段中，可能會導(dǎo)致本地混淆。 插入后，JPlag通常不會再找到具有足夠的令牌來匹配的相應(yīng)代碼段。 再舉一個(gè)例子，如果最小匹配長度的代碼段被分成兩部分然后交換，JPlag也被欺騙了。

除非程序非常短，否則在剽竊逃避檢測之前需要進(jìn)行一些局部混淆（取決于截止標(biāo)準(zhǔn)）。 完美的攻擊將需要在原始代碼的每個(gè)片段中以最小匹配長度來實(shí)現(xiàn)局部混淆。 JPlag將會成功，除非剽竊者既富有創(chuàng)造性，足以發(fā)現(xiàn)足夠的偽裝技術(shù)，可以在整個(gè)給定的程序中應(yīng)用（大多數(shù)技術(shù)只適用于某些情況），然后渴望足夠頻繁地應(yīng)用它們。

本節(jié)討論的攻擊根本不起作用，因?yàn)樗鼈儾粫Plag生成并考慮的令牌列表進(jìn)行任何修改。 幾乎每個(gè)剽竊者都至少使用過這些徒勞的偽裝技術(shù)之一。

通過改變換行符，空格和TAB來修改代碼格式[48 times3]

插入，修改或刪除評論[30次]

程序輸出或其格式的修改[33次，2次成功]在2個(gè)程序中，修改后的輸出格式導(dǎo)致額外的方法調(diào)用。

更改變量，方法或類的名稱[44次]

分割或合并變量聲明列表[6次]

修改器，如私人，最終等[6次]

常數(shù)值的修改[3次]

有些學(xué)生根本沒有試圖偽裝他們的作弊，并提交了相同的副本。 如果提交次數(shù)過大，無法手動比較所有數(shù)據(jù)并且沒有自動系統(tǒng)，則可能會發(fā)生這種“攻擊”。[4次]

正如我們從這個(gè)列表中看到的，JPlag對格式化，評論，文字和名稱的完全無知是其成功的關(guān)鍵。 為默認(rèn)令牌集選擇的粗粒度（例如，忽略修飾符）也是有用的。

粗略地說，Java類由方法和變量的聲明組成。 聲明的排序是無關(guān)緊要的。 因此，一個(gè)有前途的攻擊行是重新排序?qū)崿F(xiàn)中的聲明。 但是，如果重新排序的代碼段長于最小匹配長度，則JPlag信號將阻止移動，而不是在本地混淆。 因此，這種攻擊的成功與否關(guān)鍵取決于其應(yīng)用的粒度。

剽竊者經(jīng)常使用這種類型的重新排序[55次]。 但是，他們中只有大約15％實(shí)際上混淆了JPlag。

在變量聲明塊內(nèi)重新排序[25次，6次成功]

變量和方法聲明的全局重新排序[30次，3次成功]

以下類型的攻擊通常在本地成功，至少使用默認(rèn)的令牌集。 在134次這些襲擊中，只有12次不成功。 然而，只有極少數(shù)的剽竊者在一個(gè)特定的程序中實(shí)現(xiàn)了如此之多的局部混淆以逃避被發(fā)現(xiàn)。

修改控制結(jié)構(gòu)[35次，全部成功]

   ?用while循環(huán)代替for循環(huán)，反之亦然[8次]
   ?通過用主迭代變量[3次]表達(dá)它們來消除輔助指標(biāo)變量
   ?用無限循環(huán)代替常規(guī)循環(huán)[1次]
   ?用一系列if語句替換switch-statement [6次]
   ?為switch語句的每個(gè)case添加冗余break-statements [1次]
   

臨時(shí)變量和子表達(dá)式[28次，全部成功]

   ?將子表達(dá)式轉(zhuǎn)換為新的輔助變量[16次]
   ?反之亦然[7次]
   ?通過賦值列表替換數(shù)組初始值設(shè)定項(xiàng)[2次]
   ?從聲明中移除初始化[2次]
   ?用默認(rèn)值[1次]顯式初始化
   

內(nèi)聯(lián)和重構(gòu)[20次，16次成功]

   ?內(nèi)聯(lián)小方法[5次]
   ?將現(xiàn)有方法的部分重構(gòu)為新方法[11次]
   

修改范圍[9次，全部成功]

   ?將合理性測試或試驗(yàn)塊的開始/結(jié)束移向方法的開始和/或結(jié)束[3次]
   ?將臨時(shí)變量移動到周圍的塊中[3次]
   ?在內(nèi)部塊中添加臨時(shí)變量的冗余聲明[1次]
   ?如果只有一個(gè)實(shí)例存在，則用實(shí)例變量替換類變量[2次]
   

重新排序基本塊內(nèi)的獨(dú)立語句[8次，6次成功]

利用數(shù)學(xué)身份[5次，2次成功]

自愿引入程序缺陷[5次，3次成功] 3名剽竊者刪除代碼或添加其他語句。 兩次不成功的嘗試涉及修改后的常量。

修改數(shù)據(jù)結(jié)構(gòu)[6次，5次成功]

   ?用char數(shù)組替換字符串[1次]
   ?用兩個(gè)多帶帶的int [1次]替換int [2]
   ?用數(shù)組替換幾個(gè)相同類型的變量[3次]
   ?提升整數(shù)[1次，不成功]
   

冗余[15次，14次成功]
?添加或刪除未使用的代碼[7次]
?使用完全限定的軟件包名稱[2次]
?插入虛擬方法的調(diào)用[1次]
?導(dǎo)入額外的軟件包和類[1次]
?將呼叫插入到Thread.yield（）[1次]
?在void方法結(jié)束時(shí)插入return [1次]
?復(fù)制右側(cè)無副作用的賦值語句[1次]
?訪問實(shí)例變量時(shí)添加或刪除此事件[1次，不成功]作為對策措施，JPlag的默認(rèn)令牌集將忽略此設(shè)置。

代碼結(jié)構(gòu)重新設(shè)計(jì)[3次，全部成功]

   ?將狀態(tài)改變方法轉(zhuǎn)換為多帶帶的新類[2次]
   ?創(chuàng)建并返回一個(gè)新對象，而不是改變現(xiàn)有狀態(tài)[1次]
   

在這個(gè)列表中，最后三種類型的攻擊是非常聰明的，即使對于讀者來說也很難檢測：修改數(shù)據(jù)結(jié)構(gòu)，添加或刪除冗余，或重新設(shè)計(jì)代碼結(jié)構(gòu)。

我們使用4套真實(shí)Java程序和另外幾套包含額外剽竊的Java程序集對JPlag進(jìn)行的實(shí)證評估可總結(jié)如下：

對于清楚剽竊的節(jié)目，即完全采用節(jié)目并進(jìn)行修改以隱藏起源的節(jié)目，JPlag的結(jié)果幾乎完美 - 即使節(jié)目長度少于100行也是如此。

即使只有部分剽竊節(jié)目，就像我們的硬盤節(jié)目集合一樣，JPlag將指出相似之處，并且通?？梢院芎玫貐^(qū)分它們與意外相似之處。

剽竊者從真實(shí)程序集中選擇的偽裝（如果有的話）對JPlag完全沒用。

即使是知情剽竊者選擇的攻擊在所有案例中的成功率都不到10％。 這些人知道他們必須欺騙一個(gè)程序，并沒有其他目標(biāo)（除了只用一點(diǎn)時(shí)間來完成）。

對JPlag檢測的成功攻擊需要很多工作，或者會產(chǎn)生一個(gè)對任何人員檢查員來說都很荒謬的程序結(jié)構(gòu)。

JPlag非常適合對其兩個(gè)自由參數(shù)，令牌集和最小匹配長度的非最優(yōu)選擇。

給定JPlag計(jì)算的相似度值，一個(gè)固定的截止閾值就足以作為一種判別標(biāo)準(zhǔn)，它將剽竊的程序?qū)εc非剽竊的程序?qū)Ψ蛛x，并且具有接近最佳的回憶率，但仍具有良好的精確度。

我們并不確切知道這些結(jié)果轉(zhuǎn)移到其他情況的程度。 它們可能適用于C和C ++的較小程度，因?yàn)檫@些語言目前尚未解析，但僅由JPlag掃描。 對于不同結(jié)構(gòu)的（或更大的）程序，如果這些攻擊使某些攻擊更加有效，或者對于不同的攻擊者（如果那些攻擊者仍然使用不同的攻擊）

但是，總體而言，如果JPlag的有效性遠(yuǎn)遠(yuǎn)低于證明的效果，我們會感到驚訝。 看起來基于標(biāo)記的字符串相似性方法對尋找剽竊非常有效，至少如果令牌字符串忽略了足夠的細(xì)節(jié)。 對于用Java，C，C ++和Scheme編寫的程序，JPlag是一種易于使用的實(shí)現(xiàn)方法.

原則上，JPlag也可以用于其他目的。 如果一家軟件公司懷疑競爭對手竊取了部分源代碼，那么在法院命令或雙方協(xié)議后JPlag可以比較兩個(gè)有問題的大型程序系統(tǒng)并指出類似的區(qū)域。 JPlag已經(jīng)成功應(yīng)用于這種情況下（其各方希望保持匿名）.

通過指出不同的區(qū)域，而不是那些相似的區(qū)域，JPlag可以用作程序差異引擎（如Unix diff）。與基于字符的差異相比，JPlag差異忽略了很多細(xì)節(jié)，因此產(chǎn)生了更小的（盡管 也不太精確）的差異，這在某些情況下可能有用。

文獻(xiàn)名稱： Lutz Prechelt , Guido Malpohl , Michael Philippsen. Finding Plagiarisms among a Set of Programs with JPlag[J]

前端VUe代碼的github地址

后端地址SSM