Control Structure Analysis and Recovery of Embedded Binaries

JI Weixing; HUO Yuanhong; WANG Yizhuo; GAO Yujin; SHI Feng

doi:10.1049/cje.2017.09.003

Volume 26 Issue 6

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2017 > 26(6): 1118-1124

JI Weixing, HUO Yuanhong, WANG Yizhuo, et al., “Control Structure Analysis and Recovery of Embedded Binaries,” Chinese Journal of Electronics, vol. 26, no. 6, pp. 1118-1124, 2017, doi: 10.1049/cje.2017.09.003

Citation:

JI Weixing, HUO Yuanhong, WANG Yizhuo, et al., “Control Structure Analysis and Recovery of Embedded Binaries,” Chinese Journal of Electronics, vol. 26, no. 6, pp. 1118-1124, 2017, doi: 10.1049/cje.2017.09.003

Citation:

PDF( 680 KB)

Control Structure Analysis and Recovery of Embedded Binaries

doi: 10.1049/cje.2017.09.003

Beijing Institute of Technology, Beijing 100081, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61300010).

Received Date: 2015-05-27
Rev Recd Date: 2015-10-07
Publish Date: 2017-11-10

Abstract

Abstract

Existing decompilers use rule-based algorithms to transform unstructured Control flow graph (CFG) into equivalent high-level programming language constructs with "goto" statements. One problem of such approaches is that they generate a large number of "goto"s in the output code, which reduce the readability and hinder the understanding of input binaries. A global search algorithm is proposed based on structural analysis. This algorithm restructures a CFG and generates fewer number of "goto" statements than the rule-based algorithm does. We also present a Genetic algorithm (GA) for the global search approach to locate near optimal solutions for large CFGs. Evaluation results on a set of real CFGs show that the genetic algorithm-based heuristic for global search is capable of finding high-quality solutions.
- Decompiling,
- Control flow graph restructuring,
- Structural analysis,
- Genetic algorithm (GA)

FullText(HTML)

References(26)

References

T. Bao, J. Burket, M. Woo, et al., "BYTEWEIGHT:Learning to recognize functions in binary code", Proc. of 23rd USENIX Security Symposium, San Diego, CA, pp.845-860, 2014.

T.F. Pfeffer, P. Herber and J. Schneider, "Reverse engineering of ARM binaries using formal transformations", Proc. of the 7th International Conference on Security of Information and Networks, New York, NY, USA, pp.345-350, 2014.

P. Chen, H. Han, et al., "Detecting integer bugs based on static and dynamic program analysis", Acta Electronica Sinica, Vol.38, No.8, pp.1741-1747, 2010. (in Chinese)

F.Y. Chen, D.S. Zhang and Z.Y. Wang, "Inter-Thread inter-ference analysis for real-time WCET estimations of, multi-core architectures", Acta Electronica Sinica, Vol.40, No.7, pp.1372-1378, 2012. (in Chinese)

G.B. Chen, Z.W. Qi, S.Q. Huang, et al., "A refined decompiler to generate C code with high readability", Software:Practice and Experience, Vol.43, No.11, pp.1337-1358, 2013.

A.M. Erosa and L.J. Hendren, "Taming control flow:A structured approach to eliminating goto statements", Proc. of the 1994 International Conference on Computer Languages, Toulouse, France, pp.229-240, 1994.

B.S. Baker, "An algorithm for structuring flowgraphs", Journal of the Association for Computing Machinery, Vol.24, No.1, pp.98-120, 1997.

C. Cifuentes and K. Gough, "A methodology for decompilation", Proc. of XIX Conferencia Latinoamericana de Informatica, pp.257-266, 1992.

Z. Ammarguellat, "A control-flow normalization algorithm and its complexity", IEEE Transactions on Software Engineering, Vol.18, No.3, pp.237-250, 1997.

G. Oulsnam, "Unravelling structured programs", The Computer Journal, Vol.25, No.3, pp.379-387, 1982.

E. Ashcroft and Z. Manna, "The translation of ‘goto’ programs to ‘while’ programs", Classics in Software Engineering, 1979.

S. Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann Publishers Inc., CA, USA, 1997.

C. Cifuentes, "A structuring algorithms for decompilation", Proc. of XIX Conference Latinoamericana de Information, pp.267-276, 1993.

W. Ren, "Approach for facilitating structural recovery by clustering use cases", Acta Electronica Sinica, Vol.41, No.7, pp.1412-1418, 2013. (in Chinese)

U. Lichtblau, "Decompilation of control structures by means of graph transformations", Proc. of the International Joint Conference on Theory and Practice of Software Development, Berlin, Germany, pp.284-297, 1985.

M.H. Williams and G. Chen, "Restructuring Pascal programs containing goto statements", The Computer Journal, Vol.28, No.2, pp.134-137, 1985.

D.E. Knuth and R.W. Floyd, "Notes on avoiding go to statements", Information Processing Letters, Vol.1, No.1, pp.23-31, 1971.

M.H. Williams, "Generating structured flow diagrams:The nature of unstructuredness", The Computer Journal, Vol.20, No.1, pp.45-50, 1997.

A.L. Baker and S.H. Zweben, "A comparison of measures of control flow complexity", IEEE Transactions on Software Engineering, Vol.6, No.6, pp.506-512, 1980.

L. Ramshaw, "Eliminating goto's while preserving program structure", Journal of the ACM, Vol.35, No.4, pp.893-920, 1988.

N. Naeem and L. Hendren, "Programmer-friendly decompiled Java", Proc. of the 14th IEEE International Conference on Program Comprehension, Athens, Greece, pp.327-336, 2006.

K. Troshina, A. Chernov and Y. Derevenets, "C decompilation:Is it possible?", Proc. of International Workshop on Program Understanding, Altai Mountains, Russia, pp.18-27, 2009.

J.H. Holland, Adaptive in Natural and Artificial Systems, MIT Press, MA, USA, 1975.

M.R. Guthaus, J.S. Ringenberg, D. Ernst, et al., "MiBench:A free, commercially representative embedded benchmark suite", Proc. of 2001 IEEE International Workshop of Workload Characterization, DC, USA, pp.3-14, 2001.

ARM Ltd. and ARM Germany GmbH, "Keil C51 C compiler", http://www.keil.com/c51/c51.asp, 2015-10-1.

Flatassembler, "Flat assembler", http://flatassembler.net/, 2015-10-1.

Relative Articles

Supplements(0)

Cited By

Proportional views