Toward Cost-Effective Adaptive Random Testing: An Approximate Nearest Neighbor Approach

Rubing Huang, Chenhui Cui, Junlong Lian, Dave Towey, Weifeng Sun, Haibo Chen

Research output: Journal PublicationArticlepeer-review


Adaptive Random Testing (ART) enhances the testing effectiveness (including fault-detection capability) of Random Testing (RT) by increasing the diversity of the random test cases throughout the input domain. Many ART algorithms have been investigated such as Fixed-Size-Candidate-Set ART (FSCS) and Restricted Random Testing (RRT), and have been widely used in many practical applications. Despite its popularity, ART suffers from the problem of high computational costs during test-case generation, especially as the number of test cases increases. Although several strategies have been proposed to enhance the ART testing efficiency, such as the forgetting strategy and the kk -dimensional tree strategy, these algorithms still face some challenges, including: (1) Although these algorithms can reduce the computation time, their execution costs are still very high, especially when the number of test cases is large; and (2) To achieve low computational costs, they may sacrifice some fault-detection capability. In this paper, we propose an approach based on Approximate Nearest Neighbors (ANNs), called Locality-Sensitive Hashing ART (LSH-ART). When calculating distances among different test inputs, LSH-ART identifies the approximate (not necessarily exact) nearest neighbors for candidates in an efficient way. LSH-ART attempts to balance ART testing effectiveness and efficiency.

Original languageEnglish
Pages (from-to)1182-1214
Number of pages33
JournalIEEE Transactions on Software Engineering
Issue number5
Publication statusPublished - 1 May 2024


  • Software testing
  • adaptive random testing (ART)
  • approximate nearest neighbor (ANN)
  • cost-effectiveness
  • locality-sensitive hashing (LSH)
  • random testing (RT)

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Toward Cost-Effective Adaptive Random Testing: An Approximate Nearest Neighbor Approach'. Together they form a unique fingerprint.

Cite this