Binary translation, the automatic translation of executable programs from one machine to another, requires analyses and transformations that could be used in a wide variety of tools intended to reverse engineer bi- nary codes. Our approach to binary translation, which is designed to allow both source and target machines to be changed at low cost, is based on a combination of machine descriptions, binary-interface descriptions, and machine-independent analyses.This paper deals with the recovery of high-level procedure calls from binary code; namely, the recovery of parameters and return locations, in a machine- independent way. The use of a specification language, PAL, is described, as well as the machine-independent recovery analysis based on PAL. The work described in this paper has been integrated into UQBT, a resourceable binary translation framework. Translations across binaries for SPARC(tm), Pentium and Java(tm) virtual machine architectures have been achieved.