Feature: Generate pointer map (like Cheat Engine)

[cromachina]

To make pointer scanning as efficient and accurate as possible, you should have an option to generate a pointer map to a file, like Cheat Engine does.

The pointer map can contain every address that has "pointer-like" data, that is, it contains a list of addresses and their values, and the values look like it "points" to any active memory region's address range. This map should be very fast to generate (it's maybe like 1 or 2 seconds with Cheat Engine). I'm guessing that the pointer scanner already does this to some degree, but its main problem is that you are forced to scan first instead of caching all pointers for the current snapshot.

Cheat Engine lets you prune a pointer scan by letting you compare multiple snapshot pointer maps (and the target addresses that were saved when the pointer map was generated). It makes the scanning a lot faster; you don't need to have a result limit; and the pointer chain depth can be rather large, like say 6 to 8.

With the app that I care about scanning using Cheat Engine, generating 3 or more pointer maps from different snapshots narrows my "needle" searches down to like 20 pointer chains, and of those, I can usually identify my target static pointer address immediately.

[cromachina]

As for how the pruning process works, I'm actually not quite sure, but my guess is that when a chain is being explored, you could eliminate branches that do not have the same offsets in all compared maps from the respective saved address target associated with each map.

I can test out some ideas and post the results here.

[cromachina]

I thought about it for a bit and came up with the algorithm idea:

Address = int
Value = int
PointerMap = dict[Address, Value]

• An interval data structure library like portions would be useful for querying address ranges (offsets) using open intervals like portions.open(address - offset, address). Used my own "Interval" struct with bisect. Ended up being more useful.
• As a user, generate N pointer maps from all writable regions with an associated target address list[tuple[PointerMap, Address]]
  • That is, find your piece of data and its address, then generate a map (the map and the address found are stored/associated together).
• Path scanning:
  • For the current target addresses, find all addresses that point to it, with an offset range, in its respective map (N sets of found addresses + offsets).
  • For each found address and offset pair, remove this pair from the found set if the offset does not exist in all N sets. This cuts off the search path for this branch immediately, because we only care about matching offsets in all maps (which indicates that we are potentially observing the same fixed structures, except for arrays or maps).
  • Create or extend pointer paths that chain the previous target addresses + offsets to the next ones.
    • If a pointer path is to be extended, all extensions are created as clones, and then the original path that is one shorter is removed, otherwise it is left alone (because it is potentially static).
  • The remaining found addresses become the next current target addresses.
  • Repeat until the target depth is reached, or until no more unvisited addresses exist, or the found addresses list is empty.
• After the search is finished, return the previously assembled pointer paths for the map of the user's target address. Paths that have no addresses pointing to their respective bases can be marked as "definitely static".
• Other details
  • This does not need to be recursive, because we are scanning breadth first for each depth level.
  • Visited addresses can be added to a set in order to cut off cycles, or alternatively, removed from the respective pointer maps (using a copy of the map).
  • This could be parallelized by splitting each depth's lookup procedure into multiple worker threads, but there may not be any speed benefit if CPython's free-threading is not used (GIL will stop any parallelism). It might work with Cython but the structures would need to be converted to something like C++ STL types, and an equivalent interval data structure library in C or C++ would need to be used.
  • The main optimization is that it uses far less memory than randomly scanning paths in a depth first manner multiple times, and far less time because paths are cut off early. A high memory usage app being scanned could produce pointer maps sized in the megabyte range, instead of potentially gigabytes for many full paths.
  • I think that the more maps the user provides, the more the search branches will be cut down.

[cromachina]

I implemented this idea here and got approximately the same results as Cheat Engine, although it's a little bit slower due to the Python overhead, but it's still many orders of magnitude faster than generating and comparing full sets of pointer scans with deep depths:

https://github.com/cromachina/pointer-scan/blob/main/src/pointer_scan/pointer_scan.py

For generating a single pointer map, it takes around 10 seconds, which is simply from using the function PyMemoryEditor.process.pointer_scan.build_pointer_map.

For building a set of pointer lists from 3 generated pointer maps, with a max depth of 7 and offset range of 0x400, it takes around 12 seconds, which is somewhat comparable to speed as Cheat Engine (without parallelism). The results are filtered to show "static" base addresses (ones that come from the main module).

Here I'm highlighting my "needle" because I know it's first dereference and offset is always 0: