search

rgbkrk / 301inabox

:on: HTTP Redirects in a box
Apache License 2.0
4 stars 1 forks source link

Prevent redirect loops #7

Open rgbkrk opened 10 years ago

rgbkrk commented 10 years ago

Prevent redirect loops from occurring within the internal data structure as well as within the admin node.

For example,

"x.org" -> "y.org"
"y.org" -> "x.org"

should not be allowed. More simply stated, no value (on the right side) should be a key (on the left side).

jaycaz commented 10 years ago

I'll start on this, but no guarantees that I'll have enough time to finish this by the end of the week.

jaycaz commented 10 years ago

Okay, I've given this some thought and I want to run this by you to make sure my algorithmic thinking is still up to par.

Assuming that we run this check_cycle function every time a record is added (and the function works properly), then we can guarantee that this data structure won't have any cycles before adding a new record. Also, because a domain can't redirect to multiple domains, no nodes will have more than one outgoing edge and so we won't need BFS/DFS to look for a cycle.

So, to check that there is no cycle when adding a domain, don't we just need to follow the redirection path from that new domain and make sure this path never points back to the original domain?

rgbkrk commented 10 years ago

If we're having to verify the data structure frequently, your thinking is right in line. It's simpler than that IMO.

Assume the previous set of records was valid and handle adding a record as a transaction. Checking it then is simply "is destination in origins?"

On Wednesday, August 6, 2014, jaycaz notifications@github.com wrote:

Okay, I've given this some thought and I want to run this by you to make sure my algorithmic thinking is still up to par.

Assuming that we run this check_cycle function every time a record is added (and the function works properly), then we can guarantee that this data structure won't have any cycles before adding a new record. Also, because a domain can't redirect to multiple domains, no nodes will have more than one outgoing edge and so we won't need BFS/DFS to look for a cycle.

So, to check that there is no cycle when adding a domain, don't we just need to follow the redirection path from that new domain and make sure this path never points back to the original domain?

— Reply to this email directly or view it on GitHub https://github.com/rgbkrk/301inabox/issues/7#issuecomment-51383044.

Kyle Kelley (@rgbkrk https://twitter.com/rgbkrk; http://lambdaops.com)

jaycaz commented 10 years ago

True, but what about this case?

"x.org" -> "y.org" "z.org" -> "y.org" and you want to add "x.org" -> "z.org"? z.org would be in the origins list, but would this create a cycle?

rgbkrk commented 10 years ago

Well darn.

While true, why make multi hops? I guess a user might be in the process of changing some of these. Hmmm. Guess we'll just have to allow it.

At the very least, you have an initial validity check (destination not in origins). The next follow on then is the classic cycle detection algorithm:

I'm on my phone, but I can come back to this again later

On Wednesday, August 6, 2014, jaycaz notifications@github.com wrote:

True, but what about this case?

"x.org" -> "y.org" "z.org" -> "y.org" and you want to add "x.org" -> "z.org"? z.org would be in the origins list, but would this create a cycle?

— Reply to this email directly or view it on GitHub https://github.com/rgbkrk/301inabox/issues/7#issuecomment-51384808.

Kyle Kelley (@rgbkrk https://twitter.com/rgbkrk; http://lambdaops.com)

jaycaz commented 10 years ago

I pushed up the basic loop change (https://github.com/rgbkrk/301inaboxadmin/commit/051720f853daa00814cd0a3250294cb18dfde6ac). I'll add in the two pointer solution soon, but first I wanted to set up some tests as well and I've been having some issues. When I run nosetests on the test_redir module, it works fine. But for some reason, running nosetests on the test_app module fails with an ImportError, even though I do the same thing as in the test_redir module. Would you mind taking a look to see what the issue may be? I've been staring at it all morning...