[MalaWiki] [TitleIndex] [WordIndex]

GaCrackIta

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)


2014-06-11 14:17