)]}' { "commit": "3e55f4356f9d4754b13ac7b1f72e5e6e7164d833", "tree": "1a636a28db807c80ca2a9e41360b5d9ec22b5bb0", "parents": [ "4c2a84dc840448af5291cde08414d8f2d118c932" ], "author": { "name": "aristotelis", "email": "aristotelis@forallsecure.com", "time": "Tue Sep 07 09:25:44 2021 -0700" }, "committer": { "name": "Copybara-Service", "email": "copybara-worker@google.com", "time": "Tue Sep 07 09:44:24 2021 -0700" }, "message": "Greedy set cover implementation of `Merger::Merge`\n\nExtend the existing single-pass algorithm for `Merger::Merge` with an algorithm that gives better results. This new implementation can be used with a new **set_cover_merge\u003d1** flag.\n\nThis greedy set cover implementation gives a substantially smaller final corpus (40%-80% less testcases) while preserving the same features/coverage. At the same time, the execution time penalty is not that significant (+50% for ~1M corpus files and far less for smaller corpora). These results were obtained by comparing several targets with varying size corpora.\n\nChange `Merger::CrashResistantMergeInternalStep` to collect all features from each file and not just unique ones. This is needed for the set cover algorithm to work correctly. The implementation of the algorithm in `Merger::SetCoverMerge` uses a bitvector to store features that are covered by a file while performing the pass. Collisions while indexing the bitvector are ignored similarly to the fuzzer.\n\nReviewed By: morehouse\n\nDifferential Revision: https://reviews.llvm.org/D105284\n\nGitOrigin-RevId: e6597dbae84034ce8ef97802584039b723adb526\n", "tree_diff": [ { "type": "modify", "old_id": "653c6ca6b2b6037a1175acbc2bd9ad77437cfae4", "old_mode": 33188, "old_path": "FuzzerDriver.cpp", "new_id": "c1a7e1b4dabc9ee496f7761b39066e65b2ce4947", "new_mode": 33188, "new_path": "FuzzerDriver.cpp" }, { "type": "modify", "old_id": "ab31da0ae5d603a4d2cb45028244998d23bc9c63", "old_mode": 33188, "old_path": "FuzzerFlags.def", "new_id": "d0cf0e904d8b65d0887b443aa0ec470779784c51", "new_mode": 33188, "new_path": "FuzzerFlags.def" }, { "type": "modify", "old_id": "f7a17fdc652511ac1cd6fcb7fde11a892670f005", "old_mode": 33188, "old_path": "FuzzerFork.cpp", "new_id": "8771ab36131900b29698d843d9fd0fbd48e06f17", "new_mode": 33188, "new_path": "FuzzerFork.cpp" }, { "type": "modify", "old_id": "bfce1dfcb2ae5d617a05617a59a9ad48d7943bdb", "old_mode": 33188, "old_path": "FuzzerInternal.h", "new_id": "6637b0034e55278ff6a1c3b41e37a03852f2db19", "new_mode": 33188, "new_path": "FuzzerInternal.h" }, { "type": "modify", "old_id": "4bae7827f80b3400d9167840ec42224c4923e79a", "old_mode": 33188, "old_path": "FuzzerMerge.cpp", "new_id": "24bd11958e807090931c39e1997f178b4320d302", "new_mode": 33188, "new_path": "FuzzerMerge.cpp" }, { "type": "modify", "old_id": "de213018ee13401e42b32d5528be8ca9dca138ef", "old_mode": 33188, "old_path": "FuzzerMerge.h", "new_id": "42f798e1da18ade6ad02e0c47dbfe3f8b66e0d99", "new_mode": 33188, "new_path": "FuzzerMerge.h" }, { "type": "modify", "old_id": "99cf79c3aaa7998c0c03b65545f1e914a49da99f", "old_mode": 33188, "old_path": "tests/FuzzerUnittest.cpp", "new_id": "1b0e7342240cde11755ae286e73929a9fccccb64", "new_mode": 33188, "new_path": "tests/FuzzerUnittest.cpp" } ] }