Integer Overflow in Latest macOS/iOS Kernel

Posted on | In

There exists an integer overflow in kqueue syscall which can lead to kernel deadlock(Or crash on some devices) on latest macOS and iOS. kqueue in BSD is just like epoll in Linux which powers IO multiplexing. It means users can monitor a set of actions of file descriptors, like read or write available. At the same time, an object of kqueue in kernel is also a file descriptor in user space, so users can monitor a file descriptor of kqueue object by kqueue. The kqueues which monitor other objects are called parent kqueue, so we can name the kqueue to be monitored as child kqueue, it is fine until now because they are both file descriptors. The problem is that the user can make a circular kqueue which means the two kqueues can monitor each other.

Lets look at the source. The function associated with this issue lies in bsd/kern/kern_event.c named kqueue_kqfilter. This function is called when the child kqueue is attached to the list of parent kqueue. This is a piece of comment in this function. 

1
2
3
4
5
6
7
8
9
10
 
/*
 * We have to avoid creating a cycle when nesting kqueues
 * inside another.  Rather than trying to walk the whole
 * potential DAG of nested kqueues, we just use a simple
 * ceiling protocol.  When a kqueue is inserted into another,
 * we check that the (future) parent is not already nested
 * into another kqueue at a lower level than the potenial
 * child (because it could indicate a cycle).  If that test
 * passes, we just mark the nesting levels accordingly.
 */

It seems fine because the level of child will always be lower than the parent. But the level field of kqueue is just a 16 bit unsigned integer which means we can overflow it easily. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
/*
 * kqueue - common core definition of a kqueue
 *
 *          No real structures are allocated of this type. They are
 *          either kqfile objects or kqworkq objects - each of which is
 *          derived from this definition.
 */
struct kqueue {
	struct waitq_set    kq_wqs;       /* private waitq set */
	lck_spin_t          kq_lock;      /* kqueue lock */
	uint16_t            kq_state;     /* state of the kq */
	uint16_t            kq_level;     /* nesting level of the kq */
	uint32_t            kq_count;     /* number of queued events */
	struct proc         *kq_p;        /* process containing kqueue */
	struct kqtailq      kq_queue[1];  /* variable array of kqtailq structs */
};
 

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 int kqueue_kqfilter {
	...
	if (parentkq->kq_level > 0 &&
	    parentkq->kq_level < kq->kq_level)
	{
		kqunlock(parentkq);
		kn->kn_flags = EV_ERROR;
		kn->kn_data = EINVAL;
		return 0;
	} else {
		/* set parent level appropriately */
		if (parentkq->kq_level == 0)
			parentkq->kq_level = 2;
		if (parentkq->kq_level < kq->kq_level + 1)
			parentkq->kq_level = kq->kq_level + 1;
		kqunlock(parentkq);

		kn->kn_filtid = EVFILTID_KQREAD;
		kqlock(kq);
		KNOTE_ATTACH(&kqf->kqf_sel.si_note, kn);
		/* indicate nesting in child, if needed */
		if (kq->kq_level == 0)
			kq->kq_level = 1;

		int count = kq->kq_count;
		kqunlock(kq);
		return (count > 0);
	}
	...
}

Line 16 is the root cause of this integer overflow. When the kq->kq_level is 65535 and parentkq->kq_level is 2(Changed to 2 when it is 0), the parentkq->kq_level will be set to 0. When we do this in the opposite way, it can bypass the condition of the if statement.

Download Proof of concept.

How to reproduce:

  1. clang circular_queue.c -o circular_queue
  2. ./circular_queue

After that you can see a kernel crash or kernel deadlock.

Information about my device(sw_vers):
ProductName: Mac OS X
ProductVersion: 10.13.3
BuildVersion: 17D47

This poc is also worked on my iOS 11.0.2 of iPhone 8 Plus, I believe it can also work on latest iOS 11.2.5.

Update on July 5, 2018: This issue still exists on latest macOS 10.13.5 and iOS 11.4.