A Study of Non-Boolean Constraints in Variability Models of an Embedded Operating System

Many variability modeling tasks can be supported by automated analyses of models. Unfortunately, most analyses for Boolean variability models are NP-hard, while analyses for non-Boolean models easily become undecidable. It is thus crucial to exploit the properties of realistic models to construct viable analysis algorithms. Unfortunately, little work exists about non-Boolean models, and no benchmarks are available for such.

We present the non-Boolean aspects of 116 variability models available in the codebase of eCos—a real time embedded operating system. We characterize the types of nonBoolean features in the models, kinds and quantities of nonBoolean constraints in use, and the impact of these characteristics on the hardness of this model from analysis perspective. This way we provide researchers and practitioners with a basis for discussion of relevance of non-Boolean models and their analyses, along with the first ever benchmark for effectiveness of such analyses.