Recent Work – evolving ELF files

1. apply our technique to a wider range of programs
   • anything compiling to ELF files
   • remove need for source code
2. levels of representation
   • C level (compiler and linker)
   • at the ASM level (linker)
   • binary level (no linker, but respect instruction boundaries)
   • at the byte level (just manipulate raw bytes)

Too many Libraries!

libelf

nice tutorial, poor community, not robust

elfsh

targets virus writers, hyperbole and error prone

libbfd

poor documentation, strong community, doesn't support my use case

Finally just wrote my own using the ELF standard. Much easier.

To evolve variants we need to edit the code living in .text.

Taking a simple C file

main(){puts("hello world");}

We can load it up and check the magic number.

(elf-p "hello")

Then read it into an elf data structure.

(setf *elf* (read-elf "hello"))

And look at the top-level elf header.

(show-it (header *elf*))

An ELF file has two internal tables, and two instantiations.

table	instantiation
section table	binary executable on disk
program table	memory image during execution

looking at the program table

(mapcar #'show-it (program-table *elf*))

looking at the layout of the binary file both on disk

(show-file-layout *elf*)

and in memory

(show-memory-layout *elf*)

We can investigate the binary contents of the .text section.

(let ((instrs (subseq (data (named-section *elf* ".text")) 38 42)))
  (mapcar (lambda (el) (format nil "0x~x" el))
          (coerce instrs 'list)))

We can also update the value of this section

(setf (aref (data (named-section *elf* ".text")) 40) #xc3)

And when we write the altered file out to disk

(write-elf *elf* "hello2")

The resulting file still works

chmod +x hello2
./hello2
echo $?

I've implemented the following mutation operators on this framework.

• Delete

  (defmethod rm ((asm asm))
    (let ((rm-point (place asm)))
      (setf (aref (genome asm) rm-point) nop)
      (setf (ops asm) (cons (cons :rm rm-point) (ops asm)))))
  

• Swap

  (defmethod swap ((asm asm))
    (let* ((a (place asm)) (a-instr (aref (genome asm) a))
           (b (place asm)) (b-instr (aref (genome asm) b)))
      (setf (aref (genome asm) a) b-instr)
      (setf (aref (genome asm) b) a-instr)
      (setf (ops asm) (cons (cons :swap (list a b)) (ops asm)))))
  

• Insert

  (defmethod insert ((asm asm))
    (let ((point (place asm)) closest-nop)
      ;; remove the nop closest to the inserted instruction
      (loop for n from 1 upto (max (- (length (genome asm)) point) point)
         until closest-nop
         do (let ((forward (+ point n)) (backward (- point n)))
              (cond
                ((and (> backward 0)
                      (equal (aref (genome asm) backward) nop))
                 (setf closest-nop backward))
                ((and (< forward (length (genome asm)))
                      (equal (aref (genome asm) forward) nop))
                 (setf closest-nop forward)))))
      (setf (genome asm)
            (let ((low  (min closest-nop point))
                  (high (max closest-nop point))
                  (copy (list (aref (genome asm) (place asm)))))
              (concatenate 'vector
                           (subseq (genome asm) 0 low)
                           (when (equal low point) copy)
                           (subseq (genome asm) low high)
                           (when (equal high point) copy)
                           (subseq (genome asm) (1+ high)))))
      (setf (ops asm) (cons (cons :insert (list point closest-nop)) (ops asm)))))
  

Which result in the following mutational robustness over the simple hello world program.

op	passed 1 test	passed 0 tests	script-error	timeout-error
:RM	530	0	470	0
:SWAP	305	0	693	2
:INSERT	1000	0	0	0