{"id":766,"date":"2010-02-27T22:00:24","date_gmt":"2010-02-28T02:00:24","guid":{"rendered":"http:\/\/2d823b65bb.nxcli.io\/?p=766"},"modified":"2018-11-17T11:20:53","modified_gmt":"2018-11-17T16:20:53","slug":"microsoft-random-browser-ballot","status":"publish","type":"post","link":"https:\/\/www.robweir.com\/blog\/2010\/02\/microsoft-random-browser-ballot.html","title":{"rendered":"Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot"},"content":{"rendered":"

March 6th Update:\u00a0 Microsoft appears to have updated the www.browserchoice.eu<\/a> website and corrected the error I describe in this post.\u00a0 More details on the fix can be found in The New & Improved Microsoft Shuffle<\/a>.\u00a0 However, I think you will still find the following analysis interesting.<\/p>\n

-Rob<\/p>\n

\n

Introduction<\/h3>\n

The story first hit in last week on the Slovakian tech site DSL.sk<\/a>.\u00a0 Since I am not linguistically equipped to follow the Slovakian tech scene, I didn’t hear about the story until it was brought up in English on TechCrunch<\/a>.\u00a0 The gist of these reports is this: DSL.sk did a test of the “ballot” screen at www.browserchoice.eu<\/a>, used in Microsoft Windows 7 to prompt the user to install a browser.\u00a0 It was a Microsoft concession to the EU, to provide a randomized ballot screen for users to select a browser.\u00a0 However, the DSL.sk test suggested that the ordering of the browsers was far from random.<\/p>\n

But this wasn’t a simple case of Internet Explorer showing up more in the first position.\u00a0 The non-randomness was pronounced, but more complicated.\u00a0 For example, Chrome was more likely to show up in one of the first 3 positions.\u00a0 And Internet Explorer showed up 50% of the time in the last position.\u00a0 This isn’t just a minor case of it being slightly random.\u00a0 Try this test yourself: Load www.browserchoice.eu<\/a>, in Internet Explorer, and press refresh 20 times.\u00a0 Count how many times the Internet Explorer choice is on the far right.\u00a0\u00a0 Can this be right?<\/p>\n

The DLS.sk findings have lead to various theories, made on the likely mistaken theory that this is an intentional non-randomness.\u00a0 Does Microsoft have secret research showing that the 5th position is actually chosen more often?\u00a0 Is the Internet Explorer random number generator not random?\u00a0 There were also comments asserting that the tests proved nothing, and the results were just chance, and others saying that the results are expected to be non-random because computers can only make pseudo-random numbers, not genuinely random numbers.<\/p>\n

Maybe there was cogent technical analysis of this issue posted someplace, but if there was, I could not find it.\u00a0 So I’m providing my own analysis here, a little statistics and a little algorithms 101.\u00a0 I’ll tell you what went wrong, and how Microsoft can fix it.\u00a0 In the end it is a rookie mistake in the code, but it is an interesting mistake that we can learn from, so I’ll examine it in some depth.<\/p>\n

Are the results random?<\/h3>\n

The ordering of the browser choices is determined by JavaScript code<\/a> on the BrowserChoice.eu web site.\u00a0 You can see the core function in the GenerateBrowserOrder function.\u00a0 I took that function and supporting functions,\u00a0 put it into my own HTML file, added some test driver code and ran it for 10,000 iterations on Internet Explorer.\u00a0 The results are as follows:<\/p>\n\n\n\n\n\n\n\n\n
Internet Explorer raw counts<\/caption>\n
Position<\/th>\nI.E.<\/th>\nFirefox<\/th>\nOpera<\/th>\nChrome<\/th>\nSafari<\/th>\n<\/tr>\n
1<\/td>\n1304<\/td>\n2099<\/td>\n2132<\/td>\n2595<\/td>\n1870<\/td>\n<\/tr>\n
2<\/td>\n1325<\/td>\n2161<\/td>\n2036<\/td>\n2565<\/td>\n1913<\/td>\n<\/tr>\n
3<\/td>\n1105<\/td>\n2244<\/td>\n1374<\/td>\n3679<\/td>\n1598<\/td>\n<\/tr>\n
4<\/td>\n1232<\/td>\n2248<\/td>\n1916<\/td>\n590<\/td>\n4014<\/td>\n<\/tr>\n
5<\/td>\n5034<\/td>\n1248<\/td>\n2542<\/td>\n571<\/td>\n605<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n\n\n\n\n
Internet Explorer fraction of total<\/caption>\n
Position<\/th>\nI.E.<\/th>\nFirefox<\/th>\nOpera<\/th>\nChrome<\/th>\nSafari<\/th>\n<\/tr>\n
1<\/td>\n0.1304<\/td>\n0.2099<\/td>\n0.2132<\/td>\n0.2595<\/td>\n0.1870<\/td>\n<\/tr>\n
2<\/td>\n0.1325<\/td>\n0.2161<\/td>\n0.2036<\/td>\n0.2565<\/td>\n0.1913<\/td>\n<\/tr>\n
3<\/td>\n0.1105<\/td>\n0.2244<\/td>\n0.1374<\/td>\n0.3679<\/td>\n0.1598<\/td>\n<\/tr>\n
4<\/td>\n0.1232<\/td>\n0.2248<\/td>\n0.1916<\/td>\n0.0590<\/td>\n0.4014<\/td>\n<\/tr>\n
5<\/td>\n0.5034<\/td>\n0.1248<\/td>\n0.2542<\/td>\n0.0571<\/td>\n0.0605<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

This confirms the DSL.sk results.\u00a0 Chrome appears more often in one of the first 3 positions and I.E. is most likely to be in the 5th position.<\/p>\n

You can also see this graphically in a 3D bar chart:<\/p>\n

\"\"<\/p>\n

But is this a statistically significant result?\u00a0 I think most\u00a0 of us have an intuitive feeling that results are more significant if many tests are run, and if the results also vary much from an even distribution of positions.\u00a0 On the other hand, we also know that a finite run of even a perfectly random algorithm will not give a perfectly uniform distribution.\u00a0 It would be quite unusual if every cell in the above table was exactly 2,000.<\/p>\n

This is not a question one answers with debate.\u00a0 To go beyond intuition you need to perform a statistical test.\u00a0 In this case, a good test is Pearson’s Chi-square test, which tests how well observed results match a specified distribution.\u00a0 In this test we assume the null-hypothesis that the observed data is taken from a uniform distribution.\u00a0 The test then tells us the probability that the observed results can be explained by chance.\u00a0 In other words, what is the probability that the difference between observation and a uniform distribution was just the luck of the draw?\u00a0 If that probability is very small, say less than 1%, then we can say with high confidence, say 99% confidence, that the positions are not uniformly distributed. \u00a0 However, if the test returns a larger number, then we cannot disprove our null-hypothesis.\u00a0 That doesn’t mean the null-hypothesis is true.\u00a0 It just means we can’t disprove it.\u00a0 In the end we can never prove the null hypothesis.\u00a0 We can only try to disprove it.<\/p>\n

Note also that having a uniform distribution is not the same as having uniformly distributed random positions.\u00a0 There are ways of getting a uniform distribution that are not random, for example, by treating the order as a circular buffer and rotating through the list on each invocation.\u00a0 Whether or not randomization is needed is ultimately dictated by the architectural assumptions of your application.\u00a0 If you determine the order on a central server and then serve out that order on each innovation, then you can use non-random solutions, like the rotating circular buffer.\u00a0 But if the ordering is determined independently on each client, for each invocation, then you need some source of randomness on each client to achieve a uniform distribution overall.\u00a0 But regardless of how you attempt to achieve a uniform distribution the way to test it is the same, using the Chi-square test.<\/p>\n

Using the open source statistical package R<\/a>, I ran the\u00a0 chisq.test() routine on the above data.\u00a0 The results are:<\/p>\n

X-squared = 13340.23, df = 16, p-value < 2.2e-16<\/pre>\n
The p-value is much, much less than 1%.\u00a0 So, we can say with high confidence that the results are not random.<\/p>\n
Repeating the same test on Firefox is also non-random, but in a different way:<\/p>\n\n\n\n\n\n\n\n\n
Firefox raw counts<\/caption>\n
Position<\/th>\nI.E.<\/th>\nFirefox<\/th>\nOpera<\/th>\nChrome<\/th>\nSafari<\/th>\n<\/tr>\n
1<\/td>\n2494<\/td>\n2489<\/td>\n1612<\/td>\n947<\/td>\n2458<\/td>\n<\/tr>\n
2<\/td>\n2892<\/td>\n2820<\/td>\n1909<\/td>\n1111<\/td>\n1268<\/td>\n<\/tr>\n
3<\/td>\n2398<\/td>\n2435<\/td>\n2643<\/td>\n1891<\/td>\n633<\/td>\n<\/tr>\n
4<\/td>\n1628<\/td>\n1638<\/td>\n2632<\/td>\n3779<\/td>\n323<\/td>\n<\/tr>\n
5<\/td>\n588<\/td>\n618<\/td>\n1204<\/td>\n2272<\/td>\n5318<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n\n\n\n\n
Firefox fraction of total<\/caption>\n
Position<\/th>\nI.E.<\/th>\nFirefox<\/th>\nOpera<\/th>\nChrome<\/th>\nSafari<\/th>\n<\/tr>\n
1<\/td>\n0.2494<\/td>\n0.2489<\/td>\n0.1612<\/td>\n0.0947<\/td>\n0.2458<\/td>\n<\/tr>\n
2<\/td>\n0.2892<\/td>\n0.2820<\/td>\n0.1909<\/td>\n0.1111<\/td>\n0.1268<\/td>\n<\/tr>\n
3<\/td>\n0.2398<\/td>\n0.2435<\/td>\n0.2643<\/td>\n0.1891<\/td>\n0.0633<\/td>\n<\/tr>\n
4<\/td>\n0.1628<\/td>\n0.1638<\/td>\n0.2632<\/td>\n0.3779<\/td>\n0.0323<\/td>\n<\/tr>\n
5<\/td>\n0.0588<\/td>\n0.0618<\/td>\n0.1204<\/td>\n0.2272<\/td>\n0.5318<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
On Firefox, Internet Explorer is more frequently in one of the first 3 positions, while Safari is most often in last position.\u00a0 Strange.\u00a0 The same code, but vastly different results.<\/p>\n
The results here are also highly significant:<\/p>\n
X-squared = 14831.41, df = 16, p-value < 2.2e-16<\/pre>\n
So given the above, we know two things:\u00a0 1) The problem is real.\u00a0 2) The problem is not related to a flaw only in Internet Explorer.<\/p>\n
In the next section we look at the algorithm and show what the real problem is, and how to fix it.<\/p>\n
Random shuffles<\/h3>\n
The browser choice screen requires what we call a “random shuffle”.\u00a0 You start with an array of values and return those same values, but in a randomized order. This computational problem has been known since the earliest days of computing.\u00a0 There are 4 well-known approaches: 2 good solutions, 1 acceptable (“good enough”) solution that is slower than necessary, and 1 bad approach that doesn’t really work.\u00a0 Microsoft appears to have picked the bad approach. But I do not believe there is some nefarious intent to this bug.\u00a0 It is more in the nature of a “naive” algorithm”, like the bubble sort, that inexperienced programmers\u00a0 inevitably will fall upon when solving a given problem.\u00a0 I bet if we gave this same problem to 100 freshmen computer science majors, at least one of them would make the same mistake.\u00a0 But with education and experience, one learns about these things.\u00a0 And one of the things one learns early on is to reach for Knuth<\/a>.<\/p>\n