3 ms·

This is an interesting way to attack mitigations to the German Tank Problem [0]. I expect the optimal solution is to increase the address space to prevent rand

This is an interesting way to attack mitigations to the German Tank Problem [0]. I expect the optimal solution is to increase the address space to prevent random samples from collecting enough data to arrive at a statistically significant conclusion. There are probably other good solutions which attempt to vary the distribution in different ways, but a truly random sample should limit that angle. [0] https://en.m.wikipedia.org/wiki/German_tank_problem https://en.m.wikipedia.org/wiki/German_tank_problem

consp 3y ago
I didn't read it in the article but this hinges on it being a discrete uniform distribution. Who knows what kind of shenanigans Google did to the identifiers.
- Maxion 3y ago
  Would be quite the challenge to use a skewed distribution of the address space that's skewed enough to mitigate this type of scraping while at the same time minimizing the risk of collisions.
- cbolton 3y ago
  Actually the method works regardless of the distribution. It's an interesting and important feature of random sampling. Consider 1000 IDs assigned in the worst (most skewed) way: as a sequence from 0 to 999. If there are 20 videos they will have IDs 0 to 19. If you draw 500 independent random numbers between 0 and 999, each number will have 2% probability of being in the range 0 to 19. So on average you will find that 2% of your 500 attempts find an existing video. From that you conclude that 2% of the whole space of 1000 IDs are assigned. You find correctly that there are 0.02*1000 = 20 videos.
  - pbhjpbhj 3y ago
    You've assumed the conclusion, you don't know it's 2%; you don't know there are 1000 possible addresses.
    - Aicy 3y ago
      For this example he does, he's saying [0, 999] is the possible space, but the distribution in that space is not done uniformly.
      - cbolton 3y ago
        Exactly, and if I make a mistake and assume that the possible space is 0 to 3999, it still works! I'll just need a bigger sample to estimate the number of videos with the same precision. (The method does fail if I exclude valid values, e.g. assume a space of 0 to 499).
        Aicy 3y ago
        We know what the possible space is for YouTube URLs.
        hhda 3y ago
        We assume we know the possible space for YouTube URLs, but it might not be a fair assumption. Take phone numbers as an analogy. Without foreknowledge or without careful analysis of the distribution of phone numbers, you might assume all numbers are valid, but in fact 555-xxxx is always invalid within each area code [0]. For each set of reserved numbers our address space is that much smaller, which can skew the results of the statistics we gather from it if we don't exclude them from our original calculations. It may be that YouTube reserves off certain address spaces (eg maybe it can't start with a 0, or maybe two visually similar values cannot be next to each other (eg I and 1), etc), which may make this sampling method (slightly less) accurate than it might otherwise appear. [0] https://en.wikipedia.org/wiki/555_(telephone_number) https://en.wikipedia.org/wiki/555_(telephone_number)
  - deleted 3y ago
    [deleted]
- 867-5309 3y ago
  this is exactly what springs to mind when it emerged google "conveniently" autocomplete under certain circumstances, thus making those identifiers more likely to be targeted. this completely skews the sample from the outset
pbhjpbhj 3y ago
How does a random sample solve for a clustered, say, distribution? Don't the estimations rely on assumptions of continuity? Suppose I have addresses /v=0x00 to 0xff, but I only use f0 to ff; if you assume the videos are distributed randomly then your estimates will always be skewed, no? So I take the addressable space and apply an arbitrary filter before assigning addresses. Equally random samples will be off by the same amount, but you don't know the sparsity that I've applied with my filter?
- barrkel 3y ago
  As long as the sampling isn't skewed, and is properly random and covers the whole space evenly, it will estimate cardinality correctly regardless of the underlying distribution. There is no way for clustering to alter the probability of a hit or a miss. There is nowhere to "hide". The probability of a hit remains the proportion of the space which is filled.

consp 3y ago

I didn't read it in the article but this hinges on it being a discrete uniform distribution. Who knows what kind of shenanigans Google did to the identifiers.

Maxion 3y ago
Would be quite the challenge to use a skewed distribution of the address space that's skewed enough to mitigate this type of scraping while at the same time minimizing the risk of collisions.
cbolton 3y ago
Actually the method works regardless of the distribution. It's an interesting and important feature of random sampling. Consider 1000 IDs assigned in the worst (most skewed) way: as a sequence from 0 to 999. If there are 20 videos they will have IDs 0 to 19. If you draw 500 independent random numbers between 0 and 999, each number will have 2% probability of being in the range 0 to 19. So on average you will find that 2% of your 500 attempts find an existing video. From that you conclude that 2% of the whole space of 1000 IDs are assigned. You find correctly that there are 0.02*1000 = 20 videos.
- pbhjpbhj 3y ago
  You've assumed the conclusion, you don't know it's 2%; you don't know there are 1000 possible addresses.
  - Aicy 3y ago
    For this example he does, he's saying [0, 999] is the possible space, but the distribution in that space is not done uniformly.
    - cbolton 3y ago
      Exactly, and if I make a mistake and assume that the possible space is 0 to 3999, it still works! I'll just need a bigger sample to estimate the number of videos with the same precision. (The method does fail if I exclude valid values, e.g. assume a space of 0 to 499).
      - Aicy 3y ago
        We know what the possible space is for YouTube URLs.
        hhda 3y ago
        We assume we know the possible space for YouTube URLs, but it might not be a fair assumption. Take phone numbers as an analogy. Without foreknowledge or without careful analysis of the distribution of phone numbers, you might assume all numbers are valid, but in fact 555-xxxx is always invalid within each area code [0]. For each set of reserved numbers our address space is that much smaller, which can skew the results of the statistics we gather from it if we don't exclude them from our original calculations. It may be that YouTube reserves off certain address spaces (eg maybe it can't start with a 0, or maybe two visually similar values cannot be next to each other (eg I and 1), etc), which may make this sampling method (slightly less) accurate than it might otherwise appear. [0] https://en.wikipedia.org/wiki/555_(telephone_number) https://en.wikipedia.org/wiki/555_(telephone_number)
- deleted 3y ago
  [deleted]
867-5309 3y ago
this is exactly what springs to mind when it emerged google "conveniently" autocomplete under certain circumstances, thus making those identifiers more likely to be targeted. this completely skews the sample from the outset

pbhjpbhj 3y ago

How does a random sample solve for a clustered, say, distribution? Don't the estimations rely on assumptions of continuity? Suppose I have addresses /v=0x00 to 0xff, but I only use f0 to ff; if you assume the videos are distributed randomly then your estimates will always be skewed, no? So I take the addressable space and apply an arbitrary filter before assigning addresses. Equally random samples will be off by the same amount, but you don't know the sparsity that I've applied with my filter?

barrkel 3y ago
As long as the sampling isn't skewed, and is properly random and covers the whole space evenly, it will estimate cardinality correctly regardless of the underlying distribution. There is no way for clustering to alter the probability of a hit or a miss. There is nowhere to "hide". The probability of a hit remains the proportion of the space which is filled.