LDX: Causality Inference by Lightweight Dual Execution

LDX: Causality Inference by Lightweight Dual Execution
ASPLOS 2016, 19%=53/240

Causality inference, such as dynamic taint analysis, has many applications (e.g., information leak detection). It determines whether an event e is causally dependent on a preceding event c during execution. We develop a new causality inference engine LDX. Given an execution, it spawns a slave execution, in which it mutates c and observes whether any change is induced at e. To preclude nondeterminism, LDX couples the executions by sharing syscall outcomes. To handle path differences induced by the perturbation, we develop a novel on-the-fly execution alignment scheme that maintains a counter to reflect the progress of execution. The scheme relies on program analysis and compiler transformation. LDX can effectively detect information leaks and security attacks with an average overhead of 6.08% while running the master and the slave concurrently on separate CPUs, much lower than existing systems that require instruction level monitoring. Furthermore, it has much better accuracy in causality inference.

  author    = {Yonghwi Kwon and
               Dohyeong Kim and
               William N. Sumner and
               Kyungtae Kim and
               Brendan Saltaformaggio and
               Xiangyu Zhang and
               Dongyan Xu},
  title     = {{LDX:} Causality Inference by Lightweight Dual Execution},
  booktitle = {{ASPLOS}},
  pages     = {503--515},
  year      = {2016},