Adaptive Test Generation with Qgrams

• URL: http://arxiv.org/abs/2410.17907v1
• Date: Wed, 23 Oct 2024 14:26:51 GMT
• Title: Adaptive Test Generation with Qgrams
• 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. We show that ART with Qgrams 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: http://creativecommons.org/licenses/by/4.0/
• 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 Qgrams observed in previous runs. Test case selection then leverages this aggregated data to measure diversity (e.g., entropy of Qgrams), allowing us to reduce the computational complexity from quadratic to linear. Experiments with a benchmark of six web applications, show that ART with Qgrams covers, on average, 4x more unique targets than random testing, and 3.5x more than ART using traditional distance-based methods.

Related papers

• Sample, Don't Search: Rethinking Test-Time Alignment for Language Models [55.2480439325792]
  We introduce QAlign, a new test-time alignment approach. As we scale test-time compute, QAlign converges to sampling from the optimal aligned distribution for each individual prompt. By adopting recent advances in Markov chain Monte Carlo for text generation, our method enables better-aligned outputs without modifying the underlying model or even requiring logit access.
  arXiv  Detail & Related papers  (2025-04-04T00:41:40Z)
• 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)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  We show that the hardness of SAT encodings for LEC instances can be estimated textitw.r.t some SAT partitioning. The paper proposes several methods for constructing partitionings, which, when used in practice, allow one to estimate the hardness of SAT encodings for LEC with good accuracy.
  arXiv  Detail & Related papers  (2022-10-04T09:19:13Z)
• Sequential Permutation Testing of Random Forest Variable Importance Measures [68.8204255655161]
  It is proposed here to use sequential permutation tests and sequential p-value estimation to reduce the high computational costs associated with conventional permutation tests. The results of simulation studies confirm that the theoretical properties of the sequential tests apply. The numerical stability of the methods is investigated in two additional application studies.
  arXiv  Detail & Related papers  (2022-06-02T20:16:50Z)
• 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)
• Stress-Testing LiDAR Registration [52.24383388306149]
  We propose a method for selecting balanced registration sets, which are challenging sets of frame-pairs from LiDAR datasets. Perhaps unexpectedly, we find that the fastest and simultaneously most accurate approach is a version of advanced RANSAC.
  arXiv  Detail & Related papers  (2022-04-16T05:10:55Z)
• Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias [27.06618125828978]
  We consider the problem of learning the causal MAG of a system from observational data in the presence of latent variables and selection bias. We propose a novel computationally efficient constraint-based method that is sound and complete. We provide experimental results to compare the proposed approach with the state of the art on both synthetic and real-world structures.
  arXiv  Detail & Related papers  (2021-10-22T19:49:59Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)
• 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.