Robotic Motion Planning using Learned Critical Sources and Local Sampling

Sampling based methods are widely used for robotic motion planning. Traditionally, these samples are drawn from probabilistic ( or deterministic ) distributions to cover the state space uniformly. Despite being probabilistically complete, they fail to find a feasible path in a reasonable amount of time in constrained environments where it is essential to go through narrow passages (bottleneck regions). Current state of the art techniques train a learning model (learner) to predict samples selectively on these bottleneck regions. However, these algorithms depend completely on samples generated by this learner to navigate through the bottleneck regions. As the complexity of the planning problem increases, the amount of data and time required to make this learner robust to fine variations in the structure of the workspace becomes computationally intractable. In this work, we present (1) an efficient and robust method to use a learner to locate the bottleneck regions and (2) two algorithms that use local sampling methods to leverage the location of these bottleneck regions for efficient motion planning while maintaining probabilistic completeness. We test our algorithms on 2 dimensional planning problems and 7 dimensional robotic arm planning, and report significant gains over heuristics as well as learned baselines.

I. I
We examine the problem of using prior experience for sampling based motion planning in robots. Sampling based motion planning (SBMP) algorithms construct a graph or roadmap as a discrete representation of the state space of a robot. The vertices of this roadmap represent robot configurations and edges represent potential movements of the robot. A graph search algorithm is then used to find the path between any two vertices in the roadmap. Rapidly Exploring Random Tree (RRT) [17] is a tree growing variant of SBMP that creates this roadmap (tree) implicitly while planning. SBMP is state of the art in high dimensional spaces. A defining feature of SBMP is itâĂŹs reliance on the sampler. Traditionally, these samples are generated either probabilistically or deterministically [8] to uniformly cover the state space. Such a sampling approach allows arbitrarily accurate representations (in the limit of the number of samples approaching infinity), and thus allows theoretical guarantees on completeness. However, in environments where paths pass through narrow passages, these algorithms become computationally intractable. This is because a huge number of samples must be generated to cover these narrow passages. Thus, the main challenge in sampling based algorithms is to place a small set of samples (critical samples) on certain key *All four authors contributed equally to this research. 1   locations (bottleneck regions) to enable the algorithm to find a high quality path with low computation effort. Current state of the art approaches [1], [2] use learning algorithms (called learners hereon) to predict these critical samples. These samples are then connected to the nodes of a uniform sparse graph to construct a roadmap. Depending on the structure of the bottleneck regions (say in an extended narrow passage or semicircular tube like structure), the learner is required to place a small set of critical samples in accordance with the local structure at each bottleneck. The graph created by connecting these critical samples among themselves acts as a bridge for connecting the disjoint subgraphs (connected components) present in the sparse graph. Thus, the learner needs to not only identify the bottleneck regions but also propose samples in accordance with their local structure. This brings us to two major challenges faced by these approaches. Firstly, the learners used in these approaches are commonly fed an occupancy grid among other parameters as a representation of the workspace of a robot. There exists a trade-off between the size of the occupancy grid and, amount of data and time taken by the model to converge. In complex planning problems, the size of this occupancy grid must be large. However, this makes the convergence of the model computationally intractable. On the other hand, a decrease in the size of the occupancy grid results in low resolution and thus the learner is not able to learn the internal representation of these bottleneck regions. Thus, a large number of the generated samples are rendered useless. Secondly, most of the learners are conditioned only on the planning problem and not on the prior samples it has generated. Thus, the learner tends to repeatedly sample similar points inside a bottleneck region, leading to redundant samples.
Our key insight is to rely on the learner to identify the location of the bottleneck regions and then exploit the property of planners such as RRT to cover the local structure of these bottleneck regions. Therefore, getting a set of samples from the learner that includes a single sample in each bottleneck region is sufficient. As we expect the learner to generate a single sample per bottleneck region, we propose to convolve the occupancy grid using a kernel to create a smaller grid that contains information relevant for this generation. We use this preprocessed grid during training and for testing the learner. We thus use the learner to get this initial set of critical samples (one per bottleneck region) and call them critical sources. We then generate our required set of critical samples from these critical sources using local sampling-based methods. This solves the first challenge faced by current algorithms, as using a smaller grid as input to the learner makes it converge faster to generalizing well over planning problems that have similar global structure for the location of bottleneck regions but different local structures within these regions This also solves the second challenge as we condition the subsequent samples on our current set of critical samples. The job is therefore divided between the learner (generate the critical sources) and the local sampler (procure the required set of critical samples by using these critical sources to generate subsequent samples). We argue that this is similar to how we, as humans, given a planning problem, first globally identify the doorways present relevant to our planning problem and then locally explore how to navigate through these doorways. Due to the efficient space filling nature of RRTs, we propose the algorithm: Local Critical Source RRT (LCS−RRT). This algorithm, in conjunction with a sparse graph, uses RRTs rooted at critical sources as the local sampling algorithm. We propose another algorithm, Critical Source-RRT (CS−RRT), which forfeits the sparse graphs altogether and incrementally builds RRTs rooted at start, goal and critical sources. In addition to RRTs generating the required set of critical samples, CS−RRT depends on the inherent bias of RRTs to grow towards large unsearched areas of the problem to emulate the sparse graph once the tree is out of the bottleneck region. We thus make the following contributions: 1) We present G C S , a fast methodology that uses learning models efficiently to generate a set of critical samples, ideally one per bottleneck region (called critical sources). 2) We present the algorithm Local Critical Source -RRT (LCS−RRT) which, in conjunction with a sparse graph, uses RRTs rooted at critical sources to generate the required set of critical samples which acts as a bridge between disjoint sub-graphs of the sparse graph. 3) We present the algorithm Critical Source -RRT (CS−RRT) that works by incrementally building RRTs rooted at multiple key sources (start, goal and critical sources). 4) We show that LCS−RRT and CS−RRT outperform the sampling based baselines on a set of R 2 point object and R 7 robotic arm motion planning problems, and prove their probabilistic completeness.

II. R W
An analysis on the shortcomings of using uniform sampling in the presence of narrow passages is given by D. Hsu et. al. [7] . This has stimulated numerous works on using selective densification for non-uniform sampling [9]- [13]. A multitude of these works use adaptive sampling for roadmap densification by exploiting the structure of the environment. While some propose to sample around the obstacles [14], [15], others use heuristic based strategies to trace or locate key samples [9]. Even though these techniques generalize to a large set of problems, they suffer from placing samples in regions where a path is unlikely to traverse. Also, owing to the huge number of collision checks performed, their computation time increases rapidly with increase in dimensionality of the state space. Recent approaches use learning models for non-uniform sampling.
[1]- [6]. Some of them propose to find low dimensional structure in planning [1], [2]. In particular, generative models like conditional variational autoencoder (CVAE) [19] have been used to great success. We use the CVAE used in LEGO [1] (called LEGO−CVAE hereon) as our underlying learning model in G C S and provide a gist of the same below. Note that, although our work uses the model used in LEGO, it can be extended to work with any other learning framework that predicts samples in bottleneck regions [2]- [5].

A. LEGO: Leveraging Experience using Graph Oracles
Leveraging Experience using Graph Oracles is a framework for predicting efficient roadmaps for sampling based motion planning. During training time, LEGO processes a dense graph to identify a sparse subset of key vertices. These vertices are a diverse set of nodes lying on bottleneck regions through which a near optimal path may pass. A CVAE [16] conditioned on the occupancy grid of the workspace, start and goal positions is then trained on these key samples. During test time, given the occupancy grid, start and goal positions, the CVAE generates these key samples which are used in conjunction with a uniform sparse graph to generate a roadmap.

B. CVAE: Conditional Variational Autoencoder
The core component of the LEGO framework is a conditional variational autoencoder (CVAE). It is an extension of traditional variational autoencoder and has been increasingly used to learn low dimensional structure in planning. The addition of conditional parameters helps embed the features of a planning problem as conditions and learn the corresponding representations. Let X be the state space and x ∈ X , z ∈ R L be the latent random variable and y ∈ R m be the conditioning variable. The framework comprises of two deterministic mappingsan encoder and a decoder. An encoder maps (x, y) to a mean and variance value of a Gaussian q φ (z|x, y) in latent space, such that it is "close" to a standard Gaussian N (0, I). The decoder maps this Gaussian and y to a distribution in the output space p θ (x|z, y). This is achieved by maximizing the following function L (x, y; θ, φ): At test time, we use only the decoder to map samples from an isotropic Gaussian in the latent space to samples in the output space. The CVAE is trained by passing in a . y i is the conditional parameter vector extracted from the planning problem. In our case it's (start, goal, occupancy grid). X i is the desired set of nodes extracted from the dense graph G dense that we want our learner to predict. Hence we train the model by maximizing the following objective.
III. P F Let X denote a d−dimensional configuration space. Let X obs ⊆ X be the portion in collision and X free = X \ X obs denote the free space. Let a path ξ : [0, 1] → X be a continuous mapping from index to configurations. A path ξ is said to be collision free if ξ(τ ) ∈ X free for all τ ∈ [0, 1]. Problem: Given a motion planning problem Λ = {x s , x g , X free } where x s ∈ X free is the start configuration and x g ∈ X free is the goal configuration, find a feasible ξ i.e. ξ that is collision free, ξ(0) = x s and ξ(1) = x g . Given a database of prior worlds, the overall goal is to use a conjunction of a learned policy and local sampling based planners to generate a roadmap G which is used by a graph search algorithm A to efficiently compute a feasible path. A , given a graph G, finds and returns a feasible path ξ. If no feasible path exists in the graph, A returns ∅. An ideal roadmap should be sparse enough for A to be efficient. In addition, for problems with narrow passages (bottleneck regions), this roadmap must have a set of critical samples in the bottleneck regions to ensure existence of a feasible path. We assume the graphs to be undirected for simplicity. However, it can easily be extended to directed graphs. The following are the additional notations used in this paper: • G sparse : A sparse graph embedded in the state space of the robot. It is additionally composed with the set of samples generated from the learner and local planners while constructing G by LCS−RRT to ensure a minimal coverage. • CS : Set of critical sources.

IV. A
We propose to identify the location of bottleneck regions using G C S and then use LCS−RRT or CS−RRT to navigate through these bottlenecks using local sampling based planners instead of learning their local structures. if free_count/total_count < threshold then 17 CS ← CS ∪ sample;

return CS;
A. Critical Source Generation G C S identifies the locations of bottleneck regions by generating CS, a set of critical samples, one corresponding to each bottleneck region. It uses LEGO−CVAE as the underlying learner. If an occupancy grid of a certain size is required to learn the locations of the bottleneck regions along with their local structures, we argue that we can preprocess this occupancy grid with a kernel to create a grid of lower dimensions that encodes only the information necessary to learn the locations of the bottleneck regions. The choice of kernel depends on the features of the environment. For example, a dilation kernel can be used in environments which contain extended narrow passages. As we do not expect LEGO−CVAE to learn the local structures, there is no loss of relevant information.
This preprocessed occupancy grid is then used for training and testing LEGO−CVAE. We call the LEGO−CVAE trained with this preprocessed occupancy grid LEGO-G as it only learns global information of the planning problem.
We thus use LEGO-G for generating a set of candidate critical source samples. A sample from this set ∈ CS if (a) it is at least a distance source_sep away from all the critical sources generated up till now (Lines 4-8, Algorithm 1) and (b) if we connect the sample to the vertices of G sparse that are within distance r_critical by edges, the percentage of edges not in collision with the obstacles must be smaller than a certain threshold (Lines 9-17), Algorithm 1).

return
LG;

B. Local Critical Source -RRT
Local Critical Source -RRT (LCS-RRT) uses G -C S to get CS and adds the start and goal vertices to it. It builds G, which contains G sparse and CS. For each CS i , the algorithm maintains two graphs: a tree T i and a local graph LG i . T i is RRT rooted at CS i . LG i consists of edges and vertices of G within distance r from CS i . The goal of the algorithm is to make LG i completely connected by adding edges between the vertices of T i and the vertices of LG not belonging to the connected component of CS i . Initially, for each CS i , both T i and LG i contain only CS i . In an iteration of the outer while loop of LCS-RRT (Line 7, Algorithm 2), E L G expands each LG i to radius r. After expansion, these LGi consist of the subgraph of G within a radius r of CS i (Line 6, Algorithm LG i ← LG i ∪ {rn',edge(rn',nn)}; 12 for n ∈ LN do 13 if V (edge(rn',n)) then 14 LN ← LN -C C (LG i ,n);

return
LG, T ; 2a). E L G and D L G both maintain LN , a set of vertices of the LG i that does not belong to the connected component of CS i . Wherever possible, the nodes of T i , are connected to LN by collision free edges and LN is updated (Lines 8-12, Algorithm 2a). D L G densifies the local graph by growing its T i and adding edges between its T i and the vertices of the set LN until either the LG i is completely connected or M (hyperparameter) iterations have taken place, whichever is earlier. To grow its T i , D L G samples a random node within a radius r of CS i , interpolates it to within a distance of step_size of the vertex nearest to this node in its T i and, if possible, joins them with an edge in a similar fashion to RRT growth (and therefore the name) (Lines 5-10 Algorithm 2a). It then tries to connect this new node of T i with the vertices of LN and wherever a connection is possible, LN is updated (Lines 12-15 Algorithm 2b). After densification, LG is added to G and A is run on G (Lines 10-12 Algorithm 2). If successful, the feasible ξ is returned. Else, the radius r is increased by a factor λ and the process is repeated again and so on. Probabilistic Completeness: Let us consider the local graph LG s at start node CS s at infinite time. As time approaches infinity, so does the radius r. Thus, the goal node is present in the LG s . As we try to connect CS s to all nodes not present in the connected component of CS s using T s , we are at the least running a RRT from start node to goal node. Thus, due to the probabilistic completeness of RRT, LCS−RRT is probabilistically complete.

C. Critical Source -RRT
Critical Source -RRT (CS-RRT) uses G C -S to get CS and adds them to G. It then adds start and goal vertices to G. These nodes subsequently act as the roots of the RRTs we will grow. In each iteration of the outer while loop (Line 3, Algorithm 3), the algorithm iterates through the connected components present in G i.e. the RRTs in a round robin manner. In lines 5-10, the algorithm samples a random node, interpolates it to within a distance of step_size of the vertex nearest to this node in its RRT and loops until it is possible to join them with an edge. This is similar to how a RRT grows (and therefore the name). In lines 11-13 it then tries to connect the new_node of its tree to the nearest vertices of the other trees that lie within a distance of step_size. If a connection is possible, an edge is inserted into the graph (line 14). Insertion of this edge results in merger of the two trees the nodes belonged to. The algorithm returns a feasible path when the start and goal nodes belong to the same connected component of G (Lines 15-17). Probabilistic Completeness: As CS−RRT grows RRTs rooted at start and goal nodes along with the critical sources to connect the start and goal nodes, it runs a RRT-Connect at the least. Thus, due to the probabilistic completeness of RRT-Connect, CS−RRT is probabilistically complete.
V. E In this section, we compare the performance of LCS-RRT and CS-RRT to sampling based algorithms in multiple domains. We evaluate our algorithms against RRT-Connect [18], a variation of RRT that incrementally builds two trees rooted at the start and goal nodes. Additionally, we compare our algorithms with LEGO, a state-of-the-art learning based sampling algorithm. As LEGO is a graph based approach while others are tree based approaches, we adapted LEGO to an anytime algorithm with incremental densification for testing purposes. We have tuned the parameters of RRT-Connect and LEGO to ensure their best performance. Evaluation Procedure: For a given planning problem, we run each algorithm with a fixed timeout. For a given problem domain, each of the learning models used by these algorithms are trained on similar number of planning problems. We evaluate the performance of these algorithms on the metric of time taken to find a feasible path. Problem Domains: We evaluate our algorithms on R 2 and R 7 problem domains. The R 2 problems have random rectilinear walls with extruded narrow passages that have varying local structures (Fig 3). The R 7 problem is a robotic-arm manipulation problem in a cluttered environment. Experiment Details: We compare the algorithms LCS−RRT, CS−RRT, LEGO and RRT-Connect on a testset of 100 planning problems. For the R 2 problems, each learning model is trained on 4000 planning problems for around 30 minutes. The planning timeout for the algorithms is 5 seconds. The size of occupancy grid used by LEGO−CVAE is 50X50. The kernel used by LEGO-G for preproccessing is of size 5X5 (with stride value 5) resulting in an updated occupancy grid of size 10X10 (Fig 5). For the R 7 problems, each learning model is trained on 4000 training problems for 2 hours and the planning timeout for the algorithms is 12 seconds. The code is open sourced and can be found at https://github.com/RKJenamani/CS-RRT. is able to place a sample at each bottleneck region while LEGO−CVAE is not (Fig 2).

VI. C
We show the feasibility of using local sampling algorithms aided by a learning model to rapidly find a feasible path in complex environments containing extended bottleneck regions. These algorithms share the responsibility of generating key samples between the learner and the local sampler. This lets the learning model converge faster to generalizing well over planning problems that have similar global structure for the location of bottleneck regions but different local structures within these regions. As we require the learner to only identify the location of bottleneck regions, we introduce the idea of using a kernel to preprocess the occupancy grids for better learning. In future works, we would like to analyse the relationship between a workspace and the kernel suitable to it. We intend to explore the integration of other sampling based methods to make the approach asymptotically optimal. We would also like to test our algorithms on environments where extended bottleneck regions arise due to differential constraints. R


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.


extfieldsofstudy:
Computer Science
Mathematics

text:
Matrix Decomposition for Massive MIMO Detection

Massive multiple-input multiple-output (MIMO) is a key technology for fifth generation (5G) communication system. MIMO symbol detection is one of the most computationally intensive tasks for a massive MIMO baseband receiver. In this paper, we analyze matrix decomposition algorithms for massive MIMO systems, which were traditionally used for small-scale MIMO detection due to their numerical stability and modular design. We present the computational complexity of linear detection mechanisms based on QR, Cholesky and LDL-decomposition algorithms for different massive MIMO configurations. We compare them with the state-of-art approximate inversion-based massive MIMO detection methods. The results provide important insights for system and very large-scale integration (VLSI) designers to select appropriate massive MIMO detection algorithms according to their requirement.

I. INTRODUCTION
Massive MIMO is a key technology for fifth generation (5G) communication systems to achieve very high performance within the available radio spectrum. It is an extension of conventional small-scale MIMO, where a large number of antennas are used at the base station (BS) which serves a large number of users to achieve high data throughput and spectral efficiency [1], [2]. Massive MIMO can provide uniform good service to the user terminals with a high mobility environment. However, the benefit of massive MIMO systems come with the disadvantage of computational complexity. The complexity of symbol detection algorithms grows exponentially as the number of antennas increase in a massive MIMO system [3]. Due to the high number of antennas, conventional linear detectors also require large matrix inversion. Hence, in the past decade, a new class of detectors based on approximate inversion has become a popular choice in very large-scale integration (VLSI) implementation.
Approximate inversion-based detectors (AID) utilize channel hardening properties of massive MIMO systems to calculate the Gramian matrix inversion. This class of detectors work well for certain configurations of massive MIMO systems, for example, when the ratio between numbers of BS antennas and users is large [4]. However, their performance starts to become unstable when this ratio gets smaller. Therefore, the focus has been again shifting towards exact inversion-based linear detectors for their guaranteed performance and robustness [5]- [8]. As the semiconductor technology has also matured greatly over the past decade, the focus has been shifting towards applying better system design than saving every possible logic gate. Telecommunication industries are not always interested in saving logic area by adopting an unstable and risky solutions for their products. Therefore, we envision that exact inversionbased solutions will be more popular in the future for massive MIMO VLSI community.
Matrix decomposition algorithms have been extensively utilized for the matrix inversion procedure of small-scale MIMO detection. They provide better numerical stability over straightforward inversion methods. In addition, they help to achieve a modular design, where the whole procedure can be divided and distributed between different developers. A few popular matrix decomposition algorithms for linear detection are QR, Cholesky and LDL decomposition. Despite the importance of the matrix decomposition algorithms, their complexity analysis for massive MIMO and comparison with existing AID is lacking in the literature. An analysis of matrix decomposition algorithms for small-scale MIMO detection can be found in [9]. A comparison of explicit vs. implicit approximate inversion has been provided in [10]. However, [9] does not address the complexity from massive MIMO perspective and [10] does not focus on the complexity of matrix decomposition algorithms.
In this paper, we address this timely topic and analyze the computation complexity of matrix decomposition algorithms for massive MIMO. We also compare them with the state-ofart AID for the massive MIMO. Several hard output simulations to support our premise regarding different detection mechanisms are also presented in this paper. We believe these results will provide an important guideline to the VLSI designers to select the appropriate algorithms that is suitable to the product requirements.
The rest of the paper is organized in the following way: In Section II, we discuss the system model of a massive MIMO system. We also discuss linear detection, non-linear detection in this section. In Section III, we introduce AID and provide simulation results to demonstrate their instability for different antenna configurations. In Section IV, we present different matrix decomposition algorithms, and their application in different types of detection methods with simulation results. In Section V, we present the complexity analysis and compare with state-of-the-art AID methods. The conclusion is drawn in Section VI.

II. SYSTEM MODEL AND DETECTION METHODS
A massive multi-user MIMO base-station (BS) with N antennas is considered. We assume U single antenna users are transmitting towards the BS, where U ≤ N . Assuming that the channel between the users and BS antennas is frequency flat, the relationship between the transmit and receive vector can be characterized as where y ∈ C B is a received signal vector, x ∈ C U is a transmit symbol vector, H ∈ C B×U is a channel matrix, and n ∈ C B is a circularly symmetric complex white Gaussian noise vector with zero mean and σ 2 noise variance. The system is presented in Fig. 7.
Communication Channel

A. Linear Detection
A MIMO symbol detector determines the transmitted symbol vector x from the received signal vector y. The two most popular linear detection are zero-forcing (ZF) and linear minimum mean-square error (MMSE) equalization. The ZF algorithm does not consider the effect of noise vector n, inverts the channel matrix H to determine the transmitted vector. Therefore, the ZF detection can be expressed as where H † is a pseudo-inverse of H. The ZF detector requires an inversion of the Gramian matrix, G, where G ZF = H H H. The MMSE detector is an improvement over the ZF, which takes the noise into account. MMSE detection can be expressed asx where I U is the U × U identity matrix. The Gramian matrix is modified with a regularization by noise variance for MMSE, i.e.,

B. Non-linear Detection
The earliest massive MIMO detectors are iterative nonlinear detectors, which are initialized with a linear detector, and in subsequent iterations tries to update the results. Example of such detectors include likelihood ascent search (LAS), reactive tabu search (RTS), CHEMP etc. We present a nonlinear detector called ADMM-based Infinity-Norm Detection (ADMIN), proposed in [11], to show how these non-linear detectors for massive MIMO works in general.
ADMIN solves a box-constrained detection problem with a convex optimization method called alternating direction method of multipliers (ADMM). The ADMM method can be used to solve a convex problem by breaking it into smaller problems in an iterative fashion. The first iteration of ADMIN has been presented as, where β is an scaled form of σ 2 I. The values of z and λ λ λ vectors are calculated with two other iterations of ADMIN. When z and λ λ λ are initialized with zeros, (4) resembles the MMSE equation. Thus, the ADMIN detection method is also based on an inversion of a regularized Gramian matrix,

III. INSTABILITY OF APPROXIMATE INVERSION-BASED DETECTION
The exact inversion of the Gramian can be complex when the number of users increases. For example, Gramian of a 16user system (U = 16) will be a 16 × 16 matrix. Several AID became popular in the VLSI community over the past decade due to their less complexity. We present three such detectors in this section and analyze their error-rate performance with Matlab simulations.

A. Neumann Series Approximation
Gramian matrix G can be decomposed into a diagonal matrix (X) and off-diagonal matrix (E) as G = X + E. The Neuman series approximation (NSA) [12] of such a system can be expressed as NSA only use inversions of the diagonal matrix, X, which can be achieved with reciprocals of the diagonal elements. Both precision and complexity of the inversion increases with more iterations.

B. Gauss-Seidel Method
In Gauss-Seidel (GS) method, G can be decomposed as G = D+L+R, where D, L and R are the diagonal component, the strictly lower triangular component, and strictly upper triangular component, respectively. The GS can be used to estimate the transmitted signal vectorx aŝ wherex MF = H H y is a matched filter [13].

C. Conjugate Gradient Method
Conjugate Gradient (CG) is another approximate method used in the MIMO detection which can be formulated aŝ where p (n) is the conjugate direction with respect to the Gramian matrix and α (n) is a scalar parameter which is commonly known as the step size [14].

D. Error-rate Performance
We present error-rate simulation results for exact inversionbased MMSE, and approximate inversion-based NSA, GS, and CG detection methods. We have considered t = 3 iterations of NSA, GS and CG detection methods. The bit error rate (BER) of the detectors with respect to signal-to-noise (SNR) ratios is shown in Figs 2-4. Here, we used 10,000 Monte-Carlo trials for all simulations. The modulation scheme for these simulations is 64QAM. We consider an i.i.d. Rayleigh fading channel between the BS and users. In Fig. 2, the BER for 256-antenna BS and 16 users is presented. Here, the NSA, GS, and CG present very similar performance and perform as well as the exact inversion-based MMSE. In Fig. 3, simulations have been taken for 32 antenna BS and for 16 users. Here, all AID performs poorly and can not detect received symbol vectors properly. In Fig. 4, simulations have been taken for 64 BS antennas and 16 users. Here, NSA and CG detectors can not detect received symbol. However, GS detection method provides good performance in this scenario where the MMSE provides only 2 dB gain over the GS in this scenario. It is evident from the simulations above that all AID works very well and can provide a competitive solution compared to MMSE when the ratio between the BS antennas and number of users is high. Therefore, for such a system, it is possible to select low complexity AID methods. However, RF chains and front-end logic associated with the antennas are expensive. Therefore, having large number of antennas for a very small number of users are not always feasible from design and cost perspective. When the ratio of numbers between BS antennas and users becomes smaller, performance of AID starts to deteriorate as seen in Figs. 3 and 4. In extreme cases, when the ratio becomes close or equal to 1, these detectors do not function at all and fail to detect incoming symbol vectors. In a nutshell, the performance of these detectors is not stable and as the industry has to support various configurations for their product, such detectors might not be the ideal solution for them. Therefore, exact inversion-based detectors are still going to be an attractive solution for industries for years to come.

IV. MATRIX DECOMPOSITION ALGORITHMS
Instead of doing a straightforward matrix inversion, several matrix decomposition methods can be used which are more numerically stable. They also bring a modular design, where an inversion process can be split into parts. Here, we mainly focus on inverting the regularized Gramian matrix, which is used in the MMSE equalization. In this section, we analyze how three popular matrix decomposition algorithms, i.e. QR, Cholesky and LDLT can be applied to find the MMSE solution.

A. MMSE with QR
QR decomposition algorithm decomposes a U × U matrix A as A = QR. Here, Q is an U × U unitary matrix with orthogonal columns and R is an U ×U upper triangular matrix with non-zero diagonal elements. QR decomposition can be applied to obtain the MMSE solution as There are several algorithms to compute the QR decomposition, such as, Gram-Schmidt process, Householder transformations, Givens rotation etc. We focus on Gram-Schmidt process in this paper.

B. MMSE with Cholesky
Cholesky is another popular decomposition algorithm which utilizes a U × U lower triangular matrix L to decompose a U × U matrix A as A = LL H . The MMSE can be calculated asx Here,z can be calculated by forward substitution andx can be solved by backward substitution.

C. MMSE with LDL
LDL is another popular decomposition algorithm which decomposes a U × U matrix A as A = LDL H , where D is a diagonal matrix and L is a lower triangular matrix with zeros as diagonal. The MMSE can be calculated with the LDL asx Similar to Cholesky,z can be calculated by forward substitution andx can be solved by backward substitution.

D. Error-rate Performance
We present error-rate performance of MMSE, ADMIN and single-input multiple-output (SIMO) in Fig. 5 and 6. Similar to earlier simulations, 10,000 Monte-Carlo trials are used. The communication channel between BS and users is assumed to be i.i.d. Rayleigh Fading channel. The MMSE utilizes QR and ADMIN utilizes LDL decomposition in these simulations. We take t = 5 iterations of ADMIN in this simulations. In Fig. 5, the detectors are simulated for 32 BS antennas supporting 32 users transmitting with 64-QAM. It can be noticed that even the exact matrix inversion-based MMSE can not provide a satisfactory performance with high power, i.e., can not bring the error-rate below 10 −2 with approximately 35 dB of SNR. ADMIN provides about 5 dB gain over MMSE, which is a significant margin for communication systems using higher order modulation. Fig. 4 shows, when the ratio of numbers between BS antennas and users is small, non-linear detectors are required for necessary performance gain. Most of these non-linear detectors are based on exact inversion and matrix decomposition algorithms will be crucial for their implementation. The non-linear detectors can also provide very high gain compared to MMSE for other scenarios. In Fig. 5, ADMIN with t = 5 iterations can provide around 10 dB gain over MMSE algorithm. In this case, the difference between the SIMO bound and ADMIN is less than 10 dB.

V. COMPLEXITY ANALYSIS
We analyze the complexity of matrix decomposition algorithms in this section. First, we explain in detail how we computed the complexity of QR decomposition based on classical Gram-Schmidt process. We calculate the complexity of Gram-Schmidt applied on a U × U matrix because the Gramian is always square in the MMSE. Real multiplications dictate the overall complexity of an algorithm as they take significantly more logic than additions or subtractions. Therefore, we focus on real multiplications for comparing the algorithms. Classical Gram-Schmidt algorithm is presented in Algorithm 1.
In line 3 of Algorithm 1, norm of a vector is computed as r i,i = q i 2 . For norm calculation, we need a total of U 2 number of complex multiplications. Here, U number of multiplications are required for a single norm and we need a total of U norms. For q i = q i /r i,i , a total of U reciprocals Algorithm 1 Classical Gram-Schmidt input: A outputs: Q, R 1: Q = A 2: for i = 1, . . . , U 3: for j = i + 1, . . . , U 6: q j = q j − r i,j q i 8: end 9: end needed to compute 1 ri,i and these real-valued reciprocals will be multiplied U 2 times to the complex valued q i . Thus, a total 2U 2 real multiplications are needed for line 4. Next, r i,j = q H i q j implies a vectorvector multiplication where each vector has U complex elements. Therefore, we need U number of complex multiplications for a single q j . Here, we have U number of complex multiplications for r i,j q i . Similarly, we get a total of U (U −1) 2 U multiplication for r i,j q i . The operations are presented in Table I. 3 Therefore, we get the total number of complex multiplication (CM) for Gram-Schmidt as We assume, a complex-complex scalar multiplication hardware unit utilizes four real multiplication units and a real-complex scalar multiplication unit utilize two real multiplication units. Therefore, we get 4U 3 real multiplication from the U 3 complex multiplication. We add this with number of real multiplications (RM) for line 4, which leads to Similarly, we calculate the number of multiplications required for Cholesky decomposition from Algorithm 2. A total of U (U −1) 2 complex multiplication is required to compute the diagonal elements of L (line 3). The off-diagonal elements require a total of U 3 −3U 2 +2U 6 complex multiplication (line 5). Therefore, the total number of complex multiplication is Algorithm 2 Cholesky Decomposition input: A outputs: L 1: for i = 1, . . . , U 2: j = 1, . . . , i − 1 3: Computation of Cholesky also requires a U number of recipro- , which are then multiplied in line 5. Therefore, we require an additional U (U −1) real multiplications. Therefore, the total number of real-multiplication is The complexity of LDL decomposition is very similar to that of Cholesky with an additional 4U (U −1) real multiplications. We provide Table II with more detail of the operations required for the matrix decomposition algorithms. The number of real multiplication, addition and subtractions for QR is significantly higher than Cholesky and LDL decomposition. The complexity of Cholesky and LDL are almost similar except the additional multiplication required for LDL and the square root operations required for Cholesky.

A. Comparison against approximate inversion-based detectors
A comparison of the matrix decomposition algorithms and the AID methods is presented in Table III. All the matrix decomposition algorithms and NSA scale with U 3 while GS and CG methods scale with U 2 in terms of operations. The cubic complexity of NSA originates from the matrix multiplications associated with every iteration t in (X −1 E) t . For example, for t = 3, we have to compute a P * P * P where P = X −1 E. In Fig. 7, matrix decomposition algorithms and the AID methods are compared in terms of numbers of real multiplication required for each algorithm. Here, the AIDs applied t = 3 iterations each. From this figure, the QR decomposition and the NSA are significantly more complex than the other algorithms. Cholesky and LDL provide similar complexity, which is also supported by the operation numbers of Table II. GS and CG methods require the least number of multiplications for their execution.
As Cholesky and LDL provide significantly less complexity over the QR decomposition, they are ideal choice for implementation platforms. These algorithms even provide lower complexity than NSA. The error-rate performance of the CG method is not satisfactory according to Figs. 3 and 4. On the other hand, GS method is very promising as it outperforms other AIDs in terms of error rate while using low number of operations. From Fig. 7, the number of operations required for GS is less than half of Cholesky and LDL. It should be noted that the channel model utilized in this work is i.i.d.  8  8  2432  604  576  Cholesky  8  8  392  42  36  LDL  -8  560  42  36   16   Gram-Schmidt  16  16  17920  4532  4352  Cholesky  16  16  2960  210  136  LDL  -16  3680  210  136   32   Gram-Schmidt  32  32  137216  34660  33792  Cholesky  32  32  22816  930  528  LDL  -32  25792  930   and therefore, the performance of the GS method might suffer in a more realistic channel model. We plan to compare GS, Cholesky, LDL in a more realistic channel model for our future works.

VI. CONCLUSION
We presented an analysis of matrix decomposition algorithms from massive MIMO context and their suitability for VLSI design of massive MIMO detectors. We compared massive MIMO detection algorithms based on approximate inversion and conventional matrix decomposition algorithms. The results will provide a guideline to select the appropriate algorithm for the research community. We concluded that Cholesky and LDL are viable solutions for massive MIMO detection. We also found that the GS can be an attractive approximate inversion-based detector which might provide a good balance between error-rate performance and complexity.