Multi-Level Random Walk for Software Test Suite Reduction

Software testing is important and time-consuming. A test suite, i.e., a set of test cases, plays a key role in validating the expected program behavior. In modern test-driven development, a test suite pushes the development progress. Software evolves over time; its test suite is executed to detect whether a new code change adds bugs to the existing code. Executing all test cases after each code change is unnecessary and may be impossible due to the limited development cycle. On the one hand, multiple test cases may focus on an identical piece of code; then several test cases cannot detect extra bugs. On the other hand, even executing a test suite once in a large project takes around one hour [1]; frequent code changes require much time for conducting testing. For instance, in Hadoop, a framework of distributed computing, 2,847 version commits are accepted within one year from September 2014 with a peak of 135 commits in one week [2].