DARPA ISO Sponsored Research

1999 Project Summary
A Distributed Framework for
Perpetually Available and SecureInformation Systems
Carnegie Mellon University

Project Website:  http://pasis.ices.cmu.edu
Quad Chart:  Quad Chart  - PPT Format
Objective: PASIS is an innovative framework for demonstrating perpetually available information systems that guarantee the survivability of information under malicious attacks or system component failures.
Approach: PASIS is based on a novel architecture which breaks all information into "chunks" and distributes these "information chunks" in novel ways by using information replication and dispersal methods. This enables PASIS to not have any single point of failure (i.e., it is not possible to destroy the information in PASIS or to degrade the performance, by eliminating or capturing few selected components or information chunks within the system) and thereby achieve a very high degree of security and resiliency against failures and attacks
Recent FY-99 Accomplishments:
During FY-99, we defined the basic architecture of Pasis. The heart of the architecture we defined in the last three months is the Pasis agent, a small program that always runs on each piece of computing hardware that is a part of the Pasis collective. The Pasis agent on one machine communicates with the Pasis agents on other neighboring machines, exchanging information and fulfilling requests.  Pasis agents are all identical to one another; there is no central control or master agent, and thus no single point of system failure. Since in the envisioned application domains, the number of computers can be very large (e.g., millions of computers), we are investigating automatic schemes for partitioning and distributing knowledge that meet our security, reliability and efficiency requirements. Each machine connected to Pasis runs one Pasis agent which acts as a representative of all the agents in the systems. Applications communicate with the local agent to submit requests and the local agent dynamically distribute these requests to other agents in the system.

Applications connect with the Pasis collective by establishing a connection with their local agent.When an application makes a request of Pasis, its agent acts on its behalf to carry out the request and return the result.Multiple applications can connect to a single agent at once, and the agent will keep track of pending requests and associated security levels for each application.Since the application interface to the entire Pasis collective is through the local agent, applications are freed from the responsibility of maintaining network configurations or security information.Furthermore, any exchange of sensitive data between the application and the local agent is achieved via direct memory transfers on the local machine, making eavesdropping unlikely.

During this quarter, we defined the three basic services that each local agent must respond to. These services are persistence, concurrency and security services. The persistence service allows agents thus applications to store and retrieve information to and from Pasis. The concurrency service provides basic locking mechanisms so that multiple applications can access and modify the same piece of information. The security service allows applications to modify the security parameters of the information they store. These services are modeled after the Corba services. In fact the communication protocol employed by these services uses Corba. In the first implementation of these services we used Omni Orb a freely available Corba ORB (Object request Broker). We also defined two other services that agents do not publish but use to communicate among themselves. These services are communication and network services. The communication service allows the dispersal of the information to multiple agents and manage the communication between these agents. The network service maintains a list and properties of the agents connected to the system.

In the last period, we also started investigating how to enhance the basic Pasis architecture by implementing a technique called information dispersal protocol (also called secure secret sharing, and threshold scheme).This information dispersal technique breaks the information into n shares so that every shareholder has one of the shares and any subset of size m of the shareholders can recreate the information but (m-1) shareholders cannot.This scheme is referred to as a (m-n) threshold scheme and has been successfully used in securing crypto keys.However, it cannot be applied directly to distributed information systems where the information is dynamically created, accessed and updated by multiple users.

During this period we also participated in the Intrusion Tolerant Systems Kickoff meeting that was held in Phoenix, Arizona.

FY-00 Plans:
During FY-00, we are planning to continue to define and implement these novel security and replication schemes. We are also planning to provide methods for agent construction, information partitioning, and efficient reasoning through three major components: (1) embedded distributed security and replication mechanisms, (2) a distributed multiversioning dependency-based access control protocol and (3) Pasis infrastructure

Embedded Distributed Security and Replication Mechanisms. We are planning to continue to develop mechanisms for automatically replicating information many times across many computers using information dispersal. These mechanisms will have a dual advantage: robustness and security. To guarantee the best performance and quality of service, our proposed scheme will be realized through automatic selection of the information dispersal scheme among available threshold schemes. More specifically, our approach will employ a family of different hashing and information dispersal algorithms (each of which has different properties) which provide different degrees of dependability, reliability, availability, safety and security, thus providing and guaranteeing quality-of-service while maintaining the best possible performance.

Distributed Multiversioning Dependency-based Access Control. To guarantee integrity of information and services against failures and attacks PASIS will use a novel access control protocol. This access control protocol is an optimistic, multiversioning dependency-based algorithm.In this algorithm, each transaction will have a dependency set which contains the set of version identifiers of data items that it has read.Each version of a data item will also have a dependency set, which is the set of version identifiers that were written ‘simultaneously’ with that version. In FY00, we are planning to start investigating this protocol and develop a prototype to test these ideas,

PASIS Infrastructure. In FY00, we will start developing a highly flexible infrastructure, which includes tools and libraries, for efficient description of PASIS programs. In FY00, we will also provide libraries and extensions for C++ and Java so that existing and legacy systems can be easily converted to PASIS systems that guarantee perpetual availability.

Technology Transition:
Technical Papers and Reports:During the course of the project we will disseminate our results through technical papers published in conferences and journals and also through regular technical and progress reports that we will write for DARPA.

Web Site:In order to provide early and timely dissemination of our developments, we created and maintained a PASIS Web site.

Access to Software Tools:During the course of this project, we will be developing several software tools.Specifically, we plan to encapsulate the system and distribute as a toolkit to other participants in this program and other Government parties that the DARPA may designate from time to time.The toolkit will be either downloadable from our PASIS Web Site or we will distribute it on a CD.The alpha version of the toolkit will be available at the end 18 months and an enhanced version incorporating user feedback will be available at the end of the second year of the contract.We also plan to release a fully documented final version of the toolkit for use by the Government and the scientific community at the end of the contract.

Demonstrations:  During the course of this project, we plan to hold several demonstrations that describe our technologies and developments. 

Principal Investigator: Dr. Pradeep K. Khosla, PI
Philip and Marsha Dowd Professor of Engineering, and Department Head, 
Electrical and Computer Engineering Hamerschlag Hall 
Carnegie Mellon University Pittsburgh, PA 15213

Tel: (412) 268-5090 
Fax: (412) 268 5787
e-mail: pkk@ece.cmu.edu 

Ms. Rhonda Moyer Carnegie 
Mellon University Institute for Complex Engineered Systems 
5000 Forbes Avenue Pittsburgh PA 15213 
Tel: (412) 268-6410 
Fax: (412) 268-5229
e-mail: rm7q@andrew.cmu.edu

Return to the ITS Project Summary Page  ]