Runtime Analysis of Whole-System Provenance

ABSTRACT

Identifying the root cause and impact of a system intrusion remains a foundational challenge in computer security. Digital provenance provides a detailed history of the flow of information within a computing system, connecting suspicious events to their root causes. Although existing provenance-based auditing techniques provide value in forensic analysis, they assume that such analysis takes place only retrospectively. Such post-hoc analysis is insufficient for realtime security applications; moreover, even for forensic tasks, prior provenance collection systems exhibited poor performance and scalability, jeopardizing the timeliness of query responses. We present CamQuery, which provides inline, realtime provenance analysis, making it suitable for implementing security applications. CamQuery is a Linux Security Module that offers support for both userspace and in-kernel execution of analysis applications. We demonstrate the applicability of CamQuery to a variety of runtime security applications including data loss prevention, intrusion detection, and regulatory compliance. In evaluation, we demonstrate that CamQuery reduces the latency of realtime query mechanisms, while imposing minimal overheads on system execution. CamQuery thus enables the further deployment of provenance-based technologies to address central challenges in computer security.

References

1. Rocio Aldeco-Perez and Luc Moreau. 2009. Information Accountability supported by a Provenance-based Compliance Framework. (December. 2009). http://eprints.soton.ac.uk/268305/ Event Dates: Monday 7th -- Wednesday 9th December 2009.
2. Roc'ıo Aldeco-Pérez and Luc Moreau. 2010. Securing provenance-based audits. In International Provenance and Annotation Workshop. Springer, 148--164.
3. J. P. Anderson. 1972. Computer Security Technology Planning Study. Technical Report ESD-TR-73--51. ESD/AFSC, Hanscom AFB, Bedford, MA.
4. James P Anderson. 1972. Computer Security Technology Planning Study. Volume 2. Technical Report. Anderson (James P) and Co Fort Washington PA.
5. Nikilesh Balakrishnan, Lucian Carata, Thomas Bytheway, Ripduman Sohan, and Andy Hopper. 2017. Non-repudiable disk I/O in untrusted kernels. In Asia-Pacific Workshop on Systems. 24:1--24:6.
6. Tim Bass. 2000. Intrusion Detection Systems and Multisensor Data Fusion. Commun. ACM Vol. 43, 4 (2000), 99--105.
7. Adam Bates, KR Butler, and Thomas Moyer. 2015 a. Take only what you need: leveraging mandatory access control policy to reduce provenance storage costs. In Workshop on Theory and Practice of Provenance (TaPP'15). USENIX, 7--7.
8. Adam Bates, Ben Mood, Masoud Valafar, and Kevin Butler. 2013. Towards Secure Provenance-based Access Control in Cloud Environments Proceedings of the Third ACM Conference on Data and Application Security and Privacy (CODASPY '13). ACM, New York, NY, USA, 277--284.
9. Adam Bates, Ben Mood, Masoud Valafar, and Kevin Butler. 2013. Towards secure provenance-based access control in cloud environments Conference on Data and Application Security and Privacy. ACM, 277--284.
10. Adam Bates, Dave Jing Tian, Grant Hernandez, Thomas Moyer, Kevin RB Butler, and Trent Jaeger. 2017. Taming the Costs of Trustworthy Provenance through Policy Reduction. Transactions on Internet Technology Vol. 17, 4 (2017), 34.
11. Adam M Bates, Dave Tian, Kevin RB Butler, and Thomas Moyer. 2015. Trustworthy Whole-System Provenance for the Linux Kernel USENIX Security. 319--334.
12. Khalid Belhajjame, Reza B'Far, James Cheney, Sam Coppens, Stephen Cresswell, Yolanda Gil, Paul Groth, Graham Klyne, Timothy Lebo, Jim McCusker, Simon Miles, James Myers, Satya Sahoo, Luc Moreau, and Paolo ηl Missier. 2013. Prov-DM: The PROV Data Model. Technical Report. World Wide Web Consortium (W3C). https://www.w3.org/TR/prov-dm/
13. Donald J Berndt and James Clifford. 1994. Using dynamic time warping to find patterns in time series KDD workshop, Vol. Vol. 10. Seattle, WA, 359--370.
14. Uri Braun, Simson Garfinkel, David A Holland, Kiran-Kumar Muniswamy-Reddy, and Margo I Seltzer. 2006. Issues in automatic provenance collection. In Provenance and annotation of data. Springer, 171--183.
15. David FC Brewer and Michael J Nash. 1989. The Chinese Wall security policy. In Symposium on Security and Privacy. IEEE, 206--214.
16. Sheung Chi Chan, Ashish Gehani, James Cheney, Ripduman Sohan, and Hassaan Irshad. 2017. Expressiveness Benchmarking for System-Level Provenance Workshop on the Theory and Practice of Provenance (TaPP'17). USENIX.
17. Varun Chandola, Arindam Banerjee, and Vipin Kumar. 2009. Anomaly detection: A survey. ACM computing surveys (CSUR) Vol. 41, 3 (2009), 15.
18. Winnie Cheng, Qin Zhao, Bei Yu, and Scott Hiroshige. 2006. Tainttrace: Efficient flow tracing with dynamic binary rewriting Computers and Communications, 2006. ISCC'06. Proceedings. 11th IEEE Symposium on. IEEE, 749--754.
19. Christian Collberg and Todd A Proebsting. 2016. Repeatability in computer systems research. Commun. ACM Vol. 59, 3 (2016), 62--69.
20. Antony Edwards, Trent Jaeger, and Xiaolan Zhang. 2002. Runtime verification of authorization hook placement for the Linux security modules framework. In Conference on Computer and Communications Security (CCS'02). ACM, 225--234.
21. E Allen Emerson and Joseph Y Halpern. 1982. Decision procedures and expressiveness in the temporal logic of branching time Symposium on Theory of Computing. ACM, 169--180.
22. William Enck, Peter Gilbert, Seungyeop Han, Vasant Tendulkar, Byung-Gon Chun, Landon P Cox, Jaeyeon Jung, Patrick McDaniel, and Anmol N Sheth. 2014. TaintDroid: an information-flow tracking system for realtime privacy monitoring on smartphones. ACM Transactions on Computer Systems (TOCS) Vol. 32, 2 (2014), 5.
23. Birhanu Eshete, Rigel Gjomemo, Md Nahid Hossain, Sadegh Momeni, R Sekar, Scott Stoller, VN Venkatakrishnan, and Junao Wang. 2016. Attack Analysis Results for Adversarial Engagement 1 of the DARPA Transparent Computing Program. arXiv preprint arXiv:1610.06936 (2016).
24. Vinod Ganapathy, Trent Jaeger, and Somesh Jha. 2005. Automatic placement of authorization hooks in the Linux security modules framework Conference on Computer and Communications Security (CCS'05). ACM, 330--339.
25. Peng Gao, Xusheng Xiao, Din Li, Zhichun Li, Kangkook Jee, Zhenyu Wu, Chung Whan Kim, Sanjeev R. Kulkarni, and Prateek Mittal. 2018. SAQL: A Stream-based Query System for Real-Time Abnormal System Behavior Detection Proceedings of the 27th USENIX Security Symposium (Security'18). Baltimore, MD, USA.
26. Ashish Gehani and Dawood Tariq. 2012. SPADE: support for provenance auditing in distributed environments International Middleware Conference. ACM/IFIP/USENIX, 101--120.
27. Laurent Georget, Mathieu Jaume, Guillaume Piolle, Frédéric Tronel, and Valérie Viet Triem Tong. 2017. Information Flow Tracking for Linux Handling Concurrent System Calls and Shared Memory. In International Conference on Software Engineering and Formal Methods. Springer, 1--16.
28. Laurent Georget, Mathieu Jaume, Frédéric Tronel, Guillaume Piolle, and Valérie Viet Triem Tong. 2017. Verifying the reliability of operating system-level information flow control systems in Linux. In International Workshop on Formal Methods in Software Engineering (FormaliSE'17). IEEE/ACM, 10--16.
29. Dawid Golunski. 2016. CVE-2016--6663: MySQL / MariaDB / PerconaDB 5.5.x/5.6.x/5.7.x - 'mysql' System User Privilege Escalation / Race Condition. https://www.exploit-db.com/exploits/40678/
30. Dawid Golunski. 2016. CVE-2016--6664: MySQL / MariaDB / PerconaDB 5.5.x/5.6.x/5.7.x - 'root' System User Privilege Escalation. https://www.exploit-db.com/exploits/40679/
31. Dawid Golunski. 2016 c. CVE-2016--9566: Nagios < 4.2.4 - Privilege Escalation. https://www.exploit-db.com/exploits/40921/
32. Joseph E Gonzalez, Reynold S Xin, Ankur Dave, Daniel Crankshaw, Michael J Franklin, and Ion Stoica. 2014. GraphX: Graph Processing in a Distributed Dataflow Framework Conference on Operating Systems Design and Implementation (OSDI'14), Vol. Vol. 14. 599--613.
33. Guofei Gu, Alvaro A. Cárdenas, and Wenke Lee. 2008. Principled Reasoning and Practical Applications of Alert Fusion in Intrusion Detection Systems. In Symposium on Information, Computer and Communications Security (ASIACCS'17). ACM, 136--147.
34. Michael Austin Halcrow. 2005. eCryptfs: An enterprise-class encrypted filesystem for Linux Proceedings of the 2005 Linux Symposium, Vol. Vol. 1. 201--218.
35. Xueyuan Han, Thomas Pasquier, Tanvi Ranjan, Mark Goldstein, and Margo Seltzer. 2017. FRAPpuccino: Fault-detection through Runtime Analysis of Provenance Workshop on Hot Topics in Cloud Computing (HotCloud '17). USENIX.
36. Xueyuan Han, Thomas Pasquier, and Margo Seltzer. 2018. Provenance-based Intrusion Detection: Opportunities and Challenges Workshop on Theory and Practice of Provenance (TaPP'18). ACM.
37. Ragib Hasan, Radu Sion, and Marianne Winslett. 2009. The Case of the Fake Picasso: Preventing History Forgery with Secure Provenance Conference on File and Storage Technologies (FAST 09). USENIX.
38. Wajih Ul Hassan, Mark Lemay, Nuraini Aguse, Adam Bates, and Thomas Moyer. 2018. Towards Scalable Cluster Auditing through Grammatical Inference over Provenance Graphs. In Network and Distributed Systems Security Symposium. Internet Society.
39. Simon Hawkins, Hongxing He, Graham Williams, and Rohan Baxter. 2002. Outlier detection using replicator neural networks International Conference on Data Warehousing and Knowledge Discovery. Springer, 170--180.
40. Kai Hwang and Deyi Li. 2010. Trusted cloud computing with secure resources and data coloring. Internet Computing, IEEE Vol. 14, 5 (2010), 14--22.
41. Dino Ienco, Ruggero G Pensa, and Rosa Meo. 2017. A semisupervised approach to the detection and characterization of outliers in categorical data. IEEE Transactions on Neural Networks and Learning Systems Vol. 28, 5 (2017), 1017--1029.
42. Matteo Interlandi, Kshitij Shah, Sai Deep Tetali, Muhammad Ali Gulzar, Seunghyun Yoo, Miryung Kim, Todd Millstein, and Tyson Condie. 2015. Titian: Data provenance support in Spark. Proceedings of the VLDB Endowment Vol. 9, 3 (2015), 216--227.
43. Trent Jaeger, Antony Edwards, and Xiaolan Zhang. 2004. Consistency analysis of authorization hook placement in the Linux security modules framework. ACM Transactions on Information and System Security (TISSEC) Vol. 7, 2 (2004), 175--205.
44. Xuxian Jiang, A. Walters, Dongyan Xu, E.H. Spafford, F. Buchholz, and Yi-Min Wang. 2006. Provenance-Aware Tracing of Worm Break-in and Contaminations: A Process Coloring Approach. In International Conference on Distributed Computing Systems (ICDCS'06). IEEE, 38--38.
45. Samuel T King and Peter M Chen. 2003. Backtracking intrusions. ACM SIGOPS Operating Systems Review Vol. 37, 5 (2003), 223--236.
46. Ryan KL Ko, Markus Kirchberg, and Bu Sung Lee. 2011. From system-centric to data-centric logging-accountability, trust & security in cloud computing. In Defense Science Research Conference and Expo (DSR), 2011. IEEE, 1--4.
47. Maxwell Krohn, Alexander Yip, Micah Brodsky, Natan Cliffer, M Frans Kaashoek, Eddie Kohler, and Robert Morris. 2007. Information flow control for standard OS abstractions ACM SIGOPS Operating Systems Review, Vol. Vol. 41. ACM, 321--334.
48. George Kurtz. 2010. Operation Aurora Hit Google, Others. Available at http://securityinnovator.com/index.php?articleID=42948§ionID=25
49. Aapo Kyrola, Guy E Blelloch, Carlos Guestrin, et almbox.. 2012. GraphChi: Large-Scale Graph Computation on Just a PC Conference on Operating Systems Design and Implementation (OSDI'12), Vol. Vol. 12. 31--46.
50. Michael Larabel and Matthew Tippett. {n. d.}. Phoronix test suite. http://www. phoronix-test-suite. com
51. Kyu Hyung Lee, Xiangyu Zhang, and Dongyan Xu. 2013 a. High Accuracy Attack Provenance via Binary-based Execution Partition Proceedings of NDSS '13.
52. Kyu Hyung Lee, Xiangyu Zhang, and Dongyan Xu. 2013 b. LogGC: Garbage Collecting Audit Log. In Conference on Computer and Communications Security (CCS'13). ACM, 1005--1016.
53. Yushan Liu, Mu Zhang, Ding Li, Kangkook Jee, Zhichun Li, Zhenyu Wu, Junghwan Rhee, and Prateek Mittal. 2018. Towards a Timely Causality Analysisfor Enterprise Security Proceedings of the 25th ISOC Network and Distributed System Security Symposium (NDSS'18). San Diego, CA, USA.
54. John Lyle, Andrew P Martin, et almbox.. 2010. Trusted Computing and Provenance: Better Together. In Workshop on Theory and Practice of Provenance (TaPP'10). USENIX.
55. Shiqing Ma, Kyu Hyung Lee, Chung Hwan Kim, Junghwan Rhee, Xiangyu Zhang, and Dongyan Xu. 2015. Accurate, Low Cost and Instrumentation-Free Security Audit Logging for Windows Annual Computer Security Applications Conference. ACM, 401--410.
56. Shiqing Ma, Juan Zhai, Fei Wang, Kyu Hyung Lee, Xiangyu Zhang, and Dongyan Xu. 2017. MPI: Multiple Perspective Attack Investigation with Semantic Aware Execution Partitioning. In USENIX Security Symposium.
57. Shiqing Ma, Xiangyu Zhang, and Dongyan Xu. 2016. ProTracer: Towards Practical Provenance Tracing by Alternating Between Logging and Tainting. In Network and Distributed System Security Symposium (NDSS'16). Internet Society.
58. Jonathan Mace, Ryan Roelke, and Rodrigo Fonseca. 2015. Pivot tracing: Dynamic causal monitoring for distributed systems Symposium on Operating Systems Principles (SOSP'15). ACM, 378--393.
59. Larry W McVoy, Carl Staelin, et almbox.. 1996. lmbench: Portable Tools for Performance Analysis. In USENIX Annual Technical Conference (ATC'96). 279--294.
60. Luc Moreau and Mufajjul Ali. 2014. A provenance-based policy control framework for cloud services. (May. 2014). http://eprints.soton.ac.uk/364997/
61. James Morris, Stephen Smalley, and Greg Kroah-Hartman. 2002. Linux security modules: General security support for the Linux kernel USENIX Security Symposium.
62. Thomas Moyer and Vijay Gadepally. 2016. High-throughput ingest of data provenance records into Accumulo High Performance Extreme Computing Conference (HPEC'16). IEEE, 1--6.
63. Kiran-Kumar Muniswamy-Reddy, Uri Braun, David A Holland, Peter Macko, Diana L MacLean, Daniel W Margo, Margo I Seltzer, and Robin Smogor. 2009. Layering in Provenance Systems. In USENIX Annual Technical Conference (ATC'09).
64. Kiran-Kumar Muniswamy-Reddy, David A Holland, Uri Braun, and Margo I Seltzer. 2006. Provenance-aware storage systems. In USENIX Annual Technical Conference (ATC'06). 43--56.
65. Divya Muthukumaran, Dan O'Keeffe, Christian Priebe, David Eyers, Brian Shand, and Peter Pietzuch. 2015. FlowWatcher: Defending against Data Disclosure Vulnerabilities in Web Applications Conference on Computer and Communications Security (CCS'15). ACM, 603--615.
66. Andrew C Myers. 1999. JFlow: Practical mostly-static information flow control Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM, 228--241.
67. Adwait Nadkarni, Benjamin Andow, William Enck, and Somesh Jha. 2016. Practical DIFC enforcement on Android. In USENIX Security Symposium. 1119--1136.
68. Dang Nguyen, Jaehong Park, and Ravi Sandhu. 2013. A provenance-based access control model for dynamic separation of duties International Conference on Privacy, Security and Trust (PST'13). IEEE, 247--256.
69. Jaehong Park, Dang Nguyen, and Ravi Sandhu. 2012. A provenance-based access control model. In International Conference on Privacy, Security and Trust (PST'13). IEEE, 137--144.
70. Thomas Pasquier and David Eyers. 2016. Information Flow Audit for Transparency and Compliance in the Handling of Personal Data. In Workshop on Legal and Technical Issues in Cloud Computing and the Internet of Things (CLAW'16). IEEE.
71. Thomas Pasquier, Xueyuan Han, Mark Goldstein, Thomas Moyer, David Eyers, Margo Seltzer, and Jean Bacon. 2017 a. Practical Whole-System Provenance Capture. In Symposium on Cloud Computing (SoCCtextquoteright17). ACM, ACM.
72. Thomas Pasquier, Jatinder Singh, David Eyers, and Jean Bacon. 2015. CamFlow: Managed Data-Sharing for Cloud Services. IEEE Transactions on Cloud Computing (2015).
73. Thomas Pasquier, Jatinder Singh, Julia Powles, David Eyers, Margo Seltzer, and Jean Bacon. 2017 b. Data provenance to audit compliance with privacy policy in the Internet of Things. Springer Personal and Ubiquitous Computing (2017).
74. Devin J Pohly, Stephen McLaughlin, Patrick McDaniel, and Kevin Butler. 2012. Hi-Fi: collecting high-fidelity whole-system provenance Annual Computer Security Applications Conference. ACM, 259--268.
75. Phillip A. Porras, Martin W. Fong, and Alfonso Valdes. 2002. A Mission-Impact-Based Approach to INFOSEC Alarm Correlation International Symposium on Recent Advances in Intrusion Detection. Springer, 95--114.
76. Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. 2017. struc2vec: Learning Node Representations from Structural Identity International Conference on Knowledge Discovery and Data Mining. ACM, 385--394.
77. Indrajit Roy, Donald E Porter, Michael D Bond, Kathryn S McKinley, and Emmett Witchel. 2009. Laminar: Practical fine-grained decentralized information flow control Conference on Programming Language Design and Implementation, Vol. Vol. 44. ACM.
78. Alireza Sadighian, José M. Fernandez, Antoine Lemay, and Saman T Zargar. {n. d.}. ONTIDS: A Highly Flexible Context-Aware and Ontology-Based Alert Correlation Framework. In International Symposium on Foundations and Practice of Security. Springer, 161--177.
79. Reiner Sailer, Xiaolan Zhang, Trent Jaeger, and Leendert Van Doorn. 2004. Design and Implementation of a TCG-based Integrity Measurement Architecture USENIX Security Symposium, Vol. Vol. 13. 223--238.
80. Stephen Smalley, Chris Vance, and Wayne Salamon. 2001. Implementing SELinux as a Linux security module. NAI Labs Report Vol. 1, 43 (2001), 139.
81. Wai Kit Sze and R Sekar. 2015. Provenance-based Integrity Protection for Windows. In Annual Computer Security Applications Conference. ACM, 211--220.
82. Dawood Tariq, Maisem Ali, and Ashish Gehani. 2012. Towards Automated Collection of Application-Level Data Provenance. Workshop on Theory and Practice of Provenance (TaPP'12).
83. F. Valeur, G. Vigna, C. Kruegel, and R. A. Kemmerer. 2004. Comprehensive approach to intrusion detection alert correlation. IEEE Transactions on Dependable and Secure Computing Vol. 1, 3 (2004), 146--169.
84. Frank Wang, Yuna Joung, and James Mickens. 2017. Cobweb: Practical Remote Attestation Using Contextual Graphs Workshop on System Software for Trusted Execution (SysTEX'17). ACM.
85. Yulai Xie, Kiran-Kumar Muniswamy-Reddy, Dan Feng, Yan Li, and Darrell DE Long. 2013. Evaluation of a hybrid approach for efficient provenance storage. ACM Transactions on Storage (TOS) Vol. 9, 4 (2013), 14.
86. Wei Xu, Ling Huang, Armando Fox, David Patterson, and Michael I Jordan. 2009. Detecting large-scale system problems by mining console logs Symposium on Operating Systems Principles (SOSP'09). ACM, 117--132.
87. Ting-Fang Yen, Alina Oprea, Kaan Onarlioglu, Todd Leetham, William Robertson, Ari Juels, and Engin Kirda. 2013. Beehive: Large-scale Log Analysis for Detecting Suspicious Activity in Enterprise Networks. In Annual Computer Security Applications Conference. ACM, 199--208.
88. Ding Yuan, Jing Zheng, Soyeon Park, Yuanyuan Zhou, and Stefan Savage. 2012. Improving software diagnosability via log enhancement. ACM Transactions on Computer Systems (TOCS) Vol. 30, 1 (2012), 4.
89. Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2012. Resilient Distributed Datasets: A Fault-tolerant Abstraction for In-memory Cluster Computing. In Conference on Networked Systems Design and Implementation (NSDI'12). USENIX.
90. Nickolai Zeldovich, Silas Boyd-Wickizer, Eddie Kohler, and David Mazières. 2006. Making information flow explicit in HiStar. In Symposium on Operating Systems Design and Implementation (OSDI'06). USENIX Association, 263--278.
91. Xiaolan Zhang, Antony Edwards, and Trent Jaeger. 2002. Using CQUAL for Static Analysis of Authorization Hook Placement Proceedings of the 11th USENIX Security Symposium.
92. Xu Zhao, Kirk Rodrigues, Yu Luo, Ding Yuan, and Michael Stumm. 2016. Non-Intrusive Performance Profiling for Entire Software Stacks Based on the Flow Reconstruction Principle. In Symposium on Operating Systems Design and Implementation (OSDI'16). USENIX, 603--618.
93. Xu Zhao, Yongle Zhang, David Lion, Muhammad Faizan Ullah, Yu Luo, Ding Yuan, and Michael Stumm. 2014. Lprof: A Non-intrusive Request Flow Profiler for Distributed Systems Conference on Operating Systems Design and Implementation (OSDI'14). USENIX, Berkeley, CA, USA, 629--644.
94. Wenchao Zhou, Qiong Fei, Arjun Narayan, Andreas Haeberlen, Boon Thau Loo, and Micah Sherr. 2011. Secure network provenance. In Symposium on Operating Systems Principles (SOSP'11). ACM, 295--310.

Index Terms

• Security and privacy

  • Intrusion/anomaly detection and malware mitigation

    • Intrusion detection systems

  • Systems security

    • Information flow control

    • Operating systems security