Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:6 as permitted sender) client-ip=2620:137:e000::3:6;
MIME-Version: 1.0
References: <CACkBjsYXA8myxoP0Naz=ZxB0FWG-xS9e28CSFffGk1bA_n5RXw@mail.gmail.com>
In-Reply-To: <CACkBjsYXA8myxoP0Naz=ZxB0FWG-xS9e28CSFffGk1bA_n5RXw@mail.gmail.com>
From:   Hao Sun <sunhao.th@gmail.com>
Date:   Wed, 25 Oct 2023 11:22:25 +0200
Message-ID: <CACkBjsa=Wwxvb21m5b+F0jtnJTc6M=7w7uKUFMMA2078cEWXSw@mail.gmail.com>
Subject: Re: bpf: incorrect value spill in check_stack_write_fixed_off()
To:     Alexei Starovoitov <ast@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        John Fastabend <john.fastabend@gmail.com>,
        Andrii Nakryiko <andrii@kernel.org>,
        Martin KaFai Lau <martin.lau@linux.dev>,
        Song Liu <song@kernel.org>,
        Yonghong Song <yonghong.song@linux.dev>,
        KP Singh <kpsingh@kernel.org>,
        Stanislav Fomichev <sdf@google.com>,
        Hao Luo <haoluo@google.com>, Jiri Olsa <jolsa@kernel.org>
Cc:     bpf <bpf@vger.kernel.org>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Wed, Oct 25, 2023 at 11:16=E2=80=AFAM Hao Sun <sunhao.th@gmail.com> wrot=
e:
>
> Hi,
>
> In check_stack_write_fixed_off(), the verifier creates a fake reg to stor=
e the
> imm in a BPF_ST_MEM:
> ...
> else if (!reg && !(off % BPF_REG_SIZE) && is_bpf_st_mem(insn) &&
> insn->imm !=3D 0 && env->bpf_capable) {
>         struct bpf_reg_state fake_reg =3D {};
>
>         __mark_reg_known(&fake_reg, (u32)insn->imm);
>         fake_reg.type =3D SCALAR_VALUE;
>         save_register_state(state, spi, &fake_reg, size);
>
> Here, insn->imm is cast to u32, and used to mark fake_reg, which is incor=
rect
> and may lose sign information. Consider the following program:
>
> r2 =3D r10
> *(u64*)(r2 -40) =3D -44
> r0 =3D *(u64*)(r2 - 40)
> if r0 s<=3D 0xa goto +2
> r0 =3D 0
> exit
> r0  =3D 1
> exit
>

Sorry, the program should be:

 r2 =3D r10
 *(u64*)(r2 -40) =3D -44
 r0 =3D *(u64*)(r2 - 40)
 if r0 s<=3D 0xa goto +2
 r0 =3D 1
 exit
 r0  =3D 0
 exit

Here is the C macros for the following verifier's log:

BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ST_MEM(BPF_DW, BPF_REG_2, -40, -44),
BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_2, -40),
BPF_JMP_IMM(BPF_JSLT, BPF_REG_0, 0xa, 2),
BPF_MOV64_IMM(BPF_REG_0, 1),
BPF_EXIT_INSN(),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN()

> The verifier gives the following log:
>
> -------- Verifier Log --------
> func#0 @0
> 0: R1=3Dctx(off=3D0,imm=3D0) R10=3Dfp0
> 0: (bf) r2 =3D r10                      ; R2_w=3Dfp0 R10=3Dfp0
> 1: (7a) *(u64 *)(r2 -40) =3D -44        ; R2_w=3Dfp0 fp-40_w=3D4294967252
> 2: (79) r0 =3D *(u64 *)(r2 -40)         ; R0_w=3D4294967252 R2_w=3Dfp0
> fp-40_w=3D4294967252
> 3: (c5) if r0 s< 0xa goto pc+2
> mark_precise: frame0: last_idx 3 first_idx 0 subseq_idx -1
> mark_precise: frame0: regs=3Dr0 stack=3D before 2: (79) r0 =3D *(u64 *)(r=
2 -40)
> 3: R0_w=3D4294967252
> 4: (b7) r0 =3D 1                        ; R0_w=3D1
> 5: (95) exit
> verification time 7971 usec
> stack depth 40
> processed 6 insns (limit 1000000) max_states_per_insn 0 total_states 0
> peak_states 0 mark_read 0
>
> Here, the verifier incorrectly thinks R0 is 0xffffffd4, which should
> be 0xffffffffffffffd4,
> due to the u32 cast in check_stack_write_fixed_off(). This makes the veri=
fier
> collect incorrect reg scalar range.
>
> Since insn->imm is i32, we should cast it to the signed integer with
> correct size
> according to BPF_MEM, then promoting the imm to u64 to mark fake reg as
> known, right?
>
> Best
> Hao