Изпечатай

[gat3way]

Малко странна ситуация.

Написах си нещо като много рудиментарен интерпретаторен език за генериране на низове по определни правила. Идеята е свързана с password cracking-а, където някои алгоритми са прекалено изчислително сложни, за да можем да си позволяваме прости атаки от сорта на брутфорс, а от друга страна речниковите атаки са неефективни, понеже изискват прекалено големи речници, за да бъдат ефективни. Идеята е че ако можем да приложим прости трансформации върху някакви низове, можем да генерираме кандидат-пароли, които следват някакви pattern-и. Примерно имаме малък речник от английски думи, искаме да пробваме всяка комбинация от думи от този речник с числата от 0 до 99, като допълнително генерираме всички възможни комбинации където която и да е буква от паролата може да е главна или малка, това на моя "език" става по следния начин:

begin
must add dictionary english.txt
must add set 1:2:num
may togglecase
end

Както и да е, досега доста ненужни подробности. Парсъра на езика е проста работа, защото синтаксиса на езика е прост. Всичко се реализира лесно с function pointer-и като в общи линии има едно множество от трансформации, за които си има съответната функция и парсъра я вика. Това е вече направено и работи

Сега следва забавния момент. Аз имам четириядрен процесор и не мога да го утилизирам като хората. В зависимост от сложността на правилата които парсвам, мога да генерирам до 10-15 милиона кандидата в секунда. Това е напълно достатъчно, за да захраня GPU-тата с кандидати за някои "бавни" алгоритми като например този ползван от WPA-PSK. И напълно недостатъчно, ако искам да ги захраня с кандидати за "бързи" алгоритми, като например SHA1.

Съвсем очевидно следва да тредна парсъра, така че да се изпълнява върху ядрата паралелно. Паралелизацията да речем не е сложна задача, не е сложно да се разбие на независими части, не е embarassingly parallel, но не е далеч от това. Обаче миграцията ми разказа играта. Първата версия беше producer-consumer с определена бройка producer-и и consumer-и, синхронизацията разказа играта на производителността до степен до която single-threaded кода работеше по-добре. Просто прекалено много мутекси и condvar-и не са здравословни, а иначе не работи както трябва.

Втората идея - consumer-ите да са едновременно и producer-и и да приключим с тъпата синхронизация беше логичното следствие. Обаче това означава да пренапиша много брутално целия парсър, да редефинирам функциите да приемат като параметър нещо като thread id, което не е точно thread id-то на нишката (демек не съответства на pthread_self). Това ми строши часове безумни усилия. Да не говорим, че за да направя парсъра thread-safe и това да върви бързо, трябваше да променям структури от данни, захабявайки повече памет, защото силно държа да останат като глобални променливи, обаче всяка нишка да пипа само в нейното си (което от performance гледна точка е най-бързо, стига да нямаме false sharing).

Обаче тези упражнения ми се виждат доста тегави. Та чудно ми е в такъв случай как трябва да се постъпи най-добре?


* Това което аз направих. Моят случай не е толкова сложен и за няколко часа кода стана многонишков, нервите и усилията бяха доста обаче, дори за 2000 реда C код.

* Да ползваме "стандартизирания" POSIX-ки подход към Thread Local Storage-а, с pthread_create_key() и компания. Признавам, че не пробвах. Причината е че преди време си бях играл и бях установил че е бавно поради някаква причина, но може да съм грешал тогава. Като цяло вероятно това е правилния подход, макар че изисква също толкова усилия.

* gcc има някакъв extension, където си декларираш променливата с __thread и тя автоматично се алокира в TLS-а. Това изглежда най-просто и лесно. Обаче ме притеснява че кода няма да е много portable. Някой имал ли е вземане-даване с това?

* Мина ми една грозна мисъл да си реша половината проблеми с препроцесорен макрос. Обаче това ми се вижда дооооооста извратена идея.


Та това е. Някой имал ли е подобен проблем и как го е разрешил, много ми е интересно...

[CTEHATA]

Стигал съм до подобни положения, в които времето за синхронизация нарастваше до степен да унищожи ефекта от самото разпаралелване.
Моята практика показа, че когато стигна до такова положение, значи сам съм си усложнил задачата. Или не съм погледнал под верният ъгъл.

За твоя конкретен пример, парсерът може да мапне някъде речника/речниците, или направо да го зареди изрично.
След което да стартира  нишки, които да си пълнят буфери ( с фиксиран размер?)  със кандидат пароли. Всяка нишка да работи с конкретна група числа от "must add set" или друга подходяща за разпаралелване директива.
Всички нишки-генератори на кандидати да работят паралелно. Всяка ще има текущ буфер, както и свързан списък с буфери, достъпван само синхронизирано с мутекс. При запълване на текущия  буфер,  той ще бъде добавен към списъка (след като докопаме мутекса). Достатъчно самостоятелната нишка-генератор няма да има нужда от друга синхронизация, освен тази за добавяне на блокове към списъка.

Една или повече нишки, които тестват кандидат-паролите, могат да си вземат на някакъв принцип блокове от списъците на отделните нишки, стига да получат мутекса.
При бърза работа на генератора на кандидат-пароли и нарастване на заетата от буфери памет, могат да бъдат задържани мутексите, без да се вади блок, което ефективно ще спре нишките, веднага след текущия буфер.
При бавна работа на генератора, тестващите нишки ще пуснат мутекса веднага, след като видят, че няма какво да правят.
Може да има и нишка диспечер, която да взема и дава блокове.
При подобна схема, цялата синхронизация ще се случва при натрупване на цял блок кандидат пароли, както и след приключването на тестовете върху тях.
Единственото изискване ще е да има поне една годна за чисто разпаралелване директива. Но може да се окаже, че ако няма, по-добре да не се разпаралелва.

begin
must add dictionary english.txt
must add set 1:2:num paralelizeable level 4
may togglecase
end

П.П. Надявам се нещо да се разбира, че вече заспивам

[clovenhoof]

В шах програмирането когато се стига до момента на паралелизиране на търсенето се предпочита lockless hash table.
Там проблема е подобен.
Има обща хеш таблица за отделните нишки.
За да е lockless имаше една хитрост (по спомен):

Понеже няма синхронизация може да се корумпира ентрито, затова в хеш таблицата съхраняваш:
1. x = key ^ data
2. y = data
а за да валидизираш ентрито сравняваш текущия key_curr с key_stored = x ^ y

[lkr]

Не видях дали става въпрос за shared memory или за независими таскове. Ако са независими може да пробваш решения базирани на work-stealing queues като
http://software.intel.com/en-us/articles/intel-cilk-plus/
http://supertech.csail.mit.edu/cilk/

Дават много добри гаранции за performance и се работи супер лесно с тях. Intel TBB и .NET TPL работят на същия принцип.

[gat3way]

Паралелизацията без синхронизация в крайна сметка я измислих по следния начин:

1) Така или иначе имам по една или повече нишки за всяко GPU (бройката нишки за GPU е user-configurable)

2) Вместо една или повече нишки да генерират кандидати и да ги подават на GPU нишките, което изисква синхронизация, реших генерирането на кандидати да стане в рамките на GPU нишките.

3) За да не генерират GPU нишките едни и същи неща, а работата да е "разпределена",  парсъра още при първото правило, "пропуска" (threads_count -1) потенциални кандидати, в зависимост от id-то на нишката. Не е идеално, но работи.


При мен обаче проблема е следния, моите ID-та на нишките почват от 0 и свършват до броя нишки-1. Тези ID-та ползвам за да индексирам някои глобални структури от данни (предимно масиви от указатели към GPU буфери, масиви от OpenCL контексти, опашки и аргументи) по начин по който всяка нишка си пипа само в определена част от тях. Моите ID-та не съответстват на thread id-то на нишката (демек няма нищо общо с pthread_self()).

Парсъра работи по следния начин: за всяко правило (между begin и end) се изгражда една "верига" от функции, на края на всяка такава се вика следващата такава, ползвайки function pointer. Демек за горния пример, имаме това:

typedef  (void) (*node_func)(char *candidate);

имаме свързан списък (впоследствие стана масив с хардкоднат максимум на трансформациите на правило), който за всяка поредна трансформация пази указател към следваща функция и разни параметри. Call графа за горния пример изглежда така:


node_add_dictionary(...) -> node_add_set(...) -> node_togglecase(...) -> node_final(...)


node_final() е функция, която тъпче в един буфер кандидат-низа и когато буфера се напълни, го засилва към видеокартата.


Решението с хеш таблиците ми напомня на идиотската ми идея за макрос и lookup таблица която да match-ва thread id към "моето" id. Демек нещо от сорта на

#define SELF (lookup_table[pthread_self()])

и да си ползвам SELF вместо да въвеждам още един аргумент към всяка node функция и да го подавам по веригата. Това ми се видя малко извратено и не го направих, сега обаче на второ четене ми се вижда като доста смислена идея....хмммм

[gat3way]

Засега сътворих нещо такова:

http://youtu.be/dI30WKaNI8k

Видеото е от тест срещу около 2000 истински MD5 хешове от разбит сайт, без наложено силно password policy и с използване на някакви набързо нахвърляни от мен правила (от сорта на пробвай този речник, пробвай речника ама си поиграй с малки/главни букви или смени e->3, i->1, t->7, низове генерирани с  markov chains по зададани модели, добави символ към проста речникова дума и т.н.)

За около 10 минути, около 790 пароли паднаха, което лично според мен е успех.

Сега производителността...на клипчето си личи, върти се около 5 милиона/секунда, което е доста зле (GPU-базиран bruteforce engine на същата видеокарта прави над 2.3 милиарда/секунда за същия списък). Има много трески за дялане, най-вече от хост кода. От друга страна доста се смаза заради desktop recording софтуера, но реално погледнато рядко скача над 10 милиона/с освен с прости правила.

Дори никога да не го докарам над 20 милиона/секунда, пак ще съм доволен. Причината е че bottleneck-а е CPU-то при бързите алгоритми. При бавните такива като WPA, CPU-то може да захрани видеокартата достатъчно бързо с кандидат-пароли за тестване. Да се готвят wifi мрежите, защото мисля да издухам pyrit когато реализирам pbkdf2 kernel-а оптимизиран като хората

P.S другото което си мисля е да си напиша правила, пригодни за общия случай, следвайки масово използвани password pattern-и, правилата с най-голяма вероятност да дадат резултати най-отгоре. Доста лесно е да опишеш каквото и да било на "езика" който си си измислил сам обаче, хех. Някак си знаеш как е най-лесно и бързо да стане.

[clovenhoof]

Нищо не разбирам от пас-кракинг, но ми стана интересно.

Искам да те питам, може ли да се получи някаква информация като резултат от опит N, която да може да се ползва
в опит >= N+1?

За да може да речем за си съставиш алгоритъм за създаване на правила, дори динамично генериране на такъв.

Или всичко е на база интуитивно събиране на информация.

[gat3way]

Rule engine-а не е интелигентен достатъчно много, за да може сам да си измисли правила на базата на някакъв анализ на успешните опити.

Подобно нещо (на базата на вероятностни модели) може да се направи с Markov-ски вериги (rule engine-а подържа генериране на част от или целите кандидати на базата на зададен статистически модел). Статистическите модели лесно се съставят на базата на wordlist (в случая wordlist-а ще е списък с вече счупените пароли). Но е грубо.

За съжаление не е толкова лесно да се напише абсолютно интелигентен и адаптивен engine, или поне не е лесно за мен

[b2l]

Което ме подсеща за мултиагентните системи. Системите които се обучават сами. http://www.alyuda.com/