Category Archives: PHP

Lookup Table în PHP

Problema implementării unui lookup table pare uneori simplă. În cazul în care se implementează ca un array indexat, iar obținerea unei valori se face prin metoda dă-mi valoarea Y de la cheia X, atunci problemele de performanță nu intervin.

M-am lovit de altă bubă, și anume implementarea unui lookup table simplu bazat pe căutare liniară construit pe baza unui pre-fetch. Ideea este simplu de implementat, și deși procesul respectiv nu rulează prea des, numărul valorilor distincte complică problema destul de mult. Într-un lookup table de 70.000 – 80.000 valori căutarea unui număr mai mare de valori durează peste jumătate de oră (nu știu exact, am oprit benchmark-ul după 30 minute) cu procesorul (sau un core) la ~100% load, pe când restul operațiilor se execută în secunde. Cam multicel pentru o căutare ce ar trebui să returneze TRUE / FALSE. Faptul că numărul de căutări este mai mare decât lookup table-ul în sine mai bate un cui în coșciugul metodei de mai sus. Se mai adaugă și faptul că deși în teorie valorie ar trebui să fie unice, datele din pre-fetch nu sunt neapărat validate în acest sens.

Pre-fetch – pseudo implementare

$haystack = array();
while($value = get_data())
{
$haystack[] = $value;
}

Ideea este simplă. Stiva $haystack va conține toate valorile, inclusiv cele duplicat. Mă rog, pre-fetch-ul implementează ideea de “stivă” pentru că auto-indexarea cu [] are aceeași funcționalitate ca și array_push(), dar câștigă puțin la viteza de inserare a datelor. Durează câteva secunde, nu este o operație foarte complexă. De aici începe greul.

Căutare – implementare uzuală

Există tentația de a face căutarea pe baza lui in_array() sau array_search(). Ambele sunt aproximativ la fel de rapide (in_array() este cu maxim 1% mai lentă). Problema principală este căutarea liniară, fără indexare.

Dau chiar exemplele din codul meu de benchmark:

 public function bench_in_array($needle)
{
return in_array($needle, $this->haystack);
}
 
public function bench_array_search($needle)
{
if (array_search($needle, $this->haystack) === FALSE)
return FALSE;
return TRUE;
}

Căutare – soluția optimă

Ambele soluții anterioare sunt aproximativ la fel de rapide, dar aproximativ la fel de lente. Interesul este dacă există o valoare. Duplicatele doar încurcă.

$haystack = array_flip($haystack);

Inversează valoarea cu cheile dintr-un array. Valorile duplicat dispar din moment ce un array (mă rog, devine ordered map) nu poate avea chei duplicat. Se pot aplica alte două metode distincte. Dau din nou exemplu din codul meu de benchmark:

 public function bench_array_flip_isset($needle)
{
return isset($this->flipped_haystack[$needle]);
}
 
public function bench_array_flip_array_key_exists($needle)
{
return array_key_exists($needle, $this->flipped_haystack);
}

Pentru o listă de $needle scurtă (1% din $haystack, valori 100% valide), sunt aproximativ echivalente. Pentru un input 50% valid de dimensiunea $haystack, array_key_exists() este cu aproximativ 80% – 100% mai lent. Dar acum urmează partea frumoasă: căutarea se face indexat. Metoda este de cel puțin 2000 ori mai rapidă decât căutarea cu in_array() / array_search(). Adică în mod uzual căutarea de mai devreme de peste jumatate de oră durează aproximativ sub 3 secunde cu isset() și sub 5 secunde cu array_key_search(). Metodă testată pe un lookup table de 100.000 valori ce mi-a cam ucis browserul. Chrome a crăpat, Firefox a încărcat output-ul de la Codebench în vreo 3.5 GiB RAM. Atașez și imagini ce stau dovadă atrocității de mai devreme.

Căi UNIX corecte în PHP

Se dă următoarea problemă, aparent mai simplă decât zice titlul: să se determine dacă o cale de tip UNIX este corectă. Buba este faptul că această cale poate să fie către un fișier ce nu există, spre exemplu o cale de UNIX socket ce va fi creat într-un director ce va conține un pool de socket-uri. Deci funcțiile la nivel de filesystem nu vor ajuta, cel puțin nu în primă fază. În cazul  în care există vreo încercare de intuiție a scopului, da, scriu server scripting și în PHP. *sh este prea limitat pentru anumite chestii mai avansate, sau are nevoie de prea mult “boilerplate code”, pe când în Perl nu sunt încă fluent. Pentru cei ce au pierdut știrile de la ora 5, PHP nu mai este de mult un limbaj strict “web oriented”, funcționează bine merci și pentru “general purpose”.

Să revin la problema inițială. Practic se pot identifica două probleme: a) validarea unei căi inexistente – deci apelăm la regex; b) validarea directorului – deși fișierul poate să nu existe în timpul execuției de validare, directorul e musai să fie acolo. De regulă aplicațiile care creează câte un UNIX socket nu verifică aceasta și vor eșua să pornească.

Rezumat, codul arată cam așa:

$validate = preg_match('/^(\/[^\0]*?\/?)[^\0\/]+$/', $path, $matches);
if (empty($validate) === TRUE OR is_dir($matches[1]) !== TRUE OR is_dir($matches[0]) !== FALSE)
{
// handle error here
}

Acum, discuție pe marginea textului. Acest regex satisface direct ambele probleme. Prima, este fix problema de validare. Se ține cont doar de căi absolute – acesta fiind contextul în care operez. Cu toate acestea, soluția se poate adapta ușor pentru căi relative.

Singurul capturing group din expresie preia întreaga cale, mai puțin numele fișierului. A fost făcută să funcționeze inclusiv pentru root (/). Calea capturată trebuie să fie către un director, pe când calea întreagă trebuie să nu fie un director.

Teoria căilor este simplă. O cale UNIX poate să conțină orice caracter, mai puțin nul, iar / este folosit pe post de separator de directoare, deci este rezervat acestui scop. Căile de tip //var///www//// sunt valide. Exemplul anterior va duce în //var/www unde // în general (Linux, BSD) este tot una cu /. Nu am lucrat pe sisteme unde // să fie distinct față de /, deci nu am considerat că este nevoie să tratez cazul prin expresia de mai sus.

Importanța unui PHP framework bine scris

Spuneam la GeekMeet-ul din octombrie (damn it, iarăși fac referință la el) în timpul prezentării mele, pentru cei absenți, o abordare de la OS până la coder în privința Web Security, despre importanța folosirii unui framework ce să facă în mod implicit filtrare XSS și SQL Injection (SQLi) a input-ului, în biblioteca ce se ocupă de baza de date. Iar pentru chestii riscante, chiar o filtrare XSS cu HTML Purifier, o bibliotecă a cărui filtru XSS a fost creat să treacă de XSS (Cross Site Scripting) Cheat Sheet.

Știu, nu vreau să fac “carieră” din astfel de post-uri pe blog și nu prea cred că o să mă vedeți vreodată să trimit chestii către http://hackersblog.org/. Sunt preocupat de a proteja, de a-i învăța pe alții cum să se protejeze, și mai puțin de a demonstra vulernabilități. Sunt orientat către ce nu ar trebui să facă aplicația și mai puțin înspre a demonstra cum ajungi acolo. De altel aș prefera ca lumea să nu se ia de ‘junk’-ul de WordPress ce rulează pe blog, sunt prea ocupat pentru a scrie un engine sigur cu un număr echivalent de facilități. Mă rog, va urma un contra-exemplu pentru a susține cele din paragraful anterior.

Povestea începe de la faptul că am avut o mică discuție cu necenzurat despre importanța folosirii unui framework, dar el o susținea pe a lui cu alea 10 kile de cod. Doar pentru ce îți trebuie un framework de 1.25 megi (dimensiunea minimă, maxim 1.49) pentru o aplicație banală? Pai în primul rând bune sunt cele de PHP5 folosind OOP și clase cu auto-load. Poți face multiple instalări folosind aceleași surse ale framework-ului exceptând aplicația în sine. Folosești ce încarci. A da, și ai filtrare implicită. De ce? Pentru că nimeni nu este perfect. Greșeli apar și în codul programatorilor ce au trecut de fazele tatonării. Vorbesc din experiența lucrului și mai mult din experiența lucrului în echipă. Dacă tu ca programator nu o dai de gard, se prea poate să dea altul.

Acu recunosc, am trișat puțin. M-am uitat puțin prin cele 10 kile de cod astfel încât buba a fost oarecum imediată. Dar nu imposibil de descoperit cu puțină răbdare și stil având în vedere regulile simple de URL rewrite, destul de evidente, și faptul că era vorba de un singur parametru vulnerabil. De fapt am reușit 3 in 1: XSS, blind SQLi și disclosure în același input.

A da, a folosi mysql_error() în producție este una dintre cele mai proaste idei. XSS-ul și disclosure-ul au fost posibile prin intermediul acestei funcții magice ce ar trebui folosite doar pentru dezvoltare, nu și pentru producție.

Momentan nu dăm poze, așteptăm să aplice patch-ul trimis :).

ID-uri numerice curate in PHP

Adesea m-am lovit de problema sanitizarii variabilelor care provin din input, si nu zic asta facand referire la PHP, ci la programare in general. Din moment ce am avut boala sa studiez catusi de cat bazele securitatii, mi-a ramas in cap un principiu foarte bine formulat: “all user input is evil!”. Adevarat grait. Deci am inceput sa gandesc aplicatiile dupa metoda user proof. In primul rand cand testez ceva nou, nu testez dupa cum ar trebui sa fie utilizata aplicatia in mod corect, ci cum NU ar trebui sa fie folosita, si ce sa se intample in acele cazuri. In primul rand pentru ca o aplicatie nu este o chestie democratica unde userul face ce vrea el si adesea face prost. Deasemenea intervine si cealata extrema. Unde nu este prostie – este viclenie – deci se poate trezi cate un h4x0r de asta cu mai mult timp liber la dispozitie sa te caute la oo (a se citi: securizare).

Problema ID-urilor numerice in PHP desi este una destul de banala, rezolvarea este multipla. De-alungul timpului am testat mai multe chestii, dar doar recent am ajuns la o forma finala care sa ma multumeasca deplin. De ce ID-uri numerice? Pentru ca este foarte usor de lucrat cu ele cand se interactioneaza cu o baza de date. Orice tabela care trebuie sa stocheze in mod unic niste chestii, are o cheie primara. Pana acum cea mai desteapta chestie in materie de chei primare este cheia intreaga care se seteaza cu auto-increment – ceea ce asigura complet unicitatea datelor. Recomandarea ar fi ca auto incrementul sa inceapa de la 0 (chestia asta o sa se lege de ce o sa zic mai jos). Bonus ar fi faptul ca fiecare tabela de acest gen ar trebui sa aiba cheia primara indexata pentru a reduce considerabil timpul de cautare al ei.

Adesea aceste chei primare din baza de date sunt trimise prin intermediul requesturilor de tip GET, deci se vor regasi in componenta URL-ului. Problema se pune atunci cand pe langa acel ID numeric, utilizatorul (in mod intentionat) introduce si altceva pe langa acel ID. Treaba poate sa se imputa de la XSS (Cross Site Scripting) – atunci cand acea cheie se regaseste in pagina, sau la atacuri de tip SQL injection (mai grav).

Desi exista functii native in suportul de MySQL pentru PHP, acestea sunt destul de triste la ID-uri numerice, deci am preferat propria metoda:

function clean_id($id)
{
$id=preg_replace("@[^0-9]@", "", $id);
if (empty($id))
$id=0;
return $id;
}

Chestia asta de mai sus face vreo doua chestii … prima este aceea ca da strip la tot inputul care nu e numeric. A doua verifica ce a mai ramas, iar daca are valoarea 0 (orice 0 din PHP), atunci returneaza un 0 numeric. Este important acest zero numeric … ziceam ceva mai sus de el … acest zero numeric are grija ca interogarea sa nu dea de o chestie gen <<WHERE id=”>> si sa bubuie o eroare de SQL (care in anumite cazuri … ar putea la randul ei sa divulge alte chestii).

Actualizare:

Datorita observatiei lui AgLiAn am ajuns la concluzia ca functia mea initiala nu rezolva o problema: interger overflow, chestie ce mai departe se traduce in interpretarea ca float de catre PHP – si de unde pot aparea alte probleme. Si pentru ca am mentionat pe undeva mai sus de auto-increment (si acest obicei nu o sa se transforme peste noapte pana la proba contrara ce demonstreaza un obicei prost), functia clean_id(); devine:

function clean_id($id)
{
return abs(intval($id));
}