src/native_client/src/trusted/validator/x86/testing/enuminsts/vdiff.c

   1 /*
   2  * Copyright (c) 2012 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 /* vdiff.c
   8  * exhaustive instruction enumeration test for x86 Native Client validators.
   9  *
  10  * This file is based on enuminsts.c, but specialized to comparing two
  11  * validators instead of decoders. The enuminsts.c implementation also
  12  * had a bunch of Xed-specific logic which complicated the validator
  13  * comparison in unhelpful ways.
  14  */
  15
  16 #ifndef NACL_TRUSTED_BUT_NOT_TCB
  17 #error("This file is not meant for use in the TCB.")
  18 #endif
  19 #if NACL_WINDOWS
  20 #define _CRT_RAND_S  /* enable decl of rand_s() */
  21 #endif
  22
  23 #include "native_client/src/trusted/validator/x86/testing/enuminsts/enuminsts.h"
  24
  25 #include <ctype.h>
  26 #include <stdio.h>
  27 #include <string.h>
  28 #include <stdlib.h>
  29 #include <stdarg.h>
  30 #include <time.h>
  31
  32 #include "native_client/src/include/portability_io.h"
  33 #include "native_client/src/shared/platform/nacl_log.h"
  34 #include "native_client/src/shared/utils/flags.h"
  35 #include "native_client/src/trusted/validator/x86/testing/enuminsts/str_utils.h"
  36 #include "native_client/src/trusted/validator/x86/testing/enuminsts/text2hex.h"
  37
  38 /* Defines the maximum buffer size used to hold text generated for the
  39  * disassembly of instructions, and corresponding error messages.
  40  */
  41 #define kBufferSize 1024
  42
  43 /* When true, print more messages (i.e. verbosely). */
  44 static Bool gVerbose = FALSE;
  45
  46 /* When true, don't print out messages. That is, only print instructions
  47  * defined by --print directives.
  48  */
  49 static Bool gSilent = FALSE;
  50
  51 /* Count of errors that have a high certainty of being exploitable. */
  52 static int gSawLethalError = 0;
  53
  54 /* Defines the assumed text address for the test instruction */
  55 const int kTextAddress = 0x1000;
  56
  57 /* If non-negative, defines the prefix to test. */
  58 static unsigned int gPrefix = 0;
  59
  60 /* If non-negative, defines the opcode to test. */
  61 static int gOpcode = -1;
  62
  63 /* This option triggers a set of behaviors that help produce repeatable
  64  * output, for easier diffs on the buildbots.
  65  */
  66 static Bool gEasyDiffMode;
  67
  68 /* The production and new R-DFA validators */
  69 NaClEnumeratorDecoder* vProd;
  70 NaClEnumeratorDecoder* vDFA;
  71
  72 /* The name of the executable (i.e. argv[0] from the command line). */
  73 static const char *gArgv0 = "argv0";
  74 #define FLAG_EasyDiff "--easydiff"
  75
  76 /* Records that unexpected internal error occurred. */
  77 void InternalError(const char *why) {
  78   fprintf(stderr, "%s: Internal Error: %s\n", gArgv0, why);
  79   gSawLethalError = 1;
  80 }
  81
  82 /* Records that a fatal (i.e. non-recoverable) error occurred. */
  83 void ReportFatalError(const char* why) {
  84   char buffer[kBufferSize];
  85   SNPRINTF(buffer, kBufferSize, "%s - quitting!", why);
  86   InternalError(buffer);
  87   exit(1);
  88 }
  89
  90 /* Prints out the instruction each decoder disassembled */
  91 static void PrintDisassembledInstructionVariants(NaClEnumerator *pinst,
  92                                                  NaClEnumerator *dinst) {
  93   vProd->_print_inst_fn(pinst);
  94   vDFA->_print_inst_fn(dinst);
  95 }
  96
  97 /* Prints out progress messages. */
  98 static void PrintVProgress(const char* format, va_list ap) {
  99   if (gSilent) {
 100     /* Generating opcode sequences, so add special prefix so that we
 101      * can print these out when read by the corresponding input decoder.
 102      */
 103     printf("#PROGRESS#");
 104   }
 105   vprintf(format, ap);
 106 }
 107
 108 static void PrintProgress(const char* format, ...) ATTRIBUTE_FORMAT_PRINTF(1,2);
 109
 110 /* Prints out progress messages. */
 111 static void PrintProgress(const char* format, ...) {
 112   va_list ap;
 113   va_start(ap, format);
 114   PrintVProgress(format, ap);
 115   va_end(ap);
 116 }
 117
 118 /* Report a disagreement between decoders.
 119  */
 120 static void DecoderError(const char *why,
 121                          NaClEnumerator *pinst,
 122                          NaClEnumerator *dinst,
 123                          const char *details) {
 124   /* If reached, did not skip, so report the error. */
 125   printf("**** ERROR: %s: %s\n", why, (details == NULL ? "" : details));
 126   PrintDisassembledInstructionVariants(pinst, dinst);
 127 }
 128
 129 static void PrintBytes(FILE *f, uint8_t* bytes, size_t len) {
 130   size_t i;
 131   for (i = 0; i < len; i++) {
 132     fprintf(f, "%02x", bytes[i]);
 133   }
 134 }
 135
 136 struct vdiff_stats {
 137   int64_t tried;
 138   int64_t valid;
 139   int64_t invalid;
 140   int64_t errors;
 141   int64_t ignored;
 142 } gVDiffStats = {0, 0, 0, 0, 0};
 143
 144 static void IncrTried(void) {
 145   gVDiffStats.tried += 1;
 146 }
 147
 148 static void IncrValid(void) {
 149   gVDiffStats.valid += 1;
 150 }
 151
 152 static void IncrInvalid(void) {
 153   gVDiffStats.invalid += 1;
 154 }
 155
 156 static void IncrErrors(void) {
 157   gVDiffStats.errors += 1;
 158 }
 159
 160 static void IncrIgnored(void) {
 161   gVDiffStats.ignored += 1;
 162 }
 163
 164 static void PrintStats(void) {
 165   printf("Stats:\n");
 166   if (!gEasyDiffMode) {
 167     printf("valid: %" NACL_PRIu64 "\n", gVDiffStats.valid);
 168     printf("invalid: %" NACL_PRIu64 "\n", gVDiffStats.invalid);
 169   }
 170   printf("errors: %" NACL_PRIu64 "\n", gVDiffStats.errors);
 171   printf("tried: %" NACL_PRIu64 "\n", gVDiffStats.tried);
 172   printf("ignored: %" NACL_PRIu64 "\n", gVDiffStats.ignored);
 173   printf("    =? %" NACL_PRIu64 " valid + invalid + errors + ignored\n",
 174          gVDiffStats.valid + gVDiffStats.invalid + gVDiffStats.errors +
 175          gVDiffStats.ignored);
 176 }
 177
 178 static void InitInst(NaClEnumerator *nacle,
 179                      uint8_t *itext, size_t nbytes)
 180 {
 181   memcpy(nacle->_itext, itext, nbytes);
 182   nacle->_num_bytes = nbytes;
 183 }
 184
 185 /* Print out decodings if specified on the command line. */
 186 /* Test comparison for a single instruction. */
 187 static void TryOneInstruction(uint8_t *itext, size_t nbytes) {
 188   NaClEnumerator pinst; /* for prod validator */
 189   NaClEnumerator dinst; /* for dfa validator */
 190   Bool prod_okay, rdfa_okay;
 191
 192   IncrTried();
 193   do {
 194     if (gVerbose) {
 195       printf("================");
 196       PrintBytes(stdout, itext, nbytes);
 197       printf("\n");
 198     }
 199
 200     /* Try to parse the sequence of test bytes. */
 201     InitInst(&pinst, itext, nbytes);
 202     InitInst(&dinst, itext, nbytes);
 203     vProd->_parse_inst_fn(&pinst, kTextAddress);
 204     vDFA->_parse_inst_fn(&dinst, kTextAddress);
 205     prod_okay = vProd->_maybe_inst_validates_fn(&pinst);
 206     rdfa_okay = vDFA->_maybe_inst_validates_fn(&dinst);
 207
 208     if (prod_okay && rdfa_okay) {
 209       if (vProd->_inst_length_fn(&pinst) ==
 210           vDFA->_inst_length_fn(&dinst)) {
 211         /* Both validators see a legal instruction, */
 212         /* and they agree on critical details.      */
 213         IncrValid();
 214       } else {
 215         DecoderError("LENGTH MISMATCH", &pinst, &dinst, "");
 216         IncrErrors();
 217       }
 218     } else if (prod_okay && !rdfa_okay) {
 219       /*
 220        * 32bit production validator by design is unable to distingush a lot of
 221        * instructions (the ones which work only with memory or only with
 222        * registers).  To avoid commiting multimegabyte golden file don't count
 223        * these differences as substantial.  It's not a security problem if we
 224        * reject some valid x86 instructions and if we'll lose something
 225        * important hopefully developers will remind us.
 226        */
 227       if (NACL_ARCH(NACL_BUILD_ARCH) == NACL_x86 &&
 228           NACL_TARGET_SUBARCH == 32) {
 229         IncrIgnored();
 230       } else {
 231         /* Validators disagree on instruction legality */
 232         DecoderError("VALIDATORS DISAGREE (prod accepts, RDFA rejects)",
 233                      &pinst,
 234                      &dinst,
 235                      "");
 236         IncrErrors();
 237       }
 238     } else if (!prod_okay && rdfa_okay) {
 239       /* Validators disagree on instruction legality */
 240       DecoderError("VALIDATORS DISAGREE (prod rejects, RDFA accepts)",
 241                    &pinst,
 242                    &dinst,
 243                    "");
 244       IncrErrors();
 245     } else {
 246       /* Both validators see an illegal instruction */
 247       IncrInvalid();
 248     }
 249
 250     if (gVerbose) {
 251       PrintDisassembledInstructionVariants(&pinst, &dinst);
 252     }
 253   } while (0);
 254 }
 255
 256 /* A function type for instruction "TestAll" functions.
 257  * Parameters:
 258  *     prefix: up to four bytes of prefix.
 259  *     prefix_length: size_t on [0..4] specifying length of prefix.
 260  *     print_prefix: For easy diff of test output, avoid printing
 261  *         the value of a randomly selected REX prefix.
 262  */
 263 typedef void (*TestAllFunction)(const unsigned int prefix,
 264                                 const size_t prefix_length,
 265                                 const char* print_prefix);
 266
 267 /* Create a char* rendition of a prefix string, appending bytes
 268  * in ps. When using a randomly generated REX prefix on the bots,
 269  * it's useful to avoid printing the actual REX prefix so that
 270  * output can be diffed from run-to-run. For example, instead of
 271  * printing "0F45" you might print "0FXX". Parameters:
 272  *     prefix: The part of the prefix value to print
 273  *     ps: 'postscript', string to append to prefix value
 274  *     str: where to put the ASCII version of the prefix
 275  */
 276 static char* StrPrefix(const unsigned int prefix, char* ps, char* str) {
 277   sprintf(str, "%x%s", prefix, (ps == NULL) ? "" : ps);
 278   return str;
 279 }
 280
 281 /* Enumerate and test all 24-bit opcode+modrm+sib patterns for a
 282  * particular prefix.
 283  */
 284 static void TestAllWithPrefix(const unsigned int prefix,
 285                               const size_t prefix_length,
 286                               const char* print_prefix) {
 287   const size_t kInstByteCount = NACL_ENUM_MAX_INSTRUCTION_BYTES;
 288   const size_t kIterByteCount = 3;
 289   InstByteArray itext;
 290   size_t i;
 291   int op, modrm, sib;
 292   int min_op;
 293   int max_op;
 294
 295   if ((gPrefix > 0) && (gPrefix != prefix)) return;
 296
 297   PrintProgress("TestAllWithPrefix(%s)\n", print_prefix);
 298   /* set up prefix */
 299   memcpy(itext, &prefix, prefix_length);
 300   /* set up filler bytes */
 301   for (i = prefix_length + kIterByteCount; i < kInstByteCount; i++) {
 302     itext[i] = (uint8_t)i;
 303   }
 304   if (gOpcode < 0) {
 305     min_op = 0;
 306     max_op = 256;
 307   } else {
 308     min_op = gOpcode;
 309     max_op = gOpcode + 1;
 310   }
 311   for (op = min_op; op < max_op; op++) {
 312     itext[prefix_length] = op;
 313     if (!gEasyDiffMode) PrintProgress("%02x 00 00\n", op);
 314     for (modrm = 0; modrm < 256; modrm++) {
 315       itext[prefix_length + 1] = modrm;
 316       for (sib = 0; sib < 256; sib++) {
 317         itext[prefix_length + 2] = sib;
 318         TryOneInstruction(itext, kInstByteCount);
 319       }
 320     }
 321   }
 322 }
 323
 324 /* For 3DNow!, the operand byte goes at the end. Format is:
 325  *   0F 0F [ModRM] [SIB] [displacement] imm8_opcode
 326  * See AMD doc 24594, page 435.
 327  */
 328 static void TestAll3DNow(const unsigned int prefix,
 329                          const size_t prefix_length,
 330                          const char* print_prefix) {
 331   const size_t kInstByteCount = NACL_ENUM_MAX_INSTRUCTION_BYTES;
 332   const size_t kIterByteCount = 3;
 333   InstByteArray itext;
 334   size_t i;
 335   int op, modrm, sib;
 336
 337   if ((gPrefix > 0) && (gPrefix != prefix)) return;
 338
 339   PrintProgress("TestAll3DNow(%s)\n", print_prefix);
 340   /* set up prefix */
 341   memcpy(itext, &prefix, prefix_length);
 342   /* set up filler bytes */
 343   for (i = prefix_length + kIterByteCount; i < kInstByteCount; i++) {
 344     itext[i] = (uint8_t)i;
 345   }
 346
 347   for (op = 0; op < 256; op++) {
 348     if (!gEasyDiffMode) PrintProgress("%02x 00 00\n", op);
 349     /* Use opcode as fill byte, forcing iteration through 3DNow opcodes. */
 350     for (i = prefix_length + 2; i < kIterByteCount; i++) itext[i] = op;
 351
 352     for (modrm = 0; modrm < 256; modrm++) {
 353       itext[prefix_length] = modrm;
 354       for (sib = 0; sib < 256; sib++) {
 355         itext[prefix_length + 1] = sib;
 356         TryOneInstruction(itext, kInstByteCount);
 357       }
 358     }
 359   }
 360 }
 361
 362 #if NACL_TARGET_SUBARCH == 64
 363 /* REX prefixes range from 0x40 to 0x4f. */
 364 const uint32_t kREXBase = 0x40;
 365 const uint32_t kREXRange = 0x10;
 366 const uint32_t kREXMax = 0x50;  /* kREXBase + kREXRange */
 367
 368 /* Generate a random REX prefix, to use for the entire run. */
 369 static uint32_t RandomRexPrefix(void) {
 370   static uint32_t static_rex_prefix = 0;
 371
 372   if (0 == static_rex_prefix) {
 373 #if NACL_LINUX || NACL_OSX
 374     static_rex_prefix = kREXBase + (random() % kREXRange);
 375 #elif NACL_WINDOWS
 376     if (rand_s(&static_rex_prefix) != 0) {
 377       ReportFatalError("rand_s() failed\n");
 378     } else {
 379       static_rex_prefix = kREXBase + (static_rex_prefix % kREXRange);
 380     }
 381 #else
 382 # error "Unknown operating system."
 383 #endif
 384   }
 385   return static_rex_prefix;
 386 }
 387 #endif
 388
 389 #define AppendPrefixByte(oldprefix, pbyte) (((oldprefix) << 8) | (pbyte))
 390 /* For x86-64, enhance the iteration by looping through REX prefixes.
 391  */
 392 static void WithREX(TestAllFunction testall,
 393                     const unsigned int prefix,
 394                     const size_t prefix_length) {
 395   char pstr[kBufferSize];
 396 #if NACL_TARGET_SUBARCH == 64
 397   unsigned char irex;
 398   unsigned int rprefix;
 399   /* test with REX prefixes */
 400   printf("WithREX(testall, %x, %d, %d)\n", prefix,
 401          (int)prefix_length, gEasyDiffMode);
 402   if (gEasyDiffMode) {
 403     printf("With random REX prefix.\n");
 404     irex = RandomRexPrefix();
 405     rprefix = AppendPrefixByte(prefix, irex);
 406     testall(rprefix, prefix_length + 1, StrPrefix(prefix, "XX", pstr));
 407   } else {
 408     for (irex = kREXBase; irex < kREXMax; irex++) {
 409       rprefix = AppendPrefixByte(prefix, irex);
 410       printf("With REX prefix %x\n", rprefix);
 411       testall(rprefix, prefix_length + 1, StrPrefix(rprefix, "", pstr));
 412     }
 413   }
 414 #endif
 415   /* test with no REX prefix */
 416   testall(prefix, prefix_length, StrPrefix(prefix, NULL, pstr));
 417 }
 418 #undef AppendPrefixByte
 419
 420 /* For all prefixes, call TestAllWithPrefix() to enumrate and test
 421  * all instructions.
 422  */
 423 static void TestAllInstructions(void) {
 424   /* NOTE: Prefix byte order needs to be reversed when written as
 425    * an integer. For example, for integer prefix 0x3a0f, 0f will
 426    * go in instruction byte 0, and 3a in byte 1.
 427    */
 428   WithREX(TestAllWithPrefix, 0, 0);
 429   WithREX(TestAllWithPrefix, 0x0f, 1);     /* two-byte opcode */
 430   WithREX(TestAllWithPrefix, 0x0ff2, 2);   /* SSE2  */
 431   WithREX(TestAllWithPrefix, 0x0ff3, 2);   /* SSE   */
 432   WithREX(TestAllWithPrefix, 0x0f66, 2);   /* SSE2  */
 433   WithREX(TestAllWithPrefix, 0x380f, 2);   /* SSSE3 */
 434   WithREX(TestAllWithPrefix, 0x3a0f, 2);   /* SSE4  */
 435   WithREX(TestAllWithPrefix, 0x380f66, 3); /* SSE4+ */
 436   WithREX(TestAllWithPrefix, 0x380ff2, 3); /* SSE4+ */
 437   WithREX(TestAllWithPrefix, 0x3a0f66, 3); /* SSE4+ */
 438   WithREX(TestAllWithPrefix, 0x0ff366, 3); /* SSE4+ */
 439   WithREX(TestAll3DNow, 0x0f0f, 2);
 440 }
 441
 442 /* Used to test one instruction at a time, for example, in regression
 443  * testing, or for instruction arguments from the command line.
 444  */
 445 static void TestOneInstruction(const char *asciihex) {
 446   InstByteArray ibytes;
 447   int nbytes;
 448
 449   nbytes = Text2Bytes(ibytes, asciihex, "Command-line argument", -1);
 450   if (nbytes == 0) return;
 451   if (gVerbose) {
 452     int i;
 453     printf("trying %s (", asciihex);
 454     for (i = 0; i < nbytes; ++i) {
 455       printf("%02x", ibytes[i]);
 456     }
 457     printf(")\n");
 458   }
 459   TryOneInstruction(ibytes, (size_t) nbytes);
 460 }
 461
 462 /* A set of test cases that have caused problems in the past.
 463  * This is a bit stale; most of the test cases came from xed_compare.py.
 464  * Mostly this program has been tested by TestAllInstructions(),
 465  * possible since this program is much faster than xed_compare.py
 466  */
 467 static void RunRegressionTests(void) {
 468   TestOneInstruction("0024c2");
 469   TestOneInstruction("017967");
 470   TestOneInstruction("0f12c0");
 471   TestOneInstruction("0f13c0");
 472   TestOneInstruction("0f17c0");
 473   TestOneInstruction("0f01c1");
 474   TestOneInstruction("0f00300000112233445566778899aa");
 475   TestOneInstruction("cc");
 476   TestOneInstruction("C3");
 477   TestOneInstruction("0f00290000112233445566778899aa");
 478   TestOneInstruction("80e4f7");
 479   TestOneInstruction("e9a0ffffff");
 480   TestOneInstruction("4883ec08");
 481   TestOneInstruction("0f00040500112233445566778899aa");
 482   /* Below are newly discovered mistakes in call instructions, where the wrong
 483    * byte length was required by x86-64 nacl validator.
 484    */
 485   TestOneInstruction("262e7e00");
 486   TestOneInstruction("2e3e7900");
 487   /* From the AMD manual, "An instruction may have only one REX prefix */
 488   /* which must immediately precede the opcode or first excape byte    */
 489   /* in the instruction encoding." */
 490   TestOneInstruction("406601d8");  /* illegal; REX before data16 */
 491   TestOneInstruction("664001d8");  /* legal; REX after data16    */
 492   TestOneInstruction("414001d8");  /* illegal; two REX bytes     */
 493
 494   /* And some tests for degenerate prefix patterns */
 495   TestOneInstruction("666690");
 496   TestOneInstruction("6690");
 497   TestOneInstruction("666666666666666666666690");
 498   TestOneInstruction("66454490");
 499   TestOneInstruction("66454f90");
 500   TestOneInstruction("456690");
 501 }
 502
 503 /* Define decoders that can be registered. */
 504 extern NaClEnumeratorDecoder* RegisterNaClDecoder(void);
 505 extern NaClEnumeratorDecoder* RegisterRagelDecoder(void);
 506
 507 /* Initialize the set of available decoders. */
 508 static void VDiffInitializeAvailableDecoders(void) {
 509   vProd = RegisterNaClDecoder();
 510   vDFA = RegisterRagelDecoder();
 511 }
 512
 513 static int ParseArgv(const int argc, const char* argv[]) {
 514   int nextarg;
 515
 516   gArgv0 = argv[0];
 517   nextarg = 1;
 518   if (nextarg < argc &&
 519       0 == strcmp(argv[nextarg], FLAG_EasyDiff)) {
 520     gEasyDiffMode = TRUE;
 521     nextarg += 1;
 522   }
 523   return nextarg;
 524 }
 525
 526 static char g_standard_output_buffer[4 << 10];
 527
 528 int main(const int argc, const char *argv[]) {
 529   int nextarg;
 530
 531   NaClLogModuleInit();
 532   NaClLogSetVerbosity(LOG_FATAL);
 533   if (0 != setvbuf(stdout, g_standard_output_buffer, _IOLBF,
 534                    sizeof g_standard_output_buffer)) {
 535     NaClLog(LOG_FATAL, "vdiff: setvbuf failed\n");
 536   }
 537 #if NACL_LINUX || NACL_OSX
 538   srandom(time(NULL));
 539 #endif
 540   VDiffInitializeAvailableDecoders();
 541
 542   nextarg = ParseArgv(argc, argv);
 543   if (nextarg == argc) {
 544     if (gPrefix == 0) RunRegressionTests();
 545     TestAllInstructions();
 546   } else {
 547     int i;
 548     gVerbose = TRUE;
 549     for (i = nextarg; i < argc; ++i) {
 550       TestOneInstruction(argv[i]);
 551     }
 552   }
 553   PrintStats();
 554
 555   /* exit with non-zero error code if there were errors. */
 556   exit(gVDiffStats.errors != 0);
 557 }