In the context of data center computing, the carbon emission incurred during the manufacturing of solid-state drives (SSDs), called embodied carbon, is increasingly overtaking the emissions caused by powering these drives throughout their operational lifetime. Out of an abundance of caution, current SSDs are designed to fail long before the internal flash components are completely unusable. Although this choice may be appropriate for single-disk systems, distributed storage systems can already tolerate individual SSD failures through redundancy.

Perhaps the most influential result in the theory of caches is the following theorem due to Sleator and Tarjan: With O(1) resource augmentation, the basic LRU eviction policy is guaranteed to be O(1)-competitive with the optimal offline policy.

The second version of Intel® Software Guard Extensions (Intel SGX), or SGX2, adds dynamic management of enclave memory and threads. The first version required the address space and thread counts to be fixed before execution. The Enclave Dynamic Memory Management (EDMM) feature of SGX2 has the potential to lower launch times and overall execution time. Despite reducing the enclave loading time by 28-93%, straightforward EDMM adoption strategies actually slow execution time down by as much as 58%.

The classical paging problem, introduced by Sleator and Tarjan in 1985, formalizes the problem of caching pages in RAM in order to minimize IOs. Their online formulation ignores the cost of address translation: Programs refer to data via virtual addresses, and these must be translated into physical locations in RAM. Although the cost of an individual address translation is much smaller than that of an IO, every memory access involves an address translation, whereas IOs can be infrequent. In practice, one can spend money to avoid paging by over-provisioning RAM; in contrast, address translation is effectively unavoidable. Thus address-translation costs can sometimes dominate paging costs, and systems must simultaneously optimize both. To mitigate the cost of address translation, all modern CPUs have translation lookaside buffers (TLBs), which are hardware caches of common address translations. What makes TLBs interesting is that a single TLB entry can potentially encode the address translation for many addresses. This is typically achieved via the use of huge pages, which translate runs of contiguous virtual addresses to runs of contiguous physical addresses. Huge pages reduce TLB misses at the cost of increasing the IOs needed to maintain contiguity in RAM. This tradeoff between TLB misses and IOs suggests that the classical paging problem does not tell the full story. This article introduces the Address-Translation Problem, which formalizes the problem of maintaining a TLB, a page table, and RAM in order to minimize the total cost of both TLB misses and IOs. We present an algorithm that achieves the benefits of huge pages for TLB misses without the downsides of huge pages for IOs.

The TLB is increasingly a bottleneck for big data applications. In most designs, the number of TLB entries are highly constrained by latency requirements, and growing much more slowly than the working sets of applications. Many solutions to this problem, such as huge pages, perforated pages, or TLB coalescing, rely on physical contiguity for performance gains, yet the cost of defragmenting memory can easily nullify these gains. This paper introduces mosaic pages, which increase TLB reach by compressing multiple, discrete translations into one TLB entry. Mosaic leverages virtual contiguity for locality, but does not use physical contiguity. Mosaic relies on recent advances in hashing theory to constrain memory mappings, in order to realize this physical address compression without reducing memory utilization or increasing swapping. This paper presents a full-system prototype of Mosaic, in gem5 and modified Linux. In simulation and with comparable hardware to a traditional design, mosaic reduces TLB misses in several workloads by 6-81%. Our results show that Mosaic’s constraints on memory mappings do not harm performance, we never see conflicts before memory is 98% full in our experiments — at which point, a traditional design would also likely swap. Once memory is over-committed, Mosaic swaps fewer pages than Linux in most cases. Finally, we present timing and area analysis for a verilog implementation of the hashing function required on the critical path for the TLB, and show that on a commercial 28nm CMOS process; the circuit runs at a maximum frequency of 4 GHz, indicating that a mosaic TLB is unlikely to affect clock frequency.

Perceived accessibility of an application is a subjective measure of how well an individual with a particular disability, skills, and goals experiences the application via assistive technology. This paper first presents a study with 11 blind users to report how they perceive the accessibility of desktop applications while interacting via assistive technology such as screen readers and a keyboard. The study identifies the low navigational complexity of the user interface (UI) elements as the primary contributor to higher perceived accessibility of different applications. Informed by this study, we develop a probabilistic model that accounts for the number of user actions needed to navigate between any two arbitrary UI elements within an application. This model contributes to the area of computational interaction for non-visual interaction. Next, we derive three metrics from this model: complexity, coverage, and reachability, which reveal important statistical characteristics of an application indicative of its perceived accessibility. The proposed metrics are appropriate for comparing similar applications and can be fine-tuned for individual users to cater to their skills and goals. Finally, we present five use cases, demonstrating how blind users, application developers, and accessibility practitioners can benefit from our model and metrics.

Storage capacity demand is projected to grow exponentially in the coming decade and so will its contribution to the overall carbon footprint of computing devices. In recent years, cloud providers and device vendors have substantially reduced their carbon impact through improved power consumption and product distribution. However, by 2030, the manufacturing of flash-based storage devices will account for 1.7% of carbon emissions in the world. Therefore, reducing production-related carbon emissions of storage is key to sustainability in computing devices.

Despite the existence of file systems tailored for flash and over a decade of research into flash file systems, this paper shows that no single Linux file system performs consistently well on a commodity SSD across different workloads. We define a compleat file system as one where no workloads realize less than 30% of the best file system's performance, and most, if not all, workloads realize at least 85% of the best file system's performance, across a diverse set of microbenchmarks and applications. No file system is compleat on commodity SSDs. This paper demonstrates that one can construct a single compleat file system for commodity SSDs by introducing a set of optimizations over BetrFS. BetrFS is a compleat file system on HDDs, matching the fastest Linux file systems in its worst cases, and, in its best cases, improving performance by up to two orders of magnitude.

A promising avenue for improving the effectiveness of behavioral-based malware detectors is to leverage two-phase detection mechanisms. Existing problem in two-phase detection is that after the first phase produces borderline decision, suspicious behaviors are not well contained before the second phase completes. This article improvesChameleon, a framework to realize the uncertain environment.Chameleonoffers two environments: standard—for software identified as benign by the first phase, and uncertain—for software received borderline classification from the first phase. The uncertain environment adds obstacles to software execution through random perturbations applied probabilistically. We introduce a dynamic perturbation threshold that can target malware disproportionately more than benign software. We analyzed the effects of the uncertain environment by manually studying 113 software and 100 malware, and found that 92 percent malware and 10 percent benign software disrupted during execution. The results were then corroborated by an extended dataset (5,679 Linux malware samples) on a newer system. Finally, a careful inspection of the benign software crashes revealed some software bugs, highlightingChameleon's potential as a practical complementary anti-malware solution.

No abstract available.

Peripheral devices like SSDs are growing more complex, to the point they are effectively small computers themselves. Our position is that this trend creates a new kind of attack vector, where untrusted software could use peripherals strictly as intended to accomplish unintended goals. To exemplify, we set out to rowhammer the DRAM component of a simplified host-side FTL, issuing regular I/O requests that manage to flip bits in a way that triggers sensitive information leakage. We conclude that such attacks might soon be feasible, and we argue that systems need principled approaches for securing peripherals against them.

Users are surrounded by sensors that are available through various devices beyond their smartphones. However, these sensors are not fully utilized by current end-user applications. A key reason sensor use is so limited is that application developers must exactly identify how the sensor data can be used by smartphone apps. To mitigate this problem, we present SenseWear, a sensor-sharing platform that extends the functionality of a smartphone to use remote sensors with limited additional developer effort. Sensor sharing has several uses, including augmenting the hardware in smartphones, creating new gestural interactions with smartphone applications, and improving application's Quality of Experience via higher-quality sensors from other devices, such as wearables. We developed and present six use cases that use remote sensors in various smartphone applications. Each extension requires adding fewer than 20 lines of code on average. Furthermore, using remote sensors did not introduce a perceptible increase in latency, and creates more convenient interaction options for smartphone apps.

The classical paging problem, introduced by Sleator and Tarjan in 1985, formalizes the problem of caching pages in RAM in order to minimize IOs. Their online formulation ignores the cost of address translation: programs refer to data via virtual addresses, and these must be translated into physical locations in RAM. Although the cost of an individual address translation is much smaller than that of an IO, every memory access involves an address translation, whereas IOs can be infrequent. In practice, one can spend money to avoid paging by over-provisioning RAM; in contrast, address translation is effectively unavoidable. Thus address-translation costs can sometimes dominate paging costs, and systems must simultaneously optimize both.

Making logical copies, or clones, of files and directories is critical to many real-world applications and workflows, including backups, virtual machines, and containers. An ideal clone implementation meets the following performance goals: (1) creating the clone has low latency; (2) reads are fast in all versions (i.e., spatial locality is always maintained, even after modifications); (3) writes are fast in all versions; (4) the overall system is space efficient. Implementing a clone operation that realizes all four properties, which we call a nimble clone , is a long-standing open problem. This article describes nimble clones in B-ϵ-tree File System (BetrFS), an open-source, full-path-indexed, and write-optimized file system. The key observation behind our work is that standard copy-on-write heuristics can be too coarse to be space efficient, or too fine-grained to preserve locality. On the other hand, a write-optimized key-value store, such as a Bε-tree or an log-structured merge-tree (LSM)-tree, can decouple the logical application of updates from the granularity at which data is physically copied. In our write-optimized clone implementation, data sharing among clones is only broken when a clone has changed enough to warrant making a copy, a policy we call copy-on-abundant-write . We demonstrate that the algorithmic work needed to batch and amortize the cost of BetrFS clone operations does not erode the performance advantages of baseline BetrFS; BetrFS performance even improves in a few cases. BetrFS cloning is efficient; for example, when using the clone operation for container creation, BetrFS outperforms a simple recursive copy by up to two orders-of-magnitude and outperforms file systems that have specialized Linux Containers (LXC) backends by 3--4×.

Wearable devices, such as smart watches and fitness trackers are growing in popularity, creating a need for application developers to adapt or extend a UI, typically from a smartphone, onto these devices. Wearables generally have a smaller form factor than a phone; thus, porting an app to the watch necessarily involves reworking the UI. An open problem is identifying best practices for adapting UIs to wearable devices.

Even on modern SSDs, I/O scheduling is a first-order performance concern. However, it is unclear how best to optimize I/O patterns for SSDs, because a complex layer of proprietary firmware hides many principal aspects of performance, as well as SSD lifetime. Losing this information leads to research papers drawing incorrect conclusions about prototype systems, as well as real-world systems realizing sub-optimal performance and lifetime. It is our position that a useful performance model of a foundational system component is essential, and the community should support efforts to construct models of SSD performance. We show examples from the literature and our own measurements that illustrate serious limitations of current SSD modeling tools and disk statistics. We observe an opportunity to resolve this problem by reverse engineering SSDs, leveraging recent trends toward component standardization within SSDs. This paper presents a feasibility study and initial results to reverse engineer a commercial SSD's firmware, and discusses limitations and open problems.

Although flash cells wear out, a typical SSD has enough cells and sufficiently sophisticated firmware that its lifetime generally exceeds the expected lifetime of its host system. Even under heavy use, SSDs last for years and can be replaced upon failure. On a smartphone, in contrast, the hardware is more limited and we show that, under heavy use, one can easily, and more quickly, wear out smartphone flash storage. Consequently, a simple, unprivileged, malicious application can render a smartphone unbootable ("bricked") in a few weeks with no warning signs to the user. This bleak result becomes more worrisome when considering the fact that smartphone users generally believe it is safe to try out new applications. To combat this problem, we study the I/O behavior of a wide range of Android applications. We find that high-volume write bursts exist, yet none of the applications we checked sustains an average write rate that is high enough to damage the device (under reasonable usage assumptions backed by the literature). We therefore propose a rate-limiting algorithm for write activity that (1) prevents such attacks, (2) accommodates "normal" bursts, and (3) ensures that the smartphone drive lifetime is longer than a preconfigured lower bound (i.e., its warranty). In terms of user experience, our design only requires that, in the worst case of an app that issues continuous, unsustainable, and unusual writes, the user decides whether to shorten the phone's life or rate limit the problematic app.

Smartphones typically include flash-based storage, because flash offers benefits such as fast random access, shock resistance, high density, and decreasing costs. A main drawback, however, is that flash cells can tolerate only a limited number of writes before becoming unusable.

Storage devices have complex performance profiles, including costs to initiate IOs (e.g., seek times in hard drives), parallelism and bank conflicts (in SSDs), costs to transfer data, and firmware-internal operations. The Disk-Access Machine (DAM) model simplifies reality by assuming that storage devices transfer data in blocks of size B and that all transfers have unit cost. Despite its simplifications, the DAM model is reasonably accurate. In fact, if B is set to the half-bandwidth point, where the latency and bandwidth of the hardware are equal, the DAM approximates the IO cost on any hardware to within a factor of 2. Furthermore, the DAM explains the popularity of B-trees in the 70s and the current popularity of B-trees and log-structured merge trees. But it fails to explain why some B-trees use small nodes, whereas all B-trees use large nodes. In a DAM, all IOs, and hence all nodes, are the same size. In this paper, we show that the affine and PDAM models, which are small refinements of the DAM model, yield a surprisingly large improvement in predictability without sacrificing ease of use. We present benchmarks on a large collection of storage devices showing that the affine and PDAM models give good approximations of the performance characteristics of hard drives and SSDs, respectively. We show that the affine model explains node-size choices in B-trees and B+-trees. Furthermore, the models predict that the B-tree is highly sensitive to variations in the node size whereas B-trees are much less sensitive. These predictions are born out empirically. Finally, we show that in both the affine and PDAM models, it pays to organize data structures to exploit varying IO size. In the affine model, B-trees can be optimized so that all operations are simultaneously optimal, even up to lower order terms. In the PDAM model, B-trees (or B+-trees) can be organized so that both sequential and concurrent workloads are handled efficiently. We conclude that the DAM model is useful as a first cut when designing or analyzing an algorithm or data structure but the affine and PDAM models enable the algorithm designer to optimize parameter choices and fill in design details.

This paper presents a study of x86-64 instruction usage across 9,337 C/C++ applications and libraries in the Ubuntu 16.04 GNU/Linux distribution. We present metrics for reasoning about the relative importance of instructions weighted by the popularity of applications that contain them. From this data, we systematize and empirically ground conventional wisdom regarding the relative importance of various components of an ISA, with particular focus on building binary translation tools. We also verify the representativity of two commonly used benchmark suites, and highlight areas for improvement.

No abstract available.

Low-vision users struggle to browse the web with screen magnifiers. Firstly, magnifiers occlude significant portions of the webpage, thereby making it cumbersome to get the webpage overview and quickly locate the desired content. Further, magnification causes loss of spatial locality and visual cues that commonly define semantic relationships in the page; reconstructing semantic relationships exclusively from narrow views dramatically increases the cognitive burden on the users. Secondly, low-vision users have widely varying needs requiring a range of interface customizations for different page sections; dynamic customization in extant magnifiers is disruptive to users' browsing. We present SteeringWheel, a magnification interface that leverages content semantics to preserve local context. In combination with a physical dial, supporting simple rotate and press gestures, users can quickly navigate different webpage sections, easily locate desired content, get a quick overview, and seamlessly customize the interface. A user study with 15 low-vision participants showed that their web-browsing efficiency improved by at least 20 percent with SteeringWheel compared to extant screen magnifiers.

No abstract available.

Full-path indexing can improve I/O efficiency for workloads that operate on data organized using traditional, hierarchical directories, because data is placed on persistent storage in scan order. Prior results indicate, however, that renames in a local file system with full-path indexing are prohibitively expensive. This article shows how to use full-path indexing in a file system to realize fast directory scans, writes, and renames. The article introduces a range-rename mechanism for efficient key-space changes in a write-optimized dictionary. This mechanism is encapsulated in the key-value Application Programming Interface (API) and simplifies the overall file system design. We implemented this mechanism in B ε -trees File System (BetrFS), an in-kernel, local file system for Linux. This new version, BetrFS 0.4, performs recursive greps 1.5x faster and random writes 1.2x faster than BetrFS 0.3, but renames are competitive with indirection-based file systems for a range of sizes. BetrFS 0.4 outperforms BetrFS 0.3, as well as traditional file systems, such as ext4, Extents File System (XFS), and Z File System (ZFS), across a variety of workloads.

Sighted people can browse the Web almost exclusively using a mouse. This is because web browsing mostly entails pointing and clicking on some element in the web page, and these two operations can be done almost instantaneously with a computer mouse. Unfortunately, people with vision impairments cannot use a mouse as it only provides visual feedback through a cursor. Instead, they are forced to go through a slow and tedious process of building a mental map of the web page, relying primarily on a screen reader's keyboard shortcuts and its serial audio readout of the textual content of the page, including metadata. This can often cause content and cognitive overload. This paper describes our Speed-Dial system which uses an off-the-shelf physical Dial as a surrogate for the mouse for non-visual web browsing. Speed-Dial interfaces the physical Dial with the semantic model of a web page, and provides an intuitive and rapid access to the entities and their content in the model, thereby bringing blind people's browsing experience closer to how sighted people perceive and interact with the Web. A user study with blind participants suggests that with Speed-Dial they can quickly move around the web page to select content of interest, akin to pointing and clicking with a mouse.

Ubiquitous access is an increasingly common vision of computing, wherein users can interact with any computing device or service from anywhere, at any time. In the era of personal computing, users with visual impairments required special-purpose, assistive technologies, such as screen readers, to interact with computers. This paper investigates whether technologies like screen readers have kept pace with, or have created a barrier to, the trend toward ubiquitous access, with a specific focus on desktop computing as this is still the primary way computers are used in education and employment. Towards that, the paper presents a user study with 21 visually-impaired participants, specifically involving the switching of screen readers within and across different computing platforms, and the use of screen readers in remote access scenarios. Among the findings, the study shows that, even for remote desktop access-an early forerunner of true ubiquitous access-screen readers are too limited, if not unusable. The study also identifies several accessibility needs, such as uniformity of navigational experience across devices, and recommends potential solutions. In summary, assistive technologies have not made the jump into the era of ubiquitous access, and multiple, inconsistent screen readers create new practical problems for users with visual impairments.

Nearly all modern software has security flaws---either known or unknown by the users. However, metrics for evaluating software security (or lack thereof) are noisy at best. Common evaluation methods include counting the past vulnerabilities of the program, or comparing the size of the Trusted Computing Base (TCB), measured in lines of code (LoC) or binary size. Other than deleting large swaths of code from project, it is difficult to assess whether a code change decreased the likelihood of a future security vulnerability. Developers need a practical, constructive way of evaluating security.

When flash was introduced, wear-out was a known problem. Over time, a number of techniques have been developed to estimate the expected number of program/erase cycles under typical usage patterns, and sufficiently over-provision the cells such that the device meets its expected lifespan, even if individual cells fail. This paper started as a simple experiment: measuring whether the lifespan of flash devices in smartphones and other mobile devices, match the estimates. To our surprise, we find that, in a matter of days, simple, unprivileged applications can render the drive of several smartphones (and thus, the phone) inoperable. This result is concerning, as it means that installing malicious or poorly-written software could destroy the device itself. We experimentally demonstrate the problem, discuss reasons why it occurs, and consider potential solutions.

This paper presents a storage system that can hide the presence of hidden data alongside a larger volume of public data. Encryption allows a user to hide the contents of data, but not the fact that sensitive data is present. Under duress, the owner of high-value data can be coerced by a powerful adversary to disclose decryption keys. Thus, private users and corporations have an interest in hiding the very presence of some sensitive data, alongside a larger body of less sensitive data (e.g., the operating system and other benign files); this property is called plausible deniability. Existing plausible deniability systems do not fulfill all of the following requirements: (1) resistance to multiple snapshot attacks where an attacker compares the state of the device over time; (2) ensuring that hidden data won't be destroyed when the public volume is modified by a user unaware of the hidden data; and (3) disguising writes to secret data as normal system operations on public data.

Wearable devices, such as smart watches, offer exciting new opportunities for users to interact with their applications. The current state of the art for wearable devices is for a developer to write a custom {\em companion app}, which is a variant of the smartphone app, tailored to the wearable form factor. A developer puts a non-trivial amount of effort to write these companion apps and the programming model does not scale to an increasing diversity of form factors. In this demo, we show a working prototype of our system UIWear that allows a developer to easily extend a smartphone application to other wearable interfaces. Our system, UIWear, extracts the application GUI as a UI tree, which preserves the semantics of the GUI. The developer (or the user) only writes a {\em metaprogram} to encode the GUI design for the wearable device; no effort is needed beyond the design phase. UIWear executes the metaprogram by performing all the underlying tasks to virtualize the application GUI, adapt it, and recreate it on the wearable. A metaprogram can create the same functionality as existing companion apps with an order-of-magnitude less programming effort.

Wearable devices such as smartwatches offer exciting new opportunities for users to interact with their applications. However, the current wearable programming model requires the developer to write a custom companion app for each wearable form factor; the companion app extends the smartphone display onto the wearable, relays user interactions from the wearable to the phone, and updates the wearable display as needed. The development effort required to write a companion app is significant and will not scale to an increasing diversity of form factors. This paper argues for a different programming model for wearable devices. The developer writes an application for the smartphone, but only specifies a UI design for the wearable. Our UIWear system abstracts a logical model of the smartphone GUI, re-tailors the GUI for the wearable device based on the specified UI design, and compiles it into a companion app that we call the UICompanion app. We implemented UIWear on Android smartphones, AndroidWear smartwatches, and Sony SmartEyeGlasses. We evaluate 20 developer-written companion apps from the AndroidWear category on Google Play against the UIWear-created UICompanion apps. The lines-of-code required for the developer to specify the UI design in UIWear is an order-of-magnitude smaller compared to the companion app lines-of-code. Further, in most cases, the UICompanion app performed comparably or better than the corresponding companion app both in terms of qualitative metrics, including latency and energy, and quantitative metrics, including look-and-feel.

File systems that employ write-optimized dictionaries (WODs) can perform random-writes, metadata updates, and recursive directory traversals orders of magnitude faster than conventional file systems. However, previous WOD-based file systems have not obtained all of these performance gains without sacrificing performance on other operations, such as file deletion, file or directory renaming, or sequential writes. Using three techniques, late-binding journaling , zoning , and range deletion , we show that there is no fundamental trade-off in write-optimization. These dramatic improvements can be retained while matching conventional file systems on all other operations. BetrFS 0.2 delivers order-of-magnitude better performance than conventional file systems on directory scans and small random writes and matches the performance of conventional file systems on rename, delete, and sequential I/O. For example, BetrFS 0.2 performs directory scans 2.2 × faster, and small random writes over two orders of magnitude faster, than the fastest conventional file system. But unlike BetrFS 0.1, it renames and deletes files commensurate with conventional file systems and performs large sequential I/O at nearly disk bandwidth. The performance benefits of these techniques extend to applications as well. BetrFS 0.2 continues to outperform conventional file systems on many applications, such as as rsync, git-diff, and tar, but improves git-clone performance by 35% over BetrFS 0.1, yielding performance comparable to other file systems.

Remote desktop technology, the enabler of access to applications hosted on remote hosts, relies primarily on scraping the pixels on the remote screen and redrawing them as a simple bitmap on the client's local screen. Such a technology will simply not work with screen readers since the latter are innately tied to reading text. Since screen readers are locked-in to a specific OS platform, extant solutions that enable remote access with screen readers such as NVDARemote and JAWS Tandem require homogeneity of OS platforms at both the client and remote sites. This demo will present Sinter, a system that eliminates this requirement. With Sinter, a blind Mac user, for example, can now access a remote Windows application with VoiceOver, a scenario heretofore not possible.

Computer users commonly use applications designed for different operating systems (OSes). For instance, a Mac user may access a cloud-based Windows remote desktop to run an application required for her job. Current remote access protocols do not work well with screen readers, creating a disproportionate burden for users with visual impairments. These users' productivity depends on features of a specific screen reader, and readers are locked-in to a specific OS. The only current option is to run a different screen reader on each platform, which harms productivity.

This paper presents a study of Linux API usage across all applications and libraries in the Ubuntu Linux 15.04 distribution. We propose metrics for reasoning about the importance of various system APIs, including system calls, pseudo-files, and libc functions. Our metrics are designed for evaluating the relative maturity of a prototype system or compatibility layer, and this paper focuses on compatibility with Linux applications. This study uses a combination of static analysis to understand API usage and survey data to weight the relative importance of applications to end users.

Applications are generally written assuming a predictable and well-behaved OS. In practice, they experience unpredictable misbehavior at the OS level and across OSes: different OSes can handle network events differently, APIs can behave differently across OSes, and OSes may be compromised or buggy. This unpredictability is challenging because its sources typically manifest during deployment and are hard to reproduce. This paper introduces Bear, a framework for statistical analysis of application sensitivity to OS unpredictability that can help developers build more resilient software, discover challenging bugs and identify the scenarios that most need validation. Bear analyzes a program with a set of perturbation strategies on a set of commonly used system calls in order to discover the most sensitive system calls for each application, the most impactful strategies, and how they predict abnormal program outcome. We evaluated Bear with 113 CPU and IO-bound programs, and our results show that null memory dereferencing and erroneous buffer operations are the most impactful strategies for predicting abnormal program execution and that their impacts increase ten-fold with workload increase (e.g. number of network requests from 10 to 1000). Generic system calls are more sensitive than specialized system calls-for example, write and sendto can both be used to send data through a socket, but the sensitivity of write is twice that of sendto. System calls with an array parameter (e.g. read) are more sensitive to perturbations than those having a struct parameter with a buffer (e.g readv). Moreover, the fewer parameters a system call has, the more sensitive it is.

This paper introduces versioned programming, a technique that can be used to convert pointer-based data structures into efficient, lock-free implementations. Versioned programming allows arbitrary composition of pointer modifications. Taking linked-lists as an example, VLISTs, or versioned lists, support features missing in other lock-free implementations, such as double linking and atomic moves among lists.

Virtual machines (VMs) are an increasingly ubiquitous feature of modern computing, yet the interested student or professional has limited resources to learn how VMs work. In particular, there is a lack of "hands-on" exercises in constructing a virtual machine monitor (VMM, or hypervisor), which are both simple enough to understand completely but realistic enough to capture the practical challenges in using this technology. This paper describes a set of assignments to extend a small, pedagogical operating system (OS) to form a hypervisor and host itself. This pedagogical hypervisor, called HOSS, adds roughly 1,000 lines of code to the MIT JOS source, and includes a set of guided exercises. Initial results with HOSS in an upper-level virtualization course indicate that students enjoyed the assignments and were able to apply what they learned to solve different virtualization-related problems. HOSS is publicly available.

Applications frequently request file system operations that traverse the file system directory tree, such as opening a file or reading a file's metadata. As a result, caching file system directory structure and metadata in memory is an important performance optimization for an OS kernel.

The B ε -tree File System , or B e trFS (pronounced “better eff ess”), is the first in-kernel file system to use a write-optimized data structure (WODS). WODS are promising building blocks for storage systems because they support both microwrites and large scans efficiently. Previous WODS-based file systems have shown promise but have been hampered in several ways, which B e trFS mitigates or eliminates altogether. For example, previous WODS-based file systems were implemented in user space using FUSE, which superimposes many reads on a write-intensive workload, reducing the effectiveness of the WODS. This article also contributes several techniques for exploiting write-optimization within existing kernel infrastructure. B e trFS dramatically improves performance of certain types of large scans, such as recursive directory traversals, as well as performance of arbitrary microdata operations, such as file creates, metadata updates, and small writes to files. B e trFS can make small, random updates within a large file 2 orders of magnitude faster than other local file systems. B e trFS is an ongoing prototype effort and requires additional data-structure tuning to match current general-purpose file systems on some operations, including deletes, directory renames, and large sequential writes. Nonetheless, many applications realize significant performance improvements on B e trFS. For instance, an in-place rsync of the Linux kernel source sees roughly 1.6--22 × speedup over commodity file systems.

Trusted, setuid-to-root binaries have been a substantial, long-lived source of privilege escalation vulnerabilities on Unix systems. Prior work on limiting privilege escalation has only considered privilege from the perspective of the administrator, neglecting the perspective of regular users---the primary reason for having setuid-to-root binaries.

Library OSes are a promising approach for applications to efficiently obtain the benefits of virtual machines, including security isolation, host platform compatibility, and migration. Library OSes refactor a traditional OS kernel into an application library, avoiding overheads incurred by duplicate functionality. When compared to running a single application on an OS kernel in a VM, recent library OSes reduce the memory footprint by an order-of-magnitude.

Government and commercial enterprises are increasingly considering cloud adoption. Clouds improve overall efficiency by consolidating a number of different clients' software virtual machines onto a smaller set of hardware resources. Unfortunately, this shared hardware also creates inherent side-channel vulnerabilities, which an attacker can use to leak information from a victim VM. Side-channel vulnerabilities are especially concerning when different principals are constrained by regulations. A classic example of these regulations are Chinese Wall policies for financial companies, which aim to protect the financial system from illicit manipulation by separating portions of the business with conflicting interests. Although efficient prevention of side channels is difficult within a single node, there is a unique opportunity within a cloud. This paper proposes a low-overhead approach to cloud wide information flow policy enforcement: identifying side channels which could potentially be used to violate a security policy through run-time introspection, and reactively migrating virtual machines to eliminate node-level side-channels. In this paper we describe CloudFlow-an information flow control extension for OpenStack. CloudFlow includes a novel, virtual machine introspection mechanism that is orders of magnitude faster than previous approaches. CloudFlow efficiently and transparently enforces information flow policies cloud-wide, including information leaks through undesirable side-channels. Additionally, CloudFlow has potential uses for cloud management and resource-efficient virtual machine scheduling.

An essential goal of Virtual Machine Introspection (VMI) is assuring security policy enforcement and overall functionality in the presence of an untrustworthy OS. A fundamental obstacle to this goal is the difficulty in accurately extracting semantic meaning from the hypervisor's hardware level view of a guest OS, called the semantic gap. Over the twelve years since the semantic gap was identified, immense progress has been made in developing powerful VMI tools. Unfortunately, much of this progress has been made at the cost of reintroducing trust into the guest OS, often in direct contradiction to the underlying threat model motivating the introspection. Although this choice is reasonable in some contexts and has facilitated progress, the ultimate goal of reducing the trusted computing base of software systems is best served by a fresh look at the VMI design space. This paper organizes previous work based on the essential design considerations when building a VMI system, and then explains how these design choices dictate the trust model and security properties of the overall system. The paper then observes portions of the VMI design space which have been under-explored, as well as potential adaptations of existing techniques to bridge the semantic gap without trusting the guest OS. Overall, this paper aims to create an essential checkpoint in the broader quest for meaningful trust in virtualized environments through VM introspection.

Decentralized Information Flow Control (DIFC) is a promising model for writing programs with powerful, end-to-end security guarantees. Current DIFC systems that run on commodity hardware can be broadly categorized into two types: language-level and operating system-level DIFC. Language solutions provide no guarantees against security violations on system resources such as files and sockets. Operating system solutions mediate accesses to system resources but are either inefficient or imprecise at monitoring the flow of information through fine-grained program data structures. This article describes Laminar, the first system to implement DIFC using a unified set of abstractions for OS resources and heap-allocated objects. Programmers express security policies by labeling data with secrecy and integrity labels and access the labeled data in security methods . Laminar enforces the security policies specified by the labels at runtime. Laminar is implemented using a modified Java virtual machine and a new Linux security module. This article shows that security methods ease incremental deployment and limit dynamic security checks by retrofitting DIFC policies on four application case studies. Replacing the applications' ad hoc security policies changes less than 10% of the code and incurs performance overheads from 5% to 56%. Compared to prior DIFC systems, Laminar supports a more general class of multithreaded DIFC programs efficiently and integrates language and OS abstractions.

Server applications must process requests as quickly as possible. Because some requests depend on earlier requests, there is often a tension between increasing throughput and maintaining the proper semantics for dependent requests. Operating system transactions make it easier to write reliable, high-throughput server applications because they allow the application to execute non-interfering requests in parallel, even if the requests operate on OS state, such as file data.

This paper revisits an old approach to operating system construc-tion, the library OS, in a new context. The idea of the library OS is that the personality of the OS on which an application depends runs in the address space of the application. A small, fixed set of abstractions connects the library OS to the host OS kernel, offering the promise of better system security and more rapid independent evolution of OS components.

TxBox is a new system for sand boxing untrusted applications. It speculatively executes the application in a system transaction, allowing security checks to be parallelized and yielding significant performance gains for techniques such as on-access anti-virus scanning. TxBox is not vulnerable to TOCTTOU attacks and incorrect mirroring of kernel state. Furthermore, TxBox supports automatic recovery: if a violation is detected, the sand boxed program is terminated and all of its effects on the host are rolled back. This enables effective enforcement of security policies that span multiple system calls.

Transactional memory promises to generalize transactional programming to mainstream languages and data structures. The purported benefit of transactions is that they are easier to program correctly than fine-grained locking and perform just as well. This performance claim is not always borne out because an application may violate a common-case assumption of the TM designer or because of external system effects. This paper carefully studies a range of factors that can adversely influence transactional memory performance. In order to help programmers assess the suitability of their code for transactional memory, this paper introduces a formal model of transactional memory as well as a tool, called Syncchar. Syncchar can predict the speedup of a conversion from locks to transactions within 25 % for the STAMP benchmarks. We also use the Syncchar tool to diagnose and eliminate a starvation pathology in the TxLinux kernel, improving the performance of the Modified Andrew Benchmark by 55% over Linux. The paper also presents the first detailed study of how the performance of user-level transactional programs (from the STAMP benchmarks) are influenced by factors outside of the transactional memory system. The study includes data about the interaction of transactional programs with the architecture, memory allocator, and compiler. Because many factors influence the performance of transactional programs, getting good performance from transactions is more difficult than commonly appreciated.

Transactional memory promises to make parallel programming easier than with fine-grained locking, while performing just as well. This performance claim is not always borne out because an application may violate a common-case assumption of the TM designer or because of external system effects. In order to help programmers assess the suitability of their code for transactional memory, this work introduces a formal model of transactional memory as well as a tool, called Syncchar. Syncchar can predict the speedup of a conversion from locks to transactions within 25% for the STAMP benchmarks. Because getting good performance from transactions is more difficult than commonly appreciated, developers need tools to tune transactional performance.

Decentralized information flow control (DIFC) is a promising model for writing programs with powerful, end-to-end security guarantees. Current DIFC systems that run on commodity hardware can be broadly categorized into two types: language-level and operating system-level DIFC. Language level solutions provide no guarantees against security violations on system resources, like files and sockets. Operating system solutions can mediate accesses to system resources, but are inefficient at monitoring the flow of information through fine-grained program data structures.

Applications must be able to synchronize accesses to operating system resources in order to ensure correctness in the face of concurrency and system failures. System transactions allow the programmer to specify updates to heterogeneous system resources with the OS guaranteeing atomicity, consistency, isolation, and durability (ACID). System transactions efficiently and cleanly solve persistent concurrency problems that are difficult to address with other techniques. For example, system transactions eliminate security vulnerabilities in the file system that are caused by time-of-check-to-time-of-use (TOCTTOU) race conditions. System transactions enable an unsuccessful software installation to roll back without disturbing concurrent, independent updates to the file system.

We present an efficient protocol for privacy-preserving evaluation of diagnostic programs, represented as binary decision trees or branching programs. The protocol applies a branching diagnostic program with classification labels in the leaves to the user's attribute vector. The user learns only the label assigned by the program to his vector; the diagnostic program itself remains secret. The program's owner does not learn anything. Our construction is significantly more efficient than those obtained by direct application of generic secure multi-party computation techniques.

This paper quantifies the effect of architectural design decisions onthe performance of TxLinux. TxLinux is a Linux kernel modifiedto use transactions in place of locking primitives in several key subsystems.We run TxLinux on MetaTM, which is a new hardwaretransaction memory (HTM) model.MetaTM contains features that enable efficient and correct interrupthandling for an x86-like architecture. Live stack overwrites can corrupt non-transactional stack memory and requires a smallchange to the transaction register checkpoint hardware to ensurecorrect operation of the operating system. We also propose stack based early release to reduce spurious conflicts on stack memorybetween kernel code and interrupt handlers.We use MetaTM to examine the performance sensitivity of individualarchitectural features. For TxLinux we find that Polka and SizeMatters are effective contention management policies, someform of backoff on transaction contention is vital for performance,and stalling on a transaction conflict reduces transaction restartrates, but does not improve performance. Transaction write setsare small, and performance is insensitive to transaction abort costsbut sensitive to commit costs.

An error occurs when software cannot complete a requested action as a result of some problem with its input, configuration, or environment. A high-quality error report allows a user to understand and correct the problem. Unfortunately, the quality of error reports has been decreasing as software becomes more complex and layered. End-users take the cryptic error messages given to them by programsand struggle to fix their problems using search engines and support websites. Developers cannot improve their error messages when they receive an ambiguous or otherwise insufficient error indicator from a black-box software component.

TxLinux is a variant of Linux that is the first operating system to use hardware transactional memory (HTM) as a synchronization primitive, and the first to manage HTM in the scheduler. This paper describes and measures TxLinux and discusses two innovations in detail: cooperation between locks and transactions, and theintegration of transactions with the OS scheduler. Mixing locks and transactions requires a new primitive, cooperative transactional spinlocks (cxspinlocks) that allow locks and transactions to protect the same data while maintaining the advantages of both synchronization primitives. Cxspinlocks allow the system to attemptexecution of critical regions with transactions and automatically roll back to use locking if the region performs I/O. Integrating the scheduler with HTM eliminates priority inversion. On a series ofreal-world benchmarks TxLinux has similar performance to Linux, exposing concurrency with as many as 32 concurrent threads on 32 CPUs in the same critical region.

A crucial part of the Networking course is the examination of and experimentation with network traffic data. Most standalone network traffic sniffers are quite expensive and those freely available on general purpose platforms (e.g., Linux or Windows) are quite cryptic. Because of this, we have developed NetSpy: a Java-based network sniffer that allows plug-in Java modules to analyze network data. These modules are written by students as part of their experimentation with traffic data. This paper describes the NetSpy system and the way we use this in Networking class.