Research Highlights of Professor Keedy

Prof. Keedy has often adopted unconventional approaches and methods in his computer science research and this has led to the development of unusual ideas. In his work two principles have had an overriding significance: simplicity and orthogonality. Here are some examples from various projects.

Monads Research Ideas

The following ideas resulted from his research (together with that of his research students) in the context of the Monads Project. For further details, including references to the orignal papers, follow the appropriate links.

The Orthogonal Model for Combining Paging and Segmentation in a Virtual Memory.

This model for combining paging and segmentation treats segments and pages orthogonally, such that a page may contain several segments and/or a segment may be held in several pages, without incurring a severe loss of memory due to internal fragmentation, as occurs in the conventional scheme, which treats a segment as a pageable entity.

Uniform Persistent Virtual Memory.

This technique treats all information and programs as directly addressable entities in a uniform persistent virtual memory, thus eliminating the need for a conventional file system. Unlike Multics, and later the IBM System/38, the Monads implementation uses unique virtual addresses which are large enough to avoid the addressing problems of those systems. Techniques for efficiently translating long addresses and for efficiently resolving page faults were also developed.

Files with Semantic Operations.

Files are not accessed as freestanding data structures (in contrast with conventional file systems) but as modules based on the information hiding principle. This promotes the use of good software engineering techniques but also allows protection to be based on the right to call entry points of the type manager, which can be defined according to the semantics of the data rather than on operations such as "read" and "write".

Uniform Software Modules.

All the major software resources of a system (equivalent to program and data files in conventional systems) are treated uniformly as information hiding modules in the unique persistent virtual memory. This means that an operating system needs to provide only one mechanism for supporting and for linking all kinds of software resource, thus greatly simplifying the operating system. The protection of modules can be uniformly based on module capabilities.

Efficient Support for Unique Names in Capabilities.

An efficient implementation of capabilities is achieved by distinguishing between segment capabilities and module capabilities. Segment capabilities contain the direct virtual addresses of segments and are loaded into capability registers, with the result that long virtual addresses do not need to appear in object code. The segment organization also allows pointers between segments to be not longer than pointers in a conventional system. Module capabilities provide access to the entry points of a module. The unique module identifiers which they contain are "address space numbers" which are that part of a virtual address which identifies a module in the virtual memory. By concatenating literal offsets to these the system information about a module in the memory (e.g. page tables, segment tables) can be directly addressed.

Persistent Protected Processes.

Processes can persist like files in the uniform virtual memory. This, combined with the uniform module structure and the use of module capabilities, makes it straightforward to separate user identification from user authentication, with the latter becomng a "user" responsibility. In this way different users can have different authentication procedures, which both eliminates the need for a central repository for authentication information (e.g. a password file) and makes it difficult for a hacker even to know what he has to do to break into a process. Persistent processes also have efficiency benefits for users. Further security benefits arise from the fact that they can be used to identify users in the system.

Distributed Shared Virtual Memory.

In the first published paper on distributed shared virtual memory (with David Abramson) a scheme is described for supporting a distributed virtual memory based on a Monads-style virtual memory together with a consistency mechanism for distributed pages (similar to cache "write invalidate" schemes). The use of distributed shared memory in a large unique persistent virtual memory system also allows addresses to be unique across a network, and allows capabilities to be transferred automatically in the network (in normal pages of the shared memory).

User Implemented Directories.

Since module capabilities are stored in user addressable (protected) segments directory software is not special and each user can in principle implement his own directory type managers and structure. A directory is basically a mapping from symbolic names to module capabilities. Since a module capability for a directory module is not special it can be stored in another direcotry, thus making structured directory systems possible at the user level.

Using Standard Directory Software to Implement a Secure Communication.

Using only standard directory type managers (without additional software whatsoever) it is possible to implement a simple secure mail system within a local system and in a distributed shared memory system. In this system a sender can always verify the identity of an intended recipient and a receiver can similarly verify the identity of a sender.

Leibniz Research Ideas

To be supplied.

Synchronization Ideas

To be supplied.

L1 Research Ideas

To be supplied.

Secure Risc (S-RISC)

To be supplied.

SPEEDOS (Secure Persistent Execution Environment for Distributed Object Systems)

SPEEDOS is a new project, started in 1998. It can be considered a successor to the Monads projects, but differs from these in two fundamental ways: it is based on conventional hardware (initially the Pentium family of processors) and it enhances the Monads capability based approach by providing mechanisms which allow access controls to be enforced independently of capabilities.

Access Control Security based on Attribute Types and Bracket Routines.

The Kernel of the SPEEDOS system will provide linking mechanisms which support the association of attributes with the major modules of the system. In this way brackets can be added which for example can supply appropriate synchronisation code. The applications of this technique in the security area include the possibility of dynamically adding access control lists, capability revocation lists, and password checkers which are activated as the module is called. They can also be used to record access to a module and thus support a security logging facility.

Solving the Confinement Problem.

Associated with the execution of a process in a module is a Process Security Word, which allows normally available permissions within a module to be turned off for a process executing in the module. These optional permissions include such access modes as

• modifying the persistent data of a module and/or
• modifying the return parameters of an inter-module call and/or
• allowing a called module to have persistent data and/or
• allowing a called module to make further calls.

Such permissions can be turned off either using access rights in capabilities or from bracket routines of an attributed module. Almost all confinement problems can be solved using this technique and some related techniques in the SPEEDOS system.