# Complete information flow tracking from the gates up

From AcaWiki

**Citation:** *Mohit Tiwari, Hassan Mohamed Gamal Wassel, Bita Mazloom, Shashidhar C Mysore, Frederic T Chong, Timothy Peter Sherwood (2009/03) Complete information flow tracking from the gates up. International conference on Architectural support for programming languages and operating systems (RSS)*

**DOI (original publisher):** 10.1145/1508244.1508258

**Semantic Scholar (metadata)**: 10.1145/1508244.1508258

**Sci-Hub (fulltext)**: 10.1145/1508244.1508258

**Internet Archive Scholar (search for fulltext)**: Complete information flow tracking from the gates up

**Download:** https://dl.acm.org/doi/abs/10.1145/1508244.1508258

**Tagged:** Computer Science
(RSS) computer architecture (RSS)

## Elsewhere

## Problem

- How to prevent sensitive information from leaking through side-channels in a processor?
- Tracking taint precisely is undecidable.

if is_halting_program(x): print(y) # does x taint y? # Possibly... can't know for sure without solving halting problem.

## Solution

- GLIFT: Gate-Level Information Tracking
- Make program into boolean circuit. For each gate in the real circuit, have a second "shadow" gate that decides if the output is tainted given whether the inputs are tainted.
- Let n_t refer to "variable n is tainted" in the following example: if the real gate is c = AND(a, b), then the taint-propagating shadow-gate is c_t = OR(AND(a_t, b_t), AND(b, NOT(b_t), a), AND(a, NOT(a_t), b)).
- In the first case, AND(a_t, b_t), both inputs are tainted. In the second and third case, AND(b, NOT(b_t), a) (vice-versa) at least one true input is untainted. These are the only three cases when tainted information can affect an untainted variable.
- Traditional approaches use the more conservative c_t = OR(a_t, b_t).
- In the traditional approach, even in simple circuits like boolean counters, everything ends up being tainted.
- The approach presented in this paper is more precise (fewer false positives "this is marked tainted/secret when it doesn't need to be") than the traditional approach.

- In the first case, AND(a_t, b_t), both inputs are tainted. In the second and third case, AND(b, NOT(b_t), a) (vice-versa) at least one true input is untainted. These are the only three cases when tainted information can affect an untainted variable.

- Let n_t refer to "variable n is tainted" in the following example: if the real gate is c = AND(a, b), then the taint-propagating shadow-gate is c_t = OR(AND(a_t, b_t), AND(b, NOT(b_t), a), AND(a, NOT(a_t), b)).

- Make program into boolean circuit. For each gate in the real circuit, have a second "shadow" gate that decides if the output is tainted given whether the inputs are tainted.

- Build a machine based on GLIFT.
- Use predicated instructions for conditionals.
- Loops must be of statically fixed size, but can have predicated instructions to emulate "early termination."