среда, 8 апреля 2015 г.

[prog.c++11] Решение md5_bruteforce на SObjectizer-5.5.4. Слишком много кода

Недавно в блоге ув.тов.asfikon-а промелькнула очередная интересная заметка. На этот раз про реализацию на языке Go простой программы для подбора MD5-хэша методом грубой силы (решение от Владимира Солонина). Реализовал ту же задачу средствами SObjectizer-5.5.4. Кода получилось в два раза больше, чем в программе на Go. Можно сравнить на pastbin: вот Go-ный вариант Владимира, вот мой C++ный (с минимумом комментариев).

Причем кода много, но он простой. Но много. И что с этим делать, пока ума не приложу. В частности, не очень понимаю, где здесь проблемы C++, а где мои собственные (т.е. недостатки SObjectizer-а).

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

На мой взгляд, в реализации нет ничего сложного. Самый важный момент в том, что рабочий агент, который выполняет перебор паролей, всего один (а не N, как в решении на Go). Просто за счет того, что операция подбора пароля stateless, этот агент получает возможность работать одновременно на нескольких нитях.

#include <iostream>
#include <chrono>
#include <array>
#include <iterator>

#include <so_5/all.hpp>

#include <md5_cpp11/all.hpp>

using namespace std;
using namespace std::chrono;

// Искомый пароль представляет из себя последовательность из пяти символов.
// Использовать для работы с такой короткой последовательностью вещи вроде
// std::string или std::vector неэффективно. А у простых C-шных векторов 
// нет, например, операторов сравнения.
// Зато стандартный контейнер array, который не что иное, как очень тонкая,
// но удобная обертка над C-шным вектором, как раз то, что нужно.
//
// Для удобства обозначения необходимого нам типа вводится псевдоним.
using password = array< char5 >;

// Нам нужно будет печать найденный пароль в std::cout. Но т.к. у array
// нет готового оператора сдвига, то придется его определить самостоятельно.
ostream & operator<<( ostream & to, const password & pw )
{
   copy( begin(pw), end(pw), ostream_iterator< password::value_type >(to) );
   return to;
}

// Функции next_byte и next_pass практически 1-в-1 взяты из решения на Go.
// Совместно они обеспечивают перебор вариантов при соблюдении условия,
// что пароль состоит из ограниченного количества символов.
password::value_type next_byte( password::value_type b )
{
   switch( b )
   {
      case 'z' : return '0';
      case '9' : return 'a';
      default : return b + 1;
   }
}

void next_pass( password & p )
{
   forauto e = p.rbegin(); e != p.rend(); ++e )
   {
      *e = next_byte( *e );
      if'0' != *e )
         break;
   }
}

//
// Здесь начинается то, что относится к SObjectizer-у.
//

// Для решения задачи потребуется три сообщения.
//
// Первое сообщение отсылается генератором диапазонов рабочему агенту.
// В этом сообщении содержится диапазон, который рабочий агент должен
// обработать. Диапазон, как это принято в C++, задается в виде [start,end).
//
// Второе сообщение -- это найденный пароль. Это сообщение отсылается
// рабочим агентом при обнаружении пароля с искомым MD5-хэшем. При получении
// такого сообщения работа приложения завершается.
//
// Третье сообщение -- это запрос очередного диапазона для обработки.
// Это сообщение отсылается рабочим агентом, когда он завершает обработку
// своего текущего диапазона и готов перейти к обработке следующего.
//
// Сообщения в SObjectizer различаются по своему C++ному типу. Поэтому для
// каждого сообщения нужно описать свой собственный C++ный тип.

// Сообщение для обработки очередного диапазона рабочим агентом.
struct process_range : public so_5::rt::message_t
{
   const password m_start;
   const password m_end;

   process_range( const password & start, const password & end )
      :  m_start( start )
      ,  m_end( end )
   {}
};

// Сообщение об успешно найденном пароле.
struct found : public so_5::rt::message_t
{
   const password m_result;

   found( const password & result ) : m_result( result ) {}
};

// Запрос очередного диапазона.
// Запрос не переносит никаких данных внутри, поэтому он оформляется
// как сигнал (аналог atom-а в Erlang-е).
struct get_next_range : public so_5::rt::signal_t {};

//
// Детали реализации агентов.
//

// Основная работа генератора: сформировать новый диапазон и отослать
// его в виде сообщения в указанный канал.
void generate_next_range(
   password & last,
   const so_5::rt::mbox_t & channel )
{
   // Механизм почти 1-в-1 взят из кода на Go.
   // Из значения '00000' формирует пару '00000','10000'.
   // Затем из значения '10000' пару '10000','20000' и т.д.
   auto start = last;
   last[ 0 ] = next_byte( last[ 0 ] );

   // Полученный диапазон отсылается в канал в виде сообщения process_range.
   so_5::send< process_range >( channel, start, last );
}

// Основная функция рабочего агента: пробежаться по всему диапазону и
// проверить все значения на совпадение с MD5-хэшем. Если пароль не найден
// (т.е. вышли за правую границу диапазона), то запросить новый диапазон.
// Если же пароль найден, то отослать его в канал посредством специального
// сообщения.
void worker(
   const so_5::rt::mbox_t & channel,
   const md5_cpp11::digest & etalon,
   const process_range & evt )
{
   auto pw = evt.m_start;
   // Бежим по диапазону и ищем совпадения...
   while( pw != evt.m_end && md5_cpp11::make_digest( pw ) != etalon )
      next_pass( pw );

   if( pw == evt.m_end )
      // Вышли за правую границу, значит пароль не найден,
      // значит нужно просить следующий диапазон.
      so_5::send< get_next_range >( channel );
   else
      // Пароль найден. Отправляем его в канал.
      so_5::send< found >( channel, pw );
}

// Основная функция по запуску всех необходимых для решения задачи агентов.
void do_brute_force( so_5::rt::environment_t & env )
{
   // Этот хэш будем использовать для поиска пароля.
   const auto hash = md5_cpp11::from_hex_string(
         "95ebc3c7b3b9f1d2c40fec14415d3cb8" ); // "zzzzz"

   // Просто для того, чтобы не писать длинных конструкций.
   using namespace so_5::disp::adv_thread_pool;

   // Определяем, сколько нитей можно запустить в параллель.
   auto workers = thread::hardware_concurrency();
   // Все агенты должны быть включены в состав кооперации агентов.
   // Создаем эту кооперацию.
   // Имя для нее будет выбрано автоматически.
   // Все входящие в нее агенты должны будут работать на пуле рабочих
   // потоков. Размер этого пула мы определили только что -- значение workers.
   auto coop = env.create_coop( so_5::autoname,
         // Обеспечивать рабочий контекст агентам будет приватный
         // adv_thread_pool-диспетчер.
         create_private_disp( env, workers )->binder(
               // Для того, чтобы входящие в кооперацию агенты могли
               // работать независимо друг от друга, необходимо задать
               // для них параметр "индивидуальный FIFO".
               params_t{}.fifo( fifo_t::individual ) ) );

   // Для взаимодействия всех агентов потребуется всего лишь один
   // почтовый ящик (он будет играть роль канала).
   // Это безопасно, т.к. каждый подписчик подписывается на разные
   // типы сообщений и можно не боятся того, что кто-то получит не
   // предназначенное для него сообщение.
   const auto channel = env.create_local_mbox();

   // Генератор диапазонов будет вызываться при поступлении к нему
   // сигналов get_next_range. Между этими вызовами генератор должен
   // где-то хранить свое состояние (т.е. правую границу последнего
   // сгенерированного диапазона). Заботимся об этом создавая объект last
   // в динамической памяти.
   auto last = make_shared< password >();
   // std::array не инициализируются по-умолчанию, поэтому нужно сделать
   // это явным образом.
   last->fill( '0' );

   // Генератор диапазонов.
   //
   // В его работе есть один фокус: при старте он должен отослать себе
   // столько запросов get_next_range, сколько будет рабочих потоков.
   // Тем самым инициируется раздача диапазонов для обработки.
   //
   // Т.к. рабочий агент всего один, то при своем старте он сможет
   // отослать всего один запрос. Нам же нужно, чтобы запросов было
   // столько, сколько рабочих нитей.
   coop->define_agent()
      .on_start( [channel, workers] {
            // Рассылка стартовых запросов самому себе.
            forsize_t i = 0; i != workers; ++i )
               so_5::send< get_next_range >( channel );
         } )
      // Это обработка запроса get_next_range из почтового ящика channel.
      // Просто дергаем соответствующую функцию, передавая в нее сохраненное
      // в лямбде состояние.
      // Фокус здесь лишь в том, что last захватывается по значению.
      // А т.к. last -- это shared_ptr, то last останется валидным до тех
      // пор, пока агент жив и работает.
      .event< get_next_range >( channel,
         [last, channel] {
            generate_next_range( *last, channel );
         } );

   // Рабочий агент.
   // 
   // Рабочий агент всего один. Но за счет того, что его событие
   // является stateless (т.е. не модифицирует никакого состояния агента),
   // у нас есть возможность запускать несколько обрабтчиков события
   // параллельно.
   // Эта возможность указывается явным образом посредством значения
   // so_5::thread_safe. Если этого не сделать, то SObjectizer будет
   // считать, что обработчик события stateful и для обеспечения thread
   // safety не позволит агенту работать сразу на нескольких нитях.
   coop->define_agent().event( channel,
         [channel, hash]( const process_range & evt ) {
            worker( channel, hash, evt );
         },
         // Именно благодаря этому указанию агент сможет работать
         // одновременно на нескольких рабочих нитях.
         so_5::thread_safe );

   // Вспомогательный агент, который нужен только для того, чтобы
   // получить результат и завершить работу программы.
   // Эти действия можно было бы поручить и генератору, то тогда
   // генератору пришлось бы отвечать за не связанные друг с другом
   // задачи.
   coop->define_agent().event( channel,
         [&env]( const found & evt ) {
            cout << "password: " << evt.m_result << endl;
            env.stop();
         } );

   // Теперь кооперация полностью оформлена и может быть запущена.
   env.register_coop( move( coop ) );
}

// Просто вспомогательная функция для определения того, сколько
// секунд (с дробной частью) было затрачено.
double time_spent( const steady_clock::time_point s )
{
   const auto e = steady_clock::now();
   return duration_cast< milliseconds >( e - s ).count() / 1000.0;
}

int main()
{
   // try-catch нужен т.к. об ошибках сообщается посредством исключений.
   try
   {
      // Засекаем, когда начали.
      const auto started_at = steady_clock::now();

      // Запускаем SObjectizer и агентов внутри него.
      // Выход произойдет только когда пароль будет найден.
      // Если не будет найден, то зависнем, что и должно быть
      // по условиям исходной задачи.
      so_5::launch( do_brute_force );

      // Осталось сообщить, сколько времени нам потребовалось.
      cout << "time: " << time_spent( started_at ) << "s" << endl;

      return 0;
   }
   catchconst exception & x )
   {
      cerr << "Exception: " << x.what() << endl;
   }

   return 2;
}

В общем, кода много. Что с этим делать сходу не понятно. Буду думать. Хотя, конечно, parallel computing -- это не та область, для которой SObjectizer предназначался...

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