bug di algoritmo di generazione di chiavi hash della cache di firefox

Question

C'è a bug in Firefox (anche nelle nuove beta e nelle versioni di campo minato) che impedisce il caching di determinati file a causa dell'algoritmo per la creazione di una chiave nel loro hash della cache. Here is a link to the source code of the function.

Voglio garantire che tutti i file del mio sito possano essere memorizzati nella cache. Tuttavia, non capisco perché la loro funzione di hashing non riesca a creare chiavi univoche per URL distinti. Spero che qualcuno possa descrivere questa funzione mal in psuedo-code o java.

Sarebbe bene creare un'utilità per gli sviluppatori per garantire URL unici fino a quando questo errore non viene risolto.

---

EDIT: Ci sono state alcune risposte molto utile, però, ho bisogno di più aiuto step-by-step per creare un programma di utilità per verificare la presenza di questi mixups della cache. Sarebbe bello avere del codice java in grado di riprodurre i tasti creati da firefox. Pertanto, l'apertura di una taglia su questa domanda.

---

EDIT 2: Ecco una porta java parzialmente lavoro (scritto usando processing). Nota i test in basso; i primi tre funzionano come previsto, ma gli altri no. Sospetto qualcosa riguardo agli intro firmato/non firmato. Suggerimenti?

// 
// the bad collision function 
// http://mxr.mozilla.org/mozilla/source/netwerk/cache/src/nsDiskCacheDevice.cpp#240 
// 

//248 PLDHashNumber 
//249 nsDiskCache::Hash(const char * key) 
//250 { 
//251  PLDHashNumber h = 0; 
//252  for (const PRUint8* s = (PRUint8*) key; *s != '\0'; ++s) 
//253   h = PR_ROTATE_LEFT32(h, 4)^*s; 
//254  return (h == 0 ? ULONG_MAX : h); 
//255 } 

// 
// a java port... 
// 

String getHash(String url) 
{ 

//get the char array for the url string 
char[] cs = getCharArray(url); 

int h = 0; 

//for (const PRUint8* s = (PRUint8*) key; *s != '\0'; ++s) 
for (int i=0; i < cs.length; i++) 
{ h = PR_ROTATE_LEFT32(h, 4)^cs[i]; 
} 

//looks like the examples above return something in hex. 
//if we get matching ints, that is ok by me. 
//but for fun, lets try to hex the return vals? 
String hexVal = hex(h); 
return hexVal; 
} 

char[] getCharArray(String s) 
{ 
    char[] cs = new char[s.length()]; 
    for (int i=0; i<s.length(); i++) 
    { 
    char c = s.charAt(i); 
    cs[i] = c; 
    } 

    return cs; 
} 

// 
// how to PR_ROTATE_LEFT32 
// 

//110 /* 
//111 ** Macros for rotate left and right. The argument 'a' must be an unsigned 
//112 ** 32-bit integer type such as PRUint32. 
//113 ** 
//114 ** There is no rotate operation in the C Language, so the construct 
//115 ** (a << 4) | (a >> 28) is frequently used instead. Most compilers convert 
//116 ** this to a rotate instruction, but MSVC doesn't without a little help. 
//117 ** To get MSVC to generate a rotate instruction, we have to use the _rotl 
//118 ** or _rotr intrinsic and use a pragma to make it inline. 
//119 ** 
//120 ** Note: MSVC in VS2005 will do an inline rotate instruction on the above 
//121 ** construct. 
//122 */ 
//... 
//128 #define PR_ROTATE_LEFT32(a, bits) _rotl(a, bits) 


//return an int (32 bit). what do we do with the 'bits' parameter? ignore? 
int PR_ROTATE_LEFT32(int a, int bits) 
{ return (a << 4) | (a >> (32-bits)); 
} 

// 
// examples of some colliding hashes 
// https://bugzilla.mozilla.org/show_bug.cgi?id=290032#c5 
// 

//$ ./hashit "ABA/xxx.aba" 
//8ffac222 
//$ ./hashit "XyZ/xxx.xYz" 
//8ffac222 
//$ ./hashit "CSS/xxx.css" 
//8ffac222 
//$ ./hashit "JPG/xxx.jpg" 
//8ffac222 

//$ ./hashit modules_newsfeeds/MenuBar/MenuBar.css 
//15c23729 
//$ ./hashit modules_newsfeeds/ListBar/ListBar.css 
//15c23729 

//$ ./hashit modules_newsfeeds/MenuBar/MenuBar.js 
//a15c23e5 
//$ ./hashit modules_newsfeeds/ListBar/ListBar.js 
//a15c23e5 



// 
// our attempt at porting this algorithm to java... 
// 

void setup() 
{ 

String a = "ABA/xxx.aba"; 
String b = "CSS/xxx.css"; 
String c = "CSS/xxx.css"; 
String d = "JPG/xxx.jpg"; 

println(getHash(a)); //yes 8ffac222 
println(getHash(b)); //yes 8ffac222 
println(getHash(c)); //yes 8ffac222 
println(getHash(d)); //no [??] FFFFFF98, not 8ffac222 

println("-----"); 

String e = "modules_newsfeeds/MenuBar/MenuBar.css"; 
String f = "modules_newsfeeds/ListBar/ListBar.css"; 

println(getHash(e)); //no [??] FFFFFF8C, not 15c23729 
println(getHash(f)); //no [??] FFFFFF8C, not 15c23729 

println("-----"); 

String g = "modules_newsfeeds/MenuBar/MenuBar.js"; 
String h = "modules_newsfeeds/ListBar/ListBar.js"; 

println(getHash(g)); //yes [??] FFFFFF8C, not a15c23e5 
println(getHash(h)); //yes [??] FFFFFF8C, not a15c23e5 

} 

Answer 1

Ecco come funziona l'algoritmo:

initialize hash to 0 
for each byte 
    shift hash 4 bits to left (with rotate) 
    hash = hash XOR character 

visivamente (16 versione bit):

00110000    = '0' 
    00110001   = '1' 
     00110010  = '2' 
      00110011 = '3' 
0100   0011 = '4' 
00110101    = '5' 
==================== 
01000110001000010000 (and then this will be 'rotated' 
         so that it lines up with the end) 
giving: 
     00100001000001000110 

ciò significa che se si dispone di corde della stessa lunghezza e sono per lo più lo stesso, poi in almeno un caso, i più bassi 4 bit di un carattere e superiori di 4 bit il prossimo char xor a vicenda deve essere unico. Tuttavia, il metodo di incollare il numero a 32 bit in una tabella potrebbe essere sempre più debole, il che significa che richiede la lower4 xor upper4 di una particolare posizione nella stringa (mod 8 caratteri) essere univoca.

Answer 2

Da quello che ho capito di solo leggendo l'entrata Bugzilla, il bug si manifesta quando si verificano due problemi distinti:

1. Il loro algoritmo di hash genera collisioni per gli URL che sono "abbastanza simili". Dal bug "abbastanza simile" sembra significare ogni 4 caratteri (o forse 8) gli url sono uguali, e
2. La loro logica per gestire le collisioni di hash fallisce perché non hanno svuotato l'url precedente con lo stesso valore di hash su disco ancora.

Quindi, in sostanza, se si dispone di una pagina con due URL molto simili questo potrebbe accadere su alcune versioni di Firefox. In genere non succederà su pagine diverse, mi aspetterei, da allora FF avrà il tempo di svuotare le voci sul disco evitando il problema di temporizzazione.

Quindi se si dispone di più risorse (script, immagini, ecc.) Caricate tutte dalla stessa pagina, assicurarsi che abbiano una sequenza di 9 caratteri completamente diversi. Un modo si potrebbe evitare questo rischio è aggiungendo un querystring (che si ignora) con un po 'casuale di dati, qualcosa come:?

• http://foo.com/resource.jsr = dn # @ JdsK #

Answer 3

First , non è possibile eseguire l'hash univoco di tutte le stringhe su numeri interi (ovviamente, ci sono più stringhe di numeri interi (di dimensioni fisse), quindi devono esserci collisioni). È possibile avere una tabella hash che può contenere tutti i set di dati (ad esempio tutti i file), ma per ottenerla è necessario modificare il codice della tabella hash, non la funzione di hashing.

In secondo luogo, vedo un problema con la funzione di hashing che hai postato, in questa parte:

PR_ROTATE_LEFT32(h, 4) 

Se lo fa davvero rotazione h (non ho controllato su questo), in rotazione da 4 mezzi stringhe con due parti di 8 byte (presumo hash a 32 bit) scambiate (ad esempio xxxxxxxxyyyyyyyy rispetto a yyyyyyyyxxxxxxxx) avranno lo stesso hash. Se si cambia in qualcosa di relativamente privilegiata per la dimensione hash (ad es. 5), questo avverrà solo per le parti scambiati di lunghezza 32.

Answer 4

Apparentemente si sbaglia sul vero bug. Certo, ci sono collisioni di hash a causa della scelta incredibilmente sbagliata di un algoritmo di hash. Ma anche hash (x) = 1 non causerebbe i problemi descritti. Si limiterebbe a trasformare una ricerca O (1) in una ricerca di elenchi collegati O (N) attraverso il primo segmento.

Il vero problema è che Firefox non riesce a gestire le collisioni di hash. Richiede quindi un hash perfetto di tutti gli URL. "Tutti gli URL" sfortunatamente è un set fuori dal tuo controllo.

Answer 5

Questo bug è stato un grosso problema per il mio sito: http://worldofsolitaire.com

ho lavorato intorno ad esso molto tempo fa utilizzando una regola condizionale in un file .htaccess che avrebbe disattivare la memorizzazione nella cache delle immagini sul sito per gli utenti di Firefox . Questa è stata una cosa orribile da fare, ma al momento non sono riuscito a rintracciare il bug in Firefox e avere il sito leggermente più lento è meglio che mostrare immagini duplicate/corrotte.

Quando ho letto nel bug collegato che è stato risolto nelle ultime versioni di Firefox, ho modificato il condizionale il 19 aprile 2009 (ieri) per disattivare solo la memorizzazione nella cache per gli utenti di Firefox 2.

Alcune ore più tardi ho ricevuto più di 10 e-mail dagli utenti di Firefox 3 (confermato) che stavano visualizzando immagini duplicate. Quindi questo problema è ANCORA un problema in Firefox 3.

Ho deciso di creare un semplice programma di test Linux che mi permettesse di controllare gli URL per vedere se generano le stesse chiavi di hash della cache.

Per compilare in ogni sistema Linux: g ++ -o ffgenhash ffgenhash.cpp

Ecco il codice (Salva su file ffgenhash.cpp)

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

#define ULONG_MAX 0xFFFFFFFF 
#define PR_ROTATE_LEFT32(a, bits) (((a) << (bits)) | ((a) >> (32 - (bits)))) 

unsigned long ffgenhash(const char * key) 
{ 
    unsigned long h=0; 

    for(const unsigned char * s = (unsigned char *) key; *s != '\0'; ++s) 
    { 
     h = PR_ROTATE_LEFT32(h, 4)^*s; 
    } 

    return (h==0 ? ULONG_MAX : h); 
} 

int main(int argc, char ** argv) 
{ 
    printf("%d\n", ffgenhash(argv[1])); 
    return 0; 
} 

Come si può vedere, qui ci sono due URL di vita reale che generano la stessa chiave hash della cache:

./ffgenhash "http://worldofsolitaire.com/decks/paris/5/12c.png" 
1087949033 
./ffgenhash "http://worldofsolitaire.com/decks/paris/5/13s.png" 
1087949033 

Da quando ho precaricare queste immagini in un ciclo Javascript, cercando di utilizzare una sorta di svuotamento del tag > script < non è possibile qui.

In effetti penso che la mia unica vera soluzione sia modificare gli URL per gli utenti di Firefox in qualche modo per generare una chiave hash cache univoca. Quindi questo è l'approccio che userò.

A proposito, sono quasi tentato di creare un'aggiunta Firebug che verificherà tutte le risorse caricate da un sito e darà un grosso errore se due risorse sul sito condividono una chiave hash comune, quindi lo sviluppatore ne è a conoscenza. Sarebbe bello gestire siti come Google Maps in questo modo perché ho visto cose strane con quelle immagini negli ultimi anni :)

Answer 6

Questa è la versione modificata del generatore di hash di Sembiance che funziona correttamente anche quando è compilato su 64- bit platform:

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

#define ULONG_MAX 0xFFFFFFFF 
#define PR_ROTATE_LEFT32(a, bits) (((a) << (bits)) | ((a) >> (32 - (bits)))) 

unsigned int ffgenhash(const char * key) { 
    unsigned int h=0; 
    for(const unsigned char * s = (unsigned char *) key; *s != '\0'; ++s) { 
     h = PR_ROTATE_LEFT32(h, 4)^*s; 
    } 
    return (h==0 ? ULONG_MAX : h); 
} 

int main(int argc, char ** argv) { 
    printf("%u\n", ffgenhash(argv[1])); 
    return 0; 
}