Automatic extraction of function bodies from software binaries

ABSTRACT

This paper describes a method for automatically extracting function bodies from linked software binaries. It utilizes procedure-calling conventions along with limited control and data flow information. It has been tested with the TI C6000 DSP processor platform. Results are reported on eight benchmarks for which our algorithm successfully identifies all functions. It identifies 198% more functions than by the use procedure calling conventions alone.

REFERENCES

• 1: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 2: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 3: C. Cifuentes and K. Gough, "A Methodology for Decomposition", XIX Conferencia Latinoamericana de Informatica, August 1993.
• 4: Cristina Cifuentes , Vishv M. Malhotra, Binary Translation: Static, Dynamic, Retargetable?, Proceedings of the 1996 International Conference on Software Maintenance, p.340-349, November 04-08, 1996
• 5: Greg Stitt , Frank Vahid, Hardware/software partitioning of software binaries, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.164-170, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774596]
• 6: David Callahan , Alan Carle , Mary Wolcott Hall , Ken Kennedy, Constructing the Procedure Call Multigraph, IEEE Transactions on Software Engineering, v.16 n.4, p.483-487, April 1990 [doi>10.1109/32.54302]
• 7: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 8: Barry K. Rosen, High-level data flow analysis, Communications of the ACM, v.20 n.10, p.712-724, Oct. 1977 [doi>10.1145/359842.359849]
• 9: Mark W. Bailey , Jack W. Davidson, A formal model and specification language for procedure calling conventions, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.298-310, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199517]
• 10: M. Van Emmerik, Identifying Library Functions in Executable Files Using Patterns, Proceedings of the Australian Software Engineering Conference, p.90, November 09-13, 1998
• 11: C. Cifuentes and D. Simon, "Procedure Abstraction Recovery from binary code", Dept. of Computer Science, University of Queensland, 1999.
• 12: A. Klaiber, "The Technology Behind Crusoe Processors," Transmeta Corp., White Paper, Jan. 2000, www.transmeta.com
• 13: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 14: Michael Gschwind , Erik R. Altman , Sumedh Sathaye , Paul Ledak , David Appenzeller, Dynamic and Transparent Binary Translation, Computer, v.33 n.3, p.54-59, March 2000 [doi>10.1109/2.825696]
• 15: Gaurav Mittal , David C. Zaretsky , Xiaoyong Tang , P. Banerjee, Automatic translation of software binaries onto FPGAs, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996678]
• 16: David Zaretsky , Gaurav Mittal , Xiaoyong Tang , Prith Banerjee, Evaluation of scheduling and allocation algorithms while mapping assembly code onto FPGAs, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA [doi>10.1145/988952.989048]
• 17: David Zaretsky , Gaurav Mittal , Xiaoyong Tang , Prith Banerjee, Overview of the FREEDOM Compiler for Mapping DSP Software to FPGAs, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.37-46, April 20-23, 2004