Этот топик — перевод первых двух частей руководства по написанию своего бота для Google AI Challenge.
Весь код написан на языке Python.

Шаг 1: Как избежать столкновений

План

Чтобы муравьи не сталкивались надо:
1) Предотвратить перемещение одного муравья на другого;
2) Предотвратить перемещение двух муравьев в одну и ту же точку;
3) отслеживать информацию о местонахождении всех наших муравьёв.

Поднявшаяся в этом топике дискуссия о криптостойкости многократного применения хеша над паролем (проскальзывавшая, кстати, и в других форумах), подтолкнула меня к этому немного математическому топику. Суть проблемы возникает из идеи многократной (1.000 и более раз) обработки пароля перед хранением каким-либо криптостойким алгоритмом (чаще всего хеш-функцией) с целью получить медленный алгоритм проверки, тем самым эффективно противостоящий brute force-у в случае перехвата или кражи злоумышленником этого значения. Как совершенно верно отметили хабрапользователи Scratch (автор первой статьи), mrThe и IlyaPodkopaev, идея не нова и ею пользуются разработчики оборудования Cisco, архиватора RAR и многие другие. Но, поскольку хеширование – операция сжимающая множество значений, возникает вполне закономерный вопрос – а не навредим ли мы стойкости системы? Попытка дать ответ на этот вопрос –

К написанию сей заметки меня сподвигло то, что я устал делать развёрнутые замечания на эту тему в комментариях к статьям, где в качестве части инструкции по сборке и настройке чего-либо для конкретного дистра предлагают выполнить make install.

Суть сводится к тому, что эту команду в виде «make install» или «sudo make install» использовать в современных дистрибутивах нельзя.

Но ведь авторы программ в руководствах по установке пишут, что нужно использовать эту команду, возможно, скажете вы. Да, пишут. Но это лишь означает, что они не знают, какой у вас дистрибутив, и дистрибутив ли это вообще, может, вы вступили в секту и обкурилисьчитались LFS и теперь решили под свою хтоническую систему скомпилять их творение. А make install является универсальным, хоть и зачастую неправильным способом это сделать.

Меня очень давно заинтересовала тема программирования поведения объектов в виртуальном мире. Но практические знания в этой области оставляют желать лучшего, поэтому недавно начал искать небольшой проект для вложения сил. В итоге я его нашел, благодарен гуглу и ideas4ru за анонс.

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


_{Образец того самого pdf-а — в файле сохранена структура, но подчищены все данные.}

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

Совсем скоро стартует Google AI Challenge Ants. Два дня назад уже был анонс на хабре про это состязание:
http://habrahabr.ru/blogs/sport_programming/130457/
. Для тех, у кого есть желание поучаствовать или хотя бы просто узнать поподробнее, как это делается, я написал этот «Быстрый Старт».
Из статьи вы узнаете как запустить у себя на машине игру, написать своего первого бота и запустить две копии бороться друг против друга.

Доброго времени суток!
Вам когда-нибудь хотелось узнать как устроены файлы PNG? Нет? А я все равно расскажу.
Формат PNG(Portable Network Graphics) был изобретен в 1995 году, чтобы стать заменой GIF, а уже в 1996, с выходом версии 1.0, он был рекомендован W3C, в качестве полноправного сетевого формата. На сегодняшний день PNG является одним из основных форматов веб-графики.

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

Последние несколько месяцев я работал над SDK для Android, входящим в платформу управления контентом Nuxeo. Особенно много работы было в последнее время, с приближением официального релиза SDK. Я хочу поделиться несколькими практическими советами по поводу разработки под Android, в частности тестирования и эмуляции. Уже после нескольких дней разработки я понял, что работа с эмулятором Android — не сахар, потому что он чудовищно медленный.

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

Тонкая настройка параметров Qemu не слишком помогла — скорость работы эмулятора осталась медленной, возможно именно поэтому большинство разработчиков предпочитает использовать реальные устройства, подключенные по USB.

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

Когда-то давно взбрела мне в голову идея: написать свой собственный поисковик. Было это очень давно, тогда я еще учился в ВУЗе, мало чего знал про технологии разработки больших проектов, зато отлично владел парой десятков языков программирования и протоколов, да и сайтов своих к тому времени было понаделано много.

Ну есть у меня тяга к монструозным проектам, да…

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

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

В прошлом посте мы писали о том, как Островок.ru привлёк инвестиции размером 1 млн долларов от лучших инвесторов всего за 6 недель, имея только идею.

Мы получили очень много положительных отзывов на тот пост. Но в нём был существенный недостаток: мы описывали процесс с точки зрения нашего предыдущего опыта и связей. Большинство из этих рекомендаций неприменимы к вопросу о том, как начать в России свой бизнес, не имея связей и опыта.

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

Хотелось бы поговорить с вами на актуальную нынче тему, а именно — про DDoS и методы борьбы с ним. Рядовые администраторы знают, что это такое, а вот для большинства вебмастеров это аббревиатура остается загадкой до того момента пока они на личном опыте не столкнуться с этой неприятностью. Итак, DDoS — это сокращение от Distributed Denial of Service (распределенный отказ в обслуживании), когда тысячи зараженных компьютеров отправляют на сервер множество запросов, с которыми он, в последствии, не может справиться. Целью DDoS атаки является нарушение нормальной работы сервера, а в дальнейшем — «падение» сайта или сервера целиком.

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

Сегментация изображения

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

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

С portable document format'ом не всё так просто, как DOCX или ODT, что мы рассматривали в прошлый раз, но всё же это всё ещё изначально текстовый, а не бинарный формат. Вы удивлены? Тогда давайте посмотрим на то, что там внутри. Дальше действительно много текста.

Представьте, что сейчас 1995 год и вы собираетесь совершить первую покупку в онлайне. Вы открываете браузер Netscape и прихлёбываете из чашечки кофе, пока главная страница медленно загружается. Ваш путь лежит на Amazon.com — новый онлайн-магазинчик, о которой рассказал вам друг. Когда наступает этап оформить покупку и ввести персональные данные, адрес в браузере меняется с «http» на «https». Это сигнализирует о том, что компьютер установил зашифрованное соединение с сервером Amazon. Теперь можно передавать серверу данные кредитной карты, не опасаясь мошенников, которые хотят перехватить информацию.

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

В статье «Трудности сравнения анализаторов кода или не забывайте об удобстве использования» [1] говорится о том, что сравнить между собой два инструмента не так просто как кажется, потому что помимо собственно технических характеристик анализаторов очень большое значение имеет такой параметр как удобство использования.

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

В статье показаны ошибки, выявленные с помощью статического анализатора кода, встроенного в Visual Studio 2010. Исследование проводилось на пяти open source проектах. Эти же проекты были проверены с помощью PVS-Studio. Приведены результаты сравнения этих двух инструментов.

Хотя статьи в стиле how-to и не очень комментируемые, и в основном не с положительными комментариями, однако, именно их, больше всего добавляют в закладки.
Здесь я постараюсь описать процесс установки и настройки VPN-сервера на CentOS6 с пользователями в MySQL и авторизацией через радиус для шифрованного соединения по ms-chap-v2 и mppe.

Преамбула

Откуда берутся данные статьи? Все просто. Когда мы ищем соискателей работы, например, на должность системного администратора, то после отбора кандидатов на предварительном собеседовании, состовляются тестовые задания, реализуются своими силами, а потом предлагаем их решить соискателям. Для исполнения заданий, соискателю предоставляется виртуальная машина, доступ в интернет, и определенное время. Время расчитывается просто — наша реализация *2. При этом, Вы можете считать, что все необходимые решения (how-to) можно найти на просторах интернета, однако, мы учитываем это, и поэтому не берем готовых решения, а состовляем и решаем предварительно их сами, на свежих дистрибютивах. Кстати, бывают случаи, когда мы натыкаемся на определенные проблемы при реализации (маленькие незадокументированные шалости разработчиков), и в случае, если кандидат идет правильным курсом, но попадает в затык именно на этой проблеме, подсказываем найденное нами, её решение.

В одном из наших свежих проектов команде разработчиков была поставлена задача собрать максимально реальные контактные данные о пользователях нашего сайта. Жаркое обсуждение правильных и неправильных форм регистрации, одно- и двушаговые, дополнение информации по мере пользования сайтом… Казалось поток идей не остановится. Однако ни одна из них не гарантировала, что в результате мы не получим кучу никчемных данных. Валидировать? Можно, но разве все предусмотришь? Активация учетной записи через почтовый ящик для его валидации? Но куча сервисов типа 10 Minute Mail сводят на нет эффект. К тому же, специфика проекта не позволяла слишком растягивать процесс регистрации. Решено было, что пользователь должен зайти, сделать своё дело, а потом уже активировать или нет свою учетную запись. В конце концов прозвучала фраза «А давайте активировать по SMS!». Поиск провайдеров, изучение прайс-листов и отказ от идеи взвалить обработку SMS на стороннюю контору… Стало понятно, что принимать и обрабатывать их придется самим.

За последнее время, наш сайт часто подвергается достаточно мощным DDOS атакам, к слову последняя атака была самой крупной за последнее время, размер ботнета по нашим оценкам — около 10 тысяч машин, мощность — 100 Mbits/s.

Атаку заметила даже Лаборатория Касперского, и предложила свою помощь в отражении, за что им спасибо. Правда к тому времени мы самостоятельно нашли решение, которое блокирует атаку. Собственно про это решение и пойдет речь.

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

Атака была типа HTTP Flood. Система на которой у нас работает сайт — Apache под Linux. Мы написали несколько скриптов, которые будут приведены в тексте статьи. В принципе аналогичный подход можно применять и для Windows/IIS.

Попытаюсь рассказать, какие основные шаги мы сделали для отражения атаки, и какие проблемы возникали по ходу:

Я давно хотел написать какую-нибудь сетевую игру на bash, причём желательно, чтобы управление было удобное, с клавиатуры, обычными курсорным клавишами. Вообще, тема интерактивного взаимодействия в bash глубже, чем «введите число, нажмите „Enter“» не раскопана. Мне пришлось всё изобретать и исследовать самостоятельно. Я очень старался найти что-то похожее по уровню интерактивности, но не нашёл.

Поскольку тонкости управления с клавиатурой съели очень много моего времени, я не стал заморачиваться с тонкостями совместимости, поэтому игра тестировалась только под Mac OS X, есть ненулевая вероятность, что она заработает и под Linux и уж точно её можно допилить там до рабочего состояния.

Для работы игра требует наличия nc (aka Netcat) и терминала с поддержкой 256 цветов (под Mac OS рекомендую iTerm2). При наличие интереса к игре, допилю до терминала на 16 цветов и /dev/tcp. Кстати начал выкладывать все свои шел-поделки на ГитХаб.



Так как игра сетевая, у неё требуется указать два параметра, о которых она расскажет, если её запустить без них. Первый — адрес машины противника, второй — порт. Порт выбирается одинаковым на обеих машинах. Игру можно запустить и на одной машине, в двух консолях (на скриншоте как раз такой случай).

Играть просто — в каждый момент времени активна только одна доска (на скриншоте — правая, у неё буквы и цифры вокруг доски ярче), на активной доске курсор двигается курсорными клавишами — ←, →, ↑ и ↓, взять фигуру и поставить её на доску — по клавише пробела или Enter. Как только вы поставили фигуру на доску, ход переходит к сопернику. «Съесть» фигуру соперника проще простого — достаточно поставить свою фигуру на чужую. В игре есть защита — нельзя «съесть» свою фигуру.

Ничего помимо этого в игре нет — не производится правильность контроля ходов, нет проверки на завершение игры, можно даже ходить фигурами соперника. Было очень сложно придумать как обрабатывать нажатия в shell, так что остальное сделать я просто не успел, не поместилось в формат «игрушка за вечер».

Я постарался снабдить свой код комментариями и писать достаточно структурировано, чтобы можно было разобраться как всё работает самостоятельно.

Однажды заинтересовался, содержимым стека функции main процесса в linux. Провел некоторые изыскания и теперь представляю вам результат.

Варианты описания функции main:
1. int main()
2. int main(int argc, char **argv)
3. int main(int argc, char **argv, char **env)
4. int main(int argc, char **argv, char **env, ElfW(auxv_t) auxv[])
5. int main(int argc, char **argv, char **env, char **apple)

argc — число параметров
argv — нуль-терминальный массив указателей на строки параметров командной строки
env — нуль-терминальный массив указателей на строки переменных окружения. Каждая строка в формате ИМЯ=ЗНАЧЕНИЕ
auxv — массив вспомогательных значение (доступно только для PowerPC [1])
apple — путь к исполняемому файлу (в MacOS и Darwin [2])
Вспомогательный вектор — массив с различной дополнительной информацией, такой как эффективный идентификатор пользователя, признак setuid бита, размер страницы памяти и т.п.

Далее о том как получить массив вспомогательных значений для i386 и x86_64, а также об остальном содержимом «сегмента» стека.