简介

XML 是一种可扩展标记语言，被用来传输和存储数据。它是一种有逻辑的树结构。

Python 使用 xml.ElementTree 解析

1
2
3

import xml.etree.ElementTree as ET
import codecs
import json

codecs 用于打开文件，json 用于保存清洗完的数据。

实验描述

本次实验利用程序需要外部输入的特点，输入机器码对程序返回值覆盖，以达到攻击的目的，即在getbuf函数需要的输入中做手脚，以致不能正常返回，执行攻击代码。

第一阶段

第一阶段中栈随机化未开机，可以得知内存位置的确切地址，且栈中机器码可执行。

那么我们将需要执行的操作码和地址输入机器码即可。

实验步骤

准备工作

使用tar -vxf将炸弹压缩包解压,cd进入,可以从bomb.c中看出实验的用意以及程序的大致
逻辑,bomb为可执行程序,使用gdb调试该程序.

1
2
3
4

(gdb) b read_line 
Breakpoint 1 at 0x40155c
(gdb) b explode_bomb 
Breakpoint 2 at 0x4014e4

给read_line函数打上断点,以便每次输入运行一关.给explode_bomb打上断点,以便在炸弹爆炸
前可以处理.

phase_1

获得phase_1汇编代码

1
2
3
4
5
6
7
8
9
10
11

(gdb) disas phase_1
Dump of assembler code for function phase_1:
   0x0000000000400e80 <+0>:	sub    $0x8,%rsp
   0x0000000000400e84 <+4>:	mov    $0x4024a0,%esi
   0x0000000000400e89 <+9>:	callq  0x40127e <strings_not_equal>
   0x0000000000400e8e <+14>:	test   %eax,%eax
   0x0000000000400e90 <+16>:	je     0x400e97 <phase_1+23>
   0x0000000000400e92 <+18>:	callq  0x4014e4 <explode_bomb>
   0x0000000000400e97 <+23>:	add    $0x8,%rsp
   0x0000000000400e9b <+27>:	retq   
End of assembler dump.

可见,此题是将我们输入的字符串与地址0x4024a0处字符串比较,不等则爆炸.查看该字符串.

1
2

(gdb) x/s 0x4024a0
0x4024a0 <__dso_handle+344>:	 "We have to stand with our North Korean allies."

那么答案是We have to stand with our North Korean allies.

设计思路

BM算法是一种后缀匹配算法,其具有比KMP算法更优秀的性能表现.其核心思想有二
,第一是坏字符,坏字符就是pattern与text从右往左第一失配的在text中的字符,
二是好后缀,好后缀就是pattern与text从右往左连续匹配成功的子串.对于坏字符
和好后缀,有各自的模式串移动规则,可以确定各自失配时需要移动的位数,最终选
择二者中移动位数较大者移动.在主函数中,让用户输入文档名与需要查找的单词.
每次从文档中读取一行进行匹配搜索,每次使用BM算法搜索完成后,若搜索到单词,
则将主串中开始匹配的位置定为查找到单词的下一行,使用BM算法进行下一个匹配
搜索,直至搜索完当前行.而后循环直至匹配完整个文档.

设计思路

图编号

如图所示，从上到下，从左到右，给17个顶点进行编号，以两个顶点代表一条边，例入2-3代表可以从顶点2走到顶点3。问题即为求解从2 -> 17的通路。

求解思想

求解一条通路，应当从起点出发，不断前进到后续可行顶点，当在一个顶点无法继续前进时，则回退到上一个顶点，寻找其他可行顶点，直到到达终点。此思想符合数据结构栈的特点。首先将起点压栈，然后将从当前顶点可到达的一个顶点压栈，然后将该顶点标记为已访问，随后到达下一个顶点，在某个顶点无法继续走通时，将当前顶点出栈，回退到上一个顶点重新选择可以到达的且未访问的顶点。如此循环，直到终点被压入栈中，此时栈中所有顶点即为一条通路。

求解一条最短路径，应当从起点出发，访问所有可以到达的下一级顶点。再从所有下一级顶点出发，访问所有可访问的再下一级顶点，如此循环，每一级顶点距起点距离相同。过程中记录路线。此想法符合数据结构中队列的特点。首先，将起点入队。然后将队头元素出队，将该元素可访问到的且未被访问的顶点置为已访问，然后入队，注意记录被入队节点的前一个节点。直到队列为空。最后顺着终点的前驱顶点输出即可得到路线。若有多个终点，要寻找到最近的终点出去，则将结束循环条件改为有终点入队即可。

CS:APP 2.60

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <stdio.h>
unsigned replace_byte(unsigned x, int i, unsigned char b)
{
    x = x & (~(0XFF << (i << 3)));//相应字节置零
    x = x | (b << (i << 3));      //相应字节改为char b
    return x;
}
int main()
{
    unsigned ret = replace_byte(0X12345678, 1, 0XAB);
    printf("0X%X\n", ret);
    return 0;
}

0X1234AB78

利用按位运算$x \& 1 = x , b | 0 = b$。