Skip to content

Latest commit

 

History

History
143 lines (97 loc) · 9 KB

Manual.md

File metadata and controls

143 lines (97 loc) · 9 KB

Manual

f1x [ɛf-wʌn-ɛks] is a test-driven patch generation engine for C/C++ programs. It automatically finds and fixes software bugs by analyzing behaviour of passing and failing tests. f1x aims to be efficient, robust and easy-to-use.

Search space

Search space is the set of syntactical changes that can be generated by a program repair system. The search space of f1x is defined by the following transformation schemas:

  1. expression: modifying side-effect free expressions (conditions, RHS of assignments, return arguments);
  2. refinement: appending || expr and && expr to conditions;
  3. assignment: inserting assignment statements;
  4. guard: inserting if-guards for break, continue, function calls;
  5. initialization: inserting memory initialization;
  6. function: replace a function call with another similar function call.

f1x expression synthesizer is bit-precise; it supports all builtin (C99) integer types and pointers.

Test-equivalence analyses

f1x performs search by applying and testing candidate patches. Since the search space of f1x includes a huge number of program changes, it is inefficient to test each change individually. In order to address this, f1x implements several test-equivalence analyses that help to avoid redundant test executions:

  1. vteq: value-based test-equivalence analysis (for side-effect free program expressions).
  2. [currently unsupported] dteq: dependency-based test-equivalence analysis (for assignment synthesis).

Prioritization

Search space prioritization can be thought of as a function that assigns lower cost to better patches. f1x support two kinds of prioritization: static and dynamic. In static prioritization, the score of each patch is known before testing and therefore the search algorithm explores candidates in the order defined by the cost function (starting from candidates with lower cost) and stops immediately after a plausible patch is found. In dynamic prioritization, the score of each patch is known only after testing and therefore the search algorithm has to explore the entire search space in order to find a patch with the lowest cost.

f1x supports the following static prioritization strategies:

  1. syntactic-diff: minimize syntactic change (patches that are syntactically closer to the original program are assigned lower cost).

f1x supports the following dynamic prioritization strategies:

  1. semantic-diff: minimize semantic change (patches that produce execution traces closer to the execution traces of the original program are assigned lower cost).

Usage

In order to repair a program, f1x requires a special build configuration and an interface to the testing framework.

Project

f1x operates on projects, where a project is a directory that contains all source files, tests, build scripts, subdirectories, etc.

It order to let f1x transform and compile your application, you need to substitute C compiler in your build system with the f1x-cc tool. For instance, autotools-based projects require

  • configuring using f1x compiler wrapper (e.g. CC=f1x-cc CXX=f1x-cxx ./configure)
  • removing binaries before executing f1x (e.g. make clean)
  • ensuring that the build command uses the compilers from CC and CXX environment variables (e.g. use make with the -e option)

f1x needs to be able to execute an arbitrary test to identify if this test passes or fails. To abstract over testing frameworks, f1x uses the following entities:

  • A set of unique test identifiers (e.g. "test1", "test2", ...).
  • A test driver executable that accepts a test identifier as the only argument, runs the corresponding test, and terminates with zero exit code if and only if the test passes. The test driver is executed from the project root directory.

When executing tests, f1x appends a path to its runtime library (libf1xrt.so) to the LD_LIBRARY_PATH environment variable. Therefore, the testing framework should not overwrite this variable.

The following analyses implemented in f1x require additional runtime instrumentation: dteq analysis needed for assignment synthesis, localization of suspicious files, and dynamic patch prioritization. To enable this, the testing framework has to execute the application binary using a command stored in F1X_RUN environment variable, if it is defined. For tests written in Bash, this can be achieved by simply placing $F1X_RUN in front of the program execution command:

assert-equal () {
    diff -q <($F1X_RUN $1) <(echo -ne "$2") > /dev/null
}

case "$1" in
    test1)
        assert-equal "./program 1 2" '1\n'
        ;;
esac

You may choose not to instrument tests with F1X_RUN if you (1) disable assignment synthesis (--disable-assignment option), (2) manually specify suspicious files (--files option), (3) do not use dynamic patch prioritization.

By default, f1x compiles the project using gcc/g++. The compilers can be redefined through F1X_PROJECT_CC and F1X_PROJECT_CXX environment variables. If the project compiler is clang, it is recommended to switch from gcov to llvm-cov using --enable-llvm-cov option.

Side effects

Warning! f1x executes arbitrary modifications of your source code which may lead to undesirable side effects. Therefore, it is recommended to run f1x in an isolated environment.

The f1x tool accepts user options, executes the repair algorithm, and terminates with the following exit codes:

  • 0 if a patch is found
  • 122 if negative tests are provided but no patch is found
  • 123 if no negative tests are provided
  • an arbitrary non-zero code in case of errors

Apart from that, f1x produces the following side effects:

  • prints log messages on the standard error output
  • saves generated patch(es) in the current directory (or the path specified by --output)
  • saves intermediate data in a temporary directory (the path can be found in log messages)
  • transforms/builds/tests the provided project

f1x operates directly on the provided source tree. Typically, it is safe to execute f1x consequently on the same copy of the project (without make clean), however idempotence cannot be guaranteed. After f1x terminates successfully, it restores the original source files, but does not restore files generated/modified by the tests and the build system. If f1x does not terminate successfully (e.g. by receiving SIGKILL), the source tree is likely to be corrupted.

Command-line interface

The f1x tool must be executed from the project root directory. All subcommands used by f1x (e.g. compilation, test execution) are also executed from the project root directory. All specified filesystem paths must be either absolute or relative to the project root directory.

The following arguments are mandatory:

  • test-suite (--tests option);
  • test execution timeout (--test-timeout option);
  • test driver (--driver option).

The following summarizes main supported options:

  • -t [ --tests ] ID... - the list of unique test identifiers.
  • -T [ --test-timeout ] MS - the test execution timeout in milliseconds.
  • -d [ --driver ] PATH - the path to the test driver. The test driver is executed from the project root directory.
  • -f [ --files ] PATH... - the list of suspicious files (that may contain a bug). f1x allows to restrict the search space to certain parts of the source code files. For the arguments --files main.c:20 lib.c:5-45, the candidate locations will be restricted to the line 20 of main.c and from the line 5 to the line 45 (inclusive) of lib.c.
  • -l [ --localize ] NUM - the number of source files to localize. If omitted, 10 files are localized.
  • -b [ --build ] CMD - the build command. If omitted, make -e is used. The build command is executed from the project root directory.
  • -o [ --output ] PATH - the path to the output patch (or directory when used with --all). If omitted, the patch is generated in the current directory with the name f1x-<TIME>.patch (or in the directory f1x-<TIME> when used with --all)
  • -a [ --all ] - generates all plausible patches.
  • -c [ --cost ] FUNCTION - the cost function used to prioritize patches. If omitted, syntactic-diff is used.
  • -v [ --verbose ] - enables extended output for troubleshooting.
  • -h [ --help ] - prints help message and exits.
  • --version - prints version and exits.

Run f1x --help to view the full list of available options.

Related publications

Angelix: Scalable Multiline Program Patch Synthesis via Symbolic Analysis. [pdf]
S. Mechtaev, J. Yi, A. Roychoudhury.
International Conference on Software Engineering (ICSE) 2016.

DirectFix: Looking for Simple Program Repairs. [pdf]
S. Mechtaev, J. Yi, A. Roychoudhury.
International Conference on Software Engineering (ICSE) 2015.

SemFix: Program Repair via Semantic Analysis. [pdf]
H.D.T. Nguyen, D. Qi, A. Roychoudhury, S. Chandra.
International Conference on Software Engineering (ICSE) 2013.