[PATCH bpf 0/2] fix map_lookup_elem return value for queue/stack map

[PATCH bpf 0/2] fix map_lookup_elem return value for queue/stack map

[Prashant Bhole]

This set fixes map_lookup_elem return value for queue/stack map.
Also adds verifier tests to check whether verifier prevents lookup on
these maps.

Note that patch 2 isn't dependant on patch 1. The verifier prevents
lookup on queue/stack map because key size is zero.

Prashant Bhole (2):
  bpf: queue/stack map, fix return value of map_lookup_elem
  bpf: test_verifier, test for lookup on queue/stack maps

 kernel/bpf/queue_stack_maps.c               |  2 +-
 tools/testing/selftests/bpf/test_verifier.c | 52 +++++++++++++++++++++
 2 files changed, 53 insertions(+), 1 deletion(-)

-- 
2.17.2

[PATCH bpf 1/2] bpf: queue/stack map, fix return value of map_lookup_elem

[Prashant Bhole]

Since commit 509db2833e0d ("bpf: error handling when map_lookup_elem
isn't supported") when map lookup isn't supported, the map_lookup_elem
function should return ERR_PTR(-EOPNOTSUPP).

Fixes: f1a2e44a3aec ("bpf: add queue and stack maps")
Signed-off-by: Prashant Bhole <bhole_prashant_q7@lab.ntt.co.jp>
---
 kernel/bpf/queue_stack_maps.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/bpf/queue_stack_maps.c b/kernel/bpf/queue_stack_maps.c
index b384ea9f3254..8fd19b06da66 100644
--- a/kernel/bpf/queue_stack_maps.c
+++ b/kernel/bpf/queue_stack_maps.c
@@ -240,7 +240,7 @@ static int queue_stack_map_push_elem(struct bpf_map *map, void *value,
 /* Called from syscall or from eBPF program */
 static void *queue_stack_map_lookup_elem(struct bpf_map *map, void *key)
 {
-	return NULL;
+	return ERR_PTR(-EOPNOTSUPP);
 }
 
 /* Called from syscall or from eBPF program */
-- 
2.17.2

[PATCH bpf 2/2] bpf: test_verifier, test for lookup on queue/stack maps

[Prashant Bhole]

This patch adds tests to check whether bpf verifier prevents lookup
on queue/stack maps

Signed-off-by: Prashant Bhole <bhole_prashant_q7@lab.ntt.co.jp>
---
 tools/testing/selftests/bpf/test_verifier.c | 52 +++++++++++++++++++++
 1 file changed, 52 insertions(+)

diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 550b7e46bf4a..becd9f4f3980 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -74,6 +74,8 @@ struct bpf_test {
 	int fixup_map_in_map[MAX_FIXUPS];
 	int fixup_cgroup_storage[MAX_FIXUPS];
 	int fixup_percpu_cgroup_storage[MAX_FIXUPS];
+	int fixup_map_queue[MAX_FIXUPS];
+	int fixup_map_stack[MAX_FIXUPS];
 	const char *errstr;
 	const char *errstr_unpriv;
 	uint32_t retval, retval_unpriv;
@@ -4611,6 +4613,38 @@ static struct bpf_test tests[] = {
 		.errstr = "cannot pass map_type 7 into func bpf_map_lookup_elem",
 		.prog_type = BPF_PROG_TYPE_PERF_EVENT,
 	},
+	{
+		"prevent map lookup in queue map",
+		.insns = {
+			BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+			BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+			BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+			BPF_LD_MAP_FD(BPF_REG_1, 0),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
+				     BPF_FUNC_map_lookup_elem),
+			BPF_EXIT_INSN(),
+		},
+		.fixup_map_queue = { 3 },
+		.result = REJECT,
+		.errstr = "invalid stack type R2 off=-8 access_size=0",
+		.prog_type = BPF_PROG_TYPE_XDP,
+	},
+	{
+		"prevent map lookup in stack map",
+		.insns = {
+			BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+			BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+			BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+			BPF_LD_MAP_FD(BPF_REG_1, 0),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
+				     BPF_FUNC_map_lookup_elem),
+			BPF_EXIT_INSN(),
+		},
+		.fixup_map_stack = { 3 },
+		.result = REJECT,
+		.errstr = "invalid stack type R2 off=-8 access_size=0",
+		.prog_type = BPF_PROG_TYPE_XDP,
+	},
 	{
 		"prevent map lookup in prog array",
 		.insns = {
@@ -14048,6 +14082,8 @@ static void do_test_fixup(struct bpf_test *test, enum bpf_map_type prog_type,
 	int *fixup_map_sockhash = test->fixup_map_sockhash;
 	int *fixup_map_xskmap = test->fixup_map_xskmap;
 	int *fixup_map_stacktrace = test->fixup_map_stacktrace;
+	int *fixup_map_queue = test->fixup_map_queue;
+	int *fixup_map_stack = test->fixup_map_stack;
 	int *fixup_prog1 = test->fixup_prog1;
 	int *fixup_prog2 = test->fixup_prog2;
 	int *fixup_map_in_map = test->fixup_map_in_map;
@@ -14168,6 +14204,22 @@ static void do_test_fixup(struct bpf_test *test, enum bpf_map_type prog_type,
 			fixup_map_stacktrace++;
 		} while (fixup_map_stacktrace);
 	}
+	if (*fixup_map_queue) {
+		map_fds[13] = create_map(BPF_MAP_TYPE_QUEUE, 0,
+					 sizeof(u32), 1);
+		do {
+			prog[*fixup_map_queue].imm = map_fds[13];
+			fixup_map_queue++;
+		} while (*fixup_map_queue);
+	}
+	if (*fixup_map_stack) {
+		map_fds[14] = create_map(BPF_MAP_TYPE_STACK, 0,
+					 sizeof(u32), 1);
+		do {
+			prog[*fixup_map_stack].imm = map_fds[14];
+			fixup_map_stack++;
+		} while (*fixup_map_stack);
+	}
 }
 
 static int set_admin(bool admin)
-- 
2.17.2

Re: [PATCH bpf 2/2] bpf: test_verifier, test for lookup on queue/stack maps

[Daniel Borkmann]

On 11/28/2018 08:51 AM, Prashant Bhole wrote:
> This patch adds tests to check whether bpf verifier prevents lookup
> on queue/stack maps
> 
> Signed-off-by: Prashant Bhole <bhole_prashant_q7@lab.ntt.co.jp>
> ---
>  tools/testing/selftests/bpf/test_verifier.c | 52 +++++++++++++++++++++
>  1 file changed, 52 insertions(+)
> 
> diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
> index 550b7e46bf4a..becd9f4f3980 100644
> --- a/tools/testing/selftests/bpf/test_verifier.c
> +++ b/tools/testing/selftests/bpf/test_verifier.c
> @@ -74,6 +74,8 @@ struct bpf_test {
>  	int fixup_map_in_map[MAX_FIXUPS];
>  	int fixup_cgroup_storage[MAX_FIXUPS];
>  	int fixup_percpu_cgroup_storage[MAX_FIXUPS];
> +	int fixup_map_queue[MAX_FIXUPS];
> +	int fixup_map_stack[MAX_FIXUPS];
>  	const char *errstr;
>  	const char *errstr_unpriv;
>  	uint32_t retval, retval_unpriv;
> @@ -4611,6 +4613,38 @@ static struct bpf_test tests[] = {
>  		.errstr = "cannot pass map_type 7 into func bpf_map_lookup_elem",
>  		.prog_type = BPF_PROG_TYPE_PERF_EVENT,
>  	},
> +	{
> +		"prevent map lookup in queue map",
> +		.insns = {
> +			BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
> +			BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
> +			BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
> +			BPF_LD_MAP_FD(BPF_REG_1, 0),
> +			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
> +				     BPF_FUNC_map_lookup_elem),
> +			BPF_EXIT_INSN(),
> +		},
> +		.fixup_map_queue = { 3 },
> +		.result = REJECT,
> +		.errstr = "invalid stack type R2 off=-8 access_size=0",
> +		.prog_type = BPF_PROG_TYPE_XDP,

Hmm, the approach in patch 1 is very fragile, and we're lucky in this case
that the verifier bailed out with 'invalid stack type R2 off=-8 access_size=0'
because of key size being zero. If this would have not been the case then
the added ERR_PTR(-EOPNOTSUPP) would basically be seen as a valid pointer and
the program could read/write into it. Instead, this needs to be prevented much
earlier like check_map_func_compatibility(), and I would like to have a split
on these approaches to make verifier more robust. While you want ERR_PTR(-EOPNOTSUPP)
for user space syscall side, the BPF prog should only ever see (if anything)
a NULL here, because this is what the verifier matches later on to set the map
value_or_null pointer to a map value pointer.

> +	},
> +	{
> +		"prevent map lookup in stack map",
> +		.insns = {
> +			BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
> +			BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
> +			BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
> +			BPF_LD_MAP_FD(BPF_REG_1, 0),
> +			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
> +				     BPF_FUNC_map_lookup_elem),
> +			BPF_EXIT_INSN(),
> +		},
> +		.fixup_map_stack = { 3 },
> +		.result = REJECT,
> +		.errstr = "invalid stack type R2 off=-8 access_size=0",
> +		.prog_type = BPF_PROG_TYPE_XDP,
> +	},
>  	{
>  		"prevent map lookup in prog array",
>  		.insns = {
> @@ -14048,6 +14082,8 @@ static void do_test_fixup(struct bpf_test *test, enum bpf_map_type prog_type,
>  	int *fixup_map_sockhash = test->fixup_map_sockhash;
>  	int *fixup_map_xskmap = test->fixup_map_xskmap;
>  	int *fixup_map_stacktrace = test->fixup_map_stacktrace;
> +	int *fixup_map_queue = test->fixup_map_queue;
> +	int *fixup_map_stack = test->fixup_map_stack;
>  	int *fixup_prog1 = test->fixup_prog1;
>  	int *fixup_prog2 = test->fixup_prog2;
>  	int *fixup_map_in_map = test->fixup_map_in_map;
> @@ -14168,6 +14204,22 @@ static void do_test_fixup(struct bpf_test *test, enum bpf_map_type prog_type,
>  			fixup_map_stacktrace++;
>  		} while (fixup_map_stacktrace);
>  	}
> +	if (*fixup_map_queue) {
> +		map_fds[13] = create_map(BPF_MAP_TYPE_QUEUE, 0,
> +					 sizeof(u32), 1);
> +		do {
> +			prog[*fixup_map_queue].imm = map_fds[13];
> +			fixup_map_queue++;
> +		} while (*fixup_map_queue);
> +	}
> +	if (*fixup_map_stack) {
> +		map_fds[14] = create_map(BPF_MAP_TYPE_STACK, 0,
> +					 sizeof(u32), 1);
> +		do {
> +			prog[*fixup_map_stack].imm = map_fds[14];
> +			fixup_map_stack++;
> +		} while (*fixup_map_stack);
> +	}
>  }
>  
>  static int set_admin(bool admin)
> 

Re: [PATCH bpf 2/2] bpf: test_verifier, test for lookup on queue/stack maps

[Mauricio Vasquez]

On 11/28/18 3:45 AM, Daniel Borkmann wrote:
> On 11/28/2018 08:51 AM, Prashant Bhole wrote:
>> This patch adds tests to check whether bpf verifier prevents lookup
>> on queue/stack maps
>>
>> Signed-off-by: Prashant Bhole <bhole_prashant_q7@lab.ntt.co.jp>
>> ---
>>   tools/testing/selftests/bpf/test_verifier.c | 52 +++++++++++++++++++++
>>   1 file changed, 52 insertions(+)
>>
>> diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
>> index 550b7e46bf4a..becd9f4f3980 100644
>> --- a/tools/testing/selftests/bpf/test_verifier.c
>> +++ b/tools/testing/selftests/bpf/test_verifier.c
>> @@ -74,6 +74,8 @@ struct bpf_test {
>>   	int fixup_map_in_map[MAX_FIXUPS];
>>   	int fixup_cgroup_storage[MAX_FIXUPS];
>>   	int fixup_percpu_cgroup_storage[MAX_FIXUPS];
>> +	int fixup_map_queue[MAX_FIXUPS];
>> +	int fixup_map_stack[MAX_FIXUPS];
>>   	const char *errstr;
>>   	const char *errstr_unpriv;
>>   	uint32_t retval, retval_unpriv;
>> @@ -4611,6 +4613,38 @@ static struct bpf_test tests[] = {
>>   		.errstr = "cannot pass map_type 7 into func bpf_map_lookup_elem",
>>   		.prog_type = BPF_PROG_TYPE_PERF_EVENT,
>>   	},
>> +	{
>> +		"prevent map lookup in queue map",
>> +		.insns = {
>> +			BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
>> +			BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
>> +			BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
>> +			BPF_LD_MAP_FD(BPF_REG_1, 0),
>> +			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
>> +				     BPF_FUNC_map_lookup_elem),
>> +			BPF_EXIT_INSN(),
>> +		},
>> +		.fixup_map_queue = { 3 },
>> +		.result = REJECT,
>> +		.errstr = "invalid stack type R2 off=-8 access_size=0",
>> +		.prog_type = BPF_PROG_TYPE_XDP,
> Hmm, the approach in patch 1 is very fragile, and we're lucky in this case
> that the verifier bailed out with 'invalid stack type R2 off=-8 access_size=0'
> because of key size being zero. If this would have not been the case then
> the added ERR_PTR(-EOPNOTSUPP) would basically be seen as a valid pointer and
> the program could read/write into it. Instead, this needs to be prevented much
> earlier like check_map_func_compatibility(),

Actually it is prevented in check_map_func_compatibility(), but stack 
boundary check is done before in the verifier.

> and I would like to have a split
> on these approaches to make verifier more robust. While you want ERR_PTR(-EOPNOTSUPP)
> for user space syscall side,

In the case of QUEUE and STACK maps this is not relevant because the 
lookup syscall is mapped into peek operation.

In fact queue_stack_map_lookup_elem() & queue_stack_map_update_elem() 
should be never called, I think we can remove them safely.

Mauricio.

> the BPF prog should only ever see (if anything)
> a NULL here, because this is what the verifier matches later on to set the map
> value_or_null pointer to a map value pointer.
>
>> +	},
>> +	{
>> +		"prevent map lookup in stack map",
>> +		.insns = {
>> +			BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
>> +			BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
>> +			BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
>> +			BPF_LD_MAP_FD(BPF_REG_1, 0),
>> +			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
>> +				     BPF_FUNC_map_lookup_elem),
>> +			BPF_EXIT_INSN(),
>> +		},
>> +		.fixup_map_stack = { 3 },
>> +		.result = REJECT,
>> +		.errstr = "invalid stack type R2 off=-8 access_size=0",
>> +		.prog_type = BPF_PROG_TYPE_XDP,
>> +	},
>>   	{
>>   		"prevent map lookup in prog array",
>>   		.insns = {
>> @@ -14048,6 +14082,8 @@ static void do_test_fixup(struct bpf_test *test, enum bpf_map_type prog_type,
>>   	int *fixup_map_sockhash = test->fixup_map_sockhash;
>>   	int *fixup_map_xskmap = test->fixup_map_xskmap;
>>   	int *fixup_map_stacktrace = test->fixup_map_stacktrace;
>> +	int *fixup_map_queue = test->fixup_map_queue;
>> +	int *fixup_map_stack = test->fixup_map_stack;
>>   	int *fixup_prog1 = test->fixup_prog1;
>>   	int *fixup_prog2 = test->fixup_prog2;
>>   	int *fixup_map_in_map = test->fixup_map_in_map;
>> @@ -14168,6 +14204,22 @@ static void do_test_fixup(struct bpf_test *test, enum bpf_map_type prog_type,
>>   			fixup_map_stacktrace++;
>>   		} while (fixup_map_stacktrace);
>>   	}
>> +	if (*fixup_map_queue) {
>> +		map_fds[13] = create_map(BPF_MAP_TYPE_QUEUE, 0,
>> +					 sizeof(u32), 1);
>> +		do {
>> +			prog[*fixup_map_queue].imm = map_fds[13];
>> +			fixup_map_queue++;
>> +		} while (*fixup_map_queue);
>> +	}
>> +	if (*fixup_map_stack) {
>> +		map_fds[14] = create_map(BPF_MAP_TYPE_STACK, 0,
>> +					 sizeof(u32), 1);
>> +		do {
>> +			prog[*fixup_map_stack].imm = map_fds[14];
>> +			fixup_map_stack++;
>> +		} while (*fixup_map_stack);
>> +	}
>>   }
>>   
>>   static int set_admin(bool admin)
>>
>

Re: [PATCH bpf 2/2] bpf: test_verifier, test for lookup on queue/stack maps

[Prashant Bhole]

On 11/28/2018 10:06 PM, Mauricio Vasquez wrote:
> 
> On 11/28/18 3:45 AM, Daniel Borkmann wrote:
>> On 11/28/2018 08:51 AM, Prashant Bhole wrote:
>>> This patch adds tests to check whether bpf verifier prevents lookup
>>> on queue/stack maps
>>>
>>> Signed-off-by: Prashant Bhole <bhole_prashant_q7@lab.ntt.co.jp>
>>> ---
>>>   tools/testing/selftests/bpf/test_verifier.c | 52 +++++++++++++++++++++
>>>   1 file changed, 52 insertions(+)
>>>
>>> diff --git a/tools/testing/selftests/bpf/test_verifier.c 
>>> b/tools/testing/selftests/bpf/test_verifier.c
>>> index 550b7e46bf4a..becd9f4f3980 100644
>>> --- a/tools/testing/selftests/bpf/test_verifier.c
>>> +++ b/tools/testing/selftests/bpf/test_verifier.c
>>> @@ -74,6 +74,8 @@ struct bpf_test {
>>>       int fixup_map_in_map[MAX_FIXUPS];
>>>       int fixup_cgroup_storage[MAX_FIXUPS];
>>>       int fixup_percpu_cgroup_storage[MAX_FIXUPS];
>>> +    int fixup_map_queue[MAX_FIXUPS];
>>> +    int fixup_map_stack[MAX_FIXUPS];
>>>       const char *errstr;
>>>       const char *errstr_unpriv;
>>>       uint32_t retval, retval_unpriv;
>>> @@ -4611,6 +4613,38 @@ static struct bpf_test tests[] = {
>>>           .errstr = "cannot pass map_type 7 into func 
>>> bpf_map_lookup_elem",
>>>           .prog_type = BPF_PROG_TYPE_PERF_EVENT,
>>>       },
>>> +    {
>>> +        "prevent map lookup in queue map",
>>> +        .insns = {
>>> +            BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
>>> +            BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
>>> +            BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
>>> +            BPF_LD_MAP_FD(BPF_REG_1, 0),
>>> +            BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
>>> +                     BPF_FUNC_map_lookup_elem),
>>> +            BPF_EXIT_INSN(),
>>> +        },
>>> +        .fixup_map_queue = { 3 },
>>> +        .result = REJECT,
>>> +        .errstr = "invalid stack type R2 off=-8 access_size=0",
>>> +        .prog_type = BPF_PROG_TYPE_XDP,
>> Hmm, the approach in patch 1 is very fragile, and we're lucky in this 
>> case
>> that the verifier bailed out with 'invalid stack type R2 off=-8 
>> access_size=0'
>> because of key size being zero. If this would have not been the case then
>> the added ERR_PTR(-EOPNOTSUPP) would basically be seen as a valid 
>> pointer and
>> the program could read/write into it. Instead, this needs to be 
>> prevented much
>> earlier like check_map_func_compatibility(),
> 
> Actually it is prevented in check_map_func_compatibility(), but stack 
> boundary check is done before in the verifier.
> 
>> and I would like to have a split
>> on these approaches to make verifier more robust. While you want 
>> ERR_PTR(-EOPNOTSUPP)
>> for user space syscall side,
> 
> In the case of QUEUE and STACK maps this is not relevant because the 
> lookup syscall is mapped into peek operation.
> 
> In fact queue_stack_map_lookup_elem() & queue_stack_map_update_elem() 
> should be never called, I think we can remove them safely.

Got it. Shall we keep these verifier tests (patch 2)?

Thanks,
Prashant