Complete information flow tracking from the gates up

ABSTRACT

For many mission-critical tasks, tight guarantees on the flow of information are desirable, for example, when handling important cryptographic keys or sensitive financial data. We present a novel architecture capable of tracking all information flow within the machine, including all explicit data transfers and all implicit flows (those subtly devious flows caused by not performing conditional operations). While the problem is impossible to solve in the general case, we have created a machine that avoids the general-purpose programmability that leads to this impossibility result, yet is still programmable enough to handle a variety of critical operations such as public-key encryption and authentication. Through the application of our novel gate-level information flow tracking method, we show how all flows of information can be precisely tracked. From this foundation, we then describe how a class of architectures can be constructed, from the gates up, to completely capture all information flows and we measure the impact of doing so on the hardware implementation, the ISA, and the programmer.

REFERENCES

• 1: James Newsome and Dawn Song. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In 12th Annual Network and Distributed System Security Symposium (NDSS 05), February 2005.
• 2: Onur Aciiçmez, Yet another MicroArchitectural Attack:: exploiting I-Cache, Proceedings of the 2007 ACM workshop on Computer security architecture, November 02-02, 2007, Fairfax, Virginia, USA [doi>10.1145/1314466.1314469]
• 3: Onur Aciic¸mez, Jean pierre Seifert, and Cetin Kaya Koc. Predicting secret keys via branch prediction. In The Cryptographers Track at the RSA Conference(CT-RSA), 2007.
• 4: Tiago Alves and Don Felton. TrustZone: Integrated Hardware and Software Security, July 2004. URL http://www.arm.com/
• 5: products/esd/trustzone_home.html.
• 6: David Brumley , James Newsome , Dawn Song , Hao Wang , Somesh Jha, Towards Automatic Generation of Vulnerability-Based Signatures, Proceedings of the 2006 IEEE Symposium on Security and Privacy, p.2-16, May 21-24, 2006 [doi>10.1109/SP.2006.41]
• 7: Haibo Chen , Xi Wu , Liwei Yuan , Binyu Zang , Pen-chung Yew , Frederic T. Chong, From Speculation to Security: Practical and Efficient Information Flow Tracking Using Speculative Hardware, Proceedings of the 35th International Symposium on Computer Architecture, p.401-412, June 21-25, 2008
• 8: James Clause , Wanchun Li , Alessandro Orso, Dytan: a generic dynamic taint analysis framework, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273490]
• 9: Manuel Costa , Jon Crowcroft , Miguel Castro , Antony Rowstron , Lidong Zhou , Lintao Zhang , Paul Barham, Vigilante: end-to-end containment of internet worms, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 10: Jedidiah R. Crandall , Frederic T. Chong, Minos: Control Data Attack Prevention Orthogonal to Memory Model, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.221-232, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.26]
• 11: Joan Daemen , Vincent Rijmen, The Design of Rijndael, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 12: Michael Dalton , Hari Kannan , Christos Kozyrakis, Raksha: a flexible information flow architecture for software security, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 13: Dorothy E. Denning , Peter J. Denning, Certification of programs for secure information flow, Communications of the ACM, v.20 n.7, p.504-513, July 1977 [doi>10.1145/359636.359712]
• 14: Karine Gandolfi , Christophe Mourtel , Francis Olivier, Electromagnetic Analysis: Concrete Results, Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems, p.251-261, May 14-16, 2001
• 15: Paul C. Kocher , Joshua Jaffe , Benjamin Jun, Differential Power Analysis, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.388-397, August 15-19, 1999
• 16: Paul C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.104-113, August 18-22, 1996
• 17: Lap Chung Lam , Tzi-cker Chiueh, A General Dynamic Information Flow Tracking Framework for Security Applications, Proceedings of the 22nd Annual Computer Security Applications Conference, p.463-472, December 11-15, 2006 [doi>10.1109/ACSAC.2006.6]
• 18: Ruby B. Lee , Peter C. S. Kwan , John P. McGregor , Jeffrey Dwoskin , Zhenghong Wang, Architecture for Protecting Critical Secrets in Microprocessors, Proceedings of the 32nd annual international symposium on Computer Architecture, p.2-13, June 04-08, 2005
• 19: Shashidhar Mysore , Bita Mazloom , Banit Agrawal , Timothy Sherwood, Understanding and visualizing full systems with data flow tomography, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 20: Dag Arne Osvik, Adi Shamir, and Eran Tromer. Cache attacks and countermeasures: the case of aes. In Topics in Cryptology -- CTRSA 2006, The Cryptographers Track at the RSA Conference 2006, pages 1--20. Springer-Verlag, 2006.
• 21: Feng Qin , Cheng Wang , Zhenmin Li , Ho-seop Kim , Yuanyuan Zhou , Youfeng Wu, LIFT: A Low-Overhead Practical Information Flow Tracking System for Detecting Security Attacks, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.135-148, December 09-13, 2006 [doi>10.1109/MICRO.2006.29]
• 22: Olatunji Ruwase , Phillip B. Gibbons , Todd C. Mowry , Vijaya Ramachandran , Shimin Chen , Michael Kozuch , Michael Ryan, Parallelizing dynamic information flow tracking, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378538]
• 23: K. Shimizu , H. P. Hofstee , J. S. Liberty, Cell broadband engine processor vault security architecture, IBM Journal of Research and Development, v.51 n.5, p.521-528, September 2007
• 24: G. Edward Suh , Jae W. Lee , David Zhang , Srinivas Devadas, Secure program execution via dynamic information flow tracking, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 25: G. Edward Suh , Charles W. O'Donnell , Srinivas Devadas, Aegis: A Single-Chip Secure Processor, IEEE Design & Test, v.24 n.6, p.570-580, November 2007 [doi>10.1109/MDT.2007.179]
• 26: Neil Vachharajani , Matthew J. Bridges , Jonathan Chang , Ram Rangan , Guilherme Ottoni , Jason A. Blome , George A. Reis , Manish Vachharajani , David I. August, RIFLE: An Architectural Framework for User-Centric Information-Flow Security, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.243-254, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.31]
• 27: Guru Venkataramani, Ioannis Doudalis, Yan Solihin, and Milos Prvulovic. Flexitaint: A programmable accelerator for dynamic taint propagation. In Fourteenth International Symposium on High Performance Computer Architecture (HPCA), 2008.
• 28: Philipp Vogt, Florian Nentwich, Nenad Jovanovic, Engin Kirda, Christopher Kruegel, and Giovanni Vigna. Cross-Site Scripting Prevention with Dynamic Data Tainting and Static Analysis. In Proceeding of the Network and Distributed System Security Symposium (NDSS), San Diego, CA, February 2007.
• 29: Bin Xin , Xiangyu Zhang, Efficient online detection of dynamic control dependence, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273489]
• 30: Wei Xu , Sandeep Bhatkar , R. Sekar, Taint-enhanced policy enforcement: a practical approach to defeat a wide range of attacks, Proceedings of the 15th conference on USENIX Security Symposium, July 31-August 04, 2006, Vancouver, B.C., Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Design, Security

Keywords:
gate level, information flow tracking, provably sound