bpf: fix branch offset adjustment on backjumps after patching ctx expansion

CVE ID to be assigned.

3 files changed, 92 insertions, 0 deletions

diff --git a/debian/changelog b/debian/changelog
index 584776a16591..845650d9c14f 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -10,6 +10,8 @@ linux (4.4.1-1) UNRELEASED; urgency=medium
     (regression in 4.3)
   * af_unix: Don't set err in unix_stream_read_generic unless there was an error
     (regression in 4.4, 4.3.4)
+  * bpf: fix branch offset adjustment on backjumps after patching ctx expansion
+    (CVE-2016-XXXX)
 
   [ Roger Shimizu ]
   * Enable TTY_PRINTK as module (Closes: #814540).
diff --git a/debian/patches/bugfix/all/bpf-fix-branch-offset-adjustment-on-backjumps-after-.patch b/debian/patches/bugfix/all/bpf-fix-branch-offset-adjustment-on-backjumps-after-.patch
new file mode 100644
index 000000000000..c67376d9580b
--- /dev/null
+++ b/debian/patches/bugfix/all/bpf-fix-branch-offset-adjustment-on-backjumps-after-.patch
@@ -0,0 +1,89 @@
+From: Daniel Borkmann <daniel@iogearbox.net>
+Date: Wed, 10 Feb 2016 16:47:11 +0100
+Subject: bpf: fix branch offset adjustment on backjumps after patching ctx
+ expansion
+Origin: https://git.kernel.org/linus/a1b14d27ed0965838350f1377ff97c93ee383492
+
+When ctx access is used, the kernel often needs to expand/rewrite
+instructions, so after that patching, branch offsets have to be
+adjusted for both forward and backward jumps in the new eBPF program,
+but for backward jumps it fails to account the delta. Meaning, for
+example, if the expansion happens exactly on the insn that sits at
+the jump target, it doesn't fix up the back jump offset.
+
+Analysis on what the check in adjust_branches() is currently doing:
+
+  /* adjust offset of jmps if necessary */
+  if (i < pos && i + insn->off + 1 > pos)
+    insn->off += delta;
+  else if (i > pos && i + insn->off + 1 < pos)
+    insn->off -= delta;
+
+First condition (forward jumps):
+
+  Before:                         After:
+
+  insns[0]                        insns[0]
+  insns[1] <--- i/insn            insns[1] <--- i/insn
+  insns[2] <--- pos               insns[P] <--- pos
+  insns[3]                        insns[P]  `------| delta
+  insns[4] <--- target_X          insns[P]   `-----|
+  insns[5]                        insns[3]
+                                  insns[4] <--- target_X
+                                  insns[5]
+
+First case is if we cross pos-boundary and the jump instruction was
+before pos. This is handeled correctly. I.e. if i == pos, then this
+would mean our jump that we currently check was the patchlet itself
+that we just injected. Since such patchlets are self-contained and
+have no awareness of any insns before or after the patched one, the
+delta is correctly not adjusted. Also, for the second condition in
+case of i + insn->off + 1 == pos, means we jump to that newly patched
+instruction, so no offset adjustment are needed. That part is correct.
+
+Second condition (backward jumps):
+
+  Before:                         After:
+
+  insns[0]                        insns[0]
+  insns[1] <--- target_X          insns[1] <--- target_X
+  insns[2] <--- pos <-- target_Y  insns[P] <--- pos <-- target_Y
+  insns[3]                        insns[P]  `------| delta
+  insns[4] <--- i/insn            insns[P]   `-----|
+  insns[5]                        insns[3]
+                                  insns[4] <--- i/insn
+                                  insns[5]
+
+Second interesting case is where we cross pos-boundary and the jump
+instruction was after pos. Backward jump with i == pos would be
+impossible and pose a bug somewhere in the patchlet, so the first
+condition checking i > pos is okay only by itself. However, i +
+insn->off + 1 < pos does not always work as intended to trigger the
+adjustment. It works when jump targets would be far off where the
+delta wouldn't matter. But, for example, where the fixed insn->off
+before pointed to pos (target_Y), it now points to pos + delta, so
+that additional room needs to be taken into account for the check.
+This means that i) both tests here need to be adjusted into pos + delta,
+and ii) for the second condition, the test needs to be <= as pos
+itself can be a target in the backjump, too.
+
+Fixes: 9bac3d6d548e ("bpf: allow extended BPF programs access skb fields")
+Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
+Signed-off-by: David S. Miller <davem@davemloft.net>
+---
+ kernel/bpf/verifier.c | 2 +-
+ 1 file changed, 1 insertion(+), 1 deletion(-)
+
+diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
+index d1d3e8f57de9..2e7f7ab739e4 100644
+--- a/kernel/bpf/verifier.c
++++ b/kernel/bpf/verifier.c
+@@ -2082,7 +2082,7 @@ static void adjust_branches(struct bpf_prog *prog, int pos, int delta)
+ 		/* adjust offset of jmps if necessary */
+ 		if (i < pos && i + insn->off + 1 > pos)
+ 			insn->off += delta;
+-		else if (i > pos && i + insn->off + 1 < pos)
++		else if (i > pos + delta && i + insn->off + 1 <= pos + delta)
+ 			insn->off -= delta;
+ 	}
+ }
diff --git a/debian/patches/series b/debian/patches/series
index f2c33195717f..9c5fc07afb86 100644
--- a/debian/patches/series
+++ b/debian/patches/series
@@ -122,3 +122,4 @@ bugfix/all/fs-hugetlbfs-inode.c-fix-bugs-in-hugetlb_vmtruncate_.patch
 bugfix/all/af_unix-guard-against-other-sk-in-unix_dgram_sendmsg.patch
 bugfix/all/revert-workqueue-make-sure-delayed-work-run-in-local-cpu.patch
 bugfix/all/af_unix-don-t-set-err-in-unix_stream_read_generic-unless-there-was-an-error.patch
+bugfix/all/bpf-fix-branch-offset-adjustment-on-backjumps-after-.patch