Tuesday, 21 July 2015

Don't use Variable Length Arrays

Hi kids! I'm here to tell you about why to never play with fire! You see, fire is dangerous, hot, and can destroy your house and all your toys!

By fire I mean, the misfeature in C99 called "Variable Length Arrays." You may ask, "Why is this a misfeature? They're so convenient zomg!!!" The answer is simple really: they are ridiculously unsafe.

Take this for example:

#include <stdio.h>
#include <string.h>
#include <math.h>

void huge_vla(size_t size)
{
        int vla[size];
        while(--size) vla[size] = rand();
        printf("Ensure the compiler doesn't optimise it away\n",
                (char *)vla);
}

int main(int argc, char **argv)
{
        int power;
        printf("Input a large number: ");
        scanf("%d", &power);
        huge_vla((size_t)powl(2, power));
        return 0;
}



Looks harmless, although maybe a little contrived. If you're paying attention, you'll probably notice right away that large powers of 2 will certainly exceed the machine's memory.

Now here's where the problem comes into play:

elizabeth@catherine ~ $ ./test
Input a large number: 2
Ensure the compiler doesn't optimise it away
elizabeth@catherine ~ $ ./test
Input a large number: 10
Ensure the compiler doesn't optimise it away
elizabeth@catherine ~ $ ./test
Input a large number: 16
Ensure the compiler doesn't optimise it away
elizabeth@catherine ~ $ ./test
Input a large number: 24
Segmentation fault  

 
You might think, "well 2^24 is pretty big anyway." But, it's only 16,777,216 bytes. Odds are pretty good your average Wikipedia article (excluding stubs) has well more than that if you count images.

The reason it is is so low is because of this:

0000000000400776 <huge_vla>:
  400776:       55                      push   %rbp
  400777:       48 89 e5                mov    %rsp,%rbp
  40077a:       53                      push   %rbx
  40077b:       48 83 ec 38             sub    $0x38,%rsp
  40077f:       48 89 7d c8             mov    %rdi,-0x38(%rbp)
  400783:       64 48 8b 04 25 28 00    mov    %fs:0x28,%rax
  40078a:       00 00
  40078c:       48 89 45 e8             mov    %rax,-0x18(%rbp)
  400790:       31 c0                   xor    %eax,%eax
  400792:       48 89 e0                mov    %rsp,%rax
  400795:       48 89 c3                mov    %rax,%rbx
  400798:       48 8b 45 c8             mov    -0x38(%rbp),%rax
  40079c:       48 89 c2                mov    %rax,%rdx
  40079f:       48 83 ea 01             sub    $0x1,%rdx
  4007a3:       48 89 55 d8             mov    %rdx,-0x28(%rbp)
  4007a7:       49 89 c2                mov    %rax,%r10
  4007aa:       41 bb 00 00 00 00       mov    $0x0,%r11d
  4007b0:       49 89 c0                mov    %rax,%r8
  4007b3:       41 b9 00 00 00 00       mov    $0x0,%r9d
  4007b9:       48 c1 e0 02             shl    $0x2,%rax
  4007bd:       48 8d 50 03             lea    0x3(%rax),%rdx
  4007c1:       b8 10 00 00 00          mov    $0x10,%eax
  4007c6:       48 83 e8 01             sub    $0x1,%rax
  4007ca:       48 01 d0                add    %rdx,%rax
  4007cd:       be 10 00 00 00          mov    $0x10,%esi
  4007d2:       ba 00 00 00 00          mov    $0x0,%edx
  4007d7:       48 f7 f6                div    %rsi
  4007da:       48 6b c0 10             imul   $0x10,%rax,%rax
  4007de:       48 29 c4                sub    %rax,%rsp
  4007e1:       48 89 e0                mov    %rsp,%rax
  4007e4:       48 83 c0 03             add    $0x3,%rax
  4007e8:       48 c1 e8 02             shr    $0x2,%rax
  4007ec:       48 c1 e0 02             shl    $0x2,%rax
  4007f0:       48 89 45 e0             mov    %rax,-0x20(%rbp)
  4007f4:       eb 17                   jmp    40080d <huge_vla+0x97>
  4007f6:       b8 00 00 00 00          mov    $0x0,%eax
  4007fb:       e8 70 fe ff ff          callq  400670 <rand@plt>
  400800:       89 c1                   mov    %eax,%ecx
  400802:       48 8b 45 e0             mov    -0x20(%rbp),%rax
  400806:       48 8b 55 c8             mov    -0x38(%rbp),%rdx
  40080a:       89 0c 90                mov    %ecx,(%rax,%rdx,4)
  40080d:       48 83 6d c8 01          subq   $0x1,-0x38(%rbp)
  400812:       48 83 7d c8 00          cmpq   $0x0,-0x38(%rbp)
  400817:       75 dd                   jne    4007f6 <huge_vla+0x80>
  400819:       48 8b 45 e0             mov    -0x20(%rbp),%rax
  40081d:       48 89 c6                mov    %rax,%rsi
  400820:       bf c0 09 40 00          mov    $0x4009c0,%edi
  400825:       b8 00 00 00 00          mov    $0x0,%eax
  40082a:       e8 f1 fd ff ff          callq  400620 <printf@plt>
  40082f:       48 89 dc                mov    %rbx,%rsp
  400832:       48 8b 45 e8             mov    -0x18(%rbp),%rax
  400836:       64 48 33 04 25 28 00    xor    %fs:0x28,%rax
  40083d:       00 00
  40083f:       74 05                   je     400846 <huge_vla+0xd0>
  400841:       e8 ca fd ff ff          callq  400610 <__stack_chk_fail@plt>
  400846:       48 8b 5d f8             mov    -0x8(%rbp),%rbx
  40084a:       c9                      leaveq
  40084b:       c3                      retq


Well, GCC emits some pretty crummy code at -O0 I guess, though a lot of it is because memset was inlined. But if you look closely (and if you can't read x86 asm, I will simply tell you), you'll see it simply tosses it on the stack. It doesn't call malloc() and get anything from the program break or an mmaped region. Nope, it just uses the stack space, which is in short supply.

This is also why alloca() is considered unsafe, and anyone sensible should not be using it, no matter what that one thing Drepper wrote says.

Basically, you have a gratuitous stack overrun, and there is no real way to determine how much stack you even have left. Of course, you can see it adds guards to ensure the stack overrun can't do anything nasty, but on older systems, it won't do this at all.

Deeply nested calls or recursion could lower stack space further; more variables or arrays would do it too. Your limit may be a lot less than 2^24. You just don't know, and the compiler can't check for you (I'm not sure if GCC checks array bounds anyway), because it's only known at runtime what the size will be.

I suppose some tool will say, "why not use a SIGSEGV handler?" To which I say, "oh wow, I bet you write bug-free code which never has wild pointers that corrupt the SIGSEGV handler or anything like that, nope, that's not you." Never assume you're as good as you think you are. In any case, this is terrible practise, unusable in a library, and there is a special place in Hell reserved for people who abuse SIGSEGV in such a terrible way to hide the fact they're using unsafe practises.

Basically the takeaway is this: just use malloc(). At least when it fails, you know about it, and you can tell your user what went wrong with an "out of memory" error, versus "OH SHIT I JUST SHIT MY FUCKING PANTS!"

EDIT:

I would like to point out clang emits better code at -O0, but does the same thing, lest any of you Apple fans believe your infallible popes, His Holiness Tim Cook and the late Pontiff Steve Jobs can do no wrong:

0000000000400720 <huge_vla>:
  400720:       55                      push   %rbp
  400721:       48 89 e5                mov    %rsp,%rbp
  400724:       48 83 ec 20             sub    $0x20,%rsp
  400728:       48 89 7d f8             mov    %rdi,-0x8(%rbp)
  40072c:       48 89 e0                mov    %rsp,%rax
  40072f:       48 89 45 f0             mov    %rax,-0x10(%rbp)
  400733:       48 8d 04 bd 0f 00 00    lea    0xf(,%rdi,4),%rax
  40073a:       00
  40073b:       48 83 e0 f0             and    $0xfffffffffffffff0,%rax
  40073f:       48 89 e7                mov    %rsp,%rdi
  400742:       48 29 c7                sub    %rax,%rdi
  400745:       48 89 fc                mov    %rdi,%rsp
  400748:       48 89 7d e8             mov    %rdi,-0x18(%rbp)
  40074c:       48 8b 45 f8             mov    -0x8(%rbp),%rax
  400750:       48 05 ff ff ff ff       add    $0xffffffffffffffff,%rax
  400756:       48 89 45 f8             mov    %rax,-0x8(%rbp)
  40075a:       48 3d 00 00 00 00       cmp    $0x0,%rax
  400760:       0f 84 17 00 00 00       je     40077d <huge_vla+0x5d>
  400766:       b0 00                   mov    $0x0,%al
  400768:       e8 a3 fe ff ff          callq  400610 <rand@plt>
  40076d:       48 8b 4d f8             mov    -0x8(%rbp),%rcx
  400771:       48 8b 55 e8             mov    -0x18(%rbp),%rdx
  400775:       89 04 8a                mov    %eax,(%rdx,%rcx,4)
  400778:       e9 cf ff ff ff          jmpq   40074c <huge_vla+0x2c>
  40077d:       48 bf 0c 09 40 00 00    movabs $0x40090c,%rdi
  400784:       00 00 00
  400787:       48 8b 45 e8             mov    -0x18(%rbp),%rax
  40078b:       48 89 c6                mov    %rax,%rsi
  40078e:       b0 00                   mov    $0x0,%al
  400790:       e8 2b fe ff ff          callq  4005c0 <printf@plt>
  400795:       48 8b 75 f0             mov    -0x10(%rbp),%rsi
  400799:       48 89 f4                mov    %rsi,%rsp
  40079c:       89 45 e4                mov    %eax,-0x1c(%rbp)
  40079f:       48 89 ec                mov    %rbp,%rsp
  4007a2:       5d                      pop    %rbp
  4007a3:       c3                      retq  
  4007a4:       66 66 66 2e 0f 1f 84    data16 data16 nopw %cs:0x0(%rax,%rax,1)
  4007ab:       00 00 00 00 00


Different compiler, same old technique. Except sans stack protection.