Efficient fine-grained binary instrumentationwith applications to taint-tracking

Fine-grained binary instrumentations, such as those for taint-tracking, have become very popular in computer security due to their applications in exploit detection, sandboxing, malware analysis, etc. However, practical application of taint-tracking has been limited by high performance overheads. For instance, previous software based techniques for taint-tracking on binary code have typically slowed down programs by a factor of 3 or more. In contrast, source-code based techniques have achieved better performance using high level optimizations. Unfortunately, these optimizations are difficult to perform on binaries since much of the high level program structure required by such static analyses is lost during the compilation process. In this paper, we address this challenge by developing static techniques that can recover some of the higher level structure from x86 binaries. Our new static analysis enables effective optimizations, which are applied in the context of taint tracking. As a result, we achieve a substantial reduction in performance overheads as compared to previous works.