Alex Chiu


  • Home

  • About

  • Categories

  • Archives

  • Schedule

  • Sitemap

CSAPP-buflab

Posted on 2018-09-05
cache lab

原函数返回地址—-<
保存的%ebp值(栈帧指针)—-<
缓冲区—-<
缓冲区—-<
。。。。
。。。。
%esp(栈指针)—-<

Level2

image

global_value 是个全局变量,不在栈中,因此需要写一个函数把global_value值改为value

我们现在要找到global_value的地址,发现

0x804d100就是value的地址,0x804d108就是cookie的地址。因此我们想把0x804d100地址所在的数值改为我们的cookie

image

建立p2.s文件

注意x86是data-load 是利用register来完成的

image

把cookie值传到%eax 临时寄存器,然后把寄存器里面的数值传给global_value的地址

最后把bang函数地址压栈,那么原来返回地址就会改为执行bang函数了。

反汇编得到的代码:

image

gdb调试寻找缓冲区的位置,注意缓冲区不是esp-0x38,而是ebp-0x28噢

得到缓冲区首地址为0x55683938

意思就是说返回地址变回缓冲区首地址,然后原函数返回的时候会跳到缓冲区地址,然后开始访问我们自己写的机器代码,实现把global_value值改为cookie的功能。

image

最后结果:

image

level3

是把返回地址改为cookie值,同时不改变原函数压栈情况

因为覆盖栈的时候,会把ebp(基址指针给覆盖掉,所以先记录下基址的地址)

image

汇编代码
我们应该要改变eax的值为cookie,同时把原来getbuf后一条指令的地址压栈

image

然后为了求基址地址,这里折腾了好久,原来要求的不是寄存器本身的值,而是求寄存器指向的值

但why???
image

最后结果:

b8 14 03 aa
65 68 be 8d
04 08 c3 00 <—attack code
00 00 00 00
00 00 00 00
00 00 00 00
00 00 00 00
00 00 00 00
00 00 00 00
00 00 00 00
90 39 68 55 <— address of ebp,to ensure that the original ebp doesn’t change
38 39 68 55 <— initial address of buff zone

CS230 DeepLearning And Neural Networks

Posted on 2018-09-02 | In PRML

深度学习 ——Coursera

学习资源:https://github.com/Kulbear/deep-learning-coursera

https://github.com/andersy005/deep-learning-specialization-coursera/blob/master/01-Neural-Networks-and-Deep-Learning/week2/Programming-Assignments/Python%2BBasics%2BWith%2BNumpy%2Bv2.ipynb

官网:https://cs230-stanford.github.io/

Basic of Neural Network of Programming

Logistic Regression — Binary Classificatoin

如果想把图片作为输入,判断这张图片是否为一只猫
首先得了解如何在计算机中表示图片。

图片可以表示为一个36464的矩阵,分别记录着R,G,B三个颜色通道的数值

然后定义一个向量x 让矩阵转化为一个向量,向量包含矩阵所有元素

nx表示特征向量的维度

image

X矩阵是把向量按列排列,相应的,结果Y也是按列排列
在python中,X.shape 返回数组(nx,m)对应行数和列数,也就是向量维度为nx,个数为m

image2


Logistic Regression

1.右上角的红色笔记不必理会

2.sigma表示sigmoid函数,是一个squashing function,即把结果压缩到0-1范围内

image

下一步,为了改变w与b,需要定义一个cost function

w is an nx dimenstional vector,while b is a real number.

如果cost function是半个平方误差的话,可能只会找到局部最优解
所以我们这里使用
imgae

image

注意

不要把Loss function 和 cost function 混了!

loss function 计算的是单个训练样本的误差

而cost function 计算的是整个训练集的平均误差

Gradient Descent

梯度下降就是我们要来寻找全局最优点的方法

image

1.learning rate 学习率,控制每一次迭代或者梯度下降法中步长大小

2.那为什么右上角那个repeat能保证梯度下降是make sense的呢?


d(J)/dw 代表的是斜率,试想在全局最优点左侧,梯度是负数,相当于w加上了一个正数,那么
w就会向全局最优点靠近的方向移动。反之亦然,所以通过不停迭代最后一定会达到全局最优点。

image

Computation Graph

1.神经网络正向传播,计算输出,反向传播用来计算导数,为什么要这样组织呢?

image

反向传播意思是如果你要计算dj/da 按照红色箭头来计算(把从右到左得到的结果依次运用链式法则来求)

Logistic Regression Grdient Descent on m examples

image

两个循环,时间复杂度是M*N M为特征向量个数 N为特征数

那如何摆脱这个循环呢?

可以使用vectorization技巧

vectorization

image

所以要使用向量化来加速代码的运行

实际上,GPU和CPU都支持并行计算,SIMD指令,当时用内置函数的时候,例如np.dot,CPU和GPU会利用并行化进行更快的运算。

因此尽量避免使用显式的for循环

例如下例:

image

image

具体我们来看逻辑回归的向量化

image

用
z = np.dot(w.T,x)+b
就可实现移除两个for循环的功能

小知识:python中的broadcasting

意思就是虽然b是常数,但是当与一个向量相加的时候,b自动扩展为一个与向量维度相同,值全部为b的向量。

具体实现

image

python 的 broadcasting

(axis=0)按列相加
(axis=1)按行相加

image

小技巧,定义vector的时候,写为下半部分的形式,不要使用np.random.randn(5)这种rank为1的结构

image

CSAPP-链接器(二)

Posted on 2018-09-02 | In ICS

回顾 链接操作的步骤

1.确定符号的引用关系 (符号解析)

2.合并.o文件(同节合并)

3.确定每个符号的地址(确定地址)

4.在指令中填入新地址 (2.3.4属于重定位)(修改引用)


符号解析(符号绑定)

说白了就是把每个模块引用的符号与某个目标模块中的定义符号建立关联

-程序中有定义和引用的符号

1
2
3
void swap(){} /*定义符号swap*/
swap();   /*引用符号*/
int *xp = &x; /*定义符号xp,引用符号 x*/

-编辑器把定义的符号放在一个符号表当中

1.符号表是一个结构数组,在.symtab节中


2.每个表项包含符号名,长度与位置信息

-链接器把符号的引用存放在重定位节中(.rel.text与rel.data)

-链接器把每个符号的引用都与一个确定的符号定义建立关联


重定位

1.把多个代码段与数据段合并成一个单独的代码段和数据段


2.计算每个定义的符号在虚拟地址空间中的绝对地址


3.把可执行文件中符号引用处的地址修改为重定位后的地址信息


(局部变量temp分配在栈中,不会在过程外被引用,因此不属于符号定义)

链接符号的类型

1.Global Symbols (模块内部定义的全局符号)

eg: 全局变量 指在本模块定义,但是在外部模块可以使用的

2.External Symbols (外部定义的外部符号)

eg: 函数原型的函数名,函数中的带extern的变量名 外部模块定义,在本模块可以使用

3.Local Symbols (本模块定义并且引用的局部符号)

eg: 带static的变量名 分配在静态数据区,并不是局部变量!局部变量是分配在栈中的
本模块定义,只能在本模块使用

类型举例:

1
2
3
4
5
6
7
int buf[2] = {1,2};
void swap();

int main(){
swap();
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
extern int buf[];

int*bufp0 = &buf[0];
static int *bufp1;

void swap(){
   int temp;
bufp1 = &buf[1];
temp = *bufp0;
*bufp0 = *bufp1;
*bufp1 = temp;
}

全局符号: main.c中的buf,swap.c中的swap(),bufp0;

外部符号 swap.c中的buf[],main.c中的swap();

局部符号 swap.c中的局部符号

我们说符号的定义,实质上就是分配了存储空间。

函数名符号指代码所在区

变量名指静态数据区

定义符号的值就是目标所在的首地址

全局符号的强,弱

函数名以及初始化后的变量是强全局符号

未初始化变量是弱全局符号

上面函数 main.c 的swap(),swap.c的 buf[],是弱符号,其余的全局符号都是强符号

多重定义符号的解析规则

1.强符号不能多次定义

2.一个符号被定义为一次强符号和多次弱符号,则按强定义为准

3.多个弱符号定义,则任选其中一个

例子

image

FLD1指把1.0放在ST(0)处,ST(0)是x87浮点处理器的一个栈

FSTPL &d L指double对应的双精度,存放8个字节

image

相当于d变为浮点数表示之后,把x所在的位置给冲掉了,导致x会被改变

(注意小端方式,意味着位数小的放在地址小的位置)


静态连接

多个可重定位目标模块 + 静态库(标准库,自定义库等)
(.o文件) + (.a文件,其中包含多个.o模块)

静态库(.a archive files)

1.把所有相关的目标模块(.o)打包为一个单独的库文件(.a),称为静态库文件,也成为存档文件

2.在构建可执行文件的时候,只需要指定库文件名,连接器会自动到库中寻找那些应用程序用到的目标模块,并且只把用到的模块从库中拷贝出来,链接到可执行文件中。

eg: 在函数中使用printf函数,程序员不需要在文件中包括printf的代码,链接器会自动在静态库查找定义的符号来解析printf符号,及实现直接调用。

静态库的创建

ar 能把指定的.o文件打包生成静态库文件(.a文件)

eg: ar rs libc.a atoi.o printf.o random.o

自定义库文件

gcc -c p1.c p2.c
ar rcs mylib.a p1.o p2.o

然后如果你写了一个main.c,想要调用静态库中的函数

gcc -c main.c
gcc -static -o myproc main.o ./mylib.a

使用静态库的过程

image

-按照命令行给出的顺序扫描.o,.a文件

-扫描期间把当前未解析的引用记录到一个列表U中

-每遇到一个新的.o与.a模块,试图用其来解析UI中的符号

-扫描到最后,如果U不为空,则发生错误

image

总结出来的技巧: 把静态库都放到后面去


共享库

但如果我们只是想用库中的某一函数,却仍然要把所有内容都链接进去,会造成文件中静态库的大量重复。

动态链接可以在首次载入的时候就执行,由ld-linux.so完成,这样所有的程序可以共享同一个库,而不用进行封装。

image


符号重定位之后,得到两个文件:将要合并的*.o文件的集合以及定义符号的集合

重定位

第一步 合并相同的节

把集合E中的所有目标模块相同的节合并成新节

例如把所有.text节合并作为可执行文件中的.text节

第二步 对集合D中的定义符号进行重定位(确定地址)

即确定新节中所有定义符号在虚拟地址空间中的地址

例如为函数确定首地址,进而确定每条指令的地址,为变量确定首地址

完成这一步之后,每条指令和每个变量的地址都可以确定

第三步 对引用符号进行重定位

修改.text和.data节中对每个符号的引用(地址)
需要用到.o文件中的.rel_data 和.rel_text中保存的重定位信息

什么是重定位信息?

imaeg

例如 把add B 这一句翻译为机器代码,add翻译为操作码05 B为一个引用,一开始不知道是什么数值,于是写入一个00000000初始位置,同时生成一个重定位条目,提示后面这个位置的值要被修改。

又例如jmp 后面接的是L0,则在.rel_text节中生成重定位信息,但一开始还没走到L0指令,还不知道L0的定义是什么,于是填了一个随机地址FCFFFFFF,在后续当中修改这个地址,让他指向真正的L0地址

左下角 offset 0x1 代表从第一个字节开始重定位(下方框是.text节,起始第0个字节为05),两个数字(一共八位)一个字节,那么02就是第五个字节,FC就是第六个字节。

左下角symbol 表示重定位的符号为B

左下角 type 重定位类型为绝对地址

重定位操作举例

E中有main.o 和 swap.o两个模块! D中有所有定义的符号!

在main.o与swap.o的重定位条目中有重定位信息,反映了符号引用位置(offset),绑定的定义符号名,重定位类型)

读取重定位条目: readelf -r main.o

PC相对地址重定位

image

0: 55 表示main从.text最初的地方开始

3: and 指令的 0xfffffff0 是为了让栈顶指针esp为16字节的倍数

swap函数调用: 6: e8 fc ff ff ff 注意x86是小端法存储,因此
因此立即数为ff ff ff fc 即-4

由于 fc ff ff ff 不是swap函数的首地址,所以会生成一个重定位信息

1
7:R_386_PC32 SWAP

表示在偏移量为7的位置,即fc开始的位置,按相对地址方式进行重定位ie

数据的存储方式:

image

小端方式,第一个数据为 00 00 00 01

大端方式,第二个数据为 00 00 00 02

相对地址的重定位方式

假定:

imagel

main占 0x12B,因此swap初始地址为

-0x8048380+0x12=0x8048392

但由于不是4的倍数,因此在四字节边界对齐的情况下,应该为0x8048394

call 指令最后的机器代码应该为多少?

call指令运行机理:把call指令的下一条指令压栈,然后跳转到swap函数的首地址

转移目标地址 = PC+偏移地址 PC=0x8040380+0x07-init

注意当执行到某一条指令的时候,PC为该条指令下一条指令的地址噢,所以PC
应该为0x08048380+b = 0x0804838b

image

重定位值就是偏移地址

所以重定位值 = 转移目标地址 - PC = 0X9

CALL 机器代码就是如上图结果所示

绝对地址重定位

绝对地址重定位意思就是把buf的地址直接填到00 00 00 00
image

这两个段都从可执行文件装入,占了4kb

image

具体过程

buf在运行时候的存储地址ADDR(buf)=0x8049620

重定位之后,bufp0地址及内容变成什么? bufp0紧接在buf后,故地址为0x8049620+8 = 0x8049628

符号重定位

image

重定位结果:

image

09 00 00 00 含义是当前PC(0x804838b加上一个立即数偏移量9)得到要跳转到的目标地址
为什么是不是从8048392开始呢?因为函数地址要求4边界对齐

image

可执行文件的存储器映像

image

左边是存储在物理磁盘当中的,而右边是存储在内存当中的

CSAPP-链接器

Posted on 2018-08-31 | In CSAPP

静态连接

构造可执行文件的时候,链接器所完成的任务:

1.符号解析

每个符号对应于一个函数,一个全局变量或者静态变量,符号解析的目的是把每个符号引用正好和一个符号定义关联起来。

2.重定位

把每个符号定义和另一个内存位置关联起来,然后重定位这些节,修改所有对这些符号的引用。


目标文件有三种形式


1.可重定位目标文件:eg: prog.o

1.包含二进制代码和数据,编译的时候可以和其他可重定位目标文件合并起来,创建一个可执行目标文件。


2.每个.o文件由对应的.c文件生成


3.每个.o文件代码和数据地址都从0开始
image

2.可执行目标文件:eg: a.out

1.直接可以复制到内存中执行


2.代码和数据地址为虚拟地址空间中的地址

3.共享目标文件(*.so)

3.特殊的可重定位目标文件,能在装入或者运行的时候被装入到内存并且自动被链接


符号和符号表

1.被模块m定义并能够被其他模块引用的全局符号。全局连接器的符号对应于非静态的C函数和全局变量。

2.被其它模块定义而且被模块m引用的全局符号,这些符号叫做外部符号,对应于在其它模块中定义的非静态C函数和全局变量。

3.只能被模块m定义和引用的局部符号,对应于带static的C函数和全局变量。

————————————————————分割线————————————————————————-

Coursera 听课笔记

hello.c->预处理(cpp)->hello.i(ASCII中间文件)->编译器(cc1)->汇编语言文件->(汇编器)->可重定位目标文件(main.o)->链接->可执行目标文件

预处理命令

gcc -E hello.c -o hello.i

cpp hello.c > hello.i

处理源文件中以#开头的预编译指令,包括:
1.删除#define 并且展开所定义的宏
2.处理所有条件预编译指令
3.插入头文件到#include 处,可以用递归方式进行处理
4.删除所有的注释”//“和“/ /”
5.保留所有#pragma编译指令
6.添加行号和文件名标识,方便编译的时候编译器产生调试用的行号信息

编译

把预处理文件进行此法分析,语法分析,语义分析并且优化

编译命令

gcc -S hello.i -o hello.s


gcc -S hello.c -o hello.s


但是得到的.s 汇编代码文件,机器仍然无法识别

汇编

.s 文件称为汇编语言源程序


汇编程序用来把汇编语言源程序转换为机器指令序列


汇编指令和机器指令一一对应,前者是后者的符号表示,他们都属于机器级指令,所构成程序称为机器级代码


gcc -c hello.s -o hello.o


gcc -c hello.c -o hello.o


汇编结果是一个可重定位的目标文件

链接

把多个可重定位目标文件合并来生成可执行目标文件命令

gcc -static -o myporc main.o test.o

链接器的由来:

用符号表示跳转位置,无需修改jmp指令的跳转目标

汇编语言出现:

用助记符表示操作码 jmp mov


用符号表示位置 L0


用助记符表示寄存器


最终进行汇编和链接

链接,先确定L0的地址,然后在jmp指令中填入L0的地址

高级编程语言的出现

子程序起始地址和变量初始地址是符号定义


调用子程序和使用变量是符号的引用

链接操作的步骤

1.确定符号引用关系(符号解析)


2.合并相关.o文件


3.确定每个符号的地址


4.在指令中填入新的地址
(2.3.4都属于重定位)

使用链接好处

模块化


1.一个程序可以分成很多源程序文件


2.可以构建共享函数库


效率高


1.空间上无需包含共享库所有代码


2.源文件当中无需包含共享库所有代码
例如只要直接调用printf()函数,无需包含其源码
可执行文件和运行时的内存只需包含所调用函数的代码,不需要包含整个共享库

1
2
3
4
5
6
7
8
9

main.c
int buf[2] ={1,2};
void swap();

int main(){
swap();
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
swap.c
extern int buf[];
int *bufp0 = &buf[0];
static int *bufp1;

void swap(){
int temp;
bufp1 = &buf[1];
temp = *bufp0;
*bufp0 = *bufp1;
*bufp1 = temp;
}
局部变量temp 分配在栈中,不会在过程(函数)被引用,因此不是符号定义
可执行文件生成 -O2 2级优化 -g 生成调试信息 -o 目标文件名
链接本质:合并相同的节

系统代码: .text


系统数据: .data


未初始化的静态变量: .bss


未初始化的全局变量 COMMON


链接就是要把不同可重定位目标文件中相同的节合在一起,放在可执行目标文件当中

程序头表

目标文件的格式

目标代码:编译器和汇编器处理源代码后生成的机器语言目标代码
目标文件:包含目标代码的文件
静态连接库文件可以由若干个可重定位目标文件组成

ELF(Executable and Linkable Format)

两种视图


1.链接视图


2.执行视图

image

可执行目标文件 的节(section)是ELF文件中具有相同特征的最小可处理单位,例如 .text:代码,.data节数据,.rodata只读数据,.bss未初始化的数据

可重定位目标文件
由不同的段(Segment)组成,描述节如何映射到存储段中,多个节可以映射到同一个段中,例如可以合并
.data节和.bss节,映射到一个可读可写的数据段中。

链接视图——可重定位目标文件格式

image

image


补充: 节头表包含每个节的节名,偏移以及大小。


从ELF头读取节头表,再在节头表中读取节的信息

C语言规定

未初始化的全局变量和局部静态变量默认初始值为0

把.bss 与 .data分开的好处

data节中存放具体的初始值,需要占磁盘空间
.bss无需存放初始值,只要说明.bss每个变量将来在执行的时候占用多少字节就行
因此.bss实际上不占用磁盘空间,提高了磁盘空间利用率



所有 未初始化的全局变量和局部静态变量都被汇总到.bss节中,通过专门的“节头表”来说明应该为.bss节预留多大的空间


.bss 最初是UA-SAP汇编程序中所用的一个伪指令,为符号预留一块内存空间。

image

ELF头占52个字节
Elf_Half 占2个,e_ident 16个, 其他的占4个

image

在链接视图中,虚拟地址都为0,因为其并不会执行

执行视图–可执行目标文件

IMGAE

总结

1.可执行目标文件是ELF的执行视图,由不同的段组成

2.可重定位目标文件是ELF格式的链接视图,由不同的节组成

3.两种目标文件的数据都是二进制表示的补码形式

4. 链接的本质:

把指定的若干个可重定位目标模块的代码和数据分别合并,以生成一个只读代码段和一个可读可写数据段

5. 链接器主要功能:

符号解析以及重定位

6.符号解析的含义

就是对每个需要链接的模块中的符号引用找到对应的符号定义,把符号引用与每一个唯一的符号定义进行绑定。

7.重定位

把合并后的只读代码段以及可读可写数据段中符号引用处的引用位置重新填上新的数值,用来指向绑定的定义符号。

1…56
Alex Chiu

Alex Chiu

Alex's personal blog

54 posts
4 categories
4 tags
© 2019 Alex Chiu
Powered by Hexo
|
Theme — NexT.Mist v5.1.4