[PATCH] compat: fix possible out-of-bound accesses in compat_get_bitmap() and compat_put_bitmap()

[PATCH] compat: fix possible out-of-bound accesses in compat_get_bitmap() and compat_put_bitmap()

[Helge Deller]

In functions compat_get_bitmap() and compat_put_bitmap() the variable
nr_compat_longs stores how many compat_ulong_t words should be copied in a loop.

The copy-loop itself is this:
  if (nr_compat_longs-- > 0) {
      if (__get_user(um, umask)) return -EFAULT;
  } else {
      um = 0;
  }

Since nr_compat_longs gets unconditionally decremented in each loop, it's type
needs to be signed instead of unsigned to avoid possibly accessing userspace
memory behind the bitmap which shouldn't be accessed.

This bug seems to have been here for quite some time already, e.g. kernel
2.6.11 has the same coding. I didn't checked earlier versions.

Signed-off-by: Helge Deller <deller@gmx.de>
To: Al Viro <viro@zeniv.linux.org.uk>
Cc: stable@vger.kernel.org

diff --git a/kernel/compat.c b/kernel/compat.c
index 24f0061..bfbb312 100644
--- a/kernel/compat.c
+++ b/kernel/compat.c
@@ -893,7 +893,7 @@ long compat_get_bitmap(unsigned long *mask, const compat_ulong_t __user *umask,
 	int i, j;
 	unsigned long m;
 	compat_ulong_t um;
-	unsigned long nr_compat_longs;
+	signed long nr_compat_longs;
 
 	/* align bitmap up to nearest compat_long_t boundary */
 	bitmap_size = ALIGN(bitmap_size, BITS_PER_COMPAT_LONG);
@@ -934,7 +934,7 @@ long compat_put_bitmap(compat_ulong_t __user *umask, unsigned long *mask,
 	int i, j;
 	unsigned long m;
 	compat_ulong_t um;
-	unsigned long nr_compat_longs;
+	signed long nr_compat_longs;
 
 	/* align bitmap up to nearest compat_long_t boundary */
 	bitmap_size = ALIGN(bitmap_size, BITS_PER_COMPAT_LONG);

Re: [PATCH] compat: fix possible out-of-bound accesses in compat_get_bitmap() and compat_put_bitmap()

[Linus Torvalds]

[-- Attachment #1: Type: text/plain, Size: 1205 bytes --]

On Mon, Jun 1, 2015 at 11:44 AM, Helge Deller <deller@gmx.de> wrote:
>
> Since nr_compat_longs gets unconditionally decremented in each loop, it's type
> needs to be signed instead of unsigned to avoid possibly accessing userspace
> memory behind the bitmap which shouldn't be accessed.

I'd actually prefer to instead just make the decrement conditional,
since that would seem to be the more obvious code. Make the logic be
"iff I have more to go, do the access, and then decrement the counter"

Also, compat_put_bitmap() has the exact same code, and should have the same fix.

Finally, I don't think this is an *actual* bug, just bad and stupid
code. The thing is, the inner loop is only executed twice anyway, and
on that last iteration where "nr_compat_longs" could go negative, the
_outer_ loop will break out too. So there is no actual way we can
enter the thing with nr_compat_longs <= 1 to begin with.

So I don't think the code ever really actually overflows. I do agree
that the code looks bad, so I think a patch like the attached would be
a good idea. Not necessarily marked for stable, unless you can point
out why I'm wrong about the edge condition.

Hmm?

                            Linus

[-- Attachment #2: patch.diff --]
[-- Type: text/plain, Size: 873 bytes --]

 kernel/compat.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/kernel/compat.c b/kernel/compat.c
index 24f00610c575..333d364be29d 100644
--- a/kernel/compat.c
+++ b/kernel/compat.c
@@ -912,7 +912,8 @@ long compat_get_bitmap(unsigned long *mask, const compat_ulong_t __user *umask,
 			 * bitmap. We must however ensure the end of the
 			 * kernel bitmap is zeroed.
 			 */
-			if (nr_compat_longs-- > 0) {
+			if (nr_compat_longs) {
+				nr_compat_longs--;
 				if (__get_user(um, umask))
 					return -EFAULT;
 			} else {
@@ -954,7 +955,8 @@ long compat_put_bitmap(compat_ulong_t __user *umask, unsigned long *mask,
 			 * We dont want to write past the end of the userspace
 			 * bitmap.
 			 */
-			if (nr_compat_longs-- > 0) {
+			if (nr_compat_longs) {
+				nr_compat_longs--;
 				if (__put_user(um, umask))
 					return -EFAULT;
 			}

Re: [PATCH] compat: fix possible out-of-bound accesses in compat_get_bitmap() and compat_put_bitmap()

[Helge Deller]

Hi Linus,

On 02.06.2015 03:49, Linus Torvalds wrote:
> On Mon, Jun 1, 2015 at 11:44 AM, Helge Deller <deller@gmx.de> wrote:
>>
>> Since nr_compat_longs gets unconditionally decremented in each loop, it's type
>> needs to be signed instead of unsigned to avoid possibly accessing userspace
>> memory behind the bitmap which shouldn't be accessed.
>
> I'd actually prefer to instead just make the decrement conditional,
> since that would seem to be the more obvious code. Make the logic be
> "iff I have more to go, do the access, and then decrement the counter"

That's fine for me.
I just wanted to keep the patch small, but your proposal makes the code
of course more human readable.
  
> Also, compat_put_bitmap() has the exact same code, and should have the same fix.
>
> Finally, I don't think this is an *actual* bug, just bad and stupid
> code. The thing is, the inner loop is only executed twice anyway, and
> on that last iteration where "nr_compat_longs" could go negative, the
> _outer_ loop will break out too. So there is no actual way we can
> enter the thing with nr_compat_longs <= 1 to begin with.
>
> So I don't think the code ever really actually overflows.

Yes, it probably doesn't overflows. It's not that easy to follow all code
paths (and take into account that the bitmap sizes might be different), but
the code in general looks clean.

>  I do agree
> that the code looks bad, so I think a patch like the attached would be
> a good idea. Not necessarily marked for stable, unless you can point
> out why I'm wrong about the edge condition.

No, your code proposal is fine.
Do you want me to send it again cleaned up, or will you just take yours?

Thanks!
Helge

Re: [PATCH] compat: fix possible out-of-bound accesses in compat_get_bitmap() and compat_put_bitmap()

[Linus Torvalds]

On Thu, Jun 4, 2015 at 6:45 AM, Helge Deller <deller@gmx.de> wrote:
>
> Do you want me to send it again cleaned up, or will you just take yours?

I'd prefer to get a re-send, I've already nuked the patch from me tree.

These days, 99% of the patches I write are throw-away stuff just for
this kind of "how about this" email exchange.

I do it that way partly because I'm lazy (ok, _mostly_ because I'm
lazy, except then the explanation emails like this are actually more
work than just doing it myself - but I tell myself that it makes it
easier for me be lazy in the long run ;^). But partly it's because it
makes it more natural to credit the person who actually reported the
issue (the patch itself is *much* less important than the fact that
somebody noticed the problem in the first place), and also partly
because sometimes the patches may need some extra tender care and
loving ("Oh, the patch I sent out didn't actually compile, and it
burnt down your house? Yeah, it was just a general 'wouldn't this way
be nicer' thing, not a serious patch").

                     Linus

Re: [PATCH] compat: fix possible out-of-bound accesses in compat_get_bitmap() and compat_put_bitmap()

[Helge Deller]

Hi Linus,

* Linus Torvalds <torvalds@linux-foundation.org>:
> On Thu, Jun 4, 2015 at 6:45 AM, Helge Deller <deller@gmx.de> wrote:
> >
> > Do you want me to send it again cleaned up, or will you just take yours?
> 
> I'd prefer to get a re-send, I've already nuked the patch from me tree.

Sure.
The new patch is attached below.
If you think it's OK, you can either apply it, or alternatively just
pull it from my compat-bitmap-fix branch:

	git://git.kernel.org/pub/scm/linux/kernel/git/deller/parisc-linux.git  compat-bitmap-fix

Patch title is:
	compat: cleanup coding in compat_get_bitmap() and compat_put_bitmap()

 
> These days, 99% of the patches I write are throw-away stuff just for
> this kind of "how about this" email exchange.
> 
> I do it that way partly because I'm lazy (ok, _mostly_ because I'm
> lazy, except then the explanation emails like this are actually more
> work than just doing it myself - but I tell myself that it makes it
> easier for me be lazy in the long run ;^). But partly it's because it
> makes it more natural to credit the person who actually reported the
> issue (the patch itself is *much* less important than the fact that
> somebody noticed the problem in the first place), and also partly
> because sometimes the patches may need some extra tender care and
> loving ("Oh, the patch I sent out didn't actually compile, and it
> burnt down your house? Yeah, it was just a general 'wouldn't this way
> be nicer' thing, not a serious patch").
 
Fully understandable.

Thanks!
Helge


[PATCH] compat: cleanup coding in compat_get_bitmap() and compat_put_bitmap()

In the functions compat_get_bitmap() and compat_put_bitmap() the variable
nr_compat_longs stores how many compat_ulong_t words should be copied in a
loop.

The copy loop itself is this:
  if (nr_compat_longs-- > 0) {
      if (__get_user(um, umask)) return -EFAULT;
  } else {
      um = 0;
  }

Since nr_compat_longs gets unconditionally decremented in each loop and since
it's type is unsigned this could theoretically lead to out-of-bounds accesses
to userspace if nr_compat_longs wraps around to (unsigned)(-1).

Although the callers currently do not trigger out-of-bounds accesses, we should
better implement the loop in a safe way to completely avoid such warp-arounds.

Signed-off-by: Helge Deller <deller@gmx.de>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Al Viro <viro@zeniv.linux.org.uk>

diff --git a/kernel/compat.c b/kernel/compat.c
index 24f0061..333d364 100644
--- a/kernel/compat.c
+++ b/kernel/compat.c
@@ -912,7 +912,8 @@ long compat_get_bitmap(unsigned long *mask, const compat_ulong_t __user *umask,
 			 * bitmap. We must however ensure the end of the
 			 * kernel bitmap is zeroed.
 			 */
-			if (nr_compat_longs-- > 0) {
+			if (nr_compat_longs) {
+				nr_compat_longs--;
 				if (__get_user(um, umask))
 					return -EFAULT;
 			} else {
@@ -954,7 +955,8 @@ long compat_put_bitmap(compat_ulong_t __user *umask, unsigned long *mask,
 			 * We dont want to write past the end of the userspace
 			 * bitmap.
 			 */
-			if (nr_compat_longs-- > 0) {
+			if (nr_compat_longs) {
+				nr_compat_longs--;
 				if (__put_user(um, umask))
 					return -EFAULT;
 			}

Re: [PATCH] compat: fix possible out-of-bound accesses in compat_get_bitmap() and compat_put_bitmap()

[Al Viro]

On Fri, Jun 05, 2015 at 12:07:43AM +0200, Helge Deller wrote:
> In the functions compat_get_bitmap() and compat_put_bitmap() the variable
> nr_compat_longs stores how many compat_ulong_t words should be copied in a
> loop.
> 
> The copy loop itself is this:
>   if (nr_compat_longs-- > 0) {
>       if (__get_user(um, umask)) return -EFAULT;
>   } else {
>       um = 0;
>   }

Er...  When does that condition trigger?  We start with
(((n)+BITS_PER_COMPAT_LONG-1)/BITS_PER_COMPAT_LONG), which is
essentially DIV_ROUND_UP(n, BITS_PER_BYTE * sizeof(compat_long_t)).

Then we go through DIV_ROUND_UP(n, BITS_PER_BYTE * sizeof(long))
iterations of outer loop, with sizeof(long)/sizeof(compat_long_t)
iterations on inner one every time.  

So basically that thing will trigger only on the last pass through
the outer loop.  The only way for it to trigger a wraparound would
be to have sizeof(long)/sizeof(compat_long_t) greater than LONG_MAX,
which is, not too likely.

If we decrement nr_compat_longs and want to stop when it reaches zero, why not 
use that as the (only) loop condition?  As in

	for (m = 0, shift = 0; nr_compat_longs--;) {
		compat_ulong_t um;

		if (__get_user(um, umask++))
			return -EFAULT;

		m |= (long)um << shift;
		shift += BITS_PER_COMPAT_LONG;
		if (shift == BITS_PER_LONG) {
			shift = 0;
			*mask++ = m;
			m = 0;
		}
	}
	if (shift)
		*mask++ = m;

Re: [PATCH] compat: fix possible out-of-bound accesses in compat_get_bitmap() and compat_put_bitmap()

[Linus Torvalds]

On Thu, Jun 4, 2015 at 5:36 PM, Al Viro <viro@zeniv.linux.org.uk> wrote:
>
> So basically that thing will trigger only on the last pass through
> the outer loop.  The only way for it to trigger a wraparound would
> be to have sizeof(long)/sizeof(compat_long_t) greater than LONG_MAX,
> which is, not too likely.

No. You missed that the "nr_compat_longs-- > 0" thing is an *unsigned*
comparison.

So the bug would trigger whenever the last pass through the outer loop
would then have an inner loop that decremented it from 0 to ULONG_MAX.

However, it turns out that since sizeof(long)/sizeof(compat_long_t) in
practice is always just 2, the decrement itself can happen only twice,
and since we only ever enter with nr_compat_longs being non-zero, only
the second decrement can do that overflow thing. And since that's the
last iteration of the inner loop (_and_ the outer loop), it doesn't
matter that the value ends up having overflowed

So the code _works_. But it works almost by accident, and it sure as
hell does not need that "greater than LONG_MAX" thing you think.
Anything bigger than 2 would cause an active bug.

So the whole "nr_compat_longs-- > 0" is just broken. It happens to
work, but it is ugly and wrong. It's also pointless, when we might as
well just move the decrement into the conditional, and avoid the whole
"it could overflow/underflow" discussion entirely, and make the whole
signed-vs-unsigned a total non-issue.

So the patch is a good cleanup. It doesn't fix any actual bugs, but it
definitely fixes potential bugs (ie if somebody were to have a 32-bit
compat mode on a 128-bit native kernel - something we don't actually
have yet, but an example of a situation that would trigger the bug)

                        Linus

Re: [PATCH] compat: fix possible out-of-bound accesses in compat_get_bitmap() and compat_put_bitmap()

[Al Viro]

On Fri, Jun 05, 2015 at 09:49:46AM -0700, Linus Torvalds wrote:
> On Thu, Jun 4, 2015 at 5:36 PM, Al Viro <viro@zeniv.linux.org.uk> wrote:
> >
> > So basically that thing will trigger only on the last pass through
> > the outer loop.  The only way for it to trigger a wraparound would
> > be to have sizeof(long)/sizeof(compat_long_t) greater than LONG_MAX,
> > which is, not too likely.
> 
> No. You missed that the "nr_compat_longs-- > 0" thing is an *unsigned*
> comparison.
> 
> So the bug would trigger whenever the last pass through the outer loop
> would then have an inner loop that decremented it from 0 to ULONG_MAX.
> 
> However, it turns out that since sizeof(long)/sizeof(compat_long_t) in
> practice is always just 2, the decrement itself can happen only twice,
> and since we only ever enter with nr_compat_longs being non-zero, only
> the second decrement can do that overflow thing. And since that's the
> last iteration of the inner loop (_and_ the outer loop), it doesn't
> matter that the value ends up having overflowed
>
> So the code _works_. But it works almost by accident, and it sure as
> hell does not need that "greater than LONG_MAX" thing you think.
> Anything bigger than 2 would cause an active bug.

Right you are.

> So the whole "nr_compat_longs-- > 0" is just broken. It happens to
> work, but it is ugly and wrong. It's also pointless, when we might as
> well just move the decrement into the conditional, and avoid the whole
> "it could overflow/underflow" discussion entirely, and make the whole
> signed-vs-unsigned a total non-issue.
> 
> So the patch is a good cleanup. It doesn't fix any actual bugs, but it
> definitely fixes potential bugs (ie if somebody were to have a 32-bit
> compat mode on a 128-bit native kernel - something we don't actually
> have yet, but an example of a situation that would trigger the bug)

Yes, but... if we decrement that sucker at all, why do we need to play with
i at all?  We need exactly nr_compat_longs get_user(), so why not make _that_
the condition in the single-level loop?  Just do store when we would've started
to shift by BITS_PER_LONG (and reset the shift, obviously).  And instead of
this if (), just check if we have something collected in 'm' once after the
end of loop.  AFAICS, it's faster and not harder to understand that way.
What I suggest is
	m = 0
	shift = 0
	repeat nr_compat_long times
		fetch um, return -EFAULT if that fails
		m |= (unsigned long)um << shift
		shift += BITS_PER_COMPAT_LONG
		if (shift == BITS_PER_LONG)
			shift = 0
			store m
	if (shift)
		store m

Re: [PATCH] compat: fix possible out-of-bound accesses in compat_get_bitmap() and compat_put_bitmap()

[Linus Torvalds]

On Fri, Jun 5, 2015 at 11:24 AM, Al Viro <viro@zeniv.linux.org.uk> wrote:
>
> Yes, but... if we decrement that sucker at all, why do we need to play with
> i at all?  We need exactly nr_compat_longs get_user(), so why not make _that_
> the condition in the single-level loop?

Yeah, I think that code could be clarified further, no argument there.

And wee could just do it the copy in compat_long_t directly on
little-endian and get rid of the complications entirely, but then we'd
have the worry of separate code for big-endian, so I guess that's not
worth it (it's not like this should be hugely performance-sensitive).

I think most of that code falls under "don't touch it if it ain't
broke", with the corollary being "touch it as little as possible even
when it is broke"

                Linus