6.2 Sunday搜索记忆特性

Sunday算法是由Daniel M.Sunday于1990年开发的字符串搜索算法。该算法用于查找较长字符串中的子字符串。地点。该算法的工作原理是从模式的最左边位置开始，将要搜索的模式的字符与要搜索的字符串的字符进行比较。如果发现不匹配，算法会将图案 向右滑动 一定数量的位置。该数字由当前文本中当前模式位置的最右边的字符确定。该算法被认为比暴力方法更有效。

6.2.1 字符串与特征码转换

GetSignatureCodeArray函数，用于将给定的十六进制字符串表示的字节码签名转换为十进制数，并存储在整数数组中以供后续搜索。同时，特征代码中的未知标记符号？将被替换为256，以方便后续搜索匹配特征代码。

其中，参数SignatureCode是一串描述要查找的字节码特征码的十六进制字符串，参数BytesetSequence是一个用于存储的整数数组。将十六进制数转换为十进制数的结果。该函数首先计算给定的十六进制字符串中包含的字节码数。因为每个字节对应两个十六进制字符，加上每两个字符之间的空格，所以需要将十进制字符串长度除以三，再加一。

接下来，该函数逐字符读取特征代码字符串中的每个十六进制数字。如果是有效的十六进制数，则将其转换为十进制数并存储在 BytesetSequence 数组 中。如果遇到未知标记符号 ?，则该位置的值由 BytesetSequence 数组中的 256 表示。最后返回签名数组中字节码的数量。

//定义全局变量
#define BLOCKMAXSIZE 409600 // 每次读取的内存最大大小
字节*内存数据； // 每次读取这里读取的内存
简短 下一个[260]； // 搜索下一个内存区域

//将传入的SignatureCode特征码字符串转换为BytesetSequence特征码字节集WORD GetSignatureCodeArray(char* SignatureCode, WORD* BytesetSequence)
{
    int len = 0;

    // 用于存储特征码数组的长度
    WORD 签名代码长度 = strlen(签名代码) / 3 + 1;

    //将十六进制特征码转换为十进制
    // 依次遍历SignatureCode中的每个十六进制数
    for (int i = 0; i < strlen(SignatureCode);)
    {
        字符数[2]；

        // 分别取出第一个和第二个十六进制字符
        num[0] = 签名代码[i++];
        num[1] = 签名代码[i++];
        我++;

        // 如果两个字符都是有效的十六进制数字，则将它们转换为十进制并将它们存储在 BytesetSequence 中
        if (num[0] != '?' && num[1] != '?')
        {
            整数总和=0；
            字a[2]；

            // 将两个十六进制字符分别转换为十进制数字
            for (int i = 0; i < 2; i++)
            {
                // 如果它是一个数字
                if (num[i] >= '0' && num[i] <= '9')
                {
                    a[i] = num[i] - '0';
                }
                // 如果是小写字母
                否则 if (num[i] >= 'a' && num[i] <= 'z')
                {a[i] = num[i] - 87；
                }
                // 如果是大写字母
                否则 if (num[i] >= 'A' && num[i] <= 'Z')
                {
                    a[i] = num[i] - 55；
                }
            }

            // 计算两个十六进制数转换后的十进制数，存入BytesetSequence数组中
            总和 = a[0] * 16 + a[1];
            BytesetSequence[len++] = 总和；
        }
        别的
        {
            字节集序列[len++] = 256;
        }
    }
    返回签名代码长度；
}

6.2.2 搜索存储区功能

SearchMemoryBlock函数，该函数用于在指定进程的某个内存块中搜索给定的字节码签名。如果查找成功，则将匹配的地址存入结果数组中。其中，参数hProcess是指向要查找内存块的进程的句柄，SignatureCode是给定签名的数组指针，SignatureCodeLength 是签名长度，StartAddress 是搜索的起始地址，size 是搜索内存的大小，ResultArray 是用于存储搜索的数组引用结果。

通过调用ReadProcessMemory函数读取进程内存中指定地址和大小的数据，将读取到的数据存储到变量MemoryData中，然后匹配读取到的数据，找到签名。如果匹配成功，则将签名匹配的起始地址存储到结果数组中。匹配时使用KMP算法。如果发现与特征码中的字节码不匹配的字节，则根据Next数组中记录的回溯位置，从不匹配的位置重新开始匹配，以降低匹配的时间复杂度，提高搜索效率。代码中，如果特征代码中有问号，则匹配位置会从问号开始重新匹配。如果没有问号，则按照Next数组回溯继续匹配。

//获取GetNextArray数组
void GetNextArray(短*下一个, WORD* SignatureCode, WORD SignatureCodeLength)
{
    //签名字节集每个字节的范围在0-255（0-FF）之间
    // 256用来表示问号，260用来防止越界。
    for (int i = 0; i < 260; i++)
    {
        下一个[i] = -1;
    }
    for (int i = 0; i < SignatureCodeLength; i++)
    {
        下一个[签名代码[i]] = i;
    }
}

//在内存区域中搜索特征
void SearchMemoryBlock(HANDLE hProcess, WORD* SignatureCode, WORD SignatureCodeLength, unsigned __int64 StartAddress, unsigned long size, vector& ResultArray)
{
    //将指定进程的内存数据读入MemoryData缓冲区
    if (!ReadProcessMemory(hProcess, (LPCVOID)StartAddress, MemoryData, 大小, NULL))
    {
        返回;
    }// 循环遍历内存数据缓冲区
    for (int i = 0, j, k; i < 大小;)
    {
        j = 我； k = 0；

        // 将内存数据缓冲区中的字节和签名中的字节一一比较
        for (; k < SignatureCodeLength && j < size && (SignatureCode[k] == MemoryData[j] || SignatureCode[k] == 256); k++, j++);

        // 如果签名与内存数据缓冲区中的某条数据完全匹配
        if (k == 签名代码长度)
        {
            //将该段数据的起始地址保存到结果数组中
            ResultArray.push_back(StartAddress + i);
        }

        // 如果缓冲区末尾已被处理
        if ((i + SignatureCodeLength) >= 大小)
        {
            返回;
        }

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

        // 如果特征码中有问号，则从问号开始匹配
        如果（数字==-1）
        {
            // 如果特征码有问号，则从问号开始匹配，如果没有，则使用i += -1
            i += (SignatureCodeLength - 下一个[256]);
        }
        别的
        {
            // 否则，从匹配失败的位置开始
            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，无符号__int64 StartAddress，无符号__int64 EndAddress，int InitSize，向量＆ResultArray）
{
    整数 i = 0;
    无符号长块大小；
    MEMORY_BASIC_INFORMATION mbi；WORD 签名代码长度 = strlen(签名代码) / 3 + 1;
    WORD* SignatureCodeArray = 新 WORD[SignatureCodeLength];

    // 实现特征码字符串与数组的转换
    获取SignatureCodeArray(SignatureCode, SignatureCodeArray);
    GetNextArray(下一个, 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)
        {
            我 = 0;

            // 获取当前块长度
            块大小 = mbi.RegionSize;
            
            // 搜索这块内存
            while (块大小 >= BLOCKMAXSIZE)
            {
                // 调用内存块查找函数按顺序查找内存SearchMemoryBlock(hProcess, SignatureCodeArray, SignatureCodeLength, StartAddress + (BLOCKMAXSIZE * i), BLOCKMAXSIZE, ResultArray);
                块大小 -= BLOCKMAXSIZE;
                我++;
            }
            SearchMemoryBlock(hProcess, SignatureCodeArray, SignatureCodeLength, StartAddress + (BLOCKMAXSIZE * i), BlockSize, ResultArray);
        }

        //将起始地址增加到下一个块的长度并继续查找
        起始地址 += mbi.RegionSize;
        if (结束地址！= 0 && 开始地址 > 结束地址)
        {
            返回 ResultArray.size();
        }
    }

    // 释放签名数组并返回搜索计数器
    自由（SignatureCodeArray）；
    返回 ResultArray.size();
}

理解上面的代码后读者就可以自己使用了

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

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

    //存储搜索返回值
    矢量结果数组；// 通过进程ID获取进程句柄
    HANDLE hProcess = OpenProcess(PROCESS_ALL_ACCESS, false, Pid);

    // 开始寻找
    //搜索特征码FF 25??从 0x0000000 到 0xFFFFFFF。初始长度为3。返回值放入ResultArray中。
    SearchMemory(hProcess, "FF 25 ??", 0x0000000, 0xFFFFFFF, 3, ResultArray);

    //输出结果
    for (向量::迭代器 it = ResultArray.begin(); it != ResultArray.end(); it++)
    {
        printf("0x%08X \n", *it);
    }

    系统（“暂停”）；
    返回0；
}

编译并运行上述程序片段，会枚举进程内特征码为FF 25 ??时hProcess的片段，枚举位置为0x0000000-0xFFFFFFFF ​​枚举长度为3个特征，枚举结果最终输出到ResultArray数组中。输出效果图如下图；