podft: On Accelerating Dynamic Taint Analysis with
Precise Path Optimization
Zhiyou Tian
Xidian University

Cong Sun
Xidian University

21151213645@stu.xidian.edu.cn

suncong@xidian.edu.cn

Dongrui Zeng
Palo Alto Networks

Gang Tan
Pennsylvania State University

dzeng@paloaltonetworks.com

gtan@psu.edu

BAR 2023

Background and Motivations• Dynamic taint analysis (DTA)• What is it?
• Useful for security• Binary-level dynamic data-flow tracking (DFT)• Dynamic binary instrumentation (DBI)• Virtual machine manager (VMM)• Emulator

Background and Motivations• DBI-based DTA• Focus on explicit flows• Hold the tainting states within tagging memory• Challenge of DTA —— significant performance penalty

High Cost !

Background and Motivations• Existing works• Lift (MICOR 2006)• static fast path
• Libdft (VEE 2012)• on Pin• DBI inline routines• TaintRabbit (ASIA CCS 2020)• on DynamoRIO• dynamic fast path
• SELECTIVETAINT (USENIX 2021)• static binary rewriting
bloat the attack surface• value-set analysis
cannot work on library code

• podft advantages••••

more efficient
not bloat the attack surface
consider library code
flexible scalability

Our work —— podft defines and enforces various fast paths

Design of podft• podft overview•••••

BPA-based CFG Construction
VSA-based tainted inst identification
Tracking policy construction
PDG-based function abstract(from SDFT)
Pin-based Tracker
Fig1. Framework of podft (dashed block = usage of existing tools)

Next —— give a toy example to demonstrateExample demonstration• BPA-based CFG Construction• VSA-based tainted inst identification

basic block B (bbl-b)
basic block C (bbl-c)…etc

Fig.2 toy example

basic block A (bbl-a)

Example demonstration• Tracking policy construction• naive fast path ! main(bbl-c)• complex fast path ! toy_test+0x44(bbl-b)• slow path !toy_test(bbl-a)• function fast path !printf etc..

Why?
basic block A (bbl-a)

basic block B (bbl-b)

basic block C (bbl-c)

Example demonstration• Tracking policy construction• naive fast path ! main(bbl-c)• Not contain potentially tainted instructions

becausebasic block C (bbl-c)

Example demonstration• Tracking policy construction• complex fast path ! toy_test+0x44(bbl-b)• Contain potentially tainted instructions• Hot BBL (be executed multiple times)• TaintedMem(bbl) ∩ MergedDep(bbl) =∅.

becausebasic block B (bbl-b)

The data delivered to the sink are irrelevant to the tainted data from the source.

Example demonstration• Tracking policy construction• Slow path !toy_test(bbl-a)• Contain potentially tainted instructions• Not hot or TaintedMem(bbl) ∩ MergedDep(bbl) ≠ ∅becausebasic block A (bbl-a)

Example demonstration• PDG-based function abstract• Function fast path !printf etc..
• Pin-based Tracker
Input:• Function-level policies• Naive/Complex fast path policies• Slow path policies
output:• DTA results
Next ——podft’s efficiency and effectiveness.

Evaluations• Experimental Settings• Desktop with a 2.8GHz×4 Intel Core(TM) i7-7700HQ CPU, 8GB RAM,and Linux 3.16.0 kernel (Ubuntu 14.04 32-bit).
• The DBI framework is Pin v2.14, and libdft.

• Benchmark Programs

Evaluations• Efficiency of podft• Compare podft’s efficiency with Taint Rabbit , Dytan, Triton , and Taintgrind.

podft achieves
slowdowns of 1.6x
to 27.9x with anaverage slowdown of10.6x.
podft is more
efficient than theother DTA tools.

Evaluations• Efficiency of podft• Compare podft’s efficiency with SELECTIVETAINT.

podft achieves
slowdowns of 1.6x to27.9x with an averageslowdown of 12.5x.
and is generally more

efficient than
SELECTIVETAINT.

Evaluations• Effectiveness of podft’s Dynamic Taint Analysis

Real exploits detection by podftDevelop Pintool over podft to track vulnerability of CVEs

Work in progress• Work in progress

more scalable and more flexible to be used in traditional DTA

Hot BBl featureextraction
NN Training

Hot BBLHot BBl memory
abstraction

neural hot basic block embedding
Fig.1. the workflow of hot BBL embedding

Fig.2. the workflow of NeuTaint(SP2020)

THANKS
Thanks for listening