Static Value Analysis of Python Programs by Abstract Interpretation - Sorbonne Université
Conference Papers Year : 2018

Static Value Analysis of Python Programs by Abstract Interpretation

Abstract

We propose a static analysis by abstract interpretation for a significant subset of Python to infer variable values, run-time errors, and uncaught exceptions. Python is a high-level language with dynamic typing, a class-based object system, complex control structures such as generators, and a large library of builtin objects. This makes static reasoning on Python programs challenging. The control flow is highly dependent on the type of values, which we thus infer accurately. As Python lacks a formal specification, we first present a concrete collecting semantics of reachable program states. We then propose a non-relational flow-sensitive type and value analysis based on simple abstract domains for each type, and handle non-local control such as exceptions through continuations. We show how to infer relational numeric invariants by leveraging the type information we gather. Finally, we propose a relational abstraction of generators to count the number of available elements and prove that no StopIteration exception is raised. Our prototype implementation is heavily in development; it does not support some Python features, such as recursion nor the compile builtin, and it handles only a small part of the builtin objects and standard library. Nevertheless, we are able to present preliminary experimental results on analyzing actual, if small, Python code from a benchmarking application and a regression test suite.
Fichier principal
Vignette du fichier
fromherz-al-nfm18.pdf (401.89 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01782390 , version 1 (11-09-2018)

Identifiers

Cite

Aymeric Fromherz, Abdelraouf Ouadjaout, Antoine Miné. Static Value Analysis of Python Programs by Abstract Interpretation. NFM 2018 - 10th International Symposium NASA Formal Methods, Apr 2018, Newport News, VA, United States. pp.185-202, ⟨10.1007/978-3-319-77935-5_14⟩. ⟨hal-01782390⟩
881 View
1694 Download

Altmetric

Share

More