<a href="http://jaq.alibaba.com/community/art/show?articleid=871">學點算法搞安全之hmm（上篇）</a>
前言
本篇重點介紹hmm最常見同時也比較基礎的基于url參數異常檢測的應用，後繼文章将介紹hmm結合nlp技術在xss、sql、rce方面的應用。”多一個公式少一半讀者”，是以霍金的《時間簡史》和《明朝那些事》一樣暢銷，我的機器學習系列文章都是盡量少講概念，多講例子，希望可以讓機器學習被更多人了解和使用。
hmm基礎原理
現實世界中有一類問題具有明顯的時序性，比如路口紅綠燈、連續幾天的天氣變化，我們說話的上下文，hmm的基礎假設就是，一個連續的時間序列事件，它的狀态受且僅受它前面的n個事件決定，對應的時間序列可以成為n階馬爾可夫鍊。
假設今天是否有霧霾隻由前天和昨天決定，于是就構成了一個2階馬爾可夫鍊，若昨天和前天都是晴天，那麼今天是晴天機率就是90%。
稍微再複雜點，假設你想知道2000公裡外一個城市的霧霾情況，但是你沒法直接去當地看到空氣情況，手頭隻有當地風力情況，也就是說空氣狀态是隐藏的，風力情況是可觀察的，需要觀察序列推測隐藏序列，由于風力确實對霧霾情況有較大影響，甚至可以假設風力大的情況下90%機率是晴天，是以通過樣本學習，确實可以達到從觀察序列推測隐藏序列的效果，這就是隐式馬爾可夫。
常見的基于get請求的xss、sql注入、rce，攻擊載荷主要集中在請求參數中，以xss為例：
/0_1/include/dialog/select_media.php?userid=%3cscript%3ealert(1)%3c/script%3e
正常的http請求中參數的取值範圍都是确定的，這裡說的确定是指可以用字母數字特殊字元來表示，并非說都可以用1-200這種數值範圍來确定。以下面的幾條日志為例：
/0_1/include/dialog/select_media.php?userid=admin123
/0_1/include/dialog/select_media.php?userid=root
/0_1/include/dialog/select_media.php?userid=maidou0806
/0_1/include/dialog/select_media.php?userid=52maidou
/0_1/include/dialog/select_media.php?userid=wjq_2014
/0_1/include/dialog/select_media.php?userid=mzc-cxy
肉眼觀察可以歸納出userid字段的由字母數字和特殊字元’-_’組成,如果你足夠強大可以看完上萬的正常樣本，甚至都可以總結取值範圍為[0-9a-za-z-_]{4,}。如果有上億的日志上百萬的參數，人工如何完成？這時候機器學習可以發揮作用了。
以uid字段為例，uid的取值作為觀察序列，簡化期間可以對uid的取值進行泛化，整個模型為3階hmm，隐藏序列的狀态隻有三個s1、s2、s3:
[a-za-z]泛化為a
[0-9]泛化為n
[\-_]泛化為c
其他字元泛化為t
admin123泛化為aaaaannn
root泛化為aaaa
wjq_2014泛化為aaaacnnn
隐藏序列就是s1-s4三個狀态間循環轉化，這個機率稱為轉移機率矩陣，同時四個狀态都以确定的機率，以觀察序列中的a、c、n、t四個狀态展現，這個轉換的機率稱為發射機率矩陣。hmm模組化過程就是通過學習樣本，生成這兩個矩陣的過程。生産環境中泛化需謹慎，至少域名、中文等特殊字元需要再單獨泛化。
由于每個域名的每個url的每個參數的範圍都可能不一樣，有的userid可能是[0-9]{4，}，有的可能是[0-9a-za-z-_]{3,}，是以需要按照不同域名的不同url不同參數分别學習。泛化過程如下：
def etl(str):
vers=[]
for i, c in enumerate(str):
c=c.lower()
if ord(c) >= ord('a') and ord(c) <= ord('z'):
vers.append([ord('a')])
elif ord(c) >= ord('0') and ord(c) <= ord('9'):
vers.append([ord('n')])
else:
vers.append([ord('c')])
return np.array(vers)
友情提示，為了避免中文等字元的幹擾，ascii大于127或者小于32的可以不處理直接跳過。
從weblog中提取url參數，需要解決url編碼、參數抽取等惡心問題，還好python有現成的接口：
with open(filename) as f:
for line in f:
#切割參數
result = urlparse.urlparse(line)
# url解碼
query=urllib.unquote(result.query)
params = urlparse.parse_qsl(query, true)
for k, v in params:
#k為參數名，v為參數值
友情提示，urlparse.parse_qsl解析url請求切割參數時，遇到’;’會截斷，導緻擷取的參數值缺失’;’後面的内容，這是個大坑，生産環境中一定要注意這個問題。
安裝hmmlearn
hmmlearn是python下的一個hmm實作，是從scikit-learn獨立出來的一個項目，依賴環境如下：
python >= 2.6
numpy (tested to work with >=1.9.3)
scipy (tested to work with >=0.16.0)
scikit-learn >= 0.16
安裝指令如下：
pip install -u --user hmmlearn
将泛化後的向量x以及對應的長度矩陣x_lens輸入即可，需要 x_lens的原因是參數樣本的長度可能不一緻，是以需要單獨輸入。
remodel = hmm.gaussianhmm(n_components=3, covariance_type="full", n_iter=100)
remodel.fit(x,x_lens)
訓練樣本得分為：
score:16 query param:admin123
score:9 query param:root
score:21 query param:maidou0806
score:16 query param:52maidou
score:15 query param:wjq_2014
score:12 query param:mzc-cxy
hmm模型完成訓練後通常可以解決三大類問題，一類就是輸入觀察序列擷取機率最大的隐藏序列，最典型的應用就是語音解碼以及詞性标注；一類是輸入部分觀察序列預測機率最大的下一個值，比如搜尋詞猜想補齊等；另外一類就是輸入觀察序列擷取機率，進而判斷觀察序列的合法性。參數異常檢測就輸入第三種。
我們定義t為門檻值，機率低于t的參數識别為異常，通常會把t定義比訓練集最小值略大，在此例中可以取10。
# 切割參數
query = urllib.unquote(result.query)
for k, v in params：
if ischeck(v) and len(v) >=n :
vers = etl(v)
pro = remodel.score(vers)
if pro <= t:
print "pro:%d v:%s line:%s " % (pro,v,line)
以userid=%3cscript%3ealert(1)%3c/script%3e為例子，經過解碼後為<script>alert(1)</script>，範化後為taaaaaataaaaatntttaaaaaat，score為-13945，識别為異常。
本文介紹了hmm在web安全的基礎應用，由于僅依賴參數的文本特征進行異常檢測，雖然理論上隻要白樣本足夠多确實可以識别幾乎所有基于get請求參數的未知攻擊，但是由于缺乏語義層面異常檢測，誤報率比較高。另外掃描器等對結果的影響很大，如何進一步提升檢測能力，請看下篇。
本文來自合作夥伴“阿裡聚安全”，發表于2017年05月11日 11:24.