Hello,
I started looking at this RFE (new matching rule) and pushed the design https://www.port389.org/docs/389ds/design/matching-rule-in-chain.html
It is in a preliminary state but I hope covers major part of the RFE. Feedbacks are welcome :)
This RFE relies on another RFE (https://github.com/389ds/389-ds-base/issues/5156) that I will start to look at.
regards thierry
On 11 Feb 2022, at 00:51, Thierry Bordaz tbordaz@redhat.com wrote:
Hello,
I started looking at this RFE (new matching rule) and pushed the design https://www.port389.org/docs/389ds/design/matching-rule-in-chain.html
It is in a preliminary state but I hope covers major part of the RFE. Feedbacks are welcome :)
This RFE relies on another RFE (https://github.com/389ds/389-ds-base/issues/5156) that I will start to look at.
Is there a really compelling reason to implement this?
memberOf can already do nested groups, and populate those on leaf entries. So why do we need the IN_CHAIN behaviour?
My senses are telling me this is some IPA/AD related shenanigans, because in chain is how AD does memberOf expansion of nested groups. See:
https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-adts/1e889ad... https://docs.microsoft.com/en-au/windows/win32/adsi/search-filter-syntax?red...
However it's widely known that this operation is EXTREMELY SLOW on AD:
https://stackoverflow.com/questions/40024425/1-2-840-113556-1-4-1941-ldap-ma...
This article links to multiple other sites documenting the performance issues of this matching rule.
So I have significant concerns about:
* What is the problem this feature is required to solve? Is there a better way that we could consider by having a definition of the problem, rather than "the solution"? * The performance impact of this RFE given operational experience of MS AD * Why this RFE needs to exist at all given our memberOf capabilities that already fulfils nested group capabilities
Thanks,
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
Thank you William for diving into that RFE with as always very good points. I will try to answer.
You are right it is a requirement coming from IPA where future IPA instance will have to support MS client issuing In chain requests. I am not convince it will be very frequent req. It is even possible that this RFE is a kind of supported MR we need for conformity reasons.
The request triggers a set of recursive read operations. So it differs from memberof plugin that, does the reads and also update the target entry with memberof values. So it will be by far (I hope) faster than memberof plugin. The drawback is that the result of the computation is lost (not written) so there is no way to benefit from previous req.
The problem with memberof is that it updates the target entry. So it is beneficial only if you later search 'memberof'. If you do not it is a waste of time. Also memberof is very demanding, you need to keep the plugin always enabled to trust the result. We have seen many cases where memberof was disabled during some admin tasks then reenabled/fixup. So it is not comparing a bad 'in chain' solution vs a perfect 'memberof' solution, both have benefits/drawbacks.
Finally I have to admit, may be I auto convinced myself ;), that this matching rule provides a quite elegant membership processing without requiring plugins/config. For example with a same MR you can lookup both sides of the memberships (toward the members or toward the groups). (memberof:inChainMatch:=cn=bar) will give all the members of group 'cn=bar' while (member:inChainMatch:=uid=foo) will give all the groups foo is memberof.
best regards theirry
On 2/10/22 11:47 PM, William Brown wrote:
On 11 Feb 2022, at 00:51, Thierry Bordaz tbordaz@redhat.com wrote:
Hello,
I started looking at this RFE (new matching rule) and pushed the design https://www.port389.org/docs/389ds/design/matching-rule-in-chain.html
It is in a preliminary state but I hope covers major part of the RFE. Feedbacks are welcome :)
This RFE relies on another RFE (https://github.com/389ds/389-ds-base/issues/5156) that I will start to look at.
Is there a really compelling reason to implement this?
memberOf can already do nested groups, and populate those on leaf entries. So why do we need the IN_CHAIN behaviour?
My senses are telling me this is some IPA/AD related shenanigans, because in chain is how AD does memberOf expansion of nested groups. See:
https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-adts/1e889ad... https://docs.microsoft.com/en-au/windows/win32/adsi/search-filter-syntax?red...
However it's widely known that this operation is EXTREMELY SLOW on AD:
https://stackoverflow.com/questions/40024425/1-2-840-113556-1-4-1941-ldap-ma...
This article links to multiple other sites documenting the performance issues of this matching rule.
So I have significant concerns about:
- What is the problem this feature is required to solve? Is there a better way that we could consider by having a definition of the problem, rather than "the solution"?
- The performance impact of this RFE given operational experience of MS AD
- Why this RFE needs to exist at all given our memberOf capabilities that already fulfils nested group capabilities
Thanks,
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia _______________________________________________ 389-devel mailing list -- 389-devel@lists.fedoraproject.org To unsubscribe send an email to 389-devel-leave@lists.fedoraproject.org Fedora Code of Conduct: https://docs.fedoraproject.org/en-US/project/code-of-conduct/ List Guidelines: https://fedoraproject.org/wiki/Mailing_list_guidelines List Archives: https://lists.fedoraproject.org/archives/list/389-devel@lists.fedoraproject.... Do not reply to spam on the list, report it: https://pagure.io/fedora-infrastructure
On 11 Feb 2022, at 19:47, Thierry Bordaz tbordaz@redhat.com wrote:
Thank you William for diving into that RFE with as always very good points. I will try to answer.
You are right it is a requirement coming from IPA where future IPA instance will have to support MS client issuing In chain requests. I am not convince it will be very frequent req. It is even possible that this RFE is a kind of supported MR we need for conformity reasons.
Knew it :)
The request triggers a set of recursive read operations. So it differs from memberof plugin that, does the reads and also update the target entry with memberof values. So it will be by far (I hope) faster than memberof plugin. The drawback is that the result of the computation is lost (not written) so there is no way to benefit from previous req.
It will NOT be faster.
MemberOf is a fundamental trade - trading time during the write path to examine groups and then store these, so that we achieve in a reduction in processing time in the read path.
The plugin is the exact opposite. By saving in the write path (doing nothing), we have to do *all the work* in the read path. LDAP is also a read mostly system, meaning that we are making the exact wrong choice to go down a path to try to generate this in the read op.
Let's consider a write takes some time value defined as W . And let's assume that the member of takes some time value defined as M. And a read takes time R.
If we have memberof, with 1 write and 100 reads we have:
1(W + M) 100(R)
With In Chain we have:
1(W) 100(R + M)
So we've increased our work and time by 100M just by moving this. If you want to look at it the other way, MemberOf reduces our time by 100M.
Further, as mentioned, look at these reports:
https://stackoverflow.com/questions/40024425/1-2-840-113556-1-4-1941-ldap-ma...
"using LDAP_MATCHING_RULE_IN_CHAIN is much slower (in our case, a factor of 10x) than simply doing the recursive "member-of" search that the above quote says LDAP_MATCHING_RULE_IN_CHAIN was intended to replace."
http://dunnry.com/blog/TransitiveLinkValueFilterEvaluation.aspx
"I expected the new filter to run circles around my code and I was pretty shocked when the reverse was actually true ... transitive filter (409ms) as compared to only (41ms) using the recursive search."
https://stackoverflow.com/questions/6143665/single-line-ldap-query-that-enum...
"It works, although the query is slow as hell (~5-10 seconds)"
https://stackoverflow.com/questions/9534669/improving-recursive-active-direc...
"Code I am using as per JPBlancs's suggestion, whilst this works, it is much slower than my original, am I implementing it incorreclty?"
The problem with memberof is that it updates the target entry. So it is beneficial only if you later search 'memberof'. If you do not it is a waste of time. Also memberof is very demanding, you need to keep the plugin always enabled to trust the result.
This is a *good thing*. This is the whole point of this trade. We trade write path time and storage for huge improvement in read path time. Especially relevant given that ldap is massively read oriented.
We have seen many cases where memberof was disabled during some admin tasks then reenabled/fixup. So it is not comparing a bad 'in chain' solution vs a perfect 'memberof' solution, both have benefits/drawbacks.
I have previously stated how our MemberOf algorithm is slow and how we could fix it. I have provided proof of these algorithmic improvements, but those suggestions were not applied.
Finally I have to admit, may be I auto convinced myself ;), that this matching rule provides a quite elegant membership processing without requiring plugins/config. For example with a same MR you can lookup both sides of the memberships (toward the members or toward the groups). (memberof:inChainMatch:=cn=bar) will give all the members of group 'cn=bar' while (member:inChainMatch:=uid=foo) will give all the groups foo is memberof.
I don't know how to express this but I'm extraordinarily concerned about the impact of this RFE. I think the performance impact has not been considered accurately, and I think it will only compound the performance issues we have within IPA. Especially once we combine with the many pre-existing IPA integration specific performance issues that have repeatedly gone ignored (related to the ipa plugins for ds).
In order for me to be happy with this RFE as an extension, I would ask that:
* This MUST be a plugin, and ship default disabled. * Test cases MUST include group cycles and nesting to deep levels. IE a cycle of 100 items long or similar. We need to prove that we can cycle break since there is a risk of infinite loop and deadlock with this plugin. * The implementation must be iterative and not recursive else we may hit stack depth limits.
Implementation - EITHER:
* This OID internally uses memberOf attributes to perform the resolution IE - (member:1.2.840.113556.1.4.1941:=CN=User1,OU=X,DC=domain,DC=com) -- internally we just search the user, retrieve it's memberOf (which we already have and is pre-computed with nesting) and return the set of groups. - (memberOf:1.2.840.113556.1.4.1941:=CN=A Group,OU=Y,DC=domain,DC=com) -- A no-op, since we already have nesting in memberOf, we just return the result directly. We already have memberOf, and it's already done the work - let's use that information. * If the results of this search are virtualAttributes and cached such that repeat searches hit the cache and do not stress the server.
I think having this without a virtual attr cache, or without using existing memberof infrastructure is a recipe for disaster.
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
Hi William,
As usual I want to thank you a lot for all those precious and detailed feedbacks. I will try to summarize your points and to answer them. If I forget a point, please just give me a head up.
* Performance: The InChain search request is expensive, may put high pressure on the server and we should have a mean to protect the server.
I agree that to follow membership link has a cost, a risk (infinite loop) and impacts the server.
On the cost aspect I meant that MR computation (membership traversal) of a *single* search should be much faster than (membership traversal) during memberof plugin call because memberof triggers the same set of searches and in addition updates the members. This being said, I fully agree that it is much more efficient to do a regular SRCH req '(memberof=cn=bar)' than '(member:1.2.840.113556.1.4.1941:=cn=bar)' and a clever application should prefer 'memberof'. The main drawback of 'memberof' option is that it only works for 'memberof' attribute. While InChain works for any membership attribute.
Regarding the risk of infinite loop, the current memberof_get_groups() has a loop detection mechanism.
Regarding the impact of the server, you mentioned to enforce a limit of nesting. I agree with this idea and worth to be added to https://github.com/389ds/389-ds-base/issues/5156
Regarding https://github.com/389ds/389-ds-base/issues/5156, I think it is a good time to implement/compare current memberof_get_group implementation with your previous proposal.
* Impact of the RFE on the server
Once registered the InChain MR is presented as supported MR on base DSE. That is the only impact until a SRCH use the MR. Should we limit SRCH InChain to list of bound DN ? Regarding performance risk, I think it would be somehow similar to what a deref control is (deref drawback being aci while InChain would be nested membership) and there is no limit to the use of deref control. So IMHO there is no consequence on the server of supporting or not this RFE.
* InChain being a plugin It is a plugin (syntax), the change is the move of nested memberships searches into a slapi private function.
* Using iteration rather than recursive Knowing that there is a loop detection mechanism, I see not a huge benefit of iteration vs recursive. Indeed in identity membership we can not anticipated huge nesting.
* Shortcut InChain 'member' and 'memberof' into a use of 'memberof' attribute looks a very nice idea. Documentation should warn that InChain 'member' relies on 'memberof' properly updated (risk of enable/disable memberof plugin)
* membership attribute being a virtual attribute, is a bad idea. This will results in unindexed searches. Caching result is not possible as virtual attribute evaluation may differ between two searches. May be I misunderstand how you intend to use virtual attribute in such case.
best regards thierry
On 2/14/22 12:23 AM, William Brown wrote:
On 11 Feb 2022, at 19:47, Thierry Bordaz tbordaz@redhat.com wrote:
Thank you William for diving into that RFE with as always very good points. I will try to answer.
You are right it is a requirement coming from IPA where future IPA instance will have to support MS client issuing In chain requests. I am not convince it will be very frequent req. It is even possible that this RFE is a kind of supported MR we need for conformity reasons.
Knew it :)
The request triggers a set of recursive read operations. So it differs from memberof plugin that, does the reads and also update the target entry with memberof values. So it will be by far (I hope) faster than memberof plugin. The drawback is that the result of the computation is lost (not written) so there is no way to benefit from previous req.
It will NOT be faster.
MemberOf is a fundamental trade - trading time during the write path to examine groups and then store these, so that we achieve in a reduction in processing time in the read path.
The plugin is the exact opposite. By saving in the write path (doing nothing), we have to do *all the work* in the read path. LDAP is also a read mostly system, meaning that we are making the exact wrong choice to go down a path to try to generate this in the read op.
Let's consider a write takes some time value defined as W . And let's assume that the member of takes some time value defined as M. And a read takes time R.
If we have memberof, with 1 write and 100 reads we have:
1(W + M) 100(R)
With In Chain we have:
1(W) 100(R + M)
So we've increased our work and time by 100M just by moving this. If you want to look at it the other way, MemberOf reduces our time by 100M.
Further, as mentioned, look at these reports:
https://stackoverflow.com/questions/40024425/1-2-840-113556-1-4-1941-ldap-ma...
"using LDAP_MATCHING_RULE_IN_CHAIN is much slower (in our case, a factor of 10x) than simply doing the recursive "member-of" search that the above quote says LDAP_MATCHING_RULE_IN_CHAIN was intended to replace."
http://dunnry.com/blog/TransitiveLinkValueFilterEvaluation.aspx
"I expected the new filter to run circles around my code and I was pretty shocked when the reverse was actually true ... transitive filter (409ms) as compared to only (41ms) using the recursive search."
https://stackoverflow.com/questions/6143665/single-line-ldap-query-that-enum...
"It works, although the query is slow as hell (~5-10 seconds)"
https://stackoverflow.com/questions/9534669/improving-recursive-active-direc...
"Code I am using as per JPBlancs's suggestion, whilst this works, it is much slower than my original, am I implementing it incorreclty?"
The problem with memberof is that it updates the target entry. So it is beneficial only if you later search 'memberof'. If you do not it is a waste of time. Also memberof is very demanding, you need to keep the plugin always enabled to trust the result.
This is a *good thing*. This is the whole point of this trade. We trade write path time and storage for huge improvement in read path time. Especially relevant given that ldap is massively read oriented.
We have seen many cases where memberof was disabled during some admin tasks then reenabled/fixup. So it is not comparing a bad 'in chain' solution vs a perfect 'memberof' solution, both have benefits/drawbacks.
I have previously stated how our MemberOf algorithm is slow and how we could fix it. I have provided proof of these algorithmic improvements, but those suggestions were not applied.
Finally I have to admit, may be I auto convinced myself ;), that this matching rule provides a quite elegant membership processing without requiring plugins/config. For example with a same MR you can lookup both sides of the memberships (toward the members or toward the groups). (memberof:inChainMatch:=cn=bar) will give all the members of group 'cn=bar' while (member:inChainMatch:=uid=foo) will give all the groups foo is memberof.
I don't know how to express this but I'm extraordinarily concerned about the impact of this RFE. I think the performance impact has not been considered accurately, and I think it will only compound the performance issues we have within IPA. Especially once we combine with the many pre-existing IPA integration specific performance issues that have repeatedly gone ignored (related to the ipa plugins for ds).
In order for me to be happy with this RFE as an extension, I would ask that:
- This MUST be a plugin, and ship default disabled.
- Test cases MUST include group cycles and nesting to deep levels. IE a cycle of 100 items long or similar. We need to prove that we can cycle break since there is a risk of infinite loop and deadlock with this plugin.
- The implementation must be iterative and not recursive else we may hit stack depth limits.
Implementation - EITHER:
- This OID internally uses memberOf attributes to perform the resolution IE
We already have memberOf, and it's already done the work - let's use that information.
- (member:1.2.840.113556.1.4.1941:=CN=User1,OU=X,DC=domain,DC=com) -- internally we just search the user, retrieve it's memberOf (which we already have and is pre-computed with nesting) and return the set of groups.
- (memberOf:1.2.840.113556.1.4.1941:=CN=A Group,OU=Y,DC=domain,DC=com) -- A no-op, since we already have nesting in memberOf, we just return the result directly.
- If the results of this search are virtualAttributes and cached such that repeat searches hit the cache and do not stress the server.
I think having this without a virtual attr cache, or without using existing memberof infrastructure is a recipe for disaster.
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
On 14 Feb 2022, at 23:23, Thierry Bordaz tbordaz@redhat.com wrote:
Hi William,
As usual I want to thank you a lot for all those precious and detailed feedbacks. I will try to summarize your points and to answer them. If I forget a point, please just give me a head up.
All good mate :)
• Performance: The InChain search request is expensive, may put high pressure on the server and we should have a mean to protect the server.
I agree that to follow membership link has a cost, a risk (infinite loop) and impacts the server.
On the cost aspect I meant that MR computation (membership traversal) of a *single* search should be much faster than (membership traversal) during memberof plugin call because memberof triggers the same set of searches and in addition updates the members. This being said, I fully agree that it is much more efficient to do a regular SRCH req '(memberof=cn=bar)' than '(member:1.2.840.113556.1.4.1941:=cn=bar)' and
So there is a very major piece of context that you might be missing here. Since this is related to the (unhealthy obsession) with FreeIPA slowly morphing into AD, there are AD specific behaviours we need to remember in this proposal.
MS AD Technical Specification - https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-adts/d243592...
In AD, memberOf is constructed using what's called a "back link attribute" ([MS-ADTS] - v20210625, page 27 ). These back links are derived and inverse from a forward link. If my memory serves correctly, you can consider these as a "pointer". Rather than how we store member / member of with dn's such as:
┌───────────────────┐ ┌───────────────────┐ │ │ │ │ │dn: cn=group ◀─ ─ ┼ ─ ─ ┐┌──────────▶│dn: uid=user │ │member: uid=user───┼──────┴ ─ ─ ─ ─ ─ │memberOf: cn=group │ │ │ │ │ └───────────────────┘ └───────────────────┘
AD stores these links as a pointer:
┌───────────────────┐ ┌───────────────────┐ │ │ │ │ │dn: cn=group │ │dn: uid=user │ │linkId: 1 ◀ ─ ─ ─ ┼ ─ ┐┌────────────▶│linkId: 2 │ │member: 2 ────────┼────┴ ─ ─ ─ ─ ─ ─ │memberOf: 1 │ │ │ │ │ └───────────────────┘ └───────────────────┘
Now, importantly this means that memberOf on AD is NOT able to represent nested groups because:
""" A forward link attribute can exist with no corresponding back link attribute, but not vice-versa. """
What this means is that you can express a member (forward link) and direct memberOf (back link) but not a nested group.
┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐ │ │ │dn: cn=group │ │ │ │dn: cn=group │ ┌────────────▶│linkId: 2 ◀─ ─ ─ ─│─ ─ │dn: uid=user │ │linkId: 1 ◀ ─ ─ ─ ─│─ ┐│ │member: 3 ─────────┼───┼────────────▶ │linkId: 3 │ │member: 2 ─────────┼───┴ ─ ─ ─ ─ ─ ─ │memberOf: 1 │ ─ ─ ─ ─ ─ ─ ─ │memberOf: 2 │ │ │ │ │ │ │ └───────────────────┘ └───────────────────┘ └───────────────────┘
If we were to add memberOf for linkId: 1 notice:
┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐ │ │ │dn: cn=group │ │ │ │dn: cn=group │ ┌────────────▶│linkId: 2 ◀─ ─ ─ ─│─ ─ │dn: uid=user │ │linkId: 1 ◀ ─ ─ ─ ─│─ ┐│ │member: 3 ─────────┼───┼────────────▶ │linkId: 3 │ │member: 2 ─────────┼──┼┴ ─ ─ ─ ─ ─ ─ │memberOf: 1 │ ─ ─ ─ ─ ─ ─ ─ │memberOf: 2 │ │ │ │ │ ││memberOf: 1 │ └───────────────────┘ │ └───────────────────┘ └───────────────────┘ │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
There is no *forward link* from linkId 1 to user (memberOf 1), thus violating the constraints of link attributes in AD.
This means that in AD memberOf values are not nested and can not express or show nested groups. This is what the chain-link oid solves - since this follows each stack of the links building up the complete group graph, chain link IS able to show group nesting.
a clever application should prefer 'memberof'.
Because of this fact, a clever application that wants *nested groups* can NOT use memberOf in an AD environment, and is forced to rely on the link chain oid. There is also no magic sauce that an application will see or know about to know they are in a FreeIPA hybrid AD monster, which lets them know that our memberOf state is a full and complete group graph with nesting included so they can prefer that.
The main drawback of 'memberof' option is that it only works for 'memberof' attribute. While InChain works for any membership attribute.
But the main usage of this will be memberships to groups due to the nesting details above. Groups also tend to have larger and more complex structures. That's why this is a focus.
Regarding the risk of infinite loop, the current memberof_get_groups() has a loop detection mechanism.
Regarding the impact of the server, you mentioned to enforce a limit of nesting. I agree with this idea and worth to be added to https://github.com/389ds/389-ds-base/issues/5156
Regarding https://github.com/389ds/389-ds-base/issues/5156, I think it is a good time to implement/compare current memberof_get_group implementation with your previous proposal.
Sure, it seems like a good idea. My "previous proposal" is already in use in kanidm, and it's extremely fast for memberOf updates compared to 389.
I think that it would be hugely value for us to consider memberOf a "default and required" element of the server, and to improve it as such. That way our get_group capabilities can just search on memberOf which should be a single search.
• Impact of the RFE on the server
Once registered the InChain MR is presented as supported MR on base DSE. That is the only impact until a SRCH use the MR. Should we limit SRCH InChain to list of bound DN ?
I think we should have aci's to limit access to this yes. Alternately, it should have a cn=config switch to enable/disable this control, and it ships default disabled.
Regarding performance risk, I think it would be somehow similar to what a deref control is (deref drawback being aci while InChain would be nested membership) and there is no limit to the use of deref control. So IMHO there is no consequence on the server of supporting or not this RFE.
• InChain being a plugin It is a plugin (syntax), the change is the move of nested memberships searches into a slapi private function.
• Using iteration rather than recursive Knowing that there is a loop detection mechanism, I see not a huge benefit of iteration vs recursive. Indeed in identity membership we can not anticipated huge nesting.
Iteration won't cause your whole server instance to panic and crash because of a weird group setup.
• Shortcut InChain 'member' and 'memberof' into a use of 'memberof' attribute looks a very nice idea. Documentation should warn that InChain 'member' relies on 'memberof' properly updated (risk of enable/disable memberof plugin)
Yep - we already have that data, so we can rely on it and use it. I think we should change memberOf to enabled by default TBH.
• membership attribute being a virtual attribute, is a bad idea. This will results in unindexed searches. Caching result is not possible as virtual attribute evaluation may differ between two searches. May be I misunderstand how you intend to use virtual attribute in such case. best regards thierry
On 2/14/22 12:23 AM, William Brown wrote:
On 11 Feb 2022, at 19:47, Thierry Bordaz tbordaz@redhat.com wrote:
Thank you William for diving into that RFE with as always very good points. I will try to answer.
You are right it is a requirement coming from IPA where future IPA instance will have to support MS client issuing In chain requests. I am not convince it will be very frequent req. It is even possible that this RFE is a kind of supported MR we need for conformity reasons.
Knew it :)
The request triggers a set of recursive read operations. So it differs from memberof plugin that, does the reads and also update the target entry with memberof values. So it will be by far (I hope) faster than memberof plugin. The drawback is that the result of the computation is lost (not written) so there is no way to benefit from previous req.
It will NOT be faster.
MemberOf is a fundamental trade - trading time during the write path to examine groups and then store these, so that we achieve in a reduction in processing time in the read path.
The plugin is the exact opposite. By saving in the write path (doing nothing), we have to do *all the work* in the read path. LDAP is also a read mostly system, meaning that we are making the exact wrong choice to go down a path to try to generate this in the read op.
Let's consider a write takes some time value defined as W . And let's assume that the member of takes some time value defined as M. And a read takes time R.
If we have memberof, with 1 write and 100 reads we have:
1(W + M) 100(R)
With In Chain we have:
1(W) 100(R + M)
So we've increased our work and time by 100M just by moving this. If you want to look at it the other way, MemberOf reduces our time by 100M.
Further, as mentioned, look at these reports:
https://stackoverflow.com/questions/40024425/1-2-840-113556-1-4-1941-ldap-ma...
"using LDAP_MATCHING_RULE_IN_CHAIN is much slower (in our case, a factor of 10x) than simply doing the recursive "member-of" search that the above quote says LDAP_MATCHING_RULE_IN_CHAIN was intended to replace. "
http://dunnry.com/blog/TransitiveLinkValueFilterEvaluation.aspx
" I expected the new filter to run circles around my code and I was pretty shocked when the reverse was actually true ... transitive filter (409ms) as compared to only (41ms) using the recursive search. "
https://stackoverflow.com/questions/6143665/single-line-ldap-query-that-enum...
" It works, although the query is slow as hell (~5-10 seconds) "
https://stackoverflow.com/questions/9534669/improving-recursive-active-direc...
" Code I am using as per JPBlancs's suggestion, whilst this works, it is much slower than my original, am I implementing it incorreclty?"
The problem with memberof is that it updates the target entry. So it is beneficial only if you later search 'memberof'. If you do not it is a waste of time. Also memberof is very demanding, you need to keep the plugin always enabled to trust the result.
This is a *good thing*. This is the whole point of this trade. We trade write path time and storage for huge improvement in read path time. Especially relevant given that ldap is massively read oriented.
We have seen many cases where memberof was disabled during some admin tasks then reenabled/fixup. So it is not comparing a bad 'in chain' solution vs a perfect 'memberof' solution, both have benefits/drawbacks.
I have previously stated how our MemberOf algorithm is slow and how we could fix it. I have provided proof of these algorithmic improvements, but those suggestions were not applied.
Finally I have to admit, may be I auto convinced myself ;), that this matching rule provides a quite elegant membership processing without requiring plugins/config. For example with a same MR you can lookup both sides of the memberships (toward the members or toward the groups). (memberof:inChainMatch:=cn=bar) will give all the members of group 'cn=bar' while (member:inChainMatch:=uid=foo) will give all the groups foo is memberof.
I don't know how to express this but I'm extraordinarily concerned about the impact of this RFE. I think the performance impact has not been considered accurately, and I think it will only compound the performance issues we have within IPA. Especially once we combine with the many pre-existing IPA integration specific performance issues that have repeatedly gone ignored (related to the ipa plugins for ds).
In order for me to be happy with this RFE as an extension, I would ask that:
- This MUST be a plugin, and ship default disabled.
- Test cases MUST include group cycles and nesting to deep levels. IE a cycle of 100 items long or similar. We need to prove that we can cycle break since there is a risk of infinite loop and deadlock with this plugin.
- The implementation must be iterative and not recursive else we may hit stack depth limits.
Implementation - EITHER:
- This OID internally uses memberOf attributes to perform the resolution IE
We already have memberOf, and it's already done the work - let's use that information.
- (member:1.2.840.113556.1.4.1941:=CN=User1,OU=X,DC=domain,DC=com) -- internally we just search the user, retrieve it's memberOf (which we already have and is pre-computed with nesting) and return the set of groups.
- (memberOf:1.2.840.113556.1.4.1941:=CN=A Group,OU=Y,DC=domain,DC=com) -- A no-op, since we already have nesting in memberOf, we just return the result directly.
- If the results of this search are virtualAttributes and cached such that repeat searches hit the cache and do not stress the server.
I think having this without a virtual attr cache, or without using existing memberof infrastructure is a recipe for disaster.
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
On Tue, Feb 15, 2022 at 12:36 AM William Brown william.brown@suse.com wrote:
On 14 Feb 2022, at 23:23, Thierry Bordaz tbordaz@redhat.com wrote:
Hi William,
As usual I want to thank you a lot for all those precious and detailed
feedbacks. I will try to summarize your points and to answer them. If I forget a point, please just give me a head up.
All good mate :)
• Performance: The InChain search request is expensive, may put
high pressure on the server and we should have a mean to protect the server.
I agree that to follow membership link has a cost, a risk (infinite
loop) and impacts the server.
On the cost aspect I meant that MR computation (membership traversal) of
a *single* search should be much faster than (membership traversal) during memberof plugin call because memberof triggers the same set of searches and in addition updates the members. This being said, I fully agree that it is much more efficient to do a regular SRCH req '(memberof=cn=bar)' than '(member:1.2.840.113556.1.4.1941:=cn=bar)' and
So there is a very major piece of context that you might be missing here. Since this is related to the (unhealthy obsession) with FreeIPA slowly morphing into AD, there are AD specific behaviours we need to remember in this proposal.
MS AD Technical Specification - https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-adts/d243592...
In AD, memberOf is constructed using what's called a "back link attribute" ([MS-ADTS] - v20210625, page 27 ). These back links are derived and inverse from a forward link. If my memory serves correctly, you can consider these as a "pointer". Rather than how we store member / member of with dn's such as:
┌───────────────────┐ ┌───────────────────┐ │ │ │ │ │dn: cn=group ◀─ ─ ┼ ─ ─ ┐┌──────────▶│dn: uid=user │ │member: uid=user───┼──────┴ ─ ─ ─ ─ ─ │memberOf: cn=group │ │ │ │ │ └───────────────────┘ └───────────────────┘
AD stores these links as a pointer:
┌───────────────────┐ ┌───────────────────┐ │ │ │ │ │dn: cn=group │ │dn: uid=user │ │linkId: 1 ◀ ─ ─ ─ ┼ ─ ┐┌────────────▶│linkId: 2 │ │member: 2 ────────┼────┴ ─ ─ ─ ─ ─ ─ │memberOf: 1 │ │ │ │ │ └───────────────────┘ └───────────────────┘
Now, importantly this means that memberOf on AD is NOT able to represent nested groups because:
""" A forward link attribute can exist with no corresponding back link attribute, but not vice-versa. """
What this means is that you can express a member (forward link) and direct memberOf (back link) but not a nested group.
┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐ │ │ │dn: cn=group │ │ │ │dn: cn=group │ ┌────────────▶│linkId: 2 ◀─ ─ ─ ─│─ ─ │dn: uid=user │ │linkId: 1 ◀ ─ ─ ─ ─│─ ┐│ │member: 3 ─────────┼───┼────────────▶ │linkId: 3 │ │member: 2 ─────────┼───┴ ─ ─ ─ ─ ─ ─ │memberOf: 1 │ ─ ─ ─ ─ ─ ─ ─ │memberOf: 2 │ │ │ │ │ │ │ └───────────────────┘ └───────────────────┘ └───────────────────┘
If we were to add memberOf for linkId: 1 notice:
┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐ │ │ │dn: cn=group │ │ │ │dn: cn=group │ ┌────────────▶│linkId: 2 ◀─ ─ ─ ─│─ ─ │dn: uid=user │ │linkId: 1 ◀ ─ ─ ─ ─│─ ┐│ │member: 3 ─────────┼───┼────────────▶ │linkId: 3 │ │member: 2 ─────────┼──┼┴ ─ ─ ─ ─ ─ ─ │memberOf: 1 │ ─ ─ ─ ─ ─ ─ ─ │memberOf: 2 │ │ │ │ │ ││memberOf: 1 │ └───────────────────┘ │ └───────────────────┘ └───────────────────┘
│ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
There is no *forward link* from linkId 1 to user (memberOf 1), thus violating the constraints of link attributes in AD.
This means that in AD memberOf values are not nested and can not express or show nested groups. This is what the chain-link oid solves - since this follows each stack of the links building up the complete group graph, chain link IS able to show group nesting.
a clever application should prefer 'memberof'.
Because of this fact, a clever application that wants *nested groups* can NOT use memberOf in an AD environment, and is forced to rely on the link chain oid. There is also no magic sauce that an application will see or know about to know they are in a FreeIPA hybrid AD monster, which lets them know that our memberOf state is a full and complete group graph with nesting included so they can prefer that.
The main drawback of 'memberof' option is that it only works for
'memberof' attribute. While InChain works for any membership attribute.
But the main usage of this will be memberships to groups due to the nesting details above. Groups also tend to have larger and more complex structures. That's why this is a focus.
Regarding the risk of infinite loop, the current memberof_get_groups()
has a loop detection mechanism.
Regarding the impact of the server, you mentioned to enforce a limit of
nesting. I agree with this idea and worth to be added to https://github.com/389ds/389-ds-base/issues/5156
Regarding https://github.com/389ds/389-ds-base/issues/5156, I think it
is a good time to implement/compare current memberof_get_group implementation with your previous proposal.
Sure, it seems like a good idea. My "previous proposal" is already in use in kanidm, and it's extremely fast for memberOf updates compared to 389.
I think that it would be hugely value for us to consider memberOf a "default and required" element of the server, and to improve it as such. That way our get_group capabilities can just search on memberOf which should be a single search.
• Impact of the RFE on the server
Once registered the InChain MR is presented as supported MR on base DSE.
That is the only impact until a SRCH use the MR. Should we limit SRCH InChain to list of bound DN ?
I think we should have aci's to limit access to this yes. Alternately, it should have a cn=config switch to enable/disable this control, and it ships default disabled.
Regarding performance risk, I think it would be somehow similar to what
a deref control is (deref drawback being aci while InChain would be nested membership) and there is no limit to the use of deref control.
So IMHO there is no consequence on the server of supporting or not this
RFE.
• InChain being a plugin
It is a plugin (syntax), the change is the move of nested memberships
searches into a slapi private function.
• Using iteration rather than recursive
Knowing that there is a loop detection mechanism, I see not a huge
benefit of iteration vs recursive. Indeed in identity membership we can not anticipated huge nesting.
Iteration won't cause your whole server instance to panic and crash because of a weird group setup.
• Shortcut InChain 'member' and 'memberof' into a use of
'memberof' attribute looks a very nice idea. Documentation should warn that InChain 'member' relies on 'memberof' properly updated (risk of enable/disable memberof plugin)
Yep - we already have that data, so we can rely on it and use it. I think we should change memberOf to enabled by default TBH.
• membership attribute being a virtual attribute, is a bad idea.
This will results in unindexed searches. Caching result is not possible as virtual attribute evaluation may differ between two searches. May be I misunderstand how you intend to use virtual attribute in such case.
best regards thierry
On 2/14/22 12:23 AM, William Brown wrote:
On 11 Feb 2022, at 19:47, Thierry Bordaz tbordaz@redhat.com wrote:
Thank you William for diving into that RFE with as always very good
points. I will try to answer.
You are right it is a requirement coming from IPA where future IPA
instance will have to support MS client issuing In chain requests. I am not convince it will be very frequent req. It is even possible that this RFE is a kind of supported MR we need for conformity reasons.
Knew it :)
The request triggers a set of recursive read operations. So it differs
from memberof plugin that, does the reads and also update the target entry with memberof values. So it will be by far (I hope) faster than memberof plugin. The drawback is that the result of the computation is lost (not written) so there is no way to benefit from previous req.
It will NOT be faster.
MemberOf is a fundamental trade - trading time during the write path to
examine groups and then store these, so that we achieve in a reduction in processing time in the read path.
The plugin is the exact opposite. By saving in the write path (doing
nothing), we have to do *all the work* in the read path. LDAP is also a read mostly system, meaning that we are making the exact wrong choice to go down a path to try to generate this in the read op.
Let's consider a write takes some time value defined as W . And let's
assume that the member of takes some time value defined as M. And a read takes time R.
If we have memberof, with 1 write and 100 reads we have:
1(W + M) 100(R)
With In Chain we have:
1(W) 100(R + M)
So we've increased our work and time by 100M just by moving this. If
you want to look at it the other way, MemberOf reduces our time by 100M.
Further, as mentioned, look at these reports:
https://stackoverflow.com/questions/40024425/1-2-840-113556-1-4-1941-ldap-ma...
"using LDAP_MATCHING_RULE_IN_CHAIN is much slower (in our case, a
factor of 10x) than simply doing the recursive "member-of" search that the above quote says LDAP_MATCHING_RULE_IN_CHAIN was intended to replace.
"
http://dunnry.com/blog/TransitiveLinkValueFilterEvaluation.aspx
" I expected the new filter to run circles around my code and I was
pretty shocked when the reverse was actually true ... transitive filter (409ms) as compared to only (41ms) using the recursive search.
"
https://stackoverflow.com/questions/6143665/single-line-ldap-query-that-enum...
" It works, although the query is slow as hell (~5-10 seconds) "
https://stackoverflow.com/questions/9534669/improving-recursive-active-direc...
" Code I am using as per JPBlancs's suggestion, whilst this works, it is
much slower than my original, am I implementing it incorreclty?"
The problem with memberof is that it updates the target entry. So it
is beneficial only if you later search 'memberof'. If you do not it is a waste of time. Also memberof is very demanding, you need to keep the plugin always enabled to trust the result.
This is a *good thing*. This is the whole point of this trade. We trade
write path time and storage for huge improvement in read path time. Especially relevant given that ldap is massively read oriented.
We have seen many cases where memberof was disabled during some admin
tasks then reenabled/fixup. So it is not comparing a bad 'in chain' solution vs a perfect 'memberof' solution, both have benefits/drawbacks.
I have previously stated how our MemberOf algorithm is slow and how we
could fix it. I have provided proof of these algorithmic improvements, but those suggestions were not applied.
Finally I have to admit, may be I auto convinced myself ;), that this
matching rule provides a quite elegant membership processing without requiring plugins/config. For example with a same MR you can lookup both sides of the memberships (toward the members or toward the groups). (memberof:inChainMatch:=cn=bar) will give all the members of group 'cn=bar' while (member:inChainMatch:=uid=foo) will give all the groups foo is memberof.
I don't know how to express this but I'm extraordinarily concerned
about the impact of this RFE. I think the performance impact has not been considered accurately, and I think it will only compound the performance issues we have within IPA. Especially once we combine with the many pre-existing IPA integration specific performance issues that have repeatedly gone ignored (related to the ipa plugins for ds).
In order for me to be happy with this RFE as an extension, I would ask
that:
- This MUST be a plugin, and ship default disabled.
- Test cases MUST include group cycles and nesting to deep levels. IE a
cycle of 100 items long or similar. We need to prove that we can cycle break since there is a risk of infinite loop and deadlock with this plugin.
- The implementation must be iterative and not recursive else we may
hit stack depth limits.
Implementation - EITHER:
- This OID internally uses memberOf attributes to perform the
resolution IE
- (member:1.2.840.113556.1.4.1941:=CN=User1,OU=X,DC=domain,DC=com)
-- internally we just search the user, retrieve it's memberOf (which we already have and is pre-computed with nesting) and return the set of groups.
- (memberOf:1.2.840.113556.1.4.1941:=CN=A
Group,OU=Y,DC=domain,DC=com) -- A no-op, since we already have nesting in memberOf, we just return the result directly.
We already have memberOf, and it's already done the work - let's use
that information.
- If the results of this search are virtualAttributes and cached such
that repeat searches hit the cache and do not stress the server.
I think having this without a virtual attr cache, or without using
existing memberof infrastructure is a recipe for disaster.
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
389-devel mailing list -- 389-devel@lists.fedoraproject.org To unsubscribe send an email to 389-devel-leave@lists.fedoraproject.org Fedora Code of Conduct: https://docs.fedoraproject.org/en-US/project/code-of-conduct/ List Guidelines: https://fedoraproject.org/wiki/Mailing_list_guidelines List Archives: https://lists.fedoraproject.org/archives/list/389-devel@lists.fedoraproject.... Do not reply to spam on the list, report it: https://pagure.io/fedora-infrastructure
Hi,
Twenty years that I work in LDAP area and twenty years that I see debate on the best way to look for group membership ! -;) And simply because there is no universal answer: ismemberof is typically better than the standard lookup if a user belongs to few large groups and that is the opposite if user belongs to lots of small groups. So IMHO debating whether ismemberof is better than the chaining matching rules has not much interest. As I perceive things the chaining matching rule has the advantage of being faster than the standard lookup because there is less overhead So IMHO having both ismemberof ans chain matching rule makes sense (even if only one of these mechanism should be deployed)
As I perceive thing, The way to determine group membership is indeed a trade off and it depends a lot of the group organization (in peculiar the number of groups and the group size (including all nesting level) So I suspect that whether chaining will be faster or slower than ismemberof lookup will depend.
at is indeed a trade-off.
On Tue, Feb 15, 2022 at 2:25 PM Pierre Rogier progier@redhat.com wrote:
On Tue, Feb 15, 2022 at 12:36 AM William Brown william.brown@suse.com wrote:
On 14 Feb 2022, at 23:23, Thierry Bordaz tbordaz@redhat.com wrote:
Hi William,
As usual I want to thank you a lot for all those precious and detailed
feedbacks. I will try to summarize your points and to answer them. If I forget a point, please just give me a head up.
All good mate :)
• Performance: The InChain search request is expensive, may put
high pressure on the server and we should have a mean to protect the server.
I agree that to follow membership link has a cost, a risk (infinite
loop) and impacts the server.
On the cost aspect I meant that MR computation (membership traversal)
of a *single* search should be much faster than (membership traversal) during memberof plugin call because memberof triggers the same set of searches and in addition updates the members. This being said, I fully agree that it is much more efficient to do a regular SRCH req '(memberof=cn=bar)' than '(member:1.2.840.113556.1.4.1941:=cn=bar)' and
So there is a very major piece of context that you might be missing here. Since this is related to the (unhealthy obsession) with FreeIPA slowly morphing into AD, there are AD specific behaviours we need to remember in this proposal.
MS AD Technical Specification - https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-adts/d243592...
In AD, memberOf is constructed using what's called a "back link attribute" ([MS-ADTS] - v20210625, page 27 ). These back links are derived and inverse from a forward link. If my memory serves correctly, you can consider these as a "pointer". Rather than how we store member / member of with dn's such as:
┌───────────────────┐ ┌───────────────────┐ │ │ │ │ │dn: cn=group ◀─ ─ ┼ ─ ─ ┐┌──────────▶│dn: uid=user │ │member: uid=user───┼──────┴ ─ ─ ─ ─ ─ │memberOf: cn=group │ │ │ │ │ └───────────────────┘ └───────────────────┘
AD stores these links as a pointer:
┌───────────────────┐ ┌───────────────────┐ │ │ │ │ │dn: cn=group │ │dn: uid=user │ │linkId: 1 ◀ ─ ─ ─ ┼ ─ ┐┌────────────▶│linkId: 2 │ │member: 2 ────────┼────┴ ─ ─ ─ ─ ─ ─ │memberOf: 1 │ │ │ │ │ └───────────────────┘ └───────────────────┘
Now, importantly this means that memberOf on AD is NOT able to represent nested groups because:
""" A forward link attribute can exist with no corresponding back link attribute, but not vice-versa. """
What this means is that you can express a member (forward link) and direct memberOf (back link) but not a nested group.
┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐ │ │ │dn: cn=group │ │ │ │dn: cn=group │ ┌────────────▶│linkId: 2 ◀─ ─ ─ ─│─ ─ │dn: uid=user │ │linkId: 1 ◀ ─ ─ ─ ─│─ ┐│ │member: 3 ─────────┼───┼────────────▶ │linkId: 3 │ │member: 2 ─────────┼───┴ ─ ─ ─ ─ ─ ─ │memberOf: 1 │ ─ ─ ─ ─ ─ ─ ─ │memberOf: 2 │ │ │ │ │ │ │ └───────────────────┘ └───────────────────┘ └───────────────────┘
If we were to add memberOf for linkId: 1 notice:
┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐ │ │ │dn: cn=group │ │ │ │dn: cn=group │ ┌────────────▶│linkId: 2 ◀─ ─ ─ ─│─ ─ │dn: uid=user │ │linkId: 1 ◀ ─ ─ ─ ─│─ ┐│ │member: 3 ─────────┼───┼────────────▶ │linkId: 3 │ │member: 2 ─────────┼──┼┴ ─ ─ ─ ─ ─ ─ │memberOf: 1 │ ─ ─ ─ ─ ─ ─ ─ │memberOf: 2 │ │ │ │ │ ││memberOf: 1 │ └───────────────────┘ │ └───────────────────┘ └───────────────────┘
│ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
There is no *forward link* from linkId 1 to user (memberOf 1), thus violating the constraints of link attributes in AD.
This means that in AD memberOf values are not nested and can not express or show nested groups. This is what the chain-link oid solves - since this follows each stack of the links building up the complete group graph, chain link IS able to show group nesting.
a clever application should prefer 'memberof'.
Because of this fact, a clever application that wants *nested groups* can NOT use memberOf in an AD environment, and is forced to rely on the link chain oid. There is also no magic sauce that an application will see or know about to know they are in a FreeIPA hybrid AD monster, which lets them know that our memberOf state is a full and complete group graph with nesting included so they can prefer that.
The main drawback of 'memberof' option is that it only works for
'memberof' attribute. While InChain works for any membership attribute.
But the main usage of this will be memberships to groups due to the nesting details above. Groups also tend to have larger and more complex structures. That's why this is a focus.
Regarding the risk of infinite loop, the current memberof_get_groups()
has a loop detection mechanism.
Regarding the impact of the server, you mentioned to enforce a limit of
nesting. I agree with this idea and worth to be added to https://github.com/389ds/389-ds-base/issues/5156
Regarding https://github.com/389ds/389-ds-base/issues/5156, I think it
is a good time to implement/compare current memberof_get_group implementation with your previous proposal.
Sure, it seems like a good idea. My "previous proposal" is already in use in kanidm, and it's extremely fast for memberOf updates compared to 389.
I think that it would be hugely value for us to consider memberOf a "default and required" element of the server, and to improve it as such. That way our get_group capabilities can just search on memberOf which should be a single search.
• Impact of the RFE on the server
Once registered the InChain MR is presented as supported MR on base
DSE. That is the only impact until a SRCH use the MR. Should we limit SRCH InChain to list of bound DN ?
I think we should have aci's to limit access to this yes. Alternately, it should have a cn=config switch to enable/disable this control, and it ships default disabled.
Regarding performance risk, I think it would be somehow similar to what
a deref control is (deref drawback being aci while InChain would be nested membership) and there is no limit to the use of deref control.
So IMHO there is no consequence on the server of supporting or not this
RFE.
• InChain being a plugin
It is a plugin (syntax), the change is the move of nested memberships
searches into a slapi private function.
• Using iteration rather than recursive
Knowing that there is a loop detection mechanism, I see not a huge
benefit of iteration vs recursive. Indeed in identity membership we can not anticipated huge nesting.
Iteration won't cause your whole server instance to panic and crash because of a weird group setup.
• Shortcut InChain 'member' and 'memberof' into a use of
'memberof' attribute looks a very nice idea. Documentation should warn that InChain 'member' relies on 'memberof' properly updated (risk of enable/disable memberof plugin)
Yep - we already have that data, so we can rely on it and use it. I think we should change memberOf to enabled by default TBH.
• membership attribute being a virtual attribute, is a bad idea.
This will results in unindexed searches. Caching result is not possible as virtual attribute evaluation may differ between two searches. May be I misunderstand how you intend to use virtual attribute in such case.
best regards thierry
On 2/14/22 12:23 AM, William Brown wrote:
On 11 Feb 2022, at 19:47, Thierry Bordaz tbordaz@redhat.com wrote:
Thank you William for diving into that RFE with as always very good
points. I will try to answer.
You are right it is a requirement coming from IPA where future IPA
instance will have to support MS client issuing In chain requests. I am not convince it will be very frequent req. It is even possible that this RFE is a kind of supported MR we need for conformity reasons.
Knew it :)
The request triggers a set of recursive read operations. So it
differs from memberof plugin that, does the reads and also update the target entry with memberof values. So it will be by far (I hope) faster than memberof plugin. The drawback is that the result of the computation is lost (not written) so there is no way to benefit from previous req.
It will NOT be faster.
MemberOf is a fundamental trade - trading time during the write path
to examine groups and then store these, so that we achieve in a reduction in processing time in the read path.
The plugin is the exact opposite. By saving in the write path (doing
nothing), we have to do *all the work* in the read path. LDAP is also a read mostly system, meaning that we are making the exact wrong choice to go down a path to try to generate this in the read op.
Let's consider a write takes some time value defined as W . And let's
assume that the member of takes some time value defined as M. And a read takes time R.
If we have memberof, with 1 write and 100 reads we have:
1(W + M) 100(R)
With In Chain we have:
1(W) 100(R + M)
So we've increased our work and time by 100M just by moving this. If
you want to look at it the other way, MemberOf reduces our time by 100M.
Further, as mentioned, look at these reports:
https://stackoverflow.com/questions/40024425/1-2-840-113556-1-4-1941-ldap-ma...
"using LDAP_MATCHING_RULE_IN_CHAIN is much slower (in our case, a
factor of 10x) than simply doing the recursive "member-of" search that the above quote says LDAP_MATCHING_RULE_IN_CHAIN was intended to replace.
"
http://dunnry.com/blog/TransitiveLinkValueFilterEvaluation.aspx
" I expected the new filter to run circles around my code and I was
pretty shocked when the reverse was actually true ... transitive filter (409ms) as compared to only (41ms) using the recursive search.
"
https://stackoverflow.com/questions/6143665/single-line-ldap-query-that-enum...
" It works, although the query is slow as hell (~5-10 seconds) "
https://stackoverflow.com/questions/9534669/improving-recursive-active-direc...
" Code I am using as per JPBlancs's suggestion, whilst this works, it is
much slower than my original, am I implementing it incorreclty?"
The problem with memberof is that it updates the target entry. So it
is beneficial only if you later search 'memberof'. If you do not it is a waste of time. Also memberof is very demanding, you need to keep the plugin always enabled to trust the result.
This is a *good thing*. This is the whole point of this trade. We
trade write path time and storage for huge improvement in read path time. Especially relevant given that ldap is massively read oriented.
We have seen many cases where memberof was disabled during some admin
tasks then reenabled/fixup. So it is not comparing a bad 'in chain' solution vs a perfect 'memberof' solution, both have benefits/drawbacks.
I have previously stated how our MemberOf algorithm is slow and how we
could fix it. I have provided proof of these algorithmic improvements, but those suggestions were not applied.
Finally I have to admit, may be I auto convinced myself ;), that this
matching rule provides a quite elegant membership processing without requiring plugins/config. For example with a same MR you can lookup both sides of the memberships (toward the members or toward the groups). (memberof:inChainMatch:=cn=bar) will give all the members of group 'cn=bar' while (member:inChainMatch:=uid=foo) will give all the groups foo is memberof.
I don't know how to express this but I'm extraordinarily concerned
about the impact of this RFE. I think the performance impact has not been considered accurately, and I think it will only compound the performance issues we have within IPA. Especially once we combine with the many pre-existing IPA integration specific performance issues that have repeatedly gone ignored (related to the ipa plugins for ds).
In order for me to be happy with this RFE as an extension, I would ask
that:
- This MUST be a plugin, and ship default disabled.
- Test cases MUST include group cycles and nesting to deep levels. IE
a cycle of 100 items long or similar. We need to prove that we can cycle break since there is a risk of infinite loop and deadlock with this plugin.
- The implementation must be iterative and not recursive else we may
hit stack depth limits.
Implementation - EITHER:
- This OID internally uses memberOf attributes to perform the
resolution IE
- (member:1.2.840.113556.1.4.1941:=CN=User1,OU=X,DC=domain,DC=com)
-- internally we just search the user, retrieve it's memberOf (which we already have and is pre-computed with nesting) and return the set of groups.
- (memberOf:1.2.840.113556.1.4.1941:=CN=A
Group,OU=Y,DC=domain,DC=com) -- A no-op, since we already have nesting in memberOf, we just return the result directly.
We already have memberOf, and it's already done the work - let's use
that information.
- If the results of this search are virtualAttributes and cached such
that repeat searches hit the cache and do not stress the server.
I think having this without a virtual attr cache, or without using
existing memberof infrastructure is a recipe for disaster.
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
389-devel mailing list -- 389-devel@lists.fedoraproject.org To unsubscribe send an email to 389-devel-leave@lists.fedoraproject.org Fedora Code of Conduct: https://docs.fedoraproject.org/en-US/project/code-of-conduct/ List Guidelines: https://fedoraproject.org/wiki/Mailing_list_guidelines List Archives: https://lists.fedoraproject.org/archives/list/389-devel@lists.fedoraproject.... Do not reply to spam on the list, report it: https://pagure.io/fedora-infrastructure
Hi,
Twenty years that I work in LDAP area and twenty years that I see debate on the best way to look for group membership ! -;) And simply because there is no universal answer: ismemberof is typically better than the standard lookup if a user belongs to few large groups and that is the opposite if user belongs to lots of small groups. So IMHO debating whether ismemberof is better than the chaining matching rules has not much interest. As I perceive things the chaining matching rule has the advantage of being faster than the standard lookup because there is less overhead So IMHO having both ismemberof ans chain matching rule makes sense (even if only one of these mechanism should be deployed)
(Sorry I fumbled my previous answer and unwillingly sent the answer that
was in progress)
A few other points. - We should be careful to check that we have the right to access the groups (otherwise there will be security issues) - We should only support the matching rule if it is indexed. ( so no need to have a specific control to accept it or not)
Regards Pierre
--
389 Directory Server Development Team
Hi,
Twenty years that I work in LDAP area and twenty years that I see debate on the best way to look for group membership ! -;) And simply because there is no universal answer: ismemberof is typically better than the standard lookup if a user belongs to few large groups and that is the opposite if user belongs to lots of small groups.
I disagree, there is only one answer, and it's to pre-compute those values into memberOf. There is no way that dynamic calculation could ever be faster than pre-building this information.
So IMHO debating whether ismemberof is better than the chaining matching rules has not much interest. As I perceive things the chaining matching rule has the advantage of being faster than the standard lookup because there is less overhead So IMHO having both ismemberof ans chain matching rule makes sense (even if only one of these mechanism should be deployed)
Well, it is because applications don't adapt based on what's best for the LDAP server - applications just want "group info" and *we* need to make decisions and design choices that impact the performance of these different cases.
As above - applications in AD land have become accustomed to asking for the chain style rule to get nested groups. We can not assume an application will "do what's best for us". We have to assume worst cases, and what impact that will have.
(Sorry I fumbled my previous answer and unwillingly sent the answer that was in progress)
A few other points.
- We should be careful to check that we have the right to access the groups (otherwise there will be security issues)
Yes, this is true. If we used my suggestion of chaining consuming memberOf, then we could inherit that information naturally.
- We should only support the matching rule if it is indexed. ( so no need to have a specific control to accept it or not)
Yes, if we are evaluating it in the manner as documented by the AD implementation then we should only allow indexed searches.
Regards Pierre
--
389 Directory Server Development Team
--
389 Directory Server Development Team _______________________________________________ 389-devel mailing list -- 389-devel@lists.fedoraproject.org To unsubscribe send an email to 389-devel-leave@lists.fedoraproject.org Fedora Code of Conduct: https://docs.fedoraproject.org/en-US/project/code-of-conduct/ List Guidelines: https://fedoraproject.org/wiki/Mailing_list_guidelines List Archives: https://lists.fedoraproject.org/archives/list/389-devel@lists.fedoraproject.... Do not reply to spam on the list, report it: https://pagure.io/fedora-infrastructure
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
On 2/16/22 12:33 AM, William Brown wrote:
Hi,
Twenty years that I work in LDAP area and twenty years that I see debate on the best way to look for group membership ! -;) And simply because there is no universal answer: ismemberof is typically better than the standard lookup if a user belongs to few large groups and that is the opposite if user belongs to lots of small groups.
I disagree, there is only one answer, and it's to pre-compute those values into memberOf. There is no way that dynamic calculation could ever be faster than pre-building this information.
If I understand your point I have to say it has some limits. Managing link attribute has a cost, in term of updates, index computation, admin task to properly configure the components (plugin) that will manage the attribute. For example, if we implement InChain MR and want to support SRCH like '(manager:1.2.840.113556.1.4.1941:=uid=foo)' using a pre-compute value 'managedBy', that mean configuring a membor_manager like plugin, RI_manager plugin,... have a significant overload on updates and db size, for an attribute that we may never use (if no application will lauch a InChain 'manager').
What I find elegant on this MR is that whatever the server configuration is, you get the result. Even if, I agree with your proposal, internally the server translates a '(member:1.2.840.113556.1.4.1941:=cn=bar)' into '(memberof=cn=bar)' and get benefit of memberof/RI plugins.
regards thierry
So IMHO debating whether ismemberof is better than the chaining matching rules has not much interest. As I perceive things the chaining matching rule has the advantage of being faster than the standard lookup because there is less overhead So IMHO having both ismemberof ans chain matching rule makes sense (even if only one of these mechanism should be deployed)
Well, it is because applications don't adapt based on what's best for the LDAP server - applications just want "group info" and *we* need to make decisions and design choices that impact the performance of these different cases.
As above - applications in AD land have become accustomed to asking for the chain style rule to get nested groups. We can not assume an application will "do what's best for us". We have to assume worst cases, and what impact that will have.
(Sorry I fumbled my previous answer and unwillingly sent the answer that was in progress)
A few other points.
- We should be careful to check that we have the right to access the groups (otherwise there will be security issues)
Yes, this is true. If we used my suggestion of chaining consuming memberOf, then we could inherit that information naturally.
- We should only support the matching rule if it is indexed. ( so no need to have a specific control to accept it or not)
Yes, if we are evaluating it in the manner as documented by the AD implementation then we should only allow indexed searches.
Regards Pierre
--
389 Directory Server Development Team
--
389 Directory Server Development Team _______________________________________________ 389-devel mailing list -- 389-devel@lists.fedoraproject.org To unsubscribe send an email to 389-devel-leave@lists.fedoraproject.org Fedora Code of Conduct: https://docs.fedoraproject.org/en-US/project/code-of-conduct/ List Guidelines: https://fedoraproject.org/wiki/Mailing_list_guidelines List Archives: https://lists.fedoraproject.org/archives/list/389-devel@lists.fedoraproject.... Do not reply to spam on the list, report it: https://pagure.io/fedora-infrastructure
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
On 2/15/22 12:35 AM, William Brown wrote:
On 14 Feb 2022, at 23:23, Thierry Bordaz tbordaz@redhat.com wrote:
Hi William,
As usual I want to thank you a lot for all those precious and detailed feedbacks. I will try to summarize your points and to answer them. If I forget a point, please just give me a head up.
All good mate :)
• Performance: The InChain search request is expensive, may put high pressure on the server and we should have a mean to protect the server.
I agree that to follow membership link has a cost, a risk (infinite loop) and impacts the server.
On the cost aspect I meant that MR computation (membership traversal) of a *single* search should be much faster than (membership traversal) during memberof plugin call because memberof triggers the same set of searches and in addition updates the members. This being said, I fully agree that it is much more efficient to do a regular SRCH req '(memberof=cn=bar)' than '(member:1.2.840.113556.1.4.1941:=cn=bar)' and
So there is a very major piece of context that you might be missing here. Since this is related to the (unhealthy obsession) with FreeIPA slowly morphing into AD, there are AD specific behaviours we need to remember in this proposal.
MS AD Technical Specification - https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-adts/d243592...
In AD, memberOf is constructed using what's called a "back link attribute" ([MS-ADTS] - v20210625, page 27 ). These back links are derived and inverse from a forward link. If my memory serves correctly, you can consider these as a "pointer". Rather than how we store member / member of with dn's such as:
┌───────────────────┐ ┌───────────────────┐ │ │ │ │ │dn: cn=group ◀─ ─ ┼ ─ ─ ┐┌──────────▶│dn: uid=user │ │member: uid=user───┼──────┴ ─ ─ ─ ─ ─ │memberOf: cn=group │ │ │ │ │ └───────────────────┘ └───────────────────┘
AD stores these links as a pointer:
┌───────────────────┐ ┌───────────────────┐ │ │ │ │ │dn: cn=group │ │dn: uid=user │ │linkId: 1 ◀ ─ ─ ─ ┼ ─ ┐┌────────────▶│linkId: 2 │ │member: 2 ────────┼────┴ ─ ─ ─ ─ ─ ─ │memberOf: 1 │ │ │ │ │ └───────────────────┘ └───────────────────┘
Now, importantly this means that memberOf on AD is NOT able to represent nested groups because:
""" A forward link attribute can exist with no corresponding back link attribute, but not vice-versa. """
What this means is that you can express a member (forward link) and direct memberOf (back link) but not a nested group.
┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐ │ │ │dn: cn=group │ │ │ │dn: cn=group │ ┌────────────▶│linkId: 2 ◀─ ─ ─ ─│─ ─ │dn: uid=user │ │linkId: 1 ◀ ─ ─ ─ ─│─ ┐│ │member: 3 ─────────┼───┼────────────▶ │linkId: 3 │ │member: 2 ─────────┼───┴ ─ ─ ─ ─ ─ ─ │memberOf: 1 │ ─ ─ ─ ─ ─ ─ ─ │memberOf: 2 │ │ │ │ │ │ │ └───────────────────┘ └───────────────────┘ └───────────────────┘
If we were to add memberOf for linkId: 1 notice:
┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐ │ │ │dn: cn=group │ │ │ │dn: cn=group │ ┌────────────▶│linkId: 2 ◀─ ─ ─ ─│─ ─ │dn: uid=user │ │linkId: 1 ◀ ─ ─ ─ ─│─ ┐│ │member: 3 ─────────┼───┼────────────▶ │linkId: 3 │ │member: 2 ─────────┼──┼┴ ─ ─ ─ ─ ─ ─ │memberOf: 1 │ ─ ─ ─ ─ ─ ─ ─ │memberOf: 2 │ │ │ │ │ ││memberOf: 1 │ └───────────────────┘ │ └───────────────────┘ └───────────────────┘ │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
There is no *forward link* from linkId 1 to user (memberOf 1), thus violating the constraints of link attributes in AD.
This means that in AD memberOf values are not nested and can not express or show nested groups. This is what the chain-link oid solves - since this follows each stack of the links building up the complete group graph, chain link IS able to show group nesting.
a clever application should prefer 'memberof'.
Because of this fact, a clever application that wants *nested groups* can NOT use memberOf in an AD environment, and is forced to rely on the link chain oid. There is also no magic sauce that an application will see or know about to know they are in a FreeIPA hybrid AD monster, which lets them know that our memberOf state is a full and complete group graph with nesting included so they can prefer that.
The main drawback of 'memberof' option is that it only works for 'memberof' attribute. While InChain works for any membership attribute.
But the main usage of this will be memberships to groups due to the nesting details above. Groups also tend to have larger and more complex structures. That's why this is a focus.
Regarding the risk of infinite loop, the current memberof_get_groups() has a loop detection mechanism.
Regarding the impact of the server, you mentioned to enforce a limit of nesting. I agree with this idea and worth to be added to https://github.com/389ds/389-ds-base/issues/5156
Regarding https://github.com/389ds/389-ds-base/issues/5156, I think it is a good time to implement/compare current memberof_get_group implementation with your previous proposal.
Sure, it seems like a good idea. My "previous proposal" is already in use in kanidm, and it's extremely fast for memberOf updates compared to 389.
I think that it would be hugely value for us to consider memberOf a "default and required" element of the server, and to improve it as such. That way our get_group capabilities can just search on memberOf which should be a single search.
• Impact of the RFE on the server
Once registered the InChain MR is presented as supported MR on base DSE. That is the only impact until a SRCH use the MR. Should we limit SRCH InChain to list of bound DN ?
I think we should have aci's to limit access to this yes. Alternately, it should have a cn=config switch to enable/disable this control, and it ships default disabled.
Regarding performance risk, I think it would be somehow similar to what a deref control is (deref drawback being aci while InChain would be nested membership) and there is no limit to the use of deref control. So IMHO there is no consequence on the server of supporting or not this RFE.
• InChain being a plugin It is a plugin (syntax), the change is the move of nested memberships searches into a slapi private function.
• Using iteration rather than recursive Knowing that there is a loop detection mechanism, I see not a huge benefit of iteration vs recursive. Indeed in identity membership we can not anticipated huge nesting.
Iteration won't cause your whole server instance to panic and crash because of a weird group setup.
• Shortcut InChain 'member' and 'memberof' into a use of 'memberof' attribute looks a very nice idea. Documentation should warn that InChain 'member' relies on 'memberof' properly updated (risk of enable/disable memberof plugin)
Yep - we already have that data, so we can rely on it and use it. I think we should change memberOf to enabled by default TBH.
Updating the design with your feedback I am facing a difficulty. There is a kind of agreement that a search like '|(member:1.2.840.113556.1.4.1941:=uid=foo,dc=com)'| || that computes all groups 'foo' is memberof, should shortcut the membership computation to use 'memberof' value that is in 'foo' entry.
My concern is related to access control. Let assume we have
dn: G0 member: G1
dn: G1 member: G2
dn: G2 member: foo
dn: foo memberof: G0 memberof: G1 memberof: G2
Then ACI definition, allows (to the inChain bound user) read/search access to
* 'memberof' on 'foo' * 'member' on G2 and G0 but not on G1.
InChain MR computation will retrieve G2 (because of access granted on G2.member), then will not retrieve G1 (because of lack of rights to access to G1.member) and so not retrieve G0. => returns 'G2'
Shortcut InChain MR, retrieve G0, G1 and G2 (because of access granted to foo.memberof). If it returns G0, G1, G2 it violates lack of access to G1. If it tests access of 'member' on G0, G1, G2. It may return G0 and G2 (because access is granted) but it violates the fact that G0 was hidden behind G1. So even if the 'member' are pre-computed, we still have to access (srch) each of the member value to evaluate rights and also to create a graph of the membership to detect "hidden" entries. In clear I am unsure of the benefit of the shortcut
any thoughts.
best regards thierry
||
• membership attribute being a virtual attribute, is a bad idea. This will results in unindexed searches. Caching result is not possible as virtual attribute evaluation may differ between two searches. May be I misunderstand how you intend to use virtual attribute in such case. best regards thierry
On 2/14/22 12:23 AM, William Brown wrote:
On 11 Feb 2022, at 19:47, Thierry Bordaz tbordaz@redhat.com wrote:
Thank you William for diving into that RFE with as always very good points. I will try to answer.
You are right it is a requirement coming from IPA where future IPA instance will have to support MS client issuing In chain requests. I am not convince it will be very frequent req. It is even possible that this RFE is a kind of supported MR we need for conformity reasons.
Knew it :)
The request triggers a set of recursive read operations. So it differs from memberof plugin that, does the reads and also update the target entry with memberof values. So it will be by far (I hope) faster than memberof plugin. The drawback is that the result of the computation is lost (not written) so there is no way to benefit from previous req.
It will NOT be faster.
MemberOf is a fundamental trade - trading time during the write path to examine groups and then store these, so that we achieve in a reduction in processing time in the read path.
The plugin is the exact opposite. By saving in the write path (doing nothing), we have to do *all the work* in the read path. LDAP is also a read mostly system, meaning that we are making the exact wrong choice to go down a path to try to generate this in the read op.
Let's consider a write takes some time value defined as W . And let's assume that the member of takes some time value defined as M. And a read takes time R.
If we have memberof, with 1 write and 100 reads we have:
1(W + M) 100(R)
With In Chain we have:
1(W) 100(R + M)
So we've increased our work and time by 100M just by moving this. If you want to look at it the other way, MemberOf reduces our time by 100M.
Further, as mentioned, look at these reports:
https://stackoverflow.com/questions/40024425/1-2-840-113556-1-4-1941-ldap-ma...
"using LDAP_MATCHING_RULE_IN_CHAIN is much slower (in our case, a factor of 10x) than simply doing the recursive "member-of" search that the above quote says LDAP_MATCHING_RULE_IN_CHAIN was intended to replace. "
http://dunnry.com/blog/TransitiveLinkValueFilterEvaluation.aspx
" I expected the new filter to run circles around my code and I was pretty shocked when the reverse was actually true ... transitive filter (409ms) as compared to only (41ms) using the recursive search. "
https://stackoverflow.com/questions/6143665/single-line-ldap-query-that-enum...
" It works, although the query is slow as hell (~5-10 seconds) "
https://stackoverflow.com/questions/9534669/improving-recursive-active-direc...
" Code I am using as per JPBlancs's suggestion, whilst this works, it is much slower than my original, am I implementing it incorreclty?"
The problem with memberof is that it updates the target entry. So it is beneficial only if you later search 'memberof'. If you do not it is a waste of time. Also memberof is very demanding, you need to keep the plugin always enabled to trust the result.
This is a *good thing*. This is the whole point of this trade. We trade write path time and storage for huge improvement in read path time. Especially relevant given that ldap is massively read oriented.
We have seen many cases where memberof was disabled during some admin tasks then reenabled/fixup. So it is not comparing a bad 'in chain' solution vs a perfect 'memberof' solution, both have benefits/drawbacks.
I have previously stated how our MemberOf algorithm is slow and how we could fix it. I have provided proof of these algorithmic improvements, but those suggestions were not applied.
Finally I have to admit, may be I auto convinced myself ;), that this matching rule provides a quite elegant membership processing without requiring plugins/config. For example with a same MR you can lookup both sides of the memberships (toward the members or toward the groups). (memberof:inChainMatch:=cn=bar) will give all the members of group 'cn=bar' while (member:inChainMatch:=uid=foo) will give all the groups foo is memberof.
I don't know how to express this but I'm extraordinarily concerned about the impact of this RFE. I think the performance impact has not been considered accurately, and I think it will only compound the performance issues we have within IPA. Especially once we combine with the many pre-existing IPA integration specific performance issues that have repeatedly gone ignored (related to the ipa plugins for ds).
In order for me to be happy with this RFE as an extension, I would ask that:
- This MUST be a plugin, and ship default disabled.
- Test cases MUST include group cycles and nesting to deep levels. IE a cycle of 100 items long or similar. We need to prove that we can cycle break since there is a risk of infinite loop and deadlock with this plugin.
- The implementation must be iterative and not recursive else we may hit stack depth limits.
Implementation - EITHER:
- This OID internally uses memberOf attributes to perform the resolution IE
We already have memberOf, and it's already done the work - let's use that information.
- (member:1.2.840.113556.1.4.1941:=CN=User1,OU=X,DC=domain,DC=com) -- internally we just search the user, retrieve it's memberOf (which we already have and is pre-computed with nesting) and return the set of groups.
- (memberOf:1.2.840.113556.1.4.1941:=CN=A Group,OU=Y,DC=domain,DC=com) -- A no-op, since we already have nesting in memberOf, we just return the result directly.
- If the results of this search are virtualAttributes and cached such that repeat searches hit the cache and do not stress the server.
I think having this without a virtual attr cache, or without using existing memberof infrastructure is a recipe for disaster.
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
• Shortcut InChain 'member' and 'memberof' into a use of 'memberof' attribute looks a very nice idea. Documentation should warn that InChain 'member' relies on 'memberof' properly updated (risk of enable/disable memberof plugin)
Yep - we already have that data, so we can rely on it and use it. I think we should change memberOf to enabled by default TBH.
Updating the design with your feedback I am facing a difficulty. There is a kind of agreement that a search like '(member:1.2.840.113556.1.4.1941:=uid=foo,dc=com)' that computes all groups 'foo' is memberof, should shortcut the membership computation to use 'memberof' value that is in 'foo' entry.
My concern is related to access control. Let assume we have
dn: G0 member: G1
dn: G1 member: G2
dn: G2 member: foo
dn: foo memberof: G0 memberof: G1 memberof: G2
Then ACI definition, allows (to the inChain bound user) read/search access to
• 'memberof' on 'foo' • 'member' on G2 and G0 but not on G1. InChain MR computation will retrieve G2 (because of access granted on G2.member), then will not retrieve G1 (because of lack of rights to access to G1.member) and so not retrieve G0. => returns 'G2'
Shortcut InChain MR, retrieve G0, G1 and G2 (because of access granted to foo.memberof). If it returns G0, G1, G2 it violates lack of access to G1. If it tests access of 'member' on G0, G1, G2. It may return G0 and G2 (because access is granted) but it violates the fact that G0 was hidden behind G1. So even if the 'member' are pre-computed, we still have to access (srch) each of the member value to evaluate rights and also to create a graph of the membership to detect "hidden" entries. In clear I am unsure of the benefit of the shortcut
The benefit is "not wrecking server performance".
Even in freeipa, memberOf is not hidden ... I can't think of any situation where it is hidden ...
Today, the inverse risk exists. You can't read member from group hidden, but you can see user X is memberof: hidden. But we don't seem to worry about "that" for access controls.
Or even nsRoles? We also don't seem to worry about dynamic groups for that. Or cos templates. Or many of the other ways we generate attributes .... There is ALWAYS a trade here of exposing infomation via a generated attribute that a user otherwise couldn't ask for
If someone truly was "that worried" about access to this attribute they need to disable memberOf and this inchain control.
any thoughts.
best regards thierry
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
On 2/24/22 1:06 AM, William Brown wrote:
• Shortcut InChain 'member' and 'memberof' into a use of 'memberof' attribute looks a very nice idea. Documentation should warn that InChain 'member' relies on 'memberof' properly updated (risk of enable/disable memberof plugin)
Yep - we already have that data, so we can rely on it and use it. I think we should change memberOf to enabled by default TBH.
Updating the design with your feedback I am facing a difficulty. There is a kind of agreement that a search like '(member:1.2.840.113556.1.4.1941:=uid=foo,dc=com)' that computes all groups 'foo' is memberof, should shortcut the membership computation to use 'memberof' value that is in 'foo' entry.
My concern is related to access control. Let assume we have
dn: G0 member: G1
dn: G1 member: G2
dn: G2 member: foo
dn: foo memberof: G0 memberof: G1 memberof: G2
Then ACI definition, allows (to the inChain bound user) read/search access to
• 'memberof' on 'foo' • 'member' on G2 and G0 but not on G1. InChain MR computation will retrieve G2 (because of access granted on G2.member), then will not retrieve G1 (because of lack of rights to access to G1.member) and so not retrieve G0. => returns 'G2'
Shortcut InChain MR, retrieve G0, G1 and G2 (because of access granted to foo.memberof). If it returns G0, G1, G2 it violates lack of access to G1. If it tests access of 'member' on G0, G1, G2. It may return G0 and G2 (because access is granted) but it violates the fact that G0 was hidden behind G1. So even if the 'member' are pre-computed, we still have to access (srch) each of the member value to evaluate rights and also to create a graph of the membership to detect "hidden" entries. In clear I am unsure of the benefit of the shortcut
The benefit is "not wrecking server performance".
Even in freeipa, memberOf is not hidden ... I can't think of any situation where it is hidden ...
Today, the inverse risk exists. You can't read member from group hidden, but you can see user X is memberof: hidden. But we don't seem to worry about "that" for access controls.
Or even nsRoles? We also don't seem to worry about dynamic groups for that. Or cos templates. Or many of the other ways we generate attributes .... There is ALWAYS a trade here of exposing infomation via a generated attribute that a user otherwise couldn't ask for
If someone truly was "that worried" about access to this attribute they need to disable memberOf and this inchain control.
I think that the user sending the request '(member:1.2.840.113556.1.4.1941:=uid=foo,dc=com)' should get the same result as if he is iterating through 'member' step by step (e.g sending '(member=uid=foo,dc=com)' -> G2, then sending '(member=G2)'-> NULL), the response should only be G2.
I agree that access control that limits access to 'member' but not 'memberof' will reveal a security issue but it is because of badly designed access control, not because of access control not being enforced.
IMHO we have two aspects to evaluate the benefit of the shortcut: candidate list and access control. The use of the shortcut, gives a faster lookup of the candidates than following the links. Access control is faster while following the links than on a raw list of candidates (need to recreate the graph).
any thoughts.
best regards thierry
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
The benefit is "not wrecking server performance".
Even in freeipa, memberOf is not hidden ... I can't think of any situation where it is hidden ...
Today, the inverse risk exists. You can't read member from group hidden, but you can see user X is memberof: hidden. But we don't seem to worry about "that" for access controls.
Or even nsRoles? We also don't seem to worry about dynamic groups for that. Or cos templates. Or many of the other ways we generate attributes .... There is ALWAYS a trade here of exposing infomation via a generated attribute that a user otherwise couldn't ask for
If someone truly was "that worried" about access to this attribute they need to disable memberOf and this inchain control.
I think that the user sending the request '(member:1.2.840.113556.1.4.1941:=uid=foo,dc=com)' should get the same result as if he is iterating through 'member' step by step (e.g sending '(member=uid=foo,dc=com)' -> G2, then sending '(member=G2)'-> NULL), the response should only be G2.
I agree that access control that limits access to 'member' but not 'memberof' will reveal a security issue but it is because of badly designed access control, not because of access control not being enforced.
IMHO we have two aspects to evaluate the benefit of the shortcut: candidate list and access control. The use of the shortcut, gives a faster lookup of the candidates than following the links. Access control is faster while following the links than on a raw list of candidates (need to recreate the graph).
I think this is not correct, and I think you are thinking about edge case problems that pretty much don't exist. FreeIPA makes all groups world readable. AD does too. Most directory systems ship with an access control to allow full read to all groups.
Our memberof already nests groups. So we can look at a user and see all groups they are memberof, even if we can't read the groups. So we are not disclosing any extra information here. In freeipa this is also true.
Ultimately it's up to you. So long as this feature is disabled by default so it can't be used by most people, I'm not bothered (bonus marks if you have it behind a ./configure feature flag so SUSE doesn't even need to compile it). I've given you my warning about the (serious) performance risks which will only compound with freeipa's already poor performance in AD trust mode.
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
On 2/25/22 2:04 AM, William Brown wrote:
The benefit is "not wrecking server performance".
Even in freeipa, memberOf is not hidden ... I can't think of any situation where it is hidden ...
Today, the inverse risk exists. You can't read member from group hidden, but you can see user X is memberof: hidden. But we don't seem to worry about "that" for access controls.
Or even nsRoles? We also don't seem to worry about dynamic groups for that. Or cos templates. Or many of the other ways we generate attributes .... There is ALWAYS a trade here of exposing infomation via a generated attribute that a user otherwise couldn't ask for
If someone truly was "that worried" about access to this attribute they need to disable memberOf and this inchain control.
I think that the user sending the request '(member:1.2.840.113556.1.4.1941:=uid=foo,dc=com)' should get the same result as if he is iterating through 'member' step by step (e.g sending '(member=uid=foo,dc=com)' -> G2, then sending '(member=G2)'-> NULL), the response should only be G2.
I agree that access control that limits access to 'member' but not 'memberof' will reveal a security issue but it is because of badly designed access control, not because of access control not being enforced.
IMHO we have two aspects to evaluate the benefit of the shortcut: candidate list and access control. The use of the shortcut, gives a faster lookup of the candidates than following the links. Access control is faster while following the links than on a raw list of candidates (need to recreate the graph).
I think this is not correct, and I think you are thinking about edge case problems that pretty much don't exist. FreeIPA makes all groups world readable. AD does too. Most directory systems ship with an access control to allow full read to all groups.
Our memberof already nests groups. So we can look at a user and see all groups they are memberof, even if we can't read the groups. So we are not disclosing any extra information here. In freeipa this is also true.
Good point, if majority of deployment do not control access to 'memberof' it is fair to use it. Now knowing that it could violate access control I think we should propose both. By default, inChain should use shortcut whenever it is possible (build candidates from memberof), then use a toggle off this shortcut and build the list from links and enforce ACI.
Ultimately it's up to you. So long as this feature is disabled by default so it can't be used by most people, I'm not bothered (bonus marks if you have it behind a ./configure feature flag so SUSE doesn't even need to compile it). I've given you my warning about the (serious) performance risks which will only compound with freeipa's already poor performance in AD trust mode.
Yes use of this feature will be limited (toggle and granted users).
Thanks William for this great discussion and precious feedbacks
thierry
-- Sincerely,
William Brown
Sesion Software Engineer, Identity and Access Management SUSE Labs, Australia
389-devel@lists.fedoraproject.org