runtime/tools/dartfuzz/minimize.py

#!/usr/bin/env python3
# Copyright (c) 2019, the Dart project authors.  Please see the AUTHORS file
# for details. All rights reserved. Use of this source code is governed by a
# BSD-style license that can be found in the LICENSE file.
#
"""
This script minimizes a program generated by dartfuzz.dart.
"""

import argparse
import multiprocessing as mp
import re
import shlex
import subprocess

STATEMENT_MASK_LINE = 0
STATEMENT_NUMBER_LINE = 1
EXPRESSION_MASK_LINE = 2
EXPRESSION_NUMBER_LINE = 3


class MaskGen(object):
    """
    Generates bitpatterns of <nbits> bits which indicate which
    statements or expressions should be masked when passed as the
    --smask or --emask parameter to dartfuzz.dart.
    The patterns are generated in the following manner:
    11111111111111111111111111111111
    11111111111111110000000000000000
    00000000000000001111111111111111
    11111111111111111111111100000000
    11111111111111110000000011111111
    11111111000000001111111111111111
    00000000111111111111111111111111
    ...
    If the error persists with a given a pattern it is stored in the
    parameter <mask>.
    """

    def __init__(self, nbits, mask):
        # Mask bitlength.
        self.nbits = nbits
        # Mask determining which statements or expressions to skip.
        self.mask = mask
        # Current mask modification start index.
        self.convolution_idx = 0
        # Max mask with all bits set to 1.
        self.max = (1 << (nbits + 1)) - 1
        # Current number of bits set in the mask modification mask.
        self.nbitsVar = int(nbits)
        # Current mask modification mask.
        # This will be folded over the current value of self.mask
        # starting from 0.
        self.filter_mask = (1 << self.nbitsVar) - 1
        # All the masks already tested.
        self.tested = set()
        self.gen_new_mask = False

    def __iter__(self):
        return self

    def __next__(self):
        return self.next()

    # Update the set of tested masks.
    # This is used to keep track of tested masks that did not produce a crash.
    def update_tested(self, new_mask):
        self.tested.add(new_mask)

    # Update the current mask with the new mask that produced a crash.
    # Note: We assume that if mask
    # 11110000 produces a crash and
    # 00000011 produces a crash that
    # 11110011 will also produce a crash.
    # This might not be true for some cases.
    def update_mask(self, new_mask):
        new_mask = (self.mask | new_mask) & self.max
        self.mask = new_mask

    # Count the bits of the current mask.
    # More bits mean more statements omitted, so this is used
    # to determine the quality of the current mask.
    def count_bits(self):
        return bin(self.mask).count('1')

    def inc_var(self):
        self.convolution_idx = 0
        self.nbitsVar = self.nbitsVar >> 1
        self.filter_mask = (1 << self.nbitsVar) - 1
        return self.filter_mask == 0

    def stop(self):
        if self.convolution_idx >= self.nbits and self.inc_var() > 0:
            # Check if the last run generated a new mask.
            if self.gen_new_mask:
                # Restart mask generation from beginning.
                self.nbitsVar = self.nbits >> 1
                self.inc_var()
                self.gen_new_mask = False
                return False
            print("STOP")
            return True
        return False

    def next(self):
        while not self.stop():
            # Generate a new mask according to the mask generation algorithm.
            new_mask = (self.mask |
                        (self.filter_mask << self.convolution_idx)) & self.max
            # Update the counter variable for the mask generation algorithm.
            self.convolution_idx += self.nbitsVar
            # If the new_mask has new bits and has not been tested yet.
            # We need to check both because only masks that produce an
            # error are merged into self.mask.
            if new_mask != self.mask and \
                new_mask not in self.tested:
                # Add new mask to the set of tested masks.
                self.tested.add(new_mask)
                # Mark that we generated a new mask on this run.
                self.gen_new_mask = True
                # Return the new mask to be tested.
                return new_mask
        raise StopIteration()


# Generate a Dart program for the given statement (smask) and
# expression (emask) masks. Dartfuzz parameters for seed, ffi and
# fp are static and therefore contained in the dartfuzz_cmd parameter.
def generate_dart(dartfuzz_cmd, dart_test, smask, mask, do_expr):
    if do_expr:
        # Minimizing expressions.
        cmds = shlex.split(dartfuzz_cmd) + [dart_test] + \
            ['--mini', '--smask', '%d' % smask, '--emask', '%d' % mask]
        p = subprocess.Popen(cmds, stdout=subprocess.PIPE)
    else:
        # Minimizing statements.
        cmds = shlex.split(dartfuzz_cmd) + [dart_test] + \
            ['--mini', '--smask', '%d' % mask]
        p = subprocess.Popen(cmds, stdout=subprocess.PIPE)
    p_stdout, p_stderr = p.communicate()
    if p.returncode != 0:
        raise RuntimeError('Invalid return code on generate %d' % p.returncode)
    mask_new = 0
    if do_expr:
        mask_new = int(p_stdout.decode().splitlines()[EXPRESSION_MASK_LINE])
    else:
        mask_new = int(p_stdout.decode().splitlines()[STATEMENT_MASK_LINE])
    return mask_new


# Run the Dart program and check for error (by matching error_match_p).
def run_dart(dart_cmd, dart_test, error_match_p, timeout):
    cmd = ['timeout', str(timeout)] + shlex.split(dart_cmd) + [dart_test]
    p = subprocess.Popen(cmd, stderr=subprocess.PIPE, stdout=subprocess.PIPE)
    p_stdout, p_stderr = p.communicate()
    if error_match_p.search(p_stdout.decode()) or \
        error_match_p.search(p_stderr.decode()):
        return True
    if p.returncode != 0:
        print("Warning: error return code %d" % p.returncode)
    return False


# Run multiple tries of the given dart_cmd and check for errors by matching
# against error_match_p.
def run_dart_mp(dart_cmd, dart_test, error_match_p, tries, nthreads, timeout):
    if tries == 1:
        return run_dart(dart_cmd, dart_test, error_match_p, timeout)
    pool = mp.Pool(nthreads)
    results = [
        pool.apply_async(run_dart,
                         (dart_cmd, dart_test, error_match_p, timeout))
        for i in range(tries)
    ]
    worker_done = [False for i in range(tries)]
    while True:
        all_done = True
        for i, result in enumerate(results):
            if worker_done[i]:
                continue
            try:
                r = result.get(timeout=0.5)
                worker_done[i] = True
                if r:
                    pool.close()
                    pool.terminate()
                    pool.join()
                    return True
            except mp.TimeoutError:
                all_done = False
        if all_done:
            break
    pool.close()
    pool.join()
    return False


def minimize(dartfuzz_cmd,
             dart_cmd,
             dart_cmd_ref,
             dart_test,
             error_match1,
             error_match2,
             smask,
             emask,
             do_expr,
             verbose,
             tries,
             tries_ref,
             threads,
             timeout,
             print_every=32):
    # Run dartfuzz command once to get the total number of statements
    # and expressions in the generated program.
    # Output will look like this:
    # <Current Statement Mask>
    # <Number of Statements>
    # <Current Expression Mask>
    # <Number of Expressions>
    p = subprocess.Popen(
        dartfuzz_cmd + " --mini " + dart_test,
        shell=True,
        stdout=subprocess.PIPE)
    p_stdout, p_stderr = p.communicate()
    if do_expr:
        # Minimizing expressions.
        nstmts = int(p_stdout.decode().splitlines()[EXPRESSION_NUMBER_LINE])
        mask_gen = MaskGen(nstmts, emask)
    else:
        # Minimizing statements.
        nstmts = int(p_stdout.decode().splitlines()[STATEMENT_NUMBER_LINE])
        mask_gen = MaskGen(nstmts, smask)
    # Best mask found so far.
    min_mask = 0
    # Maximum number of statements or expressions masked.
    max_bits = 0
    # Count number of iterations.
    cntr = 0
    # Result of the last run.
    last_err = True
    # Compile pattern to match standard output and error for a string
    # identifying the crash.
    error_match_p1 = re.compile(error_match1)
    error_match_p2 = None
    if error_match2 is not None:
        error_match_p2 = re.compile(error_match2)
    for mask in mask_gen:
        if (verbose):
            print("Mask: %x" % mask)
        cntr += 1
        if cntr % print_every == 0:
            cntr = 0
            print("Best I could do so far is mask %d/%d" \
                  % (max_bits, nstmts))
            if do_expr:
                print(dartfuzz_cmd + " " + dart_test +
                      " --mini --smask 0x%x --emask 0x%x" % (smask, min_mask))
            else:
                print(dartfuzz_cmd + " " + dart_test +
                      " --mini --smask 0x%x --emask 0" % (min_mask))
        # The return value mask_new contains the actual mask applied by
        # dartfuzz. Due to nesting, masking one statement might lead to other
        # statements being masked as well; mask_new will contain this updated
        # mask.
        mask_new = generate_dart(dartfuzz_cmd, dart_test, smask, mask, do_expr)
        # Run generated Dart program and check for error.
        err = run_dart_mp(dart_cmd, dart_test, error_match_p1, tries, threads,
                          timeout)
        if err and verbose:
            print("Matched error 1 " + error_match1)
        err_ref = True
        if (dart_cmd_ref is not None) and (error_match_p2 is not None):
            err_ref = run_dart_mp(dart_cmd_ref, dart_test, error_match_p2,
                                  tries_ref, threads, timeout)
            if err_ref and verbose:
                print("Matched error 2 " + error_match2)
        if err and err_ref:
            # In case the mask used for generating the Dart program lead to an
            # error, update the mask generator accordingly.
            mask_gen.update_mask(mask)
            # TODO (felih): this line should be enough but there seems to be a
            # bug in dartfuzz.dart calculating mask_new.
            mask_gen.update_mask(mask_new)
            max_bits = mask_gen.count_bits()
            min_mask = mask_gen.mask
        elif last_err:
            # If the last run removed the error try the inverse.
            invMaskNew = mask_gen.mask | (mask_gen.max & ~mask_new)
            if invMaskNew != mask_gen.mask and \
                invMaskNew not in mask_gen.tested:
                if (verbose):
                    print("Mask: %x (i)" % invMaskNew)
                mask_new = generate_dart(dartfuzz_cmd, dart_test, smask,
                                         invMaskNew, do_expr)
                err = run_dart_mp(dart_cmd, dart_test, error_match_p1, tries,
                                  threads, timeout)
                if err and verbose:
                    print("Matched error 1 " + error_match1)
                err_ref = True
                if (dart_cmd_ref is not None) and (error_match_p2 is not None):
                    err_ref = run_dart_mp(dart_cmd_ref, dart_test,
                                          error_match_p2, tries_ref, threads,
                                          timeout)
                    if err_ref and verbose:
                        print("Matched error 2 " + error_match2)
                if err and err_ref:
                    mask_gen.update_mask(invMaskNew)
                    mask_gen.update_mask(mask_new)
                    max_bits = mask_gen.count_bits()
                    min_mask = mask_gen.mask
        last_err = err and err_ref
        # Update the set of tested masks with the one we just tested.
        mask_gen.update_tested(mask_new)

    print("Best I could do is %d/%d" \
          % (max_bits,nstmts))

    if do_expr:
        print(dartfuzz_cmd + " " + dart_test +
              " --mini --smask 0x%x --emask 0x%x" % (smask, min_mask))
    else:
        print(dartfuzz_cmd + " " + dart_test +
              " --mini --smask 0x%x --emask 0" % (min_mask))

    return min_mask


def main():
    parser = argparse.ArgumentParser(
        description='Minimize a generated Dart program ' +
        ' while maintaining an identified crash or divergence. ' +
        'A second Dart program can be specified for divergence testing.')
    parser.add_argument(
        '--dartfuzz',
        required=True,
        help="dartfuzz command string "
        "e.g. dart dartfuzz.dart --no-ffi --no-fp --seed 243123600")
    parser.add_argument(
        '--dart',
        help="Dart command string "
        "e.g. ./sdk/out/ReleaseX64/dart",
        required=True)
    parser.add_argument(
        '--dart-ref',
        dest="dart_ref",
        help="Dart command string for reference build " +
        "(in case of divergence testing) " + "e.g. ./sdk/out/ReleaseX64/dart",
        default=None)
    parser.add_argument(
        '--testfile',
        required=True,
        help="output filename for program generated by "
        "dartfuzz command and passed to Dart command "
        "e.g fuzz.dart")
    parser.add_argument(
        '--err',
        help="string indicating an error for Dart cmd (no multiline matches)",
        required=True)
    parser.add_argument(
        '--err-ref',
        dest="err_ref",
        help="string matching the diverging output for the Dart " +
        "reference command (no multiline matches)",
        default=None)
    parser.add_argument(
        '--smask', help="hexadecimal statements mask", default="0")
    parser.add_argument(
        '--emask', help="hexadecimal expressions mask", default="0")
    parser.add_argument(
        '--typ',
        choices=["s", "e", "se"],
        required=True,
        help="minimize statements (s) or expressions (e) or both (se)")
    parser.add_argument(
        '--tries',
        type=int,
        default=1,
        help='number of retries per run for Dart cmd')
    parser.add_argument(
        '--tries-ref',
        type=int,
        dest='tries_ref',
        default=1,
        help='number of retries per run for Dart reference cmd')
    parser.add_argument(
        '--threads',
        type=int,
        default=4,
        help='number of threads to use for retries')
    parser.add_argument(
        '--timeout', type=int, default=60, help='timeout for Dart command')
    parser.add_argument(
        '--verbose', help="print intermediate results", action="store_true")
    args = parser.parse_args()
    timeout = args.timeout
    do_stmt = "s" in args.typ
    do_expr = "e" in args.typ
    smask = int(args.smask, 16)
    if do_stmt:
        print("Minimizing Statements")
        smask = minimize(args.dartfuzz, args.dart, args.dart_ref,
                         args.testfile, args.err, args.err_ref, smask,
                         int(args.emask, 16), False, args.verbose, args.tries,
                         args.tries_ref, args.threads, timeout)
    if do_expr:
        print("Minimizing Expressions")
        minimize(args.dartfuzz, args.dart, args.dart_ref,
                 args.testfile, args.err, args.err_ref, smask,
                 int(args.emask, 16), True, args.verbose, args.tries,
                 args.tries_ref, args.threads, timeout)


if __name__ == "__main__":
    main()