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