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.

Sign up for GitHub

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

Jump to bottom

Use formal modeling/verification to test or prove the correctness of core algorithms #378

Open
joshlf opened this issue Sep 13, 2023 · 1 comment
Open

Use formal modeling/verification to test or prove the correctness of core algorithms #378

joshlf opened this issue Sep 13, 2023 · 1 comment

Comments

@joshlf
Copy link
Member

joshlf commented Sep 13, 2023 •
edited
Loading

While zerocopy is conceptually complex, the amount of code that executes in order to perform a particular operation is often very small. This makes it a perfect target for formal modeling and verification techniques.

This issue tracks testing or proving the correctness of our core algorithms using these tools.

Currently, we use formal modeling or verification in the following places (TODO: better way to keep this list up-to-date automatically?):
@joshlf joshlf mentioned this issue Sep 3, 2023
Open
15 tasks
@jswrenn jswrenn mentioned this issue Sep 14, 2023
Draft
joshlf added a commit that referenced this issue Sep 18, 2023
@joshlf
Add round_down_to_next_multiple_of_alignment
ca0f8a1 
This function implements the operation more efficiently using bitmasking
instead of division and multiplication. While LLVM is probably smart
enough in practice to produce this sort of code, Kani (#378) has trouble
with multiplication, and so this code is hopefully more Kani-friendly.

Closes #390
@joshlf joshlf mentioned this issue Sep 18, 2023
Merged
joshlf added a commit that referenced this issue Sep 19, 2023
@joshlf
Add round_down_to_next_multiple_of_alignment
f9b0829 
This function implements the operation more efficiently using bitmasking
instead of division and multiplication. While LLVM is probably smart
enough in practice to produce this sort of code, Kani (#378) has trouble
with multiplication, and so this code is hopefully more Kani-friendly.

Closes #390
joshlf added a commit that referenced this issue Sep 19, 2023
@joshlf
Add round_down_to_next_multiple_of_alignment
b1d541f 
This function implements the operation more efficiently using bitmasking
instead of division and multiplication. While LLVM is probably smart
enough in practice to produce this sort of code, Kani (#378) has trouble
with multiplication, and so this code is hopefully more Kani-friendly.

Closes #390
joshlf added a commit that referenced this issue Sep 19, 2023
@joshlf
Add round_down_to_next_multiple_of_alignment
fd82f80 
This function implements the operation more efficiently using bitmasking
instead of division and multiplication. While LLVM is probably smart
enough in practice to produce this sort of code, Kani (#378) has trouble
with multiplication, and so this code is hopefully more Kani-friendly.

Closes #390
joshlf added a commit that referenced this issue Sep 19, 2023
@joshlf
Add round_down_to_next_multiple_of_alignment (#393)
da4c3cc 
This function implements the operation more efficiently using bitmasking
instead of division and multiplication. While LLVM is probably smart
enough in practice to produce this sort of code, Kani (#378) has trouble
with multiplication, and so this code is hopefully more Kani-friendly.

Closes #390
@jswrenn
Copy link
Collaborator

jswrenn commented Sep 19, 2023

I left a comment about our need for alternative targets here: model-checking/kani#2402 (comment)

@joshlf joshlf changed the title Use formal modeling to test or prove the correctness of core algorithms Use formal modeling/verification to test or prove the correctness of core algorithms Sep 20, 2023
@joshlf joshlf mentioned this issue Sep 20, 2023
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@joshlf @jswrenn