Back to GeneticAlgos
========================================================
This work is licensed under a Creative Commons License
See http://creativecommons.org/licenses/by-nc-nd/2.0/
========================================================
Cracking codes with Genetic Algorithms
by +mala
200412
1. Introduzione
1.1 Note
2. GA Basics
2.1 Cos'e' un GA?
2.2 Come funziona un GA?
3. GA Techniques
3.1 Scelta del problema
3.2 Modello e cromosomi
3.3 Fitness
3.4 Riproduzione e Mutazione
3.5 Algoritmi genetici e probabilita'
4. Programmazione
4.1 GAlib
4.2 Generica struttura di un GA in C++
5. Esempi
5.1 NSCE
5.2 Cifrature monoalfabetiche
6. Bibliografia
=============================================================================
1. Introduzione
-----------------------------------------------------------------------------
Era il febbraio del 2003 quando, sul forum di anticrack, lessi il thread (che
trovate ancora su http://board.anticrack.de/viewtopic.php?t=1108) intitolato
"Genetic Algorithms". The+Q scriveva
<<This made me think, is there a limit to GA? More and more "un-solvable"
problems are solved by GA, and im starting to feel its only a matter of
time until hard crypto algorithms are cracked by such meens..>>
The+Q non era il solo a nutrire un cosi' forte entusiasmo per gli algoritmi
genetici: nel forum diversi reverser cominciarono a chiedere informazioni su
come sviluppare programmi che ne facessero uso e io stesso cominciai subito
a studiarli e a fare diversi esperimenti. Tutti quanti pensavamo che con i
GA si sarebbe potuto cambiare radicalmente l'approccio al reversing e alla
crittanalisi.
A distanza di un paio d'anni non e' cambiato molto. Anzi, i vecchi thread
sugli algoritmi genetici sono andati inaridendosi e di materiale nuovo sui
GA e' uscito veramente poco: basti pensare che, ancora adesso, come esempio
di algoritmo genetico applicato al cracking viene citato il tutorial che
The+Q aveva scritto nel 2003.
Perche' e' successo questo? Come mai la gente ha smesso di parlare di quanto
fossero potenti gli algoritmi genetici subito dopo aver provato a usarli? Non
e' sufficiente comprenderne la teoria per poter risolvere ogni problema? Io
stesso, durante i miei esperimenti, mi son trovato piu' volte incapace di
trovare una soluzione a problemi che non mi sembravano poi neanche cosi'
complessi, e ogni volta mi chiedevo dove fosse il limite di questa tecnica.
Tuttora mi sento ben lontano dall'aver imparato tutto cio' che gli algoritmi
genetici ci chiedono di comprendere prima di poterli usare in modo veramente
efficace, ma perlomeno ho superato lo stadio del "non so come funzionano,
pero' solitamente funzionano, quindi devono funzionare". Questo testo serve
a me per fare un punto della situazione, e a chi avra' la pazienza di
seguirmi per cominciare a lavorare coi GA sapendo gia' (piu' o meno) cosa
aspettarsi.
1.1 Note
-----------------------------------------------------------------------------
Immagino vi starete chiedendo perche' questo testo abbia un titolo cosi'
particolare e se vi sara' veramente utile, anche se non siete dei reverse
engineer o dei crittanalisti.
Beh, la risposta alla prima domanda e' abbastanza semplice: dato il mio
duplice interesse sia per il reversing sia per la crittografia, mi e' parso
interessante condurre esperimenti in entrambi i campi, accomunandoli sotto
il nome di "code cracking". In realta', gli esempi su cui ho lavorato sono
i piu' vari: non tutti riguardano code cracking, ne' tutti hanno avuto esito
positivo. Tuttavia, da ognuno di essi ho imparato qualcosa che cerchero' di
trasmettere proprio attraverso queste pagine.
Per quanto riguarda l'utilita' del testo che state leggendo, credo ci sia una
sufficiente quantita' di suggerimenti e idee di base per permettere a
chiunque di provare a scrivere un algoritmo genetico, qualsiasi sia il
problema che desidera risolvere. Naturalmente, una maggiore preparazione
sull'argomento specifico a cui vi dedicherete vi semplifichera' notevolmente
il lavoro.
Infine, se alla fine della lettura di questo testo siete ancora vivi e vi
interessano ancora gli algoritmi genetici, provate a dare un'occhiata su
http://mala.homeip.net/malawiki/GeneticAlgos per aggiornamenti, sorgenti,
commenti sul testo, suggerimenti e maledizioni vudu'.
=============================================================================
2. GA Basics
-----------------------------------------------------------------------------
All'interno di questa sezione parlero' di algoritmi genetici nel modo piu'
semplice e generale possibile, introducendo alcune definizioni che verranno
poi usate in tutto il testo. Se gia' conoscete i GA potete saltare tutta
questa parte, ma vi consiglio comunque di darci un'occhiata, se non altro
per verificare che la vostra terminologia sia esattamente uguale alla mia.
2.1 Cos'e' un GA?
-----------------------------------------------------------------------------
Un GA e' un Genetic Algorithtm, cioe' un algoritmo genetico (se vi chiedete
perche' li chiami GA e non AG, fate una ricerca su google e vedete cosa vi
restituisce piu' risultati).
Andando a consultare un po' di letteratura a proposito, scopriamo che quella
degli algoritmi genetici e' una famiglia di modelli computazionali che si
ispirano all'evoluzione. Essi mettono in pratica il concetto Darwiniano della
"sopravvivenza del piu' forte", partendo da una popolazione di soluzioni
possibili (solitamente casuali) a un dato problema e lasciandole evolvere in
base ad alcune misure del loro successo.
Gli studiosi ancora discutono cercando di trovare una definizione precisa di
Algoritmo Genetico. Nel frattempo, lo stesso termine viene utilizzato con due
accezioni diverse: secondo un'interpretazione letterale, esso si riferisce a
un modello introdotto e studiato da John Holland (1975) e dai suoi studenti;
con un significato un po' piu' ampio, un algoritmo genetico e' un "modello
basato su una popolazione che utilizza degli operatori di selezione e
ricombinazione per generare nuovi punti in uno spazio di ricerca".
Visto che queste definizioni sono tanto rigorose quanto poco chiare, ecco
alcuni esempi che vi faranno meglio comprendere il significato di quanto e'
stato scritto.
Un caso semplice (se non addirittura banale, ma e' uno dei principali che la
letteratura ci offre) potrebbe essere quello in cui il PROBLEMA consiste nel
riempire una riga di numeri 1. La POPOLAZIONE, cioe' il gruppo di possibili
soluzioni, potrebbe essere allora rappresentata da una serie di stringhe di
bit inizialmente casuali, lunghe tanto quanto si desidera sia lunga la riga.
La MISURA DEL SUCCESSO di un generico elemento della popolazione, che d'ora
in poi chiameremo CROMOSOMA, sara' ad esempio il numero di bit all'interno
della stringa che hanno come valore 1. Potete facilmente intuire che i
cromosomi migliori saranno quelli piu' vicini alla soluzione, e proprio
questi avranno maggiore probabilita' di "sopravvivenza".
In un gioco da tavolo come, ad esempio, Lights Out o la dama cinese (che
potete trovare, rispettivamente, su http://www.2flashgames.com/f/f-35.htm e
http://www.math.it/damacinese/dama.htm), il PROBLEMA consiste nel finire il
gioco con una particolare configurazione: per Lights Out si tratta di
spegnere tutte le luci, mentre per la dama cinese bisogna finire con una sola
pedina al centro del piano di gioco. La POPOLAZIONE, in entrambi i casi,
potrebbe essere costituita da CROMOSOMI che rappresentano sequenze di mosse,
e la MISURA DEL SUCCESSO potrebbe essere la vicinanza alle configurazioni che
risolvono il problema, cioe' quanto ci si e' riusciti ad avvicinare alla
configurazione con zero luci accese o con una sola pedina al centro.
In un altro esempio (che descriveremo in dettaglio piu' avanti) il PROBLEMA
consiste nel trovare una password per registrare un programma, la POPOLAZIONE
e' costituita da CROMOSOMI che rappresentano le password _potenzialmente_
valide (cioe' soddisfacenti alcune condizioni necessarie) e la MISURA DEL
SUCCESSO e' data dalla vicinanza della password a quella giusta, calcolata
in base allo stesso algoritmo utilizzato all'interno del programma.
Un ultimo esempio e' quello della cifratura monoalfabetica (in cui ad ogni
lettera di un testo ne corrisponde sempre e solo un'altra: per intenderci,
la stessa usata nella Settimana Enigmistica). In questo caso, il PROBLEMA
consiste nel trovare una sostituzione di lettere che risolve il crittogramma,
la POPOLAZIONE e' costituita da CROMOSOMI che corrispondono ai vari alfabeti
cifranti e la MISURA DEL SUCCESSO e' data da quanto un alfabeto e' buono,
cioe' da quanto il risultato della decifrazione con tale alfabeto e' un
testo valido.
2.2 Come funziona un GA?
-----------------------------------------------------------------------------
Dalla pagina di Wikipedia (http://it.wikipedia.org/wiki/Algoritmo):
"Nella sua definizione più semplice ed intuitiva un algoritmo è una sequenza
ordinata di passi semplici che hanno lo scopo di portare a termine un
compito più complesso (una ricetta da cucina, ad esempio, può essere
considerata come un algoritmo che partendo da un insieme di singoli alimenti
di base ed eseguendo una sequenza di passi, produce come risultato un piatto
composto). In un modo più formale, possiamo quindi definire l' algoritmo
come una sequenza ordinata e finita di istruzioni che, dato uno od una serie
di elementi in input, produce uno od una serie di risultati in output."
In quale sequenza di passi, allora, si articola un algoritmo genetico?
A livello ancora abbastanza astratto (piu' avanti aumenteremo il dettaglio),
le operazioni da compiere sono le seguenti:
1) Inizializzazione
Come primo passo dell'algoritmo viene creata una popolazione di partenza,
costituita da soluzioni casuali (cromosomi). Quando nella teoria degli
algoritmi genetici si parla di soluzione di un problema, naturalmente, non
la si deve intendere con il significato di "unica soluzione", oppure di
"soluzione giusta". Come una funzione matematica, in base a diversi valori
di ingresso, puo' restituire diversi valori, allo stesso modo noi possiamo
pensare alla presenza di diverse possibili soluzioni. E naturalmente, come
nel caso matematico possiamo avere un MASSIMO o un OTTIMO di un problema,
la soluzione che noi cerchiamo di ottenere alla fine e' quella OTTIMA.
2) Calcolo della fitness
Ad ogni cromosoma viene assegnato, in base alla sua bonta' rispetto al
problema, un valore chiamato "di fitness". Solitamente il valore di
fitness corrisponde al valore della funzione obiettivo (quella, cioe', di
cui si desidera trovare il massimo), ma non e' indispensabile che sia
sempre cosi': ad esempio, nella documentazione delle GAlib (e, per essere
piu' precisi, all'indirizzo http://lancet.mit.edu/galib-2.4/Overview.html)
questa distinzione viene fatta notare esplicitamente.
3) Riproduzione
I cromosomi che hanno un valore di fitness piu' alto sono quelli che piu'
facilmente diventeranno genitori delle prossime soluzioni durante la fase
di riproduzione. La scelta dei genitori avviene comunque in modo casuale,
tuttavia ai membri migliori di una popolazione viene data una maggiore
probabilita' di essere scelti.
Attraverso operatori che possono cambiare da un problema all'altro, i
cromosomi scelti possono generare dei figli, i quali erediteranno parte
dei propri geni da un genitore e parte dall'altro.
Attraverso un operatore di mutazione, infine, vengono operati su alcuni
dei figli dei cambiamenti casuali nei geni, prima che essi entrino a far
parte della nuova popolazione.
4) Generazione successiva
Se la soluzione ottima e' stata trovata (o se e' stata raggiunta qualche
altra condizione imposta dall'esterno, ad esempio e' stato raggiunto un
limite massimo di tempo di esecuzione), l'algoritmo termina.
In caso contrario, il vecchio insieme di cromosomi viene sostituito dai
figli appena generati: la nuova generazione e' completa, e si torna al
punto 2.
2.3 Riepilogo (e glossario)
-----------------------------------------------------------------------------
PROBLEMA
Il problema che voi desiderate risolvere. Come vedrete piu' avanti, dal
punto di vista del GA si trattera' sempre di un MODELLO del vostro
problema, da voi creato a suo uso e consumo.
POPOLAZIONE
Un insieme di cromosomi. La dimensione di una popolazione puo' variare
da un problema all'altro e tale variazione puo' cambiare anche in modo
sensibile le performance di un algoritmo genetico.
CROMOSOMA/GENOMA
Il generico elemento di una popolazione. Si tratta di una delle possibili
soluzioni al problema, non necessariamente quella ottima ma perlomeno una
che sia compatibile con il problema stesso. Ad esempio, se le soluzioni
sono le sequenze di mosse per risolvere un gioco, un cromosoma sara' una
sequenza di mosse, magari non vincente ma perlomeno valida.
FITNESS
E' il valore che viene assegnato ad ogni cromosoma per valutare la sua
bonta' in merito al problema da risolvere. Tanto maggiore e' la fitness,
tanto migliore e' il patrimonio genetico del cromosoma e quindi tanto
piu' probabilmente esso si riprodurra'.
FUNZIONE OBIETTIVO
E' la funzione di cui si desidera trovare il massimo per risolvere il
problema. Spesso il suo valore viene utilizzato come valore di fitness.
SELEZIONE
La procedura di selezione viene attuata prima della riproduzione. Essa
consiste nella scelta (casuale) dei cromosomi che si riprodurranno, tanto
piu' probabilmente quanto maggiore e' il loro valore di fitness.
RIPRODUZIONE
E' quel processo attraverso il quale vengono generati dei cromosomi figli
a partire da dei genitori, selezionati in precedenza. La modalita' con
cui questo avviene e gli operatori che vengono utilizzati sono descritti
nel prossimo capitolo.
MUTAZIONE
La mutazione consiste nel cambiamento (casuale) di alcuni geni in un
figlio appena generato. Non tutti i nuovi cromosomi mutano: anche in
questo caso, la scelta e' casuale.
GENERAZIONE
Una volta terminate le procedure di selezione, riproduzione e mutazione,
viene creata una nuova popolazione di cromosomi. Questa costituisce una
nuova generazione. Come potete notare, il numero di generazioni
corrisponde anche al numero di iterazioni dell'algoritmo e viene spesso
utilizzato per dare una stima della bonta' dell'algoritmo stesso.
=============================================================================
3. GA Techniques
-----------------------------------------------------------------------------
Nel capitolo precedente si e' accennato diverse volte alla bonta' e alle
performance di un algoritmo genetico. Naturalmente non ci si riferiva alle
caratteristiche dell'algoritmo ad alto livello di astrazione, ma a quelle
del GA completo di tutte le sue specifiche, partendo dal modello del problema
fino ad arrivare alla scelta delle probabilita' di riproduzione e mutazione
dei singoli cromosomi.
Come si costruisce, allora, un algoritmo genetico? Quali sono i passi che NOI
dobbiamo compiere per renderlo completo? Ma soprattutto, come possiamo creare
un _buon_ algoritmo genetico? Il capitolo che state per leggere cerchera' di
rispondere proprio a queste domande.
3.1 Scelta del problema
-----------------------------------------------------------------------------
Se proprio volete fare degli algoritmi genetici che funzionino, state bene
attenti a che problema scegliete! E' chiaro, purtroppo di solito succede il
contrario: voi avete un problema e dovete decidere come risolverlo. Beh, in
questo caso pensateci bene prima di scegliere di utilizzare un GA.
Parlando con diverse persone ho chiesto se esistessero problemi che di sicuro
non potevano essere risolti con un algoritmo genetico. Le risposte sono state
il piu' delle volte molto vaghe, dimostrandomi tra l'altro quale fosse il
livello medio di conoscenza dell'argomento. Tuttavia, alcune di esse sono
riuscite a chiarirmi un po' le idee: di solito, iniziavano con un onesto "non
lo so" e proseguivano con un illuminante "pero'".
Cercando di riunire i pero' chiarificatori e unendo ad essi la mia (ancora
scarsa) esperienza in proposito, sono giunto a queste conclusioni:
- gli algoritmi genetici sono perfettamente indicati per riempire delle righe
o dei quadrati di numeri 1. Tuttavia, qualsiasi problema la cui soluzione a
mano vi richieda meno tempo di quella trovata con un GA tende a perdere
interesse, specialmente quando lo leggete per la novantasettesima volta.
In generale, comunque, e' buona cosa saper valutare il tempo che potrebbe
richiedere una soluzione becera (ad esempio brute force) e paragonarlo a
quello che si sta effettivamente impiegando.
- spesso gli algoritmi genetici danno comunque l'impressione di funzionare in
quanto, a ben pensare, le popolazioni non possono fare altro che evolvere.
In realta', specialmente nel caso di problemi di una certa complessita',
essi evolvono con un'incredibile velocita' all'inizio, poi rallentano
sempre piu' man mano che si avvicinano alla soluzione fin quasi a fermarsi.
Quindi si', prima o poi risolveranno il problema, ma bisogna vedere QUANDO
lo faranno: se con un algoritmo di forza bruta o, peggio, sparando dei
valori a caso avete piu' probabilita' di terminare in un tempo inferiore,
lasciate perdere il GA.
- in alcuni casi un GA puo' non essere la soluzione ottimale, perche' magari
richiede un maggiore tempo di elaborazione rispetto a un altro algoritmo,
ma puo' allo stesso tempo essere la soluzione piu' rapida da sviluppare, in
quanto richiede un diverso tipo di conoscenza del problema. Ad esempio,
a volte anziche' eseguire il reverse engineering di un algoritmo (magari
addirittura a senso unico) e' piu' semplice utilizzarlo "a scatola chiusa"
e farci lavorare sopra un GA.
- in alcuni casi, il calcolo della fitness puo' essere esageratamente oneroso
in termini di tempo. Se non c'e' altro modo per valutare un cromosoma,
forse e' il caso di prendere in considerazione un altro algoritmo (o un
altro modello).
- gli algoritmi genetici non si prestano bene alla soluzione di problemi per
i quali "a piccoli cambiamenti in ingresso corrispondono grandi variazioni
nell'uscita" (mai sentito parlare di hash?). Dalla riproduzione e dalla
mutazione, infatti, sono soliti scaturire figli che non sono molto diversi
dai genitori: il risultato saranno valori della funzione obiettivo molto
lontani da quelli previsti (e, di conseguenza, peggiori). Per lo stesso
motivo, i problemi per cui e' garantito che "per piccoli cambiamenti in
ingresso corrispondono piccole variazioni in uscita" sono particolarmente
portati ad essere risolti con algoritmi genetici.
Un'alternativa che mi era stata suggerita per i problemi "tipo hash" e'
quella di studiare un modello diverso, che sia in grado di annullare,
ignorare, compensare o perlomeno rendere meno accentuata questa loro
proprieta': per questo vi invito a leggere il prossimo punto e la prossima
sezione.
- poiche', come vedrete fra breve, per la buona riuscita di un algoritmo
genetico e' indispensabile avere un buon modello, un fattore discriminante
per decidere se il problema sia risolubile o meno sta in chi costruisce il
modello. Detto volgarmente: se non siete capaci di modellizzare il problema
in modo adeguato, forse e' meglio che cerchiate di risolverlo con un altro
metodo.
3.2 Modello e cromosomi
-----------------------------------------------------------------------------
Gia' nella sezione precedente si e' accennato all'importanza dei modelli per
gli algoritmi genetici. In realta' i modelli sono non solo importanti, ma
addirittura fondamentali in Intelligenza Artificiale: questo perche' le
macchine che noi adoperiamo per risolvere dei problemi non lavorano mai in
modo diretto sulla realta', ma sempre attraverso dei modelli.
A questo punto la domanda sorgera' spontanea: cos'e' esattamente un modello,
allora? Per questa definizione mi piacerebbe citare alcune parole di colui
che per primo mi fece appassionare all'Intelligenza Artificiale, il prof.
Marco Somalvico:
"L’uomo, quando conosce un FENOMENO del naturale, può proporre la propria
conoscenza di tale fenomeno, oltre che con varie modalità individuali, come,
ad esempio, mediante una poesia, anche con un approccio, basato sul
cosiddetto metodo empirico sperimentale galileiano.
Tale metodo porta a formulare la conoscenza del fenomeno (si osservi che
tale conoscenza è causata nell’uomo dalla percezione del fenomeno che accade
nel naturale, ma essendone l’effetto, non deve essere, né confusa, né
identificata con la causa: un’entità è dunque il fenomeno, ed una diversa,
anche se correlata, entità è la conoscenza del fenomeno) secondo una
modalità denominata MODELLO, che, secondo l’insegnamento galileiano, è
basata sulle proprietà di:
1. FINITEZZA: la quantità di conoscenza descritta dal modello è finita,
a differenza della poesia che può attivare illimitate personali
interpretazioni nel lettore;
2. OGGETTIVITA’: il significato che si dà alla descrizione della conoscenza
espressa nel modello è unico, non esistendo ambiguità o polivalenza nella
interpretazione del linguaggio con il quale il modello viene formulato,
il che non avviene nel caso di una conoscenza descritta in una poesia o
anche in un brano di prosa basato su un’individuale adozione del
linguaggio descrittivo;
3. REPLICABILITA’: l’effetto che si ha della conoscenza acquisita,
apprendendo il modello, permette di effettuare una replica della
sperimentazione del fenomeno che porta alle stesse conclusioni (da parte
dell’UOMO SECONDO REPLICANTE, colui che ha appreso il modello) che erano
state formulate, la prima volta (da parte dell’UOMO PRIMO proponente,
colui che, conoscendo sperimentalmente il fenomeno, ne ha formulato il
modello)."
Riassumendo, un modello e' un modo di rappresentare la conoscenza di un
fenomeno, che ha come caratteristiche quelle di essere FINITO, OGGETTIVO e
REPLICABILE. Nel nostro caso particolare, tale rappresentazione deve anche
essere compatibile con i concetti base di un algoritmo genetico, quali
- i cromosomi: ogni possibile soluzione dev'essere traducibile in un
cromosoma e viceversa (cioe', una volta trovato il cromosoma migliore,
dev'essere possibile ricavare da esso la soluzione)
- il calcolo della fitness: per ogni cromosoma dev'essere possibile calcolare
un valore di fitness che rispecchi effettivamente la sua bonta'
- riproduzione e mutazione: i cromosomi devono essere in grado di riprodursi
e mutare, dando origine a nuovi cromosomi che corrispondano anch'essi a
soluzioni valide (e che possibilmente conservino, in caso di riproduzione,
le buone qualita' dei propri genitori)
Di fitness, riproduzione e mutazione parleremo in dettaglio nelle prossime
sezioni: per il momento, possiamo concentrarci sui cromosomi. Nella fase di
traduzione da realta' a modello, la costruzione dei cromosomi e' il primo
problema che dovrete affrontare: in pratica, infatti, essi costituiscono il
fondamento su cui l'intero modello si appoggia e, in base alla loro scelta,
sarete in grado di semplificare notevolmente tutto il lavoro che seguira' o
renderlo terribilmente complesso.
Un'altra considerazione da fare a proposito dei cromosomi e' che, qualsiasi
sia il modello che avete in mente, dovrete pur sempre descriverli attraverso
strutture dati compatibili con il vostro computer e con il linguaggio di
programmazione che avete deciso di usare. Questo significa che, prima di
scegliere un particolare modello per il vostro problema, sara' bene dare
un'occhiata alla documentazione delle librerie che desiderate utilizzare o,
nel caso in cui desideriate codare tutto da zero, mettersi a tavolino e
decidere in che modo desiderate rappresentare i vostri cromosomi. In genere,
indipendentemente dal linguaggio di programmazione che desiderate adottare,
le scelte che avete a disposizione sono le seguenti:
- usare un formato supportato dalle librerie specifiche del linguaggio che
avete deciso di usare (ad esempio, la "BinaryString", una "GAList" o un
"GAStringGenome", messi a disposizione dalle GAlib per C++). Il vantaggio
principale di questo approccio e' che, qualora la libreria sia abbastanza
completa, riuscirete provabilmente a trovare anche delle funzioni di
riproduzione e mutazione ad hoc. Questo, tra l'altro, e' un vantaggio da
non sottovalutare: grazie ad esso, infatti, potrete risparmiare molto tempo
in fase di programmazione e concentrarvi maggiormente sulla parte di
formalizzazione del problema.
- usare un formato personalizzato, che pero' sia possibile ricondurre in
qualche modo a uno di quelli esistenti. Un esempio pratico di questa
tecnica e' descritto in dettaglio piu' avanti, per il generatore di chiavi
di Netscape Cache Explorer: in parole povere, un sottoinsieme di caratteri
validi per l'algoritmo di controllo della chiave di registrazione viene
rimappato nell'ormai famigerato formato "stringa di bit". Il vantaggio e'
quello di avere un maggiore controllo sui dati e, allo stesso tempo, una
piena compatibilita' con le funzioni messe a disposizione dalle librerie.
- creare un formato ex novo, con tutti i vantaggi (personalizzazione totale)
e gli svantaggi (necessita' di creare anche tutte le funzioni che ne fanno
uso) che esso comporta. All'interno del testo che state leggendo questa
strada non viene mai descritta, ma a volte e' l'unica scelta per chi usa un
linguaggio che non ha ancora librerie dedicate ai GA. Che dire... in bocca
al lupo :)
Come potete notare, gia' in questo primo stadio della creazione del nostro
algoritmo genetico l'intervento umano e' _fondamentale_: prima ancora di
metter mano al codice, e ben prima che la macchina cominci a interpretarlo,
siete voi a decidere il modello che descrive il problema e in che modo i
cromosomi dovranno essere rappresentati; l'unico particolare che, in questa
fase, tradisce la presenza di una macchina, e' la necessita' di descrivere il
problema attraverso concetti che siano comprensibili ad essa.
Proprio a causa di una cosi' elevata componente umana, descrivere il modo in
cui un modello dev'essere creato o come un cromosoma dev'essere formalizzato
non e' un'operazione banale. Per quanto mi riguarda, mi limitero' ad elencare
alcune considerazioni ed esempi tratti dai miei esperimenti, tutti quanti
scritti usando le GAlib e quindi subordinati ai formati messi a disposizione
da esse.
Per il gioco "Lights Out" ho utilizzato una stringa di bit. Il motivo e'
semplice: il gioco e' rappresentato da una matrice 5x5 e scegliere una
casella due volte equivale a non sceglierla mai, quindi e' sufficiente dire
se essa deve essere selezionata (1) oppure no (0). Di conseguenza, una
partita puo' essere rappresentata da una sequenza di 25 bit, ognuno dei quali
e' acceso se la corrispondente casella dev'essere scelta o spento in caso
contrario.
Per quanto riguarda Netscape Cache Explorer, come gia' descritto, e' stata
usata una stringa di bit rimappata su un set di caratteri considerati validi
dall'algoritmo di controllo della chiave. La stringa di bit, in pratica,
viene suddivisa in tante sottostringhe, ognuna delle quali e' convertita in
un numero: tale numero rappresenta un indice che, applicato al charset creato
in precedenza, ci permette di ottenere un carattere da usare nella password.
Se non avete capito nulla, non preoccupatevi: piu' avanti questa procedura
verra' spiegata con maggiore dettaglio.
Per la crittanalisi di cifrature monoalfabetiche ho deciso di utilizzare un
particolare oggetto delle GAlib, chiamato GAStringGenome: questo perche'
avevo la necessita' di rappresentare, all'interno di un cromosoma, un
alfabeto cifrante che fosse in grado di conservare particolari proprieta',
specialmente in fase di riproduzione e di mutazione. La caratteristica di
base da conservare era il fatto che ogni alfabeto cifrante e' una semplice
permutazione dell'alfabeto normale: quindi, non potevo permettere che una
qualsiasi trasformazione generasse lettere doppie o mancanti nei miei
cromosomi. Ho ottenuto questo risultato usando, rispettivamente, le funzioni
GAStringPartialMatchCrossover per il crossover e GAStringSwapMutator per la
mutazione.
Per quanto riguarda i vari esperimenti che ho fatto con i numeri, in generale
ho sempre cercato di usare una stringa di bit che veniva poi convertita, con
una semplice funzione, da formato binario a decimale. A questo proposito ci
sarebbero moltissime considerazioni da fare: cosa significa, ad esempio, la
mutazione in una rappresentazione come questa? Cambiare un singolo bit nella
stringa significa far fare un salto al numero di una potenza di 2, tanto
maggiore quanto piu' significativo e' il bit che cambia valore. Quali sono
le conseguenza di quest'operazione? Solo queste richiederebbero un paper a
parte, che in effetti esiste e al quale vi rimando per saziare la vostra
curiosita': il testo si chiama "A Genetic Algorithm Tutorial" di Darrel
Whitley [1993] e ne trovate un link in Bibliografia.
3.3 Fitness
-----------------------------------------------------------------------------
La domanda che sono solito pormi quando devo inventarmi una funzione di
fitness e': "Cosa fa di un cromosoma un _buon_ cromosoma?". Infatti, come a
una gara di tuffi (o a una sfilata di californiane in bikini ;) immaginiamo
i giudici alzare dei cartelli con il voto proposto, allo stesso modo noi
dobbiamo dare un voto al "tuffo" (cioe' alla performance) dei nostri
cromosomi, per decidere chi di loro avra' una chance maggiore di riprodursi
e chi, invece, passera' la propria (tra l'altro brevissima) vita in bianco.
In alcuni casi, la valutazione di un cromosoma e' semplice e diretta: se,
ad esempio, vogliamo trovare il massimo di una funzione, il piu' delle volte
potremo utilizzare come voto il valore che essa restituisce. In altri casi,
invece, scegliere come assegnare una fitness ai propri cromosomi e' piu'
complesso. In generale, comunque, dovrete sempre avere una funzione in grado
di ricevere in ingresso un cromosoma e di restituire un voto in uscita: cio'
che voi dovrete decidere di volta in volta e' cosa fa tale funzione al suo
interno.
Una prima domanda che potreste porvi nel momento in cui decidete di creare
una funzione obiettivo e' la seguente: "so gia' dove desidero arrivare?". In
alcuni casi, infatti, noi gia' conosciamo, se non la soluzione esatta, almeno
il risultato che desideriamo ottenere e che sara' raggiunto solo partendo da
una soluzione esatta. Alcuni di questi casi sono dei veri e propri inviti a
nozze: escludendo quelli banali in cui veramente sappiamo gia' la soluzione
(tipo, giusto per infierire, "il cromosoma dev'essere una stringa piena di
1"), avremo solitamente una funzione da applicare (quella che ci porta dallo
spazio dei cromosomi, chiamato GENOTIPO, a quello dei risultati desiderati,
chiamato FENOTIPO) e una valutazione del valore ottenuto rispetto a quello
desiderato.
In realta', la situazione non e' sempre cosi' rosea come l'ho descritta:
innanzitutto, non sempre tali casi si verificano in realta'; inoltre, anche
quando sappiamo dove vogliamo arrivare possiamo non essere in grado di farlo
in modo semplice.
Ad esempio, mentre nel caso di NSCE il nostro GA ricava il valore esatto da
passare a una funzione a senso unico per ottenere il risultato desiderato,
nel caso di funzioni hash il lavoro e' decisamente piu' complicato: questo e'
dovuto al fatto che, mentre per l'algoritmo di NSCE piccole variazioni in
ingresso causano variazioni piu' o meno piccole in uscita, cio' non e' vero
per gli hash; la conseguenza e' che, usando la distanza dalla soluzione come
metro di valutazione, si tendono a giudicare buoni dei cromosomi pessimi e
viceversa.
Qualora, invece, non sia possibile avere un valore verso cui tendere, e'
necessario trovare comunque un modo per valutare i propri cromosomi e farli
evolvere per un numero di generazioni prefissato, sperando che questo sia
sufficiente per farli tendere alla soluzione ottima. Ad esempio, per il
problema delle cifrature monoalfabetiche noi non sappiamo a priori quale sia
il testo corretto, ma dobbiamo trovare un modo per valutare le nostre chiavi.
Varie tecniche sono possibili in questo caso, diverse per precisione e per
complessita': la scelta ideale e', naturalmente, quella che di volta in volta
porta ai risultati migliori con le risorse che si hanno a disposizione.
Il problema delle risorse e', in effetti, un altro fattore che bisogna tenere
in considerazione quando si crea una funzione obiettivo: e' normale, infatti,
cercare di ottenere il risultato migliore; tale risultato, tuttavia, deve
essere raggiungibile in tempi ragionevoli. La cosa piu' importante da tenere
presente in questa fase e' che il calcolo della fitness avviene, per ogni
generazione, per tutti i cromosomi di una popolazione: quindi, un guadagno
anche piccolo sulla singola valutazione puo' avere risultati evidenti sulle
performance generali dell'algoritmo genetico.
3.4 Riproduzione e Mutazione
-----------------------------------------------------------------------------
Gli operatori di riproduzione e mutazione consentono, rispettivamente, di
preservare cio' che di buono c'e' in un cromosoma (o, piu' in generale, in
una popolazione) e di uscire da eventuali "strade senza uscita" nel percorso
evolutivo.
Come per il calcolo della fitness anche in questo caso e' utile, nel momento
in cui si deve decidere che forma dare a tali operatori, farsi una domanda:
"Come e' possibile mantenere, o addirittura migliorare, le qualita' di un
cromosoma nel passaggio da una generazione all'altra?". Se siete fortunati,
la risposta a questa domanda verra' spontanea e sara' qualcosa del tipo
"basta usare gli operatori di default". In caso contario, dovrete ragionare
un po' su cosa state facendo e su cosa desiderate ottenere.
Ad esempio, giusto per citare alcuni dei casi piu' semplici, capita spesso
che, lavorando con stringhe di bit o loro derivati, sia sufficiente usare il
classico "OnePointCrossover" (uso i termini delle GAlib, ma una funzione di
questo tipo dovrebbe essere presente in _qualsiasi_ libreria dedicata ai GA).
Il caso di Netscape Cache Explorer ne e' un esempio: anche se le soluzioni
non sono esattamente stringhe di bit, ma vengono rimappate su di esse, il
OnePointCrossover funziona egregiamente.
In casi piu' complessi, invece, potrebbe essere necessario utilizzare delle
funzioni specifiche: ad esempio, il documento "The Applications of Genetic
Algorithms in Cryptanalysis" (citato in Bibliografia) mostra diversi
operatori di riproduzione alternativi al classico Crossover. Alcuni di questi
sono talvolta indispensabili e uno di essi (il PMX) e' stato utilizzato per
l'esempio dedicato alle cifrature monoalfabetiche, in modo da garantire la
conservazione delle proprieta' dei cromosomi da una generazione all'altra.
Per lo stesso motivo, anche la mutazione puo' essere attuata da operatori
differenti: se, infatti, in una generica stringa di bit si puo' mutare un
cromosoma semplicemente invertendo lo stato di alcuni bit scelti a caso, vi
sono situazioni (ad esempio, quando si desidera garantire l'unicita' degli
alleli in un cromosoma) in cui questa tecnica e' sconsigliata. Anche in
questo caso, l'esempio dedicato alla crittanalisi offre una soluzione al
problema, tramite la scelta di un diverso operatore di mutazione.
3.5 Algoritmi genetici e probabilita'
-----------------------------------------------------------------------------
Anche se finora se ne e' parlato relativamente poco, nel campo dei GA la
statistica e il caso rivestono un ruolo particolarmente importante. Infatti,
cosi' come ogni algoritmo genetico viene inizializzato con una popolazione
costituita da elementi casuali, allo stesso modo la sua evoluzione avviene
secondo leggi probabilistiche: non e' detto che gli individui migliori si
riproducano sicuramente, ma e' solo un fatto piu' o meno probabile; non e'
detto neanche che la prole conservi integralmente le qualita' dei genitori,
in quanto c'e' la possibilita' che essa muti.
Per questo motivo, al termine del vostro lavoro di progettazione avrete la
possibilita' di giocare con diversi parametri che, a seconda dei loro valori,
potranno cambiare anche radicalmente il comportamento del vostro GA. In
particolare, le principali variabili che potrete modificare saranno:
Dimensione della popolazione: ragionando in termini probabilistici, tanto
maggiore e' questo valore tanto piu' grande e' la probabilita' che alcune
buone qualita' degli individui vengano conservate. Naturalmente, aumentare
la dimensione della popolazione significa anche aumentare il numero di
valutazioni per ogni generazione, quindi e' un'operazione che conviene
fare solo quando il calcolo della fitness non sia troppo oneroso.
Probabilita' di riproduzione: tanto maggiore e' questo valore, tanto piu'
facilmente i migliori elementi trasmetteranno il proprio patrimonio
genetico tramite riproduzione. Anche se, in genere, si tende a mantenere il
valore di questo parametro molto vicino al massimo (cioe' 1), non sempre
questo e' il modo migliore di procedere: l'esperienza mostrera' che in
alcuni casi (in particolare, quelli in cui la riproduzione puo' causare
una perdita di informazioni) e' meglio abbassare questo parametro e
lasciare un maggior spazio alla semplice sopravvivenza degli individui o
alla loro mutazione.
Probabilita' di mutazione: in generale, tale parametro viene tenuto piuttosto
basso, perche' esso introduce una forte fonte di casualita' e solitamente,
invece, si desidera che l'algoritmo evolva in modo piu' controllato. In
alcuni casi, tuttavia, aumentare la probabilita' di mutazione aiuta ad
uscire da situazioni di ottimo locale, in cui l'algoritmo si ferma pur non
avendo trovato il risultato migliore. In questi casi, la mutazione puo'
aiutare a spostare il cromosoma in una diversa zona dello spazio delle
soluzioni e a proseguire l'indagine in questo nuovo spazio. Notate, pero',
che mentre e' molto facile trovare una soluzione migliore tramite mutazione
all'inizio dell'evoluzione, quest'operazione diventa solitamente sempre
piu' complessa man mano che i cromosomi si avvicinano all'ottimo.
=============================================================================
4. Programmazione
-----------------------------------------------------------------------------
Se mentre leggevate vi e' venuta voglia di mettere le mani sulla tastiera e
cominciare a codare il vostro primo algoritmo genetico, questo e' il capitolo
che fa per voi. In realta', la scelta di un solo linguaggio di programmazione
(il C++) e di una sola raccolta di librerie (le GAlib) potrebbero sembrarvi
un po' limitanti: tuttavia, se da una parte esse sono abbastanza buone per
diversi tipi di progetto (e, anzi, sicuramente piu' potenti di quanto non vi
possa servire per i vostri primi esperimenti), dall'altra nessuno vi
impedisce di usare gli stessi concetti appresi in questo capitolo con altri
linguaggi di programmazione. Anzi, nel caso in cui questo avvenga sarebbe
bello farmelo sapere (perl, Peeerl, vi prego, PEEERL! ;).
4.1 GAlib
-----------------------------------------------------------------------------
"GAlib contiene un insieme di oggetti per la programmazione di algoritmi
genetici. La libreria include strumenti per l'ottimizzazione tramite GA,
usando rappresentazioni e operatori genetici qualsiasi. La documentazione
comprende una descrizione estesa su come implementare un algoritmo genetico,
oltre a esempi che illustrano come personalizzare le classi di GAlib."
In aggiunta a questo, le GAlib sono free (as in speech, anche se la licenza
e' in parte GNU e in parte MIT), ormai stabili e consolidate (dire vecchie mi
pareva brutto, ma l'ultima versione risale al 2000) e, personalmente, ho
trovato la loro documentazione _veramente_ utile. E, visto il dettaglio con
cui ogni aspetto delle GAlib viene trattato, evito di dilungarmi in ulteriori
descrizioni, citando direttamente la pagina "Feature List for GAlib":
General features
* Many examples are included illustrating the use of various GAlib features,
class derivations, parallelization, deterministic crowding, travelling
salesman, DeJong, and Royal Road problems.
* The library has been used on various DOS/Windows, Windows NT/95, MacOS, and
UNIX configurations. GAlib compiles without warnings on most major
compilers.
* Templates are used in some genome classes, but GAlib can be used without
templates if your compiler does not understand them.
* Four random number generators are included with the library. You can select
the one most appropriate for your system, or use your own.
Algorithms, Parameters, and Statistics
* GAlib can be used with PVM (parallel virtual machine) to evolve populations
and/or individuals in parallel on multiple CPUs.
* Genetic algorithm parameters can be configured from file, command-line,
and/or code.
* Overlapping (steady-state GA) and non-overlapping (simple GA) populations
are supported. You can also specify the amount of overlap (% replacement).
The distribution includes examples of other derived genetic algorithms such
as a genetic algorithm with sub-populations and another that uses
deterministic crowding.
* New genetic algorithms can be quickly tested by deriving from the base
genetic algorithm classes in the library. In many cases you need only
override one virtual function.
* Built-in termination methods include convergence and number-of-generations.
The termination method can be customized for any existing genetic algorithm
class or for new classes you derive.
* Speciation can be done with either DeJong-style crowding (using a
replacement strategy) or Goldberg-style sharing (using fitness scaling).
* Elitism is optional for non-overlapping genetic algorithms.
* Built-in replacement strategies (for overlapping populations) include
replace parent, replace random, replace worst. The replacement operator can
be customized.
* Built-in selection methods include rank, roulette wheel, tournament,
stochastic remainder sampling, stochastic uniform sampling, and
deterministic sampling. The selection operator can be customized.
* "on-line" and "off-line" statistics are recorded as well as max, min, mean,
standard deviation, and diversity. You can specify which statistics should
be recorded and how often they should be flushed to file.
Genomes and Operators
* Chromosomes can be built from any C++ data type. You can use the types
built-in to the library (bit-string, array, list, tree) or derive a
chromosome based on your own objects.
* Built-in chromosome types include real number arrays, list, tree, 1D, 2D,
and 3D arrays, 1D, 2D, and 3D binary string. The binary strings, strings,
and arrays can be variable length. The lists and trees can contain any
object in their nodes. The array can contain any object in each element.
* All chromosome initialization, mutation, crossover, and comparison methods
can be customized.
* Built-in initialization operators include uniform random, order-based
random, allele-based random, and initialize-to-zero.
* Built-in mutation operators include random flip, random swap, Gaussian,
destructive, swap subtree, swap node.
* Built-in crossover operators include arithmetic, blend, partial match,
ordered, cycle, single point, two point, even, odd, uniform, node- and
subtree-single point. Edge recombination is included in the examples.
* Dominance and Diploidy are not explicitly built in to the library, but any
of the genome classes in the library can easily be extended to become
diploid chromosomes.
Objective function
* Objective functions can be population- or individual-based.
* If the built-in genomes adequately represent your problem, a user-specified
objective function is the only problem-specific code that must be written.
4.2 Generica struttura di un GA in C++
-----------------------------------------------------------------------------
La struttura di un algoritmo genetico in C++ riprende, in modo abbastanza
fedele, i passi che avevamo descritto in modo astratto nel primo capitolo:
1) Inizializzazione
2) Calcolo della fitness
3) Riproduzione
4) Generazione successiva
La versione piu' semplice di GA che e' possibile creare con le GAlib segue
questa struttura:
/*-------------------------------------------------------------------------*/
float Objective(GAGenome&); // prototipo della funzione obiettivo
main(){
// crea un genoma
GA2DBinaryStringGenome genome(width, height, Objective);
// crea un GA
GASimpleGA ga(genome);
// evolvi il GA (passi 1, 3, 4)
ga.evolve();
// scrivi i risultati
cout << ga.statistics() << endl;
}
float Objective(GAGenome&) {
// qui va il corpo della funzione obiettivo (passo 2)
}
/*-------------------------------------------------------------------------*/
Le operazioni eseguite sono le seguenti:
1) Creazione di un genoma (e' il nome che all'interno delle GAlib viene dato
a quelli che noi abbiamo finora chiamato cromosomi), attraverso uno degli
oggetti messi a disposizione dalle librerie (in questo caso, una matrice
binaria di larghezza "width" e altezza "height")
2) Creazione del GA (in questo caso, un GASimpleGA)
3) Evoluzione del GA: attraverso il comando evolve() viene eseguita prima
l'inizializzazione del GA (creazione di una popolazione casuale e prima
valutazione), quindi una serie di successive valutazioni (tramite la
funzione Objective), riproduzioni e selezioni, finche' non si verificano
le condizioni di arresto dell'algoritmo
4) Output dei risultati
Come potete notare, se si usano gli oggetti messi a disposizione dalle GAlib
e' possibile scrivere un nuovo algoritmo genetico senza quasi aggiungere
codice (se non quello relativo alla funzione obiettivo). In realta', appena
comincerete a lavorare su progetti non banali vedrete che sara' richiesto un
maggiore intervento da parte vostra, tuttavia una buona fetta di lavoro sara'
sempre gia' pronta. Per esempi un po' piu' avanzati vi rimando al prossimo
capitolo.
=============================================================================
5. Esempi
-----------------------------------------------------------------------------
All'interno di questo capitolo potrete vedere alcuni dei progetti sui quali
ho lavorato negli ultimi tempi e che hanno avuto esiti soddisfacenti (beh,
almeno per me!). Per ognuno di essi, oltre a inserire il codice C del
programma pronto e finito, ho deciso di spiegare le mie scelte progettuali,
con la speranza che questo possa aiutare anche voi nella creazione dei vostri
algoritmi genetici. Buona lettura e... in bocca al lupo ;)
5.1 NSCE
-----------------------------------------------------------------------------
NSCE (nsce.exe by Matthias Wolf, version 1.20, 22 Aug 1996, 147.456 bytes,
dead listing is about 2.109.000 bytes) e' una vecchia applicazione per
Netscape che consente di "esplorare" la Cache di tale browser e vedere, anche
quando si e' scollegati da Internet, le pagine scaricate in precedenza.
Ho gia' spiegato in dettaglio la protezione di questo programma qualche anno
fa (beh... SETTE! Comincio a sentirmi vecchio...), in un tutorial che forse
potete ancora trovare online su http://www.woodmann.com/fravia/nscekey.htm
(in inglese), su http://ringzer0.ath.cx/tutes/nscekita.htm (in italiano) o
cercando "nscekey" su google.
La protezione in se' non e' particolarmente complessa, ma puo' risultare
interessante a livello didattico per chi desidera avvicinarsi alla creazione
di algoritmi genetici: come potrete vedere piu' avanti, infatti, l'algoritmo
di validazione si presta particolarmente alla brutalizzazione tramite GA.
Poiche' esso fa uso dell'aritmetica dei moduli, ci son due modi per generare
una chiave valida:
- comprendere il funzionamento dell'algoritmo, reversarlo e stabilire alcuni
presupposti che ridurranno la dimensione del problema, consentendoci di
trovare una chiave fra tutte quelle che esistono (come descritto nel
tutorial)
- comprendere il funzionamento dell'algoritmo, adattarlo perche' funzioni con
un GA e usarlo per far evolvere i nostri cromosomi, ottenendo chiavi sempre
diverse: questa e' la strada che percorreremo ora.
5.1.1 Comprendere il funzionamento dell'algoritmo
-----------------------------------------------------------------------------
L'algoritmo e' spiegato in dettaglio all'interno del tutorial: se desiderate
capire come e' stato ricavato, vi consiglio di leggerlo; ai fini di questo
testo, invece, e' sufficiente la descrizione che segue.
- l'algoritmo riceve una login e una password, entrambe di 8 caratteri (in
realta', la stringa di login puo' avere una lunghezza diversa, ma poiche'
il programma stesso la riconduce sempre a 8 caratteri e' piu' semplice
considerarla sempre cosi')
- viene creata una nuova stringa "p", sempre di lunghezza 8, nella quale i
singoli "pn" (p1,...,p8) sono cosi' ottenuti:
pn = valore dell'n-esimo elemento della password inserita -
- ((n-esimo elemento della login)%26)+65) +
+ (26, se il valore finale e' <0)
- a questo punto, lo scopo e' soddisfare la seguente equazione
r1*r2 + r2*r3 + r3*r4 + r4*r5 + r5*r6 + r6*r7 + r7*r8 = 190h = 400d
dove
r1=p1+0%10
r2=p2+1%10
r3=p3+2%10
r4=p4+3%10
r5=p5+4%10
r6=p6+5%10
r7=p7+6%10
r8=p8+7%10
Come potete facilmente intuire, la condizione che dobbiamo soddisfare (cioe'
che la somma finale sia uguale a 400) puo' darci un notevole aiuto quando si
tratta di decidere la funzione obiettivo. Ad esempio, potremmo decidere che
quanto piu' una soluzione restituisce un valore vicino a 400, tanto essa e'
migliore.
5.1.2 Modello e cromosoma
-----------------------------------------------------------------------------
Il generico cromosoma deve rappresentare una stringa di registrazione che
risulti, innanzitutto, valida per l'algoritmo di controllo della password.
Essa, cioe', deve avere una lunghezza prestabilita di 8 byte e contenere solo
alcuni caratteri. Lo scopo del nostro GA e' quello di ottenere, a partire da
una stringa valida, una password _esatta_, cioe' una che, abbinata alla
nostra login, sia in grado di registrare il programma.
La limitazione sul set di caratteri mi ha portato a scegliere un formato piu'
o meno personalizzato per i cromosomi: dal punto di vista dell'algoritmo
genetico essi non sono altro che stringhe di bit, ma in fase di valutazione
vengono trasformati in password vere e proprie. Il metodo per trasformare la
stringa di bit in password e' il seguente:
- la stringa di bit, di lunghezza 48, viene spezzata in 8 sottostringhe da 6
bit ciascuna.
- ognuna di queste sottostringhe viene convertita in un numero, che fa da
indice a un array di 64 (2^6) caratteri. Tale array contiene i caratteri
ammessi dall'algoritmo di validazione, o meglio un loro sottoinsieme creato
intenzionalmente in modo da avere dimensione 64.
- agli 8 numeri vengono fatti corrispondere 8 caratteri, che concatenati
generano una password sicuramente valida (e, alla fine dell'esecuzione del
GA, anche esatta).
Per meglio comprendere il funzionamento di questa trasformazione, ecco un
esempio: supponiamo che l'insieme di caratteri ammessi sia il seguente
alfabeto = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_"
per un totale di 48 caratteri, e che la stringa di bit assuma a un certo
punto il valore
000011000000111110000011000000111110000011000000
Allora, dividendo la stringa in blocchi da 6 bit, otteniamo le seguenti otto
stringhe:
000011 = 3 => alfabeto[3] = "d"
000000 = 0 => alfabeto[0] = "a"
111110 = 63 => alfabeto[63] = "-"
000011 = 3 => alfabeto[3] = "d"
000000 = 0 => alfabeto[0] = "a"
111110 = 63 => alfabeto[63] = "-"
000011 = 3 => alfabeto[3] = "d"
000000 = 0 => alfabeto[0] = "a"
La password corrispondente, quindi, e' "da-da-da" (Si', e' valida. No, non
e' esatta!).
5.1.3 Fitness
-----------------------------------------------------------------------------
Come gia' anticipato, per quanto riguarda il calcolo della fitness siamo
avvantaggiati dalla presenza di un controllo numerico di validita'. Poiche'
tale controllo restituisce il valore 400 solo se la password e' corretta,
allora possiamo stabilire che tanto piu' la valutazione dei nostri cromosomi
si avvicinera' al numero 400, tanto maggiore dovra' essere la probabilita'
che essi si riproducano.
Questa ipotesi, naturalmente, non e' sempre corretta. Per verificarne la
validita', sono state fatte diverse prove su piccole variazioni delle varie
password: il risultato ha mostrato che, effettivamente, cromosomi simili
offrono soluzioni dal punteggio abbastanza vicino; inoltre, anche nel caso
in cui il salto (dovuto ai calcoli in modulo) sia significativo, esso e'
comunque in grado di convergere nuovamente nel giro di poche generazioni.
A questo punto, come possiamo far si' che la funzione obiettivo restituisca
un valore tanto piu' alto quanto piu' il risultato della funzione di
controllo sia vicino a 400? Le considerazioni che ho fatto sono le seguenti:
1) il valore "x" restituito dalla funzione di controllo e' un numero positivo
2) x puo' essere maggiore o minore di 400, e vi e' tanto piu' vicino quanto
piu' la password si avvicina all'essere corretta
3) QUINDI, la differenza fra 400 e x puo' essere una buona stima: tanto piu'
piccola e' tale differenza (IN MODULO), tanto migliore e' la password. MA,
per il calcolo standard della fitness, voglio una funzione obiettivo che
sia tanto piu' GRANDE quanto maggiore sia la bonta' della password, quindi
devo trovare un modo di invertire tale funzione
5) ALLORA ci metto davanti un bel "-": immaginate il grafico della funzione
che si ribalta e gioite :) Tuttavia, a questo punto, i valori che si
ottengono sono perlopiu' negativi: allora trasliamo la funzione verso
l'alto, esattamente di 400.
6) Concludendo, detto "x" il valore dato dalla funzione di controllo, la
funzione obiettivo restituira'
(400-abs(400-x))
e l'algoritmo genetico cerchera' di trovare i valori per cui tale funzione
restituisca _esattamente_ il valore 400.
5.1.4 Riproduzione e mutazione
-----------------------------------------------------------------------------
Su questo argomento, in realta', non c'e' molto da dire: grazie alle GAlib e
alla particolare semplicita' del problema, possiamo semplicemente appoggiarci
alle funzioni di default per la riproduzione e la mutazione di genomi del
tipo "GA1DBinaryStringGenome" (rispettivamente, il "OnePointCrossover" e il
"FlipMutator").
Dando un'occhiata alla documentazione, potrete vedere che per questo genoma
esistono altri tre tipi di crossover (UniformCrossover, EvenOddCrossover e
TwoPointCrossover): la possibilita' di sperimentare con essi e' lasciata come
esercizio ai lettori ;)
5.1.5 Parametri
-----------------------------------------------------------------------------
Pur essendo il problema abbastanza semplice e, anzi, anche in virtu' di
questa sua caratteristica, sono stato in grado di fare numerosi esperimenti
sui diversi parametri che caratterizzano l'algoritmo genetico. Questo mi ha
portato non solo a capire quale combinazione fosse la migliore per il
particolare problema in esame, ma anche a comprendere qualcosa di piu' sul
loro significato in generale.
Popolazione: il valore assegnato inizialmente a questo parametro e' stato 10.
Quando esso aumenta, aumenta anche la possibilita' di preservare un buon
patrimonio genetico, quindi l'algoritmo ha bisogno di un numero inferiore
di generazioni per convergere alla soluzione ottima: a differenza di una
popolazione di 10 membri, che impiega in media 2-3 centinaia di generazioni
per raggiungere l'ottimo, una di 50 raggiunge solitamente la password
esatta in meno di 100 generazioni. Naturalmente, aumentando la dimensione
della popolazione aumenta anche il numero di valutazioni per ogni
generazione, ma in questo caso particolare non si e' avvertito un aumento
sensibile del carico.
Crossover: la probabilita' di crossover scelta per default e' di 0.9. Quando
si è cercato di diminuirla (fino a 0.5), non si sono riscontrate differenze
apprezzabili. Aumentandola anche di poco, invece (da 0.9, valore gia' di
per se' alto, a 0.99), i risultati sono un po' migliorati.
Mutazione: il valore predefinito di probabilita' di mutazione era di 0.01. In
generale, aumentare tale valore puo' aiutare ad uscire dalle condizioni di
stallo, tuttavia in questo caso esso sembra essere abbastanza trascurabile.
Infatti, un aumento basso non ha sortito effetti significativi, mentre uno
drastico (da 0.01 a 0.1) ha rallentato notevolmente la convergenza, anche
nel caso di popolazioni molto grandi.
Numero di generazioni: All'interno del programma e' stato impostato un
ulteriore parametro "ngen", che permette di vedere alcune statistiche,
relative alla popolazione corrente, ogni "ngen" generazioni. A differenza
di altri algoritmi, dove l'evoluzione avviene in migliaia di generazioni,
in questo e' stato possibile apprezzare cambiamenti anche con un ngen molto
piccolo (al limite 1), in generale sempre piu' piccoli man mano che ci si
avvicinava alla soluzione esatta.
5.1.6 Conclusioni
-----------------------------------------------------------------------------
Nel complesso, l'esperimento ha avuto un esito positivo: dal punto di vista
puramente pratico, le password generate dal GA funzionano. Inoltre, dal punto
di vista teorico/didattico, lo stesso algoritmo genetico sembra comportarsi
piuttosto bene: i tempi di esecuzione sono ragionevoli e, indipendentemente
dalla CPU utilizzata, il numero di generazioni necessarie per raggiungere
l'ottimo non e' mai esageratamente alto (al massimo poche centinaia). Una
dimostrazione del buon comportamento dell'algoritmo e' data anche dalla
predilezione dell'operatore di riproduzione rispetto a quello di mutazione:
ai cambiamenti puramente casuali, infatti, vengono preferiti quelli dovuti
al tentativo di conservazione delle caratteristiche positive dei cromosomi.
Una delle possibili ragioni di un tale successo per l'algoritmo genetico
puo' essere imputata all'estrema semplicita' del problema: in un caso reale,
probabilmente, esso verrebbe addirittura affrontato come descritto nel primo
tutorial su NSCE, cioe' semplicemente reversando l'algoritmo di controllo.
Tuttavia, nel caso in cui la funzione fosse stata piu' complessa, la strada
piu' semplice sarebbe stata probabilmente questa, che non richiede di
ricavare funzioni inverse ma solo di lavorare con cio' che si ha gia' a
disposizione.
Un'ultima nota riguarda proprio le funzioni di protezione: spesso, come in
questo caso, i programmatori preferiscono affidarsi alla "security by
obscurity", creando algoritmi ex novo e confidando nel fatto che, una volta
compilati, essi saranno piu' complessi da comprendere. Beh, come avete visto
non e' cosi': anzi, qualora questi algoritmi siano (come in questo caso) mal
progettati, essi saranno ancora piu' deboli, facilitando non solo il loro
rovesciamento, ma anche un attacco tramite GA che non sarebbe stato possibile
con delle funzioni a senso unico piu' serie.
5.1.7 Codice sorgente
-----------------------------------------------------------------------------
/* --------------------------------------------------------------------------
NSCEKAI
Netscape Cache Explorer Genetic Keygen
-------------------------------------------------------------------------- */
#include <stdio.h>
#include <string.h>
#include <ga/GASimpleGA.h> // we're going to use the simple GA
#include <ga/GA1DBinStrGenome.h> // and the 1D binary string genome
float Objective(GAGenome &); // This is the declaration of our obj function.
// The definition comes later in the file.
char *genome2string (GAGenome &);
char *alpha = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_";
char *name = "AiTTaLaM";
char p[9], r[9], s[9];
int main (int argc,char **argv){
// See if we've been given a seed to use (for testing purposes). When you
// specify a random seed, the evolution will be exactly the same each time
// you use that seed number.
for(int ii=1; ii<argc; ii++) {
if(strcmp(argv[ii++],"seed") == 0) {
GARandomSeed((unsigned int)atoi(argv[ii]));
}
}
int width = 48; // that is, 6 bits x 8 chars
int popsize = 10;
int ngen = 1;
float pmut = 0.01;
float pcross = 0.9;
int gennum = 0;
float objective;
// create genome objects
GA1DBinaryStringGenome genome(width, Objective);
GA1DBinaryStringGenome bestgenome(width, Objective);
// create and setup ga
GASimpleGA ga(genome);
ga.populationSize(popsize);
ga.nGenerations(ngen);
ga.pMutation(pmut);
ga.pCrossover(pcross);
ga.initialize();
do {
// evolve for ngen generations
for (int i=0;i<ngen;i++) ++ga;
// print out the best genome found.
printf ("The GA found this password for name \"%s\":\n",name);
cout << ga.statistics().bestIndividual() << "\n";
gennum += ngen;
bestgenome = ga.statistics().bestIndividual();
printf ("%s\n", genome2string(bestgenome));
objective = Objective(bestgenome);
printf ("Generation: %04d Score: %.0f\n\n",gennum,objective);
for (int i=0;i<=width;i++) printf ("-");
printf ("\n");
} while (objective<400);
// print stats for the last generation
for (int i=0;i<ga.population().size();i++){
cout << ga.population().individual(i) << " (" << Objective(ga.population().individual(i)) << ")\n";
}
return 0;
}
// genome2string converts a genome into the matching string
char *genome2string (GAGenome& g){
GA1DBinaryStringGenome & genome = (GA1DBinaryStringGenome &)g;
int substr = 6;
int l = 0;
int strptr = 0;
for(int i=0;i<int(sizeof(s));i++) s[i]=0;
for(int i=0; i<genome.length(); i++){
substr--;
l += (genome.gene(i)*(1<<substr));
if (substr==0){
s[strptr] = alpha[l];
substr=6; l=0; strptr++;
}
}
return s;
}
// This is the objective function: look at NSCE keycheck algo!
float Objective(GAGenome& g) {
GA1DBinaryStringGenome & genome = (GA1DBinaryStringGenome &)g;
int i;
genome2string (genome);
for (i=0;i<8;i++){
p[i]=(s[i]-((name[i]%26)+65));
if (p[i]<0) p[i]+= 26;
r[i]=(p[i]+i)%10;
}
int j=0;
for (i=0;i<7;i++){
j += (r[i]*r[i+1]);
}
return float(400-abs(400-j));
}
5.2 Cifrature monoalfabetiche
-----------------------------------------------------------------------------
Questo esempio, pur non essendo di una complessita' disarmante, e' uno di
cui vado particolarmente fiero per diversi motivi: innanzitutto, utilizza
degli oggetti e delle funzioni delle GAlib non banali; poi, rispetto ad altri
esercizi, richiede una conoscenza un po' piu' approfondita del problema, e
documentarmi su di esso e' stato molto interessante; infine, mi sembra
funzioni discretamente e questo non puo' che farmi piacere ;)
Il problema da risolvere consiste nel decifrare una cifratura monoalfabetica,
cioe', una di quelle in cui ad ogni lettera ne corrisponde sempre un'altra
(e solo quella). In pratica, applicare una cifratura di questo genere a un
testo significa "tradurre" il testo usando un diverso alfabeto, ottenuto dal
primo sostituendo i caratteri originali con quelli desiderati.
Uno degli esempi piu' semplici di cifratura monoalfabetica e' quella di
Cesare, che consiste nel sostituire ogni lettera con quella che la precede
(o la segue) di una o piu' posizioni. Quindi, prendendo ad esempio l'alfabeto
LMNOPQRSTUVWXYZABCDEFGHIJK | (ottenuto spostando l'originale a sinistra
ABCDEFGHIJKLMNOPQRSTUVWXYZ | di 12 posizioni)
la frase:
"Nel mezzo del cammin di nostra vita"
diventa
"Ypw xpkkz opw nlxxty ot yzdecl gtel".
Il caso che ho scelto di analizzare e' quello piu' generale, in cui cioe'
l'alfabeto non viene semplicemente traslato ma le lettere possono essere
mescolate in qualsiasi modo. Lo scopo dell'algoritmo genetico sara', quindi,
quello di trovare l'alfabeto utilizzato per cifrare un dato messaggio e che,
una volta applicato nuovamente al testo, sara' in grado di decifrarlo.
L'esercizio in se' non e' particolarmente complesso, nel senso che per un
essere umano e' uno degli esercizi di crittanalisi piu' semplici. Tuttavia,
far svolgere questo compito da una macchina e' allo stesso tempo un'attivita'
interessante, per i problemi che e' necessario risolvere, e istruttiva, per
le conclusioni che si possono trarre da essi.
5.2.2 Modello e cromosoma
-----------------------------------------------------------------------------
La generica soluzione al problema, cioe' il cromosoma che cercheremo di far
evolvere, e' in questo caso l'alfabeto cifrante, cioe' una permutazione del
normale alfabeto grazie alla quale sia possibile decifrare il testo per
ottenerne uno di senso compiuto.
Proprio in virtu' della sua definizione, questo particolare cromosoma e'
molto piu' di una semplice sequenza di lettere: esso avra' sempre lunghezza
26 e le lettere saranno _TUTTE_ e _SOLE_ quelle dell'alfabeto. Per questo
motivo, e' necessario trovare un modo per
- trasmettere queste caratteristiche ai cromosomi appena creati
- conservarle durante la riproduzione e la mutazione
Mentre il secondo punto verra' affrontato in dettaglio piu' avanti, per il
primo le scelte operative sono state le seguenti:
- per il genoma, e' stato utilizzato l'oggetto GAStringGenome, che consente
di definire un cromosoma come una generica sequenza di alleli;
- l'insieme dei possibili alleli corrisponde, naturalmente, all'insieme delle
lettere dell'alfabeto;
- per garantire la presenza di tutte le lettere e la loro unicita' in ogni
cromosoma, questi vengono inizializzati con un'apposita procedura che li
"riempie" in ordine alfabetico e poi effettua degli swap casuali fra varie
lettere. Tale operazione permette di avere una popolazione di partenza
casuale, ma sempre rispettosa dei vincoli stabiliti.
5.2.3 Fitness
-----------------------------------------------------------------------------
Il calcolo della fitness e' quello che ha richiesto un maggior impiego di
risorse e una conoscenza piu' approfondita del problema. In questo caso,
infatti, valutare la bonta' di un alfabeto significa sostanzialmente usarlo
per decifrare il testo e verificare se questo ha senso compiuto. Il problema
maggiore, come si puo' intuire, e' proprio spiegare a una macchina cosa
significhi, per un testo, avere senso compiuto: in letteratura ho trovato
la diverse tecniche, alcune delle quali sono descritte in seguito insieme ai
propri pregi e difetti.
Una delle tecniche piu' classiche e, allo stesso tempo, piu' banali consiste
nel contare le frequenze delle lettere che compaiono nel testo cifrato. Tali
frequenze vengono poi paragonate con una tabella di "frequenze standard"
(creata a partire da vari testi scritti nella lingua in cui si presume sia
scritto il documento cifrato), in modo da ricavare una corrispondenza fra
l'alfabeto originale e quello cifrante. Di solito quest'operazione e' utile
in aiuto a un essere umano, ma raramente essa da sola consente di decifrare
correttamente un testo. A suo favore gioca il fatto che, a livello
computazionale, essa richiede relativamente poche risorse.
Una tecnica un po' piu' avanzata consiste nel contare le dimensioni e le
frequenze dei "cluster" di vocali o di consonanti presenti nel testo. Dalla
letteratura pare che quest'operazione dia dei risultati migliori, ma che
ancora non sia risolutiva se utilizzata in automatico da una macchina.
Due metodi piu' efficienti, in grado di fornire buoni risultati anche senza
intervento umano, usano le frequenze non delle singole lettere, ma delle
coppie (digrammi) o delle triplette (trigrammi) di lettere del testo cifrato.
Anche in questo caso, le frequenze vengono paragonate con dei valori salvati
in precedenza e derivanti dallo studio di testi in chiaro. A differenza
dell'analisi delle frequenze semplici, queste tecniche richiedono una
maggiore potenza di calcolo.
L'ultima delle soluzioni prese in esame consiste nel cercare alcune parole
del testo decifrato all'interno di un dizionario. A seconda del numero delle
parole che si desidera verificare e delle dimensioni del dizionario, la
richiesta di risorse puo' cambiare notevolmente. Il vantaggio principale sta
nel fatto che, a patto di avere un buon dizionario, questo metodo potrebbe
fornire risultati molto buoni anche per testi piccoli.
Alla fine, grazie anche alla scoperta di un programma (crank, scaricabile da
http://crank.sf.net) dal quale ho potuto attingere copiosamente codice per la
gestione delle statistiche, ho deciso di concentrare i miei esperimenti sulla
analisi delle frequenze, i digrammi e i trigrammi. La procedura attuata dalla
funzione obiettivo e' la seguente:
1) il cromosoma, nel formato di un GAStringGenome, viene convertito in una
chiave di cifratura, secondo il formato richiesto da crank
2) il testo viene decifrato utilizzando la chiave ottenuta
3) per il testo decifrato vengono create tre tabella delle frequenze: una per
i singoli caratteri, una per i digrammi e una per i trigrammi
4) per ognuna delle tabelle create viene calcolato l'errore, cioe' la
"distanza" fra le frequenze calcolate e quelle presenti nelle tabelle di
riferimento
5) il valore della funzione obiettivo e' dato, nel caso piu' generale, da una
formula del tipo 1/(a*slft_err + b*bift_err + c*trift_err), dove a, b e c
sono dei pesi da associare ai tre errori
Notate che, secondo questi calcoli, il valore restituito dalla funzione
obiettivo non dipende solamente dall'alfabeto che si desidera valutare, ma
anche dallo stesso testo cifrato. I vari voti assegnati ai nostri cromosomi,
infatti, non seguono sempre una stessa scala, ma tendono a un valore diverso
a seconda del testo preso in esame: questo valore massimo dipende, secondo la
formula citata al punto 5, dall'errore fra le tabelle calcolate per il testo
(in chiaro!) e quelle di riferimento.
5.2.4 Riproduzione e mutazione
-----------------------------------------------------------------------------
Come accennato in precedenza, riproduzione e mutazione devono essere in grado
di conservare le proprieta' dei cromosomi: in particolare, per questo
problema esse devono garantire allo stesso tempo la presenza e l'unicita' di
tutte le lettere dell'alfabeto in ogni cromosoma.
Per fortuna esistono gia' operatori di questo tipo e, per di piu', sono gia'
implementati nelle GAlib: per quanto riguarda la riproduzione e' stato usato
il "PartialMatchCrossover", che implementa il Partially Mapped Crossover
(PMX), usato frequentemente in letteratura per risolvere il problema del
commesso viaggiatore (TSP). Per maggiori informazioni a proposito, potete
dare un'occhiata alla bibliografia (Bagnall, pagg. 105 e seguenti; tutorial
sul TSP su Coyote Gulch).
Il crossover, in pratica, viene applicato sotto forma di sequenza di
trasposizioni: quest'operazione, pur causando la perdita di parte del
patrimonio genetico, garantisce una perfetta compatibilita' dei cromosomi
con le specifiche iniziali, quindi risulta essere particolarmente adatta
alle nostre esigenze.
Per quanto riguarda la mutazione, invece, l'operatore scelto e' chiamato
SwapMutator: esso muta i cromosomi invertendo alcuni alleli (cioe', nel
nostro caso, alcune lettere dell'alfabeto cifrante) tra di loro. Anche qui
l'operatore e' in grado di conservare le proprieta' richieste.
5.2.5 Parametri
-----------------------------------------------------------------------------
Questo esempio e' caratterizzato da un numero di parametri decisamente
superiore rispetto agli altri, in quanto oltre alle caratteristiche tipiche
di ogni algoritmo genetico (dimensione della popolazione e probabilita' di
crossover e mutazione) esso presenta altre scelte relative alla dimensione
del testo da decifrare e alla tipologia di statistiche da applicare per il
calcolo della fitness. In particolare, le variabili prese in esame sono le
seguenti:
Dimensione della popolazione: la dimensione predefinita usata per la
popolazione e' di 25 elementi. Un aumento di questo parametro comporta una
maggiore probabilita' di trovare soluzioni buone, ma allo stesso tempo un
notevole aumento di carico sulla macchina (ricordate che per ogni elemento
della popolazione da valutare, cioe' per ogni alfabeto, e' necessario
decifrare il testo in esame). Nei test effettuati, il valore e' stato
mantenuto fra 25 e 50.
Probabilita' di crossover e di mutazione: i valori usati di default sono,
rispettivamente, 0.9 e 0.01. Attraverso alcuni esperimenti, pero', si e'
notato che tali valori _non_ vanno bene nella maggior parte dei casi: in
particolare, la percentuale di crossover dev'essere drasticamente diminuita
e quella di mutazione aumentata, per aiutare l'algoritmo a uscire da
situazioni di stasi (per maggiori dettagli, date un'occhiata alla prossima
sezione)
Numero di generazioni: a differenza dell'esempio precedente, in questo caso
non c'e' un punto preciso di arresto per l'algoritmo se non quello deciso
dal numero di generazioni trascorse. Infatti, lavorando con delle analisi
statistiche non avremo mai la completa certezza di aver ottenuto l'alfabeto
corretto; tuttavia possiamo supporre che, se le statistiche sono buone e
se lasciamo passare un numero sufficiente di generazioni, alla fine avremo
ottime probabilita' di trovare la soluzione giusta.
Oltre a questo, c'e' un altro particolare interessante da notare: per le
considerazioni fatte in precedenza a proposito del calcolo della fitness,
una volta trovata una chiave in grado di decifrare correttamente il testo
il valore della sua funzione obiettivo (relativo, in questo caso, al testo
in chiaro!) potra' essere usato come punto di riferimento per qualsiasi
altra cifratura dello stesso testo. Tale proprieta' si e' rivelata
particolarmente utile ed e' stata utilizzata per studiare tutti gli altri
parametri del GA.
Dimensione del testo: questo tipo di parametro ha un'importanza notevole nei
problemi di crittografia e, in particolare (come in questo caso), in tutti
quei problemi dove vengono effettuate delle analisi di tipo statistico sui
testi. Per gli esperimenti e' stato usato un testo, "Alice nel paese delle
meraviglie", nella versione inglese (anche le tabelle delle frequenze sono
state create per questa lingua), in quattro formati: la versione completa
(che ammonta a circa 150KB), una di circa 8KB, una da 3KB e una da 1KB.
Le conseguenze dirette del passaggio da un file all'altro sono di due tipi:
innanzitutto, riducendo il file l'operazione di valutazione dei cromosomi
risulta notevolmente velocizzata; tuttavia, minore e' la dimensione del
testo piu' e' probabile che le statistiche siano poco accurate.
Tipo di statistiche: come descritto nella sezione dedicata al calcolo della
fitness, il valore restituito dalla funzione obiettivo e' del tipo
1/(a*slft_err + b*bift_err + c*trift_err)
dove a, b e c sono dei pesi da assegnare alle tre tipologie di errore
(rispettivamente, sulle frequenze semplici, su quelle dei digrammi e su
quelle dei trigrammi). Scegliendo diversi valori per i pesi cambia il modo
stesso in cui viene valutato ogni singolo cromosoma e, di conseguenza,
anche il modo in cui puo' evolvere l'algoritmo genetico.
5.2.6 Test
-----------------------------------------------------------------------------
Date le dimensioni del problema e la quantita' di parametri che e' possibile
modificare, e' stato necessario eseguire alcuni test per capire quali valori
fossero piu' adatti per l'algoritmo. Soprattutto, i testi si sono dimostrati
indispensabili quando, dopo un momento di euforia iniziale ("L'algoritmo
riconosce perfettamente l'alfabeto in 9 secondi, con un testo di 3KB! IL
MONDO E' MIOOOOOH!"), ho deciso di cambiare cifratura ("Che e' questo? Dieci
minuti per ottenere un alfabeto sbagliato! NOOOooOOooOoH!").
Il problema principale, quando si fanno esperimenti di questo tipo, e'
proprio quello di fermarsi, entusiasti, ai primi successi, senza chiedersi
perche' e' andato tutto bene, ma soprattutto senza cercar di capire perche'
non e' andato tutto male. Nel mio caso, avevo scelto di cifrare il testo con
un alfabeto invertito: probabilmente, a livello statistico questo doveva
essere un caso cosi' particolare da risultare inequivocabilmente distante da
ogni altra soluzione, fatto sta che i risultati erano sempre molto buoni.
Appena cambiato l'alfabeto cifrante, le performance del mio GA sono calate
drasticamente. Com'era possibile? C'era qualche problema nell'algoritmo o era
solo un fatto di statistiche? Potevo migliorare i risultati lavorando solo
sui parametri?
Per dare una risposta alle mie domande, ho deciso di lavorare nel modo piu'
formale possibile: il piccolo sorgente d'esempio e' pian piano diventato un
programma pieno di parametri, al quale e' stato aggiunto uno script in perl
(finalmente son riuscito a usare il mio linguaggio preferito!) che si occupa
di ricevere i risultati del GA ed eseguire delle statistiche. I dati ottenuti
mi hanno mostrato che, effettivamente, l'alfabeto che avevo usato la prima
volta doveva essere un caso particolare, in quanto altri due alfabeti (uno
del tipo "cifratura di Cesare", ordinato ma traslato, l'altro piu' casuale)
mi davano risultati pessimi con i parametri di default:
=============================================================================
Statistiche per ps=25 mg=3000 pm=0.01 pc=0.90
+----------------------------+----------------------------------------------+
| Alfabeto cifrante | Statistiche (medie su 10 esecuzioni) |
+----------------------------+----------------------------------------------+
| zyxwvutsrqponmlkjihgfedcba | Score = 8.3881 Gen = 00870 Time = 015 |
| qrstuvwxyzabcdefghijklmnop | Score = 5.4116 Gen = 02650 Time = 042 |
| bqklhmnoepjcarstufvdgwxyzi | Score = 4.9567 Gen = 02530 Time = 040 |
+---------------------------------------------------------------------------+
Legenda: ps = population size | Score: punteggio medio
mg = max generations | (8.7647 = alfabeto giusto)
pm = probabilita' mutazione | Gen : numero medio di generazioni
pc = probabilita' crossover | Time : tempo medio di esecuzione
=============================================================================
Un aiuto fondamentale per le statistiche mi e' arrivato dalla possibilita' di
calcolare il valore massimo di score, come descritto nella sezione 5.2.3. Una
volta ottenuto tale valore, ho potuto usarlo come condizione di arresto per
l'algoritmo (del tipo "evolvi finche' non raggiungi "mg" generazioni, oppure
quando ottieni il risultato corretto) e come punto di riferimento per poter
valutare la bonta' dei parametri.
Ad esempio, come si puo' vedere da queste prime statistiche, mentre nel primo
caso il punteggio medio e' vicinissimo al massimo (9 esecuzioni su 10 hanno
dato il risultato corretto) negli altri due lo score e' piuttosto distante
(l'alfabeto cifrante e' stato ricavato correttamente solo un paio di volte).
Questo e' testimoniato anche dal numero medio di generazioni: piu' distante
e' tale valore dal numero massimo di generazioni (in questo caso 3000), piu'
volte e' stata trovata la soluzione corretta prima dello scadere del termine.
Il tempo medio di esecuzione, naturalmente, cambia di conseguenza.
A questo punto, lo script perl e' stato utilizzato per calcolare quali sono
i valori da assegnare ai parametri per ottenere un funzionamento ottimale del
GA. Innanzi tutto, per semplificare i calcoli, ho fatto alcune premesse:
- in seguito ad alcune prove, ho verificato che il testo da 8k riesce allo
stesso tempo a dare delle buone statistiche senza pesare quanto il testo
completo. Per velocizzare i tempi, ho adottato questo testo per tutte le
prove successive (riservandomi di ridurre la dimensione una volta trovati
i parametri ideali)
- vista la maggiore precisione delle statistiche sui trigrammi rispetto alle
altre, i parametri a, b e c per il calcolo della funzione obiettivo sono
stati cosi' valorizzati: a = 1; b = 10; c = 100. Altri esperimenti su
questi parametri vengono lasciati come esercizio al lettore (non posso mica
fare tutto io, neh!)
- per quanto riguarda la riproduzione, ho deciso di eseguire il test sui
valori da .10 a .90, con intervalli di .10; per la mutazione, invece, ho
scelto (almeno per ora) solo i valori .01, .02, .04 e .08.
- a livello operativo, l'idea finale (ancora non portata completamente a
termine, per problemi di tempo) sarebbe quella di trovare prima dei valori
ideali per mutazione e crossover, quindi riprovare il calcolo cambiando
i pesi sulla funzione obiettivo, infine fare esperimenti con testi piu'
brevi
5.2.7 Conclusioni
-----------------------------------------------------------------------------
Lo script perl per il calcolo delle statistiche e' stato eseguito a piu'
riprese, con diversi valori per la probabilita' di mutazione. Ad ogni
esecuzione, esso ha calcolato le medie (basate su 10 iterazioni del GA) per
i valori di probabilita' di riproduzione compresi fra .10 e .90. Quelli che
seguono sono i risultati (riassunti, per motivi di spazio) delle statistiche:
=============================================================================
Crossover, 8k, pm=.01:
pc=0.10 Score = 5.9233 Gen = 03490 Time = 019
pc=0.20 Score = 5.5103 Gen = 03810 Time = 025
pc=0.30 Score = 4.7135 Gen = 05000 Time = 039
pc=0.40 Score = 6.1204 Gen = 03360 Time = 036
pc=0.50 Score = 6.1799 Gen = 03820 Time = 042
pc=0.60 Score = 5.3577 Gen = 04130 Time = 049
pc=0.70 Score = 6.6841 Gen = 03040 Time = 040
pc=0.80 Score = 5.8982 Gen = 03460 Time = 050
pc=0.90 Score = 4.3998 Gen = 04690 Time = 073
Crossover, 8k, pm=.02:
pc=0.10 Score = 5.3664 Gen = 04020 Time = 033
pc=0.20 Score = 5.4816 Gen = 04590 Time = 047
pc=0.30 Score = 5.2435 Gen = 04120 Time = 052
pc=0.40 Score = 5.5112 Gen = 03790 Time = 052
pc=0.50 Score = 5.2509 Gen = 04310 Time = 070
pc=0.60 Score = 6.8206 Gen = 02650 Time = 041
pc=0.70 Score = 6.1954 Gen = 03300 Time = 047
pc=0.80 Score = 6.3126 Gen = 03500 Time = 054
pc=0.90 Score = 5.8709 Gen = 03500 Time = 072
Crossover, 8k, pm=.04:
pc=0.10 Score = 8.2838 Gen = 04270 Time = 093
pc=0.20 Score = 8.2750 Gen = 03700 Time = 064
pc=0.30 Score = 7.7113 Gen = 04210 Time = 078
pc=0.40 Score = 7.1503 Gen = 04720 Time = 090
pc=0.50 Score = 7.3446 Gen = 04260 Time = 084
pc=0.60 Score = 8.2651 Gen = 03290 Time = 057
pc=0.70 Score = 8.3013 Gen = 03780 Time = 067
pc=0.80 Score = 8.2838 Gen = 03830 Time = 069
pc=0.90 Score = 7.8258 Gen = 03350 Time = 062
Crossover, 8k, pm=.08:
pc=0.10 Score = 7.6579 Gen = 05000 Time = 099
pc=0.20 Score = 7.6699 Gen = 05000 Time = 107
pc=0.30 Score = 8.0769 Gen = 05000 Time = 108
pc=0.40 Score = 7.6927 Gen = 05000 Time = 112
pc=0.50 Score = 8.0569 Gen = 05000 Time = 093
pc=0.60 Score = 8.5181 Gen = 05000 Time = 092
pc=0.70 Score = 7.6528 Gen = 05000 Time = 090
pc=0.80 Score = 7.6830 Gen = 05000 Time = 090
pc=0.90 Score = 8.1118 Gen = 05000 Time = 091
=============================================================================
Ecco, ora, alcune delle conclusioni tratte dalle statistiche calcolate:
- non e' sufficiente avere uno score medio alto: valutando solo su questo
valore, l'ultimo gruppo di statistiche potrebbe sembrare il migliore,
tuttavia dando un'occhiata al numero medio di generazioni possiamo
verificare che non e' stata MAI raggiunta una soluzione ottima
- le probabilita' di riproduzione e di mutazione ideali (almeno a livello
statistico) sono, rispettivamente, di 0.6/0.7 e di 0.04. Per questi valori
l'algoritmo genetico ha ottenuto il risultato ottimo, decifrando in modo
corretto 9 volte su 10 il testo, anche se l'alfabeto cifrante era quello
che con i valori di default aveva generato lo score piu' basso
- anche se suonera' piuttosto ovvio, piu' basse sono le probabilita' di
crossover e di mutazione piu' veloce e' l'algoritmo
- se la riproduzione non e' al 100% affidabile, come in questo caso, puo'
tornare molto utile abbassarne la probabilita'
- la mutazione aiuta ad uscire dai blocchi, ma allontana anche dal massimo
globale: essa consente, in generale, di evolvere rapidamente all'inizio,
ma poi fatica a raggiungere l'ottimo. Considerazioni analoghe possono
essere fatte per una bassa probabilita' di riproduzione: dopo una veloce
convergenza iniziale, l'algoritmo rallenta e stenta a terminare
- per i testi piu' grossi, in linea di massima, si sono ottenuti risultati
discreti anche con una bassa percentuale di riproduzione (fino a 0.2),
mentre per quelli piu' piccoli e' stato necessario alzarla almeno al valore
di 0.4
- per quanto riguarda i pesi assegnati alla funzione obiettivo, si potrebbe
provare a farli evolvere a loro volta tramite un altro algoritmo genetico
(o addirittura, con una rete neurale, come descritto in "Pacman using
genetic algorithms and Neural Networks"). Una volta deciso se, in effetti,
le altre statistiche hanno senso di esistere o meno, si puo' eventualmente
scegliere di eliminarle e guadagnare in velocita'.
5.2.7 Codice sorgente
-----------------------------------------------------------------------------
#include <stdio.h>
#include <time.h>
// crank includes
#include "common_trigram.h"
#include "common_monoalphabetic.h"
#include "files.h"
// ga specific includes
#include <ga/ga.h>
#include <ga/GAStringGenome.h>
#include <ga/GAStringGenome.C>
// This is the declaration of the objective function
float objective(GAGenome &);
// Here we declare our own initializer
void AlphabetInitializer(GAGenome &);
double *slft_std; /* Standard unigram table */
double *bift_std; /* Standard bigram table */
double *trift_std; /* Standard trigram table */
char *text;
char k[(int)('Z'+1)];
int main (int argc, char *argv[]){
int popsize = 25;
int ngen = 1000;
float pcross = 0.9;
float pmut = 0.01;
// these are used by ngen=0
float score = 0;
int gennum = 0;
int genstep = 100;
int maxgen = 0;
for(int ii=1; ii<argc; ii++) {
if(strcmp(argv[ii],"ps") == 0) {
popsize = atoi(argv[++ii]);
}
if(strcmp(argv[ii],"ng") == 0) {
ngen = atoi(argv[++ii]);
}
if(strcmp(argv[ii],"pm") == 0) {
pmut = atof(argv[++ii]);
}
if(strcmp(argv[ii],"pc") == 0) {
pcross = atof(argv[++ii]);
}
if(strcmp(argv[ii],"mg") == 0) {
maxgen = atoi(argv[++ii]);
}
}
printf ("Running GA with the following parameters: ps=%02d ng=%04d mg=%04d
pm=%.2f pc=%.2f\n",popsize,ngen,maxgen,pmut,pcross);
int i;
time_t time1,time2;
time(&time1);
/* Load 3-gram tables */
slft_std = load_slft("slft.dat");
if (!slft_std) return 0;
bift_std = load_bift("bift.dat");
if (!bift_std) return 0;
trift_std = load_trift("trift.dat");
if (!trift_std) return 0;
/* Load ciphered file */
text = file_load_text ("zorxv.txt");
// Load parameters
GAParameterList params;
GASteadyStateGA::registerDefaultParameters(params); //We use GASteadyStateGA
params.set(gaNpopulationSize, popsize); // population size
params.set(gaNpCrossover, pcross); // probability of crossover
params.set(gaNpMutation, pmut); // probability of mutation
params.set(gaNnGenerations, ngen); // number of generations
params.parse(argc, argv, gaFalse);
// Create GAStringAlleleSet
GAStringAlleleSet alleles;
for(i=0; i<26; i++)
alleles.add('A'+i); // alleles are letters from A to Z
GAStringGenome genome(26, alleles, objective);
genome.initializer(AlphabetInitializer);
genome.mutator(GAStringSwapMutator);
GASteadyStateGA ga(genome);
ga.parameters(params);
ga.crossover(GAStringPartialMatchCrossover);
if (ngen!=0){
ga.evolve();
}else{
ga.initialize();
//while (score<1067){ // see Objective to understand these values
while (score<8.764){
for (int i=0;i<genstep;i++) ga.step();
score = ga.statistics().bestIndividual().score();
printf ("Generation: %04d Score: %04.04f\n",gennum,score);
gennum+=genstep;
if (maxgen && gennum>=maxgen) break;
}
}
printf ("Generations: %d ",gennum);
if (maxgen && gennum>=maxgen){
printf("- maxgen reached (%d), GA stoppeth",maxgen);
}
printf ("\n");
time(&time2);
genome = ga.statistics().bestIndividual();
cout << "the ga generated the following string (objective score is ";
cout << genome.score() << "):\n" << genome << "\n";
printf ("Total time: %d seconds\n",(int)(time2-time1));
printf ("%s\n",argv[0]);
return 0;
}
void genome2key (GAGenome & c, key *k){
// genome to key conversion, needed inside objective function
GAStringGenome & genome = (GAStringGenome &)c;
for(int i=0; i<genome.size(); i++){
(*k)['A'+i]=genome.gene(i);
}
}
float objective(GAGenome & c){
GAStringGenome & genome = (GAStringGenome &)c;
int len;
float score = 0;
double *slft, *bift, *trift;
double slft_err, bift_err, trift_err;
char *decoded_text;
char k[(int)('Z'+1)];
// convert the genome into a key
genome2key (genome,&k);
// apply the key to the text to generate a plaintext candidate
decoded_text = apply_key_text (&k,text);
// evaluate the candidate calculating frequency table
len = make_ft(decoded_text, &slft, &bift, &trift);
slft_err = slft_error (slft_std, slft);
bift_err = bift_error (bift_std, bift);
trift_err = trift_error (trift_std, trift);
free (decoded_text);
free (slft);
free (bift);
free (trift);
score = 1/(slft_err+10*bift_err+100*trift_err); // 8.764 is the max score
//score = 1/(trift_err); // 1067.21 is the max score for this formula
return score;
}
void AlphabetInitializer(GAGenome & c){
GAStringGenome &genome=(GAStringGenome &)c;
int i;
for(i=0; i<genome.size(); i++)
genome.gene(25-i, 'a'+i);
for(i=0; i<genome.size(); i++)
if(GARandomBit()) genome.swap(i, GARandomInt(0, genome.size()-1));
}
=============================================================================
# Da Perl Skreept!
#!/usr/bin/perl
my $it = 10; # number of iterations (the higher, the better the stats)
my $ng = 0; # number of generations (default 0 => reach the BEST genome)
my $pm = 0.01; # mutation prob: change to .02, .04, .08 for global stats
my $pc = 0.9; # crossover prob: not used now, because of the for cycle
my $mg = 5000; # max no. of generations (stop even if optimum is not found)
my $ps = 25; # popsize
my $score;
my $score_tot;
my $score_avg;
my $gener;
my $gener_tot;
my $gener_avg;
my $time;
my $time_tot;
my $time_avg;
my $string;
for ($pc = 0.1; $pc<=0.9 ; $pc+=.1){
$score_tot = 0;
$gener_tot = 0;
$time_tot = 0;
printf "Running GA %02d times with the following params: ps=%02d
ng=%04d mg=%04d pm=%.2f pc=%.2f\n", $it, $ps, $ng, $mg, $pm, $pc;
for ($ii=1;$ii<=$it;$ii++){
$result = `./prova ps $ps ng $ng mg $mg pm $pm pc $pc`;
if ($result =~ /objective score is (.*?)\)/){
$score = $1;
}
if ($result =~ /Generations: (\d+)/){
$gener = $1;
}
if ($result =~ /Total time: (\d+)/){
$time = $1;
}
if ($result =~ /:\n(.*?)\nTotal time/s){
$string = $1;
}
$score_tot += $score;
$gener_tot += $gener;
$time_tot += $time;
printf "Test %02d: ",$ii;
printf "Score = %.04f ",$score;
printf "Gen = %05d ", $gener;
printf "Time = %03d ", $time;
print "String = $string\n";
}
$score_avg = $score_tot / $it;
$gener_avg = $gener_tot / $it;
$time_avg = $time_tot / $it;
printf "Average: Score = %.04f Gen = %05d Time = %03d\n",
$score_avg, $gener_avg, $time_avg;
}
=============================================================================
6. Bibliografia
-----------------------------------------------------------------------------
== Generic papers about GAs ==
* http://www.ece.umd.edu/~adityak/Pacman.pdf
Pacman using genetic algorithms and Neural Networks
* http://citeseer.nj.nec.com/29471.html
Darrel Whitley: "A Genetic Algorithm Tutorial" [1993]
* http://www.coyotegulch.com/coyotica/GAIntro/genetic.html
An Introduction to Genetic Algorithms
* http://www.coyotegulch.com/reviews/Books/IntroGA.html
http://www.generation5.org/content/2000/ga_mitchell.asp
Melanie Mitchell: "An Introduction to Genetic Algorithms" reviews
== Generic papers about crypto ==
* http://www.pmf.ukim.edu.mk/~danilo
Prof. Danilo Gligoroski's web site
* http://www.schneier.com/paper-self-study.html
Self-Study Course in Block Cipher Cryptanalysis
* http://www.ioi.dk/Homepages/thomasj/publications/subst.ps
A Fast Method for the Cryptanalysis of Substitution Ciphers
* http://citeseer.nj.nec.com/ravi93statistical.html
Statistical Techniques for Language Recognition: An Introduction and Guide
for Cryptanalysts
* http://www.dean.usma.edu/math/pubs/cryptologia
Cryptologia
== Papers about GAs and crypto ==
* http://home.ecn.ab.ca/~jsavard/crypto/co040502.htm
Cryptanalysis, Almost by Aimlessly Thrashing About
* http://www.pmf.ukim.edu.mk/~danilo/ResearchPapers/Crypto/
/AttackPolyalphabeticSCOPES2003.pdf
Attack On the Polyalphabetic Substitution Cipher Using a Parallel Genetic
Algorithm
* http://citeseer.nj.nec.com/162166.html
The Cryptanalysis of a Three Rotor Machine Using a Genetic Algorithm
* http://citeseer.nj.nec.com/bagnall96applications.html
The Applications of Genetic Algorithms in Cryptanalysis
== GA libraries ==
* http://search.cpan.org/~aqumsieh/AI-Genetic-0.01/Genetic.pm
Perl - AI::Genetic
* http://galib.sourceforge.net/
GAlib: A C++ Library of Genetic Algorithm Components
== GA Websites ==
* http://www.generation5.org
Generation 5
* http://cypherpunks.venona.com/date/1995/11/msg00609.html
''Re: coding and nnet's'' thread
Finished! (20041229)
+mala __