Skip to content
Explanation

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}\).

\[ f_h = \prod_{i=0}^{5} p(\sigma_{i+1}|h_i) \]

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\), 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\). 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.

Scoring a Case That Is Still in Progress

The scores above are for complete histories, in which all six events have happened. A real case is almost always still in progress: some of its events have not happened yet, so its sequence is a prefix of a history, not a whole one. ADR-0182 scores such a case through the histories it can still become.

A history's score is the sum of \(1 - f_d\) over the twelve desiderata \(d\) the history meets. A rare desideratum adds nearly 1, and a common one adds little. This differs from the \(-log(f_d)\) skill proxy used for the ranking above: both reward a rare desideratum more than a common one, but \(1 - f_d\) adds at most 1 for each desideratum. The most skillful history, \((\mathbf{V}, \mathbf{F}, \mathbf{D}, \mathbf{P}, \mathbf{X}, \mathbf{A})\), meets all twelve and scores about 7.37. A history that meets none scores 0.

Scoring a Prefix Through Its Completions

A completion of a prefix is a valid complete history that starts with that prefix. Every valid prefix has at least one completion. Each completion \(h\) is weighted by the probability that the random walk behind \(f_h\) reaches \(h\) from where the case stands. That weight is \(f_h\) divided by the probability of the prefix, so the weights of a prefix's completions sum to 1. The case then reports three scores:

  • The expected score is the weighted mean of the completions' scores. It is what the case would score if every remaining event happened by chance.
  • The best score is the highest score of any completion. It is the most the case can still reach.
  • The worst score is the lowest score of any completion. It is the least the case can still fall to.

A complete history is its own only completion, so its expected, best and worst scores are all equal to its score.

A case in which the vendor has a fix ready

The vendor is aware and a fix is ready, but nothing else has happened: the prefix is \((\mathbf{V}, \mathbf{F})\). It has 18 completions. Its worst score is about 3.43, its best about 7.37, and its expected score about 5.30. Once the fix is also deployed, \((\mathbf{V}, \mathbf{F}, \mathbf{D})\) has 5 completions, and the range narrows to 6.04 through 7.37, with an expected score of 6.76.

The range between the worst and the best score shows how much the outcome of the case is still open. It shrinks as events happen, and it closes when the history is complete. The expected score is a forecast under the chance baseline, not a prediction of what the participants will do.

A sequence that is not a valid prefix gets no score. It is refused, with the reason the prefix check gives, such as a fix ready before the vendor is aware. A case whose ledger has holes never reaches the scorer: the event history refuses it, so a scored sequence is incomplete only because its remaining events have not happened yet. A multi-party case is scored once for each vendor, from that vendor's own sequence, and Benchmarking MPCVD describes how the case summarizes those scores.

The desiderata from the process models are scored in the same way, in the scope of each vendor. A vendor's score has two parts. The end part holds the original twelve desiderata and the report-handling desiderata. The embargo part holds the embargo desiderata and \(\evF_i \prec \evExOwn\). The case gets no score for a group of desiderata across its vendors. The multi-party desiderata are not in a vendor's score: \(\evF_i \prec \evP\) is already the vendor's \(\evF \prec \evP\), and \(\evV_i \prec \evF_j\) is not used.

The walk for these desiderata starts at the state of the case now, not at the start of the model. Each walk uses one vendor and the events of the case, so the scorer never combines the sequences of two vendors. A group of equivalent desiderata, such as \(\evE \prec \evP\), \(\evE \prec \evX\) and \(\evE \prec \evA\), counts only once. A desideratum whose scope the case never enters counts as met: a report that is never validated does not lose the desiderata for valid reports. When a score adds up more than one walk, its best and worst scores are bounds, because the walks share the events of the case.