Note publique d'information : La validation des logiciels est une partie cruciale dans le cycle de leur développement.
Deux techniques de vérification et de validation se sont démarquées au cours de ces
dernières années : l’analyse statique et l’analyse dynamique. Les points forts et
faibles des deux techniques sont complémentaires. Nous présentons dans cette thèse
une combinaison originale de ces deux techniques. Dans cette combinaison, l’analyse
statique signale les instructions risquant de provoquer des erreurs à l’exécution,
par des alarmes dont certaines peuvent être de fausses alarmes, puis l’analyse dynamique
(génération de tests) est utilisée pour confirmer ou rejeter ces alarmes. L’objectif
de cette thèse est de rendre la recherche d’erreurs automatique, plus précise, et
plus efficace en temps. Appliquée à des programmes de grande taille, la génération
de tests, peut manquer de temps ou d’espace mémoire avant de confirmer certaines alarmes
comme de vraies erreurs ou conclure qu’aucun chemin d’exécution ne peut atteindre
l’état d’erreur de certaines alarmes et donc rejeter ces alarmes. Pour surmonter ce
problème, nous proposons de réduire la taille du code source par le slicing avant
de lancer la génération de tests. Le slicing transforme un programme en un autre programme
plus simple, appelé slice, qui est équivalent au programme initial par rapport à certains
critères. Quatre utilisations du slicing sont étudiées. La première utilisation est
nommée all. Elle consiste à appliquer le slicing une seule fois, le critère de simplification
étant l’ensemble de toutes les alarmes du programme qui ont été détectées par l’analyse
statique. L’inconvénient de cette utilisation est que la génération de tests peut
manquer de temps ou d’espace et les alarmes les plus faciles à classer sont pénalisées
par l’analyse d’autres alarmes plus complexes. Dans la deuxième utilisation, nommée
each, le slicing est effectué séparément par rapport à chaque alarme. Cependant, la
génération de tests est exécutée pour chaque programme et il y a un risque de redondance
d’analyse si des alarmes sont incluses dans d’autres slices. Pour pallier ces inconvénients,
nous avons étudié les dépendances entre les alarmes et nous avons introduit deux utilisations
avancées du slicing, nommées min et smart, qui exploitent ces dépendances. Dans l’utilisation
min, le slicing est effectué par rapport à un ensemble minimal de sous-ensembles d’alarmes.
Ces sous-ensembles sont choisis en fonction de dépendances entre les alarmes et l’union
de ces sous-ensembles couvre l’ensemble de toutes les alarmes. Avec cette utilisation,
on a moins de slices qu’avec each, et des slices plus simples qu’avec all. Cependant,
l’analyse dynamique de certaines slices peut manquer de temps ou d’espace avant de
classer certaines alarmes, tandis que l’analyse dynamique d’une slice éventuellement
plus simple permettrait de les classer. L’utilisation smart consiste à appliquer l’utilisation
précédente itérativement en réduisant la taille des sous-ensembles quand c’est nécessaire.
Lorsqu’une alarme ne peut pas être classée par l’analyse dynamique d’une slice, des
slices plus simples sont calculées. Nous prouvons la correction de la méthode proposée.
Ces travaux sont implantés dans sante, notre outil qui relie l’outil de génération
de tests PathCrawler et la plate-forme d’analyse statique Frama-C. Des expérimentations
ont montré, d’une part, que notre combinaison est plus performante que chaque technique
utilisée indépendamment et, d’autre part, que la vérification devient plus rapide
avec l’utilisation du slicing. De plus, la simplification du programme par le slicing
rend les erreurs détectées et les alarmes restantes plus faciles à analyser
Note publique d'information : Software validation remains a crucial part in software development process. Two major
techniques have improved in recent years, dynamic and static analysis. They have complementary
strengths and weaknesses. We present in this thesis a new original combination of
these methods to make the research of runtime errors more accurate, automatic and
reduce the number of false alarms. We prove as well the correction of the method.
In this combination, static analysis reports alarms of runtime errors some of which
may be false alarms, and test generation is used to confirm or reject these alarms.
When applied on large programs, test generation may lack time or space before confirming
out certain alarms as real bugs or finding that some alarms are unreachable. To overcome
this problem, we propose to reduce the source code by program slicing before running
test generation. Program slicing transforms a program into another simpler program,
which is equivalent to the original program with respect to certain criterion. Four
usages of program slicing were studied. The first usage is called all. It applies
the slicing only once, the simplification criterion is the set of all alarms in the
program. The disadvantage of this usage is that test generation may lack time or space
and alarms that are easier to classify are penalized by the analysis of other more
complex alarms. In the second usage, called each, program slicing is performed with
respect to each alarm separately. However, test generation is executed for each sliced
program and there is a risk of redundancy if some alarms are included in many slices.
To overcome these drawbacks, we studied dependencies between alarms on which we base
to introduce two advanced usages of program slicing : min and smart. In the min usage,
the slicing is performed with respect to subsets of alarms. These subsets are selected
based on dependencies between alarms and the union of these subsets cover the whole
set of alarms. With this usage, we analyze less slices than with each, and simpler
slices than with all. However, the dynamic analysis of some slices may lack time or
space before classifying some alarms, while the dynamic analysis of a simpler slice
could possibly classify some. Usage smart applies previous usage iteratively by reducing
the size of the subsets when necessary. When an alarm cannot be classified by the
dynamic analysis of a slice, simpler slices are calculated. These works are implemented
in sante, our tool that combines the test generation tool PathCrawler and the platform
of static analysis Frama-C. Experiments have shown, firstly, that our combination
is more effective than each technique used separately and, secondly, that the verification
is faster after reducing the code with program slicing. Simplifying the program by
program slicing also makes the detected errors and the remaining alarms easier to
analyze