Computer Security and Cryptography Reading Group
June 2004 List

URL: http://www.icsi.berkeley.edu/~nweaver/containment/

Computer worms -- malicious, self-propagating programs -- represent a significant threat to large networks. One possible defense, containment, seeks to limit a worm's spread by isolating it in a small subsection of the network. In this work we develop containment algorithms suitable for deployment in high-speed, low-cost network hardware. We show that these techniques can stop a scanning host after fewer than 10 scans with a very low false-positive rate. We also augment this approach by devising mechanisms for cooperation that enable multiple containment devices to more effectively detect and respond to an emerging infection. Finally, we discuss ways that a worm can attempt to bypass containment techniques in general, and ours in particular.

URL: http://www.ece.cmu.edu/~lbauer/papers/editauto.pdf

We analyze the space of security policies that can be enforced by monitoring and modifying programs at run time. Our program monitors, called edit automata, are abstract machines that examine the sequence of application program actions and transform the sequence when it deviates from a specified policy. Edit automata have a rich set of transformational powers: They may terminate the application, thereby truncating the program action stream; they may suppress undesired or dangerous actions without necessarily terminating the program; and they may also insert additional actions into the event stream.

After providing a formal definition of edit automata, we develop a rigorous framework for reasoning about them and their cousins: truncation automata (which can only terminate applications), suppression automata (which can terminate applications and suppress individual actions), and insertion automata (which can terminate and insert). We give a set-theoretic characterization of the policies each sort of automaton can enforce and we provide examples of policies that can be enforced by one sort of automaton but not another.

URL: http://doi.acm.org/10.1145/353323.353382

A precise characterization is given for the class of security policies enforceable with mechanisms that work by monitoring system execution, and automata are introduced for specifying exactly that class of security policies. Techniques to enforce security policies specified by such automata are also discussed.

URL: http://oncampus.richmond.edu/~dszajda/research/papers/sp03_szajda_d.pdf

The past few years have seen the development of distributed computing platforms designed to utilize the spare processor cycles of a large number of personal computers attached to the Internet in an effort to generate levels of computing power normally achieved only with expensive supercomputers. Such large scale distributed computations running in untrusted environments raise a number of security concerns, including the potential for intentional or unintentional corruption of computations, and for participants to claim credit for computing that has not been completed. This paper presents two strategies for hardening selected applications that utilize such distributed computations. Specifically, we show that carefully seeding certain tasks with precomputed data can significantly increase resistance to cheating (claiming credit for work not computed) and incorrect results. Similar results are obtained for sequential tasks through a strategy of sharing the computation of N tasks among K>N nodes. In each case, the associated cost is significantly less than the cost of assigning tasks redundantly.

URL: http://crypto.stanford.edu/~pgolle/papers/distr.html

Computationally expensive tasks that can be parallelized are most efficiently completed by distributing the computation among a large number of processors. The growth of the Internet has made it possible to invite the participation of just about any computer in such distributed computations. This introduces the potential for cheating by untrusted participants. In a commercial setting where participants get paid for their contribution, there is incentive for dishonest participants to claim credit for work they have not done. In this paper, we propose security schemes that defend against this threat with very little overhead. Our weaker scheme discourages cheating by ensuring that it does not pay off, while our stronger schemes let participants prove that they have done (almost) all the work they were assigned with high probability.