发表更新CS:APP11 分钟读完 (大约1696个字)0次访问

CS:APP bomblab 的逆向结果

https://csapp.cs.cmu.edu/3e/bomb.tar

输入命令 objdump -s -S -d -M att bomb > bomb.s 进行反汇编。

Phase 1

对 phase_1\verb|phase_1| 进行逆向： 

1
2
3
4
5
void phase_1(char str[]) {
  if (strings_not_equal(str, "Border relations with Canada have never been better.") != 0) {
    explode_bomb();
  }
}

explode_bomb\verb|explode_bomb| 函数将炸弹引爆；strings_not_equal\verb|strings_not_equal| 函数接受两个字符串作为参数，在两者不相等时返回 1\verb|1|，否则返回 0\verb|0|。

显然，输入应为 Border relations with Canada have never been better.。

Phase 2

逆向工程循环的一些技巧：

  • 框选出循环范围，将跳转指令的操作数由地址改成标号；
  • 大致理解代码执行顺序，可以用 gdb 辅助；
  • 尝试移动整段代码，并修改相应的跳转指令；
  • 最终使之符合任意一种通用策略。

例如，地址 400f0a\verb|400f0a| 至 400f3a\verb|400f3a| 的汇编代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
400f0a:	83 3c 24 01          	cmpl   $0x1,(%rsp)
400f0e:	74 20                	je     400f30 <phase_2+0x34>
400f10:	e8 25 05 00 00       	call   40143a <explode_bomb>
400f15:	eb 19                	jmp    400f30 <phase_2+0x34>
400f17:	8b 43 fc             	mov    -0x4(%rbx),%eax
400f1a:	01 c0                	add    %eax,%eax
400f1c:	39 03                	cmp    %eax,(%rbx)
400f1e:	74 05                	je     400f25 <phase_2+0x29>
400f20:	e8 15 05 00 00       	call   40143a <explode_bomb>
400f25:	48 83 c3 04          	add    $0x4,%rbx
400f29:	48 39 eb             	cmp    %rbp,%rbx
400f2c:	75 e9                	jne    400f17 <phase_2+0x1b>
400f2e:	eb 0c                	jmp    400f3c <phase_2+0x40>
400f30:	48 8d 5c 24 04       	lea    0x4(%rsp),%rbx
400f35:	48 8d 6c 24 18       	lea    0x18(%rsp),%rbp
400f3a:	eb db                	jmp    400f17 <phase_2+0x1b>
第一步，将地址改为标号： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  cmpl   $0x1,(%rsp)
  je     .L3
  call   explode_bomb
  jmp    .L3
.L1:
  mov    -0x4(%rbx),%eax
  add    %eax,%eax
  cmp    %eax,(%rbx)
  je     .L2
  call   explode_bomb
.L2:
  add    $0x4,%rbx
  cmp    %rbp,%rbx
  jne    .L1
  jmp    .end
.L3:
  lea    0x4(%rsp),%rbx
  lea    0x18(%rsp),%rbp
  jmp    .L1
.end:
第二步，理解代码执行顺序：

  1. 执行至第 2 行，若不跳转则炸弹引爆，若跳转则从 .L3\verb|.L3| 继续执行；
  2. 跳转至 .L1\verb|.L1|；
  3. 执行至第 9 行，若不跳转则炸弹引爆，若跳转则从 .L2\verb|.L2| 继续执行；
  4. 执行至第 14 行，若不跳转则回到步骤 2，若跳转则循环结束。

第三步，整理代码：

  • 第 4 行没有意义，删除；
  • 将 .L3\verb|.L3| 至 .end\verb|.end| 之间代码移动到 .L1\verb|.L1| 之前，删除多余的跳转（在结果中用括号呈现）。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
      cmpl   $0x1,(%rsp)
      je     .L3
      call   explode_bomb
    .L3:
      lea    0x4(%rsp),%rbx
      lea    0x18(%rsp),%rbp
      (jmp    .L1)
    .L1:
      mov    -0x4(%rbx),%eax
      add    %eax,%eax
      cmp    %eax,(%rbx)
      je     .L2
      call   explode_bomb
    .L2:
      add    $0x4,%rbx
      cmp    %rbp,%rbx
      jne    .L1
      (jmp    .end)
    (.end:)

最后，这段汇编已经相当容易理解，在此基础上逆向得到： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void phase_2(char str[]) {
  int x[6];
  read_six_numbers(x);

  if (x[0] != 1) {
    explode_bomb();
  } else {
    for (int i = 1; i < 6; i++) {
      if (x[i] != x[i - 1] * 2) {
        explode_bomb();
      }
    }
  }
}

read_six_numbers(int x[])\verb|read_six_numbers(int x[])| 读入 6 个整数，并依次存贮到 x[0]\verb|x[0]| 至 `x[5]\verb|x[5]|。

由此可知，输入应为 1 2 4 8 16 32。

Phase 3

这个 phase 包含一个跳转表，逆向为 switch\verb|switch| 语句： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void phase_3(char str[]) {
  int x, y;
  if (sscanf(str, "%d %d", &x, &y) <= 1) {
    explode_bomb();
  }
  
  if (x > 7 || x < 0) {
    explode_bomb();
  }
  int z;
  switch (x) {
    case 0:
      z = 0xcf;
      break;
    case 2:
      z = 0x2c3;
      break;
    case 3:
      z = 0x100;
      break;
    case 4:
      z = 0x185;
      break;
    case 5:
      z = 0xce;
      break;
    case 6:
      z = 0x2aa;
      break;
    case 7:
      z = 0x147;
      break;
    default:
      z = 0x137;
  }
  if (y != z) {
    explode_bomb();
  }
}
由此可知，输入的第 1 个数必须在 0 到 7 之间，第二个数与之相应即可。

Phase 4

地址 400fd6\verb|400fd6| 至 400fdd\verb|400fdd| 的汇编代码是原书 2.3.7 中提到的补码数除以 2 的幂的方法的一个实现。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int func4(int x, int y, int z) {
  int mid = y + (z - y) / 2;
  if (mid <= x) {
    if (mid >= x) {
      return 0;
    } else {
      return 2 * func4(x, mid + 1, z) + 1;
    }
  } else {
    return 2 * func4(x, y, mid - 1);
  }
}

void phase_4(char str[]) {
  int x, y;
  if (sscanf(str, "%d %d", &x, &y) != 2) {
    explode_bomb();
  }

  if (x > 15 || x < 0) {
    explode_bomb();
  }
  if (func4(x, 0, 15) != 0 || y != 0) {
    explode_bomb();
  }
}
结合线段树知识，输入的第 1 个数可以是 0、1、3 和 7，第二个数是 0。

Phase 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void phase_5(char str[]) {
  if (string_length(str) != 6) {
    explode_bomb();
  }

  char str2[7];
  for (int i = 0; i < 6; i++) {
    str2[i] = "maduiersnfotvbyl"[str[i] & 0xF];
  }
  str2[6] = 0;

  if (strings_not_equal(str2, "flyers") != 0) {
    explode_bomb();
  }
}

一个可行的输入是 9?>567。

Phase 6

对复杂变量数组的逆向技巧： - 通过观察汇编代码或数据确定一个数据类型的字长； - 判断该数据类型是结构（struct\verb|struct|）还是联合（union\verb|union|）； - 分别确定其各个组成部分是否为指针，若非指针，字长是多少。

例如，以地址 0x6032d0\verb|0x6032d0| 开头的一段内存，取出一段观察： 

1
2
3
4
6032d0 4c010000 01000000 e0326000 00000000  L........2`.....
6032e0 a8000000 02000000 f0326000 00000000  .........2`.....
6032f0 9c030000 03000000 00336000 00000000  .........3`.....
603300 b3020000 04000000 10336000 00000000  .........3`.....
不难猜到，该数据类型长度为 16 个字节，是一个结构，其中偏移量为 8 的位置存放了一个指针。结合汇编代码可以印证上述内容，同时还能确定偏移量为 0 的位置存放了一个整数。

对于全局变量，还需填入初始值。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct chain_node {
  int val;
  int id;
  struct chain_node *next;
} c[6] = {{0x014c, 1, &c[1]}, 
          {0x00a8, 2, &c[2]}, 
          {0x039c, 3, &c[3]}, 
          {0x02b3, 4, &c[4]}, 
          {0x01dd, 5, &c[5]},
          {0x01bb, 6}};

void phase_6(char str[]) {
  int x[6];
  read_six_numbers(x);
  
  for (int i = 0; ; i++) {
    if (x[i] <= 0 || x[i] > 6) {
      explode_bomb();
    }
    if (i == 5) {
      break;
    }
    for (int j = i + 1; j < 6; j++) {
      if (x[i] == x[j]) {
        explode_bomb();
      }
    }
  }

  for (int i = 0; i < 6; i++) {
    x[i] = 7 - x[i];
  }

  struct chain_node *y[6];
  for (int i = 0; i < 6; i++) {
    chain_node *p = c[0];
    for (int j = 1; j < x[i]; j++) {
      p = p->next;
    }
    y[i] = p;
  }

  for (int i = 1; i < 6; i++) {
    y[i - 1]->next = y[i];
  }
  y[5]->next = NULL;

  chain_node *p = y[0];
  for (int i = 5; i > 0; i--) {
    if (p->val < p->next->val) {
      explode_bomb();
    }
    p = p->next;
  }
}
结合链表知识，输入应为 4 3 2 1 6 5。

进入 Secret Phase

唯一对 secret_phase\verb|secret_phase| 的调用位于 phase_defused\verb|phase_defused| 中。观察 phase_defused\verb|phase_defused|，在 num_input_strings\verb|num_input_strings|（每次调用 read_line\verb|read_line| 都会使它加 1）等于 6，即完成 Phase 6 后的调用时，该函数从以地址 0x603870\verb|0x603870| 开头的字符串中先后提取了两个整数和一个字符串，并检查提取的字符串是否与 DrEvil 相等，若相等，则调用 secret_phase\verb|secret_phase|。

0x603870\verb|0x603870| 这个地址并没有在其他任何地方出现过，但是在 skip\verb|skip| 和 read_line\verb|read_line| 中，出现了地址 0x603780\verb|0x603780|。对这两个函数逆向，大致如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
char input[MAXLEN]; // 0x603780
int num_input_strings = 0;
FILE *infile;

int skip() {
  fgets(input + 90 * num_input_strings, 90, infile);
  ...
}

char* read_line() {
  ...
  char *start = input + 90 * num_input_strings;
  ...
  num_input_strings++;
  ...
  return start;
}
由此可知，以地址 0x603870\verb|0x603870| 开头的字符串就是 Phase 4 的输入，而在 Phase 4 中恰好要输入两个整数，在它们之后再输入 MrEvil，我们就能够进入 Secret Phase。

Secret Phase

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
struct tree_node {
  int val;
  struct tree_node *ls, *rs;
  long place_holder;
} t[15] = {{0x024, &t[1], &t[2]},
           {0x008, &t[5], &t[3]},
           {0x032, &t[4], &t[6]},
           {0x016, &t[12], &t[10]},
           {0x02d, &t[7], &t[13]},
           {0x006, &t[8], &t[11]},
           {0x06b, &t[9], &t[14]},
           {0x028, NULL, NULL},
           {0x001, NULL, NULL},
           {0x063, NULL, NULL},
           {0x023, NULL, NULL},
           {0x007, NULL, NULL},
           {0x014, NULL, NULL},
           {0x02f, NULL, NULL},
           {0x3e9, NULL, NULL}};

int fun7(struct tree_node *x, int y) {
  if (x == NULL) {
    return -1;
  } else {
    if (x->val <= y) {
      if (x->val == y) {
        return 0;
      } else {
        return 2 * fun7(x->rs, y) + 1;
      }
    } else {
      return 2 * fun7(x->ls, y);
    }
  }
}

void secret_phase() {
  long x = strtol(read_line(), NULL, 10);

  if (x > 1001 || x < 1) {
    explode_bomb();
  }

  if (fun7(t, x) != 2) {
    explode_bomb();
  }
  ...
}

结合二叉搜索树知识，输入应为 22。

CS:APP bomblab 的逆向结果

https://gzezfisher.top/csapp-bomblab/

作者

Fisher Cai

发布于

2025-07-31

更新于

2025-08-03

许可协议

评论

目录

链接

分类

最新文章

归档

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×