Why does bounded model checking of C blow up on loops, and how do function contracts fix it?
Title: Function Contracts for Bounded Model Checking of C Programs
URL:
❓ Why is BMC so heavy?
It unrolls loops N times and inlines every call. A function with an N-iteration loop called from K sites costs roughly N×K.
💡 What changes with contracts?
The body is verified once against its contract, and each call is replaced by a stub derived from that contract. No unrolling is needed, so cost no longer scales with call count.
❓ What is new here?
The authors add contract support to ESBMC. The assigns clause is checked observationally: snapshot the locations that must not change on entry, compare them at exit. Formula size depends on the number of globals, not the number of writes, unlike CBMC. The algebraic core is machine-checked in Lean 4.
❓ How well does it work?
・N=20,K=10: direct verification times out past 120 s, modular finishes in 12.5 s
・N=10,K=10: 42.0 s down to 1.8 s (23.3x)
・With 500 writes, ESBMC emits 5 VCCs vs. 521 for CBMC
・At the FIPS-203 ML-KEM size, monolithic runs exceed 10 minutes in both tools, but modular completes
Note that at K=1 it is slower.
#
FormalVerification# #
ModelChecking#