Differential Address Trace Analysis
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
analysis
cryptolib
pin
pintool
.gitignore
LICENSE
Makefile
README.md

README.md

DATA - Differential Address Trace Analysis

Side-channel attacks infer sensitive information from computing devices by monitoring supposedly benign properties like execution time or power consumption. Similar side-information can also be obtained from memory hierarchies and microarchitectures of modern processors. TLBs, caches, and branch prediction units, for instance, have all been targets to so-called microarchitectural attacks. These attacks typically exploit the persistent state of shared processor resources and can be launched without having physical access to a target device. Microarchitectural attacks bypass important isolation mechanisms employed by operating systems or hypervisors and consequently put critical applications at risk. Dedicated countermeasures, however, are only slowly deployed or often completely omitted in practice.

This is why we developed DATA, a differential address trace analysis framework. In simple terms, DATA is an analysis tool for detecting data and code accesses that can potentially be exploited by microarchitectural attacks. More precisely, DATA reveals address-based side-channel leaks, which account for attacks exploiting caches, TLBs, branch prediction, control channels, and likewise. The detection of leaks in a program under test works by instrumenting its binary while it processes secret information. If any data or code accesses exhibit relations to the processed secret, DATA reports them with instruction-level granularity. The relations are determined with statistical tests and classified according to the information an adversary could gain from them.

DATA is intended to be a companion during testing and verification of security-critical software. It helps to improve code quality by detecting information leaks early in the development process. Given the modest deployment of countermeasures against microarchitectural attacks in practice and the continuing discovery of new attacks, DATA constitutes an important part of the defense strategy of security and privacy critical applications.

For more information on microarchitectural attacks, the survey by Ge et al. is a good starting point.

Table of Contents

Tool Description

DATA works in three consecutive phases. Starting with the difference detection phase, the program under test is executed multiple times with different secret inputs and the addresses of all code and data accesses are written to so-called address traces. A specifically designed algorithm then compares the traces pairwise, reports differing code and data accesses, and accumulates all differences in an intermediate report. This is somewhat similar to comparing multiple text files with diff.

In the leakage detection phase, the reported control-flow and data differences are tested for dependencies on the secret input. This is done using a statistical test that compares the address traces of (i) a fixed secret input and (ii) random secret inputs. If the traces, and thus the execution, differ significantly, the corresponding control-flow and data differences are labeled as information leaks. The test results are then added to the intermediate report.

In the leakage classification phase, the reported leaks are augmented with the amount of information that can be gained from them. This is achieved with a statistical test that finds linear and non-linear relations between the secret input and the address traces. The results are valuable to determine the severity and exploitability of a leak. They are again added to the previous report, forming the final output of DATA.

Implementation Details

The address traces are generated by monitoring the program under test with a dynamic binary instrumentation framework. In the current implementation, we use Intel Pin with a custom Pintool that dumps the addresses of all executed instructions and all accessed operands. It preserves the call hierarchy and implements basic tracking of dynamic memory objects.

The detection of information leaks is done with Kuiper's test. This metric is closely related to the Kolmogorov-Smirnov statistic, a non-parametric equality test of probability distributions. In DATA, Kuiper's test is used to compare the address distributions observed at a given control-flow or data difference. If these distributions are distinct for different input sets, we conclude that the tested difference leaks some information about the secret input. Since this amount is unspecified, we say the test is a generic leakage test.

To further quantify the information an adversary can obtain from observing a leak, a specific leakage test is added. The idea behind the test is to determine any relation between the secret input and the observed addresses at a given control-flow or data leak. This is done with a bivariate relationship test, for which we use the Randomized Dependence Coefficient or RDC. Similar to Mutual Information metrics, it captures any linear or non-linear relation between the observations of two random variables.

Directory Structure

Folder Description
cryptolib Crypto frameworks (programs under test). Currently, OpenSSL and pyCrypto are supported.
Each framework provides bash script(s) that invoke the DATA scripts.
 ↳common Shared DATA scripts that coordinate all phases of DATA and invoke Intel Pin
as well as the Python analysis scripts
pin Root directory of the Intel Pin DBI framework
pintool DATA's Pintool extension to generate address traces
analysis Python analysis scripts for trace analysis, statistical tests, and reporting
 ↳leakage_models Input transformations for leakage classification (phase 3)
results This directory is automatically created during analysis. It contains the
analysis results and all files needed to obtain them, e.g. traces and keys.

Dependencies

DATA is currently implemented for 64-bit x86 Linux systems. It has been tested on Ubuntu 14.04 as well as Debian 8.3 and 9.4. On Debian/Ubuntu, the following packages are required to run DATA:

sudo apt-get install coreutils util-linux bash sed grep wget tar mawk time build-essential xdg-utils git python python-dev python-virtualenv

Build

The entire project contains Makefiles that can be used to build source code and clean up the build files afterwards. If in doubt, type make help and check the available options. By issuing

make

in the project root directory, Intel Pin is downloaded and unpacked, the Pintool is compiled, and the Python virtual environment is set up. Also, config.mk is created, holding important global absolute paths.

make clean

issues a shallow clean-up and for instance removes the build files of the Pintool. The command

make mrproper

triggers a complete clean-up of the framework and entirely removes Intel Pin, any downloaded crypto frameworks, and the Python virtual environment. Note that it might take some time to redo these steps, so only use mrproper when necessary.

Customization

Since the results directory can become rather large, its path can be modified in config.mk. To do so, modify the variable RESULTDIR inside config.mk to an absolute path with more disk space.

Run The Analysis

The Makefile in the root directory can trigger an example analysis run of the Data Encryption Standard (DES) implementation in OpenSSL. By issuing

make run

OpenSSL is downloaded and built, and all three phases of DATA are executed consecutively with default settings. Each phase can also be run separately with

make phase1
make phase2
make phase3

This might be helpful to play with analysis parameters and to get a better understanding of what each phase is doing. After each phase is completed, the Makefile automatically opens the (intermediate) analysis reports with the system's preferred application for viewing XMLs.

Analyzing Other Algorithms

To analyze other algorithms, override the Makefile variables accordingly. Here are a few examples:

  • Run all phases for OpenSSL AES:

    make FRAMEWORK=openssl SCRIPT=symmetric.sh ALGO=aes-128-ecb KS=128 run

  • Run phase 1 for OpenSSL RSA:

    make FRAMEWORK=openssl SCRIPT=asymmetric.sh ALGO=rsa KS= phase1

  • Run phase 1 for Python AES (do not use parallel execution unless you have enough RAM!):

    make FRAMEWORK=python SCRIPT=symmetric.sh ALGO=AES KS= PARALLEL= phase1

All configurable Makefile variables are listed here:

Variable Description
FRAMEWORK Framework directory path in cryptolib/
SCRIPT Framework bash script in `cryptolib/${FRAMEWORK}
ALGO Framework algorithm. For a list of algorithms, execute
cd cryptolib/${FRAMEWORK}; ./${SCRIPT} -l.
This will print optional key sizes in the second column.
KS Key size of ALGO. Set KS=, if not needed by ALGO.
PARALLEL Set PARALLEL= to disable parallel execution
TREUSE Set TREUSE= to disable trace reuse in phase 3

Analysis Steps

Preparation

Before the analysis is started, the DATA script creates a new result directory. By default it is named results and placed in the root directory. Within the results folder, a session sub-directory containing the current date and time is created. This allows to keep multiple analyses of the same program under test. Within the session dir, every analyzed program under test gets an individual sub-directory, in which every algorithm in turn gets its own analysis directory. For the example analysis of DES, the result path is

results/yyyy_mm_dd-hh:mm:ss/openssl/des-ecb

Before analyzing a cipher implementation in OpenSSL or pyCrypto, the DATA script generates the necessary key files and places them in the result directory.

Phase 1: Difference Detection

The first phase starts by recording full-length address traces with Intel Pin. Each execution of the program under test uses a different secret input. The analysis script then compares the traces to find control-flow and data differences.

At the end of phase 1, all differences are accumulated in leaks.bin and result_phase1.pickle. These are mandatory input files for phases 2 and 3. If a program under test yields no differences, the analysis is stopped and phases 2 and 3 are skipped. This is because there are no points of interest to observe in more detail.

Phase 2: Leakage Detection

The second phase continues the analysis by recording reduced address traces. For every execution of the program under test, the Pintool monitors only the instructions and memory loads listed in leaks.bin. This significantly reduces the instrumentation time and the trace sizes.

The DATA script calls Intel Pin to generate reduced traces for two input sets: fixed and random. For the fixed set, the program under test is executed repeatedly with the same secret input. For the random set, distinct inputs are generated and the program under test is executed once with each input. All traces and corresponding inputs are stored in the gen_* sub-directories.

The analysis script then iterates over all differences from phase 1 and compares the observed addresses in the fixed and random trace sets. If the addresses do not have a similar distribution in both sets, the corresponding difference is flagged as an information leak.

A common characteristic of fixed-vs-random leakage tests is that the choice of the fixed input has an effect on the test results. A particularly poor choice might cause the test to miss some leaks. This is why the generic leakage test is repeated for multiple fixed inputs.

At the end of phase 2, the results of all generic leakage tests are accumulated in result_phase2.pickle. This is a mandatory input file for the third phase.

Phase 3: Leakage Classification

The third phase requires reduced address traces obtained from (partly) random inputs. It is therefore possible to reuse some of the traces from phase 2 (see Usage Tips). If more traces are needed, the DATA script will generate the necessary delta. All traces and corresponding inputs are stored in the spe_* sub-directories.

The analysis script then iterates over all leaks from phase 2 and tests whether parts or properties of the secret input relate to the addresses observed at a leak. These parts and properties are specified by leakage models. Common models in side-channel analysis are Hamming weight, which reduces an input to its number of 1-bits, and input slicing, which tests individual bits and bytes of the input for relations.

Every statistical relation that the specific leakage test reveals is reported in a dedicated result file of the form result_phase3_<leakage-model>.pickle. Since the same traces can be tested with multiple leakage models, each model gets a separate result file.

Analysis Reports

In addition to the .pickle files, the analysis script stores all results in readable XML reports. They show where differences and leaks occur, and list the results of generic and specific leakage tests. The reports can be found in each analysis directory as:

  • result_phase1.xml
  • result_phase2.xml
  • result_phase3_<leakage-model>.xml

The results of all phases are summarized in result_final.xml. All generated reports have the same basic structure:

<Report>
  <CallHierarchy>
    ...
  </CallHierarchy>
  <LibHierarchy>
    ...
  </LibHierarchy>
<Report>

CallHierarchy

The CallHierarchy lists differences and leaks according to the call graph. Every function call in the execution creates a new context to which differences and leaks can be attributed. The following is an example of a function call during DES encryption in OpenSSL:

<context>
  CALL 7ffff6374872(+179872)[733]: PEM_read_bio(T)@/PATH/libcrypto.so.1.1
  TO 7ffff634c570(+151570)[250]: EVP_DecodeUpdate(T)@/PATH/libcrypto.so.1.1
</context>

The snippet reports that there was a call in PEM_read_bio() to EVP_DecodeUpdate(). For each code location, the report prints a set of properties:

Property Description
7ffff6374872 absolute (virtual) address
(+179872) relative address offset in the binary
[733] symbol size, if known (otherwise ? is printed)
PEM_read_bio symbol name, if known (otherwise ? is printed)
(T) symbol type, taken from nm --defined-only <binary>
/PATH/libcrypto.so.1.1 the absolute binary path

In the <CallHierarchy> element, control-flow and data differences or leaks are always attributed to a context. They are printed before the return of the call, which is indicated by </context>, as shown:

<context>
  CALL ...
  TO ...
  <dataleaks>
    ...
  </dataleaks>
  <cfleaks>
    ...
  </cfleaks>
</context>

Individual differences and leaks are each presented with a separate entry. The following leak appears during DES encryption:

<dataleaks>
  <leak>
    7ffff62ea2e9(+1782e9)[1f]: OPENSSL_hexchar2int(T)@/PATH/libcrypto.so.1.1
    7ffff6391a60: 36
    7ffff6391a61: 48
    7ffff6391a62: 12
    ...
    <result status='leak' type='generic,specific'>
      <generic result='leak' source='H_pos' kuiper='0.866667' significance='0.438291' confidence='0.999900'/>
      <generic result='leak' source='H_addr' kuiper='0.192708' significance='0.112697' confidence='0.999900'/>
      ...
      <specific result='leak' source='M_pos' leakagemodel='sym_byte_value' property='2' address='7ffff6391a96' rdc='0.4166' significance='0.4123' confidence='0.999900'/>
      <specific result='leak' source='M_addr' leakagemodel='sym_byte_value' property='2' address='7ffff6391a96' rdc='0.4577' significance='0.4123' confidence='0.999900'/>
      ...
    </result>
    <MIN>
      7ffff6391a60(+21fa60)[37]: CSWTCH.22(r)@/PATH/libcrypto.so.1.1
    </MIN>
    <MAX>
      7ffff6391a96(+21fa96)[37]: CSWTCH.22(r)@/PATH/libcrypto.so.1.1
    </MAX>
  </leak>
</dataleaks>

The location of the leak is reported similar to a function call. In the example, the instruction at address 7ffff62ea2e9(+1782e9) in function OPENSSL_hexchar2int() in the libcrypto.so.1.1 library causes a data leak. In the analyzed traces, this instruction accesses address 7ffff6391a60 36 times, address 7ffff6391a61 48 times, and so on. We refer to these accesses as evidences of the leak. The <MIN> and <MAX> elements show the smallest and largest evidences, and thereby give the range of the leak. The location of these evidences is reported similar to function calls. In this example, the leaking instruction accesses a compiler-generated lookup table named CSWTCH.22.

The conclusions of the generic and specific leakage tests are given in the <result> element. The result status can be difference, leak, or dropped. Leaks are either generic, specific or both. Generic leaks are reported as follows:

Attribute Description
result test result, leak or none (if result is insignificant)
source leakage source, H_pos or H_addr
kuiper Kuiper test statistic
significance significance threshold for the test statistic
confidence probability with which test results are truly significant

The leakage source H_pos states that the total number of evidences leaks information about the secret input. In contrast, H_addr states that the number of accesses per address leaks. If the Kuiper statistic is above the significance threshold, the result is set to leak. The confidence level states the probability of this result being a true positive. Specific leaks are reported similarly, although more information about the leakage model is provided:

Attribute Description
result test result, leak or none (if result is insignificant)
source leakage source, M_pos or M_addr
leakagemodel leakage model, as loaded from the analysis directory
property part or property of the input that exhibits a relation to the accessed address
address accessed address that exhibits a relation to the secret input
rdc RDC test statistic
significance significance threshold for the test statistic
confidence probability with which test results are truly significant

M_pos and M_addr are two matrices that are used in the specific leakage test. These matrices are built individually for each leak. For every address that is accessed at a leak, a row is added to the matrices. In M_pos, the columns contain the positions at which an address is accessed. For example, if a leaking instruction performs three memory loads, the possible positions are 0, 1, and 2. If there is no access for an address, -1 is entered. If an address is accessed multiple times, the median of the positions is entered. In M_addr, the columns contain how often an address has been accessed. If there is no access for an address, 0 is entered.

The specific leakage test compares each row in M_pos and M_addr with the output of the leakage model. Depending on the model, there can be multiple properties of one input. For example, if individual bytes of a 64-bit DES key are compared to the rows in M_pos and M_addr, there are in total 8 properties (bytes 0 to 7) that may be reported for a leak.

If the test result is significant for a leak, the reported address reveals the part or property of the input that is specified by the leakage model. For instance, if the Hamming weight model shows significant relations, then an adversary can obtain the Hamming weight of the input from the leak. Again, the confidence level states the probability with which this relation is truly significant.

LibHierarchy

The LibHierarchy takes the same differences and leaks as contained in the CallHierarchy and splits them according to functions and corresponding binaries. For the data leak discussed in the previous section, the LibHierarchy representation looks as follows:

<Lib>
  /PATH/libcrypto.so.1.1 7ffff6172000-7ffff6619e97 (dynamic)
  <Function>
    7ffff62ea2d0(+1782d0)[1f]: OPENSSL_hexchar2int(T)@/PATH/libcrypto.so.1.1
    <dataleaks>
      <leak>
        7ffff62ea2e9(+1782e9)[1f]: OPENSSL_hexchar2int(T)@/PATH/libcrypto.so.1.1
        ...
      </leak>
    </dataleaks>
  </Function>
</Lib>

Next to the absolute path of the binary, the range 7ffff6172000-7ffff6619e97 denotes the location at which the binary was mapped in the virtual address space. If the binary was dynamically loaded, a (dynamic) flag is added. Instead of contexts, the LibHierarchy contains <Function> elements to which differences and leaks are attributed. Each element contains the absolute and relative location of the function as well as its symbol size, name, and type (if available). Leaks are then reported identically to the CallHierarchy.

Leakage Statistics

At the end of the <CallHierarchy> and each library in <LibHierarchy> there is a summary of all reported differences and leaks in so-called <LeakStats>. It is structured as follows:

<LeakStats>
  <Differences>
    ...
  </Differences>
  <Leaks>
    <Generic>
      ...
    </Generic>
    <Specific>
      ...
    </Specific>
  </Leaks>
</LeakStats>

The summary is split into two parts: <Differences> and <Leaks>. The <Differences> element looks as follows:

<Differences>
  cflow: 164
  cflow-drop: 12
  cflow-notest: 5
  data: 349
  data-drop: 39
  data-notest: 15
</Differences>

The exemplary results show that 164 control-flow differences have been detected in phase 1, out of which 12 have been discarded in phase 2. 5 differences have not been tested, because there weren't enough traces to perform the generic leakage test in phase 2. Similarly, out of 349 data differences, 39 were discarded and 15 weren't tested at all. We recommend to increase the number of measurements as long as differences show up untested in the leakage statistics (see Usage Tips).

The <Leaks> element provides generic and specific leakage test results from phases 2 and 3, respectively. Each element in <Leaks> distinguishes between data and control-flow results:

<Leaks>
  <Generic>
    cflow: 147
    data: 297
  </Generic>
  <Specific>
    leakage-model: dsa_privkey_hw
    cflow: 6
    data: 24
  </Specific>
</Leaks>

The <Generic> element shows that 147 control-flow differences have been flagged as information leaks. This correspond to the previous numbers, since 164 differences - 12 discarded ones - 5 untested ones = 147 leaks. Similarly, 295 data leaks have been found among 349 differences, of which 39 have been discarded and 15 have not been tested.

The <Specific> element shows that 6 control-flow and 24 data leaks exhibit significant relations to the Hamming weight of the secret input, a DSA private key in this example. Since multiple leakage models can be tested, reports can contain multiple <Specific> result elements.

Usage Tips

The following sections contain usage recommendations that help improve your experience with DATA.

Analysis Speed-Up

The DATA script currently offers two settings that reduce the analysis time. When called with the command line argument -p or --parallel, most of the trace recording and calls to the analysis script will be performed in separate sub-processes. The number of sub-processes is limited by the number of processor cores available to the script. Nevertheless, make sure that sufficient system resources are available, as the analysis might cause significant system load.

The second command line option is -u or --reusetraces. It forces the DATA script to reuse all traces from phase 2 for the analysis in phase 3. If more traces are needed than were recorded in phase 2, the script automatically records the missing traces.

Program Inputs and Non-Determinism

When testing a program with DATA, it is recommended to set all non-secret or unrelated program inputs to fixed values. This reduces noise in the address traces and reveals leaks faster. If an input can't be fixed, DATA will filter out its effects and still reveal all leaks. Simply record more traces in this case. The same holds for non-deterministic program behavior, which is for instance introduced by side-channel countermeasures that randomize code or data accesses. Any non-deterministic behavior with no relation to the secret will be filtered at the expense of increasing the number of traces.

Number of Traces

The number of traces in each phase can be configured in the framework script of each tested program. For OpenSSL, there is one script for symmetric and one for asymmetric ciphers. For pyCrypto, there is one script for symmetric ciphers. In those scripts, the trace numbers are configured via variables:

Variable Description
NTRACE_DIFF number of keys / traces to generate in phase 1
NREPS_GEN number of generic leakage test repetitions in phase 2
NTRACE_GEN number of traces to generate per repetition in phase 2
NTRACE_SPE number of traces to generate in phase 3

Always make sure that NTRACE_DIFF is larger or equal than NREPS_GEN. Since it is not possible to provide reasonable measurement numbers that hold for arbitrary programs under test, we recommend to start with the default numbers that are pre-configured. Increase NTRACE_DIFF as long as new differences appear. Once the number of differences settles, increase NTRACE_GEN as long as the leakage statistics contain untested differences. Increase NREPS_GEN if there seem to be leaks among the dropped differences. Finally, increase NTRACE_SPE to reveal faint relations in the specific leakage tests. Note that increasing NTRACE_DIFF requires new measurements for phases 2 and 3, if the additional traces in phase 1 reveal new differences.

Contact Us

DATA is under active development and we always welcome feedback of any kind -- from bug reports to new ideas. Future versions of DATA will provide improved performance and usability. If you want to use DATA commercially, we offer appropriate licenses upon request. Feel free to send any inquiries directly to us.

License

This project is released under the GNU GPLv3 License. For more permissive commercial licenses, please contact us.

Publication

This work is published at Usenix Security 2018 under the title "DATA – Differential Address Trace Analysis: Finding Address-based Side-Channels in Binaries" by Samuel Weiser, Andreas Zankl, Raphael Spreitzer, Katja Miller, Stefan Mangard, and Georg Sigl. The paper can be downloaded here.