Thread: Make it fast !

For a single signature, the fastest algorithm you could use is probably Boyer-Moore. If you'll be scanning for many many signatures, it's not very efficient to scan for each of them one by one. You'd probably want to reduce the entire set of signatures down to a single state machine, kind of like a regular expression.

I assume you're writing some kind of virus scanner or similar..

Personally, I'd

1) Look at using pointers to control the loops, rather than array indices.

2) Break the inner loop into a separate function.

3) Find ways to avoid using any break/continue statements. This makes code more readable, and also can make it more efficient (by reducing unnecessary complexity that the compiler must deal with). Bear in mind that

Code:

   if (a != b) continue;
   stuff();

is equivalent (in a loop body) to

Code:

    if (a == b) stuff();

4) Avoid computing the same thing repeatedly in a loop (your code is doing this - accessing array[index] involves a computation - this is also one reason why controlling your loops with pointers can help)

Short of that, look at using a better algorithm. An algorithm that speeds things up by an order of magnitude is better than a few tweaks that shave a microsecond here and there.

Code:

            if(j == sigLen - 1) //if were at the end, we found a match, return index.
                return i;

Why do you loop for j being less than sigLen if you're just going to add another if check every loop to see if it's sigLen -1 ?


Quzah.

Originally Posted by eros

whiteflags,

BYTE file[] would be a standard PE file. Ranging from 150 bytes to 20mb in length.

short sig[] would be a pattern of shorts, including wildcards. Such as

Code:

short sig[] = { 0x20, 0xE6, 0xEA, 0x19, 0xBE, 0x28, -1, -1, -1, -1, 0x13,
 -1, 0x20, 0x39, 0xEA, 0x19, 0xBE, 0x28, -1, -1, -1, -1, 0x13, -1, 0x11,
 -1, 0x11, -1, 0x16, 0x1F, 0x40, 0x28, -1, -1, -1, -1, 0x26 };

Firstly, ditto to everything said so far.

Secondly, what is this for?!

Originally Posted by iMalc

Secondly, what is this for?!

Think of it as a strcmp with wild card support. The hex are the values of the characters in the string he wants to find, the -1 are wild cards.


Quzah.

Why are you checking to see if j is sigLen still, when it's your loop control?

Code:

for( j = ... )
{
}
if( j == sigLen )
    return i;

Put it outside the loop, because you don't need to check to control the loop and inside the loop too. You're checking twice for something you only need to check once.


Quzah.

Are you tied to using an array of bytes for the signature? You might consider modifying your signature structure to something like:

Code:

struct signature_chunk {
    char *bytes;  // null here signifies end of list
    int offset;
    int len;
};

Then, each signature is an array of these elements, like so:

Code:

struct signature_chunk sig[] = {
    {{0x20, 0xE6, 0xEA, 0x19, 0xBE, 0x28}, 0, 6},
    {{0x13}, 10, 1},
    {{0x20, 0x39, 0xEA, 0x19, 0xBE, 0x28}, 12, 6},
    {0x13}, 22, 1},
    {{0x11}, 24, 1},
    {{0x11}, 26, 1},
    {{0x16, 0x1F, 0x40, 0x28}, 28, 4}
    {{0x26}, 36, 1},
    {NULL, -1, -1}  // end of list marker
};

You can use Tater's method of finding possible starts by scanning your input for sig[0].bytes[0]. Once you've found a possible start, you can loop through each chunk of your signature and do something like

Code:

loop through each byte of file  // index i
    if the current byte in file matches the first byte of the first chunk of our signature
        for each chunk in our signature  // index j
            if (memcmp(file[i + sig[j].offset], sig[j].bytes, sig[j].len)) {
                // memcmp failed, so this doesnt match the signature

This saves you in at least two ways. First, you don't waste time checking for "wildcard" bytes in the signature to tell you to ignore that byte in file. You just don't check them. Second, you are leveraging the optimized library routine memcmp instead of writing your own, less optimal version. Combine this with some tips from other posters, like using pointer arithmetic instead of array indexes, and caching values you will use multiple times throughout your function, and you should be in decent shape. You should be able to extend this to multiple signatures if need be by creating an array of arrays of signature chunks.

Since I'm guessing you actually have a number of signatures, you may want to make an array of

Thanks for the idea anduril462, it would be very hard to impliment in my situation. But ill give it a shot soon.

This is what i got from Taters method, it is faster:

Code:

BOOL valid(BYTE *file, short *sig, int offset, int len)
{
	int i,j;
	int end = offset + len; //compute end before hand, so we dont have to do it every time

	for(i = offset, j=0; i < end; ++i, ++j)	
		if(sig[j] >= 0 && file[i] != sig[j]) //wildcard and check
			return FALSE;

	return TRUE;
}

BOOL DLL_EXPORT ScanSig(BYTE *file, int fileLen, short *sig, int sigLen)
{
    int i;
    for(i = 0; i < fileLen; ++i)
    {
        if( ( file[i] == sig[0] ) && ( file[i + sigLen] == sig[sigLen] ) ) // check if plausable match
			if( valid(file, sig, i, sigLen) ) // check if whole match
				return TRUE;
    }

    return FALSE;
}

Is it bad to be passing the "file" and "sig" for every check ? Would not passing it speed it up?

Code:

BOOL DLL_EXPORT ScanSig(BYTE *file, int fileLen, BYTE *sig, int sigLen)
{  int i, x, y;
    y = (fileLen - sigLen) + 1;
    for(i = 0; i <  y; ++i)
       { if ( file[i] == sig[0] )
           { for( x = 0, (x < sigLen) && (file[i + x] == sig[x]), x++);
              if ( x > sigLen)
                return TRUE;  } }
    return FALSE; }