Time limit exceeded- Error!

When running the same code for sorting integers, but on a test case of size of order 10^6 I realized that it took more than 5s to sort the integers in python.

Here is my code:

import time, profile
def timing():
    t1 = time.time()
    f1()
    print "f1: %.3f" %(time.time()-t1)
    t2 = time.time()
    f2()
    print "f2: %.3f" %(time.time()-t2)

def f1():
    lint = int
    list = [lint(raw_input()) for i in range(lint(raw_input()))]
    list.sort()
    for l in list:
        print l
    return

def f2():
    list = [int(raw_input()) for i in range(int(raw_input()))]
    list.sort()
    for l in list:
        print l
    return
profile.run('timing()', 'sort.tmp')

Vim is really programmers best friend like earthworms are farmers'
Vim helped me write a test case of this size in < 60 sec, and now I am there ready with a profiler and the time module to measure the time it takes to run that sort call.. The sort call that is a built-in function is probably not the culprit, I think in case I could parallelly carry on the reading and the sorting process the much needed optimisation can be brought..
This particular problem at the codechef.com under the easy problems tab is not that easy to do in python.. Everytime I get TLE error..
Some handy commands in vim:
:set binary
:set noeol
let me turn off the automatic end-of-line vim adds to every file editted in it.. And the profiler and time tools are easily available on the web can be found using google!

Here is the profiler output.

>>> import pstats
>>> p = pstats.Stats('sort.tmp')
>>> p.sort_stats('cumulative').print_stats(15)
Thu Dec 30 16:17:31 2010    sort.tmp

         2103371 function calls in 114.964 CPU seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000  114.964  114.964 profile:0(timing())
        1    0.109    0.109  114.964  114.964 sort.py:2(timing)
        1    0.000    0.000  114.964  114.964 :1(?)
        1   93.992   93.992  114.855  114.855 sort.py:10(f1)
  2103357   19.643    0.000   19.643    0.000 :0(raw_input)
        2    1.110    0.555    1.110    0.555 :0(sort)
        2    0.110    0.055    0.110    0.055 :0(range)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
        4    0.000    0.000    0.000    0.000 :0(time)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 sort.py:18(f2)




Suggestions solicited.. Just in case someone has faced this before, I have to submit a solution in python that sorts the huge integers in < 5 sec..

Unarchiving Heritrix' archives - arc.gz

Those who have used heritrix for web crawling are aware of  the 'arc' format. For others, Heritrix is a web crawler (a million $ guess :P) which archives the pages it has crawled into arc format.
In order to collect the corpus for training my classifier I thought of using it. Though phoneyc would have been an option, but I had to collect as many samples as possible so I planned on using heritrix.
Configuring it is pretty easy as it has a nice documentation. Well, in order to extract the crawled pages I was searching for some script or tool (I am too foolish and scared of errors while coding, in short i am a noob!), so I wasted quite a lot of time googling.. Sometimes laziness is a boon, I wish I had been lazy to google!
Finally, I mailed Peter Likarish, a Phd. student at University of Iowa, who had previous experience with heritrix and obfuscated JS classification too, and he suggested that arc's are flat files and its pretty easy to extract pages from there. Also, some understanding of sgmllib.py helped me. using a handful of regular expressions and some loops, ta-da!! I got the code up and running!
For interested readers, the code is here.
I have tried it on some arc's, it seems to work fine. Well, in case someone tries to use it and run into a bug, I apologise for their inconvenience. Please let me know in case of problems, bugs, or errors. I would be grateful..

so, start crawling!!!

Malicious Javascript - blueprints

Javascript might be a great scripting language but it has been recently been abused a lot to carry out drive-by-downloads attacks. It targets the browsers and the plugins vulnerabilities at the client side.

There are certain features in the structure of the malicious javascript, though, which can be used to detect its presence with high precision. My GSOC 2010 project aims at finding these features and extracting them and thus classify scripts on the basis of these scores into benign and malicious. Finally integrating the complete solution in the low interaction client honeypot - PhoneyC.
I have extracted 9 features, which have been mentioned by a lot of people in their works. These features have been extracted from a very very modest corpus, which is not very broad yet, of 15 benign and 10 malicious JS samples.
The findings expressed as graphs, file against the feature value can be found here. The graphs show malicious scripts features in red and benign scripts in blue.

1. average characters per line
2. average eval() argument length
3. string definition to string use ratio
4. # unicode characters
5. # lines in the script
6. % human readable characters
7. % white space in the script 
8. # words in the script
9. dynamic execution calls

Though the results aren't very encouraging for all the features, but some of them like the string definition to use ratio, % human readable characters, %white space, offer some hope. Improvements in the implementation of the features extraction with little assumptions is required to build a proper extractor for the classifier.
The code for the feature extractor and the classifier may be accessed in my svn branch of phoneyc under njain-anomalydetection.

I sincerely appreciate the comments and reviews on the current work feature extraction and classification.
p.s. - truly speaking,this is my first attempt at regex, pickling, or in short, programming, in that case. All thanks to the mentor for his able guidance and constant motivation.

Anomaly Detection

Anomaly detection is a unique approach to find the odd one out or malicious value. The approach basically involves learning the normal behavior and then detecting variation from this established behavior, which is called a profile. The variation is found based on a model. A model supports in learning as well as detecting. The crux of the approach is "the model".
A basic understanding of the approach can be had from the following program which learns A, an arbitrary integer variable. This model learns that A normally lies between the minimum and maximum values input during the learning mode. It also learns a threshold as 10% of the mean of the entered values. After successfully learning the values of A the model switches to the detection mode. In this mode the difference of the entered value and the mean is compared to the threshold. A difference greater than the threshold is marked anomalous and the value is put in the anomaly list else it is appended to the normal list of values. This is a very naive but working implementation of anomaly detection approach.
The original python implementation is here:

class learna(object):

    def learnA(self):
        """a function to learn a"""
        list=[]
        list=l.learn()
        low=min(list)
        high=max(list)
        avg=sum(list)/len(list)
        print "average is",avg
        l.detect(low,high,avg)


    def learn(self):
        print "learning mode"
        alearned=[]
        for i in range(5):
            al=int(raw_input("enter integer value for a."))
            alearned.append(al)
        lower=min(alearned)
        upper=max(alearned)
        print lower,"<",upper
        return alearned

    def detect(self,low,high,avg):
        print "running in detection mode."
        aentered=[]
        anomaly=[]
        normal=[]
        anomalous=[]
        threshold=0.1*avg
        for i in range(5):
            ae=int(raw_input("enter current integer value."))
            aentered.append(ae)
            if (aehigh):
                anomaly.append(ae)
            else:
                normal.append(ae)
            if (abs(ae-avg)>threshold):
                anomalous.append(ae)
        print "total anomalous value",len(anomaly)
        print "total normal values",len(normal)
        print "total entered values", len(aentered)
        print "total detected anomalous values",len(anomalous)