logo SBA


Digital archive of theses discussed at the University of Pisa


Thesis etd-05232016-100710

Thesis type
Tesi di dottorato di ricerca
Thesis title
Specification and Verification of Contract-Based Applications
Academic discipline
Course of study
tutor Prof. Degano, Pierpaolo
tutor Prof. Ferrari, Gian Luigi
  • automata
  • choreography
  • formal methods
  • model-checking
  • orchestration
  • service composition
  • verification
Graduation session start date
Nowadays emerging paradigms are being adopted by several companies, where applications
are built by assembling loosely-coupled distributed components, called services.
Services may belong to possibly mutual distrusted organizations and may have conflicting
goals. New methodologies for designing and verifying these applications are
necessary for coping with new scenarios in which a service does not adhere with its
prescribed behaviour, namely its contract.
The thesis tackles this problem by proposing techniques for specifying and verifying
distributed applications. The first contribution is an automata-based model checking technique
for ensuring both service compliance and security requirements in a composition of
services. We further develop the automata-based approach by proposing a novel formal
model of contracts based on tailored finite state automata, called contract automata.
The proposed model features several notions of contract agreement described from a
language-theoretic perspective, for characterising the modalities in which the duties and
requirements of services are fulfilled. Contract automata are equipped with different
composition operators, to uniformly model both single and composite services, and techniques
for synthesising an orchestrator to enforce the properties of agreement. Algorithms
for verifying these properties are introduced, based on control theory and linear programming
techniques. The formalism assumes the existence of possible malicious components
trying to break the overall agreement, and techniques for detecting and banning eventually
liable services are described. We study the conditions for dismissing the central
orchestrator in order to generate a distributed choreography of services, analysing both
closed and open choreographed systems, with synchronous or asynchronous interactions.
We relate contract automata with different intutionistic logics for contracts, introduced
for solving mutual circular dependencies between the requirements and the obligations of
the parties, with either linear or non-linear availability of resources. Finally, a prototypical tool implementing the theory developed in the thesis is presented.