# INTRODUCTION

s the usage of portable devices continues to increase, more and more user applications catering to these device platforms are being developed. Also more often than not such devices are connected to one or more communications networks and must process a significant amount of incoming data. It is therefore becoming increasingly essential to secure these devices from malware of all kinds. The traditional approach for solving this problem on desktop computers is to provide for specialized antivirus software, firewall software and more recently antispyware software etc. However as opposed to a desktop computer the limited amount of computational power packed into a small footprint portable device precludes the use of resource intensive security software. It is therefore necessary to provide for alternate means to perform these functions on a small footprint device. Central to the ability to detect a malicious piece of code, a malicious packet in a data stream etc. is the ability to quickly determine if a given string of tokens belongs to a dictionary of known signatures. If we think of this dictionary of known signatures as a set, we have essentially reduced the problem of detecting malware to a problem of resolving set membership [1]. In this paper we give a recent survey on different types of bloom filter used for network Intrusion Detection system to benefit the research community to analyze and develop an efficient Bloom Filter which can have a prominent role in Network security, each having its own merits and demerits. The details of standard Bloom filter, pipelined Bloom filter, parallel processing bloom filter, counting Bloom filter is explained below. This paper also present the hardware architectures for the implementation of different Bloom filters. A Bloom Filter is a data structure that stores a given set of signatures by computing multiple hash functions on each member of the set and testing strings for membership of that set [3]. It acts as hardware antivirus device and connected with the CPU to remove the malicious input data. It consists of a set of hash functions, a hash function buffer to store hash results temporarily, a look up array to signify hash values and a decision component made of an AND to test the membership of testing string as shown in Fig. 1. 


# STANDARD BLOOM FILTER ARCHITECTURE

Standard Bloom filter is an important and widely used tool for supporting efficient query services in networking because of its ability to represent a set of items by using a bit array with several independent hash function [6].Bloom filter provide an effective tool for saving the space when space is at a premium. For pattern matching Bloom filters are used. They are hashed based structures which have a certain degree of accuracy for considerable savings in memory. Two basic operations are defined for Bloom Filter. First is programming for programming the look up array using hash functions of strings in data set and second is testing for checking the membership of test string [2].  A class of universal hash functions described here found to be suitable for hardware implementation. Following is a description of how this hash matrix is calculated [2,3,7].
Given dataset of inputs X= {X 1 , X 2 , X 3 ???X n } Each input is of b bits X j = {x 1 , x 2 , x 3 ????x b } ith hash function over string Xj is given in eqn. (2.1) 1 1 2 2
(X ) . ^. ^...................^.
i j i i i b b H d x d x d x (2.1)
H i (X j ) is the ith hash function of jth input string of input set ij d is a random coefficient ranging 1 to m j x 's are the bits in particular input string Where '.' is a bitwise AND operator, i.e.   


# PIPELINED BLOOM FILTER

In some application such as network intrusion detection due to very low rate of malicious traffic there is no need to compute all the hash functions to get a result of non membership. To exploit this pipelined architecture is intruduced. Pipelined architecture of bloom filter consists of several group of hash function that are utilized in different stages.The first stage always compute the hash values. The second and further stages are used only if there is a match in the previous stage [3].


# Advantage of Pipelined Bloom Filter

The advantage of using a pipelined Bloom filter is if the first stage pruduces a mismatch there is no need to use the second satge in order to decide whether the input string is a member of signature set because a bloom filter never pruduces a false nagatives. This saves the power consumed by pipelined bloom filter as compared to the standard bloom filter.


# Draw Back of pipelined Bloom filter

Power saving ratio diminishes when there are high no of matches in the first stage and second stage is utilized more.To remove this problem we use fully pipelined architecture of Bloom filter [4].  Pipelined architecture of bloom filter minimizes the false positive probability because first stage utilize more no of hash function increases the probability of mismatch thus second stage is not utilized but more no of hash function consume the more power which becomes the drawback of this architecture. Hence fully pipelined architecture remove this drawback as each of its stage has only one hash function. Fully pipelined architecture has the same no of hash function as the regular bloom filter hence its false positive probability is same as the regular bloom filter [3].


# IV. PARALLEL PROCESSING ARCHITECTURE

A standard bloom filter architecture can effectively represent the items with a single attribute but it cannot support the representation and querying of  


# COUNTING BLOOM FILTER

One property of Bloom filter is that it is not possible to delete a member stored into the filter. Deleting a particular entry requires that the corresponding k hashed bits in the bit vector be set to zero. This could disturb other members programmed into the filter which hash to any of these bits. In order to solve this problem, the idea of the Counting Bloom Filters was proposed in. A Counting Bloom filter maintains a vector to counters corresponding to each bit in the bit-vector. Whenever a member is added to or deleted from the filter, the counters corresponding to the k hash values are incremented or decremented respectively. When a counter changes from 0 to 1, the corresponding bit in the bit-vector is cleared. It is important to note that the counters are changed only during addition and deletion of strings in a Bloom filter. For applications like network intrusion detection, these updates are relatively less frequent than the actual query process itself [6]. Architecture of counting bloom filter is shown in fig. 7 Fig. 7 : Counting Bloom Filter


# VI. CONCLUSION

A Bloom Filter can be used in variety of Network applications. Different architectures of Bloom filter have been described in terms of merits and demerits. Pipelined architecture of bloom filter minimizes the false positive probability because first stage utilize more number of hash function increases the probability of mismatch thus second stage is not utilized but more number of hash function consume the more power which becomes the drawback of this architecture. Hence fully pipelined architecture remove this drawback as each of its stage has only one hash function.counting bloom filter remove the problem of deleting a member stored in filter.
1![Fig.1 : Block Diagram](image-2.png "Fig. 1 :")
2![Fig. 2. The random number describing hash function value indicates a bit location in m-bit look up array, Author : Department of Electronics & Communication Engineering, Indra Gandhi Institute of Technology, IPU, Delhi. E-mail : Chhabra_ritu2006@yahoo.co.in](image-3.png "Fig. 2 .")
2![Fig. 2 : Programming of m-bit array in Bloom Filter](image-4.png "Fig. 2 :")
![is a bitwise XOR operator.Note that the hash value can be out of the range [0 . . . m 1] if m is not a power of 2. Hence, m must be a power of 2. Computation of a hash function is shown in Fig.3](image-5.png "")
3![Fig. 3 : Computation of Hash Function](image-6.png "Fig. 3 :")
4![Fig.4 : Testing in Bloom Filter](image-7.png "Fig. 4 :")
![a) Fully Pipelined Architecture of Bloom Filter In fully pipelined Architecture number of stages equals to the number of hash functions .Each stage has only one hash function. Programming Phase is same as in case of regular Bloom Filter. In query phase, test string is progressed to next stage only when a previous hash function produces a match. Fully pipelined architecture of bloom filter is shown in fig 5.](image-8.png "")
5![Fig.5 : Fully pipelined architecture of bloom Filter](image-9.png "Fig. 5 :")
![that have multiple attributes. To allow the operation on multi attribute items we proposed a simple structure called Parallel Bloom filter[5] .In thisarchitecture a number of testing strings inputs can be tested at the same time. Let test string inputs be ts 1 , ts 2 , ts 3 ?????????ts L . Each test string is a b bit long .Hash values for all of the test strings are tested by checking particular bit locations in m bit look up array as in case of regular bloom filter. Bit location values in look up array are ANDED separately for different hash values of different test string. Parallel processing architecture of bloom filter is shown in fig 6.](image-10.png "")
6![Fig. 6 : Parallel Processing Architecture](image-11.png "Fig. 6 :")
			© 2012 Global Journals Inc. (US)
		
		
			

				


* 
	
		A low power lookup technique for multi-hashing network applications
		
			TKaya
		
		
			Kocak
		
	
	
		Proc. IEEE Annual Symp. on VLSI (ISVLSI)
				IEEE Annual Symp. on VLSI (ISVLSI)Karlsruhe; Germany
		
			2006
			
		
	




* 
	
		Low power Bloom filter architecture for deep packet inspection
		
			IlhanKaya
		
		
			TaskinKocak
		
	
	
		IEEE Commun. Lett
		
			10
			3
			
			2006
		
	




* 
	
		Fully Pipelined Bloom Filter Architecture
		
			MichaelPaynter
		
		
			TaskinKocak
		
	
	
		IEEE Communications Letters
		
			12
			11
			
			November 2008
		
	




* 
	
		K-stage Bloom Filter Architecture
		
			MahmoodAhmadi
		
		
			& StephanWong
		
	
	
		International conference on Computer science and Engg
				
			2009
		
	




* 
	
		using Parallel Bloom Filters for multiattribute Representation on Network Services
		
			BinXio
		
		
			&Yuhua
		
	
	
		IEEE Transaction on Parallel and Distributed Systems
		
			21
			1
			January 2010
		
	




* 
	
		
		
			KSaravanam
		
		
			Dr
		
		
	




* 
	
		A Recent Survey on Bloom Filters in Network Intrusion Detection Systems
		
			AKumar
		
		
			JDolian
		
	
	
		International Journal on Computer science and Engg
		
			3
			3
			Mar 2011
		
	
	References Références Referencias




* 
	
		Space/time trade-offs in hash coding with allowable errors
		
			BBloom
		
	
	
		Commun. ACM
		
			13
			7
			
			1970
		
	




* 
	
		Deep packet inspection using parallel Bloom filters
		
			SDharmapurikar
		
		
			PKrishnamurthy
		
		
			TSSproull
		
		
			JWLockwood
		
	
	
		IEEE Micro
		
			24
			1
			
			2004
		
	




* 
	
		Increasing the Power Efficiency of Bloom Filters for Network String Matching
		
			IlhanKaya
		
		
			TaskinKocak
		
	
	
		P Proc.IEEE International Symposium on VLSI
				
			2006