基于熵估计的网络流量异常检测研究

华中科技大学硕士学位论文基于熵估计的网络流量异常检测研究姓名：朱建申请学位级别：硕士专业：软件工程指导教师：沈刚20070506IInternetTCP/IPAMSAMSDARPAIPAMS,,AMS,IIAbstractBecauseofitsopenness,natureofresourcesharingandincreasinginterconnectivity,inparticular,theemergenceoftheInternet,networkisgettingmoreimportantinallaspectsofpeople’ssociallives.Itisreportedthatvariousnetworkattackshavemadeseriousdamagesrecently.Withoutbuilt-inprotectionmechanismsinTCP/IPprotocols,thenetworkedcomputersareexposedtoallkindsofnetworkattacks.Asaneffectivenetworkinformationprotectionmeasure,IntrusionDetectionSystems(IDS)becomeanimportanttoolprotectingnetworkresourcesfrombeingabused.AnIDSusinglittleresources,abletodetectunknownattacksispromisinginthemarket.Thisthesisdiscussestheapplicationofnetworkinformationentropyindetectingnetworktrafficanomalybasedontheanalysisofattackcharacteristics.Ahybridalgorithmisintroducedtoestimatetheentropyofstreamdata,asanextensionofAlon-Matia-Szegedyalgorithm.Thishybridalgorithmseparatesthehigh-frequencyitemsandthelow-frequencyitemsinadatastreamandcalculatetheircontributionstothestreamentropyrespectively,givingamoreaccurateestimateofentropythanAMSalgorithm.TheexperimentsaredesignedwiththeDARPAdatasetfromMITLincolnLabs.Then,networkinformationentropyisevaluatedusingtheuniformrandomsampling,AMSalgorithmandtheproposedhybridalgorithmrespectively.Theeffectivenessoftheproposedalgorithmisverifiedbytheexperimentresults.Keywords:IntrusionDetectionSystem,InformationEntropy,AMSAlgorithm,NetworkSecurity□_____□“”111.1204070Internet[1]TCP/IP[2]1-1[3]TCP/IPInternet21-119886000,960019993,12200051002001726200112Sql20031,,26[4]1.2[5]SnortBroOC1923[6][7][8][9]1.3IP[10]IPIPIPIPIP4CiscoNetFlow[11][12]Alon,MatiasSzegedy[13][14]Hybrid1.4AMSDARPA522.12.1.13[15]X2.1.2TCP/IP[16]1.TCP2.3.4.2.1.36[17][18]1.2.1SRI2TIM33.72.1.4[19]1.“”2.81.CIDFCIDF2.WebLotusNotes3.4.PKIXSET5.IPTCP92.22.2.1BoltzmannH=kBln[20]BkBoltzmann123BoltzmannpiPi=1/(i=1,2,)iiiBPPkHln1∑Ω=−=[21](2.1)Boltzmann[22]2.2.21948C.E.ShannonBoltzmann[23]An()a1,a2anP1P2P3Pn()1,,...,2,1101==≤≤∑=niiiPniPAShannon()()∑=−==niiinnPPkPPPHAH121ln,...,,(2.2)AkHn0HnShannonShannon[24]APi=110Hn=0Pi(Pi=1/ni=1,2,3,n)Hn)ln()(maxnkHn=2-1–plog(p)2-1p=1/e-plog(p)[25]2.2.3X={x1,x2,…,xm}mmXnIPH(X)11H(X)=∑=−niiimmmm1)log((2.3)miiin=mn=1IP0IPsynfloodudpfloodicmpfloodIP2.3[26]2.3.110001001/10[27]Pmm*p122.3.21.mm2-3H(X)=∑=−niiimmmm1)log()log()(maxmXH=Pm*pH(PX)max=log(p*m)m12.(1-P)*n2.4AMSAlonMatiasSzegedy[28]AlonMatiasSzegedyAMS2.4.1AlonMatiasSzegedyFkFk11≥k0λ0ε),...,(1maaA={}nN,...,2,1=()()+−mnnkOklglg1lg112λεYkFλYkFε[13]1321118λkkns−=()ε1lg22=sm2s2,...,1sYYYiY1s11:sjXij≤≤ijXijXX=()mnOlglg+Apap1,2,…,m{}().,...,2,1nNlap=∈={}()1,:≥=≥=lapqqrqrAlpa()()kkrrmX1−−=Xlgnlap=lgmlX()EX()()()()()()()()()()()()()11221121...1121...1...121...1kkkkkkkkkkkkkkknnnkikimEXmmmmmmmmF==+−++−−++−++−−+++−++−−==∑X22()()(())VarXEXEX=−(2.4)2()EX()()()()()()()()()222221122222222()121...1121...1...121...1kkkkkkkkkkkkkkknnEXmmmmmmmm=+−++−−++−++−−+++−++−−14()(()()()(2111212111111221...121kkkkkkkkkkkmkkkmmmkk−−−−−≤+−++−−++−()())()(()())12222111212121211221121...1...21...1...kkkkkkkkkknnnkkknkkkmmmkkkmmmmkmkmkmkmFkFF−−−−−−−−−++−−+++−++−−≤+++==0ab()()12211...()kkkkkkkababaababbabka−−−−−−=−++++≤−(2.5)n12,...,nmmm21121111nnkkkkiiiiiimmnm−−===≤∑∑∑(2.6)112,...1knmnmm====1maxiniMm≤≤=kkkiiMm≤∑152111111(1)11121111211111111nnnnkkkiiiiiiiiknnnkkkiiiiiiknnkkiiiiknnkkkkkiiiinkkiimmmMmmmmmmnmmnm−−====−===−==−−==−=≤≤=≤=∑∑∑∑∑∑∑∑∑∑∑∑2111ninkikiimmn==≤∑∑(2.7)iY()1122112111()kikkVarYEXskFFsknFs−−≤≤≤()()ikEYEXF==1si()112222211Pr8kikikkkkVarYknFobYFFFsFλλλ−−≤≤≤(2.8)kFiYkFλ18A[29]kFλ22siYkFεiYm1=mlaX161a1,1==rmm21a2a0.5r1−mlarmalam1r1alamalr1rXij()mnOlglg+mn[30]XijrXij()()λ1lglglg+mOallgn()++−λλε1lglglglg1lg112mnnkOk2.4.2IPsynfloodudpfloodicmpflood[31]IPIPIPAMSAMS2.4.3AMS()11()(loglog)1000()iiiiirrrrHXHXmedianmmmmm−−∆=−−=×1irm−=01711logiirrmm−−=01.m10002.1000100iP[1,100]i∈3.iir4.()iHX∆5.100()iHX∆10()iHX∆jM[1,10]j∈6.10jM()medianm7.()1000()HXmedianm=×Hybrid2.5AMSHybrid1833.1Lallelephantmice[12]Lall2AlonMatiaSzegedy[32][11]MisraGriespmaxAlonMatiaSzegedyAlonMatiaSzegedyAlonMatiaSzegedyAlonMatiaSzegedys(s0)pp’|p’–p|δ1/eH’=H19σp+σ(0,1](p+δ)log(p+δ)–plogplog(1+σ/p)σ00σ≤00(p+σ)log(p+σ)–plogp|(p+σ)log(p+σ)–plogp|≤max(|(p+δ)log(p+δ)–plogp||(p-δ)log(p-δ)–plogp|)max(|δlogδ|,|(1-δ)log(1-δ)|)δ1/e|δlogδ||(1-δ)log(1-δ)||(p+δ)log(p+δ)–plogp||δlogδ|p≥sn≤1/ssppppppppppppXHXHiiiiniiiniiiniiiniii/log|'log''log'||)'log'log(||'log'log||)(')(|1111δδ−≤−=−=−∑∑∑∑====(3.1)s(s1/e)O((λ-2log(1/η)logsm)/log(1/s))(λ,η)X={xj|1≤j≤m}pis,nxmismxiri=|{j|xj=xi,i≤jm}|,f(r)=-(rlogmr–(r–1)logmr1−)(3.2).[1,m]iP(i=j|1≤j≤m)=1/m,,)(log1]}01[log...]2log)2(1log)1[(]1log)1(log[{1)]([1)(1)())((111111∑∑∑∑∑∑=======−=−++−−−−−+−−−−====njjjjjjjjjjjnjmiinjmiimiiixHmmmmmmmmmmmmmmmmmmrfmrfmrfPrfEj(3.3)imismlogm≥H(x)log1/s.1km/e2-1logk–log20(k-1)0,mkkmkk1log)1(log−−−0log(k