TY - CONF AU - Doherty, Simon AU - Dongol, Brijesh AU - Wehrheim, Heike AU - Derrick, John ID - 6839 T2 - 32nd International Symposium on Distributed Computing, {DISC} 2018, New Orleans, LA, USA, October 15-19, 2018 TI - Brief Announcement: Generalising Concurrent Correctness to Weak Memory ER - TY - JOUR AB - 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. AU - Isenberg, Tobias AU - Jakobs, Marie-Christine AU - Pauck, Felix AU - Wehrheim, Heike ID - 1043 JF - IEEE Embedded Systems Letters SN - 1943-0663 TI - Validity of Software Verification Results on Approximate Hardware ER - TY - CONF AB - to appear AU - Beyer, Dirk AU - Jakobs, Marie-Christine AU - Lemberger, Thomas AU - Wehrheim, Heike ID - 1096 T2 - Proceedings of the 40th International Conference on Software Engineering (ICSE) TI - Reducer-Based Construction of Conditional Verifiers ER - TY - GEN AU - Börding, Paul ID - 3512 TI - Testing Java Method Contracts ER - TY - CONF AU - Töws, Manuel AU - Wehrheim, Heike ED - Duan, Zhenhua ED - Ong, Luke ID - 3155 T2 - Formal Methods and Software Engineering - 19th International Conference on Formal Engineering Methods, {ICFEM} 2017, Xi'an, China, November 13-17, 2017, Proceedings TI - Policy Dependent and Independent Information Flow Analyses ER - TY - CONF AU - König, Jürgen AU - Wehrheim, Heike ED - Van Hung, Dang ED - Kapur, Deepak ID - 3156 T2 - Theoretical Aspects of Computing - {ICTAC} 2017 - 14th International Colloquium, Hanoi, Vietnam, October 23-27, 2017, Proceedings TI - Value-Based or Conflict-Based? Opacity Definitions for STMs ER - TY - CONF AB - 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. AU - Jakobs, Marie-Christine AU - Wehrheim, Heike ED - Barrett, Clark ED - Davies, Misty ED - Kahsai, Temesghen ID - 114 T2 - NASA Formal Methods: 9th International Symposium TI - Compact Proof Witnesses ER - TY - CONF AB - Whenever customers have to decide between different instances of the same product, they are interested in buying the best product. In contrast, companies are interested in reducing the construction effort (and usually as a consequence thereof, the quality) to gain profit. The described setting is widely known as opposed preferences in quality of the product and also applies to the context of service-oriented computing. In general, service-oriented computing emphasizes the construction of large software systems out of existing services, where services are small and self-contained pieces of software that adhere to a specified interface. Several implementations of the same interface are considered as several instances of the same service. Thereby, customers are interested in buying the best service implementation for their service composition wrt. to metrics, such as costs, energy, memory consumption, or execution time. One way to ensure the service quality is to employ certificates, which can come in different kinds: Technical certificates proving correctness can be automatically constructed by the service provider and again be automatically checked by the user. Digital certificates allow proof of the integrity of a product. Other certificates might be rolled out if service providers follow a good software construction principle, which is checked in annual audits. Whereas all of these certificates are handled differently in service markets, what they have in common is that they influence the buying decisions of customers. In this paper, we review state-of-the-art developments in certification with respect to service-oriented computing. We not only discuss how certificates are constructed and handled in service-oriented computing but also review the effects of certificates on the market from an economic perspective. AU - Jakobs, Marie-Christine AU - Krämer, Julia AU - van Straaten, Dirk AU - Lettmann, Theodor ED - Marcelo De Barros, Janusz Klink,Tadeus Uhl, Thomas Prinz ID - 115 T2 - The Ninth International Conferences on Advanced Service Computing (SERVICE COMPUTATION) TI - Certification Matters for Service Markets ER - TY - JOUR AB - We propose and extend an approach for the verification of safety properties for parameterized timed systems modeled as networks of timed automata. For this task, we introduce an incremental workflow that is based on our algorithm IC3 with Zones. It proceeds in a cycle in which single models of the system are verified, and the verification results are employed for the reasoning about the entire system. Starting with the smallest instances, the verification of the safety property is carried out fast and efficient. On successful verification, the algorithm produces an inductive strengthening of the safety property. We reuse this result and try to reason about the entire parameterized timed system. To this end, we extrapolate the inductive strengthening into a candidate for the next-larger model. In case this candidate is a valid inductive strengthening for the next larger model, our main theorem reasons about all models of the parameterized timed system, stating that the safety property holds true for all models. Otherwise, the main cycle starts over with the verification of the next larger model. This workflow is iterated indefinitely, until able to reason about the entire parameterized timed system, until a counterexample trace is found, or until the single models become too large to be handled in the verification. We reuse the intermediate results in a Feedback-loop in order to accelerate the verification runs for the single models. Furthermore, we consider an extended formalism in comparison to our previous publications. AU - Isenberg, Tobias ID - 90 IS - 2 JF - ACM Transactions on Embedded Computing Systems TI - Incremental Inductive Verification of Parameterized Timed Systems ER - TY - CONF AB - Information Flow Analysis (IFA) aims at detecting illegal flows of information between program entities. “Legality” is therein specified in terms of various security policies. For the analysis, this opens up two possibilities: building generic, policy independent and building specific, policy dependent IFAs. While the former needs to track all dependencies between program entities, the latter allows for a reduced and thus more efficient analysis. In this paper, we start out by formally defining a policy independent information flow analysis. Next, we show how to specialize this IFA via policy specific variable tracking, and prove soundness of the specialization. We furthermore investigate refinement relationships between policies, allowing an IFA for one policy to be employed for its refinements. As policy refinement depends on concrete program entities, we additionally propose a precomputation of policy refinement conditions, enabling an efficient refinement check for concrete programs. AU - Töws, Manuel AU - Wehrheim, Heike ID - 5769 SN - 0302-9743 T2 - Formal Methods and Software Engineering - 19th International Conference on Formal Engineering Methods (ICFEM 2017) TI - Policy Dependent and Independent Information Flow Analyses ER -