Skip to contentSkip to conversation

befs: bound B-tree descent depth

PATCH New Sangho Lee 1 participant 1 message Jul 22

Subsystems (2)
lore
Share & tools
lore

Sangho Lee

author
#0 lore raw

PATCH 1/1 befs: bound B-tree descent depth

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")
---
 fs/befs/btree.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
fs/befs/btree.c +15 -0
index aa24f1dac..f27e8c94e 100644
@@ -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 "
Signature · 1 line
2.43.0