Exetools
Page 1 of 2 1 2
Show 40 post(s) from this thread on one page

Exetools (https://forum.exetools.com/index.php)
-   Source Code (https://forum.exetools.com/forumdisplay.php?f=46)
-   -   [C++] C++11 Signature Scanning (https://forum.exetools.com/showthread.php?t=16459)

atom0s 01-16-2015 14:11
[C++] C++11 Signature Scanning
 
One of the more modern methods of approaching an application for modifications and relocation of specific functions, data, pointers, etc. is through signature scanning. Rather then using raw offsets or addresses, signature scanning allows you to locate data through known instructions of a function that make use of that data. I wont get into the specifics of signature scanning in this topic though for those that do not understand it.

Read this full tutorial on my personal site here:
Code:
http://atom0s.com/forums/viewtopic.php?f=5&t=4
Here is the important code that is used with this:
PHP Code:
/**
 * @brief Scans a given chunk of data for the given pattern and mask.
 *
 * @param data          The data to scan within for the given pattern.
 * @param baseAddress   The base address of where the scan data is from.
 * @param lpPattern     The pattern to scan for.
 * @param pszMask       The mask to compare against for wildcards.
 * @param offset        The offset to add to the pointer.
 * @param resultUsage   The result offset to use when locating signatures that match multiple functions.
 *
 * @return Pointer of the pattern found, 0 otherwise.
 */
static DWORD __stdcall FindPattern(std::vector<unsigned char> data, unsigned int baseAddress, const unsigned char* lpPattern, const char* pszMask, int offset, int resultUsage)
{
    // Build vectored pattern..
    std::vector<std::pair<unsigned char, bool>> pattern;
    for (size_t x = 0; x < strlen(pszMask); x++)
        pattern.push_back(std::make_pair(lpPattern[x], pszMask[x] == 'x'));
 
    // The result count for multiple results..
    auto resultCount = 0;
    auto scanStart = data.begin();
 
    while (true)
    {
        // Search for the pattern..
        auto ret = std::search(scanStart, data.end(), pattern.begin(), pattern.end(),
            [&](unsigned char curr, std::pair<unsigned char, bool> currPattern)
        {
            return (!currPattern.second) || curr == currPattern.first;
        });
 
        // Did we find a match..
        if (ret != data.end())
        {
            // If we hit the usage count, return the result..
            if (resultCount == resultUsage || resultUsage == 0)
                return (std::distance(data.begin(), ret) + baseAddress) + offset;
 
            // Increment the found count and scan again..
            ++resultCount;
            scanStart = ++ret;
        }
        else
            break;
    }
 
    return 0;
} 
Example Usage With Futures (Async)
PHP Code:
std::map<std::string, std::shared_future<unsigned long>> m_Signatures;

this->m_Signatures["sigName"] = std::async(std::launch::async, &FindPattern, std::ref(rawdata), sizeOfData, signature, mask, offset, resultUsage);

// Ensure all futures are completed..
std::for_each(this->m_Signatures.begin(), this->m_Signatures.end(), [](std::pair<std::string, std::shared_future<unsigned long>> s)
{
    // Obtain the current future status..
    auto status = std::future_status::timeout;
    do
    {
        status = s.second.wait_for(std::chrono::milliseconds(5));
    } while (status != std::future_status::ready);
 
    // Obtain the status value..
    auto pointer = s.second.get();
     
    //
    // At this point you can check if pointer is valid and handle
    // any invalid pointers as needed. Perhaps you want the application
    // to fail to load if any pointers are invalid etc.
    //
});

/**
 * @brief Returns a pointers current value.
 *
 * @param name          The name of the pointer to obtain.
 *
 * @return The value of the pointer, 0 if not found.
 */
unsigned long Memory::GetPointer(const std::string& name) const
{
    auto pointer = this->m_Signatures.find(name);
    if (pointer == this->m_Signatures.end())
        return 0;
    return pointer->second.get();
} 
Sorry for linking to my own site, the post limit is 10k chars which is too short to paste the whole post from my site. I included the important code above from the post though to have content here too.

mr.exodia 01-17-2015 05:26
Hi,

What I don't get is how your (linear) search (that uses all kinds of libraries) is faster than the linear search you say is slower at your website:

Code:
bool Compare(const BYTE* pData, const BYTE* bMask, const char* szMask)
{
    for (; *szMask; ++szMask, ++pData, ++bMask)
        if (*szMask == 'x' && *pData != *bMask)  return 0;
    return (*szMask) == NULL;
}
DWORD Pattern(DWORD dwAddress, DWORD dwLen, BYTE *bMask, char * szMask)
{
    for (DWORD i = 0; i < dwLen; i++)
        if (Compare((BYTE*)(dwAddress + i), bMask, szMask))  return (DWORD)(dwAddress + i);
    return 0;
}
The worst cast complexity of std::search is O(count1*count2) (see cppreference.com) and the worst case complexity of the algorithm above is also O(count1*count2), right? Do you have any idea what specifically makes your algorithm faster?

Greetings

EDIT: Here is a combined version of our efforts to make pattern finding easier: https://gist.github.com/mrexodia/f058868b81b2f1cb011a

atom0s 01-17-2015 09:44
Here is a benchmark of mine vs the original typical FindPattern you posted:

Code:
FindPattern Benchmark Example
(c) 2014 atom0s

================================================
Test Name  : FindPattern
Test Author : dom1n1k & Patrick (GameDeception)
Test Time  : 0.681074

================================================
Test Name  : FindPattern (C++11) w/ Async
Test Author : atom0s
Test Time  : 0.235662
In this benchmark app, I am scanning a total of 26 patterns. The way I have the benchmark setup is each test is given 3 functions:
- Initialize
- Release
- RunTest

Initialize is used to simply handle the basic stuff that the test may need to prepare itself for the test to be ran. Things that are not specific to the scanning directly. Such as any object creation and so on.
Release is to allow the test to cleanup anything it created etc.
RunTest is to allow the test to do its work to scan for all the signature in the given test data.

About The Tests
The test data is the Final Fantasy XI's main game file 'FFXiMain.dll'. I load the unpacked file into memory as the raw bytes, I do not actually load the game in any manner, so these are static scans from the files raw data.

Each test is given a total of 26 signatures to scan for within the same memory data.
So the benchmark is entirely fair in terms of what to look for and what it is looking within.

I created the C++11 / async method I use solely for this game and decided to share it since others may find it useful for faster and threaded scans. In an application where you only need to scan for a few signatures and do not need threading, then yeah mine may not be the best bet however, so far it has performed the best for me outside of some other methods I discussed on my personal site that a friend of mine (devnull) and I came up with.

There is definitely room for improvement and speed increases, this is just the fastest and cleanest method that devnull and I came up with so far that was easy to read and maintain while keeping speed and performance.

DMichael 01-17-2015 16:37
Quote:
Originally Posted by atom0s (Post 96772)
Here is a benchmark of mine vs the original typical FindPattern you posted:

Code:
FindPattern Benchmark Example
(c) 2014 atom0s

================================================
Test Name  : FindPattern
Test Author : dom1n1k & Patrick (GameDeception)
Test Time  : 0.681074

================================================
Test Name  : FindPattern (C++11) w/ Async
Test Author : atom0s
Test Time  : 0.235662
In this benchmark app, I am scanning a total of 26 patterns. The way I have the benchmark setup is each test is given 3 functions:
- Initialize
- Release
- RunTest

Initialize is used to simply handle the basic stuff that the test may need to prepare itself for the test to be ran. Things that are not specific to the scanning directly. Such as any object creation and so on.
Release is to allow the test to cleanup anything it created etc.
RunTest is to allow the test to do its work to scan for all the signature in the given test data.

About The Tests
The test data is the Final Fantasy XI's main game file 'FFXiMain.dll'. I load the unpacked file into memory as the raw bytes, I do not actually load the game in any manner, so these are static scans from the files raw data.

Each test is given a total of 26 signatures to scan for within the same memory data.
So the benchmark is entirely fair in terms of what to look for and what it is looking within.

I created the C++11 / async method I use solely for this game and decided to share it since others may find it useful for faster and threaded scans. In an application where you only need to scan for a few signatures and do not need threading, then yeah mine may not be the best bet however, so far it has performed the best for me outside of some other methods I discussed on my personal site that a friend of mine (devnull) and I came up with.

There is definitely room for improvement and speed increases, this is just the fastest and cleanest method that devnull and I came up with so far that was easy to read and maintain while keeping speed and performance.
interesting conclusion but it not matter
is more about hardware and btw scanning speed won't be noticeable when the difference is measured only in millisecond
plus another thing is about compiler optimization which affects most on the speed(after hardware of course)

mr.exodia 01-17-2015 20:38
Quote:
Originally Posted by DMichael (Post 96778)
interesting conclusion but it not matter
I don't agree with you here. Maybe it doesn't matter for searching a few MBs of data, but it will start to matter if you have to find 20 patterns in 2GB of data :)

Carbon 01-17-2015 21:14
I think both your implementations are still not perfect. Think about this: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
or at least
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm
This algorithm is even more efficient for byte search. Skip as many bytes as possible...

atom0s 01-18-2015 03:30
Quote:
Originally Posted by Carbon (Post 96786)
I think both your implementations are still not perfect. Think about this: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
or at least
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm
This algorithm is even more efficient for byte search. Skip as many bytes as possible...
Yeah there is a lot of room for improvement. My method was more aimed towards making use of C++11 features (to try them out and such) as well as being more maintainable as well as async which I needed for my project that I use it in.

Implementing Boyer Moore will definitely be a bit faster though. :)

Comparing my FindPattern to the original posted above, mine sees a lot of improvement when the data being scanned within is large and the number of scans being done is high. For low amounts of scanning and where async is not required, then the original will tend to outperform mine.

Overall it really depends on some specific factors:
- The data size being scanned within.
- The number of patterns being looked for.
- Threading; is it required or not, (along with thread-safety).
- Hardware can land up playing a roll as well etc.

Another implementation that could make use of different hardware would be a GPU implementation, which could also have a handful of speed benefits depending on similar factors above.

Nukem 01-19-2015 02:45
Quote:
Originally Posted by atom0s (Post 96793)
Yeah there is a lot of room for improvement. My method was more aimed towards making use of C++11 features (to try them out and such) as well as being more maintainable as well as async which I needed for my project that I use it in.

Implementing Boyer Moore will definitely be a bit faster though. :)
Actually a couple of those methods have been tested here: https://github.com/learn-more/findpattern-bench

BMH was second place when I checked (57ms):
Code:
FindPattern benchmark
Page size: 4096, allocating 22 pages (including 2 guard pages).
Running tests on 9 different implementations
===========
Running M-i-K-e
ran outside the area
FAILED
===========
Running Trippeh
Finding pattern 0 x 1000 took 1774.23 ms.
Finding pattern 1 x 1000 took 1905.49 ms.
===========
Running Trippeh v2
Finding pattern 0 x 1000 took 81.864 ms.
Finding pattern 1 x 1000 took 81.937 ms.
===========
Running Trippeh v3
Failed, cheating with the pattern length!
FAILED
===========
Running learn_more
Finding pattern 0 x 1000 took 204.665 ms.
Finding pattern 1 x 1000 took 164.068 ms.
===========
Running learn_more v2
Finding pattern 0 x 1000 took 82.226 ms.
Finding pattern 1 x 1000 took 82.679 ms.
===========
Running afffsdd
Finding pattern 0 x 1000 took 40.943 ms.
Finding pattern 1 x 1000 took 40.968 ms.
===========
Running DarthTon
Finding pattern 0 x 1000 took 56.974 ms.
Finding pattern 1 x 1000 took 57.045 ms.
===========
Running kokole
Finding pattern 0 x 1000 took 122.41 ms.
Finding pattern 1 x 1000 took 122.646 ms.
Done.
Press any key to continue . . .
Although it really does depend on what you're scanning/how long it is. I prefer a linear search because the code is shorter and it's still pretty fast.

atom0s 01-19-2015 03:40
Ah interesting, I'll take their examples and add it to my tester and see what I get out of them. I can post the results here later on too.

As for the portability / 64bit questions and comments, here is mine that should work on both now:
PHP Code:
/**
 * @brief Scans a given chunk of data for the given pattern and mask.
 *
 * @param data          The data to scan within for the given pattern.
 * @param baseAddress   The base address of where the scan data is from.
 * @param lpPattern     The pattern to scan for.
 * @param pszMask       The mask to compare against for wildcards.
 * @param offset        The offset to add to the pointer.
 * @param resultUsage   The result offset to use when locating signatures that match multiple functions.
 *
 * @return Pointer of the pattern found, 0 otherwise.
 */
static intptr_t FindPattern(std::vector<unsigned char> data, intptr_t baseAddress, const unsigned char* lpPattern, const char* pszMask, intptr_t offset, intptr_t resultUsage)
{
    // Build vectored pattern..
    std::vector<std::pair<unsigned char, bool>> pattern;
    for (size_t x = 0, y = strlen(pszMask); x < y; x++)
        pattern.push_back(std::make_pair(lpPattern[x], pszMask[x] == 'x'));
 
    auto scanStart = data.begin();
    auto resultCnt = 0;
 
    while (true)
    {
        // Search for the pattern..
        auto ret = std::search(scanStart, data.end(), pattern.begin(), pattern.end(),
            [&](unsigned char curr, std::pair<unsigned char, bool> currPattern)
        {
            return (!currPattern.second) || curr == currPattern.first;
        });
 
        // Did we find a match..
        if (ret != data.end())
        {
            // If we hit the usage count, return the result..
            if (resultCnt == resultUsage || resultUsage == 0)
                return (std::distance(data.begin(), ret) + baseAddress) + offset;
 
            // Increment the found count and scan again..
            ++resultCnt;
            scanStart = ++ret;
        }
        else
            break;
    }
 
    return 0;
} 
I used the following to test compiling and running on Linux:
Code:
http://www.tutorialspoint.com/compile_cpp11_online.php
I'll post the full benchmark once I have time to sit down and add all the other tests to mine and adjust as needed for how mine works.

mr.exodia 01-20-2015 08:36
Updated benchmark with atom0s' pattern finder, my pattern finder (which has nibble support, so not really a fair comparison) and atom0s' pattern finder updated with nibble support:

https://github.com/mrexodia/findpattern-bench

Code:
FindPattern benchmark
Page size: 4096, allocating 22 pages (including 2 guard pages).
Running tests on 10 different implementations
===========
Running learn_more
Finding pattern 0 x 1000 took 1103.94 ms.
Finding pattern 1 x 1000 took 887.791 ms.
===========
Running learn_more v2
Finding pattern 0 x 1000 took 467.905 ms.
Finding pattern 1 x 1000 took 473.792 ms.
===========
Running fdsasdf
Finding pattern 0 x 1000 took 216.19 ms.
Finding pattern 1 x 1000 took 217.753 ms.
===========
Running DarthTon
Finding pattern 0 x 1000 took 296.328 ms.
Finding pattern 1 x 1000 took 293.352 ms.
===========
Running kokole
Finding pattern 0 x 1000 took 541.427 ms.
Finding pattern 1 x 1000 took 587.715 ms.
===========
Running mrexodia
Finding pattern 0 x 1000 took 1089.7 ms.
Finding pattern 1 x 1000 took 1037.04 ms.
===========
Running atom0s
Finding pattern 0 x 1000 took 2274.7 ms.
Finding pattern 1 x 1000 took 2299.61 ms.
===========
Running atom0s (mrexodia modification)
Finding pattern 0 x 1000 took 1539.4 ms.
Finding pattern 1 x 1000 took 1877.84 ms.
===========
Running mrexodia (horspool)
Finding pattern 0 x 1000 took 602.06 ms.
Finding pattern 1 x 1000 took 572.722 ms.
===========
Running dom1n1k_Patrick
Finding pattern 0 x 1000 took 793.266 ms.
Finding pattern 1 x 1000 took 765.38 ms.
Done.
And yea... my laptop has an 1.8Ghz i3 so it's terribly slow compared to Nukem :D

DMichael 01-21-2015 15:59
hmm probably no one need it anyway i'm have modified the algorithm by patrick and dom1n1k in my old project for x64 compatibility here it is:

Quote:
bool Match(const BYTE* pData, const BYTE* bMask, const char* szMask)
{
for(; *szMask; ++szMask,++pData,++bMask)
{
if(*szMask=='x' && *pData!=*bMask )
return false;
}

if(*szMask == 0x00)
return true;

return false;
}

DWORD_PTR FindPattern(DWORD_PTR dwAddress,size_t dwLen,const BYTE *bMask,const char * szMask)
{
for(size_t i=0; i < dwLen; i++)
{
if( Match ( (BYTE*) (dwAddress+i) ,bMask,szMask ) == true )
return (DWORD_PTR)(dwAddress+i);
}

return NULL;
}

mr.exodia 01-21-2015 18:01
@DMichael: I recommend using a different algorithm, this one is the second-worst in time :D Thanks anyway.

DMichael 01-21-2015 18:35
Quote:
Originally Posted by mr.exodia (Post 96866)
@DMichael: I recommend using a different algorithm, this one is the second-worst in time :D Thanks anyway.
sure but you checks are meaning less since it mostly depend on compiler and hardware

alephz 01-24-2015 22:41
If anyone need a real example of signature search, I can recommend ClamAV source.

mr.exodia 01-25-2015 21:45
Quote:
Originally Posted by alephz (Post 96943)
If anyone need a real example of signature search, I can recommend ClamAV source.
After some reading it appears to be using Aho-Corasick or the Booyer-more string search algorithms, which is nice indeed. It is very unfortunate that the signature search is so tightly integrated with the codebase, otherwise I would have added it to the tests...


All times are GMT +8. The time now is 21:47.
Page 1 of 2 1 2
Show 40 post(s) from this thread on one page

Powered by vBulletin® Version 3.8.8
Copyright ©2000 - 2026, vBulletin Solutions, Inc.
Always Your Best Friend: Aaron, JMI, ahmadmansoor, ZeNiX