diff --git a/src/addrman.cpp b/src/addrman.cpp --- a/src/addrman.cpp +++ b/src/addrman.cpp @@ -758,5 +758,9 @@ bits.push_back((cur_byte >> bit) & 1); } } + if (!SanityCheckASMap(bits)) { + LogPrintf("Sanity check of asmap file %s failed\n", path); + return {}; + } return bits; } diff --git a/src/netaddress.h b/src/netaddress.h --- a/src/netaddress.h +++ b/src/netaddress.h @@ -211,4 +211,6 @@ } }; +bool SanityCheckASMap(const std::vector &asmap); + #endif // BITCOIN_NETADDRESS_H diff --git a/src/netaddress.cpp b/src/netaddress.cpp --- a/src/netaddress.cpp +++ b/src/netaddress.cpp @@ -940,3 +940,8 @@ return (a.network < b.network || (a.network == b.network && memcmp(a.netmask, b.netmask, 16) < 0)); } + +bool SanityCheckASMap(const std::vector &asmap) { + // For IP address lookups, the input is 128 bits + return SanityCheckASMap(asmap, 128); +} diff --git a/src/test/fuzz/CMakeLists.txt b/src/test/fuzz/CMakeLists.txt --- a/src/test/fuzz/CMakeLists.txt +++ b/src/test/fuzz/CMakeLists.txt @@ -78,6 +78,7 @@ addition_overflow addrdb asmap + asmap_direct base_encode_decode block block_header diff --git a/src/test/fuzz/asmap.cpp b/src/test/fuzz/asmap.cpp --- a/src/test/fuzz/asmap.cpp +++ b/src/test/fuzz/asmap.cpp @@ -4,28 +4,66 @@ #include -#include #include #include #include +//! asmap code that consumes nothing +static const std::vector IPV6_PREFIX_ASMAP = {}; + +//! asmap code that consumes the 96 prefix bits of ::ffff:0/96 (IPv4-in-IPv6 +//! map) +static const std::vector IPV4_PREFIX_ASMAP = { + true, true, false, true, true, true, true, true, true, + true, false, false, false, false, false, false, false, false, // Match 0x00 + true, true, false, true, true, true, true, true, true, + true, false, false, false, false, false, false, false, false, // Match 0x00 + true, true, false, true, true, true, true, true, true, + true, false, false, false, false, false, false, false, false, // Match 0x00 + true, true, false, true, true, true, true, true, true, + true, false, false, false, false, false, false, false, false, // Match 0x00 + true, true, false, true, true, true, true, true, true, + true, false, false, false, false, false, false, false, false, // Match 0x00 + true, true, false, true, true, true, true, true, true, + true, false, false, false, false, false, false, false, false, // Match 0x00 + true, true, false, true, true, true, true, true, true, + true, false, false, false, false, false, false, false, false, // Match 0x00 + true, true, false, true, true, true, true, true, true, + true, false, false, false, false, false, false, false, false, // Match 0x00 + true, true, false, true, true, true, true, true, true, + true, false, false, false, false, false, false, false, false, // Match 0x00 + true, true, false, true, true, true, true, true, true, + true, false, false, false, false, false, false, false, false, // Match 0x00 + true, true, false, true, true, true, true, true, true, + true, true, true, true, true, true, true, true, true, // Match 0xFF + true, true, false, true, true, true, true, true, true, + true, true, true, true, true, true, true, true, true // Match 0xFF +}; + void test_one_input(const std::vector &buffer) { - FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size()); - const Network network = - fuzzed_data_provider.PickValueInArray({NET_IPV4, NET_IPV6}); - if (fuzzed_data_provider.remaining_bytes() < 16) { + // Encoding: [7 bits: asmap size] [1 bit: ipv6?] [3-130 bytes: asmap] [4 or + // 16 bytes: addr] + if (buffer.size() < 1 + 3 + 4) { return; } - CNetAddr net_addr; - net_addr.SetRaw(network, - fuzzed_data_provider.ConsumeBytes(16).data()); - std::vector asmap; - for (const char cur_byte : - fuzzed_data_provider.ConsumeRemainingBytes()) { - for (int bit = 0; bit < 8; ++bit) { - asmap.push_back((cur_byte >> bit) & 1); + int asmap_size = 3 + (buffer[0] & 127); + bool ipv6 = buffer[0] & 128; + int addr_size = ipv6 ? 16 : 4; + if (buffer.size() < size_t(1 + asmap_size + addr_size)) { + return; + } + std::vector asmap = ipv6 ? IPV6_PREFIX_ASMAP : IPV4_PREFIX_ASMAP; + asmap.reserve(asmap.size() + 8 * asmap_size); + for (int i = 0; i < asmap_size; ++i) { + for (int j = 0; j < 8; ++j) { + asmap.push_back((buffer[1 + i] >> j) & 1); } } + if (!SanityCheckASMap(asmap)) { + return; + } + CNetAddr net_addr; + net_addr.SetRaw(ipv6 ? NET_IPV6 : NET_IPV4, buffer.data() + 1 + asmap_size); (void)net_addr.GetMappedAS(asmap); } diff --git a/src/test/fuzz/asmap_direct.cpp b/src/test/fuzz/asmap_direct.cpp new file mode 100644 --- /dev/null +++ b/src/test/fuzz/asmap_direct.cpp @@ -0,0 +1,61 @@ +// Copyright (c) 2020 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include + +#include + +#include +#include +#include + +void test_one_input(const std::vector &buffer) { + // Encoding: [asmap using 1 bit / byte] 0xFF [addr using 1 bit / byte] + bool have_sep = false; + size_t sep_pos; + for (size_t pos = 0; pos < buffer.size(); ++pos) { + uint8_t x = buffer[pos]; + if ((x & 0xFE) == 0) { + continue; + } + if (x == 0xFF) { + if (have_sep) { + return; + } + have_sep = true; + sep_pos = pos; + } else { + return; + } + } + if (!have_sep) { + // Needs exactly 1 separator + return; + } + if (buffer.size() - sep_pos - 1 > 128) { + // At most 128 bits in IP address + return; + } + + // Checks on asmap + std::vector asmap(buffer.begin(), buffer.begin() + sep_pos); + if (SanityCheckASMap(asmap, buffer.size() - 1 - sep_pos)) { + // Verify that for valid asmaps, no prefix (except up to 7 zero padding + // bits) is valid. + std::vector asmap_prefix = asmap; + while (!asmap_prefix.empty() && + asmap_prefix.size() + 7 > asmap.size() && + asmap_prefix.back() == false) { + asmap_prefix.pop_back(); + } + while (!asmap_prefix.empty()) { + asmap_prefix.pop_back(); + assert( + !SanityCheckASMap(asmap_prefix, buffer.size() - 1 - sep_pos)); + } + // No address input should trigger assertions in interpreter + std::vector addr(buffer.begin() + sep_pos + 1, buffer.end()); + (void)Interpret(asmap, addr); + } +} diff --git a/src/util/asmap.h b/src/util/asmap.h --- a/src/util/asmap.h +++ b/src/util/asmap.h @@ -5,6 +5,11 @@ #ifndef BITCOIN_UTIL_ASMAP_H #define BITCOIN_UTIL_ASMAP_H +#include +#include + uint32_t Interpret(const std::vector &asmap, const std::vector &ip); +bool SanityCheckASMap(const std::vector &asmap, int bits); + #endif // BITCOIN_UTIL_ASMAP_H diff --git a/src/util/asmap.cpp b/src/util/asmap.cpp --- a/src/util/asmap.cpp +++ b/src/util/asmap.cpp @@ -5,10 +5,13 @@ #include #include +#include #include namespace { +constexpr uint32_t INVALID = 0xFFFFFFFF; + uint32_t DecodeBits(std::vector::const_iterator &bitpos, const std::vector::const_iterator &endpos, uint8_t minval, const std::vector &bit_sizes) { @@ -30,7 +33,8 @@ } else { for (int b = 0; b < *bit_sizes_it; b++) { if (bitpos == endpos) { - break; + // Reached EOF in mantissa + return INVALID; } bit = *bitpos; bitpos++; @@ -39,13 +43,21 @@ return val; } } - return -1; + // Reached EOF in exponent + return INVALID; } +enum class Instruction : uint32_t { + RETURN = 0, + JUMP = 1, + MATCH = 2, + DEFAULT = 3, +}; + const std::vector TYPE_BIT_SIZES{0, 0, 1}; -uint32_t DecodeType(std::vector::const_iterator &bitpos, - const std::vector::const_iterator &endpos) { - return DecodeBits(bitpos, endpos, 0, TYPE_BIT_SIZES); +Instruction DecodeType(std::vector::const_iterator &bitpos, + const std::vector::const_iterator &endpos) { + return Instruction(DecodeBits(bitpos, endpos, 0, TYPE_BIT_SIZES)); } const std::vector ASN_BIT_SIZES{15, 16, 17, 18, 19, @@ -77,42 +89,190 @@ const std::vector::const_iterator endpos = asmap.end(); uint8_t bits = ip.size(); uint32_t default_asn = 0; - uint32_t opcode, jump, match, matchlen; + uint32_t jump, match, matchlen; + Instruction opcode; while (pos != endpos) { opcode = DecodeType(pos, endpos); - if (opcode == 0) { - return DecodeASN(pos, endpos); - } else if (opcode == 1) { + if (opcode == Instruction::RETURN) { + default_asn = DecodeASN(pos, endpos); + if (default_asn == INVALID) { + // ASN straddles EOF + break; + } + return default_asn; + } else if (opcode == Instruction::JUMP) { jump = DecodeJump(pos, endpos); + if (jump == INVALID) { + // Jump offset straddles EOF + break; + } if (bits == 0) { + // No input bits left break; } if (ip[ip.size() - bits]) { if (jump >= endpos - pos) { + // Jumping past EOF break; } pos += jump; } bits--; - } else if (opcode == 2) { + } else if (opcode == Instruction::MATCH) { match = DecodeMatch(pos, endpos); + if (match == INVALID) { + // Match bits straddle EOF + break; + } matchlen = CountBits(match) - 1; + if (bits < matchlen) { + // Not enough input bits + break; + } for (uint32_t bit = 0; bit < matchlen; bit++) { - if (bits == 0) { - break; - } if ((ip[ip.size() - bits]) != ((match >> (matchlen - 1 - bit)) & 1)) { return default_asn; } bits--; } - } else if (opcode == 3) { + } else if (opcode == Instruction::DEFAULT) { default_asn = DecodeASN(pos, endpos); + if (default_asn == INVALID) { + // ASN straddles EOF + break; + } } else { + // Instruction straddles EOF break; } } + + // Reached EOF without RETURN, or aborted (see any of the breaks above) - + // should have been caught by SanityCheckASMap below + assert(false); + // 0 is not a valid ASN return 0; } + +bool SanityCheckASMap(const std::vector &asmap, int bits) { + const std::vector::const_iterator begin = asmap.begin(), + endpos = asmap.end(); + std::vector::const_iterator pos = begin; + // All future positions we may jump to (bit offset in asmap -> bits to + // consume left) + std::vector> jumps; + jumps.reserve(bits); + Instruction prevopcode = Instruction::JUMP; + bool had_incomplete_match = false; + while (pos != endpos) { + uint32_t offset = pos - begin; + if (!jumps.empty() && offset >= jumps.back().first) { + // There was a jump into the middle of the previous instruction + return false; + } + Instruction opcode = DecodeType(pos, endpos); + if (opcode == Instruction::RETURN) { + if (prevopcode == Instruction::DEFAULT) { + // There should not be any RETURN immediately after a DEFAULT + // (could be combined into just RETURN) + return false; + } + uint32_t asn = DecodeASN(pos, endpos); + if (asn == INVALID) { + // ASN straddles EOF + return false; + } + if (jumps.empty()) { + // Nothing to execute anymore + if (endpos - pos > 7) { + // Excessive padding + return false; + } + while (pos != endpos) { + if (*pos) { + // Nonzero padding bit + return false; + } + ++pos; + } + // Sanely reached EOF + return true; + } else { + // Continue by pretending we jumped to the next instruction + offset = pos - begin; + if (offset != jumps.back().first) { + // Unreachable code + return false; + } + // Restore the number of bits we would have had left after this + // jump + bits = jumps.back().second; + jumps.pop_back(); + prevopcode = Instruction::JUMP; + } + } else if (opcode == Instruction::JUMP) { + uint32_t jump = DecodeJump(pos, endpos); + if (jump == INVALID) { + // Jump offset straddles EOF + return false; + } + if (jump > endpos - pos) { + // Jump out of range + return false; + } + if (bits == 0) { + // Consuming bits past the end of the input + return false; + } + --bits; + uint32_t jump_offset = pos - begin + jump; + if (!jumps.empty() && jump_offset >= jumps.back().first) { + // Intersecting jumps + return false; + } + jumps.emplace_back(jump_offset, bits); + prevopcode = Instruction::JUMP; + } else if (opcode == Instruction::MATCH) { + uint32_t match = DecodeMatch(pos, endpos); + if (match == INVALID) { + // Match bits straddle EOF + return false; + } + int matchlen = CountBits(match) - 1; + if (prevopcode != Instruction::MATCH) { + had_incomplete_match = false; + } + if (matchlen < 8 && had_incomplete_match) { + // Within a sequence of matches only at most one should be + // incomplete + return false; + } + had_incomplete_match = (matchlen < 8); + if (bits < matchlen) { + // Consuming bits past the end of the input + return false; + } + bits -= matchlen; + prevopcode = Instruction::MATCH; + } else if (opcode == Instruction::DEFAULT) { + if (prevopcode == Instruction::DEFAULT) { + // There should not be two successive DEFAULTs (they could be + // combined into one) + return false; + } + uint32_t asn = DecodeASN(pos, endpos); + if (asn == INVALID) { + // ASN straddles EOF + return false; + } + prevopcode = Instruction::DEFAULT; + } else { + // Instruction straddles EOF + return false; + } + } + // Reached EOF without RETURN instruction + return false; +}