Unprivileged bpf()

Posted Oct 15, 2015 6:31 UTC (Thu) by ibukanov (subscriber, #3942)
Parent article: Unprivileged bpf()

This sounds like the verifier itself is going to be rather complex code. I wonder if that can be simplified if BPF would not be some binary bytecode but rather an encoded AST for a higher level language as used, for example, for WebAssembly. It is much simpler to verify AST and translate it into an internal bytecode or even JIT it than to write a correct verifier for bytecode.

to post comments

Unprivileged bpf()

Posted Oct 15, 2015 7:10 UTC (Thu) by iq-0 (subscriber, #36655) [Link] (1 responses)

I think the low-level verification is better than a higher level one. A high level verifier might give a better explanation about why it would reject some particular construct, but multiple higher level constructs would map to similar lower level bytecode, so it would have to take into consideration a lot more cases.

In contrast the low-level verification only has to permit certain operations on certain values (the trick is knowing which operations on which type of value are needed and which can be abused), no matter the construct used to generate that operation.

And the more those AST have a direct correspondence to their bytecode the smaller the difference will be between both approaches. A bytecode can easily be transformed into an AST for an albeit very low-level language.

Unprivileged bpf()

Posted Oct 15, 2015 7:43 UTC (Thu) by ibukanov (subscriber, #3942) [Link]

Preventing information leakage is very difficult so it is better to start with a restrictive whitelist of allowed constructs than one can be reasonably sure are safe and gradually widen the set. It is much easier to implement such white-list in a higher level verifier precisely because it can distinguish a particular code pattern with much less efforts and O(N) complexity.

Otherwise I am afraid that a story of Java bytecode verification would repeat itself, albeit of a smaller scale. It took years for Sun to iron out bugs. Then it turned out that they could not do better then O(N**4) complexity in the worst case of the verification making DoS against a browser trivial. So they were forced to extend the bytecode format with extra information to simply the job for the verifier. That bloated already rather fat bytecode and introducing subtle compatibility bugs in quite a few applications.