[PATCH v2] lzo: fix ip overrun during compress.

[PATCH v2] lzo: fix ip overrun during compress.

[Yueyi Li]

It`s possible ip overrun in lzo1x_1_do_compress() when compressed page is
point to the end of memory and which virtual address is 0xfffffffffffff000.
Leading to a NULL pointer access during the get_unaligned_le32(ip).

Fix this panic:
[ 2738.034508] Unable to handle kernel NULL pointer dereference at virtual address 00000009
[ 2738.034515] Mem abort info:
[ 2738.034518]   Exception class = DABT (current EL), IL = 32 bits
[ 2738.034520]   SET = 0, FnV = 0
[ 2738.034523]   EA = 0, S1PTW = 0
[ 2738.034524]   FSC = 5
[ 2738.034526] Data abort info:
[ 2738.034528]   ISV = 0, ISS = 0x00000005
[ 2738.034530]   CM = 0, WnR = 0
[ 2738.034533] user pgtable: 4k pages, 39-bit VAs, pgd = ffffffff94cee000
[ 2738.034535] [0000000000000009] *pgd=0000000000000000, *pud=0000000000000000
...
[ 2738.034592] pc : lzo1x_1_do_compress+0x198/0x610
[ 2738.034595] lr : lzo1x_1_compress+0x98/0x3d8
[ 2738.034597] sp : ffffff801caa3470 pstate : 00c00145
[ 2738.034598] x29: ffffff801caa3500 x28: 0000000000001000
[ 2738.034601] x27: 0000000000001000 x26: fffffffffffff000
[ 2738.034604] x25: ffffffff4ebc0000 x24: 0000000000000000
[ 2738.034607] x23: 000000000000004c x22: fffffffffffff7b8
[ 2738.034610] x21: ffffffff2e2ee0b3 x20: ffffffff2e2ee0bb
[ 2738.034612] x19: 0000000000000fcc x18: fffffffffffff84a
[ 2738.034615] x17: 00000000801b03d6 x16: 0000000000000782
[ 2738.034618] x15: ffffffff2e2ee0bf x14: fffffffffffffff0
[ 2738.034620] x13: 000000000000000f x12: 0000000000000020
[ 2738.034623] x11: 000000001824429d x10: ffffffffffffffec
[ 2738.034626] x9 : 0000000000000009 x8 : 0000000000000000
[ 2738.034628] x7 : 0000000000000868 x6 : 0000000000000434
[ 2738.034631] x5 : ffffffff4ebc0000 x4 : 0000000000000000
[ 2738.034633] x3 : ffffff801caa3510 x2 : ffffffff2e2ee000
[ 2738.034636] x1 : 0000000000000000 x0 : fffffffffffff000
...
[ 2738.034717] Process kworker/u16:1 (pid: 8705, stack limit = 0xffffff801caa0000)
[ 2738.034720] Call trace:
[ 2738.034722]  lzo1x_1_do_compress+0x198/0x610
[ 2738.034725]  lzo_compress+0x48/0x88
[ 2738.034729]  crypto_compress+0x14/0x20
[ 2738.034733]  zcomp_compress+0x2c/0x38
[ 2738.034736]  zram_bvec_rw+0x3d0/0x860
[ 2738.034738]  zram_rw_page+0x88/0xe0
[ 2738.034742]  bdev_write_page+0x70/0xc0
[ 2738.034745]  __swap_writepage+0x58/0x3f8
[ 2738.034747]  swap_writepage+0x40/0x50
[ 2738.034750]  shrink_page_list+0x4fc/0xe58
[ 2738.034753]  reclaim_pages_from_list+0xa0/0x150
[ 2738.034756]  reclaim_pte_range+0x18c/0x1f8
[ 2738.034759]  __walk_page_range+0xf8/0x1e0
[ 2738.034762]  walk_page_range+0xf8/0x130
[ 2738.034765]  reclaim_task_anon+0xcc/0x168
[ 2738.034767]  swap_fn+0x438/0x668
[ 2738.034771]  process_one_work+0x1fc/0x460
[ 2738.034773]  worker_thread+0x2d0/0x478
[ 2738.034775]  kthread+0x110/0x120
[ 2738.034778]  ret_from_fork+0x10/0x18
[ 2738.034781] Code: 3800167f 54ffffa8 d100066f 14000031 (b9400131)
[ 2738.034784] ---[ end trace 9b5cca106f0e54d1 ]---
[ 2738.035473] Kernel panic - not syncing: Fatal exception

crash> dis lzo1x_1_do_compress+100 3 -l
../kernel/msm-4.14/lib/lzo/lzo1x_compress.c: 44
0xffffff8dec8c6af4 <lzo1x_1_do_compress+100>:   cmp     x9, x10
0xffffff8dec8c6af8 <lzo1x_1_do_compress+104>:   b.cc    0xffffff8dec8c6c28
0xffffff8dec8c6afc <lzo1x_1_do_compress+108>:   b       0xffffff8dec8c7094

crash> dis lzo1x_1_do_compress+0x198
0xffffff8dec8c6c28 <lzo1x_1_do_compress+408>:   ldr     w17, [x9]

ip = x9 = 0x0000000000000009 is overflow.

Signed-off-by: liyueyi <liyueyi@live.com>
---
 lib/lzo/lzo1x_compress.c | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)

diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
index 236eb21..b15082b 100644
--- a/lib/lzo/lzo1x_compress.c
+++ b/lib/lzo/lzo1x_compress.c
@@ -17,6 +17,9 @@
 #include <linux/lzo.h>
 #include "lzodefs.h"
 
+#define OVERFLOW_ADD_CHECK(a, b)  \
+		(((a) + (b)) < (a))
+
 static noinline size_t
 lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		    unsigned char *out, size_t *out_len,
@@ -39,6 +42,8 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		size_t t, m_len, m_off;
 		u32 dv;
 literal:
+		if (unlikely(OVERFLOW_ADD_CHECK(ip, 1 + ((ip - ii) >> 5))))
+			break;
 		ip += 1 + ((ip - ii) >> 5);
 next:
 		if (unlikely(ip >= ip_end))
@@ -99,7 +104,8 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 				m_len += 8;
 				v = get_unaligned((const u64 *) (ip + m_len)) ^
 				    get_unaligned((const u64 *) (m_pos + m_len));
-				if (unlikely(ip + m_len >= ip_end))
+				if (unlikely(OVERFLOW_ADD_CHECK(ip, m_len)
+						|| (ip + m_len >= ip_end)))
 					goto m_len_done;
 			} while (v == 0);
 		}
@@ -124,7 +130,8 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 				m_len += 4;
 				v = get_unaligned((const u32 *) (ip + m_len)) ^
 				    get_unaligned((const u32 *) (m_pos + m_len));
-				if (unlikely(ip + m_len >= ip_end))
+				if (unlikely(OVERFLOW_ADD_CHECK(ip, m_len)
+						|| (ip + m_len >= ip_end)))
 					goto m_len_done;
 			} while (v == 0);
 		}
@@ -160,7 +167,8 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 				if (ip[m_len] != m_pos[m_len])
 					break;
 				m_len += 1;
-				if (unlikely(ip + m_len >= ip_end))
+				if (unlikely(OVERFLOW_ADD_CHECK(ip, m_len)
+						|| (ip + m_len >= ip_end)))
 					goto m_len_done;
 			} while (ip[m_len] == m_pos[m_len]);
 		}
-- 
2.7.4

Re: [PATCH v2] lzo: fix ip overrun during compress.

[David Sterba]

Adding Markus to to CC

On Wed, Nov 28, 2018 at 07:31:26AM +0000, Yueyi Li wrote:
> It`s possible ip overrun in lzo1x_1_do_compress() when compressed page is
> point to the end of memory and which virtual address is 0xfffffffffffff000.
> Leading to a NULL pointer access during the get_unaligned_le32(ip).

So this could happen in practice in zram, but unlikely for other users
of lzo (like btrfs). I'm not sure but expect that the last page would
not be returned by allocator.

The fix is adding a few branches to code that's supposed to be as fast
as possible. The branches would be evaluated all the time while
protecting against one signle bad page address. This does not look like
a good performance tradeoff.

> +#define OVERFLOW_ADD_CHECK(a, b)  \
> +		(((a) + (b)) < (a))

I'm not sure if this is generally safe overflow check (never not
optimized out). Here it depends on the types of 'a' and 'b' that are
pointer (ip) and size_t (m_len). GCC has __builtin_add_overflow_p so
that one should be used where possible.

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Willy Tarreau]

Hi David,

On Wed, Nov 28, 2018 at 02:52:42PM +0100, David Sterba wrote:
> The fix is adding a few branches to code that's supposed to be as fast
> as possible. The branches would be evaluated all the time while
> protecting against one signle bad page address. This does not look like
> a good performance tradeoff.

That was my concern as well, though the simplified test should be cheaper
especially since the branch is (almost) never taken and easily predicted.

> > +#define OVERFLOW_ADD_CHECK(a, b)  \
> > +		(((a) + (b)) < (a))
> 
> I'm not sure if this is generally safe overflow check (never not
> optimized out). Here it depends on the types of 'a' and 'b' that are
> pointer (ip) and size_t (m_len). GCC has __builtin_add_overflow_p so
> that one should be used where possible.

Sure but that one came with gcc 7 which is not exactly a reasonable
prerequisite especially when it comes to stable kernels. However I'm
now seeing that we have include/linux/overflow.h which provides this.
I have not checked what versions support it though, but 4.14 already
doesn't have it. Thus a fallback will be needed anyway and maintaining
two versions is not exactly the best thing to have to do :-/

Willy

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Dave Rodgman]

On 28/11/2018 1:52 pm, David Sterba wrote:

> The fix is adding a few branches to code that's supposed to be as fast
> as possible. The branches would be evaluated all the time while
> protecting against one signle bad page address. This does not look like
> a good performance tradeoff.

As an alternative, for all but the first case, instead of:

if (unlikely(OVERFLOW_ADD_CHECK(ip, m_len) || (ip + m_len >= ip_end)))

I'd suggest we do:

if (unlikely((ip_end - ip) <= m_len))

which will be about as efficient as what's currently there, but doesn't 
have issues with overflow.

Dave

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Yueyi Li]

Hi Dave,


On 2018/11/30 0:49, Dave Rodgman wrote:
> On 28/11/2018 1:52 pm, David Sterba wrote:
>
>> The fix is adding a few branches to code that's supposed to be as fast
>> as possible. The branches would be evaluated all the time while
>> protecting against one signle bad page address. This does not look like
>> a good performance tradeoff.
> As an alternative, for all but the first case, instead of:
>
> if (unlikely(OVERFLOW_ADD_CHECK(ip, m_len) || (ip + m_len >= ip_end)))
>
> I'd suggest we do:
>
> if (unlikely((ip_end - ip) <= m_len))
>
> which will be about as efficient as what's currently there, but doesn't
> have issues with overflow.

Ooh, yes, pretty good solution to this, thanks.

> Dave

Thanks,
Yueyi

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Dave Rodgman]

> On 2018/11/30 0:49, Dave Rodgman wrote:
>> On 28/11/2018 1:52 pm, David Sterba wrote:
>>
>>> The fix is adding a few branches to code that's supposed to be as fast
>>> as possible. The branches would be evaluated all the time while
>>> protecting against one signle bad page address. This does not look like
>>> a good performance tradeoff.
>> As an alternative, for all but the first case, instead of:
>>
>> if (unlikely(OVERFLOW_ADD_CHECK(ip, m_len) || (ip + m_len >= ip_end)))
>>
>> I'd suggest we do:
>>
>> if (unlikely((ip_end - ip) <= m_len))
>>
>> which will be about as efficient as what's currently there, but doesn't
>> have issues with overflow.
> 
> Ooh, yes, pretty good solution to this, thanks.

Np :-)

Actually, looking more closely at the first case, something like this 
works quite well:

size_t inc = 1 + ((ip - ii) >> 5);
if (unlikely((ip_end - ip) <= inc))
	break;
ip += inc;

On arm64, this generates only a single branch instruction, so it's only 
two extra arithmetic operations more than the original code (using the 
macro results in an additional compare & branch).

I used this to explore the compiler output:

https://godbolt.org/z/ng2qGZ

Dave

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Yueyi Li]

On 2018/11/30 20:20, Dave Rodgman wrote:
>> On 2018/11/30 0:49, Dave Rodgman wrote:
>>> On 28/11/2018 1:52 pm, David Sterba wrote:
>>>
>>>> The fix is adding a few branches to code that's supposed to be as fast
>>>> as possible. The branches would be evaluated all the time while
>>>> protecting against one signle bad page address. This does not look like
>>>> a good performance tradeoff.
>>> As an alternative, for all but the first case, instead of:
>>>
>>> if (unlikely(OVERFLOW_ADD_CHECK(ip, m_len) || (ip + m_len >= ip_end)))
>>>
>>> I'd suggest we do:
>>>
>>> if (unlikely((ip_end - ip) <= m_len))
>>>
>>> which will be about as efficient as what's currently there, but doesn't
>>> have issues with overflow.
>> Ooh, yes, pretty good solution to this, thanks.
> Np :-)
>
> Actually, looking more closely at the first case, something like this
> works quite well:
>
> size_t inc = 1 + ((ip - ii) >> 5);
> if (unlikely((ip_end - ip) <= inc))
> 	break;
> ip += inc;
>
> On arm64, this generates only a single branch instruction, so it's only
> two extra arithmetic operations more than the original code (using the
> macro results in an additional compare & branch).
>
How about just instead of:

   if (unlikely(ip >= ip_end))
         break;

to:

   if(unlikely((ip - ip_end) < ~in_len))
         break;

This just generates only one more arithmetic operation than original 
code, not easy to grasp but more efficient.


Thanks,
Yueyi

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Yueyi Li]

On 2018/12/3 10:46, Yueyi Li wrote:
>
>
> On 2018/11/30 20:20, Dave Rodgman wrote:
>>> On 2018/11/30 0:49, Dave Rodgman wrote:
>>>> On 28/11/2018 1:52 pm, David Sterba wrote:
>>>>
>>>>> The fix is adding a few branches to code that's supposed to be as 
>>>>> fast
>>>>> as possible. The branches would be evaluated all the time while
>>>>> protecting against one signle bad page address. This does not look 
>>>>> like
>>>>> a good performance tradeoff.
>>>> As an alternative, for all but the first case, instead of:
>>>>
>>>> if (unlikely(OVERFLOW_ADD_CHECK(ip, m_len) || (ip + m_len >= ip_end)))
>>>>
>>>> I'd suggest we do:
>>>>
>>>> if (unlikely((ip_end - ip) <= m_len))
>>>>
>>>> which will be about as efficient as what's currently there, but 
>>>> doesn't
>>>> have issues with overflow.
>>> Ooh, yes, pretty good solution to this, thanks.
>> Np :-)
>>
>> Actually, looking more closely at the first case, something like this
>> works quite well:
>>
>> size_t inc = 1 + ((ip - ii) >> 5);
>> if (unlikely((ip_end - ip) <= inc))
>>     break;
>> ip += inc;
>>
>> On arm64, this generates only a single branch instruction, so it's only
>> two extra arithmetic operations more than the original code (using the
>> macro results in an additional compare & branch).
>>
> How about just instead of:
>
>   if (unlikely(ip >= ip_end))
>         break;
>
> to:
>
>   if(unlikely((ip - ip_end) < ~in_len))
>         break;
>
> This just generates only one more arithmetic operation than original 
> code, not easy to grasp but more efficient.
>
>

Sorry, should be:

   if(unlikely((ip - ip_end) < ~(in_len - 20)))
         break;

> Thanks,
> Yueyi
>
>

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Markus F.X.J. Oberhumer]

Hi,

I don't think that address space wraparound is legal in C, but I
understand that we are in kernel land and if you really want to
compress the last virtual page 0xfffffffffffff000 the following
small patch should fix that dubious case.

This also avoids slowing down the the hot path of the compression
core function.

Cheers,
Markus



diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
index 236eb21167b5..959dec45f6fe 100644
--- a/lib/lzo/lzo1x_compress.c
+++ b/lib/lzo/lzo1x_compress.c
@@ -224,8 +224,8 @@ int lzo1x_1_compress(const unsigned char *in, size_t in_len,
 
        while (l > 20) {
                size_t ll = l <= (M4_MAX_OFFSET + 1) ? l : (M4_MAX_OFFSET + 1);
-               uintptr_t ll_end = (uintptr_t) ip + ll;
-               if ((ll_end + ((t + ll) >> 5)) <= ll_end)
+               // check for address space wraparound
+               if (((uintptr_t) ip + ll + ((t + ll) >> 5)) <= (uintptr_t) ip)
                        break;
                BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
                memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));



On 2018-11-28 14:52, David Sterba wrote:
> Adding Markus to to CC
> 
> On Wed, Nov 28, 2018 at 07:31:26AM +0000, Yueyi Li wrote:
>> It`s possible ip overrun in lzo1x_1_do_compress() when compressed page is
>> point to the end of memory and which virtual address is 0xfffffffffffff000.
>> Leading to a NULL pointer access during the get_unaligned_le32(ip).
> 
> So this could happen in practice in zram, but unlikely for other users
> of lzo (like btrfs). I'm not sure but expect that the last page would
> not be returned by allocator.
> 
> The fix is adding a few branches to code that's supposed to be as fast
> as possible. The branches would be evaluated all the time while
> protecting against one signle bad page address. This does not look like
> a good performance tradeoff.
> 
>> +#define OVERFLOW_ADD_CHECK(a, b)  \
>> +		(((a) + (b)) < (a))
> 
> I'm not sure if this is generally safe overflow check (never not
> optimized out). Here it depends on the types of 'a' and 'b' that are
> pointer (ip) and size_t (m_len). GCC has __builtin_add_overflow_p so
> that one should be used where possible.
> 

-- 
Markus Oberhumer, <markus@oberhumer.com>, http://www.oberhumer.com/

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Yueyi Li]

Hi Markus,

Thanks for your review.

On 2018/12/4 18:20, Markus F.X.J. Oberhumer wrote:
> Hi,
>
> I don't think that address space wraparound is legal in C, but I
> understand that we are in kernel land and if you really want to
> compress the last virtual page 0xfffffffffffff000 the following
> small patch should fix that dubious case.

I guess the VA 0xfffffffffffff000 is available because KASLR be
enabled. For this case we can see:

crash> kmem 0xfffffffffffff000
       PAGE               PHYSICAL      MAPPING       INDEX CNT FLAGS
ffffffbfffffffc0        1fffff000 ffffffff1655ecb9  7181fd5  2 
8000000000064209 locked,uptodate,owner_priv_1,writeback,reclaim,swapbacked

> This also avoids slowing down the the hot path of the compression
> core function.
>
> Cheers,
> Markus
>
>
>
> diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
> index 236eb21167b5..959dec45f6fe 100644
> --- a/lib/lzo/lzo1x_compress.c
> +++ b/lib/lzo/lzo1x_compress.c
> @@ -224,8 +224,8 @@ int lzo1x_1_compress(const unsigned char *in, size_t in_len,
>   
>          while (l > 20) {
>                  size_t ll = l <= (M4_MAX_OFFSET + 1) ? l : (M4_MAX_OFFSET + 1);
> -               uintptr_t ll_end = (uintptr_t) ip + ll;
> -               if ((ll_end + ((t + ll) >> 5)) <= ll_end)
> +               // check for address space wraparound
> +               if (((uintptr_t) ip + ll + ((t + ll) >> 5)) <= (uintptr_t) ip)
>                          break;
>                  BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
>                  memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
I parsed panic ramdump and loaded CPU register values,  can see:

-000|lzo1x_1_do_compress(
     |    in = 0xFFFFFFFFFFFFF000,
     |  ?,
     |    out = 0xFFFFFFFF2E2EE000,
     |    out_len = 0xFFFFFF801CAA3510,
     |  ?,
     |    wrkmem = 0xFFFFFFFF4EBC0000)
     |  dict = 0xFFFFFFFF4EBC0000
     |  op = 0x1
     |  ip = 0x9
     |  ii = 0x9
     |  in_end = 0x0
     |  ip_end = 0xFFFFFFFFFFFFFFEC
     |  m_len = 0
     |  m_off = 1922
-001|lzo1x_1_compress(
     |    in = 0xFFFFFFFFFFFFF000,
     |    in_len = 0,
     |    out = 0xFFFFFFFF2E2EE000,
     |    out_len = 0x00000001616FB7D0,
     |    wrkmem = 0xFFFFFFFF4EBC0000)
     |  ip = 0xFFFFFFFFFFFFF000
     |  op = 0xFFFFFFFF2E2EE000
     |  l = 4096
     |  t = 0
     |  ll = 4096

ll = l = in_len = 4096 in lzo1x_1_compress,  so your patch is working 
for this panic case, but, I`m
not sure, is it possible that in = 0xFFFFFFFFFFFFF000 and  in_len < 4096?


Thanks,
Yueyi

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Markus F.X.J. Oberhumer]

Hi Yueyi,

yes, my LZO patch works for all cases.

The reason behind the issue in the first place is that if KASLR
includes the very last page 0xfffffffffffff000 then we do not have a
valid C "pointer to an object" anymore because of address wraparound.

Unrelated to my patch I'd argue that KASLR should *NOT* include the
very last page - indeed that might cause similar wraparound problems
in lots of code.

Eg, look at this simple clear_memory() implementation:

void clear_memory(char *p, size_t len) {
        char *end = p + len;
        while (p < end)
                *p++= 0;
}

Valid code like this will fail horribly when (p, len) is the very
last virtual page (because end will be the NULL pointer in this case).

Cheers,
Markus



On 2018-12-05 04:07, Yueyi Li wrote:
> Hi Markus,
> 
> Thanks for your review.
> 
> On 2018/12/4 18:20, Markus F.X.J. Oberhumer wrote:
>> Hi,
>>
>> I don't think that address space wraparound is legal in C, but I
>> understand that we are in kernel land and if you really want to
>> compress the last virtual page 0xfffffffffffff000 the following
>> small patch should fix that dubious case.
> 
> I guess the VA 0xfffffffffffff000 is available because KASLR be
> enabled. For this case we can see:
> 
> crash> kmem 0xfffffffffffff000
>        PAGE               PHYSICAL      MAPPING       INDEX CNT FLAGS
> ffffffbfffffffc0        1fffff000 ffffffff1655ecb9  7181fd5  2 
> 8000000000064209 locked,uptodate,owner_priv_1,writeback,reclaim,swapbacked
> 
>> This also avoids slowing down the the hot path of the compression
>> core function.
>>
>> Cheers,
>> Markus
>>
>>
>>
>> diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
>> index 236eb21167b5..959dec45f6fe 100644
>> --- a/lib/lzo/lzo1x_compress.c
>> +++ b/lib/lzo/lzo1x_compress.c
>> @@ -224,8 +224,8 @@ int lzo1x_1_compress(const unsigned char *in, size_t in_len,
>>   
>>          while (l > 20) {
>>                  size_t ll = l <= (M4_MAX_OFFSET + 1) ? l : (M4_MAX_OFFSET + 1);
>> -               uintptr_t ll_end = (uintptr_t) ip + ll;
>> -               if ((ll_end + ((t + ll) >> 5)) <= ll_end)
>> +               // check for address space wraparound
>> +               if (((uintptr_t) ip + ll + ((t + ll) >> 5)) <= (uintptr_t) ip)
>>                          break;
>>                  BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
>>                  memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
> I parsed panic ramdump and loaded CPU register values,  can see:
> 
> -000|lzo1x_1_do_compress(
>      |    in = 0xFFFFFFFFFFFFF000,
>      |  ?,
>      |    out = 0xFFFFFFFF2E2EE000,
>      |    out_len = 0xFFFFFF801CAA3510,
>      |  ?,
>      |    wrkmem = 0xFFFFFFFF4EBC0000)
>      |  dict = 0xFFFFFFFF4EBC0000
>      |  op = 0x1
>      |  ip = 0x9
>      |  ii = 0x9
>      |  in_end = 0x0
>      |  ip_end = 0xFFFFFFFFFFFFFFEC
>      |  m_len = 0
>      |  m_off = 1922
> -001|lzo1x_1_compress(
>      |    in = 0xFFFFFFFFFFFFF000,
>      |    in_len = 0,
>      |    out = 0xFFFFFFFF2E2EE000,
>      |    out_len = 0x00000001616FB7D0,
>      |    wrkmem = 0xFFFFFFFF4EBC0000)
>      |  ip = 0xFFFFFFFFFFFFF000
>      |  op = 0xFFFFFFFF2E2EE000
>      |  l = 4096
>      |  t = 0
>      |  ll = 4096
> 
> ll = l = in_len = 4096 in lzo1x_1_compress,  so your patch is working 
> for this panic case, but, I`m
> not sure, is it possible that in = 0xFFFFFFFFFFFFF000 and  in_len < 4096?
> 
> 
> Thanks,
> Yueyi
> 

-- 
Markus Oberhumer, <markus@oberhumer.com>, http://www.oberhumer.com/

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Yueyi Li]

Hi Markus,

OK, thanks. I`ll change it in v3.

Thanks,
Yueyi

On 2018/12/6 23:03, Markus F.X.J. Oberhumer wrote:
> Hi Yueyi,
>
> yes, my LZO patch works for all cases.
>
> The reason behind the issue in the first place is that if KASLR
> includes the very last page 0xfffffffffffff000 then we do not have a
> valid C "pointer to an object" anymore because of address wraparound.
>
> Unrelated to my patch I'd argue that KASLR should *NOT* include the
> very last page - indeed that might cause similar wraparound problems
> in lots of code.
>
> Eg, look at this simple clear_memory() implementation:
>
> void clear_memory(char *p, size_t len) {
>          char *end = p + len;
>          while (p < end)
>                  *p++= 0;
> }
>
> Valid code like this will fail horribly when (p, len) is the very
> last virtual page (because end will be the NULL pointer in this case).
>
> Cheers,
> Markus
>
>
>
> On 2018-12-05 04:07, Yueyi Li wrote:
>> Hi Markus,
>>
>> Thanks for your review.
>>
>> On 2018/12/4 18:20, Markus F.X.J. Oberhumer wrote:
>>> Hi,
>>>
>>> I don't think that address space wraparound is legal in C, but I
>>> understand that we are in kernel land and if you really want to
>>> compress the last virtual page 0xfffffffffffff000 the following
>>> small patch should fix that dubious case.
>> I guess the VA 0xfffffffffffff000 is available because KASLR be
>> enabled. For this case we can see:
>>
>> crash> kmem 0xfffffffffffff000
>>         PAGE               PHYSICAL      MAPPING       INDEX CNT FLAGS
>> ffffffbfffffffc0        1fffff000 ffffffff1655ecb9  7181fd5  2
>> 8000000000064209 locked,uptodate,owner_priv_1,writeback,reclaim,swapbacked
>>
>>> This also avoids slowing down the the hot path of the compression
>>> core function.
>>>
>>> Cheers,
>>> Markus
>>>
>>>
>>>
>>> diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
>>> index 236eb21167b5..959dec45f6fe 100644
>>> --- a/lib/lzo/lzo1x_compress.c
>>> +++ b/lib/lzo/lzo1x_compress.c
>>> @@ -224,8 +224,8 @@ int lzo1x_1_compress(const unsigned char *in, size_t in_len,
>>>    
>>>           while (l > 20) {
>>>                   size_t ll = l <= (M4_MAX_OFFSET + 1) ? l : (M4_MAX_OFFSET + 1);
>>> -               uintptr_t ll_end = (uintptr_t) ip + ll;
>>> -               if ((ll_end + ((t + ll) >> 5)) <= ll_end)
>>> +               // check for address space wraparound
>>> +               if (((uintptr_t) ip + ll + ((t + ll) >> 5)) <= (uintptr_t) ip)
>>>                           break;
>>>                   BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
>>>                   memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
>> I parsed panic ramdump and loaded CPU register values,  can see:
>>
>> -000|lzo1x_1_do_compress(
>>       |    in = 0xFFFFFFFFFFFFF000,
>>       |  ?,
>>       |    out = 0xFFFFFFFF2E2EE000,
>>       |    out_len = 0xFFFFFF801CAA3510,
>>       |  ?,
>>       |    wrkmem = 0xFFFFFFFF4EBC0000)
>>       |  dict = 0xFFFFFFFF4EBC0000
>>       |  op = 0x1
>>       |  ip = 0x9
>>       |  ii = 0x9
>>       |  in_end = 0x0
>>       |  ip_end = 0xFFFFFFFFFFFFFFEC
>>       |  m_len = 0
>>       |  m_off = 1922
>> -001|lzo1x_1_compress(
>>       |    in = 0xFFFFFFFFFFFFF000,
>>       |    in_len = 0,
>>       |    out = 0xFFFFFFFF2E2EE000,
>>       |    out_len = 0x00000001616FB7D0,
>>       |    wrkmem = 0xFFFFFFFF4EBC0000)
>>       |  ip = 0xFFFFFFFFFFFFF000
>>       |  op = 0xFFFFFFFF2E2EE000
>>       |  l = 4096
>>       |  t = 0
>>       |  ll = 4096
>>
>> ll = l = in_len = 4096 in lzo1x_1_compress,  so your patch is working
>> for this panic case, but, I`m
>> not sure, is it possible that in = 0xFFFFFFFFFFFFF000 and  in_len < 4096?
>>
>>
>> Thanks,
>> Yueyi
>>

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Markus F.X.J. Oberhumer]

I still claim that (0xfffffffffffff000, 4096) is not a valid C "pointer
to an object" according to the C standard - please see my reply below.

And I thought ASLR was introduced to improve security and not to create
new security problems - someone from the ASLR team has to comment on this.

Cheers,
Markus


On 2018-12-12 06:21, Yueyi Li wrote:
> Hi Markus,
> 
> OK, thanks. I`ll change it in v3.
> 
> Thanks,
> Yueyi
> 
> On 2018/12/6 23:03, Markus F.X.J. Oberhumer wrote:
>> Hi Yueyi,
>>
>> yes, my LZO patch works for all cases.
>>
>> The reason behind the issue in the first place is that if KASLR
>> includes the very last page 0xfffffffffffff000 then we do not have a
>> valid C "pointer to an object" anymore because of address wraparound.
>>
>> Unrelated to my patch I'd argue that KASLR should *NOT* include the
>> very last page - indeed that might cause similar wraparound problems
>> in lots of code.
>>
>> Eg, look at this simple clear_memory() implementation:
>>
>> void clear_memory(char *p, size_t len) {
>>          char *end = p + len;
>>          while (p < end)
>>                  *p++= 0;
>> }
>>
>> Valid code like this will fail horribly when (p, len) is the very
>> last virtual page (because end will be the NULL pointer in this case).
>>
>> Cheers,
>> Markus
>>
>>
>>
>> On 2018-12-05 04:07, Yueyi Li wrote:
>>> Hi Markus,
>>>
>>> Thanks for your review.
>>>
>>> On 2018/12/4 18:20, Markus F.X.J. Oberhumer wrote:
>>>> Hi,
>>>>
>>>> I don't think that address space wraparound is legal in C, but I
>>>> understand that we are in kernel land and if you really want to
>>>> compress the last virtual page 0xfffffffffffff000 the following
>>>> small patch should fix that dubious case.
>>> I guess the VA 0xfffffffffffff000 is available because KASLR be
>>> enabled. For this case we can see:
>>>
>>> crash> kmem 0xfffffffffffff000
>>>         PAGE               PHYSICAL      MAPPING       INDEX CNT FLAGS
>>> ffffffbfffffffc0        1fffff000 ffffffff1655ecb9  7181fd5  2
>>> 8000000000064209 locked,uptodate,owner_priv_1,writeback,reclaim,swapbacked
>>>
>>>> This also avoids slowing down the the hot path of the compression
>>>> core function.
>>>>
>>>> Cheers,
>>>> Markus
>>>>
>>>>
>>>>
>>>> diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
>>>> index 236eb21167b5..959dec45f6fe 100644
>>>> --- a/lib/lzo/lzo1x_compress.c
>>>> +++ b/lib/lzo/lzo1x_compress.c
>>>> @@ -224,8 +224,8 @@ int lzo1x_1_compress(const unsigned char *in, size_t in_len,
>>>>    
>>>>           while (l > 20) {
>>>>                   size_t ll = l <= (M4_MAX_OFFSET + 1) ? l : (M4_MAX_OFFSET + 1);
>>>> -               uintptr_t ll_end = (uintptr_t) ip + ll;
>>>> -               if ((ll_end + ((t + ll) >> 5)) <= ll_end)
>>>> +               // check for address space wraparound
>>>> +               if (((uintptr_t) ip + ll + ((t + ll) >> 5)) <= (uintptr_t) ip)
>>>>                           break;
>>>>                   BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
>>>>                   memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
>>> I parsed panic ramdump and loaded CPU register values,  can see:
>>>
>>> -000|lzo1x_1_do_compress(
>>>       |    in = 0xFFFFFFFFFFFFF000,
>>>       |  ?,
>>>       |    out = 0xFFFFFFFF2E2EE000,
>>>       |    out_len = 0xFFFFFF801CAA3510,
>>>       |  ?,
>>>       |    wrkmem = 0xFFFFFFFF4EBC0000)
>>>       |  dict = 0xFFFFFFFF4EBC0000
>>>       |  op = 0x1
>>>       |  ip = 0x9
>>>       |  ii = 0x9
>>>       |  in_end = 0x0
>>>       |  ip_end = 0xFFFFFFFFFFFFFFEC
>>>       |  m_len = 0
>>>       |  m_off = 1922
>>> -001|lzo1x_1_compress(
>>>       |    in = 0xFFFFFFFFFFFFF000,
>>>       |    in_len = 0,
>>>       |    out = 0xFFFFFFFF2E2EE000,
>>>       |    out_len = 0x00000001616FB7D0,
>>>       |    wrkmem = 0xFFFFFFFF4EBC0000)
>>>       |  ip = 0xFFFFFFFFFFFFF000
>>>       |  op = 0xFFFFFFFF2E2EE000
>>>       |  l = 4096
>>>       |  t = 0
>>>       |  ll = 4096
>>>
>>> ll = l = in_len = 4096 in lzo1x_1_compress,  so your patch is working
>>> for this panic case, but, I`m
>>> not sure, is it possible that in = 0xFFFFFFFFFFFFF000 and  in_len < 4096?
>>>
>>>
>>> Thanks,
>>> Yueyi
>>>
> 
> 

-- 
Markus Oberhumer, <markus@oberhumer.com>, http://www.oberhumer.com/

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Richard Weinberger]

[CC'ing Kees]

On Wed, Dec 12, 2018 at 1:37 PM Markus F.X.J. Oberhumer
<markus@oberhumer.com> wrote:
>
> I still claim that (0xfffffffffffff000, 4096) is not a valid C "pointer
> to an object" according to the C standard - please see my reply below.
>
> And I thought ASLR was introduced to improve security and not to create
> new security problems - someone from the ASLR team has to comment on this.
>
> Cheers,
> Markus
>
>
> On 2018-12-12 06:21, Yueyi Li wrote:
> > Hi Markus,
> >
> > OK, thanks. I`ll change it in v3.
> >
> > Thanks,
> > Yueyi
> >
> > On 2018/12/6 23:03, Markus F.X.J. Oberhumer wrote:
> >> Hi Yueyi,
> >>
> >> yes, my LZO patch works for all cases.
> >>
> >> The reason behind the issue in the first place is that if KASLR
> >> includes the very last page 0xfffffffffffff000 then we do not have a
> >> valid C "pointer to an object" anymore because of address wraparound.
> >>
> >> Unrelated to my patch I'd argue that KASLR should *NOT* include the
> >> very last page - indeed that might cause similar wraparound problems
> >> in lots of code.
> >>
> >> Eg, look at this simple clear_memory() implementation:
> >>
> >> void clear_memory(char *p, size_t len) {
> >>          char *end = p + len;
> >>          while (p < end)
> >>                  *p++= 0;
> >> }
> >>
> >> Valid code like this will fail horribly when (p, len) is the very
> >> last virtual page (because end will be the NULL pointer in this case).
> >>
> >> Cheers,
> >> Markus
> >>
> >>
> >>
> >> On 2018-12-05 04:07, Yueyi Li wrote:
> >>> Hi Markus,
> >>>
> >>> Thanks for your review.
> >>>
> >>> On 2018/12/4 18:20, Markus F.X.J. Oberhumer wrote:
> >>>> Hi,
> >>>>
> >>>> I don't think that address space wraparound is legal in C, but I
> >>>> understand that we are in kernel land and if you really want to
> >>>> compress the last virtual page 0xfffffffffffff000 the following
> >>>> small patch should fix that dubious case.
> >>> I guess the VA 0xfffffffffffff000 is available because KASLR be
> >>> enabled. For this case we can see:
> >>>
> >>> crash> kmem 0xfffffffffffff000
> >>>         PAGE               PHYSICAL      MAPPING       INDEX CNT FLAGS
> >>> ffffffbfffffffc0        1fffff000 ffffffff1655ecb9  7181fd5  2
> >>> 8000000000064209 locked,uptodate,owner_priv_1,writeback,reclaim,swapbacked
> >>>
> >>>> This also avoids slowing down the the hot path of the compression
> >>>> core function.
> >>>>
> >>>> Cheers,
> >>>> Markus
> >>>>
> >>>>
> >>>>
> >>>> diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
> >>>> index 236eb21167b5..959dec45f6fe 100644
> >>>> --- a/lib/lzo/lzo1x_compress.c
> >>>> +++ b/lib/lzo/lzo1x_compress.c
> >>>> @@ -224,8 +224,8 @@ int lzo1x_1_compress(const unsigned char *in, size_t in_len,
> >>>>
> >>>>           while (l > 20) {
> >>>>                   size_t ll = l <= (M4_MAX_OFFSET + 1) ? l : (M4_MAX_OFFSET + 1);
> >>>> -               uintptr_t ll_end = (uintptr_t) ip + ll;
> >>>> -               if ((ll_end + ((t + ll) >> 5)) <= ll_end)
> >>>> +               // check for address space wraparound
> >>>> +               if (((uintptr_t) ip + ll + ((t + ll) >> 5)) <= (uintptr_t) ip)
> >>>>                           break;
> >>>>                   BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
> >>>>                   memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
> >>> I parsed panic ramdump and loaded CPU register values,  can see:
> >>>
> >>> -000|lzo1x_1_do_compress(
> >>>       |    in = 0xFFFFFFFFFFFFF000,
> >>>       |  ?,
> >>>       |    out = 0xFFFFFFFF2E2EE000,
> >>>       |    out_len = 0xFFFFFF801CAA3510,
> >>>       |  ?,
> >>>       |    wrkmem = 0xFFFFFFFF4EBC0000)
> >>>       |  dict = 0xFFFFFFFF4EBC0000
> >>>       |  op = 0x1
> >>>       |  ip = 0x9
> >>>       |  ii = 0x9
> >>>       |  in_end = 0x0
> >>>       |  ip_end = 0xFFFFFFFFFFFFFFEC
> >>>       |  m_len = 0
> >>>       |  m_off = 1922
> >>> -001|lzo1x_1_compress(
> >>>       |    in = 0xFFFFFFFFFFFFF000,
> >>>       |    in_len = 0,
> >>>       |    out = 0xFFFFFFFF2E2EE000,
> >>>       |    out_len = 0x00000001616FB7D0,
> >>>       |    wrkmem = 0xFFFFFFFF4EBC0000)
> >>>       |  ip = 0xFFFFFFFFFFFFF000
> >>>       |  op = 0xFFFFFFFF2E2EE000
> >>>       |  l = 4096
> >>>       |  t = 0
> >>>       |  ll = 4096
> >>>
> >>> ll = l = in_len = 4096 in lzo1x_1_compress,  so your patch is working
> >>> for this panic case, but, I`m
> >>> not sure, is it possible that in = 0xFFFFFFFFFFFFF000 and  in_len < 4096?
> >>>
> >>>
> >>> Thanks,
> >>> Yueyi
> >>>
> >
> >
>
> --
> Markus Oberhumer, <markus@oberhumer.com>, http://www.oberhumer.com/



-- 
Thanks,
//richard

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Kees Cook]

On Fri, Dec 14, 2018 at 5:56 AM Richard Weinberger
<richard.weinberger@gmail.com> wrote:
>
> [CC'ing Kees]
>
> On Wed, Dec 12, 2018 at 1:37 PM Markus F.X.J. Oberhumer
> <markus@oberhumer.com> wrote:
> >
> > I still claim that (0xfffffffffffff000, 4096) is not a valid C "pointer
> > to an object" according to the C standard - please see my reply below.
> >
> > And I thought ASLR was introduced to improve security and not to create
> > new security problems - someone from the ASLR team has to comment on this.
> >
> > Cheers,
> > Markus
> >
> >
> > On 2018-12-12 06:21, Yueyi Li wrote:
> > > Hi Markus,
> > >
> > > OK, thanks. I`ll change it in v3.
> > >
> > > Thanks,
> > > Yueyi
> > >
> > > On 2018/12/6 23:03, Markus F.X.J. Oberhumer wrote:
> > >> Hi Yueyi,
> > >>
> > >> yes, my LZO patch works for all cases.
> > >>
> > >> The reason behind the issue in the first place is that if KASLR
> > >> includes the very last page 0xfffffffffffff000 then we do not have a
> > >> valid C "pointer to an object" anymore because of address wraparound.
> > >>
> > >> Unrelated to my patch I'd argue that KASLR should *NOT* include the
> > >> very last page - indeed that might cause similar wraparound problems
> > >> in lots of code.
> > >>
> > >> Eg, look at this simple clear_memory() implementation:
> > >>
> > >> void clear_memory(char *p, size_t len) {
> > >>          char *end = p + len;
> > >>          while (p < end)
> > >>                  *p++= 0;
> > >> }
> > >>
> > >> Valid code like this will fail horribly when (p, len) is the very
> > >> last virtual page (because end will be the NULL pointer in this case).
> > >>
> > >> Cheers,
> > >> Markus
> > >>
> > >>
> > >>
> > >> On 2018-12-05 04:07, Yueyi Li wrote:
> > >>> Hi Markus,
> > >>>
> > >>> Thanks for your review.
> > >>>
> > >>> On 2018/12/4 18:20, Markus F.X.J. Oberhumer wrote:
> > >>>> Hi,
> > >>>>
> > >>>> I don't think that address space wraparound is legal in C, but I
> > >>>> understand that we are in kernel land and if you really want to
> > >>>> compress the last virtual page 0xfffffffffffff000 the following
> > >>>> small patch should fix that dubious case.
> > >>> I guess the VA 0xfffffffffffff000 is available because KASLR be
> > >>> enabled. For this case we can see:

This is a weird case: I would expect the top 4k to be unmapped to
leave room of ERR_PTR, etc.

> > >>>
> > >>> crash> kmem 0xfffffffffffff000
> > >>>         PAGE               PHYSICAL      MAPPING       INDEX CNT FLAGS
> > >>> ffffffbfffffffc0        1fffff000 ffffffff1655ecb9  7181fd5  2
> > >>> 8000000000064209 locked,uptodate,owner_priv_1,writeback,reclaim,swapbacked
> > >>>
> > >>>> This also avoids slowing down the the hot path of the compression
> > >>>> core function.
> > >>>>
> > >>>> Cheers,
> > >>>> Markus
> > >>>>
> > >>>>
> > >>>>
> > >>>> diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
> > >>>> index 236eb21167b5..959dec45f6fe 100644
> > >>>> --- a/lib/lzo/lzo1x_compress.c
> > >>>> +++ b/lib/lzo/lzo1x_compress.c
> > >>>> @@ -224,8 +224,8 @@ int lzo1x_1_compress(const unsigned char *in, size_t in_len,
> > >>>>
> > >>>>           while (l > 20) {
> > >>>>                   size_t ll = l <= (M4_MAX_OFFSET + 1) ? l : (M4_MAX_OFFSET + 1);
> > >>>> -               uintptr_t ll_end = (uintptr_t) ip + ll;
> > >>>> -               if ((ll_end + ((t + ll) >> 5)) <= ll_end)
> > >>>> +               // check for address space wraparound
> > >>>> +               if (((uintptr_t) ip + ll + ((t + ll) >> 5)) <= (uintptr_t) ip)
> > >>>>                           break;

Please just use the standard add overflow checks from the kernel. See
include/linux/overflow.h

Specifically, check_add_overflow(operand1, operand2, &result). I
assume something like:

if (check_add_overflow(ip, ll, &ll_end))
   freak_out();

?

> > >>>>                   BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
> > >>>>                   memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
> > >>> I parsed panic ramdump and loaded CPU register values,  can see:
> > >>>
> > >>> -000|lzo1x_1_do_compress(
> > >>>       |    in = 0xFFFFFFFFFFFFF000,
> > >>>       |  ?,
> > >>>       |    out = 0xFFFFFFFF2E2EE000,
> > >>>       |    out_len = 0xFFFFFF801CAA3510,
> > >>>       |  ?,
> > >>>       |    wrkmem = 0xFFFFFFFF4EBC0000)
> > >>>       |  dict = 0xFFFFFFFF4EBC0000
> > >>>       |  op = 0x1
> > >>>       |  ip = 0x9
> > >>>       |  ii = 0x9
> > >>>       |  in_end = 0x0
> > >>>       |  ip_end = 0xFFFFFFFFFFFFFFEC
> > >>>       |  m_len = 0
> > >>>       |  m_off = 1922
> > >>> -001|lzo1x_1_compress(
> > >>>       |    in = 0xFFFFFFFFFFFFF000,
> > >>>       |    in_len = 0,
> > >>>       |    out = 0xFFFFFFFF2E2EE000,
> > >>>       |    out_len = 0x00000001616FB7D0,
> > >>>       |    wrkmem = 0xFFFFFFFF4EBC0000)
> > >>>       |  ip = 0xFFFFFFFFFFFFF000
> > >>>       |  op = 0xFFFFFFFF2E2EE000
> > >>>       |  l = 4096
> > >>>       |  t = 0
> > >>>       |  ll = 4096
> > >>>
> > >>> ll = l = in_len = 4096 in lzo1x_1_compress,  so your patch is working
> > >>> for this panic case, but, I`m
> > >>> not sure, is it possible that in = 0xFFFFFFFFFFFFF000 and  in_len < 4096?
> > >>>
> > >>>
> > >>> Thanks,
> > >>> Yueyi
> > >>>
> > >
> > >
> >
> > --
> > Markus Oberhumer, <markus@oberhumer.com>, http://www.oberhumer.com/
>
>
>
> --
> Thanks,
> //richard



-- 
Kees Cook

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Markus F.X.J. Oberhumer]

Yueyi,

if ASLR does indeed exclude the last page (like it should), how do
you get the invalid (0xfffffffffffff000, 4096) mapping then?

~Markus


On 2018-12-14 17:46, Kees Cook wrote:
> On Fri, Dec 14, 2018 at 5:56 AM Richard Weinberger
> <richard.weinberger@gmail.com> wrote:
>>
>> [CC'ing Kees]
>>
>> On Wed, Dec 12, 2018 at 1:37 PM Markus F.X.J. Oberhumer
>> <markus@oberhumer.com> wrote:
>>>
>>> I still claim that (0xfffffffffffff000, 4096) is not a valid C "pointer
>>> to an object" according to the C standard - please see my reply below.
>>>
>>> And I thought ASLR was introduced to improve security and not to create
>>> new security problems - someone from the ASLR team has to comment on this.
>>>
>>> Cheers,
>>> Markus
>>>
>>>
>>> On 2018-12-12 06:21, Yueyi Li wrote:
>>>> Hi Markus,
>>>>
>>>> OK, thanks. I`ll change it in v3.
>>>>
>>>> Thanks,
>>>> Yueyi
>>>>
>>>> On 2018/12/6 23:03, Markus F.X.J. Oberhumer wrote:
>>>>> Hi Yueyi,
>>>>>
>>>>> yes, my LZO patch works for all cases.
>>>>>
>>>>> The reason behind the issue in the first place is that if KASLR
>>>>> includes the very last page 0xfffffffffffff000 then we do not have a
>>>>> valid C "pointer to an object" anymore because of address wraparound.
>>>>>
>>>>> Unrelated to my patch I'd argue that KASLR should *NOT* include the
>>>>> very last page - indeed that might cause similar wraparound problems
>>>>> in lots of code.
>>>>>
>>>>> Eg, look at this simple clear_memory() implementation:
>>>>>
>>>>> void clear_memory(char *p, size_t len) {
>>>>>          char *end = p + len;
>>>>>          while (p < end)
>>>>>                  *p++= 0;
>>>>> }
>>>>>
>>>>> Valid code like this will fail horribly when (p, len) is the very
>>>>> last virtual page (because end will be the NULL pointer in this case).
>>>>>
>>>>> Cheers,
>>>>> Markus
>>>>>
>>>>>
>>>>>
>>>>> On 2018-12-05 04:07, Yueyi Li wrote:
>>>>>> Hi Markus,
>>>>>>
>>>>>> Thanks for your review.
>>>>>>
>>>>>> On 2018/12/4 18:20, Markus F.X.J. Oberhumer wrote:
>>>>>>> Hi,
>>>>>>>
>>>>>>> I don't think that address space wraparound is legal in C, but I
>>>>>>> understand that we are in kernel land and if you really want to
>>>>>>> compress the last virtual page 0xfffffffffffff000 the following
>>>>>>> small patch should fix that dubious case.
>>>>>> I guess the VA 0xfffffffffffff000 is available because KASLR be
>>>>>> enabled. For this case we can see:
> 
> This is a weird case: I would expect the top 4k to be unmapped to
> leave room of ERR_PTR, etc.
> 
>>>>>>
>>>>>> crash> kmem 0xfffffffffffff000
>>>>>>         PAGE               PHYSICAL      MAPPING       INDEX CNT FLAGS
>>>>>> ffffffbfffffffc0        1fffff000 ffffffff1655ecb9  7181fd5  2
>>>>>> 8000000000064209 locked,uptodate,owner_priv_1,writeback,reclaim,swapbacked
>>>>>>
>>>>>>> This also avoids slowing down the the hot path of the compression
>>>>>>> core function.
>>>>>>>
>>>>>>> Cheers,
>>>>>>> Markus
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
>>>>>>> index 236eb21167b5..959dec45f6fe 100644
>>>>>>> --- a/lib/lzo/lzo1x_compress.c
>>>>>>> +++ b/lib/lzo/lzo1x_compress.c
>>>>>>> @@ -224,8 +224,8 @@ int lzo1x_1_compress(const unsigned char *in, size_t in_len,
>>>>>>>
>>>>>>>           while (l > 20) {
>>>>>>>                   size_t ll = l <= (M4_MAX_OFFSET + 1) ? l : (M4_MAX_OFFSET + 1);
>>>>>>> -               uintptr_t ll_end = (uintptr_t) ip + ll;
>>>>>>> -               if ((ll_end + ((t + ll) >> 5)) <= ll_end)
>>>>>>> +               // check for address space wraparound
>>>>>>> +               if (((uintptr_t) ip + ll + ((t + ll) >> 5)) <= (uintptr_t) ip)
>>>>>>>                           break;
> 
> Please just use the standard add overflow checks from the kernel. See
> include/linux/overflow.h
> 
> Specifically, check_add_overflow(operand1, operand2, &result). I
> assume something like:
> 
> if (check_add_overflow(ip, ll, &ll_end))
>    freak_out();
> 
> ?
> 
>>>>>>>                   BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
>>>>>>>                   memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
>>>>>> I parsed panic ramdump and loaded CPU register values,  can see:
>>>>>>
>>>>>> -000|lzo1x_1_do_compress(
>>>>>>       |    in = 0xFFFFFFFFFFFFF000,
>>>>>>       |  ?,
>>>>>>       |    out = 0xFFFFFFFF2E2EE000,
>>>>>>       |    out_len = 0xFFFFFF801CAA3510,
>>>>>>       |  ?,
>>>>>>       |    wrkmem = 0xFFFFFFFF4EBC0000)
>>>>>>       |  dict = 0xFFFFFFFF4EBC0000
>>>>>>       |  op = 0x1
>>>>>>       |  ip = 0x9
>>>>>>       |  ii = 0x9
>>>>>>       |  in_end = 0x0
>>>>>>       |  ip_end = 0xFFFFFFFFFFFFFFEC
>>>>>>       |  m_len = 0
>>>>>>       |  m_off = 1922
>>>>>> -001|lzo1x_1_compress(
>>>>>>       |    in = 0xFFFFFFFFFFFFF000,
>>>>>>       |    in_len = 0,
>>>>>>       |    out = 0xFFFFFFFF2E2EE000,
>>>>>>       |    out_len = 0x00000001616FB7D0,
>>>>>>       |    wrkmem = 0xFFFFFFFF4EBC0000)
>>>>>>       |  ip = 0xFFFFFFFFFFFFF000
>>>>>>       |  op = 0xFFFFFFFF2E2EE000
>>>>>>       |  l = 4096
>>>>>>       |  t = 0
>>>>>>       |  ll = 4096
>>>>>>
>>>>>> ll = l = in_len = 4096 in lzo1x_1_compress,  so your patch is working
>>>>>> for this panic case, but, I`m
>>>>>> not sure, is it possible that in = 0xFFFFFFFFFFFFF000 and  in_len < 4096?
>>>>>>
>>>>>>
>>>>>> Thanks,
>>>>>> Yueyi
>>>>>>
>>>>
>>>>
>>>
>>> --
>>> Markus Oberhumer, <markus@oberhumer.com>, http://www.oberhumer.com/
>>
>>
>>
>> --
>> Thanks,
>> //richard
> 
> 
> 

-- 
Markus Oberhumer, <markus@oberhumer.com>, http://www.oberhumer.com/

Re: [PATCH v2] lzo: fix ip overrun during compress.

[Yueyi Li]

Hi Markus & Kees,

On 2018/12/17 0:56, Markus F.X.J. Oberhumer wrote:
> Yueyi,
>
> if ASLR does indeed exclude the last page (like it should), how do
> you get the invalid (0xfffffffffffff000, 4096) mapping then?
Regarding following code, seems ASLR is align to ARM64_MEMSTART_ALIGN,I
don`t think it will exclude the top 4K address space.

```
if (IS_ENABLED(CONFIG_RANDOMIZE_BASE)) {
         extern u16 memstart_offset_seed;
         u64 range = linear_region_size -
                    (bootloader_memory_limit - memblock_start_of_DRAM());

         /*
          * If the size of the linear region exceeds, by a sufficient
          * margin, the size of the region that the available physical
          * memory spans, randomize the linear region as well.
          */
         if (memstart_offset_seed > 0 && range >= ARM64_MEMSTART_ALIGN) {
                 range = range / ARM64_MEMSTART_ALIGN + 1;
                 memstart_addr -= ARM64_MEMSTART_ALIGN *
                                  ((range * memstart_offset_seed) >> 16);
         }
}
```

Thanks,
Yueyi