Efficient large-scale access control for internet/intranet information systems
AssigneeInternational Business Machines Corporation
InventorsQi Lu, Shang-Hua Teng
Life of this patent
Estimating the term…
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.
Claims57
A method to regulate access to a system's database using interval containment control, comprising:
- allowing a first group gm comprising one or more data requesters access to a data object contained in the database;
- mapping gm to a first interval value and a second group gn to a second interval value, wherein gn contains at least one data requester U;
- and
- allowing U access to the data object if the second interval value for gn is contained within the first interval value for gm.
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) GS and G1 having an overlap, wherein G1=G′S and wherein G′S is an iDAG and GS is a simplified DAG;
- and
- recursively repeating the decomposition on GS, wherein (G2=GS″ . . . , Gk=GSk) formed by the recursion and are iDAGs, and wherein Gi is a newly formed iDAG comprising (GS′ . . . , GSk′) and structured by hierarchial order.
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.
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 gm access to a data object contained in the database;
- mapping gm to a first interval value and a second group gn to a second interval value, wherein gn contains at least one user member U;
- and
- allowing U access to the data object if the second interval value for gn is contained within the first interval value for gm.
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) GS and G1 having an overlap, wherein G1=G′S, and wherein G′S is an iDAG and GS is a simplified DAG;
- and
- recursively repeating the decomposition on GS, wherein (G2=G″S, . . . , Gk=GSk) is formed by the recursion and are iDAGs, and wherein Gi is a newly formed iDAG comprising (G′S, . . . , GSk′) and structured by hierarchial order.
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.
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 gm comprising one or more data requesters access to a data object contained in the database;
- mapping gm to a first interval value and a second group gn to a second interval value, wherein gn contains at least one data requester U;
- and
- allowing U access to the data object if the second interval value for gn is contained within the first interval value for gm.
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) GS and G1 having an overlap, wherein G1=G′S and wherein G′S is an iDAG and GS is a simplified DAG;
- and
- recursively repeating the decomposition on GS, wherein (G2=GS″ . . . , Gk=GSk′) formed by the recursion and are iDAGs, and wherein Gi is a newly formed iDAG comprising (GS′ . . . , GSk′) and structured by hierarchial order.
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.
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 gm comprising one or more data requesters access to a data object contained in the database;
- mapping gm to a first interval value and a second group gn to a second interval value, wherein gn contains at least one data requester U;
- and
- allowing U access to the data object if the second interval value for gn is contained within the first interval value for gm;
- and
- circuitry means for communicatively coupling the storage means to the processor means.
Dependencies are inferred from the claim text.