As computers have become ever more interconnected, the complexity of security configuration has exploded. Management tools have not kept pace, and we show that this has made identity snowball attacks into a critical danger. Identity snowball attacks leverage the users logged in to a first compromised host to launch additional attacks with those users' privileges on other hosts. To combat such attacks, we present Heat-ray, a system that combines machine learning, combinatorial optimization and attack graphs to scalably manage security configuration. Through evaluation on an organization with several hundred thousand users and machines, we show that Heat-ray allows IT administrators to reduce by 96% the number of machines that can be used to launch a large-scale identity snowball attack.

We describe a new design for authorization in operating systems in which applications are first-class entities. In this design, principals reflect application identities. Access control lists are patterns that recognize principals. We present a security model that embodies this design in an experimental operating system, and we describe the implementation of our design and its performance in the context of this operating system.

Software patching has not been effective as a first-line defense against large-scale worm attacks, even when patches have long been available for their corresponding vulnerabilities. Generally, people have been reluctant to patch their systems immediately, because patches are perceived to be unreliable and disruptive to apply. To address this problem, we propose a first-line worm defense in the network stack, using shields -- vulnerability-specific, exploit-generic network filters installed in end systems once a vulnerability is discovered, but before a patch is applied. These filters examine the incoming or outgoing traffic of vulnerable applications, and correct traffic that exploits vulnerabilities. Shields are less disruptive to install and uninstall, easier to test for bad side effects, and hence more reliable than traditional software patches. Further, shields are resilient to polymorphic or metamorphic variations of exploits [43].In this paper, we show that this concept is feasible by describing a prototype Shield framework implementation that filters traffic above the transport layer. We have designed a safe and restrictive language to describe vulnerabilities as partial state machines of the vulnerable application. The expressiveness of the language has been verified by encoding the signatures of several known vulnerabilites. Our evaluation provides evidence of Shield's low false positive rate and small impact on application throughput. An examination of a sample set of known vulnerabilities suggests that Shield could be used to prevent exploitation of a substantial fraction of the most dangerous ones.

© 2003 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Encryption is often proposed as a tool for protecting the privacy of World Wide Web browsing. However, encryption-particularly as typically implemented in, or in concert with popular Web browsers-does not hide all information about the encrypted plaintext. Specifically, HTTP object count and sizes are often revealed (or at least incompletely concealed). We investigate the identifiability of World Wide Web traffic based on this unconcealed information in a large sample of Web pages, and show that it suffices to identify a significant fraction of them quite reliably. We also suggest some possible countermeasures against the exposure of this kind of information and experimentally evaluate their effectiveness.

Vulnerabilities in distributed applications are being uncovered and exploited faster than software engineers can, patch the security holes. All too often these weaknesses result from implicit assumptions made by an application about its inputs. One approach to defending against their exploitation is to interpose a filter between the input source and the application that verifies that the application's assumptions about its inputs actually hold. However, ad hoc design of such filters is nearly as tedious and error-prone as patching the original application itself. We have automated the filter generation process based on a simple formal description of a broad class of assumptions about the inputs to an application. Focusing on the back-end server application case, we have prototyped an easy-to-use tool that generates server-side filtering scripts. These can then be quickly installed on a front-end webs server (either in concert with the application or., when a vulnerability is uncovered), thus shielding the server application from a variety of existing and exploited, attacks, as solutions requiring changes to the applications are developed and tested. Our measurements suggest that input filtering can be done efficiently and should not be a performance concern for moderately loaded web servers. The overall approach may be generalizable to other domains, such as firewall filter generation and API wrapper filter generation.

Naor and Yung (1989) show that a one-bit-compressing universal one-way hash function (UOWHF) can be constructed based on a one-way permutation. This construction can be iterated to build a UOWHF which compresses by /spl epsiv/n bits, at the cost of /spl epsiv/n invocations of the one-way permutation. The show that this construction is not far from optimal, in the following sense, there exists an oracle relative to which there exists a one-way permutation with inversion probability 2/sup -p(n)/ (for any p(n)/spl isin//spl omega/(log n)), but any construction of an /spl epsiv/n-bit-compressing UOWHF. Requires /spl Omega/(/spl radic/n/p(n)) invocations of the one-way permutation, on average. (For example, there exists in this relativized world a one-way permutation with inversion probability n/sup -/spl omega/(1)/, but no UOWHF that involves it fewer than /spl Omega/(/spl radic/n/log n) times.) Thus any proof that a more efficient UOWHF can be derived from a one-way permutation is necessarily non-relativizing; in particular, no provable construction of a more efficient UOWHF can exist based solely on a "black box" one-way permutation. This result can be viewed as a partial justification for the practice of building efficient UOWHFs from stronger primitives (such as collision intractable hash functions), rather than from weaker primitives such as one-way permutations.

The quantum model of computation is a model, analogous to the probabilistic Turing machine (PTM), in which the normal laws of chance are replaced by those obeyed by particles on a quantum mechanical scale, rather than the rules familiar to us from the macroscopic world. We present here a problem of distinguishing between two fairly natural classes of functions, which can provably be solved exponentially faster in the quantum model than in the classical probabilistic one, when the function is given as an oracle drawn equiprobably from the uniform distribution on either class. We thus offer compelling evidence that the quantum model may have significantly more complexity theoretic power than the PTM. In fact, drawing on this work, Shor has recently developed remarkable new quantum polynomial-time algorithms for the discrete logarithm and integer factoring problems.

The quantum model of computation is a probabilistic model, similar to the probabilistic Turing Machine, in which the laws of chance are those obeyed by particles on a quantum mechanical scale, rather than the rules familiar to us from the macroscopic world. We present here a problem of distinguishing between two fairly natural classes of function, which can provably be solved exponentially faster in the quantum model than in the classical probabilistic one, when the function is given as an oracle drawn equiprobably from the uniform distribution on either class. We thus offer compelling evidence that the quantum model may have significantly more complexity theoretic power than the probabilistic Turing Machine. In fact, drawing on this work, Shor (1994) has recently developed remarkable new quantum polynomial-time algorithms for the discrete logarithm and integer factoring problems.>

shuffles", performed on a set of items.