[PATCH bpf v2] bpf: verifier: make sure callees don't prune with caller differences

[PATCH bpf v2] bpf: verifier: make sure callees don't prune with caller differences

[Jakub Kicinski]

Currently for liveness and state pruning the register parentage
chains don't include states of the callee.  This makes some sense
as the callee can't access those registers.  However, this means
that READs done after the callee returns will not propagate into
the states of the callee.  Callee will then perform pruning
disregarding differences in caller state.

Example:

   0: (85) call bpf_user_rnd_u32
   1: (b7) r8 = 0
   2: (55) if r0 != 0x0 goto pc+1
   3: (b7) r8 = 1
   4: (bf) r1 = r8
   5: (85) call pc+4
   6: (15) if r8 == 0x1 goto pc+1
   7: (05) *(u64 *)(r9 - 8) = r3
   8: (b7) r0 = 0
   9: (95) exit

   10: (15) if r1 == 0x0 goto pc+0
   11: (95) exit

Here we acquire unknown state with call to get_random() [1].  Then
we store this random state in r8 (either 0 or 1) [1 - 3], and make
a call on line 5.  Callee does nothing but a trivial conditional
jump (to create a pruning point).  Upon return caller checks the
state of r8 and either performs an unsafe read or not.

Verifier will first explore the path with r8 == 1, creating a pruning
point at [11].  The parentage chain for r8 will include only callers
states so once verifier reaches [6] it will mark liveness only on states
in the caller, and not [11].  Now when verifier walks the paths with
r8 == 0 it will reach [11] and since REG_LIVE_READ on r8 was not
propagated there it will prune the walk entirely (stop walking
the entire program, not just the callee).  Since [6] was never walked
with r8 == 0, [7] will be considered dead and replaced with "goto -1"
causing hang at runtime.

This patch weaves the callee's explored states onto the callers
parentage chain.  Rough parentage for r8 would have looked like this
before:

[0] [1] [2] [3] [4] [5]   [10]      [11]      [6]      [7]
     |           |      ,---|----.    |        |        |
  sl0:         sl0:    / sl0:     \ sl0:      sl0:     sl0:
  fr0: r8 <-- fr0: r8<+--fr0: r8   `fr0: r8  ,fr0: r8<-fr0: r8
                       \ fr1: r8 <- fr1: r8 /
                        \__________________/

after:

[0] [1] [2] [3] [4] [5]   [10]      [11]      [6]      [7]
     |           |          |         |        |        |
   sl0:         sl0:      sl0:       sl0:      sl0:     sl0:
   fr0: r8 <-- fr0: r8 <- fr0: r8 <- fr0: r8 <-fr0: r8<-fr0: r8
                          fr1: r8 <- fr1: r8

Now the mark from instruction 6 will travel through callees states.

Note that we don't have to connect r0 because its overwritten by
callees state on return and r1 - r5 because those are not alive
any more once a call is made.

v2:
 - don't connect the callees registers twice (Alexei: suggestion & code)
 - add more details to the comment (Ed & Alexei)
v1: don't unnecessarily link caller saved regs (Jiong)

Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)")
Reported-by: David Beckett <david.beckett@netronome.com>
Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Reviewed-by: Jiong Wang <jiong.wang@netronome.com>
---
 kernel/bpf/verifier.c                       | 13 +++++++---
 tools/testing/selftests/bpf/test_verifier.c | 28 +++++++++++++++++++++
 2 files changed, 38 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index fc760d00a38c..51ba84d4d34a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5102,9 +5102,16 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 	}
 	new_sl->next = env->explored_states[insn_idx];
 	env->explored_states[insn_idx] = new_sl;
-	/* connect new state to parentage chain */
-	for (i = 0; i < BPF_REG_FP; i++)
-		cur_regs(env)[i].parent = &new->frame[new->curframe]->regs[i];
+	/* connect new state to parentage chain. Current frame needs all
+	 * registers connected. Only r6 - r9 of the callers are alive (pushed
+	 * to the stack implicitly by JITs) so in callers' frames connect just
+	 * r6 - r9 as an optimization. Callers will have r1 - r5 connected to
+	 * the state of the call instruction (with WRITTEN set), and r0 comes
+	 * from callee with its full parentage chain, anyway.
+	 */
+	for (j = 0; j <= cur->curframe; j++)
+		for (i = j < cur->curframe ? BPF_REG_6 : 0; i < BPF_REG_FP; i++)
+			cur->frame[j]->regs[i].parent = &new->frame[j]->regs[i];
 	/* clear write marks in current state: the writes we did are not writes
 	 * our child did, so they don't screen off its reads from us.
 	 * (There are no read marks in current state, because reads always mark
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 37583267bdbc..f8eac4a544f4 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -13915,6 +13915,34 @@ static struct bpf_test tests[] = {
 		.result_unpriv = REJECT,
 		.result = ACCEPT,
 	},
+	{
+		"calls: cross frame pruning",
+		.insns = {
+			/* r8 = !!random();
+			 * call pruner()
+			 * if (r8)
+			 *     do something bad;
+			 */
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
+				     BPF_FUNC_get_prandom_u32),
+			BPF_MOV64_IMM(BPF_REG_8, 0),
+			BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
+			BPF_MOV64_IMM(BPF_REG_8, 1),
+			BPF_MOV64_REG(BPF_REG_1, BPF_REG_8),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 4),
+			BPF_JMP_IMM(BPF_JEQ, BPF_REG_8, 1, 1),
+			BPF_LDX_MEM(BPF_B, BPF_REG_9, BPF_REG_1, 0),
+			BPF_MOV64_IMM(BPF_REG_0, 0),
+			BPF_EXIT_INSN(),
+			BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 0),
+			BPF_EXIT_INSN(),
+		},
+		.prog_type = BPF_PROG_TYPE_SOCKET_FILTER,
+		.errstr_unpriv = "function calls to other bpf functions are allowed for root only",
+		.result_unpriv = REJECT,
+		.errstr = "!read_ok",
+		.result = REJECT,
+	},
 };
 
 static int probe_filter_length(const struct bpf_insn *fp)
-- 
2.17.1

Re: [PATCH bpf v2] bpf: verifier: make sure callees don't prune with caller differences

[Edward Cree]

On 13/12/18 00:29, Jakub Kicinski wrote:
> Currently for liveness and state pruning the register parentage
> chains don't include states of the callee.  This makes some sense
> as the callee can't access those registers.  However, this means
> that READs done after the callee returns will not propagate into
> the states of the callee.  Callee will then perform pruning
> disregarding differences in caller state.
>
> Example:
>
>    0: (85) call bpf_user_rnd_u32
>    1: (b7) r8 = 0
>    2: (55) if r0 != 0x0 goto pc+1
>    3: (b7) r8 = 1
>    4: (bf) r1 = r8
>    5: (85) call pc+4
>    6: (15) if r8 == 0x1 goto pc+1
>    7: (05) *(u64 *)(r9 - 8) = r3
>    8: (b7) r0 = 0
>    9: (95) exit
>
>    10: (15) if r1 == 0x0 goto pc+0
>    11: (95) exit
>
> Here we acquire unknown state with call to get_random() [1].  Then
> we store this random state in r8 (either 0 or 1) [1 - 3], and make
> a call on line 5.  Callee does nothing but a trivial conditional
> jump (to create a pruning point).  Upon return caller checks the
> state of r8 and either performs an unsafe read or not.
>
> Verifier will first explore the path with r8 == 1, creating a pruning
> point at [11].  The parentage chain for r8 will include only callers
> states so once verifier reaches [6] it will mark liveness only on states
> in the caller, and not [11].  Now when verifier walks the paths with
> r8 == 0 it will reach [11] and since REG_LIVE_READ on r8 was not
> propagated there it will prune the walk entirely (stop walking
> the entire program, not just the callee).  Since [6] was never walked
> with r8 == 0, [7] will be considered dead and replaced with "goto -1"
> causing hang at runtime.
>
> This patch weaves the callee's explored states onto the callers
> parentage chain.  Rough parentage for r8 would have looked like this
> before:
>
> [0] [1] [2] [3] [4] [5]   [10]      [11]      [6]      [7]
>      |           |      ,---|----.    |        |        |
>   sl0:         sl0:    / sl0:     \ sl0:      sl0:     sl0:
>   fr0: r8 <-- fr0: r8<+--fr0: r8   `fr0: r8  ,fr0: r8<-fr0: r8
>                        \ fr1: r8 <- fr1: r8 /
>                         \__________________/
>
> after:
>
> [0] [1] [2] [3] [4] [5]   [10]      [11]      [6]      [7]
>      |           |          |         |        |        |
>    sl0:         sl0:      sl0:       sl0:      sl0:     sl0:
>    fr0: r8 <-- fr0: r8 <- fr0: r8 <- fr0: r8 <-fr0: r8<-fr0: r8
>                           fr1: r8 <- fr1: r8
>
> Now the mark from instruction 6 will travel through callees states.
>
> Note that we don't have to connect r0 because its overwritten by
> callees state on return and r1 - r5 because those are not alive
> any more once a call is made.
>
> v2:
>  - don't connect the callees registers twice (Alexei: suggestion & code)
>  - add more details to the comment (Ed & Alexei)
> v1: don't unnecessarily link caller saved regs (Jiong)
>
> Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)")
> Reported-by: David Beckett <david.beckett@netronome.com>
> Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
> Reviewed-by: Jiong Wang <jiong.wang@netronome.com>
> ---
Reviewed-by: Edward Cree <ecree@solarflare.com>

Re: [PATCH bpf v2] bpf: verifier: make sure callees don't prune with caller differences

[Alexei Starovoitov]

On Wed, Dec 12, 2018 at 04:29:07PM -0800, Jakub Kicinski wrote:
> Currently for liveness and state pruning the register parentage
> chains don't include states of the callee.  This makes some sense
> as the callee can't access those registers.  However, this means
> that READs done after the callee returns will not propagate into
> the states of the callee.  Callee will then perform pruning
> disregarding differences in caller state.
> 
> Example:
> 
>    0: (85) call bpf_user_rnd_u32
>    1: (b7) r8 = 0
>    2: (55) if r0 != 0x0 goto pc+1
>    3: (b7) r8 = 1
>    4: (bf) r1 = r8
>    5: (85) call pc+4
>    6: (15) if r8 == 0x1 goto pc+1
>    7: (05) *(u64 *)(r9 - 8) = r3
>    8: (b7) r0 = 0
>    9: (95) exit
> 
>    10: (15) if r1 == 0x0 goto pc+0
>    11: (95) exit
> 
> Here we acquire unknown state with call to get_random() [1].  Then
> we store this random state in r8 (either 0 or 1) [1 - 3], and make
> a call on line 5.  Callee does nothing but a trivial conditional
> jump (to create a pruning point).  Upon return caller checks the
> state of r8 and either performs an unsafe read or not.
> 
> Verifier will first explore the path with r8 == 1, creating a pruning
> point at [11].  The parentage chain for r8 will include only callers
> states so once verifier reaches [6] it will mark liveness only on states
> in the caller, and not [11].  Now when verifier walks the paths with
> r8 == 0 it will reach [11] and since REG_LIVE_READ on r8 was not
> propagated there it will prune the walk entirely (stop walking
> the entire program, not just the callee).  Since [6] was never walked
> with r8 == 0, [7] will be considered dead and replaced with "goto -1"
> causing hang at runtime.
> 
> This patch weaves the callee's explored states onto the callers
> parentage chain.  Rough parentage for r8 would have looked like this
> before:
> 
> [0] [1] [2] [3] [4] [5]   [10]      [11]      [6]      [7]
>      |           |      ,---|----.    |        |        |
>   sl0:         sl0:    / sl0:     \ sl0:      sl0:     sl0:
>   fr0: r8 <-- fr0: r8<+--fr0: r8   `fr0: r8  ,fr0: r8<-fr0: r8
>                        \ fr1: r8 <- fr1: r8 /
>                         \__________________/
> 
> after:
> 
> [0] [1] [2] [3] [4] [5]   [10]      [11]      [6]      [7]
>      |           |          |         |        |        |
>    sl0:         sl0:      sl0:       sl0:      sl0:     sl0:
>    fr0: r8 <-- fr0: r8 <- fr0: r8 <- fr0: r8 <-fr0: r8<-fr0: r8
>                           fr1: r8 <- fr1: r8
> 
> Now the mark from instruction 6 will travel through callees states.
> 
> Note that we don't have to connect r0 because its overwritten by
> callees state on return and r1 - r5 because those are not alive
> any more once a call is made.
> 
> v2:
>  - don't connect the callees registers twice (Alexei: suggestion & code)
>  - add more details to the comment (Ed & Alexei)
> v1: don't unnecessarily link caller saved regs (Jiong)
> 
> Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)")
> Reported-by: David Beckett <david.beckett@netronome.com>
> Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
> Reviewed-by: Jiong Wang <jiong.wang@netronome.com>

Applied, Thanks