Article

Generating Decision Trees for Decoding Binaries

Author:

Henrik TheilingAuthors Info & Claims

OM '01: Proceedings of the 2001 ACM SIGPLAN workshop on Optimization of middleware and distributed systems

Pages 112 - 120

https://doi.org/10.1145/384198.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

Spink TWagstaff HFranke B(2020)A Retargetable System-level DBT HypervisorACM Transactions on Computer Systems10.1145/338616136:4(1-24)Online publication date: 30-May-2020
https://dl.acm.org/doi/10.1145/3386161
Spink TWagstaff HFranke BDan TDahlia M(2019)A retargetable system-level DBT hypervisorProceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference10.5555/3358807.3358850(505-520)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.5555/3358807.3358850

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

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 ...
Asymptotically optimum soft decision decoding

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OM '01: Proceedings of the 2001 ACM SIGPLAN workshop on Optimization of middleware and distributed systems

August 2001

250 pages

ISBN:1581134266

DOI:10.1145/384198

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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

OM01

Sponsor:

SIGPLAN

OM01: Workshop on Optimization of Middleware and Distributed Systems ( co-located with ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation - PLDI )

Utah, Snow Bird, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
492
Total Downloads

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

Reflects downloads up to 12 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Spink TWagstaff HFranke B(2020)A Retargetable System-level DBT HypervisorACM Transactions on Computer Systems10.1145/338616136:4(1-24)Online publication date: 30-May-2020
https://dl.acm.org/doi/10.1145/3386161
Spink TWagstaff HFranke BDan TDahlia M(2019)A retargetable system-level DBT hypervisorProceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference10.5555/3358807.3358850(505-520)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.5555/3358807.3358850

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 Table of Conten