L'asteroide che ucciderà questo dinosauro deve ancora arrivare (terza parte)

L'articolo è diviso in tre parti:
Prima Parte
Seconda Parte

Rieccoci qui a parlare di espressioni regolari. Dopo aver visto cosa sono (e da dove derivano) ed aver visto come si leggono e come si possono scrivere è giunta l'ora di informarci su alcuni dei software che ne fanno uso.

grep

Abbiamo già nominato grep nella prima parte, se ve la foste persa (MALE) ecco la definizione presa pari-pari dal primo articolo di questa serie:

grep è uno dei dinosauri di UNIX che si rifiutano di estinguersi. Nasce come modalità di ricerca di ex (General Regular Expression Print) ma è stato poi scorporato ed è diventato un tool fondamentale nelle mani di ogni amministratore di sistema e di chiunque debba ricercare pattern particolari in vaste collezioni di file di testo.

grep dà il meglio di sè all'interno di altri script o di one-liner (singole linee di comando ottenute concatenando con dei pipe vari comandi della shell UNIX). Il suo compito è quello di tagliare via da un flusso di testo le porzioni non rilevanti per poi poterle analizzare meglio con altri strumenti.

Nella migliore tradizione UNIX grep accetta testo dallo standard input, manda del testo in output sullo standard output e i messaggi di errore sullo standard error.

Facciamo subito un esempio concreto: vogliamo sapere qual è il MAC address di un'interfaccia di rete. Il comando ifconfig, sebbene deprecato, fa al caso nostro: se scriviamo /sbin/ifconfig eth0 infatti otteniamo qualcosa di simile a questo:

eth0      Link encap:Ethernet  HWaddr ba:bb:e0:ba:bb:e0
          inet addr:192.168.0.8  Bcast:192.168.0.255  Mask:255.255.255.0
          UP BROADCAST RUNNING MULTICAST  MTU:1500  Metric:1
          RX packets:201005 errors:0 dropped:0 overruns:0 frame:0
          TX packets:136434 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:1000 
          RX bytes:212918027 (203.0 MiB)  TX bytes:18123529 (17.2 MiB)
          Interrupt:21 Memory:dffe0000-e0000000 

Ma a noi non interessa TUTTO quel testo, a noi basta il MAC address (che ifconfig chiama HWaddr): come facciamo ad ottenere solo quello?

Per prima cosa osserviamo la struttura di un MAC address e vediamo che è formata da 6 gruppi di cifre esadecimali separate da dei due punti (:). Costruiamoci ora una regex che trovi questa particolare sequenza:

([0-9a-f]{2}:){5}[0-9a-f]{2}

Se avete problemi a leggerla significa che non vi siete impegnati nella lettura dell'articolo precedente (MOLTO MALE). Avrei potuto scrivere la regex diversamente, ma questa è la versione più breve che sono riuscito ad escogitare grazie all'uso dei quantificatori.

Abbiamo la regex e abbiamo il nostro input, passiamo tutto attraverso grep e vediamo cosa succede:

$ /sbin/ifconfig eth0 | grep ([0-9a-f]{2}:){5}[0-9a-f]{2}
bash: syntax error near unexpected token `[0-9a-f]{2}:'
$

Giustamente bash ci notifica che non sa cosa sia [0-9a-f]{2}:, rimediamo con un po' di quoting:

$ /sbin/ifconfig eth0 | grep '([0-9a-f]{2}:){5}[0-9a-f]{2}'
$

Nessun output... Abbiamo sbagliato qualcosa nella regex? Ni: ci siamo dimenticati che grep di default non riconosce i quantificatori, ma a questo si rimedia usando egrep (oppure indicando a grep che vogliamo usare le extended regular expressions tramite il flag -E):

$ /sbin/ifconfig eth0 | egrep '([0-9a-f]{2}:){5}[0-9a-f]{2}'
eth0      Link encap:Ethernet  HWaddr ba:bb:e0:ba:bb:e0
$

Meglio, ma non è abbastanza: abbiamo ancora troppo output. Questo perché di default grep ed egrep stampano le righe in cui c'è un riscontro positivo per la regex che gli passiamo. Fortunamente c'è un flag che ci consente di far stampare a grep solamente la parte di testo che corrisponde alla regex, si tratta del flag -o:

$ /sbin/ifconfig eth0 | egrep -o '([0-9a-f]{2}:){5}[0-9a-f]{2}'
ba:bb:e0:ba:bb:e0
$

Ottimo! Questo è il risultato che volevamo! Adesso possiamo usare quel one-liner all'interno di altri script bash per ottenere il MAC address di una scheda di rete e salvarlo in una variabile o in un file.

Ci sono diversi usi possibili di questo one-liner:

• Comporre un elenco di MAC address da inserire nella configurazione del server DHCP per ottenere delle assegnazioni statiche di indirizzi IP.
• Se si usa un sistema di installazione automatico tramite boot da rete si può notificare al server di installazione che tutto è andato a buon fine e che può rimuovere il nostro MAC address da quelli che devono essere ancora installati.
• Usando solo egrep e quell'espressione sui log del daemon DHCP si può costruire un database dei MAC Address che si sono connessi alla nostra rete.

Ad esempio eccovi uno script della shell che stampa a video tutti i MAC address delle interfacce di rete presenti nel sistema preceduti dal nome dell'interfaccia stessa:

#!/bin/sh
for IFACE in $(/sbin/ifconfig | egrep -o '^[a-z0-9]+')
    do
        MACADDR=$(/sbin/ifconfig $IFACE | egrep -o '([0-9a-f]{2}:){5}[0-9a-f]{2}')
        echo $IFACE $MACADDR
    done

Confido che lo script sia abbastanza breve e abbastanza semplice da poter essere compreso anche da chi non sa scrivere script della shell ma ha già una conoscenza di base di programmazione. Del resto il grosso del lavoro lo fa egrep filtrando adeguatamente l'output di ifconfig: prima ricavando il nome delle singole interfacce e poi estraendo i MAC address.

Bonus: questo script funziona anche su FreeBSD, NetBSD e OpenBSD (non ho un Mac su cui provarlo, ma credo che funzioni anche su Mac OS X).

Alcuni scripter di lunga data mi faranno sicuramente notare che richiamare tutte quelle volte ifconfig è superfluo: come compito per casa potete modificare quello script affinché prenda l'output di ifconfig all'inizio, lo salvi in una variabile e poi lo passi ad egrep tramite echo.

sed

sed è un altro dinosauro di UNIX: il suo nome è l'abbreviazione di stream editor ed è tutt'ora uno dei più potenti tool per il trattamento automatico dei file di testo nei sistemi operativi POSIX.

In sed le espressioni regolari sono usate in due contesti:

1. Per indicare un pattern che indichi la riga su cui agire.
2. Per indicare un pattern che indichi uno schema di sostituzione.

Vediamo più in dettaglio cosa intendo: supponiamo che vogliate eliminare da un file tutte le righe vuote (righe che contengono zero o più caratteri di spaziatura). Un'operazione del genere si fa abbastanza rapidamente con un editor di testo tradizionale (come nano, leafpad, gedit, kwrite, eccetera...) a patto che il testo non sia troppo lungo. Rifare l'operazione per una dozzina di file di testo da 10 kB l'uno comincia ad essere una cosa lunga, figuriamoci se i file fossero di più e/o più grandi...

Come si fa ad automatizzare questo compito con sed? La cosa è piuttosto semplice quando si scopre che il comando per cancellare una linea è d e che le linee da cancellare possono essere indicate da una regex racchiusa tra due slash (/). Tutto si riduce al seguente one-liner:

$ sed '/^[\ \t]*$/d' file_da_modificare > file_modificato

La regex non è molto difficile, ormai dovreste essere avvezzi alla lettura di quei simboli arcani. Tuttavia ci sono delle novità che non ho incluso nei miei articoli precedenti e che vale la pena di commentare.

La prima novità sono i delimitatori di inizio e fine riga (rispettivamente ^ e $). Questi delimitatori sono stati introdotti da sed e sono stati poi adottati anche da altri programmi che fanno uso delle espressioni regolari. Senza di essi il nostro pattern diventa troppo generico e finisce per individuare tutte le righe del file, così invece indichiamo esattamente tutte e sole le righe che contengono zero o più spazi o zero o più TAB del nostro file.

La seconda novità è meno eclatante: il simbolo \t non indica il carattere t ma il TAB. Assieme a \n che indica l'andare a capo è una delle sequenza di quoting più utilizzate. Analogamente lo spazio si indica con uno slash seguito da... Uno spazio! Ovviamente!

Se siete tra coloro che utilizzano il sed del progetto GNU avete anche un'utile estensione che permette l'editing in-place: tramite il flag -i è possibile indicare a GNU sed di modificare il file direttamente, senza passare per file intermedi. Io però tendo a non farne uso per due ragioni:

1. Potrei aver sbagliato qualcosa nell'impostare la regex per sed e mi ritroverei con un file corrotto ed irrecuperabile. 2. Non fa parte delle specifiche standard e può essere emulato con un successivo uso del comando mv sul file temporaneo.

La vera forza di sed però sta nel suo comando dedicato alla sostituzione. A differenza del comando per cancellare il comando per sostituire ha la seguente struttura:

/indirizzo/s/regex/sostituzione/flags

L'indirizzo è opzionale e può essere sia una regex che un numero non racchiuso tra slash. Nel primo caso ogni riga viene confrontata con la regex e se questa è verificata l'azione di sostituzione viene compiuta. Nel secondo caso solo la linea indicata viene coinvolta. Ad onor del vero è possibile indicare due indirizzi separandoli con una virgola (,). Per esempio 1,10 coinvolge le prime 10 righe del file mentre 10,/sed/ coinvolge le righe dalla 10 in poi ma solo quelle che sono comprese fino alla prima riga che contiene la stringa sed (occhio che la regex NON viene applicata alla decima riga che viene inclusa automaticamente tra le righe da trattare e la riga trovata dalla regex sarà processata anch'essa). È anche possibile indicare due regex ed in tal caso la prima regexp indicherà la riga da cui cominciare a processare e la seconda la riga in cui fermarsi.

La s indica il comando di sostituzione ed è seguita da una regex e da un pattern di sostituzione.

I flags modificano il comportamento del comando, ad esempio g indica di effettuare la sostituzione su TUTTI i match all'interno della riga (mentre il default è di fermarsi al primo match) mentre un numero indica che la sostituzione deve essere compiuta solo in quel match (ad esempio solo il secondo match saltando il primo).

Facciamo un esempio e prendiamo il caso descritto nel primo articolo della serie: convertire le date in formato statunitense (MM/GG/AAAA) in quello europeo (GG/MM/AAAA). Per prima cosa costruiamo l'espressione regolare che riconoscerà le date statunitensi:

(0[1-9]|1[0-2]?|[2-9])/(0?[1-9]|[1-2][0-9]|3[0-1])/([0-9]{4})

Anche in questo caso non commenterò la regex (vi lascio come compito per casa la verifica della correttezza della medesima). Sappiate però che i gruppi non sono stati scelti a caso, anzi capiremo presto come quella suddivisione sia essenziale per il nostro scopo.

Adesso decidiamo l'indirizzo: se lasciamo l'indirizzo vuoto sed opererà su tutte le righe in input. Se sappiamo che le righe contenenti le date da cambiare hanno una struttura particolare identificabile da un'espressione regolare possiamo usare quell'espressione come indirizzo, altrimenti affidiamoci al default.

L'ultima cosa da fare è decidere il flag: se vogliamo cambiare tutte le occorrenze che troviamo allora imposteremo il flag g, se sappiamo che le date da cambiare occorrono solo una volta per riga possiamo omettere i flag. Supponendo di voler cambiare tutte le occorrenze il nostro comando diventa:

sed 's/(0[1-9]|1[0-2]?|[2-9])\/(0?[1-9]|[1-2][0-9]|3[0-1])\/([0-9]{4})/pattern/g' nomefile

Questo comando legge il file indicato da nomefile, trova tutte le occorrenze della regex che gli abbiamo dato in pasto (notate come io abbia dovuto usare il backslash davanti agli slash per indicare a sed che la regex NON finiva lì) e stampa in standard output un testo che contiene la stringa pattern ogni volta che c'è stata un'occorrenza della regex.

Non male, ma adesso dobbiamo definire il nostro pattern di sostituzione. Ogni volta che sed incontra un gruppo crea una sotto-espressione e salva il risultato di quella sotto-espressione in un registro. Esistono 9 registri (numerati da 1 a 9, strano vero?) che possono essere usati nel pattern di sostituzione.

Nella nostra espressione il primo gruppo corrisponde al mese, il secondo al giorno e il terzo all'anno. Componiamo il nostro pattern invertendo i primi due e dovremmo aver finito:

sed 's/(0[1-9]|1[0-2]?|[2-9])\/(0?[1-9]|[1-2][0-9]|3[0-1])\/([0-9]{4})/\2\/\1\/\3/g' nomefile

Manca un ultima cosa: dobbiamo dire a sed che si tratta di un'espressione estesa (che fa uso dei quantificatori) tramite il flag di avvio -r:

sed -r 's/(0[1-9]|1[0-2]?|[2-9])\/(0?[1-9]|[1-2][0-9]|3[0-1])\/([0-9]{4})/\2\/\1\/\3/g' nomefile

sed può essere usato anche come se fosse grep tramite il flag -n che inibisce la copia dell'input non processato sullo standard output e il comando p che significa print, cioé stampa.

Ad esempio se volessimo stampare solo le righe che non cominciano con un # scriveremmo:

sed -n '/^[^#]/p' nomefile

Ovviamente grep ed egrep hanno più opzioni e consentono un controllo più fine sull'output.

Conclusioni

grep e sed consentono ad uno scripter di estendere la capacità di processamento dei file di testo della shell UNIX in modo considerevole grazie alla potenza delle espressioni regolari. Esistono però dei limiti: grep effettua solamente la ricerca (ma è molto veloce e può essere usato per filtrare solamente le parti interessanti dell'input), sed pur essendo Turing-equivalente (leggasi: in teoria ci si può scrivere qualsiasi programma che si può scrivere con un qualsiasi altro linguaggio di programmazione) non è molto comodo da utilizzare. L'utilizzo in script della shell consente di ovviare ad alcuni dei limiti della sintassi di sed ma genera un altro problema: la shell crea una marea di sottoprocessi (uno per ogni comando dato) e questo rallenta inevitabilmente l'esecuzione. Il linguaggio di sed inoltre ha memoria per una sola riga oltre a quella corrente e questo costringe a fare numerosi equilibrismi...

L'alternativa c'è, è molto potente ed ha alle spalle anni di sviluppo: si tratta del linguaggio di scripting perl. Purtroppo il perl è anche uno dei linguaggi più bizzarri e più ricchi di "cose strane" che vi possa capitare di incontrare. Fortunatamente per voi tutti i moderni (e anche alcuni meno moderni) linguaggi di scripting hanno un supporto più o meno complesso per le espressioni regolari: Tcl ce l'ha (ed è tra i più antichi), Python ce l'ha (tramite il modulo built-in re), PHP ce l'ha, Ruby ce l'ha, Javascript ce l'ha, Se ancora non foste convinti Java supporta le espressioni regolari tramite il package java.util.regex, per il C esistono le librerie PCRE che consentono di usare espressioni regolari compatibili con quelle del perl (il nome è infatti l'acronimo di "Perl Compatible Regular Expressions") oppure se intendete scrivere codice solo per sistemi POSIX-compatibili potete usare le regex POSIX (man 3 regex per maggiori info) infine per i fan del C++ oltre alle PCRE potete usare boost::regex delle librerie Boost.

Insomma non avete scuse per non usare le espressioni regolari quando si tratta di cercare degli schemi che si ripetono all'interno di flussi di testo!

Prima Parte
Seconda Parte

Algoritmi di sorting, questi sconosciuti

Bentornati sulle pagine di questo blog!
Cosa ci inventeremo stavolta per annoiarvi a morte? Sì, lo so, facciamo del nostro meglio ogni volta, e credo proprio che lo scopo sia quasi sempre raggiunto!
Oggi...oggi...oggi, di cosa volevo parlare? ...Ah si, algoritmi. Algoritmi di sorting.
Ok, parto dal presupposto che chi legga non sappia nulla, ma proprio nulla, nemmeno di algoritmi.

Bene, cos'è un algoritmo? Si definisce algoritmo un numero finito di istruzioni che, in un numero finito di passi, da un input finito iniziale A porta sempre e solo in uno stato finale B. Un classico esempio potrebbe essere l'algoritmo che calcola un numero della successione di Fibonacci. L'algoritmo riceve in ingresso n, e restituisce l'ennesimo numero della successione.
Passiamo ora al complemento di specificazione: “di sorting”. Sorting significa ordinamento, quindi parleremo degli algoritmi che cercano di ordinare una serie di oggetti (nel nostro caso numeri naturali) secondo una data relazione d'ordine (nel nostro caso ordine crescente).
Uno può benissimo chiedersi “ma che ca**o me ne faccio di sta roba?”, ma se vi fermaste un attimo a pensare, capireste subito che l'ordinamento (o la classificazione, più in generale) è alla base di praticamente tutte le attività umane.
Avete presente quell'ammasso informe di file di tipi diversi e con nomi assurdi che avete nella cartella Downloads del vostro pc? Immaginate se non esistesse quella splendida opzione "Ordina per...{tipo, nome, ultima_modifica, dimensione}"...vi sfiderei a trovare quel "xxx.avi" che tanto vorreste avere sottomano al momento!
Questo è solo un esempio marginale dell'importanza di tali algoritmi.

La domanda che porrei al lettore è la seguente: “hai 10 numeri naturali. Riesci a immagire un algoritmo per ordinarli dal minore al maggiore?”. Starete pensando “e se io non riesco a immaginare un algoritmo, ma solo donne nude?”; ammetto che sarebbe senz'altro una tesi ferrea la vostra.
Siccome sono convinto che prendereste questa sfida nella maggior parte dei casi sottogamba, essendo portati a pensare “e ci vuole un algoritmo per far sta roba?”, senza riflettere che se invece di 10 numeri fossero 100 milioni sarebbe un attimo più complicato, vi indico direttamente qualcuno tra gli algoritmi più famosi.

Non ho idea se qualcuno perderà davvero del tempo a pensarci, ma credo che la soluzione più banale, benché non sia il primo algoritmo che si studi solitamente, è quello che viene chiamato Selection Sort.
Praticamente, esso ci dice di cercare all'interno della nostra sequenza il minimo, e metterlo come primo elemento. Dunque procedere scansionando gli n – 1 numeri rimanenti cercando il nuovo minimo, e avanti così. Dopo n – 1 scambi (l'ultima iterazione avrà un solo intero che sarà già il maggiore, evidentemente), la nostra sequenza sarà ordinata. Ha l'enorme vantaggio, rispetto ad altri algoritmi, di essere facilmente implementabile (ossia è molto facile da programmare), e di non avere caso migliore o peggiore, cioè il tempo impiegato dall'algoritmo dipende esclusivamente dalla lunghezza della sequenza che vogliamo ordinare, non dalla posizione di ciascun numero nella sequenza. Il numero di scambi è perciò fisso, ed è, come detto in precedenza, n – 1.
Questo algoritmo prevede quindi due cicli, uno esterno da i = 0 a n – 1; l'altro, interno, da i + 1 a n. Per un totale di n * (n – 1) / 2 confronti, ossia asintotico a n^2 (chiunque abbia studiato un minimo di calcolo infinitesimale sa che basta far tendere nell'espressione precedente n a infinito).

Il secondo algoritmo, anch'esso molto famoso, è il Bubble Sort (nome simpatico, eh?). Quest'ultimo prevede l'ordinamento “a bolla” della sequenza: viene definito prendendo a due a due gli elementi adiacenti della nostra sequenza e spostando a sinistra il minore, ad esempio:
3 1 2 → 1 3 2 → 1 3 2 → 1 2 3.
Sì, l'effetto “a bolla” lo vedrete solo dopo esservi fumati un cannone; cito wikipedia:

L'algoritmo deve il suo nome al modo in cui gli elementi vengono ordinati, con quelli più piccoli che "risalgono" verso le loro posizioni corrette all'interno della lista così come fanno le bollicine in un bicchiere di spumante.

Evidente no?
Questo algoritmo è noto per essere il primo che si studia, nonché mediamente il più inefficiente battuto solo dallo stupid sort, che consiste nel continuare a mischiare a casaccio gli elementi finché non ne esce fuori una sequenza ordinata (una bella presa per il culo eh!). D'altra parte è risaputo che localmente l'entropia possa diminuire, perciò perché non tentare?
Il Bubble Sort differisce tra caso migliore e peggiore. Il caso medio asintoticamente è molto simile al peggiore. Prendiamo come caso migliore una sequenza già ordinata: il Bubble Sort non farà alcuno scambio, ma dovrà comunque fare circa n^2 confronti (come il precedente Selection Sort).
Vale lo stesso numero di confronti anche per gli altri casi, ma il numero di scambi nel caso medio e peggiore sarà sempre nell'ordine del n^2 (contro gli n – 1 del precedente algoritmo). Come caso peggiore si prende una sequenza ordinata in maniera opposta a come la vogliamo noi (ad esempio, vogliamo ordinare in maniera crescente una sequenza già ordinata in maniera decrescente). Appare evidente che il primo ciclo porterà, attraverso n - 1 scambi, il primo elemento (il maggiore) in coda alla sequenza, poi toccherà al secondo, ecc ecc.

Ora direi che è il momento di vedere un algoritmo più complesso, per avere una vaga idea di quanto si sia arrivati ad astrarre e a congetturare.
Il Quick Sort si basa sul paradigma divide et impera, e prevede di spezzare la nostra sequenza in due parti, prendendo un perno a caso al suo interno; gli interi minori del perno staranno a sinistra e quelli maggiori a destra. Poi si va avanti a fare lo stesso su ciascuna delle due sequenze così create, finché non si arriva ad avere minisequenze ordinate. Quindi si unisce il tutto. Voi penserete “oltre a essere così incasinato, ha almeno dei vantaggi?”, e la risposta è affermativa. Questo algoritmo sfrutta perfettamente le capacità dei processori moderni di gestire il multithreading, e soprattutto si rivela l'algoritmo più efficiente tra quelli basati sul confronto degli elementi nella sequenza. Tranne nel caso peggiore, in cui ha le stesse prestazioni dei precedenti algoritmi, esso permette un numero di confronti notevolmente minore rispetto ad essi.
Prendiamo ad esempio la sequenza
4 7 1 5 3, dove il perno è sottolineato. Contiamo il numero di confronti e di scambi; in questo caso sarebbero 10/4 per Selection Sort e 12/6 per Bubble Sort). Con Quick Sort si ha:
3 1 4 7 5 → 4 confronti + 2 scambi. Ora spezziamo nelle due sotto sequenze e prendiamo dei nuovi pivot.
3 1; 7 5 , che diventano 1 3; 5 7 con altri 2 confronti e 2 scambi.
Ora siamo già pronti a riordinare il tutto, dopo solo 6 confronti e 4 scambi!
Ovviamente è solo un esempio preso appositamente per far notare le differenze (anche se rientra nella casistica media), ma si può intuire come su enormi quantità di dati, quest'ultimo algoritmo risulti notevolmente migliore.

Inoltre è possibile migliorarne ancora l'efficienza scegliendo dei perni più adatti, calcolati attraverso procedimenti euristici.


"Oh! Suona la campanella...confido ragionevolmente, visto l'interesse della classe, che mi lascerete 2 minuti dell'intervallo per terminare il disc...ma no, fermi alunni, dove state andando! Sto concludendo la spiegaz..." 

"Si fotta, prof!"

"Lezione conclusa...sigh..."

Siete ancora convinti sia così inutile e banale ordinare una serie di oggetti?
Un ulteriore esempio di utilizzo di questi algoritmi, coniato dalla folle mente del Maestro Jedi +Gianfranco Gallizia, riguarda un elenco ordinato alfabeticamente; si vuole sapere in che posizione si trova la parola Xerxes. Idea stupida: si legge l'elenco da Abecedario a Zuzzurellone e ci si ferma quando si arriva a Xerxes. Idea meno stupida: si va direttamente a metà dell'elenco e si legge cosa c'è, se è Xerxes abbiamo finito altrimenti si confronta la parola e si decide se cercare nella prima metà o nella seconda ripetendo il procedimento.
Caso peggiore nella ricerca lineare (la prima idea): ci tocca leggere tutto l'elenco.
Caso peggiore nella ricerca binaria: ci tocca leggere un numero di elementi pari al logaritmo in base 2 della lunghezza dell'elenco.
Cosa cambia? Negli elenchi brevi (3 o 5 elementi) nulla (o quasi), negli elenchi di un milione di elementi, si passa da un milione di letture a 20 letture. Se il tuo elenco è ordinato la ricerca binaria è un must. Se il tuo elenco non è ordinato e fai moltissime letture ti conviene ordinarlo prima.
Se si vuole poi un esempio ancora più concreto: ogni volta che ci si logga su un sito il server deve vedere se il nome utente che viene inserito è corretto e se la password associata corrisponde. Facebook ha più di un miliardo di utenti (attivi e non attivi) e deve fare questa ricerca ogni volta che un utente tenta il login.

Beh direi che con questi ultimi esempi si è chiarito perfettamente l'importanza di questi algoritmi che va molto oltre il campo dell'informatica, e che arrivano, in maniera del tutto trasparente all'utente (come d'altra parte lo è tutta l'informatica, e forse rappresenta il motivo per cui la trovo così splendida), a migliorare notevolmente tantissimi servizi che si utilizzano quotidianamente.
Che altro dire? Al prossimo noiosissimo articolo!
E intanto, buone ferie a tutti!

A proposito di TrueCrypt su Windows

Lo so che il nome del blog è GNUrants e che Windows dovrebbe essere bandito da queste pagine, non per questo non si deve cercare di migliorare l'esperienza di utilizzo del Sistema Operativo di Redmond ricorrendo al Software Libero. Tra cui c'è anche il pacchetto di crittazione di partizioni e dischi rigidi TrueCrypt.

Recentemente TrueCrypt è stato al centro di una vicenda alquanto curiosa: la notizia non è proprio nuova (ma se leggete questo blog lo sapete che gli GNUrants si prendono il tempo necessario per scrivere bene i loro articoli) però, per chi vive sotto ad una roccia, sappiate che gli sviluppatori di TrueCrypt hanno deciso di interrompere lo sviluppo e lo hanno comunicato nella Home Page del progetto con tanto di guida su come si attiva BitLocker su Windows Vista/Windows 7.

La cosa buffa è che l'annuncio cita la fine del supporto a Windows XP come ragione della fine dello sviluppo di TrueCrypt ma è stato pubblicato quasi due mesi dopo la data dell'8 aprile 2014. La cosa ancora più buffa è che il 14 febbraio (San Valentino) è uscito il primo report dell'Open Crypto Audit Project: un progetto che, tramite il crowfunding, ha finanziato un audit completo del codice di TrueCrypt.

Siccome non sono molto bravo a speculare sulle ragioni politiche dietro le scelte operate dagli sviluppatori (lascio volentieri ad altri il compito di indossare cappelli di stagnola e puntare il dito verso i Tagliapietre di turno) mi limiterò a fare quello che mi riesce meglio: un'analisi tecnica di quello che hanno trovato gli ingegneri che hanno compiuto l'audit.

Questo primo report si è concentrato sul bootloader (il componente che permette l'avvio del computer da un volume criptato, essenziale per la FDE - Full Disk Encryption - ovvero la crittazione dell'intero disco, Sistema Operativo e Programmi inclusi).

Il report in questione è protetto da Copyright e non si può riprodurre in tutto o in parte senza l'esplicito consenso scritto di iSEC Partners Inc. Il progetto Open Crypto Audit però, in qualità di committente, ha deciso di rendere pubblico il PDF del report all'indirizzo seguente:

https://opencryptoaudit.org/reports/iSec_Final_Open_Crypto_Audit_Project_TrueCrypt_Security_Assessment.pdf

Chi non avesse tempo/voglia di leggere le 32 pagine del documento (e di studiare diversi libri su programmazione in C, crittografia, API di Windows ecc. ecc.) può leggere le righe seguenti per avere sott'occhio la versione TL:DR.

Il PDF chiarisce fin da subito che non ci sono vulnerabilità critiche in TrueCrypt, ma ci sono delle vulnerabilità nel bootloader che potrebbero essere sfruttate da un attaccante seriamente motivato a carpire i segreti gelosamente custoditi sul disco criptato.

Fine del TL:DR, ora si fa sul serio.

I due ingegneri che hanno preso visione del codice hanno trovato 8 vulnerabilità di grado medio e basso e 3 problemi che, pur non essendo delle vere e proprie vulnerabilità potrebbero essere fonti di vulnerabilità in futuro. Le vulnerabilità trovate sembrerebbero essere non intenzionali e frutto di errori nella scrittura del codice anziché di un deliberato atto di sabotaggio volto all'inserimento di backdoor (pagina 7 del report, ultimo paragrafo).

Gli 11 problemi rilevati sono poi stati classificati e ordinati in base a gravità e quindi presentati dal più grave al meno grave. Vediamo ora i quattro più gravi nell'ordine presentato dai relatori.

Algoritmo di derivazione della chiave per il Volume Header debole

Cominciamo col dire cosa si intende per "algoritmo di derivazione della chiave". In crittografia si definisce chiave una porzione di informazione (quasi sempre una sequenza di bit) che, opportunamente utilizzata, consente di passare da un messaggio in chiaro (leggibile) ad uno criptato (non leggibile). Gli algoritmi di derivazione della chiave prendono in input una porzione di informazione nota all'utente (la password), un sale (un'altra porzione di informazione nota ma che solitamente varia ad ogni utilizzo) e li utilizzano per ricavare una chiave crittografica in modo tale che sia difficile risalire alla password se si conosce solo il messaggio criptato.

TrueCrypt utilizza PBKDF2 come algoritmo di derivazione delle chiavi, lo stesso usato dal protocollo WPA2 per la criptazione delle comunicazioni WiFi. Affinché questo algoritmo sia sicuro occorre che il numero di iterazioni (ovvero il numero di volte in cui si ripete l'operazione di derivazione della chiave) sia piuttosto alto. Quanto alto? Difficile a dirsi: gli attacchi di tipo bruteforce sono tanto più efficaci quanto è più facile parallelizzare l'operazione di generazione e test delle chiavi. Con le potenze di calcolo delle attuali GPU ricavare una password da un singolo giro di MD5 può richiedere da pochi secondi a un minuto: due ATI radeon HD4870 in CrossFire hanno la capacità di generare 4 miliardi e 600 milioni di hash MD5 al secondo (fonte: http://www.golubev.com/about_cpu_and_gpu_2_en.htm ). Per contrastare una simile potenza di calcolo (che richiede un investimento inferiore ad un migliaio di Euro al momento in cui scrivo) sarebbero necessarie svariate centinaia di migliaia di iterazioni di PBKDF2. TrueCrypt usa un numero di iterazioni che va da 1000 a 2000 a seconda dei parametri scelti dall'utente.

La soluzione proposta nel breve termine è consentire all'utente di impostare manualmente il numero di iterazioni, quella a lungo termine di cambiare l'algoritmo di derivazione della chiave con un algoritmo che sia più ostile nei confronti delle GPU.

Informazioni sensibili potrebbero essere salvate nello swap

Nel caso in cui l'utente non abbia optato per la FDE ma solo per la criptazione di una porzione del disco sussiste il problema dei file di paging (o file di swap): quando la memoria RAM per i programmi in esecuzione si esaurisce il Sistema Operativo sposta alcune porzioni di memoria non utilizzate dalla RAM al disco rigido.

Un malintenzionato può causare una situazione in cui la vittima esaurisca la memoria RAM e, in un secondo tempo, ricavare informazioni sensibili (compresa la password per sbloccare i dati) dal file di paging.

TrueCrypt attua diversi meccanismi per prevenire questo, ma ci sono comunque dei casi in cui è possibile che ciò avvenga. Gli stessi sviluppatori sconsigliano di utilizzare TrueCrypt in questa configurazione e dicono chiaramente che l'utente dovrebbe optare per la criptazione dell'intero disco, compreso il file di paging.

A mio avviso questo è un non-problema: se uno è abbastanza paranoico da decidere di aver bisogno di TrueCrypt lo sarà anche abbastanza da usare la FDE e chiudere quindi la possibilità ad un malintenzionato di sfruttare lo swap.

Problemi multipli nello scompattatore del bootloader

Questo è un punto interessante, non per la vulnerabilità che espone ma per gli indizi che porta sulla qualità del codice del bootloader di TrueCrypt (tanto che i relatori hanno dedicato un'intera appendice a commentare i problemi che hanno rilevato nel modo in cui è scritto il compressore del bootloader e un'altra appendice alle problematiche che hanno riscontrato nel qualità con cui è scritto il resto del software).

In sintesi il codice che si occupa di decomprimere la porzione principale del codice del bootloader (quella che chiede all'utente la password e decripta il contenuto del disco) soffre di diversi problemi di programmazione:

• Mescolanza di tipi signed e unsigned.
• Accesso ad array senza controllare se ci si trova entro i limiti dell'array (con accesso a porzioni di memoria che non fanno parte dell'array stesso e relativi problemi).
• Mancanza di controlli sui valori di ritorno per la presenza di codici di errore.

Questo genere di errori non ci dovrebbero essere in un software che si presume orientato alla sicurezza (e quindi al rigore del codice).

Uso di memset() per la pulizia di dati sensibili

Questo è un meta-problema nel senso che non è un problema di sicurezza esplicitamente dovuto al codice ma si presenta quando i compilatori fanno i furbi ed eliminano codice che loro considerano inutile.

Supponiamo di avere un codice simile:

char* roba_importante = calloc(sizeof(char), LUNGHEZZA_ROBA_IMPORTANTE);

/*Fai qualcosa con roba_importante*/

memset(roba_importante, 0, sizeof(roba_importante));

free(roba_importante);

La chiamata a memset ha lo scopo di pulire lo spazio di memoria di roba_importante prima di rilasciare la memoria con free(roba_importante);. Non vogliamo che altre porzioni del programma (o peggio ALTRI programmi) accedano a quelle informazioni e quindi le cancelliamo.

Il problema è che i compilatori di adesso sono tarati per produrre codice che giri velocemente e quindi effettuano tutta una serie di ottimizzazioni tra cui l'eliminazione di codice ritenuto inutile. Quando il compilatore vede che noi liberiamo roba_importante e non la utilizziamo più lui elimina la chiamata a memset perché così il programma girerà più velocemente. Peccato che quella chiamata noi non la vogliamo eliminare perché ci serve a proteggere delle informazioni importanti.

La soluzione a questo problema consiste nel utilizzare altre funzioni scritte ad hoc per la pulizia della memoria (come explicit_bzero() di OpenBSD). Gli sviluppatori di TrueCrypt hanno scritto la funzione burn() a tale scopo ma ci sono porzioni di codice che non ne fanno uso (probabilmente rimasugli di vecchio codice oppure contributi di codice da altre fonti che non sono stati adeguatamente adattati prima dell'inserimento nella base di codice principale).

Conclusioni

Il codice di TrueCrypt non sembrerebbe contenere vulnerabilità critiche, ma questo non è una ragione per festeggiare: il codice andrebbe ripulito e ricontrollato per eliminare diversi problemi dovuti probabilmente a distrazioni degli sviluppatori. Inoltre il codice per essere compilato sotto Windows dipende da un mix di vecchi compilatori Microsoft (VC++ 1.52 rilasciato nel 1993!) e tools di GNU portati sull'OS di Redmond. Una simile toolchain, oltre ad essere difficile da installare e configurare, richiede di accedere a risorse online che potrebbero scomparire (quanti di voi sanno da dove scaricare una versione così vetusta di Visual C++?).

Forse gli sviluppatori di TrueCrypt sapevano che non avrebbero passato l'audit e si sono ritirati dalla competizione. Ma molto probabilmente non lo sapremo mai perché hanno fatto di tutto per restare anonimi.

Perché usiamo GNU/Linux?

Ciao a tutti!
Vi siete mai chiesti, voi che leggete questo blog dal caldo e accogliente focolare di windows 7/8.1 (magari da Internet Explorer), cosa diavolo possa aver deviato le nostre menti per farci utilizzare questo puzzle di software follemente sviluppati?
Bene, spero che in questo articolo troverete pane per i vostri denti.

Sarò breve e circonciso (ogni allusione a str***ate dette in luoghi poco consoni è puramente casuale)

1. Lo ammetto, mi avete beccato. Sono un fottuto comunista, che ci devo fare?
   Se quell'ideologia dovesse significare ancora qualcosa (ne dubito fortemente), questo sarebbe l'unico ambito in cui ancora è sopravvissuta. Si può essere d'accordo o meno, ma io la trovo una cosa fantastica.
   Ehm, fin qua son stato fin troppo politico...cambierò tono, scusate!
   Il modello di sviluppo del software Open, tralasciando la cavolata (ammesso che lo fosse) appena detta, è incredibilmente rapido, cooperativo (per definizione), sicuro (mmh incubi recenti?) e, forse la questione più significativa, libero e creativo, il che spesso gioca a sfavore purtroppo.
2. Linux, inteso come solo kernel, è stabile; ha un ciclo di rilasci molto breve che fixa bug e aggiunge funzionalità di continuo. Molto più rapidamente di qualsiasi altro sistema operativo proprietario. Risulta inoltre incredibilmente scalabile, può funzionare su hardware datatissimo, così come su supercomputer.
3. L'architettura del filesystem di linux è, in maniera assoluta e certa, per progettazione, più sicura di quella ad esempio di Windows. 
4. Hai un problema? Riscontri un bug?
   Ebbene hai la comunità più attiva che esista disposta ad aiutarti! E se sei abbastanza bravo da fixartelo da solo, puoi condividere la tua soluzione con tutti gli altri!
5. Le battaglie filosofiche. :) Sono stupende...da ultima quella pro/contro systemd. Ma ce ne sono state tantissime!
   Ravvivano la giornata, divertono e insegnano a rispettare (alcune volte...) il punto di vista e le idee delle altre persone.
6. L'utente è libero. Prendi il tuo sistema e facci quello che vuoi. E non parlo solo dal punto di vista grafico (DE ecc ecc), parlo di tutto il sistema operativo. Qualsiasi cosa tu voglia modificare, hai la possibilità di farlo...certo se sbagli ne paghi le conseguenze (quante reinstallazioni i primi mesi!).
   E sei anche libero di scegliere, hai un'enorme (troppa spesso) varietà di software tra cui scegliere! Non vi siete mai chiesti perché diavolo dobbiate usare un ambiente desktop confezionato da altri per voi, invece di crearvi voi il vostro? Perché dovreste lasciare ad altri di stabilire il modo con cui voi interagirete col vostro pc? Fanculo, il pc è mio, e devo poterlo personalizzare.
7. Spesso si riesce a parlare direttamente con gli sviluppatori del software che stai utilizzando, dandogli suggerimenti, aiutandoli nel debug o direttamente nella programmazione.
8. Avere accesso a tutto il codice di qualsiasi software, per uno sviluppatore (anche se alle prime armi come me) è un sogno.
9. Sintesi di alcuni dei punti precedenti: sentirsi al centro del progetto, sentirsi importante nello sviluppo software, e non utente passivo che raccoglie solo i frutti del lavoro dei programmatori.
10. Gloria, gloria, gloria all'Ipnopinguino...

E per concludere...

Qualcuno usava Linux perché aveva avuto una educazione troppo closed. 
Qualcuno usava Linux perché glielo avevano detto.
Qualcuno usava Linux perché non gli avevano detto tutto.
Qualcuno usava Linux perché prima… prima…prima… usava Windows.
Qualcuno usava Linux perché aveva capito che l' opensource andava piano, ma lontano.
Qualcuno usava Linux perché era così ateo che aveva bisogno di un altro S.O. .
Qualcuno usava Linux perché “driver video dignitosi?” “oggi no, domani forse, ma dopodomani sicuramente”.
Qualcuno usava Linux per fare rabbia a suo padre.
Qualcuno usava Linux per moda, qualcuno per principio, qualcuno per frustrazione.
Qualcuno usava Linux perché aveva scambiato K&R per il Vangelo secondo Stallman.
Qualcuno usava Linux perché non c'era niente di meglio.
Qualcuno usava Linux perché non sopportava più quella cosa sporca che ci ostiniamo a chiamare software proprietario.
Qualcuno credeva di usare Linux, e forse usava qualcos'altro.
Qualcuno usava Linux perché aveva bisogno di una spinta verso qualcosa di nuovo.

Niente, son proprio comunista. Non c'è nulla da fare...

Quel pasticcio di Heartbleed

L’Antefatto Il giorno primo gennaio 2011 viene dato l’ok per l’inclusione di una porzione di codice relativa ad una feature del protocollo TLS all’interno della libreria OpenSSL. Tale feature era un’estensione del protocollo volta a consentire a due server TLS di comunicare tra loro dei dati e verificare che la connessione tra i due fosse stabile. Tale estensione fu standardizzata nel febbraio 2012, ovvero più di un anno dopo l’inclusione del codice, nel RFC 6520.

In quella porzione di codice però, per un malaugurato errore, non era stato inserito un controllo di congruenza tra la quantità di dati inviata e quella richiesta.

7 aprile 2014
Viene diramato il comunicato che una nuova versione di OpenSSL è stata rilasciata e che gli utenti della libreria sono caldamente invitati ad effettuare l’upgrade per mitigare gli effetti della vulnerabilità indicata dal codice CVE-2014-0160 (Heartbleed).

Dal 8 aprile in poi
Viene aperto il sito ufficiale di Heartbleed [heartbleed.org] e il panico si diffonde nella rete: siti e blog tecnici disquisiscono sulle possibili implicazioni del bug Heartbleed mentre nel resto dei media si diffonde l’allarme sulle possibili fughe di password e altri segreti.

Le conseguenze
Il bug Heartbleed ha avuto un notevole impatto, specialmente emotivo, ma se cerchiamo materiale in merito in lingua italiana troviamo ben poco… Anche la pagina di Wikipedia in merito è decisamente scarna…
Per ovviare un po’ a questa lacuna (e perché lo stesso blog degli GNUrants è ancora molto scarno) vi esporrò (al meglio delle mie capacità) quello che ho appreso sul bug in questione e sul suo impatto dal punto di vista tecnico per poi passare ad esporre alcune considerazioni sul come si è arrivati a tutto questo e su quali passi ritengo si debbano prendere per ridurre la probabilità che si verifichi di nuovo una simile situazione (alcuni di questi passi sono già stati intrapresi, altri richiedono tempi molto più lunghi).

Giochiamo con l’input
Cominciamo col catalogare Heartbleed e col descrivere di che genere di vulnerabilità si tratta…
Per prima cosa dobbiamo studiare un po’ la feature Heartbeat del protocollo TLS e capire cosa fa e in questo ci viene in aiuto Randall di XKCD (immagine omessa per questioni di Copyright): in breve l’Heartbeat è un meccanismo per chiedere ad un server TLS se è ancora vivo in una maniera simile al caro buon vecchio ICMP Echo Request/Echo Response. Il problema è che, nell’implementazione di OpenSSL è possibile forgiare un pacchetto che abbia un messaggio breve ma che richieda una risposta lunga e la libreria, invece di ignorare tale richiesta malformata, provvederà ad allocare abbastanza spazio nella memoria per mandare indietro la risposta.
“E questo è un problema?” E’ un problema nel momento in cui in quella porzione di memoria ci sono informazioni sensibili che non verranno sovrascritte ma inviate a chi ha fatto la richiesta.
“Di che informazioni stiamo parlando?” In generale di qualsiasi informazione che sia presente nello spazio di memoria a disposizione di OpenSSL, il che può voler dire cose come:

• Traffico già criptato & spazzatura.
• Traffico non ancora criptato (token di autenticazione, email, comunicazioni VoIP).

Nel primo caso non ci sono informazioni utili subito disponibili all’attaccante, ma il secondo caso è tutta un’altra storia!

Andiamo più in profondità
Ok, è venuto il momento tanto atteso: adesso faremo un salto dentro al codice sorgente e vedremo un po' più in dettaglio cosa ha causato tutto questo pasticcio. Come riferimento userò la patch rilasciata dai maintainer del progetto OpenBSD e la ragione è duplice:

1. E’ molto leggibile e ben documentata.
2. Va dritta al punto.

La parte iniziale è un commento su cosa si va a correggere e su come applicare la patch, segue la patch vera e propria in formato diff. Per chi non fosse familiare con i diff: le righe che cominciano con un “-” sono righe eliminate, quelle che cominciano con un “+” sono righe aggiunte e infine quelle che non hanno simboli all’inizio sono invariate. Noi ci concentreremo prima sulle righe con il “-”.
E adesso, finalmente, vediamo il codice C:

    /* Read type and payload length first */
    hbtype = *p++;
    n2s(p, payload);
    pl = p;

Ok, questa è una porzione di libreria che è stata tolta, il commento ci dà un indizio: “Read type and payload length first”.
Non abbiamo tutto il codice sorgente sotto gli occhi, ma è ragionevole supporre che p sia un puntatore ai dati del pacchetto TLS Heartbeat appena ricevuto e siccome il tipo è indicato nel RFC come intero a 8 bit (ma può assumere come valori solo 1 o 2) il nostro programmatore ha deciso di fare in fretta e fare due cose con un'unica istruzione: leggere il valore (salvandolo in hbtype) e portarsi al campo successivo con l'uso dell'operatore di post-incremento (il “++” dopo “p”) il “*” davanti a “p” è necessario perché altrimenti invece del valore leggeremmo l'indirizzo di memoria in cui questo si trova (e non ce ne faremmo nulla). Fin qui nulla di strano, si tratta di una pratica standard nella programmazione C anche se è malvista perché riduce la leggibilità del codice.
La linea di codice successiva è una chiamata alla funzione n2s: anche qui non abbiamo tutto il codice, ma possiamo ricavare dal contesto e dai parametri che gli vengono passati che quella funzione non faccia altro che leggere la lunghezza del messaggio di Heartbeat dal pacchetto e salvare tale lunghezza in payload. Notate bene: questa è la lunghezza dichiarata, non necessariamente la lunghezza reale del messaggio. Tenete bene a mente che non abbiamo alcuna garanzia che quello che ci viene detto corrisponda a verità e che il diavolo sta nei dettagli.
L'ultima riga serve a salvare un puntatore al messaggio vero e proprio in “pl”.

Segue una porzione che è rimasta invariata e che si occupa di controllare se è stata registrata una callback e di chiamare tale callback: le ragioni per cui si vuole poter chiamare una funzione esterna quando si comincia a processare un pacchetto possono essere le più varie, ma di solito lo si fa per avere un log per questioni di debug.

Dopo una sezione di codice aggiunto (che ignoreremo) abbiamo le righe seguenti:

    if (hbtype == TLS1_HB_REQUEST)
        {
        unsigned char *buffer, *bp;
        int r;
        /* Allocate memory for the response, size is 1 bytes
         * message type, plus 2 bytes payload length, plus
         * payload, plus padding
         */
        buffer = OPENSSL_malloc(1 + 2 + payload + padding);
        bp = buffer;
        /* Enter response type, length and copy payload */
        /*...Omississ...*/
        /* Random padding */
        RAND_pseudo_bytes(bp, padding);

        r = dtls1_write_bytes(s, TLS1_RT_HEARTBEAT, buffer, 3 + payload +
                        padding);
        if (r >= 0 && s->msg_callback)
            s->msg_callback(1, s->version, TLS1_RT_HEARTBEAT,
               buffer, 3 + payload + padding,
               s, s->msg_callback_arg);

        OPENSSL_free(buffer);

Allora, vediamo un po' cosa abbiamo qui… Questa riga qui è la radice del Male:

buffer = OPENSSL_malloc(1 + 2 + payload + padding);

OpenSSL è una libreria multipiattaforma, il che significa che deve girare su una gran varietà di Sistemi Operativi diversi. Alcuni di questi offrono meccanismi di protezione della memoria, altri no. Per avere una base comune gli sviluppatori di OpenSSL hanno creato una loro implementazione delle chiamate malloc e free: la prima riserva della memoria mentre la seconda la libera. Il problema di questo approccio è che, se non fai le cose per bene, puoi bypassare completamente i meccanismi che il Sistema Operativo adotta per proteggere la memoria e ridurre l’impatto che possono avere certi errori di programmazione.
La chiamata malloc fa parte della libreria standard del C e si appoggia a chiamate simili del sistema operativo per allocare (riservare) una porzione di memoria che un programma in esecuzione può utilizzare come meglio crede (anche condividendola con librerie e/o altri programmi in esecuzione). malloc può riservare aree di memoria precedentemente non utilizzate da altri programmi (bene) oppure aree di memoria già utilizzate da altri processi e da questi rese libere per il riutilizzo (male perché potrebbero ancora contenere dati) mentre OPENSSL_malloc riutilizza memoria pre-allocata dalla libreria stessa (molto male) e mantiene una sua lista delle allocazioni per poter far funzionare OPENSSL_free (la funzione che si occupa di liberare la memoria per il riutilizzo). Facendo così OpenSSL bypassa i meccanismi di ASLR (Address Space Layout Randomization) messi in atto dal kernel del Sistema Operativo per ridurre l'impatto di certi errori di programmazione.
Una discussione completa sui meccanismi di protezione della memoria esula dallo scopo di questo articolo, ma invito il lettore a dare un'occhiata alle slide che Theo DeRaadt ha proposto al ruBSD 2013 e, per i più curiosi, all'articolo in merito ad ASLR su Wikipedia.
Quello che succede in quella porzione di codice è che il programmatore si è fidato della lunghezza dichiarata dal pacchetto e ha riservato una porzione di memoria pari a quella lunghezza. Come già detto OpenSSL gestisce per conto suo la memoria e, siccome la memoria non è infinita, riutilizza la memoria. Nella porzione di codice precedente quella memoria non viene “pulita” prima di essere utilizzata e quindi potrebbe contenere qualsiasi cosa. Inoltre non vengono fatti dei controlli che il messaggio sia lungo quanto dichiarato.
Se il messaggio è più breve del valore dichiarato quello che succede è che viene occupata solo parte della memoria allocata e il resto viene spedito così com'è al richiedente.
C'è una piccola consolazione: il campo lunghezza consente di avere un payload che può essere lungo al massimo 65536 byte e occorre indicare almeno un byte per il messaggio portando la quantità di dati leggibili a dall'attaccante a 65535 byte (64 kilobyte). La probabilità di trovare dati utili in una finestra così stretta si abbassa molto ed occorre anche essere in grado di distinguere i dati utili dalla spazzatura (e gli algoritmi di generazione delle chiavi crittografiche fanno di tutto per far apparire le chiavi stesse come dati casuali apparentemente senza capo nè coda), ma è già stato dimostrato che avendo abbastanza pazienza (si parla di milioni di tentativi) si può leggere anche la chiave privata usata da un server web per decrittare TUTTE le comunicazioni criptate.

Conclusioni
Il bug in questione ha tutta l'aria di essere finito lì a causa di una svista: la feature era nuovissima (ancora in fase di standardizzazione) e in seguito è stata poco utilizzata (pochi hanno sentito il bisogno di usare il TLS Hearthbeat quando ci sono decine di altre tecniche di High Availability disponibili) per cui pochi occhi si sono concentrati su quel codice.
Sicuramente è significativo che anche nel mondo dell'Open Source ci siano casi di feature “aggiunte e dimenticate” che ricevono poca o nessuna manutenzione. Ed è significativo che il presupposto principale dello sviluppo a sorgente aperto (molti occhi che guardano il codice si accorgono prima di certi errori) sia venuto meno nel caso di una delle librerie più utilizzate per la comunicazione sicura di pagine web, posta elettronica e una moltitudine di altri servizi.
Ci si è fidati della buona volontà e delle capacità di chi ha scritto OpenSSL (persone che meritano la stima e il rispetto di tutti quanti noi per il lavoro svolto) senza ricontrollare e così un errore fatto in buona fede è finito per avere un impatto clamoroso su tutta l'infrastruttura su cui si basa il web 2.0. Non basta che il codice sia visibile a tutti: occorre che qualcun altro oltre agli sviluppatori ci dia un'occhiata ogni tanto.
Ricette magiche non ce ne sono, ma questo pasticcio ha senz'altro portato all'attenzione di tutti le falle presenti in OpenSSL e la necessità di rimettere a posto quel codice nel suo complesso (e non solo la parte relativa al bug Heartbleed).
Moltissime aziende utilizzano OpenSSL nei loro prodotti (grazie anche alla licenza molto liberale) e alcuni dei player più grossi si sono resi conto che forse è il caso di dare qualcosa indietro a quei quattro gatti che lavorano su quel codice così importante. La mia speranza è che (oltre a beccarsi enormi quantità di trolling) lo sforzo degli sviluppatori venga premiato e che altra gente cominci a pensare che non basta sviluppare un daemon DHCP nell'init system ma che c'è anche bisogno di mantenere e controllare quello che già c'è.

A proposito di systemd

Qualche tempo fa nel covo segreto degli Illuminati...

Gianfranco Gallizia
Non me n'ero accorto ma abbiamo una prima richiesta: un rant su systemd!
Chi di voi giovini vuole scriverlo? Io sono poco pratico di queste cose moderne! XD

Diego Pi
Iniziamo dal fondo: un server DHCP nell'init e log scritti in un formato binario non documentato che di fatto li rende closed.

Gianfranco Gallizia
Il fatto che systemd spezzi parecchie delle convenzioni di UNIX/POSIX? Non è un singolo tool che si integra col resto del sistema, ma un nuovo sistema che si appoggia al kernel Linux. Può essere un bene o un male, ma io sono un fan di POSIX perché ha passato la prova del tempo. systemd è un pischello.
Un'altra mia obiezione a systemd è la convinzione dei suoi sviluppatori di essere nel giusto. Leggevo l'altro giorno di un rant di Linus Torvalds in merito al fatto che hanno dovuto patchare il kernel in modo da celare in /proc/cmdline la stringa "debug" perché altrimenti systemd spara talmente tanta merda di logging da bloccarsi all'avvio e impedire il boot!
Se non è un "WTF!" questo...

Federico Di Pierro
Diego: ricordiamo che si può disabilitare tranquillissimamente, nessuno è forzato a usarlo.
Gianfranco: su Torvalds, dell'altro giorno, ho letto un po' e ti do ragione, ma errare è umano.
Systemd è un insieme di tool, tant'è vero che non è solo un init system, ma un "System and Service Manager", ha molte più funzionalità del vecchio init system standard. Ma funziona meglio, e questo è innegabile. In più in fase di compilazione si può togliere parecchia roba (ma non mi sono mai documentato su quanto si possa effettivamente non compilare). Ovviamente io stesso ho qualche dubbio sul fatto che quest'accentramento sia corretto...
A volte sembra di utilizzare GNU/linux/systemd ormai.
Ma provate a vederla come un utente: hai un sistema che boota in 5 secondi, hai dei servizi che sono altamente personalizzabili e facili da creare, hai un avvio di sistema gestibile molto semplicemente (systemctl enable/start...lo capirebbe chiunque)...
Capite anche voi che rompe tante convenzioni, ma l'altra faccia della medaglia è che regala tante innovazioni!

Fanfurlio Farolfi
Federico Di Pierro a me piace systemd, ho solo alcune cose da recriminargli...
Il fatto dei log scritti in formato binario ad esempio, lo trovo fastidioso, ma non del tutto inutile.
Se fosse documentato il formato, mi piacerebbe.

Gianfranco Gallizia
Federico d’accordo, ma capisci che cose come la questione del "debug" sono uno show-stopper per chi deve far funzionare dei servizi con il 99.98% di uptime? Non esiste che un flag di avvio del kernel mi schianti l'init system perchè quest'ultimo fa troppi log!

Diego Pi
Federico systemd mi piace... Sono le idiosincrasie che si porta dietro a tirarmi fuori WTF.
Peccato io veda poco sforzo per sistemare le poche scemenze che ha e tante energie spese a buttare dentro qualsiasi tipo di funzionalità.
Il bug tirato fuori da Gianfranco è patognomonico di ciò che dico. Non puoi fixare un bug di un tuo software proponendo una patch per il kernel.

Fanfurlio Farolfi
Aggiungerei "inutile" a "funzionalità", a che serve un server DHCP all'interno del sistema di init? Non bastava far partire prima quello installato?

Federico Di Pierro
Infatti lato kernel T. gli ha aperto il culo.
Però per me è normale sbagliare...poi Lennart ha sempre dovuto combattere tra insulti (ahimè anche personali) e altre cazzate. Ovviamente si è creata una "cerchia" PRO systemd e una CONTRO. Anche se a breve resterà l'unico init system ormai.
Diciamo che effettivamente, ed è ovvio, su alcune cose errano e spero correggano il tiro. Però per ora secondo me, come tecnologia, vale la candela. Qualche bug, qualche cazzata, ma era impensabile fino a qualche anno fa un init system del genere.

Gianfranco Gallizia
Poi c'è un altro potenziale problema che potrebbe manifestarsi con l'attuale politica di integrazione sfrenata di servizi attuata dagli sviluppatori di systemd. Mettiamo il caso che in uno dei vari sottosistemi di systemd ci sia un heap overflow che consenta di eseguire codice arbitrario in kernel space: ci sarebbe un'ecatombe.
Il vecchio init, per quanto brutto e lento, è troppo semplice per consentire un simile approccio. systemd dal'tro canto ha già costretto a riscrivere parti del kernel Linux per adattarsi alle sue esigenze e chi mi dice che in tutte le migliaia di righe di codice che stanno scrivendo per aggiungere server DHCP, connessioni di rete up in 500 nanosecondi e PoetteringSaCosa non ci sia un bug nascosto che si verifica solo in determinate condizioni ma che possa essere sfruttato per fini oscuri?
Dunque: qual è il verdetto della giuria?

Federico Di Pierro
Systemd ha solamente bisogno di tempo per maturare per bene. Credo che voi abbiate ragione quando parlate insistentemente di bugfixing al posto di continuare a buttarci dentro roba (a volte anche “inutile” per un init system)...mi ricorda un po’ Gnome (e vai di flame!!) anche se qua almeno per fixare i bug non rimuovono le feature! :D
In compenso, come già detto e sottolineato, è talmente più avanzato dei vecchi init che mi vien da pensare: “a me cazzo me ne frega a me, c’ho il diesel!”.

Dissolvenza… Seguono rumori di una violenta collutazione...

Chi sono gli GNUrants?

Salve a tutti e quattro i nostri lettori! Scrivo queste poche righe a nome e per conto degli GNUrants per dare due o tre informazioni in merito a questo piccolo angolo della vasta, sconfinata e sorvegliata internet (ciao NSA!).

GNUrants deriva da un gioco di parole tra "GNU rants" (ovvero lamentazioni/invettive/discorsi enfatici relativi a GNU) e l'espressione dialettale "'gnurant" (ignorante). Gli GNUrants sono quindi invettive prodotte dalle menti di ignoranti autoproclamatisi tali in merito a GNU/Linux, Software Libero, Informatica e in generale qualsiasi altra cosa che ottenga l'approvazione della maggioranza degli Illuminati... ehm... degli autori e degli editor del Blog.

Un'ultima nota: non vi aspettate cose come articoli con cadenza periodica scritti con un vocabolario che rispetti l'Etichetta e il Protocollo di Buckingham Palace: in fin dei conti siamo o no degli GNUrants? ;-)

P.S.: FOTTETEVI STRONZI!