Malicious eBPF - slow JIT via expensive static analysis

[jon-chuang]

I'd like to know what the worst case compilation+static analysis time for an eBPF program of size up to 10MB, by causing the static analysis to become very slow (for instance, jumping randomly on every instruction).

Still, a BTreeMap with 10M entries with integer keys doesn't seem that daunting... Cfg graph also has branching factor at most 2 - this means at most 20M edges.

[Lichtso]

Short answer: We don't know and it is quite likely that it can even run into infinite loops.
That is why we currently use the static analysis for debugging only and not in production.

[jon-chuang]

I see, thanks.

May I know if a non-uniform opcode compute unit cost table is on the horizon? In the other issue I created, I argue for why it could be sensible to do so: #185.

I mistakenly assumed that CFG analysis was for the express purpose of facilitating the use of the compute meter for a non-uniform opcode cost.

[Lichtso]

The static analysis was developed for a number of reasons:

• Better debugging tools (what it is currently used for)
• Hoist VM address translation from loop bodies outward (planned, but not implemented)
• Advanced machine code diversification (this turned out to be impossible because of dynamic jumps)

[jon-chuang]

I see, thanks.

Maybe it's worth considering this if static analysis is used for async compilation of cached executors in the future.