An Efficient Algorithm for Generating Minimal Unique-Cause MC/DC Test Cases for Singular Boolean Expressions
IEEE Access · 2026 · 14 · 113828-113846
DOI: 10.1109/access.2026.3714268 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Access, 2026. Verfasst von Robin Lee und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 37 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Modified Condition/Decision Coverage (MC/DC) is a mandatory structural coverage criterion for safety-critical software. Among its variants, Unique-Cause MC/DC provides a strong independence guarantee, but minimal test generation remains challenging for general Boolean decisions. This paper focuses on Singular Boolean Expressions (SBEs), a practically dominant decision class in avionics software in which each condition appears exactly once. We propose Robin’s Rule, a deterministic direct-construction method that builds an $N+1$ Unique-Cause MC/DC suite for SBEs without solver search, BDD path extraction, or $2^{N}$ truth-table enumeration. The method uses structural decomposition, Relation Table (RT) context selection, and exception handling. We provide explicit composition invariants, RT-preservation lemmas, an exception-handling contract, and a phase-by-phase $O(N^{2})$ complexity analysis. We evaluate 25 benchmark SBEs, consisting of 15 TCAS-II-derived SBE expressions and 10 randomly generated SBEs, using VectorCAST as an external coverage oracle and compare the results with fixed-configuration BDD and SAT baselines. We also report a separate checker-validated scalability stress test for synthetic SBEs with $N=25, 50, 75, 100, 150$ , and 200 conditions. Robin’s Rule constructs exact $N+1$ suites for all evaluated SBEs, achieves full VectorCAST-validated Unique-Cause MC/DC coverage on the 25 benchmark SBEs, and satisfies all independently checked witness-pair obligations in the scalability test. The contribution is a transparent and reproducible construction procedure for SBE-focused safety-critical verification, rather than a universal replacement for solver-based MC/DC generators.
Zitieren
APA
Lee, R., & Nam, Y. (2026). An Efficient Algorithm for Generating Minimal Unique-Cause MC/DC Test Cases for Singular Boolean Expressions. IEEE Access, 14, 113828-113846. https://doi.org/10.1109/access.2026.3714268
Vancouver
Lee R, Nam Y. An Efficient Algorithm for Generating Minimal Unique-Cause MC/DC Test Cases for Singular Boolean Expressions. IEEE Access. 2026;14:113828-113846. doi:10.1109/access.2026.3714268
BibTeX
@article{Lee2026,
author = {Lee, Robin and Nam, Youngho},
title = {An Efficient Algorithm for Generating Minimal Unique-Cause MC/DC Test Cases for Singular Boolean Expressions},
journal = {IEEE Access},
year = {2026},
volume = {14},
pages = {113828--113846},
doi = {10.1109/access.2026.3714268}
}
EUVIMED