{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T17:32:01Z","timestamp":1776447121501,"version":"3.51.2"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,9,9]],"date-time":"2017-09-09T00:00:00Z","timestamp":1504915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"crossref","award":["AFOSR-FA9550-12-1-0166"],"award-info":[{"award-number":["AFOSR-FA9550-12-1-0166"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1408880, CNS-1540216, CNS-1540217 and CNS-1657534"],"award-info":[{"award-number":["CNS-1408880, CNS-1540216, CNS-1540217 and CNS-1657534"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Assistant Secretary of Defense for Research 8 Engineering","award":["#FA8721-05-C-0002"],"award-info":[{"award-number":["#FA8721-05-C-0002"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Internet Technol."],"published-print":{"date-parts":[[2017,11,30]]},"abstract":"<jats:p>\n            Provenance is an increasingly important tool for understanding and even actively preventing system intrusion, but the excessive storage burden imposed by automatic provenance collection threatens to undermine its value in practice. This situation is made worse by the fact that the majority of this metadata is unlikely to be of interest to an administrator, instead describing system noise or other background activities that are not germane to the forensic investigation. To date, storing data provenance in perpetuity was a necessary concession in even the most advanced provenance tracking systems in order to ensure the completeness of the provenance record for future analyses. In this work, we overcome this obstacle by proposing a\n            <jats:italic>policy-based approach to provenance filtering<\/jats:italic>\n            , leveraging the confinement properties provided by Mandatory Access Control (MAC) systems in order to identify and isolate subdomains of system activity for which to collect provenance. We introduce the notion of\n            <jats:italic>minimal completeness<\/jats:italic>\n            for provenance graphs, and design and implement a system that provides this property by exclusively collecting provenance for the trusted computing base of a target application. In evaluation, we discover that, while the efficacy of our approach is domain dependent, storage costs can be reduced by as much as 89% in critical scenarios such as provenance tracking in cloud computing data centers. To the best of our knowledge, this is the first policy-based provenance monitor to appear in the literature.\n          <\/jats:p>","DOI":"10.1145\/3062180","type":"journal-article","created":{"date-parts":[[2017,9,11]],"date-time":"2017-09-11T12:12:26Z","timestamp":1505131946000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Taming the Costs of Trustworthy Provenance through Policy Reduction"],"prefix":"10.1145","volume":"17","author":[{"given":"Adam","family":"Bates","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dave (Jing)","family":"Tian","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grant","family":"Hernandez","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Moyer","sequence":"additional","affiliation":[{"name":"MIT Lincoln Laboratory, Lexington, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin R. B.","family":"Butler","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Trent","family":"Jaeger","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, University Park, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,9,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Principles of Security and Trust: First International Conference. Springer","author":"Acar Umut A.","year":"2012","unstructured":"Umut A. Acar , Amal Ahmed , James Cheney , and Roly Perera . 2012 . Principles of Security and Trust: First International Conference. Springer , Berlin, 410--429. Umut A. Acar, Amal Ahmed, James Cheney, and Roly Perera. 2012. Principles of Security and Trust: First International Conference. Springer, Berlin, 410--429."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14236\/ewic\/VOCS2008.13"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14722\/sent.2014.23002"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 7th International Workshop on Theory and Practice of Provenance (TaPP\u201915)","author":"Bates Adam","year":"2015","unstructured":"Adam Bates , Kevin R. B. Butler , and Thomas Moyer . 2015 . Take only what you need: Leveraging mandatory access control policy to reduce provenance storage costs . In Proceedings of the 7th International Workshop on Theory and Practice of Provenance (TaPP\u201915) . Adam Bates, Kevin R. B. Butler, and Thomas Moyer. 2015. Take only what you need: Leveraging mandatory access control policy to reduce provenance storage costs. In Proceedings of the 7th International Workshop on Theory and Practice of Provenance (TaPP\u201915)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2435349.2435389"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2831143.2831164"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11890850_18"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1943513.1943532"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/eScience.2013.39"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2011.26"},{"key":"e_1_2_1_12_1","unstructured":"World Wide Web Consortium and others. 2013. PROV-overview: An overview of the PROV family of documents. (2013).  World Wide Web Consortium and others. 2013. PROV-overview: An overview of the PROV family of documents. (2013)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2015.01.014"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 11th IEEE\/ACM International Conference on Grid Computing (GRID\u201910)","author":"Gehani A.","unstructured":"A. Gehani , B. Baig , S. Mahmood , D. Tariq , and F. Zaffar . 2010. Fine-grained tracking of grid infections . In Proceedings of the 11th IEEE\/ACM International Conference on Grid Computing (GRID\u201910) . A. Gehani, B. Baig, S. Mahmood, D. Tariq, and F. Zaffar. 2010. Fine-grained tracking of grid infections. In Proceedings of the 11th IEEE\/ACM International Conference on Grid Computing (GRID\u201910)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2442626.2442634"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 7th USENIX Conference on File and Storage Technologies (FAST\u201909)","author":"Hasan Ragib","year":"2009","unstructured":"Ragib Hasan , Radu Sion , and Marianne Winslett . 2009 . The case of the fake Picasso: Preventing history forgery with secure provenance . In Proceedings of the 7th USENIX Conference on File and Storage Technologies (FAST\u201909) . Ragib Hasan, Radu Sion, and Marianne Winslett. 2009. The case of the fake Picasso: Preventing history forgery with secure provenance. In Proceedings of the 7th USENIX Conference on File and Storage Technologies (FAST\u201909)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/142854.142859"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133058.1133063"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 20th ISOC Network and Distributed System Security Symposium (NDSS).","author":"Lee Kyu Hyung","year":"2013","unstructured":"Kyu Hyung Lee , Xiangyu Zhang , and Dongyan Xu . 2013 a. High accuracy attack provenance via binary-based execution partition . In Proceedings of the 20th ISOC Network and Distributed System Security Symposium (NDSS). Kyu Hyung Lee, Xiangyu Zhang, and Dongyan Xu. 2013a. High accuracy attack provenance via binary-based execution partition. In Proceedings of the 20th ISOC Network and Distributed System Security Symposium (NDSS)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516731"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2016.23350"},{"key":"e_1_2_1_22_1","volume-title":"4th Workshop on the Theory and Practice of Provenance (TaPP\u201912)","author":"Macko Peter","year":"2012","unstructured":"Peter Macko and Margo Seltzer . 2012 . A general-purpose provenance library . In 4th Workshop on the Theory and Practice of Provenance (TaPP\u201912) . Peter Macko and Margo Seltzer. 2012. A general-purpose provenance library. In 4th Workshop on the Theory and Practice of Provenance (TaPP\u201912)."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 2nd Conference on Theory and Practice of Provenance (TaPP\u201911)","author":"McDaniel P.","unstructured":"P. McDaniel , K. Butler , S. McLaughlin , R. Sion , E. Zadok , and M. Winslett . 2010. Towards a secure and efficient system for end-to-end provenance . In Proceedings of the 2nd Conference on Theory and Practice of Provenance (TaPP\u201911) . P. McDaniel, K. Butler, S. McLaughlin, R. Sion, E. Zadok, and M. Winslett. 2010. Towards a secure and efficient system for end-to-end provenance. In Proceedings of the 2nd Conference on Theory and Practice of Provenance (TaPP\u201911)."},{"key":"e_1_2_1_24_1","volume-title":"Mike Jewell, Amir Sezavar Keshavarz, Jamal A. Hussein, and Danius Michaelides.","author":"Moreau Luc","year":"2011","unstructured":"Luc Moreau , Trung Dong Huynh , Mike Jewell, Amir Sezavar Keshavarz, Jamal A. Hussein, and Danius Michaelides. 2011 . ProvToolbox. Retrieved from http:\/\/lucmoreau.github.io\/ProvToolbox\/. Luc Moreau, Trung Dong Huynh, Mike Jewell, Amir Sezavar Keshavarz, Jamal A. Hussein, and Danius Michaelides. 2011. ProvToolbox. Retrieved from http:\/\/lucmoreau.github.io\/ProvToolbox\/."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 2006 USENIX Annual Technical Conference.","author":"Muniswamy-Reddy Kiran-Kumar","year":"2006","unstructured":"Kiran-Kumar Muniswamy-Reddy , David A. Holland , Uri Braun , and Margo Seltzer . 2006 . Provenance-aware storage systems . In Proceedings of the 2006 USENIX Annual Technical Conference. Kiran-Kumar Muniswamy-Reddy, David A. Holland, Uri Braun, and Margo Seltzer. 2006. Provenance-aware storage systems. In Proceedings of the 2006 USENIX Annual Technical Conference."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855807.1855817"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2342875.2342879"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04219-5_5"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/PST.2012.6297930"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2420950.2420989"},{"key":"e_1_2_1_31_1","unstructured":"Chris Runge. 2004. SELinux: A new approach to secure systems. (July2004).  Chris Runge. 2004. SELinux: A new approach to secure systems. (July2004)."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 13th USENIX Security Symposium.","author":"Sailer Reiner","year":"2004","unstructured":"Reiner Sailer , Xiaolan Zhang , Trent Jaeger , and Leendert van Doorn . 2004 . Design and implementation of a TCG-based integrity measurement architecture . In Proceedings of the 13th USENIX Security Symposium. Reiner Sailer, Xiaolan Zhang, Trent Jaeger, and Leendert van Doorn. 2004. Design and implementation of a TCG-based integrity measurement architecture. In Proceedings of the 13th USENIX Security Symposium."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1982185.1982236"},{"key":"e_1_2_1_35_1","unstructured":"United States Computer Emergency Readiness Team. 2008. Vulnerability Summary for CVE-2008-1270. Retrieved from https:\/\/web.nvd.nist.gov\/view\/vuln\/detail?vulnId&equals;CVE-2008-1270.  United States Computer Emergency Readiness Team. 2008. Vulnerability Summary for CVE-2008-1270. Retrieved from https:\/\/web.nvd.nist.gov\/view\/vuln\/detail?vulnId&equals;CVE-2008-1270."},{"key":"e_1_2_1_36_1","unstructured":"United States Computer Emergency Readiness Team. 2015. Vulnerability Summary for CVE-2015-3306. Retrieved from https:\/\/web.nvd.nist.gov\/view\/vuln\/detail?vulnId&equals;CVE-2015-3306.  United States Computer Emergency Readiness Team. 2015. Vulnerability Summary for CVE-2015-3306. Retrieved from https:\/\/web.nvd.nist.gov\/view\/vuln\/detail?vulnId&equals;CVE-2015-3306."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2414456.2414500"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 11th USENIX Security Symposium.","author":"Wright Chris","year":"2002","unstructured":"Chris Wright , Crispin Cowan , Stephen Smalley , James Morris , and Greg Kroah-Hartman . 2002 . Linux security modules: General security support for the linux kernel . In Proceedings of the 11th USENIX Security Symposium. Chris Wright, Crispin Cowan, Stephen Smalley, James Morris, and Greg Kroah-Hartman. 2002. Linux security modules: General security support for the linux kernel. In Proceedings of the 11th USENIX Security Symposium."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398511"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2501986"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 3rd Workshop on the Theory and Practice of Provenance (TAPP\u201911)","author":"Xie Yulai","year":"2011","unstructured":"Yulai Xie , Kiran-Kumar Muniswamy-Reddy , Darrell D. E. Long , Ahmed Amer , Dan Feng , and Zhipeng Tan . 2011 . Compressing provenance graphs . In Proceedings of the 3rd Workshop on the Theory and Practice of Provenance (TAPP\u201911) . Yulai Xie, Kiran-Kumar Muniswamy-Reddy, Darrell D. E. Long, Ahmed Amer, Dan Feng, and Zhipeng Tan. 2011. Compressing provenance graphs. In Proceedings of the 3rd Workshop on the Theory and Practice of Provenance (TAPP\u201911)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/647253.720279"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043584"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807234"}],"container-title":["ACM Transactions on Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3062180","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3062180","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3062180","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:32Z","timestamp":1750217792000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3062180"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,9]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11,30]]}},"alternative-id":["10.1145\/3062180"],"URL":"https:\/\/doi.org\/10.1145\/3062180","relation":{},"ISSN":["1533-5399","1557-6051"],"issn-type":[{"value":"1533-5399","type":"print"},{"value":"1557-6051","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,9]]},"assertion":[{"value":"2016-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}