Accession Number:

ADA581703

Title:

Optimal Index Policies for Quickest Localization of Anomaly in Resource-Constrained Cyber Networks

Descriptive Note:

Research paper

Corporate Author:

CALIFORNIA UNIV DAVIS DEPT OF ELECTRICAL AND COMPUTER ENGINEERING

Personal Author(s):

• Cohen, Kobi
• Zhao, Qing
• Swami, Ananthram

Report Date:

2013-01-01

Pagination or Media Count:

16.0

Abstract:

We consider the problem of quickest localization of anomaly in a resource-constrained cyber network consisting of multiple components. Due to resource constraints, only one component can be probed at a time. The observations are random realizations drawn from two different distributions depending on whether the component is normal or anomalous. Components are assigned priorities. Components with higher priorities in an abnormal state should be fixed before components with lower priorities to reduce the overall damage to the network. We formulate the problem as a priority-based constrained optimization problem. The objective is to minimize the expected weighted sum of completion times of abnormal components subject to error probability constraints. We then propose a two-stage optimization formulation to solve the problem. First, we consider the independent model, in which each component is abnormal independent of other components. Next, we consider the exclusive model, in which only one component is abnormal. We develop optimal index policies under both models. Optimal low-complexity algorithms are derived for the simple hypotheses case, in which the distribution is completely known under both hypotheses. Asymptotically as the error probability approaches zero optimal low-complexity algorithms are derived for the composite hypotheses case, where there is uncertainty in the distribution parameters. Simulation results demonstrate the performance of the algorithms.

Descriptors:

• *ANOMALIES
• *COMPUTER NETWORKS
• *INTRUSION DETECTION(COMPUTERS)
• *OPTIMIZATION
• *POLICIES
• *QUICK REACTION
• *UNCERTAINTY
• ALGORITHMS
• COMPUTERIZED SIMULATION
• HYPOTHESES
• MAXIMUM LIKELIHOOD ESTIMATION
• PROBABILITY
• PROBLEM SOLVING
• STATISTICAL ANALYSIS

Subject Categories:

• Statistics and Probability
• Computer Systems Management and Standards

Distribution Statement:

APPROVED FOR PUBLIC RELEASE