Efficient large-scale access control for internet/intranet information systems

• US 6,219,667 B1
• Filed: 05/28/1998
• Issued: 04/17/2001
• Est. Priority Date: 05/28/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lu, Qi, Teng, Shang-Hua
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/086,272
• Time in Patent Office: 1,055 Days
• Field of Search: 707/1-206, 702/5, 709/223, 379/201-221
• US Class Current: 707/763
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: H04L 63/10 for controlling access to devices or network resources
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

An efficient method and apparatus for regulating access to information objects stored in a database in which there are a large number of users and access groups. The invention uses a representation of a hierarchical access group structure in terms of intervals over a set of integers and a decomposition scheme that reduces any group structure to ones that have interval representation. This representation allows the problem for checking access rights to be reduced to an interval containment problem. An interval tree, a popular data structure in computational geometry, may be implemented to efficiently execute the access-right checking method.

Claims

1. A method to regulate access to a system'"'"'s database using interval containment control, comprising:

allowing a first group g_m comprising one or more data requesters access to a data object contained in the database;

mapping g_m to a first interval value and a second group g_n to a second interval value, wherein g_n contains at least one data requester U; and

allowing U access to the data object if the second interval value for g_n is contained within the first interval value for g_m.

2. The method recited in claim 1, wherein mapping to an interval value comprises mapping to an integer interval value, wherein b and e are integers defining the second interval and b≦

e, wherein b′ and

e′

are integers defining the first interval and b′

≦

e′ and

wherein the second interval is contained within the first interval if (b′

≦

b≦

e≦

e′

).

3. The method recited in claim 2, further comprising using a mapping means for mapping an integer interval value to a group.

4. The method recited in claim 2, further comprising mapping groups to an integer interval value, the integer interval value expressed as an interval over integers.

5. The method recited in claim 4, the mapping maintaining a hierarchial relationship within a group partial order of groups.

6. The method recited in claim 5, the group partial order being maintained wherein G is a set of groups {g₁, g₂, . . . g_m} and π

represents a mapping from G to an integer interval value, and π

respects a group partial order <

G of GROUP if for each pair of groups of g, h ε

G, g<

G^h if π

(g)<

_Iπ

(h), and π

respects a group partial order >

G of GROUP if for each pair of groups g, h ε

G, g>

G^h if π

(g)<

_I π

(h).

7. The method recited in claim 3, further comprising ordering a collection of integer interval values to define a hierarchial relationship between integer interval values in the collection.

8. The method recited in claim 7, further comprising using an ordering means for defining the hierarchial relationship.

9. The method recited in claim 4, further comprising ordering a collection of integer interval values to define a hierarchial relationship between integer interval values in the collection.

10. The method recited in claim 9, further comprising using an ordering means for defining the hierarchial relationship.

11. A method to regulate access to an object in a database by decomposing a directed acyclic graph representing a hierarchial structure of integer interval values (iDAG), each value mapped to a group, comprising:

decomposing the iDAG into multiple directed acyclic graphs (DAG) G_S and G₁ having an overlap, wherein G₁=G′

_S and wherein G′

_S is an iDAG and G_S is a simplified DAG; and

recursively repeating the decomposition on G_S, wherein (G₂=G_S″

. . . , G_k=G_S^k) formed by the recursion and are iDAGs, and wherein G_i is a newly formed iDAG comprising (G_S′

. . . , G_S^k′

) and structured by hierarchial order.

12. The method recited in claim 11, further comprising generating an interval-map for G_i using a mapping means where 1≦

i≦

k.

13. The method recited in claim 12, further comprising:

allowing a group g₁ having an interval A access to the object in the database; and

allowing a group g₂ having an interval B access to the object if the interval of B is contained within the interval of A.

14. A method to regulate access to an object in a database, comprising:

decomposing a directed acyclic graph (DAG) G having nodes and leaves into a collection of DAGs having nodes and leaves, each DAG in the collection being simpler in structure than G;

mapping a group g to a DAG in the collection; and

using a query structure of the DAG to decide if g may access the object.

15. The method recited in claim 14, wherein the query structure comprises an interval over integer mapping to each g and comparison.

16. The method recited in claim 14, wherein the query structure comprises a hash table listing all gs allowed access to the object, and a group g_i is compared to all groups in the hash table.

17. The method recited in claim 15, a DAG in the collection being more simply structured if it has less nodes or leaves than G.

18. The method recited in claim 16, a DAG in the collection being more simply structured if it has less nodes or leaves than G.

19. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method to regulate access to a system'"'"'s database, said method comprising:

allowing a first group g_m access to a data object contained in the database;

mapping g_m to a first interval value and a second group g_n to a second interval value, wherein g_n contains at least one user member U; and

allowing U access to the data object if the second interval value for g_n is contained within the first interval value for g_m.

20. The method recited in claim 19, wherein mapping to an interval value comprises mapping to an integer interval value, wherein b and e are integers defining the second interval and b≦

e, wherein b′ and

e′

are integers defining the first interval and b′

≦

e′

, and wherein the second interval is contained within the first interval if (b′

≦

b≦

e≦

e′

).

21. The medium recited in claim 20, the method embodied thereon further comprising using a mapping means for mapping an integer interval value to a group.

22. The medium recited in claim 20, the method embodied thereon further comprising mapping groups to an integer interval value, the integer interval value expressed as an interval over integers.

23. The medium recited in claim 22, wherein mapping maintains a hierarchial relationship within a group partial order of groups.

24. The medium recited in claim 23, the group partial order being maintained wherein G is a set of groups {g₁, g₂, . . . g_M} and π

represents a mapping from G to an integer interval value, and π

respects a group partial order <

G of GROUP if for each pair of groups of g, h ε

G, g<

G^h if π

(g)<

₁ π

(h), and π

respects a group partial order >

G of GROUP if for each pair of groups g, h ε

G, g>

G^h if π

(g)<

_I π

(h).

25. The medium recited in claim 21, the method embodied thereon further comprising ordering a collection of integer interval values to define a hierarchial relationship between integer interval values in the collection.

26. The medium recited in claim 25, the method embodied thereon further comprising using an ordering means for defining the hierarchial relationship.

27. The medium recited in claim 22, the method embodied thereon further comprising ordering a collection of integer interval values to define a hierarchial relationship between integer interval values in the collection.

28. The medium recited in claim 27, the method embodied thereon further comprising using an ordering means for defining the hierarchial relationship.

29. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method to regulate access to an object in a database by decomposing a directed acyclic graph representing a hierarchial structure of integer interval values (iDAG), each value mapped to a group, said method comprising:

decomposing the iDAG into multiple directed acyclic graphs (DAG) G_S and G₁ having an overlap, wherein G₁=G′

_S, and wherein G′

_S is an iDAG and G_S is a simplified DAG; and

recursively repeating the decomposition on G_S, wherein (G₂=G″

_S, . . . , G_k=G_S^k) is formed by the recursion and are iDAGs, and wherein G_i is a newly formed iDAG comprising (G′

_S, . . . , G_S^k′

) and structured by hierarchial order.

30. The medium recited in claim 29, the method embodied thereon further comprising generating an interval-map for G_i using a mapping means where 1≦

i≦

k.

31. The medium recited in claim 30, the method embodied thereon further comprising:

allowing a group g₁ having an interval A access to the object in the database; and

allowing a group g₂ having an interval B access to the object if the interval of B is contained within the interval of A.

32. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method to regulate access to a system'"'"'s database, said method comprising:

decomposing a directed acyclic graph (DAG) G having nodes and leaves into a collection of DAGs having nodes and leaves, each DAG in the collection being simpler in structure than G;

mapping a group g to a DAG in the collection; and

using a query structure of the DAG to decide if g may access the object.

33. The medium recited in claim 32, wherein the query structure comprises an interval over integer mapping to each g and comparison.

34. The method recited in claim 32, wherein the query structure comprises a hash table listing all gs allowed access to the object, and g is compared to all groups in the hash table.

35. The method recited in claim 33, a DAG in the collection being more simply structured if it has less nodes or leaves than G.

36. The method recited in claim 34, a DAG in the collection being more simply structured if it has less nodes or leaves than G.

37. A digital signal processing apparatus to regulate access to a system'"'"'s database, comprising:

a storage unit;

a processor;

circuitry communicatively connecting the processor to the storage unit, the processor capable of executing commands and data to regulate access to any object contained in the database by;

allowing a first group g_m comprising one or more data requesters access to a data object contained in the database;

mapping g_m to a first interval value and a second group g_n to a second interval value, wherein g_n contains at least one data requester U; and

allowing U access to the data object if the second interval value for g_n is contained within the first interval value for g_m.

38. The apparatus recited in claim 37, wherein mapping to an interval value comprises mapping to an integer interval value, wherein b and e are integers defining the second interval and b≦

e, wherein b′ and

e′

are integers defining the first interval and b′

≦

e′ and

wherein the second interval is contained within the first interval if (b′

≦

b≦

e≦

e′

).

39. The apparatus recited in claim 38, further comprising using a mapping means for mapping an integer interval value to a group.

40. The method recited in claim 39, further comprising mapping groups to an integer interval value, the integer interval value expressed as an interval over integers.

41. The apparatus recited in claim 40, the mapping maintaining a hierarchial relationship within a group partial order of groups.

42. The apparatus recited in claim 41, the group partial order being maintained wherein G is a set of groups {g₁, g₂, . . . g_m} and π

represents a mapping from G to an integer interval value, and π

respects a group partial order <

G of GROUP if for each pair of groups of g, h ε

G, g<

G^h if π

(g)<

_I π

(h), and π

respects a group partial order >

G of GROUP if for each pair of groups g, h ε

G, g>

G^h if π

(g)<

_I π

(h).

43. The apparatus recited in claim 42, further comprising ordering a collection of integer interval values to define a hierarchial relationship between integer interval values in the collection.

44. The apparatus recited in claim 43, further comprising using an ordering means for defining the hierarchial relationship.

45. The apparatus recited in claim 44, further comprising ordering a collection of integer interval values to define a hierarchial relationship between integer interval values in the collection.

46. The apparatus recited in claim 45, further comprising using an ordering means for defining the hierarchial relationship.

47. A digital signal processing apparatus to regulate access to a system'"'"'s database, comprising:

a storage unit;

a processor;

circuitry communicatively connecting the processor to the storage unit, the processor capable of executing commands and data to regulate access to any object contained in the database by;

decomposing the iDAG into multiple directed acyclic graphs (DAG) G_S and G₁ having an overlap, wherein G₁=G′

_S and wherein G′

_S is an iDAG and G_S is a simplified DAG; and

recursively repeating the decomposition on G_S, wherein (G₂=G_S″

. . . , G_k=G_S^k′

) formed by the recursion and are iDAGs, and wherein G_i is a newly formed iDAG comprising (G_S′

. . . , G_S^k′

) and structured by hierarchial order.

48. The apparatus recited in claim 47, further comprising:

allowing a group g₁ having an interval A access to the object in the database; and

allowing a group g₂ having an interval B access to the object if the interval of B is contained within the interval of A.

49. The apparatus recited in claim 48, further comprising:

decomposing a directed acyclic graph (DAG) G having nodes and leaves into a collection of DAGs having nodes and leaves, each DAG in the collection being simpler in structure than G;

mapping a group g to a DAG in the collection; and

using a query structure of the DAG to decide if g may access the object.

50. A digital signal processing apparatus to regulate access to a system'"'"'s database, comprising:

a storage unit;

a processor;

circuitry communicatively connecting the processor to the storage unit, the processor capable of executing commands and data to regulate access to any object contained in the database by;

decomposing a directed acyclic graph (DAG) G having nodes and leaves into a collection of DAGs having nodes and leaves, each DAG in the collection being simpler in structure than G;

mapping a group g to a DAG in the collection; and

using a query structure of the DAG to decide if g may access the object.

51. The digital signal processing apparatus recited in claim 50, wherein the query structure comprises an interval over integer mapping to each g and comparison.

52. The digital signal processing apparatus recited in claim 51, wherein the query structure comprises a hash table listing all g_S allowed access to the object, and a group g_i is compared to all groups in the hash table.

53. The digital signal processing apparatus recited in claim 50, further comprising a DAG in the collection being more simply structured if it has less nodes or leaves than G.

54. The digital signal processing apparatus recited in claim 51, further comprising a DAG in the collection being more simply structured if it has less nodes or leaves than G.

55. A digital signal processing apparatus to regulate access to a system'"'"'s database, comprising:

a storage means for storing digital signals;

a processor means for interpreting digital signals to regulate access to any object contained in the database by;

allowing a first group g_m comprising one or more data requesters access to a data object contained in the database;

mapping g_m to a first interval value and a second group g_n to a second interval value, wherein g_n contains at least one data requester U; and

allowing U access to the data object if the second interval value for g_n is contained within the first interval value for g_m; and

circuitry means for communicatively coupling the storage means to the processor means.

56. The apparatus recited in claim 55, wherein mapping to an interval value comprises mapping to an integer interval value, wherein b and e are integers defining the second interval and b≦

e, wherein b′ and

e′

are integers defining the first interval and b′

≦

e′ and

wherein the second interval is contained within the first interval if (b′

≦

b≦

e≦

e′

).

57. The apparatus recited in claim 56, further comprising a module means for displaying status and query results.