SYSTEM AND METHOD FOR FEEDBACK-GUIDED TEST GENERATION FOR CYBER-PHYSICAL SYSTEMS USING MONTE-CARLO

• US 20100094611A1
• Filed: 10/14/2009
• Published: 04/15/2010
• Est. Priority Date: 10/14/2008
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Sankaranarayanan, Sriram, Nghiem, Truong, Gupta, Aarti, Ivancic, Franjo
• Granted Patent: US 8,374,840 B2
• Time in Patent Office: Days
• US Class Current: 703/22
• CPC Class Codes: G01R 31/318357 Simulation computer simulation of digital circuits G06F30/3308

Abstract

A system and method for generating test vectors includes generating traces of a system model or program stored in memory using a simulation engine. Simulated inputs are globally optimized using a fitness objective computed using a computer processing device. The simulation inputs are adjusted in accordance with feedback from the traces and fitness objective values by computing a distance between the fitness objective value and a reachability objective. Test input vectors are output based upon optimized fitness objective values associated with the simulated inputs to test the system model or program stored in memory.

Claims

1. A method for generating test vectors in cyber-physical systems, comprising:

generating traces of a system model or program of a mixed-discrete-continuous system stored in memory using a simulation engine;

globally optimizing simulated inputs using a fitness objective computed using a computer processing device, the simulation inputs being sampled in regions of state-space and being adjusted in accordance with feedback from the traces and fitness objective values by computing a distance between the fitness objective value and a reachability objective; and

outputting test input vectors based upon optimized fitness objective values associated with the simulated inputs to test the system model or program stored in memory.

2. The method as recited in claim 1, further comprising testing the system model or program by answering reachability questions for the system model or program by searching for safety violations that include non-linear dynamics by sampling in the state-space.

3. The method as recited in claim 1, wherein globally optimizing includes sampling inputs to minimize the fitness objective value using a failed distance method.

4. The method as recited in claim 1, wherein globally optimizing includes sampling inputs to minimize a fitness objective value using a Hit-and-Run Monte-Carlo based sampling.

5. The method as recited in claim 1, wherein the traces include partially symbolic traces and concrete traces.

6. The method as recited in claim 1, wherein the reachability objectives are determined by a target selection module configured to output test input vectors for testing a program.

7. The method as recited in claim 1, wherein globally optimizing includes receiving feedback from the traces and updated fitness values to compare the fitness values to the reachability objectives such that an input vector set is steered to an improved set of input vectors in accordance with a constraint to limit regions of state-space that are sampled.

8. The method as recited in claim 7, wherein the constraints are user-defined.

9. A computer readable storage medium comprising a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform the steps of claim 1.

14. The system as recited in claim 1, wherein the optimizer globally optimizes the fitness objective by iterating to find an improved set of input vectors in accordance with a constraint to limit regions of state-space that are sampled.

10. A system for generating test vectors for cyber-physical systems, comprising:

a concrete simulation engine including a symbolic trace follower configured to generate partially symbolic traces of a system model or program of a mixed-discrete-continuous system stored in memory, the concrete simulation engine further configured to output concrete traces of the system model or program;

a fitness objective stored in memory and computed using a computer processing device;

an optimizer configured to generate simulated inputs which are sampled in regions of state-space and optimize the simulated inputs based on distances computed between fitness objective values and the target; and

a coverage selection tool configured to determine targets and to output test input vectors in accordance with the optimized simulated inputs.

11. The system as recited in claim 10, wherein the optimizer answers reachability questions by searching for safety violations that include non-linear dynamics by sampling in the state-space.

12. The system as recited in claim 10, wherein the simulated inputs are sampled by the optimizer to minimize the fitness objective value using a failed distance method.

13. The system as recited in claim 10, wherein the simulated inputs are sampled by the optimizer to minimize the fitness objective value using a Hit-and-Run Monte-Carlo based sampling.