HashFunctionsforNetworkApplications (ll)YaxuanQiNSLab,RIITTsinghua UniversityNetworkSecurityLab,RlTResearchSeminaronReconfigurableHardwareTsinghua Universityhttp://www.arl.wustl.edu/-lockwood/class/cs6812/
Hash Functions for Network Applications (II) Yaxuan Qi NSLab, RIIT Tsinghua University
OutlineConcept and Theory (1~2)HashfunctionsBloomFiltersApplications(3~4)Netvork SecmityLab,RIITTsinghua University
Outline ◼ Concept and Theory (1~2) ◼ Hash functions ◼ Bloom Filters ◼ Applications (3~4)
Basic IdeaQuerying a data base formembershipGivenadatabaseof nmessagesfind out if amessagexbelongstothedatabaseBloomfiltergivesoneoftheBloomfollowinganswersFilterxNo / May beNo,xdoesnotbelongtothedatabaseofnmessages(100%confidence)x may belong to the data base of nmessages(ambiguity)
Basic Idea
TechniqueM-bitvectorM-bitvectorH,(y)H.(H(x)H(y).HashingHashing0=>NoH(x)H,(yXy1=>MaybeH,(y)ProgrammingBloomfilterGivenamessagex,obtainkaddressesbyperformingkhashfunctionsonxSetthebitateachaddressinam-bit longvectorDothe sameforeachof the nmessagesQueryingBloomfilterGivenamessagey,obtaink addressesbyperformingthesamekhashfunctionsonyReadthebitateachaddressfromthesameM-bitlongvectorANDallthekbitsreadO =>themessage notin thedata baseIf itwasthenallthebitswouldbedefinitelyset1=>the messagemay"be in thedata base"Maybe'becausethebitscouldhavebeensetbysomeothermessagestoo
Technique
n:number ofmessagesp(y是fp）=p(y不属于X)*p(y对应的k个bits都是1）m:numberofbloombits=p(y对应的k个bits都是1）k:numberofhashfunctions考虑对y对应的特定的k个bits，都被set（由X引起）的概率FalsePositive首先考虑1个指定bit被set（由X引起）的概率..Theprobability that a hashfunction sets a bit at a random address Ais1/mThe probabilitythat ahashfunctiondoes not setthebit ataddressA is1-1/mThe probability that the k successive hash functions generated foramessage don't set the bit at address A is(1 - 1/m)kSinceeachofthenmessagesgenerateskhashfunctions,theprobabilitthat thebit at addressAisnot set by any ofthesehashfunctions is(1 - 1/m)nk = ekn/mTheprobabilitythatthebit issetbysomemessageis1- ekn/mThe probability that k such bits generated by hash functions ona singlemessageareall setis[1 - ekn/mjk = probability of false positive
False Positive n: number of messages m: number of bloom bits k: number of hash functions p(y是fp ) = p(y不属于X)*p(y对应的k个bits都是1) = p(y对应的k个bits都是1) 考虑对y对应的特定的k个bits, 都被set(由X引起)的概率 首先考虑1个指定bit被set(由X引起)的概率