Support for flexible filtering / attribution functionality

[csharrison]

In the latest f2f meeting in Paris, we had an action item to outline what a more flexible solution for ad-tech defined matching / attribution functionality could look like. This ensures business logic to sits with the ad-tech, and has the benefit of allowing innovation without changes requiring changes to our specification. On the other hand, full flexibility comes with downsides in terms of risk of side channel attacks (#153), system health issues, etc which come from executing arbitrary code from untrusted parties.

A natural approach here would be to spin up some Javascript environment to do this, which comes with many benefits (standardized, implemented in all browser engines already, etc), but has a few major drawbacks (it is Turing complete, potentially too heavyweight, large attack surface, etc). In this issue I wanted to pitch an intermediate option in between a fully declarative approach and a fully turing complete approach using CEL – a non-turing complete, minimal expression language which was designed to operate on untrusted expressions.

Kudos to @apasel422 for the original suggestion and overall help exploring this option. cc @bmayd , @eriktaubeneck , and @ohpauleez who were interested in this approach.

Straw API overview

We can allow callers to specify two CEL functions, match and assignCredit in measureConversion:

measureConversion({
  // Generalization of https://w3c.github.io/ppa/#logic-matching
  // Returns a subset of impressions.
  match: "<some CEL expr>",

  // Generalization of https://w3c.github.io/ppa/#s-logic 4.4.1.6
  // Assigns credit (in [0,1]) to the list of matching impressions, so the
  // final histogram value will be proportional to credit.
  // Returns a map of {<impression id>: <double>}.
  assignCredit: "<some CEL expr>",
  …
});

Both expressions are invoked with the following CEL environment variables:

• impressions: A list of records with the following fields:
  • id: string: An opaque implementation-defined identifier for this impression
  • age: duration: The duration since the impression was registered
  • userData: dyn: An arbitrary value provided by the impression registrar at the time it was registered, effectively one of the JSON types. In practice, this will likely be a map<string, dyn> so that multiple pieces of metadata can be associated with the impression.

For ergonomics, impressions will be pre-sorted by age, ascending.

Examples

The CEL extensions used in these examples are:

• Bindings (not strictly required, but greatly reduces code size)
• Lists
• Math
• Two-Var Comprehensions

We also expose new built-in functions ppa.sum and ppa.pow for list summation and exponentiation, though they are good candidates to add to the math extension.

Last-touch with clicks and views

This implements #42 (comment). Essentially, we:

• Filter clicks and views via possibly different lookback windows (and possibly dynamic based on conversion time)
• Give full credit to the last click if there are any clicks, otherwise give full credit to the last view

The following assume that clicks and views are saved via something like saveImpression({userData: {click: <bool>}, ...});.

match:

cel.bind(click,
  impressions.filter(i, i.userData.click && i.age <= duration('120h')),
  size(click) > 0
    ? click
    : impressions.filter(i, !i.userData.click && i.age <= duration('24h'))
).map(i, i.id)

assignCredit:

 {impressions[0].id: 1.0}

MTA with exponential decay

Requirements:

• Perform arbitrary filtering (not pictured)
• Select the n-last events
• Score the events with an exponential decay model (e.g. w/ half-life 7 days [168 hours])
• Allocate credit proportional to the score

assignCredit:

cel.bind(lastN,
  impressions.slice(0, math.least(3, size(impressions))), cel.bind(cp,
  lastN.transformMapEntry(_, i,
    {i.id: ppa.pow(2.0, double(i.age.getHours()) / -168.0)}),
cel.bind(total,
  ppa.sum(cp.transformList(_, v, v)),
  cp.transformMap(_, f, f / total))))

MTA with array-based credit

Requirements:

• Perform arbitrary filtering (not pictured)
• Select the n-last events
• Assign the events credit based on their position in the input list
• Normalize the credit

assignCredit:

cel.bind(credit, [8.0, 6.0, 2.0],
cel.bind(lastN,
  impressions.slice(0,
    math.least(size(credit), size(impressions))),
cel.bind(total,
  ppa.sum(credit.slice(0, size(lastN))),
  lastN.transformMapEntry(i, v, {v.id: credit[i] / total}))))

[apasel422]

While outputting a credit map is elegant in some ways, it has a few drawbacks:

1. Many expressions will have to perform normalization themselves, increasing expression length and complexity.
2. The PPA host implementation must still decide how to handle the situation in which the chosen credit assignment does not apply evenly to the value. For example, if value = 3, and the credit assignment indicates that each of four impressions should be given 0.25 credit, the implementation must decide how to discretize 3/4.

Just like the CEL expression generalizes matchValue, we could generalize the credit-assignment step as a “sparse-histogram output step.” Most of the original post in this issue remains the same, but we replace the assignCredit step with a computeSparseHistogram step that, in addition to the impressions variable above, also receives a value: uint variable, and evaluates to a map from uint histogram indexes to uint values.

On evaluation, the map will be validated to ensure that the sum of all values is less than or equal to value, and that each histogram index is less than the histogramSize.

To help with this, we will supply a ppa.histogramFromCredit(map(uint, double), uint) -> map(uint, uint) function that accepts the credit assignments and value, and returns the normalized map. Callers will be expected to pass the value variable as the second argument, though they do not have to.

Altogether, this means that histogramIndex from the impression need not be a first-class part of the API, and can instead be embedded in the userData. We would presumably keep it, and even expose it just like impression.age, so that a single impression could easily be used with both the declarative API and CEL. The only complexity is that the expression must ensure that it does not attempt to output duplicate histogram indexes, as CEL prohibits duplicate map keys.

All of this is most easily understood with some examples. Here are the models from the original post rewritten in this format, assuming that the corresponding impressions have been stored with a user-data field called campaign, containing the desired histogram index.

MTA with exponential decay

cel.bind(lastN,
  impressions.transformList(k, i, k < 3, i),
  ppa.histogramFromCredit(
    lastN.map(i, uint(i.user_data.campaign)).distinct()
      .transformMapEntry(_, campaign, {campaign:
        ppa.sum(
          lastN.transformList(_, i, i.user_data.campaign == campaign,
            ppa.pow(2.0, double(i.age.getHours()) / -168.0)))}),
    value))

Example instantiation:

{
  "impressions": [
    { "age": "505h", "userData": { "campaign": 11 } },
    { "age": "504h", "userData": { "campaign": 13 } },
    { "age": "504h", "userData": { "campaign": 13 } },
    { "age": "168h", "userData": { "campaign": 14 } }
  ],
  "value": 12,
  "expectedSparseHistogram": [
    { "index": 13, "value": 4 },
    { "index": 14, "value": 8 }
  ]
}

MTA with array-based credit

cel.bind(CREDIT, [8.0, 6.0, 2.0],
cel.bind(lastN,
  impressions.transformList(k, i, k < CREDIT.size(), i),
  ppa.histogramFromCredit(
    lastN.map(i, uint(i.user_data.campaign)).distinct()
      .transformMapEntry(_, campaign, {campaign:
        ppa.sum(lastN.transformList(k, i, i.user_data.campaign == campaign,
          CREDIT[k]))}),
    value)))

Example instantiation:

{
  "impressions": [
    { "age": "4h", "userData": { "campaign": 11 } },
    { "age": "3h", "userData": { "campaign": 13 } },
    { "age": "2h", "userData": { "campaign": 13 } },
    { "age": "1h", "userData": { "campaign": 14 } }
  ],
  "value": 8,
  "expectedSparseHistogram": [
    { "index": 13, "value": 4 },
    { "index": 14, "value": 4 }
  ]
}

[martinthomson]

I'm not following your second example. That's possibly because my brain doesn't do CEL (these examples are not doing much to improve my opinion of the language), but more because I can't connect two values of 4 with the input CREDIT array; or the CREDIT array with a value of 8 (the sum of the array is 16).

[apasel422]

I can't connect two values of 4 with the input CREDIT array; or the CREDIT array with a value of 8 (the sum of the array is 16).

We have 8 / 16 * 8 = 4 (the second 8 being the value, effectively what the credit array is being multiplied by after normalization) for campaign=14. campaign=13 appears twice: the 2h-old impression corresponds to 6 / 16 * 8 = 3; the 2h old one corresponds to 2 / 16 * 8 = 1; their sum is 4.

[martinthomson]

Oh, I see. I would have thought that you would have sum(CREDIT) == value, rather than scale it that way. You managed to avoid floating point answers here, but this seems suboptimal. Is it histogramFromCredit that applies the *value / sum(CREDIT) scaling?

[apasel422]

I would have thought that you would have sum(CREDIT) == value, rather than scale it that way.

Scaling it against value means that the CEL expression needn't be coordinated with the value itself, potentially allowing reuse in more circumstances. The expression could of course choose to ignore value entirely.

You managed to avoid floating point answers here, but this seems suboptimal.

Yes, we do need to figure out the best way to divide the integer value given floating-point credits.

Is it histogramFromCredit that applies the *value / sum(CREDIT) scaling?

Yes, it does the scaling, including the float-integer conversion.

[apasel422]

CEL has a variety of drawbacks compared to JavaScript:

1. Incorporating it into the web platform would be a significant undertaking in terms of specification/standardization and integration into existing browsers.
2. It is likely a novel language and execution paradigm for many developers, and lacks the same level of tooling and support across the industry.
3. Its standard library is deliberately minimal, meaning that the burden of additional functionality would be on the Attribution API implementation, rather than the existing browser.
4. It is deliberately not Turing-complete, making it difficult or impossible to implement certain algorithms.

Therefore, we could consider using JavaScript worklets as optional parts of both matching and histogram generation instead. The overall API and semantics of the JavaScript version match the previously described CEL version above.

Spec modifications

The existing API is modified as follows:

partial dictionary AttributionImpressionOptions {
  // This field, if present, will be made available during worklet-based matching
  // and histogram-generation.
  // This field exists in addition to matchValue so that matchValue, with its
  // well-known format, can still be used with the declarative matching API for
  // simple cases that do not require worklets.
  any attributionData;
};

enum AttributionLogic {
  "last-n-touch", // unchanged from the existing API
  "worklet",
};

enum AttributionAdditionalMatchMode {
  "none",
  "worklet",
};

partial dictionary AttributionConversionOptions {
  USVString workletUrl;

  // This field exists as an optimization: A single workletUrl can be fetched and
  // used for matching, histogram-generation, or both, and the measureConversion
  // caller can decide whether to use that script for either matching, histogram-
  // generation, or both, rather than requiring the API implementation to first
  // load the script to determine whether it wants to be used for matching in
  // addition to histogram-generation, which would require spinning up a new
  // isolated environment for no other purpose.
  AttributionAdditionalMatchMode additionalMatchMode = "none";
};

When saveImpression stores an impression, the attributionData, if any, is stored along with it, as matchValue is today. Implementations may impose limitations on the types and size of data that can be stored; it may make sense to limit this in the spec itself to the JSON types, especially for ease of use with the HTTP API for Save-Impression.

For measureConversion, it is a validation error to specify either logic or additionalMatchMode as worklet without also providing a workletUrl. The workletUrl must be fetched as a script workletScript during the validation process, i.e. before any branching logic associated with the attribution process itself, in order to avoid creating a side-channel through whether or not the script is fetched at all.

We modify the "do attribution and fill a histogram" algorithm as follows:

Between Steps 4.1 and 4.2 of we add the following step:

If additionalMatchMode is worklet, and impressions is not empty:

1. Let ctx be a new AttributionMatchContext whose impressions field is initialized to impressions.
2. Let matchedIndices be the result of executing workletScript in an isolated environment by calling the AttributionMatcher.matchImpressions method on the global object, passing ctx.
3. If that call resulted in an exception or a return value in an unexpected format, set matchedIndices to the empty list.
4. Let matchedImpressions be a new list.
5. For each index of impressions' indices:
   1. If matchedIndices contains index, append impressions[index] to matchedImpressions.
      Note: We deliberately do not throw an error if matchedIndices contains invalid or duplicate indices, because doing so would allow the script to exfiltrate data back to the measureConversion caller.
6. Set impressions to matchedImpressions.

Note: We unconditionally perform the common matching logic, even if the worklet-level matching is also going to be applied. This is both an optimization and an ergonomics benefit: It is an optimization, because we don't even need to execute workletScript in an isolated environment at all if the common matching logic outputs the empty set, and because it reduces the number of impressions that need to be translated for exposure to the script. It is an ergonomics benefit because it means that the majority of the common matching logic can remain declarative (lookback, impression sites/callers, conversion sites/callers) for simplicity.

// This is an interface in order to make it possible to add methods in the future.
interface Impression {
  readonly attribute double ageInHours;
  readonly attribute any attributionData;
  readonly attribute unsigned long matchValue;
};

dictionary AttributionMatchContext {
  readonly sequence<Impression> impressions;
};

interface AttributionMatcher {
  // Returns the indices of impressions in `ctx.impressions` to match.
  sequence<unsigned long> matchImpressions(AttributionMatchContext ctx);
};

We modify Step 6 to account for the case in which logic is worklet:

1. Let ctx be a new AttributionHistogramContext whose impressions field is initialized to impressions, whose value field is initialized to options' value, and whose histogramSize field is initialized to options' histogram size.
2. Sort ctx.impressions by ageInHours, ascending.
   Note: This property ensures that neither the output ordering of the matching step, nor the underlying ordering of the impressions in storage, is revealed to the histogram-generation script, and may be useful to the script in general.
3. Let histogram be the result of executing workletScript in an isolated environment by calling the AttributionHistogramGenerator.generateHistogram method on the global object, passing ctx.
4. If that call resulted in an exception or a return value in an unexpected format, or if the returned histogram is not valid with respect to options' histogram size or value, return the result of invoking create an all-zero histogram with options' histogram size.
5. Otherwise, return histogram.

dictionary AttributionHistogramContext {
  // Guaranteed to be sorted by ageInHours, ascending.
  readonly sequence<Impression> impressions;
  readonly unsigned long value;
  readonly unsigned long histogramSize;
};

interface SparseHistogram {
  // Keys are histogram indices, values are histogram values.
  maplike<unsigned long, unsigned long>;
};

interface AttributionHistogramGenerator {
  SparseHistogram generateHistogram(AttributionHistogramContext ctx);
};

Isolated Environments

The "isolated environments" in which the scripts are executed must have the following properties:

1. They must not be able to access the network, persistent storage, or the web-platform in general. This is to ensure that data from the API cannot be exfiltrated from the system to subvert the API's privacy model.
2. The matching and histogram-generation operations must be run in isolation from each other (i.e. with no state shared between the two JS environments). This is to ensure that any matched impressions are accounted for in privacy budgeting and that no unmatched impression is used in the histogram-generation process. The matching step is invoked up to once per epoch; those invocations must be isolated from each other for the same reason.
3. They must not have access to high-resolution timers. There's really no reason to expose timers at all to these scripts, but the exclusion of high-resolution ones is specifically meant to mitigate side-channel leakage.
4. They should be limited in their execution time, and possibly also in their memory consumption, subject to implementation-specific considerations, for system-health reasons and to mitigate the ability of one API user to DOS another by taking excessive execution time (e.g. while (true) {}). In the case in which an implementation terminates either operation early, it must still produce an all-zero histogram.
5. They should have some kind of guaranteed execution time or performance characteristics in order to prevent the measureConversion caller (or other non-worklet JS code) from inferring information based on the operation of the worklet JS code (e.g. how many matching impressions there were). This is already a concern for the declarative-only API, but it is exacerbated by the arbitrary nature of the user-defined worklet code. See related discussion in #188.

Performance Considerations

Fetching the script and creating these isolated environments, once per epoch for the matching operation and once total for the histogram-generation operation, is likely to be more expensive compared to the operation of the declarative API.

Notes

1. Concerns about the additional latency incurred by fetching the worklet URL can be mitigated by data URLs / blobs and/or HTTP caching.
2. While this proposal does not incorporate WASM, it seems reasonable to support WASM as an environment for histogram-generation in particular, if we discover use-cases that are more performant under it. That could be added in the future backwards-compatibly.
3. We may want to consider a security policy regarding exactly where the scripts can be fetched from. At the very least, if they are being fetched from a remote URL, they must be from potentially trustworthy origins with the proper Content-Type and subject to the usual CORS requirements.
4. We deliberately do not expose the absolute time at which an impression was stored in order to help reduce logic bugs originating from skew between the local clock and the API user's remote clock, but this is still subject to skew between the local clock at the time of saveImpression versus measureConversion. If the API user really wants the absolute time, it could store its notion of that time in the impression's attributionData field. But we could reconsider this decision.
5. We deliberately do not expose any kind of internal ID associated with the impressions to either script, as the histogram-generation script in particular could exfiltrate that data in its output and use it for user fingerprinting or, depending on the known characteristics of the implementation, to determine the total number of impressions stored by the API (i.e. those not matching either the common matching logic or the worklet matching logic). Neither script should need any kind of API-provided ID for an impression in its internal operation, as it can use either the impression's index in the original sequence, or its object identity (e.g. with a Map).
6. Related to fingerprinting, the exact characteristics of the JS environment (e.g. which global functions are available) are likewise capable of being exfiltrated by the histogram-generation script, but this is not considered a new surface with novel information, as the measureConversion caller can already do this for its JS environment, which should be approximately 1:1.
7. We may want to provide some helper functions to the histogram-generation script in particular, e.g. the fair-credit assignment from #225, though the script is capable of reproducing that itself.

[martinthomson]

General sense from 2025-08-12(ish) meeting was that this was worth continuing to think about - lots of things point in the direction of having something more flexible - but not just yet.