3

I'm writing a simple program that converts brainfuck code into x86_64 assembly. Part of that involves creating a large zero-initialized array at the beginning of the program. Thus, each compiled program starts with the following assembly code:

.data
ARR:
    .space 32430
.text
.globl _start
.type _start, @function
_start:
    ...     #code as compiled from the brainfuck program
    ...

From there the compiled program is supposed to be able to access any part of that array, but it should segfault if it tries to access memory before or after it.

Because the array is followed directly by a .text section, which by my understanding is read only, and because it is the first section of the program, I expected that my desired behavior would follow naturally. Unfortunately, this is not the case: compiled programs are able to access non-zero initialized data to the left of (that is, at lower addresses than) the beginning of the array.

Why is this the case and is there anything I can include in the assembly code that would prevent it?

Brandon Sides
  • 31
  • 2
  • One way to fix it is simply by counting `+` and `-` signs to see if the program overflows over the designated size - simply by causing a segmentation fault right when you go above the permitted size. `.text` should be read only, did you try iterating over the result with `gdb` or a similar tool? It probably doesn't overwrite `.text` – Zach P Dec 06 '16 at 07:15
  • You're right, it's only the left bound that gets violated. As a matter of fact, initially the array size was 30000 but programs were able to write to locations up to 32430 bytes past the start of the array; hence my band-aid solution of simply increasing the initialized array size. The issue of the other side is harder; what I assume is that the linker isn't putting my segments where I think it is. I could check each movement of the data pointer for validity but that's more overhead than I'd like; I'd prefer a solution that places my segments such that a bad array access causes a segfault. – Brandon Sides Dec 06 '16 at 07:22
  • on x86 you are always granted the access to the last byte of a page (at least in modern OSes). It would be useful to see the binary file generated ('cause 32430 is not a multiple of the page size) and to include the allocation granularity into consideration. Especially, guard pages could help. – Margaret Bloom Dec 06 '16 at 09:06
  • 1
    @BrandonSides Maybe ASLR is the cause of that, try [this](http://stackoverflow.com/questions/5194666/disable-randomization-of-memory-addresses). Did you try writing, also, well above 32,340? I think my solution might be better though - expecting the OS to warn the user is probably a very bad idea. Then again, if you're only converting to assembly so there is no reason for you to care about the behavior of the program itself – Zach P Dec 06 '16 at 09:27
  • The memory protection in x86 is not working with byte granularity, but per page. And the default `.data` segment will be unlikely positioned between two guard pages (invalid access) and even if, the size would be multiply of mem page size. I think I see two somewhat elegant options. 1) check OS API, if you can set up memory in detailed way, specifying two guard-pages around some 32+kiB buffer, then use the buffer as ARR -> write/read +-4kiB outside => crash. 2) create 64kiB ARR, and write all ARR index calculations to be unsigned 16bit, then ARR[zero_extended_16b_index] will wrap around. – Ped7g Dec 06 '16 at 10:30
  • Use the BSS instead of `.data` for zero-initialized data, so the zeroes don't have to appear literally in the executable, just a total length for the kernel's ELF program loader to map for you. Use the `.bss` directive instead of `.data`. (For C, compare the size of the executable from `int foo[1000000] = {1, 0};` vs. with an all-zero initializer. – Peter Cordes Apr 23 '18 at 10:15

1 Answers1

0

This is, of course, highly system-dependent, but since your observations suit a typical Linux/GNU system, I'll refer to such a system.

what I assume is that the linker isn't putting my segments where I think it is.

True, the linker puts the segments not in the order they appear in your code snippet, but rather .text first, .data second. We can see this e. g. with

> objdump -h ARR

ARR:     file format elf32-i386

Sections:
Idx Name          Size      VMA       LMA       File off  Algn
  0 .text         00000042  08048074  08048074  00000074  2**2
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  1 .data         00007eae  080490b8  080490b8  000000b8  2**2
                  CONTENTS, ALLOC, LOAD, DATA

compiled programs are able to access non-zero initialized data to the left of (that is, at lower addresses than) the beginning of the array.

Why is this the case …

As we also see in the above example, the .data section is linked at memory address 080490b8. Although memory pages have the length PAGE_SIZE (here getconf PAGE_SIZE yields 4096, i. e. 100016) and start at multiples of that size, the data starts at an address offset equal to the file offset 000000b8 (where the data is stored in the disk file), because the file pages containing the .data section are mapped into memory as copy-on-write pages. The non-zero initialized data below the .data section is just what happens to be in the first file page at bytes 0 to b716, including .text.

… is there anything I can include in the assembly code that would prevent it?

I'd prefer a solution that places my segments such that a bad array access causes a segfault.

As Margaret Bloom and Ped7g hinted at, you could allocate additional data below ARR and create an inaccessible guard page. This can be achieved with minimal effort by aligning ARR to the next page address. The example program below implements this and allows to test it by accepting an index argument (optionally negative) with which the ARR data is accessed; if within bounds, it should exit with status 0, otherwise segfault. Note: This method works only if the .text section does not end at a page boundary, because if it does, the .align 4096 is without effect; but since the assembly code is created with a converter program, that program should be able to check this and add a few extra .text bytes if needed.

.data
    .align 4096
ARR:
    .space 30000        # we'll actually get 32768
.text
.globl _start
.type _start, @function
_start:
    mov (%esp),%ebx     # argc
    cmp $1,%ebx
    jbe 9f
    mov $0,%ax
    mov $1,%ebx         # sign 1
    mov 8(%esp),%esi    # argv[1]
0:  movb (%esi),%cl     # convert argument string to integer
    jcxz 1f
    sub $'0',%cl
    js  2f
    mov $10,%dx
    mul %dx
    add %cx,%ax
    jmp 3f
2:  neg %ebx            # change sign
3:  add $1,%esi
    jmp 0b
1:  mul %ebx            # multiply with sign 1 or -1
    movzx ARR(%eax),%ebx# load ARR[atoi(argv[1])]
9:  mov $1,%eax
    int $128            # _exit(ebx);
Community
  • 1
  • 1
Armali
  • 18,255
  • 14
  • 57
  • 171
  • You should use `.bss`, instead of `.data`. Also, where did that weird asm come from? Why so much 16-bit stuff? And you're depending on the upper byte of CX to be zeroed for `movb` instead of `movzbl` to work, so why not depend on the whole ECX and `jecxz` and so on. (Or better, *use* `movzbl` to remove the false dependency in the loop). Or better, avoid `jecxz` because it's not very efficient. Also, you can multiply by 10 and accumulate with 2 LEA instructions, or you could use `imul $10, %eax, %eax` instead of that clunky stuff with `dx`. Also, everyone writes `int $0x80`, not `$128`. – Peter Cordes Apr 23 '18 at 10:23
  • _Also, everyone writes int $0x80, not $128._ - I already disproved that statement. – Armali Apr 23 '18 at 10:48
  • Heh, fair point. Everyone *else* writes `int $0x80` like a normal person. That's just a matter of style; the other points result in different (less efficient) machine code. – Peter Cordes Apr 23 '18 at 11:09