[PATCH v1 0/3] lib/842: reject malformed streams before invalid memory accesses

[PATCH v1 0/3] lib/842: reject malformed streams before invalid memory accesses

[Karl Mehltretter]

sw842_decompress() backs the crypto 842 algorithm, the NX-842 software
fallback and zram's 842 backend. Two malformed-stream checks are missing:

  - indexed and short-data templates can write beyond the caller's stated
    output capacity; and
  - a repeat after one to seven bytes of short data reads before the
    output buffer.

The first underflows the unsigned remaining length, so every later capacity
check passes. The decoder keeps writing past the destination and can
return success with an output length the caller will trust.

The decoder already returns errors for format, capacity and CRC problems;
these two cases perform invalid accesses instead.

Patches 1 and 2 add the checks. After them every output write site is
capacity-checked, repeat cannot read before the output, and all input reads
stay bounded. Patch 3 adds KUnit cases for the three malformed streams and
for three valid streams at the exact acceptance boundaries, so the new
rejections cannot regress into off-by-one.

The KMSAN reports from
syzbot+e774233ff687aada969e and syzbot+8f77ff6144a73f0cf71b are unrelated.
They trace poison from uninitialized swapped-page storage, not these bounds
failures.

KUnit under QEMU 10.2.1 TCG, two vCPUs:

                  baseline      fixed
  i386              3/6          6/6
  x86_64            3/6          6/6

Baseline runs applied patch 3 alone: the three boundary cases pass, the
three malformed streams wrongly return success. A fixed x86_64 lockdep
kernel also passes 6/6.

Separately, an x86_64 KASAN QEMU run exercised all three malformed cases
through zram's compressed writeback path by corrupting the backing-disk
contents after writeback. The baseline reported two out-of-bounds writes
and one out-of-bounds read; fixed readback returned -EIO in all three cases
without a KASAN report.

Karl Mehltretter (3):
  lib/842: reject output overflows from index and short data
  lib/842: require a complete history block for repeat templates
  lib/842: add KUnit tests for the decompressor

 MAINTAINERS                      |   1 +
 lib/842/842_decompress.c         |   7 +-
 lib/Kconfig.debug                |  15 ++++
 lib/tests/842_decompress_kunit.c | 144 +++++++++++++++++++++++++++++++
 lib/tests/Makefile               |   1 +
 5 files changed, 167 insertions(+), 1 deletion(-)
 create mode 100644 lib/tests/842_decompress_kunit.c


base-commit: cf72cbb39da84b6f02f90c07f33b102fc10b16f0
-- 
2.53.0

[PATCH v1 1/3] lib/842: reject output overflows from index and short data

[Karl Mehltretter]

The output length passed to sw842_decompress() is the caller's buffer
capacity. Indexed copies write 2, 4 or 8 bytes and short-data templates
write up to 7, but neither checks that capacity before writing and
decrementing p->olen.

Overwriting an undersized destination then underflows p->olen, which is
unsigned, so every later bounds check in the stream passes. Subsequent
operations keep writing past the destination, and a matching CRC lets
sw842_decompress() return success with an output length larger than the
capacity the caller supplied.

This is reachable through zram's compressed writeback path. With 842
selected, targeted corruption of the compressed data on its backing device
made a KASAN kernel report vmalloc-out-of-bounds writes in __do_index() and
sw842_decompress() when zram read the page back.

Check the remaining output before both operations and return -ENOSPC,
matching the other output-producing templates.

Fixes: 2da572c959dd ("lib: add software 842 compression/decompression")
Cc: stable@vger.kernel.org
Assisted-by: LLM
Signed-off-by: Karl Mehltretter <kmehltretter@gmail.com>
---
Review notes:

  - Baseline i386 and x86_64 return success and change post-capacity
    canaries for both vectors; fixed kernels return -ENOSPC without
    changing them.
  - QEMU 11.0.2 TCG with x86_64 KASAN reproduced both operations through
    zram. A 568-byte compressed page was written to a virtio backing disk
    with compressed_writeback enabled, then its backing block was replaced
    before readback. Since zram supplies a PAGE_SIZE destination, these
    were PAGE_SIZE-scaled versions of the KUnit streams: the baseline
    reported an eight-byte vmalloc-out-of-bounds write in __do_index() for
    the indexed copy and a one-byte write in sw842_decompress() for short
    data. Fixed readback returned -EIO without a KASAN report.

 lib/842/842_decompress.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/lib/842/842_decompress.c b/lib/842/842_decompress.c
index 582085ef8b49c..87d1e0f8a4926 100644
--- a/lib/842/842_decompress.c
+++ b/lib/842/842_decompress.c
@@ -165,6 +165,9 @@ static int __do_index(struct sw842_param *p, u8 size, u8 bits, u64 fsize)
 	u64 index, offset, total = round_down(p->out - p->ostart, 8);
 	int ret;
 
+	if (size > p->olen)
+		return -ENOSPC;
+
 	ret = next_bits(p, &index, bits);
 	if (ret)
 		return ret;
@@ -344,6 +347,8 @@ int sw842_decompress(const u8 *in, unsigned int ilen,
 
 			if (!bytes || bytes > SHORT_DATA_BITS_MAX)
 				return -EINVAL;
+			if (bytes > p.olen)
+				return -ENOSPC;
 
 			while (bytes-- > 0) {
 				ret = next_bits(&p, &tmp, 8);
-- 
2.53.0

[PATCH v1 2/3] lib/842: require a complete history block for repeat templates

[Karl Mehltretter]

An 842 repeat template copies the preceding eight-byte output block. The
decoder rejects a repeat only when no output has been produced. A
short-data operation can produce between one and seven bytes before a
repeat.

Such a stream makes the repeat copy read before the start of the output
buffer. Depending on the surrounding mapping, this can fault or bring
preceding memory into the decompressed data.

This is also reachable through zram's compressed writeback path. With 842
selected, targeted corruption of the compressed data on its backing device
to a short-data-then-repeat stream made a KASAN kernel report a
vmalloc-out-of-bounds read when zram read the page back.

Require at least one complete output block before accepting a repeat.

Fixes: 2da572c959dd ("lib: add software 842 compression/decompression")
Cc: stable@vger.kernel.org
Assisted-by: LLM
Signed-off-by: Karl Mehltretter <kmehltretter@gmail.com>
---
Review notes:

  - add_short_data_template() has one caller, immediately before
    add_end_template(), so valid compressor output cannot place a repeat
    after short data.
  - QEMU 11.0.2 TCG with x86_64 KASAN reproduced this through zram. A page
    was written to a virtio backing disk with compressed_writeback enabled,
    then the backing block was replaced with SHORT_DATA(seven bytes),
    REPEAT(one block), END and CRC. Baseline readback reported an eight-byte
    vmalloc-out-of-bounds read starting one byte before zram's output page.
    Fixed readback returned -EIO without a KASAN report.

 lib/842/842_decompress.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/842/842_decompress.c b/lib/842/842_decompress.c
index 87d1e0f8a4926..45a9815abd637 100644
--- a/lib/842/842_decompress.c
+++ b/lib/842/842_decompress.c
@@ -309,7 +309,7 @@ int sw842_decompress(const u8 *in, unsigned int ilen,
 			if (ret)
 				return ret;
 
-			if (p.out == out) /* no previous bytes */
+			if (p.out - p.ostart < 8) /* no complete previous block */
 				return -EINVAL;
 
 			/* copy rep + 1 */
-- 
2.53.0

[PATCH v1 3/3] lib/842: add KUnit tests for the decompressor

[Karl Mehltretter]

Add table-driven tests for the 842 decompressor's output and history
validation.

Three malformed streams cover an indexed copy larger than the remaining
output, short data larger than the remaining output, and a repeat after
fewer than eight output bytes. Every case checks the return value, output
length and fixed guard bands on both sides of the output. Successful cases
also check complete contents from a poison-filled destination. The repeat
vector's CRC includes the leading guard byte, so the unfixed decoder
successfully validates the CRC after reading before the buffer.

Three valid streams cover the same boundaries at equality: an I8 index
consuming the final eight bytes, five short-data bytes consuming the final
five, and a repeat with exactly one block of history.

On an unmodified baseline the malformed cases fail and the boundary cases
pass; with the preceding fixes all six pass.

Assisted-by: LLM
Signed-off-by: Karl Mehltretter <kmehltretter@gmail.com>
---
Review notes:

  - CONFIG_842_DECOMPRESS_KUNIT_TEST=m selects 842_DECOMPRESS=m.
  - A fixed x86_64 CONFIG_PROVE_LOCKING=y run passes all six cases without
    a lockdep report.

 MAINTAINERS                      |   1 +
 lib/Kconfig.debug                |  15 ++++
 lib/tests/842_decompress_kunit.c | 144 +++++++++++++++++++++++++++++++
 lib/tests/Makefile               |   1 +
 4 files changed, 161 insertions(+)
 create mode 100644 lib/tests/842_decompress_kunit.c

diff --git a/MAINTAINERS b/MAINTAINERS
index 98c528c99917a..4456261cf5ea4 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -12459,6 +12459,7 @@ F:	drivers/crypto/nx/Makefile
 F:	drivers/crypto/nx/nx-842*
 F:	include/linux/sw842.h
 F:	lib/842/
+F:	lib/tests/842_decompress_kunit.c
 
 IBM Power in-Nest Crypto Acceleration
 M:	Breno Leitão <leitao@debian.org>
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 134b15a44625e..48201092b3df6 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2225,6 +2225,21 @@ menuconfig RUNTIME_TESTING_MENU
 
 if RUNTIME_TESTING_MENU
 
+config 842_DECOMPRESS_KUNIT_TEST
+	tristate "KUnit tests for the 842 decompressor" if !KUNIT_ALL_TESTS
+	depends on KUNIT
+	select 842_DECOMPRESS
+	default KUNIT_ALL_TESTS
+	help
+	  Enable stream-validation and boundary tests for the software 842
+	  decompressor. The tests exercise indexed copies, short data and
+	  repeat operations at valid and invalid output or history boundaries.
+
+	  For more information on KUnit and unit tests in general, refer to
+	  Documentation/dev-tools/kunit/.
+
+	  If unsure, say N.
+
 config TEST_DHRY
 	tristate "Dhrystone benchmark test"
 	help
diff --git a/lib/tests/842_decompress_kunit.c b/lib/tests/842_decompress_kunit.c
new file mode 100644
index 0000000000000..11202ba9539bc
--- /dev/null
+++ b/lib/tests/842_decompress_kunit.c
@@ -0,0 +1,144 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#include <kunit/test.h>
+#include <linux/sw842.h>
+
+#define SW842_GUARD_SIZE	8
+#define SW842_MAX_OUTPUT	16
+#define SW842_GUARD_BYTE	0x42
+#define SW842_OUTPUT_POISON	0x5a
+
+/* ZEROS, I8(0), END, CRC32. */
+static const u8 sw842_index_exact_fit[] = {
+	0xe6, 0x40, 0x3c, 0x00, 0x00, 0x00, 0x00,
+};
+
+/* D8(eight zero bytes), I8(0), END, CRC32. */
+static const u8 sw842_index_output_overflow[] = {
+	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+	0x06, 0x40, 0x3c, 0x00, 0x00, 0x00, 0x00,
+};
+
+/* ZEROS, SHORT_DATA(01 02 03 04 05), END, CRC32. */
+static const u8 sw842_short_data_exact_fit[] = {
+	0xe7, 0x68, 0x08, 0x10, 0x18, 0x20,
+	0x2f, 0xa9, 0x67, 0xfc, 0x07, 0xc0,
+};
+
+/* ZEROS, SHORT_DATA(five zero bytes), END, CRC32. */
+static const u8 sw842_short_data_output_overflow[] = {
+	0xe7, 0x48, 0x07, 0x80, 0x00, 0x00, 0x00, 0x00,
+};
+
+/* ZEROS, REPEAT(one block), END, CRC32. */
+static const u8 sw842_repeat_exact_history[] = {
+	0xe6, 0xc0, 0xf0, 0x00, 0x00, 0x00, 0x00,
+};
+
+/*
+ * SHORT_DATA(seven zero bytes), REPEAT(one block), END, CRC32.
+ * CRC32 includes SW842_GUARD_BYTE copied from before output into byte 7.
+ */
+static const u8 sw842_repeat_without_full_history[] = {
+	0xef, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+	0xd8, 0x1e, 0x09, 0xa3, 0x1d, 0xd6,
+};
+
+static const u8 sw842_zero_output[SW842_MAX_OUTPUT];
+static const u8 sw842_short_data_output[] = {
+	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+	0x01, 0x02, 0x03, 0x04, 0x05,
+};
+
+struct sw842_decompress_test_case {
+	const char *name;
+	const u8 *compressed;
+	unsigned int compressed_len;
+	const u8 *expected_output;
+	unsigned int output_capacity;
+	int expected_ret;
+};
+
+#define SW842_DECOMPRESS_CASE(_name, _compressed, _compressed_len, _expected, \
+			      _capacity, _ret) \
+	{ \
+		.name = _name, \
+		.compressed = _compressed, \
+		.compressed_len = _compressed_len, \
+		.expected_output = _expected, \
+		.output_capacity = _capacity, \
+		.expected_ret = _ret, \
+	}
+
+static const struct sw842_decompress_test_case sw842_decompress_cases[] = {
+	SW842_DECOMPRESS_CASE("index_exact_fit", sw842_index_exact_fit,
+			      ARRAY_SIZE(sw842_index_exact_fit),
+			      sw842_zero_output, 16, 0),
+	SW842_DECOMPRESS_CASE("index_output_overflow",
+			      sw842_index_output_overflow,
+			      ARRAY_SIZE(sw842_index_output_overflow),
+			      sw842_zero_output, 8, -ENOSPC),
+	SW842_DECOMPRESS_CASE("short_data_exact_fit",
+			      sw842_short_data_exact_fit,
+			      ARRAY_SIZE(sw842_short_data_exact_fit),
+			      sw842_short_data_output,
+			      sizeof(sw842_short_data_output), 0),
+	SW842_DECOMPRESS_CASE("short_data_output_overflow",
+			      sw842_short_data_output_overflow,
+			      ARRAY_SIZE(sw842_short_data_output_overflow),
+			      sw842_zero_output, 8, -ENOSPC),
+	SW842_DECOMPRESS_CASE("repeat_exact_history",
+			      sw842_repeat_exact_history,
+			      ARRAY_SIZE(sw842_repeat_exact_history),
+			      sw842_zero_output, 16, 0),
+	SW842_DECOMPRESS_CASE("repeat_without_full_history",
+			      sw842_repeat_without_full_history,
+			      ARRAY_SIZE(sw842_repeat_without_full_history),
+			      sw842_zero_output, 15, -EINVAL),
+};
+
+KUNIT_ARRAY_PARAM_DESC(sw842_decompress, sw842_decompress_cases, name);
+
+static void sw842_decompress_test(struct kunit *test)
+{
+	const struct sw842_decompress_test_case *test_case = test->param_value;
+	u8 storage[SW842_GUARD_SIZE + SW842_MAX_OUTPUT + SW842_GUARD_SIZE];
+	u8 expected_guard[SW842_GUARD_SIZE];
+	u8 *output = storage + SW842_GUARD_SIZE;
+	unsigned int output_len = test_case->output_capacity;
+	int ret;
+
+	KUNIT_ASSERT_LE(test, test_case->output_capacity, SW842_MAX_OUTPUT);
+	memset(storage, SW842_GUARD_BYTE, sizeof(storage));
+	memset(expected_guard, SW842_GUARD_BYTE, sizeof(expected_guard));
+	memset(output, SW842_OUTPUT_POISON, test_case->output_capacity);
+
+	ret = sw842_decompress(test_case->compressed,
+			       test_case->compressed_len, output, &output_len);
+
+	KUNIT_EXPECT_EQ(test, ret, test_case->expected_ret);
+	/* Every successful case is an exact-fit boundary test. */
+	KUNIT_EXPECT_EQ(test, output_len,
+			test_case->expected_ret ? 0U : test_case->output_capacity);
+	if (!test_case->expected_ret)
+		KUNIT_EXPECT_MEMEQ(test, output, test_case->expected_output,
+				   test_case->output_capacity);
+	KUNIT_EXPECT_MEMEQ(test, storage, expected_guard, SW842_GUARD_SIZE);
+	KUNIT_EXPECT_MEMEQ(test, output + test_case->output_capacity,
+			   expected_guard, SW842_GUARD_SIZE);
+}
+
+static struct kunit_case sw842_decompress_test_cases[] = {
+	KUNIT_CASE_PARAM(sw842_decompress_test, sw842_decompress_gen_params),
+	{}
+};
+
+static struct kunit_suite sw842_decompress_test_suite = {
+	.name = "842-decompress",
+	.test_cases = sw842_decompress_test_cases,
+};
+
+kunit_test_suite(sw842_decompress_test_suite);
+
+MODULE_DESCRIPTION("Software 842 decompressor KUnit tests");
+MODULE_LICENSE("GPL");
diff --git a/lib/tests/Makefile b/lib/tests/Makefile
index 3cac3b63a7522..89ce3acad9c39 100644
--- a/lib/tests/Makefile
+++ b/lib/tests/Makefile
@@ -4,6 +4,7 @@
 
 # KUnit tests
 CFLAGS_bitfield_kunit.o := $(DISABLE_STRUCTLEAK_PLUGIN)
+obj-$(CONFIG_842_DECOMPRESS_KUNIT_TEST) += 842_decompress_kunit.o
 obj-$(CONFIG_BASE64_KUNIT) += base64_kunit.o
 obj-$(CONFIG_BITOPS_KUNIT) += bitops_kunit.o
 obj-$(CONFIG_BITFIELD_KUNIT) += bitfield_kunit.o
-- 
2.53.0