Advanced binary search ignores cancellation and long patterns take minutes instead of milliseconds
メンテナーはふだん 2 日以内に返信
まだ誰も着手していません。
評価
- 難易度
- 4/5
- 見積もり時間
- 1〜2日
- 初心者へのやさしさ
- 53/100
調査の方向性
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.
索引モデルが issue の本文から書いたものです。
説明
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.
- 主要言語
- C++
- スター
- 1.3k
- フォーク
- 304
- 平均マージ
- 2日 20時間
- マージ済み PR(30日)
- 10
環境構築
このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
Vector35/binaryninja-api のほかの issue
-
難易度 1/5 1時間未満 初心者へのやさしさ 84/100
Vector35/binaryninja-api#8715 ·
メンテナーはふだん 2 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
Vector35/binaryninja-api#8714 ·
メンテナーはふだん 2 日以内に返信
-
難易度 1/5 1時間未満 初心者へのやさしさ 85/100
Vector35/binaryninja-api#8713 ·
メンテナーはふだん 2 日以内に返信
-
難易度 1/5 1〜3時間 初心者へのやさしさ 78/100
Vector35/binaryninja-api#8689 ·
メンテナーはふだん 2 日以内に返信
-
Component: Python API
難易度 2/5 1〜3時間 初心者へのやさしさ 70/100
Vector35/binaryninja-api#8649 ·
メンテナーはふだん 2 日以内に返信
Vector35/binaryninja-api の issue をすべて見る
似ている issue
-
Bug Core VIF
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 80/100
ESPresense/ESPresense#2680 · コメント 2 件 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1時間未満 初心者へのやさしさ 75/100
stew675/llama-cpp-rdna-boosts#348 ·
メンテナーはふだん 1 日以内に返信
-
Documentation: Add comprehensive newcomer onboarding guide, project structure, and local usage to README対応中かも @Ash-Blanc が今日担当しました。 オープンarea/other status/bot-triaged status/need-triage
難易度 2/5 半日 初心者へのやさしさ 85/100
-
bug
難易度 1/5 1時間未満 初心者へのやさしさ 85/100
メンテナーはふだん 1 日以内に返信