Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
11-2019
Abstract
Given a family of independent and identically distributed samples extracted from the input region and their corresponding outputs, in this paper we propose a method to under-approximate the set of safe inputs that lead the blackbox system to respect a given safety specification. Our method falls within the framework of probably approximately correct (PAC) learning. The computed under-approximation comes with statistical soundness provided by the underlying PAC learning process. Such a set, which we call a PAC under-approximation, is obtained by computing a PAC model of the black-box system with respect to the specified safety specification. In our method, the PAC model is computed based on the scenario approach, which encodes as a linear program. The linear program is constructed based on the given family of input samples and their corresponding outputs. The size of the linear program does not depend on the dimensions of the state space of the black-box system, thus providing scalability. Moreover, the linear program does not depend on the internal mechanism of the black-box system, thus being applicable to systems that existing methods are not capable of dealing with. Some case studies demonstrate these properties, general performance and usefulness of our approach.
Keywords
Black-box systems; Linear programming; Probably approximate safety
Discipline
OS and Networks | Software Engineering
Research Areas
Software and Cyber-Physical Systems
Publication
Proceedings of the 24th International Conference on Engineering of Complex Computer Systems, Guangzhou, China, 2019 November 10-13
First Page
180
Last Page
189
ISBN
9781728146461
Identifier
10.1109/ICECCS.2019.00027
Publisher
IEEE
City or Country
Guangzhou, China
Citation
XUE, Bai; LIU, Yang; MA, Lei; ZHANG, Xiyue; SUN, Meng; and XIE, Xiaofei.
Safe inputs approximation for black-box systems. (2019). Proceedings of the 24th International Conference on Engineering of Complex Computer Systems, Guangzhou, China, 2019 November 10-13. 180-189.
Available at: https://ink.library.smu.edu.sg/sis_research/7074
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.