Henrik Theiling
Abstract
Tools reading binary code, like analysers, debuggers, disassemblers, etc., need to decode the target's machine code. A decision tree is often used to represent the decoding function.
Manually writing a decoder is a lengthy and error-prone task. It is desirable to be able to use the vendor's instruction code manual and to easily transform the documentation into a specification that a tool can use to generate a decoder.
This paper presents a novel algorithm that computes a decision tree from machine code bit patterns alone. Neither the bit fields of the machine code, nor the width of the machine command, nor the order in which the bits should be decoded need to be specified. The decoding algorithm accesses any significant bit exactly once during decoding.
- 1 C. Ferdinand, D. K. astner, M. Langenbach, F. Martin, M. Schmidt, J. Schneider, H. Theiling, S. Thesing, and R. Wilhelm. Run-Time Guarantees for Real-Time Systems The USES Approach. In Proceedings of Informatik '99 Arbeitstagung Programmiersprachen, Paderborn, 1999.Google Scholar
Cross Ref
- 2 M. Fernandez and N. Ramsey. Automatic Checking of Instruction Specifications. In Proceedings of the 19th International Conference on Software Engineering. ACM Press, 1997. Google ScholarDigital Library
- 3 J. Gustafsson. Analyzing Execution-Time of Object-Oriented Programs Using Abstract Interpretation. PhD Thesis, Uppsala University, M.alardalens H.ogskola, 2000.Google Scholar
- 4 G. Hadjiyiannis, P. Russo, and S. Devadas. A methodology for accurate performance evaluation in architecture exploration. In 36th Design Automation Conference (DAC'99), pages 927-932, 1999. Google ScholarDigital Library
- 5 http://www.ee.princeton.edu/~yauli/cinderella-3.0/. Cinderella 3.0 Home Page.Google Scholar
- 6 http://www.gnu.org. GNU Binutils.Google Scholar
- 7 IBM. PPC403GCX Embedded Controller, User's Manual, 1997.Google Scholar
- 8 Infineon. Instruction Set Manual for the C16x Family of Siemens 16-Bit CMOS Single-Chip Microcontrollers, 1997.Google Scholar
- 9 D. K.astner. TDL - A Hardware and Assembly Description Language. Technical report, Universit. at d. Saarlandes, 2000.Google Scholar
- 10 A. Laville. Comparison of Priority Rules in Pattern Matching and Term Rewriting. Journal of Symbolic Computations, 11(4):321-348, April 1991. Google ScholarDigital Library
- 11 Y.-T. S. Li, S. Malik, and A. Wolfe. Cache Modeling for Real-Time Software: Beyond Direct Mapped Instruction Caches. In Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS), 1996. Google ScholarDigital Library
- 12 S.-S. Lim, Y. H. Bae, G. T. Jang, B.-D. Rhee, S. L. Min, C. Y. Park, H. Shin, K. Park, S.-M. Moon, and C. S. Kim. An Accurate Worst Case Timing Analysis for RISC Processors. IEEE Transactions on Software Engineering, 21(7), 1995. Google ScholarDigital Library
- 13 S.-S. Lim, J. Hee Han, J. Kim, and S. Lyul Min. A Worst Case Timing Analysis Technique for Multiple Issue Machines. In Proceedings of the 19th IEEE Real-Time Systems Symposium (RTSS), 1998. Google ScholarDigital Library
- 14 B. M. E. Moret. Decision Trees and Diagrams. Computing Surveys, 14(4), 1982. Google ScholarDigital Library
- 15 Motorola. Coldfire Microprocessor Family Programmer's Reference Manual, 1997.Google Scholar
- 16 S. K. Murthy. Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey. Data Mining and Knowledge Discovery, 2(4), January 1998. Google ScholarDigital Library
- 17 P. Puschner and C. Koza. Calculating the Maximum Execution Time of Real-Time Programs. Real-Time Systems, 1, 1989. Google ScholarDigital Library
- 18 N. Ramsey and M. Fernandez. The New Jersey Machine-Code Toolkit. In Usenix Technical Conference, New Orleans, USA, 1995. Google ScholarDigital Library
- 19 N. Ramsey and M. Fernandez. The New Jersey Machine-Code Toolkit, Reference Manual, 1996.Google Scholar
- 20 S. Russell and P. Norvig. Artifitial Intelligence, A Modern Approach. Prentice Hall, 1995. Google ScholarDigital Library
- 21 H. Theiling. Extracting Safe and Precise Control Flow from Binaries. In Proceedings of the 7th International Conference onReal-Time Computing Systems and Applications (RTCSA), Cheju Island, South Korea, 2000. Google ScholarDigital Library
- 22 H. Theiling and C. Ferdinand. Combining Abstract Interpretation and ILP for Microarchitecture Modelling and Program Path Analysis. In Proceedings of the 19th IEEE Real-Time Systems Symposium (RTSS), Madrid, Spain, 1998. Google ScholarDigital Library
Index Terms
- Generating Decision Trees for Decoding Binaries
Recommendations
Generating Decision Trees for Decoding Binaries
OM '01: Proceedings of the 2001 ACM SIGPLAN workshop on Optimization of middleware and distributed systemsTools reading binary code, like analysers, debuggers, disassemblers, etc., need to decode the target's machine code. A decision tree is often used to represent the decoding function.
Manually writing a decoder is a lengthy and error-prone task. It is ...
Generating Decision Trees for Decoding Binaries
LCTES '01: Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systemsTools reading binary code, like analysers, debuggers, disassemblers, etc., need to decode the target's machine code. A decision tree is often used to represent the decoding function.
Manually writing a decoder is a lengthy and error-prone task. It is ...
Comments