[gcc(refs/users/aoliva/heads/testme)] harden conditional branches

[Alexandre Oliva <aoliva@gcc.gnu.org>]

https://gcc.gnu.org/g:dda5b2dac9b5f18cfd961aee6fbb98bb97254563

commit dda5b2dac9b5f18cfd961aee6fbb98bb97254563
Author: Alexandre Oliva <oliva@adacore.com>
Date:   Thu Sep 23 14:22:30 2021 -0300

    harden conditional branches
    
    This patch introduces optional passes to harden conditionals used in
    branches, and in computing boolean expressions, by adding redundant
    tests of the reversed conditions, and trapping in case of unexpected
    results.  Though in abstract machines the redundant tests should never
    fail, CPUs may be led to misbehave under certain kinds of attacks,
    such as of power deprivation, and these tests reduce the likelihood of
    going too far down an unexpected execution path.
    
    
    for  gcc/ChangeLog
    
            * common.opt (fharden-compares): New.
            (fharden-conditional-branches): New.
            * doc/invoke.texi: Document new options.
            * gimple-harden-conditionals.cc: New.
            * passes.def: Add new passes.
            * tree-pass.h (make_pass_harden_compares): Declare.
            (make_pass_harden_conditional_branches): Declare.
    
    TN: U910-002

Diff:
---
 gcc/Makefile.in                   |   1 +
 gcc/common.opt                    |   8 +
 gcc/doc/invoke.texi               |  19 ++
 gcc/gimple-harden-conditionals.cc | 364 ++++++++++++++++++++++++++++++++++++++
 gcc/passes.def                    |   2 +
 gcc/tree-pass.h                   |   3 +
 6 files changed, 397 insertions(+)

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index f36ffa4740b..a79ff93dd59 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1389,6 +1389,7 @@ OBJS = \
 	gimple-if-to-switch.o \
 	gimple-iterator.o \
 	gimple-fold.o \
+	gimple-harden-conditionals.o \
 	gimple-laddress.o \
 	gimple-loop-interchange.o \
 	gimple-loop-jam.o \
diff --git a/gcc/common.opt b/gcc/common.opt
index b921f5e3b25..662d81ff346 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -1719,6 +1719,14 @@ fguess-branch-probability
 Common Var(flag_guess_branch_prob) Optimization
 Enable guessing of branch probabilities.
 
+fharden-compares
+Common Var(flag_harden_compares) Optimization
+Harden conditionals not used in branches, checking reversed conditions.
+
+fharden-conditional-branches
+Common Var(flag_harden_conditional_branches) Optimization
+Harden conditional branches by checking reversed conditions.
+
 ; Nonzero means ignore `#ident' directives.  0 means handle them.
 ; Generate position-independent code for executables if possible
 ; On SVR4 targets, it also controls whether or not to emit a
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index ba98eab68a5..3d9f37aef74 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -595,6 +595,7 @@ Objective-C and Objective-C++ Dialects}.
 -fasan-shadow-offset=@var{number}  -fsanitize-sections=@var{s1},@var{s2},... @gol
 -fsanitize-undefined-trap-on-error  -fbounds-check @gol
 -fcf-protection=@r{[}full@r{|}branch@r{|}return@r{|}none@r{|}check@r{]} @gol
+-fharden-compares -fharden-conditional-branches @gol
 -fstack-protector  -fstack-protector-all  -fstack-protector-strong @gol
 -fstack-protector-explicit  -fstack-check @gol
 -fstack-limit-register=@var{reg}  -fstack-limit-symbol=@var{sym} @gol
@@ -15489,6 +15490,24 @@ which functions and calls should be skipped from instrumentation
 Currently the x86 GNU/Linux target provides an implementation based
 on Intel Control-flow Enforcement Technology (CET).
 
+@item -fharden-compares
+@opindex fharden-compares
+For every logical test that survives gimple optimizations and is
+@emph{not} the condition in a conditional branch (for example,
+conditions tested for conditional moves, or to store in boolean
+variables), emit extra code to compute and verify the reversed
+condition, and to call @code{__builtin_trap} if the results do not
+match.  Use with @samp{-fharden-conditional-branches} to cover all
+conditionals.
+
+@item -fharden-conditional-branches
+@opindex fharden-conditional-branches
+For every non-vectorized conditional branch that survives gimple
+optimizations, emit extra code to compute and verify the reversed
+condition, and to call @code{__builtin_trap} if the result is
+unexpected.  Use with @samp{-fharden-compares} to cover all
+conditionals.
+
 @item -fstack-protector
 @opindex fstack-protector
 Emit extra code to check for buffer overflows, such as stack smashing
diff --git a/gcc/gimple-harden-conditionals.cc b/gcc/gimple-harden-conditionals.cc
new file mode 100644
index 00000000000..3fe02850916
--- /dev/null
+++ b/gcc/gimple-harden-conditionals.cc
@@ -0,0 +1,364 @@
+/* Harden conditionals.
+   Copyright (C) 2021 Free Software Foundation, Inc.
+   Contributed by Alexandre Oliva <oliva@adacore.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "fold-const.h"
+#include "gimple.h"
+#include "gimplify.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "basic-block.h"
+#include "cfghooks.h"
+#include "cfgloop.h"
+#include "diagnostic.h"
+#include "intl.h"
+
+namespace {
+
+/* This pass introduces redundant, but reversed conditionals at every
+   compare, be it used for conditional branches, other conditional
+   operations, or for boolean computation.  This doesn't make sense
+   for abstract CPUs, but this kind of hardening may avoid undesirable
+   execution paths on CPUs under such attacks as of power
+   deprivation.  */
+
+/* Define a pass to harden conditionals other than branches.  */
+const pass_data pass_data_harden_compares = {
+  GIMPLE_PASS,
+  "hardcmp",
+  OPTGROUP_NONE,
+  TV_NONE,
+  PROP_cfg | PROP_ssa, // properties_required
+  0,	    // properties_provided
+  0,	    // properties_destroyed
+  0,	    // properties_start
+  TODO_update_ssa
+  | TODO_cleanup_cfg
+  | TODO_verify_il, // properties_finish
+};
+
+class pass_harden_compares : public gimple_opt_pass
+{
+public:
+  pass_harden_compares (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_harden_compares, ctxt)
+  {}
+  opt_pass *clone () { return new pass_harden_compares (m_ctxt); }
+  virtual bool gate (function *) {
+    return flag_harden_compares;
+  }
+  virtual unsigned int execute (function *);
+};
+
+/* This pass introduces redundant, but reversed conditionals at every
+   conditional branch.  This doesn't make sense for abstract CPUs, but
+   this kind of hardening may avoid undesirable execution paths on
+   CPUs under such attacks as of power deprivation.  This pass must
+   run after the above, otherwise it will re-harden the checks
+   introduced by the above.  */
+
+/* Define a pass to harden conditionals in branches.  */
+const pass_data pass_data_harden_conditional_branches = {
+  GIMPLE_PASS,
+  "hardcbr",
+  OPTGROUP_NONE,
+  TV_NONE,
+  PROP_cfg | PROP_ssa, // properties_required
+  0,	    // properties_provided
+  0,	    // properties_destroyed
+  0,	    // properties_start
+  TODO_update_ssa
+  | TODO_cleanup_cfg
+  | TODO_verify_il, // properties_finish
+};
+
+class pass_harden_conditional_branches : public gimple_opt_pass
+{
+public:
+  pass_harden_conditional_branches (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_harden_conditional_branches, ctxt)
+  {}
+  opt_pass *clone () { return new pass_harden_conditional_branches (m_ctxt); }
+  virtual bool gate (function *) {
+    return flag_harden_conditional_branches;
+  }
+  virtual unsigned int execute (function *);
+};
+
+}
+
+static inline tree
+detach_value (gimple_stmt_iterator *gsip, tree val)
+{
+  if (TREE_CONSTANT (val) || TREE_CODE (val) != SSA_NAME)
+    {
+      gcc_checking_assert (is_gimple_min_invariant (val));
+      return val;
+    }
+
+  tree ret = copy_ssa_name (val);
+
+  vec<tree, va_gc> *inputs = NULL;
+  vec<tree, va_gc> *outputs = NULL;
+  vec_safe_push (outputs,
+		 build_tree_list
+		 (build_tree_list
+		  (NULL_TREE, build_string (2, "=g")),
+		  ret));
+  vec_safe_push (inputs,
+		 build_tree_list
+		 (build_tree_list
+		  (NULL_TREE, build_string (1, "0")),
+		  val));
+  gasm *detach = gimple_build_asm_vec ("", inputs, outputs,
+				       NULL, NULL);
+  gsi_insert_before (gsip, detach, GSI_SAME_STMT);
+
+  SSA_NAME_DEF_STMT (ret) = detach;
+
+  return ret;
+}
+
+static inline void
+insert_check_and_trap (gimple_stmt_iterator *gsip, int flags,
+		       enum tree_code cop, tree lhs, tree rhs)
+{
+  basic_block chk = gsi_bb (*gsip);
+
+  gcond *cond = gimple_build_cond (cop, lhs, rhs, NULL, NULL);
+  gsi_insert_before (gsip, cond, GSI_SAME_STMT);
+
+  basic_block trp = create_empty_bb (chk);
+
+  gimple_stmt_iterator gsit = gsi_after_labels (trp);
+  gcall *trap = gimple_build_call (builtin_decl_explicit (BUILT_IN_TRAP), 0);
+  gsi_insert_before (&gsit, trap, GSI_SAME_STMT);
+
+  if (BB_PARTITION (chk))
+    BB_SET_PARTITION (trp, BB_COLD_PARTITION);
+
+  int true_false_flag = flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+  gcc_assert (true_false_flag);
+  int neg_true_false_flag = (~flags) & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+
+  single_succ_edge (chk)->flags &= ~EDGE_FALLTHRU;
+  single_succ_edge (chk)->flags |= neg_true_false_flag;
+  make_edge (chk, trp, true_false_flag);
+
+  if (dom_info_available_p (CDI_DOMINATORS))
+    set_immediate_dominator (CDI_DOMINATORS, trp, chk);
+  if (current_loops)
+    add_bb_to_loop (trp, current_loops->tree_root);
+}
+
+static inline void
+insert_edge_check_and_trap (edge e, enum tree_code cop, tree lhs, tree rhs)
+{
+  int flags = e->flags;
+
+  basic_block chk = split_edge (e);
+  e = NULL;
+
+  gimple_stmt_iterator gsik = gsi_after_labels (chk);
+
+  bool same_p = (lhs == rhs);
+  lhs = detach_value (&gsik, lhs);
+  rhs = same_p ? lhs : detach_value (&gsik, rhs);
+
+  insert_check_and_trap (&gsik, flags, cop, lhs, rhs);
+}
+
+unsigned int
+pass_harden_conditional_branches::execute (function *fun)
+{
+  basic_block bb;
+  FOR_EACH_BB_REVERSE_FN (bb, fun)
+    {
+      gimple_stmt_iterator gsi = gsi_last_bb (bb);
+
+      if (gsi_end_p (gsi))
+	continue;
+
+      gcond *cond = dyn_cast <gcond *> (gsi_stmt (gsi));
+      if (!cond)
+	continue;
+
+      /* Turn:
+
+	 if (x op y) goto l1; else goto l2;
+
+	 into:
+
+	 if (x op y) goto l1'; else goto l2';
+	 l1': if (x' cop y') goto l1'trap; else goto l1;
+	 l1'trap: __builtin_trap ();
+	 l2': if (x' cop y') goto l2; else goto l2'trap;
+	 l2'trap: __builtin_trap ();
+
+	 where cop is a complementary boolean operation to op; l1', l1'trap,
+	 l2' and l2'trap are newly-created labels; and x' and y' hold the same
+	 value as x and y, but in a way that does not enable the compiler to
+	 optimize the redundant compare away.
+      */
+
+      enum tree_code op = gimple_cond_code (cond);
+      tree lhs = gimple_cond_lhs (cond);
+      tree rhs = gimple_cond_rhs (cond);
+
+      enum tree_code cop = invert_tree_comparison (op, HONOR_NANS (lhs));
+
+      if (cop == ERROR_MARK)
+	/* ??? Can we do better?  */
+	continue;
+
+      insert_edge_check_and_trap (EDGE_SUCC (bb, 0), cop, lhs, rhs);
+      insert_edge_check_and_trap (EDGE_SUCC (bb, 1), cop, lhs, rhs);
+    }
+
+  return 0;
+}
+
+gimple_opt_pass *
+make_pass_harden_conditional_branches (gcc::context *ctxt)
+{
+  return new pass_harden_conditional_branches (ctxt);
+}
+
+unsigned int
+pass_harden_compares::execute (function *fun)
+{
+  basic_block bb;
+  FOR_EACH_BB_REVERSE_FN (bb, fun)
+    for (gimple_stmt_iterator gsi = gsi_last_bb (bb);
+	 !gsi_end_p (gsi); gsi_prev (&gsi))
+      {
+	gassign *asgn = dyn_cast <gassign *> (gsi_stmt (gsi));
+	if (!asgn)
+	  continue;
+
+	/* Turn:
+
+	   z = x op y;
+
+	   into:
+
+	   z = x op y;
+	   z' = x' cop y';
+	   if (z == z') __builtin_trap ();
+
+	   where cop is a complementary boolean operation to op; and x'
+	   and y' hold the same value as x and y, but in a way that does
+	   not enable the compiler to optimize the redundant compare
+	   away.
+	*/
+
+	enum tree_code op = gimple_assign_rhs_code (asgn);
+
+	enum tree_code cop;
+
+	switch (op)
+	  {
+	  case EQ_EXPR:
+	  case NE_EXPR:
+	  case GT_EXPR:
+	  case GE_EXPR:
+	  case LT_EXPR:
+	  case LE_EXPR:
+	  case LTGT_EXPR:
+	  case UNEQ_EXPR:
+	  case UNGT_EXPR:
+	  case UNGE_EXPR:
+	  case UNLT_EXPR:
+	  case UNLE_EXPR:
+	  case ORDERED_EXPR:
+	  case UNORDERED_EXPR:
+	    cop = invert_tree_comparison (op,
+					  HONOR_NANS
+					  (gimple_assign_rhs1 (asgn)));
+
+	    if (cop == ERROR_MARK)
+	      /* ??? Can we do better?  */
+	      continue;
+
+	    break;
+
+	    /* ??? Maybe handle these too?  */
+	  case TRUTH_NOT_EXPR: /* Unary!  */
+	  case TRUTH_ANDIF_EXPR:
+	  case TRUTH_ORIF_EXPR:
+	  case TRUTH_AND_EXPR:
+	  case TRUTH_OR_EXPR:
+	  case TRUTH_XOR_EXPR:
+	  default:
+	    continue;
+	  }
+
+	/* These are the operands for the verification.  */
+	tree lhs = gimple_assign_lhs (asgn);
+	tree op1 = gimple_assign_rhs1 (asgn);
+	tree op2 = gimple_assign_rhs2 (asgn);
+
+	/* Vector booleans can't be used in conditional branches.
+	   ??? Can we do better?  */
+	if (VECTOR_TYPE_P (TREE_TYPE (op1)))
+	  continue;
+
+	gcc_checking_assert (TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE);
+
+	tree rhs = copy_ssa_name (lhs);
+
+	gimple_stmt_iterator gsi_split = gsi;
+	gsi_next (&gsi_split);
+
+	bool same_p = (op1 == op2);
+	op1 = detach_value (&gsi_split, op1);
+	op2 = same_p ? op1 : detach_value (&gsi_split, op2);
+
+	gassign *asgnck = gimple_build_assign (rhs, cop, op1, op2);
+	gsi_insert_before (&gsi_split, asgnck, GSI_SAME_STMT);
+
+	if (!gsi_end_p (gsi_split))
+	  {
+	    gsi_prev (&gsi_split);
+	    split_block (bb, gsi_stmt (gsi_split));
+	    gsi_next (&gsi_split);
+	    gcc_checking_assert (gsi_end_p (gsi_split));
+	  }
+
+	gcc_checking_assert (single_succ_p (bb));
+
+	insert_check_and_trap (&gsi_split, EDGE_TRUE_VALUE,
+			       EQ_EXPR, lhs, rhs);
+      }
+
+  return 0;
+}
+
+gimple_opt_pass *
+make_pass_harden_compares (gcc::context *ctxt)
+{
+  return new pass_harden_compares (ctxt);
+}
diff --git a/gcc/passes.def b/gcc/passes.def
index d7a1f8c97a6..a3d854ca5a6 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -419,6 +419,8 @@ along with GCC; see the file COPYING3.  If not see
   NEXT_PASS (pass_lower_resx);
   NEXT_PASS (pass_nrv);
   NEXT_PASS (pass_gimple_isel);
+  NEXT_PASS (pass_harden_conditional_branches);
+  NEXT_PASS (pass_harden_compares);
   NEXT_PASS (pass_cleanup_cfg_post_optimizing);
   NEXT_PASS (pass_warn_function_noreturn);
   NEXT_PASS (pass_warn_access);
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index eb75eb17951..5df71fd0c9e 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -642,6 +642,9 @@ extern gimple_opt_pass *make_pass_update_address_taken (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_convert_switch (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_vaarg (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_gimple_isel (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_harden_compares (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_harden_conditional_branches (gcc::context
+							       *ctxt);
 
 /* Current optimization pass.  */
 extern opt_pass *current_pass;