Facilitating Multicore Bounded Model Checking with Stateless Explicit-State Exploration

November 2015
Computer Journal;Nov2015, Vol. 58 Issue 11, p2824
Academic Journal
Bounded Model Checking (BMC) converts a verification problem within a user-specified bound into satisfiability checks of propositional formulas. As the bound deepens, the formulas become larger in size and harder to solve. In this paper, we propose a hybrid approach in which stateless explicit-state exploration (SESE) is integrated into the BMC process to improve the scalability and performance of BMC for the verification of properties expressed in Linear Temporal Logic (LTL). Specifically, SESE is utilized to traverse, under the constraints of Bounded-Context Switching (BCS), the state space of a system design and memorize legal execution paths. These paths are classified according to heuristic state predicates into path clusters, which are then encoded into propositional formulas representing, together with the encoded formula for an LTL property, independent BMC instances. Such BMC instances are solved with SMT solvers running on mutilcores in parallel. Once a counterexample is found for one of the instances, the entire model checking (SESE as well as BMC) terminates. This hybrid checking procedure progresses in an incremental fashion until either a counterexample is found or the user-specified bound is reached. We have implemented this proposed hybrid approach in a tool called Garakabu2 with Yices 2 as its back-end solver. The experimental results show that Garakabu2 outperforms significantly the state-of-the-art BMC methods implemented in SAL for both safety and liveness properties.


Related Articles

  • Improving WalkSAT By Effective Tie-Breaking and Efficient Implementation. SHAOWEI CAI; CHUAN LUO; KAILE SU // Computer Journal;Nov2015, Vol. 58 Issue 11, p2864 

    Stochastic local search (SLS) algorithms are well known for their ability to efficiently find models of random instances of the Boolean satisfiability (SAT) problem. One of the most famous SLS algorithms for SAT is WalkSAT, which is an initial algorithm that has wide influence and performs very...

  • OpenMP Teaching-Learning Based Optimization Algorithm over Multi-Core System. Umbarkar, A. J.; Rothe, N. M.; Sathe, A. S. // International Journal of Intelligent Systems & Applications;Jun2015, Vol. 7 Issue 7, p57 

    The problem with metaheuristics, including Teaching-Learning-Based Optimization (TLBO) is that, it increases in the number of dimensions (D) leads to increase in the search space which increases the amount of time required to find an optimal solution (delay in convergence). Nowadays, multi-core...

  • Water distribution system design using multi-objective particle swarm optimisation. Patil, Mahesh B; Naidu, M Naveen; Vasan, A; Varma, Murari R R // Sadhana;2020, Vol. 45 Issue 1, p1 

    Application of the multi-objective particle swarm optimisation (MOPSO) algorithm to design of water distribution systems is described. An earlier MOPSO algorithm is augmented with (a) local search, (b) a modified strategy for assigning the leader and (c) a modified mutation scheme. For one of...

  • A multiple local search algorithm for continuous dynamic optimization. Lepagnot, Julien; Nakib, Amir; Oulhadj, Hamouche; Siarry, Patrick // Journal of Heuristics;Feb2013, Vol. 19 Issue 1, p35 

    Many real-world optimization problems are dynamic (time dependent) and require an algorithm that is able to track continuously a changing optimum over time. In this paper, we propose a new algorithm for dynamic continuous optimization. The proposed algorithm is based on several coordinated local...

  • Study of the Influence of Genetic Algorithm Parameters on Travelling Salesman Problem. Suresh, K. S.; Rajarajan, S.; Prabhu, M.; Vaithiyanathan, V. // International Journal of Applied Engineering Research;2013, Vol. 8 Issue 20, p2667 

    The Travelling Salesman Problem may be the good old problem, but it still attracts the researchers. Because it gives space for the researchers to solve using various techniques and considered as the benchmark problem for implementing optimization algorithms. In this paper, genetic algorithm is...

  • New Local Search Strategy in Artificial Bee Colony Algorithm. Kumar, Sandeep; Bhambu, Pawan; Kumar Sharma, Vivek // International Journal of Computer Science & Information Technolo;2014, Vol. 5 Issue 2, p2559 

    Artificial Bee Colony (ABC) algorithm is a Nature Inspired Algorithm (NIA) which based on intelligent food foraging behaviour of honey bee swarm. This paper introduces a local search strategy that enhances exploration competence of ABC and avoids the problem of stagnation. The proposed strategy...

  • Multi-Objective Self-Organizing Migrating Algorithm: Sensitivity on Controlling Parameters. KADLEC, Petr; RAIDA, Zbynĕk; DŘÍNOVSKÝ, Jiří // Radioengineering;Apr2013, Vol. 22 Issue 1, p296 

    In this paper, we investigate the sensitivity of a novel Multi-Objective Self-Organizing Migrating Algorithm (MOSOMA) on setting its control parameters. Usually, efficiency and accuracy of searching for a solution depends on the settings of a used stochastic algorithm, because multi-objective...

  • A Modified Immune Network Optimization Algorithm. Lu Hong; Kamruzzaman, Joarder // IAENG International Journal of Computer Science;Nov2014, Vol. 41 Issue 4, p20 

    This study proposes a modified artificial immune network algorithm for function optimization problems based on idiotypic immune network theory. A hyper-cubic mutation operator was introduced to reduce the heavy computational cost of the traditional opt-AINet algorithm. Moreover, the new...

  • Enhancing Differential Evolution Performance with Self-Adaptive Population Topologies on Numerical Benchmark Problems. Yu Sun; Yuanxiang Li; Jun Liu; Huijun Hu // Journal of Convergence Information Technology;Nov2012, Vol. 7 Issue 21, p501 

    Differential evolution is a popular and effective optimization algorithm. In this paper, an efficient technique for adapting population topology with differential evolution (DE) was proposed, motivated by the different topologies in which various search operators behave. The main goal is to...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics