Computer Sciences Commons^™

Mercer Kernels For Object Recognition With Local Features, Siwei Lyu

Computer Science Technical Reports

In this paper, we propose a new class of kernels for object recognition based on local image feature representations. Formal proofs are given to show that these kernels satisfy the Mercer condition and reflect similarities between sets of local features. In addition, multiple types of local features and semilocal constraints are incorporated to reduce mismatches between local features, thus further improve the classification performance. Experimental results of SVM classifiers coupled with the proposed kernels are reported on ecognition tasks with the standard COIL-100 database and compared with existing methods. The proposed kernels achieved satisfactory performance and were robust to changes …

Efficient Wait-Free Implementation Of Multiword Ll/Sc Variables, Prasad Jayanti, Srdjan Petrovic

Computer Science Technical Reports

Since the design of lock-free data structures often poses a formidable intellectual challenge, researchers are constantly in search of abstractions and primitives that simplify this design. The multiword LL/SC object is such a primitive: many existing algorithms are based on this primitive, including the nonblocking and wait-free universal constructions of Anderson and Moir (1995), the closed objects construction of Chandra et al.(1998) and the snapshot algorithms of Jayanti (2002, 2004). In this paper, we consider the problem of implementing a W-word LL/SC object shared by N processes. The previous best algorithm, due to Anderson and Moir (1995), is time optimal …

Experimental Evaluation Of Wireless Simulation Assumptions, David Kotz, Calvin Newport, Robert S. Gray, Jason Liu, Yougu Yuan, Chip Elliot

Dartmouth Scholarship

All analytical and simulation research on ad hoc wireless networks must necessarily model radio propagation using simplifying assumptions. We provide a comprehensive review of six assumptions that are still part of many ad hoc network simulation studies, despite increasing awareness of the need to represent more realistic features, including hills, obstacles, link asymmetries, and unpredictable fading. We use an extensive set of measurements from a large outdoor routing experiment to demonstrate the weakness of these assumptions, and show how these assumptions cause simulation results to differ significantly from experimental results. We close with a series of recommendations for researchers, whether …

Creating And Detecting Doctored And Virtual Images: Implications To The Child Pornography Prevention Act, Hany Farid

Computer Science Technical Reports

The 1996 Child Pornography Prevention Act (CPPA) extended the existing federal criminal laws against child pornography to include certain types of "virtual porn". In 2002, the United States Supreme Court found that portions of the CPPA, being overly broad and restrictive, violated First Amendment rights. The Court ruled that images containing an actual minor or portions of a minor are not protected, while computer generated images depicting a fictitious "computer generated" minor are constitutionally protected. In this report I outline various forms of digital tampering, placing them in the context of this recent ruling. I also review computational techniques for …

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

Dartmouth Scholarship

Wireless Local Area Networks (WLANs) are now commonplace on many academic and corporate campuses. As “Wi-Fi” technology becomes ubiquitous, it is increasingly important to understand trends in the usage of these networks. \par 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 …

Heterogeneous Self-Reconfiguring Robotics, Robert Charles Fitch

Dartmouth College Ph.D Dissertations

Self-reconfiguring (SR) robots are modular systems that can autonomously change shape, or reconfigure, for increased versatility and adaptability in unknown environments. In this thesis, we investigate planning and control for systems of non-identical modules, known as heterogeneous SR robots. Although previous approaches rely on module homogeneity as a critical property, we show that the planning complexity of fundamental algorithmic problems in the heterogeneous case is equivalent to that of systems with identical modules. Primarily, we study the problem of how to plan shape changes while considering the placement of specific modules within the structure. We characterize this key challenge in …

Exposing Digital Forgeries By Detecting Duplicated Image Regions, Alin C. Popescu, Hany Farid

Computer Science Technical Reports

We describe an efficient technique that automatically detects duplicated regions in a digital image. This technique works by first applying a principal component analysis to small fixed-size image blocks to yield a reduced dimension representation. This representation is robust to minor variations in the image due to additive noise or lossy compression. Duplicated regions are then detected by lexicographically sorting all of the image blocks. We show the efficacy of this technique on credible forgeries, and quantify its robustness and sensitivity to additive noise and lossy JPEG compression.

Solar: Building A Context Fusion Network For Pervasive Computing, Guanling Chen

Dartmouth College Ph.D Dissertations

The complexity of developing context-aware pervasive-computing applications calls for distributed software infrastructures that assist applications to collect, aggregate, and disseminate contextual data. In this dissertation, we present a Context Fusion Network (CFN), called Solar, which is built with a scalable and self-organized service overlay. Solar is flexible and allows applications to select distributed data sources and compose them with customized data-fusion operators into a directed acyclic information flow graph. Such a graph represents how an application computes high-level understandings of its execution context from low-level sensory data. To manage application-specified operators on a set of overlay nodes called Planets, Solar …

Kerf: Machine Learning To Aid Intrusion Analysts, Javed Aslam, Sergey Bratus, David Kotz, Ron Peterson, Daniela Rus

Dartmouth Scholarship

Kerf is a toolkit for post-hoc intrusion analysis of available system logs and some types of network logs. It takes the view that this process is inherently interactive and iterative: the human analyst browses the log data for apparent anomalies, and tests and revises his hypothesis of what happened. The hypothesis is alternately refined, as information that partially confirms the hypothesis is discovered, and expanded, as the analyst tries new avenues that broaden the investigation.

Design And Implementation Of A Large-Scale Context Fusion Network, Guanling Chen, Ming Li, David Kotz

Dartmouth Scholarship

In this paper we motivate a Context Fusion Network (CFN), an infrastructure model that allows context-aware applications to select distributed data sources and compose them with customized data-fusion operators into a directed acyclic information fusion graph. Such a graph represents how an application computes high-level understandings of its execution context from low-level sensory data. Multiple graphs by different applications inter-connect with each other to form a global graph. A key advantage of a CFN is re-usability, both at code-level and instance-level, facilitated by operator composition. We designed and implemented a distributed CFN system, Solar, which maps the logical operator graph …

Probabilistic Disease Classification Of Expression-Dependent Proteomic Data From Mass Spectrometry Of Human Serum, Ryan H. Lilien, Hany Farid, Bruce R. Donald

Dartmouth Scholarship

We have developed an algorithm called Q5 for probabilistic classification of healthy vs. disease whole serum samples using mass spectrometry. The algorithm employs Principal Components Analysis (PCA) followed by Linear Discriminant Analysis (LDA) on whole spectrum Surface-Enhanced Laser Desorption/Ionization Time of Flight (SELDI-TOF) Mass Spectrometry (MS) data, and is demonstrated on four real datasets from complete, complex SELDI spectra of human blood serum.

Q5 is a closed-form, exact solution to the problem of classification of complete mass spectra of a complex protein mixture. Q5 employs a novel probabilistic classification algorithm built upon a dimension-reduced linear discriminant analysis. Our solution is …

Type-Safe Operating System Abstractions, Lea Wittie

Dartmouth College Ph.D Dissertations

Operating systems and low-level applications are usually written in languages like C and assembly, which provide access to low-level abstractions. These languages have unsafe type systems that allow many bugs to slip by programmers. For example, in 1988, the Internet Worm exploited several insecure points in Unix including the finger command. A call to finger with an unexpected argument caused a buffer overflow, leading to the shutdown of most Internet traffic. A finger application written in a type-safe language would have prevented its exploit and limited the points the Internet Worm could attack. Such vulnerabilities are unacceptable in security-critical applications …

Outdoor Experimental Comparison Of Four Ad Hoc Routing Algorithms, Robert S. Gray, David Kotz, Calvin Newport, Nikita Dubrovsky, Aaron Fiske, Jason Liu, Christopher Masone, Susan Mcgrath, Yougu Yuan

Computer Science Technical Reports

Most comparisons of wireless ad hoc routing algorithms involve simulated or indoor trial runs, or outdoor runs with only a small number of nodes, potentially leading to an incorrect picture of algorithm performance. In this paper, we report on the results of an outdoor trial run of four different routing algorithms, APRL, AODV, GPSR, and STARA, running on top of thirty-three 802.11-enabled laptops moving randomly through an athletic field. The laptops generated random traffic according to the traffic patterns observed in a prototype application, and ran each routing algorithm for a fifteen-minute period over the course of the hour-long trial …

Simulating Mobile Ad Hoc Networks: A Quantitative Evaluation Of Common Manet Simulation Models, Calvin Newport

Dartmouth College Undergraduate Theses

Because it is difficult and costly to conduct real-world mobile ad hoc network experiments, researchers commonly rely on computer simulation to evaluate their routing protocols. However, simulation is far from perfect. A growing number of studies indicate that simulated results can be dramatically affected by several sensitive simulation parameters. It is also commonly noted that most simulation models make simplifying assumptions about radio behavior. This situation casts doubt on the reliability and applicability of many ad hoc network simulation results. In this study, we begin with a large outdoor routing experiment testing the performance of four popular ad hoc algorithms …

Ppl: A Packet Processing Language, Eric G. Krupski

Dartmouth College Undergraduate Theses

Any computing device or system that uses the internet needs to analyze and identify the contents of network packets. Code that does this is often written in C, but reading, identifying, and manipulating network packets in C requires writing tricky and tedious code. Previous work has offered specification languages for describing the format of network packets, which would allow packet type identification without the hassles of doing this task in C. For example, McCann and Chandra's Packet Types [3] system allows the programmer to define arbitrary packet types and generates C unctions which match given data against a specified packet …

Mobile Agents Simulation With Dassf, Nikita E. Dubrovsky

Dartmouth College Undergraduate Theses

Mobile agents are programs that can migrate from machine to machine in a network of computers and have complete control over their movement. Since the performance space of mobile agents has not been characterized fully, assessing the effectiveness of using mobile agents over a traditional client/server approach currently requires implementing an agent system and running time-consuming experiments. This report presents a simple mobile-agent simulation that can provide quick information on the performance and scalability of a generic information retrieval (IR) mobile-agent system under different network configurations. The simulation is built using the DaSSF and DaSSFNet frameworks, resulting in high performance …

Spatial Multipath Location Aided Routing, Soumendra Nanda

Dartmouth College Master’s Theses

Mobile ad-hoc networks (MANETs) are infrastructure-free networks of mobile nodes that communicate with each other wirelessly. There are several routing schemes that have been proposed and several of these have been already extensively simulated or implemented as well. The primary applications of such networks have been in disaster relief operations, military use, conferencing and environment sensing. There are several ad hoc routing algorithms at present that utilize position information (usually in two dimensional terms) to make routing decisions at each node. Our goal is to utilize three-dimensional (3D) position information to provide more reliable as well as efficient routing for …

Scheduling Pipelined, Multi-Threaded Programs In Linux, Brunn W. Roysden

Dartmouth College Undergraduate Theses

A process causes latency when it performs I/O or communication. Pipelined processes mitigate latency by concurrently executing multiple threads--- sequences of operations--- and overlapping computation, communication, and I/O. When more than one thread is ready to run, the scheduler determines which thread in fact runs. This paper presents techniques for scheduling pipelines, with the following three findings. First, using Linux kernel version 2.6 and the NPTL threads package, we observe a 3-6% performance improvement over kernel version 2.4 and the LinuxThreads package. Second, we test techniques that both take advantage of prior knowledge about whether a program is I/O-bound or …

Efficient Wait-Free Implementation Of Atomic Multi-Word Buffer, Rachel B. Ringel

Dartmouth College Undergraduate Theses

This thesis proposes algorithms for implementing a atomic multi-word buffer, which can be accessed concurrently by multiple readers and a single writer, from the hardware-supported shared memory. The algorithms are required to be wait-free: each process reads or writes the multi-word buffer in a bounded number of its own steps, regardless of whether other processes are fast, slow or have crashed. Our first algorithm is built from multi-writer, multi-reader variables whereas the second algorithm is built from single-writer, multi-reader variables. For either algorithm, the worst-case running time of a read or a write operation on the m-word buffer is O(m). …

Testing The Greenpass Wireless Security System, Kimberly S. Powell

Dartmouth College Undergraduate Theses

Greenpass, developed by Nick Goffee, Sung Hoon Kim, Meiyuan Zhao and John Marchesini under the supervision of Sean Smith and Punch Taylor, is a wireless security solution that implements SPKI/SDSI delegation on top of X.509 keypairs within the EAP-TLS authentication protocol. This system aims to model the decentralized way that authorization flows in real-world enterprise settings and provide a seamless solution that allows for easy access to all resources in the network by both registered users and authorized guests. These goals are achieved through the deployment of a delegation tool, which allows an active entity associated to the organization's network …

Greenpass Client Tools For Delegated Authorization In Wireless Networks, Nicholas C. Goffee

Dartmouth College Master’s Theses

Dartmouth's Greenpass project seeks to provide strong access control to a wireless network while simultaneously providing flexible guest access; to do so, it augments the Wi-Fi Alliance's existing WPA standard, which offers sufficiently strong user authentication and access control, with authorization based on SPKI certificates. SPKI allows certain local users to delegate network access to guests by issuing certificates that state, in essence, "he should get access because I said it's okay." The Greenpass RADIUS server described in Kim's thesis [55] performs an authorization check based on such statements so that guests can obtain network access without requiring a busy …

Greenpass Radius Tools For Delegated Authorization In Wireless Networks, Sung Hoon Kim

Dartmouth College Master’s Theses

Dartmouth's Greenpass project extends how public key cryptography can be used to secure the wireless LAN with a RADIUS (Remote Authentication Dial In User Service) server that is responsible for handling authentication requests from clients (called supplicants in the 802.1x authentication model). This thesis describes the design and implementation of the authentication process of Greenpass, specifically what decisions are made in determining who is granted access and how a small modification of already existing protocols can be used to provide guest access in a way that better reflects how delegation of authority works in the real world. Greenpass takes advantage …

A Secure Network Node Approach To The Policy Decision Point In Distributed Access Control, Geoffrey H. Stowe

Dartmouth College Undergraduate Theses

To date, the vast majority of access control research and development has been on gathering, managing, and exchanging information about users. But an equally important component which has yet to be fully developed is the Policy Decision Point - the system that decides whether an access request should be granted given certain attributes of the requestor. This paper describes the research and implementation of a new PDP system for an undergraduate honors project. This PDP system employs three unique features which differentiate it from existing technology: collaboration capabilities, trusted management, and interoperability with other access control systems. Security considerations and …

Technological Implications For Privacy, David Kotz

Computer Science Technical Reports

The World-Wide Web is increasingly used for commerce and access to personal information stored in databases. Although the Web is ``just another medium'' for information exchange, the fact that all the information is stored in computers, and all of the activity happens in computers and computer networks, makes it easier (cheaper) than every to track users' activities. By recording and analyzing user's activities in the Web, activities that may seem to be quite private to many users, it is more likely than ever before that a person's privacy may be threatened. In this paper I examine some of the technology …

Experimental Evaluation Of Wireless Simulation Assumptions, David Kotz, Calvin Newport, Robert S. Gray, Jason Liu, Yougu Yuan, Chip Elliott

Computer Science Technical Reports

All analytical and simulation research on ad~hoc wireless networks must necessarily model radio propagation using simplifying assumptions. Although it is tempting to assume that all radios have circular range, have perfect coverage in that range, and travel on a two-dimensional plane, most researchers are increasingly aware of the need to represent more realistic features, including hills, obstacles, link asymmetries, and unpredictable fading. Although many have noted the complexity of real radio propagation, and some have quantified the effect of overly simple assumptions on the simulation of ad~hoc network protocols, we provide a comprehensive review of six assumptions that are still …

A Sensor Fusion Approach For Meeting Detection, Jue Wang, Guanling Chen, David Kotz

Dartmouth Scholarship

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 …

A Sensor-Fusion Approach For Meeting Detection, Jue Wang, Guanling Chen, David Kotz

Dartmouth Scholarship

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 …

Synchronizing Keyframe Facial Animation To Multiple Text-To-Speech Engines And Natural Voice With Fast Response Time, William H. Pechter

Dartmouth College Undergraduate Theses

This thesis aims to create an automated lip-synchronization system for real-time applications. Specifically, the system is required to be fast, consist of a limited number of keyframes with small memory requirements, and create fluid and believable animations that synchronize with text-to-speech engines as well as raw voice data. The algorithms utilize traditional keyframe animation and a novel method of keyframe selection. Additionally, phoneme-to-keyframe mapping, synchronization, and simple blending rules are employed. The algorithms provide blending between keyframe images, borrow information from neighboring phonemes, accentuate phonemes b, p and m, differentiate between keyframes for phonemes with allophonic variations, and provide prosodromic …

Enhancing Expressiveness Of Speech Through Animated Avatars For Instant Messaging And Mobile Phones, Joseph E. Pechter

Dartmouth College Undergraduate Theses

This thesis aims to create a chat program that allows users to communicate via an animated avatar that provides believable lip-synchronization and expressive emotion. Currently many avatars do not attempt to do lip-synchronization. Those that do are not well synchronized and have little or no emotional expression. Most avatars with lip synch use realistic looking 3D models or stylized rendering of complex models. This work utilizes images rendered in a cartoon style and lip-synchronization rules based on traditional animation. The cartoon style, as opposed to a more realistic look, makes the mouth motion more believable and the characters more appealing. …

A Holesome File System, Darren Erik Vengroff, David Kotz

Computer Science Technical Reports

We present a novel approach to fully dynamic management of physical disk blocks in Unix file systems. By adding a single system call, zero, to an existing file system, we permit applications to create holes, that is, regions of files to which no physical disk blocks are allocated, far more flexibly than previously possible. zero can create holes in the middle of existing files. Using zero, it is possible to efficiently implement applications including a variety of databases and I/O-efficient computation systems on top of the Unix file system. zero can also be used to implement an efficient file-system-based paging …