Рандомизация адресного пространства (Address Space Layout Randomization, сокращенно ASLR) — это механизм обеспечения безопасности, встроенный в популярные операционные системы. Его суть сводится к рандомизации виртуальных адресов памяти различных структур данных — расположение в памяти целевой структуры сложно предугадать, поэтому шансы на успешную атаку значительно снижаются. Ранее в нашем блоге мы рассказывали об устройстве ASLR на примере ОС Windows 8.

В середине октября 2016 года группа американских исследователей информационной безопасности из Калифорнийского (Риверсайд) и Нью-Йоркского (Бинхемптон) университетов опубликовала описание техники атаки, которая использует для обхода ASLR ошибку в процессорах Intel.

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

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

Если вы плохо знакомы с применением эксплойтов, вам cледует сначала прочитать мою прошлую статью про взлом игр DS с помощью уязвимости целостности стека (stack smash) в файлах сохранений.

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

^{Мы в Меге Химки, фото одного из наших тайных покупателей на независимой проверке}

Привет!
Тут рассказывали, что Мега — это невозможно. Скажем так, наш опыт показывает немного обратное. И, чтобы не плодить иллюзии, расскажу чуть подробнее.

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

У нас с весны открыт магазин в Химках, полтора года работает магазин в Нижнем Новгороде, был магазин в Меге Уфы. В декабре мы открыли ещё 7 магазинов в Мегах.

Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G:

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

Здравствуйте, уважаемое сообщество! Думаю, многим знакома такая структура данных как суффиксное дерево. На Хабре уже было описание как его построить и зачем. Если вкратце, то оно нужно тогда, когда надо много раз искать какие-то произвольные образцы X_i в заранее заданном тексте A, а строится такое дерево мучительно с помощью алгоритма Укконена (есть и другие варианты, но они предполагают еще большее количество страданий). Общее наблюдение при работе с алгоритмами таково, что деревья — это, конечно, хорошо, но на практике их лучше избегать из за серьезных оверхэдов по памяти и не очень оптимального (с точки зрения эффективности оперирования данными компьютером) расположения. Кроме того, именно в таком дереве есть еще более существенная неприятность, а именно алфавитнозависимость структуры. Для решения этих проблем был придуман суффиксный массив. О том как его строить и как использовать и пойдет в этой статье.

Материал статьи предполагает знание понятий суффикса и префикса строки, а также знание того, как работает бинарный поиск. Надо также представлять, что такое стабильная сортировка и поразрядная сортировка, а также понимание, что имеется ввиду под стабильной сортировкой подсчетом. Для некоторых частей нам понадобится знание задачи о минимуме на отрезке — Range Minimum Query (RMQ). Ну, в общем, вас предупредили: никто не говорил, что будет просто.

Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:

Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число

Решение очевидно: просматриваем числа, находим их количество K и сумму S. По условию, N=K+1, значит, сумма чисел от 1 до N будет равна (K+1)*(K+2)/2, и пропущенное число равно (K+1)*(K+2)/2-S. Если вы почему-то боитесь переполнений, то работайте с беззнаковыми числами (там переполнения не страшны — но будьте осторожны при вычислении (K+1)*(K+2)/2 :) ), или вместо суммы ищите XOR всех чисел.

Борис Бабаян о прошлом, настоящем и будущем вычислительной техники

Почти три месяца прошло с момента публикации первой части этой работы. Всё это время вызревала вторая часть и… наконец, созрела!

Как и в предыдущей части, повествование построено от лица Бабаяна. Большинство своих комментариев я оформил в виде врезок либо ссылок на интернет-страницы.

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

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

Приветствую тебя, хабрачитатель!

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

Привет, Хабр!
Ничего не писал со времен своей первой статьи, решил, что пора это исправить.

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

Ниже я даю рецензии на книжки, которые считаю очень полезными в различных разделах computer science, которые используются в геймдеве. Я намеренно опускаю книги по C++ и алгоритмам: мне кажется, эта тема уже настолько изучена и освещена, что больше про нее не стоит рассказывать.

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

А какие книжки нравятся вам?
Также в комментах можете писать, на какие темы вам были бы интересны посты.

Моя трёхлетняя дочка София в последнее время частенько упоминает «ноль», например, в таком контексте:

— Соня, вот ты вроде сначала не послушалась, а затем послушалась, что же получается?..
— Ну… ноль!

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

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

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

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

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

По крайней мере, таков план.

Но как же именно вам, как разработчику игры, отрендерить такой эффект?

Не знаю, как у вас, но у меня любимая часть интервью — логические задачи.
Довелось пройти немало собеседований на вакансию разработчика, поэтому набралась небольшая коллекция.
Спешу поделиться с вами!

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

Несмотря на огромную популярность аппарата графических моделей для решения задачи структурной классификации, задача настройки их параметров по обучающей выборке долгое время оставалась открытой. В своем докладе Дмитрий Ветров, рассказал об обобщении метода опорных векторов и некоторых особенностях его применения для настройки параметров графических моделей. Дмитрий – руководитель группы Байесовских методов, доцент ВМК МГУ и преподаватель в ШАДе.

Видеозапись доклада.

План доклада:

• Байесовские методы в машинном обучении.
• Задачи с взаимозависимыми скрытыми переменными.
• Вероятностные графические модели
• Метод опорных векторов и его обобщение для настройки параметров графических моделей.

Сама концепция машинного обучения довольно несложная – это, если говорить образно, поиск взаимосвязей в данных. Данные представляются в классической постановке набором объектов, взятых из одной и той же генеральной совокупности, у каждого объекта есть наблюдаемые переменные, есть скрытые переменные. Наблюдаемые переменные (дальше будем их обозначать X) часто называются признаками, соответственно, скрытые переменные (T) — это те, которые подлежат определению. Для того, чтобы эту взаимосвязь между наблюдаемыми и скрытыми переменными установить, предполагается, что у нас есть обучающая выборка, т.е. набор объектов, для которых известны и наблюдаемые и скрытые компоненты. Глядя на нее, мы пытаемся настроить некоторые решающие правила, которые нам позволят в дальнейшем, когда мы видим набор признаков, оценить скрытые компоненты. Процедура обучения приблизительно выглядит следующим образом: фиксируется множество допустимых решающих правил, которые как правило задаются с помощью весов (W), а дальше каким-то образом в ходе обучения эти веса настраиваются. Тут же с неизбежностью возникает проблема переобучения, если у нас слишком богатое семейство допустимых решающих правил, то в процессе обучения мы легко можем выйти на случай, когда для обучающей выборки мы прекрасно прогнозируем ее скрытую компоненту, а вот для новых объектов прогноз оказывается плохой. Исследователями в области машинного обучения было потрачено немало лет и усилий для того, чтобы эту проблему снять с повестки дня. В настоящее время, кажется, что худо-бедно это удалось.

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

Предыстория

Доброго времени суток.
В один прекрасный летний вечер, в поисках чего-нибудь давно забытого, но увлекательного, я перебирал вещи в ящиках. Заглянув в последний, уже слегка отчаявшись, я все-таки нашел интересную вещь. Это был китайский спидометр для велосипеда. Конечно, микрокомпьютера там не было — что не удивительно (в детстве, благодаря моему любопытству, большинство разобранных мною вещей не были собраны и просто напросто были выброшены). Но это не единственная была проблема — у меня нету велосипеда. Его забрал старший брат, а сам я — катаюсь на скейте. Так и возникла идея, чем себя занять!

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

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


Вот так выглядит ленточное хранилище (наше было поменьше) и библиотечный робот (наш такой же). Китаец в комплект не входит.

Часть 1. Коробка

Помню, стояли последние дни ноября. Уже думая об окончании рабочего дня, я планировал свой вечер, когда вдруг мне сообщили, что в славном сибирском городе N у нашего заказчика сломалась ленточная библиотека. Запчасть сразу же отправили транспортной компанией, но вот уже 3 дня, как она все еще была в пути. Транспортная компания невнятно объяснялась и хмыкала в телефон, а заказчик стал не в шутку нервничать. Прогнозы были неопределенные, поэтому было принято решение везти еще одну запчасть своими силами на самолете. Сотрудник склада вручил мне габаритную коробку весом килограмм десять, обклеенную штрих-кодами и стикерами, и радостно хлопнул меня по плечу со словами: «Только не вздумай в багаж сдавать — помнут».

Коробка меня, безусловно, беспокоила, но не меньшее беспокойство мне внушал пакет с сухим молоком, который в последний момент мне вручил менеджер проекта. «У них там какие-то траблы с молочкой сейчас… из-за непогоды что ли… ребята местные просили 2 кг им привезти. Тебе ж не сложно?» — сказал он. По выражению его лица и характерному жесту ладони, как бы прикрывавшей мне рот, было ясно, как он сейчас хотел, чтобы я оказался сговорчивым или даже немым.