Adaptive Random Testing with Q-grams: The Illusion Comes True

• URL: http://arxiv.org/abs/2410.17907v4
• Date: Wed, 19 Feb 2025 15:37:46 GMT
• Title: Adaptive Random Testing with Q-grams: The Illusion Comes True
• Authors: Matteo Biagiola, Robert Feldt, Paolo Tonella,
• Abstract summary: We introduce a novel framework for adaptive random testing that replaces pairwise distance computations with a compact aggregation of past executions. Experiments show that ART with q-grams covers, on average, 4x more unique targets than random testing, and 3.5x more than ART using traditional distance-based methods.
• Score: 13.166002843307663
• License:
• Abstract: Adaptive Random Testing (ART) has faced criticism, particularly for its computational inefficiency, as highlighted by Arcuri and Briand. Their analysis clarified how ART requires a quadratic number of distance computations as the number of test executions increases, which limits its scalability in scenarios requiring extensive testing to uncover faults. Simulation results support this, showing that the computational overhead of these distance calculations often outweighs ART's benefits. While various ART variants have attempted to reduce these costs, they frequently do so at the expense of fault detection, lack complexity guarantees, or are restricted to specific input types, such as numerical or discrete data. In this paper, we introduce a novel framework for adaptive random testing that replaces pairwise distance computations with a compact aggregation of past executions, such as counting the q-grams observed in previous runs. Test case selection then leverages this aggregated data to measure diversity (e.g., entropy of q-grams), allowing us to reduce the computational complexity from quadratic to linear. Experiments with a benchmark of six web applications, show that ART with q-grams covers, on average, 4x more unique targets than random testing, and 3.5x more than ART using traditional distance-based methods.

Related papers

• Learning to Stop Overthinking at Test Time [1.0356759327536202]
  Test time scaling is one of the most active research areas that shows promise after training time scaling has reached its limits. We introduce a test time training method for determining the optimal amount of computation needed for each sample during test time. We also propose Conv-LiGRU, a novel recurrent architecture for efficient and robust visual reasoning.
  arXiv  Detail & Related papers  (2025-02-16T02:17:05Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Batch Bayesian Optimization for Replicable Experimental Design [56.64902148159355]
  Many real-world design problems evaluate multiple experimental conditions in parallel and replicate each condition multiple times due to large and heteroscedastic observation noise. We propose the Batch Thompson Sampling for Replicable Experimental Design framework, which encompasses three algorithms. We show the effectiveness of our algorithms in two practical real-world applications: precision agriculture and AutoML.
  arXiv  Detail & Related papers  (2023-11-02T12:46:03Z)
• Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
  We revisit the question of simple-versus-simple hypothesis testing with an eye towards computational complexity. An existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates.
  arXiv  Detail & Related papers  (2023-11-01T04:41:16Z)
• Toward Cost-effective Adaptive Random Testing: An Approximate Nearest Neighbor Approach [6.431858417308008]
  Adaptive Random Testing (ART) enhances the testing effectiveness (including fault-detection capability) of Random Testing (RT) Many ART algorithms have been investigated such as Fixed-Size-Candidate-Set ART (FSCS) and Restricted Random Testing (RRT)
  arXiv  Detail & Related papers  (2023-05-27T15:37:13Z)
• Comparative Study of Coupling and Autoregressive Flows through Robust Statistical Tests [0.0]
  We propose an in-depth comparison of coupling and autoregressive flows, both of the affine and rational quadratic type. We focus on a set of multimodal target distributions increasing dimensionality ranging from 4 to 400. Our results indicate that the A-RQS algorithm stands out both in terms of accuracy and training speed.
  arXiv  Detail & Related papers  (2023-02-23T13:34:01Z)
• Sequential Kernelized Independence Testing [101.22966794822084]
  We design sequential kernelized independence tests inspired by kernelized dependence measures. We demonstrate the power of our approaches on both simulated and real data.
  arXiv  Detail & Related papers  (2022-12-14T18:08:42Z)
• AdAUC: End-to-end Adversarial AUC Optimization Against Long-tail Problems [102.95119281306893]
  We present an early trial to explore adversarial training methods to optimize AUC. We reformulate the AUC optimization problem as a saddle point problem, where the objective becomes an instance-wise function. Our analysis differs from the existing studies since the algorithm is asked to generate adversarial examples by calculating the gradient of a min-max problem.
  arXiv  Detail & Related papers  (2022-06-24T09:13:39Z)
• GRACE-C: Generalized Rate Agnostic Causal Estimation via Constraints [3.2374399328078285]
  Graphical structures estimated by causal learning algorithms from time series data can provide misleading causal information if the causal timescale of the generating process fails to match the measurement timescale of the data. Existing algorithms provide limited resources to respond to this challenge, and so researchers must either use models that they know are likely misleading, or else forego causal learning entirely. Existing methods face up-to-four distinct shortfalls, as they might 1) require that the difference between causal and measurement is known; 2) only handle very small number of random variables when the timescale difference is unknown; 3) only apply to pairs of variables; or 4) be unable to
  arXiv  Detail & Related papers  (2022-05-18T22:38:57Z)
• Error Estimation for Sketched SVD via the Bootstrap [60.67199274260768]
  This paper develops a fully data-driven bootstrap method that numerically estimates the actual error of sketched singular vectors/values. The method is computationally inexpensive, because it operates only on sketched objects, and it requires no passes over the full matrix being factored.
  arXiv  Detail & Related papers  (2020-03-10T19:14:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.