Metadata-Version: 2.4
Name: scalpel-elf
Version: 0.1.0
Summary: Insert real instructions into ELF executables, keeping them valid and runnable
Author: Pincheng Wang
License: MIT
Keywords: elf,binary,patching,instrumentation,reverse-engineering,aarch64,amd64,riscv64
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Topic :: Software Development :: Assemblers
Classifier: Topic :: Software Development :: Disassemblers
Classifier: Programming Language :: Python :: 3
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: POSIX :: Linux
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: capstone>=5.0
Requires-Dist: keystone-engine>=0.9.2
Requires-Dist: pyelftools>=0.30
Dynamic: license-file

# scalpel

Insert real instructions into an ELF executable at a chosen virtual address and
produce a **valid, fully-runnable** binary. The inserted code actually
executes; every displaced or shifted instruction is re-encoded so behavior is
preserved.

```sh
# insert a nop at vaddr 0x400c80, trampoline strategy (aarch64)
python3 scalpel.py --insert 0x400c80 nop mcf_s mcf_modified

# insert 3 instructions directly at 0x1050 (amd64); --arch auto-detected
python3 scalpel.py --strategy direct --insert 0x1050 "nop" --insert 0x1050 "inc eax" a.out a_modified
```

## Architecture

scalpel is a small package. The core ELF surgery is **ISA-agnostic**; every
architecture lives in its own backend module behind one interface.

```
scalpel/
  __init__.py     imports all backends (registering them) + core
  __main__.py     `python3 -m scalpel` entry
  backend.py      IsaBackend ABC, instruction-record contract, registry
  core.py         ELF re-layout, both strategies, dynamic-link fixups, CLI
  aarch64.py      AArch64 backend      (complete, byte-identical to pre-refactor)
  amd64.py        x86-64 backend       (complete, second-ISA proof)
  riscv64.py      RISC-V 64 backend    (complete, third-ISA proof)
scalpel.py        thin 12-line shim at the repo root
```

Dependency direction is one-way and acyclic: `core` imports only `backend`;
each backend imports only `backend` and self-registers via `@register`;
`__init__` imports everything so `import scalpel` registers all backends.

### The `IsaBackend` interface

`core` relies on exactly these keys of an *instruction record* (the rest —
`operands`, `kind`, `target`, `field_off`, … — is backend-private):

| key | meaning |
|---|---|
| `addr` | vaddr of the instruction |
| `file_off` | file offset in the **original** file (pre-relayout) |
| `size` | encoded byte length |
| `raw` | original encoded bytes |
| `mnemonic` | for error messages |

Backends implement: `insn_size`, `assemble`, `encode_branch(src,dst)`,
`decode_insn(raw,addr)`, `scan_instructions(data,elf)`,
`pc_rel_target(rec)`, `reencode_pc_rel(rec,new_addr,new_target,allow_widen)`,
`fix_shifted_instructions(...)`, `is_arch`, `validate_vaddr(V,instrs)`, plus
the class attributes `name`, `e_machine`, `insn_align`, `relative_reloc`,
`abs_reloc`, `section_align`.

**`reencode_pc_rel`'s `allow_widen` is the sharpest edge.** The *direct*
strategy shifts instructions in place, so a re-encode must keep its original
length — `allow_widen=False`, and an un-widenable overflow (e.g. an amd64
rel8 branch whose target moves out of range) is a hard error that
`--strategy auto` catches by falling back. The *trampoline* replays stolen
instructions into fresh space, so `allow_widen=True` permits growth (rel8 →
`0F 8? rel32`, `EB` → `E9 rel32`).

### Adding a new ISA

1. Write `scalpel/<isa>.py` — a `@register class <Isa>Backend(IsaBackend)`.
2. Import it in `scalpel/__init__.py` (one line).
3. Nothing in `core` changes.

That is the whole contract. Two recurring sub-problems to solve per ISA:

- **PC-relative re-encoding** (branches, Jcc, RIP/PC-relative memory, and
  address pairs like A64 ADRP+imm12 or RISC-V AUIPC+imm12). The pair logic
  stays private to the backend — see `fix_shifted_instructions`.
- **Branch semantics for `encode_branch`.** Note that A64's `B.imm26`
  displacement is relative to the branch's *own* address, while amd64's `E9
  rel32` is relative to the *next* instruction (`dst - src - 5`).

## The two strategies

- **direct** — shifts everything after V by +N (total inserted bytes) and
  re-encodes every PC-relative instruction that straddles the shift. Best for
  small batches (1–single-digit instructions). Only works where all references
  are PC-relative: on amd64, PIE binaries are safe, static `ET_EXEC` binaries
  are **not** (absolute immediates in `_start` are unrelocated).
- **trampoline** — steals the shortest instruction prefix covering one
  unconditional branch at V (aarch64: 4 bytes, 1 insn; amd64: 5 bytes, often 2
  insns), writes a `B/E9` to a veneer at the end of the executable LOAD
  segment, replays the stolen instructions there with all PC-relative refs
  re-encoded, runs the inserted batch, and branches back to V+K. Nothing in
  the original layout moves. This is the only option on static ET_EXEC.

`--strategy auto` (default) picks direct for batches of at most
`--max-direct` instructions and falls back to trampoline if direct refuses.

### Two trampoline hazards encoded in `core`

1. **A displaced instruction may target another byte of the stolen region.**
   If a stolen `jcc8` at V+2 targets the 3rd byte of the 5-byte jmp (which is
   now overwritten), it must be redirected to that instruction's *replay
   address* in the veneer. The replay addresses move as rel8→rel32 widening
   changes later replays' sizes, so this is solved by fixed-point iteration.
2. **An un-displaced branch may target into the stolen region.** A branch
   strictly inside `[V, V+K)` whose instruction is *not* displaced (it sits
   before V) would land on the jmp and die. `core` refuses such insertion
   points. (A branch landing exactly on V is safe — it hits the jmp itself.)

## CLI

```
python3 scalpel.py [--arch auto|amd64|aarch64|riscv64]
                  [--strategy auto|direct|trampoline] [--max-direct N]
                  --insert VADDR 'INSTRUCTION' [--insert ...]
                  INPUT OUTPUT
```

- `--arch` defaults to `auto` (detected from the ELF's e_machine); an
  explicit arch that mismatches the input is an error.
- Multiple `--insert` pairs are applied as one batch (in order) at their
  vaddrs.
- Insertions that would need more bytes than remain in the executable LOAD
  segment are refused; `auto` then retries as a trampoline.

## Validation

- **aarch64**: a byte-identity harness (`ref/byte_identity.py`) runs 19
  scenarios — 14 success paths (direct, trampoline, multi-vaddr, auto-fallback,
  ADRP-pair fixes, runnable output) + 5 error-parity paths — comparing the
  refactored package byte-for-byte against the pre-refactor oracle
  (`ref/scalpel_old.py`). **19/19 on both the local box and `white`**
  (aarch64 dev machine). SPEC2017 `mcf_s`: trampoline and direct insertions
  are byte-identical to the oracle, and both modified binaries run to exit 0
  with output identical to the original.
- **amd64**: `ref/amd64/validate_amd64.py` — 15 scenarios on a PIE and a
  static binary, **executing** each modified output natively (RIP-relative
  probes change the printed counter), plus ELF invariants (page congruence,
  entry coverage, section count, `.scalpel` presence) and two error paths.
  The backend is also byte-identical across machines (x86-64 host vs aarch64
  `white`).
- **riscv64**: `ref/riscv64/validate_riscv64.py` — 15 checks on a `-fPIE -pie`
  and a static binary, running each modified output under
  `qemu-riscv64-static`. The focus is **Zicbop prefetch insertion**:
  `prefetch.r/w/i` are verified byte-for-byte against the GNU assembler at the
  insertion point, and every variant runs (direct, trampoline, RVC 2-byte
  steal, auto-fallback, static trampoline). An `addi` probe adds exactly 1 to
  the printed counter to prove an inserted instruction executes. Error paths:
  non-32-aligned prefetch offset, non-boundary vaddr, and compressed (2-byte)
  insertions are all refused cleanly.

## Known limitations

- **direct strategy on SPEC**: aarch64 SPEC binaries contain 16-byte-aligned
  SIMD loads (`ldr qXt, [xN, #imm]`) whose data lives in the executable
  segment. A +N shift misaligns the offset unless **N ≡ 0 (mod 16)**, so a
  direct batch of e.g. 4 nops works but 1 nop is refused (a pre-existing
  limitation of the original tool, reproduced identically). `auto` falls back
  to trampoline, which shifts nothing.
- IFUNC / `R_*_IRELATIVE` relocations are not handled (both original and
  refactored).
- amd64: no 67-address-prefix RIP-relative / jrcxz forms (refused or
  undocumented); `loop`/`jrcxz` have no rel32 form, so an overflow is refused
  even in the trampoline.
- **riscv64**:
  - **Insertions must be one 4-byte instruction.** The assembler is GNU
    `riscv64-linux-gnu-as` with `-march=rv64imafd_zicsr_zifencei_zicbop` (no
    `c`), so compressed 2-byte insertions are refused (a direct shift must move
    code by a multiple of 4). A keystone built from master with RISC-V support
    is auto-detected and preferred when importable.
  - **JAL ±1MB, B-type ±4KB**; B-type has no wider form, so an overflow is
    refused even in the trampoline (like amd64 `loop`/`jrcxz`). The trampoline
    branch-back is a register-free `jal x0`.
  - **Static `ET_EXEC` is trampoline-only**: absolute `lui`/`addi` immediates
    (e.g. in `_start`) break under a direct shift, exactly as on amd64.
  - **`prefetch.r/w/i offset(rs1)`** require Zicbop and an offset that is a
    multiple of 32 (GNU as rejects others); they encode as `ori zero, rs1, imm`
    and are verified by bytes, not by capstone mnemonic.
  - Functions compiled with default RVC packing land on 2-mod-4 boundaries;
    those are correctly refused as insertion points (`validate_vaddr` requires
    V ≡ 0 mod 4 and an instruction boundary).
