6.1 KMP演算法搜索機器碼

来源:https://www.cnblogs.com/LyShark/archive/2023/09/20/17718405.html
-Advertisement-
Play Games

KMP演算法是一種高效的字元串匹配演算法，它的核心思想是利用已經匹配成功的子串首碼的信息，避免重覆匹配，從而達到提高匹配效率的目的。KMP演算法的核心是構建模式串的首碼數組Next，Next數組的意義是：當模式串中的某個字元與主串中的某個字元失配時，Next數組記錄了模式串中應該回退到哪個位置，以便繼續匹... ...


KMP演算法是一種高效的字元串匹配演算法，它的核心思想是利用已經匹配成功的子串首碼的信息，避免重覆匹配，從而達到提高匹配效率的目的。KMP演算法的核心是構建模式串的首碼數組Next，Next數組的意義是：當模式串中的某個字元與主串中的某個字元失配時，Next數組記錄了模式串中應該回退到哪個位置，以便繼續匹配。Next數組的計算方法是找出模式串每一個首碼中最長的相等首碼和尾碼，並記錄下來它們的長度，作為Next數組中的對應值。

在字元串匹配時，KMP演算法從主串和模式串的開頭開始逐個字元比較，若發現匹配失敗，則根據Next數組中的值進行回退，從失配位置的下一位重新開始比較。這樣回退的次數比暴力匹配方式要少得多，因此匹配效率得到了大幅提升。

6.1.1 遍歷輸出進程記憶體

首先需要實現取進程PID的功能，當用戶傳入一個進程名稱時則輸出該進程的PID號，通過封裝GetPidByName函數，該函數用於根據指定的進程名稱，獲取該進程的進程PID，以便於後續針對進程進行操作。函數參數name為指定的進程名稱字元串。該函數通過調用CreateToolhelp32Snapshot函數創建一個系統快照，返回系統中所有進程的快照句柄。然後使用該快照句柄，通過進程快照函數Process32First和Process32Next函數逐個對比進程的名稱，找到進程名稱匹配的PID，返回該PID。若無法找到匹配的進程名稱，則返回0。讀者需要註意，當使用進程遍歷功能時通常需要引入<tlhelp32.h>庫作為支持；

// 根據進程名得到進程PID
DWORD GetPidByName(const char* name)
{
    HANDLE snapshot = CreateToolhelp32Snapshot(TH32CS_SNAPPROCESS, 0);
    PROCESSENTRY32 pe32 = { sizeof(PROCESSENTRY32) };
    DWORD pid = 0;

    if (Process32First(snapshot, &pe32))
    {
        do
        {
            if (_stricmp(pe32.szExeFile, name) == 0)
            {
                pid = pe32.th32ProcessID;
                break;
            }
        } while (Process32Next(snapshot, &pe32));
    }
    CloseHandle(snapshot);
    return pid;
}

在開始使用KMP枚舉特征碼之前我們需要實現簡單的記憶體讀寫功能，通過封裝一個MemoryTraversal函數，該函數接收三個參數分別是，進程PID，進程開始記憶體地址，以及進程結束記憶體地址，該函數輸出當前進程記憶體機器碼，每次讀入4096位元組，然後每16個字元換一次行，遍歷記憶體0x00401000 - 0x7FFFFFFF這篇記憶體區域，這段代碼實現如下所示；

// 遍歷並輸出進程記憶體
VOID MemoryTraversal(DWORD PID, const DWORD beginAddr, const DWORD endAddr)
{
    const DWORD pageSize = 4096;

    // 打開並獲取進程句柄
    HANDLE process = ::OpenProcess(PROCESS_ALL_ACCESS, false, PID);

    BOOL _break = FALSE;
    BYTE page[pageSize];
    DWORD tmpAddr = beginAddr;

    // 迴圈枚舉進程
    while (tmpAddr <= endAddr)
    {
        // 每次讀入記憶體
        ReadProcessMemory(process, (LPCVOID)tmpAddr, &page, pageSize, 0);

        // 依次迴圈每一個位元組
        for (int x = 0; x < 4096; x++)
        {
            // 每16個字元換一行
            if (x % 15 != 0)
            {
                DWORD ch = page[x];

                if (ch >= 0 && ch <= 15)
                {
                    printf("0%x ", ch);
                }
                else
                {
                    printf("%x ", ch);
                }
            }
            else
            {
                printf(" | %x \n", tmpAddr+x);
            }
        }
        tmpAddr += pageSize;
    }
}

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

    // 輸出記憶體遍歷0x401000-0x7FFFFFFF
    MemoryTraversal(Pid, 0x401000, 0x7FFFFFFF);

    system("pause");
    return 0;
}

讀者可自行編譯這段代碼片段，並運行特定進程，當程式運行後即可輸出PlantsVsZombies.exe進程內的機器碼，並以16個字元為一個單位進行輸出，其效果圖如下所示；

6.1.2 使用KMP搜索特征碼

為了能讓讀者更好的理解KMP特征碼搜索的實現原理，這裡筆者依然在MemoryTraversal函數基礎之上進行一定的改進在本次改進中，我們增加了memcmp函數，通過使用該函數我們可以很容易的實現對特定記憶體區域的相同比較，讀者在調用ScanMemorySignatureCode函數時需要傳入，開始地址，結束地址，特征碼，以及特征碼長度，當找到特定記憶體後則返回該記憶體的所在位置。

// 記憶體特征碼搜索
ULONG ScanMemorySignatureCode(DWORD Pid, DWORD beginAddr, DWORD endAddr, unsigned char *ShellCode, DWORD ShellCodeLen)
{
    unsigned char *read = new unsigned char[ShellCodeLen];

    // 打開進程
    HANDLE process = OpenProcess(PROCESS_ALL_ACCESS, false, Pid);

    // 開始搜索記憶體特征
    for (int x = 0; x < endAddr; x++)
    {
        DWORD addr = beginAddr + x;

        // 每次讀入ShellCodeLen位元組特征
        ReadProcessMemory(process, (LPVOID)addr, read, ShellCodeLen, 0);
        int a = memcmp(read, ShellCode, ShellCodeLen);

        if (a == 0)
        {
            printf("%x :", addr);
            for (int y = 0; y < ShellCodeLen; y++)
            {
                printf("%02x ", read[y]);
            }
            printf(" \n");
            return addr;
        }
    }
    return 0;
}

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

    // 開始搜索特征碼
    unsigned char ScanOpCode[3] = { 0x56, 0x57, 0x33 };

    // 依次傳入開始地址，結束地址，特征碼，以及特征碼長度
    ULONG Address = ScanMemorySignatureCode(Pid, 0x401000, 0x7FFFFFFF, ScanOpCode, 3);

    printf("[*] 找到記憶體地址 = 0x%x \n", Address);

    system("pause");
    return 0;
}

上述程式運行後，將枚舉當前進程0x401000-0x7FFFFFFF區域中特征碼為0x56, 0x57, 0x33的記憶體地址，枚舉到以後則輸出該記憶體地址的位置，輸出效果圖如下圖所示；

有了上面的模板我們只需要在此基礎之上增加KMP枚舉方法即可實現，如下代碼則是替換具有KMP功能的搜索模式，在代碼中可看出我們僅僅只是將ScanMemorySignatureCode函數內部的memcmp函數替換為了KMPSearchString函數，其他位置並沒有任何變化，此處主要增加的函數有GetNextval以及KMPSearchString，這兩個函數的核心思想是利用KMP演算法，在主字元串中尋找子字元串時，遇到匹配失敗的字元時，能夠跳過一些已經比較過的字元，重覆利用部分匹配的結果，提高字元串匹配的效率。將子串的每個字元失配時應該跳轉的位置通過GetNextval函數計算得出，然後在KMPSearchString函數中通過這個數組進行跳轉和匹配。該演算法的時間複雜度為O(m+n)，其中m和n分別表示主串和模式串的長度。

#include <iostream>
#include <windows.h>
#include <tlhelp32.h>

using namespace std;

// 根據進程名得到進程PID
DWORD GetPidByName(const char* name)
{
    HANDLE snapshot = CreateToolhelp32Snapshot(TH32CS_SNAPPROCESS, 0);
    PROCESSENTRY32 pe32 = { sizeof(PROCESSENTRY32) };
    DWORD pid = 0;

    if (Process32First(snapshot, &pe32))
    {
        do
        {
            if (_stricmp(pe32.szExeFile, name) == 0)
            {
                pid = pe32.th32ProcessID;
                break;
            }
        } while (Process32Next(snapshot, &pe32));
    }
    CloseHandle(snapshot);
    return pid;
}

/*
* P 為模式串，下標從 0 開始。
* nextval 數組是模式串 SubString 中每個字元失配時應該回溯的位置。
*/
void GetNextval(string SubString, int nextval[])
{
    int SubStringLen = SubString.size(); // 計算模式串的長度
    int i = 0;                           // 子串的指針
    int j = -1;                          // 首碼的指針
    nextval[0] = -1;                     // 初始化 nextval 數組，將第一個值設為 -1

    while (i < SubStringLen - 1)
    {
        if (j == -1 || SubString[i] == SubString[j]) // 如果子串和首碼相等，或 j==-1
        {
            i++; j++;                                // 子串指針和首碼指針分別加一
            if (SubString[i] != SubString[j])        // 如果下一個字元不相等
            {
                nextval[i] = j;                      // 將首碼指針 j 的值賦給 nextval 數組中的當前位置 i
            }
            else                                     // 如果下一個字元相等
            {
                nextval[i] = nextval[j];             // 已經有 nextval[j]，所以將它賦給 nextval[i]
            }
        }
        else                                        // 如果子串和首碼不相等
        {
            j = nextval[j];                        // 更新首碼指針 j 的值，指向 nextval[j]
        }
    }
}

/* 在 MainString 中找到 SubString 第一次出現的位置 下標從0開始*/
int KMPSearchString(string MainString, string SubString, int next[])
{
    GetNextval(SubString, next);

    int MainStringIndex = 0;                 // 存儲主字元串下標
    int SubStringIndex = 0;                  // 存儲子字元串下標
    int MainStringLen = MainString.size();   // 主字元串大小
    int SubStringLen = SubString.size();     // 子字元串大小

    // 迴圈遍歷字元串,因為末尾 '\0' 的存在，所以不會越界
    while (MainStringIndex < MainStringLen && SubStringIndex < SubStringLen)
    {
        // MainString 的第一個字元不匹配或 MainString[] == SubString[]
        if (SubStringIndex == -1 || MainString[MainStringIndex] == SubString[SubStringIndex])
        {
            MainStringIndex++; SubStringIndex++;
        }
        else   // 當字元串匹配失敗則跳轉
        {
            SubStringIndex = next[SubStringIndex];
        }
    }
    // 最後匹配成功直接返回位置
    if (SubStringIndex == SubStringLen)
    {
        return MainStringIndex - SubStringIndex;
    }
    return -1;
}

// 記憶體特征碼搜索
ULONG ScanMemorySignatureCode(DWORD Pid, DWORD beginAddr, DWORD endAddr, char *ShellCode, DWORD ShellCodeLen)
{
    char *read = new char[ShellCodeLen];

    // 打開進程
    HANDLE process = OpenProcess(PROCESS_ALL_ACCESS, false, Pid);
    int next[100] = { 0 };

    // 開始搜索記憶體特征
    for (int x = 0; x < endAddr; x++)
    {
        DWORD addr = beginAddr + x;

        // 每次讀入ShellCodeLen位元組特征
        ReadProcessMemory(process, (LPVOID)addr, read, ShellCodeLen, 0);

        // 在Str字元串中找Search子串,找到後返回位置
        int ret = KMPSearchString(read, ShellCode, next);

        if (ret != -1)
        {
            return addr;
        }
    }
    return 0;
}

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

    // 開始搜索特征碼
    char ScanOpCode[3] = { 0x56, 0x57, 0x33 };

    // 依次傳入開始地址，結束地址，特征碼，以及特征碼長度
    ULONG Address = ScanMemorySignatureCode(Pid, 0x401000, 0x7FFFFFFF, ScanOpCode, 3);

    printf("[*] 找到記憶體地址 = 0x%x \n", Address);

    system("pause");
    return 0;
}

編譯並運行上述代碼片段，讀者應該能看出與暴力枚舉並無任何區別，其輸出效果圖如下圖所示；

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

文章作者：lyshark (王瑞)
文章出處：https://www.cnblogs.com/LyShark/p/17718405.html
本博客所有文章除特別聲明外，均採用 BY-NC-SA 許可協議。轉載請註明出處！
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • MySQL高級11-後臺進程
    一、前言 MySQL的服務實現通過後臺多個線程、記憶體池、文件交互來實現對外服務的，不同線程實現不同的資源操作，各個線程相互協助，共同來完成資料庫的服務。MySQL常用的後臺線程概括如下，分為Master Thread，IO Thread，Purge Thread，Page Cleaner Threa ...
  • 分庫分表之拆分鍵設計
    眾所周知，在現實世界中，每一個資源都有其提供能力的最大上限，當單一資源達到最大上限後就得讓多個資源同時提供其能力來滿足使用方的需求。同理，在電腦世界中，單一資料庫資源不能滿足使用需求時，我們也會考慮使用多個資料庫同時提供服務來滿足需求。當使用了多個資料庫來提供服務時，最為關鍵的點是如何讓每一個數據 ...
  • 1-JavaScript 點擊事件
    web前端JavaScript交互 點擊事件 意義： JavaScript中的點擊事件是指當用戶在頁面上點擊某個元素時觸發的事件。這個事件可以用於執行各種操作，如改變元素的樣式、修改頁面內容等。這是Web應用程式中最常用 的交互方式之一，允許用戶與網頁進行交互，提高用戶體驗。 案例： 隨機點名器 知 ...
  • 時間格式化以及指定時區(time&&timezone)
    工作中經常遇到按照指定格式的時間進行展示。可參考以下腳本邏輯滿足需求 Date.prototype.PtTimeByFormat = function (fmt){ var o = { "M+": this.getMonth() + 1, //月份 "d+": this.getDate(), //日 ...
  • 記錄--不要再濫用可選鏈運算符(?.)啦！
    這裡給大家分享我在網上總結出來的一些知識，希望對大家有所幫助 前言 可選鏈運算符(?.)，大家都很熟悉了，直接看個例子： const result = obj?.a?.b?.c?.d 很簡單例子，上面代碼?前面的屬性如果是空值（null或undefined），則result值是undefined，反 ...
  • React hooks 大全詳情
    import React, { useEffect, useState } from 'react'; hook 是react 16.8的新增特性 ，他可以讓你不在編寫class的情況下shiystate以及react的特性 Hooks的出現，首先解決了以下問題： 告別了令人疑惑的生命周期 告別類組 ...
  • 軟體設計模式系列之十——組合模式
    設計模式 學習推薦設計模式目錄：22種設計模式 (refactoringguru.cn) 圖說設計模式 — Graphic Design Patterns (design-patterns.readthedocs.io) UML類圖初見 什麼是統一建模語言（UML）？ (visual-paradig ...
  • HNU個人項目互評
    一、前言 這篇博客是對軟體工程導論的個人項目進行互評，項目要求實現一個簡單的中小學數學卷子自動生成程式。我的搭檔謝先衍同學使用Python完成了項目，而我則是使用java。儘管語言不同增加了一定的閱讀成本，但是接觸到另一種新語言並體會編程者發揮語言特性獨特的心得，確實是拓展了眼界。一個項目，最終歸結 ...
一周排行
    -Advertisement-
    Play Games
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類