docs/StackSafetyAnalysis.rst

   1 ==================================
   2 Stack Safety Analysis
   3 ==================================
   4
   5
   6 Introduction
   7 ============
   8
   9 The Stack Safety Analysis determines if stack allocated variables can be
  10 considered 'safe' from memory access bugs.
  11
  12 The primary purpose of the analysis is to be used by sanitizers to avoid
  13 unnecessary instrumentation of 'safe' variables. SafeStack is going to be the
  14 first user.
  15
  16 'safe' variables can be defined as variables that can not be used out-of-scope
  17 (e.g. use-after-return) or accessed out of bounds. In the future it can be
  18 extended to track other variable properties. E.g. we plan to extend
  19 implementation with a check to make sure that variable is always initialized
  20 before every read to optimize use-of-uninitialized-memory checks.
  21
  22 How it works
  23 ============
  24
  25 The analysis is implemented in two stages:
  26
  27 The intra-procedural, or 'local', stage performs a depth-first search inside
  28 functions to collect all uses of each alloca, including loads/stores and uses as
  29 arguments functions. After this stage we know which parts of the alloca are used
  30 by functions itself but we don't know what happens after it is passed as
  31 an argument to another function.
  32
  33 The inter-procedural, or 'global', stage, resolves what happens to allocas after
  34 they are passed as function arguments. This stage performs a depth-first search
  35 on function calls inside a single module and propagates allocas usage through
  36 functions calls.
  37
  38 When used with ThinLTO, the global stage performs a whole program analysis over
  39 the Module Summary Index.
  40
  41 Testing
  42 =======
  43
  44 The analysis is covered with lit tests.
  45
  46 We expect that users can tolerate false classification of variables as
  47 'unsafe' when in-fact it's 'safe'. This may lead to inefficient code. However, we
  48 can't accept false 'safe' classification which may cause sanitizers to miss actual
  49 bugs in instrumented code. To avoid that we want additional validation tool.
  50
  51 AddressSanitizer may help with this validation. We can instrument all variables
  52 as usual but additionally store stack-safe information in the
  53 ``ASanStackVariableDescription``. Then if AddressSanitizer detects a bug on
  54 a 'safe' variable we can produce an additional report to let the user know that
  55 probably Stack Safety Analysis failed and we should check for a bug in the
  56 compiler.