指针扫描

Pointer Scan — 从一个运行时动态地址反向搜索出 “static base + N 层 offsets” 的指针链，使地址在游戏重启后依然可复用。Shadow CE 的实现跑在 kernel 里，single-ioctl 完成 collect → radix sort → BFS 全流程，160MB 内存预算，FPS2（4.6GB 游戏进程）实测 collect 82ms，整次扫描秒级返回。

1. 概念

1.1 为什么需要指针链

游戏里，随便一个 “值” 的地址每次启动几乎都不一样：

• ASLR：模块基址随机
• 堆分配顺序：对象地址每次不同
• session lifetime：死一次 / 换图 / 退到大厅，对象被销毁重建
• GC / UE4 tick：UObject 频繁重用 slot

扫出来的 0x70A1B2C3D0 再打开游戏就失效了。真正稳定的是 结构性路径： 从某个全局变量（.data / .bss，跟 .so 绑定）出发，一层层走指针到叶子字段。

libUE4.so + 0xB034CD8  (GEngine 全局指针)
    → +0x780            (GameViewportClient)
    → +0x78             (GameInstance)
    → +0x38             (LocalPlayers[0])
    → +0x0
    → +0x30             (PlayerController)
    → +0x260            (Character)
    → +0x750            (Actor Weapon)
    → +0x1440           (Ammo int32)

“在 libUE4.so 加载点 + 0xB034CD8 处读 8 字节指针，加上 0x780 再读 8 字节，… 最后一次加上 0x1440 读 4 字节” — 这叫一条 pointer chain，只要游戏代码结构不变，跨重启复用。

1.2 Cheat Engine 类比

1.3 术语

• Level / depth：链的跳数，0 是 target，N 是 static base。
• Offset：每一跳读完指针后加的偏移。[0] 最靠近 base，[depth-1] 最靠近 target（CE 约定，写文件时再反转）。
• Base module：链的起点 .so / elf file。必须是 rw- 段（.data / .bss），不能是 r-x（代码段里 bl 指令编码容易被误认作指针）。
• Anchor / static：就是 base 区间，扫描时判定 “已命中静态起点”。

2. 方案总览

2.1 演进史（重要设计决策都在这）

Shadow CE 的指针扫描被 重写了 4 次，每次失败的原因都塑造了当前方案。来源：ptrscan-final-plan.md, ptrscan-implementation-plan-v4.md, ptrscan-debug-lessons.md。

关键教训（来自 ptrscan-debug-lessons.md）：

“UE4 指针链深度 > 10 层，堆引用极度密集（每个 UObject 有 Outer/Class/Package 指针），反向扫描本质上被噪声淹没。但 ptrscan 仍有价值：非 UE4 游戏、初始探索、找静态 base 附近稳定链，CE 就是这么用的。“

2.2 当前 pipeline

总耗时（FPS2 4.6GB 进程）：

• Collect: ~82ms – 30M pairs（3-28-ptrscan-session-full.md）
• Radix sort: ~100ms（8-pass LSD，全 integer，cache-friendly）
• BFS: 2-13s（depth、offset、max_results 决定）
• TCP 传链：<10ms (100K chains × ~80B)

2.3 为什么不是…

为什么不 DFS（3-28 方案的教训）：DFS 对每个 candidate 都触发一次全内存扫描，UE4 堆上 226 秒。BFS 每层只 bsearch 一次，所有当前层 target 一次性匹配，总复杂度 O(depth × n_pairs × log n_pairs)。

为什么不 per-level scan（v4 per-level 教训）：每一层都要 kmap 全部 RW 页（500MB+），depth × 2s 的顺序 IO 很难 < 10s；而且每层加个硬 cap 就会在 dense heap 上随机切断深链。

为什么 collect-then-BFS 可行：collect 是一次性的，radix sort 是 O(n) 常数快，整个图压在 160MB 里。BFS 每个节点一次 upper_bound + 邻居迭代，visited hash set 防止指数爆炸。

3. Collect 阶段（kern_ptrscan.h:269-340）

3.1 要扫哪些 VMA

3.2 什么是 static base（anchor）

Phase 1 单独 walk 所有 VMA 确定哪些是 “static 基址区”：

1. File-backed rw- VMA：.data / .got 等。

2. 紧跟其后的 anon VMA：这是 .bss ！很多游戏（尤其 UE4 GEngine）的全局对象指针存在 .bss，而 .bss 在 /proc/pid/maps 里没有 file-backed 关联。源码判定逻辑：

   if (!vma->vm_file && last_file_rw_end &&
       vma->vm_start == last_file_rw_end &&
       n_statics < PTRSCAN_MAX_STATICS)
       // 加入 statics[]

3. 过滤的文件名前缀 / 后缀（避免 JIT 缓存当 anchor）：

   过滤	为什么
   kgsl*, mali*	GPU 驱动共享内存
   ashmem*, dmabuf*	匿名共享
   .vdex, .odex, .art, .dex, .oat	ART / Dalvik 缓存，每次启动都变

最多 PTRSCAN_MAX_STATICS = 512 个区间。

3.3 Pair 收集

对每个 RW VMA，按页 walk：

几个关键点：

• chunked lock：每 PTRSCAN_COLLECT_CHUNK = 2048 页放一次 mmap_read_lock，避免长时间阻塞目标进程 page fault。
• mask：req->mask 默认 0x0000_FFFF_FFFF_FFFF（48-bit VA，砍 MTE / PAC tag）。允许用户覆盖。
• 过滤 val < 0x1000：NULL-ish 和 PAGE 0 页不可能是指针。
• signal_pending(current) 每页检查：允许客户端 SIGKILL 中断。
• collect_cursor：重新 lock 后从上次位置继续，避免 iterator use-after-free（v3 滑动窗口方案因此崩过）。

3.4 Buffer 预算 & 降级

for (max_pairs = 40000000; max_pairs >= 5000000; max_pairs >>= 1) {
    pairs = vmalloc(max_pairs * sizeof(*pairs));   // 16B per pair
    if (!pairs) continue;
    sort_tmp = vmalloc(max_pairs * sizeof(*pairs));
    ...
}

注意：sort_tmp 不是浪费 —— radix sort 需要 ping-pong buffer，v1-v3 分配过但没用的 pairs_tmp 是真正的 bug。

3.5 DUMP 模式

PTRSCAN_F_DUMP flag：跳过 sort/BFS，把 raw pairs + statics 一次性 copy 出来。用途：

• Server 端或 PC 上做实验性算法（3-28 session 试过 pure-C BFS/DFS/Dijkstra/beam search，都没成功，但 dump 通道本身保留）。
• 诊断 / 导出供离线分析。

协议看 usr_server.c CMD 0xD7：318MB 回传用了 10.7s（3-28-ptrscan-session-full.md）。

4. Search 阶段

4.1 LSD Radix Sort（kern_ptrscan.h:96-133）

for (pass = 0; pass < 8; pass++) {
    int shift = pass * 8;
    // count[256]; histogram on src[i].target >> shift & 0xFF
    // prefix sum; scatter to dst[]
    swap(src, dst);
}

• 8 passes × 8-bit digits = 处理 64-bit target
• 偶数次 pass → 结果正好落回 a（原 buffer）
• 复杂度 O(8N)，30M pair 约 100ms，比 sort 泛型快数倍
• sort_tmp 就是这个算法的 pong buffer

4.2 Pair graph 的本质

排序完 pairs[] 是 按 target 升序的邻接表，一条 pair = 有向边：

source(pa+off) ---→ target(*(source)) = V

“source 里存了一个指针，指向 target”

反向 BFS 从 target = req->target 出发，找所有入度：谁指向这附近（[addr - off, addr + off]）？

unsigned int idx = ptrscan_pair_upper(pairs, n_pairs, hi_key);
while (idx > 0 && pairs[idx - 1].target >= lo_key) {
    idx--;
    unsigned long src = pairs[idx].source;
    int diff = (int)(addr - pairs[idx].target);  // offset we need to hop
    ...
}

ptrscan_pair_upper 是手写 binary search（returns first i where arr[i].target > key），然后从 idx 往左扫至 pairs[idx-1].target < lo_key 停止。

4.3 BFS 核心（kern_ptrscan.h:372-458）

关键数据结构：

struct ptrscan_bfs_node {
    unsigned long addr;
    int           offset;   // offset we added at this hop
    unsigned int  parent;   // index of parent node in queue[]
};
 
struct ptrscan_visited_entry {
    unsigned long addr;
    unsigned int  count;
};

• queue[] 容量 PTRSCAN_BFS_MAX = 4M，节点一经 enqueue 永不移动，parent 索引稳定 → 回溯链只需顺着 parent 向队首走。
• visited[] 是 open-addressing 哈希表，PTRSCAN_VISITED_SIZE = 4M slots，hash (addr >> 3) & mask，线性探测最多 32 位。每条 visited 记 count，达到 max_per_node (=3) 就不再入队，但仍允许短链命中（所以不是硬 dedup）。

4.4 几个小但关键的行为

4.5 Chain emit

当 src 落在 statics[] 里（phase 1 收集的区间）且 cur_depth >= min_depth：

hops[0] = diff;              // 当前这一跳
qi = head - 1;               // 当前节点在 queue 里的索引
while (hop_count < PTRSCAN_MAX_DEPTH && qi > 0) {
    hops[hop_count++] = queue[qi].offset;
    qi = queue[qi].parent;
}
if (qi == 0) hops[hop_count++] = 0;
 
c->depth = hop_count - 1;
c->base_addr = src;
for (i = 0; i < c->depth; i++)
    c->offsets[i] = hops[i];

hops[] 被反向组装 —— [0] 是离 target 最近的 offset，[depth-1] 是离 base 最近。这就是 CE walk order：addr = base; for off in offsets: addr = *addr + off。

4.6 常量参考

5. Validate 阶段

5.1 为什么要验证

第一次扫完经常有几千甚至几万条链，大量是堆上临时对象（UE4 GC 后断裂）或干扰指针（值恰好等于 target，但语义无关）。需要：

1. 多次换局 / 死亡重生后，哪些链仍然指向正确地址？
2. 哪些链值恒定为预期（例如 ammo 一定 > 0）？
3. 哪些能跨游戏重启活下来？

这一步本质是 CE 里的 “pointer scan → rescan” 流程。

5.2 Chain Walk Protocol (CMD 0xD8)

内核侧实现在 ptrscan_chain_walk()（kern_ptrscan.h:487-582）：

• 单次 ioctl 处理到 200K 条链。
• 每 PTRSCAN_CW_CHUNK = 256 条放一次 lock，防 page fault blocked。
• 断链（某一跳 mem_read8 失败）回传 addr=0, val=0xDEADDEAD。
• 批量执行 = 零 TCP round-trip：首轮 2 条链 14ms（vs 每条 ~5ms round trip）。

5.3 Rescan 的 UI 工作流

客户端代码 ptrscan_dialog.py:519-634 _on_rescan：

1. Probe 当前 read 连接能不能读 0x1000（活检）
2. 如果不能 → _do_reconnect：用 adb.exe shell pidof <package> 找到新 PID，刷新 module cache，重开 read 连接
3. 把所有 chain 的 base_addr 先从 base_str（libUE4.so+0x2ADCD8）解到当前 runtime（处理 ASLR）
4. 后台线程发 CMD 0xD8 批量走链
5. 过滤 val == expected 的链（区分 broken / wrong value / match 计数）
6. 用结果替换 Results table

5.4 FPS2 实战验证结果（3-28 session）

首次扫描 (FPS2 ammo target):
  25088 chains in 25s

换局 rescan (expected=40):
  11 chains survive

重启游戏 rescan:
  5 条链跨重启存活
  都共享尾部 +0x260 +0x10 +0x298 +0x1440
  来自未知 static global libUE4.so+0xAF0A7C8 —— ptrscan 自动发现的全新链

已验证可复用的几条链（3-28-ptrscan-session-full.md）：

6. 客户端实现（ptrscan_dialog.py）

6.1 Settings dialog (PtrScanSettingsDialog, 行 57-128)

Pointer Scan Settings
  Address:     [0x701169BF00           ]
  Max depth:   [10                     ]
  Max offset:  [8192                   ]
  Max results: [100000                 ]
  Min depth:   [0                      ]

  [ ] Allow negative offsets

                         [Scan]  [Cancel]

按 Scan → flags 组装成 (min_depth << 8) | (neg & 1) 发出去。

6.2 Results window (PtrScanResultsWindow, 行 131-716)

4 列表格：

核心特性：

• Live Value 刷新：QTimer 1.5s tick，每次批量 chain_rescan 只跑可见行（_table.rowAt 计算 viewport），_val_refreshing 互斥防 overlap。
• Background thread 读：所有 TCP 都在 daemon thread 里，主线程只做 pending-results apply。
• 双击 → 发 chains_added 信号 → main_window 收到后 AddrEntry(is_pointer=True, base_addr_str=..., pointer_offsets=...) 加入 address list。
• 多选 Add to Address List：一次加多条。
• Save / Load .ptr：CE 兼容格式（magic 0xCE, version 2, uncompressed）。Offset 存储时反向（CE 约定），读回时再翻回来。
• Reconnect 按钮：手动触发 adb pidof 找新 PID，重建连接（ptrscan 结果窗口要活过游戏重启）。
• Base 解析：_resolve_base_runtime() 把 libUE4.so+0x2ADCD8 在当前 module cache 里查 segment → 得到 runtime addr。段内 foff <= offset < foff + size 优先，fallback first_base + offset（PIE 天然对）。

6.3 Worker thread (PtrScanWorker, 行 25-54)

class PtrScanWorker(QThread):
    finished = pyqtSignal(object)   # (chains, time_ms) or error string
 
    def run(self):
        own = CEClient()
        own.connect(self._client._host, self._client._port)
        own.open_process(self._pid)
        chains, time_ms = own.ptrscan(
            self._pid, self._target, self._depth,
            self._offset_max, self._flags, self._max_chains,
            self._min_depth)
        own.close()
        self.finished.emit((chains, time_ms))

• 独立 socket：不抢主 scan 连接的锁。
• pyqtSignal（不是 QTimer.singleShot(0, lambda)）：后者从子线程调用会静默失败（教训来自 ptrscan-debug-lessons.md）。

6.4 菜单集成

main_window.py 里：

• 右键 address list item → Pointer scan for this address → 预填 address 打开 settings dialog
• Results window 关闭不阻塞 scan，可以同时开多个

7. 内核侧（kern_ptrscan.h）

7.1 ioctl 接口 (shadow_ce.h:172-224)

/* Scan */
#define SHADOW_CE_PTRSCAN      _IOWR(CE_IOC_MAGIC, 20, struct ce_ptrscan_req)
#define PTRSCAN_F_NEGATIVE     (1 << 0)
#define PTRSCAN_F_DUMP         (1 << 1)  /* 跳过 BFS，导出 raw pairs */
 
struct ce_ptrscan_chain {
    unsigned int  depth;
    unsigned long base_addr;
    int           offsets[PTRSCAN_MAX_DEPTH];  /* CE order */
};
 
struct ce_ptrscan_req {
    int           pid;
    unsigned long target;
    unsigned long mask;           /* 0 → 默认 48-bit */
    unsigned int  depth_max;
    unsigned int  offset_max;
    unsigned int  flags;          /* PTRSCAN_F_* | (min_depth << 8) */
    unsigned int  max_results;
    unsigned long result_buf;     /* 用户态 ce_ptrscan_chain 数组 */
    unsigned int  result_count;   /* out */
    unsigned int  scan_time_ms;   /* out */
};
 
/* Chain walk / rescan */
#define SHADOW_CE_CHAIN_WALK   _IOWR(CE_IOC_MAGIC, 21, struct ce_chain_walk_req)
#define CHAIN_WALK_MAX         200000
#define CHAIN_WALK_DEAD        0xDEADDEAD
 
struct ce_chain_walk_entry {
    unsigned long base_addr;
    unsigned int  depth;
    int           offsets[PTRSCAN_MAX_DEPTH];
};
 
struct ce_chain_walk_result {
    unsigned long addr;          /* 0 = broken */
    unsigned int  val;           /* val_size bytes at final addr */
};

7.2 TCP CMD 对照

7.3 内存 layout（执行期峰值）

vmalloc 失败会自动降级到 20M / 10M / 5M pairs。12GB RAM 手机通常 40M 也能分配。

7.4 并发性 / 可取消

• signal_pending(current) 在 collect 内循环、BFS 主循环都会检查
• 客户端取消 = close socket → server 端 send/recv 报错 → 进程退出 → kernel ioctl 被 signal 唤醒 → 干净退出，释放所有 vmalloc
• 不支持中途暂停恢复（一次 ioctl 跑完，中断只能重来）

7.5 锁分析

Phase 2 / chain walk 选择chunked read lock 不是独占，允许目标进程并行 page fault。

8. 坑 & 经验

精选来自 ptrscan-debug-lessons.md 和各历史 session 的教训，按杀伤力排序。

8.1 UE4 反向扫描本质困难

来源：ptrscan-debug-lessons.md §1, ptrscan-final-plan.md §Avoid

libUE4.so 的 rw- 段只有 84KB，GEngine/GWorld 通过 .data → .bss → 堆对象链间接引用。每个 UObject 又都有 Outer/Class/Package 指针，堆里 fan-out 100-500 per node。depth > 10 才能碰到 .data，CE 默认 depth=7 对 UE4 不够。 实际可用链都需要 min_depth >= 5，offset 4-8K。

8.2 代码段指令被误认作指针

来源：ptrscan-debug-lessons.md §2

ARM64 bl 指令 0x94000071xxxxxxxx untag 后地址范围 0x71xxxxxxxx 正好是堆区。修：static 判定只收 rw- 段（已在 Phase 1 实现）。

8.3 .bss 不是 file-backed

来源：ptrscan-debug-lessons.md §3

GEngine/GWorld 就住 .bss。/proc/pid/maps 里 .bss 段显示 [anon] 或空。必须用 “anon VMA 紧跟在 file-backed rw- 后面” 的启发式（Phase 1 的 last_file_rw_end 逻辑），否则 static base 全漏。

8.4 untagged_addr 不能硬编码 39-bit

来源：ptrscan-debug-lessons.md §8

SM8750 可能是 48-bit VA。用 req->mask（默认 0x0000FFFFFFFFFFFF）或直接 untagged_addr() 宏，别写 & 0x7FFFFFFFFF。

8.5 offset 不要 reverse

来源：ptrscan-debug-lessons.md §9, ptrscan-final-plan.md §Avoid

BFS 输出的 offsets[] 已经是 CE walk order [closest_to_base, ..., closest_to_target]（chain emit 的反向 hops 组装决定的）。

• pointer_offsets 不要 reverse
• .ptr 存档时才反转（CE 文件格式约定）

8.6 _resolve_pointer 必须 addr += offset

来源：3-28-ptrscan-session-full.md Phase 1

CE 标准语义：next = *cur + offset，先 deref 再加。老代码写 addr -= offset 跑了很久没人发现，修好后 ammo 链一次通过。

8.7 QTimer.singleShot(0, …) 从子线程会静默失败

来源：ptrscan-debug-lessons.md §6

Worker thread 里回调主线程必须用 pyqtSignal.emit，QTimer.singleShot 从子线程调用不会触发。

8.8 pairs_tmp 不要预分配但不用

来源：ptrscan-debug-lessons.md §4

v1-v3 分配了 320MB pairs_tmp 打算给 radix sort 用，但实际走的是 qsort，白占内存直接 OOM。如果你用 radix sort，它就是必须的（ping-pong）；如果你用 qsort，别分配。

8.9 VMA iterator 跨 lock cycle use-after-free

来源：ptrscan-debug-lessons.md §7

滑动窗口 drop mmap_read_lock → copy_to_user → reacquire 之后，VMA_ITERATOR 的 maple tree cursor 指向已释放内存 → kernel crash。修：

• 要么 vmalloc 一整块、一次 lock 全搞定
• 要么 chunked 时记录 collect_cursor 地址（不是 iterator state），重新 lock 后用 VMA_ITERATOR(vmi, mm, collect_cursor) 从该地址开始（当前方案）

8.10 ART / Dalvik 缓存不能当 anchor

来源：kern_ptrscan.h:238-249

.vdex / .odex / .art / .dex / .oat 每次启动都变，在里面找到的 “static” 链重启失效。kgsl / mali / ashmem / dmabuf 是设备 / 共享内存，也不算 static。Phase 1 硬编码过滤。

8.11 Rescan 前必须先 probe + 可能 reconnect

来源：ptrscan_dialog.py:546-557

游戏重启 PID 变了，旧 socket / 旧 pid 的 chain_rescan 会返回全 DEAD。修：rescan 按钮先 read_memory(pid, 0x1000, 1) 活检，失败自动 adb pidof <package> 找新 pid 并重建 read 连接。

9. 未来 / 限制

9.1 当前限制

9.2 失败的尝试（留作警示）

从 3-28-ptrscan-session-full.md Phase 5：

• PC 端 318MB raw pair dump + C BFS/DFS：44M 节点，29K 链，找不到 GEngine
• Dijkstra (offset-sum as cost)：visited 依然挡路
• Beam search K=50000：UE4 dense heap 上杯水车薪

结论：纯图搜索无法在 UE4 dense heap 上找到特定深链。正确做法是 IDA/SDK dump 先找到候选全局，再 ptrscan 做 rescan filter。

9.3 可能的优化方向

10. 一次典型扫描全景

把整个流程按时间轴串起来，参考 3-28-ptrscan-session-full.md Phase 4-9 的真实运行。

11. 快速参考

11.1 典型参数组合

11.2 相关源码

11.3 依赖

• kern_mem.h：mem_walk_pte(), struct mem_pte_result, mem_read8()（由 memscan 提供，见 内存扫描）
• kern_modules.h / enum_modules：把 runtime addr 映射回 module+file_offset（用于 base_str 展示）

11.4 相关 feature

• 内存扫描 — 提供底层 page/PTE 读取
• UI 设计 — Pointer scan 入口与整体 UI
• 反汇编 / Hexview — 手动验证指针链最终地址