A Generic Framework for Symbolic Execution: Theory and Applications - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2015

A Generic Framework for Symbolic Execution: Theory and Applications

Un cadre générique pour l'exécution symbolique : théorie et applications

Résumé

We propose a language-independent symbolic execution framework. The approach is parameterised by a language definition, which consists of a signature for the language's syntax and execution infrastructure, a model interpreting the signature, and rewrite rules for the language's operational semantics. Then, symbolic execution amounts to performing a so-called symbolic rewriting, which consists in changing both the model and the manner in which the operational semantics rules are applied. We prove that the symbolic execution thus defined has the properties naturally expected from it. A prototype implementation of our approach was developed in the K Framework. We demonstrate the genericity of our tool by instantiating it on several languages, and show how it can be used for the symbolic execution, bounded model checking, and deductive verification of several programs.
Nous proposons un cadre général pour l’exécution symbolique de programmes, qui est indépendant des langages dans lesquels les programmes en question sont écrits. L’approche est paramétrisée par une définition de langage, qui consiste en une signature pour la syntaxe du langage et pour son infrastructure, un modèle interprétant la signature, et un ensemble de règles de réécriture définissant la sémantique opérationnelle du langage. L’exécution symbolique revient alors à modifier calculer des chemins symboliques en utilisant une opration dite de dérivation. Nous démontrons que l’exécution symbolique possède les propriétés attendues par rapport à l’exécution concrète: les exécutions symboliques et concrètes d’un même programme se simulent mutuellement. Nous montrons également qu’une extension coinductive de l’exécution symbolique peut être utilisée pour la vérification déductive de programmes. Nous avons implémenté notre approche dans un outil prototype dans la K framework. L’aspect générique de l’outil est mis en évidence par son instanciation sur plusieurs langages. Nous montrons enfin comment l’outil permet l’analyse symbolique, le model checking borné, et la vérification déductive de programmes.
Fichier principal
Vignette du fichier
jsc2014-techreport.pdf (1.23 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00766220 , version 1 (17-12-2012)
hal-00766220 , version 2 (20-12-2012)
hal-00766220 , version 3 (21-06-2013)
hal-00766220 , version 4 (15-03-2014)
hal-00766220 , version 5 (21-03-2014)
hal-00766220 , version 6 (06-04-2014)
hal-00766220 , version 7 (01-09-2015)
hal-00766220 , version 8 (03-09-2015)

Identifiants

  • HAL Id : hal-00766220 , version 8

Citer

Andrei Arusoaie, Dorel Lucanu, Vlad Rusu. A Generic Framework for Symbolic Execution: Theory and Applications. [Research Report] RR-8189, Inria. 2015, pp.41. ⟨hal-00766220v8⟩
560 Consultations
1240 Téléchargements

Partager

Gmail Facebook X LinkedIn More