Re: Redirects and Revocation in a Capability Filesystem

On Sat, November 8, 2014 16:13, David Barbour wrote:
> On Sat, Nov 8, 2014 at 5:18 AM, Rob Meijer <rmeijer-qWit8jRvyhVmR6Xm/[email protected]> wrote:
>
>>
>> How much are you willing to pay in performance and storage? And how does
>> your solution scale in these respect?
>>
>
> For transitive revocability and flexible mount points with compositional
> behavior, I'm willing to pay a lot more than my solution asks.
>
> In the current design, the effective storage hit is negligible: one object
> is added to the system for each revocation point, but that's essential.

Yes, absolutely, I have two objects there, the caretaker and the symbolic
link to the read-only attenuation of the caretaker. So you've already
halve the number of objects at that level.

> One
> byte is added to a capability for each revocation point, but in practice I
> can expect this to no more than double or triple the capability size (e.g.
> it's extremely rare to have filesystem paths that are fifty links deep,
> which would be necessary to triple the cap size); the outliers would
> mostly
> exist to prove they can exist, and would not be the bulk of the cost.

Wow, that's pretty impressive, my solution (lazily) adds a membrane proxy
object to each accessed sub-node of the object with the caretaker attached
to it. Is there any need for these capabilities to be persistently stored
in the file-system, or are they directly care-taker + target node
designating? If they are directly doubly designating without a persistent
in-file-system representation, than your specs are pretty impressive. If
you need to store them in the file-system persistently themselves, than
they are similar to my membrane proxy objects with similar scalability
figures.


> The performance hit is searching an index or graph for a viable path.

I have some trouble picturing an index on a file-system without a single
root node. Even more picturing it in a file-system where the file-system
itself is subject to the same POLA discipline as its clients and has no
way to even distinguish between a root node and a non-root node, where
every node potentially is a root node. Would this mean that for use with
my Rumpelstiltskin Tree graph based file-system I would need an index with
each node? If so, any advantage from 'half the objects' and 'tiny
membrane'

> This
> is a O(N) linear search in the base case. Fortunately, it's also highly
> cacheable. So the common case cost, for using a resource many times or
> many
> related resources, is much smaller.
>
>
>
> If you are willing to take the (O(N)) performance (with N being the number
>> of revocation points in a path) and (O(NlogN)) storage hit (with N being
>> the upper bound of covered by a revocation point), you could use
>> Rumpelstiltskin hash trees with extended attributes as I described.
>
>
> I don't understand all of your solution at the moment. Was eliminating
> potentially cyclic redirects essential to these performance numbers? Or
> was
> it just a choice you made?
>

No, it was the only locking-limited way I could find to eliminate TOCTOU
data race issues with concurrent revocation. Not sure if these data races
are universal to revocation in cyclic redirects or if they are tied to my
technological choices. The only alternative I could come up with was a
file-system wide lock on all extended attribute targeting operations (what
includes accessing anything trough a caretaker) during recursive
revocation operations.


>
>> these scaling specs are not particularly appealing, especially as apart
>> from the big O scaling issues, for small files and directories even a
>> single revocation point already adds up to almost 400% of disk IO
>> overhead.  What kind of price can be expected from your solution in this
>> respect? Is it better than my O(N) performance and O(NlogN) state?
>>
>
> I do think my approach will offer better performance. The state overhead
> barely even registers (O(1) per redirect), and the space overhead
> including
> non-state elements is only slightly higher (one or two extra bytes on
> every
> revocable capability), and the worst-case validation is O(N), but is
> highly
> cacheable.
>
> My solution also seems more expressive, allowing for redirects to form
> ad-hoc cyclic graphs (which happen to overlay a tree structure, in my use
> case). And I intend to make heavy use of it - e.g. every user directory is
> revocable, and users may have revocable sessions, and applications will
> typically be given revocable spaces. The 'revocation' in my model has some
> useful stability properties, i.e. you can just as easily un-revoke by
> adding the redirect back to the graph, thus treat revoke as 'disable'.


Interestingly, my design had a similar name-stability properties that I
consider to be a potential security vulnerability.

Lets say Alice in the past worked with 'Bob Bobson', this Bob has left her
team a few years back, but recently 'Bob Carols' joined the team.
Alice has long forgotten the delegated and revoked access to
/home/alice/myteam to the old Bob. Now when Alice creates a new caretaker
named '/home/alice/myteam:bob', she would have accidentally un-revoked
'Bob Bobson' his reference while she was creating a reference to share
with 'Bob Carols'. I considered this name stability property to be a major
drawback of my design.

If your stability property is similar you may want to think about how
desirable it actually is.


> OTOH, we aren't comparing apples to apples, here. My design doesn't
> require
> encrypting data on disk, so I'm not including keys in each ID. I'm most
> likely going to implement it above Berkeley DB rather than directly on a
> filesystem (I want my ACID and log files and smart memcache). Having
> fixed-size capabilities isn't essential for my use cases.
>

I understand. Just be careful knowing that ACID doesn't come free. Using
database technology will help avoid TOCTOU issues like the one I
mentioned, it might however do so by implementing rather broad locks
during some operations like the lock I told you above I desperately want
to avoid. You don't want to have a single deep recursive revocation lock
up other file-system operations for multiple seconds. I've moved away from
using database technology (sqlite) for exactly that reason before I even
considered the revocation issue. Do you rely on the ACID as supplied by
this database technology to make revocation within a cyclic-graph
concurrency safe? If so, you may be in for spikes of unexpectedly
high-latency in your file-system due to locks you did not anticipate. The
database will need to solve the same issues you would when doing
concurrent revocation in a cyclic sub graph. If your setup does not allow
ACID without a very broad lock, than the database solution at best would
use exactly that broad lock during recursive revocation. You should thus
probably make sure the price for the added expressiveness of supporting
cyclic paths with multiple revocation points does not end up being a
database that makes your file system occasionally freeze up for seconds.



Rob