The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Patrick Cousot - One of the best experts on this subject based on the ideXlab platform.
-
Static Analysis and Verification of Aerospace Software by Abstract Interpretation
Foundations and Trends in Programming Languages, 2015Co-Authors: Julien Bertrane, Patrick Cousot, Radhia Cousot, Jérôme Feret, Laurent Mauborgne, Antoine Miné, Xavier RivalAbstract:We discuss the principles of static analysis by Abstract Interpretationand report on the automatic verification of the absence of runtimeerrors in large embedded aerospace software by static analysis basedon Abstract Interpretation. The first industrial applications concernedsynchronous control/command software in open loop. Recent advancesconsider imperfectly synchronous programs, parallel programs, and targetcode validation as well. Future research directions on Abstract Interpretationare also discussed in the context of aerospace software.
-
theories solvers and static analysis by Abstract Interpretation
Journal of the ACM, 2013Co-Authors: Patrick Cousot, Radhia Cousot, Laurent MauborgneAbstract:The algebraic/model theoretic design of static analyzers uses Abstract domains based on representations of properties and pre-calculated property transformers. It is very efficient. The logical/proof theoretic approach uses SMT solvers/theorem provers and computation of property transformers on-the-fly. It is very expressive. We propose to unify both approaches, so that they can be combined to reach the sweet spot best adapted to a specific application domain in the precision/cost spectrum. We first give a new formalization of the proof theoretic approach in the Abstract Interpretation framework, introducing a semantics based on multiple Interpretations to deal with the soundness of such approaches. Then we describe how to combine them with any other Abstract Interpretation-based analysis using an iterated reduction to combine Abstractions. The key observation is that the Nelson-Oppen procedure, which decides satisfiability in a combination of logical theories by exchanging equalities and disequalities, computes a reduced product (after the state is enhanced with some new “observations” corresponding to alien terms). By abandoning restrictions ensuring completeness (such as disjointness, convexity, stably-infiniteness, or shininess, etc.), we can even broaden the application scope of logical Abstractions for static analysis (which is incomplete anyway).
-
probabilistic Abstract Interpretation
European Symposium on Programming, 2012Co-Authors: Patrick Cousot, Michael MonerauAbstract:Abstract Interpretation has been widely used for verifying properties of computer systems. Here, we present a way to extend this framework to the case of probabilistic systems. The probabilistic Abstraction framework that we propose allows us to systematically lift any classical analysis or verification method to the probabilistic setting by separating in the program semantics the probabilistic behavior from the (non-)deterministic behavior. This separation provides new insights for designing novel probabilistic static analyses and verification methods. We define the concrete probabilistic semantics and propose different ways to Abstract them. We provide examples illustrating the expressiveness and effectiveness of our approach.
-
an Abstract Interpretation framework for termination
Symposium on Principles of Programming Languages, 2012Co-Authors: Patrick Cousot, Radhia CousotAbstract:Proof, verification and analysis methods for termination all rely on two induction principles: (1) a variant function or induction on data ensuring progress towards the end and (2) some form of induction on the program structure. The Abstract Interpretation design principle is first illustrated for the design of new forward and backward proof, verification and analysis methods for safety. The safety collecting semantics defining the strongest safety property of programs is first expressed in a constructive fixpoint form. Safety proof and checking/verification methods then immediately follow by fixpoint induction. Static analysis of Abstract safety properties such as invariance are constructively designed by fixpoint Abstraction (or approximation) to (automatically) infer safety properties. So far, no such clear design principle did exist for termination so that the existing approaches are scattered and largely not comparable with each other.For (1), we show that this design principle applies equally well to potential and definite termination. The trace-based termination collecting semantics is given a fixpoint definition. Its Abstraction yields a fixpoint definition of the best variant function. By further Abstraction of this best variant function, we derive the Floyd/Turing termination proof method as well as new static analysis methods to effectively compute approximations of this best variant function.For (2), we introduce a generalization of the syntactic notion of struc- tural induction (as found in Hoare logic) into a semantic structural induction based on the new semantic concept of inductive trace cover covering execution traces by segments, a new basis for formulating program properties. Its Abstractions allow for generalized recursive proof, verification and static analysis methods by induction on both program structure, control, and data. Examples of particular instances include Floyd's handling of loop cutpoints as well as nested loops, Burstall's intermittent assertion total correctness proof method, and Podelski-Rybalchenko transition invariants.
-
Static Analysis by Abstract Interpretation of Embedded Critical Software
2010Co-Authors: Julien Bertrane, Patrick Cousot, Radhia Cousot, Jérôme Feret, Laurent Mauborgne, Antoine Miné, Xavier RivalAbstract:Formal methods are increasingly used to help ensuring the correctness of complex, critical embedded software systems. We show how sound semantic static analyses based on Abstract Interpretation may be used to check properties at various levels of a software design: from high level models to low level binary code. After a short introduction to the Abstract Interpretation theory, we present a few current applications: checking for run-time errors at the C level, translation validation from C to assembly, and analyzing SAO models of communicating synchronous systems with imperfect clocks. We conclude by briefly proposing some requirements to apply Abstract Interpretation to modeling languages such as UML.
Radhia Cousot - One of the best experts on this subject based on the ideXlab platform.
-
Static Analysis and Verification of Aerospace Software by Abstract Interpretation
Foundations and Trends in Programming Languages, 2015Co-Authors: Julien Bertrane, Patrick Cousot, Radhia Cousot, Jérôme Feret, Laurent Mauborgne, Antoine Miné, Xavier RivalAbstract:We discuss the principles of static analysis by Abstract Interpretationand report on the automatic verification of the absence of runtimeerrors in large embedded aerospace software by static analysis basedon Abstract Interpretation. The first industrial applications concernedsynchronous control/command software in open loop. Recent advancesconsider imperfectly synchronous programs, parallel programs, and targetcode validation as well. Future research directions on Abstract Interpretationare also discussed in the context of aerospace software.
-
theories solvers and static analysis by Abstract Interpretation
Journal of the ACM, 2013Co-Authors: Patrick Cousot, Radhia Cousot, Laurent MauborgneAbstract:The algebraic/model theoretic design of static analyzers uses Abstract domains based on representations of properties and pre-calculated property transformers. It is very efficient. The logical/proof theoretic approach uses SMT solvers/theorem provers and computation of property transformers on-the-fly. It is very expressive. We propose to unify both approaches, so that they can be combined to reach the sweet spot best adapted to a specific application domain in the precision/cost spectrum. We first give a new formalization of the proof theoretic approach in the Abstract Interpretation framework, introducing a semantics based on multiple Interpretations to deal with the soundness of such approaches. Then we describe how to combine them with any other Abstract Interpretation-based analysis using an iterated reduction to combine Abstractions. The key observation is that the Nelson-Oppen procedure, which decides satisfiability in a combination of logical theories by exchanging equalities and disequalities, computes a reduced product (after the state is enhanced with some new “observations” corresponding to alien terms). By abandoning restrictions ensuring completeness (such as disjointness, convexity, stably-infiniteness, or shininess, etc.), we can even broaden the application scope of logical Abstractions for static analysis (which is incomplete anyway).
-
an Abstract Interpretation framework for termination
Symposium on Principles of Programming Languages, 2012Co-Authors: Patrick Cousot, Radhia CousotAbstract:Proof, verification and analysis methods for termination all rely on two induction principles: (1) a variant function or induction on data ensuring progress towards the end and (2) some form of induction on the program structure. The Abstract Interpretation design principle is first illustrated for the design of new forward and backward proof, verification and analysis methods for safety. The safety collecting semantics defining the strongest safety property of programs is first expressed in a constructive fixpoint form. Safety proof and checking/verification methods then immediately follow by fixpoint induction. Static analysis of Abstract safety properties such as invariance are constructively designed by fixpoint Abstraction (or approximation) to (automatically) infer safety properties. So far, no such clear design principle did exist for termination so that the existing approaches are scattered and largely not comparable with each other.For (1), we show that this design principle applies equally well to potential and definite termination. The trace-based termination collecting semantics is given a fixpoint definition. Its Abstraction yields a fixpoint definition of the best variant function. By further Abstraction of this best variant function, we derive the Floyd/Turing termination proof method as well as new static analysis methods to effectively compute approximations of this best variant function.For (2), we introduce a generalization of the syntactic notion of struc- tural induction (as found in Hoare logic) into a semantic structural induction based on the new semantic concept of inductive trace cover covering execution traces by segments, a new basis for formulating program properties. Its Abstractions allow for generalized recursive proof, verification and static analysis methods by induction on both program structure, control, and data. Examples of particular instances include Floyd's handling of loop cutpoints as well as nested loops, Burstall's intermittent assertion total correctness proof method, and Podelski-Rybalchenko transition invariants.
-
Static Analysis by Abstract Interpretation of Embedded Critical Software
2010Co-Authors: Julien Bertrane, Patrick Cousot, Radhia Cousot, Jérôme Feret, Laurent Mauborgne, Antoine Miné, Xavier RivalAbstract:Formal methods are increasingly used to help ensuring the correctness of complex, critical embedded software systems. We show how sound semantic static analyses based on Abstract Interpretation may be used to check properties at various levels of a software design: from high level models to low level binary code. After a short introduction to the Abstract Interpretation theory, we present a few current applications: checking for run-time errors at the C level, translation validation from C to assembly, and analyzing SAO models of communicating synchronous systems with imperfect clocks. We conclude by briefly proposing some requirements to apply Abstract Interpretation to modeling languages such as UML.
-
space software validation using Abstract Interpretation
The International Space System Engineering Conference : Data Systems in Aerospace - DASIA 2009, 2009Co-Authors: Olivier Bouissou, Patrick Cousot, Radhia Cousot, Eric Conquet, Jérôme Feret, Khalil Ghorbal, Eric Goubault, David Lesens, Laurent Mauborgne, Antoine MinéAbstract:This paper reports the results of an ESA funded project on the use of Abstract Interpretation to validate critical real-time embedded space software. Abstract Interpretation is industrially used since several years, especially for the validation of the Ariane 5 launcher. However, the limitations of the tools used so far prevented a wider deployment. Astrium Space Transportation, CEA, and ENS have analyzed the performances of two recent tools on a case study extracted from the safety software of the ATV: * ASTREE, developed by ENS and CNRS, to check for run-time errors, * FLUCTUAT, developed by CEA, to analyse the accuracy of numerical computations. The conclusion of the study is that the performance of this new generation of tools has dramatically increased (no false alarms and fine analysis of numerical precision).
Roberto Giacobazzi - One of the best experts on this subject based on the ideXlab platform.
-
adjoining classified and unclassified information by Abstract Interpretation
Journal of Computer Security, 2010Co-Authors: Roberto Giacobazzi, Isabella MastroeniAbstract:Completeness in Abstract Interpretation models the ideal situation where no loss of precision is introduced in computations by approximating concrete data by their Abstractions. If we interpret the Abstraction as the ability of an attacker to distinguish, i.e., observe, properties of public computations, and the computation as the concrete denotational semantics of the program, then the lack of precision, encoded in Abstract Interpretation as a lack of completeness, corresponds precisely to the leakage of information corresponding to a violated security policy. This correspondence allows us to inherit, in the field of language-based security, the whole theory and methodology for making Abstract domains complete. In particular, we prove that an adjoint relation exists between the power of the attacker and the amount of the information released - the more the attacker can observe, the less information can be kept private. This characterisation is achieved by interpreting, in the security context, the standard adjoint transformations making an Abstract domain complete by refining and simplifying Abstractions.
-
Semantics-based code obfuscation by Abstract Interpretation
Journal of Computer Security, 2009Co-Authors: Mila Dalla Preda, Roberto GiacobazziAbstract:In recent years code obfuscation has attracted research interest as a promising technique for protecting secret properties of programs. The basic idea of code obfuscation is to transform programs in order to hide their sensitive information while preserving their functionality. One of the major drawbacks of code obfuscation is the lack of a rigorous theoretical framework that makes it difficult to formally analyze and certify the effectiveness of obfuscating techniques. We face this problem by providing a formal framework for code obfuscation based on Abstract Interpretation and program semantics. In particular, we show that what is hidden and what is preserved by an obfuscating transformation can be expressed as Abstract Interpretations of program semantics. Being able to specify what is masked and what is preserved by an obfuscation allows us to understand its potency, namely the amount of obscurity that the transformation adds to programs. In the proposed framework, obfuscation and attackers are modeled as approximations of program semantics and the lattice of Abstract Interpretations provides a formal tool for comparing obfuscations with respect to their potency. In particular, we prove that our framework provides an adequate setting to measure not only the potency of an obfuscation but also its resilience, i.e., the difficulty of undoing the obfuscation. We consider code obfuscation by opaque predicate insertion and we show how the degree of Abstraction needed to disclose different opaque predicates allows us to compare their potency and resilience.
-
opaque predicates detection by Abstract Interpretation
Algebraic Methodology and Software Technology, 2006Co-Authors: Mila Dalla Preda, Matias Madou, Koen De Bosschere, Roberto GiacobazziAbstract:Code obfuscation and software watermarking are well known techniques designed to prevent the illegal reuse of software. Code obfuscation prevents malicious reverse engineering, while software watermarking protects code from piracy. An interesting class of algorithms for code obfuscation and software watermarking relies on the insertion of opaque predicates. It turns out that attackers based on a dynamic or an hybrid static-dynamic approach are either not precise or time consuming in eliminating opaque predicates. We present an Abstract Interpretation-based methodology for removing opaque predicates from programs. Abstract Interpretation provides the right framework for proving the correctness of our approach, together with a general methodology for designing efficient attackers for a relevant class of opaque predicates. Experimental evaluations show that Abstract Interpretation based attacks significantly reduce the time needed to eliminate opaque predicates.
-
control code obfuscation by Abstract Interpretation
Software Engineering and Formal Methods, 2005Co-Authors: Dalla M Preda, Roberto GiacobazziAbstract:Control code obfuscation is intended to prevent malicious reverse engineering of software by masking the program control flow. These obfuscating transformations often rely on the existence of opaque predicates, that support the design of transformations that break up the program control flow. We prove that an algorithm for control obfuscation by opaque predicate insertion can be systematically derived as an Abstraction of a suitable semantic transformation. In this framework, deobfuscation is interpreted as an attacker which can observe the computational behaviour of programs up to a given precision degree. Both obfuscation and deobfuscation can therefore be interpreted as approximations of program semantics, where approximation is formalized using Abstract Interpretation theory. In particular we prove that Abstract Interpretation provides the adequate setting to measure the potency of an obfuscation algorithm by comparing the degree of Abstraction of the most Abstract domains which are able to disclose opaque predicates.
-
semantic based code obfuscation by Abstract Interpretation
International Colloquium on Automata Languages and Programming, 2005Co-Authors: Mila Dalla Preda, Roberto GiacobazziAbstract:In this paper we introduce a semantic-based approach for code obfuscation. The aim of code obfuscation is to prevent malicious users to disclose properties of the original source program. This goal can be precisely modeled by Abstract Interpretation, where the hiding of properties corresponds to Abstract the semantics. We derive a general theory based on Abstract Interpretation, where the potency of code obfuscation can be measured by comparing hidden properties in the lattice of Abstract Interpretations. Semantic-based code obfuscation is applied to show that well known program transformation methods, such as constant propagation, can be seen as code obfuscation.
Mila Dalla Preda - One of the best experts on this subject based on the ideXlab platform.
-
Semantics-based code obfuscation by Abstract Interpretation
Journal of Computer Security, 2009Co-Authors: Mila Dalla Preda, Roberto GiacobazziAbstract:In recent years code obfuscation has attracted research interest as a promising technique for protecting secret properties of programs. The basic idea of code obfuscation is to transform programs in order to hide their sensitive information while preserving their functionality. One of the major drawbacks of code obfuscation is the lack of a rigorous theoretical framework that makes it difficult to formally analyze and certify the effectiveness of obfuscating techniques. We face this problem by providing a formal framework for code obfuscation based on Abstract Interpretation and program semantics. In particular, we show that what is hidden and what is preserved by an obfuscating transformation can be expressed as Abstract Interpretations of program semantics. Being able to specify what is masked and what is preserved by an obfuscation allows us to understand its potency, namely the amount of obscurity that the transformation adds to programs. In the proposed framework, obfuscation and attackers are modeled as approximations of program semantics and the lattice of Abstract Interpretations provides a formal tool for comparing obfuscations with respect to their potency. In particular, we prove that our framework provides an adequate setting to measure not only the potency of an obfuscation but also its resilience, i.e., the difficulty of undoing the obfuscation. We consider code obfuscation by opaque predicate insertion and we show how the degree of Abstraction needed to disclose different opaque predicates allows us to compare their potency and resilience.
-
opaque predicates detection by Abstract Interpretation
Algebraic Methodology and Software Technology, 2006Co-Authors: Mila Dalla Preda, Matias Madou, Koen De Bosschere, Roberto GiacobazziAbstract:Code obfuscation and software watermarking are well known techniques designed to prevent the illegal reuse of software. Code obfuscation prevents malicious reverse engineering, while software watermarking protects code from piracy. An interesting class of algorithms for code obfuscation and software watermarking relies on the insertion of opaque predicates. It turns out that attackers based on a dynamic or an hybrid static-dynamic approach are either not precise or time consuming in eliminating opaque predicates. We present an Abstract Interpretation-based methodology for removing opaque predicates from programs. Abstract Interpretation provides the right framework for proving the correctness of our approach, together with a general methodology for designing efficient attackers for a relevant class of opaque predicates. Experimental evaluations show that Abstract Interpretation based attacks significantly reduce the time needed to eliminate opaque predicates.
-
semantic based code obfuscation by Abstract Interpretation
International Colloquium on Automata Languages and Programming, 2005Co-Authors: Mila Dalla Preda, Roberto GiacobazziAbstract:In this paper we introduce a semantic-based approach for code obfuscation. The aim of code obfuscation is to prevent malicious users to disclose properties of the original source program. This goal can be precisely modeled by Abstract Interpretation, where the hiding of properties corresponds to Abstract the semantics. We derive a general theory based on Abstract Interpretation, where the potency of code obfuscation can be measured by comparing hidden properties in the lattice of Abstract Interpretations. Semantic-based code obfuscation is applied to show that well known program transformation methods, such as constant propagation, can be seen as code obfuscation.
Antoine Miné - One of the best experts on this subject based on the ideXlab platform.
-
static value analysis of python programs by Abstract Interpretation
NASA Formal Methods Symposium, 2018Co-Authors: Abdelraouf Ouadjaout, Aymeric Fromherz, Antoine Miné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.
-
Static Analysis and Verification of Aerospace Software by Abstract Interpretation
Foundations and Trends in Programming Languages, 2015Co-Authors: Julien Bertrane, Patrick Cousot, Radhia Cousot, Jérôme Feret, Laurent Mauborgne, Antoine Miné, Xavier RivalAbstract:We discuss the principles of static analysis by Abstract Interpretationand report on the automatic verification of the absence of runtimeerrors in large embedded aerospace software by static analysis basedon Abstract Interpretation. The first industrial applications concernedsynchronous control/command software in open loop. Recent advancesconsider imperfectly synchronous programs, parallel programs, and targetcode validation as well. Future research directions on Abstract Interpretationare also discussed in the context of aerospace software.
-
relational thread modular static value analysis by Abstract Interpretation
Verification Model Checking and Abstract Interpretation, 2014Co-Authors: Antoine MinéAbstract:We study thread-modular static analysis by Abstract Interpretation to infer the values of variables in concurrent programs. We show how to go beyond the state of the art and increase an analysis precision by adding the ability to infer some relational and history-sensitive properties of thread interferences. The fundamental basis of this work is the formalization by Abstract Interpretation of a rely-guarantee concrete semantics which is thread-modular, constructive, and complete for safety properties. We then show that previous analyses based on non-relational interferences can be retrieved as coarse computable Abstractions of this semantics; additionally, we present novel Abstraction examples exploiting our ability to reason more precisely about interferences, including domains to infer relational lock invariants and the monotonicity of counters. Our method and domains have been implemented in the AstreeA static analyzer that checks for run-time errors in embedded concurrent C programs, where they enabled a significant reduction of the number of false alarms.
-
Static Analysis by Abstract Interpretation of Embedded Critical Software
2010Co-Authors: Julien Bertrane, Patrick Cousot, Radhia Cousot, Jérôme Feret, Laurent Mauborgne, Antoine Miné, Xavier RivalAbstract:Formal methods are increasingly used to help ensuring the correctness of complex, critical embedded software systems. We show how sound semantic static analyses based on Abstract Interpretation may be used to check properties at various levels of a software design: from high level models to low level binary code. After a short introduction to the Abstract Interpretation theory, we present a few current applications: checking for run-time errors at the C level, translation validation from C to assembly, and analyzing SAO models of communicating synchronous systems with imperfect clocks. We conclude by briefly proposing some requirements to apply Abstract Interpretation to modeling languages such as UML.
-
space software validation using Abstract Interpretation
The International Space System Engineering Conference : Data Systems in Aerospace - DASIA 2009, 2009Co-Authors: Olivier Bouissou, Patrick Cousot, Radhia Cousot, Eric Conquet, Jérôme Feret, Khalil Ghorbal, Eric Goubault, David Lesens, Laurent Mauborgne, Antoine MinéAbstract:This paper reports the results of an ESA funded project on the use of Abstract Interpretation to validate critical real-time embedded space software. Abstract Interpretation is industrially used since several years, especially for the validation of the Ariane 5 launcher. However, the limitations of the tools used so far prevented a wider deployment. Astrium Space Transportation, CEA, and ENS have analyzed the performances of two recent tools on a case study extracted from the safety software of the ATV: * ASTREE, developed by ENS and CNRS, to check for run-time errors, * FLUCTUAT, developed by CEA, to analyse the accuracy of numerical computations. The conclusion of the study is that the performance of this new generation of tools has dramatically increased (no false alarms and fine analysis of numerical precision).
