Inconsistency: session and dynamic DNR rules are applied with differing priorities across browsers

[eepskamp]

Per Mozilla's PR here [https://phabricator.services.mozilla.com/D156233], session and dynamic rulesets are applied at a higher priority than the static rulesets defined in the manifest.

• When multiple rules match, the order between rules are defined as follows:
• • Ruleset precedence: session > dynamic > static (order from manifest.json).
• • Rules in ruleset precedence: ordered by rule.id, lowest (numeric) ID first.
• • Across all rules+rulesets: highest rule.priority (default 1) first, action precedence if rule priority are the same.

Safari does not give session and dynamic rulesets higher priority when determining which rule to apply.

[dotproto]

AI for Chrome from today's sync: explore the feasibility of changing the current behavior in Chrome to allow session, dynamic, and static rules to interleave priority.

[Rob--W]

Note that Chrome has only documented rule.priority as a way to change the rule precedence.
I have documented the intended behavior after evaluating Chrome's documentation and implementation, currently still in a review stage (see comment in ExtensionDNR.sys.mjs) at https://phabricator.services.mozilla.com/D156233?id=628275#C5559958NL10.

As noted there (and pasted here by Timothy), the precedence is not only affected by rule.priority, but also rule.id, ruleset index (and static vs dynamic vs session rule). These aspects are not documented but they are part of Chrome's implementation (see RequestAction::operator<, C++ header file (request_action.h) and C++ source file (request_action.cc)).

The elaborate definition of precedence is needed to unambiguously arrive at an equivalent decision when multiple rules with the same priority and action matches. This is relevant in redirect and modifyHeaders actions: there are multiple potential ways of executing these actions, and the order of doing so needs to be well-defined in order to maintain a stable behavior across different browsers, but also different versions of the same browser.

The relevant details of the disambiguation/conflict resolution behavior are not documented in Chrome's DNR API docs. The only documented precedence factors are priority and action precedence. To uniquely identify a rule, a stable rule identifier such as rule.id is needed. While Chrome's documentation does call out the need for the ID to be mandatory, it does not state whether the ID should be globally unique, or unique within a ruleset. Although not explicitly documented as such, the fact that the MatchedRule type is documented to consist of the ruleset ID and rule ID may be a sign that the rule IDs are only guaranteed to be unique within a ruleset.

In short:

• All rules must be comparable (mathematically: a total order).
• rule.priority and rule.action.type are the documented ways to affect the order.
• rule.id is an undocumented ways to affect the order, which is relevant when there are multiple matching rules with the same priority and action precedence.
• rule.id seems to be unique within a ruleset, and there is nothing that says that it is unique across all rulesets. Therefore an identifier for the ruleset (index of static ruleset in array vs dynamic rules vs static rules) are used by Chrome to uniquely identify a rule.

[dotproto]

My last comment was based on a misunderstanding on my part. I thought that Chrome applied rules first by the type of rule, then by the priority of the rule. Chrome actually applies rules in priority order and only falls back to the type of rule for tie-breaking purposes. Thanks for helping clarify Chrome's behavior here, @Rob--W.

We're supportive of clearly defining and aligning on a common rule precedence algorithm. Also, we're in the process of updating our declarativeNetRequest API documentation; I expect that as part of this work we will document Chrome's rule precedence.

[Rob--W]

I made two mistakes before in the interpretation of Chrome's order of precedence:

• Ruleset precedence: session < dynamic < static (order from manifest.json).
  • I previously swapped < and >.
  • I.e. session rules can only override dynamic rules if they have a higher priority, and the last static ruleset in the list has the highest precedence if all else is equal.
• Rules in ruleset precedence: ordered by rule.id, highest (numeric) ID first.
  • I previously wrote that the lowest rule.id takes precedence.
  • Note that rule.id cannot be relied upon for ordering in Chrome, see below.

The elaborate definition of precedence is needed to unambiguously arrive at an equivalent decision when multiple rules with the same priority and action matches. This is relevant in redirect and modifyHeaders actions: there are multiple potential ways of executing these actions, and the order of doing so needs to be well-defined in order to maintain a stable behavior across different browsers, but also different versions of the same browser.

I have examined the behavior again, and it turns out that the behavior is unstable when there are multiple same-priority actions of the same action type.
While there is indeed a defined total order when two need to be compared (e.g. when urlFilter and regexFilter matches are merged, and when matches from separate rulesets are merged), the optimized implementations for urlFilter and regexFilter lookups only account for rule.priority (and rule.action) (not rule.id). As the underlying optimization is not guaranteed to be stable, the result is that extensions with multiple same-priority redirect (or modifyHeaders) actions can behave unpredictably across different browser versions. The only way to avoid that is to specify rule.priority.

Relevant sources:

• RulesetMatcher::GetBeforeRequestAction looks up the matching urlFilter and regexFilter rule, and merges them (using the total ordering to pick the highest match among regexFilter or urlFilter rules, by GetMaxPriorityAction)
  • Matches for regexFilter rules are sorted by priority (highest first) and then the first result is picked (source).
  • Matches for urlFilter rules are iterated over and the highest priority rule is chosen (source).
• The above logic is repeated for each ruleset, and the result is merged with the total ordering again (source).

[Rob--W]

For context, I assumed that the order to be session > dynamic > static rules, because that seems to be the most sensible design to me. And indeed, that expected order was historically present in Chrome until a patch broke that.

• At first, Chrome only had one static ruleset.
• Then there were multiple static rulesets (https://crbug.com/754526).
• Dynamic rules were introduced later, to allow ad blocker extensions to override static rules.
• Up to this point, there was a defined order between rulesets; dynamic rulesets took precedence over static rulesets.
• Then rule.priority was introduced in https://crbug.com/1026733, and the defined order between dynamic and static rulesets was removed: https://chromium.googlesource.com/chromium/src.git/+/388330c80eb76ca4676175d615a910d990e00fa3%5E%21/#F9
  • Consequently, when "priority" was not specified, static rules took precedence over dynamic rules, which is an (unnoticed?) regression compared to before.
• (and session rules were introduced even later, to support in-memory, non-persistent rules.)
• At this point, the only way to patch the action of a static rule is to introduce a higher-priority rule. The problem with this is that it could potentially interfere with other "block" rules (usually block > redirect, but "priority" takes precedence).
• The "patch a static rule" use case is now covered by the ability to disable individual static rules (Declarative Net Request proposal: disable individual static rules #162).

[Rob--W]

I have updated the MDN documentation in mdn/content#26793 to remove the mention of a guaranteed rule evaluation order in relation to rulesets and rule IDs, for now.

@xeenon @oliverdunk I would like to get to a resolution here - how do we resolve this inconsistency?

This inconsistency mainly matters for a limited scenario:

• same-priority rules
• with action types that have parameters (i.e. "redirect" and "modifyHeaders")
• and have overlapping conditions

The current inconsistency forces extension developers to try and come up with a "priority" to establish a rule order. But the downside to that is that the rule priority is global and takes precedence over the precedence implies by the action type. There is currently no standard & guaranteed way for extensions to specify an explicit order between multiple actions. Having an established way would make the DNR API more useful.

Currently, for same-priority actions of the same action type, the resolution is unspecified, undocumented and implementation-dependent:

• Tie-breaking rules between different rulesets:
  • Chrome: static rules (last in manifest.json with highest precedence) > dynamic rules > static rules.
  • Safari: like Chrome? (Timothy's remark in the 2022-09-29 meeting suggests that)
  • Firefox: session > dynamic > static (last in manifest.json has lowest precedence).
    • Firefox's behavior was Chrome's behavior in the past (for Chrome's history, see my previous comment).
    • From the API design point of view, this behavior makes most sense, as it would allow extensions to use session rules to "temporarily" override a rule from a different ruleset without being forced to resort to carefully choosing rule.priority (which may not always be possible).
• Tie-breaking of rules within the same ruleset, using rule.id (which is unique within a ruleset, so this would always result in a defined order):
  • Chrome: Inconsistent. While the implementation defines an order where the higher rule IDs have a higher precedence, the matching algorithm itself does not account for this and the resulting behavior is inconsistent in practice (end of this comment for details).
  • Safari: I don't know.
  • Firefox: rule.id, lowest rule ID has the highest precedence.
    • I wouldn't mind changing this to "highest rule ID has the highest precedence, if this were to consistently be followed across browsers, because this would be more consistent with the meaning of "rule priority" (=higher value implies higher priority).