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);
}
//