Lambda the Ultimate

Brumley, Poosankam, Song & Zheng, 2008. Automatic Patch-Based Exploit Generation is Possible: Techniques and Implications:

The automatic patch-based exploit generation problem is: given a program P and a patched version of the program P′, automatically generate an exploit for the potentially unknown vulnerability present in P but fixed in P'. In this paper, we propose techniques for automatic patch-based exploit generation, and show that our techniques can automatically generate exploits for 5 Microsoft programs based upon patches provided via Windows Update. Although our techniques may not work in all cases, a fundamental tenet of security is to conservatively estimate the capabilities of attackers. Thus, our results indicate that automatic patch-based exploit generation should be considered practical. One important security implication of our results is that current patch distribution schemes which stagger patch distribution over long time periods, such as Windows Update, may allow attackers who receive the patch first to compromise the significant fraction of vulnerable hosts who have not yet received the patch.

The technique is based on flow analysis, to test code that gets changed for boundaries where safety properties fail. The limitations of the technique they have developed automatically generate vulnerabilities for only a small fraction of propagated updates. Nonetheless I find it astonishing that such a simple analysis can provide such a payoff. Via Bruce Schneier.

My introduction to formal systems was in a cybernetics class. The more I learn about concepts in programming language design, and the direction that hardware seems to be evolving, the more I think that a domain specific language for cybernetics would be a worthwhile experiment. Has someone done this already? I see glimmers of possibility in the pi-calculus, functional-reactive programming, dataflow languages, DSL's for audio synthesis. I was intregued, back when this old thread was posted, by Hank Thediek's comments, and some others following along his line of thinking. It has haunted me since.

I would love to be told that someone has already made such and such language and this is why it does not work to integrate cybernetic models into programming. But, if it has not been really tried, I have an instinct that tells me the results could be very interesting.

On a untested brainstorm kind of level, it seems like feedback could be a refinement of a closure variable or monad, the concept of a system that can be open or closed to energy, perturbation, information, or control seems to map well to varying levels of scoping, encapsulation and information hiding... etc. Of course, alot of the information theory and computation theory that evolved through with and leading up to cybernetcs are also ancestors of modern computer science, but it really seems like the low hanging fruit is still ripe and yet to be plucked.

The biggest rift I see between computer science and cybernetics is that cybernetics seems optimized for systems where components are unknowable or unpredictable (harsh external environments, hostile or incompetent users, incomplete or error-prone measurements, heuristic behaviors), while computer science seems to always strive for complete information, provability. To attempt what is surely an overgeneralization, but something close to what I mean: a cyberneticist adds redundancy to prevent failure, a computer scientist eliminates redundancy to simplify models (and then any reader of the daily wtf would be able to tell you: a software developer puts in redundancy in a way that increases the chances of failure).

Since cybernetics was designed for systems with heterogeneous and loosely coupled components with a minimum of (well specified) information flow, it seems like an ideal model for programming with multiple processes/computers, for human/computer interaction design, and for compiler/language design (finding the best fit of a high level formal model and a limited state machine representation of that model).

To sum up: is there a cybernetic DSL that someone made that I can try? Is cybernetics just out of fashion, or technically unsound and superseded, my teachers just those last conservative dinosaurs who never admitted they were wrong? Have cybernetic principles been tested and dismissed as a failure, integrated so sloppily that we no longer know what we knew in the '50s, or simply overlooked?

Please forgive the rambling of this post, I am trying to talk about something I have a incomplete understanding of, and would be honored to have others here help me clarify these things.