Solving Boolean polynomial systems by parallelizing characteristic set method for cyber‐physical systems. (23rd September 2020)

• Record Type: Journal Article
• Authors: Zhao, Juan; Zhu, Min; Li, Xiaoyong; Huang, Zhenyu; Li, Jincai; Song, Junqiang
• Other Names: Zhou Junlong guestEditor.; Kritikakou Angeliki guestEditor.; Zhu Dakai guestEditor.; Lastra Jose L. Martinez guestEditor.; Hu Shiyan guestEditor.
• Is Part Of: Software, practice & experience. Volume 51:Number 11(2021)
• Page Start: 2143
• Page End: 2167
• Publication Date: 2020-09-23
• Subjects: Boolean polynomial system -- Boolean polynomial system solving problem -- characteristic set method -- cyber‐physical systems -- parallel algorithm -- task reallocation; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2895
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: Many cyber‐attach schemes and coding models established by algebra tools are build to address the problem of security of cyber‐pysical systems (CPS). As an important field of algebra computing, Boolean Polynomial System Solving (PoSSo) problem plays a very important role in many algebra applications. In this article, we propose an efficient Parallel Boolean Characteristic Set method (PBCS) under the high‐performance computing environment to improve the efficiency of solving Boolean polynomial systems. The PBCS is implemented based on the state‐of‐the‐art Boolean Characteristic Set method (BCS). It adopts a master‐slave parallel pattern, and distributes tasks based on the polynomial sets after initial zero decomposition. We design a strategy of dynamically reallocating tasks to ameliorate load imbalance, which is caused by dynamical zero decomposition of polynomials. Furthermore, we improve its performance by optimizing the parameter settings of PBCS, including the maximum number of polynomial branches that trigger the dynamic allocation policy and the scheduling time. Experimental results with solving several Boolean polynomial systems confirm that PBCS is efficient and scalable, especially for the equations generating from stream ciphers that have block triangular structure. Moreover, the method also has good scalability. It shows a stable speedup as well even extending to the size of thousands of CPU cores.