Marco Autili
email: marco.autili@univaq.it

Paola Inverardi
email: paola.inverardi@univaq.it

Massimo Tivoli
email: massimo.tivoli@univaq.it

Automated Integration of Service-Oriented Software Systems

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In the near future we will be increasingly surrounded by a virtually infinite number of software services that can be composed to build new added value applications in the Digital Space. According to John Musser, founder of Pro-grammableWeb 1 , the production of Application Programming Interfaces (APIs) grows exponentially and some companies are accounting for billions of dollars in revenue per year via API links to their services. Moreover, the evolution of today Internet is expected to lead to an ultra large number of available services, hence increasing their number to billions of services in the near future. This situation radically changes the way software will be produced and used: (i) software is increasingly produced according to specific goals and by integrating existing software; (ii) the focus of software production is on integration of third party and typically black-box software, that is only provided with an interface that exposes the available functionalities but does not provide the assumed interaction protocol. The first characteristic implies a goal oriented, opportunistic use of the software being integrated, i.e., the producer will only use a subset of the available functionalities, some of which may not even be (completely) known. The second one implies the need to (a) extract suitable interaction models from discoverable and accessible pieces of software, which are made available as services in the digital space, and (b) devise appropriate integration means (e.g., architectures, connectors, mediators, integration patterns) that ease the composition of existing services so to achieve the goal.

The aim of the proposed research is to provide automatic support to the production of software systems by integrating existing software services according to a specified goal.

Our proposal builds on the model-based software production paradigm while accounting for the inherent incompleteness of information about existing software. This evidence suggests the use of an experimental approach, as opposed to a creationistic one, to the production of software. Software development has been so far biased towards a creationist view: a producer is the owner of the artefact and, if needed, she can declaratively supply any needed piece of information (interfaces, behaviours, contracts, etc.). The digital space promotes a different experimental view: the knowledge of a software artefact is limited to what can be observed of it. The more powerful and extensive the observations are, the deeper the knowledge will be; the knowledge will always remain partial, though. Indeed, there is a theoretical barrier that limits, in general, the power and the extent of observations. Beyond automation, a further big challenge underlying this scenario is therefore to live up with the fact that this immense software resources availability corresponds to a lack of knowledge about the software, notably on its behaviour. A software producer will know less and less the precise behaviour of a third-party software service, nevertheless she will try to use it to build her own application. This very same problem recognized in the software engineering domain [START_REF] Garlan | Software engineering in an uncertain world[END_REF] is faced in many other computer science domains, e.g., exploratory search [START_REF] White | Exploratory Search: Beyond the Query-Response Paradigm[END_REF] and search computing [START_REF] Ceri | Search computing challenges and directions[END_REF].

In order to face this problem and provide a producer with a supporting framework to realize software applications via automated integration, we envision a process that implements a radically new perspective. First results can be found in [START_REF] Inverardi | Producing software by integration: Challenges and research directions (keynote)[END_REF]. This process builds around elicit and integrate phases.

From now on, when referring to models of services we always mean models of the interaction protocols of the services, that is models of the sequences of actions/messages exchange that need to be performed in order to consume the service, e.g., "login" and "get authorized", before "access bank account".

The elicit phase automatically produces an interaction protocol model for each service that has been discovered as a candidate to provide a desired functionality with respect to a specified system goal. This model is complete enough to allow the service to be integrated with others in order to satisfy the goal.

The integrate phase assists the producer in creating the appropriate integration means to compose the observed services together in order to produce a system that satisfies the goal.

In this paper we present a specific instance of the above reuse-based elicitintegrate development process, which is suitable for service-oriented systems.

The paper is organized as follows. Section 2 describes an instance of the elicit phase, which is suitable for the automatic elicitation of the interaction protocol of a Web Service. Section 3 discusses in detail an instance of the integrate phase, which allows the producer to automatically enforce the realization of a specific form of service composition, namely a choreography. Thus, this instance is suitable for the automatic production of choreography-based service-oriented systems. Section 4 discusses related work in the domains of behavioral model elicitation techniques and of service choreography development. Section 5 discusses final remarks and future research directions.

The elicit phase

Given a software service S that has been discovered as a candidate to provide a desired functionality with respect to a system goal G, elicitation techniques must be defined to produce interaction protocol models that are complete enough to allow the service to be integrated with others in order to satisfy G. This means that we admit partial models of the service interaction protocols. For the integration phases to be automated, a goal G specification is a machine-readable model achieved by the producer by operationalizing the needs and preferences of the user [START_REF] Van Lamsweerde | Requirements Engineering -From System Goals to UML Models to Software Specifications[END_REF]. Referring to Figure 1, a concrete example of a goal specification can be found in [START_REF] Autili | Automated synthesis of service choreographies[END_REF], where domain expert and user goals are operationalized into a BPMN2 2 choreography specification, after being transformed into a CTT (ConcurTask-Trees) intermediate model [START_REF] Paternó | Preventing user errors by systematic analysis of deviations from the system task model[END_REF]. The elicit phase is composed of two steps, namely observation and construction [START_REF] Inverardi | Producing software by integration: Challenges and research directions (keynote)[END_REF]. For each service to be integrated, the observation step is driven by G and collects a set of observation data. We focus on observations devoted to the identification of a set of functional behaviours, e.g., the SOAP response to a Web-Service (WS) operation invocation. Construction takes as input the set of observation data and produces a (partial) model of the observed service. This model represents the observed behaviours enriched with inferred information that is relevant for achieving G. For instance, as done in [START_REF] Bertolino | Automatic synthesis of behavior protocols for composable web-services[END_REF], the collection of the SOAP responses to WS operation invocations, enriched with the inferred partial order of the invocations, can be represented as an automaton that models the interaction protocol of the observed WS. Note that, as it is shown in Section 3, having a partial model of the interaction protocol, for each observed WS to be integrated, is sufficient to automatically synthesize the code of proxies that allow for integrating the WSs so to realize the specified BPMN2 choreography. An important aspect is that the elicit phase produces models that, although partial, are still good enough to achieve G. Goal driven elicitation can be very effective, e.g., as observed on the Amazon E-commerce WS (AEWS) where we apply the approach in [START_REF] Bertolino | Automatic synthesis of behavior protocols for composable web-services[END_REF] to elicit the AEWS interaction protocol. The experiment considered a goal-independent elicitation versus a goaldriven one [START_REF] Autili | Modelland: Where do models come from? In Models@run.time[END_REF]. Starting from the AEWS WSDL consisting of 85 XML schema type definitions and 23 WSDL operation definitions, the goal independent elicitation resulted in an interaction protocol made of 24 states and 288 transitions by using 10 6 test cases, each executed in 10 -2 secs, e.g., few hours of testing. By considering a goal specification that the user wished to "develop a client for cart management only", the interaction protocol computed was made of 6 state and 21 transitions only. The goal driven elicitation required the generation and execution of 10 5 test cases, e.g., few seconds of testing.

As it is shown in Section 3, having a partial model of the interaction protocol, for each observed WS to be integrated, is sufficient to automatically synthesize the code of additional software entities that, proxyfing the WSs, allow for integrating them so to realize the specified BPMN2 choreography. An important aspect is that the elicit phase produces models that, although partial, are still good enough to achieve G.

Goal driven elicitation can be very effective, e.g., as observed on the Amazon E-commerce WS (AEWS) where we apply the approach in [START_REF] Bertolino | Automatic synthesis of behavior protocols for composable web-services[END_REF] to elicit the AEWS interaction protocol. The experiment considered a goal independent elicitation versus a goal driven one [START_REF] Autili | Modelland: Where do models come from? In Models@run.time[END_REF]. Starting from the AEWS WSDL consisting of 85 XML schema type definitions and 23 WSDL operation definitions, the goal independent elicitation resulted in an interaction protocol made of 24 states and 288 transitions by using 10 6 test cases, each executed in 10 -2 secs, e.g., few hours of testing. By considering a goal specification that the user wished to "develop a client for cart management only", the interaction protocol computed was made of 6 state and 21 transitions only. The goal driven elicitation required the generation and execution of 10 5 test cases, e.g., few seconds of testing.

The following section summarizes the elicit technique that we describe in detail in [START_REF] Bertolino | Automatic synthesis of behavior protocols for composable web-services[END_REF]. It represents a specific realization of the elicit phase, which is suitable for producing the interaction protocol of a WS.

StrawBerry: automated synthesis of WS interaction protocols

By taking as input a syntactical description of the WS signature, expressed by means of the WSDL notation, StrawBerry [START_REF] Bertolino | Automatic synthesis of behavior protocols for composable web-services[END_REF] derives in an automated way a partial ordering relation among the invocations of the different WSDL operations. This partial ordering relation is represented as an automaton that we call Behavior Protocol automaton. It models the interaction protocol that a client has to follow in order to correctly interact with the WS. This automaton also explicitly models the information that has to be passed to the WS operations. StrawBerry is a black-box and extra-procedural method. It is black-box since it takes into account only the WSDL of the WS. It is extra-procedural since it focuses on synthesizing a model of the behavior that is assumed when interacting with the WS from outside, as opposed to intra-procedural methods that synthesize a model of the implementation logic of the single WS operations [START_REF] Lorenzoli | Automatic generation of software behavioral models[END_REF][START_REF] Wasylkowski | Detecting object usage anomalies[END_REF].

Figure 2 graphically represents StrawBerry as a process that is split in five main activities that realize its observation and construction phases. Observation: the observation phase is in turn organized in two sub-phases. The first sub-phase exploits the WSDL of the WS, and performs data type analysis. The Dependencies Elicitation activity elicits data dependencies between the I/O parameters of the operations defined in the WSDL. A dependency is recorded whenever the type of the output of an operation (called source) matches with the type of the input of another operation (called sink). The match is syntactic. The elicited set of I/O dependencies (Input/Output Dependencies in Figure 2) may be optimized under some heuristics [START_REF] Bertolino | Automatic synthesis of behavior protocols for composable web-services[END_REF]. It is used for constructing a dataflow model (Saturated Dependencies Automaton Synthesis activity and Saturated Dependencies Automaton artifact) where each node stores data dependencies that concern the output parameters of a specific operation and directed arcs are used to model syntactic matches between output parameters of an operation and input parameters of another operation. This model is completed by applying a saturation rule. This rule adds new dependencies that model the possibility for a client to invoke a WS operation by directly providing its input parameters.

The second sub-phase validates the dependencies automaton through testing against the WS to verify conformance (Dependencies Automaton Refinement Through Testing activity). The testing phase takes as input the SOAP messages produced by the Test-cases Generation activity. The latter, driven by coverage criteria, automatically derives a suite of test cases (i.e., SOAP envelop messages) for the operations to be tested, according to the WSDL of the WS. Tests are generated from the WSDL and aim at validating whether the synthesized automaton is a correct abstraction of the service implementation. Testing is used to refine the syntactic dependencies by discovering those that are semantically wrong. By construction, the inferred set of dependencies is syntactically correct. However, it might not be correct semantically since it may contain false positives. The testing activity is organized into three steps. StrawBerry runs positive tests in the first step and negative tests in the second step. Positive test cases reproduce the elicited data dependencies and are used to reject fake dependencies: if a positive test invocation returns an error answer, StrawBerry concludes that the tested dependency does not exist. Negative test cases are instead used to confirm uncertain dependencies: StrawBerry provides in input to the sink operation a random test case of the expected type. If this test invocation returns an error answer, then StrawBerry concludes that the WS was indeed expecting as input the output produced by the source operation, and it confirms the hypothesized dependency as certain. If uncertain dependencies remain after the two steps, StrawBerry resolves the uncertainty by assuming that the hypothesized dependencies do not exist.

Construction: the construction phase consists in a synthesis stage which aims at transforming the validated dependency automaton (a data-flow model) into an automaton defining the behavior protocol (a control-flow model), see the Behavior Protocol Synthesis activity in Figure 2. This automaton explicitly models also the data that has to be passed to the WS operations. More precisely, the states of the behavior protocol automaton are WS execution states and the transitions, labeled with operation names plus I/O data, model possible operation invocations from the client of the WS.

The integrate phase

The integrate phase assists the producer in creating the appropriate integration means to compose the observed services together in order to produce a system that satisfies G. Multiple models may exist for each service (e.g., behavioural, interfaces, stochastic or Bayesian), each of them representing a view of the interaction protocol. Model transformation techniques ensure coherence and consistency among the different views, hence providing a systematic support to model interoperability [START_REF] Di Ruscio | Modeldriven techniques to enhance architectural languages interoperability[END_REF][START_REF] Hilliard | On the composition and reuse of viewpoints across architecture frameworks[END_REF]. Model and code synthesis techniques produce an Integration Architecture (IA), including the the corresponding code for the actual integration, out of the elicited models by suitably instantiating architectural styles [START_REF] Taylor | Software Architecture: Foundations, Theory, and Practice[END_REF] and integration patterns [START_REF] Hohpe | Enterprise Integration Patterns: Designing, Building, and Deploying Messaging Solutions[END_REF]. If needed, extra integration logic can be synthesized as connectors, coordinators, mediators and adapters [START_REF] Autili | Automated synthesis of service choreographies[END_REF][START_REF] Inverardi | Application-layer connector synthesis[END_REF][START_REF] Inverardi | Automatic synthesis of modular connectors via composition of protocol mediation patterns[END_REF][START_REF] Mateescu | Adaptation of service protocols using process algebra and on-the-fly reduction techniques[END_REF] to guarantee correctness of the IA with respect to G.

Continuing the example introduced above, Figure 3 shows a possible concrete instance of the Integrate phase [START_REF] Autili | Automated synthesis of service choreographies[END_REF][START_REF] Autili | Choreosynt: enforcing choreography realizability in the future internet[END_REF]. Here, the elicit phase has produced the interaction protocol of each participant service in the choreography specified by G (AEWS included). Starting from G and the elicited models, the Integrate phase synthesizes a set of software coordinators. The synthesis exploits model transformations implemented by means of the Atlas Transformation Language (ATL3 ). The developed ATL transformations consist of a number of rules each devoted to the management of specific BPMN2 Choreography Diagram modelling constructs. Coordinators are implemented in Java and their deployment descriptors are codified in XML. By instantiating a fully distributed architectural style, coordinators are interposed among the participant services that need to be coordinated. By exploiting a request/response delegation pattern, coordinators proxify the services and coordinate their interaction in a way that the resulting collaboration realizes G. Next section briefly describes the integration synthesis techniques we have implemented in the CHOReOSynt tool. More details can be found in [START_REF] Autili | Automated synthesis of service choreographies[END_REF][START_REF] Autili | Choreosynt: enforcing choreography realizability in the future internet[END_REF].

CHOReOSynt: automated synthesis of service choreographies

From the BPMN2 specification of a choreography (i.e., the goal G), CHORe-OSynt allows for deriving the coordinators, hereafter called Coordination Delegates (CD). CHOReOSynt offers bespoke functionalities to:

start the synthesis process giving as input a BPMN 2.0 Choreography Diagram; transform the BPMN2 Choreography Diagram into an intermediate automata-based model, which is amenable to automated reasoning; derive a set of Coordination Models containing information that serve to coordinate the services involved in the choreography in a distributed way; extract the participants of the choreography and project the choreography on their behavioral role; simulate the behavioral role of the participants in the choreography against the interaction protocol of the services discovered by the service discovery; generate the Coordination Delegate artefacts and the so called "ChorSpec" specification to be used by the Enactment Engine component for deploying and enacting the choreography;

We have implemented these functionalities in a set of REST (Representational State Transfer) services, which are called by CHOReOSynt as shown in Figure 4 and described below.

M2M Transformator -The Model-to-Model (M2M) Transformator offers a set of model transformations. Specifically, it offers an operation bpmn2clts() that takes as input the BPMN2 specification of the choreography and transforms it into a model called CLTS. The latter is an extended Labeled Transition System (LTS) that allows for automatically handling complex constructs of BPMN2 Choreography Diagrams, such as gateways, loops, forks and joins. Then, starting from the CLTS, CHOReOSynt extracts the list of the participants and, applying a further M2M transformation, automatically derives, for each participant, the CLTS model of the expected behavior with respect to the specified choreography. To this end another operation named extractParticipants() is offered. The CLTS model of expected behavior is achieved by projecting (projection()) the choreography onto the participant, hence filtering out those transitions, and related states, that do not belong to the participant. Basically, for each participant, this CLTS specifies the interaction protocol that a candidate service (to be discovered) has to support to play the role of the participant in the choreography.

Synthesis Discovery Manager -The Synthesis process and the Discovery process interact each other to retrieve, from the service registry, those candidate services that are suitable for playing the participant roles, and hence, those services whose (offered and required) operations and protocol are compatible with the CLTS models of the expected behavior. In particular, for each participant, the call to the discoverServices() operation is performed. It takes the participant (abstract) CLTS as input. Then, a query is issued to the eXtensible Service Discovery (XSD) component (not in the focus of this paper). Note that, although for each choreography participant a suitable third-party service may have been discovered (and hence, its interaction protocol fits the behavior of the participant in isolation), the uncontrolled (or wrongly coordinated) composite behavior of all the discovered services may show undesired interactions that prevent the choreography realization. For a detailed and formal description of the notion of undesired interaction, refer to [START_REF] Autili | A model-based synthesis process for choreography realizability enforcement[END_REF][START_REF] Autili | Synthesis of resilient choreographies[END_REF][START_REF] Autili | Distributed enforcement of service choreographies[END_REF].

Behavior Simulator -Once a set of concrete candidate services has been discovered, the synthesis process has to select them by checking, for each participant, if its expected behavior can be simulated by some candidate service. Note that, for a given participant, behavioral simulation is required since, although the discovered candidate services for it are able to offer and require (at least) the operations needed to play the role of the participant, one cannot be sure that the candidate services are able to support the operations flow as expected by the choreography. Thus, in order to simulate the expected behavior of a participant with the behavior of a service, the Behavior Simulator offers an operation named simulate() that takes as input the projected (abstract) CLTS of the participant and the extended (concrete) LTS of the service as retrieved by the URI returned by the discovery service. It might be interesting to mention that the simulation method implemented a notion of strong simulation suitably extended to treat the CLTSs and extended the LTSs we use in CHOReOS. After simulation, if all the participant roles have been "covered" by (some of) the discovered services, the abstract CLTS is concretized with the actual names of the selected services and the actual names of the offered and requested operations. Then, the automated synthesis process distributes the coordination logic specified by the obtained CLTS into a set of Coordination Models by means of the functionality clts2coord().

Coordination Delegate Generator -Once the services have been selected for all the choreography participants, and hence the CLTS has been concretized, the synthesis processor can generate the Coordination Delegates through the operation generateCDs() offered by the Coordination Delegate Generator component.

Next step in the process -Once the Coordination Delegates have been generated, the Coordination Delegate Generator component can further generate a specification of the choreography (called ChorSpec) to be passed to the choreography Enactment Engine (not in the focus of this paper). To this end, the operation createChorSpec() is offered. It takes as input the selected services and the coordination delegates generated for them. The ChorSpec is an XMLbased declarative description of the choreography that specifies the locations of the selected services and of the generated Coordination Delegate artifacts that can be deployed. Indeed, before passing the ChorSpec to the Enactment Engine, the Choreography Offline Testing process activity is performed to assess the quality of the choreography specification, its well formedness, etc.

Related work

In this section we discuss related work in the domains of behavioral model elicitation techniques and of service choreography development.

Elicitation techniques. We focus on black-box/grey-box techniques able to elicit behavioural models of the software. The reader interested on white-box techniques can refer to [START_REF] Alur | Synthesis of interface specifications for java classes[END_REF][START_REF] Wasylkowski | Mining temporal specifications from object usage[END_REF][START_REF] Wasylkowski | Detecting object usage anomalies[END_REF] and references therein.

LearnLib [START_REF] Hungar | Test-based model generation for legacy systems[END_REF] is a framework to automatically construct a finite automaton through automata learning and experimentation. Active automata learning tries to automatically construct a finite automaton that matches the behavior of a given target automaton on the basis of active interrogation of target systems and observation of the produced behavior.

The work described in [START_REF] Krogmann | Using genetic search for reverse engineering of parametric behavior models for performance prediction[END_REF] presents a comprehensive approach for building parametrized behaviour models of existing black-box components for performance prediction. Those parameters represent three performance-influencing factor, i.e., usage, assembly, and deployment context; this makes the models sensitive to changing load situations, connected components, and the underlying hardware. The approach makes use of static and dynamic analysis and searchbased approaches, namely genetic programming. These techniques take as input monitoring data, runtime bytecode counts, and static bytecode analysis.

SPY [START_REF] Ghezzi | Synthesizing intensional behavior models by graph transformation[END_REF] is an approach to infer a formal specification of stateful black-box components that behave as data abstractions (Java classes that behave as data containers) by observing their run-time behavior. SPY proceeds in two main stages: first, SPY infers a partial model of the considered Java class; second, through graph transformation, this partial model is generalized to deal with data values beyond the ones specified by the given instance pools. The inferred model is partial since it models the intentional behavior of the class with respect to only a set of instance pools provided as input, which are used to get values for method parameters, and an upper bound on the number of states of the model. GK-Tail [START_REF] Lorenzoli | Automatic generation of software behavioral models[END_REF] is a technique to automatically generate behavioral models from (object-oriented) system execution traces. GK-Tail assumes that execution traces are obtained by monitoring the system through message logging frameworks. For each system method, an Extended Finite State Machine (EFSM) is generated. It models the interaction between the components forming the system in terms of sequences of method invocations and data constraints on these invocations. The correctness of these data constraints depends on the completeness of the set of monitored traces with respect to all the possible system executions that might be infinite.

The work described in [START_REF] Berg | Regular inference for state machines using domains with equality tests[END_REF] presents an approach for inferring state machines with an infinite state space. By observing the output that the system produces when stimulated with selected inputs, they extend existing algorithms for regular inference (which infer finite state machines) to deal with infinite-state systems. This approach makes the problem of dealing with an infinite state space tractable, but may suffer a higher degree of model approximation.

The work described in [START_REF] Meinke | Automated black-box testing of functional correctness using function approximation[END_REF] presents a learning-based black-box testing approach in which the problem of testing functional correctness is reduced to a constraint solving problem. Functional correctness is modeled by pre-and postconditions that are first-order predicate formulas. A successful black-box test is an execution of the program on a set of input values satisfying the pre-condition, which terminates by retrieving a set of output values violating the post-condition. Black-box functional testing is the search for successful tests with respect to the program pre-and post-conditions. As coverage criterion the authors formulate a convergence criterion on function approximation.

The work in [START_REF] Dallmeier | Automatically generating test cases for specification mining[END_REF] presents an approach that, through a combination of systematic test case generation (by means of the TAUTOKO tool) and typestate mining, infers models of program behavior in the form of finite state automata describing transitions between object states. The generation of test cases permits to cover previously unobserved behavior, and systematically extends the execution space, and enriches the inferred behavior model. In this sense, it can be said this approach goes in an opposite direction with respect to StrawBerry.

The work in [START_REF] Aarts | Improving active mealy machine learning for protocol conformance testing[END_REF] concerns an application of active learning whose aim is to establish the correctness of protocol implementations relative to a given reference implementation. The work in [START_REF] Aarts | Automata learning through counterexample guided abstraction refinement[END_REF] shows how to fully-automatically construct the typical abstractions needed to perform automata learning.

Choreography realization techniques. CHOReOSynt is related to several approaches developed for automated choreography enforcement.

The approach described in [START_REF] Güdemann | Counterexample guided synthesis of monitors for realizability enforcement[END_REF] enforces a choreography's realizability by automatically generating monitors. Each monitor acts as a local controller for its peer. Monitors are built by iterating equivalence-checking steps between two centralized models of the whole system. A monitor is similar to our coordination delegate (CD). However, our approach synthesizes CDs without producing a centralized model of the whole system, hence preventing state explosion.

The method described in [START_REF] Kazhamiakin | Choreography conformance analysis: Asynchronous communications and information alignment[END_REF] checks the conformance between the choreography specification and the composition of participant implementations. Their framework can model and analyze compositions in which the interactions can also be asynchronous and the messages can be stored in unbounded queues and reordered if needed. Following this line of research, the authors of [START_REF] Kazhamiakin | Choreography conformance analysis: Asynchronous communications and information alignment[END_REF] provided a hierarchy of realizability notions that forms the basis for a more flexible analysis regarding classic realizability checks [START_REF] Kazhamiakin | Analysis of realizability conditions for web service choreographies[END_REF][START_REF] Kazhamiakin | Choreography conformance analysis: Asynchronous communications and information alignment[END_REF]. These two approaches are novel in that they characterize relevant properties to check a certain degree of realizability. However, they statically check realizability and do not enforce it.

The ASTRO toolset [START_REF] Trainotti | Astro: Supporting composition and execution of web services[END_REF] supports automated composition of Web services and the monitoring of their execution. It aims to compose a service starting from a business requirement and the description of the protocols defining available external services. Unlike our approach, ASTRO deals with centralized orchestration-based business processes rather than fully decentralized choreography-based ones.

The CIGAR (Concurrent and Interleaving Goal and Activity Recognition) framework aims for multigoal recognition [START_REF] Hu | CIGAR: Concurrent and Interleaving Goal and Activity Recognition[END_REF]. CIGAR decomposes an observed sequence of multigoal activities into a set of action sequences, one for each goal, specifying whether a goal is active in a specific action. Although such goal decomposition somewhat recalls CHOReOSynt's choreography decentralization, goal recognition represents a fundamentally different problem regarding realizability enforcement.

Given a set of candidate services offering the desired functionalities, the TCP-Compose* algorithm [START_REF] Santhanam | Tcpcompose a tcp-net based algorithm for efficient composition of web services using qualitative preferences[END_REF] identifies the set of composite services that best fit the user-specified qualitative preferences over non-functional attributes. CHORe-OSynt could exploit this research to extend the discovery process to enable more flexible selection of services from the registry.

The research we described in this paper is an advance over our previous research [START_REF] Autili | A model-based synthesis process for choreography realizability enforcement[END_REF][START_REF] Autili | Synthesis of resilient choreographies[END_REF]. Although the synthesis process described in our previous research treated most BPMN2 constructs, it considered a simplified version of their actual semantics. For instance, as in [START_REF] Güdemann | Counterexample guided synthesis of monitors for realizability enforcement[END_REF], the selection of conditional branches was simply abstracted as a non-deterministic choice, regardless of the run-time evaluation of their enabling conditions. Analogously, the synthesis process enforced parallel flows by non-deterministically choosing one of their linearizations obtained through interleaving, thus losing the actual degree of parallelism. To overcome these limitations, CHOReOSynt relies on a choreography model that, being more expressive than the choreography model in CIGAR and TCP-Compose*, preserves the BPMN2 constructs' actual semantics. Relying on a more expressive model led us to define a novel, more effective distributed coordination algorithm [START_REF] Autili | Distributed enforcement of service choreographies[END_REF].

Final remarks and future perspectives

Our past experience in behavioural models elicitation and integration code synthesis gives a first evidence, yet concrete, that the proposed approach is viable once referring to specific application domains, e.g., choreography-based systems.

Our experiments with strawberry have shown that it is practical and realistic in that it only assumes: (i) the availability of the WSDL; and (ii) the possibility to derive a partial oracle that can distinguish between regular and error answers. Furthermore, we observed that strawberry nicely converges to a realistic automaton. In future work, we intend to investigate if and how assumption (ii) could be relaxed.

Our experiments with CHOReOSynt demonstrated that considering domainspecific interaction patterns mitigates the complexity of coordination enforceability when recurrent business protocols must be enforced. Generally, choreography synthesis is difficult in that not all possible collaborations can be automatically realized. This suggests we could improve CHOReOSynt with a combination of domain-specific choreography patterns, as well as protocol interaction patterns that correspond to service collaborations that are tractable through exogenous coordination. Currently, CHOReOSynt supports pure coordination. It doesn't deal with protocol adaptation because it doesn't account for mismatches at the level of service operations and related I/O parameter types. To support data-based coordination through the elicitation and application of complex data mappings, CHOReOSynt should be enhanced to automatically infer mappings to match the data types of messages sent or received by mismatching participant services. This means effectively coping with heterogeneous service interfaces and dealing with as many Enterprise Integration Patterns [START_REF] Hohpe | Enterprise Integration Patterns: Designing, Building, and Deploying Messaging Solutions[END_REF] and protocol mediation patterns [START_REF] Li | A pattern-based approach to development of service mediators for protocol mediation[END_REF] as possible, in a fully automatic way. Toward that end, we achieved promising results in automated synthesis of modular mediators [START_REF] Inverardi | Automatic synthesis of modular connectors via composition of protocol mediation patterns[END_REF].

We want to enable the market acceptance and further enhancement of CHOReOSynt by third-party developers, especially small and medium enterprises, including development of applications for commercialization. So, we released CHOReOSynt under the umbrella of the Future Internet Software and Services Initiative (FISSi4 ). Using a market-oriented approach, FISSi aims to develop awareness of OW2 Future Internet software in both FISSi members and non-members and both open source vendors and proprietary vendors. Our primary objective, to be achieved in the near future, is to establish a community of developers and third-party market stakeholders (for example, users, application vendors, and policy makers) around CHOReOSynt.

Last but not least, an interesting future direction is the investigation of nonfunctional properties at the level of the elicited interaction protocols and of the synthesized choreography. For instance, this requires considering operation invocation response time, extending the choreography specification with performance or reliability attributes, and accounting for them in the CDs synthesis process.

Fig. 1 .

 1 Fig. 1. Elicit phase

Fig. 2 .

 2 Fig. 2. Overview of the StrawBerry technique

Fig. 3 .

 3 Fig. 3. Integrate phase

Fig. 4 .

 4 Fig. 4. CHOReOSynt REST architecture

http://www.programmableweb.com.

http://www.omg.org/spec/BPMN/2.0.

ATL is a domain specific language for realizing model-to-model transformationswww.eclipse.org/atl

http://www.ow2.org/view/Future_Internet/CHOReOS

Acknowledgments

The research work so far has been supported by the Italian MIUR, prot. 2012E47TM2 (project IDEAS -Integrated Design and Evolution of Adaptive Systems), and by the EC FP7 under grant agreement n. 257178 (project CHOReOS -Large Scale Choreographies for the Future Internetwww.choreos. eu). Future research efforts will be supported by the EC H2020 under grant agreement n. 644178 (project CHOReVOLUTION -Automated Synthesis of Dynamic and Secured Choreographies for the Future Internet).


Razieh Behjati
email: behjati@simula.no

Shiva Nejati
email: shiva.nejati@uni.lu

Efficient Architecture-Level Configuration of Large-Scale Embedded Software Systems

Keywords: Model-based configuration, CSP, Backtracking, UML/OCL

Configuration is a recurring problem in many domains. In our earlier work, we focused on architecture-level configuration of largescale embedded software systems and proposed a methodology that enables engineers to configure products by instantiating a given reference architecture model. Products have to satisfy a number of constraints specified in the reference architecture model. If not, the engineers have to backtrack their configuration decisions to rebuild a configured product that satisfies the constraints. Backtracking configuration decisions makes the configuration process considerably slow. In this paper, we improve our earlier work and propose a backtrack-free configuration mechanism. Specifically, given a cycle-free generic reference architecture model, we propose an algorithm that computes an ordering over configuration parameters that yields a consistent configuration without any need to backtrack. We evaluated our approach on a simplified model of an industrial case study. We show that our ordering approach eliminates backtracking. It reduces the overall configuration time by both reducing the required number of value assignments, and reducing the time that it takes to complete one configuration iteration. Furthermore, we show that the latter has a linear growth with the size of the configuration problem.

Introduction

Configuration is a recurring problem in many embedded software system domains such as energy, automotive, and avionics. In these domains, product-line engineering approaches [START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF][START_REF] Linden | Software Product Lines in Action: The Best Industrial Practice in Product Line Engineering[END_REF] are largely applied to develop various configurations of a reference architecture. Briefly, a reference architecture provides a common, high-level, and customizable structure for all members of the product family [START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF] by specifying different types of components and configurable parameters, as well as, constraints capturing relationships between these parameters. Through configuration, engineers develop each product by creating component instances and assigning values to their parameters such that the constraints over parameters are satisfied.

Normally, configuring embedded systems involves assigning values to tens of thousands of interdependent parameters, and ensuring their consistency. Typically, 15 to 20 percent of these parameters are interdependent. Finding consistent values for interdependent parameters without any automated support is challenging. Manual configuration -the common practice in many companiesis time-consuming and error-prone, especially for large-scale systems. During the last three decades, researchers have developed a large number of approaches to automate various configuration use cases [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF]. Most of these approaches concern consistency of configuration decisions, and rely on constraint solvers (e.g., [START_REF] Eames | DesertFD: a finite-domain constraint based tool for design space exploration[END_REF][START_REF] Mazo | Transforming attribute and clone-enabled feature models into constraint programs over finite domains[END_REF][START_REF] Horváth | Dynamic constraint satisfaction problems over models[END_REF]) or SAT solvers (e.g., [START_REF] Janota | How to complete an interactive configuration process?[END_REF]) for ensuring consistency.

In our earlier work [START_REF] Behjati | Architecture-level configuration of largescale embedded software systems[END_REF], we proposed an iterative approach for configuring large embedded systems where at each iteration the value for one parameter is specified. If at some point during configuration, a value assignment violates some constraints, then the engineers may have to backtrack some of their recent choices until they can find a configuration assignment consistent with the constraints in the reference architecture. Backtracking configuration decisions makes the configuration process considerably expensive.

In this paper, we extend our earlier work [START_REF] Behjati | Architecture-level configuration of largescale embedded software systems[END_REF] and propose a new approach that eliminates backtracking during configuration by configuring parameters in a certain order. We explain how such an ordering is extracted from an acyclic1 reference architecture model, and argue that if the ordering is followed, our algorithm generates consistent and complete configured products without any need to backtrack a decision. We argue that elimination of backtracking considerably improves the performance of our configuration approach. We show this by applying our approach to a simplified excerpt of an industrial case study from the oil and gas domain. The experiment shows that our ordering approach reduces the overall configuration time by both reducing the required number of value assignments, and reducing the time that it takes to complete one configuration iteration. Further, we demonstrate that in our backtrack-free configuration approach the time required for completing one configuration iteration grows linearly with the size of the configuration problem. In our original configuration approach, this time has a quadratic growth.

In the rest of the paper, we first present the related work and position our work in the literature. Section 3 provides an overview of the main concepts in product family modeling and configuration. Our ordering approach for eliminating backtracking, and the resulting backtrack-free configuration algorithm are presented in Section 4. In Section 5, we experimentally evaluate the efficiency and scalability of our approach. A discussion of the potentials and limitations of the work is presented in Section 6. Finally, we conclude the work in Section 7.

Related Work

Existing configuration approaches fall into two general categories, non-interactive and interactive. Most configuration approaches belong to the first category, where the objective is to produce some final configured products without requiring intermediate input from users. They may either find an optimized solution based on some given optimization criteria (e.g., [START_REF] Eames | DesertFD: a finite-domain constraint based tool for design space exploration[END_REF][START_REF] Horváth | Dynamic constraint satisfaction problems over models[END_REF]) or find all configuration solutions (e.g., [START_REF] Benavides | FAMA: tooling a framework for the automated analysis of feature models[END_REF][START_REF] Czarnecki | Cardinality-Based Feature Modeling and Constraints: A Progress Report[END_REF][START_REF] Mazo | Transforming attribute and clone-enabled feature models into constraint programs over finite domains[END_REF]). The non-interactive approaches may either rely on meta-heuristic search approaches [START_REF] Fonseca | An overview of evolutionary algorithms in multiobjective optimization[END_REF][START_REF] Glover | A user's guide to tabu search[END_REF][START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF], or on systematic search techniques used in constraint solvers [START_REF] Carlsson | SICStus Prolog -the first 25 years[END_REF][START_REF] Carlsson | An open-ended finite domain constraint solver[END_REF][START_REF] Hentenryck | Design, implementation, and evaluation of the constraint language cc(FD)[END_REF], or on symbolic decision procedures [START_REF] Bryant | Graph-based algorithms for boolean function manipulation[END_REF]. Among these, meta-heuristic search approaches are generally faster and require less memory. However, since meta-heuristic search is stochastic and incomplete, it cannot support an interactive process where engineers have to be provided with precise and complete guidance information at each iteration.

Interactive configuration methods (e.g., [START_REF] Hadzic | Fast backtrack-free product configuration using a precompiled solution space representation[END_REF][START_REF] Janota | How to complete an interactive configuration process?[END_REF][START_REF] Van Der Meer | Efficient interactive configuration of unbounded modular systems[END_REF][START_REF] Xiong | Generating range fixes for software configuration[END_REF]) mostly rely on constraint solvers or symbolic reasoning approaches. Backtracking is required whenever an inconsistency arises, even though it may make the process considerably slower. In general, constraint solvers alleviate the drawbacks of backtracking by employing heuristics such as back-jumping [START_REF] Dechter | Backjump-based backtracking for constraint satisfaction problems[END_REF], identifying no-goods constraints [START_REF] Armstrong | Dynamic prioritization of complex agents in distributed constraint satisfaction problems[END_REF][START_REF] Bayardo | A complexity analysis of space-bounded learning algorithms for the constraint satisfaction problem[END_REF], and ordering the search [START_REF] Freuder | A sufficient condition for backtrack-free search[END_REF]. None of these improvements, however, totally eliminates the possibility of backtracking. In addition, it is open whether these heuristics can be tailored to interactive configuration solutions. Some more recent interactive configuration approaches [START_REF] Hadzic | Fast backtrack-free product configuration using a precompiled solution space representation[END_REF][START_REF] Van Der Meer | Efficient interactive configuration of unbounded modular systems[END_REF] have eliminated backtracking by adding an offline preprocessing phase to configuration, during which all consistent configurations are computed and used to direct the user during the interactive phase, preventing the user to make any decision that gives rise to an inconsistency. These approaches only scale when the space of all consistent configurations can be encoded and computed within the available memory. In the case of large-scale embedded software systems, the complexity of constraints and the size of the configuration space is so large2 , making it impossible to compute the set of all possible configurations in an offline mode.

In our work, using information provided in reference architecture model, we identify an ordering over variables and show that by following this ordering, backtracking does not arise during the configuration of a single product. Our approach applies to architecture-level configuration of embedded software systems with architectural dependencies and constraints specified in First-Order Logic (FOL) [START_REF] Smullyan | First-order logic[END_REF]. Computation of ordering in our work is fast and performed based on static analysis of architectural models and the constraints syntax.

Preliminaries

The work presented in this paper is based on a model-based configuration framework presented in [START_REF] Behjati | Architecture-level configuration of largescale embedded software systems[END_REF]. In this section, we present the reference architecture model, and exemplify the main concepts in modeling and configuration of embedded software systems. In addition, we propose the notion of a configuration tree.

The reference architecture model

In our approach, a reference architecture model defines a hierarchy of component types. Each component has a number of configurable parameters, and may as well contain other configurable elements. We consider configurable parameters as one type of configurable elements. Furthermore, the reference architecture model specifies constraints among the configurable parameters. The SimPL methodology [START_REF] Behjati | SimPL: a product-line modeling methodology for families of integrated control systems[END_REF] is an approach for creating such reference architecture models. As mentioned earlier, during configuration, products are created by creating component instances and configuring their parameters. In the following, we explain components as the main building blocks of products, and constraints as they play a key role is ensuring the consistency of products. A complete specification of the reference architecture model and its formal semantics is given in [START_REF] Behjati | Architecture-level configuration of largescale embedded software systems[END_REF].

Components

Each component in a product is an instance of a component type in the corresponding reference architecture. We define a component c as a tuple (id, V), where id is a unique identifier, and V is a set of configurable elements. Each configurable element in V is a tuple e = (id e , t e ), where id e is the name of the element, and t e is the type of the element. Figure 1 gives a grammar for the types of elements in V. In Figure 1, primitive_type represents a set of terminals for primitive types 'integer' and 'boolean' (we do not consider 'strings'), and user_defined_type denotes a set of terminals each corresponding to a component type defined in the reference architecture model.

Configurable elements of a primitive type or a referenced type represent configurable parameters. A configurable element of a user defined type represents a sub-component of c (i.e., the sub-component is a component c = (id , V ) itself).

Constraints

Let c = (id, V) be a component. We use Φ id to denote the set of constraints defined in the context of c (i.e., specifying relations among elements of c). Each member of the set Φ id is a boolean expression denoting a constraint φ. A simplified grammar for the language of boolean expressions is given in Figure 2. This grammar maps to a subset of the Object Constraint Language (OCL) [START_REF] Omg | OMG Object Constraint Language (OMG OCL)[END_REF] that we use in the SimPL methodology. The grammar allows the basic OCL operators including for-all, exists, arithmetic, relational and logical operators. In Figure 2, FA represents the universal quantifier, which maps to OCL forAll operator. Similarly, EX represents the existential quantifier, which maps to OCL exists operator. Three types of qualified names (i.e., bool_qName, int_qName, and array_q-Name) are used in the production rules of the grammar given in Figure 2. Qualified names together with literals and operators create numerical, relational, and boolean expressions. Qualified names of numerical types (i.e., integer or a user defined enumeration) form one type of numerical factors and are used in creating relational expressions. Qualified names of type boolean form one type of boolean factors. Qualified names representing collections of items can be combined with set quantifiers (i.e., for all and exists) to form another group of boolean factors. In addition to these, variables (i.e., var) may be used as integer or boolean factors. Variables are used in combination with quantifiers.

A configuration example

Figure 3 is a class diagram showing an excerpt of a simplified reference architecture for a family of subsea oil production systems. It is part of a larger case study, which is presented in [START_REF] Behjati | SimPL: a product-line modeling methodology for families of integrated control systems[END_REF][START_REF] Behjati | Architecture-level configuration of largescale embedded software systems[END_REF]. Each class in Figure 3 represents a component type, and each attribute in a class represents a configurable parameter. In addition, two OCL constraints are defined in the context of class ElectronicConnections.

To make a product, one has to create and configure an instance of a XmasTree. To do so, engineers have to specify the number of electronic boards on each of the Subsea Electronic Modules3 (SEMs) by initializing the eBoards array in each of the two SEMs (each XmasTree instance has two SEM instances) and assign a value to each item in those arrays, create a number of electronic connections by setting the size of array myConnections, and assigning values to relatedSEM, pinIndex and bIndex attributes of each ElectronicConnection instance. Example 1. Suppose that, at some point in the configuration of a product, a user configures an ElectronicConnection by first setting its bIndex to 5, then setting its pinIndex to 20, and finally setting its relatedSEM to one of the SEM instances. At this point, if the chosen SEM instance has less than 5 electronic boards, or its eBoards [START_REF] Behjati | SimPL: a product-line modeling methodology for families of integrated control systems[END_REF] is less than 20, an inconsistency happens. In this case, the user has to backtrack to fix the inconsistency, for example by changing the value of pinIndex or bIndex. Alternatively, to eliminate backtracking, the user can first configure relatedSEM, then assign a value to bIndex, and finally configure pinIndex.

In this paper, based on a static analysis of the constraints, we propose an approach for identifying configuration orderings that eliminate backtracking.

The configuration tree

A product is usually represented by a configuration tree. We denote a configuration tree by a tuple (N, E), where N is the set of nodes, and E is the set of edges of the tree. In our approach, each node in a configuration tree has a type and a value, and each edge has a label. The type of a node belongs to the language of types in Figure 1. Based on this, we identify four types of nodes: primitive nodes, component nodes (if the node is typed by a user defined type), reference nodes, and array nodes. Figure 4 shows two example configuration trees.

Primitive nodes and reference nodes represent configurable parameters, and are always leaf nodes in the tree. The value of a leaf node must conform to its type. A missing value for a leaf node means that the corresponding configurable parameter is not yet configured. Nodes m13 and m15 in Figure 4-(b) are primitive and reference nodes, respectively. Both nodes are unconfigured.

Each array node has a child node of type 'int', which is connected to it by an edge labeled 'size()'. We refer to this node as the array's size node. An array node is called uninitialized if its size node does not have a value, and is called initialized otherwise. An initialized array node of size n, and type 'single_type[]' has n additional child nodes. Each of these child nodes is typed by 'single_type', and is connected to the array node via an edge labeled 'at(i)', where i is an integer in [1..n]. Node m2 in Figure 4-(a) is an initialized array node of size two.

A component node represents a component. Such a node is typed by a user defined type, and its value is the identifier of the corresponding component. Let

The configuration process

Our model-based configuration approach presented in [START_REF] Behjati | Architecture-level configuration of largescale embedded software systems[END_REF] validates configuration decisions automatically and interactively. For this purpose, we use the config-uration tree and the constraints defined in the reference architecture model to create a constraint network [START_REF] Montanari | Networks of constraints: Fundamental properties and applications to picture processing[END_REF]. A constraint network is a finite set of variables, each associated with a finite domain of discrete values, and a number of constraints over those variables. The problem of finding a consistent configuration maps to a constraint satisfaction problem, where the objective is to find a consistent assignment of values to all the variables in the constraint network.

Each configurable parameter (a leaf node in the configuration tree) maps to a variable in the constraint network. The domain of the variable corresponding to configurable parameter p is a finite set of literals that can be assigned to p.

Each constraint in the reference architecture model is rewritten in terms of the variables in the constraint network, and is added to the constraint network. During configuration, new variables or constraints may be added to the constraint network. We call this the dynamic growth of the constraint network.

To ensure the consistency of configuration decisions, we use constraint propagation over finite domains [START_REF] Rossi | Handbook of Constraint Programming[END_REF]. Constraint propagation provides a sound approximation of consistency: it does not eliminate any consistent solution, but it may fail to identify all inconsistent value-assignments. In other words, constraint propagation prunes the search space, but it does not enumerate all possible solutions. The benefit of using constraint propagation is that it is fast, and therefore applicable in an interactive context. Its drawback is that it does not eliminate all inconsistent value-assignments, and therefore, backtracking may be needed to ensure consistency. This can be avoided by imposing some restrictions on the reference architecture model of the product family. In particular, the model of the product family should not contain any cyclic constraints.

Another reason for requiring backtracking in our original configuration approach is the dynamic growth of the constraint network. New constraints that are added to the constraint network may be inconsistent with some of the previously made decisions. To avoid this, we configure parameters in a particular order. In the following, before presenting our approach for ordering configuration decisions, we first present the notion of qualified names. Then, based on the proposed ordering approach, we present a backtrack-free configuration algorithm.

Qualified names

Figure 6 shows a grammar for qualified names. A qualified name (e.g., int_qName) represents a typed variable (e.g., a configurable parameter) and may represent an individual item (e.g., int_qName) or a collection of items (i.e., ar-ray_qName). The last rule in Figure 6 is added to explicitly define int_qName and bool_qName as primitive qualified names. Primitive qualified names represent configurable parameters, and together with array qualified names are used in the grammar of boolean expressions in Figure 2.

A qualified name can be created by traversing a configuration tree. Let CT be a configuration tree, and n be a node representing a component c = (id, V) in the configuration tree. Each node n in the subtree rooted at n can be uniquely identified by a string created using id and edge labels. To do so, we start with string str = "id", and follow the edges that bring us to n . After traversing each edge, we concatenate str with ".l", where l is the label of the last traversed edge 4 . Using this approach each node in the tree may be represented by more than one string, depending on the starting node. A string should always start with the label of a component node. Fig. 6. The grammar of qualified names.

Semantically valid qualified names

Let CT be a configuration tree representing a possibly partially-configured product derived from a given reference architecture. A subset of the qualified names created using the grammar in Figure 6 are semantically valid with respect to the configuration tree CT . We use Q(CT ) to denote this subset. A qualified name q belongs to Q(CT ) iff one of the following holds:

q is the label of a component node in CT , q = q1.t, where q1 ∈ Q(CT ), and q1 represents a component c = (id, V), such that t is the name of an element in V, q = q1[q2], where q1 ∈ Q(CT ), q1 represents an arrayed element, and q2 is either an integer literal or a semantically valid qualified name representing an integer parameter, q = q1.size(), where q1 ∈ Q(CT ), and q1 is an arrayed element.

Mapped and unmapped qualified names

Let CT be a configuration tree, and q be a semantically valid qualified name in Q(CT ). If q corresponds to a node in CT , then we call q a mapped qualified name, otherwise, it is called an unmapped qualified name. A qualified name q is unmapped if any of the following conditions holds:

a prefix of q maps to an unconfigured reference node, q is of the form q1[q2], where q2 represents an unconfigured parameter, q is of the form q1[q2], where q1 is an uninitialized array (q1.size() is not configured).

In each case, a parameter is unconfigured. For a semantically valid unmapped qualified name q, we use U(q) to denote the set of all such unconfigured parameters. For a qualified name q mapped to a leaf node, we use M(q) to denote the corresponding configurable parameter.

Let CT be the configuration tree in Figure 5. Then xt1.mySEMs [START_REF] Armstrong | Dynamic prioritization of complex agents in distributed constraint satisfaction problems[END_REF] is mapped, and sem1.eBoards [START_REF] Armstrong | Dynamic prioritization of complex agents in distributed constraint satisfaction problems[END_REF] is an unmapped semantically valid qualified name in Q(CT ). An unmapped qualified name can become mapped as parameters are configured and the tree is expanded. For example, sem1.eBoards [START_REF] Armstrong | Dynamic prioritization of complex agents in distributed constraint satisfaction problems[END_REF] becomes mapped after configuring the size of sem1.eBoards.

Ordering configuration decisions

Example 1 in Section 3.1.3 shows an example of inconsistencies that arise due to the dynamic growth. In this example, the two constraints in Figure 3 cannot be evaluated until relatedSEM is configured. This is because relatedSEM.eBoards, appeared in both constraints, is unmapped as it does not correspond to a unique node in the tree. By configuring relatedSEM both constraints become ready-toevaluate, can be added to the constraint network, and can be used in constraint propagation to validate the values assigned to pinIndex and bIndex or to eliminate inconsistent values for them if they were not configured. We call a constraint that is not yet ready-to-evaluate, a pending constraint. Such a constraint contains one or more unmapped qualified names and is pending on one or more parameters to be configured. These parameters should be configured to make the unmapped qualified names mapped. For example, the constraints in Example 1 are pending on relatedSEM to be configured. In each configuration iteration, each constraint is either pending or ready-to-evaluate. Figure 7 shows the state transition diagram of a constraint. As a consequence of configuring parameters, a pending constraint may become ready-to-evaluate. Only ready-to-evaluate constraints can be included in the constraint network.

Consider the ith step of configuration and let c be a pending binary constraint, containing two qualified names q 1 and q 2 . Suppose that q 1 is unmapped, and q 2 is mapped to the configurable parameter p (i.e., M(q 2 ) = p). This parameter cannot be configured until c becomes ready-to-evaluate (i.e., until q 1 becomes a mapped qualified name). We refer to such a parameter as a pending parameter. Let parameters p 1 , ..., p n be the parameters that should be configured to make q 1 a mapped qualified name (i.e., U(q 1 ) = {p 1 , ..., p n }). To eliminate backtracking, parameter p should be configured after all p i s are configured. This is shown in Figure 8. Before a parameter reaches the state ready, the set X, which is the set of all p i s as described above, should be empty. As shown in Figure 8, a parameter can be configured only when it is in state ready. Note that, as suggested by the formulation of X, in general p may be involved in more than one constraint.

U(q1) = ∅ ∨ U(q2) = ∅ U(q1) = U(q2) = ∅ U(q1) = U(q2) = ∅ Fig. 7. States of constraint c = φ(q1, q2). init start pending ready configured X = ∅ X = ∅ X = ∅ Config. of p Fig. 8. States of parameter p. X is {p |∃c = φ(q1, q2).p ∈ U (q1) ∧ M(q2) = p}.
In other words, in each configuration iteration, the set of all unconfigured parameters is partitioned into two sets: pending and ready-to-configure parameters. This partitioning of parameters, together with the stepwise configuration, which in each iteration may add new unconfigured parameters to the system, imposes an ordering on the configuration decisions. Note that, in each iteration, there is no ordering among the ready-to-configure parameters. The acyclic property of the reference architecture model guarantees that every parameter eventually reaches the state ready.

Backtrack-free configuration

Algorithm 1 is our backtrack free configuration algorithm, which implements the ordering approach explained above. Input to the algorithm is a cycle-free reference architecture, which contains a class diagram and a set of constraints. The output is a configuration tree CT . We maintain three sets of parameters: configured (C), ready-to-configure (R), and pending parameters (P ); and two sets of constraints: ready-to-evaluate (Φ), and pending (Φ ) constraints. Using the input reference architecture model, we initialize all these sets and the configuration tree in line 1 of the algorithm. In line 2, domains of the unconfigured parameters are computed using the routine computeValidDomains. In this routine, we use a constraint solver to prune the domains by removing values that are inconsistent with one or more constraints in Φ or some values in C. Note that only the ready-to-evaluate constraints and their variables are considered when pruning the domains (i.e., P and Q are not included in the computation).

Algorithm 1. BTFreeConfig

Input: A reference architecture RA Output: a configuration tree CT 1 (CT, C, R, P, Φ, Φ ) ← initializeConfigurationProblem(RA) 2 D ← computeValidDomains(C, R, Φ) 3 while R = ∅ do
The while loop in lines 3-12 repeats while there are some ready-to-configure parameters (i.e., R = ∅). In each iteration, one parameter is configured. Both the parameter and its value are selected by the human user in lines 4 and 5 of the algorithm. Lines 7 and 8 guarantee that the selected value is within the domain of the selected parameter and is, therefore, consistent. As a result of assigning a value v to a parameter R[i], one or more of the following may happen:

new nodes may be added to the configuration tree, therefore new elements may be added to R and P if a constraint is pending on R[i], it may become ready-to-evaluate, and some of the parameters that are pending on R[i] may become ready for configuration. We move them to the set of ready-to-configure parameters R.

These actions are performed in line 9 by calling the routine applyConfiguration. The constraint solver is again invoked in line 10 to update the valid domains. If some domains become empty, the algorithm throws an exception in line 12. Otherwise, it continues to the next iteration. Eventually, a completely and consistently configured configuration tree is returned in line 13.

In [START_REF] Behjati | Architecture-level configuration of largescale embedded software systems[END_REF], we showed that our original configuration algorithm produces complete and consistent products. A product is complete if it does not contain any unconfigured parameters, and is consistent if it satisfies all the constraints in the reference architecture model. In our technical report [START_REF] Behjati | Backtrack-free consistent configuration of cyber-physical systems[END_REF], we have shown that Algorithm 1 produces complete and consistent products, but without requiring backtracking. In other words, for any given acyclic reference architecture model, Algorithm 1 terminates without ever reaching line 12.

Evaluation

To evaluate the efficiency brought by our ordering approach, we performed an experiment using the reference architecture model presented in Figure 3. For this purpose, 1600 random configuration scenarios were created (800 scenarios for each of our original and backtrack-free configuration approaches). In each case, we started by configuring three parameters that identify the size of the configuration problem, then randomly configured the rest of the parameters. The first three parameters were configured as listed in Table 1. This is done merely to control the number of parameters in each case to simplify the analysis of the results. For each case in Table 1, we randomly generated 100 sample configuration scenarios using our original configuration approach, and 100 sample configuration scenarios using the backtrack-free configuration approach. Figure 9 shows the average response time in each iteration for both cases. Fig. 9. A comparison of the average response time for our original and backtrack-free configuration approaches.

In our original configuration approach, a complete configuration iteration, in addition to validating the decision and propagating it, may involve several decision roll-backs, and is therefore time consuming. On the other hand, a complete configuration iteration in the backtrack-free configuration approach involves validating and propagating the decision, and updating the ordering (i.e., updating lists of pending constraints and parameters). By using the ordering, we eliminate all the roll-backs and their costs. This explains why for most cases in Figure 9, an average iteration in the original configuration approach takes much longer than that in the backtrack-free configuration approach. This experiment shows that for configuration scenarios with more than 50 parameters, the time overhead of computing the ordering is negligible compared to the time that should otherwise be spent on rolling-back the decisions.

In our original configuration approach, for fixing an inconsistency, in addition to rolling back some of the decisions, new values must be assigned to the parameters that might have caused that inconsistency. In our experiment, on average 23.6 different values were tried per parameter to achieve a consistent configuration. This high number is a result of our current naive implementation of backtracking. By exploiting heuristics such as back jumping [START_REF] Dechter | Backjump-based backtracking for constraint satisfaction problems[END_REF], this number can be reduced significantly. Table 2 shows the number of decisions that were needed to achieve a consistent configuration. To provide a better insight into the time complexity of our configuration approaches, we performed another experiment. The result of this experiment is shown in Figures 10 and11. In each case, we measured the average response time for randomly generated configuration scenarios. Figure 10 shows that for our original approach the response time (i.e., the time that it takes to complete one configuration iteration) grows quadratically with the size of the configuration problem (i.e., the number of configurable parameters). On the other hand, as shown in Figure 11, in the case of our backtrack-free configuration approach, this growth is linear with the size of the configuration problem. Furthermore, Figure 11 gives an insight into the usability of our backtrackfree configuration approach. According to a study reported in [START_REF] Nielsen | Usability Engineering[END_REF], 0.1 second is about the limit for having the user feel that the system is reacting instantaneously. Figure 11 shows that our backtrack-free configuration approach can respond instantly even for configuration problems with up to 2000 parameters.

Discussion

Normally, backtracking is used to explore the search space, in order to resolve inconsistencies, or to find all solutions. In our configuration approach [START_REF] Behjati | Architecture-level configuration of largescale embedded software systems[END_REF], we use backtracking to resolve inconsistencies that may arise while configuring a single product. Analyzing configuration scenarios shows that, in our approach, most of these inconsistencies are due to early configuration of parameters that are involved in some pending constraints. By delaying the configuration of such parameters, using our ordering approach, we can prevent inconsistent configurations. One should note that our approach cannot generally eliminate backtracking for every use-case, such as enumerating all configurations, or resolving inconsistencies that may arise due to cyclic constraints.

For our backtrack-free configuration approach to be able to produce consistent and complete products, the input reference architecture model must be cycle-free. In particular, to guarantee the termination of the configuration algorithm, the component hierarchy must be acyclic. Achieving this property for embedded software systems, where the software architecture follows, to a great extent, the architecture of hardware, is straightforward. To guarantee consistency, without requiring backtracking, the model should contain no cyclic constraints. Whether this restriction can negatively affect the applicability of our approach is a question that requires further investigation. Identifying the likelihood of embedded systems with cyclic constraints and proposing heuristics for ensuring their consistency with a minimum number of backtracks is left for future work. Finally, our proposed ordering approach may introduce some rigidity. Whether this rigidity affects usability negatively or not is an open questions that should be studied in future.

Conclusion

Constraint solving is generally used to ensure consistency of configurations, which are an essential part of software development in today's industries. A drawback of these techniques is the need for backtracking, which in the case of interactive configuration drastically hampers usability. In this paper, we proposed a partial ordering over the configurable parameters. The ordering is derived from a static analysis of the constraints between the parameters. Using the ordering approach, we have implemented a backtrack-free configuration tool. We performed a number of experiments using a case study from an industry partner. Results of our experiments show that our backtrack-free configuration tool ensures consistency, while preventing the need for backtracking. Furthermore, our approach significantly reduces the overall configuration time.

Fig. 1 .

 1 Fig. 1. A simplified grammar for types.

Fig. 2 .

 2 Fig. 2. A simplified grammar of boolean formulas.

Fig. 3 .

 3 Fig. 3. An excerpt of the reference architecture model of a subsea oil production system.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Configuration subtrees representing two components. Text inside a circle represents the type and value (in parenthesis) of the node. The text next to a node is a unique name to refer to the node in our explanation of the approach. (a) an instance of XmasTree, and (b) an instance of ElectronicConnection.

4 read(i) i: index of the selected unconfigured parameter 5 read(v) value to be assigned to the selected parameter 6 v 7 while not v ∈ D[i] do 8 read(v) 9 applyConfiguration 10 D

 45678910 must be in D[i] (the domain of the selected parameter) (CT, C, R, P, Φ, Φ , i, tmp) ← updateValidDomains(C, R, Φ) 11 if some domains in D are empty then 12 throwException() 13 return CT

Fig. 10 .

 10 Fig. 10. Quadratic growth of the average response time in our original configuration approach.

Fig. 11 .

 11 Fig. 11. Linear growth of the average response time in our backtrackfree configuration approach.

Table 1 .

 1 Configuration settings.

					35	Original (without ordering)
						Backtrack-free (with ordering)
					30
	# Parameters 25 50 75 100	# Elec. Connections on SEMs # eBoards 5 3,4 14 2,3 21 4,5 27 6,10	Avg. response time (ms)	25 15 20
	125	32	12,14		10
	150	35	17,25		5
	175	49	11,14
	200	49	25,25			50	100	150	200
						Number of parameters

Table 2 .

 2 Overhead of backtracking.

	# Parameters	25	50	75	100	125	150	175	200
	Avg. # Decisions 174.85 949.60 1773.49 2678.15 3426.29 2112.34 6301.47 3842.10
	Avg. Ratio	6.99 18.99 23.65 26.78 27.41 14.08 36.00 19.21
	Total Avg. Ratio (average number of decisions per parameter)	23.62

In our approach, a reference architecture model consists of a component hierarchy, and a set of constraints (see Section 3.1). Such a reference architecture is acyclic if it neither contains any cycles in the component hierarchy nor in the constraints. This condition is required to ensure the termination of the configuration process as well as the complete elimination of backtracking (see Sections 4 and 6).

Creating a product usually involves configuring tens of thousands of parameters. The configuration space, which is in fact the combinatorial space created for these parameters is, as well, significantly large.

A Subsea Electronic Module is an electronic unit, with software deployed on it. It is the main component in a subsea control system.

In the rest of this paper, for the sake of conciseness, we use a[i] to denote a.at(i), where a represents an array node in the configuration tree, and i is an integer literal.

Acknowledgements

The first author acknowledges the Research Council of Norway (the ModelFusion Project -NFR 205606). The second author is funded by the National Research Fund -Luxembourg (FNR/P10/03 -Verification and Validation Laboratory).