Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

C99 doesn't need function bodies, or 'VLAs are Turing complete'

lemon.rip

Post reply on HN
Print view View original

201–210 of 257 posts

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#201

Post by mtlmtlmtlmtl »

10000truths wrote: post #162
mtlmtlmtlmtl wrote: post #149

Earlier quoted context omitted.

That's not really a fair comparison though. Recursion is strictly necessary to implement several algorithms. Even if "banned" from the language, you would have to simulate it using a heap allocated stack or something to do certain things. None of this applies to VLA arguments.

It's not strictly necessary precisely because all recursions can be "simulated" with a heap allocated stack. And in fact, the "simulated" approach is almost always better, from both a performance and a maintenance perspective.

This is simply nonsense. In cases with highly complex recursive algorithms, "unrecursing" would make the code a completely unmaintainable mess, requiring an immensely complicated state machine, which is why something like Stockfish doesn't do that in its recursive search function even though the code base is extremely optimised. And yes, some algorithms are inherently recursive, and don't gain any meaningfull performance from the heap stack + state machine approach.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#202

Post by throw827474737 »

saagarjha wrote: post #175
10000truths wrote: post #162

Earlier quoted context omitted.

It's not strictly necessary precisely because all recursions can be "simulated" with a heap allocated stack. And in fact, the "simulated" approach is almost always better, from both a performance and a maintenance perspective.

Definitely not.

For the can be, or performance, or maintenance perspective?? With example please ..

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#203

Post by protomolecule »

mtlmtlmtlmtl wrote: post #152
petters wrote: post #146

Earlier quoted context omitted.

Welcome to the world of undefined behavior. Anything can happen....

I think this is a common misunderstanding about UB. It's not that anything can happen, just that the standard doesn't specify what happens, meaning whatever happens is compiler/architecture/OS dependent. So you can't depend on UB in portable code. But something definite will happen, given the current state of the system. After all, if it didn't, these things wouldn't be exploitable either.

What you are describing is unspecified and implementation-defined behavior [0].

Avoiding UB (edit: in general) doesn't have anything to do with the code being portable and everything with the code not being buggy [1][2].

[0] https://en.cppreference.com/w/c/language/behavior

[1] https://blog.regehr.org/archives/213

[2] http://blog.llvm.org/2011/05/what-every-c-programmer-should-...

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#204

Post by mtlmtlmtlmtl »

tialaramex wrote: post #171
mtlmtlmtlmtl wrote: post #152

Earlier quoted context omitted.

I think this is a common misunderstanding about UB. It's not that anything can happen, just that the standard doesn't specify what happens, meaning whatever happens is compiler/architecture/OS dependent. So you can't depend on UB in portable code. But something definite will happen, given the current state of the system. After all, if it didn't, these things wouldn't be exploitable either.

> But something definite will happen, given the current state of the system. This is only true in the very loose and more or less useless sense that the compiler is definitely going to emit some machine code. What does that machine code do in the UB case? It might be absolutely anything . One direction you could go here is you insist that surely the machine code has a defined meaning for all possible machine states,…

I'm aware you can get some pretty crazy behaviours, say if you end up overwriting a return address and your code begins to jump around like crazy. Even that could reproduce the same behaviour consistently though.

I once had a bug like that in a piece of AVR C code where the stack corruption would happen in the same place every time and the code would pathologically jump to the same places in the same order every time. It's worth noting though that when there's an OS, usually what will happen is just a SIGABRT. See the OpenBSD libc allocator for a masterclass in making misbehaving programs crash.

I was never advocating to rely on UB, btw. But yes, UB can be understood in many cases.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#205

Post by legalcorrection »

protomolecule wrote: post #203
mtlmtlmtlmtl wrote: post #152

Earlier quoted context omitted.

I think this is a common misunderstanding about UB. It's not that anything can happen, just that the standard doesn't specify what happens, meaning whatever happens is compiler/architecture/OS dependent. So you can't depend on UB in portable code. But something definite will happen, given the current state of the system. After all, if it didn't, these things wouldn't be exploitable either.

What you are describing is unspecified and implementation-defined behavior [0]. Avoiding UB (edit: in general) doesn't have anything to do with the code being portable and everything with the code not being buggy [1][2]. [0] https://en.cppreference.com/w/c/language/behavior [1] https://blog.regehr.org/archives/213 [2] http://blog.llvm.org/2011/05/what-every-c-programmer-should-...

Oh really? Then why does every compiler I use have a parameter to turn off strict aliasing?

You cite to a source that contradicts you. In the llvm blog post: "It is also worth pointing out that both Clang and GCC nail down a few behaviors that the C standard leaves undefined."

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#206

Post by rhexs »

saagarjha wrote: post #178
einpoklum wrote: post #44

Earlier quoted context omitted.

With VLAs: 1. The stack-smashing pattern is simple, straightforward and sure to be used often. Other ways to smash the stack require some more "effort"... 2. It's not just _you_ who can smash the stack. It's the fact that anyone who calls your function will smash the stack if they pass some large numeric value.

They can overflow the stack. They cannot smash the stack.

Useless semantic pedantry at best, but arguable wrong as there isn't some sort of ISO standard on dumb hacking terms.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#207

Post by saagarjha »

rhexs wrote: post #206
saagarjha wrote: post #178

Earlier quoted context omitted.

They can overflow the stack. They cannot smash the stack.

Useless semantic pedantry at best, but arguable wrong as there isn't some sort of ISO standard on dumb hacking terms.

Overflowing the stack gives you a segfault. Smashing the stack lets hackers pop a shell on your computer. They are incredibly different. VLAs can crash your program, but they do not give attackers the ability to scribble all over the stack.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#208

Post by protomolecule »

legalcorrection wrote: post #205
protomolecule wrote: post #203

Earlier quoted context omitted.

What you are describing is unspecified and implementation-defined behavior [0]. Avoiding UB (edit: in general) doesn't have anything to do with the code being portable and everything with the code not being buggy [1][2]. [0] https://en.cppreference.com/w/c/language/behavior [1] https://blog.regehr.org/archives/213 [2] http://blog.llvm.org/2011/05/what-every-c-programmer-should-...

Oh really? Then why does every compiler I use have a parameter to turn off strict aliasing? You cite to a source that contradicts you. In the llvm blog post: "It is also worth pointing out that both Clang and GCC nail down a few behaviors that the C standard leaves undefined."

Sometimes a compiler gives a guarantee that a particular UB is always handled in a specific way, but you cannot generalize this to all UB.

Added 'in general' to my comment to make this explicit.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#209

Post by Leherenn »

zajio1am wrote: post #133
rwmj wrote: post #82

Earlier quoted context omitted.

VLAs make it a lot easier to corrupt the stack by accident. Unless you're quite a careful coder, stuff like: f (size_t n) { char str[n]; leads to a possible exploit where the input is manipulated so n is large, causing a DoS attack (at best) or full exploit at worse. I'm not saying that banning VLAs solves every problem though. However the main reason we forbid VLAs in all our code is because thread stacks (particula…

> stuff like ... leads to a possible exploit where the input is manipulated so n is large The same is true for most recursive calls, should recursion be also banned in programming languages?

MISRA C bans recursion for instance.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#210

Post by Someone »

bjourne wrote: post #186
Dylan16807 wrote: post #168

Earlier quoted context omitted.

> What exactly are you doing there, in kernel code? In kernel code? What you're doing is triggering the guard page over and over if the stack is pushing into new territory. > Do what exactly? Just reject stack allocations that are larger than the cluster of guard pages? And keep book of past allocations? A lot of that needs to happen at runtime, since the compiler doesn't know the size with VLAs. Just hit the guard p…

An attacker would first trigger a large VLA-allocation that puts the stack pointer within a few bytes of the guard page. Then they would just have the kernel put a return address or two on the stack and that would be enough to cause a page fault. The only way to guard against that would be to check that every CALL instruction has enough stack space which is infeasible.

An attacker could trigger a large VLA allocation that jumps over the guard page, and a write to that allocation. That write would start _below_ the guard page, so damage would be done before the page fault occurs (ideally, that write wouldn’t touch the guard page and there wouldn’t be a page fault but that typically is harder to do; the VLA memory allocation typically is done to be fully used)

Triggering use of the injected code may require another call timed precisely to hit the changed code before the page fault occurs.

Of course, the compiler could and should check for stack allocations that may jump over guard pages and abort the program (or, if in a syscall, the OS) or grow the stack when needed. Also, VLAs aren’t needed for this. If the programmer creates a multi-megabyte local array, this happens, too (and that can happen accidentally, for example when increasing a #define and recompiling)

The lesson is, though, that guard pages alone don’t fully protect against such attacks. The compiler must check total stack space allocated by a function, and, if it can’t determine that that’s under the size of your guard page, insert code to do additional runtime checks.

I don’t see that as a reason to outright ban VLAs, though.

Post reply on HN