CREST: Hardware Formal Verification with ANSI-C Reference Specifications

Andreas Tiemeyer; Daniel Kroening; John O'Leary; Tom Melham

REVIEW 3 major objections 4 minor 11 references

CREST: Hardware Formal Verification with ANSI-C Reference Specifications

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read CREST establishes a general path from full ANSI-C reference specifications to bit-level Verilog for RTL formal verification.

desk verdict A genuinely useful C-to-Verilog pipeline with an overstated 'arbitrary ANSI-C' claim; worth reviewing with a request to document CBMC's unwinding bounds. read the letter →

arxiv 1908.01324 v1 pith:723WHQ6H submitted 2019-08-04 cs.PL cs.ARcs.SC

Andreas Tiemeyer , Tom Melham , Daniel Kroening , John O'Leary This is my paper · ORCID

classification cs.PLcs.ARcs.SC

keywords formalhardwareverificationC-to-VerilogtranslationANSI-Creferencespecificationsequivalencecheckingboundedmodelsymbolicexecutionfloating-pointRTL

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that high-level ANSI-C datapath models, written in unrestricted, natural C with pointers, casts, unions, recursion, and function pointers, can serve as reference specifications for formal RTL verification. To do this, CREST takes the symbolic-execution output of a mature bounded model checker for C and lowers each assignment to a Verilog bitvector expression, producing simple Verilog that a commercial equivalence-checking tool can read. The point is to make "verify this RTL against my C model" practical without forcing the C into a synthesizable subset or a hardware-oriented dialect. The paper demonstrates the claim on floating-point addition and multiplication, an approximate-reciprocal instruction model, a video-codec transform, and a sequential floating-point adder.

What carries the argument

The load-bearing mechanism is the single-static-assignment (SSA) assignment stream produced after symbolic execution: after loop unwinding and interpretation of pointers, casts, and conversions, the C program is reduced to a flat set of assignments over bitvector variables, with every expression still annotated back to its source line. CREST translates that stream directly: each SSA variable becomes a Verilog bitvector, each C operator becomes the equivalent Verilog operator, and unsupported expression forms, such as bit-range extraction from an arbitrary expression, are lowered through auxiliary variables. This is what lets the tool inherit full ANSI-C coverage without building a new C front end.

What would settle it

Compile the generated Verilog and the original C function to two oracles and run them on the same exhaustive input set for a small datapath, such as all 16-bit floating-point operand pairs including subnormals, NaNs, and infinities, plus targeted programs using pointer casts, unions, and function pointers; any discrepancy between the Verilog simulation and the C execution would refute the claim that the translation captures ANSI-C semantics.

Watch

Extended reading notes

Core claim

The central claim is that the bit-level semantics of full ANSI-C can be captured in a low-level Verilog model by tapping into a bounded model checker after symbolic execution, when all high-level C constructs have already been interpreted away and the program is a set of single-static-assignment assignments over bitvectors. CREST maps each such variable to a Verilog bitvector and each right-hand-side expression to the corresponding Verilog expression, adding auxiliary signals where Verilog forbids operations such as extracting a bit range from an expression. The resulting Verilog is not a synthesized circuit but a proof-oriented representation that reproduces the exact bit-level behavior of the C code, including arithmetic conversions, pointer dereferencing, and type punning. The paper further claims that the generated model can be used by off-the-shelf RTL formal-verification tools to prove equivalence against other reference models or implementations.

Load-bearing premise

The hand-written mapping from the intermediate assignment representation to Verilog is assumed to preserve the meaning of every ANSI-C construct, and this mapping is not itself verified by an independent checker.

Editorial extensions

If this is right

Equivalence checking against a C reference model can be run inside commercial EDA tools for floating-point operations, with 16-, 32-, and 64-bit addition passing automatically.
For designs where two models compute in structurally different ways, the C-to-Verilog spec does not remove the need for case splits and intermediate invariants; multiplication required a three-case decomposition.
User-written assertions in C are translated to SVA assertions, so the same properties can be checked both in the C model and in the generated Verilog.
Sequential RTL can be verified against a combinational C specification: the clocked floating-point adder was shown to be standard compliant exactly when the CREST spec is standard compliant.
The generated Verilog can serve as an independent reference for checking circuits produced by high-level synthesis from the same C source.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Inference: If the translator is trusted, the same C-to-Verilog path could also turn arbitrary C testbenches or reference models into simulation oracles for coverage-driven and dynamic validation flows, not just formal equivalence checks.
Inference: The architecture suggests a general recipe: reuse a mature software model checker's middle end as a C-to-logic front end, so improvements in software verification automatically strengthen hardware verification coverage.
Inference: A testable extension is differential testing of the generated Verilog against the original C compiled with a reference compiler across a corpus of tricky ANSI-C constructs, which would empirically certify the hand-written translation mapping.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague, here's my read.

The genuinely new thing here is CREST's pipeline: tap CBMC after symbolic execution, turn its SSA assignments into Verilog bitvectors, and feed that to an RTL equivalence checker. That is a sensible engineering move, and it lets hardware teams keep natural C reference models--including type punning and function pointers--without rewriting them in a synthesizable subset. The five case studies are the right kind of evidence: SoftFloat against VGM, Intel's RECIP14 model against a shipping design, VP9 asserts, a sequential FP adder. They use external benchmarks, report runtimes, and the multiplication study is honest about needing manual decomposition. That is real credit.

The soft spot is the abstract's 'arbitrary ANSI-C.' CREST inherits CBMC's bounds: loops are unwound to a finite depth, and recursion is not automatic. Section III-C admits the RECIP14 model was hand-unrolled. So the tool does not process arbitrary ANSI-C as written; it processes the finite unwinding of a given program. The paper never states the unwinding bound or a completeness argument. For datapath specs with compile-time-bounded loops that may be fine, but the claim as printed is stronger than the demonstration.

Secondary, but real: the SSA-to-Verilog translator itself is hand-coded and not verified. A bug there would break every downstream equivalence claim. The paper does not release an artifact, so I can't check it. That limits confidence, but this is a tool paper; I would not demand a proof of the translator, just a clear statement of its tested coverage.

The stress-test note is right that the bounded-execution issue is primary; the translator concern is secondary but still fair.

Who gets value: anyone working on C-based hardware reference models or high-level synthesis validation. It deserves peer review, not desk reject. A good referee should ask for a clear statement of the actual subset handled and, ideally, an artifact or more case studies.

Recommendation: send to review, but expect a revision that calibrates the 'arbitrary ANSI-C' claim and documents the loop-unwinding protocol.

Referee Report

3 major / 4 minor

Summary. The paper presents CREST, a prototype front-end that translates ANSI-C reference specifications into Verilog for use as reference models in RTL formal verification. The translation taps into the CBMC bounded model checker after symbolic execution, converting the resulting SSA form into combinational Verilog. The authors claim that CREST handles arbitrary ANSI-C without restricting to a synthesizable subset, and they report five case studies: SoftFloat versus VGM floating-point addition (with concrete runtimes), floating-point multiplication with manual proof decomposition, an Intel approximate-reciprocal model, WebM VP9 matrix transforms with dynamic function pointers, and a sequential floating-point adder. The paper positions CREST as a generic front-end for commercial EDA verification flows and describes possible future extensions.

Significance. If the central claim holds, CREST would offer a general path from natural, unconstrained C models to RTL formal verification, leveraging CBMC's mature bit-level semantics of C. The paper's strength is that the evaluation is anchored to external benchmarks and references: SoftFloat is checked against the VGM library, the reciprocal model against a proprietary reference and a shipping RTL design, and the VP9 assertions against a commercial tool. The concrete runtimes for floating-point addition and the explicit case split for multiplication are informative. However, the paper does not provide an artifact or a formal correctness argument for the SSA-to-Verilog translation, and the case studies contain manual interventions that substantially weaken the claim of handling arbitrary ANSI-C as written. The significance of the work is therefore conditional on a more carefully scoped statement of what CREST actually accepts and a clear account of its soundness.

major comments (3)

[Section II (Architecture and Implementation)] The central claim that CREST processes 'arbitrary ANSI-C' is not supported by the described architecture. CBMC's symbolic execution is bounded: loops are unwound to a finite depth, and the paper gives no unwinding bound, no completeness criterion, and no protocol for loops with input-dependent trip counts. The generated combinational Verilog therefore represents only a finite prefix of the C program's symbolic execution, unless additional proof is supplied. The paper should either qualify the 'arbitrary ANSI-C' claim to 'ANSI-C for which a sufficient loop unwinding can be established' or describe a mechanism for discharging the completeness obligation.
[Section III-C (Approximate Reciprocal)] This case study directly contradicts the unrestricted-language claim. The Intel reciprocal model was written recursively, and the authors state, 'We chose to unroll the recursion by hand, and used CBMC as a model checker to prove the assertions that justify the correctness of the unrolling transformation.' This is a manual, specification-dependent transformation performed before CREST processes the code; CREST did not translate the original ANSI-C as written. The paper must either present an automated handling of such recursion or explicitly exclude recursive code from the supported subset.
[Section II (Translation to Verilog)] The correctness of the SSA-to-Verilog translation is assumed rather than established. The paper states that CREST 'translates each variable in this representation to a Verilog bitvector and each C expression on the right-hand side of the assignments to a corresponding Verilog expression,' but it gives no formal semantics preservation argument and no differential validation of the translation against CBMC's own bit-level semantics. Because CREST-generated Verilog is used as the reference model in equivalence proofs, a translation bug would invalidate all downstream verification results. The paper should at least report the results of running generated Verilog and C on the same test vectors, ideally with randomized or exhaustive bit-pattern tests for each supported construct.

minor comments (4)

[Throughout] There are numerous typographical errors and spacing artifacts, such as 'verifcat ion', 'V eriﬁcation', and 'speciﬁca tions', which should be corrected with careful proofreading.
[Section III-B] The bit-vector correspondence equations contain 'quotesingle' artifacts in the PDF text (e.g., 'SoftFloat.mul_in_1[63:31] = 33/quotesingle.Varb0'), which makes them unreadable. These should be typeset as proper Verilog or mathematical notation.
[Section III-A] The runtimes for floating-point addition are presented as an inline table without a caption or formatting. A proper numbered table with units and a column for precision width would improve clarity.
[Section III-D] The sentence 'The code also contains several user-written assertions, which are are translated into SV A assertions by our tool' contains a duplicated 'are' and should read 'which are translated into SVA assertions'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: CREST's claims are validated against external benchmarks; the bounded-unwinding limitation is a completeness risk, not a circular step.

full rationale

CREST's reported validation is anchored to external benchmarks: SoftFloat is checked against the VGM library, the approximate reciprocal against a proprietary hand-coded reference and an optimized RTL design, and the VP9 assertions against a commercial RTL verification tool. The central SSA-to-Verilog translation is an implemented artifact rather than an equation fitted to the case-study outcomes, so no fitted parameter is renamed as a prediction. The paper's use of CBMC is as an execution engine, not as the criterion of success; self-citations such as [2] and [3] describe prior tools and methods but do not substitute for the reported experiments. The only notable limitation is in Section III-C, where recursive code was hand-unrolled and the paper says 'We chose to unroll the recursion by hand, and used CBMC as a model checker to prove the assertions that justify the correctness of the unrolling transformation.' This undermines the breadth of the 'arbitrary ANSI-C' claim, but it is a completeness and correctness risk, not a circular derivation: the unrolled model is still checked against external references, and the model-checking step is an independent verification of a source transformation. No result in the paper is defined in terms of itself, and no load-bearing argument reduces to a self-citation chain. The appropriate circularity finding is therefore no significant circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper rests on the correctness of CBMC's C semantics, the correctness of downstream EDA tools, and the correctness of the external reference models used in the case studies. None of these are proven within the paper, but they are standard engineering assumptions for a tool built on existing components.

assumptions (3)

domain assumption CBMC's symbolic execution faithfully captures the bit-level semantics of full ANSI-C, including pointer operations and floating-point conversions.
CREST inherits CBMC's semantics; any soundness gap in CBMC would propagate to the generated Verilog. This is invoked throughout Section II.
domain assumption The downstream formal verification tools (e.g., JasperGold SEC) correctly perform sequential equivalence checking on the generated Verilog.
The case study conclusions are obtained by running commercial EDA tools; the paper assumes these tools are sound.
domain assumption The external reference models (VGM, Intel RECIP14, proprietary references) correctly capture the intended hardware behavior.
Equivalence proofs compare CREST-generated Verilog against these references, so the hardware correctness depends on the references' accuracy, as stated in Section III.

how reviews work

0 comments

Cite this review

Pith. "Pith review of CREST: Hardware Formal Verification with ANSI-C Reference Specifications." pith.science (2026). https://pith.science/paper/723WHQ6H

@misc{pith2026190801324,
  author       = {Pith},
  title        = {Pith review of: CREST: Hardware Formal Verification with ANSI-C Reference Specifications},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/723WHQ6H}},
  note         = {Machine review of arXiv:1908.01324}
}

read the original abstract

This paper presents CREST, a prototype front-end tool intended as an add-on to commercial EDA formal verifcation environments. CREST is an adaptation of the CBMC bounded model checker for C, an academic tool widely used in industry for software analysis and property verification. It leverages the capabilities of CBMC to process hardware datapath specifications written in arbitrary ANSI-C, without limiting restrictions to a synthesizable subset. We briefly sketch the architecture of our tool and show its use in a range of verification case studies.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 10 canonical work pages

[1]

11em plus .33em minus .07em 4000 4000 100 4000 4000 500 `\.=1000 = #1 \@IEEEnotcompsoconly \@IEEEcompsoconly #1 * [1] 0pt [0pt][0pt] #1 * [1] 0pt [0pt][0pt] #1 * \| ** #1 \@IEEEauthorblockNstyle \@IEEEcompsocnotconfonly \@IEEEauthorblockAstyle \@IEEEcompsocnotconfonly \@IEEEcompsocconfonly \@IEEEauthordefaulttextstyle \@IEEEcompsocnotconfonly \@IEEEauthor...

work page 2019
[2]

R. B. Jones, J. W. O'Leary, C.-J. H. Seger, M. D. Aagaard, and T. F. Melham, ``Practical formal verification in microprocessor design,'' IEEE Design & Test of Computers , vol. 18, no. 4, pp. 16--25, July/August 2001

work page 2001
[3]

Mukherjee, S

R. Mukherjee, S. Joshi, A. Griesmayer, D. Kroening, and T. Melham, ``Equivalence checking of a floating-point unit against a high-level C model,'' in Formal Methods (FM), ser. LNCS, J. S. Fitzgerald, C. L. Heitmeyer, S. Gnesi, and A. Philippou, Eds., vol. 9995. 1em plus 0.5em minus 0.4em Springer, 2016, pp. 551--558

work page 2016
[4]

Clarke, D

E. Clarke, D. Kroening, and F. Lerda, ``A tool for checking ANSI-C programs,'' in Tools and Algorithms for the Construction and Analysis of Systems, ser. LNCS, vol. 2988. 1em plus 0.5em minus 0.4em Springer, 2004, pp. 168--176

work page 2004
[5]

B. Cook, K. Khazem, D. Kroening, S. Tasiran, M. Tautschnig, and M. R. Tuttle, ``Model checking boot code from AWS data centers,'' in Computer Aided Verification (CAV), ser. LNCS, H. Chockler and G. Weissenbacher, Eds., vol. 10982. 1em plus 0.5em minus 0.4em Springer, 2018, pp. 467--486. [Online]. Available: https://doi.org/10.1007/978-3-319-96142-2\_28

doi:10.1007/978-3-319-96142-2 2018
[6]

Hauser, ``Berkeley SoftFloat ,'' (Accessed 22 Jan

J. Hauser, ``Berkeley SoftFloat ,'' (Accessed 22 Jan. 2019). [Online]. Available: http://www.jhauser.us/arithmetic/SoftFloat.html

work page 2019
[7]

C.-J. H. Seger, R. B. Jones, J. W. O'Leary, T. Melham, M. D. Aagaard, C. Barrett, and D. Syme, ``An industrially effective environment for formal hardware verification,'' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 24, no. 9, pp. 1381--1405, September 2005

work page 2005
[8]

O'Leary, R

J. O'Leary, R. Kaivola, and T. Melham, ``Relational STE and theorem proving for formal verification of industrial circuit designs,'' in Formal Methods in Computer-Aided Design (FMCAD), B. Jobstmann and S. Ray, Eds. 1em plus 0.5em minus 0.4em IEEE, 2013, pp. 97--104

work page 2013

Show all 11 references

[9]

Intel, ``C code for RECIP14 ,'' (Accessed 28 Jan. 2019). [Online]. Available: https://software.intel.com/sites/default/files/managed/d3/4f/RECIP14.c

2019
[10]

WebM project authors , `` WebM : an open web media project,'' (Accessed 20 Jan. 2019). [Online]. Available: https://chromium.googlesource.com/webm/libvpx

2019
[11]

Dawson, ``Sequential floating point adder,'' (Accessed 22 Jan

J. Dawson, ``Sequential floating point adder,'' (Accessed 22 Jan. 2019). [Online]. Available: https://github.com/dawsonjon/fpu

2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

11em plus .33em minus .07em 4000 4000 100 4000 4000 500 `\.=1000 = #1 \@IEEEnotcompsoconly \@IEEEcompsoconly #1 * [1] 0pt [0pt][0pt] #1 * [1] 0pt [0pt][0pt] #1 * \| ** #1 \@IEEEauthorblockNstyle \@IEEEcompsocnotconfonly \@IEEEauthorblockAstyle \@IEEEcompsocnotconfonly \@IEEEcompsocconfonly \@IEEEauthordefaulttextstyle \@IEEEcompsocnotconfonly \@IEEEauthor...

work page 2019

[2] [2]

R. B. Jones, J. W. O'Leary, C.-J. H. Seger, M. D. Aagaard, and T. F. Melham, ``Practical formal verification in microprocessor design,'' IEEE Design & Test of Computers , vol. 18, no. 4, pp. 16--25, July/August 2001

work page 2001

[3] [3]

Mukherjee, S

R. Mukherjee, S. Joshi, A. Griesmayer, D. Kroening, and T. Melham, ``Equivalence checking of a floating-point unit against a high-level C model,'' in Formal Methods (FM), ser. LNCS, J. S. Fitzgerald, C. L. Heitmeyer, S. Gnesi, and A. Philippou, Eds., vol. 9995. 1em plus 0.5em minus 0.4em Springer, 2016, pp. 551--558

work page 2016

[4] [4]

Clarke, D

E. Clarke, D. Kroening, and F. Lerda, ``A tool for checking ANSI-C programs,'' in Tools and Algorithms for the Construction and Analysis of Systems, ser. LNCS, vol. 2988. 1em plus 0.5em minus 0.4em Springer, 2004, pp. 168--176

work page 2004

[5] [5]

B. Cook, K. Khazem, D. Kroening, S. Tasiran, M. Tautschnig, and M. R. Tuttle, ``Model checking boot code from AWS data centers,'' in Computer Aided Verification (CAV), ser. LNCS, H. Chockler and G. Weissenbacher, Eds., vol. 10982. 1em plus 0.5em minus 0.4em Springer, 2018, pp. 467--486. [Online]. Available: https://doi.org/10.1007/978-3-319-96142-2\_28

doi:10.1007/978-3-319-96142-2 2018

[6] [6]

Hauser, ``Berkeley SoftFloat ,'' (Accessed 22 Jan

J. Hauser, ``Berkeley SoftFloat ,'' (Accessed 22 Jan. 2019). [Online]. Available: http://www.jhauser.us/arithmetic/SoftFloat.html

work page 2019

[7] [7]

C.-J. H. Seger, R. B. Jones, J. W. O'Leary, T. Melham, M. D. Aagaard, C. Barrett, and D. Syme, ``An industrially effective environment for formal hardware verification,'' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 24, no. 9, pp. 1381--1405, September 2005

work page 2005

[8] [8]

O'Leary, R

J. O'Leary, R. Kaivola, and T. Melham, ``Relational STE and theorem proving for formal verification of industrial circuit designs,'' in Formal Methods in Computer-Aided Design (FMCAD), B. Jobstmann and S. Ray, Eds. 1em plus 0.5em minus 0.4em IEEE, 2013, pp. 97--104

work page 2013