morluto/rea

Fork

You've already forked rea

mirror of https://github.com/morluto/rea.git synced 2026-11-05 06:45:22 +00:00

Code Issues 1.3k Projects Packages Wiki Activity

[GH-ISSUE #4972] [Feature] Add semantic-equivalence verification for reconstructed native code #3076

New issue

Open

opened 2026-10-31 00:36:02 +00:00 by bsakaguchi · 1 comment

bsakaguchi commented

2026-10-31 00:36:02 +00:00

Owner

Copy link

Originally created by @heaven-hm on GitHub (Oct 18, 2026).
Original GitHub issue: https://github.com/morluto/rea/issues/4972

Problem

REA can inspect native binaries and collect runtime observations, but it does not yet provide a general, trustworthy workflow for checking whether reconstructed C/C++ preserves the original native function's behavior.

The goal is semantic equivalence, not source/CFG similarity. The candidate may use a different algorithm, control-flow graph, or set of helper functions; it should pass when the observable behavior is equivalent within a clearly declared scope. Incorrect calculations, missing branches/calls, wrong return values, omitted memory/global-state updates, or changed side effects should be reported as mismatches.

This complements the function-dossier/conformance work in #31/#55 and the evidence-trust issue #3980; it is specifically about comparing an original native function with a source-level reconstruction.

Proposed direction

Integrate existing analysis/verification engines through provider adapters rather than attempting to implement every solver and emulator inside REA. Keep tool availability explicit and optional; do not treat a tool being installed or imported as proof that a particular target/function was analyzed successfully.

Relevant tools:

angr — binary analysis, symbolic execution, path exploration and counterexample search: https://github.com/angr/angr
Triton — dynamic symbolic execution, taint analysis and SMT-backed expression analysis: https://github.com/JonathanSalwan/Triton
Remill — lift machine instructions to LLVM bitcode for compatible downstream analysis: https://github.com/lifting-bits/remill
Alive2 — LLVM IR refinement/equivalence checking within its supported model and scope: https://github.com/AliveToolkit/alive2
CBMC — bounded model checking of C/C++ assertions and properties: https://github.com/diffblue/cbmc
Z3 — SMT solver for supported expression/state obligations: https://github.com/Z3Prover/z3
Radare2 — binary inspection, disassembly and analysis (supporting evidence, not an equivalence proof): https://github.com/radareorg/radare2
Binary Ninja API — optional integration for IL, CFG and data-flow evidence: https://github.com/Vector35/binaryninja-api and https://docs.binary.ninja/

REA already supports native-analysis providers such as Hopper, Ghidra and IDA, plus selected Z3 proofs and differential observations. Reuse those capabilities where appropriate. No single listed tool proves arbitrary binary-to-source equivalence by itself; the implementation must combine them and declare limitations accurately.

Desired workflow

Bind the original executable and candidate source/build to hashes, architecture, ABI, function address/symbol and tool versions.
Recover the target's supported input/output contract and relevant state: return value, output buffers, memory/global writes, errors, and observable calls/side effects.
Use symbolic/concolic exploration or solver-backed obligations where feasible to generate inputs and find counterexamples.
Run a differential harness against the original function and candidate with equivalent initial state and inputs. For pointer/ABI-sensitive functions, require an appropriate native harness or dual-emulation strategy; do not compare incompatible calling conventions as if they were equivalent.
Where the original and candidate can be lifted to compatible semantic representations, attempt a formal equivalence/refinement check (for example, Remill + an appropriate LLVM checker). If not feasible, report tested behavior and its coverage rather than claiming a proof.
Preserve every mismatch as a regression case. Expose the same result contract through CLI and MCP.

Result model

Every check should return one of:

PROVEN — a supported formal check established equivalence under explicit assumptions and scope.
MISMATCH — a reproducible counterexample or observable difference was found.
TESTED_ONLY — all declared tests passed, but general equivalence was not proven.
INCONCLUSIVE — required observations, a trustworthy reference execution, or tool capability were unavailable.

CFG similarity, decompiler agreement, comments, a manifest status label, or a passing finite test suite must never independently produce PROVEN.

Acceptance criteria

Add an explicit native semantic-verification capability/provider contract and CLI/MCP operation.
Detect a wrong-calculation control (e.g. original x * 256, candidate x * 25) and return MISMATCH with the failing input and observed values.
Allow a different implementation/control-flow shape when the supported proof or tests establish equivalent observable behavior.
Compare return values, output bytes, relevant memory/global-state changes, error outcomes and declared side effects; identify unsupported/unobserved dimensions.
Include boundary, signedness, overflow, null/pointer and branch-transition cases when applicable to the function contract.
Bind results to the exact original binary, candidate source/build, harness, test corpus and analysis-tool versions; reject stale evidence.
Report proof assumptions, explored/tested coverage, limits and counterexamples in machine-readable Evidence.
Missing providers, timeouts, unsupported instructions, unknown state or incomplete observations result in INCONCLUSIVE—not a false PASS.
Add source-owned fixtures including both a semantically equivalent alternative implementation and deliberately incorrect candidates; test through public CLI/MCP contracts.
Respect REA's existing workflow direction: compose authorized tools/scripts and comparisons; don't reintroduce a custom replay/execution subsystem without a separately justified requirement.
Document supported target formats/architectures and the distinction between structural similarity, differential testing and formal proof.

Non-goals

Requiring candidate source or CFG to resemble the original.
Claiming universal equivalence from finite tests or symbolic exploration with incomplete coverage.
Requiring every optional engine to be installed for ordinary REA usage.
Automatically downloading or redistributing external/proprietary tools without explicit approval and license review.

Related work

#31 — Complete truthful analyze_function dossiers
#55 — Strengthen semantic Hopper conformance across source-built fixtures
#3980 — Overall replay verification passes despite unresolved capture evidence

Originally created by @heaven-hm on GitHub (Oct 18, 2026). Original GitHub issue: https://github.com/morluto/rea/issues/4972 ## Problem REA can inspect native binaries and collect runtime observations, but it does not yet provide a general, trustworthy workflow for checking whether reconstructed C/C++ preserves the original native function's behavior. The goal is **semantic equivalence, not source/CFG similarity**. The candidate may use a different algorithm, control-flow graph, or set of helper functions; it should pass when the observable behavior is equivalent within a clearly declared scope. Incorrect calculations, missing branches/calls, wrong return values, omitted memory/global-state updates, or changed side effects should be reported as mismatches. This complements the function-dossier/conformance work in #31/#55 and the evidence-trust issue #3980; it is specifically about comparing an original native function with a source-level reconstruction. ## Proposed direction Integrate existing analysis/verification engines through provider adapters rather than attempting to implement every solver and emulator inside REA. Keep tool availability explicit and optional; do not treat a tool being installed or imported as proof that a particular target/function was analyzed successfully. Relevant tools: - **angr** — binary analysis, symbolic execution, path exploration and counterexample search: https://github.com/angr/angr - **Triton** — dynamic symbolic execution, taint analysis and SMT-backed expression analysis: https://github.com/JonathanSalwan/Triton - **Remill** — lift machine instructions to LLVM bitcode for compatible downstream analysis: https://github.com/lifting-bits/remill - **Alive2** — LLVM IR refinement/equivalence checking within its supported model and scope: https://github.com/AliveToolkit/alive2 - **CBMC** — bounded model checking of C/C++ assertions and properties: https://github.com/diffblue/cbmc - **Z3** — SMT solver for supported expression/state obligations: https://github.com/Z3Prover/z3 - **Radare2** — binary inspection, disassembly and analysis (supporting evidence, not an equivalence proof): https://github.com/radareorg/radare2 - **Binary Ninja API** — optional integration for IL, CFG and data-flow evidence: https://github.com/Vector35/binaryninja-api and https://docs.binary.ninja/ REA already supports native-analysis providers such as Hopper, Ghidra and IDA, plus selected Z3 proofs and differential observations. Reuse those capabilities where appropriate. No single listed tool proves arbitrary binary-to-source equivalence by itself; the implementation must combine them and declare limitations accurately. ## Desired workflow 1. Bind the original executable and candidate source/build to hashes, architecture, ABI, function address/symbol and tool versions. 2. Recover the target's supported input/output contract and relevant state: return value, output buffers, memory/global writes, errors, and observable calls/side effects. 3. Use symbolic/concolic exploration or solver-backed obligations where feasible to generate inputs and find counterexamples. 4. Run a differential harness against the original function and candidate with equivalent initial state and inputs. For pointer/ABI-sensitive functions, require an appropriate native harness or dual-emulation strategy; do not compare incompatible calling conventions as if they were equivalent. 5. Where the original and candidate can be lifted to compatible semantic representations, attempt a formal equivalence/refinement check (for example, Remill + an appropriate LLVM checker). If not feasible, report tested behavior and its coverage rather than claiming a proof. 6. Preserve every mismatch as a regression case. Expose the same result contract through CLI and MCP. ## Result model Every check should return one of: - **PROVEN** — a supported formal check established equivalence under explicit assumptions and scope. - **MISMATCH** — a reproducible counterexample or observable difference was found. - **TESTED_ONLY** — all declared tests passed, but general equivalence was not proven. - **INCONCLUSIVE** — required observations, a trustworthy reference execution, or tool capability were unavailable. CFG similarity, decompiler agreement, comments, a manifest status label, or a passing finite test suite must never independently produce PROVEN. ## Acceptance criteria - [ ] Add an explicit native semantic-verification capability/provider contract and CLI/MCP operation. - [ ] Detect a wrong-calculation control (e.g. original `x * 256`, candidate `x * 25`) and return MISMATCH with the failing input and observed values. - [ ] Allow a different implementation/control-flow shape when the supported proof or tests establish equivalent observable behavior. - [ ] Compare return values, output bytes, relevant memory/global-state changes, error outcomes and declared side effects; identify unsupported/unobserved dimensions. - [ ] Include boundary, signedness, overflow, null/pointer and branch-transition cases when applicable to the function contract. - [ ] Bind results to the exact original binary, candidate source/build, harness, test corpus and analysis-tool versions; reject stale evidence. - [ ] Report proof assumptions, explored/tested coverage, limits and counterexamples in machine-readable Evidence. - [ ] Missing providers, timeouts, unsupported instructions, unknown state or incomplete observations result in INCONCLUSIVE—not a false PASS. - [ ] Add source-owned fixtures including both a semantically equivalent alternative implementation and deliberately incorrect candidates; test through public CLI/MCP contracts. - [ ] Respect REA's existing workflow direction: compose authorized tools/scripts and comparisons; don't reintroduce a custom replay/execution subsystem without a separately justified requirement. - [ ] Document supported target formats/architectures and the distinction between structural similarity, differential testing and formal proof. ## Non-goals - Requiring candidate source or CFG to resemble the original. - Claiming universal equivalence from finite tests or symbolic exploration with incomplete coverage. - Requiring every optional engine to be installed for ordinary REA usage. - Automatically downloading or redistributing external/proprietary tools without explicit approval and license review. ## Related work - #31 — Complete truthful `analyze_function` dossiers - #55 — Strengthen semantic Hopper conformance across source-built fixtures - #3980 — Overall replay verification passes despite unresolved capture evidence

bsakaguchi commented

2026-10-31 00:36:04 +00:00

Author

Owner

Copy link

@XinwangTao commented on GitHub (Oct 18, 2026):

Strong proposal — the result model is the most important part, especially INCONCLUSIVE instead of a false PASS and the rule that structural similarity alone can never yield PROVEN. A few implementation notes from the differential-harness side: (1) bind the ABI explicitly per target (calling convention, register/stack layout, volatile state) — comparing two functions under different implicit ABIs is the fastest route to fake MISMATCHes; (2) start the corpus with scalar/pointer-free contracts (the x256 vs x25 control) before adding heap and global-state dimensions, since equivalent initial state is the hardest thing to pin down for pointer-heavy functions; (3) scope PROVEN to what the formal layer can actually establish (Remill + Alive2 is strong on arithmetic/integer logic, weak on aliasing and side-effect ordering) and fall back to TESTED_ONLY everywhere else — the contract already says this, worth making it the default rather than the exception; (4) keep each provider's verdict plus its assumptions in the Evidence so a MISMATCH can be audited back to a concrete counterexample.

@XinwangTao commented on GitHub (Oct 18, 2026): Strong proposal — the result model is the most important part, especially INCONCLUSIVE instead of a false PASS and the rule that structural similarity alone can never yield PROVEN. A few implementation notes from the differential-harness side: (1) bind the ABI explicitly per target (calling convention, register/stack layout, volatile state) — comparing two functions under different implicit ABIs is the fastest route to fake MISMATCHes; (2) start the corpus with scalar/pointer-free contracts (the x*256 vs x*25 control) before adding heap and global-state dimensions, since equivalent initial state is the hardest thing to pin down for pointer-heavy functions; (3) scope PROVEN to what the formal layer can actually establish (Remill + Alive2 is strong on arithmetic/integer logic, weak on aliasing and side-effect ordering) and fall back to TESTED_ONLY everywhere else — the contract already says this, worth making it the default rather than the exception; (4) keep each provider's verdict plus its assumptions in the Evidence so a MISMATCH can be audited back to a concrete counterexample.

bsakaguchi referenced this issue

2026-10-31 01:07:50 +00:00

[PR #3075] [MERGED] docs(native): distinguish analysis memory from source bytes #5594

bsakaguchi referenced this issue

2026-10-31 01:07:50 +00:00

[PR #3076] [CLOSED] fix(native): align retained-view recovery guidance across MCP and docs #5595

No Branch/Tag specified

main

codex/procedure-reference-stacked

release-please--branches--main--components--rea-agents

release-please--branches--main--components--rea-agents--release-notes

codex/kuna-independent-retry

codex/byte-search-overlay-coverage

codex/open-failure-target-receipt

codex/kuna-xref-evidence

codex/ghidra-ambiguous-procedure-recovery

codex/function-source-bundle

codex/trace-function-integration-prototype

codex/snapshot-source-closure

codex/recorded-evidence-array-pages

codex/evidence-recovery-redesign

codex/trace-feature-address-scope

codex/call-discovery-scope

codex/ghidra-literal-candidate-evidence

codex/decompile-directory-independent-retry

codex/retry-provenance-base

codex/value-flow-capability-experiment

codex/ghidra-containing-instruction

cursor/readme-discord-button-ef9f

dependabot/github_actions/actions/setup-node-7.1.0

dependabot/github_actions/actions/upload-artifact-7.0.2

dependabot/npm_and_yarn/npm-minor-and-patch-d8d97ce6df

codex/kuna-1989

fix/8559-native-ui-fixture-ownership

fix/8555-go-verifier-mcp-ownership

codex/provider-capability-recovery

fix/8642-rizin-target-stdin

codex/ghidra-memory-effect-scope

codex/ghidra-annotation-entry-selector

codex/ghidra-readonly-recovery

codex/ghidra-regex-verifier-recovery

codex/evidence-discovery-view-guidance

fix/8545-bulk-append-overflow

fix/8428-navigation-refusal-alternatives

codex/address-context-recovery

codex/matching-member-limitations

codex/unknown-scope-contract

codex/evidence-view-guidance

feat/8373-native-trace-views

codex/ghidra-snapshot-verifier-binding

codex/elf-export-visibility

codex/evidence-view-recovery

codex/native-reference-cli-help

codex/provider-candidate-observation-scope

codex/kuna-session-verification

codex/ghidra-switch-lifetime-guidance

codex/pseudocode-paging-discovery

codex/clarify-evidence-view-support

codex/kuna-xrefs-selector-recovery

codex/context-capacity-recovery

codex/evidence-closure-large-links

codex/same-function-evidence-identity

codex/ghidra-verifier-inspected-jdk

codex/audit-guided-workflows

codex/crash-prompt-retained-dossiers

codex/analysis-view-error-recovery

codex/kuna-verifier-target-selection

codex/ghidra-selected-project-call-coverage

codex/docs-native-analysis-scope

codex/ghidra-java-socket-boundary

codex/ghidra-retained-snapshot-verifier

codex/ghidra-search-inventory-facts

fix/8284-zero-argument-parameter-bindings

fix/8198-ui-action-handler-offset

fix/8257-elf-entry-label-identity

fix/8304-deferred-output-schema-projection

fix/8277-call-path-computed-target-uncertainty

fix/pr-8089-conflicts

fix/ci-static-duplicate-export

dependabot/npm_and_yarn/lint-staged-17.6.0

dependabot/github_actions/actions/download-artifact-8.0.2

dependabot/npm_and_yarn/write-file-atomic-8.0.0

dependabot/npm_and_yarn/canonicalize-5.1.0

dependabot/github_actions/actions/cache/restore-6.1.0

dependabot/npm_and_yarn/toon-format/toon-4.4.0

dependabot/github_actions/actions/deploy-pages-5.0.1

codex/review-fixes-pr-2403

codex/review-fixes-pr-2400

codex/process-terminal-width

codex/test-brittleness-cleanup

verify/7167-browser-connect-macos

fix/7167-browser-connect

feat/native-matching-allowance-setting

feat/browser-scenario-dry-run

test/managed-caller-parameters-20261024

codex/parser-fortythird-boundaries

fix/6926-pinvoke-platform-decorations-20261023

fix/6889-har-body-encoding-20261023

fix/6888-sqlite-schema-budget-20261023

fix/dependency-security-gates-6708

cursor/evidence-overwrite-rebase-b4ac

feat/4057-verify-native-exports

fix/windows-acl-observer-overhead-20261022

cursor/erlang-beam-restack-4476

cursor/pe-certificate-review-bf32

fix/6116-javascript-application-fs-errors

fix/6061-unmapped-runtime-script-unknown

feat/browser-scenario-summary

fix/pe-certificates

codex/verify-3407

cursor/rebase-5699

cursor/rebase-5352

cursor/rebase-5600

cursor/fix-cli-schema-omission-10a8

codex/audit-hopper-shutdown-reasons-20261021

fix/demangle-swift-omitted-record

fix/nib-boolean-value-types

cursor/cancellation-partial-observation-a5ac

fix/ib-object-limit-reasons

fix/electron-fuse-limit-advice

fix/kuna-doctor-dangling-cache

fix/fixed-budget-refusal-advice

fix/js-ipc-listener-dedup

fix/js-return-member-provenance

fix/dmg-integrity-retry-advice

fix/ida-doctor-readiness

fix/kuna-version-probe-output-drain

fix/legacy-swift-runtime-name-matching

fix/dylib-lazy-load-commands

fix/browser-scenario-startup-cancel

fix/swift-nested-punycode-classification

fix/compare-unselected-scopes

fix/objc-method-budget-coverage

fix/dmg-mounted-root-observations

audit/ci-tests-20261019-round2

release/6.7.0

fix/wabt-cleanup-retry-resolution

fix/electron-fuse-elf-pe-architecture

fix/native-plist-descriptor-ownership

fix/kuna-caller-cleanup-ownership

experiment/atomic-codemode-20261016

review/first-contributor-3776

fix/call-resolution-full-read-cycles

fix/member-mutation-selection-repeat

experiment/atomic-re-tools-20261015

perf/member-mutation-lazy-origins

perf/static-network-mutation-index

fix/hopper-startup-lifecycle

audit/3050-windows-proof-20261015

feat/windows-window-capture-2183

audit/3049-windows-proof-20261015

audit/3735-macos-fixtures-20261015

fix/batch-decompile-null-pseudocode

fix/kuna-inventory-honors-jobs

experiment/browser-codemode-tool-design-20261015

fix/hopper-clean-runtime-argv

codex/review-2049-27f1b367

review-fixes/pr-2787-routing

fix/3360-scoped-this-emitters

fix/3367-replaced-global-effects

fix/3838-compact-any-value-items

test/hopper-download-probe-20261015

codex/windows-runtime-creation-red-green-20261015

codex/windows-readonly-root-red-green-20261015

codex/windows-root-share-red-green-20261015

codex/exp-1685-win-mcp-startup

codex/bug-sweep-20261015

investigate/2190-windows-package-phases

investigate/3543-macos-cli-deadline

perf/3281-reverse-tools-feedback-quality

fix/3406-hopper-doctor-fixture

fix/3341-wrapper-require-test-context

fix/3301-owned-uninstall-fixtures

fix/3164-compiler-input-ownership

fix/pcap-cleanup-stdout-newline-20261014

perf/interface-builder-summary

codex/review-fixes-pr-1977

fix/ghidra-effective-jvm-platform

fix/docs-turkish-rust-link-20261013

fix/main-maintenance-ci-20261010

fix/recover-binary-session-process-effects

codex/review-fixes-pr-2457

codex/ci-required-cancellation-gate

fix/main-format-baseline-20261013

fix/setup-preserve-entry-fields

cursor/restore-main-checks-1ffc

fix/ghidra-bridge-hashmap-import

codex/shared-ci-jadx-json-default-20261013

codex/shared-ci-ghidra-test-groups-20261013

codex/shared-ci-java-fixture-format-20261013

codex/fix-intrinsic-invocation-boundaries

test/release-preflight-reusable-jobs

test/js-parameter-provenance-expectation

fix/linux-hopper-verification-current

test/2419-ghidra-elf-probe-size

followup/pr-1544-native-ida

codex/fold-pr-2230-contribution

docs/readme-responsible-use

fix/issue-2064

fix/issue-2050

fix/issue-2053

fix/issue-1968

fix/issue-1945

experiment/codemode-bridge-20261011

fix/tool-effects-negative-wording-1904-20261012

fix/1842-electron-interop-provenance

feat/recover-javascript-multi-input

refactor/website-i18n-prep

fix/nativeaot-pe-virtual-extent

fix/browser-verifier-ci-hang

fix/pe-resources-input-selection

docs/beginner-friendly-guides

docs/beginner-setup-guide

fix/javascript-analysis-worker-1563

fix/1649-ghidra-duplicate-names

fix/javascript-export-keys-integration-1369

test/maintenance-boundary-contracts-20261011

review/javascript-export-keys-1369

review/process-live-progress-1483

test/javascript-1495-growth-ratio

fix/ci-escape-timing

docs/normalized-terminal-geometry-1450

release/6.3.0

archive/release-6.3.0-pr1381

release/6.2.0

fix/electron-preload-dynamic-override

fix/javascript-self-referential-bundler-edges

release/6.1.0

cursor/grok-client-cherry-pick-0b56

feat/signature-posture

feat/dyld-shared-cache

feat/artifact-integrity-policy

feat/pkg-inventory

release/6.0.0

chore/sync-release-5.0.0

release/5.0.0

cursor/cloud-agent-node-787e

fix/javascript-xhr-open-endpoints

review/pr-711-realpath-fallback-wording

cleanup/replay-confinement

codex/test-suite-performance

codex/issue-foundations

codex/address-open-issues-2026-07-20

agent/javascript-vite-rollup-esbuild-adapters

agent/process-cleanup

agent/triage-integration

agent/unknown-commands-registry

feat/mcp-identity-metadata

morlvps/issue_cleanup

codex/installer-redesign

morl/roadmap-investigation-core

morl/roadmap-investigation-docs

release-please--branches--main--components--rea

rea-agents-6.8.0

rea-agents-6.7.0

rea-agents-6.6.0

experiment/atomic-codemode-wait-runtime-20261016

rea-agents-6.5.0

rea-agents-6.4.0

rea-agents-6.3.0

rea-agents-6.2.0

rea-agents-6.1.0

rea-agents-6.0.0

rea-agents-5.0.0

rea-agents-4.1.0

rea-agents-4.0.1

rea-agents-4.0.0

rea-agents-3.2.1

rea-agents-3.2.0

rea-agents-3.1.0

rea-agents-3.0.0

rea-agents-2.7.0

rea-agents-2.6.0

rea-agents-2.5.1

rea-agents-2.5.0

rea-agents-2.4.0

rea-agents-2.3.0

rea-agents-2.2.0

rea-agents-2.1.0

rea-agents-2.0.0

rea-agents-1.7.0

rea-agents-1.6.0

rea-agents-1.5.0

rea-agents-1.4.0

rea-agents-1.3.0

rea-agents-1.2.0

rea-agents-1.1.0

rea-agents-1.0.0

rea-agents-0.5.0

rea-agents-0.4.0

rea-agents-0.3.0

rea-0.2.1

rea-0.2.0

Labels

Clear labels

Mirrored from GitHub Pull Request

No labels

Milestone

Clear milestone

No items

No milestone

Projects

Clear projects

No items

No project

Assignees

Clear assignees

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

morluto/rea#3076

Reference in a new issue

Repository

morluto/rea

Title

Body

No description provided.

Delete branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?

Rows
Columns