Возвращаясь к теме про фаззеры.

January 31st, 2008

Вот код, которым я пользуюсь для написания стресс тестов и фаззеров в своих проектах. Класс EntropyGenerator – обертка вокруг генератора случайных чисел.

class EntropyGenerator
{
public:
    EntropyGenerator():
        m_replay_index(std::numeric_limits<size_t>::max())
    {
        m_log.reserve(1024 * 64);
    }

    void
    replay()
    {
        m_replay_index = 0;
    }

    size_t
    generate(
        size_t up_to
        )
    {
        size_t r;

        if (m_replay_index == std::numeric_limits<size_t>::max())
        {
            if (up_to > 0)
            {
                errno_t err = rand_s(&r);
                BOOST_REQUIRE(err == 0);

                r /= std::numeric_limits<size_t>::max() / up_to;
            }
            else
            {
                r = 0;
            }

            m_log.push_back(r);
        }
        else
        {
            r = m_log[m_replay_index++];

            if (m_replay_index == m_log.size())
            {
                // This is the last generated number
                __debugbreak();
            }
        }

        BOOST_REQUIRE((r == 0 && up_to == 0) || (0 <= r && r < up_to));
        return r;
    }

protected:
    std::vector<size_t> m_log;
    size_t m_replay_index;
};

EntropyGenerator поддерживает два режима работы:

  1. При первом проходе он генерирует случайные целые в заданном диапазоне и сохраняет каждое сгенерированное число в лог;
  2. При втором и следующих проходах, EntropyGenerator переключается в режим воспроизведения сгенерированных чисел. При выдаче последнего сгенерированного числа срабатывает точка останова, позволяя посмотреть, что происходит в момент сбоя в отладчике.

Функция runStress запускает переданный тест, позволяя в случае сбоя прогнать тест сначала нужное количество раз. Сбоем считается любое непойманное исключение. Я пользуюсь Boost.Test, а там проверочные макросы (BOOST_REQUIRE и Ko) бросают исключения.

template <typename TestT>
runStress(
    TestT* test,
void
    size_t replay_count
    )
{
    EntropyGenerator rnd;

    for (size_t i = 0; i <= replay_count; )
    {
        try
        {
            // Run test
            (*test)(rnd);
            return;
        }
        catch (...)
        {
            if (i < replay_count)
            {
                ++i;
                rnd.replay();
            }
            else
                throw;
        }
    }
}

Пример теста:

// 64 chars
char randomData[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ[]";

void
stressLoadCells(
    EntropyGenerator& rnd
    )
{
    for (size_t repeat = 20; repeat > 0; --repeat)
    {
        //  Fill the source with random data of random length
        Source source;
        source.m_data.assign(rnd.generate(128), ' ');

        for (
            std::string::iterator i = source.m_data.begin(), i_end = source.m_data.end();
            i != i_end;
            ++i)
        {
            *i = randomData[rnd.generate(64)];
        }

        // Create buffer with a cell of random size
        Buffer buffer(&source, rnd.generate(15) + 1);

        for (size_t i = 0; i < 128; ++i)
        {
            size_t j = rnd.generate(static_cast<size_t>(source.size()));
            BOOST_REQUIRE(buffer[j] == source.m_data[j]);
        }
    }
}

void
stressTestLoadCells()
{
    runStress(&stressLoadCells, 1);
}

Точка входа в тест – функция stressTestLoadCells. Тестовый код помещается в функцию stressLoadCells, которая и вызывается один (в случае успеха) или несколько (в случае сбоя) раз.

Тест пишется как обычно. Никакой особенной поддержки повторов, логов в коде теста нет. Там где нужно получить очередное случайное число вызывается rnd.generate с нужным диапазоном. Удобно и довольно эффективно, хотя этот код ещё сильно недоработан. Нет возможности сохранить сбойную последовательность чисел для того, чтобы её затем воспроизвести. Нет возможности вывалиться в отладчик не на последнем числе, а за N вызовов rnd.generate.

, ,

  1. Oktan
    February 2nd, 2008 at 17:47 | #1

    спс) этот код мне очень помог

  2. February 5th, 2008 at 05:06 | #2

    Это тот самый ГПЧС, который “распотрошили” Leo Dorrendorf, Zvi Gutterman и Benny Pinkas?
    —–=== [ http://www.pgpru.com/novosti/2007/nestojjkostjvgpschwindowspozvoljaetbystrovskryvatjkljuchiisslsoedinenija ] ===—–
    Израильские учёные Leo Dorrendorf, Zvi Gutterman и Benny Pinkas опубликовали работу www”Cryptanalysis of the Random Number Generator of the Windows Operating System”.

    Им удалось дизассемблировать и трассировать закрытый код ОС Windows, содержащийся в библиотеках ADVAPI32.DLL, RSAENH.DLL и KSECDD.SYS и полностью восстановить исходный код генератора псевдослучайных чисел ОС Windows без какой-либо помощи со стороны компании Microsoft и практически полном отсутствии документации по этой теме. WRNG используют многочисленные приложения через вызов функции CryptGenRandom, также он используется в WinCryptoAPI.

    В работе также приводятся сравнения с LRNG – реализацией ГПСЧ в Linux, в которой также были ранее обнаружены многочисленные уязвимости, но из-за особенности архитектуры ОС, практическое значение их оказалось не так велико.

    Генератор Windows использует модифицированную функцию SHA-1 и потоковый шифр RC4. Не используя каких либо уязвимостей в самом шифре RC4, исследователи обнаружили многочисленные ошибки в дизайне генератора и его несоответствие элементарным и давно известным требованиям, которым должны отвечать такие генераторы.

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

    Атака типа forward security (предсказание предыдущих состояний генератора) составляет 223 операций (всего несколько секунд на персональном компьютере), а атака на backward security (предсказание последующих состояний) тривиальна и имеет сложность всего O(1)

    Это связано с тем, что обновление состояния генератора происходит не при каждой итерации, а только после использования выхода в 128 кбайт. Такое большое значение может быть израсходовано приложением зачастую лишь спустя несколько дней после запуска. Например, Internet Explorer обновит своё состояние PRNG только спустя 600-1200 SSL-сессий. Это очень большое временное окно для атаки. Если в Linux состояние генератора обновляется почти ежесекундно (что совместно с реализацией на уровне ядра и защитой от прямого чтения состояния пользовательскими процессами делают уязвимости в Linux некритичными – приложения могут читать только выход генератора), то в Windows оно может оставаться неизменным в течении многих дней или не успевать обновляться вообще.

    Исследователи рекоммендуют полностью переработать дизайн генератора, убрать из него функцию на основе RC4, которая не обеспечивает forward security и вообще не должна применяться в ГПСЧ. ОС Windows Vista исследованию не подвергалась, но учёные предполагают, что данный дизайн генератора сохранён и в ней.
    —–=== [ http://www.pgpru.com/novosti/2007/nestojjkostjvgpschwindowspozvoljaetbystrovskryvatjkljuchiisslsoedinenija ] ===—–

    • February 5th, 2008 at 08:32 | #3

      Ах! Порутчик, это опять вы? :-)

      Это не CryptGenRandom, а RtlGenRandom. Это немного разные вещи. Хотя вполне может быть что они используют одинаковый код. Только вот какое отношение уязвимость генератора случайных чисел имеет к тестовому коду?

  3. February 7th, 2008 at 00:05 | #4

    Ну куда я денусь-то? :)
    Пока я не проникся дзеном настолько, чтобы забыть свою неприязнь к мс и её произведениям. :)

    К тестовому – никакого. Совершенно. А вот к самому генератору – имеет, конечно. Разве нет?
    Кстати, он всё таки “генератор ПСЕВДОслучайных чисел”. Тут тоже есть некоторая разница. ;)

    • February 7th, 2008 at 23:14 | #5

      Вы бы ещё прониклись дзеном настолько, что начали бы генерировать конструктивую неприязнь вместо примитивного “увидел ключевое слово – запостил простыню не по делу”…

  4. February 8th, 2008 at 06:58 | #6

    сказав честно, я ничего не понимаю в этих фаззерах, для меня это совсем не понятно….

  1. January 31st, 2008 at 22:06 | #1
Comments are closed.