starred/brotli
1
0
Fork 0
mirror of https://github.com/google/brotli.git synced 2026-07-08 17:56:58 +00:00
Code Issues 1.2k Packages Projects Releases 20 Wiki Activity

Non-compliant decoding according to section 4? #158

New Issue
Closed
opened 2026-01-29 20:38:58 +00:00 by claunia · 11 comments
claunia commented 2026-01-29 20:38:58 +00:00
Owner
Copy Link

Originally created by @dsnet on GitHub (Feb 6, 2017).

I was running fuzz testing on my Brotli implementation and noticed that the following input differs when decompressed by my version compared to the canonical one here.

The input causing issues (in hex): e2e184886a563080e0391603e430f9

When decompressed by the google/brotli C implementation:
worldwhitemediafirstirstirstirstirstirstirstirstirstirstirst...
When decompressed by my implementation:
worldorldorldorldorldorldorldorldorldorldorldorldorldorldorl...

According to section 4 of the RFC:

When a distance symbol 0 appears, the distance it represents (i.e.,
the last distance in the sequence of distances) is not pushed to the
ring buffer of last distances

However, this seems contrary to what C decoder currently does:

if (s->distance_code >= 0) {
	--s->dist_rb_idx;
	s->distance_code = s->dist_rb[s->dist_rb_idx & 3];
	goto postReadDistance;  /* We already have the implicit distance */
}

The logic in the C version seems contrary to the stated prose in the RFC, which makes no mention that an implicit zero reverse rotates the distance ring-buffer.

Originally created by @dsnet on GitHub (Feb 6, 2017). I was running fuzz testing on [my Brotli implementation](https://github.com/dsnet/compress/tree/master/brotli) and noticed that the following input differs when decompressed by my version compared to the canonical one here. The input causing issues (in hex): `e2e184886a563080e0391603e430f9` When decompressed by the `google/brotli` C implementation: `worldwhitemediafirstirstirstirstirstirstirstirstirstirstirst...` When decompressed by my implementation: `worldorldorldorldorldorldorldorldorldorldorldorldorldorldorl...` According to section 4 of the RFC: > When a distance symbol 0 appears, the distance it represents (i.e., the last distance in the sequence of distances) is not pushed to the ring buffer of last distances However, this seems contrary to [what C decoder currently does](https://github.com/google/brotli/blob/ccabf811ffcef087d9f10cf417b05271c2067a82/dec/decode.c#L1706-L1710): ```c if (s->distance_code >= 0) { --s->dist_rb_idx; s->distance_code = s->dist_rb[s->dist_rb_idx & 3]; goto postReadDistance; /* We already have the implicit distance */ } ``` The logic in the C version seems contrary to the stated prose in the RFC, which makes no mention that an implicit zero *reverse* rotates the distance ring-buffer.
claunia commented 2026-01-29 20:38:59 +00:00
Author
Owner
Copy Link

@eustas commented on GitHub (Feb 6, 2017):

This piece of code is very tricky; it allows continuation after break in decoding.
We use special value (-1) to specify that distance is not decoded yet.
If distance is decoded, we retake it from distance ring-buffer.
Please, take a look where s->dist_rb_idx is incremented and decremented. For distance == 0 it has one extra decrement, so after processing the command it remains unchanged.

@eustas commented on GitHub (Feb 6, 2017): This piece of code is very tricky; it allows continuation after break in decoding. We use special value (-1) to specify that distance is not decoded yet. If distance is decoded, we retake it from distance ring-buffer. Please, take a look where s->dist_rb_idx is incremented and decremented. For distance == 0 it has one extra decrement, so after processing the command it remains unchanged.
claunia commented 2026-01-29 20:38:59 +00:00
Author
Owner
Copy Link

@dsnet commented on GitHub (Feb 6, 2017):

I believe there is in a mismatch in the increments and decrements in the case where the implicit zero command is repeatedly used and the static dictionary case is hit. It seems that it will short-circuit the increment logic (which only occurs in the dynamic dictionary case), causing the handling of implicit zeros to accidentally decrement one too much each time.

I compiled with debugging and logging enabled and ran bro -d. The relevant snippet is:

...
[ProcessCommandsInternal] pos = 0 insert = 0 copy = 5
IMPLICIT_ZERO
[ProcessCommandsInternal] pos = 0 distance = 4
[ProcessCommandsInternal] dictionary word: [world]
[ProcessCommandsInternal] s->meta_block_remaining_len = 9995
[ProcessCommandsInternal] pos = 5 insert = 0 copy = 5
IMPLICIT_ZERO
[ProcessCommandsInternal] pos = 5 distance = 11
[ProcessCommandsInternal] dictionary word: [white]
[ProcessCommandsInternal] s->meta_block_remaining_len = 9990
[ProcessCommandsInternal] pos = 10 insert = 0 copy = 5
IMPLICIT_ZERO
[ProcessCommandsInternal] pos = 10 distance = 15
[ProcessCommandsInternal] dictionary word: [media]
[ProcessCommandsInternal] s->meta_block_remaining_len = 9985
[ProcessCommandsInternal] pos = 15 insert = 0 copy = 5
IMPLICIT_ZERO
[ProcessCommandsInternal] pos = 15 distance = 16
[ProcessCommandsInternal] dictionary word: [first]
[ProcessCommandsInternal] s->meta_block_remaining_len = 9980
[ProcessCommandsInternal] pos = 20 insert = 0 copy = 5
IMPLICIT_ZERO
[ProcessCommandsInternal] pos = 20 distance = 4
UPDATE_RING_BUFFER
[ProcessCommandsInternal] pos = 25 insert = 0 copy = 5
IMPLICIT_ZERO
[ProcessCommandsInternal] pos = 25 distance = 4
UPDATE_RING_BUFFER
[ProcessCommandsInternal] pos = 30 insert = 0 copy = 5
IMPLICIT_ZERO
...

The IMPLICIT_ZERO message was a printf added after L1706 of decode.c. In the log printout, you see that the distance is sweeping through the sequences [4, 11, 15, 16, 4, 4, 4, 4, 4, ...]. Notice it how it goes in reverse order through the initial distances in the ring buffer (i.e., 4, 11, 15, 16) even though only the zero code is used? After exhausting the ring buffer, it no longer performs static dictionary lookups, and starts doing dynamic dictionary lookups, causing it to properly stay at 4 for the rest of the time.

@dsnet commented on GitHub (Feb 6, 2017): I believe there is in a mismatch in the increments and decrements in the case where the implicit zero command is repeatedly used and the static dictionary case is hit. It seems that it will short-circuit the increment logic (which only occurs in the dynamic dictionary case), causing the handling of implicit zeros to accidentally decrement one too much each time. I compiled with debugging and logging enabled and ran `bro -d`. The relevant snippet is: ``` ... [ProcessCommandsInternal] pos = 0 insert = 0 copy = 5 IMPLICIT_ZERO [ProcessCommandsInternal] pos = 0 distance = 4 [ProcessCommandsInternal] dictionary word: [world] [ProcessCommandsInternal] s->meta_block_remaining_len = 9995 [ProcessCommandsInternal] pos = 5 insert = 0 copy = 5 IMPLICIT_ZERO [ProcessCommandsInternal] pos = 5 distance = 11 [ProcessCommandsInternal] dictionary word: [white] [ProcessCommandsInternal] s->meta_block_remaining_len = 9990 [ProcessCommandsInternal] pos = 10 insert = 0 copy = 5 IMPLICIT_ZERO [ProcessCommandsInternal] pos = 10 distance = 15 [ProcessCommandsInternal] dictionary word: [media] [ProcessCommandsInternal] s->meta_block_remaining_len = 9985 [ProcessCommandsInternal] pos = 15 insert = 0 copy = 5 IMPLICIT_ZERO [ProcessCommandsInternal] pos = 15 distance = 16 [ProcessCommandsInternal] dictionary word: [first] [ProcessCommandsInternal] s->meta_block_remaining_len = 9980 [ProcessCommandsInternal] pos = 20 insert = 0 copy = 5 IMPLICIT_ZERO [ProcessCommandsInternal] pos = 20 distance = 4 UPDATE_RING_BUFFER [ProcessCommandsInternal] pos = 25 insert = 0 copy = 5 IMPLICIT_ZERO [ProcessCommandsInternal] pos = 25 distance = 4 UPDATE_RING_BUFFER [ProcessCommandsInternal] pos = 30 insert = 0 copy = 5 IMPLICIT_ZERO ... ``` The `IMPLICIT_ZERO` message was a printf added after L1706 of decode.c. In the log printout, you see that the distance is sweeping through the sequences [4, 11, 15, 16, 4, 4, 4, 4, 4, ...]. Notice it how it goes in reverse order through the initial distances in the ring buffer (i.e., 4, 11, 15, 16) even though only the zero code is used? After exhausting the ring buffer, it no longer performs static dictionary lookups, and starts doing dynamic dictionary lookups, causing it to properly stay at 4 for the rest of the time.
claunia commented 2026-01-29 20:38:59 +00:00
Author
Owner
Copy Link

@eustas commented on GitHub (Feb 7, 2017):

Oh! I see. Thanks for the report. Going to fix that ASAP.

@eustas commented on GitHub (Feb 7, 2017): Oh! I see. Thanks for the report. Going to fix that ASAP.
claunia commented 2026-01-29 20:39:00 +00:00
Author
Owner
Copy Link

@eustas commented on GitHub (Feb 7, 2017):

Fixed. Again, thank you! This bug is a new "survival champion" - it was introduced about 1.5 years ago =O

@eustas commented on GitHub (Feb 7, 2017): Fixed. Again, thank you! This bug is a new "survival champion" - it was introduced about 1.5 years ago =O
claunia commented 2026-01-29 20:39:00 +00:00
Author
Owner
Copy Link

@ralfjunker commented on GitHub (Feb 7, 2017):

Testing 0749d9c does not give me the same decompressed output as @dsnet proposes in his initial report of this issue.

Decompressing hex e2e184886a563080e0391603e430f9 results in

worldsmallmallmallmallmallmallmallmallmallmallmallmallma... (10000 bytes in total)

instead of the expected

worldorldorldorldorldorldorldorldorldorldorldorldorldorldor... (no total given).

@dsnet's "wrong" output before 0749d9c matches mine, so I am inclined to believe that his fixed output is also correct, in which case the fix is wrong.

Could @dsnet or @eustas please shed some light? Thanks!

PS: Will there be a test case?

@ralfjunker commented on GitHub (Feb 7, 2017): Testing 0749d9c does not give me the same decompressed output as @dsnet proposes in his initial report of this issue. Decompressing hex `e2e184886a563080e0391603e430f9` results in `worldsmallmallmallmallmallmallmallmallmallmallmallmallma...` (10000 bytes in total) instead of the expected `worldorldorldorldorldorldorldorldorldorldorldorldorldorldor...` (no total given). @dsnet's "wrong" output before 0749d9c matches mine, so I am inclined to believe that his fixed output is also correct, in which case the fix is wrong. Could @dsnet or @eustas please shed some light? Thanks! PS: Will there be a test case?
claunia commented 2026-01-29 20:39:00 +00:00
Author
Owner
Copy Link

@dsnet commented on GitHub (Feb 7, 2017):

@ralfjunker, what implementation is yours?

Mine repeats "orld" until the 10000 byte limit is hit.

@dsnet commented on GitHub (Feb 7, 2017): @ralfjunker, what implementation is yours? Mine repeats "orld" until the 10000 byte limit is hit.
claunia commented 2026-01-29 20:39:01 +00:00
Author
Owner
Copy Link

@dsnet commented on GitHub (Feb 7, 2017):

My interpretation of what should happen (assuming all implementations agree about huffman decoding of commands):

There is a repeated sequence of commands of the form (length:5, dist: 0).

According to section 4, dist:0 should result in the last distance being used, which defaults to 4 (without updating the distance ring buffer; not that it matters).

Thus, this is really a repeated sequence of (length:5, dist:4) commands.

For the first command, there is no output, so it falls under the static dictionary case according to:

if distance is less than the max allowed distance plus one
	move backwards distance bytes in the uncompressed data,
	and copy CLEN bytes from this position to
	the uncompressed stream
else
	look up the static dictionary word, transform the word as
	directed, and copy the result to the uncompressed stream

This copies "world" to the output.

For all subsequent commands, there is sufficient data in the output such that a distance of 4 is always satisfied by the dynamic dictionary. Thus, copying "orldo" the first time, "rldor" the second time, "ldorl" the third time, etc.

@dsnet commented on GitHub (Feb 7, 2017): My interpretation of what should happen (assuming all implementations agree about huffman decoding of commands): There is a repeated sequence of commands of the form (length:5, dist: 0). According to section 4, dist:0 should result in the last distance being used, which defaults to 4 (without updating the distance ring buffer; not that it matters). Thus, this is really a repeated sequence of (length:5, dist:4) commands. For the first command, there is no output, so it falls under the static dictionary case according to: ``` if distance is less than the max allowed distance plus one move backwards distance bytes in the uncompressed data, and copy CLEN bytes from this position to the uncompressed stream else look up the static dictionary word, transform the word as directed, and copy the result to the uncompressed stream ``` This copies "world" to the output. For all subsequent commands, there is sufficient data in the output such that a distance of 4 is always satisfied by the dynamic dictionary. Thus, copying "orldo" the first time, "rldor" the second time, "ldorl" the third time, etc.
claunia commented 2026-01-29 20:39:01 +00:00
Author
Owner
Copy Link

@ralfjunker commented on GitHub (Feb 8, 2017):

I am using the C implementation from this repository, in particular this check-in: 0749d9ca8b.

It repeats mall until it reaches 10000 bytes.

Did you test @eustas' fix to this C implementation?

@ralfjunker commented on GitHub (Feb 8, 2017): I am using the C implementation from this repository, in particular this check-in: 0749d9ca8b8ec1. It repeats `mall` until it reaches 10000 bytes. Did you test @eustas' fix to this C implementation?
claunia commented 2026-01-29 20:39:02 +00:00
Author
Owner
Copy Link

@eustas commented on GitHub (Feb 8, 2017):

For testing the fix we have internally added 3 synthetic tests:

TEST(SynthTest, IntactDistanceRingBuffer0) {
  uint8_t compressed[] = {
    0x1b, 0x0a, 0x00, 0x00, 0x00, 0x00, 0x80, 0xe3, 0xb4, 0x0d, 0x00, 0x00,
    0x07, 0x5b, 0x26, 0x31, 0x40, 0x02, 0x00, 0xe0, 0x4e, 0x1b, 0xa1, 0x80,
    0x20, 0x00
  };
  Verify(
      R"(
      main_header
      metablock_header_easy: 11, 1
      command_inscopy_easy: 0, 7 // "himself" from dictionary
      bits: "000000" // distance = 4 from RB; RB remains intact
      command_inscopy_easy: 0, 4 // copy "self"
      bits: "000000" // distance = 4 from RB; RB remains intact
      )",
      compressed, sizeof(compressed),
      BROTLI_DECODER_SUCCESS,
      "himselfself");
}

TEST(SynthTest, IntactDistanceRingBuffer1) {
  uint8_t compressed[] = {
    0x1b, 0x09, 0x00, 0x00, 0x00, 0x00, 0x80, 0xe3, 0xb4, 0x0d, 0x00, 0x00,
    0x07, 0x5b, 0x26, 0x31, 0x40, 0x02, 0x00, 0xe0, 0x4e, 0x1b, 0x21, 0xa0,
    0x20, 0x00
  };
  Verify(
      R"(
      main_header
      metablock_header_easy: 10, 1
      command_inscopy_easy: 0, 6 // "scroll" from dictionary
      bits: "100000" // distance = 11 from RB; RB remains intact
      command_inscopy_easy: 0, 4 // copy "roll"
      bits: "000000" // distance = 4 from RB; RB remains intact
      )",
      compressed, sizeof(compressed),
      BROTLI_DECODER_SUCCESS,
      "scrollroll");
}

TEST(SynthTest, IntactDistanceRingBuffer2) {
  uint8_t compressed[] = {
    0x1b, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x80, 0xe3, 0xb4, 0x0d, 0x00, 0x00,
    0x07, 0x5b, 0x26, 0x31, 0x40, 0x02, 0x00, 0xe0, 0x4e, 0x1b, 0x41, 0x80,
    0x20, 0x50, 0x10, 0x24, 0x08, 0x06
  };
  Verify(
      R"(
      main_header
      metablock_header_easy: 16, 1
      command_inscopy_easy: 0, 4 // "left" from dictionary (index = 3 = 4 - 1)
      bits: "000000" // distance = 4 from RB; RB remains intact
      command_inscopy_easy: 0, 4 // "data" from dictionary (index = 6 = 11 - 5)
      bits: "100000" // distance = 11 from RB; RB remains intact
      command_inscopy_easy: 0, 4 // "data" from dictionary (index = 6 = 15 - 9)
      bits: "010000" // distance = 15 from RB; RB remains intact
      command_inscopy_easy: 0, 4 // "left" from dictionary (index = 3 = 16 - 13)
      bits: "110000" // distance = 16 from RB; RB remains intact
      )",
      compressed, sizeof(compressed),
      BROTLI_DECODER_SUCCESS,
      "leftdatadataleft");
}

The first parameter of Verify is DSL code snippet used to generate compressed.
The last parameter is an expected output string.

@eustas commented on GitHub (Feb 8, 2017): For testing the fix we have internally added 3 synthetic tests: ```c++ TEST(SynthTest, IntactDistanceRingBuffer0) { uint8_t compressed[] = { 0x1b, 0x0a, 0x00, 0x00, 0x00, 0x00, 0x80, 0xe3, 0xb4, 0x0d, 0x00, 0x00, 0x07, 0x5b, 0x26, 0x31, 0x40, 0x02, 0x00, 0xe0, 0x4e, 0x1b, 0xa1, 0x80, 0x20, 0x00 }; Verify( R"( main_header metablock_header_easy: 11, 1 command_inscopy_easy: 0, 7 // "himself" from dictionary bits: "000000" // distance = 4 from RB; RB remains intact command_inscopy_easy: 0, 4 // copy "self" bits: "000000" // distance = 4 from RB; RB remains intact )", compressed, sizeof(compressed), BROTLI_DECODER_SUCCESS, "himselfself"); } TEST(SynthTest, IntactDistanceRingBuffer1) { uint8_t compressed[] = { 0x1b, 0x09, 0x00, 0x00, 0x00, 0x00, 0x80, 0xe3, 0xb4, 0x0d, 0x00, 0x00, 0x07, 0x5b, 0x26, 0x31, 0x40, 0x02, 0x00, 0xe0, 0x4e, 0x1b, 0x21, 0xa0, 0x20, 0x00 }; Verify( R"( main_header metablock_header_easy: 10, 1 command_inscopy_easy: 0, 6 // "scroll" from dictionary bits: "100000" // distance = 11 from RB; RB remains intact command_inscopy_easy: 0, 4 // copy "roll" bits: "000000" // distance = 4 from RB; RB remains intact )", compressed, sizeof(compressed), BROTLI_DECODER_SUCCESS, "scrollroll"); } TEST(SynthTest, IntactDistanceRingBuffer2) { uint8_t compressed[] = { 0x1b, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x80, 0xe3, 0xb4, 0x0d, 0x00, 0x00, 0x07, 0x5b, 0x26, 0x31, 0x40, 0x02, 0x00, 0xe0, 0x4e, 0x1b, 0x41, 0x80, 0x20, 0x50, 0x10, 0x24, 0x08, 0x06 }; Verify( R"( main_header metablock_header_easy: 16, 1 command_inscopy_easy: 0, 4 // "left" from dictionary (index = 3 = 4 - 1) bits: "000000" // distance = 4 from RB; RB remains intact command_inscopy_easy: 0, 4 // "data" from dictionary (index = 6 = 11 - 5) bits: "100000" // distance = 11 from RB; RB remains intact command_inscopy_easy: 0, 4 // "data" from dictionary (index = 6 = 15 - 9) bits: "010000" // distance = 15 from RB; RB remains intact command_inscopy_easy: 0, 4 // "left" from dictionary (index = 3 = 16 - 13) bits: "110000" // distance = 16 from RB; RB remains intact )", compressed, sizeof(compressed), BROTLI_DECODER_SUCCESS, "leftdatadataleft"); } ``` The first parameter of `Verify` is DSL code snippet used to generate `compressed`. The last parameter is an expected output string.
claunia commented 2026-01-29 20:39:02 +00:00
Author
Owner
Copy Link

@eustas commented on GitHub (Feb 8, 2017):

Ooops, missed the case when distance code is baked into command.

@eustas commented on GitHub (Feb 8, 2017): Ooops, missed the case when distance code is baked into command.
claunia commented 2026-01-29 20:39:03 +00:00
Author
Owner
Copy Link

@eustas commented on GitHub (Feb 8, 2017):

I hope, now it is finally fixed with #506 =)

@eustas commented on GitHub (Feb 8, 2017): I hope, now it is finally fixed with #506 =)
Sign in to join this conversation.
No Branch/Tag Specified
Branches Tags
Labels
Clear labels
bug
enhancement
feature
help wanted
pull-request
Mirrored from GitHub Pull Request
 release-v1.1
release-v1.1.1
release-v1.2
No Label
Milestone
No items
No Milestone
Projects
Clear projects
No project
Assignees
Clear assignees
claunia
No Assignees
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: starred/brotli#158
Delete Branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?