[Linux Kernel Exploit] Slab Allocator & msg_msg Struct

1. 개요

리눅스 커널 익스플로잇을 공부하다 보면 힙 스프레이 라는 개념이 등장합니다. 스프레이는 직역하면 무언가를 뿌리는 것 인데요. 익스플로잇 관점으로 다시 해석하면 무언가를 뿌리는데 힙 영역에 객체를 뿌리는 것 입니다. 스프레이가 필요한 이유는 리눅스 커널의 randomized free list 때문인데요. 이번 글에선 힙 스프레이에 자주 사용되는 msg_msg 구조체의 구조에 대해 간략히 알아보도록 하겠습니다.

 

2. Slab Allocator

msg_msg 구조체에 대해 알아보기에 앞서 리눅스 커널의 할당자(Allocator)에 대해 알아보겠습니다. 현재 리눅스 커널은 Slab Allocator를 사용하며 유저 영역의 힙과는 다르게 동작합니다. 구조를 보면 크게 cache라는 덩어리 안에 slab이 존재하며 slab 안에는 slot이 존재합니다. 커널에 힙 할당을 요청하면 free slot들 중 하나가 할당되고 object가 만들어집니다.

pwn.college

커널에서 free 상태의 object들은 freelist로 관리되는데 linked list 구조를 가집니다.

pwn.college

다시 재할당될 때는 마지막에 해제한 object가 재할당되는 LIFO 구조를 가지고 있습니다. free slot에는 다음 free slot을 가리키는 next 포인터가 존재하는데 slot의 중간에 존재합니다.

pwn.college

 

3. freelist randomization & harden freelist

freed slot 주소들이 저장된 freelist에는 보호기법이 적용되어 있습니다. 깊게 인터널스까지 보진 않고 간단하게 개념만 살펴보도록 하겠습니다.

먼저 randomization은 slab 내부에서 slot이 할당되는 순서가 랜덤이 됩니다. 즉, slot 하나의 주소를 안다고 하더라고 해당 slot의 다음 주소는 object 사이즈를 더한 주소가 되는 것이 아니라는 의미입니다. 이 freelist randomization을 극복하기 위해 힙 스프레이가 등장했습니다.

pwn.college

힙 스프레이는 UAF가 발생될 때 많이 쓰이며 같은 slab에 최대한 많은 attacker object를 할당받아서 다음에 할당될 object가 조작할 수 있는 attacker object가 될 확률을 높히는데에 목적을 두고 있습니다.

pwn.college

다음으로 harden freelist는 safe liking처럼 next 포인터에 특정한 연산을 수행해 보안성을 높이는 기술입니다. 다음과 같은 구조로 이루어진다고 하는데 코드 자체를 이해하려 하진 않고 이렇게 연산하는구나 하고 넘어갔습니다.

pwn.college

이를 극복하기 위해선 2개의 next 포인터를 릭해야 합니다. 하나는 다음 slot을 가리키는 next 포인터이고, 다른 하나는 null을 가리키는() next 포인터 입니다. 2개를 xor 연산한 값을 원하는 주소와 xor 연산하게 되면 next slot이 원하는 주소가 될 수 있도록 조작할 수 있습니다.

 

4. msg_msg struct

이제 드디어 msg_msg에 대해 알아보겠습니다. msg_msg는 IPC에서 사용된다고 합니다. 유저가 원하는대로 크기를 조작해서 kmalloc-64부터 kmalloc-4k까지 slot을 할당받을 수 있다는 점이 매력적이기 때문에 주로 사용하는 것 같습니다. msg_msg는 다음과 같이 총 0x30만큼의 크기를 가지고 있습니다. list_head의 크기가 0x10으로 prev, next 포인터를 가지고 있습니다.

/* one msg_msg structure for each message */
struct msg_msg {
	struct list_head m_list;
	long m_type;
	size_t m_ts;		/* message text size */
	struct msg_msgseg *next;
	void *security;
	/* the actual message follows immediately */
};

 

5. do_msgsnd()

메시지를 보낼 때 유저 영역에서 msgsnd() 함수를 사용합니다. msgsnd()가 호출되면 커널에서 do_msgsnd() -> load_msg() -> alloc_msg() 순으로 호출되면서 메시지 헤더와 메시지 데이터를 포함하는 데 필요한 객체를 할당합니다. msgsnd()를 호출할 땐 다음과 같이 사용합니다. mtext 배열은 원하는 사이즈만큼 설정해서 보내면 됩니다. mtype은 1로 지정합니다.

struct msgbuf
{
    long mtype;
    char mtext[0x1fc8];
} msg;

msg.mtype = 1;
memset(msg.mtext, 'A', sizeof(msg.mtext));

qid = msgget(IPC_PRIVATE, 0644 | IPC_CREAT));
msgsnd(qid, &msg, sizeof(msg.mtext), IPC_NOWAIT);

먼저 do_msgsnd()는 다음과 같으며 msgsz, msqid, mtype를 검사하고 load_msg()를 호출합니다. 

static long do_msgsnd(int msqid, long mtype, void __user *mtext, size_t msgsz, int msgflg)
{
	struct msg_queue *msq;
	struct msg_msg *msg;
	int err;
	struct ipc_namespace *ns;
	DEFINE_WAKE_Q(wake_q);

	ns = current->nsproxy->ipc_ns;

	if (msgsz > ns->msg_ctlmax || (long) msgsz < 0 || msqid < 0)
		return -EINVAL;
	if (mtype < 1)
		return -EINVAL;

	msg = load_msg(mtext, msgsz);
	if (IS_ERR(msg))
		return PTR_ERR(msg);

	msg->m_type = mtype;
	msg->m_ts = msgsz;

	rcu_read_lock();
	msq = msq_obtain_object_check(ns, msqid);
	if (IS_ERR(msq)) {
		err = PTR_ERR(msq);
		goto out_unlock1;
	}

	...
}

 

load_msg에서 메시지 내용을 저장합니다. 저장 공간은 alloc_msg() 함수에서 할당 받습니다.

struct msg_msg *load_msg(const void __user *src, size_t len)
{
	struct msg_msg *msg;
	struct msg_msgseg *seg;
	int err = -EFAULT;
	size_t alen;

	msg = alloc_msg(len);
	if (msg == NULL)
		return ERR_PTR(-ENOMEM);

	alen = min(len, DATALEN_MSG);
	if (copy_from_user(msg + 1, src, alen))
		goto out_err;

	for (seg = msg->next; seg != NULL; seg = seg->next) {
		len -= alen;
		src = (char __user *)src + alen;
		alen = min(len, DATALEN_SEG);
		if (copy_from_user(seg + 1, src, alen))
			goto out_err;
	}

	err = security_msg_msg_alloc(msg);
	if (err)
		goto out_err;

	return msg;

out_err:
	free_msg(msg);
	return ERR_PTR(err);
}

alloc_msg에서 kmalloc으로 보낸 메시지를 저장할 object를 할당 받습니다.

struct msg_msgseg {
	struct msg_msgseg *next;
	/* the next part of the message follows immediately */
};

#define DATALEN_MSG	((size_t)PAGE_SIZE-sizeof(struct msg_msg))
#define DATALEN_SEG	((size_t)PAGE_SIZE-sizeof(struct msg_msgseg))

static struct msg_msg *alloc_msg(size_t len)
{
	struct msg_msg *msg;
	struct msg_msgseg **pseg;
	size_t alen;

	alen = min(len, DATALEN_MSG);
	msg = kmalloc(sizeof(*msg) + alen, GFP_KERNEL_ACCOUNT);
	if (msg == NULL)
		return NULL;

	msg->next = NULL;
	msg->security = NULL;

	len -= alen;
	pseg = &msg->next;
	while (len > 0) {
		struct msg_msgseg *seg;

		cond_resched();

		alen = min(len, DATALEN_SEG);
		seg = kmalloc(sizeof(*seg) + alen, GFP_KERNEL_ACCOUNT);
		if (seg == NULL)
			goto out_err;
		*pseg = seg;
		seg->next = NULL;
		pseg = &seg->next;
		len -= alen;
	}

	return msg;

out_err:
	free_msg(msg);
	return NULL;
}

alloc_msg를 살펴보면 min(len, DATALEN_MSG)의 결과 값인 alen이 kmalloc의 사이즈로 사용됩니다. DATALEN_MSG는 PAGE_SIZE(0x1000)에서 msg_msg의 사이즈 값(0x30)을 뺀 값입니다. 즉, 한 번에 최대 0xfd0만큼 메세지가 할당됩니다. 이후 len -= alen해서 남은 len에 대해선 segment에 저장되며 단일 연결 리스트로 관리됩니다. 

 

세그먼트는 min(len, DATALEN_SEG)의 결과 값인 alen이 kmalloc의 사이즈로에 사용됩니다. 최대 값은 0x1000-0x8인 0xff8 입니다. 할당받은 세그먼트는 msg_msgseg->next에 저장됩니다. while 문을 반복하면서 len이 0이 될 때까지 반복하면서 세그먼트 리스트를 만들어 줍니다. 이렇게 만들어진 세그먼트 리스트는 msg->next에 저장되며 아래 그림과 같은 구조를 가집니다.

https://syst3mfailure.io/wall-of-perdition/

 

6. do_msgrcv()

메시지를 보내는 것을 알아봤으니 이제 받는 것을 알아보겠습니다. msgrcv() 함수를 이용하며 다음과 같이 사용할 수 있습니다. 위에서 msgsnd() 함수와 플래그 값이 다르네요.

void *memdump = malloc(0x1fc8);
msgrcv(qid, memdump, 0x1fc8, 1, IPC_NOWAIT | MSG_COPY);

유저 영역에서 msgrcv() 함수를 호출하면 커널은 ksys_msgrcv() -> do_msgrcv() 순으로 호출합니다. 

long ksys_msgrcv(int msqid, struct msgbuf __user *msgp, size_t msgsz, long msgtyp, int msgflg)
{
	return do_msgrcv(msqid, msgp, msgsz, msgtyp, msgflg, do_msg_fill);
}

ksys_msgrcv() 함수에서 do_msgrcv() 함수의 여섯 번째 인자인 함수 포인터 msg_handler를 do_msg_fill() 로 설정한 뒤 do_msgrcv() 함수를 호출합니다.

static long do_msgrcv(int msqid, void __user *buf, size_t bufsz, long msgtyp, int msgflg,
	       long (*msg_handler)(void __user *, struct msg_msg *, size_t))
{
	int mode;
	struct msg_queue *msq;
	struct ipc_namespace *ns;
	struct msg_msg *msg, *copy = NULL;
	DEFINE_WAKE_Q(wake_q);

	ns = current->nsproxy->ipc_ns;

	if (msqid < 0 || (long) bufsz < 0)
		return -EINVAL;

	if (msgflg & MSG_COPY) {
		if ((msgflg & MSG_EXCEPT) || !(msgflg & IPC_NOWAIT))
			return -EINVAL;
		copy = prepare_copy(buf, min_t(size_t, bufsz, ns->msg_ctlmax));
		if (IS_ERR(copy))
			return PTR_ERR(copy);
	}
	mode = convert_mode(&msgtyp, msgflg);

	rcu_read_lock();
	msq = msq_obtain_object_check(ns, msqid);
	if (IS_ERR(msq)) {
		rcu_read_unlock();
		free_copy(copy);
		return PTR_ERR(msq);
	}

	for (;;) {
		struct msg_receiver msr_d;

		msg = ERR_PTR(-EACCES);
		if (ipcperms(ns, &msq->q_perm, S_IRUGO))
			goto out_unlock1;

		ipc_lock_object(&msq->q_perm);

		/* raced with RMID? */
		if (!ipc_valid_object(&msq->q_perm)) {
			msg = ERR_PTR(-EIDRM);
			goto out_unlock0;
		}

		msg = find_msg(msq, &msgtyp, mode);
		if (!IS_ERR(msg)) {
			/*
			 * Found a suitable message.
			 * Unlink it from the queue.
			 */
			if ((bufsz < msg->m_ts) && !(msgflg & MSG_NOERROR)) {
				msg = ERR_PTR(-E2BIG);
				goto out_unlock0;
			}
			/*
			 * If we are copying, then do not unlink message and do
			 * not update queue parameters.
			 */
			if (msgflg & MSG_COPY) {
				msg = copy_msg(msg, copy);
				goto out_unlock0;
			}

			list_del(&msg->m_list);
			msq->q_qnum--;
			msq->q_rtime = ktime_get_real_seconds();
			ipc_update_pid(&msq->q_lrpid, task_tgid(current));
			msq->q_cbytes -= msg->m_ts;
			percpu_counter_sub_local(&ns->percpu_msg_bytes, msg->m_ts);
			percpu_counter_sub_local(&ns->percpu_msg_hdrs, 1);
			ss_wakeup(msq, &wake_q, false);

			goto out_unlock0;
		}

		/* No message waiting. Wait for a message */
		if (msgflg & IPC_NOWAIT) {
			msg = ERR_PTR(-ENOMSG);
			goto out_unlock0;
		}

		list_add_tail(&msr_d.r_list, &msq->q_receivers);
		msr_d.r_tsk = current;
		msr_d.r_msgtype = msgtyp;
		msr_d.r_mode = mode;
		if (msgflg & MSG_NOERROR)
			msr_d.r_maxsize = INT_MAX;
		else
			msr_d.r_maxsize = bufsz;

		/* memory barrier not require due to ipc_lock_object() */
		WRITE_ONCE(msr_d.r_msg, ERR_PTR(-EAGAIN));

		/* memory barrier not required, we own ipc_lock_object() */
		__set_current_state(TASK_INTERRUPTIBLE);

		ipc_unlock_object(&msq->q_perm);
		rcu_read_unlock();
		schedule();

		/*
		 * Lockless receive, part 1:
		 * We don't hold a reference to the queue and getting a
		 * reference would defeat the idea of a lockless operation,
		 * thus the code relies on rcu to guarantee the existence of
		 * msq:
		 * Prior to destruction, expunge_all(-EIRDM) changes r_msg.
		 * Thus if r_msg is -EAGAIN, then the queue not yet destroyed.
		 */
		rcu_read_lock();

		/*
		 * Lockless receive, part 2:
		 * The work in pipelined_send() and expunge_all():
		 * - Set pointer to message
		 * - Queue the receiver task for later wakeup
		 * - Wake up the process after the lock is dropped.
		 *
		 * Should the process wake up before this wakeup (due to a
		 * signal) it will either see the message and continue ...
		 */
		msg = READ_ONCE(msr_d.r_msg);
		if (msg != ERR_PTR(-EAGAIN)) {
			/* see MSG_BARRIER for purpose/pairing */
			smp_acquire__after_ctrl_dep();

			goto out_unlock1;
		}

		 /*
		  * ... or see -EAGAIN, acquire the lock to check the message
		  * again.
		  */
		ipc_lock_object(&msq->q_perm);

		msg = READ_ONCE(msr_d.r_msg);
		if (msg != ERR_PTR(-EAGAIN))
			goto out_unlock0;

		list_del(&msr_d.r_list);
		if (signal_pending(current)) {
			msg = ERR_PTR(-ERESTARTNOHAND);
			goto out_unlock0;
		}

		ipc_unlock_object(&msq->q_perm);
	}

out_unlock0:
	ipc_unlock_object(&msq->q_perm);
	wake_up_q(&wake_q);
out_unlock1:
	rcu_read_unlock();
	if (IS_ERR(msg)) {
		free_copy(copy);
		return PTR_ERR(msg);
	}

	bufsz = msg_handler(buf, msg, bufsz);
	free_msg(msg);

	return bufsz;
}

간단하게 살펴보면 find_msg로 msg_msg 구조체 가져와서 검사한 뒤 msg_hander로 설정된 do_msg_fill() 함수로 넘어가는 구조임을 알 수 있습니다. do_msg_fill()를 수행하고 나면 free_msg()를 호출합니다. 먼저 do_msg_fill() 함수부터 보시죠!

static long do_msg_fill(void __user *dest, struct msg_msg *msg, size_t bufsz)
{
	struct msgbuf __user *msgp = dest;
	size_t msgsz;

	if (put_user(msg->m_type, &msgp->mtype))
		return -EFAULT;

	msgsz = (bufsz > msg->m_ts) ? msg->m_ts : bufsz;
	if (store_msg(msgp->mtext, msg, msgsz))
		return -EFAULT;
	return msgsz;
}

요청된 크기와 저장된 크기를 비교해서 요청 크기 > 저장 크기일 경우 저장된 크기만큼만 사이즈로 설장해준 뒤 store_msg() 함수를 호출합니다.

int store_msg(void __user *dest, struct msg_msg *msg, size_t len)
{
	size_t alen;
	struct msg_msgseg *seg;

	alen = min(len, DATALEN_MSG);
	if (copy_to_user(dest, msg + 1, alen))
		return -1;

	for (seg = msg->next; seg != NULL; seg = seg->next) {
		len -= alen;
		dest = (char __user *)dest + alen;
		alen = min(len, DATALEN_SEG);
		if (copy_to_user(dest, seg + 1, alen))
			return -1;
	}
	return 0;
}

 copy_to_user 함수로 지정된 사이즈만큼 커널에서 복사해줍니다. 이제 do_msg_fill()함수가 끝났으니 free_msg() 함수를 살펴보겠습니다. 

void free_msg(struct msg_msg *msg)
{
	struct msg_msgseg *seg;

	security_msg_msg_free(msg);

	seg = msg->next;
	kfree(msg);
	while (seg != NULL) {
		struct msg_msgseg *tmp = seg->next;

		cond_resched();
		kfree(seg);
		seg = tmp;
	}
}

msgsnd() 함수에서 할당 받은 msg_msg 구조체 안에 존재하는 세그먼트를 포함한 모든 구조체들을 해제해줍니다. 그런데 해제가 되지 않는 구조체도 있습니다. do_msgrcv() 함수를 살펴보면 중간에 플래그에 MSG_COPY가 있으면 prepare_copy(), copy_msg() 함수를 호출하는 부분이 존재하는데요. 해당 부분을 살펴보겠습니다. 

	if (msgflg & MSG_COPY) {
		if ((msgflg & MSG_EXCEPT) || !(msgflg & IPC_NOWAIT))
			return -EINVAL;
		copy = prepare_copy(buf, min_t(size_t, bufsz, ns->msg_ctlmax));
		if (IS_ERR(copy))
			return PTR_ERR(copy);
	}
    ...
    	msg = find_msg(msq, &msgtyp, mode);
		if (!IS_ERR(msg)) {
			...
			if (msgflg & MSG_COPY) {
				msg = copy_msg(msg, copy);
				goto out_unlock0;
			}

prepare_copy() 함수를 호출하면 msg_msg 구조체를 할당 받습니다.

static inline struct msg_msg *prepare_copy(void __user *buf, size_t bufsz)
{
	struct msg_msg *copy;

	/*
	 * Create dummy message to copy real message to.
	 */
	copy = load_msg(buf, bufsz);
	if (!IS_ERR(copy))
		copy->m_ts = bufsz;
	return copy;
}

 이후 copy_msg() 함수에서 memcpy() 함수로 msg의 내용을 copy에 복사합니다. 이렇게 생성된 복사본은 리턴되어 msg에 저장되고 free_msg() 함수에 의해 해제되지만 원본은 남아 있게 됩니다.

struct msg_msg *copy_msg(struct msg_msg *src, struct msg_msg *dst)
{
	struct msg_msgseg *dst_pseg, *src_pseg;
	size_t len = src->m_ts;
	size_t alen;

	if (src->m_ts > dst->m_ts)
		return ERR_PTR(-EINVAL);

	alen = min(len, DATALEN_MSG);
	memcpy(dst + 1, src + 1, alen);

	for (dst_pseg = dst->next, src_pseg = src->next;
	     src_pseg != NULL;
	     dst_pseg = dst_pseg->next, src_pseg = src_pseg->next) {

		len -= alen;
		alen = min(len, DATALEN_SEG);
		memcpy(dst_pseg + 1, src_pseg + 1, alen);
	}

	dst->m_type = src->m_type;
	dst->m_ts = src->m_ts;

	return dst;
}

---

 

https://syst3mfailure.io/wall-of-perdition/

https://pwn.college/software-exploitation/kernel-exploitation/