windows 如何实现快速指针扫描?

tyu7yeag  于 2023-03-04  发布在  Windows
关注(0)|答案(1)|浏览(180)

我正在尝试构建一个实用程序,在程序更新后自动查找指针。我遇到的问题是,实际搜索特定的4/8字节值似乎很快,但不够快,无法实现扫描指针路径。
下面是我目前从VirtualQueryEx搜索内存区域的代码

public List<MemoryScanResult> Search(MemoryRegion region, byte[] targetValue)
{
    var results = new List<MemoryScanResult>();
    var buffer = region.Cache;
    
    switch (targetValue.Length)
    {
        case 8:
            CheckBufferUnsignedLong(BitConverter.ToUInt64(targetValue));
            break;
        case 4:
            CheckBufferUnsignedInt(BitConverter.ToUInt32(targetValue));
            break;
        default:
            throw new NotSupportedException();

    }
    
    void CheckBufferUnsignedInt(uint value)
    {
        unsafe
        {
            fixed (byte* pBuffer = buffer)
            {
                var itemSize = buffer!.Length / 4;
                var values = (uint*)pBuffer;
                for (var i = 0; i < itemSize; i++)
                {
                    if (value != values[i])
                        continue;

                    var foundResult = new MemoryScanResult
                                      {
                                          Address = region.BaseAddress + (i * itemSize),
                                          FoundAtBase = region.AllocationBase == _applicationMemory.Address
                                      };

                    results!.Add(foundResult);
                }
            }
        }
    }

    void CheckBufferUnsignedLong(ulong value)
    {
        unsafe
        {
            fixed (byte* pBuffer = buffer)
            {
                var itemSize = buffer!.Length / 8;
                var values = (ulong*)pBuffer;
                for (var i = 0; i < itemSize; i++)
                {
                    if (value != values[i])
                        continue;

                    var foundResult = new MemoryScanResult
                                      {
                                          Address = region.BaseAddress + (i * itemSize),
                                          FoundAtBase = region.AllocationBase == _applicationMemory.Address
                                      };

                    results!.Add(foundResult);
                }
            }
        }
    }

    return results;
}

该应用程序具有1.9GB的可读/可写存储器,分为3个部分,500个非空区域。并行运行上述函数。ForEach和4个工作线程在500 ms内读取所有1.9GB,并返回正确的结果数。这一切看起来都很好,直到我开始查看指针扫描并意识到这是4+如果我在目标值地址之前0x 1000开始搜索,可能需要30分钟才能找到第一个结构体指针。
我所知道的唯一一款具有这种功能/速度和源代码的软件是Cheat Engine。我试着查看源代码,但我不知道它是否做了一些特殊的事情,或者我只是达到了在. NET中可以实现的上限。
有什么技巧我错过了吗?这似乎是不真实的,我认为作弊引擎能够扫描,并找到1830万路径之前,我甚至找到了我的值非常第一指针。
编辑:还有一件事是Cheat Engine也不需要缓存整个堆。即使在指针扫描期间,它也不会接近我达到当前时间所需的内存使用率,所以我认为它是按需阅读区域。如果我这样做,我的搜索时间将变为900 ms。
编辑2:在发行版中运行(就像我应该做的那样),使用缓存缓冲区将我的时间降低到160- 200 ms。这使得我目前的基准测试在最坏的情况下需要1.7分钟,4个工作者找到1个指针。如果仅仅向集合中添加17个结果就增加了50 ms,我开始考虑我需要从.NET中转移出来,并为此做一个.NET Package 器。

kwvwclae

kwvwclae1#

自我回答是因为经过长时间的战斗试图建立扫描仪,我终于有了顿悟。
我在构建扫描仪时找到的每一条信息都是最基本的例子,通常类似于以下内容:“从你的目标地址X开始,一直走到最大N偏移量,然后递归检查指针,直到你到达一个静态/基址”而且在大多数情况下,这是正确的,但是一旦你开始实际构建扫描器,这是一个巨大的陷阱。使用任何简单的示例代码,如果实现得很完美,将产生非常小的结果,或者是一个非常长的过程,你永远不会让它完成,因为你知道它应该更快,而且/要么就是内存不足。
这是一个逐步模拟的例子,但主要的速度因素是:

  • 读取所有内存来创建一个巨大的指针列表{.Address, .Value}ReadProcessMemory太慢了,除此之外无法用于其他任何操作。
  • 所有集合应按地址排序。
  • 尽可能多地使用BinarySearch。甚至可以为指针或区域创建多个列表。一个按地址排序,另一个按值排序。我们讨论的是潜在的数百万个项目和大量的循环。你需要快速轻松地定位你的项目。到目前为止,这个过程对我来说和Cheat Engine一样快,有时甚至更快,但Cheat Engine有时可能给予我3,000,000个指针,我有180,000个,但到目前为止还不需要丢失的2,820,000个路径。为了比较。我运行8个线程,目标应用程序消耗2.5GB的内存,该过程大约在10-15秒内完成。24个线程的作弊引擎需要12秒。你可能只需要几秒。我武断地选择了8和作弊引擎去了物理核心在我的CPU为它的工人计数。

步骤1 -内存区域和模块链接

  • 获取与进程关联的所有内存区域的列表。最好按BaseAddress排序
  • 获取与进程一起加载的所有模块的列表。
  • 运行区域并使用其基址将模块与区域链接。
  • 根据AllocationBase将您的区域链接在一起。现在您将知道哪些区域属于哪个exe/dll。

步骤2 -指针缓存

这是两个主要速度区域中的第一个,目标是在此之后不再调用ReadProcessMemory,它很慢,可能有数千个内存区域,并且缓存它不会消耗太多内存。

  • 创建一个简单的Pointer结构体,其中只包含它所指向的AddressValue
  • 遍历所有内存区域并将内存读入缓冲区。以48的对齐方式遍历。8速度较快,但最终可能无法给予可用的结果。
  • 在这个循环中,检查Value是否确实指向了你的内存区域,如果是的话,把你的新指针保存到缓存中。

此时,您应该有一个庞大的指针列表。从现在开始,这就是扫描将扫描的对象。

步骤3 -创建指针级别列表

这是拥有一个可行的指针扫描器的实际步骤和技巧。

  • 创建一个PointerList类,用于保存指针的LevelPointer的HashSet(或任何其他唯一/排序容器)。
  • 根据最大指针深度和相应的级别创建一个PointerList数组。此时我还链接了我的PointerList,使NextPrevious链接到其他列表。例如,级别2链接到上一级别1,链接到下一级别3
  • 现在列表已经准备好了,我们可以回到一些旧的基础知识上,开始遍历指针。但是!有一个主要的区别,我们不是每次迭代遍历一个完整的指针。我们一次遍历一个级别的所有潜在指针。这就是为什么你要使用一个唯一的/排序的容器,比如HashSet(假设你把哈希值设为你的地址的哈希值)。

第4步-最终查找指针

对地址/值/指针的所有检查都基于步骤2中的指针的巨大集合。

  • 0级--从你的目标地址开始,找到所有以它为值的指针,并将它们添加到你的0级列表中。

  • 0级--用你的alignment减去你的目标地址,并检查该地址是否有指向它的指针。如果它确实添加到你的0级指针列表。不是你的结果列表!冲洗并重复,直到你达到一个最大偏移量或节点深度。例如偏移量0x 1000或最多只取3或5个指针。由你决定并需要测试。注意:很有可能在你的0级列表步骤中已经有了结果。检查你正在添加的指针的地址,并确定它是一个结果指针还是仅仅是一个下一级的指针。

  • 级别1----你在你的previous列表中有你的指针的初始种子。做和级别0完全一样的事情,检查你的地址,看看你认为是什么结果或者一个工作在下一个级别。例如,只有当指针的地址在主模块的内存区域时才接受指针结果。对所有级别重复此操作。记住诀窍是在下一关之前完成一关。

  • 例如,您的列表可能会在每个级别上看起来越来越大。20分,第一关:350分,第二级:一千个指针。

第5步-构建结果

此时,如果使用最大深度5,则应该有5个PoinerList相互指向,并且在某些列表中应该有一些结果。

  • 现在循环遍历每个列表和它们的结果。保持它的顺序,它应该会先给予你最短的路径。
  • 对于每一个指针结果,你基本上要做的步骤4,但反过来.而不是减去偏移量,增加偏移量,直到你的最大允许偏移量,即0x 1000或更小,如果你遇到你的目标地址,你的整个扫描一直在寻找.
  • 每一个结果指针都应该指向一个或多个路径。每级的偏移量越大,你应该为一个结果找到的指针路径就越多。
  • 这是你可以最终开始使用递归的步骤,因为你不应该递归超过你的实际层数,在这一点上,你的层的指针是高度过滤和有针对性的,你不会看到垃圾值。
  • 运行ReadProcessMemory并验证其工作。根据需要保存/使用。

下面是扫描仪本身。不是最干净的,需要一些调整,但这只是作为一个例子。缺少的类应该很容易能够推断出以上的指示和上下文中使用它们。

public class PointerScanner
{
    readonly PointerScanController _controller;

    public PointerScanController Controller => _controller;

    public PointerScanner(ApplicationMemory applicationMemory, PointerScanSettings settings)
    {
        _controller = new PointerScanController(settings, applicationMemory);
    }

    public async Task ScanAsync(nint targetAddress)
    {
        var pointerLists = new List<PointerList>();
        for (var i = 0; i < _controller.Settings.MaxDepth + 1; i++)
        {
            var newList = new PointerList { Level = i };
            pointerLists.Add(newList);
            if (i > 0)
            {
                newList.Previous = pointerLists[i - 1];
                pointerLists[i - 1].Next = newList;
            }
        }

        var settings = _controller.Settings;

        for (var i = 0; i < pointerLists.Count; i++)
        {
            var currentList = pointerLists[i];
            var previousList = i > 0 ? pointerLists[i - 1] : null;
            if (previousList == null)
            {
                // 1) Start walking up the struct
                for (var address = targetAddress; address >= targetAddress - settings.MaxOffset; address -= settings.Alignment)
                {
                    // 2) Find all pointers that point to this address
                    var parents = _controller.CachedValues.BinarySearchFindAll(new Pointer { Value = address }, new PointerValueComparer());
                    if (parents == null)
                        continue;

                    // 3) Add all pointers to to the list;
                    foreach (var parent in parents)
                    {
                        var block = _controller.GetBlockIndexFromAddress(parent);
                        if (block >= 0 && _controller.MemoryRegions[block].Module != null)
                        {
                            currentList.Results.Add(parent, (int)(targetAddress - address));
                        }
                        else
                        {
                            currentList.Pointers.Add(parent);
                        }
                    }
                }
            }
            else
            {
                // 1) Run through all potential pointers in the previous level.
                await Parallel
                    .ForEachAsync(previousList.Pointers,
                                  new ParallelOptions { MaxDegreeOfParallelism = 8 },
                                  (pointer, token) =>
                                  {
                                      var nodeDepth = 0;
                                      // 2) Start walking up the struct
                                      for (var address = pointer.Address;
                                           address >= pointer.Address - settings.MaxOffset;
                                           address -= settings.Alignment)
                                      {
                                          // 3) Find all pointers that point to this address
                                          var parents = _controller.CachedValues.BinarySearchFindAll(new Pointer { Value = address },
                                                                                                     new PointerValueComparer());
                                          if (parents == null)
                                              continue;

                                          nodeDepth++;

                                          // 4) Add all pointers to to the list;
                                          foreach (var parent in parents)
                                          {
                                              var block = _controller.GetBlockIndexFromAddress(parent, true);
                                              var skipAddToPointer = false;
                                              if (block >= 0 && block < _controller.MemoryRegions.Count)
                                              {
                                                  var module = _controller.MemoryRegions[block].Module;
                                                  if (module != null && module.BaseAddress < parent.Address)
                                                  {
                                                      //This lives inside a module, however, there could be better modules pointing to it.
                                                      //TODO: Accept a list of modules that should only count towards the result
                                                      lock (currentList.Results)
                                                      {
                                                          if (!currentList.Results.ContainsKey(parent))
                                                          {
                                                              skipAddToPointer = true;
                                                              currentList.Results.Add(parent, (int)(pointer.Address - address));
                                                          }
                                                      }
                                                  }
                                              }

                                              if (skipAddToPointer || currentList.Next == null)
                                                  continue;

                                              lock (currentList.Pointers)
                                              {
                                                  if (!currentList.PointerAlreadyExists(parent))
                                                  {
                                                      currentList.Pointers.Add(parent);
                                                  }
                                              }
                                          }

                                          if (nodeDepth > settings.MaxOffsetNodes)
                                              break;
                                      }

                                      return default;
                                  });
            }

            Console.WriteLine($"Pointers Level {i} -- {pointerLists[i].Pointers.Count:#,###} pointers.");
        }

        foreach (var list in pointerLists)
            list.FinalizeToList();

        foreach (var l in pointerLists)
        {
            foreach (var result in l.Results)
            {
                var regionIx = _controller.GetBlockIndexFromAddress(result.Key.Address, false);
                var module = _controller.MemoryRegions[regionIx].Module;
                FindResultPointer(targetAddress, 0, result.Key, result.Key, l.Previous, new List<int> { (int)(result.Key.Address - module!.BaseAddress) });
            }
        }

        var r = _controller.Results;
        var maxOffset = r.Max(x => x.Offsets.Length);

        var sorted = r.OrderBy(x => true);
        for (var i = maxOffset-1; i >= 0; i--)
        {
            var offsetIndex = i;
            
            //This is really hacky, but I want the main 1st set of offsets to be sorted and make sure 
            //the main big offset is grouped together as much as possible.
            if (offsetIndex == 1)
            {
                offsetIndex = 0;
            }
            else if (offsetIndex == 0)
            {
                offsetIndex = 1;
            }
            sorted = sorted.ThenBy(x => x.Offsets.Length > offsetIndex ? x.Offsets[offsetIndex] : -1);
        }

        _controller.Results = sorted.ToList();
    }

    bool FindResultPointer(nint targetAddress, int currentLevel, Pointer mainPointer, Pointer pointer, PointerList? nextLevel, List<int> currentOffsets)
    {
        if (nextLevel == null)
        {
            //The first pointer list is special because any results in it are direct and there's no previous list to build from.
            //Need to manually work it and add its results.
            if (currentLevel == 0 && (targetAddress - pointer.Value) <= _controller.Settings.MaxOffset)
            {
                currentOffsets.Add((int)(targetAddress - pointer.Value));
                var regionIx = _controller.GetBlockIndexFromAddress(mainPointer.Address, false);
                _controller.Results.Add(new PointerScanResult
                                        {
                                            Origin = mainPointer,
                                            Module = _controller.MemoryRegions[regionIx].Module!,
                                            Offsets = currentOffsets.Select(x => x).ToArray()
                                        });
                return true;
            }

            return false;
        }

        //1) Find the child pointer
        var baseChildIndex = nextLevel.PointersList.BinarySearch(new Pointer { Address = pointer.Value });
        if (baseChildIndex < 0)
            baseChildIndex = (~baseChildIndex);

        bool hadResult = false;

        //2) Loop through all potential children/offsets
        var depth = 0;
        for (var i = baseChildIndex; i < nextLevel.PointersList.Count; i++)
        {
            var child = nextLevel.PointersList[i];
            if (child.Address > pointer.Value + _controller.Settings.MaxOffset)
                break;

            currentOffsets.Add((int)(child.Address - pointer.Value));

            if (!FindResultPointer(targetAddress, currentLevel + 1, mainPointer, child, nextLevel.Previous, currentOffsets))
            {
                if (targetAddress - child.Value <= _controller.Settings.MaxOffset)
                {
                    hadResult = true;

                    currentOffsets.Add((int)(targetAddress - child.Value));
                    var regionIx = _controller.GetBlockIndexFromAddress(mainPointer.Address, true);

                    _controller.Results.Add(new PointerScanResult
                                            {
                                                Origin = mainPointer,
                                                Module = _controller.MemoryRegions[regionIx].Module!,
                                                Offsets = currentOffsets.Select(x => x).ToArray()
                                            });
                    currentOffsets.RemoveAt(currentOffsets.Count - 1);
                }
            }
            else
            {
                hadResult = true;
            }

            currentOffsets.RemoveAt(currentOffsets.Count - 1);
        }

        return hadResult;
    }
}

相关问题