Despite their importance, Web service business protocols are not always published with service interfaces, which hinders automatic management. A solution is to extract them from past executions. One of the raised issues is the discovery of temporal constraints called timed transitions, which are not explicitly recorded. In this paper we present our approach for discovering such transitions. We de ne a class of patterns called proper timeouts which are equivalent to timed transitions, and present a polynomial algorithm for extracting these patterns.3
A very important ambition associated with Web services relates to
looselycoupled integration, which is already partially carried out by the fact that
services use widespread standards. A good exibility is possible only if users know
how to interact with a service. This requires to associate with services elaborate
descriptions (such as WSDL) enabling a good understanding of their execution
semantics. However descriptions like WSDL are not su cient for a sophisticated
and automatic use of services because they provide only static properties [
Business protocols o er automatic reasoning mechanisms with many
applications, such as correctness veri cation, compatibility testing, etc. However they
are not often speci ed in real life services. Potential reasons include lack of
time during implementation or uncontrolled evolution. A solution is then to
infer this protocol from the conversation logs of a service. Direct applications
are re-engineering issues, such as implementation correctness checking or service
evolution. Once automated this extraction process could be applied in service
discovery architectures [
Discovering service protocols includes many technical challenges: cleaning
logs from \noise", identifying the di erent conversations, de ning assessable
models, developing re ning tools for an interactive extraction, etc. The rst
contribution to this problem has been proposed in [
This paper presents our approach for extracting timed transitions from
conversation logs.4 We de ne a class of patterns called proper timeouts which reveal
the presence of timed transitions in the protocol. We propose a characterization
of the set of proper timeouts satis ed by the logs, which leads to a polynomial
extraction algorithm. This work is an extension of [
We de ne an episode as a sequence of two message names. Given an episode = hm; m0i, an occurrence of is a sequence of two consecutive occurrences of m and m0 in the logs. The occurrence duration of an episode occurrence is the di erence between the message timestamps. The minimal (respect. maximal) occurrence duration of an episode is the smallest (respect. greatest) occurrence duration of all its occurrences. The occurrence duration interval (ODI) of an episode is the interval which includes all its occurrence durations. The minimal (respect. maximal) occurrence duration of a set of episodes is the minimum (respect. maximum) of all the minimal (respect. maximal) occurrence durations of these episodes. The occurrence duration interval (ODI) of a set of episodes is the interval which includes all the occurrence durations of these episodes. For each message m, we denote by Pm the set of episodes whose rst message is m.
Given two sets of episodes A and B, we say that A precedes B (denoted by
A B) if ODI(A) is before ODI(B).5 We say that A and B are not comparable
(denoted by A k B) if A B and B A. Given A; B Pm, we show that:
if there exists a timed transition between the state from which the transitions
corresponding to the elements of A are going out, and the one from which the
4 Technical results are presented in an extended version of this paper [
We de ne a proper timeout as a triplet P T (m; A; B), where m is a message and A; B Pm. We say that logs L satisfy the proper timeout P T (m; A; B), which is denoted by L P T (m; A; B), if: 8 A <
B 8 2 Pm n (A [ B); f g , A [ B : 8 Z 2 fA; Bg; 8 X; Y Z (X; Y 6= ); (X [ Y = Z) ) (X Y ) : (1)
Given a message m and A; B Pm, we show that: if there exists a timed transition in the protocol, between two states s1 and s2 such that the sets of transitions going out of s1 and s2 respectively are in bijection with A and B, then there exist A0 A and B0 B such that L P T (m; A0; B0). Since each timed transition involves the satisfaction of a proper timeout, we can nd all of them. However we can discover more proper timeouts than there are timed transitions, if some messages always take longer to be sent or received than messages associated with other transitions of the same state. Thus we will say that: a satis ed proper timeout reveals the presence of a potential timed transition.
We show that: for practical purposes, proper timeouts are the best possible representations of timed transitions. That justi es the relevance of the development of a timed transition discovery method based on the research of the proper timeouts satis ed by the logs. 3
The complexity of a basic \generate and test" method for extracting proper timeouts is exponential. Instead, we propose a nice characterization of the set of satis ed proper timeouts, which leads to a polynomial algorithm. This characterization, formalized by Theorem 1, states that: the proper timeouts satis ed by the logs and related to message m are exactly given by the pairs of consecutive elements of the partition of Pm satisfying (2). Thus, partitioning all sets Pm gives us all the proper timeouts satis ed by the logs.
Theorem 1. Consider a mesage m, im 2 IN , and fP m(1); P m(2); : : : ; P m(im)g a partition of Pm. The following assertions are equivalent:
P m(2) : : :
P m(im) i im; 8 X; Y
P m(i) (X; Y 6= ); (X [ Y = P m(i)) ) (X Y ) : ( P m(1)
We propose a polynomial algorithm, called partitionPm, for constructing this partition in an incremental way. The input of algorithm partitionPm comprises a message m, the set Pm, and the ODIs of all episodes in Pm. The output is the partition of Pm satisfying (2). is constructed by inserting one by one the elements of Pm in such a way that (2) is satis ed at each step. In order to describe the general step of the algorithm, let us consider that is already partly constructed. Let be an episode of Pm not yet considered. A single pass is made over the partition to determine (i) whether the ODIs of some elements of overlap ODI( ), and (ii) between which sets of is situated according to . If there is no overlap, a new set containing is created and inserted into the partition in compliance with . If the overlap takes place with only one element of , is simply inserted in this set. If the overlap occurs between and several parts of , they are necessarily consecutive according to ; as such they are merged and is inserted into the resulting set. As for each episode 2 Pm only one pass is made over the partition, the complexity is O(jPmj2).
The global method for extracting all the proper timeouts satis ed by the logs is divided in two steps. The rst one is a preprocessing of the data, performed in order to obtain the set of messages, the set of episodes, and the ODIs of all episodes. A single pass is made over the logs, during which the occurrence duration of each sequence of two consecutive messages is calculated. The second step consists in constructing all sets Pm, and running algorithm partitionPm for each of them. The logs' size being far greater than the number of episodes, the rst step is the most costly in term of running time. Thus the complexity of the global algorithm is O(jLj).
We have implemented our discovery process to test its scalability. In order to easily have a big amount of data, we have also implemented a log generator which creates conversation logs from a given business protocol by mimicking the behaviour of a service. Results of our experiments con rm the complexity results we have established formally. The nal test will be to run our algorithm on real-life data in further experiments.