Advances in Computing Science – ASIAN 2003. Progamming Languages and Distributed Computation Programming Languages and Distributed Computation

Type-safe, high-level languages such as Java ensure that a wide class of failures, including buffer overruns and format string attacks, simply cannot happen. Unfortunately, our computing infrastructure is built with type-unsafe low-level languages such as C, and it is economically impossible to throw away our existing operating systems, databases, routers, etc. and re-code them all in Java.

Fortunately, a number of recent advances in static analysis, language design, compilation, and run-time systems have given us a set of tools for achieving type safety for legacy C code. In this talk, I will survey some of the progress that has been made in the last few years, and focus on the issues that remain if we are to achieve type safety, and more generally, security for our computing infrastructure.

Traditional operating systems protect themselves from user programs with a privilege level facility of CPUs. One problem of the protection-by-hardware approach is that system calls become very slow because heavy operations are required to safely switch the privilege levels of user programs. To solve the problem, we design an operating system that protects itself with a type theory. In our approach, user programs are written in a typed assembly language and the kernel performs type-checking before executing the programs. Then, the user programs can be executed in the kernel mode, because the kernel knows that the type-checked programs do not violate safety of the kernel. Thus, system calls become mere function calls and can be invoked very quickly. We implemented Kernel Mode Linux (KML) that realizes our approach. Several benchmarks show effectiveness of KML.

We provide a formal definition of information flows in XML transformations and, more generally, in the presence of type driven computations and describe a sound technique to detect transformations that may leak private or confidential information. We also outline a general framework to check middleware-located information flows.

We describe a new network service, the ”ticket server”. This service provides ”tickets” that a client can attach to a request for a network service (such as sending email or asking for a stock quote). The recipient of such a request (such as the email recipient or the stockbroker) can use the ticker server to verify that the ticket is valid and that the ticket hasn’t been used before. Clients can acquire tickets ahead of time, independently of the particular network service request. Clients can maintain their stock of tickets either on their own storage, or as a balance recorded by the ticket server. Recipients of a request can tell the ticket server to refund the attached ticket to the original client, thus incrementing the client’s balance at the ticket server. For example, an email recipient might do this if the email wasn’t spam. This paper describes the functions of the ticket server, defines a cryptographic protocol for the ticket server’s operations, and outlines an efficient implementation for the ticket server.

Predicate detection is an important problem in distributed systems. Based on the temporal interactions of intervals, there exists a rich class of modalities under which global predicates can be specified. For a conjunctive predicate φ, we show how to detect the traditional Possibly(φ) and Definitely(φ) modalities along with the added information of the exact interaction type between each pair of intervals (one interval at each process). The polynomial time, space, and message complexities of the proposed on-line detection algorithms to detect Possibly andDefinitely in terms of the fine-grained interaction types per pair of processes, are the same as those of the earlier on-line algorithms that can detect only whether thePossibly andDefinitely modalities hold.

Action refinement is a practical hierarchical method to ease the design of large reactive systems. Relating hierarchical specification to hierarchical implementation is an effective method to decrease the complexity of the verification of these systems. In our previous work [15], this issue has been investigated in the simple case of the refinement of an action by a finite process.

In this paper, on the one hand, we extend our previous results by considering the issue in general, i.e., refining an abstract action by an arbitrary process; on the other hand, we exploit different techniques such that our method is easier to be followed and applied in practice.

Using recent results on integrating induction schemes into decidable theories, a method for generating lemmas useful for reasoning about \(\mathcal{T}\)-based function definitions is proposed. The method relies on terms in a decidable theory admitting a (finite set of) canonical form scheme(s) and ability to solve parametric equations relating two canonical form schemes with parameters. Using nontrivial examples, it is shown how the method can be used to automatically generate many simple lemmas; these lemmas are likely to be found useful in automatically proving other nontrivial properties of \(\mathcal{T}\)-based functions, thus unburdening the user of having to provide many simple intermediate lemmas. During the formalization of a problem, after a user inputs \(\mathcal{T}\)-based definitions, the method can be employed in the background to explore a search space of possible conjectures which can be attempted, thus building a library of lemmas as well as false conjectures. This investigation was motivated by our attempts to automatically generate lemmas arising in proofs of generic, arbitrary data-width parameterized arithmetic circuits. The scope of applicability of the proposed method is broader, however, including generating proofs for proof-carrying codes, certification of proof-carrying code as well as in reasoning about distributed computation algorithms.

Several induction theorem provers were developed to verify functional programs mechanically. Unfortunately, automated verification usually fails for functions with accumulating arguments. In particular, this holds for tail-recursive functions that correspond to imperative programs, but also for programs with nested recursion.

Based on results from the theory of tree transducers, we develop an automatic transformation technique. It transforms accumulative functional programs into non-accumulative ones, which are much better suited for automated verification by induction theorem provers. Hence, in contrast to classical program transformations aiming at improving the efficiency, the goal of our deaccumulation technique is to improve the provability.

The hierarchical process structure of Petri nets can be modelled by languages of series-parallel posets. We show how to extract this structure from a 1-safe Petri net. The technique also applies to represent 1-safe S-systems [11] and communication-free systems [5] in terms of structured programs with cobegin-coend. We also define SR-systems, a class of 1-safe Petri nets which exactly represents programs of this kind.

In this paper, we introduce the crypto-loc calculus, a calculus for modelling secure mobile computations that combine the concepts of locations, cryptography, and code mobility. All these concepts exist in mobile systems, for example, Java applets run within sandboxes or downloaded under an SSL connection. We use observational equivalence of processes as a powerful means of defining security properties, and characterize observational equivalence in terms of a labelled bisimilarity relation, which makes its proof much easier.

Resource control has attracted increasing interest in foundational research on distributed systems. This paper focuses on space control and develops an analysis of space usage in the context of an ambient-like calculus with bounded capacities and weighed processes, where migration and activation require space. A type system complements the dynamics of the calculus by providing static guarantees that the intended capacity bounds are preserved throughout the computation.

Access control systems must be evaluated in part on how well they enable one to distribute the access rights needed for cooperation, while simultaneously limiting the propagation of rights which would create vulnerabilities. Analysis to date implicitly assumes access is controlled only by manipulating a system’s protection state – the arrangement of the access graph. Because of the limitations of this analysis, capability systems have been ”proven” unable to enforce some basic policies: revocation, confinement, and the *-properties (explained in the text).

The paper presents a modular design of a distribution middleware that supports the wide variety of entities that exist in high level languages. Such entities are classified into mutables, immutables and transients. The design is factorized in order to allow multiple consistency protocols for the same entity type, and multiple coordination strategies for implementing the protocols that differ in their failure behavior. The design is implemented and evaluated. It shows a very competitive performance.

A coinduction-based technique to generate an optimal monitor from a Linear Temporal Logic (LTL) formula is presented in this paper. Such a monitor receives a sequence of states (one at a time) from a running process, checks them against a requirements specification expressed as an LTL formula, and determines whether the formula has been violated or validated. It can also say whether the LTL formula is not monitorable any longer, i.e., that the formula can in the future neither be violated nor be validated. A Web interface for the presented algorithm adapted to extended regular expressions is available.

Today, timed automaton is the standard tool for specifying and verifying real-time systems. On the other hand, recently, probabilistic timed automata have been developed in order to express the relative likelihood of the system exhibiting certain behavior. In this paper, we develop the verification method of timed simulation relation of probabilistic timed automata, and apply this method to stepwise refinement developments of real-time systems. This kind of simularity is a valuable theoretical tool to prove soundness of refinements.

Protocols for distributed systems make often use of random transitions to achieve a common goal. A popular example are randomized leader election protocols. We introduce probabilistic product automata (PPA) as a natural model for this kind of systems. To reason about these systems, we propose to use a product version of linear temporal logic (\(\textup{LTL}^{\!\otimes}\)). The main result of the paper is a model-checking procedure for PPA and \(\textup{LTL}^{\!\otimes}\). With its help, it is possible to check qualitative properties of distributed systems automatically.