Application of Bloom Filters in Chrome Safe Browsing

Application of Bloom Filters in Chrome Safe Browsing

I. Background and Requirements
The Chrome browser needs to protect users from malicious websites, but storing all malicious URLs globally on the local device is impractical. Bloom filters provide an efficient solution: storing a compact data structure locally to quickly determine whether a URL might be malicious.

II. Bloom Filter Configuration

  1. Bit Array Size: Chrome uses a bit array of approximately 20MB, capable of storing hundreds of millions of URL fingerprints.
  2. Number of Hash Functions: Employs 3-5 independent hash functions to balance false positive rates and performance.
  3. Update Mechanism: The Bloom filter data is updated from the Safe Browsing service every 30 minutes.

III. Workflow

User visits URL → URL hashing → Query Bloom Filter
    ↓
[Exists] → Possibly malicious → Server-side verification → Final decision
    ↓
[Not exists] → Safe → Directly allowed

IV. Implementation Details

  1. URL Normalization

    • Remove protocol headers (http/https)
    • Convert to lowercase uniformly
    • Handle special character encoding
    • Example: https://example.com/path → example.com/path

  2. Multi-layer Filtering Strategy

    • First layer: Full URL Bloom filter
    • Second layer: Domain-level Bloom filter
    • Third layer: IP address Bloom filter
    • Layered design improves detection coverage.

  3. Hash Function Design

    • Use fast hash functions like MurmurHash, CityHash
    • Different hash functions generate independent fingerprints for the same URL
    • Example: Compute 3 different hash values for "example.com"

V. False Positive Handling Mechanism

  1. Probabilistic Nature: URLs judged as "possibly existing" locally
  2. Server-side Verification: Send verification requests to Google Safe Browsing API
  3. Caching Strategy: Confirmed safe URLs are added to a local whitelist cache
  4. False Positive Statistics: Actual false positive rate is controlled below 0.1%

VI. Performance Optimization

  1. Batch Operations: Check all resource links on a page simultaneously
  2. Asynchronous Verification: Avoid blocking page loading
  3. Memory Mapping: Use memory-mapped files for the bit array to reduce memory usage
  4. SIMD Optimization: Use Single Instruction Multiple Data to accelerate bit operations

VII. Actual Results

  • Detection latency: <1 ms (local filtering)
  • Memory usage: Approximately 20MB
  • Update frequency: Every 30 minutes
  • Protection scope: Covers millions of malicious URLs

This implementation ensures user security while avoiding the storage and update pressure associated with storing all URL data locally.