article

Generating Decision Trees for Decoding Binaries

Author:

Henrik TheilingAuthors Info & Claims

ACM SIGPLAN Notices, Volume 36, Issue 8

Pages 112 - 120

https://doi.org/10.1145/384196.384213

Published: 01 August 2001 Publication History

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.

References

[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.

[2]

M. Fernandez and N. Ramsey. Automatic Checking of Instruction Specifications. In Proceedings of the 19th International Conference on Software Engineering. ACM Press, 1997.

Digital Library

[3]

J. Gustafsson. Analyzing Execution-Time of Object-Oriented Programs Using Abstract Interpretation. PhD Thesis, Uppsala University, M.alardalens H.ogskola, 2000.

[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.

Digital Library

[5]

http://www.ee.princeton.edu/~yauli/cinderella-3.0/. Cinderella 3.0 Home Page.

[6]

http://www.gnu.org. GNU Binutils.

[7]

IBM. PPC403GCX Embedded Controller, User's Manual, 1997.

[8]

Infineon. Instruction Set Manual for the C16x Family of Siemens 16-Bit CMOS Single-Chip Microcontrollers, 1997.

[9]

D. K.astner. TDL - A Hardware and Assembly Description Language. Technical report, Universit. at d. Saarlandes, 2000.

[10]

A. Laville. Comparison of Priority Rules in Pattern Matching and Term Rewriting. Journal of Symbolic Computations, 11(4):321-348, April 1991.

Digital 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.

Digital 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.

Digital 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.

Digital Library

[14]

B. M. E. Moret. Decision Trees and Diagrams. Computing Surveys, 14(4), 1982.

Digital Library

[15]

Motorola. Coldfire Microprocessor Family Programmer's Reference Manual, 1997.

[16]

S. K. Murthy. Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey. Data Mining and Knowledge Discovery, 2(4), January 1998.

Digital Library

[17]

P. Puschner and C. Koza. Calculating the Maximum Execution Time of Real-Time Programs. Real-Time Systems, 1, 1989.

Digital Library

[18]

N. Ramsey and M. Fernandez. The New Jersey Machine-Code Toolkit. In Usenix Technical Conference, New Orleans, USA, 1995.

Digital Library

[19]

N. Ramsey and M. Fernandez. The New Jersey Machine-Code Toolkit, Reference Manual, 1996.

[20]

S. Russell and P. Norvig. Artifitial Intelligence, A Modern Approach. Prentice Hall, 1995.

Digital 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.

Digital 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.

Digital Library

Cited By

Fokina NSolovev M(2019)Automated Generation of Machine Instruction DecodersProgramming and Computing Software10.1134/S036176881907006545:7(390-397)Online publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1134/S0361768819070065
Georgousopoulou MChipulu MOjiako UJohnson J(2014)Investment risk preference among Greek SME proprietors: a pilot studyJournal of Small Business and Enterprise Development10.1108/JSBED-10-2013-014621:1(177-193)Online publication date: 11-Feb-2014
https://doi.org/10.1108/JSBED-10-2013-0146
Ghanem AEl-mahdy AEl-salam I(2006)A Cycle-Accurate Micro-Architecture Simulation Framework for Embedded Processors2006 International Conference on Computer Engineering and Systems10.1109/ICCES.2006.320428(71-76)Online publication date: Nov-2006
https://doi.org/10.1109/ICCES.2006.320428
Show More Cited By

Index Terms

Generating Decision Trees for Decoding Binaries
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Generating Decision Trees for Decoding Binaries
OM '01: Proceedings of the 2001 ACM SIGPLAN workshop on Optimization of middleware and distributed systems

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 ...
Generating Decision Trees for Decoding Binaries
LCTES '01: Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems

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 ...
Soft-decision decoding of nonbinary cyclic and modified cyclic codes

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 36, Issue 8

Aug. 2001

245 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/384196

Chairman:
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Editor:
Cindy Norris
Appalachian State Univ., Boone, NC

Issue’s Table of Contents

LCTES '01: Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems
August 2001
250 pages
ISBN:1581134258
DOI:10.1145/384197
Chairmen:
Seongsoo Hong
Snow Bird, UT
,
Santosh Pande
Snow Bird, UT

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2001

Published in SIGPLAN Volume 36, Issue 8

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
502
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fokina NSolovev M(2019)Automated Generation of Machine Instruction DecodersProgramming and Computing Software10.1134/S036176881907006545:7(390-397)Online publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1134/S0361768819070065
Georgousopoulou MChipulu MOjiako UJohnson J(2014)Investment risk preference among Greek SME proprietors: a pilot studyJournal of Small Business and Enterprise Development10.1108/JSBED-10-2013-014621:1(177-193)Online publication date: 11-Feb-2014
https://doi.org/10.1108/JSBED-10-2013-0146
Ghanem AEl-mahdy AEl-salam I(2006)A Cycle-Accurate Micro-Architecture Simulation Framework for Embedded Processors2006 International Conference on Computer Engineering and Systems10.1109/ICCES.2006.320428(71-76)Online publication date: Nov-2006
https://doi.org/10.1109/ICCES.2006.320428
Qin WMalik SGetreu IFix LLavagno L(2003)Automated synthesis of efficient binary decoders for retargetable software toolkitsProceedings of the 40th annual Design Automation Conference10.1145/775832.776027(764-769)Online publication date: 2-Jun-2003
https://dl.acm.org/doi/10.1145/775832.776027
Wei Qin Malik S(2003)Automated synthesis of efficient binary decoders for retargetable software toolkitsProceedings 2003. Design Automation Conference (IEEE Cat. No.03CH37451)10.1109/DAC.2003.1219122(764-769)Online publication date: 2003
https://doi.org/10.1109/DAC.2003.1219122
Venkanna MRao R(2018)Static Worst-Case Execution Time Optimization using DPSO for ASIP ArchitectureIngeniería Solidaria10.16925/.v14i0.223014:25(1-11)Online publication date: 1-May-2018
https://doi.org/10.16925/.v14i0.2230
Okuda KTakeyama HFanucci LTeich J(2016)Decision tree generation for decoding irregular instructionsProceedings of the 2016 Conference on Design, Automation & Test in Europe10.5555/2971808.2972179(1592-1597)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.5555/2971808.2972179
Fournel NMichel LPétrot FHenkel J(2013)Automated generation of efficient instruction decoders for instruction set simulatorsProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561972(739-746)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561972
Fournel NMichel LPetrot F(2013)Automated generation of efficient instruction decoders for Instruction Set Simulators2013 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1109/ICCAD.2013.6691197(739-746)Online publication date: Nov-2013
https://doi.org/10.1109/ICCAD.2013.6691197
Thesing SSouyris JHeckmann RRandimbivololona FLangenbach MWilhelm RFerdinand C(2003)An abstract interpretation-based timing validation of hard real-time avionics software2003 International Conference on Dependable Systems and Networks, 2003. Proceedings.10.1109/DSN.2003.1209972(625-632)Online publication date: 2003
https://doi.org/10.1109/DSN.2003.1209972
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents