Degree Type


Date of Award


Degree Name

Doctor of Philosophy


Computer Science

First Advisor

Robyn R. Lutz


As service oriented architectures have become more widespread in industry, many complex web services are assembled using independently developed modular services from different vendors. Although the functionalities of the composite web services are ensured during the composition process, the non-functional requirements (NFRs) are often ignored in this process. Since quality of services plays a more and more important role in modern service-based systems, there is a growing need for effective approaches to verifying that a composite web service not only offers the required functionality but also satisfies the desired NFRs.

Current approaches to verifying NFRs of composite services (as opposed to individual services) remain largely ad-hoc and informal in nature. This is especially problematic for high-assurance composite web services. High-assurance composite web services are those composite web services with special concern on critical NFRs such as security, safety and reliability. Examples of such applications include traffic control, medical decision support and the coordinated response systems for civil emergencies. The latter serves to motivate and illustrate the work described here.

In this dissertation we develop techniques for ensuring that a composite service meets the user-specified NFRs expressible as hard constraints, e.g., "the messages of

particular operations must be authenticated." We introduce an automata-based framework for verifying that a composite service satisfies the desired NFRs based on the known guarantees regarding the non-functional properties of the component services. This automata-based model is able to represent NFRs that are hard, quantitative constraints on the composite web services. This model addresses two issues previously not handled in the modeling and verification of NFRs for composite web services: (1) the scope of the NFRs and (2) consistency checking of multiple NFRs.

A scope of a NFR on a web service composition is the effective range of the NFR on the sub-workflows and modular services of the web service composition. It allows more precise description of a NFR constraint and more efficient verification. When multiple NFRs exist and overlap in their scopes, consistency checking is necessary to avoid wasted verification efforts on conflicting constraints. The approach presented here captures scope information in the model and uses it to check the consistency of multiple NFRs prior to the static verification of web service compositions. We illustrate how our approach can be used to verify security requirements for an Emergency Management System.

We then focus on families of highly-customizable, composed web services where repeated verification of similar sets of NFRs can waste computation resources. We introduce a new approach to extend software product line engineering techniques to the web service composition domain. The resulting technique uses a partitioning similar to that between domain engineering and application engineering in the product-line context. It specifies the options that the user can select and constructs the resulting web service

compositions. By first creating a web-service composition search space that satisfies the common requirements and then querying the search space as the user makes customization decisions, the technique provides a more efficient way to verify customizable web services. A decision model, illustrated with examples from the emergency-response application, is created to interact with the customers and ensure the consistency of their specifications. The capability to reuse the composition search space is shown to improve the quality of the composite services and reduce the cost of re-verifying the same compositions. By distinguishing the commonalities and the variabilities of the web services, we divide the web composition into two stages: the preparation stage (to construct all commonalities) and the customization stage (to choose optional and alternative features). We thus draw most of the computation overhead into the first stage during the design in order to enable improved runtime efficiency during the second stage.

A simulation platform was constructed to conduct experiments on the two verification approaches and three strategies introduced in this dissertation. The results of these experiments were analyzed to show the advantage of our automaton-based model in its verification efficiency with scoping information. We have shown how to choose the most efficient verification strategy from the three strategies of verifying multiple NFRs introduced in this dissertation under different circumstances. The results indicate that the software product line approach has significant efficiency improvement over traditional on-demand verification for highly customizable web service compositions.


Copyright Owner

Hongyu Sun



Date Available


File Format


File Size

191 pages