c4milo / c4milo/chapulin

Give the reach gate a per-harness budget, and shrink the formula that forces it

Open
#163 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
2
Forks
0
Avg merge
1h 20m
Merged PRs (30d)
74

Description

`proof/coverage.py` gives every cover run the same `REACH_BUDGET_S`. https://github.com/c4milo/chapulin/pull/162 measured that number and raised it from 900 s to 1800 s, but the measurement also showed that one number cannot serve the roster, and that the budget is standing in for a problem it cannot fix.

## One budget, two populations

Measured under the pinned cbmc 6.11.0:

| harness | converges in | on the runner |
| --- | --- | --- |
| `hello_build` | 185 s (dev, six runs 175-195) | 278 s, 281 s, and once past 900 s |
| `pem` | 1654 s (dev, 8.1 GB peak) | about 2500 s, extrapolated |

The dev machine runs `hello_build`'s cover 1.51x faster than the runner, so `pem` needs roughly 2500 runner-seconds. Every budget is therefore wrong for someone:

- 900 s starved `pem` and `pem_ecdsa`. They timed out in all five nightly runs on record and produced nothing.
- 1800 s, what https://github.com/c4milo/chapulin/pull/162 lands, almost certainly still starves them, and now costs 1800 s each rather than 900.
- 2700 s would let them converge and earn floors, but it also becomes what every *other* harness may burn before the gate calls it dead.

`proof/reach-floors.txt` already carries per-harness data. A `pem 2700` budget line there, read the way the floors are, would let a slow harness converge without making every fast one expensive to fail.

## The budget is standing in for a formula that is too big

`hello_build`'s cover run peaks at **12.2 GB on a 16 GB runner**. That is why its wall time moved from 281 s to over 900 s on a run where the other 19 converging harnesses each finished within 17% of their own fastest time: at that margin the time follows the memory free during its own window, not the solver.

No budget fixes that. It widens the window before the same flake returns. The durable options are to split the formula the way `docs/proofs.md` describes for other harnesses, or to run `proof-reach` on a larger runner. Until one of them happens, the 1800 s budget is a delay, not a resolution, and the comment above `REACH_BUDGET_S` says so.

## Done when

- A harness can carry its own budget, recorded beside its floor and measured the way the floors are.
- `pem` and `pem_ecdsa` either converge and carry floors, or are listed as not gated with the measurement that says why.
- `hello_build`'s peak memory is under a stated fraction of the runner, or the gate runs where 12.2 GB is not three quarters of the machine.

Found while landing https://github.com/c4milo/chapulin/issues/160.

Contributor guide

Open the contributing guide

Research direction

Start in proof/coverage.py and compare its REACH_BUDGET_S handling with the per-harness data in proof/reach-floors.txt. Read docs/proofs.md for the formula-splitting context, then verify the listed harness measurements and runner memory against the three Done when conditions.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, python
Domain
ci-cd, performance, testing
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.