Fake Report で使われている任意の組み合わせをランダムに選択する仕組み

はじめに

京都研究所のTechlabに所属するエンジニアの I です。 ChromeのPrivacy Sandboxには広告クリックまたは広告視聴が、広告主サイトでの購入などのコンバージョンにつながったタイミングを測定するAttribution Reporting API が含まれています。このAPIのEvent-Levelレポートの機能は、プライバシーを保護するため、ノイズとして偽レポートを通知することがあります。

この偽レポートはランダムに数値を選ぶことから始まり、ユーザが設定した条件に基づいてランダムな組み合わせを生成します。組合せをどのように選ぶのかという点で Chromiumのコードを調べてみました。この記事では、そこで使われている計算方法や考えを具体的な数字を用いて説明します。

Fake Report

冒頭で紹介した偽レポート(Fake Report) というものを改めて説明すると、実際のユーザ行動のデータをレポート送信に使用せず、ブラウザの計算に基づいてダミーの内容でレポートを送信する機能、という感じになっています。

そのあたりは、大まかには、以下の手順でなされます。

レポートの設定で「view/click/その他」を設定して広告を表示する
設定されたレポートの設定に従い、ブラウザはレポートの送信パターンの数を組み合わせとして数え上げる
（補足：基本的にはレポートは偽レポートの対象にはならずに、設定どおりにレポートされる）
偽レポートの対象になった場合、レポートの組合せ数、例えば、3や20や2925という数字をブラウザはインデックスとみなしランダムに1つ選択する
ランダムに選択されたインデックスで対応するレポート通知の組み合わせの該当するパターンを決定し、決定した設定でダミーレポートを送信する

この４で、任意の組み合わせの中からランダムに通知の内容を選ぶのですが、任意の部分を決めるのは広告の計測の設定が元になっています。広告を計測する側の設定で仮に10パターンの区別で計測すると宣言したならば、この10パターンに1を加えた11パターンの中からランダムに送信パターンを選択するような仕様になっています（ケースの数に1を加えるのはレポートを送信しないというケースをブラウザが加えるためです）。なお、ランダムに複数の送信パターンを選ぶ際は重複組合せの考え方で選択されます。つまり、選択可能な組み合わせの中から同じ組合せが選ばれることもあります。

組み合わせ

設定として主に clickに紐づくattributionを計測するデフォルトの計測設定のケースを考えます。このclickに紐づく広告主サイトの通知ではデフォルトでレポートが3つまで送信される仕様です。送信される期間もデフォルトで3つのwindow、3bitのtriggerデータがブラウザから送られてきます。

ただ、この数字は設定で

現時点で最大のwindow数は20に変更可能( 参考 )
trigger数は今後変更可能になる( 参考 )

のように変更することが可能です。このwindow数の3と trigger データの $2^{3}$ をかけ合わせた24種別が、計測側でtriggerの内容を区別できる粒度になります。逆に考えればこれ以上の粒度では計測不可能です（triggerの正確な時刻は取得できず、trigger時に3bit以上の情報は付与できません）。この設定での偽レポートの場合はこれに加えてレポートを送信しない1ケースを足した25種別を扱います（0-base で数0～24 とします）。この中からclickに紐づくレポート送信のパターンとして3個を選ぶため、求めるのは25種から3つを選択する重複組み合わせの数になります。

また、表記ですが $H_k^{n}$ は重複を許して k 個選ぶ組合せ数を表し、 $C_k^{n}$ は重複を許さず k 個選ぶ組み合わせ数を表すようにしています。

設定は25個の区別可能な要素から3個を重複を許して選ぶ組み合わせなのですが、この計算は、3個の星（★）と24個の棒を並べる場合の数として解釈できます *1。

具体的には以下の表で示される通りです。

名称	値
bins	25
棒	24
★	3

計算例は

重複組合せの $H_3^{25}$ あるいは 25 multichoose 3 の数は2925となりますし
通常の組合せの $C_3^{27}$ あるいは 27 choose 3 の数も2925 で同じになります

この $H_3^{25}$ = 2925 が (3 * 8 + 3 choose 3) なのは、 $H_3^{25} = C_3^{25 + 3 - 1 } = C^{27}_3$ だからです。ここで、25 + 3 - 1 は星と棒による計算方法を表しており25 + 3 - 1 = 3*8 + 1 + 3 - 1 = 3*8 + 3 です。送信しない1ケースを+1したり、binsを棒で表現するときに-1しています。公式ドキュメントには 3 * 8 + 3 choose 3 が記載されています*2。

binsが25 をまず考えます。

ケース	Stars and bars
0	\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|★★★
1	\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|★\|★★
…
2924	★★★\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|

bins が4 も考えておきます(bins 25 との共通点に注意)。

ケース	Stars and bars
0	\|\|\|★★★
1	\|\|★\|★★
…
19	★★★\|\|\|

このように、★と棒の位置を固定させて、数値と組み合わせを１：１で対応を決めておきます。ここまでの段階で数値と組み合わせの対応が決まったので、次は、ランダムに組み合わせを生成する部分を説明します。ここからは、この0～2924の範囲の数値に対して1268がランダムに選択された状況を考えます。 1268 がFake 用に選ばれた時、どのような値が設定から決定されていくかを見ていきます。

しかし、最初にまずこの自然数の値1268から組合せを決定できる計算方法が必要になってきます。ここで、自然数の値から組み合わせ決めるのに、combinatorial number system が使われます。日本語だと組合せ数体系となりますが自然数Nと任意のk-組合せを対応させるルールを定めています。ルールに従うと、以下のようにすべての自然数Nをk個の2項係数の和として表現することができます。

$N = \binom{c_k}{k} + \cdots + \binom{c_2}{2} + \binom{c_1}{1}$

実際の計算例を見てみましょう。オンラインの計算ツール*3 にアクセスするとN=72が degree 5（初期値）とした場合の計算結果が表示されます（こちら*4に説明があります）。

基本的には、

$\binom{c_k}{k} - 1 = \sum_{m=1}^{k} \binom{c_k-k-1+m}{m}$ が成り立つまで $c_i (1 \leq i \leq k)$ を減少列の形で辞書的順序になるように1増やして対応するようにNを1増やします。 $\binom{c_k}{k}$ が成り立つ大きさになると最上位の桁の数値 $c_k$ を繰り上げてほかをリセットします。こうすることで同じ対応方法で数のようにNをいくらでも増やせます*5。今回の choose 3（k=3の組合せ）の場合について、Nを最小のものから順番に表示する例を見れば直感的には十分でしょう。

$0 = \binom{2}{3} + \binom{1}{2} + \binom{0}{1} = 0 + 0 + 0$

$1 = \binom{3}{3} + \binom{1}{2} + \binom{0}{1} = 1 + 0 + 0$

$2 = \binom{3}{3} + \binom{2}{2} + \binom{0}{1} = 1 + 1 + 0$

$3 = \binom{3}{3} + \binom{2}{2} + \binom{1}{1} = 1 + 1 + 1$

$4 = \binom{4}{3} + \binom{1}{2} + \binom{0}{1} = 4 + 0 + 0$

例の最後では最左の $c_i$ が増加し他をリセットしています。

現在、仮に選択している1268 の場合の計算結果は組 (20,16,8) になります。

$1268 = \binom{20}{3} + \binom{16}{2} + \binom{8}{1} = 1140 + 120 + 8$

この処理は実際の実装では（Chromiumでは）GetKCombinationAtIndex という名称の関数で実装されています。下の表に実際の(n,k)=(6,3)のケースを列挙してみました。star index の列がこの関数の出力に該当しています。

ケース	star index	Stars and bars
0	2,1,0	\|\|\|★★★
1	3,1,0	\|\|★\|★★
2	3,2,0	\|\|★★\|★
…
18	5,4,2	★★\|★\|\|
19	5,4,3	★★★\|\|\|

24+3 まで列挙すると以下のようになります。

ケース	star index	Stars and bars
0	2,1,0	\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|★★★
…
2924	26,25,24	★★★\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|\|

さて、この段階では star index はk-組合せで選択された数値になってしまっています。つまり、24+3 の範囲には収まっていますが $H^{25}_3$
の範囲の 0～24 に収まっていないです（k-組合せとして例示できるもののまだk-重複組合せとして例示できません）。

以下のように右側の棒の数を数えることで、24+3 の範囲の数値が 0～24 の範囲になるように変換できることが知られています。

この処理は実際のChromiumでは、GetBarsPrecedingEachStar 関数で行われています。

このように変換したものを以下の表に3-multiset という列*6を追加しましたが、数値が 0～24 の範囲に収まりました。

ケース	star index	3-multiset
0	2,1,0	0,0,0
1	3,1,0	1,0,0
2	3,2,0	1,1,0
…
19	5,4,3	3,3,3
20	6,1,0	4,0,0
…
1268	20,16,8	18,15,8
…
2924	26,25,24	24,24,24

これで、k-重複組合せで表示できます。

ここからは組み合わせ数体系に関する補足です。上記の棒の数え上げの変換で k-重複組合せの表示に常に変換が可能なのは、

star indexと3-multisetの関係が、3桁の数値を $c_3c_2c_1, d_3d_2d_1$ とすると

$c_1=d_1, \space c_2=d_2+1, \space c_3=d_3 + 3 - 1, \cdots, c_n = d_n + 3 - 1$

の関係が成り立っているからで、この対応は一般的に成立します*7。

k-組合せを、k-重複組合せに1:1で対応付けると重複する方はより少ない数値で表現されますがこの数体系におけるNの表現の違いと考えられます。この数体系ではkは初期値で変えません。最上位の桁 $c_k$ が変化すると、他の桁の数値がリセットされます。ここはk-重複組合せ表示を使うと直感的に理解しやすいです。 Nが $\binom{4}{3}$ や $\binom{5}{3}$ に到達すると3-multisetは111 -> 200や222 -> 300になり最上位の桁が繰り上ります。これは10を初期値とするp進数(10進数)の499->500などに似ています。

ダミーの設定の決定

ランダムに数字を選んで、対応する組み合わせも選ばれるところを紹介しました。続いてFake Report で実際に使うダミーの値を決めている個所を紹介しておきます。この段階で得られた数字の組の(0,0,0) から (24,24,24) は 3-重複組合せ( $H^{25}_3$ ) で選んだ3組の数字になっています。

今回選択している1268の場合、 (18,15,8) は実際には trigger データ/window index の2属性がダミーの設定を作る際に必要で、実装では、整商と剰余でfakeの値に使用しています。

    auto result = std::div(num_bars - 1, trigger_data_cardinality);
    const int trigger_data = result.rem;
    fake_reports.push_back({.trigger_data = static_cast<uint64_t>(trigger_data),
                            .window_index = result.quot});

上記の整商と剰余の計算に注意すると、以下がダミー値として決定します。この数字は実際に単体テストで使用されています*8。

{
                  {.trigger_data = 1, .window_index = 2},
                  {.trigger_data = 6, .window_index = 1},
                  {.trigger_data = 7, .window_index = 0},
}