head 1.4; access; symbols; locks; strict; comment @# @; 1.4 date 2002.10.29.12.52.55; author thl; state dead; branches; next 1.3; 1.3 date 2002.10.09.14.12.11; author thl; state Exp; branches; next 1.2; 1.2 date 2002.10.09.08.57.20; author thl; state Exp; branches; next 1.1; 1.1 date 2002.10.09.08.31.44; author rse; state Exp; branches; next ; desc @@ 1.4 log @move definitions @ text @ A UNIVERSAL OBJECT RELATION MODEL (CAN BE USED FOR ACLs) ======================================================== TRUSTEE A "trustee" is an entry in the "grants"-table and is a triple which defines who has what relation where. who what where source --- sign/relation --> target The source (who?) of the relation can be any object. The relation (what?) itself is any of those defined in the "relations"-table, prefixed with a sign that marks if the wholly "trustee" is a inclusion or exclusion. Finally, the target (where?) defines where the relation is to be applied to. EQUIVALENCE The source of a given "trustee" extends it's meaning to the left. It must be resolved to cover any equivalent objects. This requires a recursive search for all equivalent relations "eqrel". Recursion stops if no more relations are found or the search hit the "eqlevel" maximum nesting mark. An "eqlevel" of 0 inhibits the search for equivalent relations. SCOPE The scope of a given "trustee" extends it's meaning to the right. It must be resolved to cover any scoped objects. This requires a recursive search for all scoped relations "screl". Recursion stops if no more scopes are found or the search hit the "sclevel" maximum nesting mark. An "sclevel" of 0 inhibits the search for equivalent relations. ORL The "object relation list" contains the effective relations of all objects to each other. Given n objects and m relations the maximum number of ORL entries will be n^2*m which is certainly a scalability limitation of this model when the ORL is required to be precalculated rather than effective relations being calculated on the fly. When the relations define access control the ORL becomes a ACL. PATH The model can handle inclusive and exclusive trustees. When the effective relations are calculated (i.e. a ORL is build) every trustee being applied to a scope requires a strength to be used. Stronger relations override weaker relations. Strength is computed from the path on the equivalence graph where shorter pathes mean stronger relations. SAMPLE willi + "read access to" account3 "occupant of" oo leaders + "write access to" account4 rse + "write access to" dev oo "parent is" "occupant of" oo team + "read access to" dev oo "parent is" OBJECTS "user" oo is "child of", "member of", "occupant of", "proxy of" "nestedgroup" oo is "child of", "member of" "directgroup" 0 is "child of", "member of" "container" oo is "child of" "role" oo is "child of" RELATION [NULL] - inhibits other relations "member of" "occupies role of" "proxy of" "child of" "read access to" "write access to" x distance from source object, confict flag required for equal distances o priorities on each relation o query object o include/exclude by definition, not order VIEW admin vs. code Start with group, add members - every member gets "member of" set Start with role, add occupant - every occupant gets "fulfiles role" set Start with user, define proxy - every proxy gets "proxy of" set Start with container, define childs - every child gets "parent is" set SOURCE, TARGET any object EQUIVALENCE SOURCE = user-1382 and %eqlevel "proxies" (found by searching for all objects which are "proxy of user-1382") SOURCE = group-38 and %eqlevel "members" (found by searching for all objects which are "members of group-38") SOURCE = container-3 and %eqlevel "childs" (found by searching for all objects whose "parent is container-3") ALGORITHM // // RS_i ns b R nt RT_i // A_i ----->* S =====> T *<---- Z_i // // // A_i equivalence object(s) // RS_i source equivalence relationship(s) // ns equivalence maximum distance from source S // S source object // b relationship include/exclude // R relationship // T target object // RT_i target scope relationship(s) // nt scope maximum distance from target T // Z_i scope object(s) // defined relationships (pre-configured input) @@DR := { } = { ... } // S,R,T primary key // S,T possibly wildcards // #DR = ... // set relations (run-time admin input) @@SR := { } = { ... } // #SR = n // configured to effective relationship algorithm function drcr2er(@@DR, @@SR): @@ER { // O(n^3) // effective relationships (calculated result) @@ER := { } = 0 foreach $cr (@@SR) { // O(n) --> O(n^3) // O(n) @@EQ := { } = 0 <$RS_i,$ns> = lookup_ns_and_rsi_in_dr(@@DR, <$cr.S,$cr.R,$cr.T>) dfs_S(\@@EQ, @@DR, @@SR, $RS_i, $cr.S, $ns) // O(n) @@SC := { } = 0 <$RT_i,$nt> = lookup_nt_and_rti_in_dr(@@DR, <$cr.S,$cr.R,$cr.T>) dfs_T(\@@EQ, @@DR, @@SR, $RT_i, $cr.T, $nt) // O(n^2) foreach $eq (@@EQ) { // O(n) foreach $sc (@@SC) { // O(n) so sn to tn // O(1) = = , resolve b via R-specific conflict flag (prefer include or exlude) = < (nop) = > < = (nop) < < (nop) < > > = > < > > } } } return @@ER; } function dfs_S(\@@EQ, @@DR, @@SR, $R, $s, $d): { // O(n) if ($d == 0) return; ..insert <$s,$d> into @@EQ... foreach $a (...lookup $a=$cr.S in @@SR where ($cr.R == $R and $cr.T==$s)...) { // O(n) if (not ($a in @@EQ)) dfs(\@@EQ, @@SR, $a, $d-1) } } function lookup_ns_and_rsi_in_dr(@@DR, $t := ): $d { $d = 0 @@D = [] $R = ... FIXME ... foreach $dr (@@DR) { if ($dr.S == "*" && $dr.R == $t.R && $dr.T == "*" ) $D[0] = $dr.ns if ($dr.S == "*" && $dr.R == $t.R && $dr.T == $t.T) $D[1] = $dr.ns if ($dr.S == $t.S && $dr.R == $t.R && $dr.T == "*" ) $D[2] = $dr.ns if ($dr.S == $t.S && $dr.R == $t.R && $dr.T == $t.T) $D[3] = $dr.ns, break } $d = (def($D[3]) ? $D[3] : (def($D[2]) ? $D[2] : (def($D[1]) ? $D[1] : (def($D[0]) ? $D[0] : 0)))) return <$R,$d> } @ 1.3 log @flush and break at "object class vs. instance" and "usefulness outside acl" problems @ text @@ 1.2 log @object relation model @ text @d124 3 a126 3 // configured relationships (run-time admin input) @@CR := { } = { ... } // #CR = n d129 1 a129 1 function drcr2er(@@DR, @@CR): @@ER { // O(n^3) d132 1 a132 1 foreach $cr (@@CR) { // O(n) --> O(n^3) d137 1 a137 1 dfs_S(\@@EQ, @@DR, @@CR, $RS_i, $cr.S, $ns) d142 1 a142 1 dfs_T(\@@EQ, @@DR, @@CR, $RT_i, $cr.T, $nt) d163 1 a163 1 function dfs_S(\@@EQ, @@DR, @@CR, $R, $s, $d): { // O(n) d166 1 a166 1 foreach $a (...lookup $a=$cr.S in @@CR where ($cr.R == $R and $cr.T==$s)...) { // O(n) d168 1 a168 1 dfs(\@@EQ, @@CR, $a, $d-1) d177 4 a180 9 if ($dr.S == "*" && $dr.R == $t.R && $dr.T == "*") $D[0] = $dr.ns else if ($dr.S == "*" && $dr.R == $t.R && $dr.T == $t.T) $D[1] = $dr.ns else if ($dr.S == $t.S && $dr.R == $t.R && $dr.T == "*") $D[2] = $dr.ns else if ($dr.S == $t.S && $dr.R == $t.R && $dr.T == $t.T) $D[3] = $dr.ns break d183 4 a186 4 (def($D[2]) ? $D[2] : (def($D[1]) ? $D[1] : (def($D[0]) ? $D[0] : 0)))) @ 1.1 log @first cut for O(n^3) effective relationship calculation @ text @d2 100 @