SIIS Abstracts

Mitigating Attacks on Open Functionality in SMS-Capable Cellular Networks

The transformation of telecommunications networks from homogeneous closed systems providing only voice services to Internet-connected open networks that provide voice and data services presents significant security challenges. For example, recent research illustrated that a carefully crafted DoS attack via text messaging could incapacitate all voice communications in a metropolitan area with little more than a cable modem. This attack highlights a growing threat to these systems; namely, cellular networks are increasingly exposed to adversaries both in and outside the network. In this paper, we use a combination of modeling and simulation to demonstrate the feasibility of targeted text messaging attacks. Under realistic network conditions, we show that adversaries can achieve blocking rates of more than 70% with only limited resources. We then develop and characterize five techniques from within two broad classes of countermeasures - queue management and resource provisioning. Our analysis demonstrates that these techniques can eliminate or extensively mitigate even the most intense targeted text messaging attacks. We conclude by considering the tradeoffs inherent to the application of these techniques in current and next generation telecommunications networks.

Paper: traynor_ton08.pdf ( 2008)

Non-Invasive Methods for Host Certification

Determining whether a user or system is exercising appropriate security practices is difficult in any context. Such difficulties are particularly pronounced when uncontrolled or unknown platforms join public networks. Commonly practiced techniques used to vet these hosts, such as system scans, have the potential to infringe upon the privacy of users. In this paper, we show that it is possible for clients to prove both the presence and proper functioning of security infrastructure without allowing unrestricted access to their system. We demonstrate this approach, specifically applied to anti-virus security, by requiring clients seeking admission to a network to positively identify the presence or absence of malcode in a series of puzzles. The implementation of this mechanism and its application to real networks are also explored. In so doing, we demonstrate that it is not necessary for an administrator to be invasive to determine whether a client implements required security practices.

Exploiting Open Functionality in SMS-Capable Cellular Networks

Cellular networks are a critical component of the economic and social infrastructures in which we live. In addition to voice services, these networks deliver alphanumeric text messages to the vast majority of wireless subscribers. To encourage the expansion of this new service, telecommunications companies offer connections between their networks and the Internet. The ramifications of such connections, however, have not been fully recognized. In this paper, we evaluate the security impact of the SMS interface on the availability of the cellular phone network. Specifically, we describe the ability to deny voice service to cities the size of Washington D.C. and Manhattan with little more than a cable modem. Moreover, attacks targeting the entire United States are feasible with resources available to medium-sized zombie networks. This analysis begins with an exploration of the structure of cellular networks. We then characterize network behavior and explore a number of reconnaissance techniques aimed at effectively targeting attacks on these systems. We conclude by discussing countermeasures that mitigate or eliminate the threats introduced by these attacks.

Paper: traynor_jcs08.pdf ( 2007)

Round-Eye: A System for Tracking Nearest Surrounders in Moving Object Environments

This paper presents "Round-Eye", a system for tracking nearest surrounding objects (or nearest surrounders) in moving object environments. This system provides a platform for surveillance eapplications. The core part of this system is continuous nearest surrounder (NS) query that maintains views of the nearest objects at distinct angles from query points. This query differs from conventional spatial queries such as range queries and nearest neighbor queries as NS query considers both distance and angular aspects of objects with respect to a query point at the same time. In our system framework, a centralized server is dedicated (1) to collect locationu pdates of both objects and queries, (2)to determine which NS queries are invalidated in presence of object/query location changes and corresponding result changes if any, and (3) to refresh the affected query answers. To enhance the system performance in terms of processing time and network bandwidth consumption, we propose various techniques, namely, safe region, partial query reevaluation, and incremental query result update. Through simulations, we evaluate our system with the proposed techniques over a wide range of settings.

TARP: Ticket-based Address Resolution Protocol

IP networks fundamentally rely on the Address Resolution Protocol (ARP) for proper operation. Unfortunately, vulnerabilities in ARP enable a raft of Internet Protocol (IP)-based impersonation, man-in-the-middle, or Denial of Service (DoS) attacks. Proposed countermeasures to these vulnerabilities have yet to simultaneously address backward compatibility and cost requirements. This paper introduces the Ticket-based Address Resolution Protocol (TARP). TARP implements security by distributing centrally issued secure IP/Medium Access Control (MAC) address mapping attestations through existing ARP messages. We detail TARP and its implementation within the Linux operating system. We also detail the integration of TARP with the Dynamic Host Configuration Protocol (DHCP) for dynamic ticket distribution. Our experimental analysis shows that TARP improves the costs of implementing ARP security by as much as two orders of magnitude over existing protocols. We conclude by exploring a range of operational issues associated with deploying and administering ARP security.

Paper: sdarticle.pdf ( 2007)

Efficient Hybrid Security Mechanisms for Heterogeneous Sensor Networks

Many applications that make use of sensor networks require secure communication. Because asymmetric-key solutions are difficult to implement in such a resource-constrained environment, symmetric-key methods coupled with a priori key distribution schemes have been proposed to achieve the goals of data secrecy and integrity. These approaches typically assume that all nodes are similar in terms of capabilities and, hence, deploy the same number of keys in all sensors in a network to provide the aforementioned protections. In this paper, we demonstrate that a probabilistic unbalanced distribution of keys throughout the network that leverages the existence of a small percentage of more capable sensor nodes can not only provide an equal level of security, but also reduce the consequences of node compromise. To fully characterize the effects of the unbalanced key management system, we design, implement, and measure the performance of a complementary suite of key establishment protocols known as LIGER. Using their predeployed keys, nodes operating in isolation from external networks can securely and efficiently establish keys with each other. Should resources such as a backhaul link to a key distribution center (KDC) become available, networks implementing LIGER automatically incorporate and benefit from such facilities. Detailed experiments demonstrate that the unbalanced distribution in combination with the multimodal LIGER suite offers a robust and practical solution to the security needs in sensor networks.

Paper: tkczc07.pdf (June 2007)

ASR: Anonymous and Secure Reporting of Traffic Forwarding Activity in Mobile Ad Hoc Networks

Nodes forward data on behalf of each other in mobile ad hoc networks. In a civilian application, nodes are assumed to be selfish and rational, i.e., they pursue their own self-interest. Hence, the ability to accurately measure traffic forwarding is critical to ensure proper network operation. These measurements are also often used to credit nodes based on their level of participation, or to detect loss. Past solutions employ neighbor monitoring and reporting on traffic forwarding of nodes. These methods are not applicable in civilian networks in which neighbor nodes lack the desire or ability to perform the monitoring function. Such environments occur frequently in which neighbor hosts are resource constrained, or in networks where directional antennas are used and reliable eavesdropping is difficult or impossible.

In this paper, we propose a protocol that uses nodes on the data path to securely produce packet forwarding reports. Reporting nodes are chosen randomly and secretly so that malicious nodes cannot modify their behavior based upon the monitoring point. The integrity and authenticity of reports are preserved through the use of secure link layer acknowledgments and monitoring reports. The robustness of the reporting mechanism is strengthened by forwarding the report to multiple destinations (source and destination). We explore the security, cost, and accuracy of our protocol.

Paper: asr_winet.pdf (May 2007)

Origin Authentication in Interdomain Routing

Attacks against Internet routing are increasing in number and severity. Contributing greatly to these attacks is the absence of origin authentication; there is no way to validate claims of address ownership or location. The lack of such services not only enables attacks by malicious entities, but also indirectly allows seemingly inconsequential misconfigurations to disrupt large portions of the Internet. This paper considers the semantics, design, and costs of origin authentication in interdomain routing. We formalize the semantics of address delegation and use on the Internet, and develop and characterize original, broad classes of origin authentication proof systems. We estimate the address delegation graph representing the current use of IPv4 address space using available routing data. This effort reveals that current address delegation is dense and relatively static: as few as 16 entities perform 80% of the delegation on the Internet. We conclude by evaluating the proposed services via trace-based simulation, which demonstrates that the enhanced proof systems can significantly reduce resource costs associated with origin authentication.

Paper: comnet06.pdf (November 2006)

Enforcing Provisioning and Authorization Policy in the Antigone System

Works in communication security policy have recently focused on general-purpose policy languages and evaluation algorithms. However, because the supporting frameworks often defer enforcement, the correctness of a realization of these policies in software is limited by the quality of domain-specific implementations. This paper introduces the Antigone communication security policy enforcement framework. The Antigone framework fills the gap between representations and enforcement by implementing and integrating the diverse security services needed by policy. Policy is enforced by the run-time composition, configuration, and regulation of security services. We present the Antigone architecture, and demonstrate non-trivial applications and policies. A profile of policy enforcement performance is developed, and key architectural enhancements identified. We conclude by considering the advantages and disadvantages of a broad range of software architectures appropriate for policy enforcement.

Paper: jcs05.pdf (November 2006)

Methods and Limitations of Security Policy Reconciliation

A security policy specifies session participant requirements. However, existing frameworks provide limited facilities for the automated reconciliation of participant policies. This paper considers the limits and methods of reconciliation in a general-purpose policy model. We identify an algorithm for efficient two-policy reconciliation, and show that, in the worst-case, reconciliation of three or more policies is intractable. Further, we suggest efficient heuristics for the detection and resolution of intractable reconciliation. Based upon the policy model, we describe the design and implementation of the Ismene policy language. The expressiveness of Ismene, and indirectly of our model, is demonstrated through the representation and exposition of policies supported by existing policy languages. We conclude with brief notes on the integration and enforcement of Ismene policy within the Antigone communication system.

Paper: tissec06.pdf (August 2006)

Security Policy Enforcement in the Antigone System

Paper: jcs05.pdf ( 2005)

The Sleep Deprivation Attack in Sensor Networks: Analysis and Methods of Defense

The ability of sensor nodes to enter a low power sleep mode is very useful for extending network longevity. We show how adversary nodes can exploit clustering algorithms to ensure their selection as cluster heads for the purpose of launching attacks that prevent victim nodes from sleeping. We present two such attacks: the barrage attack and the sleep deprivation attack. The barrage attack bombards victim nodes with legitimate requests, whereas the sleep deprivation attack makes requests of victim nodes only as often as is necessary to keep the victims awake. We show that while the barrage attack causes its victims to spend slightly more energy, it is more easily detected and requires more effort on behalf of the attacker. Thus we have focused our research on the sleep deprivation attack. Our analysis indicates that this attack can nullify any energy savings obtained by allowing sensor nodes to enter sleep mode. We also analyze three separate methods for mitigating this attack: the random vote scheme, the round robin scheme, and the hash-based scheme. We have evaluated these schemes based upon their ability to reduce the adversary's attack, the amount of time required to select a cluster head, and the amount of energy required to perform each scheme. We have found that of the three clustering methods analyzed, the hash-based scheme is the best at mitigating the sleep deprivation attack.

Paper: ijdsn05.pdf (June 2005)

Analysis of Security Vulnerabilities in the Movie Production and Distribution Process

Unauthorized copying of movies is a major concern for the motion picture industry. While unauthorized copies of movies have been distributed via portable physical media for some time, low-cost, high-bandwidth Internet connections and peer-to-peer file sharing networks provide highly efficient distribution media. Many movies are showing up on file sharing networks shortly after, and in some cases prior to, theatrical release. It has been argued that the availability of unauthorized copies directly affects theater attendance and DVD sales, and hence represents a major financial threat to the movie industry. Our research attempts to determine the source of unauthorized copies by studying the availability and characteristics of recent popular movies in file sharing networks. We developed a data set of 312 popular movies and located one or more samples of 183 of these movies on file sharing networks, for a total of 285 movie samples. 77% of these samples appear to have been leaked by industry insiders. Most of our samples appeared on file sharing networks prior to their official consumer DVD release date. Indeed, of the movies that had been released on DVD as of the time of our study, only 5% first appeared after their DVD release date on a web site that indexes file sharing networks, indicating that consumer DVD copying currently represents a relatively minor factor compared with insider leaks. We perform a brief analysis of the movie production and distribution process and identify potential security vulnerabilities that may lead to unauthorized copies becoming available to those who may wish to redistribute them. Finally, we offer recommendations for reducing security vulnerabilities in the movie production and distribution process.

Paper: tcpolicy04.pdf (August 2004)

Consistency Analysis of Authorization Hook Placement in the Linux Security Modules Framework

We present a consistency analysis approach to assist the Linux community in verifying the correctness of authorization hook placement in the Linux Security Modules (LSM) framework. The LSM framework consists of a set of authorization hooks inserted into the Linux kernel to enable additional authorizations to be performed (e.g., for mandatory access control). When compared to system call interposition, authorization within the kernel has both security and performance advantages, but it is more difficult to verify that placement of the LSM hooks ensures that all the kernel's security-sensitive operations are authorized. Static analysis has been used previously to verified mediation (i.e., that some hook mediates access to a security-sensitive operation), but that work did not determine whether the necessary set of authorizations were checked. In this paper, we develop an approach to test the consistency of the relationships between security-sensitive operations and LSM hooks. The idea is that whenever a security-sensitive operation is performed as part of specifiable event, a particular set of LSM hooks must have mediated that operation. This work demonstrates that the number of events that impact consistency is manageable and that the notion of consistency is useful for verifying correctness. We describe our consistency approach for performing verification, the implementation of run-time tools that implement this approach, the anomalous situations found in an LSM-patched Linux 2.4.16 kernel, and an implementation of a static analysis version of this approach.

Paper: tissec2004.pdf (May 2004)

Policy Management Using Access Control Spaces

We present the concept of an access control space and investigate how it may be useful in managing access control policies. An access control space represents the permission assignment state of a subject or role. For example, the set of permissions explicitly assigned to a role defines its specified subspace, and the set of constraints precluding assignment to that role defines its prohibited subspace. In analyzing these subspaces, we identify two problems: (1) often a significant portion of an access control space has unknown assignment semantics, which indicates that the policy is underspecified; and (2) often high-level assignments and constraints that are easily understood result in conflicts, where resolution often leads to significantly more complex specifications. We have developed a prototype system, called Gokyo, that computes access control spaces. Gokyo identifies the unknown subspace to assist system administrators in developing more complete policy specifications. Also, Gokyo identifies conflicting subspaces and enables system administrators to resolve conflicts in a variety of ways in order to preserve the simplicity of constraint specification. We demonstrate Gokyo by analyzing a Web server policy example and examine its utility by applying it to the SELinux example policy. Even for the extensive SELinux example policy, we find that only eight additional expressions are necessary to resolve Apache administrator policy conflicts.

Paper: tissec2003.pdf (August 2003)

Practical safety in flexible access control models

Assurance that an access control configuration will not result in the leakage of a right to an unauthorized principal, called safety, is fundamental to ensuring that the most basic of access control policies can be enforced. It has been proven that the safety of an access control configuration cannot be decided for a general access control model, such as Lampson's access matrix, so safety is achieved either through the use of limited access control models or the verification of safety via constraints. Currently, almost all safety critical systems use limited access control models, such as Bell--LaPadula or Domain and Type Enforcement, because constraint expression languages are far too complex for typical administrators to use properly. However, researchers have identified that most constraints belong to one of a few basic types, so our goal is to develop a constraint expression model in which these constraints can be expressed in a straightforward way and extensions can be made to add other constraints, if desired. Our approach to expressing constraints has the following properties: (1) an access control policy is expressed using a graphical model in which the nodes represent sets (e.g., of subjects, objects, etc.) and the edges represent binary relationships on those sets and (2) constraints are expressed using a few, simple set operators on graph nodes. The basic graphical model is very simple, and we extend this model only as necessary to satisfy the identified constraint types. Since the basic graphical model is also general, further extension to support other constraints is possible, but such extensions should be made with caution as each increases the complexity of the model. Our hope is that by keeping the complexity of constraint expression in check, flexible access control models, such as role-based access control, may also be used for expressing access control policy for safety-critical systems.

Paper: tissec2001.pdf ( 2001)

Demand Transformation Analysis for Concurrent Constraint Programs

This paper presents a demand transformation analysis that maps apredicate's output demands to its input demands. This backward dataflowanalysis for concurrent constraint programs is constructed in theframework of abstract interpretation. In the context of streamparallelism, this analysis identifies an amount of input data for whichpredicate execution can safely wait without danger of introducingdeadlock. We assume that programs are well-moded and prove that ouranalysis is safe. We have constructed an implementation of this analysisand tested it on some small, illustrative programs and have determinedthat it gives useful results in practice. We identify severalapplications of the analysis results to distributed implementations ofconcurrent constraint languages, including thread construction andcommunication granularity. This analysis will enable exisitingcomputation cost estimation analyses to be applied to stream-parallellogic languages.

Higher-Order Uncurrying

We present a formal specification of unCurrying for a higher-order,functional language with ML-style let-polymorphism. This specificationsupports the general unCurrying of functions, even for functions thatare passed as arguments or returned as values. The specification alsosupports partial unCurrying of any consecutive parameters of a function,rather than only unCurrying all of a function's parameters. We presentthe specification as a deductive system that axiomatizes a judgmentrelating a source term with an unCurried form of the term. We prove thatthis system relates only typable terms and that it is correct withrespect to an operational semantics. We define a practical algorithm,based on algorithm W, that implements unCurrying and prove thisalgorithm sound and complete with respect to the deductive system. Thisalgorithm generates maximally unCurried forms of source terms. Theseresults provide a declarative framework for reasoning about unCurryingand support a richer form of unCurrying than is currently found incompilers for functional languages.

Flexible Control of Downloaded Executable Content

We present a security architecture that enables system and application a ccess control requirements to be enforced on applications composed from downloaded executable content. Downloaded executable content consists of messages downloaded from remote hosts that contain executables that run, upon receipt, on the downloading principal's machine. Unless restricted, this content can perform malicious actions, including accessing its downloading principal's private data and sending messages on this principal's behalf. Current security architectures for controlling downloaded executable content (e.g., JDK 1.2) enable specification of access control requirements for content based on its provider and identity. Since these access control requirements must cover every legal use of the class, they may include rights that are not necessary for a particular application of content. Therefore, using these systems, an application composed from downloaded executable content cannot enforce its access control requirements without the addition of application-specific security mechanisms. In this paper, we define an access control model with the following properties: (1) system administrators can define system access control requirements on applications and (2) application developers can use the same model to enforce application access control requirements without the need for ad hoc security mechanisms. This access control model uses features of role-based access control models to enable (1) specification of a single role that applies to multiple application instances; (2) selection of a content's access rights based on the content's application and role in the application; (3) consistency maintained between application state and content access rights; and (4) control of role administration. We detail a system architecture that uses this access control model to implement secure collaborative applications. Lastly, we describe an implementation of this architecture, called the Lava security architecture.

Paper: tissec1999.pdf (May 1999)

A flexible security system for using Internet content

The Internet and World Wide Web have introduced a powerful new way to acquire content. Previously, users had to either buy or order content on coded disks. They can now download executable code and applications directly. From the users' viewpoint, this decreases the amount of software stored on their machines. It also lets content providers customize applications by combining different vendors' content. Downloading content from the Internet brings risks: content that appears reputable may be malicious, given system access it can damage or destroy data. To contend with this risk, the author developed FlexxGuard, a flexible interpreter that dynamically derives protection domains and uses those domains to authorize content operations.

Rootkit-Resistant Disks

Rootkits are now prevalent in the wild. Users affected by rootkits are subject to the abuse of their data and resources, often unknowingly. Such malware becomes even more dangerous when it is persistent--infected disk images allow the malware to exist across reboots and prevent patches or system repairs from being successfully applied. In this paper, we introduce rootkit-resistant disks (RRD) that label all immutable system binaries and configuration files at installation time. During normal operation, the disk controller inspects all write operations received from the host operating system and denies those made for labeled blocks. To upgrade, the host is booted into a safe state and system blocks can only be modified if a security token is it attached to the disk controller. By enforcing immutability at the disk controller, we prevent a compromised operating system from infecting its on-disk image. We implement the RRD on a Linksys NSLU2 network storage device by extending the I/O processing on the embedded disk controller running the SlugOS Linux distribution. Our performance evaluation shows that the RRD exhibits an overhead of less than 1% for filesystem creation and less than 1.5% during I/O intensive Postmark benchmarking. We further demonstrate the viability of our approach by preventing a rootkit collected from the wild from infecting the OS image. In this way, we show that RRDs not only prevent rootkit persistence, but do so in an efficient way.

Composition Attacks and Auxiliary Information in Data Privacy

Privacy is an increasingly important aspect of data publishing. Reasoning about privacy, however, is fraught with pitfalls. One of the most significant is the auxiliary information (also called external knowledge, background knowledge, or side information) that an adversary gleans from other channels such as the web, public records, or domain knowledge. This paper explores how one can reason about privacy in the face of rich, realistic sources of auxiliary information. Specifically, we investigate the effectiveness of current anonymization schemes in preserving privacy when multiple organizations independently release anonymized data about overlapping populations.

We investigate composition attacks, in which an adversary uses independently anonymized releases to breach privacy. We explain why recently proposed models of limited auxiliary information fail to capture composition attacks. Our experiments demonstrate that even a simple instance of a composition attack can breach privacy in practice, for a large class of currently proposed techniques. The class includes $k$-anonymity and several recent variants.
On a more positive note, certain randomization-based notions of privacy (such as differential privacy) provably resist composition attacks and, in fact, the use of arbitrary side information. This resistance enables ``stand-alone" design of anonymization schemes, without the need for explicitly keeping track of other releases. We provide a precise formulation of this property, and prove that an important class of relaxations of differential privacy also satisfy the property. This significantly enlarges the class of protocols known to enable modular design.

Effective Blame for Information-Flow Violations

Programs trusted with secure data should not release this data in ways contrary to system policy. However, when a program contains an illegal flow of information, current information-flow reporting techniques are inadequate for determining the cause of the error. Reasoning about information-flow errors can be difficult, as the flows involved can be quite subtle. We present a general model for information-flow blame that can explain the source of such security errors in code. This model is implemented by changing the information-flow verification procedure to: (1) generate supplementary information to reveal otherwise hidden program dependencies; (2) modify the constraint solver to construct a blame dependency graph; and (3) develop an explanation procedure that returns a {\em complete} and {\em minimal} error report. Our experiments show that information-flow errors can generally be explained and resolved by viewing only a small fraction of the total code.

Verifying Compliance of Trusted Programs

Every system depends on trusted programs for its secure operation. A trustedprogram is trusted to only perform safe operations despite have theauthority to perform unsafe operations; for example, administrative programs, root network daemons, and many others. Currently, these programs are trusted without concrete justification. The emergence of tools for building applications that guarantee policy enforcement, such as security-typed languages (STLs), and mandatory access control systems, such as user-level policy servers, finally offer a basis for justifying trust in such programs. If the operations authorized by the program policy are also authorized by system policy, then the program complies with the system. However, program policy is not directly comparable with system policy, making compliance checking difficult in general. We observe that the integrity of trusted programs must dominate the integrity of system data (the PIDSI approach). Using this insight, we assign trusted program objects to a higherintegrity level than system data objects, resulting in a simplified programpolicy that enables automated compliance verification. We find that thisassumption is consistent with the SELinux reference policy for its trustedprograms.

Measuring Integrity on Mobile Phone Systems

Mobile phone security is a relatively new field that is gathering momentum in the wake of rapid advancements in phone system technology. Mobile phones are now becoming sophisticated smart phones that provide services beyond basic telephony, such as supporting third-party applications. Such third-party applications may be security-critical, such as mobile banking, or may be untrusted applications, such as downloaded games. Our goal is to protect the integrity of such critical applications from potentially untrusted functionality, but we find that existing mandatory access control approaches are too complex and do not provide formal integrity guarantees. In this work, we leverage the simplicity inherent to phone system environments to develop a compact SELinux policy that can be used to justify the integrity of a phone system using the Policy Reduced Integrity Measurement Architecture (PRIMA) approach. We show that the resultant policy enables systems to be proven secure to remote parties, enables the desired functionality for installing and running trusted programs, and the resultant SELinux policy is over 90% smaller in size. We envision that this approach can provide an outline for how to build high integrity phone systems.

Realizing Massive-Scale Conditional Access Systems Through Attribute-Based Cryptosystems

The enormous growth in the diversity of content services such as IPtv has highlighted the inadequacy of the accompanying content security: existing security mechanisms scale poorly, require complex and often costly dedicated hardware, or fail to meet basic security requirements. New security methods are needed. In this paper, we explore the ability of attribute-based encryption (ABE) to meet the unique performance and security requirements of conditional access systems such as subscription radio and pay-per-view television. We show through empirical study that costs of ABE make its direct application inappropriate, but present constructions that mitigate its incumbent costs. We develop an extensive simulation that allows us to explore the performance of a number of virtual hardware configurations and construction parameters over workloads developed from real subscription and television audiences. These simulations show that we can securely deliver high quality content to viewerships of the highest rated shows being broadcast today, some in excess of 26,000,000 viewers. It is through these experiments that we expose the viability of not only ABE-based content delivery, but applicability of ABE systems to large-scale distributed systems.

Paper: traynor_ndss08.pdf (February 2008)

Channels: Runtime System Infrastructure for Security-typed Languages

Security-typed languages (STLs) are powerful tools for provably implementing policy in applications. The programmer maps policy onto programs by annotating types with information flow labels, and the STL compiler guarantees that data always obeys its label as it flows within an application. As data flows into or out of an application, however, a runtime system is needed to mediate between the information flow world within the application and the non-information flow world of the operating system. In the few existing STL applications, this problem has been handled in ad hoc ways that hindered software engineering and security analysis. In this paper, we present a principled approach to STL runtime system development along with policy infrastructure and class abstractions for the STL, Jif, that implement these principles. We demonstrate the effectiveness of our approach by using our infrastructure to develop a firewall application, FLOWWALL, that provably enforces its policy.

Paper: hmm07.pdf (December 2007)

Establishing and Sustaining System Integrity via Root of Trust Installation

Integrity measurements provide a means by which distributed systems can assess the trustability of potentially compromised remote hosts. However, current measurement techniques simply assert the identity of software, but provide no indication of the ongoing status of the system or its data. As a result, a number of significant vulnerabilities can result if the system is not configured and managed carefully. To improve the management of a system�s integrity, we propose a Root of Trust Installation (ROTI) as a foundation for high integrity systems. A ROTI is a trusted system installer that also asserts the integrity of the trusted computing base software and data that it installs to enable straightforward, comprehensive integrity verification for a system. The ROTI addresses a historically limiting problem in integrity measurement: determining what constitutes a trusted system state in any heterogeneous, evolving environment. Using the ROTI, a high integrity system state is defined by its installer, thus enabling a remote party to verify integrity guarantees that approximate classical integrity models (e.g., Biba). In this paper, we examine what is necessary to prove the integrity of the trusted computing base (sCore) of a distributed security architecture, called the SRM. We describe the design and implementation of our custom ROTI sCore installer and study the costs and effectiveness of binding system integrity to installation in the distributed SRM. This demonstration shows that strong integrity guarantees can be efficiently achieved in large, diverse environments with limited administrative overhead.

Paper: acsac07.pdf (December 2007)

Smooth Sensitivity and Sampling in Private Data Analysis

We introduce a new, generic framework for private data analysis. The goal of private data analysis is to release aggregate information about a data set while protecting the privacy of the individuals whose information the data set contains. Our framework allows one to release functions f of the data with instance-based additive noise. That is, the noise magnitude is determined not only by the function we want to release, but also by the database itself. One of the challenges is to ensure that the noise magnitude does not leak information about the database. To address that, we calibrate the noise magnitude to the smooth sensitivity of f on the database x -- a measure of variability of f in the neighborhood of the instance x. The new framework greatly expands the applicability of output perturbation, a technique for protecting individuals� privacy by adding a small amount of random noise to the released statistics. To our knowledge, this is the first formal analysis of the effect of instance-based noise in the context of data privacy.

Our framework raises many interesting algorithmic questions. Namely, to apply the framework one must compute or approximate the smooth sensitivity of f on x. We show how to do this efficiently for several different functions, including the median and the cost of the minimum spanning tree. We also give a generic procedure based on sampling that allows one to release f(x) accurately on many databases x. This procedure is applicable even when no efficient algorithm for approximating smooth sensitivity of f is known or when f is given as a black box. We illustrate the procedure by applying it to k-SED (k-means) clustering and learning mixtures of Gaussians.

Paper: nrs07.pdf (August 2007)

On Attack Causality in Internet-Connected Cellular Networks

The emergence of connections between telecommunications networks and the Internet creates significant avenues for exploitation. For example, through the use of small volumes of targeted traffic, researchers have demonstrated a number of attacks capable of denying service to users in major metropolitan areas. While such investigations have explored the impact of specific vulnerabilities, they neglect to address a larger issue - how the architecture of cellular networks makes these systems susceptible to denial of service attacks. As we show in this paper, these problems have little to do with a mismatch of available bandwidth. Instead, they are the result of the pairing of two networks built on fundamentally opposing design philosophies. We support this a claim by presenting two new attacks on cellular data services. These attacks are capable of preventing the use of high-bandwidth cellular data services throughout an area the size of Manhattan with less than 200Kbps of malicious traffic. We then examine the characteristics common to these and previous attacks as a means of explaining why such vulnerabilites are artifacts of design rigidity. Specifically, we show that the shoehorning of data communications protocols onto a network rigorously optimized for the delivery of voice causes that network to fail under modest loads.

Paper: usec07.pdf (August 2007)

Email Communities of Interest

Email has become an integral and sometimes overwhelming part of users' personal and professional lives. In this paper, we measure the flow and frequency of user email toward the identification of communities of interest (COI)--groups of users that share common goals or associations. If detectable, such associations will be useful in automating email management, e.g., topical classification, flagging important missives, and SPAM mitigation. An analysis of a large corpus of university email is used to drive the generation and validation of algorithms for automatically determining COIs. We examine the effect of the structure and transience of COIs with the algorithms and validate algorithms using user-labeled data. Our analysis shows that the proposed algorithms correctly identify email as being sent from the human-identified COI with high accuracy. The structure and characteristics of COIs are explored analytically and broader conclusions about email use are posited.

Paper: jrb07_emailcoi.pdf (August 2007)

Analysis of IPv4 Address Space Delegation Structure

The Internet has grown tremendously in terms of the number of users who rely on it and the number of organizations that are connected to it. Characterizing how this growth affects its structure and topology is vitally important to determine the fundamental characteristics and limitations that must be handled, such as address space exhaustion; understanding the process of allocating and delegating address space can help to answer these questions. In this paper, we analyze BGP routing data to study the structure and growth of IPv4 address space allocation, fragmentation and usage. We explore the notion of delegation relationships among prefixes and use this information to construct an autonomous system (AS) delegation tree. We show that delegation in the Internet is not significantly correlated to the underlying topology or AS customer-provider relationships. We also analyze the fragmentation and usage of address space over a period of five years and examine prefixes that are delegated by organizations vs. those that are not delegated. We notice that the address space usage due to delegating prefixes is increasing at the same rate as the address space usage due to non-delegating prefixes. This indicates that fragmentation rate of the address space is actually almost a constant with respect to total address usage. Additionally, we show that most delegation is performed by a small number of organizations, which may aid in the implementation of a public-key infrastructure for the Internet.

Paper: iscc07.pdf (July 2007)

From Trusted to Secure: Building and Executing Applications that Enforce System Security

Commercial operating systems have recently introduced mandatory access controls (MAC) that can be used to ensure system-wide data confidentiality and integrity. These protections rely on restricting the flow of information between processes based on security levels. The problem is, there are many applications that defy simple classification by security level, some of them essential for system operation. Surprisingly, the common practice among these operating systems is simply to mark these applications as "trusted", and thus allow them to bypass label protections. This compromise is not a limitation of MAC or the operating system services that enforce it, but simply a fundamental inability of any operating system to reason about how applications treat sensitive data internally---and thus the OS must either restrict the data that they receive or trust them to handle it correctly. These practices were developed prior to the advent security-typed languages. These languages provide a means of reasoning about how the OS's sensitive data is handled within applications. Thus, applications can be shown to enforce system security by guaranteeing, in advance of execution, that they will adhere to the OS's MAC policy. In this paper, we provide an architecture for an operating system service, that integrate security-typed language with operating system MAC services. We have built an implementation of this service, called SIESTA, which handles applications developed in the security-typed language, Jif, running on the SELinux operating system. We also provide some sample applications to demonstrate the security, flexibility and efficiency of our approach.

Paper: tech07-hicks.pdf (June 2007)

Configuration Management at Massive Scale: System Design and Experience

The development and maintenance of network device configurations is one of the central challenges faced by large network providers. Current network management systems fail to meet this challenge primarily because of their inability to adapt to rapidly evolving customer and provider-network needs, and because of mismatches between the conceptual models of the tools and the services they must support. In this paper, we present the PRESTO configuration management system that attempts to address these failings in a comprehensive and flexible way. Developed for and deployed over the last 4 years within a large ISP network, PRESTO constructs device-native configurations based on the composition of configlets representing different services or service options. Configlets are compiled by extracting and manipulating data from external systems as directed by the PRESTO configuration scripting and template language. We outline the configuration management needs of large-scale network providers, introduce the PRESTO system and configuration language, and demonstrate the use, workflows, and ultimately the platform's flexibility via an example of VPN service. We conclude by considering future work and reflect on the operators� experiences with PRESTO.

Paper: usenix07.pdf (June 2007)

A Logical Specification and Analysis for SELinux MLS Policy

The SELinux mandatory access control (MAC) policy has recently added a multi-level security (MLS) model which is able to express a fine granularity of control over a subject's access rights. The problem is that the richness of this policy makes it impractical to verify, by hand, that a given policy has certain important information flow properties or is compliant with another policy. To address this, we have modeled the SELinux MLS policy using a logical specification and implemented that specification in the Prolog language. Furthermore, we have developed some analyses for testing the properties of a given policy as well an algorithm to determine whether one policy is compliant with another. We have implemented these analyses in Prolog and compiled our implementation into a tool for SELinux MLS policy analysis, called PALMS. Using PALMS, we verified some important properties of the SELinux MLS reference policy, namely that it satisfies the simple security condition and *-property defined by Bell and LaPadula.

Paper: sacmat07.pdf (June 2007)

Managing the Risk of Covert Information Flows in Virtual Machine Systems

Flexible mandatory access control (MAC) enforcement is nowavailable for virtual machine systems. For example, the sHype MAC systemfor the Xen virtual machine monitor is part of the mainline Xendistribution. Such systems offer the isolation of VM systems with theflexible security of MAC enforcement. A problem is that such MAC VMsystems will only be assured at modest levels (e.g., Common CriteriaEAL4), so they may contain covert channels. Covert channels are oftendifficult to identify and harder to remove, so we propose an approach tomanage possible covert leakage to enable verification of securityguarantees. Typically, covert channels are outside of access controlpolicies, but we propose an approach that includes both overt flows andcovert flows to assess the possible risk of information leakage due totheir combination. We define the concept of a risk flow policy thatdescribes the authorized risks due to covert flows. In this paper, weevaluate the ability of four policy models to express risk flowpolicies. Further, we examine how such policies will be enforced in VMsystems. We find that variants of the Chinese Wall model andBell-LaPadula model have features necessary to express risk flowpolicies. Further, we find that such policies can be enforced in thecontext of sHype's Type Enforcement model.

Privacy Preserving Communication in MANETs

Mobile ad hoc networks often support sensitive applications. These applications may require that users' identity, location, and correspondents be kept secret. This is a challenge in a MANET because of the cooperative nature of the network and broadcast nature of the communication media. In this paper, we propose a Privacy Preserving Communication System (PPCS) which provides a comprehensive solution to anonymize communication endpoints, keep the location and identifier of a node unlinkable, and mask the existence of communication flows. We present an analysis of the security of PPCS against passive internal attackers, provide a qualitative discussion on its strength against external attackers, and characterize its performance trade-offs. The simulation results demonstrate that PPCS has only 3% lower packet delivery ratio than existing multi-path routing protocols, while effectively providing privacy service in MANETs.

Paper: smac07.pdf (June 2007)

Toward Valley-Free Inter-domain Routing

ASes in inter-domain routing receive little information about the quality of the routes they receive. This lack of information can lead to inefficient and even incorrect routing. In this paper, we quantitatively characterize BGP announcements that violate the so-called valley-free property - an indicator that universal best practices are not being preserved in the propagation of routes. Our analysis indicates that valley announcements are more pervasive than expected. Approximately ten thousand valley announcements appear every day and involve a substantial number of prefixes. 11% of provider ASes propagate valley announcements, with a majority of violations happening at intermediate providers. We find that large surges of violating announcements can be attributed to transient configuration errors. We further propose a dynamic mechanism that provides route propagation information as transitive attributes of BGP. This information implicitly reflects the policies of the ASes along the path, without revealing the relationship of each AS pair. BGPspeaking routers use this information to identify (and presumably avoid) routes that violate the valley-free property.

Paper: icc07.pdf (June 2007)

Mining Security-Sensitive Operations in Legacy Code using Concept Analysis

This paper presents an approach to statically retrofit legacy servers with mechanisms for authorization policy enforcement. The approach is based upon the observation that security-sensitive operations performed by a server are characterized by idiomatic resource manipulations, called fingerprints. Candidate fingerprints are automatically mined by clustering resource manipulations using concept analysis. These fingerprints are then used to identify security-sensitive operations performed by the server. Case studies with three real-world servers show that the approach can be used to identify security-sensitive operations with a few hours of manual effort and modest domain knowledge.

Paper: icse07.pdf (May 2007)

Leveraging Identity-based Cryptography for Node ID Assignment in Structured P2P Systems

Structured peer-to-peer systems have grown enormously because of their scalability, efficiency and reliability. These systems assign a unique identifier to each user and object. However, current assignment schemes allow an adversary to carefully select user IDs and/or simultaneously obtain many pseudo-identities -- leading ultimately to an ability to disrupt the P2P system in very targeted (and dangerous) ways. In this paper, we propose novel ID assignment protocols based on identity-based cryptography. This approach permits the acquisition of node IDs to be tightly regulated without many of the complexities and costs associated with traditional certificate solutions. We broadly consider the security requirements of ID assignment and present three protocols representing distinct threat and trust models. A detailed empirical study of the protocols is given. Our analysis shows that the cost of our identity-based protocols is nominal, and that the associated identity services can scale to millions of users using a limited number of servers.

Paper: ssnds07.pdf (May 2007)

Limiting Sybil Attacks in Structured Peer-to-Peer Networks

One practical limitation of structured peer-to-peer (P2P) networks is that they are frequently subject to Sybil attacks: malicious parties can compromise the network by generating and controlling large numbers of shadow identities. In this paper, we propose an admission control system that mitigates Sybil attacks by adaptively constructing a hierarchy of cooperative peers. The admission control system vets joining nodes via client puzzles. A node wishing to join the network is serially challenged by the nodes from a leaf to the root of the hierarchy. Nodes completing the puzzles of all nodes in the chain are provided a cryptographic proof of the vetted identity. We evaluate our solution and show that an adversary must perform days or weeks of effort to obtain even a small percentage of nodes in small P2P networks, and that this effort increases linearly with the size of the network. We further show that we can place a ceiling on the number of IDs any adversary may obtain by requiring periodic reassertion of the IDs continued validity.

Paper: infocom07.pdf (May 2007)

Integrating SELinux with Security-typed Languages

Traditionally, operating systems have enforced MAC and information flow policies with minimal dependence on application programs. However, there are many cases where systems depend on user-level programs to enforce information flows. Previous approaches to handling this problem, such as privilege-separation of application components or assuming trust in application information flow enforcement, are prone to error and cumbersome to manage. On the other hand, recent advances in the area of security-typed languages have enabled the development of realistic applications with formally and automatically verified information flow controls. In this paper, we examine what it takes to integrate information flow enforcement of applications written in a security-typed extension of Java (called Jif) with SELinux. To this end, we have extended the Jif infrastructure to support interaction with SELinux security contexts, and we describe the SELinux policy and system calls which are necessary for a successful integration. We have also identified the need for further services, such as a means of formally verifying compliance between information flow policies. We have demonstrated the utility, flexibility and security of our approach by constructing a prototype multi-level secure email client.

Paper: jpselinux06.pdf (March 2007)

Scrambling Adversarial Errors Using Few Random Bits

When communicating over a noisy channel, it is typically much easier to deal with random, independent errors with a known distribution than with adversarial errors. This paper looks at how one can use schemes designed for random errors in an adversarial context, at the cost of relatively few additional random bits and without using unproven computational assumptions.

The basic approach is to permute the positions of a bit string using a permutation drawn from a $t$-wise independent family, where $t=o(n)$. This leads to two new results:

1. We construct *computationally efficient* information reconciliation protocols correcting $pn$ adversarial binary Hamming errors with optimal communication and entropy loss $n(h(p)+o(1))$ bits, where $n$ is the length of the strings and $h()$ is the binary entropy function. Information reconciliation protocols are important tools for dealing with noisy secrets in cryptography; they are also used to synchronize remote copies of large files.

2. We improve the randomness complexity (key length) of efficiently decodable capacity-approaching "private codes" from $\Theta(n\log n)$ to $n+o(n)$.

We also present a simplified proof of an existential result on private codes due to Langberg (FOCS '04).

Paper: s07.pdf (January 2007)

Understanding Practical Application Development in Security-typed Languages

Security-typed languages are an evolving tool for implementing systems with provable security guarantees. However, to date, these tools have only been used to build simple "toy" programs. As described in this paper, we have developed the first real-world, security-typed application: a secure email system written in the Java language variant Jif. Real-world policies are mapped onto the information flows controlled by the language primitives, and we consider the process and tractability of broadly enforcing security policy in commodity applications. We find that while the language provided the rudimentary tools to achieve low-level security goals, additional tools, services, and language extensions were necessary to formulate and enforce application policy. We detail the design and use of these tools. We also show how the strong guarantees of Jif in conjunction with our policy tools can be used to evaluate security. This work serves as a starting point--we have demonstrated that it is possible to implement real-world systems and policy using security-typed languages. However, further investigation of the developer tools and supporting policy infrastructure is necessary before they can fulfill their considerable promise of enabling more secure systems.

Paper: hicks-acsac06jpmail.pdf (December 2006)

Shamon: A system for distributed mandatory access control

We define and demonstrate an approach to securing distributed computation based on a shared reference monitor (Shamon) that enforces mandatory access control (MAC) policies across a distributed set of machines. The Shamon enables local reference monitor guarantees to be attained for a set of reference monitors on these machines. We implement a prototype system on the Xen hypervisor with a trusted MAC virtual machine built on Linux 2.6 whose reference monitor design requires only 13 authorization checks, only 5 of which apply to normal processing (others are for policy setup). We show that, through our architecture, distributed computations can be protected and controlled coherently across all the machines involved in the computation.

Paper: acsac06.pdf (December 2006)

Privacy-Preserving Web-Based Email

Recent web-based applications offer users free service in exchange for access to personal communication, such as online email services and instant messaging. The inspection and retention of user communication is generally intended to enable targeted marketing. However, unless specifically stated otherwise by the collecting service�s privacy policy, such records have an indefinite lifetime and may be later used or sold without restriction. In this paper, we show that it is possible to protect a user�s privacy from these risks by exploiting mutually oblivious, competing communication channels. We create virtual channels over online services (e.g., Google's Gmail, Microsoft's Hotmail) through which messages and cryptographic keys are delivered. The message recipient uses a shared secret to identify the shares and ultimately recover the original plaintext. In so doing, we create a wired "spread-spectrum" mechanism for protecting the privacy of web-based communication. We discuss the design and implementation of our open-source Java applet, Aquinas, and consider ways that the myriad of communication channels present on the Internet can be exploited to preserve privacy.

Paper: iciss06b.pdf (December 2006)

Password Exhaustion: Predicting the End of Password Usefulness

Passwords are currently the dominant authentication mechanism in computing systems. However, users are unwilling or unable to retain passwords with a large amount of entropy. This reality is exacerbated by the increasing ability of systems to mount offline attacks. In this paper, we evaluate the degree to which the previous statements are true and attempt to ascertain the point at which passwords are no longer sufficient to securely mediate authentication. In order to demonstrate this, we develop an analytical model for computation to understand the time required to recover random passwords. Further, an empirical study suggests the situation is much worse. In fact, we found that past systems vulnerable to offline attacks will be obsolete in 5-15 years, and our study suggests that a large number of these systems are already obsolete. We conclude that we must discard or fundamentally change these systems, and to that effect, we suggest a number of ways to prevent offline attacks.

Paper: iciss06a.pdf (December 2006)

Optimizing BGP Security by Exploiting Path Stability

The Border Gateway Protocol (BGP) is the de facto interdomain routing protocol on the Internet. While the serious vulnerabilities of BGP are well known, no security solution has been widely deployed. The lack of adoption is largely caused by a failure to find a balance between deployability, cost, and security. In this paper, we consider the design and performance of BGP path authentication constructions that limit resource costs by exploiting route stability. Based on a year-long study of BGP traffic and indirectly supported by findings within the networking community, we observe that routing paths are highly stable. This observation leads to comprehensive and efficient constructions for path authentication. We empirically analyze the resource consumption of the proposed constructions via trace-based simulations. This latter study indicates that our constructions can reduce validation costs by as much as 97.3% over existing proposals while requiring nominal storage resources. We conclude by considering operational issues related to incremental deployment of our solution.

Paper: ccs06a.pdf (November 2006)

Secure Attribute-Based Systems

Attributes define, classify, or annotate the datum to which they are assigned. However, traditional attribute architectures and cryptosystems are ill-equipped to provide security in the face of diverse access requirements and environments. In this paper, we introduce a novel secure information management architecture based on emerging attribute-based encryption (ABE) primitives. A policy system that meets the needs of complex policies is defined and illustrated. Based on the needs of those policies, we propose cryptographic optimizations that vastly improve enforcement efficiency. We further explore the use of such policies in two example applications: a HIPAA compliant distributed file system and a social network. A performance analysis of our ABE system and example applications demonstrates the ability to reduce cryptographic costs by as much as 98% over previously proposed constructions. Through this, we demonstrate that our attribute system is an efficient solution for securely managing information in large, loosely-coupled, distributed systems.

Paper: ccs06b.pdf (November 2006)

Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority

Secret sharing and multiparty computation (also called "secure function evaluation") are fundamental primitives in modern cryptography, allowing a group of mutually distrustful players to perform correct, distributed computations under the sole assumption that some number of them will follow the protocol honestly. This paper investigates how much trust is necessary -- that is, how many players must remain honest -- in order for distributed quantum computations to be possible. We present a verifiable quantum secret sharing (VQSS) protocol, and a general secure multiparty quantum computation (MPQC) protocol, which can tolerate any (n-1)/2 (rounded down) cheaters among n players. Previous protocols for these tasks tolerated (n-1)/4 (rounded down) and (n-1)/6 (rounded down) cheaters, respectively. The threshold we achieve is tight - even in the classical case, "fair" multiparty computation is not possible if any set of n/2 players can cheat. Our protocols rely on approximate quantum error-correcting codes, which can tolerate a larger fraction of errors than traditional, exact codes. We introduce new families of authentication schemes and approximate codes tailored to the needs of our protocols, as well as new state purification techniques along the lines of those used in fault-tolerant quantum circuits.

Paper: BCGHS06.pdf (October 2006)

Mitigating Open Functionality in SMS-Capable Cellular Networks

The transformation of telecommunications networks from homogeneous closed systems providing only voice services to Internetconnected open networks that provide voice and data services presents significant security challenges. For example, recent research illustrated that a carefully crafted DoS attack via text messaging could incapacitate all voice communications in a metropolitan area with little more than a cable modem. This attack highlights a growing threat to these systems; namely, cellular networks are increasingly exposed to adversaries both in and outside the network. In this paper, we use a combination of modeling and simulation to demonstrate the feasibility of targeted text messaging attacks. Under realistic network conditions, we show that adversaries can achieve blocking rates of more than 70% with only limited resources. We then develop and characterize five techniques from within two broad classes of countermeasures - queue management and resource provisioning. Our analysis demonstrates that these techniques can eliminate or extensively mitigate even the most intense targeted text messaging attacks. We conclude by considering the tradeoffs inherent to the application of these techniques in current and next generation telecommunications networks.

Paper: mobicom06.pdf (September 2006)

Efficient Group Mobility for Heterogeneous Sensor Networks

Mobility management protocols allow wireless devices to move between networks. These protocols have traditionally supported the mobility of individual nodes and are therefore not optimized to support the migration of groups. Accordingly, the time required to re-establish connectivity, frequency of dropped packets and contention for the air interface increase significantly for mobile groups. We propose a protocol for mobile groups that reduces all of the above by allowing a single node to perform handoffs on behalf of all group members. This "gateway" node eliminates the need for multiple handoff messages by obscuring group membership to external parties. Through extensive simulation and implementation, we show significant reduction in handoff times, message complexity and packet loss for groups of heterogeneous, mobile sensors running AODV and DSDV. By leveraging the naturally occurring hierarchy, we demonstrate that it is possible for groups to efficiently use traditional mobility protocols to support their collective movements.

Paper: vtc06.pdf (September 2006)

Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared key Models

We address the message authentication problem in two seemingly different communication models. In the first model, the sender and receiver are connected by an insecure channel and by a low-bandwidth auxiliary channel, that enables the sender to ``manually'' authenticate one short message to the receiver (for example, by typing a short string or comparing two short strings). We consider this model in a setting where no computational assumptions are made, and prove that for any $0 < \epsilon < 1$ there exists a $\log^* n$-round protocol for authenticating $n$-bit messages, in which only $2 \log(1 / \epsilon) + O(1)$ bits are manually authenticated, and any adversary (even computationally unbounded) has probability of at most $\epsilon$ to cheat the receiver into accepting a fraudulent message. Moreover, we develop a proof technique showing that our protocol is essentially optimal by providing a lower bound of $2 \log(1 / \epsilon) - O(1)$ on the required length of the manually authenticated string.

The second model we consider is the traditional message authentication model. In this model the sender and the receiver share a short secret key; however, they are connected only by an insecure channel. We apply the proof technique above to obtain a lower bound of $2 \log(1 / \epsilon) - 2$ on the required Shannon entropy of the shared key. This settles an open question posed by Gemmell and Naor (CRYPTO '93).

Finally, we prove that one-way functions are necessary (and sufficient) for the existence of protocols breaking the above lower bounds in the computational setting.

Paper: 175.pdf (August 2006)

Leveraging IPsec for Distributed Authorization

Mandatory access control (MAC) enforcement is becoming available for commercial environments. For example, Linux 2.6 includes the Linux Security Modules (LSM) framework that enables the enforcement of MAC policies (e.g., Type Enforcement or Multi-Level Security) for individual systems. While this is a start, we envision that MAC enforcement should span multiple machines. The goal is to be able to control interaction between applications on different machines based on MAC policy. In this paper, we describe a recent extension of the LSM framework that enables labeled network communication via IPsec that is now available in mainline Linux as of version 2.6.16. This functionality enables machines to control communication with processes on other machines based on the security label assigned to an IPsec security association. We outline a security architecture based on labeled IPsec to enable distributed MAC authorization. In particular, we examine the construction of a xinetd service that uses labeled IPsec to limit client access on Linux 2.6.16 systems. We also discuss the application of labeled IPsec to distributed storage and virtual machine access control.

Paper: securecomm06.pdf (August 2006)

Non-Invasive Methods for Host Certification

Paper: securecomm06b.pdf (August 2006)

LIGER: Implementing Efficient Hybrid Security Mechanisms for Heterogeneous Sensor Networks

The majority of security schemes available for sensor networks assume deployment in areas without access to a wired infrastructure. More specifically, nodes in these networks are unable to leverage key distribution centers (KDCs) to assist them with key management. In networks with a heterogeneous mix of nodes, however, it is not unrealistic to assume that some more powerful nodes have at least intermittent contact with a backbone network. For instance, an air-deployed battlefield network may have to operate securely for some time until uplinked friendly forces move through the area. We therefore propose LIGER, a hybrid key management scheme for heterogeneous sensor networks that allows systems to operate in both the presence and absence of a KDC. Specifically, when no KDC is available, nodes communicate securely with each other based upon a probabilistic unbalanced method of key management. The ability to access a KDC allows nodes to probabilistically authenticate neighboring devices with which they are communicating. We also demonstrate that this scheme is robust to the compromise of both low and high capability nodes and that the same keys can be used for both modes of operation. Detailed experiments and simulations are used to show that LIGER is a highly practical solution for the current generation of sensors and the unbalanced approach can significantly reduce network initialization time.

Paper: mobisys06.pdf (June 2006)

Characterizing Address Use Structure and Stabillity of Origin Advertisement in Interdomain Routing

The stability and robustness of BGP remains one of the most critical elements in sustaining today's Internet. In this paper, we study the structure and stability of origin advertisements in inter-domain routing. We visualize and quantitatively characterize the frequency, size, and effect of address assignment and origin changes by analyzing realworld BGP updates for a period of one year from multiple vantage points. Broad classes of prefix behaviors are developed. We show that a significant portion of BGP traffic is due to prefix flapping and explore the contributing factors which include a number of prefixes with abnormal short up-and-down cycles. A significant portion of prefixes have high origin stability. Most ASes are involved in few, if any, prefix movement events, while a small number of ASes are responsible for most of the origin churn. Additionally, we find that a high volume of new prefixes can be attributed to actively evolving countries, that some abnormal prefix flapping is most likely due to misconfiguration, and that some culprit ASes characterize the places where multi-origin prefixes oscillate.

Paper: icss06.pdf (June 2006)

Retrofitting Legacy Code for Authorization Policy Enforcement

Researchers have argued that the best way to construct a secure system is to proactively integrate security into the design of the system. However, this tenet is rarely followed because of economic and practical considerations. Instead, security mechanisms are added as the need arises, by retrofitting legacy code. Existing techniques to do so are manual and ad hoc, and often result in security holes. We present program analysis techniques to assist the process of retrofitting legacy code for authorization policy enforcement. These techniques can be used to retrofit legacy servers, such as X window, web, proxy, and cache servers. Because such servers manage multiple clients simultane- ously, and offer shared resources to clients, they must have the ability to enforce authorization policies. A developer can use our techniques to identify security-sensitive loca- tions in legacy servers, and place reference monitor calls to mediate these locations. We demonstrate our techniques by retrofitting the X11 server to enforce authorization policies on its X clients.

Paper: oakland06.pdf (May 2006)

Establishing Pair-Wise Keys In Heterogeneous Sensor Networks

Many applications that make use of sensor networks require secure communication. Because asymmetric-key solutions are difficult to implement in such a resource-constrained environment, symmetric-key methods coupled with a priori key distribution schemes have been proposed to achieve the goals of data secrecy and integrity. These approaches typically assume that all sensors are similar in terms of capabilities, and hence deploy the same number of keys in all sensors in a network to provide the aforementioned protections. In this paper we demonstrate that a probabilistic unbalanced distribution of keys throughout the network that leverages the existence of a small percentage of more capable sensor nodes can not only provide an equal level of security but also reduce the consequences of node compromise. We demonstrate the effectiveness of this approach on small networks using a variety of trust models and then demonstrate the application of this method to very large systems. The approach and analysis presented in this paper can be applied to all protocols that use probabilistic keys including those that employ broadcast mechanisms, hash functions or polynomials for the generation of keys.

Paper: infocom06.pdf (April 2006)

The Effects of Probabilistic Key Management on Secure Routing in Sensor Networks

Secure data dissemination in wireless ad hoc and sensor networks has recently received a great deal of attention. A variety of protocols have been proposed in order to ensure secure data delivery across these systems; however, the majority of these schemes assume the presence of public or pre-established symmetric keys. Accordingly, the cost of key management has not been incorporated into secure routing mechanisms in this setting. This paper considers the expenses incurred by sensor networks implementing secure routing schemes on top of probabilistic symmetric key management schemes. Specifically, we examine the overhead observed from proactive and reactive key establishment mechanisms for networks using a balanced method of key management. Through extensive simulation, we quantify more realistic costs for the application of secure hop-by-hop routing in sensor networks.

Paper: wcnc06.pdf (April 2006)

Calibrating Noise to Sensitivity in Private Data Analysis

We continue a line of research initiated in [10, 11] on privacy-preserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query function f mapping databases to reals, the so-called true answer is the result of applying f to the database. To protect privacy, the true answer is perturbed by the addition of random noise generated according to a carefully chosen distribution, and this response, the true answer plus noise, is returned to the user.

Previous work focused on the case of noisy sums, in which f = Σ_i g(x_i), where xi denotes the ith row of the database and g maps database rows to [0, 1]. We extend the study to general functions f, proving that privacy can be preserved by calibrating the standard deviation of the noise according to the sensitivity of the function f. Roughly speaking, this is the amount that any single argument to f can change its output. The new analysis shows that for several particular applications substantially less noise is needed than was previously understood to be the case.

The first step is a very clean characterization of privacy in terms of indistinguishability of transcripts. Additionally, we obtain separation results showing the increased value of interactive sanitization mechanisms over non-interactive.

Paper: sensitivity-tcc-final.pdf (March 2006)

Enterprise Security: A Community of Interest Based Approach

Enterprise networks today carry a range of mission critical communications. A successful worm attack within an enterprise network can be substantially more devastating to most companies than attacks on the larger Internet. In this paper we explore a brownfield approach to hardening an enterprise network against active malware such as worms. The premise of our approach is that if future communication patterns are constrained to historical "normal" communication patterns, then the ability of malware to exploit vulnerabilities in the enterprise can be severely curtailed. We present techniques for automatically deriving individual host profiles that capture historical communication patterns (i.e., community of interest (COI)) of end hosts within an enterprise network. Using traces from a large enterprise network, we investigate how a range of different security policies based on these profiles impact usability (as valid communications may get restricted) and security (how well the policies contain malware). Our evaluations indicate that a simple security policy comprised of our Extended COI-based profile and Relaxed Throttling Discipline can effectively contain worm behavior within an enterprise without significantly impairing normal network operation.

Paper: ndss06.pdf (February 2006)

Toward Automated Information-Flow Integrity Verification for Security-Critical Applications

We provide a largely automated system for verifying Clark- Wilson interprocess information-flow integrity. Information-flow integrity properties are essential to isolate trusted processes from untrusted ones by removing unwanted input dependences. For example, an untrusted user process should not be able to write to sshd config via a cron script. A useful notion of integrity is the Clark-Wilson integrity model [7], which allows trusted processes to accept necessary untrusted inputs (e.g., network data or print jobs) via filtering interfaces that sanitize the data. However, Clark-Wilson has the requirement that programs undergo formal semantic verification; in practice, this kind of burden has meant that no information-flow integrity property is verified on most widely-used systems. We define a weaker version of Clark-Wilson integrity, called CW-Lite, which has the same interprocess information-flow guarantees, but which requires less filtering, only small changes to existing applications, and which we can check using automated tools. We modify the SELinux user library and kernel module in order to support CWLite integrity verification and develop new software tools to aid developers in finding and enabling filtering interfaces. Using our toolset, we found and fixed several integrity-violating configuration errors in the default SELinux policies for OpenSSH and vsftpd.

Paper: ndss06.pdf (February 2006)

Understanding Mutable Internet Pathogens, or How I Learned to Stop Worrying and Love Parasitic Behavior

Worms are becoming increasingly hostile. The exponential growth of infection rates allows small outbreaks to have worldwide consequences within minutes. Moreover, the collateral damage caused by infections can cripple the entire Internet. While harmful, such behaviors have historically been short-lived. We assert the future holds much more caustic malware. Attacks based on mutation and covert propagation are likely to be ultimately more damaging and long lasting. This assertion is supported by observations of natural systems, where similarly behaving parasites represent by far the most successful class of living creatures. This talk considers a parasite for the Internet, providing biological metaphors for its behavior and demonstrating the structure of pathogens. Through simulation, we show that even with low infection rates, a mutating pathogen will eventually infect an entire community. We posit the inevitability of such parasites, and consider ways that they can be mitigated.

Paper: iciss05.pdf (December 2005)

Building a MAC-based Security Architecture for the Xen Open-Source Hypervisor

We present the sHype hypervisor security architecture and examine in detail its mandatory access control facilities. While existing hypervisor security approaches aiming at high assurance have been proven useful for high-security environments that prioritize security over performance and code reuse, our approach aims at commercial security where near-zero performance overhead, non-intrusive implementation, and usability are of paramount importance. sHype enforces strong isolation at the granularity of a virtual machine, thus providing a robust foundation on which higher software layers can enact finer-grained controls. We provide the rationale behind the sHype design and describe and evaluate our implementation for the Xen open-source hypervisor.

Paper: acsac05.pdf (December 2005)

TARP: Ticket-Based Address Resolution Protocol

IP networks fundamentally rely on the Address Resolution Protocol (ARP) for proper operation. Unfortunately, vulnerabilities in the ARP protocol enable a raft of IP-based impersonation, man-in-the-middle, or DoS attacks. Proposed countermeasures to these vulnerabilities have yet to simultaneously address backward compatibility and cost requirements. This paper introduces the Ticket-based Address Resolution Protocol (TARP). TARP implements security by distributing centrally issued secure MAC/IP address mapping attestations through existing ARP messages. We detail the TARP protocol and its implementation within the Linux operating system. Our experimental analysis shows that TARP improves the costs of implementing ARP security by as much as two orders of magnitude over existing protocols. We conclude by exploring a range of operational issues associated with deploying and administering ARP security.

Paper: acsac05.pdf (December 2005)

Automatic placement of authorization hooks in the Linux security modules framework

We present a technique for automatic placement of authorization hooks, and apply it to the Linux security modules (LSM) framework. LSM is a generic framework which allows diverse authorization policies to be enforced by the Linux kernel. It consists of a kernel module which encapsulates an authorization policy, and hooks into the kernel module placed at appropriate locations in the Linux kernel. The kernel enforces the authorization policy using hook calls. In current practice, hooks are placed manually in the kernel. This approach is tedious, and as prior work has shown, is prone to security holes.

Our technique uses static analysis of the Linux kernel and the kernel module to automate hook placement. Given a non-hookplaced version of the Linux kernel, and a kernel module that implements an authorization policy, our technique infers the set of operations authorized by each hook, and the set of operations performed by each function in the kernel. It uses this information to infer the set of hooks that must guard each kernel function. We describe the design and implementation of a prototype tool called TAHOE (Tool for Authorization Hook Placement) that uses this technique. We demonstrate the effectiveness of TAHOE by using it with the LSM implementation of security-enhanced Linux (SELinux). While our exposition in this paper focuses on hook placement for LSM, our technique can be used to place hooks in other LSM-like architectures as well.

Paper: ccs05.pdf (November 2005)

Exploiting Open Functionality in SMS-Capable Cellular Networks

Cellular networks are a critical component of the economic and social infrastructures in which we live. In addition to voice services, these networks deliver alphanumeric text messages to the vast majority of wireless subscribers. To encourage the expansion of this new service, telecommunications companies offer connections between their networks and the Internet. The ramifications of such connections, however, have not been fully recognized. In this paper, we evaluate the security impact of the SMS interface on the availability of the cellular phone network. Specifically, we demonstrate the ability to deny voice service to cities the size of Washington D.C. and Manhattan with little more than a cable modem. Moreover, attacks targeting the entire United States are feasible with resources available to medium-sized zombie networks. This analysis begins with an exploration of the structure of cellular networks. We then characterize network behavior and explore a number of reconnaissance techniques aimed at effectively targeting attacks on these systems. We conclude by discussing countermeasures that mitigate or eliminate the threats introduced by these attacks.

Paper: ccs05.pdf (November 2005)

The Sleep Deprivation Attack in Sensor Networks: Analysis and Methods of Defense

Paper: ICA_DSN_05b.pdf (October 2005)

Privacy Preserving Clustering

The freedom and transparency of information flow on the Internet has heightened concerns of privacy. Given a set of data items, clustering algorithms group similar items together. Clustering has many applications, such as customer-behavior analysis, targeted marketing, forensics, and bioinformatics. In this paper, we present the design and analysis of a privacy-preserving k-means clustering algorithm, where only the cluster means at the various steps of the algorithm are revealed to the participating parties. The crucial step in our privacy-preserving k-means is privacy-preserving computation of cluster means. We present two protocols (one based on oblivious polynomial evaluation and the second based on homomorphic encryption) for privacy-preserving computation of cluster means. We have a JAVA implementation of our algorithm. Using our implementation, we have performed a thorough evaluation of our privacy-preserving clustering algorithm on three data sets. Our evaluation demonstrates that privacy-preserving clustering is feasible, i.e., our homomorphic-encryption based algorithm finished clustering a large data set in approximately 66 seconds.

Paper: esorics05.pdf (September 2005)

Secure Reporting of Traffic Forwarding Activity in Mobile Ad Hoc Networks

Nodes forward data on behalf of each other in mobile ad hoc networks. In a civilian application, nodes are assumed to be selfish and rational, i.e., they pursue their own self-interest. Hence, the ability to accurately measure traffic forwarding is critical to ensure proper network operation. These measurements are often used to credit nodes based on their level of participation, or to detect loss. Past solutions employ neighbor monitoring and reporting on node forwarding traffic. These methods are not applicable in civilian networks where neighbor nodes lack the desire or ability to perform the monitoring function. Such environments occur frequently in which neighbor hosts are resource constrained, or in networks where directional antennas are used and reliable monitoring is difficult or impossible.

In this paper, we propose a protocol that uses nodes on the data path to securely produce packet forwarding reports. Reporting nodes are chosen randomly and secretly so that malicious nodes cannot modify their behavior based upon the monitoring point. The integrity and authenticity of reports are preserved through the use of secure link layer acknowledgments and monitoring reports. The robustness of the reporting mechanism is strengthened by forwarding the report to multiple destinations (source and destination). We explore the security, cost, and accuracy of our protocol.

Paper: mobiq05.pdf (July 2005)

Correcting Errors Without Leaking Partial Information

This paper explores what kinds of information two partiesmust communicate in order to correct errors which occur ina shared secret string W. Any bits they communicate mustleak a significant amount of information about W � thatis, from the adversary�s point of view, the entropy of W willdrop significantly. Nevertheless, we construct schemes withwhich Alice and Bob can prevent an adversary from learningany useful information about W. Specifically, if the entropyof W is sufficiently high, then there is no function f(W)which the adversary can learn from the error-correction informationwith significant probability. This leads to severalnew results: (a) the design of noise-tolerant �perfectly oneway�hash functions in the sense of Canetti et al. [7], whichin turn leads to obfuscation of proximity queries for highentropy secrets W; (b) private fuzzy extractors [11], whichallow one to extract uniformly random bits from noisy andnonuniform data W, while also insuring that no sensitiveinformation about W is leaked; and (c) noise tolerance andstateless key re-use in the Bounded Storage Model, resolvingthe main open problem of Ding [10].

The heart of our constructions is the design of strong randomnessextractors with the property that the source W canbe recovered from the extracted randomness and any stringW' which is close to W.

Paper: proxobf-stoc-proc.pdf (May 2005)

Approximate Quantum Error Correcting Codes and Verifiable Secret Sharing

It is a standard result in the theory of quantum error-correctingcodes that no code of length n can fix more than n/4 arbitrary errors,regardless of the dimension of the coding and encoded Hilbert spaces.However, this bound only applies to codes which recover the messageexactly. Naively, one might expect that correcting errors to very highfidelity would only allow small violations of this bound. This intuitionis incorrect: in this paper we describe quantum error-correcting codescapable of correcting up to [(n- 1)/2] arbitrary errors with fidelity exponentiallyclose to 1, at the price of increasing the size of the registers(i.e., the coding alphabet). This demonstrates a sharp distinction betweenexact and approximate quantum error correction. The codes havethe property that any t components reveal no information about themessage, and so they can also be viewed as error-tolerant secret sharingschemes.

The construction has several interesting implications for cryptographyand quantum information theory. First, it suggests that secret sharing isa better classical analogue to quantum error correction than is classicalerror correction. Second, it highlights an error in a purported proof thatverifiable quantum secret sharing (VQSS) is impossible when the numberof cheaters t is n/4. In particular, the construction directly yields anhonest-dealer VQSS scheme for t = [(n- 1)/2]. We believe the codescould also potentially lead to improved protocols for dishonest-dealerVQSS and secure multi-party quantum computation.

More generally, the construction illustrates a difference between exactand approximate requirements in quantum cryptography and (yet again)the delicacy of security proofs and impossibility results in the quantummodel.

Paper: aqecc-proc-Eurocrypt-2005.pdf (May 2005)

Secure Remote Authentication Using Biometric Data

Biometric data offer a potential source of high-entropy, secretinformation that can be used in cryptographic protocols provided twoissues are addressed: (1) biometric data are not uniformly distributed;and (2) they are not exactly reproducible. Recent work, most notablythat of Dodis, Reyzin, and Smith, has shown how these obstacles maybe overcome by allowing some auxiliary public information to be reliablysent from a server to the human user. Subsequent work of Boyen hasshown how to extend these techniques, in the random oracle model, toenable unidirectional authentication from the user to the server withoutthe assumption of a reliable communication channel.

We show two efficient techniques enabling the use of biometric data toachieve mutual authentication or authenticated key exchange over a completelyinsecure (i.e., adversarially controlled) channel. In addition toachieving stronger security guarantees than the work of Boyen, we improveupon his solution in a number of other respects: we tolerate abroader class of errors and, in one case, improve upon the parameters ofhis solution and give a proof of security in the standard model.

Paper: fuzzy-remote-proceedings-Eurocrypt-2005.pdf (May 2005)

Towards Privacy in Public Databases

We initiate a theoretical study of the census problem. Informally,in a census individual respondents give private information to atrusted party (the census bureau), who publishes a sanitized version ofthe data. There are two fundamentally conflicting requirements: privacyfor the respondents and utility of the sanitized data. Unlike in the studyof secure function evaluation, in which privacy is preserved to the extentpossible given a specific functionality goal, in the census problem privacyis paramount; intuitively, things that cannot be learned "safely" shouldnot be learned at all.

An important contribution of this work is a definition of privacy (andprivacy compromise) for statistical databases, together with a methodfor describing and comparing the privacy offered by specific sanitizationtechniques.We obtain several privacy results using two different sanitizationtechniques, and then show how to combine them via cross training.We also obtain two utility results involving clustering.

Paper: sdb-tcc-2005-almost-final-proceedings.pdf (February 2005)

Entropic Security and the Encryption of High Entropy Messages

Russell and Wang (Eurocrypt 2002) recently introduced an elegant, information-theoretic notion called entropic security of encryption: they required that the cipher text leak no predicate of the plaintext (similar to semantic security (Goldwasser and Micali, JCSS 1984)) but only as long as the distribution on messages has high entropy from the adversary's point of view. They show that this notion of security can be achieved with very short keys for entropically rich message spaces. Canetti, Miccianci and Reingold (STOC, 1998) had previously constructed hash functions which satisfy a similar entropic security condition. The output of such hash function leaks no partial information about the input, provided the input has sufficiently high entropy. This paper studies entropic security in general, and its application to the encryption of high-entropy messages.

(1) We elucidate the notion of entropic security. Our results apply to all entropically-secure primitives, including both encryption and hash functions. We strengthen the formulation of Canetti and Russell and Wang: we require that an entropically-secure primitive leak no function whasoever of its input, while the previous works focus only on predicates. This stronger formulation is much closer to the original notion of semantic security. We also show that entropic security is equivalent to indistinguishability on pairs of input distributions of sufficiently high entropy. This equivalence generalizes the conventional equivalence between indistinguishability and semantic security. Indistinguishability, in turn, is related to randomness extraction from non-uniform distributions. The proof of the equivalence of hiding predicates to hiding all functions is quite involved, and requires very different techniques from those of Goldwasser and Micali.

(2) We use the equivalence above, and the connection to randomness extraction, to prove several new results on entropically-secure encryption. We obtain:

(a) Two general frameworks for constructing entropically secure encryption schemes, one based on expander graphs and the other on XOR-universal hash functions. These schemes generalize the schemes of Russell and Wang, yielding simpler constructions and proofs as well as improved parameters. The best scheme uses a key of length k=n-t+2log(1/eps)+O(1), where eps is a measure of leakage and t is the initial min-entropy of the message.

(b) Lower bounds on the key length k for entropic security and indistinguishability. In particular, we show near tightness of Russell-Wang constructions: k > n-t. (In fact, for a large class of schemes k >= n-t + log(1/eps).)

Paper: 219.pdf (February 2005)

Attestation-based policy enforcement for remote access

Intranet access has become an essential function for corporate users. At the same time, corporation's security administrators have little ability to control access to corporate data once it is released to remote clients. At present, no confidentiality or integrity guarantees about the remote access clients are made, so it is possible that an attacker may have compromised a client process and is now downloading or modifying corporate data. Even though we have corporatewide access control over remote users, the access control approach is currently insufficient to stop these malicious processes. We have designed and implemented a novel system that empowers corporations to verify client integrity properties and establish trust upon the client policy enforcement before allowing clients (remote) access to corporate Intranet services. Client integrity is measured using a Trusted Platform Module (TPM), a new security technology that is becoming broadly available on client systems, and our system uses these measurements for access policy decisions enforced upon the client's processes. We have implemented a Linux 2.6 prototype system that utilizes the TPM measurement and attestation, existing Linux network control (Netfilter), and existing corporate policy management tools in the Tivoli Access Manager to control remote client access to corporate data. This prototype illustrates that our solution integrates seamlessly into scalable corporate policy management and introduces only a minor performance overhead.

Paper: ccs04.pdf ( 2004)

Design and Implementation of a TCG-based Integrity Measurement Architecture

We present the design and implementation of a secure integrity measurement system for Linux. All executable content that is loaded onto the Linux system is measured before execution and these measurements are protected by the Trusted Platform Module (TPM) that is part of the Trusted Computing Group (TCG) standards. Our system is the first to extend the TCG trust measurement concepts to dynamic executable content from the BIOS all the way up into the application layer. In effect, we show that many of the Microsoft NGSCB guarantees can be obtained on today's hardware and today's software and that these guarantees do not require a new CPU mode or operating system but merely depend on the availability of an independent trusted entity, a TPM for example. We apply our trust measurement architecture to a web server application where we show how our system can detect undesirable invocations, such as rootkit programs, and that our measurement architecture is practical in terms of the number of measurements taken and the performance impact of making them.

Paper: usenix_sec2004.pdf ( 2004)

Resolving Constraint Conflicts

In this paper, we define constraint conflicts and examine properties that may aid in guiding their resolution. A constraint conflict is an inconsistency between the access control policy and the constraints specified to limit that policy. For example, a policy that permits a high integrity subject to access low integrity data is in conflict with a Biba integrity constraint. Constraint conflicts differ from typical policy conflicts in that constraints are never supposed to be violated. That is, a conflict with a constraint results in a policy compilation error, whereas policy conflicts are resolved at runtime. As we have found in the past, when constraint conflicts occur in a specification a variety of resolutions are both possible and practical. In this paper, we detail some key formal properties of constraint conflicts and show how these are useful in guiding conflict resolution. We use the SELinux example policy for Linux 2.4.19 as the source of our constraint conflicts and resolution examples. The formal properties are used to guide the selection of resolutions and provide a basis for a resolution language that we apply to resolve conflicts in the SELinux example policy.

Paper: sacmat04.pdf (June 2004)

Origin Authentication in Interdomain Routing

Attacks against Internet routing are increasing in number and severity. Contributing greatly to these attacks is the absence origin authentication: there is no way to validate claims of address ownership or location. The lack of such services enables not only attacks by malicious entities, but indirectly allow seemingly inconsequential miconfigurations to disrupt large portions of the Internet. This paper considers the semantics, design, and costs of origin authentication in interdomain routing. We formalize the semantics of address delegation and use on the Internet, and develop and characterize broad classes of origin authentication proof systems. We estimate the address delegation graph representing the current use of IPv4 address space using available routing data. This effort reveals that current address delegation is dense and relatively static: as few as 16 entities perform 80% of the delegation on the Internet. We conclude by evaluating the proposed services via traced based simulation. This simulation shows the enhanced proof systems can reduce resource consumption by an order of magnitude over currently proposed solutions.

Paper: ccs03a.pdf (October 2003)

On the Performance, Feasibility, and Use of Forward Secure Signatures

Forward-secure signatures (FSSs) have recently received much attention from the cryptographic theory community as a potentially realistic way to mitigate many of the difficulties digital signatures face with key exposure. However, no previous works have explored the practical performance of these proposed constructions in real-world applications, nor have they compared FSS to traditional, non-forward-secure, signatures in a non-asymptotic way.

We present an empirical evaluation of several FSS schemes that looks at the relative performance among different types of FSS as well as between FSS and traditional signatures. Our study provides the following contributions: first, a new methodology for comparing the performance of signature schemes, and second, a thorough examination of the practical performance of FSS. We show that for many cases the best FSS scheme has essentially identical performance to traditional schemes, and even in the worst case is only 2-4 times slower. On the other hand, we also show that if the wrong FSS configuration is used, the performance can be orders of magnitude slower. Our methodology provides a way to prevent such misconfigurations, and we examine common applications of digital signatures using it. In addition to the evaluation methodology and empirical study, a third contribution of this paper is the open-source FSS library developed for the study.

We conclude that not only are forward-secure signatures a useful theoretical construct as previous works have shown, but they are also, when used correctly, a very practical solution to some of the problems associated with key exposure in real-world applications. Through our metrics and our reference implementation we provide the tools necessary for developers to efficiently use forward-secure signatures.

Paper: ccs03b.pdf (October 2003)

Analyzing Integrity Protection in the SElinux Example Policy

In this paper, we present an approach for analyzing the integrity protection in the SELinux example policy. The SELinux example policy is intended as an example from which administrators customize to create a policy for their site's security goals, but the complexity of the model and size of the policy make this quite complex. Our aim is to provide an access control model to express site security goals and resolve them against the SELinux policy. Ultimately, we aim to define a minimal trusted computing base (TCB) that satisfies Clark-Wilson integrity, by first testing for the more restrictive Biba integrity policy and resolving conflicts using Clark-Wilson semantics. Our policy analysis tool, Gokyo, implements the following approach: (1) it represents the SELinux example policy and our integrity goals; (2) it identifies conflicts between them; (3) it estimates the resolutions to these conflicts; and (4) provides information for deciding upon a resolution. Using Gokyo, we derive a proposal for a minimal TCB for SELinux includes 30 subject types, and we identify the work remaining to ensure that TCB is integrity-protected. Our analysis is performed on the SELinux example policy for Linux 2.4.19.

Paper: jsz03.pdf (August 2003)

Working Around BGP: An Incremental Approach to Improving Security and Accuracy of Interdomain Routing

BGP is essential to the operation of the Internet, but is vulnerable to both accidental failures and malicious attacks. We propose a new protocol that works in concert with BGP, which Autonomous Systems will use to help detect and mitigate accidentally or maliciously introduced faulty routing information. The protocol differs from previous efforts at securing BGP in that it is receiver-driven, meaning that there is a mechanism for recipients of BGP UPDATE messages to corroborate the information they receive and to provide feedback. We argue that our new protocol can be adopted incrementally, and we show that there is incentive for network operators to do so. We also describe our prototype implementation.

Paper: ndss03.pdf (February 2003)

Runtime Verification of Authorization Hook Placement for the Linux Security Modules Framework

We present runtime tools to assist the Linux community in verifying the correctness of the Linux Security Modules (LSM) framework. The LSM framework consists of a set of authorization hooks inserted into the Linux kernel to enable additional authorizations to be performed (e.g., for mandatory access control). When compared to system call interposition, authorization within the kernel has both security and performance advantages, but it is more difficult to verify that placement of the LSM hooks ensures that all the kernel's security-sensitive operations are authorized. We have examined both static and runtime analysis techniques for this verification, and have found them to be complementary. Static analysis is more complex to implement and tends to generate more false positives, but coverage of all type-safe execution paths is possible. Runtime analysis lacks the code and input coverage of static analysis, but tends to be simpler to gather useful information. The major simplifying factor in our runtime verification approach is that we can leverage the fact that most of the LSM hooks are properly placed to identify misplaced hooks. Our runtime verification tools collect the current LSM authorizations and find inconsistencies in these authorizations. We describe our approach for performing runtime verification, the design of the tools that implement this approach, and the anomalous situations found in an LSM-patched Linux 2.4.16 kernel.

Paper: ccs02.pdf (October 2002)

Using CQUAL for Static Analysis of Authorization Hook Placement

The Linux Security Modules (LSM) framework is a set of authorization hooks for implementing flexible access control in the Linux kernel. While much effort has been devoted to defining the module interfaces, little attention has been paid to verifying the correctness of hook placement. This paper presents a novel approach to the verification of LSM authorization hook placement using CQUAL, a type-based static analysis tool. With a simple CQUAL lattice configuration and some GCC-based analyses, we are able to verify complete mediation of operations on key kernel data structures. Our results reveal some potential security vulnerabilities of the current LSM framework, one of which we demonstrate to be exploitable. Our experiences demonstrate that combinations of conceptually simple tools can be used to perform fairly complex analyses.

Paper: usenix_sec2002.pdf (August 2002)

Methods and Limitations of Security Policy Reconciliation

A security policy is a means by which participant session requirements are specified. However, existing frameworks provide limited facilities for the automated reconciliation of participant policies. This paper considers the limits and methods of reconciliation in a general-purpose policy model. We identify an algorithm for efficient two-policy reconciliation, and show that, in the worst-case, reconciliation of three or more policies is intractable. Further, we suggest efficient heuristics for the detection and resolution of intractable reconciliation. Based upon the policy model, we describe the design and implementation of the Ismene policy language. The expressiveness of Ismene, and indirectly of our model, is demonstrated through the representation and exposition of policies supported by existing policy languages. We conclude with brief notes on the integration and enforcement of Ismene policy within the Antigone communication system.

Paper: oak2002.pdf (MAY 2002)

Flexibly Constructing Secure Groups in Antigone 2.0

Group communication is increasingly used as a low cost building block for the development of highly available and survivable services in dynamic environments. However, contemporary frameworks often provide limited facilities for the definition and enforcement of precise security policies. This paper presents the Antigone 2.0 framework that allows the flexible specification and enforcement of group security policies. Enforcement is achieved through the policy directed composition and configuration of sets of basic security services implementing the group. We summarize the design of the Antigone 2.0 architecture, its use, and the Application Programming Interface (API). The use of the API is illustrated through two applications built on Antigone; a reliable multicast system and host level multicast security service. We conclude with a description of current status and plans for future work.

Paper: discex01.pdf (June 2001)

Managing access control complexity using metrics

General access control models enable flexible expression of access control policies, but they make the verification of whether a particular access control configuration is safe (i.e., prevents the leakage of a permission to an unauthorized subject) difficult. The current approach to expressing safety policy in such models is to use constraints. When the constraints are verified, then the configuration is verified to be safe. However, the addition of constraints to an access control configuration significantly increases its complexity, so it quickly becomes difficult to understand the access control policy expressed in the configuration such that future changes can be made correctly. We propose an approach whereby the complexity of each access control configuration is estimated, so the administrators can see the effect of a configuration change on the future ability to maintain the configuration. We identify metrics for making complexity estimates and evaluate these metrics on some constraint examples. Our goal is to enable the use of flexible access control models for safety-critical systems by permitting limited use of constraints that do not complicate the configuration beyond a maintainable complexity.

Paper: sacmat01.pdf (May 2001)

Principles of Policy in Secure Groups

Security policy is increasingly being used as a vehicle for specifying complex entity relationships. When used to define group security, policy must be extended to state the entirety of the security context. For this reason, the policy requirements of secure groups are more complex than found in traditional peer communication; group policies convey information about associations greater and more abstract than their pair-wise counterparts. This paper identifies and illustrates universal requirements of secure group policy and reasons about the adherence of the Group Security Association Key Management Protocol (GSAKMP) to these principles.

Paper: ndss01.pdf (February 2001)

Information & Resources

Research

Mitigating Attacks on Open Functionality in SMS-Capable Cellular Networks

Non-Invasive Methods for Host Certification

Exploiting Open Functionality in SMS-Capable Cellular Networks

Round-Eye: A System for Tracking Nearest Surrounders in Moving Object Environments

TARP: Ticket-based Address Resolution Protocol

Efficient Hybrid Security Mechanisms for Heterogeneous Sensor Networks

ASR: Anonymous and Secure Reporting of Traffic Forwarding Activity in Mobile Ad Hoc Networks

Origin Authentication in Interdomain Routing

Enforcing Provisioning and Authorization Policy in the Antigone System

Methods and Limitations of Security Policy Reconciliation

Security Policy Enforcement in the Antigone System

The Sleep Deprivation Attack in Sensor Networks: Analysis and Methods of Defense

Analysis of Security Vulnerabilities in the Movie Production and Distribution Process

Consistency Analysis of Authorization Hook Placement in the Linux Security Modules Framework

Policy Management Using Access Control Spaces

Practical safety in flexible access control models

Demand Transformation Analysis for Concurrent Constraint Programs

Higher-Order Uncurrying

Flexible Control of Downloaded Executable Content

A flexible security system for using Internet content

Rootkit-Resistant Disks

Composition Attacks and Auxiliary Information in Data Privacy

Effective Blame for Information-Flow Violations

Verifying Compliance of Trusted Programs

Measuring Integrity on Mobile Phone Systems

Realizing Massive-Scale Conditional Access Systems Through Attribute-Based Cryptosystems

Channels: Runtime System Infrastructure for Security-typed Languages

Establishing and Sustaining System Integrity via Root of Trust Installation

Smooth Sensitivity and Sampling in Private Data Analysis

On Attack Causality in Internet-Connected Cellular Networks

Email Communities of Interest

Analysis of IPv4 Address Space Delegation Structure

From Trusted to Secure: Building and Executing Applications that Enforce System Security

Configuration Management at Massive Scale: System Design and Experience

A Logical Specification and Analysis for SELinux MLS Policy

Managing the Risk of Covert Information Flows in Virtual Machine Systems

Privacy Preserving Communication in MANETs

Toward Valley-Free Inter-domain Routing

Mining Security-Sensitive Operations in Legacy Code using Concept Analysis

Leveraging Identity-based Cryptography for Node ID Assignment in Structured P2P Systems

Limiting Sybil Attacks in Structured Peer-to-Peer Networks

Integrating SELinux with Security-typed Languages

Scrambling Adversarial Errors Using Few Random Bits

Understanding Practical Application Development in Security-typed Languages

Shamon: A system for distributed mandatory access control

Privacy-Preserving Web-Based Email

Password Exhaustion: Predicting the End of Password Usefulness

Optimizing BGP Security by Exploiting Path Stability

Secure Attribute-Based Systems

Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority

Mitigating Open Functionality in SMS-Capable Cellular Networks

Efficient Group Mobility for Heterogeneous Sensor Networks

Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared key Models

Leveraging IPsec for Distributed Authorization

Non-Invasive Methods for Host Certification

LIGER: Implementing Efficient Hybrid Security Mechanisms for Heterogeneous Sensor Networks

Characterizing Address Use Structure and Stabillity of Origin Advertisement in Interdomain Routing

Retrofitting Legacy Code for Authorization Policy Enforcement

Establishing Pair-Wise Keys In Heterogeneous Sensor Networks

The Effects of Probabilistic Key Management on Secure Routing in Sensor Networks

Calibrating Noise to Sensitivity in Private Data Analysis

Enterprise Security: A Community of Interest Based Approach

Toward Automated Information-Flow Integrity Verification for Security-Critical Applications

Understanding Mutable Internet Pathogens, or How I Learned to Stop Worrying and Love Parasitic Behavior

Building a MAC-based Security Architecture for the Xen Open-Source Hypervisor

TARP: Ticket-Based Address Resolution Protocol

Automatic placement of authorization hooks in the Linux security modules framework

Exploiting Open Functionality in SMS-Capable Cellular Networks

The Sleep Deprivation Attack in Sensor Networks: Analysis and Methods of Defense

Privacy Preserving Clustering

Secure Reporting of Traffic Forwarding Activity in Mobile Ad Hoc Networks

Correcting Errors Without Leaking Partial Information

Approximate Quantum Error Correcting Codes and Verifiable Secret Sharing

Secure Remote Authentication Using Biometric Data

Towards Privacy in Public Databases

Entropic Security and the Encryption of High Entropy Messages

Attestation-based policy enforcement for remote access

Design and Implementation of a TCG-based Integrity Measurement Architecture