Sources Bugzilla – Bug 4403
strfry() gives skewed distributions
Last modified: 2012-05-06 18:56:55 UTC
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. Steinar H. Gunderson <sgunderson@bigfoot.com> proposed the following patch: --- string/strfry.c 2007-04-21 23:12:47.000000000 +0200 +++ string/strfry.c 2007-04-21 23:22:46.000000000 +0200 @@ -38,17 +38,17 @@ } len = strlen (string); - for (i = 0; i < len; ++i) + for (i = 0; i < len - 1; ++i) { int32_t j; char c; __random_r (&rdata, &j); - j %= len; + j %= (len - i); c = string[i]; - string[i] = string[j]; - string[j] = c; + string[i] = string[j + i]; + string[j + i] = c; } return string; It turns strfry() into a proper Fisher-Yates shuffle. This gives exactly n! paths for a string with N characters, and since there are n! possible permutations, this means a one-to-one mapping, and all possibilities are equally likely.
This function is a joke. Don't you have better things to do? It's not worth arguing about and so to safe me time I added a modifeed versson of the patch.
Your version is still not right, as now some strings could not appear anymore. For example for the string "abc" the strings "abc" and "acb" could never appear. The version already attached to this bug report returns all cases with a correct distribution.
Stop wasting people's time! Nobody cares about this crap. I made a last change but it's just too embarasing to even admit that.
(In reply to comment #3) > Stop wasting people's time! Nobody cares about this crap. I made a last change > but it's just too embarasing to even admit that. Refusing someone else's better free code without reason? You're a dick. You--
Please do not reopen bugs spuriously, thank you.
This bug is apparently still not fixed. See: http://www.eglibc.org/archives/patches/msg00646.html which provides a patch. Ulrich wrote, earlier in the thread: > This function is a joke. Don't you have better things to do? The problem is that the function is not marked as a joke, and only its name (and some elements of the description) is actually funny. The task that is does is something reasonable to want to do, and it seems reasonably simple to provide a good implementation, so why not? glibc is a high quality product, so let's make the jokes high quality too! If on the other hand the glibc maintainers do not consider this function to be worth maintaining to the high standards of glibc, then please either remove it, or remove its documentation, or mark it as "obsolete, do not use", which should stop people both from using it and from reporting bugs. Without any such action, it seems unreasonable to say that bug reports about this function are wasting the maintainers' time. memfrob is a much better example of how to make this type of joke: its much simpler algorithm is obviously correct, as it has no statistical complexities, and its man page explains that it's useless for encryption. Hence, no-one is going to complain that it's bad for encryption, and no-one is going to find implementation bugs. In a library as high-profile and important as glibc, bad jokes are going to come back and bite you just like other bad design decisions. If the maintainers don't understand this, the joke, if there is one here, is very much on them.
Just a small dwarf wishing you a happy April 1st!
Still a issue in current git.