Package: libc6 Version: 2.3.2.ds1-22 Severity: minor Tags: patch strfry() tries to shuffle its string using random swaps, but it uses the wrong strategy, and thus not all permutations are equally likely. The code doing the shuffling itself looks like this:
len = strlen (string); for (i = 0; i < len; ++i) { int32_t j; char c; __random_r (&rdata, &j); j %= len; c = string[i]; string[i] = string[j]; string[j] = c; } In other words, for the string 'abc' j will always be between 0 and 2 (inclusive), giving the following possibilities (all equally likely): j0 j1 j2 result 0 0 0 cab 0 0 1 bca 0 0 2 bac 0 1 0 cba 0 1 1 acb 0 1 2 abc 0 2 0 bca 0 2 1 abc 0 2 2 acb 1 0 0 cba 1 0 1 acb 1 0 2 abc 1 1 0 cab 1 1 1 bca 1 1 2 bac 1 2 0 acb 1 2 1 bac 1 2 2 bca 2 0 0 acb 2 0 1 bac 2 0 2 bca 2 1 0 abc 2 1 1 cab 2 1 2 cba 2 2 0 bac 2 2 1 cba 2 2 2 cab Sorting and counting gives us the following distribution: 4 abc 5 acb 5 bac 5 bca 4 cab 4 cba In other words, this is clearly skewed; some strings will appear 25% more often than others. I propose changing the code to: len = strlen (string); for (i = 0; i < len - 1; ++i) { int32_t j; char c; __random_r (&rdata, &j); j %= (len-i); c = string[i]; string[i] = string[j+i]; string[j+i] = c; } which will turn it into a proper Fisher-Yates shuffle. This gives us exactly n! paths for a string with N characters, and since there are n! possible permutations, we get a one-to-one mapping, and all possibilities are equally likely. I'm also a bit disappointed that strfry() is locale-unaware... surely such an important function should be able to shuffle at least UTF-8 strings correctly. -- System Information: Debian Release: 3.1 Architecture: i386 (x86_64) Kernel: Linux 2.6.12-rc4 Locale: LANG=en_DK.UTF-8, LC_CTYPE=en_DK.UTF-8 (charmap=UTF-8) Versions of packages libc6 depends on: ii libdb1-compat 2.1.3-7 The Berkeley database routines [gl -- no debconf information -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]