LZ4_decompress_safe_partial is broken in 1.9.2

[jfkthame]

I'm seeing what I believe is incorrect behavior from LZ4_decompress_safe_partial in the latest release.

Specifically, in our use case we have a buffer of compressed data that may have a few bytes of padding at the end. We know the expected uncompressed size, but only the rounded-up (possibly padded) size of the compressed data. Therefore, we've been using LZ4_decompress_safe_partial to decompress, because it would ignore residual input once it has decompressed the expected targetOutputSize bytes (unlike LZ4_decompress_safe which expects that "compressedSize : is the exact complete size of the compressed block").

With the update from 1.9.1 to 1.9.2, however, the behavior of LZ4_decompress_safe_partial has changed, and it now returns an error if there are a small number of extra bytes at the end of the source. It works as expected if there's a lot of extra data; in this case, it stops successfully after decompressing the requested targetOutputSize. But when there are around 1-7 extra bytes -- exactly the sort of case that's likely to arise if we're working with a padded block -- it fails. I don't think this is expected behavior for this function.

See attached test file, which compares the behavior of LZ4_decompress_safe and LZ4_decompress_safe_partial when the given length of the source is slightly wrong. As expected, both fail if the source is truncated, and LZ4_decompress_safe also fails if the given compressedSize is too large. LZ4_decompress_safe_partial, however, fails for values of srcSize that are just slightly larger than needed (1-7 bytes), and then starts succeeding again for values that are substantially larger:

Length of source: 1313
Compressed size: 992
Trying input size 984:
  decompress_safe -> FAILED (-978)
  decompress_safe_partial -> FAILED (-978)
Trying input size 985:
  decompress_safe -> FAILED (-978)
  decompress_safe_partial -> FAILED (-978)
Trying input size 986:
  decompress_safe -> FAILED (-978)
  decompress_safe_partial -> FAILED (-978)
Trying input size 987:
  decompress_safe -> FAILED (-978)
  decompress_safe_partial -> FAILED (-978)
Trying input size 988:
  decompress_safe -> FAILED (-984)
  decompress_safe_partial -> FAILED (-984)
Trying input size 989:
  decompress_safe -> FAILED (-984)
  decompress_safe_partial -> FAILED (-984)
Trying input size 990:
  decompress_safe -> FAILED (-984)
  decompress_safe_partial -> FAILED (-984)
Trying input size 991:
  decompress_safe -> FAILED (-984)
  decompress_safe_partial -> FAILED (-984)
Trying input size 992:
  decompress_safe -> OK (1313) matches input? YES
  decompress_safe_partial -> OK (1313) matches input? YES
Trying input size 993:
  decompress_safe -> FAILED (-988)
  decompress_safe_partial -> FAILED (-988)
Trying input size 994:
  decompress_safe -> FAILED (-988)
  decompress_safe_partial -> FAILED (-988)
Trying input size 995:
  decompress_safe -> FAILED (-988)
  decompress_safe_partial -> FAILED (-988)
Trying input size 996:
  decompress_safe -> FAILED (-988)
  decompress_safe_partial -> FAILED (-988)
Trying input size 997:
  decompress_safe -> FAILED (-988)
  decompress_safe_partial -> FAILED (-988)
Trying input size 998:
  decompress_safe -> FAILED (-988)
  decompress_safe_partial -> FAILED (-988)
Trying input size 999:
  decompress_safe -> FAILED (-988)
  decompress_safe_partial -> FAILED (-988)
Trying input size 1000:
  decompress_safe -> FAILED (-996)
  decompress_safe_partial -> OK (1313) matches input? YES
Trying input size 1001:
  decompress_safe -> FAILED (-996)
  decompress_safe_partial -> OK (1313) matches input? YES
Trying input size 1002:
  decompress_safe -> FAILED (-996)
  decompress_safe_partial -> OK (1313) matches input? YES
Trying input size 1003:
  decompress_safe -> FAILED (-999)
  decompress_safe_partial -> OK (1313) matches input? YES
Trying input size 1004:
  decompress_safe -> FAILED (-999)
  decompress_safe_partial -> OK (1313) matches input? YES
Trying input size 1005:
  decompress_safe -> FAILED (-999)
  decompress_safe_partial -> OK (1313) matches input? YES
Trying input size 1006:
  decompress_safe -> FAILED (-1002)
  decompress_safe_partial -> OK (1313) matches input? YES
Trying input size 1007:
  decompress_safe -> FAILED (-1002)
  decompress_safe_partial -> OK (1313) matches input? YES

decompress-partial-test.c.txt

[Cyan4973]

Thanks for notification @jfkthame ,
the description of this issue does indeed sounds like a bug.
To be reproduced and investigated.

[jfkthame]

Any chance of this being investigated soon? It's currently blocking us from updating to 1.9.2, but I don't understand the LZ4 code well enough to feel confident attempting a local patch to work around the problem.

[Cyan4973]

I'm sorry, availability is very hard these days.
The topic is still in the todo list, it will be addressed, but I can't commit yet to a date unfortunately.

[szcnick]

In partial decompression (lz4.c line 1942), the number of remaining characters will be checked, but I do n’t think it should be used differently
before :
if ((ip + length> iend- (2 + 1 + LASTLITERALS)) && (ip + length! = iend))
after:
if (ip + length> iend)
then it will work

[Tragen]

This bugfix is very important for me. Can you tell me when we can have an official version with this fix included?

[hsiangkao]

Hi Yann,
I'm also worried about this issue... Since there are potential in-house kernel lz4 updates from lz4 upstream which could break the LZ4_decompress_safe_partial api and cause unexpected EROFS regression...

Could you kindly help consider some direct fix? Thanks Yann!

Thanks,
Gao Xiang

[Cyan4973]

It's definitely on my todo list.
But my short term availability has cratered towards zero.
I do plan to come back to LZ4 right after this busy period.

[Tragen]

Thanks, is there something how the "community" could help?
A lot of projects depend on LZ4 like OpenSSL and OpenSSL was also not really maintained.
This looks very similar. If such an important thing breaks, there should be a better way to handle it.

[Cyan4973]

I plan to spend some time on lz4 this summer,
with a release planned before the end of the summer.
This fix will be part of the picture.

In the meantime, if your need is more urgent, I can only suggest to apply a fix locally.

[Cyan4973]

I've spent a bit of time on this issue, and may have a better understanding now.
Let's discuss the described issue :

we have a buffer of compressed data that may have a few bytes of padding at the end. We know the expected uncompressed size, (...) but only the rounded-up (possibly padded) size of the compressed data. Therefore, we've been using LZ4_decompress_safe_partial to decompress, because it would ignore residual input once it has decompressed the expected targetOutputSize bytes (...)
With the update from 1.9.1 to 1.9.2, however, the behavior of LZ4_decompress_safe_partial has changed, and it now returns an error if there are a small number of extra bytes at the end of the source.

OK, so this part is important.
LZ4_decompress_safe_partial() was primarily developed to allow decompression of only the beginning of a block, instead of the entire block. It was primarily a speed hack.

The use case described is entirely different. Here, the objective is to decompress the full block. But the quirk is that, instead of providing the exact compressed size, only an upper bound is known.

Thing is, this capability never was a part of the contract.
As explained in its documentation:LZ4_decompress_safe_partial() expects a full block as input :

an LZ4 compressed block of size 'srcSize'.

It expects the exact size, not an upper bound.

Now, it may have nonetheless worked as OP intended up to v1.9.1, but this was just accidental.

It doesn't mean it's the end. Just it explains why this property "regressed" : nowhere was it tested, since it was not part of the contract.

Now, if we want to add this property to the contract, well it requires proper testing, and there might be surprises along the road.
To begin with, @BellaXlp PR sure improves things, but it seems does not cover all situations. A small fuzzer test adaptation is quickly able to generate test cases relevant to this issue which are not fixed by this patch.
Hence offering this new property will require more efforts. There are also additional risks : with multiple constraints pushed towards a single function, it could happen that some are incompatible, or the resulting code may become more difficult to understand, hence more difficult to maintain, and eventually may lead to a degradation of performance or introduction of new subtle bugs as an indirect consequence of complexity.

So this is still under investigation. My hope is that it can be achieved without introducing performance degradation, but that may require being creative in the way new constraints and associated runtime tests are added right into the hot decoding function.

[Cyan4973]

I'm currently wondering if it's a good idea to expose a function in charge of both objectives:
decompress less data than a full block, from an exact compressed size,
or decompress full block, but provide an upper bound of compressed size.

In the first scenario, it's also allowed to request a decompressed size which is larger than full block.
In which case, the decoder will only decompress up to the full block size (hence less than the requested amount).
The return value clearly tells how much data was regenerated, so it's well defined.

In the second scenario, since the input size is larger than the actual compressed block size,
it is extremely important that the amount of data to decompress be <= decompressed block size.
Otherwise, if both values are too large, the decoder won't recognize block's end, and will fail.
It's basically undefined.

Effectively, one of the 2 values, either compressed size or decompressed size, must be exact.
More complex scenarios are technically possible (larger compressed size + smaller decompressed size)
but others are not (larger compressed size + larger decompressed size)
and it becomes difficult to explain when the interface is valid to use or not.

It also strikes me that the intended scenario seems so close to what LZ4_decompress_fast() used to provide.
LZ4_decompress_fast() is unsafe though, and is now deprecated.
Still, the "unsafe" side could be fixed, by adding an argument providing an upper-bound of compressed size.

A minor advantage is that LZ4_decompress_fast() tells how many bytes were actually read from input, thus giving an idea of the compressed block size, an information that LZ4_decompress_safe_partial() will not provide.

Another difference is that it expects to decompress a full block, in contrast with LZ4_decompress_safe_partial() which can stop in the middle. Still, that would nonetheless match OP use case.

Anyway, that's the major take away of this post :
merging both capabilities into a single function seems to introduce undefined behaviors, including risks of silent corruption.
So maybe it would be better to separate cleanly those scenarios, make them use different functions.

[hsiangkao]

Hi Cyan,

I'm currently wondering if it's a good idea to expose a function in charge of both objectives:
decompress less data than a full block, from an exact compressed size,
or decompress full block, but provide an upper bound of compressed size.

Yeah, but there exists the third scenario, decompress a partial decompressed size
(metadata promise strictly <= exact decompressed size) with a upper bound
compressed size, that is
also what EROFS scenario I raised from v1.8.3, and it supports fine and has been
merged into Linux kernel instead of my old customized code...
#566
(EROFS now also mainly supports exact full compressed size with partial
decompressed size for now due to in-place decompression but we need
to support old on-disk format anyway...)

Yeah, for the first two scenarios, if these needs more check, I think they need
a new API for these...

From the perspective of complexity, I'm curious if introducing two decode internal
functions in the upstream LZ4 library are better, the one is for common use (so that
is stable and don't need to modify or optimize the performance aggressively by each
individual lz4 version, forcing on stability and commonality but maintain competitive
performance since for some end-users (especially filesystems), the whole scenario
is also limited to I/O but not CPU only. And we don't really care much about its
performance so the logic can be simplified and widely used, but that is helpful for
most LZ4 users since it exists in the offical library but not in fragmented random
LZ4 branches), the other one is mainly for some main given extreme performance
benchmark uses so its logic can be then much simplified as well and cleaner.
Since all downstream projects (including linux kernel project) keep track of
LZ4 upstream from time to time, the performance isn't the top concern I think...

Thanks,
Gao Xiang

[Cyan4973]

there exists the third scenario, decompress a partial decompressed size (metadata promise strictly <= exact decompressed size) with a upper bound compressed size, that is also what EROFS scenario I raised

That's a good datapoint, @hsiangkao, I'll make sure this capability is delivered in some way within next release.

[Cyan4973]

This issue is likely fixed by #910 .
The fix will also require a bit more testing, just to be sure it doesn't introduce new issues of its own.

LZ4_decompress_safe_partial() is now compatible with a scenario
allowing a few bytes of padding at the end of input,
on the condition that the amount of data requested to be generated is <= block's decompressed size.

This capability used to exist in earlier versions of liblz4, though it was a fortuitous accident,
as the only scenario it was supposed to support was srcSize == block_compressed_size.
It was broken by a fix introduced in v1.9.2, after detecting that, in some (invalid) cases, the function could read beyond input buffer.
The vulnerability was fixed, but also required a much stronger control over srcSize.

While this patch kind of restore a capability that was present by accident,
it's still unclear to me if this is the best way to support it.
The name of the function, its parameters, and the differences in supported scenarios feel a bit strange.
I've updated the function documentation to address its scope and limitations,
but I keep wondering if it wouldn't be better to separate use cases more clearly and provide dedicated entry points for them.

[jfkthame]

Thanks so much for looking into this; I'm hoping to test it shortly to confirm that it solves the issues we were seeing.