Transcript presentation

Evaluating Role Mining
Algorithms
Ian Molloy, Ninghui Li, Tiancheng Li, Ziqing
Mao, Qihua Wang, Jorge Lobo
Role Mining Overview
• Data mining techniques to discover roles from
existing system configuration data.
• Uses automated techniques.
• Can accelerate the role engineering process
Role Mining Algorithms
• Algorithms have only been evaluated when
they were proposed
• No standardized method of evaluating
algorithms
• Some framework should exist to be able to
compare role mining algorithms performance
Evaluating Role Mining Algorithms
• Three questions must be answered
1. What does a role mining algorithm output?
2. What criteria should be used to compare the outputs from
different role mining algorithms?
3. What input datasets should be used?
Evaluating Role Mining Algorithms
• Categorized algorithms into two classes based
on output
• Class 1 algorithms output a sequence of
prioritized roles
• Class 2 algorithms output complete RBAC
states
• Class 1 algorithms can be converted into Class
2 algorithms and vice versa
Class 1 Algorithms
• Prioritized list of candidate roles, each of
which is a set of permissions
• Two phases:
(a) identify a set of candidate roles from
data
(b) assign a priority value to each
candidate role (a higher priority is more
important and useful)
Class 2 Algorithms
• Output is a complete RBAC state
• Take as input a configuration <U, P, UP> and
outputs <R, UA, PA, RH, DUPA>
where:
R is a set of roles
UA is the user-role assignment
PA is the role-permission assignment
RH is the role hierarchy
DUPA is the direct user-permission assignment relation
• Often try to generate an RBAC state that
minimizes some cost measure
Metrics for Comparing Algorithms
• Quality of RBAC states
• Prioritized Role Quality
Input Datasets
• Real-world Data
• Synthetic Data
– Random
– Tree-based data generation
– ERBAC data generation
Role Mining Algorithms
Class 1 Algorithms:
• CompleteMiner (CM) and FastMiner(FM)
• DynamicMiner (DM)
• PairCount (PC)
Class 2 Algorithms:
• ORCA
• Graph Optimization (GO)
• HP Role Minimization (HPr)
• HP Edge Minimization (Hpe)
• HierarchicalMiner (HM)
Algorithm Evaluation Results
• HM tended to do the best except in
minimizing the number of roles
• Synthetic data results largely echoed realworld data
• Results indicate that algorithms which strive
to minimize the number of roles often
generate RBAC states with a larger number of
edges.