Fast byte[] searching

[SheenBR]

I have a Dictionary<int,byte[]> with 191k elements. I also have a buffer (byte[] aswell) that I get by using File.ReadAllBytes (the file has aprox. 4mb).

The problem:

I have to search the entire 4mb buffer for the given Key in the dictionary, something like:

foreach(var element in dic)
{
   var timesFound = buffer.Locate(element.Key);
}

Locate being a function that searches the entire buffer for the given byte[] pattern.

But the searching is taking too long, I waited more than 2 minutes and it is still not even in the half progress...

What could I do to speed up the process?

 

[Negata]

Is it as it looks, you need to count occurences for every key in the dict? Also, which language is this?

 

[SheenBR]

The Key are offsets and the Values are byte[] that will be further transformed into strings. It is C#. Yes, I need to count occurences for every key in the dictionary. I am doing something like:

IF offset_in_key is PUSHed or MOVed in BUFFER then confidence++;

It is a program to search for every possible string in the executable and then start cleaning the output, one way I am doing to filter the garbage, is checking if that string is referenced in the exe. If it is not, then it is crap. (possibly)

 

[Negata]

I still don't understand everything, so by locating a string (referring to the byte[]) do you mean you have to scan through the file for whether it exists or just check a known location for if it's still there?

What does "every possible string" mean? How are they generated? Do they have any known characteristics such as known average/max length or what range of characters they may be?

 

[SheenBR]

Basically it is this algorithm by bobsobol: http://forum.ragezone.com/f399/extract-strings-aid-translation-728191/

I just translated to C# and instead of saving directly the string, I save the byte, so I can convert them to string afterwards. But, as this code gathers everything, I need to check if the string is referenced in the executable.

Example:

PUSH offset1
MOV eax,offset2

Then I generate the bytes[] for the PUSH/MOV instruction and I search the entire buffer for that code, to see if the string is used somewhere in the executable. Clear now? :

Maybe here you can find more info: http://forum.ragezone.com/f740/automatic-translator-922609-new/

 

[Negata]

What you're offering sounds terribly inefficient (as you already witnessed it to be) and there must be another way.

So it is not the plain strings that you're searching for but them extended with the instruction code. This is good! The first step should be gathering the list of referrers to all referred addresses (anything that fits the pattern of the code that you would generate from each offsetstring) from the file and then making the comparison against that list. That way you'll have to process the 4mb file only once. Or if you prefer a more straight forward approach, while processing the file for every string that fits the pattern, extract the offset part of it from between the instructions and then make the lookup from your dict. As dict lookups take only a logarithmic time the algorithm should finish nearly as quickly as it would when simply scanning the file once.

If above is a bit unclear, here's the gist of what I meant not that you'd necessarily need it:
Say we have an offset 0x1234 which would make the instruction AA1234BBCCCC for you to search. Go through the file matching any AAxxxxBBCCCC's and make a dictionary lookup with the xxxx part.

I'm not sure, is this viable? There might be something I don't realize right now.

 

[SheenBR]

I decided to create a dictionary with every MOV & PUSH instructions and then compare it against my offsets.. would be better than what I am already doing I suppose

 

[Negata]

I decided to create a dictionary with every MOV & PUSH instructions and then compare it against my offsets.. would be better than what I am already doing I suppose

Isn't that almost exactly what I was suggesting, anyway

In fact even if you indexed every byte array of length n into a dictionary and made lookups against that it would still be an order of magnitude faster than what you're doing now, it would take a while to process it and n*4MB of memory, but each lookup would only take a time of c*log2(filesize) where c is a smallish constant in comparison to to a time linear in filesize. In your case, only indexing every mov-push the memory requirement is yet a lot smaller while each dictionary query will not be significantly more efficient (only by a factor of 2-4 perhaps)

When you have the 2 dictionaries: the mov-pushes and your strings, see which one is larger and use that as the one to target your searches into for a little more boost - although most likely parsing the file for the first time is the most significant task anyway so the rest doesn't matter that much.

 

[SheenBR]

Yes, I read in you answer ^^

The speed has considerably increased now. I am using a regular expression to extract all push instructions that I find. But yet, the speed isnt so fast due to the number of elements.

I think I can speed up more by cleaning my push dictionary. Since I am using regex to find them, my only guess is that I need to improve my filter.

((68).([0-9a-fA-F]{2}).([0-9a-fA-F]{2}).([0-9a-fA-F]{2}).([0-9a-fA-F)]{2}))

Im no pro in regex and Im not sure if the PUSH instructions all have the same structure. 68 + (offset - 4bytes), maybe someone that has understanding about both subjects can help me building my regex?

 

[Negata]

I think I can speed up more by cleaning my push dictionary. Since I am using regex to find them, my only guess is that I need to improve my filter.

((68).([0-9a-fA-F]{2}).([0-9a-fA-F]{2}).([0-9a-fA-F]{2}).([0-9a-fA-F)]{2}))

Im no pro in regex and Im not sure if the PUSH instructions all have the same structure. 68 + (offset - 4bytes), maybe someone that has understanding about both subjects can help me building my regex?

What's the part in the regex that you need to capture?

 

[SheenBR]

"AA BB CC DD EE" being: AA: 68 and b,c,d,e being any values that might represent a push instruction

 

[Negata]

I mean, do you really need all of them separately? You should only use braces around the part that you need to capture... if it's the whole of it then you could do this:

(68.[0-9a-fA-F]{2}.[0-9a-fA-F]{2}.[0-9a-fA-F]{2}.[0-9a-fA-F]{2})

If only I knew more of the exact format I could be of more help, unfortunately it's been years since I last worked with assembly and ollydbg... Maybe you could copy&paste a few example cases here?

 

[jMerliN]

This can't really be done faster than O(nm), and here n = 4 million and m = 191000, so it's going to take some time.

You may have to fundamentally change what you're doing to do it any faster.

 

[Negata]

This can't really be done faster than O(nm), and here n = 4 million and m = 191000, so it's going to take some time.

You may have to fundamentally change what you're doing to do it any faster.

I don't know if you read through all the discussion but in fact it can be done in O(n + logm) because the byte arrays to look for in the file have a fixed (short) length and hence can be collected into a dictionary.

So yeah that's kind of the fundamental change in how to do it, not in what to do though.

 

[SheenBR]

I guess here are the info you need: PUSH - Push Word or Doubleword Onto the Stack

 

[Negata]

Do you have to have this in the string format by the way? It would be trivial to go over the file in binary byte by byte so that if the read byte is 68 then read the next two bytes as a short and that's your key to the string dictionary. But yeah if you do go over it as a string and want to use a regex capture then I suppose the best you can do is 68.(.{11}) whether you include the 68. doesn't make much of a difference. I simplified the regex that much because isn't 0-9a-fA-F 's and dots between them all you have in the file anyway? Then it doesn't make a difference if you accept only the specified ones or any character at all. (Note that . stands for any character, not the literal .)

When you have the regex tuned let me know which takes longer, the regex parsing or dictionary lookups.

 

[jMerliN]

I don't know if you read through all the discussion but in fact it can be done in O(n + logm) because the byte arrays to look for in the file have a fixed (short) length and hence can be collected into a dictionary.

So yeah that's kind of the fundamental change in how to do it, not in what to do though.

It's pretty easy to determine if a bunch of 4 byte addresses are present in the binary, but it's not easy to determine if they're actually used. That's roughly equivalent to the halting problem.

For instance, what if there is an array of string pointers. That array stores the address in the .data section of each of those strings, but now you need to find code that does this:

mov eax,

push [eax+4]

Now it's referencing the second string. How do you determine if every string in that table is referenced?

So the most reasonable solution here is to just check if the address has been referenced somewhere in the executable.

To do that, just build a hash table of those addresses (as dwords). Then for i from 0 to file length - 4, take the dword at offset i and look it up in the table.

 

[Negata]

It's pretty easy to determine if a bunch of 4 byte addresses are present in the binary, but it's not easy to determine if they're actually used. That's roughly equivalent to the halting problem.

Obviously.

So the most reasonable solution here is to just check if the address has been referenced somewhere in the executable.

To do that, just build a hash table of those addresses (as dwords). Then for i from 0 to file length - 4, take the dword at offset i and look it up in the table.

Among the things already mentioned...

 

[jMerliN]

Obviously.
Among the things already mentioned...

There's talk about pattern matching to try and guess if it's a mov/push etc, I'm suggesting just drop all of that and look for the dword within the file. Unless I can't read, I've skimmed through most of this because I'm really busy today .

 

[Negata]

Yeah I did say "Do you have to have this in the string format by the way? It would be trivial to go over the file in binary byte by byte so that if the read byte is 68 then read the next two bytes as a short and that's your key to the string dictionary." What we didn't get to was whether it's enough to consider only the bytes after a 68 but I mentioned it's also viable to collect all of the file. But yeah anyway, I guess we could argue all night about who agrees the most with the other but at least it's safe to say the approach is recommended by more than just one person here.