2024機(jī)器學(xué)習(xí)支持向量機(jī)算法

支持向量機(jī)算法支持向量機(jī)是分類算法里面使用范圍最為廣泛的算法之一，甚至可以自豪地說沒有之一，它廣泛地應(yīng)用在生活中的眾多領(lǐng)域，基本上所有的分類問題，尤其是二分類問題，都可以先用它試下，眾多機(jī)器學(xué)習(xí)的教材都把支持向量機(jī)作為第一個算法來介紹，可見其重要地位。將介紹支持向量機(jī)的基本概念，并給出基本的使用方式。然后介紹如何使用支持向量機(jī)來檢測XSS，以及區(qū)分僵尸網(wǎng)絡(luò)的DGA家族。目錄TOC\o"1-1"\h\u301241支持向量機(jī)算法概述 3303532示例：helloworld！支持向量機(jī) 1230953示例：使用支持向量機(jī)算法識別XSS 1438614網(wǎng)絡(luò)DGA家族 22支持向量機(jī)算法概述有個非常有趣的帖子，Lvhhh用白話文解釋了支持向量機(jī)算法，非常形象，下面摘錄一下。某日，見藍(lán)球（深色）紅球（淺色）于一桌欲分之，見圖9-1。圖9-1 紅藍(lán)球故事1插一筷子于藍(lán)紅球之間則藍(lán)紅球可分，見圖9-2。圖9-2 紅藍(lán)球故事2未料，隨著球之增多，一紅球出界毀吾之分割，見圖9-3。可惜可氣。圖9-3 紅藍(lán)球故事3不服，遂變化筷子方向則又可分紅藍(lán)球也，見圖9-4。圖9-4 紅藍(lán)球故事4終有體會，欲合理分清紅藍(lán)之球，必使得近處紅藍(lán)球于筷子越遠(yuǎn)越好。他日，又偶遇眾紅藍(lán)球，見圖9-5，吾又欲分之。圖9-5 紅藍(lán)球故事5拿筷子比劃半天無從分離，百思不得其解。遂大怒，猛一拍桌。紙隔于藍(lán)紅球之間，則藍(lán)紅之球可分也，見圖9-6。圖9-6 紅藍(lán)球故事6遂可得：若于桌面上不可分（二維），則拍桌，將球騰空而起（三維），則可分之。支持向量機(jī)（SupportVectorMachine，SVM）是機(jī)器學(xué)習(xí)領(lǐng)域使用最廣泛的算法之一，其原理如圖9-7所示，通常用來進(jìn)行模式識別、分類以及回歸分析，它特別適合安全世界里面的非黑即白，所以我們重點(diǎn)介紹與分類相關(guān)的知識。圖9-7 SVM原理圖假設(shè)只有二維的特征向量，我們需要解決一個分類問題，需要通過將正常用戶和黑客區(qū)分開來，如果確實(shí)可以通過一條直線區(qū)分，那么這個問題成為可以線性可區(qū)分（linearseparable），如果不行則成為不可線性區(qū)分（linearinseparable）。討論最簡單的情況，假設(shè)這個分類問題是可以線性區(qū)分的，那么這個區(qū)分的直線成為超平面，距離超平面最近的樣本成為支持向量（SupprotVerctor）。圖9-8 SVM從二維平面升級到三維平面如圖9-8所示，對于不可線性區(qū)分的情況，需要升級到更高的平面進(jìn)行區(qū)分，比如二維平面搞不定就需要升級到三維平面來區(qū)分，這個升級就需要依靠核函數(shù)。SVM通過一個非線性映射，把樣本空間映射到一個高維乃至無窮維的特征空間中（Hilbert空間），使得在原來的樣本空間中非線性可分問題轉(zhuǎn)化為在特征空間中的線性可分問題。簡單地說，就是升維和線性化。升維，就是把樣本向高維空間做映射，一般情況下這會增加計(jì)算的復(fù)雜性，甚至?xí)稹熬S數(shù)災(zāi)難”，因而人們很少問津。但是作為分類、回歸等問題，很可能在低維樣本空間無法線性處理的樣本集，在高維特征空間中卻可以通過一個線性超平面實(shí)現(xiàn)線性劃分（或回歸）。一般的升維都會帶來計(jì)算的復(fù)雜化，SVM方法巧妙地解決了這個難題：應(yīng)用核函數(shù)的展開定理，就不需要知道非線性映射的顯式表達(dá)式；由于是在高維特征空間中建立線性學(xué)習(xí)機(jī)，所以與線性模型相比，不但幾乎不增加計(jì)算的復(fù)雜性，而且在某種程度上避免了“維數(shù)災(zāi)難”。這一切要?dú)w功于核函數(shù)的展開和計(jì)算理論。選擇不同的核函數(shù)，可以生成不同的SVM，常用的核函數(shù)有以下四種：·線性核函數(shù)K（x，y）=x·y?！ざ囗?xiàng)式核函數(shù)K（x，y）=[（x·y）+1]^d。·徑向基函數(shù)K（x，y）=exp（-|x-y|^2/d^2）?！ざ由窠?jīng)網(wǎng)絡(luò)核函數(shù)K（x，y）=tanh（a（x·y）+b）。示例：helloworld！支持向量機(jī)我們先演示支持向量機(jī)的基礎(chǔ)使用，完整演示代碼請見本書GitHub上的9-1.py。導(dǎo)入庫文件：print(doc)importnumpyasnpimportmatplotlib.pyplotaspltfromsklearnimportsvm創(chuàng)建40個隨機(jī)點(diǎn)：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()運(yùn)行代碼：localhost:codemaidou$python9-1.pyNonelocalhost:codemaidou$SVMhelloword代碼如圖9-9所示。圖9-9 SVMhelloword代碼示例：使用支持向量機(jī)算法識別XSS下面以常見的XSS檢測來說明下SVM的簡單應(yīng)用。完整演示代碼請見本書GitHub上的9-2.py。處理流程數(shù)據(jù)處理流程如圖9-10所示。圖9-10 數(shù)據(jù)處理流程數(shù)據(jù)搜集和數(shù)據(jù)清洗由于我們的例子比較簡單，把上述兩個步驟合并即可，準(zhǔn)備數(shù)量相等的正常Web訪問日志和XSS攻擊的Web日志，最簡單的方法是參考我以前的文章《基于WAVSEP的靶場搭建指南》，使用WVS等掃描器僅掃描XSS相關(guān)漏洞即可獲取XSS攻擊的Web日志。特征化實(shí)踐中數(shù)據(jù)搜集&數(shù)據(jù)清洗是最費(fèi)時間的，特征化是最燒腦的，因?yàn)槭澜缛f物是非常復(fù)雜的，具有很多屬性，然而機(jī)器學(xué)習(xí)通常只能理解數(shù)字向量，這個從現(xiàn)實(shí)世界的物體轉(zhuǎn)變成計(jì)算世界的數(shù)字的過程就是特征化，也叫向量化。比如要你特征化你前女友，你總不能說漂亮、溫柔這些詞，需要對最能代表她的特點(diǎn)的方面進(jìn)行數(shù)字化，如圖9-11所示。圖9-11 現(xiàn)實(shí)生活中將事物向量化的例子大，但是不足以干掉其他全部特征，所以我們還需要對特征進(jìn)行標(biāo)準(zhǔn)化，常見的方式為：·標(biāo)準(zhǔn)化；·均方差縮放；·去均值?；氐絏SS的問題上，我們需要針對Web日志進(jìn)行特征化，如圖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ù)標(biāo)準(zhǔn)化使用如下代碼即可：min_max_scaler=preprocessing.MinMaxScaler()x_min_max=min_max_scaler.fit_transform(x)數(shù)據(jù)打標(biāo)XSS標(biāo)記為1，正常訪問標(biāo)記為0。5.數(shù)據(jù)拆分這一步是為了隨機(jī)把數(shù)據(jù)區(qū)分成訓(xùn)練組和測試組，通常直接使用cross_validation.train_test_split即可，通常40%作為測試樣本，60%作為訓(xùn)練樣本，這個比例可以根據(jù)自己的需要進(jìn)行調(diào)節(jié)：x_train,x_test,y_train,y_test=cross_validation.train_test_split(x,y,test_size數(shù)據(jù)訓(xùn)練使用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")模型驗(yàn)證通過加載訓(xùn)練后的模型，針對測試集合進(jìn)行預(yù)測，將預(yù)測結(jié)果與打標(biāo)結(jié)果進(jìn)行比對：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萬個樣本的黑白模型上進(jìn)行訓(xùn)練，在一個各有5萬個樣本的黑白測試集上進(jìn)行校驗(yàn)，任何黑白預(yù)測錯都判斷為錯誤，最后運(yùn)行結(jié)果準(zhǔn)確率為80%，對于機(jī)器學(xué)習(xí)而言，僅依（比如大型CDN&云WAF集群的日志），進(jìn)一步增加特征個數(shù)以及增加后面環(huán)節(jié)的自動化或者半自動化的驗(yàn)證，可以進(jìn)一步提高這個比例，最后我們做到了準(zhǔn)確率90%以上。圖9-13是特征擴(kuò)展的舉例，大家可以根據(jù)實(shí)際情況增加個數(shù)。圖9-13 Web日志特征異常數(shù)據(jù)通過SVM我們識別出了異常數(shù)據(jù)，經(jīng)過人工確認(rèn)，除了變形的XSS以外，還有不少其他攻擊行為，由于測試時只打開了XSS的規(guī)則簽名，所以其他攻擊行為沒有攔截，也進(jìn)入了白樣本，舉例如下：/.|./.|./.|./.|./.|./.|./.|./.|./.|./.|./.|./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注入都是屬于代碼注入導(dǎo)致的漏洞。我們推測由于訓(xùn)練樣本中混入了SQL注入的樣本，所以導(dǎo)致訓(xùn)練結(jié)果中也出現(xiàn)了了SQL注入。網(wǎng)絡(luò)DGA家族僵尸網(wǎng)絡(luò)為了躲避域名黑名單，通常會使用DGA技術(shù)動態(tài)生成域名，通過DGA見的cryptolocker和post-tovar-goz兩個僵尸網(wǎng)絡(luò)家族為例，完整演示代碼請見本書GitHub上的9-3.py。數(shù)據(jù)搜集和數(shù)據(jù)清洗實(shí)驗(yàn)階段，我們搜集了如下數(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ù)學(xué)可以理解的語言，這使英文的元音字母比例會比較高。DGA的特征不明顯。下面我們通過數(shù)據(jù)分析來驗(yàn)證我們的想法。讀取alexa域名數(shù)據(jù)：x1_domain_list=load_alexa("../data/top-1000.csv")計(jì)算元音字母的比例：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)絡(luò)DGA域名數(shù)據(jù)以及alexa域名數(shù)據(jù)，并計(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ù)指的是域名中去掉重復(fù)的字母和數(shù)字后的個數(shù)，比如：·baidu的個數(shù)為5；個數(shù)為7；的個數(shù)為4。去重后的字母數(shù)字個數(shù)與域名長度的比例，從某種程度上反映了域名字符組成的統(tǒng)計(jì)特征。計(jì)算去重后的字母數(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)絡(luò)DGA域名數(shù)據(jù)以及alexa域名數(shù)據(jù)，并計(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計(jì)算的。計(jì)算兩個域名之間的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)計(jì)算兩個域名集合的平均jarccard系數(shù)的方法為：defget_jarccard