Jump to content

Binary Search Function


Digisoul
 Share

Recommended Posts

Hello All,

I made this function to perform the Binary Search with Patterns.

i.e:

I have data for a exe file

0x558BEC6AFF68D834400068302C400064A100000000506489250000000083C4985356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFFFFFFC70564554000FFFFFFFFFF15083240008B0D545540008908FF150C3240008B15505540008910A1143240008B08890D5C554000E886010000A17054400085C0750E68102C4000FF151032400083C404E83A01000068145040006810504000E81D01000083C4088B154C5540008955948D4594508B0D48554000518D559C528D4590508D4DA051FF15F831400083C414680C5040006800504000E8E200000083C4088B15F03140008B3289758C803E220F85A80000004689758C8A0684C074043C2275F2803E2275044689758C8A0684C0740A3C2077064689758CEBF0C745D0000000008D45A450FF152C304000F645D0

and i want to perform the serach for this signature, From the Left side of the data in order.

0x558BEC6AFF68........68........64A10000000050

Here is my function

Func BIN_Search($data,$pattern)
Local $mat_bytes = 0,$e = 1
Local $S_ign =0,$S_mat =0
$len = StringLen($pattern)/2

While 1
    $left = BinaryMid($data,$e,1)
    $e +=1
    ;---------------------------------
    $pleft = StringLeft($pattern,2)
    $pattern = StringTrimLeft($pattern,2)
    ;---------------------------------
    Switch $pleft
        Case ".."
            $S_ign +=1
        Case Else
            If $left = '0x'&$pleft Then
                $S_mat +=1
            EndIf
    EndSwitch
    If $e > $len Then
        If $S_mat+$S_ign = $len Then
            $mat_bytes = $S_mat
            Return $mat_bytes
        EndIf
        Return 0
    EndIf
WEnd

EndFunc

Now i want to know is there any more fast way to perform this type of search because i have 2999 signatures to scan.

Thanks in advance.

73 108 111 118 101 65 117 116 111 105 116

Link to comment
Share on other sites

The interesting thing about matching by hex pattern is that you can represent the binary data as a hex string and use string matching instead. Since the StringRegExp() is already optimized, you might have trouble doing it faster than this:

#include <Array.au3>

; Test binaries, only [0] matches, [1] does not match
; Rest of array filled random with [0] or [1]
Global $avSigs[100] = [ _
        Binary("0x558BEC6AFF68D834400068302C400064A100000000506489250000000083C498" & _
        "5356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFF" & _
        "FFFFC70564554000FFFFFFFFFF15083240008B0D545540008908FF150C324000" & _
        "8B15505540008910A1143240008B08890D5C554000E886010000A17054400085" & _
        "C0750E68102C4000FF151032400083C404E83A01000068145040006810504000" & _
        "E81D01000083C4088B154C5540008955948D4594508B0D48554000518D559C52" & _
        "8D4590508D4DA051FF15F831400083C414680C5040006800504000E8E2000000" & _
        "83C4088B15F03140008B3289758C803E220F85A80000004689758C8A0684C074" & _
        "043C2275F2803E2275044689758C8A0684C0740A3C2077064689758CEBF0C745" & _
        "D0000000008D45A450FF152C304000F645D0"), _
        Binary("0x558BEC6AFF68D834400068302C400064B100000000506489250000000083C498" & _
        "5356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFF" & _
        "FFFFC70564554000FFFFFFFFFF15083240008B0D545540008908FF150C324000" & _
        "8B15505540008910A1143240008B08890D5C554000E886010000A17054400085" & _
        "C0750E68102C4000FF151032400083C404E83A01000068145040006810504000" & _
        "E81D01000083C4088B154C5540008955948D4594508B0D48554000518D559C52" & _
        "8D4590508D4DA051FF15F831400083C414680C5040006800504000E8E2000000" & _
        "83C4088B15F03140008B3289758C803E220F85A80000004689758C8A0684C074" & _
        "043C2275F2803E2275044689758C8A0684C0740A3C2077064689758CEBF0C745" & _
        "D0000000008D45A450FF152C304000F645D0")]
For $n = 2 To 99
    $avSigs[$n] = $avSigs[Random(1, 2, 1) - 1]
Next

Global $sSearchPatt = "0x558BEC6AFF68.+68.+64A10000000050", $sMsg = "" & @LF

Global $iTimer = TimerInit()

For $n = 0 To UBound($avSigs) - 1
    If StringRegExp(String($avSigs[$n]), $sSearchPatt, 0) Then
        $sMsg &= $n & ": Match" & @LF
    Else
        $sMsg &= $n & ": Failed" & @LF
    EndIf
Next

$iTimer = Round(TimerDiff($iTimer) / 1000, 3)

ConsoleWrite("Results in " & $iTimer & "sec: " & @LF & $sMsg)

On my computer, it processes 100 sigs in about 30 milliseconds.

Testing how long your func takes to process the same array of data is an exercise left to the student... :D

Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law
Link to comment
Share on other sites

The interesting thing about matching by hex pattern is that you can represent the binary data as a hex string and use string matching instead. Since the StringRegExp() is already optimized, you might have trouble doing it faster than this:

#include <Array.au3>

; Test binaries, only [0] matches, [1] does not match
; Rest of array filled random with [0] or [1]
Global $avSigs[100] = [ _
        Binary("0x558BEC6AFF68D834400068302C400064A100000000506489250000000083C498" & _
        "5356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFF" & _
        "FFFFC70564554000FFFFFFFFFF15083240008B0D545540008908FF150C324000" & _
        "8B15505540008910A1143240008B08890D5C554000E886010000A17054400085" & _
        "C0750E68102C4000FF151032400083C404E83A01000068145040006810504000" & _
        "E81D01000083C4088B154C5540008955948D4594508B0D48554000518D559C52" & _
        "8D4590508D4DA051FF15F831400083C414680C5040006800504000E8E2000000" & _
        "83C4088B15F03140008B3289758C803E220F85A80000004689758C8A0684C074" & _
        "043C2275F2803E2275044689758C8A0684C0740A3C2077064689758CEBF0C745" & _
        "D0000000008D45A450FF152C304000F645D0"), _
        Binary("0x558BEC6AFF68D834400068302C400064B100000000506489250000000083C498" & _
        "5356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFF" & _
        "FFFFC70564554000FFFFFFFFFF15083240008B0D545540008908FF150C324000" & _
        "8B15505540008910A1143240008B08890D5C554000E886010000A17054400085" & _
        "C0750E68102C4000FF151032400083C404E83A01000068145040006810504000" & _
        "E81D01000083C4088B154C5540008955948D4594508B0D48554000518D559C52" & _
        "8D4590508D4DA051FF15F831400083C414680C5040006800504000E8E2000000" & _
        "83C4088B15F03140008B3289758C803E220F85A80000004689758C8A0684C074" & _
        "043C2275F2803E2275044689758C8A0684C0740A3C2077064689758CEBF0C745" & _
        "D0000000008D45A450FF152C304000F645D0")]
For $n = 2 To 99
    $avSigs[$n] = $avSigs[Random(1, 2, 1) - 1]
Next

Global $sSearchPatt = "0x558BEC6AFF68.+68.+64A10000000050", $sMsg = "" & @LF

Global $iTimer = TimerInit()

For $n = 0 To UBound($avSigs) - 1
    If StringRegExp(String($avSigs[$n]), $sSearchPatt, 0) Then
        $sMsg &= $n & ": Match" & @LF
    Else
        $sMsg &= $n & ": Failed" & @LF
    EndIf
Next

$iTimer = Round(TimerDiff($iTimer) / 1000, 3)

ConsoleWrite("Results in " & $iTimer & "sec: " & @LF & $sMsg)

On my computer, it processes 100 sigs in about 30 milliseconds.

Testing how long your func takes to process the same array of data is an exercise left to the student... :D

Thank You very much for your reply. 1stly i tried with REGexp, but it never worked like i want.

The problem with REGEXP is,

ie:

We have this signature "FFFFFF0000000000003000000040000000000000" for Microsoft Visual Basic 5.0

and we want to search this sig in the RAW data from the first byte

Raw Data:

558BEC6AFF68D834400068302C400064A100000000506489250000000083C4985356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFFFFFFC70564554000FFFFFFFFFF15083240008B0D545540008908FFFFFF0000000000003000000040000000000000

as you can see RegExp also give positive result for this condition;

but the rite condition is:

FFFFFF0000000000003000000040000000000000558BEC6AFF68D834400068302C400064A100000000506489250000000083C4985356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFFFFFFC70564554000FFFFFFFFFF15083240008B0D545540008908

I want to match bytes from the start of the data not from the whole data string.

Regards;

Digisoul

73 108 111 118 101 65 117 116 111 105 116

Link to comment
Share on other sites

  • Moderators

Digisoul,

You need to add "^" to the SRE to force matches from the beginning of the string:

Local $avSigs[2] = _
["558BEC6AFF68D834400068302C400064A100000000506489250000000083C4985356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFFFFFFC70564554000FFFFFFFFFF15083240008B0D545540008908FFFFFF0000000000003000000040000000000000", _
"FFFFFF0000000000003000000040000000000000558BEC6AFF68D834400068302C400064A100000000506489250000000083C4985356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFFFFFFC70564554000FFFFFFFFFF15083240008B0D545540008908"]

 $sSearchPatt = "FFFFFF0000000000003000000040000000000000"

$sMsg = ""
For $n = 0 To UBound($avSigs) - 1
    If StringRegExp("^" & String($avSigs[$n]), $sSearchPatt, 0) Then  ; <<<<<<<<<<<<<<< "^" added here
        $sMsg &= $n & ": Match" & @LF
    Else
        $sMsg &= $n & ": Failed" & @LF
    EndIf
Next

MsgBox(0, "", $sMsg)

This now matches only the second value.

M23

Public_Domain.png.2d871819fcb9957cf44f4514551a2935.png Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind

Open spoiler to see my UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Link to comment
Share on other sites

Digisoul,

You need to add "^" to the SRE to force matches from the beginning of the string:

Local $avSigs[2] = _
["558BEC6AFF68D834400068302C400064A100000000506489250000000083C4985356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFFFFFFC70564554000FFFFFFFFFF15083240008B0D545540008908FFFFFF0000000000003000000040000000000000", _
"FFFFFF0000000000003000000040000000000000558BEC6AFF68D834400068302C400064A100000000506489250000000083C4985356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFFFFFFC70564554000FFFFFFFFFF15083240008B0D545540008908"]

 $sSearchPatt = "FFFFFF0000000000003000000040000000000000"

$sMsg = ""
For $n = 0 To UBound($avSigs) - 1
    If StringRegExp("^" & String($avSigs[$n]), $sSearchPatt, 0) Then  ; <<<<<<<<<<<<<<< "^" added here
        $sMsg &= $n & ": Match" & @LF
    Else
        $sMsg &= $n & ": Failed" & @LF
    EndIf
Next

MsgBox(0, "", $sMsg)

This now matches only the second value.

M23

Thanks M23,

Look here is a real example

Data:

0x60BE15104B008DBEEBFFF4FF5783CDFFEB109090909090908A064688074701DB75078B1E83EEFC11DB72EDB80100000001DB75078B1E83EEFC11DB11C001DB730B75198B1E83EEFC11DB72104801DB75078B1E83EEFC11DB11C0EBD431C983E8037211C1E0088A064683F0FF7478D1F889C5EB0B01DB75078B1E83EEFC11DB11C901DB75078B1E83EEFC11DB11C975204101DB75078B1E83EEFC11DB11C901DB73EF75098B1E83EEFC11DB73E483C10281FD00FBFFFF83D1018D142F83FDFC760F8A02428807474975F7E94FFFFFFF908B0283C204890783C70483E90477F101CFE938FFFFFF5E89F7B96D2200008A07472CE83C0177F7803F1175F28B078A5F0466C1E808C1C01086C429F880EBE801F0890783C70589D8E2D98DBE00300F008B0709C0743C8B5F048D8430C0630F0001F35083C708FF9688640F00958A074708C074DC89F95748F2AE55FF968C640F0009C07407890383C304EBE1FF9690640F0061E9C8B1F0FF000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Match Result for UPX

1:Matched: 43 - UPX v0.89.6 - v1.02 / v1.05 - v1.22 = ................................................8A064688074701DB75078B1E83EEFC11DB72EDB801......01DB75078B1E83EEFC11DB11C001DB73..75..8B1E83EEFC
2:Matched: 7 - UPX -> www.upx.sourceforge.net = 60BE...04.008DBE....F.FF
3:Matched: 32 - UPX v0.89.6 - v1.02 / v1.05 - v1.22 Modified = 01DB..078B1E83EEFC11DB..EDB80100000001DB..078B1E83EEFC11DB11C001DB73..75
4:Matched: 55 - UPX 2.90 [LZMA] Delphi stub -> Markus Oberhumer, Laszlo Molnar & John Reise = 60BE........8DBE........5783CDFFEB109090909090908A064688074701DB75078B1E83EEFC11DB72EDB80100000001DB75078B1E83EEFC11DB11C001DB
5:Matched: 7 - UPX v3.0 = 60BE......008DBE......FF57

Please Watch the Result #3, Its Start with 01DB..078B1, which is the False result because

the data Start with 60BE15104B008DBEEBFFF

How can i solve this issue ? :D

73 108 111 118 101 65 117 116 111 105 116

Link to comment
Share on other sites

Thank You very much for your reply. 1stly i tried with REGexp, but it never worked like i want.

The problem with REGEXP is,

ie:

We have this signature "FFFFFF0000000000003000000040000000000000" for Microsoft Visual Basic 5.0

and we want to search this sig in the RAW data from the first byte

Raw Data:

558BEC6AFF68D834400068302C400064A100000000506489250000000083C4985356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFFFFFFC70564554000FFFFFFFFFF15083240008B0D545540008908FFFFFF0000000000003000000040000000000000

as you can see RegExp also give positive result for this condition;

but the rite condition is:

FFFFFF0000000000003000000040000000000000558BEC6AFF68D834400068302C400064A100000000506489250000000083C4985356578965E8C745FC000000006A02FF152032400083C404C70560554000FFFFFFFFC70564554000FFFFFFFFFF15083240008B0D545540008908

I want to match bytes from the start of the data not from the whole data string.

Regards;

Digisoul

Did you try that with my code? When you run a Binary type through String() it puts "0x" in front of it. Although it is trivial to change the RegExp pattern to match something at the beginning of the string (with "\A") the pattern I used starts with "0x" and therefore will always start matching from the beginning. It is not possible for the pattern I used to match in the middle of the string because "0x" only occurs in the beginning.

If that's not good enough for you, then post a demo script that can actually be run, complete with match and no match binary input values as mine had. That will overcome the vague descriptions.

:D

Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law
Link to comment
Share on other sites

Did you try that with my code? When you run a Binary type through String() it puts "0x" in front of it. Although it is trivial to change the RegExp pattern to match something at the beginning of the string (with "\A") the pattern I used starts with "0x" and therefore will always start matching from the beginning. It is not possible for the pattern I used to match in the middle of the string because "0x" only occurs in the beginning.

If that's not good enough for you, then post a demo script that can actually be run, complete with match and no match binary input values as mine had. That will overcome the vague descriptions.

:D

I am sorry :D

I didn't notice that you used 'String'.

Thank you very much for your kind help.

73 108 111 118 101 65 117 116 111 105 116

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...