| 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
| ||
|
Message-Id: <20240411122752.2873562-8-xukuohai@huaweicloud.com>
Date: Thu, 11 Apr 2024 20:27:48 +0800
From: Xu Kuohai <xukuohai@...weicloud.com>
To: bpf@...r.kernel.org,
netdev@...r.kernel.org,
linux-security-module@...r.kernel.org,
linux-kselftest@...r.kernel.org
Cc: Alexei Starovoitov <ast@...nel.org>,
Andrii Nakryiko <andrii@...nel.org>,
Daniel Borkmann <daniel@...earbox.net>,
Martin KaFai Lau <martin.lau@...ux.dev>,
Eduard Zingerman <eddyz87@...il.com>,
Song Liu <song@...nel.org>,
Yonghong Song <yonghong.song@...ux.dev>,
John Fastabend <john.fastabend@...il.com>,
KP Singh <kpsingh@...nel.org>,
Stanislav Fomichev <sdf@...gle.com>,
Hao Luo <haoluo@...gle.com>,
Jiri Olsa <jolsa@...nel.org>,
Matt Bobrowski <mattbobrowski@...gle.com>,
Brendan Jackman <jackmanb@...omium.org>,
Paul Moore <paul@...l-moore.com>,
James Morris <jmorris@...ei.org>,
"Serge E . Hallyn" <serge@...lyn.com>,
Khadija Kamran <kamrankhadijadj@...il.com>,
Casey Schaufler <casey@...aufler-ca.com>,
Ondrej Mosnacek <omosnace@...hat.com>,
Kees Cook <keescook@...omium.org>,
John Johansen <john.johansen@...onical.com>,
Lukas Bulwahn <lukas.bulwahn@...il.com>,
Roberto Sassu <roberto.sassu@...wei.com>,
Shung-Hsi Yu <shung-hsi.yu@...e.com>
Subject: [PATCH bpf-next v3 07/11] bpf: Fix a false rejection caused by AND operation
From: Xu Kuohai <xukuohai@...wei.com>
With lsm return value check, the no-alu32 version test_libbpf_get_fd_by_id_opts
is rejected by the verifier, and the log says:
0: R1=ctx() R10=fp0
; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27
0: (b7) r0 = 0 ; R0_w=0
1: (79) r2 = *(u64 *)(r1 +0)
func 'bpf_lsm_bpf_map' arg0 has btf_id 916 type STRUCT 'bpf_map'
2: R1=ctx() R2_w=trusted_ptr_bpf_map()
; if (map != (struct bpf_map *)&data_input) @ test_libbpf_get_fd_by_id_opts.c:29
2: (18) r3 = 0xffff9742c0951a00 ; R3_w=map_ptr(map=data_input,ks=4,vs=4)
4: (5d) if r2 != r3 goto pc+4 ; R2_w=trusted_ptr_bpf_map() R3_w=map_ptr(map=data_input,ks=4,vs=4)
; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27
5: (79) r0 = *(u64 *)(r1 +8) ; R0_w=scalar() R1=ctx()
; if (fmode & FMODE_WRITE) @ test_libbpf_get_fd_by_id_opts.c:32
6: (67) r0 <<= 62 ; R0_w=scalar(smax=0x4000000000000000,umax=0xc000000000000000,smin32=0,smax32=umax32=0,var_off=(0x0; 0xc000000000000000))
7: (c7) r0 s>>= 63 ; R0_w=scalar(smin=smin32=-1,smax=smax32=0)
; @ test_libbpf_get_fd_by_id_opts.c:0
8: (57) r0 &= -13 ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3))
; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27
9: (95) exit
And here is the C code of the prog.
SEC("lsm/bpf_map")
int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode)
{
if (map != (struct bpf_map *)&data_input)
return 0;
if (fmode & FMODE_WRITE)
return -EACCES;
return 0;
}
It is clear that the prog can only return either 0 or -EACCESS, and both
values are legal.
So why is it rejected by the verifier?
The verifier log shows that the second if and return value setting
statements in the prog is optimized to bitwise operations "r0 s>>= 63"
and "r0 &= -13". The verifier correctly deduces that the the value of
r0 is in the range [-1, 0] after verifing instruction "r0 s>>= 63".
But when the verifier proceeds to verify instruction "r0 &= -13", it
fails to deduce the correct value range of r0.
7: (c7) r0 s>>= 63 ; R0_w=scalar(smin=smin32=-1,smax=smax32=0)
8: (57) r0 &= -13 ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3))
So why the verifier fails to deduce the result of 'r0 &= -13'?
The verifier uses tnum to track values, and the two ranges "[-1, 0]" and
"[0, -1ULL]" are encoded to the same tnum. When verifing instruction
"r0 &= -13", the verifier erroneously deduces the result from
"[0, -1ULL] AND -13", which is out of the expected return range
[-4095, 0].
To fix it, this patch simply adds a special SCALAR32 case for the
verifier. That is, when the source operand of the AND instruction is
a constant and the destination operand changes from negative to
non-negative and falls in range [-256, 256], deduce the result range
by enumerating all possible AND results.
Signed-off-by: Xu Kuohai <xukuohai@...wei.com>
---
kernel/bpf/verifier.c | 23 +++++++++++++++++++++++
1 file changed, 23 insertions(+)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5393d576c76f..62e259f18f35 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13369,6 +13369,29 @@ static void scalar32_min_max_and(struct bpf_reg_state *dst_reg,
return;
}
+ if (src_known &&
+ dst_reg->s32_min_value < 0 && dst_reg->s32_min_value >= -256 &&
+ dst_reg->s32_max_value >= 0 && dst_reg->s32_max_value <= 256 &&
+ dst_reg->s32_min_value == dst_reg->smin_value &&
+ dst_reg->s32_max_value == dst_reg->smax_value) {
+ s32 s32_min = S32_MAX;
+ s32 s32_max = S32_MIN;
+ s32 v = dst_reg->s32_min_value;
+ while (v <= dst_reg->s32_max_value) {
+ s32 w = (v & src_reg->s32_min_value);
+ if (w < s32_min)
+ s32_min = w;
+ if (w > s32_max)
+ s32_max = w;
+ v++;
+ }
+ dst_reg->s32_min_value = s32_min;
+ dst_reg->s32_max_value = s32_max;
+ dst_reg->u32_min_value = var32_off.value;
+ dst_reg->u32_max_value = min(dst_reg->u32_max_value, umax_val);
+ return;
+ }
+
/* We get our minimum from the var_off, since that's inherently
* bitwise. Our maximum is the minimum of the operands' maxima.
*/
--
2.30.2
Powered by blists - more mailing lists