Safe inputs approximation for black-box systems

• Main Authors: XUE, Bai, LIU, Yang, MA, Lei, ZHANG, Xiyue, SUN, Meng, XIE, Xiaofei
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Black-box systems; Linear programming; Probably approximate safety; OS and Networks; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/7074; https://ink.library.smu.edu.sg/context/sis_research/article/8077/viewcontent/464600a180.pdf
• Institution: Singapore Management University

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.