NMF-NAD：基于NMF的全网络流量异常检测方法

?33??4? 2012?4?

? ? ? ?

Journal on Communications

Vol.33 No. 4 April 2012

NMF-NAD???NMF??????????????

???ēч?ē???ē???

(???ˊ??? ??????┦??? ??210007)

? ??????????????? (NMF, non-negative matrix factorization) ????????? (NMF-NAD, NMF based network-wide traffic anomalies detection)???????????????????????????????????Shewhart????????????????????????????NMF-NAD???????????????ˊ????

?????????????????????????

Ё?????TP393 ??????A ?????1000-436X(2012)04-0054-08

NMF-NAD: detecting network-wide traffic anomaly based on NMF

WEI Xiang-lin, CHEN Ming, ZHANG Guo-min, HUANG Jian-jun

(Institute of Command Automation, PLA University of Science and Technology, Nanjing 210007, China)

Abstract: A non-negative matrix factorization (NMF) based network wide traffic anomalies detection (NMF-NAD) method was proposed. NMF-NAD firstly reconstructed the traffic matrix in the non-negative sub-space, and then detected the anomalies through Shewhart control chart based on the reconstruction error. Experimental results on both simulation and Abilene data show that NMF-NAD can achieve high detection accuracy with low complexity. KHy words: network traffic; anomaly detection; non-negative matrix factorization; continuous anomalies

1 ??

????????????????????????????????╠?????????????????????????????????????????????????????????????????????????????????????????????????????????????????(ISP)???▂L?г?????????LП??

?????????????????????????????????????[1]????????????▂????????????

???????????????????????ПЁ?????????????????????????????????????????▊??ˊ??▂??????????????????????????????

??????(?DDoS??????????)???????????????[2~4]??????Lakhina??[1,5]???????????(PCA, principal component analysis)???????????(network-wide)?????????????????????PCA???????????????????????????????????????????????????????

?????2011-06-22??????2011-12-09

??-????????????-??61070173, 61103225?????????????-??BK2009058, BK2010133? Foundation Items: The National Natural Science Foundation of China (61070173, 61103225); The Natural Science Foundation of Jiangsu Province (BK2009058, BK2010133)

?4? ?????NMF-NAD???NMF???????????? g55g

???+??????????????PCA???????????PCA?????L????????Ё????????????????

????????????Н▂???????

PCA?????????????????????д??????????????????????????????????[6,7]????PCA?ˊ????????????????????(NMF, non-negative matrix factorization)????????????NMF-NAD (NMF based network wide traffic anomalies detection method)?NMF-NAD?????????????????Ё???????????????????????????????????????????????????????????????Shewhart??????????????????????NMF????????????:??????????????

???????????2????????

?3???NMF-NAD???

?4????????NMF-NAD????????5??????

2 ????

?????????????????????????????????????????????????????????????????????????????PCA?????????????Lakhina?????????????????????П???????????????PCA???????[1,5]????????????????????????????Q????????????????????????????????????????????????

?????????[8,9]????┉??????PCA?????2?????L????PCA?????????????????????????????????PCA??????????????????????????????????????????????????3??????????????????????????????????????????г??????????????????┑???????┑??

????????????????????PCA??????????????????∵?PCA????????????????Н???????????????????????PCA?????????Ё???????????????┑??????2???г?????PCA?┑???????????[10,11]?

????????????????????PCA(MSPCA, multiscale PCA)[12]??????????PCA??П???????????????┨??Ё????????????????????????????????PCA?????????????????Q??????????????????????????????MSPCA???PCA????????????????????????????????????????????????????????MSPCA????????????????????????

??[13]?????????????????????????PCA???????????[14]????????PCA??????Tarem?????[7]??PCA????????????????????????????????????????????┉???????????8????????????????????????????????????????????????????

3 ???????NMF-NAD??

?????Н?????????????NMF????????????PCA?????????????NMF??????????NMF-NAD????????????? 3.1 ???????????

??????????????????????????????????????[8]?????????????????????????????????????????????⑤IP??y??????????????????Н????X???d×p?????Ё?d??????????p????????[8]?Xij????i???????j????????????????

g56g ? ? ? ? ?33?

??????X=[X1,X2,?,Xp]??Ё?Xi??i?????????????Xi?Rd?d?????????NMF?????X???2???U?Rd×r?V?Rr×p?X?UV???????????

U∈Rdmin×X,UV) (1)

+r,V∈Rr×p

D(+

?Ё?Rd×rRr×p

+??+???????d×r?r×p?????▊??D(X,U,V)?????X?UV

????????????????????[15]?

D(X,UV)=X?UV2

F

(2)

?Ё?2

F?????2???

?Н?????П???М?(2)???????????????????L?

T

D(X,UV)=tr((X?UV)(X?UV))=tr(XXT

)?2tr(XVT

UT

)+tr(UVVT

UT

)

(3)

?(3)?????????????L????????V???????Lagrange multiplier??????U=[uij]?V=[vij]??αij?βij?????└???uij?0?vij?0?LagrangeЬ??????α=[αij], β=[βij]??М??????L???(4)???

L=D(X,UV)+tr(αUT)+tr(βVT) (4)

?L??U?V?????(5)???

???L?=?XVT+UVVT

+α?

?U

(5)

??L???V

=?XTU+VTUTU+β??Kuhn-Tucker??αijuij =0?βijvij =0???

?(6)?

???(XVT

)T

ijuij?(UVV)ijuij=0

??(XTU)(VTUT

U) ijvij?ijvij=0

(6)

?????(7)????????

?? ?

u(XVT)ij

ij←uij

?(UVVT)ij(7)

?

(XT

U ?v)ij?

ij

←vij(VTUTU)ij

3.2 ??NMF??????????

??NMF??????????????3??????????????????????????

3.2.1 ???Ш???

????????X??i????????

?????????d?????????????????????????????r?r<<d?

???????

???r?????????NMF??????????X??NMFП?????U=[U1,U2,?,Ur]????????r????????????Ё????????????╓?????????????V=[V1,V2,?,Vp]????XЁ??????r???????????????[15]Ё??????r???????????

??NMF?????????????PCA????????[15,16]?2?????????NMF???????????L??????????????????┑????????????????PCA???????????????????????????????????????????NMF?????????????????????????П??????????????П?????????“?????????????????????”?????????PCA?????Ё??????????????????????????????????

3.2.2 ??????

???r?????????????r???

???????????????X

?=[U1,U2,L,Ur] [V1,V2,L,Vp]?

???X%=X?X????????Ё???????????????????????

????Ё???????????????

???????????????? 3.2.3 ??????Ш

???i?????????Xi=(Xi1,Xi2,?,

Xip)???NMFП??????Xi≈X

?i+X%i??Ё?X

?i?X%i??????X??X%??i????X

?i?X%i???XiЁ??????(??)??????????i??????????????

Xi?????????X

%iЁ?????X%Ё????????????????????????

?????????????????X

%Ё???????????????

????????????????????

?4? ?????NMF-NAD???NMF???????????? g57g

??????????????????????

???????X

%Ё???????П??????????????П??????????Shewhart???[17]???????????????????????????????????????????????????????????????????

Shewhart????ˊ????Ё??└?ˊ[17]????????????????????????????µ????σ?????????????└?????└???????????????????????????????-?????(-R???)?

??d???X%i,i=1,2,L,d?????????N(µ,σ2)?????????p???????i?????????Ri???d?????

?????=∑Ri/d?

?µ?σ????????1?α???

?

???µ?u?1?α/2µ+u?

1?α/2Ё???┉??Ё?µ1?α/2????3?г????Ё?3σ??????Ё??└?ˊ????????????Shewhart

?????????????????????????????????????А└?????(8)~?(10)?

CL=E(R)= (8)

UCL=E(R)+µ1?α/

=??1+µd3?

(9)

?

1?α/2d?2?LCL=E(R)?µ1?α/

=??1?µd3?

(10)

?

1?α/2d??2?Ё?d3/d2?????????????d2?

d3?????????????[17]???UCL??LCL??????????????UCL????LCL??М??????????????????????????????????? 3.3 NMF-NAD???? 3.3.1 NMF-NAD??

?????????????NMF???

???????NMF-NAD?????????????1) ???????X???????

????????X

?????1Ё??1??2????2) ????????X

%=X?X?????1Ё??3????3) ??Shewhart??????????????????1Ё??4??9????

??1 NMF-NAD

???X //?????? ???ATS(anomalies time period set) //??????????▊?

1) [U V] ← NMF(X, r, k) //U?????????V??????r????????k??????

2) X?=UV 3) X

%=X?X? 4) [residual, UCL, LCL] = Shewhart (X

%)//????└

5) for i = 1; i < d; i++

6) if R(i) > UCL or R(i) < LCL then //R(i)??i????

7) add i to ATS 8) end if 9) end for 3.3.2 ???????

NMF-NAD????????????2????NMF???????????????NMF???????O(pdkr)??Ё?k???????r????????d?????????p???????????????????????O(d)???NMF-NAD?????????

O(pdkr)???П??PCA???????O(dp2)[15]?

k?r??┉??Ё????????????NMF-NAD??┉?ˊ?????PCA????ˊ????

4 ???????

NMF-NAD???????????????????????2?????????PCA[16]??MSPCA[12]??????????3?????????????NMF-NAD????????????????????????????????????????3???????????

g58g ? ? ? ? ?33?

???????????NMF-NAD????┉????Ё????????????????????????????????????????????????????2????????????????Н?????????Ё?????????????Н???????Ё??????????

4.1 ???????? 4.1.1 ??????

???????3?????[18]???????????????????????????3?????????????????Ё?????(?X???)??????????????

?????(?????7??

5??3??24h?12h?6h?3h?1.5h????)?????????????[16]?????????????1(a)?????????????????????????????????????1(b)?????????????????????1(c)????Ё????Ё?????????????????121???????????X??Ё??????2 010??????

?1 ??????????

?????4????????[19]?┃??

(alpha)???

???????????(DoS, DDoS)???(flash crowd)???/????(ingress/egress shift)???┃?????????П??????????????????????????⑤??⑤?????????????????????????????????Web?????E?

?????/??????BGP?Щ?????????????

??????4???????4???????[19]?????????????⑤-??????????????????????????????????????5?30min?┃???????????????????/????????????????????BGP?Щ???????????????2????????????????????????Ё?????Ь???Ь???????????????Ё???????????-?⑤-?????????????????????????┃???????????⑤?????????/????????????2?⑤??2???????????????⑤??????????????????????????┃??????????????????????????????????????????????????????????????????????/???????????????????????????????(?????????????)????????

???Ё????П??╘?5min????????????300??????800????????╘50????????┃???????┃??????30min(??6????)???1 000???1 500???????╘50???????????????????????????????30min(??6????)???1 700??1 800?????????????/???????(??100????)???????????????????????????? 4.1.2 ??????

3??????????????2????

Ё????????????????????????????Ё???????? (SSE, square sum of the elements of the residual traffic)?

??PCA???????Q???????????

1h0

δ2

φα=φ2h0(h0?1)?1?+1+

2? (11)

?1φ1??