[PATCH] befs: validate B-tree node layout before use

[이상호 <kudo3228@gmail.com>]

BeFS directory B-trees store several variable-sized regions inside each
on-disk B-tree node: the node header, packed key bytes, a key-length index,
and the value array.  The current reader byte-swaps all_key_count and
all_key_length from disk and then lets helpers derive pointers to the
key-length index and value array from those fields.

That means a malformed filesystem image can describe a layout that does not
fit in the buffer_head data that was actually read from disk.  In
particular, an oversized all_key_length or all_key_count can move the
key-length index or value array beyond the loaded node block.  Directory
iteration then follows those derived pointers and can read outside the node
buffer.  The local reproducer triggers KASAN reports in befs_bt_get_key()
and befs_btree_read().

The B-tree node parser should reject such images at the boundary where the
disk format is first converted into the in-memory node representation.  Add
a node-layout validator immediately after reading and byte-swapping the
node header, before later helpers can use the untrusted counts and lengths.
The validator checks that:

  - the node header fits in the bytes remaining in the block;
  - the packed key data fits after the header;
  - the aligned key-length index fits after the key data;
  - the value array fits after the key-length index; and
  - every key end offset is monotonic and remains within all_key_length.

Rejecting the malformed node at read time keeps the existing BeFS error
path and turns the crafted image into a mount/readdir failure instead of an
out-of-bounds read.

Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")
Cc: stable@vger.kernel.org
Signed-off-by: 이상호 <kudo3228@gmail.com>
---
Reproducer image and serial logs are available on maintainer request. They
are not included in this public patch email.

 fs/befs/btree.c |   83 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 83 insertions(+)

diff --git a/fs/befs/btree.c b/fs/befs/btree.c
index aa24f1daccdd..c5fc529f0069 100644
--- a/fs/befs/btree.c
+++ b/fs/befs/btree.c
@@ -100,6 +100,10 @@ static int befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
 			     struct befs_btree_node *node,
 			     befs_off_t node_off);
 
+static int befs_bt_validate_node(struct super_block *sb,
+				 struct befs_btree_node *node,
+				 size_t bytes);
+
 static int befs_leafnode(struct befs_btree_node *node);
 
 static fs16 *befs_bt_keylen_index(struct befs_btree_node *node);
@@ -192,6 +196,7 @@ befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
 		  struct befs_btree_node *node, befs_off_t node_off)
 {
 	uint off = 0;
+	size_t bytes;
 
 	befs_debug(sb, "---> %s", __func__);
 
@@ -206,6 +211,14 @@ befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
 
 		return BEFS_ERR;
 	}
+	if (off >= BEFS_SB(sb)->block_size) {
+		befs_error(sb, "%s node offset %u is outside block", __func__,
+			   off);
+		brelse(node->bh);
+		node->bh = NULL;
+		return BEFS_ERR;
+	}
+	bytes = BEFS_SB(sb)->block_size - off;
 	node->od_node =
 	    (befs_btree_nodehead *) ((void *) node->bh->b_data + off);
 
@@ -218,11 +231,81 @@ befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
 	    fs16_to_cpu(sb, node->od_node->all_key_count);
 	node->head.all_key_length =
 	    fs16_to_cpu(sb, node->od_node->all_key_length);
+	if (befs_bt_validate_node(sb, node, bytes) != BEFS_OK) {
+		brelse(node->bh);
+		node->bh = NULL;
+		return BEFS_ERR;
+	}
 
 	befs_debug(sb, "<--- %s", __func__);
 	return BEFS_OK;
 }
 
+static int
+befs_bt_validate_node(struct super_block *sb, struct befs_btree_node *node,
+		      size_t bytes)
+{
+	fs16 *keylen_index;
+	size_t keydata_end;
+	size_t keylen_index_off;
+	size_t keylen_index_size;
+	size_t valarray_off;
+	size_t valarray_size;
+	u16 prev_key_end = 0;
+	int i;
+
+	if (bytes < sizeof(befs_btree_nodehead)) {
+		befs_error(sb, "B-tree node is too small: %zu", bytes);
+		return BEFS_ERR;
+	}
+
+	if (node->head.all_key_length >
+	    bytes - sizeof(befs_btree_nodehead)) {
+		befs_error(sb, "B-tree node key data is too large: %u",
+			   node->head.all_key_length);
+		return BEFS_ERR;
+	}
+
+	keydata_end = sizeof(befs_btree_nodehead) +
+		      node->head.all_key_length;
+	keylen_index_off = (keydata_end + 7) & ~7UL;
+	keylen_index_size = node->head.all_key_count * sizeof(fs16);
+	if (keylen_index_off > bytes ||
+	    keylen_index_size > bytes - keylen_index_off) {
+		befs_error(sb, "B-tree node key index is too large: %u keys",
+			   node->head.all_key_count);
+		return BEFS_ERR;
+	}
+
+	valarray_off = keylen_index_off + keylen_index_size;
+	valarray_size = node->head.all_key_count * sizeof(fs64);
+	if (valarray_size > bytes - valarray_off) {
+		befs_error(sb, "B-tree node value array is too large: %u keys",
+			   node->head.all_key_count);
+		return BEFS_ERR;
+	}
+
+	keylen_index = befs_bt_keylen_index(node);
+	for (i = 0; i < node->head.all_key_count; i++) {
+		u16 key_end = fs16_to_cpu(sb, keylen_index[i]);
+
+		if (key_end < prev_key_end ||
+		    key_end > node->head.all_key_length) {
+			befs_error(sb, "B-tree node has invalid key offset");
+			return BEFS_ERR;
+		}
+		prev_key_end = key_end;
+	}
+
+	if (node->head.all_key_count &&
+	    prev_key_end != node->head.all_key_length) {
+		befs_error(sb, "B-tree node key length mismatch");
+		return BEFS_ERR;
+	}
+
+	return BEFS_OK;
+}
+
 /**
  * befs_btree_find - Find a key in a befs B+tree
  * @sb: Filesystem superblock
-- 
2.43.0