In this paper, we present a similarity measure between behavioural interfaces of Web services. This measure computes the difference value of simulation between two service interfaces. In our previous work we implemented an algorithm to detect the exact location of differences between service interfaces in a tool namely BESERIAL [1]. The similarity measure is based on the results of the detection algorithm. In our case study, this measure is used to select the most suitable service to substitute a previous one, which is no longer available at design time.
This paper is structured as follows. First, Section 2 introduces the running example. Section 3 gives details on the quantitative simulation measure. Section 4 shows some experimental results. Then, Section 5 gives a panel of the related work on the diagnosis of differences in service interfaces. Finally, Section 6 concludes and sketches the future work. 2
As a running example, we consider a scenario where a car factory interacts with one of its provider of goods and services. The service provider describes its operations in WSDL and the control flow is established using BPEL process protocol. Figure 1 (a) illustrates the activity diagram of the provided interface of the provider service. This provider processes service and goods orders from the car factory. The provider receives a service order which can be updated by its client (the car factory) only if the invoice is not sent yet (see the flow which loops back to the ReceiveServiceOrder activity). Once the service invoice is sent, the provider waits for the transfer from the client to finally send him the ShipmentTrackingNumber (STN). On the other hand, when a GoodsOrder is received, a GoodsInvoice is immediately sent to the client. This former can either send his CreditCardDetails, to pay the invoice, or update his order by sending a new GoodsOrder (see the flow which loops back to the ReceiveGoodsOrder activity). The client pays the invoice, and then the provider sends him the STN.
If the service provider is no more available, the car factory will send an invitation to tender to substitute the old provider and all candidates will provide their behavioural interfaces. The selection criterion is that the provided interface of the new partner must conform as much as possible to the required interface by the car company. In other words, the new provider is such as there exists a minimum number of changes in the new provided interface in order to simulate the old provided interface.
Receive GoodsOrder GoodSseInndvoice
Fig. 1. Activity diagram and FSM of the provided interface.
FSM modeling: In our approach we model the behaviour of a Web service
interface using Finite State Machines [
An FSM is a tuple (S, L, T, s0, F ) where: S is a finite set of states, L a set of events (actions), T the transition function (T : S × L −→ S). s0 is the initial state such as s0 ∈ S, and F the set of final states such as F ⊂ S. The transition function T associates a source state s1 ∈ S and an event l1 ∈ L to a target state s2 ∈ S. In this model, a transition is defined as a tuple containing a source state, a label and a target state.
Figure 1 (b) illustrates the FSM of the running example which describes the behavioural interface of the service provider. We only consider the observable behaviour of a service, thus internal activities are hidden. Activities meant to send and to receive messages are modeled. The message m is denoted by >m (respectively <m) when it is sent (respectively received). Each conversation initiated by a client starts an execution of the corresponding FSM.
We use the following notations (examples refer to the FSM depicted in the right side of the Figure 1(b)): – s• is the set of outgoing transitions from s.
(e.g. GoodsInvoiced• = {(GoodsInvoiced,<CreditCardDetails,Paid), (GoodsInvoiced, <GoodsOrder,GoodsOrdered) }). – Label(t) is the label1 of the transition t.
(e.g. Label((GoodsInvoiced,<CreditCardDetails,Paid))=<CreditCardDetails) – The Label operator is generalised to a set of transitions. For example, if T = Sin=1{ti} then Label (T ) = Sn
i=1{Label (ti)}; where n =k T k. – k X k is the cardinality of the set X.
In our previous work, we implemented an algorithm which is meant to detect the exact location of changes while comparing two FSMs P and P 0 (which respectively models the old provider and the new provider interfaces). A difference is detected if and only if the new interface does not simulate the behaviour of the previous interface. The outcome is a set Res of tuples (si, ti, sj, tj) where si and sj are states of P and P 0 respectively, while ti and tj are either null values or outgoing transitions of si and sj respectively.
Figure 2 shows three differences between P and P 0. The first difference is a deletion of the operation < ServiceOrder , which means that the new provider does not allow its client to update its service order. This difference causes an incompatibility with the required interface of the client as he can not use this operation any more. The second difference is an addition of the operation < Transfer . 1 In deterministic FSMs, ∀t1 ∈ s•, t2 ∈ s• : Label (t1) 6= Label (t2).
However, this difference does not cause any incompatibility as the added operation provides a new option to its client. The third difference is the modification of the operation > STN by the operation > ASN (Advanced Shipment Notice). An incompatibility will arise because the client can not recognize this new operation.
P FSM (old provider)
Order <GoodsOrder
GoodsOrdered >GoodsInvoice <GoodsOrder
GoodsInvoiced <CreditCardDetails
Quantitative simulation: In the detection algorithm, P and P 0 are traversed in parallel. A set of reached pair of states Rps is built such as Rps ⊆ S × S0, where S is a set of P ’s states and S0 is a set of P 0’s states. For each pair of states (si, sj) ∈ Rps, we compute a quantitative simulation function Qs. This function returns a score of differences between si’s outgoing transitions and sj’s outgoing transitions. Qs : S × S0 → [0..1] is defined as follows:
Qs((si, sj)) = (1
Pik=D1iff ((si,sj))k Weight(Di)+kLabel(si•)∩Label(sj•)k
kDiff ((si,sj))k+kLabel(si•)∩Label(sj•)k Where: Diff ((si, sj)) is a set of differences pinpointed at the state pair (si, sj) such as Diff ((si, sj)) ⊆ Res, and Di ∈ Diff ((si, sj)) for i = 1.. k Diff ((si, sj)) k. The function Weight returns a penalty value2 for each type of difference, and 0 6 Weight (Di ) < 1. The sum of all penalties in the state pair is added to the score of the common labels of the outgoing transitions. Common labels of the outgoing transitions of si and sj refer to the case where no difference is detected. Thus, a highest score is attributed (see (1): k Label (si•) ∩ Label (sj•) k). To compute the quantitative simulation of the pair state, the sum of difference score and similarity score is divided by the number of these differences and similarities between the outgoing transitions of si and sj (see (1): k Diff ((si, sj)) k + k Label (si•) ∩ Label (sj•) k). For example, in Figure 2, if the value of the deletion penalty is set to 0.5, then the quantitative simulation is: Qs((ServiceOrdered , ServiceOrdered )) = 0.5+1 = 0.75. 1+1 2 How penalty values are set is out of the scope of this paper. if, si• = {} otherwise (1)
Mean quantitative simulation: Once the quantitative simulation is computed to all state pairs, a mean quantitative simulation value of P and P 0 can be defined as follows :
Mqs(P, P 0) =
PkQsk Qs(P Si) i=1 k Rps k Where: P Si is a pair of states such as P Si ∈ Rps for i = 1.. k Rps k. In the running example, if all the penalty values are set to 0.5 then the mean quantitative simulation is: Mqs(P, P 0) = 0.875. 4
For validation purposes, we built a test collection consisting of 20 process scenarios from the xCBL3 textual description of order management choreographies. These two-party choreographies describe possible document exchanges between trading partners in an Order Management business process. (2) 1.2 1 e 0.8 u l a V ion 0.6 lt a u m iS 0.4 0.2
Mean Quantitative Simulation 0 2 4 6 8 10 12 14 16 18 20
Test Number
In BESERIAL4, one interface is compared to a collection of interfaces. In Figure 3, the graph shows which interface yields less incompatibilities with respect to the interface given as reference. In this example, the interface which simulates as much as possible the given one yields a mean quantitative simulation value of 0.97. The worst result is 0.14. The interfaces in tests number 14, 15 and 16 are selected as candidates to substitute the old service. 5
Compatibility test of interfaces has been widely studied in the context of Web
service conversations. Most of approaches, which focus on the behavioural
dimension of interfaces, rely on similarity calculus to check, at design time, whether
3 XML Common Business Library (http://www.xcbl.org/).
4 http://www-clips.imag.fr/mrim/User/ali.ait-bachir/WebServices/WebServices.html
or not interfaces described for instance by automata are compatible [
In [
In this paper we focused on the calculus of the differences between two behavioural interfaces. Ongoing work aims at extending this work towards two directions: i) detecting complex incompatibilities including structural aspects, ii) guiding analysts in fixing detected incompatibilities. As we compare two different versions of a same service, we identify adequately the delta introduced by the new version. Nevertheless, if we compare two completely different services, the semantics of operations or data types must be considered.