Skip to content

Conversation

@sgpthomas
Copy link
Contributor

This PR introduces the trait BoundedArbitrary which allows for creation of symbolic values for types up to some bound. This is useful for doing bounded proofs on types like strings and vecs. I wrote a more detailed overview of what this PR provides as a new section in the book.

The implementation of BoundedArbitrary for the container types that I provide are pretty basic and experimental at the moment. Any pointers here would be useful, and we will probably need to iterate on their implementations based on actual performance testing.

I added a test case that should fail verification using the cover! macro, however, I'm not sure that I used this correctly. Let me know if I should make this an expect test, or something else.

I slightly restructured how we deal with the the std/core usage in kani_core::kani_lib. Previously we passed in either std or core to kani_core::generate_arbitrary and generate_arbitrary renamed the import with use $core as core_path. However, I couldn't use that same strategy for kani_core::generate_bounded_arbitrary because the import names would clash. So I lifted the use $core as core_path out of the kani_core::generate_* macros.

By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 and MIT licenses.

@sgpthomas sgpthomas requested a review from a team as a code owner April 7, 2025 22:27
@sgpthomas sgpthomas changed the title introduce BoundedArbitrary trait and macro for bounded proofs Introduce BoundedArbitrary trait and macro for bounded proofs Apr 7, 2025
@github-actions github-actions bot added the Z-EndToEndBenchCI Tag a PR to run benchmark CI label Apr 7, 2025
@sgpthomas sgpthomas force-pushed the bounded_arbitrary branch from 8d08836 to 99ef1cf Compare April 7, 2025 23:39
@carolynzech carolynzech self-assigned this Apr 8, 2025
@sgpthomas sgpthomas force-pushed the bounded_arbitrary branch from 99ef1cf to 061abd7 Compare April 8, 2025 19:29
Copy link
Contributor

@zhassan-aws zhassan-aws left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

A few comments on the tests.

@zhassan-aws
Copy link
Contributor

Copy link
Contributor

@zhassan-aws zhassan-aws left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Some comments on the documentation

Copy link
Contributor

@carolynzech carolynzech left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can you write tests for Option, Result, HashMap, etc. as well?

Copy link
Contributor

@zhassan-aws zhassan-aws left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Another round of comments

@sgpthomas sgpthomas force-pushed the bounded_arbitrary branch 4 times, most recently from b6fd641 to 0684144 Compare April 14, 2025 18:01
Copy link
Contributor

@zhassan-aws zhassan-aws left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks great! Mostly minor comments. Please make sure to add a description to all the tests.

Copy link
Contributor

@zhassan-aws zhassan-aws left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Copy link
Contributor

@zhassan-aws zhassan-aws left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks!

@sgpthomas sgpthomas enabled auto-merge April 22, 2025 22:41
@sgpthomas sgpthomas added this pull request to the merge queue Apr 22, 2025
Merged via the queue into model-checking:main with commit 9de733a Apr 23, 2025
25 of 26 checks passed
@sgpthomas sgpthomas deleted the bounded_arbitrary branch April 23, 2025 00:30
zhassan-aws added a commit that referenced this pull request Apr 23, 2025
This PR introduces the trait `BoundedArbitrary` which allows for
creation of symbolic values for types up to some bound. This is useful
for doing bounded proofs on types like strings and vecs. I wrote a more
detailed overview of what this PR provides as a new section in the book.

The implementation of BoundedArbitrary for the container types that I
provide are pretty basic and experimental at the moment. Any pointers
here would be useful, and we will probably need to iterate on their
implementations based on actual performance testing.

I added a test case that should fail verification using the `cover!`
macro, however, I'm not sure that I used this correctly. Let me know if
I should make this an expect test, or something else.

I slightly restructured how we deal with the the `std/core` usage in
`kani_core::kani_lib`. Previously we passed in either `std` or `core` to
`kani_core::generate_arbitrary` and `generate_arbitrary` renamed the
import with `use $core as core_path`. However, I couldn't use that same
strategy for `kani_core::generate_bounded_arbitrary` because the import
names would clash. So I lifted the `use $core as core_path` out of the
`kani_core::generate_*` macros.

By submitting this pull request, I confirm that my contribution is made
under the terms of the Apache 2.0 and MIT licenses.

---------

Co-authored-by: Sammy Thomas <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

Z-EndToEndBenchCI Tag a PR to run benchmark CI

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants