venerdì 14 marzo 2014

Come generare programmi automaticamente

Nell'ultima lezione di Reti ho accennato al Machine Learning come tecnica per costruire i filtri anti-spam. Il Machine Learning è un insieme di tecniche che permettono di fare una cosa fantastica:
  1. ho un problema che non ho la minima idea di come risolvere;
  2. ho tanti esempi risolti di quel problema, cioè tante coppie "dati del problema", "risultato desiderato".
Grazie a queste tecniche, si può generare automaticamente un algoritmo che risolve il problema.

Descritta in questi termini la faccenda è fantastica: come generare un algoritmo in grado di cucinare piatti buonissimi ? basta fornire un grande elenco di ricette di piatti buoni, un altro grande elenco di piatti pessimi, e voilà. Come generare un algoritmo in grado di sintetizzare canzoni di successo ? idem, un elenco di successi ed un elenco di canzoni schifose e siamo a posto. Ovviamente le cose non sono così semplici e queste tecniche, pur applicabili in moltissimi campi, non si possono applicare "sempre". In questi due casi non funzionano (almeno sinora), ma in molti altri casi funzionano benissimo ed hanno permesso di risolvere problemi che nessuno sapeva come risolvere, oppure di trovare soluzioni alternative e più efficienti di quelle usate di solito.

Nel nostro laboratorio ci occupiamo anche noi di queste cose e proprio ieri abbiamo ottenuto un risultato interessante, che sarà presentato ad una top conference nei prossimi mesi.

Su Internet nascono ogni tanto delle competizioni di programmazione ("code golf") in cui i programmatori competono per scrivere il programma più corto che risolve un dato problema. Nei mesi scorsi hanno iniziato a diffondersi delle competizioni simili in cui il programma da scrivere è una espressione regolare ("regex golf"). Una espressione regolare è un modo molto compatto per descrivere sequenze di caratteri---una sorta di linguaggio specializzato per la descrizione di pattern. Ad esempio "\b\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}\b" è un'espressione regolare che descrive gli indirizzi IP (con qualche approssimazione che non approfondisco). Le espressioni regolari sono usate in moltissimi contesti pratici e sono, come si intuisce, complicate da scrivere.

Le competizioni "regex golf" sono sfide di questo genere: dato un elenco di stringhe da riconoscere ed un elenco di stringhe da non riconoscere, generare la più corta espressione regolare che riconosce tutte le stringhe nel primo elenco e non riconosce nessuna nel secondo elenco. Un esempio di regex golf è riconoscere tutti i cognomi dei presidenti degli Stati Uniti e non riconoscere nessun cognome degli sfidanti sconfitti alle elezioni.

E' facile rendersi conto che problemi di questo genere sono, in linea di principio, adatti per le tecniche di Machine Learning. In linea di principio. Nessuno era ancora riuscito a farlo.

Noi siamo riusciti a generare un regex golf player competitivo con i player umani.

We considered a popular regex golf challenge proposed recently and compared the performance of our player to the best results produced by humans and to the only existing algorithm for playing automatically---an algorithm developed by Peter Norvig, Director of Google Research (!).

We rank in the top ten list worldwide, 6-th and 7-th place, beaten only by a few humans. (full post here)

E' interessante anche la particolare tecnica di Machine Learning che abbiamo usato: il Genetic Programming, una tecnica ispirata all'evoluzione biologica. Abbiamo creato una popolazione composta da centinaia di soluzioni generate (quasi) a caso. Abbiamo fatto evolvere questa popolazione, incrociando tra loro (a caso) alcune soluzioni e modificando (a caso) altre soluzioni. Nell'evoluzione abbiamo privilegiato la sopravvivenza delle soluzioni migliori. Abbiamo fatto proseguire l'evoluzione per centinaia di generazioni ed alla fine...voilà, tante soluzioni con ottime prestazioni !

Abbiamo sempre varie proposte per tesi e tirocini, triennali e magistrali, su tematiche di Machine Learning. So che gli studenti tendono a preferire lo sviluppo dei soliti programmi con le solite finestre con i soliti bottoncini colorati semplicemente installando, configurando ed usando una delle N tecnologie di moda del momento...ma ogni tanto c'è qualcuno che preferisce qualcosa di più challenging.

giovedì 6 marzo 2014

Configurazione DNS fraudolenta (le solite cose...)

In una delle prime lezioni del corso di Reti di quest'anno ho parlato di quanto sia critico il DNS per il funzionamento di Internet.

L'eventualità che l'infrastruttura DNS fornisca informazioni fraudolente non è "teorica ed improbabile". Eventi di questo genere si verificano molto spesso. Pochi giorni fa è uscita questa notizia:


in parole povere, un attacco informatico su larga scala ha modificato le informazioni di configurazione ricevute automaticamente alla connessione da casa (approfondiremo più avanti nel corso) facendo in modo che i client si colleghino non al server DNS del proprio provider ma ad un server DNS fraudolento. Gli effetti sono facilmente immaginabili.

A lezione avevo citato la possibilità degli amministratori disonesti, qui si tratta invece di attacchi che sfruttano errori software (argomento al quale accenneremo più avanti). La sostanza comunque è la stessa: la traduzione da nome ad indirizzo IP richiede la partecipazione di molti nodi; se uno di questi non è "onesto" allora quel nodo può forzare i propri client a collegarsi con server scelti da lui. Di nuovo, gli effetti sono facilmente immaginabili.

In questo blog ho fatto qualche altro post relativo ad "eventi spiacevoli" sul DNS; il post più vecchio, del 2010, è praticamente identico a questo a riprova del fatto che il problema è sempre il solito:

Altri eventi del genere si trovano su https://www.evernote.com/pub/bartolialberto/news scrivendo "tag:dns" nella search box.