Memory corruption in out_batch parameter of batch lookup APIs

Memory corruption in out_batch parameter of batch lookup APIs

[Martin Kelly]

Hi, I noticed there's a subtlety to to the batch APIs 
(bpf_map_lookup_batch and bpf_map_lookup_and_delete_batch) that can lead 
to bugs if callers are not careful, and I'm wondering about the best way 
to document or address it.

Specifically, the size of the data pointed to by in_batch/out_batch is 
not clear, and if it's too small, the caller can see memory/stack 
corruption. The function documentation isn't super clear about this, 
calling in_batch "address of the first element in batch to read", so a 
caller might reasonably assume that a pointer size is fine. However, the 
right size actually depends on the map type.

For hash and array maps, out_batch will be u32 (as the parameter is used 
as an index). But for LPM trie, it will be the size of the key (in the 
case of LPM trie, I think that's 260 bytes). If a caller passes a 
pointer to memory smaller the key size, the kernel will overwrite past 
that memory and corrupt the stack (or wherever out_batch points). This 
is because of the copy_to_user(uobatch, prev_key, map->key_size) at the 
end of generic_map_lookup_batch.

It seems to me that we could add documentation to these functions 
indicating that out_batch should be able to hold at least one key to be 
safe. This is simple but overly strict (at the moment) for all map types 
other than LPM trie. However, if we specifically call out LPM trie as 
needing key-sized width while other map types need 4 bytes, then this 
documentation could easily become out-of-date as new map types are added.

We could alternatively add a statement like "out_batch should generally 
point to memory large enough to hold a single key, but for some map 
implementations a smaller type is possible". This gives more information 
but might be too vague for many API users, and it means future kernels 
could be tied to this implementation to avoid breaking users.

Any thoughts/preferences on how best to handle this? I'm happy to send a 
patch clarifying the documentation, but I'd like to get a general 
consensus on the best way to proceed first.

Thanks,

Martin

Re: Memory corruption in out_batch parameter of batch lookup APIs

[Yonghong Song]

On 2/16/24 4:24 PM, Martin Kelly wrote:
> Hi, I noticed there's a subtlety to to the batch APIs 
> (bpf_map_lookup_batch and bpf_map_lookup_and_delete_batch) that can 
> lead to bugs if callers are not careful, and I'm wondering about the 
> best way to document or address it.
>
> Specifically, the size of the data pointed to by in_batch/out_batch is 
> not clear, and if it's too small, the caller can see memory/stack 
> corruption. The function documentation isn't super clear about this, 
> calling in_batch "address of the first element in batch to read", so a 
> caller might reasonably assume that a pointer size is fine. However, 
> the right size actually depends on the map type.
>
> For hash and array maps, out_batch will be u32 (as the parameter is 
> used as an index). But for LPM trie, it will be the size of the key 
> (in the case of LPM trie, I think that's 260 bytes). If a caller 
> passes a pointer to memory smaller the key size, the kernel will 
> overwrite past that memory and corrupt the stack (or wherever 
> out_batch points). This is because of the copy_to_user(uobatch, 
> prev_key, map->key_size) at the end of generic_map_lookup_batch.
>
> It seems to me that we could add documentation to these functions 
> indicating that out_batch should be able to hold at least one key to 
> be safe. This is simple but overly strict (at the moment) for all map 
> types other than LPM trie. However, if we specifically call out LPM 
> trie as needing key-sized width while other map types need 4 bytes, 
> then this documentation could easily become out-of-date as new map 
> types are added.
>
> We could alternatively add a statement like "out_batch should 
> generally point to memory large enough to hold a single key, but for 
> some map implementations a smaller type is possible". This gives more 
> information but might be too vague for many API users, and it means 
> future kernels could be tied to this implementation to avoid breaking 
> users.
>
> Any thoughts/preferences on how best to handle this? I'm happy to send 
> a patch clarifying the documentation, but I'd like to get a general 
> consensus on the best way to proceed first.

For in_batch/out_batch, the only exception is hashmap which has in_batch/out_batch memory size to be 32.
For all other supported maps, in_batch/out_batch memory size should be equal to their corresponding key size.
Maybe you can clarify this in include/uapi/linux/bpf.h?

We can update the documentation later if there are any exceptions to the above rule.

>
> Thanks,
>
> Martin
>

Re: Memory corruption in out_batch parameter of batch lookup APIs

[Martin Kelly]

On 2/19/24 17:22, Yonghong Song wrote:
>
> On 2/16/24 4:24 PM, Martin Kelly wrote:
>> Hi, I noticed there's a subtlety to to the batch APIs 
>> (bpf_map_lookup_batch and bpf_map_lookup_and_delete_batch) that can 
>> lead to bugs if callers are not careful, and I'm wondering about the 
>> best way to document or address it.
>>
>> Specifically, the size of the data pointed to by in_batch/out_batch 
>> is not clear, and if it's too small, the caller can see memory/stack 
>> corruption. The function documentation isn't super clear about this, 
>> calling in_batch "address of the first element in batch to read", so 
>> a caller might reasonably assume that a pointer size is fine. 
>> However, the right size actually depends on the map type.
>>
>> For hash and array maps, out_batch will be u32 (as the parameter is 
>> used as an index). But for LPM trie, it will be the size of the key 
>> (in the case of LPM trie, I think that's 260 bytes). If a caller 
>> passes a pointer to memory smaller the key size, the kernel will 
>> overwrite past that memory and corrupt the stack (or wherever 
>> out_batch points). This is because of the copy_to_user(uobatch, 
>> prev_key, map->key_size) at the end of generic_map_lookup_batch.
>>
>> It seems to me that we could add documentation to these functions 
>> indicating that out_batch should be able to hold at least one key to 
>> be safe. This is simple but overly strict (at the moment) for all map 
>> types other than LPM trie. However, if we specifically call out LPM 
>> trie as needing key-sized width while other map types need 4 bytes, 
>> then this documentation could easily become out-of-date as new map 
>> types are added.
>>
>> We could alternatively add a statement like "out_batch should 
>> generally point to memory large enough to hold a single key, but for 
>> some map implementations a smaller type is possible". This gives more 
>> information but might be too vague for many API users, and it means 
>> future kernels could be tied to this implementation to avoid breaking 
>> users.
>>
>> Any thoughts/preferences on how best to handle this? I'm happy to 
>> send a patch clarifying the documentation, but I'd like to get a 
>> general consensus on the best way to proceed first.
>
> For in_batch/out_batch, the only exception is hashmap which has 
> in_batch/out_batch memory size to be 32.
> For all other supported maps, in_batch/out_batch memory size should be 
> equal to their corresponding key size.
> Maybe you can clarify this in include/uapi/linux/bpf.h?
>
> We can update the documentation later if there are any exceptions to 
> the above rule.
That sounds reasonable; I sent a patch for this. Thanks!
>
>>
>> Thanks,
>>
>> Martin
>>