IFT6315 - Analyse dynamiquedufour/cours/ift6315/docs/2-dynamique.pdf · • Calculs complexes mais sans impact sur l’exécution ... plusieurs types d’analyses dynamiques

Bruno [email protected]

IFT6315 - Analyse et compréhension de programmes

Analyse dynamiqueIntroduction

Bruno Dufour - Université de Montréal

Rappel - Analyse dynamique

• L’analyse dynamique permet:• d’obtenir des résultats plus précis pour une ou

plusieurs exécutions concrètes• d’obtenir de l’information de nature temporelle à

propos de l’exécution• d’obtenir de l’information sur la fréquence ou

l’importance de certains événements• Ex : une méthode est appelée très souvent,

beaucoup de tableaux sont créés, etc.

3


Comparaison des techniques 4

• Considère toutes les exécutions possibles

• Calculs complexes mais sans impact sur l’exécution

• Considère certaines exécutions concrètes, généralisation difficile

• Impact sur l’exécution proportionnel à la quantité d’information recueillie

Analyse statique Analyse dynamique


Approximation du comportement 5

Analyse statique sûre (safe)

Analysedynamique

Comportement réel

Analyse statiquenon-sûre (unsafe)


Utilité de l’analyse dynamique

• Compréhension de programmes• Détection de phases d’exécution• Analyse de l’utilisation des ressources

• Analyse de performance• Analyse de l’utilisation de la mémoire

• Optimisations JIT• Débogage• Analyses de tainte (sécurtité)• Analyse de couverture• Détection d’invariants probables• etc.

6


Analyse dynamique - préoccupations • Comment recueillir l’information ?

• Transformations du code source / compilé (instrumentation)

• Modifications de l’environnement d’exécution • Utilisation d’une interface de profilage

• Comment éviter (minimiser) le surcoût?• Comment s’assurer que les résultats ne sont pas

affectés par les observations ?• ex: changements au comportement du système

• Comment choisir les entrées / exécutions representatives ?

• Comment s’assurer de la validité des résultats?

7


Interface de profilage 8

• Fourni un mécanisme d’inspection du programme en cours d’exécution

• Permet de s’arrimer, par exemple, à une machine virtuelle pour intercepter des événements ou contrôler l’exécution

• Exemples :• Java Virtual Machine Tool Interface (JVMTI) • Valgrind• Émulateurs• Program counters (CPU)• etc.


Interface de profilage 9

JVM JVMTI

Agent de profilage

class%loading

method%entry

method%exit

classestransformées

Programme

Événements

Callbacks


Environnement d’exécution modifiés 10

• Pour les langages interprétés, il est souvent possible de modifier un interprete existant afin de collecter l’information désirée

• Exemples :• JikesRVM (aka Jalapeno VM) - JVM de recherche

écrite en Java• aussi SableVM, Maxine, ...

• Modifications d’interprete commerciaux (e.g. V8 pour JS, ...)


Instrumentation

• L’instrumentation consiste à ajouter des fragments de code (sondes, ou probes) à un programme de façon à ajouter la génération des résultats d’analyse à son comportement initial

• Le programme s’exécute dans son environnement normal

• Souvent nécessaire, e.g. WebSphere est distribué avec sa version de J9 (IBM JVM)

• Au cours de l’exécution, les sondes sont exécutées en plus du programme d’origine recueillent l’information nécessaire

11


public'static'int[]%append(int%i,%int[]%a)%{%%%%int[]%r;

%%%%%%%%

%%%%%%%%

%%%%%%%%

%%%%

}

if%(a%!=%null)%{%%%%%%%%%%%%r%=%new%int[a.length%+%1];%%%%%%%%%%%%System.arraycopy(a,%0,%r,%1,%a.length);}%else%{%%%%%%%%%%%%r%=%new%int[1];}r[0]%=%i;

%%%%return%r;

Instrumentation 12

Analysis.recordEntry(“append”);

Analysis.recordAlloc(“int[]”,%a.length%+%1);

Analysis.recordCall(“System.arraycopy”);

Analysis.recordAlloc(“int[]”,%1);

Analysis.recordExit(“append”);


public'static'int[]%append(int%i,%int[]%a)%{%%%%int[]%r;

%%%%%%%%

%%%%%%%%

%%%%%%%%

%%%%

}

%%%%try%{%%%%%%%%

%%%%%%%%

%%%%%%%%

%%%%

%%%%}%finally%{%%%%%%%%Analysis.recordExit(“append”);%%%%}

if%(a%!=%null)%{%%%%%%%%%%%%r%=%new%int[a.length%+%1];%%%%%%%%%%%%System.arraycopy(a,%0,%r,%1,%a.length);}%else%{%%%%%%%%%%%%r%=%new%int[1];}r[0]%=%i;

%%%%return%r;

Instrumentation 13

Analysis.recordEntry(“append”);

Analysis.recordAlloc(“int[]”,%a.length%+%1);

Analysis.recordCall(“System.arraycopy”);

Analysis.recordAlloc(“int[]”,%1);

Analysis.recordExit(“append”);


Instrumentation

• Types d’instrumentation• Code source (source-to-source) : transformations du

code source (haut niveau)• Code compilé (ex: bytecode)

• Stratégie• Hors-ligne : instrumenter avant de débuter l’exécution

• génère une nouvelle version du programme instrumenté

• ex : AspectJ, Soot, etc.• En-ligne : instrumenter durant l’exécution

• le code est transformé à mesure qu’il est chargé par l’environnement d’exécution

• ex: valgrind, Steamloom, Dyko, etc.

14


Instrumentation en-ligne

• Comment intercepter le chargement du code ?• En Java, plusieurs stratégies :

• JVMTI : permet d’intercepter le chargement de toutes les classes (sauf les tableaux)

• java.lang.Instrument : permet d’intercepter le chargement de certaines classes (au moins toutes les classes de l’application)

• ClassLoader personnalisé : permet de charger des classes dans un ClassLoader spécifique et de les modifier avant le chargement

• Modification de la JVM• Modifications du code d’entrée/sortie (I/O)

15


Pièges de l’instrumentation 16

• Le code inséré par instrumentation ne doit pas appeler du code instrumenté sans une garde

• Possibilité de causer de la récursion sans borne• Attention aux modifications dans java.lang.Object!

• Certaines classes sont difficiles à instrumenter• Java : Object, String, tableaux, etc.

• Toutes les classes utilisées ne sont pas forcément disponibles à l’avance

• Java : Proxy génère des classes à l’exécution!• Certaines méthodes (ex: native) ne peuvent pas être

instrumentées


Récursion infinie... 17

public%class%Object%{%%%%public%Object()%{%%%%%%%%Analysis.recordEntry(“Object.Object()”);%%%%}}

public%class%Analysis%{%%%%public%static%void%recordEntry(String%method)%{%%%%%%%%Node%n%=%new%Node(method);%%%%%%%%...%%%%}}

Oops! Va appeler Object(), puis Node(), puis Object(), etc.


Proxy - exemple 18

public interface Foo { public Object bar(Object obj);}

public class FooImpl implements Foo { public Object bar(Object obj) { return obj; }}

Source: Oracle (avec lègères modifications)


Proxy - exemple 19

public class TracingProxy implements InvocationHandler { private Object obj;

public static Object newInstance(Object obj) { return java.lang.reflect.Proxy.newProxyInstance( obj.getClass().getClassLoader(), obj.getClass().getInterfaces(), new TracingProxy(obj)); }

private TracingProxy(Object obj) { this.obj = obj; }

public Object invoke(Object proxy, Method m, Object[] args) throws Throwable { Object result; try { System.out.println("before method " + m.getName()); result = m.invoke(obj, args); } finally { System.out.println("after method " + m.getName()); } return result; }}

Source: Oracle (avec lègères modifications)Bruno Dufour - Université de Montréal

Proxy - exemple 20

public static void main(String[] args) { Foo foo = (Foo) TracingProxy.newInstance(new FooImpl());

foo.bar(null); }}

before method barafter method bar

Le type de l’objet Foo ici est $Proxy0, une classe générée durant l’exécution (et qui implémente l’interface Foo, et délègue à FooImpl).

Source: Oracle (avec lègères modifications)


Clonage des classes 21

• Technique consistant à dupliquer systématiquement toutes les classes d’un système de façon à faciliter l’instrumentation :

Source: Factor et. al., “Instrumentation of Standard Libraries in Object-OrientedLanguages: the Twin Class Hierarchy Approach”, OOPSLA’04


Clonage des classes

• Permet d’instrumenter les classes difficiles ou impossibles à instrumenter de façon portable

• Les classes copiées peuvent être modifiées sans restriction

• L’application s’exécute uniquement dans la copie• Le code original est disponible à partir du code

instrumenté• Permet d’éviter certaines sources d’interférence

entre le code d’instrumentation et le code de l’application

22


Pièges du clonage des classes

• classes/interfaces spéciales (Serializable, Thread, Exception, etc.)• class MyException extends TCH.java.lang.Exception

• Reflexion (Class.forName)• Class.forName(“MyClass”) → “TCH.MyClass”

• Transformations illégales• public String toString() → public TCH.String toString()

• Exceptions implicites• try { ... } catch (NullPointerException e) →

try { ... } catch (TCH.NullPointerException e)

• Méthodes “native”• System.currentTimeMillis() →

TCH.System.currentTimeMillis()

23


Collecte de l’information 24

InterfacesModifications

de l’environnement

Instrumentation

Information disponible

Limitée par l’interface Compléte Accessible à

l’application

Difficulté Facile Complexe Moyenne

Impact Moyen à élevé Minimal Minimal à moyen


Perturbations de l’exécution 25

• L’analyse dynamique peut perturber l’exécution de façon

• directe : le comportement de code d’analyse peut directement affecter l’information recueillie

• ex: le temps d’exécution mesuré inclut le temps passé à exécuter les sondes

• indirecte : le code d’analyse affecte indirectement le comportement mesuré/observé du système

• ex: invalidation de la mémoire cache cause un ralentissement, ordonnancement différent des fils d’exécution (threads)


Types d’analyse dynamique

• En ligne (Online)• Les résultats sont calculés au cours de l’exécution• Des calculs complexes peuvent perturber

l’exécution• Seulement l’information pertinente est enregistrée

• Hors ligne (Offline)• Les résultats sont calculés après l’exécution (post-

mortem) à l’aide de traces d’exécution• L’impact du calcul sur l’exécution est diminué• La quantité d’information à enregistrer peut être

énorme (et proportionnelle au temps d’exécution)

26


Précision de l’analyse dynamique

• Analyse exacte• Enregistre toute l’information pertinente lors d’une

exécution• Analyse par échantillonnage

• Enregistre un échantillon de l’exécution périodiquement

• Deux stratégies de base• Par interruption / minuteur : un échantillon pour

chaque période (ex: 100ms)• Par compteurs : un échantillon à chaque N

occurrences (ex: 1 échantillon à chaque 10 appels)

27


Échantillonnage par compteurs 28

Source: Arnold & Ryder, “A Framework for Reducing the Cost of Instrumented Code”, PLDI’01

Back-edge retourne au code d’origine

if%(globalCounter%<=%0)%{%%%%takeSample();%%%%globalCounter%=%resetValue;}globalCounterQQ;

Condition d’échantillonnage :


Échantillonnage par compteurs 29

• Le framework permet d’utiliser l’échantillonnage pour plusieurs types d’analyses dynamiques

• Le code est dupliqué, avec une version instrumentée (instrumented) et une version qui ne contient que des gardes (checking)

• Les gardes sont insérées à chaque entrée de méthode et sur chaque back-edge

• Si la condition de profilage est vraie, la garde branche au code instrumenté

• Les back-edges retournent au code non-instrumenté pour borner le temps passé dans le code instrumenté

• Implique que le CFG instrumenté est un DAG


Variation - Moins de duplication 30

• top-node : noeud non-instrumenté pour lequel aucun chemin depuis l’entrée ne contient de noeud instrumenté

• les gardes qui branchent à un top-node doivent être retirées

• pour chaque arc depuis un top-node vers un noeud instrumenté, on doit ajouter une garde sur l’arc correspondant dans le code non-instrumenté

• bottom-node : noeud non-instrumenté depuis lequel aucun autre noeud instrumenté n’est atteignable



Retirer plus de noeuds ?• Peut augmenter le nombre de gardes nécessaires :

• En ne retirant que les top-nodes et bottom-nodes, le nombre de gardes est borné par le nombre initial (et peut diminuer dans certains cas)

31



Alternative - Aucune duplication 32



Résultats - Performance 33

Variation-0 = Duplication complèteVariation-2 = Aucune duplication

* indique une différence ≤ 0.5%



Résultats - Précision 34



Résultats détaillés - javac 35

Precision = 93.8%



Alternative - Par interruptions 36

Precision

intervale = 10ms intervale = 30 000



Problèmes de l’échantionnage 37

void!M()!{!!!!!!!!while!(...)!{!!!!!!!!getfield!//!Long!sequence!of!non6calls

!!!!!!!!putfield

!!!!!!!!...

!!!!!!!!getfield

!!!!!!!!putfield

!!!!!!!!call_1();!//!Two!short!calls

!!!!!!!!call_2();

!!!!}

}

Source: Arnold & Grove, “Collecting and Exploiting High-Accuracy Call Graph Profiles in Virtual Machines”, CGO’05

Une stratégie naïve peut manquer ces appels à cause de la faible probabilité de prendre un échantillon lors de leur exécution.


Échantillonnage hybride 38

Source: Arnold & Grove, “Collecting and Exploiting High-Accuracy Call Graph Profiles in Virtual Machines”, CGO’05


Profilage des chemins d’exécution 39

Source: Ball & Larus, “Efficient Path Profiling”, MICRO’96

• Chaque chemin est encodé par un numéro unique entre 0 et le nombre de chemins possibles

• pour l’instant, nous allons ignorer les cycles• Les arcs sont instrumentés de façon à produire le numéro du

chemin emprunté dans un registre, qui peut alors être utilisé comme index dans une table de profilage

• Simples opérations arithmétiques sur un sous-ensemble des branches


Approche 40



Choisir l’emplacement des sondes 41

• En général, plusieurs options possibles• solution (a) requiert seulement au plus 2 calculs par chemin, (b)

et (c) en requièrent plus• Hypothèse : il existe au préalable un ensemble de poids sur les

arcs qui représentent la fréquence d’exécution attendueSource: Ball & Larus, “Efficient Path Profiling”, MICRO’96


Étapes de l’algorithme 42

• Assigner les numéros à chaque chemin de façon unique

• Utiliser un arbre couvrant (spanning tree) pour sélectionner les arcs à instrumenter

• Sélectionner l’instrumentation appropriée• Dériver le chemin après l’exécution depuis son

numéro


1. Assigner les numéros 43

ENTRY

EXIT

Arc ajouté pour des raisons techniques (étape 2)

Source: Ball & Larus, “Efficient Path Profiling”, MICRO’96Bruno Dufour - Université de Montréal

2. Sélection des arcs 44

• De façon informelle, tente de “pousser” les calculs sur les cordes (arcs qui n’appartiennent pas à l’arbre couvrant) sans changer les valeurs pour les chemins empruntés

• Considère le cycle créé en ajoutant chaque corde à l’arbre couvrant

• Calcule Inc(e) en utilisant la somme des valeurs des arcs composant le cycle (négation dans le sens inverse de l’arc)



3. Sélection de l’instrumentation 45

• Approche de base• [r = 0] : Initialisation à l’entrée (ENTRY)• [r += Inc(c)] : Mise à jour pour chaque corde c

instrumentée• [count[r]++] : Enregistrement du profil à la sortie

(EXIT)• Optimisation pour une corde c :

• [r=Inc(c)] ssi c est la première corde sur chaque chemin de ENTRY à EXIT contenant c

• [count[r + Inc(c)]++] ssi c est la dernière corde sur chaque chemin de ENTRY à EXIT contenant c


3. Sélection de l’instrumentation 46



4. Dériver un chemin 47

R = 3

R = 1

derivePath(R) v ← ENTRY while v != EXIT find e = v → w with maximum Val(e) ≤ R v ← w R ← R - Val(e)


• Pour chaque back-edge v → w, ajouter un arc ENTRY → v et un arc w → EXIT

• Eliminer les back-edges du graphe et appliquer l’algorithme précédent

• Instrumenter chaque back-edge avec [count[r]++; r = 0]• Le cas v = w doit être traité spécialement


Gestion des cycles 48



Gestion des cycles - Exemple 49

Source: Ball & Larus, “Efficient Path Profiling”, MICRO’96Bruno Dufour - Université de Montréal

Évaluation - Performance 50



Analyse de la mémoire

• Identification des fuites de mémoire (memory leaks)• Analyse d’objets de tas (heap)

• Nombre/taille/etc des objets• Classification de la mémoire utilisée• Connectivité/structure des objets• etc.

51


Utilisation des octets 52

Source: N. Mitchell & G. Sevitsky, “The Causes of Bloat, The Limits of Health”, OOPSLA’07

1"tableau"(surdimensionné)"contenant1"objet"String"et"ses"4"caractères


Rôle des octets dans les objets 53

Source: N. Mitchell & G. Sevitsky, “The Causes of Bloat, The Limits of Health”, OOPSLA’07Bruno Dufour - Université de Montréal

Agglomération d’objets en structures 54


Têtes"de"collec9ons

Tableau"deréférencesEntrée"de"liste

Objets"contenus


Rôle des objets dans les collections 55


Le rôle des octets dans les collections 56

+



La signature de « santé mémoire » 57


Classfication des octets 58

Données réelles

Coûts dûs à la machine virtuelle

Coûts d’agglomération

Coûts dûs aux pointeurs

Coûts dûs aux valeurs primitives



Résultats 59


Évolution et échelle 60



Collection de collections d’octets 61Linked

List

TLinkedList

Array

101 102 103 104Taille"interne


Analyses JIT

• JIT = Just-in-time (juste à temps)• L’interprétation pure du code est trop lente• Les interpréteurs modernes effectuent de la

compilation durant l’exécution• Les compilateurs JIT utilisent de l’information

dynamique pour guider les optimisations (feedback-directed optimisations, ou FDO) qui permet :

• de sélectionner les optimisations les plus profitables• d’effectuer des optimisations qui ne sont pas

possibles statiquement• d’invalider certaines optimisations si la situation

change

62


Exemples d’optimisations de JIT

• Incorporation de méthodes (inlining): permet d’éviter un appel en remplaçant l’appel par le code de la méthode appelée

• Restructuration du code: utilise l’information sur la fréquence d’exécution pour maximiser la localité sur le chemin le plus souvent emprunté

• Versionnement du code: génère des versions spécialisées d’un même fragment de code à utiliser dans différents contextes

• et bien d’autres…

63


Profilage et JITs 64

Source: Suganuma et al, “An Empirical Study of Method Inlining for a Java Just-In-Time Compiler”, JVM’02

• Inlining seulement appliqué aux méthodes courtes (code plus court que la séquence d’appel côté appelant)

• Propagation de constantes / copies de base

• Inlining plus agressif

• Analyse par flot de données

• Passe additionnelle pour la génération de code

• Analyse d’échappement (escape analysis)

• Allocation sur la pile (stack allocation)

• Ordonnancement des instructions


Inlining - stratégie statique 65

• Pour un budget donné, rejeter une méthode pour incorporation si

• le nombre de variables résultant de l’incorporation excède un seuil, ou

• la taille estimée du code résultant excède un seuil, ou

• la taille estimée du code de la méthode à incorporer dépasse un seuil, ou

• évite de passer tout le temps disponible sur une longue méthode

• l’appel n’a jamais été exécuté et n’est pas contenu dans une boucle


Impact sur le temps de compilation 66


La taille du code cause une augmentation significative du temps d’analyse


Impact sur la performance 67


~50% du gain total


Inlining - stratégie par profilage 68

1. Identification de la distribution des sites d’appels• Construit un graphe d’appels partiel à partir des

méthodes exécutées fréquemment (hot)• Calcule un ratio d’importance pour chaque arc en

fonction du site d’appel enregistré




2. Identification des chemin pour incorporation• Traverse les chemins en sens inverse (à partir des feuilles)• La fréquence (hotness) du parent est ajustée pour tenir

compte de l’incorporation des enfants en fonction des ratios calculés en 1

• Une portion de la contribution d’un enfant est ajoutée au parent

• Ces ratios sont obtenus par instrumentation sélective3. Requête d’incorporation

• Pour les chemins fréquents identifiés en 1 & 2, une requête est placée pour l’incorporation

• Les requêtes sont persistantes pour éviter les oscillations



4. Requêtes de recompilation• La liste de méthodes fréquemment exécutées est

traversée à nouveau pour identifier des opportunités de recompilation

• Certaines méthodes peuvent maintenant être sous le seuil à cause des réajustements en 3 et seront rejetées

• Les méthodes pour lesquelles un seul site d’appel existe et qui seront la cible d’inlining seront aussi rejetées


Identifier les méthodes courtes

• Problème : le profilage par échantillonnage peut facilement manquer certains courtes méthodes, qui sont les meilleurs cibles pour l’incorporation

• Le JIT identifie et incorpore aussi les “petites” méthodes

• La taille estimée de leur code compilé est inférieure au code nécessaire pour effectuer l’appel dans l’appelant et l’appelé (prologue, épilogue et séquence d’instructions au site d’appel).

71


Évaluation - Stratégies

• Static• Profilage statistique mais aucune instrumentation• Stratégie statique employée

• Profile-1• Stratégie statique non utilisée (sauf pour les très petites et petites

méthodes)• Stratégie conservatrice (toutes les méthodes incorporées doivent

apparaître dans la liste des méthodes fréquemment exécutées)• Profile-2

• Version plus aggressive de Profile-1• Hybrid

• Profile-1, puis Static tant que le budget n’est pas épuisé• Offline

• Profile-1, mais le profil est collecté au préalable

72


Évaluation - Temps de compilation 73



Évaluation - Taille du code 74



Évaluation - Performance 75


Structures d’appels


Traces d’exécution

• Enregistre certains événements survenus lors de l’exécution

• Exécution d’instructions / blocs de base / branches• Appels de méthodes• Lecture / écriture de valeurs en mémoire• Etc.

• Une trace peut contenir plusieurs types d’événements• Peut facilement atteindre plusieurs GB pour des

exécutions relativement courtes• La nature des traces permet de développer des

techniques de compression très efficaces

77


Arbre d’appels

• Une trace d’exécution contient habituellement au moins les appels effectués lors de l’exécution

• souvent entrées / sorties de méthodes• peut contenir d’autres événements en plus des

appels• Une trace peut facilement être convertie en un arbre

d’appels• Représente tous les appels de façon hiérarchique• Conceptuellement équivalent à un graphe d’appels

qui utilise un contexte distinct par invocation d’une méthode

78


Arbre d’appels 79

Source: Zhuang et. al., “Accurate, Efficient, and Adaptive Calling Context Profiling”, PLDI’06

ENTER%AENTER%BENTER%CENTER%ELEAVE%EENTER%ELEAVE%ELEAVE%CLEAVE%BENTER%DENTER%CLEAVE%CLEAVE%DENTER%BENTER%CENTER%ELEAVE%EENTER%ELEAVE%ELEAVE%CLEAVE%BENTER%DENTER%CENTER%ALEAVE%ALEAVE%CLEAVE%DLEAVE%A

Trace:


Graphe d’appels dynamique

• Un graphe d’appels dynamique représente les appels entre méthodes effectués lors d’une ou plusieurs exécutions concrètes

• Comme dans un graphe d’appels statique, les noeuds représentent les méthodes et les arcs les appels entre méthodes

• Peut être obtenu par analyse spécialisée ou par agrégation d’un arbre d’appels

80


Graphe d’appels 81



Arbre de contextes d’appels

• Un arbre de contextes d’appels (Calling Context Tree, ou CCT)[Ammons et al, PLDI’97] est une représentation des appels plus compacte qu’un arbre d’appels mais plus précise qu’un simple graphe d’appels

• L’arbre est agrégé par chaîne d’appels (invocation dans son contexte d’appel) et non par méthode comme pour un graphe

• En général, plus qu’un noeud par méthode

82


Arbre de contextes d’appels (CCT) 83



Construction d’un CCT à l’exécution 84

• Il est aussi possible de construire un CCT directement durant l’exécution (et non par agrégation d’un arbre)

• Considérons un appel de D par C• s’il existe déjà un noeud pour D dans les enfants de C,

ce noeud sera passé à D lors de l’appel et réutilisé• sinon, D est appelée pour la première fois dans ce

contexte• rechercher un noeud pour C dans les ancêtres de C.

Si un tel noeud est trouvé, D est un appel récursif et le noeud existant est réutilisé.

• sinon, créer un nouveau noeud pour D et l’ajouter comme enfant de C.

• La chaîne des parents n’est traversée que lors du premier appel à une méthode dans un contexte donné.


Construction du CCT - Performance 85

Source: Ammons et al, “Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling”, PLDI’97


Performance - Algo. similaire en Java 86

Source: Sarimbekov et al, “Complete and Platform-Independent Calling Context Profiling for the Java Virtual Machine”, ENTCS’11

Couverture


Analyse dynamique et couverture

• Dans certains cas, l’analyse dynamique sert à étudier une exécution précise

• Débogage, performance, etc.• Autrement, on doit s’assurer que les résultats sont

représentatifs• Couverture du code adéquate• Entrées représentatives d’après le comportement

attendu du programme

88


Couverture

• La couverture est une mesure d’exhaustivité du code touché par une ou plusieurs exécutions concrètes

• Idéalement, la couverture devrait être exprimée en fonction de tous les chemins d’exécution possibles

• En pratique, le nombre de chemins possibles est trop grand pour être utilisé.

• On utilise des approximations.

89


Couverture des instructions

• Nécessite que chaque instruction du programme soit exécutée au moins une fois

• Un critère de couverture assez faible :public!int!foo(int!x,!int!y)!{

!!!!if!(x!!=!0!&&!y!!=!0)

!!!!!!!!y=x+1;

!!!!return!y;

}

• L’entrée foo(1,1) exécute toutes les instructions, mais le cas où y est retourné sans modification n’est jamais exécuté.

90


Couverture des décisions / branches

• Nécessite que chaque décision prenne chaque valeur possible au moins un fois (en général vrai ou faux)

• Les conditions incluent les boucles (while, for, do-while, etc.), les instructions conditionnelles (if-else, switch)

• Implique la couverture des instructionspublic int foo(int x, int y) {

if (x != 0 && y != 0)

y=x+1;

return y; }• Il faudrait au moins 2 entrées, par exemple :

• foo(0, 1), foo(1, 1)

91


Couverture des conditions

• Nécessite que chaque condition qui fait partie d’une décision prenne chaque valeur possible au moins un fois (en général vrai ou faux)public int foo(int x, int y) {

if (x != 0 && y != 0)

y=x+1;

return y;

}• Il faudrait au moins 2 entrées, par exemple :

• foo(0, 0)• foo(1, 1)

92


Couverture des conditions

• La couverture de conditions n’implique pas la couverture de branches :public int foo(int x, int y) {

if (x != 0 && y != 0)

y = x+1;

return y;

}• Considérez les entrées suivantes :

• foo(0, 1)• foo(1, 0)

• Chaque condition prend les deux valeurs possibles, mais l’instruction ‘y = x+1’ n’est jamais exécutée

93


Couverture des branches/conditions

• Requiert que chaque décision prenne toutes les valeurs possibles, et que chaque condition d’une décision prenne toutes les valeurs possibles

• Combinaisons des deux approches précédentes• Problème : certaines valeurs peuvent en masquer

d’autrespublic int foo(int x, int y, int z) {

if (x != 0 && (y != 0 || z < 0))

y=x+1;

return y;

}• Pour l’entrée foo(0,1,1), y!=0 peut masquer z<0

94


Couverture de conditions multiples

• Requiert que toutes les combinaisons de conditions dans toutes les décision soient couvertes au moins une fois :

• Implique toutes les approches précédentespublic int foo(int x, int y) {

if (x != 0 && y != 0)

y=x+1;

return y;

}• Il faudrait au moins 4 entrées, par exemple :

• foo(0,0), foo(1,0), foo(0,1), foo(1,1)

95


Où trouver les entrées?• Définir des entrées manuellement

• Limité à des programmes simples• Utiliser les tests de l’application

• Permettent l’analyse dynamique de bibliothèques (aucun point d’entrée)

• Enregistrer des entrées lors d’exécutions réelles et les rejouer

• Générer des entrées au hasard• “fuzzing”• random test generation (ex: Randoop)

• Exploration dirigée (ex: concolic execution : DART, Cute, etc.)

96

Génération de tests aléatoires


Génération de tests aléatoires

• Idée générale :• Générer des entrées aléatoirement• Vérifier que le programme se comporte

correctement pour ces entrées• Plusieurs études ont montré l’efficacité des tests

aléatoires peut être comparable à d’autres techniques plus coûteuses dans certains cas

• les évaluations se concentrent généralement sur de petits programmes et mesurent la couverture du code

98


Randoop• Feedback-directed random testing

• Pacheco et al, “Feedback-directed Random Test Generation”, ICSE’07

• Permet d’éviter les tests redondants et illégaux

99

Set!s!=!new!HashSet();

s.add(“abc”);

assertTrue(s.equals(s));

Date!d!=!new!Date(2012,!2,!27);

assertTrue(d.equals(d));

Date!d!=!new!Date(2012,!2,!27);

d.setMonth(61);


Date!d!=!new!Date(2012,!2,!27);

d.setMonth(61);

d.setDay(5);


Set!s!=!new!HashSet();

s.add(“abc”);

s.isEmpty();

assertTrue(s.equals(s));

Illégal

Illégal

UtileUtile

Redondant


Randoop - Approche

• Construire des tests unitaires incrémentalement à partir de séquences de méthodes

• Exécuter les séquences aussitôt qu’elles sont générées (feedback)

• permet de détecter les séquences invalides• permet de favoriser les séquences qui génèrent de

nouveaux états pour les objets créés

100


Randoop - Approche 101

Source: Pacheco & Ernst, “Randoop: Feedback-Directed Random Testing for Java”, OOPSLA’07


Randoop - Contrats 102

• Contrats de méthodes• Pas de NullPointerException lancée

lorsqu’aucun paramètre n’était null• Pas de AssertionError lancée

• Contrats d’objets• o.equals(o) retourne vrai• o.equals(o) ne lance pas d’exception• o.hashCode() ne lance pas d’exception• o.toString() ne lance pas d’exception

• D’autres contrats peuvent être spécifiés par l’utilisateur


Randoop - Exemple de contrat violé 103

public-static-void!test1()!{!!!LinkedList!l1!=!new!LinkedList();!!!Object!o1!=!new!Object();!!!l1.addFirst(o1);

!!!TreeSet!t1!=!new!TreeSet(l1);!!!Set!s1!=!Collections.unmodifiableSet(t1);

!!!Assert.assertTrue(s1.equals(s1));!//"oops!!}


Randoop - Algorithme 104

• while time limit has not been reached• Create a new sequence snew

• Randomly pick a public method m(T1...Tk):Tret

• For each Ti, pick a value vi for the parameter‣ Ti is primitive : pick at random from a predefined set

(-1, 0, 1, ‘a’, true, etc.)‣ Ti is reference :

- Pick a value from an existing sequence- Add a new sequence and pick its value- Pick null

• Create new sequence snew = s1; ...; sk; vnew = m(v1...vk)• if snew was previously constructed, continue

• Classify the sequence snew


Randoop - Classification

• Violation de contrat ?• La séquence est rapportée à l’utilisateur

• Séquence redondante ?• La séquence est éliminée• Enregistre l’ensemble de tous les objets créés durant

la génération de séquences• Une séquence est redondante si tous les objets créés

lors de son exécution sont présents dans cet ensemble (d’après equals)

• Sinon, la séquence est ajoutée à la liste de séquences disponibles pour la génération

• Des filtres sont appliqués pour éviter d’étendre des séquences invalides

105


Randoop - Filtres

• Exceptions : élimine les tests qui génèrent des exceptions (sans violer de contrat) avant la fin de l’exécution

• Souvent une indication d’une précondition non-respectée

• Null : élimine les tests qui utilisent null comme valeur intermédiaire

106

Object!o!=!new!Object();

LinkedList!l!=!new!LinkedList();

l.add(null);!//!null!statique

Object!o!=!returnNull();!//!null!dynamique

LinkedList!l!=!new!LinkedList();

l.add(o);


OCAT

• Jaygarl et al, “OCAT: Object Capture based Automated Testing”, ISSTA’10

• Extension de Randoop qui utilise de vrais objets capturés lors d’exécutions normales

• D’autres objets sont générés aléatoirement comme pour Randoop

• Les objets peuvent aussi être mutés pour augmenter la couverture

107

Exploration dirigée


Exécution symbolique

• Généralisation de l’exécution traditionnelle (concrète)• Concept clé : permettre l’utilisation de valeurs

symboliques• Chaque entrée du programme est représentée par

une valeur symbolique (ex: α)• Les variables du programme vont recevoir des

valeurs calculées à partir de constantes ou de valeurs symboliques

• La sémantique des opérations du langage est étendue pour inclure les valeurs symboliques

• ex: les expressions manipulent des polynômes contenant des valeurs symboliques

109


Exemple 110

function!sum(a,!b,!c)!{!!!!var!x!=!a!+!b;

!!!!var!y!=!b!+!c;

!!!!var-z!=!x!+!y!6!b;

!!!!return!z;}

a b c x y z

1 3 5

4

8

9


Exemple 111

function!sum(a,!b,!c)!{!!!!var!x!=!a!+!b;

!!!!var!y!=!b!+!c;

!!!!var-z!=!x!+!y!6!b;

!!!!return!z;}

a b c x y z

α β γ

α+β

β+γ

α+β+γ!


État et conditions

• L’état d’un programme au cours d’une exécution inclut

• le compteur d’instruction (instruction en cours)• les valeurs de toutes les variables

• Après un branchement conditionnel (ex: if), l’état devra aussi contenir une condition de chemin (path condition), ou pc

• pc : condition booléenne• dépend seulement des valeurs symboliques (et non

pas des variables du programme)• conjonction d’expressions symboliques• initialement true, et raffinée au cours l’exécution

112


Branchements conditionnels

• La condition d’un branchement est une expression booléenne q = R ≥ 0, où R est un polynôme de valeurs symboliques

• L’évaluation de la condition d’une branche modifie la valeur de pc

• branche then : pc ← pc ⋀ q• branche else : pc ← pc ⋀ ¬q

• L’évaluation de chaque branche procède indépendamment avec la valeur de pc modifiée

• Intuitivement, un “fork” dans l’exécution• Les exécutions forment un arbre

113

✔


Exemple 114

function!f(a,!b,!c)!{!!!!var!x=0,!y=0,!z=0;

!!!!if-(a)!!!!!!!!x!=!62;

!!!!if-(b!<!5)!!!!!!!!if!(!a!&&!c)!!!!!!!!!!!!y!=!1;

!!!!!!!!z!=!2;

!!!!assert-(x+y+z!!=!3);}

a = α, b = β, c = γ,x = 0, y = 0, z = 0

α ¬α

x = -2

β < 5 β ≥ 5

z = 2

✔

α ⋀ (β < 5)

✔

α ⋀ (β < 5)

β < 5 β ≥ 5

✔

¬α ⋀ (β ≥ 5)¬α ⋀ γ ¬α ⋀ ¬γ

z = 2y = 1

✘

z = 2

¬α ⋀ (β < 5) ⋀ ¬γ

¬α ⋀ (β < 5) ⋀ γ


Implémentation 115

• Les solutionneurs SMT/SAT modernes permettent d’implémenter l’exécution symbolique de façon efficace

• Les implémentations utilisent souvent des heuristiques pour améliorer la performance

• ex: rechercher une paire p et ¬p pour identifier rapidement les contraintes sans solution

• Les implémentations doivent aussi faire certaines hypothèses quant à la nature des valeurs et expressions générées

• ex: expressions linéaires, polynômes, etc.


DART - Exploration dirigée

• DART = Directed Automated Random Testing• Godefroid et al, “DART : Directed Automated

Random Testing”, PLDI’05• Idée principale

• Générer des entrées aléatoires pour un programme• Exécuter le programme avec les entrées concrètes

tout en accumulant des contraintes symboliques sur le chemin emprunté

• Utiliser les contraintes pour déterminer d’autres entrées qui permettent d’emprunter les chemins non-explorées

116


DART - Exemple 117

int!double(int!x)!{!! return!2!*!x;!}

void!test_me(int!x,!int!y)!{!!int!z!=!double(x);

!!if!(z==y)!{! !!if!(y!==!x+10)! !!!!abort();!/*!error!*/

!!}

}

main(){% int%v1%=%randomInt();% int%v2%=%randomInt();% test_me(v1,v2);}

Étape 2 : Génération d’un driver

Étape 1 : Extraction d’interface• Arguments passés au point

d’entrée (spécifié par l’utilisateur)• Variables et fonctions externes


DART - Exemple 118


void!test_me(int!x,!int!y)!{!!int!z!=!double(x);!!if!(z==y)!{! !!if!(y!==!x+10)! !!!!abort();!/*!error!*/

!!}

}

x = 36y = 99

Valeurs concrètes

Contraintes symboliques

z == 2 * x

Étape 3 : Exploration dirigée

z != y

Trouver une solution à y = 2 * xex: x=1, y=2

Exécution 1

z = 72


DART - Exemple 119



!!}

}

x = 1y = 2

Valeurs concrètes


z == 2 * x


z == y

Trouver une solution à y = 2 * x ⋀ y == x + 10ex: x=10, y=20

Exécution 2

z = 2

y != x + 10


DART - Exemple 120



!!}

}

x = 10y = 20

Valeurs concrètes


z == 2 * x


z == y

Exécution 2

z = 20

y == x + 10Erreur détectée!


Exécution dirigée 121

• Permet de diriger systématiquement l’exécution vers certains chemins

• Basée sur la collecte de contraintes symboliques pour chacune des branches

• Une contrainte est inversée pour forcer l’exécution de l’autre alternative d’une branche

• Un solutionneur est utilisé pour les entrées pour la prochaine exécution

• Le processus est répété jusqu’à ce que tous les chemins soient couverts

• Peut ne jamais terminer, il faut donc limiter l’exploration dans la plupart des cas


Contraintes complexes• DART fait l’hypothèse que seules les contraintes linéaires

peuvent être résoluesvoid!foo(int!x,int!y)!{

!!!!int!z!=!x*x*x;

!!!!if!(z!==!y)!{

!!!!!!!!abort();!/*!error!*/

!!!!}

}

• Initialement, x = 3, y = 7• z = 27 (concret) et z = x3 (abstrait)• La valeur de z ne peut être gérée de façon abstraite• La valeur concrète (27) est utilisée• Lors de la prochaine exécution, y = 27 et l’erreur est

atteinte

122


Contraintes complexes (2)

• Certaines contraintes ne peuvent être résolues statiquement :void!obscure(int!x,!int!y)!{!!!if!(x!==!hash(y))!abort();!!!return!0;}

• Il n’est pas possible de générer deux valeurs x et y statiquement tel que x == hash(y).

• Par contre, il est facile de générer une valeur pour x si on fixe la valeur de y

• DART peut donc explorer les deux branches de la fonction obscure en variant la valeur de x

123

Documents

IFT6315 - Analyse dynamiquedufour/cours/ift6315/docs/2-dynamique.pdf · • Calculs complexes mais sans impact sur l’exécution ... plusieurs types d’analyses dynamiques