Added a new Verifier class to the BPF compiler.

Added a new Verifier class to the BPF compiler.

This class ensures that the generated BPF program does in fact represent the
filters that we were asked to compile. Having a verifier will allow us to make
more aggressive optimizations in the future without having to worry that we
generate invalid code.

BUG=130662
TEST=make && demo32 && demo64


Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=142258

[jln (very slow on Chromium), 2012-06-07 22:55:17]

A first wave of (quite easy to fix) concerns.

I really hope I can convince you once and for all about die() / exit.

I thinks this should be used exceedingly rarely, as it makes function re-use
difficult. That's especially the case for function that are not part of the
public interface, since you dictate what they do when they return.

https://chromiumcodereview.appspot.com/10546041/diff/6001/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/verifier.cc (right):

https://chromiumcodereview.appspot.com/10546041/diff/6001/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:13: // Evaluate the BPF filter program for
all possible inputs and
Could you document the API in the interface instead?

https://chromiumcodereview.appspot.com/10546041/diff/6001/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:14: // verify that it computes the correct
result.
We will probably never iterate over all possible input, especially with
arguments, right?

There is some room to iterate over some really large sets, but that especially
works if we make this part of a unit test, rather than something that will run
every time we compile a new policy.

https://chromiumcodereview.appspot.com/10546041/diff/6001/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:20: // it terminates the program by
calling Sandbox::die().
See my remark about dying in the interface

https://chromiumcodereview.appspot.com/10546041/diff/6001/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:29: ;
This is roughly an emulator. Can be very useful. Do you mind having this as a
separate function ?

https://chromiumcodereview.appspot.com/10546041/diff/6001/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/verifier.h (right):

https://chromiumcodereview.appspot.com/10546041/diff/6001/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.h:19: public:
I would really prefer if this returned a bool or an int.

We really want the caller to be able to make the decision of what to do next.

There are two likely callers:
1. our own code in sandbox_bpf.cc -> we can handle error fine
2. tests -> It's nice if we can put some stuff in automated tests. die() / exit
make this really painful.

https://chromiumcodereview.appspot.com/10546041/diff/6001/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.h:44: static void ret(State *state, const
struct sock_filter& insn);
Looks like Verifier is not meant to be instanciated. Do you mind to make the
constructor private etc? Chrome provides helpers for this.

https://chromiumcodereview.appspot.com/10546041/diff/6001/sandbox/sandbox.gyp
File sandbox/sandbox.gyp (right):

https://chromiumcodereview.appspot.com/10546041/diff/6001/sandbox/sandbox.gyp...
sandbox/sandbox.gyp:155: [ 'OS=="linux"', {
Don't forget to rebase your branch before trying to commit

[Markus (顧孟勤), 2012-06-08 02:47:03]

I think I addressed all your concerns by refactoring the error handling. And
after a bit of a fight and some conflict resolving, I rebased the change list in
git.

Please take another look.

[jln (very slow on Chromium), 2012-06-08 19:28:22]

LGTM

https://chromiumcodereview.appspot.com/10546041/diff/6002/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/sandbox_bpf.cc (right):

https://chromiumcodereview.appspot.com/10546041/diff/6002/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:300: die(err);
I don't like it when functions have u needed side effects, but it's consistent
with the rest of the function, so fine.

https://chromiumcodereview.appspot.com/10546041/diff/6002/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/sandbox_bpf.h (right):

https://chromiumcodereview.appspot.com/10546041/diff/6002/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.h:111: #define
DISALLOW_IMPLICIT_CONSTRUCTORS(TypeName) \
If/once we make demo.cc a proper test in Chrome, I think we should re-use what's
already provided in base::
But yes, it's convenient to have independent code for now.

https://chromiumcodereview.appspot.com/10546041/diff/6002/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/verifier.cc (right):

https://chromiumcodereview.appspot.com/10546041/diff/6002/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:14: if (evaluators.size() != 1) {
Can you also check for !err ?

https://chromiumcodereview.appspot.com/10546041/diff/6002/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:75: *err = NULL;
Check !err here too ? (as this is part of the interface)

[Markus (顧孟勤), 2012-06-08 20:04:24]

https://chromiumcodereview.appspot.com/10546041/diff/6002/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/sandbox_bpf.cc (right):

https://chromiumcodereview.appspot.com/10546041/diff/6002/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:300: die(err);
On 2012/06/08 19:28:22, Julien Tinnes wrote:
> I don't like it when functions have u needed side effects, but it's consistent
> with the rest of the function, so fine.

There actually is something slightly sub-optimal with error reporting right now.
I'll send you another CL shortly to hopefully make you happier.

https://chromiumcodereview.appspot.com/10546041/diff/6002/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/verifier.cc (right):

https://chromiumcodereview.appspot.com/10546041/diff/6002/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:14: if (evaluators.size() != 1) {
On 2012/06/08 19:28:22, Julien Tinnes wrote:
> Can you also check for !err ?

I was originally intending to make error reporting mimic how errno works. That
is, neither the caller nor the callee sets it, unless there actually is an
error.

But it turns out, that makes the code more complicated and a little harder to
read. So, now I changed the API to explicitly guarantee that "err" will always
be set. That should address your concern.

[Markus (顧孟勤), 2012-06-08 20:08:12]

On Fri, Jun 8, 2012 at 12:28 PM, <jln@chromium.org> wrote:

> https://chromiumcodereview.**appspot.com/10546041/diff/**
>
6002/sandbox/linux/seccomp-**bpf/sandbox_bpf.h#newcode111<https://chromiumcodereview.appspot.com/10546041/diff/6002/sandbox/linux/seccomp-bpf/sandbox_bpf.h#newcode111>
> sandbox/linux/seccomp-bpf/**sandbox_bpf.h:111: #define
> DISALLOW_IMPLICIT_**CONSTRUCTORS(TypeName) \
> If/once we make demo.cc a proper test in Chrome, I think we should
> re-use what's already provided in base::
> But yes, it's convenient to have independent code for now.
>

I know that there have been projects other than Chrome that use the old
seccomp sandbox. If it doesn't cost me much extra work, I am trying to give
them a transition path to the new seccomp code, as the old one is really
supposed to go away everywhere.

So, there is some incentive for me to make sure that the sandbox code can
be built independent of Chrome. But if this starts getting too complicated,
I'll stop doing so. For now, the cost is minimal, and I actually benefit
from being able to quickly test things.


Markus

[Chris Evans, 2012-06-11 19:20:41]

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/sandbox_bpf.cc (right):

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:259: for (int sysnum = MIN_SYSCALL;
sysnum <= MAX_SYSCALL+1; ++sysnum) {
Should sysnum be signed?

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:298: const char *err;
Initialize to NULL for safety, since it's a pointer?

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:299: if (!Verifier::verifyBPF(program,
evaluators_, &err)) {
I think we should only do this step under #ifdef DEBUG. That would likely be
enough to catch any problems pre-production, without any runtime cost in
production. Having just read verifier.cc, the runtime cost seems non-trivial.

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/sandbox_bpf.h (right):

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.h:114: void operator=(const TypeName&)
Does this work? The prototype for the assignment operator returns TypeName& (no
const)

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.h:161: typedef
std::vector<std::pair<EvaluateSyscall,EvaluateArguments> >Evaluators;
Missing spaces?

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/verifier.cc (right):

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:105: if (insn.k < sizeof(struct
arch_seccomp_data) && (insn.k & 3) == 0) {
I think you need to check against insn.k + sizeof(state->accumulator) ?
You'll also probably need to check than insn.k+4 does not integer overflow.

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:109: 4);
Use sizeof(state->accumulator) instead of 4 ?

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:121: state->ip += insn.k;
Missing check? You check to see if the addition is in-bounds for the other jumps
types.

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/verifier.h (right):

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.h:57: bool                                  
accIsValid;
Maybe use DISALLOW_IMPLICIT_CONSTRUCTORS in this struct too if you don't expect
it to be copied?

[Markus (顧孟勤), 2012-06-11 20:58:43]

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/sandbox_bpf.cc (right):

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:259: for (int sysnum = MIN_SYSCALL;
sysnum <= MAX_SYSCALL+1; ++sysnum) {
On 2012/06/11 19:20:41, Chris Evans wrote:
> Should sysnum be signed?

Yes, a future change list is actually changing it to "uint32_t". That's going to
make reasoning about the correctness a little easier, even if it doesn't really
change behavior.

I just pulled this change forward.

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:298: const char *err;
On 2012/06/11 19:20:41, Chris Evans wrote:
> Initialize to NULL for safety, since it's a pointer?

Done.

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.cc:299: if (!Verifier::verifyBPF(program,
evaluators_, &err)) {
On 2012/06/11 19:20:41, Chris Evans wrote:
> I think we should only do this step under #ifdef DEBUG. That would likely be
> enough to catch any problems pre-production, without any runtime cost in
> production. Having just read verifier.cc, the runtime cost seems non-trivial.

I am on the fence. Execution time various somewhere between 500us and 2ms,
depending on cache effects and on what else the machine is doing.

Does this matter in production? I don't know. On the one hand I like the extra
security of always running the verifier and I suspect that process start-up
already dwarfs the cost of sandbox start-up.

But on the other hand, I realize that people do strange things, and maybe we are
in fact starting hundred of sandbox'd processes per second -- in that case, an
extra millisecond is noticeable.

I put it behind an #ifdef for now. We might want to revisit in the future,
though.

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/sandbox_bpf.h (right):

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.h:114: void operator=(const TypeName&)
On 2012/06/11 19:20:41, Chris Evans wrote:
> Does this work? The prototype for the assignment operator returns TypeName&
(no
> const)

Dunno. I am not the C++ expert here :-)

But this is what we do in basictypes.h -- so, hopefully it works correctly.

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.h:161: typedef
std::vector<std::pair<EvaluateSyscall,EvaluateArguments> >Evaluators;
On 2012/06/11 19:20:41, Chris Evans wrote:
> Missing spaces?

If I add the space, I need to wrap the line; and it's already hard to read as
is.

Any preference how you would prefer to format this line? Or is this the best we
can do.

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/verifier.cc (right):

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:105: if (insn.k < sizeof(struct
arch_seccomp_data) && (insn.k & 3) == 0) {
On 2012/06/11 19:20:41, Chris Evans wrote:
> I think you need to check against insn.k + sizeof(state->accumulator) ?

I think, this logic is already correct, as we are checking both size and
alignment.

BPF is a /very/ restrictive language. And we are possibly even more restrictive.
We only allow 32bit reads and only on 32bit boundaries.

> You'll also probably need to check than insn.k+4 does not integer overflow.

No need to add 4. As I said, the alignment check takes care of that.

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:109: 4);
On 2012/06/11 19:20:41, Chris Evans wrote:
> Use sizeof(state->accumulator) instead of 4 ?

I want to be really explicit that BPF is defined with 32bit data types for
everything.

But if you think that sizeof() is more readable and does a better job of
conveying the intent, you can persuade me.

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:121: state->ip += insn.k;
On 2012/06/11 19:20:41, Chris Evans wrote:
> Missing check? You check to see if the addition is in-bounds for the other
jumps
> types.

Done.

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/verifier.h (right):

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.h:57: bool                                  
accIsValid;
On 2012/06/11 19:20:41, Chris Evans wrote:
> Maybe use DISALLOW_IMPLICIT_CONSTRUCTORS in this struct too if you don't
expect
> it to be copied?

Done.

Although there wouldn't be any harm, if anybody did try to copy it.

[Chris Evans, 2012-06-12 18:23:01]

https://chromiumcodereview.appspot.com/10546041/diff/8007/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/verifier.cc (right):

https://chromiumcodereview.appspot.com/10546041/diff/8007/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:121: if (state->ip + insn.k + 1 >=
state->program.size()) {
Integer overflow. This would permit a huge k that effectively jumps backward.
Since you use unsigned types, you can just check if state->ip got smaller after
the additions.

https://chromiumcodereview.appspot.com/10546041/diff/8007/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/verifier.cc:131: state->ip + insn.jf + 1 >=
state->program.size()) {
These are integer overflow free because jt and jf are just 8-bits wide. k above
is 32-bits

[Chris Evans, 2012-06-12 20:37:55]

lgtm

[jln (very slow on Chromium), 2012-06-12 20:52:14]

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
File sandbox/linux/seccomp-bpf/sandbox_bpf.h (right):

https://chromiumcodereview.appspot.com/10546041/diff/7014/sandbox/linux/secco...
sandbox/linux/seccomp-bpf/sandbox_bpf.h:114: void operator=(const TypeName&)
On 2012/06/11 20:58:43, Markus (顧孟勤) wrote:
> On 2012/06/11 19:20:41, Chris Evans wrote:
> > Does this work? The prototype for the assignment operator returns TypeName&
> (no
> > const)
> 
> Dunno. I am not the C++ expert here :-)
> 
> But this is what we do in basictypes.h -- so, hopefully it works correctly.

Indeed, return value types are not part of a function's signature for
overloading purposes.

[commit-bot: I haz the power, 2012-06-14 20:42:15]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/markus@chromium.org/10546041/2005

[commit-bot: I haz the power, 2012-06-14 20:42:16]

Failed to apply patch for sandbox/linux/seccomp-bpf/Makefile:
While running patch -p1 --forward --force;
patching file sandbox/linux/seccomp-bpf/Makefile
Hunk #1 FAILED at 1.
1 out of 1 hunk FAILED -- saving rejects to file
sandbox/linux/seccomp-bpf/Makefile.rej

[commit-bot: I haz the power, 2012-06-14 20:49:13]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/markus@chromium.org/10546041/4004

[commit-bot: I haz the power, 2012-06-14 23:12:18]

Change committed as 142258