Advanced Programming I Lecture Notes

13 April 2006 • Hashing Applications

Outline

• Bloom filters.

• Venti archive storage.

• Denial of service attacks.

Naughty-Word Blocking

• When blocking web pages with naughty words, it's important to err on the side of caution.

  • Sometimes block pages with no naughty words (minimize false positives).

  • Never leave unblocked a page with naughty words (no false negatives).

• Provide an algorithm that answers the question "Is this word naughty?"

Conditions

• Every naughty word must return "yes" (no false negatives).

• Occasionally a good word may return "yes" (some false positives).

  • For some definition of "occaionally".

• The word file may be preprocessed.

• The word file changes, but infrequently (daily or weekly, say).

• Make the solution fast and small.

Possible Solutions

• Three candiate data structures are sorted arrays, balanced binary search trees, and hash tables.

• Choosing by time:

  • A sorted array or a balanced binary tree answers questions exactly with O(log n) work.

  • A hash table answers questions exactly with constant work on average but with O(n) work in the worst case.

Chosing By Space

• An array (sorted or not) takes the least space.

• Unused buckets make a hash table less space efficient than an array.

• A bst is less space efficient than an array due to pointer overhead.

  • And is probably less space efficient than a hash table.

Choosing by Compression

• Storing a few million words in an array is expensive.

• Compressing word lists is relatively easy.

  • All three data structures can exploit a compressed word list.

• Which data structure itself can acheive the most compression?

  • And at what run-time cost?

Compressing Hash Tables

• The problem lets "yes" answers be wrong occasionally.

  • "No" answers must always be right.

• Hashing has no false negatives, but may have false positives.

  • A word in the table will always be found.

  • A word not in the table may sometimes be found.

Collisions

• A collision may cause a false positive.

• But false positives are acceptable at some low occurrence rate.

• And so collisions don't need to be resolved, or even checked for.

• Words don't need to be stored in the hash table.

  • Just their presence in a bucket.

  • That takes one bit.

Bloom Filters

• A Bloom filter is a hash table with one-bit buckets.

  bool table[N] = { false }
  
  void add(k)
    table[h(k)] = true
  
  bool find(k)
    return table[h(k)]
  
  unsigned hash(k)
    return ( /* whatever */ ) % N
  

Space Analysis.

• /usr/share/dict/american-english has 98,568 words in 931,467 bytes.

• bzip2 compresses this down to 333,414 bytes or 2.6×10⁶ bits.

  • Stored in an array, it can be accessed with three-byte indices.

Space Analysis..

• An array requires 98,568×3 ≈ 300,000 + 333,414 ≈ 600,000 bytes.

• A bst requires two more pointers per node, an extra 600,000 bytes, for a total of around 1.2×10⁶ bytes.

• A Bloom filter can use 1 byte per word for a total of around 100,000 bytes.

  • The load factor 1/8 ≈ 0.13 should provide good performance.

Bloom Filtering

• Drawin's Origin of the Species has 11,410 unique words, 3,848 of which don't appear in american-english.

• A Bloom filter with around 800,000 buckets stores american-english with a 0.12 load factor and passes 3,409 words.

  • There were 3,848 - 3,409 = 439 false positives, almost one out of every nine words.

  • See the code.

More Filtering Results

		load		false
buckets		factor		positives
1,300,000		0.07		317	8%
1,200,000		0.07		295	7%
1,100,000		0.09		337	8%
1,000,000		0.09		368	9%
900,000		0.10		393	10%
800,000		0.12		439	11%
700,000		0.13		538	14%
600,000		0.15		571	15%
500,000		0.17		669	17%

Improving Bloom Filters

• Bloom filter false positives (collisions) can be reduced by increasing the hash-table size.

  • As with regular hash tables.

• Bloom filters also allow a special-case improvement: use more hash functions.

  • More 1s make arbitrary collisions more likely.

  • A specific collision pattern, however, is less likely.

Multiple Hash Functions

	Colliding over one bit.
	Colliding over a bit pattern.

Order-k Bloom Filters

• An order-k Bloom filter is a Bloom filter with k > 0 hash functions.

  void add(w)
    table[h1(w)] = ... = table[hk(w)] = true
  
  bool find(k)
    return 
      table[h1(w)] ∧ ... ∧ table[hk(w)]
  

Order-k Results

• Same set-up, 800,000 buckets.

  		load		false
  order		factor		positives
  1		0.12		439	11%
  2		0.21		162	4%
  3		0.31		98	3%
  4		0.38		82	2%
  5		0.45		79	2%

• An order-7 filter with 1.5M buckets has no false positives.

Venti Archive Storage

Denial Of Service Attacks

References

• Space/Time Trade-offs in Hash Coding with Allowable Errors by Burton Bloom, Communications of the ACM, July 1970.

• Venti: A New Approach to Archival Storage by Sean Quinlan and Sean Dorward in the First USENIX Conference on File and Storage Technologies, January, 2002.

• Denial of Service via Algorithmic Complexity Attacks by Scott Crosby and Dan Wallach in the 12th USENIX Security Symposium, August, 2003.