| 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
| ||
|
Date: Fri, 27 Apr 2018 22:23:12 -0700
From: Yonghong Song <yhs@...com>
To: Alexei Starovoitov <alexei.starovoitov@...il.com>
CC: <ast@...com>, <daniel@...earbox.net>, <netdev@...r.kernel.org>,
<kernel-team@...com>
Subject: Re: [PATCH bpf-next v7 05/10] bpf/verifier: improve register value
range tracking with ARSH
On 4/27/18 4:48 PM, Alexei Starovoitov wrote:
> On Wed, Apr 25, 2018 at 12:29:05PM -0700, Yonghong Song wrote:
>> When helpers like bpf_get_stack returns an int value
>> and later on used for arithmetic computation, the LSH and ARSH
>> operations are often required to get proper sign extension into
>> 64-bit. For example, without this patch:
>> 54: R0=inv(id=0,umax_value=800)
>> 54: (bf) r8 = r0
>> 55: R0=inv(id=0,umax_value=800) R8_w=inv(id=0,umax_value=800)
>> 55: (67) r8 <<= 32
>> 56: R8_w=inv(id=0,umax_value=3435973836800,var_off=(0x0; 0x3ff00000000))
>> 56: (c7) r8 s>>= 32
>> 57: R8=inv(id=0)
>> With this patch:
>> 54: R0=inv(id=0,umax_value=800)
>> 54: (bf) r8 = r0
>> 55: R0=inv(id=0,umax_value=800) R8_w=inv(id=0,umax_value=800)
>> 55: (67) r8 <<= 32
>> 56: R8_w=inv(id=0,umax_value=3435973836800,var_off=(0x0; 0x3ff00000000))
>> 56: (c7) r8 s>>= 32
>> 57: R8=inv(id=0, umax_value=800,var_off=(0x0; 0x3ff))
>> With better range of "R8", later on when "R8" is added to other register,
>> e.g., a map pointer or scalar-value register, the better register
>> range can be derived and verifier failure may be avoided.
>>
>> In our later example,
>> ......
>> usize = bpf_get_stack(ctx, raw_data, max_len, BPF_F_USER_STACK);
>> if (usize < 0)
>> return 0;
>> ksize = bpf_get_stack(ctx, raw_data + usize, max_len - usize, 0);
>> ......
>> Without improving ARSH value range tracking, the register representing
>> "max_len - usize" will have smin_value equal to S64_MIN and will be
>> rejected by verifier.
>>
>> Signed-off-by: Yonghong Song <yhs@...com>
>> ---
>> include/linux/tnum.h | 4 +++-
>> kernel/bpf/tnum.c | 10 ++++++++++
>> kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++++
>> 3 files changed, 54 insertions(+), 1 deletion(-)
>>
>> diff --git a/include/linux/tnum.h b/include/linux/tnum.h
>> index 0d2d3da..c7dc2b5 100644
>> --- a/include/linux/tnum.h
>> +++ b/include/linux/tnum.h
>> @@ -23,8 +23,10 @@ struct tnum tnum_range(u64 min, u64 max);
>> /* Arithmetic and logical ops */
>> /* Shift a tnum left (by a fixed shift) */
>> struct tnum tnum_lshift(struct tnum a, u8 shift);
>> -/* Shift a tnum right (by a fixed shift) */
>> +/* Shift (rsh) a tnum right (by a fixed shift) */
>> struct tnum tnum_rshift(struct tnum a, u8 shift);
>> +/* Shift (arsh) a tnum right (by a fixed min_shift) */
>> +struct tnum tnum_arshift(struct tnum a, u8 min_shift);
>> /* Add two tnums, return @a + @b */
>> struct tnum tnum_add(struct tnum a, struct tnum b);
>> /* Subtract two tnums, return @a - @b */
>> diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
>> index 1f4bf68..938d412 100644
>> --- a/kernel/bpf/tnum.c
>> +++ b/kernel/bpf/tnum.c
>> @@ -43,6 +43,16 @@ struct tnum tnum_rshift(struct tnum a, u8 shift)
>> return TNUM(a.value >> shift, a.mask >> shift);
>> }
>>
>> +struct tnum tnum_arshift(struct tnum a, u8 min_shift)
>> +{
>> + /* if a.value is negative, arithmetic shifting by minimum shift
>> + * will have larger negative offset compared to more shifting.
>> + * If a.value is nonnegative, arithmetic shifting by minimum shift
>> + * will have larger positive offset compare to more shifting.
>> + */
>> + return TNUM((s64)a.value >> min_shift, (s64)a.mask >> min_shift);
>> +}
>> +
>> struct tnum tnum_add(struct tnum a, struct tnum b)
>> {
>> u64 sm, sv, sigma, chi, mu;
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 6e3f859..573807f 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -2974,6 +2974,47 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>> /* We may learn something more from the var_off */
>> __update_reg_bounds(dst_reg);
>> break;
>> + case BPF_ARSH:
>> + if (umax_val >= insn_bitness) {
>> + /* Shifts greater than 31 or 63 are undefined.
>> + * This includes shifts by a negative number.
>> + */
>> + mark_reg_unknown(env, regs, insn->dst_reg);
>> + break;
>> + }
>> +
>> + /* BPF_ARSH is an arithmetic shift. The new range of
>> + * smin_value and smax_value should take the sign
>> + * into consideration.
>> + *
>> + * For example, if smin_value = -16, umin_val = 0
>> + * and umax_val = 2, the new smin_value should be
>> + * -16 >> 0 = -16 since -16 >> 2 = -4.
>> + * If smin_value = 16, umin_val = 0 and umax_val = 2,
>> + * the new smin_value should be 16 >> 2 = 4.
>> + *
>> + * Now suppose smax_value = -4, umin_val = 0 and
>> + * umax_val = 2, the new smax_value should be
>> + * -4 >> 2 = -1. If smax_value = 32 with the same
>> + * umin_val/umax_val, the new smax_value should remain 32.
>> + */
>> + if (dst_reg->smin_value < 0)
>> + dst_reg->smin_value >>= umin_val;
>> + else
>> + dst_reg->smin_value >>= umax_val;
>> + if (dst_reg->smax_value < 0)
>> + dst_reg->smax_value >>= umax_val;
>> + else
>> + dst_reg->smax_value >>= umin_val;
>
> above sounds correct, but unnecessary, since we have this:
> if ((src_known && (smin_val != smax_val || umin_val != umax_val)) mark_unknown
> at the top.
Yes, so the following should be much simpler:
dst_reg->smin_value >>= umin_val;
dst_reg->smax_value >>= umin_val;
>
> Also would it work if we blow smin/smax just like umin/umax
> and rely on tnum_arshift only?
I tried. This does not work. For example, with blowing up smin/smax
method, the below R8 will have umax/smax the same as both derived
from var_off.
60: R0=inv(id=0,umax_value=800,var_off=(0x0; 0x3ff)) R1=inv0
R2_w=map_value(id=0,off=0,ks=4,vs=1600,umax_value=1023,var_off=(0
x0; 0x3ff)) R6=ctx(id=0,off=0,imm=0)
R7=map_value(id=0,off=0,ks=4,vs=1600,imm=0)
R8=inv(id=0,umax_value=1023,var_off=(0x0; 0x3
ff)) R9=inv800 R10=fp0,call_-1
60: (1f) r9 -= r8
61: R0=inv(id=0,umax_value=800,var_off=(0x0; 0x3ff)) R1=inv0
R2_w=map_value(id=0,off=0,ks=4,vs=1600,umax_value=1023,var_off=(0
x0; 0x3ff)) R6=ctx(id=0,off=0,imm=0)
R7=map_value(id=0,off=0,ks=4,vs=1600,imm=0)
R8=inv(id=0,umax_value=1023,var_off=(0x0; 0x3
ff)) R9_w=inv(id=0,smin_value=-223,smax_value=800) R10=fp0,call_-1
After r9 -= r8, the smin_value for R9 becomes -223.
>
> When you rebase please document new helper in new man-page style.
Will do.
Thanks.
>
> Thanks
>
>> + dst_reg->var_off = tnum_arshift(dst_reg->var_off, umin_val);
>> +
>> + /* blow away the dst_reg umin_value/umax_value and rely on
>> + * dst_reg var_off to refine the result.
>> + */
>> + dst_reg->umin_value = 0;
>> + dst_reg->umax_value = U64_MAX;
>> + __update_reg_bounds(dst_reg);
>> + break;
>> default:
>> mark_reg_unknown(env, regs, insn->dst_reg);
>> break;
>> --
>> 2.9.5
>>
Powered by blists - more mailing lists