src/native_client/src/trusted/validator/x86/decoder/generator/ncval_simplify.c

   1 /*
   2  * Copyright (c) 2011 The Native Client Authors. All rights reserved.
   3  * Use of this source code is governed by a BSD-style license that can be
   4  * found in the LICENSE file.
   5  */
   6
   7 /*
   8  * Simplifies instruction set to what is needed for the
   9  * (x86-64) ncval_reg_sfi validator.
  10  *
  11  * There are two parts to this story. First, the decoder used by the
  12  * ncval_reg_sfi validator use the decoder in:
  13  *   native_client/src/trusted/validator/x86/decoder
  14  *
  15  * This decoder is based on instruction flags. If the instruction flags
  16  * are not changed, the same sequence of bytes will be parsed, independent
  17  * of the instruction mnemonic. Therefore, it is safe to change the
  18  * instruction mnemonic to a "don't care" name unless it is explicitly
  19  * used in some rule of the validator. The static validator validator_names
  20  * in function NaClNcvalSimplifyMnemonic lists all instruction mnemonics that
  21  * are currently used by the validator.
  22  *
  23  * Secondly, the ncval_reg_sfi validator checks general purpose registers,
  24  * segment registers, and memory references to make sure that data and
  25  * branching have been sandboxed properly. Hence, any argument to an x86
  26  * instruction that can be shown that it will never access one of these
  27  * forms can be omitted without breaking the validator. Hence, this code
  28  * removes all such arguments. See function NaClNcvalKeepOperand for details
  29  * on what arguments are removed.
  30  *
  31  * Finally, for pragmatic reasons (i.e. readability), if an instruction is
  32  * modified by this simplification, it is marked as a "partial instruction",
  33  * so that the corresponding (ncdis) disassembler can correctly communicate
  34  * that a partial match (rather than an actual instruction decoding) was applied
  35  * to the given bits. The printed partial match communicates what was kept for
  36  * validation purposes.
  37  */
  38
  39 #ifndef NACL_TRUSTED_BUT_NOT_TCB
  40 #error("This file is not meant for use in the TCB")
  41 #endif
  42
  43 #include "native_client/src/trusted/validator/x86/decoder/generator/ncval_simplify.h"
  44
  45 #include <string.h>
  46 #include "native_client/src/include/nacl_macros.h"
  47 #include "native_client/src/trusted/validator/x86/x86_insts.h"
  48 #include "native_client/src/trusted/validator/x86/decoder/generator/nc_compress.h"
  49
  50 /* To turn on debugging of instruction decoding, change value of
  51  * DEBUGGING to 1.
  52  */
  53 #define DEBUGGING 0
  54
  55 #include "native_client/src/shared/utils/debugging.h"
  56
  57 /* Returns true if the data extracted by the operand may be needed
  58  * for register sfi sandboxing.
  59  */
  60 static Bool NaClNcvalKeepOperand(NaClOp *operand) {
  61   /* Operands in the ncval_seg_sfi (x86-64) validator are not inspected
  62    * by the validator, unless they are general purpose register, segment
  63    * registers, or memory references. The following list are all operand
  64    * specifiers that can't contain any of the above, and hence, are not
  65    * used by the validator. This list is used to safely determine if
  66    * an operand can be removed.
  67    */
  68   static NaClOpKind unnecessary_opkinds[] = {
  69     RegDR0,           /* Debug registers. */
  70     RegDR1,
  71     RegDR2,
  72     RegDR3,
  73     RegDR4,
  74     RegDR5,
  75     RegDR6,
  76     RegDR7,
  77     RegDR8,
  78     RegDR9,
  79     RegDR10,
  80     RegDR11,
  81     RegDR12,
  82     RegDR13,
  83     RegDR14,
  84     RegDR15,
  85     RegEFLAGS,        /* Program status and control registers. */
  86     RegRFLAGS,
  87     St_Operand,       /* Floating point stack registers. */
  88     RegST0,
  89     RegST1,
  90     RegST2,
  91     RegST3,
  92     RegST4,
  93     RegST5,
  94     RegST6,
  95     RegST7,
  96     Mmx_G_Operand,    /* Mxx registers. */
  97     Mmx_Gd_Operand,
  98     RegMMX0,
  99     RegMMX1,
 100     RegMMX2,
 101     RegMMX3,
 102     RegMMX4,
 103     RegMMX5,
 104     RegMMX6,
 105     RegMMX7,
 106     Xmm_G_Operand,    /* Xmm registers. */
 107     Xmm_Go_Operand,
 108     RegXMM0,
 109     RegXMM1,
 110     RegXMM2,
 111     RegXMM3,
 112     RegXMM4,
 113     RegXMM5,
 114     RegXMM6,
 115     RegXMM7,
 116     RegXMM8,
 117     RegXMM9,
 118     RegXMM10,
 119     RegXMM11,
 120     RegXMM12,
 121     RegXMM13,
 122     RegXMM14,
 123     RegXMM15,
 124   };
 125   size_t i;
 126   for (i = 0; i < NACL_ARRAY_SIZE(unnecessary_opkinds); ++i) {
 127     if (operand->kind == unnecessary_opkinds[i]) return FALSE;
 128   }
 129   return TRUE;
 130 }
 131
 132 /* Returns the instruction mnemonic to use for an instruction. The
 133  * mnemonic is changed only if the (x86-64) ncval_reg_sfi validator
 134  * doesn't need to know the corresponding instruction mnemonic.
 135  */
 136 static NaClMnemonic NaClNcvalSimplifyMnemonic(NaClModeledInst *inst) {
 137   /* List of white listed names that must be kept for the validator,
 138    * since they are used as part of the pattern checking of the validator.
 139    */
 140   static NaClMnemonic validator_names[] = {
 141     InstAnd,
 142     InstAdd,
 143     InstCall,
 144     InstInvalid,
 145     InstLea,
 146     InstMov,
 147     InstOr,
 148     InstPop,
 149     InstPush,
 150     InstSub
 151   };
 152   NaClMnemonic name = inst->name;
 153   size_t i;
 154   for (i = 0; i < NACL_ARRAY_SIZE(validator_names); ++i) {
 155     if (name == validator_names[i]) return name;
 156   }
 157   /* If not white listed, change to dont care. */
 158   if (NaClHasBit(inst->flags, NACL_IFLAG(ConditionalJump))) {
 159     return InstDontCareCondJump;
 160   }
 161   if (NaClHasBit(inst->flags, NACL_IFLAG(JumpInstruction))) {
 162     return InstDontCareJump;
 163   }
 164   return InstDontCare;
 165 }
 166
 167 /* Fixes format strings used to define the instruction operand
 168  * to its simplified form, by removing any implicit braces used
 169  * when defining the operand for the instruction.
 170  */
 171 static const char* RemoveImplicitFromFormat(const char* str) {
 172   size_t str_len = strlen(str);
 173   if ((str_len > 0) && (str[0] == '{') && (str[str_len-1] == '}')) {
 174     char* simp_str = (char*) malloc(str_len-1);
 175     if (NULL == simp_str) return str;  /* This should not happen. */
 176     strncpy(simp_str, str+1, str_len-1);
 177     simp_str[str_len-2] = '\0';
 178     return simp_str;
 179   }
 180   return str;
 181 }
 182
 183 /* Simplify the given instruction and return the simplified instruction,
 184  * based on expectations of the (x86-64) ncval_reg_sfi validator.
 185  */
 186 static void NaClNcvalSimplifyInst(NaClInstTables *inst_tables,
 187                                   NaClModeledInst *inst) {
 188   size_t i;
 189   NaClMnemonic simplified_name;
 190   size_t fill = 0;
 191   Bool is_partial = FALSE;
 192
 193   if (NULL == inst) return;
 194
 195   /* First simplify additional rules associated with the given instruction. */
 196   NaClNcvalSimplifyInst(inst_tables, inst->next_rule);
 197
 198   /* Ignore invalid instructions. */
 199   if (NACLi_INVALID == inst->insttype) return;
 200
 201   /* Remove unnecessary operands. */
 202   if (NaClHasBit(inst->flags, NACL_IFLAG(NaClIllegal))) {
 203     /* Remove all arguments. We don't need to process arguments.
 204      * Validation will fail regardless.
 205      */
 206     inst->num_operands = 0;
 207     inst->name = InstDontCare;
 208     is_partial = TRUE;
 209   } else {
 210     /* Simplify the instruction mnemonic. */
 211     simplified_name = NaClNcvalSimplifyMnemonic(inst);
 212     if (simplified_name != inst->name) {
 213       uint8_t num_operands;
 214       inst->name = simplified_name;
 215       is_partial = TRUE;
 216
 217       /* We have simplified the modeled instruction, and hence
 218        * the modeled instruction is now a pattern, rather than'
 219        * an x86 instruction. Remove operands that aren't needed,
 220        * because the operand is never going to be used by the validator.
 221        */
 222       num_operands = inst->num_operands;
 223       for (i = 0; i < num_operands; i++) {
 224         if (NaClNcvalKeepOperand(&inst->operands[i])) {
 225           inst->operands[fill++] = inst->operands[i];
 226         } else {
 227           inst->num_operands--;
 228           is_partial = TRUE;
 229         }
 230       }
 231     }
 232   }
 233
 234   /* Check if we modified anything. If so, we need to clean
 235    * up the instruction so that (all) useful information is printed
 236    * by the decoder print functions (i.e. as a pattern rather than
 237    * an x86 instruction).
 238    */
 239   if (is_partial) {
 240     uint8_t num_operands = inst->num_operands;
 241     NaClAddBits(inst->flags, NACL_IFLAG(PartialInstruction));
 242     for (i = 0; i < num_operands; i++) {
 243       if (NaClHasBit(inst->operands[i].flags, NACL_OPFLAG(OpImplicit))) {
 244         NaClRemoveBits(inst->operands[i].flags, NACL_OPFLAG(OpImplicit));
 245         inst->operands[i].format_string =
 246             RemoveImplicitFromFormat(inst->operands[i].format_string);
 247       }
 248     }
 249   }
 250 }
 251
 252 /* Simplify instructions in the given trie node. */
 253 static void NaClNcvalSimplifyNode(NaClInstTables *inst_tables,
 254                                   NaClModeledInstNode* node) {
 255   if (NULL == node) return;
 256   NaClNcvalSimplifyInst(inst_tables, node->matching_inst);
 257   NaClNcvalSimplifyNode(inst_tables, node->success);
 258   NaClNcvalSimplifyNode(inst_tables, node->fail);
 259 }
 260
 261 void NaClNcvalInstSimplify(NaClInstTables* inst_tables) {
 262   int i;
 263   NaClInstPrefix prefix;
 264
 265   /* Simplify the undefined instruction. */
 266   NaClNcvalSimplifyInst(inst_tables, inst_tables->undefined_inst);
 267
 268   /* Simplify all instructions in the instruction opcode table. */
 269   for (prefix = NoPrefix; prefix < NaClInstPrefixEnumSize; ++prefix) {
 270     for (i = 0; i < NCDTABLESIZE; ++i) {
 271       NaClNcvalSimplifyInst(inst_tables, inst_tables->inst_table[i][prefix]);
 272     }
 273   }
 274
 275   /* Simplify instructions in the instruction trie. */
 276   NaClNcvalSimplifyNode(inst_tables, inst_tables->inst_node_root);
 277 }