linux-kernel - RE: [PATCH] kasan: improve double-free detection

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20E775CA4D599049A25800DE5799F6DD1F627358@G4W3225.americas.hpqcorp.net>
Date:	Sat, 7 May 2016 08:56:42 +0000
From:	"Luruo, Kuthonuzo" <kuthonuzo.luruo@....com>
To:	Dmitry Vyukov <dvyukov@...gle.com>
CC:	Andrey Ryabinin <aryabinin@...tuozzo.com>,
	Alexander Potapenko <glider@...gle.com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	kasan-dev <kasan-dev@...glegroups.com>,
	"linux-mm@...ck.org" <linux-mm@...ck.org>,
	LKML <linux-kernel@...r.kernel.org>
Subject: RE: [PATCH] kasan: improve double-free detection

> >> >> >> 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).
> >> >> >>
> >> >> >
> >> >> > Available CAS primitives/compiler do not support CAS with bitfield. I
> >> propose
> >> >> > to change kasan_alloc_meta to:
> >> >> >
> >> >> > struct kasan_alloc_meta {
> >> >> >         struct kasan_track track;
> >> >> >         u16 size_delta;         /* object_size - alloc size */
> >> >> >         u8 state;                    /* enum kasan_state */
> >> >> >         u8 reserved1;
> >> >> >         u32 reserved2;
> >> >> > }
> >> >> >
> >> >> > This shrinks _used_ meta object by 1 byte wrt the original. (btw, patch v1
> >> does
> >> >> > not increase overall alloc meta object size). "Alloc size", where needed,
> is
> >> >> > easily calculated as a delta from cache->object_size.
> >> >>
> >> >>
> >> >> What is the maximum size that slab can allocate?
> >> >> I remember seeing slabs as large as 4MB some time ago (or did I
> >> >> confuse it with something else?). If there are such large objects,
> >> >> that 2 bytes won't be able to hold even delta.
> >> >> However, now on my desktop I don't see slabs larger than 16KB in
> >> >> /proc/slabinfo.
> >> >
> >> > max size for SLAB's slab is 32MB; default is 4MB. I must have gotten
> confused
> >> by
> >> > SLUB's 8KB limit. Anyway, new kasan_alloc_meta in patch V2:
> >> >
> >> > struct kasan_alloc_meta {
> >> >         struct kasan_track track;
> >> >         union {
> >> >                 u8 lock;
> >> >                 struct {
> >> >                         u32 dummy : 8;
> >> >                         u32 size_delta : 24;    /* object_size - alloc size */
> >> >                 };
> >> >         };
> >> >         u32 state : 2;                          /* enum kasan_alloc_state */
> >> >         u32 unused : 30;
> >> > };
> >> >
> >> > This uses 2 more bits than current, but given the constraints I think this is
> >> > close to optimal.
> >>
> >>
> >> We plan to use the unused part for another depot_stack_handle_t (u32)
> >> to memorize stack of the last call_rcu on the object (this will
> >> greatly simplify debugging of use-after-free for objects freed by
> >> rcu). So we need that unused part.
> >>
> >> I would would simply put all these fields into a single u32:
> >>
> >> struct kasan_alloc_meta {
> >>         struct kasan_track track;
> >>         u32 status;  // contains lock, state and size
> >>         u32 unused;  // reserved for call_rcu stack handle
> >> };
> >>
> >> And then separately a helper type to pack/unpack status:
> >>
> >> union kasan_alloc_status {
> >>         u32 raw;
> >>         struct {
> >>                    u32 lock : 1;
> >>                    u32 state : 2;
> >>                    u32 unused : 5;
> >>                    u32 size : 24;
> >>         };
> >> };
> >>
> >>
> >> Then, when we need to read/update the header we do something like:
> >>
> >> kasan_alloc_status status, new_status;
> >>
> >> for (;;) {
> >>     status.raw = READ_ONCE(header->status);
> >>     // read status, form new_status, for example:
> >>     if (status.lock)
> >>           continue;
> >>     new_status.raw = status.raw;
> >>     new_status.lock = 1;
> >>     if (cas(&header->status, status.raw, new_status.raw))
> >>              break;
> >> }
> >>
> >>
> >> This will probably make state manipulation functions few lines longer,
> >> but since there are like 3 such functions I don't afraid that. And we
> >> still can use bitfield magic to extract fields and leave whole 5 bits
> >> unused bits for future.

v2 has been implemented with your suggested bitfield magic + cas loop. Thanks.

> >
> > The difficulty is that the lock managed by CAS needs 1 byte, mininum; TAS bit
> > is even 'worse': address must be that of an unsigned long.
> 
> cmpxchg function can operate on bytes, words, double words and quad words:
> http://lxr.free-electrons.com/source/arch/x86/include/asm/cmpxchg.h#L146
> 
> 
> > Might it be possible for you to employ the 'kasan_free_meta' header for your
> > RCU stack handle instead since KASAN does not currently store state for RCU
> > slabs on free?
> 
> Free meta is overlapped with user object. The object is not freed yet
> when call_rcu is invoked, so free meta cannot be used yet (user still
> holds own data there). Free meta can only be used after kfree is
> invoked on the object.

Yeah; Iwrongly assumed that kasan_cache_create() special treatment for
SLAB_DESTROY_BY_RCU slabs to store free meta at end of object covers all
uses of RCU. Anyway, "u32 reserved" in alloc meta is now available again...

Kuthonuzo