[PATCH] fs: make sure we do not read beyond allocation

[PATCH] fs: make sure we do not read beyond allocation

[Kees Cook]

In dentry_string_cmp (via__d_lookup_rcu), when CONFIG_DCACHE_WORD_ACCESS
is set, word-width memory reads are performed. However, the string
allocation size may not be a multiple of the word size. To avoid reading
past the end of such an allocation, we must allocate in multiples of
the word size.

Found by the Kernel Address Sanitizer project:
https://code.google.com/p/address-sanitizer/wiki/AddressSanitizerForKernel

Reported-by: Dmitry Vyukov <dvyukov@google.com>
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 fs/dcache.c |    6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/fs/dcache.c b/fs/dcache.c
index 4100030..23665e2 100644
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -1570,7 +1570,11 @@ struct dentry *__d_alloc(struct super_block *sb, const struct qstr *name)
 	 */
 	dentry->d_iname[DNAME_INLINE_LEN-1] = 0;
 	if (name->len > DNAME_INLINE_LEN-1) {
-		dname = kmalloc(name->len + 1, GFP_KERNEL);
+		size_t alloc_size = name->len + 1;
+#ifdef CONFIG_DCACHE_WORD_ACCESS
+		alloc_size = round_up(alloc_size, sizeof(unsigned long));
+#endif
+		dname = kmalloc(alloc_size, GFP_KERNEL);
 		if (!dname) {
 			kmem_cache_free(dentry_cache, dentry); 
 			return NULL;
-- 
1.7.9.5


-- 
Kees Cook
Chrome OS Security

Re: [PATCH] fs: make sure we do not read beyond allocation

[Al Viro]

On Thu, Oct 03, 2013 at 09:34:11AM -0700, Kees Cook wrote:
> In dentry_string_cmp (via__d_lookup_rcu), when CONFIG_DCACHE_WORD_ACCESS
> is set, word-width memory reads are performed. However, the string
> allocation size may not be a multiple of the word size. To avoid reading
> past the end of such an allocation, we must allocate in multiples of
> the word size.

grep ^kmalloc /proc/slabinfo.  Observe the suffix after "kmalloc-"...

IOW, kmalloc() does round its argument up.  Seeing that we allocate an
external name only when allocation has to be longer than 32 bytes, the
sucker is guaranteed to be at least a multiple of 32 by the time we
pick the fitting cache (the worst case is when length is between 65
and 96; then we use kmalloc-96).

When you start a port to a 512-bit architecture, you'll have much nastier
problems than this one...

Re: [PATCH] fs: make sure we do not read beyond allocation

[Kees Cook]

On Thu, Oct 3, 2013 at 10:58 AM, Al Viro <viro@zeniv.linux.org.uk> wrote:
> On Thu, Oct 03, 2013 at 09:34:11AM -0700, Kees Cook wrote:
>> In dentry_string_cmp (via__d_lookup_rcu), when CONFIG_DCACHE_WORD_ACCESS
>> is set, word-width memory reads are performed. However, the string
>> allocation size may not be a multiple of the word size. To avoid reading
>> past the end of such an allocation, we must allocate in multiples of
>> the word size.
>
> grep ^kmalloc /proc/slabinfo.  Observe the suffix after "kmalloc-"...
>
> IOW, kmalloc() does round its argument up.  Seeing that we allocate an
> external name only when allocation has to be longer than 32 bytes, the
> sucker is guaranteed to be at least a multiple of 32 by the time we
> pick the fitting cache (the worst case is when length is between 65
> and 96; then we use kmalloc-96).
>
> When you start a port to a 512-bit architecture, you'll have much nastier
> problems than this one...

Well, this is simply taking advantage of this particular allocator's
behavior. Instead of depending on this side-effect, why not change the
allocation so that we never risk a potentially broken read? (Even SLOB
notes that it may have as low as 2-byte granularity.)

-Kees

-- 
Kees Cook
Chrome OS Security

Re: [PATCH] fs: make sure we do not read beyond allocation

[Al Viro]

On Thu, Oct 03, 2013 at 11:03:07AM -0700, Kees Cook wrote:

> > When you start a port to a 512-bit architecture, you'll have much nastier
> > problems than this one...
> 
> Well, this is simply taking advantage of this particular allocator's
> behavior. Instead of depending on this side-effect, why not change the
> allocation so that we never risk a potentially broken read? (Even SLOB
> notes that it may have as low as 2-byte granularity.)

Oh, for fuck sake!  "Hardening", indeed...

Kees, try to think for a minute[1].  Really.  We have general-purpose
allocator.  Asked to give us something considerably bigger than one
word.  How do you call a situation when it returns something with
the end of requested object crossing the page boundary if rounded
up to nearest multiple of word size?

That's right, FUBAR.  Because for that to happen it would have to
have given you an address that would not be word-aligned.  In response
to request to allocate something wider than a word.  Remember the
words along the lines of "the pointer returned if the allocation
succeeds is properly aligned..."?

It's not a behaviour of this particular allocator.  It's something that
will have to be guaranteed by *any* general-purpose allocator.

[1] yes, yes, I know - the mere mention of security should've prevented such
arrogant requests.  It's an imperfect universe.

Re: [PATCH] fs: make sure we do not read beyond allocation

[Kees Cook]

On Thu, Oct 3, 2013 at 11:23 AM, Al Viro <viro@zeniv.linux.org.uk> wrote:
> On Thu, Oct 03, 2013 at 11:03:07AM -0700, Kees Cook wrote:
>
>> > When you start a port to a 512-bit architecture, you'll have much nastier
>> > problems than this one...
>>
>> Well, this is simply taking advantage of this particular allocator's
>> behavior. Instead of depending on this side-effect, why not change the
>> allocation so that we never risk a potentially broken read? (Even SLOB
>> notes that it may have as low as 2-byte granularity.)
>
> Oh, for fuck sake!  "Hardening", indeed...
>
> Kees, try to think for a minute[1].  Really.  We have general-purpose
> ...
> [1] yes, yes, I know - the mere mention of security should've prevented such
> arrogant requests.  It's an imperfect universe.

I want to attempt to disassemble what you've communicating here:

a) I'm not thinking.
b) Requesting that someone think when they mention security is arrogant.

I would say that "a" is not true. We simply disagree, but you want to
tell me I'm not thinking rather than discuss the technical merits or
flaws of the change I have proposed. I am pointing out an assumption
being made in this code, and you seem to feel it is not worth fixing.
I don't think it's useful to tell me I should think harder. We just
think differently. We have different immediate goals, but share the
common goal of making Linux fantastic. I'm thinking just fine.

Your statement "b" is much more interesting. I see it as a sarcastic
comment about your opinion of "security" work in the kernel. To me
this comes across as a "them" vs "us" interpretation; one where you
may believe "people mentioning security" are condescending about
anyone questioning them. I could read into this that you think I am
part of "them" instead of part of "us". I find that rather insulting,
given our common goals. Additionally, I don't think I've been
condescending.

All of this, of course, made me go check my original email carefully.
There is no mention of "hardening" in my email nor the KASAN link. The
only mention of "security" in either place is in my email signature,
since that is a reflection of my job role working on Chrome OS. I did
not attempt to Cc stable, and there is no CVE mentioned in the email.
So, I can only assume that you have read into this bug and already
understand that this kind of out-of-bounds reading of heap is
sometimes considered a security problem. That's fair, but you appear
to be lashing out at me for this patch on the basis that it is a
"meaningless" security fix. Since I didn't actually bring "security"
up at all, it additionally makes me think you've defined me as part of
"them" doing security work. Again, that's fair, most of my patches are
security related, but we are not on different teams. Saying things
like this attempts to push me away and draw a boundary that does not
exist.

We're all trying to make Linux greater than it already is. Neither
this patch in particular, or any security efforts in general, seek to
destroy Linux.

Continued below, but this change seeks to make things easier for tools
that are trying to find "real" security flaws in the kernel. This one
is unlikely to be anything but theoretical, but it is clearly doing
something against the "contract" of the heap allocation API.

> allocator.  Asked to give us something considerably bigger than one
> word.  How do you call a situation when it returns something with
> the end of requested object crossing the page boundary if rounded
> up to nearest multiple of word size?
>
> That's right, FUBAR.  Because for that to happen it would have to
> have given you an address that would not be word-aligned.  In response
> to request to allocate something wider than a word.  Remember the
> words along the lines of "the pointer returned if the allocation
> succeeds is properly aligned..."?
>
> It's not a behaviour of this particular allocator.  It's something that
> will have to be guaranteed by *any* general-purpose allocator.

No such allocator exists today, sure. I can imagine some kind of
crazy-town allocator that tried to do really fancy storage and might
end up cramming oddly sized allocations at the end of pages, but it
likely doesn't help to ponder this.

What the patch does help with, though, is dynamic analysis tools that
are looking for out-of-bound reads, which this clearly is. It should
be considered a violation of the API to attempt to access a range
beyond what was requested for the allocation. Fixing this means lots
of noise vanishes from such analysis of the allocation API, letting
other tools besides just KASAN do work to find other more serious
problems in heap usage.

Does fixing this to help dynamic analysis tools somehow make the
kernel worse? I think that fixing this makes it easier to find further
bugs that might be much more serious.

-Kees

-- 
Kees Cook
Chrome OS Security

Re: [PATCH] fs: make sure we do not read beyond allocation

[Al Viro]

On Thu, Oct 03, 2013 at 12:36:08PM -0700, Kees Cook wrote:
> > Kees, try to think for a minute[1].  Really.  We have general-purpose
> > ...
> > [1] yes, yes, I know - the mere mention of security should've prevented such
> > arrogant requests.  It's an imperfect universe.
> 
> I want to attempt to disassemble what you've communicating here:
> 
> a) I'm not thinking.
> b) Requesting that someone think when they mention security is arrogant.

Not really.

It's just that all too often completely pointless changes are touted
as security hardening.  With replies along the lines of "it doesn't
really buy you anything" countered with indignant "but what if
<impossible situation>" and/or references to "defense in depth" (used
as a magical incantation), etc.

You've posted a provably pointless patch.  Happens to all of us.  And in
reply to "it's pointless for the following reasons" (with moderate
level of sarcasm) you responded pretty much with "but what if allocator
changes?  It's more robust that way".  OK, but if you go for that
kind of arguments (and they can be valid), you'd better be correct.
You were not, and for very obvious reasons.  Let me repeat, this
time with sarcasm level down to zero:

Let n be some integer between 32 and 4096 and N be equal to n rounded up
to word size.  If kmalloc(n) returns a pointer such that fetch from
(char *)p[N - 1] triggers an exception, we have a badly broken kernel.
It can happen only if there is a page boundary between p[n-1] and p[N-1],
which means that p is not word-aligned.
Consider the following code:
	struct foo {
		unsigned long n;
		char a[];
	} *p = kmalloc(offsetof(struct foo, a) + 33);
	if (p)
		p->n = 1;
and note that it will result in an exception on any architecture that prohibits
unaligned accesses in the kernel.  Even on architectures where those are
allowed, misaligned structures mean serious correctness problems (atomicity of
stores, etc.)

In other words, kmalloc() (or, indeed, userland malloc()) demonstrating
such behaviour would need immediate fixing.  The only exception I can
think of is something with byte granularity of memory protection; in such
case we can have that without unaligned return values returned by allocator.
Which would require a lot of changes in mm/*, at the very least, and probably
would violate a lot of assumptions elsewhere in the kernel (starting with
sizeof(void *) == sizeof(unsigned long)).

> What the patch does help with, though, is dynamic analysis tools that
> are looking for out-of-bound reads, which this clearly is. It should
> be considered a violation of the API to attempt to access a range
> beyond what was requested for the allocation. Fixing this means lots
> of noise vanishes from such analysis of the allocation API, letting
> other tools besides just KASAN do work to find other more serious
> problems in heap usage.
> 
> Does fixing this to help dynamic analysis tools somehow make the
> kernel worse? I think that fixing this makes it easier to find further
> bugs that might be much more serious.

Possibly true.  But then I'd suggest wrapping that into a different ifdef;
grep for ifdef __CHECKER__, with comment along the lines of "to simplify
analysis of potential out-of-bounds accesses".

Re: [PATCH] fs: make sure we do not read beyond allocation

[Kees Cook]

On Thu, Oct 3, 2013 at 1:57 PM, Al Viro <viro@zeniv.linux.org.uk> wrote:
> Let n be some integer between 32 and 4096 and N be equal to n rounded up
> to word size.  If kmalloc(n) returns a pointer such that fetch from
> (char *)p[N - 1] triggers an exception, we have a badly broken kernel.

Sure, this is certainly true given (4096 byte) page-level protections.
And, yes, in the __d_alloc case, the only pathological condition would
be a page boundary. However, this is not always true for other
beyond-allocation reads. Some are much worse/larger, some end up as
info leaks, etc, which is why looking for them has value.

> It can happen only if there is a page boundary between p[n-1] and p[N-1],
> which means that p is not word-aligned.
> Consider the following code:
>         struct foo {
>                 unsigned long n;
>                 char a[];
>         } *p = kmalloc(offsetof(struct foo, a) + 33);
>         if (p)
>                 p->n = 1;
> and note that it will result in an exception on any architecture that prohibits
> unaligned accesses in the kernel.  Even on architectures where those are
> allowed, misaligned structures mean serious correctness problems (atomicity of
> stores, etc.)
>
> In other words, kmalloc() (or, indeed, userland malloc()) demonstrating
> such behaviour would need immediate fixing.  The only exception I can
> think of is something with byte granularity of memory protection; in such
> case we can have that without unaligned return values returned by allocator.
> Which would require a lot of changes in mm/*, at the very least, and probably
> would violate a lot of assumptions elsewhere in the kernel (starting with
> sizeof(void *) == sizeof(unsigned long)).

Byte granularity of memory protection could be provided by future
hypervisors with hooks into the allocator routines, or by leveraging
something like Intel's future MPX[1] stuff for bounds checking. I
still think it'd be better to just fix this directly. The above
examples don't exist right now, but they could soon. Why not fix this
now instead of waiting for someone else to trip over it later?

>> What the patch does help with, though, is dynamic analysis tools that
>> are looking for out-of-bound reads, which this clearly is. It should
>> be considered a violation of the API to attempt to access a range
>> beyond what was requested for the allocation. Fixing this means lots
>> of noise vanishes from such analysis of the allocation API, letting
>> other tools besides just KASAN do work to find other more serious
>> problems in heap usage.
>>
>> Does fixing this to help dynamic analysis tools somehow make the
>> kernel worse? I think that fixing this makes it easier to find further
>> bugs that might be much more serious.
>
> Possibly true.  But then I'd suggest wrapping that into a different ifdef;
> grep for ifdef __CHECKER__, with comment along the lines of "to simplify
> analysis of potential out-of-bounds accesses".

I can live with that. I'll send an updated patch.

Thanks!

-Kees

[1] http://software.intel.com/en-us/blogs/2013/07/22/intel-memory-protection-extensions-intel-mpx-support-in-the-gnu-toolchain

-- 
Kees Cook
Chrome OS Security

Re: [PATCH] fs: make sure we do not read beyond allocation

[Dmitry Vyukov]

On Fri, Oct 4, 2013 at 12:57 AM, Al Viro <viro@zeniv.linux.org.uk> wrote:
> On Thu, Oct 03, 2013 at 12:36:08PM -0700, Kees Cook wrote:
>> > Kees, try to think for a minute[1].  Really.  We have general-purpose
>> > ...
>> > [1] yes, yes, I know - the mere mention of security should've prevented such
>> > arrogant requests.  It's an imperfect universe.
>>
>> I want to attempt to disassemble what you've communicating here:
>>
>> a) I'm not thinking.
>> b) Requesting that someone think when they mention security is arrogant.
>
> Not really.
>
> It's just that all too often completely pointless changes are touted
> as security hardening.  With replies along the lines of "it doesn't
> really buy you anything" countered with indignant "but what if
> <impossible situation>" and/or references to "defense in depth" (used
> as a magical incantation), etc.
>
> You've posted a provably pointless patch.  Happens to all of us.  And in
> reply to "it's pointless for the following reasons" (with moderate
> level of sarcasm) you responded pretty much with "but what if allocator
> changes?  It's more robust that way".  OK, but if you go for that
> kind of arguments (and they can be valid), you'd better be correct.
> You were not, and for very obvious reasons.  Let me repeat, this
> time with sarcasm level down to zero:
>
> Let n be some integer between 32 and 4096 and N be equal to n rounded up
> to word size.  If kmalloc(n) returns a pointer such that fetch from
> (char *)p[N - 1] triggers an exception, we have a badly broken kernel.
> It can happen only if there is a page boundary between p[n-1] and p[N-1],
> which means that p is not word-aligned.
> Consider the following code:
>         struct foo {
>                 unsigned long n;
>                 char a[];
>         } *p = kmalloc(offsetof(struct foo, a) + 33);
>         if (p)
>                 p->n = 1;
> and note that it will result in an exception on any architecture that prohibits
> unaligned accesses in the kernel.  Even on architectures where those are
> allowed, misaligned structures mean serious correctness problems (atomicity of
> stores, etc.)
>
> In other words, kmalloc() (or, indeed, userland malloc()) demonstrating
> such behaviour would need immediate fixing.  The only exception I can
> think of is something with byte granularity of memory protection; in such
> case we can have that without unaligned return values returned by allocator.
> Which would require a lot of changes in mm/*, at the very least, and probably
> would violate a lot of assumptions elsewhere in the kernel (starting with
> sizeof(void *) == sizeof(unsigned long)).
>
>> What the patch does help with, though, is dynamic analysis tools that
>> are looking for out-of-bound reads, which this clearly is. It should
>> be considered a violation of the API to attempt to access a range
>> beyond what was requested for the allocation. Fixing this means lots
>> of noise vanishes from such analysis of the allocation API, letting
>> other tools besides just KASAN do work to find other more serious
>> problems in heap usage.
>>
>> Does fixing this to help dynamic analysis tools somehow make the
>> kernel worse? I think that fixing this makes it easier to find further
>> bugs that might be much more serious.
>
> Possibly true.  But then I'd suggest wrapping that into a different ifdef;
> grep for ifdef __CHECKER__, with comment along the lines of "to simplify
> analysis of potential out-of-bounds accesses".


Hi,

Any single reason to not just fix the code?

With this patch:
+ sticks with "do not access beyond request size", which is a good
thing all others equal
+ makes static and dynamic verification tools happy
- ???

Current code:
- accesses memory beyond requested size, which is a bad thing all others equal
- makes static and dynamic verification tools unhappy, which makes you
miss really important things
+ ???

I think we just need to land it as is.

Re: [PATCH] fs: make sure we do not read beyond allocation

[Richard Weinberger]

On Fri, Oct 4, 2013 at 8:05 AM, Dmitry Vyukov <dvyukov@google.com> wrote:
> On Fri, Oct 4, 2013 at 12:57 AM, Al Viro <viro@zeniv.linux.org.uk> wrote:
>> On Thu, Oct 03, 2013 at 12:36:08PM -0700, Kees Cook wrote:
>>> > Kees, try to think for a minute[1].  Really.  We have general-purpose
>>> > ...
>>> > [1] yes, yes, I know - the mere mention of security should've prevented such
>>> > arrogant requests.  It's an imperfect universe.
>>>
>>> I want to attempt to disassemble what you've communicating here:
>>>
>>> a) I'm not thinking.
>>> b) Requesting that someone think when they mention security is arrogant.
>>
>> Not really.
>>
>> It's just that all too often completely pointless changes are touted
>> as security hardening.  With replies along the lines of "it doesn't
>> really buy you anything" countered with indignant "but what if
>> <impossible situation>" and/or references to "defense in depth" (used
>> as a magical incantation), etc.
>>
>> You've posted a provably pointless patch.  Happens to all of us.  And in
>> reply to "it's pointless for the following reasons" (with moderate
>> level of sarcasm) you responded pretty much with "but what if allocator
>> changes?  It's more robust that way".  OK, but if you go for that
>> kind of arguments (and they can be valid), you'd better be correct.
>> You were not, and for very obvious reasons.  Let me repeat, this
>> time with sarcasm level down to zero:
>>
>> Let n be some integer between 32 and 4096 and N be equal to n rounded up
>> to word size.  If kmalloc(n) returns a pointer such that fetch from
>> (char *)p[N - 1] triggers an exception, we have a badly broken kernel.
>> It can happen only if there is a page boundary between p[n-1] and p[N-1],
>> which means that p is not word-aligned.
>> Consider the following code:
>>         struct foo {
>>                 unsigned long n;
>>                 char a[];
>>         } *p = kmalloc(offsetof(struct foo, a) + 33);
>>         if (p)
>>                 p->n = 1;
>> and note that it will result in an exception on any architecture that prohibits
>> unaligned accesses in the kernel.  Even on architectures where those are
>> allowed, misaligned structures mean serious correctness problems (atomicity of
>> stores, etc.)
>>
>> In other words, kmalloc() (or, indeed, userland malloc()) demonstrating
>> such behaviour would need immediate fixing.  The only exception I can
>> think of is something with byte granularity of memory protection; in such
>> case we can have that without unaligned return values returned by allocator.
>> Which would require a lot of changes in mm/*, at the very least, and probably
>> would violate a lot of assumptions elsewhere in the kernel (starting with
>> sizeof(void *) == sizeof(unsigned long)).
>>
>>> What the patch does help with, though, is dynamic analysis tools that
>>> are looking for out-of-bound reads, which this clearly is. It should
>>> be considered a violation of the API to attempt to access a range
>>> beyond what was requested for the allocation. Fixing this means lots
>>> of noise vanishes from such analysis of the allocation API, letting
>>> other tools besides just KASAN do work to find other more serious
>>> problems in heap usage.
>>>
>>> Does fixing this to help dynamic analysis tools somehow make the
>>> kernel worse? I think that fixing this makes it easier to find further
>>> bugs that might be much more serious.
>>
>> Possibly true.  But then I'd suggest wrapping that into a different ifdef;
>> grep for ifdef __CHECKER__, with comment along the lines of "to simplify
>> analysis of potential out-of-bounds accesses".
>
>
> Hi,
>
> Any single reason to not just fix the code?
>
> With this patch:
> + sticks with "do not access beyond request size", which is a good
> thing all others equal
> + makes static and dynamic verification tools happy
> - ???

- It does not fix anything, it only shuts up the checker
- It adds another ifdef where it is not obvious why it's needed

Therefore it makes more sense to add a ifdef __CHECKER__ such that
everyone immediately knows that the issue is only false positive.

-- 
Thanks,
//richard

Re: [PATCH] fs: make sure we do not read beyond allocation

[Dmitry Vyukov]

On Fri, Oct 4, 2013 at 2:38 PM, Richard Weinberger
<richard.weinberger@gmail.com> wrote:
>>>> > ...
>>>> > [1] yes, yes, I know - the mere mention of security should've prevented such
>>>> > arrogant requests.  It's an imperfect universe.
>>>>
>>>> I want to attempt to disassemble what you've communicating here:
>>>>
>>>> a) I'm not thinking.
>>>> b) Requesting that someone think when they mention security is arrogant.
>>>
>>> Not really.
>>>
>>> It's just that all too often completely pointless changes are touted
>>> as security hardening.  With replies along the lines of "it doesn't
>>> really buy you anything" countered with indignant "but what if
>>> <impossible situation>" and/or references to "defense in depth" (used
>>> as a magical incantation), etc.
>>>
>>> You've posted a provably pointless patch.  Happens to all of us.  And in
>>> reply to "it's pointless for the following reasons" (with moderate
>>> level of sarcasm) you responded pretty much with "but what if allocator
>>> changes?  It's more robust that way".  OK, but if you go for that
>>> kind of arguments (and they can be valid), you'd better be correct.
>>> You were not, and for very obvious reasons.  Let me repeat, this
>>> time with sarcasm level down to zero:
>>>
>>> Let n be some integer between 32 and 4096 and N be equal to n rounded up
>>> to word size.  If kmalloc(n) returns a pointer such that fetch from
>>> (char *)p[N - 1] triggers an exception, we have a badly broken kernel.
>>> It can happen only if there is a page boundary between p[n-1] and p[N-1],
>>> which means that p is not word-aligned.
>>> Consider the following code:
>>>         struct foo {
>>>                 unsigned long n;
>>>                 char a[];
>>>         } *p = kmalloc(offsetof(struct foo, a) + 33);
>>>         if (p)
>>>                 p->n = 1;
>>> and note that it will result in an exception on any architecture that prohibits
>>> unaligned accesses in the kernel.  Even on architectures where those are
>>> allowed, misaligned structures mean serious correctness problems (atomicity of
>>> stores, etc.)
>>>
>>> In other words, kmalloc() (or, indeed, userland malloc()) demonstrating
>>> such behaviour would need immediate fixing.  The only exception I can
>>> think of is something with byte granularity of memory protection; in such
>>> case we can have that without unaligned return values returned by allocator.
>>> Which would require a lot of changes in mm/*, at the very least, and probably
>>> would violate a lot of assumptions elsewhere in the kernel (starting with
>>> sizeof(void *) == sizeof(unsigned long)).
>>>
>>>> What the patch does help with, though, is dynamic analysis tools that
>>>> are looking for out-of-bound reads, which this clearly is. It should
>>>> be considered a violation of the API to attempt to access a range
>>>> beyond what was requested for the allocation. Fixing this means lots
>>>> of noise vanishes from such analysis of the allocation API, letting
>>>> other tools besides just KASAN do work to find other more serious
>>>> problems in heap usage.
>>>>
>>>> Does fixing this to help dynamic analysis tools somehow make the
>>>> kernel worse? I think that fixing this makes it easier to find further
>>>> bugs that might be much more serious.
>>>
>>> Possibly true.  But then I'd suggest wrapping that into a different ifdef;
>>> grep for ifdef __CHECKER__, with comment along the lines of "to simplify
>>> analysis of potential out-of-bounds accesses".
>>
>>
>> Hi,
>>
>> Any single reason to not just fix the code?
>>
>> With this patch:
>> + sticks with "do not access beyond request size", which is a good
>> thing all others equal
>> + makes static and dynamic verification tools happy
>> - ???
>
> - It does not fix anything, it only shuts up the checker
> - It adds another ifdef where it is not obvious why it's needed
>
> Therefore it makes more sense to add a ifdef __CHECKER__ such that
> everyone immediately knows that the issue is only false positive.


OK, is it explicitly documented somewhere that it's legal to access
memory blocks beyond requested size? Is it a deliberate decision made
by community? Or just an ad-hoc argument based on details of current
implementation?

If it's the former then we will need to teach the tools to understand
it. But IMVHO it's a very unfortunate decision, because it will hide
real harmful bugs. And this is the only place where I observed such
out-of-bounds access after months of stress testing, so we are not
talking about hundreds and thousands of precedents. We are talking
about this particular case vs ability of tools to catch harmful
off-by-one accesses to variable-length strings and buffers.

What are the exact rules for memory accesses? Is there anything else?
Looking at the current allocator implementation I can infer lots of
other cases that are "safe"; e.g. in some single-threaded scenarios
it's perfectly fine to access memory blocks after kfree.

Re: [PATCH] fs: make sure we do not read beyond allocation

[Richard Weinberger]

Am 04.10.2013 12:53, schrieb Dmitry Vyukov:
> On Fri, Oct 4, 2013 at 2:38 PM, Richard Weinberger
> <richard.weinberger@gmail.com> wrote:
>>>>>> ...
>>>>>> [1] yes, yes, I know - the mere mention of security should've prevented such
>>>>>> arrogant requests.  It's an imperfect universe.
>>>>>
>>>>> I want to attempt to disassemble what you've communicating here:
>>>>>
>>>>> a) I'm not thinking.
>>>>> b) Requesting that someone think when they mention security is arrogant.
>>>>
>>>> Not really.
>>>>
>>>> It's just that all too often completely pointless changes are touted
>>>> as security hardening.  With replies along the lines of "it doesn't
>>>> really buy you anything" countered with indignant "but what if
>>>> <impossible situation>" and/or references to "defense in depth" (used
>>>> as a magical incantation), etc.
>>>>
>>>> You've posted a provably pointless patch.  Happens to all of us.  And in
>>>> reply to "it's pointless for the following reasons" (with moderate
>>>> level of sarcasm) you responded pretty much with "but what if allocator
>>>> changes?  It's more robust that way".  OK, but if you go for that
>>>> kind of arguments (and they can be valid), you'd better be correct.
>>>> You were not, and for very obvious reasons.  Let me repeat, this
>>>> time with sarcasm level down to zero:
>>>>
>>>> Let n be some integer between 32 and 4096 and N be equal to n rounded up
>>>> to word size.  If kmalloc(n) returns a pointer such that fetch from
>>>> (char *)p[N - 1] triggers an exception, we have a badly broken kernel.
>>>> It can happen only if there is a page boundary between p[n-1] and p[N-1],
>>>> which means that p is not word-aligned.
>>>> Consider the following code:
>>>>         struct foo {
>>>>                 unsigned long n;
>>>>                 char a[];
>>>>         } *p = kmalloc(offsetof(struct foo, a) + 33);
>>>>         if (p)
>>>>                 p->n = 1;
>>>> and note that it will result in an exception on any architecture that prohibits
>>>> unaligned accesses in the kernel.  Even on architectures where those are
>>>> allowed, misaligned structures mean serious correctness problems (atomicity of
>>>> stores, etc.)
>>>>
>>>> In other words, kmalloc() (or, indeed, userland malloc()) demonstrating
>>>> such behaviour would need immediate fixing.  The only exception I can
>>>> think of is something with byte granularity of memory protection; in such
>>>> case we can have that without unaligned return values returned by allocator.
>>>> Which would require a lot of changes in mm/*, at the very least, and probably
>>>> would violate a lot of assumptions elsewhere in the kernel (starting with
>>>> sizeof(void *) == sizeof(unsigned long)).
>>>>
>>>>> What the patch does help with, though, is dynamic analysis tools that
>>>>> are looking for out-of-bound reads, which this clearly is. It should
>>>>> be considered a violation of the API to attempt to access a range
>>>>> beyond what was requested for the allocation. Fixing this means lots
>>>>> of noise vanishes from such analysis of the allocation API, letting
>>>>> other tools besides just KASAN do work to find other more serious
>>>>> problems in heap usage.
>>>>>
>>>>> Does fixing this to help dynamic analysis tools somehow make the
>>>>> kernel worse? I think that fixing this makes it easier to find further
>>>>> bugs that might be much more serious.
>>>>
>>>> Possibly true.  But then I'd suggest wrapping that into a different ifdef;
>>>> grep for ifdef __CHECKER__, with comment along the lines of "to simplify
>>>> analysis of potential out-of-bounds accesses".
>>>
>>>
>>> Hi,
>>>
>>> Any single reason to not just fix the code?
>>>
>>> With this patch:
>>> + sticks with "do not access beyond request size", which is a good
>>> thing all others equal
>>> + makes static and dynamic verification tools happy
>>> - ???
>>
>> - It does not fix anything, it only shuts up the checker
>> - It adds another ifdef where it is not obvious why it's needed
>>
>> Therefore it makes more sense to add a ifdef __CHECKER__ such that
>> everyone immediately knows that the issue is only false positive.
> 
> 
> OK, is it explicitly documented somewhere that it's legal to access
> memory blocks beyond requested size? Is it a deliberate decision made
> by community? Or just an ad-hoc argument based on details of current
> implementation?

Al explained already why it is legal.

> If it's the former then we will need to teach the tools to understand
> it. But IMVHO it's a very unfortunate decision, because it will hide
> real harmful bugs. And this is the only place where I observed such
> out-of-bounds access after months of stress testing, so we are not
> talking about hundreds and thousands of precedents. We are talking
> about this particular case vs ability of tools to catch harmful
> off-by-one accesses to variable-length strings and buffers.

Have you ever used valgrind (or any other checkers in userspace)?
They all suffer from such issues.
If a checker reports a violation it is not always a real one and
you have to review it carefully.

Thanks,
//richard

Re: [PATCH] fs: make sure we do not read beyond allocation

[Dmitry Vyukov]

On Fri, Oct 4, 2013 at 5:53 PM, Richard Weinberger <richard@nod.at> wrote:
> Am 04.10.2013 12:53, schrieb Dmitry Vyukov:
>> On Fri, Oct 4, 2013 at 2:38 PM, Richard Weinberger
>> <richard.weinberger@gmail.com> wrote:
>>>>>>> ...
>>>>>>> [1] yes, yes, I know - the mere mention of security should've prevented such
>>>>>>> arrogant requests.  It's an imperfect universe.
>>>>>>
>>>>>> I want to attempt to disassemble what you've communicating here:
>>>>>>
>>>>>> a) I'm not thinking.
>>>>>> b) Requesting that someone think when they mention security is arrogant.
>>>>>
>>>>> Not really.
>>>>>
>>>>> It's just that all too often completely pointless changes are touted
>>>>> as security hardening.  With replies along the lines of "it doesn't
>>>>> really buy you anything" countered with indignant "but what if
>>>>> <impossible situation>" and/or references to "defense in depth" (used
>>>>> as a magical incantation), etc.
>>>>>
>>>>> You've posted a provably pointless patch.  Happens to all of us.  And in
>>>>> reply to "it's pointless for the following reasons" (with moderate
>>>>> level of sarcasm) you responded pretty much with "but what if allocator
>>>>> changes?  It's more robust that way".  OK, but if you go for that
>>>>> kind of arguments (and they can be valid), you'd better be correct.
>>>>> You were not, and for very obvious reasons.  Let me repeat, this
>>>>> time with sarcasm level down to zero:
>>>>>
>>>>> Let n be some integer between 32 and 4096 and N be equal to n rounded up
>>>>> to word size.  If kmalloc(n) returns a pointer such that fetch from
>>>>> (char *)p[N - 1] triggers an exception, we have a badly broken kernel.
>>>>> It can happen only if there is a page boundary between p[n-1] and p[N-1],
>>>>> which means that p is not word-aligned.
>>>>> Consider the following code:
>>>>>         struct foo {
>>>>>                 unsigned long n;
>>>>>                 char a[];
>>>>>         } *p = kmalloc(offsetof(struct foo, a) + 33);
>>>>>         if (p)
>>>>>                 p->n = 1;
>>>>> and note that it will result in an exception on any architecture that prohibits
>>>>> unaligned accesses in the kernel.  Even on architectures where those are
>>>>> allowed, misaligned structures mean serious correctness problems (atomicity of
>>>>> stores, etc.)
>>>>>
>>>>> In other words, kmalloc() (or, indeed, userland malloc()) demonstrating
>>>>> such behaviour would need immediate fixing.  The only exception I can
>>>>> think of is something with byte granularity of memory protection; in such
>>>>> case we can have that without unaligned return values returned by allocator.
>>>>> Which would require a lot of changes in mm/*, at the very least, and probably
>>>>> would violate a lot of assumptions elsewhere in the kernel (starting with
>>>>> sizeof(void *) == sizeof(unsigned long)).
>>>>>
>>>>>> What the patch does help with, though, is dynamic analysis tools that
>>>>>> are looking for out-of-bound reads, which this clearly is. It should
>>>>>> be considered a violation of the API to attempt to access a range
>>>>>> beyond what was requested for the allocation. Fixing this means lots
>>>>>> of noise vanishes from such analysis of the allocation API, letting
>>>>>> other tools besides just KASAN do work to find other more serious
>>>>>> problems in heap usage.
>>>>>>
>>>>>> Does fixing this to help dynamic analysis tools somehow make the
>>>>>> kernel worse? I think that fixing this makes it easier to find further
>>>>>> bugs that might be much more serious.
>>>>>
>>>>> Possibly true.  But then I'd suggest wrapping that into a different ifdef;
>>>>> grep for ifdef __CHECKER__, with comment along the lines of "to simplify
>>>>> analysis of potential out-of-bounds accesses".
>>>>
>>>>
>>>> Hi,
>>>>
>>>> Any single reason to not just fix the code?
>>>>
>>>> With this patch:
>>>> + sticks with "do not access beyond request size", which is a good
>>>> thing all others equal
>>>> + makes static and dynamic verification tools happy
>>>> - ???
>>>
>>> - It does not fix anything, it only shuts up the checker
>>> - It adds another ifdef where it is not obvious why it's needed
>>>
>>> Therefore it makes more sense to add a ifdef __CHECKER__ such that
>>> everyone immediately knows that the issue is only false positive.
>>
>>
>> OK, is it explicitly documented somewhere that it's legal to access
>> memory blocks beyond requested size? Is it a deliberate decision made
>> by community? Or just an ad-hoc argument based on details of current
>> implementation?
>
> Al explained already why it is legal.
>
>> If it's the former then we will need to teach the tools to understand
>> it. But IMVHO it's a very unfortunate decision, because it will hide
>> real harmful bugs. And this is the only place where I observed such
>> out-of-bounds access after months of stress testing, so we are not
>> talking about hundreds and thousands of precedents. We are talking
>> about this particular case vs ability of tools to catch harmful
>> off-by-one accesses to variable-length strings and buffers.
>
> Have you ever used valgrind (or any other checkers in userspace)?
> They all suffer from such issues.
> If a checker reports a violation it is not always a real one and
> you have to review it carefully.

I am not sure why you call it not a real one. Both C and C++ standards
are pretty clear on this: it is undefined behavior.
That said, Valgrind/memcheck indeed has other false positives, because
it tries to reason about source code looking only at the binary. This
can not possibly work.
AddressSanitizer
(https://sites.google.com/a/google.com/dynamic-tools/addresssanitizer)
does not have known false positives.

Re: [PATCH] fs: make sure we do not read beyond allocation

[Dmitry Vyukov]

On Fri, Oct 11, 2013 at 3:26 PM, Dmitry Vyukov <dvyukov@google.com> wrote:
> On Fri, Oct 4, 2013 at 5:53 PM, Richard Weinberger <richard@nod.at> wrote:
>> Am 04.10.2013 12:53, schrieb Dmitry Vyukov:
>>> On Fri, Oct 4, 2013 at 2:38 PM, Richard Weinberger
>>> <richard.weinberger@gmail.com> wrote:
>>>>>>>> ...
>>>>>>>> [1] yes, yes, I know - the mere mention of security should've prevented such
>>>>>>>> arrogant requests.  It's an imperfect universe.
>>>>>>>
>>>>>>> I want to attempt to disassemble what you've communicating here:
>>>>>>>
>>>>>>> a) I'm not thinking.
>>>>>>> b) Requesting that someone think when they mention security is arrogant.
>>>>>>
>>>>>> Not really.
>>>>>>
>>>>>> It's just that all too often completely pointless changes are touted
>>>>>> as security hardening.  With replies along the lines of "it doesn't
>>>>>> really buy you anything" countered with indignant "but what if
>>>>>> <impossible situation>" and/or references to "defense in depth" (used
>>>>>> as a magical incantation), etc.
>>>>>>
>>>>>> You've posted a provably pointless patch.  Happens to all of us.  And in
>>>>>> reply to "it's pointless for the following reasons" (with moderate
>>>>>> level of sarcasm) you responded pretty much with "but what if allocator
>>>>>> changes?  It's more robust that way".  OK, but if you go for that
>>>>>> kind of arguments (and they can be valid), you'd better be correct.
>>>>>> You were not, and for very obvious reasons.  Let me repeat, this
>>>>>> time with sarcasm level down to zero:
>>>>>>
>>>>>> Let n be some integer between 32 and 4096 and N be equal to n rounded up
>>>>>> to word size.  If kmalloc(n) returns a pointer such that fetch from
>>>>>> (char *)p[N - 1] triggers an exception, we have a badly broken kernel.
>>>>>> It can happen only if there is a page boundary between p[n-1] and p[N-1],
>>>>>> which means that p is not word-aligned.
>>>>>> Consider the following code:
>>>>>>         struct foo {
>>>>>>                 unsigned long n;
>>>>>>                 char a[];
>>>>>>         } *p = kmalloc(offsetof(struct foo, a) + 33);
>>>>>>         if (p)
>>>>>>                 p->n = 1;
>>>>>> and note that it will result in an exception on any architecture that prohibits
>>>>>> unaligned accesses in the kernel.  Even on architectures where those are
>>>>>> allowed, misaligned structures mean serious correctness problems (atomicity of
>>>>>> stores, etc.)
>>>>>>
>>>>>> In other words, kmalloc() (or, indeed, userland malloc()) demonstrating
>>>>>> such behaviour would need immediate fixing.  The only exception I can
>>>>>> think of is something with byte granularity of memory protection; in such
>>>>>> case we can have that without unaligned return values returned by allocator.
>>>>>> Which would require a lot of changes in mm/*, at the very least, and probably
>>>>>> would violate a lot of assumptions elsewhere in the kernel (starting with
>>>>>> sizeof(void *) == sizeof(unsigned long)).
>>>>>>
>>>>>>> What the patch does help with, though, is dynamic analysis tools that
>>>>>>> are looking for out-of-bound reads, which this clearly is. It should
>>>>>>> be considered a violation of the API to attempt to access a range
>>>>>>> beyond what was requested for the allocation. Fixing this means lots
>>>>>>> of noise vanishes from such analysis of the allocation API, letting
>>>>>>> other tools besides just KASAN do work to find other more serious
>>>>>>> problems in heap usage.
>>>>>>>
>>>>>>> Does fixing this to help dynamic analysis tools somehow make the
>>>>>>> kernel worse? I think that fixing this makes it easier to find further
>>>>>>> bugs that might be much more serious.
>>>>>>
>>>>>> Possibly true.  But then I'd suggest wrapping that into a different ifdef;
>>>>>> grep for ifdef __CHECKER__, with comment along the lines of "to simplify
>>>>>> analysis of potential out-of-bounds accesses".
>>>>>
>>>>>
>>>>> Hi,
>>>>>
>>>>> Any single reason to not just fix the code?
>>>>>
>>>>> With this patch:
>>>>> + sticks with "do not access beyond request size", which is a good
>>>>> thing all others equal
>>>>> + makes static and dynamic verification tools happy
>>>>> - ???
>>>>
>>>> - It does not fix anything, it only shuts up the checker
>>>> - It adds another ifdef where it is not obvious why it's needed
>>>>
>>>> Therefore it makes more sense to add a ifdef __CHECKER__ such that
>>>> everyone immediately knows that the issue is only false positive.
>>>
>>>
>>> OK, is it explicitly documented somewhere that it's legal to access
>>> memory blocks beyond requested size? Is it a deliberate decision made
>>> by community? Or just an ad-hoc argument based on details of current
>>> implementation?
>>
>> Al explained already why it is legal.
>>
>>> If it's the former then we will need to teach the tools to understand
>>> it. But IMVHO it's a very unfortunate decision, because it will hide
>>> real harmful bugs. And this is the only place where I observed such
>>> out-of-bounds access after months of stress testing, so we are not
>>> talking about hundreds and thousands of precedents. We are talking
>>> about this particular case vs ability of tools to catch harmful
>>> off-by-one accesses to variable-length strings and buffers.
>>
>> Have you ever used valgrind (or any other checkers in userspace)?
>> They all suffer from such issues.
>> If a checker reports a violation it is not always a real one and
>> you have to review it carefully.
>
> I am not sure why you call it not a real one. Both C and C++ standards
> are pretty clear on this: it is undefined behavior.
> That said, Valgrind/memcheck indeed has other false positives, because
> it tries to reason about source code looking only at the binary. This
> can not possibly work.
> AddressSanitizer
> (https://sites.google.com/a/google.com/dynamic-tools/addresssanitizer)
> does not have known false positives.


What about the following patch?

-               dname = kmalloc(name->len + 1, GFP_KERNEL);
+               // We are going to access it as array of long's.
+               dname = kmalloc(round_up(name->len + 1,
sizeof(unsigned long)), GFP_KERNEL);