Alba/Neagra cu maşini

[tradelover]

Foarte bine Ciordi! Nota 10!

 

Problema nu ai cum să o găsesti pe gugăl, pentru simplul fapt ca este inventia unui coleg de al meu de facultate mai mic (si ulterior student de al meu, cand am predat niste cursuri pe acolo dupa terminarea facultatii, el era in ultimii ani). In ultimii ani de facultate eram innebunit cu virusii informatici. Parca am mai scris pe vamist, lucrarea mea de licenta a fost in domeniul virusilor, antivirusi, securitatea si protectia datelor. Vreo 8o de pagini scrise mărunţel, cu cod masina (virusi polimorfi dezasamblati), teorie, etc. Si a fost notata cu 10, pe merit, nu pe cafea si sticle de bautura, cum zicea cineva mai sus (daca e intr-adevar asa, e nasol tare pe acasa....). Pe vremea aia eram fascinat de programele astea mici care se "reproduc" in computerul tău ca si cum ar fi alive. Am invatat o gramada de chestii despre programare si calculatoare, dezasambland virusi informatici si incercand sa vad cum sunt facuti. Autorii astui fel de programe erau bineinteles niste experti, pentru ca nu oricine poate scrie un virus destept, care sa fie poliform si sa scape nedetectat de cei mai multi antivirusi existenti la vremea aia. Trebuie sa stii o gramada de chestii despre computere si despre sistemul de operare, multe dintre ele nedocumentate in cartile de specialitate. Gaseam chestii de ma cruceam, nu stiam de unde sa le apuc, apeluri de intreruperi care nu existau in documentatii, algoritmi ingeniosi de criptare a codului executabil, care sa ramana executabil si dupa criptare, etc. Era o lume fantastica, extraordinara. Am si la ora actuala colectia de peste 30 de mii (no joke) de familii de virusi (in total aproape 100 de mii de "indivizi" diferiti, incepand de la batranul "ierusalem", pana la chestii super evoluate de tipul "tremor", "one-half" ori "neuroquila") dezasamblati si comentati, pe care ii pastrez undeva zipaţi pe un colţ de hdd.

 

Pe vremea cand eram ingropat in studiul virusilor informatici, in afară de faptul ca nu prea existau programe antivirus destepte (cele existente ca scanXX, mcaffe, fprot, fpsav, etc, se bazau pe liste de semnaturi si nu puteau identifica virusii noi, in plus puteau da alarme false daca se nimerea ca un program onest sa aiba aceeasi semnatura de memorie), nu prea existau nici carti de teorie, in afara de ceva volume de calculabilitate (programele care isi reproduc istoria si programele care se reproduc sunt discutate la capitolele de masini turing in teoria calculabilitatii, vezi de exemplu cartea de calculabilitate a lui C-tin Cazacu, in mod cert exista si alte chestii mai noi si mai bune in domeniu, dar eu am cam pierdut contactul cu partea teoretica de calculabilitate, cam demultisor, cartea aia e foarte greoaie, pe vremea cand a apărut eram studentul lui şi boul dracului obliga studentii mai slabi să clămpănească in TeX si LaTeX teoreme si demonstratii pe care el să le bage in carte, pentru note de trecere. Cine nu clămpănea, pica la examen. Desi nu eram intre cei mentionati, am fost unul dintre cei care am clampanit cel mai mult, pentru că imi plăcea, eram interesat de domeniu, si m-am ales cu o mentiune de multumire in prefaţa cărţii, haha).

 

Cartea de căpătâi in "virusologie teoretica" era lucrarea de doctorat a lui Fred Cohen, considerat părintele teoriei virusilor informatici. In acea lucrare, Cohen prezintă in premieră mondială o "teorie" a programelor care pot sa isi reproducă sursa (un program al cărui output este programul insusi), si prezintă pentru prima dată noţiuni de polimorfism (un program se poate transforma in alt program, care să arate total diferit, dar sa facă acelasi lucru, respectiv să se transforme in alt program care arată total diferit, si asa mai departe). El prezinta pentru prima dată noţiuni de "genetică" relativ la programare, adica mai multe programe pot "coopera" pentru a produce un alt program, care are caracteritici comune tuturor "părinţilor" lui, si poate coopera mai departe la producerea unei noi "progenituri" informatice.

 

Asemenea chestii existau deja "in the wild", ca virusi informatici, dar nimeni nu pusese mâna pe creion să facă o abordare teoretică a problemei, să arate cu teoreme si demonstratii cât de departe se poate merge, şi cât de puternice pot fi asemenea programe, care eventual cooperează împreuna, "în folosul comunităţii". Cohen era foarte pragmatic, el nu se gândea la programe care sa faca stricaciuni, ci la programe care să fie folositoare utilizatorului. Multe dintre conceptele descrise de el au fost implementate ulterior in sisteme expert industriale, motoare de căutare pe internet, şi multe si multe altele, si mai multe astfel de concepte care au fost implementate si-au găsit cale deocamdată doar spre "latura negativă a forţei", adică sunt implementate doar de catre diferiti virusi informatici si programe care fură parole ori distrug fisiere prin computere. Ca si cu dinamita, Alfred Nobel a inventat-o ca să facă drumuri si poduri şi tunele prin munţi, dar ulterior şi-a găsit calea mai mult in războaie, terorism, chestii legate de distrugere si omor. Cele mai multe dintre conceptele descrise de Cohen si de urmasii săi sunt deocamdată neimplementate in practică, şi nu se stie ce ne rezervă viitorul.

 

De ce aduc vorba de Fred Cohen si de virusi?

 

Well... Problema de care vorbim este o problema tipica de transmitere a informatiilor pe canale ne-oficiale, sau confidentiale. Practic intrebarile care se pun sunt "ce fel de informatie pot transmite studentii unul altuia?", si "cum?". Pentru ca daca ei nu pot transmite nici un fel de informatie, atunci e clar ca dupa primul ciclu de ("NU", "NU"), suntem exact in situatia de la inceput, si studentii nu au mai mult de 50% sanse.

 

In una din cărţile lui, in care imparte virusii in clase, Cohen dă o clasă de virusi numiti "virusi cu canal de informaţii ascuns" (traducere proasta din engleză). El arată cum pot fi definite teoretic o serie de programe care rulează pe terminale diferite ale unei retele Novell, nu au drepturi de supervizer (retea formată dintr-un server central si mai multe terminale), au drepturi foarte restranse si cu securitate foarte stricta pe retea, programele nu pot comunica unul cu celălalt "in nici un fel" permis de reţea, fiecare program in sine este total inofensiv, dar luate impreuna, ele reusesc sa distruga reteaua, adica să treacă prin toate filtrele de securitate si să capete acces de supervizer (Andrew Schulmann dă un astfel de exemplu pt Windows 98 in cartea lui Undocumented Windows). Cum? Foarte simplu, ele reusesc să comunice intre ele prin diferite canale "neoficiale", informatia "privată" deţinută de fiecare dintre ele devine in acest fel informaţie "de domeniul public" pentru celelalte, şi este pusă cap la cap. Ca exemple de canale neoficiale, Cohen dă câteva ZECI de astfel de canale posibile, incepand de la banalul "spatiu pe harddisk", presupunand ca spatiul disponibil pe hdd-ul serverului poate fi citit de fiecare program, un program poate transmite informatii celorlalte pur si simplu creind un fisier de cativa megi si stergandu-l regulat. Programele care stau la pândă recepţionează un 1 de fiecare dată când spatiul pe server scade, si un 0 cand creste. Cu un algoritm de filtrare de zgomotului (si alti useri "normali" creaza si sterg fisiere pe retea in acest timp), si un CRC destept, programele pot coopera intre ele si pot schimba o cantitate incredibilă de informatie. Si asta era doar un exemplu, ele pot folosi mult mai multe metode in acelasi timp. La o prima vedere se pare ca e imposibil, ca si in problema noastra, in care se pare că profesorul are toate cheile, si ca studentii nu au nici o sansa.

 

Prin '94 sau '95 participam cu un echipaj de la facultate la o competitie studenteasca legata de programare. In tren spre Craiova, unde se tinea competitia, s-a incins o discutie despre virusi poliformi (by the way, programul meu care depista si scotea virusi poliformi a luat atunci premiul intai la sectiunea practică, era cumva noutate in domeniu, păcat că nu am perseverat in domeniu, abia peste vreo jumate de an apăreau primii antivirusi cu metode euristice, f-prot, al lui Fredrik Skulason, care depista virusi de tipul "one-half" şi abia peste vreun an de zile f-prot a fost capabil să decripteze si sa scoată integral One-Half-ul, cine ştie ce "skulason" as fi fost eu acuma. Prin 2001 Skulason mi-a oferit un job, in urma unor analize pe care i le-am trimis, dar nu mi-a plăcut Islanda, prea frig, eram deja in Thai).

 

Majoritatea celor din echipaj erau foarte buni la teorie, dar mai slabi pe partea practică. Cumva au facut misto de virusii mei "ce e aia virusi? cu asta vrei tu să câştigi competitia?". Şi eu, ca să nu mă las mai prejos, le-am prezenzat chestiile lui Cohen cu reteaua Novel de mai sus, bineinteles mai in amanunt decat am scris aici. Canale ascunse prin care informatia privată devine publică. Discutia a deviat spre acest subiect, iar colegul de care vă vorbeam in primul paragraf al acestui post, pe numele lui Marian Ciobanu, un tip foarte destept si bun programator (câteva rezultate serioase in domeniul criptării cu chei publice, nu mai stiu nika de el de vo 10 ani), a scos din mânecă problema cu numerele, cu studentii si cu profesorul, un pic diferită de versiunea pe care v-am prezentat-o eu, era un caz mai general, şi mai greu. Vo juma de oră ori mai bine, s-a făcut liniste deplină in compartiment, apoi toti am constatat cu surprindere că fiecare rezolvase problema corect, dar toate rezolvările erau DIFERITE. Magda Ionescu si Tavi Procopiuc (ulterior soţ şi soţie, peste ani doctoranzi la Duke University, la ora actuala profesori pe undeva pe la o universitate prin State, nu mai stiu nika de ei de vreo 7 ani cel putin) au venit cu o solutie analitică cu şiruri de numere intregi si limite, din care nu am inteles nimic, dar restul (inclusiv Marian) au aprobat solutia ca fiind corectă. Mi-a rămas in minte intamplarea, si desigur si problema, pentru că solutia era total impotriva bunului simt, pentru că toti au reusit să o rezolve, pentru că toti au găsit metode diferite, folosind domenii diferite, adică unu a dat un algoritm, altu a dat niste sirusi si a demonstrat că converg, unul a dat o solutie bazată pe inductia matematică, identică cu solutia dată mai sus de Ciordi, etc.

 

Inductiv solutia e foarte simplă, dacă unul dintre studenti are un numar intre cele doua afisate pe tablă, el spune "da" din prima si totul e clar. Acesta e pasul 1. In pasul inductiv, presupunand ca studenti au spus "nu" de un număr de ori, se poate arăta exact ca pe exemplele lui Ciordi, "din pas in pas" cum se face inductia.

 

Interesant linkul acela cu problema si ceasul, este o varianta mult mai simplă (de care nu stiam!) şi mult mai usor de inteles. Mii de multumiri pt link!

 

Eu am mai spus problema aceasta si altora, si era greu sa le explic solutia. Intotdeauna incepeam cu problema cu filozofii si fesurile (un sultan care avea pică pe cărturari prinde trei "intelepti" si le arată 5 fesuri, 3 albe si 2 rosii, apoi ii asează in cerc, stateau turceste si fiecare ii vedea pe ceilalti doi, nu au voie sa comunice intre ei, cineva vine pe la spatele fiecarui intelept si ii aseaza un fes in cap - trei slujitori asează fesurile pe cap in acelasi timp la toti trei inteleptii. Fiecare intelept vede fesurile celorlalti doi, dar nu pe al lui. Daca fiecare spune ce fes are in cap fara sa greseasca, sunt liberi, daca nu atunci li se taie capul. Bineinteles ca inteleptii, după vreo 20 de secunde de gandire spun toti in acelasi timp "fesul meu are culoarea cutare" şi toţi ghicesc culoarea corectă şi scapă cu viaţă. Intrebare: ce culoare aveau fesurile fiecaruia, şi cum au judecat ei?). Această problemă e arhicunoscută, e mai usor de inteles, si este un caz particular al problemei cu studentii si numerele, adica un caz in care multimea "numerelor" este limitată la 5, iar rationamentul are cel mult 3 pasi, trei "ticăituri" de clock de ale lui Ciordi (vezi linkul dat de el). Dacă un tip putea să rezolve problema cu filozofii, sau măcar înţelegea rezultatul, atunci se merita să ii spun despre studenţi şi numere, altfel nu se merita să imi pierd timpul cu el

 

Acum, datorită linkului dat de Ciordi, am un pas intermediar, haha, ca in quiz-ul pt copii, ăla cu cămila pusă în frigider.

 

Şi ca sa nu ziceti că am fost total offtopi, o să vă spun soluţia pe care am dat-o eu la problema lui Marian, atunci in tren. Eu mi-am imaginat in mintea mea imediat un arbore, in care studentii trebuie să navigheze. Pentru exemplul cu 11, 17, iar pe tablă 31 si 28, de care ziceam initial, cum parcurge primul student acest arbore? El judecă asa:

 

"Dacă eu am 11, el poate avea 17 sau 20. Dacă el are 17, el judecă că eu pot avea 11 sau 14, dacă are 20, el judecă că eu pot avea 8 sau 11". Si "cumva", deocamdată nu stiu cum, acest rationament continuă in adancime. Deocamdată nu mă interesează cum. Dar realizati ce se intamplă? este vorba de o listă de forma (rescriu fraza de mai sus pe bucăţi):

 

Dacă eu am 11, el poate avea 17 sau 20. Scriu asta "..... - 17 - 11 - 20 - ....."

 

Dacă el are 17, el judecă că eu pot avea 11 sau 14. Acuma, 11 e deja la cap de listă, il adaug pe 14. Si am:

"..... - 14 - 17 - 11 - 20 - ....."

 

Dacă el are 20, el judecă că eu pot avea 8 sau 11. Acuma, 11 e deja la cap de listă, il adaug pe 8. Si am:

"..... - 14 - 17 - 11 - 20 - 8 - ....."

 

Practic, in listă numerele rosii sunt numerele pe care pot eu să le am, iar cele albastre sunt cele pe care poate partenerul să le aibă. Această listă este finită. Pentru că invariabil, numerele roşii la un capăt scad (şi nu pot scădea sub zero), iar la celălat cresc (si nu pot creste peste 31). Cele albastre invers. Lista mea completă pentru exemplul dat este foarte simplu de calculat, plec de la 11, numărul meu, si in stanga pun diferenta pana la 28, in dreapta diferenta pana la 31. Si continnui in acelasi mod până nu mai pot. Chiar si pentru numere imens de mari, de care vorbea Dan mai sus, lista poate fi FOARTE scurtă! (depinde de numere, ea poate fi foarte lunga pt numere mici "alese cu grijă"). Dau mai jos această listă, nu mai folosesc culori ca imi e greu sa scriu colorat cu editorul asta, dar vă prindeti voi:

 

29-2-26-5-23-8-20-*11*-17-14-14-17-11-20-8-23-5-26-2-29

 

Cred ca v-ati prins cum am construit-o imediat, si ati inteles de ce nu poate fi mai lungă. Sumele a doi termeni consecutivi alternează intre 28 si 31. Unul dintre cei doi de 11 (nu conteaza care) este punctul de plecare, marcat cu **, pe acest exemplu lista a iesit simetrică, dar de obicei nu e necesar sa iasa simetrica, exemplul ales e cam prost, dar l-am ales la intamplare. Imaginati-vă că numerele cu pozitie pară in lista sunt albastre, celelalte sunt rosii (mi-e greu sa le marchez cu acest editor).

 

Si ati văzut cum rationamentul continuă. Da, nu am facut altceva decat să continui rationamentul despre care ziceam mai sus că "continuă, nu stiu cum". Păi asa continuă. Si lista e finită, că mai departe dau de numere negative, la ambele capete.

 

Când am auzit problema, atunci in tren, in cateva secunde aveam deja lista in capul meu. Mi-a luat aproape 10 minute să realizez că cei doi studenti, dacă au dus rationamentul la capăt, ei au in mintea lor ACEIAŞI listă!!!! Ceea ce diferă este doar punctul de plecare.

 

Pentru colegul meu lista va fi:

 

29-2-26-5-23-8-20-11-*17*-14-14-17-11-20-8-23-5-26-2-29

 

Tocmai ĂSTA e şpilul! Imaginati-vă lista asta ca o pleteră de usturoi, agăţată in cui din punctul in care are steluţe.

 

La unul dintre studenti, un capăt e iremediabil mai scurt!!

 

 

Scuzati desenul, nu am timp de desenat arbori ori căciulii de usturoi, am făcut doar un copy-paste direct de aici din post, si rotate text folosind paintbrush, dar voi imaginati-va ca numerele sunt scriese normal, nu rotit, dar fiecare isi pastreaza nivelul pe care apare.

 

Acum lucrurile sunt foarte simple. Odata vazut numarul pe foaie si numerele pe tablă, studentului ii trebuie cateva secunde/minute să isi faca "pletera lui" de usturoi. Apoi cand vine randul lui, daca in pleteră are amândouă ramurile, spune NU si taie primul nivel cu o linie rosie. Primul student care termină una dintre ramurile "pleterei" spune DA si el stie numărul partenerului, pentru că ştie că pletera celuilalt este "balansată mai central". Pentru exemplul dat, eu stiu că partenerul are 17, in exact 8 pasi. Dacă el ar fi avut 20, ar fi spus el "da" la pasul 7. Dacă nu a spus, inseamnă că are 17, si eu voi spune "da" la pasul 8.

 

Well... gata! ma dor degetele de la taste, asta e tot pe azi.

 

Asta numesc eu o problemă rezolvată! Rezolvarea trebuie să fie de asa natură incat să fie constructivă, să vă permită să jucati jocul cu prietenii, fără să fiti matematicieni.

 

Dacă v-ati inteles cu un prieten, puteti juca drept "studenti" la vreun party, in camere separate, il puneti profesor pe vreunul care se dă mare pe la petreceri, fixati o limită la numere, sa zicem 100. Si ii trageti aluia nişte ţepe de o să creadă că sunteţi telepaţi. Odata stiuta aceasta solutie, chiar si un copil poate să joace, dacă ştie să adune si să scadă (să isi facă repede arborii).

 

De remarcat că conditia ca "jocul să cicleze de un număr de A+B+1 ori inainte de a fi declarat castigat de profesor" era prea relaxată. Practic in orice situatie, studentii stiu răspunsul după cel mult "max(A,B)+1" incercări, unde A si B sunt numerele de pe tablă, ceea ce inseamna mult mai putini pasi. Practic, daca diferenta dintre numere este 1 si toate numerele sunt prime intre ele (lista creste/scade cu 1 spre ambele capete) numarul de cicluri necesar este maxim. Altfel numarul de pasi este mult mai mic (algoritmul lui Euclid). Dacă diferenta este 2, lista scade cu 2 spre capete, cel putin, fiind la jumatate ca lungime. Si ala mai departe.

 

Inutil să vă spun că solutia mea a fost salutată cu urale, atunci in tren

Editat Decembrie 7, 2010 de tradelover