Kernel LZO compressor

Kernel LZO compressor

[Nick Terrell]

Hi Dave,

I just saw you patches adding LZO-RLE, so I decided to fuzz the LZO
compressor and decompressor. I didn't find any crashes, but I found some edge
cases in the decompressor.

After compressing the empty input with lzo1x_1_compress() I get
[0x11, 0x00, 0x00] which is rejected by lzo1x_decompress_safe() on line 60
because *ip == 17 and in_len < 5 with error LZO_E_INPUT_OVERRUN.

After compressing the input [0x00] with lzorle1x_1_compress() I get
[0x11, 0x01, 0x00, 0x11, 0x00, 0x00] which is rejected by
lzo1x_decompress_safe() with error LZO_E_OUTPUT_OVERRUN.

I ported LZO to userspace by copying the headers from the kernel to
userspace and/or rewriting them. The fuzzers and ported LZO are in
a GitHub repo so it can be easily reproduced [1]. The compression
fuzzer is also included inline below.

```
#undef NDEBUG
#include <string.h>
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>

#include "lzo.h"

char wrkmem[LZO1X_MEM_COMPRESS];

#define RLE 1

extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
  size_t outSize = lzo1x_worst_compress(size);
  uint8_t* const out = (uint8_t*)malloc(outSize);
  assert(out);
#if RLE
  assert(LZO_E_OK == lzorle1x_1_compress(data, size, out, &outSize, wrkmem));
#else
  assert(LZO_E_OK == lzo1x_1_compress(data, size, out, &outSize, wrkmem));
#endif
  uint8_t* const rt = (uint8_t*)malloc(size);
  assert(rt);
  size_t rtsize = size;
  int const ret = lzo1x_decompress_safe(out, outSize, rt, &rtsize);
  if (ret != LZO_E_OK) {
    assert(size < 4);
    fprintf(stderr, "INPUT: ");
    for (size_t i = 0; i < size; ++i)
      fprintf(stderr, "%u ", (unsigned)data[i]);
    fprintf(stderr, "\nOUTPUT: ");
    for (size_t i = 0; i < outSize; ++i)
      fprintf(stderr, "%u ", (unsigned)out[i]);
    fprintf(stderr, "\nret = %d\n", ret);
  }
  assert(ret == LZO_E_OK);
  assert(rtsize == size);
  assert(memcmp(data, rt, size) == 0);
  free(out);
  free(rt);
  return 0;
}
```

[1] https://github.com/terrelln/lzo-userspace-fuzz

Best,
Nick Terrell

Re: Kernel LZO compressor

[Dave Rodgman]

On 19/03/2019 8:15 pm, Nick Terrell wrote:
> Hi Dave,
>
> I just saw you patches adding LZO-RLE, so I decided to fuzz the LZO
> compressor and decompressor. I didn't find any crashes, but I found some edge
> cases in the decompressor.

Hi Nick,

Thanks - I will take a look at this. These cases won't affect zram, which is
currently the only place lzo-rle is used, because zram operates over complete
pages, but I would prefer not to have this kind of edge case lurking.

Presumably the fuzzer generates inputs of various sizes - how large did you
test up to?

thanks

Dave

>
> After compressing the empty input with lzo1x_1_compress() I get
> [0x11, 0x00, 0x00] which is rejected by lzo1x_decompress_safe() on line 60
> because *ip == 17 and in_len < 5 with error LZO_E_INPUT_OVERRUN.
>
> After compressing the input [0x00] with lzorle1x_1_compress() I get
> [0x11, 0x01, 0x00, 0x11, 0x00, 0x00] which is rejected by
> lzo1x_decompress_safe() with error LZO_E_OUTPUT_OVERRUN.
>
> I ported LZO to userspace by copying the headers from the kernel to
> userspace and/or rewriting them. The fuzzers and ported LZO are in
> a GitHub repo so it can be easily reproduced [1]. The compression
> fuzzer is also included inline below.
>
> ```
> #undef NDEBUG
> #include <string.h>
> #include <stdint.h>
> #include <stddef.h>
> #include <stdlib.h>
> #include <assert.h>
> #include <stdio.h>
>
> #include "lzo.h"
>
> char wrkmem[LZO1X_MEM_COMPRESS];
>
> #define RLE 1
>
> extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
>   size_t outSize = lzo1x_worst_compress(size);
>   uint8_t* const out = (uint8_t*)malloc(outSize);
>   assert(out);
> #if RLE
>   assert(LZO_E_OK == lzorle1x_1_compress(data, size, out, &outSize, wrkmem));
> #else
>   assert(LZO_E_OK == lzo1x_1_compress(data, size, out, &outSize, wrkmem));
> #endif
>   uint8_t* const rt = (uint8_t*)malloc(size);
>   assert(rt);
>   size_t rtsize = size;
>   int const ret = lzo1x_decompress_safe(out, outSize, rt, &rtsize);
>   if (ret != LZO_E_OK) {
>     assert(size < 4);
>     fprintf(stderr, "INPUT: ");
>     for (size_t i = 0; i < size; ++i)
>       fprintf(stderr, "%u ", (unsigned)data[i]);
>     fprintf(stderr, "\nOUTPUT: ");
>     for (size_t i = 0; i < outSize; ++i)
>       fprintf(stderr, "%u ", (unsigned)out[i]);
>     fprintf(stderr, "\nret = %d\n", ret);
>   }
>   assert(ret == LZO_E_OK);
>   assert(rtsize == size);
>   assert(memcmp(data, rt, size) == 0);
>   free(out);
>   free(rt);
>   return 0;
> }
> ```
>
> [1] https://github.com/terrelln/lzo-userspace-fuzz
>
> Best,
> Nick Terrell
>

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

Re: Kernel LZO compressor

[Nick Terrell]

> On Mar 25, 2019, at 6:13 AM, Dave Rodgman <dave.rodgman@arm.com> wrote:
> 
> On 19/03/2019 8:15 pm, Nick Terrell wrote:
>> Hi Dave,
>> 
>> I just saw you patches adding LZO-RLE, so I decided to fuzz the LZO
>> compressor and decompressor. I didn't find any crashes, but I found some edge
>> cases in the decompressor.
> 
> Hi Nick,
> 
> Thanks - I will take a look at this. These cases won't affect zram, which is
> currently the only place lzo-rle is used, because zram operates over complete
> pages, but I would prefer not to have this kind of edge case lurking.
> 
> Presumably the fuzzer generates inputs of various sizes - how large did you
> test up to?

I tested on inputs up to 4096 bytes large, which is the default, but the fuzzing
library libFuzzer has a flag -max_len which allows you to control the maximum
input size.

> thanks
> 
> Dave
> 
>> 
>> After compressing the empty input with lzo1x_1_compress() I get
>> [0x11, 0x00, 0x00] which is rejected by lzo1x_decompress_safe() on line 60
>> because *ip == 17 and in_len < 5 with error LZO_E_INPUT_OVERRUN.
>> 
>> After compressing the input [0x00] with lzorle1x_1_compress() I get
>> [0x11, 0x01, 0x00, 0x11, 0x00, 0x00] which is rejected by
>> lzo1x_decompress_safe() with error LZO_E_OUTPUT_OVERRUN.
>> 
>> I ported LZO to userspace by copying the headers from the kernel to
>> userspace and/or rewriting them. The fuzzers and ported LZO are in
>> a GitHub repo so it can be easily reproduced [1]. The compression
>> fuzzer is also included inline below.
>> 
>> ```
>> #undef NDEBUG
>> #include <string.h>
>> #include <stdint.h>
>> #include <stddef.h>
>> #include <stdlib.h>
>> #include <assert.h>
>> #include <stdio.h>
>> 
>> #include "lzo.h"
>> 
>> char wrkmem[LZO1X_MEM_COMPRESS];
>> 
>> #define RLE 1
>> 
>> extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
>>  size_t outSize = lzo1x_worst_compress(size);
>>  uint8_t* const out = (uint8_t*)malloc(outSize);
>>  assert(out);
>> #if RLE
>>  assert(LZO_E_OK == lzorle1x_1_compress(data, size, out, &outSize, wrkmem));
>> #else
>>  assert(LZO_E_OK == lzo1x_1_compress(data, size, out, &outSize, wrkmem));
>> #endif
>>  uint8_t* const rt = (uint8_t*)malloc(size);
>>  assert(rt);
>>  size_t rtsize = size;
>>  int const ret = lzo1x_decompress_safe(out, outSize, rt, &rtsize);
>>  if (ret != LZO_E_OK) {
>>    assert(size < 4);
>>    fprintf(stderr, "INPUT: ");
>>    for (size_t i = 0; i < size; ++i)
>>      fprintf(stderr, "%u ", (unsigned)data[i]);
>>    fprintf(stderr, "\nOUTPUT: ");
>>    for (size_t i = 0; i < outSize; ++i)
>>      fprintf(stderr, "%u ", (unsigned)out[i]);
>>    fprintf(stderr, "\nret = %d\n", ret);
>>  }
>>  assert(ret == LZO_E_OK);
>>  assert(rtsize == size);
>>  assert(memcmp(data, rt, size) == 0);
>>  free(out);
>>  free(rt);
>>  return 0;
>> }
>> ```
>> 
>> [1] https://github.com/terrelln/lzo-userspace-fuzz
>> 
>> Best,
>> Nick Terrell
>> 
> 
> IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.