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

オープン
#8,652 コメント 1 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 2 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
1〜2日
初心者へのやさしさ
53/100
issue の種類
バグ
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
c, cpp, python, rust

調査の方向性

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:

  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.
主要言語
C++
スター
1.3k
フォーク
304
平均マージ
2日 20時間
マージ済み PR(30日)
10

環境構築

このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

Vector35/binaryninja-api のほかの issue

Vector35/binaryninja-api の issue をすべて見る

似ている issue

C++ の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。