The mounting cost of stale ad blocking rules (2018) | Hacker News Reader

The mounting cost of stale ad blocking rules (2018)

brave.com

40 pointsfossislife15 comments

"... we applied EasyList to both the Alexa 5k, a curated list of the 5,000 most popular sites on the web, and a random sampling of 5,000 sites from the Alexa 1,000,000 (ensuring no duplicate sites). Our measurement was in several steps:

1. Use Selenium and the DevTools Protocol to record every URL requested when rendering and executing a website.

2. Add additional automation to randomly select three distinct same-domain URLs from anchor tags on a page.

3. Used the above automation to visit the homepage of each site, and a maximum of three child pages, and recorded all URLs requested for images, script files, and other web resources.

4. Determine which of those URLs would be blocked by the version of EasyList fetched on that day, using Brave's optimized ad-block implementation.

...

We found that the vast majority of EasyList rules are not used when browsing popular websites; 3,268 of 39,198 (~8%) of network and exception rules were used during our crawls (these measurements exclude element rules)."

That doesn't mean that EasyList is not useful for browsing the rest of the internet.

Yeah, there are likely statistical methods you could use to estimate the number of stale rules, but "try the top 5000 and ~0.5% of the rest" isn't that

Also 8% of the rules could block like 99% of web traffic. But also notice the part where they went to 1m random sites too. That would be a sample from the rest of the Internet.

Much work has been done since this article came out to remove stale filters, see:

https://twitter.com/fanboynz/status/1344796683612299265

For anyone interested in this blog post here, the full conference paper version is here: https://www.peteresnyder.com/static/papers/easylist-sigmetri...

Does anyone know how EasyList normally deals with old rules? Is there a process to identify and remove stale rules?

Can someone explain the steplike shapes in the curve in the "time to filter a request" plot? I was under the impression that ad blockers used hash tables or a similar structure which is agnostic of the address being checked with O(1). Are these some kind of cache misses?

It's not a simple address check (lookup) it's a pattern-match - like loops around a bunch of regex. Those 1000+ stale patterns slow it down.

Surely a loop over regexes is not the smartest solution that one could use for this? We do have algorithms for looking up multiple patterns at once and such, right?

I think the fastest data structure for this is to replace the whole thing by one big finite state transducer https://blog.burntsushi.net/transducers/ - such data structure can be built from the EasyList regexes, and perform all checks in a single lookup.

The idea here would be to compile the regex of each rule to an automata (each automata matches a set of strings) and them build a fst out of them (that would map strings to matched rules)

Is it really the fastest way? I imagine that without extra data it may be, but what I was proposing in a cousin comment would involve profiling and early fast rejection by means of efficient multiple string matching. The browser should be able to collect a significant amount of historical matching data to optimize these lookups.

Well, you can see one approach in the uBlock source code.

Matching against static, glob and regex patterns. And there is some grouping and filtering so, it's not like every URL gets all 64k patterns matched. And it's possible to pre-compile and group the Regex to get a little faster (lots of framework routers do this)

From my opinion the "web" is so contaminated it's a shorter accept-list than a constantly changing reject-list

I imagine that one should be able to profile the actual data from the actual web pages and then compile an optimal (or at least a near-optimal) decision tree, i.e., a decision tree with a minimum expected value of testing any of the inputs seen so far. Worst case is that this comes out as equivalent to the naive loop (the naive loop is essentially a degenerate decision tree), but average case should be much better.

Furthermore the decision tree needn't be binary. If you group regexes by common substrings and then even group substrings for, say, a Commentz-Walter matcher, you are able to distinguish N+1 cases for N patterns, with significantly lesser costs than N times the cost of matching for one substring alone.

Personally use an "allow list" as opposed to a "block list". Not sure which is "easier" but definitely know which one is faster, more efficient and has zero misses or false positives.

Arguably its more useful to know what a given website actualy requires than to know every possible advertising scheme. Allow lists teach about where to find desired content. Block lists do not teach anything useful in that regard.

The steps are an artifact of the X-axis, which is logarithmic. The first step occurs from 1 resource to 2 resources, on so on.

A hash table can't be used for this kind of check because it uses patterns, so resources need to be compared on a pattern. Although I'm sure there are special cases, like hash tables of domain names, which cover a large portion rules.

Reply on news.ycombinator.com