基于改進遺傳的XML注入式攻擊自動測試

王 茜，高建華

(上海師范大學 計算機科學與技術系，上海 200234)

0 引 言

SOA(service-oriented architecture)[1]架構也稱面向服務架構，SOA技術的普及與發展使得基于該架構的Web服務安全問題日益突出。SOA架構Web服務安全問題的重要因素就是SOAP消息的傳輸。由于SOAP傳輸協議所依賴的WS安全標準存在缺陷，所以在SOAP消息在傳輸中易受到XML(extensible markup language)[2]注入等一系列針對Web服務的攻擊。

基于模糊測試[3]的檢測方法可以在滿足以下兩個條件的情況下檢測簡單的XML注入式攻擊漏洞：①沒有檢查XML格式和有效性機制；②測試工具可以觀察到被測系統的錯誤響應。然而一些攻擊可能來自于多個用戶輸入字段的組合，所以這就使XML注入式攻擊的形式變得更加復雜，檢測更加困難。

Julia等[4]通過研究發現，基于污點分析的檢測方法會產生許多錯誤警告，此外該方法生成的跟蹤信息有可能包含了許多不相關的信息，存在大量冗余的測試數據。

基于搜索的檢測方法能夠在有限的空間和時間內找到合適的解，且不受限于系統的規模。主要方法有基于粒子群優化算法[5]的搜索和基于遺傳算法的搜索等。但是基于粒子群優化算法的搜索會在執行不久后出現大量粒子聚集的現象，存在過早收斂的缺陷。

由此，本文提出了一種基于改進遺傳的XML注入式攻擊檢測方法。該方法使用實碼遺傳算法在搜索空間自動搜索用戶輸入。執行過程中，通過引入影響因子改進適應度函數計算方法，優化適應度函數值和算法的搜索，從而縮短搜索時間，提高搜索效率。

1 相關術語

1.1 XML注入式攻擊

與SQL注入式攻擊類似，XML注入式攻擊是通過將惡意內容注入到用戶輸入從而通過修改SOAP信息的內容和結構產生惡意XML信息來實現的。惡意的XML信息能夠導致目標系統的崩潰，某些XML信息還會威脅到處理惡意信息的系統本身。假設一個Web應用程序的注冊表單有3個用戶輸入字段，分別是用戶名、密碼和電子郵箱。當用戶提交注冊頁面信息時，應用程序會調用如圖1中所示的代碼產生相應的SOAP信息并將其發送到服務端。后端服務會通過調用getnewuserid()方法為該注冊新用戶分配一個唯一的標識碼UserId。

圖1 SOAP信息

如果此時用戶名輸入字段為：Tom，密碼輸入字段為：123456<！-，電子郵箱輸入字段為：mail=->123456@qq.com。此時該用戶輸入產生的XML消息如圖2所示，因為密碼輸入字段中帶有的特殊字段將原本需要輸入的密碼注釋掉，并非法獲得UserId。如果UserId為115的用戶具有管理員權限，此時就攻擊者就可以使用管理員身份進行非法操作。

圖2 XML消息

Briand等[6]通過研究發現，非惡意的XML消息通過突變操作可以生成4種類型的XML注入式攻擊。如表1所示，它們分別是：類型1：變形；類型2：隨即關閉標記；類型3：復制；類型4：替換。這4種類型的XML注入式攻擊分別使用不同方法生成惡意信息。類型1通過創建格式不正確的XML消息使系統受到攻擊；類型2的XML注入式攻擊通過帶有額外關閉標記來顯示XML文檔或者數據庫的隱藏信息；類型3和類型4旨在更改XML消息造成嵌入式嵌套攻擊。

表1 4種類型的XML注入式攻擊

1.2 編碼模式

本文提出的基于改進遺傳的XML注入式攻擊自動測試算法旨在搜索能夠造成系統受到攻擊的所有可能用戶輸入。如果存在導致被測系統(system under test，SUT)生成惡意XML輸出的用戶輸入，此時被測系統易受到XML注入式攻擊。因此，本文將這樣的用戶輸入看作是測試目標。

通常來說，輸入字符串的字符可由擴展ASCII碼或UNICODE表示，在本文中，只考慮ASCII碼32到127之間的可打印字符，因為大多數軟件不使用非輸出字符。

對于一個給定的被測系統，如果用戶頁面由N個輸入參數組成，則算法的搜索空間可以由Web表單提交的N個字符串的所有可能元組來表示。每個用戶輸入參數就是一個字符串，每個字符串可由任意字母、數字或者特殊字符的組合。

定義1測試目標：一個給定被測系統的候選測試用例是一個由N個輸入參數組成的字符串元組，記作TO

TO={S1,S2,…,SN}

定義2 輸入參數：一個給定被測系統的輸入參數都是一個由k個字符組成的字符串，記作S

S={c1,c2,…,ck}

定義3測試目標集合：本文的測試目標是經被測系統運行后能夠產生XML注入式攻擊的用戶輸入。被測系統不同用戶的輸入參數個數也有可能不同，其輸入參數的長度限制也不同。將系統的用戶輸入看作是一個集合，稱為測試目標集合，記作T

TOs={TO1,TO2,TO3,…,TOn}

定義4注入式攻擊集合：注入式攻擊由SOLMI[5]自動生成，不同系統的XML注入式攻擊有所不同，每個系統生成的攻擊會有多個，將同一系統生成的XML注入式攻擊看作是一個集合，稱為注入式攻擊集合，記作T

T={T1,T2,T3,…,Tk}

如果存在用戶輸入TOi經被測系統執行后，產生惡意XML信息Tj則稱該注入式攻擊被覆蓋則可以表示為：SUT(TOi)=Tj。值得注意的是，測試目標TO和T并不一定是一一對應的，而且TO通過被測系統產生的T必須是滿足語法要求并且包含惡意消息的XML信息。

2 基于改進遺傳的自動測試

基于搜索的測試在進行搜索時，需解決以下3個基本問題：①選擇合適的編碼模式來表示測試目標；②選擇合適的適應度函數來指導算法的搜索；③選擇高效的搜索算法來算搜索測試用例。針對問題①本文在1.2小節中已給出解決方案。

2.1 基于改進編輯距離的適應度函數

針對問題②，搜索的有效性很大程度上取決于適應度函數的指導，適應度函數是對候選測試目標與目標相似度的評估。本文的候選測試目標(也可稱作為候選解決方案)是用戶輸入經過被測系統執行后產生的XML信息，目標是由SOLMI[5]自動生成的XML惡意信息。所以針對本文研究內容，適應度函數值由用戶輸入經被測系統執行后產生的信息與已知攻擊的相似度，即字符串之間的距離決定。

2.1.1 基于實數編碼的編輯距離

不同于漢明距離，編輯距離(edit distance，Ed)可以用來比較不同長度字符串之間距離。編輯距離是指將原字符串轉換為目標字符串所用的最少編輯操作次數。其中編輯操作包括插入、刪除和替換一個字符。

假設有兩個字符串An=a1a2…an和Bm=b1b2…bm，則字符串編輯距離可定義為如下遞歸關系

(1)

其中，an是字符串An中第n個字符，同理bm是字符串Bm中第m個字符。如果an,bm匹配，則f(an,bm)的值為0，否則值為1。

由此，考慮以下問題I：

假設一條XML注入式攻擊信息為T1=，有3個候選測試目標分別是TO1，TO2和TO3。他們通過被測系統分別產生如下XML信息：SUT(TO1)=At>,SUT(TO2)=^t>,SUT(TO3)=

Ed(T1,SUT(TO1))= Ed(T1,SUT(TO2))= Ed(T1,SUT(TO3))=1

因為傳統編輯距離只考慮操作次數，所以在這種情況下無法具體區分3個候選解決方案與目標的距離。為了解決這種情況，本文將搜索的重點放在目標領域的子區域上并提出了改進方案。在編輯距離的基礎上提出了實碼編輯距離[7](real-code edit distance，Rd)，將式(1)中的f(an,bm)替換成字符之間的ASCII碼的相對距離，則實碼編輯距離遞歸關系定義如下

(2)

(3)

φ(x)=x/(x+1)

(4)

由式(2)重新計算問題I中各個候選解決方案與目標的距離可以得出，最終3個候選解決方案經過被測系統執行后與T1之間的距離別為0.83，0.97和1

Rd(T1,SUT(TO1))=0.83

Rd(T1,SUT(TO2))=0.97

Rd(T1,SUT(TO3))=1

如圖3所示，圖3(a)、圖3(b)分別表示編輯距離和實碼編輯距離兩種距離算法。針對問題I，從圖3中可以看出，圖3(b)的實碼編輯距離能夠更加精確地區分候選解決方案執行后與目標T之間的距離，換句話來說，相對于傳統編輯距離，實碼編輯距離可以使搜索算法擁有更廣的搜索鄰域。

圖3 兩種距離算法對比

2.1.2 改進的適應度函數算法

大部分遺傳算法使用目標函數作為適應度函數，適應度函數的設計直接影響了遺傳算法的性能。這種適應度函數雖然簡單直觀，但是某些待解決問題的函數值可能彼此相差較大，這種簡單的適應度函數求解不利于群體的平均性能，影響了算法的效果。

常見的基于編輯距離的相似度計算式(5)定義為

(5)

在本文中，適應度函數可以直接由字符串間距離帶入式(5)得到，距離越小適應度函數值也就越大，適應度函數值越大則表示與目標越接近。但是這種適應度函數計算方法沒有考慮字符串之間公共子序列對相似度的影響。

文獻[8]介紹了最長公共子序列(longest common subsequence，LCS)的概念，為了解決問題II，本文在實碼編輯距離的基礎上改進了適應度函數的計算公式，將字符串最長公共子序列的長度和第一次出現不匹配字符的位置作為影響因子帶入計算得出新的適應度函數計算方法。

Needleman-Wunsch算法[8]是一種動態的編程方法，它可以用來計算最長公共子序列，并且能夠找到兩個字符串最優全局對齊。假設兩個字符串An=a1a2…an和Bm=b1b2…bm，通過式(6)可以得出算法矩陣，并通過回溯找出匹配字符串

(6)

通過引入影響因子LCS和第一次出現不匹配字符的位置p，本文重新定義適應度函數式(7)如下

(7)

重新考慮問題II，首先由式(6)計算得出BA和A與T2的Needleman-Wunsch算法矩陣，如圖4所示。

圖4 LSC矩陣

再將LSC值帶入式(7)即可得出

Sim′(T2,SUT(TO′1))=0.4

然而在自然語言處理以及數據挖掘等領域中，要將處理的語句轉化為邏輯表達式，這種轉化過程需要提取大量的特征并將實體映射到知識庫。這里的特征可以來自多個不同的維度。如數據分析模型中，需要通過用戶行為來分析用戶價值相似度或者使用用戶對內容的評分來區分用戶興趣的相似性等情況。這里的相似度評估不僅僅是計算字符串之間的距離，而來自于用戶相關操作等多個維度。在這種情況下，歐氏距離和余弦相似度的優勢得以體現。本文提到的基于改進編輯距離算法的應用需要進一步的研究和驗證。

2.2 基于實數編碼的遺傳算法

確定好編碼模式和適應度函數，就可以用搜索算法來搜索解決方案，文獻[9]中提出了各種搜索算法來解決軟件工程問題。傳統的搜索算法有隨機搜索算法(random search，RS)，(hill climbing，HC)算法，標準遺傳算法(standard genetic algorithm，SGA)。

SGA標準遺傳算法是一個模擬自然進化得到最優解的過程。SGA模擬了自然選擇和自然遺傳過程中發生的繁殖、交配和變異現象，并通過適者生存、優勝劣汰的自然法則產生新的群體，并比較個體，不斷迭代最終得到最優解。SGA算法是一種全局搜索算法，它有效地解決多模態問題。因為使用多個解決方案來采樣搜索空間，這可能會導致搜索過程的偏差。另一方面，與HC相比，局部最優收斂速度較慢。因此，對于單模問題，它的有效性和效率通常較低。所以本文針對標準遺傳算法的問題在處理單模問題時收斂速度和效率的局限性提出了改進的解決方案。

為了解決以實數或整數作為決策變量的數值問題，本文提出使用實碼遺傳算法，采用實數編碼可以大大提高計算的精度和計算效率。與標準遺傳算法不同的是，本文中的實碼遺傳算法在交叉算子和突變算子上的設計不再是對字符進行直接操作，而是對相應字符的ASCII碼進行操作，實碼遺傳算法與標準遺傳算法區別之處在于交叉和變異算子的選擇。如表2所示實碼遺傳算法的交叉選用算術交叉，變異選用高斯變異。

表2 遺傳算子對比

二元競賽選擇算子，在進行交叉和變異之前，先將每個字符替換為相應的ASCII代碼，再將輸入字符串轉換為整數數組。

ai′=ai·ρ+bi·(1-ρ)

(8)

bi′=bi·ρ+ai·(1-ρ)

(9)

其中，ρ是0到1之間的隨機數，最終的ai′和bi′通過四舍五入取最接近的整數值。

高斯突變與標準遺傳算法中的均勻變異類似，種群中的每個測試目標TO都是通過在相應的字符數組中刪除、替換或添加字符來進行變異。不同的是，高斯突變處理的是數值數據，這些數值被替換為其它數值的同時遵循高斯分布[11]。假設C={c1,c2,c3,…cj,…,ck} 作為突變的ASCII碼數組，數組中隨機位置j的元素會被替換成新的ASCII碼，并且數組中每個位置突變的概率都相等，數組中元素被替換遵循式(10)

cj*=cj+cj·δ(μ,σ)

(10)

其中，δ(μ,σ)是正態分布隨機數，平均數μ為0，方差是σ。同樣最終高斯突變產生的數值取相近的整數值，如果產生的數值不是32到127范圍內的可打印字符則取消本次突變。

結合改進的適應度函數算法和基于實數編碼的遺傳算法，本文提出的算法整體框架流程如圖5所示：

圖5 核心算法流程

(1)初始化：設置種群大小，交叉概率Pc，突變概率Pm，最大的迭代次數max_propagate；

(2)計算適應度函數值：使用基于改進編輯距離的實碼編輯距離計算字符串之間的距離，并用式(7)通過引入影響因子計算得出適應度函數值。

(3)選擇：二元競賽選擇按照適應度值選擇優秀個體；

(4)交叉：使用算數交叉對選擇的個體進行重新組合，產生新的個體；

(5)突變：高斯突變進行變異操作，產生新的種群；

(6)判斷：若到達終止條件，退出算法，否則跳轉(2)，繼續進行下一次迭代。

本文提出的基于改進遺傳算法的自動測試，解決了SGA在單模問題上有效性和效率通常較低的問題，并且通過基于改進的編輯距離的適應度函數算法優化了搜索的精確度，提高搜索的效率。

3 實 驗

3.1 實驗環境與參數的配置

為了驗證適應度函數和搜索算法的有效性，本文在JMetal上實現了測試工具的開發，本文實驗硬件環境為Intel Core i5 2.5 GHz處理器，8 GB內存。實驗在Windows10操作系統下完成，使用Java編程語言。工具由測試用例生成器和測試執行器兩個部分組成。核心組件測試用例生成器用來搜索用戶輸入，測試用例執行器在測試用例生成器和被測系統之間提供接口，提交由測試用例生成器產生的輸入給被測系統，被測系統生成對應的XML消息由執行器截獲并轉發給測試用例生成器并評估適應度函數得分。為了驗證通用性，本文在兩個規模不同的系統上進行了實驗。

首先在滲透測試演練系統MCIR(magical code injection rainbow)上進行實驗。XMLMao是MCIR中的是一個開源的應用程序，它是能夠構建可配置脆弱性測試平臺的框架，可以接收單個用戶輸入并產生相對應的XML信息。

其次設計了一個模擬仿真的銀行系統SASB(security analog simulation BANK)，仿真系統實現了簡單的HTML表單和輸入處理例程，并且有3個用戶輸入字段。并且SASB帶有對用戶輸入參數的驗證。

3.2 變量的選擇

在實驗中，本文將適應度函數和搜索算法的組合看作獨立變量來研究它們對實驗的影響。實驗內容將適應度函數和搜索算法看作是一個組合來評估它們的有效性，實驗研究了兩種搜索算法(SGA和RGA)和兩種不同適應度函數算法下(Sim[Ed],Sim[Rd]和Sim′[Rd])組合的有效性。(Sim[Ed]表示使用編輯距離和式(5)計算適應度；Sim[Rd]表示使用實碼編輯距離和式(5)計算適應度；Sim′[Rd]表示使用實碼編輯距離和式(7)計算適應度)。

為了驗證算法的有效性，方便評估實驗。本文定義成功率函數SR(success_rate)，式(11)中的Successful_runs代表了攻擊被覆蓋的次數，Total_runs代表的是運行總次數。成功率函數SR的數值越大，組合對測試目標的搜索的效果越好

(11)

另外，為了描述成功率的離散性，本文用式(12)來計算SR的標準差SD(standard deviation)，標準差函數越小組合的穩定性越好。其中N是同一組合中測試目標的個數，SR是組合中某一測試目標的成功率，μ是組合中所有測試目標成功率的平均值

(12)

3.3 參數設置

搜索算法執行時各參數值具體設置如下：

突變概率：文獻[7]證明了基于種群大小和染色體長度的突變概率Pm值可以獲得更好的性能，因此本文的RGA和SGA采用式(13)作為突變概率。其中λ是種群大小，l是種群中染色體(測試目標)的長度

(13)

交叉概率：文獻[12]提到交叉概率Pc的最佳范圍在0.45和0.95之間，本文的實驗中選取0.70作為交叉概率。

種群大小：本文設置種群規模為50，此值也與基于搜索的軟件測試[13,14]研究中使用的參數設置一致。

3.4 研究問題

本文的研究涉及到以下幾個問題：

Q1：XML注入式攻擊的最佳搜索算法是什么？

針對這一問題，本文比較了兩種搜索算法分別在3種不同適應度函數算法的指導下對測試目標的搜索。

Q2：XML注入式攻擊的最佳適應度函數是什么？

針對這一問題，本文主要比較3種不同適應度計算方法分別應用在兩種搜索算法時對實驗的影響。

本文除了研究適應度函數和搜索算法對實驗的影響，還研究了另外兩個可能對實驗有影響的因素：字母表的大小和遺傳算法中初始種群個體長度的限制。

假如已知攻擊T中不包含字符“A”,那么就可以認為字符“A”不會出現在可以導致XML注入式攻擊的用戶輸入中，所以可以通過忽略這些不出現在已知攻擊中的字符來限制字母表的大小從而減少搜索空間。

在搜索測試目標時，所有的搜索算法都是從一組隨機生成的解開始的，如果隨機生成的字符串與最終的解決方案相比太長或者太短，每次處理這些字符串時就會耗費更多的時間。所以考慮以下兩種設置：①生成具有固定(Fixed簡稱F)最大長度的字符串；②或者生成可變(Variable簡稱V)長度的字符串。

Q3：字母表的大小是否會對算法的搜索有影響？

針對這一問題，本文將對使用全字母表(Full.Alph)和限制字母表(Res.Alph)進行對比實驗，并分析得到結果。

Q4：遺傳算法初始種群中字符串的長度限制是否對算法的搜索有影響？

針對這一問題，本文將對遺傳算法初始種群的字符串長度采用兩種不同限制條件進行對比實驗，分別是：字符串定(F)長和可變(V)長。

根據上述問題中涉及到的影響因素，設計了不同約束條件的測試目標，實驗Id(Exp.Id)根據應用程序(App)、用戶輸入參數個數(Inp)、初始種群輸入字符串的長度(PopLen)以及字母表是否受限制(Res.Alph)來命名的。例如，SASB中，有2個用戶輸入并且是可變長，全字母表的測試用例ID定義為S.2.V.F，以此類推，針對不同被測系統，實驗設計了16種不同約束條件的測試用例，并分析影響搜索結果的約束條件。

3.5 實驗結果分析

表3總結了XMLMao系統中各組合的實驗結果，表中列出了各組合的成功率(SR)、標準差(SD)和執行時間(execution time，ET)的數據，其中執行時間的單位是分鐘。在只有單一用戶輸入的XMLMao開源系統中，RGA算法在搜索成功率方面明顯優于SGA，其中RGA在使用Sim′[Rd]和Sim[Rd]指導搜索時的成功率可以達到100%。再對比執行時間數據，可以發現無論是RGA還是SGA在使用Sim′[Rd]指導算法搜索時，執行時間都是最短的，Sim′[Rd]指導RGA平均用時0.92 min，指導SGA搜索平均用時5.64 min。總結得出，Sim′[Rd]指導下的RGA搜索效率較高。

表3 XMLMao中組合的成功率、標準差和執行時間數據

為了驗證算法的通用性，實驗收集了在模擬仿真系統上的數據并加以分析。該系統有3個用戶輸入字段，并結合用戶輸入字段個數、字符長度限制和字母表限制等約束條件定義了以下12種不同限制條件下的搜索實驗。如表4所示，在有3個用戶輸入字段的SASB系統中，RGA算法的搜索成功率明顯高于SGA算法，在Sim′[Rd]指導下的RGA成功率可以達到96%。同樣Sim′[Rd]指導下的SGA只有69%。同樣是RGA搜索算法的前提下，Sim′[Rd]指導的搜索成功率高于其它適應度函數指導的搜索，并且擁有最短的執行時間，平均時間約為3.36 min。總結得出，在有多個用戶輸入的系統中，搜索成功率雖然不能達到100%，但是Sim′[Rd]指導的RGA依舊在搜索效率上表現出優勢，在實碼遺傳算法的搜中相比Sim[Ed]成功率提高了83.3%，而且擁有更短的執行時間。

表4 SASB中組合的成功率、標準差和執行時間數據

為了更加清晰地分析字母表和初始種群字符串長度限制因素對搜索的影響，本文使用圖的形式描述實驗數據。圖6描述了XMLMao和SASB兩個系統中初始種群和字母表限制因素對實驗搜索平均成功率數據。從各組合數據中可以看出，當初始種群中字符串長度可變時，成功率高于字符串定長限制，成功率最高可提升16.2%。

圖6 字符限制因素成功率對比

圖7給出了字母表限制約束條件下的兩個系統的平均成功率數據。分析圖中數據可以得到結論：在字母表現制約束件下，使用限制字母表的搜索成功率高于全字母表限制，成功率最高提升了15.4%。結合兩圖6和圖7的數據可以得出結論：在搜索測試用例時，設置初始種群字符串長度可變，并限制字母表可以得到更高的成功率，有助于提高搜索算法的搜索效率。

圖7 字母表限制因素成功率對比

4 結束語

本文針對XML注入式攻擊提出了一種改進遺傳的搜索算法，用來搜索對系統造成XML注入式攻擊的用戶輸入。實驗結果表明，基于改進編輯距離的適應度函數可以有效地指導實碼遺傳算法的搜索，可以一定程度上縮短測試程序的運行時間，提高搜索效率。未來的研究內容可以將該搜索算法應用到對SOA架構Web應用程序的WSDL文檔解析方面，通過增加約束項目等方法解析WSDL文檔生成并優化測試用例集，在保證測試的前提下減少測試用例集的冗余，提高系統抵御攻擊的能力并應用在更大更復雜的系統中。