Gynvael Coldwind
2016-04-18 01:46

Rage Against The Machine (RE250) - Plaid CTF 2016
Czyli inżynieria wsteczna sztucznej inteligencji.

Dwie godziny temu skończył się Plaid CTF - podsumowanie wrzuciłem już w poprzednim poście na moim FB. Było sporo ciekawych zadań, natomiast najciekawszym i najbardziej oryginalnym (wg mnie oczywiście) było Rage Against The Machine.
(jest dość późno - prosiłbym o wybaczenie literówek)

W ramach tego zadania otrzymywało się się krótki skrypt w Pythonie, który de facto odbierał od nas obrazek 320x240 RGB i podawał go wcześniej przyuczonej, wielowarstwowej sieci neuronowej (korzystając z http://keras.io/ oraz https://www.tensorflow.org/), która sobie nad nim "rozmyślała" i zwracała jedną liczbę od 0 do 1 - tym bliżej jedynki, im bardziej "zaznajomiona" była sieć z elementami znajdującymi się na danym obrazie (w dużym skrócie i uproszczeniu).

Celem zadania było znalezienie takiego wejściowego obrazu, na który sieć zareagowałaby zwróceniem wartości 0.99 lub większej.

Przyznaję, że miałem sporą zagwozdkę jak się za to zabrać - w końcu to trochę problem typu "masz tu mózg, powiedz jaki film najbardziej lubił jego właściciel" ;)

Ostatecznie wymyśliłem dwa sposoby:

  1. Przeczytać kilka papierków naukowych o analizie sieci neuronowych i wnioskowaniu na podstawie wag poszczególnych neuronów.

  2. Wrzucić w sieć wszystkie obrazki, które znajdę na dysku i liczyć, że na któryś zareaguje jakimś lepszym wynikiem niż 0.0000000000000000000001.

Było po północy, więc zdecydowałem się jednak na to drugie rozwiązanie ;)

Po zorganizowaniu kilku automatów do konwersji obrazków do oczekiwanego formatu oraz wrzucania ich w sieć, i po poczekaniu jakichś 10 minut (skrypt chodził na linuxowek VMce więc szybko nie było - nie udało mi się wszystkich zależności zainstalować na Windowsie, a nie chciałem w tamtym momencie z tym walczyć) okazało się, że sieć neuronowa lubi (tj. daje wynik większy niż 0.1):

  • obrazek planety w kosmosie na tle jakiegoś pyłu (0.55)
    oraz
  • zdjęcie gałęzi klonu palmowego z gustownym bokeh (0.66)

Obie grafiki wrzuciłem w google images i kazałem mu szukać podobnych wizualnie obrazów, które następnie też wrzuciłem w sieć. Większą część z nich sieć odrzuciła, ale kilka kolejnych zdobyło całkiem sporo punktów:

  • fioletowy kwiatek z bokeh (0.68)
  • las jesienią (0.69)
  • zdjęcie gałęzi z czerwonymi kuleczkami (nie, nie była to jarzębina; nie wiem co prawdę mówiąc) (0.75)
  • motyl na kwiatku (0.88)

Tematyka była mniej więcej spójna - natura, w większości zdjęcia z bliska, ale trudno było o jeden konkretny temat - tu jakieś gałązki i liście, tam motyl i kwiatek, a tu planeta i czerwone kuleczki na drzewie. Wpadłem więc na pomysł, że zrobię z tego prosty kolaż, tj wybiorę cztery najwyżej punktowane zdjęcia ("ulubione zdjęcia sieci" ;) i wrzucę je na jeden obrazek na siatkę 2x2. Na ten eksperyment sieć zareagowała bardzo pozytywnie zwracając wynik w okolicy 0.95!

Idąc tym tropem stwierdziłem, że mogę zaimplementować inny algorytm z grupy wiązanej ze sztuczną inteligencją, tj. algorytm genetyczny/ewolucyjny (lub coś w tym guście), który będzie:

  1. Wybierał wymiar kolażu (2x2, 1x2, 1x3, 2x1, 3x1).
  2. Losował odpowiednią ilość zdjęć z tych wysoko punktowanych.
  3. Łączył je w jedno i zmieniał jego wielkość do 320x240 (Python Image Library się kłania).
  4. Wrzucał wynik w sieć neuronową.
  5. Jeśli wynik będzie wyższy niż 0.90, obrazek będzie dodawany do wejściowej kolekcji (a inaczej będzie odrzucany).

Algorytm sobie leciał, a ja w międzyczasie szukałem innych "podobnych wizualnie ale innych" zdjęć i wrzucałem je w sieć. Bez lepszych rezultatów.

Po około 15 minutach zaczęło się pojawiać coraz więcej kolaży powyżej 0.95, a kilka minut później magiczna bariera 0.99 została przekroczona (patrz zdjęcie załączone do tego posta) :)

Ostatecznie aby zgłosić rozwiązanie należało również wysłać tzw. proof of work; polega to na tym, że od serwera dostajemy prefiks (krótki string) oraz informacje, że należy zwrócić taki ciąg znaków, który, po doklejeniu do prefiksu i policzeniu MD5, da sumę, której pierwsze trzy bajty będą zerowe (oczywiście to może być też sufiks, SHA1, czy dwa ostatnie bajty będące ustawione na 0x13 0x37 - jest tu sport dowolność). Z uwagi na obecność prefiksu/sufiksu typowym rozwiązaniem jest napisanie brute force, który tak długo będzie próbował kolejne ciągu, aż w końcu trafi na taki, którym spełnia dane założenia i można go wysłać do serwera. Proof of work ma na celu uniemożliwienie zbytniego obciążenia serwera (co mogłoby przeszkadzać innym graczom w rozwiązywaniu zadań) poprzez zmuszenie gracza do wykonania u siebie obliczeń, które trwają zazwyczaj od kilkunastu do kilkudziesięciu sekund. Stosuje się go jedynie w przypadku zadań, które same w sobie "zjadają" dużo czasu procesora.

Dodam, że tak naprawdę nie musiałem prawie zupełnie patrzeć na Proof of Work - dostałem od masakry (którego możecie kojarzyć z moich livestreamów, gdzie jest moderatorem; http://masakradev.pl/) gotowy kod, który wszystko liczył i zwracał mi odpowiedni ciąg.

I tak oto wpadło 250 punktów. Dodam, że zadanie rozwiązaliśmy jako trzecia drużyna, a do końca CTFa zostało rozwiązane ledwo przez 20 zespołów.

Po rozwiązaniu zadania porozmawiałem chwilę z Tylerem - kapitanem PPP i autorem zadania. M.in. zapytałem go na czym uczył sieć - ku mojemu zaskoczeniu dostałem odpowiedź:

"rambutans"

Jagodzian rambutan to owoce drzewa z tej samej rodziny co liczi (a przynajmniej tak mówi wiki i kilka osób z DS). O ile nie przypominają za bardzo tego co pojawiło się na moich obrazkach, to pewne cechy wspólne można tam znaleźć. Cóż - taka natura sieci neuronowych :)

Ponadto dowiedziałem się, że tego typu zadania można również rozwiązać metodą gradientu prostego, choć musiałbym tu sporo poczytać by wiedzieć jak to użyć.

I w sumie tyle ;)
GG

grzesiek51114

@Gynvael Coldwind: Jak zobaczyłem Rage Against The Machine to się zacząłem zastanawiać czy aby nie chcesz nam zrecenzować ich jakiejś najnowszej płyty etc. Od razu zacząłem zastanawiać się czy może nie reaktywowali zespołu hehe :D No ale kiedy zacząłem czytać dalej to przekonałem się, że chyba o muzykę tutaj nie chodzi.........

Westen

@Gynvael Coldwind: Tak się zastanawiam czy zwracany wynik zależał tylko od ilości danych kolorów (tj. czerwony, zielony, pomarańcz?) czy figury na nim przedstawione tez grały rolę. Jeśli tylko kolor to czy po wygenerowaniu obrazu z losowo rozmieszczonych kropek z odpowiednimi kolorami algorytm by zwrócił powyżej 0.99?

Gynvael Coldwind

@Westen: Dobre pytanie. Patrząc po tym, że sieć jest wielowarstwowa, wnioskowałbym że kształty były bardziej istotne niż kolory. Ale to takie wróżenie z fusów, żaden ze mnie ekspert od sieci neuronowych.

cr019283

@Gynvael Coldwind: ja akurat wybralem opcje 1) i gdyby nie prywatne ograniczenia czasowe to moze dalbym rade to skonczyc. W kazdym razie dobrze wiedziec ze blackboxow tez dalo sie to zrobic.

Shalom

@cr019283: I byśmy się zmieścili w top 10 :P tak samo jakbym skończył to moje radioaktywne crypto. A tu zawsze na koniec braknie czasu ;] Ale podejście Gyna niezłe :D

Gynvael Coldwind

@Shalom @cr019283: Co tu dużo mówić, mam bogatą historię bycia leniwym na CTFach i chodzenia na skróty ;)