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数组内，输出效果图如下所示；