Advanced binary search ignores cancellation and long patterns take minutes instead of milliseconds
Maintainer antworten meist innerhalb von 2 Tagen
Dieses Issue hat noch niemand übernommen.
Bewertung
- Schwierigkeit
- 4/5
- Geschätzter Aufwand
- 1-2 Tage
- Anfängerfreundlichkeit
- 53/100
Rechercherichtung
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.
Vom Indexierungsmodell aus dem Issue-Text verfasst.
Beschreibung
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:
- During a long search,
BNSearchkeeps calling the progress callback, and stops soon after the callback returnsfalse, asBNFindNextDataWithProgressdoes and asBNSearchalready does for other patterns. - 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
BNFindNextDataWithProgresstoBNSearch. 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.
- Vorherrschende Sprache
- C++
- Sterne
- 1.3k
- Forks
- 304
- Ø Merge
- 2 T. 20 Std.
- Gemergte PRs (30 T.)
- 10
Entwicklungsumgebung
Dieses Projekt bietet weder Dev-Container noch Dockerfile noch Beitragsleitfaden – die Einrichtung liegt bei Ihnen. Beginnen Sie mit der README; die allgemeinen Schritte stehen in unserem Leitfaden für den ersten Beitrag.
Erste Schritte
- Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
- Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
- Forken Sie das Repository und arbeiten Sie in einem Branch.
- Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.
Mehr aus Vector35/binaryninja-api
-
Schwierigkeit 1/5 Unter einer Stunde Anfängerfreundlichkeit 84/100
Vector35/binaryninja-api#8715 ·
Maintainer antworten meist innerhalb von 2 Tagen
-
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 78/100
Vector35/binaryninja-api#8714 ·
Maintainer antworten meist innerhalb von 2 Tagen
-
Schwierigkeit 1/5 Unter einer Stunde Anfängerfreundlichkeit 85/100
Vector35/binaryninja-api#8713 ·
Maintainer antworten meist innerhalb von 2 Tagen
-
Schwierigkeit 1/5 1-3 Stunden Anfängerfreundlichkeit 78/100
Vector35/binaryninja-api#8689 ·
Maintainer antworten meist innerhalb von 2 Tagen
-
Component: Python API
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 70/100
Vector35/binaryninja-api#8649 ·
Maintainer antworten meist innerhalb von 2 Tagen
Alle Issues in Vector35/binaryninja-api
Ähnliche Issues
-
Bug Core VIF
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 68/100
Maintainer antworten meist innerhalb von 1 Tag
-
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 80/100
ESPresense/ESPresense#2680 · 2 Kommentare ·
Maintainer antworten meist innerhalb von 1 Tag
-
Schwierigkeit 2/5 Unter einer Stunde Anfängerfreundlichkeit 75/100
stew675/llama-cpp-rdna-boosts#348 ·
Maintainer antworten meist innerhalb von 1 Tag
-
Documentation: Add comprehensive newcomer onboarding guide, project structure, and local usage to READMEEvtl. vergeben @Ash-Blanc hat das heute übernommen. Offenarea/other status/bot-triaged status/need-triage
Schwierigkeit 2/5 Ein halber Tag Anfängerfreundlichkeit 85/100
-
bug
Schwierigkeit 1/5 Unter einer Stunde Anfängerfreundlichkeit 85/100
Maintainer antworten meist innerhalb von 1 Tag