From 0f6566e9a718ffcc4f09037ef879bb106a576961 Mon Sep 17 00:00:00 2001 From: rjung Date: Mon, 27 Apr 2009 18:54:55 +0000 Subject: [PATCH] BZ 46925: Improve search for nested roles in JNDIRealm by replacing recursive search with iterative search. Patch provided by Stefan Zoerner. git-svn-id: https://svn.apache.org/repos/asf/tomcat/trunk@769102 13f79535-47bb-0310-9956-ffa450edef68 --- java/org/apache/catalina/realm/JNDIRealm.java | 194 +++++++++++--------------- webapps/docs/changelog.xml | 6 +- 2 files changed, 84 insertions(+), 116 deletions(-) diff --git a/java/org/apache/catalina/realm/JNDIRealm.java b/java/org/apache/catalina/realm/JNDIRealm.java index 87d6f2490..9450ba986 100644 --- a/java/org/apache/catalina/realm/JNDIRealm.java +++ b/java/org/apache/catalina/realm/JNDIRealm.java @@ -144,9 +144,10 @@ import org.apache.tomcat.util.buf.CharChunk; * authenticated by setting the commonRole property to the * name of this role. The role doesn't have to exist in the directory. * - *
  • If the directory server contains nested roles, you can search for roles - * recursively by setting roleRecursionLimit to some positive value. - * The default value is 0, so role searches do not recurse.
    • + *
  • If the directory server contains nested roles, you can search for them + * by setting roleNested to true. + * The default value is false, so role searches will not find + * nested roles.
    • * *
  • Note that the standard <security-role-ref> element in * the web application deployment descriptor allows applications to refer @@ -319,14 +320,6 @@ public class JNDIRealm extends RealmBase { */ protected MessageFormat[] userPatternFormatArray = null; - - /** - * The maximum recursion depth when resolving roles recursively. - * By default we don't resolve roles recursively. - */ - protected int roleRecursionLimit = 0; - - /** * The base element for role searches. */ @@ -364,6 +357,12 @@ public class JNDIRealm extends RealmBase { * Should we search the entire subtree for matching memberships? */ protected boolean roleSubtree = false; + + /** + * Should we look for nested group in order to determine roles? + */ + protected boolean roleNested = false; + /** * An alternate URL, to which, we should connect if connectionURL fails. @@ -654,28 +653,6 @@ public class JNDIRealm extends RealmBase { /** - * Return the maximum recursion depth for role searches. - */ - public int getRoleRecursionLimit() { - - return (this.roleRecursionLimit); - - } - - - /** - * Set the maximum recursion depth for role searches. - * - * @param roleRecursionLimit The new recursion limit - */ - public void setRoleRecursionLimit(int roleRecursionLimit) { - - this.roleRecursionLimit = roleRecursionLimit; - - } - - - /** * Return the base element for role searches. */ public String getRoleBase() { @@ -765,6 +742,28 @@ public class JNDIRealm extends RealmBase { this.roleSubtree = roleSubtree; } + + /** + * Return the "The nested group search flag" flag. + */ + public boolean getRoleNested() { + + return (this.roleNested); + + } + + + /** + * Set the "search subtree for roles" flag. + * + * @param roleNested The nested group search flag + */ + public void setRoleNested(boolean roleNested) { + + this.roleNested = roleNested; + + } + /** @@ -1548,71 +1547,6 @@ public class JNDIRealm extends RealmBase { return (validated); } - - /** - * Add roles to a user and search for other roles containing them themselves. - * We search recursively with a limited depth. - * By default the depth is 0, and we only use direct roles. - * The search needs to use the distinguished role names, - * but to return the role names. - * - * @param depth Recursion depth, starting at zero - * @param context The directory context we are searching - * @param recursiveMap The cumulative result map of role names and DNs. - * @param recursiveSet The cumulative result set of role names. - * @param groupName The role name to add to the list. - * @param groupDName The distinguished name of the role. - * - * @exception NamingException if a directory server error occurs - */ - private void getRolesRecursive(int depth, DirContext context, Map recursiveMap, Set recursiveSet, - String groupName, String groupDName) throws NamingException { - if (containerLog.isTraceEnabled()) - containerLog.trace("Recursive search depth " + depth + " for group '" + groupDName + " (" + groupName + ")'"); - // Adding the given group to the result set if not already found - if (!recursiveSet.contains(groupDName)) { - recursiveSet.add(groupDName); - recursiveMap.put(groupDName, groupName); - if (depth >= roleRecursionLimit) { - if (roleRecursionLimit > 0) - containerLog.warn("Terminating recursive role search because of recursion limit " + - roleRecursionLimit + ", results might be incomplete"); - return; - } - // Prepare the parameters for searching groups - String filter = roleFormat.format(new String[] { groupDName }); - SearchControls controls = new SearchControls(); - controls.setSearchScope(roleSubtree ? SearchControls.SUBTREE_SCOPE : SearchControls.ONELEVEL_SCOPE); - controls.setReturningAttributes(new String[] { roleName }); - if (containerLog.isTraceEnabled()) { - containerLog.trace("Recursive search in role base '" + roleBase + "' for attribute '" + roleName + "'" + - " with filter expression '" + filter + "'"); - } - // Searching groups that assign the given group - NamingEnumeration results = - context.search(roleBase, filter, controls); - if (results != null) { - // Iterate over the resulting groups - try { - while (results.hasMore()) { - SearchResult result = results.next(); - Attributes attrs = result.getAttributes(); - if (attrs == null) - continue; - String dname = getDistinguishedName(context, roleBase, result); - String name = getAttributeValue(roleName, attrs); - if (name != null && dname != null) { - getRolesRecursive(depth+1, context, recursiveMap, recursiveSet, name, dname); - } - } - } catch (PartialResultException ex) { - if (!adCompat) - throw ex; - } - } - } - } - /** * Return a List of roles associated with the given User. Any * roles present in the user's directory entry are supplemented by @@ -1656,7 +1590,7 @@ public class JNDIRealm extends RealmBase { // Are we configured to do role searches? if ((roleFormat == null) || (roleName == null)) return (list); - + // Set up parameters for an appropriate search String filter = roleFormat.format(new String[] { doRFC2254Encoding(dn), username }); SearchControls controls = new SearchControls(); @@ -1693,30 +1627,60 @@ public class JNDIRealm extends RealmBase { Set keys = groupMap.keySet(); if (containerLog.isTraceEnabled()) { containerLog.trace(" Found " + keys.size() + " direct roles"); - for (Iterator i = keys.iterator(); i.hasNext();) { - Object k = i.next(); - containerLog.trace( " Found direct role " + k + " -> " + groupMap.get(k)); + for (String key: keys) { + containerLog.trace( " Found direct role " + key + " -> " + groupMap.get(key)); } } - HashSet recursiveSet = new HashSet(); - HashMap recursiveMap = new HashMap(); + // if nested group search is enabled, perform searches for nested groups until no new group is found + if (getRoleNested()) { - for (Iterator i = keys.iterator(); i.hasNext();) { - String k = i.next(); - getRolesRecursive(0, context, recursiveMap, recursiveSet, groupMap.get(k), k); - } + // The following efficient algorithm is known as memberOf Algorithm, as described in "Practices in + // Directory Groups". It avoids group slurping and handles cyclic group memberships as well. + // See http://middleware.internet2.edu/dir/ for details - HashSet resultSet = new HashSet(list); - resultSet.addAll(recursiveMap.values()); + Set newGroupDNs = new HashSet(groupMap.keySet()); + while (!newGroupDNs.isEmpty()) { + Set newThisRound = new HashSet(); // Stores the groups we find in this iteration - if (containerLog.isTraceEnabled()) { - containerLog.trace(" Returning " + resultSet.size() + " roles"); - for (Iterator i = resultSet.iterator(); i.hasNext();) - containerLog.trace( " Found role " + i.next()); + for (String groupDN : newGroupDNs) { + filter = roleFormat.format(new String[] { groupDN }); + + if (containerLog.isTraceEnabled()) { + containerLog.trace("Perform a nested group search with base "+ roleBase + " and filter " + filter); + } + + results = context.search(roleBase, filter, controls); + + try { + while (results.hasMore()) { + SearchResult result = results.next(); + Attributes attrs = result.getAttributes(); + if (attrs == null) + continue; + String dname = getDistinguishedName(context, roleBase, result); + String name = getAttributeValue(roleName, attrs); + if (name != null && dname != null && !groupMap.keySet().contains(dname)) { + groupMap.put(dname, name); + newThisRound.add(dname); + + if (containerLog.isTraceEnabled()) { + containerLog.trace(" Found nested role " + dname + " -> " + name); + } + + } + } + } catch (PartialResultException ex) { + if (!adCompat) + throw ex; + } + } + + newGroupDNs = newThisRound; + } } - return new ArrayList(resultSet); + return new ArrayList(groupMap.values()); } diff --git a/webapps/docs/changelog.xml b/webapps/docs/changelog.xml index 90a04f46e..2547e708d 100644 --- a/webapps/docs/changelog.xml +++ b/webapps/docs/changelog.xml @@ -34,6 +34,10 @@ + 46925: Replace recusive search for nested roles with + iterative search. Patch provided by Stefan Zoerner. (rjung) + + Switch from AnnotationProcessor to InstanceManager. Patch provided by David Jecks with modifications by Remy. (remm/fhanik) @@ -78,7 +82,7 @@ 713953 Include name of attribute when logging failure of - session attribute serializatyion. (mturk) + session attribute serialization. (mturk) Improve JNDI realm compatability with Active Directory. (rjung) -- 2.11.0