加速字节模式扫描 C++

Question

我编写了一个程序来扫描在我的进程中注入的错误代码，如果可能的话，我想加快它的速度。我将代码更改为一次扫描 4 个字节而不是 1 个字节，并使用掩码 AND 表示危险字节，但它仍然很慢。AntiCheats，尤其是 Anti Virus 具有超快的算法。有人可以指出我快速扫描的正确方向吗？

AddSignatureToDB("75??83FB5375??81FE890000000F84????????E9????????83FB4F75", ERROR_SIGID_1);

void AddSignatureToDB(char* szSig, DWORD dwSigID)
{
    char szHex[]        = "0x00";
    int iSigLen = lstrlenA(szSig) / 2;
    int iPadding = iSigLen % 4;

    BYTE* mSigData = new BYTE[iSigLen+iPadding];
    BYTE* mSigMask = new BYTE[iSigLen+iPadding];

    for (int i = 0; i < iSigLen; i++)
    {
        mSigData[i] = 0x00;
        mSigMask[i] = 0x00;

        if (szSig[i * 2] != '?')
        {
            szHex[3] = szSig[i * 2];
            mSigData[i] |= (strtoul(szHex, NULL, 0) << 4 & 0xF0);
            mSigMask[i] |= 0xF0;
        }

        if (szSig[i * 2 + 1] != '?')
        {
            szHex[3] = szSig[i * 2 + 1];
            mSigData[i] |= (strtoul(szHex, NULL, 0) & 0x0F);
            mSigMask[i] |= 0x0F;
        }
    }

    if (iPadding > 0)
    {
        for (int i = 0; i < iPadding; i++)
        {
            mSigData[iSigLen+i] = 0x00;
            mSigMask[iSigLen+i] = 0x00;
        }
    }

    this->SigDB[this->iNumSig].mSigBytes = mSigData;
    this->SigDB[this->iNumSig].mSigMasks = mSigMask;
    this->SigDB[this->iNumSig].iNumBytes = iSigLen+iPadding;
    this->SigDB[this->iNumSig].dwSigID = dwSigID;
    this->iNumSig++;
}

bool ScanBlockForSig(BYTE* pBuffer, int iBufSize, T_SigHolder* Sig)
{
    bool bFound = true;
    bool bFound2 = false;

    for (int i = (DWORD)pBuffer; i < ((DWORD)pBuffer + iBufSize - Sig->iNumBytes); i++)
    {
        bFound = true;

        int iStepped = 0;

        while (iStepped < Sig->iNumBytes)
        {
            DWORD dwMask = *(DWORD*)&Sig->mSigMasks[iStepped];
            DWORD dwPart1 = *(DWORD*)&Sig->mSigBytes[iStepped];
            DWORD dwPart2 = *(DWORD*)(i + iStepped) & dwMask;

            if (dwPart1 != dwPart2)
            {
                bFound = false;
                break;
            }

            iStepped += 4;
        }

        if (bFound == true)
        {
            dwAddressFound = (DWORD)i;
            bFound2 = true;
            break;
        }

    }

    return bFound2;
}

Answer 1

模式搜索的问题既令人着迷，而且幸运的是，它定义得很好。我们将搜索字符串定义为长度 n，将要搜索的模式数定义为 p，以及模式的组合长度 m。

您可以将字符串搜索视为模式扫描的一个专长。当您知道这一点时，它会解锁众所周知的算法，例如 Boyer Moore，如果该模式没有出现在搜索文本中，则该算法的最坏情况为 O(n+m)，这比 O(nm) 的朴素方法要快。

您在此处寻找的算法子类别是多模式搜索。为此，您应该调查 Rabin Karp 算法的工作原理（https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm），它比 Boyer Moore 慢，但可以扩展以支持多模式搜索在最坏的情况下为 O(nm)，空间为 O(p)。

然而，我用来解决这个问题的最快算法是 Aho Corasick ( https://github.com/bigdatadev/aho_corasick )。它不是 O(m) 上内存效率最高的算法，但它在最坏情况下的性能 O(n+m) 方面是最快的。