PROTOSS: Stopping Privacy Leaks Before They Happen in Social Networks

TL;DR

Online Social Networks (OSNs) often leak your data not because they break their own rules, but because shared relations make it easy to guess your secrets. PROTOSS is a runtime tool that uses Model Checking and Social Commitments to simulate how information flows through your social circle, flagging "inference-based" privacy violations that standard privacy settings miss.

Background: The Illusion of Privacy Settings

We’ve all seen it: you set your location to "Private," but you tag a friend in a photo who has their location set to "Public." Suddenly, your whereabouts are no longer a secret. This is an inference leakage.

Current OSNs treat privacy as a bilateral agreement between you and the platform. However, the authors argue that in a social setting, privacy is interdependent. Your privacy depends on your relations (friend, colleague, family) and the rules governing those roles.

Methodology: Formalizing Social Rules

The core innovation of PROTOSS lies in its conversion of messy social interactions into a rigorous mathematical model.

1. Social Commitments

Instead of simple "Allow/Deny" rules, the authors use Commitments: C(debtor, creditor, condition, proposition).

• Example: The OSN (debtor) commits to Charlie (creditor) that if Charlie is at a conference (condition), his location will not be visible to colleagues (proposition).

2. Inference Rules: The "Hidden" Leakage

PROTOSS accounts for the "Physical Intuition" of the world through local rules. For example: visible(location(Y, W), Z) ← visible(with(X, Y), Z) ∧ visible(location(X, W), Z) Translation: If User Z knows X and Y are together, and Z knows where X is, Z automatically knows where Y is.

3. The Architecture

The PROTOSS engine acts as a "Privacy Checker" sitting between the user and the OSN operator. It feeds the social graph and commitments into NuSMV, a symbolic model checker that explores all possible "states" of the network to see if a privacy violation (a CTL formula) could ever become true.

Experiments: Why "Dual Roles" Are Dangerous

The researchers tested PROTOSS on scenarios involving three users: Charlie, Sally, and Linus.

• Case 1 (Safe): If the system only tracks "who is with whom" but doesn't have a rule for sharing raw location data, Charlie’s privacy remains intact even if he is with a public user.
• Case 2 (Violation): If Linus is both a friend (allowed to see location) and a colleague (restricted from seeing location), a conflict arises. PROTOSS detects that the "Colleague" privacy commitment is violated because the "Friend" relationship leaks the data.

In the interface above, the right pane displays the result of the NuSMV check, showing whether a specific privacy property holds or is violated based on current network relations.

Critical Insight: Beyond Content Filtering

The value of this work is the realization that Privacy is a graph problem, not a file-permission problem.

While modern platforms like Meta or X focus on filtering what you post, PROTOSS checks the reachability of information through the social graph. By using Computation Tree Logic (CTL), the tool doesn't just look at the current state; it looks at all future possible states—such as what happens if you add a new friend or join a new group.

Limitations and Future Work

• Scalability: Model checking is computationally expensive (state-space explosion). Running this for millions of users on Facebook would require significant optimization or localized graph partitioning.
• User Modeling: The tool assumes users can define their relations accurately. In reality, users often struggle with complex privacy categories.

Conclusion

PROTOSS demonstrates that formal methods—usually reserved for hardware verification—have a place in the social web. By treating our social interactions as a state-transition system, it offers a glimpse into a future where OSNs can proactively warn users: "Warning: Tagging this person will reveal your location to your boss."