基于哈希學習的異常SQL檢測

李明威，蔣慶遠*，解銀朋，何金棟，吳 丹

（1.計算機軟件新技術(shù)國家重點實驗室（南京大學），南京 210023；2.國家電網(wǎng)福建省電力有限公司電力科學研究院，福州 350007）

0 引言

近年來，由于互聯(lián)網(wǎng)的高速發(fā)展，網(wǎng)絡(luò)安全面臨著越來越嚴峻的挑戰(zhàn)。作為網(wǎng)絡(luò)安全領(lǐng)域中一種常見的攻擊手段，異常結(jié)構(gòu)化查詢語句（Structure Query Language，SQL）［1］造成了越來越多的網(wǎng)絡(luò)安全問題。異常SQL通過在正常的SQL語句中插入惡意的SQL 語句，使攻擊者完全控制Web 端數(shù)據(jù)庫服務(wù)器。攻擊者可以在惡意SQL中插入漏洞程序來繞過應(yīng)用程序的安全措施，也可以通過惡意SQL語句來修改、刪除數(shù)據(jù)庫服務(wù)器中的記錄。因此，異常SQL 可能影響到Web 端應(yīng)用程序和數(shù)據(jù)庫服務(wù)器，用戶的數(shù)據(jù)可能因此受損。

為了解決異常SQL 帶來的問題，越來越多的研究者關(guān)注了異常SQL 問題，同時提出了很多異常SQL 檢測方法［2-3］。早期的異常SQL檢測方法［4］可以劃分為統(tǒng)計分析方法［5］、動態(tài)分析方法［6］和參數(shù)過濾方法［7］。統(tǒng)計分析方法［5］通過探測輸入SQL 語句中的詞法錯誤、語法錯誤來完成異常SQL 檢測。動態(tài)分析方法［6］通過分析SQL 執(zhí)行結(jié)果是否為惡意結(jié)果來判斷SQL 是否為注入攻擊語句。參數(shù)過濾方法［7］基于正則表達式和黑名單來過濾無效字符。上述方法通過分析SQL語句的詞法、語法、結(jié)構(gòu)等來發(fā)現(xiàn)異常SQL攻擊。

近年來，研究者們提出了一些基于機器學習技術(shù)的異常SQL 檢測方法［8-16］。例如：文獻［9］首先使用N-gram 模型抽取SQL 語句的特征，然后使用支持向量機（Support Vector Machine，SVM）來進行分類；文獻［10］設(shè)計了一種爬蟲工具來自動掃描異常SQL 攻擊，并使用機器學習技術(shù)來自動探測攻擊；文獻［11］提出了一種基于長短期記憶（Long Short Term Memory，LSTM）網(wǎng)絡(luò)的深度神經(jīng)網(wǎng)絡(luò)方法來完成異常SQL 檢測任務(wù)；文獻［12］提出了使用SVM、樸素貝葉斯（Na?ve-Bayes）、最近鄰（Nearest Neighbor，NN）來完成異常SQL 檢測任務(wù)。在現(xiàn)有的方法中，最近鄰方法能取得了很高的準確率；同時，最近鄰方法具有良好的可解釋性。然而，隨著數(shù)據(jù)量的大幅增長，最近鄰方法的性能受到了極大的限制：一方面，數(shù)據(jù)量太大時，存儲開銷通常很大；另一方面，在海量數(shù)據(jù)中進行檢索的性能也會隨著數(shù)據(jù)量的變大而變差。

本文提出一種基于哈希學習［17-20］的異常SQL 檢測（Hash learning based Malicious SQL Detection，HMSD）方法。本文的貢獻如下：

1）首次使用哈希學習方法來完成異常SQL 檢測任務(wù)。通過使用哈希學習方法，將SQL 語句表示成緊湊的二值哈希碼形式，解決了使用最近鄰進行異常SQL檢測時遇到的問題。

2）在一個異常SQL 檢測數(shù)據(jù)集上的實驗證明了，與已有的基于最近鄰的異常SQL 檢測方法相比，HMSD 能取得更好的檢測精度，提高檢索速度，并顯著降低存儲和計算開銷。

1 符號與問題定義

1.1 符號

本節(jié)介紹了本文中一些約定的符號表示。具體來說，本文使用大寫黑體字母，例如W表示矩陣，使用小寫黑體字母，例如w表示向量。使用Wij表示矩陣W中行標為i、列標為j的元素，使用Wi*和W*j分別表示矩陣W的第i行和第j列。符號tr(W)表示矩陣的跡。符號||W||F表示向量的Frobenius 范數(shù)。表1中給出了本文使用的符號說明。

表1 本文使用的符號Tab.1 Symbols used in the paper

此外，本文使用符號d(·)表示對角矩陣化操作。本文使用s(·)表示逐元素取符號函數(shù)，取符號函數(shù)的定義如下：

1.2 問題定義

對于一個查詢SQL 語句xq，通常通過判斷該SQL 語句是否是異常SQL 語句來完成異常檢測。基于哈希學習的異常SQL 檢測首先將SQL 查詢語句表示為二值編碼bq∈{-1，+1}c，這里c表示二值編碼長度，同時在學習過程中，本文使用-1 和+1 表示二值編碼。學習結(jié)束后，使用編碼0 替換編碼-1，得到使用編碼0和1表示的二值編碼。然后使用該二值編碼，查詢已有的SQL 數(shù)據(jù)庫來判斷該SQL是否為異常SQL語句，這里N表示數(shù)據(jù)庫樣本數(shù)目。

由于SQL 通常是句子的形式，因此需要為每個語句抽取特征。對于SQL 語句xi，本文使用ei∈Rd來表示該語句的特征，這里d表示SQL 語句的特征維度。然后，定義哈希函數(shù)為：h(·)：Rd?{-1，+1}c。為了保證異常SQL 檢測的精度，SQL 語句的二值編碼需要盡可能地保持原空間的相似度，即如果兩個SQL 語句在原始空間中相似，在二值空間中希望這兩個SQL語句也相似；反之，如果兩個SQL語句在原始空間中不相似，在二值空間中希望這兩個SQL語句也不相似。這里，使用海明距離來衡量兩個SQL語句在二值空間中的相似性。

2 基于哈希學習的異常SQL檢測

本章介紹HMSD 方法。整個方法的框架如圖1 所示。本章首先介紹特征提取過程。完成特征提取后，使用哈希學習方法來學習SQL 語句的二值編碼。具體來說，本文使用一種已有的哈希學習方法來學習SQL 語句的二值編碼，即等方差哈希方法［20］（Isotropic Hashing，IsoH）。最后介紹基于二值編碼的異常SQL檢測的流程。

圖1 基于哈希學習的異常SQL檢測框架Fig.1 Framework of Hash learning based malicious SQL detection

2.1 特征提取

對于給定的SQL語句，首先需要根據(jù)SQL語句提取特征。本文使用的特征提取過程包含基于語法分析的清洗過程和特征向量轉(zhuǎn)化過程。

具體來說，對于給定的SQL 語句，使用語法分析技術(shù)，將數(shù)據(jù)表示為語法樹的形式。在實際應(yīng)用場景中，用戶對數(shù)據(jù)庫的查詢可能會產(chǎn)生很多相似的SQL語句，例如，在同一位置插入不同數(shù)據(jù)等操作。因此，SQL 語句中可能存在著大量冗余的語句信息。為了避免冗余信息帶來的額外開銷，可以檢查語法樹中的葉子節(jié)點進行處理：如果葉子節(jié)點上的值是用戶自定義的字符，而非SQL關(guān)鍵字，可以將其替換為“？”；如果是數(shù)字，可以將其替換為“0”。通過這樣的操作，用戶自定義的字符和數(shù)字將被抹除。降低了數(shù)據(jù)的冗余性。如果葉子節(jié)點上的值出現(xiàn)了異常的SQL 關(guān)鍵字，那么將使用其他特殊字符，如“、”等替換以標記該SQL語句。

數(shù)據(jù)清洗過程降低了數(shù)據(jù)的冗余性，并去除了SQL 語句中的錯誤樣本。接下來，使用特征向量轉(zhuǎn)化過程來提取數(shù)據(jù)的特征。本文采用詞袋模型（Bag Of Words，BOW）來對清洗后的數(shù)據(jù)進行向量化，以說明本文的方法。當然也可以使用其他方法，如N-gram 模型或者深度神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)模型來完成向量化操作，但特征轉(zhuǎn)化過程不是本文研究的重點，這里不再贅述。

BOW 模型具有簡單易實現(xiàn)的優(yōu)點。它的基本思想是賦予每個詞一個索引，每個SQL 語句將被表示成為詞數(shù)目長的向量，如果某個詞在SQL語句出現(xiàn)，則該索引值對應(yīng)的位置為該詞在SQL 語句中出現(xiàn)的頻數(shù)，否則為0。給定SQL 語句，通過數(shù)據(jù)清洗和詞袋模型特征提取后，將其特征表示為向量。

2.2 等方差哈希學習

為了將特征投影到二值空間中，首先使用主成分分析（Principal Component Analysis，PCA）方法將數(shù)據(jù)降維到Rc中。具體來說，首先解如下的優(yōu)化問題：

這里，W∈Rd×c表示投影矩陣，并且假設(shè)SQL 語句的特征矩陣已經(jīng)經(jīng)過中心化處理。通過特征分解矩陣ETE，得到的前c個最大特征值對應(yīng)的特征向量即為目標函數(shù)的最優(yōu)解。

通過矩陣W，可將數(shù)據(jù)投影到Rc空間中。該過程表示如下：

這里T (a)定義如下：

這里，向量a表示元素為前c個特征值的平均值組成的c維向量。

定義集合M(Λ)={QTΛQ|QTQ=I}，這里可得等方差哈希的優(yōu)化問題：

使用交替優(yōu)化方法來解上述問題。具體來說，在給定參數(shù)T時，學習參數(shù)Z；反之，當參數(shù)Z給定時，學習參數(shù)T。

當參數(shù)Z固定時，使用如下公式更新參數(shù)T：

這里，k和k+1表示變量的迭代輪次。

假設(shè)當前迭代輪數(shù)為k，當參數(shù)T(k)固定時，首先對參數(shù)T(k)進行特征分解：

然后通過下面的等式得到Z(k)：

適用于異常SQL 檢測的HMSD-IsoH 算法總結(jié)在算法1中。

算法1 HMSD-IsoH模型的優(yōu)化算法。

輸出 投影矩陣W和Q。

對于不屬于訓練集中的樣本，可以使用學習得到的哈希函數(shù)得到其二值編碼表示。

2.3 基于二值編碼的異常SQL檢測

學習得到二值編碼后，給定一個查詢時，首先使用基于二值編碼的查詢過程從海量數(shù)據(jù)庫中得到前K個返回樣本，該過程通常被稱為粗排過程。然后，在返回的樣本集合中，使用基于實值特征的排序得到前k個樣本，這里，k＜K。這個過程通常被稱為精排過程。最后通過投票的方式預測SQL 是否異常。

粗排過程可以采用兩種策略，即海明排序和哈希表查詢。海明排序首先使用基于查詢SQL 語句的二值編碼和數(shù)據(jù)庫SQL 語句的二值編碼之間的海明距離進行排序。根據(jù)排序結(jié)果得到數(shù)據(jù)庫序列。在排序過程中，由于海明距離的計算可以使用位操作來完成，因此計算海明距離能加速檢索過程。完成海明距離的計算后，由于海明距離的離散性，可以設(shè)計O(N)復雜度的排序算法，因此基于海明距離的排序可以進一步加速檢索過程。哈希表查詢首先使用二值編碼將數(shù)據(jù)組織成為倒排表，當?shù)玫讲樵儤颖镜亩稻幋a時，使用哈希表查詢操作來完成檢索過程?；诘古疟淼牟樵冞^程中，如果在以查詢樣本的二值編碼為索引的哈希桶中沒有足夠的樣本，需要擴大海明半徑進行查詢以得到足夠的樣本。理想情況下，哈希表查詢能達到次線性的檢索速度。然而，當需要擴大查詢半徑時，檢索速度將呈指數(shù)級下降。在最差情況下，檢索復雜度將達到O(2c)。

精排過程通常使用實值特征來完成。具體來說，首先根據(jù)查詢SQL 語句的實值特征和包含K個SQL 語句的候選集合的實值特征，計算查詢SQL 語句與候選集中SQL 語句的歐氏距離，然后根據(jù)歐氏距離進行排序，并選取前k個SQL 語句來預測查詢SQL語句是否異常。

基于二值編碼的異常SQL檢測算法總結(jié)在算法2中。

算法2 基于二值編碼的異常SQL檢測算法。

輸入 查詢語句的二值編碼bq和實值特征eq，包含N條SQL語句的數(shù)據(jù)庫的二值編碼B(d)=和實值特征

輸出 查詢語句是否異常。

1）使用海明排序或者哈希表查詢得到前K個候選SQL 語句集合；

2）計算候選集合中K個SQL 語句對應(yīng)的實值特征和SQL 查詢實值特征的歐氏距離，并根據(jù)歐氏距離進行排序，選取最近的k個SQL語句來進行預測；

3）基于選擇出來的k個SQL 語句，投票決定查詢SQL 語句是否異常。

在算法2 中，雖然使用了SQL 語句的數(shù)據(jù)庫的實值特征，但實際實現(xiàn)基于二值編碼的異常SQL 檢測時，并不需要在內(nèi)存中加載全部的實值特征，僅需將k個SQL 語句的實值特征加載進內(nèi)存即可完成檢測過程。

3 實驗驗證

通過在一個異常SQL數(shù)據(jù)集上的實驗證明了本文提出的HMSD 方法的有效性。所有的實驗在一臺服務(wù)器上進行，該服務(wù)器的硬件配置為：Intel Xeon Gold 6248 CPU 2.50 GHz，40核心，內(nèi)存為442 GB。

3.1 數(shù)據(jù)集

本文采用異常SQL 語句的數(shù)據(jù)集Wafamole［21］進行實驗。該數(shù)據(jù)集已經(jīng)在github 網(wǎng)站公開，網(wǎng)址為https：//github.com/blindusername/wafamole-dataset。文獻［21］的作者收集了一個包含上百萬條正常SQL 語句和異常SQL 語句數(shù)據(jù)集Wafamole。本文通過對原始數(shù)據(jù)集進行去重清洗，然后篩選得到了包含20 000條正常SQL語句和20 000條異常SQL語句的子集以進行本文的實驗。在表2中給出了Wafamole數(shù)據(jù)集中正常SQL語句和異常SQL語句的示例。

表2 Wafamole數(shù)據(jù)集樣本示例Tab.2 Examples in Wafamole dataset

3.2 基準方法和實驗設(shè)置

本文采用k最近鄰方法、SVM 方法作為基準方法。最近鄰方法使用SQL 語句的特征表示之間的歐氏距離進行排序。對于給定的SQL 查詢，最近鄰使用排序后序列中前k個SQL語句的投票結(jié)果作為預測結(jié)果，用于預測查詢SQL 語句是否異常。SVM 方法中使用了RBF（Radial Basis Function）作為核函數(shù)。在訓練IsoH 方法過程中，設(shè)置迭代輪數(shù)為50。本文分別測試了比特長度為8 b、16 b、32 b、64 b、128 b 和256 b 情況下的檢測性能。對于最近鄰和HMSD-IsoH 方法，本文設(shè)置K=100，k=5。對于本文提出的HMSD-IsoH 方法，本文使用了海明排序作為粗排策略。

對于Wafamole 數(shù)據(jù)集，本文設(shè)置了3 種隨機劃分策略。分別表示如下：

1）10 000/30 000：訓練集包含10 000條SQL語句，測試集包含30 000條SQL語句；

2）20 000/20 000：訓練集包含20 000條SQL語句，測試集包含20 000條SQL語句；

3）30 000/10 000：訓練集包含30 000條SQL語句，測試集包含10 000條SQL語句。

在每種劃分策略中，保證訓練集和測試集中正常的SQL語句數(shù)目和異常的SQL語句數(shù)目相同。

為驗證HMSD-IsoH 的有效性。本文匯報了多種評價指標，包括一些評價精度的指標、評價檢測速度和內(nèi)存開銷的指標。評價精度的指標包括精確度（Accuracy）、假正例率（False Positive Rate，F(xiàn)PR）和假負例率（False Negative Rate，F(xiàn)NR）。本文直接匯報了檢測時間（Time，單位為ms）和內(nèi)存開銷（Memory Cost，單位為MB）來進行對比。

精確度（Accuracy）的計算根據(jù)返回的k個SQL 的情況決定，如果返回的k個SQL 語句中異常SQL 較多，則預測該查詢?yōu)楫惓?；反之，如果返回的k個SQL 語句中正常SQL 較多，則預測該查詢?yōu)檎！PR的計算公式如下所示：

其中：FP（False Positive）表示標記為正常但被錯誤識別為異常的數(shù)據(jù)點的數(shù)目，TN（True Positive）表示標記為正常且被正確識別為正常的數(shù)據(jù)點的數(shù)目。FNR的計算公式如下所示：

其中：FN（False Negative）表示標記為異常但被錯誤識別為正常的數(shù)據(jù)點的數(shù)目，TP（True Positive）表示標記為異常且被正確識別為異常的數(shù)據(jù)點的數(shù)目。

實驗中通過理論計算值展示了存儲開銷。對于HMSDIsoH方法，檢測時間包含了粗排過程和精排過程的所有時間。此外，檢測時間為每個查詢SQL語句檢測的平均時間。

最近鄰和HMSD-IsoH方法均使用python實現(xiàn)。為了避免由于隨機性帶來的結(jié)果不穩(wěn)定問題，所有的實驗均使用不同的隨機種子進行初始化并運行了5 次，最終展示了檢測精度和時間的平均性能。

3.3 異常SQL檢測性能

表3為最近鄰算法和HMSD-IsoH 算法在不同數(shù)據(jù)集劃分條件下的性能。

從表3 中可以看到，通過粗排和精排算法，HMSD-IsoH 方法能在所有情況下達到比最近鄰方法更高的精度，在所有情況下，HMSD-IsoH 的FPR 和FNR 也要比最近鄰方法更低。同時，隨著二值編碼長度的增加，HMSD-IsoH方法的檢索精度越來越高，F(xiàn)PR 和FNR 也變得越來越低。此外，從表3的結(jié)果中可以看到，HMSD-IsoH 能有效降低存儲空間，同時，基于二值編碼的異常SQL檢測能達到更高的檢測速度。隨著二值編碼長度的增加，存儲開銷有所增加，速度有所減慢，但整體上存儲開銷還是遠小于最近鄰方法，速度也遠快于最近鄰方法。

表3 Wafamole數(shù)據(jù)集上的檢測性能Tab.3 Detection performance on Wafamole dataset

3.4 實例展示

本節(jié)列舉了幾個在異常SQL 檢測數(shù)據(jù)集上進行異常SQL檢測任務(wù)的實際例子。具體來說，表4 展示了正常SQL 和異常SQL查詢使用HMSD-IsoH檢測后的結(jié)果。

表4 HMSD-IsoH方法在Wafamole數(shù)據(jù)集上的檢測實例展示（正常SQL查詢）Tab.4 Detection case study of HMSD-IsoH method on Wafamole dataset（normal SQL query）

在表4 中，第1 列表示當前的查詢SQL 語句，第2 列表示查詢SQL 語句是否異常，第3 列給出了前5 個返回的SQL 語句，第4 列標注了返回的語句是否異常。從表4 中可以看到，對于正常的SQL 查表操作，返回的SQL 語句也是正常的查表操作，查詢SQL 語句和返回SQL 語句的唯一區(qū)別只是參數(shù)不同。由于返回的前5 個SQL 語句均為正常SQL 語句，因此查詢被判定為正常SQL 查詢。表4 中同時給出了當查詢SQL 異常時，返回的SQL 語句也均為異常的情形。由于返回的所有SQL語句均為異常，因此預測當前查詢SQL語句為異常。

3.5 HMSD-IsoH與NN、SVM檢索精度對比

表5 中給出了最近鄰（NN）方法、HMSD-IsoH 方法與SVM方法的檢索精度對比。表5 中，HMSD-IsoH 方法采用128 b，最好的檢索精度使用加粗字體標識。

從表5中可以看出，在所有情況下，SVM 方法的檢索精度要稍好于最近鄰方法，HMSD-IsoH 方法的檢索精度要好于SVM方法。

表5 HMSD-IsoH與最近鄰方法、SVM方法的精度對比Tab.5 Accuracy comparison of HMSD-IsoH，NN and SVM

4 結(jié)語

為解決最近鄰方法應(yīng)用在異常SQL 檢測應(yīng)用中的問題，本文提出了一種基于哈希學習的異常SQL檢測方法。通過將SQL 語句表示成為二值編碼形式，解決了使用最近鄰進行異常SQL檢測時遇到的問題。在一個異常SQL檢測任務(wù)的數(shù)據(jù)集的實驗證明了與已有的基于最近鄰的異常SQL檢測方法相比，HMSD 能取得更好的檢測精度，并顯著降低存儲和計算開銷。