Determine the frame structure

src/org/adblockplus/android/AdblockPlus.java

Index: src/org/adblockplus/android/AdblockPlus.java
===================================================================
--- a/src/org/adblockplus/android/AdblockPlus.java
+++ b/src/org/adblockplus/android/AdblockPlus.java
@@ -23,7 +23,11 @@
 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;
 
@@ -84,6 +88,25 @@
   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).
@@ -338,6 +361,9 @@
    */
   public boolean matches(String url, String query, String referrer, String accept)
   {
+    if (referrer != null)
+      referrerMapping.put(url, referrer);
+
     if (!filteringEnabled)
       return false;
     
@@ -368,7 +394,24 @@
     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;
   }
 
   /**