Pointer confusion in C -language

[SiliconWizard]

Even the smallest commercial RISC-V CPU cores usually implement PMP (Physical Memory Protection) with typically 8 or 16 memory regions which can each be assigned Read/Write/eXecute protections for each of Machine/Supervisor (if it exists)/User modes. This is separate to and much lighter weight than MMU.

Hey? That's awesome! I had to pay extra money to buy MIPS32 commercial cores with PMP implemented. I really like to hear it's a default feature with RISC-V commercial cores

Before you get too excited, you'd probably need to compare the cost of the respective IPs, though.

[Nominal Animal]

Yes, but to you and those who mentioned something similar: keep in mind what I said above: what you describe is memory protection. What I suggested was for code instrumentation (with stacks in mind here, but I do have a knack for code instrumentation anyway.) Those are two different things.

Agreed; that is also why I qualified it with "If you expand the idea".

The security aspect can obviously used for instrumentation (at a suitable granularity), by simply having the out-of-bounds access interrupt expand the region.  It is probably not useful to make it byte-granular, but it does cover all accesses to that segment.

you can define a memory area for a stack and protect it, but there's little way you can prevent some program to write outside of the stack area, when it means to write inside of it, if this 'outside' location is itself another memory area that is allowed to be written to.

That is precisely why the segmented memory model so intrigues me: because the "segment register" acts as the key to the address space, it does affect all accesses.  For a stack, it means that an OS on x86-64 could trivially have separate segments (and segment descriptors) for stack data, and initially only allocate a single page; and whenever a page fault in that segment occurs, the OS kernel could expand the mapping up to whatever process-specific limits.  There would be some overhead/slowdown, but I guess it would be neglible compared to the issues with fixed-size per-thread stacks in e.g. Linux.  (Even virtual address space without backing pages, costs resources.)

What I don't know how to implement, is any sort of automatic shrinking of such segments; or even how to instrument it.  Yes, you can track accesses, but only the process itself knows when the data in that segment is no longer needed; perhaps it knows that it will never need more than N bytes of stack, and uses a region beyond that as an extra scratchpad or something.

It is also the reason why I find named address spaces (on any hardware that can use them, not just on hardware that has to use them like Harvard architecture AVRs without an unified address space) so darned intriguing and useful in embedded/freestanding C and C++.  It just makes all the complexity and overhead *vanish*.

(I've experimented a bit about vectors or indirect addressing modes including address space identifiers within the value, or address of the pointer, some time ago, and how to expose that to a C or C++ like systems programming language.  I admitted defeat there; it is technically possible, but the complexity needed and overhead spent is way more than what benefits I could squeeze out of it. "Segment register overrides", or instruction prefixes/modifiers that specify the nonstandard address space the instruction operates on, with a couple of CSRs defining those address spaces, is just delightfully simple and effective in comparison.  Granted, I have NOT implemented anything on an FPGA yet, so my opinion on this is subject to change once I do.)

[SiliconWizard]

you can define a memory area for a stack and protect it, but there's little way you can prevent some program to write outside of the stack area, when it means to write inside of it, if this 'outside' location is itself another memory area that is allowed to be written to.

That is precisely why the segmented memory model so intrigues me: because the "segment register" acts as the key to the address space, it does affect all accesses.  For a stack, it means that an OS on x86-64 could trivially have separate segments (and segment descriptors) for stack data, and initially only allocate a single page; and whenever a page fault in that segment occurs, the OS kernel could expand the mapping up to whatever process-specific limits.

OK, with this example, I can see the benefits of a segmented memory model. (Of course not the horrible segments of non-protected x86!)

Actually, any memory access could be implemented as a pair of some key (that you can call "segment") identifying a memory block with given access rights, and an address (offset) within this block. This scheme can of course be used also for MMIO.

Flat address spaces are more convenient to use, but they are pretty crappy security-wise.

[Nominal Animal]

Actually, any memory access could be implemented as a pair of some key (that you can call "segment") identifying a memory block with given access rights, and an address (offset) within this block. This scheme can of course be used also for MMIO.

Exactly.  For most accesses, like on x86-64 (aka AMD64), the default key is used (as implied by the instruction).

My experiments thus far have shown that encoding the key in the pointer value does not really work.  You do want the instruction to specify the key, and not the address being referred to.  In C and C++, this maps surprisingly well to the named address space extensions.

Encoding the key in the address value seems interesting at first.  I examined using the least significant bits of a base address, with base addresses having sufficiently large alignment requirements (64 bits or 8 bytes seems a good value on 64-bit arches; 32 bits or 4 bytes would be okay on 32-bit ones, I believe, based on examining how segments and named address spaces are used in current code).  It just does not map at all to the sort of continuous linear address spaces C and C++ expects.
After that frustration, seeing how "segments" as address space overrides, and expressing those via GCC C or clang C/C++ named address space extensions, surprised the heck out of me.

On an embedded architecture without virtual memory of any sort, the protection mechanism is still useful.  It does mean that there are quite likely ways to get around the limitations, say by using DMA memory-to-memory copy operation; but the thing that worries me wrt. embedded architectures is the stack.

I'd really want to have stack pointer arithmetic operations (assignment, addition and subtraction, push and pop) and stack pointer relative addressing modes to be compared against a pair of limiting registers –– even if it added an extra clock cycle to all stack-based instructions.  At least that way you would find out that when the device crashed due to stack overflow, that it indeed was due to stack overflow and not something else.  The software running on the device might not be able to do much besides let the user know somehow, and restart – or perhaps the interrupt can only occur after the access has already occurred –; but I am absolutely certain that for those of us humans that care why a crash occurred, the overhead and costs associated with this would be worth it.

I don't think I'm the only one who has wondered how to insert a stack pointer check to the preamble of a specific function or specific functions, on embedded architectures, just to be able to know whether at that point, the stack pointer looks sane enough to proceed.

[SiliconWizard]

My experiments thus far have shown that encoding the key in the pointer value does not really work.  You do want the instruction to specify the key, and not the address being referred to.

Wherever you encode the "key" wouldn't really matter IMO. There are drawbacks and benefits either way.

What I have in mind to be more flexible, but still more secure, would be to add a field in the "segment descriptor" (or equivalent) specifying which instruction(s) are allowed to access this particular memory block. Read, write, execute rights are common flags, but I don't think I have ever seen this: restricting access to some specific instructions.

Thus, you could allow access to some memory block only for some instructions, and not others.
For stack manipulation, having specific instructions (instead of just using general-purpose load/store instructions) would definitely help here. To avoid making the ISA too complex, it could just be a matter of encoding a flag in the load/store instructions telling if they are accessing a stack or not. Would just cost one bit.

[ataradov]

But auto variables are stored on the stack, and they should be accessed by regular instructions.

I feel like you are over complicating things that are not a real problem.

[DiTBho]

I feel like you are over complicating things that are not a real problem.

I do feel so. The same feeling. I mean, I wouldn't do it 

[DiTBho]

At least that way you would find out that when the device crashed due to stack overflow, that it indeed was due to stack overflow and not something else.

With my little 68hc11 I have a "memory segregation" unit for the stack slice (2Kbyte of 62Kbyte addressable, 2Kbyte are reserved).

It's a simple circuit attached to the address bus. It does the following:

Code: [Select]

is_stack_ok = (SP >= SP_begin) and (SP < SP_end);
if is_stack_ok is false ('0') it raises an interrupt to inform the CPU  about stack the overflow/underflow.

Unfortunately the 68hc11 doesn't have any separation between kernelspace and userspace, the stackpointer is physically the same register reloaded according to the working condition, if an application does something bad, there is no way to resume, but I added  a flip-flop with a LED, so if the CPU crashes on a program, I can visually see what happened.

The typical scenario is: d'oh, it just crashed. WTF !? Oh, see, the red segregation memory LED is on,  was there any issue with the stack? Really? Maybe too many nested function calls? Let's check it out ... 70% of times, a couple of interactions (sometimes many many more) later: problem solved.

No doubt it's wild, but it has worked well for a long time. The flip flop is reset by a GPIO or by reset 

[Nominal Animal]

I feel like you are over complicating things that are not a real problem.

I know; you've made it clear having devices crash does not bother you, as long as it does no harm to you personally.

[brucehoult]

Even the smallest commercial RISC-V CPU cores usually implement PMP (Physical Memory Protection) with typically 8 or 16 memory regions which can each be assigned Read/Write/eXecute protections for each of Machine/Supervisor (if it exists)/User modes. This is separate to and much lighter weight than MMU.

Hey? That's awesome! I had to pay extra money to buy MIPS32 commercial cores with PMP implemented. I really like to hear it's a default feature with RISC-V commercial cores

It's a standard option. It may or may not be a zero cost option. I have no idea.

If you go to the SiFive Core Designer at ...

https://scs.sifive.com/core-designer/customize/96d93240-cade-4c9e-9987-a12c8d15c9ad/

... and click "security" you'll see that you can adjust the number of PMP regions to any number from 1 to 16, or eliminate PMP entirely (which also removes User mode).

Do you save licensing cost by removing PMP and User mode? I don't know. Your chip will be smaller, certainly.

[DiTBho]

What I don't know how to implement

Why don't you write a Python simulator? So you can see if it works, and how good it goes 

(I said "Python" only because I do find it as one of the most comfortable and rapid development language, but it's just "me" ... ).

[ataradov]

It's a simple circuit attached to the address bus. It does the following:

Not going to work on ARM or any RISC. Compilers rarely actually update SP. They use SP-relative addressing. So SP itself would be in the range, but instruction accessing the memory would still access outside of the stack space.

This would catch instructions that implicitly use SP, like push and pop, but not much more.

[ataradov]

I know; you've made it clear having devices crash does not bother you, as long as it does no harm to you personally.

This is not true. There are already sufficient support in the hardware and software to catch stack overflows.

[SiliconWizard]

I feel like you are over complicating things that are not a real problem.

I know; you've made it clear having devices crash does not bother you, as long as it does no harm to you personally.

Well, to be honest, maybe I was going a little too far with my "per-instruction access rights", but I was like thinking out loud.

I do agree and think that certainly not enough has been done for software security. Now the "good" ideas are hard to come by.

[SiliconWizard]

It's a simple circuit attached to the address bus. It does the following:

Not going to work on ARM or any RISC. Compilers rarely actually update SP.

Ah, that's not true, at least on RISC-V, for which I have extensively worked with assembly. Although solely relying on checking SP is not completely robust indeed, the compilers I've used do update SP. At least with GCC, everytime the stack is being used (for local variables and/or register saving), it starts by emitting an instruction decreasing SP by the amount it needs, and then accesses the stack with offsets indeed, but only positive offsets. Even at the most aggressive optimization levels. At least that's what I've seen so far.

But, I agree this is compiler-dependent, and checking the register defined as SP in the ABI is not a 100% reliable way of handling this.

[brucehoult]

Yes, but to you and those who mentioned something similar: keep in mind what I said above: what you describe is memory protection. What I suggested was for code instrumentation (with stacks in mind here, but I do have a knack for code instrumentation anyway.) Those are two different things.

Agreed; that is also why I qualified it with "If you expand the idea".

The security aspect can obviously used for instrumentation (at a suitable granularity), by simply having the out-of-bounds access interrupt expand the region.  It is probably not useful to make it byte-granular, but it does cover all accesses to that segment.

you can define a memory area for a stack and protect it, but there's little way you can prevent some program to write outside of the stack area, when it means to write inside of it, if this 'outside' location is itself another memory area that is allowed to be written to.

That is precisely why the segmented memory model so intrigues me: because the "segment register" acts as the key to the address space, it does affect all accesses.

Sure. This was all done 40 years ago or more. Many minicomputers had this functionality. Data General ones, for example. And I think Pr1me. Probably others. HP? You can make loading the segment base and limit registers something only the OS can do, not the user program.

Such machines also tended to have "gates" for system calls. You didn't load a syscall number into a register and use a single syscall instruction -- you just did a normal function call into the OS address space. But because the caller and callee were in a different protection "ring", the call instruction would check that the address called held some special data structure specifying that it was an allowed entry point to the OS. These were rather complex and CISCy but you could achieve pretty much the same thing in a RISCy way by just requiring the first instruction of the entry point to be a special instruction indicating that it was allowed to be called. (We are getting some of the same ideas in modern CPUs as part of "control flow integrity" to prevent ROP and other security breaches)

The 386 provided basically all of this. And it was pretty much never used because existing operating systems and programming languages weren't built around using such things.

What I don't know how to implement, is any sort of automatic shrinking of such segments; or even how to instrument it.  Yes, you can track accesses, but only the process itself knows when the data in that segment is no longer needed; perhaps it knows that it will never need more than N bytes of stack, and uses a region beyond that as an extra scratchpad or something.

Most ABIs say that everything below the current stack pointer (or below a "red zone") can be arbitrarily nuked by the OS, by interrupts, by whatever. There are debugging tools that do this regularly. Boehm GC clears several KB of memory below the stack pointer at the start of every garbage collection, to prevent dead pointers being traced. I've never seen this cause a problem, and it's certainly a bug if it does.

So, you can on some regular basis clear the accessed and/or dirty bits on stack segment pages and some time later return any pages beow SP that haven't been used in that time period to the OS using mmap with MADV_DONTNEED or equivalent.

[brucehoult]

Thus, you could allow access to some memory block only for some instructions, and not others.
For stack manipulation, having specific instructions (instead of just using general-purpose load/store instructions) would definitely help here. To avoid making the ISA too complex, it could just be a matter of encoding a flag in the load/store instructions telling if they are accessing a stack or not. Would just cost one bit.

Having load/store instructions with a flag bit is exactly the same thing as having normal load/store and special load/store stack instructions. It's just a difference in how you write it in assembly language, not a difference in the binary encoding.

[SiliconWizard]

The 386 provided basically all of this. And it was pretty much never used because existing operating systems and programming languages weren't built around using such things.

Yes, I remember having studied the 386(+) protected mode, and it allowed pretty nice stuff. Actually, whereas the x86 ISA itself was pretty mediocre, the protected mode was not too badly thought out IMHO.

I was always baffled seeing how most OSs were not making good use of it (except a couple experimental OSs I had seen). Sure that would have required some serious changes, but that was not rocket science either. Oh well. Just thinking how long we've had to wait till Windows actually made use of the execute flag.

[SiliconWizard]

Thus, you could allow access to some memory block only for some instructions, and not others.
For stack manipulation, having specific instructions (instead of just using general-purpose load/store instructions) would definitely help here. To avoid making the ISA too complex, it could just be a matter of encoding a flag in the load/store instructions telling if they are accessing a stack or not. Would just cost one bit.

Having load/store instructions with a flag bit is exactly the same thing as having normal load/store and special load/store stack instructions. It's just a difference in how you write it in assembly language, not a difference in the binary encoding.

Oh yes I know. By that I was just meaning that the instructions themselves could otherwise be identical and thus there wouldn't be any overhead implementing this on a hardware level.

But, as was noted, this is a can of worms. Because most languages make use of stacks that can be accessed as regular memory, in particular through pointers, and thus there is no way to make this really work. Except if we completely change the programming model...

[brucehoult]

But auto variables are stored on the stack, and they should be accessed by regular instructions.

On modern machines with a sufficient number of registers, auto variables are stored in registers UNLESS they have their address taken.

If you run out of registers then some auto variables may be on the stack. The function that declares them knows this, and can use the special stack access instructions.

The difficulty is if the address is taken and passed to another function. Then the other function that uses the address has no way of knowing that special stack access instructions are needed.

This is a rather C-centric problem. Many other programming languages can't take the address of an auto variable.

In any case it's easily solved. The compiler knows which variables are affected and can store them on the heap instead of on the stack, with a malloc() at the start of the function and a free() at the end. This is probably a rare enough thing to be low overhead.

[Nominal Animal]

The 386 provided basically all of this. And it was pretty much never used because existing operating systems and programming languages weren't built around using such things.

I take it you never read the Speeding Up Thread-Local Storage Access report by A. Oliva and G. Araújo, 2005?  This is used by the Linux kernel and standard C library for thread-local storage, right now, on AMD64 – via the separate FS segment address space.

(And it is a separate address space, too.  The same offset to the FS segment refers to different memory, depending on the current thread doing the access, as the FS segment base address varies.  The protection features are not used.  The toolchain even has a dedicated relocation entry type (tpoff) for offsets to these objects.)

In particular,

Code: [Select]

static __thread int  foo;
int get_foo(void) { return foo; }
int *get_foo_addr(void) { return &foo; }
compiles to

Code: [Select]

get_foo:
    movl    %fs:foo@tpoff, %eax
    ret

get_foo_addr:
    movq    %fs:0, %rax
    addq    $foo@tpoff, %rax
    ret
where foo@tpoff is the 32-bit ELF-relocated TLS offset (@tpoff being the relocation type).  As you can see, address 0 relative to the FS segment contains the base address of the object in the standard address space.

[Nominal Animal]

I know; you've made it clear having devices crash does not bother you, as long as it does no harm to you personally.

This is not true. There are already sufficient support in the hardware and software to catch stack overflows.

That statement pair is evidence of my claim.

The support for catching stack overflows is based on heuristics.  It is not deterministic.  By the very definition, your "sufficient" can only mean "to the extent that I care".  I find the extent to which you care, lacking.

The existing support on architectures like AVR is limited to canaries.  Or does your "hardware and software" exclude AVR, too?  A single byte sized stack canaries have a one in 256 chance of not recording an overflow, regardless of whether the canary value is a fixed constant or not.  Perhaps you find those odds "sufficient"?  Multibyte canaries can reduce the probability, but not eliminate it.  Thus, heuristic, not deterministic.

Whatever the exact definitions to your words are, I definitely have observed a consistent attitude from you that it is not worth your time to consider "rarely" occurring problems, even when those problems cause a crash or reboot of the affected device.  I disagree.  I do fully acknowledge that your attitude makes much more business sense, is the one employers prefer, and is likely to lead to commercial success; while mine does not.

[brucehoult]

I haven't read that paper, but I'm well aware of the use of FS for thread local storage.

Other ISAs with more registers than i386's eight can just dedicate a general purpose register for this e.g. TP is register 4 in the standard RISC-V ABI. If I recall correctly, arm64 has a CSR that contains a pointer to thread-local storage and this is moved to a GP register in each function that needs it.

[ataradov]

Ah, that's not true, at least on RISC-V

So what is the problem overflowing it  from the other side? Or really any side you want with the code like this:

Code: [Select]

int foo(int a)
{
  volatile char zz[10];
  zz[a] = 1;
  return zz[a];
}

And the resulting assembly:

Code: [Select]

0000000000000000 <foo>:
   0: 1141                addi sp,sp,-16
   2: 081c                addi a5,sp,16
   4: 953e                add a0,a0,a5
   6: 4785                li a5,1
   8: fef50823          sb a5,-16(a0) // OOPS
   c: ff054503          lbu a0,-16(a0)
  10: 0141                addi sp,sp,16
  12: 0ff57513          zext.b a0,a0
  16: 8082                ret

Call this with foo(100) or foo(-100) and it will overwrite the memory well outside the stack, while SP is perfectly fine.

And this is the most common way stack overflows happen, so any system that doers not catch this is not worth considering.

[brucehoult]

Wow gcc could use some improvement there.

The second instruction is unnecessary, as the 2nd instruction could just be add a0,a0,sp and change the offsets on sb and lbu to the more natural 0. And the zext.b is completely unnecessary as the byte was loaded unsigned.

I guess you compiled this for rv64 as I got -12 offset on the sb/lbu in rv32.

Was it done with the system compiler on a BeagleV/Unmatched?