SQL-Detector：基于編碼特征的SQL習題抄襲檢測技術

許 嘉，莫曉琨，于 戈，呂 品+，韋婷婷

1.廣西大學 計算機與電子信息學院，南寧 530004

2.廣西大學 廣西多媒體通信網(wǎng)絡技術重點實驗室，南寧 530004

3.廣西大學 廣西高校并行與分布式計算重點實驗室，南寧 530004

4.東北大學 計算機科學與工程學院，沈陽 110819

數(shù)據(jù)庫技術一直以來都是計算機學科的核心主干課程，熟練掌握結構化查詢語言（structured query language，SQL）是數(shù)據(jù)庫技術教學中的重要目標。與其他編程語言一樣，掌握SQL 的關鍵在于進行大量編碼實踐。然而，大量教學實踐表明學生在完成SQL 編程習題時普遍存在抄襲現(xiàn)象，從而影響了教師對其學習效果的評估準確性，不利于提高教學質(zhì)量。因此，研發(fā)面向SQL 習題的抄襲檢測技術，從而能從學生提交的大規(guī)模SQL 代碼中檢測到潛在的抄襲代碼是現(xiàn)代計算機教育亟待解決的問題。

雖然研究人員針對Java、C、Python 等編程語言提出了代碼抄襲檢測技術，鑒于SQL 擁有許多區(qū)別于其他編程語言的性質(zhì)，這些技術在解決面向SQL習題的代碼抄襲檢測問題時存在局限性。近年來，一些研究人員提出了專門針對SQL 習題的代碼抄襲檢測技術，可分為兩類：基于字符串匹配的技術和基于編碼特征匹配的技術。然而，現(xiàn)有技術仍存在不足。首先，基于字符串匹配的抄襲檢測技術忽略了SQL 的特性，僅僅通過將某學生答案與其他學生的答案進行字符串相似性匹配來實現(xiàn)抄襲檢測，忽略了學生在編碼特征方面的差異，導致誤判率較高。其次，當前的基于編碼特征匹配的抄襲檢測技術雖然利用了學生的SQL 編碼特征來辨識抄襲行為，然而其一方面僅通過比較學生自身的編碼特征變化來判定抄襲行為，沒有對同一道SQL 習題下全體學生的編碼特征進行相似性分析，另一方面其所考慮的編碼特征過于簡單（只考慮學生編碼的關鍵字大小寫書寫特征、前后的換行特征和注釋特征），沒能充分利用SQL 的豐富編碼特征（例如習題SCHEMA特征和習題函數(shù)特征）來提高檢測精確度。鑒于現(xiàn)有研究工作存在不足，本文提出基于編碼特征的SQL 習題抄襲檢測技術，命名為SQL-Detector。SQLDetector 首先基于SQL 特性分別提取學生的習題編碼特征和泛化編碼特征；其次，以某道SQL 習題下全體學生的習題編碼特征為輸入進行聚類分析從而識別抄襲群體，最后通過比較抄襲群體中每名學生待檢測SQL 代碼的泛化編碼特征和其歷史泛化編碼特征之間的相似性來判定抄襲行為中的抄襲者與被抄襲者。綜上，本文主要貢獻如下：

（1）從SQL 的特性出發(fā)，提出了面向特定SQL 習題的學生習題編碼特征和面向編碼習慣的學生泛化編碼特征。基于這些編碼特征能夠?qū)崿F(xiàn)對學生的畫像。

（2）提出了基于編碼特征的SQL 習題抄襲檢測技術SQL-Detector。該技術首先通過對某道SQL 習題下所有學生的習題編碼特征進行聚類分析從而識別出抄襲群體；其次通過比較抄襲群體中每名學生待檢測SQL 代碼的泛化編碼特征和其歷史泛化編碼特征（即學生畫像）之間的相似性來判定抄襲行為中的抄襲者和被抄襲者。

（3）組織廣西大學計算機專業(yè)的284 名本科生于自主研發(fā)的SQL 在線答題系統(tǒng)中完成SQL 習題并收集學生們的SQL 代碼作為實驗測評數(shù)據(jù)集。實驗結果表明，SQL-Detector 技術比相關最好的技術在抄襲檢測精確度方面平均提高了14.0%。

1 相關工作

為了有效解決代碼抄襲檢測問題，研究人員提出了許多相關技術，這些技術大多面向Java、C、Python 等編程語言，可分為以下四類。

（1）詞頻統(tǒng)計

早在1977 年，Halstead 就提出了軟件科學度量理論，該理論從操作符種類數(shù)量和操作數(shù)種類數(shù)量等屬性定義軟件代碼，并以此構建代碼的特征向量，繼而可以通過計算兩段代碼的特征向量間的編輯距離判定它們是否存在抄襲現(xiàn)象。之后，Sposato 等人提出可以基于聲明語句數(shù)量、函數(shù)數(shù)量、調(diào)用語句、結構化語句塊（ifwhilefor）數(shù)量等屬性來優(yōu)化對代碼特征向量的定義。Grier 則在Halstead 的研究基礎上加入了代碼有效行數(shù)、變量聲明、控制語句數(shù)量等屬性，構成了包含20 個屬性的代碼特征向量。

（2）字符串匹配

基于字符串的代碼抄襲檢測技術先對代碼進行語義分析以便生成代碼的標記令牌（token），然后使用字符串匹配算法（例如最長公共子序列法和最長公共子串法）度量代碼的標記令牌間的相似度，從而發(fā)現(xiàn)抄襲現(xiàn)象?，F(xiàn)有的代碼抄襲檢測系統(tǒng)多是基于字符串匹配的思路實現(xiàn)的，例如：卡爾斯魯厄理工大學研發(fā)的JPlag系統(tǒng)、斯坦福大學研發(fā)的Moss系統(tǒng)和悉尼大學研發(fā)的YAP 系統(tǒng)。

近年來，Danpin 在經(jīng)典的winnowing 算法的基礎上提出了simhash 算法，能夠挖掘出八種學生常見代碼抄襲手段以提高代碼抄襲檢測的精確度。王穎則基于貪婪字符串平鋪的方法對學生提交的編碼答案進行抄襲檢測。

（3）語法樹匹配

基于語法樹匹配的方法首先將代碼轉(zhuǎn)換為其抽象語法樹結構（abstract syntax tree，AST），再通過各個代碼的語法樹間的匹配來完成代碼抄襲檢測。例如，Kim 等人基于在抽象語法樹中尋找相似子樹的方法計算語法樹間的相似度，從而判斷是否存在抄襲。Jiang 等人則定義了抽象語法樹的九維特征向量以實現(xiàn)對抽象語法樹的表示，并使用LSH 算法度量特征向量間的相似性。

（4）編碼特征匹配

Arabyarmohamady 等人提出了一個基于代碼風格的C 語言代碼剽竊檢測框架，通過檢測該生的代碼風格變化和與其他同學代碼風格的相似性實現(xiàn)代碼抄襲檢測。Ljubovic 等人設計提出了一種基于云的集成開發(fā)工具，該工具可以提取出學生編碼過程中的動態(tài)編碼特征，包括代碼添加行數(shù)、代碼刪除行數(shù)和平均粘貼長度等，最終通過神經(jīng)網(wǎng)絡實現(xiàn)了代碼抄襲檢測。

相較于面向其他編程語言的代碼抄襲檢測技術，面向SQL 代碼的抄襲檢測技術較少，現(xiàn)有研究工作或是利用字符串匹配的方法或是利用編碼特征匹配的方法實現(xiàn)對SQL 代碼的抄襲檢測。

（1）基于字符串匹配的SQL 習題抄襲檢測技術

Scerbakov 等人通過對SQL 代碼進行分詞并計算SQL代碼間的編輯距離來判定兩份作業(yè)為抄襲作業(yè)。Russell 等人提出了面向SQL 習題抄襲檢測的Equal算法。Equal算法根據(jù)SQL 代碼字符串間的相似度返回4 到10 之間的分數(shù)，10 分代表兩個SQL 代碼完全匹配，4 分代表在忽略了大小寫、不必要空格和括號等信息后兩個SQL 代碼完全匹配?；谪澙肥阶址ヅ涞腏Plag 系統(tǒng)是廣泛被使用的代碼抄襲檢測系統(tǒng)。JPlag 系統(tǒng)雖然無法直接用于SQL 習題的抄襲檢測，然而允許開發(fā)人員添加SQL 解析器對其進行擴充以實現(xiàn)對SQL 習題的抄襲檢測。

基于字符串匹配的SQL 習題抄襲檢測技術的關注點在于SQL 代碼中的單詞是否相同。當習題的SQL 答案簡單或習題不具有多個等價答案時，該類技術的誤判率較高，無法利用學生編碼特征來識別學生提交的SQL 代碼間的差異。

（2）基于編碼特征匹配的SQL習題抄襲檢測技術

葛文馨等人在2019 年提出了一種基于學生編碼習慣的SQL 習題抄襲檢測算法。該算法首先對學生歷史提交的SQL 代碼進行預處理；其次以預處理后的學生歷史提交的SQL 代碼為輸入來訓練樸素貝葉斯分類器，以便對學生新提交的SQL 代碼進行代碼功能類別判定（功能類別包括SQL 的數(shù)據(jù)查詢功能、數(shù)據(jù)操縱功能以及數(shù)據(jù)控制功能等）；之后對同一類別的SQL 代碼提取能反映出學生編碼習慣的特征矩陣，文獻中考慮的編碼習慣包括學生的關鍵字大小寫習慣、代碼換行習慣和代碼注釋習慣；最后基于學生新提交的SQL 代碼的特征矩陣和其歷史提交的SQL 代碼的特征矩陣間的Jaccard 相似度來判定學生新提交的SQL 代碼是否存在抄襲行為：與歷史不相似則判定為抄襲，反之則判定為非抄襲。

相關研究的實驗表明，由于考慮了學生在編碼過程中呈現(xiàn)出的獨特編碼習慣，基于編碼特征匹配的SQL 習題抄襲檢測技術能夠降低抄襲檢測的誤判率，是當前用于解決SQL 習題抄襲檢測問題的主流方法。然而該類方法的現(xiàn)有研究工作：（1）僅通過比較學生自身的編碼特征變化來判定抄襲行為，忽略了對學生間編碼特征的相似性分析；（2）考慮的編碼特征過于簡單，從而制約了其抄襲檢測的精確度。

2 SQL-Detector技術實現(xiàn)框架

針對現(xiàn)有SQL習題抄襲檢測技術的不足，本文提出了一種基于編碼特征的SQL習題抄襲檢測技術，即SQL-Detector技術。該技術的實現(xiàn)框架如圖1 所示。

圖1 SQL-Detector技術實現(xiàn)框架Fig.1 Implementation framework of SQL-Detector technique

如圖1所示，SQL-Detector技術包含四個重要模塊：

（1）編碼特征提取模塊。該模塊以學生提交的SQL 代碼為輸入分別提取學生的習題編碼特征和泛化編碼特征。其中，學生習題編碼特征為學生針對某道SQL 習題給出的SQL 代碼所反映出的編碼特征，與該SQL 習題的特性緊密相關，學生習題編碼特征用于發(fā)現(xiàn)該習題的抄襲群體。學生泛化編碼特征則反映了學生在編寫SQL 代碼時所展現(xiàn)出的泛化性編碼習慣，用于對學生的SQL 編碼習慣進行畫像。

（2）基于習題編碼特征的抄襲群體檢測模塊。該模塊以經(jīng)過標準化處理后的所有學生的習題編碼特征（表示為學生的習題編碼特征集合）為輸入，之后通過層次聚類算法對學生的習題編碼特征集合進行聚類分析，以檢測出抄襲群體。

（3）基于泛化編碼特征的學生畫像匹配模塊。該模塊將學生當前提交的SQL 代碼的泛化編碼特征與該生的歷史泛化編碼特征（即該生的畫像）進行相似性匹配：若相似則認為該生當前提交的SQL代碼為本人撰寫，繼而使用該生當前提交的SQL代碼的泛化編碼特征對該生的歷史泛化編碼特征進行更新；反之則認為該生當前提交的SQL代碼可能存在抄襲行為。

（4）抄襲檢測模塊。該模塊以“基于習題編碼特征的抄襲群體檢測模塊”輸出的抄襲群體和“基于泛化編碼特征學生畫像匹配模塊”輸出的匹配結果為輸入對學生的抄襲行為進行識別。對于存在于某抄襲群體中的學生：若該生當前提交的SQL 代碼的泛化編碼特征與其歷史畫像間的相似度不大于某閾值，則將該生判定為抄襲者；反之，若該生的泛化編碼特征與其歷史畫像間的相似度大于該閾值，則將該生判定為被抄襲者。

3 基于編碼特征的抄襲檢測技術

本章將詳細介紹SQL-Detector 技術的各個功能模塊的實現(xiàn)思路。

3.1 編碼特征提取模塊

學生在SQL 編碼過程中會展現(xiàn)出不同的編碼特征。表1 列出了針對同一道SQL 習題，即“查詢Geology 學院所修學分總數(shù)超過50 的學生信息”，學生A、學生B 和學生C 所給出的SQL 代碼。不難發(fā)現(xiàn)，這三名學生給出的SQL 代碼雖然實質(zhì)上是一樣的，但是在關鍵字大小寫、代碼縮進和換行這三方面因編碼習慣不同而存在差異。例如，在關鍵字大小寫書寫習慣方面，學生A 習慣采用全小寫的方式書寫關鍵字，學生C 習慣采用全大寫的方式書寫關鍵字，學生B 則習慣采用首字母大寫的方式書寫關鍵字。此外，三名學生還在代碼換行和縮進方面呈現(xiàn)出不同的習慣。可見，編碼特征能有效刻畫學生個體間的差異，有助于辨識出學生的抄襲行為。為了有效識別抄襲行為，本文提取的編碼特征包括兩類，即學生習題編碼特征和學生泛化編碼特征。其中，學生習題編碼特征反映出學生針對習題所給出的SQL 代碼的編碼特性，與特定習題緊密相關。學生泛化編碼特征則反映出學生編寫SQL 代碼的泛化編碼習慣，不與特定習題綁定。

表1 學生存在不同的SQL 編碼特征Table 1 Students show different SQL coding features

通過分析SQL 的語法、句法特性，總結得到八類與特定SQL 習題相關的學生習題編碼特征，分別是：

（1）習題SQL 關鍵字特征。SQL 關鍵字是SQL標準中指定的具有特殊含義的單詞，例如SELECT、FROM、WHERE 都是SQL 關鍵字。SQL 規(guī)范中 對SQL 關鍵字的大小寫不做書寫規(guī)定。因而，不同學生在書寫SQL 關鍵字時會呈現(xiàn)出不同的關鍵字書寫習慣。學生的SQL 關鍵字書寫習慣是可以幫助識別學生個體的SQL 編碼特征。某學生的習題關鍵字特征是基于其提交的SQL 代碼的每個子句定義的：當子句中以全小寫的方式書寫關鍵字時，設置為1；當子句中以全大寫的方式書寫關鍵字時，設置為2；其他方式設置為3。

（2）習題SCHEMA 特征。SCHEMA 是數(shù)據(jù)庫的組織和結構，包含表（table）、列（column）和視圖（view）等數(shù)據(jù)庫對象。首先將SQL 代碼涉及的SCHEMA 信息整合為SCHEMA 字典。某學生的習題SCHEMA 特征是基于其提交的SQL 代碼的每個子句定義的：若子句中出現(xiàn)的SCHEMA 信息不在SCHEMA 字典中，表明學生書寫的SCHEMA 信息存在錯誤，此時將該生的習題SCHEMA 特征定義為錯誤SCHEMA 信息與SCHEMA 字典中與其最相似的元素間的編輯距離乘以該元素的字典序；否則，表明學生寫對了相關SCHEMA信息，則將其習題SCHEMA特征定義為SCHEMA 信息在SCHEMA 字典中的字典序與SCHEMA 信息在子句中的位置之間的乘積。

（3）習題函數(shù)特征。SQL 規(guī)范中規(guī)定了一系列用于完成特定計算的內(nèi)建函數(shù)，基本類型包括Aggregate 函數(shù)和Scalar 函數(shù)。其中，Aggregate 函數(shù)包括AVG、COUNT、MAX 等；Scalar 函數(shù)包括NOW、LEN 和MID 等。將SQL 規(guī)范中定義的內(nèi)建函數(shù)整合為函數(shù)字典。某學生的習題函數(shù)特征定義為其SQL代碼的每個子句中所引用的函數(shù)在函數(shù)字典中的字典序與函數(shù)在子句中的位置間的乘積。

（4）習題關系運算符特征。SQL 的WHERE 子句和JOIN 子句中可能存在著一些對關系的判定。對于某個具體的關系判定，學生可能運用不同的關系運算符和關鍵字給出等價的寫法。例如A＞10 與NOT(A＜=10)在判定語義上是等價的。根據(jù)SQL 規(guī)范中給出的關系運算符和關鍵字生成關系運算符字典。某學生的習題關系運算符特征定義為其SQL 代碼的每個子句中關系運算符在關系運算符字典中的字典序與關系運算符在子句中的位置之間的乘積。

（5）習題括號特征。括號是SQL 中的合法符號，學生編寫SQL 代碼時對括號的使用習慣存在差異，體現(xiàn)在當括號不是必需前提下，有些學生習慣于使用括號，有些學生則放棄使用括號。某學生的習題括號特征定義為其SQL 代碼的每個子句中的每個括號在子句中的位置之和。

（6）習題空格特征。空格在SQL 中被用于分隔詞與詞。由于空格不存在語義，SQL 語法對空格的數(shù)量和位置沒有固定要求。因而，學生在編寫SQL時對空格的使用習慣存在差異。體現(xiàn)在不同學生可能會在不同的地方使用不同數(shù)量的空格，例如利用空格來調(diào)整SQL代碼的整體格式。某學生的習題空格特征定義為其SQL代碼的每個子句中所有連續(xù)空格符序列的基數(shù)與連續(xù)空格符序列起始位置的乘積之和。

（7）習題縮進特征。SQL 支持編輯時使用縮進符調(diào)整一行的起始字母與頁面邊界之間的距離。SQL 中對縮進符的使用習慣因人而異，因而也可作為辨識學生的編碼特征。例如，一些學生在編寫SQL 時習慣將多個條件判斷語句分行列出，并通過縮進符將這些條件判斷語句對齊（如表1 的學生C 的代碼所示）。某學生的習題縮進特征定義為其SQL代碼的每個子句中所有連續(xù)縮進符序列的基數(shù)與連續(xù)空格符序列起始位置的乘積之和。

（8）習題換行特征。當查詢語義較為復雜時，反映該查詢語義的SQL 代碼的篇幅將大幅增加，此時若不對SQL 代碼進行斷句處理則會降低SQL 代碼的可讀性。因此，SQL 編寫人員會使用換行符將SQL代碼基于其語義結構分割為若干行。由于換行符的使用位置不影響SQL 語句的執(zhí)行結果，換行符的使用習慣也因人而異。某學生的習題換行特征定義為其SQL代碼的每個子句中各個換行符的所在位置之和。

為保證所提取的學生習題編碼特征對于區(qū)分學生個體具有細粒度的辨識度，先對學生提交的SQL代碼進行子句劃分，然后以子句為單位提取學生的習題編碼特征，最后將學生提交的SQL 代碼中所有子句的編碼特征拼接形成該生的習題編碼特征向量。需要說明的是：首先，對于學生SQL 代碼中相同類型的子句出現(xiàn)多次的情況，將同類型子句的編碼特征進行累加；其次，當SQL 代碼不存在某種類型的子句時，其編碼特征向量中與該子句類型對應的所有取值位置全部設置為0。七類SQL 子句與其能提取的習題編碼特征之間的對應關系詳見表2。

表2 子句類型與習題編碼特征之間的關系Table 2 Relationships between clause types and exercise coding features

綜上，一個學生習題編碼特征向量是一個48 維的整型向量。具體而言，向量的第1～7 維記錄了SELECT 子句中出現(xiàn)的七類習題編碼特征（如表2 所示）；第8～13 維記錄了FROM 子句中出現(xiàn)的六類習題編碼特征；第14～20 維記錄了WHERE 子句中出現(xiàn)的七類習題編碼特征；第21～27 維記錄了JOIN 子句中出現(xiàn)的七類習題編碼特征；第28～34維記錄了GROUP BY 子句中出現(xiàn)的七類習題編碼特征；第35～42 維記錄了HAVING 子句中出現(xiàn)的八類習題編碼特征；第43～48 維記錄了ORDER BY 子句中出現(xiàn)的六類習題編碼特征。

與學生習題編碼特征不同，學生泛化編碼特征是對學生在不同的SQL 習題中都將呈現(xiàn)出的編碼習慣（即泛化編碼習慣）的刻畫，用于對學生的SQL 編碼習慣進行畫像。學生泛化編碼特征包括以下六類，它們是：

（1）泛化關鍵字特征。與習題關鍵字特征不同，泛化關鍵字特征只記錄了學生在各個SQL 子句中針對主關鍵字的大小寫書寫特征，而非針對所有關鍵字的大小寫書寫特征。首要關鍵字與SQL 子句的類型相關，例如SELECT 子句的主關鍵字是“SELECT”、FROM 子句的主關鍵字是“FROM”。學生泛化關鍵字特征的賦值規(guī)則為：當以全小寫的方式書寫子句的主關鍵字時，設置為1；當以全大寫的方式書寫子句的主關鍵字時，設置為2；其他方式設置為3。

（2）泛化括號特征。與習題括號特征不同，泛化括號特征只記錄學生在各類SQL 子句中是否使用了括號，而并不需要記錄括號在子句中出現(xiàn)的具體位置。

（3）泛化換行特征。與習題換行特征不同，泛化換行特征只記錄學生在各類SQL 子句中是否會對子句進行換行處理，而非記錄換行符在子句中的具體位置。

（4）泛化空格特征。與習題空格特征不同，泛化空格特征只記錄學生在各類SQL 子句中是否存在連續(xù)使用多于兩個空格的情況，而不記錄學生使用空格的具體位置與數(shù)量。

（5）泛化縮進特征。與習題縮進特征不同，泛化縮進特征只記錄學生在各類SQL 子句中是否在子句中使用縮進符，而不會記錄縮進符在子句中的具體位置。

（6）字段名修飾特征。字段名修飾特征記錄了學生在完成單表查詢?nèi)蝿盏腟ELECT 子句中是否使用了表名對字段進行修飾（即使用table.column 的模式對字段進行引用）。由于是否加表名對字段進行修飾并不影響單表查詢的查詢結果，學生的字段名修飾特征能反映出學生的編碼習慣。

綜上，包含以上6 類泛化編碼特征的學生泛化編碼向量是一個36 維的整型向量。具體而言，向量的第1～7 維記錄了學生對七類SQL 子句（詳見表2）的主關鍵字的大小寫書寫習慣；第8～14 維記錄了學生在七類SQL 子句中是否使用了括號；第15～21 維記錄了學生在七類SQL 子句中是否使用了換行符；第22～28 維記錄了學生在七類SQL 子句中是否連續(xù)使用了多個空格符；第29～35 維記錄了學生在七類SQL 子句中是否使用了縮進符；第36 維記錄了學生在單表查詢的SELECT 子句中是否使用表名對字段進行修飾。

3.2 基于習題編碼特征的抄襲群體檢測模塊

基于習題編碼特征的抄襲群體檢測模塊以某道SQL 習題對應的所有學生的習題編碼特征向量為輸入，并利用層次聚類的方法得到抄襲群體。由于學生習題編碼特征向量的各個維度間存在量綱不一致的問題，使用Z-score 標準化方法對學生習題編碼特征向量的各個維度進行了歸一化處理，以降低因量綱差異所導致的計算誤差。以歸一化后的所有學生習題編碼特征向量為輸入，并以歐式距離作為向量間的相似性度量函數(shù)，最終利用凝聚式層次聚類算法得到抄襲群體：若一個聚類簇中包含多個學生，則判定該聚類簇中的學生為一個抄襲群體。

3.3 基于泛化編碼特征的學生畫像匹配模塊

基于泛化編碼特征的學生畫像匹配模塊以某學生待檢測SQL 代碼的習題泛化編碼特征向量為輸入，通過比較該向量與基于該生歷史提交的SQL 代碼計算得到歷史泛化編碼特征向量（即學生畫像）之間的相似度來判定該生是否抄襲別人的代碼。若相似度高則表明該生的泛化編碼習慣與其歷史編碼習慣一致，因而認為待檢測SQL 代碼為該生本人撰寫，并使用該生待檢測SQL 代碼的泛化編碼特征向量對該生畫像進行更新；反之則表明該生的泛化編碼習慣與其歷史編碼習慣呈現(xiàn)出較大差異，此時判定待檢測SQL 代碼非該生本人撰寫，并將該結果報送給抄襲檢測模塊。學生歷史泛化編碼特征向量中每維的取值是該生歷史提交的多個SQL 代碼的泛化編碼特征向量中相應維度取值的加權和。具體而言，學生的歷史泛化編碼特征向量中第維（表示為hgf[]）的計算方法如式（1）所示。

其中，L表示基于歷史上該生提交的多個SQL 代碼的泛化編碼特征向量統(tǒng)計得到的向量在第維的獨特取值個數(shù)；v表示第維的第個獨特取值；p則表示第維的第個獨特取值在該維度上的取值占比。

3.4 抄襲檢測模塊

該模塊以“基于習題編碼特征的抄襲群體檢測模塊”輸出的抄襲群體和“基于泛化編碼特征學生畫像匹配模塊”輸出相似性比較結果為輸入，目的是為了區(qū)分抄襲群體中的抄襲者和被抄襲者。若抄襲群體中某學生的習題泛化編碼特征向量與該生的歷史泛化編碼特征向量之間相似度低，則將該生判定為抄襲者；反之，則將該生判定為被抄襲者。

基于編碼特征的SQL 抄襲檢測算法的偽代碼詳見算法1 所示。該算法以學生針對某SQL 習題所提交的SQL 代碼集合和所有學生的歷史泛化編碼特征向量集合為輸入，輸出針對該SQL 習題的抄襲檢測結果集合。其中，中的每個元素為二元組形式＜Q,R＞：Q表示第個學生針對該習題所提交的SQL 代碼，R則為此SQL 代碼的抄襲指示標記（R=copier 表示該生為抄襲者；R=giver 表示該生為被抄襲者）。算法首先遍歷中的每個學生提交的SQL代碼（行2），提取出針對待檢測習題的每個學生的習題編碼特征向量（行3）、泛化編碼特征向量（行5），并對所有學生的習題編碼特征向量進行歸一化處理（行4）。其次，利用層次聚類方法對歸一化后的所有學生的習題編碼特征向量進行聚類分析，從而得到聚類簇集合（行6）。之后，遍歷中的每一個簇，當簇內(nèi)包含多個學生時，將該簇加入抄襲群體集合中（行8～10）。對于每個抄襲群體中的學生（行11～12），首先讀取該生的歷史泛化編碼特征（行13）和針對當前待檢測習題的習題編碼特征（行14），再使用歐氏距離計算該生的習題泛化編碼特征ef與其歷史泛化編碼特征hgf之間的相似度（行15）。若相似度不大于閾值，則判定該生為抄襲者，并將檢測結果添加至抄襲檢測結果集中（行16～17）；若相似度大于閾值，則判定該生為被抄襲者，將檢測結果添加至的同時使用gf更新該生的歷史泛化編碼特征（行18～20）。最后，算法返回抄襲檢測結果集（行21）。

基于編碼特征的SQL 習題抄襲檢測算法

輸入：待檢測學生SQL 代碼集合，學生歷史泛化編碼特征向量集合。

輸出：抄襲檢測結果集={＜Q,R＞}。

下面對算法1 的時空復雜度進行分析。該算法的主要計算代價在于對所有學生的習題編碼特征進行層次聚類，因此算法時間復雜度等于所采用的層次聚類算法的時間復雜度。層次聚類是數(shù)據(jù)挖掘的重要研究內(nèi)容之一，擁有很多實現(xiàn)策略。本文采用Ward Linkage 方法實現(xiàn)聚類。Ward Linkage 方法（又稱離差平方和法）是凝聚式層次聚類方法的典型代表。在SQL 代碼抄襲檢測場景中運用Ward Linkage 方法對SQL 代碼進行聚類分析相較于傳統(tǒng)的-均值聚類方法更具優(yōu)勢：（1）Ward Linkage 方法不需要指定聚類數(shù)目的值，因此聚類結果質(zhì)量對值依賴性不強，且能產(chǎn)生高質(zhì)量的聚類結果；（2）Ward Linkage 方法的聚類結果較-均值聚類更具可解釋度，因此能更好地解釋抄襲群體和非抄襲群體之間的編碼特征差異。對于算法1，運用Ward Linkage 方法實施對學生習題編碼特征進行層次聚類的時間復雜度為(||)，其中||是待檢測學生答案集合的基數(shù)。易知，算法1 的空間存儲開銷主要來自于層次聚類過程中對鄰近度矩陣的存儲，鄰近度矩陣存放的是層次聚類中每個簇間的距離，故算法的空間復雜度為(||)。與本文最相關的研究工作（即文獻[4]）提出的SQL 代碼抄襲檢測技術的時間復雜度為計算SQL 代碼兩兩間相似度的開銷，即(||)。文獻[4]的空間復雜度由待檢測SQL 代碼集合的關鍵字詞頻矩陣大小決定，為(||)，其中為SQL 關鍵字的基數(shù)。可見，本文提出的SQL-Detector 技術與文獻[4]技術的時間復雜度相同。雖然SQL-Detector 技術的空間復雜度一般高于文獻[4]技術，但因為SQLDetector 技術一方面利用同一道SQL 習題下全體學生的編碼特征的相似性分析來提高抄襲檢測的精度，另一方面考慮了更豐富的SQL 編碼特征，因此其在SQL 代碼抄襲檢測精度方面比文獻[4]技術有顯著提升（詳見第4 章）。

4 實驗評價

4.1 實驗設置

為了驗證基于編碼特征的SQL 習題抄襲檢測技術SQL-Detector 的有效性，本節(jié)對SQL-Detector 技術與相關技術的抄襲檢測精度進行了實驗評價。實驗中參與比較的相關技術包括文獻[4]提出的SQL 習題的抄襲檢測技術和代碼抄襲檢測領域所用的經(jīng)典技術JPlag。其中，文獻[4]的技術通過提取學生SQL代碼的部分編碼特征（即學生的關鍵字大小寫習慣和換行習慣）來生成特征矩陣，繼而通過比較當前代碼的特征矩陣與該生歷史特征矩陣間的Jaccard 相似度來判定代碼是否存在抄襲行為。JPlag 技術則首先將需要比對的兩組SQL 代碼解析為Token 集合，然后基于貪婪式字符串匹配算法計算兩組Token 集合間的相似度，從而發(fā)現(xiàn)代碼間的抄襲行為。實驗中設定文獻[4]技術所依賴的相似度閾值為文獻[4]給出的最優(yōu)閾值，即0.5；設定JPlag 技術的相似度閾值為文獻[4]中給出的最優(yōu)閾值，即0.7。實驗中基于Java 語言實現(xiàn)本文提出的SQL-Detector 技術以及本文對比的文獻[4]技術、JPlag 技術。實驗所用計算機服務器的配置為：Intel Core i5-8500 3.0 GHz（4-Core）CPU、8 GB內(nèi)存、1 TB硬盤、64位Windows 10操作系統(tǒng)。

組織廣西大學計算機專業(yè)的284 名本科生于自主研發(fā)的SQL 在線答題系統(tǒng)中完成12 道SQL 習題并收集學生們的SQL 代碼作為實驗數(shù)據(jù)集，實驗數(shù)據(jù)集的詳細信息如表3 所示。為了評估不同技術對于學生提交的SQL 代碼的抄襲檢測精確度，邀請兩名具有8 年以上SQL 教學經(jīng)驗的教師對數(shù)據(jù)集中的學生SQL 代碼是否存在抄襲行為進行標注：存在抄襲行為標記為1，反之則標記為0。

表3 實驗數(shù)據(jù)集詳細信息Table 3 Details of experimental dataset

4.2 評價指標

為了便于與其他技術進行比較，仿造其他技術的輸出結果，實驗中將SQL-Detector 技術檢測為‘copier’或‘giver’的SQL 代碼都標記為1（即涉及抄襲行為）。實驗評價指標包括查準率、查全率和1值。

查準率（）表示預測為正的樣例占真實正樣例的比率，其計算方法如式（2）所示：

其中，、、和分別表示真正例（true positive）、假正例（false positive）、真反例（true negative）和假反例（false negative），且樣例總數(shù)（即后文中的Total）為以上四種樣例的數(shù)目之和。

查全率（）表示正例被正確預測的比率，其計算方法如式（3）所示：

1 值則同時兼顧了查準率和查全率，其計算方法如式（4）所示：

4.3 實驗結果與分析

SQL-Detector 技術中的習題編碼特征聚類模塊是基于Ward Linkage 凝聚式層次聚類方法執(zhí)行對所有學生習題編碼特征向量的聚類分析。相似度閾值的設定影響到聚類結果的質(zhì)量，進而影響到對抄襲檢測群體的識別質(zhì)量。因此，本節(jié)首先對習題編碼特征聚類模塊使用的相似度閾值進行實驗分析。表4 展示了不同相似度閾值下SQL-Detector 技術的抄襲檢測結果的1 值。如表4 所示，隨著相似度閾值增大，1 值呈現(xiàn)出增大的趨勢，這是因為過小的閾值會導致聚類簇的數(shù)量過多，因此不能有效識別習題編碼特征具有較大差異的抄襲行為。當相似度閾值超過0.8 時，1 值則出現(xiàn)了下降趨勢，這是因為過大的閾值會導致聚類簇的數(shù)量過多，從而導致本來具有抄襲現(xiàn)象的代碼沒有被聚為一類，繼而引發(fā)了誤判。后文實驗中將SQL-Detector 技術中聚類所依賴的相似度閾值統(tǒng)一設置為0.8。

表4 層次聚類中相似度閾值對抄襲檢測精度的影響Table 4 Impact of similarity threshold in hierarchical clustering on accuracy of plagiarism detection

表5 展示了對于每道SQL 習題，三種SQL 習題抄襲檢測技術對學生提交的SQL 代碼的抄襲檢測精確度，涉及查準率、查全率、1 值這三項指標。由表5可知，JPlag 技術的1 值最低，對12 道SQL 習題的抄襲檢測結果的1 均值僅為41.8%，這是因為JPlag 技術僅通過比較學生提交的SQL 代碼之間的字符串相似性來發(fā)現(xiàn)抄襲行為，而沒能利用辨識度更高的，能反映SQL 語法、句法特性的學生編碼特征來實現(xiàn)抄襲檢測，最終導致了較高的誤判率。文獻[4]的SQL習題抄襲檢測技術由于利用了SQL 語義下學生的部分編碼特征來辨識抄襲行為，因而對于12 道SQL 習題，文獻[4]技術的抄襲檢測結果的1 均值（即73.0%）比JPlag 技術提高了74.6%。可見，基于編碼特征的SQL 習題抄襲檢測技術比基于字符串匹配的SQL 抄襲檢測技術在抄襲行為辨識力方面更具優(yōu)勢。同時從表5 可觀察到本文提出的SQL-Detector技術針對12 道SQL 習題的查準率、查全率和1 值均優(yōu)于文獻[4]的技術。特別地，SQL-Detector技術針對12 道SQL 習題的1 均值達到了83.2%，相較于文獻[4]技術的檢測結果提高了14.0%。SQL-Detector 技術的優(yōu)勢來自于：（1）從SQL 的語法、句法特性出發(fā)，抽取并利用了比文獻[4]的技術更豐富的學生編碼特征來辨識抄襲行為；（2）不但和文獻[4]一樣通過比較學生待檢測SQL 代碼的編碼特征和該生歷史編碼特征之間的差異來識別抄襲學生，而且通過對待檢測SQL 習題的所有學生的編碼特征進行聚類分析來發(fā)現(xiàn)抄襲群體，即利用同一道SQL 習題下學生SQL 代碼相似性分析來提高抄襲檢測的精確度。可見，從具體編程語言特性出發(fā)來定義編碼特征以及在抄襲檢測流程中同時考慮同一學生的編碼特征的歷史一致性和待檢測習題下不同學生編碼特征之間的相似性是提高面向特定編程語言的代碼抄襲檢測精確度的有效手段。

表5 SQL 習題抄襲檢測精確度分析Table 5 Accuracy analysis of SQL plagiarism detection

5 結束語

面向SQL 習題的抄襲檢測技術能夠自動識別出學生提交的SQL 代碼中的抄襲問題，從而幫助教師在數(shù)據(jù)庫教學中更好地了解學生對SQL 的掌握情況，具有重要現(xiàn)實意義。然而，現(xiàn)有的SQL 習題抄襲檢測技術存在局限性：一方面僅通過比較學生自身的編碼特征變化來判定抄襲行為，忽略了同一道SQL 習題下學生所提交的SQL 代碼在編碼特征方面的相似性；另一方面所考慮的學生編碼特征過于簡單，沒能從SQL 的語法、句法特性出發(fā)提取與利用更多的編碼特征來提高SQL 習題抄襲檢測的精確度。針對現(xiàn)有研究工作的不足，本文提出了一種基于編碼特征的SQL 習題抄襲檢測技術，命名為SQLDetector。該技術從SQL 的特性出發(fā)，提取出面向特定SQL 習題的學生習題編碼特征和面向編碼習慣的學生泛化編碼特征。SQL-Detector 技術首先通過對某道SQL 習題下所有學生的習題編碼特征進行聚類分析從而識別出抄襲群體。其次，通過比較抄襲群體中每名學生待檢測SQL 代碼的泛化編碼特征和其歷史泛化編碼特征（即其歷史畫像）之間的相似性來判定抄襲行為中的抄襲者和被抄襲者?；谟啥鄠€教學班學生參與的教學實踐中收集到的學生提交的SQL 代碼進行實驗評價與分析，結果表明SQLDetector 技術比相關最好的SQL 習題抄襲檢測技術在抄襲檢測精確度方面平均提高了14.0%。

未來將在數(shù)據(jù)庫的教學實踐中繼續(xù)運用SQLDetector 技術幫助教師提高SQL 編程的教學質(zhì)量，并不斷收集和分析學生的抄襲樣例，從而進一步優(yōu)化SQL-Detector技術的抄襲檢測流程。