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.
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.
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