Re: [friam] Representing tag bits in partitioned hardware cap systems

Cute idea, but I find it impossible to believe that the complexity +
the overhead for the false hit table + worst case behaviour gives any
advantage over the tagging scheme.

Which we've already shown is essentially zero overhead anyway.

Note that for existing code that doesn't use caps, CHERI has
essentially no overhead (the tags are free and all standard
instructions use the default capability register [CR0] - so there's
potentially a tiny overhead when context-switching into such code
loading CR0).

Also note that in exchange for the "overhead" of tags, CHERI drops a
whole pile of crap used in conventional MMUs that really does have an
overhead. :-) (An MMU is still needed for virtual memory, of course,
but it is no longer part of the protection scheme).

On 30 December 2014 at 19:12, Daira Hopwood <[email protected]> wrote:
> Consider a partitioned capability system --one that enforces a type distinction
> between capability representations and data-- using hardware tagged memory.
> Examples include CHERI [Anderson], the M-Machine [CKD1994], etc.
>
> This kind of system requires tags to be maintained on both internal values (lines
> in cache, registers, etc.) and in external memory. A purported disadvantage of this
> approach, which I've heard several times recently from processor designers who seem
> to be otherwise quite conducive to supporting capabilities, is the issue of how tags
> can be efficiently represented in external memory.
>
> The argument is that, given pervasive assumptions in existing code about power-of-2
> sizes for words and pages, and the fact that external DRAM organisation is also
> based on power-of-2 sizes, that we cannot store the tags next to the words they are
> associated with; and that if we store tags in a separate side table, then memory
> access bandwidth and latency will be unacceptably increased.
>
> (I would argue that the CHERI benchmarks [CHERI2014] show that this overhead is
> perfectly acceptable even for a straightforward implementation of a side table. But
> there is nevertheless resistance to *any* overhead, especially for existing code that
> wasn't explicitly written to use capabilities.)
>
> Maintaining tags for internal values, OTOH, is straightforward. Several architectures
> store metadata with internal values anyway, e.g. to support speculation.
>
> Today I had an idea about how to represent the tag bits in external memory at minimal
> cost in memory bandwidth and latency.
>
> Assumptions:
>  * Cap representations have a fixed size, say S bytes. [Note 1]
>  * Cap representations can appear anywhere in memory, but must be aligned to a
>    multiple of S bytes.
>  * Every S-byte aligned value, both internally and in external memory, is logically
>    tagged with a single bit indicating whether it is a cap representation.
>  * The size of a cache line (as loaded from external memory) is a multiple of S bytes.
>
> These are the same assumptions made by CHERI.
>
> To make capabilities unforgeable, we need to clear the capability tag when data is
> stored over any part of a capability representation.
>
> It is also possible to make capability representations opaque by clearing the whole
> S bytes when data is stored over them, by preventing them from being loaded into
> data registers, and by requiring them to be handled only using capability-specific
> operations. This isn't required for unforgeability and might not be supported by a
> given capability system, e.g. CHERI does not enforce opaqueness. (I will not make
> any assumptions below about whether the system enforces opaqueness.)
>
> Here's the idea:
>
> Suppose that a capability representation has a bit pattern that occurs rarely in
> non-capability data. With sufficient control over the architecture design, we can
> guarantee that this pattern does not match any valid non-capability pointers,
> valid instruction encodings, valid Unicode string encodings, nor any outputs of
> floating point operations [Note 2]. We can also choose a pattern that rarely occurs
> in practice for integer data.
>
> We can also potentially make the pattern dependent on the location, i.e. virtual
> address, of the cap representation [Note 3].
>
> Then, when storing data to memory, we only need to keep track of tags for S-byte
> values that match the pattern, using a sparse table. (We can choose whether the
> table records capabilities or false matches; I'll assume that it records false
> matches below.) We only need to access this table when a cache line containing the
> pattern in any of its S-byte-aligned components is read from or written to external
> memory.
>
> Access to the table must be serialized across cores to avoid race conditions. In
> particular, a write to the table and a write to the corresponding S-byte value in
> external memory must appear to be atomic to all cores.
>
> Advantages:
>  * Memory bandwidth and latency overhead of tags is almost negligable for common
>    usage patterns.
>  * Standard external memory with power-of-2 organisation can be used.
>  * If the table stores only false matches, its size is expected to be small --
>    it might even have no entries at all if the pattern is rare enough and there
>    are no attacks (see below).
>  * Recognizing the pattern is simple in hardware, and is not on any fast path
>    (it's possible to trap to software or microcode to do the table accesses).
>
> Disadvantages:
>  * The pattern reduces the number of bits available for encoding the actual
>    capability representation, for a given size S.
>  * It is possible for an attacker to deliberately construct data that matches the
>    pattern. This implies that:
>     a) the total number of entries in the false-match table might have to be as large
>        in the worst case as the number of S-byte units of physical memory.
>     b) if large numbers of entries in the false-match table are handled inefficiently,
>        there may be denial-of-service attacks either on the system as a whole, or on
>        components that accept data from an attacker.
>     c) there may be side-channel attacks where the attacker can gain an advantage
>        from observing, via timing, whether data matching the pattern was used.
>
> The overhead in the capability representation is unlikely to be a serious problem.
> The important issue for adoption is that we reduce overhead for programs not written
> to use capabilities, even at the expense of some (small) additional overhead for
> programs that use them extensively. Note that in typical partitioned cap systems,
> programs not written to use caps are still subject to enforcement of the capability
> rules, albeit at coarser grain (they won't be protected from memory safety errors
> within their own memory region).
>
> I believe a) and b) are not serious problems given a reasonable implementation of the
> false-match table. It's quite possible to choose a representation that is guaranteed
> to be bounded by a small fraction of physical memory in size, and to have access
> time that is O(1) in the number of entries.
>
> As for c), note that the timing difference for loads only occurs on a cache miss
> leading to a load from external memory. If the location of the load revealed useful
> information to an attacker, then there would already be a timing attack, and the
> timing variation due to the false match would not make it worse. So, the remaining
> issue is for cases where the location of the load does not reveal useful information,
> but useful information *is* revealed by the contents being a false match for the
> capability pattern. There is also a similar information leak for stores with this
> pattern, although because stores usually proceed in parallel with execution, there
> will probably only be a detectable timing variation if the processor must stall
> because store bandwidth has been saturated.
>
> We can potentially mitigate this problem by providing language-level facilities for
> sensitive values to be marked (which is useful for other reasons). Then these values
> can be represented in a way that never matches the capability pattern.
>
>
> I am not aware of any patents on this technique, and hereby relinquish any potential
> IP rights and dedicate it to the public domain.
>
>
> [Note 1]    The assumption that capability representations are fixed-size can be
>             relaxed if needed. Given a tag for every S bytes, we can allow the size
>             of a cap representation to be a variable multiple of S bytes, provided
>             that:
>              * it is only considered valid if all of the tags are retained, and
>                if it is referenced from its start location;
>              * it can only be copied (without being invalidated) as a unit.
>
> [Note 2]    In the IEEE 754 binary formats, all bit patterns represent possible
>             values, but it isn't necessarily the case that all bit patterns
>             representing NaNs can be produced as outputs of floating point operations,
>             since we can reserve some NaN payloads and never produce them as outputs.
>
>             It happens that the most-significant two bytes 0xFFFF or 0xFFFE in an
>             aligned IEEE 754 binary floating-point representation (representing a
>             subset of quiet NaNs in half-, single- and double-precision formats)
>             cannot occur in a valid aligned string of UTF-8, UTF-16 or UTF-32 encoded
>             characters. We can also make sure that the portion of the virtual address
>             space with this pattern in the most-significant bytes of a non-capability
>             pointer is not mapped. (I'm assuming that byte order is consistent
>             between floating point formats, Unicode code units, and pointers.)
>
>             In practice we wouldn't want this to be the whole capability pattern,
>             because -1 and -2 are commonly used 16-bit signed integers; I suggest
>             adding at least another 8 bits to the pattern.
>
> [Note 3]    In a single-address-space system with opaque capabilities, making the
>             pattern dependent on the location would have no observable effects,
>             because the pattern would be updated whenever a cap representation is
>             copied to a different location. In a system with non-opaque capabilities,
>             this might interfere with assumptions about being able to copy memory
>             contents -- for example CHERI allows copying memory containing cap
>             representations using memcpy, which requires the representation not to
>             change in order to conform to the C standard. In non-single-address-space
>             systems, it might also interfere with mapping the same physical memory at
>             different virtual addresses.
>
> [Anderson]
> https://www.lightbluetouchpaper.org/2014/07/03/the-cheri-capability-model-revisiting-risc-in-an-age-of-risk-isca-2014/
>
> [CKD1994]   Nicholas Carter, Stephen Keckler, William Dally
>             "Hardware Support for Fast Capability-based Addressing"
>             ASPLOS VI - Proceedings of the Sixth International Conference on
>             Architectural Support for Programming Languages and Operating Systems,
>             pages 319-327.
>             https://www.cs.utexas.edu/~skeckler/pubs/asplos94.pdf
>
> [CHERI2014] Jonathan Woodruff, Robert Watson, David Chisnall, Simon Moore,
>             Jonathan Anderson, Brooks Davis, Ben Laurie, Peter Neumann, Robert Norton,
>             Michael Roe
>             "The CHERI capability model: Revisiting RISC in an age of risk"
>             International Symposium on Computer Architecture (ISCA), June 2014.
>             http://www.cl.cam.ac.uk/research/security/ctsrd/pdfs/201406-isca2014-cheri.pdf
>
> --
> Daira Hopwood ⚥
>
> --
> You received this message because you are subscribed to the Google Groups "friam" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
> To post to this group, send email to [email protected].
> Visit this group at http://groups.google.com/group/friam.
> For more options, visit https://groups.google.com/d/optout.

_______________________________________________
cap-talk mailing list
[email protected]
http://www.eros-os.org/mailman/listinfo/cap-talk