{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T01:07:21Z","timestamp":1791162441385,"version":"4.1.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>Many applications, including provenance and some analyses of social networks, require path-based queries over graphstructured data. When these graphs contain sensitive information, paths may be broken, resulting in uninformative query results. This paper presents innovative techniques that give users more informative graph query results; the techniques leverage a common industry practice of providing what we call surrogates: alternate, less sensitive versions of nodes and edges releasable to a broader community. We describe techniques for interposing surrogate nodes and edges to protect sensitive graph components, while maximizing graph connectivity and giving users as much information as possible. In this work, we formalize the problem of creating a protected account G' of a graph G. We provide a utility measure to compare the informativeness of alternate protected accounts and an opacity measure for protected accounts, which indicates the likelihood that an attacker can recreate the topology of the original graph from the protected account. We provide an algorithm to create a maximally useful protected account of a sensitive graph, and show through evaluation with the PLUS prototype that using surrogates and protected accounts adds value for the user, with no significant impact on the time required to generate results for graph queries.<\/jats:p>","DOI":"10.14778\/2002974.2002979","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"518-525","source":"Crossref","is-referenced-by-count":11,"title":["Surrogate parenthood"],"prefix":"10.14778","volume":"4","author":[{"given":"Barbara","family":"Blaustein","sequence":"first","affiliation":[{"name":"The MITRE Corporation, Colshire Drive, Mclean, VA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adriane","family":"Chapman","sequence":"additional","affiliation":[{"name":"The MITRE Corporation, Colshire Drive, Mclean, VA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Len","family":"Seligman","sequence":"additional","affiliation":[{"name":"The MITRE Corporation, Colshire Drive, Mclean, VA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. David","family":"Allen","sequence":"additional","affiliation":[{"name":"The MITRE Corporation, Colshire Drive, Mclean, VA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arnon","family":"Rosenthal","sequence":"additional","affiliation":[{"name":"The MITRE Corporation, Colshire Drive, Mclean, VA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242598"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2008.4498325"},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"Securing Provenance","author":"Braun U.","year":"2008","unstructured":"U. Braun , A. Shinnar , and M. Seltzer , \" Securing Provenance ,\" USENIX HotSec , pp. 1 -- 5 , 2008 . U. Braun, A. Shinnar, and M. Seltzer, \"Securing Provenance,\" USENIX HotSec, pp. 1--5, 2008.","journal-title":"USENIX HotSec"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/WAIM.2008.41"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687687"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989305"},{"key":"e_1_2_1_7_1","first-page":"215","article-title":"Enabling Privacy in Provenance-Aware Workflow Systems","author":"Davidson S. B.","year":"2011","unstructured":"S. B. Davidson , S. Khanna , V. Tannen , S. Roy , Y. Chen , T. Milo , and J. Stoyanovich , \" Enabling Privacy in Provenance-Aware Workflow Systems ,\" CIDR , pp. 215 -- 218 , 2011 . S. B. Davidson, S. Khanna, V. Tannen, S. Roy, Y. Chen, T. Milo, and J. Stoyanovich, \"Enabling Privacy in Provenance-Aware Workflow Systems,\" CIDR, pp. 215--218, 2011.","journal-title":"CIDR"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314313.1314318"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0210-x"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376629"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2010.07.005"},{"key":"e_1_2_1_12_1","volume-title":"Scalable Access Controls for Lineage,\" First Workshop on Theory and Practice of Provenance Systems (TaPP)","author":"Rosenthal A.","year":"2009","unstructured":"A. Rosenthal , L. Seligman , A. Chapman , and B. Blaustein , \" Scalable Access Controls for Lineage,\" First Workshop on Theory and Practice of Provenance Systems (TaPP) , 2009 . A. Rosenthal, L. Seligman, A. Chapman, and B. Blaustein, \"Scalable Access Controls for Lineage,\" First Workshop on Theory and Practice of Provenance Systems (TaPP), 2009."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11890850_21"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04219-5_2"},{"key":"e_1_2_1_15_1","first-page":"153","article-title":"Preserving the Privacy of Sensitive Relationships in Graph Data","author":"Zheleva E.","year":"2007","unstructured":"E. Zheleva and L. Getoor , \" Preserving the Privacy of Sensitive Relationships in Graph Data ,\" PinKDD , pp. 153 -- 171 , 2007 . E. Zheleva and L. Getoor, \"Preserving the Privacy of Sensitive Relationships in Graph Data,\" PinKDD, pp. 153--171, 2007.","journal-title":"PinKDD"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497459"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2002974.2002979","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:44:48Z","timestamp":1672224288000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2002974.2002979"}},"subtitle":["protected and informative graphs"],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":16,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["10.14778\/2002974.2002979"],"URL":"https:\/\/doi.org\/10.14778\/2002974.2002979","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,5]]}}}