Vector35 / Vector35/binaryninja-api

Linear sweep causing performance issues when there are fragments of functions from incomplete analysis

Open
#7,129 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Component: Core Effort: Medium Impact: Medium
Dominant language
C++
Stars
1.3k
Forks
298
Avg merge
5d 5h
Merged PRs (30d)
19

Description

Version and Platform (required):

  • Binary Ninja Version: 5.17982
  • Edition: Ultimate
  • OS: macOS
  • OS Version: 15.5
  • CPU Architecture: M3

Bug Description:
Analysis sometimes aborts for a function for numerous reasons. Historically, this was mostly for performance (function is too large, takes too long to analyze, etc.). Starting in 5.1 we added some additional conservative analysis features that try to avoid analyzing code that isn't real by aborting when invalid instructions are encountered.

Analysis isn't perfect, and sometimes real functions can encounter edge cases in heuristics that cause bad code to be introduced into a well-formed function. This can cause analysis to halt, yielding an incomplete function. The user then can go fix up the function and complete analysis with potentially better results from avoiding incorrect code.

However, linear sweep isn't very aware of this. With incomplete functions around the binary, there are leftover basic blocks that contain real code, which the analysis engine couldn't pick up. Linear sweep finds these, but because they are function fragments that sometimes loop around to common paths, it can sometimes create a very large number of very large functions, causing a massive performance issue. To make things worse, linear sweep analysis is less parallel than phase 1 analysis, so it takes even longer.

Steps To Reproduce:
The binary "XUL-x86_64" on the "Large Binary Performance Tests" project contains a binary that triggers this exclusively because of the new invalid instruction abort logic.

With the setting analysis.guided.triggers.invalidInstruction on (which is default), phase 2/3 take 52 minutes on an M3 Max. With the setting off, it takes only 8 minutes.

An example function in this binary that triggers the issue is at 0x531580. With the invalid instruction setting on, linear sweep makes a large number of extra functions containing leftover basic blocks from this function.

Expected Behavior:
We should try and be better about dealing with leftover function fragments in linear sweep, especially avoiding creating a large number of extra functions that flow into the same code.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the XUL-x86_64 binary in the Large Binary Performance Tests project and reproduce analysis with analysis.guided.triggers.invalidInstruction enabled, focusing on 0x531580. Compare phase 2/3 behavior with the setting disabled and inspect how linear sweep handles leftover fragments. Done means avoiding the large number of extra functions and reducing the reported performance impact without losing valid analysis.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
performance, reverse-engineering
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.