70 #define PASS_KEY "x86-lvi-load"
71 #define DEBUG_TYPE PASS_KEY
73 STATISTIC(NumFences,
"Number of LFENCEs inserted for LVI mitigation");
74 STATISTIC(NumFunctionsConsidered,
"Number of functions analyzed");
75 STATISTIC(NumFunctionsMitigated,
"Number of functions for which mitigations "
77 STATISTIC(NumGadgets,
"Number of LVI gadgets detected during analysis");
85 cl::desc(
"Don't treat conditional branches as disclosure gadgets. This "
86 "may improve performance, at the cost of security."),
92 "For each function, emit a dot graph depicting potential LVI gadgets"),
97 cl::desc(
"For each function, emit a dot graph depicting potential LVI "
98 "gadgets, and do not insert any fences"),
103 cl::desc(
"For each function, emit a dot graph to stdout depicting "
104 "potential LVI gadgets, used for testing purposes only"),
109 unsigned int *Edges,
int *EdgeValues,
110 int *CutEdges ,
unsigned int EdgesSize);
116 static constexpr
int GadgetEdgeSentinel = -1;
117 static constexpr
MachineInstr *
const ArgNodeSentinel =
nullptr;
120 using Node =
typename GraphT::Node;
121 using Edge =
typename GraphT::Edge;
122 using size_type =
typename GraphT::size_type;
123 MachineGadgetGraph(std::unique_ptr<Node[]> Nodes,
124 std::unique_ptr<Edge[]> Edges, size_type NodesSize,
125 size_type EdgesSize,
int NumFences = 0,
int NumGadgets = 0)
127 NumFences(NumFences), NumGadgets(NumGadgets) {}
128 static inline bool isCFGEdge(
const Edge &
E) {
129 return E.getValue() != GadgetEdgeSentinel;
131 static inline bool isGadgetEdge(
const Edge &
E) {
132 return E.getValue() == GadgetEdgeSentinel;
143 return "X86 Load Value Injection (LVI) Load Hardening";
152 using Edge = MachineGadgetGraph::Edge;
153 using Node = MachineGadgetGraph::Node;
154 using EdgeSet = MachineGadgetGraph::EdgeSet;
161 std::unique_ptr<MachineGadgetGraph>
166 std::unique_ptr<MachineGadgetGraph> Graph)
const;
168 std::unique_ptr<MachineGadgetGraph> Graph)
const;
169 int elimMitigatedEdgesAndNodes(MachineGadgetGraph &
G,
172 std::unique_ptr<MachineGadgetGraph>
173 trimMitigatedEdges(std::unique_ptr<MachineGadgetGraph> Graph)
const;
175 EdgeSet &CutEdges )
const;
179 return MI && (
MI->getOpcode() == X86::LFENCE ||
180 (STI->useLVIControlFlowIntegrity() &&
MI->isCall()));
204 if (Node->getValue() == MachineGadgetGraph::ArgNodeSentinel)
209 OS << *Node->getValue();
215 if (
MI == MachineGadgetGraph::ArgNodeSentinel)
216 return "color = blue";
217 if (
MI->getOpcode() == X86::LFENCE)
218 return "color = green";
224 int EdgeVal = (*
E.getCurrent()).getValue();
226 :
"color = red, style = \"dashed\"";
232 constexpr
MachineInstr *MachineGadgetGraph::ArgNodeSentinel;
233 constexpr
int MachineGadgetGraph::GadgetEdgeSentinel;
237 void X86LoadValueInjectionLoadHardeningPass::getAnalysisUsage(
247 MachineGadgetGraph *
G) {
249 "Speculative gadgets for \"" + MF.
getName() +
"\" function");
252 bool X86LoadValueInjectionLoadHardeningPass::runOnMachineFunction(
257 if (!STI->useLVILoadHardening())
266 if (!
F.hasOptNone() && skipFunction(
F))
269 ++NumFunctionsConsidered;
270 TII = STI->getInstrInfo();
271 TRI = STI->getRegisterInfo();
273 const auto &MLI = getAnalysis<MachineLoopInfo>();
274 const auto &MDT = getAnalysis<MachineDominatorTree>();
275 const auto &MDF = getAnalysis<MachineDominanceFrontier>();
276 std::unique_ptr<MachineGadgetGraph> Graph = getGadgetGraph(MF, MLI, MDT, MDF);
278 if (Graph ==
nullptr)
289 std::string FileName =
"lvi.";
305 std::string ErrorMsg;
308 if (!ErrorMsg.empty())
315 FencesInserted = hardenLoadsWithPlugin(MF,
std::move(Graph));
317 FencesInserted = hardenLoadsWithHeuristic(MF,
std::move(Graph));
320 if (FencesInserted > 0)
321 ++NumFunctionsMitigated;
322 NumFences += FencesInserted;
323 return (FencesInserted > 0);
326 std::unique_ptr<MachineGadgetGraph>
327 X86LoadValueInjectionLoadHardeningPass::getGadgetGraph(
334 DataFlowGraph DFG{MF, *
TII, *
TRI, MDT, MDF};
340 using GraphIter =
typename GraphBuilder::BuilderNodeRef;
342 int FenceCount = 0, GadgetCount = 0;
345 if (Ref == NodeMap.
end()) {
348 return std::pair<GraphIter, bool>{
I,
true};
350 return std::pair<GraphIter, bool>{
Ref->getSecond(),
false};
361 auto AnalyzeDef = [&](NodeAddr<DefNode *> SourceDef) {
363 std::function<void(NodeAddr<DefNode *>)> AnalyzeDefUseChain =
364 [&](NodeAddr<DefNode *>
Def) {
365 if (Transmitters.
find(
Def.Id) != Transmitters.
end())
370 RegisterRef DefReg =
Def.Addr->getRegRef(DFG);
371 for (
auto UseID : L.getAllReachedUses(DefReg,
Def)) {
372 auto Use = DFG.addr<UseNode *>(UseID);
374 NodeAddr<PhiNode *> Phi =
Use.Addr->getOwner(DFG);
375 for (
const auto&
I : L.getRealUses(Phi.Id)) {
376 if (DFG.getPRI().alias(RegisterRef(
I.first), DefReg)) {
377 for (
const auto &UA :
I.second)
378 Uses.emplace(UA.first);
389 for (
auto UseID :
Uses) {
390 if (!UsesVisited.
insert(UseID).second)
393 auto Use = DFG.addr<UseNode *>(UseID);
407 if (instrUsesRegToAccessMemory(
UseMI, UseMO.
getReg()) ||
410 Transmitters[
Def.Id].push_back(
Use.Addr->getOwner(DFG).Id);
418 NodeAddr<InstrNode *> Owner{
Use.Addr->getOwner(DFG)};
420 for (
const auto &ChildDef :
422 if (!DefsVisited.
insert(ChildDef.Id).second)
426 if (
Def.Id == ChildDef.Id)
429 AnalyzeDefUseChain(ChildDef);
432 for (
auto TransmitterId : Transmitters[ChildDef.Id])
433 Transmitters[
Def.Id].push_back(TransmitterId);
439 auto &DefTransmitters = Transmitters[
Def.Id];
443 DefTransmitters.erase(
444 std::unique(DefTransmitters.begin(), DefTransmitters.end()),
445 DefTransmitters.end());
449 AnalyzeDefUseChain(SourceDef);
450 auto &SourceDefTransmitters = Transmitters[SourceDef.Id];
451 if (SourceDefTransmitters.empty())
455 ? MachineGadgetGraph::ArgNodeSentinel
456 : SourceDef.Addr->getOp().getParent();
457 auto GadgetSource = MaybeAddNode(
Source);
459 for (
auto TransmitterId : SourceDefTransmitters) {
461 auto GadgetSink = MaybeAddNode(
Sink);
463 Builder.addEdge(MachineGadgetGraph::GadgetEdgeSentinel,
464 GadgetSource.first, GadgetSink.first);
469 LLVM_DEBUG(
dbgs() <<
"Analyzing def-use chains to find gadgets\n");
471 NodeAddr<BlockNode *> EntryBlock = DFG.getFunc().Addr->getEntryBlock(DFG);
472 for (NodeAddr<PhiNode *> ArgPhi :
478 for (NodeAddr<BlockNode *> BA : DFG.getFunc().Addr->members(DFG)) {
479 for (NodeAddr<StmtNode *> SA :
480 BA.Addr->members_if(DataFlowGraph::IsCode<NodeAttrs::Stmt>, DFG)) {
485 }
else if (
MI->mayLoad()) {
493 if (GadgetCount == 0)
495 NumGadgets += GadgetCount;
505 auto BeginBB = MaybeAddNode(&*NI);
506 Builder.addEdge(ParentDepth, GI, BeginBB.first);
512 while (++NI !=
MBB->
end()) {
514 if (Ref != NodeMap.
end()) {
515 Builder.addEdge(LoopDepth, GI,
Ref->getSecond());
516 GI =
Ref->getSecond();
523 auto EndBB = MaybeAddNode(&*
T);
525 Builder.addEdge(LoopDepth, GI, EndBB.first);
530 TraverseCFG(Succ, GI, LoopDepth);
534 GraphIter ArgNode = MaybeAddNode(MachineGadgetGraph::ArgNodeSentinel).first;
535 TraverseCFG(&MF.
front(), ArgNode, 0);
536 std::unique_ptr<MachineGadgetGraph>
G{
Builder.get(FenceCount, GadgetCount)};
542 int X86LoadValueInjectionLoadHardeningPass::elimMitigatedEdgesAndNodes(
543 MachineGadgetGraph &
G, EdgeSet &ElimEdges ,
545 if (
G.NumFences > 0) {
548 for (
const Edge &
E :
G.edges()) {
549 const Node *Dest =
E.getDest();
550 if (isFence(Dest->getValue())) {
553 for (
const Edge &DE : Dest->edges())
554 ElimEdges.insert(DE);
560 int RemainingGadgets = 0;
562 for (
const Node &RootN :
G.nodes()) {
563 if (
llvm::none_of(RootN.edges(), MachineGadgetGraph::isGadgetEdge))
567 ReachableNodes.clear();
569 [&](
const Node *
N,
bool FirstNode) {
571 ReachableNodes.insert(*
N);
572 for (
const Edge &
E :
N->edges()) {
573 const Node *Dest =
E.getDest();
574 if (MachineGadgetGraph::isCFGEdge(
E) && !ElimEdges.contains(
E) &&
575 !ReachableNodes.contains(*Dest))
576 FindReachableNodes(Dest,
false);
579 FindReachableNodes(&RootN,
true);
582 for (
const Edge &
E : RootN.edges()) {
583 if (MachineGadgetGraph::isGadgetEdge(
E)) {
584 if (ReachableNodes.contains(*
E.getDest())) {
593 return RemainingGadgets;
596 std::unique_ptr<MachineGadgetGraph>
597 X86LoadValueInjectionLoadHardeningPass::trimMitigatedEdges(
598 std::unique_ptr<MachineGadgetGraph> Graph)
const {
600 EdgeSet ElimEdges{*Graph};
601 int RemainingGadgets =
602 elimMitigatedEdgesAndNodes(*Graph, ElimEdges, ElimNodes);
603 if (ElimEdges.empty() && ElimNodes.
empty()) {
604 Graph->NumFences = 0;
605 Graph->NumGadgets = RemainingGadgets;
607 Graph = GraphBuilder::trim(*Graph, ElimNodes, ElimEdges, 0 ,
613 int X86LoadValueInjectionLoadHardeningPass::hardenLoadsWithPlugin(
614 MachineFunction &MF, std::unique_ptr<MachineGadgetGraph> Graph)
const {
615 int FencesInserted = 0;
619 Graph = trimMitigatedEdges(
std::move(Graph));
621 if (Graph->NumGadgets == 0)
625 EdgeSet CutEdges{*Graph};
626 auto Nodes = std::make_unique<unsigned int[]>(Graph->nodes_size() +
628 auto Edges = std::make_unique<unsigned int[]>(Graph->edges_size());
629 auto EdgeCuts = std::make_unique<int[]>(Graph->edges_size());
630 auto EdgeValues = std::make_unique<int[]>(Graph->edges_size());
631 for (
const Node &
N : Graph->nodes()) {
632 Nodes[Graph->getNodeIndex(
N)] = Graph->getEdgeIndex(*
N.edges_begin());
634 Nodes[Graph->nodes_size()] = Graph->edges_size();
635 for (
const Edge &
E : Graph->edges()) {
636 Edges[Graph->getEdgeIndex(
E)] = Graph->getNodeIndex(*
E.getDest());
637 EdgeValues[Graph->getEdgeIndex(
E)] =
E.getValue();
639 OptimizeCut(Nodes.get(), Graph->nodes_size(), Edges.get(), EdgeValues.get(),
640 EdgeCuts.get(), Graph->edges_size());
641 for (
int I = 0;
I < Graph->edges_size(); ++
I)
648 FencesInserted += insertFences(MF, *Graph, CutEdges);
650 LLVM_DEBUG(
dbgs() <<
"Inserted " << FencesInserted <<
" fences\n");
652 Graph = GraphBuilder::trim(*Graph,
NodeSet{*Graph}, CutEdges);
655 return FencesInserted;
658 int X86LoadValueInjectionLoadHardeningPass::hardenLoadsWithHeuristic(
659 MachineFunction &MF, std::unique_ptr<MachineGadgetGraph> Graph)
const {
662 if (Graph->NumFences > 0) {
664 Graph = trimMitigatedEdges(
std::move(Graph));
668 if (Graph->NumGadgets == 0)
672 EdgeSet CutEdges{*Graph};
676 for (
const Edge &
E : Graph->edges())
677 if (MachineGadgetGraph::isCFGEdge(
E))
678 IngressEdgeMap[
E.getDest()].push_back(&
E);
688 for (
const Node &
N : Graph->nodes()) {
689 for (
const Edge &
E :
N.edges()) {
690 if (!MachineGadgetGraph::isGadgetEdge(
E))
695 for (
const Edge &EgressEdge :
N.edges())
696 if (MachineGadgetGraph::isCFGEdge(EgressEdge))
697 EgressEdges.push_back(&EgressEdge);
699 int EgressCutCost = 0, IngressCutCost = 0;
700 for (
const Edge *EgressEdge : EgressEdges)
701 if (!CutEdges.contains(*EgressEdge))
702 EgressCutCost += EgressEdge->getValue();
703 for (
const Edge *IngressEdge : IngressEdges)
704 if (!CutEdges.contains(*IngressEdge))
705 IngressCutCost += IngressEdge->getValue();
708 IngressCutCost < EgressCutCost ? IngressEdges : EgressEdges;
709 for (
const Edge *
E : EdgesToCut)
717 int FencesInserted = insertFences(MF, *Graph, CutEdges);
719 LLVM_DEBUG(
dbgs() <<
"Inserted " << FencesInserted <<
" fences\n");
721 return FencesInserted;
724 int X86LoadValueInjectionLoadHardeningPass::insertFences(
726 EdgeSet &CutEdges )
const {
727 int FencesInserted = 0;
728 for (
const Node &
N :
G.nodes()) {
729 for (
const Edge &
E :
N.edges()) {
730 if (CutEdges.contains(
E)) {
734 if (
MI == MachineGadgetGraph::ArgNodeSentinel) {
739 }
else if (
MI->isBranch()) {
740 MBB =
MI->getParent();
742 Prev =
MI->getPrevNode();
745 for (
const Edge &
E :
N.edges()) {
746 if (MachineGadgetGraph::isCFGEdge(
E))
750 MBB =
MI->getParent();
751 InsertionPt =
MI->getNextNode() ?
MI->getNextNode() :
MBB->
end();
752 Prev = InsertionPt ==
MBB->
end()
754 : InsertionPt->getPrevNode();
757 if ((InsertionPt ==
MBB->
end() || !isFence(&*InsertionPt)) &&
758 (!Prev || !isFence(Prev))) {
765 return FencesInserted;
768 bool X86LoadValueInjectionLoadHardeningPass::instrUsesRegToAccessMemory(
771 MI.getOpcode() == X86::SFENCE ||
MI.getOpcode() == X86::LFENCE)
777 if (MemRefBeginIdx < 0) {
778 LLVM_DEBUG(
dbgs() <<
"Warning: unable to obtain memory operand for loading "
789 return (BaseMO.
isReg() && BaseMO.
getReg() != X86::NoRegister &&
791 (IndexMO.
isReg() && IndexMO.
getReg() != X86::NoRegister &&
795 bool X86LoadValueInjectionLoadHardeningPass::instrUsesRegToBranch(
797 if (!
MI.isConditionalBranch())
806 "X86 LVI load hardening",
false,
false)
814 return new X86LoadValueInjectionLoadHardeningPass();