ASLRA: ASLR Analyzer

During the development of the ASLR-NG we needed to measure the real entropy of the ASLR. Peter Busser wrote the paxtest tool, which is a nice an powerful tool but does not provide enough statistical information about the entropy provided by the ASLR. Then we decided to develop ASLRA.

Overview

ASLRA is a statistical tool specially designed to measure all the parameters that determine the quality of ASLR implementations. It is composed of two applications:

Sampler:

It is an application which generates millions of samples (address of mapped objects) and saves them in a raw data file.

The sampler is executed in the target system (the one to be analyzed). It launches thousands of processes to collect information about a set of given memory objects: Arguments, Stack, Heap, Exec, Libs, Hugepages, etc. The raw results are written to a file, which will later be processed.

The samples has been optimized to run as much samples as possible in parallel, which allows to collect enough samples to have representative results.

Analyzer:

Using the sampled raw file, the analyzer computes several statistical parameters: range, media, std deviation, individual byte entropy, Shannon entropy, flipping bits, etc. And provides graphical representation of the memory layout.

The output of the analyzer is a set of HTML pages that can be easily studied using a web browser. We have tried to make the interface very interactive and easy to understand.

Statistical parameters

Memory layout representation.

ASLR calculates the following parameters:

For each object:
1. Minimum, maximum and the range of the address.
2. Random bits (bits that change).
3. Shannon entropy (measured using 64 variable size bins).
4. Sum of Shannon entropy of individual bytes.
5. Number of lower bits that don't change (typically page bits).
6. Measured, estimated and percentage of error of:
  - Mean.
  - Median.
  - Mode.
  - Standard deviation.
7. Pearson Chi² test of uniformity (using multiple bins: 2^{5 .. 13}, 100 and 8263).
8. Plots of:
  1. Raw data.
  2. Cumulative distribution function (CDF).
  3. Histogram (using 100 bins).
  4. Individual byte histograms.
  5. Individual byte histograms of the result of dividing the address by 2.
9. Visualization of the memory layout, with the entropy.
The largest allocatable mmap object (using binary search on the target system).
Correlation matrix between all the objects.

Most of those parameters are of little help when the distribution is uniform. But depending on the shape of the distribution, some of them are key to understand it. For example, the "Individual byte histograms of the result of dividing the address by 2" plot is necessary to understand the aliasing that occurs in PaX 64 libraries.

The output

Since the output is plain HTML, you can analyze the result of current ASLR of some systems online. Next are two links to the output of the ASLR tool which compares three systems: Vanilla Linux, PaX and ASLR-NG.

[Linux↔PaX↔ASLR-NG 64-bit]

[Linux↔PaX↔ASLR-NG 32-bit]

Do the analysis yourself!

Note that the links above, show the real output of the real systems. Therefore, you can analyze by yourself the quality of the ASLR implementation on those systems.

On going work

The correlation matrix is a good statistical tool to measure "numeric" correlation, but it is not sensitive enough to correlations caused by ranges of bits (as the case of huge pages) or when the correlation is caused by the sum of a small random number.

We are working on the co-entropy between objects. It is a mathematical challenge due to the huge range of the distributions in 64-bit systems, which makes it hard to estimate the conditional entropy when the number of samples is reduced (just a few millions out of 2⁴⁷).

Also, documentation is still pending.

Ismael Ripoll
Category: Assistant Professor (Titular de Universidad) Phone: +34 963 879 218 / Internal: 79218 / Fax+34 963 877 579 Email: iripoll@upv.es Location: Room 3N12, Building 1G, Universitat Politècnica de València.