Improved Usage Model for Web Application Reliability Testing

Gregor von Bochmann, Guy-Vincent Jourdan, Bo WanICTSS 2011 · DOI

Abstract

Traditional web reliability testing often relies on first-order Markov chains, which fail to capture the history-dependent nature of user behavior. Conversely, full execution trees suffer from state-space explosion. This paper presents a hybrid usage model that combines the history-tracking capabilities of trees with the efficiency of Markov chains. By applying statistical pruning and Chi-square-based state merging, the proposed method reduces a massive execution tree into a compact, accurate model suitable for large-scale reliability testing.

Introduction

Reliability testing for web applications requires models that accurately reflect real-world user behavior. While Markov chains are computationally efficient, their "memoryless" property—where the next state depends only on the current one—is often insufficient for web navigation, which is inherently history-dependent. While a Tree of Sequences (TS) can capture full history, the resulting models are often too large and noisy for practical use.

Methodology

The authors propose a multi-step pipeline to construct a Hybrid Tree-Like Markov Usage Model.

1. Tree of Sequences Construction

The process begins by transforming web logs into a Tree of Sequences (TS), where each path from the root represents a unique user session. This structure captures the full context of every user interaction but is prone to extreme growth.

Figure 4: A Tree of Sequences (TS) representing various user navigation paths and their frequencies.

2. Pruning and Filtering

To manage complexity, the model undergoes frequency pruning and statistical filtering using the Cochran criterion. Paths with insufficient data are moved to a "Lower Markov Model," ensuring that only statistically significant behaviors remain in the primary tree structure.

3. State Merging via Chi-Square Testing

The core innovation is a dynamic state-merging process. Using Chi-square independence tests, the model determines if a user's future behavior is significantly influenced by their past path. If the history does not statistically alter future choices, the states are merged; otherwise, they remain distinct to preserve critical behavioral context.

Figure 3: Illustration of state merging and splitting based on historical context.

Experimental Results

The model was evaluated using a year's worth of logs from Bigenet, a French genealogy site. The raw data comprised over 100,000 sessions and 900,000 requests.

  • Compression: The initial tree of 348,391 nodes was compressed into an "Upper Tree" of just 337 nodes and a 30-state Markov model.
  • Performance: The entire optimization process took less than 4 seconds (3937ms) on standard hardware.
  • Stability: Sub-sampling tests confirmed that the model captures consistent usage patterns rather than over-fitting to specific logs.

Conclusion

This hybrid approach successfully bridges the gap between memoryless Markov models and unmanageable execution trees. By focusing on statistical significance and dynamic state merging, the model provides a high-fidelity representation of user behavior that is both compact and computationally efficient for web reliability testing.

Summary updated

BibTeX
@inproceedings{bochmann2011improved,
  author = {Gregor von Bochmann and Guy-Vincent Jourdan and Bo Wan},
  title = {{Improved Usage Model for Web Application Reliability Testing}},
  booktitle = {ICTSS},
  year = {2011},
  doi = {10.1007/978-3-642-24580-0\_3},
}
Figure