Taint is dynamically tracked on a mobile device. Taint virtual instructions are added to virtual instructions of a control-flow graph (CFG). A taint virtual instruction has a taint operand that corresponds to an operand of a virtual instruction and has a taint output that corresponds to an output of the virtual instruction in a block of the CFG. Registers are allocated for the taint virtual instruction and the virtual instructions. After register allocation, the taint virtual instruction and the virtual instructions are converted to native code, which is executed to track taint on the mobile device.