[bpf-next,0/3] bpf: Add LDX/STX/ST sanitize in jited BPF progs

  The verifier sometimes makes mistakes[1][2] that may be exploited to
achieve arbitrary read/write. Currently, syzbot is continuously testing
bpf, and can find memory issues in bpf syscalls, but it can hardly find
mischecking/bugs in the verifier. We need runtime checks like KASAN in
BPF programs for this. This patch series implements address sanitize
in jited BPF progs for testing purpose, so that tools like syzbot can
find interesting bugs in the verifier automatically by, if possible,
generating and executing BPF programs that bypass the verifier but have
memory issues, then triggering this sanitizing.

The idea is to dispatch read/write addr of a BPF program to the kernel
functions that are instrumented by KASAN, to achieve indirect checking. 
Indirect checking is adopted because this is much simple, instrument
direct checking like compilers makes the jit much more complex. The
main step is: back up R0&R1 and store addr in R1, and then insert the
checking function before load/store insns, during bpf_misc_fixup(), and
finally in the jit stage, backup R1~R5 to make sure the checking funcs
won't corrupt regs states. An extra Kconfig option is used to enable
this, so normal use case won't be impacted at all.

Also, not all ldx/stx/st are instrumented. Insns rewrote by other fixup
or conversion passes that use BPF_REG_AX are skipped, because that
conflicts with us; insns whose access addr is specified by R10 are also
skipped because they are trivial to verify.

Patch1 sanitizes st/stx insns, and Patch2 sanitizes ldx insns, Patch3 adds
selftests for instrumentation in each possible case, and all new/existing
selftests for the verifier can pass. Also, a BPF prog that also exploits
CVE-2022-23222 to achieve OOB read is provided[3], this can be perfertly
captured with this patch series.

I haven't found a better way to back up the regs before executing the
checking functions, and have to store them on the stack. Comments and
advice are surely welcome.

[1] http://bit.do/CVE-2021-3490
[2] http://bit.do/CVE-2022-23222
[3] OOB-read: https://pastebin.com/raw/Ee1Cw492

Hao Sun (3):
  bpf: Sanitize STX/ST in jited BPF progs with KASAN
  bpf: Sanitize LDX in jited BPF progs with KASAN
  selftests/bpf: Add tests for LDX/STX/ST sanitize

 arch/x86/net/bpf_jit_comp.c                   |  34 ++
 include/linux/bpf.h                           |  14 +
 kernel/bpf/Kconfig                            |  14 +
 kernel/bpf/verifier.c                         | 190 +++++++++++
 .../selftests/bpf/verifier/sanitize_st_ldx.c  | 323 ++++++++++++++++++
 5 files changed, 575 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/verifier/sanitize_st_ldx.c


base-commit: 8a2162a9227dda936a21fe72014a9931a3853a7b
  

On 11/23/22 3:15 PM, Hao Sun wrote:
> The verifier sometimes makes mistakes[1][2] that may be exploited to
> achieve arbitrary read/write. Currently, syzbot is continuously testing
> bpf, and can find memory issues in bpf syscalls, but it can hardly find
> mischecking/bugs in the verifier. We need runtime checks like KASAN in
> BPF programs for this. This patch series implements address sanitize
> in jited BPF progs for testing purpose, so that tools like syzbot can
> find interesting bugs in the verifier automatically by, if possible,
> generating and executing BPF programs that bypass the verifier but have
> memory issues, then triggering this sanitizing.
> 
> The idea is to dispatch read/write addr of a BPF program to the kernel
> functions that are instrumented by KASAN, to achieve indirect checking.
> Indirect checking is adopted because this is much simple, instrument
> direct checking like compilers makes the jit much more complex. The
> main step is: back up R0&R1 and store addr in R1, and then insert the
> checking function before load/store insns, during bpf_misc_fixup(), and
> finally in the jit stage, backup R1~R5 to make sure the checking funcs
> won't corrupt regs states. An extra Kconfig option is used to enable
> this, so normal use case won't be impacted at all.

Thanks for looking into this! It's a bit unfortunate that this will need
changes in every BPF JIT. Have you thought about a generic solution which
would not require changes in JITs? Given this is for debugging and finding
mischecking/bugs in the verifier, can't we reuse interpreter for this and
only implement it there? I would be curious if we could achieve the same
result from [3] with such approach.

> Also, not all ldx/stx/st are instrumented. Insns rewrote by other fixup
> or conversion passes that use BPF_REG_AX are skipped, because that
> conflicts with us; insns whose access addr is specified by R10 are also
> skipped because they are trivial to verify.
> 
> Patch1 sanitizes st/stx insns, and Patch2 sanitizes ldx insns, Patch3 adds
> selftests for instrumentation in each possible case, and all new/existing
> selftests for the verifier can pass. Also, a BPF prog that also exploits
> CVE-2022-23222 to achieve OOB read is provided[3], this can be perfertly
> captured with this patch series.
> 
> I haven't found a better way to back up the regs before executing the
> checking functions, and have to store them on the stack. Comments and
> advice are surely welcome.
> 
> [1] http://bit.do/CVE-2021-3490
> [2] http://bit.do/CVE-2022-23222
> [3] OOB-read: https://pastebin.com/raw/Ee1Cw492
> 
> Hao Sun (3):
>    bpf: Sanitize STX/ST in jited BPF progs with KASAN
>    bpf: Sanitize LDX in jited BPF progs with KASAN
>    selftests/bpf: Add tests for LDX/STX/ST sanitize
> 
>   arch/x86/net/bpf_jit_comp.c                   |  34 ++
>   include/linux/bpf.h                           |  14 +
>   kernel/bpf/Kconfig                            |  14 +
>   kernel/bpf/verifier.c                         | 190 +++++++++++
>   .../selftests/bpf/verifier/sanitize_st_ldx.c  | 323 ++++++++++++++++++
>   5 files changed, 575 insertions(+)
>   create mode 100644 tools/testing/selftests/bpf/verifier/sanitize_st_ldx.c
> 
> 
> base-commit: 8a2162a9227dda936a21fe72014a9931a3853a7b
> 

Thanks,
Daniel
  

Daniel Borkmann <daniel@iogearbox.net> 于2022年11月24日周四 07:41写道：
>
> On 11/23/22 3:15 PM, Hao Sun wrote:
> > The verifier sometimes makes mistakes[1][2] that may be exploited to
> > achieve arbitrary read/write. Currently, syzbot is continuously testing
> > bpf, and can find memory issues in bpf syscalls, but it can hardly find
> > mischecking/bugs in the verifier. We need runtime checks like KASAN in
> > BPF programs for this. This patch series implements address sanitize
> > in jited BPF progs for testing purpose, so that tools like syzbot can
> > find interesting bugs in the verifier automatically by, if possible,
> > generating and executing BPF programs that bypass the verifier but have
> > memory issues, then triggering this sanitizing.
> >
> > The idea is to dispatch read/write addr of a BPF program to the kernel
> > functions that are instrumented by KASAN, to achieve indirect checking.
> > Indirect checking is adopted because this is much simple, instrument
> > direct checking like compilers makes the jit much more complex. The
> > main step is: back up R0&R1 and store addr in R1, and then insert the
> > checking function before load/store insns, during bpf_misc_fixup(), and
> > finally in the jit stage, backup R1~R5 to make sure the checking funcs
> > won't corrupt regs states. An extra Kconfig option is used to enable
> > this, so normal use case won't be impacted at all.
>
> Thanks for looking into this! It's a bit unfortunate that this will need
> changes in every BPF JIT. Have you thought about a generic solution which
> would not require changes in JITs? Given this is for debugging and finding
> mischecking/bugs in the verifier, can't we reuse interpreter for this and
> only implement it there? I would be curious if we could achieve the same
> result from [3] with such approach.
>

Hi Daniel,

Thanks for taking a look. The reason I choose to do this in jited progs is
because JIT is used in most real cases, so does testing/fuzzing, e.g.,
syzbot test BPF with JIT_ALWAYS_ON=y. Also, a BPF program generated
by fuzzers or other tools is likely need to be run hundred times with random
inputs to trigger potential issues in it and be captured by sanitize, so JIT
makes this much faster.

We don't need changes in every BPF JIT I believe, supporting X86_64
and Arm64 would be enough, and the only thing need to be done there
is to backup regs on stack before calling checking functions.
Also, I'm wondering if anyone knows how to better make sure the checking
function won't corrupt scratch regs' states, e.g., a flag to force compiler to
push scratch regs before using them, during gen code for those funcs.
If this is feasible, the changes to JIT can be completely removed, and
fixup in the verifier would be enough.

Regards
Hao

> > Also, not all ldx/stx/st are instrumented. Insns rewrote by other fixup
> > or conversion passes that use BPF_REG_AX are skipped, because that
> > conflicts with us; insns whose access addr is specified by R10 are also
> > skipped because they are trivial to verify.
> >
> > Patch1 sanitizes st/stx insns, and Patch2 sanitizes ldx insns, Patch3 adds
> > selftests for instrumentation in each possible case, and all new/existing
> > selftests for the verifier can pass. Also, a BPF prog that also exploits
> > CVE-2022-23222 to achieve OOB read is provided[3], this can be perfertly
> > captured with this patch series.
> >
> > I haven't found a better way to back up the regs before executing the
> > checking functions, and have to store them on the stack. Comments and
> > advice are surely welcome.
> >
> > [1] http://bit.do/CVE-2021-3490
> > [2] http://bit.do/CVE-2022-23222
> > [3] OOB-read: https://pastebin.com/raw/Ee1Cw492
> >
> > Hao Sun (3):
> >    bpf: Sanitize STX/ST in jited BPF progs with KASAN
> >    bpf: Sanitize LDX in jited BPF progs with KASAN
> >    selftests/bpf: Add tests for LDX/STX/ST sanitize
> >
> >   arch/x86/net/bpf_jit_comp.c                   |  34 ++
> >   include/linux/bpf.h                           |  14 +
> >   kernel/bpf/Kconfig                            |  14 +
> >   kernel/bpf/verifier.c                         | 190 +++++++++++
> >   .../selftests/bpf/verifier/sanitize_st_ldx.c  | 323 ++++++++++++++++++
> >   5 files changed, 575 insertions(+)
> >   create mode 100644 tools/testing/selftests/bpf/verifier/sanitize_st_ldx.c
> >
> >
> > base-commit: 8a2162a9227dda936a21fe72014a9931a3853a7b
> >
>
> Thanks,
> Daniel
  

Hao Sun <sunhao.th@gmail.com> 于2022年11月24日周四 11:05写道：
>
> Daniel Borkmann <daniel@iogearbox.net> 于2022年11月24日周四 07:41写道：
> >
> > On 11/23/22 3:15 PM, Hao Sun wrote:
> > > The verifier sometimes makes mistakes[1][2] that may be exploited to
> > > achieve arbitrary read/write. Currently, syzbot is continuously testing
> > > bpf, and can find memory issues in bpf syscalls, but it can hardly find
> > > mischecking/bugs in the verifier. We need runtime checks like KASAN in
> > > BPF programs for this. This patch series implements address sanitize
> > > in jited BPF progs for testing purpose, so that tools like syzbot can
> > > find interesting bugs in the verifier automatically by, if possible,
> > > generating and executing BPF programs that bypass the verifier but have
> > > memory issues, then triggering this sanitizing.
> > >
> > > The idea is to dispatch read/write addr of a BPF program to the kernel
> > > functions that are instrumented by KASAN, to achieve indirect checking.
> > > Indirect checking is adopted because this is much simple, instrument
> > > direct checking like compilers makes the jit much more complex. The
> > > main step is: back up R0&R1 and store addr in R1, and then insert the
> > > checking function before load/store insns, during bpf_misc_fixup(), and
> > > finally in the jit stage, backup R1~R5 to make sure the checking funcs
> > > won't corrupt regs states. An extra Kconfig option is used to enable
> > > this, so normal use case won't be impacted at all.
> >
> > Thanks for looking into this! It's a bit unfortunate that this will need
> > changes in every BPF JIT. Have you thought about a generic solution which
> > would not require changes in JITs? Given this is for debugging and finding
> > mischecking/bugs in the verifier, can't we reuse interpreter for this and
> > only implement it there? I would be curious if we could achieve the same
> > result from [3] with such approach.
> >
>
> Hi Daniel,
>
> Thanks for taking a look. The reason I choose to do this in jited progs is
> because JIT is used in most real cases, so does testing/fuzzing, e.g.,
> syzbot test BPF with JIT_ALWAYS_ON=y. Also, a BPF program generated
> by fuzzers or other tools is likely need to be run hundred times with random
> inputs to trigger potential issues in it and be captured by sanitize, so JIT
> makes this much faster.
>
> We don't need changes in every BPF JIT I believe, supporting X86_64
> and Arm64 would be enough, and the only thing need to be done there
> is to backup regs on stack before calling checking functions.
> Also, I'm wondering if anyone knows how to better make sure the checking
> function won't corrupt scratch regs' states, e.g., a flag to force compiler to
> push scratch regs before using them, during gen code for those funcs.
> If this is feasible, the changes to JIT can be completely removed, and
> fixup in the verifier would be enough.
>

I think we can extend BPF prog's stack size in this mode, then backup all
the scratch regs to those free space. This way, everything just happens
in BPF insn level, we don't need to change JIT at all.

I will send patch v2 for this.

> Regards
> Hao
>
> > > Also, not all ldx/stx/st are instrumented. Insns rewrote by other fixup
> > > or conversion passes that use BPF_REG_AX are skipped, because that
> > > conflicts with us; insns whose access addr is specified by R10 are also
> > > skipped because they are trivial to verify.
> > >
> > > Patch1 sanitizes st/stx insns, and Patch2 sanitizes ldx insns, Patch3 adds
> > > selftests for instrumentation in each possible case, and all new/existing
> > > selftests for the verifier can pass. Also, a BPF prog that also exploits
> > > CVE-2022-23222 to achieve OOB read is provided[3], this can be perfertly
> > > captured with this patch series.
> > >
> > > I haven't found a better way to back up the regs before executing the
> > > checking functions, and have to store them on the stack. Comments and
> > > advice are surely welcome.
> > >
> > > [1] http://bit.do/CVE-2021-3490
> > > [2] http://bit.do/CVE-2022-23222
> > > [3] OOB-read: https://pastebin.com/raw/Ee1Cw492
> > >
> > > Hao Sun (3):
> > >    bpf: Sanitize STX/ST in jited BPF progs with KASAN
> > >    bpf: Sanitize LDX in jited BPF progs with KASAN
> > >    selftests/bpf: Add tests for LDX/STX/ST sanitize
> > >
> > >   arch/x86/net/bpf_jit_comp.c                   |  34 ++
> > >   include/linux/bpf.h                           |  14 +
> > >   kernel/bpf/Kconfig                            |  14 +
> > >   kernel/bpf/verifier.c                         | 190 +++++++++++
> > >   .../selftests/bpf/verifier/sanitize_st_ldx.c  | 323 ++++++++++++++++++
> > >   5 files changed, 575 insertions(+)
> > >   create mode 100644 tools/testing/selftests/bpf/verifier/sanitize_st_ldx.c
> > >
> > >
> > > base-commit: 8a2162a9227dda936a21fe72014a9931a3853a7b
> > >
> >
> > Thanks,
> > Daniel