CVE-2023-28638 (C#, published 2023-03-27T21:15Z)
Description: value: Snappier is a high performance C# implementation of the Snappy compression algorithm. This is a buffer overrun vulnerability that can affect any user of Snappier 1.1.0. In this release, much of the code was rewritten to use byte references rather than pointers to pinned buffers. This change generally improves performance and reduces workload on the garbage collector. However, when the garbage collector performs compaction and rearranges memory, it must update any byte references on the stack to refer to the updated location. The .NET garbage collector can only update these byte references if they still point within the buffer or to a point one byte past the end of the buffer. If they point outside this area, the buffer itself may be moved while the byte reference stays the same. There are several places in 1.1.0 where byte references very briefly point outside the valid areas of buffers. These are at locations in the code being used for buffer range checks. While the invalid references are never dereferenced directly, if a GC compaction were to occur during the brief window when they are on the stack then it could invalidate the buffer range check and allow other operations to overrun the buffer.  This should be very difficult for an attacker to trigger intentionally. It would require a repetitive bulk attack with the hope that a GC compaction would occur at precisely the right moment during one of the requests. However, one of the range checks with this problem is a check based on input data in the decompression buffer, meaning malformed input data could be used to increase the chance of success. Note that any resulting buffer overrun is likely to cause access to protected memory, which will then cause an exception and the process to be terminated. Therefore, the most likely result of an attack is a denial of service. This issue has been patched in release 1.1.1. Users are advised to upgrade. Users unable to upgrade may pin buffers to a fixed location before using them for compression or decompression to mitigate some, but not all, of these cases. At least one temporary decompression buffer is internal to the library and never pinned.

Severity: nan (CVSS v3 base score: 5.9)
Weakness: CWE-119 \u2014 Improper Restriction of Operations within the Bounds of a Memory Buffer
The product performs operations on a memory buffer, but it reads from or writes to a memory location outside the buffer's intended boundary. This may result in read or write operations on unexpected memory locations that could be linked to other variables, data structures, or internal program data.
Repository: https://github.com/brantburnett/Snappier
Files changed:
Snappier.Benchmarks/FindMatchLength.cs
Snappier.Tests/Internal/SnappyCompressorTests.cs
Snappier/Internal/SnappyCompressor.cs
Snappier/Internal/SnappyDecompressor.cs
Commit message: Allow ref byte to point just past the end of spans (#73)

Motivation
----------
I was under the impression that `ref byte` should never point past the
end of a `Span<byte>` or `ReadOnlySpan<byte>` because then GC couldn't
recognize the pointer and adjust it during GC moves. However, this there
is a specific exception that allows `ref byte` to point precisely one
byte past the end and still be recognized to allow pointer arithmetic
scenarios like the ones in this algorithm.

Modifications
-------------
Where there is more complex logic (compared to the reference C++
implementation) to allow buffer end pointers to point to the last byte
in the buffer simplify this logic and point one byte past the end of the
buffer.

Also ensure that comparison operations that ensure a certain length
don't involve an intermediate pointer that moves off the beginning of
the buffer.

Results
-------
We're now back to closer to the reference C++ implementation but still
have memory safety.

Vulnerable code:
            ref byte s2Limit = ref Unsafe.Add(ref s1, _array.Length - 1);
                SnappyCompressor.FindMatchLength(ref s1, ref s2, ref Unsafe.Add(ref s2, length - 1), ref data);
                // Last byte of the input, not one byte past the end, to avoid issues on GC moves
                ref byte inputEnd = ref Unsafe.Add(ref inputStart, input.Length - 1);
                    ref byte ipLimit = ref Unsafe.Subtract(ref inputEnd, Constants.InputMarginBytes - 1);
                        Debug.Assert(!Unsafe.IsAddressGreaterThan(ref Unsafe.Add(ref nextEmit, 16), ref Unsafe.Add(ref inputEnd, 1)));
                if (!Unsafe.IsAddressGreaterThan(ref ip, ref inputEnd))
                    op = ref EmitLiteralSlow(ref op, ref ip, (uint) Unsafe.ByteOffset(ref ip, ref inputEnd) + 1);
        ///   and n &lt;= (s2_limit - s2 + 1).
        /// Does not read *(s1 + (s2_limit - s2 + 1)) or beyond.
        /// Requires that s2_limit+1 &gt;= s2.
        /// <remarks>
        /// The reference implementation has s2Limit as one byte past the end of the input,
        /// but this implementation has it at the end of the input. This ensures that it always
        /// points within the array in case GC moves the array.
        /// </remarks>
            Debug.Assert(!Unsafe.IsAddressLessThan(ref Unsafe.Add(ref s2Limit, 1), ref s2));
            while (!Unsafe.IsAddressGreaterThan(ref s2, ref Unsafe.Subtract(ref s2Limit, 3))
            if (BitConverter.IsLittleEndian && !Unsafe.IsAddressGreaterThan(ref s2, ref Unsafe.Subtract(ref s2Limit, 3)))
                while (!Unsafe.IsAddressGreaterThan(ref s2, ref s2Limit) && Unsafe.Add(ref s1, matched) == s2)
            if (!Unsafe.IsAddressGreaterThan(ref s2, ref Unsafe.Subtract(ref s2Limit, 7)))
            if (!Unsafe.IsAddressGreaterThan(ref s2, ref Unsafe.Subtract(ref s2Limit, 15)))
            while (!Unsafe.IsAddressGreaterThan(ref s2, ref Unsafe.Subtract(ref s2Limit, 15)))
            while (!Unsafe.IsAddressGreaterThan(ref s2, ref s2Limit))
                    if (!Unsafe.IsAddressGreaterThan(ref s2, ref Unsafe.Subtract(ref s2Limit, 7)))

                // The reference Snappy implementation uses inputEnd as a pointer one byte past the end of the buffer.
                // However, this is not safe when using ref locals. The ref must point to somewhere within the array
                // so that GC can adjust the ref if the memory is moved.
                ref byte inputEnd = ref Unsafe.Add(ref input, inputSpan.Length - 1);
                ref byte inputLimitMinMaxTagLength = ref Unsafe.Subtract(ref inputEnd, Math.Min(inputSpan.Length, Constants.MaximumTagLength - 1) - 1);
                // We always allocate buffer with at least one extra byte on the end, so bufferEnd doesn't have the same
                // restrictions as inputEnd.
                        inputEnd = ref Unsafe.Add(ref input, newScratchLength - 1);
                            Math.Min(newScratchLength, Constants.MaximumTagLength - 1) - 1);
                        if (TryFastAppend(ref op, ref bufferEnd, in input, Unsafe.ByteOffset(ref input, ref inputEnd) + 1, literalLength))
                        nint inputRemaining = Unsafe.ByteOffset(ref input, ref inputEnd) + 1;
                                    inputEnd = ref Unsafe.Add(ref input, newScratchLength - 1);
                                        Math.Min(newScratchLength, Constants.MaximumTagLength - 1) - 1);
                                inputEnd = ref Unsafe.Add(ref input, newScratchLength - 1);
                                    Math.Min(newScratchLength, Constants.MaximumTagLength - 1) - 1);
                nint inputRemaining = Unsafe.ByteOffset(ref input, ref inputEnd) + 1;
            if (Unsafe.IsAddressGreaterThan(ref input, ref inputEnd))
            uint toCopy = Math.Min((uint)Unsafe.ByteOffset(ref input, ref inputEnd) + 1, needed - _scratchLength);
            if (Unsafe.IsAddressGreaterThan(ref input, ref inputEnd))
            uint inputLength = (uint)Unsafe.ByteOffset(ref input, ref inputEnd) + 1;
                    // Always pad the lookback buffer with an extra byte that we don't use. This allows a "ref byte" reference past
                    // the end of the perceived buffer that still points within the array. This is a requirement so that GC can recognize
                    // the "ref byte" points within the array and adjust it if the array is moved.
                    _lookbackBufferArray = ArrayPool<byte>.Shared.Rent(value.GetValueOrDefault() + 1);
                    _lookbackBuffer = _lookbackBufferArray.AsMemory(0, _lookbackBufferArray.Length - 1);
        private void Append(ref byte op, ref byte bufferEnd, in byte input, nint length)
        private bool TryFastAppend(ref byte op, ref byte bufferEnd, in byte input, nint available, nint length)
        private void AppendFromSelf(ref byte op, ref byte buffer, ref byte bufferEnd, uint copyOffset, nint length)
            ref byte source = ref Unsafe.Subtract(ref op, copyOffset);
            if (!Unsafe.IsAddressLessThan(ref source, ref op) || Unsafe.IsAddressLessThan(ref source, ref buffer))

Fixed code:
            ref byte s2Limit = ref Unsafe.Add(ref s1, _array.Length);
                SnappyCompressor.FindMatchLength(ref s1, ref s2, ref Unsafe.Add(ref s2, length), ref data);
                ref byte inputEnd = ref Unsafe.Add(ref inputStart, input.Length);
                    ref byte ipLimit = ref Unsafe.Subtract(ref inputEnd, Constants.InputMarginBytes);
                        Debug.Assert(!Unsafe.IsAddressGreaterThan(ref Unsafe.Add(ref nextEmit, 16), ref inputEnd));
                if (Unsafe.IsAddressLessThan(ref ip, ref inputEnd))
                    op = ref EmitLiteralSlow(ref op, ref ip, (uint) Unsafe.ByteOffset(ref ip, ref inputEnd));
        ///   and n &lt;= (s2_limit - s2).
        /// Does not read *(s1 + (s2_limit - s2)) or beyond.
        /// Requires that s2_limit &gt;= s2.
            Debug.Assert(!Unsafe.IsAddressLessThan(ref s2Limit, ref s2));
            while (Unsafe.ByteOffset(ref s2, ref s2Limit) >= (nint)4
            if (BitConverter.IsLittleEndian && Unsafe.ByteOffset(ref s2, ref s2Limit) >= (nint)4)
                while (Unsafe.IsAddressLessThan(ref s2, ref s2Limit) && Unsafe.Add(ref s1, matched) == s2)
            if (Unsafe.ByteOffset(ref s2, ref s2Limit) >= (nint)8)
            if (Unsafe.ByteOffset(ref s2, ref s2Limit) >= (nint)16)
            while (Unsafe.ByteOffset(ref s2, ref s2Limit) >= (nint)16)
            while (Unsafe.IsAddressLessThan(ref s2, ref s2Limit))
                    if (Unsafe.ByteOffset(ref s2, ref s2Limit) >= (nint)8)
                ref byte inputEnd = ref Unsafe.Add(ref input, inputSpan.Length);
                ref byte inputLimitMinMaxTagLength = ref Unsafe.Subtract(ref inputEnd, Math.Min(inputSpan.Length, Constants.MaximumTagLength - 1));
                        inputEnd = ref Unsafe.Add(ref input, newScratchLength);
                            Math.Min(newScratchLength, Constants.MaximumTagLength - 1));
                        if (TryFastAppend(ref op, ref bufferEnd, in input, Unsafe.ByteOffset(ref input, ref inputEnd), literalLength))
                        nint inputRemaining = Unsafe.ByteOffset(ref input, ref inputEnd);
                                    inputEnd = ref Unsafe.Add(ref input, newScratchLength);
                                        Math.Min(newScratchLength, Constants.MaximumTagLength - 1));
                                inputEnd = ref Unsafe.Add(ref input, newScratchLength);
                                    Math.Min(newScratchLength, Constants.MaximumTagLength - 1));
                nint inputRemaining = Unsafe.ByteOffset(ref input, ref inputEnd);
            if (!Unsafe.IsAddressLessThan(ref input, ref inputEnd))
            uint toCopy = Math.Min((uint)Unsafe.ByteOffset(ref input, ref inputEnd), needed - _scratchLength);
            if (!Unsafe.IsAddressLessThan(ref input, ref inputEnd))
            uint inputLength = (uint)Unsafe.ByteOffset(ref input, ref inputEnd);
                    _lookbackBufferArray = ArrayPool<byte>.Shared.Rent(value.GetValueOrDefault());
                    _lookbackBuffer = _lookbackBufferArray.AsMemory(0, _lookbackBufferArray.Length);
        private static void Append(ref byte op, ref byte bufferEnd, in byte input, nint length)
        private static bool TryFastAppend(ref byte op, ref byte bufferEnd, in byte input, nint available, nint length)
        private static void AppendFromSelf(ref byte op, ref byte buffer, ref byte bufferEnd, uint copyOffset, nint length)
            // ToInt64() ensures that this logic works correctly on x86 (with a slight perf hit on x86, though). This is because
            // nint is only 32-bit on x86, so casting uint copyOffset to an nint for the comparison can result in a negative number with some
            // forms of illegal data. This would then bypass the exception and cause unsafe memory access. Performing the comparison
            // as a long ensures we have enough bits to not lose data. On 64-bit platforms this is effectively a no-op.
            if (copyOffset == 0 || Unsafe.ByteOffset(ref buffer, ref op).ToInt64() < copyOffset)
            ref byte source = ref Unsafe.Subtract(ref op, copyOffset);