Who Filters the Filters: Understanding the Growth, Usefulness and Efficiency of Crowdsourced Ad Blocking

Ad and tracking blocking extensions are popular tools for improving web performance, privacy and aesthetics. Content blocking extensions typically rely on filter lists to decide whether a web request is associated with tracking or advertising, and so should be blocked. Millions of web users rely on filter lists to protect their privacy and improve their browsing experience. Despite their importance, the growth and health of filter lists are poorly understood. Filter lists are maintained by a small number of contributors, who use a variety of undocumented heuristics to determine what rules should be included. Lists quickly accumulate rules, and rules are rarely removed. As a result, users' browsing experiences are degraded as the number of stale, dead or otherwise not useful rules increasingly dwarf the number of useful rules, with no attenuating benefit. An accumulation of"dead weight"rules also makes it difficult to apply filter lists on resource-limited mobile devices. This paper improves the understanding of crowdsourced filter lists by studying EasyList, the most popular filter list. We find that EasyList has grown from several hundred rules, to well over 60,000 rules, during its 9-year history. We measure how EasyList affects web browsing by applying EasyList to a sample of 10,000 websites. We find that 90.16% of the resource blocking rules in EasyList provide no benefit to users in common browsing scenarios. We further use our changes in EasyList application rates to provide a taxonomy of the ways advertisers evade EasyList rules. Finally, we propose optimizations for popular ad-blocking tools, that allow EasyList to be applied on performance constrained mobile devices, and improve desktop performance by 62.5%, while preserving over 99% of blocking coverage.


Introduction
As the web has become more popular as a platform for information and application delivery, users have looked for ways to improve the privacy and performance of their browsing. Such efforts include popup blockers, hosts.txt files that blackhole suspect domains, and privacy-preserving proxies (like Privoxy 1 ) that filter unwanted content. Currently, the most popular filtering tools are ad-blocking browser extensions, which determine whether to fetch a web resource based on its URL. The most popular ad-blocking extensions are Adblock Plus 2 , uBlock Origin 3 and Ghostery 4 , all of which use filter lists to block unwanted web resources.
Filter lists play a large and growing role in making the web pleasant and useful. Studies have estimated that filter lists save users between 13 and 34% of network data, decreasing the time and resources needed to load websites [4,18]. Others, such as Merzdovnik et al. [16] and Gervais et al. [5], have shown that filter lists are important for protecting users' privacy and security online. Users rely on these tools to protect themselves from coin mining attacks, drive-bydownloads [12,24] and click-jacking attacks, among many others.
Though filter lists are important to the modern web, their construction is largely ad hoc and unstructured. The most popular filter lists-EasyList, EasyPrivacy, and Fanboy's Annoyance List-are maintained by either a small number of privacy activists, or crowdsourced over a large number of the same. The success of these lists is clear and demonstrated by their popularity. Intuitively, more contributors adding more filter rules to these lists provide better coverage to users.
However, the dramatic growth of filter lists carries a downside in the form of requiring ever greater resources for enforcement. Currently, the size and trajectory of this cost are not well understood. We find that new rules are added to popular filter lists 1.7 times more often than old rules are removed. This suggests the possibility that lists accumulate "dead" rules over time, either as advertisers adapt to avoid being blocked, or site popularity shifts and new sites come to users' attention. As a result, the cost of enforcing such lists grows over time, while the usefulness of the lists may be constant or negatively trending. Understanding the trajectories of both the costs and benefits of these crowdsourced lists is therefore important to maintain their usefulness to web privacy, security and efficiency.
This work improves the understanding of the efficiency and trajectory of crowdsourced filter lists through an empirical, longitudinal study. Our methodology allows us to identify which rules are useful, and which are "dead weight" in common browsing scenarios. We also demonstrate two practical applications of these findings: first in optimally shrinking filter lists so that they can be deployed on resource-constrained mobile devices, and second, with a novel method for applying filter list rules on desktops, which performs 62.5% faster than the current, most popular filtering tool, while providing nearly identical protections to users. Research questions. For two months, we applied every day an up-to-date version of EasyList to 10,000 websites, comprising both the 5K most popular sites on the web and a sampling of the less-popular tail. We aimed to answer the following research questions: 1. What is the growth rate of EasyList, measured by the number of rules?
2. What is the change in the number of active rules (and rule "matches") in EasyList?
3. Does the utility of a rule decrease over time? 4. What proportion of rules are useful in common browsing scenarios?
5. Do websites try to stealthily bypass new ad-blocking rules, and if so, how?
6. What is the performance cost of "stale" filter rules to users of popular ad-blocking tools?
Contributions. In answering these questions, we make the following primary contributions: 1. EasyList over time: we present a 9-year historical analysis of EasyList to understand the lifetime, insertion and deletion patterns of new rules in the list.
2. EasyList applied to the web: we present an analysis of the usefulness of each rule in EasyList by applying Ea-syList to 10,000 websites every day for over two months.
3. Advertiser reactions: we document how frequently advertisers change URLs to evade EasyList rules in our dataset and provide a taxonomy of evasion strategies. 4. Faster blocking strategies: we propose optimizations, based on the above findings, to make applying EasyList performant on mobile devices, and 62.5% faster on desktop environments, while maintaining over 99% of coverage.
Paper organization. The remainder of this paper is organized as follows. Sections 2 and 7 provides a brief background about tracking and ad-blockers as well as a discussion of the related work. Section 3 presents a 9-year analysis of EasyList's evolution. Section 4 presents how EasyList rules are applied on websites. Section 5 studies how our findings can improve adblocking applications on iOS and proposes two new blocking strategies to process requests faster. Finally, in Section 6 we present the limitations, and we conclude the paper in Section 8.

Background
Online tracking. Tracking is the act of third parties viewing, or being able to learn about, a users' first-party interactions. Prior work [2,11,23] has shown that the number of third-party resources included in typical websites has been increasing for a long time. Websites include these resources for many reasons, including monetizing their website with advertising scripts, analyzing the behavior of their users using analytics services such as Google analytics or Hotjar, and increasing their audience with social widgets such as the Facebook share button or Twitter retweet button. While third-party resources may benefit the site operator, they often work against the interest of web users. Third-party resources can harm users' online privacy, both accidentally and intentionally. This is particularly true regarding tracking scripts. Advertisers use such tracking tools as part of behavioral advertising strategies to collect as much information as possible about the kinds of pages users visit, user locations, and other highly identifying characteristics.
Defenses against tracking. Web users, privacy activists, and researchers have responded to tracking and advertising concerns by developing ad and tracker blocking tools. Most popularly these take the form of browser extensions, such as Ghostery or Privacy badger. 5 These tools share the goal of blocking web resources that are not useful to users, but differ in the type of resources they target. Some block advertising, others block trackers, malware or phishing. These tools are popular and growing in adoption [15]. A report by Mozilla stated that in September 2018, four out of the 10 most popular browser extensions on Firefox were either ad-blockers or tracker blockers. Adblock Plus, the most popular of all browser extension, was used by 9% of all Firefox users 6  • Privacy proxies protect users by standing between the client and the rest of the internet, and filtering out undesirable content before it reaches the client. Privoxy is a popular example of an intercepting proxy.
• Web browsers can attempt to prevent tracking, either through browser extensions or as part of the browser directly. These tools examine network requests and page renderings, and use a variety of strategies to identify unwanted resources. Some tools, such as Privacy Badger use a learning-based approach, while most others use filter lists like EasyList 9 or EasyPrivacy 10 .
EasyList. EasyList, the most popular filter list for blocking advertising, was created in 2005 by Rick Petnel. It has been maintained on Github 11 since November 2009. EasyList is primarily used in ad-blocking extensions such as Adblock Plus, uBlock origin and Adblock, and has been integrated into privacy oriented web browsers 12 . Tools also exist to convert EasyList formats to other privacy tools, like Privoxy 13 , EasyList consists of tens-of-thousands of rules describing web resources that should be blocked or hidden during display. The format also includes syntax for describing exceptions to more general rules. EasyList uses a syntax similar to regular expressions, allowing authors to generalize on patterns used in URLs.
EasyList provides two categories of benefit to users. First, EasyList describes URLs that should be blocked, or never fetched, in the browser. Second, EasyList describes page elements that should be hidden at rendering time. These rules are useful when blocking at the network layer is not possible. Examples of such cases include: • Native ads, that are directly integrated into the HTML code of the main page.
• Merging ad and tracking resources with other important files required to make the website work.
• URL obfuscation techniques, which make it difficult to narrowly identify ad and tracking related resources.
Element hiding rules can improve the user experience by hiding unwanted page contents, but cannot provide the performance and privacy improvements that network layer blocking provides. There are three types of rules in EasyList: 3. Exception rules, that contradict network rules by explicitly specifying URLs that should not be blocked, even though they match a network rule.

Composition of EasyList Over Time
This section measures how EasyList has evolved over its 9year history, through an analysis of project's public commit history. The section proceeds by first detailing our measurement methodology, along with our findings that EasyList has grown to comprise nearly 70,000 rules and that it is primarily maintained by a very small number of people. The section concludes by showing that most rules stay more than 3.8 years in EasyList before they are removed, suggesting a huge accumulation of unused rules.

Methodology
EasyList is maintained in a public repository on GitHub. We use GitPython 14 , a popular Python library, to measure commit patterns and authors in the EasyList repository over the project's 9-year history.
14 https://gitpython.readthedocs.io/en/stable/index.html For every commit in the EasyList repository, we record the author of the commit, as well as the type and number of rules modified in the commit.
Our measurements of EasyList's history were conducted as followed. First, we group commits by day. We then checkout each day's worth of commits, and measure which rules have been added and removed since the previous day. We use this per-day batching technique to avoid artifacts introduced by git diff, which we found causes over-estimations of the number of rules changed between commits.
Accounting for changes in repository structure. The structure of the EasyList repository has changed several times over the project's history. At different times, the list has been maintained in one file or several files. The repository has also included other distinct-but-related projects, such as EasyPrivacy. We use the following heuristics to attribute rules in the repository to EasyList.
On days when the repository consists of a single file called easylist.txt, we check to see if the file contains references (e.g. URLs or file paths in the repo) to lists hosted elsewhere or contains only filter rules. When the easylist.txt file contains references to other lists, we treat EasyList as the union of all rules in all referenced external lists. When easylist.txt contains only filter rules, we treat EasyList as the content of the easylist.txt file.
When the repository consists of anything other than a single easylist.txt file, we consider EasyList to be the content of all the files matching the following regular expression 'easylist_*.txt' and that are located in the main directory or in a directory called easylist.

Results
Rules inserted and removed. Figure 2 presents the change in the size of EasyList over time. It shows the cumulative number of rules inserted, removed, and present in the list over nine years. Rules are added to the list faster than they are removed, causing EasyList to grow larger over time. Over a 9year period, 124,615 rules were inserted and 52,146 removed, resulting in an increase of 72,469 rules. EasyList's growth is mostly linear. One exception is the sharp change in 2013, when "Fanboy's list", another popular filter list, was merged into EasyList.
Modification frequency. We analyzed the distribution of the time between two commits in EasyList and observed that EasyList is frequently modified, with a median time between commits of 1.12 hours, and a mean time of 20.0 hours.
EasyList contributors. Contributors add rules to EasyList in two ways. First, potential contributors propose changes in the EasyList forum. 15 Second, contributors can post issues on the EasyList Github repository. Though more than 6,000 members are registered on the EasyList forum, we find that only a small number of individuals decide what is added to the project. The five most active contributors are responsible for 72,149 of the 93,858 (76.87%) commits and changes. Figure 3 shows a bar chart of the number of commits per author of EasyList.
Lifetime of EasyList rules. Figure 4 presents the distribution of the lifetime of rules in EasyList. The figure considers only rules that were removed during the project's history. Put differently, the figure shows how much time passed between when a rule was added to EasyList, and when it was removed, for the subset of rules that have been removed. We observe that 50% of the rules stayed more than 3.8 years (45.5 months) in EasyList before being removed.

Applying EasyList to the Web
This section quantifies which EasyList rules are triggered in common browsing patterns. We conducted this measurement by applying EasyList to 10,000 websites every day for two months, and recording which rules were triggered, and how often.
This section first presents the methodology of a longitudinal, online study of a large number of websites. We then present the results of this measurement. We find that over 90% of rules in EasyList are never used. We also show that on average, 29.8 rules were added to the list every day, but that these new rules tend to be less used than rules that have been in EasyList for a long time.
The section concludes by categorizing and counting the ways advertisers react to new EasyList rules. We detect more than 2,000 situations where URLs are changed to evade rules and present a taxonomy of observed evasion strategies.

Methodology
Crawl description. To understand the usefulness of rules in EasyList, we applied EasyList to 10,000 websites every day for over two months (74 days). We selected these 10,000 websites from two groups: 1. Popular websites: Websites from the top 5K Alexa, a ranking of sites online by popularity.
2. Unpopular websites: 5,000 websites randomly selected from the top Alexa one-million, but not present in the set of popular websites. (i.e. rank 5,001-1 million) We crawled the web using an instrumented version of Chromium to measure which filter rules were applicable when browsing a large number of websites in an anonymous browsing scenario. The crawls were launched from AWS Lambda instances located in the us-east-1 region. We provide the code of the Lambda function on Github 16 . For each day of the experiment, we first visit the landing page of each URL in the popular and unpopular sets. We then 16  randomly selected up to three URLs referenced in anchor tags, pointing to pages on the eTLD+1 domain, and visit these URLs. This resulted in between 10,000 and 40,000 pages being measured every day. Table 1 provides high level statistics of these measurements. We use the Chrome devtools protocol 17 to record the following information about each network request made during page execution: We note that these measurements do not consider "element" (i.e. hiding) rules in EasyList. This work focuses only on "network" rules, since "network" rules (potentially) provide privacy and performance improvements, while "element" rules provide only cosmetic improvements.
To avoid introducing side effects, we did not block any requests during our measurements. We instead first recorded all HTTP requests made when interacting with each site. Next, we applied EasyList offline using Brave's ad-blocker NodeJS module 18 . We determine if each request would have been blocked, excepted, or allowed. A "blocked" request is one that matches an EasyList network rule, indicating that the resource should not be fetched. An "excepted" request is one that matches a blocking rule, but also matches a "excepting" rule, indicating that the resource should be fetched anyway. An "allowed" request matches no EasyList rules.
Description of the dataset. Our dataset comprises every network request made during our crawl of 10,000 websites, for 74 days between July 24th, 2018 and October 5th, 2018. Among the 10,000 websites crawled daily, 400 (4.0%) never responded during the experiment. We attribute this to a mix of websites becoming inactive (common among unpopular websites [19]) and websites blocking IP addresses belonging to AWS to deter crawlers. The existence of such AWS-including IP blacklists has been documented in other work [7]. We discuss possible limitations to our study more in Section 6.

Results
Proportion of EasyList rules used. We consider a rule as used during a crawl if the rule matched at least one network request made during the crawl. We measure the proportion of network and exception rules used during our crawls. We focus on network rules, as opposed to element (hiding) rules because network rules impact performance and privacy. We find that the vast majority of network and exception rules are never used. Only 9.84% (4, 038) of rules were used even once during our measurements.
An even smaller number of network and exception rules are frequently used. On average, only 5.14% of EasyList network and exception rules were used at least once per day (Research Question 4). We also observed that the number of active rules is stable over time (Research Question 2). Figure 5 shows the cumulative distribution function of how often filter rules were used during the 74 days of the experiment. The distribution is skewed; the majority of rules are either not used (90.16%), or were used between 1 and 100 times (4.45%). Only 3.56% of the rules were used between 100 and 1,000 times, and 1.83% more than 1000 times.
Usefulness of EasyList additions. During the experiment, 2, 202 network and exception rules were added to EasyList, an average of 29.8 new rules per day (Research Question 1). We refer to rules added to EasyList during our measurement campaign as new; we call rules old if they existed in EasyList at the start of the measurement period.
The vast majority of rules, new and old, were not used during our measurements. Of the 2, 202 rules added during the study period, 208 (9.45%) were used at least once. Those measurements are roughly similar for old rules (9.84%). However, when considering only rules that were used at least once, we found that new rules were used nearly an order of magnitude less than old rules. This suggests a declining marginal usefulness per rule as EasyList accumulates more rules, possibly because the most troublesome resources are already blocked. If a new rule was used during the study, it was used an average of 0.65 times per day. Old rules were applied much more frequently, 6.14 times a day on average. Impact of the age of rules. We also measure whether the age of a rule impacts its use. We find that the age of a rule significantly impacts the number of times rules are used. We present these findings in two ways: graphically and statistically. Figure 6 presents the distribution of the age of the rules present in EasyList, as well as the average number of uses depending on the age of a rule. The distribution of the age of the rules (black bars) shows that there are rules from all ages in EasyList. The important number of 5-year-old rules is explained by the merge of the "Fanboy's list", another popular filter list, with EasyList in 2013. If we observe the average number of times rules are used in a day (grey bars), we see that the most useful rules are old. This is caused by some really generic rules blocking URLs that contained keywords such as "ads" or popular domains such as doubleclick.net. For example, the rule .com/ads/$image,object,subdocument has been added to EasyList in September 2010 and has been used 748, 330 times during the experiment. We also observe that there is no simple linear relationship between the average use of a rule and its age.
Besides the graphical analysis, we also conduct statistic tests to determine whether the age of a rule impact its use. We use the Kolmogorov-Smirnov test to compare the distribution of the number of times rules are used depending on the duration they have been present in EasyList. For each year y i between 1 and 8, we compare the distribution of the number of times rules that have been present y i years in EasyList have been used with: 1. the distribution of the number of times rules that have been present less than one year, 2. the distribution of the number of times rules that have been present between y i−1 and y i years. For all the tests, we obtain p-values < 10 − 5, which indicates that there are significant differences in the way rules are used depending on their age (Research Question 3).

Advertiser Reactions
EasyList helps users avoid online advertising. Advertisers and websites that rely on advertising for their income do not want their content to be blocked and may try to circumvent rules in EasyList. There are several ways an advertiser may do this. One option is to try to detect the use of an adblocking tool [8]. Alternatively, the advertiser may manipulate the URLs that serve their content, to prevent matching filter rules. In this section, we measure how often, and in which ways, advertisers responded to EasyList rules. We do not observe a statistically significant reaction by advertisers in general but we note common patterns in avoidance strategies among a subset of advertisers.
Advertiser Reactions To New Rules. We first measured whether advertisers in general respond to being blocked in EasyList. We did not find a statistically significant reaction overall (meaning that most blocked-content-hosters do not seem to respond to relevant rules being added to EasyList), but find interesting commonalities among the subset of blockedcontent-hosters that do respond.
We designed this measure on the following intuition: if a resource changed URL more frequently after being blocked by EasyList than before, it would suggest an advertiser trying to evade EasyList. Similarly, if the number of times a resource was blocked spiked after the EasyList addition, and then reverted to its pre-rule block-rate, that would also suggest advertiser evasion.
We tested this intuition through the following steps. First, we considered only rules that were added during the measurement period, and which remained in EasyList for at least 14 Days since a rule has been added to EasyList   200  400  600  800  1,000  1,200  1,400  1,600 Number of times a hash is blocked/allowed Blocked Allowed Figure 7: Number of times resources are blocked or allowed after a rule is added to EasyList days. Second, we identified resources that were blocked by these new rules and looked to see if the same resource (as determined by the content's hash), was served by different URLs during the study. Third, we filtered out resources that were less than 50KB, to avoid resources that were trivially identical, like common logos and tracking pixels. Fourth, we measured whether the number of URLs a resource was served from changed significantly before and after being blocked by EasyList. Figure 7 presents the block and allow rates for resources affected by new rules. We did not find any population-wide trends of advertisers modifying URLs to avoid EasyList. As shown on the graph, adding a new EasyList rule increased how often affected resources were blocked (by definition). If advertisers were, in general, successfully evading EasyList, we would observe a decrease in blocking over time. Block rates did not, in general, revert to pre-rule levels over time. Advertiser Reactions To Old Rules. We also measured whether we could observe advertisers evading rules that existed in EasyList before the start of our study. We were able to identify many such evasions, but are unable to measure the significance of such observations, since we do not have historical records of block and allow rates for these resources.
We measured advertisers reactions to old rules by looking for instances of the following pattern: 1. A third-party resource is referenced by a first-party domain, and that third-party resource is blocked by an Ea-syList rule.
2. Later, the same third-party resource (determined by the response hash) is referenced by the same first-party domain, at least two times, and the resource is fetched from a different URL that is not blocked by EasyList. We

Evasion Strategies
In this subsection, we present a partial taxonomy of the strategies used by advertisers to avoid EasyList rules. Figure 8 presents the number of times each evasion strategy was observed during the experiment.
Changing Domains. Many advertisers changed the domains their resources were served from, either by subtly modifying the domain names or by completely changing them through domain generation algorithm style techniques. This happened 1,612 times and does not take into account resources that were moved to the first party. For example, the URL https://c. betrad.com/geo/ba.js?r170201 was blocked by the rule ||betrad.comˆ$third-party. The resource was moved to a new domain, c.evidon.com, to avoid being blocked.
In total, resources were moved from 100 distinct domains to 157 distinct domains, representing a total of 195 distinct combinations of domains. The two most frequent transitions are resources moved from pagead2.googlesyndication. com to google.com and from cs03.etcodes.com to cs03. et-cod.com. The former occurred 499 times and the latter 185 times. Concerning the latter, requests originating from cs03.etcodes.com were blocked by the rule ||etcodes.comˆ$third-party. We observe that the advertiser changed the domain that served the resources so that it looks the same when observed by a human but that does not match the filter anymore.
Moving Resources to the First Party. Advertisers avoided EasyList rules by moving resources from third-party domains to the first party. It happened 84 times, among which 23 times resources were moved to another sub-domain of the first party.
For example, we observed the domain cnn.com including resources from ssl.cdn.turner.com, which was blocked by the rule ||turner.comˆ*/ads/. We then observed the same resource being served from cdn.cnn.com directly, which prevented the resource from matching the ||turner.com domain in the filter rule.

Applications
The previous section demonstrates that most rules in EasyList are not useful in common browsing scenarios. These unused rules provide limited-to-no benefit to users, but they carry a cost. Unused rules degrade the performance of ad-blockers by increasing the amount of work that must be performed on every network request. The end result is wasted resources and degraded browser performance.
In this section, we propose two practical applications of the previous sections' findings. First, we demonstrate the benefits of an optimized, reduced EasyList on resource constrained iOS devices. Second, we present a novel EasyList-based filtering strategy targeting desktop extensions, that provides nearly all of the blocking benefits of full EasyList, but with significantly improved performance.

Improving Content Blocking on iOS
We first present how content blocking in iOS differs from content blocking in other platforms. Then, we run a benchmark that measures how the size of a filter list impacts the time to launch a content-blocking application on iOS, and how our findings could help to decrease this time.

Overview of Content Blocking on iOS
iOS and Safari use a different strategy for content blocking than is used by other common OS and browsers 19 . In most other browsers and platforms, ad-blockers receive each request as an object, containing the URL of the resource being requested, along with other relevant metadata. The extension can then apply whatever logic is desired to determine whether the request should be blocked. In most content blocking systems, this results in a large number of regular expressions (or similar text patterns) applied to the URL, along with some optimization to limit the number of rules that need to be considered.
iOS and Safari use a different approach, where extensions filter requests by declaring a static set of rules in a custom JSON format. This protects the user from malicious extensions (since extensions cannot inject tracking or similar logic into their extensions), at the cost of requiring all rules be expressed in a static rule set that is less expressive than the EasyList format. The result is that EasyList is generally expanded from EasyList's more compact rule format to a larger number of iOS-compatible rules.
Limits. There are two relevant limitations in iOS's blocking approach. First, iOS enforces a limit of 50K rules, to prevent extensions from degrading browsing performance. While this limit is not written in the Apple documentation, the main ad-blocking applications report on this limit. 20 Since Easylist alone contains 40K network rules, little room is left for other lists such as EasyPrivacy for further privacy. Thus, if a user wants to use another list such as EasyPrivacy to improve her privacy, she cannot use all the rules because of the 50K limit.
Second, iOS compiles these filter rules into a binary format each time rules are updated. Users cannot use the application during the compilation. As we show in the benchmark we conduct, users may have to wait for 14 seconds (or more) when a list composed of 40K rules is compiled, which significantly decreases the user experience. This is particularly unacceptable when launching an app for the first time when tricks like background compilation cannot be used to hide the cost from users.

Benchmark
Approach. Our approach here is to decrease the compilation cost (and increase the ability of users to include other lists of rules) on iOS devices by only compiling filter rules that are likely to be useful, instead of the full set of 40k rules. We show that reducing EasyList to only its useful rules provides a dramatically improved initial launch experience for users, and gives users more flexibility to apply additional blocking lists. Evaluation Methodology. We first measure the costs of compiling different sizes of filter lists on different popular iOS devices. We generate lists that contain between 1,000 and 40,000 rules randomly selected from the set of network and exception rules in EasyList. For each of the lists, we use a fork of the "ab2cb" library 21 to convert the rules from the Adblock Plus format to the iOS JSON format. Then, for each device and each list, we compile each iOS filter list 5 times and report the average compilation time.
Results. Figure 9 shows the average compilation time for each device and each selected list size. The figure shows that for a given device, the compilation times grows linearly with respect to the number of rules. While on average it takes 0.24 second to compile a list composed of 1,000 rules on an iPhone X, it grows to 7.4 seconds for a list composed of 40,000 rules. Device kind also impacts compilation time. For example, compiling 40k rules on an iPhone 6s takes, on average, 11.62s, or 7 seconds longer than on an iPhone X.
Thus, keeping only active rules has two main benefits in the case of ad-blockers running on iOS and Safari. First, it allows users to enjoy the benefits of EasyList while remaining well under the platform's 50K rule-limit. And second, it dramatically decreases the required compilation time for the first time the application is launched.

Improving ad-blocking performance
In this section, we leverage the fact the most of the EasyList rules are unused to propose a filtering strategy that provides nearly all of the blocking benefits of traditional ad-blockers 21 https://github.com/brave/ab2cb while improving the time to filter requests. We describe our technique in three steps. First, we describe how current tools use EasyList for blocking (treating AdBlock Plus, the most popular of such tools 22 , as representative of extensions using EasyList). Second, we present a straw-man blocking strategy that only applies frequently used filter rules. Third, we propose a novel hybrid strategy, that achieves nearly the accuracy of existing techniques, with the performance improvements of the straw-man strategy.
The section concludes with an evaluation of the three above strategies on a representative sample of the web. We find that our novel hybrid approach achieves over 99% of the coverage of the current most popular EasyList tool, but performs 62.5% faster. Because of the nature of the optimizations in this hybrid strategy, we expect it could be applied to other EasyList consuming tools to achieve similar performance improvements.

Existing and Proposed Blocking Strategies
This subsection presents three strategies for applying EasyList to the web. The first strategy is based on how existing Ea-syList based filters work. The second strategy only applies the subset of EasyList that is likely to be useful to users (as determined by the measurements in Section 4). Rather than a potential candidate for implementation, this best effort strategy is included as an upper bound of attainable performance. Finally, we describe a novel blocking strategy that approximates both the full coverage of the existing strategy and the upper bound on performance from the second strategy. Strategy One: Synchronous Full EasyList. Current Ea-syList tools decide whether a network request should be allowed by checking the URL of the request (along with some other information, such as the type of resource being requested) against every "network" rule in EasyList. More specifically, these tools follow the following steps.
1. Use hardcoded heuristics, such as not blocking top-level documents or requests coming from non-web protocols. If any of these heuristics match, allow the request.
2. Check the requested URL against the small number "exception" rules in EasyList. If any "exception" rules match, allow the request.
3. See if the requested URL matches any of the "network" rules in EasyList. If any "network" rule matches, block the request.
We note two performance impacting aspects of this strategy. First, it performs a large number of unnecessary computation, since every "exception" and "network" rule in EasyList is 22 https://data.firefox.com/dashboard/usage-behavior applied to outgoing request, even though the vast majority (over 90.16%) are very unlikely to be useful (again, based on the measurements described in Section 4). Second, this wasteful computation adds delay to a time-sensitive part of the system. These filter checks are conducted synchronously, blocking all outgoing network requests until all EasyList rules are considered. Strategy Two: Synchronous Reduced List. Next, we describe a straw-man evaluation strategy, that improves performance by only considering the 9.84% of rules expected to be useful. This strategy is otherwise identical to strategy one and differs only in the number of EasyList rules considered. Instead of applying all of EasyList's 38,710 "network" and "exception" rules, this strategy only evaluates the 4, 038 rules observed during the online measurements discussed in Section 4. The expected trade-off here is performance for coverage since resources that match rarely used filters will be allowed. Strategy Three: Synchronous Reduced List, Asynchronous Complementary List. Finally, we present our proposed blocking strategy, a hybrid strategy that achieves nearly the coverage that full EasyList provides while achieving the performance improvements of the reduced list. Figure 10 provides an overview of the hybrid strategy.
This strategy uses two steps: 1. A synchronous, request-time matcher, that operates before each request is issued, but with a reduced version of EasyList.
2. An asynchronous background matcher, that applies the uncommon-tail of EasyList, but only when a request has been allowed by the previous step.
The first step is identical to strategy two. Every outgoing network request is intercepted and blocked until the frequentlyused subset of EasyList rules is considered. The step's goal is to minimize how long network requests are blocked, by minimizing the amount of synchronous work. The result is that benign network requests complete more quickly than in strategy one (e.g. current blocking tools). The second step applies the remaining, long-tail of Ea-syList rules, but at a less performance-sensitive moment. If a network request is allowed by the first step, the request is issued, but the browser continues checking the now-issued URL against the rest of EasyList. This continued checking is done asynchronously so that it has minimal effect on the load time of the page.
If the asynchronous checker finds any rules that match the URL of the now-issued request, that rule is added to the set of rules applied by the synchronous matcher so that it will be quickly blocked in the future.
The result of this hybrid strategy is that commonly blocked requests are blocked quicker (because the synchronous blocking step is considering a smaller rule set), benign requests complete faster (again, because of the reduced rule list used in the synchronous blocker), and rare-but-undesirable URLs are adjusted to (because the asynchronous matcher moves matching filter rules into the synchronously-applied set).

Evaluation Methodology
In this section, we present a methodology for comparing the performance and blocking coverage of different EasyList application strategies. The goal of this methodology is to understand how accuracy and performance trade off against each other and to empirically compare the above-mentioned strategies. We implemented each of the above strategies in the version AdBlock Plus for Chrome available on Github 23 as of July 5th, 2018. In all strategies, we instrumented AdBlock Plus to measure the amount of time needed to evaluate each outgoing network request against EasyList (or the relevant subset of EasyList). For the hybrid approach, we also added timing measurements to the asynchronous step.
We evaluated each of the three blocking strategies against the same selection of popular and unpopular websites discussed in Section 4. As before, these websites are intended to represent both the most common websites users interact with, and the less popular websites in the web's long tail.
We conduct the crawl on an AWS T2 medium instance with 2 virtual CPUs and 4GB of RAM. Since Chromium does not support extensions in headless mode, 24 we use stock Chromium rendered with XVFB, and automated the system 23 https://github.com/adblockplus/adblockpluschrome 24 https://bugs.chromium.org/p/chromium/issues/detail?id=706008 with the Puppeteer library 25 . All experiments were conducted with caching disabled.
For each of the three strategies, we visited each of the 10K websites in our sample. We allowed each website five seconds to respond and then allowed each website to execute for two seconds. The extension measures the time taken by AdBlock Plus (modified or stock) to decide whether to block each network request on each page. Table 2 presents the results of applying the above evaluation methodology against each of the three blocking strategies.

Performance of Blocking Strategies
The first row presents measurements for the stock AdBlock Plus implementation, which uses a synchronous blocking strategy for all of EasyList. Unsurprisingly, this strategy takes the longest time of the three to determine whether to block a network request, 0.56 ms on average, with a median time of 0.30 ms and a 90th percentile of 0.50 ms. We note that this time is spent blocking each network request, which greatly impacts page load time.
The second row shows the performance of the second strategy; reducing EasyList to its most frequently used rules, and applying that reduced list synchronously. The result of this strategy is faster performance, but with a non-trivial number of false positives and false negatives occurring during blocking. Requests are decided in 0.19 ms on average, with faster median and 90th percentile times. The tradeoff is that blocking accuracy is reduced. The number of network requests blocked goes up, as a result of some "exception" rules being removed from the EasyList set. Similarly, privacy is reduced, as nearly 18,000 more third-parties are contacted during the evaluation, a result of some "network" rules missing in the reduced EasyList set that would have been useful.
Finally, the third through fifth rows present the evaluation of the hybrid strategy. Rows four and five give measurements of the synchronous and asynchronous modules of the hybrid strategy separately, while row three presents the combined effect. The most significant results of our evaluation are the following.
First, the synchronous module takes 0.21 ms on average to process a request. Thus, perceived blocking time is reduced (compared to stock AdBlock Plus) by 62.5% (Research Question 6). Second, the hybrid strategy provides blocking coverage nearly identical to stock AdBlock Plus (> 99%), with only 138 false negatives on 10, 000 websites visited. The 48 "exception" rule errors do not impact the user since the rules that would have been excepted were not added to EasyList. Third, the evaluation shows the adaptive benefit of the hybrid model. The hybrid approach initially applied 3,259 rules synchronously, but after the 10,000 site evaluation, 186 rules from the uncommon asynchronous set were added to the synchronous set.  Finally, we note the finding that the asynchronous portion of the hybrid approach applies its 35K rules faster than the reduced-list synchronous approach, which considers only 3,259 rules. This surprising observation is explained by the synchronous portion of the hybrid approach doing some work (e.g. what kind of resource is being fetched) that can be reused in the asynchronous step.
Overall, we find that the hybrid approach is a successful, performant strategy, especially when compared to current popular blocking tools. By building on the findings discussed in previous sections, the hybrid strategy is able to consider only the subset of EasyList that is likely to be useful in the performance critical path and can put off evaluating EasyList's to when it is less performance impacting. Further, the hybrid approach achieves these performance improvements with a minimal effect on blocking accuracy.

Limitations
The findings in this study depend on having a sample of the web that generalizes to the types of websites users visit and spend time on. We treat the Alexa 5K, along with a sampling of less popular websites, as representative of typical browsing patterns. While we expect this set to be a good representative of the web as a whole (largely because the highly skewed distribution of website popularity means the most popular sites represent the majority of most user's browsing time), we note it here as a possible limitation.
Similarly, our results may not generalize to localities that are not well represented by the Alexa global rankings. Reproducing our crawl methodology in sites more popular in those regions would be a necessary step to generate locally applicable results.
All of our results were generated from automated crawls, which also may have affected how generalizable our results are. It is possible that different kinds of resources are fetched and so different parts of EasyList are used, when users interact with websites in particular ways, such as logging in or using web-app like functionality. How generalizable automated crawl results are to the browsing experiences of real users is a frequently acknowledged issue in measurement studies (e.g. [20]), and one we hope the community can address with future work.
Additionally, all crawling done in this work was carried out from well known AWS IP addresses. This means that the results may be affected by the kinds of anti-crawling techniques sometimes deployed against Amazon IP addresses. This, in turn, could have affected the number and distribution of ads observed during measurement. While this is a common limitation of this kind of web-scale measurement, we note it as another limitation of the work.
Finally, our results consider every blocking action as equally useful. In our measurements, a rule that blocks ten resources is implicitly ten times more useful than a rule that only blocks one request. It is possible, though, that a less frequently used rule may be more beneficial to the user than a frequently used rule if the infrequently blocked rule is blocking a very malicious or performance harming resource. We acknowledge this limitation, but treat the question of "how beneficial is it to the user to block a given resource" beyond the scope of this work.

Related work
Online tracking. Recent studies document a growth of thirdparty tracking on the web [2,11]. Yu et al. [23] found an increase in analytics services and social widgets. Englehardt et al [2] showed tracking code on more than 10% of the websites of the top Alexa 1M. Libert et al [13] showed that 180k pages of the top 1M Alexa websites had cookies spawned by the DoubleClick domain, a behavioral advertising company.
Defenses against tracking. The NoScript extension 26 enables to prevent JavaScript execution. While this approach blocks trackers, it also breaks websites that use JavaScript for legitimate purposes. This trade-off between privacy and usability is important. Yu et al. [23] find that privacy tools that break legitimate websites may lead to users deactivating such tools, harming user privacy. The most popular kind of tracking protection is browser extensions such as Ghostery, Disconnect or uBlock origin, as well as browsers such as Brave or Safari that enable to block third-party requests.
A variety of strategies have been proposed for identifying unwanted web resources. Privacy Badger uses a learningbased approach. Iqbal et al. [9] also proposed a machine learning approach that considers features extracted from HTML elements, HTTP requests, and JavaScript to determine if a request should be blocked. Storey et al. [21] propose a visual recognition approach targeting legally mandated advertising identifiers. Yu et al [23] proposed a crowdsourced approach where users collectively identify data elements that could be used to uniquely identify users. The majority of anti-tracking and ad-blocking tools rely on filter lists. Different studies [3,18] show that tracker blockers and adblockers are popular among the general population. Malloy et al [14] showed that depending on the country, between 16% and 37% of the Internet users had an ad-blocker installed. Mathur et al [15] found that most users of anti-tracking tools use the tools to avoid advertising. Effectiveness of anti-tracking tools. Gervais et al. [5] quantified the privacy provided by the main ad-blockers. They show that on average, using an ad-blocker with the default configuration reduce the number of third parties loaded by 40%. Merzdovnik et al. [16] showed that rule-based approaches can outperform Privacy Badger's learning-based approach. They also show that extensions that rely on community-based lists are less effective than extensions based on proprietary lists such as Disconnect or Ghostery when used with the correct settings. Their study demonstrates that besides blocking trackers, most of these extensions have a negligible CPU overhead. In some cases, it even leads to a decrease in the overall CPU usage of the browser. Maintaining filter lists. In order to keep up with new domains creating and domains changing their behavior, it is crucial to maintain filter lists. Because it is a cumbersome task and it needs to be done carefully not to break websites, Gugelmann et al. [6] proposed an automated approach that relies on a set of web traffic features to identify privacy invasive services and thus help developers maintaining filter lists.
Researchers have documented several strategies that advertisers use to evade blocking strategies. Wang et al [22] found advertisers randomizing HTML identifiers and structure. Facebook has applied this technique as well [1]. Adversity has also been discussed by recent studies on anti-adblockers [8,17,25], i.e. scripts whose purpose is to detect and block ad-blockers to deliver advertising to more users. Iqbal et al. [8] conducted a retrospective measurement study of anti ad-block filter lists using the Wayback machine. They applied the Anti-Adblock Killer List, the most active anti ad-blocker list, on historical snapshots of Alexa top-5K, and measured that the list triggers only on 8.7% of the websites. They also show that similarly to EasyList, these anti ad-block lists keep growing over time. While their approach enables detection of advertisers that asks users to deactivate their ad-blockers to show them ads, the approach we propose in Section 4.3 focuses on advertisers that bypass filter rules stealthily, i.e. without interacting with the users.

Conclusion
This paper studies EasyList, the most popular filter list used for blocking advertising and tracking related content on the web. We find that the vast majority of rules in EasyList are rarely, if ever, used in common browsing scenarios. We measure the number of these "dead weight" rules, and effect on browser performance, through comparison with alternative, data-driven EasyList application strategies. We find that by separating the wheat from the chaff, and identifying the small subset of EasyList filter rules that provide common benefit for users, EasyList's benefits can be efficiently enjoyed on performance constrained mobile devices. We also use these findings to propose an alternate blocking strategy on desktops that improves performance by 62.5%, while capturing over > 99% of the benefit of EasyList.
More broadly, we hope this work will inform how similar crowdsourced security and privacy tools are developed and maintained. As previous work [10] has identified, such lists tend to accumulate cruft as they accumulate new rules. Over time, the benefit of such tools risks being outweighed by the amount of dead weight pulled with them. We hope the findings in this work highlight the need for regular pruning of these lists, to keep them lean and as helpful to users as possible.