Framework for cyber-physical interaction aware test case generation to identify operational changes
The operational characteristics of a cyber-physical system (CPS) may deviate from the certified system due to intended (in case of cheating) or unintended (wear and tear) reasons. A computer-implemented certification system makes test case search aware of the multidimensional interactions between the cyber and physical subsystems and addresses practical dynamical system problems like Zeno behavior and dynamical model divergence. The system dynamically modulates an input search space by predicting and limiting input variations that can potentially cause divergence or Zeno behavior.
1 . A system, comprising:
a processor in communication with a memory and including instructions executable by the processor to:
access, at the processor, contract information of a dynamic contract defining a reference model, an input space, and an output space of a contract for certification of a cyber-physical system, the contract information including:
information descriptive of a dynamical cyber-physical interaction model of the cyber-physical system that characterizes interactions between a set of state variables that describe an operation of the cyber-physical system;
information descriptive of an input space for construction of an input vector associated with the dynamical cyber-physical interaction model; and
information descriptive of an output space of an output vector associated with the dynamical cyber-physical interaction model;
simulate, at the processor, the dynamical cyber-physical interaction model for a plurality of time steps using a candidate input vector to generate a corresponding candidate output vector;
modify, at the processor, the input space of the contract information for an input vector and for an output vector that corresponds with the input vector based on the set of state variables of the dynamical cyber-physical interaction model such that:
a rate of change of the input vector is below a first threshold value, the rate of change of the input vector being defined in terms of interactions between the set of state variables of the dynamical cyber-physical interaction model and being computed from differences between input values of the input vector at two simulation time steps; and
a time difference between two successive zero crossings of the output vector of the dynamical cyber-physical interaction model is above a second threshold value associated with a simulation time step lower limit, the time difference between two successive zero crossings being defined in terms of interactions between the set of state variables of the dynamical cyber- physical interaction model and the input vector and being computed by detecting successive sign changes of the candidate output vector across simulation time steps; and
reject, at the processor, the candidate input vector for inclusion within a test case input vector when the computed rate of change is above the first threshold value or when the computed time difference between two successive zero crossings is below the second threshold value, and regenerate a further candidate input vector for evaluation; and
select, at the processor, input values of a test case input vector of a test case for application to the cyber-physical system that satisfies the input space of the contract in terms of the dynamical cyber-physical interaction model after modification of the input space and rejection of candidate input vectors that violate the first threshold value or the second threshold value;
apply the test case input vector to the cyber-physical system to generate a test case output vector;
determine a distance between a candidate output vector corresponding to the test case input vector and the test case output vector; and
detect the presence of software doping mischaracterization of the dynamical cyber-physical interaction model, or an unintentional software-configuration change within the cyber-physical system where the distance between the candidate output vector and test case output vector exceeds a threshold value.
2 . The system of claim 1 , where the dynamical cyber-physical interaction model represents interactions between a controller of the cyber-physical system and a physical system of the cyber-physical system.
3 . The system of claim 1 , where modification of the input space of the contract based on the set of state variables with respect to the time difference between two successive zero crossings avoids Zeno behavior of the dynamical cyber-physical interaction model near zero crossing events for a given initial condition of one or more state variables of the set of state variables of the dynamical cyber-physical interaction model.
4 . The system of claim 1 , where modification of the input space of the contract based on the set of state variables with respect to the rate of change of the input vector avoids divergence of a corresponding output of the dynamical cyber-physical interaction model.
5 . The system of claim 1 , where the input vector being an input to the dynamical cyber-physical interaction model for an nth time step and the output vector being an output of the dynamical cyber-physical interaction model for the nth time step that corresponds with the input vector.
6 . The system of claim 1 , the memory further including instructions executable by the processor to:
search, at the processor, the input space for the input values of the test case input vector of the test case following modification of the input space of the contract information, the test case satisfying the input space of the contract information in terms of the dynamical cyber-physical interaction model and violating the output space of the contract information.
7 . The system of claim 6 , searching the input space for input values of the test case input vector of the test case includes applying a labeled transition system satisfiability algorithm to the input vector to determine suitability of the input vector for inclusion within the test case input vector.
8 . The system of claim 1 , the memory further including instructions executable by the processor to:
reject, at the processor, the input vector for inclusion within the test case input vector where the rate of change of the input vector is above the first threshold value.
9 . The system of claim 1 , the memory further including instructions executable by the processor to:
reject, at the processor, the input vector for inclusion within the test case input vector where the time difference between two successive zero crossings of the output vector of the dynamical cyber-physical interaction model is below the second threshold value.
10 . The system of claim 1 , where the cyber-physical system is a vehicle and where the dynamical cyber-physical interaction model characterizes interactions between a set of state variables of the vehicle.
11 . The system of claim 10 , where the input vector includes speed values applied to a controller of the vehicle and where the output vector includes emissions values generated by a physical system of the vehicle based on the input vector.
12 . A method, comprising:
accessing, at a processor in communication with a memory, contract information for certification of a cyber-physical system, the contract information including:
information descriptive of a dynamical cyber-physical interaction model of the cyber-physical system that characterizes interactions between a set of state variables that describe operation of the cyber-physical system;
information descriptive of an input space for construction of an input vector associated with the dynamical cyber-physical interaction model; and
information descriptive of an output space of an output vector associated with the dynamical cyber-physical interaction model;
simulating, at the processor, the dynamical cyber-physical interaction model for a plurality of time steps using a candidate input vector to generate a corresponding candidate output vector;
modifying, at the processor, the input space of the contract information for an input vector and for an output vector that corresponds with the input vector based on the set of state variables of the dynamical cyber-physical interaction model such that:
a rate of change of the input vector is below a first threshold value, the rate of change of the input vector being defined in terms of interactions between the set of state variables of the dynamical cyber-physical interaction model and being computed from differences between input values of the candidate input vector at two simulation time steps; and
a time difference between two successive zero crossings of the output vector of the dynamical cyber-physical interaction model is above a second threshold value associated with a simulation time step lower limit, the time difference between two successive zero crossings being defined in terms of interactions between the set of state variables of the dynamical cyber-physical interaction model and the input vector x and being computed by detecting successive sign changes of the candidate output vector across simulation time steps,
rejecting, at the processor, the candidate input vector where the computed rate of change is above the first threshold value or where the computed time difference between two successive zero crossings is below the second threshold value, and regenerating a further candidate input vector for evaluation; and
selecting, at the processor, input values of a test case input vector of a test case for application to the cyber-physical system that satisfies the input space of the contract information in terms of the dynamical cyber-physical interaction model after modification of the input space and rejection of candidate input vectors that violate the first threshold value or the second threshold value, wherein application of the test case input vector to the cyber-physical system enables detection of software doping mischaracterization of the dynamical cyber-physical interaction model, or an unintentional software-configuration change based on an output discrepancy between the cyber-physical system and the dynamical cyber-physical interaction model.
13 . The method of claim 12 , where the dynamical cyber-physical interaction model represents interactions between a controller of the cyber-physical system and a physical system of the cyber-physical system.
14 . The method of claim 12 , where modifying the input space of the contract information based on the set of state variables with respect to the time difference between two successive zero crossings avoids Zeno behavior of the dynamical cyber-physical interaction model near zero crossing events for a given initial condition of one or more state variables of the set of state variables of the dynamical cyber-physical interaction model.
15 . The method of claim 12 , where modifying the input space of the contract information based on the set of state variables with respect to the rate of change of the input vector avoids divergence of a corresponding output of the dynamical cyber-physical interaction model.
16 . The method of claim 12 , the input vector being an input to the dynamical cyber-physical interaction model for an nth time step and the output vector being an output of the dynamical cyber-physical interaction model for the nth time step that corresponds with the input vector.
17 . The method of claim 12 , further comprising:
searching, at the processor, the input space for the input values of the test case input vector of the test case following modification of the input space of the contract information, the test case satisfying the input space of the contract information in terms of the dynamical cyber-physical interaction model and violating the output space of the contract information.
18 . The method of claim 17 , wherein searching the input space for input values of the test case input vector of the test case includes applying a labeled transition system satisfiability algorithm to the input vector to determine suitability of the input vector for inclusion within the test case input vector.
19 . The method of claim 12 , further comprising:
rejecting, at the processor, the input vector for inclusion within the test case input vector where the rate of change of the input vector is above the first threshold value.