Skip to contentSkip to conversation

ptrlist: use after free in last_ptr_list()

PATCH In review Dan Carpenter 3 participants 10 messages Jun 13, 2016 – Nov 16, 2016 Sparse checker

lore
Share & tools
lore

Dan Carpenter

author
#0 lore raw

PATCH 1/1 ptrlist: use after free in last_ptr_list()

This change is similar to 2e7dd34d11cb ('ptrlist: reading deleted items in NEXT_PTR_LIST()'). If we use DELETE_CURRENT_PTR() then we can end up with a list->nr that is zero meaning that we have to go back another list->prev to find what we want. Otherwise we dereference 0xf0f0f0f0 and crash.

Signed-off-by Dan Carpenter <[email protected]>
---
 ptrlist.h | 2 ++
 1 file changed, 2 insertions(+)
ptrlist.h +2 -0
index 61e159f..6f90c8f 100644
@@ -78,6 +78,8 @@ static inline void *last_ptr_list(struct ptr_list *list)
 	if (!list)
 		return NULL;
 	list = list->prev;
+	while (list->nr == 0)
+		list = list->prev;
 	return PTR_ENTRY(list, list->nr-1);
 }
Signature · 1 line
2.8.1
#1 lore raw
Quoted 17 lines · Dan Carpenter

This change is similar to 2e7dd34d11cb ('ptrlist: reading deleted items in NEXT_PTR_LIST()'). If we use DELETE_CURRENT_PTR() then we can end up with a list->nr that is zero meaning that we have to go back another list->prev to find what we want. Otherwise we dereference 0xf0f0f0f0 and crash.

Signed-off-by Dan Carpenter <[email protected]>
---
 ptrlist.h | 2 ++
 1 file changed, 2 insertions(+)
ptrlist.h +0 -0
index 61e159f..6f90c8f 100644

ptrlist.h static inline void *last_ptr_list(struct ptr_list *list) · line 85

Quoted 8 lines
ptrlist.h +2 -0
@@ -78,6 +78,8 @@ static inline void *last_ptr_list(struct ptr_list *list)
 	if (!list)
 		return NULL;
 	list = list->prev;
+	while (list->nr == 0)
+		list = list->prev;
 	return PTR_ENTRY(list, list->nr-1);
 }

Hi,

while trying to find a test case for this one, I noticed that something as simple as:

	void rem_rev(struct vpl *list)
	{
		void *last;
		void *ptr;
	
		FOR_EACH_PTR_REVERSE(list, ptr) {
			DELETE_CURRENT_PTR(ptr);
			last = last_ptr_list((struct ptr_list *)list);
		} END_FOR_EACH_PTR_REVERSE(ptr);
	}

loops forever on a list with 1 element with your patch.
Without your patch, last_ptr_list() return an invalid pointer instead of NULL.

So, I don't think your patch is the right solution but, yes somethings should be done about this.

Cheers,
Luc Van Oostenryck

maintainer
#2 lore raw
Quoted 2 lines · Luc Van Oostenryck

ptrlist.h static inline void *last_ptr_list(struct ptr_list *list) · line 82

Quoted 2 lines
ptrlist.h +2 -0
+     while (list->nr == 0)
+             list = list->prev;

Yes, it can deed loop here when the whole list is empty.

Quoted 8 lines
                FOR_EACH_PTR_REVERSE(list, ptr) {
                        DELETE_CURRENT_PTR(ptr);
                        last = last_ptr_list((struct ptr_list *)list);
                } END_FOR_EACH_PTR_REVERSE(ptr);
        }

loops forever on a list with 1 element with your patch.
Without your patch, last_ptr_list() return an invalid pointer instead of NULL.

I can see what is going on now. The while loop should check for the list->prev has been loop back to the tail of the list.

Some thing like this should fix it, I haven't test it at all.

list = tail = list->prev;

while (list->nr == 0) {
     list = list->prev;
     if (list == tail)
           return NULL;
}

Chris

#3 lore raw
Quoted 23 lines · Christopher Li
Quoted 2 lines · Luc Van Oostenryck

ptrlist.h static inline void *last_ptr_list(struct ptr_list *list) · line 82

Quoted 2 lines
ptrlist.h +2 -0
+     while (list->nr == 0)
+             list = list->prev;

Yes, it can deed loop here when the whole list is empty.

Quoted 8 lines
                FOR_EACH_PTR_REVERSE(list, ptr) {
                        DELETE_CURRENT_PTR(ptr);
                        last = last_ptr_list((struct ptr_list *)list);
                } END_FOR_EACH_PTR_REVERSE(ptr);
        }

loops forever on a list with 1 element with your patch.
Without your patch, last_ptr_list() return an invalid pointer instead of NULL.

I can see what is going on now. The while loop should check for the list->prev has been loop back to the tail of the list.

Some thing like this should fix it, I haven't test it at all.

list = tail = list->prev;

Quoted 8 lines
while (list->nr == 0) {
     list = list->prev;
     if (list == tail)
           return NULL;
}

Chris
--

Yes, something like this should do, indeed.
But by looking at the code, I think that 'first_ptr_list()' is also not immunised against the same problem.

Also these two functions first_ & last_ptr_list() were trivial ones but now they maybe become a bit too heavy to be inlined?

Or, maybe we should create a 'safe' version of those two, not inlined, and which do the correct list walking?
Or maybe we need to have a macro like LAST_PTR() which do everything needed, like DELETE_CURRENT_PTR() do?

I would vote for the safe version.

Luc

#4 lore raw

Another thing I noticed is that after using DELETE_CURRENT_PTR() the next PREPARE_PTR_LIST() will fail or give wrong result if the list hasn't been repacked first.

Maybe it's obvious but I wouldn't be surprised if there is even more situations that need to be protected against empty blocks.

maintainer
#5 lore raw

Those function originally all assume the list
are packed.

Is there usage case in current sparse that
feed unpacked list to those function?

Chris

Quoted 6 lines · Luc Van Oostenryck

Another thing I noticed is that after using DELETE_CURRENT_PTR() the next PREPARE_PTR_LIST() will fail or give wrong result if the list hasn't been repacked first.

Maybe it's obvious but I wouldn't be surprised if there is even more situations that need to be protected against empty blocks.

#6 lore raw
Quoted 7 lines · Christopher Li

Those function originally all assume the list
are packed.

Is there usage case in current sparse that
feed unpacked list to those function?

Chris

The situation is not black & white.

There is two 'unsafe' cases. By 'unsafe' I mean that DELETE_CURRENT_PTR() is used but without PACK_PTR_LIST() and the end of the iteration like done elsewhere.

OTOH, I've added at the beginning of every ptr_list loops some assert() that check if the ptr_list is packed or not and none ever triggered, even when LIST_NODE_NR is changed from 29 to 1 (to force list->nr == 0 at each delete). Also, assertions doing bound checking on ptr_list::list[] accesses never triggered.

So, to answer your question, it seems that in the current sparse code we don't feed unpacked lists to the 'dangerous' functions but for the two unsafe case you can't guarantee thsi just by looking at the local code
(or it's just by chance).

I think that for the moment, it's best to simply add PACK_PTR_LIST() at the end of the two unsafe cases (patch will come later).
OTOH, I feel this whole situation is a bit fragile.

NOTE: for the moment, I've only checked all this with the testsuite. I will recheck on more substantial amount of code but this will need to wait a little bit.

Luc

#7 lore raw
Quoted 8 lines · Luc Van Oostenryck
Quoted 7 lines · Christopher Li

Those function originally all assume the list
are packed.

Is there usage case in current sparse that
feed unpacked list to those function?

Chris

OK, I've checked this on a more substantial amount of code than the testsuite: the kernel for x86-64 with allyesconfig and I confirm that there is not a single out-of-bounds access to any ->list[], wich is what matters.

Nevertheless, there are two cases (in cse.c and evaluate.c) where elements are deleted from a list which is not directly repacked at the end of the loop and it's not obvious in the code why it's OK to not repack them.

Luc

maintainer
#8 lore raw
Quoted 9 lines · Luc Van Oostenryck

OK, I've checked this on a more substantial amount of code than the testsuite: the kernel for x86-64 with allyesconfig and I confirm that there is not a single out-of-bounds access to any ->list[], wich is what matters.

Nevertheless, there are two cases (in cse.c and evaluate.c) where elements are deleted from a list which is not directly repacked at the end of the loop and it's not obvious in the code why it's OK to not repack them.

Thanks for the extensive testing. As for the repacking, I think its better to repack the list to after the delete of the entry. However, we don't want to repack the list if there is not deletion at all.

How about this, we can introduce a bit field on "struct ptr_list" to keep track of the list needs repack or not. On deletion the ptr_list will be dirty. The other function which assuming the packed list will check the dirty bit and complain if list is not packed.

We can even make keep the "struct ptr_list" the same size. Just squeeze some bits from "int nr". However, that will break the binary interface of sparse as a library. The application link with sparse will need to be recompiled.

Chris

#9 lore raw
Quoted 21 lines · Christopher Li
Quoted 9 lines · Luc Van Oostenryck

OK, I've checked this on a more substantial amount of code than the testsuite: the kernel for x86-64 with allyesconfig and I confirm that there is not a single out-of-bounds access to any ->list[], wich is what matters.

Nevertheless, there are two cases (in cse.c and evaluate.c) where elements are deleted from a list which is not directly repacked at the end of the loop and it's not obvious in the code why it's OK to not repack them.

Thanks for the extensive testing. As for the repacking, I think its better to repack the list to after the delete of the entry. However, we don't want to repack the list if there is not deletion at all.

How about this, we can introduce a bit field on "struct ptr_list" to keep track of the list needs repack or not. On deletion the ptr_list will be dirty. The other function which assuming the packed list will check the dirty bit and complain if list is not packed.

Quoted 7 lines

We can even make keep the "struct ptr_list" the same size. Just squeeze some bits from "int nr". However, that will break the binary interface of sparse as a library. The application link with sparse will need to be recompiled.

Chris
--

Sound good.
I'll look at this, probably tomorrow.

Luc