How Advanced Browsing Protection Works in Messenger

Advanced Browsing Protection (ABP) extends Messenger’s Safe Browsing beyond on-device detection by checking links against a frequently updated database of millions of potentially malicious websites. Its central challenge is balancing effective URL matching with privacy: Messenger must identify unsafe links without revealing users’ exact queries or distributing the entire blocklist. ABP combines private information retrieval, cryptographic techniques, sharding, and client-side preprocessing to achieve this balance.

Safe Browsing Within End-to-End Encryption

• Messenger’s end-to-end encryption protects messages and calls, but it does not by itself protect users from malicious links.
• Safe Browsing warns users when a link may lead to phishing, credential theft, or other harmful activity.
• The standard feature uses on-device models.
• Advanced Browsing Protection adds access to a continually updated watchlist containing millions of potentially malicious websites.

Private Information Retrieval as the Foundation

• Private information retrieval (PIR) allows a client to ask whether an item exists in a server-held database while revealing as little as possible about the query.
• Sending the full database to each device is impractical because:
  • The database is large and frequently updated.
  • Exposing the complete list could help attackers evade detection.
• Existing PIR approaches use oblivious pseudorandom functions (OPRFs) and divide the database into buckets or shards.
• ABP had to address two limitations:
  • OPRFs are designed for exact matches, whereas URLs require prefix matching.
  • The client generally must identify which bucket to query, creating a privacy-versus-efficiency tradeoff.
• More advanced lattice-based constructions may reduce the need for sharding, but they were not yet practical at ABP’s scale.

Privacy-Preserving Prefix Matching for URLs

• A database entry such as example.com should match a longer URL such as example.com/a/b/index.html.
• Querying every prefix separately would work functionally:
  • example.com
  • example.com/a
  • example.com/a/b
  • example.com/a/b/index.html
• However, each query can leak information about the original URL. If one query leaks B bits and there are P prefixes, the total leakage may reach P × B bits.
• ABP instead groups URLs by domain so the client makes one bucket request and checks path prefixes within that bucket.
• This reduces query leakage but creates uneven bucket sizes.
• Domains such as link-shortening services may contain huge numbers of URLs, producing oversized buckets and potentially large padded responses.

Preprocessing Rulesets to Balance Buckets

• The server addresses bucket imbalance by generating a ruleset that tells clients how to process URLs before selecting a bucket.
• Each rule maps an 8-byte hash prefix to a number of path segments that should be appended to the current URL before hashing again.
• For example:
  • The client hashes example.com.
  • If the hash matches a ruleset entry, it appends specified path segments, such as /a/b.
  • It hashes the resulting URL again and repeats the process.
  • When no ruleset entry matches, the client uses the first two bytes of the final hash as the bucket identifier.
• The server builds the ruleset iteratively:
  • It initially hashes URLs by domain.
  • It identifies the largest bucket.
  • It finds the most common domain in that bucket.
  • It adds rules that incorporate additional URL path segments to split the oversized bucket.
• Clients receive the ruleset in advance and perform the same deterministic processing during lookups.

ABP’s design demonstrates how privacy-preserving lookup can support real-world URL semantics without exposing users’ links. The combination of PIR, controlled sharding, prefix-aware processing, and adaptive rulesets allows Messenger to warn about malicious sites while limiting what the server learns about each user’s browsing query.