Flow Tracker Installation Page

What is Flow Tracker?

Flow tracker is a tool that detects timing attack vulnerabilities in C/C++ programs that implement cryptographic routines. If the program contains a vulnerability, then Flow Tracker finds one or more (static) traces of instructions that uncover it. A vulnerable trace describes a sequence of data and control dependences from a secret information - e.g., a crypto key, the seed for a random number generator, etc - to a predicate of a branch. This is a problem because the branch normally influences the execution time of the program. So, if an adversary can measure this time for a given input which he controls, it may discover some information about the secret that we want to protect.

Timming Attacks?? What is it?

In cryptography, a timing attack is a side channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, and the time can differ based on the input; with precise measurements of the time for each operation, an attacker can work backwards to the input.

Information about the key or other sensitive information can leak from a system through measurement of the time it takes to respond to certain queries. How much such information can help an attacker depends on many variables: crypto system design, the CPU running the system, the algorithms used, assorted implementation details, timing attack countermeasures, the accuracy of the timing measurements, etc

LLVM Install

Flow Tracker has been implemented as an LLVM 3.7 Compiler pass. To run it, we use opt, a tool that comes in the llvm distribution. Thus, to use our tool, you need to install llvm 3.7. To download LLVM 3.7 use the links below:
i) LLVM 3.7
ii) Clang
- Extract llvm-3.7.0.src.tar.xz in your home directory. You can rename that folder to llvm37 for instance. Now, extract cfe-3.7.0.src.tar.xz and rename cfe-3.7.0.src as clang like /YourHome/llvm37/tool/clang
- Notice that if your system does not have an installation of g++, you will need to install it. (For Debian Linux, type as a root the following command... apt-get install g++)
- Create a folder named build in /YourHome/llvm37 and inside this build folder, you must configure the sources linke bellow. - Once you download llvm, you must type ../configure --disable-bindings at /YourHome/llvm37/build. After the configuration script finished its execution, you must type make -j 4
- After compilation, include the path to the llvm binarie in your /YourHome/.bashrc. You can do this using the following line:
export PATH=$PATH:/YourHome/llvm37/build/Release+Asserts/bin

Flow Tracker Install

Flow Tracker is available at this link.
Extract the flowtracker.tar.gz to /YourHome/llvm37/lib/Transforms/ and also to /YourHome/llvm37/build/lib/Transforms/
Now, you must compile each of the passes that constitute Flow Tracker:
cd /YourHome/llvm37/build/lib/Transforms/AliasSets
cd /YourHome/llvm37/build/lib/Transforms/DepGraph
cd /YourHome/llvm37/build/lib/Transforms/bSSA2
You have also to compile the xmlparser using the command below inside /YourHome/llvm37/lib/Transforms/bSSA2:
g++ -shared -o parserXML.so -fPIC parserXML.cpp tinyxml2.cpp
The command above will create a file named parserXML.so. Move this file to /YourHome/llvm37/build/Release+Asserts/lib.

Flow Tracker Usage

To demonstrate how to use Flow Tracker, we will find a vulnerability in this program. This file is an implementation of the montgomery reduction. It must run in constant time, otherwise it may disclosure parts of the crypto key that it uses internally. So, we want to know if the program runs always in the same time, independent on the cryptographic key or on the input that it uses. To do that, type the following command:
clang -emit-llvm -c -g monty.c -o monty.bc
opt -instnamer -mem2reg monty.bc > monty.rbc
opt -basicaa -load AliasSets.so -load DepGraph.so -load bSSA2.so -bssa2 -xmlfile in.xml monty.rbc
Moreover, you can join several .c files in a single .bc using clang + llvm-link just like example bellow:
clang -emit-llvm -c -g main.c -o main.bc
clang -emit-llvm -c -g foo.c -o foo.bc
llvm-link foo.bc main.bc -o out.bc
Please, see that you must inform a xml file with the functions and respective parameters which you consider sensitive or secrete information. Below you can see an example of such an xml file. In this case, Flow Tracker will locate the function named fp_rdcn_var and it will consider the first and the second parameters as sensitive information. If the user specify the parameter 0, FlowTracker will consider the function's return value as a secret.
If the target program contains a vulnerable trace, then Flow Tracker will create two files for each of those traces.

- The first one is a .dot file which requires a dot visualization tool like xdot to visualize it. This file shows the vulnerable subgraph of the entire dependence graph of the program analyzed. The nodes are operands and operators of the LLVM Intermediate Representation. The label used at each node informs the line and the filename where that node was observed by Flow Tracker. In case you find this file hard to understand, we also output an ASCII report, which we describe next.

- The second output of Flow Tracker is an ASCII file which informs the start line in your code where the problem happens and the intermediate lines that propagate the secret information. It also shows the line that contains the function or branch that uses this information. For instance, Let's see the content of the respective ASCII file that Flow Tracker produces to our (monty.c) example]:
Tracking vulnerability for 'file monty.c line 298 to file monty.c line 181 '
monty.c 181
monty.c 181
monty.c 181
monty.c 246
monty.c 246
monty.c 246
monty.c 199
monty.c 199
monty.c 199
monty.c 199
monty.c 199
monty.c 199
As we can see, the monty.c has a vulnerable trace that starts at line 298 and finishes at line 181. The following lines shows in backward way the entire vulnerable trace. We do not show the last line in the trace, only in the header description. Line 199 is the line that comes immediately before the start line 298 in our trace.

Virtual Machine

If you do not want to install llvm and Flow Tracker, and you have a lot of network bandwidth available, you can download our Virtual Machine (Virtual Box) with Linux Ubuntu 14 64 bits and Flow Tracker. You must install Virtual Box in your system and download our virtual machine.

The virtual machine user name is "user" and password is "user". At home directory you will see a folder named monty which contains a tiny example of the montgomery reduction. You may use it in order to test Flow Tracker. To do it, just type:
clang -emit-llvm -c -g monty.c -o monty.bc
opt -instnamer -mem2reg monty.bc > monty.rbc
opt -load AliasSets.so -load DepGraph.so -load hammock.so -load bSSA2.so -bssa2 -xmlfile in.xml monty.rbc

Example Gallery

In this section we show some examples of programs, and the results that out flow tracker analysis produces for them. For all examples, our secret is the variable pw. We use the following keys in the table: - C-Src: the C program that we have analyzed. This is an actual program, i.e., the very input to our analyzer.
- Full Dep Graph: the complete Dependence Graph with control edges and data edges. Each vertex is labeled with one operand or operator.
- Tainted Sub Graph:the Dependence Graph which IS produced by our tool. This DFG has the respective line numbers from source file and is useful for developer to identify the vulnerability in the code. Note that the SUB-DFG is one example, however the tool can to produce more than one SUB-DFG if there exists several vulnerable paths. In red color is the shortest path which connects the secret to a branch instruction.
- TXT-Lines: ASCII format of the path in red color presented at "Taited Sub Graph".