src/native_client/src/trusted/validator_ragel/verify_regular_instructions.py

   1 #!/usr/bin/python
   2 # Copyright (c) 2013 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 Generate all acceptable regular instructions by traversing validator DFA
   8 and run check them against RDFA decoder and text-based specification.
   9 """
  10
  11 import itertools
  12 import multiprocessing
  13 import optparse
  14 import os
  15 import re
  16 import subprocess
  17 import sys
  18 import tempfile
  19 import traceback
  20
  21 import dfa_parser
  22 import dfa_traversal
  23 import objdump_parser
  24 import validator
  25 import spec
  26
  27
  28 FWAIT = 0x9b
  29 NOP = 0x90
  30
  31
  32 def IsRexPrefix(byte):
  33   return 0x40 <= byte < 0x50
  34
  35
  36 def PadToBundleSize(bytes):
  37   assert len(bytes) <= validator.BUNDLE_SIZE
  38   return bytes + [NOP] * (validator.BUNDLE_SIZE - len(bytes))
  39
  40
  41 def ConditionToRestrictedRegisterNumber(condition):
  42   restricted, restricted_instead_of_sandboxed = condition.GetAlteredRegisters()
  43   if restricted is not None:
  44     assert restricted_instead_of_sandboxed is None
  45     return validator.REGISTER_BY_NAME[restricted]
  46   elif restricted_instead_of_sandboxed is not None:
  47     return validator.REGISTER_BY_NAME[restricted_instead_of_sandboxed]
  48   else:
  49     return None
  50
  51
  52 def RestrictedRegisterNumberToCondition(rr):
  53   assert rr is None or rr in validator.ALL_REGISTERS, rr
  54   if rr is None:
  55     return spec.Condition()
  56   elif rr == validator.NC_REG_RBP:
  57     return spec.Condition(restricted_instead_of_sandboxed='%rbp')
  58   elif rr == validator.NC_REG_RSP:
  59     return spec.Condition(restricted_instead_of_sandboxed='%rsp')
  60   else:
  61     return spec.Condition(validator.REGISTER_NAMES[rr])
  62
  63
  64 def ValidateAndGetPostcondition(
  65     bundle, actual_size, precondition, validator_inst):
  66   """Validate single x86-64 instruction and get postcondition for it.
  67
  68   Args:
  69     bundle: sequence of bytes (as python string)
  70     actual_size: size of the instruction in the beginning of the bundle
  71                  (remaining bytes are expected to be NOPS)
  72     precondition: instance of spec.Condition representing precondition validator
  73     is allowed to assume.
  74     validator_inst: implementation of validator.
  75   Returns:
  76     Pair (validation_result, postcondition).
  77     Validation_result is True or False. When validation_result is True,
  78     postcondition is spec.Condition instance representing postcondition
  79     for this instruction established by validator.
  80   """
  81
  82   valid, final_rr = validator_inst.ValidateAndGetFinalRestrictedRegister(
  83       bundle,
  84       actual_size,
  85       initial_rr=ConditionToRestrictedRegisterNumber(precondition))
  86
  87   if valid:
  88     return True, RestrictedRegisterNumberToCondition(final_rr)
  89   else:
  90     return False, None
  91
  92
  93 def CheckValid64bitInstruction(
  94     instruction,
  95     dis,
  96     precondition,
  97     postcondition,
  98     validator_inst):
  99   bundle = ''.join(map(chr, PadToBundleSize(instruction)))
 100   for conflicting_precondition in spec.Condition.All():
 101     if conflicting_precondition.Implies(precondition):
 102       continue  # not conflicting
 103     result, _ = ValidateAndGetPostcondition(
 104         bundle, len(instruction), conflicting_precondition, validator_inst)
 105     assert not result, (
 106         'validator incorrectly accepted %s with precondition %s, '
 107         'while specification requires precondition %s'
 108         % (dis, conflicting_precondition, precondition))
 109
 110   result, actual_postcondition = ValidateAndGetPostcondition(
 111       bundle, len(instruction), precondition, validator_inst)
 112   if not result:
 113     print 'warning: validator rejected %s with precondition %s' % (
 114         dis, precondition)
 115   else:
 116     # We are checking for implication, not for equality, because in some cases
 117     # specification computes postcondition with better precision.
 118     # For example, xchg with memory is not treated as zero-extending
 119     # instruction, so validator thinks that postcondition of
 120     #   xchg %eax, (%rip)
 121     # is Condition(default), while in fact it's Condition(%rax is restricted).
 122     # (https://code.google.com/p/nativeclient/issues/detail?id=3071)
 123     # TODO(shcherbina): change it to equality test when such cases
 124     # are eliminated.
 125     assert postcondition.Implies(actual_postcondition), (
 126         'validator incorrectly determined postcondition %s '
 127         'for %s where specification predicted %s'
 128         % (actual_postcondition, dis, postcondition))
 129     if postcondition != actual_postcondition:
 130       print (
 131           'warning: validator reported too broad postcondition %s for %s, '
 132           'where specification predicted %s'
 133           % (actual_postcondition, dis, postcondition))
 134
 135
 136 def CheckInvalid64bitInstruction(
 137     instruction,
 138     dis,
 139     validator_inst,
 140     sandboxing_error):
 141   bundle = ''.join(map(chr, PadToBundleSize(instruction)))
 142   for precondition in spec.Condition.All():
 143     result, _ = ValidateAndGetPostcondition(
 144         bundle, len(instruction), precondition, validator_inst)
 145     assert not result, (
 146         'validator incorrectly accepted %s with precondition %s, '
 147         'while specification rejected because %s'
 148         % (dis, precondition, sandboxing_error))
 149
 150
 151 def ValidateInstruction(instruction, validator_inst):
 152   dis = validator_inst.DisassembleChunk(
 153       ''.join(map(chr, instruction)),
 154       bitness=options.bitness)
 155
 156   # Objdump 2.24 (and consequently our decoder) displays fwait with rex prefix
 157   # in  the following way (note the rex byte is extraneous here):
 158   #   0: 41      rex.B
 159   #   1: 9b      fwait
 160   # We manually convert it to
 161   #   0: 41 9b   fwait
 162   # for the purpose of validation.
 163   # TODO(shyamsundarr): investigate whether we can get rid of this special
 164   # handling. Also https://code.google.com/p/nativeclient/issues/detail?id=3496.
 165   if (len(instruction) == 2 and
 166       IsRexPrefix(instruction[0]) and
 167       instruction[1] == FWAIT):
 168     assert len(dis) == 2, (instruction, dis)
 169     assert dis[1].disasm == 'fwait', (instruction, dis)
 170     dis[0] = objdump_parser.Instruction(
 171         address=dis[0].address, bytes=(dis[0].bytes + dis[1].bytes),
 172         disasm=dis[1].disasm)
 173     del dis[1]
 174
 175   assert len(dis) == 1, (instruction, dis)
 176   (dis,) = dis
 177   assert dis.bytes == instruction, (instruction, dis)
 178
 179   if options.bitness == 32:
 180     result = validator_inst.ValidateChunk(
 181         ''.join(map(chr, PadToBundleSize(instruction))),
 182         bitness=32)
 183
 184     try:
 185       spec.ValidateDirectJumpOrRegularInstruction(dis, bitness=32)
 186       if not result:
 187         print 'warning: validator rejected', dis
 188       return True
 189     except spec.SandboxingError as e:
 190       if result:
 191         print 'validator accepted instruction disallowed by specification'
 192         raise
 193     except spec.DoNotMatchError:
 194       if result:
 195         print 'validator accepted instruction not recognized by specification'
 196         raise
 197
 198     return False
 199
 200   else:
 201     try:
 202       _, precondition, postcondition = (
 203           spec.ValidateDirectJumpOrRegularInstruction(dis, bitness=64))
 204
 205       CheckValid64bitInstruction(instruction,
 206                                  dis,
 207                                  precondition,
 208                                  postcondition,
 209                                  validator_inst)
 210       return True
 211     except spec.SandboxingError as e:
 212       CheckInvalid64bitInstruction(instruction,
 213                                    dis,
 214                                    validator_inst,
 215                                    sandboxing_error=e)
 216     except spec.DoNotMatchError as e:
 217       CheckInvalid64bitInstruction(
 218           instruction,
 219           dis,
 220           validator_inst,
 221           sandboxing_error=spec.SandboxingError(
 222               'unrecognized instruction %s' % e))
 223
 224     return False
 225
 226
 227 class WorkerState(object):
 228   def __init__(self, prefix, validator_inst):
 229     self.total_instructions = 0
 230     self.num_valid = 0
 231     self.validator_inst = validator_inst
 232
 233   def ReceiveInstruction(self, bytes):
 234     self.total_instructions += 1
 235     self.num_valid += ValidateInstruction(bytes, self.validator_inst)
 236
 237
 238 def Worker((prefix, state_index)):
 239   worker_state = WorkerState(prefix, worker_validator)
 240
 241   try:
 242     dfa_traversal.TraverseTree(
 243         dfa.states[state_index],
 244         final_callback=worker_state.ReceiveInstruction,
 245         prefix=prefix,
 246         anyfield=0)
 247   except Exception as e:
 248     traceback.print_exc() # because multiprocessing imap swallows traceback
 249     raise
 250
 251   return (
 252       prefix,
 253       worker_state.total_instructions,
 254       worker_state.num_valid)
 255
 256
 257 def ParseOptions():
 258   parser = optparse.OptionParser(usage='%prog [options] xmlfile')
 259
 260   parser.add_option('--bitness',
 261                     type=int,
 262                     help='The subarchitecture: 32 or 64')
 263   parser.add_option('--validator_dll',
 264                     help='Path to librdfa_validator_dll')
 265   parser.add_option('--decoder_dll',
 266                     help='Path to librdfa_decoder_dll')
 267
 268   options, args = parser.parse_args()
 269
 270   if options.bitness not in [32, 64]:
 271     parser.error('specify -b 32 or -b 64')
 272
 273   if len(args) != 1:
 274     parser.error('specify one xml file')
 275
 276   (xml_file,) = args
 277
 278   return options, xml_file
 279
 280
 281 options, xml_file = ParseOptions()
 282 # We are doing it here to share state graph between workers spawned by
 283 # multiprocess. Passing it every time is slow.
 284 dfa = dfa_parser.ParseXml(xml_file)
 285 worker_validator = validator.Validator(
 286     validator_dll=options.validator_dll,
 287     decoder_dll=options.decoder_dll)
 288
 289
 290 def main():
 291   assert dfa.initial_state.is_accepting
 292   assert not dfa.initial_state.any_byte
 293
 294   print len(dfa.states), 'states'
 295
 296   num_suffixes = dfa_traversal.GetNumSuffixes(dfa.initial_state)
 297
 298   # We can't just write 'num_suffixes[dfa.initial_state]' because
 299   # initial state is accepting.
 300   total_instructions = sum(
 301       num_suffixes[t.to_state]
 302       for t in dfa.initial_state.forward_transitions.values())
 303   print total_instructions, 'regular instructions total'
 304
 305   tasks = dfa_traversal.CreateTraversalTasks(dfa.states, dfa.initial_state)
 306   print len(tasks), 'tasks'
 307
 308   pool = multiprocessing.Pool()
 309
 310   results = pool.imap(Worker, tasks)
 311
 312   total = 0
 313   num_valid = 0
 314   for prefix, count, valid_count in results:
 315     print ', '.join(map(hex, prefix))
 316     total += count
 317     num_valid += valid_count
 318
 319   print total, 'instructions were processed'
 320   print num_valid, 'valid instructions'
 321
 322
 323 if __name__ == '__main__':
 324   main()