https://github.com/EasyCrypt/easycrypt
Revision a9748f75a4ec83fcbcd5b907e03996e6a2ada7e2 authored by Adrien Koutsos on 28 March 2022, 09:19:38 UTC, committed by Pierre-Yves Strub on 28 March 2022, 10:45:44 UTC
** Breaking change: - to be consistent with oracle calls restrictions, negative memory restrictions are now set using a minus symbol (e.g. `(M <: T {-H})` instead of `(M <: T {H})`). - use `pragma +old_mem_restr` to retrieve old behaviour on memory restrictions ** Additions: - added a new hoare logic for cost, using predicates of the form `choare [H.f: pre ==> post] time [c]`, meaning: from any initial memory satisfying `pre`, the final memory obtained after the execution of `H.f` satisfies `post`, in time at most `c` - in choare predicates, the cost `c` is a cost-vector, comprising: + a concrete cost of type `xint`, where `xint` is a algebraic data-type with two constructors, `N of int` (for bounded running times) and `Inf` (for potentially unbounded running times). + a list of abstract procedures together with an integer indicated the number of times they can be called (e.g. `ROM.o : 42`). - complexity restrictions can be attached to module types procedures, restricting their instantiations. - added a new predicate, `cost`, to establish the cost of evaluating an expression (while `choare` upper-bound the cost of a statement). - (small) examples showing how to use the cost hoare logic can be found in the sub-directory `examples/cost/` - more advanced examples, using a new UC framework in EasyCrypt, can be found in `examples/UC/composition_cost.ec` `examples/UC/dh_enc_cost.ec`
1 parent b13fb54
Tip revision: a9748f75a4ec83fcbcd5b907e03996e6a2ada7e2 authored by Adrien Koutsos on 28 March 2022, 09:19:38 UTC
New logic to upper-bound the worst-case complexity of programs
New logic to upper-bound the worst-case complexity of programs
Tip revision: a9748f7
File | Mode | Size |
---|---|---|
.github | ||
config | ||
examples | ||
lint | ||
scripts | ||
src | ||
theories | ||
.dir-locals.el | -rw-r--r-- | 285 bytes |
.gitignore | -rw-r--r-- | 118 bytes |
COPYRIGHT | -rw-r--r-- | 581 bytes |
COPYRIGHT.yaml | -rw-r--r-- | 894 bytes |
Makefile | -rw-r--r-- | 1.3 KB |
README.md | -rw-r--r-- | 7.9 KB |
default.nix | -rw-r--r-- | 494 bytes |
dune | -rw-r--r-- | 116 bytes |
dune-project | -rw-r--r-- | 359 bytes |
easycrypt.opam | -rw-r--r-- | 1.2 KB |
easycrypt.opam.template | -rw-r--r-- | 915 bytes |
easycrypt.png | -rw-r--r-- | 182.6 KB |
Computing file changes ...