When is a store not (memory) safe?

Hi all,

I am trying to identify when a write to memory (store) is safe or not (based on LLVM IR).
I refer "safe" to spatial safety (no out of bounds write) and not temporal safety (no double free() etc).

My current approach would be to declare every pointer as unsafe that is computed somewhere by a GEP instruction with non constant indices, as well as constant indices that can be proven to be out of
bounds (but that would be more a thing for the compiler to complain).

Is that approach about right?
Are there other situations where spatial safety might be violated?
Are there already analysis that can determine something like this?

Thanks you.

Regards,

Fredi

Hi,

My current approach would be to declare every pointer as unsafe that is computed somewhere by a GEP instruction with non constant indices, as well as constant indices that can be proven to be out of
bounds (but that would be more a thing for the compiler to complain).

Are you assuming that you see the entire program (something like using LTO)? Otherwise one of the main difficulties will be that the provenance of pointers are unknown. For example, you might see a function that receives a pointer argument, and have no idea where that function is called from. Or some code might use a global, and you don’t know what the value of the global is. Or a pointer is read from memory, and you don’t know which instruction modified it.

There is definitely a lot of work already in this area. For large real-world software, I believe the idea of proving memory safety is not feasible yet; for those people tend to use dynamic (run-time) checks instead, e.g., AddressSanitizer.

For statically proving accesses, there are ideas such as abstract interpretation, model checking, CEGAR, separation logic… I think a good place to get an overview of current tools is the software verification competition. Some of the participants there are open-source and based on LLVM.

Cheers,
Jonas

Thanks for your hints, they give me a good overview.

I am not trying to achieve complete memory safety. I wrote a pass that does some safety checks for every store instruction. Now I want to optimize my pass by avoiding to instrument checks for store instructions that are somehow provable “memory safe”. So, I am only looking for some easy and obvious cases where I can optimize for performance.

Hi,

I am not trying to achieve complete memory safety. I wrote a pass that does some safety checks for every store instruction. Now I want to optimize my pass by avoiding to instrument checks for store instructions that are somehow provable “memory safe”. So, I am only looking for some easy and obvious cases where I can optimize for performance.

The first thing I’d do is compile with -O3 before you run your pass. In this case, SROA will already take care of many of the easy cases, and convert the loads/stores into registers.

That said, SoftBound uses similar optimizations. See for example the code here: https://github.com/santoshn/softboundcets-3.8.0/blob/master/llvm-38/lib/Transforms/Instrumentation/SoftBoundCETS.cpp#L3244

Another thing: in most cases the optimizations will not matter. In a typical program, there are only very few checks that cause most of the overhead. It’s the checks that are in hot loops. Incidentally, those are loop-dependent, and thus hard to prove safe. You might be better off using a tool such as ASAP that automatically recognizes and removes such checks.

Full disclaimer: I’m one of the authors of ASAP. If you want to try it out, I’m happy to help make it work for your use-case.

Best,
Jonas