[Bug libc/4403] New: strfry() gives skewed distributions

[Bug libc/4403] New: strfry() gives skewed distributions

[aurelien at aurel32 dot net]

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.

-- 
           Summary: strfry() gives skewed distributions
           Product: glibc
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: libc
        AssignedTo: drepper at redhat dot com
        ReportedBy: aurelien at aurel32 dot net
                CC: glibc-bugs at sources dot redhat dot com
 GCC build triplet: x86_64-unknown-linux-gnu
  GCC host triplet: x86_64-unknown-linux-gnu
GCC target triplet: x86_64-unknown-linux-gnu


http://sourceware.org/bugzilla/show_bug.cgi?id=4403

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/4403] strfry() gives skewed distributions

[aurelien at aurel32 dot net]

------- Additional Comments From aurelien at aurel32 dot net  2007-05-20 21:48 -------
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.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|FIXED                       |


http://sourceware.org/bugzilla/show_bug.cgi?id=4403

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/4403] strfry() gives skewed distributions

[drepper at redhat dot com]

------- Additional Comments From drepper at redhat dot com  2007-08-22 07:29 -------
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.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|                            |FIXED


http://sourceware.org/bugzilla/show_bug.cgi?id=4403

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/4403] strfry() gives skewed distributions

[me at evancarroll dot com]

------- Additional Comments From me at evancarroll dot com  2009-05-09 17:00 -------
(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--

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|FIXED                       |


http://sourceware.org/bugzilla/show_bug.cgi?id=4403

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/4403] strfry() gives skewed distributions

[pasky at suse dot cz]

------- Additional Comments From pasky at suse dot cz  2009-05-10 08:03 -------
Please do not reopen bugs spuriously, thank you.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|                            |FIXED


http://sourceware.org/bugzilla/show_bug.cgi?id=4403

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/4403] strfry() gives skewed distributions

[rrt at sc3d dot org]

------- Additional Comments From rrt at sc3d dot org  2010-09-16 12:05 -------
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.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|FIXED                       |


http://sourceware.org/bugzilla/show_bug.cgi?id=4403

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.