Computer-implemented method for obtaining a minimum biclique cover in a bipartite dataset

[0001] The present application relates generally to access control systems, and more particularly to role discovery and simplification in access control systems.

[0002] In a simple access control system, access control lists (ACLs) are used. An ACL lists the user accounts (users) that have permission to use a given resource. The resource may be a file, or a network machine (with an internet protocol address), or a service provided by a port on a network machine, for example.

[0003] Such a set of ACLs may have a very large number of entries. As a simple example, if one thousand users each had permission to use one thousand different resources, then the ACL set would have a total of one million (one thousand multiplied by one thousand) entries. As the number of users and the number of resources grow, the size of this representation becomes extremely large and unwieldy. It becomes difficult to maintain, to check, to store, to present to an administrator, and to visualize on a graphics display. Ultimately, it becomes difficult, expensive, and error-prone to manage.

[0004] One way to reduce the size of the representation of the access permission is to utilize role-based access control (RBAC). In an RBAC system, a new kind of entity, the role, is introduced. Herein, a role may be defined as a set of permissions. Users may have or be assigned roles. A given role confers to its users permission to use certain resources. In a bipartite graphical representation of users and resources, wherein user-resource permissions are represented by edges drawn between vertices of a first type that represent users and vertices of a second type that represent resources, these roles may be represented as bicliques.

[0005] In order to migrate from using a set of ACLs to using RBAC, an appropriate set of roles need to be discovered from the ACL data. The present application relates to a computer-implemented method for obtaining a minimum biclique cover in a bipartite dataset that can be applied to role discovery in access control systems.

[0017] Throughout the drawings, identical reference numbers designate similar, but not necessarily identical, elements.

[0018] In some situations, it may be desirable to discover roles from a set of ACLs by representing users and the resources to which the users have been granted access as vertices in a bipartite graph. Furthermore, it may be desirable to determine an exact solution to the role discovery problem without relying on heuristics or other imprecise methods.

[0019] Therefore, in response to this and other issues, the present specification discloses systems and methods for obtaining a minimum biclique cover in a bipartite dataset. These systems and methods may be used in the discovery of a minimum set of roles from a set of ACLs that provide an exact solution. It should be understood, however, that while the methods and systems set forth herein will be described principally in the exemplary context of biclique role discovery in access control systems, the methods and systems are not necessarily limited to such applications. It is anticipated that the methods and systems described herein may be applied to any application wherein a discovery of a minimum biclique cover in a bipartite dataset is sought.

[0020] As used herein and in the appended claims, the term “bipartite” will be defined as relating to a graph having vertices that can be divided into two disjoint independent sets such that every edge connects a vertex of the first set with a vertex of the second set.

[0021] As used herein and in the appended claims, the term “unipartite” will be defined as relating to a graph having only one type of vertices.

[0022] As used herein and in the appended claims, the term “clique” will be defined as a set of vertices within a graph such that a connecting edge exists between every two vertices within the clique.

[0023] As used herein and in the appended claims, the term “biclique” will be defined as a first set of vertices of a first type and a second set of vertices of a second type such that every vertex in the first set is connected by an edge to every vertex in the second set.

[0024] In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present systems and methods. It will be apparent, however, to one skilled in the art that the present systems and methods may be practiced without these specific details. Reference in the specification to “an embodiment,” “an example” or similar language means that a particular feature, structure, or characteristic described in connection with the embodiment or example is included in at least that one embodiment, but not necessarily in other embodiments. The various instances of the phrase “in one embodiment” or similar phrases in various places in the specification are not necessarily all referring to the same embodiment.

[0025] Referring to FIG. 1A, an illustrative bipartite graph (100) is presented showing a bipartite relationship between vertices of a first type (102) and vertices of a second type (104). In this example, the vertices of the first type (102) represent user accounts (users), labeled A1, A2, A3, and A4, and the vertices of the second type (104) represent resources, labeled B1, B2, B3, B4 and B5. Of course, in an actual network system employing an ACL set, the number of users and the number of resources may be much higher. Here, small numbers of users and resources are shown for purposes of simplified explanation.

[0026] Each of the users may have permission to access one or more resources. In the diagram, these permissions are indicated by edges (105) connecting individual users to individual resources. For example, user A1 has permission to access resources B1 and B3, user A2 has permission to access resources B1 and B5, and so on.

[0027] Referring now to FIG. 1B, the permissions indicated by the edges (105) may be covered by biclique roles (106) such that each of the biclique roles (106) represents a set of permissions to a specific group of resources. Thus, each of the users that has a certain biclique role (106) may have permission to access each of the specific resources defined by the biclique role (106). For example, as shown in the present example, biclique role C1 provides permission to access both resource B1 and resource B3. Because user A1 and user A4 are associated with biclique role C1, both user A1 and user A4 have permission to access resources B1 and B3. Although the present example illustrates each user (101) having only one assigned biclique role (106), users may be assigned to as many biclique roles (106) as necessary to confer a desired set of permissions on the users. The biclique roles (106) may cover all the existing permissions of the users.

[0028] Referring now to FIG. 2, an illustrative unipartite or unitary edge dual graph (200) of the bipartite graph (100, FIG. 1A) of FIG. 1A is shown. The unitary edge dual graph (200), also referred to herein for brevity as simply an “edge dual graph,” may be used to discover biclique roles in a bipartite user-resource graph in the following manner.

[0029] As described above, the use of biclique roles (106) to cover permissions between users and resources may simplify and optimize the storage and organization of resource permissions, especially where such permissions can be redundant for multiple users and/or resources. Referring back to the bipartite graph of FIG. 1A, each biclique role corresponds to a biclique of users and resources. In biclique role discovery, then, the goal is to find a minimum biclique cover of the edges (106) in a bipartite graph of permissions between users and resources.

[0030] Two edges in a bipartite graph whose four endpoints are distinct and are not completely connected (by two additional edges) are said to be independent. Two edges are adjacent if they are not independent. If two edges can be covered by a single biclique, then clearly the three (or four) vertices that are endpoints of these two edges are completely connected and form a small biclique, so the two edges must be adjacent, and hence a pair of independent edges cannot both be covered by a single biclique.

[0031] Let G=(V, E) be a given bipartite graph in which a minimum biclique cover is sought, where V represents the set of vertices in the graph and E represents the set of edges present in the graph. An edge dual graph G′ of the given bipartite graph may be constructed such that the edges E of G become the vertices G′, and a pair of vertices in G′ is connected by an edge if and only if the corresponding edges of G are adjacent and/or members of a common biclique.

[0032] In such a situation, the vertices of a (maximal) clique in G′ correspond to a set of edges of G whose endpoints are a (maximal) biclique in G. The edges covered by a (maximal) biclique in G induce a (maximal) clique in G′. Thus, every biclique edge cover of G corresponds to a collection of cliques of G′ whose union contains all of the vertices of G′. From such a collection, a clique partition of G′ may be obtained by removing any redundantly covered vertex from all but one of the cliques to which it belongs. Similarly, any clique partition of G′ corresponds to a biclique cover of G. Thus, the biclique cover number of a bipartite graph G is the clique cover number (the size of a minimum clique partition) of G′.

[0033] In the present example, the present edge dual graph (200) corresponds to the bipartite graph (100, FIG. 1A) of FIG. 1A. Accordingly, each of the vertices (210) of the edge dual graph (200) corresponds to an edge (105, FIG. 1A) in the bipartite graph (100, FIG. 1A). Each of the vertices (210) is labeled with the endpoints of its counterpart edge (105, FIG. 1A) in the bipartite graph. For example, vertex A1-B1 corresponds to the edge (105, FIG. 1A) between user A1 and resource B1 in FIG. 1A. Because this edge (105, FIG. 1A) is adjacent to an edge (105, FIG. 1A) between user A1 and resource B3, an edge (105, FIG. 1A) between user A4 and resource B3, and an edge (105, FIG. 1A) between user A4 and user B1 in the bipartite graph (100, FIG. 1A), edges (220) are drawn between vertex A1-B3 and vertices A1-B1, A4-B3, and A4-B1 in the edge dual graph (200).

[0034] Furthermore, since edges A1-B1, A1-B3, A4-B3, and A4-B1 form a biclique in the bipartite graph (100, FIG. 1A), their counterpart vertices (210) in the edge dual graph (200) form a clique, as described above. The edges (220) in the clique are highlighted for clarity in FIG. 2.

[0035] Referring now to FIG. 3, a flowchart of an illustrative method (300) of biclique role discovery is shown. The method (300) may be executed by a computer system configured to execute the steps of the method (300), which may be stored by and read from computer-readable media. The method (300) includes providing (step 305) a bipartite graph G of users and resources. Edges may be drawn between specific users and specific resources that are indicative of access permissions, as described above.

[0036] The bipartite graph G may then be converted (step 310) into a unipartite edge dual graph G′ according to the principles described in relation to FIG. 2. Particularly, vertices in the edge dual graph G′ may represent edges in the bipartite graph. Edges between vertices in the edge dual graph G′ may represent adjacency and/or membership in a biclique of their counterpart edges in G. A minimum clique partition (MCP) solution may then be found (step 315) for the edge dual graph G′. The minimum clique partition may be a partition of the edge dual graph G′ into a minimum number of separate cliques formed by edges in the edge dual graph G′ such that each vertex in the edge dual graph G′ is a member of only one clique.

[0037] The MCP of the edge dual graph G′ may correspond to a minimum biclique cover (MBC) of the original bipartite graph G. Therefore, by deriving from (step 320) the MCP solution of the edge dual graph G′ a minimum biclique cover solution (MBC) and associating (step 325) a user-resource biclique role with each biclique in the MBC solution for the original bipartite graph G, a minimum number of biclique roles in the original bipartite graph G may be discovered.

[0038] Referring now to FIG. 4, a flowchart of an illustrative method (400) of obtaining an exact minimum clique partition (MCP solution for an edge dual graph G′ is shown. The present method (400) may also be executed by a computer system configured to execute the steps of the method (400), which may be stored by and read from computer-readable media. The method (400) is recursive in that multiple calls to itself may result in multiple nested iterations of the method (400) that are completed in a last in, first out (LIFO) order to obtain the desired solution.

[0039] The method (400) includes determining (decision 405) whether an isolated vertex x exists in the edge dual graph G′. An isolated vertex x is a vertex that has no neighbors (i.e. is not connected to any other vertex by an edge). This determination may be made by searching through each of the vertices of the edge dual graph G′ until either an isolated vertex x is found or no more vertices remain. In certain embodiments, an algorithm may determine a particular order in which the vertices are searched for isolated vertices. Alternatively, the vertices may be searched randomly for an isolated vertex x.

[0040] If an isolated vertex x is found, then an MCP of the edge dual graph G′ exists that consists of a clique containing x alone, together with an MCP of the subgraph induced by G′\{x}, where G′\{x} indicates the edge dual graph G′ modified by the removal of x and any edges connected to x. Therefore, to find the MCP of G′, all that needs to be done is recursively find (step 410) the MCP of G′\{x} and add (step 415) a single clique containing only x to the MCP of G′\{x}.

[0041] If an isolated vertex x is not found, then a determination must be made (decision 420) as to whether a vertex d exists that dominates another vertex g. A vertex d dominates another vertex g by definition if g and all of its neighbors are a subset of d and all of its neighbors. The determination may be made by searching through the edge dual graph G′, either by algorithm or randomly, until a vertex d is found that dominates another vertex g or it is determined that no vertices exist in G′.

[0042] If no dominating vertex is found, G′ is a kernel that can not be reduced further by recursively invoking the method (400). Therefore, the MCP of G′ may be obtained by constructing (step 425) a new graph G″ from G′, wherein G″ has all of the same vertices as G′ and edges between vertices only where no edge exists between the vertices in G′. A minimum coloring of G″ may then be found (step 430) using any method that may suit a particular application of the principles herein. For example, many suitable methods of finding a minimum coloring of G″ exist and are known in the art. Additionally or alternatively, a method for finding the minimum coloring of G″ that is customized to the principles herein may be used.

[0043] Once the minimum coloring of G″ has been found, the MCP of G′ may be determined (step 435) to be the set of cliques corresponding to each color in the coloring of G″.

[0044] If, on the other hand, a vertex d is found in G′ that dominates another vertex g, an MCP of G′\{d} is found (step 440) recursively and d is added (step 445) to the clique in the MCP of G′\{d} that contains g to obtain the MCP of G′.

[0045] FIG. 5 is an illustrative edge dual graph (500) that will be used to illustrate the recursive nature of the method (400, FIG. 4) described above.

[0046] Referring now to FIG. 6, a diagram is shown of nested recursive iterations of the method (400, FIG. 4) described above in finding the MCP of the illustrative edge dual graph (500, FIG. 5). For brevity and consistency with the prior description of the method (400, FIG. 4), the edge dual graph (500, FIG. 5) is referred to as G′.

[0047] In a first iteration (605) of the method (400, FIG. 4), the isolated vertex A4-B4 is found. The isolated vertex A4-B4 will be added as a single-member clique to the MCP of G′\{A4-B4}. However, to find the MCP of G′\{A4-B4}, the method must be called on G′\{A4-B4}.

[0048] In a second iteration (610), then, the method (400, FIG. 4) is performed on G′\{A4-B4}. FIG. 7A shows G′\{A4-B4}. In this iteration, vertex A1-B2 is found to dominate vertex A1-B2. Therefore, A1-B2 will be added to the clique containing A1-B1 in the MCP of G′\A4-B4 & A1-A2} to obtain the MCP of G′\A4-B4. Thus, the method (400, FIG. 4) must now be called on G′\{A4-B4 & A1-A2}.

[0049] In a third iteration (615), the method (400, FIG. 4) is performed on G′\{A4-B4 & A1-A2}. FIG. 7B shows G′\{A4-B4 & A1-A2}. In this iteration, newly isolated vertex A1-B1 is found. A1-B1 must, then, be added as a single-member clique to the MCP of G′\{A4-B4 & A1-B2 & A1-B1} to obtain the MCP of G′\{A4-B4 & A1-A2}, thereby invoking the method (400, FIG. 4) a fourth time.

[0050] In a fourth iteration (620), the method (400, FIG. 4) is performed on G′\{A4-B4 & A1-B2 & A1-B1}, which is shown in FIG. 7C. Vertex A3-B2 is found to dominate vertex A3-B5. Therefore, to obtain the MCP of G′\{A4-B4 & A1-B2 & A1-B1}, an MCP must be found of G′\{A4-B4 & A1-B2 & A1-B1 & A3-B2} and vertex A3-B2 must be added to the clique therein that contains vertex A3-B5. Accordingly, the method (400, FIG. 4) must be invoked a fifth time.

[0051] In a fifth iteration (625), the method (400, FIG. 4) is performed on G′\{A4-B4 & A1-B2 & A1-B1 & A3-B2}, which is shown in FIG. 7D. Newly isolated vertex A2-B2 is found. Therefore A2-B2 must be added as a single-member clique to the MCP of G′\{A4-B4 & A1-B2 & A1-B1 & A3-B2 & A2-B2} to obtain the MCP of G′\{A4-B4 & A1-B2 & A1-B1 & A3-B2}.

[0052] In a sixth iteration (630), the method (400, FIG. 4) is performed to find the MCP of G′\{A4-B4 & A1-B2 & A1-B1 & A3-B2 & A2-B2}, as shown in FIG. 7E. Vertex A3-B5 is found to dominate vertex A3-B3. Thus, vertex A3-B5 will be added to the clique containing A3-B3 in the MCP of G′\{A4-B4 & A1-B2 & A1-B1 & A3-B2 & A2-B2 & A3-B5} to obtain the MCP of G′\{A4-B4 & A1-B2 & A1-B1 & A3-B2 & A2-B2}.

[0053] In a seventh iteration (635), the method (400, FIG. 4) is performed on G′\{A4-B4 & A1-B2 & A1-B1 & A3-B2 & A2-B2 & A3-B5}, which is shown in FIG. 7F. Isolated vertex A3-B3 is found. Therefore A3-B3 must be added as a single-member clique to the MCP of G′\{A4-B4 & A1-B2 & A1-B1 & A3-B2 & A2-B2 & A3-B5 & A3-B3} to obtain the MCP of G′\G′\{A4-B4 & A1-B2 & A1-B1 & A3-B2 & A2-B2 & A3-B5}.

[0054] In an eighth iteration (640), the method (400, FIG. 4) is performed on G′\{A4-B4 & A1-B2 & A1-B1 & A3-B2 & A2-B2 & A3-B5 & A3-B5}. Because no vertices remain, the method (400, FIG. 4) can determine the the MCP of the empty set (another empty set) without invoking the method (400, FIG. 4). Therefore, the chain of recursion ends with the eighth iteration (640), which returns an empty set to the seventh iteration (635).

[0055] The seventh iteration (635) then appends the single-member clique containing A3-B3 to the MCP returned by the eighth iteration (640), and returns it as an MCP to the sixth iteration (630). Control then percolates back up through the recursive iterations as each iteration finishes the method (400, FIG. 4) and returns an MCP until control is returned to the first iteration (605), which determines an MCP for the entire graph G′.

[0056] Referring now to FIG. 8, a diagram is shown of the resulting MCP from invoking the method (400, FIG. 4) on G′ in the example of FIGS. 5-7 above. The MCP includes four cliques (805, 810, 815, 820) of vertices, with a first clique (805) including only vertex A4-B4, a second clique (810) containing vertices A1-B2 and A1-B1, a third clique (815) containing only vertex A2-B2, and a fourth clique (820) containing vertices A3-B5, A3-B3, and A3-B2. Each of the four cliques (805, 810, 815, 820) can be translated into a corresponding biclique role (825, 830, 835, 840, respectively) in an original bipartite user-resource graph for which G′ is an edge dual graph.

[0057] This translation may be accomplished by determining which of the vertices of the first type (102) (representing users) in the bipartite graph and the vertices of the second type (104) (representing resources) in the bipartite graph are connected by edges in the bipartite graph that are represented by the vertices in each clique (805, 810, 815, 820) of the edge dual graph G′. Then each of the vertices of the first type (102) and the vertices of the second type (104) that are connected by edges in the bipartite graph that are represented by the vertices in the clique (805, 810, 815, 820) may be added to a biclique role (825, 830, 835, 840) in the bipartite graph corresponding to the clique (805, 810, 815, 820) in G′.

[0058] For example, the fourth clique (820) represents a biclique role in the original bipartite graph that is held only by user A3 and signifies permissive access to each of resources B2, B3, and B5.

[0059] FIG. 9 is a schematic diagram of an example computer system or apparatus (900) which may be used to execute the computer-implemented procedures for biclique role discovery and biclique role reduction in accordance with an embodiment of the invention. The computer (900) may have fewer or more components than illustrated. The computer (900) may include a processor (901), such as those from the Intel Corporation or Advanced Micro Devices, for example. The computer (900) may have one or more buses (903) coupling its various components. The computer (900) may include one or more user input devices (902) (e.g., keyboard, mouse), one or more data storage devices (906) (e.g., hard drive, optical disk, USB memory), a display monitor (904) (e.g., LCD, flat panel monitor, CRT), a computer network interface (905) (e.g., network adapter, modem), and a main memory (908) (e.g., RAM).

[0060] In the example of FIG. 9, the main memory (908) includes software modules (910), which may be software components to perform the above-discussed computer-implemented procedures. The software modules (910) may be loaded from one or more data storage device (906) to the main memory (908) for execution by the processor (901). Specifically, the software modules (910) may include one or more modules of computer readable code for performing the tasks of biclique role discovery and simplification according to the principles described herein. The computer network interface (905) may be coupled to a computer network (909), which in this example includes the Internet.

[0061] In the above description, numerous specific details are given to provide a thorough understanding of embodiments of the invention. However, the above description of illustrated embodiments of the invention is not intended to be exhaustive or to limit the invention to the precise forms disclosed. One skilled in the relevant art will recognize that the invention can be practiced without one or more of the specific details, or with other methods, components, etc. In other instances, well-known structures or operations are not shown or described in detail to avoid obscuring aspects of the invention. While specific embodiments of, and examples for, the invention are described herein for illustrative purposes, various equivalent modifications are possible within the scope of the invention, as those skilled in the relevant art will recognize.

[0062] These modifications can be made to the invention in light of the above detailed description. The terms used in the following claims should not be construed to limit the invention to the specific embodiments disclosed in the specification and the claims. Rather, the scope of the invention is to be determined by the following claims, which are to be construed in accordance with established doctrines of claim interpretation.