Monitoraggio di applicazioni software mediante modelli di Markov

Universita Degli Studi di Trieste

Facolta di Ingegneria

Dipartimento di Elettrotecnica, Elettronica ed Informatica

Tesi di Laurea in

Sistemi Operativi

Monitoraggio di applicazioni software

mediante modelli di Markov

Laureando :Riccardo CECOLIN

Relatore :Chiar.mo Prof. Enzo MUMOLO

Anno Accademico 2009-2010

Indice

1 Introduzione 7

1.1 Struttura della tesi . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Concetti preliminari 11

2.1 Prestazioni di un sistema di calcolo . . . . . . . . . . . . . . . 11

2.2 Tracce di indirizzi . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Parametrizzazione delle tracce . . . . . . . . . . . . . . . . . . 13

2.4 I Modelli di Markov Nascosti . . . . . . . . . . . . . . . . . . 16

3 Valgrind 19

3.1 Coregrind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2 Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.3 Cachegrind, analisi di un tool . . . . . . . . . . . . . . . . . . 21

3.4 Sviluppo di un Tool . . . . . . . . . . . . . . . . . . . . . . . 22

3.5 Modifiche a Coregrind . . . . . . . . . . . . . . . . . . . . . . 23

3.5.1 Wrapper interno . . . . . . . . . . . . . . . . . . . . . 24

3.5.2 Thread wrapper . . . . . . . . . . . . . . . . . . . . . 24

3.5.3 Thread injection . . . . . . . . . . . . . . . . . . . . . 25

3.5.4 External state . . . . . . . . . . . . . . . . . . . . . . 25

4 Spec 27

4.1 CPU2006 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.1.1 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . 27

4.1.2 Speed Ratio . . . . . . . . . . . . . . . . . . . . . . . . 28

4.1.3 Throughput Ratio . . . . . . . . . . . . . . . . . . . . 28

4.2 Misurazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.3 Configurazione . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.4 Esecuzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.5 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.5.1 401.bzip2 . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.5.2 445.gobmk . . . . . . . . . . . . . . . . . . . . . . . . 31

4.5.3 458.sjeng . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.5.4 403.gcc . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3

4.5.5 464.h264ref . . . . . . . . . . . . . . . . . . . . . . . . 32

4.5.6 400.perlbench . . . . . . . . . . . . . . . . . . . . . . . 32

4.5.7 429.mcf . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.5.8 462.libquantum . . . . . . . . . . . . . . . . . . . . . . 32

4.5.9 456.hmmer . . . . . . . . . . . . . . . . . . . . . . . . 33

4.5.10 471.omnetpp . . . . . . . . . . . . . . . . . . . . . . . 33

4.5.11 473.astar . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.5.12 483.xalancbmk . . . . . . . . . . . . . . . . . . . . . . 33

5 Analisi delle tracce di indirizzi 35

5.1 Addestramento hmm . . . . . . . . . . . . . . . . . . . . . . . 36

5.2 Test hmm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.3 Addestramento reti neurali . . . . . . . . . . . . . . . . . . . 38

5.4 Test reti neurali . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.5 Analisi offline . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.5.1 Hmm . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.5.2 Reti neurali . . . . . . . . . . . . . . . . . . . . . . . . 40

5.6 Analisi con Valgrind . . . . . . . . . . . . . . . . . . . . . . . 40

5.6.1 Tracehmm . . . . . . . . . . . . . . . . . . . . . . . . . 41

6 Risultati sperimentali 45

6.1 Risultati test offline . . . . . . . . . . . . . . . . . . . . . . . 46

6.1.1 Test di verifica hmm . . . . . . . . . . . . . . . . . . . 46

6.1.2 Test di verifica reti neurali . . . . . . . . . . . . . . . . 47

6.2 Analisi su Valgrind . . . . . . . . . . . . . . . . . . . . . . . . 48

6.2.1 Test di verifica . . . . . . . . . . . . . . . . . . . . . . 50

6.2.2 Test di classificazione . . . . . . . . . . . . . . . . . . 50

7 Applicazioni 63

7.1 Monitoraggio e sicurezza . . . . . . . . . . . . . . . . . . . . . 63

7.1.1 Whitelist . . . . . . . . . . . . . . . . . . . . . . . . . 63

7.1.2 Blacklist . . . . . . . . . . . . . . . . . . . . . . . . . . 64

7.2 Allocazione di risorse . . . . . . . . . . . . . . . . . . . . . . . 64

7.2.1 Sistemi operativi . . . . . . . . . . . . . . . . . . . . . 64

7.2.2 Ambienti di virtualizzazione . . . . . . . . . . . . . . . 64

7.3 Implementazione . . . . . . . . . . . . . . . . . . . . . . . . . 65

7.3.1 User space . . . . . . . . . . . . . . . . . . . . . . . . . 65

7.3.2 Kernel space . . . . . . . . . . . . . . . . . . . . . . . 66

7.3.3 Virtualizzazione . . . . . . . . . . . . . . . . . . . . . 66

8 Conclusione 69

4

A Documentazione tools offline 71A.1 train, test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71A.2 genset zero, genset one, ntrain, ntest . . . . . . . . . . . . . . 72

B Documentazione tools Valgrind 73B.1 tracebin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73B.2 tracehmm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5

Capitolo 1

Introduzione

Il problema principale affrontato in questa tesi e quello della classificazionedei processi in esecuzione su un calcolatore. Piu precisamente usando misureeffettuate sul processo in esecuzione, nel nostro caso gli indirizzi virtuali diaccesso in memoria, sono stati addestrati dei modelli statistici di tipo Marko-viano che descrivono il processo e che consentono di riconoscerlo durante lasua esecuzione.

Il problema affrontato si inquadra nel campo generale della Modellazionedel carico di lavoro (Workload Modeling) che e un argomente trattato nellaIngegneria del Software. Lo scopo del Workload Modeling e quello di forniredegli strumenti che portino a migliorare le prestazioni dei sistemi di calcolo.Ad esempio, se si riesce a riconoscere che una applicazione in esecuzionerichiedera determinate risorse, si puo agevolare l’esecuzione preallocando lerisorse richieste.

La motivazione di questo lavoro e sia quella di definire degli algoritmi peroperare classificazioni dei processi in esecuzione, sia quella di realizzare delleoperazioni di tuning del sistema adattandolo ai carichi di lavoro usualmentesopportati. Un ulteriore obiettivo e quello di implementare delle metodologiedi adattamento dinamico al workload in esecuzione, ottimizzando i sistemipur conservandone la flessibilita. L’approccio adottato e quello di model-lare la sequenza di indirizzi virtuali con un Modello di Markov Nascostoopportunamente adattato all’impiego.

Una branca dell’Ingegneria del Software si occupa di questo tipo dianalisi: accanto agli sforzi per progettare un software che ben si adattaa una specifica architettura hardware si possono aggiungere quelli per pro-gettare una certa architettura ottimizzata rispetto ai compiti che questa sarachiamata a svolgere durante il suo impiego.

Accanto a questo livello di progetto si affianca poi un livello diretta-mente superiore che consiste nel progetto del nucleo del S.O. che permetteradi gestire efficacemente questi carichi di lavoro: gestione dell’I/O su dis-co, gestione delle risorse di memoria, gestione delle sincronizzazione IPC,

7

gestione del networking, ecc.

Ecco quindi nascere la necessita di sapere il tipo di carichi in gioco ela possibilita di modellare questi workload con degli strumenti che ci per-mettono poi di implementare schemi di design e tuning del sistema hard-ware/software che materialmente eseguira il compito richiesto.

Un altro obiettivo dell’Ingegneria del Software a cui ci si avvicina par-lando di classificazione di workload e quello della misura delle prestazioni diuna CPU. Anche in questo senso le aspettative sono ampie: identificazionedi aree di sviluppo e incremento di prestazioni, monitoraggio di richieste dirisorse, identificazione di colli di bottiglia del software.

Il problema

La classificazione dei workload non e un’operazione semplice perche presup-pone di poter accedere a informazioni sul processo che spesso non possiamoreperire senza turbare l’esecuzione stessa del processo. Sviluppare degli stru-menti software che monitorizzano alcuni parametri di esecuzione di work-load puo essere molto difficile, fermo restando sempre il pericolo di falsare lamisura che si sta operando. L’idea quindi e di usare delle metriche di misurache non turbino l’esecuzione e che possano essere facilmente elaborate, suc-cessivamente, per un’analisi e uno studio a posteriori. A questo scopo unametodologia che sembra opportuna e quella di estrarre delle informazioni sutipo e quantita di richiesta di risorse di memoria durante l’esecuzione di unprocesso, cioe quella di estrarre da un processo in esecuzione la sequenzadegli indirizzi virtuali, che possono costituire tracce di indirizzi. Questeinformazioni possono essere memorizzate su memorie di massa e rese dipubblico dominio, come fatto da diverse organizzazioni come il PerformanceEvaluation Laboratory della Brigham Young University.

L’obiettivo

Un obiettivo di questa tesi e quello di verificare se la sequenza degli indirizzivirtuali puo essere utilizzata per classificare un processo in esecuzione e conche accuratezza. Se la classificazione e possibile, vogliono esaminare duestrade: una e quella di classificare un processo e l’altra e quella di verificareil processo, cioe di verificare che un processo sia quello che dichiara di essere.

L’approccio seguito e stato quello di supporre che i workload possanoessere descritti da un punto di vista statistico come processi di Markov.Si sono quindi usate librerie che realizzano Modelli di Markov di tipo dis-creto che ci hanno permesso di operare delle classificazioni considerando ilworkload nel suo complesso. In accordo con i lavori [1], [2] e [3], abbiamopensato di analizzare metriche di memoria per individuare le tipologie localidei workload.

8

1.1 Struttura della tesi

I capitoli si articolano nel modo seguente:

Capitolo 2 Prestazioni di un sistema di calcolo in particolare in riferimentoagli accessi in memoria.

Capitolo 3 Struttura di Valgrind, framework di instrumentazione per losviluppo di strumenti di analisi dinamica.

Capitolo 4 Analisi di SPEC CPU2006, suite di benchmark standard pervalutare processore, memoria e compilatore di un sistema.

Capitolo 5 Analisi, classificazione e verifica delle tracce di indirizzi e doc-umentazione dei tool sviluppati.

Capitolo 6 Presentazione e discussione dei piu importanti risultati sper-imentali conseguiti nella classificazione di tracce di processi e nellaclassificazione di workload.

Capitolo 7 Applicazioni pratiche del tool sviluppato e possibili modalitadi messa in atto in sistemi in stato di produzione.

Capitolo 8 Considerazioni finali che riassumono il lavoro svolto.

9

Capitolo 2

Concetti preliminari

2.1 Prestazioni di un sistema di calcolo

La performance di un sistema si puo definire come la capacita del sistemadi eseguire un compito, o workload, in relazione a determinati parametri.La performance puo essere valutata in termini misurabili utilizzando diversemetodologie: in relazione al tempo impiegato per completare un determinatoprocesso, ai watt consumati, al tempo di risposta. Gli obiettivi di unamisurazione possono essere di rilevare differenze nel sistema prima e dopodelle modifiche o di confrontare il sistema con altri.

Per poter avere dei risultati comparabili tra architetture diverse cheeseguono software differente sono stati sviluppati dei benchmarks, i qualiforniscono un dato misurabile ed oggettivo delle capacita di un macchina.I benchmark piu diffusi sono SPEC sviluppato da Standard PerformanceEvaluation Corporation e ConsumerMark sviluppato da EEMBC, Em-bedded Microprocessor Benchmark Consortium. Ogni benchmark fornisceun workload in modo deterministico che quindi puo essere utilizzato per mis-urare la capacita di calcolo intero, floating point, di input/output, di bandadi accesso alla memoria del sistema in esame. I benchmark valutano l’ese-cuzione di questo workload con un numero che puo quindi essere rapportatoad altri sistemi/architetture.

Un fattore significativo per la misura e la caratterizzazione di un work-load e dato dalla sequenza di indirizzi corrispondenti agli accessi in memoria[4]. Questo valore puo essere utilizzato per calcolare la frequenza di misssulle memorie cache del sistema o per misurare la localita spaziale delleistruzioni o dei dati. In Fig. 2.1 e riportata l’analisi di cache miss rate didati e istruzioni di un processo (bzip2) in diversi momenti della sua ese-cuzione. Su una macchina moderna, un cache L1 miss puo significare 10cicli di cpu persi, un cache L2 miss fino a 200. Un cache profiling adeguatopuo rivelarsi estremamente utile per capire come ottimizzare l’esecuzione diun’applicazione. Una configurazione tipica attuale e data da una cache di

11

livello 1 con istruzioni e dati separati (I1, D1) e una cache di livello 2 unifi-cata (I2 + D2). Per ottenere dati dettagliati sui rapporti miss/request delle

Figura 2.1: Cache miss rate durante una esecuzione di bzip2

memorie cache si fa uso di simulatori, i quali propongono un modello di ger-archia di memoria il piu simile possibile a quello delle architetture reali cosıda fornire dei dati attendibili per risolvere problemi di performance dovu-ti agli accessi alla memoria. I simulatori di memoria cache leggono comeinput tracce di indirizzi, ovvero dei file contenenti la sequenza di indirizzicorrispondenti accessi in memoria effettuati durante l’esecuzione.

2.2 Tracce di indirizzi

Le tracce posso essere sia file di testo ascii sia binari, tipicamente oltreagli indirizzi sono riportate anche delle informazioni ulteriori riguardantiogni singolo accesso in memoria: dimensione in byte dell’accesso, modalitalettura/scrittura... Un formato comunemente utilizzato e quello prodottodal tool lackey presente nel framework Valgrind, che genera tracce ascii nelformato qui commentato:

I 0023C790,2 # instruction read all’indirizzo 0x0023C790

S BE80199C,4 # data store di 4 byte all’indirizzo 0xBE80199C

L BE801950,4 # data load di 4 byte all’indirizzo 0xBE801950

M 0025747C,1 # data modify di 1 byte all’indirizzo 0x0025747C

In lackey lettura e scrittura di una stessa locazione in modo consecutivo sonoriportate come data modify. Altri formati di tracce sono quelli definiti dal

12

simulatore di memorie cache dinero, che prevede sia formati ascii simili aquello di lackey sia un formato binario che permette di risparmiare spaziosu disco, importante in quanto le tracce possono raggiungere dimensioninotevoli. Questi formati sono, in caso di sistema a 32bit:

traditional compatibile anche con dineroIII, e un formato ascii definitoC AAAAAAAA con C modalita di accesso e i campi A per l’indirizzo.

2 04000850

2 04000852

1 be8f1f4c

extended include anche informazioni sulla dimensione in byte dell’accessoalla memoria, C AAAAAAAA SS con SS dimensione in byte dell’accesso

i 04000850 2

i 04000852 5

r bec3446c 4

i 04000a90 1

w bec34468 4

binary vengono memorizzati 8 byte per accesso, AAAASSCP

AAAA indirizzo

SS dimensione dell’accesso

C modalita (read,write,instruction fetch-0,1,2)

P byte di padding

Nel caso delle tracce ascii per la conversione da un formato all’altro e statosviluppato uno script sed:

#!/usr/bin/sed

/^=/d

s/,[0-9]\+$//

s/^I\s/2/

s/^\sS/1/

s/^\sL/0/

s/\sM\s$[0-9a-f]*$/0 \1\n1 \1/

2.3 Parametrizzazione delle tracce

Dalle tracce di accessi in memoria devono essere rimosse le informazioniridondanti ed estratti i tratti principali, riducendo la quantita di dati daprocessare. Comportamenti sequenziali o ciclici nell’esecuzione sono di fatto

13

inclusi nel dominio spettrale della traccia, quindi si puo operare una com-pressione in questo dominio mantenendo le informazioni piu significative. Icicli per esempio introducono picchi nello spettro mentre una sequenza diindirizzi lineare produrra una componente continua. Si vogliono utilizzarequindi strumenti di analisi dei segnali per elabolare la sequenza di indirizzi.

Figura 2.2: Spettrogramma di una sequenza di indirizzi contenente cicliannidati

La sequenza di indirizzi e tempo variante, per cui si utilizza un’analisispettrale a breve termine. Nella fase di apprendimento gli indirizzi ver-ranno divisi in segmenti di lunghezza limitata sui quali verra applicata latrasformata discreta del coseno. La DCT e una operazione comunementeutilizzata nella trasformazione dei segnali, utile per ridurre la ridondanza inquanto distribuisce piu energia possibile nei primi coefficienti. Calcolata laDCT su un certo numero di segmenti vengono presi i primi coefficienti dellaDCT di ogni segmento e su di essi applicata la quantizzazione vettoriale.Il procedimento di quantizzazione vettoriale suddivide lo spazio in settoriad ognuno dei quale associa un vettore centroide, ogni vettore viene quindiassociato al centroide piu vicino ottenendo un insieme di indici relativi aicentroidi. Tali indici sono utilizzati come input per HMM.

Utilizzare solo i primi valori della DCT ha l’effetto di approssimare i pic-chi della sequenza originale pur mantenendone il comportamento generale.

14

Figura 2.3: La sequenza di vettori di indirizzi viene trasformata in unasequenza di vettori n-dimensionali

Figura 2.4: Viene applicata la quantizzazione vettoriale per trovare icentroidi e di ogni vettore calcolato il centroide piu vicino

15

2.4 I Modelli di Markov Nascosti

Una catena markoviana a tempo discreto e una sequenza aleatoria qn taleche la variabile successiva dipende solamente dalla variabile precedente. Ilsistema puo essere quindi descritto da una sequenza di stati, che corrispon-dono a degli eventi osservabili. Ad ogni istante del tempo discreto il sistemapassa da uno stato all’altro con una certa probabilita di transizione.

Figura 2.5: Modello di Markov nascosto

Lo stato attuale qn riassume quindi la storia del sistema per prevederel’elemento successivo qn+1.

Una catena di Markov e un modello troppo restrittivo per poter essereapplicato al problema di interesse. Il modello puo essere esteso al caso incui le osservazioni siano una funzione probabilistica dello stato e quindi nonosservabili direttamente. Le osservazioni sono cioe nascoste. Un modello diMarkov nascosto e caratterizzato da:

• il numero di stati N , con l’insieme degli stati S = S1, .., SN e con qt lostato al tempo t

• il numero di simboli osservati M , ovvero la dimensione dell’alfabetodiscreto. Indichiamo l’insieme dei simboli con V = V1, ..., VM

• la matrice di transizione tra stati A = [aij ] dove

aij = P [qt+1 = Sj |qt = Si] 1 ≤ i, j ≤ N

e la probabilita di passare dallo stato Si allo stato Sj .

• la distribuzione delle osservazioni nello stato j: bj(k), dove

bj(K) = P [Vk|qt = Sj ] 1 ≤ j ≤ N 1 ≤ k ≤M

e la probabilita di osservare il simbolo Vk se all’istante t il sistema sitrova nello stato j.

16

• il vettore delle probabilita iniziali π, dove

πj = P [q1 = Sj 1 ≤ j ≤ N

e la probabilita che il sistema si trovi all’istante iniziale nello stato Sj

Si puo quindi indicare un modello di Markov nascosto con λ = (A,B, π).Il processo di apprendimento di un modello di Markov implica la ricerca

dei parametri (A,B, π) tali da massimizzare la probabilita di riconoscere lasequenza di osservazioni. Poiche non si conosce una soluzione analitica chetrovi un massimo assoluto si utilizza una procedura iterativa. L’algoritmodi Baum-Welch in [5] fa questo in modo efficiente utilizzando soltanto lasequenza di simboli emessi come dati di addestramento. La parte nascostadi un hmm, cioe la sequenza di stati, non puo essere scoperta, ma puo essereinterpretata in qualche modo significativo. L’algoritmo di Viterbi in [6]permette di generare la sequenza piu probabile di stati relativi ad un datomodello hmm. Inoltre avendo una sequenza di simboli l’algoritmo di Viterbirende possibile verificarne l’affinita con un modello hmm una calcolandonela probabilita.

17

Capitolo 3

Valgrind

Piu i sistemi hardware e software crescono in complessita piu si rivelanonecessari sistemi per verificarne la correttezza. Per migliorare qualita erobustezza dei programmi possono essere utilizzati dei tool di analisi o in-strumentazione. Questi tool effettuano diversi tipi di operazioni per deter-minare informazioni di interesse relative ai programmi. Gli approcci utiliz-zati si possono suddividere in analisi statica e dinamica, analisi dei sorgentio dell’eseguibile binario.

Si definisce analisi dinamica di un software l’analisi di questi mentre e inesecuzione su un processore reale o virtuale, a differenza dell’analisi staticache si propone di verificare eventuali proprieta del software analizzandonel’object-code compilato o il codice sorgente, senza eseguire il software. I tooldi instrumentazione dinamica permettono di analizzare il 100% del codiceche viene eseguito in user mode senza richiedere accesso al codice sorgentema seguendo soltanto un flusso di esecuzione. I tool di analisi statica per-mettono di seguire tutte le diramazioni del codice ma non hanno accessoallo stato dell’applicazione in esecuzione. I due approcci si possono ritenerecomplementari.

I parametri ottenuti dai tool di analisi dinamica riguardano spesso laquantita memoria utilizzata in varie fasi di esecuzione, le chiamate alle fun-zioni di allocazione/rilascio, errori di scrittura/lettura nei buffer allocati,race conditions nel caso di programmi multithreaded... Tali tool possonoanche dare accesso allo spazio di indirizzamento del processo e ai registridella cpu.

Quando un tool di analisi permette di intervallare il proprio codice conquello dell’eseguibile analizzato allora esso si puo definire tool di instrumen-tazione. Per accedere alla traccia di indirizzi generata da un’applicazione edelaborarla per poter addestrare HMM con essa si e reso necessario l’utilizzoun tool di instrumentazione dinamica.

Valgrind e un framework di instrumentazione sul quale e possibile svilup-pare tool di analisi dinamica[7]. Valgrind viene distribuito con un insieme

19

di tool gia predisposti per le operazioni piu comuni di instrumentazione,quali gestione di memoria, threading... Il framework offre inoltre un’inter-faccia per poter sviluppare altri tool a seconda dell’esigenza. La natura opensource del framework, distribuito sotto licenza GNU GPLv2, permette an-che di modificare i tool esistenti o perfino il codice sorgente del frameworkstesso, coregrind.

3.1 Coregrind

Il framework e progettato [8] per non richiedere una nuova compilazione olinking delle applicazioni che deve eseguire, permette di analizzare eseguibiligia esistenti. Passando come parametro a Valgrind il nome dell’eseguibileda lanciare questo viene caricato in memoria insieme alle librerie ad essoassociate. Le istruzioni del programma vengono tradotte in un linguaggioRISC-like indipendente dall’architettura, chiamato VEX IR, per essere poieseguite su una cpu virtuale.

Ogni istruzione tradotta viene passata ad il tool in esecuzione (sceltocome parametro da linea di comando), il quale aggiunge il proprio codicedi instrumentazione, per poi essere simulata. VEX IR e piu simile alla rap-presentazione del codice com’e organizzata internamente in un compilatoreche ad un linguaggio assemblativo. Le istruzioni VEX sono organizzate inblocchi IRSB che possono contenere da 1 a 50 istruzioni. I blocchi hannoun solo punto di ingresso ma e possibile che l’esecuzione esca dal blocco dapiu di un punto.

I programmi multi-threaded sono supportati ma l’esecuzione di questi eserializzata con un sistema di semafori in modo tale che soltanto un threadvenga eseguito simultaneamente dal core di Valgrind. Lo scheduling deithread viene effettuato dal sistema operativo.

3.2 Tools

I tools presenti nella distribuzione ufficiale di Valgrind sono 10: Memcheck,Cachegrind, Callgrind, Helgrind, DRD, Massif, DHAT, Ptrcheck, BBV,Lackey. Memcheck, Massif e DHAT sono tool relativi all’utilizzo della memo-ria dinamica: Memcheck rileva errori nell’accesso alla memoria allocata,mentre Massif e DHAT effettuano analisi sull’utilizzo di questa.

Sempre collegato agli accessi in memoria e strettamente orientato all’ot-timizzazione della performance delle applicazioni e Cachegrind: un simu-latore di memoria cache che analizzando gli accessi effettuati dal programmaclient riporta informazioni utili per la sua ottimizzazione.

20

3.3 Cachegrind, analisi di un tool

L’implementazione di Cachegrind [9] prevede l’aggiunta di codice di instru-mentazione ad ogni accesso in memoria per aggiornare il simulatore di cacheinterno. Ogni istruzione prima di essere eseguita e tradotta in un linguag-gio RISC intermedio e passata al tool, che controlla se fa riferimenti allamemoria (load/store) o se e un’istruzione di fetch: in caso positivo la passaal simulatore.

Il modello di memoria implementato in Cachegrind e configurabile inalcuni aspetti, fisso in altri. Sono configurabili dimensione totale, dimensionedei blocchi (linee) e associativita. Il numero e tipo delle memorie invece nonlo e, sono presenti due memorie cache L1 indipendenti, una per le istruzionee una per i dati: Li1, Ld1 e una cache L2 condivisa. Caratteristiche:

• Rimpiazzamento LRU

• Write-allocate (una miss in scrittura su un dato lo porta in cache L1)

• Cache L2 inclusiva

• Bit selection hash table

Limiti:

• Fa uso di indirizzi virtuali, diversi da quelli che verrebbero inseriti nellacache realmente

• Le syscall non vengono tracciate, quindi i riferimenti effettuati inmodalita kernel non hanno effetto

• Gli altri processi in esecuzione non hanno effetto sulla cache simulata

Le opzioni per l’inizializzazione della memoria cache simulata devono esserepassate da linea di comando:

valgrind --tool=cachegrind [options] ./program

--I1=<size>,<associativity>,<line size>

--D1=<size>,<associativity>,<line size>

--L2=<size>,<associativity>,<line size>

--cache-sim=no|yes [yes]

--branch-sim=no|yes [no]

--cachegrind-out-file=<file>

Cachegrind presenta anche una funzionalita che analizza il numero di branchpredette correttamente dalla cpu, il flag -branch-sim=yes attiva questa fun-zionalita. Ogni esecuzione di Valgrind produce un file di output, controllatoda -cachegrind-out-file, di default nella forma cachegrind.out.%p con

21

%p pid del processo avviato. Questo file puo essere poi utilizzato da degliscripts (es. cg_annotate) per produrre statistiche piu dettagliate.

Il simulatore produce in output numero di reference, miss e miss-rate delfetch di istruzioni, della lettura di dati e della scrittura di dati per entrambii livelli di cache. Per ulteriori analisi e possibile fare uso di due script dis-tribuiti assieme a cachegrind: cg_merge e cg_annotate. cg_merge permettedi generare i risultati complessivi di esecuzioni multiple della stessa appli-cazione combinando diversi file di log cachegrind.out. cg_annotate analizzain modo molto approfondito i file di log e produce percentuali di cache missrelative ad ogni file, ad ogni funzione o ad ogni singola linea di codice (sel’eseguibile include informazioni di debugging).

3.4 Sviluppo di un Tool

L’architettura del framework prevede una netta distinzione tra Coregrind ei tool. Coregrind fornisce il supporto all’infrastruttura di instrumentazione,traduzione delle istruzioni, gestione della memoria, scheduling lasciando al-cune operazioni indefinite sotto forma di prototipi di funzioni, che devonoessere implementate nei singoli tool. Coregrind fornisce anche altri serviziai tool che verranno descritti in seguito.

I tool vengono compilati insieme a Coregrind per generare un nuovoeseguibile che viene selezionato dal parametro -tool all’avvio di Valgrind.Le funzioni necessarie perche il tool possa essere compilato correttamentesono:

pre_clo_init() E’ disponibile per inizializzare le strutture di memoria in-terne del tool. E’ possibile inoltre dichiarare a quali eventi dell’ese-cuzione il tool e interessato e registraci delle callback:track_pre_thread_ll_create, track_new_mem_stack ...

post_clo_init() Questa funzione viene chiamata dopo che e stato effet-tuato il parsing dei parametri passati da linea di comando per filtrarequelli relativi a coregrind. Va qui effettuato il parsing delle opzionirelative al tool ed e possibile procede ulteriormente con le operazionidi inizializzazione.

instrument() Ogni volta che l’esecuzione entra in un nuovo blocco vienechiamata instrument() con il blocco come input. Questa funzione hail compito di interpolare le istruzioni con il codice di instrumentazione(chiamate a funzioni del tool) e ritornare un nuovo blocco. Per ilfatto che i blocchi hanno diversi punti d’uscita non e assicurato chetutte le istruzioni del blocco vengano eseguite, per questo il codice diinstrumentazione va bufferizzato nel blocco d’uscita insieme ad esse enon eseguita direttamente in instrument().

22

fini() Stampa dei risultati e rilascio delle risorse. E’ possibile accede ancheall’exit code del programma client.

Il framework mette a disposizione anche altri strumenti per analizzare ilcodice in esecuzione, se si ha la possibilita di ricompilare l’applicazione di puofare uso di client requests, per comunicare direttamente col tool tramitemacro inserite nel codice sorgente del client. Utili soprattutto per il debug-ging, il framework ne propone alcune e ogni tool ne implementa di proprie.Alcuni esempi:

RUNNING_ON_VALGRIND Ritorna 1 se l’applicazione viene eseguita all’internodi Valgrind, 0 se su una vera CPU. Utile ad esempio per creare deisalti condizionali ed omettere alcune parti dell’esecuzione che rallen-terebbero troppo l’esecuzione simulata.

VALGRIND_PRINTF(format, ...) Stampa un messaggio formattato sul filedi log di Valgrind insieme ai messaggi del tool.

VALGRIND_PRINTF_BACKTRACE(format, ...) Stampa lo stato corrente del-la stack

VALGRIND_COUNT_ERRORS Ritorna il numero di errori rilevati finora dal tool

E’ possibile implementare le proprie client request, modificando il codicedei tool e quindi possibile far comunicare le proprie applicazioni con ilframework.

Un’altra funzionalita prevista e quella di effettuare function wrappingdi funzioni di libreria per analizzarne parametri passati e valori di ritorno.E’ presente un sistema di pattern per intercettare gruppi di funzioni connome simile (il nome a cui fare riferimento e quello interno generato dalcompilatore). La funzione di wrapping

I_WRAP_SONAME_FNNAME_ZZ(libpthreadZdsoZd0, pthreadZucreateZAZa)

intercettera quindi le chiamate a tutte le funzioni che corrispondono al pat-tern pthread_create@* nella libreria libpthread.so.0, quindi di tuttele versione delle glibc (pthread_create@GLIBC_2.3, ...@GLIBC_2.4). Lefunzioni di wrapping possono poi chiamare l’originale con le macro

VALGRIND_GET_ORIG_FN(fn);

CALL_FN_W_WW(result, fn, x,y);

3.5 Modifiche a Coregrind

L’utilizzo di Valgrind per l’addestramento di HMM richiede la possibilitadi eseguire la stessa applicazione client sotto il tool di instrumentazione

23

diverse volte variando i parametri di input. E’ stata analizzata la strut-tura interna di Coregrind e sono state individuate le fasi principali del suoavvio per selezionare quelle candidate ad essere modificate per ottenere talefunzionalita.

3.5.1 Wrapper interno

La prima soluzione sviluppata consiste in un wrapper scritto in POSIX C.E’ stata modificata le funzione main_process_cmd_line_options affinchericonoscesse l’opzione -wrap=<yes|no>. Se il parametro viene posto a yesil valore della stringa VG_(args_the_exename), che si riferisce all’eseguibileda lanciare, viene artificialmente posto al nome del wrapper. Valgrind loesegue passandogli gli argomenti da variare ed esso sostituisce il simbolo(arbitrariamente posto a con l’argomento variabile (nel caso di gzip conil nome del file da comprimere), quindi effettua una fork ed si sostituisce(execvep) con l’eseguibile client. Il processo padre chiamando wait attendeche il figlio completi l’esecuzione (per non sovrappore l’output dei due) erientra nel ciclo.

Il vantaggio di questo sistema e che e completamente trasparente per ilclient, esso non necessita di ricompilazione e la modifica rispetta l’architet-tura di Valgrind. Lo svantaggio principale e che l’uso di fork/execve im-plica la reinizializzazione del tool ad ogni esecuzione del programma client.Non e quindi possibile mantenere un determinato stato del tool in memoriatra un’esecuzione e l’altra (in particolare e la chiamata a execve che causail problema, Valgrind la gestisce semplicemente sostituendosi con un altroprocesso di Valgrind e non ricaricando un nuovo eseguibile).Il wrapper e stato inserito nel sistema di build di Valgrind e pertanto auto-maticamente compilato ed installato insieme al resto dei sorgenti.

3.5.2 Thread wrapper

La seconda soluzione e mirata a risolvere il problema sorto nella prima:mantenere uno stato tra le varie esecuzioni. Il sorgente del client andramodificato in modo tale da essere eseguito come funzione in un thread: ilwrapper gestisce delle struct contenti gli argomenti da passare ai diversithread e li esegue sequenzialmente, aspettando che uno finisca prima dilanciare il successivo. Questo viene fatto in quanto i thread condividendo lospazio di indirizzamento potrebbero entrare in conflitto su eventuali variabiliglobali.

Per l’implementazione e stata usata la libreria pthread ed e stato con-statato che risolve i problemi della prima ma comporta un notevole svantag-gio obbligando a modificare e ricompilare il client, seppur minimamente. Lafunzione main del wrapper e da compilare assieme al client. Il programmaclient dovra essere modificato per accettare come parametro un puntatore

24

ad una struttura contentente argc, argv ed envp e dovra terminare la suaesecuzione chiamando pthread_exit anziche exit.

3.5.3 Thread injection

Per trovare una soluzione che mantesse lo stato interno del tool tra le varieesecuzioni e che non richiedesse modifiche al client e stata fatta un’analisiapprofondita del sistema di thread e dello scheduler di coregrind, il frame-work sul quale si basano i tool di Valgrind. Seguendo il flow dell’esecuzionedi Valgrind sono stati effettuati diversi test prima per ripetere l’esecuzionedi un thread gia concluso e poi per duplicarlo artificialmente, senza che essoavesse chiamato clone.

L’implementazione di questo motodo e risultata possibile, ed e statoindividuato nella funzione run_thread_for_a_while il punto ideale per ef-fettuare l’inserimento del thread artificiale, in quanto il piu vicino all’ese-cuzione delle istruzioni sulla cpu virtuale di Valgrind. Tale funzione (inscheduler.c) e stata modificata affinche anteponesse alla prima istruzionedel client un chiamata a ML_(do_fork_clone). Con questa Valgrind duplicail thread che stava eseguendo in quel momento (che non condividera perolo spazio di indirizzamento). Sono state effettuate con successo multipleesecuzioni con una singola inizializzazione del tool scelto (ma con multiplefinalizzazioni). Il passo successivo e stato sostituirla con la chiamata ad unafunzione ancora piu interna di coregrind, do_clone.

Questa modifica ha permesso di avere piu thread eseguiti sequenzial-mente (Valgrind permette il multithreading ma esegue sempre un threadalla volta) con una sola inizializzazione e una sola finalizzazione del tool scel-to. Tuttavia non rispetta l’architettura originale del framework e potrebbeportare ad instabilita, necessita quindi un maggiore approfondimento primadi essere utilizzata con sicurezza.

3.5.4 External state

Se il progetto prevede invece lo sviluppo di un nuovo tool da zero la soluzioneottimale si rivela quella di salvare lo stato del tool in un file copiandovile strutture di memoria come si trovano al momento della chiamata allafunzione fini() e ripristinarle all’esecuzione successiva. I tool di Valgrindnon sono pero linkati alla libreria c standard quindi e necessario usare laversione reimplementata nel framework di tutte le funzioni di IO, definitenegli headers della directory include/ dei sorgenti.

25

Capitolo 4

Spec

Spec 2006 si presenta come lo standard per la misura e la valutazione delleprestazioni di un sistema. L’utilizzo di un set di benchmark standard rendepossibile la comparazione dei risultati tra macchine, compilatori e opzionidi compilazione differenti tra loro.

4.1 CPU2006

Spec CPU2006 si concentra sulla performance del processore, sull’architet-tura della memoria e sulla capacita del compilatore di produrre codice ot-timizzato [10]. Altri fattori che spesso incidono sulle performance delle ap-plicazioni (networking, I/O) sono qui considerati trascurabili, in quanto isingoli benchmark sono stati sviluppati per ottenere il maggiore impattopossibile sulla cpu e sulla memoria rispetto al resto delle componenti delsistema. Spec si compone di due suite di benchmark principali:

• CINT2006

• CFP2006

La prima effettua un’analisi delle performance del sistema nelle operazionisu valori interi, la seconda nel caso di operazioni a virgola mobile (floatingpoint). Ognuna delle due suite di compone di diversi benchmark (12 perCINT2006, 17 per CFP2006).

4.1.1 Benchmark

Un benchmark di SpecCPU2006 non e altro che un’applicazione che effet-tua una serie di operazioni ben definite che hanno l’effetto di aumentare ilcarico di lavoro della cpu. Dei benchmark di SpecCPU2006 si misura speed,ovvero quanto rapidamente l’esecuzione viene completata, e throughput,quanti flussi di esecuzione si riescono a completare per unita di tempo.

27

4.1.2 Speed Ratio

Lo standard di SpecCPU2006 definisce come ratio il rapporto tra il tempodi esecuzione di un benchmark sulla macchina e un tempo di riferimento de-terminato da Spec. E’ con questo valore che e possibile mettere in relazioneil proprio risultato con risultati ottenuti su sistemi differenti.

4.1.3 Throughput Ratio

Vengono eseguite multiple (n) istanze del benchmark contemporaneamente.Il valore di throughput corrisponde al rapporto tra il tempo impiegato percompletare l’esecuzione di tutte le istanze ed n. Il throughput ratio equindi il rapporto tra il throughput della macchina e il valore di riferimentodi Spec.

4.2 Misurazioni

La suite CINT2006 puo essere eseguita in quattro modalita differenti:

SPECint2006 La media geometrica ottenuta su 12 ratio, normalizzati su3 esecuzioni ognuno. Benchmark compilati in modalita peak.

I 12 benchmark vengono eseguiti 3 volte, calcolandone ilvalore di speed ratio. Delle 3 esecuzioni di ogni benchmarkviene presa la mediana e utilizzata per calcolare la mediageometrica sui 12: G =

√r0r1 · · · r11. La media geometri-

ca G viene utilizzata come risultato del test. I benchmarksono utilizzati in modalita peak: per ognuno di essi possonoessere specificati flag di compilazione personalizzati cosı daottimizzarne l’esecuzione.

SPECint base2006 La media geometrica ottenuta su 12 ratio, normaliz-zati su 3 esecuzioni ognuno. Benchmark compilati in modalita base.

Il valore di G viene calcolato allo stesso di SPECint2006,ma i benchmark vengono utilizzati in modalita base: i flagdi compilazione devono essere uniformi tra tutti e 12. Lamodalita base e piu restrittiva della modalita peak.

SPECint base2006 La media geometrica del valore di throughput ratiodell’esecuzione dei 12 benchmark in madalita peak.

SPECint base2006 La media geometrica del valore di throughput ratiodell’esecuzione dei 12 benchmark in modalita base.

Allo stesso modo di CINT2006, anche CFP2006 prevede quattro modal-ita di esecuzione differenti:

28

SPECfp2006 La media geometrica ottenuta su 17 ratio, normalizzati su 3esecuzioni ognuno. Benchmark compilati in modalita peak.

SPECfp base2006 La media geometrica ottenuta su 17 ratio, normalizzatisu 3 esecuzioni ognuno. Benchmark compilati in modalita base.

SPECfp rate2006 La media geometrica del valore di throughput ratiodell’esecuzione dei 17 benchmark in madalita peak.

SPECfp rate base2006 La media geometrica del valore di throughputratio dell’esecuzione dei 17 benchmark in madalita base.

4.3 Configurazione

Per eseguire SpecCPU2006 e necessario scrivere un file di configurazione rel-ativo al proprio sistema. Le opzioni di configurazione si possono dividerein opzioni relative alla compilazione ed esecuzione dei singoli benchmark erelative all’output e ai report che genera la suite. E’ quindi necessario speci-ficare il path dei compilatori C, C++, Fortran, flag di compilazione comunia tutti i benchmark e opzionalmente anche flags personalizzati per ogni sin-golo benchmark (utilizzati per le misurazioni peak). Per poter pubblicareil report dell’esecuzione della suite e necessario descrivere in modo partico-lareggiato hardware e software sulla quale e stata eseguita: architettura, n◦

di cpu, n◦ di core per cpu, quantita di memoria disponibile, motherboard,sistema operativo, versione dei compilatori... Si possono anche definire lepreferenze per quanto riguarda l’output dei risultati, se html, pdf, ascii.Un altro requisito affiche i proprio risultati siano marcati come reportablee produrre il file flags.xml, dove va commentata ogni opzione passata alcompilatore.

4.4 Esecuzione

Per compilare ed eseguire i benchmark si utilizza runspec. Il procedi-mento da effettuare per testare se l’installazione e la configurazione del-la suite e andata a buone file e source ./shrc per settare le variabilid’ambiente, quindi runspec -config=example.cfg -fakereportable -F

flags-simple.xml -size=ref -tune=base int e nella directory result

verra generato il report. Runspec prende come argomento uno o piu bench-mark da eseguire (int, fp, all). Le principali opzioni che regolano l’esecuzionedel tool sono:

-action Definisce l’azione da compiere: build compila i benchmark, runcompila(se necessario) ed esegue. clean rimuove file temporanei edeseguibili compilati.

29

-rate Se non presente il tool procede in modalita speed run. Se presente(argomento n) esegue n benchmark in parallelo, il test sara quindi untest di throughput

-tune Settabile a base, peak o all. Default base.

-reportable Per generare un report valido

Le seguenti opzioni sono utili per effettuare dei test su un singolo benchmarko in modalita particolari ma non permettono di generare un report valido:

-size Dimensioni del set di input, test, train o ref (reference). Reference eil set piu ampio, con il quale l’esecuzione dura piu a lungo

-iterations Numero di volte che ogni benchmark va eseguito. Obbligato-riamente a 3 nel caso di reportable runs.

4.5 Benchmarks

SpecCPU2006 si prefigge di calcolare le prestazioni di un sistema simulandoun workload il piu verosimile possibile, per questo molte dei benchmark sonodelle versioni adattate e modificate di applicazioni reali. Tali applicazionihanno in comune un’elevata intensita computazionale: la maggior parte deltempo speso da esse e dedicato ad operazioni di calcolo, con pochissimooverhead causato da input/output. Sono state apportate delle modifiche aisorgenti affiche i test eseguano la gran parte delle operazioni di IO in memo-ria e non su file, e affiche la memoria utilizzata rimanga inferiore ad 1GB perevitare che il sistema debba effettuare swap verso il disco. Le applicazionisono state scelte basandosi anche su criteri di portabilita, in quanto Spec-CPU2006 puo essere compilato su una moltitudine di architetture e sistemioperativi differenti.

4.5.1 401.bzip2

401.bzip2 e la versione adattata a SpecCPU2006 del programma bzip2, ilquale effettua compressione dati. 401.bzip2 si basa sulla versione 1.0.3di bzip2 di Julian Seward, con la differenza che 401.bzip2 non effettuaoperazioni di I/O se non nella lettura dei file da comprimere. Tutta lacompressione e la decompressione avviene quindi in memoria.

I file utilizzati per la compressione e decompressione sono:

chicken.jpg JPEG image data, 638K

liberty.jpg JPEG image data, 283K

input.source POSIX tar archive, contenente il codice sorgente di perl-5.8.5, 50M

30

text.html HTML document text, 130K

input.program Mach-O executable ppc, 7.7M

input.combined file composto da alcune parti molto comprimibili e altremeno, 52M. Si e rivelato essere la combinazione dei file precedenti (leimmagini JPEG, il sorgente di perl e il file html)

Ogni file viene compresso e decompresso 3 volte, a fattore crescente: 5, 7 e 9.I risultati della decompressione sono poi confrontati con il set di input pervalidare la buona riuscita del test. 401.bzip inizializza in memoria 3 bufferdi dimensione adeguata ad ospitare il file di input, lo stream compresso e lostream decompresso. Dopo aver caricato il file, le successive operazioni dilettura e scrittura sono effettuate tutte in memoria senza snaturare il codicedi bzip2 tramite le define:

./bzlib.h:98: #define read(a,b,c) spec_read(a,b,c)

./bzlib.h:104: #define write(a,b,c) spec_write(a,b,c)

spec_read e spec_write non sono altro che wrapper di memcpy che gestis-cono gli EOF e che fanno corrispondere ai file descriptor i buffer preceden-temente allocati.

4.5.2 445.gobmk

445.gobmk e una versione di GNU Go alla quale vengono presentate diverseposizioni di gioco. Il gioco del Go e considerato un problema di intelligen-za artificiale che richiede uno sforzo computazionale elevato in quanto lecombinazioni possibili di pezzi sulla scacchiera (goban) nella partita sonomoltissime.

I file di input utilizzati benchmark sono file di testo che descrivono diverseposizioni di gioco, l’output corrisponde nella mossa successiva da effettuare.

4.5.3 458.sjeng

458.sjeng e una versione leggermente modificata di Sjeng 11.2, un program-ma che gioca a scacchi ed analizza e valuta posizioni di gioco. La versioneproposta da Spec rende le ricerche nell’albero delle varianti delle mosse deter-ministiche e quindi il workload del test sempre uguale. L’input di riferimentodel test e composto da 9 differenti posizioni di gioco e dalla profondita allaquale vanno analizzate da Sjeng.

4.5.4 403.gcc

403.gcc e basato sulla versione 3.2 di GNU gcc, configurato per generarecodice assembly x86-64 per un processore AMD Opteron con diverse flag di

31

ottimizzazione abilitate. 403.gcc e stato adattato da Spec alterando l’euris-tica nelle scelte di utilizzare funzioni inline affinche il programma spendessepiu tempo nell’analisi del codice sorgente e utilizzasse piu memoria dellaversione standard. L’input e dato da file sorgente per i quali deve esseregenerato l’assembly corrispondente.

4.5.5 464.h264ref

464.h264ref e l’implementazione di Karsten Suhring dello standard di com-pressione video H.264/AVC. Le modifiche introdotte dal team di Spec facil-itano la portabilita del codice ma sono state ridotte al minimo per garantireche il test si avvicinasse il piu possibile ad un caso d’uso reale di video en-coding. In particolare, e stata rimossa la parte dei sorgenti riguardante ildecoder (il test effettua solo la compressione in h264, non la decompressione)ed e stato soppresso l’output a file di log per minimizzare l’I/O. L’input ecomposto da due video in formato raw ognuno dei quali viene compresso condue profili differenti (good compression e best compression).

4.5.6 400.perlbench

400.perlbench e Perl v5.8.7 al quale sono state rimosse tutte le feature rel-ative ai singoli sistemi operativi. A questi sono stati aggiunti alcuni moduliesterni: SpamAssassin, MailTools, Digest-MD5, HTMLParser... I modulivengono utilizzati per la manipolazione di messaggi email trasformandoli inpagine html, calcolandone checksum md5 e rilevando con che probabilita sitratta di spam.

4.5.7 429.mcf

429.mcf deriva da un software di scheduling del traffico utilizzato in ambitopubblico. 429.mcf genera un elevato carico sulla cpu eseguendo un algoritmoche implementa il metodo del simplesso su rete. Il codice del programmaoriginale e stato modificato per ridurre il numero di cache miss e quindi incre-mentare l’impatto sulla cpu rispetto alla memoria. Questo e stato ottenutomodificando l’ordine degli elementi persenti nelle struct maggiormente uti-lizzate dal benchmark. L’input al benchmark consiste in un file di testocontente un insieme di percorsi da ottimizzare.

4.5.8 462.libquantum

462.libquantum simula un computer quantistico, eseguendo l’algoritmo difattorizzazione di Peter Shor. Il benchmark si aspetta in input un numeroe resituisce l’elenco dei suoi fattori. Su un computer quantistico l’algorit-mo trova i fattori con margine d’errore arbitrariamente piccolo in tempopolinomiale rispetto alla dimensione del numero in input.

32

4.5.9 456.hmmer

456.hmmer utilizza algoritmo hmm per analizzare sequenze di dna. In inputil benchmark si aspetta un file database contente i modelli di riferimento euna sequenza nella quale effetuare la ricerca delle sequenze del database.

4.5.10 471.omnetpp

471.omnetpp simula una vasta rete ethernet basandosi sul sistema di simu-lazione discreto OMNeT++. OMNeT++ implementa completamente CS-MA/CD, i frame ethernet e IP per una simulazione del carico sulle reti. Ilbenchmark simula una rete contente circa 8000 computer e 900 tra switchese hubs suddivisi in diverse subnet. Il benchmark prende in input la topologiadi una rete e la configurazione degli host, e procede aumentando esponenzial-mente il volume di traffico simulando anche perdite di pacchetti. In ouputsono prodotte statistiche dettagliate sulla simulazione.

4.5.11 473.astar

473.astar deriva da una libreria di ricerca del percorso minimo utilizzataper le intelligenze artificiali nei videogames. In input accetta una mappa informato binario e il tipo di algoritmi da applicare per poi stampare le viepossibili per il raggiungimento della destinazione.

4.5.12 483.xalancbmk

483.xalancbmk deriva da Xalan-C++, un software che processa documentiXML trasformandoli secondo fogli di stile XSL. Implementa lo standardW3C delle XSL Transformations e di XML. Per renderlo un benchmark diSpec e stato selezionato un test-set da processare di notevole dimensioni(100MB) consistente in un file XML e un foglio di stile XSL da trasformarein HTML.

33

Capitolo 5

Analisi delle tracce diindirizzi

L’obiettivo dell’analisi consiste nel riuscire ad riconoscere a che program-ma corrisponde un processo sconosciuto in esecuzione utilizzando soltantola sequenza di indirizzi di memoria a cui accede. Si vuole testare l’efficaciadi apprendimento di hmm (modelli di Markov) e delle reti neurali nel ri-conoscere tratti caratteristici dello spettro delle tracce. Per poter utilizzaretali algoritmi di machine learning e necessario trasformare la sequenza di in-dirizzi in una forma accettabile dai modelli, procedendo inizialmente con unacompressione della stessa: la traccia viene suddivisa in segmenti e di questiviene calcolata la trasformata del coseno. I primi parametri della traformatavengono presi come vettore rappresentante il segmento. Tali vettori vengonoquindi quantizzati tramite un algoritmo di k-means clustering per ottenereuna sequenza di chiavi appartenenti ad un alfabeto e quindi ad un dominiodiscreto. E’ con queste sequenze di chiavi che vengono addestrati i modellidi Markov e le reti neurali.

Per la fase di analisi sono stati utilizzati come programmi i 12 benchmarkSPECint, i quali possono generare un numero ancora piu elevato di possibiliprocessi in quanto ogni benchmark ha associati piu possibili input, fino a 8nel caso di gcc. Sono stati sviluppati due gruppi di tool per effettuare laclassificazione delle tracce, uno dei quali utilizza modelli di Markov e l’altroreti neurali addestrate tramite back-propagation. Per ognuno di essi sonopresenti tool di addestramento, tool di test e un vasto insieme di script perautomatizzare il processo di analisi. I tool sono stati sviluppati interamentein C mentre lo scripting e stato effettuato in Ruby. Come piattaforma disviluppo e test e stato scelto un sistema Debian GNU/Linux.

35

5.1 Addestramento hmm

Partendo da una traccia di indirizzi generata dall’esecuzione di un bench-mark si vuole ottenere il modello hmm corrispondente a tale workload. E’stato sviluppato un tool in ansi C che effettua la parametrizzazione spettraledi un segmento della traccia e genera un nuovo modello hmm.

Definita V la dimensione del vettore di indirizzi sui quali applicare laDCT, la trasformata discreta del coseno, e N il numero di vettori scelti perla finestra di questa fase dell’addestramento, sono individuati sulla tracciasul disco V N vettori. Di ognuno di questi viene calcolata la DCT e nevengono salvati i primi Cs elementi. Nel tool la DCT e stata implementatain C utilizzando come riferimento i paramentri di scala proposti in GNUOctave [11].

Figura 5.1: I modelli hmm vengono addestrati utilizzando l’algoritmo diBaum-Welch su sequenze di centroidi

Il procedimento descritto comporta una compressione dei dati disponi-bili, avendo ora in memoria N vettori di dimensione Cs si vuole discretizzarequesto insieme utilizzando un algoritmo di k-means clustering. L’imple-mentazione nel tool e stata effettuata utilizzando come base algoritmica unsorgente ansi C sviluppato da Henrik Gruden, Gabriele Cutazzo, CristianoVanon, Enzo Mumolo. Tale sorgente e stato esteso e adattato per poter allo-care tutte le strutture dati dinamicamente e gestire input e ouput bufferizzatiin memoria. L’algoritmo produce in output un insieme di Cn centroidi chefaranno parte del modello hmm e percio devono essere memorizzati su disco.Per i centroidi e stato definito un formato di output binario. Ogni elementodell’insieme di N vettori generati precedentemente puo ora essere associato

36

ad un centroide: si procede quindi con una ulteriore compressione da Nvettori di Cs elementi a N interi appartenenti all’alfabeto di Cn centroidi.

Ora che si e ottenuta una sequenza di numeri interi e possibile pro-cedere con l’addestramento di una hmm discreta di S stati: e stata utiliz-zata la libreria sviluppata da Tapas Kanungo [12] che applica l’algoritmodi BaumWelch per trovare la matrice degli stati della hmm. Tale libreria(open source) e stata modificata per effettuare tutto il lavoro in memoriasenza richiedere input da file, affinche tutto il procedimento dalla sequen-za di indirizzi fino al completamento dell’addestramento potesse avveniresenza effettuare I/O su disco e affinche fosse possibile definire la dimen-sione di tutte le strutture dati da linea di comando o comunque runtime enon a tempo di compilazione, per ottenere la massima flessibilita nei testsuccessivi.

5.2 Test hmm

Con i file del modello hmm e dei centroidi e possibile testare una tracciaqualsiasi: il procedimento di parametrizzazione spettrale e lo stesso ma icentroidi in questo caso non verranno calcolati ma caricati e verra applicatol’algoritmo di Viterbi, il quale produce in output una probabilita: la prob-abilita che la sequenza di indirizzi della traccia in ingresso appartenga a talemodello hmm. Per mantere l’integrita tra il tool di addestramento e quellodi test essi sono stati sviluppati come un unico sorgente che viene compilatoin modi differenti a seconda dei flag passati al compilatore da GNU make.

Figura 5.2: Viene calcolata la probabilita di appartenenza di una traccia adun modello con l’algoritmo di Viterbi utilizzando centroidi e modello hmm

37

5.3 Addestramento reti neurali

Come algoritmo di machine learning comparativo per i modelli di Markovnascosti sono state scelte le reti neurali [13]. Una rete neurale simula ilcomportamento dei neuroni biologici per ottenere un effetto di memoria ericonoscere pattern e similarita tra gli input assegnati. Le reti utilizzate inquesto caso si compongono di diversi neuroni organizzati in strati, con glistrati completamente connessi tra loro, ovvero ogni neurone di un determi-nato strato e connesso con tutti i neuroni dello strato precedente i qualifungono da input. Ogni connessione tra i neuroni ha un peso. Ogni neuronecalcola il proprio valore di output effettuando la somma pesata di tutte leconnessioni in input ed applicando a questa somma una funzione di soglia,tipicamente la sigmoide f(x) = 1

1+e−x .

Figura 5.3: Viene utilizzata la sequenza di centroidi come input per la rete

Una rete di architettura cosı definita e determinata quindi univocamentedai valori dei pesi. Sono stati utilizzati 3 strati: input layer, hidden layer, eoutput layer. E’ stato fatto uso di apprendimento supervisionato, ovvero adogni esempio per il quale si vuole addestrare la rete e associato anche l’outputdesiderato. Per tutto il codice relativo alle reti non si e fatto affidamentoa librerie presenti in letteratura, e stato implementato ex-novo utilizzandol’algoritmo di back-propagation dell’errore per effettuare l’aggiornamentodei pesi.

Per poter effettuare una comparazione tra il modello di apprendimentohmm e le reti neurali nel caso della classificazione di tracce di indirizzi e statoutilizzato lo stesso procedimento di parametrizzazione spettrale. Ottenutala sequenza di N interi questi sono riportati in forma binaria su log2Cn bitognuno, cosı che ogni bit 0, 1 diventi un input per il primo strato di neuroni.

38

Tali input vengono utilizzati in gruppi di mlog2Cn come esempi di un set diapprendimento per la rete reurale. Il set di apprendimento viene generatosovrapponendo un esempio di mlog2Cn input col successivo in diversi modiper addestrare la rete alla sequenza di simboli.

5.4 Test reti neurali

Per il test di una rete viene selezionato un punto casuale della traccia dalquale far partire la lettura degli indirizzi, ottenuto un set di N interi quantiz-zando i vettori risultato della dct questi vengono riportati in forma binariaallo stesso modo della fase di addestramento e mappati sugli input della rete.L’output della rete e dato da un valore reale compreso tra [0, 1].

5.5 Analisi offline

L’analisi offline prevede di analizzare una traccia di indirizzi pre-generataleggendola dal disco. Per generare le tracce e stata sviluppata un’estensionedi Valgrind, tracebin, che genera le tracce in formato binario. Il formatodel file e definito dalle chiamate a VG_(write) presenti in tracebin:

VG_(write)(fd_bin,&addr,sizeof(Addr));

VG_(write)(fd_bin,&ss,sizeof(UShort));

VG_(write)(fd_bin,&op,sizeof(Char));

VG_(write)(fd_bin,&padding,sizeof(Char));

Sono registrati indirizzo, dimensione in byte e modalita di accesso. L’ottavobyte e di padding ed e sempre 0xFF.

Sono state quindi generate due tracce per ogni benchmark con diversiinput scelti tra quelli previsti da SPECint. Per la prima fase di analisi sonostati utilizzati 4 diversi benchmark, 2 tracce per ognuno di essi variandonel’input tra la prima e la seconda esecuzione. I benchmark utilizzati conrelativi input e dimensione delle tracce sono:

400.perlbench checkspam (37GB), diffmail (40GB)

401.bzip2 chicken.jpg (55GB), text.html (45GB)

403.gcc 166.i (58GB), 200.i (51GB)

445.gobmk nntgs.tst (31GB), score2.tst (32GB)

5.5.1 Hmm

Sono stati sviluppati due programmi che effettuano addestramento e testdelle tracce. Il primo produce come output due file caratterizzanti il modelloaddestrato (relativi a centroidi ed hmm), il secondo applica l’algoritmo di

39

Viterbi e stampa un valore floating point corrispondente alla probabilita chela traccia processata corrisponda al modello addestrato. I due programmisono configurabili tramite le seguenti opzioni:

./train [options] <tracefile>

./test [options] -C [centroids file] -H [hmm file] <tracefile>

-w <int> numero di blocchi di indirizzi da processare, def 1000

-d <int> numero di indirizzi per blocco, default 1024

-v <int> dimensione dei vettori da quantizzare, default 16

-c <int> numero di centroidi, default 64

-n <int> numero di stati della hmm, default 12

-s <int> offset dal quale iniziare l’analisi, default 0

-D <string> output directory, default "/tmp"

5.5.2 Reti neurali

Per le reti neurali sono stati sviluppati 3 programmi: un programma segueil processo di parametrizzazione precedentemente spiegato per generare undue training set: uno generato dalla traccia di riferimento e un set generatoda altre tracce scelte casualmente. Un secondo programma effettua l’ap-prendimento addestrando la rete per riconoscere con output vicino a 1.0 iltraining set generato dalla traccia di riferimento e con output vicino a 0il training set generato dalle altre tracce. Un programma ancora diversoeffettua il test prendendo un segmento da una traccia definita da linea dicomando.

Separando in diversi tool il lavoro e stato possibile parallelizzare gli stepdei procedimenti ed effettuare addestramenti di reti con diversi parametri apartire dallo stesso training set.

5.6 Analisi con Valgrind

L’analisi offline comporta uno svantaggio ineludibile, l’accesso al disco: perprocessare diversi GB di traccia occorre molto tempo. Effettuare l’analisi di-rettamente all’interno di Valgrind mentre il programma e in esecuzione per-metterebbe di evitare di dover generare, memorizzare e leggere i file traccia.E’ stato sviluppato quindi un tool per Valgrind che applica la parametriz-zazione spettrale ed esegue apprendimento e test di hmm utilizzando diret-tamente gli indirizzi di memoria via via che vengono generati dai benchmark.A tale tool e stato dato il nome di tracehmm ed e stato inserito nel sistemadi compilazione di Valgrind assieme agli altri tool della distribuzione.

Il porting all’interno del framework dei tool sviluppati per l’analisi of-fline non puo essere effettuato direttamente in quanto sia i tool sia coregrindnon possono utilizzare alcuna libreria utilizzata anche dal client, nemmeno

40

glibc. Per quanto riguarda la libreria standard e stato necessario riscri-vere tutte le chiamate di scrittura/lettura da file e di allocazione e copiadella memoria affinche utilizzassero il sottinsieme di funzioni libc reimple-mentate all’interno del framework appositamente per questo scopo. Inoltrenon essendo possibile utilizzare nemmeno la libreria matematica sono stateselezionate le funzioni necessarie per l’analisi (cos,sqrt,log) ed inserite inmodo indipendente dalla libm insieme ai sorgenti del tool. Per verificare chel’importazione fosse stata effettuata correttamente e stata anche effettuatauna comparazione dei risultati con quelli ottenuti eseguendo le istruzioniSSE2 non portabili fcos,fsqrt,fyl2x come assembly inline. Anche l’ar-chitettura dei tool precedenti e stata cambiata per rispettare la strutturainterna di Valgrind, che non offre l’accesso ad un flusso di istruzioni linearema prevede che venga inserito codice di instrumentazione in tutti i blocchi diistruzioni tradotti, i quali verranno eseguiti solo se l’esecuzione raggiungeraquel particolare punto.

5.6.1 Tracehmm

Il tool sviluppato presenta un’interfaccia completamente configurabile daopzioni da linea di comando:

usage: valgrind --tool=tracehmm [options] prog-and-args

--new=<model.hmm> train a new hmm model

--resume=<model.hmm> resume training

--test=<model.hmm> test hmm model

--centroids=<model.ct> centroids file

--skip=<int> memory blocks to skip

--window=<int> window size

--verbose=yes|no verbose [yes]

--vverbose=yes|no very verbose [no]

--ct-n=<int> num of centroids

--st-n=<int> num of statuses

Con esso e possibile effettuare sia l’apprendimento di un nuovo modello siacaricare un modello precedentemente generato e riprendere l’addestramen-to. Questa seconda funzionalita si rivela utile per addestrare un modellogenerico di un benchmark indipendente dall’input assegnatogli inizialmente,effettuando diversi cicli di addestramento variando l’input assegnato.

Durante l’esecuzione di un programma ogni volta che si entra in un nuovoblocco di istruzioni questo viene tradotto in VEX IR con il quale coregrindchiama la funzione th_instrument del tool. Questa funzione ha il com-pito di manipolare il blocco di istruzioni aggiungendo il proprio codice diinstrumentazione nella forma tipicamente di chiamate a funzioni C e di ri-tornare un nuovo blocco. In questa fase sarebbe anche possibile rimuovereo modificare istruzioni esistenti.

41

Figura 5.4: Struttura di tracehmm

Tracehmm riconosce le istruzioni che effettuano accessi in memoria eprepone ad ognuna di esse nel blocco di istruzioni che ritornera a coregrinduna chiamata alla funzione th_addresshandler con il meta-indirizzo del-l’istruzione interessata come parametro.Non e possibile registrare gli indirizzi in questo momento dell’instrumen-tazione in quanto non sono ancora indirizzi ma meta-indirizzi, questo percheil blocco che e stato analizzato ne ha un flusso di esecuzione lineare (single-entry, multiple-exit) ne e assicurato che venga eseguito soltanto una volta:Valgrind effettua il caching della traduzione dei blocchi. I meta-indirizzicontengono quindi informazioni su come ottenere l’indirizzo dell’accesso inmemoria e non l’indirizzo stesso: quando il blocco verra eseguito coregrindtrovera le chiamate a th_addresshandler, generera l’indirizzo reale e lafunzione cosı chiamata potra aggiungere l’indirizzo al suo buffer. Per le in-struction fetch e piu semplice in quanto basta passare a th_addresshandler

il valore del program counter.th_addresshandler per prima cosa controlla pero di aver rispettato l’offsetindicato dall’opzione -skip=offset: i primi offset · buffersize indirizzivengono scartati come richiesto dall’utente. Quindi un vettore di indirizziviene gradualmente riempito fino a raggiungere la dimensione stabilita perquale iniziare l’analisi: effettuare la DCT del vettore e salvarne i risultati.Questo viene ripetuto per un numero di volte definito da -window perche poi

42

venga chiamata th_action_NORETURN() (e stata rispettata la convenzioneinterna a Valgrind per i nomi delle funzioni) e l’analisi prosegua allo stessomodo dei tool offline.

43

Capitolo 6

Risultati sperimentali

Il procedimento di analisi delle tracce e stato suddiviso in due parti: analisioffline e analisi in Valgrind. Nel primo caso e stato analizzato un insiemedi 4 benchmark, nel secondo e stato possibile effettuare prove sull’insiemecompleto dei 12 benchmark di SPECint. I 4 benchmark del primo insiemedi test sono stati scelti in base ad un criterio di disponibilita di input: gcc,bzip2, gobmk e perlbench presentano ognuno 4 o piu file sui quali ef-fettuare l’addestramento rispetto ad altri benchmark i quali offrono menopossibilita di scelta.

Figura 6.1: Processo di classificazione di una traccia sui modelli

Le modalita di test utilizzate sono due, alle quali e stato dato il nome diverifica e classificazione. La modalita di verifica consiste nell’addestrarecon un benchmark B un modello hmm e eseguire su questo modello testdi affinita con B e poi con tutti gli altri benchmark. Per ognuno vienequindi confrontata la probabilita che il modello corrisponda alla traccia conla probabilita generata da B. La percentuale di casi per i quali la probabilitadel benchmark effettivamente corrispondente alla traccia e maggiore rispettoagli altri indica la percentuale successo del test di verifica.

Il test di classificazione invece prevede di addestrare un insieme di modellicompleto, uno per ogni benchmark, e con questi effettuare il test di unbenchmark B: se il modello che e stato addestrato con B risponde con un

45

probabilita piu alta degli altri il test ha avuto successo. In particolare perogni coppia formata da traccia e benchmark che dichiara di essere deve essereeffettuata la scelta tra:

• H0 ≡ il processo corrisponde al benchmark dichiarato

• H1 ≡ il processo non corrisponde

Per decidere tra le due ipotesi viene effettuato un test di affinita ovverocalcolata le probabilita P di appartenenza della sequenza:

• P (H0)P (H1)

> Θ allora l’ipotesi viene accettata

• P (H0)P (H1)

< Θ viene rifiutata.

Come descritto in dettaglio a pag. 51 si vuole trovare un valore di Θ chemassimizzi numero di riconoscimento corretti, ovvero che limiti al massimoi casi per cui si ottiene un falso positivo o un falso negativo. Tali eventisi verificano quando un modello presenta affinita maggiore con il benchmarkeseguito rispetto a tutti gli altri pur non essendo quello realmente corrispon-dente (falso positivo) o quando un processo dichiara di appartenere ad unbenchmark che in realta non gli corrisponde e questo non viene riconosciuto(falso negativo).

6.1 Risultati test offline

I limiti imposti dalla metodologia di analisi offline hanno permesso di effet-tuare test su porzioni di tracce di dimensioni limitate, in particolare e statoscelto di effettuare solamente test di verifica in quanto piu rapido del test diclassificazione. Il processo di riconoscimento utilizzato in questa fase prevededi addestrare un modello hmm utilizzando una sola traccia e testarlo contutte le 8 tracce del set di 4 benchmark scelto. Se il test di Viterbi produceuna probabilita maggiore per le due tracce appartenenti al benchmark as-sociato al modello allora il test ha avuto successo. Per quanto riguarda lereti neurali un valore prossimo a 1 dato dal neurone di output significa chela traccia e stata riconosciuta.

6.1.1 Test di verifica hmm

Per trovare i valori ottimali dei parametri di addestramento e stato svilup-pato uno script che effettua test variando il numero di stati, di centroidi,di blocchi di indirizzi e la dimensione dei vettori per addestrare e testare imodelli. Parametri ottimali per le 4 tracce prese in esame in questa fase sonostati trovati in 64 centroidi e 12 stati (fig 6.2), con i quali e stato possibilericonoscere tutte le 8 tracce nel caso di segmenti di addestramento e testdi dimensione contenuta. Con tali parametri le tracce di bzip rispondono

46

con valori molto piu elevati rispetto alle altre quando testate su un modellohmm addestrato con bzip, e lo stesso per gcc, gobmk e perlbench.

Figura 6.2: precisione nel riconoscimento al variare di stati e centroidi

Nel grafico in fig 6.3 e rappresentata l’affinita (in ordinata) di ognunadelle 8 tracce (in ascissa) rispetto ad un modello di hmm addestrato a ri-conoscere un determinato benchmark (in legenda). Le tracce sono disposte acoppie, la prima coppia a sinistra corrisponde ai benchmark 400.perl.diffmaile 400.perl.checkspam. I valori per i primi due punti rispetto all’asse delleascisse sono maggiori rispetto a tutti gli altri, la traccia e stata quindi ri-conosciuta come proventiente dal benchmark 400.perl. Le stesse consid-erazioni si possono fare per gli altri benchmark: 401.bzip2 (punti 3 e 4),403.gcc (punti 5 e 6) e 445.gobmk (ultimi due punti).

Comparando i singoli risultati tra loro si puo notare che alcuni bench-mark siano piu facili da riconoscere rispetto ad altri. I risultati relativi a401.bzip2 presentano molto scarto tra quelli ottenuti nei test con il loro mod-ello e quelli di altri benchmark. Inoltre addestramenti di modelli differentima relativi allo stesso benchmark portano a risultati compatibili tra loro neitest, indicando una buona generalizzazione degli stessi.

6.1.2 Test di verifica reti neurali

Lo stesso procedimento e stato utilizzato per provare l’efficacia delle retineurali in questo contesto. Effettuando un singolo test delle 8 tracce su 4reti non si ottengono risultati validi, ma siccome la procedura di calcolo del-l’output di una rete neurale e molto piu rapida dell’algoritmo di Viterbi per

47

Figura 6.3: test offline hmm su 8 tracce

una hmm, per ogni test traccia/modello sono stati calcolati numerosi out-put della rete prendendo come punto d’ingresso diversi punti della traccia.Escludendo i valori massimi e minimi di questo set di risultati e possibilenotare un trend nel riconoscimento delle tracce. Nel grafico in fig 6.4, rela-tivo ad una rete addestrata con perlbench, si puo notare come la sequenzadi test relativi alle due tracce generate con perlbench sia sempre superioreai test effettuati con le tracce degli altri benchmark.

Estendendo questo processo a tutti e 4 i benchmark non si ottengonopero gli stessi risultati(fig 6.5): gcc e risultato non riconoscibile e anchealtre tracce non sono state riconoscibili al 100%.

Con i risultati ottenuti si ricava che l’apprendimento tramite hmm dis-crete risulta piu efficace rispetto alle reti neurali nel caso di tracce parametriz-zate spettralmente. Per fase analisi successiva si e scelto quindi di effettuaretest piu estesi utilizzando soltanto hmm.

6.2 Analisi su Valgrind

Lo sviluppo del tool tracehmm ha permesso di effettuare una serie di testmolto piu estesa variando i training set mantenendo tempi di esecuzioneragionevoli. Sono stati effettuati nuovamente i test di verifica descritti inprecedenza seguiti da estesi test di classificazione.

48

Figura 6.4: serie di test di riconoscimento di perlbench utilizzando retineurali

Figura 6.5: precisione nel riconoscimento di 8 tracce con le reti neurali

49

6.2.1 Test di verifica

Prima di utilizzare tutti i 12 benchmark di Spec sono stati effettuati nuova-mente i test di verifica su 4 tracce utilizzando pero piu input a disposizione,per un totale di 16 tracce provenienti dagli stessi 4 benchmark, ottenendogli stessi risultati dei test offline. In fig. 6.6 si possono vedere i risultati dellostesso test di verifica effettuato pero sull’insieme completo dei 12 benchmark,ottenendo una percentuale di riconoscimento media dell’80%.

Figura 6.6: Risultati test di verifica su 12 benchmark, 30 tracce

6.2.2 Test di classificazione

Per la fase di apprendimento sono stati utilizzati tutti i 12 benchmark diSpec INT2006, di ogni benchmark e stato calcolato un modello hmm utiliz-zando i valori ottimali di centroidi e di stati ottenuti nei test offline effettuatiprecedentemente (64 centroidi, 12 stati). Ogni modello e stato addestratoeseguendo il benchmark piu di una volta variandone l’input, al fine di otten-erne un modello il piu generalizzato possibile. Sono stati sperimentati trediversi modi di apprendimento dei modelli, utilizzando parti differenti dellatraccia in ingresso.

standard Definita W la dimensione della finestra di indirizzi da utilizzareper il calcolo dei centroidi e per un primo apprendimento, S il numerodi indirizzi da scartare prima di iniziare l’apprendimento, di ogni in-put vengono utilizzati per l’addestramento N finestre di indirizzi W apartire da S +Wk. Fig: 6.7

50

dimensioni ridotte Definita W la dimensione della finestra di indirizzi dautilizzare per il calcolo dei centroidi e per un primo apprendimento, Sil numero di indirizzi da scartare prima di iniziare l’apprendimento, diogni input vengono utilizzati per l’addestramentoN finestre di indirizziW/2 a partire da S + (W/2)k. Fig: 6.8

sovrapposizione Definita W la dimensione della finestra di indirizzi dautilizzare per il calcolo dei centroidi e per un primo apprendimento, Sil numero di indirizzi da scartare prima di iniziare l’apprendimento, diogni input vengono utilizzati per l’addestramentoN finestre di indirizziW a partire da S + (W/R)k. Fig: 6.9

I test vengono effettuati applicando l’algoritmo di Viterbi ad un bench-mark per ogni modello. Il valore di output (probabilita) del test di Viterbidel modello corrispondente al benchmark eseguito viene preso come valore diriferimento. I valori corrispondenti agli altri modelli vengono confrontati conquesto, se presentano affinita maggiore con il benchmark eseguito vengonocontati come falsi positivi.

Per trovare i falsi negativi viene eseguito un benchmark ma preso comemodello di riferimento uno corrispondente ad una traccia diversa. In questocaso se il modello presenta piu affinita rispetto a tutti gli altri modelli si ein presenza di un falso negativo. L’affinita di un’esecuzione con quella diriferimento si calcola come il rapporto tra la probabilita del modello presoin considerazione moltiplicata per un valore θ rispetto a quella del modellodi riferimento. Al variare di θ quindi un determinato benchmark produrrapiu o meno falsi positivi/negativi.

Per ogni modello di addestramento preso in considerazione sono statieseguiti i benchmark con diversi input in ingresso e calcolata poi la per-centuale di errore al variare di θ. Con i parametri utilizzati si riesce quindiad ottenere una precisione media nella classificazione delle tracce di circa80% come presente in Fig. 6.12, ovvero dove le linee di falsi positivi e falsinegativi si intersecano.

Al crescere dell’insieme di test il modello di apprendimento migliore cam-bia, e sono necessari insiemi di test piu grandi per un corretto riconosci-mento delle tracce. Sono stati effettuati test su tutti i 12 benchmark diSpecCPU2006 e calcolato i valori ottimale di θ. In Fig 6.14 si ottengono irisultati migliori, assestando intorno al 25% l’errore di classificazione delletracce.

Utilizzando il set completo di benchmark di SPECint la precisione deirisultati diminuisce ma si assesta comunque tra 70% e 80% utilizzando unametodologia di apprendimento adeguata.

51

Figura 6.7: In chiaro a sinistra la parte di traccia utilizzata per definire icentroidi. A destra le parti utilizzate per la prosecuzione dell’addestramentostandard

Figura 6.8: In chiaro a sinistra la parte di traccia utilizzata per definire icentroidi. A destra le parti utilizzate per la prosecuzione dell’addestramentoa finestre di dimensioni ridotte

Figura 6.9: In chiaro a sinistra la parte di traccia utilizzata per definire icentroidi. A destra le parti utilizzate per la prosecuzione dell’addestramentocon sovrapposizione

52

Figura 6.10: Risultati con addestramento del tipo standard con 4 bench-mark, 4 input per benchmark (16 tracce). L’addestramento standardprevede di utilizzare lo stesso numero di segmenti di traccia per il calcolodei centroidi e per la prosecuzione dell’addestramento.

53

Figura 6.11: Risultati con addestramento del tipo dimensioni ridottecon 4 benchmark, 4 input per benchmark (16 tracce). Tale tipo di addestra-mento prevede di utilizzare un numero di segmenti di traccia molto ampioper calcolare i centroidi nel modo piu accurato possibile e un numero disegmenti minore per la prosecuzione dell’addestramento.

54

Figura 6.12: Risultati con addestramento del tipo sovrapposizione con 4benchmark, 4 input per benchmark (16 tracce). Tale tipo di addestramentoprevede di utilizzare un segmenti di traccia parzialmente sovrapposti perl’addestramento, come in fig. 6.9.

55

Figura 6.13: Risultati con addestramento del tipo standard con 12 bench-mark, 30 tracce totali. L’addestramento standard prevede di utilizzare lostesso numero di segmenti di traccia per il calcolo dei centroidi e per laprosecuzione dell’addestramento.

56

Figura 6.14: Risultati con addestramento del tipo dimensioni ridottecon 12 benchmark, 30 tracce totali. Tale tipo di addestramento prevededi utilizzare un numero di segmenti di traccia molto ampio per calcolare icentroidi nel modo piu accurato possibile e un numero di segmenti minoreper la prosecuzione dell’addestramento.

57

Figura 6.15: Risultati con addestramento del tipo sovrapposizione con12 benchmark, 30 tracce totali. Tale tipo di addestramento prevede diutilizzare un segmenti di traccia parzialmente sovrapposti, come in fig. 6.9.

58

Per migliorare i risultati ottenuti si potrebbe effettuare una selezionedi benchmark, accorpandone alcuni che presentano affinita molto elevata, orimuovere alcuni input che non risultano facilmente associabili agli altri in-put del benchmark. Per effettuare queste considerazioni sono state prodottematrici di confusione per ogni gruppo di modelli hmm come la seguente:

omnet

sjen

g

xal

anc

ast

ar

h264

hm

mer

mcf

per

l

qu

antu

m

gcc

go

bzi

p

omnet 4 3 3 2 5 4 4 2 1 1 1sjeng 4 4 3 6 5 6 6 3 6 6 6xalanc 3 4 0 2 3 4 4 2 1 0 1astar 3 3 0 2 5 3 4 2 2 1 1h264 2 6 2 2 4 6 5 5 0 4 1hmmer 5 5 3 5 4 5 5 4 3 4 3mcf 4 6 4 3 6 5 6 5 6 6 5perl 4 6 4 4 5 5 6 5 4 4 4quantum 2 3 2 2 5 4 5 5 5 5 6gcc 1 6 1 2 0 3 6 4 5 3 4go 1 6 0 1 4 4 6 4 5 3 1bzip 1 6 1 1 1 3 5 4 6 4 1

Numero di volte che un test viene riconosciuto erroneamente comeappartenente ad un altro modello, 30 test totali

Ogni numero corrispondente ad una coppia di benchmark indica il numerodi volte che tali tracce sono state erroneamente riconosciute l’una con l’altranel test effettuato. Ipotizzando di poter dividere i programmi di riferimentoin gruppi molto diversificati tra loro, sono state prese per effettuare unaprova le 4 tracce meno correlate e di esse e stato calcolato l’errore al variaredi θ, raggiungendo una precisione superiore al 95%, Fig 6.16. Inoltre se siconsidera un certo margine d’errore nel rapporto tra la probabilita di Viterbidel modello e quello della traccia sconosciuta e non si pone la soglia a 1.0ma a 1.00± 0.05 o 1.00± 0.10 a seconda che si vogliano minimizzare di piui falsi negativi/positivi, i risultati migliorano anche mantenendo un insiemedi benchmark ampio, in Fig. 6.17 i risultati relativi alla classificazione 12benchmark utilizzando un valore di soglia di 1.00± 0.05.

59

Figura 6.16: Risultati del test di classificazione effettuato su un set ad-destrato in modo standard utilizzando i 4 benchmark con correlazione piubassa: astar, xalanc, go e bzip nel caso della matrice a pag. 59. L’ad-destramento standard prevede di utilizzare lo stesso numero di segmenti ditraccia per il calcolo dei centroidi e per la prosecuzione dell’addestramento.

60

Figura 6.17: Risultati del test di classificazione effettuato su un set ad-destrato in modo standard utilizzando una soglia di 1.00 ± 0.05 per falsipositivi e negativi. L’addestramento standard prevede di utilizzare lo stessonumero di segmenti di traccia per il calcolo dei centroidi e per la prosecuzionedell’addestramento.

61

Capitolo 7

Applicazioni

Di un processo in esecuzione e in genere possibile conoscere il nome del-l’eseguibile dal quale e stato caricato in memoria analizzando la lista deiprocessi. Il nome riportato non da la certezza pero che l’eseguibile caricatosia realmente quello specificato, in quanto su molti sistemi e possibile cam-biare runtime il nome del processo. Sarebbe poco efficace anche controllareche l’eseguibile in memoria corrisponda a quello sul disco in quanto questonon garantirebbe che l’esecuzione del programma avvenga principalmente inquel blocco di istruzioni.

Inoltre gli strumenti comuni di risconoscimento di un processo fornisconoinformazioni dettagliate sulle risorse attualmente utilizzate dal programmama non permettono di sapere a breve o lungo termine che risorse richiederail processo. La capacita di riconoscere un processo in esecuzione dal work-load generato si puo rivelare quindi utile in caso si voglia gestire in modoparticolare l’esecuzione di certe applicazioni sul sistema.

7.1 Monitoraggio e sicurezza

E’ possibile utilizzare il riconoscimento di processi tramite hmm per mon-itorare le applicazioni in esecuzione su di un server/cluster: addestrandouna serie di modelli hmm con le applicazioni che si vogliono riconoscere epossibile controllare che programmi sono effettivamente in esecuzione sul-la macchina. Sono previsti due scenari possibili, in caso sia piu indicatoutilizzare una whitelist o una blacklist.

7.1.1 Whitelist

Nel caso di applicazioni mission critical si puo volere essere sicuri che iprocessi in esecuzione siano effettivamente appartenenti all’applicazione instato di produzione e non ci siano dei thread malevoli mascherati da threaddell’applicazione in grado di accedere a dati riservati: stilando una whitelist

63

dei servizi offerti dal server e possibile allertare un ammistratore di sistemain caso i risultati dei test di hmm scendessero sotto una certa soglia.

In caso di provider offrenti sulle proprie macchine servizi limitati soload alcune applicazioni, come server web limitati all’esecuzione di script ogestione di email, si puo riconoscere l’installazione di software non permessiquando l’esecuzione di questi differisse da quelli in whitelist.

7.1.2 Blacklist

Allo scenario di un provider di servizi precedente puo essere applicata ancheuna soluzione facente uso di blacklist: si possono riconoscere programmi es-plicitamente non permessi e bloccarne l’esecuzione. Tale soluzione puo essereapplicata anche in ambiti differenti, ad esempio nel caso di contratti d’usoper i quali e stato firmato un End User License Agreement con condizioniparticolari, il gestore puo essere interessato ad inibire l’uso di particolarisoftware.

7.2 Allocazione di risorse

Metodologie di riconoscimento del workload possono rivelarsi fondamentaliper una distribuzione efficace delle risorse hardware disponibili: sono pre-visti due scenari di applicazione, nel caso di sistemi operativi dove si vuoleottimizzare l’interazione tra processi nelle richieste di risorse e nel caso di sis-temi virtualizzati dove l’obiettivo e incrementare le performance delle singolevirtual machine.

7.2.1 Sistemi operativi

Nel caso di sistemi operativi sottoposti a carichi elevati puo rivelarsi fon-damentale riuscire a predirre il prima possibile la quantita di memoria cherichiedera un processo durante la sua esecuzione: utilizzando un procedi-mento di riconoscimento hmm sulla prima parte di indirizzi generata dalprocesso si puo classificare il workload ed allocare risorse al processo di con-seguenza. Tali sistemi potrebbero cosı diminuire le latenze delle richieste diallocazione dinamica di memoria.

7.2.2 Ambienti di virtualizzazione

In ambienti di virtualizzazione inoltre potrebbe essere utile conoscere lanatura di un processo in esecuzione su una determinata virtual machineper modificare la distribuzione di risorse tra le varie macchine virtuali: adesempio in caso di processi richiedenti ampi blocchi di memoria le risorsehardware potrebbe essere ripartite in modo efficace riconoscendo per tempoquali virtual machine avranno un burst nelle richieste di allocazione e quindi

64

liberare blocchi di dati cached di conseguenza. Tale software di virtualiz-zazione potrebbe cosı massimizzare la quantita di memoria offerta ai singolisistemi client.

7.3 Implementazione

I procedimenti di estrazione delle tracce finora utilizzati sono adatti allafase di ricerca dei parametri ottimali e di addestramento dei modelli dautilizzare, ma per applicare in un contesto pratico gli algoritmi sviluppati enecessario trovare metodi differenti di generazione delle tracce. Con Valgrinde stato possibile effettuare analisi in modo molto piu rapido in quanto nonpiu necessario salvare la traccia, ma la sua architettura gli impedisce diinstrumentare un processo gia in esecuzione.

Prendendo in esame un sistema Linux x86 sono qui di seguito pro-poste modalita in user space, in kernel space e nel caso di sistemi

virtualizzati.

7.3.1 User space

Figura 7.1: Un programma in user space ferma il processo e ne permettel’esecuzione un’istruzione alla volta monitorando gli indirizzi a cui accede

Per ottenere una traccia di indirizzi in user space e necessario operarecome un debugger: fermare l’esecuzione di un processo, leggere il programcounter e analizzare l’istruzione che sta per essere eseguita. In Linux epossibile utilizzare la system call ptrace per ottenere accesso allo spazio diindirizzi di un altro processo ed accedere ai suoi registri. Un tool puo quindiessere sviluppato per attaccarsi ad un processo in esecuzione fermandolo,leggere EIP e salvare l’indirizzo come accesso in memoria di tipo instructionfetch, effettuare il parsing dell’istruzione puntata e aggiungere alla traccia gliindirizzi ai quali accede. Intel ha reso disponibile pintool [14] che permettedi effettuare tali operazioni su piattaforme x86 operando interamente in userspace.

65

7.3.2 Kernel space

Figura 7.2: Si simula un page fault ad ogni riferimento in memoria delprocesso per ottenere l’indirizzo direttamente nel kernel

Il kernel Linux non effettua via software la traduzione di pagine virtuali inpagine fisiche ma utilizza l’hardware della memory management unit delprocessore (x86). Pertanto non e possibile accedere alla sequenza di indirizzivirtuali senza intervenire sulla logica della MMU. In Linux ogni processo hauna sua page table, un metodo possibile di intervento e quello modificare lapage table del processo del quale interessano gli indirizzi perche la paginerisultino tutte come non presenti: ogni accesso generera un page fault, ilkernel ottiene cosı l’indirizzo che ha generato il page fault nel registro cr2e puo memorizzarlo. I flags delle varie pagine vanno manipolati perche ilbit di presenza della pagina sia sempre a zero cosı da generare gli interruptdi page fault e il bit reale di presenza/assenza sia un altro. E’ necessarioquindi anche modificare la logica di gestione delle pagine presenti/in swapper utilizzare questo bit e non quello standard [15].

Per trasferire la traccia di indirizzi dal kernel ad un processo in userspace e indicato utilizzare un device a caratteri. In tale modo possono essereprocessati ed analizzati dai tool descritti in precedenza senza dover effettuarescrittura su disco anche in questo caso.

7.3.3 Virtualizzazione

Nel caso di sistemi nei quali le applicazioni girino in ambiente virtualizzatosi puo intervenire sul software di virtualizzazione affinche esso produca lasequenza di indirizzi necessaria all’analisi. In caso di sistemi di virtualiz-zazione open source come kvm e possibile modificare direttamente il codicedi gestione della memoria per produrre la traccia di indirizzi virtuali delsistema client. In caso di software di virtualizzazione proprietari e richiestala presenza di API [16] per ottenere tali informazioni.

66

Figura 7.3: Il sistema monitorato e virtualizzato e si utilizzano API dellayer di virtualizzazione per generale la sequenza di indirizzi

67

Capitolo 8

Conclusione

L’obiettivo che ci siamo prefissi e stato quello di realizzare uno strumentosoftware che permettesse la classificazione dei workload in relazione alle met-riche di accesso alla memoria per arrivare fondamentalmente a due risultati:

• stabilire delle caratteristiche statistiche dei diversi workload e riuscirea classificarli

• stabilire istante per istante un algoritmo di riconoscimento del work-load in modo da poter costruire un sistema di allocazione di pagine dimemoria di tipo adattativo

Questi due obiettivi sono stati raggiunti e sono state gettate le basi per lacostruzione di nuovi sistemi di ottimizzazione adattiva di un processo inesecuzione. Questo studio ha messo in evidenza vari risultati, cioe:

• i processi in esecuzione possono essere rappresentati dalla sequenza diindirizzi virtuali generata dai processi stessi

• i processi visti come sequenze di indirizzi possono essere interpretatispettralmente

• descrivendo le sequenze con parametri ottenuti dalla trasformata delcoseno, i processi possono essere riconosciuti con buona accuratezza

• la classificazione puo essere effettuata in tempo reale con bassa comp-lessita computazionale

Le sperimentazioni effettuate hanno quindi dimostrato che le classifi-cazioni ottenute con i modelli statistici di Markov sono promettenti. Questorisultato apre tutta una serie di prospettive di sviluppi futuri, in linea con leultime tendenze della ricerca per quanto riguarda l’ottimizzazione dei siste-mi di calcolo. L’utilita di questi risultati sta nel fatto che e possibile eseguireuna classificazionedel workload in tempo reale e quindi possibile usare questa

69

classificazione per ottimizzare alcuni parametri del kernel del sistema, comead esempio la gestione della memoria.

Oltre alla possibilita di classificare un processo in esecuzione, la soluzioneproposta presenta delle caratteristiche che fanno pensare ad altre possibiliapplicazioni, come ad esempio quella di monitorare un processo in esecuzioneper verificare se sia veramente quella che dichiara di essere oppure per con-trollare che non cambi natura, segno che ad esempio potrebbe essere sogget-ta di un attacco da parte di un processo malizioso. In questo caso sarebbebene bloccare l’esecuzione prima che comporti dei danni. Questo tipo diapplicazioni verranno studiate in futuro.

Una estensione dell’approccio descritto consiste nel considerare non so-lo parametri derivati dalle sequenze di indirizzi ma anche altri parametriderivati dall’uso dell’I/O da parte dei processi. Un ulteriore evoluzione diquesta ricerca potrebbe essere quella di considerare altre metriche di memo-ria e altri parametri rappresentativi per confrontare le prestazioni del sistemaadattativo nei vari casi.

70

Appendice A

Documentazione tools offline

A.1 train, test

train legge una traccia con la quale addestra modelli hmm e genera filerelativi ai centroidi e al modello.

test con in input un modello hmm, un file di centroidi e una traccia stampala probabilita che la traccia appartenga al modello.

Uso da linea di comando

./train [options] <tracefile>

./test [options] -C [centroids file] -H [hmm file] <tracefile>

-w <int> numero di blocchi di indirizzi da processare, def 1000

-d <int> numero di indirizzi per blocco, default 1024

-v <int> dimensione dei vettori da quantizzare, default 16

-c <int> numero di centroidi, default 64

-n <int> numero di stati della hmm, default 12

-s <int> offset dal quale iniziare l’analisi, default 0

-D <string> output directory, default "/tmp"

Scripts

singlerun.rb effettua l’addestramento di un modello hmm con una tracciae lo testa con tutte le tracce. Multithreaded, produce grafici.

fullrun.rb effettua l’addestramento di un modello hmm con ogni traccia,poi viene effettuato il test di ogni traccia su ogni modello. Multi-threaded, produce grafici.

bruteforce.rb effettua l’addestramento di un modello hmm con ogni trac-cia, poi viene effettuato il test di ogni traccia su ogni modello. Il pro-cedimento viene ripetuto per diversi valori di window size, centroidi,

71

stati per cercare i migliori parametri di addestramento. Multithreaded,produce (molti) grafici.

A.2 genset zero, genset one, ntrain, ntest

genset one legge una traccia, la divide in settori e genera un insieme di Nesempi per essere utilizzati come input corretto della rete neurale e unfile di centroidi.

genset zero legge una traccia e genera un insieme di M esempi da essereutilizzati come input della rete neurale per il quale si desidera outputzero utilizzando i centroidi calcolati con genset one.

ntrain addestra una rete neurale e la salva su file.

ntest con in input un esempio generato da genset zero o genset one e unmodello di rete calcola l’output applicando l’esempio agli input dellarete.


usage: ./genset_one -s seek -D directory <trace.bin>

usage: ./genset_zero -s seek -D dir -C <input.ctr> <trace.bin>

usage: ./ntrain -G <good.set> <bad.set> <bad.set>...

usage: ./ntest -D directory -N <input.net> <test.set>

Scripts

singletest.rb effettua l’addestramento di una rete neurale con una tracciae la testa con tutte le tracce. Vengono effettuati 200+ test e scartatii risultati agli estremi superiore e inferiore. Produce grafici.

multitest.rb effettua l’addestramento di una rete neurale con ogni traccia epoi le testa con tutte le tracce. Vengono effettuati 200+ test e scartatii risultati agli estremi superiore e inferiore. Multithreaded, producegrafici.

matrixtest.rb Esegue singlerun.rb variando i parametri della rete pertrovare i valori di addestramento ottimali. Multithreaded, producegrafici.

72

Appendice B

Documentazione toolsValgrind

B.1 tracebin

Estensione di valgrind che genera le tracce in formato ascii e/o binario sufile o su stdout.


usage: valgrind --tool=tracebin [options] prog-and-args

--std=yes|no enable traditional output [yes]

--din=filename write trace in a dinero traditional format file

--bin=filename write trace in a binary file

B.2 tracehmm

tracehmm applica la parametrizzazione spettrale ed esegue apprendimentoe test di hmm utilizzando direttamente gli indirizzi di memoria via via chevengono generati dai benchmark.


usage: valgrind --tool=tracehmm [options] prog-and-args

--new=<model.hmm> train a new hmm model

--resume=<model.hmm> resume training

--test=<model.hmm> test hmm model

--centroids=<model.ct> centroids file

--skip=<int> memory blocks to skip

--window=<int> window size

--verbose=yes|no verbose [yes]

73

--vverbose=yes|no very verbose [no]

--ct-n=<int> num of centroids

--st-n=<int> num of statuses

Scripts

benchmarks.rb incapsulamento in una classe Benchmark dei benchmarkSpec. Ogni oggetto di tipo Benchmark ha associata la directory coni file di input e l’eseguibile, il nome dell’eseguibile, un array di lineedi comando per lanciare il benchmark con i diversi input. Includendoquesto file negli altri script e possibile accedere all’array $benchmarks

contenente 12 oggetti di tipo Benchmark. Da configurare con il pathdei benchmark Spec.

# ricerca di gcc

b= $benchmarks.find(lambda{die "not found"}) do |el|

el.name.eql? "gcc"

end

puts b.rand_cmd # stampa comando casuale

b.each_cmd do |cmd|

# al blocco vengono passati

# uno ad uno tutti i comandi

# per essere eseguiti dalla classe Hmm

puts cmd

end

benchmarks-4.rb includendo questo file negli altri script e possibile ac-cedere all’array $benchmarks contenente un set ridotto di 4 oggetti ditipo Benchmark.

hmm.rb incapsulamento in una classe Hmm dell’utilizzo del tool Valgrindtracehmm: offre metodi di addestramento e test dei benchmarks. Levariabili d’istanza degli oggetti di classe Hmm permettono di man-tenere gli stessi centroidi e modello tra l’esecuzione di un addestrma-mento e le successive. Sono configurabili tutti i parametri di addestr-mento.

h= Hmm.new "path-to-valgrind"

h.verbose= true

h.out_dir = "models-output-directory"

h.window= 2000

h.skip= 1000

h.train "cmd-to-run" # genera centroidi e modello

74

h.resume "another-cmd" # continua l’addestramento

# test

result= h.test "another-cmd-even-from-other-benchmarks"

train.rb effettua l’addestramento di un modello hmm. Produce file dei cen-troidi e del modello. Da configurare con il path della versione customdi Valgrind con tracehmm.

train-all.sh effettua l’addestramento di modelli per tutti i benchmark es-eguendo train.rb.

verification.rb esegue un test di verifica su un benchmark. Richiede ininput il nome del benchmark da testare. Produce grafici.

full-verification.rb esegue un test di verifica su tutti i benchmark. Richiedein input la directory contenente modelli e centroidi prodotti da train.rb.Produce grafici.

classification.rb esegue un test di classificazione su tutti i benchmark.Richiede in input la directory contenente modelli e centroidi prodottida train.rb. Produce grafici.

bf.rb esegue test di verifica variando i parametri di addestramento pertrovare valori ottimali. Richiede in input la directory contenente mod-elli e centroidi prodotti da train.rb. Produce grafici.

cmatrix.rb produce la matrice di confusione di un test di classificazione informato HTML.

plot.rb contiene la classe Plot che viene utilizzata dagli altri script pergenerate grafici dallo stile uniforme.

plot2.rb refactoring di plot.rb facendo uso di programmazione funzionale,vedi plot.rb

array-plus.rb funzioni helper di manipolazione arrays.

reg-tests.rb esegue 240 regression tests sul tool di Valgrind tracehmm perverificare che l’ultima versione di sviluppo funzioni correttamente.

75

Bibliografia

[1] Ning Li and Shun-Zheng Yu. Periodic hidden markov model-basedworkload clustering and characterization. In Computer and InformationTechnology, 2008. CIT 2008. 8th IEEE International Conference on,pages 378 –383, 2008.

[2] M. Calzarossa and G. Serazzi. Workload characterization: a survey.Proceedings of the IEEE, 81(8):1136 –1150, August 1993.

[3] Ken J. McDonell. Benchmark frameworks and tools for modellingthe workload profile. Performance Evaluation, 22(1):23 – 41, 1995.6th International Conference on Modelling Techniques and Tools forComputer Performance Evalution.

[4] A. Moro, E. Mumolo, M. Nolich. Ergodic Continuous Hidden MarkovModels for workload characterization. 2009 Proceedings of 6th Interna-tional Symposium on Image and Signal Processing and Analysis, pages99–104, September 2009.

[5] Leonard E. Baum, Ted Petrie, George Soules, and Norman Weiss. Amaximization technique occurring in the statistical analysis of prob-abilistic functions of markov chains. The Annals of MathematicalStatistics, 41(1):pp. 164–171, 1970.

[6] Jr. Forney, G.D. The viterbi algorithm. Proceedings of the IEEE,61(3):268 – 278, 1973.

[7] Nicholas Nethercote and Julian Seward. Valgrind: A Framework forHeavyweight Dynamic Binary Instrumentation. Proceedings of ACMSIGPLAN 2007 Conference on Programming Language Design andImplementation, San Diego, California, USA, June 2007.

[8] Valgrind source code. Valgrind Technical Documentation. URL:http://valgrind.org/docs/manual/index.html, 2010.

[9] Nicholas Nethercote. Dynamic Binary Analysis and Instrumentation.PhD thesis, University of Cambridge, November 2004.

77

[10] The Standard Performance Evaluation Corporation. SPEC CPU2006Documentation. URL: http://www.spec.org/cpu2006/Docs/, 2006.

[11] Gnu octave source code. http://www.octave.org.

[12] Tapas Kanungo. Umdhmm: Hidden markov model toolkit. ExtendedFinite State Models of Language, 1999.

[13] David MacKay. Information Theory, Inference, and LearningAlgorithms. Cambridge University Press, 2003.

[14] Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klaus-er, Geoff Lowney, Steven Wallace, Vijay Janapa Reddi, Kim Hazelwood.Pin: Building Customized Program Analysis Tools with Dynamic In-strumentation. Programming Language Design and Implementation,Chicago, IL, pages 190–200, June 2005.

[15] Robert Love. Linux Kernel Development. Novell Press, 2005.

[16] Min Xu, Vyacheslav Malyugin, Jeffrey Sheldon, Ganesh Venkitachalam,Boris Weissman, and Vmware Inc. Retrace: Collecting execution tracewith virtual machine deterministic replay. In In Proceedings of the 3rdAnnual Workshop on Modeling, Benchmarking and Simulation, MoBS,2007.

78

Monitoraggio di applicazioni software mediante modelli di Markov

Documents

Transcript of Monitoraggio di applicazioni software mediante modelli di Markov