CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Model checking social network models

Raul Pardo Jimenez (Institutionen för Data- och informationsteknik, Formella metoder (Chalmers)) ; Gerardo Schneider
8th International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2017, Roma, Italy, 20-22 September 2017 (2075-2180). Vol. 256 (2017), p. 238-252.
[Konferensbidrag, refereegranskat]

A social network service is a platform to build social relations among people sharing similar interests and activities. The underlying structure of a social networks service is the social graph, where nodes represent users and the arcs represent the users' social links and other kind of connections. One important concern in social networks is privacy: what others are (not) allowed to know about us. The "logic of knowledge" (epistemic logic) is thus a good formalism to define, and reason about, privacy policies. In this paper we consider the problem of verifying knowledge properties over social network models (SNMs), that is social graphs enriched with knowledge bases containing the information that the users know. More concretely, our contributions are: i) We prove that the model checking problem for epistemic properties over SNMs is decidable; ii) We prove that a number of properties of knowledge that are sound w.r.t. Kripke models are also sound w.r.t. SNMs; iii) We give a satisfaction-preserving encoding of SNMs into canonical Kripke models, and we also characterise which Kripke models may be translated into SNMs; iv) We show that, for SNMs, the model checking problem is cheaper than the one based on standard Kripke models. Finally, we have developed a proof-of-concept implementation of the model-checking algorithm for SNMs.



Denna post skapades 2017-10-25. Senast ändrad 2017-11-08.
CPL Pubid: 252754

 

Läs direkt!

Lokal fulltext (fritt tillgänglig)

Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för Data- och informationsteknik, Formella metoder (Chalmers)
Institutionen för data- och informationsteknik (GU) (GU)

Ämnesområden

Datavetenskap (datalogi)

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:


Privacy Policies for Social Networks - A Formal Approach