CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 5 of 6 · 3 min read

Randomisation

Randomisation, and what protection does not give

In plain words: On a normal run, the addresses change. The same program run twice, with randomisation on, printed these heap and stack addresses:

run 1:  heap 0x565516a702a0   stack 0x7ffdb6350cb4   libc 0x7f0513060100
run 2:  heap 0x556ec6a5b2a0   stack 0x7fff98a41f74   libc 0x7f71af060100

The low bits (...2a0) stay the same, and the rest changes. This is address space layout randomisation (ASLR). The setting /proc/sys/kernel/randomize_va_space was 2 on the test machine, which means full randomisation. The kernel places the stack, the heap, the shared libraries and the program image at random starting points on each run. With setarch -R, which turns it off for one command, the addresses were the same on every run (0x555555555199 for main, as above).

Randomisation does not enforce protection. It makes attacks harder, since an attacker who needs the address of a function cannot guess it. The protection itself, the rule that process A cannot reach process B's memory, comes from the MMU and its tables.

Base and limit has serious weaknesses, and they explain what follows:

  • Each process needs one contiguous region of physical memory. Finding one large enough is hard when memory is divided into scattered pieces (page 2).
  • The space between the stack and the heap is wasted. A process needs room to grow, but the region is reserved as a whole, even though most of it is unused.
  • Sharing is hard. Two processes cannot share one copy of the code of a library, because each has its own region.
  • A process cannot be larger than the memory. There is no way to keep only part of a process in memory.

The next pages replace the single region with many small pieces, called pages, so that none of these problems remains.

Address space layout randomisation

Address space layout randomisation (ASLR) is a kernel feature that places the stack, heap, libraries and program image at random addresses on each run, so that an attacker cannot predict the address of code or data.

Example: the heap started at 0x565516a702a0 in one run and at 0x556ec6a5b2a0 in the next.

Common mistake

A pointer printed by a program is not a place in the machine's real memory. Two processes can print the same pointer value and refer to different data. Never compare pointers across processes, and never send a raw pointer to another process.

Check yourself: 1. What is ASLR, and which setting file showed it was on? 2. Does ASLR protect one process from another? What does? 3. Give two weaknesses of base and limit registers.

Words you will meet

Word Meaning
Address space The range of addresses a process can use
Logical (virtual) address An address as the program uses it
Physical address An address that picks a location in the real memory
MMU Hardware that translates logical addresses to physical ones
Base register The physical start of a process's region
Limit register The size of that region
Trap A signal to the kernel that an access is not allowed
ASLR Random placement of the regions of a process on each run
Relocation Running a program at a different physical address

Quick notes

  • An address space is the range of memory addresses that a process can use, a private view that the operating system and the hardware map onto the real memory and keep separate from the views of other processes.
  • The base and limit registers are a pair of registers in the MMU that describe one contiguous region of physical memory: the base is where the region starts and the.
  • A virtual address is an address that a process uses in its instructions and data; it is not a place in the physical memory, but a number in the process's own address space that the hardware translates on each access.
  • Address space layout randomisation (ASLR) is a kernel feature that places the stack, heap, libraries and program image at random addresses on each run, so that an attacker cannot predict the address of code or data.