Quel est le meilleur moyen d'adapter ce système de sécurité pour traiter l'héritage multiple ?

Question

Attachez vos ceintures, c'est une question délicate.

Nous avons un système qui gère de gros ensembles de données. (des millions à des milliards d'enregistrements par table). Toutes les données sont gérées dans une structure arborescente de nœuds.

Nous utilisons Symfony2, et le système de sécurité Symfony2 (Objets de domaine, Acls, Aces, etc). Notre arborescence Acl reflète notre arborescence de nœuds.

Pour inventer un langage :

• DP Permission définie, c'est-à-dire un enregistrement ace sur ce nœud acl
• EP Permission effective, aucun enregistrement ace, permission héritée d'un parent avec un DP

En termes de logique métier, nous attribuons 0 ou 1 ace à un objet par utilisateur et nous nous appuyons sur l'héritage lorsqu'il n'existe pas. Root > lvl1 (DP: VIEW) > lvl2 > lvl3 (EP: VIEW)

Jusque-là, tout va bien. Tout cela fonctionne.

Certains nœuds non seulement ont un parent, mais sont associés à d'autres nœuds (plusieurs à plusieurs). Lorsqu'un nœud est associé à un autre nœud, cela représente un chemin séparé à suivre pour les acls. Par exemple, nous aurions 1 ou plusieurs chemins jusqu'à la racine pour rassembler les ace.

Leaf < Parent < GrandParent < Root
Leaf < AssociatedNode < AssociatedNodeParent < AssociatedNodeGrandParent < Root
 ...

L'ajout d'une logique pour gérer le vote des aces est bien, mais ce dont nous ne sommes pas sûrs, c'est comment représenter les multiples chemins jusqu'à la racine. Nos idées actuelles (lire : mauvaises) sont les suivantes :

• Comportement de plusieurs parents dans l'arborescence acl
  • Avantages
    • Semble plus propre ?
  • Inconvénients
    • Presque une réécriture complète du système de sécurité pour le mettre en place.
    • Potentiel de devenir très complexe.
• Identités d'objets / acls dupliqués contre des entités, en spécifiant différents parents.
  • Avantages
    • Euh...
  • Inconvénients
    • Créera potentiellement un très grand nombre d'enregistrements acl.
    • Difficile à gérer dans le code.

Answer 1

Dans votre cas de parent multiple, vous avez effectivement une traversée d'arbre inverse de votre nœud initial à tout nœud contenant un as. Ainsi, si nous visualisons les opérations de traversée vers le haut et sur le côté comme leur propre arbre (élaguant les boucles), vous pourriez, potentiellement, parcourir l'ensemble de votre réseau de nœuds avant de trouver un as dans le pire des cas.

La façon la plus simple de résoudre cela serait de garantir une sorte de propriété de tas qui assure que chaque nœud avec un as a une valeur grande ou petite qui peut conduire la traversée. Cela réduit le temps de traversée du pire cas de O(n) (si vous aviez recherché chaque nœud dans votre index de base de données) à O(log n) alors que vous suivez le chemin de retour à travers le réseau.

La raison pour laquelle obtenir une traversée O(1) ici est difficile est que votre réseau de nœuds garantit la possibilité de boucles. Mais, si vous construisez un graphe ACL en maintenant les propriétés d'un tas minimum, vous devriez vous en sortir.

Bonne chance avec votre modèle de permissions.

Answer 2

Encore une fois, comme mentionné, il s'agit d'un problème intéressant mais non trivial - merci! Maintenant, je sais comment je vais devoir passer ce week-end :-) Je pourrais également envisager l'idée du tas, mais je le ferais sous forme de tas threadé. Chaque nœud dans le tas contient un pointeur vers un "index" ACL, si vous voulez.

Supposons que j'ai juste trois nœuds dans l'exemple (R(acine), P(arent) et N(œud)). Ainsi, l'ensemble ACL pour N est ACL(R)+ACL(P)+ACL(N). Supposons que lorsqu'un nœud est créé, ce nœud contient un pointeur X qui pointe vers un index de nœud. Donc R(X) = ACLIndex(R). Aucun nœud lui-même ne contient réellement son ACL.

Maintenant, pour un nœud N donné, je dois encore remonter à la racine dans le pire des cas, mais je saute simplement autour d'un index plat pour le faire plutôt que de rebondir partout dans l'arbre. Il serait préférable si vous pouviez affirmer que pour un nœud N donné, il n'y a qu'un seul chemin vers N, ou, s'il y a plusieurs chemins, que N conserve un autre tableau de traversées de telle sorte que, pour N, le chemin vers N depuis le nœud A soit répertorié dans ce tableau. En effet, il faut laisser des miettes de pain dans N lorsqu'un nœud s'y attache.

Je me demande si nous pouvons emprunter un concept de la géolocalisation. Il n'est pas possible pour votre petit GPS de poche de conserver toutes les routes les plus courtes possibles de n'importe quel point à n'importe quel point, et de tenir compte des temps de trajet. Il triche et divise les cartes en "tuiles". Comme vous ne pouvez pas être partout sur la carte en même temps, mais plutôt, vous êtes limité à une tuile dans laquelle vous vous trouvez actuellement, il vous suffit de calculer les chemins les plus courts de cette tuile à ses sorties connues. Une fois que vous prenez une sortie, il charge cette tuile et recommence. En effet, nous utilisons le principe de la localité pour réduire la portée.

Et si nous utilisions la même idée? Pour un nœud donné, si vous divisiez l'arbre d'accès en "shards", vous pourriez précalculer les coûts ou du moins les mettre à jour, et ensuite le coût du chemin de R à N est simplement la somme des coûts du shard plus le coût du chemin dans votre shard local.