[PATCH net] bpf: fix states equal logic for varlen access

[PATCH net] bpf: fix states equal logic for varlen access

[Josef Bacik]

If we have a branch that looks something like this

int foo = map->value;
if (condition) {
  foo += blah;
} else {
  foo = bar;
}
map->array[foo] = baz;

We will incorrectly assume that the !condition branch is equal to the condition
branch as the register for foo will be UNKNOWN_VALUE in both cases.  We need to
adjust this logic to only do this if we didn't do a varlen access after we
processed the !condition branch, otherwise we have different ranges and need to
check the other branch as well.

Signed-off-by: Josef Bacik <jbacik@fb.com>
---
 kernel/bpf/verifier.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 89f787c..2c8a688 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2478,6 +2478,7 @@ static bool states_equal(struct bpf_verifier_env *env,
 {
 	struct bpf_reg_state *rold, *rcur;
 	int i;
+	bool map_access = env->varlen_map_value_access;
 
 	for (i = 0; i < MAX_BPF_REG; i++) {
 		rold = &old->regs[i];
@@ -2489,12 +2490,17 @@ static bool states_equal(struct bpf_verifier_env *env,
 		/* If the ranges were not the same, but everything else was and
 		 * we didn't do a variable access into a map then we are a-ok.
 		 */
-		if (!env->varlen_map_value_access &&
+		if (!map_access &&
 		    rold->type == rcur->type && rold->imm == rcur->imm)
 			continue;
 
+		/* If we didn't map access then again we don't care about the
+		 * mismatched range values and it's ok if our old type was
+		 * UNKNOWN and we didn't go to a NOT_INIT'ed reg.
+		 */
 		if (rold->type == NOT_INIT ||
-		    (rold->type == UNKNOWN_VALUE && rcur->type != NOT_INIT))
+		    (!map_access && (rold->type == UNKNOWN_VALUE &&
+				     rcur->type != NOT_INIT)))
 			continue;
 
 		if (rold->type == PTR_TO_PACKET && rcur->type == PTR_TO_PACKET &&
-- 
2.7.4

Re: [PATCH net] bpf: fix states equal logic for varlen access

[Alexei Starovoitov]

On Mon, Nov 28, 2016 at 02:44:10PM -0500, Josef Bacik wrote:
> If we have a branch that looks something like this
> 
> int foo = map->value;
> if (condition) {
>   foo += blah;
> } else {
>   foo = bar;
> }
> map->array[foo] = baz;
> 
> We will incorrectly assume that the !condition branch is equal to the condition
> branch as the register for foo will be UNKNOWN_VALUE in both cases.  We need to
> adjust this logic to only do this if we didn't do a varlen access after we
> processed the !condition branch, otherwise we have different ranges and need to
> check the other branch as well.
> 
> Signed-off-by: Josef Bacik <jbacik@fb.com>
> ---
>  kernel/bpf/verifier.c | 10 ++++++++--
>  1 file changed, 8 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 89f787c..2c8a688 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2478,6 +2478,7 @@ static bool states_equal(struct bpf_verifier_env *env,
>  {
>  	struct bpf_reg_state *rold, *rcur;
>  	int i;
> +	bool map_access = env->varlen_map_value_access;

that's a bit misleading name for the variable.
Pls call it varlen_map_access.

>  	for (i = 0; i < MAX_BPF_REG; i++) {
>  		rold = &old->regs[i];
> @@ -2489,12 +2490,17 @@ static bool states_equal(struct bpf_verifier_env *env,
>  		/* If the ranges were not the same, but everything else was and
>  		 * we didn't do a variable access into a map then we are a-ok.
>  		 */
> -		if (!env->varlen_map_value_access &&
> +		if (!map_access &&
>  		    rold->type == rcur->type && rold->imm == rcur->imm)

just noticed that this one is missing comparing rold->id == rcur->id

>  			continue;
>  
> +		/* If we didn't map access then again we don't care about the
> +		 * mismatched range values and it's ok if our old type was
> +		 * UNKNOWN and we didn't go to a NOT_INIT'ed reg.
> +		 */
>  		if (rold->type == NOT_INIT ||
> -		    (rold->type == UNKNOWN_VALUE && rcur->type != NOT_INIT))
> +		    (!map_access && (rold->type == UNKNOWN_VALUE &&
> +				     rcur->type != NOT_INIT)))

please drop unnecessary ( )

Re: [PATCH net] bpf: fix states equal logic for varlen access

[Daniel Borkmann]

On 11/29/2016 04:04 AM, Alexei Starovoitov wrote:
> On Mon, Nov 28, 2016 at 02:44:10PM -0500, Josef Bacik wrote:
>> If we have a branch that looks something like this
>>
>> int foo = map->value;
>> if (condition) {
>>    foo += blah;
>> } else {
>>    foo = bar;
>> }
>> map->array[foo] = baz;
>>
>> We will incorrectly assume that the !condition branch is equal to the condition
>> branch as the register for foo will be UNKNOWN_VALUE in both cases.  We need to
>> adjust this logic to only do this if we didn't do a varlen access after we
>> processed the !condition branch, otherwise we have different ranges and need to
>> check the other branch as well.

Fixes: 484611357c19 ("bpf: allow access into map value arrays")
Reported-by: Jann Horn <jannh@google.com>

>> Signed-off-by: Josef Bacik <jbacik@fb.com>

Please also add a test case to tools/testing/selftests/bpf/test_verifier.c for
net-next tree, so we can make sure we catch this in future. Test could look
like that after this fix it fails by the verifier, but before it doesn't due
to false state pruning.

>>   kernel/bpf/verifier.c | 10 ++++++++--
>>   1 file changed, 8 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 89f787c..2c8a688 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -2478,6 +2478,7 @@ static bool states_equal(struct bpf_verifier_env *env,
>>   {
>>   	struct bpf_reg_state *rold, *rcur;
>>   	int i;
>> +	bool map_access = env->varlen_map_value_access;
>
> that's a bit misleading name for the variable.
> Pls call it varlen_map_access.

Nit: while at it, please also move it up as first var (netdev has reverse
xmas tree style).

>>   	for (i = 0; i < MAX_BPF_REG; i++) {
>>   		rold = &old->regs[i];
>> @@ -2489,12 +2490,17 @@ static bool states_equal(struct bpf_verifier_env *env,
>>   		/* If the ranges were not the same, but everything else was and
>>   		 * we didn't do a variable access into a map then we are a-ok.
>>   		 */
>> -		if (!env->varlen_map_value_access &&
>> +		if (!map_access &&
>>   		    rold->type == rcur->type && rold->imm == rcur->imm)
>
> just noticed that this one is missing comparing rold->id == rcur->id
>
>>   			continue;
>>
>> +		/* If we didn't map access then again we don't care about the
>> +		 * mismatched range values and it's ok if our old type was
>> +		 * UNKNOWN and we didn't go to a NOT_INIT'ed reg.
>> +		 */
>>   		if (rold->type == NOT_INIT ||
>> -		    (rold->type == UNKNOWN_VALUE && rcur->type != NOT_INIT))
>> +		    (!map_access && (rold->type == UNKNOWN_VALUE &&
>> +				     rcur->type != NOT_INIT)))
>
> please drop unnecessary ( )

Re: [PATCH net] bpf: fix states equal logic for varlen access

[Josef Bacik]

On 11/28/2016 10:04 PM, Alexei Starovoitov wrote:
> On Mon, Nov 28, 2016 at 02:44:10PM -0500, Josef Bacik wrote:
>> If we have a branch that looks something like this
>>
>> int foo = map->value;
>> if (condition) {
>>   foo += blah;
>> } else {
>>   foo = bar;
>> }
>> map->array[foo] = baz;
>>
>> We will incorrectly assume that the !condition branch is equal to the condition
>> branch as the register for foo will be UNKNOWN_VALUE in both cases.  We need to
>> adjust this logic to only do this if we didn't do a varlen access after we
>> processed the !condition branch, otherwise we have different ranges and need to
>> check the other branch as well.
>>
>> Signed-off-by: Josef Bacik <jbacik@fb.com>
>> ---
>>  kernel/bpf/verifier.c | 10 ++++++++--
>>  1 file changed, 8 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 89f787c..2c8a688 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -2478,6 +2478,7 @@ static bool states_equal(struct bpf_verifier_env *env,
>>  {
>>  	struct bpf_reg_state *rold, *rcur;
>>  	int i;
>> +	bool map_access = env->varlen_map_value_access;
>
> that's a bit misleading name for the variable.
> Pls call it varlen_map_access.
>
>>  	for (i = 0; i < MAX_BPF_REG; i++) {
>>  		rold = &old->regs[i];
>> @@ -2489,12 +2490,17 @@ static bool states_equal(struct bpf_verifier_env *env,
>>  		/* If the ranges were not the same, but everything else was and
>>  		 * we didn't do a variable access into a map then we are a-ok.
>>  		 */
>> -		if (!env->varlen_map_value_access &&
>> +		if (!map_access &&
>>  		    rold->type == rcur->type && rold->imm == rcur->imm)
>
> just noticed that this one is missing comparing rold->id == rcur->id
>

Do you want me to fix that here?  I'll fix up the rest of the stuff, and Daniels 
things as well.  Thanks,

Josef

Re: [PATCH net] bpf: fix states equal logic for varlen access

[Alexei Starovoitov]

On Tue, Nov 29, 2016 at 09:45:33AM -0500, Josef Bacik wrote:
> On 11/28/2016 10:04 PM, Alexei Starovoitov wrote:
> >On Mon, Nov 28, 2016 at 02:44:10PM -0500, Josef Bacik wrote:
> >>If we have a branch that looks something like this
> >>
> >>int foo = map->value;
> >>if (condition) {
> >>  foo += blah;
> >>} else {
> >>  foo = bar;
> >>}
> >>map->array[foo] = baz;
> >>
> >>We will incorrectly assume that the !condition branch is equal to the condition
> >>branch as the register for foo will be UNKNOWN_VALUE in both cases.  We need to
> >>adjust this logic to only do this if we didn't do a varlen access after we
> >>processed the !condition branch, otherwise we have different ranges and need to
> >>check the other branch as well.
> >>
> >>Signed-off-by: Josef Bacik <jbacik@fb.com>
> >>---
> >> kernel/bpf/verifier.c | 10 ++++++++--
> >> 1 file changed, 8 insertions(+), 2 deletions(-)
> >>
> >>diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >>index 89f787c..2c8a688 100644
> >>--- a/kernel/bpf/verifier.c
> >>+++ b/kernel/bpf/verifier.c
> >>@@ -2478,6 +2478,7 @@ static bool states_equal(struct bpf_verifier_env *env,
> >> {
> >> 	struct bpf_reg_state *rold, *rcur;
> >> 	int i;
> >>+	bool map_access = env->varlen_map_value_access;
> >
> >that's a bit misleading name for the variable.
> >Pls call it varlen_map_access.
> >
> >> 	for (i = 0; i < MAX_BPF_REG; i++) {
> >> 		rold = &old->regs[i];
> >>@@ -2489,12 +2490,17 @@ static bool states_equal(struct bpf_verifier_env *env,
> >> 		/* If the ranges were not the same, but everything else was and
> >> 		 * we didn't do a variable access into a map then we are a-ok.
> >> 		 */
> >>-		if (!env->varlen_map_value_access &&
> >>+		if (!map_access &&
> >> 		    rold->type == rcur->type && rold->imm == rcur->imm)
> >
> >just noticed that this one is missing comparing rold->id == rcur->id
> >
> 
> Do you want me to fix that here?  I'll fix up the rest of the stuff, and
> Daniels things as well.  Thanks,

Nevermind. Comparing 'id' is not needed in net, only in net-next.