成都旅游的网站建设,wordpress注册白屏,网站建设的优缺点,中国学校网站前台模板本文于 2007 年投稿于 ACM-SIGPLAN 会议1。
概述
指针在代码编写过程中可能出现以下两种问题#xff1a; 存在一条执行路径#xff0c;指针未成功释放#xff08;内存泄漏#xff09;#xff0c;如下面代码中注释部分所表明的#xff1a; int foo()
{int *p malloc(4 …本文于 2007 年投稿于 ACM-SIGPLAN 会议1。
概述
指针在代码编写过程中可能出现以下两种问题 存在一条执行路径指针未成功释放内存泄漏如下面代码中注释部分所表明的 int foo()
{int *p malloc(4 * sizeof(int));if (p NULL)return -1;int *q malloc(4 * sizeof(int));if (q NULL)return -1; // 注意这里q为NULL时p一定不为NULL但是函数直接返回导致p所指向的区域未释放// some code to executefree(p);free(q);return 0;
}存在一条执行路径指针被重复释放未定义行为如 free 一个空指针。 int *p (int *)malloc(4 * sizeof(int));int *q p;free(q);q p;free(q);最笨拙的方法是枚举每一条可能的路径依次判断。但是这显然是不切实际的。因而本文的主要工作是提出一个能够发现未释放指针或重复释放指针的高效算法并进行了代码实现提示编写者具体可能的错误原因。即给定一个程序找到其中可能存在的这种问题。
首先进行控制流图Condition-Flow GraphCFG的约定
赋值运算节点 e e ′ ee ee′。函数调用 e f ( p 1 , p 2 , ⋯ , p m ) ef(p_1,p_2,\cdots,p_m) ef(p1,p2,⋯,pm)。返回 return e \texttt{return}\ e return e。分支节点 switch e ( c 1 , n 1 ; c 2 , n 2 ; ⋯ ; c k , n k ; n t ) \texttt{switch}_e(c_1,n_1;c_2,n_2;\cdots;c_k,n_k;n_t) switche(c1,n1;c2,n2;⋯;ck,nk;nt)。即一个节点根据表达式 e e e 的值不同可以有 k 1 k1 k1 个分支跳转地址分别记作 I n { n 1 , n 2 , ⋯ , n k , n t } I_n\{n_1,n_2,\cdots,n_k,n_t\} In{n1,n2,⋯,nk,nt}最后一个为默认跳转地址。
此外本文将问题进行了规约定义 s o u r c e − s i n k [ n , m ] {\rm source-sink}[n,m] source−sink[n,m] 问题为从 s r c \rm src src 会流入到 [ n , m ] [n,m] [n,m] 个 s i n k \rm sink sink 的条件可满足性问题。对于未释放则是 s o u r c e − s i n k [ 0 , 0 ] {\rm source-sink}[0,0] source−sink[0,0] 问题而多次释放则是 s o u r c e − s i n k [ 2 , ∞ ] {\rm source-sink}[2,\infty] source−sink[2,∞] 问题而合法性判断是 s o u r c e − s i n k [ 1 , 1 ] {\rm source-sink}[1,1] source−sink[1,1] 问题。
算法流程
整体算法流程图如下所示 利用编译器前端搭建 CFG。到达定值点分析值流图构建无条件可达性分析即不考虑具体控制流图上条件进行的分析条件可达性分析即考虑控制流图上条件进行的分析。
在实现该算法的同时还需要调用
指针区域分析即分析流图中每个指针所指向的内存区域。条件分析。SAT可满足性问题解决器即给定一组条件约束返回一组可满足所有条件的初始值或报告无解。下文会将本论文中提出的问题规约到可满足性问题。
到达-定值分析Reaching-Definition Analysis
编译原理中经典的数据流分析方法。下文中用 p d o m ( x , n , m ) pdom(x,n,m) pdom(x,n,m) 来描述变量 x x x 能不能从 CFG 上流图节点 n n n 值不发生改变的到节点 m m m。论文中的 S S S 仅为一个记忆化的集合不做具体参数使用。 p d o m pdom pdom 的计算使用逆向数据流分析方法 p d o m ( x , n , m ) { t r u e , m n f a l s e , n 没有出边返回节点 ⋀ i ∈ I n p d o m ( x , i , m ) ∧ ¬ d e f i n e ( x , i ) , 其他情况 pdom(x,n,m) \begin{cases} true, mn\\ false,\text{$n$ 没有出边返回节点}\\ \bigwedge_{i \in I_n} pdom(x,i,m) \wedge ^\lnot{define}(x,i),\text{其他情况} \end{cases} pdom(x,n,m)⎩ ⎨ ⎧true,mnfalse,n 没有出边返回节点⋀i∈Inpdom(x,i,m)∧¬define(x,i),其他情况 其中 d e f i n e ( x , i ) define(x,i) define(x,i) 表示 i i i 节点没有进行对变量 x x x 的赋值操作。
构建值流图Value-Flow Graph
在构建值流图之前首先需要介绍 free 函数的工作原理或特性。它释放传入参数给定的指针所指向的区域也就是说它是针对内存区域而非指针的。例如下面的两个例子
下面代码中 p1 和 p2 指针所指向的区域都被释放了。 int *p1 malloc(4 * sizeof(int)), *p2 malloc(6 * sizeof(int));int *q p1;free(q);q p2;free(q);下面代码中 p 指针指向区域并未完全释放——p 指针所指向的区域仍有一个 int 大小的空间未释放。 int *p malloc(4 * sizeof(int));int *q p 1;free(q);基于以上两个特性构建如下的节点 赋值运算节点。针对 CFG 上每个形如 x y xy xy 形式的赋值语句都对应一个 VFG 的节点。 内存区域节点。由于 free 是针对区域而非指针型变量因而需要用一个单独的节点描述它是否有被释放的途径。该部分节点用 n r n_r nr 表示可以使用这篇论文2中的方法快速描述代码中每个指针可能对应的内存区域集合。 这里还需要注意的是由于指针存在加减法操作因而这里需要额外使用一个偏移量来去衡量该内存地址的具体使用情况。 释放节点。每个 free 函数调用的节点都对应一个 VFG 上的汇sink点。 函数调用实参节点。由于进行函数调用可以视为进行一次变量的值使用记为 x n x_{}n xn。 函数调用形参节点。在被调用函数callee中该函数作为新变量使用同时它对应于调用函数caller的一个变量。为避免函数多次调用导致边关系混乱因而新建一个形参节点以解决图过于混乱的问题记为 [ p ] [p] [p]。 函数返回节点。函数的返回值可能在 caller 中作为一个新变量继续存在并涉及后续赋值和计算。
遍历 CFG按如下规则建图假设当前节点为 n n n
赋值语句 y x yx yx、释放节点 f r e e ( x ) free(x) free(x)、返回节点 r e t u r n ( x ) return(x) return(x)将所有 x x x 的定值点集合 n x n_x nx 建立一条边连到 n n n 节点。 y f ( x 1 , x 2 , ⋯ , x m ) yf(x_1,x_2,\cdots,x_m) yf(x1,x2,⋯,xm)对于每个函数实参 x i x_i xi首先将 x i x_i xi 的定值点集合连接一条边到对应的实参节点 n x i → x i n n_{x_i} \to {x_i}_n nxi→xin然后每个实参节点连接到形参节点 x i n → p i {x_i}_{}n \to p_i xin→pi最后将 callee 函数的返回节点 n r e t f n_{\rm ret}^f nretf 连接到当前函数调用节点该语句可以视为一种特殊类型的赋值语句 n r e t f → n n_{\rm ret}^f \to n nretf→n。对于赋值变量中 x x x 或 y y y 不是一个有效节点的如 malloc 函数返回的堆区域指针调用内存区域查询函数返回对应的内存区域节点。
无条件可达性分析Unguarded Reachability Detection
该步骤中忽略了程序流图中的条件即认为所有的边都是可走到的在这种情况下先简单分析是否每个 malloc 函数都有至少一个 free 与之对应。
枚举一个起始点 s r c src src首先找到 VFG 顺向流图中可到达节点集合 F s r c F_{src} Fsrc找到 F s r c F_{src} Fsrc 中所有的 free 语句对应节点记为 K K K。分类讨论 如果 K K K 为空则该 malloc 语句无对应 free 语句直接报告内存泄漏。如果从该 s r c src src 节点可以到达一个内存区域节点则说明该代码片段中存在全局变量暂时不继续分析该代码的内存泄漏问题直接退出。找到能从 s r c src src 到并且能到达 K K K 的集合 R R R并将 R R R 集合传递到下一步继续分析。
条件可达性分析Guarded Reachability Detection
预处理
首先在 CFG 上进行条件分析。考虑每个分支节点 n n n 需要满足其分支出口唯一即对于分支节点 n n n switch e ( c 1 , n 1 ; c 2 , n 2 ; c k , n k ; n t ) \texttt{switch}_e(c_1,n_1;c_2,n_2;c_k,n_k;n_t) switche(c1,n1;c2,n2;ck,nk;nt)需要满足 C n [ ⋁ i ( e c i ) n ] ∧ [ ⋀ i ≠ j ( e c i ) n ∧ ( e c j ) n ‾ ] C_n\left [\bigvee_{i}(ec_i)_n\right] \wedge \left[\bigwedge_{i \ne j} \overline{(ec_i)_n \wedge (ec_j)_n}\right] Cn[i⋁(eci)n]∧ ij⋀(eci)n∧(ecj)n 即存在一条出路且不存在一个条件同时满足两条出路。
定义函数 c g ( x , n , m ) cg(x,n,m) cg(x,n,m)下简写成 c g u a r d ( n → m ) cguard(n \to m) cguard(n→m)其中程序点 n n n 为形如 x e xe xe 的赋值语句表示变量 x x x 从程序点 n n n 到 m m m 需要满足的输入条件集合有如下递推 c g ( x , n , m , E ) { t r u e , 如果满足支配关系即 p d o m ( x , n , m ) c g ( x , n 1 , m , E ) , n 处无分支 n 1 为 n 语句的唯一后续语句 ⋁ i ∈ I n , x , E c o n d ( n , n i , E ) ∧ c g ( x , n i , m , E ∪ { ⟨ n , n i ⟩ } ) , 其他情况 cg(x,n,m,E) \begin{cases} true,\texttt{如果满足支配关系即 $pdom(x,n,m)$}\\ cg(x,n_1,m,E),\texttt{$n$ 处无分支$n_1$ 为 $n$ 语句的唯一后续语句}\\ \bigvee_{i \in I_{n,x,E}} cond(n,n_i,E) \wedge cg(x,n_i,m,E \cup \{\langle n,n_i\rangle\}),\texttt{其他情况} \end{cases} cg(x,n,m,E)⎩ ⎨ ⎧true,如果满足支配关系即 pdom(x,n,m)cg(x,n1,m,E),n 处无分支n1 为 n 语句的唯一后续语句⋁i∈In,x,Econd(n,ni,E)∧cg(x,ni,m,E∪{⟨n,ni⟩}),其他情况 其中 I n , x , E I_{n,x,E} In,x,E 表示满足后续节点不是形如 d e f i n e ( n i , x ) define(n_i,x) define(ni,x) 且 ⟨ n , n i ⟩ \langle n,n_i \rangle ⟨n,ni⟩ 不在 E E E 中的后续节点集合 { n i } \{n_i\} {ni}。 c o n d ( n , n i , E ) cond(n,n_i,E) cond(n,ni,E) 函数表示从 n n n 节点走到 n i n_i ni 节点所需要满足的条件并且要求 n n n 节点后续不能有 E E E 中的边 c o n d ( n , n i , E ) { ( e c i ) n , n 是一个分支节点且 n 的后续集合不在 E 集合中 t r u e , 其他情况 cond(n,n_i,E) \begin{cases} (ec_i)_n,\texttt{$n$ 是一个分支节点且 $n$ 的后续集合不在 $E$ 集合中}\\ true,\texttt{其他情况}\\ \end{cases} cond(n,ni,E){(eci)n,n 是一个分支节点且 n 的后续集合不在 E 集合中true,其他情况 这里 ( e c i ) n (ec_i)_n (eci)n 表示在程序分支判断点 n n n 处进行条件判断 e c i ec_i eci。
这里加入 E E E 集合已遍历的边集合作为参数是方便代码实现上的由于流图中可能有环存在因而不能重复遍历同一条边通过在状态中多维护一个 E E E 集合可以有效防止重复遍历到同一条边。在 c o n d cond cond 中显然要进入循环然后退出该循环需要同时满足在循环的出口判断中 e c i ec_i eci 和 e ≠ c i e \ne c_i eci这显然是永假的。因而这里加入了边的限制条件以防止上述情况的出现。当然这里会存在一个小漏洞就是仅判断了循环入口点的条件未判断出口点的。这里会对未释放问题的判定产生一定的影响但是对多重释放不会。
接下来就是考虑利用这些条件在 VFG 上进行条件判断。同样定义 v g u a r d ( n , m ) v g ( n , m ) vguard(n,m)vg(n,m) vguard(n,m)vg(n,m) 函数表示从 VFG 图上 n n n 节点走到 m m m 的约束条件集合有 v g ( n , m , E ) { t r u e , n m ⋁ n → n ′ ∈ E c g u a r d ( n → n ′ ) ∪ v g ( n ′ , m , E ∪ { n → n ′ } ) , 其他情况 vg(n,m,E) \begin{cases} true,nm\\ \bigvee_{n \to n \in E} cguard(n \to n) \cup vg(n,m,E \cup \{n \to n\}),\texttt{其他情况} \end{cases} vg(n,m,E){true,nm⋁n→n′∈Ecguard(n→n′)∪vg(n′,m,E∪{n→n′}),其他情况 和在 CFG 上的情况类似这里只需要在 VFG 图上再加入 CFG 上的信息即可。
分析过程
考虑对于一个确定的 s r c src src 节点和所有该指针的释放操作汇点 K K K在 2.3 节中阐述的 R R R 集合上进行分析。定义 G k v g u a r d ( s r c , k ) G_kvguard(src,k) Gkvguard(src,k) C C C 为 R R R 上所有的分支节点需要满足的 C n C_n Cn 的与集合。此时就满足了一个 SAT 问题的框架
如果此处存在一组初值指派满足 ∨ k ∈ K G k ‾ ∧ C \overline{\vee_{k \in K} {G_k}} \wedge C ∨k∈KGk∧C则表明存在某种初值指派使得从该 s r c src src 语句无法走到任何一个汇点即发生了内存泄漏。如果存在一组初值指派满足 ∃ i ≠ j , G i ∧ G j ∧ C \exists i \ne j,G_i \wedge G_j \wedge C ∃ij,Gi∧Gj∧C则表明某组初值指派可以到达两个不同的 free 语句进行多次释放操作因而发生未定义行为Undefined Behavior。
可以注意到上述的操作时间复杂度是比较高的特别是对于有大量 malloc 语句存在的时候。因而本文中仅对操作数不超过阈值 30 30 30 的代码进行分析。
本文同时实现了代码将所有的错误种类分成以下几类
从未释放。又分为a指针作为局部变量在 main 函数或其他函数未释放b指针作为全局变量或存在于数组等结构中未释放。释放。又分为a一切条件下都能释放b某些情况下能释放有些情况未释放。不能判定认为释放了。这种情况通常因为分析语句过多导致超过阈值停止分析。 Cherem S, Princehouse L, Rugina R. Practical memory leak detection using guarded value-flow analysis[C]//Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation. 2007: 480-491. ↩︎ Bjarne Steensgaard. Points-to analysis in almost linear time. In Proceedings of the ACM Symposium on the Principles of Programming Languages, St. Petersburg Beach, FL, January 1996. ↩︎
