• Tuesday, December 20, 2005 - Radu Stoleru, A Flexible and Robust System for Node Localization in Wireless Sensor Networks
  • Tuesday, December 20, 2005 - Xiangyu Jin, Adaptive Relevance Feedback in Multimedia Retrieval
  • Thursday, December 15, 2005 - Kellie-Ann Smith, Nancy's Pantry: Assisting the Visually Impaired in Restaurant Meal Selection
  • Monday, December 12, 2005 - Nishit Tewari, An Event Notification Service for Mobile Ad hoc Networks
  • Monday, December 12, 2005 - Tenghui Zhu, GPU-Accelerated Render Cache
  • Wednesday, December 07, 2005 - Brian Garback, XACML for RBAC and CaDABRA: Constrained Delegation and Attribute-Based Role Assignment
  • Tuesday, December 06, 2005 - Anant Mudambi, A Transport Protocol for Dedicated End-to-End Circuits
  • Monday, December 05, 2005 - Nolan Goodnight, 4D Compression and Relighting with High-Resolution Light Transport Matrices
  • Thursday, December 01, 2005 - Shubhendu S. Mukherjee, Architectural Vulnerability Factors (or, does a soft error matter?)
  • Wednesday, November 30, 2005 - Lin Gu, Virtual Sensor Networks
  • Wednesday, November 16, 2005 - Manuvir Das, Software Excellence via Program Analysis at Microsoft
  • Wednesday, November 16, 2005 - Ankit Malhotra, Computational Infrastructure for High Throughput RNAi screening experiments
  • Friday, October 28, 2005 - Vincent W. Freeh, High-performance, power-aware computing
  • Friday, October 21, 2005 - Ajay Kulhari, RT-Transport: A Real-Time Transport Protocol for Sensor Networks
  • Tuesday, October 18, 2005 - Marc Levoy, Light field photography and videography
  • Thursday, September 29, 2005 - Ben Zorn, Execution Environments for Building Dependable Systems
  • Tuesday, September 13, 2005 - Hector Garcia-Molina, Generic Entity Resolution
  • Thursday, September 08, 2005 - Lecia Barker, Revealing Behaviors that Influence Learning Environment: A Qualitative Exploration of Computer Science Classrooms
  • Friday, August 26, 2005 - Michele Co, Designing Energy Efficient Fetch Engines
  • Friday, August 12, 2005 - M. Anthony Aiello, ASPEN: A Framework for Checking Aircraft Digital System Properties.
  • Wednesday, August 10, 2005 - Joseph Calandrino, Private Resource Pairing
  • Monday, August 01, 2005 - Michael Crane, Using Calling Sequence Diversity to Defeat Return-to-libc Attacks
  • Friday, July 29, 2005 - Hridesh Rajan, Unifying Aspect- and Object-Oriented Program Design
  • Thursday, July 28, 2005 - Leonid Bolotnyy, Multi-Tag Radio Frequency Identification Systems
  • Wednesday, July 27, 2005 - Marco Caccamo, Implicit RT-QoS for Wireless Collaborative Real-Time Systems
  • Friday, July 22, 2005 - Gregory Mattes, A Naming Service for Overlay Networks
  • Monday, July 11, 2005 - Ying Lu, Towards Self-Managing Computing Systems: An Augmented Control Theory Approach
  • Monday, July 11, 2005 - Ji-Wook Jo, An Area Event Data Service in Wireless Sensor Networks
  • Friday, July 08, 2005 - Richard P. Martin, Bayesian Positioning in Wireless Networks
  • Thursday, July 07, 2005 - Ronghua Zhang, QoS Support for Legacy Applications
  • Friday, June 17, 2005 - John Tran, Simulation of Excitable Media Wave Propagation on Arbitrary 3D Surfaces
  • Thursday, June 16, 2005 - Rui Wang, An End-to-end Solution for Interactive Rendering with Complex Lighting models
  • Friday, May 27, 2005 - Robert G. Bartholet, A Practical Process for Simulation Component Reuse
  • Thursday, May 26, 2005 - Kathi Fisler, Modular Verification of Feature-Rich Software
  • Wednesday, May 25, 2005 - Shriram Krishnamurthi, Programming and Verifying the Interactive Web
  • Wednesday, May 25, 2005 - Julie Parent, An Exploration of Combinatorial Optimization Techniques for Optimization Phase Ordering
  • Thursday, May 12, 2005 - Yuanyuan Song, Join Point Interfaces: Information Hiding Modularity for Aspect-Oriented Program Design
  • Thursday, May 12, 2005 - Mary Jane Irwin, On-Line Power Aware Systems
  • Tuesday, May 10, 2005 - Binjia Jiao, SNEDL: Sensor Network Event Description Language for Event Service Architecture
  • Thursday, May 05, 2005 - Xiang Yin, Echo: A Practical Approach to Formal Verification
  • Thursday, May 05, 2005 - Jinlin Yang, Automatic Inference and Effective Application of Temporal Specifications
  • Thursday, April 28, 2005 - Jie Luo, Limited Community Name Server System
  • Friday, April 22, 2005 - Sudhanva Gurumurthi, Power Management of Enterprise Storage Systems
  • Tuesday, April 19, 2005 - Azer Bestavros, Exploiting the Transients of Adaptation for RoQ Attacks on Internet Resources
  • Monday, April 18, 2005 - Brent Waters, Fuzzy Identity-Based Encryption -- Privacy for the Unprepared User
  • Monday, April 18, 2005 - Elisabeth A. Strunk, Reconfiguration Assurance in Embedded System Software
  • Thursday, April 14, 2005 - Jason D. Hiser, Effective Algorithms for Partitioned Memory Hierarchies in Embedded Systems
  • Wednesday, April 13, 2005 - Yih-Chun Hu, Securing Network Routing
  • Tuesday, April 12, 2005 - Yuan Wei, QoS Management for Distributed Real-Time Data Services
  • Monday, April 11, 2005 - Yutao Zhong, Whole-Program Data Locality Hierarchy
  • Friday, April 08, 2005 - Nina Mishra, Privacy-Preserving Auditing Algorithms
  • Friday, April 08, 2005 - William S. Greenwell, Pandora: An Approach to Analyzing Safety-Related Digital System Failures
  • Monday, April 04, 2005 - Michael Swift, Improving the Reliability of Commodity Operating Systems
  • Monday, March 28, 2005 - Kevin Fu, Secure content distribution using untrusted servers
  • Wednesday, March 23, 2005 - Cliff Zou, Modeling, Early Detection, and Mitigation of Internet Worm Attacks
  • Wednesday, March 16, 2005 - Brian Demsky, Data Structure Repair
  • Monday, March 14, 2005 - Kim Hazelwood, Managing Bounded Code Caches in Dynamic Binary Optimizers
  • Monday, March 07, 2005 - Ying Lu, Towards Self-Managing Computing Systems: Augmented Control Theory Approaches
  • Wednesday, March 02, 2005 - Westley Weimer, Exceptional Situations and Program Reliability
  • Wednesday, February 16, 2005 - Chenxi Wang, The Coral Project: Defending against large-scale attacks on the Internet
  • Monday, February 14, 2005 - Doina Caragea, Learning classifiers from distributed and semantically heterogeneous data sources
  • Wednesday, February 09, 2005 - Wei Le, Specification squeezing: extending the reach of bounded exhaustive test input generation
  • Monday, February 07, 2005 - Bernhard Steffen, Behavioral Model Construction
  • Monday, January 17, 2005 - Hridesh Rajan, Improved Abstractions for Aspect-Oriented Software Development
  • Monday, January 10, 2005 - Yuanfang Cai, Modularity in Abstract Design: A Theory and Applications

  • Tuesday, December 20, 2005
    Radu Stoleru
    Department of Computer Science, University of Virginia
    Chair: Sang H. Son
    Advisor: John A. Stankovic
    Olsson 236D, 2:00 PM

    A Ph.D. Proposal

    A Flexible and Robust System for Node Localization in Wireless Sensor Networks

    ABSTRACT

    Wireless Sensor Network (WSN) systems have been used in many promising applications including military surveillance, habitat monitoring and wildlife tracking. While many middleware services to support these applications have been designed and implemented successfully, node localization - finding the position of a sensor node - remains one of the most difficult research challenges to be solved practically.

    In this dissertation proposal, I address several challenges that have been at the forefront of node localization research in WSNs: cost/accuracy trade-offs, reliance on simulation based evaluations, and flexibility of the localization system. I propose a novel WSN localization system that can achieve high accuracy, practicality, cost effectiveness and flexibility through the dynamic loading and execution of a set of localization schemes. These schemes will implement new algorithms that will exploit, among other things, the free-space optical communication with sensor nodes, the sensing channel of each sensor node, the knowledge about the deployment topology of the WSN and the proximity to the deployed sensor nodes. I propose multimodality as the building block for a robust and flexible localization system for WSNs.



    Tuesday, December 20, 2005
    Xiangyu Jin
    Department of Computer Science, University of Virginia
    Chair: Worthy N. Martin
    Advisor: James C. French
    Olsson 228E, 1:00 PM

    A Ph.D. Proposal

    Adaptive Relevance Feedback in Multimedia Retrieval

    ABSTRACT

    With the advent of digital cameras and I-pods, along with existing personal digital documents, large-scale multimedia document collections are becoming more prevalent. This is increasing the need for effective multimedia information retrieval (MMIR) applications to manage these collections. Existing MMIR systems usually provide low retrieval performance to an initial search and poor means for refining searches. This makes relevance feedback, a technique to refine a search via user interactions, a crucial component of such systems. However, although proven effective in text retrieval, existing relevance feedback approaches have not been as effective for MMIR systems.

    In this dissertation proposal, I review existing relevance feedback approaches and put them in a general framework to study. I analyze their intrinsic relations and the reason why they could fail for some queries. I propose to investigate adaptive techniques for relevance feedback in MMIR applications. The basic idea is to estimate during the sampling-judging process how the relevant documents distribute in the retrieval space so that sampling and refinement strategies can be adjusted dynamically. Thus retrieval performance can be improved. I also plan to build a general evaluation environment for relevance feedback techniques. It will enable me to conduct the investigations proposed in this research. The performance of relevance feedback algorithms will be studied in relation to the retrieval space, query difficulty, and evaluation methods. New knowledge regarding these relationships will be discovered.



    Thursday, December 15, 2005
    Kellie-Ann Smith
    University of Virginia
    Advisor: Jim French and Paul Reynolds
    Olsson 236D, 9:00 AM

    A Master's Project Presentation

    Nancy's Pantry: Assisting the Visually Impaired in Restaurant Meal Selection

    ABSTRACT

    Predicting user preferences is a challenge in a broad set of applications including web browsing, recommender systems and data retrieval. We address the challenge as it relates to visually impaired users accessing information on restaurant menus through audio delivery mechanisms. Just as knowledge of user preferences can be employed in webpage and data record access prediction, so knowledge of dish and food type preferences can be used to aid information delivery to the visually impaired when perusing restaurant menus.

    Although there have been advances in assistive technology, and there exist means for the visually impaired to have access to paper documents, these technologies have limitations. For certain documents like utility bills, financial statements, restaurant menus, there does exist the means to give the visually impaired access to them. Braille or prerecorded audio versions of these documents can sometimes be made available upon request. Magnifiers are also helpful to those with low vision. However these devices do not give the user a simple way to browse through the document and focus on the sections they are really interested in, as a sighted person would. Here this problem is addressed in the domain of restaurant menus. We present a device to help a user efficiently browse through a restaurant menu by restructuring the dishes on the menu according the user's preference for the dish.



    Monday, December 12, 2005
    Nishit Tewari
    Department of Computer Science, University of Virginia
    Advisor: Kevin Sullivan
    Attending Faculty: Barry Horowitz
    Nuclear Reactor facility conference room (top floor), 6:00 PM

    A Master's Project Presentation

    An Event Notification Service for Mobile Ad hoc Networks

    ABSTRACT

    A mobile ad-hoc network (MANET) is a network of mobile hosts connected by wireless links that self-organizes into a defined topological structure. The hosts are free to move randomly and organize themselves into an overlay network; thus, the network topology may change rapidly and unpredictably. HyperCast is an overlay network protocol that supports secure point-to-point and multicast communication in overlay networks. It integrates overlay nodes into networks in a decentralized manner. A problem with HyperCast with respect to development of distributed applications is that it requires programming in terms of socket abstractions which are at too low a level for architectural design. Event-based communication is well suited for the development of distributed applications over MANETs. It decouples the communication relationship between the different components and also decentralises the network control. We describe the architecture and implementation of an event-based middleware system that is implemented on and that uses fundamental mechanisms of the HyperCast overlay network protocol. The key contribution of our approach is that it provides an easy-to-use, self-organizing event-based middleware system for MANETs that can support secure many-to-many communication between participating entities. We demonstrate our work with the help of a prototype application involving event sources generating image streams as event instances to which interested observers can subscribe to be notified. We will also show how the underlying HyperCast system manages network partitions and merges disconnected subnetworks automatically when they come in range of each other to provide for robust notification behavior in the mobile ad hoc setting.



    Monday, December 12, 2005
    Tenghui Zhu
    Department of Computer Science, University of Virginia
    Advisor: David Luebke
    Attending Faculty: Greg Humphreys
    Olsson 228E, 3:00 PM

    A Master's Project Presentation

    GPU-Accelerated Render Cache

    ABSTRACT

    The Render Cache can assist a high quality renderer, such as a ray tracer, to achieve interactive frame rate by reusing cached 3D samples. These samples can be reprojected to the new frames when viewpoint changes. However, the original Render Cache imposes high computation overheads on the CPU, making rendering at higher resolutions very expensive. Therefore, it is important to improve the efficiency of Render Cache. Recently, commodity GPUs have become increasingly powerful and flexible. With highly parallelized vector computation units, the GPU is a good candidate to address the computational requirements of the Render Cache. In this work, we present a system that implements the Render Cache on the GPU. We describe how the GPU stores the data structure of Render Cache and performs the required computations, such as reprojection, updating and image generation. Utilizing new features available on high end GPUs, our accelerated Render Cache can run more than four times faster than a highly optimized CPU implementation. Moreover, the workload has shifted from CPU to GPU, allowing us to interact with a high quality renderer in higher resolution.



    Wednesday, December 07, 2005
    Brian Garback
    Department of Computer Science, University of Virginia
    Advisor: Alfred C. Weaver
    Attending Faculty: Aaron Bloomfield
    Olsson 236D, 11:00 AM

    A Master's Project Presentation

    XACML for RBAC and CaDABRA: Constrained Delegation and Attribute-Based Role Assignment

    ABSTRACT

    We describe a model for and implementation of an enterprise access control system that extends standard RBAC and XACML to implement CaDABRA, Constrained Delegation and Attribute-Based Role Assignment. Our motivation comes from an effort to support web-based, federated healthcare requirements for authorization, including remote-user authorization and permission delegation. Our authorization system effectively represents authorization policies, provides dynamic permission definition, attribute- based role assignment, and enforcement, and provides delegation with complete administrative control. Two conditions provide this control. As part of a permission to delegate, a delegation condition must be met by a delegator and a delegate assignment condition must be met by the delegate to have a delegated permission assigned. We have created a implementation of our model using XACML and web services. Timing measurements confirm that it is an efficient solution for web-based enterprise authorization.



    Tuesday, December 06, 2005
    Anant Mudambi
    Departmen of Computer Science, University of Virginia
    Chair: Marty A. Humphrey
    Advisor: Malathi Veeraraghavan
    Thornton Hall, C311, 9:00 AM

    A Master's Thesis Presentation

    A Transport Protocol for Dedicated End-to-End Circuits

    ABSTRACT

    E-science projects involving geographically distributed data sources, computing resources and scientists, have special networking requirements such as a steady throughput and deterministic behavior. The connectionless Internet model is not well-suited to meet such requirements. Connection-oriented networks that offer guaranteed-rate, dedicated circuits have been proposed to meet the high-end networking needs of distributed scientific research. In this work we describe the design and implementation of a transport protocol for such dedicated circuits.

    We present an initial user-space, UDP-based implementation called Fixed Rate Transport Protocol (FRTP). The constraints imposed by a user-space implementation led us to implement a lower-overhead kernel-space solution that we call Circuit-TCP (C-TCP). The key feature of C-TCP is to maintain a fixed sending rate, closely matched to the circuit rate, with the aim of achieving high circuit utilization. We implemented C-TCP by modifying the Linux TCP/IP stack. Experimental results on a wide-area circuit-switched testbed show that C-TCP is able to quickly utilize circuit bandwidth and sustain a high data transfer rate.



    Monday, December 05, 2005
    Nolan Goodnight
    University of Virginia
    Advisor: Greg Humphreys
    Attending Faculty: David Luebke
    Olsson 228E, 4:00 PM

    A Master's Project Presentation

    4D Compression and Relighting with High-Resolution Light Transport Matrices

    ABSTRACT

    Many realistic image synthesis techniques require the evaluation of complex, multi-dimensional integrals, and are therefore impractical for real-time rendering. Recent research has bridged the gap between image quality and rendering speed by precomputing light transport effects. These techniques precompute functions in the light transport integral, and reuse this data to render a scene under dynamic viewpoint and/or illumination. Using such precomputation methods, it is possible to render high-quality images in real-time, but there is the burden of significant storage and memory costs. In most cases, approximation techniques are used to compress the transport matrix and reduce storage requirements by orders of magnitude.

    This project presents a method for efficient compression and relighting with high-resolution, precomputed light transport matrices. We analyze the sampling rates of the image and the lighting, with a view to determine the proper sampling rate to reduce the size of light transport matrices. We accomplish this using a 4D wavelet transform, transforming the columns of the transport matrix, in addition to the 2D row transform used in previous work. We show that a standard 4D wavelet transform can actually inflate portions of the matrix, because high-frequency lights lead to high- frequency images that cannot easily be compressed. Therefore, we present an adaptive 4D wavelet transform that terminates at a level (image sampling rate) that avoids inflation and maximizes sparsity in the matrix data. Finally, we present an algorithm for fast relighting from adaptively compressed transport matrices. Combined with a GPU-based precomputation pipeline, this results in a system that performs up to 2x better than 2D compression techniques in terms of storage costs and rendering speed.



    Thursday, December 01, 2005
    Shubhendu S. Mukherjee
    Director, Intel's FACT Group
    MSE 125, 12:30 PM

    Architectural Vulnerability Factors (or, does a soft error matter?)

    ABSTRACT

    With each technology generation, we are experiencing an increased rate of cosmically-induced soft errors in our chips. We are starting to see a dark side to Moore's Law in which the increased functionality we get with our exponentially increasing number of transistors is being countered with a exponentially increasing soft error rate. This will take increasing effort and cost to cope with.

    A key aspect of estimating a processor's soft error rate is to compute the architectural vulnerability factor (AVF) of its constituent structures. We define a structure's (AVF) as the probability that a fault in that particular structure will result in an error in the final output of a program. A structure's error rate is the product of its raw error rate, as determined by process and circuit technology, and the AVF. Processor designers can use these AVF estimates to determine which structures need protection (e.g., structures with high AVF are likely to be protected).

    Computing AVFs of complex structures, such as the instruction queue or data translation buffer tag, can be quite involved. To guide such complex AVF calculation, we identify numerous cases, such as prefetches, dynamically dead code, and wrong-path instructions, in which a fault will not affect correct execution. Our simulations suggest that AVFs of different structures can vary from 3% to 35% or more, which provides insight into which structures are potential candidates for protection.

    Biography:

    Shubu Mukherjee is the Director of Intel's FACT group. The Fault Aware Computing Technology (FACT) group is involved with various aspects of modeling, measurement, detection, and correction techniques associated with silicon reliability problems. In Intel, he pioneered techniques to compute the AVF (Architectural Vulnerability Factor), which measures how many transient faults become user-visible errors. In the past, he worked for Digital Equipment Corporation for ten days and Compaq Computer Corporation for three years. In Compaq, he invented a soft error detection technique for Alpha processors called Redundant Multithreading. He was also one of the architects of the Alpha 21364 interconnection network. He received his B.Tech. from the Indian Institute of Technology, Kanpur and M.S. and PhD from the University of Wisconsin-Madison. He has received a number of outstanding achievement awards in the past few years. Dr. Mukherjee holds 8 patents, has filed over 30 other patents, and is a co- author on more than 35 computer architecture papers.



    Wednesday, November 30, 2005
    Lin Gu
    Department of Computer Science, University of Virginia
    Chair: Sang H. Son
    Advisor: John A. Stankovic
    Thornton C311, 9:30 AM

    A Ph.D. Proposal

    Virtual Sensor Networks

    ABSTRACT

    Wireless sensor networks (WSNs) represent a promising technology with a wide spectrum of applications. However, the harsh resource constraints of WSN platforms lead many WSN designers to choose a ``thin'' operating system with very few services. Such OS's provide programmers a programming abstraction that does not hide the hardware details in resource constraints. On the other hand, a WSN application needs to handle much more issues than traditional embedded systems, due to its large scale, usually outdoor deployment, and high dynamics in network topology and link quality. Such a gap between the programming abstraction and system complexity makes it very difficult and costly to develop a large-scale WSN system.

    I propose to virtualize WSNs to be a controllable and easy-to-program system with semantics that application programmers can easily understand and use. Such a virtualization is performed in the OS kernel and compiler, thus giving maximum flexibility to the hardware designers and application programmers. I have designed a new OS kernel, t-kernel, that supports OS protection, virtual memory, and preemptive scheduling on highly resource constrained platforms without hardware support for privileged execution, memory address translation, or write-friendly external storage. A prototype has been implemented on Mica2 Motes with only 4K data RAM. I will investigate to evaluate the new kernel with real-world applications and explore new programming support that is enabled by t-kernel. Such programming support includes aspect-oriented programming, and distributed debugging interface that models a network as a state machine. I expect to make steady progress in the optimization of t-kernel and the extension of programming support so that they can significantly lower the development cost, enhance the capability, and promote the reliability of WSN systems.



    Wednesday, November 16, 2005
    Manuvir Das
    Center for Software Excellence
    Microsoft Corporation

    OLSSON 009, 3:30 PM

    Software Excellence via Program Analysis at Microsoft

    ABSTRACT

    The Windows division of Microsoft Corporation is in the midst of a massive effort to improve the security and reliability of the next release of the product - Windows Vista. In this talk, I will explain how the Center for Software Excellence at Microsoft has used program analysis technology to build the tools that enable this effort. Along the way, I will cover the current Windows engineering process and the role of the tools in the process, the core program analysis techniques we have invented and used in the tools, business and environment issues that govern the engineering process, and research directions suggested by our experience so far.

    Biography:

    Manuvir Das leads the Program Analysis research group in the Center for Software Excellence at Microsoft Corporation, and is an affiliate faculty member at the University of Washington. His research interests are in inventing and applying techniques from Programming Languages, Compilers, and Systems to the software engineering process. Manuvir holds a bachelor's degree in Computer Science from IIT Bombay, and a PhD in Computer Science from the University of Wisconsin-Madison.

    Refreshments will be served in the Lounge (Room 224) at 4:30 p.m.



    Wednesday, November 16, 2005
    Ankit Malhotra
    Departmen of Computer Science, University of Virginia
    Advisor: Gabriel Robins
    Attending Faculty: Anindya Dutta
    Olsson 236D, 1:00 AM

    A Master's Project Presentation

    Computational Infrastructure for High Throughput RNAi screening experiments

    ABSTRACT

    RNA interference (RNAi) is a recently discovered functional tool. This is a phenomenon where RNA introduced to a cell ultimately causes the degradation of the complementary cellular mRNA, and leads to the knockdown of gene activity. *Tar*geted *Co*mparitive *R*NAi (TARCOR) Screens are high throughput RNAi screens that produce large, multi dimensional expression data. However due to the biological and technical variances, there exists a lot of noise in the data and it is essential that the data be passed through various filters to extract reproducible data. The goal of the project was to put in place a computational infrastructure around this novel technique that shall take care of all aspects associated with the TARCOR assay including, handling and processing of data, putting in analysis pipelines and other important details.



    Friday, October 28, 2005
    Vincent W. Freeh
    North Carolina State University
    OLSSON 009, 3:30 PM

    High-performance, power-aware computing

    ABSTRACT

    There is a performance-at-all-costs mentality at most of the nation's supercomputing centers that has resulted in significant and growing energy use. This unchecked consumption costs the government a considerable amount of money and wastes natural resources. Moreover, energy consumption and the resultant heat dissipation are becoming important performance-limiting factors that we believe will eventually come to bear on high-performance computing users. The goal of our research is to consume less energy (generating less heat) with no more than a modest performance penalty and to do so without burdening computational scientists.

    This talk first discusses the energy consumption and execution time of applications from a standard benchmark suite (NAS) on a power-scalable cluster. Our results show that many standard scientific applications executed on a such cluster can save energy by reducing the processor frequency and voltage without a significant increase in time.

    Additionally, this talk presents two techniques for dynamically controlling power consumption and increasing the energy efficiency of application without undue performance penalties. One technique reduces CPU performance in phases that are not CPU-bound. The other technique reduces the CPU performance on nodes that are on the critical path. In both these situations, the application performance is not heavily dependent on the CPU performance, thus the resultant energy savings comes with little time increase.

    Biography:

    Vincent W. Freeh is an assistant professor of computer science at North Carolina State University. He received his Ph.D. from the University of Arizona. His research focus is high-performance system software, with concentrations in filesystems, parallel and distributed systems, and power-aware computing. Prof. Freeh received an NSF CAREER Award and an IBM Faculty Development Award. He was a captain in the US Army Corps of Engineers before entering graduate school for his MS. He worked at IBM in the Storage System Division until he returned to school to earn his PhD. Prof. Freeh was on the faculty at the University of Notre Dame prior to coming to NCSU. He lives in Holly Springs, NC with his wife, four children, and dog.

    Refreshments will be served in the Lounge (Room 224) at 4:30 p.m.



    Friday, October 21, 2005
    Ajay Kulhari
    Computer Science Department, University of Virginia
    Advisor: Tarek F. Abdelzaher
    Attending Faculty: Sang H. Son
    Olsson 228E, 10:00 AM

    A Master's Project Presentation

    RT-Transport: A Real-Time Transport Protocol for Sensor Networks

    ABSTRACT

    The promising use of sensor networks in multiple application domains motivates the development of communication protocols and interfaces that provide the equivalent of a UNIX socket layer to network applications. Towards that end, we present RT-Transport; a real-time transport service for sensor networks that incorporates a congestion control mechanism designed to enforce bounded-latency communication. Unlike congestion control in TCP, which is achieved by throttling the source, the proposed congestion control mechanism utilizes adaptive aggregation. In addition to meeting time constraints, a new design criterion that arises in this context is fairness with respect to the degree of aggregation across data collected from different locales. Adaptive mechanisms are incorporated to control the degree of aggregation such that it is uniform regardless of path length and node location. We present the design and implementation of the protocol and evaluate it on an experimental wireless sensor network testbed based on Crossbow XSMs (eXtreme Scalable Motes) nodes. Results show the efficacy of RT-Transport in enforcing both delay requirements and fairness of aggregation.



    Tuesday, October 18, 2005
    Marc Levoy
    Stanford University
    MEC 205, 3:30 PM

    Light field photography and videography

    ABSTRACT

    The light field is a 4D representation of radiance as a function of position and direction in space. In computer graphics, light fields have been used to fly through scenes without the use of geometric models. In this talk, I explore three ways to capture and use light fields that fall outside this paradigm. Specifically, I describe:

    1. A new photographic technique called dual photography, which exploits Helmholtz reciprocity to interchange the lights and cameras in a scene. In its simplest form, the technique allows us to take photographs using a projector and a photocell. Replacing the photocell with a camera or an array of cameras produces a 4D or 6D dataset, with applications to relighting and the measurement of appearance.

    2. A compact handheld camera capable of capturing a light field in a single exposure. The main idea is to insert a microlens array between the sensor and main lens. By capturing directional as well as spatial information about the light entering the camera, we can refocus a photograph *after* it is taken, and we can move the viewpoint slightly.

    3. New applications for the Stanford multi-camera array. In past work, we have configured our array to generate video at 3000 frames per second and to simulate a camera with an 8-foot aperture - allowing us to see through foliage and crowds. Recently, we have configured the array to simulate a 30-megapixel tiled video camera with independent exposure metering in each tile. This lets us record dynamic environments with unprecedented resolution and dynamic range.

    Biography:

    Marc Levoy is a Professor of Computer Science and (jointly) Electrical Engineering at Stanford University. He received a Bachelor's and Master's in Architecture from Cornell University in 1976 and 1978, and a PhD in Computer Science from the University of North Carolina at Chapel Hill in 1989. In the 1970's Levoy worked on computer animation, developing an early computer-assisted cartoon animation system. This system was used by Hanna-Barbera Productions from 1983 until 1996 to produce The Flintstones, Scooby Doo, and other shows. In the 1980's Levoy worked on volume rendering, a family of techniques for displaying sampled three-dimensional functions, for example computed tomography (CT) or magnetic resonance (MR) data. In the 1990's he worked on technology and algorithms for digitizing three-dimensional objects. This led to the Digital Michelangelo Project, in which he and a team of researchers spent a year in Italy digitizing the statues of Michelangelo using laser scanners. His current interests include light field sensing and display, computational imaging, digital photography, and applications of computer graphics in art history, preservation, restoration, and archaeology. Awards: Charles Goodwin Sands Medal for best undergraduate thesis (1976), National Science Foundation Presidential Young Investigator (1991), ACM SIGGRAPH Computer Graphics Achievement Award (1996).

    Refreshments will be served in the Lounge (Room 224) at 4:30 p.m. immediately after the talk.



    Thursday, September 29, 2005
    Ben Zorn
    Microsoft Research
    MEC 205, 3:00 PM

    Execution Environments for Building Dependable Systems

    ABSTRACT

    Managed Runtime Environments (MREs) (aka virtual execution environments or simply runtime systems) have evolved in functionality and complexity for over 40 years. MREs, such as the JVM and CLI, have absorbed functionality once only available from the operating system, and at the same time MREs support diverse and highly dynamic application configurations. While current MREs are clearly effective for many applications, opportunities remain to improve their design and broaden their applicability. In my talk, I focus on current issues with runtime systems and consider where hardware and software trends are likely to take these systems in the future. I consider MREs from the perspectives of performance, reliability, and ease of use, drawing on published experiences from both the CLI and Java communities. These experiences suggest important design directions for future MREs, including ways to improve support for modularity, error handling, concurrency, and componentization. One of the important future challenges for MREs is to demonstrate that they are up to the task of implementing the lowest-level system software, a domain where they are needed. The Bartok and Singularity projects, at Microsoft Research, are investigating this challenging problem.

    Biography:

    Ben Zorn is a Senior Researcher leading the Software Design and Implementation Group in Microsoft Research. After receiving a PhD in Computer Science from UC Berkeley in 1989, he served eight years on the Computer Science faculty at the University of Colorado in Boulder, receiving tenure and being promoted to Associate Professor in 1996. He left the University of Colorado in 1998 to become a Senior Researcher at Microsoft Research, where he currently works. Dr. Zorn's research interests include programming language design and implementation and performance measurement and analysis. He also serves as an Associate Editor of the ACM journal Transactions on Programming Languages and Systems and the ACM journal Transactions on Architecture and Code Optimization. For more information, visit his web page at: http://research.microsoft.com/~zorn/

    Refreshments will be served in the Lounge (Room 224) at 2:30 p.m.



    Tuesday, September 13, 2005
    Hector Garcia-Molina
    Stanford University
    MEC 205, 3:30 PM

    Generic Entity Resolution

    ABSTRACT

    Entity resolution (ER) is a problem that arises in many information integration scenarios: We have two or more sources containing records on the same set of real-world entities (e.g., customers). However, there are no unique identifiers that tell us what records from one source correspond to those in the other sources. Furthermore, the records representing the same entity may have differing information, e.g., one record may have the address misspelled, another record may be missing some fields. An ER algorithm attempts to identify the matching records from multiple sources (i.e., those corresponding to the same real- world entity), and merges the matching records as best it can.

    In this talk I will describe a "generic" ER approach where the functions for comparing and merging records are black-boxes, invoked on pairs of records. I will describe a set of important properties that should be satisfied by the black-box functions to enable efficient and deterministic ER algorithms, and I will present an algorithm, Swoosh, that significantly reduces the calls to these functions. In addition, I will also discuss how ER can be preformed when "confidences" are associated with the input records and with the match and merge functions.

    Refreshments will be served in the Lounge (Room 224) at 3:00 p.m.



    Thursday, September 08, 2005
    Lecia Barker
    Director, ATLAS Evaluation & Research
    University of Colorado, Bolder
    Rodman Room, Thornton Hall, 3:30 PM

    Revealing Behaviors that Influence Learning Environment: A Qualitative Exploration of Computer Science Classrooms

    ABSTRACT

    As part of an NSF-funded IT Workforce grant, the authors conducted ethnographic research to provide deep understanding of the learning environment of computer science classrooms. Categories emerging from data analysis included 1) impersonal environment and guarded behavior; and 2) the creation and maintenance of informal hierarchy resulting in competitive behaviors. These communication patterns lead to a defensive climate, characterized by competitiveness rather cooperation, judgments about others, superiority, and neutrality rather than empathy. The authors identify particular and recognizable types of discourse, which, when prevalent in a classroom, can preclude the development of a collaborative and supportive learning environment.

    Panel at SIGCSE: Contrasting women's experiences in computer science at different institutions http://portal.acm.org/citation.cfm?id=1047344.1047379 Position statement: Lecia Barker: One long-standing explanation for the low participation of women in the sciences is the social and pedagogical climate of the classroom. In our research at the University of Colorado, however, we found few of the overtly anti-woman characteristics of the “chilly climate” first described in 1982 by Hall and Sandler. Nevertheless, we found that classroom climate in introductory classes was difficult and inhospitable for both men and women. Unfortunately, however, the characteristics leading to the “defensive climate” more acutely affect women than they do men, chipping away at their confidence and motivation because women enter computer science with less experience and coursework than men, must overcome a general societal belief that computing is in the male domain (thus making their presence a violation of an unspoken norm), and because they are so few in number, feel both isolated and conspicuous.

    Our observations showed infrequent interpersonal interaction among students and professors, inexperienced students left behind by the fast pace, an unusually low frequency of questions or helpseeking, an environment where making mistakes was not allowed, and unchecked bids for attention and status among a few outspoken students. In interviews with 51 students, students said they often wanted to compare their performance with that of others, yet the individual nature of assignments made it impossible to know whether one was performing well or poorly.

    Students also perceived that one needed prior knowledge to succeed, so that in reality, the introductory course was not for beginners. Less experienced students interviewed felt intimidated by the outspoken students, and feared asking questions because they would slow down the class or expose their lack of knowledge. In combination with other changes (e.g., making assignments more concrete and palatable), changing the classroom climate to remove several of these characteristics could go a long way toward increasing the participation of women in computing.

    Biography:

    Lecia Barker is the head of the Evaluation and Research Group of the Alliance for Technology, Learning, and Society at the University of Colorado and is a senior research scientist for the National Center for Women and Information Technology. Barker studies formal and informal education in information technology, focusing on efforts to make computing more inclusive (gender and race/ethnicity). Her qualitative research on classroom communication makes visible behaviors that can lead to a "defensive climate" and how this can have gender-differentiated implications for students. She holds a PhD in communication from the University of Colorado, Boulder, an MBA in marketing from San Diego State University, and a BA in Spanish, Linguistics, and Portuguese from the University of Iowa.



    Friday, August 26, 2005
    Michele Co
    Department of Computer Science, University of Virginia
    Chair: Jack W. Davidson
    Advisor: Kevin Skadron
    Olsson 236D, 3:30 PM

    A Ph.D. Proposal

    Designing Energy Efficient Fetch Engines

    ABSTRACT

    Understanding processor design space tradeoffs and architectural requirements, as well as having metrics with which to evaluate them are key to processor design. A processor's fetch engine has been shown to consume up to 27% of overall processor power and its performance can dramatically affect overall processor energy-efficiency. Therefore, it is important to design an energy-efficient fetch engine. Previous studies have evaluated the energy-efficiency of limited segments of the fetch engine design space, but no thorough or systematic evaluation to achieve broader insights has been performed. Many of these studies do not consider additional factors such as the effect of increasing leakage-energy for future, smaller technologies, or the effect of increasing access latency due to higher frequency clocks. Both may have a major effect on the value of new designs.

    This proposal outlines a plan to systematically and more thoroughly evaluate and understand the tradeoffs within the fetch engine design space. This work proposes to use the insights gained from the design space study to improve the energy-efficiency of existing fetch engine designs. I also propose to develop new metrics to improve the designers' understanding of fetch engine energy-efficiency design tradeoffs and to design a proof-of- concept adaptable, energy-efficient fetch engine design which uses these metrics.



    Friday, August 12, 2005
    M. Anthony Aiello
    Department of Computer Science, University of Virginia
    Advisor: John C. Knight
    Attending Faculty: Ellen Bass
    Olsson 236D, 10:00 AM

    A Master's Project Presentation

    ASPEN: A Framework for Checking Aircraft Digital System Properties.

    ABSTRACT

    Both the "human-as-monitor" and "human-as-backup" models of human- automation interaction suffer from limitations of human attention: during the light cognitive workload associated with correct operation of the automation, demands on the operator for maintaining situational awareness are fairly low. In the event of a system or automation failure, however, the operator may be called upon to suddenly and decisively take control of the system. The difficulty associated with achieving this sudden switch from partial situational awareness to complete situational awareness is compounded by the fact that, in the moments leading up to a system or automation failure, the system often transitions from operation under normal conditions to operation under extreme, although still permissible, conditions. Furthermore, this transition occurs while the system is still under the control of the automation and is thus frequently unnoticed by the user.

    Existing systems designed to give the user advance warning of system failures or unsafe operation, such as aircraft flight-envelope protection systems and the Enhanced Ground Proximity Warning System, are integrated into the aircraft in an ad-hoc fashion: each system is treated alone and as a special case. This subsystem isolation prevents certain classes of errors from being detected, as each component may be in a correct state while the composition of subsystem states is erroneous.

    In this work, we propose ASPEN, an Aircraft System Protection Envelope and Notification system. ASPEN allows airframe manufacturers and avionics software designers to specify illegal system states using inputs from all components of the aircraft. Furthermore, using ASPEN, engineers can define "correct but unusual" states, which can serve as advance warning of impending failures. ASPEN thus allows for a greater range of system errors to be detected and at the same time reduces pilot workload by providing a warning that the aircraft may be operating in an exceptional, but allowable condition.



    Wednesday, August 10, 2005
    Joseph Calandrino
    Department of Computer Science, University of Virginia
    Advisor: Alfred Weaver
    Attending Faculty: David Evans
    Olsson 236D, 11:00 AM

    A Master's Project Presentation

    Private Resource Pairing

    ABSTRACT

    In privacy-critical scenarios, the need to protect information confidentiality can impede valid resource requests. Resource providers may refuse to even confirm possession of a resource to requestors that have not demonstrated a need to access the resource. Such a scenario would force requestors to first reveal their queries accompanied by justifications. As a request query alone may contain or imply confidential data, requestors need some assurance that a provider can satisfy a request before revelation of the request. If both entities refuse to compromise privacy, a reasonable request could go unfulfilled. Private resource pairing links resource providers and legitimate requestors while preserving privacy.

    This work explores private resource-pairing solutions under two models of participant behavior: honest but curious behavior and potentially malicious behavior. Several recent papers have explored the similar problem of allowing operators of two separate databases to establish common entries without revealing non-matching elements [Agrawal, et al., 2003; Li, et al., 2005]. This existing work can assist in solving the private resource-pairing problem. The unique constraints of the private pairing problem allow for a more efficient and robust solution, however. This talk will present the private resource-pairing problem, related work, a private pairing solution, performance analysis of the solution, and future research directions.



    Monday, August 01, 2005
    Michael Crane
    Departmen of Computer Science, University of Virginia
    Advisor: Jack W. Davidson
    Attending Faculty: John C. Knight
    Olsson 236D, 3:30 PM

    A Master's Project Presentation

    Using Calling Sequence Diversity to Defeat Return-to-libc Attacks

    ABSTRACT

    The traditional stack-smashing exploit takes advantage of a buffer overflow vulnerability to inject malicious code on to the stack and execute it. Several defenses have been proposed to prevent execution of injected code. However, a return-to-libc attack can bypass a non-executable stack by jumping to pre-existing library functions with arbitrary arguments.

    We have proposed the idea of calling sequence diversity to defeat return- to-libc attacks. This technique ensures that any call to a potentially malicious library function comes from a legitimate call in the program. A modified compiler is used to enforce a secure calling convention requiring a hidden parameter that will be checked by the called function. This hidden parameter is a unique key associated with the function. The attacker will not be able to jump to arbitrary functions without this key. Further security is provided using Strata, a software dynamic translation system. Strata dynamically generates keys and inserts them into the program, preventing users from determining key values through static analysis of the binary.



    Friday, July 29, 2005
    Hridesh Rajan
    Departmen of Computer Science, University of Virginia
    Chair: John C. Knight
    Advisor: Kevin J. Sullivan
    Olsson 236D, 3:00 PM

    A Ph.D. Defence

    Unifying Aspect- and Object-Oriented Program Design

    ABSTRACT

    The dominant family of aspect-oriented languages, namely the family of languages based on the AspectJ model, provides aspects as a new abstraction mechanism separate from classes. Aspects are promoted as means to modularize certain traditionally non-modularized concerns. The design decision to separate aspects and classes, however, reduces the conceptual integrity of the language model. The resulting language model is non-- orthogonal and asymmetric with respect to the key capabilities of aspects and classes. Furthermore, these asymmetries impair our ability to easily separate important classes of concerns namely, integration and higher-order concerns, and distorts our conceptual model of how to structure software systems with AOP.

    In this dissertation, I show that aspects as separate abstraction mechanism are not essential to aspect-oriented programming. Instead a new construct, quantified binding, similar to the event-handler binding in the implicit invocation style, is at the core of aspect-oriented programming. I present a language model in which aspects and classes are unified. Key technical contributions include: support for aspect instantiation under program control, instance-level advising, advising as a general alternative to object-oriented method invocation and overriding, and the provision of a separate join-point-method binding construct. The new language model is concomitantly simpler and more expressive. The simplification is manifested by the reduction of specialized constructs in favor of uniform orthogonal constructs. The expressiveness is manifested by the improvement in the modularization of integration and higher-order concerns.



    Thursday, July 28, 2005
    Leonid Bolotnyy
    Department of Computer Science
    Advisor: Gabriel Robins
    Attending Faculty: Paul Reynolds
    Olsson 228E, 1:00 PM

    A Master's Project Presentation

    Multi-Tag Radio Frequency Identification Systems

    ABSTRACT

    Radio Frequency Identification (RFID) is a promising technology that supports many useful applications (e.g., transportation toll payment, supply chain management, inventory tracking, library book checkout, and building access control). While RFID is expected to replace bar codes in the near future, high tag cost, detection issues, and privacy concerns still impede the wide deployment of this technology.

    In order to address some of these issues, we propose and analyze the effects of attaching more than one RFID tag to an object. We define different types of multi-tag systems and examine their benefits, both analytically and empirically. We also analyze the impact of multi-tags on existing tag singulation algorithms. We show how multi-tags can serve as security enhancers, and propose several new promising applications of multi-tags.



    Wednesday, July 27, 2005
    Marco Caccamo
    Department of Computer Science, University of Illinois at Urbana-Champaign
    OLSSON 009, 3:30 PM

    Implicit RT-QoS for Wireless Collaborative Real-Time Systems

    ABSTRACT

    With the miniaturization of computing, communication and sensor devices, distributed real-time systems consisting of teams of autonomous mobile units, are becoming increasingly attractive for a wide range of applications, from homeland security to environment monitoring (e.g., pollution detection).

    In critical applications (like surveillance and hazard detection), timeliness and robustness become critical issues in particular when the system is subject to dynamic workloads and node/network failures. In fact, unpredictable changes of the environment that a real-time team has to interact with, trigger different nodes' action causing dynamic workloads and/or transient losses of connectivity.

    Two innovative approaches, called "RI-EDF" and "Bandwidth Sharing" (BASH) will be presented, which have been developed to address the new challenges (i.e., temporal predictability, robustness, dynamic workloads) faced by wireless collaborative real-time systems. These approaches allow us to effectively and efficiently maximize network and CPU performance, while still providing real-time guarantee.

    Biography:

    Marco Caccamo is Assistant Professor of the Dept. of Computer Science at University of Illinois. He received a PhD in Computer Engineering from Scuola Superiore S.Anna in 2002. His research interests include real-time operating systems, real-time scheduling and resource management, wireless sensor networks, and quality of service control in next generation digital infrastructures.

    Refreshments will be served in the Lounge (Room 224) at 3:00 p.m.



    Friday, July 22, 2005
    Gregory Mattes
    Department of Computer Science, University of Virginia
    Advisor: Jorg Liebeherr
    Attending Faculty: Marty Humphrey
    Olsson 236D, 10:00 AM

    A Master's Project Presentation

    A Naming Service for Overlay Networks

    ABSTRACT

    Application-layer peer-to-peer overlay networks use logical addressing schemes to identify peers and to route messages. Examples of logical addresses for peers in an overlay networks include binary strings, coordinates in a multidimensional coordinate space, or randomly selected numerical identifiers. However, writing overlay network application programs with logical addresses can be cumbersome since they do not encode information to identify an application, service, user, or user group.

    We have created a naming service for overlay networks that decouples applications from logical addressing by allowing applications to bind a logical address to mnemonic names. The naming service is independent of any particular logical addressing scheme. The service neither interprets logical addresses nor imposes any structure on names. Names are linked to logical addresses in a database of name bindings that is distributed across all network peers. Name bindings are updated whenever a peer changes its logical address. The integrity and authenticity of name bindings is ensured by a mechanism that exchanges and verifies trust information among peers, without need for a trusted third party. Name bindings are disseminated among peers through queries that are sent by a peer that seeks to resolve a name (pull) or by broadcasting a name upon creation of a new name binding (push).

    This project explores the practicality of a peer-to-peer naming service in the HyperCast software system, and measures the performance in measurement experiments. The evaluation of the naming service measures the trade-offs between push and pull operations under static and dynamic network conditions while varying the distances used for each operation.



    Monday, July 11, 2005
    Ying Lu
    Department of Computer Science, University of Virginia
    Chair: John A. Stankovic
    Advisor: Tarek F. Abdelzaher
    Olsson 236D, 2:00 PM

    A Ph.D. Defence

    Towards Self-Managing Computing Systems: An Augmented Control Theory Approach

    ABSTRACT

    Computing systems are becoming increasingly large and complex making their performance less predictable and their management more challenging and costly. To achieve performance assurances while cutting management cost, computing systems are needed that can continually manage their performance in the face of changing computing demands and environmental conditions; an architectural paradigm called "Autonomic Computing". Towards building autonomic computing systems, we develop a new analytic foundation for automatic performance regulation in software services based on feedback control theory. A novel performance control architecture (PCA) is proposed as a general framework for providing robust performance assurance in open real-time computing systems where neither a priori system knowledge nor fine system models are available.

    PCA features an adaptive architecture based on the integration of model- based feedforward control and self-adaptive feedback control. By utilizing the complementary natures of feedforward and feedback control, PCA combines the advantages of both and provides practical solutions to performance assurance. Unlike heuristic-based adaptive mechanisms, PCA is guided by well-established theories. Another highlight of PCA lies in the methodology for building self-tuning performance regulators. Traditional performance control mechanisms often require knowledge of platform capacity and resource demand, which calls for performance measurements and profiling upon platform upgrades, failures, or new installations. To automate the process through self-learning and self-adjusting, PCA employs an approach based on adaptive control theory, where the performance regulator automatically builds a system model and maintains the system performance at a satisfactory level.

    In the dissertation, we present our performance control framework and the methodology for applying it to current software service architectures. Specifically, we show how to build the right sensors and monitors, use the available software performance actuators, map performance regulation to a feedback control problem, model the computing system and design control modules to achieve performance specifications. Following this methodology, we successfully provide robust Web performance control under significant load and resource uncertainties. Two applications are illustrated. They are robust delay control in Web server systems and robust hit rate control in a Squid proxy cache. They demonstrate the success of the control theory approach in providing a flexible range of performance assurances in an adaptive manner at minimum cost.



    Monday, July 11, 2005
    Ji-Wook Jo
    University of Virginia
    Advisor: Sang H. Son
    Attending Faculty: John A. Stankovic
    Olsson 228E, 10:00 AM

    A Master's Project Presentation

    An Area Event Data Service in Wireless Sensor Networks

    ABSTRACT

    Efficiently using wireless sensor networks to detect and report on large scale area events that persist for a long time is difficult. In this presentation, we develop a solution for efficient data processing of such area event occurrences. Notable characteristics of our solution are the separation of event description from data/query processing and the dynamic formation of a tree overlay. There are several advantages of our approach. First, it provides a clean design by separating two issues that have different functionality. Second, we provide improvements in energy consumption, response time and report accuracy. We show these results with extensive simulations that investigate different terrain sizes, network densities, area event sizes and query durations. Through the simulation studies we also show that our scheme outperforms the state of art solution called TAG.



    Friday, July 08, 2005
    Richard P. Martin
    Division of Computer and Information Sciences, Rutgers Univesity
    Olsson 228E, 11:00 AM

    Bayesian Positioning in Wireless Networks

    ABSTRACT

    The incorporation of radios in a wide range of devices presents the opportunity to position them in physical space. In this talk, I will present our work on a family of Bayesian hierarchical models for realizing generic location estimation in wireless networks. Our models achieve accuracy that is similar to other approaches, yet by harnessing prior knowledge, our models can drastically reduce, and in some cases even eliminate, the need for training data. A key advantage of our models is that they can encompass any prior knowledge in a unified framework. I will show how to scale the models to incorporate distance to signal strength, hardware variance, corridor effects, and angle-of- arrival information. I will also present recent results showing the applicability of our models for both 802.11 and 802.15.4 networks.

    Biography:

    Dr. Richard Martin is an assistant professor at Rutgers University. His current research interests include localization in wireless sensor networks and human factors in dependable computing. He co-leads the PANIC (Pervasive Available No-futz Internet Computing) Laboratory and is a member of the Rutgers WINLAB (Wireless Information Network Laboratory). His recent awards include the best paper award at the 2004 IEEE Conference on Sensor and Ad Hoc Communication Networks as well as a CAREER award from the National Science Foundation. Dr. Martin has served as an investigator on grants from the Defense Advanced Research Projects Agency, the National Science Foundation, and IBM. He received a B.A. from Rutgers University and an, M.S. and Ph.D. in computer science the University of California at Berkeley.

    Refreshments will be served in the Lounge (Room 224) at 10:30 a.m.



    Thursday, July 07, 2005
    Ronghua Zhang
    Department of Computer Science, University of Virginia
    Chair: Sang H. Son
    Advisor: John A. Stankovic, Tarek F. Abdelzaher
    Olsson 236D, 10:00 AM

    A Ph.D. Defence

    QoS Support for Legacy Applications

    ABSTRACT

    This thesis addresses several challenges encountered when augmenting legacy applications with adaptive differentiated service capabilities to support multiple classes of users of different importance. First, we present a novel architecture to build systems capable of customized performance guarantees using unmodified legacy applications. This architecture does not demand changes to legacy software, thus significantly reducing development cost. The strength and generality of the proposed solutions are demonstrated by their successful application to multiple popular server systems including web, mail, and FTP servers. For I/O intensive applications, such as databases, we study the problem of non-intrusively throttling background load (e.g., backup utilities) in order to provide performance guarantees for foreground transactions. The efficacy and robustness of the proposed I/O-centric service differentiation mechanism are tested using the commercial database server DB2 under various conditions. We then examine the impact of adaptation (i.e., feedback) on the quality of service differentiation. An adverse interaction is observed and resolved between feedback loops and a resource scheduler. Finally, we present a toolkit designed to assist developers in implementing, re-using, and experimenting with adaptive service differentiation algorithms based on formal feedback control theory. It simplifies the implementation of components, introduces new concepts to enable re-use of components and control structures, isolates developers from control knowledge as much as possible, and offers a new way to implement control loops that eases the collaboration between developers and control engineers.



    Friday, June 17, 2005
    John Tran

    Advisor: David Luekbe
    Attending Faculty: David Brogan
    Olsson 228E, 11:00 AM

    A Master's Project Presentation

    Simulation of Excitable Media Wave Propagation on Arbitrary 3D Surfaces

    ABSTRACT

    Excitable media are characterized by their ability to propagate signals through a medium without damping. One example of excitable media which has motivated our work is cardiac tissue. The heart requires the organized passage of electrical signals to function correctly. When something goes wrong and signals become blocked or delayed, various heart disorders can develop, with effects ranging from shortness of breath to more fatal disorders such as strokes.

    Our goal is to develop a framework to study cardiac electrical activity. In order to do this, we have developed an end-to-end system for collecting patient geometry and simulating arbitrary cell models on the surface of this geometry. Until recently, all heart simulations were done in 2D regular grids or 3D voxel grids. However, the structure of atrial geometry implies that the signals should be studied on a 3D surface, rather than on a sheet or in a volume. In addition, the nature of heart disorders requires the need for some level of interaction in order to study the dynamics of the propagation. In this presentation, we will demonstrate our interactive system for an arbitrary 3D triangle mesh with a second generation cellular automata model developed for general excitable media, and discuss future work we plan with this system.



    Thursday, June 16, 2005
    Rui Wang
    University of Virginia
    Chair: Greg Humphreys
    Advisor: David Luebke
    Olsson 228E, 10:30 AM

    A Ph.D. Proposal

    An End-to-end Solution for Interactive Rendering with Complex Lighting models

    ABSTRACT

    Realistic image synthesis at interactive rates continues to present a great challenge in computer graphics. Achieving the desired level of realism requires a rendering system to capture natural lighting and employ complex lighting models. At different levels of complexity, a lighting model should include realistic and complex surface reflectance, intricate hard and soft shadows, indirect illumination (interreflections), and subsurface scattering (translucency). Such sophisticated lighting models have been accurately simulated using techniques such as Monte Carlo ray tracing or photon mapping. However, these techniques are very computationally expensive and will not soon be available for real-time applications.

    I propose to design and implement an end-to-end interactive system for realistic rendering of objects that captures shadows, complex surface reflectance, interreflections and translucency in natural lighting environments. The system is based on precomputation techniques and will be built on top of four research aspects: 1) Acquisition of realistic materials. Unlike the commonly employed immobile devices for surface reflectance measurement, my goal is to develop a less sophisticated but easy to carry device, desirable for on-site measurement. 2) Efficient precomputation algorithms. I will develop rigorous analysis of different lighting models and various approximation methods to allow for efficient precomputation. 3) Data compression and representation. I plan to investigate techniques that exploit data coherence to reduce storage and transfer requirements, which are major concerns with precomputation techniques. 4) Fast rendering algorithms using recent advances in programmable graphics hardware. Finally, I will demonstrate the system in several practical applications such as interactive lighting design, visualization of global illumination solutions, and virtual museum exhibition.



    Friday, May 27, 2005
    Robert G. Bartholet
    Departmen of Computer Science, University of Virginia
    Chair: Worthy Martin
    Advisor: Paul F. Reynolds
    Thornton Hall C311, 10:00 AM

    A Ph.D. Proposal

    A Practical Process for Simulation Component Reuse

    ABSTRACT

    Constructing federations of simulations from existing simulation components is challenging, much as component based software engineering has been. In the simulation community part of the challenge arises from the frequently recurring assumption that components are immutable, or at worst can be adapted in short order. Simulation component selection, taking the costs (and benefits) of component adaptation into account, has not been studied. Neither has simulation component selection taking the benefits of simulation specific properties into account. Related problems in the software engineering community have been studied in more depth, but not with a focus on exploiting both simulation specific properties and the benefits of adaptation.

    My research addresses the simulation component selection challenge. I propose an approach I call Applied Simulation Component Reuse (ASCR), a practical federation construction process that leverages semi-automated adaptation and simulation specific characteristics in selecting the best set of components for satisfying requirements. Critical to leveraging adaptation is defining the utility or cost of selecting a component given the effort required to adapt the component. I have demonstrated that the computational complexity of considering utility values in optimal component selection is NP-complete. I will investigate efficient algorithms for near-optimal solutions. Also critical to addressing the component selection problem is development of a representative, analyzable model of the process. I have begun to develop such a model. My preliminary investigations into the exploitation of simulation specific characteristics for the component selection problem also look promising. In my proposed work I will extend my preliminary results, ultimately conducting an investigation of the important questions relating to applied simulation component selection. I expect to make the process of simulation component selection significantly better than the largely ad hoc practices in common use today.



    Thursday, May 26, 2005
    Kathi Fisler
    Worcester Polytechnic Institute
    OLSSON 009, 10:00 AM

    Modular Verification of Feature-Rich Software

    ABSTRACT

    Aspect-oriented programming (AOP) has become an increasingly important programming paradigm. AOP is one of a family of means for expressing abstractions that cut across the program's dominant modularity; these techniques enable the construction of software by composing features. Despite their importance, feature-based programming methods lack supporting computer-aided verification techniques, which are necessary for increasing reliability and developing confidence in systems.

    This talk presents a technique for verifying feature-based programs (expressed as state machines). By analogy with modular compilation, we support modular verification, to both enable independent development and to reduce the computational cost of verification. We present the analysis and discuss subtleties that arose as we applied our prototype verifiers to real case studies.

    (Joint work with Shriram Krishnamurthi [Brown].)

    Refreshments will be served in the Lounge (Room 224) at 9:30 a.m.



    Wednesday, May 25, 2005
    Shriram Krishnamurthi
    Brown University
    OLSSON 009, 3:30 PM

    Programming and Verifying the Interactive Web

    ABSTRACT

    Server-side Web applications have grown increasingly common, sometimes even replacing brick and mortar as the principal interface of corporations. Correspondingly, Web browsers grow ever more powerful, empowering users to attach bookmarks, switch between pages, clone windows, and so forth. As a result, Web interactions are not straight-line dialogs but complex nets of interaction steps.

    In practice, programmers are unaware of or are unable to handle these nets of interaction, making the Web interfaces of even major organizations buggy and thus unreliable. Even when programmers do address these constraints, the resulting programs have a seemingly mangled structure, making them difficult to develop and hard to maintain.

    In this talk, I will describe these interactions and then show how programming language ideas can shed light on the resulting problems and present solutions at various levels. I will also describe some challenges these programs pose to computer-aided verification, and outline solutions to these problems.

    Refreshments will be served in the Lounge (Room 224) at 3:00 p.m.



    Wednesday, May 25, 2005
    Julie Parent
    Departmen of Computer Science, University of Virginia
    Advisor: Jack W. Davidson
    Attending Faculty: Greg Humphreys
    Olsson 228E, 2:00 PM

    A Master's Project Presentation

    An Exploration of Combinatorial Optimization Techniques for Optimization Phase Ordering

    ABSTRACT

    The order in which optimizations are applied within a compiler greatly affects the quality of the code produced. However, there is no single ordering of optimizations that achieves optimal results for every function, because the effectiveness of a single optimization phase is dependent on the code being compiled. This work implements a framework for investigating different combinatorial optimization techniques for optimization phase sequence selection in a compiler. In this work, I compare simulated annealing, a basic hillclimber, and sequence heuristics, each of varying complexity, to determine if any are better suited for solving the phase ordering problem than an already known genetic algorithm approach. The best results obtained used simulated annealing, resulting in an average reduction of code size over an iterative batch compiler by 21%. When all the techniques were run for the same number of function evaluations, simple hill climbing and sequence heuristics outperformed the more complicated genetic algorithm and simulated annealing techniques. This result implies that it is not necessary to use complex techniques to obtain good results for the phase ordering problem.



    Thursday, May 12, 2005
    Yuanyuan Song
    Department of Computer Science, University of Virginia
    Advisor: Kevin Sullivan
    Attending Faculty: Jorg Liebeherr
    Olsson 228E, 10:00 AM

    A Master's Project Presentation

    Join Point Interfaces: Information Hiding Modularity for Aspect-Oriented Program Design

    ABSTRACT

    Aspect-oriented programming (AOP) provides new mechanisms to modularize "crosscutting" concerns in software systems. The prevailing approach of aspect-oriented design is based on the concept of "obliviousness": the designer of base code can be completely oblivious to the presence and needs of aspects. The idea is that one can write ordinary object-oriented code to implement base concern, as usual, and then extend it with aspects that implement crosscutting concerns. In recent work with Sullivan, Cai and Tewari at the University of Virginia and Griswold and Shonle at the University of California San Diego, we showed that oblivious approach creates complex, arbitrary, and unstable dependences of aspect code on base code, with expected costs in difficulty of program understanding, life cycle development costs, and complexities in software evolution. To address these problems while preserving the key elements of AOP, we introduced the concept of crosscutting join point interfaces (JPI's). JPI's are information hiding abstract interfaces that decouple base and aspect code design. A JPI obliges the base code designer to design code in a way that exposes specified execution phenomena through specified join points, and licenses aspect code designers to assume that the given join point behaviors are provided by the base code. JPI's differ from traditional API's in that their scopes are crosscutting (non-hierarchical) in general, and what they expose are not functions but points at which base code can be advised by aspects. Subsequent to our joint effort, I have continued to develop the concept of the JPI, including both syntactic and semantic aspects. In this talk, I will present an approach to specify JPI's with a combination of existing AO language constructs to specify the syntactic elements and natural language to specify semantics. I will also show that it's possible to use existing aspect-oriented language mechanisms to support limited static and dynamic checking to enforce JPI contracts. I will report on the application of these ideas in factoring crosscutting concerns in a refactoring of the HyperCast overlay network system. Finally I will compare the JPI's approach with related work. Overall, I will argue that JPI's support significantly improved modularity and abstraction in AOP as compared with the "oblivious approach," with expected benefits in program understandability, increased parallelism in development, and greater ease of program evolution.



    Thursday, May 12, 2005
    Mary Jane Irwin
    Department of Computer Science and Engineer, Pennsylvania State University
    THN E-16, 10:00 AM

    On-Line Power Aware Systems

    ABSTRACT

    Energy efficiency has joined the ranks of performance and area as a major computer design metric. This is due both to the explosive growth in mobile platforms that have battery-life and form-factor constraints and to the projected increase in power consumption and thermal dissipation of desktop and server systems that impacts their cooling and packaging costs as well as their reliability. For many machine rooms the cost of the energy to run the systems and the cost of the environment control equipment are significant budgetary issues. To quote Eric Schmidt, CEO of Google "What matters most to the computer designers at Google is not speed, but power - low power, because data centers can consume as much electricity as a city."

    After a brief review of the sources of energy consumption in electronic circuits, this talk will overview the underlying circuit fabric's support for designing power aware systems - fabric "knobs" such as supply voltage scaling and clock speed throttling, fabric "switches" such as supply voltage shut down, and fabric monitors such as performance counters and temperature sensors. Then several on-line (i.e., run-time) schemes for designing power aware systems using the fabrics switches and knobs will be presented. This will include adaptive microarchitecture optimizations, adaptive compilers, adaptive run-time systems, and even adaptive application approaches.

    Biography:

    Biography: Dr. Irwin is the A. Robert Noll Chair in Engineering in the Department of Computer Science and Engineering at Penn State University. Her research and teaching interests include computer architecture, embedded and mobile computing systems design, power aware design, and emerging computing technologies. Dr. Irwin received her Ph.D. degree in computer science from the University of Illinois in 1977 and an Honorary Doctorate from Chalmers University, Sweden, in 1997. She is an IEEE and ACM Fellow and was elected to the National Academy of Engineering in 2003.

    Dr. Irwin is currently serving as Co-Chair of ACM's Publications Board and as the Editor-in-Chief of ACM's Journal on Emerging Technologies in Computing Systems (JETC). In the past she has served as an elected member of the Computing Research Association's Board of Directors, IEEE Computer Society's Board of Governors, of ACM's Council, and as Vice President of ACM.

    Reception before the talk in THN E-316 at 9:30 a.m.



    Tuesday, May 10, 2005
    Binjia Jiao
    Department of Computer Science, University of Virginia
    Advisor: Sang H. Son
    Attending Faculty: John A. Stankovic
    Olsson 228E, 9:00 AM

    A Master's Project Presentation

    SNEDL: Sensor Network Event Description Language for Event Service Architecture

    ABSTRACT

    Most wireless sensor network (WSN) applications are event-based and their unique features demand a new paradigm for event services. We have been developing a framework for a generic event service middleware (GEM). GEM provides an integrated service package for WSN applications so that users can specify events accurately, export specified events to the network, and initiate in-mote middleware to provide multi-level event detection. A sensor network event description language (SNEDL), designed specifically for WSN events, is a part of the GEM architecture. Built upon Petri-Nets, SNEDL can also be used as an offline analysis tool. To make the sensor motes understand SNEDL specified events, GEM encodes events into a mote- understood format (called event DNA). GEM also contains an in-mote detection module to read DNAs for event recognition. When communication is necessary for higher level events, a detection module transfers a lightweight structure (called RNA) to support collaborative decisions.

    In this presentation, I will present SNEDL, which is a critical part of the GEM event service architecture. SNEDL is the first event description language specifically designed for wireless sensor network applications. Its properties fits the distributed, asynchronous and non-deterministic characteristics of sensor network events. SNEDL takes a hierarchical approach with flexible abstraction methods for differentiated specification purposes. In addition to being a description language, SNEDL can also be used as an analysis tool for studying event system properties by SNEDL simulation. SNEDL tool Java has been implemented using Java Eclipse.



    Thursday, May 05, 2005
    Xiang Yin
    Departmen of Computer Science, University of Virginia
    Advisor: John C. Knight
    Attending Faculty: David Evans
    Olsson 236D, 2:00 PM

    A Master's Project Presentation

    Echo: A Practical Approach to Formal Verification

    ABSTRACT

    Program correctness is crucial to safety-critical systems and formally verified implementations are desired. Traditional formal verification approaches follow the Floyd-Hoare style. They set up a direct compliance argument between the abstract formal specification and the concrete implementation, which involves proof of many verification conditions or theorems. The process of generating and proving verification conditions is an extremely skilled and time consuming task.

    In this project, we introduce a general verification approach that closely models the Floyd-Hoare pattern, yet tries to avoid the tedious direct compliance proof between the formal specification and the implementation. The approach moves the major proof step to a point between two abstract specification models.

    Our preliminary design takes PVS as our specification language and SPARK Ada as our implementation language. We first use a human guided translation to manually generate SPARK Ada code along with appropriate annotations from a PVS specification. And then we verify the annotations' compliance to the specification by mechanically translating them back into a PVS specification, and prove its equivalence with the original one. At the same time we rely on the existing SPARK toolset to verify the actual code against the SPARK annotations. The whole process is largely automatic or computer-aided.

    A case study has been conducted showing that this approach is feasible and practical.



    Thursday, May 05, 2005
    Jinlin Yang
    Department of Computer Science, University of Virginia
    Chair: Mary Lou Soffa
    Advisor: David Evans
    Olsson 228E, 9:00 AM

    A Ph.D. Proposal

    Automatic Inference and Effective Application of Temporal Specifications

    ABSTRACT

    The biggest hurdle of adopting verification tools is the non-availability of temporal specifications of the program. The goal of my research is to develop dynamic analysis techniques to automatically infer temporal specification of a program. In particular, I will generate execution traces of the program by running a set of test cases and then analyze the properties satisfied by traces using a set of predefined patterns. By enabling automatic inference of temporal specification, my approach will reduce the cost of developing and maintaining the software and increase the reliability of the software. To evaluate my approach, I am implementing my dynamic analysis techniques in a prototype tool called Terracotta. Initial results using Terracotta on some medium-size programs including an implementation of a file system and the handshake protocol in the OpenSSL implementation are encouraging, however, till now I have only used a small set of property patterns. My remaining work therefore is to, first, investigate new patterns for both temporal and data invariants, and second, extend my evaluation to include several other realistic size programs and use some model checkers to check the properties inferred about the program. My candidate testbeds include student assignments, implementation of network protocols, device drivers, file systems, libraries or APIs, and programs manipulating complex data structures. I also plan to investigate other possible uses of inferred temporal properties in the software development process such as aiding test input selection, debugging and program understanding.



    Thursday, April 28, 2005
    Jie Luo
    University of Virginia
    Advisor: W. N. Martin
    Attending Faculty: James C. French and David Germano
    Olsson 236D, 4:30 PM

    A Master's Project Presentation

    Limited Community Name Server System

    ABSTRACT

    Individual web sites of community with a strong interest in a given topic or set of topics often desire to build in explicit linkages to other related web sites so as to facilitate users being able to simultaneously browse and search through a whole family of web sites on a given subject. As a type of URI (Uniform Resource Identifier), URL (Uniform Resource Locator) has been dominating today's web, it is vastly accepted by most websites to achieve resource sharing by means of hyperlink. The problem with this naming and addressing convention is that the name is bounded by specific physical location where resource actually reside in, as a result, it can't guarantee linkage persistency. To remedy this problem, a location-independent naming schema, URN (Uniform Resource Name) has been introduced by researchers. We apply this resource naming scheme across limited community: each resource will be assigned a unique URN as an identifier within this community, a name resolution engine has been built to translate between URN and URL, with support from this engine, resource are referenced by using location- independent URN instead of "brittle" URL thus persistent linkage is achieved. Meta-data exchange are crucial to resource discovery, we adopt DCC (Dublin Core Code) as meta-data communication protocol. Under such an agreement, community members will be able to expose meta-data that has long resided in their databases. A URN- based search engine has been built to provide community members with a discovery mechanism for the persistent resources made available to the community.



    Friday, April 22, 2005
    Sudhanva Gurumurthi
    Pennsylvania State University
    Olsson 011, 3:30 PM

    Power Management of Enterprise Storage Systems

    ABSTRACT

    Data-centric services, such as transaction processing systems and search-engines sustain the needs of millions of users each day. These services rely heavily on the I/O subsystem for their data storage and processing requirements. Technological improvements in hard disk drive densities and data-rates have been key enablers in the realization of these storage systems. However, server storage systems consume a large amount of power, leading to higher running costs, increased stresses on the power supply, and detrimental environmental impacts. In my talk, I shall show that power management is a challenging problem for enterprise storage systems and the heat that is dissipated due to the high power consumption shall significantly restrict the ability to design higher performance disks in the near future. I shall then present a novel disk drive architecture called DRPM that can provide considerable savings in energy with little loss in delivered performance. Finally, I shall show how DRPM can be leveraged to provide a spectrum of dynamic thermal management policies, which would pave the way for maintaining good performance growth in future disk drives.

    Biography:

    Sudhanva received a BE degree in Computer Science and Engineering at the College of Engineering Guindy, Anna University. His research interests are in storage systems, computer architecture, and fault-tolerance.

    Refreshments will be served in the Lounge (Room 224) at 3:00 p.m.



    Tuesday, April 19, 2005
    Azer Bestavros
    Boston University
    OLSSON 005, 3:30 PM

    Exploiting the Transients of Adaptation for RoQ Attacks on Internet Resources

    ABSTRACT

    Over the past few years, Denial of Service (DoS) attacks have emerged as a serious vulnerability for almost every Internet service. An adversary bent on limiting access to a network resource could simply marshal enough client machines to bring down an Internet service by subjecting it to sustained levels of demand that far exceed its capacity, making that service incapable of adequately responding to legitimate requests. In this talk I will expose a different, but potentially more malignant adversarial attack that exploits the transients of a system's adaptive behavior, as opposed to its limited steady- state capacity. In particular, I will show that a determined adversary could bleed the capacity of an adaptive system, or significantly reduce its service quality by subjecting it to an unsuspicious, low-intensity (but well orchestrated and timed) request stream that causes the system to become very inefficient, or unstable. I will give examples of such "Reduction of Quality" RoQ) attacks on a number of common adaptive components in modern computing and networking systems, including congestion controllers, admission controllers, traffic shapers, and load balancers. RoQ attacks stand in sharp contrast to traditional brute-force, sustained high-rate DoS attacks, as well as recently proposed "shrew" attacks that exploit specific protocol settings. I will present control-theoretic analysis, as well as numerical and simulation results that underscore the potency of such attacks. These results are validated with observations from real Internet experiments.

    This work was done in collaboration with Mina Guirguis and Ibrahim Matta.

    Biography:

    Azer Bestavros obtained his S.M. in 1988 and his PhD in 1992 from Harvard University. He is currently Professor and Chairman of Computer Science at Boston University.

    Professor Bestavros' research interests are in the general areas of networking and real-time systems. Some of his seminal works include his generalization of the classical rate-monotonic analysis to accommodate probabilistic guarantees, his pioneering of the push model for Internet content distribution adopted years later by CDNs, his characterization of Web traffic self-similarity and reference locality, his development of various caching and streaming media delivery protocols, and his development of efficient techniques for inference of network caricatures using real- time end-to-end measurement.

    Professor Bestavros has an extensive list of publications. In 2000, WebBib ranked this list as the most referenced body of Web-related research by a single author. As of July 2004, with over 2,000 citations, CiteSeer ranks this body of work in the top 500 (5%) of the most cited in all of Computer Science at all times. Among many other issued and pending patents, Professor Bestavros is co-inventor of US Patent 6,370,584, which catalyzed a successful networking startup, now part of Network Appliances, Inc. He has delivered over 40 presentations and speeches at universities, research laboratories, and standards committees.

    Professor Bestavros received distinguished service awards from both the IEEE and the ACM. He served as chair, officer, or PC member of most major conferences in real-time and networking systems, including ICNP, Infocom, Sigmetrics, Sigmod, RTSS, RTAS, and ICDE. His research has been funded by grants totaling over $12M from various government agencies and industrial labs.

    Refreshments will be served in the Lounge (Room 224) at 3:00 p.m.



    Monday, April 18, 2005
    Brent Waters
    Stanford
    Host: Greg Humphreys
    Olsson Hall, 3:30 PM

    Fuzzy Identity-Based Encryption -- Privacy for the Unprepared User

    ABSTRACT

    Identity-Based Encryption (IBE) allows the use of an identity as a public key. For example, to encrypt a message one would only need to know the recipient's identity, e.g. the string "bob@yahoo.com", and not need access to a traditional public key infrastructure. I will present a new form of IBE that uses human biometrics as identities (public keys).

    There are two primary advantages of using biometrics as public keys in an Identity-Based Encryption scheme. First, a person will naturally carry his public key with him at all times. This is very useful in a situation, such as an emergency medical visit, where a patient will be unprepared with a traditional public key. Secondly, the process of authenticating oneself to obtain a private key is very natural. One can demonstrate ownership of an identity simply by physically presenting the biometric.

    In this talk I will further discuss the motivations for biometric-based IBE, the primary challenges in developing such as system, and a cryptographic solution that I call Fuzzy Identity-Based Encryption. Additionally, I will give a brief overview of other recent results I have in broadcast encryption and describe some practical applications.

    Refreshments will be served in the CS lounge at 3:00.



    Monday, April 18, 2005
    Elisabeth A. Strunk
    Computer Science Department, University of Virginia
    Host: Paul Reynolds and John Knight
    Olsson 236D, 10:00 AM

    Reconfiguration Assurance in Embedded System Software

    ABSTRACT

    As software systems continually become larger and more complex, assurance of their critical properties becomes correspondingly more difficult. While construction of systems of the quality produced in the past might be feasible, the engineering foundation on which the dependability record of those systems rests is weak. The lack of a rigorous dependability argument in many cases implies that system dependability is probably due at least in part to the care taken by experienced developers in the software's design. Careful development and review are likely to become less effective as the complexity of the developed software grows beyond the limits of straightforward human comprehension. In many software systems, critical properties are only a small subset of all desirable system properties. In this dissertation, I hypothesize that, in most very complex systems, there is often some much simpler subset of functionality over which critical properties can be expressed. Assuring properties over the simpler subset can provide assurance of critical properties over the entire system. In this case, system dependability can be reduced to a guarantee that either the system will function correctly, or the non-critical function will do nothing to interfere with critical system properties. My work provides a method for constructing systems to be dependably reconfigurable. A system with reconfiguration at the center of its assurance argument can allow its primary function to fail and then reconfigure to some simpler function, mitigating any unacceptable failure consequences. Reconfiguration thus controls the effective complexity of the system without forcing that system to sacrifice desired, but unassurable, capabilities. Focusing a system's dependability argument on reconfiguration means that reconfiguration must proceed correctly with very high assurance. The system construction approach in this work also provides a method through which system dependability properties can be shown. The approach accomplishes this by: (1) introducing a formal definition of reconfiguration and an associated set of high-level, general properties; (2) constructing an architecture that guarantees the high-level reconfiguration properties; and (3) making non-crucial software function fail-stop, so that the software either works correctly or fails in a way that does not disrupt other applications. Showing that a specific system complies with the architecture's properties implies assurance of reconfiguration for that system. To illustrate the ideas in this work, my colleagues and I have built part of a hypothetical avionics system that is typical of what might be found on a modern general-aviation aircraft or an unmanned aerial vehicle.



    Thursday, April 14, 2005
    Jason D. Hiser
    Department of Computer Science, University of Virginia
    Chair: Kevin Skadron
    Advisor: Jack W. Davidson
    Olsson 228E, 2:00 PM

    A Ph.D. Defence

    Effective Algorithms for Partitioned Memory Hierarchies in Embedded Systems

    ABSTRACT

    Many architectures today, especially embedded systems, have multiple memory partitions, each with potentially different performance and energy characteristics. To meet the strict time-to-market requirements of systems containing these chips, compilers require retargetable algorithms for effectively assigning values to the memory partitions. Furthermore, embedded system designers need a methodology for quickly evaluating the performance of a candidate memory hierarchy on an application without relying on time-consuming simulation.

    This dissertation presents algorithms and techniques to effectively meet these needs. First, EMBARC is presented. EMBARC is the first algorithm to realize a comprehensive, retargetable algorithm for effective partition assignment of variables in an arbitrary memory hierarchy. It supports a wide variety of memory models including on-chip SRAMs, multiple layers of caches, and even uncached DRAM partitions. Even though it is designed to handle a wide range of memory hierarchies, EMBARC is capable of generating partition assignments of similar quality to algorithms designed for specific memory hierarchies. A large range of benchmarks and memory models is used to demonstrate the effectiveness of the EMBARC algorithm. Experiments show optimal or near-optimal results for every catagory of memory hierarchy tested.

    This dissertation also presents MPRES. MPRES is an algorithm to estimate the effectiveness of the memory hierarchy for a given application without requiring time-consuming simulations. To show that MPRES generates accurate performance estimates, MPRSE performance estimates are compared to detailed simulation results. Experiments show performance estimations trend the same as values obtained via simulation. Furthermore, MPRES is significantly faster than simulation, requiring two orders of magnitude less time.

    Together, MPRES, EMBARC, and their supporting framework provide a comprehensive solution for embedded software designers who must choose a suitable partitioned memory hierarchy and application programers who rely on the compiler to automatically assign variables to memory partitions.



    Wednesday, April 13, 2005
    Yih-Chun Hu
    Carnegie Mellon School of Computer Science
    Olsson 011, 3:30 PM

    Securing Network Routing

    ABSTRACT

    Networks are increasingly used for critical functions, such as e-commerce and online banking. Unfortunately, networking services were designed for trusted environments, and are consequently extremely vulnerable to attack.

    In this talk, I will describe my work on securing routing, the central network service, in both wireless ad hoc networks and in the Internet. In the context of securing wireless ad hoc network routing, I then describe my work on SEAD, a simple and highly efficient protocol that secures the distance vector protocol against attack. I then present SPV, my protocol for secure Internet routing. This protocol is the first that provides strong security properties even when relatively few ISPs deploy the protocol, and even when those ISPs are not directly connected. Furthermore, SPV is highly efficient in computation.

    Biography:

    Bio: Yih-Chun Hu received his B.S. from the University of Washington in 1997 and his Ph.D. from Carnegie Mellon University in 2003. In his thesis work at Carnegie Mellon, he focused on security and performance in wireless ad hoc networks. Yih-Chun's research interests include security and systems. He is currently a visiting postdoctoral researcher at the University of California, Berkeley.

    Refreshments will be served in the Lounge (Room 224) at 3:00 p.m.



    Tuesday, April 12, 2005
    Yuan Wei
    Computer Science Department, University of Virginia
    Chair: John A. Stankovic
    Advisor: Sang H. Son
    Olsson 228E, 3:30 PM

    A Ph.D. Proposal

    QoS Management for Distributed Real-Time Data Services

    ABSTRACT

    Many applications need to access real-time data that are spread in large distributed environments. Typical applications that require distributed real-time data services include distributed shipboard control systems, online stock trading systems, telecommunication systems, health monitoring systems, traffic control systems, home security monitoring systems, and numerous other applications. The general data service systems that support these applications must be able to collect and distribute large amounts of dynamic data in real time. Since many of these applications are open systems and need to handle unpredictable system workloads, the data service systems also need to provide service differentiation and service quality adaptation capabilities. We propose to study and develop distributed real- time data service systems that provide flexible, high-performance, and reliable distributed real-time data services with quality-of-data (QoD) and quality-of-service (QoS) guarantees. The resulting system will be a general data service system that provides QoS and QoD support for both real-time transactions and queries. More specifically, for QoD management, we propose a dynamic replication algorithm to maintain the quality of real-time based data items and a dynamic update strategy adaptation algorithm to maintain quality of real-time derived data items. To provide QoS support for real- time transactions, we apply a feedback-based system performance monitoring and control algorithm to handle the workload fluctuations in distributed real-time databases. For real-time query processing, we address a more general query processing problem where real-time data are of the form of data streams. We extend a SQL-like continuous query language to specify real-time stream data queries and propose a set of QoS-aware operator scheduling and QoS management algorithms to maintain the specified query service qualities.



    Monday, April 11, 2005
    Yutao Zhong
    Computer Science Department, University of Rochester
    Olsson Hall, 3:30 PM

    Whole-Program Data Locality Hierarchy

    ABSTRACT

    As the speed gap between CPU and memory widens, cache performance increasingly determines performance, cost and power consumption of computer systems. The effect of caching depends on program locality, or the pattern of data reuse. However, locality has been an elusive concept at the program level because it requires defining, predicting, and verifying patterns across billions of accesses to millions of memory locations.

    In this talk, I will describe our whole-program data locality model based on reuse distance. Two selected topics will be presented. First, by profiling a few program inputs, we extract regular locality patterns and predict their changes in other data inputs. This predictability has been verified on a wide range of programs and extended to an accurate prediction of cache miss rate across program inputs on all cache sizes. Second, a distance-based model is used in reference affinity analysis in large complex programs. It has led to a new technique for array reorganization in Fortran programs and structure reorganization in C programs. The new technique consistently outperforms the data layout given by the programmer, compiler analysis, frequency profiling, and statistical clustering.

    I will conclude the talk with a discussion of some of my other work and my future research plan.

    Biography:

    Yutao Zhong is a Ph.D. candidate of the Department of Computer Science at University of Rochester. She received the B.S. and M.E. from Nanjing University, China. Her research areas are compiler-assisted program analysis and optimization, with the emphasis on program locality behavior. For more information please see http://www.cs.rochester.edu/~ytzhong/.



    Friday, April 08, 2005
    Nina Mishra
    University of Illinois/Urbana-Champaign
    Olsson 011, 3:30 PM

    Privacy-Preserving Auditing Algorithms

    ABSTRACT

    Organizations now maintain large quantities of personal information. Consequently, there is a growing need to find ways to keep this confidential information private. The need for privacy directly competes with the need to use this data for the discovery of patterns. For example, in a dataset containing the HIV status of patients, we would like to keep private the HIV status of any particular patient but allow the discovery of the total fraction of patients that are HIV+. We describe auditing algorithms that monitor an online stream of queries posed to a dataset and either deny the answer to a query if it breaches privacy or give the true answer if it does not. We uncover a fundamental problem that existing offline auditing algorithms cannot be used to solve the online problem as denials leak information. We then propose a new model of auditing, called simulatable auditing, where denials provably do not leak information. Finally we provide new simulatable auditing algorithms.

    Biography:

    Nina Mishra currently holds a joint appointment as a Senior Research Scientist at HP Labs and as an Acting Faculty member at Stanford University. Her research interests are in the design and analysis of data mining, machine learning and privacy-preserving algorithms. She served as Program Chair for the ICML'03 conference (International Conference on Machine Learning) and has served on numerous data mining and machine learning program committees. She also serves on the Editorial Board of the Machine Learning journal. She earned a PhD in Computer Science from the University of Illinois at Urbana-Champaign.

    Refreshments will be served in the Lounge (Room 224) at 3:00 p.m.



    Friday, April 08, 2005
    William S. Greenwell
    Department of Computer Science, University of Virginia
    Chair: David Evans
    Advisor: John Knight
    Olsson 236D, 10:00 AM

    A Ph.D. Proposal

    Pandora: An Approach to Analyzing Safety-Related Digital System Failures

    ABSTRACT

    Accidents have occurred in which failures of digital systems have contributed to property damage, injury, and even loss of life. Most investigative agencies do not know how to investigate these failures comprehensively because the complexity and coupling of a digital system's functions can obfuscate its design, making it difficult for an investigator to understand the system, and because the uniqueness of each digital system prevents investigators from developing generic checklists for diagnosing failures. To address these problems, this thesis proposes the development of Pandora, a systematic approach to the analysis of safety-related digital system failures that is based upon the system safety case.

    As the complete argument that a system is safe to operate, the safety case contains the information needed to understand the safety-related aspects of a system and to diagnose and address the failure. Pandora audits a system's safety case to identify the fallacious reasoning or faulty evidence that allowed a failure to occur, and in doing so it drives the elicitation of background information and counter-evidence needed to diagnose the failure. The products of this audit are a set of lessons comprising the flaws identified in the original safety argument, a revised safety case that is free of those flaws, and a set of recommendations for repairing the system and its associated development and operational practices. Pandora is a rigorous approach because it systematically revisits each of the safety claims that, if unsatisfied, could have contributed to a failure, and it is efficient because it considers only those system details, evidence, and safety claims that pertain to the investigation. This proposal discusses Pandora and its supporting work, further development, and planned evaluation of the approach through case studies.



    Monday, April 04, 2005
    Michael Swift
    University of Washington
    Host: Kevin Sullivan
    Olsson Hall, 3:30 PM

    Improving the Reliability of Commodity Operating Systems

    ABSTRACT

    Despite decades of research in fault tolerance, commodity operating systems, such as Windows and Linux, continue to crash. In this talk, I will describe a new reliability subsystem for operating systems that prevents the most common cause of crashes, device driver failures, without requiring changes to drivers themselves. To date, the subsystem has been used in Linux to prevent system crashes in the presence of driver failures, recover failed drivers transparently to the OS and applications, and update drivers "on the fly" without requiring a system reboot after installation. Measurements show that the system is extremely effective at protecting the OS from driver failures, while imposing little runtime overhead.

    Refreshments will be served in the CS lounge at 3:00.



    Monday, March 28, 2005
    Kevin Fu
    MIT
    Host: David Evans
    Olsson 009, 3:30 PM

    Secure content distribution using untrusted servers

    ABSTRACT

    A publisher can make content available to many readers through replication on remote, untrusted computers. Yet a reader should have confidence that content is authentic, and publishers should be able to control access to content. This talk presents the design and implementation of the SFS read-only file system (SFSRO) for secure, scalable distribution of public and private content replicated using untrusted servers.

    SFSRO provides authenticity of single-writer, many-reader content. A publisher creates a digitally-signed database out of the contents of a source file system. Untrusted servers replicate the content, accessed by readers through a file system interface. A reader accepts only verified, authentic content --- eliminating the need to trust the distribution infrastructure.

    To control access to private content, a publisher encrypts content for confidentiality. This talk introduces lazy revocation and key regression to cope with the cost of distributing keys to readers. These techniques allow a publisher on a low-bandwidth connection to support many readers accessing private content.

    Biography:

    Kevin Fu is a doctoral student in MIT's department of EECS, a member of the MIT Computer Science and Artificial Intelligence Lab (CSAIL), and a visiting scholar at the Johns Hopkins University Information Security Institute in Baltimore, MD. His research interests include computer system security, secure storage, RFID security, and Web authentication. Kevin holds an SB in Computer Science & Engineering and an MEng in Electrical Engineering & Computer Science from MIT.

    Refreshments will be served in the Lounge (Room 224) at 3:00 p.m.



    Wednesday, March 23, 2005
    Cliff Zou
    University of Massachusetts
    Host: Tarek Abdelzaher
    Olsson Hall, 3:30 PM

    Modeling, Early Detection, and Mitigation of Internet Worm Attacks

    ABSTRACT

    In recent years, Internet worm has become one of the major threats to the security of the Internet. In this talk, I will present our major work on modeling, early detection, and mitigation of Internet worm attacks.

    In the worm modeling area, I will first present the fluid model for worm propagation modeling. Then I will present how we model Witty worm's destructive behavior and how a worm propagates under different scanning strategies.

    To detect the presence of an unknown Internet worm at its early spreading stage, we present a Kalman-fliter based "trend detection" system, to detect the exponential growth trend, not the traffic burst, of worm monitored data. This novel detection methodology is robust to non-worm noise in monitored data.

    We have identified two basic autonomous defense principles, "preemptive quarantine" and "adaptive adjustment". Based on the first principle, we present a "dynamic quarantine" defense system. Based on the second principle, we present a "self-tuning defense system", which automatically adjusts the parameter settings of a defense system through minimizing the combined cost of false alarms and attack damage.

    Biography:

    Cliff C. Zou received his B. Sc degree and M. Sc degree in Electrical Engineering from University of Science and Technology of China, China in 1996 and 1999, respectively. He is a Ph.D candidate in the Department of Electrical and Computer Engineering at the University of Massachusetts Amherst, and is expected to obtain Ph.D degree in May 2005. His research interests are computer and network security, including modeling and defense of Internet viruses and worms, denial-of-service attacks, and intrusion detection.

    Refreshments will be served in the CS lounge at 3:00.



    Wednesday, March 16, 2005
    Brian Demsky
    MIT
    Host: David Evans
    OLSSON 009, 3:30 PM

    Data Structure Repair

    ABSTRACT

    Programs often make assumptions about the states of the data structures that they manipulate. Errors that cause these data structures to become inconsistent can therefore be especially damaging, since inconsistent data structures may cause software systems to behave unacceptably or even fail catastrophically.

    In this talk, I will present my specification-based approach to data structure repair. In this approach, the developer simply writes a declarative specification of the key consistency properties for the data structures. My repair algorithm generator then compiles this specification to automatically generate a repair algorithm for the data structure. The automatically-generated repair algorithm is guaranteed to repair the inconsistencies in damaged data structures and to terminate. I have evaluated my specification-based repair technique on several real-world applications. These applications include: AbiWord, an open source word processor; a parallel x86 emulator; CTAS, an air traffic control tool; FreeCiv, an online game; and a simplified Linux file system. My repair technique successfully enabled these programs to execute through otherwise fatal data structure corruption errors.

    Biography:

    Brian Demsky is a Ph.D. Candidate in the Program Analysis and Compilation Group at the MIT Computer Science and Artificial Intelligence Laboratory. He received a BS in Physics and a BS in Electrical Engineering from the University of Texas at Austin and a SM in Computer Science from the Massachusetts Institute of Technology. He is a recipient of the Fannie and John Hertz Foundation Fellowship. His research addresses software reliability, software debugging, and program understanding.

    Refreshments will be served in the CS lounge at 3:00.



    Monday, March 14, 2005
    Kim Hazelwood
    Havard University
    Olsson 011, 3:30 PM

    Managing Bounded Code Caches in Dynamic Binary Optimizers

    ABSTRACT

    Dynamic binary optimizers store optimized/translated code in a software-managed code cache in order to maximize reuse of transformed code. Code caches store superblocks that are not fixed in size, may contain links to other superblocks, and carry a high replacement overhead. While many cache management schemes exist, we found that they are less effective for code caches due to these additional constraints. In the past, designers of dynamic binary optimizers have used the SPEC2000 benchmarks to justify their use of simple code cache policies. We show that the problem and importance of code cache management changes dramatically when we look at today's interactive Windows applications, and motivates the design of sophisticated code cache management algorithms.

    In this talk, I will begin by describing the code cache management problem. Next, I will discuss two novel code cache policies that we have published over the past few years. In one investigation, we found that evicting more than the minimum number of superblocks will improve the runtime overhead of code cache evictions. Our second algorithm introduces a generational approach to code cache management, and distinguishes cached superblocks by their expected lifetimes. Finally, I will discuss several avenues for future work in the areas of code caching, dynamic optimization, and power-aware computing.

    Refreshments will be served in the Lounge (Room 224) at 3:00 p.m.



    Monday, March 07, 2005
    Ying Lu
    Department of Computer Science, University of Virginia
    Olsson 011, 3:30 PM

    Towards Self-Managing Computing Systems: Augmented Control Theory Approaches

    ABSTRACT

    Computing systems are becoming increasingly large and complex making their performance less predictable and their management more challenging and costly. To achieve performance assurances while cutting management cost, computing systems are needed that can continually manage their performance in the face of changing computing demands and environmental conditions; an architectural paradigm recently called "Autonomic Computing". Towards building autonomic computing systems, I developed a new analytic foundation for automatic performance regulation in software services based on feedback control theory. In the talk, I will present my performance regulation framework and the methodology for applying it to current software service architectures. Specifically, I will show how to choose the right sensors, use the available software performance actuators, map performance regulation to a feedback control problem, model the computing system and design control modules to achieve performance specifications. Following this methodology, we have successfully provided robust web QoS under significant load and resource uncertainties. Two applications will be illustrated; namely, robust delay control in an Apache web server and robust hit rate control in a Squid proxy cache. They demonstrate the success of the control theory approach in providing a flexible range of performance assurances in an adaptive manner at minimum cost.



    Wednesday, March 02, 2005
    Westley Weimer
    UC Berkeley
    Host: Paul Reynolds
    OLSSON 005, 3:30 PM

    Exceptional Situations and Program Reliability

    ABSTRACT

    Software quality and reliability are increasingly important, but software remains buggy. Static analyses can find bugs before a product ships, but I believe they are only one stage in a larger process. For a particular class of bugs I show how to find mistakes, I give tools for fixing the problem, and I infer some of what the program should be doing.

    I will present a static dataflow analysis for finding bugs in software routines that handle errors and exceptional situations. It is difficult to write iron-clad error-handling routines, and existing programming language features often provide poor support for executing clean-up code and for restoring invariants in such exceptional situations. This flow-sensitive analysis keeps track of outstanding obligations along program paths and does a precise modeling of control flow in the presence of exceptions. Using a set of standard specifications it has found over 1 thousand error handling bugs in almost 4 million lines of Java code.

    To address such bugs, I propose a language feature that keeps track of obligations at run time and ensures that they are discharged. I use case studies to demonstrate that this feature is natural, efficient, and can improve reliability; for example, retrofitting a 34kLOC program with it resulted in a 0.5% code size decrease, a surprising 17% speed increase (from correctly deallocating resources in the presence of exceptions), and more consistent behavior.

    I will also discuss a novel specification mining technique that infers application-specific safety policies automatically. This mining algorithm uses information about error handling and exceptional situations to learn temporal safety rules with few false positives. The mined safety rules find more software bugs than standard specifications do.

    Refreshments will be served in the CS lounge at 3:00.



    Wednesday, February 16, 2005
    Chenxi Wang
    Carnegie Mellon University
    Olsson 011, 3:30 PM

    The Coral Project: Defending against large-scale attacks on the Internet

    ABSTRACT

    Computer worms and viruses are a prevalent threat to today's systems and networks. The recent outbreaks have been increasingly more virulent and damaging. The Coral project at CMU aims to develop innovative, network-wide defenses against widespread worm and virus attacks. Our approaches are rooted in one simple principle: understanding the fundamental factors that enable the fast spread of malicious code---these factors include those that are topological and those that are intrinsic to the infection process. We seek to study, model, and analyze these factors, and then to exploit their characteristics to develop original network security technologies. This talk reports the research progress of Coral in its first year. We started our research asking the following questions: a) How will a virus/worm propagate in a real network?, b) Does an epidemic threshold exist for a finite power-law graph (as most real network topologies follow a power-law structure), or any finite graph?, c) Where are the most effective places in the Internet to engineer containment mechanisms? We answer the first question by providing equations that accurately model malicious propagation in an arbitrary network topology. We propose a general epidemic threshold condition that applies to arbitrary graphs: we prove that, under reasonable approximations, the epidemic threshold for a network is indicated by the inverse of the largest eigenvalue of the adjacency matrix. For the third question, we investigated the effect of containment at individual hosts, edge routers, and backbone routers. Our analysis shows that both host and edge-router based containment result in a slowdown (in the spreading rate of the worm) that is linear to the number of hosts (routers) implementing the containment filter. Containment at the backbone routers, however, achieves near exponential slowdown. We are currently studying traces we obtained from Symantec, Akamai, and our own network. Preliminary study revealed interesting traffic patterns that could potentially evade containment mechanisms that operate strictly on limiting outgoing IP addresses. I will discuss our ongoing work in developoing new containment techniques to curb the spread of email and topological worms.

    Refreshments will be served in the Lounge (Room 224) at 3:00 p.m.



    Monday, February 14, 2005
    Doina Caragea
    Iowa State University
    Olsson 011, 3:30 PM

    Learning classifiers from distributed and semantically heterogeneous data sources

    ABSTRACT

    In many real world applications data sources of interest are typically distributed and semantically heterogeneous, making it impossible to use traditional machine learning algorithms for knowledge acquisition. However, we observe that most of the learning algorithms use only certain statistics computed from data in the process of generating the hypothesis that they output. We use this observation to design a general strategy for transforming traditional algorithms for learning from data into algorithms for learning from distributed data. The resulting algorithms are provably exact, in the sense that the classifiers produced by them are identical to those obtained by the corresponding algorithms in the centralized setting (i.e., when all of the data are available at a central location). They also compare favorably to their centralized counterparts in terms of time and communication complexity. To deal with the semantical heterogeneity problem, we introduce ontology-extended data sources and define a user perspective consisting of an ontology and a set of interoperation constraints between data source ontologies and the user ontology. These constraints can be used to define mappings needed to answer statistical queries from semantically heterogeneous data viewed from a certain user perspective. The answers to such queries are further used to extend our approach to learning from distributed data into a theoretically sound approach to learning from semantically heterogeneous data.

    Biography:

    Doina Caragea is a Postdoctoral Research Associate in Computer Science department at Iowa State University. Her research interests include artificial intelligence, machine learning, data mining, information integration, bioinformatics and visualization. Doina received her Ph.D. in Computer Science from Iowa State University in August 2004. She has published more than 10 refereed conference or journal publications based on her thesis research. She has been awarded an Iowa State University Research Excellence Award. The award honors students whose research accomplishments place them among the top 10 percent of all graduate students at Iowa State University. Doina also received an IBM Research Fellowship during 2002-2003 and 2003-2004.



    Wednesday, February 09, 2005
    Wei Le
    Department of Computer Science, University of Virginia
    Advisor: Kevin Sullivan
    Attending Faculty: Mary Lou Soffa
    Olsson 236D, 4:00 PM

    A Master's Project Presentation

    Specification squeezing: extending the reach of bounded exhaustive test input generation

    ABSTRACT

    As software becomes larger and more complex, assuring its quality remains a difficult problem of great importance. One of the solutions is the bounded exhaustive testing (BET). In BET, a formal specification is given to describe the structure of the test input. A constraint solver is used to automatically and exhaustively generate test inputs within a specified size. Case studies have indicated the potential feasibility of BET to reveal failure modes of reasonably complex software systems. The main challenge of BET is to extend the bound of the test input to a given complexity and size so that more failure modes could be included.

    The work of Sullivan et al., presented in the ISSTA'04, showed that naive use of BET, based on Jackson's Alloy tool and TestEra system, did not work. The problem was that the space of inputs denoted by the original Galileo specification was too large for the tools to handle. They would run out of memory and crash before generating test inputs in a sufficiently large scope. Sullivan et al. went on to show that a certain restructuring of the original specification reduced the state space to the point that generation of inputs to a significant bound became possible. In particular, inputs were generated to the point that running, rather than generating them, became the bottleneck.

    What the ISSTA paper did not address was the nature of the restructuring that enabled Alloy/TestEra to generate a reasonable number of test inputs. The goal of this work was to understand and characterize the essential nature of the trick that allowed Alloy/TestEra to work. The contribution of this work is a generalized account of that trick, which we have called specification squeezing. The idea is that interchangeable values within specification domains are abstracted away to reduce the state space. These reductions are documented in a separate piece of specification. The key idea is to use Alloy/TestEra to generate abstract test inputs from the abstracted specification, and then apply a straightforward post-processor to expand those abstract inputs using the auxiliary information. In that way, we obtained the inputs that would have been generated in the first place. This approach was tested in the context of the Galileo case study. The experiment results showed that it corrected two bugs present in the previous test input generation of the Galileo. Furthermore, we have begun formalization of the specification reconstruction principle and design of the algorithm for automatic reconstruction.



    Monday, February 07, 2005
    Bernhard Steffen
    University of Dortmund, Dortmund, Germany
    Olsson 011, 3:30 PM

    Behavioral Model Construction

    ABSTRACT

    Automatically generated models may provide the key towards controlling the evolution of complex systems, may form the basis for test generation, and may be applied as monitors for running applications. However, the practicality of automata learning is currently largely impeded by its high complexity and unrealistic frame conditions. After a short introduction to automata learning, the talk will focus on methods to increase its practicality. In particular it will discuss applications specific optimizations, and illustrate their power along a realistic telecommunication scenario.

    Refreshments will be served in the Lounge (Room 224) at 3:00 p.m.



    Monday, January 17, 2005
    Hridesh Rajan
    Department of Computer Science, University of Virginia
    Chair: John Knight
    Advisor: Kevin Sullivan
    Olsson 236D, 1:00 PM

    A Ph.D. Proposal

    Improved Abstractions for Aspect-Oriented Software Development

    ABSTRACT

    Aspect-oriented software development promises to improve our ability to modularize complex software effectively. However, aspect-oriented programming languages and tools are still in their infancy, and many applications remain unexplored. The problem that I propose to address in my dissertation is that, notwithstanding the advances that have been made, the design models for even the most successful aspect-oriented languages today remain unnecessarily complex, significantly constrain the program designer, lead to unnecessarily complex programs, and exhibit unacceptable performance degradation as a function of the richness of advising structures. I have traced many of these problems to a key design decision at the heart of major existing language designs: they embrace a non- object-oriented, static module-based view of what an aspect is and how it interacts with the other components of a software system. My solution is based on the idea that aspects should be formulated as first-class constructs analogous to classes: e.g., subject to instantiation under program control. I show that, without loss of expressiveness, this change significantly improves the compositionality of aspect-oriented components; creates valuable new architectural possibilities; enables a unification of object- and aspect-oriented programming, simplifying the programming model; and mitigates the inherent performance problem in the current language model. I propose to develop my aspect language design ideas further with efforts to generalize both join point models and the concept of compile- time weaving at selected join points. In this proposal, I describe results to date, including published results in the three top conferences in my area, and the design of a language and a full working compiler; and I outline work that remains to be done.



    Monday, January 10, 2005
    Yuanfang Cai
    Department of Computer Science, University of Virginia
    Chair: John Knight
    Advisor: Kevin Sullivan
    Olsson 228E, 3:00 PM

    A Ph.D. Proposal

    Modularity in Abstract Design: A Theory and Applications

    ABSTRACT

    Software design involves myriad decisions, from choosing programming languages, to architectural structures, to algorithms, data structures, coding conventions, etc. People have good understanding, based on sound computer science, of how to make some of these decisions. For example, we have the necessary science for people to make effective, defensible choices of algorithms to meet given performance requirements. However, design decision-makers face other crucial decisions without the benefit of rigorous problem formulations or analyses. In this work I focus on decisions involving the coupling of design decisions, in general, and modularity in design, in particular, and on their relationships to the dynamics and economics of design variation in space and time. The kinds of decision problems that arise in this realm include the following: Is it worthwhile in the long run for a development team to delay new features in order to refactor a system to reduce the cost of future change? Which of several design structures better accommodates expected changes? Which of several current design options reduces the long-term cost of change? Decisions in these areas have profound economic and other impacts on system design and evolution, but today people make such decisions based mainly on intuition and experience. The problem is that we lack high-level design representations and methods for formulating and analyzing such decision problems. I propose to develop such a framework and show that it has the potential to help improve our understanding of such design decision problems by allowing us to formalize them precisely and resolve them analytically. The theory I propose is based on the use of declarative, logical constraint networks to represent designs and design spaces precisely but at a high level of abstraction, and the use of state transition automata, computed from these constraint networks, to capture and express possible phenomena of design variation in these spaces. I have already demonstrated the ability to compute design structure matrices (DSM?s) from my constraint representations, linking my declarative representations to an existing theory and sets of analysis techniques. I have shown that the connection works using a simple but seminal example: Parnas?s key word in context (KWIC) design analysis. I have also developed a prototype tool to automate model creation and analysis. The work that remains includes formalizing additional decision problems and associated analysis techniques, as well as evaluative work, especially of an experimental nature. The basic claims that I intend to test are that the approach provides new insights in design and has the potential as a foundation for methods of decision analysis useful in actual design practice.