GenProg: Evolutionary Program Repair
- Author: Claire Le Goues
- Modified by: Jeremy Lacomis
- Contact: firstname.lastname@example.org, email@example.com
- Date Created: July 11, 2008
- Date Modified: June 3, 2017
Current version of GenProg: 3.2
This README contains a trail-map for the use and extension of "repair", used for the GenProg experiments that appear in ASE 2013 (and others, and certainly all results thereafter, at least for now).
This README describes the use of GenProg v3.2, a.k.a. "repair." Previous versions exist and are described elsewhere. These instructions are very similar to those associated with previous versions of repair. Command line options should work as they did previously; older READMEs from previous releases contain detailed explanations of the relavent options.
These instructions primarily address the repair of C programs using the standard
genetic algorithm. Other search strategies and language front-ends exist. In
the interest of expediency, I am focusing on the type of repair I understand the
best and for which results are appearing soonest. Many of these instructions
translate directly to different language front-ends, however, so you should be
able to figure out ASM/ELF level repair pretty trivially if you understand
C-level repair. Previous READMEs advise contacting Eric Schulte
(firstname.lastname@example.org) for questions about neutral-space search or
ASM/ELF-level repair, but the ASM representation has completely changed. For
questions about ASM repair, you should email Jeremy Lacomis
(email@example.com). The README.md file in the
directory has changed to reflect the new ASM code.
These instructions include mention of how to compile for shader repair, but I unfortunately do not know how to run those experiments. Email Wes for pointers to who to ask (firstname.lastname@example.org).
Refer to the README associated with the benchmarks for information and examples regarding the use of modify/repair on particular examples.
Caveat 0: Read the entirety of this README before diving into a particular benchmark because I do not repeat instructions applying to all experiments in the benchmark-specific READMEs.
Caveat 1: GenProg operates on pre-processed code, meaning that the generated patches are sometimes non-obvious. Compare pre-processed code to original code to get a handle on what is going on.
Caveat 2: These instructions are not comprehensive, for which I apologize. repair has a huge number of command-line options and implemented behaviors. I've tried to include enough info to get you started.
- Benchmark program tarballs
If you'd like to use the tarballs associated with the repair scenarios we ran for ICSE 2012 (we used similar scenarios but with different parameters for GECCO 2012) and ASE 2013 "out of the box", you will need to use them with the VM images we provide, as they assume a certain directory structure. Check out the instructions associated with the disk image we provide on genprog.cs.virginia.edu on how to set up the VirtualBox image.
The genprog prototype assumes bash scripting and standard utilities; Windows most likely requires cygwin. Some number of experiments can be performed in OS X, with some extra legwork (Jeremy's note: the original version of this README mentions that compiling CIL for OS X is challenging, but I have not have much trouble with version 1.7.3)
Ensure that sh is symlinked to bash, not dash (as is the default on Ubuntu), on your machine. (Jeremy's note: As of 2017 I'm not sure this matters any more)
Our prototype is written in OCaml. It should work for releases starting from at least 3.09.3; the most recent version of OCaml is 4.04.x. Our code has been shown to work with version 4.02.3, but it should work with the latest versions as well.
opam install cil
If you install CIL using opam, make sure that the CIL environment variable isn't set and move on the step 2. If you choose to skip opam, the following instructions should work. Make sure that you have the OCaml compiler, perl, and ocamlfind installed and run:
wget http://downloads.sourceforge.net/project/cil/cil/cil-1.7.3.tar.gz tar xvzf cil-1.7.3.tar.gz cd cil-1.7.3 ./configure make make cillib export CIL=`pwd` # see explanation below cd ..
make cillibis the important part, so if
makechokes, try just
Set the environment variable CIL to point to whereever cil.spec ends up, or put it in your shell startup script:
Claire notes: I have had trouble getting later versions of CIL and/or OCaml to build CIL in native code (producing .cmx and .cmxa). A hack solution to this is to put
NATIVECAML := 1somewhere near the top of the Makefile, unguarded by any ifdefs.
Jeremy notes: I haven't had any problems with this, so it might not be a problem with newer versions of CIL.
The included cil-cg.tar.gz tarball is a version of CIL with extensions to support the parsing of OpenGL shaders. Compile in the same way as you do for CIL, change the CIL variable, make clean, export USE_PELLACINI=true, and re-make repair to use it. (Jeremy notes: I think this version of CIL is based off of 1.3.7, so it might not work any more.)
Once CIL is installed and the environment variable set,
makein the genprog-code/src directory should do the trick. Make sure the
OCAML_OPTIONSline that points to the obj directory for CIL is referencing your distro (that is, change
x86_DARWINif you're on OS X).
The build process will produce several artifacts:
repair: the main GenProg repair program
nhtserver: the server for the networked hash table (optional)
distserver: the server for the distributed GA search (optional)
libelf.o: utilities for elf manipulation
Additional build targets are:
doc: requires ocamldoc, generates html documentation on the API (useful if you want to understand or extend the code) in
testsuite: runs the tests in
test/. The testsuite is a work in progress and thus I make no guarantees about its functionality; this documentation will be updated as it is.
General "repair" roadmap
I will first outline the default (virtually all behaviors may be overridden) behavior of repair as run fresh on a new C program, assuming all goes well:
sanity check: repair will compile the program and run it on all positive and negative test cases to check that the behavior is as expected (i.e., compiles, passes the positive test cases, fails the negative test cases).
If no path files are found and no other localization strategy is specified, repair will instrument the program for coverage information and compile and run the instrumented program on the test cases to generate positive and negative paths for localization.
Repair then generates an initial population and computes the fitness of all variants by running them against all positive and negative test cases.
It then iterates until either the number of generations exceeds the specified/default limit or until a repair is found.
If a repair is found, the source code for that variant will be printed to disk either in
repair.c(depending on whether the source code is one file or many). If minimization is specified (not by default), the repair will then be minimized, and related files will be output Minimization_Files/.
repair produces the following artifacts by default:
program.cache: caches the representation with localization information. If a cache is found in the directory, and repair is not told otherwise, it will load the repair from this cache. By default this skips the localization/coverage step and the sanity step.
repair.cache: the test cache
coverage.path.neg: the path files used for localization.
repair.debug.Nwhere N is the seed used for the random-number generator. All output from repair is sent both to standard out and
If the caches and/or paths are found on a run on the program, they will be used.
You can turn off this loading behavior with
--regen-paths (if you're using path-based
localization but want to regenerate them). You can also specify alternative
names for the repair cache file using
Thus, to run repair on any program, at the very least, you will need:
- (C) Source code. This may be in one or many files, but it must be preprocessed.
- compile script(s)
- test script(s)
You might also want:
- localization info: there are several options here; check the output of
./repair --help, in particular near
--fix-schemefor options and how to use them.
I highly recommend that you stop between acquiring the program source and the compile and test scripts and make sure that you can run them manually first. Check the permissions on those scripts in particular as they must be executable.
The test directory also contains
gcd-test/, an example repair scenario for the
gcd program; you may find it useful as a reference.
3.1. Input program
Relevant command-line options:
--rep X(optional but encouraged)
--prefix X(necessary for multi-file repair)
You need the source code of a program with a deterministic bug that you can expose with test cases (one or many).
repaircan operate on either a single C file or multiple C files, but they will need to be preprocessed. There are several possibilities for where to get such preprocessed code:
If you're running a scenario in a VM as downloaded from the genprog website, the preprocessed code is included and does not need to be regenerated. The other benchmarks from previous papers include in their READMEs the mechanisms we used to generate the preprocessed source; you will almost certainly need to regenerate them as preprocessed source tends to be machine-specific.
The original source code sometimes suffices (only true for the smallest of programs, such as GCD).
A single source file can often be preprocessed by passing
gcc -E uniq.c > uniq.i
uniq.iis the preprocessed source version of
If a benchmark involves modifying one file or module of a larger program (e.g., openldap), the preprocessed source can be obtained by hijacking the benchmark's original build process. Build the original benchmark source, search the compiler output for the line that compiles the file you need, copy it,
cdinto the appropriate directory, add
--save-tempsas a flag to gcc in the line, producing
foo.iin that directory, where
foo.iis your input source code.
If a benchmark consists of more than one source file and repair is to be run on the entire (combined) program (e.g., nullhttpd), use CIL to "combine" the source code into one file (turning all the nullhttpd source code into, for example,
httpd_comb.c). To do this, use
gcc. For nullhttpd:
cd nullhttpd-0.5.0/src make CC="/home/weimer/src/cil/bin/cilly --merge --keepmerged"
This will generate
Specifying the program
The program is specified with
--program. By default, repair will try to figure out what kind of program you're trying to repair, be it C, asm, etc, based on the argument passed to
--program. You can be explicit by adding the
--rep file_typeargument; this switch provides a number of options even within one language family (cilpatch vs cilast, for example; patch is the default). The
--repargument is important if you are using multiple C files because repair uses the extension of the argument passed to
--programto automatically guess the type of program under repair, and it might get confused if given a .txt absent further instructions.
In the single-file case, you specify the source code with the
--programcommand line option.
In the multi-file case: put all preprocessed files in one directory. List all files, one per line, in a text file; do not include the top-level directory in which they are placed. Specify
For example, if you have
c.i, put them all in one directory:
> ls preprocessed/ a.i b.i c.i
Create a text file, e.g., source.txt:
> cat source.txt a.i b.i c.i
To repair, include the following flags:
--program source.txt --rep c --prefix preprocessed
--compiler compiler-name --compiler-command "compilation command"
compilation is governed by the compiler command and the specified compiler. The default compiler command is:
"__COMPILER_NAME__ -o __EXE_NAME__ __SOURCE_NAME__ __COMPILER_OPTIONS__ \ 2>/dev/null >/dev/null"
where each of the
__KEYWORDS__ is replaced at each compilation with the
associated concrete instance.
__COMPILER_NAME__ is "gcc" by default. You can
change either just the compiler name (
--compiler) or the entire command
--compiler-command) to be whatever you want, bearing in mind that the key
words in the default are the only ones currently available. Feel free to add
your own by modifying the source code if you want, though we have yet to need
to. Anything more complex than
gcc -o foo foo.c can usually be accomplished
with a shell script; examples appear in the ICSE 2012 tarballs. But, for
example, if you have a compile.sh that you've written to do anything more
gcc -o foo foo.c, you might say:
--compiler "./compile.sh" --compiler-command "__COMPILER_NAME__ __SOURCE_NAME__"
Relevant command-line options:
--test-script script-name --test-command "test command"
Testing is governed by a similar mechanism. The default test script is
The default test command is:
"__TEST_SCRIPT__ __EXE_NAME__ __TEST_NAME__ __PORT__ __SOURCE_NAME__ \ __FITNESS_FILE__ 1>/dev/null 2>/dev/null"
It may be modified as with the compiler command above, with slightly different key words. It will almost certainly need at least
__TEST_NAME__. The test names are "
p#" and "
#is the number of the test case and
pis for positive test cases and
nis for negative test cases. You may also specify
s, for "single test case" which should write the fitness as a (potentially list of) floating point number(s) to the fitness file. This is less common and used primarily for graphics-shader based experiments.
Suggestion: your test scripts should likely include commands like
ulimitor another utility to limit runtime and memory consumption for your program. We have a small C utility called
limitthat we use often use for the purpose of avoiding infinite loops, but any similar mechanism will work as well.
--pos-tests N --neg-tests N --fitness-in-parallel N --sample X
--neg-testsspecify the number of positive and negative tests respectively.
--fitness-in-parallelis > 1, more than one test case will be run in parallel.
--sample Xsets the sample size of the positive test cases. < 1.0 (the default) uses sampling.
There are a number of other options relevant here (
--samp-strat, for example); consult
./repair --helpfor more.
Other command-line options
repair has a large number of other command-line options controlling setup, GA
parameters, search type, minimization...the works. You may specify them either
at the command line or using a config file (or both! They are parsed in order,
so the later ones take precedence if there are repeats). I highly recommend
downloading the tarballs of the experimental setup for the ICSE 2012 benchmark
set and consulting the configuration files associated with each scenario to get
an idea of what they are, or calling
./repair --help I have tried to make
their descriptions somewhat indicative, and thus I omit additional instructions
here for the sake of brevity.
I would recommend at least using
--seed X for each run, which makes everything
CAVEAT: as of 5/10/12, I have not yet regenerated the configuration files for those benchmarks to make use of the refactored version of the command line options. Thus, the scenario tarball config files contain a number of deprecated options. HOWEVER: repair handles a large number of deprecated options, so you can still run repair on those scenarios, just be mindful that not all of those options are currently available in those exact forms. I will fix this soon. (Jeremy notes: I don't know if this has been fixed as of 6/3/17)
- Misc observations
Permissions are funny. Sometimes they are set so that
sh test.sh executes but
./test-good.sh gives a
permission denied. Check this, and then use
--seed flag to specify the random seed for reproducible runs.
If a repair is found, the code output to
repair.c is not the minimized repair.
Minimization can be performed on the initial repair by passing
in the config file.
--continue flag bypasses modify's default behavior to quit when it finds
the first fixed variant.