tag:blogger.com,1999:blog-13609318572342915242024-03-05T17:20:35.499+01:00GNUrantsRant, guide scadute e articoli informatici inusualiAnonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-1360931857234291524.post-84834408981621564732016-04-20T20:43:00.001+02:002016-04-21T08:00:09.454+02:00Costruire un sistema di monitoring scalabile<div style="text-align: justify;">
<p>Salve o miei due lettori (suppongo che la lunga pausa abbia fatto calare drasticamente il numero di lettori di questo blog) in questo articolo tratterò per sommi capi di un argomento squisitamente tecnico dimezzando ulteriormente il numero di lettori. Tale argomento sarà la costruzione di un sistema di monitoraggio scalabile.</p>
<p>Per monitoraggio si intende l'attività di raccolta, archiviazione, costruzione di statistiche, visualizzazione (ed eventualmente allerta in caso di anomalie) di uno o più host (computer connessi tramite una rete TCP/IP) eventualmente distribuiti su più siti geografici. In breve: pornografia per ingegneri di reti (<em>network engineers</em> per gli anglofili).</p>
<p>L'aggettivo scalabile presuppone che la soluzione proposta sia in grado di trattare altrettanto bene uno, dieci, cento, mille, diecimila o più host e che quindi si adatti al serverino domestico come alla rete di datacenter di MEGA_CORPORAZIONE_A_CASO.</p>
<p>Si badi bene che le tecniche che andrò a descrivere possono essere utilizzate con gli opportuni aggiustamenti anche in altre situazioni in cui occorre raccogliere ed elaborare delle misure da un numero imprecisato di entità.</p>
<p>Come potete immaginare il problema è estremamente complesso e particolarmente sentito (specialmente all'aumentare del numero di host da monitorare) e quindi vi sono un numero non indifferente di soluzioni sia a sorgente aperto che proprietarie che sviluppate ad-hoc per una determinata infrastruttura/applicazione (a.k.a. <strong>LA</strong> collezione di script costruita nel corso di anni dal guru di turno che nessun altro sa come far funzionare). Non andrò ad elencarle tutte (del resto non mi è possibile compilare un elenco esaustivo perché non ho modo di venire a conoscenza di <strong>TUTTE</strong> le soluzioni ad-hoc) ma mi limiterò a dare delle linee guida generali che potrete adoperare per valutare le varie proposte pre-esistenti ed eventualmente decidere se imbarcarvi nell'ennesima reinvenzione del treno merci (un sistema di monitoring è troppo complesso per la metafora della ruota).</p>
<h2 id="le-premesse">Le premesse</h2>
<p>Come prima cosa occorre stabilire esattamente <strong>cosa</strong> si vuole monitorare, quali sono i <strong>parametri</strong> in gioco e quali <strong>statistiche</strong> si vogliono raccogliere. Senza queste informazioni il problema è talmente vago e aperto che una soluzione vale l'altra perché qualsiasi prodotto o pila di prodotti sceglierete vi renderà scontenti per un motivo o per l'altro.</p>
<p>L'unica cosa da tenere a mente è che se vogliamo che la soluzione scali e sia affidabile dobbiamo tenere a mente due principii fondamentali:</p>
<ol style="list-style-type: decimal">
<li>Distribuzione del carico.</li>
<li>Ridondanza.</li>
</ol>
<p>In virtù di questi principii eviteremo categoricamente le soluzioni in cui c'è un ente centrale che contatta direttamente le entità da monitorare: è un'infrastruttura che introduce una debolezza fatale perché accentra il carico (violando il primo principio) ed elimina la ridondanza (per definizione un sistema ridondante ha più componenti di quante strettamente necessarie al suo funzionamento ordinario in modo tale da compensare i guasti) creando un <em>single point of failure</em> (leggasi: se va giù lui va giù tutto).</p>
<p>Basandoci sui due principii possiamo tracciare delle linee guida da seguire:</p>
<ul>
<li>La raccolta dei dati sarà decentralizzata e si procederà a pre-processare quanto più possibile sui nodi remoti.</li>
<li>Dove possibile si adotteranno tecniche di funnelling (dall'inglese <em>funnel</em> ovvero imbuto) dei dati raccolti.</li>
<li>A seconda della volontà di salvare i dati monitorati a medio e lungo termine, delle dimensioni del carico e delle previsioni di crescita del carico stesso sarà necessario scegliere il tipo di database da utilizzare per il salvataggio dei dati (od optare per nessun database se non si desidera salvare i dati).</li>
</ul>
<h2 id="raccogliere-i-dati">Raccogliere i dati</h2>
<p>Basta con la fuffa generica! Adesso ci andiamo giù pesante con la fuffa (un po' più) specifica!</p>
<p>Abbiamo deciso che i dati saranno raccolti in maniera decentrata da tante piccole entità che chiameremo agenti (ma possiamo benissimo chiamarli in qualsiasi altro modo purché non sia protetto da Copyright). È fondamentale che gli agenti siano piccoli perché non vogliamo che impattino negativamente sui dati che vogliamo raccogliere, tuttavia (grazie anche agli smartphone) al giorno d'oggi è possibile comprare per poche decine di euro al pezzo macchine piccole quanto pacchetto di sigarette con una dotazione di RAM ed un processore più che adeguati per far girare un sistema GNU/Linux da dedicare alla raccolta dati e i processori multicore e multithread ci assicurano che (se non siamo particolarmente idioti nello scrivere i nostri agenti) solo nelle condizioni di carico estreme non ci sarà la possibilità di far girare il nostro agente su un server da monitorare per cui le scelte possibili sono più ampie che in passato (nei limiti del ragionevole).</p>
<p>Un solo appunto: mi dispiace per i fan di JRuby, ma avere una Virtual Machine che esegue codice Ruby ricompilato in Java <strong>non è una soluzione leggera</strong>: fatevene una ragione.</p>
<p>Detto questo vediamo quali sono le alternative per i nostri agenti.</p>
<h3 id="shell-script">Shell script</h3>
<p>La cara buona vecchia shell che troviamo in (quasi) ogni installazione di GNU/Linux è il primo strumento a cui dovrebbe pensare un sistemista quando si tratta di scrivere un tool che faccia monitoraggio dei log. Aggiungiamo <code>awk</code> e <code>netcat</code> (anche noto come <code>nc</code>) ed avremo un potente strumento nelle nostre mani. Giusto? Purtroppo in realtà non è così semplice...</p>
<p>Partiamo dalla prima pecca della shell: se scrivo uno script <code>bash</code> che usa <code>awk</code> e <code>nc</code> dovrò installare questi tre programmi in ogni macchina da monitorare. Idem dicasi per qualsiasi altra dipendenza di cui posso aver bisogno.</p>
<p>Seconda pecca della shell: avvia un processo per ogni tool che chiama all'infuori dei suoi builtin. Una riga come questa avvia ben tre processi (a cui si aggiunge la shell):</p>
<pre><code>grep espressione $miofile | tail -n 100 | cut -d ',' -f 3</code></pre>
<p>E sebbene sia possibile fare tutto con <code>awk</code> (anche il tail delle ultime 100 righe) il risultato è alquanto ostico per i non iniziati:</p>
<pre><code>awk -F',' '/espressione/{ o[NR % 100] = $3 } \
END{ i=(NR < 100 ? 0 : NR); \
do print o[++i % 100]; while(i % 100 != NR % 100)}' $miofile</code></pre>
<p>So cosa state pensando: le lettere sono quelle del nostro alfabeto ma la lingua è quella di Mordor. Non posso darvi torto.</p>
<p>Questo ci porta alla terza pecca della shell: per quanto sia potente la sintassi e le idiosincrasie di certi tool sono tali per cui sono in pochi a poterci lavorare con profitto senza impazzire.</p>
<h3 id="python">Python</h3>
<p>Python ha conquistato sempre più proseliti nel corso degli ultimi 15 anni per cui <strong>deve</strong> essere una via percorribile per la scrittura del nostro agente. Ed in effetti Python è una buona proposta sotto molti punti di vista:</p>
<ul>
<li>Ha una sintassi comprensibile (il più delle volte).</li>
<li>Possiede una nutrita comunità di utenti che hanno sviluppato codice di ogni genere e per ogni scopo.</li>
<li>Batte la shell in quanto a velocità di esecuzione.</li>
</ul>
<p>Quindi dichiariamo Python vincitore e chiudiamo la questione? Ni.</p>
<p>Il primo problema contro cui ci scontriamo è: "quale versione di Python posso/devo utilizzare?". La risposta a questa domanda non è banale. A tutt'oggi ci sono due versioni del linguaggio attivamente utilizzate: la versione 2 e la versione 3. La prima è la versione storica di Python, presente in numerose distribuzioni ed utilizzata in un ampio raggio di progetti con diverse estensioni per l'interprete di riferimento (CPython), la seconda è la versione attuale del linguaggio e presenta parecchi cambiamenti rispetto alla precedente sia in termini di sorgenti Python che di interfaccia dell'interprete. Per aiutare chi deve migrare i propri sorgenti Python esiste il tool 2to3, disgraziatamente il tool automatico non copre tutte le possibili amenità a cui si può andare incontro. Per chi volesse approfondire l'argomento il mio consiglio è di leggere l'ottimo articolo di Peter A. Donis ed Eric S. Raymond: <a href="http://www.catb.org/esr/faqs/practical-python-porting/">Practical Python porting for systems programmers</a>.</p>
<p>CPython inoltre non è l'unica implementazione di Python disponibile (sebbene sia la più completa, stabile e maggiormente supportata).</p>
<h3 id="tcl">Tcl</h3>
<p>Qui tocchiamo un tasto dolente. Io sono un fan del Tcl, ma sono anche dolorosamente cosciente del fatto che il Tcl ha perso la guerra dei linguaggi di programmazione una ventina di anni fa e se n'è reso conto circa una decina di anni fa.</p>
<p>L'interprete Tcl è meno esoso di memoria rispetto a CPython, il linguaggio è molto espressivo (con dei tocchi di LISP qui e là) ed ha un'ottima astrazione per i socket di TCP/IP. Peccato che quelli che lo conoscano si dividano in due categorie:</p>
<ul>
<li>Barbuti sistemisti con qualche anno sulle spalle che lo associano a lentissime e buggate GUI per tool da riga di comando.</li>
<li>Fan duri a morire che cercano di infilarlo in ogni progetto a cui hanno accesso.</li>
</ul>
<p>Se volete imbarcarvi in una battaglia stile Don Chisciotte contro i mulini a vento usate pure il Tcl, sappiate però che sarete gli unici a capirci qualcosa del codice che scriverete (il che potrebbe essere un vantaggio per la conservazione del posto di lavoro).</p>
<h3 id="perl">Perl</h3>
<p>Discorso simile al Tcl con in più una certa tendenza del linguaggio a dare eccessiva libertà al programmatore. Il Perl non è stato definito un linguaggio di programmazione "write only" a caso.</p>
<p>Se avete sufficiente disciplina, non vi spaventano le espressioni regolari e vedete un pregio nella facoltà di poter ridefinire <strong>TUTTO</strong> a runtime allora potreste pensare di scrivere il vostro agente in Perl.</p>
<p>Un punto a vantaggio del Perl è che anche più ubiquo di Python in ambito UNIX data la sua età.</p>
<h3 id="c-o-c">C o C++</h3>
<p>Siete tra coloro i quali reputano che i linguaggi di scripting siano solo fumo negli occhi?</p>
<p>Non vi spaventa il dover gestire da soli la memoria? Anzi il guadagno in prestazioni giustifica l'occasionale <em>memory leak</em> o <em>use after free</em> che sarà comunque rilevato da Valgrind e debitamente eliminato.</p>
<p>Volete avvicinarvi il più possibile alla macchina fisica senza essere costretti ad impare l'assembly?</p>
<p>Il C e/o il C++ potrebbero fare per voi! Se non fosse che il trattamento del testo in C e in C++ sia una pratica sadomasochistica ai limiti della tortura...</p>
<p>Detto questo vi sono librerie che semplificano le cose, ma introducono dipendenze e complicano la compilazione dei propri programmi.</p>
<p>In definitiva il consiglio che mi sento di darvi è scegliete il C o il C++ se non ci sono altre alternative o se le alternative sono troppo pesanti o troppo lente per gestire il flusso di dati che devono gestire. Nella mia esperienza personale simili casi sono piuttosto rari.</p>
<h3 id="java">Java</h3>
<p>Devo proprio scrivere perché non dovreste usare Java?</p>
<h3 id="scala">Scala</h3>
<p>Non conosco Scala ma credo che lo userei per lo step successivo (funnelling) ma non per la raccolta diretta dei dati.</p>
<h3 id="erlang-haskell-racketcommon-lispscheme-ocaml">Erlang, Haskell, Racket/Common LISP/Scheme, OCaml</h3>
<p>Vedi Scala.</p>
<h3 id="go-rust-d">Go, Rust, D</h3>
<p>Questi potrebbero essere delle valide alternative se non fossero ancora dei <em>Work in progress</em>.</p>
<p>Fateci degli esperimenti ma non usateli in produzione senza averli testati estensivamente.</p>
<h3 id="ruby">Ruby</h3>
<p>No.</p>
<h3 id="javascriptecmascript">Javascript/ECMAscript</h3>
<p>No. Davvero, non fatelo.</p>
<h3 id="php">PHP</h3>
<p><strong>VADE RETRO!!!</strong></p>
<h3 id="altri-linguaggi-di-programmazione">Altri linguaggi di programmazione</h3>
<p>Se non ho già elencato il vostro linguaggio di programmazione preferito significa che ricade in una di queste categorie:</p>
<ul>
<li>La categoria dei linguaggi poco diffusi. Con questi dovete fare uno sforzo attivo per convincere chi prende le decisioni ad utilizzare qualcosa che nessun altro usa. Qui ci metto anche i linguaggi di cui non sono a conoscenza.</li>
<li>La categoria dei linguaggi morti o morenti. Chi scrive più in COBOL o in FORTRAN al di fuori di certi ambiti?</li>
<li>La categoria dei linguaggi inadatti al compito. Verilog e PL/SQL sono ottimi nel loro dominio di applicazione, perché piegarli ad altro?</li>
<li>Brainfuck, LOLCODE, whitespace e simili. Devo aggiungere altro?</li>
</ul>
<h2 id="funnelling">Funnelling</h2>
<p>Avrei voluto inserire qui un bel grafico, ma le ricerche con Google Immagini mi hanno portato ad un punto morto pieno di ragazzotti intenti a tracannare birra mediante imbuti... Ah la gioventù!</p>
<p>Se siete arrivati fino a qui vuol dire che siete <strong>davvero</strong> interessati all'argomento, oppure avete saltato buona parte di quanto ho scritto nella speranza che la finissi con le opinioni oppure semplicemente non avete niente di meglio da fare e state ammazzando il tempo.</p>
<p>Ad ogni modo qui le cose si fanno interessanti. Mentre gli agenti devono essere leggeri ed hanno accesso solo ai dati provenienti dall'entità in cui risiedono (limitando la quantità di pre-processamento che possono effettuare sui dati che raccolgono) i nostri <em>imbuti</em> che ricevono e reinviano i dati possono effettuare diverse operazioni sui dati medesimi:</p>
<ul>
<li>Tipizzare i dati se non è già stato fatto in fase di raccolta.</li>
<li>Aggregare i dati ricevuti da diversi agenti.</li>
<li>Filtrare i dati.</li>
</ul>
<p>Ed ovviamente possono inviare i dati ad altri imbuti che a loro volta potranno aggregare, filtrare ed inviare dati nell'eterno ciclo del <em>data mining</em>.</p>
<p>Liberi dai vincoli dettati agli agenti i nostri imbuti sono allo stesso tempo il cervello, il sistema circolatorio e i muscoli della nostra infrastruttura di monitoraggio.</p>
<p>Qui è dove si distingue il dilettante (come il sottoscritto) dal professionista.</p>
<p>Qui è dove si trova la frontiera del data mining e dove si sperimentano tecniche di analisi avanzata e diagnosi precoce mediante il <em>machine learning</em>.</p>
<p>Qui purtroppo è anche dove la mia conoscenza ha le lacune più grandi. L'unica dritta che posso darvi è che, come avrete intuito, questa parte è la più importante di tutta l'infrastruttura ed è quindi quella che va progettata al meglio per potersi adattare alle esigenze di chi dovrà poi utilizzare l'infrastruttura stessa.</p>
<h2 id="visualizzazione-reportistica-e-allarmistica">Visualizzazione, Reportistica e Allarmistica</h2>
<p>Vi ricordate quando vi ho detto che nella fase intermedia ho le lacune maggiori? Ecco nemmeno in questo sono molto ferrato.</p>
<p>La visualizzazione dei dati è una scienza ed è tutt'ora oggetto di ricerca in diverse università in giro per il Mondo.</p>
<p>Questo è anche il campo in cui le soluzioni ad-hoc spuntano come funghi dopo una pioggia autunnale proprio in virtù della necessità di adattare il risultato delle analisi alle necessità di comprensione dell'utente finale (che non necessariamente sarà un essere umano).</p>
<p>Nel caso in cui si decida di sperimentare con il <em>machine learning</em> bisogna anche mettere in conto che si dovrà monitorare anche il livello di accuratezza delle analisi e delle previsioni che ci arrivano dall'infrastruttura stessa.</p>
<p>I sistemi di allarmistica poi dovranno essere particolarmente attenti ad evitare falsi negativi (che portano ad ignorare situazioni pericolose) e falsi positivi (che spingono l'utente a spegnere i sistemi stessi a causa dell'eccessivo rumore di fondo).</p>
<p>La reportistica è opzionale nel momento in cui decidiamo che non vogliamo conservare a lungo termine i dati raccolti ed elaborati. Normalmente non è così e quindi entrano in gioco tutta una serie di scelte su come conservare i dati e sulle eventuali post-elaborazioni da effettuarsi prima di archiviare i dati stessi.</p>
<p>Tutto questo ovviamente va poi adattato alle normative vigenti sul trattamento dei dati sensibili nel Paese (o nei Paesi) in cui si va ad operare.</p>
<p>Insomma ce n'è di che divertirsi! Alla prossima!</p>
</div>Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-29816558529762175872015-08-03T17:45:00.001+02:002015-10-13T08:08:29.037+02:00Container e altre amenità<div style="text-align: justify;">
<p>Salve o lettori! Quest'oggi cercherò di illustrare a quanti di voi non lo conoscono il magico ed affascinante mondo dei Containers.</p>
<p>Per chi non sia un esperto di Information Technology e per coloro che lo sono ma che hanno vissuto sotto ad una roccia negli ultimi tre anni: i container sono una soluzione interessante ad un annoso problema, quello della separazione di diverse applicazioni residenti sulla medesima macchina fisica.</p>
<p>Supponiamo voi siate un allegro e simpatico sistemista amato dai colleghi e invidiato dal management... Fatto? Bene, torniamo ora coi piedi per terra e prendiamo un ben più comune sistemista ignorato dai colleghi e conosciuto unicamente come voce passiva di bilancio dal management.</p>
<p>Il vostro compito è quello di rendere efficace ed efficiente la fruizione dei servizi informatici da parte della vostra azienda e/o da parte dei vostri clienti. Vi è stato chiesto di integrare un nuovo servizio composto da un mix di applicazioni interagenti tra di loro e quasi incompatibili con il vostro attuale stack software. Il budget copre le cialde della macchinetta del caffè e il bonus di produttività dell'anno passato vi ha permesso di comprare la suddetta macchinetta per cui non ci sono soldi per comprare nuovo harware.</p>
<p>A questo punto sareste tentati di optare per una macchina virtuale, ma sapete già per esperienza che le macchine virtuali hanno la terribile tendenza ad essere sovrastimate o sottostimate per il compito che devono assolvere ed inoltre si portano dietro inevitabilmente il layer di virtualizzazione (o richiedono kernel speciali per la paravirtualizzazione). Niente di insormontabile: si è lavorato per un decennio con le macchine virtuali e le prestazioni sono prossime a quelle della macchina fisica su cui girano. Però quella fastidiosa vocina dentro la testa vi dice che si può fare di meglio e che si può sfruttare in maniera più oculata il ferro.</p>
<p>La vocina ha ragione, vediamo se possiamo farla star zitta con i containers.</p>
<h2 id="gabbie-chroot">Gabbie chroot</h2>
<p>Prima di addentrarci nel magico mondo dei container vi devo parlare di una syscall e delle implicazioni che questa syscall ha avuto. Tanto tempo fa, quando la Disco music era in declino e il New wave era in ascesa Bill Joy (il creatore dell'editor <code>vi</code>) aggiunse al codice della Berkeley Software Distribution la chiamata di sistema <code>chroot</code> per testare il sistema di installazione di BSD in locale senza dover reinstallare da zero una macchina fisica.</p>
<p>Immagino che gli utenti di Arch Linux a questo punto scattino in piedi come delle molle. Acquietatevi e consentitemi di spiegare anche ai comuni mortali cosa fa <code>chroot</code> e perché è importante in fase di installazione del sistema.</p>
<p>La suddetta chiamata di sistema altro non è che una maniera per far sì che un processo ed i suoi figli vedano un'altra directory come se fosse la radice della gerarchia del filesystem (la famosa <code>/</code>). Cosa significa questo? Significa ad esempio che potreste avere un web server che in <code>/var/www</code> abbia i dati da servire, gli script PHP o i CGI e la sua configurazione completa più tutte le librerie di cui ha bisogno e potreste fare in modo che non possa uscire da <code>/var/www</code> facendogli fare una chiamata a <code>chroot</code> in fase di avvio. Le implicazioni sono palesi: il vostro webserver non potrà modificare nessun file all'infuori di quelli presenti in <code>/var/www</code> e nelle relative sottodirectory e, se la sua nuova radice è montata su un filesystem separato, non potrà impedirvi di lavorare riempiendo completamente il disco di files a causa di un bug nello script che consente agli utenti di caricare files via HTTP POST o HTTP PUT.</p>
<p>Questa condizione si chiama <em>gabbia chroot</em> ed è utilizzata ampiamente da molti software: il server OpenSSH la usa in fase di autenticazione, il server di posta Postfix è diviso in diversi programmi che risiedono in gabbie chroot, il webserver thttpd ha un'opzione per avviarlo e farlo subito entrare in una gabbia chroot e l'elenco potrebbe andare avanti.</p>
<p>Per quanto utili le gabbie chroot non sono perfette. Tanto per comiciare tutti i file descriptor aperti prima della chiamata a <code>chroot</code> vengono mantenuti, anche se riguardano file presenti all'esterno. Inoltre è possibile sfuggire alla gabbia facendo una seconda chiamata a <code>chroot</code> e reimpostando la root a quella di sistema. Le gabbie chroot inoltre non possono nulla contro processi che succhiano RAM e/o cicli di CPU a scapito degli altri processi nel sistema. Senza contare che un processo in una gabbia chroot che abbia i privilegi di root può killare un qualsiasi altro processo presente nel sistema. Infine non c'è alcuna maniera per limitare l'accesso alla rete: un processo in una gabbia chroot può tranquillamente aprire quanti socket vuole verso qualsiasi destinazione sia raggiungibile dall'host da qualsiasi indirizzo IP sia disponibile.</p>
<p>Insomma: le gabbie chroot sono un buon punto di partenza, ma occorre pensare a qualcosa di più se vogliamo realmente isolare un'applicazione dal resto del sistema.</p>
<h2 id="freebsd-e-le-jails">FreeBSD e le jails</h2>
<p>Le mancanze di <code>chroot</code> erano note da anni quando Poul-Henning Kamp si trovò davanti all'annoso problema che affligge tutti coloro i quali voglio aprire un servizio di hosting di siti web: come faccio a separare il mio (o i miei) siti da quelli dei miei clienti?</p>
<p>La soluzione efficace ma dispendiosa era (è) quella di ospitare il proprio sito su di un server e quelli dei clienti su altri server. Per darvi un'idea temporale stiamo parlando del 2000: un'epoca in cui la virtualizzazione muoveva i suoi primi passi, il processore di punta di intel era il Pentium III e Windows XP era ancora in fase di sviluppo e si chiamava Whistler. Un'epoca oscura per il mondo dell'IT...</p>
<p>A quei tempi l'unica maniera per avere più di un sito ospitato sullo stesso server fisico consisteva nello sfruttare un campo nell'header HTTP reso obbligatorio a partire da HTTP 1.1: il campo "Host:". Tale campo viene compilato dal client ed indica l'host a cui si vuol fare la richiesta, nella precedente versione di HTTP non era obbligatorio perché si assumeva che l'host a cui ci si collegava fosse lo stesso host a cui si voleva richiedere i dati e che un nome a dominio puntasse a macchine fisicamente diverse (o che, se anche si fosse puntato alla stessa macchina fisica con nomi diversi, questa avrebbe fornito sempre gli stessi dati).</p>
<p>L'avvento dei proxy server (utilizzati per ridurre il traffico dati verso i siti più frequentati dai propri utenti e quindi ridurre anche i costi di connessione) ha reso necessario indicare qual è l'host a cui mi voglio rivolgere perché potrebbe non essere quello a cui sono collegato.</p>
<p>Come effetto collaterale il campo "Host"permette ad un server web di decidere che contenuto mostrare in base al valore del campo stesso tramite il meccanismo dei virtual hosts.</p>
<p>Per quanto i virtual host rendano possibile la convivenza di più siti sul medesimo server web e le gabbie chroot possano essere sfruttate per impedire agli utenti di scrivere via FTP nelle directory degli altri (il server FTP al momento dell'autenticazione crea un nuovo processo che immediamente fa una chiamata a <code>chroot</code> nella home directory dell'utente) questo meccanismo non migliora la situazione agli utenti che richiedono modifiche particolari alla configurazione del webserver e che magari entrano in conflitto con altre modifiche volute da altri utenti o dagli amministratori stessi del server.</p>
<p>La situazione descritta poc'anzi non è così campata per aria, basti pensare a versioni mutualmente incompatibili di PHP (ad esempio PHP 4 e PHP 5) richieste contemporaneamente da due utenti differenti. Si può pensare di compilare staticamente due versioni di PHP, metterle in due gabbie chroot diverse, configurare due istanze del server web affinchè si mettano in ascolto su indirizzi IP diversi e pregare che tutto funzioni. Ma questo non impedisce ai processi di vedere tutti gli altri processi in esecuzione (e potenzialmente di fare disastri).</p>
<p>La soluzione proposta da Paul Henning-Kamp è stata quella di estendere le gabbie chroot in modo da rinchiudere i processi non solo dal punto di vista dell'accesso ai file, ma anche dal punto di vista dei processi con cui possono interagire e dal punto di vista dell'interazione con le connessioni di rete. Nascono così le jails.</p>
<p>Una jail è una gabbia chroot i cui processi non vedono altri processi se non quelli lanciati all'interno della jail ed è associata ad un indirizzo IP (per cui può comunicare solo tramite quell'IP e non tramite tutti gli IP disponibili all'host che ospita la jail). Non solo: l'utente root all'interno della jail non ha la facoltà di uscire dalla jail, solo root dall'esterno della jail può entrare e uscire a piacimento.</p>
<p>In pratica si può creare una userland alternativa in una sottodirectory del proprio filesystem e farci girare quello che si vuole sapendo che il resto del sistema sarà opaco ai processi all'interno della jail.</p>
<p>Iterazioni successive hanno raffinato il meccanismo delle jail migliorandone la sicurezza e la capacità di compartimentazione e rendendole una delle feature più interessanti di FreeBSD.</p>
<h2 id="linux-containers">Linux Containers</h2>
<p>Facciamo un bel fast forward di otto anni e raggiungiamo il 2008 quando finalmente il kernel Linux ha un'implementazione matura dei <code>cgroups</code> e può replicare le funzionalità delle jails di FreeBSD. Su questa base comincia a svilupparsi LXC: un insieme di tools in userland che rendono semplice la creazione di quegli ambienti chiusi noti come container.</p>
<p>Se avete resistito fin qui potrete facilmente dedurre cosa sia un container: nient'altro che la versione in salsa Linux delle jails. Tramite <code>chroot</code> e <code>cgroups</code> si ottiene il medesimo effetto, in effetti si ha una granularità maggiore nel limitare ciò che un processo all'interno di un <code>cgroup</code> può fare. L'effetto di questa granularità è stato in parte deleterio: per anni gli unici che usavano queste feature erano pochi iniziati che seguivano attentamente gli sviluppi del kernel.</p>
<p>C'è voluto il 2013, una startup chiamata Docker, e una cospicua dose di marketing perché il mondo si rendesse conto che i container su Linux esistono, sono una tecnologia matura e possono semplificare la vita di chi deve incastrare userland mutualmente incompatibili sullo stesso hardware.</p>
<p>Non sono però la panacea a tutti i problemi: tanto per cominciare il kernel è uno per tutti i container, una macchina virtuale può far girare un kernel diverso da quello dell'host. Stesso discorso vale per i moduli del kernel: tutti i container vedranno gli stessi moduli, anche se il caricamento di un modulo dall'interno dei container può essere inibito (e solitamente è inibito di default per questioni di sicurezza).</p>
<p>Il rovescio della medaglia sono le prestazioni: non c'è bisogno di elaborati artifici con driver virtuali passthrough e simili amenità in un container perché si sta già girando direttamente sul ferro e l'accesso ad una periferica dista appena un <code>mknod</code> ed una modifica al <code>cgroup</code>.</p>
<p>In sintesi per concludere: se siete gente che sa quel che sta facendo e vuole un set di tool minimale per sfruttare rapidamente i container ed avere il massimo della personalizzazione il mio consiglio è di saltare il layer di Docker e di provare LXC direttamente. Se siete interessati ad un sistema che vi consenta di condividere efficacemente le istruzioni per la creazione di containers e che fornisca già migliaia di template già pronti al prezzo della creazione di un account gratuito allora andate tranquilli su Docker. Se dovete far girare kernel diversi o interi sistemi operativi diversi allora la scelta delle macchine virtuali è una scelta obbligata.</p>
</div>Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-90688838737506837752015-06-26T17:03:00.000+02:002015-07-15T07:50:03.962+02:00Turing e Template<div style="text-align: justify">
<p>Salve a tutti o lettori! Il blog languiva (in buona parte grazie a quella cosa chiamata "vita reale" che ha bloccato diversi GNUrants dallo scrivere qualcosa che non fosse relativo al lavoro o all'università).</p>
<p>Invece di lasciarvi in attesa che grossi articoli appaiano ho deciso di scrivere qualche paragrafo sui <a href="http://en.wikipedia.org/wiki/Template_processor">Template Engine</a> e sulle macchine di Turing <a href="http://gnurants.blogspot.it/2014/11/il-problema-dellarresto.html">di cui ha già parlato il buon Federico.</a></p>
<p>La domanda che vi pongo è: preso un Template Engine (ad esempio <a href="http://jinja.pocoo.org/docs/dev/">Jinja2 per Python</a>) questo è Turing-completo? Posso cioé scrivere un qualsiasi programma (da Quicksort a DooM) in forma di template?</p>
<p>Potete subito intuire che le conseguenze di una risposta affermativa a questa domanda non siano da poco, sia in termini di flessibilità del Template Engine (posso potenzialmente fare quello che voglio senza uscire dal Template Engine) sia in termini di sicurezza (un attaccante che riuscisse a sfruttare una mancata validazione dell'input che passo al Template Engine potrebbe far fare di tutto e di più al mio server).</p>
<p>Un vecchio detto recita: in teoria non c'è differenza tra la pratica e la teoria, in pratica la differenza c'è eccome!</p>
<p>Questo è uno dei casi in cui si verifica proprio questa situazione: in teoria io posso scrivere DooM come template Jinja2 ma in pratica non posso farlo perché il mio template engine non ha accesso all'hardware della mia macchina per cui il massimo risultato a cui poso aspirare è renderizzare le schermate una ad una sottoforma di file SVG.</p>
<h2 id="un-po-di-teoria">Un po' di teoria</h2>
<p>Prima di continuare a sproloquiare su macchine di Turing e Template occorre definire quale sia l'insieme minimo di caratteristiche che fanno sì che un linguaggio di programmazione, una definizione formale di regole di riscrittura o un modello computazionale astratto siano Turing-Completi e quindi equivalenti alla Macchina di Turing.</p>
<p>In primo luogo la memoria deve essere presente e deve essere infinita: non devo preoccuparmi di esaurirla.</p>
<p>In secondo luogo devo avere un modo per dare un input arbitrariamente grande (diciamo un infinito numerabile di possibili input) ed ottenere un numero intero che codifichi il mio output.</p>
<p>Devo ovviamente poter scrivere e leggere a piacere nella mia memoria e devo poter decidere cosa scrivere in base a determinate condizioni.</p>
<p>Ora prendiamo un modello di computo più user-friendly della Macchina di Turing e del Lambda Calcolo: la <a href="https://en.wikipedia.org/wiki/Random-access_stored-program_machine">macchina RASP</a>.</p>
<p>Questa macchina è dotata di infiniti registri contenenti ciascuno un numero intero qualsiasi e ha un set di sole quattro istruzioni:</p>
<ul>
<li>INC x: incrementa di un'unità il registro x.</li>
<li>DEC x: decrementa di un'unità il registro x.</li>
<li>JZ x z: se il contenuto del registro x è pari a zero salta all'istruzione z.</li>
<li>HALT: la computazione è terminata.</li>
</ul>
<p>È stato dimostrato che questo modello è Turing completo (tranquilli, non vi farò subire una dimostrazione formale). In alcune formulazioni DEC è sostituita da ZERO (istruzione che azzera il contenuto di un registro) e HALT è sostituita da GOTO (come condizione di arresto si assume che la macchina si fermi automaticamente dopo aver eseguito l'ultima istruzione).</p>
<p>Ora se il nostro Template Engine contempla quelle quattro istruzioni o degli equivalenti di quelle quattro istruzioni possiamo tranquillamente affermare che sia equivalente alla macchina RASP e, in virtù della proprietà transitiva, sia equivalente alla Macchina di Turing (ammesso ovviamente che sia abbia a disposizione una memoria infinita, ma siamo nel campo della teoria per cui la memoria è infinita per definizione).</p>
<h2 id="per-tutti-i-calcolatori-batman">Per tutti i calcolatori, Batman!</h2>
<p>Forse ci sarete già arrivati, ma un Template Engine che abbia gli IF e permetta di scrivere operazioni aritmetiche di somma e sottrazione può tranquillamente eseguire tre di quelle quattro istruzioni. Se rinunciamo all'istruzione HALT in favore del più amichevole "quando hai finito di processare il template hai finito la computazione" e organizziamo accuratamente i nostri IF avremo tutto quello che ci serve!</p>
<p>Quindi la maggior parte dei Template Engine avanzati <strong>SONO</strong> Turing-completi, a dispetto del fatto che spesso servono "solo" ad evitare allo sviluppatore di scrivere tonnellate di codice ripetitivo e noioso.</p>
<p>Meditate gente, meditate...</p>
</div>Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-60061837691380670742015-03-16T14:22:00.000+01:002015-03-16T14:22:20.875+01:00PiFS, e non preoccupiamoci più dello spazio di archiviazione!Eccoci tornati con la nostra consueta rubrica riguardante la simpatia dei programmatori e le loro divertentissime trovate!<br />
Cosa? Non esiste una rubrica del genere sul nostro blog? Beh, sarà proprio il caso di crearne una allora!<br />
<br />
Partiamo dal principio, ossia dal nome che apre il titolo: PiFS. “Pi” è il noto Pi greco,<span style="font-family: inherit;"> <span style="line-height: 1.38; white-space: pre-wrap;">quel</span><span style="line-height: 1.38; white-space: pre-wrap;"> numerino che ci si trova sempre in mezzo alle scatole e che quindi non dovrebbe aver bisogno di ulteriori presentazioni.</span></span><br />
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
FS sta invece per <b>F</b>ile<b>S</b>ystem, quella parte del sistema operativo che permette di compiere operazioni di scrittura e lettura su qualunque dispositivo di memorizzazione (un hard disk, una chiavetta usb ecc ecc) in maniera trasparente all'utente. I nostri dati infatti non sono organizzati in cartelle, ma piuttosto scritti a casaccio, e non sempre in maniera contigua (ad esempio <b>quel</b> film da 4Gb che avete illegalmente scaricato sarà scritto “dove c'è spazio”, e se necessario spezzato più volte: difficile infatti trovare tutto quello spazio libero contiguo sul vostro hard disk!). Compito del filesystem quindi è, mentre navighiamo tra le cartelle del nostro pc e apriamo un file, far ruotare il disco di modo che la testina legga esattamente tutte le parti di quel file. Le cartelle sono <span style="line-height: 22.0799999237061px;">semplicemente </span><span style="line-height: 1.38;">dei file speciali che contengono la lista dei file presenti al loro interno.</span></div>
E questo condensa il <i>what</i>; l'<i>how </i> è molto complesso e ve lo lascio cercare su google, se siete interessati.<br />
Trovo piuttosto affascinante che all'utente tutto ciò sia nascosto, non è fantastico?<br />
<div>
Ma bando ai sentimentalismi, andiamo avanti!<br />
<div>
<div>
Cerchiamo di capire perché asserisco che grazie a PiFS potremo scordarci dello spazio di archiviazione. Esiste una congettura, per ora mai provata ma nemmeno smentita, che afferma che Pi sia un numero normale; cosa sia un numero normale, lo lascio alla chiara definizione data da wikipedia:<br />
<blockquote class="tr_bq">
a number of infinite length is called normal when all possible sequences of digits (of any given length) appear equally often.</blockquote>
Il fatto che sia normale, implica anche che sia una <i>sequenza disgiuntiva</i>, ossia una sequenza infinita di cifre all'interno della quale compare ogni altra possibile finita sequenza. Proviamo a ragionare un po'…se Pi contiene ogni finita sequenza di numeri...allora, scrivendolo ovviamente in binario, esso conterrà anche ogni dato di tutto ciò che è stato, è, e sarà!<br />
Detto in un'altra maniera: tutti i possibili file, da questo che sto scrivendo ora, a quel file che avete cancellato per errore anni fa, alla vostra tesi di laurea salvata prontamente sul vostro PC, e pure quel progetto di software che avete in mente di scrivere, tutto ciò è già presente in Pi!!<br />
E da qui l'idea di PiFS: celebriamo la grandezza di questo numero, prostriamoci d'innanzi alla sua infinita potenza, e creiamo un FS che sfrutti questa sua proprietà!<br />
L'idea dello sviluppatore è stata quindi quella di creare un filesystem che semplicemente cerchi byte per byte di ciascun file (per questioni di performance non cerca la sequenza del file intero, ma lo spezza in “sotto-file” di un byte) dove inizia la sequenza di quel dato byte di quel dato file, e segni quest'indice come metadato sullo spazio di archiviazione (che comunque è necessario).<br />
Beh...che dire? Geniale!!! Abbiamo sconfitto <strike>la fame nel mondo</strike> il problema dello spazio di archiviazione!<br />
<br />
Ma c'è un enorme limite, anzi due: le performance sono scarsissime e soprattutto non ci è dato sapere quanto tempo ci vorrà a cercare la sequenza corrispondente (in scrittura), potrebbero volerci <b>giorni</b> anche sui pc più potenti. Vale lo stesso problema anche in lettura: pur avendo l'indice dal quale la sequenza corrispondente all'inizio dell' i-esimo byte del file, dobbiamo comunque scorrere Pi fino a quell'indice (e quindi il tempo di accesso può essere molto lungo); inoltre, se spezzare i file in sotto-file da 1 byte ci permette in scrittura di essere “più efficienti”, in lettura si è penalizzati dal fatto che si avranno molti indici da cercare in fila per leggere un file interamente.<br />
L'altro problema, e qua arriva la trollata finale, è che i metadati riguardanti gli indici generati da PiFS, hanno in media dimensione <b>maggiore</b> rispetto ai file stessi!<br />
Insomma, non solo le operazioni di lettura e scrittura sarebbero lentissime, in più alla fine sprecheremmo più spazio di quanto se ne utilizzi ora!<br />
Ovviamente lo sviluppatore è consapevole di questa contraddizione, infatti il filesystem è nato come scherzo che, devo essere sincero, gli è proprio ben riuscito! Mi ha strappato più di qualche risata, oltre a lasciarmi a bocca aperta per la genialità ovviamente!<br />
Lascio il link al github del genio: <a href="https://github.com/philipl/pifs">https://github.com/philipl/pifs</a>. <br />
<br /></div>
<div>
Gloria, gloria al nostro Pi!</div>
</div>
</div>
<div>
Al prossimo numero di questa nostra splendida rubr... no, non sbattetemi fuori! Nooooooooooooo!</div>
Anonymoushttp://www.blogger.com/profile/03854199872890515528noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-91367744703982481772015-03-02T11:09:00.000+01:002015-03-02T13:50:52.401+01:00GHOST: un fantasma nelle glibc<div style="text-align: justify;">
<p>Torniamo a discutere di sicurezza informatica e torniamo a parlare di bug in librerie che non dovrebbero contenerne. Spirito polemico a parte, il 2015 si è aperto in bellezza con la vulnerabilità di sicurezza etichettata <a href="https://www.qualys.com/research/security-advisories/GHOST-CVE-2015-0235.txt">CVE-2015-0235</a> e nota al pubblico come GHOST.</p>
<p>Cos'ha di speciale questa vulnerabilità? In primo luogo riguarda l'equivalente GNU/Linux di uno dei componenti base di ogni sistema *NIX: la libreria standard del C. Per quanto bello ed interessante il pippone sulla storia di UNIX e del linguaggio C è già stato oggetto di numerosi articoli e discussioni: i più pigri possono risparmiarsi una ricerca su Google e leggere <a href="http://it.wikipedia.org/wiki/Unix">l'articolo di Wikipedia su UNIX</a>.</p>
<p>Se non siete stati risucchiati dal gorgo degli articoli correlati e ce l'avete fatta a tornare tra noi ora sapete che, senza la libreria standard del C, scrivere un qualsiasi programma diventa un compito per guru del linguaggio assembly. Per non parlare della possibilità di avere codice (più o meno) portabile...</p>
<p>Faccio anche notare che il kernel Linux ha una sua versione ridotta della libreria standard del C (la <a href="http://en.wikipedia.org/wiki/Klibc">klibc</a>) data la necessità di massima indipendenza del kernel da librerie esterne (e anche qui ce ne sarebbe da discutere, ma mi sono imposto di ridurre le divagazioni al minimo).</p>
<p>Appurato che la libreria standard del C è importante per lo userland tanto quanto lo sono il kernel e le syscall che questo espone, vediamo di capire più in dettaglio cosa è andato storto stavolta e quali implicazioni il bug si porta dietro.</p>
<h1 id="il-diavolo-nei-dettagli">Il Diavolo nei dettagli</h1>
<p>Se avete cliccato sul link in cima all'articolo sarete arrivati ad un file di testo scritto in informatichese stretto che spiega con squisito dettaglio quali sono le cause e quali gli effetti del bug, oltre a dare un piccolo programma in C che (una volta compilato) servirà a testare i propri computer.</p>
<p>Potrei cercare di tradurre alla meglio l'articolo in questione e dichiarare festa finita, ma chi mi legge abitualmente sa che non è mia consuetudine scrivere simili articoli.</p>
<p>Cominciamo quindi la nostra maratona di brutalità informatica per iniziati! :-D</p>
<p>La colpevole è una funzione interna delle glibc (ovvero una funzione che non è possibile chiamare dall'esterno ma che viene chiamata da altre funzioni delle glibc): <code>__nss_hostname_digits_dots</code></p>
<p>Leggendo questa funzione, mi è subito sembrato chiaro che chi l'ha scritta non si fidasse del compilatore: invece di creare una struttura con 4 puntatori ed allocare un buffer per contenerne l'input, ha deciso di allocare un unico buffer e di calcolare a priori lo spazio per contenere 2 puntatori e il testo di input, dimenticando per strada un puntatore.</p>
<p>"Ma così si risparmia spazio!". Certo, se devi far girare il tuo codice su un microcontrollore con 16 kilobyte di RAM lo spazio è vitale. Ma qui si parla di PC che hanno memoria a strafottere e risparmiare lo spazio per un puntatore compromettendo la leggibilità del codice è una falsa economia.</p>
<p>Qual è il risultato di quel puntatore dimenticato? Che si può andare a scrivere roba oltre i limiti del buffer (buffer overflow) e ciò è <strong>MALE</strong>.</p>
<p>Per chi fosse curioso di scoprire quanto può essere dannoso un buffer overflow consiglio caldamente la lettura di <a href="http://phrack.org/issues/49/14.html">Smashing The Stack For Fun and Profit</a> storico articolo di Aleph One pubblicato su Phrack 49 nel lontano 1996. Per chi non avesse tempo/voglia di leggere l'articolo la versione TL:DR si riduce a "un valore sbagliato nel posto giusto e il mio computer è alla mercé di chi ha scritto quel valore in quel posto".</p>
<p>Vista la natura così pericolosa dei buffer overflow gli sviluppatori di compilatori, linguaggi di programmazione e sistemi operativi hanno passato gli ultimi 20 anni a studiare tecniche atte a mitigare le conseguenze degli errori di programmazione. La letteratura in merito è ampia e variegata e le tecniche più quotate al momento in cui scrivo sono tre:</p>
<ol>
<li>Canarini nello stack e/o bound checks a runtime.</li>
<li>NX bit (reale o emulato).</li>
<li>Address Space Layout Randomization (ASLR).</li>
</ol>
<p>Spero che mi perdonerete la brevità ma per capire come hanno fatto ad aggirare questi meccanismi occorre prima capire come questi operano.</p>
<h1 id="canarini-e-bound-checks">Canarini e bound checks</h1>
<p>I canarini devono il loro nome a quelli utilizzati nelle miniere per rilevare le fughe di gas tossici nelle gallerie: se il canarino sveniva o moriva l'aria era tossica anche per i minatori.</p>
<p>I canarini nello stack sono porzioni di dati randomizzati inserite dopo il buffer. La procedura di chiamata delle funzioni si complica un po' perché occorre verificare il canarino in fase di uscita dalla funzione se il canarino è stato modificato in qualche modo la routine di uscita dalla funzione interrompe l'esecuzione e uccide il programma. Questo comportamento è giustificato dall'idea che è preferibile una caduta di servizio che una compromissione del computer.</p>
<p>Il valore del canarino di solito è inserito in una posizione particolare di memoria circondata da aree di memoria non valida che causa un segmentation fault nel caso in cui un attaccante cerchi di leggere sequenzialmente la memoria per cercare il canarino.</p>
<p>I canarini richiedono un cambiamento del compilatore e spezzano la compatibilità binaria perché modificano <a href="http://en.wikipedia.org/wiki/Application_binary_interface">l'ABI (Application Binary Interface)</a> dei programmi e delle librerie.</p>
<p>Un altro metodo per aumentare la sicurezza consiste nel bound checking (controllo dei limiti). Quando la dimensione del buffer è nota durante la compilazione (cioè scritta direttamente nel codice o definita da una costante nota al compilatore) il controllo è facile da implementare automaticamente. Quando la dimensione del buffer non può essere nota a priori il compilatore deve aggiungere del codice che tenga traccia delle dimensioni di tutti i buffer allocati dinamicamente, così da consentire il controllo dei limiti.</p>
<p>La suite di compilatori GCC supporta i canarini, ma non li abilita di default. Per abilitarli occorre aggiungere il flag <code>-fstack-protector</code> (o <code>-fstack-protector-all</code> per proteggere tutte le chiamate a funzione).</p>
<p>Per maggiori informazioni potete consultare <a href="http://en.wikipedia.org/wiki/Buffer_overflow_protection">la pagina di Wikipedia sulla Buffer Overflow Protection</a>.</p>
<h1 id="nx-bit">NX bit</h1>
<p>Il bit NX è una caratteristica di alcune architetture (AMD64/x86_64, Alpha, UltraSPARC) che consente di segnare una pagina di memoria come non eseguibile.</p>
<p>Se la CPU prova ad eseguire istruzioni presenti in una pagina marcata dal bit NX un interrupt hardware viene eseguito e il sistema operativo può interrompere il processo in corso o (se il problema avviene in kernel space) lanciare un kernel panic.</p>
<p>A differenza dei canarini, la protezione data dal bit NX non incide sulle performance dei programmi ma richiede, oltre al supporto da parte dell'hardware, che il compilatore indichi nei file di output quali sono le aree di memoria eseguibili e le consolidi in modo da facilitare il lavoro del loader (la porzione del sistema operativo che si occupa di caricare in memoria i programmi). Inoltre il compilatore non deve emettere codice che dipenda da uno stack o da uno heap eseguibile altrimenti quel codice farà scattare la protezione.</p>
<p>Nelle architetture in cui il bit NX non è presente (le più rilevanti delle quali sono x86 e ARM) si possono utilizzare dei meccanismi alternativi come il <a href="https://pax.grsecurity.net/docs/segmexec.txt">SEGMEXEC di PaX</a> che sfrutta il registro Code Segment e gli interrupt di page fault per emulare il bit NX al prezzo di dimezzare la memoria allocabile disponibile per i programmi.</p>
<p>Ovviamente questa emulazione richiede una modifica rispetto al kernel standard ("vanilla"). Solo alcune distro hanno deciso di applicare queste patch, a causa delle ripercussioni sul resto del sistema (minori performance e, in alcuni casi, programmi che smettono di funzionare). Il kernel Linux vanilla per x86_64 (e per alcuni processori x86 che lo supportano) sfrutta il bit NX già dalla <a href="https://www.kernel.org/pub/linux/kernel/v2.6/ChangeLog-2.6.8">versione 2.6.8</a>.</p>
<h1 id="address-space-layout-randomization-aslr">Address Space Layout Randomization (ASLR)</h1>
<p>Veniamo ora al più complicato (e secondo alcuni più efficace) mezzo di protezione della memoria: la randomizzazione dello schema di disposizione di dati e istruzioni nella memoria.</p>
<p>Per prima cosa mi scuso per l'orribile termine "randomizzazione" ma non ho trovato un equivalente meno brutto ma altrettanto calzante.</p>
<p>Per seconda cosa sappiate che se non avete ancora letto "Smashing The Stack For Fun and Profit" siete delle brutte persone che non capiranno molto di quello che seguirà.</p>
<p>L'ASLR consiste in una serie di accorgimenti atti a rendere la vita difficile a chi cerca di sfruttare i buffer overflow. Ma quali buffer overflow?</p>
<p>La tecnica canonica è lo stack overflow: una scrittura di dati che eccedono in quantità la dimensione di un buffer allocato nello stack e che vanno a sovrascrivere l'indirizzo di ritorno della funzione con un valore arbitrario. Gli effetti variano dal crash dell'applicazione fino all'esecuzione di una shell con i privilegi dell'utente che ha lanciato l'applicazione.</p>
<p>Contro gli stack overflow si può adottare una tecnica che consiste nel creare uno spazio vuoto (gap) tra l'indirizzo di ritorno e i parametri della funzione. Ovviamente se questo spazio vuoto fosse fisso sarebbe facile compensare per cui il gap dev'essere casuale. Uniamo questo trucco ad un canarino piazzato prima dell'indirizzo di ritorno e abbiamo già cominciato a creare una bella gatta da pelare per chi scrive malware.</p>
<p>La randomizzazione però non si ferma qui: c'è l'intera categoria degli heap overflow che, pur essendo più complessi da sfruttare degli stack overflow, rappresentano una bella fetta delle minacce a cui si va incontro.</p>
<p>Come facciamo a proteggerci dagli heap overflow? Randomizzando la memoria ulteriormente. Per capire come dobbiamo prima capire cos'è uno heap overflow e come si può sfruttare.</p>
<h1 id="heap-overflows">Heap Overflows</h1>
<p>Se avete tempo trovate un'eccellente spiegazione di come sfruttare un overflow dello heap su <a href="http://www.win.tue.nl/~aeb/linux/hh/hh-11.html">Hackers Hut</a> e aggiungo anche l'ottimo (seppur datato) <a href="http://phrack.org/issues/57/8.html">articolo di Michel "MaXX" Kaempf su Phrack 57</a> che spiega in dettaglio il funzionamento dell'allocazione della memoria nelle glibc. La lettura è decisamente impegnativa e richiede alcune conoscenze approfondite del funzionamento del kernel Linux, del linguaggio C e un'infarinatura su come funziona un linker dinamico per eseguibili in formato ELF.</p>
<p>La versione TL:DR è la seguente: se siete sopravvissuti ad un corso di C saprete già che malloc riserva un'area di memoria nello heap mentre free la libera. Quello che fa la versione di malloc implementata nelle glibc è chiedere al kernel di riservare un po' di memoria e, se tutto va bene, usa parte di quella memoria per scrivere la seguente struttura dati:</p>
<pre><code>struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /*Size of previous chunk (if free).*/
INTERNAL_SIZE_T size; /*Size in bytes, including overhead.*/
struct malloc_chunk* fd; /*double links -- used only if free.*/
struct malloc_chunk* bk;
/*Only used for large blocks: pointer to next larger size.*/
struct malloc_chunk* fd_nextsize; /*double links -- used only if free.*/
struct malloc_chunk* bk_nextsize;
};</code></pre>
<p>Sempre se avete completato il corso di C, saprete che quella struct, al netto degli ultimi due campi (che ignoreremo), è una <a href="http://en.wikipedia.org/wiki/Doubly_linked_list">lista concatenata doppia</a>. Per chi non avesse seguito con attenzione: la lista concatenata doppia è una struttura dati dinamica i cui elementi puntano tutti all'elemento precedente e all'elemento successivo nella lista. Quella struttura dati è fondamentale per il funzionamento di <code>free</code> e per il riciclo della memoria allocata da parte di <code>malloc</code> perché consente di sapere <strong>dove</strong> si trovano e <strong>quanto grandi</strong> sono le aree già riservate ma non più utilizzate della memoria.</p>
<p>Tutto molto bello, ma che implicazioni ha? Quando si fa una chiamata a <code>free</code> questa funzione prende il puntatore, ricava da esso la posizione della <code>malloc_chunk</code> e la utilizza per consolidare la memoria liberata in un chunk più grande usando il puntatore <code>bk</code> per trovare il chunk precedente e quindi riaggiustando i puntatori <code>fd</code> e <code>bk</code>.</p>
<p>Ma come fa a sapere se il chunk precedente è libero o è in uso? Con un astuto trucchetto che sfrutta l'allineamento dei dati nella memoria. Per ragioni prestazionali è sempre bene che la memoria sia allineata secondo la dimensione della parola utilizzata internamente dall'harware: 32 bit (o 4 byte) per le architetture a 32 bit e 64 bit (8 byte) per quelle a 64 bit. Nulla vieta di allineare la memoria secondo i <strong>multipli</strong> delle parole, per cui un allineamento a 8 byte va bene sia per x86 (32 bit) che per AMD64 (64 bit).</p>
<p>Siccome il campo <code>size</code> indica la dimensione in bytes se imponiamo l'allineamento a 8 byte i due bit meno significativi saranno <strong>sempre</strong> pari a 0 (8 si scrive 100 in binario). Quei due bit sono utilizzati come flag per segnalare se il chunk di memoria è stato ottenuto con <code>mmap</code> (e quindi richiede di essere liberato con <code>munmap</code>) e se il precedente chunk è in uso o meno.</p>
<p>Se il precedente chunk non è in uso allora posso utilizzare il campo <code>prev_size</code> per raggiungere la struttura <code>malloc_chunk</code> ed utilizzare i dati ivi contenuti per aggiornare i campi della mia <code>malloc_chunk</code> e consolidare la memoria liberata.</p>
<p>Se il chunk precendente è in uso posso usare il campo <code>size</code> per saltare al campo successivo e quindi al successivo ancora e controllare se il mio vicino è in uso e, se non lo è, consolidare lo spazio libero in avanti.</p>
<p>Confusi? Forse un schema aiuterà la comprensione:</p>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhb7octqKntQ_eNqoPHYN44bS1ajk4RiPP551wWyJ_30hkvjYDqlXKZEtAjOGz2N56G_kRKvER6gYG7GvKpEmaYBuA43GmvNpnZ_pSz_SWjl1GfBFC7kzqAHQ__MlGuuEpis11Q9HPxpzo/s1600/fig1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhb7octqKntQ_eNqoPHYN44bS1ajk4RiPP551wWyJ_30hkvjYDqlXKZEtAjOGz2N56G_kRKvER6gYG7GvKpEmaYBuA43GmvNpnZ_pSz_SWjl1GfBFC7kzqAHQ__MlGuuEpis11Q9HPxpzo/s1600/fig1.png" /></a></div>
<p>Nel grafico i nodi A B e C rappresentano dei chunk di memoria contigui. Mentre nodi A e C sono liberi il nodo B è un chuck in uso che è stato selezionato per essere liberato con <code>free</code>.</p>
<p>B sa che A non è in uso grazie al bit meno significativo del suo campo <code>size</code> e sa dove si trova grazie al suo campo <code>prev_size</code>. Va a guardare A e scopre la posizione di C grazie al puntatore <code>fd</code> di A che indica la posizione di C.</p>
<p><code>free</code> a questo punto può consolidare lo spazio libero fondendo insieme i chunk A, B e C in un unico chunk la cui dimensione è pari alla somma delle dimensioni dei tre chunk. Nel fare questo <code>free</code> deve aggiornare il valore del puntatore <code>fd</code> di A facendolo puntare a <code>fd</code> di C oltre ovviamente ad aggiornare il campo <code>size</code> di A.</p>
<p>Tutto molto bello, ma in concreto cosa significa? Significa che, se non vengono fatti controlli adeguati, possiamo utilizzare i campi della <code>malloc_chunk</code> per <strong>scrivere valori arbitrari in indirizzi di memoria scelti da noi</strong>. Se avete letto "Smashing The Stack For Fun and Profit" (non smetterò mai di ripeterlo per cui leggetelo!) sapete già cosa significa, se non l'avete fatto: <a href="https://www.youtube.com/watch?v=JJ7tSpPdB_g">"Sciagura a voi!"</a>.</p>
<h1 id="address-space-layout-randomization-secondo-giro">Address Space Layout Randomization (secondo giro)</h1>
<p>Ovvero: "Come faccio ad evitare che un errore di programmazione possa causare la sistematica compromissione delle macchine che si suppone siano sotto il mio controllo?".</p>
<p>Prima di tutto: se siete arrivati fin qui vi faccio i miei complimenti, condensare 20 anni di ricerca sulla sicurezza informatica in queste poche righe è stato un compito arduo ed il testo che ne risulta è inevitabilmente frammentario e pesante da digerire.</p>
<p>Un ultimo sforzo e poi vi giuro che vi spiegherò come si fa a capire in cosa consiste GHOST.</p>
<p>Se avete seguito lo sproloquio sugli heap overflow (o se l'avete saltato perché sapevate già tutto) ora sapete che un mancato controllo su quanto viene scritto in memoria può causare grossi guai. I gap di dimensione casuale sono poco utili contro gli heap overflow e quindi che fare?</p>
<p>Una delle regole della strategia militare recita: "Se non puoi affrontarli direttamente aggirali!". Invece di cercare di prevenire futilmente una sovrascrittura della struttura <code>malloc_chunk</code> facciamo sì che l'attaccante non possa sapere a priori dove si trovano le porzioni di codice che vuole richiamare spargendo casualmente le parti eseguibili di programmi e librerie nello spazio di memoria associato al processo (pur tenendo vicini i moduli funzionali che le compongono).</p>
<p>Da una trentina d'anni i programmi sono compilati in modo da collegarsi a runtime alle librerie di cui hanno bisogno, tutto quello che dobbiamo fare è rendere il processo di linking non deterministico inserendo le librerie e il codice del programma in locazioni di memoria casuali ad ogni avvio del programma. Non solo! Possiamo addirittura fare in modo che ogni nuovo processo creato abbia una disposizione differente rispetto al processo padre che l'ha generato (per maggiori informazioni leggete <a href="http://it.wikipedia.org/wiki/Fork_%28programmazione%29">la pagina di Wikipedia dedicata alla chiamata di sistema fork</a>).</p>
<p>Così facendo complichiamo parecchio la vita a chi scrive malware: ora devono attivamente andare a cercare dove si trova il codice che intendevano eseguire.</p>
<h1 id="sfruttare-ghost-e-exim-per-bucare-una-macchina">Sfruttare GHOST e exim per bucare una macchina</h1>
<p>Finalmente dopo tanto sproloquiare arriviamo al succo del discorso. Come hanno fatto i ricercatori di Qualsys a superare lo stack protector, il bit NX e l'ASLR?</p>
<p>Primo punto: la vulnerabilità si attiva solo in <code>gethostbyname</code> e solo per indirizzi IPv4.</p>
<p>Secondo punto: perché si possa sfruttare questa vulnerabilità occorre che il programma chiami <code>gethostbyname</code> direttamente senza prima chiamare <code>inet_aton</code>. Molti programmi provano prima a vedere se la stringa contiene un indirizzo IP e <code>inet_aton</code> fa questo controllo e ritorna automaticamente un int che contiene il valore dell'indirizzo IP come sarà utilizzato internamente dallo stack TCP/IP. <code>gethostbyname</code> chiama internamente <code>inet_aton</code> per verificare che non si tratti di un nome host e quindi la stringa che passiamo <strong>DEVE</strong> passare il controllo di <code>inet_aton</code>.</p>
<p>Per passare questo controllo occorre che si verifichino le seguenti condizioni:</p>
<ul>
<li>La stringa deve contenere solamente cifre decimali o punti.</li>
<li>La stringa deve cominciare con una cifra.</li>
<li>L'ultimo carattere non può essere un punto.</li>
</ul>
<p>Ovviamente la stringa deve anche essere abbastanza lunga da causare l'overflow del buffer.</p>
<h2 id="going-deerper">Going de[er]per</h2>
<p>Punti bonus a chi ha riconosciuto il gioco di parole realizzato con una regex (sì, non ho una vita sociale degna di nota).</p>
<p>Abbiamo i prerequisiti per far scattare la nostra trappola, ma come dobbiamo metterli assieme per avere successo? Analizziamo ulteriormente il codice vulnerabile alla riga 157:</p>
<pre><code>resbuf->h_name = strcpy (hostname, name);</code></pre>
<p>La cara buona vecchia <code>strcpy</code>, anche nota come "fottitene dei limiti e copia tutto quello che puoi"! In questo caso copia in <code>hostname</code> tutto quello che trova tra <code>name</code> e il primo carattere NUL (Valore ASCII: 0) che incontra. E siccome <code>name</code> lo forniamo noi... :-D</p>
<p>Se ancora ricordate quanto scritto all'inizio sapete che lo spazio allocato è sufficiente per 2 puntatori e per la stringa contenuta in <code>name</code> ma il codice di <code>__nss_hostname_digits_dots</code> (funzione di help chiamata da <code>gethostbyname</code> e sede della vulnerabilità) ha bisogno di 3 puntatori e dello spazio per la stringa <code>name</code>. Quindi possiamo sovrascrivere il numero di bit corrispondenti ad un puntatore: 32 se siamo su x86 e 64 se siamo su AMD64.</p>
<p>La domanda successiva è: quanto danno possiamo fare con i bit a nostra disposizione?</p>
<p>Riscrivere la grandezza di un chunk con un valore maggiore e, quando il programma richiederà altra memoria, potremo riscrivere altre parti della memoria che non avremmo dovuto riscrivere.</p>
<h2 id="exim-o-non-exim">Exim o non exim?</h2>
<p>Arrivati a questo punto dell'articolo vi aspettate una lunga disquisizione tecnica su come si faccia a bypassare le difese. Non ci sarà. Primo perché questo articolo sta già raggiungendo una considerevole lunghezza, secondo perché i dettagli sono spiegati nell'advisory e presto l'exploit sarà aggiunto a <a href="https://www.metasploit.com">Metasploit</a> pronto per l'uso degli script kiddies, terzo perché a questo punto all'autore interessa di più portare il lettore ad alcune conclusioni.</p>
<p>Sopprimete la vostra delusione e cercate di seguirmi per questi ultimi paragrafi.</p>
<p>L'exploit di exim tramite GHOST è particolarmente brutto perché exim stesso adotta due pratiche che si stanno rivelando sempre più pericolose:</p>
<ol>
<li>exim ha un allocatore interno della memoria. Se questo non vi fa suonare un campanello di allarme posso permettermi di ricordare una certa libreria dedicata all'implementazione delle specifiche SSL e TLS e un <a href="http://gnurants.blogspot.com/2014/04/quel-pasticcio-di-heartbleed.html">suo certo bug</a>.</li>
<li>exim ha la possibilità di lanciare comandi arbitrari tramite una modifica del file di configurazione, file che viene copiato nello heap.</li>
</ol>
<p>Ovviamente non possiamo dare tutta la colpa agli sviluppatori di exim: quando hanno operato le loro scelte gestire in proprio l'allocazione della memoria era una buona idea per migliorare le prestazioni, mentre la possibilità di configurare il server di posta in modo che possa lanciare comandi arbitrari in base a certe condizioni aumenta di molto la flessibilità del sistema. Inoltre mappare il file di configurazione in memoria consente un accesso più veloce al medesimo: tutte ragioni legittime insomma ma, come già scritto, il Diavolo è nei dettagli.</p>
<p>Spero che, dopo aver letto questo articolo, siate giunti alla mie medesime conclusioni:</p>
<ul>
<li>Programmare in C vuol dire essere coscienti di quello che si fa e curare maniacalmente il proprio lavoro.</li>
<li>La memoria che contiene i dati in lettura/scrittura dovrebbe essere marcata come non eseguibile e la memoria eseguibile non dovrebbe essere scrivibile.</li>
<li>Si può scrivere codice intelligente (semplice da capire e ben documentato) oppure codice furbo (difficile da capire perché pieno di trucchi per migliorare le prestazioni).</li>
</ul>
<p>Il problema nelle glibc è stato risolto, ma ci sono voluti anni prima che fosse scoperto e corretto. Non stiamo parlando di un'oscura libreria piena di codice crittografico che richiede un Dottorato in Matematica con specializzazione in Teoria dei Numeri, stiamo parlando di una libreria fondamentale che ha decine di sviluppatori e centinaia di occhi che la scrutano.</p>
<p>Simili problemi non dovrebbero esserci perché minano alla base la fiducia di chi basa sistemi critici su quel codice.</p>
<p>Se è vero che "Dato un numero sufficiente di occhi, tutti i bug vengono a galla («given enough eyeballs, all bugs are shallow»)" (legge di Linus citata da <a href="http://it.wikipedia.org/wiki/Eric_Steven_Raymond">Eric Steven Raymond</a> nel saggio <a href="http://it.wikipedia.org/wiki/La_cattedrale_e_il_bazaar">La cattedrale e il bazaar</a> - fonte <a href="http://it.wikipedia.org/wiki/Legge_di_Linus">Wikipedia</a>) è anche vero che le glibc non godono di molti occhi rispetto ad altri progetti (come il kernel Linux).</p>
<p>Purtroppo GNU/Linux non è più un giocattolo per appassionati ed entusiasti ma uno strumento da cui dipendono numerose infrastrutture di rete in tutto il Mondo.</p>
</div>Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-20826705078466444822015-01-09T10:55:00.000+01:002015-01-09T10:55:42.177+01:00Su srand() e OpenBSD<div style="text-align: justify;">
<p>Salve a tutti i miei quattro lettori. In questo che è il mio primo articolo del 2015 tratterò di una questione apparentemente marginale ma che invece ha numerosi risvolti pratici.</p>
<p>Abbiamo visto in uno degli articoli precedenti (<a href="http://gnurants.blogspot.com/2014/12/sui-vizi-e-le-virtu-di-devrandom.html">"Sui vizi e le virtù di /dev/random"</a>) che un buon generatore di numeri pseudocasuali (PRNG: Pseudo Random Number Generator) sia un componente essenziale per la sicurezza di un sistema informatico (leggetevi l'articolo per maggiori informazioni... Vi prego!) e che <code>/dev/random</code> in generale non è la soluzione ottimale. Ma allora cosa dovremmo usare?</p>
<p>L'esempio classico che viene dato nei libri sul linguaggio C e nei tutorial su internet in merito a generazione di numeri pseudocasuali è il seguente:</p>
<pre><code>#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
int main(int argc, char *argv[])
{
/*Seed the RNG*/
srand(time(NULL));
puts("'s' followed by 'Enter' to start the RNG. Ctrl+C to exit\n");
while(fgetc(stdin) != 's')
{
usleep(100000); /*Sleep for 0.1 seconds*/
}
while(1)
{
int r = rand(); /*Get random number*/
printf("%d\n", r);
usleep(100000);
}
return 0;
}</code></pre>
<p>Questo esempio canonico inizializza il generatore pseudocausale con lo UNIX EPOCH corrente e poi stampa numeri tra 0 e <code>RAND_MAX</code>. Come da manuale insomma.</p>
<p>Dove sta il problema con questo codice?</p>
<p>Se andiamo a leggere il manuale di srand scopriamo che:</p>
<pre><code>The srand() function sets its argument as the seed for a new
sequence of pseudo-random integers to be returned by rand().
These sequences are repeatable by calling srand() with the same seed
value.</code></pre>
<p>In Italiano per non addetti ai lavori: se io passo a <code>srand</code> lo stesso numero due volte di seguito otterrò <strong>la stessa sequenza pseudocasuale di numeri</strong>. In altre parole la coppia <code>srand</code>/<code>rand</code> è <strong>DETERMINISTICA</strong> e gli standard C89 e POSIX impongono che sia così.</p>
<p>Si, Virginia, tutto ciò è Male e i due lettori che hanno letto l'articolo su <code>/dev/random</code> sanno anche perché (vi ho già pregato di leggere quell'articolo, vero?). Per coloro i quali fossero stati disattenti la risposta è insita nelle caratteristiche richieste ad un buon generatore di numeri pseudocasuali:</p>
<p>1. Che non ripeta la sequenza generata troppo presto (idealmente pescando centomila numeri interi a 64 bit al secondo il tempo in cui la sequenza comici a ripetersi dovrebbe eccedere i 5 milioni di anni).</p>
<p>2. Che renda difficile predire il numero successivo basandosi sui numeri già usciti (dove per "difficile" intendiamo: "data una sequenza lunga N indovinare il numero alla posizione N+1 deve richiedere più di 2<sup>M</sup> - N operazioni dove M è il numero di bit dei numeri interi generati". Idealmente la lunghezza N dovrebbe essere ininfluente e quindi ogni volta occorrerebbe effettuare 2<sup>M</sup> operazioni).</p>
<p>Ma tutto questo cosa c'entra con <code>srand</code> e <code>rand</code> ? C'entra nel momento in cui qualcuno si mette ad usare codice simile a quello dell'esempio riportato innanzi per compiti che richiederebbero un vero e proprio PRNG. Come è scritto nel manuale dare lo stesso seme a <code>srand</code> produce la medesima sequenza, quindi è facile intuire che, con un po' di prove ed errori è possibile stimare l'ora in cui un servizio è stato avviato e quandi il momento in cui è stata fatta la chiamata a <code>srand</code> (che non è thread-safe e quindi va fatta una volta sola oppure va racchiusa tra due global-lock). A quel punto ricavare la sequenza generata, per quanto difficile, non è impossibile e da lì il passo per fare danni è breve. Se aggiungiamo poi che in certi casi esiste la possibilità di far crshare un servizio e obbligarlo a riavviarsi si intuisce subito che un attaccante può ridurre al minimo l'incertezza sul momento del seed e quindi massimizzare le possibilità di riuscita dell'attacco.</p>
<p>Ok, è una cosa da paranoici, ma è possibile e se è possibile è probabile che qualcuno stia provando a sfruttare questa feature per i suoi loschi fini. In fin dei conti nessuno pensava che OpenSSL potesse divulgare informazioni in giro prima di Heartbleed.</p>
<p>E questo ci porta a vedere cosa hanno deciso di fare quei paranoici di OpenBSD; hanno rotto la compatibilità con POSIX e sostituito le chiamate a <code>rand</code> con chiamate al loro PRNG (una trattazione esaustiva di detto generatore esula dagli scopi di questo articolo, ma invito i più curiosi ad informarsi dando un'occhiata alla <a href="http://www.openbsd.org/papers/eurobsdcon2014_arc4random/mgp00001.html">presentazione che Theo de Raadt ha presentato allo EuroBSD Con del 2014</a> ). Per mantenere il vecchio comportamento occorre chiamare esplicitamente la nuova funzione <code>srand_deterministic</code> invece di <code>srand</code>.</p>
<p>L'idea di spezzare la compatibilità è derivata da un'analisi del codice dei programmi di terze parti inclusi nei ports: la maggiorparte di essi usa <code>rand</code> come una genuina sorgente di numeri pseudocasuali (o crede di farlo) e solo pochissimi software assumono il comportamento deterministico di <code>srand</code> e molti solo a scopo di test.</p>
<p>Quindi come misura ulteriore di sicurezza hanno deciso di rompere la compatibilità e di dare un migliore PRNG a quanti utilizzano <code>srand</code> su OpenBSD.</p>
<p>Se volete saperne di più:</p>
<ul>
<li><p>L'email originale di Theo de Raadt che spiega i motivi della scelta: <a href="http://marc.info/?l=openbsd-tech&m=141807224826859&w=2">http://marc.info/?l=openbsd-tech&m=141807224826859&w=2</a></p></li>
<li><p>Altra email di Theo su alcuni dei numeri usati come seed per <code>srand</code>: <a href="http://marc.info/?l=openbsd-tech&m=141776286105814&w=2">http://marc.info/?l=openbsd-tech&m=141776286105814&w=2</a></p></li>
<li><p>L'articolo del blog di Ted Unangst con ulteriori metodi bizzarri per fare il seed di <code>srand</code>: <a href="http://www.tedunangst.com/flak/post/random-in-the-wild">http://www.tedunangst.com/flak/post/random-in-the-wild</a></p></li>
</ul>
<p>E con questo è tutto! Aloha!</p>
</div>Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com2tag:blogger.com,1999:blog-1360931857234291524.post-16831506926320109812014-12-19T13:52:00.000+01:002014-12-19T13:52:46.834+01:00L'asteroide che ucciderà questo dinosauro deve ancora arrivare (seconda parte)<div style="text-align: justify;">
L'articolo è diviso in tre parti:<br />
<a href="http://gnurants.blogspot.com/2014/07/lasteroide-che-uccidera-questo.html">Prima Parte</a><br />
<a href="http://gnurants.blogspot.it/2014/08/lasteroide-che-uccidera-questo.html">Terza Parte</a><br />
<br />
La volta scorsa abbiamo visto un po' di automi e le basi delle espressioni regolari (ed abbiamo intuito una relazione tra i due). Questa volta faremo un po' meno teoria e un po' più pratica: vi illustrerò i metodi che adopero per leggere e scrivere le regex. <br />
<br />
<h1>
Leggere le espressioni regolari</h1>
Il primo impatto con le regex è (quasi) sempre traumatico, specialmente se nessuno vi ha mai spiegato prima che quelle sono istruzioni per il computer e non usi creativi della punteggiatura ("ma che c[a-z]{0,} !!?"). <br />
<br />
Anche sapendo che il punto ha un significato, il più un altro e l'asterisco un altro significato ancora è facile confondersi e sbagliare. <br />
<br />
Siccome in Rete si possono trovare numerosi esempi di espressioni regolari che eseguono i compiti più disparati molti si limitano a fare copia & incolla senza fermarsi a capire <strong>cosa</strong> effettivamente facciano quegli scampoli di lettere e caratteri apparentemente causali. <br />
<br />
Alla luce di ciò mi pare giusto che, prima di andare avanti, vi spieghi come si leggono le regex. Specialmente perché potreste ritrovarvi a dover modificare un'espressione scritta da qualcun altro molto tempo fa (anche il vostro ego di 8 mesi fa conta come "qualcun altro"). <br />
<br />
Siccome scriverò parecchie regex e siccome le scriverò in mezzo al testo dell'articolo userò la seguente convenzione: le regex saranno scritte in <code>monospace</code> e racchiuse tra singoli slash (<code>/</code>). Gli slash <strong>NON</strong> vanno interpretati come parte della regex ma solo come delimitatori. Questa convenzione è adottata sia dal linguaggio AWK che dal perl e da sed (un tool che vedremo nel prossimo articolo). <br />
<br />
La prima regola è: <strong>comportarsi come la macchina</strong>. <br />
<br />
Le espressioni regolari si leggono un carattere alla volta da sinistra a destra. Non provate a saltare dei pezzi o a fare assunzioni, perché <em>la macchina NON lo fa</em>. <br />
<br />
La seconda regola è: <strong>puntare sempre a riconoscere il più possibile</strong>. <br />
<br />
Facciamo un esempio con questo testo di input: <br />
<br />
<pre><code>Vuolsi così colà dove si puote ciò che si vuole e più non dimandare.</code></pre>
L'espressione regolare <code>/co.*/</code> applicata al testo precedente ritornerà come stringa trovata la seguente porzione: <br />
<br />
<pre><code>così colà dove si puote ciò che si vuole e più non dimandare.</code></pre>
Siccome il <code>.</code> significa "un carattere qualsiasi" e la stella (<code>*</code>) significa "zero o più" quell'espressione si legge come "<code>co</code> seguito da zero o più caratteri qualsiasi". Non essendoci un limite superiore il match prende il primo <code>co</code>, quello di <code>così</code>, e copia in uscita tutto quello che trova fino a raggiungere la fine del testo. <br />
<br />
Se invece avessimo usato l'espressione <code>/co../</code>? Avremmo avuto qualcosa del tipo "<code>co</code> seguito da un carattere qualsiasi seguito a sua volta da un altro carattere qualsiasi. Il risultato sarebbe stato solamente <code>così</code>. <br />
<br />
Il che mi permette di introdurre la terza regola: <strong>salvo indicazione contraria fermati al primo risultato corretto che trovi</strong>. <br />
<br />
Questa regola è importante quando ci si trova davanti ad una espressione regolare che, pur essendo corretta, non riconosce tutto quello che ci interessa riconoscere. La colpa spesso non è della regex, ma delle opzioni che abbiamo passato al programma che la interpreta. <br />
<br />
La seconda regola invece spiega perché certe espressioni regolari funzionano su certi input ma riconoscono anche input che non si voleva riconoscere: di solito perché si è stati troppo generosi nell'uso di <code>.</code>, <code>*</code> e <code>+</code>. <br />
<br />
Armati di queste nuove conoscenze vediamo di capire cosa riconosce la seguente espressione: <br />
<br />
<pre><code>/[0-9]*\.[0-9]+([eE][-+]?[0-9]+)?/</code></pre>
<pre><code>
</code></pre>
Piuttosto complessa, vero? Ma adesso sappiamo come procedere a leggerla (si spera). <br />
<br />
Il primo carattere è una parentesi quadra aperta e quindi quello che segue è la definizione di una classe di caratteri, segue uno <code>0</code> che ci dice che la classe contiene quel carattere. Il <code>-</code> ci dice che stiamo componendo un <em>range</em> di caratteri e il <code>9</code> è il carattere di chiusura del range. La parentesi quadra chiusa termina la definizione della classe. <br />
<br />
Riepilogando: crea una classe composta da tutti i caratteri da <code>0</code> a <code>9</code>. Segue un <code>*</code> che ci dice "zero o più di quello che mi precede", quindi adesso sappiamo che la stringa cercata può cominciare con una o più cifre decimali. <br />
<br />
Il carattere successivo è un backslash (<code>\</code>) che ci informa che il prossimo carattere va interpretato diversamente da come lo si interpreta di solito; infatti il punto che segue normalmente vorrebbe dire "un carattere qualsiasi", ma in questo caso significa "un punto". Quindi lo interpretiamo come un punto letterale. <br />
<br />
Segue una replica della classe che abbiamo definito all'inizio seguita a sua volta da un <code>+</code>. Questo si legge come "una o più cifre decimali". <br />
<br />
La parentesi tonda aperta ci informa che stiamo definendo un gruppo e la parentesi quadra aperta che la segue ci dice che stiamo definendo un'altra classe che contiene una <code>e</code> ed una <code>E</code>. La classe ci dice che il gruppo comincia con una lettera "e" minuscola oppure maiuscola. La classe che la segue ci mostra che il <code>-</code> inserito all'inizio di una classe <strong>non</strong> viene considerato come un separatore di range ma come un carattere letterale. L'espressione <code>/[-+]/</code> significa quindi "un meno oppure un più", seguita da un punto di domanda (come in questo caso) diventa: "può esserci un meno oppure un più, ma può anche non esserci nulla". <br />
<br />
Segue la classe delle cifre con un più che adesso sappiamo vuol dire "una o più cifre decimali", quindi arriva la parentesi tonda che chiude il gruppo e un punto interrogativo. <br />
<br />
Il punto di domanda è un quantificatore che si riferisce al gruppo e quindi il gruppo che abbiamo appena definito può essere presente <strong>in toto</strong> una volta oppure non esserci affatto. <br />
<br />
L'espressione nel suo complesso si legge: "Un punto preceduto eventualmente da alcune cifre decimali e seguito da almeno una cifra decimale e da un gruppo opzionale di caratteri che comincia con una 'e' o una 'E' seguita da un'eventuale indicazione di segno seguita da una o più cifre decimali". In breve si tratta di un qualsiasi numero decimale in virgola mobile positivo con eventuale indicazione dell'esponente. <br />
<br />
<h1>
Scrivere un'espressione regolare</h1>
A quanti non hanno ancora desistito e stanno proseguendo la lettura va il mio più sentito ringraziamento. Per premiarvi di tanta dedizione adesso vi confiderò il metodo che adopero per scrivere una regex (nella segreta speranza che vi sarà utile un giorno). <br />
<br />
Per rendere le cose più facili (o più difficili) espanderemo l'espressione vista nella sezione precedente, che riporto di seguito per ridurre l'usura delle rotelline dei mouse: <br />
<br />
<pre><code>/[0-9]*\.[0-9]+([eE][-+]?[0-9]+)?/</code></pre>
<pre><code>
</code></pre>
Questa espressione ha due difetti: <br />
<br />
<ul>
<li>Non riconosce i numeri decimali negativi nè quelli positivi preceduti da un più (<code>+</code>).</li>
<li>Non riconosce i numeri decimali come <code>1.</code> oppure <code>47.</code></li>
</ul>
Se volessimo riconoscere tutti i numeri decimali in virgola mobile quell'espressione mancherebbe diversi bersagli. <br />
<br />
La prima cosa che faremo sarà aggiungere il segno. Sappiamo che il segno può essere un <code>-</code> oppure un <code>+</code> oppure nulla e sappiamo che se è presente si trova al primo posto, prima cioè di qualsiasi altro carattere che compone un numero decimale in virgola mobile. <br />
<br />
Dalla nostra analisi dell'espressione abbiamo già trovato l'espressione che riconosce il segno: <code>/[-+]?/</code>. Ci limiteremo ad inserirla nel posto giusto: <br />
<br />
<pre><code>/[-+]?[0-9]*\.[0-9]+([eE][-+]?[0-9]+)?/</code></pre>
<pre><code>
</code></pre>
Risolto il nostro primo problema dobbiamo cercare una maniera per risolvere il secondo problema. <br />
<br />
La prima cosa che si deve fare quando si crea una regex è <strong>cercare un schema generale che si ripeta</strong>. Nel caso dei numeri decimali con il punto alla fine lo schema è proprio il punto alla fine: deve esserci sempre, altrimenti non stiamo leggendo un numero decimale in virgola mobile. <br />
<br />
Quindi il punto dev'esserci e deve stare alla fine, ma davanti cosa ci va? Una o più cifre decimali eventualmente precedute dal segno. <br />
<br />
Sappiamo che il simbolo <code>+</code> indica che quello che lo precede dev'essere presente "una o più volte" e che il simbolo <code>?</code> significa che ciò che lo precede dev'essere presente zero oppure una volta ma non di più. <br />
<br />
Quindi l'espressione per cercare i numeri decimali in virgola mobile composti da un numero seguito da un punto è la seguente: <br />
<br />
<pre><code>/[-+]?[0-9]+\./</code></pre>
<pre><code>
</code></pre>
Abbiamo usato due classi, due quantificatori e un simbolo letterale per trovare tutti e soli i numeri simili a <code>47.</code>. L'inizio di questa espressione somiglia moltissimo all'inizio dell'espressione precedente e potremmo essere tentati di sostituire la stella (<code>*</code> che significa "zero o più senza limite superiore") con il più (che significa "uno o più senza limite superiore"). Ricaveremmo la seguente espressione: <br />
<br />
<pre><code>/[-+]?[0-9]+\.[0-9]+([eE][-+]?[0-9]+)?/</code></pre>
<pre><code>
</code></pre>
Facendo così però abbiamo imposto che ci siano delle cifre prima e dopo il punto, restringendo la gamma di numeri che riconosciamo anzichè ampliarla. <br />
<br />
Se invece sostituissimo i due <code>+</code> dell'espressione appena trovata con due stelle? Otterremmo questa: <br />
<br />
<pre><code>/[-+]?[0-9]*\.[0-9]*([eE][-+]?[0-9]+)?/</code></pre>
<pre><code>
</code></pre>
E riconosceremmo sia i numeri che hanno delle cifre prima del punto ma niente dopo che quelli che hanno delle cifre dopo il punto. Peccato che la nuova espressione sia fin troppo generosa e riconosca anche le seguenti stringhe come valide: <br />
<br />
<ul>
<li><code>.</code></li>
<li><code>-.e0</code></li>
<li><code>.E-0</code></li>
</ul>
E noi non le vogliamo perché quelle stringhe non sono numeri validi! <br />
<br />
Che si fa? O siamo troppo rigorosi <em>oppure</em> siamo troppo permissivi... Uhm... Non c'era un operatore che ci permetteva di dire "questo oppure quello ma non tutti e due"? Sì, Virginia, c'è e si tratta della barra verticale (<code>|</code>) che i fan di UNIX chiamano "<em>pipe</em>" perché ha un significato ben preciso nella shell UNIX. <br />
<br />
Il segno opzionale all'inizio ci va bene e lo lasceremo dov'è, creeremo invece un gruppo che conterrà al suo interno un <code>|</code> per spezzare in due le possibilità di riconoscimento. Nella prima parte metteremo l'espressione per i numeri come <code>47.</code> e nella seconda metteremo l'espressione originale che abbiamo visto nella sezione precedente. <br />
<br />
Quindi abbiamo il segno: <br />
<br />
<pre><code>/[-+]?/</code></pre>
<pre><code>
</code></pre>
Poi apriamo un gruppo e ci mettiamo i numeri con prima le cifre e poi il punto <strong>e basta</strong> seguiti da un "oppure": <br />
<br />
<pre><code>/[-+]?([0-9]+\.|/</code></pre>
<pre><code>
</code></pre>
E infine rimettiamo l'espressione originaria e chiudiamo il gruppo: <br />
<br />
<pre><code>/[-+]?([0-9]+\.|[0-9]*\.[0-9]+([eE][-+]?[0-9]+)?)/</code></pre>
<pre><code>
</code></pre>
Rileggiamo la nostra nuova espressione: un segno opzionale seguito da una o più cifre seguite da un punto oppure da zero o più cifre seguite da un punto seguito da una o più cifre seguito da un esponente che si compone della lettera e (maiuscola o minuscola) seguita da un segno opzionale seguito da una o più cifre. <br />
<br />
Vi lascio come compito per casa l'espansione di quest'ultima espressione regolare affinché riconosca anche i numeri decimali interi: una o più cifre decimali precedute da un simbolo di segno opzionale e nessun punto. <br />
<br />
La prossima volta ci occuperemo di alcuni programmi della shell UNIX che fanno largo uso delle regex. <br />
<br />
Aloha! <br />
<br /><a href="http://gnurants.blogspot.com/2014/07/lasteroide-che-uccidera-questo.html">Prima Parte</a><br />
<a href="http://gnurants.blogspot.it/2014/08/lasteroide-che-uccidera-questo.html">Terza Parte</a><br /></div>
Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-89467389903261046102014-12-19T13:51:00.000+01:002014-12-19T13:51:33.158+01:00L'asteroide che ucciderà questo dinosauro deve ancora arrivare (prima parte)<div style="text-align: justify;">
<i>Disclaimer:</i> l'articolo che segue non è un rant né l'analisi di una qualche vulnerabilità di sicurezza. Si tratta di un articolo su una delle basi teoriche che fanno da fondazione ad una marea di strumenti e di software. Se non siete interessati o avete una fobia per le lezioni che vi portate dietro dai vostri trascorsi da studenti passate oltre.<br />
L'articolo è diviso in tre parti:<br />
<a href="http://gnurants.blogspot.it/2014/07/lasteroide-che-uccidera-questo_27.html">Seconda Parte</a><br />
<a href="http://gnurants.blogspot.it/2014/08/lasteroide-che-uccidera-questo.html">Terza Parte</a><br />
<br />
Riconoscere un pattern in un testo è un'operazione piuttosto comune: si va dalla ricerca di una parola (o di parte di una parola) in pagine Web o in documenti di testo e si arriva a cose come ricerca e sostituzione di date dal formato americano (MM/GG/AAAA) al formato europeo (GG/MM/AAAA).<br />
<br />
Di solito chi si intende di programmazione riconosce immediatamente questi compiti come tipiche operazioni da affidare alla macchina: si tratta infatti di attività tediose, altamente ripetitive e che richiedono l'applicazione pedissequa di una sequenza limitata di istruzioni. Compiti simili hanno risultati disastrosi se affidati ad un essere umano ma sono ideali per un computer.<br />
<br />
Ed in effetti questi compiti sono stati oggetto di studio per interi decenni da parte di quel branco di matematici pigri che si chiamano informatici (o Computer Scientists in lingua inglese). Oltre a trovare metodi ottimi per la ricerca di singole parole in un testo (Algoritmo di Knuth, Morris e Pratt) gli informatici del passato hanno studiato attentamente i pattern e i modi di definirli e di riconoscerli.<br />
<br />
<h1 id="automi-e-dinosauri">
Automi e Dinosauri</h1>
No, non si tratta di Transformers. Gli automi di cui discuteremo sono dei modelli teorici molto comuni in informatica ed ingegneria: gli automi a stati finiti. Sono utilizzati per modellare i processi in termini di stati e transizioni. Più propriamente tratteremo gli automi a stati finiti deterministici; chiamati così perché hanno un numero finito di stati e in ogni momento della loro esecuzione in base all'input e allo stato si avrà una ed una sola transizione verso un altro stato.<br />
<br />
Ora che i vostri occhi hanno smesso di roteare cominciamo con la teoria pesante! :-D<br />
<br />
Partiremo con l'analisi di un automa che, dato un testo in ingresso, stabilisce se all'interno del testo è presente una sequenza di almeno 3 'a' consecutive. Di seguito il grafico dell'automa:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgMkgNJPmi7CpRlNqumauPAD2EsxCSn20ETvLlCpYMPXSVt3EZ98kbFKe_Z4Xijfd5aRfovPck75eK9C9CC0ZNfiDCNDdFuawAX9u27rirQRqyY5Ez05mCZPw8revHRNVrTyznmPJEfkRg/s1600/automata01.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgMkgNJPmi7CpRlNqumauPAD2EsxCSn20ETvLlCpYMPXSVt3EZ98kbFKe_Z4Xijfd5aRfovPck75eK9C9CC0ZNfiDCNDdFuawAX9u27rirQRqyY5Ez05mCZPw8revHRNVrTyznmPJEfkRg/s1600/automata01.png" /></a></div>
Dal grafico è facile vedere come l'automa procede nel suo compito: si comincia dallo stato START e si legge un carattere, in base al carattere letto si decide quale transizione seguire. Se si arriva nello stato OK si interrompe la computazione e si comunica il successo, se si esaurisce il testo di input senza essere arrivati allo stato OK l'input non contiene nessuna sequenza di (almeno) tre <code>a</code>.<br />
<br />
Nel gergo degli informatici diciamo che ad ogni transizione consumiamo un carattere per indicare il fatto che, dopo ogni passaggio di stato, l'automa legga il carattere successivo del suo input.<br />
<br />
Scrivere un programma che legga dallo standard input e stampi "OK" se c'è una sequenza di 3 o più <code>a</code> è un tipico esercizio che viene dato ai principianti di un linguaggio di programmazione. Avendo presente il grafico di prima l'esercizio diventa veramente semplice dal punto di vista concettuale: praticamente il programma <b>È</b> il grafico, si tratta solo di riportarlo in una sequenza di istruzioni comprensibili dalla macchina.<br />
<br />
Da quanto scritto poc'anzi si deduce che esiste una nave portacontainer piena di applicazioni che cercano in un testo la sequenza "aaa". Una queste applicazioni è anche uno dei miei strumenti preferiti della shell UNIX: <code>grep</code>.<br />
<br />
<code>grep</code> è uno dei dinosauri di UNIX che si rifiutano di estinguersi. Nasce come modalità di ricerca di <code>ex</code> (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.<br />
<br />
<h1 id="espressioni-regolari">
Espressioni Regolari</h1>
Prima di elencarvi i numerosi pregi di <code>grep</code>, però, devo illustrare le espressioni regolari e la loro (torbida) relazione con gli automi deterministici.<br />
<br />
Abbiamo visto come gli automi deterministici siano in grado di riconoscere una sequenza di lettere (anche se non particolarmente interessante), ora vedremo quali siano le reali capacità dei nostri automi con un compito decisamente più complesso: riconoscere in un testo la presenza di date in formato americano (MM/GG/AAAA dove MM sono le cifre del mese, GG quelle del giorno e AAAA quelle dell'anno). Non solo! Ci divertiremo ad associare le cifre a dei gruppi e ad accettare tre tipi di separatore: la barra (<code>/</code>), il trattino (<code>-</code>) e il caro buon vecchio spazio (che eviterò di inserire tra parentesi per ragioni che hanno a che fare con il modo in cui i browser interpretano il linguaggio HTML).<br />
<br />
Anche in questo caso partirò da un grafico:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhaxljJuVFA8Iftq51QEiMDRvdLYmrMXilTHHRz45-71mQ7iSH9BqDVAMvIouX3ExwS2nxUSvE0kXX_M1xZOz_aMUIqYvTWVDEtYgYjWv7pp_wiHnRuByGXKj2Yz09trx2lY6B9QvVff84/s1600/automata02.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhaxljJuVFA8Iftq51QEiMDRvdLYmrMXilTHHRz45-71mQ7iSH9BqDVAMvIouX3ExwS2nxUSvE0kXX_M1xZOz_aMUIqYvTWVDEtYgYjWv7pp_wiHnRuByGXKj2Yz09trx2lY6B9QvVff84/s1600/automata02.png" /></a></div>
Per brevità (e per esigenze di impaginazione) alcune transizioni sono state riunite in un'unica transizione etichettata con "m...n" dove m e n sono due numeri ed m è minore di n.<br />
<br />
I più attenti tra di voi avranno immediatamente notato che si tratta di un automa costruito a partire da tre automi concatenati tra loro in maniera opportuna. Si tratta di una tecnica piuttosto comune e molto utilizzata: risolvere prima dei sotto-problemi e poi costruire con le soluzioni trovate una soluzione ad un problema più complesso è un tipico schema di progettazione dei software che prende il nome di Bottom-Up.<br />
<br />
Per quanto i grafici visti fin'ora siano una rappresentazione amichevole per noi esseri umani lo sono molto meno per la macchina (oltre ad essere alquanto tediosi da disegnare per il sottoscritto). C'è un metodo più immediato per descrivere un automa a stati finiti deterministico alla macchina?<br />
<br />
La risposta a questa domanda è: "Sì, c'è un metodo: le espressioni regolari".<br />
<br />
Le espressioni regolari sono stringhe di testo che descrivono dei pattern usando dei caratteri speciali. Permettono di creare le stesse strutture che si possono creare con gli automi a stati finiti deterministici (c'è una dimostrazione formale che lo dice, ma sono troppo pigro per riproporvela: per cui fidatevi oppure andate ad interrogare un motore di ricerca e preparatevi psicologicamente a leggere pagine e pagine in matematichese stretto) e quindi sono interscambiabili con i grafici del tipo che vi ho fatto vedere in questo articolo.<br />
<br />
Ad un occhio non allenato le espressioni regolari sembrano parole scritte in una lingua incomprensibile (ed in effetti lo sono), ma una volta apprese consentono di esprimere molto efficacemente tutta la gamma di pattern riconosciuti dagli automi finiti deterministici (che per brevità chiamerò DFA dalle iniziali di Deterministic Finite Automata).<br />
<br />
Fatta eccezione per alcuni caratteri particolari (che vedremo in seguito) i caratteri di una espressione regolare corrispondono ai caratteri cercati. Per cui l'spressione regolare <code>aaa</code> corrisponde al primo automa che abbiamo visto in questo articolo.<br />
<br />
Il punto (<code>.</code>) indica un carattere qualsiasi (lettera o numero o simbolo di punteggiatura). Per indicare il punto come un carattere a sè occorre aggiungere un backslash (<code>\</code>) davanti al punto. Il <code>\</code> infatti indica che il carattere che segue deve essere essere considerato diversamente dal solito. La sequenza <code>\t</code> corrisponde al TAB, mentre <code>\n</code> indica l'andare a capo. La sequenza <code>\\</code> viene sostituita con un singolo backslash.<br />
<br />
Se avessimo voluto indicare una sequenza di sole tre <code>a</code> (non tre o più) avremmo dovuto fare uso di un quantificatore: <code>a{3}</code>. I numeri che compaiono tra le parentesi graffe quantificano in numero di volte in cui si deve verificare la presenza del gruppo che li precede (vedremo dopo cosa sono i gruppi).<br />
<br />
Tramite le parentesi graffe si può anche indicare che un gruppo possa comparire un numero di volte compreso tra due numeri. Ad esempio se volessimo indicare un numero di <code>a</code> compreso tra due e quattro scriveremmo <code>a{2,4}</code>. Se il secondo numero è omesso viene considerato pari ad infinito, se viene omesso il primo allora viene considerato pari ad uno.<br />
<br />
Esistono anche altri quantificatori:<br />
<br />
<ul>
<li><code>+</code> indica <b>una o più</b> occorrenze del gruppo che precede. Equivale a <code>{,}</code>.</li>
<li><code>*</code> indica <b>zero o più</b> occorrenze del gruppo che precede. Equivale a <code>{0,}</code>.</li>
<li><code>?</code> indica <b>zero od una</b> occorrenza del gruppo che precede. Equivale a <code>{0,1}</code>.</li>
</ul>
Abbiamo nominato i gruppi in lungo e in largo, è giunta l'ora di definirli: un gruppo consiste in una o più sotto-espressioni regolari racchiuse da parentesi tonde. Nel caso di caratteri singoli le parentesi possono essere omesse: <code>(a){3}</code> equivale ad <code>a{3}</code>.<br />
<br />
I gruppi separano un'espressione complessa in diverse sottoespressioni che possono essere trattate singolarmente.<br />
<br />
Rimane un'ultimo argomento da trattare prima di provare a convertire l'automa delle date in una espressione regolare: le classi.<br />
<br />
Una classe è un insieme di caratteri racchiusi tra due parentesi quadre. Quando si incontra una classe la si può sostituire con una qualsiasi dei caratteri che contiene. Ad esempio: <code>[0123456789]</code> indica tutte le cifre da 0 a 9. Per brevità le classi composte da caratteri che si susseguono in ordine possono essere definite indicando solo il primo e l'ultimo carattere separati da un <code>-</code>. La classe di prima perciò diventa: <code>[0-9]</code>.<br />
<br />
È possibile utilizzare la notazione compatta anche con classi eterogenee, ad esempio per indicare tutte le lettere maiuscole o minuscole e tutte le cifre da 0 a 9 si può scrivere: <code>[A-Za-z0-9]</code>.<br />
<br />
All'interno di un gruppo o di una classe è possibile che sia presente il carattere <code>|</code> che si può leggere come "oppure". Ad esempio una classe che indichi una a oppure una b oppure una c si può anche scrivere come <code>[a|b|c]</code>.<br />
<br />
Adesso armiamoci di pazienza e cominciamo a tradurre l'automa in una regex (da REGular EXpression: espressione regolare).<br />
<br />
La prima cosa che notiamo è che dallo stato iniziale possiamo andare in tre rami mutualmente esclusivi: 0, da 2 a 9 e 1. Con il ramo centrale abbiamo già riconosciuto un mese, mentre coi due rami laterali dobbiamo passare per uno stato intermedio. inoltre il passaggio dallo stato MB allo stato MESE può avvenire anche nel caso in cui non ci sia un carattere dopo l'uno (nel grafico si è indicato il carattere nullo con la lettera greca ε). Quindi abbiamo 0 seguito da 1-9 oppure 1 seguito opzionalmente da 0-2 oppure 2-9. In regex diventa: <code>(0[1-9]|1[0-2]?|[2-9])</code>. Ricordatevi che una classe rappresenta UN singolo carattere che fa parte della classe stessa e che i quantificatori agiscono sul gruppo (o sul carattere) che PRECEDONO. Rileggete questo paragrafo e osservate l'espressione finché non vi sarà chiaro cosa significano tutti quei simboli e ne saprete già un bel po' sulle regex.<br />
<br />
La transizione tra MESE e START_GIORNO è banale: <code>[-\/\ ]</code>. Il <code>-</code> è stato messo per primo così da non essere confuso con l'indicatore di range di caratteri, seguono lo slash (<code>/</code>) e lo spazio preceduti dal backslash per indicare che vanno interpretati letteralmente.<br />
<br />
Il giorno si costruisce in maniera simile al mese (e ve lo lascio come esercizio) mentre l'anno si può indicare molto brevemente tramite l'uso di classi e quantificatori: <code>[0-9]{4}</code>.<br />
<br />
Ci salutiamo qui per ora, ma ci sarà un seguito a questo articolo in cui vedremo altra teoria pesante, sempre che gli altri GNUrants non mi rinchiudano e non gettino via la chiave!<br />
<br />
<a href="http://gnurants.blogspot.it/2014/07/lasteroide-che-uccidera-questo_27.html">Seconda Parte</a><br />
<a href="http://gnurants.blogspot.it/2014/08/lasteroide-che-uccidera-questo.html">Terza Parte</a><br />
</div>
Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-52618229334747177732014-12-18T13:26:00.000+01:002014-12-19T08:34:18.938+01:00Come avviare il proprio OS linux direttamente dal firmware efi<div style="text-align: justify;">
<div style="text-align: left;">
<div style="text-align: justify;">
Dopo aver sperimentato in prima persona questa follia, sono pronto a insegnarvi la sacra arte dello <i>sminchiare il pc, ma con classe</i>. </div>
</div>
</div>
<div style="text-align: justify;">
<div style="text-align: left;">
<div style="text-align: justify;">
Innanzitutto cosa è necessario: avremo bisogno di un kernel linux > 3.3 e le seguenti opzioni attive nella sua config: <a href="https://wiki.archlinux.org/index.php/Unified_Extensible_Firmware_Interface#Linux_Kernel_Config_options_for_UEFI">Kernel options needed</a> (in archlinux esse sono attive di default, come penso in tutte le distro più recenti)</div>
</div>
</div>
<div style="text-align: justify;">
<div style="text-align: left;">
<div style="text-align: justify;">
L'unica motivazione plausibile per provare a farlo è quella di voler eliminare il bisogno di un bootloader (tipo grub) per avviare il proprio OS, sfruttando appieno UEFI.<br />
In teora (non ho potuto testare perché il mio laptop è linux-only) non si dovrebbero avere problemi con eventuali multiboot con windows o altri sistemi che già utilizzino UEFI.</div>
</div>
</div>
<div style="text-align: justify;">
<div style="text-align: left;">
<div style="text-align: justify;">
La prima cosa di cui si ha bisogno è una tabella delle partizioni del disco di tipo GPT. Essa offre molti vantaggi rispetto al vecchio MBR, per informazioni vi rimando qua: <a href="https://wiki.archlinux.org/index.php/GUID_Partition_Table#Advantages_of_GPT">Advantages of GPT</a>.</div>
</div>
</div>
<div style="text-align: justify;">
<div style="text-align: left;">
<div style="text-align: justify;">
Vediamo quindi subito che tipo di partizionamento stiamo usando. Installate il tool gdisk e lanciate da root <br />
<pre>gdisk /dev/sdX</pre>
(dove X è la lettera del disco che ci interessa).</div>
</div>
</div>
<div style="text-align: justify;">
<div>
<div style="text-align: justify;">
Un risultato del genere ci dirà che siamo su MBR:</div>
<pre>MBR: MBR only
GPT: not present</pre>
</div>
</div>
<div style="text-align: justify;">
Altrimenti, per GPT, riceveremmo<br />
<pre><span style="text-align: center;">MBR: protective</span>
<span style="text-align: center;">GPT: present</span></pre>
</div>
<div style="text-align: justify;">
<div style="text-align: left;">
<div style="text-align: justify;">
Nel caso fossimo su MBR, ora ci appresteremo a convertire a GPT il nostro disco. Nessuna perdita di dati ovviamente. </div>
<div style="text-align: justify;">
<b>DISCLAIMER</b>: <u>non ritenetemi colpevole di qualsivoglia perdita di dati. Fate comunque un backup se non vi fidate</u> (<b>NON FIDATEVI!</b>)</div>
</div>
</div>
<div style="text-align: justify;">
<div style="text-align: left;">
<div style="text-align: justify;">
Ci sarà bisogno di una live, io per tutta la prima parte (cioè la conversione a GPT e la creazione della partizione EFI + impostazione di fstab per montare la partizione EFI in /boot) ho usato una live grafica (archbang nello specifico) e gparted; per l'ultimissima parte ho dovuto usare una live di archlinux (l'ultima disponibile), poiché non riuscivo ad avviare archbang da UEFI.</div>
</div>
</div>
<div style="text-align: justify;">
<div style="text-align: left;">
<div style="text-align: justify;">
Innanzitutto controllate che l'ultima partizione sul disco non termini alla fine dello stesso (cioè che lasci un po' di spazio libero). Se così non fosse, tramite gparted ridimensionate l'ultima partizione lasciando 500Kb (in linea teorica bastano 20Kb) a fine disco.</div>
</div>
</div>
<div style="text-align: justify;">
<div style="text-align: left;">
<div style="text-align: justify;">
Aprite gdisk e uscite con l'opzione “w” che convertirà il disco in GPT. State attenti all'output; se non vi dà errori, siete pronti a proseguire.</div>
</div>
</div>
<div style="text-align: justify;">
<div style="text-align: left;">
<div style="text-align: justify;">
Adesso, se non è già presente (ad esempio se avevate windows 8 installato sul pc, probabilmente ci sarà già) bisognerà creare una partizione EFI (tramite gparted sempre), da 512Mb, formattata in FAT32; assegnategli il flag <u>boot</u> (attenzione, non legacy_boot). Io ho ridimensionato la mia root per crearla.</div>
</div>
</div>
Ora montate la root del vostro OS e la partizione EFI, e modificate /etc/fstab per far montare la partizione EFI in /boot, ossia aggiungete una linea del genere, modificando sdXY con la vostra partizione EFI:<br />
<div>
<pre>/dev/sdXY /boot vfat defaults,noatime 0 1</pre>
Siamo quasi pronti; adesso copiate il contenuto di /boot (sempre dalla directory in cui avete montato la vostra root) nella partizione EFI (di modo che al primo avvio, quando verrà montata come /boot, non ci siano problemi).<br />
Bene; dopo aver smontato la root e la partizione EFI, possiamo riavviare.<br />
<div style="text-align: justify;">
<div style="text-align: left;">
<div style="text-align: justify;">
<br /></div>
</div>
</div>
<div style="text-align: justify;">
<div style="text-align: left;">
<div style="text-align: justify;">
Nell'ultima parte utilizzeremo la live di archlinux poiché abbiamo bisogno di un sistema che booti su uefi. Prima di tutto, disabilitate il secure boot dal bios (o meglio, io l'ho disabilitato per comodità, altrimenti seguite questo: <a href="https://wiki.archlinux.org/index.php/Unified_Extensible_Firmware_Interface#Secure_Boot">Boot archlinux live media with secure boot enabled</a> ).</div>
</div>
</div>
Attiviamo ovviamente la modalità UEFI dal bios, e procediamo al boot della live di arch.<br />
Ci manca solo da dare un comando:</div>
<div>
<pre>efibootmgr -d /dev/sdX -p Y -c -L "Arch Linux" -l /vmlinuz-linux \
-u "root=/dev/sdXZ rw initrd=/initramfs-linux.img"</pre>
dove X è la lettera del disco su cui c'è la partizione EFI, e Y è il numero della partizione EFI. Z invece è il numero della partizione root (attenzione è un comando unico, anche se qua è spezzato su due righe). Nel caso aveste opzioni che passavate alla command line del kernel, aggiungetele alla fine del comando precedente, prima delle virgolette alte conclusive.<br />
Ora diamo un:</div>
<div>
<pre>efibootmgr -v </pre>
e controlliamo che sia tutto in ordine. Fatto ciò, possiamo riavviare rimuovendo la chiavetta. Godetevi il vostro boot da UEFI! E disinstallate pure grub/syslinux ;)<br />
<br />
Ps: ringrazio il fantastico wiki di archlinux che è colmo di informazioni e su cui si appoggia la guida.</div>
Anonymoushttp://www.blogger.com/profile/03854199872890515528noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-69032225308052166922014-12-01T17:17:00.000+01:002014-12-02T08:14:36.723+01:00Sui vizi e le virtù di /dev/random<div style="text-align: justify;">
<p>Eccomi qui a scrivere un articolo su una delle componenti fondamentali del kernel Linux (e non solo): <code>/dev/random</code>.</p>
<p>Come si può ricavare dal suo path <code>/dev/random</code> è un <strong>character device</strong> che, una volta letto, emette una sequenza pseudocasuale di byte.</p>
<p>Se volete riempire completamente il vostro terminale di caratteri casuali vi basta invocare il seguente comando:</p>
<pre><code>cat /dev/random</code></pre>
<p>Ovviamente vi consiglio <strong>CALDAMENTE</strong> di <strong>NON FARLO</strong>, ma si sa: il Mondo è pieno di masochisti e magari a qualcuno di voi potrebbe piacere!</p>
<p>Tralasciando gli scherzacci per cosa può essere utile un simile device?</p>
<ol>
<li><p>Creazione di password pseudocasuali mediante shell-fu:</p>
<pre><code>dd if=/dev/random bs=1 count=6 2> /dev/null | base64 | \
sed -r 's/[^A-Z|a-z|0-9]//g'</code></pre></li>
<li><p>Simulatore di tiri di dado per Giochi di Ruolo (se siete veri nerd sapete di cosa sto parlando).</p></li>
<li><p>Cancellazione sicura di un disco: prima di formattarlo potete sovrascrivere i suoi dati con un l'output di <code>/dev/random</code> per un certo numero di volte.</p></li>
</ol>
<p>Queste sono solo alcune delle idee che potrebbero essere implementate grazie a letture da <code>/dev/random</code>, una di queste idee però si scontrerà subito con il principale limite del generatore di numeri pseudocasuali. Sapete per caso dirmi quale?</p>
<p>Chi ha risposto "la terza!" vince un simpatico sguardo condiscendente! Chi invece non sapeva la risposta potrà leggere la spiegazione nel prossimo paragrafo.</p>
<p>La procedura per interrogare <code>/dev/random</code> si compone dei seguenti passi: si apre un file descriptor e lo si associa al device, si richiedono i dati tramite una chiamata <code>read</code> (<a href="http://linux.die.net/man/2/read">http://linux.die.net/man/2/read</a> ), si <em>ASPETTA</em> che <code>read</code> popoli il buffer con i dati richiesti, si chiude il file descriptor.</p>
<p>No, Virginia, non ho evidenziato in corsivo la voce del verbo aspettare per puro vezzo personale. <code>/dev/random</code> non è sempre disponibile ad inviare dati pseudocasuali perché ha bisogno che ci sia una sufficiente entropia per generare dei <strong>buoni</strong> numeri pseudocasuali. La teoria matematica che sta dietro ai generatori di numeri pseudocasuali è piuttosto complicata ed esula da quelli che sono gli scopi di questo articolo, se avete parecchio tempo da spendere e un diploma di scuola media superiore potete cercare "PRNG" (Pseudo Random Number Generator) su Wikipedia (meglio se interrogate la versione inglese) e smarrirvi in un buco nero di congetture, lemmi e teoremi.</p>
<p>Per chi va di fretta la versione TLDR è la seguente: ogni PRNG è un algoritmo che gira su una macchina deterministica (se la macchina è nello stato X e legge N andrà sempre nello stato Y) e quindi ogni PRNG è condannato prima o poi (meglio se <strong>molto</strong> poi) a replicare la sequenza di numeri che ha generato dall'inizio. Questa caratteristica si chiama <strong>periodo</strong> del generatore ed è molto importante per distinguere un buon generatore (leggasi: un generatore che un periodo molto lungo) da uno cattivo. Ma non basta! Ogni PRNG è tale per cui da una sequenza sufficientemente lunga si può ricavare quali saranno i prossimi numeri generati <strong>prima</strong> che essi vengano generati. Un buon PRNG deve fare in modo che la sequenza che permetta una simile previsione sia la più lunga possibile.</p>
<p>Una maniera che hanno i creatori di PRNG per allungare il periodo ed introdurre una maggiore casualità nella sequenza (rendendo più difficile la previsione dei numeri successivi) è effettuare un (a)periodico re-seed (re-inseminazione mi pareva brutto da scrivere... OPS!) dell'algoritmo da altre fonti di numeri casuali. Semplificando molto quello che si fa è far ripartire il generatore da un altro numero rispetto a quello da cui era partito all'inizio, generando quindi una nuova sequenza.</p>
<p>Sì Virginia? Ah ti stai chiedendo cosa c'entri tutto questo con l'aspettare? Tutto dipende da quanto disordine c'è nel tuo sistema nel momento in cui vai ad interrogare <code>/dev/random</code>. Non è chiaro, allora lasciami spiegare un altro po'.</p>
<p>Come scritto poc'anzi ogni PRNG che consenta il re-seed ha bisogno di un numero di partenza: tanto maggiore è la casualità con cui ricava questo numero ad ogni re-seed tanto migliore sarà la sequenza che ne sarà generata. Verrebbe la tentazione di usare un altro PRNG come generatore di semi per il nostro PRNG ma ci ritroveremmo con il solito problema dell'uovo e della gallina. Per mitigare questo di solito quello che si fa è sfruttare una fonte di disordine esterna alla macchina: l'utente.</p>
<p>La pressione dei tasti, il flusso di dati via rete o da/per il disco rigido, i tempi di latenza delle periferiche sono tutte possibili fonti di disordine che, per essere affini con la teoria dell'informazione di Claude Elwood Shannon, chiameremo <strong>entropia</strong>.</p>
<p>Maggiore è l'entropia del sistema maggiore sarà la casualità con cui viene prodotto il seme che darà l'avvio alla sequenza di numeri. Intuitivamente possiamo supporre che occorra un certo tempo perché all'interno di un sistema si formi una quantità sufficiente di entropia e che una richiesta continua di numeri pseudocasuali causi l'esaurimento dell'entropia con conseguenze catastrofiche sulla lunghezza del periodo.</p>
<p>Per questa ragione <code>/dev/random</code> blocca qualsiasi richiesta finché non ha abbastanza entropia per soddisfarla, bloccando quindi qualsiasi software che fa uso dei suoi servizi.</p>
<p>Come palliativo gli sviluppatori di Linux hanno creato <code>/dev/urandom</code>: una versione non-bloccante di <code>/dev/random</code> che ricicla i numeri generati in caso di esaurimento dell'entropia del sistema. Eliminando così tutti i benefici derivanti dal re-seeding.</p>
<p>Ora starete pensando che un utente accorto può effettivamente fare un buon uso di <code>/dev/random</code> limitando le chiamate e creando un proprio PRNG all'interno dei suoi programmi... Sorvolando sull'intera questione del "perché usare <code>/dev/random</code> allora?" punto il dito su quanto scritto prima: scrivere un buon PRNG richiede numerose conoscenze e capacità e ci si espone molto facilmente ad attacchi se si decide di fare affidamento ad algoritmi men che perfetti.</p>
<p>In sostanza: se non siete dei guru, non fatelo.</p>
<p>C'è un'altra circostanza in cui l'uso di <code>/dev/(u)random</code> è sconsigliato: per ottenere un numero casuale occorre eseguire la procedura sopradescritta che consta di tre fasi. Aprire un file descriptor può non essere possibile (sì, Virginia, un processo può esaurire il numero massimo di file che può aprire in contemporanea), inoltre un'operazione che dovrebbe essere atomica (indivisibile) viene divisa in tre operazioni. Questo è male in tutti quei contesti in cui l'atomicità di un'operazione è critica, come ad esempio nel caso di un'applicazione multi-threaded.</p>
<p>Forse un esempio chiarirà le idee: supponiamo di avere un'applicazione che ha la necessità di autenticare gli utenti e che lo faccia tramite un meccanismo di crittazione basato su chiavi monouso. Ogni volta che un utente si vuole connettere il server crea una stringa di bit casuali che verranno usati come chiave crittografica temporanea per quella sessione. Supponiamo ora che l'applicazione in questione sia multi-threaded e che crei un nuovo thread ad ogni richiesta di connessione. Oltre al problema dell'esaurimento dell'entropia abbiamo ora anche un problema di accesso concorrente a <code>/dev/(u)random</code> in cui due thread potrebbero leggere la medesima porzione dello stream di dati casuali con conseguente calo drastico della sicurezza del sistema.</p>
<p>Il nostro programma di esempio si trova ora incastrato tra l'incudine e il martello: se utilizza dei meccanismi per impedire l'accesso concorrente a <code>/dev/(u)random</code> si troverà ad avere dei thread bloccati in attesa del loro turno, se non li utilizza rischia di avere due (o più connessioni) che condividono la stessa chiave crittografica. Quanto sia alto questo rischio dipende da numerosi fattori tra cui il più importante è il carico a cui è sottoposto il sistema: maggiore sarà il carico maggiore sarà la probabilità di collisioni.</p>
<p>Ed ora il motivo principe per cui usare <code>/dev/(u)random</code> non è una buona idea: pur essendo un file speciale si tratta sempre di un file. Per leggerlo, oltre alla necessità di avere un file descriptor disponibile, dovete anche avere i permessi per leggerlo e dovete essere in grado di trovarlo. Supponiamo che il vostro programma sia eseguito in una gabbia chroot e che quindi non abbia accesso alla directory <code>/dev</code> e quindi al suo contenuto. In questa situazione le chiamate a file esterni alla gabbia falliscono e quindi siete costretti a ricreare i file speciali all'interno della gabbia chroot e ad istruire il kernel a collegare il generatore di entropia a quei file (non è impossibile, ma è alquanto laborioso). Ma c'è un caso peggiore: supponete che il vostro sistema abbia ricevuto la visita di un malintenzionato che abbia eliminato <code>/dev/random</code> e <code>/dev/urandom</code> e li abbia sostituiti con un nuovo device che altro non è che <code>/dev/zero</code>. Inquietante, nevvero?</p>
<p>Certo, in quest'ultimo caso siete già stati compromessi e quindi non c'è molto che possiate fare, ma sappiate che esistono delle alternative e che (grazie alle pressioni fatte dal team che sta portando LibreSSL su Linux) è possibile chiedere direttamente al kernel di riempire un buffer di memoria con dati casuali grazie a getrandom(2) (<a href="https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=c6e9d6f38894798696f23c8084ca7edbf16ee895">https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=c6e9d6f38894798696f23c8084ca7edbf16ee895</a> ).</p>
<p>Con questo vi saluto e vi invito a leggere la presentazione di Theo DeRaadt tenuta all'EuroBSDcon 2014 (nonostante sia scritta in Comic Sans contiene numerosi spunti e informazioni utili):</p>
<p><a href="http://www.openbsd.org/papers/eurobsdcon2014_arc4random/index.html">http://www.openbsd.org/papers/eurobsdcon2014_arc4random/index.html</a></p>
</div>
Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-11678718589295258512014-11-12T08:00:00.000+01:002014-11-12T08:00:08.780+01:00Il problema dell'arrestoNo, non ha niente a che vedere con le forze dell'ordine, e nemmeno con brusche frenate. Il problema dell'arresto, traduzione di “Halting problem”, ha invece a che fare con l'informatica teorica e nella fattispecie, con la teoria della computabilità.<br />
La versione più famosa del problema fu ipotizzata e risolta da Alan Turing, nel 1936.<br />
Prima di spiegare per bene cosa sia l'halting problem, devo però introdurre al lettore qualche concetto essenziale.<br />
Innanzitutto, cosa si intende per <b>macchina di Turing</b> (mdT d'ora innanzi)? Essa è una macchina ideale in grado di eseguire algoritmi. Congetturata da Turing, essa prevede, tecnicamente, l'utilizzo di un nastro di ingresso da cui si legge, <i>k</i> nastri di memoria, tradizionalmente considerati di lunghezza infinita (è un modello astratto, appunto), e un nastro di uscita. La “testina” che scorre il nastro di input, così come le testine dei nastri di memoria, ha tre movimenti possibili: S(tand), L(eft), R(ight). Sul nastro di output, sono possibili invece solamente i movimenti S e R (L sovrascriverebbe un simbolo di output, il che sarebbe stupido e inutile).<br />
La mdT risulta importantissima poiché secondo la Tesi di Church essa è il modello astratto di riferimento di macchina con maggiore potenziale espressivo, ossia non è possibile pensare un algoritmo che non sia implementabile da una macchina di Turing.<br />
Detto in altra maniera, citando wikipedia:<br />
<blockquote class="tr_bq">
<i>L'importanza della MdT deriva dal fatto che permette di compiere tutte le elaborazioni effettuate mediante le macchine (elettroniche o meccaniche) apparse nella storia dell'umanità, incluse le elaborazioni che oggi si eseguono con le tecnologie più avanzate e gli odierni computer, e perfino le dimostrazioni matematiche che l'umanità ha raccolto nel corso della sua storia, diciamo a partire da Euclide.</i></blockquote>
Bene, adesso invece prepariamoci a affrontare un ulteriore concetto: cosa si intenda per <i>decidibilità</i> di un problema o <i>computabilità</i> di una funzione.<br />
Innanzitutto occorre notare che i problemi decidibili sono solo una minima parte dei problemi <i>definibili</i>, dove per definibile si intende un qualsiasi problema che possa essere formalizzato.<br />
In pratica, un problema è decidibile (e una funzione è computabile) se e solo se esiste una mdT che lo risolva. Spesso non ci interessa nemmeno sapere la soluzione o conoscere nel dettaglio il funzionamento di quella mdT, ci basta sapere che essa esiste. Ad esempio, il problema di stabilire se nell'universo ci siano 10^999 molecole, è un problema decidibile, anche se non ne conosciamo la risposta; infatti sappiamo che esiste una mdT che contando una a una le molecole, prima o poi ci dirà se avessimo ragione o meno.<br />
<div>
<br />
Siamo giunti al fulcro della discussione: il problema dell'arresto. Esso si domanda se, data una mdT (dato un algoritmo), e un input finito, sia sempre possibile determinare se la mdT termini oppure continui la sua esecuzione all'infinito (vada "in loop") con ingresso quel dato input.<br />
Il problema è indecidibile; e lo si dimostra ragionando per assurdo. La dimostrazione è davvero stuzzichevole, spero di riuscire a renderne evidente la genialità!<br />
Immaginiamo esista una mdT <b>H</b> tale che, ricevuto in ingresso l'algoritmo <i>a</i> e un input finito <i>x</i> su cui calcolarlo, ci ritorni TRUE se la macchina termina la computazione, o FALSE se invece va in loop.<br />
<div style="text-align: center;">
<b>H</b>(<i>a</i>, <i>x</i>): if (loop) then return false; else return true;</div>
Possiamo pensare di passare ad <b>H</b>, come input finito, <i>a</i> stesso! Già, poiché per la nostra mdT esso è solo una sequenza indistinta di simboli. Staremmo quindi calcolando <b>H</b>(<i>a</i>, <i>a</i>), chiedendoci se l'algoritmo <i>a</i> termini o meno con input <i>a</i>.<br />
Ora inventiamoci una ulteriore mdT <b>K</b> che vada in loop se e solo se <b>H</b>(<i>a</i>, <i>a</i>) restituisce TRUE, altrimenti ritorna FALSE.<br />
<div style="text-align: center;">
<b>K</b>(<i>a</i>): if <b style="text-align: start;">H</b><span style="text-align: start;">(</span><i style="text-align: start;">a</i><span style="text-align: start;">, </span><i style="text-align: start;">a</i><span style="text-align: start;">)</span> then loop; else return false;</div>
Proviamo infine a passare come input a <b>K</b>, <i>K</i> stesso, calcolando <b>K</b>(<i>K</i>). Dunque se <b>H</b>(<i>K</i>, <i>K</i>) termina, <b>K</b>(<i>K</i>) va in loop; altrimenti restituisce FALSE.<br />
<div style="text-align: center;">
<b>K</b>(<i>K</i>): if <b>H</b>(<i>K</i>, <i>K</i>) then loop; else return false;</div>
Ma <b style="text-align: center;">H</b><span style="text-align: center;">(</span><i style="text-align: center;">K</i><span style="text-align: center;">, </span><i style="text-align: center;">K</i><span style="text-align: center;">)</span> dovrebbe proprio dirci se <b>K</b>(<i>K</i>) termina o meno!<br />
Siamo giunti alla contraddizione: infatti questo algoritmo termina solo se l'algoritmo <i>K</i>, con input <i>K</i>, non termina. Ossia <b>K</b>(<i>K</i>) termina se e solo se <b>K</b>(<i>K</i>) non termina.<br />
<br />
Se qualche carissimo lettore avesse superato lo scoglio della dimostrazione sano e salvo, e si stesse chiedendo “e quindi?”, vorrei puntualizzare l'importanza di questa dimostrazione: immaginate se fosse vero il contrario, ossia se fosse possibile conoscere a priori se un determinato algoritmo termini o meno dato un input. Penso sia evidente lo straordinario potenziale che si creerebbe in una situazione simile: sapremmo con certezza se quel programmino che macina da 20 giorni si sia bloccato o se invece stia ancora computando. Potremmo risolvere congetture come quella di Goldbach, tuttora aperte.<br />
Insomma avremmo tra le mani uno strumento incommensurabilmente potente; ma, per fortuna o purtroppo, esso ci è negato. Insomma, accontentiamoci di cercare di capire se il nostro algoritmo sia andato in loop o meno leggendo attentamente il codice, invece di poterci affidare a una comoda mdT che risolva il problema dell'arresto!<br />
<div align="justify">
<!--EndFragment--></div>
</div>
Anonymoushttp://www.blogger.com/profile/03854199872890515528noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-4831338210941262122014-11-11T10:28:00.001+01:002014-11-11T10:28:54.194+01:00GNUrants Day 2015 - Call for Papers<div style="text-align: justify;">
<p>Un festoso saluto a tutti! Per festeggiare il primo compleanno del blog (che ricordo essere partito il primo di aprile di quest'anno) noi GNUrants abbiamo deciso di indire lo GNUrants Day!</p>
<p>Vi starete chiedendo di cosa si tratti, è presto detto: si tratta di un giorno dedicato a talk ed interventi sul mondo Linux sullo stile degli GNUrants.</p>
<p>Sì, lo sappiamo che la ILS (l'associazione che raccoglie i vari Linux Users Group d'Italia) tiene il Linux Day ogni anno nell'ultimo sabato di ottobre e di sicuro non abbiamo i soldi e le capacità per organizzare una simile manifestazione nazionale. Siamo molto più stretti di budget (0 € in totale) e non abbiamo una sede in cui invitare i nostri quattro lettori a sentirci sproloquiare. Ma questo non ci fermerà perché abbiamo un potente alleato dalla nostra parte: la For... ehm... Youtube!</p>
<p>Realizzeremo gli interventi sottoforma di filmati che caricheremo su Youtube assieme alla trascrizione di quello che diremo e pubblicheremo tutto sul blog il primo di aprile.</p>
<p>È la prima volta che ci diamo una scadenza (anche se abbiamo optato per una scadenza piuttosto lunga) e non fingiamo che la cosa sia una passeggiata (il video editing richiede tempo e ci teniamo che i nostri contenuti siano di un certo spessore) per cui non siamo sicuri di riuscire a produrre abbastanza materiale in tempo per il primo di aprile.</p>
<p>E qui entrate in gioco voi! Se avete un'idea per un talk e avete il tempo e la pazienza per realizzarla contattateci e vedremo di inserirvi nella "scaletta"!</p>
<p>Alcune precisazioni prima di continuare:<br/>
<ul>
<li><b>Dovrete rendere disponibile il trascritto del talk</b>. Potrete, a vostra totale discrezione, rendere disponibili anche le slides che avrete eventualmente prodotto.</li>
<li>I temi trattati dovranno essere in linea con quelli trattati dal blog: <b>Software Libero, Sicurezza Informatica, Informatica Teorica (Algoritmi, Linguaggi Formali, ecc. ecc.).</b> I rant politicizzati sono un'esclusiva di Federico Di Pierro e non saranno accettati.</li>
<li>Vi chiederemo il diritto <b>NON ESCLUSIVO</b> di pubblicazione del video e del trascritto e nient'altro: tutti i diritti resteranno a voi e sarete liberi di fare ciò che meglio credete dei vostri elaborati.</li>
</ul>
</p>
<p>Per ora è tutto, se avete altre domande consultateci la nostra pagina su Google+: <a href="https://plus.google.com/108084535358373749989?prsrc=5">GNUrants su G+</a>.</p>
</div>Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-40052610198398027252014-10-01T08:00:00.000+02:002014-10-01T20:14:23.954+02:00Di nuovo su systemd<div style="text-align: justify;">
Come forse saprete c'è un notevole grado di insofferenza nei confronti di <code>systemd</code> da parte di certi vecchi amministratori di sistemi UNIX con una folta barba. Parte di questa insofferenza è data dalla natura Linux-centrica (Linux inteso come solo kernel) di <code>systemd</code> e dalla quantità abnorme di feature che sono implementate in quello che, secondo la filosofia UNIX, dovrebbe essere un processo semplice e snello che assolve a due soli compiti: avviare/spegnere il sistema e raccogliere i processi orfani ponendo fine alle loro sofferenze.<br />
<br />
I fautori di <code>systemd</code> sostengono che ci sono degli indubbi vantaggi nell'approccio da loro scelto (li potete leggere tutti dal sito personale di Lennart Poettering: <a href="http://0pointer.de/blog/projects/systemd.html">http://0pointer.de/blog/projects/systemd.html</a> e <a href="http://0pointer.de/blog/projects/the-biggest-myths.html">http://0pointer.de/blog/projects/the-biggest-myths.html</a> ) e che le obiezioni arrivano da dinosauri incartapecoriti che non accettano il cambiamento.<br />
<br />
Essendo io uno dei suddetti dinosauri capirete che sono fortemente di parte e che non dovete prendere le mie parole per oro colato.<br />
<br />
Sì, lo so, ne avevamo già parlato e rischiamo di essere monotoni, ma sono successe due nuove cose che meritano di essere commentate.<br />
<br />
<ol style="list-style-type: decimal;">
<li><code>uselessd</code> ( <a href="http://uselessd.darknedgy.net/">http://uselessd.darknedgy.net</a>/ )</li>
<li>Il progetto sviluppato dallo studente Ian Kremlin per la Google Summer of Code.</li>
</ol>
<br />
Il primo è una versione ridotta del codice di <code>systemd-208-stable</code> (il default in Fedora 20) a cui hanno levato quasi tutto e a cui hanno migliorato la compatibilità con le librerie C diverse dalla GNU libc (sì, <code>systemd</code> compila solo se si usano le <code>glibc</code> perché si basa su alcune aggiunte/modifiche che non sono presenti nello standard o che sono specifiche dell'implementazione GNU).<br />
<br />
L'obiettivo a breve termine di <code>uselessd</code> è quello di dare all'utenza GNU/Linux una versione più snella di <code>systemd</code> che contenga solo l'essenziale per far funzionare un init system ma che conservi i due principali vantaggi della creatura di Lennart Poettering:<br />
<br />
<ol style="list-style-type: decimal;">
<li>L'avvio basato su dipendenze definite dall'amministratore (per cui il servizio B che dipende da A non sarà avviato finché A non sarà in grado di offrire i suoi servizi).</li>
<li>L'isolamento e la gestione dei gruppi di processi tramite i <code>cgroups</code> (o meccanismi equivalenti come le <code>jails</code> di FreeBSD).</li>
</ol>
<br />
L'obiettivo a lungo termine è portare <code>uselessd</code> su altri sistemi operativi (principalmente FreeBSD) così da porre fine alle due principali obiezioni che vengono rivolte a <code>systemd</code>: fare troppe cose e non essere portabile.<br />
<br />
L'autore ci tiene a precisare che la ragione per cui ha cominciato questo fork è stato per studiare il funzionamento di <code>systemd</code> e che <i>smontare</i> e <i>togliere</i> componenti gli è venuto naturale. In fin dei conti una delle pratiche del reverse-engineering consiste proprio nel vedere cosa smette di funzionare se si tolgono X e Y.<br />
<br />
Insomma un esercizio didattico pienamente contemplato dalla licenza LGPL 2.1 (usata da <code>systemd</code>) il cui scopo non è sostituire <code>systemd</code>, ma dimostrare qual è l'insieme minimo di feature che compongono un init system moderno.<br />
<br />
<code>uselessd</code> però diventa interessante se appaiato con il secondo punto della lista in apertura: il progetto di Ian Kremlin per la Google Summer of Code 2014.<br />
<br />
Tutto da nasce da alcune parole di Lennart Poettering:<br />
<br />
<blockquote>
<i>We also have pretty comprehensive documentation (all linked from the homepage) about pretty much every detail of systemd, and this not only covers admin/user-facing interfaces, but also developer APIs.</i><br />
<br /></blockquote>
Siccome una delle frasi tipiche degli sviluppatori di OpenBSD è "if you have a problem you can either shut up and hack a solution or pay someone to do that" hanno suggerito agli studenti della GSoC di leggersi la documentazione menzionata da Poettering e di creare dei rimpiazzi API-compatibili per <code>logind</code>, <code>hostnamed</code>, <code>localed</code> e <code>timedated</code> che non avessero altre dipendenze oltre a quello già installato di default nel sistema base di OpenBSD (leggasi: ben poca roba).<br />
<br />
Ian Kremlin ha raccolto questo suggerimento, compilato una proposta che è stata approvata e ha lavorato a spese di Google per scrivere questi rimpiazzi completandoli tutti ad eccezione di <code>logind</code> (che per sua natura è decisamente complesso e presenta numerose sfide di implementazione).<br />
<br />
L'obiettivo a breve termine è facilitare il port di GNOME 3 su OpenBSD (sì, ad alcuni dinosauri piace GNOME 3) scrivendo dei daemon che siano compatibili a livello di chiamate D-BUS coi corrispettivi in <code>systemd</code>.<br />
<br />
L'obiettivo a lungo termine è scrivere un'implementazione portabile su vari sistemi POSIX-compatibili così da fornire delle alternative a chi volesse fare uso delle funzionalità esposte ma non potesse o non volesse installare <code>systemd</code> sul proprio sistema.<br />
<br />
A differenza di <code>uselessd</code> il codice di questi daemon è stato scritto da zero basandosi sulla documentazione rilasciata dagli sviluppatori di <code>systemd</code>. Non hanno riscritto l'init system, hanno solo emulato alcune delle chiamate che <code>systemd</code> recepisce.<br />
<br />
La speranza di alcuni è che questi due progetti messi insieme possano offrire un'alternativa valida e funzionale a quanti criticano il modus operandi degli sviluppatori di <code>systemd</code> ma si trovano obbligati ad utilizzare in qualche modo i suoi servizi.<br />
<br />
Per quanto mi riguarda sono entrambi dei progetti che hanno una buona ragione di esistere: il primo perché dimostra quanto sia possibile fare anche con un init minimale e che apre le porte all'uso di <code>systemd</code> su sistemi che hanno pochissime risorse a disposizione (non ci sono solo desktop e server, ma anche numerosi apparecchi che non hanno abbastanza risorse per far girare <b>tutto quanto</b> ma che beneficerebbero dall'uso di certe parti di <code>systemd</code>). Il secondo progetto ha ancor più ragione di esistere perché offre un'implementazione alternativa che consentirebbe di testare l'effettiva compatibilità con le specifiche da parte di sviluppatori terzi.<br />
<br />
Detto questo io torno nel mio antro ad accarezzare la mia folta barba!<br />
<br /></div>
Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com2tag:blogger.com,1999:blog-1360931857234291524.post-10445921171625887712014-08-26T08:00:00.000+02:002014-12-19T13:53:41.597+01:00L'asteroide che ucciderà questo dinosauro deve ancora arrivare (terza parte)<div style="text-align: justify;">
L'articolo è diviso in tre parti:<br />
<a href="http://gnurants.blogspot.com/2014/07/lasteroide-che-uccidera-questo.html">Prima Parte</a><br />
<a href="http://gnurants.blogspot.it/2014/07/lasteroide-che-uccidera-questo_27.html">Seconda Parte</a><br />
<br />
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.<br />
<br />
<h1 id="grep">
grep</h1>
Abbiamo già nominato <code>grep</code> nella prima parte, se ve la foste persa (MALE) ecco la definizione presa pari-pari dal primo articolo di questa serie:<br />
<br />
<blockquote>
<code>grep</code> è uno dei dinosauri di UNIX che si rifiutano di estinguersi. Nasce come modalità di ricerca di <code>ex</code> (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.<br />
<br /></blockquote>
<code>grep</code> 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.<br />
<br />
Nella migliore tradizione UNIX <code>grep</code> accetta testo dallo <i>standard input</i>, manda del testo in output sullo <i>standard output</i> e i messaggi di errore sullo <i>standard error</i>.<br />
<br />
Facciamo subito un esempio concreto: vogliamo sapere qual è il MAC address di un'interfaccia di rete. Il comando <code>ifconfig</code>, sebbene deprecato, fa al caso nostro: se scriviamo <code>/sbin/ifconfig eth0</code> infatti otteniamo qualcosa di simile a questo:<br />
<br />
<pre><code>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 </code></pre>
<pre><code> </code></pre>
Ma a noi non interessa <b>TUTTO</b> quel testo, a noi basta il MAC address (che <code>ifconfig</code> chiama HWaddr): come facciamo ad ottenere <i>solo</i> quello?<br />
<br />
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 (<code>:</code>). Costruiamoci ora una regex che trovi questa particolare sequenza:<br />
<br />
<pre><code>([0-9a-f]{2}:){5}[0-9a-f]{2}</code></pre>
<pre><code> </code></pre>
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.<br />
<br />
Abbiamo la regex e abbiamo il nostro input, passiamo tutto attraverso <code>grep</code> e vediamo cosa succede:<br />
<br />
<pre><code>$ /sbin/ifconfig eth0 | grep ([0-9a-f]{2}:){5}[0-9a-f]{2}
bash: syntax error near unexpected token `[0-9a-f]{2}:'
$</code></pre>
<pre><code> </code></pre>
Giustamente bash ci notifica che non sa cosa sia <code>[0-9a-f]{2}:</code>, rimediamo con un po' di quoting:<br />
<br />
<pre><code>$ /sbin/ifconfig eth0 | grep '([0-9a-f]{2}:){5}[0-9a-f]{2}'
$</code></pre>
<pre><code> </code></pre>
Nessun output... Abbiamo sbagliato qualcosa nella regex? Ni: ci siamo dimenticati che <code>grep</code> di default non riconosce i quantificatori, ma a questo si rimedia usando <code>egrep</code> (oppure indicando a <code>grep</code> che vogliamo usare le extended regular expressions tramite il flag <code>-E</code>):<br />
<br />
<pre><code>$ /sbin/ifconfig eth0 | egrep '([0-9a-f]{2}:){5}[0-9a-f]{2}'
eth0 Link encap:Ethernet HWaddr ba:bb:e0:ba:bb:e0
$</code></pre>
<pre><code> </code></pre>
Meglio, ma non è abbastanza: abbiamo ancora troppo output. Questo perché di default <code>grep</code> ed <code>egrep</code> stampano <b>le righe</b> in cui c'è un riscontro positivo per la regex che gli passiamo. Fortunamente c'è un flag che ci consente di far stampare a <code>grep</code> solamente la parte di testo che corrisponde alla regex, si tratta del flag <code>-o</code>:<br />
<br />
<pre><code>$ /sbin/ifconfig eth0 | egrep -o '([0-9a-f]{2}:){5}[0-9a-f]{2}'
ba:bb:e0:ba:bb:e0
$</code></pre>
<pre><code> </code></pre>
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.<br />
<br />
Ci sono diversi usi possibili di questo one-liner:<br />
<br />
<ul>
<li>Comporre un elenco di MAC address da inserire nella configurazione del server DHCP per ottenere delle assegnazioni statiche di indirizzi IP.</li>
<li>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.</li>
<li>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.</li>
</ul>
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:<br />
<br />
<pre><code>#!/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</code></pre>
<pre><code> </code></pre>
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 <code>egrep</code> filtrando adeguatamente l'output di <code>ifconfig</code>: prima ricavando il nome delle singole interfacce e poi estraendo i MAC address.<br />
<br />
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).<br />
<br />
Alcuni scripter di lunga data mi faranno sicuramente notare che richiamare tutte quelle volte <code>ifconfig</code> è superfluo: come compito per casa potete modificare quello script affinché prenda l'output di <code>ifconfig</code> all'inizio, lo salvi in una variabile e poi lo passi ad <code>egrep</code> tramite <code>echo</code>.<br />
<br />
<h1 id="sed">
sed</h1>
<code>sed</code> è un altro dinosauro di UNIX: il suo nome è l'abbreviazione di <i>stream editor</i> ed è tutt'ora uno dei più potenti tool per il trattamento automatico dei file di testo nei sistemi operativi POSIX.<br />
<br />
In <code>sed</code> le espressioni regolari sono usate in due contesti:<br />
<br />
<ol style="list-style-type: decimal;">
<li>Per indicare un pattern che indichi la riga su cui agire.</li>
<li>Per indicare un pattern che indichi uno schema di sostituzione.</li>
</ol>
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...<br />
<br />
Come si fa ad automatizzare questo compito con <code>sed</code>? La cosa è piuttosto semplice quando si scopre che il comando per cancellare una linea è <code>d</code> e che le linee da cancellare possono essere indicate da una regex racchiusa tra due slash (<code>/</code>). Tutto si riduce al seguente one-liner:<br />
<br />
<pre><code>$ sed '/^[\ \t]*$/d' file_da_modificare > file_modificato</code></pre>
<pre><code> </code></pre>
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.<br />
<br />
La prima novità sono i delimitatori di inizio e fine riga (rispettivamente <code>^</code> e <code>$</code>). 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.<br />
<br />
La seconda novità è meno eclatante: il simbolo <code>\t</code> non indica il carattere <code>t</code> ma il TAB. Assieme a <code>\n</code> 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!<br />
<br />
Se siete tra coloro che utilizzano il <code>sed</code> del progetto GNU avete anche un'utile estensione che permette l'editing in-place: tramite il flag <code>-i</code> è 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:<br />
<br />
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.<br />
<br />
La vera forza di <code>sed</code> però sta nel suo comando dedicato alla sostituzione. A differenza del comando per cancellare il comando per sostituire ha la seguente struttura:<br />
<br />
<pre><code>/indirizzo/s/regex/sostituzione/flags</code></pre>
<pre><code> </code></pre>
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 (<code>,</code>). Per esempio <code>1,10</code> coinvolge le prime 10 righe del file mentre <code>10,/sed/</code> coinvolge le righe dalla 10 in poi ma solo quelle che sono comprese fino alla prima riga che contiene la stringa <code>sed</code> (occhio che la regex <b>NON</b> 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.<br />
<br />
La <code>s</code> indica il comando di sostituzione ed è seguita da una regex e da un pattern di sostituzione.<br />
<br />
I flags modificano il comportamento del comando, ad esempio <code>g</code> indica di effettuare la sostituzione su <b>TUTTI</b> 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).<br />
<br />
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:<br />
<br />
<pre><code>(0[1-9]|1[0-2]?|[2-9])/(0?[1-9]|[1-2][0-9]|3[0-1])/([0-9]{4})</code></pre>
<pre><code> </code></pre>
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.<br />
<br />
Adesso decidiamo l'indirizzo: se lasciamo l'indirizzo vuoto <code>sed</code> 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.<br />
<br />
L'ultima cosa da fare è decidere il flag: se vogliamo cambiare tutte le occorrenze che troviamo allora imposteremo il flag <code>g</code>, 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:<br />
<br />
<pre><code>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</code></pre>
<pre><code> </code></pre>
Questo comando legge il file indicato da <code>nomefile</code>, 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 <code>sed</code> che la regex <b>NON</b> finiva lì) e stampa in <i>standard output</i> un testo che contiene la stringa <code>pattern</code> ogni volta che c'è stata un'occorrenza della regex.<br />
<br />
Non male, ma adesso dobbiamo definire il nostro pattern di sostituzione. Ogni volta che <code>sed</code> 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.<br />
<br />
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:<br />
<br />
<pre><code>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</code></pre>
<pre><code> </code></pre>
Manca un ultima cosa: dobbiamo dire a <code>sed</code> che si tratta di un'espressione estesa (che fa uso dei quantificatori) tramite il flag di avvio <code>-r</code>:<br />
<br />
<pre><code>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</code></pre>
<pre><code> </code></pre>
<code>sed</code> può essere usato anche come se fosse <code>grep</code> tramite il flag <code>-n</code> che inibisce la copia dell'input non processato sullo <i>standard output</i> e il comando <code>p</code> che significa <i>print</i>, cioé <i>stampa</i>.<br />
<br />
Ad esempio se volessimo stampare solo le righe che non cominciano con un <code>#</code> scriveremmo:<br />
<br />
<pre><code>sed -n '/^[^#]/p' nomefile</code></pre>
<pre><code> </code></pre>
Ovviamente <code>grep</code> ed <code>egrep</code> hanno più opzioni e consentono un controllo più fine sull'output.<br />
<br />
<h1 id="conclusioni">
Conclusioni</h1>
<code>grep</code> e <code>sed</code> 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: <code>grep</code> effettua solamente la ricerca (ma è molto veloce e può essere usato per filtrare solamente le parti interessanti dell'input), <code>sed</code> 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 <code>sed</code> 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 <code>sed</code> inoltre ha memoria per una sola riga oltre a quella corrente e questo costringe a fare numerosi equilibrismi...<br />
<br />
L'alternativa c'è, è molto potente ed ha alle spalle anni di sviluppo: si tratta del linguaggio di scripting <code>perl</code>. Purtroppo il <code>perl</code> è 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: <code>Tcl</code> ce l'ha (ed è tra i più antichi), <code>Python</code> ce l'ha (tramite il modulo built-in <code>re</code>), <code>PHP</code> ce l'ha, <code>Ruby</code> ce l'ha, <code>Javascript</code> ce l'ha, Se ancora non foste convinti <code>Java</code> supporta le espressioni regolari tramite il package <code>java.util.regex</code>, per il <code>C</code> esistono le librerie <code>PCRE</code> che consentono di usare espressioni regolari compatibili con quelle del <code>perl</code> (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 (<code>man 3 regex</code> per maggiori info) infine per i fan del <code>C++</code> oltre alle <code>PCRE</code> potete usare <code>boost::regex</code> delle librerie Boost.<br />
<br />
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!<br />
<br />
<a href="http://gnurants.blogspot.com/2014/07/lasteroide-che-uccidera-questo.html">Prima Parte</a><br />
<a href="http://gnurants.blogspot.it/2014/07/lasteroide-che-uccidera-questo_27.html">Seconda Parte</a><br />
</div>Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com3tag:blogger.com,1999:blog-1360931857234291524.post-29166591793169248712014-07-18T14:05:00.000+02:002014-07-21T07:45:47.079+02:00Algoritmi di sorting, questi sconosciuti<br />
<br />
Bentornati sulle pagine di questo blog!<br />
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!<br />
Oggi...oggi...oggi, di cosa volevo parlare? ...Ah si, algoritmi. Algoritmi <b>di sorting</b>.<br />
Ok, parto dal presupposto che chi legga non sappia nulla, ma proprio nulla, nemmeno di algoritmi.<br />
<br />
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.<br />
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).<br />
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.<br />
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!<br />
Questo è solo un esempio marginale dell'importanza di tali algoritmi.<br />
<br />
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.<br />
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.<br />
<div>
<br />
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 <i>Selection Sort</i>.<br />
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.<br />
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). <br />
<br />
Il secondo algoritmo, anch'esso molto famoso, è il <i>Bubble Sort</i> (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:<br />
<u>3</u> <u>1</u> 2 → <u>1</u> <u>3</u> 2 → 1 <u>3</u> <u>2</u> → 1 <u>2</u> <u>3</u>. <br />
Sì, l'effetto “a bolla” lo vedrete solo dopo esservi fumati un cannone; cito wikipedia: <br />
<blockquote class="tr_bq">
<i>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.</i></blockquote>
Evidente no?<br />
Questo algoritmo è noto per essere il primo che si studia, nonché mediamente il più inefficiente battuto solo dallo <i>stupid sort</i>, 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?<br />
Il <i>Bubble Sort</i> differisce tra caso migliore e peggiore. Il caso medio asintoticamente è molto simile al peggiore. Prendiamo come caso migliore una sequenza già ordinata: il <i>Bubble Sort</i> non farà alcuno scambio, ma dovrà comunque fare circa n^2 confronti (come il precedente <i>Selection Sort</i>).<br />
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. <br />
<br />
<div>
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.<br />
Il <i>Quick Sort </i>si basa sul paradigma <u>divide et impera</u>, 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.<br />
Prendiamo ad esempio la sequenza<br />
<u>4</u> 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:<br />
3 1 <u>4</u> 7 5 → 4 confronti + 2 scambi. Ora spezziamo nelle due sotto sequenze e prendiamo dei nuovi pivot.<br />
<u>3</u> 1; <u>7</u> 5 , che diventano 1 3; 5 7 con altri 2 confronti e 2 scambi.<br />
Ora siamo già pronti a riordinare il tutto, dopo solo 6 confronti e 4 scambi!<br />
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.</div>
<div>
Inoltre è possibile migliorarne ancora l'efficienza scegliendo dei perni più adatti, calcolati attraverso procedimenti euristici.<br />
<br />
<br />
"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..." </div>
<div>
"Si fotta, prof!"</div>
<div>
"Lezione conclusa...sigh..."</div>
<div>
Siete ancora convinti sia così inutile e banale ordinare una serie di oggetti?<br />
Un ulteriore esempio di utilizzo di questi algoritmi, coniato dalla folle mente del Maestro Jedi <a class="g-profile" href="https://plus.google.com/117906490473157303154" target="_blank">+Gianfranco Gallizia</a>, 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.<br />
Caso peggiore nella ricerca lineare (la prima idea): ci tocca leggere tutto l'elenco.<br />
Caso peggiore nella ricerca binaria: ci tocca leggere un numero di elementi pari al logaritmo in base 2 della lunghezza dell'elenco.<br />
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.<br />
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.</div>
<div>
<span style="color: #404040; font-family: Roboto, arial, sans-serif; font-size: x-small;"><span style="line-height: 18.200000762939453px;"><br /></span></span>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.<br />
Che altro dire? Al prossimo noiosissimo articolo!<br />
E intanto, buone ferie a tutti!</div>
</div>
Anonymoushttp://www.blogger.com/profile/03854199872890515528noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-16259175388659715282014-06-12T09:26:00.000+02:002014-06-12T09:26:02.686+02:00A proposito di TrueCrypt su Windows<div style="text-align: justify;">
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.<br />
<br />
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.<br />
<br />
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 <a href="https://www.indiegogo.com/projects/the-truecrypt-audit/">finanziato un audit completo del codice di TrueCrypt</a>.<br />
<br />
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.<br />
<br />
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).<br />
<br />
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:<br />
<br />
<a href="https://opencryptoaudit.org/reports/iSec_Final_Open_Crypto_Audit_Project_TrueCrypt_Security_Assessment.pdf">https://opencryptoaudit.org/reports/iSec_Final_Open_Crypto_Audit_Project_TrueCrypt_Security_Assessment.pdf</a><br />
<br />
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.<br />
<br />
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.<br />
<br />
Fine del TL:DR, ora si fa sul serio.<br />
<br />
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).<br />
<br />
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.<br />
<br />
<h1 id="algoritmo-di-derivazione-della-chiave-per-il-volume-header-debole">
Algoritmo di derivazione della chiave per il Volume Header debole</h1>
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.<br />
<br />
TrueCrypt utilizza <a href="http://en.wikipedia.org/wiki/PBKDF2">PBKDF2</a> 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: <a href="http://www.golubev.com/about_cpu_and_gpu_2_en.htm">http://www.golubev.com/about_cpu_and_gpu_2_en.htm</a> ). 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.<br />
<br />
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.<br />
<br />
<h1 id="informazioni-sensibili-potrebbero-essere-salvate-nello-swap">
Informazioni sensibili potrebbero essere salvate nello swap</h1>
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
<h1 id="problemi-multipli-nello-scompattatore-del-bootloader">
Problemi multipli nello scompattatore del bootloader</h1>
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).<br />
<br />
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:<br />
<br />
<ul>
<li>Mescolanza di tipi signed e unsigned.</li>
<li>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).</li>
<li>Mancanza di controlli sui valori di ritorno per la presenza di codici di errore.</li>
</ul>
Questo genere di errori non ci dovrebbero essere in un software che si presume orientato alla sicurezza (e quindi al rigore del codice).<br />
<br />
<h1 id="uso-di-memset-per-la-pulizia-di-dati-sensibili">
Uso di memset() per la pulizia di dati sensibili</h1>
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.<br />
<br />
Supponiamo di avere un codice simile:<br />
<br />
<pre><code>char* roba_importante = calloc(sizeof(char), LUNGHEZZA_ROBA_IMPORTANTE);
/*Fai qualcosa con roba_importante*/
memset(roba_importante, 0, sizeof(roba_importante));
free(roba_importante);</code></pre>
<br />
La chiamata a memset ha lo scopo di pulire lo spazio di memoria di roba_importante prima di rilasciare la memoria con <code>free(roba_importante);</code>. Non vogliamo che altre porzioni del programma (o peggio <b>ALTRI</b> programmi) accedano a quelle informazioni e quindi le cancelliamo.<br />
<br />
Il problema è che i compilatori di adesso sono tarati per produrre codice che giri <b>velocemente</b> 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 <b>elimina</b> 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.<br />
<br />
La soluzione a questo problema consiste nel utilizzare altre funzioni scritte ad hoc per la pulizia della memoria (come <code>explicit_bzero()</code> di OpenBSD). Gli sviluppatori di TrueCrypt hanno scritto la funzione <code>burn()</code> 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).<br />
<br />
<h1 id="conclusioni">
Conclusioni</h1>
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++?).<br />
<br />
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.<br />
<br /></div>
Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-24004462689448544222014-05-22T13:37:00.002+02:002014-05-23T08:30:26.600+02:00Perché usiamo GNU/Linux?<div style="text-align: justify;">
Ciao a tutti!<br />
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?<br />
Bene, spero che in questo articolo troverete pane per i vostri denti.<br />
<br />
Sarò breve e circonciso (ogni allusione a str***ate dette in luoghi poco consoni è puramente casuale)<br />
<ol>
<li>Lo ammetto, mi avete beccato. Sono un fottuto comunista, che ci devo fare?<br />
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.<br />
Ehm, fin qua son stato fin troppo politico...cambierò tono, scusate!<br />
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.</li>
<li> 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.</li>
<li>L'architettura del filesystem di linux è, in maniera assoluta e certa, per progettazione, più sicura di quella ad esempio di Windows. </li>
<li> Hai un problema? Riscontri un bug?<br />
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!</li>
<li> Le battaglie filosofiche. :) Sono stupende...da ultima quella pro/contro systemd. Ma ce ne sono state tantissime!<br />
Ravvivano la giornata, divertono e insegnano a rispettare (alcune volte...) il punto di vista e le idee delle altre persone.</li>
<li> 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!).<br />
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 <b>devo</b> poterlo personalizzare.</li>
<li> Spesso si riesce a parlare direttamente con gli sviluppatori del software che stai utilizzando, dandogli suggerimenti, aiutandoli nel debug o direttamente nella programmazione.</li>
<li> Avere accesso a tutto il codice di qualsiasi software, per uno sviluppatore (anche se alle prime armi come me) è un sogno.</li>
<li> 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.</li>
<li>Gloria, gloria, gloria all'Ipnopinguino...</li>
</ol>
<div>
E per concludere...<br />
<blockquote class="tr_bq">
<i>Qualcuno usava Linux perché aveva avuto una educazione troppo </i><span style="font-style: italic;"><b>closed</b></span><i>. </i><br />
<i>Qualcuno usava Linux perché glielo avevano detto.</i><br />
<i> Qualcuno usava Linux perché </i><b><i>non</i></b><i> gli avevano detto tutto.</i><br />
<i> Qualcuno usava Linux perché prima… prima…prima… usava Windows.</i><br />
<i>Qualcuno usava Linux perché aveva capito che l' opensource andava piano, ma lontano.</i><br />
<i>Qualcuno usava Linux perché era così ateo che aveva bisogno di un altro S.O. .</i><br />
<i>Qualcuno usava Linux perché “driver video dignitosi?” “oggi no, domani forse, ma dopodomani sicuramente”.</i><br />
<i> Qualcuno usava Linux per fare rabbia a suo padre.</i><br />
<i> Qualcuno usava Linux per moda, qualcuno per principio, qualcuno per frustrazione.</i><br />
<i> Qualcuno usava Linux perché aveva scambiato K&R per il Vangelo secondo Stallman.</i><br />
<i>Qualcuno usava Linux perché non c'era niente di meglio.</i><br />
<i> Qualcuno usava Linux perché non sopportava più quella cosa sporca che ci ostiniamo a chiamare software proprietario.</i><br />
<i>Qualcuno credeva di usare Linux, e forse usava qualcos'altro.</i><br />
<i> Qualcuno usava Linux perché aveva bisogno di una spinta verso qualcosa di nuovo.</i></blockquote>
</div>
Niente, son proprio comunista. Non c'è nulla da fare...</div>
Anonymoushttp://www.blogger.com/profile/03854199872890515528noreply@blogger.com1tag:blogger.com,1999:blog-1360931857234291524.post-47273789402306529802014-05-01T08:23:00.000+02:002014-05-01T08:23:16.362+02:00Quel pasticcio di Heartbleed<div style="text-align: justify;">
<b>L’Antefatto</b>
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 <a href="https://tools.ietf.org/html/rfc6520">RFC 6520</a>.<br />
<br />
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.<br />
<br />
<b>7 aprile 2014</b><br />
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).<br />
<br />
<b>Dal 8 aprile in poi</b><br />
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.<br />
<br />
<b>Le conseguenze</b><br />
Il bug Heartbleed ha avuto un notevole impatto, specialmente emotivo, ma se cerchiamo materiale in merito in lingua italiana troviamo ben poco… Anche <a href="http://it.wikipedia.org/wiki/Heartbleed">la pagina di Wikipedia</a> in merito è decisamente scarna…
<br />
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).<br />
<br />
<b>Giochiamo con l’input</b><br />
Cominciamo col catalogare Heartbleed e col descrivere di che genere di vulnerabilità si tratta…<br />
Per prima cosa dobbiamo studiare un po’ la feature Heartbeat del protocollo TLS e capire cosa fa e in questo ci viene in aiuto <a href="http://xkcd.com/1354/">Randall di XKCD</a> (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.<br />
“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.<br />
“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:<br />
<ul>
<li>Traffico già criptato & spazzatura.</li>
<li>Traffico non ancora criptato (token di autenticazione, email, comunicazioni VoIP).</li>
</ul>
Nel primo caso non ci sono informazioni utili subito disponibili all’attaccante, ma il secondo caso è tutta un’altra storia!<br />
<br />
<b>Andiamo più in profondità</b><br />
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 <a href="http://ftp.openbsd.org/pub/OpenBSD/patches/5.4/common/007_openssl.patch">patch rilasciata dai maintainer del progetto OpenBSD</a> e la ragione è duplice:
<br />
<ol>
<li>E’ molto leggibile e ben documentata.</li>
<li>Va dritta al punto.</li>
</ol>
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 “-”.<br />
E adesso, finalmente, vediamo il codice C:<br />
<br />
<pre> /* Read type and payload length first */
hbtype = *p++;
n2s(p, payload);
pl = p;
</pre>
<br />
Ok, questa è una porzione di libreria che è stata tolta, il commento ci dà un indizio: “Read type and payload length first”.<br />
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.<br />
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. <b>Notate bene:</b> questa è la <b>lunghezza dichiarata</b>, non necessariamente la <b>lunghezza reale</b> 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.<br />
L'ultima riga serve a salvare un puntatore al messaggio vero e proprio in “pl”.<br />
<br />
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.<br />
<br />
Dopo una sezione di codice aggiunto (che ignoreremo) abbiamo le righe seguenti:<br />
<br />
<pre> 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);
</pre>
<br />
Allora, vediamo un po' cosa abbiamo qui… Questa riga qui è la radice del Male:<br />
<br />
<pre>buffer = OPENSSL_malloc(1 + 2 + payload + padding);</pre>
<br />
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.<br />
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.<br />
Una discussione completa sui meccanismi di protezione della memoria esula dallo scopo di questo articolo, ma invito il lettore a dare un'occhiata alle <a href="http://www.openbsd.org/papers/ru13-deraadt/mgp00001.html">slide che Theo DeRaadt ha proposto al ruBSD 2013</a> e, per i più curiosi, <a href="http://en.wikipedia.org/wiki/ASLR">all'articolo in merito ad ASLR su Wikipedia</a>.<br />
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.<br />
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.<br />
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 <b>TUTTE</b> le comunicazioni criptate.<br />
<br />
<b>Conclusioni</b><br />
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.<br />
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.<br />
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.<br />
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).<br />
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'è.
</div>Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com0tag:blogger.com,1999:blog-1360931857234291524.post-57667960001018332982014-04-22T23:12:00.000+02:002014-04-22T23:13:33.697+02:00A proposito di systemd<div style="text-align: justify;">
Qualche tempo fa nel covo segreto degli Illuminati... <br />
<br />
<b>Gianfranco Gallizia</b><br />
Non me n'ero accorto ma abbiamo una prima richiesta: un rant su systemd! <br />
Chi di voi giovini vuole scriverlo? Io sono poco pratico di queste cose moderne! XD <br />
<br />
<b>Diego Pi</b><br />
Iniziamo dal fondo: un server DHCP nell'init e log scritti in un formato binario non documentato che di fatto li rende closed. <br />
<br />
<b>Gianfranco Gallizia</b><br />
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. <br />
Un'altra mia obiezione a systemd è la convinzione dei suoi sviluppatori di essere nel giusto. Leggevo l'altro giorno di un <a href="https://lkml.org/lkml/2014/4/2/420" target="_blank">rant di Linus Torvalds</a> 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!<br />
Se non è un "WTF!" questo... <br />
<br />
<b>Federico Di Pierro</b><br />
Diego: ricordiamo che si può disabilitare tranquillissimamente, nessuno è forzato a usarlo. <br />
Gianfranco: su Torvalds, dell'altro giorno, ho letto un po' e ti do ragione, ma errare è umano. <br />
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... <br />
A volte sembra di utilizzare GNU/linux/systemd ormai. <br />
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)... <br />
Capite anche voi che rompe tante convenzioni, ma l'altra faccia della medaglia è che regala tante innovazioni! <br />
<br />
<b>Fanfurlio Farolfi</b><br />
Federico Di Pierro a me piace systemd, ho solo alcune cose da recriminargli... <br />
Il fatto dei log scritti in formato binario ad esempio, lo trovo fastidioso, ma non del tutto inutile. <br />
Se fosse documentato il formato, mi piacerebbe. <br />
<br />
<b>Gianfranco Gallizia</b><br />
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! <br />
<br />
<b>Diego Pi</b><br />
Federico systemd mi piace... Sono le idiosincrasie che si porta dietro a tirarmi fuori WTF. <br />
Peccato io veda poco sforzo per sistemare le poche scemenze che ha e tante energie spese a buttare dentro qualsiasi tipo di funzionalità. <br />
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. <br />
<br />
<b>Fanfurlio Farolfi</b><br />
Aggiungerei "inutile" a "funzionalità", a che serve un server DHCP all'interno del sistema di init? Non bastava far partire prima quello installato?<br />
<br />
<b>Federico Di Pierro</b><br />
Infatti lato kernel T. gli ha aperto il culo. <br />
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. <br />
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. <br />
<br />
<b>Gianfranco Gallizia</b><br />
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. <br />
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? <br />
Dunque: qual è il verdetto della giuria? <br />
<br />
<b>Federico Di Pierro</b><br />
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 <br />
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!”. <br />
<br />
Dissolvenza… Seguono rumori di una violenta collutazione... <br />
<br /></div>
Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com1tag:blogger.com,1999:blog-1360931857234291524.post-47328721567842589392014-04-04T17:05:00.001+02:002014-04-04T17:06:01.032+02:00Chi 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!).<br /><br />
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.<br /><br />
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? ;-)<br /><br />
P.S.: <b>FOTTETEVI STRONZI!</b>Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com1tag:blogger.com,1999:blog-1360931857234291524.post-23411376956212460832014-04-01T13:33:00.002+02:002014-04-01T13:33:50.347+02:00<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEglxg7LlyOQe7SODWCNGICWbga-j_dAviScQGMIQC2n0n0ciyis_yCp82FN8TyL5wCzqWSfVdmcvkLBNhPGHewU1urFgzgiY_FTi8DgzhzvqVswQSyr_tixICGzmiFQemi7ashkH3_cFbE/s1600/angry_gnu.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEglxg7LlyOQe7SODWCNGICWbga-j_dAviScQGMIQC2n0n0ciyis_yCp82FN8TyL5wCzqWSfVdmcvkLBNhPGHewU1urFgzgiY_FTi8DgzhzvqVswQSyr_tixICGzmiFQemi7ashkH3_cFbE/s1600/angry_gnu.png" height="320" width="240" /></a></div>
<br />
Gli GNUrants stanno arrivando.<br />
<br />
No, non è un pesce, è uno GNU.Anonymoushttp://www.blogger.com/profile/06730906533356698368noreply@blogger.com1