Bug #45301 [Ana]: Serious flaw in array_rand()
| From: | cmb@php.net | Date: | Wed, 05 Aug 2015 12:09:46 +0000 |
| Subject: | Bug #45301 [Ana]: Serious flaw in array_rand() | ||
| References: | 1 | Groups: | php.bugs |
| Request: | Send a blank email to php-bugs+get-194964@lists.php.net to get a copy of this message | ||
Edit report at https://bugs.php.net/bug.php?id=45301&edit=1
ID: 45301
Updated by: cmb@php.net
Reported by: payton2558 at googlemail dot com
-Summary: Serious flaw in random related functions
+Summary: Serious flaw in array_rand()
Status: Analyzed
Type: Bug
Package: Math related
Operating System: win32 only
PHP Version: *
Assigned To: pajoye
Block user comment: N
Private report: N
New Comment:
>> What about merging a patch that circulated in @internals that
>> made rand() and alias to mt_rand() and be done with this ?
>
> Because it may not fix the problem? (see the other report today
> and two weeks ago).
For reference, these reports are bug #45302 (which is a duplicate
of this ticket) and bug #45184 (which is about the scaling issue
that affects rand() as well as mt_rand(); see also PR #1416[1]).
[1] <https://github.com/php/php-src/pull/1416>
Previous Comments:
------------------------------------------------------------------------
[2015-07-30 11:32:13] cmb@php.net
The problem is the way array_rand() works, in combination with the
limited random number range available on Windows. The function
loops over all elements[1], calculating a new random number for
each, and checks whether to draw the current element[2]. However,
on Windows PHP_RAND_MAX == 32767, so this condition is likely to
be false for large num_avail. Particularly, when num_req == 1,
what is the default, the condition *can* only be true if either
randval == 0 or num_avail < PHP_RAND_MAX+1; the latter case
requires randval to be rather small still.
In practise, randval is always equal to zero for the OP's second
test script, so the random generator is always seeded to zero for
the next random operation.
On Linux, PHP_RAND_MAX == (2**31)-1, so this algorithm is less of
a problem, but still there may be issues for *very* large arrays.
If we can ignore these (so large an array won't easily fit into
memory), a solution would be to use php_mt_rand() instead of
php_rand() (and to seed the the MT random number generator
automatically).
[1] <https://github.com/php/php-src/blob/php-7.0.0beta2/ext/standard/array.c#L4547-L4573>
[2] <https://github.com/php/php-src/blob/php-7.0.0beta2/ext/standard/array.c#L4554>
------------------------------------------------------------------------
[2014-05-08 14:19:00] levim@php.net
Bug https://bugs.php.net/bug.php?id=67233 is a
duplicate of this one.
------------------------------------------------------------------------
[2014-02-15 15:49:10] timo dot fiersen at web dot de
Looks like my previous comment got lost... I was wondering if this is going to be fixed some day, it
seems to exist for ages already?
Or did this maybe just popped up again, because I'm experiencing the exact same problem with
5.5.x, calling array_random() kills all randomness.
PHP: 5.5.6 and 5.5.9 (both TS)
OS: Windows 7 x64
------------------------------------------------------------------------
[2009-10-30 22:15:26] scott046 at hotmail dot com
If anybody is interested, this code:
<?php
print("20 element array; apparently no problem<br>\r\n");
$array1 = array();
$counter1 = 0;
while($counter1 < 20) {
$array1[] = $counter1;
$counter1++;
}
$print_counter1 = 0;
while($print_counter1 < 10) {
print($array1[array_rand($array1)] . "<br>\r\n");
$print_counter1++;
}
print("<br>\r\n<br>\r\n200 element array; apparently no
problem<br>\r\n");
$array1 = array();
$counter1 = 0;
while($counter1 < 200) {
$array1[] = $counter1;
$counter1++;
}
$print_counter1 = 0;
while($print_counter1 < 10) {
print($array1[array_rand($array1)] . "<br>\r\n");
$print_counter1++;
}
print("<br>\r\n<br>\r\n2000 element array; apparently no
problem<br>\r\n");
$array1 = array();
$counter1 = 0;
while($counter1 < 2000) {
$array1[] = $counter1;
$counter1++;
}
$print_counter1 = 0;
while($print_counter1 < 10) {
print($array1[array_rand($array1)] . "<br>\r\n");
$print_counter1++;
}
print("<br>\r\n<br>\r\n10000 element array; apparent problem: mild
repetition<br>\r\n");
$array1 = array();
$counter1 = 0;
while($counter1 < 10000) {
$array1[] = $counter1;
$counter1++;
}
$print_counter1 = 0;
while($print_counter1 < 10) {
print($array1[array_rand($array1)] . "<br>\r\n");
$print_counter1++;
}
print("<br>\r\n<br>\r\n20000 element array; apparent problem:
repetition<br>\r\n");
$array1 = array();
$counter1 = 0;
while($counter1 < 20000) {
$array1[] = $counter1;
$counter1++;
}
$print_counter1 = 0;
while($print_counter1 < 10) {
print($array1[array_rand($array1)] . "<br>\r\n");
$print_counter1++;
}
print("<br>\r\n<br>\r\n30000 element array; apparent problem:
repetition<br>\r\n");
$array1 = array();
$counter1 = 0;
while($counter1 < 30000) {
$array1[] = $counter1;
$counter1++;
}
$print_counter1 = 0;
while($print_counter1 < 10) {
print($array1[array_rand($array1)] . "<br>\r\n");
$print_counter1++;
}
print("<br>\r\n<br>\r\n50000 element array; apparent problem:
repetition<br>\r\n");
$array1 = array();
$counter1 = 0;
while($counter1 < 50000) {
$array1[] = $counter1;
$counter1++;
}
$print_counter1 = 0;
while($print_counter1 < 10) {
print($array1[array_rand($array1)] . "<br>\r\n");
$print_counter1++;
}
print("<br>\r\n<br>\r\n100000 element array; 32767=2^15-1 repeating;
<br>\r\n");
$array1 = array();
$counter1 = 0;
while($counter1 < 100000) {
$array1[] = $counter1;
$counter1++;
}
$print_counter1 = 0;
while($print_counter1 < 10) {
print($array1[array_rand($array1)] . "<br>\r\n");
$print_counter1++;
}
print("<br>\r\n<br>\r\n200000 element array; 32767=2^15-1 repeating;
<br>\r\n");
$array1 = array();
$counter1 = 0;
while($counter1 < 200000) {
$array1[] = $counter1;
$counter1++;
}
$print_counter1 = 0;
while($print_counter1 < 10) {
print($array1[array_rand($array1)] . "<br>\r\n");
$print_counter1++;
}
print("<br>\r\n<br>\r\n300000 element array; 32767=2^15-1 repeating;
<br>\r\n");
$array1 = array();
$counter1 = 0;
while($counter1 < 300000) {
$array1[] = $counter1;
$counter1++;
}
$print_counter1 = 0;
while($print_counter1 < 10) {
print($array1[array_rand($array1)] . "<br>\r\n");
$print_counter1++;
}
?>
produces this output:
20 element array; apparently no problem
16
5
11
9
17
7
15
2
8
9
200 element array; apparently no problem
43
25
147
127
127
2
109
14
67
165
2000 element array; apparently no problem
26
1513
1882
1721
590
917
1237
596
409
1170
10000 element array; apparent problem: mild repetition
2661
6633
8864
1157
2432
6681
6995
6633
8864
1157
20000 element array; apparent problem: repetition
2432
13677
15498
3590
13677
15498
3590
13677
15498
3590
30000 element array; apparent problem: repetition
13677
15498
3590
13677
15498
3590
13677
15498
3590
13677
50000 element array; apparent problem: repetition
19089
29176
3590
29176
3590
29176
3590
29176
3590
29176
100000 element array; 32767=2^15-1 repeating;
3590
32767
32767
32767
32767
32767
32767
32767
32767
32767
200000 element array; 32767=2^15-1 repeating;
32767
32767
32767
32767
32767
32767
32767
32767
32767
32767
300000 element array; 32767=2^15-1 repeating;
32767
32767
32767
32767
32767
32767
32767
32767
32767
32767
for me. I do not know the exact problem although the randomization seems progressively worse on
larger arrays.
------------------------------------------------------------------------
[2008-07-02 11:47:39] jani@php.net
See also bug #45302
------------------------------------------------------------------------
The remainder of the comments for this report are too long. To view
the rest of the comments, please view the bug report online at
https://bugs.php.net/bug.php?id=45301
--
Edit this bug report at https://bugs.php.net/bug.php?id=45301&edit=1