防火墙策略不一致性检测算法

24320075JournaloftheGraduateSchooloftheChineseAcademyofSciencesVol.24MayNo.32007*863(2003AA103710):10021175(2007)03037208*王卫平陈文惠李哲鹏陈华平(,230026)(200669;20061016)WangWP,ChenWH,LiZP,etal.Algorithmfordetectingfirewallpolicyinconsistency.JournaloftheGraduateSchooloftheChineseAcademyofSciences,2007,24(3):372~379安全管理员经常需要对防火墙策略进行比较,以找出其中不一致的地方.但是,这个比较平台的选择,令安全管理员煞费脑筋.为了进行防火墙策略的比较,首先给出了FPT(防火墙策略树)模型;其次给出了策略树的构造算法,该算法可以把一个防火墙策略转换为策略树;再次是策略树的比较算法;最后给出了防火墙策略的比较过程.这些算法的组合可以对防火墙策略进行比较,给出不同防火墙采用不同过滤决策的数据包集合,为安全管理员保证企业网络的安全提供了方便.另外,该模型还可以推广到大量的包分类系统当中,来进行策略的比较.防火墙,策略,比较,算法TN915081,,Internet.,.,.,,.,,,.,.,.,.,.,,,,,;,,,,,,.,.,m,,.2,.,.[1~4]3:,.(policytree),,(translationtree).[5],Trie,,.[6],,40,.,,.[7],?.[8],.,,.,,AlexLiu[9,10].(FDD),FDD,,.[10],FDD,Alex2,;,.[10],.([1~4]),,.[11~14].33.1,.,.,.,,,.3:().,1OrderF1F2Action11,34,6,7,8121,2,3,51,3,6036,72,7,80.,5:IP,IP,,.2:,;,.1,F1F2,[0,9],.,,1,,1,1,,,,.Microsoft!RInternetSecurityandAcceleration(ISA)Server2004,.ISA,,3733,:,.:,,,,,,,.,:[],.3.2P,n,R1,R2,∀,Rn.R,OrderFilterAction3,R[order],R[filter]R[action].R[order][1,+#),R[order]∃[1,+#).R[action]{Accept,Deny},R[action]∃{Accept,Deny}.R[filter]d(R[F1],R[F2],∀,R[Fd]).i,1%i%d,Fi,IP.R[Fi]D(Fi),D(Fi).,R[Fi]D(Fi),R[Fi]!D(Fi),.,R,:orderR[F1]&R[F2]&∀&R[Fd]∋(action)3.3Alex[9](FDD),,,.FDD,f,.FDD,f,.F1,F2,∀,Fdf6:(1).,..(2)fv,F(v),[9]:F(v)∃{F1,∀,Fd}v{accept,deny}v.(3)fe,I(e),ev,[9]:I(e)!D(F(v)).(4)f,,(v1e1∀vkekvk+1),v1,vk+1,eivivi+1.[9]:F(vi)(F(vj),i,j∃{1,∀,k},i(j,:2.(5)v2ee):I(e)∗I(e))=,e(e).(6),.(a).F1,F2,∀,Fd,,F1∀Fd,(v1e1∀vkekvk+1),:F(v1)∀F(v2)∀∀F(vk).(b).S1S2,S1S2S1S2.v,e1∀ekv,,:I(ei)I(ej),i,j∃{1,∀,k},ij.,(v1e1∀vkekvk+1)[9]:orderR[F1]&R[F2]&∀&R[Fd]∋F(vk+1),R[Fi]=I(ej)#j∃{1,∀,k},F(vj)=FiD(Fi)i,Fi∃{F1,∀,Fd}-{F(v1),∀,F(vk)},,(order).,P,f,37424p,Pf.f.4F1,F2,∀,FdP,n,R1,R2,∀,Rn.f,P,,p,Pf.,F1∀Fd.,fF1,2F2,∀∀,fd.f.R1,v1e1∀vdedvd+1,F(vi)=Fi,I(ei)=R1[Fi],i∃{1,∀,d},F(vd+1)=R1[action],R1.f,R2∀Rnf,Pf.R1∀Rjf,fv,ve1∀ek.Rj+1,2[10].,I=Rj+1[F1]-+ki=1I(ei),J=Rj+1[F1]-I,I=,v;I(,.X,Y,l(X,Y)={z|z∃X&{z}Y}.ei,1%i%k,I(I(ei)I,:l(I(ei),I)(,ei,e,eei,I(e)=l(I(ei),I),ei,e,I(ei)=I(ei)-l(I(ei),I);l(I,I(ei))(,eei,I(e)=l(I,I(ei)),I=I-l(I,I(ei)),,Rj+1[F2]&Rj+1[F3]&∀&Rj+1[Fd]∋Rj+1[action],,e.,I(,eek,I(e)=I,,Rj+1[F2]&Rj+1[F3]&∀&Rj+1[Fd]∋Rj+1[action],,e.,.,J(,ve1∀ek,JI(ei),1%i%k,3:(a)J∗I(ei)=.F1eip,Rj+1,,ei.(b)J∗I(ei)=I(ei).p,F1ei,Pj,Rj+1.,Rj+1[F2]&Rj+1[F3]&∀&Rj+1[Fd]∋Rj+1[action]ei[10].(c)J∗I(ei)=&J∗I(ei)=I(ei).ei2e)e,,I(e))=I(ei)-J,I(e,)1f=I(ei)∗J,ei2,e)e,,ei.I(e))I(e,),e)e,;I(e,)I(e)),e)e,,e,,(b).2,I(e))I(e,),e)e,,,,e,,(b).1,,1.5mf1,f2,∀,fm,F1,F2,∀,Fd,F1∀Fd.p:m3753,:,2fifj.pS,2.51(1)i,1%i%m,vifi,vik(i),ei1,ei2,∀,eik(i).I(ei)=+k(i)j=1I(eij),I(ei)fiF1,,F1I(ei),fi.mf1,f2,∀,fm,I=∗mi=1I(ei),IF1.,F1D(F1)-I,,S.(2)vi,1%i%mIeij,1%j%k(i),2:(a)I∗I(eij)=.F1eijpS,fieij.(b)I∗I(eij)(.I∗I(eij)(I(eij),eij,I(eij)=I∗I(eij),.(3)fi,1%i%m,fi,ei1,ei2,∀,eik(i)vi.,I(ei)=I(ej),1%i,j%m.J(ej)=∗mi=1I(eij),j.e11,e21,∀,em1,J(e1)I(ei1),1%i%m,2:(a)J(e1)=I(ei1).vi,ei2.(b)J(e1)∃I(ei1).ei12ee),e,I(e)=J(e1),I(e))=I(ej1)-J(ei),ei12,ee),ei1.e).,,.,,.(4),f1,f2,∀,fm,k,.,,.,mf1,f2,∀,fm,.52mf1,f2,∀,fm,.lij,1%i%m,1%j%kfij,k.j,1%j%k,lij,1%i%m,2:(a)x,y,1%x,y%m,lxj=lyj.p,l1j,.(b)#x,y,1%x,y%m,lxj(lyj.p,l1j,fxfy.,pS.,S,.12ff),,2,S.2f)2ff)OrderF1F214,6,8,91,2,3,4,5,6,7,8,9212,5,9311,3414,6,7,8522,4,5,7,8,91171,3,4,5,6,9376246,S.,S3OrderF1F211,4,5,6,8,91,2,3,4,5,6,7,8,922,31,2,3,4,5,7,8,9371,3,4,5,6,9.,S,S),S,,32.,.,.S,,deny.,f,.,.f2v1v2,,,2,.7mP1,P2,∀,Pm,,PiFi1,Fi2,∀,Fik(i),1%i%m,.(1)UU∀;(2)Pi,1%i%m,PiP)i,P)iU.F,F∃{U-{Fi1,Fi2,∀,Fik(i)}},P)iFD(F);(3)P)i,1%i%m,fi;(4)f1,f2,∀,fm.8,VisualBasic60,MicrosoftAccess.,;,m.m,mm.CPU2GHZRAM1GB,Windows.345.345+,.,5:IP,IP,,,.[12],[12],.3000,[12].3773,:3,3000,30s,.,,,.4,,m,,m8,7s,.,,.5,,8,3000,4min.,,3.,,4[12],,.,,.9,.,,;,;,;.,.,.,.1,,.,,,.[1]AlShaerES,HamedHH.Managementandtranslationoffilteringsecuritypolicies.In:IEEEICC)03.AnchorageAlaska:IEEE,2003.256~260[2]AlShaerES,HamedHH.Firewallpolicyadvisorforanomalydetectionandruleediting.In:ZuckermanD,IEEEIFIPIntegratedNetworkManagement.ColoradoSprings,Colorado:IEEE,2003.17~30[3]AlShaerES,HamedHH.Discoveryofpolicyanomaliesindistributedfirewalls.In:LiVOK.IEEEINFOCOM−04.HongKong:IEEE,2004.2605~2616[4]AlShaerES,HamedHH,BoutabaR,etal.Conflictclassificationandanalysisofdistributedfirewallpolicies.IEEEJournalonSelectedAreasinCommunications,2005,23(10):2069~2084[5]HariB,SuriS,ParulkarG.Detectingandresolvingpacketfilterconflicts.In:RomR.IEEEINFOCOM−2000.TelAviv,Israel:IEEE,2000.1203~1212[6]BaboescuF,VargheseG.Fastandscalableconflictdetectionforpacketclassifiers.In:CavalliA.Procofthe10thIEEEInternationalConferenceonNetworkProtocols.Paris:IEEE,2002.270~279[7]MayerA,WoolA,ZiskindE.Fang:afirewallanalysisengine.In:ProcofIEEESymposiumonSecurityandPrivacy.Berkeley:IEEE,2000.177~187[8]EronenP,ZittingJ.Anexpertsystemforanalyzingfirewallrules.In:NielsonHR.Procof6thNordicWorkshoponSecureITSystems.Denmark:Copenhagen,2001.100~107[9]GoudaMG,LiuXY.Firewalldesign:consistency,completenessandcompactness.In:Procofthe24thIEEEInternationalConferenceonDistributedCo