Open list in Research Information System
2018
Validity of Software Verification Results on Approximate Hardware
T. Isenberg, M. Jakobs, F. Pauck, H. Wehrheim, IEEE Embedded Systems Letters (2018), pp. 22-25
DOI
Abstract
Approximate computing (AC) is an emerging paradigm for energy-efficient computation. The basic idea of AC is to sacrifice high precision for low energy by allowing hardware to carry out “approximately correct” calculations. This provides a major challenge for software quality assurance: programs successfully verified to be correct might be erroneous on approximate hardware. In this letter, we present a novel approach for determining under what conditions a software verification result is valid for approximate hardware. To this end, we compute the allowed tolerances for AC hardware from successful verification runs. More precisely, we derive a set of constraints which—when met by the AC hardware—guarantees the verification result to carry over to AC. On the practical side, we furthermore: 1) show how to extract tolerances from verification runs employing predicate abstraction as verification technology and 2) show how to check such constraints on hardware designs. We have implemented all techniques, and exemplify them on example C programs and a number of recently proposed approximate adders.
2017
Policy Dependent and Independent Information Flow Analyses
M. Töws, H. Wehrheim, in: Formal Methods and Software Engineering - 19th International Conference on Formal Engineering Methods, {ICFEM} 2017, Xi'an, China, November 13-17, 2017, Proceedings, 2017, pp. 362--378
Compact Proof Witnesses
M. Jakobs, H. Wehrheim, in: NASA Formal Methods: 9th International Symposium, 2017, pp. 389-403
DOI
Abstract
Proof witnesses are proof artifacts showing correctness of programs wrt. safety properties. The recent past has seen a rising interest in witnesses as (a) proofs in a proof-carrying-code context, (b) certificates for the correct functioning of verification tools, or simply (c) exchange formats for (partial) verification results. As witnesses in all theses scenarios need to be stored and processed, witnesses are required to be as small as possible. However, software verification tools – the prime suppliers of witnesses – do not necessarily construct small witnesses. In this paper, we present a formal account of proof witnesses. We introduce the concept of weakenings, reducing the complexity of proof witnesses while preserving the ability of witnessing safety. We develop aweakening technique for a specific class of program analyses, and prove it to be sound. Finally, we experimentally demonstrate our weakening technique to indeed achieve a size reduction of proof witnesses.
Predicting Rankings of Software Verification Tools
M. Czech, E. Hüllermeier, M. Jakobs, H. Wehrheim, in: Proceedings of the 3rd International Workshop on Software Analytics, 2017, pp. 23-26
DOI
Abstract
Today, software verification tools have reached the maturity to be used for large scale programs. Different tools perform differently well on varying code. A software developer is hence faced with the problem of choosing a tool appropriate for her program at hand. A ranking of tools on programs could facilitate the choice. Such rankings can, however, so far only be obtained by running all considered tools on the program.In this paper, we present a machine learning approach to predicting rankings of tools on programs. The method builds upon so-called label ranking algorithms, which we complement with appropriate kernels providing a similarity measure for programs. Our kernels employ a graph representation for software source code that mixes elements of control flow and program dependence graphs with abstract syntax trees. Using data sets from the software verification competition SV-COMP, we demonstrate our rank prediction technique to generalize well and achieve a rather high predictive accuracy (rank correlation > 0.6).
Proof-Carrying Hardware via Inductive Invariants
T. Isenberg, M. Platzner, H. Wehrheim, T. Wiersema, ACM Transactions on Design Automation of Electronic Systems (2017), pp. 61:1--61:23
DOI
Abstract
Proof-carrying hardware (PCH) is a principle for achieving safety for dynamically reconfigurable hardware systems. The producer of a hardware module spends huge effort when creating a proof for a safety policy. The proof is then transferred as a certificate together with the configuration bitstream to the consumer of the hardware module, who can quickly verify the given proof. Previous work utilized SAT solvers and resolution traces to set up a PCH technology and corresponding tool flows. In this article, we present a novel technology for PCH based on inductive invariants. For sequential circuits, our approach is fundamentally stronger than the previous SAT-based one since we avoid the limitations of bounded unrolling. We contrast our technology to existing ones and show that it fits into previously proposed tool flows. We conduct experiments with four categories of benchmark circuits and report consumer and producer runtime and peak memory consumption, as well as the size of the certificates and the distribution of the workload between producer and consumer. Experiments clearly show that our new induction-based technology is superior for sequential circuits, whereas the previous SAT-based technology is the better choice for combinational circuits.
Programs from Proofs: A Framework for the Safe Execution of Untrusted Software
M. Jakobs, H. Wehrheim, ACM Transactions on Programming Languages and Systems (2017), pp. 7:1-7:56
DOI
Abstract
Today, software is traded worldwide on global markets, with apps being downloaded to smartphones within minutes or seconds. This poses, more than ever, the challenge of ensuring safety of software in the face of (1) unknown or untrusted software providers together with (2) resource-limited software consumers. The concept of Proof-Carrying Code (PCC), years ago suggested by Necula, provides one framework for securing the execution of untrusted code. PCC techniques attach safety proofs, constructed by software producers, to code. Based on the assumption that checking proofs is usually much simpler than constructing proofs, software consumers should thus be able to quickly check the safety of software. However, PCC techniques often suffer from the size of certificates (i.e., the attached proofs), making PCC techniques inefficient in practice.In this article, we introduce a new framework for the safe execution of untrusted code called Programs from Proofs (PfP). The basic assumption underlying the PfP technique is the fact that the structure of programs significantly influences the complexity of checking a specific safety property. Instead of attaching proofs to program code, the PfP technique transforms the program into an efficiently checkable form, thus guaranteeing quick safety checks for software consumers. For this transformation, the technique also uses a producer-side automatic proof of safety. More specifically, safety proving for the software producer proceeds via the construction of an abstract reachability graph (ARG) unfolding the control-flow automaton (CFA) up to the degree necessary for simple checking. To this end, we combine different sorts of software analysis: expensive analyses incrementally determining the degree of unfolding, and cheap analyses responsible for safety checking. Out of the abstract reachability graph we generate the new program. In its CFA structure, it is isomorphic to the graph and hence another, this time consumer-side, cheap analysis can quickly determine its safety.Like PCC, Programs from Proofs is a general framework instantiable with different sorts of (expensive and cheap) analysis. Here, we present the general framework and exemplify it by some concrete examples. We have implemented different instantiations on top of the configurable program analysis tool CPAchecker and report on experiments, in particular on comparisons with PCC techniques.
2016
Just test what you cannot verify!
M. Czech, M. Jakobs, H. Wehrheim, in: Software Engineering 2016, 2016, pp. 17-18
Abstract
Software verification is an established method to ensure software safety. Nevertheless, verification still often fails, either because it consumes too much resources, e.g., time or memory, or the technique is not mature enough to verify the property. Often then discarding the partial verification, the validation process proceeds with techniques like testing.To enable standard testing to profit from previous, partial verification, we use a summary of the verification effort to simplify the program for subsequent testing. Our techniques use this summary to construct a residual program which only contains program paths with unproven assertions. Afterwards, the residual program can be used with standard testing tools.Our first experiments show that testing profits from the partial verification.The test effort is reduced and combined verification and testing is faster than a complete verification.
A Formal Approach to Error Localization and Correction in Service Compositions
J. Krämer, H. Wehrheim, in: Proceedings of the 1st International Workshop on Formal to Practical Software Verification and Composition (VeryComp 2016), 2016, pp. 445--457
DOI
Abstract
Error detection, localization and correction are time-intensive tasks in software development, but crucial to deliver functionally correct products. Thus, automated approaches to these tasks have been intensively studied for standard software systems. For model-based software systems, the situation is different. While error detection is still well-studied, error localization and correction is a less-studied domain. In this paper, we examine error localization and correction for models of service compositions. Based on formal definitions of error and correction in this context, we show that the classical approach of error localization and correction, i.e. first determining a set of suspicious statements and then proposing changes to these statements, is ineffective in our context. In fact, it lessens the chance to succeed in finding a correction at all.In this paper, we introduce correction proposal as a novel approach on error correction in service compositions integrating error localization and correction in one combined step. In addition, we provide an algorithm to compute such correction proposals automatically.
A CEGAR Scheme for Information Flow Analysis
M. Töws, H. Wehrheim, in: Proceedings of the 18th International Conference on Formal Engineering Methods (ICFEM 2016), 2016, pp. 466--483
DOI
Abstract
Information flow analysis studies the flow of data between program entities (e.g. variables), where the allowed flow is specified via security policies. Typical information flow analyses compute a conservative (over-)approximation of the flows in a program. Such an analysis may thus signal non-existing violations of the security policy.In this paper, we propose a new technique for inspecting the reported violations (counterexamples) for spuriousity. Similar to counterexample-guided-abstraction-refinement (CEGAR) in software verification, we use the result of this inspection to improve the next round of the analysis. We prove soundness of this scheme.
Verification of AUTOSAR Software Architectures with Timed Automata
S. Beringer, H. Wehrheim, in: Critical Systems: Formal Methods and Automated Verification - Joint 21st International Workshop on Formal Methods for Industrial Critical Systems and 16th International Workshop on Automated Verification of Critical Systems, FMICS-AVoCS 2016, Pisa, Italy, September 26-28, 2016, Proceedings, 2016, pp. 189--204
Verification of Concurrent Programs on Weak Memory Models
O. Travkin, H. Wehrheim, in: Theoretical Aspects of Computing - {ICTAC} 2016 - 13th International Colloquium, Taipei, Taiwan, ROC, October 24-31, 2016, Proceedings, 2016, pp. 3--24
Proving Opacity of a Pessimistic {STM}
S. Doherty, B. Dongol, J. Derrick, G. Schellhorn, H. Wehrheim, in: 20th International Conference on Principles of Distributed Systems, {OPODIS} 2016, December 13-16, 2016, Madrid, Spain, 2016, pp. 35:1--35:17
A short survey on using software error localization for service compositions
J. Krämer, H. Wehrheim, in: Proceedings of the 5th European Conference on Service-Oriented and Cloud Computing (ESOCC 2016), 2016, pp. 248--262
DOI
Abstract
In modern software development, paradigms like component-based software engineering (CBSE) and service-oriented architectures (SOA) emphasize the construction of large software systems out of existing components or services. Therein, a service is a self-contained piece of software, which adheres to a specified interface. In a model-based software design, this interface constitutes our sole knowledge of the service at design time, while service implementations are not available. Therefore, correctness checks or detection of potential errors in service compositions has to be carried out without the possibility of executing services. This challenges the usage of standard software error localization techniques for service compositions. In this paper, we review state-of-the-art approaches for error localization of software and discuss their applicability to service compositions.
Towards a Thread-Local Proof Technique for Starvation Freedom
G. Schellhorn, O. Travkin, H. Wehrheim, in: Integrated Formal Methods - 12th International Conference, {IFM} 2016, Reykjavik, Iceland, June 1-5, 2016, Proceedings, 2016, pp. 193--209
On-The-Fly Construction of Provably Correct Service Compositions - Templates and Proofs
S. Walther, H. Wehrheim, Science of Computer Programming (2016), pp. 2--23
DOI
Abstract
Today, service compositions often need to be assembled or changed on-the-fly, which leaves only little time for quality assurance. Moreover, quality assurance is complicated by service providers only giving information on their services in terms of domain specific concepts with only limited semantic meaning.In this paper, we propose a method for constructing service compositions based on pre-verified templates. Templates, given as workflow descriptions, are typed over a (domain-independent) template ontology defining concepts and predicates. Their meaning is defined by an abstract semantics, leaving the specific meaning of ontology concepts open, however, only up to given ontology rules. Templates are proven correct using a Hoare-style proof calculus, extended by a specific rule for service calls. Construction of service compositions amounts to instantiation of templates with domain-specific services. Correctness of an instantiation can then simply be checked by verifying that the domain ontology (a) adheres to the rules of the template ontology, and (b) fulfills the constraints of the employed template.
2015
Just test what you cannot verify!
M. Czech, M. Jakobs, H. Wehrheim, in: Fundamental Approaches to Software Engineering, 2015, pp. 100-114
DOI
Abstract
Today, software verification is an established analysis method which can provide high guarantees for software safety. However, the resources (time and/or memory) for an exhaustive verification are not always available, and analysis then has to resort to other techniques, like testing. Most often, the already achieved partial verification results arediscarded in this case, and testing has to start from scratch.In this paper, we propose a method for combining verification and testing in which testing only needs to check the residual fraction of an uncompleted verification. To this end, the partial results of a verification run are used to construct a residual program (and residual assertions to be checked on it). The residual program can afterwards be fed into standardtesting tools. The proposed technique is sound modulo the soundness of the testing procedure. Experimental results show that this combinedusage of verification and testing can significantly reduce the effort for the subsequent testing.
Verifying Opacity of a Transactional Mutex Lock
J. Derrick, B. Dongol, G. Schellhorn, O. Travkin, H. Wehrheim, in: {FM} 2015: Formal Methods - 20th International Symposium, Oslo, Norway, June 24-26, 2015, Proceedings, 2015, pp. 161--177
{TSO} to {SC} via Symbolic Execution
H. Wehrheim, O. Travkin, in: Hardware and Software: Verification and Testing - 11th International Haifa Verification Conference, {HVC} 2015, Haifa, Israel, November 17-19, 2015, Proceedings, 2015, pp. 104--119
Programs from Proofs of Predicated Dataflow Analyses
M. Jakobs, H. Wehrheim, in: Proceedings of the 30th Annual ACM Symposium on Applied Computing, 2015, pp. 1729-1736
DOI
Abstract
Programs from Proofs" is a generic method which generates new programs out of correctness proofs of given programs. The technique ensures that the new and given program are behaviorally equivalent and that the new program is easily verifiable, thus serving as an alternative to proof-carrying code concepts. So far, this generic method has one instantiation that verifies type-state properties of programs. In this paper, we present a whole range of new instantiations, all based on data ow analyses. More precisely, we show how an imprecise but fast data ow analysis can be enhanced with a predicate analysis as to yield a precise but expensive analysis. Out of the safety proofs of this analysis, we generate new programs, again behaviorally equivalent to the given ones, which are easily verifiable" in the sense that now the data ow analysis alone can yield precise results. An experimental evaluation practically supports our claim of easy verification.
Temporal plans for software architecture reconfiguration
S. Ziegert, H. Wehrheim, Computer Science - R & D (2015), pp. 303--320
Grammar-based model transformations: Definition, execution, and quality properties
G. Besova, D. Steenken, H. Wehrheim, Computer Languages, Systems & Structures (2015), pp. 116-138
DOI
Abstract
Model transformation is a key concept in model-driven software engineering. The definition of model transformations is usually based on meta-models describing the abstract syntax of languages. While meta-models are thereby able to abstract from uperfluous details of concrete syntax, they often loose structural information inherent in languages, like information on model elements always occurring together in particular shapes. As a consequence, model transformations cannot naturally re-use language structures, thus leading to unnecessary complexity in their development as well as in quality assurance.In this paper, we propose a new approach to model transformation development which allows to simplify the developed transformations and improve their quality via the exploitation of the languages׳ structures. The approach is based on context-free graph grammars and transformations defined by pairing productions of source and target grammars. We show that such transformations have important properties: they terminate and are sound, complete, and deterministic.
2014
Integrating Software and Hardware Verification
M. Jakobs, M. Platzner, T. Wiersema, H. Wehrheim, in: Proceedings of the 11th International Conference on Integrated Formal Methods (iFM), 2014, pp. 307-322
DOI
Abstract
Verification of hardware and software usually proceeds separately, software analysis relying on the correctness of processors executing instructions. This assumption is valid as long as the software runs on standard CPUs that have been extensively validated and are in wide use. However, for processors exploiting custom instruction set extensions to meet performance and energy constraints the validation might be less extensive, challenging the correctness assumption.In this paper we present an approach for integrating software analyses with hardware verification, specifically targeting custom instruction set extensions. We propose three different techniques for deriving the properties to be proven for the hardware implementation of a custom instruction in order to support software analyses. The techniques are designed to explore the trade-off between generality and efficiency and span from proving functional equivalence over checking the rules of a particular analysis domain to verifying actual pre and post conditions resulting from program analysis. We demonstrate and compare the three techniques on example programs with custom instructions, using stateof-the-art software and hardware verification techniques.
Programs from Proofs -- Approach and Applications
D. Wonisch, A. Schremmer, H. Wehrheim, in: Proceedings of the Software Engineering Conference (SE), 2014, pp. 67-68
Download
Abstract
Proof-carrying code approaches aim at safe execution of untrusted code by having the code producer attach a safety proof to the code which the code consumer only has to validate. Depending on the type of safety property, proofs can however become quite large and their validation - though faster than their construction - still time consuming. In this paper we introduce a new concept for safe execution of untrusted code. It keeps the idea of putting the time consuming part of proving on the side of the code producer, however, attaches no proofs to code anymore but instead uses the proof to transform the program into an equivalent but more efficiently verifiable program. Code consumers thus still do proving themselves, however, on a computationally inexpensive level only. Experimental results show that the proof effort can be reduced by several orders of magnitude, both with respect to time and space.
Quiescent Consistency: Defining and Verifying Relaxed Linearizability
J. Derrick, B. Dongol, G. Schellhorn, B. Tofan, O. Travkin, H. Wehrheim, in: {FM} 2014: Formal Methods - 19th International Symposium, Singapore, May 12-16, 2014. Proceedings, 2014, pp. 200--214
Grammar-based model transformations
G. Besova, D. Steenke, H. Wehrheim, in: Proceedings 3rd Workshop on Model Driven Approaches in System Development (MDASD), 2014, pp. 1601-1610
DOI
Abstract
Model transformation is a key concept in modeldrivensoftware engineering. The definition of model transformationsis usually based on meta-models describing the abstractsyntax of languages. While meta-models are thereby able to abstractfrom superfluous details of concrete syntax, they often loosestructural information inherent in languages, like information onmodel elements always occurring together in particular shapes.As a consequence, model transformations cannot naturally re-uselanguage structures, thus leading to unnecessary complexity intheir development as well as analysis.In this paper, we propose a new approach to model transformationdevelopment which allows to simplify and improve thequality of the developed transformations via the exploitation ofthe languages’ structures. The approach is based on context-freegrammars and transformations defined by pairing productions ofsource and target grammars. We show that such transformationsexhibit three important characteristics: they are sound, completeand deterministic.
Certification for Configurable Program Analysis
M. Jakobs, H. Wehrheim, in: Proceedings of the 21st International Symposium on Model Checking of Software (SPIN), 2014, pp. 30-39
DOI
Abstract
Configurable program analysis (CPA) is a generic concept for the formalization of different software analysis techniques in a single framework. With the tool CPAchecker, this framework allows for an easy configuration and subsequent automatic execution of analysis procedures ranging from data-flow analysis to model checking. The focus of the tool CPAchecker is thus on analysis. In this paper, we study configurability from the point of view of software certification. Certification aims at providing (via a prior analysis) a certificate of correctness for a program which is (a) tamper-proof and (b) more efficient to check for validity than a full analysis. Here, we will show how, given an analysis instance of a CPA, to construct a corresponding sound certification instance, thereby arriving at configurable program certification. We report on experiments with certification based on different analysis techniques, and in particular explain which characteristics of an underlying analysis allow us to design an efficient (in the above (b) sense) certification procedure.
Handling {TSO} in Mechanized Linearizability Proofs
O. Travkin, H. Wehrheim, in: Hardware and Software: Verification and Testing - 10th International Haifa Verification Conference, {HVC} 2014, Haifa, Israel, November 18-20, 2014. Proceedings, 2014, pp. 132--147
Verified Service Compositions by Template-Based Construction
S. Walther, H. Wehrheim, in: Proceedings of the 11th International Symposium on Formal Aspects of Component Software (FACS), 2014, pp. 31-48
DOI
Abstract
Today, service compositions often need to be assembled or changed on-the-fly, which leaves only little time for quality assurance. Moreover, quality assurance is complicated by service providers only giving information on their services in terms of domain specific concepts with only limited semantic meaning. In this paper, we propose a method to construct service compositions based on pre-verifiedtemplates. Templates, given as workflow descriptions, are typed over a (domain-independent) template ontology defining concepts and predicates. Templates are proven correct using an abstract semantics, leaving the specific meaning of ontology concepts open, however, only up to given ontology rules. Construction of service compositions amounts to instantiation of templates with domain-specific services.Correctness of an instantiation can then simply be checked by verifying that the domain ontology(a) adheres to the rules of the template ontology, and (b) fulfills the constraints of the employed template.
Timed Automata Verification via {IC3} with Zones
T. Isenberg, H. Wehrheim, in: Formal Methods and Software Engineering - 16th International Conference on Formal Engineering Methods, {ICFEM} 2014, Luxembourg, Luxembourg, November 3-5, 2014. Proceedings, 2014, pp. 203--218
Managing {LTL} Properties in Event-B Refinement
S. A. Schneider, H. Treharne, H. Wehrheim, D. M. Williams, in: Integrated Formal Methods - 11th International Conference, {IFM} 2014, Bertinoro, Italy, September 9-11, 2014, Proceedings, 2014, pp. 221--237
2013
Knowledge-Based Verification of Service Compositions - An SMT approach
S. Walther, H. Wehrheim, in: Proceedings of the 18th IEEE International Conference on Engineering of Complex Computer Systems (ICECCS), 2013, pp. 24 - 32
DOI
Abstract
In the Semantic (Web) Services area, services are considered black boxes with a semantic description of their interfaces as to allow for precise service selection and configuration. The semantic description is usually grounded on domain-specific concepts as modeled in ontologies. This accounts for types used in service signatures, but also predicates occurring in preconditions and effects of services. Ontologies, in particular those enhanced with rules, capture the knowledge of domain experts on properties of and relations between domain concepts. In this paper, we present a verification technique for service compositions which makes use of this domain knowledge. We consider a service composition to be an assembly of services of which we just know signatures, preconditions, and effects. We aim at proving that a composition satisfies a (user-defined) requirement, specified in terms of guaranteed preconditions and required postconditions. As an underlying verification engine we use an SMT solver. To take advantage of the domain knowledge (and often, to enable verification at all), the knowledge is fed into the solver in the form of sorts, uninterpreted functions and in particular assertions as to enhance the solver’s reasoning capabilities. Thereby, we allow for deductions within a domain previously unknown to the solver. We exemplify our technique on a case study from the area of water network optimization software.
Programs from Proofs – A PCC Alternative
D. Wonisch, A. Schremmer, H. Wehrheim, in: Proceedings of the 25th International Conference on Computer Aided Verification (CAV), 2013, pp. 912-927
DOI
Abstract
Proof-carrying code approaches aim at safe execution of untrusted code by having the code producer attach a safety proof to the code which the code consumer only has to validate. Depending on the type of safety property, proofs can however become quite large and their validation - though faster than their construction - still time consuming. In this paper we introduce a new concept for safe execution of untrusted code. It keeps the idea of putting the time consuming part of proving on the side of the code producer, however, attaches no proofs to code anymore but instead uses the proof to transform the program into an equivalent but more efficiently verifiable program. Code consumers thus still do proving themselves, however, on a computationally inexpensive level only. Experimental results show that the proof effort can be reduced by several orders of magnitude, both with respect to time and space.
Bounded Model Checking of Graph Transformation Systems via {SMT} Solving
T. Isenberg, D. Steenken, H. Wehrheim, in: Formal Techniques for Distributed Systems - Joint {IFIP} {WG} 6.1 International Conference, {FMOODS/FORTE} 2013, Held as Part of the 8th International Federated Conference on Distributed Computing Techniques, DisCoTec 2013, Florence, Italy, June 3-5, 2013. Proceedings, 2013, pp. 178--192
{SPIN} as a Linearizability Checker under Weak Memory Models
O. Travkin, A. Mütze, H. Wehrheim, in: Hardware and Software: Verification and Testing - 9th International Haifa Verification Conference, {HVC} 2013, Haifa, Israel, November 5-7, 2013, Proceedings, 2013, pp. 311--326
Zero Overhead Runtime Monitoring
D. Wonisch, A. Schremmer, H. Wehrheim, in: Proceedings of the 11th International Conference on Software Engineering and Formal Methods (SEFM), 2013, pp. 244-258
DOI
Abstract
Runtime monitoring aims at ensuring program safety by monitoring the program's behaviour during execution and taking appropriate action before a program violates some property.Runtime monitoring is in particular important when an exhaustive formal verification fails. While the approach allows for a safe execution of programs, it may impose a significant runtime overhead.In this paper, we propose a novel technique combining verification and monitoring which incurs no overhead during runtime at all. The technique proceeds by using the inconclusive result of a verification run as the basis for transforming the program into one where all potential points of failure are replaced by HALT statements. The new program is safe by construction, behaviourally equivalent to the original program (except for unsafe behaviour),and has the same performance characteristics.
A High-Level Semantics for Program Execution under Total Store Order Memory
B. Dongol, O. Travkin, J. Derrick, H. Wehrheim, in: Theoretical Aspects of Computing - {ICTAC} 2013 - 10th International Colloquium, Shanghai, China, September 4-6, 2013. Proceedings, 2013, pp. 177--194
2012
How to Prove Algorithms Linearisable
G. Schellhorn, H. Wehrheim, J. Derrick, in: Computer Aided Verification - 24th International Conference, {CAV} 2012, Berkeley, CA, USA, July 7-13, 2012 Proceedings, 2012, pp. 243--259
Predicate Analysis with Block-Abstraction Memoization
D. Wonisch, H. Wehrheim, in: Proceedings of the 14th International Conference on Formal Engineering Methods (ICFEM), 2012, pp. 332-347
DOI
Abstract
Predicate abstraction is an established technique for reducing the size of the state space during verification. In this paper, we extend predication abstraction with block-abstraction memoization (BAM), which exploits the fact that blocks are often executed several times in a program. The verification can thus benefit from caching the values of previous block analyses and reusing them upon next entry into a block. In addition to function bodies, BAM also performs well for nested loops. To further increase effectiveness, block memoization has been integrated with lazy abstraction adopting a lazy strategy for cache refinement. Together, this achieves significant performance increases: our tool (an implementation within the configurable program analysis framework CPAchecker) has won the Competition on Software Verification 2012 in the category “Overall”.
Heuristic-Guided Abstraction Refinement for Concurrent Systems
N. Timm, H. Wehrheim, M. Czech, in: Proceedings of the 14th International Conference on Formal Engineering Methods (ICFEM), 2012, pp. 348-363
DOI
Abstract
Predicate abstraction is an established technique in software verification. It inherently includes an abstraction refinement loop successively adding predicates until the right level of abstraction is found. For concurrent systems, predicate abstraction can be combined with spotlight abstraction, further reducing the state space by abstracting away certain processes. Refinement then has to decide whether to add a new predicate or a new process. Selecting the right predicates and processes is a crucial task: The positive effect of abstraction may be compromised by unfavourable refinement decisions. Here we present a heuristic approach to abstraction refinement. The basis for a decision is a set of refinement candidates, derived by multiple counterexample-generation. Candidates are evaluated with respect to their influence on other components in the system. Experimental results show that our technique can significantly speed up verification as compared to a naive abstraction refinement.
Weaving-based configuration and modular transformation of multi-layer systems
G. Besova, S. Walther, H. Wehrheim, S. Becker, in: Proceedings of the 15th International Conference on Model Driven Engineering Languages & Systems (MoDELS), 2012, pp. 776-792
DOI
Abstract
In model-driven development of multi-layer systems (e.g. application, platform and infrastructure), each layer is usually described by separate models. When generating analysis models or code, these separate models rst of all need to be linked. Hence, existing model transformations for single layers cannot be simply re-used. In this paper, we present a modular approach to the transformation of multi-layer systems. It employs model weaving to dene the interconnections between models of dierent layers. The weaving models themselves are subject to model transformations: The result of transforming a weaving model constitutes a conguration for the models obtained by transforming single layers, thereby allowing for a re-use of existing model transformations. We exemplify our approach by the generation of analysis models for component-based software.
2011
Sound and Complete Abstract Graph Transformation
D. Steenken, H. Wehrheim, D. Wonisch, in: Formal Methods, Foundations and Applications - 14th Brazilian Symposium, {SBMF} 2011, S{\~{a}}o Paulo, Brazil, September 26-30, 2011, Revised Selected Papers, 2011, pp. 92--107
A {CSP} Account of Event-B Refinement
S. Schneider, H. Treharne, H. Wehrheim, in: Proceedings 15th International Refinement Workshop, Refine@FM 2011, Limerick, Ireland, 20th June 2011., 2011, pp. 139--154
ReL: {A} Generic Refactoring Language for Specification and Execution
T. Ruhroth, H. Wehrheim, S. Ziegert, in: 37th {EUROMICRO} Conference on Software Engineering and Advanced Applications, {SEAA} 2011, Oulu, Finland, August 30 - September 2, 2011, 2011, pp. 83--90
2010
Showing Full Semantics Preservation in Model Transformation - {A} Comparison of Techniques
M. Hülsbusch, B. König, A. Rensink, M. Semenyak, C. Soltenborn, H. Wehrheim, in: Integrated Formal Methods - 8th International Conference, {IFM} 2010, Nancy, France, October 11-14, 2010. Proceedings, 2010, pp. 183--198
A {CSP} Approach to Control in Event-B
S. Schneider, H. Treharne, H. Wehrheim, in: Integrated Formal Methods - 8th International Conference, {IFM} 2010, Nancy, France, October 11-14, 2010. Proceedings, 2010, pp. 260--274
{SLAB:} {A} Certifying Model Checker for Infinite-State Concurrent Systems
K. Dräger, A. Kupriyanov, B. Finkbeiner, H. Wehrheim, in: Tools and Algorithms for the Construction and Analysis of Systems, 16th International Conference, {TACAS} 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, {ETAPS} 2010, Paphos, Cyprus, March 20-28, 2010. Proceedings, 2010, pp. 271--274
2009
Measure, Diagnose, Refactor: {A} Formal Quality Cycle for Software Models
T. Ruhroth, H. Voigt, H. Wehrheim, in: 35th Euromicro Conference on Software Engineering and Advanced Applications, {SEAA} 2009, Patras, Greece, August 27-29, 2009, Proceedings, 2009, pp. 360--367
2008
From {UML} Activities to {TAAL} - Towards Behaviour-Preserving Model Transformations
G. Engels, A. Kleppe, A. Rensink, M. Semenyak, C. Soltenborn, H. Wehrheim, in: Model Driven Architecture - Foundations and Applications, 4th European Conference, {ECMDA-FA} 2008, Berlin, Germany, June 9-13, 2008. Proceedings, 2008, pp. 94--109
Mechanizing a Correctness Proof for a Lock-Free Concurrent Stack
J. Derrick, G. Schellhorn, H. Wehrheim, in: Formal Methods for Open Object-Based Distributed Systems, 10th {IFIP} {WG} 6.1 International Conference, {FMOODS} 2008, Oslo, Norway, June 4-6, 2008, Proceedings, 2008, pp. 78--95
Decomposition for Compositional Verification
B. Metzler, H. Wehrheim, D. Wonisch, in: Formal Methods and Software Engineering, 10th International Conference on Formal Engineering Methods, {ICFEM} 2008, Kitakyushu-City, Japan, October 27-31, 2008. Proceedings, 2008, pp. 105--125
2007
Assuring Consistency of Business Process Models and Web Services Using Visual Contracts
G. Engels, B. Güldali, C. Soltenborn, H. Wehrheim, in: Applications of Graph Transformations with Industrial Relevance, Third International Symposium, {AGTIVE} 2007, Kassel, Germany, October 10-12, 2007, Revised Selected and Invited Papers, 2007, pp. 17--31
The Challenges of Building Advanced Mechatronic Systems
W. Schäfer, H. Wehrheim, in: International Conference on Software Engineering, {ISCE} 2007, Workshop on the Future of Software Engineering, {FOSE} 2007, May 23-25, 2007, Minneapolis, MN, {USA}, 2007, pp. 72--84
Analysis of {UML} Activities Using Dynamic Meta Modeling
G. Engels, C. Soltenborn, H. Wehrheim, in: Formal Methods for Open Object-Based Distributed Systems, 9th {IFIP} {WG} 6.1 International Conference, {FMOODS} 2007, Paphos, Cyprus, June 6-8, 2007, Proceedings, 2007, pp. 76--90
Proving Linearizability Via Non-atomic Refinement
J. Derrick, G. Schellhorn, H. Wehrheim, in: Integrated Formal Methods, 6th International Conference, {IFM} 2007, Oxford, UK, July 2-5, 2007, Proceedings, 2007, pp. 195--214
Refactoring Object-Oriented Specifications with Data and Processes
T. Ruhroth, H. Wehrheim, in: Formal Methods for Open Object-Based Distributed Systems, 9th {IFIP} {WG} 6.1 International Conference, {FMOODS} 2007, Paphos, Cyprus, June 6-8, 2007, Proceedings, 2007, pp. 236--251
2006
Incremental Slicing
H. Wehrheim, in: Formal Methods and Software Engineering, 8th International Conference on Formal Engineering Methods, {ICFEM} 2006, Macao, China, November 1-3, 2006, Proceedings, 2006, pp. 514--528
Model Transformations Incorporating Multiple Views
J. Derrick, H. Wehrheim, in: Algebraic Methodology and Software Technology, 11th International Conference, {AMAST} 2006, Kuressaare, Estonia, July 5-8, 2006, Proceedings, 2006, pp. 111--126
2005
Slicing Object-Z Specifications for Verification
I. Brückner, H. Wehrheim, in: {ZB} 2005: Formal Specification and Development in {Z} and B, 4th International Conference of {B} and {Z} Users, Guildford, UK, April 13-15, 2005, Proceedings, 2005, pp. 414--433
Slicing an Integrated Formal Method for Verification
I. Brückner, H. Wehrheim, in: Formal Methods and Software Engineering, 7th International Conference on Formal Engineering Methods, {ICFEM} 2005, Manchester, UK, November 1-4, 2005, Proceedings, 2005, pp. 360--374
Checking the Validity of Scenarios in {UML} Models
H. Rasch, H. Wehrheim, in: Formal Methods for Open Object-Based Distributed Systems, 7th {IFIP} {WG} 6.1 International Conference, {FMOODS} 2005, Athens, Greece, June 15-17, 2005, Proceedings, 2005, pp. 67--82
Non-atomic Refinement in {Z} and {CSP}
J. Derrick, H. Wehrheim, in: {ZB} 2005: Formal Specification and Development in {Z} and B, 4th International Conference of {B} and {Z} Users, Guildford, UK, April 13-15, 2005, Proceedings, 2005, pp. 24--44
2004
Linking {CSP-OZ} with {UML} and Java: {A} Case Study
M. Möller, E. Olderog, H. Rasch, H. Wehrheim, in: Integrated Formal Methods, 4th International Conference, {IFM} 2004, Canterbury, UK, April 4-7, 2004, Proceedings, 2004, pp. 267--286
2003
Preserving Properties Under Change
H. Wehrheim, in: Formal Methods for Components and Objects, Second International Symposium, {FMCO} 2003, Leiden, The Netherlands, November 4-7, 2003, Revised Lectures, 2003, pp. 330--343
Inheritance of Temporal Logic Properties
H. Wehrheim, in: Formal Methods for Open Object-Based Distributed Systems, 6th {IFIP} {WG} 6.1 International Conference, {FMOODS} 2003, Paris, France, November 19.21, 2003, Proceedings, 2003, pp. 79--93
Using Coupled Simulations in Non-atomic Refinement
J. Derrick, H. Wehrheim, in: {ZB} 2003: Formal Specification and Development in {Z} and B, Third International Conference of {B} and {Z} Users, Turku, Finland, June 4-6, 2003, Proceedings, 2003, pp. 127--147
Checking Consistency in {UML} Diagramms: Classes and State Machines
H. Rasch, H. Wehrheim, in: Formal Methods for Open Object-Based Distributed Systems, 6th {IFIP} {WG} 6.1 International Conference, {FMOODS} 2003, Paris, France, November 19.21, 2003, Proceedings, 2003, pp. 229--243
2002
Specification and Inheritance in {CSP-OZ}
E. Olderog, H. Wehrheim, in: Formal Methods for Components and Objects, First International Symposium, {FMCO} 2002, Leiden, The Netherlands, November 5-8, 2002, Revised Lectures, 2002, pp. 361--379
Checking Behavioural Subtypes via Refinement
H. Wehrheim, in: Formal Methods for Open Object-Based Distributed Systems V, {IFIP} {TC6/WG6.1} Fifth International Conference on Formal Methods for Open Object-Based Distributed Systems {(FMOODS} 2002), March 20-22, 2002, Enschede, The Netherlands, 2002, pp. 79--93
2001
A {CSP} View on {UML-RT} Structure Diagrams
C. Fischer, E. Olderog, H. Wehrheim, in: Fundamental Approaches to Software Engineering, 4th International Conference, {FASE} 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, {ETAPS} 2001 Genova, Italy, April 2-6, 2001, Proceedings, 2001, pp. 91--108
2000
Behavioural Subtyping and Property Preservation
H. Wehrheim, in: Formal Methods for Open Object-Based Distributed Systems IV, {IFIF} {TC6/WG6.1} Fourth International Conference on Formal Methods for Open Object-Based Distributed Systems {(FMOODS} 2000), September 6-8, 2000, Stanford, California, {USA}, 2000, pp. 213--231
Behavioural Subtyping Relations for Object-Oriented Formalisms
C. Fischer, H. Wehrheim, in: Algebraic Methodology and Software Technology. 8th International Conference, {AMAST} 2000, Iowa City, Iowa, USA, May 20-27, 2000, Proceedings, 2000, pp. 469--483
Specification of an Automatic Manufacturing System: {A} Case Study in Using Integrated Formal Methods
H. Wehrheim, in: Fundamental Approaches to Software Engineering, Third Internationsl Conference, {FASE} 2000, Held as Part of the European Joint Conferences on the Theory and Practice of Software, {ETAPS} 2000, Berlin, Germany, March 25 - April 2, 2000, Proceedings, 2000, pp. 334--348
1999
Data Abstraction for {CSP-OZ}
H. Wehrheim, in: FM'99 - Formal Methods, World Congress on Formal Methods in the Development of Computing Systems, Toulouse, France, September 20-24, 1999, Proceedings, Volume {II}, 1999, pp. 1028--1047
1998
An Algebraic Semantics for Message Sequence Chart Documents
T. Gehrke, M. Huhn, A. Rensink, H. Wehrheim, in: Formal Description Techniques and Protocol Specification, Testing and Verification, {FORTE} {XI} / {PSTV} XVIII'98, {IFIP} {TC6} {WG6.1} Joint International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols {(FORTE} {XI)} and Protocol Specification, Testing and Verification {(PSTV} XVIII), 3-6 November, 1998, Paris, France, 1998, pp. 3--18
Partial Order Reductions for Bisimulation Checking
M. Huhn, P. Niebert, H. Wehrheim, in: Foundations of Software Technology and Theoretical Computer Science, 18th Conference, Chennai, India, December 17-19, 1998, Proceedings, 1998, pp. 271--282
A Process Algebra Semantics for {MSC} Including Conditions
T. Gehrke, M. Huhn, P. Niebert, A. Rensink, H. Wehrheim, in: Formale Beschreibungstechniken f{\"{u}}r verteilte Systeme, 8. GI/ITG-Fachgespr{\"{a}}ch, Cottbus, 4. und 5. Juni 1998, 1998, pp. 185--196
1997
Dependency-Based Action Refinement
A. Rensink, H. Wehrheim, in: Mathematical Foundations of Computer Science 1997, 22nd International Symposium, MFCS'97, Bratislava, Slovakia, August 25-29, 1997, Proceedings, 1997, pp. 468--477
Dependency-Based Action Refinement
A. Rensink, H. Wehrheim, in: Mathematical Foundations of Computer Science 1997, 22nd International Symposium, MFCS'97, Bratislava, Slovakia, August 25-29, 1997, Proceedings, 1997, pp. 468--477
1996
Causal Testing
U. Goltz, H. Wehrheim, in: Mathematical Foundations of Computer Science 1996, 21st International Symposium, MFCS'96, Cracow, Poland, September 2-6, 1996, Proceedings, 1996, pp. 394--406
1994
Weak Sequential Composition in Process Algebras
A. Rensink, H. Wehrheim, in: {CONCUR} '94, Concurrency Theory, 5th International Conference, Uppsala, Sweden, August 22-25, 1994, Proceedings, 1994, pp. 226--241
Parametric Action Refinement
H. Wehrheim, in: Programming Concepts, Methods and Calculi, Proceedings of the {IFIP} {TC2/WG2.1/WG2.2/WG2.3} Working Conference on Programming Concepts, Methods and Calculi {(PROCOMET} '94) San Miniato, Italy, 6-10 June, 1994, 1994, pp. 247--266
Max number of publications reached - all publications can be found in our Research Infomation System.
Open list in Research Information System
