search

theupdateframework / specification

The Update Framework specification
https://theupdateframework.github.io/specification/
Other
368 stars 54 forks source link

Confirm terminating roles logic from spec #168

Open tedbow opened 3 years ago

tedbow commented 3 years ago

In https://github.com/php-tuf/php-tuf we are making sure we have the logic correct around terminating delegations. As we have updated our implementation of the spec from v1.0.9(the release when we started) to the most recent releases we have notice there has been some changes to wording in this area of the spec.

To make sure we get the logic correct for terminating delegations I have created this simple example to make sure our assumptions are correct(actually we don't all have same assumptions these are mine) TUF delegation assumptions

Constraints

term = terminating delegation non-term = non terminating delegation Priority: The roles in each level are ordered from left to right in the order they would appear under [delegations][roles] All roles have paths = [‘assets/*’](just to provide matches for every role only focus on terminating logic now) Target being searched for = 'assets/always-match.txt’

Expected outcome

Expected role evaluation: Targets -> A > B > C > D

Am I correct?

trishankatdatadog commented 3 years ago

Thanks, Ted!

There's still one point of confusion here: the term/non-term labels should apply to the edges, not the nodes.

However, I think your interpretation is correct, as per the spec and the Diplomat paper.

From simulating the code on this graph in my head, I think my tuf-on-a-plane code would correctly not explore E, but would incorrectly explore F.

Any disagreements, @mnm678 and @JustinCappos?

trishankatdatadog commented 3 years ago

IOW: once you see a terminating delegation anywhere in the graph, the rest of the graph is completely pruned.

trishankatdatadog commented 3 years ago

There are two ways of interpreting terminating delegations: global vs local pruning. Only one of them is the intended/correct interpretation.

joshuagl commented 3 years ago

I'm not one of the original authors, but my interpretation of the spec and the Diplomat paper matches the expected outcome suggested here.

JustinCappos commented 3 years ago

I agree this interpretation is correct.

I'm also curious what everyone thinks should happen if there is a threshold delegation to A and F as well. Certainly that is worth a test case...

mnm678 commented 3 years ago

From simulating the code on this graph in my head, I think my tuf-on-a-plane code would correctly not explore E, but would incorrectly explore F.

I read it the same. The loop will need to propagate that there was a terminating delegation up to previous iterations in order to correctly not explore F. It looks like the reference implementation handles this correctly by breaking out of the for loop here (I didn't check the new client).

I'm also curious what everyone thinks should happen if there is a threshold delegation to A and F as well. Certainly that is worth a test case...

In that case, I'd argue that F should be explored (and required for the threshold). But I don't think this behavior is well-defined in the spec.

trishankatdatadog commented 3 years ago

I'm also curious what everyone thinks should happen if there is a threshold delegation to A and F as well. Certainly that is worth a test case...

By threshold delegation, you mean multirole delegation? Agree with @mnm678 that if min_roles_in_agreement >=1 (which I assume is always the case), then, yes, it should backtrack from A and check F, despite any terminating delegation from A. Agree that the spec is underspecified with respect to TAP 3. Also need to think about whether there is any contradiction between terminating delegations and TAP 3.

mnm678 commented 3 years ago

The spec states that

A terminating delegation for a package causes any further statements about a package that are not made by the delegated party or its descendants to be ignored.

Which by a literal reading does contradict TAP 3. I don't think TAP 3 is supported by 1.0 of the specification, but this is something we should figure out before adding it.

trishankatdatadog commented 3 years ago

Which by a literal reading does contradict TAP 3. I don't think TAP 3 is supported by 1.0 of the specification, but this is something we should figure out before adding it.

In particular, I'd like to see concrete pseudocode added to the spec. Otherwise, readers are likely to get confused.

tedbow commented 3 years ago

Thanks everyone for the confirmation. I working on fixing our implementation increasing our test coverage for different cases here https://github.com/php-tuf/php-tuf/pull/216

If anyone is interested we test our client implementation by creating test fixtures with a FixtureBuilder that uses the Python server implementation. For example here is 1 for that PR that creates the above test case https://github.com/php-tuf/php-tuf/blob/tedbow-fix_terminating_2/fixtures/TUFTestFixtureTerminatingDelegation/__init__.py (BTW @phenaproxima and myself are learning python to create these test fixtures so don't expect great python code 😁)

We then make test case for a given test fixture and given target, whether it should be found and which metadata files the client should retreive/evaluate to determine this. Like this case for role "F" in the example not finding a target because of terminating delegation in "B" https://github.com/php-tuf/php-tuf/blob/tedbow-fix_terminating_2/tests/Client/UpdaterTest.php#L653