SPL Conqueror: Toward optimization of non-functional properties in software product lines

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.     

Efficient software product-line model checking using induction and a SAT solver

Software product line (SPL) engineering is increasingly being adopted in safety-critical systems. It is highly desirable to rigorously show that these systems are designed correctly. However, formal analysis for SPLs is more difficult than for single systems because an SPL may contain a large number of individual systems. In this paper, we propose an efficient model-checking technique for SPLs using induction and a SAT (Boolean satisfiability problem) solver. We show how an induction-based verification method can be adapted to the SPLs, with the help of a SAT solver. To combat the state space explosion problem, a novel technique that exploits the distinguishing characteristics of SPLs, called feature cube enlargement, is proposed to reduce the verification efforts. The incremental SAT mechanism is applied to further improve the efficiency. The correctness of our technique is proved. Experimental results show dramatic improvement of our technique over the existing binary decision diagram (BDD)-based techniques.     

Model-based pairwise testing for feature interaction coverage in software product line engineering

Testing software product lines (SPLs) is very challenging due to a high degree of variability leading to an enormous number of possible products. The vast majority of today??s testing approaches for SPLs validate products individually using different kinds of reuse techniques for testing. Because of their reusability and adaptability capabilities, model-based approaches are suitable to describe variability and are therefore frequently used for implementation and testing purposes of SPLs. Due to the enormous number of possible products, individual product testing becomes more and more infeasible. Pairwise testing offers one possibility to test a subset of all possible products. However, according to the best of our knowledge, there is no contribution discussing and rating this approach in the SPL context. In this contribution, we provide a mapping between feature models describing the common and variable parts of an SPL and a reusable test model in the form of statecharts. Thereby, we interrelate feature model-based coverage criteria and test model-based coverage criteria such as control and data flow coverage and are therefore able to discuss the potentials and limitations of pairwise testing. We pay particular attention to test requirements for feature interactions constituting a major challenge in SPL engineering. We give a concise definition of feature dependencies and feature interactions from a testing point of view, and we discuss adequacy criteria for SPL coverage under pairwise feature interaction testing and give a generalization to the T-wise case. The concept and implementation of our approach are evaluated by means of a case study from the automotive domain.     

PAxSPL: A feature retrieval process for software product line reengineering

Software product lines (SPLs) are a well-known solution to systematically create reusable software products. Among the approaches to create an SPL, the extractive approach is usually used when the organization already has a set of similar systems. These systems are analyzed to extract, categorize, and group their common and variant features throughout the SPL reengineering process. As there are different scenario variables, such as available artifacts and team experience, the activities and techniques used to perform these tasks may change. This may increase the effort and decrease the quality of retrieved features when users with low experience in SPL reengineering perform such tasks. However, there is a lack of a process supporting these tasks considering different scenarios. Therefore, we specify the P repare, A ssemble, and E x ecute Process for SPL Reengineering (PAxSPL), a process that provides support to prepare, assemble, and execute feature retrieval throughout the analysis of documentation and team experience. To initially evaluate PAxSPL, we conducted and reported an exploratory case study in a real development environment. The results indicated that our proposal helps in the assembly of a feature retrieval process according to user needs. Results were important to identify points for improvement in PAxSPL. We also could use the information gathered to improve the guidelines and provide this information to be used as basis of comparison for future users.     

A Feature Model Based Framework for Refactoring Software Product Line Architecture

Software product line (SPL) is an approach used to develop a range of software products with a high degree of similarity. In this approach, a feature model is usually used to keep track of similarities and differences. Over time, as modifications are made to the SPL, inconsistencies with the feature model could arise. The first approach to dealing with these inconsistencies is refactoring. Refactoring consists of small steps which, when accumulated, may lead to large-scale changes in the SPL, resulting in features being added to or eliminated from the SPL. In this paper, we propose a framework for refactoring SPLs, which helps keep SPLs consistent with the feature model. After some introductory remarks, we describe a formal model for representing the feature model. We express various refactoring patterns applicable to the feature model and the SPL formally, and then introduce an algorithm for finding them in the SPL. In the end, we use a real-world case study of an SPL to illustrate the applicability of the framework introduced in the paper.     

Heuristic and exact algorithms for product configuration in software product lines

Software product line (SPL) is a set of software applications that share a common set of features satisfying the specific needs of a particular market segment. SPL engineering is a paradigm to develop software applications that commonly use a feature model to capture and document common and variable features, and their relationships. A big challenge is to derive one product among all possible products in the SPL, which satisfies the business and customer requirements. This task is known as product configuration. Although product configuration has been extensively investigated in the literature, customer's preferences are frequently neglected. In this paper, we propose a novel approach to configure a product that considers both qualitative and quantitative feature properties. We model the product configuration task as a combinatorial optimization problem, and heuristic and exact algorithms are proposed. As far as we are concerned, this proposal is the first work in the literature that considers feature properties in both leaf and nonleaf features. Computational experiments showed that the best of our heuristics found optimal solutions for all instances where those are known. For the instances where optimal solutions are not known, our heuristic outperformed the best solution obtained by a one‐hour run of the exact algorithm by up to 67.89%.     

Automated diagnosis of feature model configurations

Software product-lines (SPLs) are software platforms that can be readily reconfigured for different project requirements. A key part of an SPL is a model that captures the rules for reconfiguring the software. SPLs commonly use feature models to capture SPL configuration rules. Each SPL configuration is represented as a selection of features from the feature model. Invalid SPL configurations can be created due to feature conflicts introduced via staged or parallel configuration or changes to the constraints in a feature model. When invalid configurations are created, a method is needed to automate the diagnosis of the errors and repair the feature selections.This paper provides two contributions to research on automated configuration of SPLs. First, it shows how configurations and feature models can be transformed into constraint satisfaction problems to automatically diagnose errors and repair invalid feature selections. Second, it presents empirical results from diagnosing configuration errors in feature models ranging in size from 100 to 5,000 features. The results of our experiments show that our CSP-based diagnostic technique can scale up to models with thousands of features.     

Deriving products for variability test of Feature Models with a hyper-heuristic approach

Deriving products from a Feature Model (FM) for testing Software Product Lines (SPLs) is a hard task. It is important to select a minimum number of products but, at the same time, to consider the coverage of testing criteria such as pairwise, among other factors. To solve such problems Multi-Objective Evolutionary Algorithms (MOEAs) have been successfully applied. However, to design a solution for this and other software engineering problems can be very difficult, because it is necessary to choose among different search operators and parameters. Hyper-heuristics can help in this task, and have raised interest in the Search-Based Software Engineering (SBSE) field. Considering the growing adoption of SPL in the industry and crescent demand for SPL testing approaches, this paper introduces a hyper-heuristic approach to automatically derive products to variability testing of SPLs. The approach works with MOEAs and two selection methods, random and based on FRR-MAB (Fitness Rate Rank based Multi-Armed Bandit). It was evaluated with real FMs and the results show that the proposed approach outperforms the traditional algorithms used in the literature, and that both selection methods present similar performance.     

Feature Nets: behavioural modelling of software product lines

Software product lines (SPLs) are diverse systems that are developed using a dual engineering process: (a) family engineering defines the commonality and variability among all members of the SPL, and (b) application engineering derives specific products based on the common foundation combined with a variable selection of features. The number of derivable products in an SPL can thus be exponential in the number of features. This inherent complexity poses two main challenges when it comes to modelling: firstly, the formalism used for modelling SPLs needs to be modular and scalable. Secondly, it should ensure that all products behave correctly by providing the ability to analyse and verify complex models efficiently. In this paper, we propose to integrate an established modelling formalism (Petri nets) with the domain of software product line engineering. To this end, we extend Petri nets to Feature Nets. While Petri nets provide a framework for formally modelling and verifying single software systems, Feature Nets offer the same sort of benefits for software product lines. We show how SPLs can be modelled in an incremental, modular fashion using Feature Nets, provide a Feature Nets variant that supports modelling dynamic SPLs, and propose an analysis method for SPL modelled as Feature Nets. By facilitating the construction of a single model that includes the various behaviours exhibited by the products in an SPL, we make a significant step towards efficient and practical quality assurance methods for software product lines.     

Pairwise testing for software product lines: comparison of two approaches

Software Product Lines (SPL) are difficult to validate due to combinatorics induced by variability, which in turn leads to combinatorial explosion of the number of derivable products. Exhaustive testing in such a large products space is hardly feasible. Hence, one possible option is to test SPLs by generating test configurations that cover all possible t feature interactions (t-wise). It dramatically reduces the number of test products while ensuring reasonable SPL coverage. In this paper, we report our experience on applying t-wise techniques for SPL with two independent toolsets developed by the authors. One focuses on generality and splits the generation problem according to strategies. The other emphasizes providing efficient generation. To evaluate the respective merits of the approaches, measures such as the number of generated test configurations and the similarity between them are provided. By applying these measures, we were able to derive useful insights for pairwise and t-wise testing of product lines.     

A systematic mapping study of search-based software engineering for software product lines

ContextSearch-Based Software Engineering (SBSE) is an emerging discipline that focuses on the application of search-based optimization techniques to software engineering problems. Software Product Lines (SPLs) are families of related software systems whose members are distinguished by the set of features each one provides. SPL development practices have proven benefits such as improved software reuse, better customization, and faster time to market. A typical SPL usually involves a large number of systems and features, a fact that makes them attractive for the application of SBSE techniques which are able to tackle problems that involve large search spaces.ObjectiveThe main objective of our work is to identify the quantity and the type of research on the application of SBSE techniques to SPL problems. More concretely, the SBSE techniques that have been used and at what stage of the SPL life cycle, the type of case studies employed and their empirical analysis, and the fora where the research has been published.MethodA systematic mapping study was conducted with five research questions and assessed 77 publications from 2001, when the term SBSE was coined, until 2014.ResultsThe most common application of SBSE techniques found was testing followed by product configuration, with genetic algorithms and multi-objective evolutionary algorithms being the two most commonly used techniques. Our study identified the need to improve the robustness of the empirical evaluation of existing research, a lack of extensive and robust tool support, and multiple avenues worthy of further investigation.ConclusionsOur study attested the great synergy existing between both fields, corroborated the increasing and ongoing interest in research on the subject, and revealed challenging open research questions.     

Flexible feature binding in software product lines

A software product line (SPL) is a family of programs that share assets from a common code base. The programs of an SPL can be distinguished in terms of features, which represent units of program functionality that satisfy stakeholders’ requirements. The features of an SPL can be bound either statically at program compile time or dynamically at run time. Both binding times are used in SPL development and have different advantages. For example, dynamic binding provides high flexibility whereas static binding supports fine-grained customizability without any impact on performance (e.g., for use on embedded systems). However, contemporary techniques for implementing SPLs force a programmer to choose the binding time already when designing an SPL and to mix different implementation techniques when multiple binding times are needed. We present an approach that integrates static and dynamic feature binding seamlessly. It allows a programmer to implement an SPL once and to decide per feature at deployment time whether it should be bound statically or dynamically. Dynamic binding usually introduces an overhead regarding resource consumption and performance. We reduce this overhead by statically merging features that are used together into dynamic binding units. A program can be configured at run time by composing binding units on demand. We use feature models to ensure that only valid feature combinations can be selected at compile and at run time. We provide a compiler and evaluate our approach on the basis of two non-trivial SPLs.     

Product line engineering, the state of the practice

Software product lines can be very powerful for ensuring quality, economic efficiency, and manageability of software system families. SPLs are relevant to large industrial enterprises that want to better manage their software-intensive systems' development. They can also provide small start-ups with unique and striking business models. However, SPL technology can be difficult to implement and maintain. A work group comprising five organizations has investigated and compared SPL practices. The results detail the state of SPL practice.     

Comparing practices for reuse in integration‐oriented software product lines and large open source software projects

This article compares the organization and practices for software reuse in integration‐oriented software product lines (SPLs) and open source software projects. The main observation is that both approaches are successful regarding large variability and reuse, but differ widely in their practices and organization. To capture practices in large open source projects, we describe an open compositional model, which reflects their more decentralized organization of software development. We capture key practices and organizational forms for this and validate these by comparing four case studies of this model. Two of these studies are based on published SPL case studies, for the other two we analyze the practices in two large and successful open source projects based on their published developer documentation. Our analysis highlights key differences between the practices in the two open source organizations and the more integrational practices used in the other two cases. Finally, we discuss which practices are successful in which environment and how the current practices can move towards more open, widely scoped and distributed software development. Copyright © 2010 John Wiley & Sons, Ltd.     

Formal semantics,modular specification,and symbolic verification of product-line behaviour

Formal techniques for specifying and verifying Software Product Lines (SPL) are actively studied. While the foundations of this domain recently made significant progress with the introduction of Featured Transition Systems (FTSs) and associated algorithms, SPL model checking still faces the well-known state explosion problem. Moreover, there is a need for high-level specification languages usable in industry. We address the state explosion problem by applying the principles of symbolic model checking to FTS-based verification of SPLs. In order to specify properties on specific products only, we extend the temporal logic CTL with feature quantifiers. Next, we show how SPL behaviour can be specified with fSMV, a variant of SMV, the specification language of the industry-strength model checker NuSMV. fSMV is a feature-oriented extension of SMV originally introduced by Plath and Ryan. We prove that fSMV and FTSs are expressively equivalent. Finally, we connect these results to a NuSMV extension we developed for verifying SPLs against CTL properties.     

Consistency maintenance for evolving feature models

Software product line (SPL) techniques handle the construction of customized systems. One of the most common representations of the decisions a customer can make in SPLs is feature models (FMs). An FM represents the relationships among common and variable features in an SPL. Features are a representation of the characteristics in a system that are relevant to customers.FMs are subject to change since the set of features and their relationships can change along an SPL lifecycle. Due to this evolution, the consistency of FMs may be compromised. There exist some approaches to detect and explain inconsistencies in FMs, however this process can take a long time for large FMs.In this paper we present a complementary approach to dealing with inconsistencies in FM evolution scenarios that improves the performance for existing approaches reducing the impact of change to the smallest part of an FM that changes. To achieve our goal, we formalize FMs from an ontological perspective and define constraints that must be satisfied in FMs to be consistent. We define a set of primitive operations that modify FMs and which are responsible for the FM evolution, analyzing their impact on the FM consistency. We propose a set of predefined strategies to keep the consistency for error-prone operations.As a proof-of-concept we present the results of our experiments, where we check for the effectiveness and efficiency of our approach in FMs with thousands of features. Although our approach is limited by the kinds of consistency constraints and the primitive operations we define, the experiments present a significant improvement in performance results in those cases where they are applicable.     

Domain modeling as a basis for building a meshing tool software product line

Meshing tools are highly complex software for generating and managing geometrical discretizations. Due to their complexity, they have generally been developed by end users – physicists, forest engineers, mechanical engineers – with ad hoc methodologies and not by applying well established software engineering practices. Different meshing tools have been developed over the years, making them a good application domain for Software Product Lines (SPLs). This paper proposes building a domain model that captures the different domain characteristics such as features, goals, scenarios and a lexicon, and the relationships among them. The model is partly specified using a formal language. The domain model captures product commonalities and variabilities as well as the particular characteristics of different SPL products. The paper presents a rigorous process for building the domain model, where specific roles, activities and artifacts are identified. This process also clearly establishes consistency and completeness conditions. The usefulness of the model and the process are validated by using them to generate a software product line of Tree Stem Deformation (TSD) meshing tools. We also present Meshing Tool Generator, a software that follows the SPL approach for generating meshing tools belonging to the TSD SPL. We show how an end user can easily generate three different TSD meshing tools using Meshing Tool Generator.     

Improving software product line configuration: A quality attribute-driven approach

ContextDuring the definition of software product lines (SPLs) it is necessary to choose the components that appropriately fulfil a product’s intended functionalities, including its quality requirements (i.e., security, performance, scalability). The selection of the appropriate set of assets from many possible combinations is usually done manually, turning this process into a complex, time-consuming, and error-prone task.ObjectiveOur main objective is to determine whether, with the use of modeling tools, we can simplify and automate the definition process of a SPL, improving the selection process of reusable assets.MethodWe developed a model-driven strategy based on the identification of critical points (sensitivity points) inside the SPL architecture. This strategy automatically selects the components that appropriately match the product’s functional and quality requirements. We validated our approach experimenting with different real configuration and derivation scenarios in a mobile healthcare SPL where we have worked during the last three years.ResultsThrough our SPL experiment, we established that our approach improved in nearly 98% the selection of reusable assets when compared with the unassisted analysis selection. However, using our approach there is an increment in the time required for the configuration corresponding to the learning curve of the proposed tools.ConclusionWe can conclude that our domain-specific modeling approach significantly improves the software architect’s decision making when selecting the most suitable combinations of reusable components in the context of a SPL.     

Evolving feature model configurations in software product lines

The increasing complexity and cost of software-intensive systems has led developers to seek ways of reusing software components across development projects. One approach to increasing software reusability is to develop a software product-line (SPL), which is a software architecture that can be reconfigured and reused across projects. Rather than developing software from scratch for a new project, a new configuration of the SPL is produced. It is hard, however, to find a configuration of an SPL that meets an arbitrary requirement set and does not violate any configuration constraints in the SPL.Existing research has focused on techniques that produce a configuration of an SPL in a single step. Budgetary constraints or other restrictions, however, may require multi-step configuration processes. For example, an aircraft manufacturer may want to produce a series of configurations of a plane over a span of years without exceeding a yearly budget to add features.This paper provides three contributions to the study of multi-step configuration for SPLs. First, we present a formal model of multi-step SPL configuration and map this model to constraint satisfaction problems (CSPs). Second, we show how solutions to these SPL configuration problems can be automatically derived with a constraint solver by mapping them to CSPs. Moreover, we show how feature model changes can be mapped to our approach in a multi-step scenario by using feature model drift. Third, we present empirical results demonstrating that our CSP-based reasoning technique can scale to SPL models with hundreds of features and multiple configuration steps.     

Generative software product line development using variability-aware design patterns

Software Product Lines (SPLs) are an approach to reuse in-the-large that models a set of closely related software systems in terms of commonalities and variabilities. Design patterns are best practices for addressing recurring design problems in object-oriented source code. In the practice of implementing SPL, instances of certain design patterns are employed to handle variability, which makes these “variability-aware design patterns” a best practice for SPL design. However, currently there is no dedicated method for proactively developing SPLs using design patterns suitable for realizing variable functionality. In this paper, we present a method to perform generative SPL development with design patterns. We use role models to capture design patterns and their relation to a variability model. We further allow mapping of individual design pattern roles to (parts of) implementation elements to be generated (e.g., classes, methods) and check the conformance of the realization with the specification of the pattern. We provide definitions for the variability-aware versions of the design patterns Observer, Strategy, Template Method and Composite. Furthermore, we support generation of realizations in Java, C++ and UML class diagrams utilizing annotative, compositional and transformational variability realization mechanisms. Hence, we support proactive development of SPLs using design patterns to apply best practices for the realization of variability. We realize our concepts within the Eclipse IDE and demonstrate them within a case study.