Java decoder: large-window top distance codes wrap to negative in calculateDistanceLut and decode as ringbuffer garbage (C reference rejects them)

BODY

Reading java/org/brotli/dec against c/dec/decode.c at commit 4508218e turned up a conformance divergence on the large-window distance alphabet: the Java decoder accepts and mis-decodes distance code points that the C reference rejects. Correctness only — see the scope note below; there is no memory-safety angle here.

What happens

Decode.calculateDistanceLut (java/org/brotli/dec/Decode.java:881-912) fills the per-metablock distance tables in signed int arithmetic:

distExtraBits[i] = (byte) bits;
distOffset[i]    = ndirect + ((((2 + half) << bits) - 4) << npostfix) + 1 + j;

For large-window streams (application opt-in via enableLargeWindow, window up to 30 bits), the distance alphabet limit reaches calculateDistanceAlphabetLimit(s, MAX_ALLOWED_DISTANCE, npostfix, ndirect) (Decode.java:183-191), and the top-of-alphabet groups compute base values above 2^31 - 1. Java int wraps where the C brotli_reg_t (unsigned) does not:

• npostfix=0, ndirect=15 — limit 90; the top entry takes bits=30, half=0, so the base is 15 + ((2 << 30) - 4) + 1; 2 << 30 is Integer.MIN_VALUE, giving distOffset[89] at roughly -2147483636.
• npostfix=1, ndirect=30 — limit 158; top base 30 + ((3 << 28) - 4) * 2 + 1 = 1610612759; distance = base + (extraBits << 1) then overflows int for the top ~23 values (intended distances 2147483648..2147483670).
• npostfix=3, ndirect=120 — limit 536; top base 1610612825; same wrap band.

The value is consumed on the extraBits path (Decode.java:1413-1423, assignment at :1422):

s.distance = s.distOffset[distanceCode] + (bits << s.distancePostfixBits);

That path has no negative-distance check; the short-code path has one a few lines earlier (Decode.java:1410-1412). A wrapped-negative s.distance then fails both guards simply by being negative:

• if (s.distance > s.maxDistance) (Decode.java:1433) — never true for a negative left side;
• if (s.distance > MAX_ALLOWED_DISTANCE) inside doUseDictionary (Decode.java:1119) — unreachable for the same reason.

The copy loop then computes its source as (s.pos - s.distance) & ringBufferMask (Decode.java:1451): the huge negative distance wraps through int overflow onto an in-bounds offset in the stream's own ringbuffer, the decoder emits those bytes, and the decode completes successfully.

What the C reference does

CalculateDistanceLut (c/dec/decode.c:1835-1866) computes the same base in brotli_reg_t, an unsigned register type — no wrap on any build. ReadDistanceInternal (c/dec/decode.c:1868-1905) keeps the distance unsigned; it exceeds max_distance, takes the dictionary check, exceeds MAX_ALLOWED_DISTANCE, and the decoder returns BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DISTANCE). Every affected code point is rejected.

All affected code points represent backward distances greater than MAX_ALLOWED_DISTANCE (0x7FFFFFFC), i.e. invalid per RFC 7932 — only malicious or pathological streams contain them. The reference contract is reject; the port's behavior is accept-and-mis-decode.

Scope note (why this is filed as correctness, not security)

The observable effect is an invalid stream decoding to garbage instead of erroring. The copy source is mask-bounded inside the same stream's ringbuffer (JVM bounds-checked besides); the ringbuffer is per decoder instance, so nothing from other streams or surrounding memory can surface; never-written ringbuffer regions read as zeros (a fresh byte[] is zero-initialized); output sizes are unchanged, so there is no amplification; and large-window decoding requires the non-default enableLargeWindow opt-in — the Content-Encoding: br path never enables it. Filing it as a correctness/conformance gap against the reference decoder, not as a vulnerability.

Reproduction

The divergence was found by source reading; the test below is written but not yet executed (no JDK at hand for the review), so STREAM is a placeholder — the comment inside the test is a deterministic bit-level recipe that produces the bytes (SynthTest's hand-packed style, or a small bit-writer following it verbatim). The C side of the differential is directly checkable by feeding the same bytes to any large-window-enabled C build.

import java.io.ByteArrayInputStream;
import java.io.IOException;
import org.brotli.dec.BrotliInputStream;
import org.junit.Test;

import static org.junit.Assert.fail;

/**
 * Differential PoC: large-window top-of-alphabet distance code (invalid per
 * RFC 7932, distance > MAX_ALLOWED_DISTANCE) is REJECTED by the reference C
 * decoder but DECODED to ringbuffer-derived bytes by the Java port, because
 * calculateDistanceLut's base overflows signed int and the negative result
 * slips past both `distance > maxDistance` guards (Decode.java:881-912,
 * 1413-1423, 1119 at pin 4508218e).
 *
 * Build: needs the google/brotli java decoder classes + JUnit4 on the
 * classpath. Run as a plain JUnit test.
 */
public class NegativeDistancePoC {

  /**
   * Bit-level stream recipe (LSB-first per bit position, brotli order):
   *
   *  WBITS (large window): 1 | 000 | 001 | 0 | 011110
   *    = flag(1), n==0, n2==1 -> large window (requires enableLargeWindow),
   *      reserved(0), lgwin=30.
   *  Metablock 1 (ISLAST=0): MNIBBLES code 0 (4 nibbles), MLEN-1 = 7
   *    (say), ISUNCOMPRESSED=0.
   *  NBLTYPESL=1 (2-bit varlen 0), NBLTYPESC=1, NBLTYPESD=1 -> all three
   *    partitions skip their trees (block lengths 1<<28).
   *  NPOSTFIX(2 bits)=0, NDIRECT(4 bits)=15  -> distance alphabet limit 90
   *    (calculateDistanceAlphabetLimit(MAX_ALLOWED_DISTANCE, 0, 15)).
   *  Context mode for literal block 0: 2 bits = 0. NTREESL=1, NTREESD=1
   *    (each: 1 bit 0 -> varlen 0 -> single tree, no RLE bit, no IMTF bit).
   *  Literal tree: simple, 1 symbol 'a' (2 bits numSymbols-1=00, 8 bits 'a').
   *  Command tree: simple, 1 symbol = a command with distanceCode >= 0
   *    (e.g. cmdCode 128: insert 0..0 extras, copy offset with dist context 0)
   *    so the distance tree is consulted.
   *  Distance tree: simple, 1 symbol = 89 (2 bits 00, 8 bits 89) -> every
   *    distance read yields code 89.
   *  Body: one command consuming insertLength 0 / copyLength 4; distance read:
   *    code 89 -> extraBits = distExtraBits[89] = 30 -> read 30 bits (any,
   *    e.g. all 0) -> s.distance = distOffset[89] + 0, distOffset[89] is
   *    negative from the (2<<30) int overflow.
   *  Close: ISLAST=1, ISLASTEMPTY=1, pad to byte boundary with zeros.
   *
   * Materialize the byte array with the SynthTest idiom (see
   * SetDictionaryTest.ONE_COMMAND for the hand-packed style), or emit it with
   * a small bit-writer script following the layout above verbatim.
   */
  private static final byte[] STREAM = {
      // Replace with the materialized bytes per the recipe above.
      // (Static-analysis lane: host has no JDK; bytes are not generated here.)
      (byte) 0x00
  };

  @Test
  public void topDistanceCodeIsNotRejected() throws Exception {
    BrotliInputStream in = new BrotliInputStream(new ByteArrayInputStream(STREAM));
    in.enableLargeWindow();  // application opt-in required for large-window
    byte[] out = new byte[4096];
    try {
      int total = 0;
      int n;
      while ((n = in.read(out)) >= 0) {
        total += n;
      }
      // At pin: reaches here — decoder succeeded on an invalid stream,
      // output copied from (pos + ~2^31) & ringBufferMask (own ringbuffer).
      // Reference C: BROTLI_DECODER_ERROR_FORMAT_DISTANCE (reject).
      System.out.println("decoded " + total + " bytes: NOT rejected (bug)");
    } catch (IOException expectedAfterUpstreamFix) {
      // Fixed behavior: INVALID_BACKWARD_REFERENCE wrapped as IOException.
      System.out.println("rejected: fixed behavior");
    } finally {
      in.close();
    }
    fail("replace STREAM with materialized bytes before running");
  }
}

Suggested fix

Two directions; either closes the divergence.

1. Parity with the short-code path: extend the existing negative-distance check at Decode.java:1410-1412 to the extraBits path — reject s.distance < 0 as an invalid backward reference (INVALID_BACKWARD_REFERENCE, surfacing as IOException from BrotliInputStream).
2. Mirror the C unsigned semantics: compute the LUT base (or at minimum the final s.distance) in long. The unwrapped intended value then trips the existing s.distance > maxDistance guard at Decode.java:1433 on its own.

A regression test in the SynthTest idiom with the materialized stream pins either fix.

A systemic note: the Java port has no fuzzing

OSS-Fuzz coverage for brotli is the C/C++ project (the in-repo decode_fuzzer); java/BUILD.bazel carries no fuzz targets, and the in-repo Java tests are hand-built synthetic streams (SynthTest and friends). Both this divergence and the metadata ISUNCOMPRESSED one referenced below are C-vs-Java conformance gaps that source reading found — exactly the class a Jazzer harness over BrotliInputStream (with enableLargeWindow enabled) catches mechanically: differential against the C decoder, or at minimum asserting that streams the reference rejects are rejected by the port too.

Related

• #1518 — C-vs-Java conformance divergence (ISUNCOMPRESSED read after a metadata meta-block); patches the Java file.
• #1536 — compound-dictionary range checks across the language ports.

Happy to send a PR for either fix direction together with the regression test.