In Facebook-style Social Network Systems (FSNSs), which are a generalization
of the access control model of Facebook, an access control policy specifies a graphtheoretic
relationship between the resource owner and resource accessor that must hold
in the social graph in order for access to be granted. Pseudonymous identities may
collude to alter the topology of the social graph and gain access that would otherwise
be forbidden. We formalize Denning’s Principle of Privilege Attenuation (POPA) as a
run-time property, and demonstrate that it is a necessary and sufficient condition for
preventing the above form of Sybil attacks. A static policy analysis is then devised for
verifying that an FSNS is POPA compliant (and thus Sybil free). The static analysis is
proven to be both sound and complete. We also extend our analysis to cover a peculiar
feature of FSNS, namely, what Fong et al. dubbed as Stage-I Authorization. We
discuss the anomalies resulted from this extension, and point out the need to redesign
Stage-I Authorization to support a rational POPA-compliance analysis.