Computer Sciences Commons^™

Dependency Management In Distributed Settings (Poster Abstract), Guanling Chen, David Kotz

Dartmouth Scholarship

Ubiquitous-computing environments are heterogeneous and volatile in nature. Systems that support ubicomp applications must be self-managed, to reduce human intervention. In this paper, we present a general service that helps distributed software components to manage their dependencies. Our service proactively monitors the liveness of components and recovers them according to supplied policies. Our service also tracks the state of components, on behalf of their dependents, and may automatically select components for the dependent to use based on evaluations of customized functions. We believe that our approach is flexible and abstracts away many of the complexities encountered in ubicomp environments. In …

Simulation Validation Using Direct Execution Of Wireless Ad-Hoc Routing Protocols, Jason Liu, Yougu Yuan, David M. Nicol, Robert S. Gray, Calvin C. Newport, David Kotz, Luiz Felipe Perrone

Dartmouth Scholarship

Computer simulation is the most common approach to studying wireless ad-hoc routing algorithms. The results, however, are only as good as the models the simulation uses. One should not underestimate the importance of \em validation, as inaccurate models can lead to wrong conclusions. In this paper, we use direct-execution simulation to validate radio models used by ad-hoc routing protocols, against real-world experiments. This paper documents a common testbed that supports direct execution of a set of ad-hoc routing protocol implementations in a wireless network simulator. The testbed reads traces generated from real experiments, and uses them to drive direct-execution implementations …

The Kerf Toolkit For Intrusion Analysis, Javed Aslam, Sergey Bratus, David Kotz, Ron Peterson, Daniela Rus, Brett Tofel

Computer Science Technical Reports

We consider the problem of intrusion analysis and present the Kerf Toolkit, whose purpose is to provide an efficient and flexible infrastructure for the analysis of attacks. The Kerf Toolkit includes a mechanism for securely recording host and network logging information for a network of workstations, a domain-specific language for querying this stored data, and an interface for viewing the results of such a query, providing feedback on these results, and generating new queries in an iterative fashion. We describe the architecture of Kerf, present examples to demonstrate the power of our query language, and discuss the performance of our …

A Subgroup Algorithm To Identify Cross-Rotation Peaks Consistent With Non-Crystallographic Symmetry, Ryan H. Lilien, Chris Bailey-Kellogg, Amy C. Anderson, Bruce R. Donald

Dartmouth Scholarship

Molecular replacement (MR) often plays a prominent role in determining initial phase angles for structure determination by X-ray crystallography. In this paper, an efficient quaternion-based algorithm is presented for analyzing peaks from a cross-rotation function in order to identify model orientations consistent with proper non-crystallographic symmetry (NCS) and to generate proper NCS-consistent orientations missing from the list of cross-rotation peaks. The algorithm, CRANS, analyzes the rotation differences between each pair of cross-rotation peaks to identify finite subgroups. Sets of rotation differences satisfying the subgroup axioms correspond to orientations compatible with the correct proper NCS. The CRANS algorithm was first …

The Changing Usage Of A Mature Campus-Wide Wireless Network, Tristan Henderson, David Kotz, Ilya Abyzov

Computer Science Technical Reports

Wireless Local Area Networks (WLANs) are now common on academic and corporate campuses. As ``Wi-Fi'' technology becomes ubiquitous, it is increasingly important to understand trends in the usage of these networks. This paper analyzes an extensive network trace from a mature 802.11 WLAN, including more than 550 access points and 7000 users over seventeen weeks. We employ several measurement techniques, including syslogs, telephone records, SNMP polling and tcpdump packet sniffing. This is the largest WLAN study to date, and the first to look at a large, mature WLAN and consider geographic mobility. We compare this trace to a trace taken …

Parallel Out-Of-Core Sorting: The Third Way, Geeta Chaudhry

Dartmouth College Ph.D Dissertations

Sorting very large datasets is a key subroutine in almost any application that is built on top of a large database. Two ways to sort out-of-core data dominate the literature: merging-based algorithms and partitioning-based algorithms. Within these two paradigms, all the programs that sort out-of-core data on a cluster rely on assumptions about the input distribution. We propose a third way of out-of-core sorting: oblivious algorithms. In all, we have developed six programs that sort out-of-core data on a cluster. The first three programs, based completely on Leighton's columnsort algorithm, have a restriction on the maximum problem size that they …

Identification Of Novel Small Molecule Inhibitors Of Core-Binding Factor Dimerization By Computational Screening Against Nmr Molecular Ensemble, Ryan H. Lilien, Mohini Sridharan, Bruce R. Donald

Computer Science Technical Reports

The long development process of novel pharmaceutical compounds begins with the identification of a lead inhibitor compound. Computational screening to identify those ligands, or small molecules, most likely to inhibit a target protein may benefit the pharmaceutical development process by reducing the time required to identify a lead compound. Typically, computational ligand screening utilizes high-resolution structural models of both the protein and ligand to fit or `dock' each member of a ligand database into the binding site of the protein. Ligands are then ranked by the number and quality of interactions formed in the predicted protein-ligand complex. It is currently …

A Meeting Detector And Its Applications, Jue Wang, Guanling Chen, David Kotz

Computer Science Technical Reports

In this paper we present a context-sensing component that recognizes meetings in a typical office environment. Our prototype detects the meeting start and end by combining outputs from pressure and motion sensors installed on the chairs. We developed a telephone controller application that transfers incoming calls to voice-mail when the user is in a meeting. Our experiments show that it is feasible to detect high-level context changes with ``good enough'' accuracy, using low-cost, off-the-shelf hardware, and simple algorithms without complex training. We also note the need for better metrics to measure context detection performance, other than just accuracy. We propose …

Dependency Management In Distributed Settings, Guanling Chen, David Kotz

Computer Science Technical Reports

Ubiquitous-computing environments are heterogeneous and volatile in nature. Systems that support ubicomp applications must be self-managed, to reduce human intervention. In this paper, we present a general service that helps distributed software components to manage their dependencies. Our service proactively monitors the liveness of components and recovers them according to supplied policies. Our service also tracks the state of components, on behalf of their dependents, and may automatically select components for the dependent to use based on evaluations of customized functions. We believe that our approach is flexible and abstracts away many of the complexities encountered in ubicomp environments. In …

Evaluating Location Predictors With Extensive Wi-Fi Mobility Data, Libo Song, David Kotz, Ravi Jain, Xiaoning He

Dartmouth Scholarship

Location is an important feature for many applications, and wireless networks can better serve their clients by anticipating client mobility. As a result, many location predictors have been proposed in the literature, though few have been evaluated with empirical evidence. This paper reports on the results of the first extensive empirical evaluation of location predictors, using a two-year trace of the mobility patterns of over 6,000 users on Dartmouth's campus-wide Wi-Fi wireless network. \par We implemented and compared the prediction accuracy of several location predictors drawn from two major families of domain-independent predictors, namely Markov-based and compression-based predictors. We found …

Keyjacking: The Surprising Insecurity Of Client-Side Ssl, John Marchesini, S W. Smith, Meiyuan Zhao

Computer Science Technical Reports

In theory, PKI can provide a flexible and strong way to authenticate users in distributed information systems. In practice, much is being invested in realizing this vision via client-side SSL and various client keystores. However, whether this works depends on whether what the machines do with the private keys matches what the humans think they do: whether a server operator can conclude from an SSL request authenticated with a user's private key that the user was aware of and approved that request. Exploring this vision, we demonstrate via a series of experiments that this assumption does not hold with standard …

A Case Study Of Four Location Traces, Guanling Chen, David Kotz

Computer Science Technical Reports

Location is one of the most important context information that an ubiquitous-computing application may leverage. Thus understanding the location systems and how location-aware applications interact with them is critical for design and deployment of both the location systems and location-aware applications. In this paper, we analyze a set of traces collected from two small-scale one-building location system and two large-scale campus-wide location systems. Our goal is to study characteristics of these location systems ant how these factors should be taken into account by a potentially large number of location-aware applications with different needs. We make empirical measurements of several important …

Application-Controlled Loss-Tolerant Data Dissemination, Guanling Chen, David Kotz

Computer Science Technical Reports

Reactive or proactive mobile applications require continuous monitoring of their physical and computational environment to make appropriate decisions in time. These applications need to monitor data streams produced by sensors and react to changes. When mobile sensors and applications are connected by low-bandwidth wireless networks, sensor data rates may overwhelm the capacity of network links or of the applications. In traditional networks and distributed systems, flow-control and congestion-control policies either drop data or force the sender to pause. When the data sender is sensing the physical environment, however, a pause is equivalent to dropping data. Arbitrary data drops are not …

Greenpass: Flexible And Scalable Authorization For Wireless Networks, Sean Smith, Nicholas C. Goffee, Sung Hoon Kim, Punch Taylor, Meiyuan Zhao, John Marchesini

Computer Science Technical Reports

Wireless networks break the implicit assumptions that supported authorization in wired networks (that is: if one could connect, then one must be authorized). However, ensuring that only authorized users can access a campus-wide wireless network creates many challenges: we must permit authorized guests to access the same network resources that internal users do; we must accommodate the de-centralized way that authority flows in real universities; we also must work within standards, and accommodate the laptops and systems that users already have, without requiring additional software or plug-ins.

This paper describes our ongoing project to address this problem, using SPKI/SDSI delegation …

Access Control In A Distributed Decentralized Network: An Xml Approach To Network Security Using Xacml And Saml, Paul J. Mazzuca

Dartmouth College Undergraduate Theses

The development of eXtensible Distributed Access Control (XDAC) systems is influenced by the transference of data access and storage from the local computer to the network. In this distributed system, access control is determined by independent components which transmit requests and decisions over a network, utilizing XML signing capabilities found in the Security Assertion Markup Language (SAML). All resources in the XDAC system are protected by the first component, a Policy Enforcement Point (PEP), which acts as the main divider between the requesting entity and the requested resource. The PEP grants access to a resource only if the second component, …

Using Spki/Sdsi For Distributed Maintenance Of Attribute Release Policies In Shibboleth, Sidharth Nazareth, Sean W. Smith

Computer Science Technical Reports

The Shibboleth middleware from Internet2 provides a way for users at higher-education institutions to access remote electronic content in compliance with the inter-institutional license agreements that govern such access. To protect end-user privacy, Shibboleth permits users to construct attribute release policies that control what user credentials a given content provider can obtain. However, Shibboleth leaves unspecified how to construct these policies. To be effective, a solution needs to accommodate the typical nature of a university: a set of decentralized fiefdoms. This need argues for a public-key infrastructure (PKI) approach---since public-key cryptography does not require parties to agree on a secret …

Experimenting With Tcpa/Tcg Hardware, Or: How I Learned To Stop Worrying And Love The Bear, John Marchesini, Sean Smith, Omen Wild, Rich Macdonald

Computer Science Technical Reports

Over the last few years, our group has been working on applications of secure coprocessors---but has been frustrated by the limited computational environment and high expense of such devices. Over the last few years, the TCPA (now TCG) has produced a specification for a trusted platform module (TPM)---a small hardware addition intended to improve the overall security of a larger machine (and tied up with a still-murky vision of Windows-based trusted computing). Some commodity desktops now come up with these TPMs. Consequently, we began an experiment to see if (in the absence of a Non-Disclosure Agreement) we could use this …

A Subgroup Algorithm To Identify Cross-Rotation Peaks Consistent With Non-Crystallographic Symmetry, Ryan H. Lilien, Chris Bailey-Kellogg, Amy C. Anderson, Bruce R. Donald

Computer Science Technical Reports

Molecular replacement (MR) often plays a prominent role in determining initial phase angles for structure determination by X-ray crystallography. In this paper, an efficient quaternion-based algorithm is presented for analyzing peaks from a cross-rotation function to identify model orientations consistent with non-crystallographic symmetry (NCS), and to generate NCS-consistent orientations missing from the list of cross-rotation peaks. Our algorithm, CRANS, analyzes the rotation differences between each pair of cross-rotation peaks to identify finite subgroups of NCS. Sets of rotation differences satisfying the subgroup axioms correspond to orientations compatible with the correct NCS. The CRANS algorithm was first tested using cross-rotation peaks …

On The Complexity Of Implementing Certain Classes Of Shared Objects, King Yang Tan

Dartmouth College Ph.D Dissertations

We consider shared memory systems in which asynchronous processes cooperate with each other by communicating via shared data objects, such as counters, queues, stacks, and priority queues. The common approach to implementing such shared objects is based on locking: To perform an operation on a shared object, a process obtains a lock, accesses the object, and then releases the lock. Locking, however, has several drawbacks, including convoying, priority inversion, and deadlocks. Furthermore, lock-based implementations are not fault-tolerant: if a process crashes while holding a lock, other processes can end up waiting forever for the lock.

Wait-free linearizable implementations were conceived …

A Probability-Based Similarity Measure For Saupe Alignment Tensors With Applications To Residual Dipolar Couplings In Nmr Structural Biology, Anthony K. Yan, Christopher J. Langmead, Bruce Randall Donald

Computer Science Technical Reports

High-throughput NMR structural biology and NMR structural genomics pose a fascinating set of geometric challenges. A key bottleneck in NMR structural biology is the resonance assignment problem. We seek to accelerate protein NMR resonance assignment and structure determination by exploiting a priori structural information. In particular, a method known as Nuclear Vector Replacement (NVR) has been proposed as a method for solving the assignment problem given a priori structural information [24,25]. Among several different kinds of input data, NVR uses a particular type of NMR data known as residual dipolar couplings (RDCs). The basic physics of residual dipolar couplings tells …

Mobicom Poster: Evaluating Location Predictors With Extensive Wi-Fi Mobility Data, Libo Song, David Kotz, Ravi Jain, Xiaoning He

Dartmouth Scholarship

A fundamental problem in mobile computing and wireless networks is the ability to track and predict the location of mobile devices. An accurate location predictor can significantly improve the performance or reliability of wireless network protocols, the wireless network infrastructure itself, and many applications in pervasive computing. These improvements lead to a better user experience, to a more cost-effective infrastructure, or both. Location prediction has been proposed in many areas of wireless cellular networks as a means of enhancing performance, including better mobility management, improved assignment of cells to location areas, more efficient paging, and call admission control. To the …

High-Throughput 3d Homology Detection Via Nmr Resonance Assignment, Christopher James Langmead, Bruce Randall Donald

Computer Science Technical Reports

One goal of the structural genomics initiative is the identification of new protein folds. Sequence-based structural homology prediction methods are an important means for prioritizing unknown proteins for structure determination. However, an important challenge remains: two highly dissimilar sequences can have similar folds --- how can we detect this rapidly, in the context of structural genomics? High-throughput NMR experiments, coupled with novel algorithms for data analysis, can address this challenge. We report an automated procedure, called HD, for detecting 3D structural homologies from sparse, unassigned protein NMR data. Our method identifies 3D models in a protein structural database whose geometries …

An Improved Nuclear Vector Replacement Algorithm For Nuclear Magnetic Resonance Assignment, Christopher James Langmead, Bruce Randall Donald

Computer Science Technical Reports

We report an improvement to the Nuclear Vector Replacement (NVR) algorithm for high-throughput Nuclear Magnetic Resonance (NMR) resonance assignment. The new algorithm improves upon our earlier result in terms of accuracy and computational complexity. In particular, the new NVR algorithm assigns backbone resonances without error (100% accuracy) on the same test suite examined in [Langmead and Donald J. Biomol. NMR 2004], and runs in $O(n^{5/2} \log {(cn)})$ time where $n$ is the number of amino acids in the primary sequence of the protein, and $c$ is the maximum edge weight in an integer-weighted bipartite graph.

Bear: An Open-Source Virtual Secure Coprocessor Based On Tcpa, Rich Macdonald, Sean Smith, John Marchesini, Omen Wild

Computer Science Technical Reports

This paper reports on our ongoing project to use TCPA to transform a desktop Linux machine into a virtual secure coprocessor: more powerful but less secure than higher-end devices. We use TCPA hardware and modified boot loaders to protect fairly static components, such as a trusted kernel; we use an enforcer module---configured as Linux Security Module---to protected more dynamic system components; we use an encrypted loopback filesystem to protect highly dynamic components. All our code is open source and available under GPL from http://enforcer.sourceforge.net/

Formal Properties Of Linear Memory Types, Heng Huang, Lea Wittie, Chris Hawblitzel

Computer Science Technical Reports

Efficient low-level systems need more control over memory than safe high-level languages usually provide. As a result, run-time systems are typically written in unsafe languages such as C. This report describes an abstract machine designed to give type-safe code more control over memory. It includes complete definitions and proofs of preservation, progress, strong normalization, erasure, and translation correctness.

Using Caching For Browsing Anonymity, Anna M. Shubina, Sean W. Smith

Computer Science Technical Reports

Privacy-providing tools, including tools that provide anonymity, are gaining popularity in the modern world. Among the goals of their users is avoiding tracking and profiling. While some businesses are unhappy with the growth of privacy-enhancing technologies, others can use lack of information about their users to avoid unnecessary liability and even possible harassment by parties with contrary business interests, and to gain a competitive market edge. Currently, users interested in anonymous browsing have the choice only between single-hop proxies and the few more complex systems that are available. These still leave the user vulnerable to long-term intersection attacks. In this …

The Mistaken Axioms Of Wireless-Network Research, David Kotz, Calvin Newport, Chip Elliott

Computer Science Technical Reports

Most research on ad-hoc wireless networks makes simplifying assumptions about radio propagation. The ``Flat Earth'' model of the world is surprisingly popular: all radios have circular range, have perfect coverage in that range, and travel on a two-dimensional plane. CMU's ns-2 radio models are better but still fail to represent many aspects of realistic radio networks, including hills, obstacles, link asymmetries, and unpredictable fading. We briefly argue that key ``axioms'' of these types of propagation models lead to simulation results that do not adequately reflect real behavior of ad-hoc networks, and hence to network protocols that may not work well …

Investigation Of Third Party Rights Service And Shibboleth Modification To Introduce The Service, Sanket Agrawal

Dartmouth College Master’s Theses

Shibboleth is an architecture to support inter-institutional sharing of electronic resources that are subject to access control. Codifying copyright in Shibboleth authorization policies is difficult because of the copyright exceptions which can be highly subjective. Third Party Rights Service is a high-level concept that has been suggested as a solution to approximate the exceptions of copyright law. In this thesis, I investigate the components of the Third Party Rights Service. I design and analyze a modified Shibboleth architecture based on these components. The resulting architecture allows for the phased addition of the resources to make use of the Third Party …

Discrete-Event Fluid Modeling Of Background Tcp Traffic, David M. Nicol, Guanhua Yan

Computer Science Technical Reports

TCP is the most widely used transport layer protocol used in the internet today. A TCP session adapts the demands it places on the network to observations of bandwidth availability on the network. Because TCP is adaptive, any model of its behavior that aspires to be accurate must be influenced by other network traffic. This point is especially important in the context of using simulation to evaluate some new network algorithm of interest (e.g. reliable multi-cast) in an environment where the background traffic affects---and is affected by---its behavior. We need to generate background traffic efficiently in a way that captures …

802.11b Wireless Network Visualization And Radiowave Propagation Modeling, Chris Lentz

Dartmouth College Undergraduate Theses

This paper outlines the methods of creating detailed coverage maps of 802.11b networks, with an emphasis on minimizing the expenses and time involved. The goal of this work is to develop and present a streamlined, reproducible approach to wireless visualization as well as techniques for predicting coverage area before conducting network installations. After evaluating these coverage maps, a repeated series of field measurements will be checked against interpolated values in order to improve techniques for extrapolation of data for unsampled regions. If successful, these extrapolation techniques will provide additional guidelines for, and assist modeling of, new wireless network installations. However, …