Automated Reasoning for Multi-step Feature Model Configuration Problems

Automated Reasoning for Multi-step Feature Model Configuration Problems Jules White, Brian Dougherty, and Doulas C. Schmidt Vanderbilt University, Nashville, TN USA Email:{jules, briand, schmidt}@dre.vanderbilt.edu David Benavides University of Seville, Seville, Spain Email:[email protected] Abstract The increasing complexity and cost of software-intensive systems has led developers to seek ways of increasing software reusability. One software reuse approachis to develop a Software Product-line (SPL), which is a reconfigurable software architecture that can be reused across projects. Creating configurations of the SPL that meets arbitrary requirements is hard. Existing research has focused on techniques that produce a configuration of the SPL in a single step. 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 CSP configuration problem CSPs can be derived automatically with a constraint solver. Third, we present empirical results demonstratingthat ourCSP-based technique can solve multi-step configuration problems involving hundreds of features in seconds. 1 Introduction The high-cost of developing distributed real-time and embedded (DRE) systems has pushed developers to find novel solutions to increase the reusability of software. One promising reuse approach is Software Product-lines (SPLs) [7], which are software architectures that are designed with built-in points of variability that can be altered so that the software can be more readily reused across projects. For example, an SPL for a car can be built with the ability to use multiple engine control software components so it can be adapted to cars with different engine types. Ensuring that a correct software product is produced from an SPL involves building models of the rules for configuring the points of variabilty. For example, an SPL configuration for a car cannot simultaneously employ two different engine control software components or the wrong component for the given engine type. A common technique for specifying SPL configuration rules is a feature model [12], which abstracts the components and points of variaiblity in a software product as features. Feature models are typically implemented as tree-like structures that specify how the components and points of variability affect one another. For example, the feature model of a car in Figure 1 can optionally include an Automated Driving Controller . If the car includes this feature it must also include the Collision Avoidance Breaking feature. Any arbitrary configuration can be checked against the feature model to determine if it is a complete and correct configuration of a software product. When an SPL is configured for a new set of requirements, developers must find a selection of the features from the feature model that (1) satisfy the requirements and (2) adhere to the rules in the feature model. This configuration process involvesreasoning overa complex set of constraints to meet an end goal. Various tools [2, 13, 1, 4, 5, 15] have been developed to help reduce the complexity of this process by automating parts of the feature selection process. Open problems. Some configuration problems require starting at an arbitrary state and deriving a new configuration that meets the target requirements. For instance, an automotive software designer using an SPL may start with no features selected and derive a selection of features for the automobile software to meet the needs of a new model year car. Often, however, constraints limit developers from directly transitioning from the starting state to the desired end configuration. For example, assume that a group of automotive SPL developers want to modify the configuration of an existing SPL car model to include automated driving capabilities, as shown in Figure 1. The developershave determined that the cost of adding all the new features will be 88 million dollars. The developers only have a annual development budget of 35 million dollars to reconfigure the SPL variant, however, which means that the developers cannot simply add all features in a single year. Management has also asked the developers to make continual progress on developing the car by adding new features to it every year. To manage these constraints, the developers must incrementally add the desired features over a series of steps, i.e., 11 Copyright held by the author/owner. Figure 1: A Configuration Problem Requiring Multiple Steps overseveral years the developerswill produce a series of intermediate configurations that leverage each other to reach the desired configuration. For example, they can develop a subset of the new features in the first year’s car configuration, add more of the remaining desired features in the second year, and add the rest of the desired features and reach the new configuration in the third year. This process of producing a series of intermediate configurations—i.e., aconfiguration path—is shown in Figure 2. We call this sequence of activities a multi-step configuration problem. A key challenge is that the developers cannot arbitrarily pick and choose features to add in a given year to meet the budget constraint. For example, developers will violate the feature model rules if they choose to add Parallel Parking in year 3 without Lateral Range Finder , which is required via a cross-tree constraint, as shown in Figure 2. Developers must therefore not only adhere to their constraints on the changes that can be produced in a given year (such as the maximum allowed annual development budget) but also ensure that the changes they choose create a valid configuration at the end of each year. The developers also cannot choose an intermediate configuration to transition through that will not function and hence cannot be sold. Further complicating the multi-step configuration problem is that developers may need to foresee tradeoffs that must be made along the way. For example, it is not possible to simultaneously add Collision Avoidance Braking and Enhanced Avoidance in the same year since their total development cost is 36 million dollars, as shown in Figure 2. Developers must therefore add Collision Avoidance Braking and Standard Avoidance one year (to simultaneously meet the budget constraint and the feature model constraints) and then remove the Standard Avoidance feature at a later step to add the desired Enhanced Avoidance feature. Prior work on configuration analysis and automation [13, 1, 4, 5] focused on creating one configuration that meets a specific set of requirements, i.e., they find a configurationin one step and assume that it is possible to directly transition to it. These techniques do not, however, support the need to split the configuration over multiple steps to adhere to a change constraint, such as the maximum development budget per year. A gap therefore exists in current techniques when developers need to reason about and automate configuration over multiple steps. Solution overview and contributions. To fill the gap in existing research, we have developed an automated method for deriving a set of configurations that meet a series of requirements over a span of configuration steps. We call our technique the MUlti-step Software Configuration prob- LEm solver (MUSCLE). MUSCLE transforms multi-step feature configuration problems into constraint satisfaction problems (CSPs) [10]. Once a CSP has been produced for the problem, MUSCLE uses a constraint solver (which is an automated tool for finding solutions to CSPs) to generate a series of configurations that meet the multi-step constraints. This paper provides the following contributions to the study of feature model configurationovera span of multiple steps: 1. We provide a formal model of multi-step configuration, 2. We show how the formal model of multi-step configuration can be mapped to a CSP, 3. We show how multi-step requirements, such as limits on the cost of feature changes between two successive configurations, can be specified using our CSP formulation of multi-step configuration, 4. We describe mechanisms for optimally deriving a set of configurations that meet the requirements and minimize or maximize a property of the configurations or configuration process, such as total configuration cost, 5. We show how multi-step optimizations can be performed, such as deriving the series of configurations that meet a set of end-goals in the fewest time steps, and Paper organization. The remainder of the paper is organized as follows: Section 2 summarizes the challenges of performing automated configuration reasoning over a sequence of steps; Section 3 describes a formal model of 12 Figure 2: Potential Configuration Paths multi-step configuration; Section 4 explains MUSCLE’s CSP-based automated multi-step configuration reasoning approach; Section 5 analyzes empirical results from experiments demonstrating the scalability of MUSCLE; Section 6 compares MUSCLE with related work; and Section 7 presents concluding remarks. 2 Challenges A multi-step configuration problem for an SPL involves transitioning from a starting configuration through a series of intermediate configurations to a configuration that meets a desired set of end state requirements. The solution space for producing a series of successive intermediate configurations to reach the desired end state can be represented as a directed graph, as shown in Figure 3(a). (a) A Graph of a Multi-step Configuration Problem (b) Optimization of Total Steps Figure 3: Multi-step Configuration Graphs Each successive series of points represents potential configurations of the feature model at a given step. For example, the configurations B0...Birepresent the intermediate configurations that can be reached in one step from the starting configuration. In this section we use this graph formulation of the problem’s solution space to showcase the challenges of finding valid solutions. 2.1 Challenge 1: Graph Complexity A critical challenge to developers attempting to derive solutions to multi-step configuration problems manually or to use a graph algorithm is that there are an exponential number of potential intermediate configurations and paths that could be used to reach the desired end state. In the worst case, at any given intermediate step, there can be O(2n)points (where nis the number of features in the feature model). In the worst case, therefore, there are 2npoten- tial subsets of the features in the feature model that could form a configuration. Moreover, for a multi-step configuration problem over Ktime steps, there are O(K2n)possible intermediate points. Further compounding this problem is that for any intermediate configuration at step T, there are in the worst case 2n−1 points at step T+1 that could be reached from it by adding or removing features to its feature selection. The intermediate configurations that do not precede the end point will therefore have 2n−1 outgoing edges. Section 4 discusses how MUSCLE uses CSP-based automation to eliminate the need for developers to manually find solutions to these multi-step configuration problems, which reduces configuration time and cost. 2.2 Challenge 2: Point ConfigurationConstraints Although there are a substantial number of potential intermediate configurations, many of these configurations will not meet developer requirements. For example, many of the K2narbitrary subsets of feature selections will represent configurations that do not adhere to the feature model 13 constraints. Moreover, other external constraints, such as safety constraints requiring a specific feature to be selected at all times, may not be met. We term these constraints on the allowed configurations at a given step point configuration constraints. Point configuration constraints eliminate many potential configuration paths. These constraints may create small additional restrictions, such as that a particular feature must always be selected. Complex step-based constraints may also be present, such as a particular automotive feature becomes unavailable after a specific time step (year) because the supplier discontinues it. Finally, a multi-step configuration problem may not dictate an exact starting and ending configuration, but merely a series of point configuration constraints that must hold for the start and end points of the configuration path. The myriad of possible point configuration constraints significantly increases the challenge of finding a valid configuration path for a multi-step configuration problem. Section 4.3 describes how MUSCLE models these constraints using a CSP, which enables a CSP solver to automatically derive solutions that adhere to these constraints and thus reduce tedious and error-prone manual configuration. 2.3 Challenge 3: Configuration Change/Edge Constraints The automotive example in Figure 1 requires that developers adding new features spend no more than 35 million dollars in one year. The cost of adding/removing features can be captured as the length or weight of the edges connecting two transitions. For example, to transition directly from the starting configuration to the desired end configuration requires 88 million dollars and has an edge weight of 88.Developers must not only find a path that reaches the desired end state without violating the point configuration constraints in Section 2.2, but also ensure that any constraints on the edges connecting successive configurations are met. Transitioning directly from the start configuration to end configuration would violate the edge constraint of the 35 million dollar yearly developmentbudget. Edge constraints further reduce the number of valid paths and add complexity to the problem. Section 4.4 shows how these edge restrictions can be encoded as constraints on MUSCLE’s CSP variables to plan configuration paths that adhere to development budgets, which is hard to determine manually. 2.4 Challenge 4: Configuration Path Optimization There may often be multiple correct configuration paths that reach the desired end point. In these cases, developers would like to optimize the path chosen, for example to minimize total cost (the sum of the edge weights). In other cases, it may be more imperative to meet the desired end point constraints in as few time steps as possible. For example, in Figure 3(b), developers have an initial development budget of 35 million dollars and then a subsequent yearly budget of 50 million dollars. Although the cost of the path through intermediate configurations Biand Ciis cheaper (70 million), developers may prefer to pass through B0and C0since they will already have a configuration that meets the end goals at C0. Developers must therefore not only contend with numerous multi-step constraints, but must also perform complex optimizations on the properties of the configuration path. Section 4.5 shows how optimization can be performed on MUSCLE’s CSP formulation of multi-step configuration to allow developers to find the fastest and most cost-effective means of achieving a configuration goal. 3 A Formal Definition of Multi-step Configuration This section presents a formal model of multi-step configuration. In its most general form, multi-step configuration involves finding a sequence of at most Kconfigurations that satisfy a series of point configuration constraints and edge constraints. This definition requires the start and end configurations meet a set of point constraints, but does not dictate that there be a single valid starting and ending configuration. General formal model. We define a multistep configuration problem using the 6-tuple Msc =< E,PC,∆(FT,FU),K,FStart,Fend >, where: •Eis the set of edge constraints, such as the maximum development cost per year for features, •PC is the set of point configuration constraints that must be met at each step, such as the feature model rules that developers may require to be adhered to across all steps (feature model rules do not have to be enforced at each time step), •∆(FT,FU)is a function that calculates the change cost or edge weight of moving from a configuration FTat step Tto a configuration FUat step U, •Kis the maximum number of steps in the configuration problem, •FStart is a set of configuration constraints on the starting configuration, such as a list of features that must initially be selected, •Fend is a set of configuration constraints on the final configuration, such as a list of features that must be selected or maximum cost of the final configuration. We define a configuration path from step Tover Ksteps as a K-tuple P=<FT,FT+1,...FT+K−1> 14 , where the configuration at step Tis denoted by FT. Each configuration,FT, denotes the set of selected features at step T.Section 4 shows how this formal model can be specified as a CSP. Although we use CSPs for reasoning on the formal model, we could also use SAT solvers, propositional logic, or other techniques to reason about this model. The formal model is thus applicable to a wide range of reasoning approaches. 3.1 Constraint and Function Examples We now describe how the formal model presented above can be used to model typical SPL configuration constraints. We show how common configuration needs, such as the selection of specific features or budgetary constraints, can be mapped to portions of our multi-step configuration problem tuple. Edge constraint examples. The set of edge constraints Ecan include numerous types of constraints on the transition from one configuration to another. For example, a constraint e1∈Emay dictate that the maximum weight of any edge between successive configurationsin FT,FT+1∈P have at most weight 35 (for the automotive problem from Figure 1): ∀T∈(0..K−1),∆(FT,FT+1)≤35 Edge constraints may also vary depending on the step, for example a developmentbudget may start at $35 million and may expand as a function of the step: ∀T∈(0..K−1),∆(FT,FT+1)≤35 1−(.01∗T) Edge constraints may also be attached to specific time steps: ∀T∈(0..4,6..K−1),∆(FT,FT+1)≤35 1−(.01∗T) ∆(F5,F6)≤40 Point configuration constraint examples. The point configuration constraints specify properties that must hold for the feature selection at a given step. Both the starting and ending points for the multi-step configuration problem are defined as point configuration constraints on the first and last steps. For example, we want to start at a specific configuration Fstart and reach another configuration Fend: (F0=Fstart)∧(FK=Fend) Another general constraint pc1∈PC could require that for any step T, the feature selection FTsatisfies the feature model constraints Fc: ∀T∈(0..K−1),FT⇒Fc Developers could also require that a specific set of features Fstart, such as safety critical braking features, be selected at all times: ∀T∈(0..K−1),Fstart ⊂FT Change calculation function examples. The function ∆(FT,FU)calculates the cost of changing from one configuration to another configuration at a different step. For example, the following change calculation function computes the cost of changing from one configuration to another: Fadded =FU−FT ∆(FT,FU) = ∑fi∗ci,fi∈Fadded where fiis the ith added feature and ciis the price of adding that feature. 4 A CSP Model of Multi-step Configuration This section describes how MUSCLE uses CSPs to automatically derive solutions to multi-step configuration problems. To address the challenges outlined in Section 2 we showthat derivinga configurationpath for a multi-step configuration problem can be modeled as a CSP [10] using the formal framework from Section 3. After a CSP formulation of a multi-step configurationproblemis built, MUSCLE can use a CSP solver to automatically derive a valid configuration path on behalf of the developer. Automating the configuration path derivation helps reduce the complexity from Challenge 1 in Section 2.1. Moreover, the CSP solver can be used to perform optimizations that would be extremely hard to achieve manually. Prior work on automated feature model configuration [3, 15, 16] has yielded a framework for representing feature models and configuration problems as CSPs. This section shows how a new formulation of feature models and configuration problems can be developed that (1) incorporates multiple steps, (2) allows a constraint solver to derive a configuration path for evolving a feature selection over multiple intermediate steps to meet an end goal, (3) permits the specification of intermediate configuration constraints, (4) allows for change/edge constraints on the transition between feature selections, and (5) can be leveraged to optimize configuration path properties, such as path length or cost. 4.1 CSP Automated Configuration Background A CSP is a set of variables and a set of constraints over the variables. For example, (X−Y>0)∧(X<10)is a simple CSP involving the integer variables Xand Y. A constraint solver is an automated tool that takes a CSP as input and produces a labeling or set of values for the variables that simultaneously satisfies all of the constraints. The solver can also be used to find a labeling of the variables that maximizes or minimizes a function of the variables e.g. maximize X+Yyields X=9,Y=8. A feature model can be modeled as a CSP through a series of integer variables F, where the variable fi∈Fcorresponds to the ith feature in the feature model. A configuration is defined as a series of values for these variables 15 Figure 4: Mapping Feature Model Rules to a CSP such that fi=1 implies that the ith feature is selected in the configuration. If the ith feature is not selected, fi=0. Configuration rules from the feature model are represented as constraints over the variables in F, as shown in Figure 4. More details on building a CSP from a feature model are described in [15, 3]. 4.2 Introducing Multiple Steps into the CSP The goal of automated configuration over multiple-steps is to find a configuration path that permutes a given starting configurationthrougha sequence of intermediate configurations to reach a desired end state. For example, the configuration paths in Figure 2 capture sequential modifications to the car configuration, shown in Figure 1, that will incorporate high-end features into the base automobile model. To reason about a configuration path over a span of steps, we first introduce a notion of a configuration step into MUSCLE’s CSP model of configuration. CSP model of configuration steps. To introduce configuration steps into MUSCLE’s configuration CSP, we modify the configuration CSP formulation outlined in Section 4.1. We no longer use a variable fito refer to whether or not the ith feature is selected or deselected. Instead, we refer to the selection state of each feature at a specific step Twith the variable fiT ,i.e., if the ith feature is selected at step T,fiT =1. We refer to an entire configuration at a specific step as a set of values for these variables, fiT ∈FT. A solution to the CSP is configuration path defined by a labeling of all of the variables in the K-tuple: <FT,FT+1...FT+K−1>. For example, if the ABS feature (denoted fa) is not selected at step Tand is selected at step T+1, then: faT =0 faT+1=1 Figure 5 shows a visualization of how the fiT ∈FTvariables map to feature selections. 4.3 CSP Point Configuration Constraints To address Challenge 2 from Section 2.2, the point configuration constraints (which are the constraints that define Figure 5: An Example of Variables Representing Feature Selection State at Specific Steps what constitutes a valid intermediate configuration) can be modeledas constraints on the variables fiT ∈FT. Each point configuration constraint has a specific set of steps, Tpc, during which it must be met, i.e., the constraint must only evaluate to true on the precise steps for which it is in effect. For example, a simple constraint would be that the 2nd and 3rd configurations must have the feature f1selected. The set of steps for which this constraint must hold would be Tpc ={2,3}. CSP model of point configuration constraints. A CSP point configuration constraint, pci∈PC, requires that: ∀T∈Tpc,FT⇒pci Arbitrary point configuration constraints can be built using this model to restrict the valid configurationsthat are passed through by the configuration path. This flexible point configuration constraint mechanism allows developers to specify and automatically find solutions to problems involving the constraints from Challenge 2 in Section 2.2. CSP point configuration constraint example. Assume that we want to find values for FT...FT+Ksuch that we never violate any of the feature model constraints at any step. Further assume that the constraints in the feature modelremain static overthe Ksteps (feature modelchanges over multiple steps can also be modeled). If the jth feature is a mandatorychild of the ith feature, we add the constraint: ∀T∈(0...K),(fiT =1)⇔(FjT =1) That is, we require that at any step T, if the ith feature (FiT ) is selected, the jth feature (fjT ) is also selected. Furthermore, at any step T, if the jth feature (FjT) is selected, the ith feature (fiT ) is also selected. Other example point configuration constraints can be mapped to the CSP as shown in Figure 6(a) and Figure 6(b). 16 (a) Point Configuration Constraints for Feature Model Structure (b) Point Configuration Constraint for Feature Selection Figure 6: Point Configuration Constraint Examples 4.4 CSP Edge/Change Constraints Challenge 3 from Section 2.3 described how developers must be able to specify and adhere to constraints on the differencebetweentwoconfigurationsat differentsteps. These edge/change constraints can be modeled in the CSP as constraints over the variables in two configurations FTand FU. By extendingthe CSP techniqueswe have developedin past work [16], we can specifically capture which features are selected or deselected between any two steps and constrain these changes via budget or other restrictions. CSP model of edge/change constraints. To capturedifferences between feature selections between steps TandU, we create two new sets of variables STU and DTU. These variables have the following constraints applied to them: ∀siTU ∈STU,(siTU =1)⇔(fiT =0)∧(fiU =1) ∀diTU ∈DTU,(diTU =1)⇔(fiT =1)∧(fiU =0) If a feature is selected at time step Tand not at time stepU, then diTU is equal to 1. Similarly, if a feature is not selected at step Tand selected at step U,siTU is equal to 1. An edge edge(T,U)between the configurations at steps Tand Uis defined as a 2-tuple: edge(T,U) =<DTU,STU > An edge is thus defined by the features deselected and selected to reach configurationFUfrom configuration FT. The weight of the edge weight(edge(T,U)) can then be calculated as a function of the edge tuple. For example, if the ith feature costs cito add or remove then weight(edge(T,U)) = n ∑ i=0siTU ∗ci+ n ∑ i=0diTU ∗ci CSP edge/change constraint example. The cost of including a particular feature may change over time. For example, the cost of adding a GPS guidance system to a car does not remain fixed, but instead typically decreases from one year to the next as GPS technology is commoditized. We can model and account for these changes in MUSCLE’s CSP formulation and constrain the configuration path so that it adds features at times when they are sufficiently cheap. We will define an edge constraint that takes into account changing feature modification costs and limits the change in cost between two successive configurationsto $35 million dollars. We assume we can calculate that the price of including the ith feature so that it is included in the feature selection at step Tby the function: Cost(i,T) = ci T+1 We can then define the cost of adding features to a configuration as: weight(edge(T,T+1)) = n ∑ i=1 (siTT+1∗Cost(i,T+1)) We can now limit the cost of any two successive configurations via the edge constraint: ∀T∈(0..K−1),weight(edge(T,T+1)) ≤35 4.5 Multi-step Configuration Optimization Challenge 4 from Section 2.4 showed that optimizing the configuration path is an important issue. CSP solvers can automatically perform optimizationwhile finding values for the variables in a CSP (though it may be impractical timewise for some problems). We can define goal functions over the CSP variablesto leveragethese optimizationcapabilities and address Challenge 4. In some cases, developers may not want to just find any configuration path that ends in the desired state. Instead, they may want a path that produces a configuration that meets the end goals as early as possible. For example, in the automotiveproblem from Section 1 developersmay want to find a configuration path that meets their constraints and includes the high-end features in the base model in fewer than five years. CSP model of path length. To support path length optimization, we define a measure of the number of steps needed to reach a valid end state. We must therefore determine if the constraints on the final configurationFend (which is the goal state) are met by some configuration prior to the 17 last configuration (FTwhere T<K−1). If we meet the final state constraintssooner than the final configuration,then we have found a configuration process that requires fewer configuration steps. To track whether or not a configuration has met the constraints on the ending configuration Fend, we create a series of variableswT∈Wto represent whether or not the configuration FT∈Psatisfies Fend. For each configuration, FT∈P, if Fend is satisifed: (FT⇒Fend)⇒(wT=1) i.e., if at any step (up to and including the last step) we satisfy the end state requirements, set wTequal to 1. We also require that after one step has reached a correct ending configuration, the remaining steps also keep the correct configuration and do not alter it: (wT=1)⇒(wT+1=1) (wT=1)⇒(∑n i=0siTT+1+∑n i=0diTT+1=0) Optimizationexamples. We can optimize to find the shortest configuration path to reach the goals over K steps by asking the solver to maximize: K−1 ∑ T=0 wT The reason that maximizing this sum will minimize the number of steps taken to reach the desired end state is that the sooner the state is reached, the more steps wTwill equal 1. The most straightforward optimization functions are defined as functions of the variables in the configuration path P. For example, we can instruct the solver to minimize the cost of the ending configuration. Assume that the cost of ith feature at step Kis denoted by the variable ci∈CK, minimize CK, where: CK= n ∑ i=0 fi∗ci Other optimizations can be performed on the weights of the edges. For example, to find the configuration path with the lowest development cost, where the development cost is the edge weight the goal is to minimize: K−1 ∑ T=0weight(edge(T,T+1)) 4.6 A Complete Multi-step CSP Example We now provide a complete mapping of the automotive configuration problem in Section 1 to MUSCLE’s multistep CSP. For this problem, the automotive developers want to include the high-end features into the base model over the course of five years (K=5). We first create a series of configuration variables to represent the feature selection at the end of each of the five years: Figure 7: Point Configuration Constraints for the Automobile Example F0= (f00,f10,... f80) F1= (f00,f11,... f81) ... F4= (f00,f14,... f84) The mappings of the automobile features from Figure 1 to CSP variables can be seen in Figure 7. A configuration path is defined by a set of feature selections for each of the five years: P=<F0,F1,...F4> The point constraint, pc0∈PC, ensures that the feature model constraints are met by each year’s configuration, as shown in Figure 7. We must also specify the point configuration constraint for the starting configuration: Fstart = (f00 =1)∧(f10 =1)∧(f20 =0)∧(f30 =0) ∧(f40 =0)∧(f50 =0)∧(f60 =0)∧f70 =0) ∧(f80 =0) Moreover, we must ensure that the high-end features are included in the last configuration: Fend = (f74 =0)∧(f04 =1)∧(f14 =1)∧(f24 =1)∧ (f34 =1)∧(f44 =1)∧(f54 =1)∧(f64 =1) ∧(f84 =1) Our complete set of point configuration constraints is PC = (pc0). Finally, we must specify how the change cost between two configurations is calculated and enforce the edge constraint that at most $35 million dollars is spent per year. ∆(FT,FT+1) = 20s2TT+1+14s3TT+1+19s4TT+1+8s5TT+1 +11s6TT+1+1s7TT+1+16s8TT+1 E= (∀T∈(0..3),∆(FT,FT+1)≤35) Given this CSP formulation, we can use a constraint solver to automatically derive a solution to the multi-step automotive configuration problem described in Section 1. 18 5 Results As described in Section 2.1, configuring an SPL over multiple steps is a highly combinatorial problem. An automated multi-step SPL configuration technique should be able to scale to hundredsof features and multiple steps. This section presents empirical results from experiments we performed to determine the scalability of MUSCLE. Our experiments were performed with an implementation of the MUSCLE provided by the open-source Ascent Design Studio (available from code.google.com/ p/ascent-design-studio ). The Ascent Design Studio’s implementation of MUSCLE is built using the Java Choco open-source CSP solver (available from choco. sourceforge.net ). The experiments were performed on a computer with an Intel Core DUO 2.4GHZ CPU, 2 gigabytes of memory, Windows XP, and a version 1.6 Java Virtual Machine (JVM). The JVM was run in server mode using a heap size of 40 megabytes (-Xms40m) and a maximum memory size of 256 megabytes (-Xmx256m). To test the scalability of MUSCLE we needed 1,000s of feature models to test with, which posed a problem since there are not many large-scale feature models available to researchers. To solve this problem, we used a random feature model generator developed in prior work [16]. The feature model generator and code for these experiments is available in open-sourceform along with the Ascent Design Studio. We used a maximum branching factor of 5 children per feature and a maximum of 1/3 of the features were in an XOR group.1 We measured the solving time of MUSCLE by generating random multi-step configuration problems and solving for configuration paths that involved larger and larger numbers of steps. The problems were created by generating a semi-random feature model with 500 features as well as starting and ending configurations. MUSCLE was used to derive a configuration path between the two configurations. Our experiments were performed with large-scale configurationpaths, which were produced by forcing the solver to find a configuration path that involved switching between two children of the root feature that were involved in an XOR group. For a feature model with 500 features configured over 3 steps, the worst case solving time we observed was roughly3 seconds. The worst case solving time for feature models configured over 10 steps was 16s. These initial results indicate that the technique should be sufficiently fast for feature models with hundreds of features. 6 Related Work This section compares MUSCLE with related work. 1XOR feature groups are features that require the set of their selected children to satisfy a cardinality constraint (the constraint is 1..1 for XOR). Automated Single-step Configuration: Several singlestep feature model configuration and validation techniques have been proposed [2, 13, 1, 4, 5, 15]. These techniques use CSPs and propositional logic to derive feature model configurations in a single stage as well as assure their validity. These techniques help address the high complexity of finding a valid feature selection for a feature model that meets a set of intricate constraints. While these techniques are useful for the derivation and validation of configurations in a single step, they do not consider feature configuration over the course of multiple steps. In scenarios, such as the automotive example from Section 1, the ability to reason about configuration over multiple steps is critical. MUSCLE provides this automated reasoning across multiple steps. Moreover, MUSCLE can also be used for single-step configurations since it is a special case of multi-step configurationwhere there is only one step K=1. Staged Configuration: Czarnecki et al. [8] describe a method for using staged feature selection to achieve a final target configuration. This multi-stage selection considers cases in which the selection of features in a previous stage impacts the validitiy of later stage feature selections. Our technique also examines the production of a feature model configuration over multiple configuration steps. MUSCLE is complementary to Czarnecki et al.’s work and provides a general formal framework that can be used to perform automated reasoning on staged configuration processes. Moreover, MUSCLE can also be used to reason about other multi-step configuration processes that do not fit into the staged configuration model, such as the the example from Section 1 where each step must reach a valid configuration. Staged configuration can be modeled as a special instance of multi-step configuration. Specifically, staged configuration is an instance of a multi-step configuration problem where: E=/ 0,Fstart =/ 0,Fend = (FK−1⇒Fc),Kis set to the number of stages, ∆(FT,FU)is not defined, and Fc is the set of feature model constraints. That is, there are no limitations on the changes that can be made between successive configurations, the starting configuration has no features selected, andthe endingconfigurationyields a valid feature model configuration. The staged configuration definition can be refined to guarantee that successive stages only add features: ∀T∈(0..K−1),FT⊂FT+1. Classen et al. [6] have investigated creating a formal semantics for staged configuration. Furthermore, they have provided a definition of a configuration path through a series of stages for a feature model. Whereas Classen et al. have focused on configuration paths that continually reduce variability, MUSCLE is a formal model that allows for both the reduction and introduction of variability in the configuration process. Moreover, MUSCLE allows for complete 19