Parallelizing dynamic information flow tracking

ABSTRACT

Dynamic information flow tracking (DIFT) is an important tool for detecting common security attacks and memory bugs. A DIFT tool tracks the flow of information through a monitored program's registers and memory locations as the program executes, detecting and containing/fixing problems on-the-fly. Unfortunately, sequential DIFT tools are quite slow, and DIFT is quite challenging to parallelize. In this paper, we present a new approach to parallelizing DIFT-like functionality. Extending our recent work on accelerating sequential DIFT, we consider a variant of DIFT that tracks the information flow only through unary operations relaxed DIFT, and yet makes sense for detecting security attacks and memory bugs. We present a parallel algorithm for relaxed DIFT, based on symbolic inheritance tracking, which achieves linear speed-up asymptotically. Moreover, we describe techniques for reducing the constant factors, so that speed-ups can be obtained even with just a few processors. We implemented the algorithm in the context of a Log-Based Architectures (LBA) system, which provides hardware support for logging a program trace and delivering it to other (monitoring) processors. Our simulation results on SPEC benchmarks and a video player show that our parallel relaxed DIFT reduces the overhead to as low as 1.2X using 9 monitoring cores on a 16-core chip multiprocessor.

REFERENCES

• 1: Derek L. Bruening , Saman Amarasinghe, Efficient, transparent, and comprehensive runtime code manipulation, Massachusetts Institute of Technology, Cambridge, MA, 2004
• 2: William R. Bush , Jonathan D. Pincus , David J. Sielaff, A static analyzer for finding dynamic programming errors, Software—Practice & Experience, v.30 n.7, p.775-802, June 2000 [doi>10.1002/(SICI)1097-024X(200006)30:7<775::AID-SPE309>3.0.CO;2-H]
• 3: Shimin Chen , Babak Falsafi , Phillip B. Gibbons , Michael Kozuch , Todd C. Mowry , Radu Teodorescu , Anastassia Ailamaki , Limor Fix , Gregory R. Ganger , Bin Lin , Steven W. Schlosser, Log-based architectures for general-purpose monitoring of deployed code, Proceedings of the 1st workshop on Architectural and system support for improving software dependability, p.63-65, October 21-21, 2006, San Jose, California [doi>10.1145/1181309.1181319]
• 4: Shimin Chen , Michael Kozuch , Theodoros Strigkos , Babak Falsafi , Phillip B. Gibbons , Todd C. Mowry , Vijaya Ramachandran , Olatunji Ruwase , Michael Ryan , Evangelos Vlachos, Flexible Hardware Acceleration for Instruction-Grain Program Monitoring, ACM SIGARCH Computer Architecture News, v.36 n.3, p.377-388, June 2008
• 5: Marc L. Corliss , E. Christopher Lewis , Amir Roth, DISE: a programmable macro engine for customizing applications, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 6: 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
• 7: Crispin Cowan , Calton Pu , Dave Maier , Heather Hintony , Jonathan Walpole , Peat Bakke , Steve Beattie , Aaron Grier , Perry Wagle , Qian Zhang, StackGuard: automatic adaptive detection and prevention of buffer-overflow attacks, Proceedings of the 7th conference on USENIX Security Symposium, p.5-5, January 26-29, 1998, San Antonio, Texas
• 8: 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]
• 9: 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
• 10: Dawson Engler , Benjamin Chelf , Andy Chou , Seth Hallem, Checking system rules using system-specific, programmer-written compiler extensions, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.1-1, October 22-25, 2000, San Diego, California
• 11: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically Discovering Likely Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering, v.27 n.2, p.99-123, February 2001 [doi>10.1109/32.908957]
• 12: Cormac Flanagan , K. Rustan M. Leino , Mark Lillibridge , Greg Nelson , James B. Saxe , Raymie Stata, Extended static checking for Java, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 13: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 14: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 15: Satish Narayanasamy , Gilles Pokam , Brad Calder, BugNet: Continuously Recording Program Execution for Deterministic Replay Debugging, Proceedings of the 32nd annual international symposium on Computer Architecture, p.284-295, June 04-08, 2005
• 16: N. Nethercote. Dynamic Binary Analysis and Instrumentation. PhD thesis, U. Cambridge, 2004. http://valgrind.org.
• 17: N. Nethercote and J. Seward. Valgrind: A program supervision framework. Electronic Notes in Theoretical Computer Science, 89(2), 2003.
• 18: Nicholas Nethercote , Julian Seward, How to shadow every byte of memory used by a program, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA [doi>10.1145/1254810.1254820]
• 19: Nicholas Nethercote , Julian Seward, Valgrind: a framework for heavyweight dynamic binary instrumentation, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 20: J. Newsome and D. Song. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In NDSS, 2005.
• 21: Edmund B. Nightingale , Daniel Peek , Peter M. Chen , Jason Flinn, Parallelizing security checks on commodity hardware, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 22: Harish Patil , Charles Fischer, Low-cost, concurrent checking of pointer and array accesses in C programs, Software—Practice & Experience, v.27 n.1, p.87-110, Jan. 1997 [doi>10.1002/(SICI)1097-024X(199701)27:1<87::AID-SPE78>3.0.CO;2-P]
• 23: 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]
• 24: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 25: R. Shetty , M. Kharbutli , Y. Solihin , M. Prvulovic, HeapMon: a helper-thread approach to programmable, automatic, and low-overhead memory bug detection, IBM Journal of Research and Development, v.50 n.2/3, p.261-275, March 2006 [doi>10.1147/rd.502.0261]
• 26: Weidong Shi , Hsien-Hsin S. Lee , Laura `Falk , Mrinmoy Ghosh, An Integrated Framework for Dependable and Revivable Architectures Using Multicore Processors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.102-113, June 17-21, 2006
• 27: 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
• 28: The MITRE Corporation. Common vulnerabilities and exposures (cve). http://cve.mitre.org/.
• 29: G.-R. Uh, R. Cohn, B. Yadavalli, R. Peri, and R. Ayyagari. Analyzing dynamic binary instrumentation overhead. In WBIA Workshop at ASPLOS, 2006.
• 30: G. Venkataramani, I. Doudalis, Y. Solihin, and M. Prvulovic. FlexiTaint: A programmable accelerator for dynamic taint propagation. In HPCA, 2008.
• 31: Guru Venkataramani , Brandyn Roemer , Yan Solihin , Milos Prvulovic, MemTracker: Efficient and Programmable Support for Memory Access Monitoring and Debugging, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.273-284, February 10-14, 2007 [doi>10.1109/HPCA.2007.346205]
• 32: J. Wilander and M. Kamkar. A comparison of publicly available tools for dynamic buffer overflow prevention. In NDSS, 2003.
• 33: Min Xu , Rastislav Bodik , Mark D. Hill, A "flight data recorder" for enabling full-system multiprocessor deterministic replay, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 34: Min Xu , Mark D. Hill , Rastislav Bodik, A regulated transitive reduction (RTR) for longer memory race recording, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 35: Pin Zhou , Radu Teodorescu , Yuanyuan Zhou, HARD: Hardware-Assisted Lockset-based Race Detection, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.121-132, February 10-14, 2007 [doi>10.1109/HPCA.2007.346191]
• 36: Yuanyuan Zhou , Pin Zhou , Feng Qin , Wei Liu , Josep Torrellas, Efficient and flexible architectural support for dynamic monitoring, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.1, p.3-33, March 2005 [doi>10.1145/1061267.1061269]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Reliability

General Terms:
Algorithms, Reliability, Security

Keywords:
dynamic information flow tracking (dift), log-based monitoring, parallel algorithm, program monitoring, taint analysis