Complete, Sound, and Scalable Identification of Minimal Failure-Causing Schema

Combinatorial Testing is an effective testing technique for detecting failures caused by interactions between parameters in an SUT (System Under Test). After a failure is detected, fault localization has to be performed on the failed test-case to identify the concrete faulty interactions ( i.e. Minimal Failure-causing Schemas, MFS). However, a longstanding “trilemma” persists in MFS identification: no existing method can simultaneously achieve completeness, soundness, and scalability. We present NoPend , resolving this trilemma through (1) an efficient data structure to characterize our knowledge of all schemas in the failed test-case, (2) pending space characterization via minimal hitting set generation, and (3) approximate greedy search that systematically eliminates all pending schemas. We evaluate NoPend against seven existing MFS identification methods on diverse real-world SUTs with authentic MFS, including large-scale SUTs with up to 208 parameters. The results demonstrate that NoPend not only leads in comprehensive metrics, but also attains either joint first place or top-tier place in each individual criterion: (1) completeness (100% MFS detection), (2) soundness (zero false positives), and (3) scalability in terms of execution time and additional test-case demand.