如何统计程序中内存间接加载访问占比？求更优方案与实现思路

你的思路本质是污点跟踪（Taint Tracking）——核心逻辑是对来自内存加载的值做标记，并跟踪其在寄存器间的传播，当标记过的寄存器参与内存地址计算时判定为间接访问，这个方向完全可行，但落地时需要处理寄存器重用、常数覆盖、特殊寄存器（如栈基址）等细节，同时还有更高效的实现路径可以选择。

更优实现方案 #

1. 动态二进制插桩（推荐用于真实运行时统计） #

如果不需要源码，或想统计程序实际运行时的真实占比，用动态插桩工具（如Intel Pin、DynamoRIO）是最高效的选择，工具已经封装了指令拦截、寄存器上下文获取等底层细节，无需手动模拟指令集：

• 核心步骤：
  • 拦截所有内存加载指令（比如x86的mov rax, [addr]），统计总加载次数。
  • 维护一个污点寄存器集合：只要寄存器的值来自内存加载，或依赖内存加载的值经过ALU/位运算得到，就标记为污点；若寄存器被常数直接赋值，则清除标记。
  • 对于加载指令，检查其地址计算用到的基址/索引寄存器是否在污点集合中：如果是，就将该加载计数为间接访问。
  • 程序退出时，计算间接访问数 / 总加载数得到占比。
• 优势：无需源码，支持二进制程序，统计结果反映真实执行情况，能准确覆盖你提到的A[B[i]]、A[(B[i]&mask)+c]等复杂地址计算场景。

2. 编译器IR分析（适合源码级批量分析） #

如果有程序源码，基于LLVM IR或GIMPLE等中间表示做静态/动态分析会更灵活：

• 核心步骤：
  • 将源码编译为中间表示（比如用clang -emit-llvm -S生成LLVM IR）。
  • 遍历所有load指令，分析其地址操作数：
    • 若地址来自getelementptr（数组索引指令），检查索引参数是否依赖其他load指令的结果；
    • 若地址是指针变量，检查该指针的值是否来自内存加载。
  • 用编译器Pass自动完成遍历、标记与统计。
• 优势：可在编译阶段完成分析，无需运行程序，适合批量处理大量代码，还能结合静态分析覆盖所有潜在执行路径。

3. 优化你的污点跟踪思路 #

如果坚持自己实现污点跟踪，可做以下优化：

• 区分强污点与弱污点：完全来自内存加载的寄存器标记为强污点，经过常数运算后仍保留标记；若寄存器被常数覆盖，则立即清除污点。
• 处理特殊指令：比如x86的lea是地址计算指令，不会加载内存，但如果其源操作数带污点，目标寄存器也要标记为污点。
• 加入寄存器别名分析：避免因编译器寄存器重命名导致的误判，跟踪值的流向而非固定寄存器编号。

具体实现示例（以Intel Pin为例） #

#include "pin.H"
#include <iostream>
#include <unordered_map>

std::unordered_map<REG, bool> tainted_regs;
UINT64 total_loads = 0;
UINT64 indirect_loads = 0;

// 标记/清除寄存器污点
void UpdateTaint(REG dst_reg, bool is_tainted) {
    tainted_regs[dst_reg] = is_tainted;
}

// 处理指令，完成污点传播与访问统计
VOID InstructionCallback(INS ins, VOID *v) {
    // 处理内存加载指令
    if (INS_IsMemoryRead(ins)) {
        total_loads++;
        bool is_indirect = false;
        // 检查基址寄存器是否带污点
        REG base_reg = INS_MemoryBaseReg(ins);
        if (base_reg != REG_INVALID && tainted_regs.count(base_reg) && tainted_regs[base_reg]) {
            is_indirect = true;
        }
        // 检查索引寄存器是否带污点
        REG index_reg = INS_MemoryIndexReg(ins);
        if (index_reg != REG_INVALID && tainted_regs.count(index_reg) && tainted_regs[index_reg]) {
            is_indirect = true;
        }
        // 排除栈基址/栈指针的访问（不算间接）
        if (base_reg == REG_RBP || base_reg == REG_RSP) {
            is_indirect = false;
        }
        if (is_indirect) {
            indirect_loads++;
        }
        // 将加载指令的目标寄存器标记为污点
        REG dst_reg = INS_OperandReg(ins, 0);
        if (dst_reg != REG_INVALID) {
            UpdateTaint(dst_reg, true);
        }
    }
    // 处理算术/位运算指令，传播污点
    else if (INS_IsALU(ins) || INS_IsBitwise(ins)) {
        REG dst_reg = INS_OperandReg(ins, 0);
        if (dst_reg == REG_INVALID) return;
        bool src_tainted = false;
        for (UINT32 i = 0; i < INS_OperandCount(ins); i++) {
            if (INS_OperandIsReg(ins, i)) {
                REG src_reg = INS_OperandReg(ins, i);
                if (tainted_regs.count(src_reg) && tainted_regs[src_reg]) {
                    src_tainted = true;
                    break;
                }
            }
        }
        UpdateTaint(dst_reg, src_tainted);
    }
    // 处理常数赋值指令，清除污点
    else if (INS_OperandIsImmediate(ins, 1)) {
        REG dst_reg = INS_OperandReg(ins, 0);
        if (dst_reg != REG_INVALID) {
            UpdateTaint(dst_reg, false);
        }
    }
}

// 程序结束时输出统计结果
VOID FiniCallback(INT32 code, VOID *v) {
    if (total_loads == 0) {
        std::cout << "No memory loads detected." << std::endl;
        return;
    }
    double ratio = (double)indirect_loads / total_loads * 100;
    std::cout << "Total memory loads: " << total_loads << std::endl;
    std::cout << "Indirect memory loads: " << indirect_loads << std::endl;
    std::cout << "Indirect access ratio: " << ratio << "%" << std::endl;
}

int main(int argc, char *argv[]) {
    if (PIN_Init(argc, argv)) {
        std::cerr << "Pin initialization failed." << std::endl;
        return 1;
    }
    INS_AddInstrumentFunction(InstructionCallback, 0);
    PIN_AddFiniFunction(FiniCallback, 0);
    PIN_StartProgram();
    return 0;
}

注意事项 #

• 排除栈局部变量访问：栈基址寄存器（如rbp/rsp）的值来自程序初始化，并非内存加载，这类访问不算间接访问。
• 处理寄存器重用：循环中寄存器可能被重新赋值为常数，要及时清除污点标记，避免误判。
• 复杂地址计算：只要地址计算链中存在来自内存加载的值，就应标记为间接访问，这完全覆盖你提到的嵌套索引、位运算+常数等场景。

内容的提问来源于stack exchange，提问作者Sai Aravind