Re: Capabilities, Anybody?

On 3/10/2024 11:24 AM, Theo Markettos wrote:

MitchAlsup1 <mitchalsup@aol.com> wrote:

BGB wrote:
>

On 3/9/2024 1:58 PM, Robert Finch wrote:

On 2024-03-09 1:56 p.m., BGB wrote:

On 3/9/2024 9:09 AM, Scott Lurndal wrote:

mitchalsup@aol.com (MitchAlsup1) writes:

<snip>

>
For Femtiki OS, I have a single object describing an array of values.
For instance messages which are small objects, are described with a
single object for an array of messages. It is too costly to use an
object descriptor for each message.

>

For a CHERI like approach, one would need a tag of 1 bit for every 16
bytes of RAM (to flag whether or not that RAM represents a valid
capability).

>

For the combination of RAM sizes and FPGAs I have access to, this is
non-viable, as I would need more BRAM for the tag memory than exists in
the FPGAs.

 If you have ECC RAM on your FPGA board you could use the ECC bits for tags.
Otherwise a tag cache is another way.  The L1s and L2s carry tags (ie 129
bit datapath), but you just put the tag cache on the front of your DRAM.
 

The RAM on my FPGA boards only provides a 16-bit bus interface.
If one spent the "big money" on something like a Nexys Video, IIRC, this is 32-bit RAM.

Yes, indeed, not viable. Now imagine a page of those, and now you have
to write out 4096 bytes and 2048-tag-bits onto a disk with standard
sectors......

 Our swapping implementation keeps the tag bits in RAM, while the page is
swapped out.  Eventually you need to swap out a page of tag bits, but that's
much less common.
 

Yeah. In any case, tag bits need to be somewhere where the page-swapping code has access to them...

In effect, this will mean needing another smaller cache which is bolted
onto the L2 cache or similar, whose sole purpose is to provide tag-bits
(and probably bounce requests to some other area of RAM which contains
the tag-bits memory).

>
Denelcor HEP had tag-like-bits and all the crud they bring (but they were
used as locks instead of tags).
>

>
As I see it, "locking things down" would likely require turning things
like "malloc()/free()", "dlopen()/dlsym()/...", etc, into system calls
(and generally giving the kernel a much more active role in this
process).
>

I think this may not be necessary, but I have to read some more. The
capabilities have transfer rules which might make it possible to use
existing code. They have ported things over to Riscv. It cannot be too
mountainous a task.
>

>

You can make it work, yes, but the question is less "can you make it
work, technically", but more:
Can you make it work in a way that provides both a fairly normal C
experience, and *also* an unbreakable sandbox, at the same time.

 The C experience is fairly normal, as long as you are actually playing by
the C rules.  You can't arbitraily cast integers to pointers - if you plan
to do that you need to use intptr_t so the compiler knows to keep the data
in a capability so it can use it as a pointer later.
 Tricks which store data in the upper or lower bits of pointers are awkward.
Other tricks like XOR linked lists of pointers don't work.  This is all
stuff that's pushing into the 'undefined behaviour' parts of C (even if C
doesn't explicitly call it out).
 

The model of C that I consider normal arguably has a fair bit of UB.

Changes in a 6M LoC KDE desktop codebase were 0.026% of lines:
https://www.capabilitieslimited.co.uk/_files/ugd/f4d681_e0f23245dace466297f20a0dbd22d371.pdf
 Depends what you mean by 'unbreakable sandbox': this is compiling code with
every pointer being a capability, so every memory access is bounds checked.
 Sandboxing involves dividing code into compartments; that involves some
decision making as to where you draw the security boundaries.  There aren't
good tools to do that (they are being worked on).  CHERI offers you the
tools to implement whatever compartmentalisation stategy you wish, but it's
not quite as simple as just recompiling.
 

Seems so.
Looks like, at a minimum, things like "malloc()" need to be modified to be aware of the capability system.

And here the answer is essentially <wait for it> no.
>

My skepticism here is that, short of drastic measures like moving malloc
and libdl and similar into kernel space, it may not be possible to keep
the sandbox secure using solely capabilities.

>

ASLR could help, but using ASLR to maintain an image of integrity for
the capability system would be "kinda weak".

>
How do you ALSR code when a latent capability on disk still points at
its defined memory area ? Yes, you can ALSR at boot, but you can use
the file system to hold capabilities {which is something most capability
systems desire and promote.}

 Why would you want to ASLR?  ASLR is to prevent you guessing valid addresses
for things so you can't craft pointers to them.  CHERI prevents you crafting
pointers to arbitrary things in the first place.
 

It stops you from crafting pointers directly...
But, that is not the question, it is what happens if the program manages to steal a capability that gives it access to something that it shouldn't have access to, and then can use this capability to access something else.
If you ASLR things, this may make this latter scenario more difficult (and, if it does happen, one is merely back to the situation on current systems).
Say, for example, we have an ABI where, say:
Function pointer points to a 32-byte location, containing two capabilities:
   The executable code to be run;
   A capability representing the GOT to be used by the callee.
Here, I am assuming an FDPIC style ABI, don't actually know what ABI design they are using (my quick look didn't find much, but the normal ELF ABI isn't likely to work within a pure capability system, so...).
And, then someone realizes, say:
The malloc function has a GOT, and say, entry 31 has access to the array of heap capabilities.
Then, say, the program does something like, say:
   void **forbidden_array;
   forbidden_array=((void ***)malloc)[1][31];
Or, say, for sake of "blessing pointers" (for int->pointer casts), if there is a:
   void *__blessify_qi2c(intptr_t a);
And, if "blessify" has access to a global capability (at index 5):
   void *very_bad;
   very_bad=((void ***)__blessify_qi2c)[1][5];
But, if such things are possible, capabilities can't be the sole line of defense.
Though, ideally, the ABI would also include mechanisms to mitigate the effectiveness of these sorts of attack vectors (likely also needing to involve the use of random number generators).
Luckily, ASLR is "virtually free", and so there isn't a good reason to not use it, if there is still a possibility of holes in the armor.

One could ask though:
    How is my security model (with Keyrings) any different?

>

Well, the partial answer mostly is that a call that switches keyrings is
effectively accomplished via context switches (with the two keyrings
effectively running in separate threads).

>

So, like, even if the untrusted thread has a pointer to the protected
thread's memory, it can't access it...

>

Though, a similar model could potentially be accomplished with
conventional page-tables, by making pseudo-processes which only share
parts of their address space with another process (and the protected
memory is located in the non-shared spaces, with any calls between them
via an RPC mechanism).

>
Capability manipulation via messages.

 That's the microkernel setup: the software running in system mode holds
the privilege to alter access control (via page tables), so any time you
want to change that you have to ask the system (microkernel or whatever) to do
so.  That's slow, in particular TLB manipulation (invalidation and
shootdowns).  CHERI allows you to manipulate them in userspace without
having to call out to the kernel. Additionally it is finer grained than page
granularity.
 Some experimental OSes have done things with manipulating page tables from
userspace processes which avoids syscall overhead but not TLB costs - and it
probably depends on the architecture whether you can do TLB invalidations
from userspace.
 

It is a question of what can be done without compromising security.
For example, I had considered mechanisms to change keyrings without context switches, but they fell short of "acceptably secure" as I saw it.
Some mechanisms would have been subject to the possibility of memory tinkering and/or using brute-forcing strategies to crack the bit-shuffling of the keys.
Had added a mechanism which allowed for a "controlled" transient privilege escalation to use certain instructions (for sake of being able to update the keyring or similar).
In this case, pages would be designated in a special "Secure Execute" mode, with special SXENTER/etc instructions. If control was in one of these pages, then one would be allowed to use SXENTER to enter "Superuser Mode" (while the CPU is still otherwise flagged as Usermode), and use certain privileged instructions.
If no SXENTER was used, the superuser instructions couldn't be used, and if code did not return to normal usermode before transferring control out of this memory, the CPU will fault.
But, then noted that, assuming the secure-execute mechanism worked, there was still an issue if one could trick the "more privileged" code into jumping to a pointer injected by hostile code (such as via stack corruption, other sorts of non-local control transfers, etc). If both are running as the same logical task, this sort of attack is much more viable.
The use of explicit context switches did at least sidestep a lot of these sorts of vectors.
More so, if one limits which memory is shared, and what can be done in this shared memory (for example, all "GlobalAlloc" memory being non-executable, etc).
Similarly, use of ASLR to prevent any sort of "widgets" from being used, and the experimental bounds-checking feature could mostly eliminate buffer overflows (with in this case, stack-arrays, global arrays, and malloc'ed memory, using bounds-checked forms).
It mostly works, but is not entirely transparent (as in, some code will require modifications to work correctly).

Had considered mechanisms which could pull this off without a context
switch, but most would fall short of "acceptably secure" (if a path
exists where a task could modify its own KRR or similar, this mechanism
is blown).

>
>

My bounds-checking scheme also worked, but with a caveat:
It only works if code does not get "overly clever" with the use of pointers.

>
Which no-one can trust of C programs.

 A lot of modern software is well behaved (see figure above).  Particular
software like JIT compilers can be more awkward - ideally you would really want
the JIT compiler to emit capability-aware code.  You can still run generated
aarch64/rv64 non-capability code, but without the benefit of capability
checks.
 

Yeah.
Well behaved software is not really the concern, the possibility of actively hostile software is.
But, ideally, one can stop hostile software from doing its thing, without needlessly hindering non-hostile software (such as VMs and JIT compilers).

So, it worked well enough to where I was able to enable full
bounds-checking in Doom and similar, but was not entirely transparent to
some of the runtime code. If you cast between pointers and integers, and
manipulate the pointer bits, there are "gotchas".

 That's the kind of thing that fall down: software being 'clever', where it
doesn't need to be.  I get the sense Doom's primary purpose in life was
being 'clever' in order to be fast on a 386.
 

A lot of the code I am dealing with has similar sorts of issues.
Simply disallowing certain coding practices because they are not compatible with the model is not ideal.
But, then if one allows mechanisms to allow these practices (with some extra checks to verify the operation is "sane"), this creates an attack surface.
I guess, another related question is if one is only trying to secure C code (a slightly easier problem), or potentially hostile assembler or machine code (another issue). My assumptions had also included the possibility of hostile ASM code.
Machine code will have an easier time doing things that involve poking holes in the ABI, etc.

Gee, if only we had trained programmers to avoid some of the things we
are now requiring new languages to prevent.....

 If only we could rewrite all the software out there in memory-safe
languages... then we'd have twice as much software (and more bugs).
 

Possibly, but only if one can trust that the code is compiled with a safe/trusted compiler of that language; or security enforcement via a VM (like in the JVM or .NET).
Though, even if the VM is memory-safe, this still doesn't prevent other types of attacks (like, in the era where VBScript viruses were a bane of Windows users).

Either pointer<->integer casting would need to be disallowed, or (more
likely), turned into a runtime call which can "bless" the address before
returning it as a capability, which would exist as another potential
attack surface (unless, of course, this mechanism is itself turned into
a system call).

>
>

OTOH:
If one can't implement something like a conventional JavaScript VM, or
if it takes a significant performance hit, this would not be ideal.

>
Going for 2 in one post !!

 We've had the DukTape Javascript interpreter working for CHERI for a while.
Work is under way to port Chromium and V8 - that's a much bigger project,
just because Chromium is a huge piece of software (and we're running on
FreeBSD, which is not a platform that Chrome supports building for).  The
work in V8 is to get it to implement the JS object model using CHERI
instructions as part of its generated code.
 

I was thinking, say, of one built on the NaN boxing approach or similar.
Efficiently mapping NaN boxing over to capabilities would be more of a problem.
In my case at least, there is an "ABI Approved" tagged pointer system, with the bounds-checked pointers (and possible capabilities, if I go this direction) being built on top of this.
But, asking VMs to change their pointer tagging model to fit the target is a bit of an ask.

Though, on my side of things, it is possible I could revive a modified
form of the 128-bit ABI, while dropping the VAS back down to 48 bits,
and turn it into a more CHERI-like form (with explicit upper and lower
bounds and access-enable flags, rather than a shared-exponent size and
bias scheme).
>

Yeah, IMO explicit upper and lower bounds would be better even though it
uses more memory. The whole manipulation of the bounds is complex. I
sketched out using a 256b capability descriptor. Some of the bits can be
trimmed from the bounds if things are page aligned.

 We originally started out with a 256-bit capability with explicit base and
top - this was to try things out simply so as not to prematurely optimise.
One early finding was that we needed to support capabilities being out of
bounds, as long as they aren't dereferenced out of bounds - software
sometimes saves a pointer that's before or after the object, before then
bringing it back in bounds when dereferencing it.
 This is something the 128-bit compressed capability format supports, which
compresses the bounds a bit like floating point.  This imposes certain
limits on bounds granularity, but they haven't been a problem in practice -
memory allocators tend to allocate objects in aligned chunks anyway (eg ask
for a 128MiB block and it'll probably be page aligned).  The pointer is always
byte aligned.
 

OK.
The bounds-checking scheme I had used thus far has a similar property, but is "very approximate" in its current forms, and does not support pointers going significantly out of bounds.
The scheme I had been using for 96-bit addresses was:
* (    127)=ReadOnly
* (126:124)=CrudeExp
* (123:112)=Bias
* (111: 64)=Address (95:48)
* ( 63: 60)=Tag (0011)
* ( 59: 48)=Size
* ( 47:  0)=Address(47:0)
Where, in this case, the exponent (in log2) was:
   Exp = CrudeExp*2+4
No hidden bits in this case.
The scheme used for smaller pointers differed:
* (63:60)=Tag (0011)
* (59:56)=Bias
* (55:51)=Exp
* (50:48)=Size
This time using smaller bounds with a log2 exponent, with the size encoded with a hidden bit.
The 96-bit scheme was the older of the two, with a scheme being designed to work with 64-bit pointers being developed as the use of 128-bit pointers seemed too heavyweight.
It may make sense to modify the 128-bit encoding to have slightly smaller Size and Bias fields, direct exponent, and have a few bits for access control.
Say:
* (127:123)=Exp
* (122:112)=Bias
* (111: 64)=Address (95:48)
* ( 63: 60)=Tag (0011)
* ( 59: 58)=Attrib
* ( 57: 48)=Size
* ( 47:  0)=Address(47:0)
Attrib:
   00: Read/Write
   01: Read-Only
   10: -
   11: -
But, as noted, dropping down to a 48-bit address would allow a lot more bits for metadata.

Theo