Heat-ray: combating identity snowball attacks using machinelearning, combinatorial optimization and attack graphs

ABSTRACT

As computers have become ever more interconnected, the complexity of security configuration has exploded. Management tools have not kept pace, and we show that this has made identity snowball attacks into a critical danger. Identity snowball attacks leverage the users logged in to a first compromised host to launch additional attacks with those users' privileges on other hosts. To combat such attacks, we present Heat-ray, a system that combines machine learning, combinatorial optimization and attack graphs to scalably manage security configuration. Through evaluation on an organization with several hundred thousand users and machines, we show that Heat-ray allows IT administrators to reduce by 96% the number of machines that can be used to launch a large-scale identity snowball attack.

REFERENCES

• 1: A. Agarwal, M. Charikar, K. Makarychev, and Y. Makarychev. O (√log n) Approximation Algorithms for Min UnCut, Min 2CNF Deletion, and Directed Cut Problems. In STOC, 2005.
• 2: P. Ammann, D. Wijesekera, and S. Kaushik. Scalable, Graph-Based Network Vulnerability Analysis. In ACSAC, 2002.
• 3: S. Arora, E. Hazan, and S. Kale. O(√log n) Approximation to SPARSEST CUT in Õ(n²) Time. In FOCS, 2004.
• 4: S. Arora, S. Rao, and U. Vazirani. Expander Flows, Geometric Embeddings and Graph Partitioning. In STOC, 2004.
• 5: S. Bhatkar, D. DuVarney, and R. Sekar. Address Obfuscation: An Efficient Approach to Combat a Broad Range of Memory Error Exploits. In USENIX Security, 2003.
• 6: O. Bousquet, U. von Luxburg, and G. Rätsch. Advanced Lectures on Machine Learning. Springer, 2003.
• 7: R. Butler, V. Welch, D. Engert, I. Foster, S. Tuecke, J. Volmer, and C. Kesselman. National-Scale Authentication Infrastructure. COMPUTER, 33(12):60--66, 2000.
• 8: S. Chen, J. Dunagan, C. Verbowski, and Y. Wang. A Black-Box Tracing Technique to Identify Causes of Least-Privilege Incompatibilities. In NDSS, 2005.
• 9: S. Chong, K. Vikram, and A. Myers. SIF: Enforcing Confidentiality and Integrity in Web Applications. In USENIX Security, 2007.
• 10: W. Chu and S.S. Keerthi. Support vector ordinal regression. Neural Computation, 19(3):792--815, 2007.
• 11: C. Cortes and V. Vapnik. Support-Vector Networks. Machine Learning, 20, 1995.
• 12: M. Costa, J. Crowcroft, M. Castro, A. Rowstron, L. Zhou, L. Zhang, and P. Barham. Vigilante: End-to-End Containment of Internet Worms. In SOSP, 2005.
• 13: C. Cowan, C. Pu, D. Maier, H. Hintony, J. Walpole, P. Bakke, S. Beattie, A. Grier, P. Wagle, and Q. Zhang. StackGuard: Automatic Adaptive Detection and Prevention of Buffer-Overflow Attacks. In USENIX Security, 1998.
• 14: E. Dijkstra. A Note on Two Problems in Connexion with Graph Theory. Numerische Mathematik, 1(269--271):1, 1959.
• 15: EC2. http://aws.amazon.com/ec2.
• 16: C. Ellison, B. Frantz, B. Lampson, R. Rivest, B. Thomas, and T. Ylonen. SPKI Certificate Theory, 1999.
• 17: Ethernet Address Resolution Protocol. http://tools.ietf.org/html/rfc826.
• 18: Forefront. http://www.microsoft.com/forefront.
• 19: C. Grier, S. Tang, and S. King. Secure Web Browsing with the OP Web Browser. In IEEE Security and Privacy, 2008.
• 20: R. Herbrich, T. Graepel, and K. Obermayer. Support Vector Learning for Ordinal Regression. In International Conference on Artificial Neural Networks, 1999.
• 21: Jain, A. and Flynn, P. and Ross, A. Eds. Handbook of Biometrics. Springer, 2007.
• 22: James C. Spall. Introduction to Stochastic Search and Optimization. Wiley, 2003.
• 23: J. Johansson and S. Riley. Protect Your Windows Network: From Perimeter to Data. Addison-Wesley, 2005.
• 24: A. Joshi, S. King, G. Dunlap, and P. Chen. Detecting Past and Present Intrusions through Vulnerability-specific Predicates. In SOSP, 2005.
• 25: M. Kaminsky, G. Savvides, D. Mazieres, and M. Kaashoek. Decentralized User Authentication in a Global File System. In SOSP, 2003.
• 26: S. King and P. Chen. Backtracking Intrusions. ACM Transactions on Computer Systems (TOCS), 23(1):51--76, 2005.
• 27: P. Klein, S. Plotkin, C. Stein, and E. Tardos. Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts. In SIAM JOURNAL ON COMPUTING, 1994.
• 28: M. Krohn, M. Brodsky, M. Kaashoek, and R. Morris. Information Flow Control for Standard OS Abstractions. In SOSP, 2007.
• 29: B. Lampson, M. Abadi, M. Burrows, and E. Wobber. Authentication in Distributed Systems: Theory and Practice. In ACM Transactions on Computer Systems (TOCS), 1992.
• 30: Live ID. http://winliveid.spaces.live.com/.
• 31: M. Luby and N. Nisan. A Parallel Approximation Algorithm for Positive Linear Programming. In STOC, 1993.
• 32: D. Moore, V. Paxson, S. Savage, C. Shannon, S. Staniford, and N. Weaver. Inside the Slammer Worm. In IEEE Security and Privacy, 2003.
• 33: MT. Hajiaghayi and H. Räcke. An O(√n)-approximation algorithm for directed sparsest cut. In Information Processing Letters, 2006.
• 34: T. Munzner. Interactive Visualization of Large Graphs and Networks. PhD thesis, Stanford University, 2000.
• 35: P. Naldurg, S. Schwoon, S. Rajamani, and J. Lambert. NETRA: Seeing Through Access Control. In ACM Workshop on Formal Methods in Security, 2006.
• 36: J. Newsome and D. Song. Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Commodity Software. In NDSS, 2005.
• 37: S. Noel and S. Jajodia. Managing Attack Graph Complexity Through Visual Hierarchical Aggregation. In ACM Workshop on Visualization and Data Mining for Computer Security, 2004.
• 38: X. Ou, S. Govindavajhala, and A. Appel. MulVAL: A Logic-based Network Security Analyzer. In USENIX Security, 2005.
• 39: N. Provos, D. McNamee, P. Mavrommatis, K. Wang, and N. Modadugu. The Ghost In The Browser: Analysis of Web-based Malware. In HotBots, 2007.
• 40: M. Rajab, J. Zarfoss, F. Monrose, and A. Terzis. A Multifaceted Approach to Understanding the Botnet Phenomenon. In IMC, 2006.
• 41: W. Rankl and W. Effing. Smart Card Handbook. Wiley, 2004.
• 42: R. Rivest and B. Lampson. SDSI -- A Simple Distributed Security Infrastructure. Crypto, 1996.
• 43: S. Schechter, J. Jung, W. Stockwell, and C. McLain. Inoculating SSH Against Address Harvesting. In NDSS, 2006.
• 44: E. Schultz. A framework for understanding and predicting insider attacks. In Conference on Computers and Security (CompSec), 2002.
• 45: Secure4Privilege White Paper on Unix Root Accounts. http://www.s4software.com/PDF/s4privilege_whitepaper.pdf.
• 46: Security Assertion Markup Language. http://saml.xml.org.
• 47: F. Shahrokhi and D. Matula. The Maximum Concurrent Flow Problem. In JACM, 1990.
• 48: O. Sheyner, J. Haines, S. Jha, R. Lippmann, and J. Wing. Automated generation and analysis of attack graphs. In IEEE Security and Privacy, 2002.
• 49: A. Singer. Tempting Fate. USENIX login, 30(1):27--30, 2005.
• 50: E. Spafford. The Internet Worm Program: An Analysis. ACM SIGCOMM Computer Communication Review, 19(1):17--57, 1989.
• 51: J. Steiner, C. Neuman, and J. Schiller. Kerberos: An Authentication Service for Open Network Systems. In USENIX, 1988.
• 52: L. Swiler, C. Phillips, D. Ellis, and S. Chakerian. Computer-Attack Graph Generation Tool. In DARPA Information Survivability Conference and Expo (DISCEX), 2001.
• 53: Symark White Paper on Unix Root Accounts. http://www.symark.com/downloads/whitepapers/Symark_Privileged_Access_Control.html.
• 54: System Center Operations Manager. http://www.microsoft.com/systemcenter/operationsmanager.
• 55: User-Workstations Attribute. http://msdn.microsoft.com/en-us/library/ms680868(VS.85).aspx.
• 56: G. Wahba. Support Vector Machines, Reproducing Kernel Hilbert Spaces, and Randomized GACV. MIT Press, 1999.
• 57: I. Winkler and B. Dealy. Information Security Technology?... Don't Rely on It: A Case Study in Social Engineering. In USENIX Security, 1995.
• 58: T. Wobber, A. Yumerefendi, M. Abadi, A. Birrell, and D. Simon. Authorizing Applications in Singularity. In EuroSys, 2007.
• 59: N. Young. Sequential and Parallel Algorithms for Mixed Packing and Covering. In FOCS, 2001.
• 60: N. Zeldovich, S. Boyd-Wickizer, E. Kohler, and D. Mazieres. Making Information Flow Explicit in HiStar. In OSDI, 2006.
• 61: C. Zou, W. Gong, and D. Towsley. Code Red Worm Propagation Modeling and Analysis. In ACM CCS, 2002.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Access controls

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Authentication

General Terms:
Management, Security

Keywords:
access control, attack graph, authentication, combinatorial optimization, identity snowball, machine learning, sparsest cut, support vector machine