1. |
|
|
2. |
|
|
3. |
|
|
4. |
- Abdulla, Parosh Aziz, et al.
(author)
-
An Integrated Specification and Verification Technique for Highly Concurrent Data Structures
- 2013
-
In: Tools and Algorithms for the Construction and Analysis of Systems. - Berlin, Heidelberg : Springer Berlin Heidelberg.
-
Conference paper (peer-reviewed)abstract
- We present a technique for automatically verifying safety properties of concurrent programs, in particular programs which rely on subtle dependen- cies of local states of different threads, such as lock-free implementations of stacks and queues in an environment without garbage collection. Our technique addresses the joint challenges of infinite-state specifications, an unbounded num- ber of threads, and an unbounded heap managed by explicit memory allocation. Our technique builds on the automata-theoretic approach to model checking, in which a specification is given by an automaton that observes the execution of a program and accepts executions that violate the intended specification. We extend this approach by allowing specifications to be given by a class of infinite-state au- tomata. We show how such automata can be used to specify queues, stacks, and other data structures, by extending a data-independence argument. For verifica- tion, we develop a shape analysis, which tracks correlations between pairs of threads, and a novel abstraction to make the analysis practical. We have imple- mented our method and used it to verify programs, some of which have not been verified by any other automatic method before.
|
|
5. |
- Abdulla, Parosh Aziz, et al.
(author)
-
Block me if you can! : Context-sensitive parameterized verification
- 2014
-
In: Static Analysis. - Cham : Springer. - 9783319109350 ; , s. 1-17
-
Conference paper (peer-reviewed)abstract
- We present a method for automatic verification of systems with a parameterized number of communicating processes, such as mutual exclusion protocols or agreement protocols. To that end, we present a powerful abstraction framework that uses an efficient and precise symbolic encoding of (infinite) sets of configurations. In particular, it generalizes downward-closed sets that have successfully been used in earlier approaches to parameterized verification. We show experimentally the efficiency of the method, on various examples, including a fine-grained model of Szymanski’s mutual exclusion protocol, whose correctness, to the best of our knowledge, has not been proven automatically by any other existing methods.
|
|
6. |
- Abdulla, Parosh Aziz, Professor, et al.
(author)
-
Chain-Free String Constraints
- 2019
-
In: Automated Technology for Verification and Analysis. - Cham : Springer. - 9783030317836 - 9783030317843 ; , s. 277-293
-
Conference paper (peer-reviewed)abstract
- We address the satisfiability problem for string constraints that combine relational constraints represented by transducers, word equations, and string length constraints. This problem is undecidable in general. Therefore, we propose a new decidable fragment of string constraints, called weakly chaining string constraints, for which we show that the satisfiability problem is decidable. This fragment pushes the borders of decidability of string constraints by generalising the existing straight-line as well as the acyclic fragment of the string logic. We have developed a prototype implementation of our new decision procedure, and integrated it into in an existing framework that uses CEGAR with under-approximation of string constraints based on flattening. Our experimental results show the competitiveness and accuracy of the new framework.
|
|
7. |
- Abdulla, Parosh Aziz, et al.
(author)
-
Composed Bisimulation for Tree Automata
- 2008
-
In: Implementation and Application of Automata. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783540708438 ; , s. 212-222
-
Conference paper (peer-reviewed)
|
|
8. |
- Abdulla, Parosh Aziz, et al.
(author)
-
Composed bisimulation for tree automata
- 2009
-
In: International Journal of Foundations of Computer Science. - 0129-0541. ; 20:4, s. 685-700
-
Journal article (peer-reviewed)
|
|
9. |
|
|
10. |
|
|