angr / angr/cle

Regions.find_region_containing bisects on a key its list is not sorted by when regions overlap

Open
#742 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
485
Forks
135
Avg merge
2d 2h
Merged PRs (30d)
15

Description

THIS MESSAGE WAS GENERATED BY AN AUTOMATED PROCESS

`Regions` documents that its members do not overlap, and `find_region_containing` bisects on their end addresses on that basis. When two regions do overlap, the list is no longer sorted by the key being searched, and the lookup can return `None` or the wrong region depending on where the search lands and on the `_last_section` cache.

angr/cle#739 removed one cause of overlap — relocatable objects, where a section CLE deliberately does not load was still taking an address and landing on top of the section after it. But overlap also occurs in ordinary linked ELFs, because `.tbss` occupies no memory at run time and legitimately shares its address range with the section that follows. On angr/binaries master that is 17 of 299 ELF fixtures, so it is not unusual.

No sampled address is currently lost on those files: the bisection happens to land somewhere harmless given how the sections are ordered. That is luck rather than design, and it is the kind of thing that changes silently when a linker emits sections in a different order.

The question is what the invariant should be. Either `Regions` genuinely forbids overlap and something upstream has to guarantee it — which means deciding what `.tbss` should look like in the model — or the structure should tolerate overlap and `find_region_containing` should stop assuming a total order it does not have. Both are defensible; the current state, where the docstring claims one and the data provides the other, is the one that is not.

Reproducing needs nothing beyond the fixtures already in angr/binaries.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.