Automated Repair of Binary and Assembly Programs for Cooperating Embedded Devices

Created by W.Langdon from gp-bibliography.bib Revision:1.4496

  author =       "Eric Schulte and Jonathan DiLorenzo and 
                 Westley Weimer and Stephanie Forrest",
  title =        "Automated Repair of Binary and Assembly Programs for
                 Cooperating Embedded Devices",
  booktitle =    "Proceedings of the eighteenth international conference
                 on Architectural support for programming languages and
                 operating systems",
  year =         "2013",
  series =       "ASPLOS 2013",
  pages =        "317--328",
  address =      "Houston, Texas, USA",
  publisher_address = "New York, NY, USA",
  month =        mar # " 16-20",
  publisher =    "ACM",
  keywords =     "genetic algorithms, genetic programming, assembly
                 code, automated program repair, bytecode, evolutionary
                 computation, fault localisation, legacy software,
                 parallel distributed GP via SMS text",
  isbn13 =       "978-1-4503-1870-9",
  URL =          "",
  DOI =          "doi:10.1145/2451116.2451151",
  acmid =        "2451151",
  size =         "11 pages",
  abstract =     "We present a method for automatically repairing
                 arbitrary software defects in embedded systems, which
                 have limited memory, disk and CPU capacities, but exist
                 in great numbers. We extend evolutionary computation
                 (EC) algorithms that search for valid repairs at the
                 source code level to assembly and ELF format binaries,
                 compensating for limited system resources with several
                 algorithmic innovations. Our method does not require
                 access to the source code or build toolchain of the
                 software under repair, does not require program
                 instrumentation, specialised execution environments, or
                 virtual machines, or prior knowledge of the bug

                 We repair defects in ARM and x86 assembly as well as
                 ELF binaries, observing decreases of 86percent in
                 memory and 95percent in disk requirements, with
                 62percent decrease in repair time, compared to similar
                 source-level techniques. These advances allow repairs
                 previously possible only with C source code to be
                 applied to any ARM or x86 assembly or ELF executable.
                 Efficiency gains are achieved by introducing stochastic
                 fault localization, with much lower overhead than
                 comparable deterministic methods, and low-level program

                 When distributed over multiple devices, our algorithm
                 finds repairs faster than predicted by naive
                 parallelism. Four devices using our approach are five
                 times more efficient than a single device because of
                 our collaboration model. The algorithm is implemented
                 on Nokia N900 smartphones, with inter-phone
                 communication fitting in 900 bytes sent in 7 SMS text
                 messages per device per repair on average.",
  notes =        "gcc -S and objdump -d -j light weight sandboxing with
                 ulimit and chroot. OProfile

                 written in code AST == tree GP, ASM == assembler, ELF
                 == machine code binary.

                 ptrace slowdown 2400 fold. p326 'no evidence of
                 introduced bugs.'

                 p326 'distributed automated repair methods will be
                 necessary' 'Sandboxing is crucial'.",

Genetic Programming entries for Eric Schulte Jonathan DiLorenzo Westley Weimer Stephanie Forrest