Долгий апогей сорванной резьбы

12:44pm: Flip A Coin
Пока ждал брата в Цюрихе, повертел в руках местную валюту и заметил любопытную деталь. Ниже фотография двух пятифранковых монет 1968-го и 1982-го годов выпуска.



У второй обе стороны имеют одинаковую направленность, то есть голова смотрит туда же, куда и цифра 5, а у первой они друг относительно друга перевернуты. Таким образом более старая рассчитана на вертикальное направление переворота, а более новая на горизонтальное. Горизонтальный переворот для современного человека действительно привычнее, видимо по аналогии с перелистыванием страниц книги. Но с точки зрения моторики крутить в пальцах мелкие симметричные предметы по-прежнему удобнее вертикально. Любопытный пример, как со временем привычка может победить удобство в государственном масштабе :)
-----За 4 месяца reversed-java.com обработал 537000 класов общим размером 1640 MB. Более полутора гигабайт кода - не думаю, что какой-либо еще декомпилятор тестировался на таких объемах. Тривиальные баги (надеюсь) все выловлены, теперь идет уже настоящий hardcore и всякая разная эзотерика.
-----Пираты набрали 2% на выборах в парламент - меньше, чем надеялись, но больше, чем опасались. Тем более, что были допущены к участию только в 15 из 16 земель. В результате пиратская партия занимает сейчас 6-ое место по количеству избирателей и 7-ое по количеству членов, число которых перевалило за 10000 (мой номер 5211). А если учесть и "качество" голосующих за них (молодежь - студенты, научные работники, программисты), то вывод очевиден: правильным путем идем.

9:06pm: Epic Fail


Так начинания, вознесшиеся мощно,
Сворачивают в сторону, теряют имя действия — какой срам.
(Б.Г.)

Поскольку официальное объявление вчера наконец прозвучало, то можно теперь и собственные соображения высказать. Вероятно всем уже известно, что Либрусек заключил полюбовное соглашение с Литресом. На подробностях останавливаться не буду, их можно узнать на сайте Либрусека, где со вчерашнего дня кипит не всегда цензурное обсуждение. Вкратце: запрет скачивания/добавления книг на месяц + реклама в онлайне по типу литресовской.

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

1) Реакция библиотекарей

Имен называть не буду, незачем, так как интересны именно типажи. Библиотекари довольно четко разделились на три группы:
- некоторые, самые принципиальные и совестливые, незамедлительно подали в отставку. Почет им и уважение! А также белая зависть.
- небольшая группка встретила перемены верноподданным визгом, в надежде упрочить свою маленькую власть и добыть кусочек нового пирога. К счастью их мало. К несчастью вред они наносят уже сейчас значительный. Заповедник таких персонажей был на Альдебаране перед его падением, кто помнит - поймет.
- основная масса стиснула зубы и молча привыкает. Слишком много труда и времени вложено в Либрусек. Но самое главное - мы, в отличие от, действительно любим книги, любим до одури. Очень трудно решиться бросить их.

2) Причина матерных воплей "нас предали"

Спорщики, мнящие себя особенно рассудительными и выдержанными, в ответ клеймят жадных детей, любителей халявы и защищают право автора проекта делать с ним, что душе угодно. И вообще, не нравится - dann geh doch nach drüben!* Но если задуматься, откуда же все-таки берется это стойкое ощущение обмана и предательства? Кто и что предал?

Ответ простой: нет дыма без огня и обман действительно имеет место быть. Судя по modus operandi, решение искать союза с Литресом не было спонтанным, а вынашивалось очень давно, как бы даже не с самого начала. А теперь представим себе, что автор с самого начала озвучил бы замечательную цель - набрать побольше книг, пользователей, известности и пойти с ними на поклон к Литресу. Реакцию легко предсказать, правда? Либрусек сдох бы не родившись и ни один идиот не стал бы с ним работать. Во избежание такого скоропостижного конца пришлось пару лет маскироваться под пиратов, изобретать символику, заманивать пользователей светлой идеей совместного труда на благо свободной книги.. "раскручиваться" одним словом. Ну а теперь можно и сбросить маску, надоела. Вот только люди почему-то чувствуют себя обманутыми простаками.

Очередной epic fail, очередная скурвившаяся революция. Очень будет недоставать тех времен, когда библиотека активно строилась и вокруг нее бурлила книжная, одновременно демократичная и сплоченная вольница. Оставим пока политику и сосредоточимся на книгах, будем читать, скачивать, разбирать и приводить их в порядок. И ждать появления нового ростка :) Если кому-то нужна заблокированная книга раньше назначенного Литресом времени, пишите в личку.

Да, к библиотеке Genesis вышесказанное не имеет отношения. Ее курируют сейчас люди с несколько более твердыми моральными устоями. Что в очередной раз доказывает превосходство научников/технарей в самых разных областях деятельности ;)
________________________________________
* Ну и пошел на ту сторону! - Стандартное высказывание старшего поколения немцев во время холодной войны, если кто-то осмеливался критиковать что-то в ФРГ. Утратило смысл после выступлений 60х, когда молодежь вынесла "ту сторону" на улицы.

12:32pm: 2nd Mensiversary
Прошло примерно два месяца с того момента, как Fernflower официально вышел в свободный доступ - время подвести небольшие итоги. Округляя вниз до первых трех разрядов, за это время на reversed-java.com было обработано 191000 классов общим объемом 626 MB. Исправлено большое количество багов разной степени тривиальности и приделаны некоторые дополнительные, в том числе уникальные функции. Еще раз большое спасибо всем не поленившимся прислать сообщения об ошибках и просто свои пожелания и благодарности. Не перевелись еще грамотные и дружелюбные разработчики и пользователи!

Планы на следующее время:
1) Дальнейший вылов багов, разные мелкие улучшения (for each, debug information и т.д.)
2) Деобфускация урезанных/расширенных try-catch областей (как например в Opera Mini)
3) Единая и более осмысленная смеха наименования переменных и доступа к типам
4) Переименование (обфусцированных) классов, полей и методов по заданной схеме

Кроме того, в скором времени станет доступен плагин для Eclipse.

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

11:03am: downtime
reversed-java лежит.
( Причина )
Идиоты. Вот так взяли и обнаружили с чистого неба "тяжелые повреждения" файловой системы. Обещают к вечеру исправить, посмотрим..

6:18pm: The Dreaded Irreducibility
С самого начала было ясно, что проблемой несводимых CFG¹ придется рано или поздно заняться вплотную. Оставить ее нерешенной означает подтвердить право современных обфускаторов (см. http://stiver-rus.livejournal.com/3355.html) на жизнь и признать, по крайней мере частично, несостоятельность декомпилятора. Очень неприятная перспектива. Но время шло, а умные мысли не приходили ни в голову, ни куда-либо еще, и хитрые графы продолжали висеть грозовой тучкой где-то на краю сознания.

Правильно старые бюрократы говорят: если проблему достаточно долго мариновать, то она решится самостоятельно. Похоже мне повезло. Напомню, что несводимость - это свойство CFG, определяющее в том числе возможность декомпиляции. В частности CFG не сводим <=> код не может быть выражен на языке, не имеющем произвольных переходов goto. С другой стороны у нас есть чисто графическое определение, данное еще в 1974 году в работе "Characterizations of Reducible Flow Graphs" (M.S.Hecht, J.D.Ullman)²:
( Рисунок под катом )
Граф является несводимым тогда и только тогда, когда он содержит показанную на рисунке (а) фигуру. Волнистыми линиями обозначены произвольные пути с тем единственным условием, что они различны, т.е. не содержат общих узлов³. А теперь собственно решение. Как выяснилось, мой алгоритм разложения CFG сам по себе доводит несводимые графы до формы базового треугольника, сокращая волнистые пути до прямых ребер. Структура (а) превращается в (b), а дальше дело техники и треугольник разрывается удвоением любого из симметричных узлов (см. (c), где C' - копия С). От меня потребовалось сейчас всего лишь написать дополнительную процедуру копирования узлов - операция если и не тривиальная, то достаточно близкая к таковой.

Реализацию проверил на нескольких примерах, в том числе на процедуре расшифровки строковых констант из ZKM. Все испытания прошли успешно, желающие могут скачать тестовый класс и посмотреть на результат: http://www.reversed-java.com/download/irredcfg.zip Получившийся код вполне рабочий и правильно расшифровывает все строки.

Таким образом решилась еще одна из основных проблем декомпиляции/деобфускации. Думаю нет нужды уточнять, что Fernflower - первый декомпилятор с подобной способностью :) Не только по отношению к Яве, но и вообще. Официального анонса пока не было, тем не менее функция уже доступна для теста в онлайновой версии. Кроме того приделал по заявке kosiakk декомпиляцию assert'ов, изменил дизайн страницы, прикрутил к новостям RSS, исправил разнообразные баги и т.д. и т.п.

Кстати упомянутой статьи нет в свободном доступе, я ее скачивал с ACM. Думаю сделать на reversed-java раздел "Библиотека" и сложить туда полезное чтиво по теме декомпиляции, какое вспомню и попадется под руку. Если будут рекомендации или пожелания, постараюсь прислушаться.

____________________________________________________________________________________________________________________________
(1) русский перевод control flow graph?
(2) определение и описание несводимых CFG - по-моему единственный достойный результат теории декомпиляции за последние 40 лет.
(3) disjoint - как одним словом?

2:45pm: Civil Duty
Несмотря на проливной дождь сходил и успешно проголосовал. Естественно за пиратов, как всякий здравомыслящий человек. Удивило количество партий в списке - аж 31 штука, где пиратская на 29-ом месте. Два последних занимают партии пенсионеров, не очень понятно чем друг от друга отличающиеся.

12:59am: Аналитический декомпилятор Fernflower
Как было обещано некоторое время назад, официально объявляю о начале открытого бета теста моего декомпилятора. Ниже следует краткое описание и ответы на основные вопросы:

( <--- Объемный текст ---> )

8) Выводы и манифест

Со своей стороны могу гарантировать - с поправкой на force majeure - следующее:

a) Декомпилятор всегда будет в бесплатном доступе
b) Буду поддерживать, исправлять баги и развивать Fernflower по мере сил
c) Если в какой-то момент я пойму, что больше не могу уделять проекту необходимое количество времени, то сразу открою его под GPL-подобной лицензией независимо ни от каких внешних обстоятельств

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

9) Связь

Со мной можно связаться:

- через www.reversed-java.com
- через журнал
- через fernflower (dot) decompiler (at) gmail (dot) com

Как кому удобнее.

12:50am: Mission Accomplished


Ну вот исчезла дрожь в руках
Наверх, наверх
Ну вот сорвался в пропасть страх
Навек, навек
Для остановки нет причин
Иду, скользя
И в мире нет таких вершин
Что взять нельзя

Ну вот в общем-то и все. Святой Грааль джаваистов последних 13-ти лет найден, добыт и приспособлен к делу. Конечно это всего лишь первый шаг на пути пока еще неизвестной длины - слишком многое предстоит еще сделать, доделать, а зачастую и переделать заново, пыхтя и выражаясь по адресу самого себя полгода назад. Практически непаханной остается теория, где одной лишь задачи нормализации уже хватит как минимум на очень хорошую дипломную. Но зато шаг широкий, устойчивый и в верном направлении :) Проблема декомпиляции Явы таким образом решена.

Выше поместил сводку со всей полезной информацией (дубль в сообщество ru_java)

9:06pm: Early Adopters Only :)
Желающие уже сейчас потестировать Fernflower могут это сделать по следующему адресу:

URL: http://www.reversed-java.com
Username: fernflower
Password: beta

Страница все еще в процессе обтесывания, но пользоваться вроде бы можно. На следующей неделе надеюсь опубликовать полное "официальное" сообщение со всей необходимой информацией. Пока же надо убедиться, что спешная и незапланированная перестройка самостоятельного декомпилятора под вызов с вебсайта прошла успешно. К тому же это мой первый опыт с Wicket (весьма приятная вещь кстати). Так что стабильность пока не гарантируется, но критика принимается ;)

Если по адресу выше вылезает сообщение о пустом домене, придется подождать, пока обновятся записи DNS. Сегодня днем переключил, может занять несколько часов.

Добавлено: поскольку возникли недоразумения, уточняю - доступен именно _декомпилятор_. Модулей деобфускации он пока никаких не содержит. Задача состоит в правильной декомпиляции любого необфусцированного кода.

9:08pm: Our world, dumb and dangerous


Четвертые сутки пылают станицы..

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

Но этого мало. Как же, ведь остались еще несломленные провайдеры помельче, которые с самого начала послали правительственных идиотов туда, где не светит солнце. Поэтому нужно закрепить достигнутое законом. Как стало известно сегодня, в рабочей версии этого закона предписывается: 1) фильтровать не только страницы черного списка, но и все на них ссылающиеся и упоминающие 2) фильтровать страницы независмо от страны (сначала хотели сделать поблажку для внутриевропейских адресов) 3) все попытки доступа к запрещенным страницам протоколировать и передавать IP управлению криминальной полиции. Как ни удивительно, но законодатели вполне отдают себе отчет, что их творчество нарушает Конституцию. И плевать - в черновике ничтоже сумняшеся заявляется об урезании соответствующего параграфа Конституции. Действительно, делов-то.

Честное слово, я не понимаю происходящего, как не понимает его никто из моих коллег, друзей и знакомых. За последние годы правительство все дальше и дальше сходит с резьбы и те, кто еще находит в себе силы следить за его взбрыками, постепенно просто теряют дар речи. Кто-то что-то говорил про несоблюдение прав человека? Цензуру интернета в бедном несчастном Китае? Ха.

"A bunch of mindless jerks who'll be the first against the wall when the revolution comes" (Douglas Adams, "The Hitchhiker's Guide to the Galaxy")

10:50pm: книжное
Доделал и выложил на Либрусек "Russia After Stalin", Isaac Deutscher (1953, sec.ed.) В сети эта книга обрела несколько нелепую известность как первоисточник долгое время приписываемой Черчиллю цитаты:

"The core of Stalin's genuine historic achievement lies in the fact that he found Russia working with the wooden plough and left her equipped with atomic piles."

12:16am: ...
Занесло меня сегодня более или менее случайно на местную подвальную барахолку, где - опять-таки случайно - удалось найти довольно любопытный предмет. Это настольный колокольчик (см. фото), примерно такие можно увидеть на стойке старых отелей или в фильмах о них.
( Фото )
Время и место изготовления определить невозможно, но судя по стертому металлу возраст у него приличный. Орнамент изображает четырех евангелистов и поверху выбиты их имена на латыни "S.MATHEUS S.MARCUS S.LUCAS S.JOHANNES". Google нашел упоминания двух колоколов 14го века с такой надписью, значит колокольчик делался по образу и подобию полноразмерных собратьев. Символы евангелистов изображены тоже правильно и соответствуют именам, но как раз с одной интересной деталью: все четыре имеют нимб и крылья (да, даже у орла :) вторая пара крыльев), но если человек, лев и бык держат по книге, то орел остался обделенным. Про традицию изображения евангелистов с книгой мне известно, знаю и то, что Иоанн всегда упоминается последним и вообще стоит несколько особняком из-за своего Откровения (иначе Апокалипсиса). Но никогда не слышал, чтобы его из-за этого урезали в правах, то бишь в изображении. Странно, странно очень.

11:21pm: Looking for Science
Если взяться формулировать условия, необходимые для возведения какой-либо области знаний в ранг науки, то создается ощущение, что одним из них будет наличие собственных фундаментальных констант. Как это ни глупо. С действительностью отлично согласуется: у физики, химии, математики такие константы имеются. С биологией труднее, но что-то наверняка накопать можно. Зато информатика вроде бы отлично обходится без них, в очередной раз доказывая свою ненаучность :)

3:41am: Direct Decompilation Confirmed Impossible
Пусть у нас есть некий класс X, версия Явы 1.5 или выше. Тогда в общем случае невозможно правильно* декомпилировать X без изучения всех классов, на которые X ссылается.

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

10:33pm: High Music
400-летний орган в новогоднюю ночь, да в большой базилике на полную мощь, когда кажется, будто звук идет из стен и вибрирует мраморный пол - нечто совершенно изумительное. Königin der Instrumente, слушать которую - мне по крайней мере - никогда не надоедает. "Королева", так как орган в немецком странным образом женского рода. Но с другой стороны "катюша" тоже называется органом (Stalinorgel), и уж тут женский род пришелся как нельзя кстати :) Математика, ассемблер и орган - предметы явно одного порядка, хотя и нелегко объяснить их родство и его критерии. Жаль, что Hofstadter не умел как следует программировать и спасибо Stephenson'у за его sonic computer. С Новым Годом нас всех :)

11:00pm: Kurioses Kräftemessen
На ноутбуке у меня все еще стоит Eclipse 3.1, так как плагин Metrics с более новыми версиями пока не дружит. И такое ощущение, что Fernflower с EJC теперь бодаются на предмет, кто у кого больше багов найдет. За два дня отловил четыре штуки, половину которых потом нашел в официальных списках.

1) генерация недоступного кода (https://bugs.eclipse.org/bugs/show_bug.cgi?id=114894)
2) двойной каст (https://bugs.eclipse.org/bugs/show_bug.cgi?id=115693)
3) отсутствие каста после generic, например

List<String> lst = new ArrayList<String>();
(new String[1])[0] = lst.get(0);

перед lst.get(0) в коде не будет checkcast. Выглядит особенно смешно на фоне 2) - вот уж где густо, а где пусто.
4) Не понимает public класс со знаком доллара в имени

В Eclipse 3.3 все четыре вроде бы уже исправлены. Но как же здорово наконец работать с декомпилятором, которому можно доверять. После стольких лет мучений на чужих кривых поделках - благодать прямо :) Даже ошибки, и те все свои и понятные.

6:51pm: ...
По сравнению с англо- или русскоязычными программистами немцы гораздо строже относятся к комментариям в коде, не допуская в них как правило никаких вольностей. Даже просто высказывание от первого лица трудно найти (особенно в тех структурах, где я сейчас обретаюсь), не говоря уже о выражении более сильных эмоций. Тем драгоценнее немногочисленные выжившие перлы:

// Diese Datei wurde manschinell erstellt und traegt deswegen weder
// Unterschrift noch Siegel.

или

// Diese Klasse ist mein Vermächtnis an die Nachwelt.
// Es kopiert generisch VOs in VOs, damit entfällt der Umkopiercode.

Такой вот незатейливый юмор :)

11:30pm: Simplest Value Propagation
Пусть a и b переменные и имеется присваивание

a = b;

пусть где-то дальше переменная a как-то используется

System.out.println(a);

Вопрос:
1) Как выглядят необходимые и достаточные условия для замены a на b?
   1а) В целом
   1b) Именно в этом месте
2) Как выглядит эффективный алгоритм для расчета 1)?

Осмысленного и внятного ответа нет до сих пор..

1:10pm: Slow Unfolding
Постепенно и неуклонно Fernflower раскрывается :) Не так быстро, как хотелось бы, но в отсутствии дедлайна есть и свои преимущества. Тестовый класс обрабатывает без ошибок, можно переходить к более масштабным испытаниям.

Для интересующихся: класс, байткод (Eclipse 3.1) и декомпилят http://rapidshare.com/files/150811772/testclass.zip.html

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

Стоит отметить, что в области декомпиляции пока еще не существует никакого канона стандартных алгоритмов и подходов. Каждый воюет по собственному разумению, получая в награду замечательное ощущение первопроходца. Современная computer science дарит такую возможность редко и стоит она дорого.

11:16am: ...
Боты одолевают, пора учиться банить в ЖЖ. Непонятна только логика их автора - неужели он серьезно расчитывает, что его создания пройдут тест Тьюринга, пусть даже и в урезанном письменном виде?

( Upd: Отловлено )

5:18pm: So Many Books
Колхоз + еще некоторые сборники доступны в виде подраздела Либрусека: hxxp://gen[dot]lib[dot]rus[dot]ec. Еще бы теперь каталог и возможность самому добавлять/редактировать записи (т.е. по сути полная интеграция в Либрусек :)) и цены бы не было.

7:50pm: Dynamic future
Почитал спецификацию седьмой Явы, оказалось там предполагается ввести новую инструкцию invokedynamic. Вот тогда и увидим, какие инструменты развиваются и поддерживаются авторами, а какие нет :) Это вам не запрещать инструкции (как произошло в 1.6), тут без обновления полетит все разом.

11:10pm: The Paths We Choose
Не секрет, что одним из основных достоинств структурных декомпиляторов является их независимость от физического места команд в файле. Блоки могут быть перемешаны как угодно, структура и связи все равно останутся неизменными. Однако из этого не следует, что такой декомпилятор будет вообще свободен от зависимостей. Место внешних факторов занимают факторы внутренние, с - как выяснилось - довольно забавными последствиями.
( Последствия )
И даже возразить ему нечего, так как оба варианта нормально компилируются и вполне имеют право на существование.

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

3:18pm: Forever Postdominant
Наткнулся еще на одно интуитивное понятие, требующее формализации. В теории CFG используется термин "постдоминатор"(postdominator), который повсеместно определяется примерно так:

Block M postdominates block N if every path from N to the exit has to pass through block M

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

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

9:28pm: EM
Мало было WM 2006, так сейчас история повторяется с EM - от орущих и сигналящих под окнами толп не знаешь, куда деваться. Слабо вот проводить чемпионаты зимой? Только что прошли хаотическим шествием пара сотен хорватских болельщиков, перегородив улицу минут на 20. Хорошо еще, трамвай проезжал :) с ним особо не поспоришь и болельщикам пришлось убраться.