BehaviorDistill: Distilling Black-Box Software via Evolving, Verifiable Specifications

Black-box software replication builds a student program from scratch to match a teacher's behavior using documentation and execution observations without source access. Recent methods capture observed behavior in specifications to guide construction, but natural-language specifications cannot be executed to verify consistency or locate discrepancies. Tests enable such verification, yet handcrafted generation rules restrict exploration and risk biased, incomplete coverage, while unstructured suites obscure behavioral relations and coverage gaps. We introduce BehaviorDistill, a method connecting exploration and construction through evolving, verifiable behavioral specifications. Evolving Class-Structured Coverage (ECC) synthesizes these specifications by linking executable tests to an evolving class-structured behavior model, where high-level classes guide feature discovery, fine-grained classes guide deeper exploration, and new tests refine the model. Building on these specifications, Plan-Guided Coverage-Expanding Construction (PCC) uses dynamic plans to organize test constraints into staged implementation and repair tasks, while construction feedback drives test expansion and revisions to plans and code. Across multiple benchmarks and models, BehaviorDistill achieves Raw Pass Rate and Almost Resolved gains reaching 15.8 and 18.2 percentage points, respectively, illuminating a path toward autonomous software reconstruction through evolving, verifiable behavioral specifications.