Detailed Instructions: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Problem:Modern conflict-driven clause-learning (CDCL) Boolean SAT solvers provide efficient automatic analysis of real-world feature models (FM) of systems ranging from cars to operating systems. It is well-known that solver-based analysis of real-world FMs scale very well even though SAT instances obtained from such FMs are large, and the corresponding analysis problems are known to be NP-complete. To better understand why SAT solvers are so effective, we systematically studied many syntactic and semantic characteristics of a representative set of large real-world FMs. We discovered that a key reason why large real-world FMs are easy-toanalyze is that the vast majority of the variables in these models are unrestricted, i.e., the models are satisfiable for both true and false assignments to such variables under the current partial assignment. Given this discovery and our understanding of CDCL SAT solvers, we show that solvers can easily find satisfying assignments for such models without too many backtracks relative to the model size, explaining why solvers scale so well. Further analysis showed that the presence of unrestricted variables in these real-world models can be attributed to their high-degree of variability. Additionally, we experimented with a series of well-known nonbacktracking simplifications that are particularly effective in solving FMs. The remaining variables/clauses after simplifications, called the core, are so few that they are easily solved even with backtracking, further strengthening our conclusions. We explain the connection between our findings and backdoors, an idea posited by theorists to explain the power of SAT solvers. This connection strengthens our hypothesis that SAT-based analysis of FMs is easy. In contrast to our findings, previous research characterizes the difficulty of analyzing randomly-generated FMs in terms of treewidth. Our experiments suggest that the difficulty of analyzing realworld FMs cannot be explained in terms of treewidth. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. SPLC 2015, July 20 24, 2015, Nashville, TN, USA c ©️ 2015 ACM. ISBN 978-1-4503-3613-0/15/07. . . $15.00 DOI: http://dx.doi.org/10.1145/2791060.2791070 CCS Concepts Software and its engineering Software product lines;
Solution:
SAT-based Analysis of Large Real-world Feature Models is Easy