How Chrome Checks Millions of Malicious Sites
42sReveals the hidden tech behind a common browser feature, sparking curiosity and relatability.
▶ Play ClipAI Summary
This video explains Bloom filters, a probabilistic data structure used by Chrome to check URLs against a list of malicious sites without storing the full list. It highlights how Bloom filters trade a small false positive rate for massive memory savings while guaranteeing zero false negatives.
Chapters
[00:02]
The Problem
Chrome needs to check URLs against millions of malicious sites instantly without sending browser history to Google servers. A database lookup on every navigation is too slow and a privacy nightmare.
[00:15]
Naive Approach
Downloading the full list of bad URLs and storing them locally in a hash set is impractical because millions of URLs at 50 bytes each would consume too much memory, and the list changes constantly.
[00:29]
Bloom Filter Basics
A Bloom filter is a fixed-size bit array. When adding a URL, you hash it into multiple positions and flip those bits. To check membership, you hash again and see if all positions are set.
[01:01]
False Positives and Negatives
Bloom filters guarantee zero false negatives (if a URL is on the list, it will be detected), but they can have false positives (a URL not on the list might be flagged) due to bit collisions.
[01:14]
Trade-off Acceptable
In Chrome's case, a false positive just means an extra server call to verify a URL that turns out fine, which is acceptable. A false negative (missing a malicious URL) would be a real bug.
[01:27]
Memory Savings
Tracking a billion URLs at a 1% false positive rate costs about 1.2 gigabytes, while a hash set storing the same data would be 10 to 20 times more.
[01:40]
Other Applications
The same pattern is used in web crawlers to check visited URLs, spam filters, and any system doing high-volume membership testing at scale.
Bloom filters offer an efficient way to handle membership testing at scale, accepting a small false positive rate in exchange for significant memory savings, making them ideal for applications like Chrome's safe browsing.
Study Flashcards (5)
What is a Bloom filter?
easy
Click to reveal answer
What is a Bloom filter?
easy
Click to reveal answer
A fixed-size bit array used to test whether an element is a member of a set, with a configurable false positive rate and zero false negatives.
00:29
Why does Chrome use a Bloom filter instead of storing the full list of malicious URLs?
medium
Click to reveal answer
Why does Chrome use a Bloom filter instead of storing the full list of malicious URLs?
medium
Click to reveal answer
Storing millions of URLs would consume too much memory, and the list changes constantly. A Bloom filter provides instant membership checks with minimal memory.
00:15
What is the trade-off of a Bloom filter?
medium
Click to reveal answer
What is the trade-off of a Bloom filter?
medium
Click to reveal answer
It trades a configurable false positive rate for massive memory savings, while guaranteeing zero false negatives.
01:14
What is the memory cost of tracking a billion URLs at a 1% false positive rate?
hard
Click to reveal answer
What is the memory cost of tracking a billion URLs at a 1% false positive rate?
hard
Click to reveal answer
About 1.2 gigabytes, compared to 10-20 times more for a hash set.
01:27
What happens if a Bloom filter returns a false positive in Chrome's safe browsing?
easy
Click to reveal answer
What happens if a Bloom filter returns a false positive in Chrome's safe browsing?
easy
Click to reveal answer
It makes one extra server call to verify the URL, which is acceptable.
01:14
💡 Key Takeaways
🔧
Bloom Filter Mechanics
Explains the core mechanism of hashing into multiple bit positions, which is fundamental to understanding the data structure.
00:29
📊
Zero False Negatives
Highlights the key property that makes Bloom filters reliable for security applications.
01:01
📊
Memory Savings Quantified
Provides concrete numbers showing the dramatic memory savings compared to a hash set.
01:27Full Transcript
[00:02] you visit against a list of millions of malicious sites instantly without sending your browser history to Google servers? A database lookup on every navigation would be too slow and a privacy nightmare. So, Chrome needs
[00:15] something that lives on your device. The obvious approach is to download the full list of bad URLs and store them locally in a hash set. It sounds reasonable until you do the math. Millions of URLs at even 50 bytes each blows past what
[00:29] you want sitting in browser memory. And the list is changing constantly. What you actually need is a way to check membership instantly at scale without storing every URL. Chrome uses a Bloom filter. It's a fixed-size bit array.
[00:44] When you add a URL to the filter, you hash into multiple positions and flip those bits. To check membership, you hash the URL again and see if all of the positions are set. If any bit is zero, that URL is definitely on the list. If
[01:01] all of the bits are set, it probably is, but occasionally other entries flip those same bits, giving you what's called a false positive. Bloom filters guarantee zero false negatives, so if it's in the list, you're going to know,
[01:14] but they trade a configurable false positive rate for massive memory savings. In Chrome's case, a false positive just means you make one extra server call to verify a URL that turns out to be fine. It's acceptable. A false
[01:27] negative of missing an actually malicious URL would be a real bug. The numbers back it up. Tracking a billion URLs at a 1% false positive rate costs URLs at a 1% false positive rate costs about 1.2 gigs. A hash set storing the
[01:40] same data would be 10 to 20 times more. The same pattern shows up in web crawlers checking visited URLs, spam filters, and any system doing high-volume membership testing at scale. Want to hear about more tricks like
[01:53] Want to hear about more tricks like this? Follow us for more system design.
