2024機器學習支持向量機算法

支持向量機算法支持向量機是分類算法里面使用范圍最為廣泛的算法之一，甚至可以自豪地說沒有之一，它廣泛地應用在生活中的眾多領(lǐng)域，基本上所有的分類問題，尤其是二分類問題，都可以先用它試下，眾多機器學習的教材都把支持向量機作為第一個算法來介紹，可見其重要地位。將介紹支持向量機的基本概念，并給出基本的使用方式。然后介紹如何使用支持向量機來檢測XSS，以及區(qū)分僵尸網(wǎng)絡的DGA家族。目錄TOC\o"1-1"\h\u301241支持向量機算法概述 3303532示例：helloworld！支持向量機 1230953示例：使用支持向量機算法識別XSS 1438614網(wǎng)絡DGA家族 22支持向量機算法概述有個非常有趣的帖子，Lvhhh用白話文解釋了支持向量機算法，非常形象，下面摘錄一下。某日，見藍球（深色）紅球（淺色）于一桌欲分之，見圖9-1。圖9-1 紅藍球故事1插一筷子于藍紅球之間則藍紅球可分，見圖9-2。圖9-2 紅藍球故事2未料，隨著球之增多，一紅球出界毀吾之分割，見圖9-3。可惜可氣。圖9-3 紅藍球故事3不服，遂變化筷子方向則又可分紅藍球也，見圖9-4。圖9-4 紅藍球故事4終有體會，欲合理分清紅藍之球，必使得近處紅藍球于筷子越遠越好。他日，又偶遇眾紅藍球，見圖9-5，吾又欲分之。圖9-5 紅藍球故事5拿筷子比劃半天無從分離，百思不得其解。遂大怒，猛一拍桌。紙隔于藍紅球之間，則藍紅之球可分也，見圖9-6。圖9-6 紅藍球故事6遂可得：若于桌面上不可分（二維），則拍桌，將球騰空而起（三維），則可分之。支持向量機（SupportVectorMachine，SVM）是機器學習領(lǐng)域使用最廣泛的算法之一，其原理如圖9-7所示，通常用來進行模式識別、分類以及回歸分析，它特別適合安全世界里面的非黑即白，所以我們重點介紹與分類相關(guān)的知識。圖9-7 SVM原理圖假設只有二維的特征向量，我們需要解決一個分類問題，需要通過將正常用戶和黑客區(qū)分開來，如果確實可以通過一條直線區(qū)分，那么這個問題成為可以線性可區(qū)分（linearseparable），如果不行則成為不可線性區(qū)分（linearinseparable）。討論最簡單的情況，假設這個分類問題是可以線性區(qū)分的，那么這個區(qū)分的直線成為超平面，距離超平面最近的樣本成為支持向量（SupprotVerctor）。圖9-8 SVM從二維平面升級到三維平面如圖9-8所示，對于不可線性區(qū)分的情況，需要升級到更高的平面進行區(qū)分，比如二維平面搞不定就需要升級到三維平面來區(qū)分，這個升級就需要依靠核函數(shù)。SVM通過一個非線性映射，把樣本空間映射到一個高維乃至無窮維的特征空間中（Hilbert空間），使得在原來的樣本空間中非線性可分問題轉(zhuǎn)化為在特征空間中的線性可分問題。簡單地說，就是升維和線性化。升維，就是把樣本向高維空間做映射，一般情況下這會增加計算的復雜性，甚至會引起“維數(shù)災難”，因而人們很少問津。但是作為分類、回歸等問題，很可能在低維樣本空間無法線性處理的樣本集，在高維特征空間中卻可以通過一個線性超平面實現(xiàn)線性劃分（或回歸）。一般的升維都會帶來計算的復雜化，SVM方法巧妙地解決了這個難題：應用核函數(shù)的展開定理，就不需要知道非線性映射的顯式表達式；由于是在高維特征空間中建立線性學習機，所以與線性模型相比，不但幾乎不增加計算的復雜性，而且在某種程度上避免了“維數(shù)災難”。這一切要歸功于核函數(shù)的展開和計算理論。選擇不同的核函數(shù)，可以生成不同的SVM，常用的核函數(shù)有以下四種：·線性核函數(shù)K（x，y）=x·y?！ざ囗検胶撕瘮?shù)K（x，y）=[（x·y）+1]^d?！较蚧瘮?shù)K（x，y）=exp（-|x-y|^2/d^2）。·二層神經(jīng)網(wǎng)絡核函數(shù)K（x，y）=tanh（a（x·y）+b）。示例：helloworld！支持向量機我們先演示支持向量機的基礎(chǔ)使用，完整演示代碼請見本書GitHub上的9-1.py。導入庫文件：print(doc)importnumpyasnpimportmatplotlib.pyplotaspltfromsklearnimportsvm創(chuàng)建40個隨機點：np.random.seed(0)X=np.r_[np.random.randn(20,2)-[2,2],np.random.randn(20,2)+[2,2]]Y=[0]*20+[1]*20#fitthemodelclf=svm.SVC(kernel='linear')clf.fit(X,Y)構(gòu)造超平面：w=clf.coef_[0]a=-w[0]/w[1]xx=np.linspace(-5,5)yy=a*xx-(ercept_[0])/w[1]#plottheparallelstotheseparatinghyperplanethatpassthroughthe#supportvectorsb=clf.support_vectors_[0]yy_down=a*xx+(b[1]-a*b[0])b=clf.support_vectors_[-1]yy_up=a*xx+(b[1]-a*b[0])調(diào)用matplotlib畫圖：plt.plot(xx,yy,'k-')plt.plot(xx,yy_down,'k--')plt.plot(xx,yy_up,'k--')plt.scatter(clf.support_vectors_[:,0],clf.support_vectors_[:,1],s=80,facecolors='none')plt.scatter(X[:,0],X[:,1],c=Y,cmap=plt.cm.Paired)plt.axis('tight')plt.show()運行代碼：localhost:codemaidou$python9-1.pyNonelocalhost:codemaidou$SVMhelloword代碼如圖9-9所示。圖9-9 SVMhelloword代碼示例：使用支持向量機算法識別XSS下面以常見的XSS檢測來說明下SVM的簡單應用。完整演示代碼請見本書GitHub上的9-2.py。處理流程數(shù)據(jù)處理流程如圖9-10所示。圖9-10 數(shù)據(jù)處理流程數(shù)據(jù)搜集和數(shù)據(jù)清洗由于我們的例子比較簡單，把上述兩個步驟合并即可，準備數(shù)量相等的正常Web訪問日志和XSS攻擊的Web日志，最簡單的方法是參考我以前的文章《基于WAVSEP的靶場搭建指南》，使用WVS等掃描器僅掃描XSS相關(guān)漏洞即可獲取XSS攻擊的Web日志。特征化實踐中數(shù)據(jù)搜集&數(shù)據(jù)清洗是最費時間的，特征化是最燒腦的，因為世界萬物是非常復雜的，具有很多屬性，然而機器學習通常只能理解數(shù)字向量，這個從現(xiàn)實世界的物體轉(zhuǎn)變成計算世界的數(shù)字的過程就是特征化，也叫向量化。比如要你特征化你前女友，你總不能說漂亮、溫柔這些詞，需要對最能代表她的特點的方面進行數(shù)字化，如圖9-11所示。圖9-11 現(xiàn)實生活中將事物向量化的例子大，但是不足以干掉其他全部特征，所以我們還需要對特征進行標準化，常見的方式為：·標準化；·均方差縮放；·去均值?；氐絏SS的問題上，我們需要針對Web日志進行特征化，如圖9-12所示。圖9-12 Web日志特征舉特征提取的示例代碼如下：defget_len(url):returnlen(url)defget_url_count(url):ifre.search('(http://)|(https://)',url,re.IGNORECASE):return1else:return0defget_evil_char(url):returnlen(re.findall("[<>,\'\"/]",url,re.IGNORECASE))defget_evil_word(url):returnlen(re.findall("(alert)|(script=)(%3c)|(%3e)|(%20)|(onerror)|(onload)|(e數(shù)據(jù)標準化使用如下代碼即可：min_max_scaler=preprocessing.MinMaxScaler()x_min_max=min_max_scaler.fit_transform(x)數(shù)據(jù)打標XSS標記為1，正常訪問標記為0。5.數(shù)據(jù)拆分這一步是為了隨機把數(shù)據(jù)區(qū)分成訓練組和測試組，通常直接使用cross_validation.train_test_split即可，通常40%作為測試樣本，60%作為訓練樣本，這個比例可以根據(jù)自己的需要進行調(diào)節(jié)：x_train,x_test,y_train,y_test=cross_validation.train_test_split(x,y,test_size數(shù)據(jù)訓練使用Scikit-Learn的SVM模型即可，SVM用于分類的模型稱為SVC，我們使用最簡單的核函數(shù)linear：clf=svm.SVC(kernel='linear',C=1).fit(x,y)joblib.dump(clf,"xss-svm-200000-module.m")模型驗證通過加載訓練后的模型，針對測試集合進行預測，將預測結(jié)果與打標結(jié)果進行比對：clf=joblib.load("xss-svm-200000-module.m")y_test=[]y_test=clf.predict(x)printmetrics.accuracy_score(y_test,y)在測試環(huán)節(jié)中，我們在一個各有20萬個樣本的黑白模型上進行訓練，在一個各有5萬個樣本的黑白測試集上進行校驗，任何黑白預測錯都判斷為錯誤，最后運行結(jié)果準確率為80%，對于機器學習而言，僅依（比如大型CDN&云WAF集群的日志），進一步增加特征個數(shù)以及增加后面環(huán)節(jié)的自動化或者半自動化的驗證，可以進一步提高這個比例，最后我們做到了準確率90%以上。圖9-13是特征擴展的舉例，大家可以根據(jù)實際情況增加個數(shù)。圖9-13 Web日志特征異常數(shù)據(jù)通過SVM我們識別出了異常數(shù)據(jù)，經(jīng)過人工確認，除了變形的XSS以外，還有不少其他攻擊行為，由于測試時只打開了XSS的規(guī)則簽名，所以其他攻擊行為沒有攔截，也進入了白樣本，舉例如下：/.|./.|./.|./.|./.|./.|./.|./.|./.|./.|./.|./windows/win.ini/index.php?op=viewarticle&articleid=9999/**/union/**/select/**/1331908730,1,1,1,1,1/index.php?go=detail&id=-99999/**/union/**/select/**/0,1,concat(1331919200,0x3a,512/examples/jsp/num/.|./.|./.|./.|./.|./.|./.|./.|./.|./.|./.|./.|./windows/win.ini/cgi-bin/modules/tinymce/content_css.php?templateid=-1/**/union/**/select/**/133192/manager/ajax.php?rs=expgetfeedcontent&rsargs[]=-99unionselect1161517009,2,1從廣義上講，XSS和SQL注入都是屬于代碼注入導致的漏洞。我們推測由于訓練樣本中混入了SQL注入的樣本，所以導致訓練結(jié)果中也出現(xiàn)了了SQL注入。網(wǎng)絡DGA家族僵尸網(wǎng)絡為了躲避域名黑名單，通常會使用DGA技術(shù)動態(tài)生成域名，通過DGA見的cryptolocker和post-tovar-goz兩個僵尸網(wǎng)絡家族為例，完整演示代碼請見本書GitHub上的9-3.py。數(shù)據(jù)搜集和數(shù)據(jù)清洗實驗階段，我們搜集了如下數(shù)據(jù)：·1000個cryptolocker域名；·1000個post-tovar-goz域名；·alexa前1000域名。DGA文件格式如下：xsxqeadsbgvpdke.co.uk,DomainusedbyCryptolocker-FlashbackDGAfor13Apr2017,2從DGA文件中提取域名數(shù)據(jù)：defload_dga(filename):domain_list=[]#xsxqeadsbgvpdke.co.uk,DomainusedbyCryptolocker-FlashbackDGAfor13Apr2#\h/manual/cl.txtwithopen(filename)asf:forlineinf:domain=line.split(",")[0]ifdomain>=MIN_LEN:returndomain_listalexa文件使用CSV格式保存域名的排名和域名，提取數(shù)據(jù)方式如下：defload_alexa(filename):domain_list=[]csv_reader=csv.reader(open(filename))forrowincsv_reader:domain=row[1]ifdomain>=MIN_LEN:domain_list.append(domain)returndomain_list特征化元音字母個數(shù)正常人通常在取域名的時候，都會偏向選取“好讀”的幾個字母組合，抽象成數(shù)學可以理解的語言，這使英文的元音字母比例會比較高。DGA的特征不明顯。下面我們通過數(shù)據(jù)分析來驗證我們的想法。讀取alexa域名數(shù)據(jù)：x1_domain_list=load_alexa("../data/top-1000.csv")計算元音字母的比例：defget_aeiou(domain_list):x=[]y=[]fordomainindomain_list:x.append(len(domain))count=len(re.findall(r'[aeiou]',domain.lower()))count=(0.0+count)/len(domain)y.append(count)returnx,y分別獲取兩個僵尸網(wǎng)絡DGA域名數(shù)據(jù)以及alexa域名數(shù)據(jù)，并計算元音字母比例：x1_domain_list=load_alexa("../data/top-1000.csv")x_1,y_1=get_aeiou(x1_domain_list)x2_domain_list=load_dga("../data/dga-cryptolocke-1000.txt")x_2,y_2=get_aeiou(x2_domain_list)x3_domain_list=load_dga("../data/dga-post-tovar-goz-1000.txt")x_3,y_3=get_aeiou(x3_domain_list)以域名長度為橫軸，元音字母比例為縱軸作圖：fig,ax=plt.subplots()ax.set_xlabel('DomainLength')ax.set_ylabel('AEIOUScore')ax.scatter(x_3,y_3,color='b',label="dga_post-tovar-goz",marker='o')ax.scatter(x_2,y_2,color='g',label="dga_cryptolock",marker='v')ax.scatter(x_1,y_1,color='r',label="alexa",marker='*')ax.legend(loc='best')plt.show()分析圖9-14，不同家族之間具有明顯聚合效果，正常域名與DGA之間具有一定的區(qū)分性。圖9-14 元音字母比例分布圖去重后的字母數(shù)字個數(shù)與域名長度的比例去重后的字母數(shù)字個數(shù)指的是域名中去掉重復的字母和數(shù)字后的個數(shù)，比如：·baidu的個數(shù)為5；個數(shù)為7；的個數(shù)為4。去重后的字母數(shù)字個數(shù)與域名長度的比例，從某種程度上反映了域名字符組成的統(tǒng)計特征。計算去重后的字母數(shù)字個數(shù)可以使用python的set數(shù)據(jù)結(jié)構(gòu)：defget_uniq_char_num(domain_list):x=[]y=[]fordomainindomain_list:x.append(len(domain))count=len(set(domain))count=(0.0+count)/len(domain)y.append(count)returnx,y分別獲取兩個僵尸網(wǎng)絡DGA域名數(shù)據(jù)以及alexa域名數(shù)據(jù)，并計算去重后的字母數(shù)字個數(shù)與域名長度的比例：x1_domain_list=load_alexa("../data/top-1000.csv")x_1,y_1=get_uniq_char_num(x1_domain_list)x2_domain_list=load_dga("../data/dga-cryptolocke-1000.txt")x_2,y_2=get_uniq_char_num(x2_domain_list)x3_domain_list=load_dga("../data/dga-post-tovar-goz-1000.txt")x_3,y_3=get_uniq_char_num(x3_domain_list)以域名長度為橫軸，去重后的字母數(shù)字占域名長度的比例為縱軸作圖，結(jié)果如圖9-15所示。圖9-15 唯一字母數(shù)字比例分布圖分析圖9-15，不同家族之間具有明顯聚合效果，正常域名與DGA之間具有一定的區(qū)分性。平均jarccard系數(shù)jarccard系數(shù)定義為兩個集合交集與并集元素個數(shù)的比值，本例的jarccard系數(shù)是基于2-gram計算的。計算兩個域名之間的jarccard系數(shù)的方法為：defcount2string_jarccard_index(a,b):x=set(''+a[0])y=set(''+b[0])foriinrange(0,len(a)-1):x.add(a[i]+a[i+1])x.add(a[len(a)-1]+'')foriinrange(0,len(b)-1):y.add(b[i]+b[i+1])y.add(b[len(b)-1]+'')return(0.0+len(x-y))/len(x|y)計算兩個域名集合的平均jarccard系數(shù)的方法為：defget_jarccard