419117 - Add noise to gethash requests

Status: RESOLVED FIXED

(Toolkit :: Safe Browsing, defect, P1)

Description

[Dave Camp (:dcamp)]

We want to add a few randomly-selected hash prefixes to the gethash request to obscure which hash prefix we actually visited.

Comment 1

[Dave Camp (:dcamp)]

Attachment: v1

Attached patch adds 4 randomly-selected partial hashes to the gethash request.

We do this (as suggested by Dr. Hipp) by
a) Ensuring that ids are distributed somewhat evenly across the space by assigning them randomly at insert time.
b) Choosing a row with an id >= random() at lookup time.
c) If that set is empty, select the lowest id (simulate wrapping around the list)

Comment 2

[Dave Camp (:dcamp)]

Attachment: v1, right patch

Comment 3

[Tony Chang (Google)]

Comment on attachment 305620 [details] [diff] [review]
v1, right patch

>   rv = mConnection->CreateStatement
>-    (NS_LITERAL_CSTRING("INSERT OR REPLACE INTO ") + entriesTableName +
>-     NS_LITERAL_CSTRING(" VALUES (?1, ?2, ?3, ?4, ?5, ?6)"),
>+    (NS_LITERAL_CSTRING("INSERT INTO ") + entriesTableName +
>+     NS_LITERAL_CSTRING(" VALUES (abs(random()), ?2, ?3, ?4, ?5, ?6)"),
>      getter_AddRefs(mInsertStatement));
>   NS_ENSURE_SUCCESS(rv, rv);

The REPLACE INTO was removed because we want to error out on collisions of random numbers right?  Does this break any old behavior that expected being able to replace entries?


>   if (newEntry) {
>+    // The insert statement chooses a random ID for the entry, which
>+    // might collide.  This should be exceedingly rare, but we'll try
>+    // a few times, otherwise assume a real error.
>+    nsresult rv;
>+    for (PRUint32 i = 0; i < 10; i++) {
>+      mozStorageStatementScoper scoper(mInsertStatement);
>+

Should 10 be a const in the file?


And a more general question: What type of performance hit does this change have?

Comment 4

[Dave Camp (:dcamp)]

(In reply to comment #3)

> The REPLACE INTO was removed because we want to error out on collisions of
> random numbers right?  Does this break any old behavior that expected being
> able to replace entries?

Nah, WriteEntry() was updated to use the UPDATE statement in the case of existing entries.

> >   if (newEntry) {
> >+    // The insert statement chooses a random ID for the entry, which
> >+    // might collide.  This should be exceedingly rare, but we'll try
> >+    // a few times, otherwise assume a real error.
> >+    nsresult rv;
> >+    for (PRUint32 i = 0; i < 10; i++) {
> >+      mozStorageStatementScoper scoper(mInsertStatement);
> >+
> 
> Should 10 be a const in the file?

I chose to just keep the magic number in that one place rather than having to spread the documentation explaining what we're doing between that function and the top of the file.  I could change it, but...

> And a more general question: What type of performance hit does this change
> have?

I'd previously been measuring lookup performance.  There's no penalty for a lookup that doesn't match.  A lookup that does match incurs a slight penalty, but insignificant compared to the gethash request that follows.

However, after looking more closely it appears to cause a few other problems.  On my tests it slows down updates by like 50-70%, and increases the file size by 30-40%.  The file size increase is worrisome, it's already an unfortunately large file.

I'm going to put together a patch that tries to solve this a different way.

Comment 5

[Dave Camp (:dcamp)]

Attachment: different approach

This patch takes a different approach.

Rather than selecting 4 random rows, it selects 4 rows adjacent to the row we hit.  How much it selects in each direction is determined randomly.  The general idea should still be the same (we send 5 rows, with no reliable way to determine which I visited), but it's not really as random - the same adjacent rows are generally going to be sent next to each other.

Update performance/disk space usage are not affected, and lookup speed should be a bit faster in most cases than the previous patch.

I couldn't find a decent safe-on-a-thread random number generator, so this code asks sqlite for a random number.  Any suggestions?

Comment 6

[Tony Chang (Google)]

Comment on attachment 305791 [details] [diff] [review]
different approach

PR_GetRandomNoise isn't thread safe?

Comment 7

[Dave Camp (:dcamp)]

As I understand it, PR_GetRandomNoise() isn't really intended to give a random number.  It's just meant to seed a decent PRNG.

Comment 8

[Dave Camp (:dcamp)]

Actually, nsIRandomGenerator should be ok on a thread (as long as it isn't passed between threads), putting together a new patch now.

Comment 9

[Dave Camp (:dcamp)]

Urgh, except it's a Service, not a CreateInstance'ed Object, so that won't work.

Fixing that should be easy enough, but I don't know if we can get that reviewed etc. in time for beta 4.  I think it'd be best to land this patch as-is and file a follow-up to make nsIRandomGenerator threadsafe.

Comment 10

[Tony Chang (Google)]

(In reply to comment #9)
> Urgh, except it's a Service, not a CreateInstance'ed Object, so that won't
> work.
> 
> Fixing that should be easy enough, but I don't know if we can get that reviewed
> etc. in time for beta 4.  I think it'd be best to land this patch as-is and
> file a follow-up to make nsIRandomGenerator threadsafe.

Sounds good to me.

Comment 11

[Dave Camp (:dcamp)]

Attachment: use nsIRandomGenerator

Followup patch to use nsIRandomGenerator once bug 419739 has landed.

Comment 12

[Mike Beltzner [:beltzner, not reading bugmail]]

I think we want this for beta 4.

Comment 13

[Dave Camp (:dcamp)]

Checking in browser/app/profile/firefox.js;
/cvsroot/mozilla/browser/app/profile/firefox.js,v  <--  firefox.js
new revision: 1.288; previous revision: 1.287
done
Checking in toolkit/components/url-classifier/src/nsUrlClassifierDBService.cpp;
/cvsroot/mozilla/toolkit/components/url-classifier/src/nsUrlClassifierDBService.cpp,v  <--  nsUrlClassifierDBService.cpp
new revision: 1.63; previous revision: 1.62
done
Checking in toolkit/components/url-classifier/tests/unit/head_urlclassifier.js;
/cvsroot/mozilla/toolkit/components/url-classifier/tests/unit/head_urlclassifier.js,v  <--  head_urlclassifier.js
new revision: 1.9; previous revision: 1.8
done