befs: bound B-tree descent depth
Subsystems (2)
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.
--- fs/befs/btree.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)
fs/befs/btree.c +15 -0
@@ -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