lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:	Mon, 21 Apr 2014 15:20:18 -0700
From:	Alexei Starovoitov <ast@...mgrid.com>
To:	Chema Gonzalez <chema@...gle.com>
Cc:	David Miller <davem@...emloft.net>,
	Eric Dumazet <edumazet@...gle.com>,
	Daniel Borkmann <dborkman@...hat.com>,
	Network Development <netdev@...r.kernel.org>
Subject: Re: [PATCH v2] filter: added BPF random opcode

On Mon, Apr 21, 2014 at 2:54 PM, Chema Gonzalez <chema@...gle.com> wrote:
> On Mon, Apr 21, 2014 at 2:46 PM, Alexei Starovoitov <ast@...mgrid.com> wrote:
>> as I was saying in the other thread, would be nice to see more
>> realistic example, since "icmp 1 in 4" can be done in user space...
>> What is the real problem being solved?
>> I suspect for true packet sampling you'd need to have the knowledge
>> of packet rate, potentially computing time delta within filter with
>> another extension?
>> The patch itself looks good to me.
> Random sampling. There's a huge performance penalty if you do this in
> user-space. You don't want to send all the packets to user-space to
> just get (e.g.) 1 in 1000 and discard all the others.

Of course.
Just 1 out of 4 example you gave wasn't very real.

> From http://www.icir.org/vern/papers/secondary-path-raid06.pdf:

Nice. Now I see where it's going :)
The article helps a lot.

Acked-by: Alexei Starovoitov <ast@...mgrid.com>

btw it's funny how different people think of similar things.
It seems to complete what you wanted in the article you'd need
table access from the filter.
Did you have a chance to look at my bpf table proposal?
It seems it will fit perfectly to your use case as well.

Here is the copy paste from the other thread:
-----
Similar basic interface I'm proposing to use for bpf tables.
Probably makes sense to drop 'bpf' prefix, since they're just
hash tables. Little to do with bpf.
Have a netlink API from user into kernel:
- create hash table (num_of_entries, key_size, value_size, id)
- dump table via netlink
- add/remove key/value pair
Some kernel module may use it to transfer the data between
kernel and userspace.
This can be a generic kernel/user data sharing facility.

Also let bpf programs do 'table_lookup/update', so that
filters can store interesting data.
--------
I've posted early bpf_table patches back in September...
Now in process of redoing them with cleaner interface.

Thanks

> When dealing with large volumes of network traffic, we can often
> derive significant
> benefit while minimizing the processing cost by employing sampling.
> Generally, this
> is done on either a per-packet or per-connection basis. BPF does not
> provide access
> to pseudo-random numbers, so applications have had to rely on proxies
> for random-
> ness in terms of network header fields with some semblance of entropy
> across packets
> (checksum and IP fragment identifier fields) or connections (ephemeral
> ports). These
> sometimes provide acceptable approximations to random sampling, but
> can also suffer
> from significant irregularities due to lack of entropy or aliasing;
> see [11] for an analysis.
>
> -Chema
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Powered by blists - more mailing lists