SoK: State of the Krawlers – Evaluating the Effectiveness of Crawling Algorithms for Web Security Measurements

SoK: State of the Krawlers – Evaluating the Effectiveness of Crawling Algorithms for Web Security Measurements

Speakers: Aleksei Stafeev; Giancarlo Pellegrino

Conference: USENIX Security '24

YouTube: https://www.youtube.com/watch?v=i6ts-0V8SIY

Overview

This talk, titled "SoK: State of the Krawlers – Evaluating the Effectiveness of Crawling Algorithms for Web Security Measurements," delves into the critical role of web crawlers in empirical security research and the often-overlooked inconsistencies in their application and evaluation. Presented by Andrea on behalf of authors Aleksei Stafeev and Giancarlo Pellegrino, the research addresses the fundamental challenge of effectively traversing the complex landscape of the modern web to gather data for large-scale security measurements. The presentation highlights that despite their ubiquity, the actual effectiveness of different crawling algorithms in varied web security contexts remains largely unclear.

The core contribution of this work lies in its comprehensive systematization and extensive assessment of state-of-the-art web crawling techniques. By analyzing a vast body of academic literature and then empirically evaluating a wide array of identified algorithms, the authors bridge a significant gap in understanding how different navigation strategies and page similarity algorithms impact data collection for security-focused investigations. This research is crucial because the accuracy and completeness of web security measurements—such as identifying vulnerabilities, assessing defense mechanisms, or studying web ecosystems—are directly dependent on the underlying crawling technology.

Ultimately, this paper provides invaluable guidance for researchers and practitioners who rely on web crawlers. It offers data-driven recommendations for selecting optimal crawling configurations based on specific measurement objectives and exposes critical shortcomings in the reporting of crawling methodologies within existing academic work. By making their benchmark tool, Arkarium, openly available, the authors also provide a foundational platform for future, more standardized evaluations of web crawling efficacy in the security domain.

Background

▶ Watch: Introduction to crawlers and research problem (0:00)

Web measurements serve as an invaluable tool for empirical investigations in cybersecurity, enabling researchers to study phenomena such as the prevalence of vulnerabilities, the impact of new attack vectors, or the effectiveness of defensive mechanisms at scale. The linchpin of these large-scale web measurements is the crawler, an automated tool designed to traverse websites and collect diverse data, including JavaScript files, web pages, and cookies. However, the construction and deployment of an effective crawler are fraught with challenges due to the inherent complexity and dynamic nature of the web.

A crawler's architecture fundamentally relies on two key components: a navigation strategy and a page similarity algorithm. The navigation strategy dictates the order in which the crawler interacts with a website, determining which links to follow, buttons to click, or forms to submit. Common strategies include classic graph-based approaches like Breadth-First Search (BFS) and Depth-First Search (DFS), as well as more advanced techniques such as randomized algorithms, reinforcement learning-based methods, and coverage-guided crawling. The page similarity algorithm, on the other hand, is crucial for preventing infinite loops and avoiding the redundant collection of already-visited or nearly identical pages. This typically involves comparing new pages with previously encountered ones using various metrics, ranging from simple URL comparisons to more sophisticated analyses of DOM trees, HTML strings, or even visual page elements.

The primary challenge lies in the complex, often dynamic, and interlinked structure of modern websites. This complexity frequently leads to crawlers either missing significant portions of a site (under-coverage) or repeatedly processing the same content (duplicate pages), thereby compromising the integrity and efficiency of web measurements. Over the past decades, researchers have indeed proposed numerous novel ideas to improve crawling algorithms, yet their effectiveness specifically in the context of web security measurements has remained largely unassessed. Previous studies evaluating crawler effectiveness have typically been conducted in isolation, utilizing heterogeneous settings and often presenting only partial comparative evaluations. This fragmented understanding has created a significant gap, making it difficult for researchers to select the most appropriate crawling techniques for their specific security-related data collection tasks. This paper directly addresses this gap by systematizing the existing knowledge and conducting an extensive, comparative assessment of these diverse crawling algorithms under realistic conditions.

Key Findings

▶ Watch: Survey findings: current crawler usage in research (4:00)

The research yielded a wealth of insights, categorized into findings from their systematization of literature and the empirical assessment of crawling algorithms.

Findings from Literature Systematization:

1. Limited In-Website Navigation: A surprising observation was that only 32% of the reviewed papers conducting web measurements actually navigated within a website. The majority either collected data from a single visit or focused on specific URLs.
2. Algorithm Specification Gaps:

• For navigation algorithms, 71% of papers specified their chosen strategy, with randomized navigation, BFS, and rule-based navigation being the top three. However, 29% failed to specify any algorithm.
• For page similarity algorithms, 78% specified their method, with URL comparison being the most popular, followed by "no algorithm" (implying unique URLs were sufficient or no explicit comparison was done), and hash-based algorithms. A notable 22% did not specify their page similarity approach.
• The most frequently cited combination of algorithms was BFS for navigation paired with URL comparison for page similarity.

1. Reasons for Limited Navigation:

• 26% of papers did not require in-depth navigation because all necessary data could be gathered from a single visit (e.g., studies based on specific URL feeds, fishing studies, endpoint probing for vulnerabilities, or censorship studies targeting particular domains).
• 42% of papers explicitly acknowledged a trade-off between comprehensive coverage and computational resources. Authors often recognized the benefit of more extensive data but chose to limit their scope to a lower-bound analysis or a restricted selection of websites due to resource constraints.

1. Difficulty in Reproducibility: The authors found it extremely challenging to identify and reimplement algorithms from published papers. Many papers lacked sufficient detail: 38 papers did not list their navigation strategy, and 28 papers did not list their similarity algorithm. Even when algorithms were specified, crucial setup details, such as parameter values, were often missing. Out of 31 identified algorithms, the researchers could only reuse existing code for 14, reimplement 4, and were unable to do either for the remaining 13, underscoring a significant problem in research transparency and reproducibility.

Findings from Extensive Algorithm Assessment (Top 5 of 14 Insights):

1. No Single Outperforming Configuration: The most critical finding was that no single crawling configuration (combination of navigation and page similarity algorithms) universally outperformed all others across different metrics. The optimal choice depends heavily on the specific targeted metric (e.g., code coverage, link coverage, or JavaScript file coverage). For instance, randomized BFS and tree edit distance performed best for code coverage, while randomized BFS and URL comparison excelled at collecting links.
2. Randomized Techniques Often Superior: Generally, randomized techniques were observed to perform better than their deterministic counterparts, suggesting that introducing an element of randomness can help overcome the structured biases of web design and achieve broader coverage.
3. Popularity ≠ Optimality: The highly popular combination of BFS and URL comparison was found to be suboptimal for many tasks. Better options exist, such as random crawling combined with tree edit distance comparison, demonstrating a disconnect between common practice and empirical effectiveness.
4. Budgetary Impact on Algorithm Choice: For tight resource budgets (e.g., less than 100 seconds allocated per website visit), the choice of crawling algorithm had a negligible effect on coverage. This suggests that for quick scans or very large datasets with limited time per target, the overhead of sophisticated algorithms might not be justified.
5. Need for Detailed Disclosure: The significant difficulty in reimplementing algorithms highlighted the urgent need for the research community to provide full, detailed disclosure of their crawling methodologies, including specific algorithms, parameters, and any custom setups, to foster reproducibility and comparative analysis.

These findings collectively underscore the complexity of effective web crawling for security measurements and provide a data-driven foundation for improving future research and tools.

Technical Deep Dive

▶ Watch: First insight: No single best crawling configuration (6:00)

The technical depth of this research is rooted in its two-pronged approach: a rigorous systematization of existing literature and an extensive empirical evaluation.

The systematization of literature involved a comprehensive review process. The authors conducted two distinct literature surveys. The first focused on how crawlers are employed in web measurements, examining over 7,800 papers from top security, privacy, and web conferences published over the past 12 years. The second survey specifically identified crawling techniques, reviewing over 900 papers from top security conferences over the past 3 years. This dual approach ensured a broad understanding of both the application contexts and the technical methodologies. The methodology for these surveys involved an initial keyword search to identify papers related to web measurement and crawling, followed by a meticulous manual review of all identified papers to filter out false positives and extract relevant details.

From this extensive review, the researchers successfully identified:

• Six unique navigation strategies: These included well-known approaches like Breadth-First Search (BFS) and Depth-First Search (DFS), often categorized under graph-based algorithms. More advanced strategies such as randomized algorithms, reinforcement learning (RL)-based techniques, and coverage-guided algorithms were also identified.
• Seventeen distinct page similarity algorithms: These algorithms are critical for determining whether a newly encountered page is unique or a variant of an already visited one, thus preventing redundant processing and infinite loops. Categories included URL comparison (the simplest), DOM tree comparison (analyzing the Document Object Model structure), HTML string comparison (often involving hashing the page content), page image comparison (for visual similarity), and various custom algorithms tailored for specific contexts.

When combined, these navigation and page similarity algorithms yielded a total of 102 distinct crawling techniques. Additionally, the survey identified four prominent web security scanner tools that incorporate crawling functionalities.

The extensive assessment phase aimed to empirically evaluate these 102 identified crawling techniques, along with the four scanner tools, in realistic settings. To achieve this, the researchers designed a sophisticated experimental setup:

• Target Environments: The evaluation was conducted across two distinct types of web environments:
• 11 local web applications: These controlled environments were used primarily to measure code coverage, allowing for precise quantification of how much of an application's backend code was exercised by different crawling strategies.
• 2,000 randomly selected web domains: Sourced from the Alexa ranking, these live domains provided a realistic and diverse set of targets for measuring JavaScript file coverage and link coverage. This large-scale setup addressed the limitations of previous isolated studies.
• Benchmark Tool - Arkarium: Recognizing the immense scale and complexity of this evaluation, the authors developed their own benchmark tool named Arkarium. This framework was engineered to enable large-scale experiments by efficiently scheduling and running numerous crawling experiments in parallel. Arkarium's design specifically facilitates the addition of more web applications and crawlers by the community, promoting collaborative research and standardized evaluation. The tool has been made freely available, inviting broader participation and continuous improvement of crawler assessment capabilities.

The empirical evaluation focused on comparing the performance of the 102 techniques across the defined metrics. For example, the study revealed that while randomized BFS combined with a variant of tree edit distance performed optimally for maximizing code coverage, the best combination for collecting links involved randomized BFS and URL comparison. These granular findings highlight the nuanced effectiveness of different algorithm choices based on the specific data collection objective, challenging the notion of a universally superior crawling strategy. The systematic approach to identifying, categorizing, and then empirically testing such a vast array of crawling techniques, supported by the custom-built Arkarium framework, constitutes a significant technical advancement in the field of web security measurement.

Demo / Proof of Concept

▶ Watch: Randomized techniques often outperform popular choices (7:00)

While the talk did not feature a live, interactive demonstration in the traditional sense, the core of their experimental work relied on a newly developed benchmark tool, Arkarium, which serves as a robust proof of concept for their methodology and findings. Arkarium is presented as a practical, open-source framework designed to facilitate large-scale, reproducible evaluations of web crawling algorithms.

The creation of Arkarium itself is a significant technical achievement and a testament to the practical application of their research. It functions as an experimental platform that schedules and runs crawling experiments in parallel across diverse web environments. The authors utilized Arkarium to conduct their extensive assessment of 102 crawling techniques on 11 local web applications and 2,000 live web domains, collecting data on code coverage, JavaScript file coverage, and link coverage. The ability of Arkarium to manage such a complex and resource-intensive evaluation demonstrates its effectiveness as a tool for empirical security research.

The fact that Arkarium is freely available and designed to be extensible (allowing the community to add more web applications and crawlers) positions it as a vital contribution to the field. It acts as a standardized environment where researchers can systematically test and compare new or existing crawling algorithms, validating the findings presented in the paper and enabling future advancements in web security measurement techniques. Thus, Arkarium serves as the tangible, demonstrable output of their work, proving the feasibility of their large-scale comparative assessment.

Defensive Implications

▶ Watch: Challenge: Difficulty in re-implementing published algorithms (8:15)

The findings from "SoK: State of the Krawlers" carry significant implications for defenders, particularly those involved in proactive security measures, vulnerability assessment, and large-scale threat intelligence gathering. The effectiveness of many defensive tools and research efforts hinges directly on the quality and completeness of their underlying web crawling capabilities.

Firstly, security researchers and practitioners developing or utilizing vulnerability scanners, penetration testing tools, or web application firewalls (WAFs) need to critically re-evaluate their default crawling strategies. The research clearly demonstrates that the commonly used combination of BFS and URL comparison is often suboptimal. If a scanner uses this default, it may be significantly under-covering web applications, leading to missed vulnerabilities or an incomplete understanding of the application's attack surface. Defenders should understand that different objectives—such as achieving maximum code coverage to find backend flaws, identifying all links to map attack paths, or discovering all JavaScript files for client-side vulnerability analysis—require distinct, optimized crawling configurations.

Secondly, the finding that randomized techniques often outperform deterministic ones suggests that introducing an element of unpredictability into crawling strategies can lead to more comprehensive discovery. For security teams trying to emulate attacker behavior or discover hidden endpoints, incorporating randomized navigation could yield better results than strictly structured approaches. This means moving beyond simple sequential link following and embracing more dynamic exploration strategies.

Thirdly, the insight regarding resource constraints is crucial for operational security. For organizations with vast numbers of web assets or limited time windows for scanning, the study indicates that for very short crawl durations (e.g., under 100 seconds per site), the choice of a sophisticated algorithm has minimal impact on coverage. This suggests that for rapid, high-level assessments across a massive attack surface, simpler, faster algorithms might be sufficient, allowing resources to be allocated more effectively for deeper dives into critical assets.

Finally, the call for detailed disclosure of crawling methodologies in research papers is vital for the defensive community. When security research presents findings based on web measurements (e.g., prevalence of a certain vulnerability), understanding the crawling strategy used is paramount for assessing the generalizability and reliability of those findings. Defenders relying on such research to inform their strategies must be able to trust that the data was collected comprehensively and transparently. The open-sourcing of Arkarium further empowers defenders by providing a standardized, community-driven platform to benchmark and improve the crawling component of their security tools, fostering better, more effective web security measurements across the board.

Key Takeaways

• Tailor Crawling to Objectives: There is no single "best" crawling algorithm. Optimal performance depends heavily on the specific measurement goal, whether it's maximizing code coverage, discovering links, or collecting JavaScript files. Researchers and practitioners must select navigation and page similarity algorithms based on their targeted metrics.
• Embrace Randomized Techniques: Randomized navigation strategies often achieve superior coverage compared to deterministic methods, suggesting that introducing an element of unpredictability can help overcome the structured biases of web design and lead to more comprehensive data collection.
• Rethink Default Strategies: The widely popular combination of Breadth-First Search (BFS) for navigation and URL comparison for page similarity is frequently suboptimal. Better alternatives, such as random crawling with tree edit distance comparison, exist and should be considered for more effective web measurement.
• Consider Resource Constraints: For very short crawl durations (e.g., under 100 seconds per website), the choice of a sophisticated crawling algorithm has a minimal impact on coverage. This insight can help optimize resource allocation for large-scale, rapid assessments.
• Improve Methodological Transparency: The significant difficulty in identifying and reimplementing crawling algorithms from existing research highlights a critical need for the security community to provide full, detailed disclosure of their crawling methodologies, including specific algorithms, parameters, and custom setups, to ensure reproducibility and foster comparative analysis.
• Utilize Arkarium for Benchmarking: The open-source Arkarium framework provides a valuable, standardized platform for evaluating and comparing web crawling algorithms, offering a critical tool for future research and development in web security measurement.

About the Speaker(s)

The paper "SoK: State of the Krawlers – Evaluating the Effectiveness of Crawling Algorithms for Web Security Measurements" was authored by Aleksei Stafeev and Giancarlo Pellegrino. The presentation at USENIX Security '24 was delivered by Andrea, who filled in for Aleksei Stafeev due to unforeseen visa problems. While the transcript acknowledges Andrea's role as the presenter, specific titles or company affiliations for the authors, Aleksei Stafeev and Giancarlo Pellegrino, were not provided within the talk metadata or the transcript itself. The work represents a significant contribution to the field of web security measurement and the empirical evaluation of crawling technologies.