Regression Testing for Wrapper Maintenance

AAAI 1999

TL;DR

Maintaining web data extraction "wrappers" is tough because websites change. This paper introduces RAPTURE, a novel regression testing approach that treats wrapper verification as a probabilistic problem, outperforming traditional methods by accounting for both site formatting and content changes.

What Problem Does This Paper Address?

The internet is a treasure trove of information, but accessing it programmatically often requires "wrappers" – specialized scripts that extract structured data from unstructured web pages. The challenge is that websites are dynamic; their formatting, structure, and even content can change frequently. When this happens, wrappers break, requiring maintenance. Traditional software testing methods, like regression testing, assume a static environment. However, for web wrappers, both the underlying data (e.g., today's stock prices vs. historical ones) and the page's formatting (e.g., bolding countries vs. italicizing them) can change, making standard regression testing ineffective. This paper tackles the problem of wrapper verification: determining if a wrapper is still correctly extracting data from a given web page, especially in the face of these dynamic changes.

Methods

The paper proposes RAPTURE, a domain-independent, heuristic algorithm for wrapper verification. RAPTURE operates on a "black-box" principle, treating the wrapper as a function that takes a web page and outputs a structured label (a set of tuples). The core idea is to compare the output of the wrapper on a new page (p) with the known correct outputs (labels) from a set of previously verified pages (L) for the same site.

Instead of requiring an exact match (like traditional regression testing), RAPTURE uses a probabilistic approach:

  1. Feature Extraction: RAPTURE extracts various numerical features from the text fragments of the wrapper's output. Examples include word count, letter density, and mean word length.
  2. Distribution Modeling: For each feature and attribute combination, RAPTURE models the distribution of its values using a normal distribution, estimating the mean (µ) and standard deviation (σ) from the verified pages.
  3. Probability Calculation: For a new page, RAPTURE calculates the probability that each extracted feature value is consistent with the learned distributions. This is done for each attribute and feature, yielding a set of probabilities.
  4. Verification Probability: These individual probabilities are then combined (often using an independence assumption, but other dependency assumptions are explored) to produce an overall "verification probability" (v) that the wrapper is correct for the given page.
  5. Thresholding: This verification probability v is compared against a threshold (T) to decide whether the wrapper is considered verified (correct) or not. The paper also discusses how to estimate the distribution of these verification probabilities themselves to make the thresholding more robust.

RAPTURE also incorporates query information (q and Q) to refine the verification process, recognizing that the number of extracted tuples can depend on the query.

Datasets

The paper describes an experimental setup using 27 actual Internet sites. For each site, 15 queries were selected and issued approximately every 3 days over a 6-month period, resulting in a total of 23,416 fetched pages. Wrappers were generated for each page using semi-automated techniques, serving as the "gold standard" for evaluation. No new benchmark datasets were introduced; instead, existing real-world internet sites were used.

Key Insights and Ideas

  • Beyond Exact Matches: The most crucial insight is that wrapper verification cannot rely on exact output matches due to the dynamic nature of web content and formatting. RAPTURE's probabilistic approach is key.
  • Features as Evidence: Syntactic features extracted from the text are treated as evidence for or against the correctness of an extraction. The choice of features (e.g., HTML density) can significantly impact performance.
  • Modeling Uncertainty: By modeling feature distributions and calculating probabilities, RAPTURE explicitly accounts for the inherent uncertainty in web data extraction.
  • Query Sensitivity: Recognizing that query parameters influence extraction results is important for accurate verification.
  • The "Moving Target" Problem: The paper clearly articulates the challenge of having two "moving targets" – website formatting and underlying content – which standard regression testing fails to address.

Key Results

  • Significant Performance Improvement: RAPTURE demonstrated substantial performance improvements over a baseline "STRAWMAN" regression tester.
  • Accuracy and F-score: RAPTURE achieved significantly higher accuracy and F-scores across various parameter settings. For instance, one optimized setting showed a 56% gain in accuracy and 28% in F over STRAWMAN.
  • Handling Changes: RAPTURE was much more effective at detecting wrapper changes. The paper reports a 344-fold improvement in detecting wrapper changes compared to STRAWMAN.
  • Feature Importance: HTML density was found to be a particularly effective feature, likely because incorrect wrappers often leave HTML tags in the extracted data.
  • Robustness: RAPTURE's performance was evaluated across different dependency assumptions and feature sets, showing consistent advantages.

Limitations and Future Work

  • Assumptions: RAPTURE relies on assumptions about feature distributions (normal) and dependencies between extracted elements (e.g., independence). While these assumptions yielded good results, they are acknowledged as potentially not perfectly reflecting reality.
  • Feature Selection: The feature set was selected somewhat ad-hoc. The authors suggest investigating additional features.
  • Probabilistic Assumptions: The paper mentions exploring alternative probabilistic assumptions beyond independence, entailment, and equivalence.
  • Generalization: The current work focuses on relational data models. Future work includes generalizing the techniques to object-oriented, semi-structured, and other data models.
  • Threshold Tuning: While the paper discusses adjusting the "pessimism" by varying the threshold T, further work could explore more sophisticated methods for threshold selection.

Summary updated

BibTeX
@inproceedings{1999regression,
  title = {{Regression Testing for Wrapper Maintenance}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure