[PATCH] befs: bound B-tree descent depth

[Sangho Lee <kudo3228@gmail.com>]

BeFS B-tree descent follows child and overflow offsets supplied by the
filesystem image until a leaf node is reached.  It does not compare the
number of levels traversed with the B-tree superblock's max_depth field.

A crafted directory B-tree can therefore make an empty interior root point
its overflow field back to itself.  Directory iteration remains in
befs_btree_seekleaf() indefinitely.  The same unbounded descent exists in
befs_btree_find().

Track the descent depth in both paths and reject trees that exceed their
declared maximum depth.  Also apply a 64-level absolute limit so a
corrupted max_depth value cannot itself make the bound ineffective.  A
valid B-tree in a 64-bit address space cannot require more than 64 interior
levels.

This is separate from validation of the packed key layout inside each node;
the looping image uses a structurally valid empty node and malformed graph
connectivity.

Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")
Cc: stable@vger.kernel.org
Signed-off-by: Sangho Lee <kudo3228@gmail.com>
---
 fs/befs/btree.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/fs/befs/btree.c b/fs/befs/btree.c
index aa24f1dac..f27e8c94e 100644
--- a/fs/befs/btree.c
+++ b/fs/befs/btree.c
@@ -87,6 +87,8 @@ struct befs_btree_node {
 /* local constants */
 static const befs_off_t BEFS_BT_INVAL = 0xffffffffffffffffULL;
 
+#define BEFS_BTREE_MAX_DEPTH 64
+
 /* local functions */
 static int befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds,
 			       befs_btree_super * bt_super,
@@ -248,6 +250,7 @@ befs_btree_find(struct super_block *sb, const befs_data_stream *ds,
 	struct befs_btree_node *this_node;
 	befs_btree_super bt_super;
 	befs_off_t node_off;
+	u32 depth = 0;
 	int res;
 
 	befs_debug(sb, "---> %s Key: %s", __func__, key);
@@ -276,6 +279,12 @@ befs_btree_find(struct super_block *sb, const befs_data_stream *ds,
 	}
 
 	while (!befs_leafnode(this_node)) {
+		if (++depth > bt_super.max_depth ||
+		    depth > BEFS_BTREE_MAX_DEPTH) {
+			befs_error(sb, "B-tree depth exceeds limit");
+			goto error_alloc;
+		}
+
 		res = befs_find_key(sb, this_node, key, &node_off);
 		/* if no key set, try the overflow node */
 		if (res == BEFS_BT_OVERFLOW)
@@ -543,6 +552,7 @@ befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds,
 		    struct befs_btree_node *this_node,
 		    befs_off_t * node_off)
 {
+	u32 depth = 0;
 
 	befs_debug(sb, "---> %s", __func__);
 
@@ -559,6 +569,11 @@ befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds,
 	}
 
 	while (!befs_leafnode(this_node)) {
+		if (++depth > bt_super->max_depth ||
+		    depth > BEFS_BTREE_MAX_DEPTH) {
+			befs_error(sb, "B-tree depth exceeds limit");
+			goto error;
+		}
 
 		if (this_node->head.all_key_count == 0) {
 			befs_debug(sb, "%s encountered "
-- 
2.43.0