International audience

Session types are widely used as abstractions of asynchronous message passing systems. Refinement for such abstractions is crucial as it allows improvements of a given component without compromising its compatibility with the rest of the system. In the context of session types, the most general notion of refinement is asynchronous session subtyping, which allows message emissions to be anticipated w.r.t. a bounded amount of message consumptions. In this paper we investigate the possibility to anticipate emissions w.r.t. an unbounded amount of consumptions: to this aim we propose to consider fair compliance over asynchronous session types and fair refinement as the relation that preserves it. This allows us to propose a novel variant of session subtyping that leverages the notion of controllability from service contract theory and that is a sound characterisation of fair refinement. In addition, we show that both fair refinement and our novel subtyping are undecidable. We also present a sound algorithm which deals with examples that feature potentially unbounded buffering. Finally, we present an implementation of our algorithm and an empirical evaluation of it on synthetic benchmarks.

Detecting programming errors in software is increasingly important, and building tools that help developers with this task is a crucial area of investigation on which the industry depends. Leveraging on the observation that in Object-Oriented Programming (OOP) it is natural to define stateful objects where the safe use of methods depends on their internal state, we present Java Typestate Checker (JATYC), a tool that verifies Java source code with respect to typestates. A typestate defines the object’s states, the methods that can be called in each state, and the states resulting from the calls. The tool statically verifies that when a Java program runs: sequences of method calls obey to object’s protocols; objects’ protocols are completed; null-pointer exceptions are not raised; subclasses’ instances respect the protocol of their superclasses. To the best of our knowledge, this is the first OOP tool that simultaneously tackles all these aspects.

Abstract Session types are widely used as abstractions of asynchronous message passing systems. Refinement for such abstractions is crucial as it allows improvements of a given component without compromising its compatibility with the rest of the system. In the context of session types, the most general notion of refinement is the asynchronous session subtyping, which allows to anticipate message emissions but only under certain conditions. In particular, asynchronous session subtyping rules out candidates subtypes that occur naturally in communication protocols where, e.g., two parties simultaneously send each other a finite but unspecified amount of messages before removing them from their respective buffers. To address this shortcoming, we study fair compliance over asynchronous session types and fair refinement as the relation that preserves it. This allows us to propose a novel variant of session subtyping that leverages the notion of controllability from service contract theory and that is a sound characterisation of fair refinement. In addition, we show that both fair refinement and our novel subtyping are undecidable. We also present a sound algorithm, and its implementation, which deals with examples that feature potentially unbounded buffering.

Abstract We study the relationship between session types and behavioural contracts, representing Communicating Finite State Machines (CFSMs), under the assumption that processes communicate asynchronously. Session types represent a syntax-based approach for the description of communication protocols, while behavioural contracts, formally expressing CFSMs, follow an operational approach. We show the existence of a fully abstract interpretation of session types into a fragment of contracts that maps session subtyping into binary compliance-preserving CFSMs/behavioural contract refinement. In this way, on the one hand, we enrich the theory of session types with an operational characterization and, on the other hand, we use recent undecidability results for asynchronous session subtyping to obtain an original undecidability result for asynchronous CFSMs/behavioural contract refinement.

Microservices are highly modular and scalable Service Oriented Architectures. They underpin automated deployment practices like Continuous Deployment and Autoscaling. In this paper we formalize these practices and show that automated deployment — proven undecidable in the general case — is algorithmically treatable for microservices. Our key assumption is that the configuration life-cycle of a microservice is split into two phases: (i) creation, which entails establishing initial connections with already available microservices, and (ii) subsequent binding/unbinding with other microservices. To illustrate the applicability of our approach, we implement an automatic optimal deployment tool and compute deployment plans for a realistic microservice architecture, modeled in the Abstract Behavioral Specification (ABS) language.

We give two different notions of deadlock for systems based on active objects and futures. One is based on blocked objects and conforms with the classical definition of deadlock by Coffman, Jr. et al. The other one is an extended notion of deadlock based on blocked processes which is more general than the classical one. We introduce a technique to prove deadlock freedom of systems of active objects. To check deadlock freedom an abstract version of the program is translated into Petri nets. Extended deadlocks, and then also classical deadlock, can be detected via checking reachability of a distinct marking. Absence of deadlocks in the Petri net constitutes deadlock freedom of the concrete system.

The investigation into the foundational aspects of linguistic mechanisms for programming long-running transactions (such as thescopeoperator of WS-BPEL) has recently renewed the interest in process algebraic operators that, due to the occurrence of a failure,interruptthe execution of one process, replacing it with another one called thefailure handler. We investigate the decidability of termination problems for two simple fragments of CCS (one with recursion and one with replication) extended with one of two such operators, theinterruptoperator of CSP and thetry-catchoperator for exception handling. More precisely, we consider the existential termination problem (existence of one terminated computation) and the universal termination problem (all computations terminate). We prove that, as far as the decidability of the considered problems is concerned, under replication there is no difference between interrupt and try-catch (universal termination is decidable while existential termination is not), while under recursion this is not the case (existential termination is undecidable while universal termination is decidable only for interrupt). As a consequence of our undecidability results, we show the existence of an expressiveness gap between a fragment of CCS and its extension with either the interrupt or the try-catch operator.

We investigate, in a process algebraic setting, a new notion of correctness for service compositions, which we callstrong service compliance: composed services are strong compliant if their composition is both deadlock and livelock free (this is the traditional notion of compliance), and whenever a message can be sent to invoke a service, it is guranteed to be ready to serve the invocation. We also define a new notion of refinement, calledstrong subcontract pre-order, suitable for strong compliance: given a composition of strong compliant services, we can replace any service with any other service in subcontract relation while preserving the overall strong compliance. Finally, we present a characterisation of the strong subcontract pre-order by resorting to the theory of a (should) testing pre-order.

The three classical process algebras CCS, CSP and ACP present several differences in their respective technical machinery. This is due, not only to the difference in their operators, but also to the terminology and ‘way of thinking’ of the community that has been (and still is) working with them. In this paper we will first discuss these differences and try to clarify the different usage of terminology and concepts. Then, as a result of this discussion, we define a generic process algebra where each of the basic mechanisms of the three process algebras (including minimal fixpoint based unguarded recursion) is expressed by an operator, and which can be used as an underlying common language. We show an example of the advantages of adopting such a language instead of one of the three more specialised algebras: producing a complete axiomatisation for Milner's observational congruence in the presence of (unguarded) recursion and static operators. More precisely, we provide a syntactical characterisation (allowing as many terms as possible) for the equations involved in recursion operators, which guarantees that transition systems generated by the operational semantics are finite state. Conversely, we show that every process admits a specification in terms of such a restricted form of recursion. We then present an axiomatisation that is ground complete over such a restricted signature. Notably, we also show that the two standard axioms of Milner for weakly unguarded recursion can be expressed using a single axiom only.

We define several security properties for the analysis of probabilistic noninterference as a conservative extension of a classical, nondeterministic, process-algebraic approach to information flow theory. We show that probabilistic covert channels (that are not observable in the nondeterministic setting) may be revealed through our approach and that probabilistic information can be exploited to give an estimate of the amount of confidential information flowing to unauthorized users. Finally, we present a case study showing that the expressiveness of the calculus we adopt makes it possible to model and analyze real concurrent systems.

Due to the complex nature of bisimulation equivalences that express some form of history dependence, it turned out to be problematic to decide them over nontrivial classes of recursive systems. Moreover, to the best of our knowledge, the problem of axiomatizing them over such classes of systems has never been solved. In this article, we face this problem in the case of weak ST bisimulation, an equivalence that expresses the execution of an action as the combination of the two interdependent events of action start and action termination and that supports the operation of action refinement. We first consider a basic process algebra with CSP multiway synchronization and recursion and we show that a simple technique based on static names is sufficient to decide weak ST bisimulation over processes that are finite state according to the standard interleaving semantics. Then we introduce a different technique based on dynamic names and on the new idea of compositional level-wise renaming of actions (which produces semantic models via SOS such that weak ST bisimulation can be established through standard weak bisimulation) and we show that it can be applied to decide and axiomatize weak ST bisimulation over the same class of processes. Finally, we introduce a third technique based on pointers, updated according to a pseudo-stack discipline, which preserves the possibility of deciding and axiomatizing weak ST bisimulation also when an action refinement operator is considered.