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
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類