3.5.2 ASM Super Mutants

3.5.2.1 asm-super-mutant Overview

asm-super-mutant software objects are designed to provide the benefits of super-mutant to assembly programs. Its primary advantage is the ability to evaluate the fitness of large numbers of variants of a given target function, in a single process, in a minimal amount of time. Avoiding the per-process overhead in fitness evaluations results in orders-of-magnitude improvements of efficiency.

The asm-super-mutant has been tested with at&t and Intel syntax and for nasm (Intel) and gas (at&t) assemblers. Like asm-heap, it won’t work for arbitrary macro-heavy assembler code.

The asm-super-mutant derives from an asm-heap and also contains the super-mutant methods.

The asm-super-mutant initially contains a complete program executable (initialized from an asm format file). In addition it contains a specification of a target function within the overall program. The target function (specified either by name or as start and end addresses) is used to mark a range of lines within the overall program (returned by CREATE-TARGET).

Like a super-mutant, the asm-super-mutant maintains a collection of mutants, each one being an instance of the asm-heap software object. Each mutant is a variant of the target function.

3.5.2.2 Fitness Evaluation

To perform fitness evaluation, the asm-supermutant performs the following steps:

• The mutants are combined into a single assembly file (.asm), which also includes the data sections and declarations necessary to be able to assemble. Every mutant is given a unique label (variant_0, (variant_1, ... variant_n), and those labels are exported.
• Input/output data, see see I/O File Format, is appended to the asm file, and is used to determine fitness of each variant. A set of I/O data (memory and register contents) is provided for each test run of the target function.
• The .asm file is assembled with nasm.
• A C harness file (asm-super-mutant-fitness.c), which runs and evaluates variants, is compiled and linked to the compiled object file. The C code provides functions to set up each test, execute each variant, calculate the variant’s fitness and aggregate results. Currently the fitness is set to the number of executed instructions as collected by the linux Performance Application Programming Interface (papi) (http://icl.utk.edu/papi/) using the PAPI_TOT_INS event. The harness contains some sandboxing code to handle differences in execution address of the original test runs and the fitness runs, manage heap memory pages, and trap and handle segment violations and function crashes.
• Each variant is assigned an array of fitness results, with each item in in the array representing the number of instructions required to execute the function on a given test run (i.e., I/O pair). If the variant did not properly pass the tests (I/O data did not match) then maxint is assigned as the fitness variable for that test run (since smaller is better, this is the worst possible fitness).
• The fitness harness writes an array of all test results for all variants to the *standard-output* stream.
• The compiled/linked fitness executable is executed by the fitness test and the results (written to *STANDARD-OUTPUT*) are parsed and stored in Lisp data structures (as an array of arrays). This is cached on the asm-super-mutant instance, and can be obtained with the fitness method.

3.5.2.3 Tool Dependencies

The asm-super-mutant currently depends upon:

• Nasm to assemble the generated fitness program
• Clang (version 6 or later) to compile and link the fitness program.
• Assembly code or a high quality lifter (e.g., GrammaTech’s CodeSurfer for Binaries) to disassemble an original binary program.
• A method of collecting binary I/O pairs from a series of dynamic tests in the format described below, see I/O File Format

The asm-heap, which is the basis for asm-super-mutant and all its variants, uses Intel-format assembly code (Nasm-compatible). In the near future we are planning to switch to at&t assembler syntax and to replace Nasm with a more efficient assembler.

3.5.2.4 I/O File Format

The file is ascii. In internal tests it s generated using the ibm pin tool to observe the execution of a binary program on a test suite.

An I/O file contains 1 or more test runs, and each test run comprises 2 sections: Input Data and Output Data.

The format of Input Data is identical to Output Data, except that the set of registers that are included may differ.

Each section (Input Data or Output Data) contains a section of register lines, followed by a section of memory lines.

In the register section, the values of all significant registers are specified, one per line. This includes general-purpose registers (gpr) i.e. rax rbx, etc. followed by floating-point registers ymm0-15.

Following the registers are values of relevant memory addresses. These include any memory addresses read or written by the function being tested. If the function depends on a global variable for instance, it will be included.

In the first section (registers) each line contains:

• The name of the register, followed by the bytes in big-endian order,
• The register name is separated from the bytes by whitespace, but any other whitespace on the line should be ignored.

For example, the line,

    %rax    00 00 00 00 00 00 01 00

indicates that register rax should contain the value 256.

For the general-purpose registers rax, rcx, rdx, rbx, rsp, rbp, rsi, rdi, r8, r9, r10, r11, r12, r13, r14, and r15, all eight bytes will be explicitly included on the line. For the simd registers ymm0-ymm15, all 32 bytes will be explicit.

Memory would be specified with one 8-byte long per line, in big-endian order, consisting of an address, followed by a mask indicating which bytes are live, followed by the bytes themselves. The mask would be separated from the address and bytes by whitespace, but again any other whitespace on the line should be ignored.

For example, the line,

    00007fbb c1fcf768   v v v v v v v .   2f 04 9c d8 3b 95 7c 00

indicates that the byte at address 0x7fbbc1fcf768 has value 0x00, the byte at 0x7fbbc1fcf769 has value 0x7c, and so forth (big-endian order). Note that bytes 0x7fbbc1fcf769-0x7fbbc1fcf76f are live (indicated with "v") while 0x7fbbc1fcf768 is not (indicated with ".").

3.5.2.5 Components

asm-super-mutant software object consists of:

• The asm-heap, which is typically based on a file of assembly source code. The asm-super-mutant object contains the whole original binary application (in assembler source format).
• Input/output specifications, in a specific file format as generated using the Intel monitoring application and our Python scripts
• Data object original addresses ("sanity file").
• Function boundary deliminators which determines the target of the mutation and evaluation.

Note that the struct input-specification is a bit of a misnomer as it is used here for both input specification and output specification (their formats are identical so we use the same struct for both).

super-mutant slots:

• mutants will contain a list of asm-heap objects.
• super-soft caches a combined asm-heap representing the output fitness program.
• phenome-results caches the results obtained from calling the phenome method.

3.5.2.6 Current Limitations

• Functions which use floating point data as input or outputs will not evaluate correctly. The fitness file that is generated does not yet handle ymm0-ymm15 registers, which are used to pass floating point values in x86_64 binaries.
• Currently only leaf functions (functions which do not call any other functions) are supported.
• The fitness test program does not do full sandboxing. It does protect against segment violations (those will typically result in a +worst-c-fitness+ rating) but a function variant could potentially write on other code or data without triggering a segment violation, and this will not get trapped. When that happens it will possibly invalidate further fitness tests, or cause the whole fitness program to crash, resulting in all variants to come back as +worst-c-fitness+.

3.5.2.7 Installing PAPI on Ubuntu

Fitness evaluation requires the PAPI component and the Linux Perf functionality. Building the fitness evaluation program (on the fly during fitness evaluation) requires a C program to compile and link to PAPI. This also requires a .h file to compile.

To install papi:

sudo apt-get install papi-tools

To install perf:

    sudo apt-get install linux-tools-common linux-tools-generic linux-tools-`uname -r`

Perf requires system permission to run. In linux, the value in /proc/sys/kernel/perf_event_paranoid should be set to 1 (Disallow cpu event access by users without CAP_SYS_ADMIN). This is typically set to 3 (maximum paranoia) by default.

This can be accomplished with the following: sudo sh -c ’echo 1 >/proc/sys/kernel/perf_event_paranoid’ sudo sysctl -w kernel.perf_event_paranoid=1 You may need to use: sudo sh -c ’echo kernel.perf_event_paranoid=1 > /etc/sysctl.d/local.conf’ and then reboot for it to take effect.

It’s also a good idea to turn off randomizing of address base (to get more consistency): sudo sh -c ’echo 0 >/proc/sys/kernel/randomize_va_space’ sudo sysctl -w kernel.randomize_va_space=0 sudo sh -c ’echo kernel.randomize_va_space=0 >> /etc/sysctl.d/local.conf’

To get necessary include (.h) file for compiling C harness with PAPI (needed to perform fitness evaluation):

sudo apt-get install libpapi-dev

Then you should be able to enter

papi_avail

and see a list of available PAPI events. asm-super-mutant requires the use of the PAPI_TOT_INS event (total number of instructions executed). After installation, the PAPI library should be found in one of these locations: /usr/lib/x86_64-linux-gnu/libpapi.so /usr/lib/libpapi.so.5.6.1