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

• US 20040064735A1
• Filed: 08/11/2003
• Published: 04/01/2004
• 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 National Security Solutions Incorporated (BAE Systems Plc)
• Inventors: Frazier, Tiffany M., Kreidl, O. Patrick
• Granted Patent: US 7,363,515 B2
• Time in Patent Office: Days
• US Class Current: 713/201
• 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 at least a part of 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) to provide a model of 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 using the PO-MDP to model 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 using 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 model includes states of at least part of at least one of an electronic intrusion and an electronic attack based 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.

23. A system for controlling at least a part of a microprocessor device, the system comprising:

a partially observable Markov decision process (PO-MDP) controller, the PO-MDP controller comprising;

two or more states based on one or more objectives of an electronic attack,

one or more state transition probabilities based on a state at a stage k and a control at a stage k,

one or more sensor observation probabilities based on the state at stage k and a control at a stage k−

1,

one or more state transition costs based on the state at stage k, the control at stage k−

1, and a state estimate for stage k+1,

a recursive estimator to generate a probabilistic state estimate for stage k, and,

a response policy to associate the probabilistic state estimate to a control for stage k.

24. A system according to claim 23, where the recursive estimator computes a sufficient statistic.

25. A system according to claim 23, where the probabilistic state estimate is a sufficient statistic.

26. A system according to claim 23, further comprising at least one actuator to affect the control for stage k.

27. A system according to claim 23, further comprising one or more sensors to provide one or more sensor observations based on the system.

28. A system according to claim 27, where the one or more sensor observations include sensor observations based on at least one of:

a process activity associated with the system, a network activity associated with the system, and a kernel activity associated with the system.

29. A system according to claim 23, where the system includes at least a part of at least one of:

a microprocessor-controlled device and a set of instructions.

30. A system according to claim 23, where the system states include one or more states associated with at least one of an electronic attack and an electronic intrusion.

31. A system according to claim 23, where the control for stage k includes at least one of a default process and a kill process.