Computer Sciences Commons^™

Abortable Reader-Writer Locks Are No More Complex Than Abortable Mutex Locks, Zhiyu Liu

Dartmouth College Master’s Theses

When a process attempts to acquire a mutex lock, it may be forced to wait if another process currently holds the lock. In certain applications, such as real-time operating systems and databases, indefinite waiting can cause a process to miss an important deadline. Hence, there has been research on designing abortable mutual exclusion locks, and fairly efficient algorithms of O(log n) RMR complexity have been discovered (n denotes the number of processes for which the algorithm is designed). The abort feature is just as important for a reader-writer lock as it is for a mutual exclusion lock, but to the …

Constructing Simplicial Complexes Over Topological Spaces, Milka N. Doktorova

Dartmouth College Master’s Theses

The first step in topological data analysis is often the construction of a simplicial complex. This complex approximates the lost topology of a sampled point set. Current techniques often assume that the input is embedded in a metric -- often Euclidean -- space, and make significant use of the underlying geometry for efficient computation. Consequently, these techniques do not extend to non-Euclidean or non-metric spaces. In this thesis, we present an oracle-based framework for constructing simplicial complexes over arbitrary topological spaces. The framework consists of an oracle and an algorithm that builds the simplicial complex by making calls to the …

Asymptotic Statistics Of Nodal Domains Of Quantum Chaotic Billiards In The Semiclassical Limit, Kyle T. Konrad

Dartmouth College Undergraduate Theses

Quantum chaos concerns eigenfunctions of the Laplace operator in a domain where a billiard ball would bounce chaotically. Such chaotic eigenfunctions have been conjectured to share statistical properties of their nodal domains with a simple percolation model, from which many interesting quantities can be computed analytically. We numerically test conjectures on the number and size of nodal domains of quantum chaotic eigenfunctions at very high energies, approaching the semiclassical limit. We use a highly efficient scaling method to quickly compute eigenfunctions at low resolution and interpolate to higher resolution. We computed 10^5 eigenfunctions and counted 10^9 nodal domains. Our results …

A Data Flow Tracker And Reference Monitor For Webkit And Javascriptcore, Andrew Bloomgarden

Dartmouth College Undergraduate Theses

Browser security revolves around the same-origin policy, but it does not defend against all attacks as evidenced by the prevalence of cross-site scripting attacks. Rather than solve that attack in particular, I have opted for a more general solution. I have modified WebKit to allow data flow tracking via labels and to allow security-sensitive operations to be allowed or denied from JavaScript.

Quantitative Patterns Of Stylistic Influence In The Evolution Of Literature, James M. Hughes, Nicholas J. Foti, David C. Krakauer, Daniel N. Rockmore

Dartmouth Scholarship

Literature is a form of expression whose temporal structure, both in content and style, provides a historical record of the evolution of culture. In this work we take on a quantitative analysis of literary style and conduct the first large-scale temporal stylometric study of literature by using the vast holdings in the Project Gutenberg Digital Library corpus. We find temporal stylistic localization among authors through the analysis of the similarity structure in feature vectors derived from content-free word usage, nonhomogeneous decay rates of stylistic influence, and an accelerating rate of decay of influence among modern authors. Within a given time …

Sensor-Based System For Verifying Blood-Pressure Measurement Position, Emma N. Smithayer

Dartmouth College Undergraduate Theses

Mobile maternal-health programs send workers door to door to visit pregnant women in rural India and collect data such as blood pressure or weight, then send that data to doctors for review. Since the doctors do not see the data collection, ensuring correct collection methods is crucial to allow them to make good treatment decisions. However, blood-pressure measurements are sometimes taken with the patient’s arm in the wrong position, which can cause inaccurate readings. This paper describes a system consisting of an automatic blood pressure cuff with an accelerometer and force sensors attached to determine whether the arm is at …

Meshgit: Diffing And Merging Polygonal Meshes, Jonathan D. Denning, Fabio Pellacini

Computer Science Technical Reports

This paper presents MeshGit, a practical algorithm for diffing and merging polygonal meshes. Inspired by version control for text editing, we introduce the mesh edit distance as a measure of the dissimilarity between meshes. This distance is defined as the minimum cost of matching the vertices and faces of one mesh to those of another. We propose an iterative greedy algorithm to approximate the mesh edit distance, which scales well with model complexity, providing a practical solution to our problem. We translate the mesh correspondence into a set of mesh editing operations that transforms the first mesh into the second. …

Toward Evaluating Progressive Rendering Methods In Appearance Design Tasks, Jiawei Ou, Ondrej Karlik, Jaroslav Krivanek, Fabio Pellacini

Computer Science Technical Reports

Progressive rendering is becoming a popular alternative to precomputation approaches for appearance design tasks. Images created by different progressive algorithms exhibit various kinds of visual artifacts at the early stages of computation. We present a user study that investigates the effects of these artifacts on user performance in appearance design tasks. Specifically, we ask both novice and expert subjects to perform lighting and material editing tasks with the following algorithms: random path tracing, quasi-random path tracing, progressive photon mapping, and virtual point light (VPL) rendering. Data collected from the experiments suggest that path tracing is strongly preferred to progressive photon …

Access Control Realities As Observed In A Clinical Medical Setting, Sara Sinclair, Sean Smith

Computer Science Technical Reports

Effective computer security requires looking not just at technology, but also at how it meshes with users in the real-world enterprises depending on it. As part of a longer-term series of projects, we have been looking at these issues-- particularly access control-- in a variety of real-world enterprises. In previous work, we looked at companies in the finance and software industries; this paper reports on a study of a hospital's access control systems. Both studies employ ethnographic methods to elicit observations on the failures of current access control technologies in large, dynamic organizations; participants in the corporate study were largely …

Access Control Hygiene And The Empathy Gap In Medical It, Yifei Wang, Sean Smith, Andrew Gettinger

Computer Science Technical Reports

In theory, access control is a solved problem. In practice, large real-world enterprises still report trouble: de facto policy becomes unmanageable; users circumvent controls. These issues can be particularly critical in medical IT, such as emerging EMR and EHR, where access control errors can have serious repercussions. In this paper, we investigate how real-world EMR users think about access control when they are making policy decisions in the abstract---and when they are actually using the system in treatment scenarios. Mismatches suggest places ("empathy gaps") where new policy tools may be needed.

Wallpaper Maps, M. Douglas Mcilroy

Computer Science Technical Reports

A wallpaper map is a conformal projection of a spherical earth onto regular polygons with which the plane can be tiled continuously. A complete set of distinct wallpaper maps that satisfy certain natural symmetry conditions is derived and illustrated. Though all of the projections have been published before, the family had not been characterized as a whole. Some wallpaper maps generalize to one-parameter subfamilies in which the sphere is pre-transformed by a conformal automorphism.

Exposing Privacy Concerns In Mhealth Data Sharing, Aarathi Prasad

Dartmouth College Master’s Theses

Mobile health (mHealth) has become important in the field of healthcare information technology, as patients begin to use mobile devices to record their daily activities and vital signs. These devices can record personal health information even outside the hospital setting, while the patients are at home or at their workplace. However, the devices might record sensitive information that might not be relevant for medical purposes and in some cases may be misused. Patients need expressive privacy controls so that they can trade potential health benefits of the technology with the privacy risks. To provide such privacy controls, it is important …

An Amulet For Trustworthy Wearable Mhealth, Jacob Sorber, Minho Shin, Ronald Peterson, Cory Cornelius, Shrirang Mare, Aarathi Prasad, Zachary Marois, Emma N. Smithayer, David Kotz

Dartmouth Scholarship

Mobile technology has significant potential to help revolutionize personal wellness and the delivery of healthcare. Mobile phones, wearable sensors, and home-based tele-medicine devices can help caregivers and individuals themselves better monitor and manage their health. While the potential benefits of this “mHealth” technology include better health, more effective healthcare, and reduced cost, this technology also poses significant security and privacy challenges. In this paper we propose \emphAmulet, an mHealth architecture that provides strong security and privacy guarantees while remaining easy to use, and outline the research and engineering challenges required to realize the Amulet vision.

Passive Biometrics For Pervasive Wearable Devices (Poster Paper), Cory Cornelius, Zachary Marois, Jacob Sorber, Ron Peterson, Shrirang Mare, David Kotz

Dartmouth Scholarship

Wearable devices – like the FitBit, MOTOACTV, and Jawbone UP – are increasingly becoming more pervasive whether for monitoring health and fitness, personal assistance, or home automation. While pervasive wearable devices have long been researched, we are now beginning to see the fruits of this research in the form of commercial offerings. Today, many of these commercial wearable devices are closed systems that do not interoperate with other devices a person might carry. We believe, however, these commercial offerings signal the coming of wireless body-area networks that will connect these pervasive wearable devices and leverage existing devices a user already …

Derivation Of A Novel Efficient Supervised Learning Algorithm From Cortical-Subcortical Loops, Ashok Chandrashekar, Richard Granger

Dartmouth Scholarship

Although brain circuits presumably carry out powerful perceptual algorithms, few instances of derived biological methods have been found to compete favorably against algorithms that have been engineered for specific applications. We forward a novel analysis of a subset of functions of cortical-subcortical loops, which constitute more than 80% of the human brain, thus likely underlying a broad range of cognitive functions. We describe a family of operations performed by the derived method, including a non-standard method for supervised classification, which may underlie some forms of cortically dependent associative learning. The novel supervised classifier is compared against widely used algorithms for …

Effects Of Network Trace Sampling Methods On Privacy And Utility Metrics, Phillip A. Fazio, Keren Tan, David Kotz

Dartmouth Scholarship

Researchers choosing to share wireless-network traces with colleagues must first anonymize sensitive information, trading off the removal of information in the interest of identity protection and the preservation of useful data within the trace. While several metrics exist to quantify this privacy-utility tradeoff, they are often computationally expensive. Computing these metrics using a \emphsample\/ of the trace could potentially save precious time. In this paper, we examine several sampling methods to discover their effects on measurement of the privacy-utility tradeoff when anonymizing network traces. We tested the relative accuracy of several packet and flow-sampling methods on existing privacy and utility …

A Perceptual Metric For Photo Retouching, Eric Kee, Hany Farid

Dartmouth Scholarship

In recent years, advertisers and magazine editors have been widely criticized for taking digital photo retouching to an extreme. Impossibly thin, tall, and wrinkle- and blemish-free models are routinely splashed onto billboards, advertisements, and magazine covers. The ubiquity of these unrealistic and highly idealized images has been linked to eating disorders and body image dissatisfaction in men, women, and children. In response, several countries have considered legislating the labeling of retouched photos. We describe a quantitative and perceptually meaningful metric of photo retouching. Photographs are rated on the degree to which they have been digitally altered by explicitly modeling and …

Security Applications Of Formal Language Theory, Len Sassaman, Meredith L. Patterson, Sergey Bratus, Michael E. Locasto, Anna Shubina

Computer Science Technical Reports

We present an approach to improving the security of complex, composed systems based on formal language theory, and show how this approach leads to advances in input validation, security modeling, attack surface reduction, and ultimately, software design and programming methodology. We cite examples based on real-world security flaws in common protocols representing different classes of protocol complexity. We also introduce a formalization of an exploit development technique, the parse tree differential attack, made possible by our conception of the role of formal grammars in security. These insights make possible future advances in software auditing techniques applicable to static and dynamic …

The Good, The Bad, And The Actively Verified, John Williamson

Dartmouth College Master’s Theses

We believe that we can use active probing for compromise recovery. Our intent is to exploit the differences in behavior between compromised and uncompromised systems and use that information to identify those which are not behaving as expected. Those differences may indicate a deviation in either con figuration or implementation from what we expect on the network, either of which suggests that the misbehaving entity might not be trustworthy. In this work, we propose and build a case for a method for using altered behavior directly resulting from or introduced as a side-effect of the compromise of a network service …

A 3-D Lighting And Shadow Analysis Of The Jfk Zapruder Film (Frame 317), Hany Farid

Computer Science Technical Reports

Claims of a broader conspiracy behind U.S. President John F. Kennedy's assassination have persisted for the past nearly five decades. The Zapruder film is considered to be the most complete recording of JFK's assassination. Many have claimed that this 8mm film was manipulated to conceal evidence of a second shooter, which would invalidate the claim that a lone gunman, Lee Harvey Oswald, was responsible for JFK's assassination. Here we consider the viability of one specific claim of postproduction tampering in the Zapruder film.

Adapt-Lite: Privacy-Aware, Secure, And Efficient Mhealth Sensing, Shrirang Mare, Jacob Sorber, Minho Shin, Cory Cornelius, David Kotz

Dartmouth Scholarship

As healthcare in many countries faces an aging population and rising costs, mobile sensing technologies promise a new opportunity. Using mobile health (mHealth) sensing, which uses medical sensors to collect data about the patients, and mobile phones to act as a gateway between sensors and electronic health record systems, caregivers can continuously monitor the patients and deliver better care. Although some work on mHealth sensing has addressed security, achieving strong security and privacy for low-power sensors remains a challenge. \par We make three contributions. First, we propose Adapt-lite, a set of two techniques that can be applied to existing wireless …

Hide-N-Sense: Privacy-Aware Secure Mhealth Sensing, Shrirang Mare, Jacob Sorber, Minho Shin, Cory Cornelius, David Kotz

Computer Science Technical Reports

As healthcare in many countries faces an aging population and rising costs, mobile sensing technologies promise a new opportunity. Using mobile health (mHealth) sensing, which uses medical sensors to collect data about the patients, and mobile phones to act as a gateway between sensors and electronic health record systems, caregivers can continuously monitor the patients and deliver better care. Furthermore, individuals can become better engaged in monitoring and managing their own health. Although some work on mHealth sensing has addressed security, achieving strong privacy for low-power sensors remains a challenge.

We make three contributions. First, we propose an mHealth sensing …

Bgrep And Bdiff: Unix Tools For High-Level Languages, Gabriel A. Weaver, Sean W. Smith

Computer Science Technical Reports

The rise in high-level languages for system administrators requires us to rethink traditional UNIX tools designed for these older data formats. We propose new block-oriented tools, bgrep and bdiff, operating on syntactic blocks of code rather than the line, the traditional information container of UNIX. Transcending the line number allows us to introduce longitudinal diff, a mode of bdiff that lets us track changes across arbitrary blocks of code. We present a detailed implementation roadmap and evaluation framework for the full version of this paper. In addition we demonstrate how the design of our tools already addresses several real-wold problems …

Tackling Latency Using Fg, Priya Natarajan

Dartmouth College Ph.D Dissertations

Applications that operate on datasets which are too big to fit in main memory, known in the literature as external-memory or out-of-core applications, store their data on one or more disks. Several of these applications make multiple passes over the data, where each pass reads data from disk, operates on it, and writes data back to disk. Compared with an in-memory operation, a disk-I/O operation takes orders of magnitude (approx. 100,000 times) longer; that is, disk-I/O is a high-latency operation. Out-of-core algorithms often run on a distributed-memory cluster to take advantage of a cluster's computing power, memory, disk space, and …

Anomaly Detection In Network Streams Through A Distributional Lens, Chrisil Arackaparambil

Dartmouth College Ph.D Dissertations

Anomaly detection in computer networks yields valuable information on events relating to the components of a network, their states, the users in a network and their activities. This thesis provides a unified distribution-based methodology for online detection of anomalies in network traffic streams. The methodology is distribution-based in that it regards the traffic stream as a time series of distributions (histograms), and monitors metrics of distributions in the time series. The effectiveness of the methodology is demonstrated in three application scenarios. First, in 802.11 wireless traffic, we show the ability to detect certain classes of attacks using the methodology. Second, …

Beyond Selinux: The Case For Behavior-Based Policy And Trust Languages, Sergey Bratus, Michael E. Locasto, Boris Otto, Rebecca Shapiro, Sean W. Smith, Gabriel Weaver

Computer Science Technical Reports

Despite the availability of powerful mechanisms for security policy and access control, real-world information security practitioners---both developers and security officers---still find themselves in need of something more. We believe that this is the case because available policy languages do not provide clear and intelligible ways to allow developers to communicate their knowledge and expectations of trustworthy behaviors and actual application requirements to IT administrators. We work to address this policy engineering gap by shifting the focus of policy language design to this communication via behavior-based policies and their motivating scenarios.

Adaptive Security And Privacy For Mhealth Sensing, Shrirang Mare, Jacob Sorber, Minho Shin, Cory Cornelius, David Kotz

Dartmouth Scholarship

As healthcare in many countries faces an aging population and rising costs, mobile Health (mHealth) sensing technologies promise a new opportunity. However, the privacy concerns associated with mHealth sensing are a limiting factor for their widespread adoption. The use of wireless body area networks pose a particular challenge. Although there exist protocols that provide a secure and private communication channel between two devices, the large transmission overhead associated with these protocols limit their application to low-power mHealth sensing devices. We propose an adaptive security model that enables use of privacy-preserving protocols in low-power mHealth sensing by reducing the network overhead …

Autoscopy Jr.: Intrusion Detection For Embedded Control Systems, Jason O. Reeves

Dartmouth College Master’s Theses

Securing embedded control systems within the power grid presents a unique challenge: on top of the resource restrictions inherent to these devices, SCADA systems must also accommodate strict timing requirements that are non-negotiable, and their massive scale greatly amplifies costs such as power consumption. These constraints make the conventional approach to host intrusion detection--namely, employing virtualization in some manner--too costly or impractical for embedded control systems within critical infrastructure. Instead, we take an in-kernel approach to system protection, building upon the Autoscopy system developed by Ashwin Ramaswamy that places probes on indirectly-called functions and uses them to monitor its host …

Large-Scale Wireless Local-Area Network Measurement And Privacy Analysis, Keren Tan

Dartmouth College Ph.D Dissertations

The edge of the Internet is increasingly becoming wireless. Understanding the wireless edge is therefore important for understanding the performance and security aspects of the Internet experience. This need is especially necessary for enterprise-wide wireless local-area networks (WLANs) as organizations increasingly depend on WLANs for mission- critical tasks. To study a live production WLAN, especially a large-scale network, is a difficult undertaking. Two fundamental difficulties involved are (1) building a scalable network measurement infrastructure to collect traces from a large-scale production WLAN, and (2) preserving user privacy while sharing these collected traces to the network research community. In this dissertation, …

Scalable Object-Class Search Via Sparse Retrieval Models And Approximate Ranking, Mohammad Rastegari, Chen Fang, Lorenzo Torresani

Computer Science Technical Reports

In this paper we address the problem of object-class retrieval in large image data sets: given a small set of training examples defining a visual category, the objective is to efficiently retrieve images of the same class from a large database. We propose two contrasting retrieval schemes achieving good accuracy and high efficiency. The first exploits sparse classification models expressed as linear combinations of a small number of features. These sparse models can be efficiently evaluated using inverted file indexing. Furthermore, we introduce a novel ranking procedure that provides a significant speedup over inverted file indexing when the goal is …