Graduate Research Conference 2005 -
Agenda
Department of Computer Science
Stony Brook University
Stony Brook, NY
11794-4400
10:00am - 5:30pm, Friday, April 22nd, 2005
1. Theory - 1306 Seminar Room: 10:00am - 12:00pm
- Theory of Computation
- Algorithms
- Logic, Artificial Intelligence, Machine Learning
- Special Topics: Natural Language Processing, Computational Biology,
Computational Geometry
Organizer: Paul Fodor
Session Chair: Dhyanesh Damania
Judge: Prof. Anita Wasilewska
Theory Presentation 1 - time: 10:00am - 10:20am
- Title: On the complexity of finding circumscribed rectangles and squares
of a Jordan curve
- Authors: Ker-I Ko, Fuxiang Yu (Presenter)
- Abstract: We consider in the real computation model of Ko
and Friedman the problem of finding a rectangle or square that circumscribes
about a Jordan curve. This problem is related to fixed point theory and root
theory. We prove that for a polynomial-time computable Jordan curve, the
complexity of finding a circumscribed square can be arbitrarily high. We also
show that the complexity of finding the minimal area or perimeter of the
circumscribed rectangles of a polynomial-time computable Jordan curve is
characterized by the complexity class $\Sigma_2^P$. These results and some
other related results build a link between geometry and the NP theory.
- Keywords: Complexity, Jordan curve, Circumscribed square, NP, Sigma_2^P.
- Link to the student webpage or the full content of the presentation:
Theory Presentation 2 - time: 10:20am - 10:40am (* Best Paper Award * )
- Title: Bounded Drift Iterated Snap Rounding
- Authors: Eli Packer
- Abstract: Snap Rounding and its varient, Iterated
Snap Rounding, are methods for converting
arbitrary-precision arrangements of segments into a fixed-precision
representation. Each induces an output which might be unacceptable for cerain cases. While in Snap Rounding the distance between a
vertex and a non-incident edge can be extremely small, inducing potential degeneracies, in Iterated Snap Rounding segments may drift
far from their origin. We propose a new method based on the above two, Bounded
Drift Iterated Snap Rounding, in which none of the above undesirable properties
hold. As a result, we are the first to propose an algorithm whose output
satisfies all the desirable properties discussed in the literature so far.
- Keywords: "computational geometry", "finite precision
approximation", "robust computation"
- Link to the student webpage or the full content of the presentation: http://www.cs.sunysb.edu/~epacker/
Theory Presentation 3 - time: 10:40am - 11:00am
- Title: Meta-analysis based on control of False Discovery Rate
- Authors: Saumyadipta Pyne,
Steve Skiena, Bruce Futcher
- Abstract: High-throughput technology such as microarrays
can be used to simultaneously examine thousands of features, such as all the
genes or regulatory sequences of an organism, and measure their expression
under various experimental conditions. Two common requirements of microarray bioinformatics at this point are of techniques
to combine the significance values for each feature across independent
analogous experiments with high power, as well as to control the proportion of
false positives among those features declared significant. In spite of the variety
of existing methods to address either issue, in general the two issues, with
dual requirements, are tackled independently and sequentially. We present a
novel algorithm to simultaneously address and integrate the two, and discuss
results due to its application.
- Keywords: Meta-analysis, False Discovery Rate, P-values, Microarrays
- Link to the student webpage or the full content of the presentation:
Theory Presentation 4 - time: 11:00am - 11:20am
- Title: Fast generation of DNA and protein motifs from profile matrices
- Authors: Paul Fodor, Joy Dutta, Steven
Skiena
- Abstract: A DNA profile matrix gives probability of each base appearing in
each position in a DNA sequence, so a length n profile matrix scores the
likelihood of each possible DNA sequence of length n. The protein profiles are similar, the only difference is that the alphabet size
varies with the number of different amino acids. Finding the most probable
sequence is trivial, but finding the second most or k-th
most probable sequence requires sorting 4n DNA sequences or 20n protein
sequences. This paper describes and implements a geometric algorithm based on
the zone theorem to provide a much faster alter-native to the brute force
method.
- Keywords: "computational biology", "DNA", "protein",
"motif", and "profile"
- Link to the student webpage or the full content of the presentation: http://www.algorithm.cs.sunysb.edu/compbio/motif/
2. Software - 2313A Conference Room: 10:00am -
12:30pm
- Programming Languages
- Compiler Design
- Database Systems and Web Services
- Graphics
- Special Topics: Verification
Organizer: Mohit Gupta
Session Chair: Amitabh Basu
Judge: Prof. CR Ramakrishnan
Software Presentation 1 - time: 10:00am - 10:20am (* Best Paper Award * )
- Title: Efficient Modeling of Excitable Cells Using Hybrid Automata
- Authors: Pei Ye, Dept. of Computer Science, Stony
Brook Univ. , Emilia Entcheva,
Dept. of Biomedical Engineering, Stony Brook Univ., Radu
Grosu, Dept. of Computer Science, Stony Brook Univ. ,
Scott A. Smolka, Dept. of Computer Science, Stony
Brook Univ.
- Abstract: We present an approach to modeling complex biological systems that
is based on Hybrid automata (HA). HA combine discrete transition graphs with
continuous dynamics. Our goal is to efficiently capture the behavior of
excitable cells previously modeled by systems of nonlinear differential
equations. In particular, we derive HA models from the Hodgkin-Huxley model of
the giant squid axon, the Luo-Rudy dynamic model of a
guinea pig ventricular cell, and a model of a neonatal rat ventricular myocyte. Our much simpler HA models are able to
successfully capture the action-potential morphology of the different cells, as
well as reproduce typical excitable cell characteristics, such as
refractoriness (period of non-responsiveness to external stimulation) and
restitution (adaptation to pacing rates). To model electrical wave propagation
in a cell network, the single-cell HA models are linked to a classical 2D
spatial model. The resulting simulation framework exhibits significantly
improved computational efficiency in modeling complex wave patterns, such as
the spiral waves underlying pathological conditions in the heart.
- Keywords: Hybrid Automata, Action Potential, restitution.
- Link to the student webpage or the full content of the presentation: http://www.cs.sunysb.edu/~pye/CMSB05.pdf
Software Presentation 2 - time: 10:20am - 10:40am
- Title: Static Analysis of Atomicity for Programs with Lock-Free
Synchronization
- Authors: Liqiang Wang, Scott D. Stoller
- Abstract: In concurrent programming, lock-free synchronization is very
efficient but difficult to design correctly. This paper presents a static
analysis to show that code blocks are atomic, i.e., that every execution of the
program is equivalent to one in which those code blocks execute without
interruption by other threads. Our analysis determines commutativity
of operations based primarily on how synchronization primitives (including
locks, load-linked, store-conditional, and compare-and-swap) are used. A
reduction theorem states that certain patterns of commutativity
imply atomicity. Atomicity is itself an important correctness requirement for
many concurrent programs. Furthermore, an atomic code block can be treated as a
single transition during subsequent analysis of the program; this can greatly
improve the efficiency of the subsequent analysis. We demonstrate the
effectiveness of our approach on several concurrent lock-free programs.
- Keywords: Atomicity, Lock-free, Non-blocking, Synchronization, Static
Analysis, Verification, Linearizability.
- Link to the student webpage or the full content of the presentation: http://www.cs.sunysb.edu/~liqiang/lockfree.html
Software Presentation 3 - time: 10:40am - 11:00am
- Title: Conformal Colon Flattening
- Authors: Wei Hong, Xianfeng
Gu, Feng
Qiu, Arie Kaufman
- Abstract: We present an efficient colon flattening algorithm using conformal
mapping, which is angle-preserving and the global distortion is minimized. The
colon wall is segmented and extracted from the CT dataset first. The minuet
handles are located and removed automatically. Moreover, our algorithm can
handle high genus surfaces. Each vertex on the 3D colon surface is registered
with a camera on the central path. The flattened colon image is then rendered
using a direct volume rendering method accelerated with the GPU. Our algorithm
is tested with a number of CT datasets of real pathological cases. We
demonstrated the shape of the polyps is well preserved on the flattened colon
images, which provides an efficient way to enhance the fly-through virtual
colonoscopy system.
- Keywords: Conformal Mapping, Direct Volume Rendering, Virtual Colonoscopy
- Link to the student webpage or the full content of the presentation:
Software Presentation 4 - time: 11:00am - 11:20am
- Title: Answering Rule-Based Queries Efficiently with Complexity
Guarantees
- Authors: Katia Hristova,
Annie Liu
- Abstract: Many practical problems that may be difficult to understand and
implement otherwise can conveniently and intuitively be expressed using rules.
However, answering queries based on the rules efficiently with complexity
guarantees has been a major challenge. In particular, existing implementations
can have dramatically different running times depending on the order of rules
or the order of hypotheses in a rule. We propose a method that combines magic
set transformation and formal complexity analysis to automatically provide time
complexity guarantees for answering queries efficiently, regardless of the
orders of rules or hypotheses, and we apply the method to RBAC (role-based
access control) and a Trust Management system for electronic health records.
- Keywords: Datalog, complexity analysis, security
policy
- Link to the student webpage or the full content of the presentation:
Software Presentation 5 - time: 11:20am - 11:40am
- Title: Automated Type-Based Analysis of Data Races and Atomicity
- Authors: Amit Sasturkar
- Abstract: Concurrent programs are notorious for containing errors that are
difficult to reproduce and diagnose at run-time. This motivated the development
of type systems that statically ensure the absence of some common kinds of
concurrent programming errors. This paper presents Extended Parameterized
Atomic Java (EPAJ), a type system for specifying and verifying atomicity of
methods in multi-threaded Java programs. Atomicity is a common correctness
requirement for concurrent programs which requires that concurrent invocations
of a set of methods be equivalent to performing the invocations serially in
some order. EPAJ combines Flanagan and Qadeer's
atomicity types with a new and significantly more expressive type system for
analyzing data races, called Extended Parameterized Race-Free Java (EPRFJ),
allowing a more accurate analysis of atomicity. The paper also presents a type
discovery algorithm to automatically obtain EPRFJ types, and a static interprocedural type inference algorithm that, given EPRFJ
types, infers atomicity types. These algorithms can be incorporated into
testing and debugging tools, benefiting users who know nothing about type
systems. We report our experience with a prototype implementation.
- Keywords: Data Races, Atomicity, Type Systems, Type inference
- Link to the student webpage or the full content of the presentation: http://www.cs.sunysb.edu/~amits/papers/atomicity-inference/
Software Presentation 6 - time: 11:40am - 12:00am
- Title: Incremental Points-To Analysis using logic programming
- Authors: Diptikalyan Saha,
C. R. Ramakrishnan
- Abstract: Several program analysis problems can be cast elegantly as a logic
program. In this paper we show how recently-developed techniques for
incremental evaluation of logic programs can be refined and used for deriving
practical implementations of incremental program analyzers. Incremental program
analyzers compute the changes to the analysis information due to small changes
in the input program rather than re-analyzing the program. We show the
effectiveness of this approach by building a practical
incremental context insensitive points-to analysis and evaluating this
implementation for analyzing C programs with 10-70K lines of code. Experiments
show that our technique can compute the changes to analysis information due to
small changes in the input program in, on the average, 6\% of the time it takes
to reanalyze the program from scratch, and with little space overhead.
- Keywords:
- Link to the student webpage or the full content of the presentation: http://www.lmc.cs.sunysb.edu/~dsaha/ppdp05.ps
3. Systems - 2311 Wireless Seminar Room:
Session 1: (10:00am - 12:30pm)
Topic: Wireless Networks
Organizer: Ritesh Maheshwari
Session Chair: Srikant Sharma
Judge: Prof. Tzi-cker Chiueh
Presentation 1 - Time: 10:00am - 10:20am
- Title: Beneficial Caching in Wireless Ad Hoc Networks
- Authors: Bin Tang, Samir Das, Himanshu
Gutpa
- Abstract: In this paper we propose and design a benefit-based
caching paradigm for wireless ad hoc networks. We start by designing a
centralized algorithm in static network with provable bound under memory
constraint of each node. We then implement it in a distributed manner and show
it has a very close performance to the centralized one. Finally, we compare our
algorithm with the latest published work in mobile environment. We first show
that our proposed caching paradigm is more general and it can be easily
extended into the peer-to-peer domain. Then, through extensive simulations in
$ns2$, we show our scheme performs better in some range of parameters.
- Keywords: caching, ad hoc networks, algorithms
- Link to the student webpage or the full content of the
presentation: http://www.cs.sunysb.edu/~bintang/papers/cache.pdf
Presentation 2 - Time: 10:20am - 10:40am
- Title: Solving Deafness and Directional Hidden Terminal Problem in
Wireless Multihop networks using Directional Antennas
- Authors: Anand Prabhu Subramanian, Samir Das
- Abstract: The capacity of Wireless Multihop
Networks is highly limited because the wireless channel is a shared one and a
single transmission along a multihop path can inhibit
a large number of nearby nodes. This is mainly due to the omnidirectional
transmission that reserves a large region of space, while only a small portion
of it is used for the communication. Other nodes defer their communication as
they are exposed to this transmission. Directional Antenna is a technology that
solves this problem and has a great potential to increase the capacity of multihop networks. Though directional antennas offer many
benefits such as spatial reuse, coverage range, better link reliability and
increase in network capacity, there are some tradeoffs that need to be
addressed. Deafness and directional hidden terminal problem are two such
problems that have a serious effect on network performance when left
unaddressed. Deafness occurs when a transmitter fails to communicate to its
intended receiver, because the receiver’s antenna is oriented in a
different direction. The hidden terminal problem occurs when the transmitter
failed to hear the RTS/CTS exchange between another pair of nodes and cause
collision by initiating a transmission to the receiver node of the ongoing
communication. Existing directional MAC protocols try to solve deafness but the
directional hidden terminal problem is left unaddressed. In this paper, we
present a novel directional MAC protocol that uses a single transceiver and a
single channel and effectively solves both deafness and directional hidden
terminal problem. In this scheme, we transmit the RTS and CTS packets omnidirectionally with the directional information about
the following data transmission which is done directionally. Instead of
transmitting RTS/CTS and data packets alternatively, we transmit a series of
RTS/CTS packets in a control window before multiple simultaneous data
transmissions take place in different directions. The length of the control
window can be adaptively adjusted based on the traffic information to allow
multiple data transmission simultaneously in different directions. Keywords: Directional Antenna, Control Window, Deafness, Hidden
Terminal Problem
Presentation 3 - Time: 10:40am - 11:00am (* Best Paper Award * )
- Title: Directional Antennas in Ad Hoc Networks
- Authors: Umesh Kumar
- Abstract: Most of the previous research on directional
antennas in ad hoc networks assumes nodes have sufficient directional antennas
(or an omni directional antenna) to cover all directions simultaneously. In
this paper we consider networks where nodes maynot
have enough directional antennas to cover all directions simultaneously. This
may be caused due to antenna failures or deployment decisions (e.g monetary reasons). We slightly modify the approximation
algorithms proposed in the literature for minimum degree spanning tree problem
to determine whether the network can be connected with the available
directional antennas at each node. We observe that even with the 3 antennas
network is almost always connected ( more than 99.99\% times) and then evaluate
how the performance of the network depends on the number and beamwidth of antenna's at each node using Qualnet simulator.
- Link to the student webpage or the full content of the
presentation: http://www.wings.cs.sunysb.edu/~umesh
Presentation 4 - Time: 11:00am - 11:20am
- Title: Fault Tolerant Connected Sensor Cover with Variable Sensing
and Transmission Ranges
- Authors: Zongheng Zhou,
Samir R. Das, Himanshu Gupta
- Abstract: Sensor networks are often deployed in a redundant
fashion. In order to prolong the network lifetime, it is desired to choose only
a subsetof sensors to keep active and put the rest to
sleep. In order to provide fault tolerance, this small subset of active sensors
should also provide some degree of redundancy. In this paper, we consider the
problem of choosing a minimum subset of sensors such that they maintain a
required degree of coverage and also form a connected network with a required
degree of fault tolerance. In addition, we consider a more general, variable
radii sensor model, wherein every sensor can adjust both its sensing and
transmission ranges to minimize overall energy consumption in the network. We
call this the variable radii $k_1$-Connected, $k_2$-Cover problem. To address
this problem, we propose a distributed and localized Voronoi-based
algorithm. The approach extends the relative neighborhood graph (RNG) structure
to preserve $k$-connectivity in a graph, and design a distributed technique to
inactivate desirable nodes while preserving $k$-connectivity of the remaining
active nodes. We show through extensive simulations that our proposed
techniques result in overall energy savings in random sensor networks over a
wide range of experimental parameters.
- Keywords: Sensor Network; Sensor Coverage;
Topology Control;
Presentation 5 - Time: 11:20am - 11:40am
- Title: Fault-Tolerant Manycast to
Mobile Destinations in Sensor Network
- Authors: Xianjin Zhu, Himanshu
Gupta
- Abstract: Manycast is a group communication
primitive wherein the source is required to send a data packet to a certain
number/percentage of a given set of destinations. In this article, we design
fault-tolerant protocols for the manycast operation
in sensor networks when the given set of destinations are
mobile. To develop efficient protocols, we propose a distributed location
management scheme, which manages information about the location of mobile
destinations in a distributed manner. Using the proposed location management
scheme, we develop various fault-tolerant manycast
routing protocols to reach the required number of destinations. First, we
propose the rectangular-based manycast protocols
using two routing schemes viz. rectangle flooding and GeoGrid-based
routing. In addition, we develop a GridTree technique
which is based upon developing fault-tolerant paths between adjacent nodes in
an appropriately constructed geometric tree. We evaluate the performance of our
designed techniques through extensive simulations.
Session 2: (2:00pm - 3:20pm)
Topics: P2P Networks, Security, File Systems
Organizer: Abhishek Rai
Session Chair: Ma Chi
Judge: Prof Himanshu Gupta
Presentation 1 - Time: 2:00pm - 2:20pm
- Title: One-way Isolation: An Effective Approach for Realizing Safe
Execution Environments
- Authors: Weiqing Sun, Zhenkai
Liang, R. Sekar and V.N. Venkatakrishnan
- Abstract:In this paper, we present an approach for realizing a safe
execution environment (SEE) that enables users to "try out" new
software (or configuration changes to existing software) without the fear of
damaging the system in any manner. A key property of our SEE is that it
faithfully reproduces the behavior of applications, as if they were running
natively on the underlying host operating system. This is accomplished via
one-way isolation: processes running within the SEE are given read-access to
the environment provided by the host OS, but their write operations are
prevented from escaping outside the SEE. As a result, SEE processes cannot
impact the behavior of host OS processes, or the integrity of data on the host
OS. Our SEE supports a wide range of tasks, including: study of malicious code,
controlled execution of untrusted software, experimentation with software
configuration changes, testing of software patches, and so on. It provides a
convenient way for users to inspect system changes made within the SEE. If the
user does not accept these changes, they can be rolled back at the click of a
button. Otherwise, the changes can be "committed" so as to become
visible outside the SEE. We provide consistency criteria that ensure semantic
consistency of the committed results. We also develop an efficient technique
for implementing the commit operation. Our implementation results show that
most software, including fairly complex server and client applications, can run
successfully within the SEE. The approach introduces low performance overheads,
typically below 10%.
- Keywords: Security, one-way Isolation, SEE.
- Link to the student webpage or the full content of the
presentation: Not available
Presentation 2 - Time: 2:20pm -
2:40pm (* Best Paper Award * )
- Title: An Efficient and Backwards-Compatible Transformation to
Ensure Memory Safety of C Programs
- Authors: Wei Xu, Daniel C. DuVarney,
and R. Sekar
- Abstract:Memory-related errors, such as buffer overflows and
dangling pointers, remain one of the principal reasons for failures of C
programs. As a result, a number of recent research efforts have focused on the
problem of dynamic detection of memory errors in C programs. However, existing
approaches suffer from one or more of the following problems: inability to
detect all memory errors (e.g., Purify), requiring non-trivial modifications to
existing C programs (e.g., Cyclone), changing the memory management model of C
to use garbage collection (e.g., CCured), and excessive performance overheads.
In this paper, we present a new approach that addresses these problems. Our
approach operates via source code transformation and combines efficient
data-structures with simple, localized optimizations to obtain good
performance.
- Keywords:Memory Safety, C, Program Transformation.
- Link to the student webpage or the full content of the
presentation: http://seclab.cs.sunysb.edu/seclab/pubs/papers/fse04.pdf
A Pairwise Currency Mechanism for Streaming in
Non-Cooperative Environments
Presentation 3 - Time: 2:40pm - 3:00pm
- Title: A Pairwise Currency Mechanism for Streaming in
Non-Cooperative Environments
- Authors: Vinay Pai, Kapil
Kumar, Alexander E. Mohr
- Abstract:We investigate whether the application of a pairwise currency
mechanism to mesh-based multicast overlay networks can give incentives to peers
to contribute to the system, but at the same time maintain short propagation
delays. Whereas traditional tree-based multicast systems are not amenable to
pairwise currency mechanisms, we find that pairwise currency can be used to
good effect in these newly developed unstructured mesh-based overlay multicast
systems. This combination results in a simple, lightweight system in which only
local state must be maintained. Through simulations and real-world experiments
on PlanetLab, we show that nodes with upload to download ratios less than 1.0
are penalized by their neighbors and suffer significant packet loss, but nodes
with ratios greater than 1.0 have minimal packet loss. Moreover, we show that
when there are altruistic nodes willing to contribute their excess bandwidth to
the system, it is feasible to accommodate nodes with limited upload capacity,
such as ADSL users, and allow them to download without packet loss as well.
- Keywords:p2p, overlay multicast, incentives
- Link to the student webpage or the full content of the
presentation: Not available
Presentation 4 - Time: 3:00pm - 3:20pm
- Title: Self-Optimizing OS Debugging: The
Monte Carlo Approach
- Authors: Sean Callanan (presenter), Radu
Grosu, Abhishek Rai (presenter), Scott Smolka, Mike True, Erez Zadok,
- Abstract:Large software is complex to debug, especially when
it runs for long periods of time under production load, like an operating
system kernel. Developers can include debugging with such software; however,
debugging instrumentation often incurs overheads. Therefore, developers run
their software in debugging mode for limited periods of time, and then release
the software without debugging support. This leaves software vulnerable to those
bugs that only appear after prolonged real-world use. We have developed a
dynamic-analysis system that provides the best of both worlds: always include
debugging instrumentation in commercially- shipped software, while reducing
overheads by selectively turning off instrumentations at run-time.
Our system includes a kernel-specific compiler (KGCC) which instruments
arbitrary parts of the kernel with checks against invariants. A novel
Monte-Carlo model-checking algorithm which we developed estimates the confidence
that a certain invariant holds. When the confidence exceeds a threshold, the
inline monitoring instrumentation is turned off. Confidence for
frequently-executed portions of the code will be accrued the fastest, leading
to the rapid deactivation of instrumentation for those sections, which in turn
restores performance to non-instrumented levels quickly.
- Keywords:Linux, debugging, instrumentation, model checking
- Link to the student webpage or the full content of the
presentation: http://www.fsl.cs.sunysb.edu/~sean,
http://www.fsl.cs.sunysb.edu/~abba