TACL Seminar Fall '03
Fall '03 Schedule
|Sep 12||Dominic Duggan - Stevens Inst||Type-Based Distributed Access Control||Abstract|
|Sep 26||Spyros Triantafyllis||LIL: A portable low-level language for expressing runtime support code||Abstract|
|Oct 3||Dinghao Wu||Precise Race Detection Using Sequential Program Analysis and Model Checking||Abstract|
|Oct 17||Iliano Cervesato||MSR 3.0: the Logical Meeting Point of Multiset Rewriting and Process Algebra||Abstract|
Type-Based Distributed Access Control
The term 'distributed access control' is used here to refer to a weak form of information flow control, one that ensures that access control restrictions on data are propagated to all the places where it is accessed in a distributed system. The motivation for DAC is accountability: building an audit trail based on accesses to data. The key to making this practical is performing the access checks statically, at compile-time.
Various forms of type-based access control and information flow control require that network security be maintained by the runtime rather than the application. This is because the guarantees of the information flow might otherwise be violated by unsafe communication. This talk presents the 'Key-based Decentralized Label Model (KDLM)', an approach to extending a type system for distributed access control to a typed API for cryptographic operations, that ensures that the access control restrictions are preserved by the application's use of cryptography to secure communications. The notion of 'declassification certificates' is introduced to support the declassification of encrypted data.
This is joint work with Tom Chothia (Stevens) and Jan Vitek (Purdue University).
LIL: A portable low-level language for expressing runtime support code
The ORP managed runtime environment consists of a core virtual machine (VM), several just-in-time compilers (JITs), and a garbage collector (GC). In order to avoid exposing the VM, the JITs, and the GC to each other's implementation specifics, ORP employs a call-based runtime-support interface. Whenever the user's code requires runtime support, an ORP JIT generates calls to VM generated code stubs, which may in turn call the GC. LIL is a low-level, architecture-independent language for expressing such code stubs. The first part of the talk describes LIL and its implementation, with emphasis on the LIL code generator for IPF. It demonstrates that LIL makes the development of runtime support stubs much easier, less error-prone, and more portable than the direct generation of such code stubs in machine language. Moreover, these gains in flexibility and maintainability come at negligible performance loss. The second part of the talk describes how LIL can be used in order to implant VM-dependent or GC-dependent code directly into JITed code. This implanting avoids the performance losses associated with a call-based interface yet retains the modularity of ORP's components.
Precise Race Detection Using Sequential Program Analysis and Model Checking
Based on static program analysis and model checking techniques, a precise static race detector, Zen, has been developed for Windows device drivers. However, the technique is applicable to software verification in general. Zen is precise and static. Comparing to other existing race detectors, Zen is not sound (it may miss potential races, but we believe it will catch a large class of races) but complete (or precise; it won't report false alarms). It checks race conditions automatically and requires no annotations from the users.
The novelty of Zen is that it uses sequential program analysis and model checking techniques. The idea of constructing a sequential program to simulate some interleavings for the input multithreaded program is very useful since many existing sequential program analysis techniques such as alias analysis can be used. The biggest challenge we have encountered is scalability. Currently we have made Zen scalable to thousands of lines of driver code (written in C), and found several serious race conditions in some Windows device drivers, such as kbfilter and fakemodem drivers.
(Joint work with Shaz Qadeer, Microsoft Research)
MSR 3.0: the Logical Meeting Point of Multiset Rewriting and Process Algebra
Multiset rewriting, as embodied in MSR versions 1 and 2, and in the operation of numerous tools for security protocol verification (e.g. CIS/CAPL and the NRL protocol analyzer), is based on local transitions between explicit states. This paradigm has a simple interpretation in terms of both Petri nets and linear logic.
Languages derived from process algebras (e.g. the spi-calculus) and strand spaces are instead based on self-transforming processes, with little emphasis on a notion of state. The translations between languages in these two families (e.g. between MSR and strand spaces, or between MSR and the spi-calculus) have proved cumbersome and somewhat ad-hoc.
MSR 3 is a conservative extension of MSR 1 and 2 that pushes to new heights the links between multiset rewriting and linear logic. This also allows immediate translations to and from process algebraic languages. The tension between state-transition and process-transformation witnessed earlier is internally resolved on logical grounds through a technique reminiscent of Skolemization. This transformation itself is interesting as it allows reasoning on certain aspects of denial-of-service.