Meeting Notes - Githubissues

makerdao / mkr-mcd-spec

High level KSpecification for the MCD System by Runtime Verification and Maker Foundation

GNU General Public License v3.0

28 stars 9 forks source link

Meeting Notes #22

Open ehildenb opened 5 years ago

ehildenb commented 5 years ago

Unfortunately we didn't take meeting notes from the beginning, but hopefully this helps the project owners on the MKR side report progress.

ehildenb commented 4 years ago

Wednesday October 07, 2020

Was off last week to close on house in Illinois, getting back into the project slowly.
Have been working on gas expression simplifications, just today got it working for all the cases I've seen, but a handful of the generated proofs aren't passing with the simplified expressions. Need to examine what's being sent to z3. The updated gas expressions lead to a 20% or so performance improvement though in cases where they work, so I think ti's worth it. We run through about 85% of the entire proof-suite in 5.5 hours now.
Any updates on the use of the Firefly report? https://sandbox.fireflyblockchain.com/app/report.html?reportId=4a3e2109-300b-4640-be2d-6156ed561406. Anything we can do to speed this along a bit? Can try pointing at this branch Liq-2.0 and see what our coverage there is, if the unit tests are helpful for coverage.
Are working on supporting the more general bytecode submitted to the ERC20 tool (proxy bytecode in one case, constructor bytecode in another). This requires some generalizations to our tooling, but we'll let you know when to try another contract. If you have any bare ERC20s that you have the runtime bytecode for, we can try again (we're working on supporting constructor bytecode).

ehildenb commented 3 years ago

Wednesday October 14, 2020

Have finished working on the gas expression generation. Had a few last remaining bugs, but I'm happy with the new resulting gas formula, which are much smaller in general and resulted in somewhere between a 20-25% speedup in the existing proofs. It's in a python file in the k-dss repo, but this should be moved to the KLab repo instead.
Began work on checking that sub-proofs are used in some of the simpler compound proofs, and profiling whether they are actually helpful or not (vs re-running the entire proof again without the sub-proofs). No conclusive results yet though. I'm going to try and set up the build system so that when a proof has sub-proofs, it fails if it doesn't use them all (so either too many sub-proofs were declared as dependencies, or the generated proof obligations don't work to apply them). I've picked a simple dependency proof to start (Vat_flux-diff_pass_rough), and it appears we are not using sub-lemmas. So I'm trying to figure out the best way to add log information about why the lemmas are not being applied.
Need any help with firefly report? How is that going?

ehildenb commented 3 years ago

Wednesday October 21, 2020

Figured out why sub-lemmas are not being applied. Was because the matcher for sub-lemmas in java backeend will not apply to function symbols, and the new infinite gas abstraction #gas is a functional term. Just had to modify the generated sublemmas to add matching(infGas) to tell it "go ahead and match on this particular function symbol".
Build system has been modified to check that sub-lemmas are applied on every proof that has them. This did not result in any more proofs failing, and a few more are passing now, so that's good news.
Found one bug(?) in the way that KLab extracts gas expressions. Haven't narrowed down exactly what the bug is, but AFAICT, it does not always select the excactly correct side-condition to put in the #if_#then_#else_#fi. I'm working through this one currentnly. Also AFAICT, it only actually ends up affecting 1 proof that I'm currently running. Just not sure if it's quietly affecting other proofs, or will affect some of the bigger proofs.
With application of sub-lemmas, smaller proofs do not seem to benefit appreciably (mabye a couple %), but the overall test-suite runs about 10% faster, so it's a win overall.
Next step is to move on to really big failing proofs.

ehildenb commented 3 years ago

Wednesday October 28, 2020

Found that many of the sub-proofs that are not applying are due to the addui, mului, etc... lemmas. These have trouble applying because they have a function symbol on top of the wordStack (that is, they have things like chop(ABI_y) on the lhs of the sub-lemma), which the java-backend won't try to match/unify with whatever exists there (usually a concrete or symbolic number). After trying several techniques to get these to apply, I'm disabling these lemmas for now, because they're small and don't have an appreciable impact on performance.
Have begun working on automating the transformation from a dapp project to a truffle project. Now we're making sure that the steps needed to do so can reliably be done by hand, and then we will begin automating parts of the steps at a time. The basic approach is outlined here:

- add package.json - npm init -yf
- add truffle-config.js
- move test out of src/
For each test
- fix test imports
    - import "ds-test/test.sol" => import "../lib/ds-test/src/test.sol"
    - import "../dai.sol"            => import "../src/dai.sol"
- replace dapp asserts with truffle ones
    - import "truffle/Assert.sol"
    - assertEq    => Assert.equal
    - assertTrue => Assert.isTrue
    - I did it with a regex: s/assertEqual(\(.*\))/Assert.equal(\1, "");
- remove everything related to Hevm
    - Hevm hevm declaration in test contract
    - hevm.warp calls (https://github.com/dapphub/dapptools/tree/master/src/hevm#cheat-codes) (edited)

ehildenb commented 3 years ago

Wednesday December 9, 2020

Proofs

One draft PR with progress on signed division lemma: https://github.com/kframework/evm-semantics/pull/946
A PR with updates to the infinite gas model which work better with MKR proofs (and should behave more soundly, not sure we were running afoul of the problems with it, but better safe than sorry): https://github.com/kframework/evm-semantics/pull/945
Current status: 918/1011 proofs are generated (91%), and 834 of them are passing (91%). Generating 56 new proofs than earlier, and passing 63 more than before. All with 20minute timeout per proof.

Firefly

Have been working on updating the display to show coverage using the new format, work is in progress, not ready for review yet.
Andrei has worked on making the tool able to correctly line up bytecode from the Firefly client to the bytecode generated by solc output. Dropping the last 106 bytes helped, but turns out that Truffle is "batch-deploying" contracts, which means the bytecode we see deployed is actually a big smashing together of the test contract with helper contracts and some shim code. So our sub-string matching is being improved to identify this situation.

ehildenb commented 3 years ago

Wednesday December 16, 2020

Proofs

Merged: kframework/evm-semantics#945
Updated lemmas for word-pack: kframework/evm-semantics#948 (and adds functional test as smoke test for lemmas)
Simple lemma for gas expressions on vat-subui: kframework/evm-semantics#949
Lemmas for simplifying gas expressions more (results in much smaller gas expressions for proofs with CALL, and in many of those proofs up to 10% performance improvement): kframework/evm-semantics#952
Updates to many of the proofs write-order. The generation process (abstract-pre/concrete-post storage model) is now sensitive to the order that updates to the storage are specified in, so several specs had to be updated to reflect this. I suspect I will find many more, just updating them as I find them. See example here: https://github.com/makerdao/k-dss/commit/a193b633c72841ed47dbd23a2b87be9c8a5d3030

With 5 min timeout, 12 in parallel at a time (4 hrs):

tried:   813 - 0.8041543026706232
passing: 711 - 0.8745387453874539
timeout: 95 - 0.11685116851168512

Re-running with 20 min timeout, 8 in parallel at a time (4 hrs):

tried:   913 - 0.9030662710187932
passing: 840 - 0.9200438116100766
timeout: 52 - 0.056955093099671415

Re-running with 120 min timeout, 6 in parallel at a time (8 hrs):

tried:   936 - 0.9258160237388724
passing: 884 - 0.9444444444444444
timeout: 5 - 0.005341880341880342

ehildenb commented 3 years ago

Wedesday Jan 6, 2021

Proofs

Merged: vat-subui lemmas: https://github.com/kframework/evm-semantics/pull/949
Merged: WordPack abstractions for flopper: https://github.com/kframework/evm-semantics/pull/948
In Review: Better infinite gas reasoning: https://github.com/kframework/evm-semantics/pull/952
PRs to be opened: vow-cage-surplus-pass-rough, vow-cage-deficit-pass-rough, vat-frob-diff-zero-dart-pass, vat-fork-diff-pass-rough, flopper-dent-guy-diff-tic-not-0-pass, flapper-tend-guy-diff-pass-rough

Current Status (timeout is 120min, runtime is ~13hrs):

tried:   964 - 0.9535113748763601
passing: 923 - 0.9574688796680498
timeout: 6 - 0.006224066390041493

Remaining issues: (i) _/sWord_ lemma that I cannot prove sound yet, so I can't open a PR (majority of failing proofs are due to this. (ii) rpow proofs.

Full run of all the proofs:

[test "deps"]
    step = rm -rf deps out
    step = git submodule update --init --recursive
    step = make include.mak
    step = make deps -j3

[test "5min"]
    step = rm -rf log-prove-5
    step = echo % Timeout = 5              >> log-prove
    step = echo                            >> log-prove
    step = make prove -j12 -k KLAB='profile log-prove-5   timeout 300  klab' CHECK_SUB_LEMMAS=true || true
    step = cat log-prove-5   | sort -h -k2 >> log-prove
    step = echo                            >> log-prove

[test "120min"]
    step = rm -rf log-prove-120
    step = echo % Timeout = 120            >> log-prove
    step = echo                            >> log-prove
    step = make prove -j8  -k KLAB='profile log-prove-120 timeout 7200 klab' CHECK_SUB_LEMMAS=true || true
    step = cat log-prove-120 | sort -h -k2 >> log-prove
    step = echo                            >> log-prove

Firefly

Got the changes to the coverage processing merged (https://github.com/runtimeverification/firefly/pull/1134)
Updated the pre-processing of the dapp repository to replace the ds-test lib with truffle/Assert.sol lib. (https://github.com/runtimeverification/firefly/pull/1151)
Began working on the HEVM module implementation

ehildenb commented 3 years ago

Wednesday January 13, 2021

Proofs

Merged: https://github.com/kframework/evm-semantics/pull/952 (improvements to infinite gas reasoning, Denis found some potentially looping rules, so I fixed that).
Merged: https://github.com/kframework/evm-semantics/pull/954 (Several more regression proofs, lemmas to make them pass, improvements to WordPack abstraction, adding #rmul abstraction).
Merged: https://github.com/kframework/evm-semantics/pull/957 (Update proofs in regression suite to be the newest versions that KLab produces, since KLab generation changed in the meantime).
Opened: https://github.com/kframework/evm-semantics/pull/958/files (Remaining lemmas I have found except for the signed word lemma that I cannot prove yet).
I have found a simpler form of the signed word lemma that I believe I will be able to prove using Z3, have not attempted yet.
Status (still running):
```
tried:   955 - 0.9446092977250248
passing: 919 - 0.962303664921466
timeout: 6 - 0.0062827225130890054
```
The regression in the number of tried proofs is because some of the changes above caused gas expressions to change, which caused some passing quick-running proofs to fail. This shouldn't be hard to fix, haven't had time to investigate yet. There are 12 new proofs running, and 23 new proofs passing, but the quick-running proof that is now failing caused others to not be generated or run.

Firefly

drafted an hevm module in k for processing the warp function but it doesn't match any hevm call yet https://github.com/runtimeverification/firefly/pull/1151/files
looked for the warp function signature( 0xe5d6bf02 ) inside the compiled artifacts and the transactions sent to the firefly client but I didn't find any matches.

ehildenb commented 3 years ago

Wednesday January 20, 2020

Proofs

Slow week, helped move my sister across the country.
Merged: https://github.com/kframework/evm-semantics/pull/958
Updates to gas generation to fix issue where changes two weeks ago made some proofs fail (they are now passing): https://github.com/ehildenb/k-dss/blob/pr/write-gas.py#L146

Current status:

tried:   973 - 0.9624134520276953
passing: 940 - 0.9660842754367934
timeout: 3 - 0.003083247687564234

Firefly

Andrei had no time this week, personal emergency came up.