Skip to content

Make malloc-ed variables non-unique#345

Merged
sim642 merged 10 commits intomasterfrom
issue-316
Sep 14, 2021
Merged

Make malloc-ed variables non-unique#345
sim642 merged 10 commits intomasterfrom
issue-316

Conversation

@sim642
Copy link
Copy Markdown
Member

@sim642 sim642 commented Sep 8, 2021

Closes #316.

This implements the solution proposed in #310 (comment). By answering IsMultiple query for malloc-ed variables with false, the address set equality check introduced in #310 automatically considers this non-uniqueness information.

This should be sound and good enough until we design a more precise malloc uniqueness analysis (#186).

@sim642
Copy link
Copy Markdown
Member Author

sim642 commented Sep 10, 2021

Initially this PR failed marshaling regression tests for macOS in the unlocked job.

This unusual behavior seemed to be due to the heap_vars hashtable used by mallocWrapper to record which varinfos correspond to mallocs. The problem is that such global (within the module) hashtables are not marshaled and unmarshaled.
Therefore after unmarshaling that hashtable is initialized to be empty and everything is considered a program variable.

The possible reason why it still worked on Ubuntu is that depending on the order of keys in the solution hashtables, verification reevaluates the transfer functions in non-deterministic order. If it happens to evaluate the malloc edge before whereever the non-uniqueness of this variable is used, then that would have repopulated the mallocWrapper hashtable and appear to still work.
Something about the macOS environment and the hashtable implementation caused it to differ from Ubuntu. Clearly this non-determinism is bad.

The solution for now was to use the mallocWrapper global invariant, which also has varinfo keys with a boolean lattice, in place of this hashtable. Then it's properly marshaled and unmarshaled as part of the solution.
This required undoing part of #214 to be able to do the corresponding sideg during a query which is used to ask for a malloc variable. The original part_access stuff still works around it, so the grouping that was fixed there still works, but now the dangerous ungrouped sideg (only used here) is possible again.

The other heap_hash table in mallocWrapper is safe for extremely fragile reasons: Goblintutil.create_var is deterministic w.r.t the variable name (here including the location), so it gets identically reconstructed. Moreover, this cannot be moved into the analysis global invariant because it uses location keys.

This exposes a much deeper marshaling problem that's not specific to here. For example, even the RETURN varinfo created by base analysis is similarly imperatively created and globally stored in the base module. It is also not marshaled and the name-determinism of create_var just hides this issue by allocating a new varinfo, which happens to behave well with the unmarshaled solution containing RETURN since they have the same vid.

So any kind of state in the analysis modules is problematic for marshaling and should maybe be avoided or replaced with a mechanism that allows it to also be marshaled from all analyses.
This also affects the amazing RichVarinfo, which currently doesn't expose the internal hashtable at all, but would have to for marshaling (assuming we want to marshal closures), which largely defeats the point of RichVarinfo.

@sim642 sim642 merged commit c0b94c1 into master Sep 14, 2021
@sim642 sim642 deleted the issue-316 branch September 14, 2021 17:45
sim642 added a commit that referenced this pull request Sep 20, 2021
…bles

This was revealed by #345.
Simply get-ing/eval-ing global constraint variables added bottom to rho.
This unnecessarily increases rho with default values.

An an unintended consequence, the bottom values for all dead local variables also never get stored.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Unsoundness for comparing pointers to malloced values

2 participants