Automated testing and debugging of configuration knowledge bases with direct diagnosis

Abstract

Abstract Configuration knowledge bases are used to represent commonality and variability properties of physical products as well as software artifacts. These knowledge bases can become quite large and complex and – as a result – are in the need of testing and debugging support. If some test cases become inconsistent with the configuration knowledge base, this means that some constraints in the knowledge base do not represent expected variability properties of the underlying product domain. In this article, we present MSSDirect , a direct diagnosis approach for test case driven automated testing and debugging of configuration knowledge bases. This approach helps knowledge engineers identify minimal sets of faulty constraints in a knowledge base which can be regarded as an explanation of the observed faulty behavior. Furthermore, we introduce a tunable parameter $$\lambda$$ that allows knowledge engineers to explicitly trade off diagnosis minimality against computational efficiency. Our empirical evaluation on six real-world configuration knowledge bases (64 to 13,972 constraints) shows that MSSDirect substantially outperforms existing hitting set based approaches in the majority of evaluated scenarios. Speedups reach up to three orders of magnitude at a 20% rate of inconsistency-inducing test cases and up to four orders of magnitude at higher rates (30%, 50%). In these scenarios, the baseline frequently exceeds timeout limits. For very large knowledge bases with few violated test cases, the baseline remains competitive, indicating complementary strengths of the two approaches.