Vorgurakendused 2 prax 1 2014

Allikas: Lambda

Zombie robot attack

P2Net - P2P botnet

NB! See on 2014 aasta praksi arhiiv, mitte hetkel kehtiv praks!

UUS: 16. oktoober tulge kohale, kui tahate katsetada oma P2Net implementatsiooni ühilduvust teistega. 23. oktoober selleks tõenäoliselt eriti aega pole, kuna kaitsmistel on prioriteet.

Ülesandeks on ehitada P2P rakendus P2Net programmide (käsurea kujul) käivitamiseks võõrastes masinates ja rehkendustulemuste kättesaamiseks, mis teeb laviinitaolise otsingu mööda P2Net klient/servereid, isetehtud P2P mehhanismi abil.

Kasutajaliidese hea kvaliteet ei ole praksis oluline.

Huvi korral võid vaadata ka veidi sarnaseid vanu ülesandeid 2013 aasta arhiivis ning sealt edasi vanemaid.


Üldkirjeldus

P2Net võimaldab:

  • kasutajal käivitada võõrastes masinatest käsurea.
  • saada tagasi käsurea rehkendatud tulemus(tekst/binary vms blob).
  • idee on selle peale ehitada mingi rakendus, näit:
    • mingite mahukate arvutuste jaotamine masinate vahel (#Näiterakendus)
    • web scrapingu (näit google otsingu) load balancing
    • kaugadministreerimine
    • ...

Rakenduse tegemine P2Net protokolli peale on ka praksi osa.

Võõraste masinate leidmiseks kasutab P2Net järgmist viisi:

  • Saadab tema oma masinas oleva faili machines.txt masinatele käsu. machines.txt sees on masinate ip ja pordid json listina kujul 
[["11.22.33.44","2345"],...,["111.222.333.444","23456"]]
  • Samamoodi saadab käivitus-päringu P2Net startlehel http://dijkstra.cs.ttu.ee/~priit/P2Net.txt olevatele masinatele (startlehel on plaintekstina eelmises punktis näidatud formaadis json-fail)
  • Kui mingi masin saab minu päringu-käsurea kätte, siis ta paneb selle kohapeal käsureal käima ja saadab tulemuse päringu algatanud masinasse.
  • Iga võõras masin, mis algselt minu käest tulnud päringu saab, saadab ta omakorda kõigile talle teadaolevatele edasi, vähendades seejuures nn ttl (time to live) counti, et päringud lõpmatult rändama ei jääks.

Ehk, masinad saadavad minu antud päringut rekursiivselt ise edasi.

Pane tähele, et sinu P2Net ei pea üldse salvestama võõraste P2Net-ide ip-sid ja porte! Samas ei ole ka kuidagi keelatud (debugimiseks või niisama huvi pärast vms) salvestada teiste P2Net-ide ip-sid, mida saab teada näiteks sulle tulnud päringutest, sulle vastajate ip-dest ja miks mitte ka portscannides :)

Miks just selline päringu edasisaatmisviis?

Põhimõtteliselt saab päringut massidesse P2P meetoditega laiali saata kahel viisil:

  • Iteratiivne meetod (antud praksis seda ei kasuta): algne masin küsib tuttavatelt neile tuttavate masinate faile, ja suurendab seeläbi endale teadaolevate masinate hulka. Igalt uuelt teadasaadud masinalt küsib ta jälle selle masina tuttavate faile jne. Teised masinad algset päringut ise kuhugi edasi ei saada. Meetodi pluss on see, et algne masin saab lihtsalt tagada, et päringut ei saadetaks kaks korda samale masinale. Meetodi miinus on see, et kõik masinad võrgus saadavad lõpuks terve neile tuttavate masinate faili algsele masinale: see tähendab väga suurt hulka väga suurte failide saatmisi, mis hakkavad jõhkralt ummistama võrku, ja algse masina väike kanal tõenäoliselt ummistub varsti. Saadud failide ühisosad on väga suured. Halvemal juhul saab algne masin N identset sõnumit, kus igaühes on N ip-d, kus N on kõigi masinate arv, kus jookseb P2Net.
  • Rekursiivne meetod (antud praksis nõutud): algne masin saadab oma päringu tuttavatele masinatele, kes selle omakorda enda tuttavatele edasi saadavad jne. Igüks, kes leiab enda failide hulgast vajaliku faili, saadab info algsele masinale (vastasel korral ei saada ta algsele masinale midagi). Algne masin ei suurenda endale teadaolevate masinate hulka. Meetodi pluss on see, et algsele masinale saadetakse tagasi infot ainult siis, kui vajalik info leitakse (väga väike protsent masinaid) ja see info on lühike. Koormus võrgule langeb tugevasti ja algse masina kanal tõenäoliselt ei ummistu. Meetodi miinus on asjaolu, et üks ja sama masin võib saada algse päringu mitu korda eri suundadest, mis jällegi kasvatab võrgu koormust. Seda viimast probleemi saab mitmel moel leevendada (kuigi mitte täielikult kaotada), eeskätt päringu ttl (time to live) parameetrit kasutades, päringu ahela masinate lisamises päringu parameetrite hulka jne.

Gnutella kasutab rekursiivset meetodit, nii ka meie P2Net. Lihtsakoeline rekursiivne meetod ummistab suure klientide arvu korral võrgu ja sele asemel kasutavad suured P2P süsteemid kas:

  • struktureeritud nn superpeeride süsteemi a la Kazaa ja esialgne Skype, kus rekursiivne päring toimub ainult superpeeride vahel, ja neid on vähe, või
  • väga kavalat nn distributed hash tables (DHT) mehhanismi, a la freenet ja (osaliselt) bittorrent. DHT on üks mitmest bittorrenti poolt kasutatud meetodist, kuigi bittorrenti põhifookus on hoopis faili paralleelse allatõmbamise optimeerimisel mitme masina koostöös, mitte masinate/failide leidmisel. Või:
  • kasutavad masinate leidmiseks eeskätt tsentraalseid servereid, a la esialgne Napster või kaasaegne Skype

Tehnilised nõuded

Programmeerimiskeele ja muu tehnoloogia valik on vaba, kuid rakendus peab vastama neile tingimustele:

  • Kogu programm peab töötama kas ITC-maja klassi arvutis või sinu oma läptopis, mis ITC maja klassis kaasas. Mingit kaugel asuvat serverit põhirakenduse jaoks kasutada ei tohi. Arusaadavalt võib aga panna P2Net lisaks käima ka suvalistesse välistesse masinatesse.
  • Http protokolli jms realisatsioon peab olema teie oma programmi osa, mingit "suurt" http serverit a la apache kasutada ei või. Kõikvõimalike võrguteekide (versus eraldiseisvad veebiserverid) kasutamine on ok, mikroserverite koodi integreerimine oma programmi on ok.

Protokoll

Otsipäringu saatmine ja edasisaatmine

Konkreetsele masinale 11.22.33.44 (kus P2Net jookseb pordis 2345) käsu saatmine 

http://11.22.33.44:2345/run?prog=käsurida&sendip=55.66.77.88&sendport=6788&ttl=5&id=wqeqwe23&noask=11.22.33.44_111.222.333.444 ...

kus parameetritel on järgmine sisu:

  • prog: käsk
  • sendip: esialgse saatja ip
  • sendport: esialgse saatja port
  • ttl: kui mitu otsingu-hopi veel teha (iga edasiküsimine vähendab ühe võrra)
  • id: optsionaalne päringu identifikaator
  • noask: optsionaalne list masinatest, kellele pole mõtet edastada (eraldajaks alakriips)

Päringu identifikaator ei pea tingimata üle terve võrgu unikaalne olema - lihtsam on ja ajab asja ära, kui on saatva masina piires unikaalne.

prog parameeter peab ilmselt olema urlencoded, näit. midagi taolist: 

...&prog=ipconfig%20/displaydns&...

GET-päringu vastuseks on õnnestunud päringu korral number 0, ebaõnnestunud päringu korral muu (vea)number. Vastuse mõte on eeskätt debugimise lihtsustamine ja vastust peaks pärija üldiselt ignoreerima. P2Net peaks töötama edukalt ka juhul, kui ta saatmise peale ühenduse lihtsalt kinni paneb ja vastust kuulama ei hakka.

P2Net-le tulnud päringu edasisaatmine käib täpselt sama protokolliga, kuid edasi saadetakse veidi muudetud päring:

  • ttl vähendatakse ühe võrra
  • optionaalselt: lisatakse oma masina ip noask parameetrile otsa

Seejuures ei saadeta päringut edasi, kui sissetulnud ttl oli 1 võ i vähem (st ttl=0 päringuid enam kuhugi ei saadeta)

Seda päringut saab ka brauserist katsetada, kuigi brauser ei saa vastuseks midagi huvitavat peale debugimis-vastuse 0 või mingi veakoodi.

Klientide filtreerimine (juhul kui soovitakse juhtida mingit alamhulka masinatest) toimub programmi käsurea kaudu. See osa ei ole kohustuslik vaid tuleneb konkreetsest rakendusest; protokollis see funktsionaalsus ei sisaldu.


Tulemuse tagastamine algsele pärijale

Vastus oleks http post meetodiga käivitatud programmi kogu väljundi saatmine algsele küsijale muutmata kujul koos lisainfoga 

http://11.22.33.44:2345/result

POST-itatud data: 

  {"sendip": "55.66.77.88", 
    "sendport": "6788",
    "id": "asasasas",
    "encoding": "ascii" või "base64",	  
    "content": "failisisustring"}

id peaks vastama esialgse saatja antud id-le, juhul kui seda kasutatakse.

  • id: esialgse päringu id (kui oli algselt antud)
  • content: käsureaprogrammi väljund (kui ei ole plaintext, peaks olema base64-encodetud)
  • encoding: mis formaadis content on
  • sendip: tulemuse saatnud masina ip
  • sendport: tulemuse saatnud masina port

Programm võiks ka mitte crashida, kui id puudu on, kuna id on optional (aga praktiline ja mõtekas on lisada).

Postituse saaja vastab eduka kättesaamise korral arvu 0, arusaamatuste korral mõne muu (vea) numbri. Jällegi, vastuse mõte on eeskätt debugimise lihtsustamine ja vastust peaks pärija üldiselt ignoreerima. P2Net peaks töötama edukalt ka juhul, kui ta saatmise peale ühenduse lihtsalt kinni paneb ja vastust kuulama ei hakka.

Praksi kaks osa

Väga soovitav on teha praks kahes osas ja esitada kaks korda ülevaatamiseks:

  • Teha http protokolli järgida suutev esmane rakendus.
  • Lisada sinna kogu vajalik funktsionaalsus:
    • P2Net protokolli implementatsioon
    • P2Net peale ehitatud rakendus (nagu data korjamine, web query hajutamine, lihtsustatud remote admin, ...). Vt ka #Näiterakendus.

Http protokolli järgimise võimet kontrollitakse praksi eduka läbimise tingimusena.

Soovitusi ja ideid

Arendamiseks ja testimiseks pead saama jooksutada oma masinas mitut erinevat koopiat omaenda P2Net-st, igaüks oma pordil, igaühel oma konfifail tuttavate masinatega.

Hea mõte on teha P2Net käsurealt käivitavaks nii, et ta võtab kohe käsurealt pordinumbri parameetriks ning loeb siis oma konfifaili vastavast pordinumbrist tuletatud failipathist.

P2Net peab päris kindlasti sisaldama või kasutama http serverit, muidu ei ole temaga võimalik väljast ühendust võtta. NB! See ei tähenda mingit nö suurt veebiserverit a la apache, vaid pigem ise kirjutatud väikest minimaalset serverit, mis pealegi ei pea veebilehti serveerima ja cgi-sid käivitama, vaid ainult teatud käskudele/parameetritele reageerima.

Server tuleb realiseerida ise, kasutades võrgust leitavaid näiteid mikro-http-serveri jaoks (tüüpiliselt paar lehekülge koodi). Selliseid näitekoode võib täiesti otse kasutada.

C jaoks on sobiv mikroserver näiteks tiny, java jaoks on see server väga hea väike näide, aga selgitava tekstita, ning selgitavate tekstidega servereid leiad mh siit ja siit.Loe java socketitest põhjalikumalt siit. Pythoni serverinäite saad siit. Http kohta võib lugeda näiteks siit.

Kasutajaliides võib olla tehtud aknaga, aga see ei ole kohustuslik: võib teha ka puhtalt käsurea rakenduse.

Rakendus on mõistlik teha nii, et annad käivitamisel ette pordi, millel ta räägib, ning kui seda porti ei ole antud, siis kasutad vaikimisi porti 1215 (1214 on Kazaa port).

Häid selgeid näiteid ja õpetusi socketite ja serveri tegemise kohta leiad veel siit:

Näiterakendus

Sisend on list sõnadest (näiteks faili kujul, kus igal real üks unikaalne sõna). Tahaks teada saada, millised neist sõnadest on üksteisega sarnased. Väljund võiks olla mapping, kus on sõna ning siis sellega sarnaste sõnade list. Sellist asja võib vaja minna juhul, kui ma tahan mingit sisenddatat, näiteks veebist scrapetud andmeid, normaliseerida - oletame et ma otsin sõna "serials", siis võiks mind tegelikult ka huvitada kohad, kus esineb sõna "serial" (süntaktiline sarnasus) või kui ma otsin sõna "truck", siis mind võib huvitada ka "lorry" (semantiline sarnasus, mida on küll tegelikult suht keeruline tuvastada).

Kuidas sellist mappingut tekitada? Proovime kõiki sõnu üksteisega paarikaupa võrrelda. Näiteks oletame, et mul on sõnad: ["oma", "masinas", "mitut", "erinevat", "koopiat", "omaenda"]. Hakkame võrdlema: "oma" ja "masinas" ei ole sarnased, "oma" ja "mitut" ei ole sarnased jne. kuni jõuame "oma" ja "omaenda" juurde, mis võiks olla sarnased (see sõltub täpselt sellest, kuidas sarnasus defineeritud on). Sellega on "oma" läbi vaadatud, järgmiseks võtame "masinas". Sõnaga "oma" pole seda enam tarvis võrrelda, järelikult alustame paarist "masinas" ja "mitut" ja nõnda edasi kuni lõpuni. Väljund võiks olla näiteks mapping {"oma" : ["omaenda"], "omaenda": ["oma"]}.

Selleks tuleb vaadata (n(n-1))/2 paari, ehk sellel ülesandel on polünomiaalne keerukus O(n^2). Mida see tähendab? Kui ma võtan näitena toodud kuuesõnalise listi asemel mingi realistlikuma listi, kus on 6000 sõna, siis aeg, mis selle läbi töötamisele kulub, ei kasva mitte 1000 korda vaid umbkaudu 1000000 korda. Ehk siis suht kerge on jõuda kohta, kus me enam ei viitsi tulemust ära oodata, kuna selle leidmine võtab tunde.

Antud ülesanne kuulub triviaalselt paralleelsete ülesannete hulka. Kui meil on 60 masinat käepärast, siis saab töö nii jagada, et iga masin teeb ~1/60 vajaminevatest võrdlustest ning see võiks tuua tööaja tundidest jälle minutite peale tagasi. Kuidas asja võiks P2Neti peal teha:

  • Partitsioneerimine. Oletame, et me teame, kui palju meil masinaid täpselt P2Net-iga liitunud on. Kui neid masinaid on k, siis iga masin võiks võtta 1/k-ndiku sõnadest ette ja võrrelda neid kõigi sõnadega. Näiteks kolme masina korral meie kuuesõnalisel näitel võiks üks masin võrrelda sõna "oma" ja "masinas" kõigi teiste vastu, teine teha seda sõnadega "mitut" ja "erinevat" jne. Natuke ressurssi läheb siin raisku selle peale, et ühte paari võrreldakse kaks korda: esimene masin teeb võrdluse "oma" ja "mitut", teine teeb ka "mitut" ja "oma". Selle vältimisega ei ole mõtet vaeva näha, see on pigem kasulik (sellest hiljem veel). Järgmiseks tekib küsimus, kuidas juhtida masinaid nii, et me ei peaks igaühele otse käsku andma. Seda võib lahendada nii: 1.) panen päringule kaasa parameetri k ja URL-i, kust sisendandmed saab alla tõmmata 2.) iga masin arvutab h=hash(omaip,omaport) % k ja saab numbri h mis on vahemikus 0 kuni k-1. 3.) iga masin teeb sisendandmete listist täpselt iga k-nda sõna, nihkega h: kui mul h=0 ja masinaid on kokku 7, siis ma võtan ette sõnad 1,8,15,... .
  • Tulemuste kokku korjamine. Iga masin saadab oma osalise mappingu päringu algatajale. See paneb need kokku umbes nii: kui ühest masinast saadi {"koer": ["koera"]} ja teisest {"koerad": ["koera"]}, siis me saaks sellest kokku järeldada ka midagi sellist: {"koera":["koer", "koerad"]}. Mismoodi tulemusi täpselt kokku panna, sõltub natuke, kas teie arust on sarnasuse seos sümmeetriline ja/või transitiivne.

Tähelepanelikumal tudengil võib tekkida küsimus, mis siis saab kui hash collision tekib ning mõni tükk üleliia tehakse ning mõni mitte kordagi. Selle probleemi jätame koduülesandeks, vihjeks ainult, et 1.) P2P rakendustes ei ole niikuinii mõtet loota, et kõik masinad algusest lõpuni ilusti võrgus kättesaadavad on ja ei crashi töö jooksul 2.) partitsioneerimise meetod, mida kasutasime, tekitab teatud ülekattuvuse.

Juhul kui ka selle näiterakenduse uurimine mingeid ideid ei tekitanud, võib ka sellesama asja realiseerida. Tasub ainult tähele panna, et see on tõenäoliselt natuke töömahukam, kui mõni ise välja mõeldud rakendus.

Firewall ja NAT

Firewallist läbi murdmise ja kinniste portidega ühendamise probleemiga ei pea selles praksis tegelema. Samas tähendab see, et ei ole kuigi lihtne teise masinaga tegelikult ühendust saada (ühes masinas debugimise võimaldamine ongi seepärast kriitiline).

Kes P2Net käima saab, võib mõelda välja ja realiseerida probleemi lahendamiseks sobiva vaheserveri: selle eest saab ekstrapunkte.

Võrgust infot otsides leiad kahte liiki teemasid, meie jaoks oluline on siit listist teine:

NB! Seda kõike ei ole väga lihtne teha ja sinu P2Net (ja ka selle inimese P2Net, kellega suhtled) peab ka oskama seda vaheserverit kasutada. Ära hakka seda ehitama, kui nö lihtne P2Net veel ei tööta!

Ekstra-lisapunktide saamise variant: realiseeri ja pane kõigile kasutatavaks firewalliprobleemi lahendamiseks sobiv vaheserver. Kirjuta kasutamise juhend ja näited, mida teised saaks soovi korral oma P2Net jaoks tarvitada (st panna nad sinu vaheserverit kasutama, nii et seda saaks ka arvutiklassist kasutada). Esimesed kaks gruppi, kes sellega hakkama saavad, saavad lisaks pooled praksipunktid!


Punktiarvestusest

Kui P2Net protokoll töötab vastu mõne teise grupi P2Net-i, sellele on realiseeritud mingi rakendus ja koodi suudetakse seletada, saab täispunktid.

Kui teiste P2Net-programmidega ei suuda suhelda, aga iseenda koopiatega siiski, siis päris täispunkte ei saa.

Pärit leheküljelt "http://lambda.ee/w/index.php?title=Vorgurakendused_2_prax_1_2014&oldid=12496"