虚拟团队的领导角色与成员互动之社会网路分析-淡江大学

《虚拟团队的领导角色与成员互动之社会网路分析-淡江大学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

淡江大學資訊管理學系碩士班碩士論文指導教授：魏世杰博士學生程式碼相似度之研究—以抄襲偵測之應用為例ResearchonDetectionofSimilarityinStudentPrograms–withApplicationtoDetectionofPlagiarism研究生：林世唐撰中華民國94年6月61 誌謝本論文順利完成，最重要的是要感謝我的指導教授魏世杰老師這給予我的指導，不辭辛苦的跟我討論論文的研究，並給予我很多寶貴的意見和指正。也非常感謝三位口試委員陳安斌老師、陳彥良老師和梁恩輝老師提供我論文上的指正和改進，讓我的論文能夠更加完整。再者，要感謝714的同學和淡江學弟妹們，謝謝大家一起陪我熬夜做研究，讓我們渡過了最堅難的日子。另外，感謝陶笛界的朋友，包括山莊的朋友和國北師的學生，謝謝你們用音樂替我打氣，讓我能專心一致的研究論文。最後要感謝我親愛的家人，爸爸、媽媽和妹妹，謝謝你們一直支持我走我想走的路和做我想做的事。林世唐謹於私立淡江大學中華民國九十四年六月二十日61 論文名稱:學生程式碼相似度之研究—以抄襲偵測之應用為例頁數:57校系所組別:淡江大學資訊管理學系碩士班畢業時間及提要別:九十三學年度第二學期碩士學位論文提要研究生:林世唐指導教授:魏世杰博士論文提要內容:程式的相似判斷不像文字那麼複雜，比起文字的語法來說，程式的文法更有規則性。程式相似判斷的應用上有很多方面，在實際教學應用上，最常用來作抄襲的檢測。但我們發現在可以參考範例的考試或作業下，可能因為修改自相同的範例程式，因此雖然找出大量相似片段組，但有很多相似是因為參考範例本身而相似，不具抄襲意義。另一方面，在資訊檢索領域有IDF(InverseDocumentFrequency,反轉文件頻率法)的概念，發生頻率高的片段較不具意義，發生頻率低的片段較具意義。因此我們提出以IDF為主的新方法，幫助我們找出發生頻率低的相似片段組，視為較有抄襲可能性之片段。並用開放式(openbook)的一次考試和一次作業程式來作驗證。關鍵字：程式比對、結構度量、抄襲偵測、反轉文件頻率法61 TitleofThesis:ResearchonDetectionofSimilarityinStudentPrograms–withApplicationtoDetectionofPlagiarismKeywords:ProgramCompare,StructureMetric,PlagiarismDetection,InverseDocumentFrequencyTotalPage:57NameofInstitute:GraduateInstituteofInformationManagementTamkangUniversityGraduateDate:June,2005DegreeConferred:MasterNameofStudent:LinShih-Tang林世唐Advisor:Dr.WeiShih-Chieh魏世杰博士Abstract:Similaritydetectiononprogramsissimplerthanontextdocuments.Comparedtotextdocuments,thegrammarusedinprogramlanguagesiseasiertodefine.Asaresult,moreandmoreapplicationsaredevelopedtodetectprogramsimilarity.Onepracticaluseoftheseappicationsistodetectplagiarismforeducationalpurposes.Inparticular,whenstudentshavetestorhomeworkonprogramswheretheycanopenbookstoconsulttheexamples,theymaycopyfromtheexampleprogramswithoutmuchthinkingandrewriting.Inthiscase,wewillfindmanysimilarcodetilesthatarecopiedfromthesameexamplebutoflittlevalueinplagiarismdetection.SointhispaperbasedontheIDF(InverseDocumentFrequency)conceptfrominformationretrieval,weproposeanewmethodtoreducetheinfluenceofhighfrequencycodetiles,andcomparewithtraditionalnon-IDFresultusingthedatasetsfromanopen-bookprogramtestandahomework.61 目錄第一章緒論1第一節動機與目的1第二節論文貢獻2第三節論文章節概要2第二章文獻探討4第一節屬性比對4第二節結構度量(StructureMetric)5第三章相似度與抄襲的定義11第一節程式碼相似度的比對11第二節程式相似度的應用11第三節程式相似度在抄襲的運用12第四章問題定義與實驗限制15第一節程式相似範圍定義15第二節YAP在可參考範例下的誤判15第三節引入IDF的概念15第四節引入曾氏演算法16第五節實驗限制16第六節利用相似度來做抄襲判斷17第五章系統架構18第一節系統模組圖19第二節參數設定20第三節前處理：程式轉為符號序列21第四節比對過程：曾氏演算法21第五節評分公式22第六章實驗結果分析與討論25第一節能力分析25第二節抄襲片段排名分析28第三節召回率和準確率計算32第七章結論與未來研究方向3361 表格目錄表格一結構度量常用系統方法之比較9表格二結構度量常用系統能力之比較9表格三不同最小比對長度值下本系統與YAP的比較27表格四兩系統與人工的排名差異量29表格五考試程式用本系統和YAP做出的前40名片段29表格六作業程式用本系統和YAP做出的前40名片段31表格七召回率和準確率計算結果3261 圖形目錄圖一：Faidhi的六個等級程式改寫14圖二：系統模組圖19圖三：相似門檻值和有效相似門檻值區間20圖四：最小比對長度=7下，與第1支程式的相似度27圖五：最小比對長度=7下，與第8支程式的相似度28圖六：最小比對長度=7下，與第15支程式的相似度2861 第一章緒論第一節動機與目的抄襲一直是學校電腦教育中，很重要的議題，尤其在程式語言課程上，抄襲的行為更為嚴重。過去有很多的研究文獻，討論如何去預防和檢測學生的考試和作業，避免學生有抄襲的行為。預防通常是著重在管理面上，透過事先告知學生什麼是抄襲的行為，並花時間宣導討論，最好能展示抄襲的例子，讓學生可以加以避免觸犯。而在檢測上，通常是比較困難的部份，尤其是當一個班級人數多時，每次要比對50幾份至100多份的程式，單純靠人工的比對，往往會發生混亂的，而且是相當累人的一件工作。因此這個檢測的工作可以交由程式來完成，而學生的程式或作業通常會出現的抄襲範圍只包含到語法上的相近，對於語義上的抄襲，應被視為一種已學習的成果。所以對於程式的語法上比對，用簡單的工具就可以來完成了。目前程式比對的工具相當多，他們利用各種文字比對的方法，將程式視為兩段文字序列，來判斷兩隻程式的相似度，如果兩隻程式的相似度過高，則可以判斷他們之間具有較高的抄襲可能性。比對工具會回報給使用者，再讓使用者去判斷兩隻程式之間是否有抄襲的行為。有些工具經過前處理後，對於做了註解或變數命名等的簡單改寫的程式，仍可以檢測。然而，雖然已經有這麼方便的工具，可以幫助做抄襲的檢測，但我們在實際教學時仍然遇到難題。因為大部分的程式寫作需要參考書本上的資料，或網路上的文件。因此程式課程的考試，常常是採開放方式(open61 book)。程式課程的作業，也大部分是跟課本範例類似的習題。在這樣的環境下，學生可以去參考課本範例，或是網路上的範例，而在我們無法掌握這些範例程式來源，使用一般的比對工具，所找出來的大量相似程式，事實上可能是因為他們都參考了同一個範例，因此有很高度的相似性。但這樣的參考是我們所允許的，所以不能算是抄襲。而目前的工具都無法有效區別實際抄襲和這些假抄襲的不同。因此在本論文中利用抄襲具有少部分特有相似的特性，排除因大量被參考的範例造成的高相似度的誤判。幫助我們在檢測抄襲時，能更加準確且有效。第一節論文貢獻一般來說，學生程式的抄襲比對工具，是利用程式之間的相似度去做判斷。但在有參考範例之下的作業或考試，對參考同一來源的程式，相似度都相當高，容易收集到無用的資訊。我們利用關鍵字粹取的方法，取得每一種片段被多少隻程式所共同擁有。利用抄襲的特性，我們找出現頻率低，但長度長的片段，作為具有高可能性的抄襲片段。第二節論文章節概要本篇論文主要可以分成下列幾個章節，內容大綱如下:第一章:緒論介紹本論文解決的問題和貢獻第二章:文獻探討探討目前常見的比對方法和抄襲檢測工具，並分析各種工具的能力和優缺點。第三章:相似度與抄襲定義分別對我們論文的相似度和抄襲範圍做定義。第四章:問題定義與實驗限制詳細解說我們要解決的問題，以及我們系統的實驗限制和解決問題的範圍。第五章:系統架構與參數設定說明系統的架構以及所用到的參數設定和評估值的計算。第六章:實驗結果分析與討論分析我們系統與對照系統的實驗結果，並討論系統的效應。第七章:結論與未來研究方向61 對本論文實驗結果下結論以及未來系統可以改進的目標。61 透過網路溝通管道的虛擬團隊領導、信任和團隊效能之相關性研究---以學習任務導向之虛擬團隊為例TheEffectsofLeadershipandTrustonthePerformanceofVirtualLearningTeams效果(Isthetrustamoderatingorindependentfactorontheteameffectiveness?Noneedtomentionleadershipfornow.)。JarvenpaaandLeidner(1999)歸納團隊發展時期有哪些溝通行為和成員活動可以促進快速信任(swifttrust)建立和持續維護信任關係，正面領導就是其一要素，團隊領導者必須能夠整合團隊與網路資源，督促並鼓勵團隊成員。Zaccaro(2002)也認為虛擬團隊領導人是團隊信任的滋潤劑。在虛擬團隊裡領導者是核心，促進溝通並建立團隊歷程，背負著任務完成的責任(DuarteandTennant-Snyder,1999)。David(2003/2004)用行動學習方法歸納虛擬團隊領導人與成員關係建立模型，領導人是「關係中介者」，進行任務前要建立關係，對成員更多了解、親近、信任、動機，才有較佳的工作關係，對未來再度合作也有助益。所以本研究欲進一步探討領導效能對團隊信任的影響(needtomakeastrongercasebystatingearlywork61 hasnotaddressedleadershipstyleastheantecedentsoftrustandtheireffectsonperformanceinvirtualteams.)Trytobespecific!David(2001)於網路和傳統(電話)溝通管道幫助虛擬團隊建立關係研究中指出，不同的溝通管道有不同的效果，溝通管道的選擇與使用跟環境、擁有的資源和關係的欲達程度有關，因此本研究將探討網路溝通管道對領導效能及信任關係的影響(Virtualteamscanbeoperatedviadifferentmedia.Yet,itisunclearifthechoiceofmediahasanyeffectontheleadership,trustorboth.)領導效能如何影響團隊信任領導效能、團隊信任與團隊效能之相關性網路溝通管道是否會影響領導效能與團隊信任第一章文獻探討Clough[1]曾在他的文章中提過，比對程式比起比對自然語言的文件簡單多了，因為程式的文法書可以完全的定義出來，但自然語言則複雜多了。Clough的文章也提及到數個當時已存在的程式比對方法[20]，大致可以區分為兩類：一是屬性比對[3][4][8][10][17]，一是結構度量[2][6][13][15]16][21][22]，亦有綜合兩種的[7][11][18]。第一節屬性比對61 Sallis等人將Clough所提到的屬性比對的方法縮小範圍，用六個維度來代表出程式相似的程度。這六個值很清楚的刻晝出程式的特性，僅管是一佪長程式可能有很多的屬性值，都可以用這六個元素表達出來，因此極具有代表性。一、取值(Volume)用Halstead[9]的sofewaresciencematrics可以量化演算法，並且所得到的值可以用來代表此演算法的大小。因此，我們要先求出底下六個值：n1(單獨或唯一的運算子個數)n2(單獨或唯一的運算元個數)N1(全部使用到的運算子個數)N2(全部使用到的運算元個數)n=n1+n2(字詞數)N=N1+N2(執行長度)接著就可以求出一個V值：V=Nlog2n而這個V值就可以用來代表一隻程式的屬性。二、結構(Structure)這個元素利用某些指標表示出模組間相聯的程度，這可以提供程式的資料和控制轉變的表象。三、資料相依(DataDependency)藉由程式流程圖的描繪出來，資料之間的相依性可以用敘述或變數定義的方式，記錄在節點內。記錄的方式可以採用Bieman和Debanth的GeneralisedProgramGraph(GPG)的格式。四、迴圈深度(NestingDepth)61 計算程式的平均迴圈深度只需統計每一行程式碼的深度，再把這些總數除以程式的總行數即可。五、控制結構(ControlStructure)將程式中所有發生的控制結構給予一個比重，然後對所有的程式都可以計數出一個比重值，這個值就可以用來代表程式的複雜度。六、控制流程(ControlFlow)控制流程可以採用McCabe’sCyclomaticComplexity來計算，此演算法需先把程式碼轉換成單一進單一出的程式結構圖，因此他是與程式語言相關的。屬性比對的方法具有簡單且可快速比對的特性，對於兩隻程式的整體比較相當的方便，可惜他所得的資訊是屬於整體的，對於實際那一段落有相似，並無法顯示出來，所以我們可以改用結構度量的方式來比對。也就是透過網路溝通管道(科技子系統)的虛擬團隊領導、信任(社會子系統)和團隊效能(團隊績效與合作滿意度)之相關性研究。第一節結構度量(StructureMetric)字串結構的方式，是從本文比對的方法延用過來的。底下是幾個過去使用過的方法：一、DotPlotDotPlot可以用視覺化的方式呈現兩個片段程式的比對狀況。因為他不受限於特定的程式，因此並不需要去了解程式語言本身的語法和語義。DotPlot最大的功用在於幫助使用者去利用視覺化系統去找出成對的部分。雖然如此，但此系統也只能幫助找出相似的部分，卻無法對結果做量化，這也造成他的缺點。二、MOSS(MeasureOfSoftwareSimilarity)61 moss[16]是一種將程式的符號字串(tokenstring)，每相鄰的k個符號合併計算一個雜湊值，也就是如果有n個符號，就可以計算出n-1個雜湊值，每一個雜湊值都隱藏著一些資訊，包括他在程式的位置和他的內容等，從這些雜湊值集合選擇他的部分子集合做為指紋(fingerprinter)，例如，取雜湊值可以被4整除的。依照雜湊的原理，不相同的子串得到相同的雜湊值的碰撞機率是很小的。因此，如果兩隻程式有一個或更多個雜湊值相同，那他就有k-gram的相同性。三、YAP(YetAnotherPlague)YAP[7][21][22]是一套可以偵測程式中可能抄襲的片段，目前最新版本是YAP3。此系統背後的演算法可以幫助我們找出程式中相似的部份。最新的YAP3所使用的演算法是Running-Karp-RabinGreedy-String-Tiling(RKR-GST)，而RKR是用來最佳化GST的演算法的速度，使其執行的複雜度為O3。GST則是實際比對出兩隻程式相似部分的演算法。GST的演算法分為兩個階段，一個是前處理階段，負責把來源和目標程式碼做轉換以下的工作：l移除註解和固定字串l轉換大寫字母為小寫字母l將同義字對應到一般格式(如function轉換為procedure)l依照呼叫的順序重新排列function的次序。並把第一次呼叫到的function展開，之後的呼叫則以FUN替代。l移除非程式語言字彙的字第二個階段則是對來源和目標程式做比對。正式引用GST演算法的地方，他有幾個基本概念：l片段(tile)是來自來源和目標的程式一對一成對的子字串。l當一個符號成為片段的一部份，我們稱他被標記(marked)了lMaximalMatch(MaxM)類似片段，但是他只是從來源和目標程式得來的一個暫時成對子字串。61 lMinimalMatchLength(MinML)定義為搜尋出最小片段長度，而比MinML小的片段都將被乎略。GST演算法所要做的工作，就是找出來源和目標程式的最大片段。首先找出來源和目標程式中相同而不重疊，且大於MinML的子字串，接著再將片段能覆蓋到的符號擴到最大數量。四、JPlagJPlag[13][15]與YAP的方法相似，核心都採用了GST演算法的方式，但在符號化(tokenizer)的部分，JPlag不像YAP單純的只保留下關鍵字(keyword)和運算子，他還對符號上做了一些集合的處理。l前處理：前處理的部分是跟要比對的語言相關的，目前能處理的只有三種語言，包括Java和Scheme可以做”full”的的集合轉換。而C和C++可以做到”scanner-based”的集合轉換(只有做符號取代)。在符號選擇上，JPlag排除了空白，註解，和變數命名。並將語義的概念放入符號中，舉例來說，他用BEGIN_METHOD的符號來代替函式開頭的大括號，這樣子可以避免潛在的假相似造成的誤判。l比對：JPlag的比對方式是使用GST的演算法，找出兩個符號文字序列中最長的相似片段。可以分成兩個步驟：步驟1：在這個步驟裡，要找出兩個字串最長的連續片段。他做了三次的迴圈，第一次對A程式做掃瞄，並記錄所有的片段，第二次對B做掃瞄並找出出相同的片段，當找到相同的片段，則進入內迴圈去延伸片段到最大的相同長度。步驟2：第二步，把第一步找到的片段標記起來，並重複第一步比對，而標記起來的部分，就不會再第一步時再使用到，這樣可以確保所找到的片段不會重複使用到。61 JPlag是一套線上使用的系統，所有的程式必須上傳至JPlag的主機去比對，JPlag再透過網頁的方式顯現出來。五、SID(SoftwareIntegrityDiagnosissystem)由Chen[2]等人所提出的，一種利用壓縮方式，來找出程式相似片段的方法。基本上他與YAP和JPlag一樣，都可以分成兩階段，第一階段也是將程式轉換成符號字串，第二階段則不是像YAP用GST演算法做文字的比對，而是利用壓縮器(compressor)找出兩隻程式相似的片段。他的演算法如下：Input:一個符號字串sOutput:Comp(s)及相同的片段組i=0;一個空的bufferB;while(i<|s|)p=FindRepeatPair(i);if(p.compressProfit>0)EncodeRepeatPair(p,compFile);i=i+p.length;OutputRepeatPair(p,repFile);elseAppendCharToBuffer(si,B);i++;EncodeLiteralZone(B,compFile);returnComp(s)=compFile.filesize及在repFile的相同片段組SID的方法可以避免因大量插入無意義的敘述，如intx=1等。對MOSS或JPlag，可能都會造成偵測不出來，但SID可以解決這樣的問題。六、SIM(softwareSIMilaritytester)61 SIM[6]的系統是由Gitchel等人所提出的，他利用DNA比對上常用的序列排比(alignment)方式，來計算兩隻程式之間的相似性。序列排比[23][24]的方法有很多種，例如”masters”和”stars”兩個字串的排比可以為masters或mastersstarsstars分別給每個成對的字元分數，相同為m，不同為d，空白為g，最佳的排比是能找出所得的分數最高的，利用得到的分數，可以比較兩隻程式的相似性。七、各系統比較表格一結構度量常用系統方法之比較DotPlotMossSIMJPlagSIDYAP本系統前處理斷字詞斷字詞取關鍵字和運算子結構標記替換取關鍵字和運算子取關鍵字和運算子分類關鍵字和運算子比對法人工比對g-gramedit-distanceGST壓縮法GST曾氏[19]分析文法程度無低低高低低低表格二結構度量常用系統能力之比較DotPlotMossSIMJPlagSIDYAP本系統改寫註解XXOOOOO變數命名XXOOOOO更改順序XOX部分O部分部分更換型別XXXOXXO插入無用敘述XXO部分O部分部分更改迴圈寫法XXXXXXX61 更改選擇結構寫法XXXXXXX表格一和表格二為現行常用的結構度量的程式比對工具之比較。在比對方法上，DotPlot和MOSS的前處理，都只是單純的將程式做斷字詞，而SID,SIM和YAP會對斷出來的字詞做篩選，只保留程式的關鍵特性字。而JPlag則會對斷出來的字詞依內容做文法上的改寫。而分析文法程度這項，則是看前處理對符號化的過程是否有考慮到程式語法的結構性，程度高在能力上會比較精準，但在運用到不同語言上，也相對的較不方便。在能力的比較部分，YAP和JPlag在某些狀況下更改順序和插入無用敘述會破壞比對的結果。以屬性方法去判斷相似程度，雖然速度較快，通用性較高，但他只能對兩隻程式做相似性，並無法確切找出可能相似的地方在那裡。而利用結構度量則可以找出實際可能相似的片段，對我們在檢視程式上更加有用。以上結構度量的工具適用在簡單的程式寫法上的比對，最常被用來做為學生程式的抄襲偵測之用。61 相似度與抄襲的定義第一節程式碼相似度的比對在程式碼比對的研究文獻上，比文字比對還要來得多。主要的原因是程式的比對比自然語言來得容易。程式語言的複雜文法可以被定義出來，而自然語言的文法，則複雜且不確定多了，因此在比對上有比較高的難度。與文字比對一樣，我們對程式碼的比對，也可以區分在只是語彙上的比對，或是文義上的比對。程式語彙上的比對與文字的語彙比對相近，是以字詞為單位，找出來源程式與比對程式之間相同的部分。而單純的使用程式的語彙來做比對，會受到更改註解或更改變數名稱的影響。因此許多比對的工具，會選擇有用的字詞來做比對，最常見的是使用程式特有的保留字和運算元等。對註解或變數名稱則在前處理時，將其捨棄或做一致性的改寫，再將處理後的字串序列送到文字比對器去比對。如此可以避免一些等級低的程式改寫。另一種以結構去分析的程式碼相似度，必須將程式碼轉換成結構圖或流程圖，再將來源程式和比對程式的流程圖，依節點互相比對，找出最接近的兩個節點。利用流程圖，比單純用語彙的比對來得精確多了，對於程式的控制流程或是迴圈被改寫，也能判斷出他們具有相似性。利用節點的比對，可以知道每個節點所做的工作，並且比對兩個節點的工作內容是否有相同，因此有對程式功能性的相似做判斷。然而結構上的比對程序上比較複雜，且模糊度也較高，因此須更多複雜的人工智慧去處理。第二節程式相似度的應用從大量的程式碼找出相似的部分，是非常有用的，常見的應用有以下幾個方面[12]：一、軟體系統分析61 在軟體發展工程上，常需要對大規模的軟體元件進行修改、改造或使用。通常這些都是傳統資訊系統，缺乏完整的文件、鬆散的結構和難以去理解。因此隨著時間變長，就變得十分難維護。在這樣情況下，我們可以透過程式比對，加快程式開發的速度，且能夠更深入了解軟體系統。二、軟體元件庫的查找對程式開發者而言，常常會需要參考其他相似的範例程式，來加速他們開發程式的速度，這些範例的程式，集結在一起成為軟體元件庫，提供程式開發者需要時可以去查找。一般找尋相似程式碼的方法是用grep-like的搜尋或是普通的文字檢索引擎，然而程式開發者通常需要一個能更深層查尋程式集的工具。三、程式重複和合併軟體開發者在開發大型程式時，常會出現程式碼重複的現象，主要的原因有兩個，一個是因為習慣性使用剪貼(copy-and-paste)的方式來複製相同功能的程式碼，另一個原因則是對軟體設計沒有完全的了解，因此在軟體再造時，重複了寫了相同的程式碼，另一方面軟體開發者也常需要將新程式碼與舊程式碼做合併，這時就要找出適當的程式點將新程式碼合併到舊程式碼中。四、抄襲偵測由於電子文件和程式碼的特性，使得他們很容易被複製和修改，程式碼抄襲的偵測方式又與文字模式不同，因此不能單純用一般文字的搜尋引擎。第一節程式相似度在抄襲的運用61 判斷程式之間的相似度，最常用來做為程式抄襲的檢測。具有高相似度的兩隻程式，相對也有較高的抄襲可能性，但是否有抄襲的行為，還必須透過人為的判斷。抄襲是一種將其他人的成果重新再製，而未加以告知的行為。程式的抄襲如同文章的抄襲，可能只是單純的複製貼上，也可能是複雜性的語義改寫。而抄襲的判定在不同的領域之下，有不同的界定，例如在學校教育上對於抄襲的界定，可能著重在寫法上的相似，而如果摸仿者有能力將來源的文章或程式加以語義或方法上的改寫，在教育的意義上，他已經對所學的知識加以吸收，並有能力重新組織且以不同的方式呈現，因此這一類的相似，並不被歸為抄襲的行為。但在企業間，獨特的創意對企業是相當重要的資產，因此在抄襲的認定上，就必須包含到語義或程式功能的相近，屬於比較高等級的改寫。針對不同抄襲界定的須求，所用的抄襲檢測工具也會有所不同。學生考試或作業的檢測，只要判別出文字和架構上的相近，而企業上的抄襲檢測，必須考慮到功能相近或語義相近的抄襲檢測能力。Parker和Hamblen[13]對軟體抄襲下了定義，”一個程式經由某些特定的規則，做少部分轉換而產生出另一個程式”，而這些特定的轉換，可以從很簡單(改變程式碼註解或改變程式碼變數名稱等)到很複雜(置換同等意義的控制流程，例如for迴圈改寫成while)。Faidhi和Robinson[4]則用圖畫表示出程式改寫的六個等級，如圖一，而愈外圍的等級，也代表則愈高程度的改寫。Whale[20]也提出更明確抄襲可能使用的方法和抄襲偽裝的方式，包括有：l更改註解l更改資料形態l更改變數命名l加入多餘的敘述或變數l更改選擇敘述的寫法l結合複製和原始程式的敘述一套好的抄襲檢測軟體能夠檢測出可疑的程式碼。要有效的區分偶然造成相似和抄襲造成相似的不同。抄襲造成的相似存在著一些不平常的文字或片語，且恰巧的在兩個程式之間都具有相似的不常見片段。因此我們關心的是那些特殊的相同部分。61 圖一：Faidhi的六個等級程式改寫隨著我們對抄襲的界定範圍不同，而選用的抄襲偵測系統能力也不相同。用來對企業間的程式抄襲偵測，必須要能做到Faidhi等級五甚至於等級六的偵測。而對學生程式的改寫類型，大都局限在前四等級的抄襲。因此所用的抄襲偵測工具，也都以前四個等級的改寫為主，後面我們將會深入探討幾個常見的抄襲偵測工具，分別如何對前四等級的改寫做判斷。抄襲的行為在學校教育上特別容易出現，因為學生可以很容易的從書本、範例或同學之間取得參考資料，加上現在網路上的發達，資訊的電子化，更容易被重覆使用。但在某些情況之下，教授允許可以參考書本範例或與同學互相討論，在這樣有條件的給予參考程式，造成學生的作業或考試與參考程式具有相似性，這樣的抄襲行為就非我們所關心的了。一般的抄襲偵測工具，可以找出沒有任何參考資料下的作業或考試。但對於開放式考試(openbook)或可互相討論的作業程式，就不能有效的找出抄襲的部分。我們沿用舊有系統的方法加以改良，並利用抄襲特有的觀念排除出現頻繁高的相似部分，找出罕見的特殊相似部分，用來處理有參考資料下的作業或考試的抄襲偵測。第一章61 問題定義與實驗限制第一節程式相似範圍定義第一節研究方法的選擇(Writemoreforthissection)第二節研究架構(YoucanmovetheResearchModeltoyoursecondsection)團隊效能․團隊學習績效․團隊合作滿意度使用多種資訊科技網路溝通管道領導效能領導角色H56第三節研究假說上述61 在不同目的之下，對程式抄襲範圍定義會有所不同，如果運用在企業間軟體程式碼的比對，則必須要考慮到程式文法和結構的相似。而學生作業和考試的程式，則以寫法相近為主。在學生作業上的抄襲偵測，主要也在找出寫法相近的片段。因為不同的目的下，所要使用的比對工具也就不相同，用來比對學生作業和考試程式的比對工具，主要以有能力分辦簡單的變數更換、順序改寫等就足夠了，對於複雜的結構或文法的改寫不常出現，亦較不具有抄襲的意義。我們可以用Faidhi程式改寫六個等級來區分，學生程式的改寫侷限在前四個等級之內。因此我們選用簡單的結構度量工具，來做為我們程式比對之用，其中又以YAP這項工具最為好用，他具可免費取得和簡單的將程式序列化兩種特點，其精確度在過去的研究[18]顯示用在對學生作業的偵測上，也相當的準確。但可惜的如果考試或作業資料可能參考允許的共同範例時，YAP無法有效的排除。第一節YAP在可參考範例下的誤判YAP雖然適用處理學生程式的比對上，但必須假設兩兩程式之間是獨立寫作的，沒有可以做為參考的範例程式。但在實際的開放式考試(open-book)下，任何人都有可能以與題目相近的範例程式下去改寫，在課後作業，也可能以課堂上教過的範例下去改寫。以YAP去偵測，會對所有參考相同範例的程式都有相近的相似片段，但這些來自於合法的參考範例的相似，並不是我們要偵測的抄襲片段。第二節引入IDF的概念IDF(InverseDocumentFrequency)是在資訊檢索上常用到的一種計算關鍵字詞重要度的方法，其概念為在一文獻集合中，如果一個字彙出現次數很高，表示該詞彙的字義很廣，不應給予太高的加權，如果一個詞彙出現在某一篇文獻的次數很高，表示該字很重要。在程式抄襲中，也有相同的特性。61 當考試或作業被控制在不能輕易抄襲他人程式時，抄襲的行為應是發生頻率少，而長度長的相似片段。發生頻率多的相似片段，則可以視為因為參考了同一個範例程式，或是常見的習慣性寫法。因此我們可以利用IDF的概念，找尋發生頻率少，而長度長的相似片段，此片段具有較高的抄襲可能性。第一節引入曾氏演算法YAP的GST演算法在計算片段在程式集合中的發生頻率，必須全部比對完之後，再去做片段的統計，在使用上比較麻煩。為了能夠有效計算出每種相似片段被多少隻程式所共有，我們改用一種關鍵字萃取的曾氏演算法來取代YAP的GST比對，此演算可以找出所兩隻程式以上的相同片段組，並且可以得到該片段組為那些程式所共同出現的，利用他出現的頻率，我們可以做為該片段組抄襲的重要性。第二節實驗限制我們所用的方法與GST相近，都是找出兩隻程式之間最長的程式序列。但這樣的方法會在某些情況之下，造成無法辨視的情況[15]。一般來說，用最大字串長度比對方法，找區塊為最大連續字串。因此，如果抄襲所做的更改顆粒小於最大比對長度，就很容易造成遺失。我們的系統也存在這種抄襲更改的範圍過小，而使系統混淆的情況。不過依Parker對程式抄襲的定義，我們可以知道抄襲是將某程式做少部分程序性的改寫，我們可利用其他部分的相似，判斷是否有抄襲的可能。另外，我們的系統使用前，必須滿足兩個假設：1.參考課本範例或題庫範例是合法的，不視為抄襲行為。2.抄襲的行為擴散是小範圍的，可能僅散播給少數人使用。在以上兩個假設前提下，我們用新的演算法來與YAP的GST演算法做比較。61 第一節利用相似度來做抄襲判斷我們採用的抄襲偵測方法，是利用程式之間的相似度，來對抄襲做判斷。因此對於兩隻程式，我們比對他們之間的相似程度，相似度高的，則認為具有抄襲的可能。對於兩隻程式之間可能做了什麼樣的改寫，或是做了那一類型的改寫，檢測工具並無法明確的說明，但我們可以將相類似的片段提供給使用者查看，讓使用者可以自行判斷兩個片段之間是否有做改寫。如果需要進一步去了解程式碼之間做了什麼樣的改寫，則必須使用結構圖或流程圖來比對，並做人工智慧的分析。但就我們運用在學生程式上，以輔助檢測抄襲為主。因此我們採用計算相似度來協助使用者做判斷。61 系統架構我們使用的方法是來自於結構度量的YAP，因此也同樣分為前處理跟序列比對兩部分。YAP在前處理的階段，是取用較具意義的保留字和運算子做為程式序列的符號，而我們進一步再對符號做分類，以避免型別更改的抄襲。再序列比對的部分，YAP原本是使用GST(Greedy-String-Tiling)演算法，以找出兩個程式序列中最長的相似片段，但為了有效的計算片段在程式集合中出現的頻縴率，我們改採用了關鍵萃取的曾氏演算法[19]來取代原本的GST比對方法，改良後的曾氏演算法除了可以達到原本GST的序列最長比對，更能快速的收集片段被引用的次數，以方便我們計算IDF的評分。61 第一節系統模組圖程式資料集字符斷字器MML曾氏演算法程式相似片段集合匯總兩兩程式之間相似片段總合依引用度和片段長度排名THSIDF兩兩程式之間的相似度前40名片段前處理階段比對階段評分階段程式相似排名片段抄襲排名圖二：系統模組圖61 第一節參數設定在我們的系統裡，要先設定兩個參數，分別是最小比對長度和相似門檻值。一、最小比對長度和相似門檻值依Wise[22][22]所研究的結果，較長的相同子字串，比短的子字串來的更具相似意義。對於過短的連續片段，我們應該加以排除。因此我們必需定義一個值，稱為最小比對長度(MinimalMatchLengthMML)。在最小比對長度底下的相同片段，我們把他摒除，我們的最小比對長度是以符號(token)為單位。相似門檻值非相似平均值加一標準差相似平均值減一標準差非相似集合相似集合有效相似門檻值區間圖三：相似門檻值和有效相似門檻值區間相似門檻值(SimilarityThresholdTHS)，是用來決定我們切割兩個程式是否有相似。好的門檻值應該落在相似群組的減一個標準差，和非相似群組的加一個標準差之間，此區間我們稱為有效相似門檻值區間，當相似門檻值落在此區間，我們都可以對相似和非相似的程式做有效區分。但相似門檻值會受到最小比對長度的影響，太大或太小的最小比對長度，可以使用的門檻值區間都會變得很窄，甚至無法有效切割，所以適當的最小比對長度，可以讓我們有足夠的區間可以使用，而我們也習慣把門檻值切割在區間的正中央。61 第一節前處理：程式轉為符號序列前處理將程式字串做適當的符號化。符號化方式只取用關鍵字和運算子做為我們的符號。為了加強我們的系統的精準度，我們再進一步將具有相近意義的符號給予相同的符號取代，例如：”int”,”float”,”double”等，取代為變數宣告類(_VARDECL)，”private”,”protected”,”public”等，取代為存取層級類(_ACCESS)。其他還有指派運算符類(_ASSIGOP)，和比較運算符類(_COMPOP)。其他未在此四類的符號，仍用原本的字串表示。第二節比對過程：曾氏演算法在比對的演算法，我們不同於YAP的GST演算法，我們使用的比對演算法是改良自曾氏演算法[19]，由輔仁大學曾元顯博士所提出的，原本的目的是用在文章中的關鍵字的萃取，而我們將他運用在程式的符號字串的比對上，其演算法如下：1.ConvertthesourcefileintoasrcLISTofoverlappingMML2.ConvertthedestinationfileintoadstLISTofoverlappingMML3.While(srcLIST!=null^dstLIST!=null)3.1.setsrcMergeLISTanddstMergeLISTasnull3.2ForeachpairofadjacentelementsK1andK2indstLISTdoIF((K=merge(K1,K2))istrue^srcLIST.contain(K1,K2)dstMergeLIST.add(K))ElseIF(srcLIST.contain(K1)^K1didnotmergewiththeelementbeforeitindstLIST)FinalLIST.add(K1)3.3.ForeachpairofadjacentelementsK1andK2insrcLISTdoIF((K=merge(K1,K2))istrue^dstLIST.contain(K1,K2)srcMergeLIST.add(K))ElseIF(dstLIST.contain(K1)^K1didnotmergewiththeelementbeforeitinsrcLIST)FinalLIST.add(K1)3.4.setsrcMergeLIST=srcLIST，dstMergeLIST=dstLIST，doWhile3.outputFinalList61 演算法中merge(K1,K2)是判斷K1和K2是否是相隔一個符號的兩個片段。如果是的話則可以合併為更長的K片段。contain(K1)則判斷LIST中是否存在K1這元素。add(K1)則可以K1加入到LIST中。舉例來說，如果有來源程式符號為”BACDB”和目標程式集為”CDABACD”，而我們的最小比對長度設為2，則我們將相鄰的2個符號組成一個元素分別放入srcLIST和dstLIST中，我們可以得到srcLIST(BAACCDDB)和dstLIST(CDDAABBAACCD)，接著我們重複演算法的步驟2，srcLIST和tarLIST中的元素做合併，可以依序得到以下的srcLIST(BACACD)dstLIST(BACACD)及srcLIST(BACD)dstLIST(BACD)。合併的過程中，在FinalList中我們得到了(CD:1)(BACD:4)。其他的元素在過程中我們都捨棄掉了。而利用這個演算法，我們收集到BACD和CD這兩種程式片段。曾氏演算法是一種用來萃取文章中所有可能出現k次以上最長的關鍵字。把他改良用在程式比對上，也可以找出兩兩程式之間所有可能共同(k=2)出現的最長程式片段，並且可以同時計算片段在全部資料集中發生的頻率，對於頻率低的長片段，他的抄襲可能性也相對比較高，在取得片段發生的頻率，比原本單純只用GST演算法來得快。第一節評分公式經由系統比對的結果，可以得到相似的片段和片段在程式集中的發生頻率，而系統提供給使用者，可以以單獨片段排名的方式，讓使用者直接觀看排名高的片段發生在那些程式中，亦可以利用相似片段進一步去計算兩兩程式之間的相似度。一、程式相似排名為了讓使用者可以更明確比較兩隻程式之間的相似程度，我們定義兩兩程式之間的相似值計算方法，公式定義如下：61 其中sFile,tFile分別是來源程式和目標程式的符號序列，而表示在sFile內可能與tFile有相相似的符號數總合，則表示在tFile內與sFile有相相似的符號數總合。我們得到的相似分數大小介於0跟1之間，愈接近1的得分，表示兩隻程式的相似性愈高。而利用相似門檻值(THS)的設定，我們可以決定大於相似門檻值的程式組，具有抄襲的可能性。在以程式的相似度為抄襲評分下，亦可以導入引用度(IDF)的概念，但因為在公式計算上尚無法找出合適的評分法，故我們的系統這部分的評分並沒有導入引用度的計算，其計算方法與YAP的評分相近。二、片段抄襲排名為了幫助使用者可以找出抄襲的部分，我們分別利用YAP和我們的系統找出相似的片段，並將相似的片段做排名，再回傳排名前40的相似片段給使用者。YAP的排名是以相似片段的長度做為排名，片段長的相似者比較有相似性。而我們的系統則是以IDF的概念，提出以引用度為排名的法則。我們依抄襲指值的值，來做為片段排名的依據，片段發生頻率高的，表示片段被引用的次數多，因此較不具有抄襲意義，因此抄襲指數會被降低。而相對應YAP在這部分沒有考慮引用度，因此只單純以相似片段長度做為排名的依據。61 將兩個系統所得到的前40名片段集合起來共80個片段，再由人工去挑選前40名片段，做為人工排名的結果。用來評估兩個系統所做出排名與人工排名相比較，算得排名差異值(Diff)。其排名差異量公式為：為編號r片段的排名，m為機器算出的排名，h為人工算出的排名。r=1…40為機器前40名的片段編號。當排名差異量低時，表示機器的排名與人工排名結果相近。三、召回率和準確率我們利用二個指標:召回率(Recall)、準確率(Precision)來評估系統的效能。61 實驗結果分析與討論第一節能力分析能力分析實驗為我們的系統對YAP的比較，以確定我們採用新的演算法在一般情況下比對的結果能與YAP有相同的能力。我們用以已知的資料集去判斷我們的系統和YAP能否有效的判斷出相類似的程式出來。一、能力分析資料集能力分析用的程式資料集，來自於三本不同的資料結構的書所附的範例程式http://web.engr.oregonstate.edu/~budd/books/jds/，我們挑選三本書中的有關BubbleSort的程式，三隻程式之間雖然在bubblesort架構上相近，但所用的方法不相同，其中一隻元素是使用陣列儲存，另兩隻是用物件儲存，而物件方法中的其中一隻的變數的交換是使用物件自訂函式處理，另兩隻則是直接指派的方式。因此這三隻程式彼此之間相似性並不高。我們參考Granville[7]的實驗方法，將每個程式做6種不同等級的改寫：L0:原始程式，不做任何修改。L1:加入或更改註解及字串的內容。L2:將L1的程式加以更改變數的命名。L3:將L2的程式加以更改宣告方式，包括宣告額外的變數，改變變數宣告的位置，和函式的順序。L4:將L3的程式加以更改程式的模組，包括合併兩個函式，或分割一個新的函式，或重複寫一相同的函式。L5:將L4的程式加以更改程式的寫法，包括for換成while，if換成switch等。L6:將L5的程式加以更改程式邏輯寫法，包括比較元素，順序的變換。從三個原始61 程式下去做改寫，每一個程式會得到另外六隻相似的程式，連同我們的三隻原始程式，就成為我們的測試資料集了。愈後面的改寫，變化愈大，與原始程式相距也愈遠。資料集程式請參考AppendixA。二、與YAP能力比較為了評估我們系統的效能，我們將對系統做能力的分析，以及針對我們需求的分群目的，做正確性評估，並且將YAP的結果與我們的結果做比較。我們用YAP的GST演算法來與我們的演算法做比較，資料集來自於三本不同的資料結構書，所寫的BubbleSort的程式，每一個程式我們做七等級的改寫，成為21隻程式。再利用兩種演算法所算出資料集與三隻原始程式的相似度。相似集合的來源是來自同源改寫的程式，非相似集合就是其他不同源的改寫程式，例如我們放入第一隻來源程式去與全部21做比對，則前7隻程式就為此比對下的相似集合，其他14隻程式則為非相似集合。分別對三隻原始程式去與21隻程式做比對，並求得相似集合的平均值減一個標準差的位置，及非相似集合的平均值加一個標準差的位置，並計算此區間的大小。表格三錄的是在不同最小比對長度下，對三隻程原始程式比對所得的平均值。大於11和小於4的最小比對長度，由於相似和不雷的集合相重疊，故其結果不列入比較。三、結果分析由表格三看到我們的系統平均區間大小都比YAP來得大，但是因為程式碼的長度都很短，所以與YAP的差距並沒有很大。從圖四圖五和圖六來看，在第四級之後的改寫，我們都能得到比較高的相似度，這是因為第四級有程式片段重複複製的改寫，這部分是YAP所不能檢測到的。而圖五在第三級改寫上，是有改寫到變數的宣告型態，而比對的結果也看出來我們的系統比YAP來得高，這也表示在這點上，我們的系統能優於YAP的比對。將此系統用在一般的程式比對狀況下，能有優於YAP的比對效果。表格三不同最小比對長度值下本系統與YAP的比較本系統YAP61 最小比對長度相似集合平均值減一個標準差非相似集合平均值加一個標準差平均區間大小相似集合平均值減一個標準差非相似集合平均值加一個標準差平均區間大小110.5133070.0699210.4433860.4394470.0630590.376388100.5776810.10013330.47754770.4493090.09004730.359261890.5965490.1173890.4791590.4780230.0873250.39069980.6425860.1380470.5045390.4780230.0873250.39069970.6938120.1479660.5458470.5233310.1149590.40837260.7272590.2863010.4409570.5764740.2265360.34993850.78520940.30708760.47812180.59685380.23607560.360778240.8206330.3982560.4223780.647660.2830660.36459461 圖四：最小比對長度=7下，與第1支程式的相似度圖五：最小比對長度=7下，與第8支程式的相似度61 圖六：最小比對長度=7下，與第15支程式的相似度第一節抄襲片段排名分析在抄襲片段分析上，我們利用我們的系統和YAP系統分別找出最可能抄襲的相似片段，並做排名，在機器找出的前40名中，與人工排名的結果相比較，評估兩個系統的與人工排名的差異性。一、抄襲排名分析資料集用來做抄襲排名分析的資料取用來自於92學年度淡江資管多媒體結構課程，學生期中考試程式和學生課後作業程式各一題，考試採上機考，可參考書本範例，不可相互討論的方式。作業為兩人一組的小組作業，不得與其他組討論。考試資料集約有180隻程式，作業資料集約有63隻程式。二、抄襲分析過程與實驗數據我們分別以我們的系統和YAP的系統，對考試和作業的資料集作比對，最小長度的設定如果在小於第40名的片段長度，則對前40名的排名不會有影響，因此我們採用能力分析實驗所找出來相似區間最大的最小比對長度7，做為我們的系統和YAP系統找出前40名的參數值。我們分別找出兩系統抄襲可能性高的前40名片段組，收集兩個系統的各別前40名片段組，形成80個相似片段組，由人工去對80個相似片段組做排名，並比較機器排出的前40名片段組在人工中的排名，用排名差異量的公式計算出他們與人工排名的差異，分別得到如下的結果：表格四兩系統與人工的排名差異量最小比對長度=7下本系統YAP考試程式排名差異量144824作業程式排名差異量63400表格五和表格六分別利用本系統和YAP61 系統對考試和作業所做出來的片段排名，片段的長度以tokens數表示，分別紀錄兩個片段的來源程式編號和在程式內的位置。我們可以發現用YAP做出的排名，前40名中，幾乎是同樣的幾隻程式之間互相的雷同。以考試資料集而言，YAP的前40名中，是同樣的9隻程式的相互雷同。而作業資料集是同樣的17程式的相互雷同，因此YAP找出的前40名片段受到來自同一個參考程式的影響，而我們的系統判斷這些片段重覆頻率太高，因而給予較低的抄襲可能值。表格五考試程式用本系統和YAP做出的前40名片段本系統做出的片段排名YAP做出的片投排名排名抄襲指數人工排名程式一編號和起始行數程式二編號和起始行數片段長度人工排名程式一編號和起始行數程式二編號和起始行數1224448952136814895214261483414865201322487060484222172488341958348952115234834148652013224875207842317614895207821489521418248341486520132248752096624175348852116184895201219483414865201322487520990151466488521948648952160836483414865201322488350488261435488520361548852172454834148652013224885202703713874895218142489521848248341486520132248852060138133404890017591489520527248341486520132248952040219129848952021274905271071148341487060484248752078421012894885206431248952057674834148706048424875209662111253948952012134489521723634834148706048424875209901121251048952036012489521236144834148706048424883504882131201148947019431489520121344834148706048424885202703141192048852113844895208735483414870604842488520601315117124895212931148952145984834148706048424895204021161151348952129354895202469483414875207842487520966217111144895212931048852128612483414875207842487520990118111154893403301148952031134834148752078424883504882191102148852607964895212441483414875207842488520270320108164895204281948952159051483414875207842488520601321108174885211611489521459148341487520784248952040212210818488520676149489520543148341487520966248752099012310119489340330748952012184834148752096624883504882241012248852109634905271073483414875209662488520270325101234885201971948952150925483414875209662488520601326982448852074263488520742824834148752096624895204021279325489521715124895202799483414875209902488350488261 28922648852144398488521443114483414875209902488520270329922748852651744488521286234834148752099024885206013309228488521096548952114584834148752099024895204021319029488520676171489520162184834148835048824885202703328930489520196104895207334483414883504882488520601333883148952109514895207331483414883504882489520402134843248952019613489520394748341488520270348852060133583334905271313149052713136483414885202703489520402136823448852127854885200315483414885206013489520402137823548952129357489001452403144248952067524895207092388136489521541248845084123144248952067524895206422398137489001452424895216579631442489520642248952070924080384905270991048852003193144248852041124895206422表格六作業程式用本系統和YAP做出的前40名片段本系統做出的片段排名YAP做出的片投排名排名抄襲指數人工排名程式一編號和起始行數程式二編號和起始行數片段長度人工排名程式一編號和起始行數程式二編號和起始行數15161041254105282011213224791128012552820112142347422295725282011218244193341521528201122125419920323352820112242625385147813528201122737247472050195282011230382217389409528201123739210113534444852820112422101885750606852820112432111786508781320528201124821216114561483352820112882131601228122152075282011289214141138518419138528201128215110152612782136528201129216108178510526995282011290217103182274410528201321421810216122884505282013218219981935775282013221220942185219281145282013224261 219322821761514352820132273229223814118056528201323032391241213822252820132373247925269782975282013242225582631178123252820132432265727392345375282013248227462836687555282013288228412956968124652820132892293830822048551152820132823036315129851125282013292313532315150185282013290232333350170854945282014218233333449887105282014221234313585170861475282014224235303645175612528201422733630373941567452820142303372838516586150528201423733827393187825252820142422392440814818028528201424324024415117803052820142482三、結果分析在我們的考試和作業資料集中，我們發現YAP找出來的排名高的片段組，在考試資料集中是由9隻程式所共有的，而作業資料集中，則是17程式所共有的，因此可明顯看出，YAP的前40名排名中，都為相同的一個出現頻率高且長度長的片段。而我們的系統對出現頻率高的片段組加以降低他的排名，因此出現在前40中的片段組，皆為兩隻程式所共有的長片段組，在判斷抄襲可能性上，也明顯比YAP的排名來得有意義，且接近人所期望的抄襲排名結果。第一節召回率和準確率計算我們分別計算能力分析實驗和抄襲片段排名分析所得的召回率和準確率61 表格七召回率和準確率計算結果本系統YAP召回率準確率召回率準確率能力分析1111抄襲片段排名分析不能計算0.9875不能計算0.5在抄襲片段排名部分，因為使用的是外測資料集，因此召回率的分數不能計算。在能力分析上，我們的系統與YAP的可以準確的判斷。而在抄襲片段排名分析，我們加入了引用度的概念後，明顯得在準確度上，比YAP來得高。61 結論與未來研究方向程式之間的相似度可以做為抄襲可能性的判斷，而過去的相關的文獻，對於學生程式抄襲的偵測，都採文字比對的方式。在我們的研究中，引用了資訊檢索裡，IDF反轉文件頻率的概念，來幫助我們做抄襲比對。對程式集中所有相似片段，發生頻率低的相似片段，應比發生頻率高的相似片段更具有抄襲的可能性。為了幫助我們找出相似片段發生的可能性，我們的系統使用了關鍵字萃取的演算法，來取代舊有YAP的文字比對方式。關鍵字萃取的方法，除了可以與YAP的GST演算法一樣，找出最長的相似片段，另一方面，他也統計各片段發生的頻率，幫助我們使用IDF的方式來做抄襲評估。因此在我們使用人工修改的抄襲程式測試集去對我們的系統和YAP做能力測試，發現我們的系統並沒有因為使用了關鍵字萃取的方法，而降低效能。更因為我們對變數型態改寫做了一致化的處理，因此，他能有更佳的檢測能力。而另一方面我們使用真實資料集，一次的學生考試和一次的程式作業，去對我們的系統和YAP系統做評估，發現YAP受到可參考範例的影響，可能的抄襲片段被掩蓋住了。反觀我們的系統，排除了受參考範例影響的片段，提供更具抄襲可能性的片段給使用者。因此我們可以說在假設與參考範例相同的片段不算抄襲，和抄襲的行為散播的範圍不大的兩個前提下，我們的系統能夠做出優於YAP的判斷，且更接近人工想得到的片段排名。程式相似除了以文字比對的方式檢測外，亦可用結構分析方式去做比對。而未來我們亦可進一步以結構分析的方式，配合IDF的概念，找出因抄襲行為造成的罕見的相似片段，結構分析比文字比對更精準，應可更準確的檢測公開範例下抄襲的持徵。另外，利用抄襲是罕見的相似的特性，我們應進一步考慮其他的罕見相似的特徵，例如出現相同的錯字，相同的排列格式，甚至是相同的註解或文字字串。這些特徵應更有助於我們偵測抄襲。61 參考文獻1.P.Clough,“PlagiarisminNaturalandProgrammingLanguages:anOverviewofCurrentToolsandTechnologies”,DepartmentofComputerScience,UniversityofSheffield,July2000.2.X.Chen,M.Li,B.MckinnonandA.Seker,“ATheoryofUncheatableProgramPlagiarismDetectionandItsPracticalImplementation”,UniversityofCalifornia,SantaBarbara,May5,2002.3.J.L.Donaldson,A.M.LancasterandP.H.Sposato,”APlagiarismDetectionSystem”,ProceedingsofThe12SIGCSETechnicalSymposiumonComputerScienceEducation,p.21-25,1981.4.J.A.FaidhiandS.K.Robinson,“Anempiricalapproachfordetectingprogramsimilarityandplagiarismwithinauniversityprogrammingenvironment”,ComputinginEducation,(11):1:,p11-19,1987.5.M.Ghosh,B.VermaandA.Nguyen,”AnAutomaticAssessmentMarkingandPlagiarismDetection“,InternationConferenceonInformationTechonologyandApplications2002Theme5,p.274-275,2002.6.D.GitchellandN.Tran,“Sim:AUtilityforDetectingSimilarityinComputerPrograms”,SIGCSEBulletin(31):1,p.266-270,1999.7.A.Granville,“DetectingPlagiarisminJavaCode”,UndergraduateProjectDissertation,TheUniversityofSheffield,May04,2002.8.S.Grier,”AToolThatDetectsPlagiarisminPascalPrograms”,SIGCSEBulletin(13):1,p.15-20,1981.9.M.H.Halstead,ElementsofSoftwareScience,1977,NewYork,Elsevier,127pages.10.E.L.Jones,“MetricsBasedPlagiarismMonitoring”,ProceedingsofThe6AnnualCCSCNortheasternConferenceonTheJournalofComputinginSmallColleges,p.253-261,May2001.11.R.J.Leach,“UsingMetricstoEvaluateStudentPrograms”,SIGCSEBulletin(27):2,p41-43,June1995.61 1.G.Mishne,“SourceCodeRetrievalUsingConceptualGraphs”,MasterofLogicThesis,UniversityofAmsterdam,December2003.2.A.ParkerandJ.Hamblen,“ComputeralgorithmsforPlagiarismDetection”,IEEETransactionsonEducation(32):2,p.94-99,May1989.3.L.Prechelt,G.MalpohlandM.Phlippsen,”JPlag:FindingPlagiarismsAmongaSetofPrograms”,UniversityofKarlsruhe,March28,2000.4.L.Prechelt,G.MalpohlandM.Philippsen,“FindingPlagiarismsAmongaSetofProgramsWithJPlag”,JournalofUniversalComputerScience(8):11,p.1016-1038,November28,2002.5.S.Schleimer,D.S.WilkersonandA.Aiken,“Winnowing:LocalAlgorithmsforDocumentFingerprinting”,ProceedingsofSIGMOD,p76-85,2003.6.M.L.SoffaandS.S.Robinson,”AnInstructionalAidforStudentPrograms”,ProcceedingsofThe11thSIGCSETechnicalSymposiumonComputerScienceEducation,p.118-129,1980.7.S.D.Stephens,“UsingMetricstoDetectPlagiarism”,ProceedingsofThe7thAnnualConsortiumforComputinginSmallCollegesCentralPlainsConferenceonTheJournalofComputinginSmallColleges,p.191-196,March2001.8.Y.H.Tseng,“MultilingualKeywordExtractionforTermSuggestion”,ProceedingsofThe21stAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval,p.377-378,1998.9.G.Whale,“IdentificationofPlagiarismSimilarityinLargePopulation”,TheComputerJournal,(33):2,p.140-146,April1990.10.M.J.Wise,“DetectionofSimilaritiesinStudentPrograms:YAP’ingMaybePreferabletoPlague’ing”,ProcceedingsofThe23stSIGCSETechnicalSymposiumonComputerScienceEducation,p.268-271,1992.11.M.J.Wise,“YAP3:ImprovedDetectionofSimilaritiesinComputerProgramandOtherTexts”,Proceedingsofthe27thSIGCSETechnicalSymposiumonComputerScienceEducation,p130-134,1996.12.孫士烘,“使用Edit-Distance比對C程式碼相似度”,私立中原大學資訊工程學系碩士論文,July200261 1.李昶宏,“利用序列比對演算法辨識抄襲之C程式作業”,國立暨南國際大學資訊工程學系碩士論文,May28,200461 AppendixA手工修改的三個測驗程式程式一_Level_00：importDataStructures.Comparable;importDataStructures.MyInteger;publicclassFig02_09{publicstaticfinalintNOT_FOUND=-1;publicstaticintbinarySearch(Comparable[]a,Comparablex){intlow=0,high=a.length-1;while(low<=high){intmid=(low+high)/2;if(a[mid].compareTo(x)<0)low=mid+1;elseif(a[mid].compareTo(x)>0)high=mid-1;elsereturnmid;}returnNOT_FOUND;}publicstaticvoidmain(String[]args){intSIZE=8;Comparable[]a=newMyInteger[SIZE];for(inti=0;i0)high=mid-1;else//Returnindexoffounditemreturnmid;}returnNOT_FOUND;}//ProgramtotestBinarySearchpublicstaticvoidmain(String[]args){intSIZE=8;Comparable[]a=newMyInteger[SIZE];for(inti=0;i0)up=middle-1;else//Returnindexoffounditemreturnmiddle;}returnNOT_IN;}//ProgramtotestBinarySearchpublicstaticvoidmain(String[]args){intnumItems=8;Comparable[]itemArray=newMyInteger[numItems];for(inti=0;iZERO_FLAG)up=middle-1;else//Returnindexoffounditemreturnmiddle;}returnNOT_IN;}}程式一_Level_04：importDataStructures.Comparable;importDataStructures.MyInteger;publicclassFig02_09{publicstaticfinalintNOT_IN=-1;publicstaticfinalintZERO_FLAG=0;publicstaticfinalintNUM_ITEMS=8;//ProgramtotestBinarySearchpublicstaticvoidmain(String[]args){searchResults();}publicstaticvoidsearchResults(){for(intj=0;jZERO_FLAG)up=middle-1;else//Returnindexoffounditemreturnmiddle;}returnNOT_IN;}}程式一_Level_05：importDataStructures.Comparable;importDataStructures.MyInteger;publicclassFig02_09{publicstaticfinalintNOT_IN=-1;publicstaticfinalintZERO_FLAG=0;publicstaticfinalintNUM_ITEMS=8;//ProgramtotestBinarySearchpublicstaticvoidmain(String[]args){searchResults();61 }publicstaticvoidsearchResults(){intj=ZERO_FLAG;while(jZERO_FLAG)up=middle-1;else//Returnindexoffounditemreturnmiddle;}returnNOT_IN;}61 }程式一-Level_06：importDataStructures.Comparable;importDataStructures.MyInteger;publicclassFig02_09{publicstaticfinalintNOT_IN=-1;publicstaticfinalintZERO_FLAG=0;publicstaticfinalintNUM_ITEMS=8;//ProgramtotestBinarySearchpublicstaticvoidmain(String[]args){searchResults();}publicstaticvoidsearchResults(){intj=ZERO_FLAG;while(jZERO_FLAG)up=middle-1;elseif(inArray[middle].compareTo(toFind)