| blob | 29ab70548ef1986277e24a50e472df1772a223c8 |
1 //====- X86SpeculativeLoadHardening.cpp - A Spectre v1 mitigation ---------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 ///
10 /// Provide a pass which mitigates speculative execution attacks which operate
11 /// by speculating incorrectly past some predicate (a type check, bounds check,
12 /// or other condition) to reach a load with invalid inputs and leak the data
13 /// accessed by that load using a side channel out of the speculative domain.
14 ///
15 /// For details on the attacks, see the first variant in both the Project Zero
16 /// writeup and the Spectre paper:
17 /// https://googleprojectzero.blogspot.com/2018/01/reading-privileged-memory-with-side.html
18 /// https://spectreattack.com/spectre.pdf
19 ///
20 //===----------------------------------------------------------------------===//
56 #include <algorithm>
57 #include <cassert>
58 #include <iterator>
59 #include <utility>
64 #define DEBUG_TYPE PASS_KEY
85 "Use LFENCE along each conditional edge to harden against speculative "
92 "flushing the loaded bits to 1. This is hard to do "
117 "stored attacker controlled addresses. This is designed to "
129 }
133 /// Pass identification, replacement for typeid.
137 /// The information about a block's conditional terminators needed to trace
138 /// our predicate state through the exiting edges.
142 // We mostly have one conditional branch, and in extremely rare cases have
143 // two. Three and more are so rare as to be unimportant for compile time.
147 };
149 /// Manages the predicate state traced through the program.
155 MachineSSAUpdater SSA;
159 };
193 DebugLoc Loc);
195 void
199 MachineInstr *
205 DebugLoc Loc);
212 };
221 }
233 // We have to insert the new block immediately after the current one as we
234 // don't know what layout-successor relationships the successor has and we
235 // may not be able to (and generally don't want to) try to fix those up.
238 // Update the branch instruction if necessary.
244 // If this successor was reached through a branch rather than fallthrough,
245 // we might have *broken* fallthrough and so need to inject a new
246 // unconditional branch.
251 "Without an unconditional branch, the old layout successor should "
255 // Update the unconditional branch now that we've added one.
257 }
259 // Insert unconditional "jump Succ" instruction in the new block if
260 // necessary.
264 }
269 "A non-branch successor must have been a layout successor before "
271 }
273 // If this is the only edge to the successor, we can just replace it in the
274 // CFG. Otherwise we need to add a new entry in the CFG for the new
275 // successor.
280 }
282 // Hook up the edge from the new basic block to the old successor in the CFG.
285 // Fix PHI nodes in Succ so they refer to NewMBB instead of MBB.
297 // If this is the last edge to the succesor, just replace MBB in the PHI
301 }
303 // Otherwise, append a new pair of operands for the new incoming edge.
307 }
308 }
310 // Inherit live-ins from the successor
317 }
319 /// Removing duplicate PHI operands to leave the PHI in a canonical and
320 /// predictable form.
321 ///
322 /// FIXME: It's really frustrating that we have to do this, but SSA-form in MIR
323 /// isn't what you might expect. We may have multiple entries in PHI nodes for
324 /// a single predecessor. This makes CFG-updating extremely complex, so here we
325 /// simplify all PHI nodes to a model even simpler than the IR's model: exactly
326 /// one entry per predecessor, regardless of how many edges there are.
335 // First we scan the operands of the PHI looking for duplicate entries
336 // a particular predecessor. We retain the operand index of each duplicate
337 // entry found.
343 // Now walk the duplicate indices, removing both the block and value. Note
344 // that these are stored as a vector making this element-wise removal
345 // :w
346 // potentially quadratic.
347 //
348 // FIXME: It is really frustrating that we have to use a quadratic
349 // removal algorithm here. There should be a better way, but the use-def
350 // updates required make that impossible using the public API.
351 //
352 // Note that we have to process these backwards so that we don't
353 // invalidate other indices with each removal.
356 // Remove both the block and value operand, again in reverse order to
357 // preserve indices.
360 }
363 }
364 }
366 /// Helper to scan a function for loads vulnerable to misspeculation that we
367 /// want to harden.
368 ///
369 /// We use this to avoid making changes to functions where there is nothing we
370 /// need to do to harden against misspeculation.
374 // Loads within this basic block after an LFENCE are not at risk of
375 // speculatively executing with invalid predicates from prior control
376 // flow. So break out of this block but continue scanning the function.
380 // Looking for loads only.
384 // An MFENCE is modeled as a load but isn't vulnerable to misspeculation.
388 // We found a load.
390 }
391 }
393 // No loads found.
395 }
402 // Only run if this pass is forced enabled or we detect the relevant function
403 // attribute requesting SLH.
413 // FIXME: Support for 32-bit.
417 // Nothing to do for a degenerate empty function...
420 // We support an alternative hardening technique based on a debug flag.
424 }
426 // Create a dummy debug loc to use for all the generated code here.
427 DebugLoc Loc;
432 // Do a quick scan to see if we have any checkable loads.
435 // See if we have any conditional branching blocks that we will need to trace
436 // predicate state through.
439 // If we have no interesting conditions or loads, nothing to do here.
443 // The poison value is required to be an all-ones value for many aspects of
444 // this mitigation.
451 // If we have loads being hardened and we've asked for call and ret edges to
452 // get a full fence-based mitigation, inject that fence.
454 // We need to insert an LFENCE at the start of the function to suspend any
455 // incoming misspeculation from the caller. This helps two-fold: the caller
456 // may not have been protected as this code has been, and this code gets to
457 // not take any specific action to protect across calls.
458 // FIXME: We could skip this for functions which unconditionally return
459 // a constant.
463 }
465 // If we guarded the entry with an LFENCE and have no conditionals to protect
466 // in blocks, then we're done.
468 // We may have changed the function's code at this point to insert fences.
471 // For every basic block in the function which can b
473 // Set up the predicate state by extracting it from the incoming stack
474 // pointer so we pick up any misspeculation in our caller.
477 // Otherwise, just build the predicate state itself by zeroing a register
478 // as we don't need any initial state.
482 PredStateSubReg);
494 }
496 // We're going to need to trace predicate state throughout the function's
497 // CFG. Prepare for this by setting up our initial state of PHIs with unique
498 // predecessor entries and all the initial predicate state.
501 // Track the updated values in an SSA updater to rewrite into SSA form at the
502 // end.
506 // Trace through the CFG.
509 // We may also enter basic blocks in this function via exception handling
510 // control flow. Here, if we are hardening interprocedurally, we need to
511 // re-capture the predicate state from the throwing code. In the Itanium ABI,
512 // the throw will always look like a call to __cxa_throw and will have the
513 // predicate state in the stack pointer, so extract fresh predicate state from
514 // the stack pointer and make it available in SSA.
515 // FIXME: Handle non-itanium ABI EH models.
526 }
527 }
530 // If we are going to harden calls and jumps we need to unfold their memory
531 // operands.
534 // Then we trace predicate state through the indirect branches.
537 }
539 // Now that we have the predicate state available at the start of each block
540 // in the CFG, trace it through each block, hardening vulnerable instructions
541 // as we go.
544 // Now rewrite all the uses of the pred state using the SSA updater to insert
545 // PHIs connecting the state between blocks along the CFG edges.
552 }
557 }
559 /// Implements the naive hardening approach of putting an LFENCE after every
560 /// potentially mis-predicted control flow construct.
561 ///
562 /// We include this as an alternative mostly for the purpose of comparison. The
563 /// performance impact of this is expected to be extremely severe and not
564 /// practical for any real-world users.
567 // First, we scan the function looking for blocks that are reached along edges
568 // that we might want to harden.
571 // If there are no or only one successor, nothing to do here.
575 // Skip blocks unless their terminators start with a branch. Other
576 // terminators don't seem interesting for guarding against misspeculation.
581 // Add all the non-EH-pad succossors to the blocks we want to harden. We
582 // skip EH pads because there isn't really a condition of interest on
583 // entering.
587 }
594 }
595 }
601 // Walk the function and build up a summary for each block's conditions that
602 // we need to trace through.
604 // If there are no or only one successor, nothing to do here.
608 // We want to reliably handle any conditional branch terminators in the
609 // MBB, so we manually analyze the branch. We can handle all of the
610 // permutations here, including ones that analyze branch cannot.
611 //
612 // The approach is to walk backwards across the terminators, resetting at
613 // any unconditional non-indirect branch, and track all conditional edges
614 // to basic blocks as well as the fallthrough or unconditional successor
615 // edge. For each conditional edge, we track the target and the opposite
616 // condition code in order to inject a "no-op" cmov into that successor
617 // that will harden the predicate. For the fallthrough/unconditional
618 // edge, we inject a separate cmov for each conditional branch with
619 // matching condition codes. This effectively implements an "and" of the
620 // condition flags, even if there isn't a single condition flag that would
621 // directly implement that. We don't bother trying to optimize either of
622 // these cases because if such an optimization is possible, LLVM should
623 // have optimized the conditional *branches* in that way already to reduce
624 // instruction count. This late, we simply assume the minimal number of
625 // branch instructions is being emitted and use that to guide our cmov
626 // insertion.
630 // Now walk backwards through the terminators and build up successors they
631 // reach and the conditions.
633 // Once we've handled all the terminators, we're done.
637 // If we see a non-branch terminator, we can't handle anything so bail.
641 }
643 // If we see an unconditional branch, reset our state, clear any
644 // fallthrough, and set this is the "else" successor.
649 }
651 // If we get an invalid condition, we have an indirect branch or some
652 // other unanalyzable "fallthrough" case. We model this as a nullptr for
653 // the destination so we can still guard any conditional successors.
654 // Consider code sequences like:
655 // ```
656 // jCC L1
657 // jmpq *%rax
658 // ```
659 // We still want to harden the edge to `L1`.
664 }
666 // We have a vanilla conditional branch, add it to our list.
668 }
674 }
677 }
680 }
682 /// Trace the predicate state through the CFG, instrumenting each conditional
683 /// branch such that misspeculation through an edge will poison the predicate
684 /// state.
685 ///
686 /// Returns the list of inserted CMov instructions so that they can have their
687 /// uses of the predicate state rewritten into proper SSA form once it is
688 /// complete.
692 // Collect the inserted cmov instructions so we can rewrite their uses of the
693 // predicate state into SSA form.
696 // Now walk all of the basic blocks looking for ones that end in conditional
697 // jumps where we need to update this register along each edge.
707 // Compute the non-conditional successor as either the target of any
708 // unconditional branch or the layout successor.
715 // Count how many edges there are to any given successor.
722 // A lambda to insert cmov instructions into a block checking all of the
723 // condition codes in a sequence.
728 // First, we split the edge to insert the checking block into a safe
729 // location.
732 ? Succ
739 // Now insert the cmovs to implement the checks.
742 "Should never have a PHI in the initial checking block as it "
745 // We will wire each cmov to each other, but need to start with the
746 // incoming pred state.
754 // Note that we intentionally use an empty debug location so that
755 // this picks up the preceding location.
761 // If this is the last cmov and the EFLAGS weren't originally
762 // live-in, mark them as killed.
770 // The first one of the cmovs will be using the top level
771 // `PredStateReg` and need to get rewritten into SSA form.
775 // The next cmov should start from this one's def.
777 }
779 // And put the last one into the available values for SSA form of our
780 // predicate state.
782 };
796 // Decrement the successor count now that we've split one of the edges.
797 // We need to keep the count of edges to the successor accurate in order
798 // to know above when to *replace* the successor in the CFG vs. just
799 // adding the new successor.
801 }
803 // Since we may have split edges and changed the number of successors,
804 // normalize the probabilities. This avoids doing it each time we split an
805 // edge.
808 // Finally, we need to insert cmovs into the "fallthrough" edge. Here, we
809 // need to intersect the other condition codes. We can do this by just
810 // doing a cmov for each one.
812 // If we have no fallthrough to protect (perhaps it is an indirect jump?)
813 // just skip this and continue.
817 "We should never have more than one edge to the unconditional "
818 "successor at this point because every other edge must have been "
821 // Sort and unique the codes to minimize them.
826 // Build a checking version of the successor.
829 }
832 }
834 /// Compute the register class for the unfolded load.
835 ///
836 /// FIXME: This should probably live in X86InstrInfo, potentially by adding
837 /// a way to unfold into a newly created vreg rather than requiring a register
838 /// input.
847 }
853 // Grab a reference and increment the iterator so we can remove this
854 // instruction if needed without disturbing the iteration.
857 // Must either be a call or a branch.
860 // We only care about loading variants of these instructions.
871 }
879 // We cannot mitigate far jumps or calls, but we also don't expect them
880 // to be vulnerable to Spectre v1.2 style attacks.
900 // Use the generic unfold logic now that we know we're dealing with
901 // expected instructions.
902 // FIXME: We don't have test coverage for all of these!
909 }
912 // If we were able to compute an unfolded reg class, any failure here
913 // is just a programming error so just assert.
920 // Now stitch the new instructions into place and erase the old one.
929 }
930 });
932 }
933 }
935 }
936 }
938 /// Trace the predicate state through indirect branches, instrumenting them to
939 /// poison the state if a target is reached that does not match the expected
940 /// target.
941 ///
942 /// This is designed to mitigate Spectre variant 1 attacks where an indirect
943 /// branch is trained to predict a particular target and then mispredicts that
944 /// target in a way that can leak data. Despite using an indirect branch, this
945 /// is really a variant 1 style attack: it does not steer execution to an
946 /// arbitrary or attacker controlled address, and it does not require any
947 /// special code executing next to the victim. This attack can also be mitigated
948 /// through retpolines, but those require either replacing indirect branches
949 /// with conditional direct branches or lowering them through a device that
950 /// blocks speculation. This mitigation can replace these retpoline-style
951 /// mitigations for jump tables and other indirect branches within a function
952 /// when variant 2 isn't a risk while allowing limited speculation. Indirect
953 /// calls, however, cannot be mitigated through this technique without changing
954 /// the ABI in a fundamental way.
958 // We use the SSAUpdater to insert PHI nodes for the target addresses of
959 // indirect branches. We don't actually need the full power of the SSA updater
960 // in this particular case as we always have immediately available values, but
961 // this avoids us having to re-implement the PHI construction logic.
965 // Track which blocks were terminated with an indirect branch.
968 // We need to know what blocks end up reached via indirect branches. We
969 // expect this to be a subset of those whose address is taken and so track it
970 // directly via the CFG.
973 // Walk all the blocks which end in an indirect branch and make the
974 // target address available.
976 // Find the last terminator.
984 // No terminator or non-branch terminator.
991 // Direct branch or conditional branch (leading to fallthrough).
997 // We cannot mitigate far jumps or calls, but we also don't expect them
998 // to be vulnerable to Spectre v1.2 or v2 (self trained) style attacks.
1007 // Mostly as documentation.
1019 }
1021 // We have definitely found an indirect branch. Verify that there are no
1022 // preceding conditional branches as we don't yet support that.
1025 })) {
1032 }
1033 });
1035 }
1037 // Make the target register an available value for this block.
1041 // Add all the successors to our target candidates.
1044 }
1046 // Keep track of the cmov instructions we insert so we can return them.
1049 // If we didn't find any indirect branches with targets, nothing to do here.
1053 // We found indirect branches and targets that need to be instrumented to
1054 // harden loads within them. Walk the blocks of the function (to get a stable
1055 // ordering) and instrument each target of an indirect branch.
1057 // Skip the blocks that aren't candidate targets.
1061 // We don't expect EH pads to ever be reached via an indirect branch. If
1062 // this is desired for some reason, we could simply skip them here rather
1063 // than asserting.
1067 // We should never end up threading EFLAGS into a block to harden
1068 // conditional jumps as there would be an additional successor via the
1069 // indirect branch. As a consequence, all such edges would be split before
1070 // reaching here, and the inserted block will handle the EFLAGS-based
1071 // hardening.
1075 // We can't handle having non-indirect edges into this block unless this is
1076 // the only successor and we can synthesize the necessary target address.
1078 // If we've already handled this by extracting the target directly,
1079 // nothing to do.
1083 // Otherwise, we have to be the only successor. We generally expect this
1084 // to be true as conditional branches should have had a critical edge
1085 // split already. We don't however need to worry about EH pad successors
1086 // as they'll happily ignore the target and their hardening strategy is
1087 // resilient to all ways in which they could be reached speculatively.
1090 })) {
1096 });
1099 }
1101 // Now we need to compute the address of this block and install it as a
1102 // synthetic target in the predecessor. We do this at the bottom of the
1103 // predecessor.
1108 // Directly materialize it into an immediate.
1118 TargetReg)
1128 }
1129 // And make this available.
1131 }
1133 // Materialize the needed SSA value of the target. Note that we need the
1134 // middle of the block as this block might at the bottom have an indirect
1135 // branch back to itself. We can do this here because at this point, every
1136 // predecessor of this block has an available value. This is basically just
1137 // automating the construction of a PHI node for this target.
1140 // Insert a comparison of the incoming target register with this block's
1141 // address. This also requires us to mark the block as having its address
1142 // taken explicitly.
1147 // Check directly against a relocated immediate when we can.
1155 // Otherwise compute the address into a register first.
1173 }
1175 // Now cmov over the predicate if the comparison wasn't equal.
1189 // And put the new value into the available values for SSA form of our
1190 // predicate state.
1192 }
1194 // Return all the newly inserted cmov instructions of the predicate state.
1196 }
1198 /// Returns true if the instruction has no behavior (specified or otherwise)
1199 /// that is based on the value of any of its register operands
1200 ///
1201 /// A classical example of something that is inherently not data invariant is an
1202 /// indirect jump -- the destination is loaded into icache based on the bits set
1203 /// in the jump destination register.
1204 ///
1205 /// FIXME: This should become part of our instruction tables.
1209 // By default, assume that the instruction is not data invariant.
1212 // Some target-independent operations that trivially lower to data-invariant
1213 // instructions.
1219 // On x86 it is believed that imul is constant time w.r.t. the loaded data.
1220 // However, they set flags and are perhaps the most surprisingly constant
1221 // time operations so we call them out here separately.
1232 // Bit scanning and counting instructions that are somewhat surprisingly
1233 // constant time as they scan across bits and do other fairly complex
1234 // operations like popcnt, but are believed to be constant time on x86.
1235 // However, these set flags.
1252 // Bit manipulation instructions are effectively combinations of basic
1253 // arithmetic ops, and should still execute in constant time. These also
1254 // set flags.
1278 // Bit extracting and clearing instructions should execute in constant time,
1279 // and set flags.
1287 // Shift and rotate.
1308 // Basic arithmetic is constant time on the input but does set flags.
1337 // Arithmetic with just 32-bit and 64-bit variants and no immediates.
1341 // Unary arithmetic operations.
1345 // Check whether the EFLAGS implicit-def is dead. We assume that this will
1346 // always find the implicit-def because this code should only be reached
1347 // for instructions that do in fact implicitly def this.
1349 // If we would clobber EFLAGS that are used, just bail for now.
1353 }
1355 // Otherwise, fallthrough to handle these the same as instructions that
1356 // don't set EFLAGS.
1357 LLVM_FALLTHROUGH;
1359 // Unlike other arithmetic, NOT doesn't set EFLAGS.
1362 // Various move instructions used to zero or sign extend things. Note that we
1363 // intentionally don't support the _NOREX variants as we can't handle that
1364 // register constraint anyways.
1373 // Arithmetic instructions that are both constant time and don't set flags.
1383 // LEA doesn't actually access memory, and its arithmetic is constant time.
1389 }
1390 }
1392 /// Returns true if the instruction has no behavior (specified or otherwise)
1393 /// that is based on the value loaded from memory or the value of any
1394 /// non-address register operands.
1395 ///
1396 /// For example, if the latency of the instruction is dependent on the
1397 /// particular bits set in any of the registers *or* any of the bits loaded from
1398 /// memory.
1399 ///
1400 /// A classical example of something that is inherently not data invariant is an
1401 /// indirect jump -- the destination is loaded into icache based on the bits set
1402 /// in the jump destination register.
1403 ///
1404 /// FIXME: This should become part of our instruction tables.
1408 // By default, assume that the load will immediately leak.
1411 // On x86 it is believed that imul is constant time w.r.t. the loaded data.
1412 // However, they set flags and are perhaps the most surprisingly constant
1413 // time operations so we call them out here separately.
1424 // Bit scanning and counting instructions that are somewhat surprisingly
1425 // constant time as they scan across bits and do other fairly complex
1426 // operations like popcnt, but are believed to be constant time on x86.
1427 // However, these set flags.
1444 // Bit manipulation instructions are effectively combinations of basic
1445 // arithmetic ops, and should still execute in constant time. These also
1446 // set flags.
1470 // Bit extracting and clearing instructions should execute in constant time,
1471 // and set flags.
1479 // Basic arithmetic is constant time on the input but does set flags.
1514 // Check whether the EFLAGS implicit-def is dead. We assume that this will
1515 // always find the implicit-def because this code should only be reached
1516 // for instructions that do in fact implicitly def this.
1518 // If we would clobber EFLAGS that are used, just bail for now.
1522 }
1524 // Otherwise, fallthrough to handle these the same as instructions that
1525 // don't set EFLAGS.
1526 LLVM_FALLTHROUGH;
1528 // Integer multiply w/o affecting flags is still believed to be constant
1529 // time on x86. Called out separately as this is among the most surprising
1530 // instructions to exhibit that behavior.
1534 // Arithmetic instructions that are both constant time and don't set flags.
1544 // Conversions are believed to be constant time and don't set flags.
1555 // AVX512 added unsigned integer conversions.
1565 // Loads to register don't set flags.
1585 }
1586 }
1590 // Check if EFLAGS are alive by seeing if there is a def of them or they
1591 // live-in, and then seeing if that def is in turn used.
1594 // If the def is dead, then EFLAGS is not live.
1598 // Otherwise we've def'ed it, and it is live.
1600 }
1601 // While at this instruction, also check if we use and kill EFLAGS
1602 // which means it isn't live.
1605 }
1607 // If we didn't find anything conclusive (neither definitely alive or
1608 // definitely dead) return whether it lives into the block.
1610 }
1612 /// Trace the predicate state through each of the blocks in the function,
1613 /// hardening everything necessary along the way.
1614 ///
1615 /// We call this routine once the initial predicate state has been established
1616 /// for each basic block in the function in the SSA updater. This routine traces
1617 /// it through the instructions within each basic block, and for non-returning
1618 /// blocks informs the SSA updater about the final state that lives out of the
1619 /// block. Along the way, it hardens any vulnerable instruction using the
1620 /// currently valid predicate state. We have to do these two things together
1621 /// because the SSA updater only works across blocks. Within a block, we track
1622 /// the current predicate state directly and update it as it changes.
1623 ///
1624 /// This operates in two passes over each block. First, we analyze the loads in
1625 /// the block to determine which strategy will be used to harden them: hardening
1626 /// the address or hardening the loaded value when loaded into a register
1627 /// amenable to hardening. We have to process these first because the two
1628 /// strategies may interact -- later hardening may change what strategy we wish
1629 /// to use. We also will analyze data dependencies between loads and avoid
1630 /// hardening those loads that are data dependent on a load with a hardened
1631 /// address. We also skip hardening loads already behind an LFENCE as that is
1632 /// sufficient to harden them against misspeculation.
1633 ///
1634 /// Second, we actively trace the predicate state through the block, applying
1635 /// the hardening steps we determined necessary in the first pass as we go.
1636 ///
1637 /// These two passes are applied to each basic block. We operate one block at a
1638 /// time to simplify reasoning about reachability and sequencing.
1648 // Track the set of load-dependent registers through the basic block. Because
1649 // the values of these registers have an existing data dependency on a loaded
1650 // value which we would have checked, we can omit any checks on them.
1654 // The first pass over the block: collect all the loads which can have their
1655 // loaded value hardened and all the loads that instead need their address
1656 // hardened. During this walk we propagate load dependence for address
1657 // hardened loads and also look for LFENCE to stop hardening wherever
1658 // possible. When deciding whether or not to harden the loaded value or not,
1659 // we check to see if any registers used in the address will have been
1660 // hardened at this point and if so, harden any remaining address registers
1661 // as that often successfully re-uses hardened addresses and minimizes
1662 // instructions.
1663 //
1664 // FIXME: We should consider an aggressive mode where we continue to keep as
1665 // many loads value hardened even when some address register hardening would
1666 // be free (due to reuse).
1667 //
1668 // Note that we only need this pass if we are actually hardening loads.
1671 // We naively assume that all def'ed registers of an instruction have
1672 // a data dependency on all of their operands.
1673 // FIXME: Do a more careful analysis of x86 to build a conservative
1674 // model here.
1677 }))
1682 // Both Intel and AMD are guiding that they will change the semantics of
1683 // LFENCE to be a speculation barrier, so if we see an LFENCE, there is
1684 // no more need to guard things in this block.
1688 // If this instruction cannot load, nothing to do.
1692 // Some instructions which "load" are trivially safe or unimportant.
1696 // Extract the memory operand information about this instruction.
1697 // FIXME: This doesn't handle loading pseudo instructions which we often
1698 // could handle with similarly generic logic. We probably need to add an
1699 // MI-layer routine similar to the MC-layer one we use here which maps
1700 // pseudos much like this maps real instructions.
1708 }
1717 // If we have at least one (non-frame-index, non-RIP) register operand,
1718 // and neither operand is load-dependent, we need to check the load.
1727 // No register operands!
1730 // If any register operand is dependent, this load is dependent and we
1731 // needn't check it.
1732 // FIXME: Is this true in the case where we are hardening loads after
1733 // they complete? Unclear, need to investigate.
1738 // If post-load hardening is enabled, this load is compatible with
1739 // post-load hardening, and we aren't already going to harden one of the
1740 // address registers, queue it up to be hardened post-load. Notably,
1741 // even once hardened this won't introduce a useful dependency that
1742 // could prune out subsequent loads.
1751 }
1753 // Record this instruction for address hardening and record its register
1754 // operands as being address-hardened.
1764 }
1766 // Now re-walk the instructions in the basic block, and apply whichever
1767 // hardening strategy we have elected. Note that we do this in a second
1768 // pass specifically so that we have the complete set of instructions for
1769 // which we will do post-load hardening and can defer it in certain
1770 // circumstances.
1773 // We cannot both require hardening the def of a load and its address.
1777 // Check if this is a load whose address needs to be hardened.
1791 }
1793 // Test if this instruction is one of our post load instructions (and
1794 // remove it from the set if so).
1798 // If this is a data-invariant load, we want to try and sink any
1799 // hardening as far as possible.
1801 // Sink the instruction we'll need to harden as far as we can down
1802 // the graph.
1805 // If we managed to sink this instruction, update everything so we
1806 // harden that instruction when we reach it in the instruction
1807 // sequence.
1809 // If in sinking there was no instruction needing to be hardened,
1810 // we're done.
1814 // Otherwise, add this to the set of defs we harden.
1817 }
1818 }
1822 // Mark the resulting hardened register as such so we don't re-harden.
1826 }
1828 // Check for an indirect call or branch that may need its input hardened
1829 // even if we couldn't find the specific load used, or were able to
1830 // avoid hardening it for some reason. Note that here we cannot break
1831 // out afterward as we may still need to handle any call aspect of this
1832 // instruction.
1835 }
1837 // After we finish hardening loads we handle interprocedural hardening if
1838 // enabled and relevant for this instruction.
1844 // If this is a direct return (IE, not a tail call) just directly harden
1845 // it.
1849 }
1851 // Otherwise we have a call. We need to handle transferring the predicate
1852 // state into a call and recovering it after the call returns (unless this
1853 // is a tail call).
1856 }
1863 // Currently, we only track data-dependent loads within a basic block.
1864 // FIXME: We should see if this is necessary or if we could be more
1865 // aggressive here without opening up attack avenues.
1867 }
1868 }
1870 /// Save EFLAGS into the returned GPR. This can in turn be restored with
1871 /// `restoreEFLAGS`.
1872 ///
1873 /// Note that LLVM can only lower very simple patterns of saved and restored
1874 /// EFLAGS registers. The restore should always be within the same basic block
1875 /// as the save so that no PHI nodes are inserted.
1878 DebugLoc Loc) {
1879 // FIXME: Hard coding this to a 32-bit register class seems weird, but matches
1880 // what instruction selection does.
1882 // We directly copy the FLAGS register and rely on later lowering to clean
1883 // this up into the appropriate setCC instructions.
1887 }
1889 /// Restore EFLAGS from the provided GPR. This should be produced by
1890 /// `saveEFLAGS`.
1891 ///
1892 /// This must be done within the same basic block as the save in order to
1893 /// reliably lower.
1899 }
1901 /// Takes the current predicate state (in a register) and merges it into the
1902 /// stack pointer. The state is essentially a single bit, but we merge this in
1903 /// a way that won't form non-canonical pointers and also will be preserved
1904 /// across normal stack adjustments.
1909 // FIXME: This hard codes a shift distance based on the number of bits needed
1910 // to stay canonical on 64-bit. We should compute this somehow and support
1911 // 32-bit as part of that.
1922 }
1924 /// Extracts the predicate state stored in the high bits of the stack pointer.
1927 DebugLoc Loc) {
1931 // We know that the stack pointer will have any preserved predicate state in
1932 // its high bit. We just want to smear this across the other bits. Turns out,
1933 // this is exactly what an arithmetic right shift does.
1944 }
1952 // Check if EFLAGS are alive by seeing if there is a def of them or they
1953 // live-in, and then seeing if that def is in turn used.
1959 // A frame index is never a dynamically controllable load, so only
1960 // harden it if we're covering fixed address loads as well.
1965 // Some idempotent atomic operations are lowered directly to a locked
1966 // OR with 0 to the top of stack(or slightly offset from top) which uses an
1967 // explicit RSP register as the base.
1974 // For both RIP-relative addressed loads or absolute loads, we cannot
1975 // meaningfully harden them because the address being loaded has no
1976 // dynamic component.
1977 //
1978 // FIXME: When using a segment base (like TLS does) we end up with the
1979 // dynamic address being the base plus -1 because we can't mutate the
1980 // segment register here. This allows the signed 32-bit offset to point at
1981 // valid segment-relative addresses and load them successfully.
1990 }
2003 // Remove any registers that have alreaded been checked.
2005 // See if this operand's register has already been checked.
2008 // Not checked, so retain this one.
2011 // Otherwise, we can directly update this operand and remove it.
2014 });
2015 // If there are none left, we're done.
2019 // Compute the current predicate state.
2024 // If EFLAGS are live and we don't have access to instructions that avoid
2025 // clobbering EFLAGS we need to save and restore them. This in turn makes
2026 // the EFLAGS no longer live.
2031 }
2038 // If this is a vector register, we'll need somewhat custom logic to handle
2039 // hardening it.
2045 // Move our state into a vector register.
2046 // FIXME: We could skip this at the cost of longer encodings with AVX-512
2047 // but that doesn't seem likely worth it.
2056 // Broadcast it across the vector register.
2061 VBStateReg)
2068 // Merge our potential poison state into the value with a vector or.
2086 // Broadcast our state into a vector register.
2099 // Merge our potential poison state into the value with a vector or.
2109 // FIXME: Need to support GR32 here for 32-bit code.
2114 // Merge our potential poison state into the value with an or.
2122 // We need to avoid touching EFLAGS so shift out all but the least
2123 // significant bit using the instruction that doesn't update flags.
2132 }
2133 }
2135 // Record this register as checked and update the operand.
2141 }
2143 // And restore the flags if needed.
2146 }
2153 // See if we can sink hardening the loaded value.
2158 // We need to find a single use which we can sink the check. We can
2159 // primarily do this because many uses may already end up checked on their
2160 // own.
2163 // If we're already going to harden this use, it is data invariant and
2164 // within our block.
2167 // If we've already decided to harden a non-load, we must have sunk
2168 // some other post-load hardened instruction to it and it must itself
2169 // be data-invariant.
2173 }
2175 // Otherwise, this is a load and the load component can't be data
2176 // invariant so check how this register is being used.
2189 // The load uses the register as part of its address making it not
2190 // invariant.
2194 }
2197 // We already have a single use, this would make two. Bail.
2200 // If this single use isn't data invariant, isn't in this block, or has
2201 // interfering EFLAGS, we can't sink the hardening to it.
2205 // If this instruction defines multiple registers bail as we won't harden
2206 // all of them.
2210 // If this register isn't a virtual register we can't walk uses of sanely,
2211 // just bail. Also check that its register class is one of the ones we
2212 // can harden.
2219 }
2221 // If SingleUseMI is still null, there is no use that needs its own
2222 // checking. Otherwise, it is the single use that needs checking.
2224 };
2228 // Update which MI we're checking now.
2232 }
2235 }
2241 // We don't support post-load hardening of vectors.
2244 // If this register class is explicitly constrained to a class that doesn't
2245 // require REX prefix, we may not be able to satisfy that constraint when
2246 // emitting the hardening instructions, so bail out here.
2247 // FIXME: This seems like a pretty lame hack. The way this comes up is when we
2248 // end up both with a NOREX and REX-only register as operands to the hardening
2249 // instructions. It would be better to fix that code to handle this situation
2250 // rather than hack around it in this way.
2261 }
2263 /// Harden a value in a register.
2264 ///
2265 /// This is the low-level logic to fully harden a value sitting in a register
2266 /// against leaking during speculative execution.
2267 ///
2268 /// Unlike hardening an address that is used by a load, this routine is required
2269 /// to hide *all* incoming bits in the register.
2270 ///
2271 /// `Reg` must be a virtual register. Currently, it is required to be a GPR no
2272 /// larger than the predicate state register. FIXME: We should support vector
2273 /// registers here by broadcasting the predicate state.
2274 ///
2275 /// The new, hardened virtual register is returned. It will have the same
2276 /// register class as `Reg`.
2279 DebugLoc Loc) {
2288 // FIXME: Need to teach this about 32-bit mode.
2296 }
2316 }
2318 /// Harden a load by hardening the loaded value in the defined register.
2319 ///
2320 /// We can harden a non-leaking load into a register without touching the
2321 /// address by just hiding all of the loaded bits during misspeculation. We use
2322 /// an `or` instruction to do this because we set up our poison value as all
2323 /// ones. And the goal is just for the loaded bits to not be exposed to
2324 /// execution and coercing them to one is sufficient.
2325 ///
2326 /// Returns the newly hardened register.
2335 // Because we want to completely replace the uses of this def'ed value with
2336 // the hardened value, create a dedicated new register that will only be used
2337 // to communicate the unhardened value to the hardening.
2341 // Now harden this register's value, getting a hardened reg that is safe to
2342 // use. Note that we insert the instructions to compute this *after* the
2343 // defining instruction, not before it.
2347 // Finally, replace the old register (which now only has the uses of the
2348 // original def) with the hardened register.
2353 }
2355 /// Harden a return instruction.
2356 ///
2357 /// Returns implicitly perform a load which we need to harden. Without hardening
2358 /// this load, an attacker my speculatively write over the return address to
2359 /// steer speculation of the return to an attacker controlled address. This is
2360 /// called Spectre v1.1 or Bounds Check Bypass Store (BCBS) and is described in
2361 /// this paper:
2362 /// https://people.csail.mit.edu/vlk/spectre11.pdf
2363 ///
2364 /// We can harden this by introducing an LFENCE that will delay any load of the
2365 /// return address until prior instructions have retired (and thus are not being
2366 /// speculated), or we can harden the address used by the implicit load: the
2367 /// stack pointer.
2368 ///
2369 /// If we are not using an LFENCE, hardening the stack pointer has an additional
2370 /// benefit: it allows us to pass the predicate state accumulated in this
2371 /// function back to the caller. In the absence of a BCBS attack on the return,
2372 /// the caller will typically be resumed and speculatively executed due to the
2373 /// Return Stack Buffer (RSB) prediction which is very accurate and has a high
2374 /// priority. It is possible that some code from the caller will be executed
2375 /// speculatively even during a BCBS-attacked return until the steering takes
2376 /// effect. Whenever this happens, the caller can recover the (poisoned)
2377 /// predicate state from the stack pointer and continue to harden loads.
2384 // No need to fence here as we'll fence at the return site itself. That
2385 // handles more cases than we can handle here.
2388 // Take our predicate state, shift it to the high 17 bits (so that we keep
2389 // pointers canonical) and merge it into RSP. This will allow the caller to
2390 // extract it when we return (speculatively).
2392 }
2394 /// Trace the predicate state through a call.
2395 ///
2396 /// There are several layers of this needed to handle the full complexity of
2397 /// calls.
2398 ///
2399 /// First, we need to send the predicate state into the called function. We do
2400 /// this by merging it into the high bits of the stack pointer.
2401 ///
2402 /// For tail calls, this is all we need to do.
2403 ///
2404 /// For calls where we might return and resume the control flow, we need to
2405 /// extract the predicate state from the high bits of the stack pointer after
2406 /// control returns from the called function.
2407 ///
2408 /// We also need to verify that we intended to return to this location in the
2409 /// code. An attacker might arrange for the processor to mispredict the return
2410 /// to this valid but incorrect return address in the program rather than the
2411 /// correct one. See the paper on this attack, called "ret2spec" by the
2412 /// researchers, here:
2413 /// https://christian-rossow.de/publications/ret2spec-ccs2018.pdf
2414 ///
2415 /// The way we verify that we returned to the correct location is by preserving
2416 /// the expected return address across the call. One technique involves taking
2417 /// advantage of the red-zone to load the return address from `8(%rsp)` where it
2418 /// was left by the RET instruction when it popped `%rsp`. Alternatively, we can
2419 /// directly save the address into a register that will be preserved across the
2420 /// call. We compare this intended return address against the address
2421 /// immediately following the call (the observed return address). If these
2422 /// mismatch, we have detected misspeculation and can poison our predicate
2423 /// state.
2433 // Tail call, we don't return to this function.
2434 // FIXME: We should also handle noreturn calls.
2437 // We don't need to fence before the call because the function should fence
2438 // in its entry. However, we do need to fence after the call returns.
2439 // Fencing before the return doesn't correctly handle cases where the return
2440 // itself is mispredicted.
2445 }
2447 // First, we transfer the predicate state into the called function by merging
2448 // it into the stack pointer. This will kill the current def of the state.
2452 // If this call is also a return, it is a tail call and we don't need anything
2453 // else to handle it so just return. Also, if there are no further
2454 // instructions and no successors, this call does not return so we can also
2455 // bail.
2459 // Create a symbol to track the return address and attach it to the call
2460 // machine instruction. We will lower extra symbols attached to call
2461 // instructions as label immediately following the call.
2470 // If we have no red zones or if the function returns twice (possibly without
2471 // using the `ret` instruction) like setjmp, we need to save the expected
2472 // return address prior to the call.
2475 // If we don't have red zones, we need to compute the expected return
2476 // address prior to the call and store it in a register that lives across
2477 // the call.
2478 //
2479 // In some ways, this is doubly satisfying as a mitigation because it will
2480 // also successfully detect stack smashing bugs in some cases (typically,
2481 // when a callee-saved register is used and the callee doesn't push it onto
2482 // the stack). But that isn't our primary goal, so we only use it as
2483 // a fallback.
2484 //
2485 // FIXME: It isn't clear that this is reliable in the face of
2486 // rematerialization in the register allocator. We somehow need to force
2487 // that to not occur for this particular instruction, and instead to spill
2488 // or otherwise preserve the value computed *prior* to the call.
2489 //
2490 // FIXME: It is even less clear why MachineCSE can't just fold this when we
2491 // end up having to use identical instructions both before and after the
2492 // call to feed the comparison.
2505 }
2506 }
2508 // Step past the call to handle when it returns.
2511 // If we didn't pre-compute the expected return address into a register, then
2512 // red zones are enabled and the return address is still available on the
2513 // stack immediately after the call. As the very first instruction, we load it
2514 // into a register.
2522 // the return address is 8-bytes past it.
2524 }
2526 // Now we extract the callee's predicate state from the stack pointer.
2529 // Test the expected return address against our actual address. If we can
2530 // form this basic block's address as an immediate, this is easy. Otherwise
2531 // we compute it.
2534 // FIXME: Could we fold this with the load? It would require careful EFLAGS
2535 // management.
2550 }
2552 // Now conditionally update the predicate state we just extracted if we ended
2553 // up at a different return address than expected.
2567 }
2569 /// An attacker may speculatively store over a value that is then speculatively
2570 /// loaded and used as the target of an indirect call or jump instruction. This
2571 /// is called Spectre v1.2 or Bounds Check Bypass Store (BCBS) and is described
2572 /// in this paper:
2573 /// https://people.csail.mit.edu/vlk/spectre11.pdf
2574 ///
2575 /// When this happens, the speculative execution of the call or jump will end up
2576 /// being steered to this attacker controlled address. While most such loads
2577 /// will be adequately hardened already, we want to ensure that they are
2578 /// definitively treated as needing post-load hardening. While address hardening
2579 /// is sufficient to prevent secret data from leaking to the attacker, it may
2580 /// not be sufficient to prevent an attacker from steering speculative
2581 /// execution. We forcibly unfolded all relevant loads above and so will always
2582 /// have an opportunity to post-load harden here, we just need to scan for cases
2583 /// not already flagged and add them.
2594 // We don't need to harden either far calls or far jumps as they are
2595 // safe from Spectre.
2600 }
2602 // We should never see a loading instruction at this point, as those should
2603 // have been unfolded.
2606 // If the first operand isn't a register, this is a branch or call
2607 // instruction with an immediate operand which doesn't need to be hardened.
2611 // For all of these, the target register is the first operand of the
2612 // instruction.
2616 // Try to lookup a hardened version of this register. We retain a reference
2617 // here as we want to update the map to track any newly computed hardened
2618 // register.
2621 // If we don't have a hardened register yet, compute one. Otherwise, just use
2622 // the already hardened register.
2623 //
2624 // FIXME: It is a little suspect that we use partially hardened registers that
2625 // only feed addresses. The complexity of partial hardening with SHRX
2626 // continues to pile up. Should definitively measure its value and consider
2627 // eliminating it.
2632 // Set the target operand to the hardened register.
2636 }
2645 }