System for selectively browsing a large, distributed directory tree using authentication links5826254Abstract A browser for efficiently browsing large directory trees is presented. The browser uses authentication links as the structure through which the browser navigates. By adhering to the rules for a valid authentication chain, the browser increases efficiency by storing the results of preliminary steps to browsing. Claims What is claimed is: Description FIELD OF THE INVENTION
______________________________________
a) zero or more up-links
(3)
(wherein a principal vouches for one of
its ancestors)
b) zero or one cross-links
(4)
(wherein a principal vouches for
another principal that is neither an
ancestor nor a descendant)
c) zero or more down-links
(5)
(wherein a principal vouches for one of
its descendants).
______________________________________
The above rules enhance system security in that they ensure that only ancestors of the two end principals involved in an authentication chain can successfully disguise an imposter as one of the principals. Other rules which accomplish the same effect may be used. For example, in a system where there is one well-known principal which all other principals trust, the following rules will produce a valid authentication chain:
______________________________________
(a) zero or more up-links
(6)
(b) zero or one cross-link to the well-known
(7)
principal
(c) zero or one other cross link
(8)
(d) zero or more down-links.
(9)
______________________________________
Applying the above rules to the tree in FIG. 5 to authenticate User 535, as someone who may access information in Corporations A's Finance node 545, for example, could yield the following authentication chain 550: /U.S./Corporation X/Finance/User (535) /U.S./Corporation X/Finance (530) /U.S./Corporation X (520) /U.S./Corporation A (525) /U.S./Corporation A/Engineering (540) /U.S./Corporation A/Engineering/Finance (545) The authentication scheme described above may be implemented in a graphical browser. By browsing principals along authentication links, names which are not useful or needed in a particular search through the tree may be eliminated from the browser view. In the exemplary embodiment of the invention, the links described are used for security, however, if links with the required structure exist in a tree, the invention works whether or not the links are used for security. The steps of the browser are illustrated in FIG. 6. The browser requires as input the name of a known principal, for example, a principal called X, box 605; In order to make a list of all the principals that principal X could authenticate, the browser would follow the up-links starting from principal X, box 610. This yields the names of the principals reachable by uplinks from X. Then, starting from principal X and each of the principal names obtained in the previous step, box 610, follow all the cross-links, to obtain a number of additional principal names, if there are any, box 615. Lastly, starting from principal X and each of the principal names obtained in both the two previous steps, follow all of the down-links, box 620. The above-described steps result in the names of all the principals which X can authenticate, according to the rules for valid authentication chains. This method alone is impractical because there may be far too many principals for X to browse if the directory was very large. If the up-link and cross-link steps were performed in advance, a smaller, more manageable set of names that contains at least one ancestor of every name that X can authenticate or else contains the authenticable name itself would result. Then the down-links could be followed on demand as a user browses down the tree. It is not necessary to cryptographically validate the authentication chains in order for the browser to work. However, if the authentication chains are not cryptographically validated, the browser may list a few principals that the user cannot actually authenticate, a result which is generally inconsequential. FIG. 7 shows an exemplary tree which may be used to illustrate the actions of the browser. The root 705 of the tree has one branch 707 leading to a principal called U.S. 709 and one branch 711 leading to a principal called U.K. 713. The principal U.S. 709 has one branch 715 leading to a principal called XYZ Co. 717 and one branch 719 leading to a principal called ABC Corp. 721. The principal XYZ Co. 717 has a branch 723 leading to a principal called Engineering 725 which in turn has a branch 727 leading to a principal called Sue.sub.-- Wong 729. The principal ABC Corp. 721 has a branch 731 leading to a principal called Sales 733. Sales 733 has a branch 735 leading to a principal called Northeast U.S. 737 which has a first branch 739 leading to a principal called Henry.sub.-- Adams 741 and a second branch 743 to a principal called Ordering System 745. The principal U.K. 713 has a branch 747 leading to a principal called AAA Ltd. 749. AAA Ltd. 749 has a branch 751 leading to a principal called Engineering 753 which has a branch 755 leading to a principal called Finance 757. The tree in FIG. 7 also has authentication links. XYZ Co. 717 and Engineering 725 have an authentication link 759 between them. Engineering 725 and Sue.sub.-- Wong 729 have an authentication link 761. XYZ Co. 717 and ABC Corp. 721 have an authentication cross-link 763. ABC Corp. 721 and Sales 733 have an authentication link 765. Sales 733 also has an authentication link 767 with Northeast U.S. 737 and an authentication cross-link 769 with Engineering 753. Northeast U.S. 737 has an authentication link 771 with Henry.sub.-- Adams 741 and another authentication link 773 with Ordering System 745. Engineering 753 has an authentication link 775 with AAA Ltd. 749 and an authentication link 777 with Finance 757. For example, if the person Henry Adams is browsing, the principal Henry.sub.-- Adams 741 will be used as the starting point for the browser. Before the browser is started up, a set of authenticable roots, i.e. a set of the roots of subtrees, is created by performing the steps from blocks 610 and 615 from FIG. 6. That is, the up-links and the cross-links from Henry.sub.-- Adams 741 are followed and the set is created in the following order, Northeast U.S. 737, Sales 733, Engineering 753, ABC Corp. 721, and XYZ Co. 717. When user Henry Adams starts the browser, represented as principal Henry.sub.-- Adams 741, the principals U.S. 709 and U.K. 713 are displayed as shown in FIG. 8, because they are the top-level names that have descendants in the set of authenticable roots created before-hand. If Adams expands U.S. 709, the principals U.S. 709 with the principals XYZ Co. 717 and ABC Corp. 721 as well as the principal U.K. 713 are displayed as shown in FIG. 9. XYZ Co. 717 and ABC Corp. 721 are part of the authenticable roots set. If Adams expands on the principal XYZ Co. 717, the principals U.S. 709, XYZ Co. 717, Engineering 725, ABC Corp. 721 and U.K. 713 are displayed as shown in FIG. 10. Engineering 725 is displayed because XYZ Co. 717 has an authentication down-link to it. If Adams expands on the principal Engineering 725, the principals U.S. 709, XYZ Co. 717, Engineering 725, Sue.sub.-- Wong 729, ABC Corp. 721 and U.K. 713 are displayed as shown in FIG. 11. The creation of the authenticable roots may be done on a batch basis performed periodically, or it may be done when the user starts up the browser. Pseudo-code implementation of the browser forming the authenticable roots set is as follows below.
__________________________________________________________________________
PENDING.sub.-- PRINCS := {STARTING.sub.-- PRINCIPAL};
// A queue of names to be processed
PRINC.sub.-- AND.sub.-- ANCESTORS := {};
// The empty set, initially
// Follow up-links repeatedly, starting from STARTING.sub.-- PRINCIPAL.
// This will yield the names of all principals reachable by
// uplinks from STARTING.sub.-- PRINCIPAL.
While PENDING.sub.-- PRINCS <> {} Do
// Pick a pending name to process.
PRINC := longest and deepest member of PENDING.sub.-- PRINCS;
PENDING.sub.-- PRINCS := PENDING.sub.-- PRINCS - {PRINC};
// Add the name to the set.
PRINC.sub.-- AND.sub.-- ANCESTORS := PRINC.sub.-- AND.sub.-- ANCESTORS +
{PRINC};
// And continue up the tree.
Go out to the authentication link service and obtain all the
up-links that start from PRINC.
For each principal U that principal PRINC has an up-link
to, Do
PENDING.sub.-- PRINCS := PENDING.sub.-- PRINCS + {U};
END For;
END While;
// Now PRINC.sub.-- AND.sub.-- ANCESTORS contains the name of the
initial
// principal and all ancestors reachable by up-links.
// Starting from STARTING.sub.-- PRINCIPAL and each of the principal
// names obtained above, follow all of the cross-links, to obtain
// additional principal names.
AUTHENTICABLE.sub.-- SUBTREE.sub.-- ROOTS : = PRINC.sub.-- AND.sub.--
ANCESTORS;
For each PRINC in PRINC.sub.-- AND.sub.-- ANCESTORS Do
Go out to the directory and obtain all cross-links that
start from PRINC.
For each principal C that principal PRINC has a cross-link
to, Do
AUTHENTICABLE.sub.-- SUBTREE.sub.-- ROOTS :=
AUTHENTICABLE.sub.-- SUBTREE.sub.-- ROOTS + {C};
END //
AUTHENTICABLE.sub.-- SUBTREE.sub.-- ROOTS set.
__________________________________________________________________________
The authenticable roots set is a set of principals names with the following properties:
______________________________________
Starting.sub.-- Principal X can authenticate every member
(10)
of the set.
For every principal Y that Starting.sub.-- Principal X
(11)
can authenticate, either Y or an ancestor of
Y is a member of the set.
______________________________________
The authenticable roots set is stored in the authentication link service on disk or other storage until a user starts up the browser. Each authenticable roots set is stored under the name of the principal doing the authenticating. An alternative embodiment of the invention deals with the problem of the heavy load placed on directories near the root. If the browser is widely used, the directories near the root will be frequently queried for up-links and cross-links, that is, every principal under any given directory will query that directory at least once a day. The pseudo-code alternative embodiment is as follows:
______________________________________
PENDING.sub.-- PRINCS := {STARTING.sub.-- PRINCIPAL};
// A queue of names to be processed.
AUTHENTICABLE.sub.-- SUBTREE.sub.-- ROOTS := { }; // Initially,
an empty set.
While PENDING.sub.-- PRINCS < > { } Do
// Pick a pending name to process.
PRINC := longest and deepest member of PENDING.sub.-- PRINCS;
PENDING.sub.-- PRINCS := PENDING.sub.-- PRINCS - {PRINC};
// Add the name to the set.
AUTHENTICABLE.sub.-- SUBTREE.sub.-- ROOTS :=
AUTHENTICABLE.sub.-- SUBTREE.sub.-- ROOTS + {PRINC};
If PRINC < > STARTING.sub.-- PRINCIPAL Then
// PRINC is an ancestor of STARTING.sub.-- PRINCIPAL.
Go out to the directory to see whether an
AUTHENTICABLE.sub.-- SUBTREE.sub.-- ROOTS set associated
with PRINC is there.
If so,
Add all the members of that set to our own
AUTHENTICABLE.sub.-- SUBTREE.sub.-- ROOTS set (since
any principal that PRINC can reach,
STARTING.sub.-- PRINCIPAL can reach too).
EXIT;
END If;
END If;
Go out to the directory and obtain all cross-links
that start from PRINC.
For each principal C that principal PRINC has a
cross-link to, Do
AUTHENTICABLE.sub.-- SUBTREE.sub.-- ROOTS :=
AUTHENTICABLE.sub.-- SUBTREE.sub.-- ROOTS + {C};
// And continue up the tree.
Go out to the directory and obtain all up-links
that start out from PRINC.
For each principal U that principal PRINC has an
up-link to, Do
PENDING.sub.-- PRINCS := PENDING.sub.-- PRINCS + {U};
END For;
END While;
______________________________________
This alternative embodiment can be performed periodically, and the resulting set of principal names can be stored in the directory service, associated with STARTING.sub.-- PRINCIPAL. It is possible to have both methods for establishing authenticable roots sets operating in the same browser system. When the user is browsing, initially it is desirable to show all the children of the root that are authenticable or have authenticable descendants. This is implemented in pseudo-code as follows:
______________________________________
AUTHENTICABLE.sub.-- NAMES :=
AUTHENTICABLE.sub.-- SUBTREE.sub.-- ROOTS
If the root if a member of AUTHENTICABLE.sub.-- NAMES Then
For each principal Y that the root has a down-link to, Do,
AUTHENTICABLE.sub.-- NAMES :=
AUTHENTICABLE.sub.-- NAMES + {Y}
END For
End If
Let NEW.sub.-- NAMES := { }
For each Y in AUTHENTICABLE.sub.-- NAMES Do
If Y is a child of the root then
NEW.sub.-- NAMES := NEW.sub.-- NAMES + {Y}
Else
Let T be the child of the root that is an
ancestor of Y.
NEW.sub.-- NAMES := NEW.sub.-- NAMES + {T}
END If
End For
Display the names in NEW.sub.-- NAMES
// Some of the names displayed may belong to AUTHENTICABLE.sub.--
// NAMES, and others may have descendants that belong to
// AUTHENTICABLE.sub.-- NAMES.
______________________________________
When the user expands a name other than the root, it is desirable to show all children of that name that are authenticable or have authenticable descendants. Let Z denote the name to be expanded. This is implemented in pseudo-code as follows:
______________________________________
If Z if a member of AUTHENTICABLE.sub.-- NAMES Then
For each principal Y that principal Z has a down-link to,
Do,
AUTHENTICABLE.sub.-- NAMES :=
AUTHENTICABLE.sub.-- NAMES + {Y}
END For
End If
Let NEW.sub.-- NAMES := { }
For each Y in AUTHENTICALBE.sub.-- NAMES Do
If Y is a child of Z then
NEW.sub.-- NAMES := NEW.sub.-- NAMES + {Y}
Else if Y is a descendant of Z Then
Let T be the child of Z that is an ancestor of Y.
NEW.sub.-- NAMES := NEW.sub.-- NAMES + {T}
END If
End For
Display the names in NEW.sub.-- NAMES
// Some of the names displayed may belong to AUTHENTICABLE.sub.--
// NAMES, and others may have descendants that belong to
// AUTHENTICABLE.sub.-- NAMES.
______________________________________
When the user collapses an item in the browser, the set of AUTHENTICABLE.sub.-- NAMES would be pared back to keep the memory requirements from becoming excessive. The operation of the browser is illustrated in FIG. 12. The browser system 1200 has two main parts, the authenticable subtree roots subsystem 1205 and the browser subsystem 1210. The browser 1200, in the authenticable subtree roots system 1205, starts with an input of the name of a known principal, for example, a principal called X. Principal X could be any principal however it would generally not be a leaf principal. The leaf principal and the cell above it have identical links making it more efficient to start with the cell. Principal X is input for initialization of a pending principals queue 1215. The pending principals queue 1215 is a priority queue in which the names of principals are prioritized by length. Initially the queue contains only one name, principal X. As the browser operates, the names of all of principal X's ancestors to which it has uplinks will be added to the queue 1215. Next, the principal with the longest name, meaning that it is deepest in the directory tree, is taken from the queue 1215 and added to a set called the authenticable subtree roots set in the authenticable subtree roots store 1220. As the browser 1200 operates, the authenticable subtree roots set will contain the initial principal name, Principal X, and all of the names of principals to which Principal X has up-links and cross-links. So far in this example, Principal X is the only principal in the queue, so it would have the longest name, and it is passed on to the authenticable subtree roots set. Principal X would also be given to the link follower 1225. The link follower 1225 interacts with the directory service 1230 to obtain all of the links from the principal, and then sorts the up-links and the cross-links. The link follower 1225 adds all of the names of principals linked to principal X by up-links or cross-links to the authenticable subtree roots set. The link follower 1225 also adds all the names connected to principal X by up-links to the pending principals queue 1215. In the most efficient embodiment of the invention, Principal X would given to the precomputed roots fetcher 1235 after being taken from the pending principals queue 1215 as well as to the authenticable subtree roots set and the link follower 1225. The precomputed roots fetcher 1235 is not essential to the invention, but increases efficiency by taking advantage of names already in the authenticable subtree roots set, i.e. names of principals whose links have already been established. The precomputed-roots fetcher 1235 takes input of the original name from the pending principals queue 1215 and the name just removed from the queue 1215. If the names are equal, then the precomputed-roots fetcher 1235 does nothing, except to send a "not found" signal out to the link follower 1225. If the names are unequal, in which case the principal from the link follower 1225 is an ancestor of the original principal, then the precomputed-roots fetcher 1235 sends out a query to the directory/security service 1230. The query is to retrieve the authenticable roots set associated with the name. If a set of names comes back, the fetcher 1235 sends these to the authenticable-subtree roots set store 1220. If no set of names comes back, the fetcher sends a "not found" signal to the link follower 1225. The link follower 1230 waits for a "not found" signal before starting to follow links. The process of removing the longest name from the pending principals queue 1215 through searching for up-links and crosslinks and adding sets to the authenticable subtree roots store 1220 is repeated until there are no more ancestors of the starting principal, Principal X, reachable by up-links. Once the authenticable subtree roots set is created by the authenticable subtree roots subsystem 1205, it is used to initialize a set of authenticable roots 1240 in the browser subsystem 1210. The authenticable names set 1240 is the set of known principals available for browsing. The authenticable names set 1240 receives input from the user 1242 of the system through an interface, the display subsystem 1245. The display subsystem 1245 has a display output 1250 for the user and a display manipulation subsystem 1255 through which the user can command the browser 1200. When the user chooses to expand the browser display, the name of the principal from which the user wishes to expand is given to the link follower 1225 which gets all the names of principals linked by down-links. The names of these principals is given to the authenticable roots set 1240. When the user chooses to collapse a part of the browser display, the name of the principal to be collapsed is given to the authenticable roots set 1240 and all descendants are removed from the authenticable roots set 1240 unless the name is part of the subtree roots set 1220. The authenticable roots set 1240 is at all times a superset of the authenticable subtree roots set 1220. Whenever a new name is to be expanded on the browser display, the filter 1260 takes input from the authenticable roots set 1240 and extracts just those names that are children of the name to expand. The resulting, usually smaller, set of names is sent to the display subsystem 1245. The display subsystem 1245 can be based on any of several widely used systems for displaying a hierarchy using a graphical display device. Initially, only the root is displayed. When names are supplied on input to the display subsystem 1245, they are added to the display that the user sees. When a name is to be collapsed, all descendants of that name are removed from the display. When the link follower 1225 receives a name from the display subsystem 1245, it sends one or more queries to the directory/security service 1230 to obtain all down-links from the name. The directory service 1230 responds with the names, if any, that are the targets of down-links from the name. The link follower 1225 sends these names to the authenticable roots set 1240. Upon initial operation of the browser system 1200, the authenticable subtree roots set is loaded into the authenticable roots set 1240. The name to be expanded initially is the root. The link follower 1225 follows all down-links from the root and the names of the principals found by the link follower are added to the authenticable roots set 1240. The filter 1260 extracts those members of the authenticable roots set 1240 that are children of the root, and sends them to the display subsystem 1245. Thereafter, when the user picks a name to expand, that name is sent to the link follower 1225, which follows all down-links from the name and adds them to the authenticable roots set 1240. Then the filter 1260 extracts those members of the authenticable roots set 1240 that are children of the name being expanded. These names are sent to the display subsystem 1245. In collapsing the browser display, the name to be collapsed is sent to the authenticable roots set 1240. All descendants of that name are removed from the set 1240, except for names that belong to the authenticable subtree roots set 1220. This removal is optional, and is a way of limiting memory demands. Names could instead be retained for a longer time. In any case, the name to be collapsed is also sent to the display subsystem 1245, which removes all descendants of that name from the browser display. It is to be understood that the above-described embodiments are simply illustrative of the principles of the invention. Various and other modifications and changes may be made by those skilled in the art which will embody the principles of the invention and fall within the spirit and scope thereof.
|
Same subclass Same class Consider this |
||||||||||