Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve crucible_jvm_verify performance #399

Closed
atomb opened this issue Apr 2, 2019 · 5 comments
Closed

Improve crucible_jvm_verify performance #399

atomb opened this issue Apr 2, 2019 · 5 comments
Assignees
Labels
performance Issues that involve or include performance problems subsystem: crucible-jvm Issues related to Java verification with crucible-jvm

Comments

@atomb
Copy link
Contributor

atomb commented Apr 2, 2019

Ensure that the entire ECDSA proof can complete successfully, and in less than 2x the time taken by java_verify.

@atomb atomb added this to the 0.3 milestone Apr 2, 2019
@brianhuffman
Copy link
Contributor

brianhuffman commented Apr 11, 2019

Currently the crucible ECDSA proof is about 15x slower than the java_verify version, so we have a lot of work to do. It appears that there are slowdowns in both simulation and proving.

@brianhuffman
Copy link
Contributor

Even when using crucible_jvm_unsafe_assume_spec to skip every subproof, the script takes more than 30 seconds to run; some subproofs take up to 1.5 seconds. (To be clear, this only involves processing the setup block; it does no symbolic simulation or proof.)

I believe the slowdown is due to calling the Cryptol parser and type checker so many times to process terms in Cryptol quotes {{ }}. This is due to the fact that we don't yet have any points_to command that can do a whole array at once, so we have to do things (rather expensively, it turns out) like this:

let jvm_array24_is ref x =
  do {
    for [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23]
      (\i -> jvm_elem_is ref i (jvm_term {{ x@(`i:[8]) }}));
    return ();
  };

I wonder if there might be some computation that is repeated for every set of cryptol quotes, which we might be able to cache and re-use.

@atomb atomb added the performance Issues that involve or include performance problems label Apr 26, 2019
@atomb
Copy link
Contributor Author

atomb commented May 28, 2019

We've made a bunch of improvements which should be sufficient for 0.3. I'm going to leave this open to track further improvements, though.

@atomb atomb modified the milestones: 0.3, 1.0 May 28, 2019
@brianhuffman brianhuffman added the subsystem: crucible-jvm Issues related to Java verification with crucible-jvm label Jun 6, 2019
@atomb atomb modified the milestones: 1.0, 0.4 Oct 1, 2019
@atomb atomb removed this from the 0.4 milestone Oct 21, 2019
@atomb atomb added this to the 1.0 milestone Nov 8, 2019
@atomb atomb changed the title Test crucible_jvm_verify more thoroughly Improve crucible_jvm_verify performance Nov 8, 2019
@atomb atomb modified the milestones: 0.5, 0.6 Apr 3, 2020
@atomb atomb modified the milestones: 0.6, 0.7 Aug 11, 2020
@atomb atomb removed this from the 0.7 milestone Oct 16, 2020
@brianhuffman
Copy link
Contributor

In a branch, the ecdsa-crucible.saw runtime is down to about 5 minutes, compared to 3 for ecdsa.saw. So we are already within the 2x performance target. I'll close this ticket once the relevant changes are merged to master.

@brianhuffman
Copy link
Contributor

As of #932, ecdsa-crucible.saw is part of the regression test suite, and runs suitably fast.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
performance Issues that involve or include performance problems subsystem: crucible-jvm Issues related to Java verification with crucible-jvm
Projects
None yet
Development

No branches or pull requests

2 participants