Adaptive random testing with Q-grams : the illusion comes true
Informazioni aggiuntive
Autori
Biagiola M.,
Feldt R.,
Tonella P.
Tipo
Articolo pubblicato in rivista scientifica
Anno
2025
Lingua
Inglese
Sommario
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, 4× more unique targets than random testing, and 3.5×more than ART using traditional distance-based methods.
Parole chiave
Software testing, Adaptive random testing, Diversity-based testing
Periodico
Proceedings of the ACM on Software Engineering
Volume
2
Numero ( Mese )
FSE
Pagine (o numero dell’articolo)
533-553
ISSN
2994-970X
DOI
Diffusione
Licenza
CC BY
Visibilità
Pubblico
Status open access
Hybrid
