5 Search Results for "M�hlenbein, Heinz"

Document
DOI: 10.4230/LIPIcs.ECOOP.2021.2
Lossless, Persisted Summarization of Static Callgraph, Points-To and Data-Flow Analysis

Authors: Philipp Dominik Schubert, Ben Hermann, and Eric Bodden

Published in: LIPIcs, Volume 194, 35th European Conference on Object-Oriented Programming (ECOOP 2021)

Abstract
Static analysis is used to automatically detect bugs and security breaches, and aids compiler optimization. Whole-program analysis (WPA) can yield high precision, however causes long analysis times and thus does not match common software-development workflows, making it often impractical to use for large, real-world applications. This paper thus presents the design and implementation of ModAlyzer, a novel static-analysis approach that aims at accelerating whole-program analysis by making the analysis modular and compositional. It shows how to compute lossless, persisted summaries for callgraph, points-to and data-flow information, and it reports under which circumstances this function-level compositional analysis outperforms WPA. We implemented ModAlyzer as an extension to LLVM and PhASAR, and applied it to 12 real-world C and C++ applications. At analysis time, ModAlyzer modularly and losslessly summarizes the analysis effect of the library code those applications share, hence avoiding its repeated re-analysis. The experimental results show that the reuse of these summaries can save, on average, 72% of analysis time over WPA. Moreover, because it is lossless, the module-wise analysis fully retains precision and recall. Surprisingly, as our results show, it sometimes even yields precision superior to WPA. The initial summary generation, on average, takes about 3.67 times as long as WPA.
Cite as

Philipp Dominik Schubert, Ben Hermann, and Eric Bodden. Lossless, Persisted Summarization of Static Callgraph, Points-To and Data-Flow Analysis. In 35th European Conference on Object-Oriented Programming (ECOOP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 194, pp. 2:1-2:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{schubert_et_al:LIPIcs.ECOOP.2021.2,
  author =	{Schubert, Philipp Dominik and Hermann, Ben and Bodden, Eric},
  title =	{{Lossless, Persisted Summarization of Static Callgraph, Points-To and Data-Flow Analysis}},
  booktitle =	{35th European Conference on Object-Oriented Programming (ECOOP 2021)},
  pages =	{2:1--2:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-190-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{194},
  editor =	{M{\o}ller, Anders and Sridharan, Manu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2021.2},
  URN =		{urn:nbn:de:0030-drops-140453},
  doi =		{10.4230/LIPIcs.ECOOP.2021.2},
  annote =	{Keywords: Inter-procedural static analysis, compositional analysis, LLVM, C/C++}
}
Document
Tool Insights Paper
DOI: 10.4230/LIPIcs.ECOOP.2019.21
MagpieBridge: A General Approach to Integrating Static Analyses into IDEs and Editors (Tool Insights Paper)

Authors: Linghui Luo, Julian Dolby, and Eric Bodden

Published in: LIPIcs, Volume 134, 33rd European Conference on Object-Oriented Programming (ECOOP 2019)

Abstract
In the past, many static analyses have been created in academia, but only a few of them have found widespread use in industry. Those analyses which are adopted by developers usually have IDE support in the form of plugins, without which developers have no convenient mechanism to use the analysis. Hence, the key to making static analyses more accessible to developers is to integrate the analyses into IDEs and editors. However, integrating static analyses into IDEs is non-trivial: different IDEs have different UI workflows and APIs, expertise in those matters is required to write such plugins, and analysis experts are not typically familiar with doing this. As a result, especially in academia, most analysis tools are headless and only have command-line interfaces. To make static analyses more usable, we propose MagpieBridge - a general approach to integrating static analyses into IDEs and editors. MagpieBridge reduces the mxn complexity problem of integrating m analyses into n IDEs to m+n complexity because each analysis and type of plugin need be done just once for MagpieBridge itself. We demonstrate our approach by integrating two existing analyses, Ariadne and CogniCrypt, into IDEs; these two analyses illustrate the generality of MagpieBridge, as they are based on different program analysis frameworks - WALA and Soot respectively - for different application areas - machine learning and security - and different programming languages - Python and Java. We show further generality of MagpieBridge by using multiple popular IDEs and editors, such as Eclipse, IntelliJ, PyCharm, Jupyter, Sublime Text and even Emacs and Vim.
Cite as

Linghui Luo, Julian Dolby, and Eric Bodden. MagpieBridge: A General Approach to Integrating Static Analyses into IDEs and Editors (Tool Insights Paper). In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 21:1-21:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{luo_et_al:LIPIcs.ECOOP.2019.21,
  author =	{Luo, Linghui and Dolby, Julian and Bodden, Eric},
  title =	{{MagpieBridge: A General Approach to Integrating Static Analyses into IDEs and Editors}},
  booktitle =	{33rd European Conference on Object-Oriented Programming (ECOOP 2019)},
  pages =	{21:1--21:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-111-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{134},
  editor =	{Donaldson, Alastair F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2019.21},
  URN =		{urn:nbn:de:0030-drops-108139},
  doi =		{10.4230/LIPIcs.ECOOP.2019.21},
  annote =	{Keywords: IDE, Tool Support, Static Analysis, Language Server Protocol}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.22
Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets

Authors: Heiko Hamann, Christine Markarian, Friedhelm Meyer auf der Heide, and Mostafa Wahby

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
The modern warehouse is partially automated by robots. Instead of letting human workers walk into shelfs and pick up the required stock, big groups of autonomous mobile robots transport the inventory to the workers. Typically, these robots have an electric drive and need to recharge frequently during the day. When we scale this approach up, it is essential to place recharging stations strategically and as soon as needed so that all robots can survive. In this work, we represent a warehouse topology by a graph and address this challenge with the Online Connected Dominating Set problem (OCDS), an online variant of the classical Connected Dominating Set problem [Guha and Khuller, 1998]. We are given an undirected connected graph G = (V, E) and a sequence of subsets of V arriving over time. The goal is to grow a connected subgraph that dominates all arriving nodes and contains as few nodes as possible. We propose an O(log^2 n)-competitive randomized algorithm for OCDS in general graphs, where n is the number of nodes in the input graph. This is the best one can achieve due to Korman's randomized lower bound of Omega(log n log m) [Korman, 2005] for the related Online Set Cover problem [Alon et al., 2003], where n is the number of elements and m is the number of subsets. We also run extensive simulations to show that our algorithm performs well in a simulated warehouse, where the topology of a warehouse is modeled as a randomly generated geometric graph.
Cite as

Heiko Hamann, Christine Markarian, Friedhelm Meyer auf der Heide, and Mostafa Wahby. Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hamann_et_al:LIPIcs.FUN.2018.22,
  author =	{Hamann, Heiko and Markarian, Christine and Meyer auf der Heide, Friedhelm and Wahby, Mostafa},
  title =	{{Pick, Pack, \& Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.22},
  URN =		{urn:nbn:de:0030-drops-88136},
  doi =		{10.4230/LIPIcs.FUN.2018.22},
  annote =	{Keywords: connected dominating set, online algorithm, competitive analysis, geometric graph, robot warehouse, recharging stations}
}
Document
DOI: 10.4230/DagSemProc.08441.2
08441 Final Report – Emerging Uses and Paradigms for Dynamic Binary Translation

Authors: Erik Altman, Bruce R. Childers, Robert Cohn, Jack Davidson, Koen De Brosschere, Bjorn De Sutter, Anton M. Ertl, Michael Franz, Yuan Gu, Matthias Hauswirth, Thomas Heinz, Wei-Chung Hsu, Jens Knoop, Andreas Krall, Naveen Kumar, Jonas Maebe, Robert Muth, Xavier Rival, Erven Rohou, Roni Rosner, Mary Lou Soffa, Jens Troeger, and Christopher Vick

Published in: Dagstuhl Seminar Proceedings, Volume 8441, Emerging Uses and Paradigms for Dynamic Binary Translation (2009)

Abstract
Software designers and developers face many problems in designing, building, deploying, and maintaining cutting-edge software applications–reliability,security,performance,power,legacy code,use of multi-core platforms,and maintenance are just a few of the issues that must be considered. Many of these issues are fundamental parts of the grand challenges in computer science such as reliability and security.
Cite as

Erik Altman, Bruce R. Childers, Robert Cohn, Jack Davidson, Koen De Brosschere, Bjorn De Sutter, Anton M. Ertl, Michael Franz, Yuan Gu, Matthias Hauswirth, Thomas Heinz, Wei-Chung Hsu, Jens Knoop, Andreas Krall, Naveen Kumar, Jonas Maebe, Robert Muth, Xavier Rival, Erven Rohou, Roni Rosner, Mary Lou Soffa, Jens Troeger, and Christopher Vick. 08441 Final Report – Emerging Uses and Paradigms for Dynamic Binary Translation. In Emerging Uses and Paradigms for Dynamic Binary Translation. Dagstuhl Seminar Proceedings, Volume 8441, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{altman_et_al:DagSemProc.08441.2,
  author =	{Altman, Erik and Childers, Bruce R. and Cohn, Robert and Davidson, Jack and De Brosschere, Koen and De Sutter, Bjorn and Ertl, Anton M. and Franz, Michael and Gu, Yuan and Hauswirth, Matthias and Heinz, Thomas and Hsu, Wei-Chung and Knoop, Jens and Krall, Andreas and Kumar, Naveen and Maebe, Jonas and Muth, Robert and Rival, Xavier and Rohou, Erven and Rosner, Roni and Soffa, Mary Lou and Troeger, Jens and Vick, Christopher},
  title =	{{08441 Final Report – Emerging Uses and Paradigms for Dynamic Binary Translation}},
  booktitle =	{Emerging Uses and Paradigms for Dynamic Binary Translation},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8441},
  editor =	{Bruce R. Childers and Jack Davidson and Koen De Bosschere and Mary Lou Soffa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08441.2},
  URN =		{urn:nbn:de:0030-drops-18888},
  doi =		{10.4230/DagSemProc.08441.2},
  annote =	{Keywords: Dynamic binary translation, Virtual machines}
}
Document
DOI: 10.4230/DagSemProc.06061.9
The Factorized Distribution Algorithm and the Minimum Relative Entropy Principle

Authors: Heinz Mühlenbein and Robin Höns

Published in: Dagstuhl Seminar Proceedings, Volume 6061, Theory of Evolutionary Algorithms (2006)

Abstract
We assume that the function to be optimized is additively decomposed (ADF). Then the interaction graph $G_{ADF}$ can be used to compute exact or approximate factorizations. For many practical problems only approximate factorizations lead to efficient optimization algorithms. The relation between the approximation used by the FDA algorithm and the minimum relative entropy principle is discussed. A new algorithm is presented, derived from the Bethe-Kikuchi approach in statistical physics. It minimizes the relative entropy to a Boltzmann distribution with fixed $eta$. We shortly compare different factorizations and algorithms within the FDA software. We use 2-d Ising spin glass problems and Kaufman's n-k function as examples.
Cite as

Heinz Mühlenbein and Robin Höns. The Factorized Distribution Algorithm and the Minimum Relative Entropy Principle. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 6061, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{muhlenbein_et_al:DagSemProc.06061.9,
  author =	{M\"{u}hlenbein, Heinz and H\"{o}ns, Robin},
  title =	{{The Factorized Distribution Algorithm and the Minimum Relative Entropy Principle}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--27},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06061.9},
  URN =		{urn:nbn:de:0030-drops-5973},
  doi =		{10.4230/DagSemProc.06061.9},
  annote =	{Keywords: Junction tree, minimum relative entropy, maximum likelihood, Bethe-Kikuchi approximation}
}
  • Refine by Author
  • 2 Bodden, Eric
  • 1 Altman, Erik
  • 1 Childers, Bruce R.
  • 1 Cohn, Robert
  • 1 Davidson, Jack
  • Show More...

  • Refine by Classification
  • 1 Software and its engineering → Automated static analysis
  • 1 Software and its engineering → Software notations and tools
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 Bethe-Kikuchi approximation
  • 1 C/C++
  • 1 Dynamic binary translation
  • 1 IDE
  • 1 Inter-procedural static analysis
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2006
  • 1 2009
  • 1 2018
  • 1 2019
  • 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