CToPtr returning nonsense

[brooksdavis]

While trying to hunt down a problem in memcpy_c, I'm seeing this in the trace:

0xffffffff80535fb8:  csetdefault        c28
    Write C00|v:1 s:0 p:0007807d b:0000000000000000 l:0000010000000000
             |o:0000000000000000 t:0 
...
0x000000016062884c:  cfromptr   c1,c0,s0
    Write C01|v:1 s:0 p:0007807d b:0000000000000000 l:0000010000000000
             |o:0000000161000018 t:0
0x0000000160628850:  csetbounds c3,c1,a2
    Write C03|v:1 s:0 p:0007807d b:0000000161000018 l:00000000000fffc7
             |o:0000000000000000 t:0
0x0000000160628854:  cfromptr   c1,c0,a1
    Write C01|v:1 s:0 p:0007807d b:0000000000000000 l:0000010000000000
             |o:0000000160e0d518 t:0
0x0000000160628858:  csetbounds c4,c1,a2
    Write C04|v:1 s:0 p:0007807d b:0000000160e0d518 l:00000000000fffc7
             |o:0000000000000000 t:0
0x000000016062885c:  ld t9,5824(gp)
    Memory Read [00000001606662b0] = 000000016062b510 
    Write t9 = 000000016062b510   
0x0000000160628860:  jalr       t9
    Write ra = 0000000160628868
0x0000000160628864:  move       a0,a2
    Write a0 = 00000000000fffc7   
0x000000016062b510:  beqz       a0,0x16062b5b8
0x000000016062b514:  cgetbase   v0,c3
    Write v0 = 0000000161000018
0x000000016062b518:  cgetoffset at,c3
    Write at = 0000000000000000
0x000000016062b51c:  dadd       v0,v0,at
0x000000016062b520:  cgetbase   v1,c4
    Write v1 = 0000000160e0d518
0x000000016062b524:  cgetoffset at,c4
0x000000016062b528:  dadd       v1,v1,at
0x000000016062b52c:  andi       t4,v0,0xf
    Write t4 = 0000000000000008   
0x000000016062b530:  ctoptr     v0,c0,c3
    Write v0 = fffffffe9effffe8   

It appears CToPtr is producing a completely wrong value (it looks like a bit flipped version of C3's virtual address)

[staceyson]

Yeah, it is returning the two's complement of 0x161000018 (or 0xfffffffe9effffe8) because of the computation of: v0 = c0.base + c0.offset - c3.base = 0 + 0 - 0x161000018 = -0x161000018
So should it actually be 0x161000018?

[brooksdavis]

I think so.

[staceyson]

Adding the email conversation on this...

On 22 Jul 2016, at 19:11, Brooks Davis brooks.davis@sri.com wrote:
On 7/22/16 09:40, Stacey Son wrote:

Hi All:

Currently the spec for CToPtr states the pointer (rd) is computed as follows:

rd ← (cb.base + cb.offset − ct.base) mod 2^64

This is only true if:

(1) cb.base != ct.base. If so, then rd ← 0. (This is not specified in the pseudo code but in the description.)

I don't think this makes sense. if (cb.base == ct.base) then rd <- cb.offset is the behavior I'd want. >I wonder if this language is left over from a previous revision.
(2) cb != null capability (or, more generally by the pseudo code, cb.tag != 0). If so, then rd ← 0.

The above is in the spec. What is missing is:

(3) (cb.base + cb.offset) >= ct.base. In the case of (cb.base + cb.offset) < ct.base, rd ← (ct.base - cb.base - cb.offset) mod 2^64?

I think (cb.base + cb.offset < ct.base || cb.base + cb.offset > ct.base + ct.offset) should produce rd <- 0. Otherwise you need to perform those checks before deciding if it's safe to use CToPtr. I'd also >be tempted to add if ct.base + ct.length > ct.base + ct.offset then rd <- 0. Of course, such an >instruction doesn't seem very RISC-flavored.

The invariant that we want is:

Assuming that address 0 is inaccessible, any MIPS load/store of CToPtr $Cx, $C0 will give the same result as CHERI load/store of $Cx.

This means that:

• Any untagged capability must give 0
• Any capability that can not be wholly represented within $c0 (or whatever the base address is) must give 0.

The compiler will substitute (ld $x) for (cld (cfromptr $x, $c0)) currently (this is important for GOT accesses). This is safe, because it’s not possible for the result of the cfromptr to have different permissions to the $c0. Even with these invariants, it’s not quite safe to do the converse, because the capability given to ctoptr may have different permissions from $c0, but the MIPS load/store will use the $c0 permissions and not the source ones and I don’t think that there’s any way of avoiding that.

David

[staceyson]

Maybe the pseudocode for CToPtr should be updated in the CHERI ISA spec to be something like the following:

if register_inaccessible(cb) then
    raise_c2_exception(exceptionAccessSystem, cb)
else if register_inaccessible(ct) then
    raise_c2_exception(exceptionAccessSystem, ct)
else if not ct.tag then
    raise_c2_exception(exceptionTag, ct)
else if not cb.tag then 
    rd ← 0
else if ((cb.base + cb.offset) < ct.base) || ((cb.base + cb.offset) > (ct.base + ct.length)) then
    // capability that can not be wholly represented within ct
    rd  ← 0
else if (ct.base > (cb.base + cb.offset) then
    rd  ← (ct.base - cb.base - cb.offset) mod2^64
else
    rd ← (cb.base + cb.offset − ct.base) mod2^64 
end if

@rwatson @michael-roe @davidchisnall

[staceyson]

@brooksdavis 43ab4c9 implements the above. Please check it with your test and let me know if this helps.

[brooksdavis]

Shouldn't this line:

else if ((cb.base + cb.offset) < ct.base) || ((cb.base + cb.offset) > (ct.base + ct.length)) then

be

else if ((cb.base + cb.offset) < ct.base) || ((cb.base + cb.offset + cb.length) > (ct.base + ct.length)) then

Also, the next line can't happen.

I also wonder if there should be a:

else if (cb.offset < 0 || cb.offset > cb.length) then
    rd  ← 0

[staceyson]

Yes,

else if (ct.base > (cb.base + cb.offset) then
    rd  ← (ct.base - cb.base - cb.offset) mod2^64

can't happen.

Of course, this implies that your example above would return 0 instead of 0x161000018.

[staceyson]

I wonder if the "capability that can not be wholly represented within ct" check shouldn't be something like:

cb_cursor = (cb.base + cb.offset) mod 2^64
cb_top = (cb.base + cb.length) mod 2^64
ct_top = (ct.base + ct.length) mod 2^64
[...]
else if (cb.base < ct.base  ||   // cb's "bottom" is below ct's
            cb_top > ct_top ||  // cb's "top" is above ct's
            cb_cursor < ct.base ||   // cb's cursor is currently below ct's bottom.
            cb_cursor > ct_top)  //cb's cursor is currently above ct's top.

Of course, this doesn't consider the cases where addition mod 2^64 wraps.

[brooksdavis]

I think we should only allow cb where the cursor is in bounds. If that's the case than I think no mod is required and overflow can't happen except where cb or ct covers the whole address space (which I now can't remember how we represent).

[jonwoodruff]

All,
I'm trying to think through the implications of the new semantics for this
instruction. I believe this instruction requires more decoded fields than
any other instruction. We need the decoded top and bottom of the
capability we are trying to convert to a pointer and need to bounds-check
both against the C0 capability. There may be a trick for comparing the
offset and the length, but as the two capabilities can have different
exponents, I'm not sure there is a good optimisation here. As doing the
wrong thing doesn't actually break the security model, can we get most of
the benefit by just checking that the pointer value is in-bounds?

-Jon

On 28 July 2016 at 23:55, Brooks Davis notifications@github.com wrote:

I think we should only allow cb where the cursor is in bounds. If that's
the case than I think no mod is required and overflow can't happen except
where cb or ct covers the whole address space (which I now can't remember
how we represent).

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
#14 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AGSnRyaKlnzvSWVnx-ZwdqP55g2-T0Y7ks5qaTNjgaJpZM4JPMh8
.

[davidchisnall]

Just checking that the virtual address is in-bounds means that software then needs to do all of the subsequent checks. I'd much rather that the instruction took two cycles than that we had to rely on the programmer doing something a lot more than a null check after the cast.

[jonwoodruff]

Maybe this isn't the place, so we should feel free to make a more general
thread, but what is the case in normal use where we have an in-bounds
pointer with out-of-bounds limits that should be converted to a null
pointer so that the program can continue to operate normally?

-Jon

On 29 July 2016 at 10:26, davidchisnall notifications@github.com wrote:

Just checking that the virtual address is in-bounds means that software
then needs to do all of the subsequent checks. I'd much rather that the
instruction took two cycles than that we had to rely on the programmer
doing something a lot more than a null check after the cast.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
#14 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AGSnRzCZewblMla6amOlof9fcQ1_yJs8ks5qacc5gaJpZM4JPMh8
.

[davidchisnall]

The instruction is used when you cast a __capability void* x to a void* y. The assumption for the programmer is that either any use of x that would succeed would also succeed for y or none of them would. The none case is easy to check with a null check. If I get a __capability void * and I want to cast it and be able to use it safely, then I must check that the length of $gdc + y is greater than or equal to the base plus length plus offset of x. I must also check that x doesn't have any permissions that $gdc doesn't have. I'll need to do that in all user code that performs a cast, because otherwise we can't safely use y. Having an instruction that takes two cycles is preferable to having half a dozen instructions that each take one cycle.

[jonwoodruff]

Am I right in understanding that this programming model implies that the programmer is using capabilities explicitly and that he needs to be aware of the span of his DDC relative to his other capabilities? In this context, have we encountered objects partially overlapping with DDC that eventually drifted out of bounds? Also, I assume when you mean "safely", you mean that it might throw an exception in the future, as memory safety would not be violated. What would the program do if it attempts a cast that fails? Is this not an exceptional case?

…

-Jon

[davidchisnall]

Also, I assume when you mean "safely", you mean that it might throw an
exception in the future, as memory safety would not be violated.

If the __capability void* comes from somewhere else, then the attacker may be able to trigger the code that they're invoking to raise an exception, which can have security implications.

What
would the program do if it attempts a cast that fails? Is this not an
exceptional case?

Expecting programmers to handle null checks is not unreasonable - they already exist for the most part. Similarly, if a programmer has a pointer to a struct and safely accesses the first field, then they may safely assume that it's possible to access the second. If this fails, then the code will leave data in an undefined state (particularly as the compiler is free to modify the order of non-interfering loads / stores via a pointer if there are not explicit atomic operations), which may also have security implications.

[jonwoodruff]

Do we also expect the cursor to be in-bounds of DDC? This one would
introduce a 3rd bounds check.

This is seeming to me like it's turning into a very expensive instruction
for subtle and non-security-critical benefits, but that's coming from a
hardware guy. Is trying to help a programmer infer if a cast of a pointer
might be unusual not a bit beyond what we need to support in hardware?
Surely an attacker could just send over some other malformed something to
cause an exception? The CToPtr is basically amplifying the rights of a
capability, so he could send any capability he likes with a pointer way out
of bounds that would be in-bounds to DDC. The original bounds would be
lost in CToPtr and you could cause the recipient of the call to access
memory he didn't intend to. I'm sure there's lots of other issues, but the
question is, is a source capability that is bigger than DDC really such a
unique threat model that it needs special hardware support?

-Jon

On 29 July 2016 at 11:04, davidchisnall notifications@github.com wrote:

Also, I assume when you mean "safely", you mean that it might throw an
exception in the future, as memory safety would not be violated.

If the __capability void* comes from somewhere else, then the attacker
may be able to trigger the code that they're invoking to raise an
exception, which can have security implications.

What
would the program do if it attempts a cast that fails? Is this not an
exceptional case?

Expecting programmers to handle null checks is not unreasonable - they
already exist for the most part. Similarly, if a programmer has a pointer
to a struct and safely accesses the first field, then they may safely
assume that it's possible to access the second. If this fails, then the
code will leave data in an undefined state (particularly as the compiler is
free to modify the order of non-interfering loads / stores via a pointer if
there are not explicit atomic operations), which may also have security
implications.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
#14 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AGSnR707Gd_6mYi-e-YId4_uyGJEla9dks5qadAfgaJpZM4JPMh8
.

[davidchisnall]

Do we also expect the cursor to be in-bounds of DDC?

No, I'd expect to simply return 0 for an out-of-range offset.

Is trying to help a programmer infer if a cast of a pointer might be unusual not a bit beyond what we need to support in hardware?

If we do not have the invariants that make sense to the programmer then we need to:

• Explicitly state what they are
• Write detailed programming guidelines describing why we don't have these invariants and how to do the safe thing
• Make sure that people writing C don't write buggy code

I would have a lot more confidence in expecting programmers to write safe code if the instructions are 'always do a null check after casting from a __capability-qualified pointer than if they are 'do a bunch of complicated and error-prone checks every time you cast from a __capability-qualified pointer'. We don't need to do this in hardware, but if we don't do it in hardware then the compiler is going to need to insert a very long sequence of instructions for every single cast to give the programmer-expected behaviour. That doesn't seem very much in keeping with the philosophy of an ISA designed for compiler use.

[jonwoodruff]

To clarify, "return 0" means we have to check in hardware if it is in
bounds and then decide to return 0, right? And the other two cause
exceptions? If so, that still comes out to three bounds checks.

What would be the consequences of only checking if the casted pointer is
dereferenceable in DDC, returning NULL otherwise, and not doing the extra
checks in software? We would lose the guarantee that the whole original
object is reachable within DDC. There is no guarantee of whole-object
reachability in non-capability code in general as the hardware doesn't know
about object sizes in non-capability code. Is it fair to say that you're
just leaving safe capability mode so you wouldn't expect object-level
guarantees?

-Jon

On 29 July 2016 at 11:50, davidchisnall notifications@github.com wrote:

Do we also expect the cursor to be in-bounds of DDC?

No, I'd expect to simply return 0 for an out-of-range offset.

Is trying to help a programmer infer if a cast of a pointer might be
unusual not a bit beyond what we need to support in hardware?

If we do not have the invariants that make sense to the programmer then we
need to:

• Explicitly state what they are
• Write detailed programming guidelines describing why we don't have
  these invariants and how to do the safe thing
• Make sure that people writing C don't write buggy code

I would have a lot more confidence in expecting programmers to write safe
code if the instructions are 'always do a null check after casting from a
__capability-qualified pointerthan if they are 'do a bunch of complicated
and error-prone checks every time you cast from a__capability`-qualified
pointer'. We don't need to do this in hardware, but if we don't do it
in hardware then the compiler is going to need to insert a very long
sequence of instructions for every single cast to give the
programmer-expected behaviour. That doesn't seem very much in keeping with
the philosophy of an ISA designed for compiler use.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
#14 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AGSnR4dq0Ex4mYSx-ABiLJhUMIekh98Aks5qadrjgaJpZM4JPMh8
.

[davidchisnall]

To clarify, "return 0" means we have to check in hardware if it is in
bounds and then decide to return 0, right? And the other two cause
exceptions? If so, that still comes out to three bounds checks.

We should only get exceptions from ctoptr if it's a register that we aren't allowed to access or if it's sealed (I'd prefer to get 0 for a sealed pointer too, but we're still throwing exceptions for a bunch of stuff where it's more convenient for the programmer to get a testable failure).

What would be the consequences of only checking if the casted pointer is
dereferenceable in DDC, returning NULL otherwise, and not doing the extra
checks in software?

What do you think dereferencable mean? Generally, it means that you can access the object that the pointer points to, not simply that you can access the first byte (of word, or whatever) of the object.

We would lose the guarantee that the whole original object is reachable within DDC.

Precisely.

There is no guarantee of whole-objectreachability in non-capability code in general as the hardware doesn't know about object sizes in non-capability code

Yes there is, because in non-capability code all objects are reachable. You are never in the situation where you can only access half of an object.

Is it fair to say that you're just leaving safe capability mode so you wouldn't expect object-level
guarantees?

No, because the idea that you can access half of an object but not the other half is a brand new thing that CHERI makes possible and we shouldn't have that by accident.