Skip to contentSkip to conversation

bpf: unconditionally reset backtrack_state masks on global func exit

PATCH Applied Andrii Nakryiko 5 participants 6 messages Sep 18, 2023 – Sep 20, 2023

Subsystems (2)
lore
Share & tools
lore

Andrii Nakryiko

author maintainer
#0 lore raw

PATCH 1/1 bpf: unconditionally reset backtrack_state masks on global func exit

In mark_chain_precision() logic, when we reach the entry to a global func, it is expected that R1-R5 might be still requested to be marked precise. This would correspond to some integer input arguments being tracked as precise. This is all expected and handled as a special case.

What's not expected is that we'll leave backtrack_state structure with some register bits set. This is because for subsequent precision propagations backtrack_state is reused without clearing masks, as all code paths are carefully written in a way to leave empty backtrack_state with zeroed out masks, for speed.

The fix is trivial, we always clear register bit in the register mask, and then, optionally, set reg->precise if register is SCALAR_VALUE type.

Fixes be2ef8161572 ("bpf: allow precision tracking for programs with subprogs")
---
 kernel/bpf/verifier.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +3 -5
index bb78212fa5b2..c0c7d137066a 100644
@@ -4047,11 +4047,9 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
 				bitmap_from_u64(mask, bt_reg_mask(bt));
 				for_each_set_bit(i, mask, 32) {
 					reg = &st->frame[0]->regs[i];
-					if (reg->type != SCALAR_VALUE) {
-						bt_clear_reg(bt, i);
-						continue;
-					}
-					reg->precise = true;
+					bt_clear_reg(bt, i);
+					if (reg->type == SCALAR_VALUE)
+						reg->precise = true;
 				}
 				return 0;
 			}
Signature · 1 line
2.34.1
#1 lore raw
Quoted 28 lines · Andrii Nakryiko

In mark_chain_precision() logic, when we reach the entry to a global func, it is expected that R1-R5 might be still requested to be marked precise. This would correspond to some integer input arguments being tracked as precise. This is all expected and handled as a special case.

What's not expected is that we'll leave backtrack_state structure with some register bits set. This is because for subsequent precision propagations backtrack_state is reused without clearing masks, as all code paths are carefully written in a way to leave empty backtrack_state with zeroed out masks, for speed.

The fix is trivial, we always clear register bit in the register mask, and then, optionally, set reg->precise if register is SCALAR_VALUE type.

Fixes be2ef8161572 ("bpf: allow precision tracking for programs with subprogs")
---
 kernel/bpf/verifier.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +0 -0
index bb78212fa5b2..c0c7d137066a 100644
@@ -4047,11 +4047,9 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
                                bitmap_from_u64(mask, bt_reg_mask(bt));

kernel/bpf/verifier.c static int __mark_chain_precision(struct bpf_verifier_env *env, int regno) · line 4052

Quoted 10 lines
kernel/bpf/verifier.c +3 -5
                                for_each_set_bit(i, mask, 32) {
                                        reg = &st->frame[0]->regs[i];
-                                       if (reg->type != SCALAR_VALUE) {
-                                               bt_clear_reg(bt, i);
-                                               continue;
-                                       }
-                                       reg->precise = true;
+                                       bt_clear_reg(bt, i);
+                                       if (reg->type == SCALAR_VALUE)
+                                               reg->precise = true;

Looks good, but is there a selftest that can demonstrate the issue?

#2 lore raw
Quoted 34 lines · Alexei Starovoitov
Quoted 32 lines · Andrii Nakryiko

In mark_chain_precision() logic, when we reach the entry to a global func, it is expected that R1-R5 might be still requested to be marked precise. This would correspond to some integer input arguments being tracked as precise. This is all expected and handled as a special case.

What's not expected is that we'll leave backtrack_state structure with some register bits set. This is because for subsequent precision propagations backtrack_state is reused without clearing masks, as all code paths are carefully written in a way to leave empty backtrack_state with zeroed out masks, for speed.

The fix is trivial, we always clear register bit in the register mask, and then, optionally, set reg->precise if register is SCALAR_VALUE type.

Fixes be2ef8161572 ("bpf: allow precision tracking for programs with subprogs")
---
 kernel/bpf/verifier.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +0 -2
index bb78212fa5b2..c0c7d137066a 100644
@@ -4047,11 +4047,9 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
                                bitmap_from_u64(mask, bt_reg_mask(bt));
                                for_each_set_bit(i, mask, 32) {
                                        reg = &st->frame[0]->regs[i];
-                                       if (reg->type != SCALAR_VALUE) {
-                                               bt_clear_reg(bt, i);
Quoted 8 lines

kernel/bpf/verifier.c static int __mark_chain_precision(struct bpf_verifier_env *env, int regno) · line 4052

Quoted 6 lines
kernel/bpf/verifier.c +3 -3
-                                               continue;
-                                       }
-                                       reg->precise = true;
+                                       bt_clear_reg(bt, i);
+                                       if (reg->type == SCALAR_VALUE)
+                                               reg->precise = true;

Looks good, but is there a selftest that can demonstrate the issue?

I'll see if I can write something small and reliable.

#3 lore raw
Quoted 46 lines · Andrii Nakryiko
Quoted 34 lines · Alexei Starovoitov
Quoted 32 lines · Andrii Nakryiko

In mark_chain_precision() logic, when we reach the entry to a global func, it is expected that R1-R5 might be still requested to be marked precise. This would correspond to some integer input arguments being tracked as precise. This is all expected and handled as a special case.

What's not expected is that we'll leave backtrack_state structure with some register bits set. This is because for subsequent precision propagations backtrack_state is reused without clearing masks, as all code paths are carefully written in a way to leave empty backtrack_state with zeroed out masks, for speed.

The fix is trivial, we always clear register bit in the register mask, and then, optionally, set reg->precise if register is SCALAR_VALUE type.

Fixes be2ef8161572 ("bpf: allow precision tracking for programs with subprogs")
---
 kernel/bpf/verifier.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +0 -2
index bb78212fa5b2..c0c7d137066a 100644
@@ -4047,11 +4047,9 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
                                bitmap_from_u64(mask, bt_reg_mask(bt));
                                for_each_set_bit(i, mask, 32) {
                                        reg = &st->frame[0]->regs[i];
-                                       if (reg->type != SCALAR_VALUE) {
-                                               bt_clear_reg(bt, i);
Quoted 8 lines

kernel/bpf/verifier.c static int __mark_chain_precision(struct bpf_verifier_env *env, int regno) · line 4052

Quoted 6 lines
kernel/bpf/verifier.c +3 -3
-                                               continue;
-                                       }
-                                       reg->precise = true;
+                                       bt_clear_reg(bt, i);
+                                       if (reg->type == SCALAR_VALUE)
+                                               reg->precise = true;

Looks good, but is there a selftest that can demonstrate the issue?

Quoted 1 line

I'll see if I can write something small and reliable.

I give up. It seems like lots of conditions have to come together to trigger this. In production it was an application that happened to finish global func validation with that r1 set as precise in backtrack_state, and then proceeded to have some equivalent state matched immediately, which triggered propagate_precision() -> mark_chain_precision_batch(), but doing propagation of r9. Then with this bug we were looking to propagate r1 and r9, but the code path under verification didn't have any instruction touching r1 until we bubbled back up to helper call instruction, where verifier complained about r1 being required to be precise right after helper call (which is illegal, as r1-r5 are clobbered).

Few simple tests I tried failed to set up all the necessary conditions to trigger this in the exact sequence necessary. The fix is simple and well understood, I'd vote for landing it, given crafting a test is highly non-trivial.

maintainer
#4 lore raw
Quoted 62 lines · Andrii Nakryiko
Quoted 46 lines · Andrii Nakryiko
Quoted 34 lines · Alexei Starovoitov
Quoted 32 lines · Andrii Nakryiko

In mark_chain_precision() logic, when we reach the entry to a global func, it is expected that R1-R5 might be still requested to be marked precise. This would correspond to some integer input arguments being tracked as precise. This is all expected and handled as a special case.

What's not expected is that we'll leave backtrack_state structure with some register bits set. This is because for subsequent precision propagations backtrack_state is reused without clearing masks, as all code paths are carefully written in a way to leave empty backtrack_state with zeroed out masks, for speed.

The fix is trivial, we always clear register bit in the register mask, and then, optionally, set reg->precise if register is SCALAR_VALUE type.

Fixes be2ef8161572 ("bpf: allow precision tracking for programs with subprogs")
---
 kernel/bpf/verifier.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +0 -2
index bb78212fa5b2..c0c7d137066a 100644
@@ -4047,11 +4047,9 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
                                bitmap_from_u64(mask, bt_reg_mask(bt));
                                for_each_set_bit(i, mask, 32) {
                                        reg = &st->frame[0]->regs[i];
-                                       if (reg->type != SCALAR_VALUE) {
-                                               bt_clear_reg(bt, i);
Quoted 8 lines

kernel/bpf/verifier.c static int __mark_chain_precision(struct bpf_verifier_env *env, int regno) · line 4052

Quoted 6 lines
kernel/bpf/verifier.c +3 -3
-                                               continue;
-                                       }
-                                       reg->precise = true;
+                                       bt_clear_reg(bt, i);
+                                       if (reg->type == SCALAR_VALUE)
+                                               reg->precise = true;

Looks good, but is there a selftest that can demonstrate the issue?

Quoted 1 line

I'll see if I can write something small and reliable.

I give up. It seems like lots of conditions have to come together to trigger this. In production it was an application that happened to finish global func validation with that r1 set as precise in backtrack_state, and then proceeded to have some equivalent state matched immediately, which triggered propagate_precision() -> mark_chain_precision_batch(), but doing propagation of r9. Then with this bug we were looking to propagate r1 and r9, but the code path under verification didn't have any instruction touching r1 until we bubbled back up to helper call instruction, where verifier complained about r1 being required to be precise right after helper call (which is illegal, as r1-r5 are clobbered).

Quoted 4 lines

Few simple tests I tried failed to set up all the necessary conditions to trigger this in the exact sequence necessary. The fix is simple and well understood, I'd vote for landing it, given crafting a test is highly non-trivial.

I agree with this change and it does not cause any issues when tested locally. As far as I understand, to make a test case one needs to:
- make a special async callback that would leave some garbage "r1-r5" bits set in frame zero;
- trick verifier to check the async callback first and then jump to a state where precision marks on "r1-r5" are forbidden, e.g. a point right after pseudo call, so that backtrack_insn would jump to BPF_EXIT and complain.
Crafting such testcase sounds tricky and it might be fragile.

It appears to me that from time to time we get to situations when having kunit tests would be beneficial ¯\_(ツ)_/¯.

#5 lore raw
In reply to Andrii Nakryiko
This patch was applied to bpf/bpf.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This patch was applied to bpf/bpf.git (master)
by Alexei Starovoitov <[email protected]>:

Quoted 5 lines · On Mon, 18 Sep 2023 14:01:10 -0700 you wrote:

In mark_chain_precision() logic, when we reach the entry to a global func, it is expected that R1-R5 might be still requested to be marked precise. This would correspond to some integer input arguments being tracked as precise. This is all expected and handled as a special case.

Quoted 7 lines

What's not expected is that we'll leave backtrack_state structure with some register bits set. This is because for subsequent precision propagations backtrack_state is reused without clearing masks, as all code paths are carefully written in a way to leave empty backtrack_state with zeroed out masks, for speed.

[...]

Here is the summary with links:
- [bpf] bpf: unconditionally reset backtrack_state masks on global func exit

    https://git.kernel.org/bpf/bpf/c/81335f90e8a8

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html