Translating Xd-C programs to MSVL programs

DOI10.1016/J.TCS.2019.12.038MaRDI QIDQ2290648zbMATH OpenOpenAlexWikidataFDO

Authors Meng Wang, Cong Tian, Nan Zhang, Zhenhua Duan, Chenguang Yao

Publication date 29 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.00959

zbMATH Keywords

verificationmodel checkingtranslationC languageMSVL

Mathematics Subject Classification ID

Theory of programming languages (68N15) Theory of compilers and interpreters (68N20) Specification and verification (program logics, model checking, etc.) (68Q60)

Abstract: C language is one of the most popular languages for software systems. In order to verify safety, reliability and security properties of such systems written in C, a tool UMC4M for runtime verification at code level based on Modeling, Simulation and Verification Language (MSVL) and its compiler MC is employed. To do so, a C program $P$ has to be translated to an MSVL program M and the negation of a desired property $Q$ is also translated to an MSVL program M', then "M and M" is compiled and executed armed with MC. Whether $P$ violates $Q$ is checked by evaluating whether there exists an acceptable execution of new MSVL program M and M". Therefore, how to translate a C program to an MSVL program is a critical issue. However, in general, C is of complicated structures with goto statement. In this paper, we confine the syntax of C in a suitable subset called Xd-C without loss of expressiveness. Further, we present a translation algorithm from an Xd-C program to an MSVL program based on translation algorithms for expressions and statements. Moreover, the equivalences between expressions and statements involved in Xd-C and MSVL programs are inductively proved. Subsequently, the equivalence between the original Xd-C program and the translated MSVL program is also proved. In addition, the proposed approach has been implemented by a tool called $C2M$. A benchmark of experiments including 13 real-world Xd-C programs is conducted. The results show that $C2M$ works effectively.

Recommendations

• Model Checking MSVL Programs Based on Dynamic Symbolic Execution
• Automated Technology for Verification and Analysis
• A proof system for MSVL programs in Coq
• Towards verification of C programs. C-light language and its formal semantics
• Model checking Petri nets with MSVL

Cites work

• scientific article; zbMATH DE number 1744961 (Why is no real title available?)
• scientific article; zbMATH DE number 1903365 (Why is no real title available?)
• A compiler for MSVL and its applications
• A decision procedure for propositional projection temporal logic with infinite models
• A mechanism of function calls in MSVL
• A practical decision procedure for propositional projection temporal logic with infinite models
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• Efficient abstraction algorithms for predicate detection
• Fairness modulo theory: a new approach to LTL software model checking
• Framed temporal logic programming
• Kernel P systems: from modelling to verification and testing
• Lazy abstraction
• Mechanized semantics for the clight subset of the C language
• Operational semantics of Framed Tempura
• Tools and algorithms for the construction and analysis of systems. 20th international conference, TACAS 2014, held as part of the European joint conferences on theory and practice of software, ETAPS 2014, Grenoble, France, April 5--13, 2014. Proceedings

Cited in

(3)

• C2M
• Generating Java code pairing with ChatGPT
• Ownership guided C to Rust translation

Describes a project that uses

Uses Software

• MSVL
• UMC4M
• MinGW
• LTLAutomizer
• RiTHM
• CBMC
• CPAchecker
• NuSMV
• SPIN
• BLAST

This page was built for publication: Translating Xd-C programs to MSVL programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2290648)