Skip to content
No description, website, or topics provided.
Coq Ruby Other
Branch: v3.5
Clone or download
Latest commit c34dc79 Nov 13, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
backend Simplify MatchSimModSem Oct 24, 2019
bound remove comments (#3) Oct 20, 2019
cfrontend Simplify MatchSimModSem Oct 24, 2019
common Move some files Jul 10, 2019
compose remove comments (#3) Oct 20, 2019
demo Simplify MatchSimModSem Oct 24, 2019
driver hotfix Jul 11, 2019
lib remove Print and Compute Keywords Jul 10, 2019
proof Apply comments Nov 13, 2019
scripts Fix to print tex Jul 11, 2019
selfsim Simplify MatchSimModSem Oct 24, 2019
x86 Simplify MatchSimModSem Oct 24, 2019
x86_64
.gitignore move mkPR definition from RUSC.v to AdequacyLocal.v Oct 20, 2019
Makefile Redir some files Jul 10, 2019
README.md Update README.md Nov 13, 2019
admits.sh Tweak Jul 7, 2019
count.rb dongjoo's work : reduce line numbers Jul 9, 2019
count_dir.sh Add LOC counting script May 28, 2019
make_graph.sh modify Makefile Apr 22, 2019

README.md

CompCertM: CompCert with Lightweight Modular Verification and Multi-Language Linking

Build

CompCertM is based on CompCertR which is a refactored version of CompCert. In order to build CompCertM, you need to build CompCertR first.

  1. Clone https://github.com/snu-sf/CompCertR and follow the installation instructions.

  2. Go to the CompCertR directory and issue the following commands:

    git clone https://github.com/snu-sf/CompCertM.git
    cd CompCertM
    make -j[N]

Or, you can download a Docker image in which /home/coq/CompCertR/CompCertM contains the build result:

docker pull minkiminki/popl20-93:v3.5
docker run -it minkiminki/popl20-93:v3.5

Code Structure

For directories that existed in CompCert (e.g. backend/), there are files that extends original CompCert's files.

New directories are roughly as follows.

  • bound/: adequacy w.r.t. C and assembly (UpperBound_A.v, UpperBound_B.v, LowerBound.v)
  • compose/: interaction semantics and its properties
  • demo/: examples including Unreadglob, mutual-sum and utod
  • selfsim/: self-simulation of Clight and Assembly
  • scripts/: scripts used for SLOC counting (Table 1, 2, 3)
  • proof/: our meta theory

We list a few important definitions/proofs from the paper.

Semantics

Verification Techniques

Correctness Theorems

Examples

Workflow

We first describe a step-by-step process of software verification using CompCert, and then describe such instructions for CompCertM.

(Running) Write a C program, compile it to binary using CompCert executable (i.e. ccomp), and run it.

(Verifying)

  • Translate each C module into Coq using clightgen.
  • CompCert's C semantics formally defines behavior of your translated program.
  • Verify properties about such behavior with your own technique. (e.g. a workflow using VST)

For CompCertM, it is basically the same except we also support hand-written assembly modules.

(Running) Write a program (you can use both C and assembly), compile C modules to binary using CompCert executable (i.e. compcomp), and run it. (a.c, b.s)

(Verifying)

  • Translate each C module into Coq using clightgen as before. (MutrecA.v)

    Unfortunately, as there is no such translation tool yet for assembly language, user should manually translate assembly modules into Coq. (MutrecB.v)

    CompCert emits assembly module (defined in Coq) into actual .s file using PrintAsm.ml.

    You should make sure that printing your assembly (defined in Coq) using PrintAsm.ml yields a .s file that is equivalent to the one you have manually wrote.

  • CompCertM's interaction semantics formally defines behavior of your translated program.

  • Verify properties about such behavior with your own technique.

    As discussed in the paper, we advocate the use of RUSC theory in program verification, and we demonstrate this with mutrec example.

    Define open specs for each module. (MutrecAspec.v, MutrecBspec.v)

    Verify each module against its specification modularly. (MutrecAproof.v, MutrecBproof.v)

    Merge such open specs togather (MutrecABproof.v)

    Prove self-simulations required for RUSC theory. (IdSim*.v)

    Get final result with RUSC theory. (MutrecRefinement.v)

Delta Between Paper's Presentation

Roughly speaking, the implementation is strictly more general or equivalent to the presentation of the paper.

Fig 11

  • In (STEP) case, the implementation is more general than the paper version, allowing "stuttering". (We support 4 different kinds of stuttering, forward/backward x source/target)
  • In (CALL) case, the implementation existentially quantifies source call data ((SAFESRC: ms_src.(is_call) st_src0)) and then universally quantifies it (ATSRC: ms_src.(at_external) st_src0 args_src), following forward simulation style. In paper, it is just existentially quantified. However, as we require at_external to be deterministic (ModSem.at_external_dtm), both are equivalent. The implementation followed this style just for uniformity with forward (STEP) case.
  • The paper hides coinductive nature of open_sim (following CompCert's style), but in implementation we used coinductive predicate using Paco library, which gives more flexibility to the user (e.g. allowing intermediate states outside the match_states).
  • In (INIT) case, the paper presents it in a forward-style, but it is implemented in backward-style.
  • In paper, (SIM:MOD) asserts open_prsv of sound_state but in implementation (SIM:MODSEM) asserts it. We designed Mod datatype to be minimal syntactic data, so it does not know the type of state and can't state about sound_state. Changing the implementation to follow the paper's presentation will take just 3 person-hour or so, but we prefer current design.
  • In implementation, we have local_preservation_noguarantee which is not mentioned in the paper. This predicate is strictly easier to prove than the local_preservation, lessening the proof obligation for user once (s)he has proven local_preservation for at least one analysis.
You can’t perform that action at this time.