Machine Problem 2

Bloom Filters for String Matching

Introduction

Bloom Filters

In Lecture 5 we learned about bloom filters and their uses for string/signature matching.  In this machine problem, we are going to implement a bloom filter to be used to do signature matching.  Bloom filters are very good at performing large membership queries very quickly.  Some important things of note about bloom filters include:

• A bloom filter computes k hash functions on an input
• Each resulting hash value is then queried to determine membership
• If each hash function test for membership results in a match, a potential match is reported.
• A bloom filter will never give a false negative, but it can return a false positive.  (We will not deal with false positives in this MP.)
• To analyze a bloom filter the following parameters are used:
  • n = number of strings to be stored
  • k = number of hash functions
  • m = the size of the bit-array (memory)
• The false positive probability is f = (1/2)^k
• The optimal value of hash functions is k = (m/n)ln2

Hash Function

In Lecture 6 and Lecture 6b we learned about hashing techniques that can be implemented in hardware.  Since the bloom filter uses a hash function to set a bit vector, a simple hash function will also need to be implemented.  In this assignment we will compute 10 different hash functions.  By calculating 10 hash functions, the false positive probability becomes f = (1/2)^10 = 0.001.  The i^th hash function is defined as:

In this machine problem, the set of {d_i1, d_i2, d_i3, ...., d_ib} is a set of random 12-bit values.  To put this equation in words, for each bit in a character string, if that bit is equal to '1', xor the random value associated with that bit with the current result.  For example, suppose you have to calculate a 3-bit hash value and you are given the follow parameters:

d = {"011", "100", "001", "011", "110"}  -- the random values

X = 01011  -- the input string

The resulting hash value will be 100 xor 011 xor 110 = 001   

Note that the only difference between the 10 hash functions will be the set of random values, d.

References

• Network Applications of Bloom Filters
• Deep Packet Inspection using Parallel Bloom Filters
• Lecture 5
• Lecture 6
• Lecture 6b

Directions:

• Part 0: Download the MP2 Distribution file here.  The following files are new to this distribution:

  • options_processor.vhd - wrapper file around the bloom filter

  • input_controller_fsm.vhd - component to control input controller.

  • input_controller.vhd - component which takes 32-bit words and converts them to an in-order byte stream

  • fifo_512_by_36.vhd (and edn) - buffer for the input controller

  • large_bloom_filter.vhd - main bloom filter component top level

  • random_values.vhd - array of random values for the 10 different hash functions

  • alert_generator.vhd - component which creates an alert message for statistics counter reads, testing output, and bloom filter matches.

  • alert_generator_fsm.vhd - the FSM for the alert_generator.  (Note that these two files have changed since MP1)

  • fifo_256_by_32.vhd (and edn) - buffer for the alert generator.

• Part 1: Generating your bloom filter memory (bit vector)

  • Your bloom filter will need multiple block ram components that are 4096 entries by 1 bit.
  • Generate a dual port block memory component using Xilinx CORE Generator (Programs --> Xilinx --> Accessories --> CORE Generator).
  • Refer to this tutorial.

• Part 2: Creating a Partial Bloom Filter (PBF)

  • A partial bloom filter (PBF) is a wrapper around a single block ram.  
  • Since the block ram has two ports, we can support 2 hash functions per PBF. 
  • The proposed interface is shown in Figure 1.
  • Note that the clk and reset_l signals are not explicitly shown.

    

    Figure 1: Partial Bloom Filter Interface.

     

  • The 3 signals bit_data, set_bit, and bit_addr provide the control interface to the PBF for setting/resetting bits in the bit vector.
  • The 2 signals h1 and h2 are the supplied hash address to look up.
  • bit_data - this is the value to place at the bit location specified by bit_addr.
  • bit_addr - the location of the bit to update
  • set_bit - a control signal specifying that the value on bit_data and bit_addr is valid, and therefore, you need to update block ram.
  • h1 - a hash address to look up
  • h2 - a hash address to look up
  • pbf_ready - asserted '1' when the PBF is ready to begin (i.e. after resetting all 4096 locations in memory)
  • partial_bloom_match - asserted '1' when the value located at h1 and h2 are both set ('1').
  • Reset Operation
    • When the reset_l signal is asserted ('0'), you will need to reset the block ram component inside your PBF. 
    • After this operation is complete, pbf_ready can be asserted ('1').  
    • You will have to use a multiplexer between the reset address and one of the hash functions coming in.
  • Configuration Operation
    • When set_bit is asserted ('1'), you will need to update the bit found at bit_addr with the value on bit_data. set_bit will be asserted on back-to-back clock cycles.
    • You will have to use a multiplexer between the bit_addr value and one of the hash functions coming in.
    • Give configuration precedence over normal bit vector queries.
  • Matching Operation (querying the bit vector)
    • On each clock cycle a new hash address will be arriving on both h1 and h2.
    • Thus, you will need to lookup addresses h1 and h2 in parallel.  (This can be done since we are using a dual-port block ram.)
    • If the bits located at h1 and h2 are set ('1'), assert partial_bloom_match ('1'). 
  • Note note note note:  You will need to pipeline your design because h1 and h2 values will change every cycle.
  • Before you proceed to Part 3, simulate your component to make sure it works properly. 

     

• Part 3:  Creating a Large Bloom Filter
(LBF)
• For the most part, a large bloom filter (LBF) just wires up multiple PBFs.  There are two other vital components that need to interface with the PBFs, as can be seen in Figure 2.
• Note note note note:  You will need to pipeline your design because the string_in value will change every cycle, and you have to look up every string_in value that comes in.
• In addition, you cannot do all the steps necessary to do a lookup in a single clock cycle.



Figure 2: High Level block diagram of a large bloom filter.

 

• bram_decoder
  • This component will need to accept two inputs: valid_req and bram_num.
  • valid_req signifies that the bram_num, bit_data, and bit_addr values are valid. This means you will have to update one of the PBF's bit values.
  • bram_num informs you which PBF to update.  In this case, bram_num will range from 0 to 4. 
  • The bram_decoder will have to decode the bram number and assert the appropriate PBF's set_bit input.
• hash_matrix
  • This component will need to compute 10 hash values over the string_in input.  Two hash values will be fed to each PBF (one on h1, and one on h2).
  • Specifically:
    • hash functions 0 and 1 will go to bram 0 (PBF 0)
    • hash functions 2 and 3 will go to bram 1 (PBF 1)
    • hash functions 4 and 5 will go to bram 2 (PBF 2)
    • hash functions 6 and 7 will go to bram 3 (PBF 3)
    • hash functions 8 and 9 will go to bram 4 (PBF 4)
  • This component will need to use the random_values.vhd file provided with the distribution.  A snippet of the table is shown in Figure 3.

  

  Figure 3:  A table entry for 1 hash function (specifically hash function 9).

   

  • This table can be interpreted as follows:
    • The rows consist of a byte of a string (the most significant byte appears in the first row)
    • The columns consist of the specific bit in a byte (the most significant bit appears on the far left)
    • Each block consists of 1 hash function (hash function 9 is the first one listed in the file)
    • You can access this constant value (once you've compiled it into your library) by simply typing ran(hash #)(byte #)(bit #)
    • For example, to access hash function 9, byte 2, and bit 3, you would type ran(9)(2)(3).  This value is x"31d"
  • As another example, let's say that the string in is x"80000000000000000003".  Three of the bits in this string are set.  Hash function 9 will need to compute x"5b6" xor x"f5b" xor x"9e9" = x"304"
• Suggestion:  Code and simulate each component individually.  Before you wire them all together, simulate them to ensure they are working properly.
• The top level entity description of the LBF has been provided for you in the distribution file.  Adhering to the signal names of Figure 2 will simplify instantiating it in the options processor. 
• Before you proceed to Part 4, simulate your LBF!

• Part 4: Wiring up your LBF into the options processor file.

  • The block diagram of the options processor can be seen in Figure 4.

  

  Figure 4: Options Processor Block Diagram

   

  • As is evident from the byte-stream pipeline, a new string will be passed to your LBF every clock cycle. 
  • Modify the options_processor.vhd file to instantiate your LBF. 
    • When your LBF tells you there has been a match, return the string that matched.
    • However, this string that caused the match will have moved on in the pipeline by the time you know it matched. 
    • You will need to modify what the offending signature is based on the latency of your LBF.
    • The value of bit_data, bit_addr, and bram_num can be taken directly from the input d_out_appl_int, as will be seen in the next section.

• Part 5: Modifying the CPP to accept a new opcode to just test whether your module is working properly.

  • In the entity declaration, add:  test_output : OUT STD_LOGIC;
  • In the type declaration of states, add one state: test_outgoing
  • In the nextstate process, add this to the WHEN opcode => case:  ELSIF (d_out_appl_int(31 DOWNTO 24) = x"86") THEN next_state <= test_outgoing;
  • In the nextstate process, add this line:  WHEN test_outgoing => IF (dataen_out_appl_int = '1') THEN next_state <= idle;
    END IF;
  • In the outputs process, add this line to the default assignment values:  test_output <= '0';
  • In the outputs process, add this:  WHEN test_outgoing => IF (dataen_out_appl_int = '1') THEN test_output <= '1' ;
    END IF ;

• Part 6: Modifying the CPP to interface with your bloom filter

  • Modify the CPP to accept a new opcode.  This opcode will be x74, and it has the format given in Figure 5.

  • The # Bits to Edit field is 8 bits.  A 0 in this field means there is one entry following.  A 1 in this field means there are two entries following.  Etc. etc.. up to 255 which means there are 256 entries following. 
     

  

  Figure 5: Control Packet format for opcode x74.

   

  • Modify your state machine to count these 2 new opcodes

  • A suggested modification for the cpp is shown in Figure 6.  Note that this requires storing the # of bits to edit field in a register.   

  

  Figure 6: Suggested Modification of CPP.

   

• Part 7:  Modifying Top Level to include your components.

  • The new top level has wired everything up already.  CHECK that everything is mapped correctly for your implementation.

• Part 8:  Simulating Everything

  • Simulate your design in modelsim.  You will be asked to submit a simulation.

  • A Java Program has been provided which creates control packets to set bits for a specific character string.  (You will need to compile the source code).

  • To use this program type java BitSetter <location of random_values.vhd file> in a cygwin window.

  • The program will await input from you.  You can either input:

    • hexadecimal inputs by typing x<hexstring>  - Example x0102030405060708090a
    • character strings by typing "<string characters>" - Example "We Love CS"
    • to quit, type quit

• Part 9: Synthesis and Build

  • Use Synplicity to make an edn file for your design.  Follow the steps given in MP1.

  • Once you have completed synthesis, use the provided makefile in the backend directory.  From a cygwin shell, type 'make build'.

  • If you want to change the target frequency, you can change all 4 values in the network_application_core.ncf file.  Currently, the rad_clk period is set to 40 ns (25 MHz). 

  • This will generate a bitfile if there are no errors. You will submit this bitfile to the online test server to test it in hardware.

Table 1: Symbol Key

Table 2: New files in MP2_distribution.tar

Things to Turn In:

Bonus Opportunities:

Submission:

• Everything submitted on or before Monday, the 20th  +5
• Everything submitted on Tuesday, the 21st  +4
• Everything submitted on Wednesday, the 22nd  +3
• Everything submitted on Thursday, the 23rd  +2
• Everything submitted on Friday, the 24th  +1

PAR Speed

• > 75 MHz + 4
• 62.5 < f  < 75 MHz +3
• 50 < f  < 62.5 MHz +2
• 35 < f  < 50 MHz +1

Here is a checklist of the things you need to turn in:

• Part 2:  Partial Bloom Filter

  • VHDL code written. ( 5 pts)

• Part 3: Large Bloom Filter

  • All VHDL code written/modified. ( 4 pts)

  • Simulation waveforms showing this working. ( 4 pts)

• Part 4: Options Processor Modification

  • All vhdl code modified. ( 2 pts)

• Parts 5 & 6: Control Packet Processor Modification

  • All vhdl code modified. ( 2 pts)

• Part 7: Top Level Modifications (if any)

  • All vhdl code modified. ( 1 pt)

• Part 8: Simulation

  • A simulation using this DAT file and this waveform list. ( 5 pts)
  • NOTE: These files are probably not sufficient to show that your components are working, so you should generate your own test traffic and waveform lists.

• Part 9: Synthesis and Build

  • Also submit the network_application_core.par file generated after running the build scripts.  ( 2 pts)

  • Submit the requested waveforms and vhdl to the Electronic Homework Server. ( 25 pts)

  • Submit synthesized .bit file to the test server where it will be tested in hardware. ( 75 pts)

    • Click on the Test Bitfile link on the left
    • To log in use the User Name: cse535
    • Password: soc_snort

  • Follow the instructions on the server, it will inform you if your design passed or not.