Jeraig
`Spe
`
`
`
`«itmmasonssites”
`
`i
`
`ont,
`
`—
`
`endla fD
`
`
`The Sixth Workshop on
`
`Hot Topics in Operating
`
`Systems
`19-AUG-1987BSDSEEF"
`(HotOS-VI)
`HHA
`“* *
`
`-AUG-1997 BSDS 793!°,3°°
`
`9352.231659
`
`S
`
`ive
`
`
`
`
`
`Vi
`so ahs Fg
`WA sm ont Fa
`
`«
`7 OY ot lee ee GS GC
`LW6 Gia I « k-
`f
`\
`
`MaAapvlewVIFitLtebxX ./
`
`
`
`5-6 May, 1997
`Cape Cod, Massachusetts ay
`TONIGHT
`ot
`C
`ESLB T net
`WE
`RIPSEVWE
`i Hu4CAE
`
`TleGatValue()
`nA
`ee
`Sponsored by the
`IEEE Computer Society Technical Committeeon ~~=
`Operating Systems and Application Environments (TCOS)
`Corporate sponsors:
`AT&T, CLARiiON, Digital Equipment Corporation,
`Lucent Technologies, Microsoft, and Sun Microsystems
`® IEEE Computer Society Press
`ELECTRONICS ENGINEERS. Ne
`
`f
`
`
`
`ba
`fF
`L.
`ninstru
`
`C
`
`a es
`fa
`
`££
`a §
`
`KYOCERA1005
`
`KYOCERA 1005
`
`

`

`HotOS-VI
`
`
`
`
`
`
`
`r
`Ge 4
`
`7
`‘
`{
`
`i
`i
`\
`|
`
`i
`
`
`
`
`
`KYOCERA1005
`
`KYOCERA 1005
`
`

`

`Proceedings
`
`The Sixth Workshop on
`Hot Topics in
`Operating Systems
`
`May 5 — 6, 1997
`
`Cape Cod, Massachusetts
`
`Sponsored by
`
`IEEE Computer Society Technical Committee on Operating Systems (TCOS)
`
`Corporate Sponsors
`
`AT&T, CLARiON, Digital Equipment Corporation,
`Lucent Technologies, Microsoft, and Sun Microsystems
`
`®
`
`IEEE Computer Society Press
`Los Alamitos, California
`
`Washington
`
`e
`
`Brussels
`
`e
`
`Tokyo
`
`KYOCERA1005
`
`KYOCERA 1005
`
`

`

`Table of Contents
`The 6th Workshop on Hot Topics in Operating Systems (HotOS-VI)
`
`From the General Chair ............................................................................................................................................. ix
`From the Program Chair ............................................................................................................................................. x
`Conference Committees ............................................................................................................................................. xi
`
`Implementation
`Session Leader: Peter Druschel
`
`Experience with the Development of a Microkernel-Based, Multi-Server Operating System .................................... 2
`F. Rawson Ill
`
`The Failure of Personalities to Generalize .................................................................................................................. 8
`B. Fleisch
`
`The Flux OS Toolkit: Reusable Components for OS Implementation ...................................................................... 14
`B. Ford, J. Lepreau, S. Clawson,
`K. Van Maren, B. Robinson, J. Turner
`
`Formal Methods: A Practical Tool for OS Implementors ......................................................................................... 20
`P. Tullmann, J. Turner, J. McCorquodale,
`J. Lepreau, A. Chitturi, G. Back
`
`Microkernels
`Session Leader: John Carter
`
`Achieved IPC Performance ...................................................................................................................................... 28
`J. Liedtke, K. Elphinstone, S. Schonberg,
`H. Hartig, G. Heiser, N. Islam, T. Jaeger
`
`The Network Hardware is the Operating System ...................................................................................................... 32
`F. Ballesteros, L. Fernandez
`
`Customizability
`Session Leader: Pei Cao
`
`Extensible Kernels are Leading OS Research Astray ............................................................................................... 38
`P. Druschel, V. Pai, W. Zwaenepoel
`
`Customization Lite .................................................................................................................................................... 43
`M. Auslander, H. Franke,
`B. Gamsa, 0. Krieger, M. Stumm
`
`Operating Systems for Component Software Environments ..................................................................................... 49
`N. Mendelsohn
`
`V
`
`KYOCERA 1005
`
`

`

`Security
`Session Leader: Rob Gingell
`
`Secure Applications Need Flexible Operating Systems ............................................................................................ 56
`D. Mazieres, M. Kaashoek
`
`Security for Extensible Systems ............................................................................................................................... 62
`R. Grimm, B. Bershad
`
`Building Diverse Computer Systems ........................................................................................................................ 67
`S. Forrest, A. Somayaji, D. Ackley
`
`Preventing Denial-of-Service Attacks on a µ-Kernel for WebOSes ......................................................................... 73
`J. Liedtke, N. Islam, T. Jaeger
`
`The Internet as a Big Distributed System
`Session Leader: Jeff Mogul
`
`Query Routing: Applying Systems Thinking to Internet Search ............................................................................... 82
`P. Leach, C. Weider
`
`General Purpose Proxies: Solved and Unsolved Problems ....................................................................................... 87
`B. Zenel, D. Duchamp
`
`Reduce, Reuse, Recycle: An Approach to Building Large Internet Caches ............................................................. 93
`S. Gadde, M. Rabinovich, J. Chase
`
`Distributed Systems Support for Networked Games ................................................................................................ 99
`T. Chiueh
`
`Rethinking
`Session Leader: Mary Baker
`
`Operating System Directions for the Next Millennium .......................................................................................... 106
`R. Draves, W. Bolosky, R. Fitzgerald, C. Fraser,
`M. Jones, T. Knoblock, R. Rashid
`
`Other panelists: B. Frankston, A. Nemeth, D. Presotto, J. Waldo
`
`System Services
`Session Leader: Brad Chen
`
`Run-Time Code Generation as a Central System Service ....................................................................................... 112
`M. Franz
`
`What Synchronous Groupware Needs: Notification Services ................................................................................ 118
`M.Day
`
`VI
`
`KYOCERA 1005
`
`

`

`Building Diverse Computer Systems
`
`Stephanie Forrest t
`Dept. of Computer Science
`University of New Mexico
`Albuquerque, NM 87131
`forrest@cs.unm.edu
`
`Anil Somayajit
`Dept. of Computer Science
`University of New Mexico
`Albuquerque, NM 87131
`soma@cs.unm.edu
`
`David H. Ackley
`Dept. of Computer Science
`University of New Mexico
`Albuquerque, NM 87131
`ackley@cs.unm.edu
`
`Abstract
`
`Diversity is an important source of robustness in biological
`systems. Computers. by contrast, are notable for their lack
`of diversity. Although homogeneous systems have many ad(cid:173)
`vantages, the beneficial effects of diversity in computing
`systems have been overlooked, specifically in the area of
`computer security. Several methods of achieving software
`diversity are discussed based on randomizations that re(cid:173)
`spect the specified behavior of the program. Such random(cid:173)
`ization could potentially increase the robustness of software
`systems with minimal impact on convenience, usability, and
`efficiency. Randomization of the amount of memory alloc(cid:173)
`ated on a stack frame is shown to disrupt a simple buffer
`overflow attack.
`
`1 Introduction: Diversity is valuable
`
`Diversity is an important source of robustness in biolo(cid:173)
`gical systems. A stable ecosystem, for example, contains
`many different species which occur in highly-conserved fre(cid:173)
`quency distributions. If this diversity is lost and a few spe(cid:173)
`cies become dominant, the ecosystem becomes susceptible
`to perturbations such as catastrophic fires, infestations, and
`disease. Similarly, health problems can emerge when there
`is low genetic diversity within a species, as in the case of en(cid:173)
`dangered species or animal breeding programs. The verteb(cid:173)
`rate immune system offers a third example, providing each
`individual with a unique set of immunological defenses,
`helping to control the spread of disease within a population.
`Computers, by contrast, are notable for their lack of di(cid:173)
`versity. Manufacturers produce multitudes of identical cop(cid:173)
`ies from a single design, with the goal of making every
`hardware and software component identical. Beyond the
`economic leverage provided by the massive cloning of one
`
`t Current address: MIT Artificial Intelligence Laboratory, 545 Techno(cid:173)
`logy Sq., Cambridge, MA 02139.
`
`design, such homogeneous systems have other advantages:
`They behave consistently, application software is more port(cid:173)
`able and more likely to run identically across machines,
`debugging is simplified, and distribution and maintenance
`tasks are eased. Standardization efforts are a further ex(cid:173)
`ample of the almost universal belief that homogeneity is
`beneficial.
`As computers increasingly become mass-market com(cid:173)
`modities, the decline in the diversity of available hardware
`and software is likely to continue, and as in biological sys(cid:173)
`tems, such a development carries serious risks. All the ad(cid:173)
`vantages of uniformity become potential weaknesses when
`they replicate errors or can be exploited by an attacker.
`Once a method is created for penetrating the security of one
`computer, all computers with the same configuration be(cid:173)
`come similarly vulnerable. The potential danger grows with
`the population of interconnected and homogeneous com(cid:173)
`puters.
`In this paper we argue that the beneficial effects of di(cid:173)
`versity in computing systems have been overlooked, and we
`discuss methods by which diversity could be enhanced with
`minimal impact on convenience, usability, and efficiency.
`Although diversity considerations affect computing at many
`levels, here we focus primarily on computer security, and
`our emphasis is on diversity at the software level, particu(cid:173)
`larly for operating systems, which are a common point of
`intrusion.
`Computer security is a growing concern for open com(cid:173)
`puting environments. Malicious intrusions are multiplying
`as huge numbers of people connect to the Internet, exchange
`electronic mail and commercially valuable data, download
`files, and run computer programs remotely, often across
`international boundaries. Traditional approaches to com(cid:173)
`puter security-based on passwords, access controls, and
`so forth-are ineffective when an attacker is able to bypass
`them by exploiting some unintended property of a system.
`Finding ways to mitigate such attacks is likely to be an in(cid:173)
`creasing concern for the operating systems community.
`Deliberately introducing diversity into computer systems
`
`0-8186-7834-8/97 $10.00 © 1997 IEEE
`
`67
`
`KYOCERA 1005
`
`

`

`can make them more robust to easily replicated attacks.
`More speculatively, it might also enhance early detection of
`timing problems in software and other faults. Today, each
`new discovery of a security hole in any operating system
`is a serious problem, because all of the installed base of
`that operating system-thousands, if not millions, of ma(cid:173)
`chines, running almost exactly the same system software(cid:173)
`may well be vulnerable. An attack script developed on one
`machine is likely to work on thousands of other machines.
`If every intrusion, virus, or worm had to be crafted explicitly
`to a particular machine, the cost of trying to penetrate com(cid:173)
`puter systems would go up dramatically. Only sites with
`high-value information would be worth attacking, and these
`could be secured using stronger methods. The relevance of
`diversity to computer security was recognized as early as
`1989 in the aftermath of the Morris Worm, when it was ob(cid:173)
`served that only a few machine types were vulnerable to in(cid:173)
`fection [2]. Yet, this simple principle has not been adopted
`in any computer security system that we know of.
`
`2 Strategy: Avoid Unnecessary Consistency
`
`Our goal is to prevent widespread attacks by mak(cid:173)
`ing intrusions much harder to replicate. Can we intro(cid:173)
`duce diversity in a way that will tend to disrupt malicious
`attacks-even through security holes that have not yet been
`discovered-without compromising reliability, efficiency,
`and convenience for legitimate users? We believe that the
`answer is yes, because computers today are far more con(cid:173)
`sistent than necessary. For example, all but the lowest-level
`computational tasks are now implemented in a high-level
`programming language, and for each such program there
`are many different translations into machine code that will
`accomplish the same task. Each aspect of a programming
`language that is "arbitrary" or "implementation dependent"
`is an opportunity for randomized compilation techniques
`to introduce diversity. Here we extend the term "compil(cid:173)
`ation" beyond its usual meaning to include both load- and
`execution-time transformations [I]. Such diversity would
`preserve the functionality of well-behaved programs and be
`highly likely to disrupt others by removing unnecessary reg(cid:173)
`ularities. We refer to the strict virtual machine implied by
`a programming language's semantics as "the box." As far
`as possible all functional properties not required by a lan(cid:173)
`guage's semantics should vary across individuals, a prin(cid:173)
`ciple that we refer to as "surrounding the box with noise." In
`short, when a property is described by a programming lan(cid:173)
`guage as "arbitrary," that should mean "random," not "un(cid:173)
`specified but usually constant."
`We have adopted the following guidelines to help us
`identify the most promising directions to explore:
`
`1. Preserve high-level functionality. At the user level, the
`behavior of different systems should be predictable,
`
`and the input/output behavior of programs should be
`identical on different computers.
`·
`
`2. Introduce diversity in places that will be most disrupt(cid:173)
`ive to known or anticipated intrusion methods.
`
`3. Minimize costs, both run-time performance costs and
`the cost of introducing and maintaining diversity. We
`believe that the latter is likely to be related directly to
`where the variations are introduced in the software de(cid:173)
`velopment process. A load-time modification is likely
`to be less expensive than a compile-time modification
`which in turn is less expensive than requiring a de(cid:173)
`veloper to write multiple versions of application code.
`
`4. Introduce diversity through randomization. Tech(cid:173)
`niques based on prior knowledge of the semantics of
`the property being varied would also be possible, but
`they are unlikely to scale as well as methods based on
`randomization.
`
`3 Possible Implementations
`
`There are a wide variety of possible implementation
`strategies for introducing diversity. In this section, we dis(cid:173)
`cuss several of these and their implications for security. Our
`emphasis is on variability that can be introduced into soft(cid:173)
`ware between the time that the software is written and when
`it is executed, and as we mentioned earlier, we believe that
`variations introduced late in the compilation process are
`most likely to be successful. The expense of producing a
`unique executable for every different machine is high, and
`there are many ways that variations could be introduced
`after an executable is written. In our initial explorations,
`however, we cover as many different kinds of transforma(cid:173)
`tions as possible. We consider methods ranging from those
`that produce variability in the physical location of executed
`instructions, the order in which instructions are executed,
`the location of instructions in memory at run-time, and the
`ability of executing code to access external routines, files,
`and other resources.
`
`3.1 Adding or deleting nonfunctional code
`
`Perhaps the simplest method is to insert no-ops or other
`nonfunctional sequences of instructions at random loca(cid:173)
`tions in compiled code. Depending on the architecture, this
`could potentially affect timing relations at execution-time
`and would slightly change the physical location of instruc(cid:173)
`tions. It would also interact with compiler optimizations
`that insert no-ops to preserve cache alignment, but it might
`be possible to insert the nonfunctional code in such a way
`as to respect cache alignment constraints.
`
`68
`
`KYOCERA 1005
`
`

`

`The timing attacks reported on RSA [3] could potentially
`be disrupted using this method, although other remedies for
`this particular attack have also been proposed.
`
`3.2 Reordering code
`
`Optimizing and parallelizing compilers use many tech(cid:173)
`niques to improve performance, and some of these could be
`used to generate code variations. For example,
`
`1. Basic blocks: Rearrange the basic blocks of compiled
`code in random order. This would cause instructions
`to be stored in different locations but would not affect
`the order in which they are executed. However, basic(cid:173)
`block placement is an important performance optim(cid:173)
`ization [6], so the impact on execution-time efficiency
`for this method is likely to be large.
`
`Basic-block rearrangements could potentially disrupt
`some viruses. However, most file-infector viruses in(cid:173)
`sert a single jump instruction that transfers control to
`the virus code (stored at the end of the program), and
`then return control to the original program. Thus, re(cid:173)
`arranging basic blocks in the program segment would
`be unlikely to affect this large class of viruses.
`
`2. Optimizations for parallel processing: Many tech(cid:173)
`niques exist for producing blocks of instructions that
`can be run simultaneously on multiple processors.
`These techniques could be applied to code intended for
`execution on a single processor, resulting in a unique
`order of execution. We do not know what if any intru(cid:173)
`sion methods this would disrupt. Further, the amount
`of variability that could be produced with this method
`would be limited to the amount of parallelism that
`could be extracted from the original program.
`
`3. Instruction scheduling: Vary the order of instructions
`within a basic block, while respecting the data and con(cid:173)
`trol dependencies present in the source code. A pre(cid:173)
`liminary study of the source code for the Linux ker(cid:173)
`nel concluded that the number of different orderings
`that could be automatically generated was very high
`[5]. As in the case for basic-block rearrangements, in(cid:173)
`teractions with code optimizations would need to be
`considered carefully to avoid serious degradations of
`execution-time performance.
`
`3.3 Memory layout
`
`There are standard ways of allocating memory when pro(cid:173)
`grams execute and of ordering the components of memory.
`These are arbitrary and could be varied in many ways. Here
`are a few examples:
`
`I. Pad each stack frame by a random amount (so return
`addresses are not located in predictable locations). The
`amount of padding could be fixed for each compilation
`and varied between compilations, or it could be varied
`within a single compilation.
`
`2. Randomize the locations of global variables, and the
`offsets assigned to local variables within a stack frame.
`
`3. Assign each newly allocated stack frame in an unpre(cid:173)
`dictable (e.g., randomly chosen) location instead of in
`the next contiguous location. This would have the ef(cid:173)
`fect of treating the stack as a heap, which would in(cid:173)
`crease memory-management overhead. Many func(cid:173)
`tional languages have this capability for constructs
`such as closures.
`
`Some of these memory-layout schemes would likely disrupt
`a pervasive form of attack-the buffer overflow-in which
`an input buffer is intentionally overflowed to gain access to
`an adjacent stack frame.
`There are several potential complications, however, in(cid:173)
`cluding whether and how to preserve Application Binary
`Interface (ABI) compatibility, preserving the correct func(cid:173)
`tionality for certain user functions (e.g., the C function "al(cid:173)
`loca"), and how to maintain compatibility with dynamic
`libraries.
`In spite of these complications, we consider
`memory-layout modifications to be a promising initial dir(cid:173)
`ection, because buffer overflows are such an important path
`of intrusion.
`
`3.4 Other transformations
`
`I. Process initialization: Instructions that are executed
`before user code could be varied. Such changes could
`involve varying object files such as crtO. o that are
`linked into every executable and are responsible for
`calling main. Alternatively, it would be possible to in(cid:173)
`troduce variations in the kernel (e.g., in execve) such
`that data locations (e.g., command-line arguments and
`environment variables) are randomized.
`
`2. Dynamic libraries and system calls: For a program
`to run on different machines, it must know the cor(cid:173)
`rect names and arguments for dynamic library routines
`and system calls. By varying names and permuting
`arguments, binaries could be made machine-specific.
`An importation process could also be developed that
`would allow users to convert foreign binaries into the
`local format. Such changes would make it much harder
`for viruses and worms to propagate.
`
`3. Unique names for system files: Varying the names of
`common system files so they are difficult for intruding
`code to find would be highly effective against attacks
`
`69
`
`KYOCERA 1005
`
`

`

`targeting these files. However, such changes would
`complicate system administration unreasonably unless
`authorized administrators were provided with a secure
`interface under the inverse mapping (from the random(cid:173)
`ized names back to their standard counterparts).
`
`4. Magic numbers in certain files, e.g., executables: The
`type of information contained in many files can be
`(at least tentatively) identified by searching for char(cid:173)
`acteristic signatures at the beginning of the file. In(cid:173)
`dividual systems could re-map such signatures to ran(cid:173)
`domly chosen alternatives and convert the signatures
`of externally obtained files via an explicit importation
`process.
`
`5. Randomized run-time checks: Many successful intru(cid:173)
`sions could be prevented if all compiled code per(cid:173)
`formed dynamic array bounds checking. However,
`such checks are rarely performed in production code
`because of perceived performance costs. Instead of re(cid:173)
`quiring every program to pay the cost of doing com(cid:173)
`plete dynamic checking, each executing program could
`perform some of these checks (potentially a very small
`number of them). Which checks were to be performed
`could be determined either at compile-time or at run(cid:173)
`time.
`
`4 Preliminary Results
`
`As an initial demonstration of these ideas, we have im(cid:173)
`plemented a simple method for randomizing the amount of
`memory allocated on a stack frame and shown that it dis(cid:173)
`rupts a simple buffer overflow attack (item 1 from Section
`3.3). Buffer overflow attacks arise because many programs
`statically allocate storage for input on the stack, and then
`do not ensure that their received input fits within the al(cid:173)
`lotted space. Because C does not require array bounds to
`be checked dynamically, overflows can result in the cor(cid:173)
`ruption of variables and return addresses. Buffer overflows
`are problematic in the context of programs that run as root
`in UNIX, primarily because they provide a way for a non(cid:173)
`privileged user to obtain root access. However, any script
`exploiting such vulnerabilities is brittle. To overwrite the re(cid:173)
`turn address, the distance between the start of the buffer and
`the function's return address on the stack must be known as
`well as the exact location of the code to be executed.
`If every compilation produced an executable with a dif(cid:173)
`ferent stack layout, then exploit scripts developed on one
`executable would have a low probability of success on other
`executables. To change the layout of the stack, we increase
`the size of the stack frame by a random amount, by adding
`a random amount of space to certain stack slots. Such addi(cid:173)
`tions affect both the stack layout for the modified function
`and the exact locations of every function called by it. To
`
`implement this, we made a small modification to gee (ver(cid:173)
`sion 2.7.2.1), so that it adds a random number of bytes to
`any stack allocation request larger than 16 bytes, where the
`number of extra bytes is randomly selected to be between 8
`and 64 in increments of 8. That is, on each new stack alloc(cid:173)
`ation request (above the 16-byte threshold), a random num(cid:173)
`ber is selected (one of 8, 16, 24, ... , 64) which designates
`the number of bytes of padding for that call. This gives one
`example of how a compiler could help users create unique
`systems, which are vulnerable to attack but vulnerable in
`ways different from every other computer.
`The idea behind the 16-byte threshold is to minimize the
`amount of unnecessary padding. Because the buffer over(cid:173)
`flow technique requires a relatively large buffer in which to
`store the intrusion, it is unnecessary to pad stack allocations
`smaller than some threshold. We have not experimented
`with different threshold sizes but chose one that we believe
`is well below the threshold needed for buffer-overflow at(cid:173)
`tacks.
`The revised version of gee produces a program that dis(cid:173)
`rupts a simple buffer overflow attack against lpr on Linux
`2.0.28, Debian Linux 1.1 [4]. This attack works by giv(cid:173)
`ing lpr a large argument for the -c (class) command-line
`switch. In the function card, lpr copies the command(cid:173)
`line argument into a fixed size local buffer causing an over(cid:173)
`flow. As a result, card transfers control to the original copy
`(located in argv), which execs a shell running as root. This
`attack is disrupted by changing the size of the buffer, pre(cid:173)
`venting card's return address from being overwritten.
`These modifications have a relatively small impact on
`execution-time performance. In tests of gzip and gee
`(compiled by both the modified and unmodified versions
`of gee) the differences in CPU time were negligible. Be(cid:173)
`cause our modifications cause a program to expand its use
`of stack memory, we expected some reduction in perform(cid:173)
`ance, which testing on additional programs might reveal.
`An important question is how much extra stack space is re(cid:173)
`quired for this method to be effective. In terms of static
`stack space, the answer appears to be 10-15%. In the gzip
`example, 17 slots exceed the 16-byte threshold (thus, quali(cid:173)
`fying for modification) out of a total of 125. Notably, these
`17 slots consume most of the stack usage for the program
`(93%). Similarly, in the case of gee, 313 slots exceed
`the threshold, out of 6183 total. The 313 slots account for
`64.7% of the stack usage.
`There are several parts to a buffer-overflow attack: (1)
`overflowing the original buffer to gain access to a return
`address, (2) transferring control to a known location con(cid:173)
`taining intrusive instructions, and (3) executing the intrus(cid:173)
`ive instructions. The stack-frame variations we described
`affect the first of these but not necessarily the second. For
`example, in Linux, command-line arguments are stored
`in a predictable location determined by the kernel and
`
`70
`
`KYOCERA 1005
`
`

`

`are not affected by stack-frame modifications. In the de(cid:173)
`scribed attack, the contents of argv are later copied into
`a stack frame (causing a buffer overflow), but the attacker
`has the option of transferring control to the original copy
`(stored in a highly predictable location). Although our
`method successfully disrupts the overflow and subverts the
`attack, these considerations suggest yet another possible
`randomization-one that we plan to explore in future work.
`
`5 Impact on Computer Security
`
`Here we give a brief overview of common security prob(cid:173)
`lems and our assessment of which diversity methods would
`be most effective against them. Unfortunately, assessing
`and documenting the most common routes of intrusion is
`difficult: (1) new routes of intrusion are continually be(cid:173)
`ing discovered, (2) old routes of intrusion are sometimes
`patched, (3) there are few if any reliable statistics on suc(cid:173)
`cessful intrusions, and (4) there is a distinction between the
`variety of intrusion methods and the frequency with which
`they are exploited.
`Software errors (e.g., buffer overflows, insecurely pro(cid:173)
`cessing command-line options, symlink errors, temp file
`problems, etc.) lead to several common forms of attack.
`Memory-layout variations, such as the one we implemen(cid:173)
`ted, would primarily affect buffer overflows. A race condi(cid:173)
`tion is an interaction between two normally operating pro(cid:173)
`grams via some shared resource (often, a file). Compilation
`techniques, such as the ones we have discussed, are unlikely
`to prevent race conditions. However, diversity at the level
`of the shared resource would likely be effective. For con(cid:173)
`figuration problems (e.g., setup errors in how a service is
`provided or file permission problems), unique naming of
`system files would be highly effective. Denial-of-service at(cid:173)
`tacks are sometimes due to software errors and sometimes
`due to lack of resource checking or poor policies. Thus, one
`diversity technique alone is unlikely to address all denial(cid:173)
`of-service problems. For problems associated with insecure
`channels (e.g., IP spoofing, terminal hijacking, etc.), we ex(cid:173)
`pect that cryptography techniques are probably more help(cid:173)
`ful than diversity techniques, at least for diversity generated
`on a single host. Trust abuse, including key management
`problems and inappropriately trusted IP addresses, could be
`addressed by generating a unique profile of each computer's
`behavior and using it to establish identity. A final security
`problem that has been well-studied is that of covert chan(cid:173)
`nels. It might be possible to introduce diversity to prevent
`exploitation of covert channels, although we have not stud(cid:173)
`ied it well enough to have specific suggestions.
`Within computer security there is widespread distrust
`of "security through obscurity"-for example, proprietary
`cryptographic algorithms that are kept secret on the grounds
`that publishing their algorithms would weaken their secur-
`
`ity. Such distrust is warranted-proprietary cryptographic
`algorithms, once revealed, often tum out to have serious
`flaws. Nevertheless, it is worth noting that at the level of
`whole systems, all security is ultimately based on making
`some aspect of the system obscure, whether it be passwords
`or private keys. Possession of a secret is the basis for grant(cid:173)
`ing differential access. By randomizing implementation de(cid:173)
`pendencies, our approach can be thought of as adding a new
`level of automatically-generated "secrets" that are transpar(cid:173)
`ent to properly functioning code, but which misbehaving
`code must possess to crack the system successfully. Fur(cid:173)
`ther, at the level of algorithms, our approach would actually
`reduce obscurity by eliminating obscure implementation(cid:173)
`dependent consistencies of which the algorithm designer
`was unaware and certainly did not intend, but which, once
`discovered, might form the basis of an attack.
`
`For some security applications it is important to certify
`that a computer system is trustworthy, through a combin(cid:173)
`ation of proving formal properties about the specification
`and testing and analyzing the implementation. Although
`the method we propose would complicate the testing pro(cid:173)
`cedure, any system that stayed within its formal specifica(cid:173)
`tions ("in the box") would be robust to variations outside
`the box. Thus, an implementation that successfully with(cid:173)
`stood random variations of the sort we propose would be
`more trustworthy than one that did not.
`
`6 Conclusion
`
`Diversity techniques such as those we have proposed
`here can serve an important role in the development of
`more robust and secure computing systems. They cannot,
`by themselves, solve all security problems, because many
`exploitable holes are created completely "within the box"
`of a program functioning under the semantics of the lan(cid:173)
`guage in which it is written. And indeed, diversity tech(cid:173)
`niques may sometimes disrupt legitimate use by unmask(cid:173)
`ing unintended implementation dependencies (i.e., "bugs")
`in benign code. Nonetheless, the essential principles of
`di