Composition of heterogeneous software components is required in many domains to build complex systems. However, such compositions raise mismatches between components. Software adaptation aims at generating adaptors to correct mismatches between components to be composed. In this paper, we propose a formal approach based on Petri nets which relies on mapping rules to generate automatically adaptors and check compatibilities of components. Our solution addresses both signature and behaviour level and covers both asynchronous and synchronous communication between components. State space of the Petri model is used to localise mismatches.
Component-based development aims at facilitating the construction of very
complex and huge applications by supporting the composition of simple building
existing modules, called components. The assembly of components offers a great
potential for reducing cost and time to build complex software systems and
improving system maintainability and flexibility. The reuse of a component and
substitution of an old component by a new one are very promising solution [
A component is a software unit characterised by an interface which describes
the services offered or required by the component, without showing its
implementation. In other terms, only information given by a component interface are
visible for the other components. Moreover, interfaces may describe component
information at signature level (method names and their types), behaviour or
protocol (scheduling of method calls) and method semantics.
A software component is generally developed independently and is subject to
assembly with other components, which have been designed separately, to create a
system. Normally ‘glue code’ is written to realise such assembly. Unfortunately,
components can be incompatible and cannot work together. Two components are
incompatible if some services requested by one component cannot be provided
by the other [
Incompatibilities are identified: (i) at signature level coming from different
names of methods, types or parameters, (ii) at behaviour or protocol level as
incompatible orderings of messages, and (iii) at semantic aspect concerning senses
of operations as the use of synonyms for messages or methods [
There exist some works aiming at working out mismatches of components
which remain incompatible, even in the optimistic approach. These works
generally use adaptors, which are components that can be plugged between the
mismatched components to convert the exchanged information causing mismatches.
For example, the approach proposed in [
Other works are based on formal methods such as interface automata, logic
formula and Petri nets which give formal description to software interface and
behaviour [
In [
Interface automata are introduced by L.Alfaro and T.Henzinger [
An interface automaton A = hSA, SAinit, ⌃ A, ⌧ Ai where : – SA is a finite set of states, – SAinit ✓ SA is a set of initial states. If SAinit = ; then A is empty, – ⌃ A = ⌃ AO [ ⌃ AI [ ⌃ AH a disjoint union of output, input and internal actions, – ⌧ A ✓ SA ⇥ ⌃ A ⇥ SA.
The input or output actions of automaton A are called external actions denoted by ⌃ Aext = ⌃ AO [ ⌃ AI. A is closed if it has only internal actions, that is ⌃ Aext = ; ; otherwise we say that A is open. Input, output and internal actions are respectively labelled by the symbols ”?”, ”!” and ”; ”. An action a 2 ⌃ A is enabled at a state s 2 SA if there is a step (s, a, s0) 2 ⌧ A for some s0 2 SA.
example will be used throughout this paper. The system contains two components Client and Server which have been designed separately. On the one hand,
username (!uid). If Client is not authenticated by Server (!nAck and !errN ), it exits. Otherwise, Client loops on sending read or update requests. A read request (!req) is followed by its parameters (!arg), then Client waits the result (?data).
word (?pwd), it either accepts the client access request (!ok) or denies it (!nOk).
ceives a read request (?query), it performs a local action (; readDB) and sends the appropriate data (!data). Server can execute an update request (?update). Figure 1.a depicts interface automaton Server. It is composed of six states (s0, . . . s5), with state s0 being initial, and nine steps, for instance (s0, ?uid, s1). Some arcs are dashed, they will be referred in section 4. The sets of input, output and internal actions are given below: - ⌃ SOerver ={ok, nOk, data}, - ⌃ SIerver = {uid, pwd, logout, query, update}, - ⌃ SHerver= {readDB}.
?uid ?pwd ?query ?update ?logout !data !ok !nOk !uid !pwd !req !arg !exit ?data ?ack ?nAck ?errN 2.1
Let A1 and A2 two automata. An input action of one may coincide with a corresponding output action of the other. Such an action is called a shared action. We define the set shared(A1, A2) = (⌃ AI1 \ ⌃ AO2 ) [ (⌃ AO1 \ ⌃ AI2 ), e.g. set Shared(Client, Server) = {uid, pwd, update, data}.
The composition of two interface automata is defined only if their actions are
disjoint, except shared input and output ones. The two automata will synchronize
on shared actions, and asynchronously interleave all other actions [
?uid
(⌃ AH1 \ ⌃ A2 = ; ) ^ (⌃ AH2 \ ⌃ A1 = ; ) ^ (⌃ AI1 \ ⌃ AI2 = ; ) ^ (⌃ AO1 \ ⌃ AO2 = ; )
If A1 and A2 are composable interface automata, their product A1 ⌦ A2 is the interface automaton defined by: 1. SA1⌦ A2 = SA1 ⇥ SA2 , 2. SAin1t⌦ A2 = SAin1t ⇥ SAin2t, 3. ⌃ AH1⌦ A2 =(⌃ AH2 [ ⌃ AH1 ) [ shared(A1, A2), 4. ⌃ AI1⌦ A2 =(⌃ AI1 [ ⌃ AI2 ) \ shared(A1, A2), 5. ⌃ AO1⌦ A2 =(⌃ AO1 [ ⌃ AO2 ) \ shared(A1, A2), 6. ⌧ A1⌦ A2 ={(v, u), a, (v0, u) | (v, a, v0) 2 ⌧ A1 ^ a 62 shared(A1, A2) ^ u 2 SA2 } [ { (v, u), a, (v, u0) | (u, a, u0) 2 ⌧ A2 ^ a 62 shared(A1, A2) ^ v 2 SA1 } [ { (v, u), a, (v0, u0) | (v, a, v0) 2 ⌧ A1 ^ (u, a, u0) 2 ⌧ A2 ^ a 2 shared(A1, A2)}. An action of Shared(A1, A2) is internal for A1 ⌦ A2. Moreover, any internal action of A1 or A2 is also internal for A1 ⌦ A2 (3). The not shared input (resp. output) actions of A1 or A2 are input (resp. output) ones for A1 ⌦ A2 (4, 5). Each state of the product consists of a state of A1 together with a state of A2 (1). Each step of the product is either a joint shared action step or a non shared action step in A1 or A2 (6).
In the product A1 ⌦ A2, one of the automata may produce an output action
that is an input action of the other automaton, but is not accepted. A state of
A1 ⌦ A2 where this occurs is called an illegal state of the product. When A1 ⌦ A2
contains illegal states, A1 and A2 can’t be composed in the pessimistic approach.
In the optimistic approach A1 and A2 can be composed provided that there is
an adequate environment which avoids illegal states [
The automata associated with Client and Server are composable since
definition 2 holds. However, their synchronous product is empty, in fact (s0, s00) is an
illegal state: Client sends password (!pwd) while Server requires a username
(?uid), causing a deadlock situation. Thus, Client and Server are incompatible.
As mentioned in the introduction, two incompatible components can be
composed provided that there exits an adaptor to convert the exchanged information
causing mismatches. In particular, mapping rules are used to adapt exchanged
action names between the components. Such rules may be given by designer. For
more details, we refer reader to [
Mapping rules for incompatible components A mapping rule establishes correspondence between some actions of A1 and A2. Each mapping rule of A1 and A2 associates an action of A1 with more actions of A2 (one-for-more) or vice versa (more-for-one).
(L1, L2) 2 (2⌃ Aex1t ⇥ 2⌃ Aex2t ) such that (L1 [ L2) \ shared(A1, A2) = ; and if |L1| > 1 (resp. |L2| > 1) then |L2| = 1 (resp. |L1| = 1).
A mapping (A1, A2) of two composable interface automata A1 and A2 is a set of mapping rules associated with A1 and A2.
We denote by ⌃ (A1,A2) the set {a 2 ⌃ Aex1t [ ⌃ Aex2t|9 ↵ 2 (A1, A2) s.t a 2 ⇧ 1(↵ ) [ ⇧ 2(↵ )}, with ⇧ 1(hL1, L2i) = L1 and ⇧ 2(hL1, L2i) = L2 are respectively the projection on the first element and the second one of the couple hL1, L2i. Observe that each action of ⌃ (A1,A2) is a source of mismatch situation between A1 and A2.
Example 2 Consider again the components of example 1. In Client a read request is structured into two parts (!req and !arg), whereas it is viewed as one part (?query) in Server. A mapping rule is necessarily to map {!req, !arg} to {?query}. The sets of mapping rules between Client and Server (Client,Server) and ⌃ (Client,Server) are defined as follows: – (Client,Server) = {↵ 1, ↵ 2, ↵ 3, ↵ 4} with : ↵ 1 = ({!req, !arg}, {?query}), ↵ 2 = ({?ack}, {!ok}), ↵ 3 = ({?nAck, ?errN }, {!nOk}), ↵ 4 = ({!exit}, {?logout})} – ⌃ (Client,Server) =
{req, arg, query, ack, ok, nAck, nOk, errN, exit, logout} 4
In A1 ⌦ A2, the actions of ⌃ (A1,A2) are interleaved asynchronously since they are named differently in A1 and A2. In fact, A1 ⌦ A2 doesn’t deal with correspondence between actions of ⌃ (A1,A2). Moreover, the product A1 ⌦ A2 doesn’t accept shared actions which have incompatible ordering in A1 and A2. For instance Client sends a password followed by a user name, whereas Server accepts the last message and then the former one. It is obvious that A1 ⌦ A2 cannot be used to check the compatibility of A1 and A2. In this context, an adaptor component, must be defined. Such an adaptor is mainly based on the set (A1, A2) and is a mediator between A1 and A2. It receives the output actions specified in ⌃ (A1,A2) from one automaton and sends the corresponding input actions to the other. In case of incompatible ordering of shared actions, the adaptor works out such situations by receiving, reordering and sending such actions to their destination component.
automaton adaptor. 4.1
Petri Net Construction for Components Adaptation Contrary to interface automata formalism, the Petri net model is well suited to validate interactions between components, especially whenever events reordering is required. In fact, Petri nets allow to store resources (e.g. messages) before their use. In this paper, we use a Petri net model to adapt two interface automata according to a set of mapping rules given by the user of the components. The approach we propose consists of building a Petri net which mimics the component interfaces. Furthermore, the Petri net also contains a set of transitions, one per matching rule, which represent the adaptor component. More details will be given below.
First, we give the basic definitions of a Petri net model. For more details, we
refer reader to [
Definition 6 (Labeled Petri Net) A Petri net N is a tuple hP, T , W, i where : – P is a set of places, – T is a set of transitions such that P \ T = ; , – W is the arc weight function defined from P ⇥ T [ T ⇥ P to N. – is a label mapping defined from T to an alphabet set ⌃ [ { ✏}. A marking is a function M : P ! N where M (p) denotes the number of tokens at place p. The firing of a transition depends on enabling conditions. Definition 7 (Enabling) A transition t is enabled in a marking M iff 8 p 2 P , M (p) W (p, t).
marking M . Firing t yields a new marking M 0, 8 p 2 P , M 0(p) = M (p) W (p, t) + W (t, p). from M0. An arc M! from M .
Definition 9 (State Space ) A state space, denoted by S(N, M0), of a marked labelled Petri net (N, M0) is an oriented graph of accessible markings starting t M 0 of S(N, M0) means that M 0 is obtained by firing t s s0 ; a(s,s0) a s s0 s s0 a a1 ...
an !a(s,s0)
?as,s0 (d) ↵ a ... a ... (e)
↵ a1 an (a) (b)
(c)
The algorithm described below returns a marked labelled Petri net (N, M0) composed of three parts dedicated for A1, A2 and a set of matching rules. These parts are glued by mean of places which model communication channels and are associated with external actions of A1 and A2, i.e. the actions of sets Shared(A1, A2) and ⌃ (A1,A2).
For each state s (resp. external action a) of A1 and A2, the algorithm generates a corresponding place s (resp. a) in N . Furthermore, the places corresponding to initial states of interface automata will be initially marked in N .
Fig. 2.a, 2.b and 2.c show how to translate steps of A1 and A2. The gray full circles represent communication places. An internal action s! ;a s0 is represented by a transition ; a(s,s0) which has an input place s and an output place s0 (Fig 2.a). An output action s! !a s0 is represented by a transition !a(s,s0) which has an input place s and two output places s0 and a. A firing of !a(s,s0) produces a token in place a modelling an emission of a message a (see Fig 2.b). Fig 2.c gives the translation of an input action s! ?a s0, here each firing of ?a(s,s0) models a reception of a message a.
Fig. 2.d and 2.b show how to translate the mismatch rules. For each mismatch rule ↵ = ({!a}, {?a1, . . . , ?an}) of (A1, A2), a transition ↵ is added. The input places of ↵ are a1 . . . an and its output place is a. Each firing of ↵ models the receptions of a1 . . . an and the emission of a (see Fig 2.d). The same pattern is applied for a rule ↵ = ({?a1, . . . , ?an}, {!a}). Fig 2.e shows the translation of a rule ↵ = ({!a1, . . . , !an}, {?a}) or ↵ = ({?a}, {!a1, . . . , !an}). In this case, each firing of ↵ models the reception of a and the emissions of a1 . . . an. These transitions simulate the adaptor.
For analysis requirement (next section), transitions associated with mismatch rules are labelled by the rule names and the others by the corresponding action names.
Algorithm 1 BuildP etriN et ————————————————————————— Inputs A1 = hS1, A1, I1, T1i, A2 = hS2, A2, I2, T2i and of rules Output (A1, A2) a set A labelled Petri Net N =hP, T, W, i and its initial marking M0 Initialization P =; , T = ; Begin // Generation of places corresponding to the states of A1 and A2 for each state s 2 S1 [ S2 do add a place s to P If s 2 SAin1it [ SAin2it then M0(s) =1 else M0(s) =0
Endif endfor // Places simulating direct communication between A1 and A2 for each action a 2 Shared(A1, A2) do
add a place a to P endfor // Places simulating indirect communication between A1 and A2 for each action a 2 ⌃ (A1,A2) do
add a place a to P endfor // Transitions simulating steps of A1 and A2
a for each transition s1! s2 2 T1 [ T2, (with 2 { !, ?, ; }) add a transition a s1,s2 to T
(a s1,s2) = a add the arcs s1 ! a s1,s2 and a s1,s2 ! s2 to W case: =0!0 : add the arc !as1,s2 ! a to W =0?0 : add the arc a ! ?as1,s2 to W endcase endfor // Transitions simulating adaptor of A1 and A2 for each ↵ 2 (A1, A2) do add a transition ↵ to T
(↵ ) = ↵ case: ↵ 2 { ({!a}, {?a1, . . . , ?an}), ({{?a1, . . . , ?an}, {!a})} :
add the arcs ai ! ↵ , i 2 1 . . . n, and ↵ ! a to W , ↵ 2 { ({!a1, . . . , !an}, {?a}), ({?a}, {!a1, . . . , !an})}:
add the arcs a ! ↵ and ↵ ! ai, i 2 1 . . . n, to W endcase endfor return (N, M0) End
Fig. 3 gives a labelled and marked Petri net N associated with Client and Server according to the set of rules (Client, Server) (which are defined in example 2). For sake of clarity, communication places are duplicated and transitions are represented by their labels. Moreover, transitions ?update, !update
?update and place update are represented differently, a special attention will be accorded to them in the next section. The left and right parts of the net are respectively dedicated to Client and Server, they are glued by mean of communication places uid, pwd, update and data. These latter correspond to the actions of Shared(Client, Server) and are used to simulate direct communications between Client and Server.
The lower part of the net represents the adaptor, it contains four transitions ↵ 1, ↵ 2, ↵ 3 and ↵ 4, each one represents a rule of (Client, Server). The communication places req, arg, query, ack, ok, nAck, nOk, errN , exit and logout are used to link the three parts and correspond to the actions of ⌃ (Client,Server). Places s0 and s00 are initially marked in N , they translate the initial places of Client and Server automata.
Synchronisation Semantics between Components At this level, the Petri net construction models only asynchronous communication between two components. Such kind of communication may be source of incoherence as illustrated by the following scenario: – Client: Authentication, – Server: Okay message, – Client: update request, – Client: read request, – Server: response for the read request, – Server: data base update.
It is worth noting that the result of the read request may be incorrect. This occurs whenever the required information is concerned by the update operation. To work out this problem, Client and Server must synchronise on update action. Therefore, we propose to enrich the Petri net construction to strengthen synchronisation between transitions which are related to critical shared actions (e.g. update action): (1) such transitions must be fired by pair (w.r.t some critical action, one for an output step and the other for an input step). (2) The communication places of critical external actions are not useful since here messages are not stored. (3) The set of critical actions, denoted by Synch, is an input of the algorithm. The set of transitions related to Synch is denoted by TSynch. For instance, to avoid the previous scenario, action update is considered as critical, so transitions !update and ?update must be fired simultaneously. Place update is omitted, Sync = {update} and TSync = {?update, !update}. 4.3
In order to model synchronous communication between components, transitions of TSynch are fired by pair. Further conditions are necessary to fire simultaneously a pair of transitions t and t0 belonging to TSynch from a state s : - (t) = a and (t0) = a . - Both t and t0 are enabled in s.
As mentioned in the introduction, the compatibility control of components
is made by using the state graph. In order to do this, we adapt the notion of
illegal state for our approach. We use the classical definition [
- s has no successor and contains at least a marked communication place, - or there is an enabled transition t of Tsynch, with (t) = !a but no enabled transition t0 with (t0) = ?a in s.
The state graph of the marked Petri net shown in Fig. 3 contains no illegal state, therefore Client and Server can be composed according to the set of rules (Client, Server).
Example 3 Consider again the example of Fig. 2 and let us omit the dashed arcs. The corresponding state graph contains two illegal states. Fig. 4 exhibits a particular sequence of the state graph, containing the two illegal states (gray states): 1. In (s3s03), transition !update is enabled but cannot be fired since transition ?update is not enabled within the state. This means that Client issues an update request which is not assumed by Server at this state. 2. State (s3s06, exit) has no successor in the state graph and a marked communication place ( exit). Such a mark means that Client has sent an exit request which will not be covered by Server.
s0s00 !pwd s0s01, pwd !uid s0s02, pwd, uid ?uid s1s02, pwd ?pwd s3s06, logout ↵ 4
s3s06, exit !exit Software Adaptation is widely used for adapting incompatible components, viewed as black boxes. In this paper, we have presented a Petri net construction for software adaptation at signature and behavioural levels based on mapping rules. These latter are used to express correspondence between actions of components. The Petri net construction reflects the structure of component interface automata to assemble and their corresponding mapping rules. The proposed construction is incremental, e.g. rules can be easily added or replaced. Our approach allows both synchronous and asynchronous communications, unlike the other approaches referred in this paper. In our future work, we plane to extend our Petri net construction to take into account adaptation of components with temporal constraints.