[PATCH] ptrlist: use after free in last_ptr_list()

[PATCH] ptrlist: use after free in last_ptr_list()

[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 <dan.carpenter@oracle.com>
---
 ptrlist.h | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/ptrlist.h b/ptrlist.h
index 61e159f..6f90c8f 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -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);
 }
 
-- 
2.8.1

Re: [PATCH] ptrlist: use after free in last_ptr_list()

[Luc Van Oostenryck]

On Mon, Jun 13, 2016 at 12:45:17PM +0300, Dan Carpenter wrote:
> 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 <dan.carpenter@oracle.com>
> ---
>  ptrlist.h | 2 ++
>  1 file changed, 2 insertions(+)
> 
> diff --git a/ptrlist.h b/ptrlist.h
> index 61e159f..6f90c8f 100644
> --- a/ptrlist.h
> +++ b/ptrlist.h
> @@ -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

Re: [PATCH] ptrlist: use after free in last_ptr_list()

[Christopher Li]

On Wed, Nov 2, 2016 at 8:48 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> +     while (list->nr == 0)
>> +             list = list->prev;

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

>                 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

Re: [PATCH] ptrlist: use after free in last_ptr_list()

[Luc Van Oostenryck]

On Wed, Nov 02, 2016 at 10:52:35PM +0800, Christopher Li wrote:
> On Wed, Nov 2, 2016 at 8:48 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >> +     while (list->nr == 0)
> >> +             list = list->prev;
> 
> Yes, it can deed loop here when the whole list is empty.
> 
> >                 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
> --

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

Re: [PATCH] ptrlist: use after free in last_ptr_list()

[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.

Re: [PATCH] ptrlist: use after free in last_ptr_list()

[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


On Fri, Nov 4, 2016 at 6:44 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> 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.

Re: [PATCH] ptrlist: use after free in last_ptr_list()

[Luc Van Oostenryck]

On Sat, Nov 05, 2016 at 08:30:31AM +0800, Christopher Li wrote:
> 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

Re: [PATCH] ptrlist: use after free in last_ptr_list()

[Luc Van Oostenryck]

On Sun, Nov 06, 2016 at 09:49:38AM +0100, Luc Van Oostenryck wrote:
> On Sat, Nov 05, 2016 at 08:30:31AM +0800, Christopher Li wrote:
> > 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

Re: [PATCH] ptrlist: use after free in last_ptr_list()

[Christopher Li]

On Mon, Nov 7, 2016 at 6:00 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> 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

Re: [PATCH] ptrlist: use after free in last_ptr_list()

[Luc Van Oostenryck]

On Thu, Nov 17, 2016 at 06:46:44AM +0800, Christopher Li wrote:
> On Mon, Nov 7, 2016 at 6:00 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > 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
> --

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


Luc