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