lz4_flex: Decompression can leak information from uninitialized memory or reused output buffer

@@ -60,3 +60,9 @@ name = "fuzz_decomp_corrupt_frame"
 path = "fuzz_targets/fuzz_decomp_corrupt_frame.rs"
 test = false
 doc = false
+
+[[bin]]
+name = "fuzz_decomp_no_output_leak"
+path = "fuzz_targets/fuzz_decomp_no_output_leak.rs"
+test = false
+doc = false

@@ -1,16 +1,40 @@
 #![no_main]
 use libfuzzer_sys::fuzz_target;
-use std::convert::TryInto;
 
-use lz4_flex::block::{decompress_size_prepended, decompress_size_prepended_with_dict};
-fuzz_target!(|data: &[u8]| {
-    if data.len() >= 4 {
-        let size = u32::from_le_bytes(data[0..4].try_into().unwrap());
-        if size > 20_000_000 {
-            return;
+use lz4_flex::block::{decompress, decompress_with_dict};
+
+// dict content does not matter
+static DICT: [u8; 1024] = [0_u8; 1024];
+
+#[derive(Debug, arbitrary::Arbitrary)]
+struct FuzzData {
+    input: Vec<u8>,
+    #[arbitrary(with = |u: &mut arbitrary::Unstructured| u.int_in_range(0..=DICT.len()))]
+    dict_size: usize,
+    #[arbitrary(with = |u: &mut arbitrary::Unstructured| u.int_in_range(0..=65535))]
+    output_size: usize,
+}
+
+fuzz_target!(|fuzz_data: FuzzData| {
+    let input = fuzz_data.input;
+    let dict = &DICT[..fuzz_data.dict_size];
+    let output_size = fuzz_data.output_size;
+
+    // use decompress functions which for the unsafe feature use an uninitialized Vec,
+    // making this fuzz test interesting for MemorySanitizer
+    let result = if dict.is_empty() {
+        decompress(&input, output_size)
+    } else {
+        decompress_with_dict(&input, output_size, &dict)
+    };
+    // mainly verify that no panic had occurred, but ignore whether result was Ok or Err
+    if let Ok(decomp) = result {
+        // to detect invalid memory access have to consume each byte, otherwise if the decompression
+        // function copies uninitialized memory in place, MemorySanitizer does not seem to report it;
+        // and even that only works when fuzzing is run with `--dev`, otherwise the access here seems
+        // to be optimized away, see also https://github.com/rust-fuzz/cargo-fuzz/issues/436
+        for byte in decomp {
+            std::hint::black_box(byte);
         }
     }
-    // should not panic
-    let _ = decompress_size_prepended(&data);
-    let _ = decompress_size_prepended_with_dict(&data, &data);
 });

@@ -0,0 +1,44 @@
+#![no_main]
+use libfuzzer_sys::fuzz_target;
+
+use lz4_flex::block::{decompress_into, decompress_into_with_dict, DecompressError};
+
+// dict content does not matter
+static DICT: [u8; 1024] = [0_u8; 1024];
+
+#[derive(Debug, arbitrary::Arbitrary)]
+struct FuzzData {
+    input: Vec<u8>,
+    #[arbitrary(with = |u: &mut arbitrary::Unstructured| u.int_in_range(0..=DICT.len()))]
+    dict_size: usize,
+}
+
+fuzz_target!(|fuzz_data: FuzzData| {
+    let input = fuzz_data.input;
+    let dict = &DICT[..fuzz_data.dict_size];
+    // create an output buffer which is presumably large enough for the decompressed result
+    let mut output = vec![0u8; 512.max(input.len() * 4)];
+
+    fn decompress(input: &[u8], output: &mut [u8], dict: &[u8]) -> Result<usize, DecompressError> {
+        if dict.is_empty() {
+            decompress_into(input, output)
+        } else {
+            decompress_into_with_dict(input, output, dict)
+        }
+    }
+
+    let decompressed1;
+    if let Ok(decompressed_len) = decompress(&input, &mut output, &dict) {
+        decompressed1 = output[..decompressed_len].to_owned();
+    } else {
+        // Skip if decompression failed
+        return;
+    }
+
+    // Pre-fill output buffer with arbitrary data and repeat decompression; should not have any effect on decompression result
+    output.fill(255);
+    let decompressed_len = decompress(&input, &mut output, &dict).unwrap();
+    let decompressed2 = &output[..decompressed_len];
+
+    assert_eq!(decompressed1, decompressed2);
+});

@@ -16,6 +16,8 @@ jobs:
       uses: dtolnay/rust-toolchain@master
       with:
         toolchain: nightly
+        # 'rust-src' component is needed for fuzzing with `--sanitizer=memory`
+        components: rust-src
     - uses: actions/checkout@v3
     - name: Ensure no_std compiles
       run: cargo build --no-default-features
@@ -47,6 +49,15 @@ jobs:
       run: for fuzz_test in `cargo fuzz list`; do cargo +nightly fuzz run $fuzz_test -- -max_total_time=30 || exit 1; done
     - name: Run fuzz tests (unsafe)
       run: for fuzz_test in `cargo fuzz list`; do cargo +nightly fuzz run $fuzz_test --no-default-features -- -max_total_time=30 || exit 1; done
+    - name: Run decompress fuzz test (unsafe; memory sanitizer)
+      # Only run this single test because this fuzz target is where invalid memory access might occur
+      # (uses decompress functions which create uninitialized `Vec`); running all fuzz tests with MemorySanitizer
+      # might make them less effective due to the slowdown from the sanitizer
+      # Have to run with `--dev` because otherwise memory access might be optimized away
+      # Note that the stack traces reported by MemorySanitizer here are not readable;
+      # that would require llvm-symbolizer, see https://clang.llvm.org/docs/MemorySanitizer.html#report-symbolization
+      # But setting up llvm-symbolizer here might not be worth it; can do that locally when reproducing the issue
+      run: cargo +nightly fuzz run fuzz_decomp_corrupt_block --no-default-features --sanitizer=memory --dev -- -max_total_time=30
 
   semver:
     name: semver

@@ -107,13 +107,16 @@ Tested on AMD Ryzen 7 5900HX, rustc 1.69.0 (84c898d65 2023-04-16), Manjaro, CPU
 `MIRIFLAGS="-Zmiri-disable-isolation -Zmiri-disable-stacked-borrows" cargo +nightly miri test --no-default-features --features frame`
 
 ## Fuzzer
-This fuzz target generates corrupted data for the decompressor. 
+This fuzz target generates corrupted data for the decompressor:\
 `cargo +nightly fuzz run fuzz_decomp_corrupt_block` and `cargo +nightly fuzz run fuzz_decomp_corrupt_frame`
 
-This fuzz target asserts that a compression and decompression roundtrip returns the original input.
+This fuzz target asserts that the decompressor does not leak previous data when reusing an output buffer:\
+`cargo +nightly fuzz run fuzz_decomp_no_output_leak`
+
+This fuzz target asserts that a compression and decompression roundtrip returns the original input:\
 `cargo +nightly fuzz run fuzz_roundtrip` and `cargo +nightly fuzz run fuzz_roundtrip_frame`
 
-This fuzz target asserts compression with cpp and decompression with lz4_flex returns the original input.
+This fuzz target asserts compression with cpp and decompression with lz4_flex returns the original input:\
 `cargo +nightly fuzz run fuzz_roundtrip_cpp_compress`
 
 ## Bindings in other languages

@@ -59,11 +59,6 @@ unsafe fn duplicate_overlapping(
     mut start: *const u8,
     match_length: usize,
 ) {
-    // There is an edge case when output_ptr == start, which causes the decoder to potentially
-    // expose up to match_length bytes of uninitialized data in the decompression buffer.
-    // To prevent that we write a dummy zero to output, which will zero out output in such cases.
-    // This is the same strategy used by the reference C implementation https://github.com/lz4/lz4/pull/772
-    output_ptr.write(0u8);
     let dst_ptr_end = output_ptr.add(match_length);
 
     while output_ptr.add(1) < dst_ptr_end {
@@ -161,16 +156,21 @@ pub(super) fn read_integer_ptr(
     Ok(n)
 }
 
-/// Read a little-endian 16-bit integer from the input stream.
+/// Read the match offset as a little-endian 16-bit integer from the input stream.
 #[inline]
-fn read_u16_ptr(input_ptr: &mut *const u8) -> u16 {
+fn read_match_offset(input_ptr: &mut *const u8) -> Result<u16, DecompressError> {
     let mut num: u16 = 0;
     unsafe {
         core::ptr::copy_nonoverlapping(*input_ptr, &mut num as *mut u16 as *mut u8, 2);
         *input_ptr = input_ptr.add(2);
     }
 
-    u16::from_le(num)
+    let offset = u16::from_le(num);
+    if offset == 0 {
+        Err(DecompressError::OffsetZero)
+    } else {
+        Ok(offset)
+    }
 }
 
 const FIT_TOKEN_MASK_LITERAL: u8 = 0b00001111;
@@ -281,10 +281,12 @@ pub(crate) fn decompress_internal<const USE_DICT: bool, S: Sink>(
 
             // input_ptr <= input_ptr_safe should guarantee we have enough space in input
             debug_assert!(input_ptr_end as usize - input_ptr as usize >= 2);
-            let offset = read_u16_ptr(&mut input_ptr) as usize;
+            let offset = read_match_offset(&mut input_ptr)? as usize;
 
             let output_len = unsafe { output_ptr.offset_from(output_base) as usize };
-            let offset = offset.min(output_len + ext_dict.len());
+            if offset > output_len + ext_dict.len() {
+                return Err(DecompressError::OffsetOutOfBounds);
+            }
 
             // Check if part of the match is in the external dict
             if USE_DICT && offset > output_len {
@@ -372,7 +374,7 @@ pub(crate) fn decompress_internal<const USE_DICT: bool, S: Sink>(
                 return Err(DecompressError::ExpectedAnotherByte);
             }
         }
-        let offset = read_u16_ptr(&mut input_ptr) as usize;
+        let offset = read_match_offset(&mut input_ptr)? as usize;
         // Obtain the initial match length. The match length is the length of the duplicate segment
         // which will later be copied from data previously decompressed into the output buffer. The
         // initial length is derived from the second part of the token (the lower nibble), we read
@@ -534,10 +536,88 @@ mod test {
         assert_eq!(decompress(&[0x30, b'a', b'4', b'9'], 3).unwrap(), b"a49");
     }
 
-    // this error test is only valid with checked-decode.
+    #[test]
+    fn incomplete_input() {
+        assert!(matches!(
+            decompress(&[], 255),
+            Err(DecompressError::ExpectedAnotherByte)
+        ));
+        assert!(matches!(
+            // incomplete literal len
+            decompress(&[0xF0], 255),
+            Err(DecompressError::ExpectedAnotherByte)
+        ));
+        assert!(matches!(
+            // incomplete match offset
+            decompress(&[0x0F, 0], 255),
+            Err(DecompressError::ExpectedAnotherByte)
+        ));
+        assert!(matches!(
+            // incomplete match len
+            decompress(&[0x0F, 1, 0], 255),
+            Err(DecompressError::ExpectedAnotherByte)
+        ));
+    }
+
+    // this error test is only valid in safe-decode.
     #[test]
     fn offset_oob() {
-        decompress(&[0x10, b'a', 2, 0], 4).unwrap_err();
-        decompress(&[0x40, b'a', 1, 0], 4).unwrap_err();
+        // incomplete literal
+        assert!(matches!(
+            decompress(&[0x40, b'a', 1, 0], 4),
+            Err(DecompressError::LiteralOutOfBounds)
+        ));
+        // literal too large for output
+        assert!(matches!(
+            decompress(&[0x20, b'a', b'a', 1, 0], 1),
+            Err(DecompressError::OutputTooSmall {
+                expected: 2,
+                actual: 1
+            })
+        ));
+        // match too large for output
+        assert!(matches!(
+            decompress(&[0x10, b'a', 1, 0], 4),
+            Err(DecompressError::OutputTooSmall {
+                expected: 5,
+                actual: 4
+            })
+        ));
+
+        // out-of-bounds hot-loop
+        assert!(matches!(
+            decompress(
+                &[0x0E, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+                256
+            ),
+            Err(DecompressError::OffsetOutOfBounds)
+        ));
+        // out-of-bounds for dict
+        assert!(matches!(
+            decompress_with_dict(
+                &[0x0E, 255, 0, 0x70, 0, 0, 0, 0, 0, 0, 0],
+                256,
+                &[0_u8; 250]
+            ),
+            Err(DecompressError::OffsetOutOfBounds)
+        ));
+        // out-of-bounds non-hot-loop overlapping
+        assert!(matches!(
+            decompress(&[0x0F, 1, 0, 1, 0x70, 0, 0, 0, 0, 0, 0, 0], 256),
+            Err(DecompressError::OffsetOutOfBounds)
+        ));
+        // out-of-bounds non-hot-loop non-overlapping
+        assert!(matches!(
+            decompress(&[0x40, 0, 0, 0, 0, 255, 0, 0x70, 0, 0, 0, 0, 0, 0, 0], 256),
+            Err(DecompressError::OffsetOutOfBounds)
+        ));
+    }
+
+    #[test]
+    fn offset_0() {
+        assert!(matches!(
+            decompress(&[0x0E, 0, 0, 0x70, 0, 0, 0, 0, 0, 0, 0], 256),
+            Err(DecompressError::OffsetZero)
+        ));
     }
 }

@@ -50,14 +50,19 @@ pub(super) fn read_integer(input: &[u8], input_pos: &mut usize) -> Result<usize,
     Ok(n)
 }
 
-/// Read a little-endian 16-bit integer from the input stream.
+/// Read the match offset as a little-endian 16-bit integer from the input stream.
 #[inline]
-fn read_u16(input: &[u8], input_pos: &mut usize) -> Result<u16, DecompressError> {
+fn read_match_offset(input: &[u8], input_pos: &mut usize) -> Result<u16, DecompressError> {
     let dst = input
         .get(*input_pos..*input_pos + 2)
         .ok_or(DecompressError::ExpectedAnotherByte)?;
     *input_pos += 2;
-    Ok(u16::from_le_bytes(dst.try_into().unwrap()))
+    let offset = u16::from_le_bytes(dst.try_into().unwrap());
+    if offset == 0 {
+        Err(DecompressError::OffsetZero)
+    } else {
+        Ok(offset)
+    }
 }
 
 const FIT_TOKEN_MASK_LITERAL: u8 = 0b00001111;
@@ -84,7 +89,7 @@ fn does_token_fit(token: u8) -> bool {
 /// Decompress all bytes of `input` into `output`.
 ///
 /// Returns the number of bytes written (decompressed) into `output`.
-#[inline(always)] // (always) necessary to get the best performance in non LTO builds
+#[inline]
 pub(crate) fn decompress_internal<const USE_DICT: bool, S: Sink>(
     input: &[u8],
     output: &mut S,
@@ -139,7 +144,7 @@ pub(crate) fn decompress_internal<const USE_DICT: bool, S: Sink>(
             input_pos += literal_length;
 
             // clone as we don't want to mutate
-            let offset = read_u16(input, &mut literal_length.clone())? as usize;
+            let offset = read_match_offset(input, &mut literal_length.clone())? as usize;
             input_pos += 2;
 
             let mut match_length = MINMATCH + (token & 0xF) as usize;
@@ -157,7 +162,10 @@ pub(crate) fn decompress_internal<const USE_DICT: bool, S: Sink>(
             // In this branch we know that match_length is at most 18 (14 + MINMATCH).
             // But the blocks can overlap, so make sure they are at least 18 bytes apart
             // to enable an optimized copy of 18 bytes.
-            let start = output.pos().saturating_sub(offset);
+            let (start, did_overflow) = output.pos().overflowing_sub(offset);
+            if did_overflow {
+                return Err(DecompressError::OffsetOutOfBounds);
+            }
             if offset >= match_length {
                 output.extend_from_within(start, 18, match_length);
             } else {
@@ -199,7 +207,7 @@ pub(crate) fn decompress_internal<const USE_DICT: bool, S: Sink>(
             break;
         }
 
-        let offset = read_u16(input, &mut input_pos)? as usize;
+        let offset = read_match_offset(input, &mut input_pos)? as usize;
         // Obtain the initial match length. The match length is the length of the duplicate segment
         // which will later be copied from data previously decompressed into the output buffer. The
         // initial length is derived from the second part of the token (the lower nibble), we read
@@ -390,11 +398,88 @@ mod test {
         assert_eq!(decompress(&[0x30, b'a', b'4', b'9'], 3).unwrap(), b"a49");
     }
 
+    #[test]
+    fn incomplete_input() {
+        assert!(matches!(
+            decompress(&[], 255),
+            Err(DecompressError::ExpectedAnotherByte)
+        ));
+        assert!(matches!(
+            // incomplete literal len
+            decompress(&[0xF0], 255),
+            Err(DecompressError::ExpectedAnotherByte)
+        ));
+        assert!(matches!(
+            // incomplete match offset
+            decompress(&[0x0F, 0], 255),
+            Err(DecompressError::ExpectedAnotherByte)
+        ));
+        assert!(matches!(
+            // incomplete match len
+            decompress(&[0x0F, 1, 0], 255),
+            Err(DecompressError::ExpectedAnotherByte)
+        ));
+    }
+
     // this error test is only valid in safe-decode.
-    #[cfg(feature = "safe-decode")]
     #[test]
     fn offset_oob() {
-        decompress(&[0x10, b'a', 2, 0], 4).unwrap_err();
-        decompress(&[0x40, b'a', 1, 0], 4).unwrap_err();
+        // incomplete literal
+        assert!(matches!(
+            decompress(&[0x40, b'a', 1, 0], 4),
+            Err(DecompressError::LiteralOutOfBounds)
+        ));
+        // literal too large for output
+        assert!(matches!(
+            decompress(&[0x20, b'a', b'a', 1, 0], 1),
+            Err(DecompressError::OutputTooSmall {
+                expected: 2,
+                actual: 1
+            })
+        ));
+        // match too large for output
+        assert!(matches!(
+            decompress(&[0x10, b'a', 1, 0], 4),
+            Err(DecompressError::OutputTooSmall {
+                expected: 5,
+                actual: 4
+            })
+        ));
+
+        // out-of-bounds hot-loop
+        assert!(matches!(
+            decompress(
+                &[0x0E, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+                256
+            ),
+            Err(DecompressError::OffsetOutOfBounds)
+        ));
+        // out-of-bounds for dict
+        assert!(matches!(
+            decompress_with_dict(
+                &[0x0E, 255, 0, 0x70, 0, 0, 0, 0, 0, 0, 0],
+                256,
+                &[0_u8; 250]
+            ),
+            Err(DecompressError::OffsetOutOfBounds)
+        ));
+        // out-of-bounds non-hot-loop overlapping
+        assert!(matches!(
+            decompress(&[0x0F, 1, 0, 1, 0x70, 0, 0, 0, 0, 0, 0, 0], 256),
+            Err(DecompressError::OffsetOutOfBounds)
+        ));
+        // out-of-bounds non-hot-loop non-overlapping
+        assert!(matches!(
+            decompress(&[0x40, 0, 0, 0, 0, 255, 0, 0x70, 0, 0, 0, 0, 0, 0, 0], 256),
+            Err(DecompressError::OffsetOutOfBounds)
+        ));
+    }
+
+    #[test]
+    fn offset_0() {
+        assert!(matches!(
+            decompress(&[0x0E, 0, 0, 0x70, 0, 0, 0, 0, 0, 0, 0], 256),
+            Err(DecompressError::OffsetZero)
+        ));
     }
 }

@@ -91,6 +91,8 @@ pub enum DecompressError {
     LiteralOutOfBounds,
     /// Expected another byte, but none found.
     ExpectedAnotherByte,
+    /// Match offset is 0
+    OffsetZero,
     /// Deduplication offset out of bounds (not in buffer).
     OffsetOutOfBounds,
 }
@@ -119,6 +121,7 @@ impl fmt::Display for DecompressError {
             DecompressError::ExpectedAnotherByte => {
                 f.write_str("expected another byte, found none")
             }
+            DecompressError::OffsetZero => f.write_str("0 is not a valid match offset"),
             DecompressError::OffsetOutOfBounds => {
                 f.write_str("the offset to copy is not contained in the decompressed buffer")
             }

@@ -220,6 +220,12 @@ impl PtrSink {
     /// Panics if `pos` is out of bounds.
     #[inline]
     pub fn from_vec(output: &mut Vec<u8>, pos: usize) -> Self {
+        assert!(
+            pos <= output.len(),
+            "invalid pos {pos} for vec with len {}",
+            output.len()
+        );
+
         // SAFETY: Bytes behind pointer may be uninitialized.
         Self {
             output: output.as_mut_ptr(),