Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Random number generation bugs #1076

Closed
jsbarber opened this issue Jul 20, 2020 · 2 comments · Fixed by #1081
Closed

Random number generation bugs #1076

jsbarber opened this issue Jul 20, 2020 · 2 comments · Fixed by #1081
Assignees
Labels
Type: Bug 🐛 Unexpected behavior or output.
Milestone

Comments

@jsbarber
Copy link
Contributor

Issue 1:
There is code in init_random_seed that checks if HAVE_GETRANDOM is defined and, when set, calls getrandom to fill a buffer with random data. However, the code then bypasses the code block that uses the buffer to create the actual seed value from the random data. It then calls bro_srandom with a seed value of 0 and a "true" second argument (which causes bro_rand_determistic to be set). Hence, the seed is always set the same. See https://try.zeek.org/#/tryzeek/saved/440256:

# Issues 1 - 3
event zeek_init()
	{
	local i = 0;
	while (i < 20)
		{
		print rand(65535);
		i += 1;
		}
	}

Issue 2:
I presume this would be considered by design, but bro_rand_deterministic always get set and hence the system random function is never used; instead the built-in bro_prng is used. (Which, at a minimum contradicts the documentation.)

Issue 3:
When the seed is 0, bro_prng returns the same one value (0x7fffffff) continuously.

Issue 4:
bro_prng also violates the constraint that its return value should be less than or equal to the system RAND_MAX. This in turn causes the BiF rand function to violate its specification: it can return a value greater than the max argument. (Due to issue 3, this only occurs if you re-seed the generator.)

For issue 4, https://try.zeek.org/#/tryzeek/saved/440259:

event zeek_init()
	{
	srand(0x7d662799A);
	local i = 0;
	while (i < 40)
		{
		local rn = rand(65535);
		if (rn > 65535)
			print "ACK", rn;
		i += 1;
		}
	}
@jsiwek jsiwek added this to Unassigned / Todo in Release 3.2.0 via automation Jul 21, 2020
@jsiwek jsiwek added this to the 3.2.0 milestone Jul 21, 2020
@jsiwek jsiwek added the Type: Bug 🐛 Unexpected behavior or output. label Jul 21, 2020
@jsiwek jsiwek self-assigned this Jul 21, 2020
jsiwek added a commit that referenced this issue Jul 21, 2020
The availability and use of getrandom() actually caused unrandom and
deterministic results in terms of Zeek's random number generation.
jsiwek added a commit that referenced this issue Jul 22, 2020
The intermediate result of the PRNG used unsigned storage, preventing
the ( result < 0 ) branch from ever being evaluated.  This could cause
return values to exceed the modulus as well as RAND_MAX.

One interesting effect of this is potential for the rand() BIF to
return values outside the requested maximum limit.

Another interesting effect of this is that a PacketFilter may start
randomly dropping packets even if it was not configured for
random-packet-drops.
jsiwek added a commit that referenced this issue Jul 22, 2020
The bro_prng() implementation cannot generate 0 as a result since it
causes every subsequent number from the PRNG to also be 0, so use the
number 1 instead of 0.
jsiwek added a commit that referenced this issue Jul 22, 2020
The availability and use of getrandom() actually caused unrandom and
deterministic results in terms of Zeek's random number generation.
jsiwek added a commit that referenced this issue Jul 22, 2020
The intermediate result of the PRNG used unsigned storage, preventing
the ( result < 0 ) branch from ever being evaluated.  This could cause
return values to exceed the modulus as well as RAND_MAX.

One interesting effect of this is potential for the rand() BIF to
return values outside the requested maximum limit.

Another interesting effect of this is that a PacketFilter may start
randomly dropping packets even if it was not configured for
random-packet-drops.
jsiwek added a commit that referenced this issue Jul 22, 2020
The bro_prng() implementation cannot generate 0 as a result since it
causes every subsequent number from the PRNG to also be 0, so use the
number 1 instead of 0.
@jsiwek
Copy link
Contributor

jsiwek commented Jul 22, 2020

@jsbarber Thanks for reporting those, #1081 should address the issues if you'd like to confirm. Particularly:

timwoj added a commit that referenced this issue Jul 23, 2020
* origin/topic/jsiwek/gh-1076-fix-random:
  Deprecate bro_srandom(), replace with zeek::seed_random().
  Add zeek::max_random() & fix misuse of RAND_MAX w/ zeek::random_number()
  Deprecate bro_random(), replace with zeek::random_number()
  Deprecate bro_prng(), replace with zeek::prng()
  GH-1076: Fix bro_srandom() to replace 0 seeds with 1
  GH-1076: Fix bro_prng() implementation
  GH-1076: Fix use of getrandom()
Release 3.2.0 automation moved this from Unassigned / Todo to Done Jul 23, 2020
@jsbarber
Copy link
Contributor Author

@jsiwek Looks good to me. Thanks!

jsiwek added a commit that referenced this issue Jul 24, 2020
The intermediate result of the PRNG used unsigned storage, preventing
the ( result < 0 ) branch from ever being evaluated.  This could cause
return values to exceed the modulus as well as RAND_MAX.

One interesting effect of this is potential for the rand() BIF to
return values outside the requested maximum limit.

Another interesting effect of this is that a PacketFilter may start
randomly dropping packets even if it was not configured for
random-packet-drops.

(cherry picked from commit 0f4eb9a)
jsiwek added a commit that referenced this issue Jul 24, 2020
The bro_prng() implementation cannot generate 0 as a result since it
causes every subsequent number from the PRNG to also be 0, so use the
number 1 instead of 0.

(cherry picked from commit 887b53b)
jsiwek added a commit that referenced this issue Jul 24, 2020
The intermediate result of the PRNG used unsigned storage, preventing
the ( result < 0 ) branch from ever being evaluated.  This could cause
return values to exceed the modulus as well as RAND_MAX.

One interesting effect of this is potential for the rand() BIF to
return values outside the requested maximum limit.

Another interesting effect of this is that a PacketFilter may start
randomly dropping packets even if it was not configured for
random-packet-drops.

(cherry picked from commit 0f4eb9a)
jsiwek added a commit that referenced this issue Jul 24, 2020
The bro_prng() implementation cannot generate 0 as a result since it
causes every subsequent number from the PRNG to also be 0, so use the
number 1 instead of 0.

(cherry picked from commit 887b53b)
jsiwek added a commit that referenced this issue Jul 24, 2020
The availability and use of getrandom() actually caused unrandom and
deterministic results in terms of Zeek's random number generation.

(cherry picked from commit dba7643)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Type: Bug 🐛 Unexpected behavior or output.
Projects
No open projects
Release 3.2.0
  
Done
Development

Successfully merging a pull request may close this issue.

2 participants