Types for the Ambient Calculus

The ambient calculus is a concurrent calculus where the unifying notion of ambient is used to model many different constructs for distributed and mobile computation. We study a type system that describes several properties of ambient behavior. The type system allows ambients to be partitioned in disjoint sets (groups), according to the intended design of a system, in order to specify both the communication and the mobility behavior of ambients.     

On the Expressiveness of Movement in Pure Mobile Ambients

Pure Mobile Ambients (i.e., Mobile Ambients without communication) provides three mobility primitives: in and out for ambient movement, and open to dissolve ambient boundaries. In this paper we consider the expressiveness of the primitives in and out for ambient movement; more precisely, we concentrate on the interplay between ambient movement and the ability to create new names (exploiting the restriction operator). To this aim, we consider a version of Pure Mobile Ambients (with explicit recursive definitions instead of replication) and we concentrate on the three fragments of the calculus that can be obtained removing either one or both between movement and the ability to create new names. The unique mobility primitive that we retain in all of the considered calculi is open. Te three fragments are denoted as follows: MA^−mv without ambient movement, MA_−v without restriction, and MA^−mv_−v without both movement and restriction. We prove that both the fragments MA^−mv and MA_−v are Turing-complete, while this is not the case for MA^−mv_−v. Indeed, we prove that in this latter calculus the existence of an infinite computation turns to be a decidable property.     

The Calculus of Context-aware Ambients

We present the Calculus of Context-aware Ambients (CCA in short) for the modelling and verification of mobile systems that are context-aware. This process calculus is built upon the calculus of mobile ambients and introduces new constructs to enable ambients and processes to be aware of the environment in which they are being executed. This results in a powerful calculus where both mobility and context-awareness are first-class citizens. We present the syntax and a formal semantics of the calculus. We propose a new theory of equivalence of processes which allows the identification of systems that have the same context-aware behaviours. We prove that CCA encodes the π-calculus which is known to be a universal model of computation. Finally, we illustrate the pragmatics of the calculus through many examples and a real-world case study of a context-aware hospital bed.     

Stochastic Ambient Calculus

Mobile Ambients (MA) have acquired a fundamental role in modelling mobility in systems with mobile code and mobile devices, and in computation over administrative domains. We present the stochastic version of Mobile Ambients, called Stochastic Mobile Ambients (SMA), where we extend MA with time and probabilities. Inspired by previous models, PEPA and Sπ, we enhance the prefix of the capabilities with a rate and the ambient with a linear function that operates on the rates of processes executing inside it. The linear functions associated with ambients represent the delays that govern particular administrative domains. We derive performance measures from the labelled transition semantics as in standard models. We also define a strong Markov bisimulation in the style of reduction semantics known as barbed bisimulation. We argue that performance measures are of vital importance in designing any kind of distributed system, and that SMA can be useful in the design of the complicated mobile systems.     

Guardians for Ambient-Based Monitoring

In the Mobile Ambients of Cardelli and Gordon an ambient is a unit for mobility, which may contain processes (data) and sub-ambients. Since the seminal work of Cardelli and Gordon, several ambient-based calculi have been proposed (Seal, Box-π, Safe Ambients, Secure Safe Ambients, Boxed Ambients), mainly for supporting security. At the operational level these (box- and) ambient-based calculi differ only in the capabilities of processes. We propose a way of extending ambient-based calculi, which embodies two principles: an ambient is a unit for monitoring and coordination, the name of an ambient determines its (monitoring and coordination) policy. More specifically, to each ambient we attach a guardian, which monitors the activity of sub-components (i.e. processes and sub-ambients) and the interaction with the external environment. In our proposal, guardians and processes play a dual role: guardians are centralized entities monitoring and inhibiting actions, while processes are decentralized entities performing actions. We exemplify the use of guardians for enforcing security properties.     

Leader Election in Rings of Ambient Processes

Palamidessi has shown that the π-calculus with mixed choice is powerful enough to solve the leader election problem on a symmetric ring of processes. We show that this is also possible in the calculus of Mobile Ambients (MA), without using communication or restriction. Following Palamidessi's methods, we deduce that there is no encoding satisfying certain conditions from MA into CCS. We also show that the calculus of Boxed Ambients is more expressive than its communication-free fragment.     

On the expressive power of movement and restriction in pure mobile ambients

Pure mobile ambients is a process calculus suitable to focus on issues related to mobility, abstracting away from aspects concerning process communication. However, it incorporates name restriction (i.e. the (νn) binder) and ambient movement (i.e. the in and out capabilities) that can be seen as characteristics adapted, or directly borrowed, from the tradition of communication-based process calculi. For this reason, we retain that it is worth to investigate whether or not these features can be removed from pure mobile ambients without losing expressive power.To this aim, we consider two variants of pure mobile ambients which differ in the way infinite processes can be defined; the former exploits process replication, while the latter is more general and permits recursive process definition. We analyse whether or not the elimination of ambient movement and/or name restriction reduces the expressive power of these two calculi, using the decidability of process termination as a yardstick. We prove that name restriction can be removed from both calculi without reducing the expressive power. On the other hand, the elimination of both ambient movement and name restriction strictly reduces the expressive power of both calculi. As far as the elimination of only ambient movement is concerned, we prove an interesting discrimination result: process termination is undecidable under recursive process definition, while it turns out to be decidable under process replication.     

Hybrid logical analyses of the ambient calculus

In this paper, hybrid logic is used to formulate three control flow analyses for Mobile Ambients, a process calculus designed for modelling mobility. We show that hybrid logic is very well-suited to express the semantic structure of the ambient calculus and how features of hybrid logic can be exploited to reduce the “administrative overhead” of the analysis specification and thus simplify it. Finally, we use HyLoTab, a fully automated theorem prover for hybrid logic, both as a convenient platform for a prototype implementation as well as to formally prove the correctness of the analysis.     

Fair ambients

Based on an analysis of the capability operators of the Calculus of Mobile Ambients, three fairness principles are proposed to safeguard the interactions of the ambients. The Calculus of Fair Ambient is designed to meet these fairness principles. A labeled transition semantics for the calculus is defined to support structural investigation. The bisimulation theory of the fair ambients is studied and two coincidence results are established. An expressiveness result of the calculus is formally established by proving that it contains the pi calculus as a sub-calculus.     

On the computational strength of pure ambient calculi

Cardelli and Gordon's calculus of Mobile Ambients has attracted widespread interest as a model of mobile computation. The standard calculus is quite rich, with a variety of operators, together with capabilities for entering, leaving and dissolving ambients. The question arises of what is a minimal Turing-complete set of constructs. Previous work has established that Turing completeness can be achieved without using communication or restriction. We show that it can be achieved merely using movement capabilities (and not dissolution). We also show that certain smaller sets of constructs are either terminating or have decidable termination.     

Bigraphical Semantics of Higher-Order Mobile Embedded Resources with Local Names

Bigraphs have been introduced with the aim to provide a topographical meta-model for mobile, distributed agents that can manipulate their own linkages and nested locations, generalising both characteristics of the π-calculus and the Mobile Ambients calculus. We give the first bigraphical presentation of a non-linear, higher-order process calculus with nested locations, non-linear active process mobility, and local names, the calculus of Higher-Order Mobile Embedded Resources (Homer). The presentation is based on Milner's recent presentation of the λ-calculus in local bigraphs. The combination of non-linear active process mobility and local names requires a new definition of parametric reaction rules and a representation of the location of names. We suggest localised bigraphs as a generalisation of local bigraphs in which links can be further localised.     

A typed encoding of boxed into safe ambients

We present: (i) an encoding of Boxed Ambients into a variant of Safe Ambients; and (ii) a new type system for multi-level security of Safe Ambients in the style of Cardelli et al. (Information and Computation 177(2), 160–194 (2002)) and Dezani-Ciancaglini and Salvo (Security types for mobile safe ambients. In: Proceedings of ASIAN '00, LNCS 1961, pp. 215–236. Springer Verlag (2000)). Then, we show that the types, when applied to the encoded BA proceses, permits to accurately verify Mandatory Access Control policies of the source processes.     

On the Expressiveness of Pure Mobile Ambients

We consider the Pure Ambient Calculus, which is Cardelli and Gordon's Ambient Calculus (or more precisely its safe version by Levi and Sangiorgi) restricted to its mobility primitives, and we focus on its expressive power. Since it has no form of communication or substitution, we show how these notions can be simulated by mobility and modifications in the hierarchical structure of ambients. As an example, we give an encoding of the synchronous π-calculus into pure ambients and we state an operational correspondence result. In order to simplify the proof and give an intuitive understanding of the encoding, we design an intermediate language: the π-Calculus with Explicit Substitutions and Channels, which is a syntactic extension of the π-calculus with a specific operational semantics.     

Interaction in Time and Space

Distributed π-calculus and ambient calculus are extended with timers which may trigger timeout recovery processes. Timers provide a useful notion of relative time with respect to the interaction in a distributed system. The rather flat notion of space in timed distributed π-calculus is improved by considering a hierarchical representation of space in timed mobile ambients. Some basic results are proven, making sound both formal approaches. An easily understood example is used for both extensions, showing how it is possible to describe a non-monotonic behaviour and use a decentralized control to coordinate the interacting components in time and space.     

Name-Passing in an Ambient-Like Calculus and Its Proof Using Spatial Logic

This paper studies a restricted version of the ambient calculus. We only allow single-threaded ambients migrating in a network of immobile ambients, exchanging payloads, and delivering them. With this restriction, we arrive at a calculus free from grave interferences. In previous works, this is only possible by sophisticated type systems.We focus on the expressiveness of the restricted calculus. We show that we can still repeat Zimmer's encoding of name-passing in our calculus. Moreover, we prove a stronger operational correspon- dence result using a novel spatial logic, which specifies spatial properties of processes invariant to process reductions.     

移动界程模型检测

首次将嵌套谓词等式系应用到带递归的谓词界程逻辑模型检测中,提出了第1个时间复杂性与逻辑公式的交错嵌套深度呈指数关系的局部模型检测算法,这也是目前已知的第2个带递归的谓词界程逻辑模型检测算法.所做的工作有：①讨论了谓词界程逻辑公式与嵌套谓词等式系间语义的等价性,给出了谓词界程逻辑公式转换成嵌套谓词等式系的方法;②讨论了谓词界程逻辑模型检测问题,给出了具体算法,并分析了算法的复杂性.     

带口令的安全盒子环境演算

带口令的安全盒子环境演算是对原有的移动环境演算的改进，避免了移动环境演算中open操作所带来的干扰，加强了环境对其自身边界的控制能力，实现了对环境的回收。文中给出了SBAP的语法和语义定义，用SBAP对Pi-演算中的匹配算子进行了改写，并对电子邮件系统进行了描述和仿真。     

类型化移动资源

在移动资源演算(MR)中发现了一种干扰现象,称为直接访问干扰,该现象比移动灰箱演算(MA)中的墙干扰现象更具破坏力,因为在MR中恶意的环境或上下文可以不受限制地访问进程内部的敏感资源.因而该干扰问题当被视为一种程序运行错误.为了控制直接干扰现象,提出了一种MR的变体:安全移动资源演算(SR).它使用了一种类型系统来避免所有的直接访问干扰的发生.基于该研究,MA中的强干扰现象实际上是直接访问干扰的一种特殊形式,自然地,在SR中也得到了相应的控制.最后给出一些用例,说明如何使用新设计的演算系统,以及它的健壮性.     

Abstract interpretation based verification of temporal properties for BioAmbients

This paper concerns the application of formal methods to biological systems, modeled specifically in BioAmbients, a variant of the Mobile Ambients calculus. Following the semantic-based approach of abstract interpretation, we define a new static analysis that computes an abstract transition system. Our analysis has two main advantages with respect to the analyses appearing in the literature: (i) it is able to address temporal properties which are more general than invariant properties; (ii) it supports, by means of a particular labeling discipline, the validation of systems where several copies of an ambient may appear.We also design new weaker and more efficient analyses by means of simple widening operators.     

Using ambients to control resources

Current software and hardware systems, being parallel and reconfigurable, raise new safety and reliability problems, and the resolution of these problems requires new methods. Numerous proposals aim at reducing the threat of bugs and preventing several kinds of attacks. In this paper, we develop an extension of the calculus of mobile ambients, named controlled ambients, that is suited for expressing such issues, specifically denial of service attacks. We present a type system for controlled ambients, which makes static resource control possible in our setting, and enhance it with a rich notion of resources .