Computer Sciences Commons^™

An Evaluation Of The Impact Of Models For Radio Propagation On The Simulation Of 802.11b Wireless Networks, Evan W. Richardson

Dartmouth College Undergraduate Theses

Working with an existing wireless network simulator, we describe the addition of both a method for modeling arbitrary terrain, and for calculating signal attenuation with the Irregular Terrain Model (ITM). We also investigate ITM's effects on upper protocol layer in comparison to the Two-Ray Ground Reflection model. Upon examination, it was found that aside from the terrain between the transmitter and receiver, ITM's various parameters are of little significance in the computed signal attenuation. Further, examination of the behavior of the upper protocol layers revealed that at high traffic levels, choice of propagation model can have significant effects on the …

Power Conservation In The Network Stack Of Wireless Sensors, Michael De Rosa

Dartmouth College Undergraduate Theses

Wireless sensor networks have recently become an incredibly active research area in the networking community. Much attention has been given to the construction of power-conserving protocols and techniques, as battery life is the one factor that prevents successful wide-scale deployment of such networks. These techniques concentrate on the optimization of network behavior, as the wireless transmission of data is the most expensive operation performed by a sensor node. Very little work has been published on the integration of such techniques, and their suitability to various application domains. This paper presents an exhaustive power consumption analysis of network stacks constructed with …

Enhancing Asynchronous Parallel Computing, Elizabeth Anne Hamon

Dartmouth College Undergraduate Theses

In applications using large amounts of data, hiding the latency inherent in accessing data far from the processor is often necessary in order to achieve high performance. Several researchers have observed that one way to address the challenge of latency is by using a common structure: in a series of passes, the program reads in the data, performs various operations on it, and writes out the data. Passes often consist of a pipeline structure composed of different stages. In order to achieve high performance, the stages are frequently overlapped, for example, by using asynchronous threads. Out-of-core parallel programs provide one …

Distributed Planning And Control For Modular Robots With Unit-Compressible Modules, Zack Butler, Daniela Rus

Computer Science Technical Reports

Self-reconfigurable robots are versatile systems consisting of large numbers of independent modules. Effective use of these systems requires parallel actuation and planning, both for efficiency and independence from a central controller. This paper presents the PacMan algorithm, a technique for distributed actuation and planning for systems with two- or three-dimensional unit-compressible modules. We give two versions of the algorithm along with correctness analysis. We also analyze the parallel actuation capability of the algorithm, showing that it will not deadlock and will avoid disconnecting the robot. We have implemented PacMan on the Crystal robot, a hardware system developed in our lab, …

A Surface-Based Approach For Classification Of 3d Neuroanatomic Structures, Li Shen, James Ford, Fillia Makedon, Andrew Saykin

Computer Science Technical Reports

We present a new framework for 3D surface object classification that combines a powerful shape description method with suitable pattern classification techniques. Spherical harmonic parameterization and normalization techniques are used to describe a surface shape and derive a dual high dimensional landmark representation. A point distribution model is applied to reduce the dimensionality. Fisher's linear discriminants and support vector machines are used for classification. Several feature selection schemes are proposed for learning better classifiers. After showing the effectiveness of this framework using simulated shape data, we apply it to real hippocampal data in schizophrenia and perform extensive experimental studies by …

Digital Art Forensics, Siwei Lyu, Daniel Rockmore, Hany Farid

Computer Science Technical Reports

We describe a computational technique for digitally authenticating works of art. This approach builds statistical models of an artist from a set of authenticated works. Additional works are then authenticated against this model. The statistical model consists of first- and higher-order wavelet statistics. We show preliminary results from our analysis of thirteen drawings by Pieter Bruegel the Elder. We also present preliminary results showing how these techniques may be applicable to determining how many hands contributed to a single painting.

Efficient And Practical Constructions Of Ll/Sc Variables, Prasad Jayanti, Srdjan Petrovic

Computer Science Technical Reports

Over the past decade, LL/SC have emerged as the most suitable synchronization instructions for the design of lock-free algorithms. However, current architectures do not support these instructions; instead, they support either CAS or RLL/RSC (e.g. POWER4, MIPS, SPARC, IA-64). To bridge this gap, this paper presents two efficient wait-free algorithms for implementing 64-bit LL/SC objects from 64-bit CAS or RLL/RSC objects. Our first algorithm is practical: it has a small, constant time complexity (of 4 for LL and 5 for SC) and a space overhead of only 4 words per process. This algorithm uses unbounded sequence numbers. For theoretical interest, …

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

Dartmouth Scholarship

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 in detail, present examples to demonstrate the power of our query language, and discuss the performance …

Spade: Spki/Sdsi For Attribute Release Policies In A Distributed Environment, Sidharth P. Nazareth

Dartmouth College Master’s Theses

Shibboleth is a federated administrated system that supports inter-institutional authentication and authorization for sharing of resources. SPKI/SDSI is a public key infrastructure whose creation was motivated by the perception that X.509 is too complex and flawed. This thesis addresses the problem of how users that are part of a Public Key Infrastructure in a distributed computing system can effectively specify, create, and disseminate their Attribute Release Policies for Shibboleth using SPKI/SDSI. This thesis explores existing privacy mechanims, as well as distributed trust management and policy based systems. My work describes the prototype for a Trust Management Framework called SPADE (SPKI/SDSI …

Electronic Documents And Digital Signatures, Kunal Kain

Dartmouth College Master’s Theses

Often, the main motivation for using PKI in business environments is to streamline workflow, by enabling humans to digitally sign electronic documents, instead of manually signing paper ones. However, this application fails if adversaries can construct electronic documents whose viewed contents can change in useful ways, without invalidating the digital signature. In this paper, we examine the space of such attacks, and describe how many popular electronic document formats and PKI packages permit them.

Discovery, Visualization And Analysis Of Gene Regulatory Sequence Elements In Genomes, Daniel F. Simola

Dartmouth College Undergraduate Theses

The advent of rapid DNA sequencing has produced an explosion in the amount of available sequence information, permitting us to ask many new questions about DNA. There is a pressing need to design algorithms that can provide answers to questions related to the control of gene expression, and thus to the structure, function, and behavior of organisms. Such algorithms must filter through massive amounts of informational noise to identify meaningful conserved regulatory DNA sequence elements. We are approaching these questions with the notion that visualization is a key to exploring data relationships. Understanding the exact nature of these relationships can …

A Progressive Folding Algorithm For Rna Secondary Structure Prediction, Samuel J. Stearns

Dartmouth College Master’s Theses

RNA secondary structure prediction is an area where computational techniques have shown great promise. Most RNA secondary structure prediction algorithms use dynamic programming to compute a secondary structure with minimum free energy. Energy minimization algorithms are less accurate on larger RNA molecules. One potential reason is that larger RNA molecules do not fold instantaneously. Instead, several studies show that RNA molecules fold progressively during transcription. This process could encourage the molecule to fold into a structure that is not at the global lowest energy level. Additionally, dynamic programming algorithms do not allow for a important type of structure called a …

Using Low Level Linear Memory Management For Type-Preserving Mark-Sweep Garbage Collector, Edward Wei

Dartmouth College Undergraduate Theses

Efficient low-level systems such as garbage collectors need more control over memory than safe high-level languages usually provide. Due to this constraint, garbage collectors are typically written in unsafe languages such as C. A collector of this form usually resides as a trusted primitive runtime service outside the model of the programming language. The type safety of these languages depends on the assumption that the garbage collector will not violate any typing invariants. However, no realistic systems provide proof of this assumption. A garbage collector written in a strongly typed language can guarantee not only the safety of the garbage …

An Analysis Of Convergence Properties Of The Border Gateway Protocol Using Discrete Event Simulation, Brian J. Premore

Dartmouth College Ph.D Dissertations

The Internet is an enormous internetwork formed by connecting tens of thousands of independently managed computer networks. Though the Internet has no central authority and is highly heterogeneous, a universally adopted addressing scheme---defined by the Internet Protocol (IP)---makes interaction between the individual networks possible. Complementing IP is the Border Gateway Protocol (BGP), which facilitates communication between parts of the internetwork by determining paths by which data can get from one network to any other. Just as IP is used ubiquitously as an addressing scheme, BGP is used ubiquitously for the purpose of network-to-network routing. Because BGP is universal, its well-being …

Efficient Security For Bgp Route Announcements, David M. Nicol, Sean W. Smith, Meiyuan Zhao

Computer Science Technical Reports

The Border Gateway Protocol (BGP) determines how Internet traffic is routed throughout the entire world; malicious behavior by one or more BGP speakers could create serious security issues. Since the protocol depends on a speaker honestly reporting path information sent by previous speakers and involves a large number of independent speakers, the Secure BGP (S-BGP) approach uses public-key cryptography to ensure that a malicious speaker cannot fabricate this information. However, such public-key cryptography is expensive: S-BGP requires a digital signature operation on each announcement sent to each peer, and a linear (in the length of the path) number of verifications …

Billiards Adviser As A Search In A Continuous Domain With Significant Uncertainty, Thomas Mueller

Dartmouth College Undergraduate Theses

Typical search algorithms are limited to problems in which there is a certain number of moves for any given state, and the effect of each move is well known. In order to overcome this limitation, we consider the problem of determining the optimal shot given the positions of balls on a billiards table. Our solution includes the image recognition necessary to determine each ball's position, the calculation of the optimal shot, and the presentation of that shot to the player. The focus of the paper is on the second part - determining the angle and force with which the player …

An Active Learning Approach To Efficiently Ranking Retrieval Engines, Lisa A. Torrey

Dartmouth College Undergraduate Theses

Evaluating retrieval systems, such as those submitted to the annual TREC competition, usually requires a large number of documents to be read and judged for relevance to query topics. Test collections are far too big to be exhaustively judged, so only a subset of documents is selected to form the judgment ``pool.'' The selection method that TREC uses produces pools that are still quite large. Research has indicated that it is possible to rank the retrieval systems correctly using substantially smaller pools. This paper introduces an active learning algorithm whose goal is to reach the correct rankings using the smallest …

Trusted S/Mime Gateways, Mindy J. Pereira

Dartmouth College Undergraduate Theses

The utility of Web-based email clients is clear: a user is able to access their email account from any computer anywhere at any time. However, this option is unavailable to users whose security depends on their key pair being stored either on their local computer or in their browser. Our implementation seeks to solve two problems with secure email services. The first that of mobility: users must have access to their key pairs in order to perform the necessary cryptographic operations. The second is one of transition: initially, users would not want to give up their regular email clients. Keeping …

Persistence And Prevalence In The Mobility Of Dartmouth Wireless Network Users, Clara Lee

Dartmouth College Undergraduate Theses

Wireless local-area networks (WLANs) are increasing in popularity. As more people use WLANs it is important to understand how these users behave. We analyzed data collected over three months of 2002 to measure the persistence and prevalence of users of the Dartmouth wireless network.

We found that most of the users of Dartmouth's network have short association times and a high rate of mobility. This observation fits with the predominantly student population of Dartmouth College, because students do not have a fixed workplace and are moving to and from classes all day.

Computational Markets To Regulate Mobile-Agent Systems, Jonathan Bredin, David Kotz, Daniela Rus, Rajiv T. Maheswaran, Cagri Imer, Tamer Başar

Dartmouth Scholarship

Mobile-agent systems allow applications to distribute their resource consumption across the network. By prioritizing applications and publishing the cost of actions, it is possible for applications to achieve faster performance than in an environment where resources are evenly shared. We enforce the costs of actions through markets where user applications bid for computation from host machines. \par We represent applications as collections of mobile agents and introduce a distributed mechanism for allocating general computational priority to mobile agents. We derive a bidding strategy for an agent that plans expenditures given a budget and a series of tasks to complete. We …

Efficient I/O For Computational Grid Applications, Ron A. Oldfield

Dartmouth College Ph.D Dissertations

High-performance computing increasingly occurs on "computational grids" composed of heterogeneous and geographically distributed systems of computers, networks, and storage devices that collectively act as a single "virtual" computer. A key challenge in this environment is to provide efficient access to data distributed across remote data servers. This dissertation explores some of the issues associated with I/O for wide-area distributed computing and describes an I/O system, called Armada, with the following features: a framework to allow application and dataset providers to flexibly compose graphs of processing modules that describe the distribution, application interfaces, and processing required of the dataset before or …

The Online Median Problem, Ramgopal R. Mettu, C. Greg Plaxton

Dartmouth Scholarship

We introduce a natural variant of the (metric uncapacitated) k-median problem that we call the online median problem. Whereas the k-median problem involves optimizing the simultaneous placement of k facilities, the online median problem imposes the following additional constraints: the facilities are placed one at a time, a facility cannot be moved once it is placed, and the total number of facilities to be placed, k, is not known in advance. The objective of an online median algorithm is to minimize the competitive ratio, that is, the worst-case ratio of the cost of an online placement to …

Relaxing The Problem-Size Bound For Out-Of-Core Columnsort, Geeta Chaudhry, Elizabeth A. Hamon, Thomas H. Cormen

Computer Science Technical Reports

Previous implementations of out-of-core columnsort limit the problem size to $N \leq \sqrt{(M/P)^3 / 2}$, where $N$ is the number of records to sort, $P$ is the number of processors, and $M$ is the total number of records that the entire system can hold in its memory (so that $M/P$ is the number of records that a single processor can hold in its memory). We implemented two variations to out-of-core columnsort that relax this restriction. Subblock columnsort is based on an algorithmic modification of the underlying columnsort algorithm, and it improves the problem-size bound to $N \leq (M/P)^{5/3} / 4^{2/3}$ …

Stupid Columnsort Tricks, Geeta Chaudhry, Thomas H. Cormen

Computer Science Technical Reports

Leighton's columnsort algorithm sorts on an $r \times s$ mesh, subject to the restrictions that $s$ is a divisor of~$r$ and that $r \geq 2s^2$ (so that the mesh is tall and thin). We show how to mitigate both of these restrictions. One result is that the requirement that $s$ is a divisor of~$r$ is unnecessary; columnsort sorts correctly whether or not $s$ divides~$r$. We present two algorithms that, as long as $s$ is a perfect square, relax the restriction that $r \geq 2s^2$; both reduce the exponent of~$s$ to~$3/2$. One algorithm requires $r \geq 4s^{3/2}$ if $s$ divides~$r$ and …

Context-Sensitive Resource Discovery, Guanling Chen, David Kotz

Dartmouth Scholarship

This paper presents the “Solar” system framework that allows resources to advertise context-sensitive names and for applications to make context-sensitive name queries. The heart of our framework is a small specification language that allows composition of “context-processing operators” to calculate the desired context. Resources use the framework to register and applications use the framework to lookup context-sensitive name descriptions. The back-end system executes these operators and constantly updates the context values, adjusting advertised names and informing applications about changes. We report experimental results from a prototype, using a modified version of the Intentional Naming System (INS) as the core directory …

Flexible And Scalable Public Key Security For Ssh, Yasir Ali

Dartmouth College Master’s Theses

A standard tool for secure remote access, the SSH protocol uses public-key cryptography to establish an encrypted and integrity-protected channel with a remote server. However, widely-deployed implementations of the protocol are vulnerable to man-in-the-middle attacks, where an adversary substitutes her public key for the server's. This danger particularly threatens a traveling user Bob borrowing a client machine.

Imposing a traditional X.509 PKI on all SSH servers and clients is neither flexible nor scalable nor (in the foreseeable future) practical. Requiring extensive work or an SSL server at Bob's site is also not practical for many users.

This paper presents our …

Privacy-Enhanced Credential Services, Alex Iliev, Sean Smith

Computer Science Technical Reports

The use of credential directories in PKI and authorization systems such as Shibboleth introduces a new privacy risk: an insider at the directory can learn much about otherwise protected interactions by observing who makes queries, and what they ask for. Recent advances in Practical Private Information Retrieval provide promising countermeasures. In this paper, we extend this technology to solve this new privacy problem, and present a design and preliminary prototype for a LDAP-based credential service that can prevent even an insider from learning anything more than the fact a query was made. Our preliminary performance analysis suggests that the complete …

Keyjacking: Risks Of The Current Client-Side Infrastructure, 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 browser-based keystores. Exploring this vision, we demonstrate that browsers will use personal certificates to authenticate requests that the person neither knew of nor approved (and which password-based systems would have defeated), and we demonstrate the easy permeability of these keystores (including new attacks on medium and high-security IE/XP keys). We suggest some countermeasures, but also suggest that a fundamental rethinking of the trust, usage, and storage model might result …

3d-Structural Homology Detection Via Unassigned Residual Dipolar Couplings, Christopher James Langmead, Bruce Randall Donald

Computer Science Technical Reports

Recognition of a protein's fold provides valuable information about its function. While many sequence-based homology prediction methods exist, 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 for detecting 3D-structural homologies from sparse, unassigned protein NMR data. Our method identifies the 3D-structural models in a protein structural database whose geometries best fit the unassigned experimental NMR data. It does not use sequence information and is …

Proofs Of Soundness And Strong Normalization For Linear Memory Types, Heng Huang, 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.