20080603

Move to WordPress

I was writing blog about interesting security stuff before in blogspot.

However, it seems that WordPress is a more interesting place to writing on

(Mostly because its beautiful themes)

I just start writing there, enjoy and feel free to visit my new blog.

New blog:
http://cskane.wordpress.com/
Posted by at No comments:

20080523

document.write()

These days I am working on Ajax, learning how to do simple HTTP request through Ajax.
Accidentally, I found an interesting property that js has: document.write(). Some of you may already know how to use it to do evil thing, but it is really new to me and I would like to share it with you.

document.write() is a function in js going to write data into the browsing page. The interesting point of this function is that it will overwrite the original HTML file. Let see an example using it with HTTP request.
Let say we have a evil.html containing a piece of code as follow.
<html>
<script type="text/javascript">
function fetch() {
var xmlHttp;
  try {
    xmlHttp = new XMLHttpRequest();
} catch (e) {
  try {
    xmlHttp = new ActiveXObject("Msxml2.XMLHTTP");
  } catch (e) {
    try {
      xmlHttp = new ActiveXObject("Microsoft.XMLHTTP");
    } catch (e) {
      alert("You Win!");
      return false;
    }
  }
}
xmlHttp.onreadystatechange = function() {
  if (xmlHttp.readyState == 4) {
    document.write(xmlHttp.responseText);
    document.close();
  }
}
xmlHttp.open("GET", "index.html", true);
xmlHttp.send(null);
return true;
}
</script>
<body onload="javascript:fetch()">

</body>
</html>

The index.html file that evil.html want to get is a normal page. Once a user going to browse evil.html, the script will replace evil.html as index.html. The code above is no harm at all. It tried to request the index.html under the same directory. However, it can easily be used to do malicious thing. Consider we add some code before getting the index.html, eg.
userInfoRequest = new XMLHttpRequest();
userInfoRequest.onreadystatechange = function() {
if (xmlHttp.readyState == 4) {
  var content = userInfoRequest.responseText;
  /* send the content to somewhere hacker want to store it */
}
}userInfoRequest.open("GET", "user_info.html", true);
userInfoRequest.send(null);
You can imagine what's going on with this piece of code. I am going to find a vulnerable site that allow me to demo this malicious code. I will back on this topic soon.

Should you have any comment or idea or whatever interesting stuff, please feel free to share with me.
Posted by at No comments:
Labels: , ,

20080101

Minimum Cut

Minimum cut problem usually refer to s-t minimum cut, which can be solved by using maximum flow algorithm (eg. Ford-Fulkerson, Edmonds-Karp, relabel-to-front, ... etc.). The problem discuss in this article is general minimum cut problem. Given an undirected graph G = (V, E), a cut is to split the nodes of the graph into two set S and T. Any edge (u, v) in E with either u in S and v in T or u in T and v in S is a cut edge, which is belongs to the cut set. In weighted undirected graph, a cut is minimum if the sum of weight of its set is the smallest among all possible cut set.

Gomory-Hu tree. This algorithm is used to construct a general graph into a tree, weight of edges of the tree correspond to the weight of the cut set to disconnect adjacent vertices. The idea of this algorithm is very simple. At the beginning, pick two vertices arbitrarily, and compute the minimum cut between them. Then separate the graph into two groups, contract the edges in the cut set into a new edge e', and the weight of e' is the weight of the cut set. After that, in each iteration, pick two vertices from the same group, and find the minimum cut between them, then separate the group into two and contract the edges as before. It is obvious that this algorithm only need O(n) iterations of computing minimum cut. There are many variations of this algorithm to get a better time complexity, you can google it if you are interested in.

Stoer-Wagner's min-cut algorithm. This is the algorithm I implemented these days. The algorithm is based on a theorem. Let s and t be two vertices of graph G = (V, E). Let G/{s, t} be the graph obtained by contracting s and t. Then, a minimum cut of G can be obtained by taking the smaller of minimum s-t cut and minimum cut of G/{s, t}. By this theorem, Stoer and Wagner comes up an algorithm. In each iteration of the algorithm, get two vertices which have a minimum cut to separate them, then contract these two vertices. This algorithm follows the theorem stated above. If the minimum cut is not current s-t cut, then it should be in the graph G/{s, t}. The following is the pseudo code of this algorithm.
MinCutPhase(G, w, a):
 A <- {a}
 while (A != V)
  x <- Most Tightly Connected Vertex
  if (|A| == |V| - 2)
   s <- x
  if (|A| == |V| - 1)
   t <- x
   CurrentCut <- (A, complement of A)
  add x to A
 Contract(s, t)
 return CurrentCut

MinCut (G, w, a):
 while (|V| > 1)
  CurrentCut <- MinCutPhase(G, w, a)
  if (w(CurrentCut) < w(MinimumCut))
   MinimumCut <- CurrentCut
In the pseudo code above, the definition of most tightly connected vertex x is:
  • x not in A s.t.
    • w(A, x) = max { w(A, y) | y not in A }
The only thing that we need to care is the correctness of the MinCutPhase function, and it can be proved by induction. This algorithm also need O(n) iterations to compute MinCutPhase(). If priority queue is used for getting the most tightly connected vertex in each iteration in MinCutPhase, in total it needs O(nlogn) time. For updating the weights of all the edges from the selected vertex to any vertices not in A, in overall it takes O(m) time. As a result, this algorithm run in O(nm + n2logn) time.

Related Problems:
Reference:
  • Stoer, M. and Wagner, F. 1997. A simple min-cut algorithm. J. ACM 44, 4 (Jul. 1997), 585-591. DOI= http://doi.acm.org/10.1145/263867.263872
  • Anne Loomis, Min cut, CS 105 (Winter 2005), Computer Science, Dartmouth College
Posted by at No comments:
Subscribe to: Posts (Atom)