search

NationalSecurityAgency / ghidra

Ghidra is a software reverse engineering (SRE) framework
https://www.nsa.gov/ghidra
Apache License 2.0
51.31k stars 5.85k forks source link

VT duplicate function matching correlator remains prohibitively slow, even after GP-3527 #5857

Closed clearbluejar closed 1 year ago

clearbluejar commented 1 year ago

Describe the bug

VT duplicate function matching correlator continues to prohibitively slow even after GP-3527

To Reproduce

Steps to reproduce the behavior:

Perform version tracking on a relatively large binary (~7MB+ such as the Windows kernel):

  1. Download two recent versions of latest ntoskrnl.exe (aka ntkrnlmp.exe)

wget https://msdl.microsoft.com/download/symbols/ntkrnlmp.exe/A5E88A321047000/ntkrnlmp.exe -O ntkrnlmp.exe.x64.10.0.22000.2360

wget https://msdl.microsoft.com/download/symbols/ntkrnlmp.exe/B76D01041047000/ntkrnlmp.exe -O ntkrnlmp.exe.x64.10.0.22000.2416



2. Import / Analyze / Download Symbols
3. Run new VT session and load bins
4. Run automatic version tracking
5. Get stuck at Duplicate Function Correlation

> ![image](https://github.com/NationalSecurityAgency/ghidra/assets/3752074/eb953693-85e9-40c9-819c-764c977df285)
This was progress after 20 mins on i7 with 32GB RAM assigned to the JVM. 

Maybe the duplicate function correlation is matching too many?
> ![image](https://github.com/NationalSecurityAgency/ghidra/assets/3752074/8c0575b1-6e72-43fc-840b-7f04f5f459f3)

**Expected behavior**
Duplicate function matching occurs at rate similar to running the correlator manually with default options. 

**Workaround**

1. Cancel Automatic VT at step 6.
2. Manually Run 'Duplicate Function Instructions Match' Correlator with default settings
3. It completes in about 30 seconds or less.
4. Finish by manually running remaining correlators. 

**Environment (please complete the following information):**
 - OS: Windows 11
 - Java Version: 17.0.8
 - Ghidra Version: 10.4
 - Ghidra Origin: official GitHub distro

**Additional context**
I have been doing VT patch diffing for awhile, I feel like this hang on step 6 was introduced in 10.3  https://github.com/NationalSecurityAgency/ghidra/releases/tag/Ghidra_10.3_build , but could have been earlier. If needed I can go try earlier versions to see if I experience the same behaviour.
ghidra007 commented 1 year ago

Yes. There is another fix in the works that should be better. Thanks.

One reason it takes longer in the autoVT is because it is actually doing more with the returned duplicate matches than the duplicate matcher does. It uses operand info to try and find "the" match amongst the subset of possible matches for a particular function. The initial stopgap fix was to limit how many it would work on. The new fix is actually doing the compares faster.

ghidra007 commented 1 year ago

@clearbluejar The portion of the code doing the "real" matching after the duplicate matcher finds possible matches should now be noticeably faster. I'd be curious to know if you notice a difference. My timing tests showed a big improvement in the "Processing match .." portion. The correlator code itself is still slow but I'm hoping to speed that up too if possible. I am also going to eventually add an option to the AutoVT to change the minimum function length for matches.

clearbluejar commented 1 year ago

Great! I'll give it a try. As this is set for milestone 10.5, will I need to build from 'patch' or 'master' to try it?

I like the idea to add options for AutoVT. It would be nice to be able to customize each of the correlator options before kicking off the script, or even optionally run exclude/add some correlators. But those can be future feature requests.

ryanmkurtz commented 1 year ago

As this is set for milestone 10.5, will I need to build from 'patch' or 'master' to try it?

master

ghidra007 commented 1 year ago

Great! I'll give it a try. As this is set for milestone 10.5, will I need to build from 'patch' or 'master' to try it?

I like the idea to add options for AutoVT. It would be nice to be able to customize each of the correlator options before kicking off the script, or even optionally run exclude/add some correlators. But those can be future feature requests.

That is the plan while adding the one option to just go ahead and add the other correlator options.

clearbluejar commented 12 months ago

duplicate function correlator now completes in about 2 mins for the kernel. well done. that was using this build https://github.com/roblabla/ghidra-ci/releases/tag/2023-10-27

ghidra007 commented 12 months ago

duplicate function correlator now completes in about 2 mins for the kernel. well done. that was using this build https://github.com/roblabla/ghidra-ci/releases/tag/2023-10-27

Great! Thanks for trying it!