2 Search Results for "Giacobazzi, Roberto"

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.117
A Rice’s Theorem for Abstract Semantics

Authors: Paolo Baldan, Francesco Ranzato, and Linpeng Zhang

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Classical results in computability theory, notably Rice’s theorem, focus on the extensional content of programs, namely, on the partial recursive functions that programs compute. Later and more recent work investigated intensional generalisations of such results that take into account the way in which functions are computed, thus affected by the specific programs computing them. In this paper, we single out a novel class of program semantics based on abstract domains of program properties that are able to capture nonextensional aspects of program computations, such as their asymptotic complexity or logical invariants, and allow us to generalise some foundational computability results such as Rice’s Theorem and Kleene’s Second Recursion Theorem to these semantics. In particular, it turns out that for this class of abstract program semantics, any nontrivial abstract property is undecidable and every decidable overapproximation necessarily includes an infinite set of false positives which covers all values of the semantic abstract domain.
Cite as

Paolo Baldan, Francesco Ranzato, and Linpeng Zhang. A Rice’s Theorem for Abstract Semantics. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 117:1-117:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{baldan_et_al:LIPIcs.ICALP.2021.117,
  author =	{Baldan, Paolo and Ranzato, Francesco and Zhang, Linpeng},
  title =	{{A Rice’s Theorem for Abstract Semantics}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{117:1--117:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.117},
  URN =		{urn:nbn:de:0030-drops-141860},
  doi =		{10.4230/LIPIcs.ICALP.2021.117},
  annote =	{Keywords: Computability Theory, Recursive Function, Rice’s Theorem, Kleene’s Second Recursion Theorem, Program Analysis, Affine Program Invariants}
}
Document
DOI: 10.4230/DagRep.4.6.48
Challenges in Analysing Executables: Scalability, Self-Modifying Code and Synergy (Dagstuhl Seminar 14241)

Authors: Roberto Giacobazzi, Axel Simon, and Sarah Zennou

Published in: Dagstuhl Reports, Volume 4, Issue 6 (2015)

Abstract
This report summarizes the program and the outcomes of the Dagstuhl Seminar 14241, entitled "Challenges in Analysing Executables: Scalability, Self-Modifying Code and Synergy". The seminar brought together practitioners and researchers from industry and academia to discuss the state-of-the art in the analysis of binaries, the handling of the most challenging malware and the ever-lasting problem of scalability. The meeting created new links within this very diverse community and highlighted the broad interest in dealing with obfuscated code.
Cite as

Roberto Giacobazzi, Axel Simon, and Sarah Zennou. Challenges in Analysing Executables: Scalability, Self-Modifying Code and Synergy (Dagstuhl Seminar 14241). In Dagstuhl Reports, Volume 4, Issue 6, pp. 48-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{giacobazzi_et_al:DagRep.4.6.48,
  author =	{Giacobazzi, Roberto and Simon, Axel and Zennou, Sarah},
  title =	{{Challenges in Analysing Executables: Scalability, Self-Modifying Code and Synergy (Dagstuhl Seminar 14241)}},
  pages =	{48--63},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{6},
  editor =	{Giacobazzi, Roberto and Simon, Axel and Zennou, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.6.48},
  URN =		{urn:nbn:de:0030-drops-47627},
  doi =		{10.4230/DagRep.4.6.48},
  annote =	{Keywords: Executable analysis, reverse engineering, malware detection, control flow reconstruction, emulators, binary instrumentation}
}
  • Refine by Author
  • 1 Baldan, Paolo
  • 1 Giacobazzi, Roberto
  • 1 Ranzato, Francesco
  • 1 Simon, Axel
  • 1 Zennou, Sarah
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Abstraction
  • 1 Theory of computation → Computability
  • 1 Theory of computation → Recursive functions

  • Refine by Keyword
  • 1 Affine Program Invariants
  • 1 Computability Theory
  • 1 Executable analysis
  • 1 Kleene’s Second Recursion Theorem
  • 1 Program Analysis
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2014
  • 1 2021

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 Imprint Privacy Contact