The Experts below are selected from a list of 537 Experts worldwide ranked by ideXlab platform

Marie-laure Potet - One of the best experts on this subject based on the ideXlab platform.

  • get rid of Inline Assembly through verification oriented lifting
    Automated Software Engineering, 2019
    Co-Authors: Frédéric Recoules, Sébastien Bardin, Richard Bonichon, Laurent Mounier, Marie-laure Potet
    Abstract:

    Formal methods for software development have made great strides in the last two decades, to the point that their application in safety-critical embedded software is an undeniable success. Their extension to non-critical software is one of the notable forthcoming challenges. For example, C programmers regularly use Inline Assembly for low-level optimizations and system primitives. This usually results in rendering state-of-the-art formal analyzers developed for C ineffective. We thus propose TINA, the first automated, generic, verification-friendly and trustworthy lifting technique turning Inline Assembly into semantically equivalent C code amenable to verification, in order to take advantage of existing C analyzers. Extensive experiments on real-world code (including GMP and ffmpeg) show the feasibility and benefits of TINA.

  • Get rid of Inline Assembly through verification-oriented lifting
    arXiv: Programming Languages, 2019
    Co-Authors: Frédéric Recoules, Sébastien Bardin, Richard Bonichon, Laurent Mounier, Marie-laure Potet
    Abstract:

    Formal methods for software development have made great strides in the last two decades, to the point that their application in safety-critical embedded software is an undeniable success. Their extension to non-critical software is one of the notable forthcoming challenges. For example, C programmers regularly use Inline Assembly for low-level optimizations and system primitives. This usually results in driving state-of-the-art formal analyzers developed for C ineffective. We thus propose TInA, an automated, generic, trustable and verification-oriented lifting technique turning Inline Assembly into semantically equivalent C code, in order to take advantage of existing C analyzers. Extensive experiments on real-world C code with Inline Assembly (including GMP and ffmpeg) show the feasibility and benefits of TInA.

  • get rid of Inline Assembly through trustable verification oriented lifting
    2019
    Co-Authors: Frédéric Recoules, Sébastien Bardin, Richard Bonichon, Laurent Mounier, Marie-laure Potet
    Abstract:

    Formal methods for software development have made great strides in the last two decades, to the point that their application in safety-critical embedded software is an undeniable success. Their extension to non-critical software is one of the notable forthcoming challenges. For example, C programmers regularly use Inline Assembly for low-level optimizations and system primitives. This usually results in driving state-of-the-art formal analyzers developed for C ineffective. We thus propose TInA, an automated, generic, trustable and verification-oriented lifting technique turning Inline Assembly into semantically equivalent C code, in order to take advantage of existing C analyzers. Extensive experiments on real-world C code with Inline Assembly (including GMP and ffmpeg) show the feasibility and benefits of TInA.

  • ASE - Get Rid of Inline Assembly through Verification-Oriented Lifting
    2019 34th IEEE ACM International Conference on Automated Software Engineering (ASE), 2019
    Co-Authors: Frédéric Recoules, Sébastien Bardin, Richard Bonichon, Laurent Mounier, Marie-laure Potet
    Abstract:

    Formal methods for software development have made great strides in the last two decades, to the point that their application in safety-critical embedded software is an undeniable success. Their extension to non-critical software is one of the notable forthcoming challenges. For example, C programmers regularly use Inline Assembly for low-level optimizations and system primitives. This usually results in rendering state-of-the-art formal analyzers developed for C ineffective. We thus propose TINA, the first automated, generic, verification-friendly and trustworthy lifting technique turning Inline Assembly into semantically equivalent C code amenable to verification, in order to take advantage of existing C analyzers. Extensive experiments on real-world code (including GMP and ffmpeg) show the feasibility and benefits of TINA.

Alexandra Tsyban - One of the best experts on this subject based on the ideXlab platform.

  • pervasive verification of an os microkernel Inline Assembly memory consumption concurrent devices
    Verified Software: Theories Tools Experiments, 2010
    Co-Authors: Eyad Alkassar, Wolfgang J Paul, Artem Starostin, Alexandra Tsyban
    Abstract:

    We report on the first formal pervasive verification of an operating system microkernel featuring the correctness of Inline Assembly, large non-trivial C portions, and concurrent devices in a single seamless formal proof. We integrated all relevant verification results we had achieved so far [21,20,2,5,4] into a single top-level theorem of microkernel correctness. This theorem states the simulation of user processes with own, separate virtual memories -- via the microkernel -- by the underlying hardware with devices. All models, theorems, and proofs are formalized in the interactive proof system Isabelle/HOL.

  • pervasive verification of an os microkernel
    Verified Software: Theories Tools Experiments, 2010
    Co-Authors: Eyad Alkassar, Wolfgang J Paul, Artem Starostin, Alexandra Tsyban
    Abstract:

    We report on the first formal pervasive verification of an operating system microkernel featuring the correctness of Inline Assembly, large non-trivial C portions, and concurrent devices in a single seamless formal proof. We integrated all relevant verification results we had achieved so far [21,20,2,5,4] into a single top-level theorem of microkernel correctness. This theorem states the simulation of user processes with own, separate virtual memories — via the microkernel — by the underlying hardware with devices. All models, theorems, and proofs are formalized in the interactive proof system Isabelle/HOL.

  • VSTTE - Pervasive verification of an OS microkernel: Inline Assembly, memory consumption, concurrent devices
    2010
    Co-Authors: Eyad Alkassar, Wolfgang J Paul, Artem Starostin, Alexandra Tsyban
    Abstract:

    We report on the first formal pervasive verification of an operating system microkernel featuring the correctness of Inline Assembly, large non-trivial C portions, and concurrent devices in a single seamless formal proof. We integrated all relevant verification results we had achieved so far [21,20,2,5,4] into a single top-level theorem of microkernel correctness. This theorem states the simulation of user processes with own, separate virtual memories -- via the microkernel -- by the underlying hardware with devices. All models, theorems, and proofs are formalized in the interactive proof system Isabelle/HOL.

  • formal verication of a framework for microkernel programmers
    2009
    Co-Authors: Alexandra Tsyban
    Abstract:

    This thesis presents the formal verification of a framework for microkernel programmers called CVM (communicating virtual machines) [41]. CVM is a computational model for concurrent user processes interacting with a generic microkernel and devices. It is implemented in C0A, a restricted C-dialect with support of Inline Assembly, as a framework featuring virtual memory, demand paging, memory management, and low-level inter-process and devices communications. The framework can be linked on the source code level with an abstract kernel, an interface to users, in order to obtain a concrete kernel, a program that can be translated and run on a target machine. We use a formally verified microprocessor VAMP [20] as a platform to run the concrete kernel. The main result of this work is a mechanically checked formal proof that concurrent executions of user processes interacting with a kernel are simulated by executions of the VAMP instruction set architecture model interleaved with devices. In order to obtain this result a number of attendant formal theories have been developed, most notably, a theory of Inline Assembly verification. This work is a part of the Verisoft project [111], a large scale effort bringing together industrial and academic partners to push the state-of-the-art in formal verification for realistic computer systems comprising hardand software.

  • VSTTE - Verified Process-Context Switch for C-Programmed Kernels
    Verified Software: Theories Tools Experiments, 1
    Co-Authors: Artem Starostin, Alexandra Tsyban
    Abstract:

    A context switch -- an act of saving and restoring the state of a CPU such that multiple processes can share a single CPU resource -- is an essential feature of multitasking operating systems. Commonly computationally intensive and necessarily accessing hardware registers, context-switch procedures are implemented as Inline Assembly portions in C-programmed operating-system kernels. Feasible verification of operating systems is usually attempted in some kind of C semantics. However, seamless verification of kernels requires reasoning about context-switch routines in semantics of Assembly language. At the end of the day, both semantics meet together in an overall correctness theorem of operating system. The task of formal integration of correctness results achieved on different semantical layers is challenging but inevitable for systems verification. The paper describes a formal approach to pervasive reasoning about interleaved computations of user processes and a C-programmed kernel. The interleaving is achieved by context-switch procedures implemented in Inline Assembly. We report on the correctness proof of the context-switch procedures and elaborate on our experience in formal integration of this result into the correctness proof of CVM, a verified framework for microkernel programmers.

Frédéric Recoules - One of the best experts on this subject based on the ideXlab platform.

  • get rid of Inline Assembly through verification oriented lifting
    Automated Software Engineering, 2019
    Co-Authors: Frédéric Recoules, Sébastien Bardin, Richard Bonichon, Laurent Mounier, Marie-laure Potet
    Abstract:

    Formal methods for software development have made great strides in the last two decades, to the point that their application in safety-critical embedded software is an undeniable success. Their extension to non-critical software is one of the notable forthcoming challenges. For example, C programmers regularly use Inline Assembly for low-level optimizations and system primitives. This usually results in rendering state-of-the-art formal analyzers developed for C ineffective. We thus propose TINA, the first automated, generic, verification-friendly and trustworthy lifting technique turning Inline Assembly into semantically equivalent C code amenable to verification, in order to take advantage of existing C analyzers. Extensive experiments on real-world code (including GMP and ffmpeg) show the feasibility and benefits of TINA.

  • Get rid of Inline Assembly through verification-oriented lifting
    arXiv: Programming Languages, 2019
    Co-Authors: Frédéric Recoules, Sébastien Bardin, Richard Bonichon, Laurent Mounier, Marie-laure Potet
    Abstract:

    Formal methods for software development have made great strides in the last two decades, to the point that their application in safety-critical embedded software is an undeniable success. Their extension to non-critical software is one of the notable forthcoming challenges. For example, C programmers regularly use Inline Assembly for low-level optimizations and system primitives. This usually results in driving state-of-the-art formal analyzers developed for C ineffective. We thus propose TInA, an automated, generic, trustable and verification-oriented lifting technique turning Inline Assembly into semantically equivalent C code, in order to take advantage of existing C analyzers. Extensive experiments on real-world C code with Inline Assembly (including GMP and ffmpeg) show the feasibility and benefits of TInA.

  • get rid of Inline Assembly through trustable verification oriented lifting
    2019
    Co-Authors: Frédéric Recoules, Sébastien Bardin, Richard Bonichon, Laurent Mounier, Marie-laure Potet
    Abstract:

    Formal methods for software development have made great strides in the last two decades, to the point that their application in safety-critical embedded software is an undeniable success. Their extension to non-critical software is one of the notable forthcoming challenges. For example, C programmers regularly use Inline Assembly for low-level optimizations and system primitives. This usually results in driving state-of-the-art formal analyzers developed for C ineffective. We thus propose TInA, an automated, generic, trustable and verification-oriented lifting technique turning Inline Assembly into semantically equivalent C code, in order to take advantage of existing C analyzers. Extensive experiments on real-world C code with Inline Assembly (including GMP and ffmpeg) show the feasibility and benefits of TInA.

  • ASE - Get Rid of Inline Assembly through Verification-Oriented Lifting
    2019 34th IEEE ACM International Conference on Automated Software Engineering (ASE), 2019
    Co-Authors: Frédéric Recoules, Sébastien Bardin, Richard Bonichon, Laurent Mounier, Marie-laure Potet
    Abstract:

    Formal methods for software development have made great strides in the last two decades, to the point that their application in safety-critical embedded software is an undeniable success. Their extension to non-critical software is one of the notable forthcoming challenges. For example, C programmers regularly use Inline Assembly for low-level optimizations and system primitives. This usually results in rendering state-of-the-art formal analyzers developed for C ineffective. We thus propose TINA, the first automated, generic, verification-friendly and trustworthy lifting technique turning Inline Assembly into semantically equivalent C code amenable to verification, in order to take advantage of existing C analyzers. Extensive experiments on real-world code (including GMP and ffmpeg) show the feasibility and benefits of TINA.

Stephan Falke - One of the best experts on this subject based on the ideXlab platform.

  • llbmc a bounded model checker for llvm s intermediate representation competition contribution
    Tools and Algorithms for Construction and Analysis of Systems, 2012
    Co-Authors: Carsten Sinz, Florian Merz, Stephan Falke
    Abstract:

    We present LLBMC, a bounded model checker for C programs. LLBMC uses the LLVM compiler framework in order to translate C programs into LLVM’s intermediate representation (IR). The resulting code is then converted into a logical representation and simplified using rewrite rules. The simplified formula is finally passed to an SMT solver. In contrast to many other tools, LLBMC uses a flat, bit-precise memory model. It can thus precisely model, e.g., memory-based re-interpret casts. 1 Verification Approach Bounded model checking (BMC) has proven to be a very successful technique in hardware verification. More recently, it has also been applied for verifying software written in C [1,4]. Applying BMC for verifying C programs, however, comes with many obstacles that have to be tackled. One of the most important differences is that the syntax and semantics of a programming language like C is much more complicated than a hardware description. One has to deal, e.g., with memory allocation and de-allocation, (function) pointers, complex data structures, and function calls. LLBMC uses an approach which, instead of exploring the source code directly, makes use of existing compiler technology and performs the analysis on a compiler intermediate representation. Such an intermediate representation offers a much simpler syntax and semantics than a programming language like C, and thus eases a logical encoding of the verification problem considerably. We have chosen the LLVM [5] compiler infrastructure and its assembler-like intermediate representation as the starting point for our approach, but the idea can also be applied to other low-level languages. LLVM is both a (GCC-compatible) C/C++/Objective-C compiler and a library of compiler technologies, providing, e.g., sourceand target-independent optimizations. Our primary goal is to detect memory errors in C code [7,2,6]. Memory errors include invalid memory accesses, heap and stack buffer overflows, and invalid frees (e.g., double frees). This work was supported in part by the “Concept for the Future” of Karlsruhe Institute of Technology within the framework of the German Excellence Initiative. C. Flanagan and B. Konig (Eds.): TACAS 2012, LNCS 7214, pp. 542–544, 2012. c © Springer-Verlag Berlin Heidelberg 2012 LLBMC: A Bounded Model Checker for LLVM’s Intermediate Representation 543 2 Software Architecture While LLBMC is designed for C programs, its input format is LLVM-IR, the intermediate representation of the LLVM compiler framework. LLVM-IR is an abstract assembler language that is programming-language-independent. This makes it easier to extend LLBMC to other languages supported by LLVM (like C++ or Objective-C). Furthermore, the challenges in parsing complex high-level language syntax, such as C++, are eliminated. Instead, only a limited instruction set needs to be supported. LLVM-IR is architecture-dependent in the sense that the compiler frontend selects, e.g., the bitwidth of pointers and integer data types. After reading in the LLVM-IR code, LLBMC applies a number of transformations to it. In particular, loops are unrolled, functions are Inlined, and the control flow graph is simplified. The transformed code is then converted to ILR, which is a representation of a program in the logic of bit-vectors and arrays plus some extensions, related to memory allocation. ILR provides an explicit state object for the memory content as well as for the state of the memory allocation system. These state objects encode the dependencies between memory accessing instructions in the ILR formula. Because of this, dependencies between instructions in LLVM, which were implicitly given by the ordering of the read and write operations are made explicit in the ILR formula. This change makes the expressions in an ILR formula ordering-independent. The ILR formula is then simplified using rewrite rules, and memory access correctness expressions are reduced to bit-vector formulas (see [2,7] for details). If no more rewrite rules can be applied, the formula is passed to the SMT solver STP [3]. 3 Strengths and Weaknesses of the Approach LLBMC is tailored towards finding bugs in C programs, especially memory-related ones (not so much towards proving their absence). Detectable errors include: – arithmetic overflow and underflow, including shift overflow, – invalid memory access operations, – invalid memory allocation, including invalid frees, and – overlapping memory regions in memcpy. Furthermore, LLBMC supports checking of user assertions and reachability of labels named “ERROR” in the C-code. It can also detect whether the loop unrolling and function inlining bound was sufficient or has to be increased in order to achieve full coverage. In the competition, LLBMC was used with a fixed unwinding bound of 7 and an automatically determined function inlining bound. It was not checked whether the unwinding bound is sufficient, but only whether the “ERROR” label was reachable within these bounds (as other comparable tools have chosen similar settings). If no error was found, the instance was considered safe. LLBMC was able to successfully handle 146 out of 269 benchmark instances (not participating in category “Concurrency”, as this is not supported by LLBMC), resulting in a first place in category “Device Drivers” and a second place in category “Heap 544 C. Sinz, F. Merz, and S. Falke Manipulation”. Among the unsolved instances, 65 were due to time-outs, and 48 due to current restrictions of LLBMC (e.g., related to memcpy or Inline Assembly). LLBMC produced 7 false positives and 3 false negatives. The false negatives (i.e. where an error was missed) were due to an insufficient loop unrolling bound. Among the 7 false positives, one was due to an error in LLBMC related to detecting a malloc function. The other 6 were due to uninitialized pointer variables, by which other (e.g., global) variables could be overwritten and thus be modified, resulting in the “ERROR” label becoming reachable. We do not consider these errors as “false positives”, but see here a special strength of LLBMC and its precise memory model, as such errors are very hard to detect and, in practice, result in non-deterministic program behavior. 4 Tool Setup and Configuration The version of LLBMC (0.9) submitted to TACAS can be downloaded from http://llbmc.org/llbmc-tacas12.zip. LLBMC requires llvm-gcc (version 2.9) in order to convert C input files to LLVM’s intermediate representation. For instructions on how to use LLBMC, just enter llbmc --help. The ZIP archive also contains two wrapper shell scripts to run LLBMC on individual C files. The first, llbmcc, iteratively increases the loop unwind bound and also checks whether the unwind bound is sufficient. The second, llbmcc2, which was used in the competition, also increases the unwind bound, but only up to a maximal value of 7, and does not perform unwind bound checks. Both shell scripts compile the C program, run LLBMC, and perform only a reachability check for a basic block labelled “ERROR”, but no other checks, such as for invalid memory accesses. They output either SAFE, if the error label is unreachable (within the given bound for llbmcc2), or UNSAFE otherwise. Further information on LLBMC is available on the web at http://llbmc.org.

  • TACAS - LLBMC: A Bounded Model Checker for LLVM's Intermediate Representation - (Competition Contribution).
    2012
    Co-Authors: Carsten Sinz, Florian Merz, Stephan Falke
    Abstract:

    We present LLBMC, a bounded model checker for C programs. LLBMC uses the LLVM compiler framework in order to translate C programs into LLVM’s intermediate representation (IR). The resulting code is then converted into a logical representation and simplified using rewrite rules. The simplified formula is finally passed to an SMT solver. In contrast to many other tools, LLBMC uses a flat, bit-precise memory model. It can thus precisely model, e.g., memory-based re-interpret casts. 1 Verification Approach Bounded model checking (BMC) has proven to be a very successful technique in hardware verification. More recently, it has also been applied for verifying software written in C [1,4]. Applying BMC for verifying C programs, however, comes with many obstacles that have to be tackled. One of the most important differences is that the syntax and semantics of a programming language like C is much more complicated than a hardware description. One has to deal, e.g., with memory allocation and de-allocation, (function) pointers, complex data structures, and function calls. LLBMC uses an approach which, instead of exploring the source code directly, makes use of existing compiler technology and performs the analysis on a compiler intermediate representation. Such an intermediate representation offers a much simpler syntax and semantics than a programming language like C, and thus eases a logical encoding of the verification problem considerably. We have chosen the LLVM [5] compiler infrastructure and its assembler-like intermediate representation as the starting point for our approach, but the idea can also be applied to other low-level languages. LLVM is both a (GCC-compatible) C/C++/Objective-C compiler and a library of compiler technologies, providing, e.g., sourceand target-independent optimizations. Our primary goal is to detect memory errors in C code [7,2,6]. Memory errors include invalid memory accesses, heap and stack buffer overflows, and invalid frees (e.g., double frees). This work was supported in part by the “Concept for the Future” of Karlsruhe Institute of Technology within the framework of the German Excellence Initiative. C. Flanagan and B. Konig (Eds.): TACAS 2012, LNCS 7214, pp. 542–544, 2012. c © Springer-Verlag Berlin Heidelberg 2012 LLBMC: A Bounded Model Checker for LLVM’s Intermediate Representation 543 2 Software Architecture While LLBMC is designed for C programs, its input format is LLVM-IR, the intermediate representation of the LLVM compiler framework. LLVM-IR is an abstract assembler language that is programming-language-independent. This makes it easier to extend LLBMC to other languages supported by LLVM (like C++ or Objective-C). Furthermore, the challenges in parsing complex high-level language syntax, such as C++, are eliminated. Instead, only a limited instruction set needs to be supported. LLVM-IR is architecture-dependent in the sense that the compiler frontend selects, e.g., the bitwidth of pointers and integer data types. After reading in the LLVM-IR code, LLBMC applies a number of transformations to it. In particular, loops are unrolled, functions are Inlined, and the control flow graph is simplified. The transformed code is then converted to ILR, which is a representation of a program in the logic of bit-vectors and arrays plus some extensions, related to memory allocation. ILR provides an explicit state object for the memory content as well as for the state of the memory allocation system. These state objects encode the dependencies between memory accessing instructions in the ILR formula. Because of this, dependencies between instructions in LLVM, which were implicitly given by the ordering of the read and write operations are made explicit in the ILR formula. This change makes the expressions in an ILR formula ordering-independent. The ILR formula is then simplified using rewrite rules, and memory access correctness expressions are reduced to bit-vector formulas (see [2,7] for details). If no more rewrite rules can be applied, the formula is passed to the SMT solver STP [3]. 3 Strengths and Weaknesses of the Approach LLBMC is tailored towards finding bugs in C programs, especially memory-related ones (not so much towards proving their absence). Detectable errors include: – arithmetic overflow and underflow, including shift overflow, – invalid memory access operations, – invalid memory allocation, including invalid frees, and – overlapping memory regions in memcpy. Furthermore, LLBMC supports checking of user assertions and reachability of labels named “ERROR” in the C-code. It can also detect whether the loop unrolling and function inlining bound was sufficient or has to be increased in order to achieve full coverage. In the competition, LLBMC was used with a fixed unwinding bound of 7 and an automatically determined function inlining bound. It was not checked whether the unwinding bound is sufficient, but only whether the “ERROR” label was reachable within these bounds (as other comparable tools have chosen similar settings). If no error was found, the instance was considered safe. LLBMC was able to successfully handle 146 out of 269 benchmark instances (not participating in category “Concurrency”, as this is not supported by LLBMC), resulting in a first place in category “Device Drivers” and a second place in category “Heap 544 C. Sinz, F. Merz, and S. Falke Manipulation”. Among the unsolved instances, 65 were due to time-outs, and 48 due to current restrictions of LLBMC (e.g., related to memcpy or Inline Assembly). LLBMC produced 7 false positives and 3 false negatives. The false negatives (i.e. where an error was missed) were due to an insufficient loop unrolling bound. Among the 7 false positives, one was due to an error in LLBMC related to detecting a malloc function. The other 6 were due to uninitialized pointer variables, by which other (e.g., global) variables could be overwritten and thus be modified, resulting in the “ERROR” label becoming reachable. We do not consider these errors as “false positives”, but see here a special strength of LLBMC and its precise memory model, as such errors are very hard to detect and, in practice, result in non-deterministic program behavior. 4 Tool Setup and Configuration The version of LLBMC (0.9) submitted to TACAS can be downloaded from http://llbmc.org/llbmc-tacas12.zip. LLBMC requires llvm-gcc (version 2.9) in order to convert C input files to LLVM’s intermediate representation. For instructions on how to use LLBMC, just enter llbmc --help. The ZIP archive also contains two wrapper shell scripts to run LLBMC on individual C files. The first, llbmcc, iteratively increases the loop unwind bound and also checks whether the unwind bound is sufficient. The second, llbmcc2, which was used in the competition, also increases the unwind bound, but only up to a maximal value of 7, and does not perform unwind bound checks. Both shell scripts compile the C program, run LLBMC, and perform only a reachability check for a basic block labelled “ERROR”, but no other checks, such as for invalid memory accesses. They output either SAFE, if the error label is unreachable (within the given bound for llbmcc2), or UNSAFE otherwise. Further information on LLBMC is available on the web at http://llbmc.org.

Eyad Alkassar - One of the best experts on this subject based on the ideXlab platform.