Lecture notes for CS 503, Advanced Programming I

Advanced Programming I Lecture Notes

10 April 2007 • Hashing Applications

Outline

Bloom filters.
Fingerprinting.
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[h₁(w)] = ... = table[h_k(w)] = true

bool find(k)
  return 
    table[h₁(w)] ∧ ... ∧ table[h_k(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.

Fingerprinting

Archival storage backs-up and maintains file systems.
- Massive amounts of data, widely and deeply accessed.
Massive conflicts with access.
- The larger the store, the less able the access.
  - Both physical and logical access limitations.

Disruption

New and improved storage technologies effect the archiving trade-off.
- New definitions of “massive”.
- Greater and more consistent access.
How do archiveing services change in response to changed storage technologies?
- There are lots of guesses

Venti Archiving

Venti is the archive server for the Plan 9 operating system.
Venti properties include
- variable-sized, block-level storage.
- Write-once storage.
- Hashing block contents provide block identity.

Indexed Block Storage

A storage device is an array of fixed-length storage blocks.
- A block's index is the block address.
A file is a sequence of blocks.
- The block addresses are stored in the file's metadata.

Venti Block Storage

Venti hashes a block's content to get a fingerprint.
An index maintains a map of fingerprints to storage addresses.a

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.

This page last modified on 7 June 2006.
This work is covered by a
Creative Commons License.