國立虎尾科技大學 |

Formal Verification of AI-controlled Cyber-physical Systems Using Polynomial Approximations : = Constraints Solver, Model Checkers, and Applications.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Formal Verification of AI-controlled Cyber-physical Systems Using Polynomial Approximations :/
Reminder of title:	Constraints Solver, Model Checkers, and Applications.
Author:	Fatnassi, Wael.
Description:	1 online resource (165 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 85-11, Section: B.
Contained By:	Dissertations Abstracts International85-11B.
Subject:	Electrical engineering. -
Online resource:	click for full text (PQDT)
ISBN:	9798382733395

Formal Verification of AI-controlled Cyber-physical Systems Using Polynomial Approximations : = Constraints Solver, Model Checkers, and Applications.
Fatnassi, Wael.

Formal Verification of AI-controlled Cyber-physical Systems Using Polynomial Approximations :Constraints Solver, Model Checkers, and Applications. - 1 online resource (165 pages)

Source: Dissertations Abstracts International, Volume: 85-11, Section: B.

Thesis (Ph.D.)--University of California, Irvine, 2024.

Includes bibliographical references

The last decade's advancement in machine learning (ML) for controlling cyber-physical systems has heralded a new era in autonomous technology, driving innovations from self-driving cars to smart infrastructure. However, these systems often grapple with challenges related to safety, reliability, and the ability to generalize across different scenarios. This dissertation aims to bridge the gap between the scalability and flexibility of ML-based control systems and the rigorous safety and reliability guarantees provided by formal methods and control theory. It introduces novel methodologies that leverage machine learning to enhance the design, verification, and optimization of AI-controlled cyber-physical systems, ensuring they meet high-level specifications while managing such systems' inherent complexity and non-linearity.The contributions of this thesis are multi-fold. 1) We proposed a highly efficient and parallelizable solver called PolyAR, which aims to solve general multivariate polynomial inequality constraints. PolyAR uses convex polynomials as an abstraction for highly nonlinear polynomials. Such abstractions were previously shown to be powerful to prune the search space and restrict the usage of sound and complete solvers to small search space. We compared the scalability of PolyAR against state-of-the-art solvers such as Z3 8.9 and Yices 2.6 on complex design and verification problems. The experiment results show that the PolyAR solver drastically outperformed Z3 8.9 and Yices 2.6 regarding execution time. 2) We developed PolyARBerNN, an enhancement to PolyAR that employs neural networks (NN) to guide the abstraction refinement procedure that helps to select the right abstraction out of a set of pre-defined abstractions and a Bernstein polynomial-based search space pruning mechanism. These enhancements together made PolyARBerNN capable of solving complex instances and scaling more favorably compared to the state-of-the-art nonlinear real arithmetic solvers while maintaining the soundness and completeness of the resulting solver. In addition, we proposed an efficient optimizer called PolyAROpt that transforms polynomial objective functions into polynomial constraints (on the gradient of the objective function) whose solutions are guaranteed to be close to the global optima. PolyAROpt optimizer uses PolyARBerNN to solve constrained polynomial optimization problems. Numerical results show that PolyAROpt can solve high-dimensional and high-order polynomial optimization problems faster than the built-in optimizer in the Z3 8.9 solver. 3) We proposed an efficient algorithm called BERN-NN that employs polynomial interval arithmetic, where tight over/under approximations of the NN's activation functions are computed using Bernstein polynomials. These polynomials have several interesting mathematical proprieties. One particular property is called the sharpness propriety, which allows us to obtain extremely tight bounds that are tighter than those currently exist in the literature (e.g., interval arithmetic, crowns, linear programming, and many centered forms). Moreover, we exploited the mathematical proprieties of Bernstein polynomials to convert the proposed polynomial interval arithmetic operations into add-and-multiply operations, which are easily implemented using GPUs. Thanks to those GPUs, our tool's execution time is drastically reduced. Experimental results show that our method approximates NN's outputs tighter than state-of-the-art NN verification tools by several orders of magnitude. 4) We proposed BERN-NN-IBF, a significant enhancement of the Bernstein-polynomial-based bound propagation algorithms. BERN-NN-IBF offers three main contributions: (i) a memory-efficient encoding of Bernstein-polynomials to scale the bound propagation algorithms, (ii) optimized tensor operations for the new polynomial encoding to maintain the integrity of the bounds while enhancing computational efficiency, and (iii) tighter under-approximations of the ReLU activation function using quadratic polynomials tailored to minimize approximation errors. Through comprehensive testing, we demonstrate that BERN-NN-IBF achieves tighter bounds and higher computational efficiency than the original BERN-NN and state-of-the-art methods, including linear programming and convex used within the winner of the VNN-COMPETITION.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798382733395Subjects--Topical Terms:

596380
Electrical engineering.
Subjects--Index Terms:

Abstraction refinementIndex Terms--Genre/Form:

554714
Electronic books.

Formal Verification of AI-controlled Cyber-physical Systems Using Polynomial Approximations : = Constraints Solver, Model Checkers, and Applications.
LDR:05873ntm a22004097 4500 001 1146267
005 20240812064356.5
006 m o d
007 cr bn ---uuuuu
008 250605s2024 xx obm 000 0 eng d
020 $a 9798382733395
035 $a (MiAaPQ)AAI30995682
035 $a AAI30995682
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Fatnassi, Wael. $3 1471627
245 1 0 $a Formal Verification of AI-controlled Cyber-physical Systems Using Polynomial Approximations : $b Constraints Solver, Model Checkers, and Applications.
264 0 $c 2024
300 $a 1 online resource (165 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 85-11, Section: B.
500 $a Advisor: Shoukry, Yasser.
502 $a Thesis (Ph.D.)--University of California, Irvine, 2024.
504 $a Includes bibliographical references
520 $a The last decade's advancement in machine learning (ML) for controlling cyber-physical systems has heralded a new era in autonomous technology, driving innovations from self-driving cars to smart infrastructure. However, these systems often grapple with challenges related to safety, reliability, and the ability to generalize across different scenarios. This dissertation aims to bridge the gap between the scalability and flexibility of ML-based control systems and the rigorous safety and reliability guarantees provided by formal methods and control theory. It introduces novel methodologies that leverage machine learning to enhance the design, verification, and optimization of AI-controlled cyber-physical systems, ensuring they meet high-level specifications while managing such systems' inherent complexity and non-linearity.The contributions of this thesis are multi-fold. 1) We proposed a highly efficient and parallelizable solver called PolyAR, which aims to solve general multivariate polynomial inequality constraints. PolyAR uses convex polynomials as an abstraction for highly nonlinear polynomials. Such abstractions were previously shown to be powerful to prune the search space and restrict the usage of sound and complete solvers to small search space. We compared the scalability of PolyAR against state-of-the-art solvers such as Z3 8.9 and Yices 2.6 on complex design and verification problems. The experiment results show that the PolyAR solver drastically outperformed Z3 8.9 and Yices 2.6 regarding execution time. 2) We developed PolyARBerNN, an enhancement to PolyAR that employs neural networks (NN) to guide the abstraction refinement procedure that helps to select the right abstraction out of a set of pre-defined abstractions and a Bernstein polynomial-based search space pruning mechanism. These enhancements together made PolyARBerNN capable of solving complex instances and scaling more favorably compared to the state-of-the-art nonlinear real arithmetic solvers while maintaining the soundness and completeness of the resulting solver. In addition, we proposed an efficient optimizer called PolyAROpt that transforms polynomial objective functions into polynomial constraints (on the gradient of the objective function) whose solutions are guaranteed to be close to the global optima. PolyAROpt optimizer uses PolyARBerNN to solve constrained polynomial optimization problems. Numerical results show that PolyAROpt can solve high-dimensional and high-order polynomial optimization problems faster than the built-in optimizer in the Z3 8.9 solver. 3) We proposed an efficient algorithm called BERN-NN that employs polynomial interval arithmetic, where tight over/under approximations of the NN's activation functions are computed using Bernstein polynomials. These polynomials have several interesting mathematical proprieties. One particular property is called the sharpness propriety, which allows us to obtain extremely tight bounds that are tighter than those currently exist in the literature (e.g., interval arithmetic, crowns, linear programming, and many centered forms). Moreover, we exploited the mathematical proprieties of Bernstein polynomials to convert the proposed polynomial interval arithmetic operations into add-and-multiply operations, which are easily implemented using GPUs. Thanks to those GPUs, our tool's execution time is drastically reduced. Experimental results show that our method approximates NN's outputs tighter than state-of-the-art NN verification tools by several orders of magnitude. 4) We proposed BERN-NN-IBF, a significant enhancement of the Bernstein-polynomial-based bound propagation algorithms. BERN-NN-IBF offers three main contributions: (i) a memory-efficient encoding of Bernstein-polynomials to scale the bound propagation algorithms, (ii) optimized tensor operations for the new polynomial encoding to maintain the integrity of the bounds while enhancing computational efficiency, and (iii) tighter under-approximations of the ReLU activation function using quadratic polynomials tailored to minimize approximation errors. Through comprehensive testing, we demonstrate that BERN-NN-IBF achieves tighter bounds and higher computational efficiency than the original BERN-NN and state-of-the-art methods, including linear programming and convex used within the winner of the VNN-COMPETITION.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Electrical engineering. $3 596380
650 4 $a Computer science. $3 573171
650 4 $a Computer engineering. $3 569006
653 $a Abstraction refinement
653 $a Bernstein polynomials
653 $a Convex programming
653 $a Neural networks
653 $a Polynomial inequalities
655 7 $a Electronic books. $2 local $3 554714
690 $a 0544
690 $a 0984
690 $a 0464
690 $a 0800
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of California, Irvine. $b Electrical and Computer Engineering. $3 1192604
773 0 $t Dissertations Abstracts International $g 85-11B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30995682 $z click for full text (PQDT)