A kolmogorov complexity approach for measuring attack path complexity

A Kolmogorov Complexity Approach for Measuring Attack Path ComplexityBy Nwokedi C. Idika & Bharat BhargavaPresented by Bharat BhargavaOutlineMotivationThe Kolmogorov Complexity Method (KCM)The K-step Capability Accumulation Metric (KCA)Applying KCM to KCAMotivationPerfect enterprise security is impossible to achieve, and must be approximatedThe difficulty associated with causing a security breach is used as an indicator of the quality of an enterprise’s securityThe ability of an attacker to exploit a vulnerability is referred to as exploitabilityExploitability is ImportantCommon Vulnerability Scoring System (CVSS)exploitability is incorporated scoring of vulnerabilitiesComputer Emergency Response Team/ Coordination Center (CERT/CC)has a numeric score based exploitabilitySANS Critical Vulnerability Analysis Scale Rating 2 of its 4 ratings include exploitabilityThus, assessing the difficulty of attack paths is important!Representing Attack Paths with Attack GraphsTotal Attack Paths: 4Issues with RepresentationCounting the number of paths is straightforward (usually)Measuring the complexity of each attack is non-trivial Choices for determining attack complexity have been made in the literatureHowever, these choices lack consistency, and fail to make some of the modeler’s assumptions explicit If security metrics will become more of a science, we will need a standard way of communicating our measurements!What We Would LikeA standard way of measuring attack path complexity that is grounded in some sound theoryA attack path measurement approach that incorporates the assumptions of the modelerA way of measuring attack paths that provides a modeler sufficient flexibility to model the attack path as desiredThe Kolmogorov Complexity Method achieves these aimsKolmogorov Complexity (KC)KC determines a string’s complexity by using the size of the smallest program that can produce that stringLet K be a the function that returns the KC of a stringGiven strings x1 and x2, if K(x1) < K(x2), then x2 is more complex than x1Idea: If we model attack paths as strings, we can apply KC to attack pathsRepresenting Attack PathsAlphabetA corresponds to the set of all exploits (i.e., instances of vulnerabilities) found in all attack graphs under considerationConstantsε is the empty stringvi ∈ A denotes that an exploit from an attack graph ∅ corresponds to the empty setRepresenting Attack Paths (II)OperatorsLet S and T be two strings composed of characters from ALet E1 and E2 be expressions in the languageST evaluates to the concatenation of strings S and T() provides priority ordering(S)+ denotes that S may repeat one or more timesRepresenting Attack Paths (III)Operators (continued...)Sk evaluates to k instances of S concatenated togetherE1[k]E2 evaluates to the insertion of E1 into index k of E2 where the first character of E2 is index 0 (the above can be generalized to E1[k1],[k2],...[kn]E2)E1l,[k]E2 concatenate E1l to E2 and insert E1 into the kth index of E2E1l[k]E2 inserts E1l into the kth index of E2The Kolmogorov Complexity Method (KCM) Applied to an Attack PathQuantitative Representation: v1v1v1v2v3v1v1Qualitative Representations: v13,2[2]v2v3, v13,[2]v2v3v1, v13v2v3v1v1 Each representation makes explicit distinct assumptions about the attack path KCM Can Handle Cyclic Attack PathsA Representation: v12(v1v2v3)+v12OutlineMotivationThe Kolmogorov Complexity Method (KCM)The K-step Capability Accumulation Metric (KCA)Applying KCM to KCAPreviously Proposed MetricsCapability Metrics: measure security in terms of an attacker’s capability Number of Paths (Ortalo et al. ’99), Weakest Adversary (Pamula et al. ’06), Network Compromise Percentage (Lippmann et al. ’06)Complexity Metrics: measure security in terms of effortShortest Path (Phillips & Swiler ’98), Mean of Path Lengths (Li & Vaughn ’06)The K-Step Capability Accumulation Metric (KCA)KCA is a hybrid of a complexity metric and a capability metricMore than how difficult it is to cause a security breach, or what capabilities can an attacker obtain, KCA is concerned with the amount of capability an attacker can attain for varying levels of attack effortIntuition: In general, a network that can be compromised in a single attack step is less secure than another network that requires a series of multiple attack steps to compromise the network KCA: Comparing 2 Attack GraphsG1G2KCA1(G1) = KCA1(G2)KCA2(G1) < KCA2(G2)G1 is more secure than G2Adapting KCA for KCMAssuming the KCM qualitative representationCappi(G) = ∪ capabilities(pi)Let q1 through qn be quantitative representations of the attack paths p1 through pn respectively qj0...i is the substring of qj from index 0 to index iqji is the ith position of of qjAdapting KCA for KCM (II)Similar definitions exist for se(sj0...i) = qj0...m, such that sji = qjm and qjm ≠ qjm+1 also ∀ v ∈ qj0...m, v ∈ sj0...iThis gives the following:KCAk(G) = ∪i=1kCape(sj0...i)(G), for all attack paths jSummaryWe have proposed a methodology for measuring attack paths, the Kolmogorov Complexity Method (KCM)We have proposed a novel security metric that combines complexity and capabilities obtained by the attacker, the K-step Capability Accumulation Metric (KCA)We have shown that KCM can be applied to a security metric, namely, KCAThank You