RAPPORT de Stage d’immersion en Entreprise

1.1 Architecture du systŁme . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.1 Recherche de patrons avec un automate (cid:224) Øtats (cid:28)nis . . . . . . . . . . . . . 10

2.2 Format des ØvŁnements Lttng . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.1 Diagramme de cas d’utilisation . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2 Diagramme de sØquence du cas d’utilisation "Ajout de scØnarios" . . . . . 24

3.3 Diagramme de sØquence du cas d’utilisation "Edition d’un scØnario" . . . . 25

3.4 Diagramme de sØquence du cas d’utilisation "VØri(cid:28)cation de scØnarios" . . 25

4.1 Diagramme de paquetages . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.2 Diagramme de classe du package Parser . . . . . . . . . . . . . . . . . . . . 29

4.3 Diagramme de classe du package Expressions . . . . . . . . . . . . . . . . . 30

4.4 Diagramme de classe du package Evaluators . . . . . . . . . . . . . . . . . 33

4.5 Diagramme de classe du package Exceptions . . . . . . . . . . . . . . . . . 34

4.6 Diagramme de classe du package Trace . . . . . . . . . . . . . . . . . . . . 35

4.7 Diagramme de classe du package DetectionEngine . . . . . . . . . . . . . . 36

4.8 Diagramme de classe du package CheckType . . . . . . . . . . . . . . . . . 37

4.9 Diagramme de classe du package Observable . . . . . . . . . . . . . . . . . 38

. . . . . . . . . . . . . . . 39

4.10 Diagramme de classe du package Environments

5.1 Capture d’Øcran - 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.2 Capture d’Øcran - 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.3 Capture d’Øcran - 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.4 Capture d’Øcran - 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.5 Capture d’Øcran - 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.6 Capture d’Øcran - 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.7 Capture d’Øcran - 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.8 Capture d’Øcran - 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.9 Capture d’Øcran - 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

ix

Table des (cid:28)gures

5.10 Capture d’Øcran - 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.11 Capture d’Øcran - 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.12 Capture d’Øcran - 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.13 Capture d’Øcran - 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.14 Capture d’Øcran - 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.15 Chronogramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

x

Introduction

L’Ømergence des systŁmes distribuØs, multi-coeurs, o(cid:27)re certes un niveau de per-

formance supØrieur aux infrastructures d’entreprise mais rend leur (cid:28)abilitØ plus di(cid:30)cile (cid:224)

garantir, qui n’en dØmeure pas un critŁre moins important. En e(cid:27)et, force est de constater

que la complexitØ grandissante de ces systŁmes ne facilite en rien la dØtection d’activitØs

malicieuses et des comportements (cid:224) risque avec les outils de surveillance classiques qui

se voient dØsormais dØpassØs par cette technologie. C’est l(cid:224) qu’appara(cid:238)t la gØnØration de

traces d’exØcution comme solution (cid:224) ce problŁme. Le noyau du systŁme est instrumenta-

lisØ de telle sorte (cid:224) journaliser tous les appels systŁme exØcutØs. Les quantitØs Ønormes

de donnØes traitØes font de la lecture manuelle de ces (cid:28)chiers et la detection des activitØs

malicieuses une t(cid:226)che di(cid:30)cile voire fastidieuse.

La question qui se pose alors est comment peut-on automatiser l’analyse des traces

d’exØcution tout en gardant un niveau de dØtails similaire (cid:224) celui o(cid:27)ert par la lecture

manuelle de ces traces ? Le projet au sein duquel j’ai participØ au cours de ce stage (cid:224) pour

mission de rØpondre (cid:224) cette problØmatique. En e(cid:27)et, il s’agit d’automatiser l’analyse de

traces en adoptant une approche dØclarative se basant sur les langages rØguliers qui seront

employØs pour spØci(cid:28)er le comportement du systŁme. Certes, ce genre de spØci(cid:28)cation est

gØnØralement utilisØ pendant la phase de conception du systŁme pour vØri(cid:28)er que son

exØcution future respectera le comportement spØci(cid:28)Ø, mais peut Œtre Øgalement exploitØ

lors de la phase de dØploiement a(cid:28)n de surveiller le comportement e(cid:27)ectif du systŁme et

dØclencher des alertes lorsque la spØci(cid:28)cation est violØe par un comportement (cid:224) risque. La

mission qui m’a ØtØ con(cid:28)Øe pendant ce stage s’interesse essentiellement (cid:224) l’analyse statique

des scØnarios spØci(cid:28)Øs pour la detection de ces comprtements (cid:224) risque et le prØsent rapport

rØcapitule les di(cid:27)Ørentes Øtapes par laquelle j’ai dß passer pour rØaliser ce travail.

Le premier chapitre, prØsentera le groupe LSFM de l’UniversitØ Laval oø j’ai e(cid:27)ectuØ

ce stage. Il dØcrira Øgalement le projet auquel j’ai participØ et les di(cid:27)Ørentes t(cid:226)ches (cid:224)

rØaliser pendant la durØe du stage.

Le deuxiŁme chapitre intitulØ Øtude thØorique, se chargera de traiter l’Øtude de l’art

relative (cid:224) ce projet, (cid:224) prØsenter le langage de spØci(cid:28)cation utilisØ pour la recherche de

1

Introduction

patrons ainsi qu’une spØci(cid:28)cation formelle des rŁgles de typage que doit respecter ce

langage.

Le chapitre suivant dØgagera les besoins que doit satisfaire notre application (fonc-

tionnels soient ils ou encore non fonctionnels) ainsi qu’un aper(cid:231)u sommaire de son fonc-

tionnement (cid:224) travers ses di(cid:27)Ørents cas d’utilisation.

Nous nous attaquerons (cid:224) la conception de notre application dans le quatriŁme cha-

pitre. Cette partie dØcrira tout d’abord l’architecture gØnØrale de l’application et s’appro-

fondira par la suite encore plus pour bien dØtailler ses di(cid:27)Ørentes composantes.

Le cinquiŁme et dernier chapitre traitera de l’implØmentation de ce projet en dØ-

crivant l’environnement de travail ainsi qu’en prØsentant (cid:224) l’aide de captures d’Øcran un

scØnario d(cid:17)exØcution. Nous clorons ce chapitre avec un chronogramme dØtaillant le che-

minement de ce travail.

2

Chapitre 1

PrØsentation gØnØrale

Dans ce premier chapitre, nous commen(cid:231)ons par prØsenter briŁvement l’organisme

d’accueil au sein duquel nous avons e(cid:27)ectuØ le stage relatif au prØsent projet. La suite du

chapitre est consacrØe (cid:224) prØsenter ses di(cid:27)Ørents objectifs..

1.1 PrØsentation de l’organisme

UniversitØ Laval

[N1] L’universitØ Laval est le premier Øtablissement d’enseignement supØrieur au

QuØbec et au Canada. Elle est Øgalement la premiŁre universitØ francophone en AmØ-

rique, et la cinquiŁme plus ancienne toutes langues confondues. Ses origines remontent

(cid:224) 1663 avec la fondation du SØminaire de QuØbec par Fran(cid:231)ois de Montmorency-Laval,

le premier ØvŒque de la Nouvelle-France. Elle est un Øtablissement pluridisciplinaire qui

propose environ 350 programmes d’Øtudes, du premier au troisiŁme cycle, (cid:224) plus de 38

000 Øtudiants. Elle fait Øgalement partie des 10 plus importantes universitØs canadiennes

en matiŁre de recherche avec plus de 250 millions de dollars en fonds de recherche et

coopØration internationale.

Le DØpartement d’informatique

[N2] Le dØpartement d’informatique est rattachØ (cid:224) la FacultØ des Sciences et du

GØnie de l’UniversitØ Laval. Il fut crØØ en 1974 avec un groupe de 7 professeurs et en

compte actuellement une vingtaine qui enseignent annuellement environs 1100 Øtudiants.

Sept groupes de recherches lui sont a(cid:30)liØs :

(cid:21) DAMAS : Data mining, Agents et Systemes Multi-Agent

3

Chapitre 1. PrØsentation gØnØrale

(cid:21) ERICAE : Equipe de Recherche en IngØnierie des ConnAissancEs

(cid:21) GRAAL : Groupe de Recherche en Apprentissage Automatique de l’UniversitØ

Laval

(cid:21) LIC/LCI : Laboratoire d’intelligence computationnelle

(cid:21) LSFM : Langages, SØmantiques et MØthodes Formelles

(cid:21) Monarc : Group Mobile Network Application Research Group

(cid:21) MUSCAMAGS : Multi-scale Multi-agent geo-simulation

LSFM

[N3] Le groupe LSFM, Langages, SØmantique et MØthodes formelles, existe depuis

janvier 1995 et reprØsente une structure de recherche qui regroupe plusieurs professeurs

et plusieurs Øtudiants graduØs du DØpartement d’Informatique et de gØnie logiciel de

l’UniversitØ Laval. Les travaux menØs au sein du groupe gravitent autour des thŁmes

suivants :

(cid:21) Langages multiparadigmes.

(cid:21) MØthodes formelles : spØci(cid:28)cation et vØri(cid:28)cation.

(cid:21) Analyse statique de programmes.

(cid:21) SØcuritØ et protocoles cryptographiques.

(cid:21) Technologie WWW.

(cid:21) SØmantique formelle.

(cid:21) ThØorie des graphes

(cid:21) ComplexitØ

(cid:21) Compression de donnØes

1.2 PrØsentation du projet

[N4] Il s’agit d’un projet intitulØ "Analyse de traces et surveillance de systemes

multi-coeurs distribuØs". Ce projet, d’une durØe de trois ans, est (cid:28)nancØ conjointement

par Ericsson, Recherche et dØveloppement pour la dØfense Canada et le Conseil de re-

cherches en sciences naturelles et en gØnie du Canada. DirigØ (cid:224) l’(cid:201)cole polytechnique par

le DORSAL, il est menØ en collaboration avec l’UniversitØ Concordia, l’UniversitØ Laval

et l’UniversitØ d’Ottawa. Il comporte sept axes de recherche :

(cid:21) Instrumentation adaptative de fautes

(cid:21) Synchronisation de traces distribuØes multi-niveaux et multi-coeurs

(cid:21) Abstraction, analyse et corrØlation de traces

(cid:21) Identi(cid:28)cation automatique de fautes

4

1.3. Analyse de l’existant et position du problŁme

(cid:21) ModØlisation de systŁme basØe sur les traces d’exØcution

(cid:21) Surveillance de l’intØgritØ des systŁmes et activation de mesures de rØaction

(cid:21) PrØdiction de l’impact de l’infrastructure de tra(cid:231)age et de surveillance

La partie relative (cid:224) l’UniversitØ Laval et surlaquelle j’ai ØtØ amenØ (cid:224) travailler conjoin-

tement avec un Øtudiant en ma(cid:238)trise, qui fait depuis dØj(cid:224) une annØe de ce projet, est la

partie relative (cid:224) l’identi(cid:28)cation automatique de fautes. Ce travail consiste (cid:224) automatiser

l’analyse des traces gØnØrØes par l’outil Lttng (cid:224) travers un langage qui permet de spØci-

(cid:28)er un ensemble de propriØtØs (cid:224) rechercher dans la trace et de vØri(cid:28)er si une succession

d’ØvŁnements vØri(cid:28)ant certains critŁres a vraiment eu lieu. L’architecture du systŁme est

dØcrite par la (cid:28)gure 1.1

Figure 1.1 (cid:21) Architecture du systŁme

(cid:21) Les traces d’exØcution sont gØnØrØes (cid:224) partir du noyau par Lttng.

(cid:21) Les patterns spØci(cid:28)Øs sont traduits par le parseur.

(cid:21) L’engin de detection recherche par suite ces patrons dans la trace et gØnŁre des

alertes lorsqu’il en dØtecte un.

1.3 Analyse de l’existant et position du problŁme

1.3.1 Analyse de l’existant

A mon arrivØe, le projet Øtait dØj(cid:224) (cid:224) un stade avancØ : Une bonne partie de la

grammaire du langage de spØci(cid:28)cation Øtait dØj(cid:224) dØ(cid:28)nie. Le parseur ainsi que l’engin de

5

DetectionenginekernelTracesPatternsAlerts,etc.DecodingengineChapitre 1. PrØsentation gØnØrale

dØtection sont eux aussi implØmentØs et rØalisaient dØj(cid:224) la vØri(cid:28)cation des scØnarios sauf

que la spØci(cid:28)cation des scØnarios se faisait toujours dans le mŒme (cid:28)chier (et donc on Øtait

limitØs aux scØnarios d’un seul (cid:28)chier) et les ØvŁnements dØtectØs Øtaient tout simplement

sauvegardØs dans un (cid:28)chier de journalisation, ce qui se rØvŁle inappropriØ au niveau de

la visualisation des rØsultats de la vØri(cid:28)cation et fait de l’interprØtation des rØsultats de

la vØri(cid:28)cation une t(cid:226)che di(cid:30)cile. Le projet est sous la forme d’une archive Jar et donc il

fallait (cid:224) chaque modi(cid:28)cation recompiler tout le projet et ajouter la nouvelle archive Jar

dans un des plugins fournis par Ericsson.

Un autre Øtudiant en ma(cid:238)trise, travaillant quant (cid:224) lui sur un projet d’analyse de

paquets IP, et qui (cid:224) dß aussi avoir recours (cid:224) un langage quasi identique au langage utilisØ

pour le prØsent projet, a implØmentØ un plugin Eclipse sous la forme d’un Øditeur. La

saisie du programme se faisait (cid:224) travers cette vue eclipse, comme pour du code java, et

par la suite la compilation du (cid:28)chier se lan(cid:231)ait et l’Øditeur a(cid:30)chait Øventuellement les

erreurs dØtectØs pendant la construction de l’arbre syntaxique.

1.3.2 Description des taches (cid:224) rØaliser

1.3.2.1 RØalisation d’une interface graphique

Comme spØci(cid:28)Ø auparavant, la solution prØsente Øtait tout (cid:224) fait fonctionnelle, mais

les di(cid:27)Ørentes restrictions au niveau de l’utilisation ne satisfaisaient pas les critŁres d’er-

gonomie d’un projet pareil, qui sera utilisØ par la suite par des utilisateurs qui ignorent

pour la plupart les dØtails de l’implØmentation et qui ne devaient pas en Œtre sanctionnØs.

Dans cette Øtape, nous proposons la conception et la rØalisation d’une interface graphique

ergonomique permettant (cid:224) un utilisateur lambda d’exploiter le projet sans trop de soucis,

de visualiser le rØsultat de l’analyse de la trace en temps rØel et d’Œtre informØ des infor-

mations utiles de la trace qui interviennent dans la dØtection des scØnarios spØci(cid:28)es dans

le programme.

1.3.2.2 ImplØmentation d’un systŁme de typage

Les seules erreurs que le projet traitait convenablement jusque l(cid:224) Øtaient les erreurs

signalØes par le parseur ce qui Øtait loin d’Œtre su(cid:30)sant surtout que la richesse du langage

augmentait considØrablement les erreurs possibles au niveau des types des donnØes trai-

tØes et la cohØrence des donnØes spØci(cid:28)Øes, des erreurs que nous pouvions jusque l(cid:224) s’en

apercevoir que lors de l’exØcution. Nous dØ(cid:28)nirons donc un systŁme de typage qui permet-

tra de vØri(cid:28)er que la spØci(cid:28)cation est bien typØe et qu’il ne prØsentera pas d’incohØrences

(cid:224) l’Øvaluation au niveau du type des donnØes traitØes .

6

1.3. Analyse de l’existant et position du problŁme

1.3.2.3 Extension vers un plugin IndØpendant du domaine d’Øtude

Comme spØci(cid:28)Ø auparavent, l’existence en parallŁle du projet analysant les paquets

IP utilisant un langage de spØci(cid:28)cation quasi identique (cid:224) celui utilisØ pour notre projet

et les possibilitØs d’avoir recours au mŒme langage pour une multitude de projets dont

les domaines di(cid:27)Łrent totalement d’un projet (cid:224) l’autre nous ont poussØ (cid:224) rØ(cid:29)Øchir sur

l’ØventualitØ d’exploiter le travail e(cid:27)ectuØ pour ce projet pour les deux projets et Øviter

ainsi une rØØcriture (cid:224) deux reprises du mŒme code. Nous avons donc dØcidØ de mettre au

coeur de notre travail la rØutilisabilitØ du code et sa gØnØricitØ et faire tout notre possible

pour que les di(cid:27)Ørents traitements soient indØpendants du domaine d’Øtudes et limiter

ainsi au maximum les adaptations (cid:224) e(cid:27)ectuer d’un projet (cid:224) l’autre. Le projet sera aussi

rØØcrit sous la forme d’un plugin Eclipse, qui nous permettra (cid:224) la livraison du projet d’Œtre

en concordance avec les di(cid:27)Ørentes participations au projet qui se feront pour la plupart

sous cette forme Øvitant ainsi le dØsagrØment liØ (cid:224) la recompilation en une archive Jar (cid:224)

chaque mise (cid:224) jour.

Conclusion

A travers ce chapitre, nous avons prØsentØ l’organisme d’accueil de ce stage. Nous

avons Øgalement dØcrit oø en Øtait le projet pour le moment ainsi que les di(cid:27)Ørentes t(cid:226)ches

(cid:224) rØaliser durant ce stage Nous passons maintenant (cid:224) l’Øtude thØorique qui nous permettra

de mieux assimiler ces t(cid:226)ches.

7

Chapitre 2

Etude ThØorique

Dans ce chapitre, nous traiterons tout d’abord l’Øtat de l’art en se penchant sur les

principaux mots clØs liØs (cid:224) ce projet. Nous dØtaillerons Øgalement la spØci(cid:28)cation formelle

relative au langage de description des scØnarios en prØsentant d’abord sa grammaire et

par la suite les di(cid:27)Ørentes rŁgles de typage qui composent son systŁmes de types.

2.1 Etat de l’art

2.1.1 Tracing

Le tracing consiste (cid:224) gØnØrer des traces d’exØcution pour bien comprendre ce qui se

passe au niveau d’un systŁme a(cid:28)n de le surveiller ou encore dØboguer pour remØdier aux

divers problŁmes qui peuvent survenir aux systŁmes temps rØel ou encore d’autres sys-

tŁmes aux architectures parallŁles complexes. Un traceur est un outil utilisØ pour gØnØrer

ces traces et dont la fonctionnalitØ est un peu similaire (cid:224) la journalisation vu qu’aprŁs

tout il ne fait qu’enregistrer les ØvŁnements sauf que pour le tra(cid:231)age il s’agit d’enregis-

trer des ØvŁnements de bas niveau qui ont lieu beaucoup plus frØquemment. En e(cid:27)et, les

traces contiennent gØnØralement les ØvŁnements gØnØrØs par le noyau du systŁme d’opØra-

tion ( Appels systŁme, Ordonnancement, ActivitØ sur le rØseau, etc.) ou encore d’autres

gØnØrØs par toute autre application ce qui fait que des milliers d’ØvŁnements sont enregis-

trØes toutes les secondes gØnØrant des traces de taille pouvant atteindre des dizaines de

gigaoctets.

Les traces peuvent Œtre lues directement dans les (cid:28)chiers gØnØrØes par les traceurs,

ce qui o(cid:27)re un niveau de dØtail inØgal, mais ceci se rØvŁle contraignant voire une t(cid:226)che

fastidieuse lorsqu’il pour avoir une idØe gØnØrale cela se rØvŁle de lire manuellement d’aussi

importantes quantitØs d’informations d’ou l’utilitØ des outils facilitant l’analyse de traces

8

2.2. Lttng

(cid:224) travers des graphes ou encore des statistiques modØlisant ces informations.

Un autre moyen, qui facilite nettement l’analyse de traces, sans perdre niveau des dØ-

tails, consiste (cid:224) spØci(cid:28)er certains comportements du systŁme que nous souhaitons dØtecter

et par la suite parcourir la trace automatiquement pour rechercher ces comportements ;

ceci est notamment possible gr(cid:226)ce au Pattern Matching ou encore la recherche de patrons.

2.1.2 Pattern Matching

[N5] Le pattern matching, ou encore la recherche de motifs, est le fait de parcou-

rir un ensemble de jetons, et de rechercher une sØquence bien prØcise de ces jetons, le

pattern, reprØsente au fait cette sØquence de jetons. Les patterns sont gØnØralement re-

prØsentØs avec sous formes d’arbres ou des structures sØquentielles. L’approche adoptØe

par la recherche de patterns dans les traces d’exØcution gØnØrØes par Lttng, consiste (cid:224)

modØliser les di(cid:27)Ørents comportements possibles du systŁme (traces) par un langage qui

sera par la suite utilisØ pour dØcrire les sØquences d’ØvŁnements (ØlØments de la trace) qui

seront combinØs de telle sorte (cid:224) indiquer tout comportement (cid:224) risque que nous dØsirons

dØtecter/rechercher dans la trace. La recherche par la suite de ces sØquences d’ØvŁnements

sera modØlisØe par la recherche d’une expression rØguliŁre dans une suite trace (cid:224) l’aide

des automates (cid:28)nis. La (cid:28)gure 2.1 dØcrit la recherche du pattern "aabaaa" dans une trace

contenant la sØquence "aaabaabaaab".

2.2 Lttng

[N6,N7,N8] LTTng, Linux Trace Toolkit Next Generation (LTTng), qui est une sorte

d’Øvolution de l’outil "LTT", est un outil de Tracing pour les noyaux Linux. Il gØnŁre

des traces sont utilisØs pour surveiller les problŁmes de performance ou encore pour le

dØboguage pour des systŁmes multiprocesseurs et multit(cid:226)ches. LTTV est un outil qui fait

partie du mŒme projet, conduit (cid:224) l’Ecole Polytechnique de MontrØal, et qui permet l’ana-

lyse et la visualisation de ces traces. Comme son prØdØcesseur, il assure une architecture

indØpendante et a(cid:27)ecte peu les performances gØnØrales du systŁme mais tout en Øtant

prØcis, extensible, modulaire et facile (cid:224) utiliser.

Lttng journalise les ØvŁnements exØcutØs par le noyau dans des (cid:28)chiers binaires que

nous pourrons convertir par la suite en un format textuel lisible (cid:224) l’aide du plugin text-

Dump. Chaque ØvŁnement est modØlisØ selon le format reprØsentØ dans la (cid:28)gure 2.2.

On retrouve donc les champs :

(cid:21) Channel name : LTTng regroupe les ØvŁnements selon leur channel (ou encore

9

Chapitre 2. Etude ThØorique

Figure 2.1 (cid:21) Recherche de patrons avec un automate (cid:224) Øtats (cid:28)nis

10

0baba2abbababa1345a a a b a a b a a a b0baba2abbababa1345a a a b a a b a a a b0baba2abbababa1345a a a b a a b a a a b0baba2abbababa1345a a a b a a b a a a b0baba2abbababa1345a a a b a a b a a a b012230baba2abbababa1345a a a b a a b a a a b0baba2abbababa1345a a a b a a b a a a b0baba2abbababa1345a a a b a a b a a a b0baba2abbababa1345a a a b a a b a a a b0baba2abbababa1345a a a b a a b a a a b0baba2abbababa1345453452.3. Langage de spØci(cid:28)cation

Figure 2.2 (cid:21) Format des ØvŁnements Lttng

canal), comme par exemple kernel pour le noyau, mm pour la gestion de la mØmoire

(memory management), fs pour le systŁme de (cid:28)chiers ((cid:28)lesystem), etc.

(cid:21) Event subtype : Le nom spØci(cid:28)que a l’ØvŁnement sous la structure relative au

channel. Comme exemple on cite fs.open pour l’ØvŁnement "open" pour la channel

"fs".

(cid:21) Time-stamp : La date (en secondes et nano-secondes) (cid:224) laquelle l’ØvŁnement a lieu.

(cid:21) Trace (cid:28)le name : Le nom du (cid:28)chier binaire dans lequel l’ØvŁnement a ØtØ journalisØ.

Ce nom est construit (cid:224) partir du nom du channel (le champ channel name) suivi du

numØro du processeur. Pour l’exemple ØtudiØ dans la (cid:28)gure prØcØdente "kernel_0"

reprØsente tous les ØvŁnements "kernel" exØcutØs sur le CPU 0.

(cid:21) PID : L’identi(cid:28)ant du processus.

(cid:21) TGID : L’identi(cid:28)ant du groupe de threads, (thread group id), utilisØ pour les

applications multi-threads.

(cid:21) Process name : Le nom du processus.

(cid:21) Parent PID (PPID) : L’identi(cid:28)ant du processus parent.

(cid:21) Execution mode : Le mode d’exØcution relatif (cid:224) l’ØvŁnement : system call, user

mode, etc.

(cid:21) Event Parameters : Contenu de l’ØvŁnement, qui peut Œtre une valeur retournØe,

nom d’un (cid:28)chier ouvert, etc.

2.3 Langage de spØci(cid:28)cation

[B1] Comme spØci(cid:28)Ø lors de la prØsentation du Pattern Matching, nous utiliserons

un langage formel pour dØcrire les di(cid:27)Ørents patrons qu’on souhaite rechercher dans la

trace d’exØcution. Voici la syntaxe abstraite du langage considØrØ :

11

kernel.syscall_exit:26126.7872610 (./kernel_0), 30844, 30844 /chroot_violation, , 30844, 0x0, USER_MODE ret=0 Channel name Event subtype Process name Timestamp Trace file name PID Parent PID Execution Mode Event Parameters TGID Channel name CPU # Chapitre 2. Etude ThØorique

::= ext∗ spec? group∗ spec?

::= extern (cid:28) f ((cid:28)1; : : : ; (cid:28)n)

::= group g { spec }

::= var∗ pred∗ evtdef∗ scenario∗

::= var x = exp

::= predicate p (x1; : : : ; xn) { exp }

::= eventdef e (exp)

pgm

ext

group

spec

var

pred

evtdef

scenario ::= scenario s (x1; : : : ; xn) as (exp

evt(cid:28)lter

1; : : : ; exp

2) { evt(cid:28)lter∗ }

::= ( !)? event e (: etype)? (where exp)?

within(exp

1; exp

|

repetition(exp) { evt(cid:28)lter∗ }

|

::= c | x | exp:l | (exp) | f (exp

::= ! | -

::= exp

::= && | ||

::= == | !=

::= = | <= | > | <

::= - | * | /

::= +

logop exp

eqop exp

| exp

2

2

1

1

exp

unop

binop

logop

eqop

relop

arop

ovop

1; : : : ; exp

n) { evt(cid:28)lter∗ }

n) | unop exp | exp

1

binop exp

| exp in [exp

1; : : : ; exp

n]

2

| exp

relop exp

| exp

1

2

arop exp

| exp

1

2

1

ovop exp

2

Remarques : t∗ indique que t peut appara(cid:238)tre 0 ou n fois alors que t? indique que t

peut appara(cid:238)tre 0 ou 1 fois.

2.3.1 Typage

2.3.1.1 PrØliminaires

[N8] La sØmantique d’un langage est la description du sens des constructions du

langage. Comme dans une langue naturelle, les phrases syntaxiquement correctes d’un

langage de programmation n’ont pas toutes un sens et pour Øviter nous devons nous

assurer que le programme est bien correct sØmantiquement, avant d’e(cid:27)ectuer l’Øvaluation

d’une de ces expressions erronØes qui peut soit provoquer un plantage du programme

(segmentation fault), soit continuer l’exØcution avec un rØsultat absurde. On compte sur

le typage statique pour assurer que cela ne se produira pas

Une relation de typage est une relation portant sur le triplets (E, exp, (cid:28) ), oø E un

environnement de typage qui associe le type (cid:28) (cid:224) exp et les types E(x) aux identi(cid:28)cateurs x

libres dans exp. La relation de typage est notee E ⊢ exp : (cid:28) et se lit "dans l’environnement

E, l’expression exp a le type (cid:28) ", ou encore "sous les hypothŁses de typage sur les variables

exprimØes dans E, l’expression exp a le type (cid:28) ".

12

Nous spØci(cid:28)erons dans la suite les di(cid:27)Ørentes rŁgles de typage sur lesquelles on se

basera pour dØcider si la spØci(cid:28)cation est bien typØe ou non. Nous utiliserons les rŁgles

d’infØrence pour reprØsenter ces rŁgles de typage.

2.3. Langage de spØci(cid:28)cation

RŁgle d’infØrence

[N10] Dans la logique formelle, Une rŁgle d’infØrence est une regle syntaxique qui

nous permet de dØduire une certaine conclusion (cid:224) partir de prØmisses.

Elle est gØnØralement sous la forme

dans les deux sens :

P1 P2

::: Pn

C

Ces rŁgles peuvent Œtre lues

(cid:21) Si P1 et P2 et ... Pn sont vraies alors on peut conclure que C est vraie.

(cid:21) C est vraie pourvu que P1, P2, ..., Pn sont vraies.

Grammaire des types

Les donnØes traitØes par notre langage seront soit de type entier, cha(cid:238)ne de caractŁres,

boolØen, date, prototype de fonction ou encore une structure avec un ensemble d’ØlØments

avec leurs types respectifs :

(cid:28) ::= int | string | bool | time | (cid:28)1 × : : : × (cid:28)n → (cid:28) | { l1 : (cid:28)1; : : : ; ln : (cid:28)n }

Environnements de typage

(cid:21) L’environnement de typage associera aux di(cid:27)Ørents identi(cid:28)cateurs du programme

un type bien prØcis. L’environnement E = [x1 : (cid:28)1; : : : ; xn : (cid:28)n] par exemple associe

le type (cid:28)i (cid:224) chaque identi(cid:28)cateur xi.

(cid:21) Les constantes quant (cid:224) eux peuvent soient Œtre de type entier, cha(cid:238)ne de carac-

tŁres ou encore date. L’environnement prØcisant leurs types est TypeOf = [INT :

int; IDENT : string; TIME : time]

.

(cid:21) Nous devrons aussi initialiser l’environnement avec les di(cid:27)Ørents champs d’un ØvŁ-

0(lttng)))

nement lttng avec leurs types respectifs. Nous avons alors E0 = E ′

0

avec

E ′

0 = [lttng : {trace : string; type : string; channel : string; cpu : int; timestamp :

time}]

† ((cid:29)at(E ′

13

Chapitre 2. Etude ThØorique

SØquents

Nous utiliserons deux sortes de sØquents dans la suite :

(cid:21) E ⊢ exp : (cid:28) qui permet de typer une expression du langage et qui nous donne le

type de exp dans l’environnement E

(cid:21) E ⊢ o : E ′ et permet de typer les autres constructions syntaxiques du langage et

qui nous renvoient l’environnement, Øventuellement mis (cid:224) jour aprŁs parcours du

sous-arbre de la construction syntaxique.

2.3.2 RŁgles de typage

Notations

Dans ce qui va suivre, nous allons utiliser certaines notions que nous expliciterons

ici :

(cid:21) La notation E(x) pour retrouver le type associØ (cid:224) x dans l’environnement E :

[ x1 : (cid:28)1; x2 : (cid:28)2; x3 : (cid:28)3 ]

{z

}

|

E

(x2) = (cid:28)2.

(cid:21) Le (cid:29)at sert (cid:224) applatir un environnement ou encore une structure englobant un

ensemble d’identi(cid:28)ants avec leurs types respectifs et extraire ainsi ces ØlŁments :

(cid:29)at({ l1 : (cid:28)1; : : : ; ln : (cid:28)n }) = [ l1 : (cid:28)1; : : : ; ln : (cid:28)n ].

(cid:21) L’opØrateur † sera utiliser pour mettre (cid:224) jour un environnement (cid:224) partir d’un autre

environnement : [ x1 : (cid:28)1; x2 : (cid:28)2; x3 : (cid:28)3 ]

}

|

{z

E1

† [ x2 : (cid:28)1; x4 : (cid:28)4; x1 : (cid:28)3 ]

{z

}

|

E2

= [ x2 : (cid:28)1; x4 :

(cid:28)4; x1 : (cid:28)3; x3 : (cid:28)3 ].

(cid:21) L’opØrateur ⊖ sera utilisØ pour exclure d’un environnement certains ØlŁments :

[ x1 : (cid:28)1; x2 : (cid:28)2; x3 : (cid:28)3 ]

{z

}

|

E1

|

⊖ [ x2 : (cid:28)2; x1 : (cid:28)1 ]

{z

}

E2

= [ x3 : (cid:28)3 ].

(cid:21) L’opØrateur ⊕ sera utiliser pour rattacher un environnement (cid:224) un autre :

{ l1 : (cid:28)1; l2 : (cid:28)2; l3 : (cid:28)3 }

|

{z

}

E1(g)

|

⊕ { l2 : (cid:28)1; l4 : (cid:28)4; l1 : (cid:28)3 }

{z

}

E2(g)

= { l2 : (cid:28)1; l4 : (cid:28)4; l1 : (cid:28)3; l3 : (cid:28)3 }.

Expressions

Constante

14

TypeOf(c) = (cid:28)

E ⊢ c : (cid:28)

(cte)

2.3. Langage de spØci(cid:28)cation

Identi(cid:28)ant

Point

ParenthŁses

Appel de fonction

E(x) = (cid:28)

E ⊢ x : (cid:28)

(id)

E ⊢ exp : { : : : ; l : (cid:28); : : : }

E ⊢ exp:l : (cid:28)

(pt)

E ⊢ e : (cid:28)

E ⊢ (e) : (cid:28)

(par)

E ⊢ f : (cid:28)1 × : : : × (cid:28)n → (cid:28)

E ⊢ f (exp

E ⊢ exp

1; : : : ; exp

1 : (cid:28)1 : : : E ⊢ exp

n) : (cid:28)

n : (cid:28)n

(call)

Dans ensemble

evt(cid:28)lter

Negation

E ⊢ exp : (cid:28)

E ⊢ exp

E ⊢ exp in [exp

1 : (cid:28) : : : E ⊢ exp

n] : bool

1; : : : ; exp

n : (cid:28)

(set)

E...