BDD algorithms to perform hard analysis operations on variability models

Abstract

To compete in the global marketplace, manufacturers try to differentiate their products by focusing on individual customer needs. Fulfilling this goal requires companies to shift from mass production to mass customization. In the context of software development, software product line engineering has emerged as a cost-effective approach to developing families of similar products by supporting high levels of mass customization. Variability models are often used to specify the common and variable features of the products in one such family. Moreover, they model the inter-feature constraints which must be satisfied to guarantee the validity of the derived products. Despite the benefits of variability models, constructing and maintaining them can be a laborious task, especially in product lines with a large number of features and constraints. As a consequence, the study of automated techniques to reason on variability models has become an important research topic for the product line community. The aim of most automated techniques can be grouped in two classes: (i) ensuring the correctness of variability models, and (ii) providing guidance to derive products from a variability model. The former is usually put in the practise by means of analysis operations, which can be performed by black box reusing logic engines, such as SAT-solvers and binary decision diagram libraries. Unfortunately, such kind of reuse implies long computation times, and for some operations that need calling the logic engine an excessive amount of times, the approach does not scale. To overcome this problem, this thesis proposes new algorithms that directly deal with the binary decision decision diagram data structure encoding a variability model. In particular, our algorithms are specifically designed to detect those features that need to be included in all legal products, those ones that do not belong to any legal product, the number of products that include a particular feature, as well as the set of features that a particular feature needs to include or exclude to be part in any legal product. The second problem this thesis faces is related to product derivation. In complex variability models, deriving a valid product is not trivial task at all, since a lot of constraints between the features must be taken into account. To speed up product derivation, this thesis proposes a new approach that tries to minimise the number of configuration steps required on average to derive a whole product. Our approach, based on the information theory concept of entropy, takes advantage of the fact that, due to the inter-feature constraints, some decisions may be automatically derived from other decisions previously made.