Advanced binary search ignores cancellation and long patterns take minutes instead of milliseconds

Ouverte
#8,652 1 commentaire 0 réactions 0 personnes assignées Voir sur GitHub

Les mainteneurs répondent en général sous 2 jours

Personne n'a encore pris cette issue.

Évaluation

Difficulté
4/5
Temps estimé
1-2 jours
Accessibilité débutants
53/100
Type d'issue
Bug
Clarté
Clairement spécifiée
Activité
Active
Stack technique
c, cpp, python, rust
Domaine
backend, performance

Piste de recherche

Start by comparing the progress handling in BNSearch with BNFindNextDataWithProgress; the report identifies BinaryView.search in Python and BinaryView::search_with_progress in Rust as related entry points. Reproduce with the supplied headless script and the 4096-byte FlexHex pattern, then trace the long-pattern search path. Done means progress is called during the scan, cancellation stops it promptly, and the regression is covered by a test.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

Version and platform: 6.1.10874-dev, Linux x86_64, headless

Bug description:
BNSearch (advanced binary search; BinaryView.search in Python, BinaryView::search_with_progress in Rust) calls its progress callback once, when the search starts, and never again on some patterns. A search that goes down that path can't be cancelled: returning false from the progress callback has no effect, so the caller is stuck until the scan finishes.

Long patterns are the easiest way to hit this, because they also make the search very slow. On 8 MiB of zeros, a FlexHex pattern of 4095 zero bytes followed by 01 (no wildcards, never matches) takes about 150 s and calls the progress callback once. The same pattern through BNFindNextDataWithProgress takes 0.019 s and calls the callback 33 times. Shorter patterns stay fast (39 ms at 3072 bytes), so there seems to be a cliff somewhere between 3072 and 4095 bytes. A regex has the same cliff: \x00{3000}\x01 is fast, while \x00{5000}\x01 stalls the same way.

Other searches do keep calling the progress callback. On 8 MiB of random data, a YARA-jump search ({ 00 [0-1024] 01 [0-1024] 02 }) called it four times and stopped within 0.3 s of being cancelled. So the missing calls seem specific to whatever path long patterns take.

Steps to reproduce:
Run the script below headless. It creates an 8 MiB file of zeros and searches it for patterns of increasing length. Each search's progress callback returns false once 1 s has passed.

# Advanced binary search (BNSearch) ignores cancellation on long patterns.
import ctypes, json, os, tempfile, time
import binaryninja as bn
from binaryninja import core
from binaryninja.databuffer import DataBuffer

print("Binary Ninja", bn.core_version())

# 8 MiB of zeros; the pattern is N-1 zero bytes followed by 0x01 (never matches).
path = os.path.join(tempfile.mkdtemp(), "zeros.bin")
with open(path, "wb") as f:
    f.write(bytes(8 * 1024 * 1024))
bv = bn.load(path, update_analysis=False)

PROGRESS = ctypes.CFUNCTYPE(ctypes.c_bool, ctypes.c_void_p, ctypes.c_ulonglong, ctypes.c_ulonglong)
MATCH = ctypes.CFUNCTYPE(ctypes.c_bool, ctypes.c_void_p, ctypes.c_ulonglong, ctypes.POINTER(core.BNDataBuffer))
CANCEL_AFTER = 1.0  # seconds; the progress callback returns False after this

def cancelling_progress(t0, calls):
    def cb(ctxt, cur, total):
        calls[0] += 1
        return time.time() - t0 < CANCEL_AFTER
    return PROGRESS(cb)

def bnsearch(n):
    q = {"pattern": " ".join(["00"] * (n - 1) + ["01"]), "searchType": "flexhex",
         "start": bv.start, "end": bv.end - 1}
    t0, calls = time.time(), [0]
    core.BNSearch(bv.handle, json.dumps(q), None, cancelling_progress(t0, calls),
                  None, MATCH(lambda c, a, b: True))
    return time.time() - t0, calls[0]

def find_next_data(n):
    buf, result = DataBuffer(bytes(n - 1) + b"\x01"), ctypes.c_ulonglong()
    t0, calls = time.time(), [0]
    core.BNFindNextDataWithProgress(bv.handle, bv.start, bv.end, buf.handle, result, 0,
                                    None, cancelling_progress(t0, calls))
    return time.time() - t0, calls[0]

for n in (1024, 3072, 4096):
    for name, fn in (("BNFindNextDataWithProgress", find_next_data), ("BNSearch (flexhex)", bnsearch)):
        dt, calls = fn(n)
        print(f"{n:5}-byte pattern  {name:27} {dt:8.3f}s  progress calls: {calls}")

Output:

Binary Ninja 6.1.10874-dev
 1024-byte pattern  BNFindNextDataWithProgress     0.019s  progress calls: 33
 1024-byte pattern  BNSearch (flexhex)             0.015s  progress calls: 1
 3072-byte pattern  BNFindNextDataWithProgress     0.019s  progress calls: 33
 3072-byte pattern  BNSearch (flexhex)             0.039s  progress calls: 1
 4096-byte pattern  BNFindNextDataWithProgress     0.019s  progress calls: 33
 4096-byte pattern  BNSearch (flexhex)           152.316s  progress calls: 1

Expected behavior:

  1. During a long search, BNSearch keeps calling the progress callback, and stops soon after the callback returns false, as BNFindNextDataWithProgress does and as BNSearch already does for other patterns.
  2. Less important: a long pattern without wildcards shouldn't take thousands of times longer than the same bytes through BNFindNextDataWithProgress. Having a size limit on the pattern matcher makes sense, but falling back from 39 ms to about 150 s, maybe by routing exact patterns to the existing fast matcher, seems avoidable.

Additional information:

  • This came up while switching a headless tool from BNFindNextDataWithProgress to BNSearch. The tool cancels a search when its client disconnects, so a search like this keeps a thread busy for minutes after nobody is waiting for the result.
  • I haven't checked whether the Find dialog's advanced search in the UI is affected, but it probably uses the same call.
  • Matches were reported normally in every case I tried. Only the progress and cancellation behavior and the speed are wrong.
Langage dominant
C++
Étoiles
1.3k
Forks
304
Merge moyen
2 j 20 h
PR mergées (30 j)
10

Préparer son environnement

Ce projet ne fournit ni conteneur de développement, ni Dockerfile, ni guide de contribution : l'installation est à votre charge. Commencez par son README, et consultez notre guide de la première contribution pour les étapes générales.

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de Vector35/binaryninja-api

Toutes les issues de Vector35/binaryninja-api

Issues similaires

Plus d'issues C++

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.