| 1. |
- Ahrendt, Wolfgang, 1967, et al.
(författare)
-
A broader view on verification: From static to runtime and back (track summary)
- 2018
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. ; 11245 LNCS, s. 3-7
-
Konferensbidrag (refereegranskat)abstract
- © Springer Nature Switzerland AG 2018. When seeking to verify a computational system one can either view the system as a static description of possible behaviours or a dynamic collection of observed or actual behaviours. Historically, there have been clear differences between the two approaches in terms of their level of completeness, the associated costs, the kinds of specifications considered, how and when they are applied, and so on. Recently there has been a concentrated interest in the combination of static and runtime (dynamic) techniques and this track (taking place as part of ISoLA 2018) aims to explore this combination further.
|
|
| 2. |
- Ahrendt, Wolfgang, 1967, et al.
(författare)
-
SpecifyThis – Bridging Gaps Between Program Specification Paradigms
- 2022
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. ; 13701 LNCS, s. 3-6
-
Konferensbidrag (refereegranskat)abstract
- We motivate and summarise the track SpecifyThis – Bridging gaps between program specification paradigms, taking place at the International Symposium on Leveraging Applications of Formal Methods, ISoLA 2022.
|
|
| 3. |
- Amighi, Afshin, et al.
(författare)
-
Provably Correct Control Flow Graphs from Java Bytecode Programs with Exceptions
- 2016
-
Ingår i: International Journal on Software Tools for Technology Transfer. - : Springer Nature. - 1433-2779 .- 1433-2787. ; 18:6, s. 653-684
-
Tidskriftsartikel (refereegranskat)abstract
- We present an algorithm for extracting control flow graphs from Java bytecode that captures normal as well as exceptional control flow. We prove its correctness, in the sense that the behaviour of the extracted control flow graph is a sound over-approximation of the behaviour of the original program. This makes control flow graphs suitable for performing various static analyses, such as model checking of temporal safety properties.Analyzing exceptional control flow for Java bytecode is difficult because of the stack-based nature of the language. We therefore develop the extraction in two stages. In the first, we abstract away from the complications arising from exceptional flows, and relativize the extraction on an oracle that is able to look into the stack and predict the exceptions that can be raised at each instruction. This idealized algorithm provides a specification for concrete extraction algorithms, which have to provide a suitable implementation for the oracle. We prove correctness of the idealized algorithm by means of behavioural simulation.In the second stage, we develop a concrete extraction algorithm that consists of two phases. In the first phase, the program is transformed into a BIR program, a stack-less intermediate representation of Java bytecode, from which the control flow graph is extracted in the second phase. We use this intermediate format because it provides the information needed to implement the oracle, and since it gives rise to more compact graphs. We show that the behaviour of the control flow graph extracted via the intermediate representation is a sound over-approximation of the behaviour of the graph extracted by the direct, idealized algorithm, and thus of the original program. The concrete extraction algorithm is implemented as the ConFlEx tool. A number of test cases are performed to evaluate the efficiency of the algorithm.
|
|
| 4. |
- Amighi, Afshin, et al.
(författare)
-
Provably Correct Control-Flow Graphs from Java Programs with Exceptions
- 2012
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We present an algorithm to extract flow graphs from Java bytecode, including exceptional control flows. We prove its correctness, meaning that the behavior of the extracted control-flow graph is a sound over-approximation of the behavior of the original program. Thus any safety property that holds for the extracted control-flow graph also holds for the original program. This makes control-flow graphs suitable for performing various static analyses, such as model checking.The extraction is performed in two phases. In the first phase the program is transformed into a BIR program, a stack-less intermediate representation of Java bytecode, from which the control-flow graph is extracted in the second phase. We use this intermediate format because it results in compact flow graphs, with provably correct exceptional control flow. To prove the correctness of the two-phase extraction, we also define an idealized extraction algorithm, whose correctness can be proven directly. Then we show that the behavior of the control-flow graph extracted via the intermediate representation is an over-approximation of the behavior of the directly extracted graphs, and thus of the original program. We implemented the indirect extraction as the CFGEx tool and performed several test-cases to show the efficiency of the algorithm.
|
|
| 5. |
- Amighi, Afshin, et al.
(författare)
-
Provably Correct Control-Flow Graphs from Java Programs with Exceptions
- 2011
-
Ingår i: Formal Verification of Object-Oriented Software. ; , s. 31-48
-
Konferensbidrag (refereegranskat)abstract
- We present an algorithm to extract flow graphs from Java bytecode, focusing on exceptional control flows. We prove its correctness, meaning that the behaviour of the extracted control-flow graph is an over-approximation of the behaviour of the original program. Thus any safety property that holds for the extracted control-flow graph also holds for the original program. This makes control-flow graphs suitable for performing different static analyses. For precision and efficiency, the extraction is performed in two phases. In the first phase the program is transformed into a BIR program, where BIR is a stack-less intermediate representation of Java bytecode; in the second phase the control-flow graph is extracted from the BIR representation. To prove the correctness of the two-phase extraction, we also define a direct extraction algorithm, whose correctness can be proven immediately. Then we show that the behaviour of the control-flow graph extracted via the intermediate representation is an over-approximation of the behaviour of the directly extracted graphs, and thus of the original program.
|
|
| 6. |
- Amighi, Afshin, et al.
(författare)
-
Sound Control-Flow Graph Extraction for Java Programs with Exceptions
- 2012
-
Ingår i: Software Engineering and Formal Methods. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642338250 ; , s. 33-47
-
Konferensbidrag (refereegranskat)abstract
- We present an algorithm to extract control-flow graphs from Java bytecode, considering exceptional flows. We then establish its correctness: the behavior of the extracted graphs is shown to be a sound over-approximation of the behavior of the original programs. Thus, any temporal safety property that holds for the extracted control-flow graph also holds for the original program. This makes the extracted graphs suitable for performing various static analyses, in particular model checking. The extraction proceeds in two phases. First, we translate Java bytecode into BIR, a stack-less intermediate representation. The BIR transformation is developed as a module of Sawja, a novel static analysis framework for Java bytecode. Besides Sawja’s efficiency, the resulting intermediate representation is more compact than the original bytecode and provides an explicit representation of exceptions. These features make BIR a natural starting point for sound control-flow graph extraction. Next, we formally define the transformation from BIR to control-flow graphs, which (among other features) considers the propagation of uncaught exceptions within method calls. We prove the correctness of the two-phase extraction by suitably combining the properties of the two transformations with those of an idealized control-flow graph extraction algorithm, whose correctness has been proved directly. The control-flow graph extraction algorithm is implemented in the ConFlEx tool. A number of test-cases show the efficiency and the utility of the implementation.
|
|
| 7. |
|
|
| 8. |
- Bartocci, Ezio, et al.
(författare)
-
TOOLympics 2019 : An overview of competitions in formal methods
- 2019
-
Ingår i: Tools and Algorithms for the Construction and Analysis of Systems. - Cham : Springer. - 9783030175016 ; , s. 3-24
-
Konferensbidrag (refereegranskat)abstract
- Evaluation of scientific contributions can be done in many different ways. For the various research communities working on the verification of systems (software, hardware, or the underlying involved mechanisms), it is important to bring together the community and to compare the state of the art, in order to identify progress of and new challenges in the research area. Competitions are a suitable way to do that.The first verification competition was created in 1992 (SAT competition), shortly followed by the CASC competition in 1996. Since the year 2000, the number of dedicated verification competitions is steadily increasing. Many of these events now happen regularly, gathering researchers that would like to understand how well their research prototypes work in practice. Scientific results have to be reproducible, and powerful computers are becoming cheaper and cheaper, thus, these competitions are becoming an important means for advancing research in verification technology.TOOLympics 2019 is an event to celebrate the achievements of the various competitions, and to understand their commonalities and differences. This volume is dedicated to the presentation of the 16 competitions that joined TOOLympics as part of the celebration of the 25?ℎ anniversary of the TACAS conference.
|
|
| 9. |
- Ben Henda, Noomene, et al.
(författare)
-
OpenSAW: Open Security Analysis Workbench
- 2017. - 1
-
Ingår i: Fundamental Approaches to Software Engineering : 20th International Conference, FASE 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings - 20th International Conference, FASE 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783662544938 - 9783662544945 ; 10202, s. 321-337
-
Konferensbidrag (refereegranskat)abstract
- Software is today often composed of many sourced components, which potentially contain security vulnerabilities, and therefore require testing before being integrated. Tools for automated test case generation, for example, based on white-box fuzzing, are beneficial for this testing task. Such tools generally explore limitations of the specific underlying techniques for solving problems related to, for example, constraint solving, symbolic execution, search heuristics and execution trace extraction. In this article we describe the design of OpenSAW, a more flexible general-purpose white-box fuzzing framework intended to encourage research on new techniques identifying security problems. In addition, we have formalized two unaddressed technical aspects and devised new algorithms for these. The first relates to generalizing and combining different program exploration strategies, and the second relates to prioritizing execution traces. We have evaluated OpenSAW using both in-house and external programs and identified several bugs.
|
|
| 10. |
- Cai, Simin
(författare)
-
Systematic Design and Analysis of Customized Data Management for Real-Time Database Systems
- 2019
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Modern real-time data-intensive systems generate large amounts of data that are processed using complex data-related computations such as data aggregation. In order to maintain logical data consistency and temporal correctness of the computations, one solution is to model the latter as transactions and manage them using a Real-Time Database Management System (RTDBMS). Ideally, depending on the particular system, the transactions are customized with the desired logical and temporal correctness properties, which should be enforced by the customized RTDBMS via appropriate transaction management mechanisms. However, developing such a data management solution with high assurance is not easy, partly due to inadequate support for systematic specification and analysis during the design. Firstly, designers do not have means to identify the characteristics of the computations, especially data aggregation, and to reason about their implications. Design flaws might not be discovered early enough, and thus they may propagate to the implementation. Secondly, meeting more properties simultaneously might not be possible, so trading-off the less critical ones for the critical one, for instance, temporal correctness, is sometimes required. Nevertheless, trade-off analysis of conflicting properties, such as transaction atomicity, isolation and temporal correctness, is mainly performed ad-hoc, which increases the risk of unpredictable behavior.In this thesis, we address the above problems by showing how to systematically design and provide assurance of transaction-based data management with data aggregation support, customized for real-time systems. We propose a design process as our methodology for the systematic design and analysis of the trade-offs between desired properties, which is facilitated by a series of modeling and analysis techniques. Our design process consists of three major steps as follows: (i) Specifying the data-related computations, as well as the logical data consistency and temporal correctness properties, from system requirements, (ii) Selecting the appropriate transaction models to model the computations, and deciding the corresponding transaction management mechanisms that can guarantee the properties, via formal analysis, and, (iii) Generating the customized RTDBMS with the proved transaction management mechanisms, via configuration or implementation. In order to support the first step of our process, we propose a taxonomy of data aggregation processes for identifying their common and variable characteristics, based on which their inter-dependencies can be captured, and the consequent design implications can be reasoned about. Tool support is provided to check the consistency of the data aggregation design specifications. To specify transaction atomicity, isolation and temporal correctness, as well as the transaction management mechanisms, we also propose a Unified Modeling Language (UML) profile with explicit support for these elements. The second step of our process relies on the systematic analysis of trade-offs between transaction atomicity, isolation and temporal correctness. To achieve this, we propose two formal frameworks for modeling transactions with abort recovery, concurrency control, and scheduling. The first framework UPPCART utilizes timed automata as the underlying formalism, based on which the desired properties can be verified by model checking. The second framework UPPCART-SMC models the system as stochastic timed automata, which allows for probabilistic analysis of the properties for large complex RTDBMS using statistical model checking. The encoding of high-level UTRAN specifications into corresponding formal models is supported by tool automation, which we also propose in this thesis. The applicability and usefulness of our proposed techniques are validated via several industrial use cases focusing on real-time data management.
|
|
