Re: [PATCH] kasan: improve double-free detection

[Alexander Potapenko]

On Mon, May 2, 2016 at 1:41 PM, Dmitry Vyukov <dvyukov@xxxxxxxxxx> wrote:
> On Mon, May 2, 2016 at 12:09 PM, Dmitry Vyukov <dvyukov@xxxxxxxxxx> wrote:
>> On Mon, May 2, 2016 at 11:49 AM, Kuthonuzo Luruo
>> <kuthonuzo.luruo@xxxxxxx> wrote:
>>> Hi Alexander/Andrey/Dmitry,
>>>
>>> For your consideration/review. Thanks!
>>>
>>> Kuthonuzo Luruo
>>>
>>> Currently, KASAN may fail to detect concurrent deallocations of the same
>>> object due to a race in kasan_slab_free(). This patch makes double-free
>>> detection more reliable by atomically setting allocation state for object
>>> to KASAN_STATE_QUARANTINE iff current state is KASAN_STATE_ALLOC.
>>>
>>> Tested using a modified version of the 'slab_test' microbenchmark where
>>> allocs occur on CPU 0; then all other CPUs concurrently attempt to free the
>>> same object.
>>>
>>> Signed-off-by: Kuthonuzo Luruo <kuthonuzo.luruo@xxxxxxx>
>>> ---
>>>  mm/kasan/kasan.c |   32 ++++++++++++++++++--------------
>>>  mm/kasan/kasan.h |    5 ++---
>>>  2 files changed, 20 insertions(+), 17 deletions(-)
>>>
>>> diff --git a/mm/kasan/kasan.c b/mm/kasan/kasan.c
>>> index ef2e87b..4fc4e76 100644
>>> --- a/mm/kasan/kasan.c
>>> +++ b/mm/kasan/kasan.c
>>> @@ -511,23 +511,28 @@ void kasan_poison_slab_free(struct kmem_cache *cache, void *object)
>>>  bool kasan_slab_free(struct kmem_cache *cache, void *object)
>>>  {
>>>  #ifdef CONFIG_SLAB
>>> +       struct kasan_alloc_meta *alloc_info;
>>> +       struct kasan_free_meta *free_info;
>>> +
>>>         /* RCU slabs could be legally used after free within the RCU period */
>>>         if (unlikely(cache->flags & SLAB_DESTROY_BY_RCU))
>>>                 return false;
>>>
>>> -       if (likely(cache->flags & SLAB_KASAN)) {
>>> -               struct kasan_alloc_meta *alloc_info =
>>> -                       get_alloc_info(cache, object);
>>> -               struct kasan_free_meta *free_info =
>>> -                       get_free_info(cache, object);
>>> -
>>> -               switch (alloc_info->state) {
>>> -               case KASAN_STATE_ALLOC:
>>> -                       alloc_info->state = KASAN_STATE_QUARANTINE;
>>> -                       quarantine_put(free_info, cache);
>>> -                       set_track(&free_info->track, GFP_NOWAIT);
>>> -                       kasan_poison_slab_free(cache, object);
>>> -                       return true;
>>> +       if (unlikely(!(cache->flags & SLAB_KASAN)))
>>> +               return false;
>>> +
>>> +       alloc_info = get_alloc_info(cache, object);
>>> +
>>> +       if (cmpxchg(&alloc_info->state, KASAN_STATE_ALLOC,
>>> +                               KASAN_STATE_QUARANTINE) == KASAN_STATE_ALLOC) {
>>> +               free_info = get_free_info(cache, object);
>>> +               quarantine_put(free_info, cache);
>>> +               set_track(&free_info->track, GFP_NOWAIT);
>>> +               kasan_poison_slab_free(cache, object);
>>> +               return true;
>>> +       }
>>> +
>>> +       switch (alloc_info->state) {
>>>                 case KASAN_STATE_QUARANTINE:
>>>                 case KASAN_STATE_FREE:
>>>                         pr_err("Double free");
>>> @@ -535,7 +540,6 @@ bool kasan_slab_free(struct kmem_cache *cache, void *object)
>>>                         break;
>>>                 default:
>>>                         break;
>>> -               }
>>>         }
>>>         return false;
>>>  #else
>>> diff --git a/mm/kasan/kasan.h b/mm/kasan/kasan.h
>>> index 7da78a6..8c22a96 100644
>>> --- a/mm/kasan/kasan.h
>>> +++ b/mm/kasan/kasan.h
>>> @@ -75,9 +75,8 @@ struct kasan_track {
>>>
>>>  struct kasan_alloc_meta {
>>>         struct kasan_track track;
>>> -       u32 state : 2;  /* enum kasan_state */
>>> -       u32 alloc_size : 30;
>>> -       u32 reserved;
>>> +       u32 state;      /* enum kasan_state */
>>> +       u32 alloc_size;
>>>  };
>>>
>>>  struct kasan_free_meta {
>>
>>
>> Hi Kuthonuzo,
>>
>> I agree that it's something we need to fix (user-space ASAN does
>> something along these lines). My only concern is increase of
>> kasan_alloc_meta size. It's unnecessary large already and we have a
>> plan to reduce both alloc and free into to 16 bytes. However, it can
>> make sense to land this and then reduce size of headers in a separate
>> patch using a CAS-loop on state. Alexander, what's the state of your
>> patches that reduce header size?
>
>
> I missed that Alexander already landed patches that reduce header size
> to 16 bytes.
> It is not OK to increase them again. Please leave state as bitfield
> and update it with CAS (if we introduce helper functions for state
> manipulation, they will hide the CAS loop, which is nice).
Note that in this case you'll probably need to update alloc_size with
CAS loop as well.

>
>> I think there is another race. If we have racing frees, one thread
>> sets state to KASAN_STATE_QUARANTINE but does not fill
>> free_info->track yet, at this point another thread does free and
>> reports double-free, but the track is wrong so we will print a bogus
>> stack. The same is true for all other state transitions (e.g.
>> use-after-free racing with the object being pushed out of the
>> quarantine).  We could introduce 2 helper functions like:
>>
>> /* Sets status to KASAN_STATE_LOCKED if the current status is equal to
>> old_state, returns current state. Waits while current state equals
>> KASAN_STATE_LOCKED. */
>> u32 kasan_lock_if_state_equals(struct kasan_alloc_meta *meta, u32 old_state);
>>
>> /* Changes state from KASAN_STATE_LOCKED to new_state */
>> void kasan_unlock_and_set_status(struct kasan_alloc_meta *meta, u32 new_state);
>>
>> Then free can be expressed as:
>>
>> if (kasan_lock_if_state_equals(meta, KASAN_STATE_ALLOC) == KASAN_STATE_ALLOC) {
>>                free_info = get_free_info(cache, object);
>>                quarantine_put(free_info, cache);
>>                set_track(&free_info->track, GFP_NOWAIT);
>>                kasan_poison_slab_free(cache, object);
>>                kasan_unlock_and_set_status(meta, KASAN_STATE_QUARANTINE);
>>                return true;
>> }
>>
>> And on the reporting path we would need to lock the header, read all
>> state, unlock the header.
>>
>> Does it make sense?
>>
>> Please add the test as well. We need to start collecting tests for all
>> these tricky corner cases.
>>
>> Thanks!



-- 
Alexander Potapenko
Software Engineer

Google Germany GmbH
Erika-Mann-StraÃe, 33
80636 MÃnchen

GeschÃftsfÃhrer: Matthew Scott Sucherman, Paul Terence Manicle
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg