ошибка алгоритма генерации ключа хэш-кода firefox

Question

Существует a bug in Firefox (даже в новых бета-версиях и в выпусках минного поля), что предотвращает кеширование определенных файлов из-за алгоритма создания ключа в их кеш-кеше. Here is a link to the source code of the function.

Я хочу, чтобы все файлы моего сайта могли быть кэшированы. Однако я не понимаю, почему их хэш-функция не создает уникальные ключи для разных URL-адресов. Я надеюсь, кто-нибудь сможет описать эту функцию mal в psuedo-code или java.

Было бы полезно создать утилиту для разработчиков, чтобы обеспечить уникальные URL-адреса до тех пор, пока эта ошибка не будет исправлена.

---

EDIT: Там были некоторые очень полезные ответы, однако, мне нужно больше шаг за шагом поможет создать утилиту для проверки этих mixups кэша. Было бы здорово получить код Java, который может воспроизводить ключи, которые создает firefox. Поэтому открытие щедрости по этому вопросу.

---

EDIT 2: Здесь частично работает Java порт (написанные с использованием processing). Обратите внимание на тесты внизу; первые три работают, как ожидалось, а другие нет. Я подозреваю что-то в отношении подписанных/неподписанных ints. Предложения?

// 
// 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

Вот как работает алгоритм:

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

визуально (16 -битовый версия):

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 

что это означает, что если у вас есть строки одинаковой длины и в основном совпадают, то, по крайней мере в одном случае, нижние 4 бита полукокса и старшие 4 бита следующий символ должен быть уникальным. Тем не менее, метод приклеивания 32-битного числа в таблицу может быть все слабее, что означает, что для него требуется, чтобы нижний 4 xor upper4 определенного места в строке (символы 8-го порядка) был уникальным.

Answer 2

Из того, что я понимаю, просто прочитав запись Bugzilla, ошибка проявляется, когда возникают две различные проблемы:

1. Их хэш-алгоритм генерирует коллизий для URL-адресов, которые «достаточно похожи». Из ошибки «достаточно похоже» кажется, что каждый 4 символа (или, возможно, 8) совпадают, и
2. Их логика для борьбы с хеш-коллингами терпит неудачу, потому что они не сбросили предыдущий url с одинаковым значением хэша на диск еще.

Так что, если у вас есть страница с двумя очень похожими URL-адресами, это может случиться в некоторых версиях Firefox. Как правило, этого не произойдет на разных страницах, я бы ожидал, так как тогда FF успеет сбросить записи на диск, избегая проблемы с синхронизацией.

Итак, если у вас есть несколько ресурсов (сценариев, изображений и т. Д.), Которые загружаются с одной и той же страницы, убедитесь, что они имеют пробег из 9 символов, которые совершенно разные. Один из способов, вы можете обеспечить это путем добавления строки запроса (что вы игнорируете) со случайным битом данных, что-то вроде:

• http://foo.com/resource.jsг = дп # @ JdsK #

Answer 3

Первый , вы не можете однозначно присвоить все цепочки целым числам (очевидно, существует целая последовательность строк (фиксированный размер), поэтому должны быть столкновений). У вас может быть хеш-таблица, которая может хранить все наборы данных (например, все ваши файлы), но для ее получения вам нужно изменить код хеш-таблицы, а не хеширование.

Во-вторых, я вижу проблему с помощью функции хеширования вы публикуемую в этой части:

PR_ROTATE_LEFT32(h, 4) 

Если это действительно вращение h (я не проверял это), вращающийся на 4 означает, что строки, имеющие две 8-байтовые (я предполагаю, 32-разрядный хеш) части, замененные (например, xxxxxxxxyyyyyyyy против yyyyyyyyxxxxxxxx), будут иметь равный хеш. Если изменить его на что-то относительно простым с размером хеш (например, 5.), Это будет происходить только обмениваемых части длины 32.

Answer 4

Вы, по-видимому, ошибаетесь в отношении настоящей ошибки. Несомненно, есть хеш-коллизии из-за неуклюжего выбора алгоритма хеширования. Но даже хэш (x) = 1 не вызовет описанных проблем. Он просто превратил поиск O (1) в поиск списка ссылок (через N) по первому ведру.

Настоящая проблема заключается в том, что Firefox не справляется с хеш-коллизиями. Поэтому для этого требуется идеальный хэш всех URL-адресов. «Все URL-адреса», к сожалению, находятся вне вашего контроля.

Answer 5

Эта ошибка была серьезной проблемой для моего сайта: http://worldofsolitaire.com

Я работал вокруг него давно с помощью условного правила в файле .htaccess, который будет отключить кеширование изображений на сайте для пользователей Firefox , Это была ужасная вещь, которую нужно было делать, но в то время я не мог отследить ошибку в Firefox и иметь сайт немного медленнее, чем показывать дубликаты/искаженные изображения.

Когда я прочитал связанную ошибку, что она была исправлена ​​в последних версиях Firefox, я изменил условие 19 апреля 2009 года (вчера), чтобы отключить кеширование для пользователей Firefox 2.

Через несколько часов я получил более 10 сообщений электронной почты пользователей Firefox 3 (подтвержденных) о том, что они видят дубликаты изображений. Таким образом, эта проблема является проблемой STILL в Firefox 3.

Я решил создать простую программу тестирования Linux, которая позволила бы мне проверять URL-адреса, чтобы узнать, генерируют ли они одни и те же ключи кеша кэша.

Чтобы скомпилировать в любой системе Linux: г ++ -o ffgenhash ffgenhash.cpp

Вот код (сохранить в файл 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; 
} 

Как вы можете видеть, здесь два URL реальной жизни в том, что генерируют один и тот же кэш хэш-ключ:

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

Поскольку я предварительно загрузить эти изображения в цикле Javascript, пытаясь использовать какой-то пустой < сценарий > бирка обходной способ невозможно здесь.

Действительно, я считаю, что единственным реальным решением является изменение URL-адреса для пользователей Firefox каким-то образом для создания уникального кеш-ключа. Так что это подход, который я буду использовать.

Кстати, я получу соблазн создать дополнение Firebug, которое проверит все ресурсы, загруженные сайтом, и даст большую ошибку, если два ресурса на сайте имеют общий хеш-ключ, чтобы разработчик знал. Было бы здорово запускать такие сайты, как карты Google, так как я видел странные вещи с этими изображениями за последние несколько лет :)

Answer 6

Это модифицированная версия хэш-генератора Sembiance, которая работает корректно, даже если скомпилирована на 64- бит платформы:

#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; 
}