ICST

Metamorphic Fuzzing of C++ Libraries

We present a method for automated metamorphic fuzzing of software libraries, implemented as a new open-source tool, MF++, that targets C++ libraries. To use our approach, a library developer first identifies a number of high-level operations their library can be made to perform. For each operation, they provide multiple equivalent implementations of the operation that use a combination of (a) functions of the library under test, and (b) other high-level operations. A given sequence of high-level operations can then be randomly expanded into a large number of distinct, equivalent sequences of calls to functions of the library under test: when expanding a high-level operation to an implementation that invokes other high-level operations, those operations can in turn be randomly expanded. Mutual recursion between high-level operations allows generation of large and complex equivalent call sequences. Equivalent call sequences can then be automatically cross-checked against randomized inputs to check that they yield equivalent outputs. Assuming that high- level operation implementations are correct, output mismatches indicate bugs in the library under test. This approach avoids the oracle problem: we do not need to know the expected results for a particular sequence of operations, only that the results should be equivalent to those obtained from an equivalent sequence; thus our approach is an instance of metamorphic testing. Test case reduction via hierarchical delta debugging can then be applied to find a minimally-expanded pair of minimized high-level operation sequences that suffice to trigger the bug, serving as a useful test case to aid in debugging. Test case reduction also aids the library developer in identifying and fixing cases where they have accidentally provided inequivalent implementations of high-level operations. We evaluate MF++ with respect to 6 libraries: four SMT solvers and two Presburger arithmetic libraries, leading to the discovery of 15 bugs. We have also successfully used MF++ and its test case reduction facilities to automatically generate small test cases that exercise source code not covered by the regression test suites of various libraries under test. Due to our metamorphic approach, the tests that we synthesise are automatically equipped with an equivalence-based oracle. We have submitted patches contributing new test cases to the isl, Yices2 and Z3 projects. The developers of these projects have been receptive to these contributions, accepting 21 tests based on our patches so far.