)]}'
{
  "commit": "5fc6ed1831ca5a30fb0ceefd5e33c7c689e7627b",
  "tree": "5de72027b489cff5b38844b4406acde8080733fc",
  "parents": [
    "960b08dd36de1e341e3eb43d1c547513e338f4f8"
  ],
  "author": {
    "name": "Daniel Borkmann",
    "email": "daniel@iogearbox.net",
    "time": "Fri May 28 15:47:32 2021 +0000"
  },
  "committer": {
    "name": "Greg Kroah-Hartman",
    "email": "gregkh@linuxfoundation.org",
    "time": "Wed Jun 23 14:42:45 2021 +0200"
  },
  "message": "bpf: Fix leakage under speculation on mispredicted branches\n\n[ Upstream commit 9183671af6dbf60a1219371d4ed73e23f43b49db ]\n\nThe verifier only enumerates valid control-flow paths and skips paths that\nare unreachable in the non-speculative domain. And so it can miss issues\nunder speculative execution on mispredicted branches.\n\nFor example, a type confusion has been demonstrated with the following\ncrafted program:\n\n  // r0 \u003d pointer to a map array entry\n  // r6 \u003d pointer to readable stack slot\n  // r9 \u003d scalar controlled by attacker\n  1: r0 \u003d *(u64 *)(r0) // cache miss\n  2: if r0 !\u003d 0x0 goto line 4\n  3: r6 \u003d r9\n  4: if r0 !\u003d 0x1 goto line 6\n  5: r9 \u003d *(u8 *)(r6)\n  6: // leak r9\n\nSince line 3 runs iff r0 \u003d\u003d 0 and line 5 runs iff r0 \u003d\u003d 1, the verifier\nconcludes that the pointer dereference on line 5 is safe. But: if the\nattacker trains both the branches to fall-through, such that the following\nis speculatively executed ...\n\n  r6 \u003d r9\n  r9 \u003d *(u8 *)(r6)\n  // leak r9\n\n... then the program will dereference an attacker-controlled value and could\nleak its content under speculative execution via side-channel. This requires\nto mistrain the branch predictor, which can be rather tricky, because the\nbranches are mutually exclusive. However such training can be done at\ncongruent addresses in user space using different branches that are not\nmutually exclusive. That is, by training branches in user space ...\n\n  A:  if r0 !\u003d 0x0 goto line C\n  B:  ...\n  C:  if r0 !\u003d 0x0 goto line D\n  D:  ...\n\n... such that addresses A and C collide to the same CPU branch prediction\nentries in the PHT (pattern history table) as those of the BPF program\u0027s\nlines 2 and 4, respectively. A non-privileged attacker could simply brute\nforce such collisions in the PHT until observing the attack succeeding.\n\nAlternative methods to mistrain the branch predictor are also possible that\navoid brute forcing the collisions in the PHT. A reliable attack has been\ndemonstrated, for example, using the following crafted program:\n\n  // r0 \u003d pointer to a [control] map array entry\n  // r7 \u003d *(u64 *)(r0 + 0), training/attack phase\n  // r8 \u003d *(u64 *)(r0 + 8), oob address\n  // [...]\n  // r0 \u003d pointer to a [data] map array entry\n  1: if r7 \u003d\u003d 0x3 goto line 3\n  2: r8 \u003d r0\n  // crafted sequence of conditional jumps to separate the conditional\n  // branch in line 193 from the current execution flow\n  3: if r0 !\u003d 0x0 goto line 5\n  4: if r0 \u003d\u003d 0x0 goto exit\n  5: if r0 !\u003d 0x0 goto line 7\n  6: if r0 \u003d\u003d 0x0 goto exit\n  [...]\n  187: if r0 !\u003d 0x0 goto line 189\n  188: if r0 \u003d\u003d 0x0 goto exit\n  // load any slowly-loaded value (due to cache miss in phase 3) ...\n  189: r3 \u003d *(u64 *)(r0 + 0x1200)\n  // ... and turn it into known zero for verifier, while preserving slowly-\n  // loaded dependency when executing:\n  190: r3 \u0026\u003d 1\n  191: r3 \u0026\u003d 2\n  // speculatively bypassed phase dependency\n  192: r7 +\u003d r3\n  193: if r7 \u003d\u003d 0x3 goto exit\n  194: r4 \u003d *(u8 *)(r8 + 0)\n  // leak r4\n\nAs can be seen, in training phase (phase !\u003d 0x3), the condition in line 1\nturns into false and therefore r8 with the oob address is overridden with\nthe valid map value address, which in line 194 we can read out without\nissues. However, in attack phase, line 2 is skipped, and due to the cache\nmiss in line 189 where the map value is (zeroed and later) added to the\nphase register, the condition in line 193 takes the fall-through path due\nto prior branch predictor training, where under speculation, it\u0027ll load the\nbyte at oob address r8 (unknown scalar type at that point) which could then\nbe leaked via side-channel.\n\nOne way to mitigate these is to \u0027branch off\u0027 an unreachable path, meaning,\nthe current verification path keeps following the is_branch_taken() path\nand we push the other branch to the verification stack. Given this is\nunreachable from the non-speculative domain, this branch\u0027s vstate is\nexplicitly marked as speculative. This is needed for two reasons: i) if\nthis path is solely seen from speculative execution, then we later on still\nwant the dead code elimination to kick in in order to sanitize these\ninstructions with jmp-1s, and ii) to ensure that paths walked in the\nnon-speculative domain are not pruned from earlier walks of paths walked in\nthe speculative domain. Additionally, for robustness, we mark the registers\nwhich have been part of the conditional as unknown in the speculative path\ngiven there should be no assumptions made on their content.\n\nThe fix in here mitigates type confusion attacks described earlier due to\ni) all code paths in the BPF program being explored and ii) existing\nverifier logic already ensuring that given memory access instruction\nreferences one specific data structure.\n\nAn alternative to this fix that has also been looked at in this scope was to\nmark aux-\u003ealu_state at the jump instruction with a BPF_JMP_TAKEN state as\nwell as direction encoding (always-goto, always-fallthrough, unknown), such\nthat mixing of different always-* directions themselves as well as mixing of\nalways-* with unknown directions would cause a program rejection by the\nverifier, e.g. programs with constructs like \u0027if ([...]) { x \u003d 0; } else\n{ x \u003d 1; }\u0027 with subsequent \u0027if (x \u003d\u003d 1) { [...] }\u0027. For unprivileged, this\nwould result in only single direction always-* taken paths, and unknown taken\npaths being allowed, such that the former could be patched from a conditional\njump to an unconditional jump (ja). Compared to this approach here, it would\nhave two downsides: i) valid programs that otherwise are not performing any\npointer arithmetic, etc, would potentially be rejected/broken, and ii) we are\nrequired to turn off path pruning for unprivileged, where both can be avoided\nin this work through pushing the invalid branch to the verification stack.\n\nThe issue was originally discovered by Adam and Ofek, and later independently\ndiscovered and reported as a result of Benedict and Piotr\u0027s research work.\n\nFixes: b2157399cc98 (\"bpf: prevent out-of-bounds speculation\")\nReported-by: Adam Morrison \u003cmad@cs.tau.ac.il\u003e\nReported-by: Ofek Kirzner \u003cofekkir@gmail.com\u003e\nReported-by: Benedict Schlueter \u003cbenedict.schlueter@rub.de\u003e\nReported-by: Piotr Krysiuk \u003cpiotras@gmail.com\u003e\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nReviewed-by: John Fastabend \u003cjohn.fastabend@gmail.com\u003e\nReviewed-by: Benedict Schlueter \u003cbenedict.schlueter@rub.de\u003e\nReviewed-by: Piotr Krysiuk \u003cpiotras@gmail.com\u003e\nAcked-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nSigned-off-by: Sasha Levin \u003csashal@kernel.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "4f50d6f128be3598b806ade6e83b0f92d7f25788",
      "old_mode": 33188,
      "old_path": "kernel/bpf/verifier.c",
      "new_id": "da8fc57ff5b2500956627746ae008fe7a08d81e2",
      "new_mode": 33188,
      "new_path": "kernel/bpf/verifier.c"
    }
  ]
}