NDLI: SAT-based analysis of large real-world feature models is easy

Please wait, while we are loading the content...

Synthesis of attributed feature models from product descriptions

Harnessing variability in product-lines of self-adaptive software systems

Using multiple feature models to specify configuration options for electrical transformers: an experience report

Test control algorithms for the validation of cyber-physical systems product lines

Understanding hybrid SPL composition impact on the refactoring into SPL

Using pure::variants across the product line lifecycle

Lean variation management: increasing business value with a diversified approach

Modular synthesis of product lines (ModSyn-PL)

Statistical analysis of probabilistic models of software product lines with quantitative constraints

Smart factory product lines: a configuration perspective on smart production ecosystems

Integrating variability and safety analysis models using commercial UML-based tools

Towards model-based derivation of systems in the industrial automation domain

An MDE tool for defining software product families with explicit variation points

Managing variability with feature models

Third International Workshop on Reverse Variability Engineering (REVE 2015)

What is a feature?: a qualitative study of features in industrial software product lines

Variability middleware for multi-tenant SaaS applications: a research roadmap for service lines

A process to support a systematic change impact analysis of variability and safety in automotive functions

Modeling aerospace systems product lines in SysML

Tooling support for variability and architectural patterns in systems engineering

Managing requirements in product lines

SPLat 2015: Second International Workshop on Software Product Line Analysis Tools

All-at-once-synthesis of controllers from scenario-based product line specifications

Preliminary product line support in BitKeeper

The more you do, the more you save: the superlinear cost avoidance effect of systems product line engineering

IVML: a DSL for configuration in variability-rich software ecosystems

Second generation systems and software product line engineering

SPLTea 2015: Second International Workshop on Software Product Line Teaching

Assessing product line derivation operators applied to Java source code: an empirical study

Automated testing of software-as-a-service configurations using a variability language

Evaluation across multiple views for variable automation systems

OPLA-tool: a support tool for search-based product line architecture design

EASy-Producer: from product lines to variability-rich software ecosystems

Family-based model checking using off-the-shelf model checkers: extended abstract

Building software product lines from conceptualized model patterns

Evolving an industrial analytics product line architecture

Mechanical product lifecycle management meets product line engineering

VariaMos: an extensible tool for engineering (dynamic) product lines

Leveraging model driven engineering in software product line architectures

Synthesizing type-safe compositions in feature oriented software designs using staged composition

Towards migrating object-oriented frameworks to enable synthesis of product line members

Applying the product lines paradigm to the quantitative analysis of collective adaptive systems

The BVR tool bundle to support product line engineering

CMT and FDE: tools to bridge the gap between natural language documents and feature diagrams

Maintaining feature traceability with embedded annotations

How automotive engineering is taking product line engineering to the extreme

Automating the variability formalization of a model family by means of common variability language

Choosy and picky: configuration of language product lines

Cyber-physical system product line engineering: comprehensive domain analysis and experience report

Composition of proof-carrying architectures for cyber-physical systems

Delta-oriented test case prioritization for integration testing of software product lines

User-level synthesis: treating product lines as systems of constraints

SAT-based analysis of large real-world feature models is easy

Using FMC for family-based analysis of software product lines

Bottom-up adoption of software product lines: a generic and extensible approach

Tuning GitHub for SPL development: branching models & repository operations for product engineers

REFAS: a PLE approach for simulation of self-adaptive systems requirements

Evolution in dynamic software product lines: challenges and perspectives

Fault-based product-line testing: effective sample generation based on feature-diagram mutation

Behavioral compatibility of simulink models for product line maintenance and evolution

Faster bug detection for software product lines with incomplete feature models

A product line of theories for reasoning about safe evolution of product lines

Safe evolution of product populations and multi product lines

Defining metric thresholds for software product lines: a comparative study

Empirical comparison of regression methods for variability-aware performance prediction

SAT-based analysis of large real-world feature models is easy

Content Provider	ACM Digital Library
Author	Ganesh, Vijay Liang, Jia Hui Raman, Venkatesh Czarnecki, Krzysztof
Abstract	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-to-analyze 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 real-world FMs cannot be explained in terms of treewidth.
Starting Page	91
Ending Page	100
Page Count	10
File Format	PDF
ISBN	9781450336130
DOI	10.1145/2791060.2791070
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-07-20
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Feature model Sat-based analysis
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in