Parallelizing Dynamic Information Flow Tracking

Tuesday March 4, 2008
Hamerschlag Hall D-210
4:00 pm

Olatunji Ruwase
Carnegie Mellon University

Despite software auditing, pre-release testing and static analysis, production software remains buggy. Consequently run-time monitoring tools (lifeguards) remain valuable for software reliability. Dynamic Information Flow Tracking (DIFT) lifeguards detect and fix/contain security and memory bugs in an executing program by tracking how information propagates through the registers and memory locations of an executing program. The fine-grained nature of DIFT monitoring and contention for hardware resources between the lifeguard and the monitored program results in the monitored program experiencing 15-80X slowdown, which is unacceptable for production code.

Log-based Architecture (LBA) tackles the resource contention issue by augmenting chip multiprocessors with a hardware mechanism for the efficient logging and delivery of the execution trace of a program to a monitoring process running on a separate core. Monitoring overhead of DIFT lifeguards reduces to as low as 3X on LBA systems.

In this talk, we propose parallel DIFT for achieving real time program monitoring on LBA systems. We present an algorithm for parallelizing DIFT lifeguards that is based on parallel inheritance tracking. We also present a relaxed variant of DIFT, that propagates information only through unary operations but is still capable of detecting the most common security attacks and memory bugs.

We have implemented a parallel relaxed security DIFT lifeguard (taint analysis) in the context of an LBA system. We compared the performance of a sequential and parallel relaxed taint analysis lifeguard in a simulated 16-core LBA system, with the parallel lifeguard using up to 9 monitoring cores. Our results show that the parallel lifeguard is up to 2.75X faster. Furthermore, monitoring overhead is reduced to as low as 1.2X, making monitoring of production code practical.

Olatunji Ruwase is a 2nd year PhD student advised by Professor Todd Mowry in the Computer Science Department at Carnegie Mellon University. He received a B.S. Computer Science from University of Ibadan, Nigeria and a M.S. Computer Science from Stanford University. His research interests are compilers and computer architecture.