跳到主要内容

技术研究：IRify 中 C 语言指针的 SSA 处理方案

· 阅读需 7 分钟
Yak Project
Yak Project
网络安全垂直语言团队

目前 IRify 已经支持 C 语言了，说起 C 语言那绕不开的点就是指针了。

IRify 最初的指针设计​

在 SSA 中，指针处理是一个很麻烦的点。

指针最关键的特性是读写指针时需要影响其指向的内容。最初的实现方案是使用别名表：

1、读指针：遇到 *(valueName) 时先在当前作用域的别名表中查找替换

2、写指针：遇到 &(valueName) 时更新别名表内容

a := 10
p := &a  // *p和a建立别名关系
*p = 20  // 通过指针修改a的值

由于对于每个块作用域都需要一个别名表来管理指针。

别名表浪费了大量空间，干脆将指针改为了一种特殊的 value（PointValue）并复用现有的 ScopedVersionedTable 来管理指针。

  • 遇到 & 时就会生成一个 PointValue 然后将原来的 value 设置为 PointValue->origin
  • 右值遇到 * 时就读取 PointValue->origin
  • 左值遇到 * 时就读取 PointValue->origin 的 last variable，然后直接修改

指针与 Phi 值的交互问题​

现在已经解决了裸指针最简单的情况，可以考虑更复杂的问题了。

在静态分析中，Phi 是很重要的概念，用于解决控制流合并时的变量赋值冲突问题。当程序的控制流存在分支时，Phi 函数会"选择"正确的变量值，确保每个变量在 SSA 形式中仍然保持单赋值特性。

funcmain() {
    a := 1
    p := &a
    if a > 0 {
        *p = 2
    } else {
        *p = 3
    }
    println(a) // phi(a)[2,3]
}

在上述案例中，对于变量 a 而言有两条路径可以选择因此会生成 phi(a)[2,3]。但是，a 的修改是通过指针进行间接修改的，导致 *p = 3 会覆盖 *p = 2 对变量 a 造成的影响。

为了解决这个问题，我们将指针的左值操作重新定义为一次对原变量的赋值，那么上面这段包含指针的代码就可以转化为下面代码：

funcmain() {
    a := 1
    p := &a
    if a > 0 {
        // *p = 2
        a = 2
    } else {
        // *p = 3
        a = 3
    }
    println(a) // phi(a)[2,3]
}

看似好像解决了问题，但指针并没有这么简单，我们看下面这个更复杂的案例：

funcmain() {
    a := 1
    b := 2
    p := &a
    if a > 0 {
        p = &a
    } else {
        p = &b
    }
    println(a) // 1
    println(b) // 2
    *p = 3
    println(a) // phi(a)[1,3]
    println(b) // phi(a)[2,3]
    println(*p) // 3
}

这个案例几乎推倒了现有的所有逻辑，因为 *p = 3 这个在后续作用域中生效的值，竟然可以影响在之前的 If 语句中已经合并的作用域。

在这个案例中，似乎可以通过直接修改值的方式为变量 a 和 b 重新设置 Phi 值，但是问题就在于我们不知道 *p = 3 会在何时调用，调用之前变量 a 和 b 是否还会发生变化。

尝试引入 memery 层进行内存建模​

有一个解决方案就是模仿指针在物理内存中的行为，在 variable 和 value 之间加了一个 memery 层，这样 p = &a 的含义就是将指针 p 的 memery 给赋值为变量 a 的 memery，这样就变相实现了指针 p 和变量 a 共享同一个 value：

正常赋值：

指针赋值：

由于两个 variable 指向同一个 memery，*p = 3 将 value 赋值给一个 memery 后，两个 variable 都会查找到修改后的值，这种方案的复杂之处就是需要同时处理两个层次的 Phi 值：

a := 1
b := 2
if a > 0 {
    p = &a
} else {
    p = &b
}
*p = 3

上述代码中的指针 P 不会直接指向 A 或者 B 的 Memery，而是生成一个 Memery 层次的 phi 值，对于变量 A 而言：A 虽然只持有自己的 Memery A，但 Memery A 会被 phi( MemeryA,MemeryB ) 影响从而产生 Vable 层次的 phi 值。

当 *p = 3 执行时，Memery Phi 值的每一个成员都会被添加 phi 值，这样 A 的值为 phi(a)[1,3]，B 的值为 phi(b)[2,3]，而对于 P 自己的值就是 3。

Memery 层和 Value 层之间也是可以出现 Phi 值的：

a := 1
if a > 0 {
    p = &a
} else {
    a = 2
}
println(a) // phi(a)[1,2]
*p = 3
println(a) // phi(a)[3,2]

当 Value 层的 Phi 值计算完毕后得到 phi(a)[1,2]，而 Memery 层的 Phi 值也会影响到 a 并将其 Phi 值改为 phi(a)[3,2]：

最复杂的情况是多级指针：

a := 1
b := 2
pp = &p
if a > 0 {
    p = &a
} else {
    p = &b
}
**pp = 3

多级指针引入了一个 Memery Level 的逻辑：例如这里 pp 的 Memery 不会指向 Value，而是指向另一个 Memery，本质上就是将 *pp（下图红框部分）当做一个虚拟 Value，这个虚拟 Value 的逻辑和指针 p 是一样的，因此处理 **pp 时，可以看做是在处理*p：

多级指针中，不同 Level 的 Memery 也是可能生成 Phi 值的，有时候还可能跨好几个 Level 生成 Phi 值：

a := 1
b := 2
pa := &a
pb := &b
if a > 0 {
    pp = &pa
} else {
    pb = &a
}
**pp = 3

上述代码几乎就没法使用这套逻辑进行静态分析，因为 pp 和 pb 属于不同的 Level，当 **pp = 3 执行时将产生非常复杂的结构，同时也需要更加完善的算法来兼容各种情况。最后我们放弃的内存建模的想法，保留未完成的分支在 fix/ssa/variableMemory 中。

简化逻辑，使用闭包解决问题​

在不考虑指针本身参与 Phi 值的情况下，这个问题还是很好解决的。

现在正在使用的方案就是将指针当做一个 object，该 object 有一个 pointer 和一个 value 成员，pointer 成员的 variable 中有一个 PointHandler 闭包负责在指针改变时修改原始值，然后我们就可以使用这套逻辑来解释一些指针的使用场景，例如：

  • p := &a（注册指针）：生成 object，object->pointer，object->value
  • b := *p（读指针）：读取 object->value
  • *p = 3（写指针）：设置 object->pointer 的 PointHandler 闭包
  • p2 := p（指针赋值）：通过 AssignVariable 正常赋值

使用闭包的好处就是可以记录上下文信息，方便我们在写指针时复原原始数据。

指针与 side-effect 相关的问题​

其实上述文章描述的内容都是和指针本身的性质强相关的，为指针生成 side-effect 才是 C 语言中迫切需要的机制。由于 C 语言中常常使用返回值来传递错误信息，往往数据都是通过指针进行传递的。

#include<stdio.h>
intadd(int a,int b,int* c){
    *c = a + b;
    return 0;
}
intmain()
{
    int a=1,b=2,c;
    add(a,b,&c);
    printf("%d\n",c);
    return 0;
}

使用 printf(* #-> as $a) 进行分析时数据流都会在 add(a,b,&c) 这里断掉，为此需要在 add 调用时生成 side-effect(c)。

现在我们支持在 C 语言的库函数导入时解析函数签名中的指针，这样类似于 sprintf 这种不由用户定义的库函数也可以生成 side-effect：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
voidvulnerable_file_list(constchar *directory){
    char command[256];
    sprintf(command, "ls -la %s", directory);
    println(command); // side-effect(Parameter-directory, command)
}

未来需要解决的问题​

测试发现，当前 C 规则有较多的误报，这是由于 c2ssa 中的机制有不完善的地方，类似于宏定义和宏函数之类的处理也不完善。

目前我们正在调试并完善 C 语言的编译代码，今后会推出更加稳定版本的 C 语言代码扫描模块。

本文首发于 Yak Project 公众号，阅读原文。