... или "Зачем нужно бета-тестирование".

Недавно в поисках улучшения производительности своего музыкального сервиса перевел один из своих джанговских проектов с mod_python на FastCGI. Обе эти схемы по-разному реализуют одно и то же: постоянное нахождение в памяти загруженного приложения, чтобы не тратить время на его загрузку при каждом обращении. И обычно первый рекомендуют как наиболее простой вариант, а второй — как более экономный в памяти. Но именно различие в их работе сказалось в исключительно неожиданном баге.

Mod_python работает как часть самого Апача. Апачевские же процессы не живут вечно, один процесс обрабатывает какое-то количество (например 1000) запросов, а потом принудительно уничтожается.

FastCGI — это отдельно висящий в системе сервис, в который веб-сервер передает запросы, и получает ответы. Тот серверр, который я использую, всегда держит загруженными минимальное количество (5 в моем случае) процессов, которые висят там от начала времен. К ним могут добавляться новые по мере роста загрузки, но этот минимум живет вечно.

Одна из функций системы — рассылка приглашений с генерируемым уникальным паролем. Работает она совершенно просто: из набора допустимых символов случайно выбирается один, и так повторяется столько раз, сколько нужно для длины пароля. Только, как известно, "случайность" в компьютерах — это надувательство просто очень сложная функция, которая выдает числа, кажущиеся случайными. Поскольку сама последовательность на самом деле исключительно предсказуема, для придания процессу большей случайности она рассчитывается от какого-то базового значения ("seed"), которое тоже надо выбрать случайно. Чаще всего этот seed берется из текущего системного времени в момент, когда вам понадобились случаные числа. Другими словами, если ваша программа запускается периодически по запросам пользователя, то вы получаете вполне себе достаточно случайные пароли (здесь специалисты по безопасности должны саркастически смеяться).

Так у меня и было с mod_python: код перезагружался в какие-то моменты времени и успешно генерировал пароли. А в FastCGI он периодически перезагружаться перестал, что означает, что этот самый реально случайный выбор seed'а в нем произошел только один раз при генерации первого пароля. А потом должна идти просто длинная псевдослучайная последовательность.

Чего я не ожидал, это насколько же она псевдослучайная. Вчера мне завели баг о том, что система говорит, что не может никому оформить приглашения, потому что в базе записано аж 4 одинаковых "уникальных" пароля. Я попробовал сгенерировать еще два: оба раза вылез точно такой же пароль. То есть эта самая последовательность выродилась со временем так, что стала генерировать повторяющиеся значения, да еще и период повторения совпал с длиной пароля. Вот вам и уникальность :-)

В итоге починил тем, что стал рандомизировать последовательность каждый раз при генерации, но не только от системного времени, но и еще добавил парочку других значений из близлежащих данных. Это, причем, не паранойя: у нас часто приглашения генерируются пачкой и я подумал, что довольно вероятно, что два пароля могут сгенерироваться достаточно быстро, чтобы попасть в один момент времени.

Комментарии: 15

  1. Ivan A-R

    Хм? А пароль генерится стандартными средствами python'a?
    Есть же стандартные формулы для генерации псевдослучайных последовательностей с длинными периодами повторения и без вырождения.
    Такие фортели происходят обычно, когда какой нибудь шибко умный программист пишет "оригинальную" функцию случайных значений. Но совсем не задумывается, что неплохо бы ещё и математически доказать, что это функция хорошая.

  2. Ivan A-R

    оговорился.. Не пароль, а случайное число. =) Жара...

  3. Иван Сагалаев

    Да, стандартными. Забыл написать, хотя это и есть самое удивительное :-). Вот кусочек, как он генерится:

    from random import choice
return ''.join([choice(allowed_chars) for i in range(length)])
  4. Макс Лапшин

    Прямо хоть с аппаратного рандомайзера считывай.

  5. Ivan A-R

    Иван Сагалаев, может это грабли конкретной версии? Сейчас попробовал сгенерить 10e6 символов таким способом, вроде заметных повторов нет. Python 2.3.5

    Макс Лапшин, их затем и придумали, что бы ими пользоваться. Насколько я знаю в последних x86 процах реализован аппаратный рандомайзер. Умные системы предпочитают с него читать случайное число, если он доступен.

  6. Иван Сагалаев

    Судя по документации модуля random, версии 2.3 и 2.4 используют один и тот же алгоритм (Mersenne Twister). Возможно, дело не в алгоритме, а в том, что на разных seed'ах это проявляется по-разному.

    И в той же документации написано, что для случайного seed'а таки используется генератор, доступный в ОС, а не системное время. А ОС, судя по всему, использует именно аппаратные средства (/dev/urandom в юниксах и CryptGenRandom в Windows). Так что может я и зря свои данные подпихивал в seed().

  7. Макс Лапшин

    Ivan A-R Ну так такими вещами должна функция rand заниматься

  8. CGVictor

    Я делал по-другому: добавялл к паролу подчеркнуто неслучайное значение, сопоставленное конкретному пользователю (это может быть email, какой-то номер, etc). А потом брал куски из MD5 и SHA1 полученного seed-а.
    Discuss.

  9. Pavel Plesov

    А в FastCGI он периодически перезагружаться перестал, что означает, что этот самый реально случайный выбор seed’а в нем произошел только один раз при генерации первого пароля. А потом должна идти просто длинная псевдослучайная последовательность.

    Напротив, очень похоже на чистый запуск, о чем свидетельствует эксперимент - 6 одинаковых чисел подряд.

    Тогда значение seed'а - строго заданное начальное значение в использованной библиотеке генерации случайных чисел.

  10. Max Ischenko

    Ха, у меня весьма похожий алгоритм используется на knigoman.com.ua. Только я проверяю новое значение по базе:

        while 1:
        pubid = idgenerator(length)
        try:
            f(pubid)
        except SQLObjectNotFound:
            # found unused identifier
            return pubid

    Кондово конечно, но работает. ;-)
    Опять же, есть UNIQUE constraint.

  11. Иван Сагалаев

    Да дело не в том, как это починить. Это просто, и есть миллион способов. Меня удивил сам факт того, что даже умный оттестированный алгоритм иногда дает такие сбои.

  12. Julik

    Погоди, а причем тут сбои? Если ты всего один раз за запуск процесса делаешь seed то естественно он зациклится на определенном диапазоне значений. Если я правильно понимаю это просто premature optimisation (задание зерна один раз при запуске процесса as opposed to задание оного для каждого прогона генератора). Или я не догоняю?

  13. Иван Сагалаев

    Ну он не обязан циклиться, вообще-то. Или, если циклится, то хороший алгоритм должен это делать с огромным периодом, чтобы значения не повторялись в обозримом практическом применении. Но вот так, чтобы генератор устойчиво генерировал один и тот же пароль длинной в 8 символов — это сбой.

  14. Julik

    Мм.. зависит от релизации генератора ИМХО. В Руби то же самое - если засидить генератор одним числом и долго гонять, то будешь поулчать повторяющийся результат.

  15. MEOW

    > перевел один из своих джанговских проектов с mod_python на FastCGI

    А SCGI не пробовали? По идее, быстрее всех должно получиться..

Добавить комментарий