LCOV - code coverage report
Current view: top level - src/util - asmap.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 4 150 2.7 %
Date: 2023-11-06 23:13:05 Functions: 0 12 0.0 %
Branches: 4 188 2.1 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2019-2022 The Bitcoin Core developers
       2                 :            : // Distributed under the MIT software license, see the accompanying
       3                 :            : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4                 :            : 
       5                 :            : #include <util/asmap.h>
       6                 :            : 
       7                 :            : #include <clientversion.h>
       8                 :            : #include <crypto/common.h>
       9                 :            : #include <logging.h>
      10                 :            : #include <serialize.h>
      11                 :            : #include <streams.h>
      12                 :            : #include <util/fs.h>
      13                 :            : 
      14                 :            : #include <algorithm>
      15                 :            : #include <cassert>
      16                 :            : #include <cstdio>
      17                 :            : #include <utility>
      18                 :            : #include <vector>
      19                 :            : 
      20                 :            : namespace {
      21                 :            : 
      22                 :            : constexpr uint32_t INVALID = 0xFFFFFFFF;
      23                 :            : 
      24                 :          0 : uint32_t DecodeBits(std::vector<bool>::const_iterator& bitpos, const std::vector<bool>::const_iterator& endpos, uint8_t minval, const std::vector<uint8_t> &bit_sizes)
      25                 :            : {
      26                 :          0 :     uint32_t val = minval;
      27                 :            :     bool bit;
      28         [ #  # ]:          0 :     for (std::vector<uint8_t>::const_iterator bit_sizes_it = bit_sizes.begin();
      29                 :          0 :         bit_sizes_it != bit_sizes.end(); ++bit_sizes_it) {
      30         [ #  # ]:          0 :         if (bit_sizes_it + 1 != bit_sizes.end()) {
      31         [ #  # ]:          0 :             if (bitpos == endpos) break;
      32                 :          0 :             bit = *bitpos;
      33                 :          0 :             bitpos++;
      34                 :          0 :         } else {
      35                 :          0 :             bit = 0;
      36                 :            :         }
      37         [ #  # ]:          0 :         if (bit) {
      38                 :          0 :             val += (1 << *bit_sizes_it);
      39                 :          0 :         } else {
      40         [ #  # ]:          0 :             for (int b = 0; b < *bit_sizes_it; b++) {
      41         [ #  # ]:          0 :                 if (bitpos == endpos) return INVALID; // Reached EOF in mantissa
      42                 :          0 :                 bit = *bitpos;
      43                 :          0 :                 bitpos++;
      44                 :          0 :                 val += bit << (*bit_sizes_it - 1 - b);
      45                 :          0 :             }
      46                 :          0 :             return val;
      47                 :            :         }
      48                 :          0 :     }
      49                 :          0 :     return INVALID; // Reached EOF in exponent
      50                 :          0 : }
      51                 :            : 
      52                 :            : enum class Instruction : uint32_t
      53                 :            : {
      54                 :            :     RETURN = 0,
      55                 :            :     JUMP = 1,
      56                 :            :     MATCH = 2,
      57                 :            :     DEFAULT = 3,
      58                 :            : };
      59                 :            : 
      60         [ +  - ]:          2 : const std::vector<uint8_t> TYPE_BIT_SIZES{0, 0, 1};
      61                 :          0 : Instruction DecodeType(std::vector<bool>::const_iterator& bitpos, const std::vector<bool>::const_iterator& endpos)
      62                 :            : {
      63                 :          0 :     return Instruction(DecodeBits(bitpos, endpos, 0, TYPE_BIT_SIZES));
      64                 :            : }
      65                 :            : 
      66         [ +  - ]:          2 : const std::vector<uint8_t> ASN_BIT_SIZES{15, 16, 17, 18, 19, 20, 21, 22, 23, 24};
      67                 :          0 : uint32_t DecodeASN(std::vector<bool>::const_iterator& bitpos, const std::vector<bool>::const_iterator& endpos)
      68                 :            : {
      69                 :          0 :     return DecodeBits(bitpos, endpos, 1, ASN_BIT_SIZES);
      70                 :            : }
      71                 :            : 
      72                 :            : 
      73         [ +  - ]:          2 : const std::vector<uint8_t> MATCH_BIT_SIZES{1, 2, 3, 4, 5, 6, 7, 8};
      74                 :          0 : uint32_t DecodeMatch(std::vector<bool>::const_iterator& bitpos, const std::vector<bool>::const_iterator& endpos)
      75                 :            : {
      76                 :          0 :     return DecodeBits(bitpos, endpos, 2, MATCH_BIT_SIZES);
      77                 :            : }
      78                 :            : 
      79                 :            : 
      80         [ +  - ]:          2 : const std::vector<uint8_t> JUMP_BIT_SIZES{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30};
      81                 :          0 : uint32_t DecodeJump(std::vector<bool>::const_iterator& bitpos, const std::vector<bool>::const_iterator& endpos)
      82                 :            : {
      83                 :          0 :     return DecodeBits(bitpos, endpos, 17, JUMP_BIT_SIZES);
      84                 :            : }
      85                 :            : 
      86                 :            : }
      87                 :            : 
      88                 :          0 : uint32_t Interpret(const std::vector<bool> &asmap, const std::vector<bool> &ip)
      89                 :            : {
      90                 :          0 :     std::vector<bool>::const_iterator pos = asmap.begin();
      91                 :          0 :     const std::vector<bool>::const_iterator endpos = asmap.end();
      92                 :          0 :     uint8_t bits = ip.size();
      93                 :          0 :     uint32_t default_asn = 0;
      94                 :            :     uint32_t jump, match, matchlen;
      95                 :            :     Instruction opcode;
      96         [ #  # ]:          0 :     while (pos != endpos) {
      97                 :          0 :         opcode = DecodeType(pos, endpos);
      98         [ #  # ]:          0 :         if (opcode == Instruction::RETURN) {
      99                 :          0 :             default_asn = DecodeASN(pos, endpos);
     100         [ #  # ]:          0 :             if (default_asn == INVALID) break; // ASN straddles EOF
     101                 :          0 :             return default_asn;
     102         [ #  # ]:          0 :         } else if (opcode == Instruction::JUMP) {
     103                 :          0 :             jump = DecodeJump(pos, endpos);
     104         [ #  # ]:          0 :             if (jump == INVALID) break; // Jump offset straddles EOF
     105         [ #  # ]:          0 :             if (bits == 0) break; // No input bits left
     106         [ #  # ]:          0 :             if (int64_t{jump} >= int64_t{endpos - pos}) break; // Jumping past EOF
     107         [ #  # ]:          0 :             if (ip[ip.size() - bits]) {
     108                 :          0 :                 pos += jump;
     109                 :          0 :             }
     110                 :          0 :             bits--;
     111         [ #  # ]:          0 :         } else if (opcode == Instruction::MATCH) {
     112                 :          0 :             match = DecodeMatch(pos, endpos);
     113         [ #  # ]:          0 :             if (match == INVALID) break; // Match bits straddle EOF
     114                 :          0 :             matchlen = CountBits(match) - 1;
     115         [ #  # ]:          0 :             if (bits < matchlen) break; // Not enough input bits
     116         [ #  # ]:          0 :             for (uint32_t bit = 0; bit < matchlen; bit++) {
     117         [ #  # ]:          0 :                 if ((ip[ip.size() - bits]) != ((match >> (matchlen - 1 - bit)) & 1)) {
     118                 :          0 :                     return default_asn;
     119                 :            :                 }
     120                 :          0 :                 bits--;
     121                 :          0 :             }
     122         [ #  # ]:          0 :         } else if (opcode == Instruction::DEFAULT) {
     123                 :          0 :             default_asn = DecodeASN(pos, endpos);
     124         [ #  # ]:          0 :             if (default_asn == INVALID) break; // ASN straddles EOF
     125                 :          0 :         } else {
     126                 :          0 :             break; // Instruction straddles EOF
     127                 :            :         }
     128                 :            :     }
     129                 :          0 :     assert(false); // Reached EOF without RETURN, or aborted (see any of the breaks above) - should have been caught by SanityCheckASMap below
     130                 :            :     return 0; // 0 is not a valid ASN
     131                 :          0 : }
     132                 :            : 
     133                 :          0 : bool SanityCheckASMap(const std::vector<bool>& asmap, int bits)
     134                 :            : {
     135                 :          0 :     const std::vector<bool>::const_iterator begin = asmap.begin(), endpos = asmap.end();
     136                 :          0 :     std::vector<bool>::const_iterator pos = begin;
     137                 :          0 :     std::vector<std::pair<uint32_t, int>> jumps; // All future positions we may jump to (bit offset in asmap -> bits to consume left)
     138         [ #  # ]:          0 :     jumps.reserve(bits);
     139                 :          0 :     Instruction prevopcode = Instruction::JUMP;
     140                 :          0 :     bool had_incomplete_match = false;
     141 [ #  # ][ #  # ]:          0 :     while (pos != endpos) {
     142         [ #  # ]:          0 :         uint32_t offset = pos - begin;
     143 [ #  # ][ #  # ]:          0 :         if (!jumps.empty() && offset >= jumps.back().first) return false; // There was a jump into the middle of the previous instruction
     144         [ #  # ]:          0 :         Instruction opcode = DecodeType(pos, endpos);
     145         [ #  # ]:          0 :         if (opcode == Instruction::RETURN) {
     146         [ #  # ]:          0 :             if (prevopcode == Instruction::DEFAULT) return false; // There should not be any RETURN immediately after a DEFAULT (could be combined into just RETURN)
     147         [ #  # ]:          0 :             uint32_t asn = DecodeASN(pos, endpos);
     148         [ #  # ]:          0 :             if (asn == INVALID) return false; // ASN straddles EOF
     149         [ #  # ]:          0 :             if (jumps.empty()) {
     150                 :            :                 // Nothing to execute anymore
     151 [ #  # ][ #  # ]:          0 :                 if (endpos - pos > 7) return false; // Excessive padding
     152 [ #  # ][ #  # ]:          0 :                 while (pos != endpos) {
     153 [ #  # ][ #  # ]:          0 :                     if (*pos) return false; // Nonzero padding bit
     154         [ #  # ]:          0 :                     ++pos;
     155                 :            :                 }
     156                 :          0 :                 return true; // Sanely reached EOF
     157                 :            :             } else {
     158                 :            :                 // Continue by pretending we jumped to the next instruction
     159         [ #  # ]:          0 :                 offset = pos - begin;
     160         [ #  # ]:          0 :                 if (offset != jumps.back().first) return false; // Unreachable code
     161                 :          0 :                 bits = jumps.back().second; // Restore the number of bits we would have had left after this jump
     162                 :          0 :                 jumps.pop_back();
     163                 :          0 :                 prevopcode = Instruction::JUMP;
     164                 :            :             }
     165         [ #  # ]:          0 :         } else if (opcode == Instruction::JUMP) {
     166         [ #  # ]:          0 :             uint32_t jump = DecodeJump(pos, endpos);
     167         [ #  # ]:          0 :             if (jump == INVALID) return false; // Jump offset straddles EOF
     168 [ #  # ][ #  # ]:          0 :             if (int64_t{jump} > int64_t{endpos - pos}) return false; // Jump out of range
     169         [ #  # ]:          0 :             if (bits == 0) return false; // Consuming bits past the end of the input
     170                 :          0 :             --bits;
     171         [ #  # ]:          0 :             uint32_t jump_offset = pos - begin + jump;
     172 [ #  # ][ #  # ]:          0 :             if (!jumps.empty() && jump_offset >= jumps.back().first) return false; // Intersecting jumps
     173         [ #  # ]:          0 :             jumps.emplace_back(jump_offset, bits);
     174                 :          0 :             prevopcode = Instruction::JUMP;
     175         [ #  # ]:          0 :         } else if (opcode == Instruction::MATCH) {
     176         [ #  # ]:          0 :             uint32_t match = DecodeMatch(pos, endpos);
     177         [ #  # ]:          0 :             if (match == INVALID) return false; // Match bits straddle EOF
     178         [ #  # ]:          0 :             int matchlen = CountBits(match) - 1;
     179         [ #  # ]:          0 :             if (prevopcode != Instruction::MATCH) had_incomplete_match = false;
     180 [ #  # ][ #  # ]:          0 :             if (matchlen < 8 && had_incomplete_match) return false; // Within a sequence of matches only at most one should be incomplete
     181                 :          0 :             had_incomplete_match = (matchlen < 8);
     182         [ #  # ]:          0 :             if (bits < matchlen) return false; // Consuming bits past the end of the input
     183                 :          0 :             bits -= matchlen;
     184                 :          0 :             prevopcode = Instruction::MATCH;
     185         [ #  # ]:          0 :         } else if (opcode == Instruction::DEFAULT) {
     186         [ #  # ]:          0 :             if (prevopcode == Instruction::DEFAULT) return false; // There should not be two successive DEFAULTs (they could be combined into one)
     187         [ #  # ]:          0 :             uint32_t asn = DecodeASN(pos, endpos);
     188         [ #  # ]:          0 :             if (asn == INVALID) return false; // ASN straddles EOF
     189                 :          0 :             prevopcode = Instruction::DEFAULT;
     190                 :          0 :         } else {
     191                 :          0 :             return false; // Instruction straddles EOF
     192                 :            :         }
     193                 :            :     }
     194                 :          0 :     return false; // Reached EOF without RETURN instruction
     195                 :          0 : }
     196                 :            : 
     197                 :          0 : std::vector<bool> DecodeAsmap(fs::path path)
     198                 :            : {
     199                 :          0 :     std::vector<bool> bits;
     200         [ #  # ]:          0 :     FILE *filestr = fsbridge::fopen(path, "rb");
     201         [ #  # ]:          0 :     AutoFile file{filestr};
     202 [ #  # ][ #  # ]:          0 :     if (file.IsNull()) {
     203 [ #  # ][ #  # ]:          0 :         LogPrintf("Failed to open asmap file from disk\n");
                 [ #  # ]
     204                 :          0 :         return bits;
     205                 :            :     }
     206         [ #  # ]:          0 :     fseek(filestr, 0, SEEK_END);
     207         [ #  # ]:          0 :     int length = ftell(filestr);
     208 [ #  # ][ #  # ]:          0 :     LogPrintf("Opened asmap file %s (%d bytes) from disk\n", fs::quoted(fs::PathToString(path)), length);
         [ #  # ][ #  # ]
                 [ #  # ]
     209         [ #  # ]:          0 :     fseek(filestr, 0, SEEK_SET);
     210                 :            :     uint8_t cur_byte;
     211         [ #  # ]:          0 :     for (int i = 0; i < length; ++i) {
     212         [ #  # ]:          0 :         file >> cur_byte;
     213         [ #  # ]:          0 :         for (int bit = 0; bit < 8; ++bit) {
     214         [ #  # ]:          0 :             bits.push_back((cur_byte >> bit) & 1);
     215                 :          0 :         }
     216                 :          0 :     }
     217 [ #  # ][ #  # ]:          0 :     if (!SanityCheckASMap(bits, 128)) {
     218 [ #  # ][ #  # ]:          0 :         LogPrintf("Sanity check of asmap file %s failed\n", fs::quoted(fs::PathToString(path)));
         [ #  # ][ #  # ]
                 [ #  # ]
     219                 :          0 :         return {};
     220                 :            :     }
     221                 :          0 :     return bits;
     222                 :          0 : }
     223                 :            : 

Generated by: LCOV version 1.14