A pattern-based approach to protocol mediation for web services composition

ContextWith the increasing popularity of Service Oriented Architecture (SOA), service composition is gaining momentum as the potential silver bullet for application integration. However, services are not always perfectly compatible and therefore cannot be directly composed. Service mediation, roughly classified into signature and protocol ones, thus becomes one key working area in SOA.ObjectiveAs a challenging problem, protocol mediation is still open and existing approaches only provide partial solutions. Further investigation on a systematic approach is needed.MethodsIn this paper, an approach based on mediator patterns is proposed to generate executable mediators and glue partially compatible services together. The mediation process and its main steps are introduced. By utilizing message mapping, a heuristic technique for identifying protocol mismatches and selecting appropriate mediator patterns is presented. The corresponding BPEL templates of these patterns are also developed.ResultsA prototype system, namely Service Mediation Toolkit (SMT), has been implemented to validate the feasibility and effectiveness of the proposed approach.ConclusionThe approach along with the prototype system facilitate the existing practice of protocol mediation for Web services composition.     

Integrating formal verification and conformance testing for reactive systems

In this paper, we describe a methodology integrating verification and conformance testing. A specification of a system - an extended input-output automaton, which may be infinite-state - and a set of safety properties ("nothing bad ever happens") and possibility properties ("something good may happen") are assumed. The properties are first tentatively verified on the specification using automatic techniques based on approximated state-space exploration, which are sound, but, as a price to pay for automation, are not complete for the given class of properties. Because of this incompleteness and of state-space explosion, the verification may not succeed in proving or disproving the properties. However, even if verification did not succeed, the testing phase can proceed and provide useful information about the implementation. Test cases are automatically and symbolically generated from the specification and the properties and are executed on a black-box implementation of the system. The test execution may detect violations of conformance between implementation and specification; in addition, it may detect violation/satisfaction of the properties by the implementation and by the specification. In this sense, testing completes verification. The approach is illustrated on simple examples and on a bounded retransmission protocol.     

A formal approach to MpSoC performance verification

Multiprocessor system on chip designs use complex on-chip networks to integrate different programmable processor cores, specialized memories, and other components on a single chip. MpSoC have been become the architecture of choice in many industries. Their heterogeneity inevitably increases with intellectual-property integration and component specialization. System integration is becoming a major challenge in their design. Simulation is state of the art in MpSoC performance verification, but it has conceptual disadvantages that become disabling as complexity increases. Formal approaches offer a systematic alternative. The article presents a technology that uses event model interfaces and a novel event flow mechanism that extends formal analysis approaches from real-time system design into the multiprocessor system on chip domain.     

A formal approach to fuzzy modeling

A formalism for coding fuzzy models of dynamical systems is presented. It is shown that the formalism is rich enough to capture the performance of arbitrary conventional discrete time dynamical systems whose transition maps are polynomials with rational coefficients. The proof of this fact provides a constructive algorithm for generating fuzzy models to arbitrarily closely approximate an arbitrary map on a compact set. Our modeling formalism highlights the similarities between fuzzy systems and hybrid control systems. We hope to be able to exploit these similarities by extending results from the area of hybrid systems to the fuzzy domain and vice versa     

Automated formal verification of visual modeling languages by model checking

Graph transformation has recently become more and more popular as a general, rule-based visual specification paradigm to formally capture (a) requirements or behavior of user models (on the model-level), and (b) the operational semantics of modeling languages (on the meta-level) as demonstrated by benchmark applications around the Unified Modeling Language (UML). The current paper focuses on the model checking-based automated formal verification of graph transformation systems used either on the model-level or meta-level. We present a general translation that inputs (i) a metamodel of an arbitrary visual modeling language, (ii) a set of graph transformation rules that defines a formal operational semantics for the language, and (iii) an arbitrary well-formed model instance of the language and generates a transitions system (TS) that serve as the underlying mathematical specification formalism of various model checker tools. The main theoretical benefit of our approach is an optimization technique that projects only the dynamic parts of the graph transformation system into the target transition system, which results in a drastical reduction in the state space. The main practical benefit is the use of existing back-end model checker tools, which directly provides formal verification facilities (without additional efforts required to implement an analysis tool) for many practical applications captured in a very high-level visual notation. The practical feasibility of the approach is demonstrated by modeling and analyzing the well-known verification benchmark of dining philosophers both on the model and meta-level.     

Reliability-aware automatic composition approach for web services

In this paper,we study the reliability-aware synthesis problem for composing available services automatically and guaranteeing that the composed result satisfies the specification,such as temporal constraints of functionality and reliability,centered on a synthesis model for mediator of web services composition (CSM).This approach focuses on handling attributes and state relations,and permitting users and services to operate over them,i.e.,read /write their data values and compare them according to a dense state order.We show that the reliability-aware synthesis problem for the specification is EXPTIME-complete and we give an exponential-time algorithm (CSM-NSA) which for a given formula ψ and a synthesis model,synthesizes available services in the library satisfying ψ over the synthesis model (if they exist) or responds with not satisfiable (otherwise).The specification ψ is a fragment of PCTL (probabilistic computation tree logic),obtained from ordinary CTL (computation tree logic) by replacing the EX,AX,EU and AU operation with their quantitative counterparts X >p,X =1,U >p,and U =1,respectively.As opposed to NSA,we provide a more effective algorithm to replace the NSA algorithm called CSM-HSA (heuristic synthesis algorithm).Though HSA is an incomplete algorithm,the answer is correct.The experiments show that the HSA algorithm solves the problem of reliability-aware service synthesis effectively and efficiently.     

Ready for testing: ensuring conformance to industrial standards through formal verification

The design of distributed, safety-critical real-time systems is challenging due to their high complexity, the potentially large number of components, and complicated requirements and environment assumptions that stem from international standards. We present a case study that shows that despite those challenges, the automated formal verification of such systems is not only possible, but practicable even in the context of small to medium-sized enterprises. We considered a wireless fire alarm system, regulated by the EN 54 standard. We performed formal requirements engineering, modeling and verification and uncovered severe design flaws that would have prevented its certification. For an improved design, we provided dependable verification results which in particular ensure that certification tests for a relevant regulation standard will be passed. In general we observe that if system tests are specified by generalized test procedures, then verifying that a system will pass any test following those test procedures is a cost-efficient approach to improve the product quality based on formal methods. Based on our experience, we propose an approach useful to integrate the application of formal methods to product development in SME.     

A formal approach to modeling office information systems

This paper formally specifies a document model for office information systems, including formal definitions of document types (frame templates), a document type hierarchy, folders, and folder organizations. Folder Organizations are defined using predicates and directed graphs. AReconstruction Problem for folder organizations is then formulated; viz., under what circumstances it is possible to reconstruct a folder organization from its folder level predicates. The Reconstruction Problem is solved in terms of such graph-theoretic concepts as Associated Digraphs, transitive closure, and redundant/nonredundant filing paths. A Transitive Closure Inversion algorithm is then presented which efficiently recovers a Folder Organization digraph from its Associated Digraph.This work was supported in part by the National Science Foundation under Grant No. IRI-9224602, by the New Jersey Institute of Technology undre Grant No. 421280 and by a grant from AT&T Foundation.     

基于WS-BPEL的服务组合流程建模工具的设计与实现

详细介绍了基于BPEL语言的可视化Web服务组合流程建模工具的体系结构;引入节点和弧的概念实现可视化流程编辑器;采用图形化方法和流程图到WS-BPEL元素的映射技术,实现了Web服务组合流程模型的建立、编辑和配置等功能,简化了抽象流程到可执行流程的转化;提出了基于Web服务QOS约束的服务查询、QOS本体表示和QOS筛选方案,使得符合用户需求的Web服务能够被动态灵活地绑定到业务流程中.     

A monolithic approach to automated composition of semantic web services with the Event Calculus

In this paper, a web service composition and execution framework is presented for semantically -annotated web services. A monolithic approach to automated web service composition and execution problem is chosen, which provides some benefits by separating composition and execution phases. An AI planning method using a logical formalism, namely Abductive Event Calculus, is chosen for the composition phase. This formalism allows one to generate a narrative of actions and temporal orderings using abductive planning techniques given a goal. The functional properties of services, namely input/output/precondition/effects (IOPE) are taken into consideration in the composition phase and non-functional properties, namely Quality of Service (QoS) parameters are used in selecting the most appropriate solution to be executed. The repository of OWL-S semantic web services are translated to the Event Calculus axioms and the resulting plans found by the Abductive Event Calculus Planner are converted to graphs. These graphs can be sorted according to a score calculated using the defined quality of service parameters of the atomic services in the composition to determine the optimal solution. The selected graph is converted to an OWL-S file which is executed consequently.     

Behavioral modeling and formal verification of a resource discovery approach in Grid computing

Grid computing is the federation of resources from multiple locations to facilitate resource sharing and problem solving over the Internet. The challenge of finding services or resources in Grid environments has recently been the subject of many papers and researches. These researches and papers evaluate their approaches only by simulation and experiments. Therefore, it is possible that some part of the state space of the problem is not analyzed and checked well. To overcome this defect, model checking as an automatic technique for the verification of the systems is a suitable solution. In this paper, an adopted type of resource discovery approach to address multi-attribute and range queries has been presented. Unlike the papers in this scope, this paper decouple resource discovery behavior model to data gathering, discovery and control behavior. Also it facilitates the mapping process between three behaviors by means of the formal verification approach based on Binary Decision Diagram (BDD). The formal approach extracts the expected properties of resource discovery approach from control behavior in the form of CTL and LTL temporal logic formulas, and verifies the properties in data gathering and discovery behaviors comprehensively. Moreover, analyzing and evaluating the logical problems such as soundness, completeness, and consistency of the considered resource discovery approach is provided. To implement the behavior models of resource discovery approach the ArgoUML tool and the NuSMV model checker are employed. The results show that the adopted resource discovery approach can discovers multi-attribute and range queries very fast and detects logical problems such as soundness, completeness, and consistency.     

A structural-semantic web service selection approach to improve retrievability of web services

Service-Oriented Computing promotes building applications by consuming and reusing Web Services. However, the selection of adequate Web Services given a client application is still a major challenge. The effort of assessing and adapting candidate services could be overwhelming due to the “impedance” of Web Service interfaces expected by clients versus the actual interfaces of retrieved Web Services. In this work, we present a novel structural-semantic approach to help developers in the retrieval and selection of services from a service registry. The approach is based on a comprehensive structural scheme for service Interface Compatibility analysis, and WordNet as the semantic support to assess identifiers of operations and parameters. We also empirically analyze, compare and contrast the performance of three service selection methods: a pure structural approach, a pure semantic approach, and the structural-semantic (hybrid) approach proposed in this work. The experimental analysis was performed with two data-sets of real-world Web Services and a service discovery support already published in the literature. Results show that our hybrid service selection approach improved effectiveness in terms of retrievability of Web Services compared to the other approaches.     

基于FCA的Web服务动态组合及管理方法研究

为实现Web服务的动态组合及管理,分析了该领域的研究现状,针对存在的问题,运用形式概念分析相关理论来研究Web服务的组合管理,对候选Web服务的输入输出数据关系进行形式化建模,有效地利用消息依赖关系实现服务的组合请求.提出了利用二分图求得所有形式概念的算法,建立服务格及计算服务组合关系的算法,设计并实现了原型系统以满足Web服务的动态组合及管理.     

基于与或图的Web服务自动组合

为快速、灵活、高效地组合Web服务,通过论证与或图的重要,陛质及归约算法的有效性,提出了一种基于与或图的Web服务自动组合方法.该方法针对Web服务请求的每一个输出对象实时构造与或图,再通过归约算法获取该输出对象的合成路径.与已有方法相比,该方法实现简单,搜索空间小,避免了重复搜索和循环搜索.仿真实验结果表明,该方法时间复杂度较好,能够在大规模的服务集中进行灵活、快速的服务组合.     

Non-redundant web services composition based on a two-phase algorithm

Recently, there has been growing interest in developing web services composition search systems. Current solutions have the drawback of including redundant web services in the results. In this paper, we proposed a non-redundant web services composition search system called NRC, which is based on a two-phase algorithm. In the NRC system, the Link Index is built over web services according to their connectivity. In the forward phase, the candidate compositions are efficiently found by searching the Link Index. In the backward phase, the candidate compositions decomposed into several non-redundant web services compositions by using the concept of tokens. Results of experiments involving data sets with different characteristics show the performance benefits of the NRC techniques in comparison to state-of-the-art composition approaches.     

基于MDA的Web服务动态组合的研究

针对目前Web服务动态组合方面出现的技术问题,给出了基于MDA的Web服务组合的方法,MDA具有将功能需求与具体实现技术分离的优势,因此可以有效地解决Web服务动态合成的可靠性、灵活性、复用性问题.在给出了结合MDA思想的服务合成体系框架的基础上,分析了UML类图与WSDL语言元模型、UML活动图与WS-BPEL语言元模型的对应关系以确定模型到代码的转换规则.最后以某制造企业的案例验证该技术的可行性.     

A behavioral analysis and verification approach to pattern-based design composition

Integrating software components to produce large-scale software systems is an effective way to reuse experience and reduce cost. However, unexpected interactions among components when integrated into software systems are often the cause of failures. Discovering these composition errors early in the development process could lower the cost and effort in fixing them. This paper introduces a rigorous analysis approach to software design composition based on automated verification techniques. We show how to represent, instantiate and integrate design components, and how to find design composition errors using model checking techniques. We illustrate our approach with a Web-based hypermedia case study.