From Isomorphism-Based Security for Graphs to Semantics-Preserving Security for the Resource Description Framework
In this work we address security in the context of the Resource Description Framework (RDF). RDF is a graph-like data model designed for the web. One of its compelling features is a precise, model-theoretic semantics. We first observe that the problem of securing RDF is related closely to the more traditional problem of securing graphs. Consequently, before we address security for RDF, we make broader contributions to security in the context of graphs. Specifically, we reconcile four different notions of security that have been proposed in prior work, and compare them from the standpoint of strength of security — whether satisfaction of one implies satisfaction of another. We then ask whether strength of security is correlated to computational complexity. We make the somewhat surprising observation that the answer to this question is, “no.” We then extend the two strongest notions of security in a natural way for RDF. We establish results on RDF’s semantics that then gives us a way of meaningfully quantifying the loss of information from security. Thus, for RDF, we are able to pose the natural trade-off between information-quality and security in a precise way. We show that a corresponding decision problem is NP-complete, and with a reduction to CNF-SAT that we have designed and implemented, present empirical results on realistic data. Our empirical results show interesting relationships between the various parameters, such as the size of the graph versus the information-loss, while maintaining a particular level of security.