More error detection

[GoogleCodeExporter]

In some cases, LZ4_uncompress does not return error codes when the input is 
invalid.

For example uncompressing [16, 42, 1, 0, 80, 42, 42, 42, 42, 42, 42] (which is 
a compressed form of an array of length 10 whose elements are all 42) with 
osize == 11 won't return an error, although the uncompressed length of the 
array is 10.

Additionally, LZ4 does not return errors when ref == op (dec == 0).

Original issue reported on code.google.com by jpou...@gmail.com on 29 Oct 2012 at 9:21

Attachments:

• lz4_error_detection.patch

[GoogleCodeExporter]

Thanks for notifying. It's clearly described.
I'll look into it.

Original comment by yann.col...@gmail.com on 29 Oct 2012 at 11:06

• Changed state: Accepted

[GoogleCodeExporter]

The first point is fairly clear.
The decoder exits silently becauses it believes it completed its job, which is 
true when the compressed stream is correct. But not if the stream is 
hand-crafted to be wrong, or if the output size is wrong.

The second point is clear too, but its interest more debatable.

If the "delta" is zero, it means, necessarily, that the decoding will be 
incorrect : we are essentially copying "noise" or more probably initialised 
values, such as "00".

When such a case does happen ?
Well, it cannot happen if the stream is produced by an LZ4 encoder, so the 
stream must be modified, either by error, or hand-crafted for this situation to 
be triggered.

If the stream is maliciously hand-crafted, then of course it is "wrong".
It's not possible to prevent such a scenario. There are many ways to modify a 
compressed stream "transparently". For example, just modify a few literals, or 
provide a wrong delta value. LZ4 will not detect that : it's not an encryption 
layer.

So we don't even try to do that. What we want to ensure is the LZ4 format 
cannot be exploited by attackers to silently crash a process or for any kind of 
buffer overflow scenario : LZ4 shall never read nor write outside of provided 
buffers.
Copying from a distance range of zero does not help for such a scenario. Since 
it's useless, we don't even bother with it.

So now, we are targeting "errors".
How many times this specific error will happen ?
I mean, we suppose only the delta value is wrong, AND its value is zero.
So, on a collection of 65536 possible delta values, 1 is correct, 65535 are 
wrong, and one of the wrong ones is 0. So we will detect one error among 65535 
possible ones. Does that really improve anything ?

To be fair, if it could be demonstrated that, when a delta value is wrong, it's 
more likely to be "zero", then okay, detecting this case could be useful.
Note that this detection has some cost : one test, one branch, so a potential 
burden to performance. Better be useful...

Original comment by yann.col...@gmail.com on 30 Oct 2012 at 2:46

[GoogleCodeExporter]

Thanks for the details, Yann. I just wanted to make LZ4 fail sooner when 
inconsistencies are encountered, these are not security issues: if one of them 
proves to make uncompression slower then I fully agree that it should not be 
fixed.

Thank you again!

Original comment by jpou...@gmail.com on 30 Oct 2012 at 3:10

[GoogleCodeExporter]

The following attached file is supposed to implement your first suggestion 
(regarding undetected end of file reached before oend).
I did not had time (yet) to test if the detection of delta=0 does cost some 
performance.

Original comment by yann.col...@gmail.com on 1 Nov 2012 at 5:46

Attachments:

• lz4_rc82.zip

[GoogleCodeExporter]

Corrected into r82.
Well i have only corrected the main part, regarding detecting early exit (when 
provided osize has wrong size). For the "delta 0" part, i'll have to start a 
more thorough benchmark session.

Thanks for the clear description and proposed correction.

Original comment by yann.col...@gmail.com on 3 Nov 2012 at 9:08

• Changed state: Fixed

[GoogleCodeExporter]

Thanks for the fix!

Original comment by jpou...@gmail.com on 3 Nov 2012 at 9:12