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

Share

COinS