Bernd Finkbeiner

Bernd Finkbeiner

Auto-generated profile, based on publicly available information

Bernd Finkbeiner

CISPA Helmholtz Center for Information Security

Research Focus & Metrics

Academic Career Length

20Years (2007-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
15 July 2021
Verified
Book Chapter
Open access
PDF file
JBJan Baumeister
Jan Baumeister
NCNorine Coenen
Norine Coenen
BBBorzoo Bonakdarpour
Borzoo Bonakdarpour
BFBernd Finkbeiner
Bernd Finkbeiner
CSCésar Sánchez
César Sánchez
Hyperpropertiesare properties of computational systems that require more than one trace to evaluate, e.g., many information-flow security and concurrency requirements. Where a trace property defines a set of traces, a hyperproperty defines a set of sets of traces. The temporal logics HyperLTL and HyperCTL* have been proposed to express hyperproperties. However, their semantics aresynchronousin the sense that all traces proceed at the same speed and are evaluated at the same position. This precludes the use of these logics to analyze systems whose traces can proceed at different speeds and allow that different traces take stuttering steps independently. To solve this problem in this paper, we propose anasynchronousvariant of HyperLTL. On the negative side, we show that the model-checking problem for this variant is undecidable. On the positive side, we identify a decidable fragment which covers a rich set of formulas with practical applications. We also propose two model-checking algorithms that reduce our problem to the HyperLTL model-checking problem in the synchronous semantics.

7 August 2022
Verified
Book Chapter
Open access
PDF file
RBRaven Beutner
Raven Beutner
BFBernd Finkbeiner
Bernd Finkbeiner
Temporal hyperproperties are system properties that relate multiple execution traces. For (finite-state) hardware, temporal hyperproperties are supported by model checking algorithms, and tools for general temporal logics like HyperLTL exist. For (infinite-state) software, the analysis of temporal hyperproperties has, so far, been limited tok-safety properties, i.e., properties that stipulate the absence of a bad interaction between anyktraces. In this paper, we present an automated method for the verification of $$\forall ^k\exists ^l$$∀k∃l -safety properties in infinite-state systems. A $$\forall ^k\exists ^l$$∀k∃l -safety property stipulates that for anyktraces, thereexistltraces such that the resulting $$k+l$$k+l traces do not interact badly. This combination of universal and existential quantification enables us to express many properties beyondk-safety, including, for example, generalized non-interference or program refinement. Our method is based on a strategy-based instantiation of existential trace quantification combined with a program reduction, both in the context of a fixed predicate abstraction. Notably, our framework allows for mutual dependence of strategy and reduction.

25 June 2019 in Formal Methods in System Design
Verified
Journal Article
Open access
PDF file
BFBernd Finkbeiner
Bernd Finkbeiner
CHChristopher Hahn
Christopher Hahn
MSMarvin Stenger
Marvin Stenger
LTLeander Tentrup
Leander Tentrup
Hyperproperties, such as non-interference and observational determinism, relate multiple system executions to each other. They are not expressible in standard temporal logics, like LTL, CTL, and CTL*, and thus cannot be monitored with standard runtime verification techniques. \(\text {HyperLTL}\) extends linear-time temporal logic (LTL) with explicit quantification over traces in order to express hyperproperties. We investigate the runtime verification problem of \(\text {HyperLTL}\) formulas for three different input models: (1) The parallel model, where a fixed number of system executions is processed in parallel. (2) The unbounded sequential model, where system executions are processed sequentially, one execution at a time. In this model, the number of incoming executions is a-priori unbounded and may in fact grow forever. (3) The bounded sequential model where the traces are processed sequentially and the number of incoming executions is bounded. We show that the existence of a bound in the parallel and bounded sequential models leads to a different notion of monitorability than in the unbounded sequential model. We show that deciding the monitoriability problem for alternation-free HyperLTL is \(\textsc {PSpace}\)-complete while the problem is undecidable in general. For every input model, we provide monitoring algorithms along with run-time and storage optimizations. By recognizing properties of specifications such as reflexivity, symmetry, and transitivity, we reduce the number of comparisons between traces. For the sequential models, we present a technique that minimizes the number of traces that need to be stored. We evaluate our optimizations, showing that this leads to a more scalable monitoring and, in particular, a significantly lower memory consumption.

20 September 2016
Verified
Book Chapter
Closed access
PDF file
PFPeter Faymonville
Peter Faymonville
BFBernd Finkbeiner
Bernd Finkbeiner
SSSebastian Schirmer
Sebastian Schirmer
HTHazem Torfah
Hazem Torfah

22 April 2023
Verified
Book Chapter
Open access
PDF file
RBRaven Beutner
Raven Beutner
BFBernd Finkbeiner
Bernd Finkbeiner
HyperLTL is a temporal logic that can express hyperproperties, i.e., properties that relate multiple execution traces of a system. Such properties are becoming increasingly important and naturally occur, e.g., in information-flow control, robustness, mutation testing, path planning, and causality checking. Thus far, complete model checking tools for HyperLTL have been limited to alternation-free formulas, i.e., formulas that use only universal or only existential trace quantification. Properties involving quantifier alternations could only be handled in an incomplete way, i.e., the verification might fail even though the property holds. In this paper, we present , an explicit-state automata-based model checker that supports full HyperLTL and is complete for properties with arbitrary quantifier alternations. We show that language inclusion checks can be integrated into HyperLTL verification, which allows to benefit from a range of existing inclusion-checking tools. We evaluate on a broad set of benchmarks drawn from different areas in the literature and compare it with existing (incomplete) methods for HyperLTL verification.

14 July 2020
Verified
Book Chapter
Open access
PDF file
JBJan Baumeister
Jan Baumeister
BFBernd Finkbeiner
Bernd Finkbeiner
SSSebastian Schirmer
Sebastian Schirmer
MSMaximilian Schwenger
Maximilian Schwenger
CTChristoph Torens
Christoph Torens
The autonomous control of unmanned aircraft is a highly safety-critical domain with great economic potential in a wide range of application areas, including logistics, agriculture, civil engineering, and disaster recovery. We report on the development of a dynamic monitoring framework for the DLR ARTIS (Autonomous Rotorcraft Testbed for Intelligent Systems) family of unmanned aircraft based on the formal specification language RTLola. RTLola is a stream-based specification language for real-time properties. An RTLola specification of hazardous situations and system failures is statically analyzed in terms of consistency and resource usage and then automatically translated into an FPGA-based monitor. Our approach leads to highly efficient, parallelized monitors with formal guarantees on the noninterference of the monitor with the normal operation of the autonomous system.