6.2 Sunday搜索記憶體特征

Sunday 演算法是一種字元串搜索演算法，由Daniel M.Sunday於1990年開發，該演算法用於在較長的字元串中查找子字元串的位置。演算法通過將要搜索的模式的字元與要搜索的字元串的字元進行比較，從模式的最左側位置開始。如果發現不匹配，則演算法將模式向右滑動一定數量的位置。這個數字是由當前文本中當前模式位置的最右側字元確定的。相比於暴力方法，該演算法被認為更加高效。

6.2.1 字元串與特征碼轉換

GetSignatureCodeArray函數，該函數用於將給定的十六進位串表示的位元組碼特征碼轉換為十進位數，存儲在一個整型數組中，以便後續進行搜索。同時，特征碼中的未知標記符號?會被用256 替代，方便後續搜索對特征碼的匹配。

其中，參數SignatureCode為一串十六進位字元串，描述要搜索的位元組碼特征碼，參數BytesetSequence為一個整型數組，用於存儲將十六進位數轉為十進位後的結果。該函數首先計算給定的十六進位串中包含的位元組碼個數，因為每個位元組對應兩個十六進位字元，再加上每兩個字元間的空格，故需要將十六進位字元串長度除以三，再加上一。

接下來，函數逐個字元讀入特征碼串中的每一個十六進位數，如果是有效的十六進位數，則轉化為十進位數存入BytesetSequence數組中。如果遇到未知的標記符號?，則在BytesetSequence數組中用256表示該位置的值。最後，返回特征碼數組中位元組碼的個數。

// 定義全局變數
#define BLOCKMAXSIZE 409600  // 每次讀取記憶體的最大大小
BYTE* MemoryData;            // 每次將讀取的記憶體讀入這裡
SHORT Next[260];             // 搜索下一個記憶體區域

// 將傳入的SignatureCode特征碼字元串轉換為BytesetSequence特征碼位元組集
WORD GetSignatureCodeArray(char* SignatureCode, WORD* BytesetSequence)
{
    int len = 0;

    // 用於存儲特征碼數組長度
    WORD SignatureCodeLength = strlen(SignatureCode) / 3 + 1;

    // 將十六進位特征碼轉為十進位
    // 依次遍歷SignatureCode中的每一個十六進位數
    for (int i = 0; i < strlen(SignatureCode);)
    {
        char num[2];

        // 分別取出第一個和第二個十六進位字元
        num[0] = SignatureCode[i++];
        num[1] = SignatureCode[i++];
        i++;

        // 如果兩個字元都是有效的十六進位數，則將它們轉換成十進位並存儲到 BytesetSequence 中
        if (num[0] != '?' && num[1] != '?')
        {
            int sum = 0;
            WORD a[2];

            // 分別將兩個十六進位字元轉換成十進位數
            for (int i = 0; i < 2; i++)
            {
                // 如果是數字
                if (num[i] >= '0' && num[i] <= '9')
                {
                    a[i] = num[i] - '0';
                }
                // 如果是小寫字母
                else if (num[i] >= 'a' && num[i] <= 'z')
                {
                    a[i] = num[i] - 87;
                }
                // 如果是大寫字母
                else if (num[i] >= 'A' && num[i] <= 'Z')
                {
                    a[i] = num[i] - 55;
                }
            }

            // 計算兩個十六進位數轉換後的十進位數，並將其存儲到 BytesetSequence 數組中
            sum = a[0] * 16 + a[1];
            BytesetSequence[len++] = sum;
        }
        else
        {
            BytesetSequence[len++] = 256;
        }
    }
    return SignatureCodeLength;
}

6.2.2 搜索記憶體區域特征

SearchMemoryBlock函數，該函數用於在指定進程的某一塊記憶體中搜索給定的位元組碼特征碼，查找成功則將匹配地址存入結果數組中。其中，參數hProcess為指向要搜索記憶體塊所在進程的句柄，SignatureCode為給定特征碼的數組指針，SignatureCodeLength為特征碼長度，StartAddress為搜索的起始地址，size為搜索記憶體的大小，ResultArray為存儲搜索結果的數組引用。

通過調用ReadProcessMemory函數讀取進程記憶體中指定地址和大小的數據，將讀取的數據存入變數MemoryData中，然後對讀取的數據進行匹配，查找特征碼。若匹配成功，則將特征碼匹配的起始地址存入結果數組中。在匹配時，採用了KMP演算法。如果找到與特征碼中的位元組碼不匹配的位元組，就根據Next數組記錄的回溯位置，重新從失配的位置開始匹配，以降低匹配的時間複雜度，提高搜索效率。在代碼中，若特征碼中存在問號，則匹配位置從問號處開始重新匹配，如果沒有則繼續按照Next數組回溯進行匹配。

// 獲取GetNextArray數組
void GetNextArray(short* next, WORD* SignatureCode, WORD SignatureCodeLength)
{
    // 特征碼位元組集的每個位元組的範圍在0-255（0-FF）之間
    // 256用來表示問號，到260是為了防止越界
    for (int i = 0; i < 260; i++)
    {
        next[i] = -1;
    }
    for (int i = 0; i < SignatureCodeLength; i++)
    {
        next[SignatureCode[i]] = i;
    }
}

// 搜索一塊記憶體區域中的特征
void SearchMemoryBlock(HANDLE hProcess, WORD* SignatureCode, WORD SignatureCodeLength, unsigned __int64 StartAddress, unsigned long size, vector<unsigned __int64>& ResultArray)
{
    // 讀取指定進程的記憶體數據到MemoryData緩衝區中
    if (!ReadProcessMemory(hProcess, (LPCVOID)StartAddress, MemoryData, size, NULL))
    {
        return;
    }

    // 迴圈遍歷記憶體數據緩衝區
    for (int i = 0, j, k; i < size;)
    {
        j = i; k = 0;

        // 逐個比對記憶體數據緩衝區中的位元組和特征碼中的位元組
        for (; k < SignatureCodeLength && j < size && (SignatureCode[k] == MemoryData[j] || SignatureCode[k] == 256); k++, j++);

        // 如果特征碼完全匹配到記憶體數據緩衝區中的一段數據
        if (k == SignatureCodeLength)
        {
            // 將該段數據的起始地址保存到結果數組中
            ResultArray.push_back(StartAddress + i);
        }

        // 如果已經處理到緩衝區的末尾
        if ((i + SignatureCodeLength) >= size)
        {
            return;
        }

        int num = Next[MemoryData[i + SignatureCodeLength]];

        // 如果特征碼中有問號，從問號處開始匹配
        if (num == -1)
        {
            // 如果特征碼有問號，就從問號處開始匹配，如果沒有就 i += -1
            i += (SignatureCodeLength - Next[256]);
        }
        else
        {
            // 否則從匹配失敗的位置開始
            i += (SignatureCodeLength - num);
        }
    }
}

6.2.3 搜索整塊記憶體區域

SearchMemory函數，該函數用於在指定進程的記憶體空間中搜索給定特征碼的記憶體塊，並把搜索到的記憶體地址存入結果數組中。函數為一層迴圈枚舉給定的記憶體塊，內部則調用SearchMemoryBlock函數進行記憶體塊搜索。其中，參數hProcess為指向要搜索記憶體塊所在進程的句柄，SignatureCode為給定特征碼的字元串指針，StartAddress為搜索的起始地址，EndAddress為搜索的結束地址，InitSize為搜索結果數組初始空間大小，ResultArray為存儲搜索結果的數組引用。

該函數首先通過調用VirtualQueryEx函數獲取可讀可寫和可讀可寫可執行的記憶體塊信息，並遍歷每個記憶體塊，對記憶體塊進行搜索。之所以不直接搜索整個記憶體區域，是因為那樣可以減少非必要的搜索，提高效率。

記憶體塊的搜索通過調用SearchMemoryBlock函數實現。搜索採用了KMP演算法，先通過GetNextArray函數和GetSignatureCodeArray函數將特征碼轉換為對應的變數，再對每個記憶體塊逐個匹配，在匹配過程中若找到與特征碼中的位元組碼不匹配的位元組，就根據Next數組記錄的回溯位置從失配的位置開始重新匹配，以降低匹配的時間複雜度。在記憶體塊搜索過程中，若匹配成功，則將特征碼匹配的起始地址存入結果數組中，最終函數返回結果數組大小。

// 實現搜索整個程式
int SearchMemory(HANDLE hProcess, char* SignatureCode, unsigned __int64 StartAddress, unsigned __int64 EndAddress, int InitSize, vector<unsigned __int64>& ResultArray)
{
    int i = 0;
    unsigned long BlockSize;
    MEMORY_BASIC_INFORMATION mbi;

    WORD SignatureCodeLength = strlen(SignatureCode) / 3 + 1;
    WORD* SignatureCodeArray = new WORD[SignatureCodeLength];

    // 實現特征碼字元串與數組轉換
    GetSignatureCodeArray(SignatureCode, SignatureCodeArray);
    GetNextArray(Next, SignatureCodeArray, SignatureCodeLength);

    // 初始化結果數組
    ResultArray.clear();
    ResultArray.reserve(InitSize);

    // 查詢記憶體屬性並迴圈
    while (VirtualQueryEx(hProcess, (LPCVOID)StartAddress, &mbi, sizeof(mbi)) != 0)
    {
        // 判斷並獲取具有PAGE_READWRITE讀寫，或者PAGE_EXECUTE_READWRITE讀寫執行許可權的記憶體
        if (mbi.Protect == PAGE_READWRITE || mbi.Protect == PAGE_EXECUTE_READWRITE)
        {
            i = 0;

            // 得到當前塊長度
            BlockSize = mbi.RegionSize;
            
            // 搜索這塊記憶體
            while (BlockSize >= BLOCKMAXSIZE)
            {
                // 調用記憶體塊搜索功能依次搜索記憶體
                SearchMemoryBlock(hProcess, SignatureCodeArray, SignatureCodeLength, StartAddress + (BLOCKMAXSIZE * i), BLOCKMAXSIZE, ResultArray);
                BlockSize -= BLOCKMAXSIZE;
                i++;
            }
            SearchMemoryBlock(hProcess, SignatureCodeArray, SignatureCodeLength, StartAddress + (BLOCKMAXSIZE * i), BlockSize, ResultArray);
        }

        // 開始地址增加下一塊長度繼續搜索
        StartAddress += mbi.RegionSize;
        if (EndAddress != 0 && StartAddress > EndAddress)
        {
            return ResultArray.size();
        }
    }

    // 釋放特征碼數組並返回搜索計數器
    free(SignatureCodeArray);
    return ResultArray.size();
}

將上述代碼理解後讀者可以自行使用

int main(int argc, char *argv[])
{
    // 通過進程名獲取進程PID號
    DWORD Pid = GetPidByName("PlantsVsZombies.exe");
    printf("[*] 獲取進程PID = %d \n", Pid);

    // 初始化MemoryData大小
    MemoryData = new BYTE[BLOCKMAXSIZE];

    // 存儲搜索返回值
    vector<unsigned __int64> ResultArray;

    // 通過進程ID獲取進程句柄
    HANDLE hProcess = OpenProcess(PROCESS_ALL_ACCESS, false, Pid);

    // 開始搜索
    // 搜索特征碼 FF 25 ?? 從0x0000000到0xFFFFFFF 初始長度為3 返回值放入ResultArray
    SearchMemory(hProcess, "FF 25 ??", 0x0000000, 0xFFFFFFF, 3, ResultArray);

    // 輸出結果
    for (vector<unsigned __int64>::iterator it = ResultArray.begin(); it != ResultArray.end(); it++)
    {
        printf("0x%08X \n", *it);
    }

    system("pause");
    return 0;
}

編譯並運行上述程式片段，則會枚舉hProcess進程內特征碼時FF 25 ??的片段，枚舉位置為0x0000000-0xFFFFFFF枚舉長度為3個特征，最終將枚舉結果輸出到ResultArray數組內，輸出效果圖如下所示；

本文作者： 王瑞
本文鏈接： https://www.lyshark.com/post/ae682eb.html
版權聲明： 本博客所有文章除特別聲明外，均採用 BY-NC-SA 許可協議。轉載請註明出處！