SVF——C/C++指针分析/(数据)依赖分析框架

大家好，欢迎来到IT知识分享网。

请查看我的讲解视频以及ppt：

讲解视频：程序依赖图分析-SVF
ppt：程序依赖图——以SVF为例.pdf

这篇文章包括：

SVF介绍

SVF源码解读

SVF优势与不足

如何扩展改进

文章包括一些个人观点，若觉得有误请留言纠正，感谢🙏

在这篇文章之前强烈推荐看我公众号之前推的一篇文章：CG0’2011 “Flow-sensitive pointer analysis for millions of lines of code”

1. SVF简介

静态值流分析（Static Value Flow Analysis）：静态地识别程序的控制依赖，数据依赖。例如“程序点A的信息是否能沿着某些程序路径流到程序点B”，“是否存在触发bug的不安全的内存访问”。（刚开始可以，简单地看成Def-Use或者数据依赖分析即可）

变量的值流。LLVM中存在两类变量：

未被取过地址的变量（top-level pointer），这类变量在LLVM IR中是register value，显式地编码为SSA形式。
被取过地址的变量（address-token variable），LLVM IR中是allocated memory objects，比较难去精确地计算这些内存变量的Def-Use关系。

2. 参考资料

FSE‘2003 Tracking pointers with path and context sensitivity for bug detection in C programs 中提出的IPSSA，利用它检测外部输入(fgets)导致的缓冲区溢出。
PLDI’2007 Practical Memory Leak Detection using Guarded Value-Flow Analysis检测内存泄漏，只能够处理top-level变量的Def-Use，利用SAT求解器消除部分误报。
CG0’2011 “Flow-sensitive pointer analysis for millions of lines of code”。SVF的整个指针分析框架（Memory SSA构造）参考。
ISSTA’2012“Static Memory Leak Detection Using Full-Sparse Value-Flow Analysis”，SVF的原始论文。

注解：

(1) 实际上最早03年斯坦福提出的IPSSA就已经解决了这类针对top-level和address-token变量的Def-Use关系的建模，并形成工具。
(2) 07年是FastCheck利用SAT求解器消除一些误报，不过FastCheck不能处理address-token变量
(3) SVF (Saber) 相当于把(1)和(2)的工作结合了，不过SVF最初的SAT求解使用BDD编码的，最新的版本是用Z3编码SAT公式。

3. SVF框架

(1) LLVM IR前端。Clang编译程序为LLVM IR，可使用wllvm之类的工具将bitcode链接合并，以实现全程序的符号表构建。

(4) 供上层客户端使用。

4. 运行案例

4.1 Swap例子

通过一个完整的小例子简单介绍一下SVF中间的IR。

(1) 编译LLVM IR

clang -S -c -Xclang -o0 -g -fno-discard-value-names -emit-llvm swap.c -o swap.ll opt -S -mem2reg swap.ll -o swap.ll

(2) 查看生成的Memory SSA

wpa -ander -svfg -stat=false -dump-mssa swap.ll >> swap_ssa.txt

(3) 生成SVFG，dot调试查看

wpa -ander -svfg -dump-vfg swap.ll

其中，SVF节点

SVFStmt
- 绿色方框是AddrStmt，红色是LoadStmt，蓝色是StoreStmt，黑色是CopyStmt，紫色是GepStmt，灰色是单目双目运算操作CmpStmt，BinaryOpStmt，UnaryOpStmt。绿色是Fork/Join。
Parameter。黄色方框表示参数。
memory region。黄色方框。函数entry/exit或者调用点/load/store处的memory region。虚线黑边为参数传递，点线黑边为函数返回值。

(4) 查看Andersen流不敏感指针分析的约束图（参考SVF_EUROLLVM2016 page 8/26）

wpa -nander -dump-pag -dump-constraint-graph -brief-constraint-graph=false swap.ll

4.2 CWE程序MemoryLeak

目的：主要观察SVF对全局变量的处理，以及路径敏感分析的能力。我们已知，SVF/Saber的路径敏感分析能力是SAT逻辑求解，所以能力仍然不够，这里通过一个例子来演示。

Juliet CWE的内存泄漏的一个刁钻例子，这个例子主要是有全局变量作为分支条件。

#include <stdlib.h> #include <string.h> static int static_t = 1; /* true */ static int static_f = 0; /* false */ void CWE401_Memory_Leak__char_malloc_05_bad() { 
     char * data; data = NULL; if(static_t) { 
     /* POTENTIAL FLAW: Allocate memory on the heap */ data = (char *)malloc(100*sizeof(char)); /* Initialize and make use of data */ strcpy(data, "A String"); } else { 
     /* INCIDENTAL: CWE 561 Dead Code, the code below will never run */ /* FIX: Use memory allocated on the stack with ALLOCA */ data = (char *)malloc(100*sizeof(char)); /* Initialize and make use of data */ strcpy(data, "A String"); } if(static_t) { 
     /* POTENTIAL FLAW: No deallocation */ ; /* empty statement needed for some flow variants */ } else { 
     /* INCIDENTAL: CWE 561 Dead Code, the code below will never run */ /* FIX: Deallocate memory */ free(data); } } static void goodB2G1() { 
     char * data; data = NULL; if(static_t) { 
     /* POTENTIAL FLAW: Allocate memory on the heap */ data = (char *)malloc(100*sizeof(char)); /* Initialize and make use of data */ strcpy(data, "A String"); } else { 
     /* INCIDENTAL: CWE 561 Dead Code, the code below will never run */ /* FIX: Use memory allocated on the stack with ALLOCA */ data = (char *)malloc(100*sizeof(char)); /* Initialize and make use of data */ strcpy(data, "A String"); } if(static_f) { 
     /* INCIDENTAL: CWE 561 Dead Code, the code below will never run */ /* POTENTIAL FLAW: No deallocation */ ; /* empty statement needed for some flow variants */ } else { 
     /* FIX: Deallocate memory */ free(data); } } static void goodB2G2() { 
     char * data; data = NULL; if(static_t) { 
     /* POTENTIAL FLAW: Allocate memory on the heap */ data = (char *)malloc(100*sizeof(char)); /* Initialize and make use of data */ strcpy(data, "A String"); } else { 
     /* INCIDENTAL: CWE 561 Dead Code, the code below will never run */ /* FIX: Use memory allocated on the stack with ALLOCA */ data = (char *)malloc(100*sizeof(char)); /* Initialize and make use of data */ strcpy(data, "A String"); } if(static_t) { 
     /* FIX: Deallocate memory */ free(data); } else { 
     /* INCIDENTAL: CWE 561 Dead Code, the code below will never run */ /* POTENTIAL FLAW: No deallocation */ ; /* empty statement needed for some flow variants */ } } static void goodG2B1() { 
     char * data; data = NULL; if(static_f) { 
     /* INCIDENTAL: CWE 561 Dead Code, the code below will never run */ /* POTENTIAL FLAW: Allocate memory on the heap */ data = (char *)malloc(100*sizeof(char)); /* Initialize and make use of data */ strcpy(data, "A String"); } else { 
     /* FIX: Use memory allocated on the stack with ALLOCA */ data = (char *)malloc(100*sizeof(char)); /* Initialize and make use of data */ strcpy(data, "A String"); } if(static_t) { 
     /* POTENTIAL FLAW: No deallocation */ ; /* empty statement needed for some flow variants */ } else { 
     /* INCIDENTAL: CWE 561 Dead Code, the code below will never run */ /* FIX: Deallocate memory */ free(data); } } static void goodG2B2() { 
     char * data; data = NULL; if(static_t) { 
     /* FIX: Use memory allocated on the stack with ALLOCA */ data = (char *)malloc(100*sizeof(char)); /* Initialize and make use of data */ strcpy(data, "A String"); } else { 
     /* INCIDENTAL: CWE 561 Dead Code, the code below will never run */ /* POTENTIAL FLAW: Allocate memory on the heap */ data = (char *)malloc(100*sizeof(char)); /* Initialize and make use of data */ strcpy(data, "A String"); } if(static_t) { 
     /* POTENTIAL FLAW: No deallocation */ ; /* empty statement needed for some flow variants */ } else { 
     /* INCIDENTAL: CWE 561 Dead Code, the code below will never run */ /* FIX: Deallocate memory */ free(data); } } void CWE401_Memory_Leak__char_malloc_05_good() { 
     goodB2G1(); goodB2G2(); goodG2B1(); goodG2B2(); } int main(int argc, char * argv[]) { 
     CWE401_Memory_Leak__char_malloc_05_good(); CWE401_Memory_Leak__char_malloc_05_bad(); return 0; }

(1) 编译

clang -S -c -Xclang -o0 -g -fno-discard-value-names -emit-llvm malloc.c -o malloc.ll opt -S -mem2reg malloc.ll -o malloc.ll

(2) 检测内存泄漏

saber -leak -stat=false malloc.ll

报告5个，误报4个。分析原因：5个case每个case中都存在全局变量作为分支条件，但是SVF利用SAT求解器没有对全局变量进行跨函数整数等式逻辑的处理，具体查看IR:
下面是goodG2B1函数的LLVM IR：

下面是Memory SSA：

wpa -ander -svfg -dump-mssa -stat=false malloc.ll >> malloc_mssa.txt

查看SVFG：

wpa -ander -svfg -dump-vfg malloc.ll

从图中可以看到，全局变量是全部考虑进来的(actual -> formal)，并不是误报的原因。下面分析误报原因，分析方法为调试跟踪SVF的Saber运行源代码。

Saber在作污点分析的时候：

如果追踪污点时，污点流进全局变量，那么不继续追踪。这个跟误报原因无关，本cwe的例子是条件约束是全局变量。
约束求解。
- 实际上就是SAT求解（可参考FastCheck，最初Saber使用BDD进行SAT公式化简与编码）。
  
  可以看到，约束求解条件生成部分都是SAT公式（布尔变量），并不会考虑条件变量的数据依赖以形成整型等式公式（整数算数理论，BitVector）。
  
  其中newCond为每条if条件跳转命名一些布尔变量（fresh bool variable）。

4.3 嵌入式C程序代码片段

场景：局部循环导致越界，全局数组元素变量作为整个循环的路径条件判断。

这里主要查看SVF如何对这样的嵌入式代码片段建模的（实际上SVF并不能检测越界问题）

typedef unsigned int uint_32; uint_32 SPIZL_buffer[10][4]; uint_32 control_data[10]; #define CD_SPIYC_FLAG 0 #define CD_SPIZL_T1 1 #define CD_SPI_phead 3 #define CD_SPI_ptail 9 #define C_SPI_BUFFER_LENGTH 10 void Proc_process_Buffer_SPI() { 
     uint_32 tempi, SPIbufdata[5]; if ((0x00 == control_data[1]) && (0x00 == control_data[0])) { 
     if (control_data[3] != control_data[9]) { 
     if (0x == (SPIZL_buffer[control_data[9]][0] & 0xFF000000)) { 
     for (tempi = 0 ; tempi < 5 ; tempi++) { 
     SPIbufdata[tempi] = SPIZL_buffer[control_data[9]][tempi]; // Overflow } } SPIZL_buffer[control_data[9]][0] = 0x00; control_data[9] = (control_data[9] + 1) % 10; } } }

(1) 编译生成IR

clang -S -c -Xclang -o0 -g -fno-discard-value-names -emit-llvm case.c -o case.ll opt -S -mem2reg case.ll -o case.ll

(2) 生成MemorySSA以及构造SVFG

wpa -ander -svfg -dump-mssa -stat=false case.ll >> case_mssa.txt wpa -ander -svfg -dump-vfg case.ll dot -Tpng -o svfg_final.svg svfg_final.dot

生成的IR如下：

生成的MemorySSA如下：

生成SVFG如下：

下面是control_data[]的局部数据依赖关系图：

下面是SPIZL_buffer[

][]的局部数据依赖图：

下面是SPIbufdata[

]的局部数据依赖图：

4.4 简单的指针分析测试

应用场景：分析指针是否越界，但是指针是通过数组传入成为函数的参数的，静态无法直接知道它的大小，通过指针分析就可以知道。

被测程序：

#include <stdlib.h> typedef double float64; typedef struct _SQuater { 
     float64 arr[4]; } SQuater; void foo4(float64 *pQ) { 
     pQ[4] = 0; } void foo5(SQuater *pQ) { 
     pQ->arr[4] = 0; } int bar4() { 
     float64 arr[4]; foo4(arr); SQuater *p = (SQuater *)malloc(sizeof(SQuater)); foo5(p); }

编译生成LLVM IR，生成Memory SSA，SVFG

clang -S -c -Xclang -o0 -g -fno-discard-value-names -emit-llvm case.c -o case.ll opt -S -mem2reg case.ll -o case.ll wpa -ander -svfg -dump-mssa -stat=false case.ll >> case_mssa.txt wpa -ander -svfg -dump-vfg case.ll

5. SVF源码解读

5.1 SVF中图概览

SVF中存在几种图：

(1) PAG。Program Assignment Graph程序赋值图。SVF中的核心IR。可惜它是流不敏感的，上下文不敏感的。它的存在只是为了方便构造Memory SSA时，进行指针分析预分析。

 它是用来初始化Andersen式指针分析，描述初始状态下指针变量间的集合包含关系的。

(2) Constraint Graph。指针分析约束图。指针分析初始状态下，它就是PAG的一份copy，随着Andersen指针分析的迭代，会在该图上添加约束边。

(3) Call Graph。调用图，最基础的图，可直接复用。

(4) ICFG。Inter-procedural Control Flow Graph。函数间控制流图，对LLVM IR指令进行了封装。可方便地用它进行对LLVM IR分析的二次开发。

(5) SVFG。SVFG的构造严格按照3个步骤完成：① 流不敏感指针分析 ② 插入Mu/Chi ③ Full SSA构造 ④ 连接函数间Def-Use，形成SVFG

5.2 Program Assignment Graph (PAG)

SVF源码中SVFIR数据结构，就是PAG。SVF输入LLVM IR后，最初建立的图结构就是SVFIR，也叫PAG。PAG的设计就是给后续执行Andersen式的flow-,context-insensitive指针分析作准备的。所以不能够直接在SVFIR上作flow-,context-sensitive指针分析，因为它的图结构就是流不敏感，上下文不敏感的。

LLVM IR输入SVF后，转换为PAG。其中 ①节点为指针变量，或者抽象对象(alloca,malloc等)。②边表示指针变量之间的关系。

SVF中是这么定义PAG上的节点和边的：①typedef SVFVar PAGNode ②typedef SVFStmt PAGEdge。可以看到，节点就是变量，边就是被封装好的LLVM IR指令。

边的类型	指令	连边
Address边	p = alloca_i	alloca_i $\stackrel{Addr}{\longrightarrow}$ p
Copy边	p = q	q $\stackrel{Copy}{\longrightarrow}$ p
Load边	p = *q	q $\stackrel{Load}{\longrightarrow}$ p
Store边	*p = q	q $\stackrel{Store}{\longrightarrow}$ p
Field边	p = q gep f	q $\stackrel{.f}{\longrightarrow}$ p

5.3 ConstraintGraph

Constraint Graph为Andersen指针分析约束图。指针分析的初始状态时，Constraint Graph为PAG的一份拷贝，然后根据Andersen指针分析的传播规则，沿着Constraint Graph的边不断迭代地传播指向信息，在这个迭代的过程中可能在Constraint Graph上引入新的节点和边。

5.3 Inter-procedural Control Flow Graph

AssignStmt
- AddrStmt: lhs = &rhs
- CallPE: lhs = call_fun (arg1, arg2, …)
- CopyStmt: lhs = rhs
- GepStmt: lhs = rhs -> field1 -> field2
- LoadStmt: lhs = *rhs
- StoreStmt: *lhs = rhs
- RetPE: return ®?
- TDForkStmt: fork()
- TDJoinStmt: join()
MultiOpndStmt
- BinaryOpStmt: lhs = a op b
- CmpStmt: lhs = a cmp b
- PhiStmt: lhs = phi (op1, op2, …)
- SelectStmt: lhs = c ? rhs1 : rhs2
BranchStmt: if语句或者switch语句
- switch/if (cond):
  case a1: goto label1
  case a2; goto label2
  …
UnaryOpStmt: lhs = op rhs
SVF指令中变量为SVFVar，它同时又是PAG中的节点，所以它有一个唯一节点ID，有前驱/后继边（PAGEdge）表示与它相关的语句（PAGEdge，SVFStmt）。
它的子类如下：
DummyObjVar
DummyValVar
FIObjVar。o.*，字段不敏感时生成
ObjVar: 抽象对象
- MemObj。alloca, malloc等。
- GepObjVar。o->field，表示MemObj的一个字段
ValVar: 指针变量
- GepValVar。var->field，表示指针变量的一个字段
RetPN: 返回值变量

5.3 Sparse Value-Flow Graph

6. 扩展点

6.1. 流敏感指针分析

SVF自带的流敏感指针分析实现。①在PAG上构造Constraint Graph执行预分析，flow-,context-insensitive Andersen式全程序指针分析AndersenWaveDiff。②利用已有全程序指针分析结果对程序划分内存 ③构造Full SSA，连接全程序函数间Def-Use形成SVFG ④在稀疏图上执行稀疏指针分析，该指针分析是流敏感的。

可以看到在PAG IR上不能直接作流敏感指针分析，也不能作单函数模块化指针分析。SVF的框架要求它先构造全程序Memory SSA，SVFG，然后在SVFG上执行稀疏的流敏感指针分析。

所以，我们的任务是作模块化的，单函数流敏感的指针分析，不能在PAG/SVFIR上作，因为它是全程序的，flow-,context-insensitive的。于是得在SVF封装的Interprocedural Control Flow Graph (ICFG)上自己重新实现一套。

7. 总结

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/119855.html