Determine the frame structure

src/org/adblockplus/android/AdblockPlus.java

 /*
  * This file is part of Adblock Plus <http://adblockplus.org/>,
  * Copyright (C) 2006-2013 Eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 package org.adblockplus.android;
 
 import java.io.BufferedReader;
 import java.io.File;
 import java.io.FileNotFoundException;
 import java.io.IOException;
 import java.io.InputStream;
 import java.io.InputStreamReader;
+import java.util.ArrayList;
 import java.util.Calendar;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
 import java.util.TimeZone;
 import java.util.regex.Pattern;
 
 import org.adblockplus.android.updater.AlarmReceiver;
 
 import android.app.ActivityManager;
 import android.app.ActivityManager.RunningServiceInfo;
 import android.app.AlarmManager;
 import android.app.Application;
 import android.app.PendingIntent;
@@ skipping 40 matching lines @@
   private Subscription[] subscriptions;
 
   /**
    * Indicates whether filtering is enabled or not.
    */
   private boolean filteringEnabled = false;
 
   private ABPEngine abpEngine;
   
   private static AdblockPlus instance;
+  
+  private static class ReferrerMappingCache extends LinkedHashMap<String, String>
+  {
+    private static final long serialVersionUID = 1L;
+    private static final int MAX_SIZE = 5000;
+
+    public ReferrerMappingCache()
+    {
+      super(MAX_SIZE + 1, 0.75f, true);
+    }
+
+    @Override
+    protected boolean removeEldestEntry(Map.Entry<String, String> eldest)
+    {
+      return size() > MAX_SIZE;
+    }
+  };
+
+  private ReferrerMappingCache referrerMapping = new ReferrerMappingCache();
 
   /**
    * Returns pointer to itself (singleton pattern).
    */
   public static AdblockPlus getApplication()
   {
     return instance;
   }
 
   public int getBuildNumber()
@@ skipping 234 matching lines @@
    *          Request query string
    * @param referrer
    *          Request referrer header
    * @param accept
    *          Request accept header
    * @return true if matched filter was found
    * @throws Exception
    */
   public boolean matches(String url, String query, String referrer, String accept)
   {
+    if (referrer != null)
+      referrerMapping.put(url, referrer);
+
     if (!filteringEnabled)
       return false;
     
     String contentType = null;
 
     if (accept != null)
     {
       if (accept.contains("text/css"))
         contentType = "STYLESHEET";
       else if (accept.contains("image/*"))
@@ skipping 10 matching lines @@
         contentType = "IMAGE";
       else if (RE_FONT.matcher(url).matches())
         contentType = "FONT";
     }
     if (contentType == null)
       contentType = "OTHER";
 
     if (!"".equals(query))
       url = url + "?" + query;
 
-    return abpEngine.matches(url, contentType, referrer);
+    final List<String> referrerChain = buildReferrerChain(referrer);
+    Log.d("Referrer chain", url + ": " + referrerChain.toString());
+    String[] referrerChainArray = referrerChain.toArray(new String[referrerChain.size()]);
+    return abpEngine.matches(url, contentType, referrerChainArray);
+  }
+
+  private List<String> buildReferrerChain(String url)
+  {
+    final List<String> referrerChain = new ArrayList<String>();
+    if (url != null)
+    {
+      referrerChain.add(url);
+
+      final String referrer = referrerMapping.get(url);
+      if (referrer != null)
+        referrerChain.addAll(buildReferrerChain(referrer));
+    }

[Wladimir Palant, 2013/11/27 14:00:30]

Please don't use recursive algorithms where they don't make sense. Note how this
code can allocate an unlimited number of lists, in addition to potentially
overflowing the stack. The iterative approach:

while (url != null)
{
  referrerChain.add(url);
  url = referrerMapping.get(url);
}

However, this is still a DoS vulnerability - a website can easily make us go
into an endless loop (make sure http://example.com/foo.html is recorded as
referrer of http://example.com/bar.html and http://example.com/bar.html as
referrer of http://example.com/foo.html). Limiting the size of referrerChain to
10 entries (?) should be the simplest solution, adding it to the loop condition
will do.

[Felix Dahlke, 2013/11/27 14:47:32]

Valid points, fixed.

+    return referrerChain;
   }
 
   /**
    * Checks if filtering is enabled.
    */
   public boolean isFilteringEnabled()
   {
     return filteringEnabled;
   }
 
@@ skipping 114 matching lines @@
       Log.e(TAG, e.getMessage(), e);
     }
 
     // Set crash handler
     Thread.setDefaultUncaughtExceptionHandler(new CrashHandler(this));
 
     // Initiate update check
     scheduleUpdater(0);
   }
 }