Efficient synthesis of feature models

Variability modeling, and in particular feature modeling, is a central element of model-driven software product line architectures. Such architectures often emerge from legacy code, but, unfortunately creating feature models from large, legacy systems is a long and arduous task. We address the problem of automatic synthesis of feature models from propositional constraints. We show that this problem is NP-hard. We design efficient techniques for synthesis of models from respectively CNF and DNF formulas, showing a 10- to 1000-fold performance improvement over known techniques for realistic benchmarks. Our algorithms are the first known techniques that are efficient enough to be applied to dependencies extracted from real systems, opening new possibilities of creating reverse engineering and model management tools for variability models. We discuss several such scenarios in the paper.