Skip to content

Reasoning over Possible Histories

This page is not normative

This page is not considered a core part of the Vultron Protocol as proposed in the main documentation. Although within the page we might provide guidance in terms of SHOULD, MUST, etc., the content here is not normative.

Our goal in this section is to formulate a way to rank our undifferentiated desiderata \(\mathbb{D}\) from On the Desirability of Possible Histories in order to develop the concept of CVD skill and its measurement in Discriminating Skill and Luck. This will provide a baseline expectation about CS events.

History Frequency Analysis

As described in Random Walks, we apply the principle of indifference to the available transition events \(\sigma_{i+1}\) at each state \(q\) for each of the possible histories to compute the expected frequency of each history, which we denote as \(f_h\).

Frequency of a History

The frequency of a history \(f_h\) is the cumulative product of the probability \(p\) of each event \(\sigma_i\) in the history \(h\). We are only concerned with histories that meet our sequence constraints, namely \(h \in \mathcal{H}\).

\[\label{eq:history_freq} f_h = \prod_{i=0}^{5} p(\sigma_{i+1}|h_i) %\textrm{ where } \sigma_i \in h \textrm{ and } h \in H\]

The Possible Histories table displays the value of \(f_h\) for each history. Having an expected frequency (\(f_h\)) for each history \(h\) will allow us to examine how often we might expect our desiderata \(d \in \mathbb{D}\) to occur across \(\mathcal{H}\).

Choosing uniformly over event transitions is more useful than treating the six-element histories as uniformly distributed.

Uniform Distribution over Histories vs Transitions

For example, \(\mathbf{P} \prec \mathbf{A}\) in 59% of valid histories, but when histories are weighted by the assumption of uniform state transitions \(\mathbf{P} \prec \mathbf{A}\) is expected to occur in 67% of the time. These differences arise due to the dependencies between some states. Since CVD practice is comprised of a sequence of events, each informed by the last, our uniform distribution over events is more likely a useful baseline than a uniform distribution over histories.

Event Order Frequency Analysis

Each of the event pair orderings in the Event Order Table (reproduced below from Desirable Histories can be treated as a Boolean condition that either holds or does not hold in any given history.

Ordered Pairs of Events

This table displays all 36 possible orderings of paired transitions and whether they are considered impossible, required (as defined by the formalized constraints reproduced below for convenience)

\(\prec\) \(\mathbf{V}\) \(\mathbf{F}\) \(\mathbf{D}\) \(\mathbf{P}\) \(\mathbf{X}\) \(\mathbf{A}\)
\(\mathbf{V}\) -
\(\mathbf{F}\) -
\(\mathbf{D}\) -
\(\mathbf{P}\) -
\(\mathbf{X}\) -
\(\mathbf{A}\) -

Key: = Required, = Desired, = Undesired, = Impossible, = row, = column \(\prec\) = precedes

Above, we described how to compute the expected frequency of each history (\(f_h\)) given the presumption of indifference to possible events at each step. We can use \(f_h\) as a weighting factor to compute the expected frequency of event orderings (\(\sigma_i \prec \sigma_j\)) across all possible histories \(H\).

Formalizing Event Order Frequency

The following equations define the frequency of an ordering \(f_{\sigma_i \prec \sigma_j}\) as the sum over all histories in which the ordering occurs (\(H^{\sigma_i \prec \sigma_j}\)) of the frequency of each such history (\(f_h\)) as shown in the Possible Histories table.

\[ H^{\sigma_i \prec \sigma_j} \stackrel{\mathsf{def}}{=}\{h \in H \textrm{ where } \sigma_i \prec \sigma_j \textrm{ is true for } h \textrm{ and } i \neq j\} \]
\[ f_{\sigma_i \prec \sigma_j} \stackrel{\mathsf{def}}{=}\sum_{h \in H^{\sigma_i \prec \sigma_j}} {f_h} \]

The table below displays the results of this calculation.

Expected Frequency of \({row} \prec {col}\) when events are chosen uniformly from possible transitions in each state

\(\mathbf{V}\) \(\mathbf{F}\) \(\mathbf{D}\) \(\mathbf{P}\) \(\mathbf{X}\) \(\mathbf{A}\)
\(\mathbf{V}\) 0 1 1 0.333 0.667 0.750
\(\mathbf{F}\) 0 0 1 0.111 0.333 0.375
\(\mathbf{D}\) 0 0 0 0.037 0.167 0.187
\(\mathbf{P}\) 0.667 0.889 0.963 0 0.500 0.667
\(\mathbf{X}\) 0.333 0.667 0.833 0.500 0 0.500
\(\mathbf{A}\) 0.250 0.625 0.812 0.333 0.500 0

Required event orderings have an expected frequency of 1, while impossible orderings have an expected frequency of 0. As defined in On the Desirability of Possible Histories, each desiderata \(d \in \mathbb{D}\) is specified as an event ordering of the form \(\sigma_i \prec \sigma_j\). We use \(f_d\) to denote the expected frequency of a given desiderata \(d \in \mathbb{D}\). The values for the relevant \(f_d\) appear in the upper right of the Event Frequency table above.

Some event orderings have higher expected frequencies than others

For example, vendor awareness precedes attacks in 3 out of 4 histories in a uniform distribution of event transitions (\(f_{\mathbf{V} \prec \mathbf{A}} = 0.75\)), whereas fix deployed prior to public awareness holds in less than 1 out of 25 (\(f_{\mathbf{D} \prec \mathbf{P}} = 0.037\)) histories generated by a uniform distribution over event transitions.

Hasse Diagram for the Partial Order on Desiderata

The full Hasse Diagram for the partial order \((\mathbb{D},\leq_{\mathbb{D}})\) is shown below. The most skillful (lowest frequency) orderings are at the top of the diagram, while the least skillful (highest frequency) ones are at the bottom.

flowchart TD
    dp(["D ≺ P"])
    fp(["F ≺ P"])
    dx(["D ≺ X"])
    da(["D ≺ A"])
    fx(["F ≺ X"])
    vp(["V ≺ P"])
    fa(["F ≺ A"])
    px(["P ≺ X"])
    xa(["X ≺ A"])
    pa(["P ≺ A"])
    vx(["V ≺ X"])
    va(["V ≺ A"])

    dp --- fp
    fp --- dx
    dx --- da
    da --- fx
    da --- vp
    fx --- fa
    vp --- fa
    fa --- px
    fa --- xa
    px --- pa
    xa --- pa
    px --- vx
    xa --- vx
    vx --- va
    pa --- va

A Partial Order on Desiderata

Skill, on the other hand, accounts for the outcomes once luck has been accounted for. So the more likely an outcome is due to luck, the less skill we can infer when it is observed.

Skill is inversely proportional to luck

As an example, from the Event Frequency Table above we see that fix deployed before the vulnerability is public is the rarest of our desiderata with \(f_{\mathbf{D} \prec \mathbf{P}} = 0.037\), and thus exhibits the most skill when observed. On the other hand, vendor awareness before attacks is expected to be a common occurrence with \(f_{\mathbf{V} \prec \mathbf{A}} = 0.75\).

We can therefore use the set of \(f_d\) to construct a partial order over \(\mathbb{D}\) in which we prefer desiderata \(d\) which are more rare (and therefore imply more skill when observed) over those that are more common.

A Partial Order on Desiderata

We create the partial order on \(\mathbb{D}\) as follows: for any pair \(d_1,d_2 \in \mathbb{D}\), we say that \(d_2\) exhibits less skill than \(d_1\) if \(d_2\) occurs more frequently in \(\mathcal{H}\) than \(d_1\).

\[ (\mathbb{D},\leq_{\mathbb{D}}) \stackrel{\mathsf{def}}{=}d_2 \leq_{\mathbb{D}} d_1 \iff {f_{d_2}} \stackrel{\mathbb{R}}{\geq} {f_{d_1}} \]

Note that the inequalities on the left and right sides of the above are flipped because skill is inversely proportional to luck. Also, while \(\leq_{\mathbb{D}}\) on the left side of the above defines a preorder over the poset \(\mathcal{H}\), the \(\stackrel{\mathbb{R}}{\geq}\) is the usual ordering over the set of real numbers. The result is a partial order \((\mathbb{D},\leq_{\mathbb{D}})\) because a few \(d\) have the same \(f_d\) (\(f_{\mathbf{F} \prec \mathbf{X}} = f_{\mathbf{V} \prec \mathbf{P}} = 0.333\) for example).


Ordering Possible Histories by Skill

Next we develop a new partial order on \(\mathcal{H}\) given the partial order \((\mathbb{D},\leq_{\mathbb{D}})\) just described.

Refining a Skill Metric for Histories

We observe that \(\mathbb{D}^{h}\) acts as a Boolean vector of desiderata met by a given \(h\). Since \(0 \leq f_d \leq 1\), simply taking its inverse could in the general case lead to some large values for rare events. For convenience, we use \(-log(f_d)\) as our proxy for skill. For example, if a desideratum were found to occur in every case (indicating no skill required), \(f_d=1\) and therefore \(-log(1) = 0\). On the other hand, for increasingly rare desiderata, our skill metric rises: \(\lim_{f_d \to 0} -log(f_d) = +\infty\).

Taking the dot product of \(\mathbb{D}^h\) with the set of \(-log(f_d)\) values for each \(d \in \mathbb{D}\) represented as a vector, we arrive at a single value representing the skill exhibited for each history \(h\). Careful readers may note that this value is equivalent to the TF-IDF score for a search for the "skill terms" represented by \(\mathbb{D}\) across the corpus of possible histories \(\mathcal{H}\).

We have now computed a skill value for every \(h \in \mathcal{H}\), which allows us to sort \(\mathcal{H}\) and assign a rank to each history \(h\) contained therein. The rank is shown in the Possible Histories table, reproduced below for convenience.

The Possible Histories of CVD, Ranked by Skill

The table below shows the possible histories of CVD, ranked by skill. The rank is ordered from least skillful to most skillful histories. Rank values start at 1 for least skill up to a maximum of 62 for most skill. Owing to the partial order \((\mathbb{D},\leq_{\mathbb{D}})\), some \(h\) have the same computed skill values, and these are given the same rank.

See Possible Histories table for the development of the table.

# \(h \in \mathcal{H}\) rank \(\mathbb{D}^h\) count \(f_h\)
0 (A, X, P, V, F, D) 1 0 0.0833
1 (A, P, V, X, F, D) 2 2 0.0417
2 (A, V, X, P, F, D) 3 2 0.0278
3 (X, P, V, A, F, D) 4 3 0.1250
4 (V, A, X, P, F, D) 5 3 0.0208
5 (P, V, A, X, F, D) 6 4 0.0417
6 (A, V, P, X, F, D) 7 3 0.0139
7 (A, P, V, F, X, D) 7 3 0.0208
8 (X, P, V, F, A, D) 8 4 0.0625
9 (V, A, P, X, F, D) 9 4 0.0104
10 (P, V, X, A, F, D) 10 5 0.0417
11 (V, P, A, X, F, D) 11 5 0.0104
12 (P, V, A, F, X, D) 11 5 0.0208
13 (V, X, P, A, F, D) 11 5 0.0312
14 (A, V, P, F, X, D) 12 4 0.0069
15 (A, P, V, F, D, X) 13 4 0.0208
16 (V, A, P, F, X, D) 14 5 0.0052
17 (X, P, V, F, D, A) 15 5 0.0625
18 (P, V, X, F, A, D) 16 6 0.0208
19 (A, V, F, X, P, D) 17 4 0.0093
20 (V, P, X, A, F, D) 18 6 0.0104
21 (P, V, F, A, X, D) 19 6 0.0139
22 (V, X, P, F, A, D) 19 6 0.0156
23 (V, P, A, F, X, D) 20 6 0.0052
24 (V, A, F, X, P, D) 21 5 0.0069
25 (P, V, A, F, D, X) 22 6 0.0208
26 (A, V, P, F, D, X) 23 5 0.0069
27 (A, V, F, P, X, D) 24 5 0.0046
28 (P, V, F, X, A, D) 25 7 0.0139
29 (V, P, X, F, A, D) 25 7 0.0052
30 (V, A, P, F, D, X) 26 6 0.0052
31 (V, A, F, P, X, D) 27 6 0.0035
32 (P, V, X, F, D, A) 28 7 0.0208
33 (V, P, F, A, X, D) 29 7 0.0035
34 (V, F, A, X, P, D) 30 6 0.0052
35 (V, X, P, F, D, A) 31 7 0.0156
36 (P, V, F, A, D, X) 32 7 0.0139
37 (V, P, A, F, D, X) 33 7 0.0052
38 (V, P, F, X, A, D) 34 8 0.0035
39 (A, V, F, P, D, X) 35 6 0.0046
40 (V, F, A, P, X, D) 36 7 0.0026
41 (V, P, X, F, D, A) 37 8 0.0052
42 (P, V, F, X, D, A) 37 8 0.0139
43 (V, A, F, P, D, X) 38 7 0.0035
44 (V, P, F, A, D, X) 39 8 0.0035
45 (V, F, P, A, X, D) 40 8 0.0026
46 (V, F, X, P, A, D) 41 8 0.0078
47 (A, V, F, D, X, P) 42 6 0.0046
48 (P, V, F, D, A, X) 43 8 0.0139
49 (V, A, F, D, X, P) 44 7 0.0035
50 (V, P, F, X, D, A) 45 9 0.0035
51 (V, F, A, P, D, X) 46 8 0.0026
52 (V, F, P, X, A, D) 46 9 0.0026
53 (A, V, F, D, P, X) 47 7 0.0046
54 (P, V, F, D, X, A) 48 9 0.0139
55 (V, P, F, D, A, X) 49 9 0.0035
56 (V, F, X, P, D, A) 50 9 0.0078
57 (V, F, P, A, D, X) 51 9 0.0026
58 (V, A, F, D, P, X) 52 8 0.0035
59 (V, F, A, D, X, P) 53 8 0.0026
60 (V, P, F, D, X, A) 54 10 0.0035
61 (V, F, P, X, D, A) 55 10 0.0026
62 (V, F, A, D, P, X) 56 9 0.0026
63 (V, F, P, D, A, X) 57 10 0.0026
64 (V, F, D, A, X, P) 58 9 0.0026
65 (V, F, P, D, X, A) 59 11 0.0026
66 (V, F, D, A, P, X) 60 10 0.0026
67 (V, F, D, X, P, A) 61 11 0.0052
68 (V, F, D, P, A, X) 61 11 0.0026
69 (V, F, D, P, X, A) 62 12 0.0026

The ranks for \(h \in \mathcal{H}\) lead directly to a new poset \((\mathcal{H},\leq_{\mathbb{D}})\). It is an extension of and fully compatible with \((\mathcal{H},\leq_{H})\) as developed in On the Desirability of Possible Histories.

The resulting Hasse Diagram would be too large to reproduce here. Histories having identical rank are incomparable to each other within the poset. The refined poset \((\mathcal{H},\leq_{\mathbb{D}})\) is much closer to a total order on \(\mathcal{H}\), as indicated by the relatively few histories having duplicate ranks.

Towards a Total Order on all Possible CVD Histories (\(\mathcal{H}\))

The remaining incomparable histories are the direct result of the incomparable \(d\) in \((\mathbb{D},\leq_{\mathbb{D}})\), corresponding to the branches in the Desiderata Hasse Diagram above. Achieving a total order on \(\mathbb{D}\) would require determining a preference for one of each of the following:

Outcome A Outcome B Explanation
\(\mathbf{F} \prec \mathbf{X}\) \(\mathbf{V} \prec \mathbf{P}\) fix ready before exploit publication or vendor awareness before public awareness
\(\mathbf{P} \prec \mathbf{X}\) \(\mathbf{X} \prec \mathbf{A}\) public awareness before exploit publication or exploit publication before attacks
\(\mathbf{P} \prec \mathbf{A}\) \(\mathbf{V} \prec \mathbf{X}\) public awareness before attacks or vendor awareness before exploit publication

In other words, would you rather that Outcome A or Outcome B for each of the above? Recognizing that readers may have diverse opinions on all three items, we leave further consideration of the answers to these as future work.

This is just one example of how poset refinements might be used to order \(\mathcal{H}\). Different posets on \(\mathbb{D}\) would lead to different posets on \(\mathcal{H}\). For example, one might construct a different poset if certain \(d\) were considered to have much higher financial value when achieved than others.