Complete information flow tracking from the gates up

From AcaWiki
Jump to: navigation, search

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? 
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.
  • 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."
Retrieved from "https://acawiki.org/index.php?title=Complete_information_flow_tracking_from_the_gates_up&oldid=11859"