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 consider the problem of solving a symmetric, positive definite system of linear equations.The most well-known and widely-used method for solving such systemsis the preconditioned Conjugate Gradient method.The performance of this method depends crucially on knowing a good preconditioner matrix.We show that the Conjugate Gradient method itself canproduce good preconditioners as a by-product. These preconditioners allow us to derive new asymptotic bounds on the timeto solve multiple related linear systems.

Vulnerability-driven filtering of network data can offer a fast and easy-to-deploy alternative or intermediary to software patching, as exemplified in Shield [Wang et al. 2004]. In this article, we take Shield's vision to a new domain, inspecting and cleansing not just static content, but also dynamic content. The dynamic content we target is the dynamic HTML in Web pages, which have become a popular vector for attacks. The key challenge in filtering dynamic HTML is that it is undecidable to statically determine whether an embedded script will exploit the browser at runtime. We avoid this undecidability problem by rewriting web pages and any embedded scripts into safe equivalents, inserting checks so that the filtering is done at runtime. The rewritten pages contain logic for recursively applying runtime checks to dynamically generated or modified web content, based on known vulnerabilities. We have built and evaluated BrowserShield , a general framework that performs this dynamic instrumentation of embedded scripts, and that admits policies for customized runtime actions like vulnerability-driven filtering. We also explore other applications on top of BrowserShield.

Remote code injection exploits inflict a significant societal cost, and an active underground economy has grown up around these continually evolving attacks. We present a methodology for inferring the phylogeny, or evolutionary tree, of such exploits. We have applied this methodology to traffic captured at several vantage points, and we demonstrate that our methodology is robust to the observed polymorphism. Our techniques revealed non-trivial code sharing among different exploit families, and the resulting phylogenies accurately captured the subtle variations among exploits within each family. Thus, we believe our methodology and results are a helpful step to better understanding the evolution of remote code injection exploits on the Internet.

Capacity improvement is one of the principal challenges in wireless networking. We present a link-layer protocol called Slotted Seeded Channel Hopping, or SSCH, that increases the capacity of an IEEE 802.11 network by utilizing frequency diversity. SSCH can be implemented in software over an IEEE 802.11-compliant wireless card. Each node using SSCH switches across channels in such a manner that nodes desiring to communicate overlap, while disjoint communications mostly do not overlap, and hence do not interfere with each other. To achieve this, SSCH uses a novel scheme for distributed rendezvous and synchronization. Simulation results show that SSCH significantly increases network capacity in several multi-hop and single-hop wireless networking scenarios.

The perceptron algorithm, developed mainly in the machine learning literature, is a simple greedy method for finding a feasible solution to a linear program (alternatively, for learning a threshold function. ). In spite of its exponential worst-case complexity, it is often quite useful, in part due to its noise-tolerance and also its overall simplicity. In this paper, we show that a randomized version of the perceptron algorithm with periodic rescaling runs in polynomial-time. The resulting algorithm for linear programming has an elementary description and analysis.

We study the problem of finding an outlier-free subset of a set of points (or a probability distribution) in n-dimensional Euclidean space. A point x is defined to be a β-outlier if there exists some direction w in which its squared distance from the mean along w is greater than β times the average squared distance from the mean along w [1]. Our main theorem is that for any ε>0, there exists a (1-ε) fraction of the original distribution that has no O(\frac{n}{ε}(b+log \frac{n}{ε))-outliers, improving on the previous bound of O(n^7b/ε). This bound is shown to be nearly the best possible. The theorem is constructive, and results in a \frac{1}{1-ε} approximation to the following optimization problem: given a distribution μ (i.e. the ability to sample from it), and a parameter ε>0, find the minimum β for which there exists a subset of probability at least (1-ε) with no β-outliers.