Outils d’analyse statique et de vérification pour les ... · Outils d’analyse statique et de vérification pour les applications Java distribuées Rapport de stage. ... la vérification

Christophe [email protected]

DESS TELECOMAnnée 2003/2004

INRIA – Projet OASIS2004 route des LuciolesBP 9306902 Sophia Antipolis

Outils d’analyse statiqueet de vérification pour les

applications Java distribuées

Rapport de stage

Rapport de stage Outils d’analyse statique etde vérification pour les


Christophe Massol Année 2003-2004 Page 2 sur 27

REMERCIEMENTS

Je remercie tout particulièrement l’INRIA qui m’a permis d’effectuer un stage intéressant etenrichissant.

Je remercie également Monsieur Eric Madelaine ainsi que Madame Rabéa Boulifa pour toute leur aideapportée sur la compréhension du sujet ainsi que leurs précieuses explications.

Je remercie Virginie Legrand, ma compagne de bureau avec qui le stage a été un vrai plaisir. Je tienségalement à remercier tous les membres de l’équipe OASIS.

Enfin, je tiens à remercier le personnel de l’INRIA pour son accueil et sa sympathie.




SOMMAIRE

INTRODUCTION________________________________________________________4

1 Présentation de l’entreprise_____________________________________________5

2 Le projet OASIS______________________________________________________62.1 La librairie ProActive ___________________________________________________________ 6

2.2 Environnement d’analyse et de vérification __________________________________________ 7

3 Objectifs du stage_____________________________________________________83.1 Présentation du stage____________________________________________________________ 8

4 La plate-forme Vercors ________________________________________________94.1 Présentation ___________________________________________________________________ 9

4.2 Analyse de l’application_________________________________________________________ 104.2.1 Transformation du code source en un code intermédiaire _____________________________ 104.2.2 Analyse de la structure de l ‘application__________________________________________ 114.2.3 Analyse statique de l’application _______________________________________________ 12

4.3 eXtended Call Graph ___________________________________________________________ 13

4.4 Calcul des comportements _______________________________________________________ 15

5 Travaux effectués ____________________________________________________165.1 Génération d’un code intermédiaire d’une application utilisant la librairie ProActive________ 16

5.2 Collecte des informations sur la structure du réseau __________________________________ 175.2.1 Recherche des objets actifs ___________________________________________________ 175.2.2 Recherche du type et des paramètres de création ___________________________________ 175.2.3 Méthodes exposées par un objet actif ____________________________________________ 18

5.3 Collecte des informations pour chaque activité_______________________________________ 185.3.1 Analyse des primitives de création d’objets actif ___________________________________ 185.3.2 Identification de la nature des points d’appels______________________________________ 18

5.4 Génération du XMCG __________________________________________________________ 195.4.1 Implémentation ____________________________________________________________ 195.4.2 Point d’entrée de l’analyse ____________________________________________________ 205.4.3 Analyse du corps des méthodes locales à une activité ________________________________ 20

5.5 Avancement __________________________________________________________________ 245.5.1 Les fonctionnalités implémentées_______________________________________________ 245.5.2 Les fonctionnalités non terminées ______________________________________________ 245.5.3 Les problèmes ouverts _______________________________________________________ 24

CONCLUSION _________________________________________________________25

REFERENCES _________________________________________________________26




INTRODUCTION

Afin de développer mes connaissances avec profit et m’initier à la vie d’entreprise, l’enseignement duDESS réseau et télécommunication propose un stage de fin d’étude de 5 mois.

Parmi les nombreuses propositions, mon choix s’est porté sur l’INRIA, dans lequel on m’a permisd’approfondir le stage effectué l’an passé lors de ma fin d’étude d’IUP Miage. De par mon expérience acquisel’an dernier sur le sujet, j’ai pu être opérationnel rapidement, apporter des solutions aux problèmes soulevés l’anpassé, fixer de nouveaux objectifs ainsi que soulever de nouveaux problèmes.

J’ai évolué dans le projet OASIS, projet dont le but est d’offrir des outils pour la construction, l’analyse,la vérification et la maintenance d’applications réparties Java. J’ai été intégré dans l’équipe Vercors.




1 Présentation de l’entreprise

L’INRIA est un institut publique de recherche en informatique et automatique créé en 1967 par lesministères de la recherche, de l’économie, des finances et de l’industrie.Les buts de cet institut sont de réunir les compétences du dispositif de recherche français afin de développer lesnouvelles technologies qui sont un des moteurs important de notre économie, partager ses connaissances dans uncadre international, assurer la diffusion de son savoir, contribuer à la normalisation ainsi que de réaliser desexpertises dans le domaine informatique. Cet institut doit également réaliser des programmes de coopérationavec d’autres structures pour le développement des nouvelles technologies et réaliser des systèmesexpérimentaux.

Cette vocation envers la haute technologie se traduit par des publications de concepts et de connaissancesdans la littérature scientifique mais également par des logiciels et prototypes expérimentaux novateurs (commeexemple, nous pouvons citer la librairie ProActive – développée par le projet OASIS sur le site de SophiaAntipolis – qui facilite la programmation répartie Java entre plusieurs machines virtuelles). Pour mener à bientous ses projets, l’INRIA met en place des partenariats avec le CNRS, les écoles d’ingénieurs, les universités, lesindustries ainsi que des relations européennes et internationales.

Cet établissement est partagé en 6 sites indépendants qui lui permettent de renforcer sa présence sur leterritoire et de multiplier les partenariats. J’ai été intégré dans l’unité de recherche de Sophia Antipolis dirigéepar Michel Cosnard. Cette unité a été créée en 1982 dans la plus grande technopole européenne. Elle intègreaujourd’hui 455 personnes formant 28 équipes de recherche. Ces équipes couvrent des sujets très variés del’informatique et de l’automatique avec quatre thèmes principaux :

• Réseaux et systèmes ;• Génie logiciel et calcul symbolique ;• Interaction homme-machine, images, données et connaissances ;• Simulation et optimisation des systèmes complexes.

Une équipe de recherche est organisée autour de 10 à 25 scientifiques. Elle intègre des chercheurspermanents de l’INRIA mais elle peut également intégrer des ingénieurs, des étudiants en thèse ainsi que desstagiaires ponctuels venant de diverses écoles. Elle est dirigée par un directeur de projet (personne habilitée àdiriger des projets) et sa durée de vie est d’au plus douze ans.




2 Le projet OASIS

Le projet OASIS (Ref 18), créé par l’initiative d’Isabelle Attali, est un projet commun entre l’INRIA, l’I3Set l’UNSA. Son but est de proposer dans un contexte d’applications réparties des principes, techniques et outilspour la construction, l’analyse, la vérification et la maintenance de systèmes.

Le projet a été créé dans le contexte de l’explosion de l’Internet, du partage de l’information et del’avènement du langage Java. La problématique du projet est exprimée par la difficulté liée à la programmationet à la maintenance d’applications réparties. Les objectifs sont alors de définir une plate-forme d’aide à laprogrammation ainsi qu’une plate-forme de développement, d’analyse et de vérification d’applications répartiessur un réseau local (LAN), sur un système de clusters ou sur le réseau Internet.

2.1 La librairie ProActive

La librairie Java ProActive (Ref 17) est la solution de l’équipe OASIS face à l’absence de bibliothèquebasée sur la programmation de systèmes répartis. Elle est basée sur la JVM (Java Virtual Machine) Java de SUNet utilise le protocole meta-objet structuré sur la librairie RMI pour assurer le transport de l’information.

Concrètement, ProActive propose des primitives permettant de simplifier la programmationd’applications distribuées en Java et d’en garantir la sécurité (

Figure 1). Cette librairie introduit la notion d’objets actifs.

Figure 1: Communication ProActive

Un objet actif est un objet distribué par la librairie ProActive sur un réseau. Il peut alors effectuer desappels distants vers d’autres objets actifs sur le réseau ainsi que réceptionner des appels distants provenantd’autres objets actifs et y répondre. (

Figure 2).

Figure 2 : Communication distribuée

Les communications ProActive intègrent la notion de Futur. A chaque point d’appel à un objet actif enrésulte l’obtention d’un futur. L’appel est asynchrone puisque l’appel n’est pas bloquant jusqu’à ce quel’utilisateur est besoin de la valeur renvoyée dans le Futur.

JVM B

Objet distribuéA

Objet distribuéB

Objet distribuéC

LibrairieProActive

JVM AGarantie de sécurité

Object actifObjet passif




Figure 4 : Objet Actif

Un objet actif dispose d’une queue de requêtes (appels passés par l’intermédiaire de la librairieProActive) représentée sur la

Figure 4 par l’objet Body.La librairie ProActive permet à l’utilisateur de définir le comportement des objets actifs. Le

comportement de ces objets est caractérisé par la politique de traitement vis-à-vis des appels distants. Il est définipar l’utilisateur par la surcharge sur tout objet actif de la méthode runActivity liée à la librairie ProActive.

2.2 Environnement d’analyse et de vérification

L’équipe OASIS développe également un environnement d’analyse et de vérification de programmes dansle cadre de systèmes Java distribués : la plate-forme VERCORS (VERification de modèles pour COmposantsRépartis communicants, surs et Sécurisés). Cette analyse repose sur la définition de modèles comportementauxdéfinissant le comportement des objets de l’application. En utilisant des outils de vérification basés sur cesmodèles comportementaux, des analyses peuvent être conduites afin de s’assurer du bon comportement(recherche d’inter-blocages, propriétés de sûreté).

Ces développements reposent sur les travaux des membres de l’équipe (Ref 3): définition d’une sémantiquepour ProActive, d’un modèle intermédiaire (système d’automates paramètrés) pour exprimer les comportements,analyse statique permettant de déterminer certaines propriétés des applications.

Proxy Object

Body




3 Objectifs du stage

3.1 Présentation du stage

L’objectif est de développer un ensemble d’outils permettant, à partir d’un code source Java, l’analyse ducomportement d’une application utilisateur ainsi que la vérification de propriétés comportementales. Ceprototype se compose d’outils existants modifiés afin de leur intégrer la sémantique distribuée ProActive ainsique d’outils développés au sein de l’équipe Vercors. Le but est alors d’intégrer aux outils existants lareconnaissance du langage distribué ProActive et d’interfacer les outils existants à ceux développés par l’équipe(calculs des comportements, génération de modèles comportementaux paramètrés, outil d’instanciation).

Lors d’un premier stage, nous avons étudié les différents modules présents dans l’outil existant Banderaafin d’y intégrer les informations concernant la mécanique des applications réparties ProActive. Bandera, outilsd’analyse et de vérification de programme reposant sur le langage intermédiaire Jimple intégré à la plate-formeSoot, dispose de modules de parsing, de slicing, d’abstraction et de vérification de code ainsi que d’une interfacegraphique simple et puissante permettant au plus grand nombre d’intégrer l’univers de la vérification deprogramme. Nous avons intégré à cet outil l’identification des points d’appel au langage ProActive. Nousétablissons la liste des objets actifs présents dans le code source Java utilisateur et identifions statiquement lespoints de communication répartie. Cette étude permet d’établir la structure du réseau distribué et de déterminer lanature des communications, locales ou distantes, d’un point d’appel précis pour en déduire l’utilisationéventuelle d’un futur ProActive.

L’objectif fixé cette année est tout d’abord de régler les problèmes ouverts soulevés lors du stageprécédent concernant l’analyse des objets actifs présent dans le code utilisateur. Cela nous permettra ensuited’exprimer toutes les informations récoltées lors de la phase d’analyse statique du code source (objets actifs,communication locale ou distante, reconnaissance des futurs) sous forme d’un graphe d’appel étendu structuréappelé XMCG (eXtended Method Call Graph). Cette structure est l’élément central sur lequel se fonde laconstruction du modèle comportemental d’un objet actif (Ref 1, Ref 2). Le prototype réalisé pendant le stage vapermettre d’avoir une première chaîne complète d’outils pour la construction de ce modèle à partir d’un codeProActive.




4 La plate-forme Vercors

4.1 Présentation

La plate-forme Vercors (Figure 5) a pour but l’analyse et la vérification des applications distribuéesutilisant la librairie ProActive. Son analyse repose sur le source Java du code utilisateur interprété dans unlangage intermédiaire proche du Bytecode, facile à analyser.

L’analyse statique du code source permet d’identifier la structure de l’application :• Les objets actifs créés par l’application ;• Les points de communication entre objets actifs ;• Les points d’appels distants ;• Les points d’utilisation des futurs.

Le calcul du comportement de l’application permet d’obtenir un modèle comportemental compositionnelparamétré. Les modèles comportementaux sont des systèmes de transitions représentant les actions et les étatsdes objets de l’application (Ref 1).

Ce modèle paramètré sera instancié par un outil spécifique d’instanciation permettant au moteur d’analysede valider les propriétés définies par l’utilisateur (recherche d’inter-blocage, test de sûreté, preuve de vivacité)(Ref 4).

Figure 5 : Plate-forme Vercors

Analyse de lastructure del’application

Calcul descomportements

Vérificationpar moteurd’analyse

Codeutilisateur

Objetsdistribués

Liens decommunication

Modèlecompositionnel

paramètré

Instanciation

Modèlecompositionnel

fini




4.2 Analyse de l’application

L’analyse statique de l’application va pouvoir nous renseigner dans un premier temps sur sa structure :Les objets actifs présent dans l’application, leurs types, leurs paramètres de création, leurs méthodes exposées.Elle va également nous renseigner sur tous les points d’appel de méthode, la problématique étant d’identifier despoints d’appel distant utilisant la mécanique ProActive. Pour finir, elle nous renseignera sur les pointsd’utilisation des futurs qui sont la aussi gérés par la librairie ProActive.

Le cœur du processus d’analyse (Figure 6) est basé sur des outils d’analyse existants :

• Bandera (projet de l’université de Santos, Kansas)Ce module (Ref 6, Ref 8) permet d’analyser un code source Java et de l’interfacer avec des vérificateurs demodèles comportementaux connus.

• Lande (projet IRISA, Rennes)Les outils du projet Lande (Ref 12) permettent d’affiner l’analyse du code et de produire une analyse de classesafin d’établir un graphe précis d‘appels de méthode.

• SootLa plate-forme Soot (Ref 13) propose un langage intermédiaire entre le Java et le Bytecode (le Jimple)permettant d’optimiser et d’analyser un code utilisateur. Cette plate-forme propose notamment l’outil Spark quipermet une analyse statique de pointeur.

Figure 6 : Analyse du code source Java

4.2.1 Transformation du code source en un code intermédiaire

Cette phase est principalement gérée par l’outil Bandera utilisant le langage intermédiaire Jimple de laplate-forme Soot. Bandera dispose d’une interface graphique et est particulièrement recommandée pour réalisernotre prototype Vercors de par son accessibilité au plus grand nombre.

Bandera

SourceJava

Parsing

RepresentationJimple

Slicing

Abstraction

Représentation interneSOOT

Analyse declasses

(LANDE)

XMCGGraph Modèle compositionnel

comportemental paramètré

Checker

Analysestatique desobjets actifs

Règlessémantiques




Bandera intègre un module de parsing de code permettant depuis un code source Java d’obtenir un codeintermédiaire Jimple. Il intègre également des modules de slicing et d’abstraction de code.

Dans cette phase, nous empêchons Bandera d’analyser la librairie ProActive, du fait qu'elle fait appel àde la génération dynamique de code, ce qui n’est pas gérable par Soot. Chaque appel à la librairie ProActivecontiendra seulement les informations d’appel de méthodes mais ne contiendra pas le corps de la méthodeassociée.

4.2.1.1 Le slicing (découpage de code)

Le slicing (découpage de code) est une méthode (Ref 7) permettant de supprimer les parties nonfonctionnelles d’un code utilisateur afin de diminuer l’espace d’états à analyser (la taille de l’arbre d’analyse).On va alors conserver seulement la partie du code sur laquelle agit la propriété qu’on souhaite vérifier et ne pastraiter de code superflu.

4.2.1.2 L’abstraction de donnée

A partir d’un code source Java, nous n’avons pas accès aux données dynamiques qui constituent leprogramme (Ref 9). Nous devons alors approximer les valeurs de celles-ci afin de pouvoir les traiterstatiquement et garantir le comportement du programme accompagné de cette approximation. Concrètement,l'abstraction permet de remplacer l'espace inconnu accordé à une variable du programme par un espace définirespectant le comportement du programme.

4.2.2 Analyse de la structure de l’application

Afin de pouvoir analyser une application répartie, nous devons connaître ses éléments distribués (objetsactifs). Nous établissons alors par étude statique la liste des types d’objets actifs constituant l’application et leursliens dans le réseau distribué (Figure 7).Un point de création d’objet actif peut être défini par deux primitives ProActive :

• newActive( ) ;La primitive newActive crée une instance d’objet d’actif.

• turnActive( ) .La primitive turnActive permet de passer un objet du stade passif au stade actif.

Un objet actif est défini par :• Son type ;• Ses paramètres de création ;• Ses méthodes exposées ;

Figure 7 : Structure du réseau distribué

Activité A Activité B

Activité A/B

Call_runActivity Call_runActivity

Call_foo

Call_foo




4.2.3 Analyse statique de l’application

Nous voulons déterminer dans le code utilisateur tout code faisant appel à la mécanique ProActive. Lespoints à considérer sont les appels de méthodes vers des objets actifs distants, le traitement des futurs ainsi que letraitement de la queue de requêtes. Cette analyse fait appel au moteur d’analyse de pointeur Spark afin dedéterminer la nature des instances pointées à chaque point de programme.

4.2.3.1 Spark : Outils d’analyse de pointeurs

L’analyse statique est une méthode d’étude de programme basée sur le code source et n’a donc pas accèsaux données réelles dynamiques représentant le programme. Cela se traduit par une approximation et desexpressions sur les données garantissant le comportement du programme.

Nous avons besoin, pour notre analyse du comportement d’un objet basé sur la librairie ProActive,d’étudier les pointeurs d’objets du programme utilisateur afin d’identifier leur appartenance éventuelle à lalibrairie ProActive. Un tel outil, travaillant sur une représentation Jimple, est présent dans la plate-forme Soot :Spark (Ref 16 et Ref 15).

Cet outil va nous permettre d’identifier les instances statiques associées à un pointeur. Cet outil vatravailler sur les points de création des objets.

Void foo(){1. Object a ;2. ….3. a = new A() ;4. a.foo() ;}

Figure 8 : Analyse statique du code source

Void foo(int i){1. Object a ;2. If( i == 0)3. a = new A() ;4. Else5. a = new B() ;6. a.foo() ;}

public class A{…}public class B{…}


Void foo(int i){1. A[] a ;2. For(int x=0 ; x<i ; x++)3. A[x] = new A() ;4. ….}





Sur la Figure 8, Spark va associer le point de création contenu dans la ligne 3 (new A()) au pointeur a.Lors de l’appel à a.foo() contenu dans la ligne 4, nous connaissons alors l’instance assocíée à a qui estreprésentée par le point de création new A().

Comme nous n’avons pas accès au contenu dynamique des pointeurs, il peut alors naître une imprécision.En effet, sur la Figure 9, le pointeur lors de l’appel situé à la ligne 6 est associé à deux points de créationdifférents. Dans ce cas, nous traitons séparément les deux possible afin de garantir le traitement de tous les caspossible de l’application.

Sur la Figure 10, nous traitons un cas différent. Ici, un point de création peut être associé à une ouplusieurs instances d’objets du même type. Il est alors statiquement impossible d’identifier précisément uneinstance.

4.3 eXtended Call Graph

Après avoir collecté toutes les informations contenues dans le code, nous allons les formaliser afind’avoir une vue de type distribuée. Cette structure sera sous la forme d’un graphe noeud-transition (Figure 11).

Dans une vue distribuée d’une application, chaque objet réparti définit une activité et chaque activité peutêtre liée à une autre activité. Cette vue est conforme à la vision ProActive puisqu’une activité est représentéedans ProActive par un objet actif donné et que ses interfaces de sorties sont ses méthodes publiques.

Nous construisons alors pour chaque objet actif, un graphe XMCG ayant pour point de départ la méthoderunActivity qui est l’équivalent de la méthode main pour un objet actif (la méthode traitant l’activité de l’objetactif).

4.3.1 Nœuds du graphe

Le graphe XMCG est défini suivant les nœuds :

• Ent(m, args)Le nœud Ent défini l’entrée dans le corps d’une méthode.Le paramètre m représente la signature de la méthode ;Le paramètre args représente les paramètre associé à la méthode.

• Call(m, c)Le nœud Call représente un appel de méthode (locale ou distante).Le paramètre m défini le nom de la méthode.Le paramètre c représente la classe mère contenant la méthode appelée.

• Pp(lab)Le nœud Pp représente un point du programme. Il peut servir à mettre en évidence un point de programme précisspécifié par l’utilisateur et qui doit être pris en compte dans le XMCG. Il peut définir également un point deretour avec condition pour représenter une boucle.Le paramètre lab représente le point de programme Jimple spécifique à traiter.

• Ret(val)Le nœud ret représente le nœud de retour d’une méthode.Le paramètre val définit la valeur typée à retourner.

• Serve(m, mode)Ce nœud représente le traitement des requêtes de la queue d’appels de l’objet actif. ProActive proposedifférentes primitives à l’utilisateur et différents modes de traitement (FIFO, Serve oldest…) afin de traiter lesrequêtes extérieures.Le paramètre m représente le nom de méthode à servir. Ce paramètre peut être null dans le cas d’un appel detraitement sans filtre de nom de méthode.Le paramètre mode représente le mode de traitement des requêtes.

• Use(futur)




Le nœud use défini le point de dernière utilisation d’un futur. Cette utilisation peut conduire à une attente deréponse du client associé à ce futur.

4.3.2 Transitions du graphe

Nous distinguons deux types de transitions : les transitions d’appel de méthode et les méta transition.Une méta transition (Figure 11, Figure 14) lie le nœud courant à un ou plusieurs nœuds destination. Leur codefonctionnel commun est contenu à l’intérieur de la transition. Ce code est sous forme d’une liste d’instructionsJimple et contient toutes les informations concernant les variables, les instructions goto et instructions If.

De plus, les nœuds spécifiques Call et Serve, nœuds caractérisant un appel de méthode, contiennentégalement une liste de liens vers les corps des méthodes à traiter. Ces liens sont définis comme étant desCallTransitions et peuvent avoir quatre types différents :

• Remote(o, m, args, futur)La transition remote représente un appel distant à une méthode d’un objet actif. Cet appel étant distant, cettetransition n’est pas reliée à un corps de méthode, puisque nous traitons dans chaque XMCG une seule activité.Le paramètre o défini l’instance de l’objet appelé.Le paramètre m défini la signature de la méthode précise appelée.Le paramètre args représente les différents arguments passés en paramètre de l’appel de méthode.Le paramètre futur défini le futur affecté par l’appel à l’objet distant.

• Local(o, m, args, var)La transition local représente un appel local à une méthode de l’activité (méthode appartenant à l’objet actif localou à l’un de ses objets passifs associés). La méthode étant interne à l’activité, la transition pointe vers un nœudent définissant le corps de la méthode appelée.Le paramètre o défini l’instance de l’objet appelé.Le paramètre m défini la signature de la méthode précise appelée.Le paramètre args représente les différents arguments passés en paramètre de l’appel de méthode.Le paramètre var défini la variable résultant de l’appel de méthode.

• Unknown(o, m, args, var, futur)La transition unknown représente l’incertitude lors de l’appel de méthode. En effet, en analyse statique, nouspouvons être en présence, en un point donné, avec plusieurs points de création liés au pointeur sur l’objet appelé.Cette incertitude peut nous spécifier qu’à un point d’appel peut être associé soit un objet actif distant, soit unobjet de l’activité courante.

En présence de cette incertitude, nous nous devons de traiter tous les cas possible et donc, de traiter lecas d’un appel distant et le cas d’un appel local. Cette transition pointera donc vers un nœud ent définissantl’appel à une méthode locale mais incorporera également la notion de futur afin de représenter également le casd’un appel distant.Le paramètre o défini l’instance de l’objet appelé.Le paramètre m défini la signature de la méthode précise appelée.Le paramètre args représente les différents arguments passés en paramètre de l’appel de méthode.Le paramètre var défini la variable résultant de l’appel à la méthode locale.Le paramètre futur défini le futur résultant de l’appel à l’objet distant.

• Static(m, args, var)La transition static représente un appel de méthode statique. Nous avons choisi de ne pas traiter le corps desméthodes statiques. Nous prenons seulement en compte le type de retour de la méthode.Le paramètre m défini la signature de la méthode précise appelée.Le paramètre args représente les différents arguments passés en paramètre de l’appel de méthode.Le paramètre var défini la variable résultant de l’appel à la méthode statique.




Figure 11 : XMCG de l’activité Philosophe

4.4 Calcul des comportements

Le calcul des comportements résulte d’une phase de transformation du XMCG par des règles sémantiquesvers un modèle comportemental paramètré. Le modèle devra être instancié par un moteur d’instanciationdéveloppé au sein de l’équipe afin de générer un modèle comportemental fini. Ce modèle fini pourra être analysépar un model checker classique.




5 Travaux effectués

Figure 11 : Modules étudiés

Lors de ce stage, j’ai travaillé sur toutes les étapes permettant d’obtenir un graphe XMCG completdécrivant toutes les activités d’un programme réparti utilisant la librairie ProActive :

• Parsing d’un code Java utilisant la librairie ProActive ;• analyse de la structure du réseau distribué ;• analyse des primitives ProActive rencontrées dans le code ;• génération du graphe XMCG.

5.1 Génération d’un code intermédiaire d’une application utilisant lalibrairie ProActive

Bandera, dans sa version initiale, ne reconnaît ni les applications réparties, ni les traitements effectuéspar la librairie ProActive. En effet, la librairie ProActive créé des classes à la volée et du code dynamique non-analysables par Bandera. De plus, le traitement de la librairie ProActive est à écarter dans notre approche. Eneffet, nous utilisons des propriétés générales garanties par l’implantation des primitives ProActive comme basenotre sémantique ; il n’est donc pas nécessaire de les analyser (Figure 1).

La première étape a été de permettre à Bandera d’analyser le code utilisateur d’un programme utilisantProActive en écartant l’analyse de la librairie ProActive. Nous pouvons alors simplifier le dialogue entre deuxobjets actifs par l’envoi de requêtes entre ces deux objets et le traitement effectué par chaque objet (en occultantla liaison avec l’API ProActive). Nous analysons donc le code utilisateur ainsi que le comportement des objetsactifs vis-à-vis des requêtes qu’ils reçoivent en identifiant les primitives fournies par la bibliothèque ProActivequi décrit ce comportement.

Bandera

SourceJava

Parsing

RepresentationJimple

Slicing

Abstraction

Représentation interneSOOT

Analyse declasses

(LANDE)

XMCGGraph Modèle compositionnel

comportemental paramétré

Checker

Analysestatique desobjets actifs

Règlessémantiques




Concrètement, cette modification crée une méthode (objet SootMethod dans la représentation Jimple) définissantla primitive appelée mais ne lui associe aucun corps de méthode (objet body dans la représentation Jimple). Celaaura des répercussions sur toute la suite de l’analyse et des modifications spécifiques au traitement de cesprimitives ont dû être effectuées sur toutes les étapes.

5.2 Collecte des informations sur la structure du réseau

L’analyse de la structure du réseau résulte de la connaissance des objets actifs présents sur le réseau et deleurs liens de communication.

5.2.1 Recherche des objets actifs

L’identification des objets actifs dans le code utilisateur se traduit par la recherche des primitivesProActive de création d’objets actifs dans le code Jimple. Nous parcourons la structure Jimple afin de descendreau niveau des corps de méthodes (objet Body contenu dans l’objet SootMethod). Nous parcourons alors leslignes de code Jimple (une ligne de code est représentée par un objet Stmt) et identifions les lignes contenant uneexpression traduisant un appel de méthode. Ce test est effectué par l’appel à la méthode containsInvokeExpr()pour chaque ligne de code.

Pour chaque objet actif, nous devons établir :• Son type ;• Ses paramètres de création ;• Sa liste de méthodes exposées.

5.2.2 Recherche du type et des paramètres de création

Dans le cas d’une création utilisant la primitive newActive, le type est contenu dans le premierargument de la primitive. Une analyse statique d’obtenir la liste des types possibles. En effet, l’analyseur statiqueSpark contenu dans la plate-forme Soot va nous permettre d’identifier tous les points de création possibles pource premier paramètre. Nous en déduisons alors les types qui en découlent.

Dans le cas d’une création utilisant la primitive turnActive, le type est contenu dans les points antérieursde création de l’objet à rendre actif. Par une analyse de pointeur sur l’alias de l’objet nous en déduisons une listepotentielle de types.

5.2.2.1 Cas 1 : Utilisation de la primitive turnActive()

L’utilisation de la primitive turnActive() entraîne la création antérieure d’une instance Java de l’objetpar l’appel de la méthode Java new(). Il suffit alors statiquement d’établir les points de création résultant del’instance d’objet à rendre active afin de d’établir une liste de types d’objets possibles pour cet objet actif. Il fautenfin déterminer le type des paramètres de création d’objet utilisés dans la primitive new() afin d’obtenir lesparamètres de création associés à l’objet actif.

L’utilisation d’un outil d’analyse de pointeurs permet facilement de faire cette analyse.

5.2.2.2 Cas 2 : Utilisation de la primitive newActive()

Ce cas de figure est bien plus compliqué que le précédent. Deux problèmes différents interviennent :• Les paramètres de création de l’objet actif se trouvent intégrés dans un tableau d’objets ;• La primitive Java new() de création d’objet n’est pas présente dans le code (elle est en effet

exécutée par la mécanique ProActive).

En effet, dans l’appel précédent, la primitive Java new() étant intégré dans le code utilisateur, le moteurd’analyse de pointeur a pu alors parcourir et analyser l’objet actif en question. Ici, aucun appel de création Java




n’est visible par l’analyseur de pointeur et la primitive newActive(), appartenant à la librairie ProActive n’est pasanalysée. Deux solutions se présentaient à nous :

• Analyser les primitives newActive() prises en compte par l’analyseur de pointeurs lors de chaquepasse (pour la première passe, seules les primitives présentes dans la classe principale, les objetspassifs et les objets actifs créé par la primitive turnActive() seront donc traités). Puis, analyser pourchaque primitive newActive ses paramètres de créations contenu dans le tableau d’objet (analysestatique) pour pouvoir intégrer dans le code la primitive de création Java new() représentant lacréation de l’instance de l’objet actif. Cet ajout a pour seul effet de permettre à l’analyseur depointeur de faire son travail sur les classes actives. Pour finir, nous lançons le moteur d’analyse depointeur pour une nouvelle passe. Si lors de cette nouvelle passe, de nouvelles primitivesnewActive étaient découvertes, nous recommencerions alors leur analyse ;

• Analyser simplement les primitives avec une analyse de pointeur très simple et sans utiliser lemoteur d’analyse qui est très lourde. Cela est possible si le tableau des paramètres, la création desparamètres, l’ajout des paramètres au tableau et la création de l’objet actif sont faits dans la mêmeméthode Java. Il y aura donc qu’une seule passe pour la mécanique d’analyse de pointeur.

La deuxième solution, malgré sa forte restriction, nous a paru plus raisonnable dans un premier tempsau vu des performances de l’analyseur statique contenu dans Soot. En effet, pour deux classes simples contenantpeu de codes, l’analyse peut prendre dix minutes pour une passe.

5.2.3 Méthodes exposées par un objet actif

Les méthodes exposées par un objet actif sont les méthodes publiques contenues dans la classe mère et lesméthodes publiques présentes dans les classes héritées. La structure Jimple nous permet, à partir d’une classedonnée (objet SootClass dans la représentation Jimple), d’avoir accès à la liste de ses méthodes et également à laclasse Java éventuellement héritée. L’objet SootClass associé à un objet actif a été déterminé dans le pointprécédent.

5.3 Collecte des informations pour chaque activité

Nous avons besoin d’identifier les points du code utilisateur faisant appel à la mécanique ProActive dufait que nous voulons modélisons la mécanique ProActive indépendamment de l’activité.Les points faisant appel à la mécanique ProActive sont :

• Les primitives newActive et turnActive ; définissant un point de création d’un objet actif ;• Les points d’appels distants ;• L’utilisation d’un futur ;• Les primitives serve gérant les requêtes distantes.

5.3.1 Analyse des primitives de création d’objets actifs

Nous faisons ici appel à l’analyseur de pointeur Spark en modifiant son analyse pour pouvoir différencierles créations d’objet java new() des créations d’objets actifs. L’idée est donc d'arrêter l’analyse lors d’appels auxméthodes de création de la librairie ProActive et de lui faire assimiler qu’un appel à la méthode newActive outurnActive est équivalent à un appel Java « new » - Ceci pour identifier les points de création d’objets actifs. Enprésence d’une de ces primitives, Spark crée donc un nœud d’allocation AllocNode contenant la méthode decréation. Il est alors facile pour chaque allocation de différencier allocation ProActive et allocation locale.

5.3.2 Identification de la nature des points d’appels

Lors de l’identification d’un point d’appel de méthode (Objet InvokeStmt en langage Jimple), Spark nousretourne le ou les points de création correspondant au pointeur sur l’objet appelé. En analysant les points decréation, nous identifions trois cas :

• Tous les points de création associés sont des appels standard new ;L’appel est alors forcément un appel local.




• Tous les points de création associés sont des appels aux primitives de ProActive ;L’appel fait appel à la mécanique ProActive.

• Il y a mixité entre points de créations standard et ProActive.L’appel peut être local ou distant, nous traitons alors simultanément les deux cas. Ces deux cas seront égalementtraités par le modèle comportemental. La résolution de la mixité (qui se traduira par soit un appel local, soit unappel distant) sera soit résolu par le processus d’instanciation, qui fournira un modèle comportemental fini , soitpar le model checker lui-même (dans ce cas, le model checker prend en entrée un modèle paramétré).

Un problème est ici à soulever : Dans le cas de l’identification d’un appel à un objet actif, nous nepouvons pas identifier précisément si cet objet actif est local ou externe à l’activité.

5.4 Génération du XMCG

Le graphe d’appel XMCG (eXtended Method Call Graph) représente toutes les informations collectéespour chaque activité (un objet actif représente une activité) -Ref 2 -. La méthode ProActive représentant lecomportement d’une activité est la méthode runActivity(). Par défaut, elle traite les requêtes reçues par un objetactif suivant la politique FIFO (la première requête entrée dans la queue est la première servie). Cette méthodepeut être surchargée par l’utilisateur afin qu’il définisse sa propre politique de comportement. Le graphe a donc,pour référence, la méthode runActivity().

5.4.1 Implémentation

Le package Java xmcg (Figure 12) résulte de l’implémentation du module de construction du grapheXMCG. La classe principale est la classe Xmcg. Elle doit être crée en lui spécifiant une liste d’objets actifs (lastructure définissant un objet actif est la classe ActiveObject qui a été créée lors de la phase d’analyseprécédente). La phase de construction du Xmcg construit pour chaque objet actif, un objet Module qui est lepoint d’entrée d’une activité. Le module analyse le corps de l’activité et construit pour chaque méthode analyséede l’activité, un objet LocalMethod contenant l’analyse de ces corps de méthodes. Les objets Ent, Pp, Ret, Serve,Call, Use héritent de la class AbstractNode (qui implémente l’interface Node) et représentent les actionscontenues dans le code.

La représentation des variables contenues dans le code est garantie par les objets Local (représentantune variable locale) et Futur (représentant un Futur ProActive) qui héritent de l’objet abstrait AbstractVar (quiimplémente l’interface englobante Var).

Les objets Branchee et To servent à l’analyse le code Jimple.




Figure 12 : Package xmcg

5.4.2 Point d’entrée de l’analyse

5.4.2.1 Stratégie par défaut

Par défaut, l’utilisateur peut ne pas implémenter la méthode runActivity. La stratégie est alors de traiteravec une politique FIFO les requêtes entrantes. Statiquement, toutes les méthodes exposées par l’objet actifpeuvent être appelées. Nous construisons alors la méthode runActivity et toutes les méthodes exposées quipeuvent potentiellement être servies.

5.4.2.2 Stratégie utilisateur

Dans le cas où l’utilisateur a implémenté la méthode runActivity, l’étude de l’activité débute par l’analysedu contenu de cette méthode.

5.4.3 Analyse du corps des méthodes locales à une activité

Une méthode est représentée dans notre XMCG par un objet LocalMethod et son point d’entrée est lenœud Ent qui contient la signature de la méthode ainsi que l’objet contenant la méthode. Nous parcouronsensuite les lignes Jimple et, pour chaque action, nous construisons le nœud associé.

Les actions Jimple qui nous intéressent ici sont les appels de méthodes, les utilisations d’un futur, lesretours de méthode.

5.4.3.1 Traitement des appels de méthodes

Nous construisons à ce stade un nœud Call qui traduit l’appel à un nom de méthode donné. Une étudestatique sur cet appel de méthode va nous permettre de déterminer s’il est statique, local, distant ou indéterminé.

Il est facile de déterminer si l’appel est de type statique. En effet, la structure Jimple contient plusieurstypes d’appel de méthode dont le type d’appel statique. Pour ce type d’appel, nous associons donc uneCallTransition de type statique au nœud Call.

Dans le cas d’un appel classique, nous devons faire appel à une analyse spécifique. Nous devonsdéterminer, par analyse de pointeur, la nature de l’appel (local, distant ou indéterminé) et nous devons également

xmcg

Module

Node

AbstractNode

Call Serve Ent Ret Use Pp

Var

AbstractVar

Local Futur

Branchee

LocalMethod

To

CallTransition

ActiveObject




déterminer, par analyse de classe, les types dynamiques d’objets pouvant potentiellement contenir la méthodeappelée.

Comme expliqué dans la partie 5.3, Spark nous renseigne sur la nature de l’instance référencée par lepointeur sur instance contenu dans l’appel de méthode. Spark nous retourne une liste de points de créationcorrespondante au pointeur donné. Nous analysons la liste de points de créations retournée et déterminons leurnature (un point de création d’objet actif étant caractérisé par l’appel à une primitive ProActive).

Après avoir déterminé la nature de l’appel, nous devons déterminer les types d’objet dynamiquespotentiellement appelés afin d’établir la liste des méthodes potentiellement appelées. Cette analyse fait appel àl’analyse de classe de l’outil Reqs du projet Lande. Cet outil nous retourne une liste de types d’objetsdynamiques pour un pointeur donné.

Ayant la liste des méthodes candidates à l’appel et la nature de l’appel, nous établissons une liste d’objetsCallTransition liée au nœud Call.

5.4.3.2 Sélection d’une requête

Le traitement d’une requête utilise la primitive ProActive serve(). Par analyse statique du nom deméthode appelé et de la nature du pointeur référençant l’instance appelée (5.3), nous pouvons déterminer l’appelà une primitive serve(). La requête serve peut avoir plusieurs formes :

• Serve(nom de méthode)Traitement de la requête correspondant au nom de méthode donné.

• Serve(liste de noms de méthode)Traitement des requêtes correspondant aux noms de méthode donnés.

• ServeAll(nom de méthode)Traitement de toutes les requêtes correspondant à l’appel de la méthode spécifiée en paramètre.

• ServeOldest()Traitement de la plus ancienne requête.

• ServeOldest(nom de méthode)Traitement de la plus ancienne requête correspondant à l’appel de la méthode spécifiée en paramètre.

• ServeYoungest()Traitement de la plus récente requête.

• ServeYoungest(nom de méthode)Traitement de la plus récente requête correspondant à l’appel de la méthode spécifiée en paramètre.

Statiquement, nous distinguons deux types d’information dans l’appel serve : Le ou la méthode à serviret la stratégie à adopter pour sélectionner la requête à servir. Nous distinguons trois types de sélection de larequête : serveAll, serveOldest, serve et serveYoungest. Ces types sont intégrés à l’objet CallTransition résultantdu traitement d’une requête et doivent être définis lors de sa création.

Nous distinguons également deux stratégies de traitement de requête : stratégie de filtrage par le nom deméthode et stratégie de traitement de toutes les requêtes. Dans le cas où le nom de méthode serait spécifié, nouspouvons déterminer statiquement que ce traitement de requête résultera d’un appel de méthode identifié par celuipassé en paramètre. Nous construisons alors un objet CallTransition de type local (le traitement des requêtes estlocal), pour la méthode correspondant à la définition passée en paramètre.

Dans le cas où aucun nom de méthode ne serait passé en paramètre, nous traitons alors tous les caspossibles de requêtes. Nous construisons alors autant de transitions d’appel CallTransition que de méthodesexposées par l’objet actif.

5.4.3.3 Détermination de l’utilisation d’un futur

Un futur est retourné pour chaque appel à un objet actif. L’intérêt des futurs est que l’appel à l’objet actifn’est pas bloquant, mais l’accès au contenu du Futur est bloquant. Il nous faut alors déterminer dans notreanalyse le premier point d’utilisation d’un Futur, point bloquant. Par analyse statique, nous déterminons une listede premier point d’utilisation pour chaque objet Futur.




Pour chaque appel distant (déterminé grâce au moteur Spark comme vu dans la partie 5.3), nousconstruisons un objet Futur dans notre arbre XMCG. Ce Futur est caractérisé par son point de création qui estl’appel distant en question.

Lorsque l’utilisateur a besoin d’avoir le contenu d’un pointeur ou d’une variable, nous devons établir si cepointeur est un futur, autrement dit, si ce pointeur résulte d’un appel distant. Par analyse de pointeur et avecl’aide du moteur Spark, nous pouvons déterminer si ce pointeur résulte d’un appel distant. En effet, en prenant enparamètre un pointeur sur résultat d’un appel distant et le pointeur à élucider, Spark peut nous dire si le secondest un alias du premier.

L’utilisation d’un futur est traduite par le nœud Use qui contient l’objet Futur correspondant.

5.4.3.4 Traitement des transitions entre les noeuds

Chaque nœud contient des pointeurs sur les nœuds potentiels suivant le nœud courant et contientégalement des informations sur le code Jimple présent entre chaque nœud.

Figure 14 : Transitions

L’algorithme de traitement du code Jimple associé à une méthode est le suivant :• Pour chaque ligne de code Jimple, nous déterminons sa nature. Nous nous intéressons à des lignes

spécifiques : Goto, Appel de méthode ou retour de méthode.• En présence d’un appel de méthode ou d’un retour de méthode, nous construisons son nœud associé

et le gardons en mémoire comme nœud courant.• En présence d’un nœud If,• Pour tout autre ligne de code Jimple, nous ajoutons cette ligne à tous les nœuds courants.• Pour déterminer quels sont les nœuds pointant une ligne de code donnée, nous utilisons le mécanisme

des branchements :• En présence d’un Goto (branchement), nous créons un Objet branche du Xmcg. Cet objet

associe à une ligne de code donnée, tous les nœuds qui la pointe. Nous associons donc laligne de code pointée par l’instruction Goto à tous les nœuds courants lors de l’appel àl’instruction Goto.

• A chaque traitement d’instruction Jimple, nous recherchons si un objet Branche lui estassocié. Si oui, alors nous associons aux nœuds courants, les nœuds déterminés par laBranche.

5.4.3.4.1 Cas spécifique des boucles

Une boucle (If, For) doit être traitée spécifiquement comme un nœud. Comme en assembleur, une boucleest caractérisée par un point de programme spécifique sur lequel boucler suivant une condition. Notre nœudpermettant de représenter une boucle est le nœud Pp (program point).

En Jimple, une boucle est représentée de la façon suivante :




Représentation Jimple

1 Goto 32 …..3 If condition goto 14 …

Représentation Java

While(a<b){ ….}….

Figure 14 : Représentation des boucles en langage Jimple

Un test sur l’instruction pointée par une instruction Goto permet de déterminer si nous sommes enprésence d’une boucle (Figure 14). Nous construisons alors un nœud Pp correspondant à la condition formuléedans l’instruction If. Nous construisons alors pour l’instruction qui succède à l’instruction If, une nouvellebranche afin de déterminer les nœuds pointant vers la sortie de la boucle.




5.5 Avancement

5.5.1 Les fonctionnalités implémentées

- Bandera parse en code Jimple une application utilisant la librairie ProActive ;- Les objets actifs présents dans le code sont identifiés ;- La nature des liens de communication (distante, locale ou indéterminée) peut être reconnu par l’outil Spark ;- La structure du graphe XMCG est implémentée.

5.5.2 Les fonctionnalités non terminées

- Prise en compte des variables futurs et locales dans le XMCG ;- Exportation du XMCG en vu d’être traité à travers les règles sémantiques.

5.5.3 Les problèmes ouverts

- Déterminer dans le cas d’un appel à un objet actif, si cet objet est local ou externe à l’activité.




CONCLUSION

Lors de ce stage, j’ai eu la chance de pouvoir approfondir le travail commencé l’année dernière.Connaissant déjà le domaine d’étude et l’univers de l’entreprise, j’ai pu être opérationnel rapidement afin de meconsacrer tout d’abord aux problèmes soulevés l’an passé, puis à la construction du prototype de la plate-formeVercors.

Grâce à ma connaissance et mon expérience sur le sujet, j’ai pu collaborer efficacement avec l’équipe,apporter rapidement des solutions et soulever de nouveaux problèmes ouverts afin de faire progresser la plate-forme Vercors.

De plus, j’ai été plongé dans le monde de la recherche informatique, monde à la pointe de l’avancéeinformatique. J’ai beaucoup appris des membres de l’équipe qui n’ont pas hésité à répondre à mes nombreusessollicitations et à m’aider au travers de mon stage. J’ai pu aussi élargir mes connaissances en assistant à nombresde colloques effectués par des invités prestigieux plus intéressants les uns que les autres organisés au sein del’institut.

Cette expérience m’a également initiée à la vie en entreprise, liée aux engagements, à la tenued’objectifs à long et court terme sous un rythme soutenu.

Pour finir, je tiens à remercier le docteur Eric Madelaine de m’avoir fait confiance pour réaliser cetravail très théorique, travail ne correspondant pas à mon cursus.




REFERENCES

Ref 1 : Parameterized Models for distributed Java Objects, Tomas Barros, Rabéa Boulifa, Eric Madelaine

Ref 2 : Génération de modèles comportementaux applications distribuées, Rabéa Boulifa, 2004

Ref 3 : Preuves de propriétés de comportement de programmes ProActive, Rabéa Bouliffa, Eric Madelaine, mai2002

Ref 4 : I. Attali, T. Barros, E. Madelaine: Formalisation and Verification of the Chilean Electronic InvoiceSystem, SCCC'04, Arica, Chili, Nov 2004

Ref 5 : The Bandera Tools for motel-checking Java source code : A user’s manual, John Hatcliff, OksanaTkachuk, march 2001

Ref 6 : Bandera : Extracting Finite-state Models from Java Source Code, Matthew B. Dwyer, John Hatcliff,Shawn Laubach, Corina S. Pasareanu, Robby, Hongjun Zheng, 2000

Ref 7 : Slicing software for model construction, John Hatcliff, Matthew Dwyer, Hongjun Zheng, December1999

Ref 8 : Using the Bandera tool set to model-check properties of concurrent Java software, John Hatcliff,Matthew Dwyer

Ref 9 : Tool-supported Program Abstraction for Finite-state Verification, Matthew Dwyer, John Hatcliff, RobyJoehanes, Shawn Laubach, Corina Pasareanu, Robby, Willem Visser, Hongjun Zheng, in Proceedings of the23rd International Conference on Software Engineering, May, 2001

Ref 10 : Expressing Checkable properties of dynamic systems : The Bandera specification language, James C.Corbett, Matthew B. Dwyer, John Hatcliff, Robby, June 2001

Ref 11 : Constructing Compact Models of Concurrent Java Programs, James C. Corbett, In Proceedings of theInternational Symposium on Software Testing and Analysis (ISSTA), March, 1998.

Ref 12 : Class Analysis of Object-Oriented Programs through Abstract Interpretation, Thomas Jensen and FautoSpoto

Ref 13 : Soot - a Java Optimization Framework, Raja Vallée-Rai, Laurie Hendren, Vijay Sundaresan, PatrickLam, Etienne Gagnon and Phong Co, September 1999

Ref 14 : Jimple : Symplifying Java Bytecode for analyses and transformations, Raja Vallée-Rai, Laurie J.Hendren

Ref 15 : Spark Options, Ondrej Lhotak, February 2003




Ref 16 : Spark: A flexible points-to analysis framework for Java, Ondej Lhoták, February 2003

Ref 17 : Towards Seamless Computing and Metacomputing in Java

D. Caromel, W. Klauser, J. Vayssiere, pp. 1043--1061 in Concurrency Practice and Experience, September-November 1998

Ref 18 : OASIS : Objets actifs, Sémantique, Internet et sécurité, Juin 1999

Ref 19 : Automatic determination of communication topologies in mobile systems, A. Venet, 1998

Documents

Outils d’analyse statique et de vérification pour les ... · Outils d’analyse statique et de vérification pour les applications Java distribuées Rapport de stage. ... la vérification