From fffd8dca2de39ad4a683f0dce57cdca55ed2f600 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Thu, 2 Apr 2020 18:18:08 -0700
Subject: Add asmap sanity checker

---
 src/addrman.cpp    |  4 ++++
 src/netaddress.cpp |  5 +++++
 src/netaddress.h   |  2 ++
 src/util/asmap.cpp | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/util/asmap.h   |  5 +++++
 5 files changed, 70 insertions(+)

(limited to 'src')

diff --git a/src/addrman.cpp b/src/addrman.cpp
index 2f8a3a0bd5..b22ad6d641 100644
--- a/src/addrman.cpp
+++ b/src/addrman.cpp
@@ -644,5 +644,9 @@ std::vector<bool> CAddrMan::DecodeAsmap(fs::path path)
             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.cpp b/src/netaddress.cpp
index 228caf74a9..e0b27b1d7c 100644
--- a/src/netaddress.cpp
+++ b/src/netaddress.cpp
@@ -894,3 +894,8 @@ bool operator<(const CSubNet& a, const CSubNet& b)
 {
     return (a.network < b.network || (a.network == b.network && memcmp(a.netmask, b.netmask, 16) < 0));
 }
+
+bool SanityCheckASMap(const std::vector<bool>& asmap)
+{
+    return SanityCheckASMap(asmap, 128); // For IP address lookups, the input is 128 bits
+}
diff --git a/src/netaddress.h b/src/netaddress.h
index b7381c1eb4..ec06a588bf 100644
--- a/src/netaddress.h
+++ b/src/netaddress.h
@@ -180,4 +180,6 @@ class CService : public CNetAddr
         }
 };
 
+bool SanityCheckASMap(const std::vector<bool>& asmap);
+
 #endif // BITCOIN_NETADDRESS_H
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 <map>
 #include <vector>
 #include <assert.h>
 #include <crypto/common.h>
@@ -118,3 +119,56 @@ uint32_t Interpret(const std::vector<bool> &asmap, const std::vector<bool> &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<bool>& asmap, int bits)
+{
+    const std::vector<bool>::const_iterator begin = asmap.begin(), endpos = asmap.end();
+    std::vector<bool>::const_iterator pos = begin;
+    std::vector<std::pair<uint32_t, int>> 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
+}
diff --git a/src/util/asmap.h b/src/util/asmap.h
index a0e14013c5..b31e639bb5 100644
--- 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 <stdint.h>
+#include <vector>
+
 uint32_t Interpret(const std::vector<bool> &asmap, const std::vector<bool> &ip);
 
+bool SanityCheckASMap(const std::vector<bool>& asmap, int bits);
+
 #endif // BITCOIN_UTIL_ASMAP_H
-- 
cgit v1.2.3