196082's blog
Pspray: Timing Side-Channel based Linux Kernel Heap Exploitation Technique
196082 慢慢好起来
  2023-11-23 17:05:25   2023-11-29 18:14:05    8.3k 字  39 分钟  

前言

近期在工作上遇到的内核很少，以至于我都快忘记了我是玩内核的了。这篇文章需要一点slub allocator的基础，所以为什么我以前要偷懒不写slub allocator啊！！！当然这些基础在以前都是默认大家都已经学习过的了，在这里虽然可以一样这样，但是我觉得如果再不分析以后可能就没多少时间写这类分析细致的文章了。

slub allocator基本结构

上面这张overview大家应该都挺熟悉的。

了解过Linux kernel内存管理的朋友应该知道slab allocator主要有三个版本：

  1. slab 最初的版本，机制复杂，效率低
  2. slob 用于嵌入式场景的极简版本
  3. slub 优化后的版本，现在常用

所以后面均已slub为例。

slab

Linux kernel 中用以统筹所有内存的依然是buddy system，slub allocator也不例外，其负责向buddy system请求内存后分割给多个小 object 后再返还给上层调用者，单次向buddy system所请求的一份连续内存页便称之为一张 slab，在内核中对应 slab 结构体，本质上是复用 page 结构体：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct slab {
	unsigned long __page_flags;

#if defined(CONFIG_SLAB)
// ... ...

#elif defined(CONFIG_SLUB)

	struct kmem_cache *slab_cache;
	union {
		struct {
			union {
				struct list_head slab_list;
#ifdef CONFIG_SLUB_CPU_PARTIAL
				struct {
					struct slab *next;
					int slabs;	/* Nr of slabs left */
				};
#endif
			};
			/* Double-word boundary */
			union {
				struct {
					void *freelist;		/* first free object */
					union {
						unsigned long counters;
						struct {
							unsigned inuse:16;
							unsigned objects:15;
							unsigned frozen:1;
						};
					};
				};
#ifdef system_has_freelist_aba
				freelist_aba_t freelist_counter;
#endif
			};
		};
		struct rcu_head rcu_head;
	};
	unsigned int __unused;

#else
#error "Unexpected slab allocator configured"
#endif

	atomic_t __page_refcount;
#ifdef CONFIG_MEMCG
	unsigned long memcg_data;
#endif
};

这里简单解释一下前面的成员：

  • slab_cache: 该slab对应的内存池
  • freelist: slab上空闲的第一个对象，形式为单向链表以NULL结尾
  • slab_list: 按照其用途连接多个slabs双向链表
  • inuse: 已被使用的对象数量
  • objects: 该slab上的对象总数
  • frozen: 是否被冻结，即其已经归属于特定的CPU

这里我们需要注意的是 counters 成员直接涵盖了 inuse & objects & frozen，后面会有大量的直接通过 counters 成员进行赋值的操作，实际上就是赋值了 inuse & objects & frozen

和page结构体类似，这里slab也是对应一张slab内存页，可以通过page_to_pfn函数等可以直接完成slab结构体到内存页虚拟地址的转化，当然反过来也可以从一个空闲空间的虚拟地址找到其对应的slab结构体。

kmem_cache

kmem_cache想必各位较为熟悉，其用于分配特定大小对象的内存池，所有的kmem_cache构成一个双向链表，并存放于一个用于存放通用kmem_cache的数组kmem_caches。

1
2
3
4
struct kmem_cache *
kmalloc_caches[NR_KMALLOC_TYPES][KMALLOC_SHIFT_HIGH + 1] __ro_after_init =
{ /* initialization for https://bugs.llvm.org/show_bug.cgi?id=42570 */ };
EXPORT_SYMBOL(kmalloc_caches);

下面看一下kmem_cache的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
struct kmem_cache {
#ifndef CONFIG_SLUB_TINY
	struct kmem_cache_cpu __percpu *cpu_slab;
#endif
	/* Used for retrieving partial slabs, etc. */
	slab_flags_t flags;
	unsigned long min_partial;
	unsigned int size;	/* The size of an object including metadata */
	unsigned int object_size;/* The size of an object without metadata */
	struct reciprocal_value reciprocal_size;
	unsigned int offset;	/* Free pointer offset */
#ifdef CONFIG_SLUB_CPU_PARTIAL
	/* Number of per cpu partial objects to keep around */
	unsigned int cpu_partial;
	/* Number of per cpu partial slabs to keep around */
	unsigned int cpu_partial_slabs;
#endif
	struct kmem_cache_order_objects oo;

	/* Allocation and freeing of slabs */
	struct kmem_cache_order_objects min;
	gfp_t allocflags;	/* gfp flags to use on each alloc */
	int refcount;		/* Refcount for slab cache destroy */
	void (*ctor)(void *);
	unsigned int inuse;		/* Offset to metadata */
	unsigned int align;		/* Alignment */
	unsigned int red_left_pad;	/* Left redzone padding size */
	const char *name;	/* Name (only for display!) */
	struct list_head list;	/* List of slab caches */
#ifdef CONFIG_SYSFS
	struct kobject kobj;	/* For sysfs */
#endif
#ifdef CONFIG_SLAB_FREELIST_HARDENED
	unsigned long random;
#endif

#ifdef CONFIG_NUMA
	/*
	 * Defragmentation by allocating from a remote node.
	 */
	unsigned int remote_node_defrag_ratio;
#endif

#ifdef CONFIG_SLAB_FREELIST_RANDOM
	unsigned int *random_seq;
#endif

#ifdef CONFIG_KASAN_GENERIC
	struct kasan_cache kasan_info;
#endif

#ifdef CONFIG_HARDENED_USERCOPY
	unsigned int useroffset;	/* Usercopy region offset */
	unsigned int usersize;		/* Usercopy region size */
#endif

	struct kmem_cache_node *node[MAX_NUMNODES];
};

首先这里第一个成员cpu_slab其为__percpu变量指向一个kmem_cache_cpu结构体，即当前CPU独占的内存池。min_partial指的是node partial链表上slab的最大数量。cpu_partial_slabs指的是cpu partial链表上slab的最大数量。size一个对象的实际大小。object_size对象所有数据的大小。offset即空闲对象链表指针对于其对象的偏移。min一个slab上最少的对象数量。allocflags向buddy system申请页面时所使用的gfp flag。ctor对象的构造函数。

random_seq: 用于在 slab 初始化时随机化 freelist 上空闲对象的连接顺序。

useroffset: 用户空间能读写的起始偏移，后面的就时用户空间能读写的大小。

node: 一个 kmem_cache_node 数组，对应多个不同 node 的后备内存池

关于其合并和类型之类的前面的文章提到过，可以去看看 CVE-2022-0185复现 。

kmem_cache_cpu

当一个进程请求分配内存时，首先会尝试向当前CPU的独占内存池进行分配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct kmem_cache_cpu {
	union {
		struct {
			void **freelist;	/* Pointer to next available object */
			unsigned long tid;	/* Globally unique transaction id */
		};
		freelist_aba_t freelist_tid;
	};
	struct slab *slab;	/* The slab from which we are allocating */
#ifdef CONFIG_SLUB_CPU_PARTIAL
	struct slab *partial;	/* Partially allocated frozen slabs */
#endif
	local_lock_t lock;	/* Protects the fields above */
#ifdef CONFIG_SLUB_STATS
	unsigned stat[NR_SLUB_STAT_ITEMS];
#endif
};

而这里的kmem_cache_cpu结构体代表的就是每个CPU独占的内存池。这里的结构体比较简单且眼熟，首先就是freelist含义一样指向下一个空闲的对象。slab指向当前用于分配的slab。partial指向的是percpu partial list链表。

kmem_cache_node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct kmem_cache_node {
#ifdef CONFIG_SLAB
 // ... ...
#endif

#ifdef CONFIG_SLUB
	spinlock_t list_lock;
	unsigned long nr_partial;
	struct list_head partial;
#ifdef CONFIG_SLUB_DEBUG
	atomic_long_t nr_slabs;
	atomic_long_t total_objects;
	struct list_head full;
#endif
#endif

};

其含义为每个node的后备内存池，当percpu的内存池分配完毕之后就会想node的后备内存池进行内存申请。

这里的partial成员同前面的一致，nr_partial很好理解，就是partial的数量。这里的full成员连接的是slab page中的所有对象都已经被使用的slab另外两个计数的也很好理解了。

对象的分配

slab_alloc_node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
static __fastpath_inline void *slab_alloc_node(struct kmem_cache *s, struct list_lru *lru,
		gfp_t gfpflags, int node, unsigned long addr, size_t orig_size)
{
	void *object;
	struct obj_cgroup *objcg = NULL;
	bool init = false;

	s = slab_pre_alloc_hook(s, lru, &objcg, 1, gfpflags);
	if (!s)
		return NULL;

	object = kfence_alloc(s, orig_size, gfpflags);
	if (unlikely(object))
		goto out;

	object = __slab_alloc_node(s, gfpflags, node, addr, orig_size);

	maybe_wipe_obj_freeptr(s, object);
	init = slab_want_init_on_alloc(gfpflags, s);

out:
	/*
	 * When init equals 'true', like for kzalloc() family, only
	 * @orig_size bytes might be zeroed instead of s->object_size
	 */
	slab_post_alloc_hook(s, objcg, gfpflags, 1, &object, init, orig_size);

	return object;
}

首先是通过slab_pre_alloc_hook函数进行检测标识位，随后调用kfence_alloc进行内存错误检测，接下来调用__slab_alloc_node函数进行真正的内存分配，最后两个函数则是将对象原本用于存放next object的位置写为0，最后则是看标识位是否有__GFP_ZERO，若是有则调用slab_post_alloc_hook将堆块上的数据清零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
static __always_inline void *__slab_alloc_node(struct kmem_cache *s,
		gfp_t gfpflags, int node, unsigned long addr, size_t orig_size)
{
	struct kmem_cache_cpu *c;
	struct slab *slab;
	unsigned long tid;
	void *object;

redo:
	c = raw_cpu_ptr(s->cpu_slab);
	tid = READ_ONCE(c->tid);
	barrier();
	object = c->freelist;
	slab = c->slab;

	if (!USE_LOCKLESS_FAST_PATH() ||
	    unlikely(!object || !slab || !node_match(slab, node))) {
		object = __slab_alloc(s, gfpflags, node, addr, c, orig_size);
	} else {
		void *next_object = get_freepointer_safe(s, object);
		if (unlikely(!__update_cpu_freelist_fast(s, object, next_object, tid))) {
			note_cmpxchg_failure("slab_alloc", s, tid);
			goto redo;
		}
		prefetch_freepointer(s, next_object);
		stat(s, ALLOC_FASTPATH);
	}

	return object;
}

首先这里获取percpu上的kmem_cache_cpu，然后获得其freelist以及slab。若 slab 或 freelist 为空 / slab 与 node 不匹配，则调用 __slab_alloc() 分配一张新 slab 并从其中获取一个空闲对象。

这里先考虑条件成立的情况那么就会调用get_freepointer_safe获取到当前空闲对象的下一个空闲对象，接下来调用__update_cpu_freelist_fast函数进行检查是否发生了抢占，如果是则跳回redo重新获取kmem_cache_cpu。最后通过prefetch_freepointer将已分配对象的地址载入缓存中，之后返回分配成功的对象。

前面主要说的是当slab和freelist存在时的情况，下面主要提一下if分支内的内容。这里是直接调用了__slab_alloc函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static void *__slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
			  unsigned long addr, struct kmem_cache_cpu *c, unsigned int orig_size)
{
	void *p;

#ifdef CONFIG_PREEMPT_COUNT
	/*
	 * We may have been preempted and rescheduled on a different
	 * cpu before disabling preemption. Need to reload cpu area
	 * pointer.
	 */
	c = slub_get_cpu_ptr(s->cpu_slab);
#endif

	p = ___slab_alloc(s, gfpflags, node, addr, c, orig_size);
#ifdef CONFIG_PREEMPT_COUNT
	slub_put_cpu_ptr(s->cpu_slab);
#endif
	return p;
}

其主要是对___slab_alloc函数的wrapper

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
			  unsigned long addr, struct kmem_cache_cpu *c, unsigned int orig_size)
{
	void *freelist;
	struct slab *slab;
	unsigned long flags;
	struct partial_context pc;

	stat(s, ALLOC_SLOWPATH);

reread_slab:

	slab = READ_ONCE(c->slab);
	if (!slab) {
		/*
		 * if the node is not online or has no normal memory, just
		 * ignore the node constraint
		 */
		if (unlikely(node != NUMA_NO_NODE &&
			     !node_isset(node, slab_nodes)))
			node = NUMA_NO_NODE;
		goto new_slab;
	}
redo:

	if (unlikely(!node_match(slab, node))) {
		/*
		 * same as above but node_match() being false already
		 * implies node != NUMA_NO_NODE
		 */
		if (!node_isset(node, slab_nodes)) {
			node = NUMA_NO_NODE;
		} else {
			stat(s, ALLOC_NODE_MISMATCH);
			goto deactivate_slab;
		}
	}

	/*
	 * By rights, we should be searching for a slab page that was
	 * PFMEMALLOC but right now, we are losing the pfmemalloc
	 * information when the page leaves the per-cpu allocator
	 */
	if (unlikely(!pfmemalloc_match(slab, gfpflags)))
		goto deactivate_slab;

	/* must check again c->slab in case we got preempted and it changed */
	local_lock_irqsave(&s->cpu_slab->lock, flags);
	if (unlikely(slab != c->slab)) {
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		goto reread_slab;
	}
	freelist = c->freelist;
	if (freelist)
		goto load_freelist;

	freelist = get_freelist(s, slab);

	if (!freelist) {
		c->slab = NULL;
		c->tid = next_tid(c->tid);
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		stat(s, DEACTIVATE_BYPASS);
		goto new_slab;
	}

	stat(s, ALLOC_REFILL);

load_freelist:

	lockdep_assert_held(this_cpu_ptr(&s->cpu_slab->lock));

	/*
	 * freelist is pointing to the list of objects to be used.
	 * slab is pointing to the slab from which the objects are obtained.
	 * That slab must be frozen for per cpu allocations to work.
	 */
	VM_BUG_ON(!c->slab->frozen);
	c->freelist = get_freepointer(s, freelist);
	c->tid = next_tid(c->tid);
	local_unlock_irqrestore(&s->cpu_slab->lock, flags);
	return freelist;

deactivate_slab:

	local_lock_irqsave(&s->cpu_slab->lock, flags);
	if (slab != c->slab) {
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		goto reread_slab;
	}
	freelist = c->freelist;
	c->slab = NULL;
	c->freelist = NULL;
	c->tid = next_tid(c->tid);
	local_unlock_irqrestore(&s->cpu_slab->lock, flags);
	deactivate_slab(s, slab, freelist);

new_slab:

	if (slub_percpu_partial(c)) {
		local_lock_irqsave(&s->cpu_slab->lock, flags);
		if (unlikely(c->slab)) {
			local_unlock_irqrestore(&s->cpu_slab->lock, flags);
			goto reread_slab;
		}
		if (unlikely(!slub_percpu_partial(c))) {
			local_unlock_irqrestore(&s->cpu_slab->lock, flags);
			/* we were preempted and partial list got empty */
			goto new_objects;
		}

		slab = c->slab = slub_percpu_partial(c);
		slub_set_percpu_partial(c, slab);
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		stat(s, CPU_PARTIAL_ALLOC);
		goto redo;
	}

new_objects:

	pc.flags = gfpflags;
	pc.slab = &slab;
	pc.orig_size = orig_size;
	freelist = get_partial(s, node, &pc);
	if (freelist)
		goto check_new_slab;

	slub_put_cpu_ptr(s->cpu_slab);
	slab = new_slab(s, gfpflags, node);
	c = slub_get_cpu_ptr(s->cpu_slab);

	if (unlikely(!slab)) {
		slab_out_of_memory(s, gfpflags, node);
		return NULL;
	}

	stat(s, ALLOC_SLAB);

	if (kmem_cache_debug(s)) {
		freelist = alloc_single_from_new_slab(s, slab, orig_size);

		if (unlikely(!freelist))
			goto new_objects;

		if (s->flags & SLAB_STORE_USER)
			set_track(s, freelist, TRACK_ALLOC, addr);

		return freelist;
	}

	/*
	 * No other reference to the slab yet so we can
	 * muck around with it freely without cmpxchg
	 */
	freelist = slab->freelist;
	slab->freelist = NULL;
	slab->inuse = slab->objects;
	slab->frozen = 1;

	inc_slabs_node(s, slab_nid(slab), slab->objects);

check_new_slab:

	if (kmem_cache_debug(s)) {
		/*
		 * For debug caches here we had to go through
		 * alloc_single_from_partial() so just store the tracking info
		 * and return the object
		 */
		if (s->flags & SLAB_STORE_USER)
			set_track(s, freelist, TRACK_ALLOC, addr);

		return freelist;
	}

	if (unlikely(!pfmemalloc_match(slab, gfpflags))) {
		/*
		 * For !pfmemalloc_match() case we don't load freelist so that
		 * we don't make further mismatched allocations easier.
		 */
		deactivate_slab(s, slab, get_freepointer(s, freelist));
		return freelist;
	}

retry_load_slab:

	local_lock_irqsave(&s->cpu_slab->lock, flags);
	if (unlikely(c->slab)) {
		void *flush_freelist = c->freelist;
		struct slab *flush_slab = c->slab;

		c->slab = NULL;
		c->freelist = NULL;
		c->tid = next_tid(c->tid);

		local_unlock_irqrestore(&s->cpu_slab->lock, flags);

		deactivate_slab(s, flush_slab, flush_freelist);

		stat(s, CPUSLAB_FLUSH);

		goto retry_load_slab;
	}
	c->slab = slab;

	goto load_freelist;
}

而___slab_alloc函数才是其核心函数，首先是reread_slab标签中，判断是否存在slab如果不存在则跳转到new_slab。

在new_slab会检查是否存在percpu partial slab，如果存在则将则将链表中取出一个slab给到percpu slab随后跳进redo。

在redo标签中，首先判断slab是否和node以及分配标识位匹配，如果不匹配则跳转至deactivate_slab标签，紧接着验证当前的slab是否是原来cpu的slab，如果不是则表示发生了抢占跳转到reread_slab标签中。随后获取freelist若freelist不为空则跳转到load_freelist中，若为空则调用get_freelist函数获取slab的freelist如果仍然为空，则将percpu slab的freelist设置为NULL随后跳转到下一个tid，并重新进入new_slab标签获取slab。

随后看load_freelist标签，这一段就比较简单理解了，就是将freelist的next指针赋值给percpu freelist，然后获得下一个tid随后返回freelist。可以注意到的是这里使用的是get_freepointer函数，而这个函数最终会调用到freelist_ptr_decode函数。

1
2
3
4
5
6
7
8
9
10
11
12
static inline void *freelist_ptr_decode(const struct kmem_cache *s,
					freeptr_t ptr, unsigned long ptr_addr)
{
	void *decoded;

#ifdef CONFIG_SLAB_FREELIST_HARDENED
	decoded = (void *)(ptr.v ^ s->random ^ swab(ptr_addr));
#else
	decoded = (void *)ptr.v;
#endif
	return decoded;
}

简单观察这个函数可以发现即便是开启了Hardened freelist保护的情况下slab->freelist都是没有加密的，加密的只是对象上的内容。

回到前面的流程进入到deactivate_slab标签中，这里逻辑很简单，就是将percpu的freelist和slab设置为NULL并且获取到下一个tid之后直接调用deactivate_slab函数，对整张slab进行deactivate。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
static void deactivate_slab(struct kmem_cache *s, struct slab *slab,
			    void *freelist)
{
	enum slab_modes { M_NONE, M_PARTIAL, M_FREE, M_FULL_NOLIST };
	struct kmem_cache_node *n = get_node(s, slab_nid(slab));
	int free_delta = 0;
	enum slab_modes mode = M_NONE;
	void *nextfree, *freelist_iter, *freelist_tail;
	int tail = DEACTIVATE_TO_HEAD;
	unsigned long flags = 0;
	struct slab new;
	struct slab old;

	if (slab->freelist) {
		stat(s, DEACTIVATE_REMOTE_FREES);
		tail = DEACTIVATE_TO_TAIL;
	}

	/*
	 * Stage one: Count the objects on cpu's freelist as free_delta and
	 * remember the last object in freelist_tail for later splicing.
	 */
	freelist_tail = NULL;
	freelist_iter = freelist;
	while (freelist_iter) {
		nextfree = get_freepointer(s, freelist_iter);

		/*
		 * If 'nextfree' is invalid, it is possible that the object at
		 * 'freelist_iter' is already corrupted.  So isolate all objects
		 * starting at 'freelist_iter' by skipping them.
		 */
		if (freelist_corrupted(s, slab, &freelist_iter, nextfree))
			break;

		freelist_tail = freelist_iter;
		free_delta++;

		freelist_iter = nextfree;
	}

	/*
	 * Stage two: Unfreeze the slab while splicing the per-cpu
	 * freelist to the head of slab's freelist.
	 *
	 * Ensure that the slab is unfrozen while the list presence
	 * reflects the actual number of objects during unfreeze.
	 *
	 * We first perform cmpxchg holding lock and insert to list
	 * when it succeed. If there is mismatch then the slab is not
	 * unfrozen and number of objects in the slab may have changed.
	 * Then release lock and retry cmpxchg again.
	 */
redo:

	old.freelist = READ_ONCE(slab->freelist);
	old.counters = READ_ONCE(slab->counters);
	VM_BUG_ON(!old.frozen);

	/* Determine target state of the slab */
	new.counters = old.counters;
	if (freelist_tail) {
		new.inuse -= free_delta;
		set_freepointer(s, freelist_tail, old.freelist);
		new.freelist = freelist;
	} else
		new.freelist = old.freelist;

	new.frozen = 0;

	if (!new.inuse && n->nr_partial >= s->min_partial) {
		mode = M_FREE;
	} else if (new.freelist) {
		mode = M_PARTIAL;
		/*
		 * Taking the spinlock removes the possibility that
		 * acquire_slab() will see a slab that is frozen
		 */
		spin_lock_irqsave(&n->list_lock, flags);
	} else {
		mode = M_FULL_NOLIST;
	}


	if (!slab_update_freelist(s, slab,
				old.freelist, old.counters,
				new.freelist, new.counters,
				"unfreezing slab")) {
		if (mode == M_PARTIAL)
			spin_unlock_irqrestore(&n->list_lock, flags);
		goto redo;
	}


	if (mode == M_PARTIAL) {
		add_partial(n, slab, tail);
		spin_unlock_irqrestore(&n->list_lock, flags);
		stat(s, tail);
	} else if (mode == M_FREE) {
		stat(s, DEACTIVATE_EMPTY);
		discard_slab(s, slab);
		stat(s, FREE_SLAB);
	} else if (mode == M_FULL_NOLIST) {
		stat(s, DEACTIVATE_FULL);
	}
}

这里简单提一下deacticate_slab函数的逻辑，遍历freelist检查是否被破坏，放弃被破坏的部分，将slab->freelist设为原kmem_cache_cpu->freelist，若slab上原有freelist不为 NULL 则再接到后面，设置 slab 的 counters，其中将 frozen 设为 0，若 slab 上的对象全部空闲且 node 的 partial slab 数量大于 kmem_cache->min_partial，调用 discard_slab() 将 slab 释放，若 slab 上存在空闲对象，调用 add_partial() 将其加入 node 的 partial 链表。这里的操作在 CVE-2022-2588复现 里面的CVE-2023-3269中使用过。

接下来进入new_object标签内，若是percpu partial链表也为空，便会进入到这个标签内。这里首先会分配一个新的slab并设置partial_context，调用get_partial尝试从当前node的kmem_cache_node的partial链表中分配一个slab，若成功则直接跳转到check_new_slab。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void *get_partial(struct kmem_cache *s, int node, struct partial_context *pc)
{
	void *object;
	int searchnode = node;

	if (node == NUMA_NO_NODE)
		searchnode = numa_mem_id();

	object = get_partial_node(s, get_node(s, searchnode), pc);
	if (object || node != NUMA_NO_NODE)
		return object;

	return get_any_partial(s, pc);
}

这里如果node的为NUMA_NO_NODE则会调用get_any_partial尝试从其他的node的kmem_cache_node中分配。如果get_partial函数没能从node的kmem_cache_node中获得slab的话则会调用new_slab向buddy system申请一份新的slab。

在拿到slab之后继续往后面走会先判断是否有SLAB_DEBUG_FLAGS标识位，如果有则调用alloc_single_from_new_slab函数，从新分配的slab中获取一个对象之后放回partial/full中，如果失败则退出，成功返回。若是没有设置SLAB_DEBUG_FLAGS这个标识位，那就获取slab的freelist随后调用inc_slabs_node函数给node的引用计数增加。

接下来看check_new_slab标签，这里面做的事比较少，首先则是检查该kmem_cache是否设置了SLAB_DEBUG_FLAGS标识位，然后检查是否设置了SLAB_STORE_USER标识位，随后返回freelist。如果没有设置则调用pfmemalloc_match检查slab与分配标识位是否不匹配，如果不匹配则调用deactivate_slab禁用slab并返回freelist。

最后就是retry_load_slab标签，这里就是尝试加载新获得的slab，如果percpu slab不为NULL，那么这里就将其和freelist设置为NULL，随后调用deactivate_slab禁用slab并获取下一个tid，最后将新获得的slab设置到percpu slab随后跳转到load_freelist分配对象并返回。

kmalloc

前面主要是slub算法的核心逻辑，下面来对象分配更上级的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static __always_inline __alloc_size(1) void *kmalloc(size_t size, gfp_t flags)
{
	if (__builtin_constant_p(size) && size) {
		unsigned int index;

		if (size > KMALLOC_MAX_CACHE_SIZE)
			return kmalloc_large(size, flags);

		index = kmalloc_index(size);
		return kmalloc_trace(
				kmalloc_caches[kmalloc_type(flags, _RET_IP_)][index],
				flags, size);
	}
	return __kmalloc(size, flags);
}

这个函数的逻辑很简单，首先看size为编译预知的，如果不是则直接调用__kmalloc。如果是则进入内部，首先会判断size是否大于KMALLOC_MAX_CACHE_SIZE如果是则直接调用kmalloc_large进行分配并返回，如果不是则调用kmalloc_index函数获取到索引随后使用kmalloc_trace函数进行分配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
static void *__kmalloc_large_node(size_t size, gfp_t flags, int node)
{
	struct page *page;
	void *ptr = NULL;
	unsigned int order = get_order(size);

	if (unlikely(flags & GFP_SLAB_BUG_MASK))
		flags = kmalloc_fix_flags(flags);

	flags |= __GFP_COMP;
	page = alloc_pages_node(node, flags, order);
	if (page) {
		ptr = page_address(page);
		mod_lruvec_page_state(page, NR_SLAB_UNRECLAIMABLE_B,
				      PAGE_SIZE << order);
	}

	ptr = kasan_kmalloc_large(ptr, size, flags);
	/* As ptr might get tagged, call kmemleak hook after KASAN. */
	kmemleak_alloc(ptr, size, 1, flags);
	kmsan_kmalloc_large(ptr, size, flags);

	return ptr;
}

void *kmalloc_large(size_t size, gfp_t flags)
{
	void *ret = __kmalloc_large_node(size, flags, NUMA_NO_NODE);

	trace_kmalloc(_RET_IP_, ret, size, PAGE_SIZE << get_order(size),
		      flags, NUMA_NO_NODE);
	return ret;
}
EXPORT_SYMBOL(kmalloc_large);

这里kmalloc_large最终会调用的是__kmalloc_large_node函数进行分配，可以看到其直接调用了alloc_pages_node向buddy system请求内存了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
static __always_inline unsigned int __kmalloc_index(size_t size,
						    bool size_is_constant)
{
	if (!size)
		return 0;

	if (size <= KMALLOC_MIN_SIZE)
		return KMALLOC_SHIFT_LOW;

	if (KMALLOC_MIN_SIZE <= 32 && size > 64 && size <= 96)
		return 1;
	if (KMALLOC_MIN_SIZE <= 64 && size > 128 && size <= 192)
		return 2;
	if (size <=          8) return 3;
	if (size <=         16) return 4;
	if (size <=         32) return 5;
	if (size <=         64) return 6;
	if (size <=        128) return 7;
	if (size <=        256) return 8;
	if (size <=        512) return 9;
	if (size <=       1024) return 10;
	if (size <=   2 * 1024) return 11;
	if (size <=   4 * 1024) return 12;
	if (size <=   8 * 1024) return 13;
	if (size <=  16 * 1024) return 14;
	if (size <=  32 * 1024) return 15;
	if (size <=  64 * 1024) return 16;
	if (size <= 128 * 1024) return 17;
	if (size <= 256 * 1024) return 18;
	if (size <= 512 * 1024) return 19;
	if (size <= 1024 * 1024) return 20;
	if (size <=  2 * 1024 * 1024) return 21;

	if (!IS_ENABLED(CONFIG_PROFILE_ALL_BRANCHES) && size_is_constant)
		BUILD_BUG_ON_MSG(1, "unexpected size in kmalloc_index()");
	else
		BUG();

	/* Will never be reached. Needed because the compiler may complain */
	return -1;
}

#define kmalloc_index(s) __kmalloc_index(s, true)

而kmalloc_index函数其实就是调用__kmalloc_index，其内部实现也是比较简单粗暴。

关于kmalloc_type函数在 CVE-2022-0185复现 文章中详细分析过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void *__kmem_cache_alloc_node(struct kmem_cache *s, gfp_t gfpflags,
			      int node, size_t orig_size,
			      unsigned long caller)
{
	return slab_alloc_node(s, NULL, gfpflags, node,
			       caller, orig_size);
}

void *kmalloc_trace(struct kmem_cache *s, gfp_t gfpflags, size_t size)
{
	void *ret = __kmem_cache_alloc_node(s, gfpflags, NUMA_NO_NODE,
					    size, _RET_IP_);

	trace_kmalloc(_RET_IP_, ret, size, s->size, gfpflags, NUMA_NO_NODE);

	ret = kasan_kmalloc(s, ret, size, gfpflags);
	return ret;
}
EXPORT_SYMBOL(kmalloc_trace);

kmalloc_trace就是对__kmem_cache_alloc_node函数的调用，而__kmem_cache_alloc_node其实就是对slab_alloc_node的wrapper，前面也已经分析过slab_alloc_node了，不过需要注意的是这里指定了node为NUMA_NO_NODE。

1
2
3
4
5
void *__kmalloc(size_t size, gfp_t flags)
{
	return __do_kmalloc_node(size, flags, NUMA_NO_NODE, _RET_IP_);
}
EXPORT_SYMBOL(__kmalloc);

这里__kmalloc也是直接调用了__do_kmalloc_node函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static __always_inline
void *__do_kmalloc_node(size_t size, gfp_t flags, int node, unsigned long caller)
{
	struct kmem_cache *s;
	void *ret;

	if (unlikely(size > KMALLOC_MAX_CACHE_SIZE)) {
		ret = __kmalloc_large_node(size, flags, node);
		trace_kmalloc(caller, ret, size,
			      PAGE_SIZE << get_order(size), flags, node);
		return ret;
	}

	s = kmalloc_slab(size, flags, caller);

	if (unlikely(ZERO_OR_NULL_PTR(s)))
		return s;

	ret = __kmem_cache_alloc_node(s, flags, node, size, caller);
	ret = kasan_kmalloc(s, ret, size, flags);
	trace_kmalloc(caller, ret, size, s->size, flags, node);
	return ret;
}

这里的逻辑在开头位置同上，如果size大于KMALLOC_MAX_CACHE_SIZE那么就直接调用__kmalloc_large_node进行分配。如果小于的话则贤调用kmalloc_slab寻找到对应的kmem_cache然后调用__kmem_cache_alloc_node进行分配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct kmem_cache *kmalloc_slab(size_t size, gfp_t flags, unsigned long caller)
{
	unsigned int index;

	if (size <= 192) {
		if (!size)
			return ZERO_SIZE_PTR;

		index = size_index[size_index_elem(size)];
	} else {
		if (WARN_ON_ONCE(size > KMALLOC_MAX_CACHE_SIZE))
			return NULL;
		index = fls(size - 1);
	}

	return kmalloc_caches[kmalloc_type(flags, caller)][index];
}

这里寻找的方式也和前面的十分相似，size_index和size_index_elem的实现也是比较粗暴。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
static u8 size_index[24] __ro_after_init = {
	3,	/* 8 */
	4,	/* 16 */
	5,	/* 24 */
	5,	/* 32 */
	6,	/* 40 */
	6,	/* 48 */
	6,	/* 56 */
	6,	/* 64 */
	1,	/* 72 */
	1,	/* 80 */
	1,	/* 88 */
	1,	/* 96 */
	7,	/* 104 */
	7,	/* 112 */
	7,	/* 120 */
	7,	/* 128 */
	2,	/* 136 */
	2,	/* 144 */
	2,	/* 152 */
	2,	/* 160 */
	2,	/* 168 */
	2,	/* 176 */
	2,	/* 184 */
	2	/* 192 */
};

static inline unsigned int size_index_elem(unsigned int bytes)
{
	return (bytes - 1) / 8;
}

对象的释放

do_slab_free

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
static __always_inline void do_slab_free(struct kmem_cache *s,
				struct slab *slab, void *head, void *tail,
				int cnt, unsigned long addr)
{
	void *tail_obj = tail ? : head;
	struct kmem_cache_cpu *c;
	unsigned long tid;
	void **freelist;

redo:
	/*
	 * Determine the currently cpus per cpu slab.
	 * The cpu may change afterward. However that does not matter since
	 * data is retrieved via this pointer. If we are on the same cpu
	 * during the cmpxchg then the free will succeed.
	 */
	c = raw_cpu_ptr(s->cpu_slab);
	tid = READ_ONCE(c->tid);

	/* Same with comment on barrier() in slab_alloc_node() */
	barrier();

	if (unlikely(slab != c->slab)) {
		__slab_free(s, slab, head, tail_obj, cnt, addr);
		return;
	}

	if (USE_LOCKLESS_FAST_PATH()) {
		freelist = READ_ONCE(c->freelist);

		set_freepointer(s, tail_obj, freelist);

		if (unlikely(!__update_cpu_freelist_fast(s, freelist, head, tid))) {
			note_cmpxchg_failure("slab_free", s, tid);
			goto redo;
		}
	} else {
		/* Update the free list under the local lock */
		local_lock(&s->cpu_slab->lock);
		c = this_cpu_ptr(s->cpu_slab);
		if (unlikely(slab != c->slab)) {
			local_unlock(&s->cpu_slab->lock);
			goto redo;
		}
		tid = c->tid;
		freelist = c->freelist;

		set_freepointer(s, tail_obj, freelist);
		c->freelist = head;
		c->tid = next_tid(tid);

		local_unlock(&s->cpu_slab->lock);
	}
	stat(s, FREE_FASTPATH);
}

这里依旧分为两条路径，首先会比较待释放的对象所属于的slab是否是percpu slab，如果是则直接挂回去即可，遵循LIFO机制。

如果不是则会进入到__slab_free函数中进行处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
static void __slab_free(struct kmem_cache *s, struct slab *slab,
			void *head, void *tail, int cnt,
			unsigned long addr)

{
	void *prior;
	int was_frozen;
	struct slab new;
	unsigned long counters;
	struct kmem_cache_node *n = NULL;
	unsigned long flags;

	stat(s, FREE_SLOWPATH);

	if (kfence_free(head))
		return;

	if (IS_ENABLED(CONFIG_SLUB_TINY) || kmem_cache_debug(s)) {
		free_to_partial_list(s, slab, head, tail, cnt, addr);
		return;
	}

	do {
		if (unlikely(n)) {
			spin_unlock_irqrestore(&n->list_lock, flags);
			n = NULL;
		}
		prior = slab->freelist;
		counters = slab->counters;
		set_freepointer(s, tail, prior);
		new.counters = counters;
		was_frozen = new.frozen;
		new.inuse -= cnt;
		if ((!new.inuse || !prior) && !was_frozen) {

			if (kmem_cache_has_cpu_partial(s) && !prior) {

				/*
				 * Slab was on no list before and will be
				 * partially empty
				 * We can defer the list move and instead
				 * freeze it.
				 */
				new.frozen = 1;

			} else { /* Needs to be taken off a list */

				n = get_node(s, slab_nid(slab));
				/*
				 * Speculatively acquire the list_lock.
				 * If the cmpxchg does not succeed then we may
				 * drop the list_lock without any processing.
				 *
				 * Otherwise the list_lock will synchronize with
				 * other processors updating the list of slabs.
				 */
				spin_lock_irqsave(&n->list_lock, flags);

			}
		}

	} while (!slab_update_freelist(s, slab,
		prior, counters,
		head, new.counters,
		"__slab_free"));

	if (likely(!n)) {

		if (likely(was_frozen)) {
			/*
			 * The list lock was not taken therefore no list
			 * activity can be necessary.
			 */
			stat(s, FREE_FROZEN);
		} else if (new.frozen) {
			/*
			 * If we just froze the slab then put it onto the
			 * per cpu partial list.
			 */
			put_cpu_partial(s, slab, 1);
			stat(s, CPU_PARTIAL_FREE);
		}

		return;
	}

	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial))
		goto slab_empty;

	/*
	 * Objects left in the slab. If it was not on the partial list before
	 * then add it.
	 */
	if (!kmem_cache_has_cpu_partial(s) && unlikely(!prior)) {
		remove_full(s, n, slab);
		add_partial(n, slab, DEACTIVATE_TO_TAIL);
		stat(s, FREE_ADD_PARTIAL);
	}
	spin_unlock_irqrestore(&n->list_lock, flags);
	return;

slab_empty:
	if (prior) {
		/*
		 * Slab on the partial list.
		 */
		remove_partial(n, slab);
		stat(s, FREE_REMOVE_PARTIAL);
	} else {
		/* Slab must be on the full list */
		remove_full(s, n, slab);
	}

	spin_unlock_irqrestore(&n->list_lock, flags);
	stat(s, FREE_SLAB);
	discard_slab(s, slab);
}

首先还是kfence和kmem_cache_debug相关，如果设置了SLAB_DEBUG_FLAGS则直接调用free_to_partial_list函数后返回即可。

随后进入循环，这里首先将待释放freelist所属于的slab的freelist写到带释放freelist对应的位置，这里new是栈上的临时slab结构体。

然后进行判断，slab的所有对象都未被使用或者slab上没有空闲的对象并且slab未被冻结，则会进入分支中。进入分支之后继续判断，首先查看是否有percpu partial slab并且slab上没有空闲的对象，如果成立则让该slab冻结，如果不是则获取slab所对应的kmem_cahce_node。

结束循环后，会判断是否找到kmem_cache_node，如果没有找到则进入分支中，如果slab已被冻结，则什么都不敢，若需要被冻结则调用put_cpu_partial函数直接将slab放入到percpu partial链表中，完成释放工作。

接下来会判断，slab的被使用的对象的数量是否为0并且n->nr_partial == s->min_partial的话就代表该slab的所有的对象都被释放掉了并且node上的partial slab数量已经超过min_partial了，这时会跳入slab_empty标签中。在slab_empty标签的逻辑比较简单，判断当前slab原先是否有空闲对象，然后选择从对应的地方移除，最后调用discard_slab函数，释放该slab到内存中。

如果不满足会做一些检查，并且如果以前该slab位于full也将被移到partial中。

kfree

上面是释放对象的核心函数逻辑，下面一样提一下上层函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void kfree(const void *object)
{
	struct folio *folio;
	struct slab *slab;
	struct kmem_cache *s;

	trace_kfree(_RET_IP_, object);

	if (unlikely(ZERO_OR_NULL_PTR(object)))
		return;

	folio = virt_to_folio(object);
	if (unlikely(!folio_test_slab(folio))) {
		free_large_kmalloc(folio, (void *)object);
		return;
	}

	slab = folio_slab(folio);
	s = slab->slab_cache;
	__kmem_cache_free(s, (void *)object, _RET_IP_);
}
EXPORT_SYMBOL(kfree);

这里出现了一个遗忘不熟悉的结构体folio，这里简单提一下，其表示的是一块物理，虚拟，逻辑上都是连续的内存，其本质是复用page结构体然后将其转化为了folio结构体。

可以看到函数最先使用virt_to_folio函数得到了folio结构体

1
2
3
4
5
static inline struct folio *virt_to_folio(const void *x)
{
	struct page *page = virt_to_page(x);
	return page_folio(page);
}

这里首先调用virt_to_page函数从虚拟地址找到其页面，随后调用page_folio函数从页面获得folio结构体。

然后根据名字就能看出来free_large_kmalloc主要用于free大的对象，而大的对象是以复合页的形式存在的，所以如果是复合页则会进入到if分支中，如果不是则进入到下面的内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void free_large_kmalloc(struct folio *folio, void *object)
{
	unsigned int order = folio_order(folio);

	if (WARN_ON_ONCE(order == 0))
		pr_warn_once("object pointer: 0x%p\n", object);

	kmemleak_free(object);
	kasan_kfree_large(object);
	kmsan_kfree_large(object);

	mod_lruvec_page_state(folio_page(folio, 0), NR_SLAB_UNRECLAIMABLE_B,
			      -(PAGE_SIZE << order));
	__free_pages(folio_page(folio, 0), order);
}

可以看到这个函数在最后直接调用了__free_pages将对象返回给了buddy system。

1
2
3
4
void __kmem_cache_free(struct kmem_cache *s, void *x, unsigned long caller)
{
	slab_free(s, virt_to_slab(x), x, NULL, &x, 1, caller);
}

而面对普通的对象释放是调用的__kmem_cache_free函数其内部其实就是调用了slab_free函数。

1
2
3
4
5
6
7
8
9
10
11
12
static __fastpath_inline void slab_free(struct kmem_cache *s, struct slab *slab,
				      void *head, void *tail, void **p, int cnt,
				      unsigned long addr)
{
	memcg_slab_free_hook(s, slab, p, cnt);
	/*
	 * With KASAN enabled slab_free_freelist_hook modifies the freelist
	 * to remove objects, whose reuse must be delayed.
	 */
	if (slab_free_freelist_hook(s, &head, &tail, &cnt))
		do_slab_free(s, slab, head, tail, cnt, addr);
}

slab_free函数内部最终也会调用到前面分析了do_slab_free函数。

Pspray简单介绍

在前面分析slab_alloc_node的函数中发现了存在了两条路，两条路的名字分别为fast path和slow path，而这一利用手法就是基于上述的代码完成的，这是一项基于时序侧信道的漏洞利用技术，通过此方法可以大幅度提高内核漏洞利用成功率。

众所周知，在内核中有很多 动物朋友 保护机制，比如CFI，KASLR等诸多保护，使得攻击者十分难以完成利用。而且现如今的内核加入了shadow stack并且近期爆出的诸多漏洞也都和堆相关，所以内核的堆利用一直都是内核漏洞的主流门派。但是玩过堆的应该都知道内核存在一种机制是slab freelist随机化，让攻击者无法预测到即将申请的堆块在何处，这也就使得更加难以利用了。

而今天给大家介绍的一种利用手法Pspray可以用来很好的对抗slab freelist的随机化。

现状分析

image-20231123153331621

上图十分简单明了的给出了分配一个对象的流程。

  1. 如果在cpu freelist中有则直接取，如果没有进入下一阶段
  2. 这里从cpu page freelist中取，操作主要是用cpu page freelist给到cpu freelist，即freelist的初始化
  3. 这里从cpu partial list中取
  4. 这里从node partial list中取
  5. 全都没了就向buddy system申请

然后就是Slab Freelist Random机制，当开启CONFIG_SLAB_FREELIST_RANDOM选项时会开启保护，主要形式如下图所示

image-20231123155055348

Out Of Bounds

在堆利用中时常会遇到堆溢出的漏洞，一般来说我们都期望能够实现下图这样堆的形式

image-20231123155332029

但是事与愿违，因为地址随机化的存在大概率会成为下图这样

image-20231123155423929

中间可能隔着其他结构体，一类的情况。

在开启 freelist 随机化之后的漏洞利用成功率如下，基于 Linux kernel 使用 Fisher-Yates shuffle 算法来进行随机化这个前提计算的，其中N为一张 slub 上的总对象数，同时我们假设在同一张 slab 上分配了 1 个漏洞对象与k个 victim 对象：

image-20231123155859344

（不会写数学公式）

总体而言，我们从N个空闲对象中选择k个 victim 对象 与 1 个漏洞对象，在进行利用时 victim 对象与漏洞对象必须相邻，因此我们从N−1 个对象中取出k个对象（还有一个作为漏洞对象），喷射的 victim 对象数量可以从 0 到 N−1 ，因此对于带有 random slab freelist 的 OOB 利用而言的成功率计算如下：

image-20231123160048017

Use After Free

image-20231123160326552

UAF 漏洞的利用通常是要将漏洞对象与 victim 对象放在同一内存地址，上图展示了对 CVE-2019-2215 的利用过程，首先用 epoll_ctl() 分配漏洞对象，接下来用 ioctl() 释放漏洞对象，随后用 msgsnd() 取回刚刚释放的对象，最后再用 close() 将该对象释放

image-20231123160510337

上图主要展示了UAF的失败案例，UAF的成功率如下

image-20231123160657856

上式中A表示的分配的对象数量，N表示一张slab拥有的对象数量。漏洞利用失败的主要原因是对 slab 信息的缺失，本文找到了一种能够获取 slab 的部分分配信息的时序侧信道方法，从而提高利用成功概率。

利用原理分析

如前面的一张图所示，SLUB 有五条不同深度的分配路径以优化性能表现，为了弄清不同路径的表现，作者通过 msgsnd() 系统调用测试了从 kmalloc() 的核心函数 slab_alloc_node() 的开始到结尾的性能，经过多轮测试发现 slow-path 与其他路径相比存在明显的表现差距，因此攻击者可以通过测量分配时间得知内存分配所经历的路径。

slow-path 以外的分配路径的分配状态都是难以确定的，但 slow-path 的行为与其他路径不同，此时内核会从buddy system分配一张新 slab，由此我们可以知道当前的 slab 刚被分配且仅分配了一个对象

为了能够使用时序侧信道攻击，需要找到满足这样三个条件的系统调用，首先是普通用户可以使用，其次只分配一个对象，最后除了分配对象外性能开销较小。

image-20231123162356541

这里原作者找到了满足上面三个条件并且从涵盖kmalloc-32到kmalloc-8192的系统调用。

image-20231123162555768

这里使用msgsnd系统调用测试得到了如上图所示的结果，可以知道的事fast path和medium path一般来说较为难以区分，但是在slow path时会有很明显的时间差。

image-20231123162822451

上图展示了利用Pspray的流程：

  1. 首先使用Pspray确定了slow path被执行，此时意味着当前的cpu slab是新向buddy system申请的slab
  2. 接下来堆喷N-1个对象使其完全被分配
  3. 此时如果再次申请一个对象则又回进入到slow path中，并且是一个全部为空的slab
  4. 不难想到的是如果我们的Vuln object不在高地址那么就一定可以完成漏洞利用

此时利用的成功率为

image-20231123163220066

image-20231123163250150

后面的UAF的流程和上述类似，并且其成功率为

image-20231123163335334

实际测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <stdint.h>
#include <sched.h>
#include <sys/msg.h>
#include <sys/ipc.h>

struct list_head
{
    uint64_t next;
    uint64_t prev;
};

struct msg_msg
{
    struct list_head m_list;
    uint64_t m_type;
    uint64_t m_ts;
    uint64_t next;
    uint64_t security;
};

struct msg_msgseg
{
    uint64_t next;
};

void bind_cpu(int core)
{
    cpu_set_t cpu_set;

    CPU_ZERO(&cpu_set);
    CPU_SET(core, &cpu_set);
    sched_setaffinity(getpid(), sizeof(cpu_set), &cpu_set);
}

uint64_t rdtsc(void)
{
    __asm__(
        "rdtsc;"
        "shl rdx,32;"
        "add rax,rdx;"
        "leave;"
        "ret;");
}

int main(int argc, char **argv, char **envp)
{
    int msqid[0x1000];
    uint64_t exec_time[0x1000];
    char buf[0x1000];
    struct msqid_ds ds_buf;

    bind_cpu(0);

    for (int i = 0; i < 0x1000; i++)
    {
        if ((msqid[i] = msgget(IPC_PRIVATE, 0666 | IPC_CREAT)) < 0)
        {
            printf("[x] FAILD to get %d msg_queue!\n", i);
            perror("FAILED to get msg_queue");
            exit(EXIT_FAILURE);
        }
    }

    *(size_t *)buf = 123456;
    ((struct msgbuf *)buf)->mtype = 0xdeadbeef;

    for (int i = 0; i < 0x1000; i++)
    {
        uint64_t begin, end;

        begin = rdtsc();
        if (msgsnd(msqid[i], &buf, 512 - sizeof(struct msg_msg), 0) < 0)
        {
            printf("[x] FAILD to send %d msg!\n", i);
            perror("FAILED to alloc msg_msg");
            exit(EXIT_FAILURE);
        }
        end = rdtsc();

        exec_time[i] = end - begin;
    }

    for (int i = 0; i < 0x1000; i++)
    {
        if (msgrcv(msqid[i], buf, 512 - sizeof(struct msg_msg), 0xdeadbeef, 0) < 0)
        {
            printf("[x] FAILD to read %d msg!\n", i);
            perror("FAILED to free msg_msg");
            exit(EXIT_FAILURE);
        }
    }

    for (int i = 0; i < 0x1000; i++)
    {
        if (msgctl(msqid[i], IPC_RMID, &ds_buf) < 0)
        {
            printf("[x] FAILD to delete %d msg_queue!\n", i);
            perror("FAILED to free msg_queue");
            exit(EXIT_FAILURE);
        }
    }

    for (int i = 0; i < 0x1000; i++)
    {
        printf("[*] Execute time for no.%d msgsnd(): %ld\n", i, exec_time[i]);
    }

    return 0;
}

这里使用ctf题目进行了测试一下，发现还是存在非常明显的时间差的。

image-20231123165208062

总的来说，利用方法还是比较简单的，想必看完了大家也应该都明白了如何利用此手法。

参考链接：

​ https://arttnba3.cn/2023/09/16/PAPER-0X03-PSPRAY/

​ https://www.usenix.org/system/files/usenixsecurity23-lee-yoochan.pdf

 评论
评论插件加载失败
正在加载评论插件
  1. 前言
  2. slub allocator基本结构
    1. slab
    2. kmem_cache
    3. kmem_cache_cpu
    4. kmem_cache_node
  3. 对象的分配
    1. slab_alloc_node
    2. kmalloc
  4. 对象的释放
    1. do_slab_free
    2. kfree
  5. Pspray简单介绍
  6. 现状分析
    1. Out Of Bounds
    2. Use After Free
  7. 利用原理分析
    1. 实际测试
© 2020 - 2025    196082
由 Hexo 驱动 & 主题 Keep
本站由 提供部署服务
总字数 335.6k 访客数 访问量
  1. 前言
  2. slub allocator基本结构
    1. slab
    2. kmem_cache
    3. kmem_cache_cpu
    4. kmem_cache_node
  3. 对象的分配
    1. slab_alloc_node
    2. kmalloc
  4. 对象的释放
    1. do_slab_free
    2. kfree
  5. Pspray简单介绍
  6. 现状分析
    1. Out Of Bounds
    2. Use After Free
  7. 利用原理分析
    1. 实际测试