linux-kernel - Re: [PATCH v2 bpf-next 2/2] selftests/bpf: add inline assembly helpers to access array elements

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Thu, 4 Jan 2024 09:31:52 -0800
From: Yonghong Song <yonghong.song@...ux.dev>
To: Jiri Olsa <olsajiri@...il.com>, Barret Rhoden <brho@...gle.com>,
 Eddy Z <eddyz87@...il.com>
Cc: Andrii Nakryiko <andrii@...nel.org>, Alexei Starovoitov <ast@...nel.org>,
 Daniel Borkmann <daniel@...earbox.net>, Song Liu <song@...nel.org>,
 mattbobrowski@...gle.com, bpf@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2 bpf-next 2/2] selftests/bpf: add inline assembly
 helpers to access array elements

cc Eduard.

On 1/4/24 5:43 AM, Jiri Olsa wrote:
> On Wed, Jan 03, 2024 at 01:53:59PM -0500, Barret Rhoden wrote:
>
> SNIP
>
>> +
>> +
>> +/* Test that attempting to load a bad program fails. */
>> +#define test_bad(PROG) ({						\
>> +	struct array_elem_test *skel;					\
>> +	int err;							\
>> +	skel = array_elem_test__open();					\
>> +	if (!ASSERT_OK_PTR(skel, "array_elem_test open"))		\
>> +		return;							\
>> +	bpf_program__set_autoload(skel->progs.x_bad_ ## PROG, true); 	\
>> +	err = array_elem_test__load(skel);				\
>> +	ASSERT_ERR(err, "array_elem_test load " # PROG);		\
>> +	array_elem_test__destroy(skel);					\
>> +})
> I wonder we could use the existing RUN_TESTS macro and use tags
> in programs like we do for example in progs/test_global_func1.c:
>
>    SEC("tc")
>    __failure __msg("combined stack size of 4 calls is 544")
>    int global_func1(struct __sk_buff *skb)
>
> jirka
>
>
>> +
>> +void test_test_array_elem(void)
>> +{
>> +	if (test__start_subtest("array_elem_access_all"))
>> +		test_access_all();
>> +	if (test__start_subtest("array_elem_oob_access"))
>> +		test_oob_access();
>> +	if (test__start_subtest("array_elem_access_array_map_infer_sz"))
>> +		test_access_array_map_infer_sz();
>> +	if (test__start_subtest("array_elem_bad_map_array_access"))
>> +		test_bad(map_array_access);
>> +	if (test__start_subtest("array_elem_bad_bss_array_access"))
>> +		test_bad(bss_array_access);
>> +
[...]
>> diff --git a/tools/testing/selftests/bpf/progs/bpf_misc.h b/tools/testing/selftests/bpf/progs/bpf_misc.h
>> index 2fd59970c43a..002bab44cde2 100644
>> --- a/tools/testing/selftests/bpf/progs/bpf_misc.h
>> +++ b/tools/testing/selftests/bpf/progs/bpf_misc.h
>> @@ -135,4 +135,47 @@
>>   /* make it look to compiler like value is read and written */
>>   #define __sink(expr) asm volatile("" : "+g"(expr))
>>   
>> +/*
>> + * Access an array element within a bound, such that the verifier knows the
>> + * access is safe.
>> + *
>> + * This macro asm is the equivalent of:
>> + *
>> + *	if (!arr)
>> + *		return NULL;
>> + *	if (idx >= arr_sz)
>> + *		return NULL;
>> + *	return &arr[idx];
>> + *
>> + * The index (___idx below) needs to be a u64, at least for certain versions of
>> + * the BPF ISA, since there aren't u32 conditional jumps.
>> + */
>> +#define bpf_array_elem(arr, arr_sz, idx) ({				\
>> +	typeof(&(arr)[0]) ___arr = arr;					\
>> +	__u64 ___idx = idx;						\
>> +	if (___arr) {							\
>> +		asm volatile("if %[__idx] >= %[__bound] goto 1f;	\
>> +			      %[__idx] *= %[__size];		\
>> +			      %[__arr] += %[__idx];		\
>> +			      goto 2f;				\
>> +			      1:;				\
>> +			      %[__arr] = 0;			\
>> +			      2:				\
>> +			      "						\
>> +			     : [__arr]"+r"(___arr), [__idx]"+r"(___idx)	\
>> +			     : [__bound]"r"((arr_sz)),		        \
>> +			       [__size]"i"(sizeof(typeof((arr)[0])))	\
>> +			     : "cc");					\
>> +	}								\
>> +	___arr;								\
>> +})

The LLVM bpf backend has made some improvement to handle the case like
   r1 = ...
   r2 = r1 + 1
   if (r2 < num) ...
   using r1
by preventing generating the above code pattern.

The implementation is a pattern matching style so surely it won't be
able to cover all cases.

Do you have specific examples which has verification failure due to
false array out of bound access?

>> +
>> +/*
>> + * Convenience wrapper for bpf_array_elem(), where we compute the size of the
>> + * array.  Be sure to use an actual array, and not a pointer, just like with the
>> + * ARRAY_SIZE macro.
>> + */
>> +#define bpf_array_sz_elem(arr, idx) \
>> +	bpf_array_elem(arr, sizeof(arr) / sizeof((arr)[0]), idx)
>> +
>>   #endif
>> -- 
>> 2.43.0.472.g3155946c3a-goog
>>
>>