)]}'
{
  "commit": "f5893af2704eb763eb982f01d573f5b19f06b623",
  "tree": "dd32c4e50aab6d6eab7c6a1381032330bfc72343",
  "parents": [
    "e80c3533c354ede56146ab0e4fbb8304d0c1209f"
  ],
  "author": {
    "name": "Daniel Borkmann",
    "email": "daniel@iogearbox.net",
    "time": "Tue Sep 07 16:16:59 2021 +0300"
  },
  "committer": {
    "name": "Greg Kroah-Hartman",
    "email": "gregkh@linuxfoundation.org",
    "time": "Wed Sep 15 09:47:38 2021 +0200"
  },
  "message": "bpf: Fix leakage due to insufficient speculative store bypass mitigation\n\ncommit 2039f26f3aca5b0e419b98f65dd36481337b86ee upstream.\n\nSpectre v4 gadgets make use of memory disambiguation, which is a set of\ntechniques that execute memory access instructions, that is, loads and\nstores, out of program order; Intel\u0027s optimization manual, section 2.4.4.5:\n\n  A load instruction micro-op may depend on a preceding store. Many\n  microarchitectures block loads until all preceding store addresses are\n  known. The memory disambiguator predicts which loads will not depend on\n  any previous stores. When the disambiguator predicts that a load does\n  not have such a dependency, the load takes its data from the L1 data\n  cache. Eventually, the prediction is verified. If an actual conflict is\n  detected, the load and all succeeding instructions are re-executed.\n\naf86ca4e3088 (\"bpf: Prevent memory disambiguation attack\") tried to mitigate\nthis attack by sanitizing the memory locations through preemptive \"fast\"\n(low latency) stores of zero prior to the actual \"slow\" (high latency) store\nof a pointer value such that upon dependency misprediction the CPU then\nspeculatively executes the load of the pointer value and retrieves the zero\nvalue instead of the attacker controlled scalar value previously stored at\nthat location, meaning, subsequent access in the speculative domain is then\nredirected to the \"zero page\".\n\nThe sanitized preemptive store of zero prior to the actual \"slow\" store is\ndone through a simple ST instruction based on r10 (frame pointer) with\nrelative offset to the stack location that the verifier has been tracking\non the original used register for STX, which does not have to be r10. Thus,\nthere are no memory dependencies for this store, since it\u0027s only using r10\nand immediate constant of zero; hence af86ca4e3088 /assumed/ a low latency\noperation.\n\nHowever, a recent attack demonstrated that this mitigation is not sufficient\nsince the preemptive store of zero could also be turned into a \"slow\" store\nand is thus bypassed as well:\n\n  [...]\n  // r2 \u003d oob address (e.g. scalar)\n  // r7 \u003d pointer to map value\n  31: (7b) *(u64 *)(r10 -16) \u003d r2\n  // r9 will remain \"fast\" register, r10 will become \"slow\" register below\n  32: (bf) r9 \u003d r10\n  // JIT maps BPF reg to x86 reg:\n  //  r9  -\u003e r15 (callee saved)\n  //  r10 -\u003e rbp\n  // train store forward prediction to break dependency link between both r9\n  // and r10 by evicting them from the predictor\u0027s LRU table.\n  33: (61) r0 \u003d *(u32 *)(r7 +24576)\n  34: (63) *(u32 *)(r7 +29696) \u003d r0\n  35: (61) r0 \u003d *(u32 *)(r7 +24580)\n  36: (63) *(u32 *)(r7 +29700) \u003d r0\n  37: (61) r0 \u003d *(u32 *)(r7 +24584)\n  38: (63) *(u32 *)(r7 +29704) \u003d r0\n  39: (61) r0 \u003d *(u32 *)(r7 +24588)\n  40: (63) *(u32 *)(r7 +29708) \u003d r0\n  [...]\n  543: (61) r0 \u003d *(u32 *)(r7 +25596)\n  544: (63) *(u32 *)(r7 +30716) \u003d r0\n  // prepare call to bpf_ringbuf_output() helper. the latter will cause rbp\n  // to spill to stack memory while r13/r14/r15 (all callee saved regs) remain\n  // in hardware registers. rbp becomes slow due to push/pop latency. below is\n  // disasm of bpf_ringbuf_output() helper for better visual context:\n  //\n  // ffffffff8117ee20: 41 54                 push   r12\n  // ffffffff8117ee22: 55                    push   rbp\n  // ffffffff8117ee23: 53                    push   rbx\n  // ffffffff8117ee24: 48 f7 c1 fc ff ff ff  test   rcx,0xfffffffffffffffc\n  // ffffffff8117ee2b: 0f 85 af 00 00 00     jne    ffffffff8117eee0 \u003c-- jump taken\n  // [...]\n  // ffffffff8117eee0: 49 c7 c4 ea ff ff ff  mov    r12,0xffffffffffffffea\n  // ffffffff8117eee7: 5b                    pop    rbx\n  // ffffffff8117eee8: 5d                    pop    rbp\n  // ffffffff8117eee9: 4c 89 e0              mov    rax,r12\n  // ffffffff8117eeec: 41 5c                 pop    r12\n  // ffffffff8117eeee: c3                    ret\n  545: (18) r1 \u003d map[id:4]\n  547: (bf) r2 \u003d r7\n  548: (b7) r3 \u003d 0\n  549: (b7) r4 \u003d 4\n  550: (85) call bpf_ringbuf_output#194288\n  // instruction 551 inserted by verifier    \\\n  551: (7a) *(u64 *)(r10 -16) \u003d 0            | /both/ are now slow stores here\n  // storing map value pointer r7 at fp-16   | since value of r10 is \"slow\".\n  552: (7b) *(u64 *)(r10 -16) \u003d r7           /\n  // following \"fast\" read to the same memory location, but due to dependency\n  // misprediction it will speculatively execute before insn 551/552 completes.\n  553: (79) r2 \u003d *(u64 *)(r9 -16)\n  // in speculative domain contains attacker controlled r2. in non-speculative\n  // domain this contains r7, and thus accesses r7 +0 below.\n  554: (71) r3 \u003d *(u8 *)(r2 +0)\n  // leak r3\n\nAs can be seen, the current speculative store bypass mitigation which the\nverifier inserts at line 551 is insufficient since /both/, the write of\nthe zero sanitation as well as the map value pointer are a high latency\ninstruction due to prior memory access via push/pop of r10 (rbp) in contrast\nto the low latency read in line 553 as r9 (r15) which stays in hardware\nregisters. Thus, architecturally, fp-16 is r7, however, microarchitecturally,\nfp-16 can still be r2.\n\nInitial thoughts to address this issue was to track spilled pointer loads\nfrom stack and enforce their load via LDX through r10 as well so that /both/\nthe preemptive store of zero /as well as/ the load use the /same/ register\nsuch that a dependency is created between the store and load. However, this\noption is not sufficient either since it can be bypassed as well under\nspeculation. An updated attack with pointer spill/fills now _all_ based on\nr10 would look as follows:\n\n  [...]\n  // r2 \u003d oob address (e.g. scalar)\n  // r7 \u003d pointer to map value\n  [...]\n  // longer store forward prediction training sequence than before.\n  2062: (61) r0 \u003d *(u32 *)(r7 +25588)\n  2063: (63) *(u32 *)(r7 +30708) \u003d r0\n  2064: (61) r0 \u003d *(u32 *)(r7 +25592)\n  2065: (63) *(u32 *)(r7 +30712) \u003d r0\n  2066: (61) r0 \u003d *(u32 *)(r7 +25596)\n  2067: (63) *(u32 *)(r7 +30716) \u003d r0\n  // store the speculative load address (scalar) this time after the store\n  // forward prediction training.\n  2068: (7b) *(u64 *)(r10 -16) \u003d r2\n  // preoccupy the CPU store port by running sequence of dummy stores.\n  2069: (63) *(u32 *)(r7 +29696) \u003d r0\n  2070: (63) *(u32 *)(r7 +29700) \u003d r0\n  2071: (63) *(u32 *)(r7 +29704) \u003d r0\n  2072: (63) *(u32 *)(r7 +29708) \u003d r0\n  2073: (63) *(u32 *)(r7 +29712) \u003d r0\n  2074: (63) *(u32 *)(r7 +29716) \u003d r0\n  2075: (63) *(u32 *)(r7 +29720) \u003d r0\n  2076: (63) *(u32 *)(r7 +29724) \u003d r0\n  2077: (63) *(u32 *)(r7 +29728) \u003d r0\n  2078: (63) *(u32 *)(r7 +29732) \u003d r0\n  2079: (63) *(u32 *)(r7 +29736) \u003d r0\n  2080: (63) *(u32 *)(r7 +29740) \u003d r0\n  2081: (63) *(u32 *)(r7 +29744) \u003d r0\n  2082: (63) *(u32 *)(r7 +29748) \u003d r0\n  2083: (63) *(u32 *)(r7 +29752) \u003d r0\n  2084: (63) *(u32 *)(r7 +29756) \u003d r0\n  2085: (63) *(u32 *)(r7 +29760) \u003d r0\n  2086: (63) *(u32 *)(r7 +29764) \u003d r0\n  2087: (63) *(u32 *)(r7 +29768) \u003d r0\n  2088: (63) *(u32 *)(r7 +29772) \u003d r0\n  2089: (63) *(u32 *)(r7 +29776) \u003d r0\n  2090: (63) *(u32 *)(r7 +29780) \u003d r0\n  2091: (63) *(u32 *)(r7 +29784) \u003d r0\n  2092: (63) *(u32 *)(r7 +29788) \u003d r0\n  2093: (63) *(u32 *)(r7 +29792) \u003d r0\n  2094: (63) *(u32 *)(r7 +29796) \u003d r0\n  2095: (63) *(u32 *)(r7 +29800) \u003d r0\n  2096: (63) *(u32 *)(r7 +29804) \u003d r0\n  2097: (63) *(u32 *)(r7 +29808) \u003d r0\n  2098: (63) *(u32 *)(r7 +29812) \u003d r0\n  // overwrite scalar with dummy pointer; same as before, also including the\n  // sanitation store with 0 from the current mitigation by the verifier.\n  2099: (7a) *(u64 *)(r10 -16) \u003d 0         | /both/ are now slow stores here\n  2100: (7b) *(u64 *)(r10 -16) \u003d r7        | since store unit is still busy.\n  // load from stack intended to bypass stores.\n  2101: (79) r2 \u003d *(u64 *)(r10 -16)\n  2102: (71) r3 \u003d *(u8 *)(r2 +0)\n  // leak r3\n  [...]\n\nLooking at the CPU microarchitecture, the scheduler might issue loads (such\nas seen in line 2101) before stores (line 2099,2100) because the load execution\nunits become available while the store execution unit is still busy with the\nsequence of dummy stores (line 2069-2098). And so the load may use the prior\nstored scalar from r2 at address r10 -16 for speculation. The updated attack\nmay work less reliable on CPU microarchitectures where loads and stores share\nexecution resources.\n\nThis concludes that the sanitizing with zero stores from af86ca4e3088 (\"bpf:\nPrevent memory disambiguation attack\") is insufficient. Moreover, the detection\nof stack reuse from af86ca4e3088 where previously data (STACK_MISC) has been\nwritten to a given stack slot where a pointer value is now to be stored does\nnot have sufficient coverage as precondition for the mitigation either; for\nseveral reasons outlined as follows:\n\n 1) Stack content from prior program runs could still be preserved and is\n    therefore not \"random\", best example is to split a speculative store\n    bypass attack between tail calls, program A would prepare and store the\n    oob address at a given stack slot and then tail call into program B which\n    does the \"slow\" store of a pointer to the stack with subsequent \"fast\"\n    read. From program B PoV such stack slot type is STACK_INVALID, and\n    therefore also must be subject to mitigation.\n\n 2) The STACK_SPILL must not be coupled to register_is_const(\u0026stack-\u003espilled_ptr)\n    condition, for example, the previous content of that memory location could\n    also be a pointer to map or map value. Without the fix, a speculative\n    store bypass is not mitigated in such precondition and can then lead to\n    a type confusion in the speculative domain leaking kernel memory near\n    these pointer types.\n\nWhile brainstorming on various alternative mitigation possibilities, we also\nstumbled upon a retrospective from Chrome developers [0]:\n\n  [...] For variant 4, we implemented a mitigation to zero the unused memory\n  of the heap prior to allocation, which cost about 1% when done concurrently\n  and 4% for scavenging. Variant 4 defeats everything we could think of. We\n  explored more mitigations for variant 4 but the threat proved to be more\n  pervasive and dangerous than we anticipated. For example, stack slots used\n  by the register allocator in the optimizing compiler could be subject to\n  type confusion, leading to pointer crafting. Mitigating type confusion for\n  stack slots alone would have required a complete redesign of the backend of\n  the optimizing compiler, perhaps man years of work, without a guarantee of\n  completeness. [...]\n\n\u003eFrom BPF side, the problem space is reduced, however, options are rather\nlimited. One idea that has been explored was to xor-obfuscate pointer spills\nto the BPF stack:\n\n  [...]\n  // preoccupy the CPU store port by running sequence of dummy stores.\n  [...]\n  2106: (63) *(u32 *)(r7 +29796) \u003d r0\n  2107: (63) *(u32 *)(r7 +29800) \u003d r0\n  2108: (63) *(u32 *)(r7 +29804) \u003d r0\n  2109: (63) *(u32 *)(r7 +29808) \u003d r0\n  2110: (63) *(u32 *)(r7 +29812) \u003d r0\n  // overwrite scalar with dummy pointer; xored with random \u0027secret\u0027 value\n  // of 943576462 before store ...\n  2111: (b4) w11 \u003d 943576462\n  2112: (af) r11 ^\u003d r7\n  2113: (7b) *(u64 *)(r10 -16) \u003d r11\n  2114: (79) r11 \u003d *(u64 *)(r10 -16)\n  2115: (b4) w2 \u003d 943576462\n  2116: (af) r2 ^\u003d r11\n  // ... and restored with the same \u0027secret\u0027 value with the help of AX reg.\n  2117: (71) r3 \u003d *(u8 *)(r2 +0)\n  [...]\n\nWhile the above would not prevent speculation, it would make data leakage\ninfeasible by directing it to random locations. In order to be effective\nand prevent type confusion under speculation, such random secret would have\nto be regenerated for each store. The additional complexity involved for a\ntracking mechanism that prevents jumps such that restoring spilled pointers\nwould not get corrupted is not worth the gain for unprivileged. Hence, the\nfix in here eventually opted for emitting a non-public BPF_ST | BPF_NOSPEC\ninstruction which the x86 JIT translates into a lfence opcode. Inserting the\nlatter in between the store and load instruction is one of the mitigations\noptions [1]. The x86 instruction manual notes:\n\n  [...] An LFENCE that follows an instruction that stores to memory might\n  complete before the data being stored have become globally visible. [...]\n\nThe latter meaning that the preceding store instruction finished execution\nand the store is at minimum guaranteed to be in the CPU\u0027s store queue, but\nit\u0027s not guaranteed to be in that CPU\u0027s L1 cache at that point (globally\nvisible). The latter would only be guaranteed via sfence. So the load which\nis guaranteed to execute after the lfence for that local CPU would have to\nrely on store-to-load forwarding. [2], in section 2.3 on store buffers says:\n\n  [...] For every store operation that is added to the ROB, an entry is\n  allocated in the store buffer. This entry requires both the virtual and\n  physical address of the target. Only if there is no free entry in the store\n  buffer, the frontend stalls until there is an empty slot available in the\n  store buffer again. Otherwise, the CPU can immediately continue adding\n  subsequent instructions to the ROB and execute them out of order. On Intel\n  CPUs, the store buffer has up to 56 entries. [...]\n\nOne small upside on the fix is that it lifts constraints from af86ca4e3088\nwhere the sanitize_stack_off relative to r10 must be the same when coming\nfrom different paths. The BPF_ST | BPF_NOSPEC gets emitted after a BPF_STX\nor BPF_ST instruction. This happens either when we store a pointer or data\nvalue to the BPF stack for the first time, or upon later pointer spills.\nThe former needs to be enforced since otherwise stale stack data could be\nleaked under speculation as outlined earlier. For non-x86 JITs the BPF_ST |\nBPF_NOSPEC mapping is currently optimized away, but others could emit a\nspeculation barrier as well if necessary. For real-world unprivileged\nprograms e.g. generated by LLVM, pointer spill/fill is only generated upon\nregister pressure and LLVM only tries to do that for pointers which are not\nused often. The program main impact will be the initial BPF_ST | BPF_NOSPEC\nsanitation for the STACK_INVALID case when the first write to a stack slot\noccurs e.g. upon map lookup. In future we might refine ways to mitigate\nthe latter cost.\n\n  [0] https://arxiv.org/pdf/1902.05178.pdf\n  [1] https://msrc-blog.microsoft.com/2018/05/21/analysis-and-mitigation-of-speculative-store-bypass-cve-2018-3639/\n  [2] https://arxiv.org/pdf/1905.05725.pdf\n\nFixes: af86ca4e3088 (\"bpf: Prevent memory disambiguation attack\")\nFixes: f7cf25b2026d (\"bpf: track spill/fill of constants\")\nCo-developed-by: Piotr Krysiuk \u003cpiotras@gmail.com\u003e\nCo-developed-by: Benedict Schlueter \u003cbenedict.schlueter@rub.de\u003e\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Piotr Krysiuk \u003cpiotras@gmail.com\u003e\nSigned-off-by: Benedict Schlueter \u003cbenedict.schlueter@rub.de\u003e\nAcked-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nSigned-off-by: Sasha Levin \u003csashal@kernel.org\u003e\n[OP: - apply check_stack_write_fixed_off() changes in check_stack_write()\n     - replace env-\u003ebypass_spec_v4 -\u003e env-\u003eallow_ptr_leaks]\nSigned-off-by: Ovidiu Panait \u003covidiu.panait@windriver.com\u003e\nSigned-off-by: Greg Kroah-Hartman \u003cgregkh@linuxfoundation.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "22f070085971b58c4a1c1cbd10479184517bad09",
      "old_mode": 33188,
      "old_path": "include/linux/bpf_verifier.h",
      "new_id": "4292e8e42c120b17c6b5285835e0ccbcda200f72",
      "new_mode": 33188,
      "new_path": "include/linux/bpf_verifier.h"
    },
    {
      "type": "modify",
      "old_id": "c5ecb6147ea28e23ffbac2ca24954db2408fe163",
      "old_mode": 33188,
      "old_path": "kernel/bpf/verifier.c",
      "new_id": "28767cd43046079ad979e88bb04e3121f1719006",
      "new_mode": 33188,
      "new_path": "kernel/bpf/verifier.c"
    }
  ]
}