Коллизии при генерации UUID в JavaScript?

94

Это относится к этому вопросу . Я использую приведенный ниже код из этого ответа для создания UUID в JavaScript:

'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);
});

Это решение работает нормально, но возникают коллизии. Вот что у меня есть:

  • Веб-приложение, работающее в Google Chrome.
  • 16 пользователей.
  • около 4000 UUID были сгенерированы этими пользователями за последние 2 месяца.
  • У меня было около 20 коллизий - например, новый UUID, сгенерированный сегодня, был таким же, как около 2 месяцев назад (другой пользователь).

Что вызывает эту проблему и как ее избежать?

Muxa
источник
2
Совместите хорошее случайное число с текущим временем (в миллисекундах). Шансы на то, что случайное число столкнется в одно и то же время, действительно, очень, очень низка.
jfriend00 02
7
@ jfriend00, если вам нужно это сделать, то это не «хорошее случайное число», даже не приличное псевдослучайное число.
Аттила О.
2
что означает (r&0x3|0x8)часть / оценка?
Кристиан
А как насчет добавления к нему Date.now (). ToString ()?
Vitim.us
4
В вашей архитектуре есть большая проблема, не связанная с UUID - клиент может намеренно генерировать конфликтующие идентификаторы. Создавайте идентификаторы только той системой, которой вы доверяете. Однако в качестве обходного пути добавьте идентификаторы, сгенерированные клиентом, с user_id, чтобы злоумышленник / неисправный клиент мог столкнуться только с самим собой (и обработать это на стороне сервера).
Дмитрий Лазерка

Ответы:

35

Я предполагаю, что Math.random()по какой-то причине ваша система сломалась (как бы странно это ни звучало). Это первый отчет о столкновениях, который я видел.

node-uuidимеет тестовую программу, которую вы можете использовать для проверки распределения шестнадцатеричных цифр в этом коде. Если все в порядке, значит, это не Math.random()так, поэтому попробуйте заменить используемую вами реализацию UUID в uuid()метод и посмотреть, получите ли вы по-прежнему хорошие результаты.

[Обновление: только что видел отчет Веселина об ошибке Math.random()при запуске. Поскольку проблема только при запуске, node-uuidтест вряд ли пригодится. Я прокомментирую более подробно ссылку на devoluk.com.]

брофа
источник
1
Спасибо, сейчас я использую uuid.js, так как он использует надежную криптовалюту браузера, если она доступна. Посмотрим, есть ли коллизии.
Muxa
вы можете предоставить ссылку на код uuid.js, о котором вы говорите? (извините, я не уверен, какую библиотеку вы имеете в виду.)
broofa
10
Пока столкновений не было :)
Muxa
В любом случае, если это Chrome и только при запуске, ваше приложение может сгенерировать и отбросить строку, скажем, из десяти руководств, используя указанную выше функцию :)
Винко Врсалович
Проблема заключается в ограниченной энтропии, которую вы получаете от Math.random (). Для некоторых браузеров энтропия всего 41 бит вместе. Многократный вызов Math.random () не приведет к увеличению энтропии. Если вам действительно нужны уникальные UUID v4, вам необходимо использовать криптографически стойкий RNG, который производит не менее 122 бит энтропии на сгенерированный UUID.
mlehmk
36

Коллизии действительно есть, но только под Google Chrome. Ознакомьтесь с моим опытом по этой теме здесь

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

(Ссылка не работает с 2019 года. Ссылка на архив: https://web.archive.org/web/20190121220947/http://devoluk.com/google-chrome-math-random-issue.html .)

Похоже, что коллизии происходят только при первых вызовах Math.random. Потому что, если вы просто запустите описанный выше метод createGUID / testGUIDs (который, очевидно, был первым, что я попробовал), он просто работает без каких-либо столкновений.

Итак, чтобы провести полный тест, необходимо перезапустить Google Chrome, сгенерировать 32 байта, перезапустить Chrome, сгенерировать, перезапустить, сгенерировать ...

Веселин Кулов
источник
2
Это довольно тревожно - кто-нибудь сообщал об ошибке?
UpTheCreek
1
Особенно нравится ссылка на лучшие генераторы случайных чисел в javascript: baagoe.com/en/RandomMusings/javascript
Leopd
к сожалению, указанная ссылка теперь не работает :(
Gus
2
web.archive.org/web/20120503063359/http://baagoe.com/en/…
Бени Чернявский-Паскин
7
Может ли кто-нибудь подтвердить, устранена ли эта ошибка?
Xdrone
21

Просто чтобы другие знали об этом - я столкнулся с удивительно большим количеством очевидных коллизий, используя упомянутую здесь технику генерации UUID. Эти столкновения продолжались даже после того, как я переключился на seedrandom для своего генератора случайных чисел. Это заставило меня вырвать себе волосы, как вы понимаете.

В конце концов я понял, что проблема была (почти?) Связана исключительно с роботами-роботами Google. Как только я стал игнорировать запросы с "googlebot" в поле user-agent, коллизии исчезли. Я предполагаю, что они должны кэшировать результаты JS-скриптов каким-то полуинтеллектуальным способом, в результате чего нельзя рассчитывать на то, что их браузеры-пауки будут вести себя так, как обычные браузеры.

Просто к вашему сведению.

Кен Смит
источник
2
Возникла та же проблема с нашей системой показателей. Наблюдал тысячи конфликтов UUID с использованием модуля node-uuid для генерации идентификаторов сеансов в браузере. Оказывается, все это время это был робот Google. Благодарность!
domkck
4

Я хотел опубликовать это как комментарий к вашему вопросу, но, видимо, StackOverflow мне не позволит.

Я только что провел рудиментарный тест из 100000 итераций в Chrome, используя опубликованный вами алгоритм UUID, и не получил никаких коллизий. Вот фрагмент кода:

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);

Вы уверены, что здесь больше ничего не происходит?

user533676
источник
4
Да, я провел несколько локальных тестов и не обнаружил коллизий. Коллизии происходят между UUID, которые сгенерированы на компьютерах разных пользователей. Мне может потребоваться сгенерировать некоторые данные на разных машинах и проверить наличие столкновений.
Muxa 02
2
Кроме того, я заметил, что конфликты возникают между UUID, сгенерированными с интервалом в 3-4 недели.
Muxa 03
Очень странный. На какой платформе вы работаете?
user533676 03
1
Кажется маловероятным, что в V8 Math.random () есть такая простая ошибка, но Chromium 11 добавил поддержку сильной генерации случайных чисел с помощью API window.crypto.getRandomValues, если вы хотите попробовать его вместо этого. См. Blog.chromium.org/2011/06/… .
user533676 03
Работает в сочетании с Windows 7 и Windows XP.
Muxa 03
3

Ответ, который изначально опубликовал это решение UUID, был обновлен 28.06.2017:

Хорошая статья от разработчиков Chrome обсуждают состояние качества Math.random ПСЧ в Chrome, Firefox и Safari. tl; dr - По состоянию на конец 2015 года он «неплохой», но не по криптографическому качеству. Чтобы решить эту проблему, вот обновленная версия вышеупомянутого решения, которая использует ES6, cryptoAPI и немного JS-мастера, за которые я не могу поверить :

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());

Люк
источник
0

Ответы здесь касаются того, "что вызывает проблему?" (Проблема с семенами Chrome Math.random), но не «как я могу этого избежать?».

Если вы все еще ищете, как избежать этой проблемы, я написал этот ответ некоторое время назад как модифицированный подход к функции Бруфа, чтобы обойти эту точную проблему. Он работает, смещая первые 13 шестнадцатеричных чисел шестнадцатеричной частью метки времени, что означает, что даже если Math.random находится на одном и том же семени, он все равно будет генерировать другой UUID, если он не сгенерирован точно в ту же миллисекунду.

Бригуй37
источник