The Symposium on Engineering Test Harness (TSETH '13),
in Proceedings of the 13th International Conference on Quality Software (QSIC '13),
IEEE Computer Society Press, Los Alamitos, CA, pp. 268-275 (2013)

The ART of Divide and Conquer:
an Innovative Approach to Improving the Efficiency of Adaptive Random Testing

Cliff Chow 2 , Tsong Yueh Chen 3 , and T.H. Tse 2

[paper from IEEE Xplore | paper from IEEE digital library | technical report TR-2013-04]


Test case selection is a prime process in the engineering of test harnesses. In particular, test case diversity is an important concept. In order to achieve an even spread of test cases across the input domain, Adaptive Random Testing (ART) was proposed such that the history of previously executed test cases are taken into consideration when selecting the next test case. This was achieved through various means such as best candidate selection, exclusion, partitioning, and diversity metrics. Empirical studies showed that ART algorithms make good use of the concept of even spreading and achieve 40 to 50% improvement in test effectiveness over random testing in revealing the first failure, which is close to the theoretical limit. However, the computational complexity of ART algorithms may be quadratic or higher, and hence efficiency is an issue when a large number of previously executed test cases are involved. This paper proposes an innovative divide-and-conquer approach to improve the efficiency of ART algorithms while maintaining their performance in effectiveness. Simulation studies have been conducted to gauge its efficiency against two most commonly used ART algorithms, namely, fixed size candidate set and restricted random testing. Initial experimental results show that the divide-and-conquer technique can provide much better efficiency while maintaining similar, or even better, effectiveness.

Keywords: adaptive random testing, divide and conquer, efficiency, effectiveness, software testing, test harness

1. This work is supported in part by a linkage grant of the Australian Research Council (project no. LP100200208) and grants of the General Research Fund of the Research Grants Council of Hong Kong (project nos. 716612 and 717811).
2. The University of Hong Kong, Pokfulam, Hong Kong.
3. (Corresponding author.)
Faculty of Information and Communication Technologies, Swinburne University of Technology, Hawthorn 3122, Australia.


  Cumulative visitor count