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 experimental 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 in this paper an alternative proof system, in which symbolic execution becomes a rule for proof construction. We show that under reasonable conditions on the semantics of programming languages our proof system is sound. We then present a Reachability-Logic verifier based on our proof system, which is implemented in the K framework and illustrated on 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 cela 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 possède 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. C'est pourquoi nous proposons dans cet article un nouveau système déductif où l'exécution symbolique de programmes devient une règle pour la construction de preuves. Nous montrons que, moyennant des conditions raisonnables sur la sémantique des langages de programmation, notre méthode de vérification est correcte. 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
tap-techreport.pdf (1.09 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

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 4

Citer

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

Partager

Gmail Facebook X LinkedIn More