Effective ACL Resource discovery requires 2n+1 requests

[bblfish]

The Access Control Panel has been putting together protocol comparisons between WAC, ACP, and various WAC+ solutions. (WAC+ are potential ways of extending WAC in a backward compatible way).

The Effective Access Control Resource Discovery Use Case reveals a quite dramatic problem for WAC when a resource is using a default rule further up the hierarchy. We have 4 WAC+ ways to solve the problem listed in the document there. Please could the WAC community help us select one of them?

Problem description

Our resources are set up as follows:

</default.acr>
</foo/bar/baz/x>
</foo/bar/baz/x.acr>

0. The client makes a request on </foo/bar/baz/x> and receives a response —

401 Credentials Required
Link: </foo/bar/baz/x.acr>; rel="acl"
Link: <.>; rev="http://www.w3.org/ns/ldp#contains"
...

The server needs to link to the closest possible ACR for the resource, to allow a client with Control rights to know what ACR to edit if it wants the rules there to apply specifically to that resource. If the resource were to link directly to the default, the client would not know where to overwrite the default.

1. The client makes a request to the ACR </foo/bar/baz/x.acr> but receives the reponse —

404 Not Found

— as the resource does not yet exist.

2. First the client is lucky enough to be shown the reverse ldp:contains relation in the response in (1) above, so it can do a HEAD on that to find its ACL.

HEAD /foo/bar/baz/ HTTP/1.1

— and with luck the server will respond —

200 Ok
Link: </foo/bar/baz/.acr>; rel="acl"
Link: </foo/bar/>; rev="http://www.w3.org/ns/ldp#contains"

3. The client can then continue with —

GET /foo/bar/baz/.acr HTTP/1.1

— to which the server will also return —

404 Not Found

— as the resource does not yet exist.

4. As a result, the client will need to look up one level in the hierarchy to search for the effective ACR:

HEAD /foo/bar/ HTTP/1.1

— and with luck the server will respond —

200 Ok
Link: </foo/bar/.acr>; rel="acl"
Link: </foo/>; rev="http://www.w3.org/ns/ldp#contains"

5. The client can then continue with —

GET /foo/bar/.acr HTTP/1.1

— to which the server will also return —

404 Not Found

— as the resource does not yet exist.

6. As a result, the client will need to look up one level in the hierarchy to search for the effective ACR:

HEAD /foo/ HTTP/1.1

— and with luck the server will respond —

200 Ok
Link: </foo/.acr>; rel="acl"
Link: </>; rev="http://www.w3.org/ns/ldp#contains"

7. The client can then continue with —

GET /foo/.acr HTTP/1.1

— to which the server will also return —

404 Not Found

— as the resource does not yet exist.

8. As a result, the client will need to look up one level in the hierarchy to search for the effective ACR:

HEAD / HTTP/1.1

— and with luck the server will respond —

200 Ok
Link: </.acr>; rel="acl"

9. The client can then continue with —

GET /.acr HTTP/1.1

— to which the server will finally return the content.

The number of requests needed to find the default can be calculated by the formula —

reqN = 2 * slashes + extraFile

— where —

• slashes is the number of slashes between the original resource and the effective ACR
• extraFile is 0 if the resource is an ldp:Container and 1 if it is a plain resource

So in our example above we have reqN = 2 * 4 + 1 = 9.

What we want is for that number to be cut down to 1 request.
As I mentioned there are 3 or 4 answers.
The one I prefer, as it is the simplest is explained in define another relation for non-created ACR.

[kjetilk]

I believe and always have, that the resource should link directly to its effective access control resource. It may also link to a resource that could be created to control it, but that is of secondary value, I think.

[bblfish]

I believe and always have, that the resource should link directly to its effective access control resource. It may also link to a resource that could be created to control it, but that is of secondary value, I think.

@kjetilk I agree for clients only interested in reading the ACL, which should be 99.99% of the cases if not more, the only interesting acl is the effective access control resource. So I think we can assume that that is what "acl" links refer to.

But - and this is really the crux of the matter - if you only link to that effective resource, say the default root ACL </default.acr>, then the client ACL editor cannot change the rules if it wants to make new defaults further into the directory tree: because it will not know what the URI of the ACL for that resource is or should be. We need the new link type to help the client know what link to follow in which circumstance.

So that is why I think the really simple answer is: we should link to both, but distinguish not-yet existing resources from the active ones. I don't know what to call that link: "potential-access-control-resource", "potential-acr", "specific-acr", "my-rule-resource"... (ideas welcome!)

The advantage of having two links is that

1. people who want their servers with most of the rules in a few default places, get that working with minimal number of ACL resources required. This could be especially useful for servers where nearly everything is public or for that matter for servers where everything is private.
2. people who prefer to have very specific rules tightly specified for one single resource can have that too.

Our use case from the use case document is actually one that starts off with a generic default and then moves to a more specific rule for a given container.

I think this is actually a nice compromise between ACP and WAC, that both could agree to.

[kjetilk]

But - and this is really the crux of the matter - if you only link to that effective resource, say the default root ACL </default.acr>, then the client ACL editor cannot change the rules if it wants to make new defaults further into the directory tree: because it will not know what the URI of the ACL for that resource is or should be. We need the new link type to help the client know what link to follow in which circumstance.

It might be that I don't understand what you are referring to, but I think that it can, given the slash semantics and container hierarchy assumption of Solid. Given that, it is, as far as I can tell, perfectly legitimate for the client to parse the URI of the access control resource and the target URI, and reason that they can create a new access control resource somewhere in between, if they are permitted to.

Therefore, I think that only a single link is required, a link targeting the effective access control resource, but I'd be OK with adding more, as being explicit about it is often a good practice.

[bblfish]

@kjetilk

but I'd be OK with adding more, as being explicit about it is often a good practice.

Great :-) [1]
We just need to come up with a good name for the missing relation!

Henry

[1] I'd say that working with decentralised hyper-apps requires a very high degree of explicitness. In usual client/server apps a lot can be implicit, because the person building the client also controls the server, and the location of data on the server as well as the schemas used. Here all we have to agree on is a protocol, and some Linked Data Vocabularies. The type of data published, the way people from different cultures prefer to organise their data and the schemas they will use all has to be left open.

[kjetilk]

[1] I'd say that working with decentralised hyper-apps requires a very high degree of explicitness.

I absolutely agree with that, in the interest of supporting HATEOAS, being explicit is very important.

The reason why am willing to depart from that ideal in this case is that in principle, the client can put the access controls at any level between the effective access control and itself. It all depends on what the client wants, and so, having that as out-of-band knowledge seems OK to me in this case.

[bblfish]

@kjetilk here are some more detailed answers to your last two posts:

But - and this is really the crux of the matter - if you only link to that effective resource, say the default root ACL </default.acr>, then the client ACL editor cannot change the rules if it wants to make new defaults further into the directory tree: because it will not know what the URI of the ACL for that resource is or should be. We need the new link type to help the client know what link to follow in which circumstance.

It might be that I don't understand what you are referring to, but I think that it can, given the slash semantics and container hierarchy assumption of Solid. Given that, it is, as far as I can tell, perfectly legitimate for the client to parse the URI of the access control resource and the target URI, and reason that they can create a new access control resource somewhere in between, if they are permitted to.

Say the a GET on </foo/bar/baz/secret> returns

200 Ok
WWW-Authenticate: Http-Sig
Link: <.>; rev="http://www.w3.org/ns/ldp#contains"
Link: </default.acl>; rel="acl"
...

Indeed, this is the best for auth based clients who want to find out what rights they may have for the given resource, as the acl link points them right to the effective resource. I suggest we should keep things that way.

In that situation access to </foo/bar/baz/secret> will be controlled by the rules in </default.acl>. If the user wants to change the default for that resource only, how is the client going to know where the access control resource for </foo/bar/baz/secret> should be placed? Where should it PUT the new rules?

Should it just guess and try all the following and more?

• </foo/bar/baz/secret.acr>
• </foo/bar/baz/secret.acl>
• </foo/bar/baz/secret.ac>
• </foo/bar/baz/secret.control>
• </foo/bar/baz/secret.kontrol>
• </foo/bar/baz/secret.ctrl>
• </foo/bar/baz/secret?ctrl>
• </foo/bar/baz/secret?control=1>
• </foo/bar/baz/secret?ctrl=sdj3j2dd342a> //<= for servers that don't want anyone to guess the URL

Clearly that is not a practical answer.
Instead this would be solved if the server returned a link to the ACR in the response.

401 Unauthorized
WWW-Authenticate: Http-Sig
Link: <.>; rev="http://www.w3.org/ns/ldp#contains"
Link: </default.acl>; rel="acl"
Link: </foo/bar/baz/secret?ctrl>; rel="direct-control"
...

Of course we need a word better than "direct-control".

The other simple answer is to have the "acl" Link points directly to the direct access control resource (</foo/bar/baz/secret?ctrl> in the case above): but then we have the problem of clients having to find the effective one, as show in the main text of this issue, leading to a problem of 2n+1 connections.

@kjetilk wrote

The reason why am willing to depart from that ideal in this case is that in principle, the client can put the access controls at any level between the effective access control and itself. It all depends on what the client wants, and so, having that as out-of-band knowledge seems OK to me in this case.

True, and that is why, in a way, I think that there is some degree of usefulness in allowing an Access Control Editor client to follow the container hierarchy to choose the right level at which to place the rules.

But that still requires the intermediate containers to have a link to their non-default ACL.
So say the client in our example wanted not only to change the rules for </foo/bar/baz/secret> as described above, but also set a new default for </foo/bar/baz/>, then it would want to make a HEAD request on </foo/bar/baz/> in order to find out what the URL of its acl should be. Clearly we'd have the same problem of the client having to guess the associated acl resource, if that is not made explicit.

[kjetilk]

Mmmm, right! We need a more open brainstorming session, I think.

Indeed, I think it should be up to the client to choose where in the hierarchy it is most suitable to put access control (subject to control permission of course), and so, it doesn't make sense for the server to enumerate all possibilities in every header for every request.

I have also been thinking that we may be using headers a little too much and the body possibly not enough. I'm thinking that the container may contain more descriptive resources in RDF. If we need to enumerate affordances, it might be better done in the body. If the container is unsuited for it, perhaps the payload of an OPTIONS request on the target resource is better? Or perhaps we could define some patterns that can be used for the client to put a valid access control into the hierarchy suitably.

I very much agree we need to avoid 2n+1 number of requests for this kind of behavior.

[bblfish]

@kjetilk wrote:

Indeed, I think it should be up to the client to choose where in the hierarchy it is most suitable to put access control (subject to control permission of course), and so, it doesn't make sense for the server to enumerate all possibilities in every header for every request.

I also agree with that now (I had not really thought of that before looking at :default acls to be honest).

If we adopt the two link relation types then we would have the following link headers
for each of the relevant resources:

resource path	resource's ACR (exists?)	Active ACR "acl"
/foo/bar/baz/x	/foo/bar/baz/x.ac (❌)	/default.ac
/foo/bar/baz/	/foo/bar/baz/.ac (❌)	/default.ac
/foo/bar/	/foo/bar/.ac (❌)	/default.ac
/foo/	/foo/.ac (❌)	/default.ac
/	/default.ac (✅)	/default.ac

The idea here is that every resource has a Link to it's "Access Control Resource" ACR to use the terminology from ACP. But as opposed to ACP that resource would not have to exist (right @matthieubosquet ?). We see above that only the Access Control Resource that exists is the </default.ac> resource. All others resources in the second column would return a 405 Method Not Allowed on a GET request, and specify that only PUT and PATCH are allowed.

So now on making a request to /foo/bar/baz/x an access control editor would know that it could edit /foo/bar/baz/x.ac to affect that resource alone. But it would know that it could also edit the ACRs for the intermediate containers if it wanted the rules it sets to have a wider range of application. How would it find those intermediate containers? Well the answer is simple: just the way I showed in the issue description, by following Link: <..>; rev="http://www.w3.org/ns/ldp#contains"links. That may require going through the directory hierarchy to set (PUT or PATCH) a new ACL. But that is fine, as setting an acl should be a very rare phenomenon compared to reading the ACL.

So let us imagine that the Client wants to set an acl default at /foo/bar/. After doing a HEAD on /foo/bar/baz/ it would find that /foo/bar/ was the grandparent container, and a HEAD on that would tell it that /foo/bar/.ac was the ACR for that container (but not the active one). So it could do a PUT on /foo/bar/.ac with the new rules and the situation would be as follows:

resource path	resource's ACR (exists?)	Active ACR "acl"
/foo/bar/baz/x	/foo/bar/baz/x.ac (❌)	/foo/bar/.ac
/foo/bar/baz/	/foo/bar/baz/.ac (❌)	/foo/bar/.ac
/foo/bar/	/foo/bar/.ac (✅)	/foo/bar/.ac
/foo/	/foo/.ac (❌)	/default.ac
/	/default.ac (✅)	/default.ac

Note that whenever a resource's ACR has a ✅ then the resource need only present the "acl" link relation.

So every resource with an active ACR that is not it's own will have two link relations. Otherwise only one relation to the "acl". The container hierarchy is then only needed in the very special case when a client wants to edit acl rules.

[csarven]

(mentioned this before in meetings, issues..)

First: There is an issue on this solid/specification#106 but I see no reference to it in proposed discussions. As there was no consensus on 106, I simplified the effective-acl-resource-algorithm so that it can be used by both servers and clients. And, then added a section in WAC ED to acknowledge Distinct Effective ACL Resource Extensions: https://solid.github.io/web-access-control-spec/#distinct-effective-acl-resource-extensions . The spec also notes Effective ACL Resource Alternatives: https://solid.github.io/web-access-control-spec/#effective-acl-resource-alternatives . No reference to any of those. So, the good news is that, it is possible.

Second: For the time being, I'm taking the 2n+1 formula (but discussed in terms of complexity) with a grain of salt. WAC doesn't prohibit a server to have a representation for every ACL resource. It only says that it should not have a representation in order for defaults to be used from a container higher up (towards root). So, yes, a particular server implementation with a particular data organisation will encounter 2n+1 as worst case but none of that is factored in the discussion. It is based off an example - I'm not arguing that it is not a legitimate case but nevertheless, it is a case. Can we have proper best, average, worst cases based on data/time/space, if we are going to talk about complexity?

[kjetilk]

I don't think anybody is suggesting that you didn't capture the consensus at the time, @csarven , but it is worth taking a look back at certain aspects.

FWIW, in this very open world, it is quite likely that someone will stumble on the worst case and the practical average case is basically a priori unknowable. I therefore think it is quite sufficient to consider the worst case unless there is obviously no use case for the situation where it arises. That is not to say that it is the only consideration, but it should be an important one.

[bblfish]

Prior work

Thanks @csarven for pointing to spec #106 and prior work. As I see we have quite a number of people who are for a header to point to the effective acl: @dmitrizagidulin, @RubenVerborgh, @kjetilk, @acoburn (suggested using http://www.trellisldp.org/ns/trellis#effectiveAcl) all were in favour of having two URLs: one for the resources own ACR and one for the effective one. Indeed the new spec, as you point out, states:

To enable clients to perform discovery faster, separate link relation type targeting the effective ACL resource is allowed, but no behaviour is defined by this specification

So what we are asking for here, is for that consensus be realised: I.e for a relation name to be coined so that all clients can follow that link, so as to avoid them having to make 2n+1 requests in the case where defaults are specified.
Whether the current "acl" header should point to the effective ACR and a new relation to the not yet existing ACL, or vice versa, is I think something that can be established by looking at how implementations are currently working.

On 2n+1

2n+1 is precisely the number of requests a client will have to make if it is to follow the procedure specified when dealing with default rules. That is a consequence of having default rules that are overridable by creating a new ACR, and I think now that there are reasonable use cases for that, such as a public web server where all content is publicly readable: why bother having ACRs on each resource, when there is only one effective one? I would complement that with :imports to allow new acls to avoid having to copy new rules everywhere. But that is a different issue.

[csarven]

This can be introduced. It'd be good to get some intent to implement for servers.

As far as I can tell, this feature would be an optimisation (MAY) so are there reasons for it to be MUST?

The #effective-acl-resource-algorithm will still need to work if there is no specific effective-acl-resource link relation.

[bblfish]

I don't think we are at the point of having to decide on MUST or MAY.
We are at the point of wanting a name for the relation, either a URL or a short name to go with "acl".

I think having the new relation does not invalidate the "effective-acl-resource algorithm", since a Control-Client may want to edit intermediate ACLs.

ACP: Access Control Potential?

[acoburn]

@acoburn (suggested using http://www.trellisldp.org/ns/trellis#effectiveAcl)

I would not suggest this. If I have suggested this in the past, I have changed my mind and do not think it solves the issue being discussed here.

[bblfish]

do not think it solves the issue being discussed here.

could you elaborate @acoburn ?

[acoburn]

Whether there exists a link to an "effective ACL" or not, when inheritance is in effect with WAC, any client needs to understand a lot about the overall (global) structure of the ACLs involved in a hierarchy of resources in order to make decisions about how a change in that effective ACL would affect the permission structure of that hierarchy. And while in the context of Solid there is a Pod owner which does have (or can have) global access to the ACL structure, that is not an assumption that holds generally.

And if a client does not have global understanding of the ACL structure for a hierarchically arranged set of resources, it doesn't matter whether that client can efficiently navigate to an "effective ACL" or not: that client still needs to navigate through the entire tree (which may not even be a possibility) in order to understand what will happen if that "effective ACL" is changed.

In a word: this just makes "unintended consequences" much, much more likely for clients. I would tread very carefully here.

[TallTed]

I would not think a client should do anything about discovering an ACL, whether that's an EACL or otherwise. Rather, the server should be doing that, and acting on what it discovers -- i.e., CREATING the requested resource, READing (i.e., providing a representation of) the requested resource, UPDATING the requested resource, DELETING the requested resource, or REFUSING any/all of these actions. If the server needs the client to authenticate in order to act on the ACL, the server might prompt for same -- but the server should not provide the client with the ACL, nor with information about what user(s) or group(s) might have or gain permission to access the resource(s); only the need for authentication should generally be provided -- and then, whatever the client provides be put against the ACL by the server which then responds with access granted or access denied, with whatever details make sense for the use case -- which might include "the user you authenticated as was denied, but you can contact xyz to request access" or an anonymized "click here to request access" (as Gdocs does, for instance), etc.

Anyway -- my point is that no client should ever need to know anything about the structure/mechanism/process the server uses to determine whether the client has permission to access anything or take any action.

[acoburn]

I would not think a client should do anything about discovering an ACL

This is true, but only in certain cases. There are also cases where a client will invariably want to change an ACL. That's where all of this becomes very relevant. Assuming that a client wants to change an ACL, that client will need a clear understanding of what will happen when that ACL is changed along with needing to know which ACL to change. That is where this issue becomes relevant.

[TallTed]

I'm not confident that the times a client will want or need to change an ACL will outnumber the times a client will not want or need to change an ACL, so I don't have a strong sense of which set of scenarios are "only certain cases" ... but I'm inclined to think the latter will happen significantly more often.

Even if the need to change is the more common situation, it seems to me that the server should be doing the heavy lifting, not the client. This does put some more work on the list for server developers, but it should lessen the work for client developers, and for users of both clients and servers. A lot more work does indeed fall to the spec developers (us), but that's generally as it should be.

[bblfish]

@acoburn two points:

1. the most requested interaction on ACL should be to read them, not to write to them. For that we need a direct link to the effective ACL in order to avoid the client having to search for them with 2n+1 requests.
2. A client that wanted to set special permissions on a folder higher up the hierarchy perhaps on the LDPR itself, does not need to know anything about the intermediate rules, as the rule it is setting affects the much smaller set it is dealing with, and overrides the previous ones. So a client should only set rules for the resources it knows about. If it only know of a specific LDPR, then it should just set the acl for that. That is why we need a direct link to the potential ACL. (potential because if it is active, then it the potential acl will be the same as effective one).

It seems to me that allowing 2n+1 efficiency improvements for the price of potentially one Link header (except for when n=0) is very much worth our putting in this little standardization effort.

[acoburn]

@bblfish I will just say that "it's complicated". When writing apps that interact directly with ACLs, I have yet to be convinced that this mechanism will ultimately make things easier. My experience suggests that the answer is that it will not. I am not interested in arguing this point; I am simply wanting to clarify that when you say that I'm advocating for this feature, it is not correct: I am not advocating for this feature.

[bblfish]

have yet to be convinced that this mechanism will ultimately make things easier.

Well it will save 2n+1 requests to find them, that I made crystal clear above. There is no doubt about it.

If you have a problem with default rules, then that is another thing, and perhaps worth arguing in another issue. Given the situation we have now, we need the extra link.

[acoburn]

Well it will save 2n+1 requests to find them, that I made crystal clear above. There is no doubt about it.

Indeed. And now you need to traverse the entire tree downwards to find out what the access controls in that resource actually mean. And those resources you traverse downward have already been fetched when you traverse upwards.

[bblfish]

And now you need to traverse the entire tree downwards to find out what the access controls in that resource actually mean.

Why? There should be no effective ACL between the requested resource and the effective ACL, as per Effective ACL Resource Algorithm.
Who has to do the traversing in "you need"? The client or the server? The server can do that quickly as the data is local and cachable. The client should not have to make those requests, as there are speed of light limitations to take into account.

[acoburn]

Consider the structure:

/
  container/ *
     child1/  *
        grandchild1a
        grandchild1b
        grandchild1c *
    child2/
        grandchild2a
        grandchild2b *
        grandchild2c
    child3/
        grandchild3a
        grandchild3b
        grandchild3c *

There is an acl on all resources with an asterisk. Say you perform a GET on /container/child3/grandchild3b

You get back two link headers: one pointing to the (non-existent) ACL for /container/child3/grandchild3b and one pointing to the ACL on /container/. What does the client do if it wants to give a user read access to /container/child3/grandchild3b?

One option:

• Create a new ACL resource associated with /container/child3/grandchild3b and add that user there. This is simple and can be done without the new link header.

The alternative that this new link header enables:

• Adjust the ACL associated with /container/.

However, what is the side-effect of making that second change? This user is now granted access to all of the other resources under /container/ that don't already have an ACL. How does the client know that? By traversing the entire tree.

[acoburn]

@bblfish my suggestion: implement this yourself on the code you are writing. Then write some apps. Then decide whether this is a good idea.

I have been through that process, and I concluded that it's not a good idea.

[bblfish]

Thanks @acoburn for drawing out the example nicely as you did above. Your first answer

Create a new ACL resource associated with /container/child3/grandchild3b and add that user there. This is simple and can be done without the new link header.

This is the answer I was pointing at when I wrote above a client should only set rules for the resources it knows about. It's a good rule of thumb. [1]

Furthermore your two examples assume that the only reason to know the effective ACL is to edit it. Usually reading outweighs writing by many factors as pointed out above by @TallTed. And for reading, those complications don't arise at all.

So the obvious answer to your problem we agree to: the safest rule to change is the potential ACL. And furthermore removing 2n+1 is also widely needed for quickly reading the ACL.

Given that we have this process we just need a link to the effective acl, like the one you have in Trellis.
http://www.trellisldp.org/ns/trellis#effectiveAcl

[1] (Also we can simplify a lot by only allowing positive rules (no negation). But that is something to be discussed elsewhere. I just point that out because there are many things that can be done to make things simpler. I am just proposing the simplest one we can agree to that has the most immediate impact.)

[kjetilk]

However, what is the side-effect of making that second change? This user is now granted access to all of the other resources under /container/ that don't already have an ACL. How does the client know that? By traversing the entire tree.

I don't understand. Wouldn't you in that case only add acl:accessTo </container/child3/grandchild3b> to the /container/.acl?