Sébastien Salva
email: sebastien.salva@uca.fr

Elliott Blot
email: eblot@isima.fr

COnfECt: An Approach to Learn Models of Component-based Systems

Keywords: Model learning, Passive learning, Component-based systems, Callable-EFSM

This paper addresses the problem of learning models of component-based systems. We focus on model learning approaches that generate state diagram models of software or systems. We present COnfECt, a method that supplements passive model learning approaches to generate models of component-based systems seen as black-boxes. We define the behaviours of components that call each other with Callable Extended FSMs (CEFSM). COnfECt tries to detect component behaviours from execution traces and generates systems of CEFSMs. To reach that purpose, COnfECt is based on the notions of trace analysis, event correlation, model similarity and data clustering. We describe the two main steps of COnfECt in the paper and show an example of integration with the passive model learning approach Gk-tail.

INTRODUCTION

Delivering high quality software to end-users has become a high priority in the software industry. To help develop high quality products, the software engineering field suggests to use models, which can serve as documentation, for verification or testing. But models are often written by hand, and such a task is difficult and error-prone, even for experts. To make this task easier, model learning approaches have proven to be valuable for recovering the model of a system. In this paper, we consider one specific type of formal models, namely state machines, which are crucial for describing system behaviours. In a nutshell, model learning approaches infer a behavioural formal model of a system seen as a black-box, either by interacting with it (active approaches), e.g., with test cases, or by analysing a set of execution traces resulting from the monitoring of the system (passive approaches).

Although it is possible to infer models from some realistic systems, several points require further investigation before entering in an industrial phase. Among them, we observed that the current approaches consider a black-box system as a whole, which takes input events from an external environment and produces output events. Yet, most of the systems being currently developed are made up of reusable features or components that interact together. The modelling of these components and of their compositions would bring a better readability and understanding of the functioning of the system under learning.

We focus on this open problem in this paper and propose a method called COnfECt (COrrelate Extract Compose) for learning a system of CEF-SMs (Callable Extended FSMs), which describes a component-based system. COnfECt aims at completing the passive model learning approaches, which take execution traces as inputs. The fundamental idea considered in COnfECt is that a component of a system can be identified from the others by its behaviour. COnfECt analyses execution traces, detects sequences of distinctive behaviours, extracts them into new trace sets from which CEFSMs are generated. To do this, COnfECt uses the notions of event correlation, similarities of models and data clustering. More precisely, the contributions of our work are:

• the definitions of the CEFSM model and of a system of CEFSMs allowing to express the behaviours of components calling each other; • COnfECt, a method supplementing the passive model learning approaches that generate EFSMs (Extended FSMs). COnfECt consists of two steps called Trace Analysis & Extraction and CEFSM Synchronisation. The first step splits traces into event sequences that are analysed to build new trace sets and to prepare the CEFSM synchronisation. The second step proposes three strategies of CEFSM synchronisation, which help manage the over-generalisation problem, i.e., the problem of generating models expressing more behaviours than those given in the initial trace set. This step returns a system of CEFSMs. We briefly show how COnfECt can be combined with the passive approach Gk-tail [START_REF] Lorenzoli | Automatic generation of software behavioral models[END_REF]. We call the new approach Ck-tail. We show how to arrange the steps of Gk-tail and COnfECt to generate a system of CEFSMs from the traces of a black-box system.

The remainder of the paper is organised as follows: Section 2 presents some related work. Section 3 provides some definitions about the CEFSM model. The COnfECt method is presented in Section 4. We finally conclude and give some perspectives for future work in Section 6.

RELATED WORK

We consider in this paper that model learning is defined as a set of methods that infer a specification by gathering and analysing system executions and concisely summarising the frequent interaction patterns as state machines that capture the system behaviour [START_REF] Ammons | Mining specifications[END_REF]. Models can be generated from different kinds of data samples such as affirmative/negative answers [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF], execution traces [START_REF] Krka | Using dynamic execution traces and program invariants to enhance behavioral model inference[END_REF][START_REF] Antunes | Reverse engineering of protocols from network traces[END_REF][START_REF] Durand | Passive testing of production systems based on model inference[END_REF], or source code [START_REF] Pradel | Automatic generation of object usage specifications from large method traces[END_REF]. Two kinds of approaches emerge from the literature: active and passive model learning methods.

Active learning approaches repeatedly query systems or humans to collect positive or negative observations, which are studied to build models. Many existing active techniques have been conceived upon the L * algorithm [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF]. Active learning cannot be applied on all systems though. For instance, uncontrollable systems cannot be queried easily, or the use of active testing techniques may lead a system to abnormal functioning because it has to be reset many times. The second category includes the techniques that passively generate models from a given set of samples, e.g., a set of execution traces. These techniques are said to be passive since there is no interaction with the system to model. Models are often constructed with these passive approaches by representing sample sets with automata whose equivalent states are merged. The state equivalence is usually defined by means of event sequence abstractions or state based abstractions. With event sequence abstractions, the abstraction level of the models is raised by merging the states having the same event sequences. This process stands on two main algorithms: kTail [START_REF] Biermann | On the synthesis of finite-state machines from samples of their behavior[END_REF] and kBehavior [START_REF] Mariani | Dynamic detection of cots component incompatibility[END_REF]. Both algorithms were enhanced to support events combined with data values [START_REF] Lorenzoli | Automatic generation of software behavioral models[END_REF][START_REF] Mariani | Automated identification of failure causes in system logs[END_REF]. In particu-lar, kTail has been enhanced with Gk-tail to generate EFSMs [START_REF] Lorenzoli | Automatic generation of software behavioral models[END_REF][START_REF] Mariani | Gk-tail+ an efficient approach to learn software models[END_REF]. The approaches that use state-based abstraction, e.g., [START_REF] Meinke | Incremental learning-based testing for reactive systems[END_REF], adopted the generation of state-based invariants to define equivalence classes of states that are combined together to form final models. The Daikon tool [START_REF] Ernst | Dynamically discovering likely program invariants to support program evolution[END_REF] were originally proposed to infer invariants composed of data values and variables found in execution traces.

None of the current model learning approaches support the generation of models describing the behaviours of components of a system under learning. This work tackles this research problem and proposes an original method for inferring models as systems of CEFSMs. Our main contribution is the detection of component behaviours in an execution trace set by means of trace analysis, event correlation, model similarity and data clustering.

CALLABLE EXTENDED FINITE STATE MACHINE

We propose in this section a model of componentsbased systems called Callable Extended Finite State Machine (CEFSM), which is a specialised FSM including parameters and guards restricting the firing of transitions. Parameters and symbols are combined together to constitute events. A CEFSM describes the behaviours of a component, which interacts with the external environment, accepting input valued events (i.e. symbols associated with parameter assignments) and producing output valued events. In addition, the CEFSM model is equipped by a special internal (unobservable) event denoted call(CEFSM) to trigger the execution of another CEFSM. This event means that the current CEFSM is being paused while another CEFSM C 2 starts its execution at its initial state. Once C 2 reaches a final state, the calling CEFSM resumes its execution after the event call(CEFSM). We do not consider in this paper that a component is able to provide results to another one. Before giving the CEFSM definition, we assume that there exist a finite set of symbols E, a domain of values denoted D and a variable set X taking values in D. The assignment of variables in Y ⊆ X to elements of D is denoted with a mapping α : Y -→ D. We denote D Y the assignment set over Y . For instance, α = {x := 1, y := 3} is a variable assignment of D {x,y} . α(x) = {x := 1} is the variable assignment related to the variable x.

Definition 1 (CEFSM) A Callable Extended Finite State Machine (CEFSM) is a 5-tuple S, s0, Σ, P, T where :

• S is a set of states, S F ⊆ S is the non-empty set of final states, s0 is the initial state,

• Σ ⊆ E = Σ I ∪ Σ O ∪ {call} is the finite set of sym-
bols, with Σ I the set of input symbols, Σ O the set of output symbols and call an internal action, • P is a finite set of parameters, which can be assigned to values of D P , • T is a finite set of transitions. A transition

(s 1 , e(p), G, s 2 ) is a 4-tuple also denoted s 1 e(p),G
---→ s 2 where : s 1 , s 2 ∈ S are the source and destination states, e(p) is an event with e ∈ Σ and p = p 1 , ..., p k a finite tuple of parameters in P k (k ∈ N), -G : D P → {true, f alse} is a guard that restricts the firing of the transition.

A component-based system is often made up of several components. This is why we talk about systems of CEFSMs in the remainder of the paper. A system of CEFSMs SC consists of a CEFSM set C and of a set of initial states S0, which also are the initial states of some CEFSMs of C. SC is assumed to include at least one CEFSM that calls others CEFSMs and whose initial state is in S0:

Definition 2 (System of CEFSMs) A System of CEFSMs a 2-tuple C, S0 where :

• C is a non-empty and finite set of CEFSMs, • S0 is a non-empty set of initial states such that ∀s ∈ S0, ∃C 1 = S, s0, Σ, P, T ∈ C : s = s0.

We also say that a CEFSM C 1 is callable-complete over a system of CEFSMs SC, iff the CEFSMs of SC can be called from any state of C 1 :

Definition 3 (Callable-complete CEFSM) Let SC = C, S0 be a system of CEFSMs. A CEFSM C 1 = S, s0, Σ, P, T is said callable-complete over SC iff ∀s ∈ S, ∃s 2 ∈ S : s call(EFSM),G --------→ s 2 , with G : C 2 ∈C\{C 1 } CEFSM = C 2
A trace is a finite sequence of observable valued events in (E × D X ) * . We use ε to denote the empty sequence.

THE CONFECT APPROACH

COnfECt (COrrelate Extract Compose) is an approach for learning a system of CEFSMs from the execution traces of a black-box system. COnfECt analyses traces and tries to detect components and theirs respective behaviours, which are modelled with CEFSMs. COnfECt aims to complement the passive model learning methods and requires a trace set to analyse them and identify the components of a blackbox system. And the more traces, the more correct the component detection will be.

The system under learning SUL can be indeterministic, uncontrollable (it may provide output valued events without querying it with a valued input event) or can have cycles among its internal states. However, SUL and its trace set denoted Traces have to obey certain restrictions to avoid the interleaving of events. We consider that SUL is constituted of components whose observable behaviours are not carried out in parallel. One component is executed at a time; a caller component is being paused until the callee terminates its execution. Furthermore, we consider having a set Traces composed of traces collected from SUL in a synchronous manner (traces are collected by means of a synchronous environment with synchronous communications). Traces can be collected by means of monitoring tools or extracted from log files. Furthermore, we do not focus this work on the trace formatting, hence, we assume having a mapper [START_REF] Aarts | Generating models of infinite-state communication protocols using regular inference with abstraction[END_REF] As depicted in Figure 1, COnfECt is composed of two main stages called Trace Analysis & Extraction and CEFSM Synchronisation. The former tries to detect components in the traces of Traces and segments them into a set of trace sets called STraces. The second stage proposes three CEFSM synchronisation strategies and provides a system of CEFSMs SC. Theses stages are presented below. We believe they can be interleaved with the steps of several passive model learning techniques, e.g., [START_REF] Mariani | Automated identification of failure causes in system logs[END_REF][START_REF] Lorenzoli | Automatic generation of software behavioral models[END_REF].

Trace Analysis & Extraction

This stage tries to identify components in the traces of Traces by means of Algorithm 1. This algorithm is based on three notions implemented by three procedures. It analyses every trace of Traces with Inspect, it segments them and builds the new trace sets T 1 , . . . , T n with Extract. Finally, it analyses the first trace set T 1 to detect other components with Separate. The algorithm returns the set STraces, which is itself composed of trace sets. Each will give birth to a CEFSM.

Algorithm 1: Inspect&Extract Algorithm input : Traces = {σ 1 , . . . , σ m } output: STraces = {T 1 , . . . , T n } 1 T 1 = {}; 2 STraces = {T 1 }; 3 foreach σ ∈ Traces do 4 σ 1 σ 2 . . σ k =Inspect(σ); 5 STraces=Extract(σ 1 σ 2 . . . σ k , T 1 , STraces);
6 STraces=Separate(T 1 , STraces); 7 return STraces;

Trace analysis

We assume that a component can be identified by its behaviour, which is materialised by valued events composed of symbols and data. We also observed in many systems, in particular in embedded devices, that the observation of controllability issues, i.e., observing output events without giving any input event before, is often the result of a component interacting with the external environment.

From these observations, we firstly analyse traces by means of a Correlation coefficient. This coefficient aims to evaluate the correlation of successive valued events, in other words, their links or relations. We define the Correlation coefficient between two valued events by means of a utility function, which involves a weighting process for representing user priorities and preferences, here towards some correlation factors. We have chosen the technique Simple Additive Weighting (SAW) [START_REF] Yoon | Multiple attribute decision making: An introduction (quantitative applications in the social sciences)[END_REF], which allows the interpretation of these preferences with weights: Definition 4 (Correlation coefficient) Let e 1 (α 1 ), e 2 (α 2 ) be two valued events of (E × D X ), and f 1 (e 1 (α 1 ), e 2 (α 2 )), . . . f k (e 1 (α 1 ), e 2 (α 2 )) be correlation factors.

Corr(e 1 (α 1 ), e 2 (α 2 )) is a utility function, defined as:

0 ≤ Corr(e 1 (α 1 ), e 2 (α 2 )) = ∑ k i=1 f i (e 1 (α 1 ), e 2 (α 2 )).w i ≤ 1 with w i ∈ R + 0 and ∑ k i=1 w i = 1.
The factors must give a value between 0 and 1. They can have a general form or be established with regard to the system context and addressed by an expert. We give below two general factor examples:

• f 1 (e 1 (α 1 ), e 2 (α 2 )) = freq(e 1 e 2 )
freq(e 1 ) + freq(e 1 e 2 )

freq(e 2 ) with freq(e 1 e 2 ) the frequency of having the two symbols one after the other in Traces and freq(e) the frequency of having the symbol e. This factor, used in text mining, computes the frequency of the term e 1 e 2 in Traces over e 1 and over e 2 to avoid the bias of getting a low factor when e 1 is greatly encountered (resp. e 2 );

• f 2 (e 1 (α 1 ), e 2 (α 2 )) = |param(α 1 ) ∩ param(α 2 )| /min(|param(α 1 )|, |param(α 2 )|) with param(α) = {p | (p := v)
∈ α} is the overlap of the shared parameters between two valued events e 1 (α 1 ), e 2 (α 2 ). We have chosen the Overlap coefficient because it is more suited for comparing sets of different sizes. We recall that the overlap of two sets X and Y is defined by |X ∩Y |/min(|X|, |Y |).

From this Correlation coefficient, we define two relations to express what a strong and weak event correlations are. Unfortunately, experts in data mining often claim that this depends on the considered context. This is why we use two thresholds X and Y in the following. Both are factors between 0 and 1, which need to be appraised, for instance after some iterative attempts.

Definition 5 (Strong and Week event Correlations)

Let e 1 (α 1 ), e 2 (α 2 ) be two valued events of (E × D X ) such that e 1 = call and e 2 = call. e 1 (α 1 ) weak-corr e 2 (α 2 ) ⇔ de f Corr(e 1 (α 1 ), e 2 (α 2 )) < X. e 1 (α 1 ) strong-corr e 2 (α 2 ) ⇔ de f Corr(e 1 (α 1 ), e 2 (α 2 )) > Y .

These relations are specialised on two valued events. We complete them to formalise the strong correlation of valued event sequences. We say that strong-corr(σ 1 ) holds when σ 1 has successive valued events that strongly correlate. We are now ready to identify the behaviours of components. We define the relation σ 1 mismatch σ 2 , which holds when the last event of σ 1 weakly correlates with the first one of σ 2 or when a controllability issue is observed between σ 1 and σ 2 :

Definition 6 (Valued event sequence correlation) strong-corr(σ) iff    σ = e(α) (E × D X ), σ = e 1 (α 1 ) . . . e k (α k )(k > 1), ∀(1 ≤ i < k) : e i (α i ) strong-corr e i+1 (α i+1 ) Let σ 1 = e 1 (α 1 ) . . . e k (α k ), σ 2 = e 1 (α 1 ) . . . e l (α l ) ∈ (E × D X ) * . σ 1 mismatch σ 2 iff    σ 2 = ε, e k (α k ) weak-corr e 1 (α 1 ), e 1 is an output symbol ∧ e k

is an output symbol

The trace analysis is performed with the procedure Inspect given in Algorithm 2, which covers every trace σ of Traces and tries to segment σ into subsequences such that sub-sequence has a strong correlation and has a weak correlation with the next sub-sequence. We consider that these sub-sequences result from the execution of components.

Trace extraction

Every trace σ ∈ Traces was segmented into σ 1 σ 2 . . . σ k by means of the relations strong-corr and mismatch. Every time σ i mismatch σ i+1 holds between two successive sub-sequences, we consider having the call of other components by the current one because both sub-sequences exhibit different behaviours. σ is modified by the procedure Extract to express these calls.

The procedure Extract(σ, T, STraces), given in Algorithm 2, takes the trace σ = σ 1 . . . σ k , transforms it and then adds the new trace into the trace set T . For a sub-sequence σ id of the trace σ = σ 1 . . . σ k , the procedure Extract tries to find another sub-sequence σ i such that strong-corr(σ id σ i ) holds (lines 10,11). The sequence σ id+1 . . . σ i-1 or σ id+1 . . . σ k (when σ i is not found) exposes the behaviour of other components that are called by the current one. If this sequence is itself composed of more than two sub-sequences, then the procedure Extract is recursively called (lines 13,14). Otherwise, the sequence is added to a new trace set T n . In σ, the sequence σ id+1 . . . σ i-1 (or σ id+1 . . . σ k ) is removed and replaced by the valued event call(CEFSM := C n ) (lines 12,19). Once, the sequence σ is covered by the procedure Extract, it is placed into the set T . Let us consider the example of Figure 2, which illustrates the transformation of a trace σ. This trace was initially segmented into 6 sub-sequences. A) We start with σ 1 . We suppose the first sequence that is strongly correlated with σ 1 is σ 5 . σ is transformed into σ 1 call(CEFSM := C 2 )σ 5 σ 6 . Recursively, Extract(σ 2 σ 3 σ 4 , T 2 ) is called to split σ = σ 2 σ 3 σ 4 . B) We suppose σ 2 σ 4 strongly correlates, hence, σ is modified and is equal to σ = σ 2 call(CEFSM := C 3 )σ 4 . The sequence σ 3 is a new trace of the new set T 3 . As σ is completely covered, σ is added to the new trace set T 2 . C) We go back to the trace σ at the sub-sequence σ 5 . As there is no more sub-sequence that strongly correlates with σ 5 , the end of the sequence σ, i.e., σ 6 , is extracted and placed into the new trace set T 4 . The trace σ is now equals to σ 1 call(CEFSM := C 2 )σ 5 call(CEFSM := C 4 ). This trace is placed into the trace set T 1 . At the end of this process, we have recovered the hierarchical component call depicted in Figure 3. And we get four trace sets.

When the procedure Extract terminates, Algorithm 1 yields the set Straces = {T 1 , T 2 , . . . , T n } with T 2 , . . . , T n some sets including one trace and T 1 a set of modified traces, originating from Traces. As we do not suppose that Traces expresses the behaviours of only one component, T 1 may include traces resulting from different components. Hence, T 1 needs to be analysed as well and possibly partitioned.

Trace clustering

The trace set T 1 is analysed with the procedure Separate, which returns an updated set STraces. The procedure aims at partitioning T 1 into trace sets exclusively composed of similar traces. We consider that similar traces exhibit a behaviour provided by the same component. We evaluate the trace similarity with regard to the symbols and parameters shared between pairs of traces. Several general similarity coefficients are available in the literature for comparing the similarity and diversity of sets, e.g., the wellknown Jaccard coefficient. We have once more chosen the Overlap coefficient because the symbol or parameter sets used two traces may have different sizes.

Definition 7 (Trace Similarity coefficient) Let σ i (i = 1, 2) be two traces in (E × D X ) * . Σ(σ i ) = {e | e(α) is a valued event of σ i } is the sym- bol set of σ i . P(σ i ) = {p | e(α) is a valued event of σ i , (p := v) ∈ α} is the parameter set of σ i . Similarity Trace (σ 1 , σ 2 ) = Overlap(Σ(σ 1 ), Σ(σ 2 )) + Overlap(P(σ 1 ), P(σ 2 ))/2.
With this coefficient, the procedure Separate builds the sets of similar traces from T 1 by means of a clustering technique. In short, the coefficient is evaluated for every pair of traces to build a similarity matrix, which can be used by several clustering algorithms to find equivalence classes. The clustering techniques here return the clusters of similar traces T S 11 , . . . T S 1k . These sets are added into STraces. The sets T S 1i are marked with the exponent S to denote they are composed of execution traces observed from components that were not called by other components at the beginning of these executions.

The CEFSM Synchronisation Stage

This stage aims to organise the component synchronisation with regard to the event call(CEFSM). The choice of integration of this stage within an existing model learning approach mainly depends on the steps of this approach. But it sounds natural to focus on models, here CEFSMs, for applying different synchronisation strategies. Thus, we consider that the set STraces has been lifted to a system of CEF-SMs SC = C, S0 by means of a passive learning method, e.g., [START_REF] Lorenzoli | Automatic generation of software behavioral models[END_REF]. C is composed of the CEFSM C i such that C i is derived from a trace T i ∈ STraces. In particular, a marked set T S j (composed of traces observed from components that were not called by other components) gives the CEFSM C j = S j , s0 j , Σ j , P j , T j whose initial state s0 j is also an initial state of the system of CEFMs SC (s0 j ∈ S0).

We propose three general CEFSM synchronisation strategies in the paper, which provide systems of CEFSMs having different levels of generalisation. These strategies are implemented in Algorithm 3 and described below:

Strict synchronisation (Algorithm 3 lines(1,2)). We want a system of CEFSMs SC in such a way Algorithm 2: Procedures Inspect, Extract and Separate

1 Procedure Inspect(σ) : σ 1 σ 2 . . . σ k is 2
Find the no-empty sequences σ 1 σ 2 . . . σ k such that: that a CEFSM of SC cannot repetitively call another CEFSM. The callee CEFSM must be composed of one acyclic path only (one behaviour). This strategy aims to limit the over-generalisation problem, i.e. the fact of generating models expressing more behaviours than those given in the initial trace set Traces. This strategy was already almost achieved by the previous stage Trace Analysis & Extraction. Indeed, each subsequence extracted from a trace is placed into new trace set T i and is replaced by one valued event of the form Call(CEFSM := C i ). Hence, it remains to transform the trace sets of STraces into CEFSMs for obtaining a system of CEFSMs organised with a strict synchronisation.

σ = σ 1 σ 2 . . . σ k , strong-corr(σ i ) (1≤i≤k) , (σ i mismatch σ i+1 ) (1≤i≤k-1) ; 3 Procedure Extract(σ = σ 1 σ 2 . . . σ k , T,
Weak synchronisation (Algorithm 3 lines(3-16)). This strategy aims at reducing the number of components and allows repetitive component calls. The previous stage has possibly created too much trace sets, therefore the system of CEFSMs SC may include several similar CEFSMs modelling the functioning of the same component. The similarity notion is once more defined evaluated by a Similarity coefficient.

Definition 8 (CEFSM Similarity coefficient) Let C i = S i , s0 i , Σ i , P i , T i (i = 1, 2) be two CEFSMs. Similarity CEFSM (C 1 ,C 2 ) = Overlap(Σ 1 , Σ 2 ) + Overlap(P 1 , P 2 )/2.
The similar CEFSMs of SC are once more grouped by means of a clustering technique, which uses the Similarity coefficient. The CEFSMs of the same cluster are joined by means of a disjoint union. Furthermore, the guards of the transitions

s 1 call(CEFSM),G
---------→ s 2 are updated accordingly so that the correct CEFSMs are being called. In addition,

every transition s 1 call(CEFSM),G ---------→ s 2 is replaced by a self loop (s 1 , s 2 ) call(CEFSM),G
---------→ (s 1 , s 2 ) by merging the states s 1 and s 2 .

Strong synchronisation (Algorithm 3 lines(4-20)). This strategy provides more over-generalised models by generating callable-complete CEFSMs. It is based on the previous strategy: we join the similar CEFMSs of SC into bigger CEFSMs and we transform the transitions labelled by call as previously. In addition, we complete every state s with new selfloop transitions of the form s call(CEFSM),G ---------→ s so that all the CEFSMs become callable-complete over the system of CEFSMs SC. This strategy seems particularly interesting for modelling component-based systems having independent components that are started any time.

We studied the integration of COnfECt with several passive learning approaches. We have implemented a combination of the approach with kTail to generate Labelled Transition Systems (LTS). The source code as well as examples are available in [START_REF] Salva | Model Learning of Componentbased Systems[END_REF].

We are also studying the integration of COnfECt with Gk-tail to generate systems of CEFSMs. Figure 4 illustrates how the COnfECt and Gk-tail steps can be organised. The COnfECt steps are given with white boxes. We call the resulting approach Ck-tail.

Step 2 corresponds to the first step of COnfECt. We placed it after Step 1 (trace merging) to have less trace to analyse, and before Step 3 (guard generation) to measure the event correlation on symbols and real values. The CEFSM Synchronisation step of COn-fECt is the fifth step of Ck-tail. It is performed af- ter the CEFSM tree generation, and before Step 6 (state merging) because it sounds more interesting to group the similar CEFMS and to merge their equivalent states after, as more equivalent states should be merged if we follow this step order. We illustrate this integration with a example based upon a real system (an IOT (Internet Of Things) thermostat) in [START_REF] Salva | Model Learning of Componentbased Systems[END_REF].

ACKNOWLEDGMENT

Research supported by the French Project VASOC (Auvergne-Rhne-Alpes Region) https://vasoc. limos.fr/ We have presented COnfECT, a method that complements existing passive model learning approaches to infer systems of CEFSMs from execution traces. COnfECT is able to detect component behaviours by analysing traces by means of a Correlation coefficient and a Similarity coefficient. In addition, COn-fECT proposes model synchronisation strategies, which help manage the over-generalisation of systems of CEFSMs.

In future work, we intend to carry out more evaluations of COnfECT on several kinds of systems. The main issue concerns the implementation of monitors and mappers, which are required to format traces. We also intend to tackle the raise of the abstraction level of CEFSMs. Indeed, while the trace analysis, the successive computations of the Correlation coefficient could also be used to perform event aggregation in accordance with event correlation and some CEFSM structural restrictions.

  performing abstraction and returning traces as sequences of valued events of the form e(p 1 := d 1 , . . . , p k := d k ) where p 1 := d 1 , . . . , p k := d k are parameter assignments.

Figure 1 :

 1 Figure 1: The COnfECt approach overview

Figure 2 :

 2 Figure 2: Sequence extraction example

  STraces ∪ {T n }; 9 σ p is the prefix of σ up to σ id ;10 if ∃i > id: strong-corr(σ id σ i ) then 11 σ i is the first sequence in σ id . . . σ k such that strong-corr(σ id σ i ); 12 σ := σ p σ id call(CEFSM := C n )σ i . . . σ k ; 13 if (iid) > 2 then 14 Extract(σ id+1 . . . σ i-1 , T n ); σ p σ id call(CEFSM := C n ); 20 if (kid) > 1 then 21 Extract(σ id+1 . . . σ k , T n ); i , σ j ) ∈ T 2 ComputeSimilarity Trace (σ i , σ j ); 29 Build a similarity matrix; 30 Group the similar traces into clusters {T 11 , . . . T 1k }; 31 STraces = STraces \ {T 1 } ∪ {T S 11 , . . . , T S 1k };

Algorithm 3 :

 3 CEFSM synchronisation strategies input : System of CEFSMs SC = C, S0 , strategy output: System of CEFSMs SCf = C f , S0 f 1 if strategy = Strict synchronisation then 2 i ,C j ) ∈ C 2 Compute Similarity CEFSM (C i ,C j );5 Build a similarity matrix; 6 Group the similar CEFSMs into clusters {Cl 1 , . . .Cl k }; 7 foreach cluster Cl = {C 1 , . . . ,C l } do 8 C Cl :=Disjoint Union of the CEFSMs C 1 , . . . ,C l ;9 if s0 i ∈ S0(1 ≤ i ≤ l) then 10 S0 f = S0 f ∪ s0 Cl ; 11 C f = C f ∪ {C Cl }; 12 foreach C i = S, s0, Σ, P,V, T ∈ C f do 13 foreach s 1 call(CEFSM),G --------→ s 2 ∈ Twith G : CEFSM = C m do 14 Find the Cluster Cl such that C m ∈ Cl; 15 Replace G by G : CEFSM = C Cl ; 16 Merge (s 1 , s 2 ); 17 if strategy = Strong synchronisation then 18 foreach C i = S, s0, Σ, P, T ∈ C f do 19 Complete the states of S with self-loop transitions so that C i is callable-complete; 20 return SC f

Figure 4 :

 4 Figure 4: Ck-tail: Integration of COnfECt with Gk-tail


Ilya Yuskevich
email: ilya.yuskevich@skolkovotech.ru

Rob Vingerhoeds
email: rob.vingerhoeds@isae.fr

Alessandro Golkar
email: a.golkar@skoltech.ru

Two-dimensional Pareto frontier forecasting for technology planning and roadmapping

Keywords: Technology forecasting, technology planning, trend extrapolation, Pareto frontiers

Technology evolution forecasting based on historical data processing is a useful tool for quantitative analysis in technology planning and roadmapping. While previous efforts focused mainly on onedimensional forecasting, real technical systems require the evaluation of multiple and conflicting figures of merit at the same time, such as cost and performance. This paper presents a methodology for technology forecasting based on Pareto (efficient) frontier estimation algorithms and multiple regressions in presence of at least two conflicting figures of merits. A tool was developed on the basis of the approach presented in this paper. The methodology is illustrated with a case study from the automotive industry. The paper also shows the validation of the methodology and the estimation of the forecast accuracy adopting a backward testing procedure.

I. INTRODUCTION

Forecasting technology evolution and developing research investment plans are at the core of the mission of a technology planning and roadmapping function of any engineering organizations. Companies need to identify and capture those trends, in order to remain ahead of their competition. Evolution forecasts are often done based on the intuition of experts and senior executives, and are complemented by methods such as technology scouting and other approaches adopted by strategy departments. Quantitative methods based on historical data analysis are decision-making support methods that help decision makers identifying patterns and defining evolution trends from data. In particular, trend extrapolation methods stand out from other technology forecasting approaches by being simple, fully quantitative and free from subjectivity biases. Trend extrapolation can be mathematically modelled using quantitative inputs and its accuracy can be likewise estimated. The disadvantage of this type of methods lies in its simplicity. First of all, there is always a risk of the emergence of unknown events which can break evolution trend (breakthrough innovations, economic crisis, and so on). This kind of events are ignored during the numerical and unsupervised process and should be taken into account by human intervention into the mathematical model (what at the same time introduce new biases). Secondly, classical growth curves trend extrapolation [START_REF] Meade | The use of growth curves in forecasting market development -a review and appraisal[END_REF] address onedimensional forecasting ignoring the fact that reality is more complex in a sense that a technology or a system can rarely be evaluated by just one figure of merit (FoM). In reality, for any given year a technology needs to be evaluated under multiple FoMs, thus defining an n-dimensional surface of Pareto efficient design points.

This paper proposes a methodology to quantify technology evolution using a Pareto frontier forecasting approach assuming evaluations based on two competing Figures of Merit. A similar approach to solve this problem was proposed by researchers at Portland State University, under the name of Technology Forecasting Using DEA (TFDEA). With TFDEA, they adopted the data envelopment analysis (DEA) approach for technology forecasting to estimate the relative efficiency of each point and use this information to estimate the rate of change of technology evolution to verify Moore's law [START_REF] Anderson | Further examination of Moore's law with data envelopment analysis[END_REF], predict US Jet Fighter Aircraft introductions [START_REF] Inman | Predicting U.S. jet fighter aircraft introductions from 1944 to 1982: A dogfight between regression and TFDEA[END_REF], forecast the performances of wireless communication systems [START_REF] Anderson | Technology forecasting for wireless communication[END_REF] and estimate performance of the hybrid electric vehicle [START_REF] Jahromi | Forecasting hybrid electric vehicles using TFDEA[END_REF]. Latest methodological advances in TFDEA development proposed frontiers segmentation and local rate of change calculation to improve accuracy in technology evolution forecasts [START_REF] Lim | Improving forecast accuracy by a segmented rate of change in technology forecasting using data envelopment analysis (TFDEA)[END_REF].

We propose an alternative procedure for technology evolution forecasting targeting two main goals. The first goal is to forecast future nonlinear Pareto frontiers using a direct approach, differing from the ambition of TFDEA of accurately estimating technology rate of change. The second goal is to incorporate growth curve models (such as the S-curve model) into the analysis, as proven patterns describing technological progress.

Our proposed approach, being also visual, is suited for use in concurrent design studies, such as for technology roadmapping for example, where multiple experts convene and integrate their knowledge using models. The resulting framework is therefore suited for strategic planning and roadmapping and facilitates its future integration in a concurrent design data exchange platform such as CEDESK [START_REF] Knoll | A coordination method for concurrent design and a collaboration tool for parametric system models[END_REF].

Furthermore, our approach accounts for physical limits in estimating technology evolution, which allows for additional validation of the results. By providing engineering teams tools for forecast adjustments, we allow experts to decide between different evolution scenarios and avoid fallacies in conclusion due to reliance on a purely automated approach. The approach furthermore informs users on the value of residual errors in evolution estimates, as well as its determination coefficients, giving them a chance to validate the accuracy of forecasts.

The remainder of the paper is structured as follows. Section II provides background and theory. Section III describes the mathematical approach here proposed for technology evolution forecasting. Successively, the results of the case study are discussed along with validation. The paper ends with conclusions and identification of avenues for future work.

II. BACKGROUND AND THEORY

The input for the proposed forecasting procedure is a time-sampled dataset of related technologies, systems or services with at least two conflicting figures of merit (that is, for which a tradeoff has been identified). It is assumed that each FoM has a monotonous behaviour over the evolution of the system or service of interest, such as increasing quality or decreasing cost and development time. In measuring of productive efficiency theory each FoM is classified either as input or as output [START_REF] Farrell | The Measurement of Productive Efficiency[END_REF].

During system development we aim to maximize outputs (e.g. quality, power, performance) and minimize inputs (e.g. cost, mass, consumption). Technological progress occurs in such a way that inputs in average tend to decrease while outputs increase at the same time (which means, in turn, that average systems become more efficient over time). This is the case for example in data storage technology, where devices such as hard drives becomes cheaper and more capable at the same time over the last three decades.

Out of all possibilities, we can identify three mathematically different trade spaces that we define as "input-input", "input-output" and "output-output", respectively, as shown in Fig. 1. Inputs are all FoMs we wish to minimize (as they are proxy for resources, hence cost). Outputs are FoMs we wish to maximize (as they represent production, or other beneficial attribute contributing to value delivery). For the first type of trade space (Fig. 1a), the origin is an utopia point. Utopia is defined as the ideal optimum, which however cannot be achieved due to the opposing nature of the two FoMs. For the second type of trade space (Fig. 1b) the [inf,inf] point is an utopia. Finally, for the third type of trade space (Fig. 1c) we have an utopia line (asymptote) coinciding with the y-axis.

To simplify the explanations and visualization this paper is concerned with two-dimensional Pareto frontiers only. However, we foresee to extend this approach to analyze n-dimensional Pareto frontiers, where each FoM again may be either input or output. With an increasing number of FoMs the number of possible trade space types is increasing as well. So to have a single unified mathematical process for all types of trade spaces, we are proposing to convert all inputs to outputs by taking outputs as the reciprocals of the inputs. For example, for cars we have two reciprocal metrics of the fuel consumption -miles per gallon (MPG) and liters per 100 Kilometers where first one is an output and second one is an input. We can easily switch between these metrics during pre-or postprocessing while core process works exclusively with outputs.

Year-by-year frontier movements can be mathematically expressed by means of multiple growth curves (one growth curve for each radial direction on a tradespace). The type of the fitting curves is the second attribute for the classification. The simplest case (Fig. 2) is the translational progress with constant rate of change in absence of physical limits. The growth curves in this case are straight lines.

In the second case, (Fig. 3) technology evolution rate of change slows down with time and asymptotically approach the physical limit. Such situations occur more often in applications and commonly described as the S-curve growth model.

In the most general case we have several growth curve models in a single trade space. This means that the shape of frontier is changed in time.

For instance, the double S-curve like the one depicted on Fig. paradigm shifts. Because of such influential events the convex frontier may became concave which can be mathematically expressed as a superposition of two or more growth curves.

III. MATHEMATICAL PROCEDURE

The proposed approach of frontiers estimating and forecasting is illustrated in the Object Process Model (OPM) [START_REF] Dori | Object-Process Methodology[END_REF] shown in Fig. 5.

After the dataset is obtained and all FoMs are converted to outputs we construct efficient frontiers by identifying Pareto efficient solutions for each year. It is impossible to use directly the standard Pareto frontier definition in our estimation algorithm. Instead, we require the Pareto frontier to satisfy the following properties:

1) No point shall be ahead of the frontier (e.g. in the unfeasible region); 2) The frontier is a monotonically decreasing function in a FoM space (first derivative is greater than zero); 3) The frontier can be either convex or concave on the entire domain, but its first derivative must be monotonic (no concavity changes).

The latter statement is worth discussing in depth because the concavity of the Pareto frontier in the output-output space is not obvious, and traditional econometrics approaches such as Data Envelopment Analysis (DEA) fail at estimating results for non-convex Pareto frontiers. Pareto front convexity is not always a realistic assumption in technology trade space analysis, due to the nonlinear physical processes underlying engineering tradeoffs. For instance, the set of frontiers of thermal versus propulsive efficiencies for commercial aircraft engines have been shown to be non-convex [START_REF] Epstein | Aeropropulsion for Commercial Aviation in the Twenty-First Century and Research Directions Needed[END_REF].

The problem of the Pareto optimal solutions determination in the non-convex regions can be solved by applying the adaptive weighted sum (AWS) method [START_REF] Kim | Adaptive weighted sum method for multiobjective optimization: a new method for Pareto front generation[END_REF]. However, in our case this method is not applicable due to the inverse nature of the considered problem. AWS is the Pareto frontier generator which means that the model of the system is known and mathematically defined. This situation is common for the model-based systems engineering. In contrast, in the considered problem the model of the system is unknown, the set of solutions is limited and given as algorithm input. Thus, instead of Pareto frontier generation (multi-objective optimization) we deal with Pareto frontier estimation problem (curve fitting).

Further the exact mathematical routine is discussed.

For each dataset year we sample a set of nondominated points. By definition point xi is nondominated if there is no any other point xj for which F k (xi) < F k (xj) for ∀k, j, where F is the vector function of multiple FoMs (which corresponds to dominated points filtering step on Fig. 5).

The orange circles on Fig. 6 represent the set of nondominated points of some given year for our case study. The frontier consisted of this set is not smooth or, more precisely, doesn't meet the formulated above conditions for valid Pareto frontier. This means that due to the finite number of existing products on the market (lack of data) some points are not lying on true Pareto frontier which is current cutting-edge for the given technology. To find this true Pareto frontier we need to apply a curve-fitting procedure (referred to as frontier estimation algorithm on OPM diagram on Fig. 5).

The problem of finding this true frontier can be formulated as standard linear optimization problem of minimizing distances between true frontier ftrue and nondominated set f nd under the condition of dominance ftrue over f nd and ftrue monotony:

min ftrue -f nd ∞ ftrue ≥ f nd (1) f ′′ true ≥ 0 or f ′′ true ≤ 0
After we've calculated set of frontiers for all years (we call it instance frontiers set in a sense that we've not applied interpolation in a time domain yet). The result of solving this problem for two different years is shown on Fig. 6.

We perform the time domain interpolation along set of radial directions (the concept of this step is illustrated on Fig. 7).

Each direction has its own combination of FoM weights and represents very important concept of market segmentation (e.g. if FoM 1 is engine power and FoM 2 is MPG the direction A stands for the powerful cars whereas C stands for the economical).

Points A ′ , A ′′ , B ′ , B ′′ , C ′ , C ′′ are inputs to our approach (described as follows). Their location is found as intersection of piecewise interpolated efficient frontiers and radial directions A, B and C. The resulting point series could be fitted by any growth curve. In this paper the Gompertz curve was used in straight line form [START_REF] Winsor | The Gompertz Curve as a Growth Curve[END_REF]:

log log L y = a -bx (2)
Before fitting, the physical limit L or its allowed interval has to be set or estimated as regression model parameter if dataset is full enough to make a reliable prediction. In the two-dimensional space set of all physical limits in all possible radial directions forms a limiting curve to which frontiers approach asymptotically. There are several possibilities to define this limiting curve. One can define it directly, but this is redundant and impractical because this curve has the same shape as most recent frontiers. Therefore, it is enough to set the estimates of some parameters of this curve e.g. absolute or relative maximal value of each FoM (L1 and L2 on Fig. 7). Then, the averaged shape of a several the most recent frontiers is estimated and scaled to L1 and L2 (curve of physical limits estimation step on Fig. 5).

In our methodology curve fitting procedure is applied to all radial directions simultaneously with couple of additional conditions to preserve the right shape curve transformation in time (see Fig. 234). The resulting problem is a nonlinear convex optimization problem (NLP). To give an example let's formulate NLP for the Gompertz curve-case model and also require the frontier to preserve concave behaviour in time:

min a,b log log L f (t) -(a -bt) 2 log log L f (t) -(a -bt) ≤ 0 (3) bi-1 -2bi + bi+1 ≤ 0 0.2(ai -ai-1) ≤ ai+1 -ai ≤ ai -ai-1
Where i = 1...n is the indexes of the radial directions set, t is the timescale, f (t) is the instant frontiers set, ai, bi are the parameters of Gompertz curves for each radial direction, Li is the physical limit estimation for each radial direction.

First equation determines the least-squares minimization of the fitting residual errors. Second equation require the growth curves to dominate the instance frontiers set in all points. Third and fourth equations constrain the optimization parameters and mutually link them in the FoMs space to preserve the right shape of the frontiers.

Here we would like to draw the attention to the following. After time domain interpolation with growth curves most of the products that were the best at their time actually no longer lie on cutting edge. Consequently, frontiers estimated independently from time (blue dots on Fig. 8) do not always coincide with true frontier set which depends also on time trends of trade-off evolution. This corresponds to real world experience; a technological frontier always goes ahead of mass market products. From this perspective it is important that proposed analysis allows to calculate two kinds of slacks separately: delays of best practise products and delays of all products from a general technological frontier.

IV. CASE STUDY

We applied our approach to the estimation of Pareto frontiers in the the automotive industry using a publicly available dataset (as obtained from http://www.cars-data.com). The data set used for this case study contains more than 5 000 car models with petrol engine and manual transmission and covers over 40 years. The tradeoff is the engine power vs fuel consumption in miles per gallon (output-output type). An example of the data included in the data set is shown in Table 1. Fig. 9 shows the data sets of cars plotted on two FoMs of interest: maximum engine power (as measured in horsepower) and average fuel consumption in miles-per-gallon (MPG). This tradeoff is representative of a typical compromise a customer makes between performance and cost efficiency when purchasing a new vehicle. This of course does not mean that there are no other factors which could affect the decision. Among such factors are the level of comfort, price, body type, trunk capacity, and so on. However, the chosen tradeoff is probably a main technology-driven one in the automobile industry. The analysis proposed here can (and has to) be extended to account multiple figures of merit at the same time. However, for illustration purposes in this paper, we limit the analysis here to two FoMs, with no loss of generality, and leave multi-dimensional analysis for future work.

As we account for two FoMs only in this case study, we focused on data points different from each other in engine power and fuel consumption, and neglected car variants distinguished by other characteristics. For example, we did not consider in the data set those cars that have the same engine power and fuel consumption values, and different between each other under other characteristics (for instance automatic versus manual transmission, and different engine types such as diesel and hybrid). Fig. 10 show the generated families of Pareto frontiers exhibiting different physical limits. Suppose we have two estimates of physical limits for our tradeoff -pessimistic and optimistic one. The historical data are the same for both cases.

V. VALIDATION

We estimated the accuracy of our proposed Pareto forecasting method using a backward testing approach. That is, we partition our data set into training and validation subsets considering a given threshold year, and verify the accuracy of our forecasts. The error of forecasting is the difference between the real frontier (using known data) and the estimated one (using only data before the given threshold year).

The error itself could be measured either in years (as time difference between two corresponding frontiers) or as normalized distance in FoM space (normalized with respect to maximal variance of FoMs in the dataset). We used normalized distance since the estimated models could have different performance in different regions of the Pareto curve, due to varying rate of change as in the case of Scurve models. Fig. 11 illustrates the logic of the accuracy estimation. The normalized distance between points A and A ′ is the accuracy estimation for point A by proposed backward (or any other) test:

σ(A) = σ 2 1 + σ 2 2 = = f1(A) -f1(A ′ ) max(f1) -max(f1) 2 + f2(A) -f2(A ′ ) max(f2) -max(f2) 2 (4)
In a given formula f1(A) and f2(A) are the frontier values estimated with full dataset and f1(A ′ ) and f2(A ′ ) are the frontier values estimated with cutted dataset for the same radial direction.

Where Lupper and L lower are the upper and lower threshold years respectively. The average error is calculated for frontier 2027 (10 years prediction).

Parametric contour plot of and is shown on Fig. 14. As can be seen from this figure accuracy is more correlated with α than with β which means that recent data (cars from 90s, 00s and 10s) have more influence on the prediction (recent data is more sufficient). This is not necessarily means that this is true for any dataset. We are not using any time weighting in our algorithm. Such situation occurs because this time period is characterized with more competitive and diverse market. This basically means more data which makes trends more evident.

The last test is intended to confirm the sufficiency of a dataset. Our case study is quite big (2160 data points). Obviously most of the points are not Pareto optimal and, because of that, do not determine the trend. The process of iterative exclusion of random points from the full dataset and comparison of the results of frontier forecasting gives us the estimation of the dataset sufficiency. The output of this test is shown on Fig. 15. If the threshold accuracy for us is 10% then the sufficient dataset should contain at least 400-500 data points.

VI. CONCLUSION

We propose a Pareto forecasting approach to estimate technology evolution over time. This approach helps users to visualize technology evolution and facilitates the identification of efficient and nonefficient technologies and supports decision-making in technology investment by setting realistic target performances and forecasting a development time for future technology. At the same time, to be effective, the proposed approach requires proper calibration in terms of growth curve and physical limits selection in characterizing technologies.

Future work will extend this approach to n-dimensional Pareto frontier forecasting, and development of additional case studies in industrial applications. We also foresee experimentation of the approach in concurrent design studies for technology planning and roadmapping.

Fig. 1 :

 1 Fig. 1: Trade space classification by FoMs direction.

  4 may occur due to the emergence of disruptive innovations and

Fig. 2 :

 2 Fig. 2: Constant rate of change progress.

Fig. 3 :

 3 Fig. 3: Slowing rate of change progress.

Fig. 4 :

 4 Fig. 4: Progress with two different growth curve models (e.g. in case of disruptive innovation along FoM 2).

Fig. 5 :

 5 Fig. 5: OPM diagram of the proposed procedure.

Fig. 6 :

 6 Fig. 6: Two results of frontier estimation algorithm (for two different cut-off years).

Fig. 7 :

 7 Fig. 7: Time domain interpolation concept.

1 Fig. 8 :

 18 Fig. 8: Fitting the efficient frontiers in time domain along one of the radial directions with Gompertz curves.

Fig. 9 :

 9 Fig. 9: Cars case study.

Fig. 10 :

 10 Fig. 10: Cars case study frontiers.

Fig. 11 :

 11 Fig. 11: The error calculation.

Fig. 12 :

 12 Fig. 12: Frontiers generated during backward test.

Fig. 13 :

 13 Fig. 13: Normalized error of 1972-1994 timeframe dataset with respect to 1972-2017.

Fig. 12

 12 Fig.12show the Pareto frontiers of the case study calculated using the full data set versus the reduced data set (threshold year 1994).The normalized error chart of the backward test shown on Fig.13. A forecast error is a function of a dataset sufficiency and of a chosen approximation curve shape. It is clear from the figures that

Fig. 15 :

 15 Fig. 15: Dataset sufficiency estimation.

TABLE I :

 I Cars dataset sample

	Model	Cost, e	Model year	MPG	Engine Power, Hp
	Volkswagen Golf Sportsvan 1.4	34 970	2016	43.5	150
	Smart forfour	11 195	2015	56.0	71
	Porsche 911 Targa 4	148 776 2015	19.0	370
	Toyota Celica Liftback 2000 ST	10 596	1980	24.0	89
	Hyundai Atos Multi 1.0i GLS	9 525	1998	37.3	55