Memory leak in CreateSearchExpressionTree: partial SSearchTerm tree leaks on exception during recursive parse of KADEMLIA2_SEARCH_KEY_REQ #884

• Criticality: High
• Component: Kademlia (Kad) UDP listener — search-expression parser (CKademliaUDPListener::CreateSearchExpressionTree)
• File: src/kademlia/net/KademliaUDPListener.cpp (lines 780–907; leak sites 794, 807, 820, 842, 844, 868, 898, 900)
• CWE: CWE-401 (Missing Release of Memory after Effective Lifetime)
• Reachability: Remote pre-auth (Kad UDP, KADEMLIA2_SEARCH_KEY_REQ)
• Impact: Memory leak / resource-exhaustion DoS. Each malformed packet orphans a partial heap-allocated SSearchTerm subtree; repeatable and unbounded across packets. Not memory corruption.

Summary

CKademliaUDPListener::CreateSearchExpressionTree() recursively parses an attacker-supplied search expression out of a CMemFile into a tree of raw-pointer SSearchTerm nodes, allocating each node with bare new and providing no try/catch and no RAII. For a boolean node (AND/OR/NOT) the function allocates the node, fully builds its left child via a recursive call, and then builds its right child via a second recursive call. The recursive call begins by reading from the wire (bio.ReadUInt8() at line 790, or ReadString/ReadUInt32/ReadUInt64). On a truncated or crafted packet that read throws CEOFException after the parent node and its entire left subtree have already been allocated. Because there is no handler in this function, in the caller Process2SearchKeyRequest() (line 920), or in the dispatcher CKademlia::ProcessPacket() (which only logs and continues), the stack unwinds past the raw local pointer. ~SSearchTerm (Indexed.cpp:935) only frees astr/tag and never recurses into left/right — recursive cleanup lives exclusively in the manual Free() helper, which is only reached on the success path (line 927) or the NULL-return path, never the throw path. The parent node and its already-built left subtree (with their wxArrayString/CTagString/CTagVarInt allocations) are therefore permanently leaked. The path is wire-reachable pre-authentication, the exception is recoverable (the process keeps running), and the leak accumulates per malformed packet, yielding a remote resource-exhaustion DoS.

Affected code

// src/kademlia/net/KademliaUDPListener.cpp

// Recursive cleanup helper — the ONLY thing that frees children.
// It is called on success/NULL-return paths, never on the throw path.
void CKademliaUDPListener::Free(SSearchTerm* pSearchTerms)            // line 771
{
	if (pSearchTerms) {
		Free(pSearchTerms->left);
		Free(pSearchTerms->right);
		delete pSearchTerms;
	}
}

SSearchTerm* CKademliaUDPListener::CreateSearchExpressionTree(CMemFile& bio, int iLevel)  // line 780
{
	if (iLevel >= 24){                                            // depth cap, line 784
		AddDebugLogLineN(logKadSearch, "***NOTE: Search expression tree exceeds depth limit!");
		return NULL;
	}
	iLevel++;

	uint8_t op = bio.ReadUInt8();                                 // line 790 — THROWS CEOFException on truncated packet
	if (op == 0x00) {
		uint8_t boolop = bio.ReadUInt8();
		if (boolop == 0x00) { // AND
			SSearchTerm* pSearchTerm = new SSearchTerm;           // line 794 — node allocated (raw ptr, no RAII)
			pSearchTerm->type = SSearchTerm::AND;
			if ((pSearchTerm->left = CreateSearchExpressionTree(bio, iLevel)) == NULL) {
				delete pSearchTerm;                               // only the NULL-return path is cleaned up
				return NULL;
			}
			// left subtree is now fully built and attached.
			if ((pSearchTerm->right = CreateSearchExpressionTree(bio, iLevel)) == NULL) {  // line 800 — recursion may THROW
				Free(pSearchTerm->left);                          // reached ONLY on NULL return, NOT on throw
				delete pSearchTerm;
				return NULL;
			}
			return pSearchTerm;
		} else if (boolop == 0x01) { // OR
			SSearchTerm* pSearchTerm = new SSearchTerm;           // line 807 — identical defect
			...
			if ((pSearchTerm->right = CreateSearchExpressionTree(bio, iLevel)) == NULL) {  // line 813 — may THROW
				Free(pSearchTerm->left);
				delete pSearchTerm;
				return NULL;
			}
			return pSearchTerm;
		} else if (boolop == 0x02) { // NOT
			SSearchTerm* pSearchTerm = new SSearchTerm;           // line 820 — identical defect
			...
			if ((pSearchTerm->right = CreateSearchExpressionTree(bio, iLevel)) == NULL) {  // line 826 — may THROW
				...
			}
			return pSearchTerm;
		}
		...
	} else if (op == 0x01) { // String
		wxString str(bio.ReadString(true));
		str.MakeLower();
		SSearchTerm* pSearchTerm = new SSearchTerm;               // line 842 — leakable left child
		pSearchTerm->type = SSearchTerm::String;
		pSearchTerm->astr = new wxArrayString;                    // line 844 — extra allocation that leaks with the node
		...
		return pSearchTerm;
	} else if (op == 0x02) { // Meta tag
		wxString strValue(bio.ReadString(true));
		strValue.MakeLower();
		wxString strTagName = bio.ReadString(false);
		SSearchTerm* pSearchTerm = new SSearchTerm;               // line 866
		pSearchTerm->type = SSearchTerm::MetaTag;
		pSearchTerm->tag = new CTagString(strTagName, strValue);  // line 868
		return pSearchTerm;
	} else if (op == 0x03 || op == 0x08) { // Numeric relation
		uint64_t ullValue = (op == 0x03) ? bio.ReadUInt32() : bio.ReadUInt64();  // throwing reads happen BEFORE the new
		uint8_t mmop = bio.ReadUInt8();
		...
		wxString strTagName = bio.ReadString(false);
		SSearchTerm* pSearchTerm = new SSearchTerm;               // line 898 — leakable left child
		pSearchTerm->type = _aOps[mmop].eSearchTermOp;
		pSearchTerm->tag = new CTagVarInt(strTagName, ullValue);  // line 900
		return pSearchTerm;
	}
	...
}

// Caller — also has NO try/catch around the builder.
void CKademliaUDPListener::Process2SearchKeyRequest(...)              // line 911
{
	CMemFile bio(packetData, lenPacket);
	CUInt128 target = bio.ReadUInt128();
	uint16_t startPosition = bio.ReadUInt16();
	bool restrictive = ((startPosition & 0x8000) == 0x8000);         // line 916
	startPosition &= 0x7FFF;
	SSearchTerm* pSearchTerms = NULL;
	if (restrictive) {
		pSearchTerms = CreateSearchExpressionTree(bio, 0);           // line 920 — partial tree lost on throw
		if (pSearchTerms == NULL) {
			throw wxString("Invalid search expression");
		}
	}
	CKademlia::GetIndexed()->SendValidKeywordResult(target, pSearchTerms, ...);  // ownership sink; unreached on throw
	if (pSearchTerms) {
		Free(pSearchTerms);                                          // line 927 — only the success path frees
	}
}

// src/kademlia/kademlia/Indexed.cpp:935 — destructor does NOT recurse into children
SSearchTerm::~SSearchTerm()
{
	if (type == String) {
		delete astr;
	}
	delete tag;
}

// src/kademlia/kademlia/Kademlia.cpp:299 — the only upstream handler: logs and continues, cannot reach the lost tree
void CKademlia::ProcessPacket(...)
{
	try {
		...
		instance->m_udpListener->ProcessPacket(...);
	} catch (const wxString& DEBUG_ONLY(error)) {
		AddDebugLogLineN(logKadMain, ...);          // line 305 — recovers, leak persists
	} catch (...) {
		AddDebugLogLineN(logKadMain, "Unhandled exception on Kad ProcessPacket");  // line 310
	}
}

Trigger / Attack vector

1. The Kad UDP dispatcher routes KADEMLIA2_SEARCH_KEY_REQ to Process2SearchKeyRequest() (dispatch at KademliaUDPListener.cpp:270–272). This requires no cryptographic authentication — Kad is an open DHT; only flood/track filters apply. The path is therefore remotely reachable pre-auth.
2. The attacker crafts a datagram whose payload, after the 16-byte target and the 2-byte startPosition, sets the restrictive bit (startPosition & 0x8000, line 916) so that CreateSearchExpressionTree(bio, 0) is invoked (line 920).
3. The attacker encodes a boolean node, e.g. AND( <valid left subtree>, <truncated right> ): byte 0x00 (boolean), byte 0x00 (AND), followed by a complete, well-formed left child (for example a String node 0x01 "foo", or a Numeric leaf 0x03 …), and then truncates the buffer so the right-child recursion runs out of data.
4. When the parser recurses for the right child, the first bio.ReadUInt8() (line 790) — or a deeper ReadString/ReadUInt32/ReadUInt64 — reads past the end of the CMemFile and throws CEOFException (SafeFile.cpp Read() throws on short read).
5. The exception unwinds through the AND/OR/NOT frame (no try/catch), through Process2SearchKeyRequest (no try/catch), and is finally swallowed by CKademlia::ProcessPacket (Kademlia.cpp:305–311), which only logs. The parent SSearchTerm (allocated at line 794/807/820) and its already-built left subtree — including any wxArrayString (line 844), CTagString (line 868), or CTagVarInt (line 900) — are now orphaned heap objects with no remaining pointer; ~SSearchTerm is never invoked on them and Free() is never reached.
6. The process survives and keeps listening, so the attacker repeats the packet. Although a single packet leaks only a depth-≤24-bounded partial tree, the leak is unbounded across packets, producing gradual memory exhaustion (DoS).

The leak is triggered by an ordinary truncation exception, not by std::bad_alloc. Sites 794/807/820 are the AND/OR/NOT boolean nodes (the root defect); sites 842/844/868/898/900 enumerate the leaf nodes (String, MetaTag, Numeric) that leak when they are the already-built left child of such a boolean node whose right recursion throws.

Suggested fix

Make the builder exception-safe so an in-flight node and its children are released during unwinding. Options, in order of preference:

• RAII ownership of each node. Hold the freshly allocated node in a smart pointer with a custom deleter that calls the recursive Free() (so children are released too), and only release() it on the success return. For example, with the project's CScopedPtr/std::unique_ptr:

  std::unique_ptr<SSearchTerm, decltype(&CKademliaUDPListener::Free)>
      guard(new SSearchTerm, &CKademliaUDPListener::Free);
  guard->type = SSearchTerm::AND;
  guard->left  = CreateSearchExpressionTree(bio, iLevel);   // throw here -> guard frees node (+ NULL children)
  if (!guard->left) return NULL;
  guard->right = CreateSearchExpressionTree(bio, iLevel);   // throw here -> guard frees node + left subtree
  if (!guard->right) return NULL;
  return guard.release();

  (Free() is null-safe and recursive, so it correctly handles partially-populated nodes.)
• Or wrap the recursive children in a local try { ... } catch (...) { Free(pSearchTerm); throw; } block at each boolean branch (and analogously delete the leaf node if a throw can follow its new).
• A robust additional safeguard is to give ~SSearchTerm recursive ownership of left/right (i.e. delete left; delete right; in the destructor) and rely on stack unwinding, but this requires auditing every Free()/delete call site to avoid double frees; the scoped-guard approach above is the lower-risk change.