[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.

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

[coleharrisjohnson at gmail dot com]

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

Cole Johnson <coleharrisjohnson at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |coleharrisjohnson at gmail dot com

-- 
You are receiving this mail because:
You are on the CC list for the bug.

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

[fweimer at redhat dot com]

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

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
              Flags|                            |security-

-- 
You are receiving this mail because:
You are on the CC list for the bug.

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

[allachan at au1 dot ibm.com]

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

paxdiablo <allachan at au1 dot ibm.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |allachan at au1 dot ibm.com

--- Comment #10 from paxdiablo <allachan at au1 dot ibm.com> ---
Well, nothing in the doco
(http://www.gnu.org/software/libc/manual/html_node/strfry.html) for strfry()
stated that all combinations would be equally likely. The only mention of
uniform distribution was that it was used to do the swaps themselves, not that
the results would be uniformly distributed.

In any case, when I make stir fry, it's rarely distributed perfectly. Having
said that, Ulrich probably spent more time complaining about the patch than it
would have taken to just put the damn thing in :-)

I have to go with Reuben here. If it's a joke, get rid of it, it has no place
in a serious piece of software. If not, we should be willing to accept patches
that make it better in some way, given any constraints from elsewhere (such as
time needed by maintainers to do it).

-- 
You are receiving this mail because:
You are on the CC list for the bug.

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

[schwab at sourceware dot org]

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

Andreas Schwab <schwab at sourceware dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|jackie.rosen at hushmail dot com   |

-- 
You are receiving this mail because:
You are on the CC list for the bug.

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

[jackie.rosen at hushmail dot com]

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

Jackie Rosen <jackie.rosen at hushmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jackie.rosen at hushmail dot com

--- Comment #9 from Jackie Rosen <jackie.rosen at hushmail dot com> ---
*** Bug 260998 has been marked as a duplicate of this bug. ***
Seen from the domain http://volichat.com
Page where seen: http://volichat.com/adult-chat-rooms
Marked for reference. Resolved as fixed @bugzilla.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

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

[aj at suse dot de]

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

Andreas Jaeger <aj at suse dot de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2012-05-06
         AssignedTo|drepper.fsp at gmail dot    |unassigned at sourceware
                   |com                         |dot org

--- Comment #8 from Andreas Jaeger <aj at suse dot de> 2012-05-06 18:56:55 UTC ---
Still a issue in current git.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

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

[kirill at shutemov dot name]

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

Kirill A. Shutemov <kirill at shutemov dot name> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |kirill at shutemov dot name

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

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

[awreece at gmail dot com]

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

awreece at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |awreece at gmail dot com

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.