Control systems and methods using a partially-observable markov decision process (PO-MDP)

• US 7,363,515 B2
• Filed: 08/11/2003
• Issued: 04/22/2008
• Est. Priority Date: 08/09/2002
• Status: Active Grant

• Current Assignee: BAE Systems Information and Electronic Systems Integration Incorporated (BAE Systems Plc)
• Original Assignee: BAE Systems Advanced Information Technologies, Inc. (BAE Systems Plc)
• Inventors: Frazier, Tiffany M., Kreidl, O. Patrick
• Primary Examiner(s): Moazzami, Nasser
• Assistant Examiner(s): Okoronkwo, Chinwendu C
• Application Number:
  US10/638,818
• Publication Number:
  US 20040064735A1
• Time in Patent Office: 1,716 Days
• Field of Search: 713/150, 726/2, 726/22, 726/26
• US Class Current: 703/2
• CPC Class Codes: G06F 21/316 by observing the pattern of computer usage, e.g. typical user behaviour
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06F 21/554 involving event detection and direct action

Abstract

Methods and systems for controlling at least a part of a microprocessor system, that include, based at least in part on objectives of at least one electronic attack, using a partially observable Markov decision process (PO-MDP) to provide a model of at least part of the microprocessor system, the PO-MDP including a controller, the controller including an estimation policy to recursively generate a state estimate at stage k based on a state estimate at stage k−1, a control at stage k−1, and an observation at stage k, and, a response policy to select a control at stage k based on the state estimate at stage k, and cause the selected control to be provided to at least a part of the microprocessor system.

Claims

1. A method for controlling a microprocessor system, the method comprising:

based at least in part on objectives of at least one electronic attack, using a partially observable Markov decision process (PO-MDP) for modeling at least part of the microprocessor system, the PO-MDP including a controller, the controller comprising;

an estimation policy to recursively generate a state estimate at stage k based on a state estimate at stage k−

1, a control at stage k−

1, and an observation at stage k, and,

a response policy to select a control at stage k based on the state estimate at stage k, and cause the selected control to be provided to at least a part of the microprocessor system.

2. A method according to claim 1, where modeling includes collecting at least one training set based on a sample electronic attack.

3. A method according to claim 2, where collecting includes collecting from one or more sensors, where the one or more sensors are in communications with at least part of the microprocessor system.

4. A method according to claim 3, where collecting includes determining sensor observation probabilities.

5. A method according to claim 1, further comprising selecting the estimation policy and the response policy to minimize an average cost per stage.

6. A method according to claim 5, where selecting the response policy includes selecting based on at least one of:

an infinite-horizon assumption and a multi-state look-ahead optimization technique.

7. A method according to claim 5, where selecting the estimation policy includes constructing a recursive estimator to provide a sufficient statistical state estimate.

8. A method according to claim 1, where modeling includes:

selecting the estimation policy based on minimizing an error per stage.

9. A method according to claim 8, where minimizing the error per stage includes determining a distance metric.

10. A method according to claim 9, where determining the distance metric includes determining a difference between an estimate of each state of the model, and the true state.

11. A method according to claim 9, where determining the distance metric includes computing a Euclidean norm.

12. A method according to claim 8, further comprising:

selecting the response policy based on a fixed estimation policy and minimizing the average cost per stage.

13. A method according to claim 12, where minimizing the average cost per stage includes determining a minimum cost-to-go based on the state estimate at stage k.

14. A method according to claim 1, further comprising:

receiving observations from one or more sensors at stage k, and,

associating the observations with observation probabilities based on the state estimate at stage k and the control at stage k−

1.

15. A method according to claim 14, where receiving observations includes producing a distance measure based on the received observations.

16. A method according to claim 14, where receiving observations include applying the received observations to a detection scheme.

17. A method according to claim 16, where the detection scheme includes employing a Bayesian classifier.

18. A method according to claim 1, further comprising specifying at least one of:

a state space associated with the model, a control space associated with the model, and an observation space associated with the model.

19. A method according to claim 1, further comprising specifying one or more state transition probabilities for a state at stage k+1 based on the state at stage k and a control at stage k.

20. A method according to claim 1, further comprising specifying one or more sensor observation probabilities for stage k based on a state at stage k and a control at stage k−

1.

21. A method according to claim 1, where the system states includes states of at least one of an electronic intrusion and an electronic attack on at least a part of at least one of:

a microprocessor-controlled device and a set of instructions.

22. A method according to claim 1, where the model is a stationary model.