Improve asmap checks and add sanity check #18512

pull sipa wants to merge 7 commits into bitcoin:master from sipa:202003_asmap_checks changing 8 files +198 −26
  1. sipa commented at 2:20 am on April 3, 2020: member

    This improves/documents the failure cases inside the asmap interpreter. None of the changes are bug fixes (they only change behavior for corrupted asmap files), but they may make things easier to follow.

    In a second step, a sanity checker is added that effectively executes every potential code path through the asmap file, checking the same failure cases as the interpreter, and more. It takes around 30 ms to run for me for a 1.2 MB asmap file.

    I’ve verified that this accepts asmap files constructed by https://github.com/sipa/asmap/blob/master/buildmap.py with a large dataset, and no longer accepts it with 1 bit changed in it.

  2. sipa force-pushed on Apr 3, 2020
  3. fanquake added the label P2P on Apr 3, 2020
  4. sipa commented at 2:23 am on April 3, 2020: member
    cc @naumenkogs.
  5. sipa commented at 3:27 am on April 3, 2020: member

    @practicalswift There may be opportunity to fuzz here: if SanityCheckASMap succeeds, then no input to Interpret should return 0.

    EDIT: Oh no, 0 can mean no match or error; it’s still possible to reach no match.

  6. DrahtBot commented at 8:48 am on April 3, 2020: member

    The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

    Conflicts

    Reviewers, this pull request conflicts with the following ones:

    • #18573 ([RFC] bitcoin-asmap utility by sipa)

    If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

  7. MarcoFalke commented at 1:30 pm on April 3, 2020: member

    Would be nice to have the new code covered by some tests. Maybe the fuzzers?

    0diff --git a/src/test/fuzz/asmap.cpp b/src/test/fuzz/asmap.cpp
1index 7f3eef79a1..1ab5459b12 100644
2--- a/src/test/fuzz/asmap.cpp
3+++ b/src/test/fuzz/asmap.cpp
4@@ -25,4 +25,5 @@ void test_one_input(const std::vector<uint8_t>& buffer)
5         }
6     }
7     (void)net_addr.GetMappedAS(asmap);
8+    (void)SanityCheckASMap(asmap);
9 }
  8. naumenkogs commented at 2:52 pm on April 3, 2020: member

    Code review ACK 47192230486e9305abb7c1ce882a515cdfb0a8b5 Tested: did some bit-flipping and saw that sanity check does not pass anymore.

    Thank you for working on this.

  9. sipa force-pushed on Apr 3, 2020
  10. sipa commented at 8:40 pm on April 3, 2020: member

    A few changes:

    • I’ve split out the changes into more commits
    • Made it an error to reach EOF without a RETURN instruction
    • Made the sanity checker slightly more tolerant (it now supports multiple jumps to the same location, a potential optimization that buildmap.py doesn’t currently use).
    • Added a commit that makes failures in the Interpreter assertion failures, and adds a fuzz tester that verifies this does not happen with asmaps that pass SanityCheckASMap.

    I’ve verified that the fuzzer actually finds asmaps that pass the sanity check, and the Interpreter is run on it (by adding an early assertion failure in Interpreter). I’ll try to share my corpus.

  11. sipa force-pushed on Apr 4, 2020
  12. naumenkogs commented at 1:16 pm on April 4, 2020: member

    Using gcc 9.2.1, AFL 2.5.2, got this at compilation for fuzzing:

     0libbitcoin_util.a(libbitcoin_util_a-threadinterrupt.o): In function `UniqueLock<AnnotatedMixin<std::mutex>, std::unique_lock<std::mutex> >::~UniqueLock()':
 1/home/gleb/bitcoin/src/./sync.h:169: undefined reference to `LeaveCritical()'
 2libbitcoin_util.a(libbitcoin_util_a-threadinterrupt.o): In function `UniqueLock<AnnotatedMixin<std::mutex>, std::unique_lock<std::mutex> >::TryEnter(char const*, char const*, int)':
 3/home/gleb/bitcoin/src/./sync.h:139: undefined reference to `EnterCritical(char const*, char const*, int, void*, bool)'
 4/home/gleb/bitcoin/src/./sync.h:142: undefined reference to `LeaveCritical()'
 5libbitcoin_util.a(libbitcoin_util_a-threadinterrupt.o): In function `UniqueLock<AnnotatedMixin<std::mutex>, std::unique_lock<std::mutex> >::Enter(char const*, char const*, int)':
 6/home/gleb/bitcoin/src/./sync.h:126: undefined reference to `EnterCritical(char const*, char const*, int, void*, bool)'
 7collect2: error: ld returned 1 exit status
 8Makefile:7281: recipe for target 'test/fuzz/addrman_deserialize' failed
 9make[2]: *** [test/fuzz/addrman_deserialize] Error 1
10make[2]: *** Waiting for unfinished jobs....
11libbitcoin_util.a(libbitcoin_util_a-threadinterrupt.o): In function `UniqueLock<AnnotatedMixin<std::mutex>, std::unique_lock<std::mutex> >::~UniqueLock()':
12/home/gleb/bitcoin/src/./sync.h:169: undefined reference to `LeaveCritical()'
13libbitcoin_util.a(libbitcoin_util_a-threadinterrupt.o): In function `UniqueLock<AnnotatedMixin<std::mutex>, std::unique_lock<std::mutex> >::TryEnter(char const*, char const*, int)':
14/home/gleb/bitcoin/src/./sync.h:139: undefined reference to `EnterCritical(char const*, char const*, int, void*, bool)'
15/home/gleb/bitcoin/src/./sync.h:142: undefined reference to `LeaveCritical()'
16libbitcoin_util.a(libbitcoin_util_a-threadinterrupt.o): In function `UniqueLock<AnnotatedMixin<std::mutex>, std::unique_lock<std::mutex> >::Enter(char const*, char const*, int)':
17/home/gleb/bitcoin/src/./sync.h:126: undefined reference to `EnterCritical(char const*, char const*, int, void*, bool)'
18collect2: error: ld returned 1 exit status
19Makefile:7329: recipe for target 'test/fuzz/block' failed
20make[2]: *** [test/fuzz/block] Error 1
21libbitcoin_util.a(libbitcoin_util_a-threadinterrupt.o): In function `UniqueLock<AnnotatedMixin<std::mutex>, std::unique_lock<std::mutex> >::~UniqueLock()':
22/home/gleb/bitcoin/src/./sync.h:169: undefined reference to `LeaveCritical()'
23libbitcoin_util.a(libbitcoin_util_a-threadinterrupt.o): In function `UniqueLock<AnnotatedMixin<std::mutex>, std::unique_lock<std::mutex> >::TryEnter(char const*, char const*, int)':
24/home/gleb/bitcoin/src/./sync.h:139: undefined reference to `EnterCritical(char const*, char const*, int, void*, bool)'
25/home/gleb/bitcoin/src/./sync.h:142: undefined reference to `LeaveCritical()'
26libbitcoin_util.a(libbitcoin_util_a-threadinterrupt.o): In function `UniqueLock<AnnotatedMixin<std::mutex>, std::unique_lock<std::mutex> >::Enter(char const*, char const*, int)':
27/home/gleb/bitcoin/src/./sync.h:126: undefined reference to `EnterCritical(char const*, char const*, int, void*, bool)'
28collect2: error: ld returned 1 exit status
29Makefile:7369: recipe for target 'test/fuzz/block_header_and_short_txids_deserialize' failed
30make[2]: *** [test/fuzz/block_header_and_short_txids_deserialize] Error 1
31make[2]: Leaving directory '/home/gleb/bitcoin/src'
32Makefile:18893: recipe for target 'all-recursive' failed
33make[1]: *** [all-recursive] Error 1
34make[1]: Leaving directory '/home/gleb/bitcoin/src'
35Makefile:783: recipe for target 'all-recursive' failed
36make: *** [all-recursive] Error 1

    cc: @practicalswift

  13. MarcoFalke commented at 1:24 pm on April 4, 2020: member
    @naumenkogs have you run make distclean?
  14. practicalswift commented at 1:47 pm on April 4, 2020: contributor

    Concept ACK

    Thanks a lot for adding a fuzzing harness!

  15. naumenkogs commented at 1:50 pm on April 4, 2020: member
    @MarcoFalke This helped. @sipa With the latest code, the map I generated with truncate -s 1M wrong_asmap seems to be valid. I don’t think that’s correct behavior?
  16. sipa force-pushed on Apr 4, 2020
  17. sipa commented at 6:11 pm on April 4, 2020: member
    @naumenkogs Nice catch. DecodeBits wasn’t returning failure when EOF occurred in the mantissa bits. Should be fixed now. I believe it should be impossible to take a valid asmap and truncate it, and having it still be acceptable.
  18. naumenkogs commented at 11:04 pm on April 4, 2020: member
    ACK 906e031
  19. sipa force-pushed on Apr 6, 2020
  20. sipa force-pushed on Apr 6, 2020
  21. sipa commented at 10:14 pm on April 6, 2020: member
    Now added an extra check that verifies that no truncation of a valid asmap remains valid.
  22. Introduce Instruction enum in asmap 1479007a33
  23. Deal with decoding failures explicitly in asmap Interpret 2b3dbfa5a6
  24. Improve asmap Interpret checks and document failures 5feefbe6e7
  25. Add asmap sanity checker fffd8dca2d
  26. Add additional effiency checks to sanity checker c81aefc537
  27. Make asmap Interpreter errors fatal and fuzz test it 7cf97fda15
  28. Add asmap_direct fuzzer that tests Interpreter directly 748977690e
  29. sipa force-pushed on Apr 8, 2020
  30. laanwj added this to the "Blockers" column in a project
  31. hebasto commented at 5:25 pm on April 17, 2020: member
    @sipa Mind addressing a compiler warning issue on ARM 32-bit platforms: d0b10ed97a37c18a1750c776d6930378b64a5db9 from #18686 ?
  32. practicalswift commented at 5:59 am on April 25, 2020: contributor
    ACK 748977690e0519110cda9628162a7ccf73a5934b modulo feedback below. @sipa, would it be possible to make it so that the existing coverage-increasing inputs to src/test/fuzz/asmap are not invalidated by the merge of this PR? The qa-assets inputs achieve very comprehensive coverage for asmap thanks to previous fuzzing efforts. It would be nice to keep those inputs. Perhaps your src/test/fuzz/asmap.cpp changes can be moved to a separate new fuzzing harness file? :)
  33. in src/util/asmap.cpp:88 in 748977690e 
    87     while (pos != endpos) {
88         opcode = DecodeType(pos, endpos);
89-        if (opcode == 0) {
90-            return DecodeASN(pos, endpos);
91-        } else if (opcode == 1) {
92+        if (opcode == Instruction::RETURN) {
    jonatack commented at 1:05 pm on April 26, 2020:
    nit: Perhaps use a switch statement for the opcode conditionals, here and in SanityCheckASMap, to make explicit the nature of the operation (testing a single value against a set of scoped enumerations) and possibly generate better code with a jump table instead of repeatedly checking individual values.
  34. in src/test/fuzz/asmap_direct.cpp:40 in 748977690e 
    35+        // Verify that for valid asmaps, no prefix (except up to 7 zero padding bits) is valid.
36+        std::vector<bool> asmap_prefix = asmap;
37+        while (!asmap_prefix.empty() && asmap_prefix.size() + 7 > asmap.size() && asmap_prefix.back() == false) asmap_prefix.pop_back();
38+        while (!asmap_prefix.empty()) {
39+            asmap_prefix.pop_back();
40+            assert(!SanityCheckASMap(asmap_prefix, buffer.size() - 1 - sep_pos));
    jonatack commented at 1:08 pm on April 26, 2020:

    nit suggestion:

     0+    size_t bits = buffer.size() - sep_pos - 1;
 1-    if (buffer.size() - sep_pos - 1 > 128) return; // At most 128 bits in IP address
 2+    if (bits > 128) return; // At most 128 bits in IP address
 3 
 4     // Checks on asmap
 5     std::vector<bool> asmap(buffer.begin(), buffer.begin() + sep_pos);
 6-    if (SanityCheckASMap(asmap, buffer.size() - 1 - sep_pos)) {
 7+    if (SanityCheckASMap(asmap, bits)) {
 8         // Verify that for valid asmaps, no prefix (except up to 7 zero padding bits) is valid.
 9         std::vector<bool> asmap_prefix = asmap;
10         while (!asmap_prefix.empty() && asmap_prefix.size() + 7 > asmap.size() && asmap_prefix.back() == false) asmap_prefix.pop_back();
11         while (!asmap_prefix.empty()) {
12             asmap_prefix.pop_back();
13-            assert(!SanityCheckASMap(asmap_prefix, buffer.size() - 1 - sep_pos));
14+            assert(!SanityCheckASMap(asmap_prefix, bits));
  35. in src/test/fuzz/asmap_direct.cpp:29 in 748977690e 
    24+            sep_pos = pos;
25+        } else {
26+            return;
27+        }
28+    }
29+    if (!have_sep) return; // Needs exactly 1 separator
    jonatack commented at 1:14 pm on April 26, 2020:

    nit suggestion:

     0-    bool have_sep = false;
 1+    int separators{0};
 2     size_t sep_pos;
 3     for (size_t pos = 0; pos < buffer.size(); ++pos) {
 4         uint8_t x = buffer[pos];
 5         if ((x & 0xFE) == 0) continue;
 6         if (x == 0xFF) {
 7-            if (have_sep) return;
 8-            have_sep = true;
 9+            if (separators != 0) return;
10+            separators += 1;
11             sep_pos = pos;
12         } else {
13             return;
14         }
15     }
16-    if (!have_sep) return; // Needs exactly 1 separator
17+    if (separators != 1) return; // Needs exactly 1 separator
    fjahr commented at 6:07 pm on May 1, 2020:
    @jonatack Even in your code the only values the variable can have is 0 and 1. Why would you want to use an int instead of a bool then?
    jonatack commented at 6:23 pm on May 1, 2020:
    My thoughts were (a) a sanity check is better than just eyeballing code, not only for now but also future changes, and (b) a check for exactly one is more strongly verified when a state of more than one is also tested.
  36. jonatack commented at 1:22 pm on April 26, 2020: member

    Thanks for adding sanity checks and fuzzing.

    ACK 748977690e0519110cda9628162a7ccf73a5934b code review, regular build/tests/ran bitcoin with -asmap, fuzz build/ran both fuzzers overnight.

    fuzz/asmap_direct

    0[#900803874](/bitcoin-bitcoin/900803874/)	REDUCE cov: 730 ft: 3838 corp: 210/19Kb exec/s: 19950 rss: 562Mb L: 78/2049 MS: 1 EraseBytes-
1[#906401851](/bitcoin-bitcoin/906401851/)	REDUCE cov: 730 ft: 3838 corp: 210/19Kb exec/s: 19899 rss: 562Mb L: 249/2049 MS: 2 InsertRepeatedBytes-EraseBytes-
2[#906756962](/bitcoin-bitcoin/906756962/)	REDUCE cov: 730 ft: 3838 corp: 210/19Kb exec/s: 19895 rss: 562Mb L: 247/2049 MS: 1 EraseBytes-

    fuzz/asmap

    0[#183578499](/bitcoin-bitcoin/183578499/)	REDUCE cov: 1226 ft: 3413 corp: 222/7168b exec/s: 3930 rss: 421Mb L: 39/147 MS: 1 EraseBytes-
1[#184582017](/bitcoin-bitcoin/184582017/)	REDUCE cov: 1226 ft: 3413 corp: 222/7165b exec/s: 3928 rss: 421Mb L: 116/147 MS: 2 EraseBytes-ChangeByte-
2[#185253963](/bitcoin-bitcoin/185253963/)	REDUCE cov: 1226 ft: 3413 corp: 222/7164b exec/s: 3928 rss: 421Mb L: 115/147 MS: 1 EraseBytes-

    A few non-blocking ideas for your consideration below.

  37. in src/util/asmap.cpp:123 in fffd8dca2d outdated 
    118@@ -118,3 +119,56 @@ uint32_t Interpret(const std::vector<bool> &asmap, const std::vector<bool> &ip)
119     // Reached EOF without RETURN, or aborted (see any of the breaks above).
120     return 0; // 0 is not a valid ASN
121 }
122+
123+bool SanityCheckASMap(const std::vector<bool>& asmap, int bits)
    fjahr commented at 6:31 pm on May 1, 2020:
    nit: It’s a bit inconsistent that this function has ASMap in it while DecodeAsmap for example has Asmap.
  38. fjahr approved
  39. fjahr commented at 9:33 pm on May 1, 2020: member

    ACK 748977690e0519110cda9628162a7ccf73a5934b

    Reviewed code and tested asmap and asmap_direct fuzzers. Confirmed that bitcoind starts with a correct map and Sanity checker catches a corrupt file.

  40. laanwj merged this on May 6, 2020
  41. laanwj closed this on May 6, 2020
  42. laanwj removed this from the "Blockers" column in a project
  43. sidhujag referenced this in commit 4345a2445a on May 12, 2020
  44. Fabcien referenced this in commit eda85704fc on Jan 25, 2021
  45. Fabcien referenced this in commit 942d91965b on Feb 10, 2021
  46. random-zebra referenced this in commit 85f000ecbe on Jul 30, 2021
  47. random-zebra referenced this in commit b4751e10ce on Aug 11, 2021
  48. DrahtBot locked this on Feb 15, 2022


sipa DrahtBot MarcoFalke naumenkogs practicalswift hebasto jonatack fjahr

Labels
P2P

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-19 00:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me