Source-linked AI summary
DTM: Deterministic Approaches for Black-box Test Suite Minimization with Tree-based Similarity
Md Siam, Shartaz Sajid Nahid, Md Arif Hasan, Nurul Ahad Tawhid, Kazi Sakib
TL;DR
Existing black-box test-suite minimization approaches can produce inconsistent selections because they rely on non-deterministic search, weakening repeatability in automated testing. DTM uses tree-based test-case similarity with deterministic subset-selection algorithms and reports improved accuracy, efficiency, and consistent outputs across repeated runs.
Problem
Non-deterministic test-suite minimization can produce inconsistent selections, undermining repeatability, debugging, benchmarking, and trust in automated testing pipelines.
Method
DTM converts test cases into ASTs, computes pairwise similarity with four tree-based measures, and selects subsets using modified MST, Spectral Clustering, or Dynamic Programming.
Results
DTM’s SC configuration with tree edit distance achieved 2.9% and 7% accuracy gains over LTM and ATM, respectively, while delivering 50 times and 2.82 times faster execution; configurations also produced identical results across runs.
Takeaways & Limitations
DTM provides a deterministic black-box test-suite minimization framework that combines consistent outputs with high fault-detection effectiveness and efficient execution.
Takeaways & Limitations
Evaluation on only Java projects from Defects4J limits external and language generalizability to projects with different structures, domains, testing practices, or programming languages.
Abstract
from arXiv · showhide
Black-box Test Suite Minimization (TSM) techniques reduce testing costs without requiring access to production code. However, existing effective approaches rely on evolutionary search algorithms, introducing non-determinism that produces inconsistent results across runs, undermining reliability in automated testing pipelines. We propose DTM (Deterministic approaches for black-box Test suite Minimization), a framework that ensures deterministic test suite reduction while preserving effectiveness and efficiency. DTM converts test cases into Abstract Syntax Trees and computes pairwise similarities using four tree-based measures. For subset selection, it employs three deterministic algorithms: Modified Minimum Spanning Tree, Spectral Clustering, and Dynamic Programming. We evaluated DTM on 16 Java projects from Defects4J with 661 buggy versions. Experimental results show that DTM achieved an average accuracy of 0.74 with an execution time of just 0.98 minutes, outperforming all state-of-the-art approaches. Moreover, it consistently produced identical results across multiple runs, ensuring full determinism.
I. INTRODUCTION
Black-box TSM reduces test suites using test artifacts rather than production code, but evolutionary subset selection can produce inconsistent outputs. DTM addresses this with tree-based similarity and deterministic selection while targeting effectiveness and efficiency.
- Black-box TSM reduces test cases while preserving fault-detection ability using test artifacts instead of production code.
- Evolutionary search strategies such as GA and NSGA-II introduce non-determinism into otherwise effective black-box TSM techniques.
- Deterministic selection is important because repeated runs should produce reproducible suites for reliable automated testing, debugging, and benchmarking.
- DTM converts test cases into ASTs, computes four tree-based similarities, and selects subsets with modified MST, SC, or DP.
- 7% accuracy gain and 50x faster execution were achieved by DTM’s best configuration over ATM, while accuracy was 2.9% higher and execution 2.8 times faster than LTM.
- All DTM configurations produced identical results across multiple runs, unlike the non-deterministic ATM and LTM baselines.
II. RELATED WORK
Black-box TSM evolved from metadata- and text-based methods toward AST- and LLM-based similarity, but recent effective approaches still rely on non-deterministic evolutionary search.
- FastLane used historical logs, commit complexity, and test runtime, but its reliance on historical data limited use where such data was unavailable.
- TF-IDF clustering removed metadata dependence but was efficient for C projects and failed to generalize well to Java programs.
- ATM parsed Java tests into ASTs and LTM embedded tests into vectors, using structural or distance-based pairwise similarity.
- Both ATM and LTM used GA or NSGA-II to select subsets minimizing overall similarity, making them non-deterministic.
III. METHODOLOGY
DTM is a black-box TSM framework that uses tree-based test-code similarity to reduce suites deterministically while targeting effectiveness and efficiency.
- DTM reduces test suites without production-code access by leveraging tree-based similarity of test code.
- The framework’s core steps are presented as an overview in Figure 1.
- DTM preprocesses test source code before similarity-based analysis by removing elements considered irrelevant to test behavior.
B. Generate AST
DTM represents test cases as ASTs to preserve syntactic structure and compares them with complementary tree-based similarity measures.
- Generate AST: ASTs preserve test-code syntactic structure that text-based or token-based processing may fail to capture.
- Generate AST: DTM adopts top-down, bottom-up, combined, and tree edit distance measures because each captures distinct structural information.
- Generate AST: Tree edit distance captures scattered structural changes by computing the minimum edits needed to transform one tree into another.
D. Selecting an optimal subset of test cases
DTM selects a diverse, minimally redundant subset by minimizing total pairwise similarity through three deterministic strategies: modified MST, Spectral Clustering, and Dynamic Programming.
- Selection objective: DTM formulates subset selection as choosing k test cases from n while minimizing total pairwise similarity.The objective is to maximize diversity and reduce redundancy.
- Modified MST: Modified MST starts with the least similar pair and iteratively adds the unselected test case with minimum loss until k cases are selected.Loss is the maximum similarity between a candidate and any currently selected test case.
- Modified MST: In the example, test cases 1 and 3 form the initial subset because their similarity is the lowest at 0.1.The method then evaluates loss values for remaining test cases using their similarities to the selected cases.
- Spectral Clustering: Spectral Clustering computes L = D −S and uses eigenvectors associated with the k smallest eigenvalues to form k clusters.It maximizes intra-cluster similarity while minimizing inter-cluster similarity.
- Spectral Clustering: DTM selects one representative from each cluster, producing a diverse subset with minimal redundancy.This selection balances coverage and diversity because cases within each cluster are highly similar.
3) Dynamic Programming:
The Dynamic Programming method selects a size-k subset by minimizing total pairwise similarity through a structured table and traceback procedure.
- Dynamic Programming: Dynamic Programming selects k test cases from n while minimizing the total pairwise similarity within the selected subset.The resulting subset is intended to contain minimal redundancy.
- Dynamic Programming: Each entry dp[i][j] stores the minimum total similarity for selecting j cases from the first i test cases, with j ≤ k and i ≤ n.The table records the best partial selection for each prefix and subset size.
- Dynamic Programming: The algorithm checks whether to include or exclude each current test case, then reconstructs the selected subset by tracing decisions backward.Traceback converts the completed DP table into the desired subset.
A. Experimental Design and Dataset
The evaluation measures DTM across 12 configurations on Defects4J’s Java projects, using multiple reduction budgets and accuracy and execution time as key metrics.
- Experimental setup: The study evaluates 12 configurations combining three deterministic algorithms with four test-similarity measures.Experiments use an Intel Core i5-9400F system with 16GB RAM and Ubuntu 22.04.
- Dataset: Defects4J contributes 661 buggy versions across 16 real-world Java projects.Project sizes range from 2 KLoC to 74 KLoC, and test suites range from 4 KLoC to 73 KLoC.
- Experimental setup: The minimization budgets target reduced suites containing 25%, 50%, or 75% of the original test cases.These budgets follow prior work and reflect common industry practices.
- Evaluation metrics: Accuracy measures the proportion of faults preserved in the reduced suite, while execution time measures efficiency.Accuracy uses fault-revealing tests in the reduced suite relative to faults in the original suite.
D. Results and Discussion
Under the 50% minimization budget, DTM’s Spectral Clustering with tree edit distance achieved the strongest accuracy and efficiency results, while DTM configurations remained deterministic across runs.
- Evaluation scope: The results focus on the 50% minimization budget because outcomes at the other budgets were consistent.The study evaluated all three budgets and reports the 50% case in detail.
- Effectiveness: Tree edit distance consistently delivered the highest accuracy across the evaluated algorithms.Table I compares DP, MST, and SC with four similarity measures alongside ATM and LTM.
- Effectiveness: SC with tree edit distance achieved mean accuracy 0.73 and median accuracy 0.72, the strongest algorithm–similarity combination.DP had mean accuracy between 0.56 and 0.63, while MST’s tree-edit-distance configuration reached mean accuracy 0.63.
- Baseline comparison: SC with tree edit distance gained 2.9% accuracy over LTM (0.71) and 7% over ATM (0.67).This configuration outperformed both reported baselines.
- Efficiency: SC achieved mean execution time 0.92 minutes and a 50 times speedup over ATM and 2.82 times improvement over LTM.For the largest project, Time, SC required 7.28 minutes across 3918 test cases.
V. THREATS TO VALIDITY
The evaluation is constrained by its exclusive use of Defects4J and Java test cases, limiting how broadly the findings may generalize.
- Defects4J-only evaluation may limit external validity across projects with different structures, domains, or testing practices.
- Java-only test suites may restrict generalization to other programming languages.
- Repeated experiments reduce variability concerns, but non-deterministic baselines may still introduce minor result fluctuations and threaten internal validity.Experiments used the same hardware and software configuration and were repeated 10 times.
VI. CONCLUSION AND FUTURE WORK
DTM combines tree-structured test-code similarity with deterministic subset-selection algorithms to produce consistent, efficient, and effective black-box test-suite reductions. Evaluation across Defects4J projects supports its suitability for reliable and reproducible test automation, while future work targets broader strategies, richer similarity representations, and multilingual validation.
- VI. CONCLUSION AND FUTURE WORK: DTM applies deterministic MST, SC, and DP algorithms to select test subsets with minimal total similarity.
- VI. CONCLUSION AND FUTURE WORK: Evaluation across 16 projects and 661 buggy versions found deterministic behavior, improved efficiency, and high fault detection effectiveness.
- VI. CONCLUSION AND FUTURE WORK: DTM is presented as practically suitable for reliable and reproducible test automation workflows.
- VI. CONCLUSION AND FUTURE WORK: Future work may examine optimization-based and hybrid deterministic strategies, tensor-based similarity matrices, and performance across additional programming languages.