Publications by Eric Eide
|
Publications by Eric Eide
|
These documents are provided to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
| Pubs | Most of my papers are available online. Look in the: | Coauthors |
Links to the pages of my co-conspirators: Will Archer | Venkat Chakravarthy | Yvonne Coady | Nathan Cooprider | Matthew Flatt | Bryan Ford | Kevin Frei | Juliana Freire | David Gay | Wilson Hsieh | Chris Johnson | Jay Lepreau | Gary Lindstrom | David H. Lorenz | Sean McDirmid | Ken Parker | John Regehr | Alastair Reid | James Simister | Tim Stack | Leigh Stoller | Sean Walton | Bin Xin | Joe Zachary |
| Related | You might also want to look at: |
Listed in order from newest to oldest.
Listed in order from newest to oldest.
C's volatile qualifier is intended to provide a reliable link between operations at the program level and operations at the memory system level. We tested thirteen production-quality C compilers and, for each, we found situations in which the compiler generates incorrect code for accessing volatile variables. This result is disturbing because it implies that embedded software and operating systems—both typically coded in C, both being bases for many mission-critical and safety-critical applications, and both relying on the correct translation of volatiles—may be being miscompiled.Our contribution centers around a novel technique for finding volatile bugs and a novel technique for working around them. First, we developed access summary testing: an efficient, practical, and automatic way to detect code generation errors related to the volatile qualifier. We have found a number of compiler bugs by performing access summary testing on randomly generated C programs. Some of these bugs have already been confirmed and even fixed by compiler developers. Second, we present and evaluate a workaround for the compiler defects we discovered. In 93% of the cases in which one of our randomly generated programs is miscompiled, we can cause the faulty C compiler to produce correctly behaving code by applying a straightforward source-level transformation to the test program.
In a software product line, the binding time of a feature is the time at which one decides to include or exclude a feature from a product. Typical binding site implementations are intended to support a single binding time only, e.g., compile time or run time. Sometimes, however, a product line must support features with variable binding times. For instance, a product line may need to include both embedded system configurations, in which features are selected and optimized early, and desktop configurations, in which client programs choose features on demand.We present a new technique for implementing the binding sites of features that require flexible binding times. Our technique combines design patterns and aspect-oriented programming: a pattern encapsulates the variation point, and targeted aspects—called edicts—set the binding times of the pattern participants. We describe our approach and demonstrate its usefulness by creating a middleware product line capable of serving the desktop and embedded domains. Our product line is based on JacORB, a middleware platform with many dynamically configurable features. By using edicts to select features at compile time, we create a version of JacORB more suited to resource-constrained environments. By configuring four JacORB subsystems via edicts, we achieve a 32.2% reduction in code size. Our examples show that our technique effectively modularizes binding-time concerns, supporting both compile-time optimization and run-time flexibility as needed.
Reliable sensor network software is difficult to create: applications are concurrent and distributed, hardware-based memory protection is unavailable, and severe resource constraints necessitate the use of unsafe, low-level languages. Our work improves this situation by providing efficient memory and type safety for TinyOS 2 applications running on the Mica2, MicaZ, and TelosB platforms. Safe execution ensures that array and pointer errors are caught before they can corrupt RAM. Our contributions include showing that aggressive optimizations can make safe execution practical in terms of resource usage; developing a technique for efficiently enforcing safety under interrupt-driven concurrency; extending the nesC language and compiler to support safety annotations; finding previously unknown bugs in TinyOS; and, finally, showing that safety can be exploited to increase the availability of sensor networks applications even when memory errors are left unfixed.
The software that runs on a typical wireless sensor network node must address a variety of constraints that are imposed by its purpose and implementation platform. Examples of such constraints include real-time behavior, highly limited RAM and ROM, and other scarce resources. These constraints lead to crosscutting concerns for the implementations of sensor network software: that is, all parts of the software must be carefully written to respect its resource constraints. Neither traditional languages (such as C) nor component-based languages (such as nesC) for implementing sensor network software allow programmers to deal with crosscutting resource constraints in a modular fashion.In this paper we describe Aspect nesC (ANesC), a language we are now implementing to help programmers modularize the implementations of crosscutting concerns within sensor network software. Aspect nesC extends nesC, a component-based dialect of C, with constructs for aspect-oriented programming. In addition to combining the ideas of components and aspects in a single language, ANesC will provide specific and novel constructs for resource-management concerns. For instance, pointcuts can identify program points at which the run-time stack is about to be exhausted or a real-time deadline has been missed. Corrective actions can be associated with these points via ``advice.'' A primary task of the Aspect nesC compiler is to implement such resource-focused aspects in an efficient manner.
The networked and distributed systems research communities have an increasing need for ``replayable'' research, but our current experimentation resources fall short of satisfying this need. Replayable activities are those that can be re-executed, either as-is or in modified form, yielding new results that can be compared to previous ones. Replayability requires complete records of experiment processes and data, of course, but it also requires facilities that allow those processes to actually be examined, repeated, modified, and reused.We are now evolving Emulab, our popular network testbed management system, to be the basis of a new experimentation workbench in support of realistic, large-scale, replayable research. We have implemented a new model of testbed-based experiments that allows people to move forward and backward through their experimentation processes. Integrated tools help researchers manage their activities (both planned and unplanned), software artifacts, data, and analyses. We present the workbench, describe its implementation, and report how it has been used by early adopters. Our initial case studies highlight both the utility of the current workbench and additional usability challenges that must be addressed.
The network and distributed systems research communities have an increasing need for ``replayable'' research, but our current experimentation resources fall short of reaching this goal. Replayable activities are those that can be re-executed, either as-is or in modified form, yielding new results that can be compared to previously obtained results. Replayability requires complete records of experiment processes and data, of course, but it also requires facilities that allow those processes to actually be examined, repeated, modified, and reused for new studies.We are now evolving Emulab, our popular network testbed management system, to be the basis of a new ``experimentation workbench'' in support of realistic, large-scale, replayable networking research. We have implemented a new model of testbed-based experiments, based on scientific workflow, that allows people to move forward and backward through their experimentation processes. Integrated tools in the workbench help researchers manage their activities (both planned and unplanned), software artifacts, data, and analyses. In this paper we present the workbench, describe its implementation, and report how it has been used by early adopters. Our initial case studies, using PlanetLab nodes, cluster PCs, 802.11 wireless, and software radio, have highlighted both the utility of the current workbench and additional usability challenges that must be addressed.
We report our experience in implementing type and memory safety in an efficient manner for sensor network nodes running TinyOS: tiny embedded systems running legacy, C-like code. A compiler for a safe language must often insert dynamic checks into the programs it produces; these generally make programs both larger and slower. In this paper, we describe our novel compiler toolchain, which uses a family of techniques to minimize or avoid these run-time costs. Our results show that safety can in fact be implemented cheaply on low-end 8-bit microcontrollers.
Sensor network applications should be reliable. However, TinyOS, the dominant sensor net OS, lacks basic building blocks for reliable software systems: memory protection, isolation, and safe termination. These features are typically found in general-purpose operating systems but are believed to be too expensive for tiny embedded systems with a few kilobytes of RAM. We dispel this notion and show that CCured, a safe dialect of C, can be leveraged to provide memory safety for largely unmodified TinyOS applications. We build upon safety to implement two very different environments for TinyOS applications. The first, Safe TinyOS, provides a minimal kernel for safely executing trusted applications. Safe execution traps and identifies bugs that would otherwise have silently corrupted RAM. The second environment, UTOS, implements a user-kernel boundary that supports isolation and safe termination of untrusted code. Existing TinyOS components can often be ported to UTOS with little effort. To create our environments, we substantially augmented the CCured toolchain to emit code that is safe under interrupt-driven concurrency, to reduce storage requirements by compressing error messages, to refactor direct hardware access into calls to trusted helper functions, and to make safe programs more efficient using whole-program optimization. A surprising result of our work is that a safe, optimized TinyOS program can be faster than the original unsafe, unoptimized application.
The main forces that shaped current network testbeds were the needs for realism and scale. Now that several testbeds support large and complex experiments, management of experimentation processes and results has become more difficult and a barrier to high-quality systems research. The popularity of network testbeds means that new tools for managing experiment workflows, addressing the ready-made base of testbed users, can have important and significant impacts.We are now evolving Emulab, our large and popular network testbed, to support experiments that are organized around scientific workflows. This paper summarizes the opportunities in this area, the new approaches we are taking, our implementation in progress, and the challenges in adapting scientific workflow concepts for testbed-based research. With our system, we expect to demonstrate that a network testbed with integrated scientific workflow management can be an important tool to aid research in networking and distributed systems.
The main forces that shaped current network testbeds were the needs for realism and scale. Now that several testbeds support large and complex experiments, management of experimentation processes and results has become more difficult and a barrier to high-quality systems research. The popularity of network testbeds means that new tools for managing experiment workflows, addressing the ready-made base of testbed users, can have important and significant impacts.We are now evolving Emulab, our large and popular network testbed, to support experiments that are organized around scientific workflows. This paper summarizes the opportunities in this area, the new approaches we are taking, our implementation in progress, and the challenges in adapting scientific workflow concepts for testbed-based research. With our system, we expect to demonstrate that network testbeds with integrated scientific workflow management can be an important tool to aid research in networking and distributed systems.
An implementation and deployment plan is critically important in the development of a software product or product line. A good plan results from an informed feature analysis that incorporates crosscutting concerns such as variability management and the project time-line. A poor feature analysis, on the other hand, can result in an ineffective project schedule and an implementation that hinders the delivery of new features. An early understanding of product features can help a project planner create an effective plan, and help a designer avoid unsupportable code.Feature typing is our emerging model that describes what features are in terms of two separate natures. The vertical nature of a feature generally follows a UML's use-case path, describing what the feature does. The horizontal nature expresses a program characteristic, describing what the feature has. Because each nature affects feature interaction and product integration and testing, early identification and typing can increase predictability of project time-lines and reduce code complexity.
This paper details the feature typing model and its application for two separate case studies. The studies demonstrate the ways that feature typing can help with the design, planning, coding, and testing of feature implementations. The studies also illuminate the limitations of the approach.
Many real-world distributed, real-time, embedded (DRE) systems, such as multi-agent military applications, are built using commercially available operating systems, middleware, and collections of pre-existing software. The complexity of these systems makes it difficult to ensure that they maintain high quality of service (QoS). At design time, the challenge is to introduce coordinated QoS controls into multiple software elements in a non-invasive manner. At run time, the system must adapt dynamically to maintain high QoS in the face of both expected events, such as application mode changes, and unexpected events, such as resource demands from other applications.In this paper we describe the design and implementation of a CPU Broker for these types of DRE systems. The CPU Broker mediates between multiple real-time tasks and the facilities of a real-time operating system: using feedback and other inputs, it adjusts allocations over time to ensure that high application-level QoS is maintained. The broker connects to its monitored tasks in a non-invasive manner, is based on and integrated with industry-standard middleware, and implements an open architecture for new CPU management policies. Moreover, these features allow the broker to be easily combined with other QoS mechanisms and policies, as part of an overall end-to-end QoS management system. We describe our experience in applying the CPU Broker to a simulated DRE military system. Our results show that the broker connects to the system transparently and allows it to function in the face of run-time CPU resource contention.
Feature-wise decomposition is an important approach to building configurable software systems. Although there has been research on the usefulness of particular tools for feature-wise decomposition, there are not many informative comparisons on the relative effectiveness of different tools. In this paper, we compare AspectJ and Jiazzi, which are two different systems for decomposing Java programs. AspectJ is an aspect-oriented extension to Java, whereas Jiazzi is a component system for Java. To compare these systems, we reimplemented an AspectJ implementation of a highly configurable CORBA Event Service using Jiazzi. Our experience is that Jiazzi provides better support for structuring the system and manipulating features, while AspectJ is more suitable for manipulating existing Java code in non-invasive and unanticipated ways.
Many real-world distributed, real-time, embedded (DRE) systems, such as multi-agent military applications, are built using commercially available operating systems, middleware, and collections of pre-existing software. The complexity of these systems makes it difficult to ensure that they maintain high quality of service (QoS). At design time, the challenge is to introduce coordinated QoS controls into multiple software elements in a non-invasive manner. At run time, the system must adapt dynamically to maintain high QoS in the face of both expected events, such as application mode changes, and unexpected events, such as resource demands from other applications.In this paper we describe the design and implementation of a CPU Broker for these types of DRE systems. The CPU Broker mediates between multiple real-time tasks and the facilities of a real-time operating system: using feedback and other inputs, it adjusts allocations over time to ensure that high application-level QoS is maintained. The broker connects to its monitored tasks in a non-invasive manner, is based on and integrated with industry-standard middleware, and implements an open architecture for new CPU management policies. Moreover, these features allow the broker to be easily combined with other QoS mechanisms and policies, as part of an overall end-to-end QoS management system. We describe our experience in applying the CPU Broker to a simulated DRE military system. Our results show that the broker connects to the system transparently and allows it to function in the face of run-time CPU resource contention.
Mobile code makes it possible for users to define the processing and protocols used to communicate with a remote node, while still allowing the remote administrator to set the terms of interaction with that node. However, mobile code cannot do anything useful without a rich execution environment, and no administrator would install a rich environment that did not also provide strict controls over the resources consumed and accessed by the mobile code.Based on our experience with ANTS, we have developed Bees, an execution environment that provides better security, fine-grained control over capsule propagation, simple composition of active protocols, and a more flexible mechanism for interacting with end-user programs. Bees' security comes from a flexible authentication and authorization mechanism, capability-based access to privileged resources, and integration with our custom virtual machine that provides isolation, termination, and resource control. The enhancements to the mobile code environment make it possible to compose a protocol with a number of ``helper'' protocols. In addition, mobile code can now interact naturally with end-user programs, making it possible to communicate with legacy applications. We believe that these features offer significant improvements over the ANTS execution environment and create a more viable platform for active applications.
Design patterns are a valuable mechanism for emphasizing structure, capturing design expertise, and facilitating restructuring of software systems. Patterns are typically applied in the context of an object-oriented language and are implemented so that the pattern participants correspond to object instances that are created and connected at run-time. This paper describes a complementary realization of design patterns, in which many pattern participants correspond to statically instantiated and connected components.Our approach separates the static parts of the software design from the dynamic parts of the system behavior. This separation makes the software design more amenable to analysis, thus enabling more effective and domain-specific detection of system design errors, prediction of run-time behavior, and more effective optimization. This technique is applicable to imperative, functional, and object-oriented languages: we have extended C, Scheme, and Java with our component model. In this paper, we illustrate our approach in the context of the OSKit, a collection of operating system components written in C.
Design patterns are a valuable mechanism for emphasizing structure, capturing design expertise, and facilitating restructuring of software systems. Patterns are typically applied in the context of an object-oriented language and are implemented so that the pattern participants correspond to object instances that are created and connected at run-time. This paper describes a complementary realization of design patterns, in which the pattern participants are statically instantiated and connected components.Our approach separates the static parts of the software design from the dynamic parts of the system behavior. This separation makes the software design more amenable to analysis, enabling more effective and domain specific detection of system design errors, prediction of run-time behavior, and more effective optimization. This technique is applicable to imperative, functional, and object-oriented languages: we have extended C, Scheme, and Java with our component model. In this paper, we illustrate this approach in the context of the OSKit, a collection of operating system components written in C.
Knit is a new component specification and linking language. It was initially designed for low-level systems software, which requires especially flexible components with especially well-defined interfaces. For example, threads and virtual memory are typically implemented by components within the system, instead of being supplied by some execution environment. Consequently, components used to construct the system must expose interactions with threads and memory. The component composition tool must then check the resulting system for correctness, and weave the components together to achieve reasonable performance.Component composition with Knit thus acts like aspect weaving: component interfaces determine the ``join points'' for weaving, while components (some of which may be automatically generated) implement aspects. Knit is not limited to the construction of low-level software, and to the degree that a set of components exposes fine-grained relationships, Knit provides the benefits of aspect-oriented programming within its component model.
Knit is a new component definition and linking language for systems code. Knit helps make C code more understandable and reusable by third parties, helps eliminate much of the performance overhead of componentization, detects subtle errors in component composition that cannot be caught with normal component type systems, and provides a foundation for developing future analyses over C-based components, such as cross-component optimization. The language is especially designed for use with component kits, where standard linking tools provide inadequate support for component configuration. In particular, we developed Knit for use with the OSKit, a large collection of components for building low-level systems. However, Knit is not OSKit-specific, and we have implemented parts of the Click modular router in terms of Knit components to illustrate the expressiveness and flexibility of our language. This paper provides an overview of the Knit language and its applications.
Distributed applications are complex by nature, so it is essential that there be effective software development tools to aid in the construction of these programs. Commonplace ``middleware'' tools, however, often impose a tradeoff between programmer productivity and application performance. For instance, many CORBA IDL compilers generate code that is too slow for high-performance systems. More importantly, these compilers provide inadequate support for sophisticated patterns of communication. We believe that these problems can be overcome, thus making IDL compilers and similar middleware tools useful for a broader range of systems.To this end we have implemented Flick, a flexible and optimizing IDL compiler, and are using it to produce specialized high-performance code for complex distributed applications. Flick can produce specially ``decomposed'' stubs that encapsulate different aspects of communication in separate functions, thus providing application programmers with fine-grain control over all messages. The design of our decomposed stubs was inspired by the requirements of a particular distributed application called Khazana, and in this paper we describe our experience to date in refitting Khazana with Flick-generated stubs. We believe that the special IDL compilation techniques developed for Khazana will be useful in other applications with similar communication requirements.
The author of a distributed system is often faced with a dilemma when writing the system's communication code. If the code is written by hand (e.g., using Active Messages) or partly by hand (e.g., using MPI) then the speed of the application may be maximized, but the human effort required to implement and maintain the system is greatly increased. On the other hand, if the code is generated using a high-level tool (e.g., a CORBA IDL compiler) then programmer effort will be reduced, but the performance of the application may be intolerably poor. The tradeoff between system performance and development effort arises because existing communication middleware is inefficient, imposes excessive presentation layer overhead, and therefore fails to expose much of the underlying network performance to application code. Moreover, there is often a mismatch between the desired communication style of the application (e.g., asynchronous message passing) and the communication style of the code produced by an IDL compiler (synchronous remote procedure call). We believe that this need not be the case, but that established optimizing compiler technology can be applied and extended to attack these domain-specific problems.We have implemented Flick, a flexible and optimizing IDL compiler, and are using it to explore techniques for producing high-performance code for distributed and parallel applications. Flick produces optimized code for marshaling and unmarshaling data; experiments show that Flick-generated stubs can marshal data between 2 and 17 times as fast as stubs produced by other IDL compilers. Further, because Flick is implemented as a ``kit'' of components, it is possible to extend the compiler to produce stylized code for many different application interfaces and underlying transport layers. In this paper we outline a novel approach for producing ``decomposed'' stubs for a distributed global memory service.
An interface definition language (IDL) is a nontraditional language for describing interfaces between software components. IDL compilers generate ``stubs'' that provide separate communicating processes with the abstraction of local object invocation or procedure call. High-quality stub generation is essential for applications to benefit from component-based designs, whether the components reside on a single computer or on multiple networked hosts. Typical IDL compilers, however, do little code optimization, incorrectly assuming that interprocess communication is always the primary bottleneck. More generally, typical IDL compilers are ``rigid'' and limited to supporting only a single IDL, a fixed mapping onto a target language, and a narrow range of data encodings and transport mechanisms.Flick, our new IDL compiler, is based on the insight that IDLs are true languages amenable to modern compilation techniques. Flick exploits concepts from traditional programming language compilers to bring both flexibility and optimization to the domain of IDL compilation. Through the use of carefully chosen intermediate representations, Flick supports multiple IDLs, diverse data encodings, multiple transport mechanisms, and applies numerous optimizations to all of the code it generates. Our experiments show that Flick-generated stubs marshal data between 2 and 17 times faster than stubs produced by traditional IDL compilers, and on today's generic operating systems, increase end-to-end throughput by factors between 1.2 and 3.7.
Many modern human-computer interfaces are difficult for people to use. This is often because these interfaces make no significant attempt to communicate with the people who use them. In other words, these interfaces are uncooperative: They do not adapt themselves to their users' needs and they are insensitive to human foibles. Ordinary command line interfaces such as that of the UNIX C shell (csh) are intolerant of even the most simple input errors, even when those errors have obvious corrections. An ``intelligent'' UNIX shell interface, on the other hand, would make use of knowledge and interaction context in order to interpret — and as necessary, correct — its users' commands.Valet is a prototype of such an ``intelligent'' interface to the UNIX C shell. Valet adds knowledge-based parsing and input correction to the shell by encapsulating an ordinary C shell process within a framework that allows Valet to control the shell's input and output. Valet intercepts shell commands and parses them, using its knowledge of the most popular UNIX shell commands, its built-in model of the file system, and data that describe the commands and files most often and recently referenced by individual users. Valet incorporates heuristics designed to detect and correct the kinds of mistakes that experienced users make most frequently: typographical errors, file location errors, and minor syntactic errors.
In order to evaluate the interface, eleven volunteers agreed to use Valet in the course of their normal work for approximately four weeks. The commands that those people entered, along with Valet's responses, were recorded and analyzed in order to measure the overall usefulness and effectiveness of the system. The data from the experiment suggest that knowledge-based, error-tolerant, ``intelligent'' command parsing can have very beneficial effects. The experiment also pointed to ways in which Valet could be improved.
| Eric Eide <eeide@cs.utah.edu> | Last modified: Sat Apr 19 16:35:29 MDT 2008 |