[RFC,bpf-next,RESEND,03/16] bpf: Improve bpf kfuncs pointer arguments chain of trust

Commit Message

Juntong Deng July 11, 2024, 11:19 a.m. UTC

Currently we have only three ways to get valid pointers:

1. Pointers which are passed as tracepoint or struct_ops
callback arguments.

2. Pointers which were returned from a KF_ACQUIRE kfunc.

3. Guaranteed valid nested pointers (e.g. using the
BTF_TYPE_SAFE_TRUSTED macro)

But this does not cover all cases and we cannot get valid
pointers to some objects, causing the chain of trust to be
broken (we cannot get a valid object pointer from another
valid object pointer).

The following are some examples of cases that are not covered:

1. struct socket
There is no reference counting in a struct socket, the reference
counting is actually in the struct file, so it does not make sense
to use a combination of KF_ACQUIRE and KF_RELEASE to trick the
verifier to make the pointer to struct socket valid.

2. sk_write_queue in struct sock
sk_write_queue is a struct member in struct sock, not a pointer
member, so we cannot use the guaranteed valid nested pointer method
to get a valid pointer to sk_write_queue.

3. The pointer returned by iterator next method
Currently we cannot pass the pointer returned by the iterator next
method as argument to the KF_TRUSTED_ARGS kfuncs, because the pointer
returned by the iterator next method is not "valid".

This patch adds the KF_OBTAIN flag to solve examples 1 and 2, for cases
where a valid pointer can be obtained without manipulating the reference
count. For KF_OBTAIN kfuncs, the arguments must be valid pointers.
KF_OBTAIN kfuncs guarantees that if the passed pointer argument is valid,
then the pointer returned by KF_OBTAIN kfuncs is also valid.

For example, bpf_socket_from_file() is KF_OBTAIN, and if the struct file
pointer passed in is valid (KF_ACQUIRE), then the struct socket pointer
returned is also valid. Another example, bpf_receive_queue_from_sock() is
KF_OBTAIN, and if the struct sock pointer passed in is valid, then the
sk_receive_queue pointer returned is also valid.

In addition, this patch sets the pointer returned by the iterator next
method to be valid. This is based on the fact that if the iterator is
implemented correctly, then the pointer returned from the iterator next
method should be valid. This does not make the NULL pointer valid.
If the iterator next method has the KF_RET_NULL flag, then the verifier
will ask the ebpf program to check the NULL pointer.

Signed-off-by: Juntong Deng <[e-mail]>
---
 include/linux/btf.h   |  1 +
 kernel/bpf/verifier.c | 12 +++++++++++-
 2 files changed, 12 insertions(+), 1 deletion(-)

Comments

Kumar Kartikeya Dwivedi July 23, 2024, 12:20 a.m. UTC | #1

On Thu, 11 Jul 2024 at 13:26, Juntong Deng <[e-mail]> wrote:
>
> Currently we have only three ways to get valid pointers:
>
> 1. Pointers which are passed as tracepoint or struct_ops
> callback arguments.
>
> 2. Pointers which were returned from a KF_ACQUIRE kfunc.
>
> 3. Guaranteed valid nested pointers (e.g. using the
> BTF_TYPE_SAFE_TRUSTED macro)
>
> But this does not cover all cases and we cannot get valid
> pointers to some objects, causing the chain of trust to be
> broken (we cannot get a valid object pointer from another
> valid object pointer).
>
> The following are some examples of cases that are not covered:
>
> 1. struct socket
> There is no reference counting in a struct socket, the reference
> counting is actually in the struct file, so it does not make sense
> to use a combination of KF_ACQUIRE and KF_RELEASE to trick the
> verifier to make the pointer to struct socket valid.

Yes, but the KF_OBTAIN like flag also needs to ensure that lifetime
relationships are reflected in the verifier state.
If we return a trusted pointer A using bpf_sock_from_file, but
argument B it takes is later released, the verifier needs to ensure
that the pointer A whose lifetime belongs to that pointer B also gets
scrubbed.

>
> 2. sk_write_queue in struct sock
> sk_write_queue is a struct member in struct sock, not a pointer
> member, so we cannot use the guaranteed valid nested pointer method
> to get a valid pointer to sk_write_queue.

I think Matt recently had a patch addressing this issue:
https://lore.kernel.org/bpf/[e-mail]/
I believe that should resolve this one (as far as passing them into
KF_TRUSTED_ARGS kfuncs is concerned atleast).

>
> 3. The pointer returned by iterator next method
> Currently we cannot pass the pointer returned by the iterator next
> method as argument to the KF_TRUSTED_ARGS kfuncs, because the pointer
> returned by the iterator next method is not "valid".

This does sound ok though.

>
> This patch adds the KF_OBTAIN flag to solve examples 1 and 2, for cases
> where a valid pointer can be obtained without manipulating the reference
> count. For KF_OBTAIN kfuncs, the arguments must be valid pointers.
> KF_OBTAIN kfuncs guarantees that if the passed pointer argument is valid,
> then the pointer returned by KF_OBTAIN kfuncs is also valid.
>
> For example, bpf_socket_from_file() is KF_OBTAIN, and if the struct file
> pointer passed in is valid (KF_ACQUIRE), then the struct socket pointer
> returned is also valid. Another example, bpf_receive_queue_from_sock() is
> KF_OBTAIN, and if the struct sock pointer passed in is valid, then the
> sk_receive_queue pointer returned is also valid.
>
> In addition, this patch sets the pointer returned by the iterator next
> method to be valid. This is based on the fact that if the iterator is
> implemented correctly, then the pointer returned from the iterator next
> method should be valid. This does not make the NULL pointer valid.
> If the iterator next method has the KF_RET_NULL flag, then the verifier
> will ask the ebpf program to check the NULL pointer.
>
> Signed-off-by: Juntong Deng <[e-mail]>
> ---

I think you should look at bpf_tcp_sock helper (and others), which
converts struct bpf_sock to bpf_tcp_sock. It also transfers the
ref_obj_id into the return value to ensure ownership is reflected
correctly regardless of the type. That pattern has a specific name
(is_ptr_cast_function), but idk what to call this.

Juntong Deng July 31, 2024, 1:28 p.m. UTC | #2

On 7/23/24 01:20, Kumar Kartikeya Dwivedi wrote:
> On Thu, 11 Jul 2024 at 13:26, Juntong Deng <[e-mail]> wrote:
>>
>> Currently we have only three ways to get valid pointers:
>>
>> 1. Pointers which are passed as tracepoint or struct_ops
>> callback arguments.
>>
>> 2. Pointers which were returned from a KF_ACQUIRE kfunc.
>>
>> 3. Guaranteed valid nested pointers (e.g. using the
>> BTF_TYPE_SAFE_TRUSTED macro)
>>
>> But this does not cover all cases and we cannot get valid
>> pointers to some objects, causing the chain of trust to be
>> broken (we cannot get a valid object pointer from another
>> valid object pointer).
>>
>> The following are some examples of cases that are not covered:
>>
>> 1. struct socket
>> There is no reference counting in a struct socket, the reference
>> counting is actually in the struct file, so it does not make sense
>> to use a combination of KF_ACQUIRE and KF_RELEASE to trick the
>> verifier to make the pointer to struct socket valid.
> 
> Yes, but the KF_OBTAIN like flag also needs to ensure that lifetime
> relationships are reflected in the verifier state.
> If we return a trusted pointer A using bpf_sock_from_file, but
> argument B it takes is later released, the verifier needs to ensure
> that the pointer A whose lifetime belongs to that pointer B also gets
> scrubbed.
> 

Thanks for your review!

You are right, I will fix this problem in the next version of the patch.

>>
>> 2. sk_write_queue in struct sock
>> sk_write_queue is a struct member in struct sock, not a pointer
>> member, so we cannot use the guaranteed valid nested pointer method
>> to get a valid pointer to sk_write_queue.
> 
> I think Matt recently had a patch addressing this issue:
> https://lore.kernel.org/bpf/[e-mail]/
> I believe that should resolve this one (as far as passing them into
> KF_TRUSTED_ARGS kfuncs is concerned atleast).
> 

Thanks for letting me know.

I tested it and it works well in most cases, but there are a few cases
that are not fully resolved.

Yes, the verifier has relaxed the constraint on non-zero offset
pointers, but the type of the pointer does not change.

This means that passing non-zero offset pointers as arguments to kfuncs
with KF_ACQUIRE will be rejected by the verifier because KF_ACQUIRE
requires strict type match and casting cannot be used.

An example, bpf_skb_peek_tail:

# ; struct sk_buff *skb = bpf_skb_peek_tail(head);
@ test_restore_udp_socket.bpf.c:209

# 75: (bf) r1 = r2                      ;
frame2: R1_w=ptr_sock(ref_obj_id=6,off=168)
R2=ptr_sock(ref_obj_id=6,off=168) refs=4,6

# 76: (85) call bpf_skb_peek_tail#101113
# kernel function bpf_skb_peek_tail args#0 expected pointer to
STRUCT sk_buff_head but R1 has a pointer to STRUCT sock

Should we relax the strict type-matching constraint on non-zero offset
pointers when used as arguments to kfuncs with KF_ACQUIRE?


In addition, this method is not portable (such as &task->cpus_mask),
and the offset of the member will change once a new structure member
is added, or an old structure member is removed.

Now that we have relaxed the constraints on non-zero offset pointers,
this method will probably be used a lot, maybe we could add a
BPF_CORE_POINTER macro to get a pointer to a struct member?
(Different from BPF_CORE_READ, which is reading member contents)

For example, BPF_CORE_POINTER(task, cpus_mask), which is a simple
user-friendly wrapper for __builtin_preserve_access_index.

>>
>> 3. The pointer returned by iterator next method
>> Currently we cannot pass the pointer returned by the iterator next
>> method as argument to the KF_TRUSTED_ARGS kfuncs, because the pointer
>> returned by the iterator next method is not "valid".
> 
> This does sound ok though.
> 
>>
>> This patch adds the KF_OBTAIN flag to solve examples 1 and 2, for cases
>> where a valid pointer can be obtained without manipulating the reference
>> count. For KF_OBTAIN kfuncs, the arguments must be valid pointers.
>> KF_OBTAIN kfuncs guarantees that if the passed pointer argument is valid,
>> then the pointer returned by KF_OBTAIN kfuncs is also valid.
>>
>> For example, bpf_socket_from_file() is KF_OBTAIN, and if the struct file
>> pointer passed in is valid (KF_ACQUIRE), then the struct socket pointer
>> returned is also valid. Another example, bpf_receive_queue_from_sock() is
>> KF_OBTAIN, and if the struct sock pointer passed in is valid, then the
>> sk_receive_queue pointer returned is also valid.
>>
>> In addition, this patch sets the pointer returned by the iterator next
>> method to be valid. This is based on the fact that if the iterator is
>> implemented correctly, then the pointer returned from the iterator next
>> method should be valid. This does not make the NULL pointer valid.
>> If the iterator next method has the KF_RET_NULL flag, then the verifier
>> will ask the ebpf program to check the NULL pointer.
>>
>> Signed-off-by: Juntong Deng <[e-mail]>
>> ---
> 
> I think you should look at bpf_tcp_sock helper (and others), which
> converts struct bpf_sock to bpf_tcp_sock. It also transfers the
> ref_obj_id into the return value to ensure ownership is reflected
> correctly regardless of the type. That pattern has a specific name
> (is_ptr_cast_function), but idk what to call this.

Thanks for mentioning this part of the code!

I tried it, it was very helpful.

After setting ref_obj_id, once pointer A (passed into KF_OBTAIN kfuncs)
is released, then pointer B (returned from KF_OBTAIN kfuncs)
becomes invalid.

I will include this fix in the next version of the patch.

Kumar Kartikeya Dwivedi July 31, 2024, 4:35 p.m. UTC | #3

On Wed, 31 Jul 2024 at 15:29, Juntong Deng <[e-mail]> wrote:
>
> On 7/23/24 01:20, Kumar Kartikeya Dwivedi wrote:
> > On Thu, 11 Jul 2024 at 13:26, Juntong Deng <[e-mail]> wrote:
> >>
> >> [...]
> >>
> >> 2. sk_write_queue in struct sock
> >> sk_write_queue is a struct member in struct sock, not a pointer
> >> member, so we cannot use the guaranteed valid nested pointer method
> >> to get a valid pointer to sk_write_queue.
> >
> > I think Matt recently had a patch addressing this issue:
> > https://lore.kernel.org/bpf/[e-mail]/
> > I believe that should resolve this one (as far as passing them into
> > KF_TRUSTED_ARGS kfuncs is concerned atleast).
> >
>
> Thanks for letting me know.
>
> I tested it and it works well in most cases, but there are a few cases
> that are not fully resolved.
>
> Yes, the verifier has relaxed the constraint on non-zero offset
> pointers, but the type of the pointer does not change.
>
> This means that passing non-zero offset pointers as arguments to kfuncs
> with KF_ACQUIRE will be rejected by the verifier because KF_ACQUIRE
> requires strict type match and casting cannot be used.
>
> An example, bpf_skb_peek_tail:
>
> # ; struct sk_buff *skb = bpf_skb_peek_tail(head);
> @ test_restore_udp_socket.bpf.c:209
>
> # 75: (bf) r1 = r2                      ;
> frame2: R1_w=ptr_sock(ref_obj_id=6,off=168)
> R2=ptr_sock(ref_obj_id=6,off=168) refs=4,6
>
> # 76: (85) call bpf_skb_peek_tail#101113
> # kernel function bpf_skb_peek_tail args#0 expected pointer to
> STRUCT sk_buff_head but R1 has a pointer to STRUCT sock
>
> Should we relax the strict type-matching constraint on non-zero offset
> pointers when used as arguments to kfuncs with KF_ACQUIRE?
>

Yes, I think it makes sense (on surface, though it requires some
deliberation, can do it over the exact code).
As long as we prevent special cases through existing
btf_type_ids_nocast_alias, it should be ok.
Please send a separate patch for this, and include selftests
exercising corner cases.

>
> In addition, this method is not portable (such as &task->cpus_mask),
> and the offset of the member will change once a new structure member
> is added, or an old structure member is removed.

This should be handled by BPF CO-RE. A lot of selftests would fail if
this didn't work.
As long as the struct is annotated as __attribute__((preserve_access_index)).

>
> [...]

Patch

diff --git a/include/linux/btf.h b/include/linux/btf.h
index 323a74489562..624f1e3d6287 100644
--- a/include/linux/btf.h
+++ b/include/linux/btf.h
@@ -77,6 +77,7 @@ 
 #define KF_RCU_PROTECTED (1 << 11) /* kfunc should be protected by rcu cs when they are invoked */
 #define KF_ITER_GETTER   (1 << 12) /* kfunc implements BPF iter getter */
 #define KF_ITER_SETTER   (1 << 13) /* kfunc implements BPF iter setter */
+#define KF_OBTAIN        (1 << 14) /* kfunc is an obtain function */
 
 /*
  * Tag marking a kernel function as a kfunc. This is meant to minimize the
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 51302a256c30..177c98448b05 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -10819,9 +10819,15 @@  static bool is_kfunc_release(struct bpf_kfunc_call_arg_meta *meta)
 	return meta->kfunc_flags & KF_RELEASE;
 }
 
+static bool is_kfunc_obtain(struct bpf_kfunc_call_arg_meta *meta)
+{
+	return meta->kfunc_flags & KF_OBTAIN;
+}
+
 static bool is_kfunc_trusted_args(struct bpf_kfunc_call_arg_meta *meta)
 {
-	return (meta->kfunc_flags & KF_TRUSTED_ARGS) || is_kfunc_release(meta);
+	return (meta->kfunc_flags & KF_TRUSTED_ARGS) || is_kfunc_release(meta) ||
+		is_kfunc_obtain(meta);
 }
 
 static bool is_kfunc_sleepable(struct bpf_kfunc_call_arg_meta *meta)
@@ -12682,6 +12688,10 @@  static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 			/* For mark_ptr_or_null_reg, see 93c230e3f5bd6 */
 			regs[BPF_REG_0].id = ++env->id_gen;
 		}
+
+		if (is_kfunc_obtain(&meta) || is_iter_next_kfunc(&meta))
+			regs[BPF_REG_0].type |= PTR_TRUSTED;
+
 		mark_btf_func_reg_size(env, BPF_REG_0, sizeof(void *));
 		if (is_kfunc_acquire(&meta)) {
 			int id = acquire_reference_state(env, insn_idx);