Re: [riot-devel] To global seed or not to global seed

[Mathias Tausig]

On Mit, 2017-03-08 at 09:09 +0100, Kaspar Schleiser wrote:
> Hey,
> 
> On 03/08/2017 12:18 AM, Cenk Gündoğan wrote:
> > 
> > we rather
> > should opt to allow local states for each thread (not excluding a global
> > state).
> Interesting. Up to now our trouble with RNGs was mostly on how to make
> them more random. Now we're trying to make them predictable. What's your
> use case for that?

Using the random numbers for a stream cipher, for instance.

> How about an interface a la
> 
> rand_init_(rnd__t *rnd);
> rand_seed32(rnd_t *rnd, uint32_t);
> rand_seed(rnd_t *rnd, const uint8_t *in, size_t len);
> rand_get(rnd_t *rnd, uint8_t *out, size_t n);
> rand_get32(rnd_t *rnd);
> 
> typedef struct {
>   
> } rnd_t;
> 
> typedef struct {
>   rnd_t rnd;
>   ;
> } rnd_tinymt32_t;
> 
> That way we'd have:
> 
> - user controlled state
> - the ability to overload (e.g., combine hwrng, collected entropy, prng
> but with the same interface)
> 

Look good, imo.

cheers
Mathias



___
devel mailing list
devel@riot-os.org
https://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] To global seed or not to global seed

[Thomas C. Schmidt]

Hi Oleg, Ludwig,

On 08.03.2017 10:30, Oleg Hahm wrote:

Hi Ludwig!

On Wed, Mar 08, 2017 at 10:28:13AM +0100, Ludwig Knüpfer wrote:

Am 8. März 2017 10:21:15 MEZ schrieb Oleg Hahm :

Is testing and simulation the only use case you can imagine? I'm somewhat
reluctant to add code just for non-production purposes.


Since we outspokenly target researchers with RIOT this is a production feature.

However we might want to move this feature into a dedicated implementation
of the same interface.


Thanks, that was more or less what I meant.


I'm not sure whether we 'over-complicate' the issue.

There are good PRNGs with state space of one (or very few) int, call it 
seed. So if this function is called as 'rand(seed)', rand can be 
stateless ... and seed is allocated memory of the application. Seeds 
could be initially generated by 'random_init(seed)'.


At the same time, one can overload with a stateful 'rand()' which is 
auto-initialized and convenient ... and for those who don't care for 
more control. IMO, this would not need a 'random_init()' user call.


Cheers,
 Thomas


Btw: David Jones (UCL Bioinformatics) writes "Rule #1: Do not use system 
generators. ... Almost all of these generators are badly flawed. Even 
when they are not, there is no guarantee that they were not flawed in 
earlier releases of the library."



--

Prof. Dr. Thomas C. Schmidt
° Hamburg University of Applied Sciences   Berliner Tor 7 °
° Dept. Informatik, Internet Technologies Group20099 Hamburg, Germany °
° http://www.haw-hamburg.de/inet   Fon: +49-40-42875-8452 °
° http://www.informatik.haw-hamburg.de/~schmidtFax: +49-40-42875-8409 °
___
devel mailing list
devel@riot-os.org
https://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] To global seed or not to global seed

[Oleg Hahm]

Hi Ludwig!

On Wed, Mar 08, 2017 at 10:28:13AM +0100, Ludwig Knüpfer wrote:
> Am 8. März 2017 10:21:15 MEZ schrieb Oleg Hahm :
> >Is testing and simulation the only use case you can imagine? I'm somewhat
> >reluctant to add code just for non-production purposes.
> 
> Since we outspokenly target researchers with RIOT this is a production 
> feature.
> 
> However we might want to move this feature into a dedicated implementation
> of the same interface.

Thanks, that was more or less what I meant.

Cheers,
Oleg
-- 
The problem with TCPIP jokes is that when I tell them, all I want is an ACK but
usually get FINs and RSTs


signature.asc
Description: PGP signature
___
devel mailing list
devel@riot-os.org
https://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] To global seed or not to global seed

[Ludwig Knüpfer]

Hi,

Am 8. März 2017 10:21:15 MEZ schrieb Oleg Hahm :
>Is testing and simulation the only use case you can imagine? I'm
>somewhat
>reluctant to add code just for non-production purposes.

Since we outspokenly target researchers with RIOT this is a production feature.

However we might want to move this feature into a dedicated implementation of 
the same interface.

Cheers,
Ludwig
___
devel mailing list
devel@riot-os.org
https://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] To global seed or not to global seed

[Ludwig Knüpfer]

Hi,

Am 8. März 2017 10:06:17 MEZ schrieb "Cenk Gündoğan" :
>On 17-03-08 09:09:34, Kaspar Schleiser wrote: 
>> That way we'd have:
>> 
>> - user controlled state
>> - the ability to overload (e.g., combine hwrng, collected entropy,
>prng
>> but with the same interface)
>
>Looks good at first sight. We also would need some sort of
>synchronization for concurrent access, e.g. a mutex in the `rnd_t`
>struct, if two threads should use the same local state.

Just as a remark (might make sense to copy and paste to upcoming documentation):
If two threads are using the same local state they will probably not get 
deterministic numbers.

Cheers,
Ludwig
___
devel mailing list
devel@riot-os.org
https://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] To global seed or not to global seed

[Oleg Hahm]

Dear Cenk,

thanks for bringing up this discussion.

On Wed, Mar 08, 2017 at 12:18:28AM +0100, Cenk Gündoğan wrote:
 
> 1) we can define it as BCP to *not* use `random_init()` if `auto_init`
>is used
>=> it's hard to guarantee a one-time call to `random_init()` as human
>do surely err (especially if several nested modules are involved).

Basically, we have similar problems for other modules that should (or even
must) not be initialized twice. So far, my/our take on this was to document
this rather than programmatically prevent this. The memory overhead is small,
but existent, the runtime overhead is probably negligible for a function that
should not be called more than once.

> In contrast to the current procedure of having a global state, we rather
> should opt to allow local states for each thread (not excluding a global
> state).

Is testing and simulation the only use case you can imagine? I'm somewhat
reluctant to add code just for non-production purposes.

Cheers,
Oleg
-- 
/* vsprintf.c -- Lars Wirzenius & Linus Torvalds. */
 *
 * Wirzenius wrote this portably, Torvalds fucked it up :-)
 */
linux-2.2.16/lib/vsprintf.c


signature.asc
Description: PGP signature
___
devel mailing list
devel@riot-os.org
https://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] To global seed or not to global seed

[Kaspar Schleiser]

Hey,

On 03/08/2017 10:06 AM, Cenk Gündoğan wrote:
> 
>> How about an interface a la
>>
> Looks good at first sight. We also would need some sort of
> synchronization for concurrent access, e.g. a mutex in the `rnd_t`
> struct, if two threads should use the same local state.

Do we need that kind of synchronization if all state is localized in the
overloaded rnd_t, at that level?

Applications *seeding* the same state in multiple threads will be rare
and can synchronize externally.

Whether "reading" from the rng needs to be synchronized should be up to
the RNG implementation.

Kaspar



signature.asc
Description: OpenPGP digital signature
___
devel mailing list
devel@riot-os.org
https://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] To global seed or not to global seed

[Kaspar Schleiser]

Hey,

On 03/08/2017 12:18 AM, Cenk Gündoğan wrote:
> we rather
> should opt to allow local states for each thread (not excluding a global
> state).

Interesting. Up to now our trouble with RNGs was mostly on how to make
them more random. Now we're trying to make them predictable. What's your
use case for that?

How about an interface a la

rand_init_(rnd__t *rnd);
rand_seed32(rnd_t *rnd, uint32_t);
rand_seed(rnd_t *rnd, const uint8_t *in, size_t len);
rand_get(rnd_t *rnd, uint8_t *out, size_t n);
rand_get32(rnd_t *rnd);

typedef struct {

} rnd_t;

typedef struct {
rnd_t rnd;
;
} rnd_tinymt32_t;

That way we'd have:

- user controlled state
- the ability to overload (e.g., combine hwrng, collected entropy, prng
but with the same interface)

Kaspar



signature.asc
Description: OpenPGP digital signature
___
devel mailing list
devel@riot-os.org
https://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] To global seed or not to global seed

[Cenk Gündoğan]

Hey,

oh sure, here it follows:

```
The ISO C standard rand() and srand() functions allow per-process
pseudo-random streams shared by all threads. Those two functions need
not change, but there has to be mutual-exclusion that prevents
interference between two threads concurrently accessing the random
number generator.

With regard to rand(), there are two different behaviors that may be
wanted in a multi-threaded program:

1. A single per-process sequence of pseudo-random numbers that is shared
   by all threads that call rand()
2. A different sequence of pseudo-random numbers for each thread that
   calls rand()

This is provided by the modified thread-safe function based on whether
the seed value is global to the entire process or local to each thread.
```
See: http://pubs.opengroup.org/onlinepubs/9699919799/functions/rand.html

The above prose makes me wonder: our current
global-state-PRNG-implementations do AFAIK not provide mutual
exclusion.. So, two threads accessing the PRNG could get in each other's
way (?). And this is not just about `random_init()`, but all calls that
modify an existing PRNG sequence, such as a simple `rand()`.

Just as info: in the above link it says:

```
The drand48() and random() functions provide much more elaborate
pseudo-random number generators.
```

and those do actually allow to intuitively set custom states, or do
mutual exclusion:
http://pubs.opengroup.org/onlinepubs/9699919799/functions/random.html
http://pubs.opengroup.org/onlinepubs/9699919799/functions/drand48.html

Cheers,
Cenk

On 17-03-08 00:26:02, Thomas C. Schmidt wrote:
> Hi Cenk,
> 
> thanks for bringing this up!
> 
> Can you add the POSIX perspective to the rand* calls? I guess it would be
> beneficial to remain close to what POSIX describes for an API.
> 
> Cheers,
>  Thomas
> 
> On 08.03.2017 00:18, Cenk Gündoğan wrote:
> > Dear RIOTers,
> > 
> > for quite some time now we have semi-active discussions (mostly on
> > GitHub) about various PRNG and seeding concepts. In this mail I merely
> > want to focus on the scope of our PRNG implementations' seeds/states.
> > 
> > Currently, all function calls in our PRNG implementations and the
> > abstraction layer `sys/random` do *not* allow to pass a custom state.
> > This means, there is *one* global state, that is overwritten with
> > successive calls to `random_init()`, not necessarily from the same
> > thread. At the moment, `auto_init` is the only instance, that calls
> > `random_init` (albeit with `0`, but this is another story). So
> > everything seems to be OK for now (?), but will it stay this way? In the
> > current state, and to guarantee deterministic PRNG sequences, all calls
> > to `random_init()` *must* be ignored, but not the first. Of course, this
> > can be done in various ways ..
> > 
> > 1) we can define it as BCP to *not* use `random_init()` if `auto_init`
> >is used
> >=> it's hard to guarantee a one-time call to `random_init()` as human
> >do surely err (especially if several nested modules are involved).
> > 
> > 2) check within `random_init()` for an unitialized state and only
> >initialize if such a state is prevalent. Ignore the call to
> >`random_init()` if the PRNG was initialized before.
> >=> this introduces a further check that is done with each call to
> >`random_init()` and feigns to the user a freshly initialized PRNG.
> > 
> > In contrast to the current procedure of having a global state, we rather
> > should opt to allow local states for each thread (not excluding a global
> > state). Although I have no special use case in mind at the moment, I
> > believe that it should be possible to let user applications initialize
> > "their own PRNG" to produce deterministic sequences. With the current
> > approach, the sequence of our PRNG is shared with all available threads.
> > This means, a user application would share the sequence with the network
> > stack's NDP, RPL, TCP, ... implementations.
> > 
> > IMO, our random API needs to be extended to provide function definitions
> > that also allow the passing of local seed states. However, different
> > PRNGs use different kind / different numbers of seeds. A "local scope"
> > seed struct would need to encapsulate enough information to be usable
> > with all PRNGs; and that's the part that deserves some thinking.
> > 
> > What is your opinion on having / allowing local scope seed states?
> > 
> > Cheers,
> > Cenk
> > 
> 
> -- 
> 
> Prof. Dr. Thomas C. Schmidt
> ° Hamburg University of Applied Sciences   Berliner Tor 7 °
> ° Dept. Informatik, Internet Technologies Group20099 Hamburg, Germany °
> ° http://www.haw-hamburg.de/inet   Fon: +49-40-42875-8452 °
> ° http://www.informatik.haw-hamburg.de/~schmidtFax: +49-40-42875-8409 °
> ___
> devel mailing list
> devel@riot-os.org
> https://lists.riot-os.org/mailman/listinfo/devel


signature.asc
Description: PGP signature

[riot-devel] To global seed or not to global seed

[Cenk Gündoğan]

Dear RIOTers,

for quite some time now we have semi-active discussions (mostly on
GitHub) about various PRNG and seeding concepts. In this mail I merely
want to focus on the scope of our PRNG implementations' seeds/states.

Currently, all function calls in our PRNG implementations and the
abstraction layer `sys/random` do *not* allow to pass a custom state.
This means, there is *one* global state, that is overwritten with
successive calls to `random_init()`, not necessarily from the same
thread. At the moment, `auto_init` is the only instance, that calls
`random_init` (albeit with `0`, but this is another story). So
everything seems to be OK for now (?), but will it stay this way? In the
current state, and to guarantee deterministic PRNG sequences, all calls
to `random_init()` *must* be ignored, but not the first. Of course, this
can be done in various ways ..

1) we can define it as BCP to *not* use `random_init()` if `auto_init`
   is used
   => it's hard to guarantee a one-time call to `random_init()` as human
   do surely err (especially if several nested modules are involved).

2) check within `random_init()` for an unitialized state and only
   initialize if such a state is prevalent. Ignore the call to
   `random_init()` if the PRNG was initialized before.
   => this introduces a further check that is done with each call to
   `random_init()` and feigns to the user a freshly initialized PRNG.

In contrast to the current procedure of having a global state, we rather
should opt to allow local states for each thread (not excluding a global
state). Although I have no special use case in mind at the moment, I
believe that it should be possible to let user applications initialize
"their own PRNG" to produce deterministic sequences. With the current
approach, the sequence of our PRNG is shared with all available threads.
This means, a user application would share the sequence with the network
stack's NDP, RPL, TCP, ... implementations.

IMO, our random API needs to be extended to provide function definitions
that also allow the passing of local seed states. However, different
PRNGs use different kind / different numbers of seeds. A "local scope"
seed struct would need to encapsulate enough information to be usable
with all PRNGs; and that's the part that deserves some thinking.

What is your opinion on having / allowing local scope seed states?

Cheers,
Cenk


signature.asc
Description: PGP signature
___
devel mailing list
devel@riot-os.org
https://lists.riot-os.org/mailman/listinfo/devel