WIXLIB

4·Thomas Thüm et al.Feature module SingleStoreclass Store {private Object value;Object read() { return value; }void set(Object nvalue) { value nvalue; }}Feature module MultiStoreclass Store {private LinkedList values new LinkedList();Object read() { return values.getFirst(); }Object[] readAll() { return values.toArray(); }void set(Object nvalue) { values.addFirst(nvalue); }}Feature module AccessControlrefines class Store {private boolean sealed false;Object read() {if (!sealed) { return Super.read(); }else { throw new RuntimeException("Access denied!"); }}void set(Object nvalue) {if (!sealed) { Super.set(nvalue); }else { throw new RuntimeException("Access denied!"); }}}Fig. 1. A feature-oriented implementation of an object store: feature code is separated in multiplecomposition units.control access (Super is used to refer from the overriding method to the overriddenmethod).Once a user has selected a list of desired features, a composer generates the final product. In our example, we use the AHEAD tool suite [Batory et al. 2004]for the composition of the feature modules that correspond to the selected features. Essentially, the composer assembles all classes and all class refinements ofthe features modules being composed. The semantics of a class refinement (denotedwith refines class) is that a given class is extended by new methods and fields.Similar to a subclass, using class refinements is also possible to override or extendexisting methods. While the features SingleStore and MultiStore introduce onlyregular Java classes, feature AccessControl refines an existing class by adding newmembers.As said previously, there are alternative implementation approaches for softwareproduct lines (e.g., conditional compilation, frameworks) [Apel and Kästner 2009].The analysis strategies presented in this article are largely independent of the usedimplementation approach.Variability models. Decomposing the object store along its features gives riseto compositional flexibility; features can be composed in any combination. Often

Analysis Strategies for Software Product ltiStoreSingleStore MultiStore AccessControl (SingleStore crete(a) Feature diagramP1P2P3P4(b) Propositional formula {SingleStore} {SingleStore, AccessControl} {MultiStore} {MultiStore, AccessControl}(c) Enumeration of all valid combinationsFig. 2.The variability model of the object store in three alternative representations.not all feature combinations are desired (e.g., we must not select SingleStore andMultiStore in the same product); hence, product-line engineers typically specifyconstraints on feature combinations in a variability model (i.e., the set of validproducts). In Figure 2a, we specify the valid combinations of our object store ina feature diagram. A feature diagram is a graphical representation of a variabilitymodel defining a hierarchy between features, in which child features depend ontheir parent feature [Kang et al. 1990]. Each object store has a type that is eitherSingleStore or MultiStore. Furthermore, the object store may have the optionalfeature AccessControl. Valid feature combinations can alternatively be specifiedusing propositional formulas [Batory 2005], as shown in Figure 2b; each variableencodes the absence or presence of a particular feature in the final product, andthe overall formula yields true for valid feature combinations. In our example,there are four products that are valid according to the variability model, which areenumerated in Figure 2c – another representation of a feature model.Automatic Product Generation. In this survey, we focus on implementation techniques for software product lines that support the automatic generation of productsbased on a selection of features. Once a user selects a valid subset of features, agenerator generates the corresponding product, without any user assistance such asproviding glue code. Examples of such implementation techniques are conditionalcompilation [Kästner 2010; Heidenreich et al. 2008], generative programming [Czarnecki and Eisenecker 2000], feature-oriented programming [Prehofer 1997; Batoryet al. 2004], aspect-oriented programming [Kiczales et al. 1997], and delta-orientedprogramming [Schaefer et al. 2010]. All these approaches give software developersthe ability to derive software products automatically based on a selection of desiredfeatures. The overall goal is to minimize the effort to implement new features andthus to implement new software products.

·ApplicationEngineeringDomainEngineering6Thomas Thüm et iability ModelConfigurationsDomain ArtifactsSoftware GeneratorSoftware ProductsFig. 3. In domain engineering, variability models and domain artifacts are created, which are usedin application engineering to automatically generate software products based on feature selections.In Figure 3, we illustrate the processes of domain engineering and applicationengineering (in a simplified form), since they are central to the development of software product lines. In domain engineering, a developer creates a variability modeldescribing the valid combinations of features. Furthermore, a developer createsreusable software artifacts (i.e., domain artifacts) that implement each feature. Forexample, the feature modules of the object store are considered as domain artifacts. In application engineering, the developer determines a selection of featuresthat is valid according to the variability model. Based on this selection, the software product containing the selected features is generated automatically based onthe domain artifacts created during domain engineering. For example, composingthe feature modules SingleStore and AccessControl results in generated softwareartifacts constituting a software product in our product line of object stores.Correctness. An interesting issue in our running example (introduced deliberately) is that one of the four valid products misbehaves. The purpose of featureAccessControl is to prohibit access to sealed stores. We could specify this intendedbehavior formally, for example, using temporal logic: G AccessControl (state access(Store s) s.sealed)The formula states, given that feature AccessControl is selected, whenever theobject store s is accessed, the object store is not sealed. If we select AccessControlin combination with MultiStore (i.e., generating product P4 from Figure 2c), thespecification of AccessControl is violated; a client can access a store using methodreadAll() even though the store is sealed.To fix the problem, we can alter the implementation of feature AccessControl.For example, we can refine method readAll() in analogy to read() and set().While this change fixes the behavior problem for combining MultiStore and AccessControl, it introduces a new problem: The changed implementation of AccessControl no longer composes with SingleStore, because it attempts to override method

Analysis Strategies for Software Product Lines·7readAll(), which is not present in this feature combination.The illustrated problem is called the optional feature problem [Kästner et al.2009]: The implementation of a certain feature may rely on the implementationof another feature (e.g., caused by method references) and thus the former featurecannot be selected independently, even if it is desired by the user. There are severalsolutions (for example, we could modify the variability model to forbid the criticalfeature combination for P4 , we could change the specification, or we could resolvethe problem with alternative implementation patterns) [Kästner et al. 2009], buta discussion is outside the scope of this article. The point of our example is toillustrate how products can misbehave or cause compiler-errors even though theyare valid according to the variability model. Even worse, such problems may occuronly in specific feature combinations (e.g., only in P4 ), out of potentially millionsof products that are valid according to the variability model; hence, they are hardto find and may show up only late in the software life cycle. Such situation wherethe variability model and implementation are inconsistent, have been repeatedlyobserved in real product lines and are certainly not an exception [Thaker et al.2007; Kästner et al. 2012; Tartler et al. 2011].2.2Software AnalysesWe briefly introduce important software analyses that have been applied andadapted to software product lines (from light-weight to heavy-weight). As saidpreviously, we focus analysis that operate statically and can guarantee the absenceof errors; thus, we exclude runtime analyses and testing. Each of the discussedanalyses has its strengths and weaknesses. We argue that a wide variety of analyses is needed to increase the reliability of software, in general, and software productlines, in particular.Type Checking. A type system is a tractable syntactic method for proving theabsence of certain program behaviors by classifying phrases according to the kindsof values they compute [Pierce 2002]. Type systems can be used to classify programs into well-typed and ill-typed programs syntactically based on a set of interference rules. Type checking refers to the process of analyzing whether a programis well-typed according to a certain type system defined for the given programminglanguage. A type checker is the actual tool analyzing programs written in a certainlanguage, usually part of a compiler or linker [Pierce 2002].Using type checking, we can detect type errors such as incompatible type casts,dangling method references, and duplicate class names. For instance, a danglingmethod reference occurs if a method with a certain signature is called that is notdeclared. For our object store, we discussed that calling method readAll() infeature AccessControl would result in a dangling method reference in product P4 .Other examples are that a programmer may have misspelled the name of a method,or the number of parameters is not correct. Type errors are frequent in the development of software; the evolution of software often requires to add new parametersto a method declaration or to rename identifiers.A type system can be seen as a formal specification that is common to all programs written in a certain language. Pierce [2002] argues that, in principle, typescan be created to check arbitrary specifications. But in practice, type systems are

8·Thomas Thüm et al.limited to properties that are efficiently statically decidable and checkable.Model Checking. Model checking is an automatic technique for verification. Essentially, it verifies that a given formal model of a system satisfies its specification [Clarke et al. 1999]. While early work concentrated on abstract system modelsor models of hardware, recently software systems came into focus (e.g., C or Javaprograms) in software model checking. Often, a specification is concerned withsafety properties such as the absence of deadlocks and race conditions, but alsoapplication-specific requirements can be formulated. To solve a model-checkingproblem algorithmically, both the system model and the specification must be formulated in a precise mathematical language.A model checker is a tool that performs a model-checking task based on the system to verify and its specification. Some model checkers require the use of dedicatedinput languages for this task (e.g., Promela in SPIN, CMU SMV input languagein NuSMV), and some work on programs and specifications written in mainstreamprogramming languages (e.g., C in Blast or CPAchecker, Java in JavaPathfinder).After encoding a model-checking problem into the model checker’s input language,the model-checking task is fully automated; each property is either stated valid ora counterexample is provided. The counterexample helps the user to identify thesource of invalidity. The most severe reduction for the practical applicability ofmodel checkers is the limit of the size of the state space they can handle [Schumann2001].Static Analysis. The term static analysis refers to a set of possible programanalyses that can be performed without actually executing the program [Nielsonet al. 2010]. In this sense, type checking and model checking are special instancesof static analysis techniques. Some static analyses approaches operate on sourcecode (e.g., Lint for C), others on byte code (e.g., FindBugs for Java byte code).Some are lightweight such that defects are searched based on simple patterns (e.g.,Lint), while others target the whole program behavior such as model checkers.Static analyses can be implemented within compilers such as Clang or in the formof dedicated tools such as FindBugs. Common examples of static analyses arecontrol-flow analysis, data-flow analysis, and alias analysis.Theorem Proving. Theorem proving is a deductive approach to prove the validity of logical formulas. A theorem prover is a tool processing logical formulas byapplying inference rules upon them [Schumann 2001] and it assists the programmer in verifying the correctness of formulas, which can be achieved interactivelyor automatically. Interactive theorem provers such as Coq, PVS, or Isabellerequire a user to write commands to apply inference rules. Instead, automated theorem provers such as Prover9, SPASS, or Simplify evaluate the validity withoutfurther assistance by the user.All kinds of theorem provers provide a language to express logical formulas (theorems). Furthermore, interactive theorem provers also need to provide a language forproof commands. Automated theorem provers are often limited to first-order logicor subsets thereof, whereas interactive theorem provers are available for higherorder logics and typed logics. Theorem provers are able to generate proof scriptscontaining deductive reasoning that can be inspected by humans.

Analysis Strategies for Software Product Lines·9Theorem provers are used in many applications, because of their high expressiveness and generality. In the analysis of software products, theorem provers are usedto formally prove that a program fulfills its specification. A formal specificationcould be that the program terminates and returns a number larger than zero. Inprogram verification, a specification is given in some formal language, and thena verification tool generates theorems based on implementation and specificationthat is the input for a theorem prover. If a theorem cannot be proved, theoremprovers point to the part of a theorem that could not be proved. The main disadvantage of theorem proving is that experts with an education in logical reasoningand considerable experience are needed [Clarke et al. 1999].3.ANALYSIS STRATEGIES FOR SOFTWARE PRODUCT LINESMany software systems such as the Linux kernel [Berger et al. 2010; Sincero et al.2007] are implemented as software product lines. But, contemporary analysis toolsare usually inefficient, as they do not take variability into account. The reason isthat software product lines require language extensions or preprocessors to expressand manage variability. Hence, analysis tools are applicable mostly only to derivedsoftware products – not to domain artifacts as developed and maintained by theprogrammer. But, analyzing each software product of a product line individuallydoes not scale in practice. The mismatch between efficient implementation techniques and inefficient software-analysis techniques is an open research topic. Fislerand Krishnamurthi [2005] argue that the analysis effort should be proportional tothe implementation effort. Even if this goal may not be reachable in general, analyses of software product lines need to scale better than exhaustively analyzing eachproduct.In the last decade, researchers have proposed and developed a number of analysistechniques tailored to software product lines. The key idea is to exploit knowledgeabout features and the commonalities and variabilities of a product line to systematically reduce analysis effort. Existing product-line analyses are typically basedon standard analysis methods, in particular, type checking, static analysis, modelchecking, and theorem proving. All these methods have been used successfullyfor analyzing single software products. They have complementary strengths andweaknesses, for instance, with regard to practicality, correctness guarantees, andcomplexity; so all of them appear useful for product-line analysis.Unfortunately, in most cases it is hard to compare these analysis techniquesregarding scalability or even to find the approach that fits best for a given productline scenario. The reason is that approaches are presented using varying nomenclatures, especially if multiple software analyses are involved. In this section, weclassify existing product-line-analysis approaches based on how they attempt toreduce analysis effort – the analysis strategy. We distinguish three basic strategies:product-based, family-based, and feature-based. We explain the basic strategiesand discuss existing approaches realizing each strategy. While surveying the literature, we found that some approaches for the analysis of software product linesactually combine the basic strategies, so we discuss possible combinations.

103.1·Thomas Thüm et al.Product-Based AnalysesPursuing a product-based analysis, products are generated and analyzed individually, each using a standard analysis method. The simplest approach is to generateand analyze all products in a brute-force fashion, but this is feasible only for product lines with few products. A typical strategy is to sample a smaller number ofproducts, usually based on some coverage criteria, such that still reasonable statements on the correctness of the entire product line are possible [Oster et al. 2010;Perrouin et al. 2010]. We define product-based analyses as follows:Definition 3.1 Product-based analysis. An analysis of a software product line iscalled product-based, if it operates only on generated products or models thereof. Aproduct-based analysis is called optimized, if it operates on a subset of all productsor if intermediate analysis results are reused, and is called unoptimized otherwise.Example. In our object store example, we can generate and compile each productto detect type errors. While such unoptimized product-based strategy is applicableto our small example, we need optimizations for larger software product lines.One could save analysis effort when checking whether the specification of featureAccessControl is satisfied: First, all products that do not contain AccessControl donot need to be checked. Second, if two products differ only in features that do notconcern class Store (not shown in our example; e.g., features that are concernedwith other data structures), only one of these products needs to be checked.Advantages and Disadvantages. The main advantage of product-based analyses isthat every existing software analysis can easily be applied in the context of softwareproduct lines. In particular, existing off-the-shelf tools can be reused to analyzethe products. Furthermore, product-based analyses can easily deal with changes tosoftware product lines that alter only a small set of products, because only changedproducts need to be re-analyzed.An unoptimized product-based analysis is sound and complete with respect to theapplied software analysis. First, every error detected using this strategy, is an errorof a software product that can be detected by the base software analysis (soundness).Second, every error that can be detected using a the considered software analysis,is also detected using an unoptimized product-based analysis (completeness). Notethat while th

A software product line is a set of software products that share a common set of features. Software product lines challenge traditional analysis techniques, such as type checking, testing, and formal veri cation, in their quest of ensuring correctness and reliability of software. Simply creating and analyzing all products of a product line is .