Towards Robust Overlay
Networks: Enhancing Adaptivity Mechanisms with
Byzantine-Resilience
Dr. Cristina Nita-Rotaru
Purdue University
Department of Computer Sciences
http://homes.cerias.purdue.edu/~crisn
Adaptive measurement-based overlay networks offer increased performance and resilience to benign failures for end-to-end communication by using aggressive adaptivity mechanisms. These mechanisms dynamically optimize application-centric metrics such as latency, jitter, bandwidth, and loss rate. However, end-systems are more vulnerable than core routers, making overlay networks susceptible to malicious attacks coming from untrusted outsiders, and especially from trusted (but compromised) members of the overlay. Unlike outsider attacks, insider (or Byzantine) attacks can not be prevented by simply deploying cryptographic authentication mechanisms.
In this talk, we present several insider attacks against adaptivity mechanisms in overlay networks and demonstrate them against the ESM/ Narada multicast overlay system. The attacks target the overlay network construction, maintenance, and availability and allow malicious nodes to control significant traffic in the network, facilitating further attacks such as selective forwarding and traffic analysis. We propose techniques to enhance the adaptivity mechanisms with Byzantine-resilience and demonstrate their effectiveness through real-life deployments and emulations conducted on the PlanetLab and DETER testbeds, respectively.
BIO
Cristina Nita-Rotaru is an Assistant Professor in the Department of Computer Science and a member of Center for Education and Research in Information Assurance and Security (CERIAS) at Purdue University. She leads the Dependable and Secure Distributed Systems Laboratory. Her research interests lie in designing distributed systems, network protocols and applications that are dependable and secure, while maintaining acceptable levels of performance. Her Ph.D. work, Secure Spread, focused on providing support for secure and robust services for group communication. Secure Spread is one of the 12 technologies featured on a DARPA DVD summarizing the accomplishment of 6 programs (Cyber Panel, Dynamic Coalitions, Chats, OASIS, Fault Tolerant Networks, and IA OPX) and it was selected to participate in JWID 2004, a large coalition experiment. Her current research focuses on designing intrusion-tolerant architectures for distributed services that scale to wide-area networks, investigating survivable services in multi-hop wireless networks and building robust and secure overlay networks. Her work is funded by the Center for Education and Research in Information Security and Assurance (CERIAS), by the Defense Advanced Research Projects Agency (DARPA), and by the National Science Foundation (NSF).
Beyond the PhD
Getting a PhD can be a goal in and of itself, but usually it is a
stepping stone to other goals. Suppose you have just finished your PhD
in Computer Science. What happens next? This talk encapulates my own
personal opinions about why one gets a PhD, how one gets a PhD and the
transition from graduate student to professional. What you want to do
after you get a PhD changes what you should do while you get your PhD.
Whether you want a faculty position at a Unversity or with a company,
how do you increase your chances of getting the job you want? What
does the competition look like? What are the elements of a good vita,
and what mistakes should you avoid? And what should you know about
those first few years after your PhD?
On Demand Skills for an On Demand World
Phil Farley, of IBM's Academic Initiative team, will provide some
insights into the world of Open Source and Open Standard technologies
that are in high demand in the corporate world. Young IT
professionals are in unique positions to fill the rolls being
abandoned by an aging workforce. There are lots of jobs out there in
the real world. Phil will describe the skills you need to land the
highest paying of the lot, and will outline a way that IBM can help
through the Academic Initiative.
Reducing Complexities
Efficient programs are difficult to code, even for the best of
programmers and scientists. Therefore, in this research, we
`outsource' to a compiler, algorithm optimizations that are hard for
most programmers. Take, for an example, the following computation (in
latex syntax)
for i = 0 ... n, Y[i] = \max_{j=i}^{2i} \max_{k=i}^{3i-j} X[j,k]
A straightforward implementation (given below) of such a specification has Theta(n3) complexity.
Model-based Security Engineering
The current industrial practice in the development and use of
security-critical software systems is far from satisfactory.
There is so far only limited support for the automated analysis
of artefacts created during industrial development and
deployment of software for security requirements
such as secrecy, integrity, and authenticity. We apply formal
security analysis techniques to such artefacts, which include
specifications in the Unified Modeling Language (UML),
annotated C code, and permission configuration data. The
security analysis techniques make use of automated theorem
provers for first-order logic. We give examples for security
flaws found in industrial software using our tools.
Fingerprinting Internet Paths using Packet Pair Dispersion
Path fingerprinting is an essential component of applications that
distinguish among different network paths, including path selection in
overlay networks, multi-path routing, monitoring and diagnosis of
network problems, and developing a deeper understanding of network
behavior. We propose a new approach to Internet path fingerprinting
based on the distribution of end-to-end packet-pair measurements. This
approach allows detection of busy link sharing between two paths, even
when those segments have low utilization and are not the paths'
bottlenecks. While our fingerprints do not assure physically disjoint
paths (since that requires information external to the network), they
reflect the traffic and link characteristics of intermediate
links. This methodology is therefore tolerant of opaque clouds such as
VPNs, VLANs, or MPLS (unlike traceroute).
Using analysis and simulation we explore the network factors that
affect the fingerprints, and we introduce a simple method to compare
them. Through measurements of up to a year over 15 Internet paths, we
show that our fingerprints are both distinct and persistent over
periods of several months, making their collection and use for path
selection feasible.
Protecting Critical Computing Systems: A Hardware/Software Codesign Approach
Widespread piracy and malicious attacks on software systems have
become a rapidly growing economic burden. As a result, research into
defense mechanisms for digital information has intensified by
necessity.
Many recently proposed architectures attempt to provide a
tamper-resistant execution environment through a combination of
cryptographic storage and memory domain separation. These approaches
typically assume that an attacker does not have low-level access to
the supporting hardware. Consequently, these architectures fail to
prevent an assortment of sophisticated and increasingly practical
local attacks that can leak underlying information and compromise
trust. For critical computing systems, such an approach may not
provide a sufficient level of security.
This talk will focus on the design and evaluation of software
protection architectures that utilize reconfigurable hardware as a
run-time integrity enforcement engine. By considering the additional
threats posed by untrusted processor and memory components, the joint
hardware/software codesign approach presented here provides a higher
level of security. Also, the choice of reconfigurable hardware
increases the flexibility available to system architects, and the
ensuing designs are immediately applicable to a number of commercial
hardware platforms available today.
Techniques and optimizations that are well-suited to this approach,
including register sequence encoding, selective memory encryption and
protection, and dynamic program-flow verification, will be discussed.
Results demonstrate that this framework can serve as a successful
basis for the development of applications that meet a wide range of
security and performance requirements.
Toward a better probabilistic understanding of sequence alignment
While pairwise sequence alignment is the most fundamental problem in
bioinformatics, it still continues to be an active area of research as
well. In the past few years, one particularly impressive discovery
was the finding that the quality of an alignment algorithm can be
tuned through a parameter called its seed model. With no runtime
cost, this approach can be adapted to yield a 50% improvement in
alignment algorithm success, if alignments match a trivial
probabilistic model.
We will review this work, and then describe our subsequent work for
more complicated probabilistic models and seed models. Finally, we
will describe an approach to obtain 100% sensitivity in sequence
alignment in runtimes hundreds of times smaller than were previously
possible.
This is joint work with Brona Brejova, Tomas Vinar, Jinbo Xu, Ming Li
and Bin Ma.
Building Better Gene Finders
Gene finding is the task of locating parts of a DNA sequence that
encode proteins. Accurate gene annotation is a key to understanding
an organism: it is needed to study gene regulation, protein folding,
and function. Commonly used methods for gene finding are based on
hidden Markov models, probabilistic models that characterize
differences in the statistical properties of introns, exons, and
intergenic regions.
In this talk, I will present our new gene finder ExonHunter. We will
explore two ways of increasing the accuracy of gene prediction. First,
we improve the accuracy by using information other than the DNA
sequence (for example, databases of known proteins, genome-genome
comparisons, or EST databases). Each of these gives us partial
information about gene location and structure. We have developed a
novel method to combine such heterogeneous information with hidden
Markov models.
We can also achieve substantial improvements by extending hidden
Markov models to model more features of biological sequences. This is
a tricky task, since the sequences are long, and we need to balance
running time of generalized algorithms and accuracy of our models. We
will show that even small changes in strucuture of the model may lead
to computationally infeasible tasks.
Characterizing Flows in Wireless Networks
The convenience of wireless technologies has led to proliferation of
various wireless networks. As one of the most widely deployed wireless
networks, wireless Local Area Networks (wireless LANs) provide
high-speed wireless connectivity to users for accessing the
Internet. However, wireless LANs bring significant challenges to
network management. Network management includes tasks such as traffic
regulation, network performance monitoring, fault diagnosis,
etc. Managing wireless LANs is particularly difficult because of two
unique properties of wireless networks: user mobility and unreliable
wireless channels. In this talk, I will present results for a specific
network management problem: managing the "flow". Flow refers to a
sequence of packets traveling from a source to a destination. It is an
important traffic element used by many protocols and most
applications.
Managing flows requires a clear understanding of flow behavior and its
performance in real wireless networks. I will first present a
flow-level study based on traces collected from four real wireless
LANs. In this study, I use statistical modeling methods to
characterize both the temporal-domain and spatial-domain dynamics of
flows. I also demonstrate the usefulness of the characterization
results. I will then present results on characterizing the worst-case
flow performance under the unreliable wireless channel. A
game-theoretic approach is applied to devise a solution achieving the
optimal worst-case flow performance. At the end of the talk I will
summarize my current work and outline the future directions in
wireless networking research.
Bio
George Meng received his B.S. degree from University of Science and
Technology of China in 1998, and his M.S. degree from Institute of
Automation in Computer Science in 2001. He is currently a
Ph.D. candidate in UCLA Computer Science department. His research
interests include wireless networks, mobile computing, and sensor
networks.
Computational Foundations of Automatic Differentiation
Automatic, or algorithmic, differentiation is a technique for
transforming a program or subprogram that computes a mathematical
function into one that computes the derivatives of that function.
Successful implementation of automatic differentiation tools requires
research and development across a broad spectrum of computer science,
including graph theory, compilers, parallel algorithms, and numerical
analysis. We describe some of the computational foundations of
automatic differentiation, including graph-based heuristics for
identifying and exploiting common subexpressions, parallel numerical
algorithms, and domain-specific dataflow analysis problems. We
demonstrate the importance of accurate derivatives to numerical
algorithms. We also describe ongoing research in the design of
language-independent source transformation infrastructures and memory
management for automatic differentiation algorithms.
Incorporating Feature Hierarchies into Bayesian Network Learning
Bayesian networks can be used to provide a compact representation of a
joint probability distribution by capturing the dependency structure
among the variables, and can be inductively learned from data.
Context-specific independence representations, such as tree- structured
conditional probability tables (TCPTs), reduce the number of
parameters in Bayesian networks by capturing local independence
relationships. However, for applications that include discrete
variables with large domain sizes, the TCPTs can still grow quite
large.
In this talk, I will present joint research with Dr. Lise Getoor
(University of Maryland, College Park) on incorporating abstraction
value hierarchies into BN learning. The first method we developed,
Abstraction-Based Search (ABS), uses heuristic search to identify an
appropriate level of abstraction (value grouping) for a standard BN.
The second method, TCPT ABS, integrates ABS with TCPT learning.
Since expert-provided hierarchies may not be available, or may not
provide the most useful distinctions, I will also describe two
alternative clustering techniques for deriving hierarchies from data,
and will present results from three real-world domains.
Model Driven Engineering for Distributed Real-time and Embedded Systems
Some of the most challenging R&D problems are those associated with
producing software for distributed, real-time, and embedded (DRE)
systems, where computer processors control physical, chemical, or
biological processes or devices. Examples of such systems include
airplanes and air traffic control systems, automobiles, power grids, oil
refineries, and patient monitoring systems. Despite advances in
standards-based commercial-off-the-shelf (COTS) technologies, key
challenges must be addressed before COTS software can be used to build
mission-critical DRE systems effectively and productively. For example,
developers of DRE systems continue to use ad hoc means to develop,
configure, and deploy their applications and middleware due to the lack
of formally analyzable and verifiable building block components.
This talk will describe how Model Driven Engineering (MDE) techniques
and tools can be used to specify, analyze, optimize, synthesize,
validate, and deploy product-line architectures (PLAs) and
standards-compliant middleware platforms that can be customized for the
needs of next-generation DRE systems. Various model-based approaches
(e.g., MDE and MDA) will be compared and contrasted. The talk will also
show how MDE techniques and tools have been successfully combined with
standards-based QoS-enabled component middleware to develop PLAs that
significantly improve the quality and productivity associated with
developing next-generation mission-critical DRE systems. Concrete
examples from avionics, process control, software defined radios, and
warehouse management systems will be used to illustrate key points. The
talk will conclude with a survey of MDE technologies from researchers
and commercial tool providers.
Bio:
Dr. Douglas C. Schmidt is a Professor of Computer Science, Associate
Chair of the Computer Science and Engineering program, and a Senior
Researcher in the Institute for Software Integrated Systems (ISIS) all
at Vanderbilt University. He has published over 300 technical papers
and 6 books that cover a range of research topics, including patterns,
optimization techniques, and empirical analyses of software frameworks
and domain-specific modeling environments that facilitate the
development of distributed real-time and embedded (DRE) middleware and
applications running over high-speed networks and embedded system
interconnects. Dr. Schmidt has served as a Deputy Office Director and a
Program Manager at DARPA, where he led the national R&D effort on
middleware for DRE systems.
Darrell Whitley,
Department of Computer Science, CSU
Phil Farley, IBM Academic Initiative Team
Gautam, Computer Science Department, Colorado State University
for i = 0 to n {
Y[i] = -infinitity
for j = i to 2i {
for k = i to 3i-j {
Y[i] = max(Y[i], X[j,k])
}
}
}
Our compiler will generate a Theta(n2) implementation for this
specification. See if you can get it. This is joint work with my
advisor, Sanjay Rajopadhye. The first paper on this research
"Simplifying Reductions" was presented at POPL 2006. BTW, the ASiCS
group will take out to coffee whoever finds the optimization of the
given example.
Dr. Jan Juerjens, Senior Researcher, Software and Systems Engineering,
Department of Informatics, TU Munich, Germany.
Christos Papadopoulos, Department of Computer Science
Information Sciences Institute and Integrated Media Systems Center
University of Southern California
Joseph A. Zambreno
Department of Electrical and Computer Engineering
Northwestern University
Dan Brown, Cheriton School of Computer Science, University of Waterloo
Tomas Vinar, University of Waterloo
Xiaoqiao (George) Meng
Computer Science Department
University of California at Los Angeles
Paul Hovland, Argonne NL
Marie desJardins
University of Maryland Baltimore County
Department of Computer Science and Electrical Engineering
Dr. Douglas C. Schmidt, Vanderbilt University
d.schmidt@vanderbilt.edu