The Geometry of Innocent Flesh on the Bone: Return-into-libc without Function Calls (on the x86)

Full version of an extended abstract published in Proceedings of ACM CCS 2007, ACM Press, 2007.

扩展摘要的完整版本发表于 2007 年 ACM CCS 2007 论⽂集，ACM Press。

The Geometry of Innocent Flesh on the Bone: Return-into-libc without Function Calls (on the x86)

⻣头上⽆辜⾁体的⼏何形状： ⽆需函数调⽤即可返回 libc（在 x86 上）

#笔者注解

主标题隐喻：

"The Geometry of Innocent Flesh on the Bone"（骨骼上无辜血肉的几何结构）是一个比喻，指代在看似无害的代码片段中寻找可利用的指令序列（gadgets）。这里的"骨骼"象征程序原本合法的代码结构，而"血肉"则指攻击者通过组合这些代码片段构建的攻击链，形成精密的利用逻辑

副标题技术含义：

"Return-into-libc without Function Calls (on the x86)"指一种针对x86架构的漏洞利用技术，特点是通过返回导向编程（ROP）绕过数据执行保护（DEP）。与传统"Return-to-libc"直接调用系统函数（如system()）不同，该技术通过拼接代码库（如libc）中零散的短指令序列（如pop, ret等），形成无需完整函数调用的攻击链，实现任意代码执行

技术背景补充：

• x86特性依赖：x86指令集的变长指令特性，使得在合法代码中容易找到可拼接的短指令序列（如0xC3对应ret指令）

• 防御绕过：通过复用程序自身的代码片段，可绕过DEP（不可执行栈）和ASLR（地址随机化）等防护机制，标志着ROP攻击技术的早期突破

这篇论文提出的方法为后续高级漏洞利用技术奠定了基础，被后续研究如《Hacking: The Art of Exploitation》多次引用

Hovav Shacham∗

hovav@cs.ucsd.edu

霍⽡夫·沙查姆

hovav@cs.ucsd.edu

Abstract

抽象的

We present new techniques that allow a return-into-libc attack to be mounted on x86 exe- cutables that calls no functions at all. Our attack combines a large number of short instruction sequences to build gadgets that allow arbitrary computation. We show how to discover such instruction sequences by means of static analysis. We make use, in an essential way, of the properties of the x86 instruction set.

译文：

我们介绍了允许在不调⽤任何函数的 x86 可执行⽂件上发起返回 libc 攻击的新技术。我们的攻击结合了⼤量短指令序列来构建 允许任意计算的⼩⼯具。我们展⽰了如何通过静态分析发现此类指令序列。我们以基本⽅式利⽤了 x86 指令集的属性。

1 Introduction

We present new techniques that allow a return-into-libc attack to be mounted on x86 executables that is every bit as powerful as code injection. We thus demonstrate that the widely deployed “W⊕X” defense, which rules out code injection but allows return-into-libc attacks, is much less useful than previously thought.

Attacks using our technique call no functions whatsoever. In fact, the use instruction sequences from libc that weren’t placed there by the assembler. This makes our attack resilient to defenses that remove certain functions from libc or change the assembler’s code generation choices.

Unlike previous attacks, ours combines a large number of short instruction sequences to build gadgets that allow arbitrary computation. We show how to build such gadgets using the short sequences we find in a specific distribution of gnu libc, and we conjecture that, because of the properties of the x86 instruction set, in any sufficiently large body of x86 executable code there will feature sequences that allow the construction of similar gadgets. (This claim is our thesis.) Our paper makes three major contributions:

1. We describe an efficient algorithm for analyzing libc to recover the instruction sequences that can be used in our attack.

2. Using sequences recovered from a particular version of gnu libc, we describe gadgets that allow arbitrary computation, introducing many techniques that lay the foundation for what we call, facetiously, return-oriented programming.

3. In doing the above, we provide strong evidence for our thesis and a template for how one might explore other systems to determine whether they provide further support.

∗ Work done while at the Weizmann Institute of Science, Rehovot, Israel, supported by a Koshland Scholars Program postdoctoral fellowship.

In addition, our paper makes several smaller contributions. We implement a return-oriented shell- code and show how it can be used. We undertake a study of the provenance of ret instructions in the version of libc we study, and consider whether unintended rets could be eliminated by compiler modifications. We show how our attack techniques fit within the larger milieu of return-into-libc techniques.

译文：

我们提出了新技术，允许在 x86 可执行⽂件上安装 return-into-libc 攻击，其威力与代码注⼊⼀样强⼤。因此，我们证明了⼴泛部署的“W⊕X” 防御（它排除了代码注⼊但允许 return-into-libc 攻击）的⽤处远没有以前想象的那么⼤。

使⽤我们的技术进行的攻击不会调⽤任何函数。事实上，我们使⽤的指令序列来⾃ libc，⽽这些指令序列并⾮由汇编程序放置在那里。这 使得我们的攻击能够抵御从 libc 中删除某些函数或更改汇编程序的代码⽣成选择的防御措施。

与之前的攻击不同，我们的攻击结合了⼤量短指令序列来构建允许任意计算的⼩⼯具。我们展⽰了如何使⽤在 gnu libc 的特定发行版中 找到的短序列来构建此类⼩⼯具，并且我们推测，由于 x86 指令集的属性，在任何足够⼤的 x86 可执行代码体中都会存在允许构建类似⼩⼯ 具的特征序列。（此主张是我们的论点。）我们的论⽂做出了三⼤贡献：

1. 我们描述了⼀种有效的算法来分析 libc，以恢复指令序列，可以⽤于我们的攻击。

2. 使⽤从特定版本的 gnu libc 恢复的序列，我们描述了允许任意计算的⼩⼯具，引⼊了许多为我们称之为⾯向返回编程奠定基础的技术。

3. 通过上述操作，我们为我们的论点提供了强有力的证据，并为如何探索其他系统以确定它们是否提供进⼀步的⽀持提供了模板。

在以⾊列雷霍沃特魏茨曼科学研究所完成的⼯作，由 Koshland 学者资助 项⽬博⼠后奖学⾦。

此外，我们的论⽂还做出了⼀些较⼩的贡献。我们实现了⼀个返回导向的 shell 代码并展⽰了如何使⽤它。我们对所研究的 libc 版 本中的 ret 指令的来源进行了研究，并考虑是否可以通过修改编译器来消除意外的 ret。我们展⽰了我们的攻击技术如何适应更⼤的 返回 libc 技术环境。

1.1 Background: Attacks and Defenses

Consider an attacker who has discovered a vulnerability in some program and wishes to exploit it. Exploitation, in this context, means that he subverts the program’s control flow so that it performs actions of his choice with its credentials. The traditional vulnerability in this context is the buffer overflow on the stack [1], though many other classes of vulnerability have been considered, such as buffer overflows on the heap [29, 2, 13], integer overflows [34, 11, 4], and format string vulnerabilities [25, 10]. In each case, the attacker must accomplish two tasks: he must find some way to subvert the program’s control flow from its normal course, and he must cause the program to act in the manner of his choosing. In traditional stack-smashing attacks, an attacker completes the first task by overwriting a return address on the stack, so that it points to code of his choosing rather than to the function that made the call. (Though even in this case other techniques can be used, such as frame-pointer overwriting [14].) He completes the second task by injecting code into the process image; the modified return address on the stack points to this code. Because of the behavior of the C-language string routines that are the cause of the vulnerability, the injected code must not contain nul bytes. Aleph One, in his classic paper, discusses how to write Linux x86 code under this constraint that execs a shell (for this reason called “shellcode”) [1]; but shellcodes are available for many platforms and for obtaining many goals (see, e.g., [31]).

This paper concerns itself with evaluating the effectiveness of security measures designed to mitigate the attacker’s second task above. There are many security measures designed to mitigate against the first task — each aimed at a specific class of attacks such as stack smashing, heap overflows, or format string vulnerabilities — but these are out of scope.

The defenders’ gambit in preventing the attacker’s inducing arbitrary behavior in a vulnerable program was to prevent him from executing injected code. The earliest iterations of this defense, notably Solar Designer’s StackPatch [27], modified the memory layout of executables to make the stack nonexecutable. Since in stack-smashing attacks the shellcode was typically injected onto the stack, this was already useful. A more complete defense, dubbed “W⊕X,” ensures that no memory location in a process image is marked both writable (“W”) and executable (“X”). With W⊕X, there is no location in memory into which the attacker can inject code to execute. The PaX project has developed a patch for Linux implementing W⊕X [22]. Similar protections are included in recent versions of OpenBSD. AMD and Intel recently added to their processors a per-page execute disable (“NX” in AMD parlance, “XD” in Intel parlance) bit to ease W⊕X implementation, and Microsoft Windows (as of XP SP2) implements W⊕X on processors with NX/XD support.

Now that the attackers cannot inject code, their response was to use, for their own purposes, code that already exists in the process image they are attacking. (It was Solar Designer who first suggested this approach [28].) Since the standard C library, libc, is loaded in nearly every Unix program, and since it contains routines of the sort that are useful for an attacker (e.g., wrappers for system calls), it is libc that is the usual target, and such attacks are therefore known as return- into-libc attacks. But in principle any available code, either from the program’s text segment or from a library it links to, could be used.

By carefully arranging values on the stack, an attacker can cause an arbitrary function to be invoked, with arbitrary arguments. In fact, he can cause a series of functions to be invoked, one after the other.

译文：

假设有攻击者发现某个程序存在漏洞并希望加以利⽤。在这种情况下，利⽤意味着攻击者破坏程序的控制流，以便程序使⽤其凭据执 行攻击者选择的操作。在这种情况下，传统的漏洞是堆栈上的缓冲区溢出，尽管还考虑了许多其他类型的漏洞，例如堆上的 缓冲区溢出、整数溢出 和 格式字符串漏洞（笔者注：缓存区漏洞类型 更好理解这几个类型笔者提供了示例代码见下）。在每种情况下，攻击者都必须完成两项任务：他必须找到某种⽅ 法来破坏程序的控制流，使其偏离其正常路径，并且他必须使程序按照他选择的⽅式运行。在传统的堆栈破坏攻击中，攻击者通过覆 盖堆栈上的返回地址来完成第⼀项任务，以便它指向他选择的代码⽽不是进行调⽤的函数。 （尽管在这种情况下也可以使⽤其他 技术，例如帧指针覆盖。）他通过将代码注⼊进程映像来完成第⼆项任务；堆栈上修改后的返回地址指向此代码。由于导致漏洞 的 C 语⾔字符串例程的行为，注⼊的代码不能包含空字节。Aleph One 在他的经典论⽂中讨论了如何在这种约束下编写执行 shell 的 Linux x86 代码（因此称为“shellcode”）；但 shellcode 可⽤于许多平台并可⽤于实现许多⽬标（例如，参⻅ [31]）。

本⽂主要关注评估旨在缓解上述攻击者的第⼆项任务的安全措施的有效性。有许多旨在缓解第⼀项任务的安全措施 每种 措施都针对特定类型的攻击，例如堆栈破坏、堆溢出或格式字符串漏洞 但这些不在本⽂讨论范围内。

防御者在防⽌攻击者在易受攻击的程序中引发任意行为时采取的策略是阻⽌攻击者执行注⼊的代码。这种防御的最早迭代，尤 其是 Solar Designer 的 StackPatch，修改了可执行⽂件的内存布局，使堆栈不可执行。由于在堆栈破坏攻击中，shellcode 通 常被注⼊到堆栈中，因此这已经很有⽤。⼀种更完整的防御措施，称为“W⊕X”，可确保进程映像中的任何内存位置都不会被标记为 可写（“W”）和可执行（“X”）。有了 W⊕X，攻击者就⽆法在内存中注⼊代码来执行。（笔者注：在Linux系统中 W（是英文Write的缩写：对应的权限数字是 “2”），X（是英文Execute的缩写：对应的权限数字是 “1”）它们分别代表着两种权限，写入和执行权限。这句话的简单意思就是 “攻击者没有写入和执行权限来注入shellcode到内存中去执行”也就导致了无法反向连接）PaX 项⽬已经为 Linux 开发了⼀个补丁， 实现了 W⊕X 。OpenBSD 的最新版本也包含类似的保护措施。 AMD 和 Intel 最近在其处理器中添加了每⻚执行禁⽤（AMD 术语中为“NX”，Intel 术语中为“XD”）位以简化 W⊕X 的实现，⽽ Microsoft Windows（从 XP SP2 开始）在⽀持 NX/XD 的处 理器上实现了 W⊕X。

既然攻击者⽆法注⼊代码，他们的反应就是使⽤他们正在攻击的进程映像中已经存在的代码来达到⾃⼰的⽬的。（Solar Designer 是第⼀个提出这种⽅法的⼈。）由于标准 C 库 libc ⼏乎加载到每个 Unix 程序中，并且它包含对攻击者有⽤的例程（例如，系统调⽤的包装器），因此 libc 是通常的⽬标，因此此类攻击被称为返回 libc 攻击。但原则上，可以使⽤任何可⽤的代码，⽆ 论是来⾃程序的⽂本段还是来⾃它链接到的库。

通过仔细安排堆栈上的值，攻击者可以调⽤任意函数并使⽤任意参数。事实上，他可以⼀个接⼀个地调⽤⼀系列函数 。

笔者注：

#整数溢出攻击和整数符号攻击

简介：

如果说格式化字符串攻击是黑客世界在2000年和2001年的大庆典，那么整数溢出攻击和整数符号攻击则是黑客们在2002年和2003年的节目。OpenSSH、Apache、Snort和Samba 等一大批在世界范围内都很流行的应用软件都存在着整数溢出漏洞，而这种漏洞会导致缓冲区【（我相信读到这里的人，很多人都会感到疑惑，不应是“缓存区”吗？为什么是缓冲区；笔者在这里解释一下，笔者没有打错，是因为你懂得太少了！！！）缓冲区是内存空间的一部分。也就是说，在内存空间中预留了一定的存储空间，这些存储空间用来缓冲输入或输出的数据，这部分预留的空间就叫做缓冲区】溢出问题。与缓冲区溢出漏洞一样。整数溢出也是一种编程错误；但整数溢出漏洞往往隐藏得很深——在最终发布的应用程序里发现整数溢出漏洞，意味着编译器都成了程序员的帮凶。

那么，什么是整数？在C语言里，整数是一种用来保存数字的数据类型。整数是没有小数的实数，也就是说，整数不支持小数点运算。计算机只能处理二进制数字，所以整数必须具备区分数值是一个正整数还是一个负整数的能力。有符号整数（带有正号或负号的整数）的第一个存储字节的最高位（符号位）必须是1或0。如果符号是1【笔巧：C语言中while循环里，如果条件为1就是True，否则条件为0就是False。同样可以迁移到这里来理解“符号位”；例：1就是True，为负数，为真】，则表示该数值是一个负数；如果是0，则表示那是一个正数。无符号正数没有符号位，所以无符号整数都是正数。因为判断某个变量到底是一个有符号整数还是一个无符号整数并没有统一标准，下面看到的种种混乱就是这一原因而引起的。

不同的整数类型所能容纳的数值大小是有限度的，超出了这个限度的数值就会引起溢出。比如说，16位数据类型所能容纳的最大整数值是32767，而32位数据类型所能容纳的最大整数值是2147 483 647（我们这里说的都是有符号整数）。那么，如果你把整数值60 000赋值给一个16位的有符号数据类型，将会发生什么样的事情呢？将发生整数溢出，实际存储在那个变量里的值将是-5536。我们来看看这种事情是如何发生的。

ISO C99标准指出：整数溢出将导致未定义行为的后果：不同的编译器会对整数溢出做出不同的处理。它们或许会忽略这种情况，或许会试图纠正这种情况，或许会放弃对那个程序继续编译。大多数编译器都会忽略这种错误。但这种“忽略”并不意味着完全不做处理，根据 ISO C99 标准的有关规定，编译器应该采用某种同余算法把一个较大的值“塞”到一个较小的数据类型里去。同余算法在将数值“塞”到较小的数据类型之前执行以确保能够匹配该数据类型。为什么应该关心这些同余算法呢？因为编译器在执行算法时都是在幕后处理，程序员无法得知自己编写的程序里存在着一个整数溢出漏洞。很多编译器都使用下面的同余式：

stored_value = value % (max_value_for_datatype + 1)

简单地说，这个公式将从最高位开始把数值value截短到数据类型datatype刚好能够容纳的长度，然后再把它赋值给变量 stored_value。这种行为可以在下面这个例子里看得很清楚：

#include <stdio.h>

int main(int argc, char **argv) {
    long l = 0xdeadbeef;
    short s = l;
    char c = l;
    printf("long: %x\n", l);
    printf("short: %x\n", s);
    printf("char: %x\n", c);
    return 0;
}

在32位的Intel平台上，上面这个程序的输出将是：

long: deadbeef

short: ffffbeef

char: ffffffef

看明白了吗？short类型的变量“s"和char类型的变量"c"是long类型的变量"l"从最高位开始被截短到适当长度后剩下来的东西：short类型只能存储2个字节长的数据，所以变量"s"的值成为了”beef"：char类型只能存储1个字节长的数据，所以变量"c"的值成为了“ef"。这种截短使得给定数据类型（比如本例中的 short 和 char）的变量只能容纳实际数值（比如本例中的“deadbeef"）的一部分。我们上文提到的“60 000"变成"-5536”正是因为这个原因。

#整数溢出：无符号整数回绕

#include <stdio.h>

int main() {
    unsigned short a = 65535; // 无符号短整型最大值
    a = a + 5;               // 溢出后回绕到 4
    printf("a = %d\n", a);   // 输出 4
    return 0;
}

#整数溢出：有符号整数溢出导致负数

#include <stdio.h>

int main() {
    short b = 32767;        // 有符号短整型最大值
    b = b + 5;              // 溢出后变为 -32764
    printf("b = %d\n", b);  // 输出 -32764
    return 0;
}

漏洞原因：有符号整数溢出导致符号位错误，数值变为负数。此类漏洞可能引发逻辑错误（如数组索引为负）

#格式化字符串攻击

每隔数年，就会有一类新的漏洞暴风骤雨般地席卷安全界。格式化字符串漏洞在软件代码中已经出现了许多年，但是其危险直到2000年中期才显露出来。格式化字符春和缓冲区溢出攻击从机制上讲非常类似，都源自不良的程序设计习惯。

格式化字符串漏洞是格式化输出函数（包括 printf（）和 sprintf() ）的微小程序设计错误造成的。攻击者对此的利用，主要通过传递精心编制的含有格式化指令的文本字符串，以使目标计算机执行任意命令。如果有漏洞的程序以 root 权限运行，并且成为了攻击目标，就会导致严重的安全风险。当然，大多数攻击者会把精力放在 SUID root 程序中格式化字符串的漏洞上。

格式化字符串如果能正确使用是非常有用的。它提供了用动态数目的参数格式化文本输出的方式，但每个参数应该正确地匹配字符串中的格式化指令。printf函数通过扫描格式化字符串中的 "%" 字符来完成的这项工作。找到 ”%“ 字符后，再通过 stdarg 系列函数获取参数。紧接”%“的字符就是格式化指令，用于指示如何格式化文本字符串。举一例子，%i指令可以将整数变量格式化位可读的十进制值。如 printf("%i", val)将在屏幕上显示val的十进制形式。如果指令的数目与所提供的参数数目不符，就会出现安全问题。要指出的是，每个所给出的要格式化的参数是保存在堆栈中的。如果格式化指令比参数多，堆栈中后面保存的数据就将被当作参数。因此格式化指令和参数的不匹配将导致奇怪的输出。

有些懒惰的程序员喜欢使用用户提供的参数作为格式化字符串本身，而不是使用更合适的字符串输出函数，这时会出现另一种问题。此类糟糕的编程习惯可以举一个例子，打印变量buf中保存的字符串。例如，可以直接用 puts(buf) 或者 printf("%s", buf) 将字符串输出到屏幕。如果程序员不遵守格式化输出函数的规则，就会出问题。虽然后面的参数在printf()中是可选的，但第一个参数必须是格式化字符串。如果将用户提供的参数作为第一个参数，比如 printf(buf) 中，程序可能会出现严重的安全风险。用户只需把适当的格式化字符串指令（如%x）传送给 printf 函数，就可以把存放在整个进程空间的数据全部读取出来，%x 就让 printf 把堆栈里的内容以字（WORD）为单位显示出来。

读取进程内存空间本身是一个问题。但是，如果攻击者可以直接写入内存，就更具摧毁性了。幸运的是，printf()函数为攻击者提供了 %n 指令。printf() 并不格式化和输出相应的参数，而是把参数当作整数的内存地址，并将一些字符保存到这个内存地址指示的位置。格式化字符串漏洞的最后一个关键，是攻击者能够将数据放入格式化字符串指令要处理的堆栈中——通过printf()处理格式化字符串的方式实现。数据可以很方便地在处理之前放入堆栈。因此，如果在格式化字符串中提供了足够的额外指令，格式化字符串本身将被用作格式化指令的后续参数。

下面是攻击程序的一个例子：

#include <stdio.h>
#include <string.h>

int main(int argc, char **argv){
    char buf[2048] = { 0 };
    strncpy(buf, argv[1], sizeof(buf) - 1);
    printf(buf);
    putchar('\n');
    return 0;
} 

程序编译运行的结果如下：

[shadow $] ./code DDDD%x%x

DDDDbffffaa44444444

可以看到，经printf()处理的由%x 指定的格式化输出结果，它把堆栈中的内容以十六进制的格式输出。更有趣的是，第二个参数的格式化输出是”44444444“，代表着内存中对应的”DDDD“。如果把第二个%x格式化指令改成%n，由于应用程序想写到地址0x44444444，则会出现内存越段错误（除非那段内存是可写的）。攻击者（和内存漏洞发掘者）经常采用这种方式在堆栈中写入返回地址。覆写堆栈中的地址将使函数返回到攻击者在格式化字符串中提供的恶意代码段。可以看到，这种情况是极为有害的，这正是格式化字符串攻击如此致命的原因。

#格式化字符串：读取栈内存敏感信息

#include <stdio.h>

int main() {
    char input[100];
    printf("Enter input: ");
    gets(input);            // 用户输入如 "%x %x %x"
    printf(input);          // 直接输出栈内存数据
    return 0;
}

漏洞原因：未经验证直接将用户输入作为格式字符串。攻击者可输入 %x 泄露栈内存内容（如返回地址、局部变量）

#格式化字符串：利用 %n 修改内存值

#include <stdio.h>

int main() {
    int secret = 0;
    char input[100];
    printf("Enter input: ");
    gets(input);            // 用户输入如 "AAAA%n"
    printf(input, &secret); // 将已输出字符数（4）写入 secret
    printf("\nsecret = %d", secret); // 输出 secret = 4
    return 0;
}

漏洞原因：%n 将已输出的字符数写入 secret 的地址。攻击者可构造输入修改关键变量（如身份验证标志）

1.2 Our Results

One might reasonably ask why, in the face of return-into-libc attacks, it was considered worthwhile to invest in deploying W⊕X. The answer is that return-into-libc was considered a more limited attack than code injection, for two reasons:

1. in a return-into-libc attack, the attacker can call one libc function after another, but this still allows him to execute only straight-line code, as opposed to the branching and other arbitrary behavior available to him with code injection;

2. the attacker can invoke only those functions available to him in the program’s text segment and loaded libraries, so by removing certain functions from libc it might be possible to restrict his capabilities.1

Were the perception of return-into-libc attacks described above correct, deploying W⊕X would in fact weaken attackers. Unfortunately, we show in this paper that this perception is entirely untrue: we describe new return-into-libc techniques that allow arbitrary computation (and that are not, therefore, straight-line limited) and that do not require calling any functions whatsoever, so removing functions from libc is no help.

译文：

有⼈可能会问，为什么在⾯临 return-into-libc 攻击的情况下，部署 W⊕X 被认为是值得的。答案是 return-into-libc 被认为是⼀ 种⽐代码注⼊更有限的攻击，原因有⼆：

1. 在返回 libc 攻击中，攻击者可以依次调⽤⼀个 libc 函数，但这仍然允许他执行直线代码，⽽不是通过代码注⼊来实现分⽀ 和其他任意行为；

2. 攻击者只能调⽤程序⽂本段和已加载库中可⽤的函数，因此通过从 libc 中删除某些函数，可能会限制他的能力。

如果上述对返回 libc 攻击的认识正确，部署 W⊕X 实际上会削弱攻击者。不幸的是，我们在本⽂中表明这种认识完全不正确： 我们描述了新的返回 libc 技术，这些技术允许任意计算（因此不受直线限制），并且不需要调⽤任何函数，因此从 libc 中删除函 数没有帮助。

1.2.1 The Building Blocks for Our Attack

The building blocks for the traditional return-into-libc attack are functions, and these can be removed by the maintainers of libc. By contrast, the building blocks for our attack are short code sequences, each just two or three instructions long. Some are present in libc as a result of the code-generation choices of the compiler. Others are found in libc despite not having been placed there at all by the compiler. In either case, these code sequences would be very difficult to eliminate without extensive modifications to the compiler and assembler.

To understand how there exist code sequences in libc that were not placed there by the compiler, consider an analogy to English. English words vary in length, and there is no particular position on the page where a word must end and another start. Intel x86 code is like English written without punctuation or spaces, so that the words all run together.2 The processor knows where to start reading and, continuing forward, is able to recover the individual words and make out the sentence, as it were. At the same time, one can make out more words on the page than were intentionally placed there. Some words will be suffixes of other words, as “dress” is a suffix of “address”; others will consist of the end of one word and the beginning of the next, as “head” can be found in “the address”; and so on. Here is a concrete example for the x86, taken from our testbed libc (see Section 1.2.6). Two instructions in the entrypoint ecb_crypt are encoded as follows:

f7 c7 07 00 00 00 test $0x00000007, %edi

0f 95 45 c3 setnzb -61(%ebp)

译文：

传统的返回 libc 攻击的构建块是函数，这些函数可以由 libc 的维护者删除。相⽐之下，我们的攻击的构建块是短代码序列，每个只 有两三条指令⻓。有些代码序列存在于 libc 中，这是编译器的代码⽣成选择的结果。其他代码序列存在于 libc 中，尽管编译器根本 没有将它们放在那里。⽆论哪种情况，如果不对编译器和汇编器进行⼤量修改，这些代码序列将很难消除。

要理解 libc 中存在未被编译器放置的代码序列的原因，可以将其类⽐为英语。英语单词的⻓度各不相同，⻚⾯上没有⼀个单词 必须结束和另⼀个单词必须开始的特定位置。Intel x86 代码就像没有标点符号或空格的英语，因此所有单词都连在⼀起。处理器 知道从哪里开始读取，并继续向前读取，能够恢复单个单词并形成句⼦。同时，⼈们可以在⻚⾯上识别出⽐有意放置的单词更多的单 词。⼀些单词将是其他单词的后缀，例如“dress”是“address”的后缀；其他单词将由⼀个单词的结尾和下⼀个单词的开头组成， 例如“head”可以在“the address”中找到；等等。以下是 x86 的具体⽰例，取⾃我们的测试平台 libc（参⻅第 1.2.6 节）。⼊⼝ 点 ecb_crypt 中的两个指令编码如下：

---

One candidate for removal from libc is system, a function often used in return-into-libc attacks but not much used in Unix daemons, since it is difficult to apply securely to user input [33, Section 8.3].

... if English were a prefix-free code, to be pedantic.

Starting one byte later, the attacker instead obtains

译文：

可以从 libc 中删除的⼀个候选函数是 system，该函数经常⽤于返回 libc 攻击，但并不常⽤ ⽤于 Unix 守护进程，因为很难安全地应⽤于⽤⼾输⼊ 。...如果英语是⼀种⽆前缀的代码，那就太迂腐了。

攻击者从下⼀个字节开始获取

c7 07 00 00 00 0f movl $0x0f000000, (%edi)

95 xchg %ebp, %eax

45 inc %ebp

c3 ret

How frequently such things occur depends on the characteristics of the language in question, what we call its geometry. And the x86 ISA is extremely dense, meaning that a random byte stream can be interpreted as a series of valid instructions with high probability [3]. Thus for x86 code it is quite easy to find not just unintended words but entire unintended sequences of words. For a sequence to be potentially useful in our attacks, it need only end in a return instruction, represented by the byte c3.3 In analyzing a large body of code such as libc we therefore expect to find many such sequences, a claim that we codify as this paper’s thesis:

Our thesis: In any sufficiently large body of x86 executable code there will exist sufficiently many useful code sequences that an attacker who controls the stack will be able, by means of the return-into-libc techniques we introduce, to cause the exploited program to undertake arbitrary computation.

By contrast, on an architecture such as MIPS where all instructions are 32 bits long and 32-bit aligned there is no ambiguity about where instructions start or stop, and no unintended instructions of the sort we describe. One way to weaken our attack is to bring the same features to the x86 architecture. McCamant and Morrisett, as part of their x86 Software Fault Isolation (SFI) design [19], propose an instruction alignment scheme that does this. However, their scheme has some downsides: first, code compiled for their scheme cannot call libraries not so compiled, so the switch must be all-or-nothing; second, the nop padding allows less code to fit in the instruction cache and the “andl $0xfffffff0, (%esp); ret” idiom imposes a data dependency that may introduce slowdowns that might be unacceptable in general-purpose software as opposed to the traditional, more limited SFI usage scenarios.4 We stress, however, that while countermeasures of this sort would impede our attack, they would not necessarily prevent it. We have taken some steps, described in Section 2, to avoid including sequences in our trie that were intentionally placed there by the compiler, but an attacker is under no such obligation, and there may well be enough sequences that are suffixes of functions in libc to mount our attack.

In relying intimately on the details of the x86 instruction set, our paper is inspired by two others: rix’s Phrack article showing how to construct alphanumeric x86 shellcode [24] and Sovarel, Evans, and Paul’s “Where’s the FEEB?,” which showed how to defeat certain kinds of instruction set randomization on the x86 [30].

译文：

此类事件发⽣的频率取决于所讨论语⾔的特性，也就是我们所说的⼏何结构。x86 ISA ⾮常密集，这意味着随机字节流可以以很⾼的概率被 解释为⼀系列有效指令 。因此，对于 x86 代码，很容易找到不仅是⾮预期单词，⽽且是整个⾮预期单词序列。对于可能对我们的攻击有⽤ 的序列，它只需要以返回指令结尾，由字节表⽰。

3 因此，在分析 libc 等⼤量代码时，我们期望找到许多这样的序列，我们将其编纂为本⽂的论点：

我们的论点：在任何足够⼤的 x86 可执行代码体中，都会存在足够多的有⽤代码序列，控制堆栈的攻击者将能够通过我们引⼊的返 回 libc 技术，使被利⽤的程序进行任意计算。

相⽐之下，在 MIPS 等所有指令都是 32 位⻓且 32 位对⻬的架构上，指令的起始和终⽌位置没有任何歧义，也没有我们描述的那种⾮预期指令。削弱我们攻击的 ⼀种⽅法是将相同的功能引⼊ x86 架构。作为其 x86 软件故障隔离 (SFI) 设计 的⼀部分，McCamant 和 Morrisett 提出了⼀种实现这⼀点的指令对⻬⽅ 案。但是，他们的⽅案有⼀些缺点：⾸先，为他们的⽅案编译的代码⽆法调⽤未如此编译的库，因此切换必须是全有或全⽆；其次，nop 填充允许更少的代码放⼊指 令缓存中，⽽“andl $0xfffffff0, (%esp); ret”习语会强加数据依赖性，这可能会导致速度减慢，这在通⽤软件中可能是不可接受的，⽽不是传统的、更有限的 SFI 使⽤场景。然⽽，我们要强调，虽然这种对策会阻碍我们的攻击，但它们不⼀定能阻⽌它。我们已采取第 2 节中描述的⼀些步骤来避免在我们的 trie 中包含编译器 故意放置在那里的序列，但攻击者没有这样的义务，并且可能有足够多的序列是 libc 中函数的后缀，足以让我们发起攻击。

在密切依赖 x86 指令集细节的过程中，我们的论⽂受到了另外两篇⽂章的启发：rix 的 Phrack ⽂章展⽰了如何构造字⺟数字 x86 shellcode，以及 Sovarel、Evans 和 Paul 的“FEEB 在哪里？”，其中展⽰了如何在 x86 上击败某些类型的指令集随机化。

1.2.2 How We Find Sequences

In Section 2, we describe an efficient algorithm for static analysis of x86 executables and libraries. In the version of libc we examined, our tool found thousands of sequences, from which we chose a small subset by means of which to mount our attack. Static analysis has recently found much use as an attack tool. For example, Kruegel et al. [16] use sophisticated symbolic execution to find ways

3 Sequences ending with some other instructions can also be useful; see Section 5.1.

4 Things would be better if Intel added 16-byte–aligned versions of ret, call, jmp, and jcc to the x86 instruction set.

by which an attacker can regain control after supposedly restoring a program to its pristine state, with the goal of defeating host-based intrusion detection system. In their setting, unlike ours, the attacker can execute arbitrary injected code. Their static analysis techniques, however, might be applicable to our case as well.

译文：

在第 2 节中，我们描述了⼀种⽤于静态分析 x86 可执行⽂件和库的有效算法。

在我们检查的 libc 版本中，我们的⼯具发现了数千个序列，我们从中选择了⼀⼩部分来发起攻击。静态分析最近被发现是⼀种很有⽤的攻 击⼯具。例如，Kruegel 等⼈使⽤复杂的符号执行来寻找⽅法以其他指令结尾的序列也可能有⽤；参⻅第 5.1 节。如果英特尔在 x86 指令集中添加 16 字节对⻬的 ret、call、jmp 和 jcc 版本，情况会更好。

攻击者可以在将程序恢复到原始状态后重新获得控制权，⽬的是击败基于主机的⼊侵检测系统。在他们的设置中，与我们的情况不同，攻击者可以执行 任意注⼊的代码。然⽽，他们的静态分析技术可能也适⽤于我们的情况。

1.2.3 How We Use Sequences in Crafting an Attack

The way we interact with libc in return-oriented programming differs from the way we interact with libc in traditional return-into-libc attacks in three ways that make crafting gadgets a delicate, difficult task.

1. The code sequences we call are very short — often two or three instructions — and, when executed by the processor, perform only a small amount of work. In traditional return-into- libc attacks, the building blocks are entire functions, which each perform substantial tasks. Accordingly, our attacks are crafted at a lower level of abstraction, like assembler instead of a high-level language.

2. The code sequences we call generally have neither function prologue nor function epilogue, and aren’t chained together during the attack in the standard ways described in the literature, e.g., by Nergal [21].

3. Moreover, the code sequences we call, considered as building blocks, have haphazard inter- faces; by contrast, the function-call interface is standardized as part of the ABI.

(Recall that there is, of course, a fourth difference between our code sequences and libc functions that is what makes our attack attractive: the code sequences we call weren’t intentionally placed in libc by the authors, and are not easily removed.) In Section 3, we show, despite the difficulties, how to construct gadgets — short blocks placed on the stack that chain several of instruction sequences together — that perform all the tasks one needs to perform. We describe gadgets that perform load/store, arithmetic and logic, control flow, and system call operations.

We stress that while we choose to use certain code sequences in the gadgets in Section 3, we could have used other sequences, perhaps less conveniently; and while our specific code sequences might not be found in a libc on another platform, other code sequences will be, and gadgets similar to ours could be constructed with those — at least if our thesis holds.

译文：

在⾯向返回编程中我们与 libc 交互的⽅式与我们在传统的返回 libc 攻击中与 libc 交互的⽅式有三种不同，这使得制作⼩⼯具成为⼀项微妙⽽困难的 任务。

1. 我们调⽤的代码序列⾮常短 通常只有两三条指令 处理器执行时只执行少量⼯作。在传统的 return-into-libc 攻击中，构建块是整个函数， 每个函数都执行⼤量任务。

因此，我们的攻击是在较低的抽象层次上设计的，例如汇编程序⽽不是⾼级语⾔。

2. 我们调⽤的代码序列通常既没有函数序⾔，也没有函数尾声，并且在攻击过程中不会按照⽂献中描述的标准⽅式链接在⼀起，例如 Nergal 。

3. 此外，我们调⽤的代码序列被视为构建块，具有随意的接⼝；相⽐之下，函数调⽤接⼝作为 ABI 的⼀部分是标准化的。

（回想⼀下，我们的代码序列和 libc 函数之间当然还有第四个不同点，这也是我们的攻击具有吸引力的原因：我们调⽤的代码序列不是作者故意放在 libc 中的，⽽且不容易被删除。）在第 3 节中，我们展⽰了如何构建⼩⼯具（放置在堆栈上的短块，将多个指令序列链接在⼀起）来执行需要执行的所有 任务，尽管存在困难。我们描述了执行加载/存储、算术和逻辑、控制流和系统调⽤操作的⼩⼯具。

我们强调，虽然我们选择在第 3 节的⼩⼯具中使⽤某些代码序列，但我们也可以使⽤其他序列，也许不那么⽅便；虽然我们的特定代码序列可能⽆ 法在另⼀个平台的 libc 中找到，但其他代码序列可以找到，并且可以⽤这些代码序列构建与我们类似的⼩⼯具 - ⾄少如果我们的论点成⽴的话。

1.2.4 Previous Uses of Short Sequences in Attacks

Some previous return-into-libc attacks have used short code snippets from libc. Notably, code segments of the form pop %reg; ret to set registers have been used to set function arguments on architectures where these are passed in registers, such as SPARC [20] and x86-64 [15]. Other examples are Nergal’s “pop-ret” sequences [21] and the “register spring” technique introduced by dark spyrit [6] and discussed by Crandall, Wu, and Chong [5]. Our attack differs in doing away altogether with calling functions in libc. The previous attacks used short sequences as glue in combining the invocations of functions in libc or in jump-starting the execution of attacker-injected code. Our technique shows that short code sequences, combined in appropriate ways, can express any computation an attacker might want to carry out, without the use of any functions.

Of the previous uses discussed here, Krahmer’s borrowed code chunks exploitation technique [15] is the closest to ours. Krahmer uses static analysis to look for register-pop sequences. He describes a shellcode-building tool that combines these sequences to allow arbitrary arguments to be passed to libc functions. However, exploits constructed using Krahmer’s techniques are still straight-line limited and still rely on specific functions in libc — like other traditional return-into-libc attacks, and unlike the new attack we propose.

译文：

之前的⼀些返回 libc 攻击使⽤了 libc 中的短代码⽚段。值得注意的是，在 SPARC 和 x86-64 等通过寄存器传递函数参数的体系结构中，⼈ 们曾使⽤ pop %reg; ret 形式的代码段来设置寄存器。其他⽰例包括 Nergal 的“pop-ret”序列 和 dark spyrit 引⼊的“register spring” 技术，Crandall、Wu 和 Chong 对此进行了讨论。我们的攻击不同之处在于完全取消了对 libc 中函数的调⽤。之前的攻击使⽤短序列作为粘合剂， 将 libc 中函数的调⽤组合在⼀起，或者启动攻击者注⼊的代码的执行。我们的技术表明，以适当⽅式组合的短代码序列可以表达攻击者可能想要执行的 任何计算，⽽⽆需使⽤任何函数。

在本⽂讨论的先前⽤途中，Krahmer 的借⽤代码块利⽤技术与我们最接近。Krahmer 使⽤静态分析来寻找寄存器弹出序列。他描述了⼀个 shellcode 构建⼯具，它结合了这些序列，允许将任意参数传递给 libc 函数。但是，使⽤ Krahmer 的技术构建的漏洞利⽤仍然受 到直线限制，并且仍然依赖于 libc 中的特定函数 就像其他传统的返回 libc 攻击⼀样，与我们提出的新攻击不同。

1.2.5 Wait, What about Zero Bytes?

The careful reader will observe that some of the gadgets we describe in Section 3 require that a nul byte be placed on the stack. This means that they cannot be used in the payload of a simple stack-smash buffer overflow. This is not a problem, however, for the following reasons:

1. We have not optimized our gadgets to avoid nul bytes. If they are a concern, it should be possible to eliminate the use of many of them, using the same techniques used in standard shellcode construction. For example, loading an immediate 0 into %eax could be replaced by a code sequence of the form xor %eax, %eax; ret, or by a load of 0xffffffff followed by an increment. If the address of a code sequence includes a nul byte, we could have Galileo choose another instance of that sequence whose address does not include a nul byte, or we can substitute a different sequence.

2. There are other ways by which an attacker can overwrite the stack than standard buffer overflows, and not all suffer from the same constraints. For example, there is no problem writing nul bytes onto the stack in a format-string exploit.

3. We view our techniques not in isolation but as adding to the toolbox available for return- into-libc attacks. This toolbox already contains techniques for patching up nul bytes — as described, for example, by Nergal [21, Section 3.4] — that are just as applicable to exploits structured in the ways we describe.

A similar argument applies to the interaction between our techniques and address space layout randomization (ASLR). Those gadgets that do not require knowledge of addresses on the stack can be used directly in the Shacham et al. [26] derandomization framework. Some of those gadgets that do require knowledge of addresses on the stack could likely be rewritten not to require it.

译文：

细⼼的读者会发现，我们在第 3 节中描述的⼀些⼩⼯具要求将空字节放在堆栈上。这意味着它们不能⽤于简单的堆栈破坏缓冲区溢出 的有效载荷。然⽽，这不是问题，原因如下：

1. 我们没有优化我们的⼩⼯具来避免使⽤空字节。如果它们令⼈担忧，应该可以使⽤标准 shellcode 构造中使⽤的相同技术来消 除其中许多的使⽤。例如，将⽴即数 0 加载到 %eax 中可以⽤ xor %eax, %eax; ret 形式的代码序列替换，或者⽤加载 0xffffffff 后跟增量替换。如果代码序列的地址包含空字节，我们可以让 Galileo 选择该序列的另⼀个实例，其地址不包含空字 节，或者我们可以替换不同的序列。

2. 除了标准缓冲区溢出之外，攻击者还可以通过其他⽅式覆盖堆栈，⽽且并⾮所有⽅式都受到相同的限制。例如，在格式字符串漏洞 中将空字节写⼊堆栈没有任何问题。

3. 我们认为我们的技术并⾮孤⽴存在，⽽是为可⽤于 return-into-libc 攻击的⼯具箱添加了内容。此⼯具箱已包含修补空字节的 技术（例如，Nergal [第 3.4 节] 中所述的技术），这些技术同样适⽤于以我们所述⽅式构建的漏洞利⽤。

类似的观点也适⽤于我们的技术与地址空间布局随机化 (ASLR) 之间的交互。那些不需要了解堆栈地址的⼩⼯具可以直接在 Shacham 等⼈ 的去随机化框架中使⽤。其中⼀些需要了解堆栈地址的⼩⼯具可能会被重写为不需要它。

1.2.6 Our Libc Testbed

We carry out our experiments on the gnu C Library distributed with Fedora Core Release 4: libc-2.3.5.so. Our testing environment was a 2.4 GHz Pentium 4 running Fedora Core Release 4, with Linux kernel version 2.6.14 and gnu libc 2.3.5, as noted.

译文：

我们在 Fedora Core Release 4 中发布的 gnu C 库 libc-2.3.5.so 上进行了实验。我们的测试环境是运行 Fedora Core Release 4 的 2.4 GHz Pentium 4，Linux 内核版本为 2.6.14，gnu libc 为 2.3.5（如前所述）。

2 Discovering Useful Instruction Sequences in Libc

In this section, we describe our algorithm for discovering useful code sequences in libc. We sifted through the sequences output by this algorithm when run on our testbed libc to select those sequences employed in the gadgets described in Section 3.

Before we describe the algorithm, we must first make more precise our definition of “useful code sequence.” We say that a sequence of instructions is useful if it could be used in one of our gadgets, that is, if it is a sequence of valid instructions ending in a ret instruction and such that

Algorithm Galileo:

create a node, root, representing the ret instruction;

place root in the trie;

译文：

在本节中，我们将介绍⽤于发现 libc 中有⽤代码序列的算法。我们筛选了该算法在测试平台 libc 上运行时输出的序列，以选择第 3 节 中描述的⼩⼯具中使⽤的序列。

在描述算法之前，我们必须⾸先更精确地定义“有⽤的代码序列”。如果⼀个指令序列可以在我们的某个⼩⼯具中使⽤，我们就 说它是有⽤的，也就是说，如果它是⼀个以 ret 指令结尾的有效指令序列，并且伽利略算法：创建⼀个节点 root，代表 ret 指令；将 root 放⼊ trie 中

for pos from 1 to textseg len do:

if the byte at pos is c3, i.e., a ret instruction, then:

call BuildFrom(pos, root).

Procedure BuildFrom(index pos, instruction parent insn):

for step from 1 to max insn len do:

if bytes (pos − step) . . . (pos − 1) decode as a valid instruction insn then: ensure insn is in the trie as a child of parent insn;

if insn isn’t boring then:

call BuildFrom(pos − step, insn).

Figure 1: The Galileo Algorithm.

that none of the instructions causes the processor to transfer execution away, not reaching the ret. (It is the ret that causes the processor to continue to the next step in our attack.) We say that a useful sequence is intended if the instructions were actually inserted by the compiler in giving the machine-code compiled equivalent for some function in libc. In accordance with our thesis, the algorithm we describe attempts to avoid intended code sequences, though it does not shy away from using intended rets at the end of sequences.

Two observations guide us in the choice of a data structure in which to record our findings. First, any suffix of an instruction sequence is also a useful instruction sequence. If, for example, we discover the sequence “a; b; c; ret” in libc, then the sequence “b; c; ret” must of course also exist. Second, it does not matter to us how often some sequence occurs, only that it does.5 Based on these observations, we choose to record sequences in a trie. At the root of the trie is a node representing the ret instruction; the “child-of” relation in the trie means that the child instruction immediately precedes the parent instruction at least once in libc. For example, if, in the trie, a node representing pop %eax is a child of the root node (representing ret) we can deduce that we have discovered, somewhere in libc, the sequence pop %eax; ret.

Our algorithm for populating the trie makes use of following fact: It is far simpler to scan backwards from an already found sequence than to disassemble forwards from every possible location in the hope of finding a sequence of instructions ending in a ret. When scanning backwards, the sequence-so-far forms the suffix for all the sequences we discover. The sequences will then all start at instances of the ret instruction, which we can scan libc sequentially to find.

In looking backwards from some location, we must ask: Does the single byte immediately preceding our sequence represent a valid one-byte instruction? Do the two bytes immediately preceding our sequence represent a valid two-byte instruction? And so on, up to the maximum length of a valid x86 instruction.6 Any such question answered “yes” gives a new useful sequence of which our sequence-so-far is a suffix, and which we should explore recursively by means of the same approach. Because of the density of the x86 ISA, more than one of these questions can

5 From all the occurrences of a sequence, we might prefer to use one whose address does not include a nul byte over one that does.

6 Including all instruction-modifying prefixes, 20 bytes.

simultaneously have a “yes” answer.7

Figure 1 presents, in pseudocode, our algorithm for finding useful sequences.

译文：

没有任何指令会导致处理器转移执行，没有达到 ret。

（在我们的攻击中，ret 使处理器继续执行下⼀步。）如果指令实际上是由编译器插⼊的，以便为 libc 中的某些函数提供机器代码编 译等效项，那么我们就说有⽤的序列是预期的。根据我们的论⽂，我们描述的算法试图避免预期的代码序列，但它并不回避在序列末尾 使⽤预期的 ret。

两个观察结果指导我们选择⼀种数据结构来记录我们的发现。

⾸先，任何指令序列的后缀也是有⽤的指令序列。例如，如果我们在 libc 中发现序列“a; b; c; ret”，那么序列“b; c; ret”当然也⼀ 定存在。其次，某个序列出现的频率对我们来说并不重要，重要的是它确实出现了。5基于这些观察，我们选择在 trie 中记录序列。trie 的根节点代表 ret 指令；trie 中的“⼦”关系意味着⼦指令在 libc 中⾄少有⼀次紧接着⽗指令。例如，如果在 trie 中，代表 pop %eax 的节点是根节点（代表 ret）的⼦节点，我们可以推断我们在 libc 的某个地⽅发现了序列 pop %eax; ret。

我们填充 trie 的算法利⽤了以下事实：从已找到的序列向后扫描⽐从每个可能的位置向前反汇编以期找到以 ret 结尾的指令序 列要简单得多。向后扫描时，迄今为⽌的序列构成了我们发现的所有序列的后缀。然后，这些序列都将从 ret 指令的实例开始，我们可 以按顺序扫描 libc 来找到这些实例。

从某个位置向后看时，我们必须问：我们序列前⾯的单个字节是否代表有效的单字节指令？我们序列前⾯的两个字节是否代表有 效的双字节指令？等等，直到有效 x86 指令的最⼤⻓度。6任何回答“是”的问题都会产⽣⼀个新的有⽤序列，我们⽬前的序列是其后 缀，我们应该⽤同样的⽅法递归地探索它。由于 x86 ISA 的密度，可以提出不⽌⼀个这样的问题

5从序列的所有出现情况中，我们可能倾向于使⽤地址不包含空字节的序列 ⽽不是⼀个。

6 包括所有指令修改前缀，20字节。

同时得到“是”的回答。7

图 1 以伪代码的形式展⽰了我们寻找有⽤序列的算法。