LCOV - code coverage report
Current view: top level - src/test/fuzz - txrequest.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 24 209 11.5 %
Date: 2023-10-05 12:38:51 Functions: 8 24 33.3 %
Branches: 13 216 6.0 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2020-2021 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 <crypto/common.h>
       6                 :            : #include <crypto/sha256.h>
       7                 :            : #include <crypto/siphash.h>
       8                 :            : #include <primitives/transaction.h>
       9                 :            : #include <test/fuzz/fuzz.h>
      10                 :            : #include <txrequest.h>
      11                 :            : 
      12                 :            : #include <bitset>
      13                 :            : #include <cstdint>
      14                 :            : #include <queue>
      15                 :            : #include <vector>
      16                 :            : 
      17         [ +  - ]:          2 : namespace {
      18         [ +  - ]:          2 : 
      19                 :            : constexpr int MAX_TXHASHES = 16;
      20                 :            : constexpr int MAX_PEERS = 16;
      21                 :            : 
      22                 :            : //! Randomly generated GenTxids used in this test (length is MAX_TXHASHES).
      23                 :            : uint256 TXHASHES[MAX_TXHASHES];
      24                 :            : 
      25         [ +  - ]:          2 : //! Precomputed random durations (positive and negative, each ~exponentially distributed).
      26                 :            : std::chrono::microseconds DELAYS[256];
      27                 :            : 
      28                 :            : struct Initializer
      29                 :            : {
      30                 :          2 :     Initializer()
      31                 :            :     {
      32         [ +  + ]:         34 :         for (uint8_t txhash = 0; txhash < MAX_TXHASHES; txhash += 1) {
      33                 :         32 :             CSHA256().Write(&txhash, 1).Finalize(TXHASHES[txhash].begin());
      34                 :         32 :         }
      35                 :          2 :         int i = 0;
      36                 :            :         // DELAYS[N] for N=0..15 is just N microseconds.
      37         [ +  + ]:         34 :         for (; i < 16; ++i) {
      38                 :         32 :             DELAYS[i] = std::chrono::microseconds{i};
      39                 :         32 :         }
      40                 :            :         // DELAYS[N] for N=16..127 has randomly-looking but roughly exponentially increasing values up to
      41                 :            :         // 198.416453 seconds.
      42         [ +  + ]:        226 :         for (; i < 128; ++i) {
      43                 :        224 :             int diff_bits = ((i - 10) * 2) / 9;
      44                 :        224 :             uint64_t diff = 1 + (CSipHasher(0, 0).Write(i).Finalize() >> (64 - diff_bits));
      45                 :        224 :             DELAYS[i] = DELAYS[i - 1] + std::chrono::microseconds{diff};
      46                 :        224 :         }
      47                 :            :         // DELAYS[N] for N=128..255 are negative delays with the same magnitude as N=0..127.
      48         [ +  + ]:        258 :         for (; i < 256; ++i) {
      49                 :        256 :             DELAYS[i] = -DELAYS[255 - i];
      50                 :        256 :         }
      51                 :          2 :     }
      52                 :          2 : } g_initializer;
      53                 :            : 
      54                 :            : /** Tester class for TxRequestTracker
      55                 :            :  *
      56                 :            :  * It includes a naive reimplementation of its behavior, for a limited set
      57                 :            :  * of MAX_TXHASHES distinct txids, and MAX_PEERS peer identifiers.
      58                 :            :  *
      59                 :            :  * All of the public member functions perform the same operation on
      60                 :            :  * an actual TxRequestTracker and on the state of the reimplementation.
      61                 :            :  * The output of GetRequestable is compared with the expected value
      62                 :            :  * as well.
      63                 :            :  *
      64                 :            :  * Check() calls the TxRequestTracker's sanity check, plus compares the
      65                 :            :  * output of the constant accessors (Size(), CountLoad(), CountTracked())
      66                 :            :  * with expected values.
      67                 :            :  */
      68                 :            : class Tester
      69                 :            : {
      70                 :            :     //! TxRequestTracker object being tested.
      71                 :            :     TxRequestTracker m_tracker;
      72                 :            : 
      73                 :            :     //! States for txid/peer combinations in the naive data structure.
      74                 :          2 :     enum class State {
      75                 :            :         NOTHING, //!< Absence of this txid/peer combination
      76                 :            : 
      77                 :            :         // Note that this implementation does not distinguish between DELAYED/READY/BEST variants of CANDIDATE.
      78                 :            :         CANDIDATE,
      79                 :            :         REQUESTED,
      80                 :            :         COMPLETED,
      81                 :            :     };
      82                 :            : 
      83         [ +  - ]:          2 :     //! Sequence numbers, incremented whenever a new CANDIDATE is added.
      84                 :          0 :     uint64_t m_current_sequence{0};
      85                 :            : 
      86                 :            :     //! List of future 'events' (all inserted reqtimes/exptimes). This is used to implement AdvanceToEvent.
      87                 :            :     std::priority_queue<std::chrono::microseconds, std::vector<std::chrono::microseconds>,
      88                 :            :         std::greater<std::chrono::microseconds>> m_events;
      89                 :            : 
      90                 :            :     //! Information about a txhash/peer combination.
      91                 :          0 :     struct Announcement
      92                 :            :     {
      93                 :            :         std::chrono::microseconds m_time;
      94                 :            :         uint64_t m_sequence;
      95                 :          0 :         State m_state{State::NOTHING};
      96                 :            :         bool m_preferred;
      97                 :            :         bool m_is_wtxid;
      98                 :            :         uint64_t m_priority; //!< Precomputed priority.
      99                 :            :     };
     100                 :            : 
     101                 :            :     //! Information about all txhash/peer combination.
     102                 :            :     Announcement m_announcements[MAX_TXHASHES][MAX_PEERS];
     103                 :            : 
     104                 :            :     //! The current time; can move forward and backward.
     105         [ #  # ]:          0 :     std::chrono::microseconds m_now{244466666};
     106                 :            : 
     107                 :            :     //! Delete txhashes whose only announcements are COMPLETED.
     108                 :          0 :     void Cleanup(int txhash)
     109                 :            :     {
     110                 :          0 :         bool all_nothing = true;
     111         [ #  # ]:          0 :         for (int peer = 0; peer < MAX_PEERS; ++peer) {
     112                 :          0 :             const Announcement& ann = m_announcements[txhash][peer];
     113         [ #  # ]:          0 :             if (ann.m_state != State::NOTHING) {
     114         [ #  # ]:          0 :                 if (ann.m_state != State::COMPLETED) return;
     115                 :          0 :                 all_nothing = false;
     116                 :          0 :             }
     117                 :          0 :         }
     118         [ #  # ]:          0 :         if (all_nothing) return;
     119         [ #  # ]:          0 :         for (int peer = 0; peer < MAX_PEERS; ++peer) {
     120                 :          0 :             m_announcements[txhash][peer].m_state = State::NOTHING;
     121                 :          0 :         }
     122                 :          0 :     }
     123                 :            : 
     124                 :            :     //! Find the current best peer to request from for a txhash (or -1 if none).
     125                 :          0 :     int GetSelected(int txhash) const
     126                 :            :     {
     127                 :          0 :         int ret = -1;
     128                 :          0 :         uint64_t ret_priority = 0;
     129         [ #  # ]:          0 :         for (int peer = 0; peer < MAX_PEERS; ++peer) {
     130                 :          0 :             const Announcement& ann = m_announcements[txhash][peer];
     131                 :            :             // Return -1 if there already is a (non-expired) in-flight request.
     132         [ #  # ]:          0 :             if (ann.m_state == State::REQUESTED) return -1;
     133                 :            :             // If it's a viable candidate, see if it has lower priority than the best one so far.
     134   [ #  #  #  # ]:          0 :             if (ann.m_state == State::CANDIDATE && ann.m_time <= m_now) {
     135   [ #  #  #  # ]:          0 :                 if (ret == -1 || ann.m_priority > ret_priority) {
     136                 :          0 :                     std::tie(ret, ret_priority) = std::tie(peer, ann.m_priority);
     137                 :          0 :                 }
     138                 :          0 :             }
     139                 :          0 :         }
     140                 :          0 :         return ret;
     141                 :          0 :     }
     142                 :            : 
     143                 :            : public:
     144   [ #  #  #  # ]:          0 :     Tester() : m_tracker(true) {}
     145                 :            : 
     146                 :          0 :     std::chrono::microseconds Now() const { return m_now; }
     147                 :            : 
     148                 :          0 :     void AdvanceTime(std::chrono::microseconds offset)
     149                 :            :     {
     150                 :          0 :         m_now += offset;
     151   [ #  #  #  # ]:          0 :         while (!m_events.empty() && m_events.top() <= m_now) m_events.pop();
     152                 :          0 :     }
     153                 :            : 
     154                 :          0 :     void AdvanceToEvent()
     155                 :            :     {
     156   [ #  #  #  # ]:          0 :         while (!m_events.empty() && m_events.top() <= m_now) m_events.pop();
     157         [ #  # ]:          0 :         if (!m_events.empty()) {
     158                 :          0 :             m_now = m_events.top();
     159                 :          0 :             m_events.pop();
     160                 :          0 :         }
     161                 :          0 :     }
     162                 :            : 
     163                 :          0 :     void DisconnectedPeer(int peer)
     164                 :            :     {
     165                 :            :         // Apply to naive structure: all announcements for that peer are wiped.
     166         [ #  # ]:          0 :         for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
     167         [ #  # ]:          0 :             if (m_announcements[txhash][peer].m_state != State::NOTHING) {
     168                 :          0 :                 m_announcements[txhash][peer].m_state = State::NOTHING;
     169                 :          0 :                 Cleanup(txhash);
     170                 :          0 :             }
     171                 :          0 :         }
     172                 :            : 
     173                 :            :         // Call TxRequestTracker's implementation.
     174                 :          0 :         m_tracker.DisconnectedPeer(peer);
     175                 :          0 :     }
     176                 :            : 
     177                 :          0 :     void ForgetTxHash(int txhash)
     178                 :            :     {
     179                 :            :         // Apply to naive structure: all announcements for that txhash are wiped.
     180         [ #  # ]:          0 :         for (int peer = 0; peer < MAX_PEERS; ++peer) {
     181                 :          0 :             m_announcements[txhash][peer].m_state = State::NOTHING;
     182                 :          0 :         }
     183                 :          0 :         Cleanup(txhash);
     184                 :            : 
     185                 :            :         // Call TxRequestTracker's implementation.
     186                 :          0 :         m_tracker.ForgetTxHash(TXHASHES[txhash]);
     187                 :          0 :     }
     188                 :            : 
     189                 :          0 :     void ReceivedInv(int peer, int txhash, bool is_wtxid, bool preferred, std::chrono::microseconds reqtime)
     190                 :            :     {
     191                 :            :         // Apply to naive structure: if no announcement for txidnum/peer combination
     192                 :            :         // already, create a new CANDIDATE; otherwise do nothing.
     193                 :          0 :         Announcement& ann = m_announcements[txhash][peer];
     194         [ #  # ]:          0 :         if (ann.m_state == State::NOTHING) {
     195                 :          0 :             ann.m_preferred = preferred;
     196                 :          0 :             ann.m_state = State::CANDIDATE;
     197                 :          0 :             ann.m_time = reqtime;
     198                 :          0 :             ann.m_is_wtxid = is_wtxid;
     199                 :          0 :             ann.m_sequence = m_current_sequence++;
     200                 :          0 :             ann.m_priority = m_tracker.ComputePriority(TXHASHES[txhash], peer, ann.m_preferred);
     201                 :            : 
     202                 :            :             // Add event so that AdvanceToEvent can quickly jump to the point where its reqtime passes.
     203         [ #  # ]:          0 :             if (reqtime > m_now) m_events.push(reqtime);
     204                 :          0 :         }
     205                 :            : 
     206                 :            :         // Call TxRequestTracker's implementation.
     207         [ #  # ]:          0 :         m_tracker.ReceivedInv(peer, is_wtxid ? GenTxid::Wtxid(TXHASHES[txhash]) : GenTxid::Txid(TXHASHES[txhash]), preferred, reqtime);
     208                 :          0 :     }
     209                 :            : 
     210                 :          0 :     void RequestedTx(int peer, int txhash, std::chrono::microseconds exptime)
     211                 :            :     {
     212                 :            :         // Apply to naive structure: if a CANDIDATE announcement exists for peer/txhash,
     213                 :            :         // convert it to REQUESTED, and change any existing REQUESTED announcement for the same txhash to COMPLETED.
     214         [ #  # ]:          0 :         if (m_announcements[txhash][peer].m_state == State::CANDIDATE) {
     215         [ #  # ]:          0 :             for (int peer2 = 0; peer2 < MAX_PEERS; ++peer2) {
     216         [ #  # ]:          0 :                 if (m_announcements[txhash][peer2].m_state == State::REQUESTED) {
     217                 :          0 :                     m_announcements[txhash][peer2].m_state = State::COMPLETED;
     218                 :          0 :                 }
     219                 :          0 :             }
     220                 :          0 :             m_announcements[txhash][peer].m_state = State::REQUESTED;
     221                 :          0 :             m_announcements[txhash][peer].m_time = exptime;
     222                 :          0 :         }
     223                 :            : 
     224                 :            :         // Add event so that AdvanceToEvent can quickly jump to the point where its exptime passes.
     225         [ #  # ]:          0 :         if (exptime > m_now) m_events.push(exptime);
     226                 :            : 
     227                 :            :         // Call TxRequestTracker's implementation.
     228                 :          0 :         m_tracker.RequestedTx(peer, TXHASHES[txhash], exptime);
     229                 :          0 :     }
     230                 :            : 
     231                 :          0 :     void ReceivedResponse(int peer, int txhash)
     232                 :            :     {
     233                 :            :         // Apply to naive structure: convert anything to COMPLETED.
     234         [ #  # ]:          0 :         if (m_announcements[txhash][peer].m_state != State::NOTHING) {
     235                 :          0 :             m_announcements[txhash][peer].m_state = State::COMPLETED;
     236                 :          0 :             Cleanup(txhash);
     237                 :          0 :         }
     238                 :            : 
     239                 :            :         // Call TxRequestTracker's implementation.
     240                 :          0 :         m_tracker.ReceivedResponse(peer, TXHASHES[txhash]);
     241                 :          0 :     }
     242                 :            : 
     243                 :          0 :     void GetRequestable(int peer)
     244                 :            :     {
     245                 :            :         // Implement using naive structure:
     246                 :            : 
     247                 :            :         //! list of (sequence number, txhash, is_wtxid) tuples.
     248                 :          0 :         std::vector<std::tuple<uint64_t, int, bool>> result;
     249                 :          0 :         std::vector<std::pair<NodeId, GenTxid>> expected_expired;
     250         [ #  # ]:          0 :         for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
     251                 :            :             // Mark any expired REQUESTED announcements as COMPLETED.
     252         [ #  # ]:          0 :             for (int peer2 = 0; peer2 < MAX_PEERS; ++peer2) {
     253                 :          0 :                 Announcement& ann2 = m_announcements[txhash][peer2];
     254   [ #  #  #  #  :          0 :                 if (ann2.m_state == State::REQUESTED && ann2.m_time <= m_now) {
                   #  # ]
     255   [ #  #  #  #  :          0 :                     expected_expired.emplace_back(peer2, ann2.m_is_wtxid ? GenTxid::Wtxid(TXHASHES[txhash]) : GenTxid::Txid(TXHASHES[txhash]));
             #  #  #  # ]
     256                 :          0 :                     ann2.m_state = State::COMPLETED;
     257                 :          0 :                     break;
     258                 :            :                 }
     259                 :          0 :             }
     260                 :            :             // And delete txids with only COMPLETED announcements left.
     261         [ #  # ]:          0 :             Cleanup(txhash);
     262                 :            :             // CANDIDATEs for which this announcement has the highest priority get returned.
     263                 :          0 :             const Announcement& ann = m_announcements[txhash][peer];
     264   [ #  #  #  #  :          0 :             if (ann.m_state == State::CANDIDATE && GetSelected(txhash) == peer) {
                   #  # ]
     265         [ #  # ]:          0 :                 result.emplace_back(ann.m_sequence, txhash, ann.m_is_wtxid);
     266                 :          0 :             }
     267                 :          0 :         }
     268                 :            :         // Sort the results by sequence number.
     269         [ #  # ]:          0 :         std::sort(result.begin(), result.end());
     270         [ #  # ]:          0 :         std::sort(expected_expired.begin(), expected_expired.end());
     271                 :            : 
     272                 :            :         // Compare with TxRequestTracker's implementation.
     273                 :          0 :         std::vector<std::pair<NodeId, GenTxid>> expired;
     274         [ #  # ]:          0 :         const auto actual = m_tracker.GetRequestable(peer, m_now, &expired);
     275         [ #  # ]:          0 :         std::sort(expired.begin(), expired.end());
     276   [ #  #  #  # ]:          0 :         assert(expired == expected_expired);
     277                 :            : 
     278         [ #  # ]:          0 :         m_tracker.PostGetRequestableSanityCheck(m_now);
     279         [ #  # ]:          0 :         assert(result.size() == actual.size());
     280         [ #  # ]:          0 :         for (size_t pos = 0; pos < actual.size(); ++pos) {
     281   [ #  #  #  #  :          0 :             assert(TXHASHES[std::get<1>(result[pos])] == actual[pos].GetHash());
                   #  # ]
     282   [ #  #  #  # ]:          0 :             assert(std::get<2>(result[pos]) == actual[pos].IsWtxid());
     283                 :          0 :         }
     284                 :          0 :     }
     285                 :            : 
     286                 :          0 :     void Check()
     287                 :            :     {
     288                 :            :         // Compare CountTracked and CountLoad with naive structure.
     289                 :          0 :         size_t total = 0;
     290         [ #  # ]:          0 :         for (int peer = 0; peer < MAX_PEERS; ++peer) {
     291                 :          0 :             size_t tracked = 0;
     292                 :          0 :             size_t inflight = 0;
     293                 :          0 :             size_t candidates = 0;
     294         [ #  # ]:          0 :             for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
     295                 :          0 :                 tracked += m_announcements[txhash][peer].m_state != State::NOTHING;
     296                 :          0 :                 inflight += m_announcements[txhash][peer].m_state == State::REQUESTED;
     297                 :          0 :                 candidates += m_announcements[txhash][peer].m_state == State::CANDIDATE;
     298                 :          0 :             }
     299         [ #  # ]:          0 :             assert(m_tracker.Count(peer) == tracked);
     300         [ #  # ]:          0 :             assert(m_tracker.CountInFlight(peer) == inflight);
     301         [ #  # ]:          0 :             assert(m_tracker.CountCandidates(peer) == candidates);
     302                 :          0 :             total += tracked;
     303                 :          0 :         }
     304                 :            :         // Compare Size.
     305         [ #  # ]:          0 :         assert(m_tracker.Size() == total);
     306                 :            : 
     307                 :            :         // Invoke internal consistency check of TxRequestTracker object.
     308                 :          0 :         m_tracker.SanityCheck();
     309                 :          0 :     }
     310                 :            : };
     311                 :            : } // namespace
     312                 :            : 
     313         [ -  + ]:          4 : FUZZ_TARGET(txrequest)
     314                 :            : {
     315                 :            :     // Tester object (which encapsulates a TxRequestTracker).
     316                 :          0 :     Tester tester;
     317                 :            : 
     318                 :            :     // Decode the input as a sequence of instructions with parameters
     319                 :          0 :     auto it = buffer.begin();
     320         [ #  # ]:          0 :     while (it != buffer.end()) {
     321                 :          0 :         int cmd = *(it++) % 11;
     322                 :            :         int peer, txidnum, delaynum;
     323   [ #  #  #  #  :          0 :         switch (cmd) {
          #  #  #  #  #  
                      # ]
     324                 :            :         case 0: // Make time jump to the next event (m_time of CANDIDATE or REQUESTED)
     325         [ #  # ]:          0 :             tester.AdvanceToEvent();
     326                 :          0 :             break;
     327                 :            :         case 1: // Change time
     328         [ #  # ]:          0 :             delaynum = it == buffer.end() ? 0 : *(it++);
     329         [ #  # ]:          0 :             tester.AdvanceTime(DELAYS[delaynum]);
     330                 :          0 :             break;
     331                 :            :         case 2: // Query for requestable txs
     332         [ #  # ]:          0 :             peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
     333         [ #  # ]:          0 :             tester.GetRequestable(peer);
     334                 :          0 :             break;
     335                 :            :         case 3: // Peer went offline
     336         [ #  # ]:          0 :             peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
     337         [ #  # ]:          0 :             tester.DisconnectedPeer(peer);
     338                 :          0 :             break;
     339                 :            :         case 4: // No longer need tx
     340         [ #  # ]:          0 :             txidnum = it == buffer.end() ? 0 : *(it++);
     341         [ #  # ]:          0 :             tester.ForgetTxHash(txidnum % MAX_TXHASHES);
     342                 :          0 :             break;
     343                 :            :         case 5: // Received immediate preferred inv
     344                 :            :         case 6: // Same, but non-preferred.
     345         [ #  # ]:          0 :             peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
     346         [ #  # ]:          0 :             txidnum = it == buffer.end() ? 0 : *(it++);
     347   [ #  #  #  # ]:          0 :             tester.ReceivedInv(peer, txidnum % MAX_TXHASHES, (txidnum / MAX_TXHASHES) & 1, cmd & 1,
     348                 :          0 :                 std::chrono::microseconds::min());
     349                 :          0 :             break;
     350                 :            :         case 7: // Received delayed preferred inv
     351                 :            :         case 8: // Same, but non-preferred.
     352         [ #  # ]:          0 :             peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
     353         [ #  # ]:          0 :             txidnum = it == buffer.end() ? 0 : *(it++);
     354         [ #  # ]:          0 :             delaynum = it == buffer.end() ? 0 : *(it++);
     355         [ #  # ]:          0 :             tester.ReceivedInv(peer, txidnum % MAX_TXHASHES, (txidnum / MAX_TXHASHES) & 1, cmd & 1,
     356   [ #  #  #  # ]:          0 :                 tester.Now() + DELAYS[delaynum]);
     357                 :          0 :             break;
     358                 :            :         case 9: // Requested tx from peer
     359         [ #  # ]:          0 :             peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
     360         [ #  # ]:          0 :             txidnum = it == buffer.end() ? 0 : *(it++);
     361         [ #  # ]:          0 :             delaynum = it == buffer.end() ? 0 : *(it++);
     362   [ #  #  #  #  :          0 :             tester.RequestedTx(peer, txidnum % MAX_TXHASHES, tester.Now() + DELAYS[delaynum]);
                   #  # ]
     363                 :          0 :             break;
     364                 :            :         case 10: // Received response
     365         [ #  # ]:          0 :             peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
     366         [ #  # ]:          0 :             txidnum = it == buffer.end() ? 0 : *(it++);
     367         [ #  # ]:          0 :             tester.ReceivedResponse(peer, txidnum % MAX_TXHASHES);
     368                 :          0 :             break;
     369                 :            :         default:
     370                 :          0 :             assert(false);
     371                 :            :         }
     372                 :            :     }
     373         [ #  # ]:          0 :     tester.Check();
     374                 :          0 : }

Generated by: LCOV version 1.14