Endogenous Interpretation Semantic Deobfuscation as Architecture-Constrained Recovery of Factored Transition Models Antonio Nappa ACM
arXiv:2609.23514v1 [cs.CR] 20 Sep 2026
September 2026 — working paper, v2 Abstract We propose endogenous interpretation as a viewpoint on executable programs: relative to a host substrate, program, interpreter, and emulated machine are parameters of one transition relation rather than disjoint semantic objects. Each executable representation carries an implicit constraint bias, the structural restrictions imposed by its instruction basis, state encoding, control transfers, and finite substrate. Under this viewpoint a transformation that preserves a chosen observable behaviour does not remove the computation that produces it; it redistributes that computation over another state space and encoding, which we call semantic diffusion. Semantic deobfuscation—a sub-problem of reverse engineering, distinct from the recovery of provenance such as types, names, and intent—is then the recovery of a low-complexity representative of the behavioural equivalence class under a chosen observation model. We give two formal instances and keep them separate. For an explicitly given finite-state realization, contraction under branching bisimilarity is canonical and computable by partition refinement, and this extends to trace equivalence when both the realization and the contraction are required to be deterministic; if the analyst admits nondeterministic contractions, minimal contraction under trace equivalence is PSPACE-hard again. The tractability boundary is thus set by the observation model and the hypothesis class, not by the transformation. For inference from executions, where the analyst holds concrete traces rather than the transition system, we pose deobfuscation as minimum-description-length recovery of a factored transition model—a dependency hypergraph with local transition functions—over an architectureconstrained family of factorizations. The number of nonzeros of the transition tensor is invariant under all such reshapings; what obfuscation inflates is the factored description length and the size of the version space of consistent factorizations. We catalogue the sources of that ambiguity (gauge, coverage, dependency, role, granularity, level, and observation-model ambiguity), relate each standard protection to the ambiguity it induces, and state four independent falsifiable experiments. Factored transition models and MDL structure recovery are established; the contribution claimed is their connection to binary semantics, virtualization, and code reuse through an architecture-aware hypothesis class in which program and interpreter roles are recovered as part of the structure.
1
Introduction
1.1
Endogenous interpretation and implicit constraint bias
An executable substrate can induce further executable languages from its own available state transformers. An instruction set, an interpreter, a virtual machine, or a code-reuse gadget set may each provide a basis from which programs are formed. Relative to a fixed host, the distinction among “program,” “interpreter,” and “emulated machine” depends on which parameters of the host’s transition relation are held fixed; we call this endogenous interpretation. Every such representation is constrained. Its instruction vocabulary, state layout, addressing rules, control transfers, calling conventions, decoder, and finite implementation restrict the space of realizable descriptions. We call the resulting structural preference an implicit constraint bias. It is not a heuristic imposed by the analyst; it is carried by the executable representation, because a transformed program must respect the constraints of some substrate in order to run. The working conjecture of this note is that semantic deobfuscation succeeds in practice partly because these constraints restrict the otherwise enormous space of factorizations the analyst must consider. 1
1.2
Vocabulary: O-semantics, provenance, and which gap
Throughout, “semantics” means observable behaviour under a chosen observation model O, written O-semantics. A transformation is O-preserving if it preserves that behaviour. This is the sense in which compiler-correctness results are stated [28]: preservation of a chosen set of observable traces, not of every internal operational fact. Ordinary compilers and obfuscators preserve I/O behaviour and do not preserve intermediate states, evaluation order, or memory layout; we never claim they preserve “operational semantics in full.” Two different “semantic gaps” appear in the literature. In virtual-machine introspection the phrase names the distance between raw guest memory and operating-system abstractions [15, 22]. In decompilation it names the distance between machine code and source-level meaning. We are concerned with the latter, which we call the decompilation gap. Within the decompilation gap, two things are lost at once. Compilation and obfuscation genuinely destroy provenance: source identifiers, types, data-structure boundaries, module structure, invariants, intent. Recovering provenance is a large part of reverse engineering and is not the subject of this note. What a transformation cannot destroy, if the result is to execute, is the structure needed to reproduce the O-observable behaviour. We distinguish provenance loss ̸= O-semantic loss, and confine the theory to the second.
1.3
Scope: semantic deobfuscation, not reverse engineering
Reverse engineering recovers types, protocols, algorithms, vulnerabilities, design decisions, and intent, most of which are provenance. The problem this note models is narrower: semantic deobfuscation = recovery of a low-complexity representative of [P ]O under a chosen O. Semantic deobfuscation is a prerequisite for much provenance recovery (one cannot type what one cannot read), but it is not the whole task, and no claim here should be read as one about reverse engineering in general.
1.4
Contributions
1. A vocabulary (endogenous interpretation, implicit constraint bias, semantic diffusion, semantic contraction) under which compilation, interpreter towers, virtualization, and code-reuse computation appear as refactorizations of one host transition relation (§3–4). 2. For explicitly given finite-state realizations: canonical contraction under branching bisimilarity; its extension to trace equivalence under a deterministic hypothesis class; the return of PSPACE-hardness when nondeterministic contractions are admitted; and a submultiplicativity law for kernel size under parallel composition (§5). These are classical results assembled into a statement about where the tractability boundary lies. 3. For inference from executions: a formulation of semantic deobfuscation as MDL recovery of a factored transition model over an architecture-constrained family, with a proper description length; a lemma that transition-tensor sparsity is invariant under reshaping, so that factored description length, not sparsity, is the object of study (§6). 4. A catalogue of the sources of ambiguity in factorization recovery, a definition of identifiability relative to a trace set, and a map from standard protections to the ambiguity each induces (§7). 5. Four independent falsifiable experiments, stated as multi-trace or active-query problems (§8).
2
Preliminaries
A machine is a labelled transition system (LTS) M = (Q, Σ, −→, q0 ) with −→ ⊆ Q × Σ × Q; Reach(M ) is the set of states reachable from q0 , and we identify M with its reachable part. An observation model is a map πO : Tr(M ) → O on traces; M1 ≈O M2 when the images agree. Three models recur [31]: trace equivalence ≡tr , strong and branching bisimilarity ∼, and I/O equivalence. T is O-preserving when T (M ) ≈O M ; [M ]O is the equivalence class.
2
Lemma 1 (observation preservation). If T is O-preserving then [T (M )]O = [M ]O . Consequently T cannot remove information required to reproduce the O-observable behaviour; it may remove any information outside O, including information relevant to other reverse-engineering objectives. The lemma is immediate from the definitions and is stated only to fix what follows from O-preservation and what does not. It does not say that reverse engineering faces no informational obstacle: under a coarse O, much of what a reverse engineer wants is outside O and may be gone. Two problems must be kept apart throughout: explicit-model contraction ̸= model inference from executions. In the first (§5) the analyst is given M and asks for a smaller O-equivalent system. In the second (§6) the analyst holds finitely many concrete traces of M and must infer a model. Visibility of internal state settles aliasing in the second problem but says nothing about coverage; results about the first do not transfer to the second without an identifiability argument.
3
Endogenous interpretation
3.1
One transition function, many representations
For Q = Fn2 a deterministic step is F : Q → Q, representable as a transition table, as a vector of Boolean polynomials in algebraic normal form (the representation in which mixed Boolean–arithmetic obfuscation and its defeat live [42, 12]), or as a 2n × 2n one-hot transition matrix. These are standard; they motivate treating the transition function as the semantic object and instruction streams, bytecodes, polynomials, and matrices as its representations. The one-hot matrix is also a first example that representation cost is not intrinsic: it describes the same F exponentially more verbosely.
3.2
Universal hosts and the three roles
Let H be a host substrate with transition relation ∆H on host states SH . A universal evaluator on H is written UH : E × P × Q → Q, where e ∈ E encodes an evaluator (an interpreter, an emulated machine description, a specializer), p ∈ P a program for that evaluator, and q ∈ Q the evaluator’s own state, all three carried as data within SH . Fixing e gives the evaluator’s transition relation; fixing (e, p) gives the machine that program induces. The slogan “program, interpreter, and machine are parameters of one relation” is true relative to H: the host’s own semantics is ∆H itself, not a parameter of UH . This relativity is what “endogenous” means, and the Futamura projections [14, 24] are the classical statement that the parameters of UH can be traded against one another by a specializer.
3.3
Interpretation flattening
If P is run by interpreter I1 , itself run by I2 , the complete host state is a reachable subset of SI2 × SI1 × SP with one transition relation ∆. Proposition 2 (finite interpreter flattening). Any finite tower of effective interpreters is one effective transition system over a reachable subset of the product of their states, and simulations between adjacent levels compose. Interpreter depth therefore need not imply irreducible semantic depth, consistent with the derivation of virtual machines from interpreters [1] and with specialization removing an interpretation layer [24]; Giacobazzi, Jones, and Mastroeni run the same construction backwards, obtaining obfuscators by specializing distorted interpreters [17]. The flattened ∆ is not a synchronous product of level relations, which matters for composition (§5.1).
3
3.4
Endogenous machines
An executable image B induces reusable state transformers Γ(B) = {g1 , . . . , gm } and, with a sequencing convention, a transformation monoid ⟨Γ(B), ◦, id⟩; a chain of gadget addresses denotes a composition. Roemer et al. construct Turing-complete gadget sets and compile a high-level language to chains [36]. Virtualization obfuscators [37, 26] are the same construction with handlers for gadgets and a dispatcher for the sequencing convention. We call such a construction an endogenous machine: the substrate’s own transformers form the instruction basis of a further language on the same substrate.
4
Diffusion and contraction
An original transition qi → qj may be realized in a transformed system as a path r0 ⇒ · · · ⇒ rk , related by an abstraction α : Q′ → Q with α(∆′∗ (r)) = ∆(α(r)). Definition 3 (diffusion, contraction). An O-preserving T is a diffusion with respect to a representation cost c κ when κ(T (M )) > κ(M ). A contraction is a quotient, projection, synthesis, or refactorization C : M ′ 7→ M ′ ′ c c with M ≈O M and κ(M ) < κ(M ). Obfuscation replaces a factorization F = gk ◦ · · · ◦ g1 by F = hm ◦ · · · ◦ h1 with m ≫ k, possibly over an extended state space, preserving the induced computation while making the factorization harder to recognize. Existing deobfuscation work exploits instances of this: emulation-based simplification [41], synthesis of small equivalents from I/O samples [5, 10], trace-informed control-flow synthesis [29], and abstract-interpretation models of what obfuscation hides [9]. The question is whether these admit a common quantitative model. Under composition the O-preserving transformations form a monoid; a diffusion and a contraction are typically a section/retraction pair (C ◦ D = id on the semantic side, D ◦ C = ̸ id on the richer side), and a canonical normalization N with N 2 = N , N ◦ T = N is expected only property-relative or on restricted classes. §5 exhibits one. Execution witness. If P (x) ⇓ y and T preserves terminating behaviour then T (P )(x) ⇓ y, so a finite target trace witnesses the result. The elementary consequence is the separation of a per-step execution cost Cexec from a recognition cost Crecognize ; obfuscation may inflate the latter while the former stays linear in trace length. The two are not directly comparable quantities and we make no complexity-class claim from their separation alone. The witness argument applies to the artifact as executed; environment-keyed code [39], split execution, and hardware-bound execution place part of the computation outside the artifact, and the substrate must then be taken to include the environment.
5
Explicit-model contraction
Here the analyst is given a finite LTS M explicitly. Theorem 4 (canonical kernel). Let ∼ be branching bisimilarity and M ↓ = M/∼. Then M ↓ ∼ M ; M ↓ has the fewest states of any LTS branching bisimilar to M and is unique up to isomorphism among minimal ones; and M ↓ is computable in O(m log n) for n = | Reach(M )|, m transitions [19, 20] (for strong bisimilarity, [34, 25]). Branching rather than strong bisimilarity is required because inserting an internal step changes the strong bisimulation class; branching bisimilarity absorbs inserted internal computation while preserving branching structure visible in Σ. Definition 5 (diffusion ratio). δ(M ) = | Reach(M )|/|M ↓ | ≥ 1; for T with T (M ) ∼ M , δ(T ; M ) = δ(T (M ))/δ(M ). δ is invariant under the choice of abstraction onto a minimal bisimilar system, and N (M ) = M ↓ is a canonical normalization in the sense of §4. “Computable in O(m log n)” is relative to the explicit reachable state count, which is exponential in state bits; the theorem locates where difficulty is not, it does not say contraction is cheap.
4
Proposition 6 (deterministic hypothesis class). If M1 and M2 are deterministic then M1 ≡tr M2 iff M1 ∼ M2 . Consequently the smallest deterministic LTS trace-equivalent to a deterministic M is M ↓ , computable in O(n log n) [21]. Proposition 7 (nondeterministic contractions restore hardness). For deterministic M and k, deciding whether some LTS with at most k states (nondeterminism allowed) is trace-equivalent to M is PSPACE-complete [23]; the minimal such LTS is in general not unique and may be exponentially smaller than M ↓ . Trace languages here are prefix-closed, and minimization remains hard in that setting. Propositions 6 and 7 concern the same M . What changes is the hypothesis class the analyst admits for the contraction: canonical and cheap within deterministic contractions, hard as soon as nondeterministic ones are allowed, even though execution itself is deterministic. Determinism of execution does not by itself make contraction easy; restricting the class of contractions does. Theorem 8 (hardness under traces). For finite nondeterministic LTSs, deciding ≡tr is PSPACE-complete [30, 25], and minimal trace-equivalent LTSs are neither unique nor efficiently computable unless P = PSPACE. Nondeterminism of the observed system arises when the observation model hides state: erasing registers, memory, or internal labels merges distinct concrete states under one observable and the projection may become nondeterministic. Together with Proposition 7, the boundary between the tractable and intractable regimes is set on both sides by choices the analyst makes—what to observe and what contractions to admit—not by the transformation. This is the explicit-model form of the constraint-bias conjecture: the substrate keeps the concrete system deterministic; hardness enters when that structure is discarded or when the analyst’s hypothesis class outruns it.
5.1
Composition
Proposition 9 (submultiplicativity of kernel size). For synchronous parallel composition ⊗ [31], |(M1 ⊗ M2 )↓ | ≤ |M1↓ | · |M2↓ |, since bisimilarity is a congruence for ⊗ and ·↓ is minimal. The inequality can be strict. When the product is fully reachable this gives δ(M1 ⊗ M2 ) ≥ δ(M1 )δ(M2 ), i.e. δ is supermultiplicative and log δ superadditive in that case. The flattened relation of an interpreter tower is not a synchronous product, so no bound for towers follows; whether one exists is open (§10).
6
Inference from executions: factored transition models
Here the analyst is not given M . They hold a finite set of concrete traces T = {τ1 , . . . , τr }, each τ = (q0 , . . . , qm ) a sequence of full host states from an emulator or hardware tracer, and must infer a model. Visibility of the full state means no two distinct visited states are confused (aliasing is solved); it does not mean every state or transition has been visited (coverage is not).
6.1
The transition tensor and the invariance of sparsity n
n
Write U ∈ {0, 1}2 ×2 , U [q, q ′ ] = 1 iff q → q ′ , and consider reindexings of U by bit permutations, regroupings of bits into factors, and per-factor recodings. Lemma 10 (sparsity is shape-invariant). For a total deterministic F , nnz(U ) = 2n , and every permutation, regrouping, reshaping, or bijective recoding of U preserves nnz. Sparsity of the transition tensor therefore cannot measure diffusion and is not what obfuscation changes. What changes is the factored description: how compactly F can be written as a collection of local functions on small parent sets. That is the object of the rest of this section, and it is exactly the object of factored transition models in planning and probabilistic inference [6, 11], where enormous transition spaces are represented by dynamic Bayesian networks with small parent sets. The tensor picture is retained only as intuition.
5
6.2
Factorizations
Definition 11 (factorization). A factorization σ = (π, φ, ρ, D) of F consists of (i) a partition π = {B1 , . . . , Bk } of the n state bits into factors; |B | (ii) a recoding φ = (φj ), each φj a bijection on F2 j from an admissible family Φ; (iii) a role ρ(Bj ) ∈ {fixed, state} per factor; (iv) a dependency hypergraph D = (Dj ): for each state factor Bj , a set of parents, each either a whole factor (direct) or an indexed window B[S]w of width w into a factor B at an address held in a state factor S. width(D )
|B |
j σ represents F if there are local functions fj : F2 → F2 j with φj (F (q)|Bj ) = fj (φ(q)|Dj ) for all reachable q, and fixed factors are constant on reachable states.
The “interpreter” of a factorization is a derived notion: a factor whose value selects the window another factor reads (a dispatcher, a virtual program counter). Indexed windows are what make an interpreter expressible: the handler chosen by the opcode at the virtual PC depends on bytecode[vpc]8 , not on the whole array. Proposition 12 (slicing as extensional specialization). Fixing the fixed factors of a factorization at a value p yields the transition relation of a machine on the state factors alone. If a state factor is constant on every execution of that machine, it may be moved into the fixed factors and the slice taken again. This is the extensional analogue of fixing the static argument in the first Futamura projection: it exhibits the specialized semantics but does not construct a residual program, which requires a specializer as in §3.2.
6.3
Consistency with a trace set
Definition 13 (consistency). σ |= T if (a) every fixed factor is constant on all states in T and is a parent of some state factor; and (b) for each state factor Bj , the observed pairs φ(qi )|Dj , φj (qi+1 )|Bj over all consecutive (qi , qi+1 ) in T define a partial function, i.e. contain no conflicting entries. Checking consistency is one pass over T with hash lookups. A trace set can only refute a factorization: consistency establishes that the local tables observed so far are functional, not that they are complete or that the parent sets are minimal.
6.4
Description length
Definition 14 (description length). For σ |= T , κ(σ; T ) = ℓ(π, ρ, D) + ℓ(φ) +
X
ℓ(fj ) +
j: ρ(Bj )=state
X
|Bj | + ℓ(T | σ),
j: ρ(Bj )=fixed
where ℓ(π, ρ, D) is the code length of the structure under a fixed prefix code over Σadm , ℓ(φ) that of the recodings under a fixed encoding of Φ, ℓ(fj ) the length of the local function (as a table, |Bj | · 2width(Dj ) ; or as a decision diagram or ANF when smaller), and ℓ(T | σ) the length of the traces given the model, which is zero for the deterministic, exactly consistent case except for the initial states. Charging for π, ρ, and D is essential: they are the objects searched over, and a cost that omits them lets the optimizer acquire structural complexity for free. Indexed windows are charged for the window width, not for the array read, since otherwise the cost model penalizes by 2|bytecode| exactly the interpreter structure to be recovered. Definition 15 (semantic deobfuscation as factorization recovery). Given an admissible family Σadm and a trace set T , σ ⋆ (T ) = arg min κ(σ; T ). σ∈Σadm , σ|=T
This is MDL structure learning [35] of a factored transition model from trajectories. That problem is established for Boolean and dynamical networks [2, 27, 13]; what is specific here is the hypothesis class and what is recovered from it.
6
Definition 16 (admissible factorizations). Σadm is generated by the substrate’s own boundaries: each architectural register and architecturally named sub-register, each flag, each stack slot, and each contiguous memory region touched in T is a candidate atomic factor; factors may be merged; recodings are drawn from a small family (identity, affine over F2 , byte permutations); parent sets are direct factors or indexed windows whose address factor is a register or slot. Factorizations that cut an architectural unit at a non-architectural boundary are excluded. This is the constraint-bias conjecture made operational: the analyst does not search over all factorizations of F —partitions alone are counted by the Bell number Bn —but over those the machine could have executed, and the conjecture is that Σadm is small enough that σ ⋆ can be found where the unrestricted problem cannot. Whether it is small enough is empirical (§8). Scope. The conjecture is about substrate-constrained protections: virtualization, flattening, arithmetic encoding, code reuse. It excludes cryptographic obfuscation. An indistinguishability-obfuscated program with an embedded pseudorandom-function key [16] preserves [P ]O yet admits no efficient recovery of a small equivalent without breaking the PRF; an obfuscated point function is a password hash. There a compact factorization exists but is hidden by a hardness assumption, not by the combinatorics of Σadm , and factorization recovery must fail. What visibility buys. Because each visited state is fully visible, the sub-LTS induced by T is recovered exactly: no two distinct visited states are merged by observation, and Proposition 6 applies to that sub-LTS within a deterministic hypothesis class. What visibility does not buy is coverage: from T the analyst knows one successor for each visited state and nothing about untaken branches. Every claim in this section is therefore relative to T , and the gap between T and M is the subject of the next section.
7
Ambiguity
The set of factorizations consistent with T is a version space. This section says what makes it large, how to count it, what obfuscation does to it, and when it collapses.
7.1
Counting
Two factorizations are gauge-equivalent, σ ∼ = σ ′ , if they differ only by relabelling factors, permuting bits within a factor together with the corresponding change of φ, or composing φ with a bijection that leaves every local function’s table unchanged up to relabelling. Gauge-equivalent factorizations represent the same model and must not be counted separately. Definition 17 (version space, ambiguity). V (T ) = {[σ]∼ = : σ ∈ Σadm , σ |= T } and A(T ) = |V (T )|. For a prefix length k applied to every trace, AT (k) = |V (T≤k )|, non-increasing in k. A is a version-space size. It is not a lower bound on the running time of any recovery procedure: SAT, constraint propagation, and branch-and-bound eliminate exponentially many members at once, and a runtime bound would require a query or comparison model that this note does not supply. A measures how underdetermined the model is by the data, which is a property of the data and the hypothesis class, not of the algorithm. Definition 18 (identifiability). F is identifiable from T within Σadm if V (T ) contains a unique class of minimal κ, and recoverable if in addition that class represents F on all of Reach(M ), not only on the states in T. Identifiability is about the data singling out a model; recoverability adds that the model is right where the data did not look. The second requires an argument about coverage that consistency alone cannot give.
7.2
Sources of ambiguity
The following are the ways V (T ) can contain more than one class. They are distinct, they compound, and different protections exploit different ones. 7
(A1) Gauge ambiguity. Relabellings and recodings that leave the model unchanged. Removed by counting classes rather than factorizations. Not a real ambiguity, but a common source of over-counting in a naive A. (A2) Coverage ambiguity. States and transitions not in T . Every factorization consistent with T is free on the unvisited part, so V (T ) contains classes that agree on T and disagree elsewhere. This is the ambiguity that traces alone cannot remove and that additional traces or active queries (chosen inputs, forced branches) reduce. It is the reason a single trace cannot recover a control-flow graph whose branches it did not take. (A3) Dependency ambiguity. Several parent sets Dj consistent with T for the same factor. On short traces a factor may appear to depend on bits that are merely correlated with its true parents; conversely a true parent whose value never varied in T is invisible. MDL prefers the smallest consistent parent set, which is correct only if T is long enough to have exercised the true parents. (A4) Role ambiguity. A factor that is constant on T may be fixed (program, table) or a state factor that happened not to change. Requiring fixed factors to be read (Definition 13) removes untouched constants but not a variable that was read and never written in T . Role ambiguity is resolved by a write in some trace, or left open with the fixed reading preferred by κ. (A5) Granularity ambiguity. Two factorizations with equal κ that differ by merging or splitting factors. MDL ties are real ties: the data do not distinguish a two-factor model from a merged one when the local functions have the same total length. Ties should be reported, not broken arbitrarily. (A6) Level ambiguity. In an interpreter tower, a bytecode array may be read as the program of the interpreter (fixed) or as data of the flattened machine (state that is read and never written). Both are consistent and both represent F ; they differ in which slice of UH the analyst is looking at (§3.2). This is not an error but the endogenous-interpretation phenomenon itself: the level at which a computation is “the program” is a choice of fixed parameters, and V (T ) contains one class per admissible choice. κ prefers the choice with the shortest total description, which for a virtualized function is the one that isolates the interpreter. (A7) Observation-model ambiguity. Different O give different equivalence classes and hence different σ ⋆ . A factorization minimal under I/O equivalence may drop factors that a finer O (timing, memory traffic) requires. This ambiguity is not in V (T ) but above it: it is the analyst’s choice of what counts as behaviour, and it must be fixed before V is defined.
7.3
What protections do to the version space
Each standard protection increases one or more of these ambiguities, and this gives a more discriminating description of a protection than “increases complexity.” Protection
Primary ambiguity
Mechanism
Virtualization Control-flow flattening Mixed Boolean–arithmetic Opaque predicates Code reuse (ROP) Junk / dead code Environment keying
A6, A4 A3 A1→A3 A2 A4, A6 A3, A5 A2
program becomes read-only data of a new level next-state depends on a dispatcher variable recoding makes true parents look wider branches never taken remain consistent stack becomes the program of an induced machine spurious parents and factors with no effect coverage impossible without the key
The map is a hypothesis about mechanism, not a result; it predicts, for instance, that flattening should be undone by longer traces (A3 shrinks with data) while opaque predicates should not (A2 does not shrink without active queries), and that virtualization should be undone by a change of level rather than by more data. Those predictions are testable.
8
7.4
When the version space collapses
V (T ) collapses to one class when T is rich enough that every true parent has varied, every reachable branch has been taken, every factor has been written if it is state, and Σadm excludes the gauge alternatives. The sample complexity of that collapse—how many traces, of what length, chosen how—is the identifiability question proper, and it is the theorem this framework should eventually contain. For the deterministic finite-state case there is an active-learning baseline: Angluin’s L∗ [3] learns the minimal automaton with polynomially many membership and equivalence queries, and a factored-model analogue with architecture-constrained hypotheses would be the natural target. We do not have that result; we state it as the open problem the rest of the paper points at.
8
Proposed evaluation
The formulation predicts, for each protection, which factorization σ ⋆ should recover and which ambiguity must be reduced to get there. The experiments below test that on independent axes: partition (E1, E2), recoding (E3), role (E4). Each is stated as a multi-trace or active-query problem, with a falsification criterion. Common pipeline: compile a small function; protect it; record full-state traces in an emulator for a chosen input set; enumerate Σadm ; compute σ ⋆ (T ) by branch-and-bound on κ; compare with the ground-truth structure of the unprotected build; report AT (k) for protected and clean builds. E1: Virtualization (partition, level). Tigress Virtualize [40] with a table dispatcher; inputs chosen to exercise every handler at least once (checked against the unprotected build). Prediction. σ ⋆ places the bytecode in a fixed factor, the virtual PC and virtual registers in state factors, and the native handler PC in a state factor with the single parent bytecode[vpc]8 ; slicing away the fixed factors yields a machine on the virtual registers whose kernel is branching bisimilar to the kernel of the unprotected function on the covered states. Falsified if the MDL-optimal admissible factorization does not isolate the handler table, or if a handler exercised in T is not recovered. Baseline. Syntia [5], QSynth [10]. E2: Control-flow flattening (dependency). Tigress Flatten or O-LLVM -fla [33]; inputs chosen to cover every original edge, or active queries forcing the untaken ones. Prediction. σ ⋆ isolates the dispatcher variable as a state factor whose local function, on the covered edges, has the original control-flow graph as its graph. Falsified if MDL merges the dispatcher with data, or if the recovered graph is not isomorphic to the covered part of the original CFG. Also measure how AT (k) falls with added traces (the A3 prediction). Baseline. Mariano et al. [29]. E3: Mixed Boolean–arithmetic (recoding). Tigress EncodeArithmetic or the identities of Zhou et al. [42]; π trivial, search over φ ∈ Φ affine plus bit-slicing. Prediction. σ ⋆ is a recoding under which the local function’s ANF has degree ≤ 2, recovering the original operator. Falsified if no admissible recoding lowers the degree, which would mean the identity is not a change of basis within Φ—a finding about Φ, to be reported as such. Baseline. Eyrolles et al. [12]. E4: Return-oriented chain (role, level). A small function compiled to a chain against a fixed binary [36]. Prediction. σ ⋆ assigns the chain region the fixed role, the stack pointer a state role with itself as parent, and the instruction pointer a state role with parent stack[sp]64 , i.e. the chain is recognized as a program and gadget addresses as its opcodes. Falsified if the chain region is not assigned the fixed role or the sliced machine is not bisimilar to the original on covered states. Failure of the approach. The approach is refuted, not merely incomplete, if in any of E1–E4 the MDLoptimal factorization within Σadm fails to coincide with ground truth on the covered part while a factorization outside Σadm does: that would falsify the constraint-bias conjecture directly. Failure due to coverage (A2) is not a refutation of the approach but a measurement of sample complexity, and must be reported separately.
9
9
Related work
Cryptographic obfuscation. Barak et al. [4] construct function families with a predicate efficiently recoverable from any implementation but not from oracle access, showing virtual-black-box obfuscation impossible in general. Indistinguishability obfuscation [16] guarantees computational indistinguishability of obfuscations of functionally equivalent circuits; best-possible obfuscation [18] reveals no more than any equivalent program does. Lemma 1 is consistent with these results and says nothing beyond them; cryptographic obfuscation is outside the scope of §6. Semantics-based obfuscation and deobfuscation. Collberg et al. [7] introduced the potency/resilience/cost vocabulary. Dalla Preda and Giacobazzi model obfuscation as incompleteness of an abstract interpretation [9, 8]; Giacobazzi, Jones, and Mastroeni obtain obfuscators by specializing distorted interpreters [17], the closest prior work to §3.3. Schrittwieser et al. survey the arms race [38]; Ollivier et al. give an analyzer-relative potency measure [32]. On the recovery side, Rolles [37] and Kinder [26] treat VM obfuscators as machines to be modelled; Yadegari et al. [41] simplify from traces; Syntia [5] and QSynth [10] synthesize from I/O; Mariano et al. [29] synthesize control flow; Eyrolles et al. [12] normalize MBA. Each is a contraction under some O. Factored transition models and structure learning. Dynamic Bayesian networks [11] and factored MDPs [6] represent large transition systems by local functions with small parent sets; learning their structure from time series is established for DBNs [13] and for Boolean networks [2, 27], with MDL as a standard criterion [35]. Angluin’s L∗ [3] learns minimal automata from queries. §6 is an instance of this literature; the claimed novelty is the architecture-constrained hypothesis class, the recovery of program and interpreter roles as structure, and the connection to protections on binaries. Interpreters, partial evaluation, code reuse. Futamura [14], Jones et al. [24], Ager et al. [1], and Roemer et al. [36] supply the established ingredients of endogenous interpretation. The semantic gap of virtual-machine introspection [15, 22] is a recognition problem over a complete artifact and is in that respect closer to this note than the decompilation usage. Equivalence and minimization. Paige–Tarjan [34], Kanellakis–Smolka [25], Groote–Vaandrager [19] and Groote et al. [20] for bisimulation quotients; Hopcroft [21] for DFA minimization; Meyer–Stockmeyer [30] and Jiang–Ravikumar [23] for the PSPACE results; Milner [31] for the spectrum of equivalences.
10
Established, proposed, open
Established. Universal interpretation and specialization; simulation and bisimulation; derivation of VMs from interpreters; O-preserving transformations; abstract-interpretation models of obfuscation; semantic deobfuscation and synthesis; code-reuse computation; finite-state minimization and its complexity; factored transition models and MDL structure learning. Proposed. Endogenous interpretation as a viewpoint; semantic diffusion in place of the gap metaphor for O-semantics; the tractability boundary of explicit-model contraction as a function of observation model and hypothesis class; semantic deobfuscation as architecture-constrained factorization recovery with a proper description length; the ambiguity catalogue and the protection-to-ambiguity map. Open. 1. Identifiability: a sample-complexity result for factorization recovery within Σadm , in a passive or active model, in the style of L∗ for the factored, architecture-constrained class. This is the theorem the framework needs. 2. Whether a composition bound holds for interpreter towers, where the flattened relation is not a synchronous product. 3. Where in the equivalence spectrum between branching bisimilarity and trace equivalence the cost of contraction jumps, and which deobfuscation technique’s observation model sits where. 10
4. Whether Σadm for a real ISA admits exact search or only greedy search, and which protections defeat the greedy variant. 5. Whether the protection-to-ambiguity map predicts, on E1–E4, which interventions (more traces, active queries, change of level) reduce AT for which protection. Thesis. Under a chosen observation model, an O-preserving transformation redistributes rather than removes the computation that produces the observable behaviour. For explicitly given finite-state realizations the cost of contracting it is set by the observation model and the admitted hypothesis class, not by the transformation. For realizations known only through executions, semantic deobfuscation is the recovery of a compact factored transition model over the factorizations the substrate could have executed; protections act by enlarging the version space of consistent factorizations, and the kind of ambiguity they induce determines what reduces it.
References [1] M. S. Ager, D. Biernacki, O. Danvy, and J. Midtgaard. From Interpreter to Compiler and Virtual Machine: A Functional Derivation. BRICS Report Series, RS-03-14, 2003. [2] T. Akutsu, S. Miyano, and S. Kuhara. Identification of Genetic Networks from a Small Number of Gene Expression Patterns under the Boolean Network Model. In Pacific Symposium on Biocomputing, 1999. [3] D. Angluin. Learning Regular Sets from Queries and Counterexamples. Information and Computation, 75(2):87–106, 1987. [4] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, and K. Yang. On the (Im)possibility of Obfuscating Programs. In CRYPTO, 2001. [5] T. Blazytko, M. Contag, C. Aschermann, and T. Holz. Syntia: Synthesizing the Semantics of Obfuscated Code. In USENIX Security Symposium, 2017. [6] C. Boutilier, T. Dean, and S. Hanks. Decision-Theoretic Planning: Structural Assumptions and Computational Leverage. Journal of Artificial Intelligence Research, 11:1–94, 1999. [7] C. Collberg, C. Thomborson, and D. Low. A Taxonomy of Obfuscating Transformations. Technical Report 148, University of Auckland, 1997. [8] P. Cousot and R. Cousot. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In POPL, 1977. [9] M. Dalla Preda and R. Giacobazzi. Semantics-based code obfuscation by abstract interpretation. Journal of Computer Security, 17(6):855–908, 2009. [10] R. David, L. Coniglio, and M. Ceccato. QSynth: A Program Synthesis based Approach for Binary Code Deobfuscation. In Workshop on Binary Analysis Research (BAR), NDSS, 2020. [11] T. Dean and K. Kanazawa. A Model for Reasoning about Persistence and Causation. Computational Intelligence, 5(3):142–150, 1989. [12] N. Eyrolles, L. Goubin, and M. Videau. Defeating MBA-based Obfuscation. In ACM Workshop on Software PROtection (SPRO), 2016. [13] N. Friedman, K. Murphy, and S. Russell. Learning the Structure of Dynamic Probabilistic Networks. In UAI, 1998. [14] Y. Futamura. Partial Evaluation of Computation Process—An Approach to a Compiler-Compiler. Systems, Computers, Controls, 2(5):45–50, 1971. [15] T. Garfinkel and M. Rosenblum. A Virtual Machine Introspection Based Architecture for Intrusion Detection. In NDSS, 2003.
11
[16] S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, and B. Waters. Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits. In FOCS, 2013. [17] R. Giacobazzi, N. D. Jones, and I. Mastroeni. Obfuscation by Partial Evaluation of Distorted Interpreters. In PEPM, 2012. [18] S. Goldwasser and G. N. Rothblum. On Best-Possible Obfuscation. In TCC, 2007. [19] J. F. Groote and F. Vaandrager. An Efficient Algorithm for Branching Bisimulation and Stuttering Equivalence. In ICALP, 1990. [20] J. F. Groote, D. N. Jansen, J. J. A. Keiren, and A. J. Wijs. An O(m log n) Algorithm for Computing Stuttering Equivalence and Branching Bisimulation. ACM Transactions on Computational Logic, 18(2), 2017. [21] J. Hopcroft. An n log n Algorithm for Minimizing States in a Finite Automaton. In Theory of Machines and Computations, Academic Press, 1971. [22] B. Jain, M. B. Baig, D. Zhang, D. E. Porter, and R. Sion. SoK: Introspections on Trust and the Semantic Gap. In IEEE Symposium on Security and Privacy, 2014. [23] T. Jiang and B. Ravikumar. Minimal NFA Problems are Hard. SIAM Journal on Computing, 22(6):1117– 1141, 1993. [24] N. D. Jones, C. K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice Hall, 1993. [25] P. C. Kanellakis and S. A. Smolka. CCS Expressions, Finite State Processes, and Three Problems of Equivalence. Information and Computation, 86(1):43–68, 1990. [26] J. Kinder. Towards Static Analysis of Virtualization-Obfuscated Binaries. In WCRE, 2012. [27] H. Lähdesmäki, I. Shmulevich, and O. Yli-Harja. On Learning Gene Regulatory Networks under the Boolean Network Model. Machine Learning, 52:147–167, 2003. [28] X. Leroy. Formal Verification of a Realistic Compiler. Communications of the ACM, 52(7):107–115, 2009. [29] B. Mariano, S. Mukherjee, A. Huang, S. Wang, and I. Dillig. Control-Flow Deobfuscation using TraceInformed Compositional Program Synthesis. Proc. ACM Program. Lang., 8(OOPSLA2), 2024. [30] A. R. Meyer and L. J. Stockmeyer. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. In IEEE Symposium on Switching and Automata Theory, 1972. [31] R. Milner. Communication and Concurrency. Prentice Hall, 1989. [32] M. Ollivier, S. Bardin, R. Bonichon, and J.-Y. Marion. How to Kill Symbolic Deobfuscation for Free. In ACSAC, 2019. [33] P. Junod, J. Rinaldini, J. Wehrli, and J. Michielin. Obfuscator-LLVM: Software Protection for the Masses. In SPRO, 2015. [34] R. Paige and R. E. Tarjan. Three Partition Refinement Algorithms. SIAM Journal on Computing, 16(6):973–989, 1987. [35] J. Rissanen. Modeling by Shortest Data Description. Automatica, 14(5):465–471, 1978. [36] R. Roemer, E. Buchanan, H. Shacham, and S. Savage. Return-Oriented Programming: Systems, Languages, and Applications. ACM TISSEC, 15(1), 2012. [37] R. Rolles. Unpacking Virtualization Obfuscators. In WOOT, 2009. [38] S. Schrittwieser, S. Katzenbeisser, J. Kinder, G. Merzdovnik, and E. Weippl. Protecting Software through Obfuscation: Can It Keep Pace with Progress in Code Analysis? ACM Computing Surveys, 49(1), 2016. [39] M. Sharif, A. Lanzi, J. Giffin, and W. Lee. Impeding Malware Analysis Using Conditional Code Obfuscation. In NDSS, 2008. [40] C. Collberg et al. The Tigress C Obfuscator. https://tigress.wtf, accessed 2026. 12
[41] B. Yadegari, B. Johannesmeyer, B. Whitely, and S. Debray. A Generic Approach to Automatic Deobfuscation of Executable Code. In IEEE Symposium on Security and Privacy, 2015. [42] Y. Zhou, A. Main, Y. X. Gu, and H. Johnson. Information Hiding in Software with Mixed BooleanArithmetic Transforms. In WISA, 2007.
13