Language-Independent Program Verification Using Symbolic Execution - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2013

Language-Independent Program Verification Using Symbolic Execution

Résumé

We present an automatic, language-independent program verification approach and prototype tool based on symbolic execution. The program-specification formalism we consider is Reachability Logic, a language-independent alternative to Hoare logics. Reachability Logic has a sound and relatively complete deduction system, which offers a lot of freedom (but very few guidelines) for constructing proofs. Hence, we propose an alternative proof system, in which symbolic execution becomes a rule for systematic proof construction. We show that, under reasonable conditions on the semantics of programming languages and of the Reachability-Logic formulas, a certain strategy executing our proof system is sound and weakly complete. This essentially means that, when it terminates, the strategy solves the Reachability-Logic verification problem: when presented with a valid input (set of RL formulas) it proves the formulas, and when presented with an invalid input it detects this invalidity. We then introduce a prototype Reachability-Logic verifier based on our proof system, which is implemented in the K framework and illustrated on several programs written in languages also defined in K.
Nous présentons une méthode automatique pour vérifier des programmes qui ne dépend pas du langage de programmation dans lequel les programmes à vérifier sont écrits. Pour celà nous nous appuyons sur la Reachability Logic, un formalisme de spécification introduit récemment, qui peut être vu comme une alternative à la logique de Hoare, mais qui, contrairement à cette dernière, ne dépend pas du langage de programmation utilisé. La Reachability Logic a un système déductif qui est correct et relativement complet, qui laisse beaucoup de liberté à l'utilisateur sur la manière d'appliquer les règles de déduction, mais qui n'offre pas de mode d'emploi pour construire des preuves. Par conséquent nous proposons ici un autre système déductif dans lequel l'exécution symbolique est utilisée pour la construction systématique de preuves. Nous montrons que, moyennant des conditions raisonnables sur la sémantique des langages de programmation et sur les propriétés des programmes, une certaine stratégie d'application des règles de notre système déductif est correcte et faiblement complète. Ceci dit en substance que, lorsqu'elle termine, notre stratégie résout le problème de vérification de programmes à base de Reachability Logic. Nous présentons une implémentation prototype d'un outil de vérification basé sur ces idées, que nous avons implémenté dans la K framework, et que nous illustrons sur des exemples de programmes écrits dans des langages formellement définis en K.
Fichier principal
Vignette du fichier
aplas2014-techreport.pdf (1.2 Mo) Télécharger le fichier
Origine : Accord explicite pour ce dépôt

Dates et versions

hal-00864341 , version 1 (20-09-2013)
hal-00864341 , version 2 (26-09-2013)
hal-00864341 , version 3 (15-03-2014)
hal-00864341 , version 4 (07-04-2014)
hal-00864341 , version 5 (11-06-2014)
hal-00864341 , version 6 (10-10-2014)

Identifiants

  • HAL Id : hal-00864341 , version 5

Citer

Andrei Arusoaie, Dorel Lucanu, Vlad Rusu. Language-Independent Program Verification Using Symbolic Execution. [Research Report] RR-8369, 2013, pp.24. ⟨hal-00864341v5⟩
446 Consultations
335 Téléchargements

Partager

Gmail Facebook X LinkedIn More