g1mv / density

Superfast compression library
Apache License 2.0
1.02k stars 48 forks source link

Crash in density_memory_teleport_read_reserved #16

Closed nemequ closed 9 years ago

nemequ commented 9 years ago

My density plugin is crashing on ARM. I do

density_stream_create (NULL, NULL); // returns 0xb5200640
density_stream_prepare (0xb5200640, 0xb35ff800, 102171, 0xb34fd800, 1048576); // returns 0
density_stream_decompress_continue (0xb5200640);

Density allocates 1024 at 0xb480b980 (memory_teleport.c:37), then tries to memcpy(0xb480b980, 0xb35ff810, 102155).

And I end up with a crash in density_memory_teleport_read_reserved:

==3054==ERROR: AddressSanitizer: unknown-crash on address 0xb480b980 at pc 0xb3ce9445 bp 0xbef2fd88 sp 0xbef2fd8c
WRITE of size 102155 at 0xb480b980 thread T0
    #0 0xb3ce9443 in memcpy /usr/include/arm-linux-gnueabihf/bits/string3.h:51
    #1 0xb3ce9443 in density_memory_teleport_read_reserved /home/nemequ/squash/plugins/density/density/src/memory_teleport.c:132
    #2 0xb3cd155b in density_chameleon_decode_continue /home/nemequ/squash/plugins/density/density/src/kernel_chameleon_decode.c:173
    #3 0xb3cc9ef5 in density_block_decode_continue /home/nemequ/squash/plugins/density/density/src/block_decode.c:218
    #4 0xb3ce6a3b in density_decode_continue /home/nemequ/squash/plugins/density/density/src/main_decode.c:110
    #5 0xb3cf548f in density_stream_decompress_continue /home/nemequ/squash/plugins/density/density/src/stream.c:223
    #6 0xb3cc7781 in squash_density_process_stream /home/nemequ/squash/plugins/density/squash-density.c:369
    #7 0xb6a6a7cb in squash_stream_process_internal /home/nemequ/squash/squash/stream.c:515
    #8 0xb6a6add7 in squash_stream_process /home/nemequ/squash/squash/stream.c:619
    #9 0xb6a5eff9 in squash_codec_process_file_with_options /home/nemequ/squash/squash/codec.c:1087
    #10 0xb6a5f22d in squash_codec_decompress_file_with_options /home/nemequ/squash/squash/codec.c:1162
    #11 0xad71 in main /home/nemequ/squash/utils/squash.c:292
    #12 0xb6966631 in __libc_start_main (/lib/arm-linux-gnueabihf/libc.so.6+0x17631)

0xb480bd80 is located 0 bytes to the right of 1024-byte region [0xb480b980,0xb480bd80)
allocated by thread T0 here:
    #0 0xb6abd343 in __interceptor_malloc (/usr/lib/arm-linux-gnueabihf/libasan.so.1+0x43343)
    #1 0xb3ce7c69 in density_memory_teleport_allocate /home/nemequ/squash/plugins/density/density/src/memory_teleport.c:37
    #2 0xb3cf4809 in density_stream_create /home/nemequ/squash/plugins/density/density/src/stream.c:40
    #3 0xb3cc8d81 in squash_density_stream_init /home/nemequ/squash/plugins/density/squash-density.c:193
    #4 0xb3cc8d81 in squash_density_stream_new /home/nemequ/squash/plugins/density/squash-density.c:179
    #5 0xb3cc8d81 in squash_density_create_stream /home/nemequ/squash/plugins/density/squash-density.c:222
    #6 0xb6a5d20d in squash_codec_create_stream_with_options /home/nemequ/squash/squash/codec.c:507
    #7 0xb6a5ee83 in squash_codec_process_file_with_options /home/nemequ/squash/squash/codec.c:1064
    #8 0xb6a5f22d in squash_codec_decompress_file_with_options /home/nemequ/squash/squash/codec.c:1162
    #9 0xad71 in main /home/nemequ/squash/utils/squash.c:292
    #10 0xb6966631 in __libc_start_main (/lib/arm-linux-gnueabihf/libc.so.6+0x17631)

SUMMARY: AddressSanitizer: unknown-crash /usr/include/arm-linux-gnueabihf/bits/string3.h:51 memcpy
Shadow bytes around the buggy address:
  0x369016e0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x369016f0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x36901700: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x36901710: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x36901720: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x36901730:[00]00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x36901740: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x36901750: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x36901760: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x36901770: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x36901780: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Contiguous container OOB:fc
  ASan internal:           fe
==3054==ABORTING
nemequ commented 9 years ago

Test case:

#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <stdlib.h>

#include "density/src/density_api.h"

#define OUTPUT_BUFFER_SIZE (1024 * 1024)

int main(int argc, char *argv[])
{
  FILE* input_fp = fopen (argv[1], "rw");
  assert (input_fp != NULL);
  int input = fileno (input_fp);
  assert (input != -1);

  struct stat sb;
  fstat (input, &sb);

  uint8_t* compressed = mmap (NULL, sb.st_size, PROT_READ, MAP_SHARED, input, 0);
  assert (compressed != MAP_FAILED);
  uint8_t* decompressed = malloc (OUTPUT_BUFFER_SIZE);
  assert (decompressed != NULL);

  fprintf (stderr, "%d: density_stream_create (NULL, NULL);", __LINE__);
  density_stream* stream = density_stream_create (NULL, NULL);
  fprintf (stderr, " -> %p\n", stream);

  fprintf (stderr, "%d: density_stream_prepare (%p, %p, %ld, %p, %d);\n", __LINE__, stream, compressed, sb.st_size, decompressed, OUTPUT_BUFFER_SIZE);
  DENSITY_STREAM_STATE state = density_stream_prepare(stream, compressed, sb.st_size, decompressed, OUTPUT_BUFFER_SIZE);
  fprintf (stderr, " -> %d\n", state);
  assert (state == DENSITY_STREAM_STATE_READY);

  fprintf (stderr, "%d: density_stream_decompress_init (%p, NULL);", __LINE__, stream);
  state = density_stream_decompress_init (stream, NULL);
  fprintf (stderr, " -> %d\n", state);

  fprintf (stderr, "%d: density_stream_decompress_continue (%p);\n", __LINE__, stream);
  density_stream_decompress_continue (stream);

  fprintf (stderr, "Success\n");

  return 0;
}

If you can't reproduce I can provide SSH access to the board. For the input file I think anything fairly large will trigger it, but I've been using http://code.coeusgroup.com/alice29.txt.density (alice29.txt from the canterbury corpus, compressed with chameleon).

g1mv commented 9 years ago

It is possible that this could be fixed in the dev branch as I've increased the memory teleport buffer size, could you give it a try ? Thanks

nemequ commented 9 years ago

No, unfortunately it's still there, though it has changed a bit. The buffer increased from 1024 to 4096 bytes, but it still tries to memcpy 102155 bytes. The problematic memcpy is now the one in density_memory_teleport_copy_from_direct_buffer_to_staging_buffer. Updated info from asan:

==16761==ERROR: AddressSanitizer: unknown-crash on address 0xb4d02900 at pc 0xbaf35 bp 0xbedd8da8 sp 0xbedd8dac
WRITE of size 102155 at 0xb4d02900 thread T0
    #0 0xbaf33 in density_memory_teleport_copy_from_direct_buffer_to_staging_buffer density/src/memory_teleport.c:74
    #1 0xbaf33 in density_memory_teleport_read density/src/memory_teleport.c:116
    #2 0xbaf33 in density_memory_teleport_read_reserved density/src/memory_teleport.c:123
    #3 0x1816f in density_chameleon_decode_continue density/src/kernel_chameleon_generic_decode.h:62
    #4 0xb85f in density_block_decode_continue density/src/block_decode.c:218
    #5 0xb69f7 in density_decode_continue density/src/main_decode.c:114
    #6 0xbf537 in density_stream_decompress_continue density/src/stream.c:223
    #7 0x9481 in main /home/nemequ/squash/plugins/density/test.c:46
    #8 0xb69e9631 in __libc_start_main (/lib/arm-linux-gnueabihf/libc.so.6+0x17631)

0xb4d03900 is located 0 bytes to the right of 4096-byte region [0xb4d02900,0xb4d03900)
allocated by thread T0 here:
    #0 0xb6b1d343 in __interceptor_malloc (/usr/lib/arm-linux-gnueabihf/libasan.so.1+0x43343)
    #1 0xb86bb in density_memory_teleport_allocate density/src/memory_teleport.c:40
    #2 0xbde23 in density_stream_create density/src/stream.c:40
    #3 0x91d7 in main /home/nemequ/squash/plugins/density/test.c:33
    #4 0xb69e9631 in __libc_start_main (/lib/arm-linux-gnueabihf/libc.so.6+0x17631)
g1mv commented 9 years ago

Ok thanks I'll look into this soon. Just to make sure, the same code works on x86 right ? Also it's probably irrelevant but you don't seem to use density_stream_decompress_finish I suppose that's just because you're giving an example code.

nemequ commented 9 years ago

It works on x86_64, no idea about x86. Right, I don't call decompress_finish because the crash is in continue--it never gets to where I would call finish.

Sent with AquaMail for Android http://www.aqua-mail.com

nemequ commented 9 years ago

I'm not trying to push you, but do you have any idea about when you'll have time for this? I'm updating my benchmark (preview of the new output: https://quixdb.github.io/squash-benchmark/), and I'm wondering if I should wait until density is fixed or just do the initial version without it.

Again, no pressure (it doesn't really matter much from my perspective if density is included or not), I just want to make a decision.

g1mv commented 9 years ago

No worries, your new layout seems nice although a bit "dense" maybe :) I'm actually looking for density to have more exposure so it would be great if it could be integrated in your new benchmark. I'm virtually hours of releasing 0.12.0 beta which boasts a new algorithm - not fully optimized yet but, I hope, promising - and speed enhancements, so inclusion of this version in your bench would be great ! I've had a quick look on the ARM bug and it's disconcerting for now, chameleon never reads more than a few hundred bytes at a time (streaming oblige) and on this platform it is requesting a reading of 100,000 bytes at once !? This is exceeding by far the staging buffer's capacity hence the bug, to fix this I would need an access to your platform with gdb to track down the origin of the problem. I can't promise anything but tomorrow I'll try to sort this out so everything works on ARM. One thing : it is little endian, correct ? because big endian code is probably buggy at this stage and would take a much longer time to fix.

For a quick reference here are the latest perf/file sizes from the dev branch (3b16ef8018bbb1f8f1b19790f0be49b7ef81f491) on my platform, sizes should be identical on ARM :

$ ./sharc -c1 -f enwik8
Compressed enwik8 (100,000,000 bytes) to enwik8.sharc (61,524,502 bytes) ➔ 61.5% (User time 0.113s ➔ 882 MB/s)
$ ./sharc -c2 -f enwik8
Compressed enwik8 (100,000,000 bytes) to enwik8.sharc (53,156,782 bytes) ➔ 53.2% (User time 0.212s ➔ 471 MB/s)
$ ./sharc -c3 -f enwik8
Compressed enwik8 (100,000,000 bytes) to enwik8.sharc (47,162,722 bytes) ➔ 47.2% (User time 0.412s ➔ 243 MB/s)
nemequ commented 9 years ago

No worries, your new layout seems nice although a bit "dense" maybe :)

Yeah, suggestions definitely welcome, but it's a lot of data (I'm benchmarking every codec at every level now, it used to be just the default level), so I'm not sure I can do much better :(

If anything comes to mind, please file an issue.

I'm actually looking for density to have more exposure so it would be great if it could be integrated in your new benchmark.

That's really why I finally got around to rewriting it. I'm going to try to get some press coverage for Squash… if it works, and if density performs, well I'm sure some of it will translate to exposure for density. I have a bunch of boards lined up, and the number of codecs Squash supports is pretty good now.

to fix this I would need an access to your platform with gdb to track down the origin of the problem.

That's not a problem at all. Paste your SSH key, I'll open up a hole for you.

One thing : it is little endian, correct ?

Yep. Unfortunately all my machines are little endian. I'm thinking about buying a MIPS Creator C120 (IIRC MIPS is big endian) largely so I can test big-endian, but I don't like the idea of giving money to Imagination Technologies (PowerVR being utter crap on Linux has cost me a lot)…

nemequ commented 9 years ago

on this platform it is requesting a reading of 100,000 bytes at once !?

It's worth mentioning that the input is, as I mentioned in the first comment, alice29.txt compressed with chameleon. That is 102171 bytes… close enough to the 102155 to make me very suspicious.

g1mv commented 9 years ago

Ok I'll test with this file, just sent you a PM with my public SSH key. Thanks !

g1mv commented 9 years ago

I just installed sharc on your Odroid C1 board (thanks for the access it worked perfectly), and I'm unable to reproduce using alice29.txt. The file compresses/decompresses nicely without any problem... Do you have a round trip test case (compress + decompress) ? I'm using the latest dev version of everything and that includes all the latest fixes, maybe the error was due to something fixed recently ?

Also for info alice29.txt compresses to 100,696 bytes with sharc and chameleon, this seems to differ from what you got. You should actually have less bytes if you don't use sharc as it adds some extra metadata.

nemequ commented 9 years ago

To get that data I'm doing this:

density_stream_create (NULL, NULL) // returns 0x1d420
density_stream_prepare (0x1d420, 0xb6bf0008, 152089, 0xb6aef008, 1048576) // returns 0
density_stream_compress_init (0x1d420, 1, 0) // returns 0
density_stream_compress_continue (0x1d420, NULL) // returns 1
density_stream_update_input (0x1d420, 0xb6c15221, 0)
density_stream_compress_finish (0x1d420, NULL) // returns 0
density_stream_update_output (0x1d420, 0xb6aef008, 1048576)
density_stream_destroy (0x1d420)

I'll try to turn that into a proper test, but it's kind of unrelated to the bug—best case for density is that the stream is invalid, but density should handle that by returning an error not passing a huge value to memcpy. At the very least this is a DoS vulnerability.

g1mv commented 9 years ago

Yes you're very right on that, but it's like when you use memcpy, at some stage you have to trust the devs, otherwise you start putting verification tests everywhere and it destroys the purpose of the library which is speed and efficiency. What I mean is that for example the memcpy implementation could do memory boundary checks and return cleanly but it doesn't because the designers assume that the devs know what they are doing, it's kind of the same thing here isn't it ?

nemequ commented 9 years ago

That is what assertions are for—they can be disabled in release builds, but enabled during development. However, that's not the problem here. It's okay to trust the code calling your library, but you absolutely can't trust the compressed data—that's a security issue. If I write a server which accepts compressed input, should someone be able to crash the whole thing just by sending malformed data? AFAICT this is only a DoS issue, but if you trust the input you can easily end up with remote execution vulnerabilities, too.

nemequ commented 9 years ago

Compressor:

#define _BSD_SOURCE
#define _POSIX_SOURCE

#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <stdlib.h>

#include "density/src/density_api.h"

#define MAX_OUTPUT_SIZE (1024 * 1024)

int main(int argc, char *argv[])
{
  FILE* input_fp = fopen (argv[1], "r+");
  assert (input_fp != NULL);
  int input = fileno (input_fp);
  assert (input != -1);
  FILE* output_fp = fopen (argv[2], "w+");
  assert (output_fp != NULL);
  int output = fileno (output_fp);
  assert (output != -1);

  struct stat sb;
  fstat (input, &sb);

  uint8_t* uncompressed = mmap (NULL, sb.st_size, PROT_READ, MAP_SHARED, input, 0);
  assert (uncompressed != MAP_FAILED);

  assert (ftruncate (output, MAX_OUTPUT_SIZE) == 0);
  uint8_t* compressed = mmap (NULL, MAX_OUTPUT_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, input, 0);
  assert (compressed != MAP_FAILED);

  fprintf (stderr, "%d: density_stream_create (NULL, NULL);", __LINE__);
  density_stream* stream = density_stream_create (NULL, NULL);
  fprintf (stderr, " -> %p\n", stream);

  fprintf (stderr, "%d: density_stream_prepare (%p, %p, %ld, %p, %d);", __LINE__, stream, uncompressed, sb.st_size, compressed, MAX_OUTPUT_SIZE);
  DENSITY_STREAM_STATE state = density_stream_prepare(stream, uncompressed, sb.st_size, compressed, MAX_OUTPUT_SIZE);
  fprintf (stderr, " -> %d\n", state);
  assert (state == DENSITY_STREAM_STATE_READY);

  fprintf (stderr, "%d: density_stream_compress_init (%p, DENSITY_COMPRESSION_MODE_CHAMELEON_ALGORITHM, DENSITY_BLOCK_TYPE_DEFAULT);", __LINE__, stream);
  state = density_stream_compress_init (stream, DENSITY_COMPRESSION_MODE_CHAMELEON_ALGORITHM, DENSITY_BLOCK_TYPE_DEFAULT);
  fprintf (stderr, " -> %d\n", state);
  assert (state == DENSITY_STREAM_STATE_READY);

  fprintf (stderr, "%d: density_stream_decompress_continue (%p);", __LINE__, stream);
  state = density_stream_compress_continue (stream);
  fprintf (stderr, " -> %d\n", state);
  assert (state == DENSITY_STREAM_STATE_STALL_ON_INPUT);

  fprintf (stderr, "%d: density_stream_update_input (%p, %p, 0);\n", __LINE__, stream, uncompressed + sb.st_size);
  density_stream_update_input (stream, uncompressed + sb.st_size, 0);

  fprintf (stderr, "%d: density_stream_compress_finish (%p, NULL);", __LINE__, stream);
  state = density_stream_compress_finish (stream);
  fprintf (stderr, " -> %d\n", state);
  assert (state == DENSITY_STREAM_STATE_READY);

  fprintf (stderr, "%d: density_stream_output_available_for_use (%p):", __LINE__, stream);
  uint_fast64_t outsize = density_stream_output_available_for_use (stream);
  fprintf (stderr, " -> %" PRIu64 "\n", outsize);

  fprintf (stderr, "%d: density_stream_destroy (%p);\n", __LINE__, stream);
  density_stream_destroy (stream);

  fprintf (stderr, "Success\n");

  return 0;
}
g1mv commented 9 years ago

Yes that's true, but it's very difficult to know if the input data is malformed or not because there is no clue (unless you use integrity checks) of what the output data has to look like. However I totally agree on the fact that it's unacceptable for a malformed input data to incur segfaults, but sadly I'm unable to reproduce the problem so far, even with the file you sent (alice29.txt.density) I can't get a segfault :)

g1mv commented 9 years ago

Perfect ! thanks I'll check this out

nemequ commented 9 years ago

The file I posted + the test case from the second comment should reliably reproduce it on ARM (both that ORDROID C1 and a Raspberry Pi 2, haven't tested any other boards).

g1mv commented 9 years ago

I get this on Odroid C1 :

39: density_stream_create (NULL, NULL); -> 0x132e8
43: density_stream_prepare (0x132e8, 0xb6b59000, 148480, 0xb6a59000, 1048576); -> 0
48: density_stream_compress_init (0x132e8, DENSITY_COMPRESSION_MODE_CHAMELEON_ALGORITHM, DENSITY_BLOCK_TYPE_DEFAULT); -> 0
53: density_stream_decompress_continue (0x132e8); -> 1
58: density_stream_update_input (0x132e8, 0xb6b7d400, 0);
61: density_stream_compress_finish (0x132e8, NULL); -> 0
66: density_stream_output_available_for_use (0x132e8): -> 100666
70: density_stream_destroy (0x132e8);
Success
nemequ commented 9 years ago

Since it memcpy could very well succeed, you shouldn't rely on it crashing 100% of the time, unless you compile with -fsanitize=address or something similar. Or you could put some printfs around that memcpy, or fire up gdb, etc.

g1mv commented 9 years ago

I also ran

for i in `seq 100`; do ./test alice29.txt alice29.txt.density; done

All of the iterations succeed.

nemequ commented 9 years ago

Try compiling with something like this:

gcc -std=c99 -fno-omit-frame-pointer -fsanitize=address -g -O0 -o test-decompress test-decompress.c density/src/*.c density/src/spookyhash/src/*.c
nemequ commented 9 years ago

I just put an executable and c file in your home folder on the odroid. If I run gcc -std=c99 -fno-omit-frame-pointer -fsanitize=address -g -O0 -o test-decompress test-decompress.c density/src/*.c density/src/spookyhash/src/*.c && ./test-decompress alice29.txt.density as you I'm seeing a crash reliably.

g1mv commented 9 years ago

Ok Houston I see a segfault as well ! Perfect I'll check this out.

g1mv commented 9 years ago

What's really interesting is that when I compile using :

gcc -std=c99 -L./density/ -Wall -fno-omit-frame-pointer -fsanitize=address -g -O0 -o test test-decompress.c -ldensity

and run

./test alice29.txt.density

I get

32: density_stream_create (NULL, NULL); -> 0xb5000be0
36: density_stream_prepare (0xb5000be0, 0xb5432000, 102171, 0xb51ff800, 1048576); -> 0
41: density_stream_decompress_init (0xb5000be0, NULL); -> 0
45: density_stream_decompress_continue (0xb5000be0);
Success

I compiled density as a library using the project's Makefile

nemequ commented 9 years ago

Unless you compiled density with asan that's not surprising—only test-decompress.c will be instrumented there.

Now to try to figure out what I'm doing wrong in the compressor…

g1mv commented 9 years ago

I found the problem, some obscure uint_fast allocation that fails. Fixing now.

g1mv commented 9 years ago

Fixed in 8ac642d6c5aed91ea0563591b561b9b3131ad8d0. Thanks a lot for your input, great stuff ! If everything works on your side I'll call it a go for the next beta, keep me advised.