вторник, 6 мая 2014 г.

Longest common substring

Задачка http://acm.timus.ru/problem.aspx?space=1&num=1517 вызвала размышления на тему нахождения наибольшей общей подстроки двух строк.
В интернете удивительный чулан по этой теме. Решил упорядочить методы решения данной задачи, а заодно переписать на питоне.

№1 (решение в лоб), асимптотика выше квадрата.

Ну не совсем в лоб (перебираем все подстроки одной из строк и ищем вхождения во второй строке).

Тут оптимизация :D

def lcs_native(a, b):
    a, b = (a, b) if len(a) < len(b) else (b, a)
    pos = 0
    substr = ""
    search_str = a[:]
    while ( pos != len(a) ):
        while ( len(search_str) > len(substr) ):
            if search_str in b:
                substr = search_str[:]
                break
            else:
                search_str = search_str[:-1]
        pos += 1
        search_str = a[pos:]
    return substr

№2 (решение модное через динамику), асимптотика n*m

def longest_common_substring(s1, s2):
    m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in xrange(1, 1 + len(s1)):
        for y in xrange(1, 1 + len(s2)):
            if s1[x - 1] == s2[y - 1]:
                m[x][y] = m[x - 1][y - 1] + 1
                if m[x][y] > longest:
                    longest = m[x][y]
                    x_longest = x
            else:
                m[x][y] = 0
    return s1[x_longest - longest: x_longest]

№3 (решение самодельное через суффиксный массив), асимптотика странная

def lcs_suffix_handmade(a, b):
    result_len = 0
    result_str = 0
    text = a + b
    sarray  = sorted(range(len(text)), key = lambda i: text[i:])
    for i in range(len(text)-1):
        if sarray[i] >= len(a) and sarray[i+1] >= len(b):
            continue
        elif sarray[i] < len(a) and sarray[i+1] < len(b):
            ##print sarray[i],
            continue
        else:
            max_len = 0
            while (max_len < len(text)-sarray[i] and max_len < len(text)-sarray[i+1]):
                if text[sarray[i]+max_len] == text[sarray[i+1] + max_len]:
                    max_len += 1
                else:
                    break
            if  max_len > result_len:
                result_len = max_len
                result_str = sarray[i]

    return text[result_str:result_str + result_len]

№4 (решение читерское), асимптотика n+m

import difflib
def lcs_suffix_tree(a, b):
    seq_matcher = difflib.SequenceMatcher(None, a, b)
    res = seq_matcher.find_longest_match(0, len(a), 0, len(b))
    return a[res.a:res.a+res.size]

Исходники тут: https://github.com/n0str/python-learning/blob/master/acm/strings/lcs.py
Если найдете неточности - сообщите мне: ntpcp@yandex.ru

воскресенье, 4 мая 2014 г.

Отчет о тренировке Siberian CTF между командами Красноярска, Томска и Омска.

Задумка проводить регулярные тренировки по attack-defence CTF родилась на sibirCTF в Томске в начале апреля. Уже через месяц мы сумели силами 2 команд подготовить первую тренировку.
Суть в том, что каждая команда по очереди готовит сервисы к игре, а остальные тренируются.
Команда Yozik вызвалась проводить тренировку первой. Подготовить сервисы проблемой не является (хотя, это гораздо более серьезная задача, чем делать таски для jeopardy).
Проверяющую систему было решено писать с нуля т.к. нам не нравилась ни одна из существующих для такого рода задач.

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

Собрать удалось только 3 команды: yozik (наши первокурсники), brizzz (Омск), keva-mustang (Томск). Надеемся, что в следующей тренировке команд будет больше.


Сервисы

Сервисы мы готовили для боевых условий, в них были весьма интересные уязвимости, похожие на уязвимости сервисов в RUCTFE.
Всего 3 сервиса: "php", "perl", "python", написанные на соответствующих языках.
В сервисе php был сайт, имитирующий систему интернет-банкинга, в сервисе perl - сервер заметок, в сервисе python - сайт, позволяющий загружать и просматривать котиков :)



Регламент

Тренировка была рассчитана на 4 часа (хотя, мы осознавали, что команды не успеют раскурить все сервисы). В ходе соревнований, чек-система устанавливала в каждом раунде флаги на сервисы и проверяла наличие флагов из предыдущего раунда. В случае, если сервис работает корректно, командам начислялись 3 балла за защиту.
За каждый украденный флаг команда получала баллы по формуле: 6 / N, где N - число команд, сдавших данный флаг.
Длительность раунда 1 минута, время жизни флага - 5 раундов.

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

Уязвимый образ

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

Фейлы

Теперь о самом важном, для чего все тренировки и проводятся :)
1) Задержка старта игры из-за клонирования виртуалок. Тут наш косяк - стоило заполнить образ раньше и отдать его кеv'е на клонирование заранее. То же самое относилось и к самой сети, которую стоило протестировать.
Я до сих пор не понимаю, как сеть могла работать, а потом неожиданно перестать давать доступ командам на свои! образы, при этом доступ к чужим сохранялся :)

2) VPN. У keva были белые ip адреса, но строить на них игру неправильно. Однако, с vpn классически много накладных проблем. Все это нужно тестировать и продумывать архитектуру. Чего стоит только подключение моего компьютера к сети (из-за политик безопасности университета)



3) Скрипты запуска сервисов. Для каждого сервиса мы завели bash скрипт, который данный сервис перезапускал. Однако, скрипт не был рассчитан на внезапное изменение архитектуры сети в середине игры. Из-за чего, некоторые команды имели проблемы с защитой.
Не столько фейл, сколько обычная админская задача, но это же тренировка и не стоит требовать от команд знание запуска django сервера. Я надеюсь, что команды перезапуска, которые мы выложили, своевременно помогли решить данную проблему.

4) Сервисы. В сервисе php, я забыл затереть index.html, что очень почему-то помешало разбору сервиса.

5) После перезапуска игры, когда я переделывал конфиги, я перепутал команду keva и brizzz местами, в итоге, команда keva недополучала баллы за защиту где-то 10 минут. Эта ошибка была устранена, но она также сказалась на команде brizzz, которая была удивлена, когда у них сервисы резко легли (хотя, они и не работали).

Что получилось хорошо

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

2) Администрирование. keva сумела очень быстро переключить игру на внешние ip адреса, когда с VPN что-то произошло :) И в целом, все было доступно быстро и удобно.

Что дальше

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

Статистика

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


Графики защиты, атаки и общего счета.

DEFENCE
ATTACK
SUM

Атаки были только по сервису PHP.
Хотя, в каждом из 3 сервисов было по 3-4 уязвимости.

БД игры, где можно посмотреть общую статистику или же (если кто хочет) реализовать визуализацию игры. http://yadi.sk/d/WkvOzxDkNycGH

Исходники проверяющей системы: https://github.com/n0str/checksystem
Мы приглашаем всех принять участие в ее разработке. Ниша нашей чек-системы - создание условий для простого проведения локальных тренировок командами.

Спасибо

Спасибо команде keva за администрирование и полную поддержку (они придумали все эти тренировки).
Спасибо командам brizzz из Омска, keva из Томска и yozik из Красноярска за участие и поддержку.
Спасибо statos за сервис php.
Спасибо kenny за сервис python.
Спасибо kwisatz Haderach за сервис perl.