【bsauce读论文】2022-USENIX-LinKRID: Vetting Imbalance Reference Counting in Linux kernel with Symbolic Execution

1.简介

目标：挖掘错误使用引用计数（reference counter）的漏洞。

挑战：可扩展性；独特的内核约定（不统一的引用计数管理，eg，external vs. internal reference counter）

• 需要进行 path-sensitive analysis，检查可行的路径上，refcount递增递减是否匹配reference的增加与移除；
• Linux内核中使用refcount时有特殊的约定，有些是良性的，并不会违反refcount的一致性原则，可能会导致误报，例如 internal references 不需要被refcount计数。

工作：基于 KENALI [31] 和KLEE [3,33]，开发了 LinKRID (Linux Kernel Refcount Imbalance Detector)，基于path-sensitive analysis，代码包含3.5k C++ 和 2.7K python。首先识别refcount对象及其约束范围，然后采用 under-constrained symbolic execution 来具体分析相应的 refcount change 和 reference change。

实验：在内核 4.14.0（allyesconfig编译）上找到118个漏洞，其中87个新洞。

2.背景

reference counter 介绍：防止内存对象被过早释放，可以记录内存对象的引用次数（C语言中的指针）。当refcount值为0时，表示该对象不会被访问，可以安全释放。通常采用结构 struct kref 来存储计数器，并提供API（eg，kref_get 和 kref_put）来操纵计数器。

refcount漏洞：常见漏洞分为两种，一是创建新的引用时没有递增计数器，可能导致UAF，例如 CVE-2016-4557；二是移除引用时没有递减计数器，可能导致memory leak。如果refcount能无限递增，可能导致refcount溢出并触发UAF，例如CVE-2016-0728。

相关工作：都没有解决第2个挑战。

• Mao[20] 提出 inconsistent path pair (IPP)，如果两条路径返回相同的error code，但是处理refcount的方式不同（有不同数量的 get 或 put），则其中一条路径有漏洞（eg，Figure 3）。不准确，只考虑了refcount change，未考虑reference change。即便多条路径都返回相同的error code，也保持了一致性，仍可能有漏洞。
• Li [15] 为了找Python扩展（C编写）的refcount漏洞，采用 escape rule —— 在任何函数和任何路径中，refcount change 必须和 reference change 次数相等。但它依赖已经定义好的接口（Python和C之间），且采用了 shallow aliasing（不准确）。

案例分析（CVE-2016-0728）：见 Figure 1，函数 join_session_keyring() 中，如果找到相应的 keyring 就会引用加1（31行），但如果 keyring 等于当前的（16行），则直接返回，不会将refcount减1。可能产生refcount溢出，从而导致UAF。

Internal References（需排除）：external reference 就是我们上面讨论的情况，需要遵守一致性原则；internel reference 不需要refcount计数，最常见的就是 software cache 中的指针，例如 radix tree / double-linked list / hash map，内核线程可以查找相应的对象（eg, by name），然后从 cache 的 internel reference 中获得一个 externel reference，这种 internel reference 只表示对象存在，并不表示对象被使用，所以不需要refcount计数。在最后一个 externel reference 释放后，对应的 internel reference 会自动释放，例如，Figure 2 中，当mgr->kref 为0时，kref_put 会调用 amp_mgr_destroy 移除对 mgr 的 internel reference 。internel reference 显然也违反了一致性原则，会带来误报。

再例如，back-pointers，网络命名空间对象 struct net 包含refcount，很多网络相关的对象包含一个 back-pointer 指向所属的网络命名空间，但是并没有refcount计数，当指向的对象被释放后，这些 internal reference 也随之自动释放。也有例外，例如Point-to-Point Protocol (PPP) 中，这类 back-pointer不属于 internal reference，应该被refcount计数，由于没有被正确计数导致了UAF CVE-2016-4805。

3.方法

问题定义：在 local reference scope 中检查是否满足条件 ∆refcount == ∆#(live reference) （称为invariant check）。因为local reference 都要通过全局变量来获取，而全局变量永远是live的，所以只需检查局部引用是否满足这个条件。且只需在每个 local analysis scope 的末尾进行invariant check。

global reference 生命周期：见 Figure 3。

• Creation：分配点（kmalloc()）到 local reference 到 global reference （func_1）；
• Usage：从 global reference 到 local reference 到 usage （func_2）；
• Escape：从 global reference 到 local reference 到另一个 global reference（func_3）；
• Release：从 global reference 到 local reference 到移除 global reference （func_4）。

local references scope定义：开始，从global reference （指向一个 refcounted object）获取一个 local reference；结束，所有的 local reference （指向一个 refcounted object）都被释放。

定义1—refcount bug：在local references scope末尾，refcount change 次数（∆refcount)）不等于全局可见的reference change 次数（∆#(reference) == #escaped - #released)）。Figure 3 展示了4种不同的 local references scope，以及如何计算 refcount change 不变量。

LinKRID总览：见Figure 4。

• static analysis：识别 refcount 堆对象（refcounted structures）和操纵 refcount 的API（refcount wrappers）；识别 local reference scope（构造 flow chains，也就是 local reference 的数据流，从reference创建到不可访问为止），使符号执行在这个范围执行。
• symbolic analysis：采用约束符号执行，不需要初始化数据结构和环境建模，在 local reference scope 中按照定义1进行检查。
• bug detection：筛除 internal reference 带来的误报（通过总结 internal reference 类型）。

4.静态分析

分析LLVM IR。

（1）收集refcount信息：

• refcounted structures：内核结构是嵌入式的，例如 kobject -> kref -> refcount_t -> atomic_t，可以通过检查是否嵌入 refcount 结构来识别（例如，kref 和 refcount_t）。
• refcount wrappers：通常命名为 get()/put() ，例如 kobject_get/put, kref_get/put, refcount_inc/dec，或直接使用atomic_inc/dec。作者收集了 16个能在底层操纵 refcount 的API，然后采用启发式策略来识别 wrapper，一是调用了已知的 refcount wrappers，二是通过函数参数或返回值来传递 reference，三是不改变 global reference 数目。因此作者在4.14中找到685个 refcount wrappers，可分为两类，一类是递增，一类是递减。

（2）构造 flow chain

挑战：local reference 可能通过数据流扩大了 life-scope，例如将引用传给其他局部变量、函数参数、返回值，所以需要用 flow chain 将重合的 life-scope 整合起来。 这样看来，flow chain 就是一个小的调用图，包含了和 local reference 相关的待分析的所有函数。

过程：

• 识别某个 local reference 的3种关系：
  • Return-Return relation：$(f_i,f_j)$ 表示调用函数和被调用函数，局部引用 lr 既是 $f_i$ 的返回值，也是 $f_j$ 的返回值。见 Figure 5a。
  • Call-Call relation：局部引用 lr 是 $f_i$ 和 $f_j$ 的参数。见 Figure 5b。
  • Call-Return relation：局部引用 lr 是 $f_i$ 传给 $f_j$ 的参数，是 $f_j$ 的返回值。见 Figure 5c。
• 对给定的 local reference，串起所有相关的函数，来表示其 scope。Figure 6(I) 展示了4个local reference相关的函数调用关系（源代码见Figure 11），Figure 6(II) 展示了 4个局部引用的scope。

5.符号执行

5-1 追踪 reference change 和 refcount change

（1）追踪 reference change

方法一：计算方法是 ∆#(reference) = #escaped - #released，创建全局引用的次数 - 移除全局引用的次数。escape——reference开始被其他 syscall/threads 可访问，也就是在 local reference 被拷贝到全局可见的变量（eg, 堆对象中的某个域成员）；released——reference开始被其他 syscall/threads 不可访问，两种情况，一是全局可见的变量被覆写（另一个reference或常量NULL），二是全局可见的变量指向的reference被释放。因此可以通过追踪全局可见变量的write和free，来获取reference change。

规则1：reference change——通过全局变量或动态分配的内存。当某个local reference 被赋值到某个全局可见的对象，表示 escaped reference，创建了一个 global reference；当某个 global reference 被覆写为另一个 reference 或 NULL值，或者被释放，则表示 released reference。

方法2：多数 write 和 free 可以在 LLVM IR 层追踪，但还有一些是通过内核API来操作的（较难分析，可能涉及到汇编代码），例如， list_add() 将refcount对象加入到双链表—escape，list_del() 将 refcount 对象从双链表移除—release。详细总结参见 Table 1。

规则2：reference change——通过 reference wrappers。当调用了 Table 1中的API，则更新相应的 reference change。

（2）追踪 refcount change

方法：可通过 refcount wrapper 来追踪 refcount change，但是还是要检查其返回值来判断是否成功处理refcount。例如，当 refcount 为0时，kref_get_unless_zero() 不会递增refcount 并返回错误码0。可以对 refcount wrapper 进行 symbolic path summary ，弄清哪些返回值表示 refcount 成功递增，哪些返回值表示处理失败。

规则3：refcount change——只有当 refcount wrapper 成功处理了 reference，才记录相应的 refcopunt change。

（3）追踪异步操作中的change

问题：若某个 local reference 作为参数传给了某个异步机制如 work queue / timer，则在异步调用函数触发之前，相应的 refcount 不能被释放（refcount 不能减为0）。两种情况，一是传给异步机制时refcount递增，异步调用函数中有相应的refcount递减；二是当前syscall/thread 等待异步任务完成（不需要处理refcount）。

解决：将异步调用当作同步调用（普通函数），LinKRID单独分析异步调用函数并进行函数总结，例如异步注册函数 queue_work / mod_timer。对于异步解注册函数 cancel_work / del_timer，LinKRID会创建新的路径，把异步调用当作没有执行，和之前的 refcount wrapper 处理方法一样。

规则4：refcount change——当异步调用函数成功注册/解注册，就将其summary从当前 flow chain 包含进/移除。

5-2 Summary-based chain analysis

缓解路径爆炸：一是只执行同一源码文件中的函数，对于外部函数都当作返回无约束符号值；二是避免重复分析同一函数，采用summarizing function；三是每次reference都设置可探索的最大路径数。

（1） path summary 计算

路径总结：$Sum = (lr, escape, release, ∆refcnt, retval)$

• lr——函数中的 local reference；
• escape——lr传递到 glocal reference 的指令集合；
• release——global reference 被移除的指令集合；∆#reference = escape - release，保存指令集合而非仅仅是数字，是为了便于筛除误报（eg, internel reference）
• ∆refcnt——表示 refcount change
• retval——该路径的返回值，会影响到caller的控制流。

方法：为了计算 path summary，我们要对函数进行约束符号执行，执行过程中要不断 maintaining / forking “states”。

state定义：$State* = (ip, con, escape, release, ∆refcnt, vmap, retval)$

• ip——指向下一条待执行指令；
• cons——路径约束；
• escape / release / ∆refcnt / retval—— 同上；
• vmap——变量到符号值的映射map。

符号执行方法：见Table 2。case 3/5/6 对应 5-1 的规则，case 1/2/4/7 对应UC-KLEE处理典型指令的方法。例如，vmap[x] = vmap[u] 表示变量x映射到值u。当LinKRID遇到call指令，首先检查目标函数是否有summary，有的话则加入到当前state，否则，对该函数进行符号化分析。如果函数调用自身，则只执行1次（递归深度为1）。 符号执行会生成很多新的state，每个state单独执行，每执行一个返回指令，就创建一个function summary（根据state来记录 reference change / refcount change / retval）

（2） Summary-Based Analysis of Flow Chains

方法：为避免重复分析同一函数，所以采用自底向上的迭代分析。整合同一源文件中的所有 flow chain，先分析叶节点（加入到 worklist），然后遍历 worklist，若某个函数有多个caller，则调用 symbolicexec(f) 来计算 summary；若某个函数为入口函数，则对其进行符号执行；对其他函数则标记为 analyzed 状态，不需要符号执行。执行完一轮后，继续将新的叶节点加入到worklist。

6.漏洞检测

6-1 识别 internal reference

第1种，见 Figure 2，当 refcount 为0时，就会调用 list_del() 移除 mgr。LinKRID通过分析 refcount wrapper （eg, kref_put()）注册的回调函数来发现这类 internal reference。

第2种，更加普遍，internal reference 并不是在某个点被释放（eg, refcount 变为0的点），而是以 domain-specific 的方式 ，例如，net 对象被释放后，会自动释放所有包含 back-pointer 指针指向 net 的网络对象。很难识别这种 internel reference 所有的释放点，因此采用启发式策略，当一个reference（例如某个struct中的指针）在内核中不存在任何refcount，则视为 internal reference。缺点是会导致漏报，可参见实验 7-3。

6-2 确定 refcount change 和 reference change 的联系

问题：很难确定$∆refcount_{lr}, escape_{lr}, release_{lr}$ 三者是针对同一 refcount object。例如，结构关系 gdm->tty_port->kref，tty_port->kref 可以表示 tty_port 的refcount，但由于 container_of() 这类函数的使用，很难区分refcount 是属于 gdm 还是 tty_port。本质上是嵌入结构导致的别名分析问题，由指针运算和 type casting 导致。

解决：启发式策略。若2个 local reference （eg, gdm / tty_port）在同一函数中触发两个警告，一个导致 missing refcount change ，另一个导致 missing reference change，且其中一个 local reference 嵌入到另一个，作者就把其中一个 local reference 的 refcount change 和另一个的 reference change 联系到一起。缺点是会导致漏报，在 7-3 中讨论如何提升。

6-3 漏洞报告

筛除 internal reference 后，就可以对剩下的警告进行手动分析。Figure 7 展示了一个 bug report 示例，含路径信息（eg, branch direction）和refcount信息（eg, refcount get/put）。

7.实验评估

总体结果：见 Table 3。

漏洞：LinKRID报告209个 refcount 错误，人工确认118个，87个是未知漏洞，47个漏洞被确认，细节可以参见 Table 4。漏洞主要分为两类，一类是 Improper refcount changes，另一类是 Improper reference changes。

后面具体分析的误报漏报，以及漏洞的安全影响。