(no title)

Linux Keylogger Proof of Concept

Posted on Sunday 24th April, 2011 | 8 Comments

I’ve just read ‘The Linux Security Circus: On GUI isolation’

It struck me that a linux keylogger is perfectly easy to write – I had previously (naïvely) thought such a program would only work given root permissions.

Alas! It’s stupidly easy.

see result of 30 minutes of hacking

The code simply calls xinput test [id of keyboard device] and parses out the keycodes. The id of your keyboard device can be found from the device listing given by xinput list.

→ 8 Comments

Posted in General

Tagged keylogger, linux, proof of concept, python, xlib

GrouPAY

Posted on Wednesday 23rd March, 2011 | Leave a comment

I’m currently interning at this new exciting startup in London – www.groupay.co.uk – check it out!

→ Leave a comment

Posted in General

Tagged groupay, intern, online payment, start-up

Haskell, Cellular Automata and Sierpinski Rule 90

Posted on Saturday 8th January, 2011 | 2 Comments

I’ve just finished writing an article for The Invariant Magazine (the annual Oxford Maths Society magazine which tends to actually get published once a decade) about cellular automata.

Whilst writing, I became a bit distracted, and decided to write some haskell to print 1D automata. After replacing most variables with single letters, and manually inlining some things, behold:
import Data.Bits ns xs = zip3 (drop (l-1) xs') xs (tail xs') where xs' = cycle xs; l = length xs s ru xs = map (\(l,c,r) -> if (2^(l*4 + c*2 + r) .&. ru) == 0 then 0 else 1) $ ns xs ss = map (\c -> if c == 0 then ' ' else '#') printAutomata :: Int -> Int -> [Int] -> IO () --one type sig needed printAutomata n r xs = mapM_ putStrLn $ map ss $ take n $ iterate (s r) xs

Then in GHCI, let’s try to simulate Rule 90 starting with a single cell of state 1.

Prelude> :l ca.hs
[1 of 1] Compiling Main             ( ca.hs, interpreted )
Ok, modules loaded: Main.
*Main> printAutomata 20 90 $ (replicate 20 0) ++ [1] ++ (replicate 20 0)
                    #                    
                   # #                   
                  #   #                  
                 # # # #                 
                #       #                
               # #     # #               
              #   #   #   #              
             # # # # # # # #             
            #               #            
           # #             # #           
          #   #           #   #          
         # # # #         # # # #         
        #       #       #       #        
       # #     # #     # #     # #       
      #   #   #   #   #   #   #   #      
     # # # # # # # # # # # # # # # #     
    #                               #    
   # #                             # #   
  #   #                           #   #  
 # # # #                         # # # #

Yay Sierpinski!

→ 2 Comments

Posted in General

Tagged automata, cellular, haskell, sierpinski

Fantastic HTTP Console

Posted on Friday 24th December, 2010 | 1 Comment

I’ve just started coding something for Google App Engine (which I’ll publish if it gets anywhere) and after reading First we built an API, then we built a CMS on Hacker News I decided to design the API first.

I wanted a way to test and play with this API from the console. A search threw up HTTY: the HTTP TTY, which is a fantastic HTTP console and makes testing a breeze.

One can cd between urls, build and clear query string with query-set and query-clear and use the HTTP verbs.

An example session

http://localhost:8080/api> query-set key aglib29rbWFya3NyDgsSCEJvb2ttYXJrGAMM http://localhost:8080/api?key=aglib29rbWFya3NyDgsSCEJvb2ttYXJrGAMM> get 200 OK -- 6 headers -- 328-character body http://localhost:8080/api?key=aglib29rbWFya3NyDgsSCEJvb2ttYXJrGAMM> body [{"user_tags": ["omg", "lol", "google", "123"], "created": "Fri Dec 24 18:42:42 2010", "_key": "aglib29rbWFya3NyDgsSCEJvb2ttYXJrGAMM", "title": "lol", "access": "public", "link": {"_key": "aglib29rbWFya3NyCgsSBExpbmsYAgw", "url": "http:\/\/www.lol.com\/"}, "user": {"nickname": "test@example.com", "email": "test@example.com"}}]

→ 1 Comment

Posted in General

Tagged google app engine, http, htty

Simple Quine in Python

Posted on Monday 20th December, 2010 | 1 Comment

I recently saw this blogpost – http://philipsung.blogspot.com/2010/12/people-who-are-not-in-our-league-v.html – which gives a quine in ruby with a twist (read the post). It struck me that somehow I’ve never tried at writing a quine.

Turns out a very simple quine (no attempt be concise) is.. very simple.

import zlib
data = b'x\x9c\xcb\xcc-\xc8/*Q\xa8\xca\xc9L\xe2JI,IT\xb0U\xa86\xa8\xe5*(\xca\xcc+\xd1\x00\x89\xea\xa5\xa4&\xe7\xe7\x16\x14\xa5\x16\x17k\x80\x14h\x82\x05RR5\xd4KK\xd2t-\xd45\xf5\xd2\xf2\x8br\x13K \x92\x9a\x00\x82\x1e\x1b\xc4'
print(zlib.decompress(data).decode('utf-8').format(data))

The data section is result of compressing the string:

import zlib
data = {0}
print(zlib.decompress(data).decode('utf-8').format(data))

and so we decompress the data and replace {0} with what the data is.

→ 1 Comment

Posted in General

Tagged python, quine

Annihilators, Perpendicular Spaces, A Connection

Posted on Wednesday 15th December, 2010 | 2 Comments

Whilst writing out revision notes, something struck me!

$\huge X^{\circ} = \varphi(X^{\bot})$

let $V$ be a finite dimensional real inner product space.
let $X \leqslant V$ be a subspace of V.

Definition

The annihilator of $X$ , denoted $X^{\circ} := \{ f \in V' \mid f(x) = 0 \, \forall x \in X\}$ where $V'$ is the dual space of V.

Definition

The perpendicular space of $X$ , denoted $X^{\bot} := \{ v \in V \mid \langle x,v \rangle = 0 \, \forall x \in X \}$

It might already be apparent that there is some connection between these two – both involve things going to zero, whenever something is done to everything in $X$ .

To make this more explicit, first we need a theorem.

Theorem: (weaker version of) Riesz Representation Theorem

$\varphi \colon V \rightarrow V' \colon w \mapsto (v \mapsto \langle v , w \rangle)$ is an isomorphism of vector spaces. Restated, we can associate each linear map uniquely $f \colon V \rightarrow \mathbb{R}$ with a vector $w \in V$ such that $f(x) := \langle x,w \rangle$ .

Proof:

Linearity:

let $u,v \in V, \lambda, \mu \in \mathbb{R}$
$\varphi(\lambda u + \mu v)(x)$
$= \langle x, \lambda u + \mu v \rangle$
$= \lambda \langle x, u \rangle + \mu \langle x , v \rangle$
$= \left ( \lambda \varphi(u) + \mu \varphi(v) \right )(x)$
and hence we see this is a linear map.

Injectivity:

Suppose $\langle v , w \rangle = \langle v , w' \rangle \, \forall v \in V$
then $\langle v, w - w' \rangle = 0 \, \forall v \in V$
so specifically $\langle w-w', w - w' \rangle = 0$
thus by positive definiteness, $w = w'$ hence $\varphi$ is injective.

Surjectivity:

Since we have that this is an injective linear map between spaces of the same dimension, this follows by Rank Nullity. Alternatively:
let $f \in V'$
take a basis $\varepsilon = \{e_1, \ldots, e_n\}$
then define $w := \sum_{i=1}^n \langle f(e_i),e_i \rangle e_i$
and we can check that this works.

Now to use this theorem to show the connection.

$X^{\circ} := \{ f \in V' \mid f(x) = 0 \, \forall x \in X \}$
but $\forall f \in V', f = \varphi(w)$ for some $w \in V$ .
thus $X^{\circ} = \{\varphi(w) \mid \varphi(w)(x) = \langle x , w \rangle = 0 \, \forall x \in X \} = \varphi(X^{\bot})$

So we have the result we wanted:
$\huge X^{\circ} = \varphi(X^{\bot})$

Applications

This means all of those oh-so-fun identities one derives for annihilator subspace structure can be passed over to perpendicular subspace structure!

Example:

Given the identity $X_1^{\circ} + X_2^{\circ} = (X_1 \cap X_2)^{\circ}$
we can deduce $\varphi \left ( (X_1 \cap X_2 )^{\bot} \right ) = (X_1 \cap X_2)^{\circ} = X_1^{\circ} + X_2^{\circ} = \varphi(X_1^{\bot}) + \varphi(X_2^{\bot})$
linearity of $\varphi$ gives us $\varphi(X_1^{\bot}) + \varphi(X_2^{\bot})= \varphi(X_1^{\bot} + X_2^{\bot})$
so by injectivity of $\varphi$ we have $(X_1 \cap X_2)^{\bot} = X_1^{\bot} + X_2^{\bot}$

i.e. compare
$X_1^{\circ} + X_2^{\circ} = (X_1 \cap X_2)^{\circ}$
to
$X_1^{\bot} + X_2^{\bot} = (X_1 \cap X_2)^{\bot}$

→ 2 Comments

Posted in General

Tagged annihilators, inner product space, isomorphism, linear algebra, perpendicular, real inner product space, representation theorem, riesz, vector space

Dual Numbers, Automatic Differentiation, Haskell

Posted on Friday 10th December, 2010 | 3 Comments

Duals are an extension to a number system such that $x^2 = 0$ has a non-zero solution.
We could consider them as a quotient:
– take a ring $R$
– quotient $R[X]$ by the ideal $< X^2 >$

Since we can keep things general in the theory, I’m going to take
duals over a general type a. Maybe I should look into the mathematical
prelude so that I will be able to specify a to be a ring, but that’s
for another day.

> data Dual a = D a a deriving Show

Some Notation

I shall also slip in and out of the notation $a + b\mathrm{j}$ to represent the Dual (D a b).

We could maybe use some utility functions to give us the ‘real’ and ‘dual’ parts

> real, dual :: Dual a -> a
> real (D a _) = a
> dual (D _ b) = b

In some ways, we can consider these as an analogue of the complex numbers,
but instead with $j^2 = 0$ . Anyhow, equality comes naturally as follows.
(We could get this from the polynomial definition using the coset definition of
equality)

> instance Eq a => Eq (Dual a) where
> (D a b) == (D c d) = (a == c) && (b == d)

Now, we want to treat this as a number.
Since things commute, addition and multiplication come naturally.

> instance Num a => Num (Dual a) where
> (D a b) + (D c d) = D (a+c) (b+d)
> (D a b) * (D c d) = D (a*c) (b*c + a*d)

Again, negation is fairly obvious

> negate (D a b) = D (-a) (-b)

Now Haskell wants us to give a definition for signum – i.e. give
some kind of subset of ‘positive’ duals.
Not sure that this really makes much sense. I’ll leave it undefined for now.

> signum (D a b) = undefined

We also need to give an ‘abs’. Taking inspiration from complex numbers,
if we were to define abs (D a b) to be (D a b)*(D a -b) we end up with

~~> abs (D a b) = D (abs a) 0~~

This is all kind of crazy! The complex numbers modulus maps from $\mathbb{C} \rightarrow \mathbb{R}$ whereas Haskell requires us to give a function from Duals to Duals. I can’t seem to see anywhere what properties such an abs function should have.

Haskell’s implementation of complex numbers does seem to give something similar to my implementation.
$\mathrm{abs } z \mapsto |z| + 0i$

For now then, I’ll just use the definition given here: http://en.wikipedia.org/wiki/Automatic_differentiation#Automatic_differentiation_using_dual_numbers

Finally we need to give a way of converting from integrals to duals – just
take the ‘dual’ part to be 0

> fromInteger n = D (fromIntegral n) 0

Now since Dual numbers are PRETTY MAGIC
– f(D a 1) = D f(a) f’(a)
we can automagically differentiate functions of type Num a => a -> a

> deriv :: Num a => (Dual a -> Dual b) -> a -> b
> deriv f x = dual $ f (D x 1)

Now we could probably do with some notion of division!

but how?!

(D a b) / (D c d) = (D a b) * (D c -d) / c² ?!?!

let’s try and see if crazy happens.

> instance Fractional a => Fractional (Dual a) where
> (D a b) / (D c d) = D (real x / (c*c)) (dual x / (c*c))
> where
> x = (D a b) * (D c (-d))
> fromRational r = D (fromRational r) 0

Everything seems fine!

Now for maybe the more interesting bit, I’d like to implement Duals for
standard functions – sin, cos, … etc
In haskell, this means implementing the Floating class.

> instance Floating a => Floating (Dual a) where

Taking pi to be the Dual with ‘real’ part of pi seems sensible,
though maybe we should ensure that this is still twice the first
‘positive’ root of cos, though quite what positive means.
Since it seems good to have that $cos(\pi/2) = 0$ ,
let us take pi to be $\pi + 2\pi\mathrm{j}$

> pi = D pi (2*pi)

Next thing to define is exp. Taking the power series definition,
and noting that

$(a+b\mathrm{j})^n = a^n + n b a^{n-1}\mathrm{j}$
(which follows from binomially expanding $(a+b\mathrm{j})^n$ and then noting that all other terms contain a $j^2$ .

it follows trivially that

> exp (D a b) = D (exp a) (b*(exp a))

Ok, so maybe something better is happening here.
Why not try a general power series. If we have:
$f(x) = \sum_0^\infty a_n x^n$
Then we can try sticking in the dual $x + y\mathrm{j}$
$f(x + y\mathrm{j}) = \sum_0^\infty a_n x^n nyx^{n-1}\mathrm{j}$
$= \sum_0^\infty a_n x^n + \left (y\sum_1^\infty a_n n x^{n-1} \right ) \mathrm{j}$

where we see the dual part is the termwise derivative! Woooop!
so, taking what we already ‘know’ of the derivatives of these functions
(though quite how this is applicable when our underlying Num type isn’t sane)
we get

$f(a + b\mathrm{j}) = f(a) + bf'(a)$

though, there is a problem in that, since haskell doesn’t ‘know’
these functions are defined in terms of power series, we can’t use
our existing deriv function to produce $f'$ :(
Lets get cracking then…

> log (D a b) = D (log a) (b*(1/a))
> sin (D a b) = D (sin a) (b*(cos a))
> cos (D a b) = D (cos a) (b*(- sin a))
> sinh (D a b) = D (sinh a) (b*(cosh a))
> cosh (D a b) = D (cosh a) (b*(sinh a))

–leave the inverse trigometric and hyperbolics for now, I’m lazy :D

We can even do crazy things now by taking duals over complex numbers, though
what this ‘means’ I’m not yet sure.

I shall have to think on this.

On the other hand, we are now able to differentiate fairly complicated functions.

> g x = (sin (x * cos (log (1 / (x**2 – 2*x + 3)))))**3
> g’ = deriv g

→ 3 Comments

Posted in General

Tagged complex numbers, differentiation, dual numbers, haskell, quotient

Linux Keylogger Proof of Concept

GrouPAY

Haskell, Cellular Automata and Sierpinski Rule 90

Fantastic HTTP Console

An example session

Simple Quine in Python

Annihilators, Perpendicular Spaces, A Connection

Definition

Definition

Theorem: (weaker version of) Riesz Representation Theorem

Proof:

Linearity:

Injectivity:

Surjectivity:

Applications

Example:

Dual Numbers, Automatic Differentiation, Haskell

Some Notation

Search It!

Recent Entries

Links

Follow “”

Linux Keylogger Proof of Concept

Share this:

Like this:

GrouPAY

Share this:

Like this:

Haskell, Cellular Automata and Sierpinski Rule 90

Share this:

Like this:

Fantastic HTTP Console

An example session

Share this:

Like this:

Simple Quine in Python

Share this:

Like this:

Annihilators, Perpendicular Spaces, A Connection

Definition

Definition

Theorem: (weaker version of) Riesz Representation Theorem

Proof:

Linearity:

Injectivity:

Surjectivity:

Applications

Example:

Share this:

Like this:

Dual Numbers, Automatic Differentiation, Haskell

Some Notation

Share this:

Like this:

Search It!

Recent Entries

Links

Follow “”