/root/bitcoin/src/test/fuzz/util/descriptor.cpp

Source
// Copyright (c) 2023-present 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 <test/fuzz/util/descriptor.h>

#include <key.h>
#include <key_io.h>
#include <pubkey.h>
#include <span.h>
#include <util/strencodings.h>

#include <ranges>
#include <stack>
#include <vector>

void MockedDescriptorConverter::Init()
{
    // The data to use as a private key or a seed for an xprv.
    std::array<std::byte, 32> key_data{std::byte{1}};
    // Generate keys of all kinds and store them in the keys array.
    for (size_t i{0}; i < TOTAL_KEYS_GENERATED; i++) {
        key_data[31] = std::byte(i);

        // If this is a "raw" key, generate a normal privkey. Otherwise generate
        // an extended one.
        if (IdIsCompPubKey(i) || IdIsUnCompPubKey(i) || IdIsXOnlyPubKey(i) || IdIsConstPrivKey(i)) {
            CKey privkey;
            privkey.Set(key_data.begin(), key_data.end(), !IdIsUnCompPubKey(i));
            if (IdIsCompPubKey(i) || IdIsUnCompPubKey(i)) {
                CPubKey pubkey{privkey.GetPubKey()};
                keys_str[i] = HexStr(pubkey);
            } else if (IdIsXOnlyPubKey(i)) {
                const XOnlyPubKey pubkey{privkey.GetPubKey()};
                keys_str[i] = HexStr(pubkey);
            } else {
                keys_str[i] = EncodeSecret(privkey);
            }
        } else {
            CExtKey ext_privkey;
            ext_privkey.SetSeed(key_data);
            if (IdIsXprv(i)) {
                keys_str[i] = EncodeExtKey(ext_privkey);
            } else {
                const CExtPubKey ext_pubkey{ext_privkey.Neuter()};
                keys_str[i] = EncodeExtPubKey(ext_pubkey);
            }
        }
    }
}

std::optional<uint8_t> MockedDescriptorConverter::IdxFromHex(std::string_view hex_characters) const {
    if (hex_characters.size() != 2) return {};
    auto idx = ParseHex(hex_characters);
    if (idx.size() != 1) return {};
    return idx[0];
}

std::optional<std::string> MockedDescriptorConverter::GetDescriptor(std::string_view mocked_desc) const {
    // The smallest fragment would be "pk(%00)"
    if (mocked_desc.size() < 7) return {};

    // The actual descriptor string to be returned.
    std::string desc;
    desc.reserve(mocked_desc.size());

    // Replace all occurrences of '%' followed by two hex characters with the corresponding key.
    for (size_t i = 0; i < mocked_desc.size();) {
        if (mocked_desc[i] == '%') {
            if (i + 3 >= mocked_desc.size()) return {};
            if (const auto idx = IdxFromHex(mocked_desc.substr(i + 1, 2))) {
                desc += keys_str[*idx];
                i += 3;
            } else {
                return {};
            }
        } else {
            desc += mocked_desc[i++];
        }
    }

    return desc;
}

bool HasDeepDerivPath(std::span<const uint8_t> buff, const int max_depth)
{
    auto depth{0};
    for (const auto& ch: buff) {
        if (ch == ',') {
            // A comma is always present between two key expressions, so we use that as a delimiter.
            depth = 0;
        } else if (ch == '/') {
            if (++depth > max_depth) return true;
        }
    }
    return false;
}

bool HasTooManySubFrag(std::span<const uint8_t> buff, const int max_subs, const size_t max_nested_subs)
{
    // We use a stack because there may be many nested sub-frags.
    std::stack<int> counts;
    for (const auto& ch: buff) {
        // The fuzzer may generate an input with a ton of parentheses. Rule out pathological cases.
        if (counts.size() > max_nested_subs) return true;

        if (ch == '(') {
            // A new fragment was opened, create a new sub-count for it and start as one since any fragment with
            // parentheses has at least one sub.
            counts.push(1);
        } else if (ch == ',' && !counts.empty()) {
            // When encountering a comma, account for an additional sub in the last opened fragment. If it exceeds the
            // limit, bail.
            if (++counts.top() > max_subs) return true;
        } else if (ch == ')' && !counts.empty()) {
            // Fragment closed! Drop its sub count and resume to counting the number of subs for its parent.
            counts.pop();
        }
    }
    return false;
}

bool HasTooManyWrappers(std::span<const uint8_t> buff, const int max_wrappers)
{
    // The number of nested wrappers. Nested wrappers are always characters which follow each other so we don't have to
    // use a stack as we do above when counting the number of sub-fragments.
    std::optional<int> count;

    // We want to detect nested wrappers. A wrapper is a character prepended to a fragment, separated by a colon. There
    // may be more than one wrapper, in which case the colon is not repeated. For instance `jjjjj:pk()`.  To count
    // wrappers we iterate in reverse and use the colon to detect the end of a wrapper expression and count how many
    // characters there are since the beginning of the expression. We stop counting when we encounter a character
    // indicating the beginning of a new expression.
    for (const auto ch: buff | std::views::reverse) {
        // A colon, start counting.
        if (ch == ':') {
            // The colon itself is not a wrapper so we start at 0.
            count = 0;
        } else if (count) {
            // If we are counting wrappers, stop when we crossed the beginning of the wrapper expression. Otherwise keep
            // counting and bail if we reached the limit.
            // A wrapper may only ever occur as the first sub of a descriptor/miniscript expression ('('), as the
            // first Taproot leaf in a pair ('{') or as the nth sub in each case (',').
            if (ch == ',' || ch == '(' || ch == '{') {
                count.reset();
            } else if (++*count > max_wrappers) {
                return true;
            }
        }
    }

    return false;
}

bool HasTooLargeLeafSize(std::span<const uint8_t> buff, const uint32_t max_leaf_size)
{
    uint32_t leaf_len{0};
    for (auto c : buff) {
        if (c == '(' || c == ')' || c == ',' || c == '{' || c == '}') {
            // Possibly start a fresh leaf, or a fresh function name (with
            // wrappers), or terminate a prior leaf.
            leaf_len = 0;
        } else {
            // Just treat everything else as a leaf. This will also reject long
            // function names, but this should be fine if the max_leaf_size is
            // set large enough.
            if (++leaf_len > max_leaf_size) {
                return true;
            }
        }
    }
    return false;
}

Line	Count	Source
1		// Copyright (c) 2023-present 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 <test/fuzz/util/descriptor.h>
6
7		#include <key.h>
8		#include <key_io.h>
9		#include <pubkey.h>
10		#include <span.h>
11		#include <util/strencodings.h>
12
13		#include <ranges>
14		#include <stack>
15		#include <vector>
16
17		void MockedDescriptorConverter::Init()
18	0	{
19		// The data to use as a private key or a seed for an xprv.
20	0	std::array<std::byte, 32> key_data{std::byte{1}};
21		// Generate keys of all kinds and store them in the keys array.
22	0	for (size_t i{0}; i < TOTAL_KEYS_GENERATED; i++) { Branch (22:23): [True: 0, False: 0]
23	0	key_data[31] = std::byte(i);
24
25		// If this is a "raw" key, generate a normal privkey. Otherwise generate
26		// an extended one.
27	0	if (IdIsCompPubKey(i) \|\| IdIsUnCompPubKey(i) \|\| IdIsXOnlyPubKey(i) \|\| IdIsConstPrivKey(i)) { Branch (27:13): [True: 0, False: 0] Branch (27:34): [True: 0, False: 0] Branch (27:57): [True: 0, False: 0] Branch (27:79): [True: 0, False: 0]
28	0	CKey privkey;
29	0	privkey.Set(key_data.begin(), key_data.end(), !IdIsUnCompPubKey(i));
30	0	if (IdIsCompPubKey(i) \|\| IdIsUnCompPubKey(i)) { Branch (30:17): [True: 0, False: 0] Branch (30:38): [True: 0, False: 0]
31	0	CPubKey pubkey{privkey.GetPubKey()};
32	0	keys_str[i] = HexStr(pubkey);
33	0	} else if (IdIsXOnlyPubKey(i)) { Branch (33:24): [True: 0, False: 0]
34	0	const XOnlyPubKey pubkey{privkey.GetPubKey()};
35	0	keys_str[i] = HexStr(pubkey);
36	0	} else {
37	0	keys_str[i] = EncodeSecret(privkey);
38	0	}
39	0	} else {
40	0	CExtKey ext_privkey;
41	0	ext_privkey.SetSeed(key_data);
42	0	if (IdIsXprv(i)) { Branch (42:17): [True: 0, False: 0]
43	0	keys_str[i] = EncodeExtKey(ext_privkey);
44	0	} else {
45	0	const CExtPubKey ext_pubkey{ext_privkey.Neuter()};
46	0	keys_str[i] = EncodeExtPubKey(ext_pubkey);
47	0	}
48	0	}
49	0	}
50	0	}
51
52	367k	std::optional<uint8_t> MockedDescriptorConverter::IdxFromHex(std::string_view hex_characters) const {
53	367k	if (hex_characters.size() != 2) return {}; Branch (53:9): [True: 0, False: 367k]
54	367k	auto idx = ParseHex(hex_characters);
55	367k	if (idx.size() != 1) return {}; Branch (55:9): [True: 62, False: 367k]
56	367k	return idx[0];
57	367k	}
58
59	23.1k	std::optional<std::string> MockedDescriptorConverter::GetDescriptor(std::string_view mocked_desc) const {
60		// The smallest fragment would be "pk(%00)"
61	23.1k	if (mocked_desc.size() < 7) return {}; Branch (61:9): [True: 117, False: 23.0k]
62
63		// The actual descriptor string to be returned.
64	23.0k	std::string desc;
65	23.0k	desc.reserve(mocked_desc.size());
66
67		// Replace all occurrences of '%' followed by two hex characters with the corresponding key.
68	14.3M	for (size_t i = 0; i < mocked_desc.size();) { Branch (68:24): [True: 14.3M, False: 22.9k]
69	14.3M	if (mocked_desc[i] == '%') { Branch (69:13): [True: 367k, False: 13.9M]
70	367k	if (i + 3 >= mocked_desc.size()) return {}; Branch (70:17): [True: 6, False: 367k]
71	367k	if (const auto idx = IdxFromHex(mocked_desc.substr(i + 1, 2))) { Branch (71:28): [True: 367k, False: 62]
72	367k	desc += keys_str[*idx];
73	367k	i += 3;
74	367k	} else {
75	62	return {};
76	62	}
77	13.9M	} else {
78	13.9M	desc += mocked_desc[i++];
79	13.9M	}
80	14.3M	}
81
82	22.9k	return desc;
83	23.0k	}
84
85		bool HasDeepDerivPath(std::span<const uint8_t> buff, const int max_depth)
86	27.6k	{
87	27.6k	auto depth{0};
88	62.0M	for (const auto& ch: buff) { Branch (88:24): [True: 62.0M, False: 27.6k]
89	62.0M	if (ch == ',') { Branch (89:13): [True: 1.55M, False: 60.4M]
90		// A comma is always present between two key expressions, so we use that as a delimiter.
91	1.55M	depth = 0;
92	60.4M	} else if (ch == '/') { Branch (92:20): [True: 302k, False: 60.1M]
93	302k	if (++depth > max_depth) return true; Branch (93:17): [True: 6, False: 302k]
94	302k	}
95	62.0M	}
96	27.6k	return false;
97	27.6k	}
98
99		bool HasTooManySubFrag(std::span<const uint8_t> buff, const int max_subs, const size_t max_nested_subs)
100	29.1k	{
101		// We use a stack because there may be many nested sub-frags.
102	29.1k	std::stack<int> counts;
103	69.3M	for (const auto& ch: buff) { Branch (103:24): [True: 69.3M, False: 29.1k]
104		// The fuzzer may generate an input with a ton of parentheses. Rule out pathological cases.
105	69.3M	if (counts.size() > max_nested_subs) return true; Branch (105:13): [True: 11, False: 69.3M]
106
107	69.3M	if (ch == '(') { Branch (107:13): [True: 1.34M, False: 68.0M]
108		// A new fragment was opened, create a new sub-count for it and start as one since any fragment with
109		// parentheses has at least one sub.
110	1.34M	counts.push(1);
111	68.0M	} else if (ch == ',' && !counts.empty()) { Branch (111:20): [True: 1.96M, False: 66.0M] Branch (111:33): [True: 1.95M, False: 10.4k]
112		// When encountering a comma, account for an additional sub in the last opened fragment. If it exceeds the
113		// limit, bail.
114	1.95M	if (++counts.top() > max_subs) return true; Branch (114:17): [True: 11, False: 1.95M]
115	66.0M	} else if (ch == ')' && !counts.empty()) { Branch (115:20): [True: 934k, False: 65.1M] Branch (115:33): [True: 918k, False: 15.7k]
116		// Fragment closed! Drop its sub count and resume to counting the number of subs for its parent.
117	918k	counts.pop();
118	918k	}
119	69.3M	}
120	29.1k	return false;
121	29.1k	}
122
123		bool HasTooManyWrappers(std::span<const uint8_t> buff, const int max_wrappers)
124	29.1k	{
125		// The number of nested wrappers. Nested wrappers are always characters which follow each other so we don't have to
126		// use a stack as we do above when counting the number of sub-fragments.
127	29.1k	std::optional<int> count;
128
129		// We want to detect nested wrappers. A wrapper is a character prepended to a fragment, separated by a colon. There
130		// may be more than one wrapper, in which case the colon is not repeated. For instance `jjjjj:pk()`. To count
131		// wrappers we iterate in reverse and use the colon to detect the end of a wrapper expression and count how many
132		// characters there are since the beginning of the expression. We stop counting when we encounter a character
133		// indicating the beginning of a new expression.
134	68.1M	for (const auto ch: buff \| std::views::reverse) { Branch (134:23): [True: 68.1M, False: 29.1k]
135		// A colon, start counting.
136	68.1M	if (ch == ':') { Branch (136:13): [True: 1.15M, False: 66.9M]
137		// The colon itself is not a wrapper so we start at 0.
138	1.15M	count = 0;
139	66.9M	} else if (count) { Branch (139:20): [True: 10.5M, False: 56.4M]
140		// If we are counting wrappers, stop when we crossed the beginning of the wrapper expression. Otherwise keep
141		// counting and bail if we reached the limit.
142		// A wrapper may only ever occur as the first sub of a descriptor/miniscript expression ('('), as the
143		// first Taproot leaf in a pair ('{') or as the nth sub in each case (',').
144	10.5M	if (ch == ',' \|\| ch == '(' \|\| ch == '{') { Branch (144:17): [True: 867k, False: 9.64M] Branch (144:30): [True: 266k, False: 9.37M] Branch (144:43): [True: 15.5k, False: 9.36M]
145	1.14M	count.reset();
146	9.36M	} else if (++*count > max_wrappers) { Branch (146:24): [True: 20, False: 9.36M]
147	20	return true;
148	20	}
149	10.5M	}
150	68.1M	}
151
152	29.1k	return false;
153	29.1k	}
154
155		bool HasTooLargeLeafSize(std::span<const uint8_t> buff, const uint32_t max_leaf_size)
156	27.5k	{
157	27.5k	uint32_t leaf_len{0};
158	61.1M	for (auto c : buff) { Branch (158:17): [True: 61.1M, False: 27.5k]
159	61.1M	if (c == '(' \|\| c == ')' \|\| c == ',' \|\| c == '{' \|\| c == '}') { Branch (159:13): [True: 861k, False: 60.2M] Branch (159:25): [True: 637k, False: 59.6M] Branch (159:37): [True: 1.49M, False: 58.1M] Branch (159:49): [True: 28.0k, False: 58.1M] Branch (159:61): [True: 9.46k, False: 58.1M]
160		// Possibly start a fresh leaf, or a fresh function name (with
161		// wrappers), or terminate a prior leaf.
162	3.03M	leaf_len = 0;
163	58.1M	} else {
164		// Just treat everything else as a leaf. This will also reject long
165		// function names, but this should be fine if the max_leaf_size is
166		// set large enough.
167	58.1M	if (++leaf_len > max_leaf_size) { Branch (167:17): [True: 13, False: 58.1M]
168	13	return true;
169	13	}
170	58.1M	}
171	61.1M	}
172	27.5k	return false;
173	27.5k	}

Coverage Report

Created: 2026-08-25 19:22