native_client_sdk/src/doc/reference/pnacl-undefined-behavior.rst

   1 ========================
   2 PNaCl Undefined Behavior
   3 ========================
   4
   5 .. contents::
   6    :local:
   7    :backlinks: none
   8    :depth: 3
   9
  10 .. _undefined_behavior:
  11
  12 Overview
  13 ========
  14
  15 C and C++ undefined behavior allows efficient mapping of the source
  16 language onto hardware, but leads to different behavior on different
  17 platforms.
  18
  19 PNaCl exposes undefined behavior in the following ways:
  20
  21 * The Clang frontend and optimizations that occur on the developer's
  22   machine determine what behavior will occur, and it will be specified
  23   deterministically in the *pexe*. All targets will observe the same
  24   behavior. In some cases, recompiling with a newer PNaCl SDK version
  25   will either:
  26
  27   * Reliably emit the same behavior in the resulting *pexe*.
  28   * Change the behavior that gets specified in the *pexe*.
  29
  30 * The behavior specified in the *pexe* relies on PNaCl's bitcode,
  31   runtime or CPU architecture vagaries.
  32
  33   * In some cases, the behavior using the same PNaCl translator version
  34     on different architectures will produce different behavior.
  35   * Sometimes runtime parameters determine the behavior, e.g. memory
  36     allocation determines which out-of-bounds accesses crash versus
  37     returning garbage.
  38   * In some cases, different versions of the PNaCl translator
  39     (i.e. after a Chrome update) will compile the code differently and
  40     cause different behavior.
  41   * In some cases, the same versions of the PNaCl translator, on the
  42     same architecture, will generate a different *nexe* for
  43     defense-in-depth purposes, but may cause code that reads invalid
  44     stack values or code sections on the heap to observe these
  45     randomizations.
  46
  47 Specification
  48 =============
  49
  50 PNaCl's goal is that a single *pexe* should work reliably in the same
  51 manner on all architectures, irrespective of runtime parameters and
  52 through Chrome updates. This goal is unfortunately not attainable; PNaCl
  53 therefore specifies as much as it can and outlines areas for
  54 improvement.
  55
  56 One interesting solution is to offer good support for LLVM's sanitizer
  57 tools (including `UBSan
  58 <http://clang.llvm.org/docs/UsersManual.html#controlling-code-generation>`_)
  59 at development time, so that developers can test their code against
  60 undefined behavior. Shipping code would then still get good performance,
  61 and diverging behavior would be rare.
  62
  63 Note that none of these issues are vulnerabilities in PNaCl and Chrome:
  64 the NaCl sandboxing still constrains the code through Software Fault
  65 Isolation.
  66
  67 Behavior in PNaCl Bitcode
  68 =========================
  69
  70 Well-Defined
  71 ------------
  72
  73 The following are traditionally undefined behavior in C/C++ but are well
  74 defined at the *pexe* level:
  75
  76 * Dynamic initialization order dependencies: the order is deterministic
  77   in the *pexe*.
  78 * Bool which isn't ``0``/``1``: the bitcode instruction sequence is
  79   deterministic in the *pexe*.
  80 * Out-of-range ``enum`` value: the backing integer type and bitcode
  81   instruction sequence is deterministic in the *pexe*.
  82 * Aggressive optimizations based on type-based alias analysis: TBAA
  83   optimizations are done before stable bitcode is generated and their
  84   metadata is stripped from the *pexe*; behavior is therefore
  85   deterministic in the *pexe*.
  86 * Operator and subexpression evaluation order in the same expression
  87   (e.g. function parameter passing, or pre-increment): the order is
  88   defined in the *pexe*.
  89 * Signed integer overflow: two's complement integer arithmetic is
  90   assumed.
  91 * Atomic access to a non-atomic memory location (not declared as
  92   ``std::atomic``): atomics and ``volatile`` variables all lower to the
  93   same compatible intrinsics or external functions; the behavior is
  94   therefore deterministic in the *pexe* (see :ref:`Memory Model and
  95   Atomics <memory_model_and_atomics>`).
  96 * Integer divide by zero: always raises a fault (through hardware on
  97   x86, and through integer divide emulation routine or explicit checks
  98   on ARM).
  99
 100 Not Well-Defined
 101 ----------------
 102
 103 The following are traditionally undefined behavior in C/C++ which also
 104 exhibit undefined behavior at the *pexe* level. Some are easier to fix
 105 than others.
 106
 107 Potentially Fixable
 108 ^^^^^^^^^^^^^^^^^^^
 109
 110 * Shift by greater-than-or-equal to left-hand-side's bit-width or
 111   negative (see `bug 3604
 112   <https://code.google.com/p/nativeclient/issues/detail?id=3604>`_).
 113
 114   * Some of the behavior will be specified in the *pexe* depending on
 115     constant propagation and integer type of variables.
 116   * There is still some architecture-specific behavior.
 117   * PNaCl could force-mask the right-hand-side to `bitwidth-1`, which
 118     could become a no-op on some architectures while ensuring all
 119     architectures behave similarly. Regular optimizations could also be
 120     applied, removing redundant masks.
 121
 122 * Using a virtual pointer of the wrong type, or of an unallocated
 123   object.
 124
 125   * Will produce wrong results which will depend on what data is treated
 126     as a `vftable`.
 127   * PNaCl could add runtime checks for this, and elide them when types
 128     are provably correct (see this CFI `bug 3786
 129     <https://code.google.com/p/nativeclient/issues/detail?id=3786>`_).
 130
 131 * Some unaligned load/store (see `bug 3445
 132   <https://code.google.com/p/nativeclient/issues/detail?id=3445>`_).
 133
 134   * Could force everything to `align 1`; performance cost should be
 135     measured.
 136   * The frontend could also be more pessimistic when it sees dubious
 137     casts.
 138
 139 * Some values can be marked as ``undef`` (see `bug 3796
 140   <https://code.google.com/p/nativeclient/issues/detail?id=3796>`_).
 141
 142 * Reaching end-of-value-returning-function without returning a value:
 143   reduces to ``ret i32 undef`` in bitcode. This is mostly-defined, but
 144   could be improved (see `bug 3796
 145   <https://code.google.com/p/nativeclient/issues/detail?id=3796>`_).
 146
 147 * Reaching “unreachable” code.
 148
 149   * LLVM provides an IR instruction called “unreachable” whose effect
 150     will be undefined.  PNaCl could change this to always trap, as the
 151     ``llvm.trap`` intrinsic does.
 152
 153 * Zero or negative-sized variable-length array (and ``alloca``) aren't
 154   defined behavior. PNaCl's frontend or the translator could insert
 155   checks with ``-fsanitize=vla-bound``.
 156
 157 .. _undefined_behavior_fp:
 158
 159 Floating-Point
 160 ^^^^^^^^^^^^^^
 161
 162 PNaCl offers a IEEE-754 implementation which is as correct as the
 163 underlying hardware allows, with a few limitations. These are a few
 164 sources of undefined behavior which are believed to be fixable:
 165
 166 * Float cast overflow is currently undefined.
 167 * Float divide by zero is currently undefined.
 168 * The default denormal behavior is currently unspecified, which isn't
 169   IEEE-754 compliant (denormals must be supported in IEEE-754). PNaCl
 170   could mandate flush-to-zero, and may give an API to enable denormals
 171   in a future release. The latter is problematic for SIMD and
 172   vectorization support, where some platforms do not support denormal
 173   SIMD operations.
 174 * ``NaN`` values are currently not guaranteed to be canonical; see `bug
 175   3536 <https://code.google.com/p/nativeclient/issues/detail?id=3536>`_.
 176 * Passing ``NaN`` to STL functions (the math is defined, but the
 177   function implementation isn't, e.g. ``std::min`` and ``std::max``), is
 178   well-defined in the *pexe*.
 179
 180 SIMD Vectors
 181 ^^^^^^^^^^^^
 182
 183 SIMD vector instructions aren't part of the C/C++ standards and as such
 184 their behavior isn't specified at all in C/C++; it is usually left up to
 185 the target architecture to specify behavior. Portable Native Client
 186 instead exposed :ref:`Portable SIMD Vectors <portable_simd_vectors>` and
 187 offers the same guarantees on these vectors as the guarantees offered by
 188 the contained elements. Of notable interest amongst these guarantees are
 189 those of alignment for load/store instructions on vectors: they have the
 190 same alignment restriction as the contained elements.
 191
 192 Hard to Fix
 193 ^^^^^^^^^^^
 194
 195 * Null pointer/reference has behavior determined by the NaCl sandbox:
 196
 197   * Raises a segmentation fault in the bottom ``64KiB`` bytes on all
 198     platforms, and on some sandboxes there are further non-writable
 199     pages after the initial ``64KiB``.
 200   * Negative offsets aren't handled consistently on all platforms:
 201     x86-64 and ARM will wrap around to the stack (because they mask the
 202     address), whereas x86-32 will fault (because of segmentation).
 203
 204 * Accessing uninitialized/free'd memory (including out-of-bounds array
 205   access):
 206
 207   * Might cause a segmentation fault or not, depending on where memory
 208     is allocated and how it gets reclaimed.
 209   * Added complexity because of the NaCl sandboxing: some of the
 210     load/stores might be forced back into sandbox range, or eliminated
 211     entirely if they fall out of the sandbox.
 212
 213 * Executing non-program data (jumping to an address obtained from a
 214   non-function pointer is undefined, can only do ``void(*)()`` to
 215   ``intptr_t`` to ``void(*)()``).
 216
 217   * Just-In-Time code generation is supported by NaCl, but is not
 218     currently supported by PNaCl. It is currently not possible to mark
 219     code as executable.
 220   * Offering full JIT capabilities would reduce PNaCl's ability to
 221     change the sandboxing model. It would also require a "jump to JIT
 222     code" syscall (to guarantee a calling convention), and means that
 223     JITs aren't portable.
 224   * PNaCl could offer "portable" JIT capabilities where the code hands
 225     PNaCl some form of LLVM IR, which PNaCl then JIT-compiles.
 226
 227 * Out-of-scope variable usage: will produce unknown data, mostly
 228   dependent on stack and memory allocation.
 229 * Data races: any two operations that conflict (target overlapping
 230   memory), at least one of which is a store or atomic read-modify-write,
 231   and at least one of which is not atomic: this will be very dependent
 232   on processor and execution sequence, see :ref:`Memory Model and
 233   Atomics <memory_model_and_atomics>`.