應用于擬態Web服務器的相似度求解方法①

王 燦， 倪 明， 喻衛東， 黎 想

(華東計算技術研究所， 上海 201808)

國家互聯網信息中心2016年12月報告顯示， 中國網站總量達到475.4萬個. 網站給人們生活提供多種便利， 同時也遭受越來越多的安全威脅， Web服務器作為網站承載平臺， 已經成為了網絡攻擊中的主要目標.為應對越來越嚴峻的網絡安全挑戰， 我國獨立自主提出了擬態防御技術[1]， 擬態防御技術使用動態調度策略切換等價異構執行體， 構造出動態異構冗余的擬態環境， 利用所構建環境的不確定性和非持續性切斷網絡攻擊鏈.

擬態Web服務器[2]是擬態防御技術在網站系統中一個應用， 在擬態網站系統中， 對每個異構執行體輸出結果合法性的判決是安全的前提， 表決器中的相似度求解算法則是表決器的核心內容.

目前現有擬態Web服務器的表決器中， 通過字符串編輯距離衡量異構執形體響應網頁的相似度[3]. 但是擬態Web服務器的異構執行體在發揮防御能力的同時也一定程度上造成了不同平臺響應的差異性， 其中很多差異并不會影響網頁的輸出效果， 卻很大程度上干擾了響應網頁之間相似性的判決結果. 本文采用改進簡單樹匹配算法計算異構執行體響應網頁的相似度，并應用于擬態Web服務器的表決器中， 提高了表決器的效率和準確性.

1 基于字符串編輯距離的相似度求解

字符串編輯距離是一種常用的字符串相似度指標.通過一些操作編輯一個字符串， 使其變成另外一個字符串， 編輯的最少次數即為衡量兩個字符串的相似度[4]指標. 在網頁相似性比較、網頁相關性排序以及快速模糊匹配等方面有很多應用.

1.1 字符串編輯距離求解

編輯距離是指原字符串A經過插入、刪除、替換三種編輯操作， 變成字符串B所需要的最少編輯次數.

設有2個字符串A和B:A=a1a2…am，B=b1b2…bm.式(1)構造了A與B的(m+1)×(n+1)階匹配關系矩陣LD，矩陣的第1列是字符串A， 第1行是字符串B:

匹配關系矩陣中的元素被稱為單元， 按如下方式計算:

匹配關系矩陣中元素dmn即為字符串A和B之間的編輯距離， 用ld表示.

1.2 基于LD的相似度計算公式

字符串A和B的相似度可通過ld計算，ld越小，A和B越相似， 反之， 差異越大. 根據編輯距離求解A和B的相似度公式如下:

式中，ld為字符串A和B之間的編輯距離， |A|和|B|分別表示2個字符串的長度.Similar(A，B)值越大， 說明字符串A和B越相似.

異構Web服務器對于網頁的請求響應存在差異性， 通常情況下這種差異并不會影響輸出， 但是利用字符串編輯距離求解網頁相似度時， 卻會干擾相似度的計算結果. 而且網頁作為一種結構化的內容[5，6]， 將網頁轉化成字符串利用編輯距離計算相似性時， 會跨越結構層級比較， 忽略網頁原有結構信息， 可能計算結果相似， 但呈現的結果卻有較大差異. 因此現有字符串編輯距離計算方法在擬態Web服務器系統應用中存在短板. 本文為適用擬態Web服務器的要求， 給出了對節點采用編輯距離比較相似性的改進簡單樹匹配計算方法.

2 基于改進簡單樹匹配的相似度求解

針對擬態Web服務器中采用字符串編輯距離處理網頁字符串計算量大， 忽略原有網頁結構信息等問題， 本文將異構執行體響應網頁轉化成保留原結構信息的DOM樹， 利用改進簡單樹匹配算法[7]計算異構執行體響應網頁的相似度. DOM樹的節點是響應網頁部分內容， 為兼容異構執行體造成的差異性， 在比較DOM樹的節點時， 計算節點間的編輯距離， 根據編輯距離與所設閾值的大小判定節點是否相似.

2.1 簡單樹匹配基本原理

令S和T為兩棵樹，i和j分別為S和T上的節點.定義S和T的匹配為映射M， 節點對 (i，j)∈M，i、j不是根節點.S=(RS，S1，…，Sm)和T=(RT，T1，…，Tn)是兩棵DOM樹，RS、RT分別表示子樹S和子樹T的根節點，Si和Tj為第i個和第j個第1層子樹. 根據編輯距離判斷S、T兩棵樹的對應節點是否匹配， 當RS和RT匹配時，S和T最大匹配為MS，T+1，MS，T是＜S1，S2，…，Sm＞和＜T1，T2，…，Tn＞最大匹配.MS，T由動態規劃算法求出 ，步驟如下:

步驟1. 若Sm和Tn最大匹配大于任意一個Sm和Ti(1≤i＜n)最大匹配， 那么MS，T是＜S1，S2，…，Sm-1＞和＜T1，T2， …，Tn-1＞之間的最大匹配加上Sm和Tn的最大匹配.

步驟 2. 否則，MS，T等于＜S1，S2， …，Sm-1＞和＜T1，T2，…，Tn＞之間的最大匹配或＜S1，S2， …，Sm＞和＜T1，T2，…，Tn-1＞之間的最大匹配相似.

2.2 節點相似度計算

擬態Web服務器異構執行體輸出結果會存在一定差異， 計算待匹配節點的編輯距離， 根據編輯距離差異程度判斷是否在可接受范圍內. 網頁DOM樹節點內容的字串量不大， 采用改進字符串編輯距離方法計算對應節點的相似度， 方法如下:

式中，n1、n2 是 2 個節點內容字符串， |pref|、|stuff|是字符串n1、n2最長公共前綴長度和最長公共后綴長度；lcs是n1、n2 去掉|pref|、|stuff|后剩余部分n1’、n2’的最長公共子串的長度；ed為n1、n2去掉|pref|和|stuff|后的編輯距離.

如果Similar(n1，n2)＞K1， 則判為相似， 否則判為不同.

2.3 基本簡單樹匹配算法

對樹S和T第一層進行遞歸匹配， 得到最大匹配，結果保存在W矩陣中， 根據矩陣W中的值計算矩陣M中的值. 算法如算法1.

算法1. 簡單樹匹配STM(S， T)輸入: S， T輸出: 匹配的節點數IF 樹S和T的根節點不相似RETRUN 0 ELSE m=樹S第一層節點數n=樹T第一層節點數Initialize M[i， 0]=0 (i=0，…， m)M[0， j]=0 (j=0，…， n)FOR i=1:m FOR j=1:n M[i， j] = max(M[i， j-1]， M[i-1， j]， M[i-1， j-1]+W[i， j])；W[i， j]=STM(Si， Tj)；ENDFOR ENDFOR RETURN M[m， n]+1 END

圖2舉例說明了基本簡單樹匹配算法執行過程.為求圖1中樹S和T的最大匹配， 首先進行第一層子樹的匹配， 定義M1-17[5， 3]是樹S和T第一層子樹的最大匹配； 由W1-17計算得到M1-17； 矩陣W1-17中的W[i，j]表示S和T第一層第i個和第j個子樹的最大匹配，繼續對M遞歸計算W值.

執行圖2運算流程， 可以求出兩棵樹的匹配節點個數. 顯然， 圖1中S、T兩棵樹有7個節點匹配.

圖1 兩顆DOM樹

圖2 部分節點匹配矩陣

2.4 相似度計算

擬態Web服務器網頁防篡改應用中， 表決器根據異構執行體響應網頁的相似度進行判決. DOM樹T1和T2相似度定義[8]如下:

式中， |T1|、|T2|分別是兩個樹的節點數， STM(T1，T2)是樹T1和T2的最大匹配值.similarity(T1，T2)值越大， 表示網頁T1和T2越相似.

3 擬態Web服務器防網頁篡改應用

網站作為復雜信息系統， 漏洞無法避免. 常見Web服務系統包括Web服務器硬件漏洞、數據庫漏洞、操作系統漏洞、網站源碼漏洞等， 攻擊者通常利用其中的一個或多個漏洞進行攻擊.

3.1 擬態Web服務系統基本模型

擬態防御技術中動態異構冗余機制[9，10](Dynamic Heterogeneous Redundancy， DHR)使得攻擊者無法建立穩定的攻擊鏈接. 執行體的冗余使得即便某個執行體被攻擊破壞， 也不會對系統的輸出結果產生直接影響， 并且動態性保證了攻擊結果無法重現， 大大降低了攻擊者攻擊成功的可能性.

擬態Web服務器借助動態異構冗余機制， 把Web服務系統部署在異構執行體上， 對輸出結果的一致性進行擇多判決后再輸出， 實現抗攻擊的目的.

圖3是擬態Web服務系統架構圖. 擬態Web服務系統由前端接入模塊、Web服務器池和控制器三部分組成. 前端輸入模塊主要實現了輸入代理和輸出代理兩個功能， 是用戶訪問的實際入口和實際出口. 輸入代理根據特定分發機制將用戶請求分發至Web服務器池中的執行體上， 輸出代理也被稱為表決器， 根據特定判決算法對來自不同執行體響應進行表決輸出. 池中包含多樣、異構、冗余的執行體， 對外界提供Web服務. 實際使用中， Web服務器池中只有一個執行體在線， 接收前端接入模塊分發請求并做出回應； 池中其余執行體一直處于待機狀態， 等待控制器模塊的上線指令. 控制器模塊根據系統異構性最大化策略調度池中的執行體， 降低了執行體的持續暴露時間和系統中存在一致性漏洞的可能性.

圖3 擬態Web服務器架構圖

圖3中的管理中心模塊主要起到監測作用， 檢測系統中其他模塊運行狀態， 處理各個模塊的正異常信息， 保證擬態Web服務器正常運行.

3.2 求解方法在擬態Web服務器的應用

在擬態Web服務器的表決器中， 將響應網頁解析成DOM樹形式， 使DOM樹除了包含網頁展示的文本信息外[11，12]， 還包含動態腳本信息. 對處理后的網頁 DOM樹用改進簡單樹匹配方法求最大匹配， 計算相似度值.

計算兩個網頁的相似度值時， 采用遞歸方式對DOM樹進行匹配， 求解樹的待匹配節點的字符串計算編輯距離， 根據對應節點編輯距離的差異程度判斷是否匹配. 統計出DOM樹中節點匹配的個數.

在計算異構執行體Web服務器響應網頁T1和T2的相似度之前， 將T1和T2作為普通字符串計算兩者長度的比值， 并將計算結果與設置的閾值K2進行比較， 若比值大于K2， 則說明兩個網頁的差異較大， 直接判定為不同， 不予輸出； 若比值小于等于閾值K2， 表決器利用特定相似度計算算法進行相似度判決， 計算出T1、T2的相似度值后與所設置的閾值K3進行比較. 若兩個網頁相似度大于等于K3， 則說明兩個網頁差異在允許的范圍內， 可判定為合法響應， 予以輸出； 若相似度小于K3， 則說明兩個網頁之間差異不在允許范圍內，判定為非法響應， 不予輸出. 表決器執行流程如圖4所示.

圖4 表決器處理流程圖

4 實驗結果分析

擬態Web服務器網頁防篡改應用場景中， 計算效率和計算準確性是兩個重要的評價指標. 本文中， 為驗證本方法的可用性， 采用計算效率和計算準確性兩個指標與現使用算法進行比較. 實驗將中電集團某研究所的官方網站部署到擬態Web服務器上. 基于字符串編輯距離的計算方法是通過計算兩個字符串的編輯距離判斷相似性， 于是在現有經典算法中將響應網頁看成一個字符串進行完全比較. 改進簡單樹匹配方法中，把響應網頁所轉換成的DOM樹進行匹配. 首先， 分別對具有差異性的8對網頁利用兩種算法計算相同請求中異構執行體響應網頁的相似度， 記錄相似度值和計算所用時間.

實驗中， 保存了Ubuntu和Centos兩個虛擬機執行體Web服務器中有差異的8對網頁， 在表決器中分別使用經典方法和改進簡單樹匹配方法計算每對網頁之間的相似度值并分別記錄耗時. 測試環境為CPU: E5 4 核； 內存: 8 GB； 操作系統: CentOS-7 64 位.

分別設計基于經典算法和本文算法的表決器， 對8對網頁相似度進行計算. 圖5和圖6為得到的相似度計算結果. 圖中結果顯示， 兩種算法所計算的正常網頁的相似度的結果差異不明顯， 改進的算法對網頁差異容忍度比經典算法略高， 但是差異不大， 不會對比較結果造成明顯影響.

圖5 a網站相似度求解算法結果對比

表1中記錄8對網頁分別采用經典方法和本文改進簡單樹匹配算法計算相似度的耗時結果， 對比表中數據可以看出， 本文所用改進算法大幅降低了計算耗時， 原因是改進算法中， 僅對網頁可展示部分以及部分腳本進行比較計算， 大大縮減了需要計算的字符串量.從表中還可以看出， 本文所用改進方法在計算網頁的DOM樹相似性時， 計算耗時與編輯距離和節點距離并不是線性關系. 其原因是， 改進的字符串匹配算法在比較網頁的相似度時， 采用的是遞歸的方式遍歷整棵DOM樹， 網頁被篡改的位置越靠近根節點， 所需計算時間越短， 差異地方越靠近葉節點， 所需時間越長. 實際應用場景中， DOM樹葉節點對應著網頁頁面上重要性相對低的位置， 這些位置被篡改價值低， 通常這些位置不會發生篡改， 因此改進方法可以防范常規的網頁篡改攻擊.

圖6 b網站相似度求解算法結果對比

表1 網頁相似性計算時間

實驗2， 在擬態防御系統中， 針對Centos虛擬機的在線Web服務器發起篡改網頁攻擊， 改變本實驗中網頁4的信息. 篡改形式包括更改官網標題、篡改官網超鏈接信息以及在網頁上嵌入惡意腳本信息等. 分別利用改進簡單樹匹配方法和現有經典方法計算被篡改網頁的相似度. 根據網頁被篡改前后相似度的變化程度判斷算法性能， 理論上， 變化幅度越明顯， 越能反應網頁被篡改的實際情況.

從圖7中可看出， 網頁被篡改后利用經典算法和改進簡單樹匹配方法所計算的相似度均出現一定程度下降. 但從圖中曲線變化趨勢來看， 針對前兩種篡改手段， 改進簡單樹匹配算法在網頁被篡改后有較明顯的下降趨勢， 在網頁嵌入惡意腳本攻擊情況下， 也保持了和現有經典方法相近的趨勢. 實驗結果表明， 在擬態Web服務器中， 與現使用方法相比， 本文所采用改進簡單樹匹配算法能夠在一定程度適應異構執行體Web服務器自身差異的基礎上， 提高了擬態防御系統中表決器對于網頁相似度計算所要求的準確性和計算效率.

圖7 篡改網頁檢測效果

5 結論與展望

針對擬態Web服務器的應用場景， 結合字符串編輯距離計算方法和簡單樹匹配算法， 本文設計了一種符合擬態Web服務器系統中表決器需求的改進簡單樹匹配算法， 并用其計算擬態Web服務器中異構執行體響應網頁的相似度. 實驗結果表明， 本文所使用的算法更適用于擬態Web服務器異構環境下的表決器判決場景， 在測試環境中提高了表決器的計算效率和準確性， 對于被篡改網頁有明顯檢測效果. 今后將對插入腳本篡改攻擊檢測不明顯、深層節點篡改檢測效率優化等方面做進一步的研究.