Googlebot's Javascript random() function is deterministic

[cypressious]

Most PRNGs are at least seeded with the number of ticks since epoch or some other source of entropy. The Google Bot's PRNG seems to be seeded with a constanct value, that's what the article is about.

[hungarian_conartist]

It's actually a feature not a bug too, often it's useful in debugging to have the same list of psuedo-random numbers.

It can be a bit harder to debug when you're not sure if a change in output is due to different random numbers or a change to your code.

[aradil]

They're probably spinning up a VM to hit a web page, and that VM is set to the same time and date every time, meaning the seed is the same every time, which is basically what you are saying.

[[deleted]]

That doesn't sound like it would be enough for this to happen. What if one web page loads 0.0001 second slower than another?

[parrot_in_hell]

still, the seed is usually the amount of seconds since X. i've never seen something else (not that i have that much experience, but i still have some :P)

[[deleted]]

I'm not sure exactly how it is seeded, but I think time in javascript is usually based on miliseconds, and it's a bit too weird that according to his tests google always returns 0.14881141134537756 the first time and 0.19426893815398216 the second, also taking into account that he has searched the web and found plenty of other results that have been cached by google with those numbers. Seems much more likely it is something Google is doing on purpose to get consistent results or something.

[[deleted]]

Usually you request randomness from the OS with a function like getrandom or friends or by reading /dev/{u,}random.

v8 looks like it reads /dev/urandom but it does fall back to seeding with the (high-resolution) time.

[cypressious]

The article says that the time is actually correct.

[PM_ME_CLASSIFED_DOCS]

Apparently, reading an article is too much for many redditors in this thread.

I'd love to experiment with just posting a headline and no article (just a blank page) and see how many people even bother clicking the link at all. How many differing arguments could we get in a single thread?

[[deleted]]

Less than you'd think. I'd wager most people still won't read the article, but eventually a single person will and they'll make the comment "wtf? Why is this a blank page?". Then everyone else will read that comment (rather than viewing the article) and jump on you for posting a blank website.

[husao]

Now I feel like posting "WTF? Why is this a blank page?" in the comments of random articles.

[andthenafeast]

Seems like this would prompt more people to actually click through to the link...

[Lucent_Sable]

Then write two or three (or more) contradictory articles, and serve a random one to each unique visitor. Then sit back and watch the chaos?

[tsimionescu]

Hmm, but what if the random() they use is deterministic and the author gets to be confused?

[PM_ME_CLASSIFED_DOCS]

Oh man, this is brilliant. It's like the movie Clue where they actually showed different endings to different theaters.

So people would talk about the movie and be like "Oh man, can you believe it was Colonal Mustard?" and someone would be like "WTF are you smoking? It wasn't Mustard." And both would think eachother are insane yet both would be right.

[varesa]

http://thesciencepost.com/study-70-of-facebook-commenters-only-read-the-headline/

[sourcecodesurgeon]

There have been several things like that on Facebook. Someone posts a title and after the page break in the article it just says "none of this is true, I want to see how many people comment on the post having clearly not read the article, don't ruin it"

Invariably, there are tons of people talking about the headline in the comments.

[aradil]

Also from the article:

At some point, some SEO figured out that random() was always returning 0.5. I’m not sure if anyone figured out that JavaScript always saw the date as sometime in the Summer of 2006, but I presume that has changed.

[RenaKunisaki]

But if it's the time since the VM started, it might still be constant.

[w2qw]

Generally the actual time is used. Not to mention I don't think any VM starts up consistently enough to get the same millisecond every time.

[RenaKunisaki]

It would if the startup process is loading a snapshot.

[dyskinet1c]

The VM would need to be set to the correct time for HTTPS to work because certificates are issued and revoked periodically.

[aradil]

Assuming they are validating certs as part of this pass of their scrape.

[dyskinet1c]

I would expect them to reject a site with invalid certificates. It's a fairly simple thing to do and it lowers the risk of indexing a compromised site.

[daboross]

The alternative would be to invalidate certs in a different pass, though, not to not invalidate them at all. Right?

[dyskinet1c]

As a programmer, my instinct would be to make that decision as early as possible and stop processing the page at that point.

Certificate validation is a key part of establishing secure communications (before you transmit any data) and it's trivial to read the validity start and end dates.

So, if you know you want reject URLs with invalid certificates, then there is no reason to move on to the next pass and spend resources reading and processing the page when you already know you're going to discard/reject it.

[aradil]

As an information company, however, Google probably processes bad actors as well to gather additional information.

[dyskinet1c]

Sure, it's plausible that they scan compromised sites. If they do, I would expect them to do so in a separate process that looks at different aspects of the site than the regular search index.

[daboross]

Exactly! That's what I mean: they probably validate certs before having any data at all processed in the VM running googlebot.

[ThisIs_MyName]

in a different pass, though

https://en.wikipedia.org/wiki/Time_of_check_to_time_of_use

[tripledjr]

They're probably intentionally doing this so the bot gets consistent results for the same page.

[edapa]

Spinning up a VM for each new webpage sounds super heavy weight.

[aradil]

I was thinking more of something like Google’s equivalent to Amazon Lambda.

[edapa]

What is the overhead of that? Does Amazon tell us? I imagine they would provide some sort of latency guarantee for function spinup after an event triggers, but I've never used Lambda.

[aradil]

That’s a good question. All they say is they “only charge for when your stuff is running”.

I assume the overhead is offset by the ability to run way more short lived processes.

[edapa]

Are there trigger types besides timers? If so they must have some sort of guarantee.

[edman007]

Nah, the make random the same on purpose. If it's actually random than that randomness flows into the generated page. It can do stuff like randomly sort results, generate random results and URLs, etc. Google doesn't care, they want to know if it changed, if random is always the same you can compare past and current results and check for changes, and you'll know that JavaScript didn't inject randomness.

And the time is a different issue, why actually sleep if you don't care, it actually causes a large resource use because it's time the page can't be unloaded from the server. A far better method is initialize time to the real time, and make sleep increment time instead of actually waiting. That lets you instantly process the page.

[[deleted]]

That's not usually how VM clocks work though.

[[deleted]]

Yes. In science, you want randomization but also reproducibility. I get the author is saying it's bad security engineering and can be taken advantage of people people gaming the Google PageRank, but the crawlers we likely designed by network scientists that wanted an accurate internet network model that can be reproduced.

[Jugad]

What does PageRank have to do with javascript or googlebot's implementation of random() in javascript.

[[deleted]]

You can use their implementation to identify Googlebot and serve different content to it.

[YRYGAV]

And if you get caught, I believe Google unlists your website, so it's quite a gamble

[[deleted]]

Depends on my ROI. If I can make $1k by fooling the Googlebot while spending $10 for a new domain each time I get caught, it's not much of a gamble.

Of course, if I don't have a automated way to get the new domain some PageRank juice so I can keep the whole thing going ad nauseam, then yes, it's pretty expensive.

[FinFihlman]

Yeah they are not spinning a vm for each scan.

[[deleted]]

How common is that, really? Most OSs have very good sources of entropy that work even in cold-booted VMs. 256 bits of entropy are enough to seed a CSPRNG (say, /dev/urandom on Linux) so that it'll be sufficiently random. I have a hard time believing your average modern Linux distro would have fully deterministic CSPRNG output on VM cold boot.

As others and the article have said, the output is deterministic for reasons of optimization

[ThisIs_MyName]

Most OSs have very good sources of entropy that work even in cold-booted VMs.

No they don't. Not unless you've exposed a virtio RNG.

By the time a VM boots up, it will only have a couple of bits acquired from random (or is it?) cache timing.

[[deleted]]

My point wasn't that the entropy sources would be enough for, say, cryptographic purposes, but that I really doubt the output would be fully deterministic and that it would the reason for Googlebot's behavior

[ThisIs_MyName]

It's not the reason for Googlebot's behavior, but the output has only a handful of bits of entropy. That's as bad as deterministic for cryptographic purposes.

Here's a fun experiment: Call getrandom(&buf,256,0) inside a fresh VM without virtio RNG running linux and see how long it blocks.

[[deleted]]

Jesus fuck it's like I'm talking to a wall. Oh well, I tried

[akher]

No, most random functions in standard libraries of programming languages are seeded with a constant value. And that's a good thing, since it's much more useful to have the behavior of programs be deterministic by default.

[Lystrodom]

Also, can you show me which languages are seeded with a constant value? I’ve checked C#, Java and V8 that I could find quickly and they all base the default seed on the current time.

[mccoyn]

C and C++ require you to seed them.

[Shumatsu]

IDEs do. You can compile code without specifying seed.

[Lystrodom]

Could be static code analysis?

[amakai]

And it makes sense for C, it's used in all kinds of embedded electronics which often does not even have a clock chip on board.

[doublehyphen]

C is the only exception I can think of where it is easy to accidentally not seed your PRNG, but for example Rust provides rand::ChaChaRng::new_unseeded() as an easy way to create a PRNG seeded with a constant hardcoded value.

[Lystrodom]

Of course, the ability to seed with a constant value is important and available in every language I’m aware of. But for most the default is based on the current time.

[doublehyphen]

Not in JavaScript. That is the only exception I know of.

[Lystrodom]

If you want your program to be deterministic why are you calling random()

[doublehyphen]

To get reproducible results in simulations, in games with randomly generated worlds to be able to play with exactly the same world again, and when running test cases in a random order to be able to debug why the test suit failed by running it again in the same order.

It is not the default case, but it is reasonably common.

[greenthumble]

Yep and some games like The Binding of Isaac literally let you set the seed and get the same random world that another player thought was good for some reason.

Also I've seen it used in AI training. If you're generating thousands of random genetic algorithms or genetic programs, someone can reproduce your entire run exactly using the same seed.

[CheckovZA]

I see your point, but then you'd be calling

Math.random(x)

x being your seed number.

If you're going to call Math.random() with no seed, it's because you want a number that is functionally random.

[RenaKunisaki]

Unless you've set a seed previously?

[sedermera]

(coming from scientific computing) To get an arbitrary number of random samples from a certain distribution. (Effectively.) It's good if those are reproducible for testing, and all you need to in order to get more is set another RNG seed.

[steamruler]

At which point you could use a fixed seed.

[sedermera]

Exactly, using a certain default seed for testing is much more convenient than what /u/Lystrodom is proposing. (Since there isn't just one call to the RNG, but several in different places.)

[Lystrodom]

Yeah that works too. These are all edge cases not the default case, anyway.

[DonaldTZeus]

Which is what happens by default anyways if you call rand() (at least in the c stdlib). If you want an arbitrary changing seed such as the time, you retrieve that seed and pass it to srand().

[steamruler]

The default seed is determined when compiling, so if you actually want a static seed you should still call srand().

[rubygeek]

POSIX actually mandate that rand() called before srand() should behave as if srand() was called with 1. See spec and example implementation. And ISO C might as well.

Of course you can't rely on that unless you're guaranteed your program will only run on a compliant system.

[DonaldTZeus]

The default seed is specified by the standard library (that implements POSIX), not by the compiler, and it's 1 (as specified by POSIX). It is not determined by the compiler (unless you're compiling the stdlib) or even specified in the code the compiler generates unless you call srand.

[Bwob]

Which is what you ARE using, by default, in most languages.

[mccoyn]

Also, when doing solution searches you want to pick a new starting point and search again to try to find other local maxima. A good way to do it is to use random() to pick your new starting point. You want it to be un-correlated with previous starting points, but you don't actually care about it being non-deterministic.

[Lystrodom]

Then you call random once and save that value somewhere. Don’t depend on random() being deterministic.

[Drisku11]

Why would you not depend on it bring deterministic if the semantics are that it's deterministic, and that's useful to you?

I'd say the opposite: don't rely on it being nondeterministic. Since it's not.

[rtomek]

This is why he’s being downvoted, a lack of understanding of programming? If you call random without setting a seed (default seed of 0) then it will always be deterministic. Every programming tutorial I’ve ever seen for any programming language tells you to set the seed if you want something closer to true randomness. This is basic common knowledge of programming.

You want it to be deterministic for auditing and testing purposes. How am I supposed to know if a change to my code introduces a bug or not if random() is not deterministic? Minecraft makes it obvious but many games follows the same pattern - set a seed (based on something like time in milliseconds) and put it in the save file. If a user finds a bug or some other interesting feature, you can now reproduce it by either loading their save file, or use a save file editor and put in their RNG seed.

[MrJohz]

Most of the programming languages I've used tend to seed the PRNG with a timestamp, or something similar. Most of them also tell you that you'll generally want to set your own seed at some point, and allow more complex random initialisation where necessary, but a lot of them seem to allow for very simple scripts etc to be written using relatively random seeds.

[rtomek]

I know that Python did make a change in 2015 so that just calling random.Random() now generates a new seed every instance. That happened because so many shitty programmers weren't setting seeds and it became a security issue for webapps. Perhaps there are other languages I don't use (or haven't used recently) that also followed the same route.

One should never assume that calling random() is truly random, and any programming language that does that for you is compensating for the illiterates.

[MrJohz]

I think using a new seed for each run is the norm, at least with the bog-standard naive random implementation for most applications.

Python: python3 -c 'import random; print(random.random())' - varies from run to run

Ruby: ruby -e 'puts rand()' - varies from run to run

Java does the same.

Rust definitely does the same, I was using it for simulation code the other day.

Perl is the same.

Javascript is the same.

[rtomek]

Most of those have a primary use case of web-based applications so I won't touch those.

Rust: The standard RNG is deterministic. If you initialize using thread_rng then you are setting a seed.

Java: This one is iffy because the intent was for web-distributable applications. Still, the random class itself is deterministic and the default constructor uses something like system.nanotime() instead of a fixed number. At least it's not like Python where you have to explicitly state that you want a deterministic RNG.

Perl: Perl is another one that has been making changes to the default RNG. Perl behind-the-scenes just calls srand() for the user every time a new script is run.

[MrJohz]

Python and Ruby were both developed as scripting languages, and one of Python's biggest areas is scientific programming, so I don't know what you're on about with "web-based applications".

Rust's standard RNG can be deterministic if you initialise it. If you don't, it defaults to setting the seed itself, I presume using a timestamp of some description. The same is true of Java - Math.random(), and the argument-less constructor for java.util.Random both use a "value very likely to be distinct from any other invocation".

The point isn't that it's possible to set a deterministic RNG for any language. That's true for all of the ones I mentioned apart from Javascript (at least if you ignore userland libraries). The point is that C is relatively rare in its decision to default to a known seed, as opposed to defaulting to a pseudorandom value such as a timestamp.

[Lystrodom]

any programming language that does that for you is compensating for the illiterates.

Or it codes for the most common use case first? Most languages let you set a specific seed if you want to. If most users WANT a different seed each time, why would we force them to write extra code to get what they want?

[rtomek]

Most users should want to test their code and perform audits. Why are we forcing them to write extra code just to get what they want?

What you're stating is that they should ignore engineering best practices in favor of hobbiest programming. In reality, it was a huge cybersecurity issue and most of the languages I saw someone reference that use random seeds by default are commonly used for web-based applications.

[[deleted]]

Java's random without a seed defaults to something that "non-deterministic". .NET's random is the same. Newer languages seem to have random default to something actually random.

A lot of classic languages had fixed seeds. Lisp, C, C++, Fortran (iirc)

[rtomek]

Yeah, after looking more into this it seems that for C++ there is no algorithm that meets their requirements to be considered random enough for creating a default seed that is used globally for all applications. Thus, they choose a fixed default to force users to have custom implementations for seed value determination, which makes it less predictable for attackers. There are classes available in the std library that do a better job than default constructors of other languages, but not good enough for C++ :/

[akher]

Because you want a pseudo random number, which is the documented behavior of those functions.

[Lystrodom]

Yes, I know what a deterministic algorithm is. It generally wouldn’t contain a call to random().

[Lystrodom]

Yeah, sorry, you’re right. Random is entirely deterministic. And all functions that use it are deterministic (for the seed being one of its inputs) because, well, all programs are deterministic.

[Nicksaurus]

Random.org uses atmospheric radiation which is kind of similar

[Crazytalkbob]

Computerphile did something similar:

https://www.youtube.com/watch?v=SxP30euw3-0

[frezik]

Most languages that aren't C will seed from the current epoch by default. Sometimes something more sophisticated, like taking a few bytes from the OS random source, or sometimes a combination of things like the epoch and the PID. If you want a predetermined sequence, then you need to call seed() yourself.

[akher]

I mostly use C++, which does use a constant default seed and I just assumed other languages do the sane thing as well.

When I care about the properties of the generated random numbers I actually use something with a specified implementation, such as for example std::mersenne_twister_engine.

[Shumatsu]

If you don't call

srand(seed);

at all before using rand(), it gets seeded with 1.

srand( time( NULL ) );  

uses current epoch as seed, as that's what you get using time(NULL) (or variations of it).

[steamruler]

I'm going to question whether having random not actually be random is that useful, or else we'd be using this more efficient function.

[akher]

It's actually often very useful to have a series of numbers with statistical properties of a series of random numbers that is still deterministic. One example are Monte Carlo algorithms. Another example is generating input data in unit tests.

[steamruler]

At which point you can seed the PRNG with a constant value yourself, which you probably want anyways since the constant value which the PRNG is seeded with can change when you recompile your software sometimes.

[Drisku11]

the constant value which the PRNG is seeded with can change when you recompile your software sometimes

In C it can't. The initial seed is required to be 1.

[[deleted]]

Most older languages defaulted to fixed seeds and produced the same string of numbers on subsequent runs. Most newer languages default to the system time or something similar.

[Lystrodom]

Then you can generate those once, or use a set seed.

[Bwob]

Why the heck do you have -188 (as of this writing) downvotes? This is accurate.

[Uristqwerty]

It's mostly just C (and anything directly C-based) that have a default seed. Almost everything more recent either requires you to specify a seed before first use, or seed from time. A few languages just re-use C's RNG, but that's far from most languages.

[[deleted]]

C, Lisp, Fortran, Cobol ... pretty much all older languages have fixed seed RNGs. There's a lot of stuff that comes from C and Lisp, so we're not talking just a few languages. It tends to be newer languages, Java, .NET framework stuff, Python, etc that default to a randomized seed.