ELF, PIE ASLR and everything in between, specifically within Linux

Question

Before asking my question, I would like to cover some few technical details I want to make sure I've got correct:

• A Position Independent Executable (PIE) is a program that would be able to execute regardless of which memory address it is loaded into, right?

• ASLR (Address Space Layout Randomization) pretty much states that in order to keep addresses static, we would randomize them in some manner,

I've read that specifically within Linux and Unix based systems, implementing ASLR is possible regardless of if our code is a PIE, if it is PIE, all jumps, calls and offsets are relative hence we have no problem. If it's not, code somehow gets modified and addresses are edited regardless of whether the code is an executable or a shared object.

Now this leads me to ask a few questions

1. If ASLR is possible to implement within codes that aren't PIE and are executables AND NOT SHARED / RELOCATABLE OBJECT (I KNOW HOW RELOCATION WORKS WITHIN RELOCATABLE OBJECTS!!!!), how is it done? ELF format should hold no section that states where within the code sections are functions so the kernel loader could modify it, right? ASLR should be a kernel functionality so how on earth could, for example, an executable containing, for example, these instructions.

   pseudo code:

    inc_eax:
     add eax, 5
     ret
   
    main:
     mov eax, 5
     mov ebx, 6
     call ABSOLUTE_ADDRES{inc_eax}
   

   How would the kernel executable loader know how to change the addresses if they aren't stored in some relocatable table within the ELF file and aren't relative in order to load the executable into some random address?

2. Let's say I'm wrong, and in order to implement ASLR you must have a PIE executable. All segments are relative. How would one compile a C++ OOP code and make it work, for example, if I have some instance of a class using a pointer to a virtual table within its struct, and that virtual table should hold absolute addresses, hence I wouldn't be able to compile a pure PIE for C++ programs that have usage of run time virtual tables, and again ASLR isn't possible.... I doubt that virtual tables would contain relative addresses and there would be a different virtual table for each call of some virtual function...

3. My last and least significant question is regarding ELF and PIE — is there some special way to detect an ELF executable is PIE? I'm familiar with the ELF format so I doubt that there is a way, but I might be wrong. Anyway, if there isn't a way, how does the kernel loader know if our executable is PIE hence it could use ASLR on it.

I've got this all messed up in my head and I'd love it if someone could help me here.

Answer 1

Your question appears to be a mish-mash of confusion and misunderstanding.

A Position Independent Executable (PIE) is a program that would be able to execute regardless of which memory address it is loaded into, right?

Almost. A PIE binary usually can not be loaded into memory at arbitrary address, as its PT_LOAD segments will have some alignment requirements (e.g. 0x400, or 0x10000). But it can be loaded and will run correctly if loaded into memory at address satisfying the alignment requirements.

ASLR (Address Space Layout Randomization) pretty much states that in order to keep addresses static we would randomize them in some manner,

I can't parse the above statement in any meaningful way.

ASLR is a technique for randomizing various parts of address space, in order to make "known address" attacks more difficult.

Note that ASLR predates PIE binaries, and does not in any way require PIE. When ASLR was introduced, it randomized placement of stack, heap, and shared libraries. The placement of (non-PIE) main executable could not be randomized.

ASLR has been considered a success, and therefore extended to also support PIE main binary, which is really a specially crafted shared library (and has ET_DYN file type).

1. call ABSOLUTE_ADDRES{inc_eax} how would the kernel executable loader know how to change the addresses if > they aren't stored in some relocatable table

Simple: on x86, there is no instruction to call ABSOLUTE_ADDRESS -- all calls are relative.

2 ... I wouldn't be able to compile a pure PIE for C++ programs that have usage of run time virtual tables, and again ASLR isn't possible..

PIE binary requires relocation, just like a shared library. Virtual tables in PIE binaries work exactly the same way they work in shared libraries: ld-linux.so.2 updates GOT (global offset table) before transferring control to the PIE binary.

3 ... is there some special way to detect an ELF executable is PIE

Simple: a PIE binary has ELF file type set to ET_DYN (a non-PIE binary will have type ET_EXEC). If you run file a.out on a PIE executable, you'll see that it's a "shared library".