An overview on analysis tools for software product lines
---
paper_title: Clafer tools for product line engineering

paper_content:

Clafer is a lightweight yet expressive language for structural modeling: feature modeling and configuration, class and object modeling, and metamodeling. Clafer Tools is an integrated set of tools based on Clafer. In this paper, we describe some product-line variability modeling scenarios of Clafer Tools from the viewpoints of product-line owner, product-line engineer, and product engineer.
---
paper_title: Feature-Oriented Domain Analysis (FODA) Feasibility Study

paper_content:

Abstract : Successful Software reuse requires the systematic discovery and exploitation of commonality across related software systems. By examining related software systems and the underlying theory of the class of systems they represent, domain analysis can provide a generic description of the requirements of that class of systems and a set of approaches for their implementation. This report will establish methods for performing a domain analysis and describe the products of the domain analysis process. To illustrate the application of domain analysis to a representative class of software systems, this report will provide a domain analysis of window management system software.
---
paper_title: A Classification and Survey of Analysis Strategies for Software Product Lines

paper_content:

Software-product-line engineering has gained considerable momentum in recent years, both in industry and in academia. A software product line is a family of software products that share a common set of features. Software product lines challenge traditional analysis techniques, such as type checking, model checking, and theorem proving, in their quest of ensuring correctness and reliability of software. Simply creating and analyzing all products of a product line is usually not feasible, due to the potentially exponential number of valid feature combinations. Recently, researchers began to develop analysis techniques that take the distinguishing properties of software product lines into account, for example, by checking feature-related code in isolation or by exploiting variability information during analysis. The emerging field of product-line analyses is both broad and diverse, so it is difficult for researchers and practitioners to understand their similarities and differences. We propose a classification of product-line analyses to enable systematic research and application. Based on our insights with classifying and comparing a corpus of 123 research articles, we develop a research agenda to guide future research on product-line analyses.
---
paper_title: Feature-Oriented Software Product Lines: Concepts and Implementation

paper_content:

While standardization has empowered the software industry to substantially scale software development and to provide affordable software to a broad market, it often does not address smaller market segments, nor the needs and wishes of individual customers. Software product lines reconcile mass production and standardization with mass customization in software engineering. Ideally, based on a set of reusable parts, a software manufacturer can generate a software product based on the requirements of its customer. The concept of features is central to achieving this level of automation, because features bridge the gap between the requirements the customer has and the functionality a product provides. Thus features are a central concept in all phases of product-line development. The authors take a developers viewpoint, focus on the development, maintenance, and implementation of product-line variability, and especially concentrate on automated product derivation based on a users feature selection. The book consists of three parts. Part I provides a general introduction to feature-oriented software product lines, describing the product-line approach and introducing the product-line development process with its two elements of domain and application engineering. The pivotal part II covers a wide variety of implementation techniques including design patterns, frameworks, components, feature-oriented programming, and aspect-oriented programming, as well as tool-based approaches including preprocessors, build systems, version-control systems, and virtual separation of concerns. Finally, part III is devoted to advanced topics related to feature-oriented product lines like refactoring, feature interaction, and analysis tools specific to product lines. In addition, an appendix lists various helpful tools for software product-line development, along with a description of how they relate to the topics covered in this book. To tie the book together, the authors use two running examples that are well documented in the product-line literature: data management for embedded systems, and variations of graph data structures. They start every chapter by explicitly stating the respective learning goals and finish it with a set of exercises; additional teaching material is also available online. All these features make the book ideally suited for teaching both for academic classes and for professionals interested in self-study.
---
paper_title: Software Product Lines: Practices and Patterns

paper_content:

Foreword. Preface. Acknowledgements. Dedication. Reader's Guide. I. SOFTWARE PRODUCT LINE FUNDAMENTALS. 1. Basic Ideas and Terms. What Is a Software Product Line? What Software Product Lines Are Not. Fortuitous Small-Grained Reuse. Single-System Development with Reuse. Just Component-Based Development. Just a Reconfigurable Architecture. Releases and Versions of Single Products. Just a Set of Technical Standards. A Note on Terminology. For Further Reading. Discussion Questions. 2. Benefits. Organizational Benefits. Individual Benefits. Benefits versus Costs. For Further Reading. Discussion Questions. 3. The Three Essential Activities. What Are the Essential Activities? Core Asset Development. Product Development. Management. All Three Together. For Further Reading. Discussion Questions. II. SOFTWARE PRODUCT LINE PRACTICE AREAS. Describing the Practice Areas. Starting versus Running a Product Line. Organizing the Practice Areas. 4. Software Engineering Practice Areas. Architecture Definition. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Architecture Evaluation. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Component Development. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. COTS Utilization. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Mining Existing Assets. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. Discussion Questions. Requirements Engineering. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Software System Integration. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Testing. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Understanding Relevant Domains. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. 5. Technical Management Practice Areas. Configuration Management. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Data Collection, Metrics, and Tracking. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Make/Buy/Mine/Commission Analysis. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Process Definition. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Scoping. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Technical Planning. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. Discussion Questions. Technical Risk Management. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Tool Support. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. 6. Organizational Management Practice Areas. Building a Business Case. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Customer Interface Management. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. Discussion Questions. Developing an Acquisition Strategy. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Funding. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. Discussion Questions. Launching and Institutionalizing. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. Discussion Questions. Market Analysis. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Operations. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Organizational Planning. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. Discussion Questions. Organizational Risk Management. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Structuring the Organization. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. Discussion Questions. Technology Forecasting. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. Training. Aspects Peculiar to Product Lines. Application to Core Asset Development. Application to Product Development. Specific Practices. Practice Risks. For Further Reading. Discussion Questions. III. PUTTING THE PRACTICE AREAS INTO ACTION. 7. Software Product Line Practice Patterns. The Value of Patterns. Software Product Line Practice Pattern Descriptions. The Curriculum Pattern. The Essentials Coverage Pattern. Each Asset Pattern. What to Build Pattern. Product Parts Pattern. Assembly Line Pattern. Monitor Pattern. Product Builder Pattern. Cold Start Pattern. In Motion Pattern. Process Pattern. Factory Pattern. Other Patterns. Practice Area Coverage. Discussion Questions. 8. Product Line Technical Probe. What Is the Product Line Technical Probe? Probe Interview Questions. Probe Participants. Probe Process. Using the Probe Results. Conducting a Mini Self-Probe. Discussion Questions. 9. Cummins Engine Company: Embracing the Future. Prologue. Company History. A Product Line of Engine Software. Getting off the Ground. An Organization Structured for Cooperation. Running the Product Line. Results. Lessons Learned. Epilogue. Practice Area Compendium. For Further Reading. Discussion Questions. 10. Control Channel Toolkit: A Software Product Line that Controls Satellites. Contextual Background. Organizational Profiles. Project History. Control Channels. Launching CCT. Developing a Business Case for CCT. Developing the Acquisition Strategy and Funding CCT. Structuring the CCT Organization. Organizational and Technical Planning. Operations. Engineering the CCT Core Assets. Domain Analysis. Architecture. Component Engineering. Testing: Application and Test Engineering. Sustainment Engineering: Product Line Evolution. Documentation. Managing the CCT Effort. Early Benefits from CCT. First CCT Product. Benefits beyond CCT Products. Lessons and Issues. Tool Support Is Inadequate. Domain Analysis Documentation Is Important. An Early Architecture Focus Is Best. Product Builders Need More Support. CCT Users Need Reuse Metrics. It Pays to Be Flexible, and Cross-Unit Teams Work. A Real Product Is a Benefit. Summary. For Further Reading. Discussion Questions. 11. Successful Software product Line Development in Small Organization. Introduction. The Early Years. The MERGER Software Product Line. Market Maker Software Product Line Practices. Architecture Definition. Component Development. Structuring (and Staffing) the Organization. Testing. Data Collection and Metrics. Launching and Institutionalizing the Product Line. Understanding the Market. Technology Forecasting. A Few Observations. Effects of Company Culture. Cost Issues. The Customer Paradox. Tool Support. Lessons Learned. Drawbacks. Conclusions: Software Product Lines in Small Organizations. For Further Reading. Discussion Questions. 12. Conclusions: Practices, Patterns and Payoffs. The Practices. The Patterns. The Success Factors. The Payoff. Finale. Glossary. Bibliography. Index.
---
paper_title: Automated analysis of feature models 20 years later: A literature review

paper_content:

Software product line engineering is about producing a set of related products that share more commonalities than variabilities. Feature models are widely used for variability and commonality management in software product lines. Feature models are information models where a set of products are represented as a set of features in a single model. The automated analysis of feature models deals with the computer-aided extraction of information from feature models. The literature on this topic has contributed with a set of operations, techniques, tools and empirical results which have not been surveyed until now. This paper provides a comprehensive literature review on the automated analysis of feature models 20 years after of their invention. This paper contributes by bringing together previously disparate streams of work to help shed light on this thriving area. We also present a conceptual framework to understand the different proposals as well as categorise future contributions. We finally discuss the different studies and propose some challenges to be faced in the future.
---
paper_title: Delta-oriented programming of software product lines

paper_content:

Feature-oriented programming (FOP) implements software product lines by composition of feature modules. It relies on the principles of stepwise development. Feature modules are intended to refer to exactly one product feature and can only extend existing implementations. To provide more flexibility for implementing software product lines, we propose delta-oriented programming (DOP) as a novel programming language approach. A product line is represented by a core module and a set of delta modules. The core module provides an implementation of a valid product that can be developed with well-established single application engineering techniques. Delta modules specify changes to be applied to the core module to implement further products by adding, modifying and removing code. Application conditions attached to delta modules allow handling combinations of features explicitly. A product implementation for a particular feature configuration is generated by applying incrementally all delta modules with valid application condition to the core module. In order to evaluate the potential of DOP, we compare it to FOP, both conceptually and empirically.
---
paper_title: Feature-Oriented Domain Analysis (FODA) Feasibility Study

paper_content:

Abstract : Successful Software reuse requires the systematic discovery and exploitation of commonality across related software systems. By examining related software systems and the underlying theory of the class of systems they represent, domain analysis can provide a generic description of the requirements of that class of systems and a set of approaches for their implementation. This report will establish methods for performing a domain analysis and describe the products of the domain analysis process. To illustrate the application of domain analysis to a representative class of software systems, this report will provide a domain analysis of window management system software.
---
paper_title: Feature-Oriented Programming: A Fresh Look at Objects

paper_content:

We propose a new model for flexible composition of objects from a set of features. Features are similar to (abstract) subclasses, but only provide the core functionality of a (sub)class. Overwriting other methods is viewed as resolving feature interactions and is specified separately for two features at a time. This programming model allows to compose features (almost) freely in a way which generalizes inheritance and aggregation. For a set of n features, an exponential number of different feature combinations is possible, assuming a quadratic number of interaction resolutions. We present the feature model as an extension of Java and give two translations to Java, one via inheritance and the other via aggregation. We further discuss parameterized features, which work nicely with our feature model and can be translated into Pizza, an extension of Java.
---
paper_title: A Classification and Survey of Analysis Strategies for Software Product Lines

paper_content:

Software-product-line engineering has gained considerable momentum in recent years, both in industry and in academia. A software product line is a family of software products that share a common set of features. Software product lines challenge traditional analysis techniques, such as type checking, model checking, and theorem proving, in their quest of ensuring correctness and reliability of software. Simply creating and analyzing all products of a product line is usually not feasible, due to the potentially exponential number of valid feature combinations. Recently, researchers began to develop analysis techniques that take the distinguishing properties of software product lines into account, for example, by checking feature-related code in isolation or by exploiting variability information during analysis. The emerging field of product-line analyses is both broad and diverse, so it is difficult for researchers and practitioners to understand their similarities and differences. We propose a classification of product-line analyses to enable systematic research and application. Based on our insights with classifying and comparing a corpus of 123 research articles, we develop a research agenda to guide future research on product-line analyses.
---
paper_title: Feature-Oriented Software Product Lines: Concepts and Implementation

paper_content:

While standardization has empowered the software industry to substantially scale software development and to provide affordable software to a broad market, it often does not address smaller market segments, nor the needs and wishes of individual customers. Software product lines reconcile mass production and standardization with mass customization in software engineering. Ideally, based on a set of reusable parts, a software manufacturer can generate a software product based on the requirements of its customer. The concept of features is central to achieving this level of automation, because features bridge the gap between the requirements the customer has and the functionality a product provides. Thus features are a central concept in all phases of product-line development. The authors take a developers viewpoint, focus on the development, maintenance, and implementation of product-line variability, and especially concentrate on automated product derivation based on a users feature selection. The book consists of three parts. Part I provides a general introduction to feature-oriented software product lines, describing the product-line approach and introducing the product-line development process with its two elements of domain and application engineering. The pivotal part II covers a wide variety of implementation techniques including design patterns, frameworks, components, feature-oriented programming, and aspect-oriented programming, as well as tool-based approaches including preprocessors, build systems, version-control systems, and virtual separation of concerns. Finally, part III is devoted to advanced topics related to feature-oriented product lines like refactoring, feature interaction, and analysis tools specific to product lines. In addition, an appendix lists various helpful tools for software product-line development, along with a description of how they relate to the topics covered in this book. To tie the book together, the authors use two running examples that are well documented in the product-line literature: data management for embedded systems, and variations of graph data structures. They start every chapter by explicitly stating the respective learning goals and finish it with a set of exercises; additional teaching material is also available online. All these features make the book ideally suited for teaching both for academic classes and for professionals interested in self-study.
---
paper_title: Aspect-oriented programming

paper_content:

We have found many programming problems for which neither procedural nor object-oriented programming techniques are sufficient to clearly capture some of the important design decisions the program must implement. This forces the implementation of those design decisions to be scattered throughout the code, resulting in “tangled” code that is excessively difficult to develop and maintain. We present an analysis of why certain design decisions have been so difficult to clearly capture in actual code. We call the properties these decisions address aspects, and show that the reason they have been hard to capture is that they cross-cut the system's basic functionality. We present the basis for a new programming technique, called aspect-oriented programming, that makes it possible to clearly express programs involving such aspects, including appropriate isolation, composition and reuse of the aspect code. The discussion is rooted in systems we have built using aspect-oriented programming.
---
paper_title: Virtual Separation of Concerns -- A Second Chance for Preprocessors

paper_content:

Conditional compilation with preprocessors like cpp is a simple but eective means to implement variability. By annotating code fragments with #ifdef and #endif directives, dierent program variants with or without these fragments can be created, which can be used (among others) to implement software product lines. Although, preprocessors are frequently used in practice, they are often criticized for their negative eect on code quality and maintainability. In contrast to modularized implementations, for example using components or aspects, preprocessors neglect separation of concerns, are prone to introduce subtle errors, can entirely obfuscate the source code, and limit reuse. Our aim is to rehabilitate the preprocessor by showing how simple tool support can address these problems and emulate some benets of modularized implementations. At the same time we emphasize unique benets of preprocessors, like simplicity and language independence. Although we do not have a denitive answer on how to implement variability, we want highlight opportunities to improve preprocessors and encourage research toward novel preprocessor-based approaches.
---
paper_title: Reducing Configurations to Monitor in a Software Product Line

paper_content:

A software product line is a family of programs where each program is defined by a unique combination of features. Product lines, like conventional programs, can be checked for safety properties through execution monitoring. However, because a product line induces a number of programs that is potentially exponential in the number of features, it would be very expensive to use existing monitoring techniques: one would have to apply those techniques to every single program. Doing so would also be wasteful because many programs can provably never violate the stated property. We introduce a monitoring technique dedicated to product lines that, given a safety property, statically determines the feature combinations that cannot possibly violate the property, thus reducing the number of programs to monitor. Experiments show that our technique is effective, particularly for safety properties that crosscut many optional features.
---
paper_title: Model composition in product lines and feature interaction detection using critical pair analysis

paper_content:

Software product lines (SPL) are an established technology for developing families of systems. In particular, they focus on modeling commonality and variability, that is, they are based on identifying features common to all members of the family and variable features that appear only in some members. Model-based development methods for product lines advocate the construction of SPL requirements, analysis and design models for features. This paper describes an approach for maintaining feature separation during modeling using a UML composition language based on graph transformations. This allows models of features to be reused more easily. The language can be used to compose the SPL models for a given set of features. Furthermore, critical pair analysis is used to detect dependencies and conflicts between features during analysis and design modeling. The approach is supported by a tool that allows automated composition of UML models of features and detection of some kinds of feature interactions.
---
paper_title: ASADAL: a tool system for co-development of software and test environment based on product line engineering

paper_content:

Recently, product line software engineering (PLSE) is gaining popularity. To employ PLSE methods, many organizations are looking for a tool system that supports PLSE methods so that core assets and target software can be developed and tested in an effective and systematic way.ASADAL (A System Analysis and Design Aid tooL) supports the entire lifecycle of software development process based on a PLSE method called FORM (Feature-Oriented Reuse Method) [6]. It supports domain analysis, architecture and component design, code generation, and simulation-based verification and validation (V&V). Using the tool, users may co-develop target software and its test environment and verify software in a continuous and incremental way.
---
paper_title: Integration Testing of Software Product Lines Using Compositional Symbolic Execution

paper_content:

Software product lines are families of products defined by feature commonality and variability, with a well-managed asset base. Recent work in testing of software product lines has exploited similarities across development phases to reuse shared assets and reduce test effort. The use of feature dependence graphs has also been employed to reduce testing effort, but little work has focused on code level analysis of dataflow between features. In this paper we present a compositional symbolic execution technique that works in concert with a feature dependence graph to extract the set of possible interaction trees in a product family. It composes these to incrementally and symbolically analyze feature interactions. We experiment with two product lines and determine that our technique can reduce the overall number of interactions that must be considered during testing, and requires less time to run than a traditional symbolic execution technique.
---
paper_title: PLEDGE: a product line editor and test generation tool

paper_content:

Specific requirements of clients lead to the development of variants of the same software. These variants form a Software Product Line (SPL). Ideally, testing a SPL involves testing all the software products that can be configured through the combination of features. This, however, is intractable in practice since a) large SPLs can lead to millions of possible software variants and b) the testing process is usually limited by budget and time constraints. To overcome this problem, this paper introduces PLEDGE, an open source tool that selects and prioritizes the product configurations maximizing the feature interactions covered. The uniqueness of PLEDGE is that it bypasses the computation of the feature interactions, allowing to scale to large SPLs.
---
paper_title: A systematic mapping study of software product lines testing

paper_content:

ContextIn software development, Testing is an important mechanism both to identify defects and assure that completed products work as specified. This is a common practice in single-system development, and continues to hold in Software Product Lines (SPL). Even though extensive research has been done in the SPL Testing field, it is necessary to assess the current state of research and practice, in order to provide practitioners with evidence that enable fostering its further development. ObjectiveThis paper focuses on Testing in SPL and has the following goals: investigate state-of-the-art testing practices, synthesize available evidence, and identify gaps between required techniques and existing approaches, available in the literature. MethodA systematic mapping study was conducted with a set of nine research questions, in which 120 studies, dated from 1993 to 2009, were evaluated. ResultsAlthough several aspects regarding testing have been covered by single-system development approaches, many cannot be directly applied in the SPL context due to specific issues. In addition, particular aspects regarding SPL are not covered by the existing SPL approaches, and when the aspects are covered, the literature just gives brief overviews. This scenario indicates that additional investigation, empirical and practical, should be performed. ConclusionThe results can help to understand the needs in SPL Testing, by identifying points that still require additional investigation, since important aspects regarding particular points of software product lines have not been addressed yet.
---
paper_title: Exploring variability-aware execution for testing plugin-based web applications

paper_content:

In plugin-based systems, plugin conflicts may occur when two or more plugins interfere with one another, changing their expected behaviors. It is highly challenging to detect plugin conflicts due to the exponential explosion of the combinations of plugins (i.e., configurations). In this paper, we address the challenge of executing a test case over many configurations. Leveraging the fact that many executions of a test are similar, our variability-aware execution runs common code once. Only when encountering values that are different depending on specific configurations will the execution split to run for each of them. To evaluate the scalability of variability-aware execution on a large real-world setting, we built a prototype PHP interpreter called Varex and ran it on the popular WordPress blogging Web application. The results show that while plugin interactions exist, there is a significant amount of sharing that allows variability-aware execution to scale to 2^50 configurations within seven minutes of running time. During our study, with Varex, we were able to detect two plugin conflicts: one was recently reported on WordPress forum and another one was not previously discovered.
---
paper_title: Feature integration using a feature construct

paper_content:

Abstract A feature is a unit of functionality that may be added to (or omitted from) a system. Examples of features are plug-ins for software packages or additional services offered by telecommunications providers. Many features override the default behaviour of the system, which may lead to unforeseen behaviour of the system; this is known as feature interaction . We propose a feature construct for defining features, and use it to provide a plug-and-play framework for exploring feature interactions. Our approach to the feature interaction problem has the following characteristics: • Features are treated as first-class objects during the development phase. • A method is given for integrating a feature into a system description. It allows features to override existing behaviour of the system being developed. • A prototype tool has been developed for performing the integration. • Interactions between features may be witnessed. In principle, our approach is quite general and need not be tied to any particular system description language. In this paper, however, we develop the approach in the context of the SMV model checking system. We describe two case studies in detail: a lift system and a telephone system.
---
paper_title: Incremental Test Generation for Software Product Lines

paper_content:

Recent advances in mechanical techniques for systematic testing have increased our ability to automatically find subtle bugs, and hence, to deploy more dependable software. This paper builds on one such systematic technique, scope-bounded testing, to develop a novel specification-based approach for efficiently generating tests for products in a software product line. Given properties of features as first-order logic formulas in Alloy, our approach uses SAT-based analysis to automatically generate test inputs for each product in a product line. To ensure soundness of generation, we introduce an automatic technique for mapping a formula that specifies a feature into a transformation that defines incremental refinement of test suites. Our experimental results using different data structure product lines show that an incremental approach can provide an order of magnitude speedup over conventional techniques. We also present a further optimization using dedicated integer constraint solvers for feature properties that introduce integer constraints, and show how to use a combination of solvers in tandem for solving Alloy formulas.
---
paper_title: Strategies for product-line verification: Case studies and experiments

paper_content:

Product-line technology is increasingly used in mission-critical and safety-critical applications. Hence, researchers are developing verification approaches that follow different strategies to cope with the specific properties of product lines. While the research community is discussing the mutual strengths and weaknesses of the different strategies - mostly at a conceptual level - there is a lack of evidence in terms of case studies, tool implementations, and experiments. We have collected and prepared six product lines as subject systems for experimentation. Furthermore, we have developed a model-checking tool chain for C-based and Java-based product lines, called SPLverifier, which we use to compare sample-based and family-based strategies with regard to verification performance and the ability to find defects. Based on the experimental results and an analytical model, we revisit the discussion of the strengths and weaknesses of product-line-verification strategies.
---
paper_title: A product line based aspect-oriented generative unit testing approach to building quality components

paper_content:

The quality of component-based systems highly depends on how effectively testing is carried out. To achieve the maximal testing effectiveness, this paper presents a product line based aspect oriented approach to unit testing. The aspect product line facilitates the automatic creation of aspect test cases that deal with specific quality requirements. An expandable repository of reusable aspect test cases has been developed. A prototype tool is built to verify and lever up the approach.
---
paper_title: Avoiding redundant testing in application engineering

paper_content:

Many software product line testing techniques have been presented in the literature. The majority of those techniques address how to define reusable test assets (such as test models or test scenarios) in domain engineering and how to exploit those assets during application engineering. In addition to test case reuse however, the execution of test cases constitutes one important activity during application testing. Without a systematic support for the test execution in application engineering, while considering the specifics of product lines, product line artifacts might be tested redundantly. Redundant testing in application engineering, however, can lead to an increased testing effort without increasing the chance of uncovering failures. In this paper, we propose the model-based ScenTED-DF technique to avoid redundant testing in application engineering. Our technique builds on data flow-based testing techniques for single systems and adapts and extends those techniques to consider product line variability. The paper sketches the prototypical implementation of our technique to show its general feasibility and automation potential, and it describes the results of experiments using an academic product line to demonstrate that ScenTED-DF is capable of avoiding redundant tests in application engineering.
---
paper_title: Evolutionary Search-based Test Generation for Software Product Line Feature Models

paper_content:

Product line-based software engineering is a paradigm that models the commonalities and variabilities of different applications of a given domain of interest within a unique framework and enhances rapid and low cost development of new applications based on reuse engineering principles. Despite the numerous advantages of software product lines, it is quite challenging to comprehensively test them. This is due to the fact that a product line can potentially represent many different applications; therefore, testing a single product line requires the test of its various applications. Theoretically, a product line with n software features can be a source for the development of 2n application. This requires the test of 2n applications if a brute-force comprehensive testing strategy is adopted. In this paper, we propose an evolutionary testing approach based on Genetic Algorithms to explore the configuration space of a software product line feature model in order to automatically generate test suites. We will show through the use of several publicly-available product line feature models that the proposed approach is able to generate test suites of O(n) size complexity as opposed to O(2n) while at the same time form a suitable tradeoff balance between error coverage and feature coverage in its generated test suites.
---
paper_title: A survey of combinatorial testing

paper_content:

Combinatorial Testing (CT) can detect failures triggered by interactions of parameters in the Software Under Test (SUT) with a covering array test suite generated by some sampling mechanisms. It has been an active field of research in the last twenty years. This article aims to review previous work on CT, highlights the evolution of CT, and identifies important issues, methods, and applications of CT, with the goal of supporting and directing future practice and research in this area. First, we present the basic concepts and notations of CT. Second, we classify the research on CT into the following categories: modeling for CT, test suite generation, constraints, failure diagnosis, prioritization, metric, evaluation, testing procedure and the application of CT. For each of the categories, we survey the motivation, key issues, solutions, and the current state of research. Then, we review the contribution from different research groups, and present the growing trend of CT research. Finally, we recommend directions for future CT research, including: (1) modeling for CT, (2) improving the existing test suite generation algorithm, (3) improving analysis of testing result, (4) exploring the application of CT to different levels of testing and additional types of systems, (5) conducting more empirical studies to fully understand limitations and strengths of CT, and (6) combining CT with other testing techniques.
---
paper_title: On strategies for testing software product lines: A systematic literature review

paper_content:

Context: Testing plays an important role in the quality assurance process for software product line engineering. There are many opportunities for economies of scope and scale in the testing activities, but techniques that can take advantage of these opportunities are still needed. Objective: The objective of this study is to identify testing strategies that have the potential to achieve these economies, and to provide a synthesis of available research on SPL testing strategies, to be applied towards reaching higher defect detection rates and reduced quality assurance effort. Method: We performed a literature review of two hundred seventy-six studies published from the year 1998 up to the 1st semester of 2013. We used several filters to focus the review on the most relevant studies and we give detailed analyses of the core set of studies. Results: The analysis of the reported strategies comprised two fundamental aspects for software product line testing: the selection of products for testing, and the actual test of products. Our findings indicate that the literature offers a large number of techniques to cope with such aspects. However, there is a lack of reports on realistic industrial experiences, which limits the inferences that can be drawn. Conclusion: This study showed a number of leveraged strategies that can support both the selection of products, and the actual testing of products. Future research should also benefit from the problems and advantages identified in this study.
---
paper_title: Automated and Scalable T-wise Test Case Generation Strategies for Software Product Lines

paper_content:

Software Product Lines (SPL) are difficult to validate due to combinatorics induced by variability across their features. This leads to combinatorial explosion of the number of derivable products. Exhaustive testing in such a large space of products is infeasible. One possible option is to test SPLs by generating test cases that cover all possible T feature interactions (T-wise). T-wise dramatically reduces the number of test products while ensuring reasonable SPL coverage. However, automatic generation of test cases satisfying T-wise using SAT solvers raises two issues. The encoding of SPL models and T-wise criteria into a set of formulas acceptable by the solver and their satisfaction which fails when processed ``all-at-once''. We propose a scalable toolset using Alloy to automatically generate test cases satisfying T-wise from SPL models. We define strategies to split T-wise combinations into solvable subsets. We design and compute metrics to evaluate strategies on Aspect OPTIMA, a concrete transactional SPL.
---
paper_title: MoSo-PoLiTe: tool support for pairwise and model-based software product line testing

paper_content:

Testing Software Product Lines is a very challenging task and approaches like combinatorial testing and model-based testing are frequently used to reduce the effort of testing Software Product Lines and to reuse test artifacts. In this contribution we present a tool chain realizing our MoSo-PoLiTe concept combining combinatorial and model-based testing. Our tool chain contains a pairwise configuration selection component on the basis of a feature model. This component implements an heuristic finding a minimal subset of configurations covering 100% pairwise interaction. Additionally, our tool chain allows the model-based test case generation for each configuration within this generated subset. This tool chain is based on commercial tools since it was developed within industrial cooperations. A non-commercial implementation of pairwise configuration selection is available and an integration with an Open Source model-based testing tool is under development.
---
paper_title: A Classification and Survey of Analysis Strategies for Software Product Lines

paper_content:

Software-product-line engineering has gained considerable momentum in recent years, both in industry and in academia. A software product line is a family of software products that share a common set of features. Software product lines challenge traditional analysis techniques, such as type checking, model checking, and theorem proving, in their quest of ensuring correctness and reliability of software. Simply creating and analyzing all products of a product line is usually not feasible, due to the potentially exponential number of valid feature combinations. Recently, researchers began to develop analysis techniques that take the distinguishing properties of software product lines into account, for example, by checking feature-related code in isolation or by exploiting variability information during analysis. The emerging field of product-line analyses is both broad and diverse, so it is difficult for researchers and practitioners to understand their similarities and differences. We propose a classification of product-line analyses to enable systematic research and application. Based on our insights with classifying and comparing a corpus of 123 research articles, we develop a research agenda to guide future research on product-line analyses.
---
paper_title: Coevolution of variability models and related artifacts: a case study from the Linux kernel

paper_content:

Variability-aware systems are subject to the coevolution of variability models and related artifacts. Surprisingly, little knowledge exists to understand such coevolution in practice. This shortage is directly reflected in existing approaches and tools for variability management, as they fail to provide effective support for such a coevolution. To understand how variability models and related artifacts coevolve in a large and complex real-world variability-aware system, we inspect over 500 Linux kernel commits spanning almost four years of development. We collect a catalog of evolution patterns, capturing the coevolution of the Linux kernel variability model, Makefiles, and C source code. Further, we extract general findings to guide further research and tool development.
---
paper_title: Feature consistency in compile-time-configurable system software: facing the linux 10,000 feature problem

paper_content:

Much system software can be configured at compile time to tailor it with respect to a broad range of supported hardware architectures and application domains. A good example is the Linux kernel, which provides more than 10,000 configurable features, growing rapidly. From the maintenance point of view, compile-time configurability imposes big challenges. The configuration model (the selectable features and their constraints as presented to the user) and the configurability that is actually implemented in the code have to be kept in sync, which, if performed manually, is a tedious and error-prone task. In the case of Linux, this has led to numerous defects in the source code, many of which are actual bugs. We suggest an approach to automatically check for configurability-related implementation defects in large-scale configurable system software. The configurability is extracted from its various implementation sources and examined for inconsistencies, which manifest in seemingly conditional code that is in fact unconditional. We evaluate our approach with the latest version of Linux, for which our tool detects 1,776 configurability defects, which manifest as dead/superfluous source code and bugs. Our findings have led to numerous source-code improvements and bug fixes in Linux: 123 patches (49 merged) fix 364 defects, 147 of which have been confirmed by the corresponding Linux developers and 20 as fixing a new bug.
---
paper_title: Reducing combinatorics in testing product lines

paper_content:

A Software Product Line (SPL) is a family of programs where each program is defined by a unique combination of features. Testing or checking properties of an SPL is hard as it may require the examination of a combinatorial number of programs. In reality, however, features are often irrelevant for a given test - they augment, but do not change, existing behavior, making many feature combinations unnecessary as far as testing is concerned. In this paper we show how to reduce the amount of effort in testing an SPL. We represent an SPL in a form where conventional static program analysis techniques can be applied to find irrelevant features for a test. We use this information to reduce the combinatorial number of SPL programs to examine.
---
paper_title: Configuration coverage in the analysis of large-scale system software

paper_content:

System software, especially operating systems, tends to be highly configurable. Like every complex piece of software, a considerable amount of bugs in the implementation has to be expected. In order to improve the general code quality, tools for static analysis provide means to check for source code defects without having to run actual test cases on real hardware. Still, for proper type checking a specific configuration is required so that all header include paths are available and all types are properly resolved. In order to find as many bugs as possible, usually a "full configuration" is used for the check. However, mainly because of alternative blocks in form of #else-blocks, a single configuration is insufficient to achieve full coverage. In this paper, we present a metric for configuration coverage (CC) and explain the challenges for (properly) calculating it. Furthermore, we present an efficient approach for determining a sufficiently small set of configurations that achieve (nearly) full coverage and evaluate it on a recent Linux kernel version.
---
paper_title: PACOGEN: Automatic Generation of Pairwise Test Configurations from Feature Models

paper_content:

Feature models are commonly used to specify variability in software product lines. Several tools support feature models for variability management at different steps in the development process. However, tool support for test configuration generation is currently limited. This test generation task consists in systematically selecting a set of configurations that represent a relevant sample of the variability space and that can be used to test the product line. In this paper we propose \pw tool to analyze feature models and automatically generate a set of configurations that cover all pair wise interactions between features. \pw tool relies on constraint programming to generate configurations that satisfy all constraints imposed by the feature model and to minimize the set of the tests configurations. This work also proposes an extensive experiment, based on the state-of-the art SPLOT feature models repository, showing that \pw tool scales over variability spaces with millions of configurations and covers pair wise with less configurations than other available tools.
---
paper_title: Feature-Oriented Software Product Lines: Concepts and Implementation

paper_content:

While standardization has empowered the software industry to substantially scale software development and to provide affordable software to a broad market, it often does not address smaller market segments, nor the needs and wishes of individual customers. Software product lines reconcile mass production and standardization with mass customization in software engineering. Ideally, based on a set of reusable parts, a software manufacturer can generate a software product based on the requirements of its customer. The concept of features is central to achieving this level of automation, because features bridge the gap between the requirements the customer has and the functionality a product provides. Thus features are a central concept in all phases of product-line development. The authors take a developers viewpoint, focus on the development, maintenance, and implementation of product-line variability, and especially concentrate on automated product derivation based on a users feature selection. The book consists of three parts. Part I provides a general introduction to feature-oriented software product lines, describing the product-line approach and introducing the product-line development process with its two elements of domain and application engineering. The pivotal part II covers a wide variety of implementation techniques including design patterns, frameworks, components, feature-oriented programming, and aspect-oriented programming, as well as tool-based approaches including preprocessors, build systems, version-control systems, and virtual separation of concerns. Finally, part III is devoted to advanced topics related to feature-oriented product lines like refactoring, feature interaction, and analysis tools specific to product lines. In addition, an appendix lists various helpful tools for software product-line development, along with a description of how they relate to the topics covered in this book. To tie the book together, the authors use two running examples that are well documented in the product-line literature: data management for embedded systems, and variations of graph data structures. They start every chapter by explicitly stating the respective learning goals and finish it with a set of exercises; additional teaching material is also available online. All these features make the book ideally suited for teaching both for academic classes and for professionals interested in self-study.
---
paper_title: Testing Software Product Lines Using Incremental Test Generation

paper_content:

We present a novel specification-based approach for generating tests for products in a software product line. Given properties of features as first-order logic formulas, our approach uses SAT-based analysis to automatically generate test inputs for each product in a product line. To ensure soundness of generation, we introduce an automatic technique for mapping a formula that specifies a feature into a transformation that defines incremental refinement of test suites. Our experimental results using different data structure product lines show that incremental approach can provide an order of magnitude speed-up over conventional techniques.
---
paper_title: Types and Programming Languages

paper_content:

A type system is a syntactic method for automatically checking the absence of certain erroneous behaviors by classifying program phrases according to the kinds of values they compute. The study of type systems -- and of programming languages from a type-theoretic perspective -- has important applications in software engineering, language design, high-performance compilers, and security.This text provides a comprehensive introduction both to type systems in computer science and to the basic theory of programming languages. The approach is pragmatic and operational; each new concept is motivated by programming examples and the more theoretical sections are driven by the needs of implementations. Each chapter is accompanied by numerous exercises and solutions, as well as a running implementation, available via the Web. Dependencies between chapters are explicitly identified, allowing readers to choose a variety of paths through the material.The core topics include the untyped lambda-calculus, simple type systems, type reconstruction, universal and existential polymorphism, subtyping, bounded quantification, recursive types, kinds, and type operators. Extended case studies develop a variety of approaches to modeling the features of object-oriented languages.
---
paper_title: Modeling and Model Checking Software Product Lines

paper_content:

Software product line engineering combines the individual developments of systems to the development of a family of systems consisting of common and variable assets.In this paper we introduce the process algebra PL-CCS as a product line extension of CCS and show how to model the overall behavior of an entire family within PL-CCS. PL-CCS models incorporate behavioral variability and allow the derivation of individual systems in a systematic way due to a semantics given in terms of multi-valued modal Kripke structures. Furthermore, we introduce multi-valued modal μ-calculus as a property specification language for system families specified in PL-CCS and show how model checking techniques operate on such structures. In our setting the result of model checking is no longer a simple yesor noanswer but the set of systems of the product line that do meet the specified properties.
---
paper_title: Dead or Alive: finding zombie features in the Linux kernel

paper_content:

When an interference signals is detected by a base station, the base station issues a report to a switching apparatus. The switching apparatus checks self to see whether it is in a standby mode waiting for a frequency change completion report from another base station which is in the process of changing the control channel frequency. If the switching apparatus is satisfied that the station should be given a new control channel frequency, it issues a frequency change command to the requesting base station, and the base station receiving the command revises the current control channel frequency. In the meantime, all other requests from other stations are denied by the switching apparatus until the requesting base station has successfully completed the process of changing the control channel frequency. The base station acknowledges the completion of frequency change process by sending a frequency change completion report to the switching apparatus.
---
paper_title: Model checking JAVA programs using JAVA PathFinder

paper_content:

Abstract.This paper describes a translator called Java PathFinder (Jpf), which translates from Java to Promela, the modeling language of the Spin model checker. Jpf translates a given Java program into a Promela model, which then can be model checked using Spin. The Java program may contain assertions, which are translated into similar assertions in the Promela model. The Spin model checker will then look for deadlocks and violations of any stated assertions. Jpf generates a Promela model with the same state space characteristics as the Java program. Hence, the Java program must have a finite and tractable state space. This work should be seen in a broader attempt to make formal methods applicable within NASA’s areas such as space, aviation, and robotics. The work is a continuation of an effort to formally analyze, using Spin, a multi-threaded operating system for the Deep-Space 1 space craft, and of previous work in applying existing model checkers and theorem provers to real applications.
---
paper_title: Language-independent reference checking in software product lines

paper_content:

Feature-Oriented Software Development (FOSD) is a paradigm for the development of software product lines. A challenge in FOSD is to guarantee that all software systems of a software product line are correct. Recent work on type checking product lines can provide a guarantee of type correctness without generating all possible systems. We generalize previous results by abstracting from the specifics of particular programming languages. In a first attempt, we present a reference-checking algorithm that performs key tasks of product-line type checking independently of the target programming language. Experiments with two sample product lines written in Java and C are encouraging and give us confidence that this approach is promising.
---
paper_title: Language-Independent and Automated Software Composition: The FeatureHouse Experience

paper_content:

Superimposition is a composition technique that has been applied successfully in many areas of software development. Although superimposition is a general-purpose concept, it has been (re)invented and implemented individually for various kinds of software artifacts. We unify languages and tools that rely on superimposition by using the language-independent model of feature structure trees (FSTs). On the basis of the FST model, we propose a general approach to the composition of software artifacts written in different languages. Furthermore, we offer a supporting framework and tool chain, called FEATUREHOUSE. We use attribute grammars to automate the integration of additional languages. In particular, we have integrated Java, C#, C, Haskell, Alloy, and JavaCC. A substantial number of case studies demonstrate the practicality and scalability of our approach and reveal insights into the properties that a language must have in order to be ready for superimposition. We discuss perspectives of our approach and demonstrate how we extended FEATUREHOUSE with support for XML languages (in particular, XHTML, XMI/UML, and Ant) and alternative composition approaches (in particular, aspect weaving). Rounding off our previous work, we provide here a holistic view of the FEATUREHOUSE approach based on rich experience with numerous languages and case studies and reflections on several years of research.
---
paper_title: Access Control in Feature-Oriented Programming

paper_content:

In feature-oriented programming (FOP) a programmer decomposes a program in terms of features. Ideally, features are implemented modularly so that they can be developed in isolation. Access control mechanisms in the form of access or visibility modifiers are an important ingredient to attain feature modularity as they allow programmers to hide and expose internal details of a module's implementation. But developers of contemporary feature-oriented languages have not considered access control mechanisms so far. The absence of a well-defined access control model for FOP breaks encapsulation of feature code and leads to unexpected program behaviors and inadvertent type errors. We raise awareness of this problem, propose three feature-oriented access modifiers, and present a corresponding access modifier model. We offer an implementation of the model on the basis of a fully-fledged feature-oriented compiler. Finally, by analyzing ten feature-oriented programs, we explore the potential of feature-oriented modifiers in FOP.
---
paper_title: Proof Composition for Deductive Verification of Software Product Lines

paper_content:

Software product line engineering aims at the efficient development of program variants that share a common set of features and that differ in other features. Product lines can be efficiently developed using feature-oriented programming. Given a feature selection and the code artifacts for each feature, program variants can be generated automatically. The quality of the program variants can be rigorously ensured by formal verification. However, verification of all program variants can be expensive and include redundant verification tasks. We introduce a classification of existing software product line verification approaches and propose proof composition as a novel approach. Proof composition generates correctness proofs of each program variant based on partial proofs of each feature. We present a case study to evaluate proof composition and demonstrate that it reduces the effort for verification.
---
paper_title: Principles of Program Analysis

paper_content:

Program analysis utilizes static techniques for computing reliable information about the dynamic behavior of programs. Applications include compilers (for code improvement), software validation (for detecting errors) and transformations between data representation (for solving problems such as Y2K). This book is unique in providing an overview of the four major approaches to program analysis: data flow analysis, constraint-based analysis, abstract interpretation, and type and effect systems. The presentation illustrates the extensive similarities between the approaches, helping readers to choose the best one to utilize.
---
paper_title: Aspect Composition Applying the Design by Contract Principle

paper_content:

The composition of software units has been one of the main research topics in computer science. This paper addresses the composition validation problem evolving in this context. It focuses on the composition for a certain kind of units called aspects. Aspects are a new concept which is introduced by aspect-oriented programming aiming at a better separation of concerns. Cross-cutting code is captured and localised in these aspects. Some of the cross-cutting features which are expressed in aspects cannot be woven with other features into the same application since two features could be mutually exclusive. With a growing number of aspects, manual control of these dependencies becomes error-prone or even impossible. We show how assertions can be useful in this respect to support the software developer.
---
paper_title: Emergo: a tool for improving maintainability of preprocessor-based product lines

paper_content:

When maintaining a feature in preprocessor-based Software Product Lines (SPLs), developers are susceptible to introduce problems into other features. This is possible because features eventually share elements (like variables and methods) with the maintained one. This scenario might be even worse when hiding features by using techniques like Virtual Separation of Concerns (VSoC), since developers cannot see the feature dependencies and, consequently, they become unaware of them. Emergent Interfaces was proposed to minimize this problem by capturing feature dependencies and then providing information about other features that can be impacted during a maintenance task. In this paper, we present Emergo, a tool capable of computing emergent interfaces between the feature we are maintaining and the others. Emergo relies on feature-sensitive dataflow analyses in the sense it takes features and the SPL feature model into consideration when computing the interfaces.
---
paper_title: Abstract Features in Feature Modeling

paper_content:

A software product line is a set of program variants, typically generated from a common code base. Feature models describe variability in product lines by documenting features and their valid combinations. In product-line engineering, we need to reason about variability and program variants for many different tasks. For example, given a feature model, we might want to determine the number of all valid feature combinations or compute specific feature combinations for testing. However, we found that contemporary reasoning approaches can only reason about feature combinations, not about program variants, because they do not take abstract features into account. Abstract features are features used to structure a feature model that, however, do not have any impact at implementation level. Using existing feature-model reasoning mechanisms for program variants leads to incorrect results. Hence, although abstract features represent domain decisions that do not affect the generation of a program variant. We raise awareness of the problem of abstract features for different kinds of analyses on feature models. We argue that, in order to reason about program variants, abstract features should be made explicit in feature models. We present a technique based on propositional formulas that enables to reason about program variants rather than feature combinations. In practice, our technique can save effort that is caused by considering the same program variant multiple times, for example, in product-line testing.
---
paper_title: Delta-oriented programming of software product lines

paper_content:

Feature-oriented programming (FOP) implements software product lines by composition of feature modules. It relies on the principles of stepwise development. Feature modules are intended to refer to exactly one product feature and can only extend existing implementations. To provide more flexibility for implementing software product lines, we propose delta-oriented programming (DOP) as a novel programming language approach. A product line is represented by a core module and a set of delta modules. The core module provides an implementation of a valid product that can be developed with well-established single application engineering techniques. Delta modules specify changes to be applied to the core module to implement further products by adding, modifying and removing code. Application conditions attached to delta modules allow handling combinations of features explicitly. A product implementation for a particular feature configuration is generated by applying incrementally all delta modules with valid application condition to the core module. In order to evaluate the potential of DOP, we compare it to FOP, both conceptually and empirically.
---
paper_title: CPAchecker: A Tool for Configurable Software Verification

paper_content:

Configurable software verification is a recent concept for expressing different program analysis and model checking approaches in one single formalism. This paper presents CPAchecker, a tool and framework that aims at easy integration of new verification components. Every abstract domain, together with the corresponding operations, implements the interface of configurable program analysis (CPA). The main algorithm is configurable to perform a reachability analysis on arbitrary combinations of existing CPAs. In software verification, it takes a considerable amount of effort to convert a verification idea into actual experimental results -- we aim at accelerating this process. We hope that researchers find it convenient and productive to implement new verification ideas and algorithms using this flexible and easy-to-extend platform, and that it advances the field by making it easier to perform practical experiments. The tool is implemented in Java and runs as command-line tool or as Eclipse plug-in. CPAchecker implements CPAs for several abstract domains. We evaluate the efficiency of the current version of our tool on software-verification benchmarks from the literature, and compare it with other state-of-the-art model checkers. CPAchecker is an open-source toolkit and publicly available.
---
paper_title: Detection of feature interactions using feature-aware verification

paper_content:

A software product line is a set of software products that are distinguished in terms of features (i.e., end-user-visible units of behavior). Feature interactions-- situations in which the combination of features leads to emergent and possibly critical behavior --are a major source of failures in software product lines. We explore how feature-aware verification can improve the automatic detection of feature interactions in software product lines. Feature-aware verification uses product-line-verification techniques and supports the specification of feature properties along with the features in separate and composable units. It integrates the technique of variability encoding to verify a product line without generating and checking a possibly exponential number of feature combinations. We developed the tool suite SPLVERIFIER for feature-aware verification, which is based on standard model-checking technology. We applied it to an e-mail system that incorporates domain knowledge of AT&T. We found that feature interactions can be detected automatically based on specifications that have only local knowledge.
---
paper_title: Toward variability-aware testing

paper_content:

We investigate how to execute a unit test for all products of a product line without generating each product in isolation in a brute-force fashion. Learning from variability-aware analyses, we (a) design and implement a variability-aware interpreter and, alternatively, (b) reencode variability of the product line to simulate the test cases with a model checker. The interpreter internally reasons about variability, executing paths not affected by variability only once for the whole product line. The model checker achieves similar results by reusing powerful off-the-shelf analyses. We experimented with a prototype implementation for each strategy. We compare both strategies and discuss trade-offs and future directions. In the long run, we aim at finding an efficient testing approach that can be applied to entire product lines with millions of products.
---
paper_title: Model checking lots of systems: efficient verification of temporal properties in software product lines

paper_content:

In product line engineering, systems are developed in families and differences between family members are expressed in terms of features. Formal modelling and verification is an important issue in this context as more and more critical systems are developed this way. Since the number of systems in a family can be exponential in the number of features, two major challenges are the scalable modelling and the efficient verification of system behaviour. Currently, the few attempts to address them fail to recognise the importance of features as a unit of difference, or do not offer means for automated verification. In this paper, we tackle those challenges at a fundamental level. We first extend transition systems with features in order to describe the combined behaviour of an entire system family. We then define and implement a model checking technique that allows to verify such transition systems against temporal properties. An empirical evaluation shows substantial gains over classical approaches.
---
paper_title: A Classification and Survey of Analysis Strategies for Software Product Lines

paper_content:

Software-product-line engineering has gained considerable momentum in recent years, both in industry and in academia. A software product line is a family of software products that share a common set of features. Software product lines challenge traditional analysis techniques, such as type checking, model checking, and theorem proving, in their quest of ensuring correctness and reliability of software. Simply creating and analyzing all products of a product line is usually not feasible, due to the potentially exponential number of valid feature combinations. Recently, researchers began to develop analysis techniques that take the distinguishing properties of software product lines into account, for example, by checking feature-related code in isolation or by exploiting variability information during analysis. The emerging field of product-line analyses is both broad and diverse, so it is difficult for researchers and practitioners to understand their similarities and differences. We propose a classification of product-line analyses to enable systematic research and application. Based on our insights with classifying and comparing a corpus of 123 research articles, we develop a research agenda to guide future research on product-line analyses.
---
paper_title: Feature consistency in compile-time-configurable system software: facing the linux 10,000 feature problem

paper_content:

Much system software can be configured at compile time to tailor it with respect to a broad range of supported hardware architectures and application domains. A good example is the Linux kernel, which provides more than 10,000 configurable features, growing rapidly. From the maintenance point of view, compile-time configurability imposes big challenges. The configuration model (the selectable features and their constraints as presented to the user) and the configurability that is actually implemented in the code have to be kept in sync, which, if performed manually, is a tedious and error-prone task. In the case of Linux, this has led to numerous defects in the source code, many of which are actual bugs. We suggest an approach to automatically check for configurability-related implementation defects in large-scale configurable system software. The configurability is extracted from its various implementation sources and examined for inconsistencies, which manifest in seemingly conditional code that is in fact unconditional. We evaluate our approach with the latest version of Linux, for which our tool detects 1,776 configurability defects, which manifest as dead/superfluous source code and bugs. Our findings have led to numerous source-code improvements and bug fixes in Linux: 123 patches (49 merged) fix 364 defects, 147 of which have been confirmed by the corresponding Linux developers and 20 as fixing a new bug.
---
paper_title: Precise interprocedural dataflow analysis via graph reachability

paper_content:

The paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem. The only restrictions are that the set of dataflow facts must be a finite set, and that the dataflow functions must distribute over the confluence operator (either union or intersection). This class of probable problems includes—but is not limited to—the classical separable problems (also known as “gen/kill” or “bit-vector” problems)— e.g. , reaching definitions, available expressions, and live variables. In addition, the class of problems that our techniques handle includes many non-separable problems, including truly-live variables, copy constant propagation, and possibly-uninitialized variables. Results are reported from a preliminary experimental study of C programs (for the problem of finding possibly-uninitialized variables).
---
paper_title: FeatureIDE: An Extensible Framework for Feature-Oriented Software Development

paper_content:

FeatureIDE is an open-source framework for feature-oriented software development (FOSD) based on Eclipse. FOSD is a paradigm for the construction, customization, and synthesis of software systems. Code artifacts are mapped to features, and a customized software system can be generated given a selection of features. The set of software systems that can be generated is called a software product line (SPL). FeatureIDE supports several FOSD implementation techniques such as feature-oriented programming, aspect-oriented programming, delta-oriented programming, and preprocessors. All phases of FOSD are supported in FeatureIDE, namely domain analysis, requirements analysis, domain implementation, and software generation.
---
paper_title: Automatic detection of feature interactions using the Java modeling language: an experience report

paper_content:

In the development of complex software systems, interactions between different program features increase the design complexity. Feature-oriented software development focuses on the representation and compositions of features. The implementation of features often cuts across object-oriented module boundaries and hence comprises interactions. The manual detection and treatment of feature interactions requires a deep knowledge of the implementation details of the features involved. Our goal is to detect interactions automatically using specifications by means of design by contract and automated theorem proving. We provide a software tool that operates on programs in Java and the Java Modeling Language (JML). We discuss which kinds of feature interactions can be detected automatically with our tool and how to detect other kinds of interactions.
---
paper_title: Applying 'design by contract'

paper_content:

Methodological guidelines for object-oriented software construction that improve the reliability of the resulting software systems are presented. It is shown that the object-oriented techniques rely on the theory of design by contract, which underlies the design of the Eiffel analysis, design, and programming language and of the supporting libraries, from which a number of examples are drawn. The theory of contract design and the role of assertions in that theory are discussed. >
---
paper_title: Potential synergies of theorem proving and model checking for software product lines

paper_content:

The verification of software product lines is an active research area. A challenge is to efficiently verify similar products without the need to generate and verify them individually. As solution, researchers suggest family-based verification approaches, which either transform compile-time into runtime variability or make verification tools variability-aware. Existing approaches either focus on theorem proving, model checking, or other verification techniques. For the first time, we combine theorem proving and model checking to evaluate their synergies for product-line verification. We provide tool support by connecting five existing tools, namely FeatureIDE and FeatureHouse for product-line development, as well as KeY, JPF, and OpenJML for verification of Java programs. In an experiment, we found the synergy of improved effectiveness and efficiency, especially for product lines with few defects. Further, we experienced that model checking and theorem proving are more efficient and effective if the product line contains more defects.
---
paper_title: Virtual Separation of Concerns -- A Second Chance for Preprocessors

paper_content:

Conditional compilation with preprocessors like cpp is a simple but eective means to implement variability. By annotating code fragments with #ifdef and #endif directives, dierent program variants with or without these fragments can be created, which can be used (among others) to implement software product lines. Although, preprocessors are frequently used in practice, they are often criticized for their negative eect on code quality and maintainability. In contrast to modularized implementations, for example using components or aspects, preprocessors neglect separation of concerns, are prone to introduce subtle errors, can entirely obfuscate the source code, and limit reuse. Our aim is to rehabilitate the preprocessor by showing how simple tool support can address these problems and emulate some benets of modularized implementations. At the same time we emphasize unique benets of preprocessors, like simplicity and language independence. Although we do not have a denitive answer on how to implement variability, we want highlight opportunities to improve preprocessors and encourage research toward novel preprocessor-based approaches.
---
paper_title: SPL Conqueror: Toward optimization of non-functional properties in software product lines

paper_content:

A software product line (SPL) is a family of related programs of a domain. The programs of an SPL are distinguished in terms of features, which are end-user visible characteristics of programs. Based on a selection of features, stakeholders can derive tailor-made programs that satisfy functional requirements. Besides functional requirements, different application scenarios raise the need for optimizing non-functional properties of a variant. The diversity of application scenarios leads to heterogeneous optimization goals with respect to non-functional properties (e.g., performance vs. footprint vs. energy optimized variants). Hence, an SPL has to satisfy different and sometimes contradicting requirements regarding non-functional properties. Usually, the actually required non-functional properties are not known before product derivation and can vary for each application scenario and customer. Allowing stakeholders to derive optimized variants requires us to measure non-functional properties after the SPL is developed. Unfortunately, the high variability provided by SPLs complicates measurement and optimization of non-functional properties due to a large variant space. With SPL Conqueror, we provide a holistic approach to optimize non-functional properties in SPL engineering. We show how non-functional properties can be qualitatively specified and quantitatively measured in the context of SPLs. Furthermore, we discuss the variant-derivation process in SPL Conqueror that reduces the effort of computing an optimal variant. We demonstrate the applicability of our approach by means of nine case studies of a broad range of application domains (e.g., database management and operating systems). Moreover, we show that SPL Conqueror is implementation and language independent by using SPLs that are implemented with different mechanisms, such as conditional compilation and feature-oriented programming.
---
paper_title: Reducing Configurations to Monitor in a Software Product Line

paper_content:

A software product line is a family of programs where each program is defined by a unique combination of features. Product lines, like conventional programs, can be checked for safety properties through execution monitoring. However, because a product line induces a number of programs that is potentially exponential in the number of features, it would be very expensive to use existing monitoring techniques: one would have to apply those techniques to every single program. Doing so would also be wasteful because many programs can provably never violate the stated property. We introduce a monitoring technique dedicated to product lines that, given a safety property, statically determines the feature combinations that cannot possibly violate the property, thus reducing the number of programs to monitor. Experiments show that our technique is effective, particularly for safety properties that crosscut many optional features.
---
paper_title: ASADAL: a tool system for co-development of software and test environment based on product line engineering

paper_content:

Recently, product line software engineering (PLSE) is gaining popularity. To employ PLSE methods, many organizations are looking for a tool system that supports PLSE methods so that core assets and target software can be developed and tested in an effective and systematic way.ASADAL (A System Analysis and Design Aid tooL) supports the entire lifecycle of software development process based on a PLSE method called FORM (Feature-Oriented Reuse Method) [6]. It supports domain analysis, architecture and component design, code generation, and simulation-based verification and validation (V&V). Using the tool, users may co-develop target software and its test environment and verify software in a continuous and incremental way.
---
paper_title: Dead or Alive: finding zombie features in the Linux kernel

paper_content:

When an interference signals is detected by a base station, the base station issues a report to a switching apparatus. The switching apparatus checks self to see whether it is in a standby mode waiting for a frequency change completion report from another base station which is in the process of changing the control channel frequency. If the switching apparatus is satisfied that the station should be given a new control channel frequency, it issues a frequency change command to the requesting base station, and the base station receiving the command revises the current control channel frequency. In the meantime, all other requests from other stations are denied by the switching apparatus until the requesting base station has successfully completed the process of changing the control channel frequency. The base station acknowledges the completion of frequency change process by sending a frequency change completion report to the switching apparatus.
---
paper_title: Integration Testing of Software Product Lines Using Compositional Symbolic Execution

paper_content:

Software product lines are families of products defined by feature commonality and variability, with a well-managed asset base. Recent work in testing of software product lines has exploited similarities across development phases to reuse shared assets and reduce test effort. The use of feature dependence graphs has also been employed to reduce testing effort, but little work has focused on code level analysis of dataflow between features. In this paper we present a compositional symbolic execution technique that works in concert with a feature dependence graph to extract the set of possible interaction trees in a product family. It composes these to incrementally and symbolically analyze feature interactions. We experiment with two product lines and determine that our technique can reduce the overall number of interactions that must be considered during testing, and requires less time to run than a traditional symbolic execution technique.
---
paper_title: Language-independent reference checking in software product lines

paper_content:

Feature-Oriented Software Development (FOSD) is a paradigm for the development of software product lines. A challenge in FOSD is to guarantee that all software systems of a software product line are correct. Recent work on type checking product lines can provide a guarantee of type correctness without generating all possible systems. We generalize previous results by abstracting from the specifics of particular programming languages. In a first attempt, we present a reference-checking algorithm that performs key tasks of product-line type checking independently of the target programming language. Experiments with two sample product lines written in Java and C are encouraging and give us confidence that this approach is promising.
---
paper_title: Language-Independent and Automated Software Composition: The FeatureHouse Experience

paper_content:

Superimposition is a composition technique that has been applied successfully in many areas of software development. Although superimposition is a general-purpose concept, it has been (re)invented and implemented individually for various kinds of software artifacts. We unify languages and tools that rely on superimposition by using the language-independent model of feature structure trees (FSTs). On the basis of the FST model, we propose a general approach to the composition of software artifacts written in different languages. Furthermore, we offer a supporting framework and tool chain, called FEATUREHOUSE. We use attribute grammars to automate the integration of additional languages. In particular, we have integrated Java, C#, C, Haskell, Alloy, and JavaCC. A substantial number of case studies demonstrate the practicality and scalability of our approach and reveal insights into the properties that a language must have in order to be ready for superimposition. We discuss perspectives of our approach and demonstrate how we extended FEATUREHOUSE with support for XML languages (in particular, XHTML, XMI/UML, and Ant) and alternative composition approaches (in particular, aspect weaving). Rounding off our previous work, we provide here a holistic view of the FEATUREHOUSE approach based on rich experience with numerous languages and case studies and reflections on several years of research.
---
paper_title: Access Control in Feature-Oriented Programming

paper_content:

In feature-oriented programming (FOP) a programmer decomposes a program in terms of features. Ideally, features are implemented modularly so that they can be developed in isolation. Access control mechanisms in the form of access or visibility modifiers are an important ingredient to attain feature modularity as they allow programmers to hide and expose internal details of a module's implementation. But developers of contemporary feature-oriented languages have not considered access control mechanisms so far. The absence of a well-defined access control model for FOP breaks encapsulation of feature code and leads to unexpected program behaviors and inadvertent type errors. We raise awareness of this problem, propose three feature-oriented access modifiers, and present a corresponding access modifier model. We offer an implementation of the model on the basis of a fully-fledged feature-oriented compiler. Finally, by analyzing ten feature-oriented programs, we explore the potential of feature-oriented modifiers in FOP.
---
paper_title: Clafer tools for product line engineering

paper_content:

Clafer is a lightweight yet expressive language for structural modeling: feature modeling and configuration, class and object modeling, and metamodeling. Clafer Tools is an integrated set of tools based on Clafer. In this paper, we describe some product-line variability modeling scenarios of Clafer Tools from the viewpoints of product-line owner, product-line engineer, and product engineer.
---
paper_title: PLEDGE: a product line editor and test generation tool

paper_content:

Specific requirements of clients lead to the development of variants of the same software. These variants form a Software Product Line (SPL). Ideally, testing a SPL involves testing all the software products that can be configured through the combination of features. This, however, is intractable in practice since a) large SPLs can lead to millions of possible software variants and b) the testing process is usually limited by budget and time constraints. To overcome this problem, this paper introduces PLEDGE, an open source tool that selects and prioritizes the product configurations maximizing the feature interactions covered. The uniqueness of PLEDGE is that it bypasses the computation of the feature interactions, allowing to scale to large SPLs.
---
paper_title: Aspect Composition Applying the Design by Contract Principle

paper_content:

The composition of software units has been one of the main research topics in computer science. This paper addresses the composition validation problem evolving in this context. It focuses on the composition for a certain kind of units called aspects. Aspects are a new concept which is introduced by aspect-oriented programming aiming at a better separation of concerns. Cross-cutting code is captured and localised in these aspects. Some of the cross-cutting features which are expressed in aspects cannot be woven with other features into the same application since two features could be mutually exclusive. With a growing number of aspects, manual control of these dependencies becomes error-prone or even impossible. We show how assertions can be useful in this respect to support the software developer.
---
paper_title: Emergo: a tool for improving maintainability of preprocessor-based product lines

paper_content:

When maintaining a feature in preprocessor-based Software Product Lines (SPLs), developers are susceptible to introduce problems into other features. This is possible because features eventually share elements (like variables and methods) with the maintained one. This scenario might be even worse when hiding features by using techniques like Virtual Separation of Concerns (VSoC), since developers cannot see the feature dependencies and, consequently, they become unaware of them. Emergent Interfaces was proposed to minimize this problem by capturing feature dependencies and then providing information about other features that can be impacted during a maintenance task. In this paper, we present Emergo, a tool capable of computing emergent interfaces between the feature we are maintaining and the others. Emergo relies on feature-sensitive dataflow analyses in the sense it takes features and the SPL feature model into consideration when computing the interfaces.
---
paper_title: Variability-aware parsing in the presence of lexical macros and conditional compilation

paper_content:

In many projects, lexical preprocessors are used to manage different variants of the project (using conditional compilation) and to define compile-time code transformations (using macros). Unfortunately, while being a simple way to implement variability, conditional compilation and lexical macros hinder automatic analysis, even though such analysis is urgently needed to combat variability-induced complexity. To analyze code with its variability, we need to parse it without preprocessing it. However, current parsing solutions use unsound heuristics, support only a subset of the language, or suffer from exponential explosion. As part of the TypeChef project, we contribute a novel variability-aware parser that can parse almost all unpreprocessed code without heuristics in practicable time. Beyond the obvious task of detecting syntax errors, our parser paves the road for further analysis, such as variability-aware type checking. We implement variability-aware parsers for Java and GNU C and demonstrate practicability by parsing the product line MobileMedia and the entire X86 architecture of the Linux kernel with 6065 variable features.
---
paper_title: Delta-oriented programming of software product lines

paper_content:

Feature-oriented programming (FOP) implements software product lines by composition of feature modules. It relies on the principles of stepwise development. Feature modules are intended to refer to exactly one product feature and can only extend existing implementations. To provide more flexibility for implementing software product lines, we propose delta-oriented programming (DOP) as a novel programming language approach. A product line is represented by a core module and a set of delta modules. The core module provides an implementation of a valid product that can be developed with well-established single application engineering techniques. Delta modules specify changes to be applied to the core module to implement further products by adding, modifying and removing code. Application conditions attached to delta modules allow handling combinations of features explicitly. A product implementation for a particular feature configuration is generated by applying incrementally all delta modules with valid application condition to the core module. In order to evaluate the potential of DOP, we compare it to FOP, both conceptually and empirically.
---
paper_title: Exploring variability-aware execution for testing plugin-based web applications

paper_content:

In plugin-based systems, plugin conflicts may occur when two or more plugins interfere with one another, changing their expected behaviors. It is highly challenging to detect plugin conflicts due to the exponential explosion of the combinations of plugins (i.e., configurations). In this paper, we address the challenge of executing a test case over many configurations. Leveraging the fact that many executions of a test are similar, our variability-aware execution runs common code once. Only when encountering values that are different depending on specific configurations will the execution split to run for each of them. To evaluate the scalability of variability-aware execution on a large real-world setting, we built a prototype PHP interpreter called Varex and ran it on the popular WordPress blogging Web application. The results show that while plugin interactions exist, there is a significant amount of sharing that allows variability-aware execution to scale to 2^50 configurations within seven minutes of running time. During our study, with Varex, we were able to detect two plugin conflicts: one was recently reported on WordPress forum and another one was not previously discovered.
---
paper_title: Incremental Test Generation for Software Product Lines

paper_content:

Recent advances in mechanical techniques for systematic testing have increased our ability to automatically find subtle bugs, and hence, to deploy more dependable software. This paper builds on one such systematic technique, scope-bounded testing, to develop a novel specification-based approach for efficiently generating tests for products in a software product line. Given properties of features as first-order logic formulas in Alloy, our approach uses SAT-based analysis to automatically generate test inputs for each product in a product line. To ensure soundness of generation, we introduce an automatic technique for mapping a formula that specifies a feature into a transformation that defines incremental refinement of test suites. Our experimental results using different data structure product lines show that an incremental approach can provide an order of magnitude speedup over conventional techniques. We also present a further optimization using dedicated integer constraint solvers for feature properties that introduce integer constraints, and show how to use a combination of solvers in tandem for solving Alloy formulas.
---
paper_title: A product line based aspect-oriented generative unit testing approach to building quality components

paper_content:

The quality of component-based systems highly depends on how effectively testing is carried out. To achieve the maximal testing effectiveness, this paper presents a product line based aspect oriented approach to unit testing. The aspect product line facilitates the automatic creation of aspect test cases that deal with specific quality requirements. An expandable repository of reusable aspect test cases has been developed. A prototype tool is built to verify and lever up the approach.
---
paper_title: Avoiding redundant testing in application engineering

paper_content:

Many software product line testing techniques have been presented in the literature. The majority of those techniques address how to define reusable test assets (such as test models or test scenarios) in domain engineering and how to exploit those assets during application engineering. In addition to test case reuse however, the execution of test cases constitutes one important activity during application testing. Without a systematic support for the test execution in application engineering, while considering the specifics of product lines, product line artifacts might be tested redundantly. Redundant testing in application engineering, however, can lead to an increased testing effort without increasing the chance of uncovering failures. In this paper, we propose the model-based ScenTED-DF technique to avoid redundant testing in application engineering. Our technique builds on data flow-based testing techniques for single systems and adapts and extends those techniques to consider product line variability. The paper sketches the prototypical implementation of our technique to show its general feasibility and automation potential, and it describes the results of experiments using an academic product line to demonstrate that ScenTED-DF is capable of avoiding redundant tests in application engineering.
---
paper_title: Detection of feature interactions using feature-aware verification

paper_content:

A software product line is a set of software products that are distinguished in terms of features (i.e., end-user-visible units of behavior). Feature interactions-- situations in which the combination of features leads to emergent and possibly critical behavior --are a major source of failures in software product lines. We explore how feature-aware verification can improve the automatic detection of feature interactions in software product lines. Feature-aware verification uses product-line-verification techniques and supports the specification of feature properties along with the features in separate and composable units. It integrates the technique of variability encoding to verify a product line without generating and checking a possibly exponential number of feature combinations. We developed the tool suite SPLVERIFIER for feature-aware verification, which is based on standard model-checking technology. We applied it to an e-mail system that incorporates domain knowledge of AT&T. We found that feature interactions can be detected automatically based on specifications that have only local knowledge.
---
paper_title: Toward variability-aware testing

paper_content:

We investigate how to execute a unit test for all products of a product line without generating each product in isolation in a brute-force fashion. Learning from variability-aware analyses, we (a) design and implement a variability-aware interpreter and, alternatively, (b) reencode variability of the product line to simulate the test cases with a model checker. The interpreter internally reasons about variability, executing paths not affected by variability only once for the whole product line. The model checker achieves similar results by reusing powerful off-the-shelf analyses. We experimented with a prototype implementation for each strategy. We compare both strategies and discuss trade-offs and future directions. In the long run, we aim at finding an efficient testing approach that can be applied to entire product lines with millions of products.
---
paper_title: Family-based performance measurement

paper_content:

Most contemporary programs are customizable. They provide many features that give rise to millions of program variants. Determining which feature selection yields an optimal performance is challenging, because of the exponential number of variants. Predicting the performance of a variant based on previous measurements proved successful, but induces a trade-off between the measurement effort and prediction accuracy. We propose the alternative approach of family-based performance measurement, to reduce the number of measurements required for identifying feature interactions and for obtaining accurate predictions. The key idea is to create a variant simulator (by translating compile-time variability to run-time variability) that can simulate the behavior of all program variants. We use it to measure performance of individual methods, trace methods to features, and infer feature interactions based on the call graph. We evaluate our approach by means of five feature-oriented programs. On average, we achieve accuracy of 98%, with only a single measurement per customizable program. Observations show that our approach opens avenues of future research in different domains, such an feature-interaction detection and testing.
---
paper_title: Automated and Scalable T-wise Test Case Generation Strategies for Software Product Lines

paper_content:

Software Product Lines (SPL) are difficult to validate due to combinatorics induced by variability across their features. This leads to combinatorial explosion of the number of derivable products. Exhaustive testing in such a large space of products is infeasible. One possible option is to test SPLs by generating test cases that cover all possible T feature interactions (T-wise). T-wise dramatically reduces the number of test products while ensuring reasonable SPL coverage. However, automatic generation of test cases satisfying T-wise using SAT solvers raises two issues. The encoding of SPL models and T-wise criteria into a set of formulas acceptable by the solver and their satisfaction which fails when processed ``all-at-once''. We propose a scalable toolset using Alloy to automatically generate test cases satisfying T-wise from SPL models. We define strategies to split T-wise combinations into solvable subsets. We design and compute metrics to evaluate strategies on Aspect OPTIMA, a concrete transactional SPL.
---
paper_title: Feature consistency in compile-time-configurable system software: facing the linux 10,000 feature problem

paper_content:

Much system software can be configured at compile time to tailor it with respect to a broad range of supported hardware architectures and application domains. A good example is the Linux kernel, which provides more than 10,000 configurable features, growing rapidly. From the maintenance point of view, compile-time configurability imposes big challenges. The configuration model (the selectable features and their constraints as presented to the user) and the configurability that is actually implemented in the code have to be kept in sync, which, if performed manually, is a tedious and error-prone task. In the case of Linux, this has led to numerous defects in the source code, many of which are actual bugs. We suggest an approach to automatically check for configurability-related implementation defects in large-scale configurable system software. The configurability is extracted from its various implementation sources and examined for inconsistencies, which manifest in seemingly conditional code that is in fact unconditional. We evaluate our approach with the latest version of Linux, for which our tool detects 1,776 configurability defects, which manifest as dead/superfluous source code and bugs. Our findings have led to numerous source-code improvements and bug fixes in Linux: 123 patches (49 merged) fix 364 defects, 147 of which have been confirmed by the corresponding Linux developers and 20 as fixing a new bug.
---
paper_title: Reducing combinatorics in testing product lines

paper_content:

A Software Product Line (SPL) is a family of programs where each program is defined by a unique combination of features. Testing or checking properties of an SPL is hard as it may require the examination of a combinatorial number of programs. In reality, however, features are often irrelevant for a given test - they augment, but do not change, existing behavior, making many feature combinations unnecessary as far as testing is concerned. In this paper we show how to reduce the amount of effort in testing an SPL. We represent an SPL in a form where conventional static program analysis techniques can be applied to find irrelevant features for a test. We use this information to reduce the combinatorial number of SPL programs to examine.
---
paper_title: FeatureIDE: An Extensible Framework for Feature-Oriented Software Development

paper_content:

FeatureIDE is an open-source framework for feature-oriented software development (FOSD) based on Eclipse. FOSD is a paradigm for the construction, customization, and synthesis of software systems. Code artifacts are mapped to features, and a customized software system can be generated given a selection of features. The set of software systems that can be generated is called a software product line (SPL). FeatureIDE supports several FOSD implementation techniques such as feature-oriented programming, aspect-oriented programming, delta-oriented programming, and preprocessors. All phases of FOSD are supported in FeatureIDE, namely domain analysis, requirements analysis, domain implementation, and software generation.
---
paper_title: A Case Study Implementing Features Using AspectJ

paper_content:

Software product lines aim to create highly configurable programs from a set of features. Common belief and recent studies suggest that aspects are well-suited for implementing features. We evaluate the suitability of AspectJ with respect to this task by a case study that refactors the embedded database system Berkeley DB into 38 features. Contrary to our initial expectations, the results were not encouraging. As the number of aspects in a feature grows, there is a noticeable decrease in code readability and maintainability. Most of the unique and powerful features of AspectJ were not needed. We document where AspectJ is unsuitable for implementing features of refactored legacy applications and explain why.
---
paper_title: Analyzing the discipline of preprocessor annotations in 30 million lines of C code

paper_content:

The C preprocessor cpp is a widely used tool for implementing variable software. It enables programmers to express variable code (which may even crosscut the entire implementation) with conditional compilation. The C preprocessor relies on simple text processing and is independent of the host language (C, C++, Java, and so on). Language-independent text processing is powerful and expressive - programmers can make all kinds of annotations in the form of #ifdefs - but can render unpreprocessed code difficult to process automatically by tools, such as refactoring, concern management, and variability-aware type checking. We distinguish between disciplined annotations, which align with the underlying source-code structure, and undisciplined annotations, which do not align with the structure and hence complicate tool development. This distinction raises the question of how frequently programmers use undisciplined annotations and whether it is feasible to change them to disciplined annotations to simplify tool development and to enable programmers to use a wide variety of tools in the first place. By means of an analysis of 40 medium-sized to large-sized C programs, we show empirically that programmers use cpp mostly in a disciplined way: about 84% of all annotations respect the underlying source-code structure. Furthermore, we analyze the remaining undisciplined annotations, identify patterns, and discuss how to transform them into a disciplined form.
---
paper_title: Automatic detection of feature interactions using the Java modeling language: an experience report

paper_content:

In the development of complex software systems, interactions between different program features increase the design complexity. Feature-oriented software development focuses on the representation and compositions of features. The implementation of features often cuts across object-oriented module boundaries and hence comprises interactions. The manual detection and treatment of feature interactions requires a deep knowledge of the implementation details of the features involved. Our goal is to detect interactions automatically using specifications by means of design by contract and automated theorem proving. We provide a software tool that operates on programs in Java and the Java Modeling Language (JML). We discuss which kinds of feature interactions can be detected automatically with our tool and how to detect other kinds of interactions.
---
paper_title: Testing Software Product Lines Using Incremental Test Generation

paper_content:

We present a novel specification-based approach for generating tests for products in a software product line. Given properties of features as first-order logic formulas, our approach uses SAT-based analysis to automatically generate test inputs for each product in a product line. To ensure soundness of generation, we introduce an automatic technique for mapping a formula that specifies a feature into a transformation that defines incremental refinement of test suites. Our experimental results using different data structure product lines show that incremental approach can provide an order of magnitude speed-up over conventional techniques.
---
paper_title: Virtual Separation of Concerns -- A Second Chance for Preprocessors

paper_content:

Conditional compilation with preprocessors like cpp is a simple but eective means to implement variability. By annotating code fragments with #ifdef and #endif directives, dierent program variants with or without these fragments can be created, which can be used (among others) to implement software product lines. Although, preprocessors are frequently used in practice, they are often criticized for their negative eect on code quality and maintainability. In contrast to modularized implementations, for example using components or aspects, preprocessors neglect separation of concerns, are prone to introduce subtle errors, can entirely obfuscate the source code, and limit reuse. Our aim is to rehabilitate the preprocessor by showing how simple tool support can address these problems and emulate some benets of modularized implementations. At the same time we emphasize unique benets of preprocessors, like simplicity and language independence. Although we do not have a denitive answer on how to implement variability, we want highlight opportunities to improve preprocessors and encourage research toward novel preprocessor-based approaches.
---
paper_title: Language-Independent and Automated Software Composition: The FeatureHouse Experience

paper_content:

Superimposition is a composition technique that has been applied successfully in many areas of software development. Although superimposition is a general-purpose concept, it has been (re)invented and implemented individually for various kinds of software artifacts. We unify languages and tools that rely on superimposition by using the language-independent model of feature structure trees (FSTs). On the basis of the FST model, we propose a general approach to the composition of software artifacts written in different languages. Furthermore, we offer a supporting framework and tool chain, called FEATUREHOUSE. We use attribute grammars to automate the integration of additional languages. In particular, we have integrated Java, C#, C, Haskell, Alloy, and JavaCC. A substantial number of case studies demonstrate the practicality and scalability of our approach and reveal insights into the properties that a language must have in order to be ready for superimposition. We discuss perspectives of our approach and demonstrate how we extended FEATUREHOUSE with support for XML languages (in particular, XHTML, XMI/UML, and Ant) and alternative composition approaches (in particular, aspect weaving). Rounding off our previous work, we provide here a holistic view of the FEATUREHOUSE approach based on rich experience with numerous languages and case studies and reflections on several years of research.
---
paper_title: Access Control in Feature-Oriented Programming

paper_content:

In feature-oriented programming (FOP) a programmer decomposes a program in terms of features. Ideally, features are implemented modularly so that they can be developed in isolation. Access control mechanisms in the form of access or visibility modifiers are an important ingredient to attain feature modularity as they allow programmers to hide and expose internal details of a module's implementation. But developers of contemporary feature-oriented languages have not considered access control mechanisms so far. The absence of a well-defined access control model for FOP breaks encapsulation of feature code and leads to unexpected program behaviors and inadvertent type errors. We raise awareness of this problem, propose three feature-oriented access modifiers, and present a corresponding access modifier model. We offer an implementation of the model on the basis of a fully-fledged feature-oriented compiler. Finally, by analyzing ten feature-oriented programs, we explore the potential of feature-oriented modifiers in FOP.
---
paper_title: A Classification and Survey of Analysis Strategies for Software Product Lines

paper_content:

Software-product-line engineering has gained considerable momentum in recent years, both in industry and in academia. A software product line is a family of software products that share a common set of features. Software product lines challenge traditional analysis techniques, such as type checking, model checking, and theorem proving, in their quest of ensuring correctness and reliability of software. Simply creating and analyzing all products of a product line is usually not feasible, due to the potentially exponential number of valid feature combinations. Recently, researchers began to develop analysis techniques that take the distinguishing properties of software product lines into account, for example, by checking feature-related code in isolation or by exploiting variability information during analysis. The emerging field of product-line analyses is both broad and diverse, so it is difficult for researchers and practitioners to understand their similarities and differences. We propose a classification of product-line analyses to enable systematic research and application. Based on our insights with classifying and comparing a corpus of 123 research articles, we develop a research agenda to guide future research on product-line analyses.
---
paper_title: FeatureIDE: An Extensible Framework for Feature-Oriented Software Development

paper_content:

FeatureIDE is an open-source framework for feature-oriented software development (FOSD) based on Eclipse. FOSD is a paradigm for the construction, customization, and synthesis of software systems. Code artifacts are mapped to features, and a customized software system can be generated given a selection of features. The set of software systems that can be generated is called a software product line (SPL). FeatureIDE supports several FOSD implementation techniques such as feature-oriented programming, aspect-oriented programming, delta-oriented programming, and preprocessors. All phases of FOSD are supported in FeatureIDE, namely domain analysis, requirements analysis, domain implementation, and software generation.
---
paper_title: SPL Conqueror: Toward optimization of non-functional properties in software product lines

paper_content:

A software product line (SPL) is a family of related programs of a domain. The programs of an SPL are distinguished in terms of features, which are end-user visible characteristics of programs. Based on a selection of features, stakeholders can derive tailor-made programs that satisfy functional requirements. Besides functional requirements, different application scenarios raise the need for optimizing non-functional properties of a variant. The diversity of application scenarios leads to heterogeneous optimization goals with respect to non-functional properties (e.g., performance vs. footprint vs. energy optimized variants). Hence, an SPL has to satisfy different and sometimes contradicting requirements regarding non-functional properties. Usually, the actually required non-functional properties are not known before product derivation and can vary for each application scenario and customer. Allowing stakeholders to derive optimized variants requires us to measure non-functional properties after the SPL is developed. Unfortunately, the high variability provided by SPLs complicates measurement and optimization of non-functional properties due to a large variant space. With SPL Conqueror, we provide a holistic approach to optimize non-functional properties in SPL engineering. We show how non-functional properties can be qualitatively specified and quantitatively measured in the context of SPLs. Furthermore, we discuss the variant-derivation process in SPL Conqueror that reduces the effort of computing an optimal variant. We demonstrate the applicability of our approach by means of nine case studies of a broad range of application domains (e.g., database management and operating systems). Moreover, we show that SPL Conqueror is implementation and language independent by using SPLs that are implemented with different mechanisms, such as conditional compilation and feature-oriented programming.
---
paper_title: Reducing Configurations to Monitor in a Software Product Line

paper_content:

A software product line is a family of programs where each program is defined by a unique combination of features. Product lines, like conventional programs, can be checked for safety properties through execution monitoring. However, because a product line induces a number of programs that is potentially exponential in the number of features, it would be very expensive to use existing monitoring techniques: one would have to apply those techniques to every single program. Doing so would also be wasteful because many programs can provably never violate the stated property. We introduce a monitoring technique dedicated to product lines that, given a safety property, statically determines the feature combinations that cannot possibly violate the property, thus reducing the number of programs to monitor. Experiments show that our technique is effective, particularly for safety properties that crosscut many optional features.
---
paper_title: ASADAL: a tool system for co-development of software and test environment based on product line engineering

paper_content:

Recently, product line software engineering (PLSE) is gaining popularity. To employ PLSE methods, many organizations are looking for a tool system that supports PLSE methods so that core assets and target software can be developed and tested in an effective and systematic way.ASADAL (A System Analysis and Design Aid tooL) supports the entire lifecycle of software development process based on a PLSE method called FORM (Feature-Oriented Reuse Method) [6]. It supports domain analysis, architecture and component design, code generation, and simulation-based verification and validation (V&V). Using the tool, users may co-develop target software and its test environment and verify software in a continuous and incremental way.
---
paper_title: Dead or Alive: finding zombie features in the Linux kernel

paper_content:

When an interference signals is detected by a base station, the base station issues a report to a switching apparatus. The switching apparatus checks self to see whether it is in a standby mode waiting for a frequency change completion report from another base station which is in the process of changing the control channel frequency. If the switching apparatus is satisfied that the station should be given a new control channel frequency, it issues a frequency change command to the requesting base station, and the base station receiving the command revises the current control channel frequency. In the meantime, all other requests from other stations are denied by the switching apparatus until the requesting base station has successfully completed the process of changing the control channel frequency. The base station acknowledges the completion of frequency change process by sending a frequency change completion report to the switching apparatus.
---
paper_title: Integration Testing of Software Product Lines Using Compositional Symbolic Execution

paper_content:

Software product lines are families of products defined by feature commonality and variability, with a well-managed asset base. Recent work in testing of software product lines has exploited similarities across development phases to reuse shared assets and reduce test effort. The use of feature dependence graphs has also been employed to reduce testing effort, but little work has focused on code level analysis of dataflow between features. In this paper we present a compositional symbolic execution technique that works in concert with a feature dependence graph to extract the set of possible interaction trees in a product family. It composes these to incrementally and symbolically analyze feature interactions. We experiment with two product lines and determine that our technique can reduce the overall number of interactions that must be considered during testing, and requires less time to run than a traditional symbolic execution technique.
---
paper_title: Language-independent reference checking in software product lines

paper_content:

Feature-Oriented Software Development (FOSD) is a paradigm for the development of software product lines. A challenge in FOSD is to guarantee that all software systems of a software product line are correct. Recent work on type checking product lines can provide a guarantee of type correctness without generating all possible systems. We generalize previous results by abstracting from the specifics of particular programming languages. In a first attempt, we present a reference-checking algorithm that performs key tasks of product-line type checking independently of the target programming language. Experiments with two sample product lines written in Java and C are encouraging and give us confidence that this approach is promising.
---
paper_title: Access Control in Feature-Oriented Programming

paper_content:

In feature-oriented programming (FOP) a programmer decomposes a program in terms of features. Ideally, features are implemented modularly so that they can be developed in isolation. Access control mechanisms in the form of access or visibility modifiers are an important ingredient to attain feature modularity as they allow programmers to hide and expose internal details of a module's implementation. But developers of contemporary feature-oriented languages have not considered access control mechanisms so far. The absence of a well-defined access control model for FOP breaks encapsulation of feature code and leads to unexpected program behaviors and inadvertent type errors. We raise awareness of this problem, propose three feature-oriented access modifiers, and present a corresponding access modifier model. We offer an implementation of the model on the basis of a fully-fledged feature-oriented compiler. Finally, by analyzing ten feature-oriented programs, we explore the potential of feature-oriented modifiers in FOP.
---
paper_title: Clafer tools for product line engineering

paper_content:

Clafer is a lightweight yet expressive language for structural modeling: feature modeling and configuration, class and object modeling, and metamodeling. Clafer Tools is an integrated set of tools based on Clafer. In this paper, we describe some product-line variability modeling scenarios of Clafer Tools from the viewpoints of product-line owner, product-line engineer, and product engineer.
---
paper_title: PLEDGE: a product line editor and test generation tool

paper_content:

Specific requirements of clients lead to the development of variants of the same software. These variants form a Software Product Line (SPL). Ideally, testing a SPL involves testing all the software products that can be configured through the combination of features. This, however, is intractable in practice since a) large SPLs can lead to millions of possible software variants and b) the testing process is usually limited by budget and time constraints. To overcome this problem, this paper introduces PLEDGE, an open source tool that selects and prioritizes the product configurations maximizing the feature interactions covered. The uniqueness of PLEDGE is that it bypasses the computation of the feature interactions, allowing to scale to large SPLs.
---
paper_title: Aspect Composition Applying the Design by Contract Principle

paper_content:

The composition of software units has been one of the main research topics in computer science. This paper addresses the composition validation problem evolving in this context. It focuses on the composition for a certain kind of units called aspects. Aspects are a new concept which is introduced by aspect-oriented programming aiming at a better separation of concerns. Cross-cutting code is captured and localised in these aspects. Some of the cross-cutting features which are expressed in aspects cannot be woven with other features into the same application since two features could be mutually exclusive. With a growing number of aspects, manual control of these dependencies becomes error-prone or even impossible. We show how assertions can be useful in this respect to support the software developer.
---
paper_title: Emergo: a tool for improving maintainability of preprocessor-based product lines

paper_content:

When maintaining a feature in preprocessor-based Software Product Lines (SPLs), developers are susceptible to introduce problems into other features. This is possible because features eventually share elements (like variables and methods) with the maintained one. This scenario might be even worse when hiding features by using techniques like Virtual Separation of Concerns (VSoC), since developers cannot see the feature dependencies and, consequently, they become unaware of them. Emergent Interfaces was proposed to minimize this problem by capturing feature dependencies and then providing information about other features that can be impacted during a maintenance task. In this paper, we present Emergo, a tool capable of computing emergent interfaces between the feature we are maintaining and the others. Emergo relies on feature-sensitive dataflow analyses in the sense it takes features and the SPL feature model into consideration when computing the interfaces.
---
paper_title: Variability-aware parsing in the presence of lexical macros and conditional compilation

paper_content:

In many projects, lexical preprocessors are used to manage different variants of the project (using conditional compilation) and to define compile-time code transformations (using macros). Unfortunately, while being a simple way to implement variability, conditional compilation and lexical macros hinder automatic analysis, even though such analysis is urgently needed to combat variability-induced complexity. To analyze code with its variability, we need to parse it without preprocessing it. However, current parsing solutions use unsound heuristics, support only a subset of the language, or suffer from exponential explosion. As part of the TypeChef project, we contribute a novel variability-aware parser that can parse almost all unpreprocessed code without heuristics in practicable time. Beyond the obvious task of detecting syntax errors, our parser paves the road for further analysis, such as variability-aware type checking. We implement variability-aware parsers for Java and GNU C and demonstrate practicability by parsing the product line MobileMedia and the entire X86 architecture of the Linux kernel with 6065 variable features.
---
paper_title: Delta-oriented programming of software product lines

paper_content:

Feature-oriented programming (FOP) implements software product lines by composition of feature modules. It relies on the principles of stepwise development. Feature modules are intended to refer to exactly one product feature and can only extend existing implementations. To provide more flexibility for implementing software product lines, we propose delta-oriented programming (DOP) as a novel programming language approach. A product line is represented by a core module and a set of delta modules. The core module provides an implementation of a valid product that can be developed with well-established single application engineering techniques. Delta modules specify changes to be applied to the core module to implement further products by adding, modifying and removing code. Application conditions attached to delta modules allow handling combinations of features explicitly. A product implementation for a particular feature configuration is generated by applying incrementally all delta modules with valid application condition to the core module. In order to evaluate the potential of DOP, we compare it to FOP, both conceptually and empirically.
---
paper_title: Exploring variability-aware execution for testing plugin-based web applications

paper_content:

In plugin-based systems, plugin conflicts may occur when two or more plugins interfere with one another, changing their expected behaviors. It is highly challenging to detect plugin conflicts due to the exponential explosion of the combinations of plugins (i.e., configurations). In this paper, we address the challenge of executing a test case over many configurations. Leveraging the fact that many executions of a test are similar, our variability-aware execution runs common code once. Only when encountering values that are different depending on specific configurations will the execution split to run for each of them. To evaluate the scalability of variability-aware execution on a large real-world setting, we built a prototype PHP interpreter called Varex and ran it on the popular WordPress blogging Web application. The results show that while plugin interactions exist, there is a significant amount of sharing that allows variability-aware execution to scale to 2^50 configurations within seven minutes of running time. During our study, with Varex, we were able to detect two plugin conflicts: one was recently reported on WordPress forum and another one was not previously discovered.
---
paper_title: Incremental Test Generation for Software Product Lines

paper_content:

Recent advances in mechanical techniques for systematic testing have increased our ability to automatically find subtle bugs, and hence, to deploy more dependable software. This paper builds on one such systematic technique, scope-bounded testing, to develop a novel specification-based approach for efficiently generating tests for products in a software product line. Given properties of features as first-order logic formulas in Alloy, our approach uses SAT-based analysis to automatically generate test inputs for each product in a product line. To ensure soundness of generation, we introduce an automatic technique for mapping a formula that specifies a feature into a transformation that defines incremental refinement of test suites. Our experimental results using different data structure product lines show that an incremental approach can provide an order of magnitude speedup over conventional techniques. We also present a further optimization using dedicated integer constraint solvers for feature properties that introduce integer constraints, and show how to use a combination of solvers in tandem for solving Alloy formulas.
---
paper_title: A product line based aspect-oriented generative unit testing approach to building quality components

paper_content:

The quality of component-based systems highly depends on how effectively testing is carried out. To achieve the maximal testing effectiveness, this paper presents a product line based aspect oriented approach to unit testing. The aspect product line facilitates the automatic creation of aspect test cases that deal with specific quality requirements. An expandable repository of reusable aspect test cases has been developed. A prototype tool is built to verify and lever up the approach.
---
paper_title: Avoiding redundant testing in application engineering

paper_content:

Many software product line testing techniques have been presented in the literature. The majority of those techniques address how to define reusable test assets (such as test models or test scenarios) in domain engineering and how to exploit those assets during application engineering. In addition to test case reuse however, the execution of test cases constitutes one important activity during application testing. Without a systematic support for the test execution in application engineering, while considering the specifics of product lines, product line artifacts might be tested redundantly. Redundant testing in application engineering, however, can lead to an increased testing effort without increasing the chance of uncovering failures. In this paper, we propose the model-based ScenTED-DF technique to avoid redundant testing in application engineering. Our technique builds on data flow-based testing techniques for single systems and adapts and extends those techniques to consider product line variability. The paper sketches the prototypical implementation of our technique to show its general feasibility and automation potential, and it describes the results of experiments using an academic product line to demonstrate that ScenTED-DF is capable of avoiding redundant tests in application engineering.
---
paper_title: Evolutionary Search-based Test Generation for Software Product Line Feature Models

paper_content:

Product line-based software engineering is a paradigm that models the commonalities and variabilities of different applications of a given domain of interest within a unique framework and enhances rapid and low cost development of new applications based on reuse engineering principles. Despite the numerous advantages of software product lines, it is quite challenging to comprehensively test them. This is due to the fact that a product line can potentially represent many different applications; therefore, testing a single product line requires the test of its various applications. Theoretically, a product line with n software features can be a source for the development of 2n application. This requires the test of 2n applications if a brute-force comprehensive testing strategy is adopted. In this paper, we propose an evolutionary testing approach based on Genetic Algorithms to explore the configuration space of a software product line feature model in order to automatically generate test suites. We will show through the use of several publicly-available product line feature models that the proposed approach is able to generate test suites of O(n) size complexity as opposed to O(2n) while at the same time form a suitable tradeoff balance between error coverage and feature coverage in its generated test suites.
---
paper_title: Detection of feature interactions using feature-aware verification

paper_content:

A software product line is a set of software products that are distinguished in terms of features (i.e., end-user-visible units of behavior). Feature interactions-- situations in which the combination of features leads to emergent and possibly critical behavior --are a major source of failures in software product lines. We explore how feature-aware verification can improve the automatic detection of feature interactions in software product lines. Feature-aware verification uses product-line-verification techniques and supports the specification of feature properties along with the features in separate and composable units. It integrates the technique of variability encoding to verify a product line without generating and checking a possibly exponential number of feature combinations. We developed the tool suite SPLVERIFIER for feature-aware verification, which is based on standard model-checking technology. We applied it to an e-mail system that incorporates domain knowledge of AT&T. We found that feature interactions can be detected automatically based on specifications that have only local knowledge.
---
paper_title: Toward variability-aware testing

paper_content:

We investigate how to execute a unit test for all products of a product line without generating each product in isolation in a brute-force fashion. Learning from variability-aware analyses, we (a) design and implement a variability-aware interpreter and, alternatively, (b) reencode variability of the product line to simulate the test cases with a model checker. The interpreter internally reasons about variability, executing paths not affected by variability only once for the whole product line. The model checker achieves similar results by reusing powerful off-the-shelf analyses. We experimented with a prototype implementation for each strategy. We compare both strategies and discuss trade-offs and future directions. In the long run, we aim at finding an efficient testing approach that can be applied to entire product lines with millions of products.
---
paper_title: Family-based performance measurement

paper_content:

Most contemporary programs are customizable. They provide many features that give rise to millions of program variants. Determining which feature selection yields an optimal performance is challenging, because of the exponential number of variants. Predicting the performance of a variant based on previous measurements proved successful, but induces a trade-off between the measurement effort and prediction accuracy. We propose the alternative approach of family-based performance measurement, to reduce the number of measurements required for identifying feature interactions and for obtaining accurate predictions. The key idea is to create a variant simulator (by translating compile-time variability to run-time variability) that can simulate the behavior of all program variants. We use it to measure performance of individual methods, trace methods to features, and infer feature interactions based on the call graph. We evaluate our approach by means of five feature-oriented programs. On average, we achieve accuracy of 98%, with only a single measurement per customizable program. Observations show that our approach opens avenues of future research in different domains, such an feature-interaction detection and testing.
---
paper_title: Automated and Scalable T-wise Test Case Generation Strategies for Software Product Lines

paper_content:

Software Product Lines (SPL) are difficult to validate due to combinatorics induced by variability across their features. This leads to combinatorial explosion of the number of derivable products. Exhaustive testing in such a large space of products is infeasible. One possible option is to test SPLs by generating test cases that cover all possible T feature interactions (T-wise). T-wise dramatically reduces the number of test products while ensuring reasonable SPL coverage. However, automatic generation of test cases satisfying T-wise using SAT solvers raises two issues. The encoding of SPL models and T-wise criteria into a set of formulas acceptable by the solver and their satisfaction which fails when processed ``all-at-once''. We propose a scalable toolset using Alloy to automatically generate test cases satisfying T-wise from SPL models. We define strategies to split T-wise combinations into solvable subsets. We design and compute metrics to evaluate strategies on Aspect OPTIMA, a concrete transactional SPL.
---
paper_title: MoSo-PoLiTe: tool support for pairwise and model-based software product line testing

paper_content:

Testing Software Product Lines is a very challenging task and approaches like combinatorial testing and model-based testing are frequently used to reduce the effort of testing Software Product Lines and to reuse test artifacts. In this contribution we present a tool chain realizing our MoSo-PoLiTe concept combining combinatorial and model-based testing. Our tool chain contains a pairwise configuration selection component on the basis of a feature model. This component implements an heuristic finding a minimal subset of configurations covering 100% pairwise interaction. Additionally, our tool chain allows the model-based test case generation for each configuration within this generated subset. This tool chain is based on commercial tools since it was developed within industrial cooperations. A non-commercial implementation of pairwise configuration selection is available and an integration with an Open Source model-based testing tool is under development.
---
paper_title: Feature consistency in compile-time-configurable system software: facing the linux 10,000 feature problem

paper_content:

Much system software can be configured at compile time to tailor it with respect to a broad range of supported hardware architectures and application domains. A good example is the Linux kernel, which provides more than 10,000 configurable features, growing rapidly. From the maintenance point of view, compile-time configurability imposes big challenges. The configuration model (the selectable features and their constraints as presented to the user) and the configurability that is actually implemented in the code have to be kept in sync, which, if performed manually, is a tedious and error-prone task. In the case of Linux, this has led to numerous defects in the source code, many of which are actual bugs. We suggest an approach to automatically check for configurability-related implementation defects in large-scale configurable system software. The configurability is extracted from its various implementation sources and examined for inconsistencies, which manifest in seemingly conditional code that is in fact unconditional. We evaluate our approach with the latest version of Linux, for which our tool detects 1,776 configurability defects, which manifest as dead/superfluous source code and bugs. Our findings have led to numerous source-code improvements and bug fixes in Linux: 123 patches (49 merged) fix 364 defects, 147 of which have been confirmed by the corresponding Linux developers and 20 as fixing a new bug.
---
paper_title: Reducing combinatorics in testing product lines

paper_content:

A Software Product Line (SPL) is a family of programs where each program is defined by a unique combination of features. Testing or checking properties of an SPL is hard as it may require the examination of a combinatorial number of programs. In reality, however, features are often irrelevant for a given test - they augment, but do not change, existing behavior, making many feature combinations unnecessary as far as testing is concerned. In this paper we show how to reduce the amount of effort in testing an SPL. We represent an SPL in a form where conventional static program analysis techniques can be applied to find irrelevant features for a test. We use this information to reduce the combinatorial number of SPL programs to examine.
---
paper_title: FeatureIDE: An Extensible Framework for Feature-Oriented Software Development

paper_content:

FeatureIDE is an open-source framework for feature-oriented software development (FOSD) based on Eclipse. FOSD is a paradigm for the construction, customization, and synthesis of software systems. Code artifacts are mapped to features, and a customized software system can be generated given a selection of features. The set of software systems that can be generated is called a software product line (SPL). FeatureIDE supports several FOSD implementation techniques such as feature-oriented programming, aspect-oriented programming, delta-oriented programming, and preprocessors. All phases of FOSD are supported in FeatureIDE, namely domain analysis, requirements analysis, domain implementation, and software generation.
---
paper_title: A Case Study Implementing Features Using AspectJ

paper_content:

Software product lines aim to create highly configurable programs from a set of features. Common belief and recent studies suggest that aspects are well-suited for implementing features. We evaluate the suitability of AspectJ with respect to this task by a case study that refactors the embedded database system Berkeley DB into 38 features. Contrary to our initial expectations, the results were not encouraging. As the number of aspects in a feature grows, there is a noticeable decrease in code readability and maintainability. Most of the unique and powerful features of AspectJ were not needed. We document where AspectJ is unsuitable for implementing features of refactored legacy applications and explain why.
---
paper_title: Analyzing the discipline of preprocessor annotations in 30 million lines of C code

paper_content:

The C preprocessor cpp is a widely used tool for implementing variable software. It enables programmers to express variable code (which may even crosscut the entire implementation) with conditional compilation. The C preprocessor relies on simple text processing and is independent of the host language (C, C++, Java, and so on). Language-independent text processing is powerful and expressive - programmers can make all kinds of annotations in the form of #ifdefs - but can render unpreprocessed code difficult to process automatically by tools, such as refactoring, concern management, and variability-aware type checking. We distinguish between disciplined annotations, which align with the underlying source-code structure, and undisciplined annotations, which do not align with the structure and hence complicate tool development. This distinction raises the question of how frequently programmers use undisciplined annotations and whether it is feasible to change them to disciplined annotations to simplify tool development and to enable programmers to use a wide variety of tools in the first place. By means of an analysis of 40 medium-sized to large-sized C programs, we show empirically that programmers use cpp mostly in a disciplined way: about 84% of all annotations respect the underlying source-code structure. Furthermore, we analyze the remaining undisciplined annotations, identify patterns, and discuss how to transform them into a disciplined form.
---
paper_title: PACOGEN: Automatic Generation of Pairwise Test Configurations from Feature Models

paper_content:

Feature models are commonly used to specify variability in software product lines. Several tools support feature models for variability management at different steps in the development process. However, tool support for test configuration generation is currently limited. This test generation task consists in systematically selecting a set of configurations that represent a relevant sample of the variability space and that can be used to test the product line. In this paper we propose \pw tool to analyze feature models and automatically generate a set of configurations that cover all pair wise interactions between features. \pw tool relies on constraint programming to generate configurations that satisfy all constraints imposed by the feature model and to minimize the set of the tests configurations. This work also proposes an extensive experiment, based on the state-of-the art SPLOT feature models repository, showing that \pw tool scales over variability spaces with millions of configurations and covers pair wise with less configurations than other available tools.
---
paper_title: Automatic detection of feature interactions using the Java modeling language: an experience report

paper_content:

In the development of complex software systems, interactions between different program features increase the design complexity. Feature-oriented software development focuses on the representation and compositions of features. The implementation of features often cuts across object-oriented module boundaries and hence comprises interactions. The manual detection and treatment of feature interactions requires a deep knowledge of the implementation details of the features involved. Our goal is to detect interactions automatically using specifications by means of design by contract and automated theorem proving. We provide a software tool that operates on programs in Java and the Java Modeling Language (JML). We discuss which kinds of feature interactions can be detected automatically with our tool and how to detect other kinds of interactions.
---
paper_title: Testing Software Product Lines Using Incremental Test Generation

paper_content:

We present a novel specification-based approach for generating tests for products in a software product line. Given properties of features as first-order logic formulas, our approach uses SAT-based analysis to automatically generate test inputs for each product in a product line. To ensure soundness of generation, we introduce an automatic technique for mapping a formula that specifies a feature into a transformation that defines incremental refinement of test suites. Our experimental results using different data structure product lines show that incremental approach can provide an order of magnitude speed-up over conventional techniques.
---
paper_title: Virtual Separation of Concerns -- A Second Chance for Preprocessors

paper_content:

Conditional compilation with preprocessors like cpp is a simple but eective means to implement variability. By annotating code fragments with #ifdef and #endif directives, dierent program variants with or without these fragments can be created, which can be used (among others) to implement software product lines. Although, preprocessors are frequently used in practice, they are often criticized for their negative eect on code quality and maintainability. In contrast to modularized implementations, for example using components or aspects, preprocessors neglect separation of concerns, are prone to introduce subtle errors, can entirely obfuscate the source code, and limit reuse. Our aim is to rehabilitate the preprocessor by showing how simple tool support can address these problems and emulate some benets of modularized implementations. At the same time we emphasize unique benets of preprocessors, like simplicity and language independence. Although we do not have a denitive answer on how to implement variability, we want highlight opportunities to improve preprocessors and encourage research toward novel preprocessor-based approaches.
---
paper_title: A Classification and Survey of Analysis Strategies for Software Product Lines

paper_content:

Software-product-line engineering has gained considerable momentum in recent years, both in industry and in academia. A software product line is a family of software products that share a common set of features. Software product lines challenge traditional analysis techniques, such as type checking, model checking, and theorem proving, in their quest of ensuring correctness and reliability of software. Simply creating and analyzing all products of a product line is usually not feasible, due to the potentially exponential number of valid feature combinations. Recently, researchers began to develop analysis techniques that take the distinguishing properties of software product lines into account, for example, by checking feature-related code in isolation or by exploiting variability information during analysis. The emerging field of product-line analyses is both broad and diverse, so it is difficult for researchers and practitioners to understand their similarities and differences. We propose a classification of product-line analyses to enable systematic research and application. Based on our insights with classifying and comparing a corpus of 123 research articles, we develop a research agenda to guide future research on product-line analyses.
---

Title: An overview on analysis tools for software product lines

Section 1: INTRODUCTION
Description 1: Introduce the concept of software product lines, the importance of feature-oriented software development (FOSD), and the need for efficient analysis tools.

Section 2: CHARACTERISTICS OF PRODUCT-LINE TOOLS
Description 2: Describe the different aspects of FOSD, including domain analysis, domain design and specification, domain implementation, and product configuration and generation, and introduce the categorization of tools.

Section 3: PRODUCT-LINE TESTING
Description 3: Discuss the tools available for testing product lines, including those for sampling and beyond sampling, highlighting different strategies and examples of tools.

Section 4: PRODUCT-LINE VERIFICATION
Description 4: Outline the tools used for the verification of product lines, including type checking, static analysis, software model checking, theorem proving, and consistency checking, with examples of each.

Section 5: FURTHER PRODUCT-LINE ANALYSES
Description 5: Cover additional analysis tools for non-functional properties and code metrics, providing examples and explaining their relevance to software product lines.

Section 6: OVERVIEW ON TOOL SUPPORT
Description 6: Summarize the tools discussed in previous sections, categorizing them by analysis technique and product-line implementation technique, and discuss the current state of tool support.

Section 7: CONCLUSION
Description 7: Conclude the paper by emphasizing the importance of efficient analysis for software product lines, summarizing the contributions, and referring to additional resources such as the website maintained for product-line tools.