================================================================================ ---------------------[ BFi14-dev - file 01 - 12/01/2004 ]----------------------- ================================================================================ -[ DiSCLAiMER ]----------------------------------------------------------------- Tutto il materiale contenuto in BFi ha fini esclusivamente informativi ed educativi. Gli autori di BFi non si riterranno in alcun modo responsabili per danni perpetrati a cose o persone causati dall'uso di codice, programmi, informazioni, tecniche contenuti all'interno della rivista. BFi e' libero e autonomo mezzo di espressione; come noi autori siamo liberi di scrivere BFi, tu sei libero di continuare a leggere oppure di fermarti qui. Pertanto, se ti ritieni offeso dai temi trattati e/o dal modo in cui lo sono, * interrompi immediatamente la lettura e cancella questi file dal tuo computer * . Proseguendo tu, lettore, ti assumi ogni genere di responsabilita` per l'uso che farai delle informazioni contenute in BFi. Si vieta il posting di BFi in newsgroup e la diffusione di *parti* della rivista: distribuite BFi nella sua forma integrale ed originale. -------------------------------------------------------------------------------- -[ CRACKiNG ]------------------------------------------------------------------- ---[ CRACKiNG C0DES WiTH GENETiC ALG0RiTHMS ]----------------------------------- -----[ +mala ]----------------------------------------------- ======================================================== 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 ============================================================================= Un ringraziamento particolare a Giulia: se e' vero che a molti ho promesso lavori che non son mai riuscito a portare a termine, l'entusiasmo con cui hai portato avanti la creazione di muflone mi ha convinto a far di tutto per non deluderti. Quindi: - se state leggendo questo articolo su BFi, sappiate che esso e' stato pubblicato in parallelo anche su http://quequero.org/store/various/muflone_1.zip muflone! Una zine nuova, che ho visto nascere e che spero di poter veder crescere tanto bene quanto promette ============================================================================= ============================================================================= 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 <> 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 piu' semplice ed intuitiva un algoritmo e' una sequenza ordinata di passi semplici che hanno lo scopo di portare a termine un compito piu' complesso (una ricetta da cucina, ad esempio, puo' 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 piu' 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, puo' proporre la propria conoscenza di tale fenomeno, oltre che con varie modalita' 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 e' causata nell'uomo dalla percezione del fenomeno che accade nel naturale, ma essendone l'effetto, non deve essere, ne' confusa, ne' identificata con la causa: un'entita' e' dunque il fenomeno, ed una diversa, anche se correlata, entita' e' la conoscenza del fenomeno) secondo una modalita' denominata MODELLO, che, secondo l'insegnamento galileiano, e' basata sulle proprieta' di: 1. FINITEZZA: la quantita' di conoscenza descritta dal modello e' finita, a differenza della poesia che puo' attivare illimitate personali interpretazioni nel lettore; 2. OGGETTIVITA': il significato che si da' alla descrizione della conoscenza espressa nel modello e' unico, non esistendo ambiguita' 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 e' 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 ----------------------------------------------------------------------------- <-| ga/nscekai.cpp |-> /* -------------------------------------------------------------------------- NSCEKAI Netscape Cache Explorer Genetic Keygen -------------------------------------------------------------------------- */ #include #include #include // we're going to use the simple GA #include // 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 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 ----------------------------------------------------------------------------- <-| ga/monoalfa.cpp |-> #include #include // crank includes #include "common_trigram.h" #include "common_monoalphabetic.h" #include "files.h" // ga specific includes #include #include #include // 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=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 <-| ga/stats.pl |-> # 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; } <-X-> ============================================================================= 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 ================================================================================ ------------------------------------[ EOF ]------------------------------------- ================================================================================