Service Substitution Analysis in Protocols Evolution Context Ali Khebizi1 , Hassina Seridi-Bouchelaghem2 , Imed Chemakhi3 , and Hychem Bekakria3 1 LabStic Laboratory, 08 May 45 University, Guelma -Algeria- ali.khebizi@gmail.com 2 LABGED Laboratory, University Badji Mokhtar Annaba, Po-Box 12, 23000, Algeria seridi@labged.net 3 Computer science Institute, 08 May 45 University, Guelma -Algeria- Chemakhi.imed@gmail.com,hychem.bekakria@gmail.com Abstract. As Web services become the dominant technology for in- tegrating distributed information systems, enterprises are more inter- ested by these environments. However, enterprises socio-economic envi- ronments are more and more subject to changes which impact directly business processes published as Web services. In parallel, if at change time some instances are running, the business process evolution will im- pact the equivalence and substitution classes of the actual service. In this paper, we present an equivalence and substitution analysis in dynamic evolution context. We suggest an approach to identify residual services that can substitute a modified one, where ongoing instances are pending. Our analysis is based on protocol schema matching and on real execution traces. The proposed approach has been implemented in a software tool which provides some useful functionalities for protocol managers. Keywords: Service protocol, Protocol equivalence, Protocol substitution, Dy- namic evolution, Execution path, Execution trace. 1 Introduction Web services are the new generation of distributed software components. They generate a lot of enthusiasm among different socio-economic operators’s which favourite these environments to deploy applications at a large scale. Standard- ization is a key concept, so actors uses standards like WSDL [1], UDDI [2] and SOAP [3] to publish, discover, invoke and compose distributed software. In this context, intra and inter enterprises applications integration is more flexible, easy and transparent. Moreover, integration process is accelerated among internet stakeholders. In Web services technology, two elements are fundamental for providing a high interactivity level between service providers and service requesters. The first one is service interface, described via the standard WSDL. The second element is service protocol (Business Protocol), which describes the provider’s business process logic. A Business process consists of a group of business activities un- dertaken by one or more organizations in pursuit of some particular goal [4],[5]. For example, booking flight tickets and B2B transactions. In addition, Busi- ness process specifies the service external behaviour by providing constraints on operations order, temporal constraints [6] and transactional constraints [7], in order to promote correct conversations, as service operations can’t be invoked in an aleatory order. However, if a service protocol is published in the Web (its interface and its protocol), at a moment during its life cycle, it can be in- voked by some clients. Furthermore, in large public applications (e-commerce, e-government, electronic library, . . . ), thousand of clients are invoking the ser- vice at the same time and every one has reached a particular execution level. In parallel, as enterprises are open systems, changes are permanent and inevitable. Consequently, business processes may evolve to adapt to environment changes that affect real word. In this case, related service protocols must be updated, otherwise services execution may produce incoherences when they are invoked. This context is called dynamic protocol evolution. In dynamic protocol evolution, the evolved service protocol may not be able to satisfy initial customer requirements. Furthermore, some services may fails and clients must find new services that can replace actual one. Services substitution analysis deal with checking if two services satisfy the same functionalities; if they support the same conversation messages [5]. This concept is very useful in case of service failure, in order to search an other one to replace it. In some cases, this analysis can serve to search and locate a new service with the same functionalities but with a higher quality of service (Qos). It can also be used to test whether a new proposed version, that expresses evolution or maintenance requirements, is yet, equivalent to an obsolete one and for finding new services that can support conversations required by standards like ebXML [8], Rosetanet [9] and xCBL [10]. Service evolution is expressed through the creation and de- commission of its different versions during its lifetime. [11] Service protocol update induces challenges for filtering which services, already identified and compared to old version, remain equivalents or can replace the evolved one. The major constraint is related to active instances that have al- ready executed some operations based on old version. In this context, we must deal with historical executions in substitution analysis process. In this paper we are interested to dynamic evolution and we focus on change impact analysis on service protocol substitution. A set of methods are exposed to check if new service version, can be yet substituted by the hole (or partially) set of services that were discovered corresponding to the obsolete version. The remainder of the paper is structured as follow. We start by describing the problem and exposing our motivations, in section 2. In section 3, we propose our formal approach and algorithms for managing substitution aspects in dy- namic evolution context. Section 4, describes system architecture and software tool implementation. We expose related works in section 5 and conclude with a summary and directions for future works in section 6. Proceedings ICWIT 2012 13 2 Problem and Motivations Every organisation (enterprises, administrations, banks, ...etc.) is an open sys- tem which is, eventually, impacted by environment changes. In order to sur- vive, organization must adapt there business processes. Today’s organizations information systems -reflecting business processes- are exposed on the Web as services (interfaces and protocols) and every business process changes induce, immediately, these two descriptions update. The challenge in dynamic protocol evolution context is to identify, among the set of already identified class substitu- tion services, the subset of those that can, yet, replace an actual service after its specification changes, with respect to past interactions. Addressing service pro- tocols substitution analysis, after protocol evolution, responds to the following motivations: 1. Ensuring service execution continuation for active instances. 2. Ensuring correct interactions between customers and providers by specifying the new service substitution class. 3. In dynamic environments, like Web services, transactions are long dura- tion and resources consumer. It’s not conceivable to restart execution from scratch because loss of work is catastrophic for customers. 4. In real time systems and critical applications (aeronautics, e-commerce, med- ical systems, control systems, manufacture,. . . ), brutal service stop is catas- trophic for organizations. It is imperative to treat with precision and accu- racy services that can substitute an evolved or failed one. 5. In large public applications (e-libraries, e-government, e-learning. . . ), a large number of active instances are pending, at a time. Manual management of these instances is cumbersome and an automatic support is required to ensure that only pertinent services are proposed for substitution process. The main issue is to manage protocol substitution with respect to historical traces. Starting a new search query for locating new services, based on the new version, is expensive and in addition, returned services that can be inconsistent with old version. To illustrate our motivations, we present in Fig.1 a real world scenario. In this scenario, service protocol P have some equivalent services (P1 , P2 , . . . , Pn ) and other services (P3 , P4 , . . . Pm ) can substitute it. However, service P has evolved to a new version P ′ (for different reasons). Evolution operations added a new message cancelOrder and removed the message Order validated. At evo- lution time, active instances (instance 1, instance 2,. . . ), are running and have reached a particular execution level. In order to be able to substitute service P in case of problems, protocol manager want to know: Which protocols remain in conformance with the new protocol specification and can replace it ? 3 Analysing Substitution in Dynamic Protocol Evolution One of the most challenging issues in dynamic protocol evolution context is to find potential protocols for substitution, where instances are running accord- Proceedings ICWIT 2012 14 Fig. 1. After Protocol evolution of P to P’ which services can substitute P ′ ? ing to old protocol. To address this analysis, we introduce three fundamental concepts: service protocol model, execution path and execution trace. – A service protocol: We use finite state machine to represent service pro- tocols. In this model states represent different phases that a service may go through during its interaction with a requester. Transitions are triggered by messages sent by the requester to the provider or vice versa [4], [5]. A message corresponds to operation invocation or to its reply, as shown in Fig 1. A finite state machine is described by the tuple: P = (S, s0 , F, M, R), consisting of: • S : A finite set of states; • s0 ∈ S: is the protocol initial state; • F : Set of final states machine, with F ⊂ S; • M : Finite set of messages; • R ⊂ (S × S × M ): Transitions set. Each one involves a source state to a target state following the message receipt. – Execution trace: Service behaviour traces is a finite sequence of opera- tions (a, b, c, d, e, ...). It represents events that service have invoked, from its beginning to the actual state. We note : trace(P, i) to express the execution trace performed by an active instance i in a protocol P . – Complete Execution path: Represents the sequence of states and mes- sages from an initial state to a final one. We note : expath(P ). Proceedings ICWIT 2012 15 3.1 Structural approach based protocol schema Let P and P ′ respectively, old and new service versions, after operating changes. EP = {Pi (i = 1 . . . n)}: Is the services set equivalent to P . We note Equi(Pi , P ), the equivalence relationship between services. Two service are equivalent if they can be used interchangeably and they provide the same functionalities in every context. Every service P i ∈ EP can replace P . Equi(Pi , P ) ⇔ ∀(i = 1 . . . n)(expath(Pi ) ⊂ expath(P ))∧(expath(P ) ⊂ expath(Pi )). (∧ is the logic and operator). (1) Let SP = {Pj (j = 1 . . . m)}: The services set that can substitute P . We note Subst(Pj , P ), the substitution relationship. A service can substitute an other one if it provides, at least, all the conversations that P supports [5] (complete execution paths). Subst(Pi , P ) ⇔ ∀(i = 1 . . . m)(expath(P ) ⊂ expath(Pi ) (2). Based on this formalization we notice that if protocol P has evolved to a new version P ′ , equations (1) does not remain valid. So we want to identify the protocols subset that satisfy equation (2), in order to provide services that can replace the evolved protocol. From equation (2):Subst(Pi , P ′ ) ⇔ ∀(i = 1 . . . m) (expath(P ′ ) ⊂ expath(Pi ). (3) . We conclude: Lemma 1:: If the changes related to protocol evolution are reductionist, all protocols (Pi ) that can substitute P , can substitute the new reduced version P ′ . Reducing Protocol description is an application of change operations including: – Loops removal. – Final sub-paths removal. – Operations and messages removal. – Complete paths removal and sub-protocols removal. This change operation goals are motivated by procedures cancellation, reduc- ing tasks, business processes alignment, and so one. However, when changes are additive, substitution analysis must consider the protocol difference. Protocol difference between two protocols P ′ and P describe the set of all complete exe- cution paths of P ′ that are not common with P [5]. We note P ′ /P this difference. Substitution analysis consists to examine each protocol in the class SP , with the aim to identify possible protocols that can substitute P ′ . Because equation (1) no longer holds, we must comply with equation (2). In order to replace P ′ , each protocol Pi ∈ SP must be able to replace the new requirements (the difference P ′ /P ). Subst(Pi , P ′ ) ⇒ Subst(Pi , P ′ /P ) ⇔ ∀(i = 1 . . . m) (expath(P ′ /P ) ⊂ expath(Pi ) (4). We conclude: Lemma 2: If changes are additive, protocols subset ⊂ SP which are contain- ing the difference P ′ /P can substitute the new extended version P ′ . Additive changes are operations performing: – Adding loops. – Adding sub-paths – Adding messages and operations . – Adding new complete paths and sub-protocols. Proceedings ICWIT 2012 16 3.2 Execution traces based analysis Protocol schema based analysis is rigid and does not take into account the actual execution for active instances. Really, it’s possible that a protocol Pi ∈ SP can’t substitute an evolved one in general, but by taking into account execution traces, it can do that for specific instances. As an example, let a protocol P and its active instances i1 , i2 , . . . , in , as mentioned in Fig.1. In parallel, protocol changes have added new states and messages to a particular path: part-path. After analysing active instances execution traces, we see that all instances have’t executed this unexpected path part-path. In this case, even if we can’t replace P ′ with a protocol Pi ∈ SP , basing on protocol schema analysis, we can substitute it basing on real execution traces, because changes do not impact real instances. We notice that execution traces may inform protocol managers on how to proceed with substitution analysis. We propose two substitution analysis based execution traces: Historical execution paths and state execution paths. Historical execution paths substitution analysis: Let histpath a protocol p historical execution path executed by an active in- stance i, during its execution, instance i has invoked an operations sequence : a, b, c, d, e, . . .. And, let futurpath: future paths not yet executed by this instance. If P ′ is the new version of P , after changes and SP is the protocol set that can substitute P . We are interested by filtering instances that are not concerned with changes. We consider protocol changes as the difference between P ′ and P : P ′ /P . In this situation, if protocol Pi ∈ SP can’t substitute P ′ , contrarily, it can substitute it for the instances subset that have not executed this difference. We note: Subst(Pi , P ′ )/Occurj : The substitution of P ′ by Pi for occurrence j. Subst(Pi , P ′ )/Occurj (i = 1 . . . n), j = 1 . . . m)is is possible if : (histpath(occurj ) ∈ / allpaths(P ′ /P ) .(5),where Allpaths(P ′ /P ) is the hole pos- sible paths set generated by protocol difference P ′ /P . This means that, substi- tution is possible if actual instance i had executed an old path not affected by changes. State Based Substitution Analysis: Historical execution path analysis is more general and based on the hole histor- ical execution paths. Although, protocols P ′ ∈ SP can’t replace P in the general case, substitution is possible for some states. We need to compute which states are not affected by changes. Substitution analysis must deal with this kind of traces by selecting protocol services that substitute active service by considering actual state and future execution path. As an example, consider the execution path from Fig. 1: If a subset of actual instances are in the state: Order made, so their execution trace are : begin.order made. A service Pi ∈ SP can substitute P ′ if it can replace it from the actual state and future execution paths. We don’t consider past execution paths be- cause changes occurs after the state (Order made). We formalize this analysis as follows: Proceedings ICWIT 2012 17 Let futurpaths the future execution path set of an active instance (all future paths), and s the actual instance i state. Subst(Pi , P ′ )/state(s) : (i = 1 . . . n) if : (f uturpaths(state(s)) ⊂ allpaths(P ′ /P )) ∧ (trace(P, i) ∈ histpath(P i)) .(6) 3.3 Algorithms We present here Substitution-schema-based algorithm to calculate schema protocol based substitution analysis presented in section 3.1. Algorithm 1: Substitution-schema-based Input: P = (S, s0 , F, M, R), P ′ = (S ′ , s′0 , F ′ , M ′ , R′ ), Pi = (Si , s0i , Fi , Mi , Ri ). Output: Decision on Substitution. Begin 1. Substitution := T rue 2. P ath = ϕ, Completpath = ϕ, Completpath′ = ϕ 3. Completpath := RecursiveP aths(S, s0 , F, M, R) 4. Completpath′ := RecursiveP aths(S ′ , s′0 , F ′ , M ′ , R′ ) 5. F or i = 1 to n // n is protocol number 6. W hile (path ∈ Completpath) Do 7. If (path ∈/ Completpath′ ) Do 8. Substitution := F alse 9. break 10. EndIf 11.EndW hile 12.EndF or 13.Return (Substitution) 14.End Substitutions-schema-based. RecursivePaths Algorithm, computes recursively all possible paths in a protocol definition, from an initial state to a final one. (is not exposed by lack of space). 4 System Architecture and Software tool presentation We have implemented the software performing substitution analysis in Java- Eclipse environment. Service protocols are implemented as automata and saved in XML files. The software performs some operational functions useful for proto- col manager like protocol description and correctness specification. Furthermore, it allows final users performing different changes operations. The system kernel provides checking static equivalence and substitution. Fig. 3. Based on schema definitions or on execution traces, the system strength is dynamic analysis. This analysis allows user to select a particular protocol, operate changes and then proceed to change impact analysis on protocol substitution. The system filters the protocol database, analysis logs directory and searches for the remaining service protocols which can substitute the evolved version Fig. 4. We visualize, below some screen-shots of the the software tool. Proceedings ICWIT 2012 18 Fig. 2. System Architecture for managing dynamic substitution Fig. 3. Protocol specification, evolution, and static equivalence and substitution Proceedings ICWIT 2012 19 Fig. 4. Substitution analysis provide services substitution class for an evolved protocol 5 Related Work Protocol management and analysis had benefited for a lot off contributions, from protocol schema matching to static evolution. But, dynamic protocol analysis did not receive all the interest it deserves. In [4],[5] authors presents a general frame- work for representing, analysing and managing Web service protocols, however this analysis is restricted to static context. In [6], protocol description is en- riched with temporal constraints and the same static analysis was performed. In [12], authors had proposed some change operators and patterns specification for changes, but change impact analysis was not presented. In [13], dynamic replaceabilty analysis had been presented in therms of compatibility only. Au- thors studies the compatibility between old and new protocol version only. No comparison with other services was made. Our work responds in a consistent manner to the previous deficiencies. 6 Conclusion and future Work In this article we have formalized substitution problem inherent to dynamic pro- tocol evolution. We have proposed an approach and a software tool for providing service protocols that can, yet replace an evolved one. As future work, we plan to address protocol substitution analysis for richer pro- tocols descriptions, such as timed and transactional constraints automata. In addition, we aim to specify protocol changes more formally by identifying evo- lution patterns and by their classification with respect to induced impact on protocol substitution and compatibility. Proceedings ICWIT 2012 20 References 1. R. Chinnici and al. Web Services description Language (WSDL) version 2.0 June 2007. http://www.w3.org/TR/wsdl20/ 2. T. Bellwood and al. UDDI Version 3.0.2 UDDI Spec Technical Committee Draft, 2004. http: uddi.org/pubs/uddi-v3.htm/ 3. M. Gudgin and al. SOAP version 1.2, July 2001. http://www.w3.org/TR/2001/WD- soap12-20010709/ 4. B. Benatallah and al : Web Service Conversation Modeling A cornerstone for E- Business automation, IEEE Internet computing 8 (1) (2004) 46-545 WSC 5. B. Benatallah and al : Representing, Analysing and Managing Web Service Proto- cols. Data Knowledge Ingineering. 58 (3): 327-357, 2006. 6. J. Ponge and al: Fine-Grained Compatibility and Replaceability Analysis of Timed Web Service Protocols. ER 2007: 599-614 7. A. Khebizi: External Behavior Modeling Enrichment of Web Services by Transactional Constraints, ICSOC PhD Symposium, December 2008. http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol- 421/paper12.pdf 8. Technical Architecture Specification v1.0.4 February 2001 http://ebxml.org/specs/ebTA.pdf. 9. Rosetanet; http://www.rosettanet.org/. 10. xCBL; http://www.xcbl.org/. 11. Gustavo Alonso, Fabio Casati, Hurumi Kuno,Vijay Machiraju : Web services con- cepts Architectures and applications, Edition Springer Verlag Berlin 2004. 12. Barbara Weber and al : Change Patterns and Change Support Features - Enhanc- ing Flexibility in Process-Aware Information Systems , 2008 13. Ryu, S. H. and al, 2008. Supporting the dynamic evolution of Web service protocols in service-oriented architectures. ACM Trans. Web 2, 2, Article 13, 46 pages. DOI = 10.1145/1346237.1346241 http://doi.acm.org/10.1145/1346237.1346241. Proceedings ICWIT 2012 21