精子又要搬家了,来  看一看有什么正在甩卖  吧。
标签 #计算机科学

笔记:函数和栈

从入门编程开始,我们一直在和函数打交道,但直到今天,我才勉强敢谈一谈对函数的认识。

在以C为代表的,绝大多数“正常”的编程语言中,函数都 是组织代码和组成程序的基本单位,甚至在CPU中也内建了对函数(过程)调用的支持。其他所谓面向对象风格 不过是对函数的进一步封装而已。

程序执行时的控制流,也是以函数为基本单位来进行调度的,每一次函数调用,就标志着一次控制流的转移。在经典的模型中,一个函数可以调用包括自己(调用自身的行为被称为递归)在内的任何函数,被调用的函数也可以再调用其他函数。函数间通过参数和返回值来传递信息,前者用于调用者向被调用信息发送信息,后者用于被调用函数向调用者返回信息。

那么我们如何在脑中构建一幅函数间互相调用的景象呢?这里我就不得不提到栈这个概念。栈是最简单最基础的数据结构之一,栈是一种线性的容器,但其特殊之处在于只能从其中一端插入或取出数据,这一端被称为栈顶。这使得栈具有这样的特征:先被插入栈的数据,要最后被取出;后加入栈的数据,将先被取出,即LIFO(Last In First Out, 后进先出).

函数调用存在着类似的性质:在某一时刻的同一调用树(而不是多个并行执行的函数)上,最先被调用的函数将最后被返回,因为它需要等待所有之后被调用的函数返回才行。 于是在计算机中,我们通过栈来维护函数间的调用状态,这种栈,也被称为运行栈,线程栈,函数栈。

栈上为单个函数所分配的区域,被称为栈帧。栈顶由一个栈顶指针来指示,栈顶指针在函数执行时会随时改变,因此还有另外一个帧指针指向当前栈帧的起始处,函数通常通过帧指针来访问数据。栈指针和帧指针被保存在单独的寄存器上。

函数执行时所定义的局部变量都将被分配在栈上,这些局部变量(和函数参数)决定了函数的执行状态。

当函数调用另一个函数时,首先要保存寄存器的值。因为寄存器是被多个函数所共享的自由,为了防止被调函数覆盖寄存器,主调函数必须负责将部分寄存器的值保存在栈上。然后将要传递给被调函数的参数插入栈中,在参数较少的情况下,也可能直接使用寄存器来传递参数。然后再插入下一条指令的地址,即被调函数返回时要返回到的地址。最后将控制权移交到被调函数的首地址。

被调函数开始执行,这也标志着调用者的栈帧已经结束。被调函数首先在栈上保存当前旧的帧指针,然后将帧指针甚至为栈指针减去1,即当前栈帧的第一项是旧的帧指针。 然后被调函数也开始保存寄存器,调用者和被调函数分别负责保存哪些寄存器是有约定的。

然后被调函数开始执行真正的代码,并通过帧指针来访问参数,参数在栈中的顺序是由调用约定决定的。在函数执行的过程中,函数也可能在栈上创建和销毁局部变量,但均遵循栈的后入先出原则。在函数执行即将结束时,将返回值保存在特定的寄存器中。

当被调函数返回时,首先恢复已保存的寄存器的值,然后将帧指针赋值给栈指针,即丢弃当前栈帧除了已保存的旧的帧指针的全部数据。然后从栈恢复旧的帧指针,至此被调函数已经完成了全部清理工作,帧指针指向调用者的栈帧头部,栈指针指向调用者栈帧的尾部。被调函数将控制权移交给当前栈指针指向的返回地址。

现在控制权回到了调用者,调用者首先弹出栈中的返回地址和参数,然后恢复寄存器的值,接着执行剩下的代码,被调函数的返回值在特定的寄存器中。

本文从栈的角度描述了一个函数的执行过程,着重介绍了4个关键的时间点:调用者调用被调函数、被调函数开始执行、被调函数返回前的清理工作、控制权返回到调用者。

可以看到函数的执行和栈的使用本来就是密不可分的。

笔记:缓冲区溢出

缓冲区溢出可以说是针对系统级软件最常见的攻击方式了,这类攻击可以通过操作系统或软件提供的API接口,或者通过文件和网络,发送一个特定的字节序列,最终改变被攻击程序的行为,甚至取得被攻击进程的权限。

计算机使用栈来维护函数的执行状态,如果函数在栈上分配了一段缓冲区,但向其写入数据时没有进行充分的长度检查,那么溢出的数据就会覆盖栈上之后的内存。因为栈是由高地址向低地址延伸的,即栈底在高地址,而数据写入是由低地址向高地址覆盖的,所以溢出的数据会向着栈底,即调用者的栈帧进行覆盖。

在调用者和被调用者的栈帧交界处,存在着一些相当敏感的数据,如函数的返回地址,通过覆盖这个值,可以将控制权移交到任意地址。

攻击者需要将返回地址指向到攻击者构造的恶意代码,因此攻击者必须知道当前栈帧的地址。在经典的情况下,同一个程序在相同架构,相同的操作系统中的栈地址是固定的,攻击者很容易通过几次尝试来确认这个值。

针对这个思路,较新版本的Linux和GCC使用了一种地址空间布局随机化的技术,同一个程序每次运行时,程序的各个部分,如代码段,数据段,堆和栈,动态链接库都会被装载到随机的地址。

但攻击者可以在真正的恶意代码前加入足够长的nop指令,nop指令不执行操作,只是一个空指令。然后随机地进行跳转,只要能够跳转到nop序列中的任意一条指令,都可以执行到后面的恶意代码。

较新版本的GCC中还加入了一种“栈保护者”的机制,GCC会在每个函数的栈帧开始处加入一个随机的哨兵值,并在函数返回时检查该哨兵值,如果哨兵值发生了变化,即表示出现了缓冲区溢出,程序会中断执行。

因为攻击者需要在栈上构造可执行的恶意代码,因此还有一种思路就是将栈所在页标记为不可执行,由硬件进行这个检查,使得攻击者在栈上的恶意代码根本无法执行,目前有部分CPU支持这项特征。

以上是缓冲区溢出攻击的基本原理,和三种操作系统级别的防御对策,这些防御措施对用户态的程序而言都是透明的,无需程序员额外关注,同时这些机制的效率损失也相当小。

零毫秒:Kademlia 笔记

Kademlia协议(模型)是被电驴,BitTorrent所采用了的,基于异或距离算法的分布式散列表(DHT), 它实现了一个去中心化的信息储存与查询系统。

Kademlia将网络设计为一个具有160层的二叉树,树最末端的每个叶子便是一个节点,节点在树中的位置由同样是160bit的节点ID决定。

每个bit的两种可能值(0或1), 决定了节点在树中属于左面还是右面的子树,160层下来,每个节点ID便都有了一个确定的位置。

Kademlia使用独特的异或距离算法来计算节点间的距离,异或是一种简单的数学计算,它有很多独特的性质,这些性质在之后会为我们带来方便:

自己与自己的距离为0:
x ^ x = 0
不同的节点间必有距离:
x ^ y > 0
交换律,x到y的距离等于y到x的距离:
x ^ y = y ^ x
从a经b绕到c, 要比直接从a到c距离长:
a ^b + b ^ c >= a ^ c
下面两个是资料上提到的,似乎很重要,但我不大理解他们的含义:
a + b >= a ^ b
(a ^ b) ^ (b ^ c) = a ^ c

在Kademlia中,异或(距离)算法具有单向性(或者说一一对应关系),即给定一个节点和一个距离,必定存在唯一一个相对应节点。包括距离算法在内的,Kademlia中大部分的概念,都既有算术上的意义,又可以在节点树上表现实际意义。

事实上,节点间距离反映的就是节点ID中比特的差异情况,而且越靠前的比特权值越大。或者说是反映节点在树中相隔了多少个分支,需要向上多少个树节点才能找到共同的祖先节点。

Kademlia中使用了名为K-桶的概念来储存其他(临近)节点的状态信息,这里的状态信息主要指的就是节点ID, IP, 和端口。

对于160bit的节点ID, 就有160个K-桶,对于每一个K-桶i, 它会储存与自己距离在区间 [2^i, 2^(i+1)) 范围内的节点的信息,每个K-桶中储存有k个其他节点的信息,在BitTorrent的实现中,k的取值为8.

下表反映了每个K-桶所储存的信息











K-桶储存的距离区间储存的距离范围储存比率
0[20, 21)1100%
1[21, 22)2-3100%
2[22, 23)4-7100%
3[23, 24)8-15100%
4[24, 25)16-3175%
5[25, 26)32-6357%
10[210, 211)1024-204713%
i[2i, 2i+1)/0.75i-3

放在节点树上,即每个节点都更倾向于储存与自己距离近的节点的信息,形成 储存的离自己近的节点多, 储存离自己远的节点少 的局面。

从上表可以看出,在1-15这个范围内的节点,只要发现,就会被100%地储存下来,而离自己距离在1000左右的节点,只会储存13%.

对于一个节点而言,K-桶就代表着节点树上那些未知的节点(其实除了自己都是未知的)构成的子树,160个K桶分别是具有1到160层的子树,由小至大。对于节点ID, 160个K-桶分别储存着节点ID前0到159个bit和自己一致的节点。

K-桶中的条目(其他临近节点的状态信息)排序的,每当收到一个消息(如查询)时,就要更新一次K桶。

首先计算自己与对方的距离,然后储存到对应的K-桶中,但如果K-桶已满(前面提到每个K-桶储存有k=8个条目), 则会倾向放弃储存,继续保持旧的节点信息(如果还有效的话). 除了距离外,Kademlia更倾向于与在线时间长,稳定的节点建立联系。

这是因为实践证明,累积在线时间越长的节点越稳定,越倾向于继续保持在线,即节点的失效概率和在线时长成反比。

这样还可以在一定程度上抵御攻击行为。因为当大量恶意的新节点涌入时,大家都会选择继续保持旧的节点信息,而不是接受新的。

除此之外,还需要定时检查K-桶中的节点是否任然在线,及时删去已失效节点。

Kademlia协议仅定义了四种操作:

  • PING: 探测一个节点是否在线
  • STORE: 令对方储存一份数据
  • FIND NODE: 根据节点ID查找一个节点
  • FIND VALUE: 根据键查找一个值(数据)

当查找一个节点时,首先计算自己与目标节点的距离d, 然后将 log2d 向下取整,找到对应的K-桶,从这个K-桶中选取a个节点(在BitTorrent的实现中取值为3), 向它们发送查询。

收到查询的节点同样计算距离后从自己的对应K-桶中选取a个节点返回给查询者。查询者不断重复这个过程,知道找到目标节点,或无法再找到更近的结果。

很多资料将这个过程描述成是递归的,但我觉得这里认为它是迭代的更为恰当。

因为每个节点都更倾向于储存距自己近的节点的信息,而整个网络又是一个二叉树,因此每次查询都会至少取得距离减半的结果,对于有N个节点的网络,至多只需要 log2N 次查询。

当进行 FIND VALUE 操作时,查询操作是类型的,每份数据都有一个同样是160bit的键,每份数据都倾向于储存在与键值距离较近的节点上。

当上传者上传一份数据时,上传者首先定位几个较为接近键值的节点,用STORE操作要求他们储存这份数据。

储存有数据的节点,每当发现比自己与键值距离更为接近的节点时,便将数据复制一份到这个节点上。

当一个新节点欲加入网络时,只需找到一个已在网络中的节点,借助它对自己的节点ID进行一次常规查询即可,这样便完成了对自己信息的广播,让距自己较近的节点获知自己的存在。而离开网络不必执行任何操作,一段时间后,你的信息会自动地从其他节点被删除。

毫无疑问,Kademlia要比我之前为零毫秒设想的网络模型优秀得多,更为彻底地实现了去中心化,弱化了关键节点失效对整个网络的影响。而电驴和BitTorrent的实践也证明了kademlia是具有相当的可行性的。

Kademlia的精妙之处在于它选择了异或运算作为计算距离的依据,异或运算不仅具有算术的意义,在二叉树式的网络模型中,同样具有实际意义,同时任何情况下都在强调距离的概念,让节点间通过距离来聚合起来。

在上一篇日志的末尾,我便在思考如何来聚合节点,现在通过Kademlia, 我算是找到了。下一步我想思考的是,既然以上是Kademlia的优势,那么它的弱势在哪?哪些地方存在不足?

精子生于 1995.11.25, 21 岁,英文 ID jysperm.

订阅推送

通过邮件订阅精子的博客日志、产品和项目的最新动态,精子承诺每一封邮件都会认真撰写(历史邮件),有想和精子说的话也可以直接回复邮件。

该博客使用基于  Hexo  的  simpleblock  主题。博客内容使用  CC BY-NC-SA 3.0  授权发布。最后生成于 2017-04-09.