PartialExecuter: Reducing WebAssembly size by exploring all executions in LLVM

CheerpX looks amazing. Not blaming that project it in any way.

But rowhammer is still a thing.

There's a whole stack of abstractions, that all _may be_ vulnerable. I'm sure CheerpX is very good, but there's no way to _know_ that all the dependencies from the toolchain used to build all the way down to the running environment is actually bug free.

As a first line of investigation, I'd suspect cheerpX, just because so many eyes look at browser sandboxes. _shrug_ your milage may vary.

How does this differ from existing LLVM interprocedural optimizations? Particularly value propagation sounds like it would handle a lot of these cases.

> You might have heard of dead-code elimination, an LLVM optimization pass that removes code proven as unreachable. I was actually interested in less-obvious situations. In particular blocks that are reachable on the control flow graph, but not when consider wider execution invariants.

I've got a trivial example here: https://gcc.godbolt.org/z/7EnPG5WM6 noinline is added to foo to demonstrate Clang is actually changing the number of arguments foo takes, and its inlined the arguments from bar and baz.

> Can we use information on the call-sites and the corresponding format strings to prove that some code paths, for example formatting for floating point numbers, are actually never taken?

Seems to already have that effect in Clang. Using Emscripten 3.1.3, compiling 2 different main's with just

    printf("Hello world %d\n", argc);

And

    printf("Hello world %d %f\n", argc, volatileFloatArg);

For the single int arg, the top 3 symbols by size are

    47.7%  2.65Ki -NAN(IND)%       0    printf_core
     7.4%     421 -NAN(IND)%       0    [section Data]
     6.6%     375 -NAN(IND)%       0    main

And for the one that added a float arg,

    34.5%  3.04Ki -NAN(IND)%       0    fmt_fp
    28.8%  2.54Ki -NAN(IND)%       0    printf_core
     5.1%     464 -NAN(IND)%       0    [section Data]

So when a float argument wasn't passed into printf, it did not include fmt_fp, a delegate that handles floating point for printf

One issue that can complicate this analysis is linking multiple libraries that reference standard library (or functions in other libraries). If you're linking together object code, without more IR context, LLVM is going to have to be more conservative. So I think if you link in a WASM object code file that references printf, it won't be able to perform all the IPO that will allow it to trim the CFG.

You can Rowhammer from JavaScript already, so this really has nothing to do with CheerpX.

How much does this optimization save in terms of executable size on realistic examples (i.e. a full-sized code base)?

I would naively expect that for most functions you know too little about their arguments or the state in which they will be executed to be able to tell that certain branches will definitely not be taken. Especially since any function that has some mildly interesting side-effects (like loading and storing from a pointer or a class/struct field, or even _calling into any function that does that_) would seem to foil the analysis and turn large chunks of code into "unknown reachability".

Rephrasing, I would expect the set of basic blocks that can be removed just by essentially repeated constant propagation of statically-known function arguments to be pretty small. But I would be happy to be proved wrong if that intuition is not right.

Printf is somewhat of an exception, since the format strings are usually known at compile time, meaning that a lot of the control flow can indeed be deduced by compile-time evaluation, but for most functions I would not expect that.

I would be interested in the previously mentioned claims like “wasm can’t protect against rowhammer” —- while perhaps not an easily exploited vulnerability, and likely every current sandbox tech is vulnerable, is there anything specific to wasm that would help here?

Also, how does wasm relate to traditional sandboxes that “just” hijack system calls? Is there a difference?