TL;DR
This paper proposes a machine learning approach to automatically identify and block unwanted web advertisements, moving beyond the limitations of traditional, manually-curated filter lists. By training a classifier on existing ad-blocking rules, they achieve comparable accuracy to manual methods while also identifying new, previously unblocked ads, thus reducing human overhead and improving user experience.
What Problem Does This Paper Address?
The internet's economic model heavily relies on advertising, but these ads often become a significant annoyance and a privacy concern for users. Traditional ad blockers, like AdBlock Plus, rely on extensive, manually-crafted filter lists (often tens of thousands of rules) to identify and block ad resources. This manual process is time-consuming, prone to errors, and struggles to keep pace with the constantly evolving ad ecosystem. New ad formats and tracking techniques emerge frequently, necessitating continuous human effort to update these filter lists. This paper aims to automate and improve this process by leveraging machine learning to create a more robust and adaptable ad-blocking classifier.
Methods
The core of the paper's contribution lies in its machine learning approach. They frame ad blocking as a binary classification problem: determining if a given URL is ad-related or not. Their method involves:
- Feature Engineering: They extract 12 features from URLs and their surrounding page context. These features include:
- Ad-related keywords: Presence of terms like "ad," "banner," "popup" in the URL.
- Lexical features: Characteristics of the URL's structure, like the use of semicolons for parameters.
- Page context: Whether the URL's domain is present in the page's parameters or if the URL is hosted on the same domain as the page.
- Size and dimensions: Information about ad sizes or screen dimensions often embedded in ad URLs.
- Iframe usage: Whether the URL was requested from within an iframe.
- External resource proportion: The ratio of external scripts, iframes, or resources requested by the page.
- Classifier Training: They use an older version of the EasyList filter list as "ground truth" to train various machine learning classifiers. The goal is to see if a classifier trained on historical data can accurately identify ads according to a more current filter list.
- Model Selection: They experiment with several common classifiers, including Naïve Bayes, Support Vector Machines (SVMs) with different kernels, Logistic Regression, and k-Nearest Neighbors (kNN).
Datasets
The authors created their own dataset by:
- Crawling: They crawled the Alexa top 500 US websites up to a depth of 2.
- Labeling: For each requested resource URL, they compared it against two versions of the EasyList filter list:
- "Old" EasyList: A version from September 22nd, 2013.
- "New" EasyList: A version from February 23rd, 2014.
- Dataset Size: They collected approximately 60,000 total URLs, with roughly 30,000 classified as ad-related and 30,000 as non-ad-related based on the "new" EasyList.
- Evaluation Benchmark: They define two key evaluation metrics:
- Baseline Accuracy: The accuracy of classifying ads that were present in both the "old" and "new" EasyList.
- New-Ad Accuracy: The accuracy of classifying ads that were present in the "new" EasyList but not in the "old" one, representing ads that would have been missed by older filters.
Key Insights and Ideas
- Machine Learning for Ad Blocking is Viable: The paper demonstrates that machine learning can effectively learn to identify ad-related URLs, offering a promising alternative to manual filter list creation.
- Feature Engineering is Crucial: The combination of URL-based and page-context features proved effective in distinguishing ad content.
- k-Nearest Neighbors Shines: Among the tested classifiers, kNN emerged as the most effective, achieving high accuracy and a very low false positive rate.
- The "New-Ad" Challenge: A significant finding is the ability of the ML model to identify ads that are new to the filter list, highlighting the potential to proactively block emerging ad techniques.
- Trade-off Between Accuracy Types: There's an observed trade-off: improving "new-ad accuracy" sometimes comes at the cost of overall accuracy or baseline accuracy.
Key Results
- kNN Performance: The k-Nearest Neighbors classifier achieved the highest overall accuracy (97.55%), precision (98.6%), and the lowest false positive rate (1.3%) among the tested methods.
- Baseline vs. New-Ad Accuracy: While kNN achieved a high baseline accuracy, its "new-ad accuracy" was around 48.78% when using all features. This indicates that while it's good at identifying known ads, there's still room for improvement in catching entirely novel ones.
- Feature Importance: Removing feature set F (Proportion of external requested resources) significantly dropped the overall accuracy to 76%, suggesting its critical role.
- False Positives: The kNN classifier achieved an average false positive rate of around 1% on the test set. Manual inspection of these false positives revealed that a large majority were indeed ad-related URLs that were simply not caught by the "new" EasyList, suggesting the classifier was correctly identifying them as ads.
Limitations and Future Work
- Static vs. Dynamic Training: The current approach uses batch training on historical data. The authors acknowledge the need for a system that can adapt and learn incrementally in real-time as new ad types emerge.
- User Feedback Loop: They suggest incorporating a feedback mechanism, similar to spam filters, where users can identify ad elements, and the system can learn from these inputs.
- Semi-Supervised Learning: For real-time adaptation, they propose exploring semi-supervised online learning techniques.
- kNN Scalability: While kNN performed well, its runtime can increase with the number of training examples. Future work might involve optimizing search algorithms or using techniques like clustering to manage large datasets.
- False Negatives: While minimizing false positives is crucial, the paper notes that the low false negative rate on new ads is a tolerable tradeoff. However, further tuning for both is a direction for future work.
Summary updated