Skip to contentSkip to conversation

idr: fix invalid ptr dereference on item delete

PATCH Matthew Wilcox 3 participants 8 messages May 18, 2018 – May 21, 2018

Subsystems (2)
lore
Share & tools
lore

Matthew Wilcox

author maintainer
#0 lore raw

It'd be nice if you cc'd the person who wrote the code you're patching. You'd get a response a lot quicker than waiting until I happened to notice the email in a different forum.

Thanks for finding the situation that leads to the bug. Your fix is incorrect; it's legitimate to store a NULL value at offset 0, and your patch makes it impossible to delete. Fortunately, the test-suite covers that case ;-)

Andrew, can you take this through your tree for extra testing?

--- >8 ---

From: Matthew Wilcox <[email protected]>

If the radix tree underlying the IDR happens to be full and we attempt to remove an id which is larger than any id in the IDR, we will call __radix_tree_delete() with an uninitialised 'slot' pointer, at which point anything could happen. This was easiest to hit with a single entry at id 0 and attempting to remove a non-0 id, but it could have happened with 64 entries and attempting to remove an id >= 64.

Fixes 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
Reported-by [email protected]
lib/radix-tree.c +3 -1
index da9e10c827df..4dd4fbc7279c 100644
@@ -2036,10 +2036,12 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
 			     unsigned long index, void *item)
 {
 	struct radix_tree_node *node = NULL;
-	void __rcu **slot;
+	void __rcu **slot = NULL;
 	void *entry;
 
 	entry = __radix_tree_lookup(root, index, &node, &slot);
+	if (!slot)
+		return NULL;
 	if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
 						get_slot_offset(node, slot))))
 		return NULL;
tools/testing/radix-tree/idr-test.c +7 -0
index 1c18617951dd..410ca58bbe9c 100644
@@ -254,6 +254,13 @@ void idr_checks(void)
 	idr_remove(&idr, 0xfedcba98U);
 	idr_remove(&idr, 0);
 
+	assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == 0);
+	idr_remove(&idr, 1);
+	for (i = 1; i < RADIX_TREE_MAP_SIZE; i++)
+		assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == i);
+	idr_remove(&idr, 1 << 30);
+	idr_destroy(&idr);
+
 	for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) {
 		struct item *item = item_create(i, 0);
 		assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i);

--- original email ---

If an IDR contains a single entry at index==0, the underlying radix tree has a single item in its root node, in which case __radix_tree_lookup(index!=0) doesn't set its *@nodep argument (in addition to returning NULL).

However, the tree itself is not empty, i.e. the tree root doesn't have IDR_FREE tag.

As a result, on an attempt to remove an index!=0 entry from such an IDR, radix_tree_delete_item doesn't return early and calls __radix_tree_delete with invalid parameters which are then dereferenced.

---
 lib/radix-tree.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
lib/radix-tree.c +3 -2
index da9e10c827df..10ff1bfae952 100644
@@ -2040,8 +2040,9 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
 	void *entry;
 
 	entry = __radix_tree_lookup(root, index, &node, &slot);
-	if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
-						get_slot_offset(node, slot))))
+	if (!entry && (!is_idr(root) || !node ||
+		       node_tag_get(root, node, IDR_FREE,
+				    get_slot_offset(node, slot))))
 		return NULL;
 
 	if (item && entry != item)
#1 lore raw
Quoted 3 lines · Matthew Wilcox

It'd be nice if you cc'd the person who wrote the code you're patching. You'd get a response a lot quicker than waiting until I happened to notice the email in a different forum.

I sent it to someone called "Matthew Wilcox <[email protected]>". Also I cc'd that guy when I only started to point the finger at IDR as the suspected culprit in that syzcaller report. I thought it was him who wrote the code...

Quoted 4 lines

Thanks for finding the situation that leads to the bug. Your fix is incorrect; it's legitimate to store a NULL value at offset 0, and your patch makes it impossible to delete. Fortunately, the test-suite covers that case ;-)

How do you build it? I wish I had it when debugging but I got linking errors due to missing spin_lock_init, so I decided it wasn't up-to-date.

Thanks,
Roman.

P.S. I'll forward your message to all the recepients of my patch, to let them know it's wrong and you have a better one.

author maintainer
#2 lore raw
Quoted 9 lines · Roman Kagan
Quoted 3 lines · Matthew Wilcox

It'd be nice if you cc'd the person who wrote the code you're patching. You'd get a response a lot quicker than waiting until I happened to notice the email in a different forum.

I sent it to someone called "Matthew Wilcox <[email protected]>". Also I cc'd that guy when I only started to point the finger at IDR as the suspected culprit in that syzcaller report. I thought it was him who wrote the code...

I didn't get them ;-( Sorry.

Quoted 7 lines
Quoted 4 lines

Thanks for finding the situation that leads to the bug. Your fix is incorrect; it's legitimate to store a NULL value at offset 0, and your patch makes it impossible to delete. Fortunately, the test-suite covers that case ;-)

How do you build it? I wish I had it when debugging but I got linking errors due to missing spin_lock_init, so I decided it wasn't up-to-date.

Yeah, I inadvertently broke it with commit f6bb2a2c0b81 ("xarray: add the xa_lock to the radix_tree_root")

Andrew has a patch to fix it in his tree. All you need is:

+++ b/tools/include/linux/spinlock.h
@@ -8,6 +8,7 @@
#define spinlock_t pthread_mutex_t
#define DEFINE_SPINLOCK(x) pthread_mutex_t x = PTHREAD_MUTEX_INITIALIZER;
#define __SPIN_LOCK_UNLOCKED(x) (pthread_mutex_t)PTHREAD_MUTEX_INITIALIZ
ER
+#define spin_lock_init(x) pthread_mutex_init(x, NULL);

#define spin_lock_irqsave(x, f) (void)f, pthread_mutex_lock(x)
#define spin_unlock_irqrestore(x, f) (void)f, pthread_mutex_unlock(x)

Quoted 5 lines

Thanks,
Roman.

P.S. I'll forward your message to all the recepients of my patch, to let them know it's wrong and you have a better one.

Thanks!

maintainer
#3 lore raw
In reply to Matthew Wilcox
Quoted 11 lines · On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <[email protected]> wrote:

If the radix tree underlying the IDR happens to be full and we attempt to remove an id which is larger than any id in the IDR, we will call __radix_tree_delete() with an uninitialised 'slot' pointer, at which point anything could happen. This was easiest to hit with a single entry at id 0 and attempting to remove a non-0 id, but it could have happened with 64 entries and attempting to remove an id >= 64.

Fixes 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
Reported-by [email protected]

Neither of the changelogs I'm seeing attempt to describe the end-user impact of the bug. People like to know that so they can decide which kernel version(s) need patching, so please always remember it.

Looknig at the sysbot report, the impact is at least "privileged user can trigger a WARN", but I assume there could be worse, as-yet-undiscovered impacts. So I'm thinking a cc:stable is needed, yes?

author maintainer
#4 lore raw
Quoted 8 lines · Andrew Morton
Quoted 7 lines · On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <[email protected]> wrote:

If the radix tree underlying the IDR happens to be full and we attempt to remove an id which is larger than any id in the IDR, we will call __radix_tree_delete() with an uninitialised 'slot' pointer, at which point anything could happen. This was easiest to hit with a single entry at id 0 and attempting to remove a non-0 id, but it could have happened with 64 entries and attempting to remove an id >= 64.

Quoted 8 lines
Quoted 4 lines
Fixes 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
Reported-by [email protected]

Neither of the changelogs I'm seeing attempt to describe the end-user impact of the bug. People like to know that so they can decide which kernel version(s) need patching, so please always remember it.

The problem is that it could be user-triggerable a dozen different ways.

Quoted 4 lines

Looknig at the sysbot report, the impact is at least "privileged user can trigger a WARN", but I assume there could be worse, as-yet-undiscovered impacts. So I'm thinking a cc:stable is needed, yes?

I thought if I used the Fixes: tag it would automatically get picked up. Did I misunderstand? I can imagine many different parts of the kernel that use the IDR could trigger such a warning (although syzbot should probably have tripped over them before now) so I wouldn't downplay it to "only privileged users".

#5 lore raw
In reply to Andrew Morton
Quoted 9 lines · Andrew Morton
Quoted 7 lines · On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <[email protected]> wrote:

If the radix tree underlying the IDR happens to be full and we attempt to remove an id which is larger than any id in the IDR, we will call __radix_tree_delete() with an uninitialised 'slot' pointer, at which point anything could happen. This was easiest to hit with a single entry at id 0 and attempting to remove a non-0 id, but it could have happened with 64 entries and attempting to remove an id >= 64.

Quoted 8 lines
Quoted 4 lines
Fixes 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
Reported-by [email protected]

Neither of the changelogs I'm seeing attempt to describe the end-user impact of the bug. People like to know that so they can decide which kernel version(s) need patching, so please always remember it.

That's my fault, Matthew may not have seen the original discussion among the KVM folks.

Quoted 2 lines

Looknig at the sysbot report, the impact is at least "privileged user can trigger a WARN", but I assume there could be worse,

Unfortunately it is worse: the syzcaller test boils down to opening /dev/kvm, creating an eventfd, and calling a couple of KVM ioctls. None of this requires superuser. And the result is dereferencing an uninitialized pointer which is likely a crash.

Quoted 2 lines

as-yet-undiscovered impacts. So I'm thinking a cc:stable is needed, yes?

Well the specific path caught by syzbot is via KVM_HYPERV_EVENTD ioctl which is new in 4.17. But I guess there are other user-triggerable paths, so cc:stable is probably justified.

Thanks,
Roman.

author maintainer
#6 lore raw
Quoted 30 lines · Roman Kagan
Quoted 9 lines · Andrew Morton
Quoted 7 lines · On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <[email protected]> wrote:

If the radix tree underlying the IDR happens to be full and we attempt to remove an id which is larger than any id in the IDR, we will call __radix_tree_delete() with an uninitialised 'slot' pointer, at which point anything could happen. This was easiest to hit with a single entry at id 0 and attempting to remove a non-0 id, but it could have happened with 64 entries and attempting to remove an id >= 64.

Quoted 8 lines
Quoted 4 lines
Fixes 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
Reported-by [email protected]

Neither of the changelogs I'm seeing attempt to describe the end-user impact of the bug. People like to know that so they can decide which kernel version(s) need patching, so please always remember it.

That's my fault, Matthew may not have seen the original discussion among the KVM folks.

Quoted 2 lines

Looknig at the sysbot report, the impact is at least "privileged user can trigger a WARN", but I assume there could be worse,

Unfortunately it is worse: the syzcaller test boils down to opening /dev/kvm, creating an eventfd, and calling a couple of KVM ioctls. None of this requires superuser. And the result is dereferencing an uninitialized pointer which is likely a crash.

Quoted 6 lines
Quoted 2 lines

as-yet-undiscovered impacts. So I'm thinking a cc:stable is needed, yes?

Well the specific path caught by syzbot is via KVM_HYPERV_EVENTD ioctl which is new in 4.17. But I guess there are other user-triggerable paths, so cc:stable is probably justified.

We have around 250 calls to idr_remove() in the kernel today. Many of them pass an ID which is embedded in the object they're removing, so they're safe. Picking a few likely candidates:

drivers/firewire/core-cdev.c looks unsafe; the ID comes from an ioctl. drivers/gpu/drm/amd/amdgpu/amdgpu_ctx.c is similar drivers/atm/nicstar.c could be taken down by a handcrafted packet

maintainer
#7 lore raw
Quoted 38 lines · On Sat, 19 May 2018 07:14:45 -0700 Matthew Wilcox <[email protected]> wrote:
Quoted 30 lines · Roman Kagan
Quoted 9 lines · Andrew Morton
Quoted 7 lines · On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <[email protected]> wrote:

If the radix tree underlying the IDR happens to be full and we attempt to remove an id which is larger than any id in the IDR, we will call __radix_tree_delete() with an uninitialised 'slot' pointer, at which point anything could happen. This was easiest to hit with a single entry at id 0 and attempting to remove a non-0 id, but it could have happened with 64 entries and attempting to remove an id >= 64.

Quoted 8 lines
Quoted 4 lines
Fixes 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
Reported-by [email protected]

Neither of the changelogs I'm seeing attempt to describe the end-user impact of the bug. People like to know that so they can decide which kernel version(s) need patching, so please always remember it.

That's my fault, Matthew may not have seen the original discussion among the KVM folks.

Quoted 2 lines

Looknig at the sysbot report, the impact is at least "privileged user can trigger a WARN", but I assume there could be worse,

Unfortunately it is worse: the syzcaller test boils down to opening /dev/kvm, creating an eventfd, and calling a couple of KVM ioctls. None of this requires superuser. And the result is dereferencing an uninitialized pointer which is likely a crash.

Quoted 6 lines
Quoted 2 lines

as-yet-undiscovered impacts. So I'm thinking a cc:stable is needed, yes?

Well the specific path caught by syzbot is via KVM_HYPERV_EVENTD ioctl which is new in 4.17. But I guess there are other user-triggerable paths, so cc:stable is probably justified.

Quoted 7 lines

We have around 250 calls to idr_remove() in the kernel today. Many of them pass an ID which is embedded in the object they're removing, so they're safe. Picking a few likely candidates:

drivers/firewire/core-cdev.c looks unsafe; the ID comes from an ioctl. drivers/gpu/drm/amd/amdgpu/amdgpu_ctx.c is similar drivers/atm/nicstar.c could be taken down by a handcrafted packet

OK, thanks, I sprinkled some of the above words into the changelog ad added cc:stable.

From: Matthew Wilcox <[email protected]>
Subject: idr: fix invalid ptr dereference on item delete

If the radix tree underlying the IDR happens to be full and we attempt to remove an id which is larger than any id in the IDR, we will call __radix_tree_delete() with an uninitialised 'slot' pointer, at which point anything could happen. This was easiest to hit with a single entry at id 0 and attempting to remove a non-0 id, but it could have happened with 64 entries and attempting to remove an id >= 64.

Roman said:

The syzcaller test boils down to opening /dev/kvm, creating an eventfd, and calling a couple of KVM ioctls. None of this requires superuser. And the result is dereferencing an uninitialized pointer which is likely a crash. The specific path caught by syzbot is via KVM_HYPERV_EVENTD ioctl which is new in 4.17. But I guess there are other user-triggerable paths, so cc:stable is probably justified.

Matthew added:

We have around 250 calls to idr_remove() in the kernel today. Many of them pass an ID which is embedded in the object they're removing, so they're safe. Picking a few likely candidates:

drivers/firewire/core-cdev.c looks unsafe; the ID comes from an ioctl. drivers/gpu/drm/amd/amdgpu/amdgpu_ctx.c is similar drivers/atm/nicstar.c could be taken down by a handcrafted packet

Fixes 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
Reported-by [email protected]

---

 lib/radix-tree.c                    |    4 +++-
 tools/testing/radix-tree/idr-test.c |    7 +++++++
 2 files changed, 10 insertions(+), 1 deletion(-)
lib/radix-tree.c renamed from lib/radix-tree.c~idr-fix-invalid-ptr-dereference-on-item-delete +3 -1
diff -puN lib/radix-tree.c~idr-fix-invalid-ptr-dereference-on-item-delete lib/radix-tree.c
@@ -2034,10 +2034,12 @@ void *radix_tree_delete_item(struct radi
 			     unsigned long index, void *item)
 {
 	struct radix_tree_node *node = NULL;
-	void __rcu **slot;
+	void __rcu **slot = NULL;
 	void *entry;
 
 	entry = __radix_tree_lookup(root, index, &node, &slot);
+	if (!slot)
+		return NULL;
 	if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
 						get_slot_offset(node, slot))))
 		return NULL;
tools/testing/radix-tree/idr-test.c renamed from tools/testing/radix-tree/idr-test.c~idr-fix-invalid-ptr-dereference-on-item-delete +7 -0
diff -puN tools/testing/radix-tree/idr-test.c~idr-fix-invalid-ptr-dereference-on-item-delete tools/testing/radix-tree/idr-test.c
@@ -252,6 +252,13 @@ void idr_checks(void)
 	idr_remove(&idr, 3);
 	idr_remove(&idr, 0);
 
+	assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == 0);
+	idr_remove(&idr, 1);
+	for (i = 1; i < RADIX_TREE_MAP_SIZE; i++)
+		assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == i);
+	idr_remove(&idr, 1 << 30);
+	idr_destroy(&idr);
+
 	for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) {
 		struct item *item = item_create(i, 0);
 		assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i);

_