BPF_MISC+BPF_COP and BPF_COPX

[Mindaugas Rasiukevicius]

Hello,

I would like propose new BPF instructions for the misc category: BPF_COP
and BPF_COPX. It would provide a capability of calling an external
function - think of BPF "coprocessor". The argument for BPF_COP is an
index to a pre-loaded array of function pointers. BPF_COPX takes the
function index from the register X rather than a constant.

BPF_STMT(BPF_MISC+BPF_COP, 0), /* A <- funcs[0](...) */

typedef uint32_t(*bpf_copfunc_t)(struct mbuf *pkt,
uint32_t A, uint32_t *M);

int bpf_set_cop(bpf_ctx_t *c, bpf_copfunc_t funcs[], size_t n);

The arguments passed to a called function would be the packet, accumulator
and the memory store. The return value would be stored in the accumulator
and the register X would be reset to 0. Note that the function may also
change the memory store. If the function index is out of range, then the
register X would be set to 0xffffffff.

Note that bpf_filter(9) would need to take some context structure (which is
preferable in general).

Comments?

[Rui Paulo]

Post by Mindaugas Rasiukevicius
Hello,
I would like propose new BPF instructions for the misc category: BPF_COP
and BPF_COPX. It would provide a capability of calling an external
function - think of BPF "coprocessor". The argument for BPF_COP is an
index to a pre-loaded array of function pointers. BPF_COPX takes the
function index from the register X rather than a constant.
BPF_STMT(BPF_MISC+BPF_COP, 0), /* A <- funcs[0](...) */
typedef uint32_t(*bpf_copfunc_t)(struct mbuf *pkt,
uint32_t A, uint32_t *M);
int bpf_set_cop(bpf_ctx_t *c, bpf_copfunc_t funcs[], size_t n);
The arguments passed to a called function would be the packet, accumulator
and the memory store. The return value would be stored in the accumulator
and the register X would be reset to 0. Note that the function may also
change the memory store. If the function index is out of range, then the
register X would be set to 0xffffffff.
Note that bpf_filter(9) would need to take some context structure (which is
preferable in general).
Comments?

Why do you need this in the first place?
Are you sure this is a safe design? Adding this functionality to BPF makes me a little nervous as an error in the implementation leads to kernel code execution (I could be able to call random kernel functions).

--
Rui Paulo


--
Posted automagically by a mail2news gateway at muc.de e.V.
Please direct questions, flames, donations, etc. to news-***@muc.de

[Mindaugas Rasiukevicius]

Post by Rui Paulo

Post by Mindaugas Rasiukevicius
Comments?

Why do you need this in the first place?

It provides us a capability to offload more complex packet processing.
My primary user would be NPF in NetBSD, e.g. one of the operations is to
lookup an IP address in a table/ipset.

Post by Rui Paulo
Are you sure this is a safe design? Adding this functionality to BPF
makes me a little nervous as an error in the implementation leads to
kernel code execution (I could be able to call random kernel functions).

This is functionality is for a custom use of BPF. There would be no
coprocessor by default and the instruction would essentially be a NOP.
Perhaps I was not clear on bpf_set_cop(9) - it is a kernel routine, so
the user would be a kernel subsystem which has a full control over the
functions it provides. The functions are predetermined, not random.

[Mindaugas Rasiukevicius]

I think it's slightly unfair to propose a new extension for BPF
without any in-tree users.

Post by Mindaugas Rasiukevicius
It provides us a capability to offload more complex packet processing.
My primary user would be NPF in NetBSD, e.g. one of the operations is to
lookup an IP address in a table/ipset.

I would like to coordinate the reservation of BPF opcodes though.

[Christos Zoulas]

Post by Mindaugas Rasiukevicius
Hello,
I would like propose new BPF instructions for the misc category: BPF_COP
and BPF_COPX. It would provide a capability of calling an external
function - think of BPF "coprocessor". The argument for BPF_COP is an
index to a pre-loaded array of function pointers. BPF_COPX takes the
function index from the register X rather than a constant.
BPF_STMT(BPF_MISC+BPF_COP, 0), /* A <- funcs[0](...) */
typedef uint32_t(*bpf_copfunc_t)(struct mbuf *pkt,
uint32_t A, uint32_t *M);
int bpf_set_cop(bpf_ctx_t *c, bpf_copfunc_t funcs[], size_t n);
The arguments passed to a called function would be the packet, accumulator
and the memory store. The return value would be stored in the accumulator
and the register X would be reset to 0. Note that the function may also
change the memory store. If the function index is out of range, then the
register X would be set to 0xffffffff.

Well, aside from the consideration that somehow bpf needs to understand
what memory locations the coproc function alters (so that it considers
them initialized), the bigger question is how does the code for those
functions gets loaded and unloaded, and which bpf programs have access to
those functions.

christos


--
Posted automagically by a mail2news gateway at muc.de e.V.
Please direct questions, flames, donations, etc. to news-***@muc.de

[Alexander Nasonov]

Post by Mindaugas Rasiukevicius
Hello,
I would like propose new BPF instructions for the misc category: BPF_COP
and BPF_COPX. It would provide a capability of calling an external
function - think of BPF "coprocessor". The argument for BPF_COP is an
index to a pre-loaded array of function pointers. BPF_COPX takes the
function index from the register X rather than a constant.
BPF_STMT(BPF_MISC+BPF_COP, 0), /* A <- funcs[0](...) */
typedef uint32_t(*bpf_copfunc_t)(struct mbuf *pkt,
uint32_t A, uint32_t *M);
int bpf_set_cop(bpf_ctx_t *c, bpf_copfunc_t funcs[], size_t n);
The arguments passed to a called function would be the packet, accumulator
and the memory store. The return value would be stored in the accumulator
and the register X would be reset to 0. Note that the function may also
change the memory store. If the function index is out of range, then the
register X would be set to 0xffffffff.

I like the idea but I have some questions:

1. Why do you need access to scratch memory? Is your goal to keep a
state for C code between cop calls? In this case, you can use
the standard void* pointer technique. You'd need to define special
getter/setter cop functions and they will be slower than getting/setting
scratch memory but it's more important to keep a very clear separation
between C code and bpf code. You'd also need to pass void* to
bpf_filter(9), of course.

2. Why do you set X to 0 and 0xffffffff? For the out-of-range access,
all other bpf code aborts filter program with code 0. I think it's
better to keep X unchanged.

3. Can cop "patch" itself or other cop functions at runtime? It'd be
much safe if an array of cop functions was read-only. As an
additional benefit when using bpfjit, you could generate direct calls
for BPF_COP (but not for BPF_COPX) in bpfjit_generate_code().

Alex

--
Posted automagically by a mail2news gateway at muc.de e.V.
Please direct questions, flames, donations, etc. to news-***@muc.de

[Alexander Nasonov]

Yes, I may want to keep the state in the memory store or pass the arguments
through it, since the accumulator might not be enough.

You have access to a whole packet, why do you need to pass additional
arguments through the store? I'm worried about introducing tight
coupling between these two very different environments and adding
"sugar" for easy interaction is a big step in this direction.

If you prefer getter
and setter to perform a boundary check and enforce uint32_t type, I am fine
with that. Although BPF_MEMWORDS constant and words storing 32-bit values
stayed since 80s.. it is not going to change.
However, abusing void * is wrong. Once bpf_filter(9) is adjusted to take
an opaque struct bpf_ctx *, the memory store ought to be moved into it.

Ah, you plan to generalize scratch memory. It's probably fine but don't
generalize too many things because people (me at least) want to be able
to recognize the original bpf and its orignal design.

Please note that I allocate scratch memory on the stack in bpfjit.
If you change scratch memory to be under bpf_ctx, you will need to
reimplement quite a lot in bpfjit code.

The rationale behind it is that we might want to handle out-of-range in the
byte-code without breaking the flow. This can be a valid case for BPF_COPX.
Just BPF_RET 0 seems a limitation, but I do not have a strong feeling here.

I'd keep it consistent with bpf.

Alex

--
Posted automagically by a mail2news gateway at muc.de e.V.
Please direct questions, flames, donations, etc. to news-***@muc.de

[Mindaugas Rasiukevicius]

Post by Alexander Nasonov

Yes, I may want to keep the state in the memory store or pass the
arguments through it, since the accumulator might not be enough.

You have access to a whole packet, why do you need to pass additional
arguments through the store? I'm worried about introducing tight
coupling between these two very different environments and adding
"sugar" for easy interaction is a big step in this direction.

Why is it a problem? Given that the byte-code and the functions would come
from the same source, some coupling seems natural to me. It is simplistic
anyway: some already parsed offsets or values could be passed through the
memory store.

Post by Alexander Nasonov

If you prefer getter
and setter to perform a boundary check and enforce uint32_t type, I am
fine with that. Although BPF_MEMWORDS constant and words storing
32-bit values stayed since 80s.. it is not going to change.
However, abusing void * is wrong. Once bpf_filter(9) is adjusted to
take an opaque struct bpf_ctx *, the memory store ought to be moved
into it.

Ah, you plan to generalize scratch memory. It's probably fine but don't
generalize too many things because people (me at least) want to be able
to recognize the original bpf and its orignal design.

Well, you suggested getter/setter. :)

Post by Alexander Nasonov
Please note that I allocate scratch memory on the stack in bpfjit.
If you change scratch memory to be under bpf_ctx, you will need to
reimplement quite a lot in bpfjit code.

Is it really a lot? We can waste some cycles and just copy them into the
stack (if there are any initial values).

[Alexander Nasonov]

Post by Mindaugas Rasiukevicius
Why is it a problem? Given that the byte-code and the functions would come
from the same source, some coupling seems natural to me. It is simplistic
anyway: some already parsed offsets or values could be passed through the
memory store.

You surely have some picture in mind but I can't get it. I'm a bit
worried that two different environments may look unnatural when married
together.
Perhaps, you should right a proposal with some use-cases to support your
points.

Post by Mindaugas Rasiukevicius

Post by Alexander Nasonov
Ah, you plan to generalize scratch memory. It's probably fine but don't
generalize too many things because people (me at least) want to be able
to recognize the original bpf and its orignal design.

Well, you suggested getter/setter. :)

Yeah, please write a proposal ;-)

Post by Mindaugas Rasiukevicius

Post by Alexander Nasonov
Please note that I allocate scratch memory on the stack in bpfjit.
If you change scratch memory to be under bpf_ctx, you will need to
reimplement quite a lot in bpfjit code.

Is it really a lot? We can waste some cycles and just copy them into the
stack (if there are any initial values).

Not really a lot given a size of bpfjit.c but if you hit some limitation
of sljit, be prepared to do extra coding to work around it.

Alex

--
Posted automagically by a mail2news gateway at muc.de e.V.
Please direct questions, flames, donations, etc. to news-***@muc.de

[Mindaugas Rasiukevicius]

Post by Mindaugas Rasiukevicius
I would like propose new BPF instructions for the misc category: BPF_COP
and BPF_COPX. It would provide a capability of calling an external
function - think of BPF "coprocessor".

No.

You do not have to use it.

A BPF program is an entity that can be verified as correct from a
security perspective.It is also self contained and requires no
external references in order to understand.
This change brakes the BPF security model because now the BPF program
is calling out to some random function as part of the packet matching.

BPF byte-code can still be verified. You cannot call random functions,
the functions are predetermined and cannot change during the life-cycle.
There is a difference. However, it is as secure as calling any other
function in the kernel on packet transmission. You can make a bug in
your function, but you can as well make it in tcp_input().

Post by Mindaugas Rasiukevicius
It provides us a capability to offload more complex packet processing.
My primary user would be NPF in NetBSD, e.g. one of the operations is to
lookup an IP address in a table/ipset.

Then add BPF instructions to manipulate address sets (add, remove, lookup)
and pick a datastore to use to support it.

How adding specialised random instructions is better than having a generic
mechanism? You mean BPF_SOME_LOOKUP calling some_lookup() suddenly becomes
more secure than BPF_MISC+BPF_COP calling the same some_lookup()?

In doing that the benefits can thereafter be applied to other programs
(such as tcpdump) that have a large list of entities that need to be
matched against.

They can grow such support using coprocessor. There is no reason why
there could not be a generic (or custom) coprocessor which you could
simply modload, if you trust it (or blacklist if you do not).

[Mindaugas Rasiukevicius]

Post by Mindaugas Rasiukevicius
You do not have to use it.

I get no choice - it is in the kernel by default.

There is no default coprocessor. Here is your choice: do not call
bpf_set_cop(9) and those instructions will effectively be NOPs.

<...>
No. It's not about calling a function, it is about proving the BPF
program is correct and secure.
BPF today is essentially assembly language operations that are all
easily tested and verified.
<...>

Post by Mindaugas Rasiukevicius

A BPF program is an entity that can be verified as correct from a
security perspective.It is also self contained and requires no
external references in order to understand.

How is this relevant for the discussion?

It is important to understand what BPF is before making changes to it.

It is *your* understanding with a premise you just came up. I do not
think that your premise is universally accepted.

The reason why we have bpf_validate(9) is to ensure that the byte-code
cannot cause any harm to the kernel (whether it is an infinite loop, a
crash or any other security vulnerability), because it is passed from
the *user*. The fundamental difference is that the coprocessor comes
from the *kernel*. We tend to trust that the kernel is not self-harming
and compilers do constructive job. We cannot validate that (unless you
want to challenge Turing's halting problem), but the point being is that
we do not need to.

Post by Mindaugas Rasiukevicius

Then add BPF instructions to manipulate address sets (add, remove,
lookup) and pick a datastore to use to support it.

How is that more useful than the proposal?

Actually, add/remove are not instructions for the BPF language,
only lookup. Add, remove, etc, would be handled in the usual manner.
How is that more useful?

You contradict yourself here. It still calls some "external reference"
which you are arguing against.

The capability of the opcodes is programmed into the BPF program,
not through some external reference. A BPF program generated on
Linux is just as valid as on Solaris or NetBSD. Whilst that may
be meaningless because nobody copies BPF programs around (in byte
code format), this would open a door on developing specialised
behaviour for "my platform" that isn't present elsewhere. This
then diminishes the value of BPF.

When I was thinking of BPF_COP/BPF_COPX, I was thinking of MIPS. The
capability of the opcodes does not have to be programmed into the BPF
program. You still have a core set of BPF instructions which will work
everywhere and there is a reason why we have BPF_MISC. I can understand
the concern about platforms implementing different behaviour, but your
proposal of adding an instruction for every specific operation is not
going to help. It is a question of agreement (hence CC freebsd-net).

[Mindaugas Rasiukevicius]

Steven,

There's a one-word summary: *assurance*. With the current design,
it's easy to *know* what can happen. With a Turing-complete extension,
it isn't.

It is still easy and the concept itself is very simple. I mentioned that
this extension does not make byte-code Turing-complete and the rest is in
your control. Darren ignored it.

[Joerg Sonnenberger]

A BPF program is an entity that can be verified as correct from a
security perspective.It is also self contained and requires no
external references in order to understand.

How is this relevant for the discussion?

Post by Mindaugas Rasiukevicius
It provides us a capability to offload more complex packet processing.
My primary user would be NPF in NetBSD, e.g. one of the operations is to
lookup an IP address in a table/ipset.

Then add BPF instructions to manipulate address sets (add, remove, lookup)
and pick a datastore to use to support it.

How is that more useful than the proposal?

The BPF design has some serious limitations for modern network
protocols. For example, the forward-jump-only property makes it
impossible to write rules for protocols with arbitrary header
composition. While it is not desirable to completely remove this
restriction, the proposal could help to deal with many of the
interesting case efficently.

In doing that the benefits can thereafter be applied to other programs
(such as tcpdump) that have a large list of entities that need to be
matched against.

tcpdump would just as well use the BPF extensions provided here.

Joerg

--
Posted automagically by a mail2news gateway at muc.de e.V.
Please direct questions, flames, donations, etc. to news-***@muc.de

[Mindaugas Rasiukevicius]

Post by Alexander Nasonov

Post by Mindaugas Rasiukevicius
Why is it a problem? Given that the byte-code and the functions would
come from the same source, some coupling seems natural to me. It is
simplistic anyway: some already parsed offsets or values could be
passed through the memory store.

You surely have some picture in mind but I can't get it. I'm a bit
worried that two different environments may look unnatural when married
together.

OK, but you did not explain why is it a problem i.e. why is it worrying?

Post by Alexander Nasonov
Perhaps, you should right a proposal with some use-cases to support your
points.

They are simple: consider detecting IP version and calculating the offset
to L4 header. There is no reason to duplicate this work in the byte-code
and the coprocessor. If one of them does it - let's just save it.

Post by Alexander Nasonov

Post by Mindaugas Rasiukevicius

Post by Alexander Nasonov
Ah, you plan to generalize scratch memory. It's probably fine but
don't generalize too many things because people (me at least) want to
be able to recognize the original bpf and its orignal design.

Well, you suggested getter/setter. :)

Yeah, please write a proposal ;-)

int bpf_get_memword(const bpf_ctx_t *c, size_t i, uint32_t *val);
int bpf_set_memword(bpf_ctx_t *c, size_t i, uint32_t val);

You prefer something like this?

[Thor Lancelot Simon]

Post by Mindaugas Rasiukevicius
Steven,

There's a one-word summary: *assurance*. With the current design,
it's easy to *know* what can happen. With a Turing-complete extension,
it isn't.

It is still easy and the concept itself is very simple. I mentioned that
this extension does not make byte-code Turing-complete and the rest is in
your control. Darren ignored it.

Yes, but since the extension makes the program no longer consist solely
of bytecode, it tends to give the impression that the program may now
be, in total, in a Turing-complete language. It blurs the boundary
between the program and its interpreter, by allowing the bytecode to
directly call into the interpreter. Or am I missing something?

I think what you want to do may be a good idea, in the end, but I do
think it calls for what others are requesting: a real problem statement
and an explanation of why the proposed solution is safer than it would
at first appear.

Thor

--
Posted automagically by a mail2news gateway at muc.de e.V.
Please direct questions, flames, donations, etc. to news-***@muc.de

[Mouse]

Post by Thor Lancelot Simon
Yes, but since the extension makes the program no longer consist
solely of bytecode, it tends to give the impression that the program
may now be, in total, in a Turing-complete language. It blurs the
boundary between the program and its interpreter, by allowing the
bytecode to directly call into the interpreter.

Like pretty much any bytecode, BPF bytecode is _nothing but_ direct
calls into the interpreter. Except for psychological effects, this
whole modification is nothing but reserving a particular range of
bytecodes for per-(kernel-)user-of-bpf custom uses.

Mind you, psychological effects can be important. But I think the
biggest psychological effect here is the one that is causing most of
the trouble: the way this is named and was described make it sound as
though it is more general, and less safe, than it actually is. It
bothered me too at first, but when it was clarified that a given COP
function is not automatically available to every BPF program in the
system just because it's available to one, I've been unable to come up
with a reason to dislike this that I can actually defend to myself.

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

--
Posted automagically by a mail2news gateway at muc.de e.V.
Please direct questions, flames, donations, etc. to news-***@muc.de

[Matt Thomas]

Post by Thor Lancelot Simon

Post by Mindaugas Rasiukevicius
Steven,

There's a one-word summary: *assurance*. With the current design,
it's easy to *know* what can happen. With a Turing-complete extension,
it isn't.

It is still easy and the concept itself is very simple. I mentioned that
this extension does not make byte-code Turing-complete and the rest is in
your control. Darren ignored it.

Yes, but since the extension makes the program no longer consist solely
of bytecode, it tends to give the impression that the program may now
be, in total, in a Turing-complete language. It blurs the boundary
between the program and its interpreter, by allowing the bytecode to
directly call into the interpreter. Or am I missing something?

You already have to trust the interpreter, you are now extending that
trust to who invoked the interpreter. One aspect of all this is
that by allowing the invoker to setup the initial register set used
by the BPF program and then having access to it after it returns, you
can have BPF do more sophisticated things than just returning a scalar.

The possibility of the COP/COPX functions doing bad things is over
wrought. It makes the assumption of avoiding BPF and then coding
everything is safer than using BPF and COP/COPX functions.

--
Posted automagically by a mail2news gateway at muc.de e.V.
Please direct questions, flames, donations, etc. to news-***@muc.de

[Mindaugas Rasiukevicius]

Post by Thor Lancelot Simon

Post by Mindaugas Rasiukevicius
Steven,

There's a one-word summary: *assurance*. With the current design,
it's easy to *know* what can happen. With a Turing-complete
extension, it isn't.

It is still easy and the concept itself is very simple. I mentioned
that this extension does not make byte-code Turing-complete and the
rest is in your control. Darren ignored it.

Yes, but since the extension makes the program no longer consist solely
of bytecode, it tends to give the impression that the program may now
be, in total, in a Turing-complete language. It blurs the boundary
between the program and its interpreter, by allowing the bytecode to
directly call into the interpreter. Or am I missing something?

I think "impression" is the right word here. :) The extension i.e. the
coprocessor cannot change the flow of your program. It can inspect the
packet in a read-only manner and return couple 32-bit numbers. Nothing
really more, unless you are abusing the provided interface and writing
some crazy coprocessor functions. However, you can as well write crazy
code in tcp_input(). I think we have enough common sense to not do that.

Post by Thor Lancelot Simon
I think what you want to do may be a good idea, in the end, but I do
think it calls for what others are requesting: a real problem statement
and an explanation of why the proposed solution is safer than it would
at first appear.

The problem is simple: I want a generic mechanism to offload more complex
packet inspection operations, e.g. lookup IP address in some container or
walk IPv6 headers and return some offsets. There is no reason why we need
a separate instruction for each operation, it can (and I argue that it
should) be generic.

[Mindaugas Rasiukevicius]

Hi,
- Problem
There is a need to perform more complex operations from the BPF program.
Currently, there is no (practical) way to do that from the byte-code.
Such functionality is useful for the packet filters or other components,
which could integrate with BPF. For example, while most of the packet
inspection logic can stay in the byte-code, such operations as looking
up an IP address in some container or walking the IPv6 headers and
returning some offsets have to be done externally. The first existing
user of such capability would be NPF in NetBSD.

I'd argue that the IPv6 problem is of such a generic nature that
it deserves its own instruction/s. We may look at IPv6 today and
think nobody uses it much but over time that is going to change.
Thus there will be an outcome not possible with co-processor
approach if an instruction is created for that purpose and is
common across all platforms through libpcap. Unless the IPv6
problem is too complex for a single instruction (this has not
been demonstrated.) In that case maybe BPF itself needs to evolve
such that it can support more complex instructions.

This is a separate issue. Feel free to propose an new instruction to
parse IPv6 headers.

The current implementation of BPF makes it very hard to expand
the instruction set without impinging on the ability to make
future changes due to the way in which instructions are codified
into 32bits. Whilst the method of supporting a co-processor gets
around that, it does so in such a generic fashion that it becomes
too easy to use it as a bit-bucket for anything you think might
be a good idea if BPF could do without really evaluating if it
should do.

It is certainly possible that some operations, which will be implemented
using BPF coprocessor, will be useful in general. Again, whether such
operations should be "promoted" to be new BPF instructions or there should
be a global "standardised" coprocessor or how BPF should evolve (including
RISC vs CISC-like instruction set debate) is a separate discussion.

[Mindaugas Rasiukevicius]

Hi,

Post by Mindaugas Rasiukevicius

Post by Mindaugas Rasiukevicius
It provides us a capability to offload more complex packet
processing. My primary user would be NPF in NetBSD, e.g. one of the
operations is to lookup an IP address in a table/ipset.

I would like to coordinate the reservation of BPF opcodes though.

That's a good idea. I have no problem with that.

I have added these to the NetBSD tree:

#define BPF_MISCOP(code) ((code) & 0xf8)
#define BPF_TAX 0x00
+#define BPF_COP 0x20
+#define BPF_COPX 0x40
#define BPF_TXA 0x80

Would you like to reserve them in FreeBSD as well?

Thanks.