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.
|
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.
|
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.
|
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).
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.
|
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.
|
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. |
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.
|
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.
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.
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."
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.
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.
|
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.
|
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.
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.
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.
|
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.
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.
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.
|
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.
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. |