Booster: Effective and Efficient Web GUI Trace Reduction Based on Multi-Level State Abstraction and Time-Guided Hierarchical Delta Debugging

Automated approaches of web GUI testing are widely used to reduce labor costs in quality assurance of web applications by mimicking human interaction to trigger failures through GUI actions (e.g., clicks). However, these approaches often generate lengthy GUI traces containing unnecessary actions before triggering a failure, complicating the identification of root causes of failures for developers. Trace reduction approaches have been proposed to remove unnecessary actions from failure-triggering traces. Existing approaches of trace reduction typically employ algorithms from the Delta Debugging (DD) family. However, these approaches suffer from inefficiencies due to exhaustive trial-based strategies and fail to account for action preconditions and the varying time intervals between actions. To address the limitations, in this article, we propose Booster, with the following two key components. (1) Multi-level state abstraction. Booster identifies unnecessary actions through a hierarchical abstraction of GUI states, preserving the preconditions of actions on different abstraction levels to minimize the number of failed trials. (2) Time-Guided Hierarchical Delta Debugging (TGHDD). Booster optimizes the reduction process by applying our TGHDD algorithm, which partitions the action trace according to the estimated execution time of actions instead of action counts, ensuring a more balanced time distribution across partitions and enhancing the efficiency of the trace reduction. We evaluate Booster on traces generated by state-of-the-art automated approaches of web GUI testing, WebExplor and WebRLED. Experimental results demonstrate that Booster greatly outperforms the state-of-the-art approach named SimplyDroid and the traditional Delta Debugging in terms of efficiency, on average with 43.4% and 72.1% less time cost, while obtaining 60.2% and 38.8% shorter length of the reduced traces in a 24-hour time budget. Additional experiments confirm the effectiveness of Booster's individual techniques.