Colisões ao gerar UUIDs em JavaScript?

94

Isso se relaciona com esta questão . Estou usando o código abaixo de desta resposta para gerar UUID em 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);
});

Esta solução parecia estar funcionando bem, mas estou recebendo colisões. Aqui está o que eu tenho:

  • Um aplicativo da web em execução no Google Chrome.
  • 16 usuários.
  • cerca de 4.000 UUIDs foram gerados nos últimos 2 meses por esses usuários.
  • Tive cerca de 20 colisões - por exemplo, o novo UUID gerado hoje era o mesmo de cerca de 2 meses atrás (usuário diferente).

O que está causando esse problema e como posso evitá-lo?

Muxa
fonte
2
Combine um bom número aleatório com a hora atual (em milissegundos). As chances de um número aleatório colidir exatamente ao mesmo tempo são muito, muito, muito baixas.
jfriend00
7
@ jfriend00 se você precisar fazer isso, então não é um "bom número aleatório", nem mesmo um número pseudo-aleatório decente.
Attila O.
2
o que significa a (r&0x3|0x8)porção / avaliação?
Kristian de
Que tal acrescentar um Date.now (). ToString () a ele?
Vitim.us
4
Há um grande problema em sua arquitetura, não relacionado aos UUIDs - o cliente pode gerar intencionalmente IDs em colisão. Gere IDs apenas por um sistema em que você confia. Como uma solução alternativa, porém, acrescente IDs gerados pelo cliente com user_id, para que o cliente adversário / defeituoso possa apenas colidir consigo mesmo (e lidar com isso no lado do servidor).
Dzmitry Lazerka de

Respostas:

35

Meu melhor palpite é que Math.random() seu sistema está quebrado por algum motivo (por mais bizarro que isso pareça). Este é o primeiro relatório que vejo de alguém sofrendo colisões.

node-uuidtem um equipamento de teste que você pode usar para testar a distribuição de dígitos hexadecimais nesse código. Se isso parecer certo, então não está Math.random(), então tente substituir a implementação UUID que você está usando no uuid()método lá e veja se você ainda obtém bons resultados.

[Atualização: acabei de ver o relatório do Veselin sobre o bug com Math.random()na inicialização. Como o problema está apenas na inicialização, o node-uuidteste provavelmente não será útil. Vou comentar com mais detalhes no link devoluk.com.]

broofa
fonte
1
Obrigado, vou usar o uuid.js agora, pois ele usa a criptografia forte do navegador, se disponível. Vou ver se há alguma colisão.
Muxa
você pode fornecer um link para o código uuid.js ao qual está se referindo? (desculpe, não tenho certeza de qual lib você quer dizer.)
Broofa
10
Não teve colisões até agora :)
Muxa
De qualquer forma, se for o Chrome e apenas ao iniciar, seu aplicativo pode gerar e descartar uma linha de, digamos, dez guids usando a função acima :)
Vinko Vrsalovic
O problema é com a entropia limitada obtida em Math.random (). Para alguns navegadores, a entropia é tão baixa quanto 41 bits juntos. Chamar Math.random () várias vezes não aumentará a entropia. Se você realmente deseja UUIDs v4 exclusivos, você precisa usar um RNG criptograficamente forte que produza pelo menos uma entropia de 122 bits por UUID gerado.
mlehmk
36

Na verdade, existem colisões, mas apenas no Google Chrome. Confira minha experiência no assunto aqui

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

(Link quebrado em 2019. Link do arquivo: https://web.archive.org/web/20190121220947/http://devoluk.com/google-chrome-math-random-issue.html .)

Parece que as colisões acontecem apenas nas primeiras chamadas de Math.random. Porque se você apenas executar o método createGUID / testGUIDs acima (que obviamente foi a primeira coisa que tentei), ele funciona sem qualquer tipo de colisão.

Então, para fazer um teste completo, é necessário reiniciar o Google Chrome, gerar 32 bytes, reiniciar o Chrome, gerar, reiniciar, gerar ...

Veselin Kulov
fonte
2
Isso é muito preocupante - alguém levantou um relatório de bug?
UpTheCreek de
1
Especialmente como o link para melhores geradores de números aleatórios em javascript: baagoe.com/en/RandomMusings/javascript
Leopd
infelizmente, o referido link está quebrado :(
Gus
7
Alguém pode confirmar se este bug foi corrigido?
Xdrone
20

Só para que outras pessoas possam saber disso - eu estava enfrentando um número surpreendentemente grande de colisões aparentes usando a técnica de geração de UUID mencionada aqui. Essas colisões continuaram mesmo depois que eu mudei para seedrandom para meu gerador de números aleatórios. Isso me fez arrancar os cabelos, como você pode imaginar.

Acabei descobrindo que o problema estava (quase?) Exclusivamente associado aos bots rastreadores da web do Google. Assim que comecei a ignorar as solicitações com "googlebot" no campo do agente do usuário, as colisões desapareceram. Estou supondo que eles devem armazenar em cache os resultados dos scripts JS de alguma forma semi-inteligente, com o resultado final de que seu navegador spidering não pode ser considerado para se comportar da maneira que os navegadores normais fazem.

Apenas um FYI.

Ken Smith
fonte
2
Tive o mesmo problema com nosso sistema de métricas. Estava vendo milhares de colisões de UUID usando o módulo 'node-uuid' para gerar IDs de sessão no navegador. Acontece que era o googlebot o tempo todo. Obrigado!
domkck
4

Eu queria postar isso como um comentário à sua pergunta, mas aparentemente o StackOverflow não permite.

Acabei de executar um teste rudimentar de 100.000 iterações no Chrome usando o algoritmo UUID que você postou e não tive colisões. Aqui está um snippet de código:

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

Tem certeza de que não há mais nada acontecendo aqui?

user533676
fonte
4
Sim, também fiz alguns testes locais e não tive colisões. As colisões acontecem entre UUIDs que são gerados nas máquinas de diferentes usuários. Posso precisar gerar alguns dados em máquinas diferentes e verificar se há colisões.
Muxa
2
Além disso, notei que as colisões são entre UUIDs gerados com intervalos de 3-4 semanas.
Muxa
Muito estranho. Em qual plataforma você está rodando?
user533676
1
Parece improvável que haja uma falha tão básica no Math.random () do V8, mas o Chromium 11 adicionou suporte para geração de números aleatórios fortes usando a API window.crypto.getRandomValues ​​se você quiser tentar. Veja blog.chromium.org/2011/06/… .
user533676
Executando em combinação de Windows 7 e Windows XP.
Muxa
3

A resposta que postou originalmente esta solução UUID foi atualizada em 28/06/2016:

Um bom artigo de desenvolvedores do Chrome discutindo o estado da qualidade PRNG Math.random no Chrome, Firefox e Safari. tl; dr - No final de 2015 é "muito bom", mas não de qualidade criptográfica. Para resolver esse problema, aqui está uma versão atualizada da solução acima que usa ES6, a cryptoAPI e um pouco de assistente JS que não posso levar crédito :

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

Lucas
fonte
0

As respostas aqui tratam de "o que está causando o problema?" (Chrome Math.random seed issue), mas não "como posso evitá-lo?".

Se você ainda está procurando como evitar esse problema, escrevi esta resposta há algum tempo como uma versão modificada da função do Broofa para contornar esse problema exato. Ele funciona compensando os primeiros 13 números hexadecimais por uma porção hexadecimal do carimbo de data / hora, o que significa que, mesmo que Math.random esteja na mesma semente, ele ainda gerará um UUID diferente, a menos que seja gerado no mesmo milissegundo.

Briguy37
fonte