Document Open Access Logo

BEST: a Binary Executable Slicing Tool

Authors Armel Mangean, Jean-Luc Béchennec, Mikaël Briday, Sébastien Faucou

PDF
Thumbnail PDF

File

OASIcs.WCET.2016.7.pdf
  • Filesize: 0.56 MB
  • 10 pages

Document Identifiers

Author Details

Armel Mangean
Jean-Luc Béchennec
Mikaël Briday
Sébastien Faucou

Cite As Get BibTex

Armel Mangean, Jean-Luc Béchennec, Mikaël Briday, and Sébastien Faucou. BEST: a Binary Executable Slicing Tool. In 16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016). Open Access Series in Informatics (OASIcs), Volume 55, pp. 7:1-7:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/OASIcs.WCET.2016.7

Abstract

We describe the implementation of BEST, a tool for slicing binary code. We aim to integrate this tool in a WCET estimation framework based on model checking. In this approach, program slicing is used to abstract the program model in order to reduce the state space of the system. In this article, we also report on the results of an evaluation of the efficiency of the abstraction technique.

Subject Classification

Keywords
  • Program Slicing
  • Binary Code Analysis
  • WCET Analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hiralal Agrawal. On slicing programs with jump statements. ACM Sigplan Notices, 29(6):302-312, 1994. Google Scholar
  2. Florian Brandner, Stefan Hepp, and Alexander Jordan. Static profiling of the worst-case in real-time programs. In International Conference on Real-Time and Network Systems (RTNS), 2012. URL: http://dx.doi.org/10.1145/2392987.2393000.
  3. Florian Brandner and Alexander Jordan. Refinement of worst-case execution time bounds by graph pruning. Computer Languages, Systems & Structures, 40(3-4):155-170, 2014. URL: http://dx.doi.org/10.1016/j.cl.2014.09.001.
  4. Franck Cassez and Jean-Luc Béchennec. Timing Analysis of Binary Programs with UPPAAL. In International Conference on Application of Concurrency to System Design (ACSD), 2013. Google Scholar
  5. Franck Cassez and Pablo González de Aledo Marugán. Timed automata for modeling caches and pipelines. In Workshop on Models for Formal Analysis of Real Systems (MARS), 2015. URL: http://dx.doi.org/10.4204/EPTCS.196.4.
  6. Andreas Engelbredt Dalsgaard, Mads Chr. Olesen, Martin Toft, René Rydhof Hansen, and Kim Guldstrand Larsen. METAMOC: modular execution time analysis using model checking. In 10th International Workshop on Worst-Case Execution Time Analysis, WCET 2010, July 6, 2010, Brussels, Belgium, pages 113-123, 2010. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2010.113.
  7. Balázs Dezső, Alpár Jüttner, and Péter Kovács. LEMON - an Open Source C++ Graph Template Library. ENTCS, 264(5):23-45, 2011. Google Scholar
  8. Jeanne Ferrante, Karl J Ottenstein, and Joe D Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems (TOPLAS), 9(3):319-349, 1987. Google Scholar
  9. Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Björn Lisper. The mälardalen WCET benchmarks: Past, present and future. In 10th International Workshop on Worst-Case Execution Time Analysis, WCET 2010, July 6, 2010, Brussels, Belgium, pages 136-146, 2010. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2010.136.
  10. Andreas Gustavsson, Andreas Ermedahl, Björn Lisper, and Paul Pettersson. Towards WCET analysis of multicore architectures using UPPAAL. In 10th International Workshop on Worst-Case Execution Time Analysis, WCET 2010, July 6, 2010, Brussels, Belgium, pages 101-112, 2010. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2010.101.
  11. Susan Horwitz, Thomas Reps, and David Binkley. Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(1):26-60, 1990. Google Scholar
  12. Rola Kassem, Mikaël Briday, Jean-Luc Béchennec, Guillaume Savaton, and Yvon Trinquet. Harmless, a hardware architecture description language dedicated to real-time embedded system simulation. JSA, 58(8):318-337, 2012. Google Scholar
  13. Akos Kiss, Judit Jász, Gábor Lehotai, and Tibor Gyimóthy. Interprocedural Static Slicing of Binary Executables. In International Workshop on Source Code Analysis and Manipulation, 2003. Google Scholar
  14. Kim G. Larsen, Paul Pettersson, and Wang Yi. UPPAAL in a Nutshell. STTT, 1(1-2):134-152, 1997. Google Scholar
  15. Paul Lokuciejewski, Daniel Cordes, Heiko Falk, and Peter Marwedel. A fast and precise static loop analysis based on abstract interpretation, program slicing and polytope models. In International Symposium on Code Generation and Optimization (CGO), pages 136-146, 2009. Google Scholar
  16. Karl J Ottenstein and Linda M Ottenstein. The program dependence graph in a software development environment. ACM Sigplan Notices, 19(5):177-184, 1984. Google Scholar
  17. Christer Sandberg, Andreas Ermedahl, Jan Gustafsson, and Björn Lisper. Faster WCET flow analysis by program slicing. In ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES), pages 103-112, 2006. URL: http://dx.doi.org/10.1145/1134650.1134666.
  18. Frank Tip. A Survey of Program Slicing Techniques. Journal of programming languages, 3(3), 1995. Google Scholar
  19. Mark Weiser. Program Slicing. In International Conference on Software Engineering (ICSE), 1981. Google Scholar
  20. Reinhard Wilhelm. Why AI + ILP is Good for WCET, but MC is not, nor ILP alone. In International Conference on Verification, Model Checking and Abstract Interpretation (VMCAI), 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact