Abstract:
This volume contains the proceedings of the 10th International Workshop on Parallel and Distributed Methods in verifiCation (PDMC 2011) that took place in Snowbird, Utah, on July 14, 2011. The workshop was co-located with 23rd International Conference on Computer Aided Verification (CAV 2011). The PDMC workshop series covers all aspects related to the verification and analysis of very large and complex systems using, in particular, methods and techniques that exploit contemporary, hence parallel, hardware architectures. To celebrate the 10th anniversary of PDMC, the workshop consisted of a half day invited session together and a half day session of regular contributed presentations.

Abstract:
In this paper bounded model checking of asynchronous concurrent systems is introduced as a promising application area for answer set programming. As the model of asynchronous systems a generalisation of communicating automata, 1-safe Petri nets, are used. It is shown how a 1-safe Petri net and a requirement on the behaviour of the net can be translated into a logic program such that the bounded model checking problem for the net can be solved by computing stable models of the corresponding program. The use of the stable model semantics leads to compact encodings of bounded reachability and deadlock detection tasks as well as the more general problem of bounded model checking of linear temporal logic. Correctness proofs of the devised translations are given, and some experimental results using the translation and the Smodels system are presented.

Abstract:
This paper investigates approaches to parallelizing Bounded Model Checking (BMC) for shared memory environments as well as for clusters of workstations. We present a generic framework for parallelized BMC named Tarmo. Our framework can be used with any incremental SAT encoding for BMC but for the results in this paper we use only the current state-of-the-art encoding for full PLTL. Using this encoding allows us to check both safety and liveness properties, contrary to an earlier work on distributing BMC that is limited to safety properties only. Despite our focus on BMC after it has been translated to SAT, existing distributed SAT solvers are not well suited for our application. This is because solving a BMC problem is not solving a set of independent SAT instances but rather involves solving multiple related SAT instances, encoded incrementally, where the satisfiability of each instance corresponds to the existence of a counterexample of a specific length. Our framework includes a generic architecture for a shared clause database that allows easy clause sharing between SAT solver threads solving various such instances. We present extensive experimental results obtained with multiple variants of our Tarmo implementation. Our shared memory variants have a significantly better performance than conventional single threaded approaches, which is a result that many users can benefit from as multi-core and multi-processor technology is widely available. Furthermore we demonstrate that our framework can be deployed in a typical cluster of workstations, where several multi-core machines are connected by a network.

Abstract:
We consider the problem of bounded model checking (BMC) for linear temporal logic (LTL). We present several efficient encodings that have size linear in the bound. Furthermore, we show how the encodings can be extended to LTL with past operators (PLTL). The generalised encoding is still of linear size, but cannot detect minimal length counterexamples. By using the virtual unrolling technique minimal length counterexamples can be captured, however, the size of the encoding is quadratic in the specification. We also extend virtual unrolling to Buchi automata, enabling them to accept minimal length counterexamples. Our BMC encodings can be made incremental in order to benefit from incremental SAT technology. With fairly small modifications the incremental encoding can be further enhanced with a termination check, allowing us to prove properties with BMC. Experiments clearly show that our new encodings improve performance of BMC considerably, particularly in the case of the incremental encoding, and that they are very competitive for finding bugs. An analysis of the liveness-to-safety transformation reveals many similarities to the BMC encodings in this paper. Using the liveness-to-safety translation with BDD-based invariant checking results in an efficient method to find shortest counterexamples that complements the BMC-based approach.

Abstract:
This paper presents a novel technique for process discovery. In contrast to the current trend, which only considers an event log for discovering a process model, we assume two additional inputs: an independence relation on the set of logged activities, and a collection of negative traces. After deriving an intermediate net unfolding from them, we perform a controlled folding giving rise to a Petri net which contains both the input log and all independence-equivalent traces arising from it. Remarkably, the derived Petri net cannot execute any trace from the negative collection. The entire chain of transformations is fully automated. A tool has been developed and experimental results are provided that witness the significance of the contribution of this paper.

Abstract:
Consider a complete communication network on $n$ nodes, each of which is a state machine. In synchronous 2-counting, the nodes receive a common clock pulse and they have to agree on which pulses are "odd" and which are "even". We require that the solution is self-stabilising (reaching the correct operation from any initial state) and it tolerates $f$ Byzantine failures (nodes that send arbitrary misinformation). Prior algorithms are expensive to implement in hardware: they require a source of random bits or a large number of states. This work consists of two parts. In the first part, we use computational techniques (often known as synthesis) to construct very compact deterministic algorithms for the first non-trivial case of $f = 1$. While no algorithm exists for $n < 4$, we show that as few as 3 states per node are sufficient for all values $n \ge 4$. Moreover, the problem cannot be solved with only 2 states per node for $n = 4$, but there is a 2-state solution for all values $n \ge 6$. In the second part, we develop and compare two different approaches for synthesising synchronous counting algorithms. Both approaches are based on casting the synthesis problem as a propositional satisfiability (SAT) problem and employing modern SAT-solvers. The difference lies in how to solve the SAT problem: either in a direct fashion, or incrementally within a counter-example guided abstraction refinement loop. Empirical results suggest that the former technique is more efficient if we want to synthesise time-optimal algorithms, while the latter technique discovers non-optimal algorithms more quickly.

Abstract:
The managerial form of university governance has changed the conditions of academic work in many countries. While some academics consider this a welcome development, others experience it as a threat to their autonomy and to the meaningfulness of their work. This essay suggests a stance in response to the current conditions that should serve especially the latter group of academics. The claim is that by approaching academic work as a potential praxis in emergence, it is possible to appreciate local, autonomous activity in renewing academic work. Even if such efforts remain difficult, dispersed in space, discontinuous in time, and incomplete, they may provide a sense of direction and keep up hope. The conception of praxis is a way of articulating the mission of such efforts; simultaneously, it is also a way of defining an epistemic object for research on academic work.

Abstract:
In this note we prove algebraic independence results for the values of a special class of Mahler functions. In particular, the generating functions of Thue-Morse, regular paperfolding and Cantor sequences belong to this class, and we obtain the algebraic independence of the values of these functions at every non-zero algebraic point in the open unit disk. The proof uses results on Mahler's method.

In this paper, we proposed a novel triple algorithm based on RSA (Rivest-Shamir-Adleman), AES (Advanced Encryption Standard), and TwoFish in order to further improve the security of Bluetooth that is currently using only 128-bit AES for encryption in its latest versions (Bluetooth 4.0 - 5.0). Further-more, older Bluetooth 1.0A – 3.0 + HS (High-Speed) devices use E0 stream cipher for encryption that has been shown to be weak by numerous researchers and thus it could be considered insufficient for high security purposes nowadays. In our novel approach, the triple protection of AES, RSA, and TWOFISH would enhance the level of security, which shields the data transmission in the Bluetooth. As the first step of our novel approach, we first encrypted the message by using AES with 128-bit key and then further encrypted it by using Twofish with the same 128-bit key. Finally, the 128-bit key generated in the beginning will be encrypted by using RSA with 1024-bit key to protect its over-the-air transfer. In the receiving end, the decryption process goes in reverse order compared with encryption process. We showed with experimental figures that our novel algorithm improved the security of Bluetooth encryption by eliminating all known weaknesses and thus made data exchange between Bluetooth devices secure.

Abstract:
The maximal degree over rational numbers that an n-dimensinonal Kloosterman sum defined over a finite field of characteristic p can achieve is known to be (p-1)/d where d=gcd(p-1,n+1). Wan has shown that this maximal degree is always achieved in points whose absolute trace is nonzero. By the works of Fischer, Wan we know that there exist many finite fields for which the values of the Kloosterman sums are distinct except Frobenius conjugation. For these fields we completely determine the degrees of all the Kloosterman sums. Even if the finite field does not satisfy this condition we can still often find points in which the Kloosterman sum has smaller degree than (p-1)/d.