Henry M. Levy - US grants

While distributed systems are now commonplace, the programming of distributed systems is still a complex task. This research focuses on simplifying the programming of distributed subsystems and applications by supporting distribution in the language. The design of an object- based language, called Emerald, and a distributed run-time system for Emerald, that facilitate the construction of distributed programs will be undertaken. The novel features of Emerald include: (1) a uniform object model that is used for programming both private local objects and shared remote objects, (2) a type system that permits multiple user-defined and compiler-defined implementations, and (3) an explicit notion of object location and mobility. A prototype Emerald system is currently operating on a small local area network of workstations.

This research concerns the design and implementation of a programming system for building highly parallel applications on networks of multiprocessors. Multiprocessor based shared memory multiprocessors are becoming widely available and promise to provide cost effective high performance computing. Multiprocessor workstations will surely be widely available within the next year: one expects them to be even more cost effective than their mainframe counterparts for many applications, just as current uniprocessor workstations often are more cost effective than uniprocessor mainframes. Simply stated, the goal of this research is to provide a facility for programming a network of multiprocessors as if it were a large, integrated, shared memory computer. This effort requires study of several aspects of operating system structure. First, there is a search for programming primitives that provide the right level of abstraction for expressing parallel algorithms. The important tradeoff, in a system integrating parallelism and distribution, is providing uniformity of access across the network without sacrificing local performance. Second, one must explore alternatives in operating system organization for increasing performance on a single multiprocessor node. The objective here is to provide the lowest overhead mechanisms for parallel execution so that programmers can express and utilize medium grained parallelism. Third, one must develop tools that aid the programmer in assessing the performance of his or her application, and in properly optimizing it for an environment of networked multiprocessors. This project is a natural outgrowth of a program of research in distributed and parallel computing systems in which we have been involved for the past 8 years. This program of research has been supported by NSF under a variety of awards; it also has received significant support from industrial sources, particularly Digital Equipment Corporation, whose Firefly prototype multiprocessor workstations will be our experimental vehicle. (The DECSystems Research Center has supplied Fireflys to Washington, Stanford, MIT, Princeton, Toronto, and Cambridge, making these universities uniquely well equipped to conduct experimental research on medium scale multiprocessing.) The results that we have already obtained in our preliminary work on support for parallel computing are in active use by many university sites and by companies such as Sequent, Digital, Microsoft, and Tera.

This award supports infrastructure for research in high performance parallel/distributed computing. The award supports the purchase of a high performance distributed memory computer. The award also supports a programmer to develop, maintain, and distribute software developed on this computer. The research supported by this infrastructure is of two forms: compute intensive research and systems applications research. The compute intensive research includes computer vision, computer graphics, simulations, 3-D animation, and computational chemistry. The systems applications research includes developing fast operating system kernal service routines, programming models of parallel computation activities, software engineering environments, and fundamental research on parallel algorithms for distributed memory computers.

The fundamental issue addressed in this work is the structuring of operating systems to take advantage of multiprocessors so as to yield the best possible application performance. The division of labor between the kernel and the user level is different on a multiprocessor than on a uniprocessor. On a uniprocessor, the kernel is responsible for address spaces, communication, resource allocation, threads, and thread scheduling. On a shared memory multiprocessor, the kernel iis left in charge of address spaces and resource allocation, but communication, threads, and thread scheduling are implemented at user level through runtime support in each address space. Furthermore, each address space is in direct control over certain key aspects of virtual memory management and file management. It is important to understand that while ``micro-kernel'' designs such as Mach 3.0 take the important step of moving the file system, the virtual memory system, etc., out of the kernel to user-level servers, they leave cross-address space communication, threads, and thread scheduling in the kernel. There are structural differences between these monolithic kernels, micro-kernel designs and the ``nano-kernel'' advocated here. In experimental work over the past several years, the researchers have constructed proof-of-concept prototypes in most of the essential areas that must be addressed: locking protocols, user-level threads, cross-address space communication, the kernel interface, processor allocation policies, and user-level virtual memory management. The objectives in this work are of two kinds, direct and indirect. Direct objectives include: (1) integrating these proof-of-concept prototypes into a single system, convincingly demonstrating the viability of the overall approach; and (2) solving the problems that stand in the way of this integration, some of which are known and some of which can only be discovered by undertaking the task. Indirect objectives include: (a) using the ``core'' of the resulting system to study a number of important policy questions (thread scheduling, processor allocation, virtual memory management) that can only be explored given such an experimental testbed, and (b) using this core as a base for exploring high performance system support for more advanced architectures, specifically large scale machines with distributed memory, distributed/parallel programming using high band-width low-latency networks, and wide-address machines.

EIA-9870740 Levy, Henry M. Karlin, Anna R. University of Washington ESS: Distributed Resource Management in Local-Area and Wide-Area Networks Advances in network and processor technology are greatly changing the communication and computational power of networked computers. However, current software systems are unable to utilize the capabilities of modern hardware components, because they are designed for last-generation hardware. The goal of this research is to enable more effective use of future networks and processors through design and implementation of new software structures and algorithms better suited to the characteristics of future hardware. The research focuses on two related but independent domains. First, in local-area networks (clusters), this work seeks to improve the performance of applications through distributed, cluster-wide resource management. It will develop algorithms that permit the tight-knit sharing of all cluster-wide network resources: processors, network, memory, and disk storage. Second, this research seeks to apply experience in global resource management to a much broader domain -- the global Internet. The project will develop and test algorithms that optimally and dynamically locate both data and computation in the Internet, in order to improve data-access latencies and reduce network bandwidth utilization. A significant component of this research is the construction of a software simulation infrastructure to test hypotheses applied to such a large-scale system as the world-wide web.

Proposal Number: 0085670
Title: Interactions of Multithreaded Computing and Operating System Design
PIs: Henry M. Levy and Susan J. Eggers

Abstract:

Over the next decade, highly scalable computer systems consisting of
hundreds or thousands of nodes will become necessary to meet the
demands of emerging global applications, such as Web and database
servers used for Internet commerce. These applications must be
multithreaded to handle the thousands of simultaneous requests. One
promising technology for this scalable server domain is the use of
multithreaded processors; for example, Compaq has announced
Simultaneous Multithreading (SMT) support for its Alpha processor
in the 2002/2003 time frame.

Unfortunately, no research has been conducted on multithreading
support for operating systems or on how to structure operating systems
for multithreaded CPUs. Yet the OS may be crucial in this environment;
e.g., measurements show that a loaded web server can spend 75% of its
time in the OS. The proposed research will develop the software
environment to complement the multithreaded hardware environment
provided by SMT and other fine-grained parallel processors. The
research sits squarely between architecture and operating systems,
examining (1) the design and performance of multithreaded processors
to support OS needs, and (2) the structure of operating systems in
light of the capabilities of multithreaded processors. The research
will focus on these questions in the domain of highly parallel,
request-driven workloads, such as Web servers and database servers.

The explosive popularity and exponentially increasing scale of the World Wide Web has severely stressed the Internet's content-delivery infrastructure. This stress has begun to expose the inefficiencies and limitations of the Web's traditional client-server architecture. A progression of new mechanisms and alternative architectures have recently appeared, including content delivery networks (CDNs), such as Akamai, and peer-to-peer overlay networks, such as Napster. Despite the rapid deployment and global use of these architectures, however, little is understood about their behavior in many cases.

The goals of this research project are threefold. First, the effectiveness of existing Internet content-delivery architectures will be quantitatively analyzed, specifically focusing on (1) cache infrastructure, (2) content-delivery networks, and (3) peer-to-peer networks. Second, based upon these measurements, the design of new or enhanced architectures for Web content delivery will be explored. Third, new designs will be implemented, deployed, and measured. One particular focus will be the design and implementation of adaptive systems that make heavy use of self-measurement and on-line algorithms, e.g., to dynamically optimize request routing, content placement, or the topology of the peer-to-peer overlay network. Overall, the hope is to increase the understanding of content-delivery architectures and to develop new content-delivery mechanisms that greatly improve the behavior of the Internet.

This research seeks to create a new global-scale information facility
on the Internet in which structured data, rather than raw text, is the
key element supported. Currently, the information provided on the
Internet consists of simple text-based documents (HTML), or other
unstructured types such as images and streams. The new facility will
allow data sources to be described by schemas and their content to be
indexed and located. Sophisticated query-oriented database-style
operations will be possible over simple or complex data sources, and
new views of multiple data sources can be created and shared with
other clients. A new class of data processing services will be
possible to collect, manipulate, analyze, and store data.

The first goal of project is to define the basic architecture of a
client, allowing it to share its data with other peers, participate in
distributed query processing, and cooperate with other clients. A
specific data integration formalism will be designed that will allow
clients to integrate their data with others' using both global-as-view
and local-as-view data integration paradigms. Building on this
arthictecture, a new query processing technique will be developed that
can adapt to both data integration paradigms. The project will then
develop intelligent data placement techniques for storing query
results on different clients, thus enabling dramatic performance
improvments for subsequent queries. The data such placed on servers
may become stale, when the source data gets updated: the project will
develop specific update propagation techniques for publishing and
disseminating updates. Finally, the project is developing novel data
indexing techniques that allow clients to search data items globally.

Despite decades of research in extensible operating system
technology, extensions such as device drivers remain
a significant cause of system failures. In Windows XP, for example,
drivers account for 85% of recently reported failures.

In this project, the researchers are developing a reliability subsystem
for commodity operating systems. Their approach is
to improve OS reliability by isolating the OS from driver
failures. Rather than guaranteeing
complete fault tolerance through a new (and incompatible) OS or
driver architecture, their goal is to prevent the vast majority of
driver-caused crashes with little or no change to existing
driver and system code. To achieve this, they isolate drivers within
lightweight protection domains inside the kernel address space.
Drivers run largely unchanged in kernel mode, but are prevented
from corrupting the kernel by both software and hardware means. The
system
also tracks a driver's use of kernel resources to hasten automatic
clean-up during recovery.

To prove the viability of their approach, they are implementing a system
called "Nooks" in the Linux operating system and are using it
to fault-isolate several device
drivers. Their initial results show that Nooks offers a substantial
increase
in the reliability of operating systems, catching and quickly
recovering from 99% of the faults that would otherwise crash the system.
While Nooks was designed for drivers, their techniques generalize to
other kernel extensions as well. The researchers are demonstrating
this by isolating a kernel-mode file system and an
in-kernel Internet service.

Overall, because Nooks supports existing C-language extensions, runs on
a
commodity operating system and commodity hardware, and enables
automated recovery, it represents a substantial step beyond the
specialized architectures and type-safe languages required by previous
efforts directed at safe extensibility.

Proposal Number: 0430477

TItle: OS Support for Application Installation, Execution, and Management in
an Untrustworthy World

PI: Steven Gribble

Modern computer users face many security threats and manageability obstacles. Today's software is increasingly complex, buggy, and prone to vulnerability. In addition to familiar threats such as worms and viruses, users must contend with new, more subtle attacks, such as the spread of spyware. Unfortunately, operating systems do little to help users address the security and vulnerability challenges of the networked environment. For example, it is difficult to determine what programs are running on a system, or what code is responsible for generating visible activity (such as network traffic, file system activity, or windowing activity).
This research focuses on the construction of a new application and operating system architecture based on lightweight virtual machines, with each application being both installed and isolated in its own VM. Installing and removing applications becomes simple, as a VM provides a clean container in which all of the application dependencies and resources can be embedded. Tracking an application and associating activity with its source becomes possible, since activity is easily observable through and traceable to the narrow VM interface. This architecture provides stronger security properties, since malicious applications are isolated from benign programs and data, and a vulnerability within an application no longer puts other applications at risk. The impact of this work will be to provide users with trustworthy infrastructure that they can depend on, and to mitigate damage to users in the case of successful attacks.

Steve Gribble
University of Washington
0626367
Panel: P060975
The detection and prevention of spyware


This project is building a foundation for understanding spyware, and
is advancing the state of the art in detecting and preventing spyware
infections. Our research consists of four broad activities:

Measurement: Using a combination of passive network monitoring
and active Web crawling, we are gathering quantitative evidence
about the nature of spyware and its lifecycle.

Early detection: We are exploring schemes to detect new spyware
threats before they have had the opportunity to cause widespread
infection. For example, we are developing techniques for examining
software found while Web crawling to automatically identify
"spyware-like" behavior, or to statically analyze software to look for
code fragments in common with previously detected spyware.

Prevention: To prevent spyware from reaching a computer, we are
augmenting firewall and proxy systems to detect and block spyware
before it reaches its victims. As well, to prevent new code from
gaining a foothold on a PC, we are exploring ways of "locking down"
what code is permitted to execute.

Infrastructure development: To conduct our research, we are developing
new spyware testing infrastructure and workload repositories; our virtual
"spyware laboratory" uses clusters and virtual machine monitors to
enable high-throughput, scalable sandboxing and observation of
malicious code. As well, we are amassing a large collection of
known spyware programs to enable additional analysis.

Technology is changing our lives in numerous and ever increasing ways. Even a simple modern house contains wired and wireless networks, dedicated devices (such as TV set-top boxes and game consoles), multi-media displays, mobile devices, and traditional computers. Unfortunately, managing this technology is a challenge to all but the most sophisticated users, and as a result, users are increasingly overwhelmed with the administration, integration, and security management of their home infrastructure.

This work simplifies the operation and management of home-based technology, through a new architecture that provides users with simple, powerful, and safe mechanisms for executing programs and storing data. The high-level concept is to support the outsourcing of a large portion of home computing and data management to third parties. The project examines mechanisms that allow third party operators to manage, back-up, upgrade, and diagnose/repair the applications and data resident within the home. As well, the project examines an in-home architecture in which applications and data are hosted off of a powerful server, enabling users are able to access their applications and data from a variety of devices, using a combination of new search mechanisms and thin-client techniques.

Overall, the project makes home computing as easy to use as other home infrastructure, such as heating or security systems that just work in an invisible and natural way. In the long run, the existance of PCs as we know them will disappear and be replaced by appliances that are easily operated by children and adults alike.

Modern operating systems (OSs) are the foundation of our software stacks. Most OS code consists of device drivers -- code that controls devices like keyboards and disks -- yet drivers are complex, stagnant, poorly written, and are responsible for most OS crashes and bugs. Worse, driver frameworks haven't been re-examined for decades, holding back OS innovation.

We are building "driverless OSs," in which drivers are completely removed from the OS. We are replacing complex, low-level device interconnects (like PCI) with commodity, high-speed networks (like USB or Ethernet). With this, drivers become high-level, simple services that act as an RPC layer between OS frameworks and the devices themselves.

We are prototyping two driverless OSs. Our first, called ND, is retrofitted into Linux and is our vehicle for exploring the relationship between the driverless approach and modern multicore hardware. The only part of ND that needs conventional interrupt-driven code is the network driver; as a result, we can eliminate complexity like interrupt-context code and synchronization.

Our second, called browserOS, treats drivers and frameworks as untrusted Web programs. "Web drivers" are written in JavaScript or compiled Native Client code, and are downloaded and executed on-demand by the browser. Web services push Web drivers to clients to interact safely with client-side devices in an OS-agnostic manner.

The expected impact of our work is (a) to make OSs simpler, safer, and more robust, (b) to accelerate the convergence of Web browsers and OSs, and (c) to facilitate new architectural innovations in operating systems.

This grant provides travel support for students wishing to attend the 2014 Operating Systems Design and Implementation (OSDI) conference, which is to be held in Broomfield, Colorado, from Oct 6-8, 2014. OSDI is the leading international conference on both research and industrial innovations in the field of computer systems, which includes operating systems, mobile computing, distributed systems, file systems, computer security and reliability, and the management and debugging of complex computer systems.

This grant supports up to 30 US-based graduate students to attend and participate in the conference, to learn about the latest research directions, and to meet and discuss their research with leading experts in the field. Students have an opportunity to participate in workshops on special topics or on workshops intended to support students with diverse backgrounds, to present research posters and/or talks, and to volunteer as scribes for the conference sessions. This grant support enables attendance of students who would not otherwise have been able to attend.

This award is to assist approximately 35 US-based graduate students to attend the 12th Symposium on Operating Systems Design and Implementation (OSDI 2016) in Savannah, GA, on Nov 2-4, 2016. The conference focuses on computer systems, and brings together professionals from academic and industrial backgrounds in the premier forum for discussing the design, implementation, and implications of systems software. The OSDI Symposium emphasizes innovative research as well as quantified or insightful experiences in systems design and implementation. The papers represent some of the most outstanding work in the areas of file and storage systems, embedded systems, distributed systems, cloud computing, mobile systems, secure and reliable systems, virtualization and troubleshooting of complex systems.

The purpose of this trip is to provide students with unique opportunities to interact with senior researchers in the field, and exposes students to leading edge work. The support requested in this proposal will enable the participation of students who would otherwise be unable to attend OSDI.