Kollisionen beim Generieren von UUIDs in JavaScript?

94

Dies bezieht sich auf diese Frage . Ich verwende den folgenden Code aus dieser Antwort , um eine UUID in JavaScript zu generieren:

'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
    var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
    return v.toString(16);
});

Diese Lösung schien gut zu funktionieren, aber ich bekomme Kollisionen. Folgendes habe ich:

  • Eine Web-App, die in Google Chrome ausgeführt wird.
  • 16 Benutzer.
  • In den letzten 2 Monaten wurden von diesen Benutzern etwa 4000 UUIDs generiert.
  • Ich habe ungefähr 20 Kollisionen erhalten - z. B. war die heute generierte neue UUID dieselbe wie vor ungefähr 2 Monaten (anderer Benutzer).

Was verursacht dieses Problem und wie kann ich es vermeiden?

Muxa
quelle
2
Kombinieren Sie eine gute Zufallszahl mit der aktuellen Zeit (in Millisekunden). Die Wahrscheinlichkeit, dass die Zufallszahl genau zur gleichen Zeit kollidiert, ist sehr, sehr, sehr gering.
jfriend00
7
@ jfriend00 Wenn du das tun musst, dann ist es keine "gute Zufallszahl", nicht einmal eine anständige Pseudozufallszahl.
Attila O.
2
Was bedeutet der (r&0x3|0x8)Teil / Bewertung?
Kristian
Was ist mit dem Anhängen eines Date.now (). ToString ()?
Vitim.us
4
Es gibt ein großes Problem in Ihrer Architektur, das nicht mit UUIDs zusammenhängt. Der Client generiert möglicherweise absichtlich kollidierende IDs. Generieren Sie IDs nur von einem System, dem Sie vertrauen. Um dieses Problem zu umgehen, stellen Sie dem Client generierte IDs mit user_id voran, sodass der gegnerische / fehlerhafte Client nur mit sich selbst kollidieren kann (und dies auf der Serverseite handhaben kann).
Dzmitry Lazerka

Antworten:

35

Meine beste Vermutung ist, dass Math.random()Ihr System aus irgendeinem Grund kaputt ist (so bizarr das klingt). Dies ist der erste Bericht, den ich über Kollisionen von Personen gesehen habe.

node-uuidverfügt über ein Testkabel , mit dem Sie die Verteilung von Hex-Ziffern in diesem Code testen können. Wenn das in Ordnung aussieht, ist dies nicht der Fall. Math.random()Versuchen Sie also, die von Ihnen verwendete UUID-Implementierung durch die dortige uuid()Methode zu ersetzen, und prüfen Sie, ob Sie immer noch gute Ergebnisse erzielen.

[Update: Ich habe gerade Veselins Bericht über den Fehler Math.random()beim Start gesehen. Da das Problem erst beim Start auftritt, node-uuidist es unwahrscheinlich, dass der Test nützlich ist. Ich werde den Link devoluk.com genauer kommentieren.]

Broofa
quelle
1
Danke, ich gehe jetzt mit uuid.js, da es die starke Krypto des Browsers verwendet, falls verfügbar. Wird sehen, ob es Kollisionen gibt.
Muxa
Können Sie einen Link zu dem Code uuid.js bereitstellen, auf den Sie sich beziehen? (Entschuldigung, nicht sicher, welche Bibliothek du meinst.)
Broofa
10
Hatte bisher keine Kollisionen :)
Muxa
Wie auch immer, wenn es Chrome ist und nur beim Start, könnte Ihre App eine Reihe von beispielsweise zehn Guids mit der oben genannten Funktion generieren und verwerfen :)
Vinko Vrsalovic
Das Problem ist die begrenzte Entropie, die Sie von Math.random () erhalten. Bei einigen Browsern beträgt die Entropie insgesamt nur 41 Bit. Durch mehrmaliges Aufrufen von Math.random () wird die Entropie nicht erhöht. Wenn Sie wirklich eindeutige v4-UUIDs wünschen, müssen Sie ein kryptografisch starkes RNG verwenden, das pro generierter UUID mindestens 122-Bit-Entropie erzeugt.
Mlehmk
36

In der Tat gibt es Kollisionen, aber nur unter Google Chrome. Schauen Sie sich hier meine Erfahrungen zu diesem Thema an

http://devoluk.com/google-chrome-math-random-issue.html

(Link ab 2019 defekt. Archivlink: https://web.archive.org/web/20190121220947/http://devoluk.com/google-chrome-math-random-issue.html .)

Es scheint, als würden Kollisionen nur bei den ersten Aufrufen von Math.random auftreten. Denn wenn Sie nur die oben beschriebene Methode createGUID / testGUIDs ausführen (was offensichtlich das erste war, was ich versucht habe), funktioniert sie einfach ohne jegliche Kollisionen.

Um einen vollständigen Test durchzuführen, muss Google Chrome neu gestartet, 32 Byte generiert, Chrome neu gestartet, generiert, neu gestartet, generiert werden ...

Veselin Kulov
quelle
2
Das ist ziemlich besorgniserregend - hat jemand einen Fehlerbericht erstellt?
UpTheCreek
1
Besonders wie der Link zu besseren Zufallszahlengeneratoren in Javascript: baagoe.com/de/RandomMusings/javascript
Leopd
Leider ist der Link jetzt defekt :(
Gus
7
Kann jemand bestätigen, ob dieser Fehler behoben wurde?
Xdrone
20

Nur damit andere sich dessen bewusst werden können - ich bin mit der hier erwähnten UUID-Generierungstechnik auf eine überraschend große Anzahl offensichtlicher Kollisionen gestoßen. Diese Kollisionen setzten sich fort, selbst nachdem ich für meinen Zufallszahlengenerator auf Seedrandom umgestellt hatte . Das hat mich dazu gebracht, mir die Haare auszureißen, wie Sie sich vorstellen können.

Ich fand schließlich heraus, dass das Problem (fast?) Ausschließlich mit den Webcrawler-Bots von Google zusammenhängt. Sobald ich anfing, Anfragen mit "googlebot" im Feld "User-Agent" zu ignorieren, verschwanden die Kollisionen. Ich vermute, dass sie die Ergebnisse von JS-Skripten auf halbintelligente Weise zwischenspeichern müssen, mit dem Endergebnis, dass man sich nicht darauf verlassen kann, dass sich ihr Spidering-Browser so verhält, wie es normale Browser tun.

Nur zu Ihrer Information.

Ken Smith
quelle
2
Ist bei unserem Metriksystem auf dasselbe Problem gestoßen. Es wurden Tausende von UUID-Kollisionen mit dem Modul 'node-uuid' festgestellt, um Sitzungs-IDs im Browser zu generieren. Es stellte sich heraus, dass es die ganze Zeit über Googlebot war. Vielen Dank!
Domkck
4

Ich wollte dies als Kommentar zu Ihrer Frage posten, aber anscheinend lässt mich StackOverflow nicht.

Ich habe gerade einen rudimentären Test mit 100.000 Iterationen in Chrome mit dem von Ihnen veröffentlichten UUID-Algorithmus durchgeführt und keine Kollisionen festgestellt. Hier ist ein Code-Snippet:

var createGUID = function() {
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
        var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
        return v.toString(16);
    });
}

var testGUIDs = function(upperlimit) {
    alert('Doing collision test on ' + upperlimit + ' GUID creations.');
    var i=0, guids=[];
    while (i++<upperlimit) {
        var guid=createGUID();
        if (guids.indexOf(guid)!=-1) {
            alert('Collision with ' + guid + ' after ' + i + ' iterations');
        }
        guids.push(guid);
    }
    alert(guids.length + ' iterations completed.');
}

testGUIDs(100000);

Sind Sie sicher, dass hier nichts anderes los ist?

user533676
quelle
4
Ja, ich habe auch einige lokale Tests durchgeführt und keine Kollisionen erhalten. Kollisionen treten zwischen UUIDs auf, die auf den Computern verschiedener Benutzer generiert werden. Möglicherweise muss ich einige Daten auf verschiedenen Computern generieren und nach Kollisionen suchen.
Muxa
2
Außerdem habe ich festgestellt, dass Kollisionen zwischen UUIDs im Abstand von 3-4 Wochen auftreten.
Muxa
Sehr komisch. Auf welcher Plattform laufen Sie?
user533676
1
Es ist unwahrscheinlich, dass Math.random () in V8 einen so grundlegenden Fehler aufweist, aber Chromium 11 bietet Unterstützung für die Erzeugung starker Zufallszahlen mithilfe der window.crypto.getRandomValues-API, wenn Sie es stattdessen versuchen möchten. Siehe blog.chromium.org/2011/06/… .
user533676
Läuft unter einer Kombination von Windows 7 und Windows XP.
Muxa
3

Die Antwort , die diese UUID-Lösung ursprünglich veröffentlicht hat, wurde am 28.06.2017 aktualisiert:

Ein guter Artikel von Chrome-Entwicklern zum Status von Math.random PRNG in Chrome, Firefox und Safari. tl; dr - Ab Ende 2015 ist es "ziemlich gut", aber keine kryptografische Qualität. Um dieses Problem zu beheben, finden Sie hier eine aktualisierte Version der oben genannten Lösung, die ES6 verwendetcrypto beheben API und ein wenig JS-Assistenten verwendet, für die ich keine Anerkennung finden kann :

function uuidv4() {
  return ([1e7]+-1e3+-4e3+-8e3+-1e11).replace(/[018]/g, c =>
    (c ^ crypto.getRandomValues(new Uint8Array(1))[0] & 15 >> c / 4).toString(16)
  )
}

console.log(uuidv4());

Luke
quelle
0

Die Antworten hier beziehen sich auf "Was verursacht das Problem?" (Chrome Math.random Seed-Problem), aber nicht "Wie kann ich das vermeiden?".

Wenn Sie immer noch nach Möglichkeiten suchen, dieses Problem zu vermeiden, habe ich diese Antwort vor einiger Zeit als modifizierte Version von Broofas Funktion geschrieben, um genau dieses Problem zu umgehen. Es funktioniert, indem die ersten 13 Hex-Zahlen um einen Hex-Teil des Zeitstempels versetzt werden. Dies bedeutet, dass selbst wenn sich Math.random auf demselben Startwert befindet, eine andere UUID generiert wird, sofern sie nicht genau in derselben Millisekunde generiert wird.

Briguy37
quelle