|国家预印本平台
首页|An Efficient Algorithm for Generating Minimal Unique-Cause MC/DC Test cases for Singular Boolean Expressions

An Efficient Algorithm for Generating Minimal Unique-Cause MC/DC Test cases for Singular Boolean Expressions

An Efficient Algorithm for Generating Minimal Unique-Cause MC/DC Test cases for Singular Boolean Expressions

来源:Arxiv_logoArxiv
英文摘要

Modified Condition/Decision Coverage (MC/DC) is a mandatory structural coverage criterion for ensuring the reliability and safety of critical systems. While its strictest form, Unique-Cause MC/DC, offers the highest assurance, research on its efficient test generation has been lacking. This gap is particularly significant, as an analysis of large-scale avionics systems shows that 99.7% of all conditional decisions are, in fact, Singular Boolean Expressions (SBEs) the ideal structure for applying Unique-Cause MC/DC. This paper proposes 'Robin's Rule', a deterministic algorithm that directly constructs a minimal test set of N + 1 cases to guarantee 100% Unique-Cause MC/DC for SBEs with N conditions, without generating a full truth table. To validate our approach, we constructed a benchmark by reformulating the TCAS-II specifications into SBEs and verified the results using an industry-standard, certified commercial tool. The results confirm that our method consistently achieves 100% coverage with the theoretical minimum number of tests and is more efficient than the commercial tool. This work provides a practical and provably optimal solution for verifying safety-critical systems, ensuring both rigor and efficiency.

Robin Lee、Youngho Nam

航空计算技术、计算机技术

Robin Lee,Youngho Nam.An Efficient Algorithm for Generating Minimal Unique-Cause MC/DC Test cases for Singular Boolean Expressions[EB/OL].(2025-08-11)[2025-08-18].https://arxiv.org/abs/2507.14687.点此复制

评论