# Dynamic Information Flow Tracking: Taxonomy, Challenges, and Opportunities
## 4 Software-Based Dynamic Information Flow Tracking
### Program-Level Dynamic Information Flow Tracking  
[PERSON] et al. in [PERSON] et al. (2018) proposed an instrumentation method to track the tag for the target program and shared libraries dynamically. This system includes four parts: a configuration file, shadow memory, a program monitor and a loader. The configuration file is responsible for security policy configuration. Shadow memory is a special structure to hold the tag. The program and its metadata are loaded at the initial stage using the loader. The program monitor activates the customized security policies and raises an exception when the tag check fails. This type of method may incur a high performance overhead for two reasons: an instrumentation overhead and a runtime overhead. The influence of the instrumentation overhead is relatively small because of modern storage capabilities. The runtime overhead comes from register spilling, tag mapping and tag propagation. In order to further reduce the whole performance overhead, the runtime overhead needs to be optimized. [PERSON] et al. in [PERSON] et al. (2018) presented an efficient static information flow tracking method in order to reduce the performance overhead. Instead of using DBI-based methods, they adopted static binary instrumentation (SBI) to scan sources of taint and select the instructions need to be implemented and monitored. They proposed an approach to statically identify the instructions that will involve tainted memory or registers through value set analysis (VSA). Similarly, [PERSON] et al. in [PERSON] et al. (2019) presented a basic software framework to enforce data-flow integrity. This framework includes two basic steps: i) using static analysis (reaching definition analysis) to generate a data-flow graph (DFG); ii) running the target program to ensure the data flow follows the DFG at runtime. This method introduces a high performance overhead and many false negatives because of the more conservative static analysis. To support more flexible and programmable dynamic taint analysis, [PERSON] et al. in [PERSON] et al. (2019) presented a framework to perform data-flow and control-flow taint analysis. This framework provides variable tags for different types of program data, including variables, memory locations, function calls and I/O streams. Therefore, a software programmer can specify different tags for different data to perform various analyses, e.g., program debugging, program testing and vulnerability detection. Further, the data can be assigned multiple tags at the same time for different usages. The tag checking and propagation rules can be configured to examine different tags. The flexible tag design introduces a high performance overhead caused by programmable tag checking and propagation rules at runtime, and a storage overhead. [PERSON] et al. in [PERSON] et al. (2019) presented an IFT system for smartphones to provide adequate control over user's privacy information. The main goal of this system is to monitor the usage of sensitive user information on third-party applications. Therefore, multiple sources of sensitive data need to be tracked at runtime. This IFT system provides four basic granularities of data tracking, i.e., variable-level, method-level, message-level and file-level, to enforce complete data tracking on smartphones. For variable-level tracking, every variable is assigned a bit vector to hold 32 different taint markings. The tags are stored adjacent to variables to provide spatial locality. Additionally, the size of stack frame allocated is doubled. The message-level tracking is responsible for the messages between different processors. The method-level tracking is used for system-provided native libraries. The consistency of taint metadata is ensured by file-level tracking. The tag propagation logic for object reference, native code, IPC and secondary storage is implemented in the virtual machine (VM) interpreter. The authors in [PERSON] et al. (2018) aimed to provide a shared dynamic flow tracking (DFT) library for commodity software without modifications.