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

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.

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

Il problema dell'arresto

No, 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à.
La versione più famosa del problema fu ipotizzata e risolta da Alan Turing, nel 1936.
Prima di spiegare per bene cosa sia l'halting problem, devo però introdurre al lettore qualche concetto essenziale.
Innanzitutto, cosa si intende per macchina di Turing (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, k 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).
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.
Detto in altra maniera, citando wikipedia:

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.

Bene, adesso invece prepariamoci a affrontare un ulteriore concetto: cosa si intenda per decidibilità di un problema o computabilità di una funzione.
Innanzitutto occorre notare che i problemi decidibili sono solo una minima parte dei problemi definibili, dove per definibile si intende un qualsiasi problema che possa essere formalizzato.
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.

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.
Il problema è indecidibile; e lo si dimostra ragionando per assurdo. La dimostrazione è davvero stuzzichevole, spero di riuscire a renderne evidente la genialità!
Immaginiamo esista una mdT H tale che, ricevuto in ingresso l'algoritmo a e un input finito x su cui calcolarlo, ci ritorni TRUE se la macchina termina la computazione, o FALSE se invece va in loop.

H(a, x): if (loop) then return false; else return true;

Possiamo pensare di passare ad H, come input finito, a stesso! Già, poiché per la nostra mdT esso è solo una sequenza indistinta di simboli. Staremmo quindi calcolando H(a, a), chiedendoci se l'algoritmo a termini o meno con input a.
Ora inventiamoci una ulteriore mdT K che vada in loop se e solo se H(a, a) restituisce TRUE, altrimenti ritorna FALSE.

K(a): if H(a, a) then loop; else return false;

Proviamo infine a passare come input a K, K stesso, calcolando K(K). Dunque se H(K, K) termina, K(K) va in loop; altrimenti restituisce FALSE.

K(K): if H(K, K) then loop; else return false;

Ma H(K, K) dovrebbe proprio dirci se K(K) termina o meno!
Siamo giunti alla contraddizione: infatti questo algoritmo termina solo se l'algoritmo K, con input K, non termina. Ossia K(K) termina se e solo se K(K) non termina.

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

GNUrants Day 2015 - Call for Papers

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!

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.

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!

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.

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

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"!

Alcune precisazioni prima di continuare:

• Dovrete rendere disponibile il trascritto del talk. Potrete, a vostra totale discrezione, rendere disponibili anche le slides che avrete eventualmente prodotto.
• I temi trattati dovranno essere in linea con quelli trattati dal blog: Software Libero, Sicurezza Informatica, Informatica Teorica (Algoritmi, Linguaggi Formali, ecc. ecc.). I rant politicizzati sono un'esclusiva di Federico Di Pierro e non saranno accettati.
• Vi chiederemo il diritto NON ESCLUSIVO 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.

Per ora è tutto, se avete altre domande consultateci la nostra pagina su Google+: GNUrants su G+.

Di nuovo su systemd

Come forse saprete c'è un notevole grado di insofferenza nei confronti di systemd 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 systemd 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.

I fautori di systemd sostengono che ci sono degli indubbi vantaggi nell'approccio da loro scelto (li potete leggere tutti dal sito personale di Lennart Poettering: http://0pointer.de/blog/projects/systemd.html e http://0pointer.de/blog/projects/the-biggest-myths.html ) e che le obiezioni arrivano da dinosauri incartapecoriti che non accettano il cambiamento.

Essendo io uno dei suddetti dinosauri capirete che sono fortemente di parte e che non dovete prendere le mie parole per oro colato.

Sì, lo so, ne avevamo già parlato e rischiamo di essere monotoni, ma sono successe due nuove cose che meritano di essere commentate.

1. uselessd ( http://uselessd.darknedgy.net/ )
2. Il progetto sviluppato dallo studente Ian Kremlin per la Google Summer of Code.

Il primo è una versione ridotta del codice di systemd-208-stable (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ì, systemd compila solo se si usano le glibc perché si basa su alcune aggiunte/modifiche che non sono presenti nello standard o che sono specifiche dell'implementazione GNU).

L'obiettivo a breve termine di uselessd è quello di dare all'utenza GNU/Linux una versione più snella di systemd che contenga solo l'essenziale per far funzionare un init system ma che conservi i due principali vantaggi della creatura di Lennart Poettering:

1. 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).
2. L'isolamento e la gestione dei gruppi di processi tramite i cgroups (o meccanismi equivalenti come le jails di FreeBSD).

L'obiettivo a lungo termine è portare uselessd su altri sistemi operativi (principalmente FreeBSD) così da porre fine alle due principali obiezioni che vengono rivolte a systemd: fare troppe cose e non essere portabile.

L'autore ci tiene a precisare che la ragione per cui ha cominciato questo fork è stato per studiare il funzionamento di systemd e che smontare e togliere 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.

Insomma un esercizio didattico pienamente contemplato dalla licenza LGPL 2.1 (usata da systemd) il cui scopo non è sostituire systemd, ma dimostrare qual è l'insieme minimo di feature che compongono un init system moderno.

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

Tutto da nasce da alcune parole di Lennart Poettering:

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.

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 logind, hostnamed, localed e timedated che non avessero altre dipendenze oltre a quello già installato di default nel sistema base di OpenBSD (leggasi: ben poca roba).

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 logind (che per sua natura è decisamente complesso e presenta numerose sfide di implementazione).

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

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 systemd sul proprio sistema.

A differenza di uselessd il codice di questi daemon è stato scritto da zero basandosi sulla documentazione rilasciata dagli sviluppatori di systemd. Non hanno riscritto l'init system, hanno solo emulato alcune delle chiamate che systemd recepisce.

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 systemd ma si trovano obbligati ad utilizzare in qualche modo i suoi servizi.

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 systemd 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 tutto quanto ma che beneficerebbero dall'uso di certe parti di systemd). 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.

Detto questo io torno nel mio antro ad accarezzare la mia folta barba!

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

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

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

grep

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ci sono diversi usi possibili di questo one-liner:

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

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

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

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

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

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

sed

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

In sed le espressioni regolari sono usate in due contesti:

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

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

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

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

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

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

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

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

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

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

/indirizzo/s/regex/sostituzione/flags

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Conclusioni

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

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

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

Prima Parte
Seconda Parte