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é

In this paper we present an automatic and language-independent program verification approach based on symbolic execution. The specification formalism we consider is Reachability Logic, a language-independent logic that constitutes an alternative to Hoare logics. Reachability Logic has a sound and relatively complete deduction system, which offers a lot of freedom (but no guidelines) for constructing proofs. Hence, we propose symbolic execution as a strategy for proof construction. We show that, under reasonable conditions on the semantics of programming languages, our symbolic-execution based Reachability-Logic formula verification is sound. We present a prototype implementation of the resulting language-independent verifier as an extension of a generic symbolic execution engine that we are developing in the K framework. The verifier is illustrated on programs written in languages also formally 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 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. Nous montrons que l'on peut utiliser une méthode générique d'exécution symbolique de programmes, que nous avons introduite récemment, comme une stratégie de construction de preuves dans ce système déductif. 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
RR-8369.pdf (1.01 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 2

Citer

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

Partager

Gmail Facebook X LinkedIn More