CSAPP：Bomblab —— 原来习题还可以这么做

第一次在豆瓣上发东西，呵呵～

本学期选了汇编程序设计，实际上就是用这本CSAPP当教材了。作者是CMU计算机系主任，该门课的经典地位应该和MIT的SICP差不多吧（也在这学期选了～）。

最初只是想混学分，结果上了之后才发觉这门课是如此强大。我们老师也将CMU原配的几个Lab作业给移植 了过来，目前已经完成了datalab和下面要介绍的bomblab，做过之后真的是觉得受益匪浅。

Bomblab 的主要是通过姓名学号可以从服务器上下载一个bomb的tar包，用objdump可以得到它的汇编源码与c文件。在程序运行过程中需要输入若干字符串，如果字符串不符合要求则将导致炸弹爆炸，每爆炸一次扣0.25分。所需输入字符串的信息可以根据分析汇编代码以及GDB的单步调试推测得出，不过只能在服务器上运行与调试程序。

花了一天时间终于把6个phase给过了。虽然每个人的bomb都不相同，但总体上每个phase的解法应该都是差不多的。篇幅原因bomb的代码就不帖了，有需要的朋友可以私下联系。

phase1：
    热身关卡。string_not_equal就提示需要比较两个字符串，通过gcc函数调用规范知道压入堆栈的两个参数分别为输入字符串与程序内部字符串。然后就是去相应的内存空间找字符串了，我得到的是“Why make trillions when we could make... billions?”，很无语的一句话。

phase2：
    要求输入6个数，输入后就直接放在堆栈的局部变量里了。后面一段汇编代码实际上是一个循环判断6个数需要满足的条件。我的bomb是要求一个公差为5的等差数列，随便敲6个搞定。（样例里的是1到6的阶乘）

phase3：
    最初开始看如此之长的代码实在是下了一跳。但分析之后发现代码之间的模块还是相当明显的，每一段都仅仅是执行一个判断。这就很自然联想到C中的switch语句，后面又看到一条jmp语句，jmp的内容是根据输入的第一个值进行选择，更证实了猜想。
    sscanf，它的三个操作数分别为输入的源，格式，存储位置，而格式是程序内可以在相应地址单元查到的，也就是“％d %c %d”。
    第一个d是switch选择的分支，通过输入格式或堆栈信息可知后面要输入一个4Byte整数和一个1Byte字符。上面提到的jmp可以查到相应分支的比较语句使输入的字符与整数满足比较即可。
    需要注意的是， 结果的存储布局相当诡异。先存的是第一个d,然后是第二个d，最后才是c。我也是用x命令查看堆栈后才发现的，不注意的话就可能把字符和整数输入反引爆炸弹。由于上周末刚做的操作系统实习Lab1(MIT 6.828)，因此一开始没反应过来。

phase4:
    phase的代码要求输入的数值作为fun4的参数，使返回值等于给定值。查看fun4的内容，每次把参数减1后自调用，再用参数与结果相乘，出口是参数1时返回1。很明显的阶乘。

phase5:
    代码不长，但是相当绕。有第一个炸弹点知要输入的字符串长度为6。后面又看到了一个string_not_equal，可见又是一个字符串比较的题目。待比较的字符串为"titans"，泰坦，呵呵。
    但显然这已经不是第一题的热身关卡了，需要对输入的字符串作相应变换。其实中间一段变换代码就是一个不断寻地址的过程。把每个字符ascii码截取出后四位，得到一个0～F范围内的十六进制数。在以这个数做索引从某段地址空间中提取所要的6个字符。逆着推上去就可以知道输入字符串应该是什么了，由于高4位认给，因此我输了个很无耻的“＝0＝5；1”，哈哈。

phase6:
     boss关。
     要求输入6个整数，第一个循环判断所有数只能为1～6。后面一个两重循环判断所有数互不相等。然后就是一个很恶心的多重循环，在内存和寄存器中倒腾半天后才知道原来是要把某个内存块中的链表给排序。
     说起来简单，不过那漫天的跳转以及地址与数据之间的传递实在是看得人头疼。难怪人们不提倡goto语句。
     在这关上花的时间超过了前5关的总和，炸弹还爆了3次。果然如作业介绍中所说：“The last phase will challenge even the best students”。

secret_phase:
     隐藏关我看了一下进入条件，连进入的密码都弄出来了，就是不知道那个该死的地址为什么无法被修改。看了一下隐藏关的代码，其实比前几个来说还是简单点的。就是输入一个整数，然后在一棵BST中查找，并按照要求的算法求权值，使值等于某个给定数。
     只是汇编中的BST，怎么看怎么ws。

总结:
昨晚9点下课后直奔实验室，一直弄到凌晨3点半还是没把phase6给拆掉。中午午饭后一直想到下午才解决。其间的惊险刺激与身心疲惫自然是不必说。尽管其间爆了4次，但把全部炸弹都拆完后还是充满了成就感。
感觉这份作业还是很有创意的，使我们对工具的掌握以及汇编级编程的能力都得到很好锤炼。老美这方面实在太nb了，国内什么时候也能想出点这样的教育方式呢？