Augmented B+Tree Rank Disregard & RESP Inline Command Injection

Location: src/facade/reply_builder.cc:441-443, src/server/protocol_client.cc:268-270, src/core/sorted_map.cc:785-788, src/core/sorted_map.cc:937-957 Classification: Protocol Injection & $O(\text{offset})$ / $O(K \log N)$ Algorithmic Degradation

Analysis

Part A: Asymptotic Degradation in Sorted Sets

Dragonfly's BPTree is an augmented order-statistic B+tree: every interior node maintains subtree element counts (GetChildTreeCount), permitting rank seeks in $O(\log N)$ time via FromRank(). However, in SortedMap::GetRange and SortedMap::GetLexRange:

while (offset--) {
  if (!path.Prev())
    return arr;
}

When skipping offset elements, instead of computing target_rank = path.Rank() - offset in $O(\log N)$ and jumping directly via FromRank(target_rank), the code performs an $O(\text{offset})$ sequential leaf traversal. A command such as ZREVRANGEBYSCORE key +inf -inf LIMIT 10000000 1 executes 10 million pointer hops in a single fiber invocation without yielding.

Furthermore, in SortedMap::DeleteRangeByScore:

while (!score_tree->Empty()) {
  ScoreSds min_key = BuildScoredKey(range.min, buf);
  auto path = score_tree->GEQ(Query{min_key, false, range.minex});
  ...
  score_tree->Delete(item);
  ++deleted;
}

Deleting $K$ elements in a range performs $K$ individual root-to-leaf searches from scratch ($O(K \log N)$), rather than locating the lower bound once ($O(\log N)$) and deleting along the leaf linked list in $O(\log N + K)$ time.

Part B: Replication Protocol / CRLF Injection

In RedisReplyBuilderBase::SerializeCommand:

std::string RedisReplyBuilderBase::SerializeCommand(std::string_view command) {
  return string{command} + kCRLF;
}

Commands sent by ProtocolClient are formatted as raw strings with \r\n appended, rather than RESP multi-bulk arrays (*<argc>\r\n$<len>\r\n...):

auto cmd = masteruser.empty() ? StrCat("AUTH ", masterauth)
                              : StrCat("AUTH ", masteruser, " ", masterauth);
RETURN_ON_ERR(SendCommandAndReadResponse(cmd));

If masterauth or masteruser contains whitespace (e.g., base64 tokens, passphrases) or control characters (\r\n), the command breaks argument boundaries or injects arbitrary Redis commands directly into the replication channel.

Remediation

1. In SortedMap, replace while (offset--) path.Prev() / path.Next() with an $O(\log N)$ rank calculation: path = score_tree->FromRank(path.Rank() +/- offset).
2. In ProtocolClient, serialize replication commands using standard RESP multi-bulk arrays rather than raw inline strings.