Category: наука

Category was added automatically. Read all entries about "наука".

2014-04

ICFP Postmortem: Team ryba, part 4

(начало здесь, здесь и здесь)

Итак, что же мы имели по состоянию на начало следующего рабочего дня, позднее воскресное утро? В минусе были несломанный алгоритм шифрования, непонятно куда применимые адаптации, не всегда работающий активатор и загадочный ген hitWithTheClueStick, в котором явно было что-то очень полезное, только вот вытащить это было никак. Зато в плюсе были дизассемблер, таблица генов и некоторое понимание того, как эта штука работает.

А работает она, кстати, крайне красиво. Очень сжато это объясняется в хелпе, только фиг это поймёшь с первого раза. :) В отличие от обычного компьютера, который передвигает instruction pointer по памяти фиксированного размера, в интерпретаторе DNA instruction pointer всегда указывает в начало, зато размер памяти переменный, и код постоянно копируется туда-сюда. То есть, например, вызов функции (гена) - это копирование в начало DNA (в красную зону, если пользоваться терминологией из хелпа) тела функции из фиксированной области (зелёной зоны) и генерация кусочка кода, который потом вернёт управление обратно. Условный переход - это поиск в памяти значения true или false по определённому offset'у и пропуск определённого количества байт, если оно там нашлось.

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

Подробно рассказывать, что именно и как нам удалось пропатчить, я не буду, поскольку организаторы просили-таки не разглашать результаты до их окончательного объявления, а список пропатченных областей практически эквивалентен этому самому результату. :) Так или иначе, времени на эксперименты с разными вариантами патчей ушло довольно много. Занятие это было изрядно ностальгическим - доводилось мне в своё время менять 74 на EB в коде проверки регистрации всяких разных досовых софтинок. :) Здесь дело осложнялось, во-первых, тем, что не было простого способа кодировать переходы назад (вперёд-то просто - инструкции пропустить, а назад - нужно как-то хитро оригинальный код копировать), и во-вторых, тем, что значения true и false в закодированном виде занимали разное количество acid'ов. Так что обходились в основном пропуском кусков методов (в частности, переходов) и изменением числовых параметров, передаваемых в функции.

Интереснее было с битыми генами. Нам намекали, что некоторые гены могут быть повреждены и их как-то можно восстановить, но хитрость была в том, что каждый ген надо было восстанавливать по-своему. Нам удалось восстановить три из них. Для одного из них имелись коды Хэмминга, упоминавшиеся в одной из страничек документации. Вызывать встроенную функцию коррекции мы не научились, поэтому я просто вбил таблицу кодов из википедии (брутфорс - наше всё) и сделал генератор нужного патча на Java. Для другого гена нашлась просто его копия задом наперёд, на которую намекала страничка про палиндромы. С третьим оказалось совсем смешно - он был заражён вирусом. :) С вирусом разбирались Майк с Лёшей, поэтому рассказ о том, в чём там была фишка, я оставлю им.

По дороге Майк с Лёшей ещё больше ускорили нашу рендерилку, и к концу она справлялась с отрисовкой картинки уже всего за полторы минуты.

Последние префиксы, которые мы пытались отсылать на сервер уже в начале шестого утра, почему-то результата совершенно не давали, но мы решили, что утро вечера мудренее, и пошли по домам спать. :)

Ну и в понедельник, за последние два с половиной часа контеста, мы с Лёшей подчистили хвосты, починили некоторые из патчей, которые не заработали в воскресенье, и получили в итоге вполне весомое улучшение итогового результата. Насколько он в итоге хорош - узнаем в октябре. :)

Суммарное время, потраченное на работу, получается примерно таким: 16 часов в пятницу, 14 в субботу, 14 в воскресенье и 2 в понедельник. Итого 46 из 72. При этом я не могу сказать, что у нас было много больших продолбов или хождения по ложным следам - основная часть времени была потрачена вполне по делу. Поэтому очень интересно, получился ли осмысленный результат хотя бы у кого-нибудь из lightning division, в котором результат надо было сдать через 24 часа.

Ну и ещё немного цифр для статистики: примерно 4К итоговый префикс, 165К кода на Java, 306 коммитов в Subversion.

Вроде как всё, отчёт окончен. :)
2014-04

ICFP Postmortem: Team ryba, part 3

(начало здесь и здесь)

В субботу утром ковыряние нашего задания я продолжил из дома. Начать я решил с того, чтобы попробовать написать декомпилятор для DNA - раз у генов есть start offset и size, значит, то, что между ними, можно сдампить в виде последовательности инструкций. (Тем более что у меня уже был некоторый опыт расковыривания скриптовых языков разных игрушек, так что подходы были известны.)

Начал я с одной из функций отрисовки страничек хелпа. Раз экран хелпа состоит из нескольких строк текста, а в таблице генов есть функция drawString, можно было предположить, что в этой функции можно будет найти вызовы drawString. И действительно, в дампе обнаружились паттерны, которые содержали offset и длину функции drawString в качестве параметров инструкций skip. Так что дизассемблер был быстро научен находить все паттерны такой же структуры и печатать их как вызовы функций.

Следующим номером были строковые параметры. Кое-что про то, как они кодируются мы знали из хелпа, поэтому найти перед вызовами drawString инструкции копирования кусков DNA с длиной, делящейся на 9, было несложно. Чуть больше времени ушло на то, чтобы восстановить, как именно выглядит кодировка. Но и это было делом техники, поскольку мы знали, что именно печатается, и даже таблицу с намёками из хелпа получилось пустить в дело. (Как и с шифрованием, после окончания контеста оказалось, что кодировка эта - просто EBCDIC.)

Научившись вытаскивать из генов строчки, я радостно начал дампить строчки из генов impdoc*, которые содержали документацию по отдельным генам. Нашлась куча интересного, хотя потом и выяснилось, что гены эти можно было просто запустить, и получить намного более читаемый результат.

На этой радостной ноте я ушёл поздравлять свою сестру squirrel_ с днём рожденья, а народ тем временем уже вовсю ковырялся в офисе. Майк выложил ещё пачку оптимизаций DNA, Лёша оптимизировал рендерер, а Олег экспериментировал с вызовами отдельных генов и смотрел, что получается.

Поздравив сестру и приехав в офис, я узнал что народ продолжил мою работу по написанию дизассебмлера, и заодно наковырял ещё какую-то интересную документацию. Похоже было, что в нашей замечательной DNA был засунут ещё и интерпретатор какого-то функционального языка.

Следующее принципиальное улучшение дизассебмлера заключалось в том, что мы загнали в него таблицу генов. Решили, что набить её ручками будет быстрее, чем выдумывать какие-то утилитки: поделили 14 страниц на четверых, набили, выложились, смёржились, и всего за 40 минут необходимый результат был получен.

Дальше я ещё немножко почитал документацию и научился передавать параметр в функцию checkGeneTable. С этим параметром она подсчитывала контрольную сумму всех генов, что было очень полезно для того, чтобы понять, какие из генов побиты или зашифрованы. Проблема была только в том, что считалось это очень медленно, так что следующие два с половиной часа я занимался в основном тем, что менял параметры, выкладывал картинки и тупил, пока работал сам рендеринг. Майк в это время безуспешно пытался понять, как работает активатор и как запустить через него два гена последовательно, а Олег продолжал ковырять дизассемблер.

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

На следующее интересное открытие нас натолкнула страничка про стеганографию. Оказалоcь, что из подозрительных жёлтых буковок на страничках с описаниями предыдущих контестов тоже можно составить префикс, и этот префикс включает рисование холмов - только вот почему-то после этого вся остальная картинка совершенно разъезжается. Что с этим делать, мы разобрались только на следующий день - оказалось, это всё неспроста. :)

Тем временем Роман приспособил для целей контеста ещё один из продуктов компании - а именно TeamCity. Отрисовка полной картинки на тот момент занимала у нас порядка 40 минут, поэтому идея приспособить наших build-агентов для тестирования разных префиксов казалась очень заманчивой. Так что он завернул наш рендерер в Ant'овскую таску и настроил билд-конфигурацию для того, чтобы гонять её на агентах.

Остаток субботы мы потратили на попытки разобраться с шифром. Получить какой-то результат из встроенного крекера нам не удалось (видимо, мы неправильно поняли, откуда взять the integer 0 encrypted with the key), поэтому мы решили реализовать алгоритм и написать перебиралку ключей на Java. Толку от этого было, впрочем, не больше - видимо, по той же причине. Так что настроение к концу рабочего дня в субботу (то бишь, пол-четвёртого утра) у нас было не ахти.

to be continued...
2014-04

ICFP Postmortem: Team ryba, part 2

(начало здесь)

Итак, как гласят логи нашего Subversion, после обнаружения очень интересной картинки мы продолжали ковырять интерпретатор. Майк продолжал заниматься оптимизациями интерпретатора DNA, Лёша переписывал алгоритм flood fill с рекурсивного на итеративный, а я тем временем делал структурированную дампилку выполняемых RNA-команд, которая вместо отдельных команд mark, move и задания цветов печатала координаты и цвета рисуемых линий. Роман же засамбитил на сервер второй из префиксов с интересной картинки, и выяснилось, что он включает свет. Этого оказалось достаточно, чтобы обеспечить нам целых полтора процента выживания и вывести нас в top 20. Из него мы, кажется, не выпадали ни разу до самого конца конкурса (даже когда он сократился до top 15).

Пока Майк продолжал заниматься оптимизациями, я пытался найти багу в текущей имплементации, из-за которой мы не проходили последний шаг self check. Разбираться в этом было на редкость тоскливо. Даже когда мне удалось выяснить, что на 28й итерации мы продалбываем кусок DNA в самом хвосте, который потом безуспешно пытаемся найти на 140й итерации, понять, на какой именно из 28 итераций мы делаем что-то не так, шансов было мало. Совсем было отчаявшись, я решил написать альтернативную реализацию на Haskell, про который до этого читал книжку, но писать ничего не пробовал. Увы, попытки быстро-быстро изучить незнакомый язык полвторого ночи оказались практически безуспешными, и то, что очередная оптимизированная Майковская имплементация начала полностью проходить self check сама по себе, оказалось большим облегчением.

(YourKit, кстати, наше всё. Иметь мощный и знакомый инструментарий помогает очень здорово. А вот с Subversion всё было не очень гладко - для всяческих экспериментов народ постоянно дописывал и комментировал кусочки кода примерно в одних и тех же местах, постоянно приходилось резолвить конфликты при мёрже, и, кажется, пару раз какие-то изменения терялись. Заодно я пронаблюдал пару трудновоспроизводимых багов в идейской svn-интеграции - но разбираться подробнее времени не было совсем.)

Дальнейшие несколько часов были, наверное, самыми увлекательными во всём контесте. Наконец-то правильно работающий интерпретатор позволил нам отрендерить последний из имеющихся префиксов и получить инструкции по навигации по хелпу. Куда и как запихивать номера страниц, Майк понял быстро, и мы смогли получить индекс страниц в хелпе и все перечисленные там страницы (кроме тех, которые были помечены заманчивым словом encrypted).

(Олег тем временем, уже сидя дома, выложил реализацию интерпретатора на .NET, но наша часть команды никакой пользы из этого извлечь не пыталась.)

Страничка про security features вызвала у меня бурный энтузиазм "о-о, это подстановочный шифр, дайте же я скорее его разгадаю!", и я бросился руками восстанавливать таблицу подстановки, так до самого конца и не сообразив, что шифр этот всего лишь ROT-13. Тем не менее, основное время ушло не на расшифровку, а на то, чтобы набить ручками два с половиной килобайта бессмысленного текста. (Другой народ успел аж OCR-утилитку написать, а мы всё по старинке, ручками...) Расшифрованный текст, как оказалось, описывал некий алгоритм шифрования.

Куда более многообещающей оказалась страница 42, содержащая список генов. Точнее, его маленькую часть. :) Но пока Майк перебирал не перечисленные в каталоге номера страниц в надежде найти ещё что-нибудь интересное, я сообразил, что первая строчка в списке генов (AAA_geneTablePageNr) очень похожа на переменную, и её значение не так сложно поменять. Следующие полчаса ушли на то, чтобы отрендерить остальные 13 страниц списка. (Хорошо Майку - он на своём четырёхпроцессорном Mac Pro запускал по 4 рендера параллельно, а я-то всё на ноуте своём ковырял, он хоть и Core 2 Duo, но больше одного рендера тянул с трудом.)

Ещё одна страничка из хелпа научила нас запускать гены из таблицы поштучно, чем мы и воспользовались для того, чтобы отрендерить пару описаний старых ICFP и ещё одну страничку хелпа.

И хотя спать всё ещё практически не хотелось (без всяких стимуляторов - за всё время контеста я выпил всего одну банку ред-булла и чашки 4 кофе), было уже пол-седьмого утра, и мы решили расползаться по домам.
to be continued...