One of the most noteworthy features of computer security is its overwhelmingly defensive stance. While there are certain programming practices that mitigate threats (e.g. sanitize your inputs, check your array bounds), it is practically impossible to preclude all possible attempts to corrupt or co-opt a system. Granted, there are always a few stubborn hold-outs willing to step forward and claim that the system that they have constructed is constructed in that elusive "right way" that everyone so far has failed at. It's possible that one of these people may be right, but evidence seems to weigh against such claims.
All the way back in 1993, a landmark report from the Naval Research Laboratory [3] found that almost half of 50 serious security breaches involved code that correctly implemented its specification. Of course, that was well over 15 years ago, and so one might protest that perhaps some better model of security has come forward since that time. Even so, one has to take notice when large teams of talented programmers correctly implement a meticulously specified system, and the system nonetheless succumbs to attack. Cases such as this lead illustrious security researcher William Wulf to call for a revolutionized approach to security that abandons the old paradigms of "perimeter defense" [7] as late as last year. Wulf proposes a model of security inspired by the success of the Internet, wherein a small foundation with minimal but very general functionality allows for systems to adapt to localized and quickly evolving conditions as needed and desired. This seems a very pragmatic and promising approach, and the success of the Internet is nothing to sneeze at. Even so, one cannot help but wonder what exactly it is about the traditional way of doing things that leads it to fail.
Let's consider a very intuitive idea from the traditional theory of security. Noninterference is a rather early and very successful idea due originally to J. A. Goguen and J. Meseguer [2] that can be informally phrased as follows: if two users (or processes) share a system, then the action of one should have no effect on the other. In some sense, this is like what we would expect in many kinds of situations where security is important: if you're on a time-sharing system, you don't want your files, or what you do to them, to be visible to other people; if you're buying something online, you don't want the credit card number you send to the vendor to somehow end up on the computer of some third party not part of the transaction. Of course, such assurances are very hard to make on large systems that a lot of people use; it would be pure whimsy to suggest that one could ever make such an assurance about the Internet (especially considering that large-scale data mining by merchants and advertisers already counts, arguably, as producing unwanted side-effects), and it would even seem like a bit of stretch to make absolute promises about a large, practical system that a lot of different people had to use to readily exchange information. However, suppose that someone were to successfully construct a shared system conforming to Goguen-Meseguer noninterference; if we were really that confident in its conception and construction, we could be assured that no one would be meddling in anyone else's data, nor would the kernel be unwittingly divulging any secrets to attackers bent on trying to compromise it.
Here's the catch: even a perfectly conceived and constructed system has to interact with the rest of the world in order to be used by anyone. This of course introduces the vector of social engineering, whereby the human element becomes part of the system. Even so, we don't have to rely on operator fallibility to show how problems immediately and essentially arise once the theoretical construct is out of its own solitary universe. One such very simple and very clever example is due to Daryl McCullough [4], and works essentially as follows:
Imagine we don't want any information flowing from the red parts of the system to the blue parts, although blue-to-red is okay. (This is indicated by the directions of the arrows.) Considered separately, the blue and red parts of the system both satisfy noninterference, since the red portion consists only of a single process, while the blue portion is defined in such a way that its two processes never interact. Does the entire system obey noninterference, once its parts are put together? It turns out that it does not.
The reason for this comes from a subtle but important detail of machines, namely, their finiteness. Suppose that processes A and B fill up their respective input buffers -- which they certainly can do in any kind of realistic machine. Should they start throwing away messages, or should they wait? We don't want to lose any messages, so we insist that the processes wait once their respective buffers fill up. However, in order to know to wait, the buffer or some mechanism attached to it must be able to send signals back to its process, telling either to go ahead or wait. That is, we want our processes to perform blocking reads and writes on the buffers, wherein their execution is suspended until the necessary read or write becomes possible. Now suppose, that our red process has a one-bit input from S that is uses to decide which of buffers A or B to read from, i.e. red multiplexes A and B according to the input it receives from S. The red process waits until acknowledgment arrives in buffer C before reading the next input from S. Suppose processes A and B immediately fill their respective buffers; once our red process reads from one of them, the buffer will have space for a new message, and will signal back to its respective process that it can go ahead with its execution. This is all good and fine and perfectly reasonable. What's the problem? The problem is this: suppose also that A writes some innocuous notice to the output on the left, say '0', each time it sends to buffer A, and that B writes '1' to the same source each time it sends to buffer B. Why is this problem? Because, given this setup, the stream of bits being written to the (blue) output on the left now exactly matches the stream of inputs being read from the (red) input on the right, which is precisely what we did not want to happen.
One immediate conclusion that one can draw from this result is that some security properties simply are not composable, that is, even if two different systems exhibit the property, there is no guarantee that putting them together will result in a system that exhibits the same property. However, I think that there is another informative way of looking at what's happening in McCullough's example: connecting the blue to the red system gives the blue system an opportunity to emulate red.
Emulation is an idea that goes all the way back to Alan Turing's universal computer. In essence, one machine emulates another whenever it performs computations equivalent in rule and structure to another. This is what gives Turing's machine its universality; it has the capability to emulate any of a very large class of other machines, and hence to perform any computation of which any machine in that class is capable. Chip developers use emulators to test against design errors. Nostalgic gamers use emulators to play titles from long-defunct platforms on modern personal computers. Interpreted programming languages (e.g. Java) use an emulated abstract computer to achieve some measure of portability. However, the basic principle that one machine (or tool) can serve in the stead of any of large class of others seems to me much broader and deeper than any of the niche purposes to which it has so far been put, especially as regards security.
Most prisons in the United States place rigid constraints on what sorts of items prisoners are allowed to keep in their cells. The reason for this is that a small piece of metal or a hard, sturdy object can easily be improvised into an excavating tool or a weapon, given the proper motivation -- of which prison inmates typically have an abundance. Ingenuity in making and using tools is one of the distinguishing and noteworthy characteristics of humanity, and the dramatic success of the tool-weilding primate is a testament to the power of a usable tool, however crude. This is not a new or surprising observation. However, it is truly astonishing to observe the huge disparity between the smallness of the means necessary to cause a disruption and the explosive magnitude of the disruption itself. Who would have ever imagined that using a bludgeon instead of fists and teeth would have catapulted humans to the position of dominant predator, or that millennia later those same humans would be improvising artifacts for personal hygiene into deadly melee weapons?
What we have here is a very broad principle. How does it apply?
A number of attempts were made during the 1960s and 1970s to construct a universal Turing machine with the smallest number of possible states; Marvin Minsky constructed one with only 7 states and 4 symbols in 1962 [5]. Successive attempts collected and published by Yuri Rogozhin in 1998 produced at least one smaller machine. In 1985, Stephen Wolfram claimed that his famous Rule 110 one-dimensional cellular automaton was able to emulate a Turing machine with only two states and five symbols, sketching a proof in his widely read and controversial 2002 opus [6]. Though such constructions always give some whiff of obsession with arcana, they also give very concrete evidence of a genuinely startling conclusion: it takes very, very little in order to make almost anything possible.
This should be a very potent lesson for the discipline computer security. Systems can be very tightly walled off from the rest of the world, but it takes only a very narrow gap for an attacker to worm his way in. A first reflex is to try to wall off the system even tighter but this, ultimately, turns out to be a failing solution: one can only constrain the system's use so much before it becomes completely unusable, whereas the attacker needs only the slightest concession in order to devise an exploit. This seems to confirm Wulf's argument that a pitched battle over the integrity of a rigid boundary is doomed to defeat. However, it also gives a potentially very useful language in which to phrase the problems of security. Consider the following informal conjecture:
If a system S allows its users functionality F, then S is vulnerable to an exploit E if and only if F is computationally expressive enough to emulate E.
This is plainly visible in McCullough's construction above; the blocking signal from a full buffer gives the blue portion of the system exactly enough information to act as if it were reading off of the secret input buffer. Erik Buchanan, Ryan Roemer, and Stefan Savage presented a method of constructing exploits without the use of code injection (which I also cited here several months ago) at Black Hat 2008 [1], which seems to confirm this very same intuition. The authors showed that subverting normal control flow was sufficient to coerce "trusted" code into arbitrary computations, thus producing "bad" code without the need to introduce any new code.
Explaining security breaches in terms of "emulating your inferiors" also provides a graded metric of susceptibility. (This may be useful if it turns out that Mr. Wolfram is indeed right and the world is rife with computational universality.) If one system is capable of emulating another, then the time complexity of the emulated computations will always differ from those of the native, non-emulated computations by a constant factor. However, a given system may be better suited to emulating some systems than others, and the program required to set up the emulation may be substantially more or less complicated. A rock might serve as both a hammer or a crude knife, but it makes a much better hammer than knife; an actual knife, by contrast, can be improvised to a wide variety of very practical purposes. The same is undeniably true of computational systems; although the Rule 110 automaton can emulate a Universal Turing Machine, and that universal Turing Machine can emulate the operation of the latest multi-core processor running your favorite operating system, the time performance of your system would decrease by a very large (but nonetheless constant) factor, and require quite a bit of memory besides. In the same vein, dynamic database access through a webpage makes it relatively easy to steal privileged information from the database because (if the website is badly designed) the user has the chance to pass arbitrary SQL queries to the server, but would be much more difficult (by itself) to leverage into an attempt to seize control of the operating system kernel.
Malware, then is just software coerced into emulating an unwanted computation; attack vectors are essentially just abstract buses over which the victim machine receives instructions from its attacker; exploits are essentially programs running on a maliciously purposed abstract machine. This is, of course, all highly speculative, but it seems to give an expressive language in which to formulate many of the problems of security, and to tie together many well-developed branches of computer science.
[1] Buchanan, Erik, Ryan Roemer, and Stefan Savage. "Return-Oriented Programming: Exploits Without Code Injection". Presented at Black Hat 2008, slides available here
[2] Goguen, J. A. and J. Meseguer. "Security Policies and Security Models". IEEE Symposium on Security and Privacy, 1982.
[3] Landwehr, Carl E., Alan R. Bull, John P. McDermott and William S. Choi. "A Taxonomy of Computer Program Security Flaws, with Examples". ACM Computing Surveys, 26:3, September 1994.
[4] McCullough, Daryl. "Noninterference and the Composability of Security Properties". IEEE Symposium on Security and Privacy, 1988.
[5] Minsky, Marvin. "Size and Structure of Universal Turing Machines". Recursive Function Theory, Proceedings of the Symposium in Pure Mathematics, 5, American Mathematical Society 1962.
[6] Wolfram, Stephen. "A New Kind of Science". Wolfram Media, 2002.
[7] Wulf, William A. and Anita K. Jones. "Reflections on Cybersecurity". Science, vol. 326, 13 November 2009.
No comments:
Post a Comment