CS 636 Internetworking CS#636#Internetworking#ROUTER#ALGORITHMICS#Lecture#19#String#Searches#1Intrusion#DetecBon#Systems#• Intrusion#detecBon#systems,#IDSes#must#be#capable#of#disBnguishing#between#normal#and#abnormal#user#acBviBes#• Broad#Categories#– String#or#PaNern#Matching#– Behavioral#Anomaly#DetecBon#2 CS 636 InternetworkingSignature#matching#• Used#in#intrusion#prevenBon/detecBon,#applicaBon#classificaBon,#load#balancing#• Guard:#a#byte#string#or#a#regular#expression#• AcBon:#drop#packet,#log#alert,#set#priority,#direct#to#specific#server#• Input:#byte#string#from#the#payload#of#packet(s)#– Hence#the#name#“deep#packet#inspecBon”#• Output:#the#posiBons#at#which#various#signatures#match#or#the#idenBfier#of#the#“highest#priority”#signature#that#matches#• Size#of#problem:#hundreds#of#signatures#per#protocol#3 CS 636 InternetworkingString#matching#• Most#widely#used#early#form#of#deep#packet#inspecBon,#but#the#more#expressive#regular#expressions#have##superceded#strings#by#now#– SBll#used#as#pre‐filter#to#more#expensive#matching#operaBons#by#popular#open#source#IDS/IPS#Snort##• Matching#mulBple#strings#a#well‐studied#problem#– A.#Aho,#M.#Corasick.#“Efficient#string#matching:#An#aid#to#bibliographic#search”,#CommunicaBons#of#the#ACM,#June#1975#– GeneralizaBon#of#Knuth‐Morris‐PraN#algorithm#for#finding#the#occurrence#of#one#word#within#a#given#text#string#– Snort#uses#opBmized#Aho‐Corasick#implementaBon#– Matching#Bme#independent#of#number#of#strings,#memory#requirements#proporBonal#to#sum#of#their#sizes#4 CS 636 InternetworkingSingle#string#search#• Knuth#Morris#PraN#algorithm##• Boyer‐Moore#algorithm#• Searches#for#the#occurrence#of#a#word#w#within#string#S#5 CS 636 InternetworkingKnuth‐Morris‐PraN#• KMP#algorithm.###[over#binary#alphabet]###– Build#DFA#from#paNern.#3 4 a a 5 6 a 0 1 a a 2 b b b b b b a a a b a a a a a a b a a Search Text b a a a b accept state 6 CS 636 InternetworkingKnuth‐Morris‐PraN#• KMP#algorithm.###[over#binary#alphabet]###– Build#DFA#from#paNern.#3 4 a a 5 6 a 0 1 a a 2 b b b b b b a accept state a a b a a a a a a b a a Search Text b a a a b 7 CS 636 InternetworkingKnuth‐Morris‐PraN#• KMP#algorithm.###[over#binary#alphabet]###– Build#DFA#from#paNern.#3 4 a a 5 6 a 0 1 a a 2 b b b b b b a accept state a a b a a a a a a b a a Search Text b a a a b 8 CS 636 InternetworkingKnuth‐Morris‐PraN#• KMP#algorithm.###[over#binary#alphabet]###– Build#DFA#from#paNern.#3 4 a a 5 6 a 0 1 a a 2 b b b b b b a accept state a a b a a a a a a b a a Search Text b a a a b a a b a a a 9 CS 636 InternetworkingKnuth‐Morris‐PraN#• KMP#algorithm.###[over#binary#alphabet]###– Build#DFA#from#paNern.#3 4 a a 5 6 a 0 1 a a 2 b b b b b b a accept state a a b a a a a a a b a a Search Text b a a a b a a b a a a 10 CS 636 InternetworkingKnuth‐Morris‐PraN#• KMP#algorithm.###[over#binary#alphabet]###– Build#DFA#from#paNern.#3 4 a a 5 6 a 0 1 a a 2 b b b b b b a accept state a a b a a a a a a b a a Search Text b a a a b a a b a a a 11 CS 636 InternetworkingKnuth‐Morris‐PraN#• KMP#algorithm.###[over#binary#alphabet]###– Build#DFA#from#paNern.#3 4 a a 5 6 a 0 1 a a 2 b b b b b b a accept state a a b a a a a a a b a a Search Text b a a a b a a b a a a 12 CS 636 InternetworkingKnuth‐Morris‐PraN#• KMP#algorithm.###[over#binary#alphabet]###– Build#DFA#from#paNern.#3 4 a a 5 6 a 0 1 a a 2 b b b b b b a accept state a a b a a a a a a b a a Search Text b a a a b a a b a a a a a b a a a 13 CS 636 InternetworkingKnuth‐Morris‐PraN#• KMP#algorithm.###[over#binary#alphabet]###– Build#DFA#from#paNern.#3 4 a a 5 6 a 0 1 a a 2 b b b b b b a accept state a a b a a a a a a b a a Search Text b a a a b a a b a a a a a b a a a 14 CS 636 InternetworkingKnuth‐Morris‐PraN#• KMP#algorithm.###[over#binary#alphabet]###– Build#DFA#from#paNern.#3 4 a a 5 6 a 0 1 a a 2 b b b b b b a accept state a a b a a a a a a b a a Search Text b a a a b a a b a a a a a b a a a 15 CS 636 InternetworkingKnuth‐Morris‐PraN#• KMP#algorithm.###[over#binary#alphabet]###– Build#DFA#from#paNern.#3 4 a a 5 6 a 0 1 a a 2 b b b b b b a accept state a a b a a a a a a b a a Search Text b a a a b a a b a a a a a b a a a 16 CS 636 InternetworkingKnuth‐Morris‐PraN#• KMP#algorithm.###[over#binary#alphabet]###– Build#DFA#from#paNern.#3 4 a a 5 6 a 0 1 a a 2 b b b b b b a accept state a a b a a a a a a b a a Search Text b a a a b a a b a a a a a b a a a 17 CS 636 InternetworkingString#Search#Problem#DefiniBon#• Input#– P,#a#set#of#z#paNerns#{P1,#…,#Pz}#(total#length#n)#– text#T,#length#m#within#which#to#look#for#paNerns#• Task#– Output#locaBon#of#all#occurrences#of#each#paNern#Pi#in#T#• Bounds#– O(n+zm)#bound#using#exact#string#matching#algorithms#– Goal:#O(n+m+k)#bound#where#k#is#the#number#of#occurrences#of#some#paNern#Pi#in#T#18 CS 636 InternetworkingKeyword#Tree#• P#=#{poet,#pope,#popo,#too}#p o e t 1 p e 2 o 3 t o o 4 19 CS 636 InternetworkingObser vaBons#• Keyword#tree#K#construcBon#– Can#be#done#in#O(n)#Bme#• remember#n#is#total#length#of#all#paNerns#• Naïve#search#algorithm#with#keyword#tree#K#– Align#tree#to#each#posiBon#in#T#and#see#if#there#is#a#match#– O(nm)#Bme#• Can#we#do#beNer#?#20 CS 636 InternetworkingFailure#funcBons#• Temporar y#assumpBon#– no#paNern#in#P#is#a#proper#substring#of#another#paNern#in#P#• DefiniBons#– For#each#node#v#of#K,#L(v)#denotes#the#concatenaBon#of#the#characters#from#the#root#to#node#v#– For#any#node#v#of#K,#define#lp(v)#to#be#the#length#of#the#longest#proper#suffix#of#L(v)#that#is#a#prefix#of#some#paNern#in#P#– For#a#node#v#of#K,#let#f(v)#denote#the#unique#node#in#K#with#the#suffix#of#L(v)#of#length#lp(v)#• Note,#f(v)#=#the#root#of#K#if#lp(v)#=#0.#– Directed#edge#(v,#f(v))#is#a#failure#link#21 CS 636 InternetworkingKeyword#Tree#and#failure#links#• P#=#{poet,#pope,#popo,#too}#p o e t 1 p e 2 o 3