Computer Sciences Commons^™

Secure Context-Sensitive Authorization, Kazuhiro Minami, David Kotz

Computer Science Technical Reports

There is a recent trend toward rule-based authorization systems to achieve flexible security policies. Also, new sensing technologies in pervasive computing make it possible to define context-sensitive rules, such as ``allow database access only to staff who are currently located in the main office.'' However, these rules, or the facts that are needed to verify authority, often involve sensitive context information. This paper presents a secure context-sensitive authorization system that protects confidential information in facts or rules. Furthermore, our system allows multiple hosts in a distributed environment to perform the evaluation of an authorization query in a collaborative way; we …

Statistical Tools For Digital Image Forensics, Alin C. Popescu

Dartmouth College Ph.D Dissertations

A digitally altered image, often leaving no visual clues of having been tampered with, can be indistinguishable from an authentic image. The tampering, however, may disturb some underlying statistical properties of the image. Under this assumption, we propose five techniques that quantify and detect statistical perturbations found in different forms of tampered images: (1) re-sampled images (e.g., scaled or rotated); (2) manipulated color filter array interpolated images; (3) double JPEG compressed images; (4) images with duplicated regions; and (5) images with inconsistent noise patterns. These techniques work in the absence of any embedded watermarks or signatures. For each technique we …

Discrete-Time Fractional Differentiation From Integer Derivatives, Hany Farid

Computer Science Technical Reports

Discrete-time fractional derivative filters (1-D and 2-D) are shown to be well approximated from a small set of integer derivatives. A fractional derivative of arbitrary order (and, in 2-D, of arbitrary orientation) can therefore be efficiently computed from a linear combination of integer derivatives of the underlying signal or image.

Secure Hardware Enhanced Myproxy: A Ph.D. Thesis Proposal, John Marchesini, David Kotz

Computer Science Technical Reports

In 1976, Whitfield Diffie and Martin Hellman demonstrated how "New Directions In Cryptography" could enable secure information exchange between parties that do not share secrets. In order for public key cryptography to work in modern distributed environments, we need an infrastructure for finding and trusting other parties' public keys (i.e., a PKI). A number of useful applications become possible with PKI. While the applications differ in how they use keys (e.g., S/MIME uses the key for message encryption and signing, while client-side SSL uses the key for authentication), all applications share one assumption: users have keypairs. In previous work, we …

A Survey Of Wpa And 802.11i Rsn Authentication Protocols, Kwang-Hyun Baek, Sean W. Smith, David Kotz

Computer Science Technical Reports

In the new standards for WLAN security, many choices exist for the authentication process. In this paper, we list eight desired properties of WLAN authentication protocols, survey eight recent authentication protocols, and analyze the protocols according to the desired properties.

Problems With The Dartmouth Wireless Snmp Data Collection, Tristan Henderson, David Kotz

Computer Science Technical Reports

The original Dartmouth wireless network study used SNMP to query the college's Cisco 802.11b access points. The perl scripts that performed the SNMP queries suffered from some problems, in that they queried inappropriate SNMP values, or misunderstood the meaning of other values. This data was also used in a subsequent analysis. The same scripts were used to collect data for a subsequent study of another wireless network. This document outlines these problems and indicates which of the data collected by the original scripts may be invalid.

Composing A Well-Typed Region, Chris Hawblitzel, Heng Huang, Lea Wittie

Computer Science Technical Reports

Efficient low-level systems need more control over memory than safe high-level languages usually provide. In particular, safe languages usually prohibit explicit deallocation, in order to prevent dangling pointers. Regions provide one safe deallocation mechanism; indeed, many region calculi have appeared recently, each with its own set of operations and often complex rules. This paper encodes regions from lower-level typed primitives (linear memory, coercions, and delayed types), so that programmers can design their own region operations and rules.

Performance Evaluation Of A Resource Discovery Service, Jue Wang

Dartmouth College Master’s Theses

In a pervasive computing environment, the number and variety of resources (services, devices, and contextual information resources) make it necessary for applications to accurately discover the best ones quickly. Thus a resource-discovery service, which locates specific resources and establishes network connections as better resources become available, is necessary for those applications. The performance of the resource-discovery service is important when the applications are in a dynamic and mobile environment. In this thesis, however, we do not focus on the resource- discovery technology itself, but the evaluation of the scalability and mobility of the resource discovery module in Solar, a context …

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 …

Automatic Image Orientation Determination With Natural Image Statistics, Siwei Lyu

Computer Science Technical Reports

In this paper, we propose a new method for automatically determining image orientations. This method is based on a set of natural image statistics collected from a multi-scale multi-orientation image decomposition (e.g., wavelets). From these statistics, a two-stage hierarchal classification with multiple binary SVM classifiers is employed to de- termine image orientation. The proposed method is evaluated and compared to existing methods with experiments performed on 18040 natural images, where it showed promising performance.

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 …

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 …

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.

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 …

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.

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). …

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 …