Ошибка алгоритма генерации ключа хэша кеша Firefox - PullRequest
7 голосов
/ 20 марта 2009

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

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

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


РЕДАКТИРОВАТЬ: Там были некоторые очень полезные ответы, однако мне нужна дополнительная пошаговая помощь для создания утилиты для проверки этих смешений кэша. Было бы здорово получить код Java, который может воспроизводить ключи, которые создает Firefox. Поэтому открытие щедрости по этому вопросу.


РЕДАКТИРОВАТЬ 2: Вот частично работающий Java-порт (записывается с использованием обработка ). Обратите внимание на тесты внизу; первые три работают как положено, а остальные нет. Я подозреваю что-то относительно подписанных / неподписанных целых. Предложения? * * 1023

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

}

Ответы [ 6 ]

6 голосов
/ 20 марта 2009

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

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

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

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

5 голосов
/ 20 марта 2009

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

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-битного числа в таблицу может быть когда-либо более слабым, а это означает, что требуется, чтобы lower4 xor upper4 определенного местоположения в строке (mod 8 символов) был уникальным.

2 голосов
/ 20 апреля 2009

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

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

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

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

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

Чтобы скомпилировать в любой системе Linux: g ++ -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, так как за последние несколько лет я видел странные вещи с этими изображениями:)

1 голос
/ 10 марта 2010

Это модифицированная версия генератора хеша 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;
}
1 голос
/ 20 марта 2009

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

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

PR_ROTATE_LEFT32(h, 4)

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

0 голосов
/ 01 апреля 2009

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...