A long-standing and fundamental issue in computer security is to control the flow of information, whether to prevent confidential information from being leaked, or to prevent trusted information from being tainted. While there have been many efforts aimed at preventing improper flows completely (see for example, the survey by Sabelfeld and Myers (2003)), it has long been recognized that perfection is often impossible in practice. A basic example is a login program – whenever it rejects an incorrect password, it unavoidably reveals that the secret password differs from the one that was entered. More subtly, systems may be vulnerable to side channel attacks, because observable characteristics like running time and power consumption may depend, at least partially, on sensitive information.

This special issue of Mathematical Structures in Computer Science is composed mainly of papers submitted by participants of the Dagstuhl Seminar on Computing with Infinite Data: Topological and Logical Foundations. The workshop took place in the Schloss Dagstuhl - Leibniz Center for Informatics in the first half of October 2011.

We give a short and elementary proof of the Schröder–Simpson Theorem, which states that the space of all continuous maps from a given space X to the non-negative reals with their Scott topology is the cone-theoretic dual of the probabilistic powerdomain on X.

Divergence and non-determinism play a fundamental role in the theory of computation, and their combined effect on computational equality deserves further study. By looking at the issue from the point of view of both computation and interaction, we are led to a canonical equality for non-deterministic computation, revealing its rich algebraic structure. We study this structure in three ways. First, we construct a complete equational system for finite-state non-deterministic computation. The challenge with such a system is to find an equational alternative to fixpoint induction à la Milner. We establish a negative result in the form of the non-existence of a finite equational system for the canonical equality of non-deterministic computation to support our approach. We then investigate infinite-state non-deterministic computation in the light of definability and show that every recursively enumerable set is generated by an unobservable process. Finally, we prove that, as far as computation is concerned, the effect produced jointly by divergence and non-determinism is model independent for a large class of process models.

We use C-graphs, which are interesting in their own right, as abstract representations of the computational objects throughout the paper.

This special issue contains selected papers from the Eighth Asian Symposium on Programming Languages and Systems (APLAS 2010), held from 28 November – 1 December 2010, in Shanghai, China. The symposium was sponsored by the Asian Association for Foundation of Software (AAFS) and Shanghai Jiao Tong University.

Objects and services are pervasive concepts in modern distributed systems. Objects and services, sometimes generically referred to as components, represent the unit of interaction. They offer mechanisms for abstraction and encapsulation, through a well-defined interface that specifies the way in which a given component can be used from the outside, thus hiding the details of the internal implementation. These features are important for building flexible systems, in which components can be used just by inspecting their interface.

We show that the category of basic pairs (BP) and the category of concrete spaces (CSpa) are both small-complete and small-cocomplete in the framework of constructive Zermelo–Frankel set theory extended with the set generation axiom. We also show that CSpa is a coreflective subcategory of BP.

We give an overview of the main ideas involved in the development of homotopy type theory and the univalent foundations of Mathematics programme. This serves as a background for the research papers published in the special issue.

We develop category theory within Univalent Foundations, which is a foundational system for mathematics based on a homotopical interpretation of dependent type theory. In this system, we propose a definition of ‘category’ for which equality and equivalence of categories agree. Such categories satisfy a version of the univalence axiom, saying that the type of isomorphisms between any two objects is equivalent to the identity type between these objects; we call them ‘saturated’ or ‘univalent’ categories. Moreover, we show that any category is weakly equivalent to a univalent one in a universal way. In homotopical and higher-categorical semantics, this construction corresponds to a truncated version of the Rezk completion for Segal spaces, and also to the stack completion of a prestack.

Continuous lattices were characterised by Martín Escardó as precisely those objects that are Kan-injective with respect to a certain class of morphisms. In this paper we study Kan-injectivity in general categories enriched in posets. As an example, ω-CPO's are precisely the posets that are Kan-injective with respect to the embeddings ω ↪ ω + 1 and 0 ↪ 1.

For every class $\mathcal{H}$ of morphisms, we study the subcategory of all objects that are Kan-injective with respect to $\mathcal{H}$ and all morphisms preserving Kan extensions. For categories such as Top0 and Pos, we prove that whenever $\mathcal{H}$ is a set of morphisms, the above subcategory is monadic, and the monad it creates is a Kock–Zöberlein monad. However, this does not generalise to proper classes, and we present a class of continuous mappings in Top0 for which Kan-injectivity does not yield a monadic category.

Three integrity measures are introduced: contamination, channel suppression and program suppression. Contamination is a measure of how much untrusted information reaches trusted outputs; it is the dual of leakage, which is a measure of information-flow confidentiality. Channel suppression is a measure of how much information about inputs to a noisy channel is missing from the channel outputs. And program suppression is a measure of how much information about the correct output of a program is lost because of attacker influence and implementation errors. Program and channel suppression do not have interesting confidentiality duals. As a case study, a quantitative relationship between integrity, confidentiality and database privacy is examined.

We introduce infinitary propositional theories over a set and their models which are subsets of the set, and define a generalized geometric theory as an infinitary propositional theory of a special form. The main result is that the class of models of a generalized geometric theory is set-generated. Here, a class $\mathcal{X}$ of subsets of a set is set-generated if there exists a subset G of $\mathcal{X}$ such that for each α ∈ $\mathcal{X}$, and finitely enumerable subset τ of α there exists a subset β ∈ G such that τ ⊆ β ⊆ α. We show the main result in the constructive Zermelo–Fraenkel set theory (CZF) with an additional axiom, called the set generation axiom which is derivable in CZF, both from the relativized dependent choice scheme and from a regular extension axiom. We give some applications of the main result to algebra, topology and formal topology.

What reasoning rules can be used for the deduction of bisimulation formulas in coalgebraic specifications is problematic because those rules used in algebraic specifications possibly cannot be applied to bisimulation formulas. Although some categorical bisimulation proof methods for coalgebras have been proposed, they are not based on specification languages of coalgebras so that they cannot be used as reasoning rules. In this paper, a specification language based on paths of polynomial functors is proposed to specify polynomial coalgebras. Paths of polynomial functors give detailed observations and transitions on the state space of coalgebras so that the techniques used in transition system specifications can be applied to such a path-based language. In particular, because bisimulations can be characterized by paths, the notions of progressions, respectful functions and faithful contexts can be defined based on paths, and then bisimulation up-to proof techniques, including bisimulation up-to bisimilarities and up-to contexts for transition systems can be transformed into reasoning rules in the language. Several examples illustrate how to reason syntactically about bisimulations in the language by using the rules induced by the bisimulation proof techniques.

Delta modelling is an approach to facilitate the automated product derivation for software product lines. It is based on a set of deltas specifying modifications that are incrementally applied to a core product. The applicability of deltas depends on application conditions over features. This paper presents abstract delta modelling, which explores delta modelling from an abstract, algebraic perspective. Compared to the previous work, we take a more flexible approach to conflicts between modifications by introducing the notion of conflict-resolving deltas. Furthermore, we extend our approach to allow the nesting of delta models for increased modularity. We also present conditions on the structure of deltas to ensure unambiguous product generation.

We propose a refinement and a simplification of the behavioural semantics of session types, based on the concepts of compliance and sub-behaviour from the theory of web contracts. We introduce three relations on a suitable class of behaviours with higher-order input/output, called ‘session behaviours’. Such relations, depending on each other, represent the idea of sub-behaviour from the point of view of a client, a server or a peer, respectively. A restriction of the intersection of the first two relations characterizes the ‘usual’ sub-behaviour relation from the literature. We then device an algorithmic formal system for three subtyping relations (dubbed CSP-subtyping) for session types that takes into account the role played by a user of a channel during an interaction, so extending Gay and Hole subtyping theory. We show that our session behaviours and sub-behaviour relations provide sound and complete semantics for CSP-subtyping, and for Gay and Hole subtyping as a by-product.

Every co-c.e. closed set (Π01 class) in Cantor space is represented by a co-c.e. tree. Our aim is to clarify the interaction between the Medvedev and Muchnik degrees of co-c.e. closed subsets of Cantor space and the Turing degrees of their co-c.e. representations. Among other results, we present the following theorems: if v and w are different c.e. degrees, then the collection of the Medvedev (Muchnik) degrees of all Π01 classes represented by v and the collection represented by w are also different; the ideals generated from such collections are also different; the collections of the Medvedev and Muchnik degrees of all Π01 classes represented by incomplete co-c.e. sets are upward dense; the collection of all Π01 classes represented by K-trivial sets is Medvedev-bounded by a single Π01 class represented by an incomplete co-c.e. set; and the Π01 classes have neither nontrivial infinite suprema nor infima in the Medvedev lattice.

We propose a framework for reasoning about program security building on language-theoretic and coalgebraic concepts. The behaviour of a system is viewed as a mapping from traces of high (unobservable) events to low (observable) events: the less the degree of dependency of low events on high traces, the more secure the system. We take the abstract view that low events are drawn from a generic semiring, where they can be combined using product and sum operations; throughout the paper, we provide instances of this framework, obtained by concrete instantiations of the underlying semiring. We specify systems via a simple process calculus, whose semantics is given as the unique homomorphism from the calculus into the set of behaviours, i.e. formal power series, seen as a final coalgebra. We provide a compositional semantics for the calculus in terms of rational operators on formal power series and show that the final and the compositional semantics coincide. This compositional, syntax-driven framework lays a foundation for automation and abstraction of a quantified approach to flow security of system specifications.

In this paper we introduce stable systems of inclusions, which feature chosen arrows A ↪ B to capture the notion that A is a subobject of B, and proposes them as an alternative context to stable systems of monics to discuss partiality. A category C equipped with such a system $\mathscr{I}$, called an i-category, is shown to give rise to an associated category ∂(C,$\mathscr{I}$) of partial maps, which is a split restriction category whose restriction monics are inclusions. This association is the object part of a 2-equivalence between such inclusively split restriction categories and i-categories. $\mathscr{I}$ determines a stable system of monics $\mathscr{I}$+ on C, and, conversely, a stable system of monics $\mathscr{M}$ on C yields an i-category (C[$\mathscr{M}$],$\mathscr{M}$+), giving a 2-adjunction between i-categories and m-categories. The category of partial maps Par(C,$\mathscr{M}$) is isomorphic to the full subcategory of ∂(C[$\mathscr{M}$],$\mathscr{M}$+) comprising the objects of C, and ∂(C,$\mathscr{I}$) ≅ Par(C,$\mathscr{I}$+).

Recently, in order to mix algebraic and logic styles of specification in a uniform framework, the notion of a logic labelled transition system (Logic LTS or LLTS for short) has been introduced and explored. A variety of constructors over LLTS, including usual process-algebraic operators, logic connectives (conjunction and disjunction) and standard temporal modalities (always and unless), have been given. However, no attempt has been made so far to develop the general theory concerning (nested) recursive operations over LLTS and a few fundamental problems are still open. This paper intends to study this issue in a pure process-algebraic style. A few fundamental properties, including precongruence and the uniqueness of consistent solutions of equations, will be established.

Through foreign function interfaces (FFIs), software components in different programming languages interact with each other in the same address space. Recent years have witnessed a number of systems that analyse FFIs for safety and reliability. However, lack of formal specifications of FFIs hampers progress in this endeavour. We present a formal operational model, Java Native Interface (JNI) light (JNIL), for a subset of a widely used FFI – the Java Native Interface (JNI). JNIL focuses on the core issues when a high-level garbage-collected language interacts with a low-level language. It proposes abstractions for handling a shared heap, cross-language method calls, cross-language exception handling, and garbage collection. JNIL can directly serve as a formal basis for JNI tools and systems. We demonstrate its utility by proving soundness of a system that checks native code in JNI programs for type-unsafe use of JNI functions. The abstractions in JNIL are also useful when modelling other FFIs, such as the Python/C interface and the OCaml/C interface.