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

151–160 of 257 posts

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

#151

Post by rhexs »

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?

When writing secure C? In most cases, absolutely.

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

#152

Post by mtlmtlmtlmtl »

petters wrote: post #146
Dylan16807 wrote: post #144

Earlier quoted context omitted.

How does a huge VLA corrupt the stack? If there's not enough space but code keeps going then isn't that a massive bug with your compiler or runtime?

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.

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

#153

Post by phibz »

Koshkin wrote: post #102
pjmlp wrote: post #98

Earlier quoted context omitted.

That is like saying if sushi knifes are already sharp enough, there is no issue cutting fish with a samurai sword instead, except at least with the knife maybe the damage isn't as bad.

I like your comparison of a C programmer with a samurai.

It's more like the C programmer is a sushi master. They can make a delicious, beautifully crafted snack. But if the wrong ingredients are used you'll get very sick.

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

#154

Post by Phrodo_00 »

camel-cdr wrote: post #72
Phrodo_00 wrote: post #63

Earlier quoted context omitted.

Talking theoretically, since size_t is defined as: > size_t can store the maximum size of a theoretically possible object of any type (including array). In a proper theoretical turing machine, size_t would allow you to create and address arbitrarily large arrays too.

`sizeof(size_t)` and `size_t x; sizeof x` must be constant expressions. It is possible to create a c implementation where the size of a pointer is arbitrarily large, but it can't grow/isn't infinite. For any give C implementation, it is thus trivial to theoretically solve the halting problem (assuming no stdio.h stuff is used).

Speaking in so much the abstract that it becomes absurd (which also can be used to prove your point, but bear with me here), since `size_t` is required to hold the size of any object, and a turing machine has infinite memory, then size_t would also need to be infinitely big, and `sizeof(size_t)` would be a constant returning infinity.

So, I don't think it having to be a constant is a problem as much as having to deal with infinitely big numbers inside of infinite memory (which may or may not be a contradiction, depending on axioms used to define a turing machine. I still need to work my way through annotated turing).

Of course, things do get a lot simpler and grounded using IO functions like you said earlier.

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

#155

Post by kllrnohj »

dataflow wrote: post #125
tedunangst wrote: post #123

Earlier quoted context omitted.

Here's a nickel, kid. The bullshit about oh my embedded systems doesn't have dynamic memory is bullshit. You either know how big your stack is and how many elements there are, and you make the array that big. Or you don't know and you're fucked. You can't clever your way out of not knowing how big to make the array with magic stack fairy pretend dynamic memory. You can only fuck up. Is there room for 16 elements? The…

I think the parent comment was about malloc not being real-time? Not about storage space. Though I do wonder why there can't be a form of malloc that allocates in a stack like fashion in real time to satisfy the formal verifier?

Real time also generally means your input sizes are bounded and known, otherwise the algorithm itself isn't realtime and malloc isn't the reason why.

But strictly speaking the only problem is a malloc/free that can lock (you can end up with priority inversion). So a lock-free malloc would be realtime just fine, it doesn't have to be stack growth only.

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

#156

Post by camel-cdr »

Phrodo_00 wrote: post #154
camel-cdr wrote: post #72

Earlier quoted context omitted.

`sizeof(size_t)` and `size_t x; sizeof x` must be constant expressions. It is possible to create a c implementation where the size of a pointer is arbitrarily large, but it can't grow/isn't infinite. For any give C implementation, it is thus trivial to theoretically solve the halting problem (assuming no stdio.h stuff is used).

Speaking in so much the abstract that it becomes absurd (which also can be used to prove your point, but bear with me here), since `size_t` is required to hold the size of any object, and a turing machine has infinite memory, then size_t would also need to be infinitely big, and `sizeof(size_t)` would be a constant returning infinity. So, I don't think it having to be a constant is a problem as much as having to deal…

I don't think infinitely large integer constant area construct that makes sense.

As far as I'm aware, there isn't an instance of an infinitely large integer, even in mathematics, there are finite integers and there is the concept of infinity. (And size_t is defined as an unsigned integer type)

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

#157

Post by dataflow »

kllrnohj wrote: post #155
dataflow wrote: post #125

Earlier quoted context omitted.

I think the parent comment was about malloc not being real-time? Not about storage space. Though I do wonder why there can't be a form of malloc that allocates in a stack like fashion in real time to satisfy the formal verifier?

Real time also generally means your input sizes are bounded and known, otherwise the algorithm itself isn't realtime and malloc isn't the reason why. But strictly speaking the only problem is a malloc/free that can lock (you can end up with priority inversion). So a lock-free malloc would be realtime just fine, it doesn't have to be stack growth only.

> Real time also generally means your input sizes are bounded and known, otherwise the algorithm itself isn't realtime and malloc isn't the reason why.

I think you meant to say something else? Real-time is a property of the system indicating a constraint on the latency from the input to the output—it doesn't constrain the input itself. (Otherwise even 'cat' wouldn't be real-time!)

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

#158

Post by kllrnohj »

asguy wrote: post #101
SavageBeast wrote: post #19

I haven't thought about C in years - that one where author passes in a printf as a char array element and de-references it to execute it ... gives me chills. Y'all kids have fun - Im going to stick with my VM over here and call it a day. This makes even modern JS look sane by comparison. Excellent write up too.

> I haven't thought about C in years ... Im going to stick with my VM over here and call it a day. What's your VM written in?

Probably not C regardless. How many widely used VMs are in C? Python is about it, right?

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

#159

Post by asguy »

Banana699 wrote: post #148
asguy wrote: post #143

Earlier quoted context omitted.

Except for most of deno that's written in Unsafe C++. https://v8.dev/

A JS runtime is a lot more than the core engine, or else nodejs is just a thin wrapper over V8 as well, which is obviously absurd. So without a count of the source lines for each language's portion of the implementation (very rough but acceptable first approximation of how much is implemented in each), you can't claim C++ is doing most of the heavy lifting and be taken seriously. PS. the worst C++ code is still a hel…

No post body was provided.

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

#160

Post by anyfoo »

Dylan16807 wrote: post #144
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…

How does a huge VLA corrupt the stack? If there's not enough space but code keeps going then isn't that a massive bug with your compiler or runtime?

Okay. How do you tell the kernel that? Sure, the kernel will have put a guard page or more at the end of the stack, so that if you regularly push onto the stack, you will eventually hit a guard page and things will blow up appropriately.

But what if the length of your variable length array is, say, gigabytes, you've blown way past the guard pages, and your pointer is now in non-stack kernel land.

You'd have to check the stack pointer all the time to be sure, that's prohibitive performance-wise. Ironically, x86 kind of had that in hardware back when segmentation was still used.

Post reply on HN