Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
From:   Nick Terrell <terrelln@fb.com>
To:     "dave.rodgman@arm.com" <dave.rodgman@arm.com>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        Kernel Team <Kernel-team@fb.com>
Subject: Kernel LZO compressor
Thread-Topic: Kernel LZO compressor
Thread-Index: AQHU3pByWt4yBWNOP0ewGbmZjuuI6A==
Date:   Tue, 19 Mar 2019 20:15:07 +0000
Message-ID: <31D143C0-D64F-4905-B25F-5C3630D38913@fb.com>
Accept-Language: en-US
Content-Language: en-US
received-spf: None (protection.outlook.com: fb.com does not designate
 permitted sender hosts)
Content-Type: text/plain; charset="us-ascii"
Content-ID: <B76C7350B42D4846A33F964A76905327@namprd15.prod.outlook.com>
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: 5c73ff9b-6aa8-4978-ff83-08d6aca794fc
X-MS-Exchange-CrossTenant-originalarrivaltime: 19 Mar 2019 20:15:07.7137
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 8ae927fe-1255-47a7-a2af-5f3a069daaa2
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MW2PR1501MB2185
X-OriginatorOrg: fb.com
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2019-03-19_09:,,
 signatures=0
X-Proofpoint-Spam-Reason: safe
X-FB-Internal: Safe
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

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 ed=
ge
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 =3D=3D 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 =3D lzo1x_worst_compress(size);
  uint8_t* const out =3D (uint8_t*)malloc(outSize);
  assert(out);
#if RLE
  assert(LZO_E_OK =3D=3D lzorle1x_1_compress(data, size, out, &outSize, wrk=
mem));
#else
  assert(LZO_E_OK =3D=3D lzo1x_1_compress(data, size, out, &outSize, wrkmem=
));
#endif
  uint8_t* const rt =3D (uint8_t*)malloc(size);
  assert(rt);
  size_t rtsize =3D size;
  int const ret =3D lzo1x_decompress_safe(out, outSize, rt, &rtsize);
  if (ret !=3D LZO_E_OK) {
    assert(size < 4);
    fprintf(stderr, "INPUT: ");
    for (size_t i =3D 0; i < size; ++i)
      fprintf(stderr, "%u ", (unsigned)data[i]);
    fprintf(stderr, "\nOUTPUT: ");
    for (size_t i =3D 0; i < outSize; ++i)
      fprintf(stderr, "%u ", (unsigned)out[i]);
    fprintf(stderr, "\nret =3D %d\n", ret);
  }
  assert(ret =3D=3D LZO_E_OK);
  assert(rtsize =3D=3D size);
  assert(memcmp(data, rt, size) =3D=3D 0);
  free(out);
  free(rt);
  return 0;
}
```

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

Best,
Nick Terrell