Countering Code-Injection Attacks With Instruction-SetRandomizationGaurav S. KcComputer Science Dept.Columbia [email protected] D. KeromytisComputer Science Dept.Columbia [email protected] PrevelakisComputer Science Dept.Drexel [email protected] describe a new, general approach for safeguarding systems a-gainst any type of code-injection attack. We apply Kerckhoff’sprinciple, by creating process-specific randomized instruction sets(e.g., machine instructions) of the system executing potentially vul-nerable software. An attacker who does not know the key to therandomization algorithm will inject code that is invalid for that ran-domized processor, causing a runtime exception. To determine thedifficulty of integrating support for the proposed mechanism in theoperating system, we modified the Linux kernel, the GNU binu-tils tools, and the bochs-x86 emulator. Although the performancepenalty is significant, our prototype demonstrates the feasibility ofthe approach, and should be directly usable on a suitable-modifiedprocessor (e.g., the Transmeta Crusoe).Our approach is equally applicable against code-injecting attacksin scripting and interpreted languages, e.g., web-based SQL injec-tion. We demonstrate this by modifying the Perl interpreter to per-mit randomized script execution. The performance penalty in thiscase is minimal. Where our proposed approach is feasible (i.e.,in an emulated environment, in the presence of programmable orspecialized hardware, or in interpreted languages), it can serve asa low-overhead protection mechanism, and can easily complementother mechanisms.Categories and Subject DescriptorsD.2.0 [Protection Mechanisms]: Software RandomizationGeneral TermsSecurity, Performance.KeywordsInterpreters, Emulators, Buffer Overflows.1. INTRODUCTIONSoftware vulnerabilities have been the cause of many computersecurity incidents. Among these, buffer overflows are perhaps thePermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.CCS’03,October27–31,2003,Washington,DC,USA.Copyright 2003 ACM 1-58113-738-9/03/0010 ...$5.00.most widely exploited type of vulnerability, accounting for approx-imately half the CERT advisories in the past few years [58]. Bufferoverflow attacks exploit weaknesses in software that allow them toalter the execution flow of a program and cause arbitrary code toexecute. This code is usually inserted in the targeted program, aspart of the attack, and allows the attacker to subsume the privilegesof the program under attack. Because such attacks can be launchedover a network, they are regularly used to break into hosts or as aninfection vector for computer worms [54, 4, 9, 10, 45, 63].In their original form [12], such attacks seek to overflow a bufferin the program stack and cause control to be transfered to the in-jected code. Similar attacks overflow buffers in the program heap[42, 5] or use other injection vectors (e.g., format strings [6]). Suchcode-injection attacks are by no means restricted to languages likeC; attackers have exploited failures in input validation of web CGIscripts to permit them to execute arbitrary SQL [7] and unix com-mand line [8] instructions respectively on the target system. Therehas been some speculation on similar attacks against Perl scripts(that is, causing Perl scripts to execute arbitrary code that is in-jected as part of input arguments). Although the specific techniquesused in each attack differ, they all result in the attacker executingcode of their choice, whether machine code, shell commands, SQLqueries, etc. The natural implication is that the attacker knows what“type” of code (e.g., x86 machine code, SQL queries, unix shellcommands) can be injected.This observation has led us to consider a new, general approachfor preventing code-injection attacks, instruction-set randomiza-tion. By randomizing the underlying system’s instructions, “for-eign” code introduced by an attack would fail to execute correctly,regardless of the injection approach. Thus, our approach addressesnot only stack- and heap-based buffer overflow attacks, but anytype of code-injection attack. What constitutes the instruction set tobe randomized depends on the system under consideration: com-mon stack or heap-based buffer overflow attacks typically injectmachine code that corresponds to the underlying processor (e.g.,Intel x86 instructions). For Perl injection attacks, the “instructionset” is the Perl language, since any injected code will be executedby the Perl interpreter. To simplify the discussion, we will focuson machine code randomization for the remainder of this paper,although we discuss our prototype randomized Perl in Section 3.2.Randomizing an arbitrary instruction set, e.g., the x86 machinecode, involves three components: the randomizing element, the ex-ecution environment (e.g., an appropriately modified processor),and the loader. Where the processor supports such functionality(e.g., the TransMeta Crusoe, some ARM-based systems [55], orother programmable processors), our approach can be implementedwithout noticeable loss of performance, since the randomizationprocess can be fairly straightforward, as we report in Section 2. We272describe the necessary modifications to the operating system andthe randomizing element. We use a modified version of the bochs-x86 Pentium emulator to validate our design. Generally, the loss ofperformance associated with an emulator is unacceptable for most(but not all [61]) applications: we present a small but concrete ex-ample of this in Section 3.1.3. Our prototype demonstrates the sim-plicity of the necessary software support. In the case of interpretedlanguages, our approach does not lead to any measurable loss inperformance. Compared to previous techniques, we offer greatertransparency to languages, applications and compilers, as well as asmaller impact on performance.Paper Organization. The remainder of this paper is organizedas follows. Section 2 presents the details of our approach. Sec-tion 3 describes two prototype implementations, for x86 executa-bles and Perl scripts