JI Weixing, HUO Yuanhong, WANG Yizhuo, GAO Yujin, SHI Feng. Control Structure Analysis and Recovery of Embedded Binaries[J]. Chinese Journal of Electronics, 2017, 26(6): 1118-1124. doi: 10.1049/cje.2017.09.003
Citation: JI Weixing, HUO Yuanhong, WANG Yizhuo, GAO Yujin, SHI Feng. Control Structure Analysis and Recovery of Embedded Binaries[J]. Chinese Journal of Electronics, 2017, 26(6): 1118-1124. doi: 10.1049/cje.2017.09.003

Control Structure Analysis and Recovery of Embedded Binaries

doi: 10.1049/cje.2017.09.003
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
  • 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.
  • loading
  • 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.
  • 加载中


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (157) PDF downloads(244) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint