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

Add a MemoryModelContents option for not initializing writable global data #372

Open
langston-barrett opened this issue Feb 23, 2024 · 1 comment
Labels
symbolic-execution Issues relating to macaw-symbolic and symbolic execution

Comments

@langston-barrett
Copy link
Contributor

The MemoryModelContents datatype determines how writable global data is initialized.

data MemoryModelContents = SymbolicMutable

The Haddock on this type notes that to support sound verification of individual functions in isolation, such data must be initialized as fully symbolic, i.e., an overapproximation of the possible runtime values. However, none of the available options enable sound bug-finding, which would require that globals are initialized to an underapproximation of the possible runtime values. This is infeasible in practice, as the possible values of the global data upon the entry to the target function are unknowable. The next best thing would be to provide an option to leave such data uninitialized, leading any loads from it to fail, which would prevent unsound results (for bug-finding).

@RyanGlScott
Copy link
Contributor

I can conceptualize how this third option would work in the lazy memory model. The lazy memory model carries around an IntervalMap of which addresses have been initialized, and it would be possible to detect a read from an uninitialized address and throw an error.

It's less obvious to me how to implement this in the eager memory model. The eager memory model backs the global address space with a single SMT array, and reads from an SMT array always succeed. Perhaps we'd need to dedicate an extra bit of space to track whether each address's contents are initialized or not?

@RyanGlScott RyanGlScott added the symbolic-execution Issues relating to macaw-symbolic and symbolic execution label Jul 3, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
symbolic-execution Issues relating to macaw-symbolic and symbolic execution
Projects
None yet
Development

No branches or pull requests

2 participants