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.
Web service interfaces can be described from two aspects: i) The structural aspect models the provided operations, and the schema of the messages that the service can send and receive. These operations can be described by using WSDL for instance. ii) The behavioural aspect refers to the control flow between the operations and establishes their inter-dependencies. In conversational services, such behavioural interfaces can be described using BPEL for instance. Nevertheless, Finite State Machines (FSM) is the formal model adapted in our work to describe behavioural interfaces [7]. In this paper, we do not consider semantic aspects of operation definitions.
Client applications are meant to consume provided operations in a service interface. Conversations between a client application and a service are loosly coupled. Thus, if the service evolves and provides a new interface, then incompatibilities may arise as a client application does no longer match the new interface. The provided interface of a service evolves from a previous definition to a new one by means of basic differences (addition, deletion and modification of operations). The exact location of these differences can be detected and resolved instead of programing a new client application whose required interface is compatible with the new interface definition. However, if the service is no more available, there is no choice left to developers than to substitute this service by another one, at design time. If there exists no service whose interface simulates the old service interface, it is interesting to discover another service whose interface has a minimum number of differences with the previous one. 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.
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. 3 Quantitative simulation FSM modeling: In our approach we model the behaviour of a Web service interface using Finite State Machines [6]. Techniques exist to transform behavioral service interfaces defined in other languages (e.g. BPEL) into FSMs(see for example the WS-Engineer tool [3]). In the FSMs considered in this paper, transitions are labelled with messages to be exchanged. When a message is sent or received, the corresponding transition is fired.
An FSM is a tuple (S, L, T, s 0 , F ) where: S is a finite set of states, L a set of events (actions), T the transition function (T : S × L −→ S). s 0 is the initial state such as s 0 ∈ S, and F the set of final states such as F ⊂ S. The transition function T associates a source state s 1 ∈ S and an event l 1 ∈ L to a target state s 2 ∈ 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
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
X 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 (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 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 . 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 . 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. Quantitative simulation: In the detection algorithm, P and P are traversed in parallel. A set of reached pair of states Rps is built such as Rps ⊆ S × S , where S is a set of P 's states and S is a set of P '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 × S → [0..1] is defined as follows:
Where: Diff ((si, sj)) is a set of differences pinpointed at the state pair (si, sj) such as Diff ((si, sj)) ⊆ Res, and D i ∈ Diff ((si, sj)) for i = 1.. Diff ((si, sj)) .
The function Weight returns a penalty value 2 for each type of difference, and 0 Weight(D i ) < 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): Label (si•) ∩ Label (sj•) ). 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):
Diff ((si, sj)) + Label (si•) ∩ Label (sj•) ). 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 1+1 = 0.75.
2 How penalty values are set is out of the scope of this paper.
Mean quantitative simulation: Once the quantitative simulation is computed to all state pairs, a mean quantitative simulation value of P and P can be defined as follows :
Where: P S i is a pair of states such as P S i ∈ Rps for i = 1.. Rps . In the running example, if all the penalty values are set to 0.5 then the mean quantitative simulation is: Mqs(P, P ) = 0.875.
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. In BESERIAL 4 , 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.
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 or not interfaces described for instance by automata are compatible [2]. The behavioural interface describes the structured activities of a business process. Checking interface compatibility is thus based on bi-similarity algorithms [5]. These approaches do not deal with the quantification of interface simulation.
In [6], authors introduced a technique to diagnosis message structure missmatches between service interfaces and to fix them with adapters. An extention of this technique is applied to reslove missmatches between service protocols. The proposed iterative algorithm builds a missmatch tree to help developers to choose the suitable adapter each time and incompatibility is detected. However, this technique can only be applied to protocols which describe a sequence of operations. More complex flow controls, such as loops and options, are not taken into consideration. Recent research has addressed interface similarity measures issues. In [4], authors present a similarity measure for labeled directed graphs inspired by the simulation and bi-simulation relations on labeled transition systems. The presented algorithm returns a value of a simulation measure but does not tell us more about the location of incompatibilities.
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.
This author is partially funded by the Web Intelligence project granted by the French Rhône-Alpes Region