From 1479007a335ab43af46f527d0543e254fc2a8e86 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 2 Apr 2020 18:22:04 -0700 Subject: Introduce Instruction enum in asmap --- src/util/asmap.cpp | 23 ++++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-) (limited to 'src/util/asmap.cpp') diff --git a/src/util/asmap.cpp b/src/util/asmap.cpp index 60bd27bf90..2ffd618203 100644 --- a/src/util/asmap.cpp +++ b/src/util/asmap.cpp @@ -36,10 +36,18 @@ uint32_t DecodeBits(std::vector::const_iterator& bitpos, const std::vector return -1; } +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) +Instruction DecodeType(std::vector::const_iterator& bitpos, const std::vector::const_iterator& endpos) { - return DecodeBits(bitpos, endpos, 0, TYPE_BIT_SIZES); + return Instruction(DecodeBits(bitpos, endpos, 0, TYPE_BIT_SIZES)); } const std::vector ASN_BIT_SIZES{15, 16, 17, 18, 19, 20, 21, 22, 23, 24}; @@ -70,12 +78,13 @@ uint32_t Interpret(const std::vector &asmap, const std::vector &ip) 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) { + if (opcode == Instruction::RETURN) { return DecodeASN(pos, endpos); - } else if (opcode == 1) { + } else if (opcode == Instruction::JUMP) { jump = DecodeJump(pos, endpos); if (bits == 0) break; if (ip[ip.size() - bits]) { @@ -83,7 +92,7 @@ uint32_t Interpret(const std::vector &asmap, const std::vector &ip) pos += jump; } bits--; - } else if (opcode == 2) { + } else if (opcode == Instruction::MATCH) { match = DecodeMatch(pos, endpos); matchlen = CountBits(match) - 1; for (uint32_t bit = 0; bit < matchlen; bit++) { @@ -93,7 +102,7 @@ uint32_t Interpret(const std::vector &asmap, const std::vector &ip) } bits--; } - } else if (opcode == 3) { + } else if (opcode == Instruction::DEFAULT) { default_asn = DecodeASN(pos, endpos); } else { break; -- cgit v1.2.3 From 2b3dbfa5a63cb5a6625ec00294ebd933800f0255 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Fri, 3 Apr 2020 10:43:38 -0700 Subject: Deal with decoding failures explicitly in asmap Interpret --- src/util/asmap.cpp | 15 +++++++++++---- 1 file changed, 11 insertions(+), 4 deletions(-) (limited to 'src/util/asmap.cpp') diff --git a/src/util/asmap.cpp b/src/util/asmap.cpp index 2ffd618203..5b21d01f3a 100644 --- a/src/util/asmap.cpp +++ b/src/util/asmap.cpp @@ -8,6 +8,8 @@ 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) { uint32_t val = minval; @@ -25,7 +27,7 @@ uint32_t DecodeBits(std::vector::const_iterator& bitpos, const std::vector val += (1 << *bit_sizes_it); } else { for (int b = 0; b < *bit_sizes_it; b++) { - if (bitpos == endpos) break; + if (bitpos == endpos) return INVALID; // Reached EOF in mantissa bit = *bitpos; bitpos++; val += bit << (*bit_sizes_it - 1 - b); @@ -33,7 +35,7 @@ uint32_t DecodeBits(std::vector::const_iterator& bitpos, const std::vector return val; } } - return -1; + return INVALID; // Reached EOF in exponent } enum class Instruction : uint32_t @@ -83,9 +85,12 @@ uint32_t Interpret(const std::vector &asmap, const std::vector &ip) while (pos != endpos) { opcode = DecodeType(pos, endpos); if (opcode == Instruction::RETURN) { - return DecodeASN(pos, endpos); + default_asn = DecodeASN(pos, endpos); + if (default_asn == INVALID) break; // ASN straddles EOF + return default_asn; } else if (opcode == Instruction::JUMP) { jump = DecodeJump(pos, endpos); + if (jump == INVALID) break; // Jump offset straddles EOF if (bits == 0) break; if (ip[ip.size() - bits]) { if (jump >= endpos - pos) break; @@ -94,6 +99,7 @@ uint32_t Interpret(const std::vector &asmap, const std::vector &ip) bits--; } else if (opcode == Instruction::MATCH) { match = DecodeMatch(pos, endpos); + if (match == INVALID) break; // Match bits straddle EOF matchlen = CountBits(match) - 1; for (uint32_t bit = 0; bit < matchlen; bit++) { if (bits == 0) break; @@ -104,8 +110,9 @@ uint32_t Interpret(const std::vector &asmap, const std::vector &ip) } } else if (opcode == Instruction::DEFAULT) { default_asn = DecodeASN(pos, endpos); + if (default_asn == INVALID) break; // ASN straddles EOF } else { - break; + break; // Instruction straddles EOF } } return 0; // 0 is not a valid ASN -- cgit v1.2.3 From 5feefbe6e7b6cdd809eba4074d41dc95a7035f7e Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 2 Apr 2020 18:17:55 -0700 Subject: Improve asmap Interpret checks and document failures --- src/util/asmap.cpp | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'src/util/asmap.cpp') diff --git a/src/util/asmap.cpp b/src/util/asmap.cpp index 5b21d01f3a..e428ec8138 100644 --- a/src/util/asmap.cpp +++ b/src/util/asmap.cpp @@ -91,9 +91,9 @@ uint32_t Interpret(const std::vector &asmap, const std::vector &ip) } else if (opcode == Instruction::JUMP) { jump = DecodeJump(pos, endpos); if (jump == INVALID) break; // Jump offset straddles EOF - if (bits == 0) break; + if (bits == 0) break; // No input bits left + if (jump >= endpos - pos) break; // Jumping past EOF if (ip[ip.size() - bits]) { - if (jump >= endpos - pos) break; pos += jump; } bits--; @@ -101,8 +101,8 @@ uint32_t Interpret(const std::vector &asmap, const std::vector &ip) match = DecodeMatch(pos, endpos); if (match == INVALID) break; // Match bits straddle EOF matchlen = CountBits(match) - 1; + if (bits < matchlen) break; // Not enough input bits 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; } @@ -115,5 +115,6 @@ uint32_t Interpret(const std::vector &asmap, const std::vector &ip) break; // Instruction straddles EOF } } + // Reached EOF without RETURN, or aborted (see any of the breaks above). return 0; // 0 is not a valid ASN } -- cgit v1.2.3 From fffd8dca2de39ad4a683f0dce57cdca55ed2f600 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 2 Apr 2020 18:18:08 -0700 Subject: Add asmap sanity checker --- src/util/asmap.cpp | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 54 insertions(+) (limited to 'src/util/asmap.cpp') diff --git a/src/util/asmap.cpp b/src/util/asmap.cpp index e428ec8138..5c3652f89b 100644 --- a/src/util/asmap.cpp +++ b/src/util/asmap.cpp @@ -2,6 +2,7 @@ // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. +#include #include #include #include @@ -118,3 +119,56 @@ uint32_t Interpret(const std::vector &asmap, const std::vector &ip) // Reached EOF without RETURN, or aborted (see any of the breaks above). return 0; // 0 is not a valid ASN } + +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; + std::vector> jumps; // All future positions we may jump to (bit offset in asmap -> bits to consume left) + jumps.reserve(bits); + while (pos != endpos) { + uint32_t offset = pos - begin; + if (!jumps.empty() && offset >= jumps.back().first) return false; // There was a jump into the middle of the previous instruction + Instruction opcode = DecodeType(pos, endpos); + if (opcode == Instruction::RETURN) { + uint32_t asn = DecodeASN(pos, endpos); + if (asn == INVALID) return false; // ASN straddles EOF + if (jumps.empty()) { + // Nothing to execute anymore + if (endpos - pos > 7) return false; // Excessive padding + while (pos != endpos) { + if (*pos) return false; // Nonzero padding bit + ++pos; + } + return true; // Sanely reached EOF + } else { + // Continue by pretending we jumped to the next instruction + offset = pos - begin; + if (offset != jumps.back().first) return false; // Unreachable code + bits = jumps.back().second; // Restore the number of bits we would have had left after this jump + jumps.pop_back(); + } + } else if (opcode == Instruction::JUMP) { + uint32_t jump = DecodeJump(pos, endpos); + if (jump == INVALID) return false; // Jump offset straddles EOF + if (jump > endpos - pos) return false; // Jump out of range + if (bits == 0) return false; // Consuming bits past the end of the input + --bits; + uint32_t jump_offset = pos - begin + jump; + if (!jumps.empty() && jump_offset >= jumps.back().first) return false; // Intersecting jumps + jumps.emplace_back(jump_offset, bits); + } else if (opcode == Instruction::MATCH) { + uint32_t match = DecodeMatch(pos, endpos); + if (match == INVALID) return false; // Match bits straddle EOF + int matchlen = CountBits(match) - 1; + if (bits < matchlen) return false; // Consuming bits past the end of the input + bits -= matchlen; + } else if (opcode == Instruction::DEFAULT) { + uint32_t asn = DecodeASN(pos, endpos); + if (asn == INVALID) return false; // ASN straddles EOF + } else { + return false; // Instruction straddles EOF + } + } + return false; // Reached EOF without RETURN instruction +} -- cgit v1.2.3 From c81aefc5377888c7ac4f29f570249fd6c2fdb352 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Fri, 3 Apr 2020 11:09:21 -0700 Subject: Add additional effiency checks to sanity checker --- src/util/asmap.cpp | 11 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'src/util/asmap.cpp') diff --git a/src/util/asmap.cpp b/src/util/asmap.cpp index 5c3652f89b..5f3f53c393 100644 --- a/src/util/asmap.cpp +++ b/src/util/asmap.cpp @@ -126,11 +126,14 @@ bool SanityCheckASMap(const std::vector& asmap, int bits) std::vector::const_iterator pos = begin; std::vector> jumps; // All future positions we may jump to (bit offset in asmap -> bits to consume left) 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) return false; // There was a jump into the middle of the previous instruction Instruction opcode = DecodeType(pos, endpos); if (opcode == Instruction::RETURN) { + if (prevopcode == Instruction::DEFAULT) return false; // There should not be any RETURN immediately after a DEFAULT (could be combined into just RETURN) uint32_t asn = DecodeASN(pos, endpos); if (asn == INVALID) return false; // ASN straddles EOF if (jumps.empty()) { @@ -147,6 +150,7 @@ bool SanityCheckASMap(const std::vector& asmap, int bits) if (offset != jumps.back().first) return false; // Unreachable code bits = jumps.back().second; // Restore the number of bits we would have had left after this jump jumps.pop_back(); + prevopcode = Instruction::JUMP; } } else if (opcode == Instruction::JUMP) { uint32_t jump = DecodeJump(pos, endpos); @@ -157,15 +161,22 @@ bool SanityCheckASMap(const std::vector& asmap, int bits) uint32_t jump_offset = pos - begin + jump; if (!jumps.empty() && jump_offset >= jumps.back().first) return false; // Intersecting jumps jumps.emplace_back(jump_offset, bits); + prevopcode = Instruction::JUMP; } else if (opcode == Instruction::MATCH) { uint32_t match = DecodeMatch(pos, endpos); if (match == INVALID) return false; // Match bits straddle EOF int matchlen = CountBits(match) - 1; + if (prevopcode != Instruction::MATCH) had_incomplete_match = false; + if (matchlen < 8 && had_incomplete_match) return false; // Within a sequence of matches only at most one should be incomplete + had_incomplete_match = (matchlen < 8); if (bits < matchlen) return false; // Consuming bits past the end of the input bits -= matchlen; + prevopcode = Instruction::MATCH; } else if (opcode == Instruction::DEFAULT) { + if (prevopcode == Instruction::DEFAULT) return false; // There should not be two successive DEFAULTs (they could be combined into one) uint32_t asn = DecodeASN(pos, endpos); if (asn == INVALID) return false; // ASN straddles EOF + prevopcode = Instruction::DEFAULT; } else { return false; // Instruction straddles EOF } -- cgit v1.2.3 From 7cf97fda154ba837933eb05be5aeecfb69a06641 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Fri, 3 Apr 2020 13:32:34 -0700 Subject: Make asmap Interpreter errors fatal and fuzz test it --- src/util/asmap.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/util/asmap.cpp') diff --git a/src/util/asmap.cpp b/src/util/asmap.cpp index 5f3f53c393..f24a382d6e 100644 --- a/src/util/asmap.cpp +++ b/src/util/asmap.cpp @@ -116,7 +116,7 @@ uint32_t Interpret(const std::vector &asmap, const std::vector &ip) break; // Instruction straddles EOF } } - // Reached EOF without RETURN, or aborted (see any of the breaks above). + assert(false); // Reached EOF without RETURN, or aborted (see any of the breaks above) - should have been caught by SanityCheckASMap below return 0; // 0 is not a valid ASN } -- cgit v1.2.3