4403 2007-04-21 22:36:00 +0000 strfry() gives skewed distributions 2012-05-06 18:56:55 +0000 1 1 1 Unclassified glibc libc unspecified All All REOPENED P2 normal --- 1 aurelien unassigned awreece glibc-bugs kirill slashtrooll x86_64-unknown-linux-gnu x86_64-unknown-linux-gnu x86_64-unknown-linux-gnu 2012-05-06 00:00:00 oldest_to_newest 16519 0 aurelien 2007-04-21 22:36:13 +0000 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. 16823 1 drepper.fsp 2007-05-08 04:28:42 +0000 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. 17084 2 aurelien 2007-05-20 21:48:50 +0000 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. 18729 3 drepper.fsp 2007-08-22 07:29:53 +0000 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. 36094 4 me 2009-05-09 17:00:37 +0000 (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-- 36100 5 pasky 2009-05-10 08:03:52 +0000 Please do not reopen bugs spuriously, thank you. 45120 6 rrt 2010-09-16 12:05:23 +0000 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. 54321 7 slashtrooll 2012-03-31 21:05:54 +0000 Just a small dwarf wishing you a happy April 1st! 55020 8 aj 2012-05-06 18:56:55 +0000 Still a issue in current git.