A Graph-Based Model for Automatic Test Case Generation from Textual Requirements with Hierarchical Coverage
Mathematical Modeling and Computing · 2026 · 13 (1) · 311-320
DOI: 10.23939/mmc2026.01.311 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Modeling and Computing, 2026. Verfasst von B. B. Liubinskyi und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 19 Literaturangaben.
Abstract (Originalsprache)
The automation of software test case generation from natural language requirements remains a critical challenge in software engineering. While large language models (LLMs) demonstrate impressive generation capabilities, they suffer from high discrepancy rates (up to 57% for direct generation), hallucinated test steps, and lack formal verification mechanisms for safety-critical constraints. This paper presents a novel algorithmic framework that addresses these limitations through five principal contributions. First, we introduce the Neuro-Symbolic Requirements Graph (NSRG) model GNS=(V,E,w,Γ,Ψ), which integrates transformer-derived semantic dependencies with Linear Temporal Logic (LTL) constraints (Ψ) and control flow subgraphs (Γ). Second, we derive the Extended Minimum Coverage Theorem establishing theoretical lower bounds for hierarchical coverage. Third, we propose the Hybrid Semantic-Temporal Coverage (HSTC) metric utilizing Determinantal Point Processes (DPP) to systematically optimize test suite diversity. Fourth, we develop the MCTS-Guided Neuro-Symbolic Traversal (MCTS-NST) algorithm based on Monte Carlo Tree Search. Fifth, we implement Dynamic HNSW Indexing reducing graph construction complexity from O(|V|2) to O(|V|log|V|). Experimental evaluation on four benchmark datasets (3,581 requirements) demonstrates: 96.8% precision, 98.4% recall, 99.1% LTL satisfaction rate for negative requirements, and 0.94% discrepancy rate. The framework achieves practitioner acceptance scores of 4.85/5.
Zitieren
APA
Liubinskyi, B. B., & Zvarych, M. M. (2026). A Graph-Based Model for Automatic Test Case Generation from Textual Requirements with Hierarchical Coverage. Mathematical Modeling and Computing, 13(1), 311-320. https://doi.org/10.23939/mmc2026.01.311
Vancouver
Liubinskyi BB, Zvarych MM. A Graph-Based Model for Automatic Test Case Generation from Textual Requirements with Hierarchical Coverage. Mathematical Modeling and Computing. 2026;13(1):311-320. doi:10.23939/mmc2026.01.311
BibTeX
@article{Liubinskyi2026,
author = {Liubinskyi, B. B. and Zvarych, M. M.},
title = {A Graph-Based Model for Automatic Test Case Generation from Textual Requirements with Hierarchical Coverage},
journal = {Mathematical Modeling and Computing},
year = {2026},
volume = {13},
number = {1},
pages = {311--320},
doi = {10.23939/mmc2026.01.311}
}
EUVIMED