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]
Message-ID: <2b49b96de9f8a1cd6d78cc5aebe7c35776cd2c19.camel@gmail.com>
Date: Fri, 15 Dec 2023 03:24:42 +0200
From: Eduard Zingerman <eddyz87@...il.com>
To: Andrii Nakryiko <andrii.nakryiko@...il.com>
Cc: Hao Sun <sunhao.th@...il.com>, Alexei Starovoitov <ast@...nel.org>, 
 Andrii Nakryiko <andrii@...nel.org>, Daniel Borkmann
 <daniel@...earbox.net>, bpf <bpf@...r.kernel.org>, Linux Kernel Mailing
 List <linux-kernel@...r.kernel.org>
Subject: Re: [Bug Report] bpf: incorrectly pruning runtime execution path

On Fri, 2023-12-15 at 02:49 +0200, Eduard Zingerman wrote:
> On Thu, 2023-12-14 at 16:06 -0800, Andrii Nakryiko wrote:
> [...]
> > If you agree with the analysis, we can start discussing what's the
> > best way to fix this.
> 
> Ok, yeap, I agree with you. 
> Backtracker marks both registers in 'if' statement if one of them is
> tracked, but r8 is not marked at block entry and we miss r0.

The brute-force solution is to keep a special mask for each
conditional jump in jump history. In this mask, mark all registers and
stack slots that gained range because of find_equal_scalars() executed
for this conditional jump. Use this mask to extend precise registers set.
However, such mask would be prohibitively large: (10+64)*8 bits.

---

Here is an option that would fix the test in question, but I'm not
sure if it covers all cases:
1. At the last instruction of each state (first instruction to be
   backtracked) we know the set of IDs that should be tracked for
   precision, as currently marked by mark_precise_scalar_ids().
2. In jump history we can record IDs for src and dst registers when new
   entry is pushed.
3. While backtracking 'if' statement, if one of the recorded IDs is in
   the set identified at (1), add src/dst regs to precise registers set.

E.g. for the test-case at hand:

  0: (85) call bpf_get_prandom_u32#7    ; R0=scalar()
  1: (bf) r7 = r0                       ; R0=scalar(id=1) R7_w=scalar(id=1)
  2: (bf) r8 = r0                       ; R0=scalar(id=1) R8_w=scalar(id=1)
  3: (85) call bpf_get_prandom_u32#7    ; R0=scalar()
  --- checkpoint #1 r7.id = 1, r8.id = 1 ---
  4: (25) if r0 > 0x1 goto pc+0         ; R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=1,...)
  --- checkpoint #2 r7.id = 1, r8.id = 1 ---
  5: (3d) if r8 >= r0 goto pc+3         ; R0=1 R8=0 | record r8.id=1 in jump history
  6: (0f) r8 += r8                      ; R8=0
  --- checkpoint #3 r7.id = 1, r8.id = 0 ---
  7: (15) if r7 == 0x0 goto pc+1

The precise set for checkpoint #3 state is {1}.
When insn (5) is backtracked r8.id would be in jump history and in
"precise set" => r8 and r0 would be added to backtracker state.

But this seems a bit ad-hoc.

Powered by blists - more mailing lists