venerdì 19 dicembre 2014

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

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

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.

Leggere le espressioni regolari

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,} !!?").

Anche sapendo che il punto ha un significato, il più un altro e l'asterisco un altro significato ancora è facile confondersi e sbagliare.

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 cosa effettivamente facciano quegli scampoli di lettere e caratteri apparentemente causali.

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").

Siccome scriverò parecchie regex e siccome le scriverò in mezzo al testo dell'articolo userò la seguente convenzione: le regex saranno scritte in monospace e racchiuse tra singoli slash (/). Gli slash NON 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).

La prima regola è: comportarsi come la macchina.

Le espressioni regolari si leggono un carattere alla volta da sinistra a destra. Non provate a saltare dei pezzi o a fare assunzioni, perché la macchina NON lo fa.

La seconda regola è: puntare sempre a riconoscere il più possibile.

Facciamo un esempio con questo testo di input:

Vuolsi così colà dove si puote ciò che si vuole e più non dimandare.
L'espressione regolare /co.*/ applicata al testo precedente ritornerà come stringa trovata la seguente porzione:

così colà dove si puote ciò che si vuole e più non dimandare.
Siccome il . significa "un carattere qualsiasi" e la stella (*) significa "zero o più" quell'espressione si legge come "co seguito da zero o più caratteri qualsiasi". Non essendoci un limite superiore il match prende il primo co, quello di così, e copia in uscita tutto quello che trova fino a raggiungere la fine del testo.

Se invece avessimo usato l'espressione /co../? Avremmo avuto qualcosa del tipo "co seguito da un carattere qualsiasi seguito a sua volta da un altro carattere qualsiasi. Il risultato sarebbe stato solamente così.

Il che mi permette di introdurre la terza regola: salvo indicazione contraria fermati al primo risultato corretto che trovi.

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.

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 ., * e +.

Armati di queste nuove conoscenze vediamo di capire cosa riconosce la seguente espressione:

/[0-9]*\.[0-9]+([eE][-+]?[0-9]+)?/

Piuttosto complessa, vero? Ma adesso sappiamo come procedere a leggerla (si spera).

Il primo carattere è una parentesi quadra aperta e quindi quello che segue è la definizione di una classe di caratteri, segue uno 0 che ci dice che la classe contiene quel carattere. Il - ci dice che stiamo componendo un range di caratteri e il 9 è il carattere di chiusura del range. La parentesi quadra chiusa termina la definizione della classe.

Riepilogando: crea una classe composta da tutti i caratteri da 0 a 9. Segue un * 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.

Il carattere successivo è un backslash (\) 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.

Segue una replica della classe che abbiamo definito all'inizio seguita a sua volta da un +. Questo si legge come "una o più cifre decimali".

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 e ed una E. La classe ci dice che il gruppo comincia con una lettera "e" minuscola oppure maiuscola. La classe che la segue ci mostra che il - inserito all'inizio di una classe non viene considerato come un separatore di range ma come un carattere letterale. L'espressione /[-+]/ 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".

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.

Il punto di domanda è un quantificatore che si riferisce al gruppo e quindi il gruppo che abbiamo appena definito può essere presente in toto una volta oppure non esserci affatto.

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.

Scrivere un'espressione regolare

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).

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:

/[0-9]*\.[0-9]+([eE][-+]?[0-9]+)?/

Questa espressione ha due difetti:

  • Non riconosce i numeri decimali negativi nè quelli positivi preceduti da un più (+).
  • Non riconosce i numeri decimali come 1. oppure 47.
Se volessimo riconoscere tutti i numeri decimali in virgola mobile quell'espressione mancherebbe diversi bersagli.

La prima cosa che faremo sarà aggiungere il segno. Sappiamo che il segno può essere un - oppure un + 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.

Dalla nostra analisi dell'espressione abbiamo già trovato l'espressione che riconosce il segno: /[-+]?/. Ci limiteremo ad inserirla nel posto giusto:

/[-+]?[0-9]*\.[0-9]+([eE][-+]?[0-9]+)?/

Risolto il nostro primo problema dobbiamo cercare una maniera per risolvere il secondo problema.

La prima cosa che si deve fare quando si crea una regex è cercare un schema generale che si ripeta. 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.

Quindi il punto dev'esserci e deve stare alla fine, ma davanti cosa ci va? Una o più cifre decimali eventualmente precedute dal segno.

Sappiamo che il simbolo + indica che quello che lo precede dev'essere presente "una o più volte" e che il simbolo ? significa che ciò che lo precede dev'essere presente zero oppure una volta ma non di più.

Quindi l'espressione per cercare i numeri decimali in virgola mobile composti da un numero seguito da un punto è la seguente:

/[-+]?[0-9]+\./

Abbiamo usato due classi, due quantificatori e un simbolo letterale per trovare tutti e soli i numeri simili a 47.. L'inizio di questa espressione somiglia moltissimo all'inizio dell'espressione precedente e potremmo essere tentati di sostituire la stella (* che significa "zero o più senza limite superiore") con il più (che significa "uno o più senza limite superiore"). Ricaveremmo la seguente espressione:

/[-+]?[0-9]+\.[0-9]+([eE][-+]?[0-9]+)?/

Facendo così però abbiamo imposto che ci siano delle cifre prima e dopo il punto, restringendo la gamma di numeri che riconosciamo anzichè ampliarla.

Se invece sostituissimo i due + dell'espressione appena trovata con due stelle? Otterremmo questa:

/[-+]?[0-9]*\.[0-9]*([eE][-+]?[0-9]+)?/

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:

  • .
  • -.e0
  • .E-0
E noi non le vogliamo perché quelle stringhe non sono numeri validi!

Che si fa? O siamo troppo rigorosi oppure 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 (|) che i fan di UNIX chiamano "pipe" perché ha un significato ben preciso nella shell UNIX.

Il segno opzionale all'inizio ci va bene e lo lasceremo dov'è, creeremo invece un gruppo che conterrà al suo interno un | per spezzare in due le possibilità di riconoscimento. Nella prima parte metteremo l'espressione per i numeri come 47. e nella seconda metteremo l'espressione originale che abbiamo visto nella sezione precedente.

Quindi abbiamo il segno:

/[-+]?/

Poi apriamo un gruppo e ci mettiamo i numeri con prima le cifre e poi il punto e basta seguiti da un "oppure":

/[-+]?([0-9]+\.|/

E infine rimettiamo l'espressione originaria e chiudiamo il gruppo:

/[-+]?([0-9]+\.|[0-9]*\.[0-9]+([eE][-+]?[0-9]+)?)/

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.

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.

La prossima volta ci occuperemo di alcuni programmi della shell UNIX che fanno largo uso delle regex.

Aloha!

Prima Parte
Terza Parte

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

Disclaimer: 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.
L'articolo è diviso in tre parti:
Seconda Parte
Terza Parte

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).

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.

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.

Automi e Dinosauri

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.

Ora che i vostri occhi hanno smesso di roteare cominciamo con la teoria pesante! :-D

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:

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 a.

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.

Scrivere un programma che legga dallo standard input e stampi "OK" se c'è una sequenza di 3 o più a è 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 È il grafico, si tratta solo di riportarlo in una sequenza di istruzioni comprensibili dalla macchina.

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: grep.

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

Espressioni Regolari

Prima di elencarvi i numerosi pregi di grep, però, devo illustrare le espressioni regolari e la loro (torbida) relazione con gli automi deterministici.

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 (/), il trattino (-) 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).

Anche in questo caso partirò da un grafico:

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.

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.

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?

La risposta a questa domanda è: "Sì, c'è un metodo: le espressioni regolari".

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.

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).

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 aaa corrisponde al primo automa che abbiamo visto in questo articolo.

Il punto (.) indica un carattere qualsiasi (lettera o numero o simbolo di punteggiatura). Per indicare il punto come un carattere a sè occorre aggiungere un backslash (\) davanti al punto. Il \ infatti indica che il carattere che segue deve essere essere considerato diversamente dal solito. La sequenza \t corrisponde al TAB, mentre \n indica l'andare a capo. La sequenza \\ viene sostituita con un singolo backslash.

Se avessimo voluto indicare una sequenza di sole tre a (non tre o più) avremmo dovuto fare uso di un quantificatore: a{3}. 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).

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 a compreso tra due e quattro scriveremmo a{2,4}. Se il secondo numero è omesso viene considerato pari ad infinito, se viene omesso il primo allora viene considerato pari ad uno.

Esistono anche altri quantificatori:

  • + indica una o più occorrenze del gruppo che precede. Equivale a {,}.
  • * indica zero o più occorrenze del gruppo che precede. Equivale a {0,}.
  • ? indica zero od una occorrenza del gruppo che precede. Equivale a {0,1}.
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: (a){3} equivale ad a{3}.

I gruppi separano un'espressione complessa in diverse sottoespressioni che possono essere trattate singolarmente.

Rimane un'ultimo argomento da trattare prima di provare a convertire l'automa delle date in una espressione regolare: le classi.

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: [0123456789] 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 -. La classe di prima perciò diventa: [0-9].

È 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: [A-Za-z0-9].

All'interno di un gruppo o di una classe è possibile che sia presente il carattere | 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 [a|b|c].

Adesso armiamoci di pazienza e cominciamo a tradurre l'automa in una regex (da REGular EXpression: espressione regolare).

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: (0[1-9]|1[0-2]?|[2-9]). 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.

La transizione tra MESE e START_GIORNO è banale: [-\/\ ]. Il - è stato messo per primo così da non essere confuso con l'indicatore di range di caratteri, seguono lo slash (/) e lo spazio preceduti dal backslash per indicare che vanno interpretati letteralmente.

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: [0-9]{4}.

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!

Seconda Parte
Terza Parte

giovedì 18 dicembre 2014

Come avviare il proprio OS linux direttamente dal firmware efi

Dopo aver sperimentato in prima persona questa follia, sono pronto a insegnarvi la sacra arte dello sminchiare il pc, ma con classe
Innanzitutto cosa è necessario: avremo bisogno di un kernel linux > 3.3 e le seguenti opzioni attive nella sua config: Kernel options needed (in archlinux esse sono attive di default, come penso in tutte le distro più recenti)
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.
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.
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: Advantages of GPT.
Vediamo quindi subito che tipo di partizionamento stiamo usando. Installate il tool gdisk e lanciate da root
gdisk /dev/sdX
(dove X è la lettera del disco che ci interessa).
Un risultato del genere ci dirà che siamo su MBR:
MBR: MBR only
GPT: not present
Altrimenti, per GPT, riceveremmo
MBR: protective
GPT: present
Nel caso fossimo su MBR, ora ci appresteremo a convertire a GPT il nostro disco. Nessuna perdita di dati ovviamente. 
DISCLAIMER: non ritenetemi colpevole di qualsivoglia perdita di dati. Fate comunque un backup se non vi fidate (NON FIDATEVI!)
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.
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.
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.
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 boot (attenzione, non legacy_boot). Io ho ridimensionato la mia root per crearla.
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:
/dev/sdXY /boot vfat defaults,noatime 0 1
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).
Bene; dopo aver smontato la root e la partizione EFI, possiamo riavviare.

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: Boot archlinux live media with secure boot enabled ).
Attiviamo ovviamente la modalità UEFI dal bios, e procediamo al boot della live di arch.
Ci manca solo da dare un comando:
efibootmgr -d /dev/sdX -p Y -c -L "Arch Linux" -l /vmlinuz-linux \
-u "root=/dev/sdXZ rw initrd=/initramfs-linux.img"
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.
Ora diamo un:
efibootmgr -v 
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 ;)

Ps: ringrazio il fantastico wiki di archlinux che è colmo di informazioni e su cui si appoggia la guida.

lunedì 1 dicembre 2014

Sui vizi e le virtù di /dev/random

Eccomi qui a scrivere un articolo su una delle componenti fondamentali del kernel Linux (e non solo): /dev/random.

Come si può ricavare dal suo path /dev/random è un character device che, una volta letto, emette una sequenza pseudocasuale di byte.

Se volete riempire completamente il vostro terminale di caratteri casuali vi basta invocare il seguente comando:

cat /dev/random

Ovviamente vi consiglio CALDAMENTE di NON FARLO, ma si sa: il Mondo è pieno di masochisti e magari a qualcuno di voi potrebbe piacere!

Tralasciando gli scherzacci per cosa può essere utile un simile device?

  1. Creazione di password pseudocasuali mediante shell-fu:

    dd if=/dev/random bs=1 count=6 2> /dev/null | base64 | \
    sed -r 's/[^A-Z|a-z|0-9]//g'
  2. Simulatore di tiri di dado per Giochi di Ruolo (se siete veri nerd sapete di cosa sto parlando).

  3. Cancellazione sicura di un disco: prima di formattarlo potete sovrascrivere i suoi dati con un l'output di /dev/random per un certo numero di volte.

Queste sono solo alcune delle idee che potrebbero essere implementate grazie a letture da /dev/random, una di queste idee però si scontrerà subito con il principale limite del generatore di numeri pseudocasuali. Sapete per caso dirmi quale?

Chi ha risposto "la terza!" vince un simpatico sguardo condiscendente! Chi invece non sapeva la risposta potrà leggere la spiegazione nel prossimo paragrafo.

La procedura per interrogare /dev/random si compone dei seguenti passi: si apre un file descriptor e lo si associa al device, si richiedono i dati tramite una chiamata read (http://linux.die.net/man/2/read ), si ASPETTA che read popoli il buffer con i dati richiesti, si chiude il file descriptor.

No, Virginia, non ho evidenziato in corsivo la voce del verbo aspettare per puro vezzo personale. /dev/random non è sempre disponibile ad inviare dati pseudocasuali perché ha bisogno che ci sia una sufficiente entropia per generare dei buoni 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.

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 molto poi) a replicare la sequenza di numeri che ha generato dall'inizio. Questa caratteristica si chiama periodo 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 prima che essi vengano generati. Un buon PRNG deve fare in modo che la sequenza che permetta una simile previsione sia la più lunga possibile.

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.

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 /dev/random. Non è chiaro, allora lasciami spiegare un altro po'.

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.

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 entropia.

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.

Per questa ragione /dev/random blocca qualsiasi richiesta finché non ha abbastanza entropia per soddisfarla, bloccando quindi qualsiasi software che fa uso dei suoi servizi.

Come palliativo gli sviluppatori di Linux hanno creato /dev/urandom: una versione non-bloccante di /dev/random che ricicla i numeri generati in caso di esaurimento dell'entropia del sistema. Eliminando così tutti i benefici derivanti dal re-seeding.

Ora starete pensando che un utente accorto può effettivamente fare un buon uso di /dev/random limitando le chiamate e creando un proprio PRNG all'interno dei suoi programmi... Sorvolando sull'intera questione del "perché usare /dev/random 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.

In sostanza: se non siete dei guru, non fatelo.

C'è un'altra circostanza in cui l'uso di /dev/(u)random è 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.

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 /dev/(u)random in cui due thread potrebbero leggere la medesima porzione dello stream di dati casuali con conseguente calo drastico della sicurezza del sistema.

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 /dev/(u)random 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.

Ed ora il motivo principe per cui usare /dev/(u)random 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 /dev 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 /dev/random e /dev/urandom e li abbia sostituiti con un nuovo device che altro non è che /dev/zero. Inquietante, nevvero?

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) (https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=c6e9d6f38894798696f23c8084ca7edbf16ee895 ).

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):

http://www.openbsd.org/papers/eurobsdcon2014_arc4random/index.html