Online judge security problem

These few days, I am trying to use Python to rewrite the core of a online judging system (I use C to implement it before).
First, let me brief describe what is included in the core system.

• Compile program


• distinguish what programming language the user is using; (basically it only support Pascal, C and C++)


• use the corresponding compiler to compile the source code;


• limit the size of the objective program it can generate;


• report the compilation is success or not.


• Judge program


• run the compiled objective program with specific test input;


• limit its running time, memory used when it is executing;


• restrict its function call (or system call); (more on this later)


• compare its output with the test output;


• or, special judge if necessary.

I would like to discuss why we need to restrict its function call. Actually, it is both a security issue and prevent on cheating.
Let's discuss the prevention on cheating first. Obviously, if the user know the judge system architecture, one way to cheat is to open the test output file and print it, then he must get an Accept on the task. Or, if the system has stored other users solution, the cheater may hack in and use the solution as his own, even get a copy.

The most serious problem is that, the hacker may write a program which is trying to damage the operating system (OS). He may delete files, change the ownership of files, even get copy of some private files, then he can do some further attack. How horrible it is!

What most commonly use in C is a function ptrace (if I remember correctly, it only available *nix system). How it works is as follow.

• ptrace is called in a child process and stating that ptracing on itself;


• then parent process keep ptracing on its child process, for each signal the child process send out, parent process is first capture it before it send the signal away;


• at this point, the parent process is trying to recognize what child is doing by reading this signal, if its child is a bad guy, parent will kill him immediately;


• otherwise, parent will allow the child continue its process.

Actually, ptrace itself is also a very useful tool for hacking program. If the system allow ptrace call, hacker can write a program by using ptrace and stop some of your applications in OS and fetch the private information.

However, I am still trying to figure out how to do the same thing in Python. Actually, I cannot find something in Python which is similar to ptrace.

PC-tree

Definition:

A circular-arc graph is the intersection graph of a family of arcs of a circle.

Problem definition:

Given a graph G = (V, E), determine whether the graph is a circular-arc graph.

PC-tree is a data structure used to solve the above problem, discovered by Hsu and McConnell. PC-tree is an unrooted tree, its previous version is called PQ-tree which is discovered by Booth and Lueker in 1976. This article will focus on PC-tree only, because PC-tree is generalization of PQ-tree, which means any problem that can be solved by PQ-tree can reduce to PC-tree problems.

Each circular-arc graph can be represented by a clique matrix. Consider circular arc its corresponding circular-arc graph and clique matrix as follow:


By theorem, a graph is circular-arc iff. its clique matrix must a circular-ones property (proof provide later). Now the problem is focusing on how to check a matrix contains circular one property. PC-tree take the place to solve this problem. Let me introduce what is a PC-tree first.

PC-tree has two kinds of internal node, P-node and C-node (that's why it is called PC-tree). The children of P-node can be arranged in any order (ie. all permutations). Other than P-node, the children of C-node can only be arranged in the original order or its reverse (ie. if it's leaves is "ABC", another possible ordering is "CBA"). PC-tree is built by considering the rows of clique matrix one by one. The outline of the algorithm is as follow:

for each row in clique matrix {

assign the value to each row symbol;

find a Terminal Path to separate 0s and 1s;

align all 1s and 0s to the same side;

split each node on the path into two nodes, one connect to the leaves with 1s and one connect to 0s;

delete the edges of the path and replace with a C-node x;

contract all edges from x to C-node neighbors, and any node has only 2 neighbors.

}

The circular-ones ordering can be discovered from the graph by reading the leaves on PC-tree in clockwise or anti-clockwise. Like the following:
img provide later
The time complexity of the O(|E|) (proof provide later).

Further application is: scheduling jobs, minimum coloring, maximum cliques, planarity test, consecutive-ones, ...

Cross-Site Request Forgeries (CSRF/ XSRF)

Today, I google with the word "XSRF", some of you may know what it is, and it is not new. However, it is very amazing to me, because I did not think of using HTML code like this.

If you don't know what it is, let me introduce to you. If not, please state the mistake if any. XSRF, obviously is a webapp attack method. It is not only applied to HTML, but all markup language.
Let's see an example then you may know what the problem is.

<img src="http://www.bookstore.com/order.php?isbn=817525766-0&quantity=100&submit=yes" height=0 width=0 />

Although img is not including an image, the HTTP request is still send to the server. By setting the height and width of the img or using CSS style, the broken image can be hidden, the user even don't know such request has been sent. XSRF can force the user to updateing their profile, post new message or thread unknowingly. Sounds like not so dangerous, however it is more worse than that.

Difference between XSS and XSRF

Cross-Site Scripting (XSS) and XSRF are quite similar, isn't it? Actually they are not the same. XSS is try to either abuse client-side active scripting holes, or send privileged information to unknown site by inserting active code in HTML document.

XSRF is not rely on client-side active scripting, it try to take unwanted, unapproved actions on a site where the user has some authority.

It is difficult to filter content, because the XSRF attack may look like this:

<img src="http://itisnotanattack.com/logo.jpg" height=0 width=0 />

When your client requests logo.jpg, the file does not exist, but itisnotanattack.com server will redirect you to somewhere it like to show you.

XSRF can also be used to attack servers behind firewalls. It is not just public webapps that are at risk.

<img src="http://intranet/admin/purgeDB?confirm=yes" />

If the attackers knows enough to make a URL and can get the admin open this file, then everything is done. Now you know how funny (dangerous) it is.

Hide disclaimer in CSE personal hp

The day before yesterday, Billy try to hide the disclaimer in his personal homepage in CSE.
Tom suggested that the html file without "</body></html>" can avoid the disclaimer include in the file.
However, clearly, it is not satisfy the rule of W3C.
The file is obviously not complete.

Actually, I still cannot get the idea how it write the disclaimer in my file.
I think the page has been pass to some program to add the disclaimmer before including in response packet.
What it added to my file is as follow:

<link ... href="/css/disclaimer.css" ... >
<script ... src="/js/disclaimer.js" ... ></script>

and

<div></div><div></div>
<div id="cse-disclaimer">
...
</div><!-- #cse-disclaimer -->

The .js file has a function disclaimer(), it may called at the end of the page (before </body></html>), this function will enable visibility of the disclaimer block.

What I did to block the disclaimer again is very simple, create a .js file, content is similar to disclaimer.js.
When the body is being loaded, call the block function in my .js file, and it will disable the visibility of the disclaimer.
Is it easy? Yes, it is. However I spend whole day to test it, because I am not familar with JS.

Start this blog for what?

I am thinking these few day, if I should create this for making note on the interesting thing related to prog or security.
(I expect more on security. it is very new and interesting to me)

Hope I can post something everyday. :D
Please feel free to share your opinion