2008 · 71 citations · 37 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureComputer SecurityParallel ComputingControl-flow AnalysisData-flow AnalysisLog AnalysisParallel ArchitecturesParallel Computer ArchitectureData Flow TrackingDynamic Information Flow TrackingExecution Trace AnalysisExecution TracingHardware Acceleration SupportLog-based DetectionProgram Trace Analysis
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.
37
Chi-Keung Luk, Robert Cohn, Robert Muth et al. · ACM SIGPLAN Notices · 2005 · 3.2K citations
Chi-Keung Luk, Robert Cohn, Robert Muth et al. · 2005 · 2.3K citations
Nicholas Nethercote, Julian Seward · 2007 · 2.3K citations
Stefan Savage, Michael T. Burrows, Greg Nelson et al. · ACM Transactions on Computer Systems · 1997 · 1.6K citations · Full text
Extended static checking for Java
Cormac Flanagan, K. Rustan M. Leino, Mark Lillibridge et al. · 2002 · 1.3K citations