This extended abstract presents an approach to enhance the Fixed-Sized-Candidate-Set Adaptive Random Testing (FSCS-ART) sampling strategy. SWFC-ART, the proposed approach, stores the previously-executed, non-failure-causing test cases into a Hierarchical Navigable Small World Graph (HNSWG) data structure and uses an efficient and consistent Nearest Neighbor Search (NNS) mechanism, especially for high-dimensional input domains. Our experiments show that SWFC-ART reduces the computational overhead of FSCS-ART from quadratic to log-linear order while retaining the failure-detection effectiveness of FSCS-ART.

Fixed-size-candidate-set adaptive random testing (FSCS-ART) is an ART technique well-known for its best failure-detection effectiveness and usages in testing many real-life applications. However, it faces substantial computational overhead in terms of O(n2) time cost for generating n test inputs, which becomes worse for high dimensional input domains (number of inputs a software takes). As real-life programs generally have low failure-rates and have high dimensional input domains, it is vital to reduce the computational overhead while preserving the failure-detection effectiveness for efficient software testing. In this work, we adopted Quantization and InVerted File structure approach to enhance the original FSCS-ART, called QIVFSCS-ART. The proposed method preprocesses the software input domain by partitioning it into discrete cells by using K-means clustering using a uniform random dataset. After this, the quantized form of each executed test input is stored in the inverted list of its cell’s center, called centroid. Results show that the proposed method significantly relieves the computational overhead of FSCS-ART while preserving its failure-detection effectiveness, especially for the high-dimensional software input domains.

The Fixed-Size-Candidate-Set (FSCS) version of Adaptive Random Testing (ART) attempts to enhance the fault detection effectiveness of Random Testing (RT) by generating new test cases that are far away from previously executed test cases. Despite its simplicity and good fault-detection effectiveness, FSCS suffers from a very high time cost mainly due to its Single-Instruction-Single-Data (SISD) mechanism for its distance calculation process. To overcome this drawback, in this paper, we propose a novel and efficient implementation of FSCS, namely Fixed-Sized-Candidate-Set using Single-Instruction-Multiple-Data (FSCS-SIMD), which employs SIMD instruction architecture for simultaneous distance calculations of multiple test cases in a many-to-many style. Compared with the original FSCS, our proposed method loads a batch of multiple test cases from the candidate test case set and executed test case set in one CPU execution cycle. After that, a single distance calculation instruction is given to the whole batch for the calculation of all pairwise distances. We conducted a series of simulations and empirical studies to evaluate testing effectiveness and efficiency of our proposed method against FSCS. Our results show that, on average, FSCS-SIMD reduces test case generation overhead of FSCS up to 90%, while maintaining the comparable fault detection effectiveness.

Fixed Sized Candidate Set (FSCS) is the first of a series of methods proposed to enhance the effectiveness of random testing (RT) referred to as Adaptive Random Testing methods or ARTs. Since its inception, test case generation overheads have been a major drawback to the success of ART. In FSCS, the bulk of this cost is embedded in distance computations between a set of randomly generated candidate test cases and previously executed but unsuccessful test cases. Consequently, FSCS is caught in a logical trap of probing the distances between every candidate and all executed test cases before the best candidate is determined. Using data mining, however, we discovered that about 50% of all valid test cases are encountered much earlier in the distance computations process but without any benefit of a hindsight, FSCS is unable to validate them; a wild goose chase. This paper then uses this information to propose a new strategy that predictively and proactively selects valid candidates anywhere during the distance computation process without vetting every candidate. Theoretical analysis, simulations and experimental studies conducted led to a similar conclusion: 25% of the distance computations are wasteful and can be discarded without any repercussion on effectiveness.

Mirror Adaptive random testing (MART) is an overhead reduction strategy for adaptive random testing methods. Theoretically speaking, MART's advantage over ordinary ARTs is determined by the mirroring scheme selected. Incidentally, an inherent problem with MART relates to the difficulty in the choice of a scheme for any testing task. This is because a higher scheme (larger mirror domains) does not necessarily guarantee efficient utilization of testing resources due to lack of diversity of mirror generated test cases. The culprit has been identified as the mapping functions used as substitutes to complex ART methods. In this paper, we present a new method for generating diversified mirror test cases by randomly displacing the mirror partitions upon which the mapping functions of MART operates. The result of simulations and experiments conducted shows remarkable improvement over MART's effectiveness and efficiency across MART schemes, especially where program failures are unrelated to one or more input parameters.

One goal of software testing may be the identification or generation of a series of test cases that can detect a fault with as few test executions as possible. Motivated by insights from research into failure-causing regions of input domains, the even-spreading (even distribution) of tests across the input domain has been identified as a useful heuristic to more quickly find failures. This finding has encouraged a shift in focus from traditional random testing (RT) to its enhancement, adaptive random testing (ART), which retains the randomness of test input selection, but also attempts to maintain a more evenly distributed spread of test inputs across the input domain. Given that there are different ways to achieve the even distribution, several different ART methods and approaches have been proposed. This paper presents a new ART method, called ART by orthogonal recursive bisection (ART-ORB), which explores the advantages of repeated geometric bisection of the input domain, combined with restriction regions, to evenly spread test inputs. Experimental results show a better performance in terms of fewer test executions than RT to find failures. Compared with other ART methods, ART-ORB has comparable performance (in terms of required test executions), but incurs lower test input selection overheads, especially in higher dimensional input space. It is recommended that ART-ORB can be used in testing situations involving expensive test input execution.

A key objective of software testing is to find program errors that cause failure in software, at less cost. One basic testing technique is random testing (RT), but many researchers have criticised its failure‐detection effectiveness. Several researchers have proposed that an enhancement of the failure‐detection effectiveness of RT is achieved if test cases are evenly spread within the input domain. Adaptive RT (ART) describes a family of algorithms that employ various strategies to evenly and randomly spread test cases. Fixed sized candidate set ART (FSCS‐ART) is an ART algorithm that has gained many research studies far and wide; however, the high distance computations make its algorithm computationally expensive. The authors propose a new ART method that restricts distance computations to only test cases inside an exclusion zone. The experimental results show that the new ART method not only improves RT but also provides failure‐detection effectiveness similar to FSCS‐ART, while significantly minimising computation overhead.

The process of component security testing can produce massive amounts of monitor logs. Current approaches to detect implicit security exceptions (those which cannot be identified by visual inspection alone) compare correct execution sequences with fixed patterns mined from the execution of sequential patterns in the monitor logs. However, this is not efficient and is not suitable for mining large monitor logs. To enable effective mining of implicit security exceptions from large monitor logs, this paper proposes a method based on improved variable-length sequential pattern mining. The proposed method first mines the variable-length sequential patterns from correct execution sequences and from actual execution sequences, thus reducing the number of patterns. The sequential patterns are then detected using the Sunday string-searching algorithm. We conducted an experimental study based on this method, the results of which show that the proposed method can efficiently detect the implicit security exceptions of components.