UURAC: Redefining Social Privacy through Regular Expression Path Checking

Executive Summary

TL;DR: The paper proposed a novel access control model, UURAC, specifically designed for the complex, graph-based architecture of Online Social Networks (OSNs). By treating social relationships as labeled edges in a graph, the authors use Regular Expressions to define how users can access resources based on the type and depth of their connection to the owner.

Context: Within the academic landscape of security, this work marks a shift from centralized Role-Based Access Control (RBAC) to a decentralized, topology-aware model. It bridges the gap between simple "Friend" toggles and formal logic-based security systems.

The Core Problem: Why Traditional Security Fails OSNs

In a standard corporate environment, you are a "Manager" or an "Engineer." In a social network, your identity is relative. You are Alice's "Brother," Bob's "Co-worker," and Charlie's "Friend." Traditional models (DAC/RBAC) struggle because:

• Scale: Explicitly naming users in a whitelist is impossible for millions of participants.
• Dynamics: Relationships change faster than system administrators can update roles.
• Individualization: Every user wants to be the "admin" of their own profile.

Methodology: The Power of Path Patterns

The innovation of UURAC lies in its use of Path Specifiers based on regular expressions. Instead of just "Friends of Friends," a user can specify:

• f+: A chain of one or more friends.
• fc?: A friend followed by an optional co-worker transition.
• (f|c)*: Any sequence of friends or co-workers.

Model Architecture

The system processes an access request by Evaluating a triple: <Accessing User, Action, Target>. The authorization engine must find a path on the social graph that matches the regular expression defined in the policy.

Figure 1: The UURAC component interaction model, showing how users, actions, and targets are processed.

Path Checking: DFS vs. BFS

The authors developed two primary algorithms to verify these paths. They convert the regular expression policy into a Deterministic Finite Automaton (DFA). As the algorithm traverses the social graph, the DFA tracks the "state" of the relationship.

• DFS (Depth-First Search): Explores one path to its maximum depth (hop count) before backtracking. It is memory-efficient but can get stuck in long, fruitless branches.
• BFS (Breadth-First Search): Explores all connections layer by layer. It is guaranteed to find the shortest path first but requires more memory to store multiple DFA states simultaneously.

Experimental Insights

Through rigorous testing on synthetic datasets, several technical truths emerged:

1. Small World Dominance: Most "True" access decisions occur within 3–4 hops. In OSNs, if a path exists, it's usually short.
2. Scalability: While the worst-case complexity is $O(d_{max}^{Hopcount})$, the sparsity of real social graphs makes this manageable for practical use.
3. Efficiency: DFS generally outperforms BFS in OSN settings because it doesn't suffer from the massive overhead of managing a queue of thousands of potential paths in dense clusters.

Figure 2: Performance analysis showing the impact of node degree and hop count on execution time.

Critical Analysis & Conclusion

The UURAC model is a significant step forward in Relationship-Based Access Control (ReBAC). By using regular expressions, it provides a "User-UX-friendly" way to represent complex logical constraints that were previously only possible in heavyweight modal logics.

Limitations:

• The model assumes a Simple Graph (no multiple edges between same users).
• It predominantly focuses on U2U (User-to-User) relationships, whereas modern OSNs are increasingly defined by U2R (User-to-Resource) interactions (e.g., "Liked," "Tagged," "Purchased").

Future Outlook: The industry is moving toward "Attribute-Aware" models where the path checking isn't just about who you know, but what those people's attributes are (e.g., "A friend who is also over 18"). UURAC provides the mandatory topological foundation for these future developments.