CSAPP 3. 程序的机器级表示

yyi
yyi
2023-08-04 / 0 评论 / 164 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2023年08月08日,已超过310天没有更新,若内容或图片失效,请留言反馈。

程序的机器级表示

长期的逆向工作,这一章可以说是我最熟悉的知识了。本章以复习记录为主,如有缺漏还请见谅。

机器级表示 :计算机使用字节序列编码操作,程序最终生成机器码。

Benefits:

  • 理解编译器优化能力,分析关键代码效率
  • 了解高级语言隐藏的行为,如并发。

本章讨论的都是x86_64下的机器码。

2 程序编码

机器码中可见的部分寄存器状态

  • 程序计数器PC:RIP寄存器
  • 整数寄存器:如RAX、RSI等
  • 条件码寄存器:如CF、OF等
  • 向量寄存器:XMM、YMM等

机器不区分数据类型,包括整数与指针、有符号与无符号。编译器通过源代码、条件码寄存器等确定数据的行为

汇编文件通过汇编器生成目标文件,目标文件中即为机器所用的字节序列。

gdb中,使用 x/nt addr/sym 展示从addr开始的n个t类型长度的字节内容,如x/16b main展示从main开始的16个byte

objdump -d对文件进行反汇编,它只基于二进制文件获取信息。业界常用强大的IDA来做这项工作。

3 数据格式

对于各类整数数据类型不做区别。指令集中可以操作1、2、4、8字节的数据,即使是相同的操作,根据数据长度的不同,其汇编指令也不同,在机器码上以不同的编码体现,在汇编中用不同的后缀体现。在64位系统中,指针也长8字节

大小后缀(整形)
1b(yte)
2w(ord)
4l(ong word)、double words
8q(uad words)

4 访问信息

通用寄存器共有十六个,包括rax-rdx,rs/di,rs/bp,r8-r15

它们都有自己对应的低32、16、8位寄存器名,

对于rax-rdx,分别为eax、ax、al(ah),(以此类推,下同)

对于rsi-rbp,分别为esi、si、sil,

对于r8-r15,分别为r8d、r8w、r8b

在不同的时候,不同的寄存器可能会因为某些约定出现不一样的行为,比如在fastcall约定中,用si等寄存器传参数、使用sp、bp管理栈空间等。

4.1 操作数指示符

附上表即可,其中 M[addr]表示对存储器addr位置的引用,具体长度可以依据指令确定。R[r]代表对r寄存器的引用。

image.jpg

4.2 数据传送指令

MOV的核心只是数据传送,主要区别是源和目的的类型和大小,此外,当大小不同时,还涉及到如何扩展

源和目的类型允许如下操作,其实就是不允许Mem互传和Imm作为目的,后者是显然的。

SD
ImmReg
RegReg
MemReg
ImmMem
RegMem

零扩展用后缀z(ero)表示,符号扩展用后缀s(ign)表示,后接源和目的的大小,比如:

movswl:符号扩展,字传送到双字

此外,还有一个特殊的指令cltq,代表把eax符号扩展到rax,它和movslq eax rax是一样的,不过机器码更短。

4.4 栈操作指令

通过push/pop这组指令完成,push的过程可以看为:

  1. rsp -= 8
  2. M[rsp] = S

而pop可以看为:

  1. D = M[rsp]
  2. rsp += 8

显然,这样的操作也可以由add/sub和mov完成,但是pop和push的编码更短

此外,先修改栈顶再压栈似乎有些奇怪,但是其实想一下栈是倒着增长的就能很容易理解

5 算数和逻辑操作

这部分没什么好说的,贴表格

image 1.jpg

5.1 LEA指令

lea是mov的变形,把操作数的内存地址写到目的操作数中,就像&S。

在编译器中,它经常被用来优化简单的乘法加法操作,如leaq 7(rdx, rdx, 4), rax 等同于 rax = 5*rdx + 7 。

5.3 位移操作

位移操作无非就是左/右移、逻辑/算数移,对于左来讲,算数和逻辑一样,右移的算数SAR会在最左侧填符号位,而SHR会填0 。

此外,位移量可以是立即数或者cl寄存器

5.5 特殊算数

对于乘除法,两个八字节的乘法需要16字节来表示,Intel称为o(ct)word。

然而乘除法也无非是有符号、无符号两类罢了,加上一个把rdx和rdx拼在一起做操作数的小魔术。

6 控制

控制类语句帮助我们实现条件、循环与分支

6.1 条件码

CPU维护一组Flag寄存器,最常用的包括:

CF:Carry Flag 进位

ZF:Zero Flag 零

SF:Sign Flag 符号

OF:Overflow 溢出

算数和逻辑运算的结果会影响上述Flag的值,而LEA指令不会。

此外,还要引入CMP和TEST指令,CMP和SUB行为一致,TEST和AND行为一致,但是它们都不会改变目的寄存器的值。

在这要多提一嘴,CPU如何判断大于、小于的呢?我们刚刚只说了条件码,没说它们和大小的关系。这是一个分类讨论问题。用以下几个例子解释一下。

相等:ZF == 0

小于(无符号):CF ,其实就是两数相减不等于零、且产生了进位,也就是A+B的补码进位了,

小于(有符号):SF^OF,分类讨论:A-B为负数,那么在没溢出的情况下,A小于B。其他几个情况无非就是正负与是否有溢出,当只满足一个的情况下是小于。

所有常见后缀包括:

e/z:相等/零,以及前面加n的否定

s:负数,以及前面加n的否定(下同)

以下四个是有符号范畴内的大小比较

g/nle :大于

ge/nl:大于等于

l/nge:小于

le/ng:小于等于

以下四个是无符号范围内的大小比较

a/nbe:超过

ae/nb:超过或相等

b/nae:低于

be/na:低于或相等

6.2 访问条件码

我们有一组指令来访问条件码,然而在86的程序里我很少见到这类指令,反而是RISC系列的处理器用的多一点。主要就是set(cond) rd,比如sete/setz rax就是根据ZF的结果设置rax,其中e和z分别代表equal和zero,它们是等价的。其他的等价还包括g和le、ae和nb等(above&equal/not below)

6.3 跳转指令

跳转指令的构成和6.2说的set(cond)差不多,不过变成了j(cond)+ Label(*Operand),此外还加入了修改RIP寄存器的作用。并且有一组无条件转指令jmp

条件转举一例:jg(jnle)*rax :如果大于则跳转到rax中的值那个地址。

6.5 条件控制实现分支

一个典型的if-else结构,组成为

if (expr) {
    then ...
} else {
    else ...
}

我们可以翻译为

t = expr;
if(!t) goto false;

then...

goto done
false :
    else ...
done:

这是一类通用的翻译方式。

当然,我们可以第一步条件跳转到else,也就可以第一步条件转到then,翻译为如下

t = expr;
if(t) goto true;

else ...
goto done

true:
    then...

done:

显然它们是等价的,但是我们一般选择第一种,因为在没有else的情况下,第一种更能节省代码。

6.6 用条件传送实现分支

现代处理器流水线依赖于分支预测,如果用上面这种方法,当分支预测失败的时候就会影响处理器性能,因此在特定情况下我们可以使用条件传送cmov系列指令。

比如这种:

int res;
if(x < y) res = y-x;
else res = x-y;

显然,我们的流水线可以同时计算两个表达式的值,然后根据条件决定把哪个结果送入res里。CPU提供的条件传送(满足条件时mov)指令可以把原来的分支消除掉,不会出现分支预测失败的情况。

至于什么是分支预测和为什么分支预测影响这么大,本书下一章应该会讲到(写到这里时我还不确定,如果没有请各位读者不要打我)。

cmov指令的格式是cmov[diff] S, R,如cmovge rdx, rax是当ge为真时rax = rdx。

公式:预测错误概率为p,没错误执行的时间时Tok,预测错误处罚是Tmp,则

执行代码的平均时间:

$$ T_{avg}(p)=(1-p)T_{ok}+p(T_{ok}+T_{mp}) = T_{ok} + pT_{mp} $$

一类非法情况

int *xp;

a = xp ? *xp : 0;

如果顺序的把三目运算符的两个结果都算完,再cmov,这时如果xp是0,就出现了一次对0的解引用,这显然是错误的。

此外,如果then或者else的计算量很大,可能会导致浪费,所以并不是所有情况都适用这种优化。

6.7 循环

汇编中没有支持C语言多种循环结构的语句(其实8086里应该是有的,loop指令应该能支持do-while结构,不太清楚本书为什么没有提这个指令。),使用条件跳转实现

  1. do-while循环

    do {
     statements...
    } while(expr)

    等价于

    loop:
        statements...
    t = expr;
    if(t)
        goto loop;

    下面这种表达方式就很容易直接翻译成汇编了。

  2. while循环

    while(expr) 
        statements...

    改写:jump to the middle

    goto test;
    loop:
        statements...;
    test:
        t = expr;
    if(t)
        goto loop;

    其实就是在循环之前先跳到test一次。

    但是较高优化等级可能会采用另一种方式:guarded-do

    t = expr;
    if (!t) goto done;
    loop:
        statements...;
    t = expr;
    if(t) goto loop;
    done:
    ...

    编译器可能在这种方式下采取更多的优化,比如认为第一次进入测试的代码永远满足。

  3. for循环

    for(init; test; update) 
        statements...

    其实学C语言的时候应该都有讲过,可以直接拆成while

    init;
    while(test) {
        statements...;
        update;
    }

    但是需要注意,在有continue语句的for循环中,不能直接简单的按上述方式转换为while翻译,否则就会出现少执行update的情况。

    for(init; test; update) {
        if(if_test) continue;
            print(haha);
    }

    上述应该改写成这样:

    init;
    while(test) {
        if(if_test) goto update_;
        print(haha);
    update_ :
        update;
    }

6.8 switch语句

刚学C语言的时候,很多人会把switch当成if-else结构的语法糖使用,但是其实switch结构在特定情况下对性能有很大优化

  • 跳转表:一个数组,表项i是当switch的开关索引是i的时候要跳转到的地址。

当case们的条件是一个可作为索引的(char就是8b整数,我相信你是知道的)、且范围不超过255的值组的时候,编译器就会先把最小值归0,然后再生成跳转表。我觉得这里没有什么方式比放书上的例子更能方便理解的了。

这样的优化是显然的,当情况很多时,jump-table只需要一次跳转,而if-else需要多次判断+跳转

image 2.jpg

7 过程

过程是对代码的封装、对功能的抽象,用一组指定的参数和一个可选的返回值(事实上,在现代语言中往往已经支持一组返回值了)实现某种功能。

function、method、subroutine和handler都是过程的形式。

过程往往需要实现如下几个机制:

  • 传递控制:进入过程时,PC应该被设置为Callee的起始地址,退出过程时,应该被设置为Caller调用Callee的下一条地址。
  • 传递数据:Caller向Callee提供参数,Callee提供返回值给Caller
  • 管理内存:进入Callee可能需要为Callee的局部变量分配空间,退出需要释放

7.1 Runtime Stack

大多数语言都用FILO的Stack来管理过程调用。对于一次调用,会为它分配一段独特的空间称为栈帧。x86-64为这种非常常见的操作提供了一组指令。

一次函数调用的栈帧可能包含 局部变量、它所调用的过程将返回到的地址、它为调用的过程传递的参数和它为调用它的过程保存的寄存器等。

以下以函数调用P→Q为例

7.2 控制

调用 call:

  1. 把PC(rip)设为Q的起始位置
  2. 把call Q后面那条指令的地址压栈

其过程就相当于一组push+jmp

  • 跳转call可以是直接或者间接的,用call LABEL或者 call *Op都可以

返回 ret:

  1. 从栈中弹出返回地址
  2. 跳转到返回地址

7.3 数据

  1. 当参数个数小于等于6(整形)时,按顺序用rdi、rsi、rdx、rcx、r8、r9传递
  2. 当大于6时,多出来的参数需要放在P的栈帧上,因此P的栈帧最顶部(最低地址)的部分,也需要给它调用的参数最多的那个函数的调用(听起来有点拗口,就是所需空间取max)准备好传参的空间。其中排位最后的参数位于栈顶,所有数据向8对齐

7.4 局部变量

  • 寄存器不够存放所有的local数据(书上用的是本地,但是我觉得中文的本地并不能很好的描述这个意思,大概就是本次“运行时调用”需要的数据)
  • 对局部变量取地址
  • 局部变量是数组或结构体,需要通过引用被访问。

这些情况时,局部变量需要分配在内存中,作为当前函数栈帧的一部分

7.5 寄存器中的局部空间

  • callee-saved registers:rbx rbp,r12-r15
  • caller-saved registers:除了以上寄存器及rsp

顾名思义,不同的寄存器由不同的角色保护,当被调用者需要使用那些寄存器时,它需要先保存那些寄存器到栈,在返回之前再恢复它们。

7.6 递归

在栈模式下,P→P和P→Q没有什么本质上的不同,每个运行时的函数的局部数据由栈帧维护、隔离

8 数组

数组:将标量数据聚集成更大数据类型的方式

8.1 基本原则

声明:当有声明 T a[N];时,在内存中分配一个L*N字节的连续区域,L=sizeof T

对于一次访问:a[i],a的地址放在rdx,i的数值存放在rcx,就可以用(rdx, rcx, k)索引到该位置的值,其中k是伸缩因子,可以为1、2、4、8,足够覆盖所有基本简单数据类型

8.2 指针运算

若:指针p的类型为T,值为xp,则p+i的值为xp+L*i

8.3 嵌套数组

对于二维数组 a5,可以看成a是一个长度为5的数组,其中每个元素是一个长度为3的数组。

在引用时,先计算第一维的地址,再加上第二维的偏移

  • 对于 T DR, &Di = val_D + L(C*i+j)

8.4 定长数组

对于定长数组,GCC有一些优化,可以减少很多不必要的运算,举一例:

int A[16][16], B[16][16];
// original code
for(j = 0; j < 16; j ++ ) res += A[i][j] * b[j][k];

// after optimize
int *Ap = &A[i][0], *Bp = &B[0][k]; Bend = &B[16][k];
do {
    res += *Ap * *Bp;
    Ap ++;
    Bp += 16;
} while(Bp != Bend);

把未优化时的四次访存(A[i], Ai, B[j], Bj)变为了两次加法

8.5 变长数组

由于编译器不知道数组的大小,只能通过运行时的值确定偏移,该偏移必须要在运行时用一次乘法,其性能劣化很严重。但是这并不意味编译器无法进行优化。

9 异质数据结构

  • struct
  • union

9.1 结构

  • 对结构字段的访问:结构体基地址+字段偏移
  • 编译时处理字段与偏移信息,机器码中不包括结构具体信息

9.2 联合

联合体是允许用多种类型来引用相同的一段内存地址,一般只适用于一个内存地址在不同情况下互斥的情况的使用。

9.3 数据对齐

许多系统限制:某种类型对象的地址必须是某个值K的倍数。

x86_64虽然能在不对齐的前提下正常工作,但是建议:

任何K字节的基本对象地址必须是K的倍数。

举一例

struct s {
    int i; // offset : 0
    char j; // 4
    int k; // 8
}

如果不对齐,单纯排列,k的偏移似乎应该是5,但是5-7这三个字节被插入了一个间隙。

此外,即使把s的字段顺序改为i、k、j,也可能需要在j的后面填充三个字节。

10、11 指针、内存溢出与浮点操作

只给一些简略的概念罗列

指针信息包括:类型、值,使用&创建,*引用

指针可以指向函数


内存溢出主要是栈溢出和堆溢出,本书只讲了栈溢出

还记得返回地址写在栈上,当本层栈帧的某个变量可以任意控制长度和内容,我们就可以覆盖返回地址。进而进行攻击。

缓解方法

  • ASLR栈地址随机化
  • Canary
0

评论 (0)

取消