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.
Wed 6 AprDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
11:30 - 12:45
ICST Fuzzing and Random TestingResearch Papers / Journal-First Papers / Industry at Margaret Hamilton
Chair(s): Marcel Böhme MPI-SP, Germany and Monash University, Australia
|Metamorphic Fuzzing of C++ Libraries|
Andrei Lascu Imperial College London, Alastair F. Donaldson Imperial College London, Tobias Grosser University of Edinburgh, Torsten Hoefler ETH Zurich
|POWER: Program Option-Aware Fuzzer for High Bug Detection Ability|
Ahcheong Lee KAIST, Irfan Ariq KAIST, Yunho Kim Hanyang University, Moonzoo Kim KAIST / VPlusLab Inc.
|Comparing Fuzzers on a Level Playing Field with FuzzBench|
Dario Asprone University College London (UCL), Jonathan Metzman Google, Abhishek Arya Google, Giovani Guizzo University College London, Federica Sarro University College London
|SWFC-ART: A cost-effective approach for Fixed-Size-Candidate-Set Adaptive Random Testing through small world graphs|
Muhammad Ashfaq Jiangsu University, Rubing Huang Macau University of Science and Technology (MUST), Dave Towey University of Nottingham Ningbo China, Michael Omari Takoradi Technical University, Dmitry Yashunin Harman X, Patrick Kwaku Kudjo University of Professional Studies, Accra-Ghana, Tao Zhang Macau University of Science and Technology (MUST)Link to publication DOI
|Discussion and Q&A|