Loader: ELF non-zero based PIC binaries support

[symflood]

It is may be not a real issue but a lack of understanding.

I am trying to load some 32bit ARM binary with dependencies resolution enabled

angr.cle.Loader(..., custom_ld_path=["./lib/"])

the result is

INFO    | 2017-05-17 17:04:36,806 | cle.loader | Rebasing ##cle_tls## at 0x192000000
Traceback (most recent call last):
...
  File "/home/user/Desktop/repos/angr-dev/cle/cle/tls/elf_tls.py", line 63, in drop_int
    drop(struct.pack(self.arch.struct_fmt(), num), offset)
error: argument out of range for 4-bytes integer format

The virtual address 0x1 9200 0000 is not of 32 bit length.

The problem, as I understood, arise from method Loader._get_safe_rebase_addr

    def _get_safe_rebase_addr(self):
        granularity = self._rebase_granularity
        return self.max_addr() + (granularity - self.max_addr() % granularity)

and located inside Loader.max_addr→backends.get_max_addr

    def get_max_addr(self):

        out = self.segments.max_addr

        if out is None:
            out = self.sections.max_addr

        if out is None:
            return self.rebase_addr
        else:
            return out + self.rebase_addr

The line I am interested in is the last one

...
            return out + self.rebase_addr

it should return new rebased image base address (the one inside Clemory map), but in my case it instead returns
(old image base + maximum rva from ELF objects) out + self.rebase_addr (new image base)

Does this logic correct? Maybe out should be normalized (- old image base)...

Please correct me if I am wrong.

[rhelmot]

You are wrong about the correct behavior of get_max_addr() - it is supposed to return a rebased address, not an unrebased address. Unless it's super inconvenient, every CLE API should work with rebased addresses.

However, there is definitely a bug. I think the issue is just that our rebase granularity is too large. Can you try loading the binary with rebase_granularity=0x10000 and see what happens?

[symflood]

Can you try loading the binary with rebase_granularity=0x10000 and see what happens?

Thought about granularity and tried it already with 0x1000/0x10000/0x100000. It doesn't help too much as each new base (for every shared object) is rapidly increasing anyway.

it is supposed to return a rebased address, not an unrebased address.

In my case self.segments.max_addr is always based on original base (from ELF Object) and the result of out + self.rebase_addr looks like a VA with 2 image bases applied (original base from ELF embedded in out and a new base self.rebase_addr).

As I understand self.segments.max_addr returns a VA (from ELF Object) and not an offset (or RVA). Also self.rebase_addr is also a VA of new image base. Where am I wrong?

[rhelmot]

Are your shared libraries not position-independent? I'm having a hard time understanding the situation you're describing. Can you send me the binaries to reproduce this?

[symflood]

Can you send me the binaries to reproduce this?

Unfortunately, I can't because of NDA.

Are your shared libraries not position-independent?

No. They are all PICs except the main binary as usual.

I found that the problem has occurred because CLE can't correctly load prelinked binaries.
All the binaries have some ImageBase. And as I see CLE does support this, at least it does it for PE and basic Backend. I am talking about self.requested_base
For example, this code is from PE backend

self.requested_base = self._pe.OPTIONAL_HEADER.ImageBase

and this one is from the basic Backend

class Backend(object):
    """
    Main base class for CLE binary objects.
...
    :ivar requested_base:   The base address this object requests to be loaded at, or None
...
        self.requested_base = None

and from loader

    def add_object(self, obj, base_addr=None):
...
        elif obj.requested_base is not None and self._is_range_free(obj.requested_base + obj_offset, obj_size):
            base_addr = obj.requested_base

so generally it supports the concept of image base, but the usage I think is wrong.
This leads to such problems:

1. Loader can't load prelinked binaries.
2. Loader incorrectly maps non-PIC binaries. It always maps non-PIC main binary not at requested_base, but at 0x0 address and have a size of Image Base + Image Size, which doesn't seem to be correct. In result, a large part of a memory is occupied by any non-PIC binary and nothing can't be mapped below this region (non-PIC and prelinked binaries).
3. Rebasing is incorrect because to rebase a VA, it needs to be normalized to the 0x0 base (substact an old base, I mean even if it 0x0 by default) and then rebased to the new one (add a new base).

Is that correct?

[rhelmot]

I think your diagnosis is correct, and the solution you propose is also good. An easy fix might be to just use min_addr as the other base.

On the other hand, I've never encountered a "prelinked" binary before. Can you compile one for me or find me an example not covered by your NDA?

[symflood]

An easy fix might be to just use min_addr as the other base.

I've tried such fast fix at first, but the issue touches several more files and many regression tests failed as a result.
Anyway I'll try to PR a fix for review.

Is it possible that an assertion is wrong in this case

index bf60598..09c782e 100644
--- a/tests/test_overlap.py
+++ b/tests/test_overlap.py
@@ -14,7 +14,7 @@ class MockBackend(cle.backends.Backend):
 def test_overlap():
     filename = os.path.join(os.path.dirname(os.path.realpath(__file__)), '../../binaries/tests/i386/manysum')
     ld = cle.Loader(filename, auto_load_libs=False)
-    nose.tools.assert_equal(ld.main_bin.rebase_addr, 0)
+    nose.tools.assert_equal(ld.main_bin.rebase_addr, 0x8048000)
     nose.tools.assert_equal(ld.main_bin.get_min_addr(), 0x8048000)
 
     obj1 = MockBackend(0x8047000, 0x2000, custom_arch=ld.main_bin.arch)

Any image is actually rebasing each time it is loading:

    def add_object(self, obj, base_addr=None):
...
        l.info("Rebasing %s at %#x", obj.binary, base_addr)

The new base should stay the same (ld.main_bin.rebase_addr should equal to the same address as requested). The binary cannot be rebased to any address, except an initial one, because it doesn't have any relocations or PIC supply code to support such operation. Is that correct?

Can you compile one for me or find me an example not covered by your NDA?

I'll attach them here a bit later.

[symflood]

It looks like angr project itself also suffers from this issue.
Maybe I do not understand the semantics behind operations like addr + self.rebase_addr.
Is it true that addr generally is a virtual address inside a virtual space (except cases where addr represent an offset, to switch from rva to virtual address)?
Is it possible that this behavior is due to an incorrect assumption that default base (requested base) is always 0x0 for relocatable images?
I have passed all the tests inside cle, but have a lot of errors with angr tests. It also uses an operation addr + self.rebase_addr without normalization.

[rhelmot]

The semantics of addr + rebase_addr are the following: addr is an address as it appears in readelf, and rebase_addr is the address that must be added to it in order to produce the address as it appears at runtime, i.e. the address in real loaded memory corresponding to address zero in the unrebased image. Therefore, in the ideal world where all the code worked, you wouldn't need to change the assertion in that one test.

Is it possible that this behavior is due to an incorrect assumption that default base (requested base) is always 0x0 for relocatable images?

Yes. I honestly didn't know that such binaries could exist before this issue was opened, so who knows where else the problem could be lurking... My hope is that except for the testcases, the rest of angr will only use the CLE interfaces instead of the direct addresses, so making the interface consistent will fix problems elsewhere.

[symflood]

Thanks for the support.
I have one question left, it's about addressing in memory mapper used by the loader (Clemory) and related objects:

1. Top level backers addressing is absolute, i.e. start is virtual address where each module is mapped
2. Child level backers addressing is relative to the parent

If these assumptions are correct, it seems that addressing in the second case should be also absolute, and also because of rebasing.

But are they correct?

[rhelmot]

The top level clemory, Loader.memory, is the whole address space as it appears in a debugger. Each backer memory should be the layout as it appears in readelf. Both these assumptions are very strongly baked into CLE. I now realize that this will cause problems with non-zero-based pic-libraries, since clemory will probably complain that there are overlapping backers. Two possible solutions come to mind:

• Change clemory's overlap detection to use the "minimum mapped address" of another clemory. This will complicate the lookup code drastically, I think.
• Have each backer have two clemories - one that is the memory of the process starting at address 0, regardless of what the base address of the program is supposed to be, and one that is the former clemory mapped at the correct address for where the elf says it should go. The former clemory would be what is mapped into the global clemory, at address obj.get_min_addr().

[ltfish]

@rhelmot I think this is the problem that we've discussed before. CLE respects the "ideal" base address specified by the library being loaded into the memory, and it always uses the previously maximum address as the new minimum base address for future libraries to be loaded. Hence, when libraries with large default base addresses are loaded, some large holes will be created between their memory spaces, which in the end leads to the issue above.

The fix, as I proposed before, was to change how _get_safe_rebase_addr() behaves: instead of using the current max_addr, we always perform a linear scan from the beginning of the memory space and find a hole that is large enough to accommodate the new library to load. So we don't have to manually patch any library and change their default base addresses before loading them. What do you think?

[symflood]

@ltfish
As I understand, there are a lot of confusion with addresses types, so

a linear scan from the beginning of the memory space and find a hole that is large enough to accommodate the new library to load

will not help too much. As an example, main_bin is already located at 0x0 address, so there is no such hole

[ltfish]

@amttr My understanding is that the original issue was because that the maximum address (rebased) is too large due to loading some libraries with very high default base addresses, apart from several other less obvious bugs you and @rhelmot mentioned in this issue.

[symflood]

@ltfish it just a result of incorrect usage of addresses types. The reason is there are many places inside CLE where VA(MVA/LVA)/RVA were misused. angr and angrop also suffer from the same issue.

[rhelmot]

I still don't understand what the semantics of those three acronyms are supposed to refer to. Is there somewhere where all this is written down? For CLE we couldn't find anything of the sort so we sort of... made up our own classification.

[rhelmot]

Regardless, we do have test cases now, so I can and will make it all work. I think we could even do it before the hell refactor over in angr is over, since this should just touch CLE if my understanding of the problem is right. (From rereading my last post last month on this issue I think I know what I'm talking about? probably? and I know where to start working on a solution)

[symflood]

@rhelmot sorry, I mean Relative Virtual Address and Virtual Address (using Linked or Mapped image base). As we've talked earlier CLE consist code which sometimes uses address with two bases applied.
I'll provide the first part of PR in about an hour or so. It took some time to test several solutions and to understand that addressing inside Clemory cannot be changed )).

[ltfish]

@amttr Don't get me wrong, I'm not saying the misuses do not exist. In fact, they have always been a big problem in CLE. I'm sure we got a lot of things wrong due to our ignorance. However, the current logic in _get_safe_rebase_addr() is buggy in the sense that it will create "holes" when multiple libraries are loaded and are always rebased using the most recent maximum address in the process. I experienced that issue, and I don't think that will be mitigated by your PR. Let me know if you disagree with this.

I'm not saying you should address it. If it is a real issue (which I believe it is), it can be a separate issue anyway.

[symflood]

@ltfish I agree. This is definitely a separate issue.

[rhelmot]

Is this now resolved with the merging of those PRs? :)

[symflood]

I think prelinked binaries from should be merged too, or you can add rebased versions of those by yourself with prelink rebase angr/binaries#13

$ prelink --help | grep -A1 Relocate
  -r, --reloc-only=BASE_ADDRESS   Relocate library to given address, don't
                             prelink