2014/08/03

How to set up your own MongoDB sharded cluster for development in one host.

In my current job I am using MongoDB as I need to deal with high-volumes of generated data and this NoSQL database is able to scale in a straight-forward and automatic way.

I will probably be covering different things related to this database engine in my next posts that I encountered while dealing while working with this.

In this post I will start with a basic thing: how to set up a MongoDB sharded cluster in your local machine.

If you don't know what a MongoDB sharded cluster is or what is it purpose I highly recommend reading the sharding section of the MongoDB documentation.

Components of a sharded cluster
Every sharded cluster has three main components:
  • Shards: This are the actual places where the data is stored. Each of the shards can be a mongod instance or a replica set.
  • Config Servers: The config server has the metadata about the cluster. It is in charge of keeping track of which shard has each piece of data.
  • Query Routers: The query routers are the point of interaction between the clients and the shard. The query servers use information from the config servers to retrieve the data from the shards.
For development purposes I am going to use three mongod instances as shards, exactly one mongod instance as config server and one mongos instance to be a query router.

For now I am not going to setup replica-sets for the shards, I am going to leave that for a future post.

It is important to remember that due to mongo restrictions the number of mongo config servers needs to be either one or three. In a production environment you need to use three to guarantee redundancy but for a development environment with one will be enough.

Setting up the sharded cluster

Folder structure

We are going to store the whole cluster inside a folder, this way it is easier to manage the cluster when needed .

For that we create the following folder structure in some location, in my case I am going to use the / directory:
  • /mongocluster/
    • mongod1/
      • logs/
      • data/
    • mongod2/    
      • logs/
      • data/
    • mongod3/
      • logs/
      • data/
    • mongoc/
      • logs/
      • data/
    • mongos/
      • logs/
      • data/
The mongods folders will be used for the shards, mongoc for the config server and mongos for the query router.

Configuration Files

Once the folder structure has been created, we proceed to create the configuration files for each of the processes.

We are going to use YAML configuration files, the new version of MongoDB uses this type of configuration file.
If you intend to use a version of MongoDB before 2.6 you will need to go to MongoDB's documentation to see how to translate the config files to the old config file format.

The configuration files I am going to give are the most basic ones to have the cluster up and running. If you need authentication or SSL you can add these to the configuration.

Shards configuration

For each shard we are going to use the following configuration template:
systemLog:
  destination: file
  path: "/mongocluster/mongodN/logs/mongodN.log"
  logAppend: true
processManagement:
  pidFilePath: "/mongocluster/mongodN/mongodN.pid"
  fork: true
net:
  bindIp: 127.0.0.1
  port: UNIQUE_PORT
storage:
  dbPath: "/mongocluster/mongodN/data"
  directoryPerDB: true
sharding:
  clusterRole: shardsvr
operationProfiling:
  mode: all

We are going to create a mongodN.conf inside each of the mongodN folders, replacing N for the corresponding number of shard.
Also it is important to set a different port to each of the shards, of course these ports have to be available in the host.

For example, for the /mongocluster/mongod1/mongod1.conf we can have this:

systemLog:
  destination: file
  path: "/mongocluster/mongod1/logs/mongod1.log"
  logAppend: true
processManagement:
  pidFilePath: "/mongocluster/mongod1/mongod1.pid"
  fork: true
net:
  bindIp: 127.0.0.1
  port: 47018
storage:
  dbPath: "/mongocluster/mongod1/data"
  directoryPerDB: true
sharding:
  clusterRole: shardsvr
operationProfiling:
  mode: all

The important things to notice here are:

  • That dbPath under the storage section is pointing to the correct place, otherwise you might have issues with the files mongod creates for normal operation if two of the shards point to the same data directory.
  • The sharding.clusterRole is the essential part of this configuration, it is the one that indicates that the mongod instance is part of a sharded cluster and that its role is to be a data shard.

Config server

The configuration file for the server is identical to the shards configuration except for the key difference that in the sharding.clusterRole we need to set up configsvr as the value.

Here is my configuration file for the server, the /mongocluster/mongoc/mongoc.conf file:
systemLog:
  destination: file
  path: "/mongocluster/mongoc/logs/mongoc.log"
  logAppend: true
processManagement:
  pidFilePath: "/mongocluster/mongoc/mongoc.pid"
  fork: true
net:
  bindIp: 127.0.0.1
  port: 47019
storage:
  dbPath: "/mongocluster/mongoc/data"
  directoryPerDB: true
sharding:
  clusterRole: configsvr
operationProfiling:
  mode: "all"

Query router (Mongos)

The configuration of the query router is pretty simple. The important part in it, is the sharding.configDB value.
The value needs to be a string containing the configuration server's location in the form of <host>:<port>.

If you have a 3-config server cluster you need to put the location of the three configuration servers separated by commas in the string.

Important: if you have more than one query router, make sure you use exactly the same string for the sharding.configDB in every query router.

This is the configuration file for the query router, which we'll locate at /mongocluster/mongos/mongos.conf:
systemLog:
  destination: file
  path: "mongocluster/mongos/logs/mongos.log"
  logAppend: true
processManagement:
  pidFilePath: "/mongocluster/mongos/mongos.pid"
  fork: true
net:
  bindIp: 127.0.0.1
  port: 47017
sharding:
  configDB: "localhost:47019"

Running the sharded cluster

Once the folder structure and the files have been created, we are ready to start all of its components.

Starting the components

The order in which the components should be started is the following:
  1. shards
  2. config servers
  3. query routers
Launching each of the elements is trivial. For each of the shards and config servers we need to launch a mongod process with the corresponding configuration file. Like this:

mongod --config <path_to_config>

For the query server case, we need to launch a mongos instance with the configuration for the query router:
mongos -f <path_to_config>

We can create a simple bash script that will launch all the required instances. I call it start-mongo-cluster.sh and it has the following content:

#!/bin/bash

#Start the mongod shard instances
mongod --config /mongocluster/mongod1/mongod1.conf
mongod --config /mongocluster/mongod2/mongod2.conf
mongod --config /mongocluster/mongod3/mongod3.conf

#Start the mongod config server instance
mongod --config /mongocluster/mongoc/mongoc.conf

#Start the mongos
mongos -f /mongocluster/mongos/mongos.conf

Stopping the components

To stop the components we just need to stop the started instances.

For that we are going to use the kill  command. In order to use it, we need the PIDs of each of the processes. For that reason, we added the processManagement.pidFile to the configuration files of the components: the instances are going to store their PIDs in the those files, making it easy to get the PID of the process to kill when wanting to shutdown the cluster.

The following script shuts down each of the processes in case the PID file exists:

#!/bin/bash

#Stop mongos
PID_MONGOS_FILE=/mongocluster/mongos/mongos.pid
if [ -e $PID_MONGOS_FILE ]; then
    PID_MONGOS=$(cat $PID_MONGOS_FILE)
    kill $PID_MONGOS
    rm $PID_MONGOS_FILE
fi

#Stop mongo config
PID_MONGOC_FILE=/mongocluster/mongoc/mongoc.pid
if [ -e $PID_MONGOC_FILE ]; then
    PID_MONGOC=$(cat $PID_MONGOC_FILE)
    kill $PID_MONGOC
    rm $PID_MONGOC_FILE
fi

#Stop mongod shard instances
PID_MONGOD1_FILE=/mongocluster/mongod1/mongod1.pid
if [ -e $PID_MONGOD1_FILE ]; then
    PID_MONGOD1=$(cat $PID_MONGOD1_FILE)
    kill $PID_MONGOD1
    rm $PID_MONGOD1_FILE
fi

PID_MONGOD2_FILE=/mongocluster/mongod2/mongod2.pid
if [ -e $PID_MONGOD2_FILE ]; then
    PID_MONGOD2=$(cat $PID_MONGOD2_FILE)
    kill $PID_MONGOD2
    rm $PID_MONGOD2_FILE
fi

PID_MONGOD3_FILE=/mongocluster/mongod3/mongod3.pid
if [ -e $PID_MONGOD3_FILE ]; then
    PID_MONGOD3=$(cat $PID_MONGOD3_FILE)
    kill $PID_MONGOD3
    rm $PID_MONGOD3_FILE
fi

Before using the sharded cluster

So, now we have the sharded cluster almost ready to be used. We can start it and stop it, but the configuration server has no idea of the existing shards.

What we need to do is setup the shards we created in the configuration server.
In order to do that we need to connect to the cluster using the mongo client against the query server, like this:
$ mongo localhost:47017

Once we are connected we need to issue the following commands to add the shards to the cluster:
mongos> sh.addShard("localhost:47018")
mongos> sh.addShard("localhost:48018")
mongos> sh.addShard("localhost:49018")
And we're ready to go!

2012/05/23

Validating a SSL Certificate in Python using PyOpenSSL

I'm working in porting the rabbit-vs to Python 3 while documenting it in an appropriate manner and doing quite a lot of code refactoring. Right now I'm in the stage of porting the plugins and I decided to take a look again at the techniques used in them.

In the previous version of the SSL certificate validation plugin I used to use M2Crypto library but there's no port to Py3k of that. So I had to look for another technique, after reading a while I finally decided to use PyOpenSSL.


What are the advantages of using PyOpenSSL?

  • Works in Python 3
  • Works in Linux and Windows
  • Based on OpenSSL which is present almost in every system.

What is it going to be checked?

Basically what is going to be checked is whether the certificate's signature is valid, the correctness of its format, if it's valid in time, if it is for the server we are accessing and, optionally, if the certificate is trusted. Other things to be checked are the size of its public key and if the signature algorithm used is strong enough.

Procedure

Creating the SSL Context.

First of all, it is necessary to create an SSL Context, the context is the object that will let us create the SSL Layer on top of a socket in order to get an SSL Connection. The purpose of this context is to indicate the type of SSL we want the connection to be, the verification mode that is going to be used and where to look for the root certificates in case we want to check the trustworthiness of the certificate.

The code to create a SSL.Context object is:

from OpenSSL import SSL

context = SSL.Context(SSL.TLSv1_METHOD) # Use TLS Method
context.set_options(SSL.OP_NO_SSLv2) # Don't accept SSLv2
context.set_verify(SSL.VERIFY_NONE, callback)
context.load_verify_locations(ca_file, ca_path)

In the first line we create the object, in that moment we have to indicate which version of SSL the Context will handle. In this case I want to use TLSv1.
After that we set the option OP_NO_SSLv2, this is in order to not establish SSLv2 connections, which are really insecure.
The third line of code sets the verification mode and the callback function to call when verifying, I'll go deeper into this afterwards.
The last line of code sets two things that are fundamental if we want to validate if a certificate is trustworthy or not. The first parameter is the location of a file whose content must be a list of trusted/root certificates encoded in PEM and the second parameter is the path to a folder that contains trusted/root certificates. The ones that are loaded from there are the ones that are going to be used when checking the certificate's trustworthiness.

Creating an SSL Connection

This basically consists of creating a socket and wrapping it with an SSL Context. In that way we create an SSL Connection which can connect to SSL services and do the corresponding handshake.
The following is the Python code to do that:

from socket import socket

sock = socket()
ssl_sock = SSL.Connection(context, sock)
ssl_sock.connect((ip_addr, port))
ssl_sock.do_handshake()

Verification routine

When the do_handshake() method is called, the SSL initialization is executed and if the verification method is set (using the set_verify() method) it is performed. The callback function will get called for each of the certificates in the certificate chain that is being validated, it receives five arguments:
  1. SSL.Connection object that triggered the verification.
  2. OpenSSL.crypto.X509 the certificate being validated.
  3. An integer containing the error number (0 in case no error) of the error detected. You can find their meaning in the OpenSSL documentation.
  4. An integer indicating the depth of the certificate being validated. If it is 0 then it means it is the given certificate is the one being validated, in other case is one of the chain of certificates.
  5. An integer that indicates whether the validation of the certificate currently being validated (the one in the second argument) passed or not the validation. A value of 1 is a successful validation and 0 an unsuccessful one.
The callback function must return a boolean value indicating the result of the verification, it must return True for a successful verification and False otherwise.

In this callback function you can do as you want. In the rabbit's plugin case I decided to take into account some of the errors, I could ignore trust errores when they are not needed and I decided to raise an Exception when a certificate was not valid.

For example, if one is only interested in checking whether the certificate at depth 0 is time valid and no other error is contemplated a possible callback function would be:
def callback_function(conn, cert, errno, depth, result):
    if depth == 0 and (errno == 9 or errno == 10):
        return False # or raise Exception("Certificate not yet valid or expired")
    return True

The behavior of what happens if a callback functions returns False depends on the verification method set: if SSL.VERIFY_NONE was used then the verification chain is not followed but if SSL.VERIFY_PEER was used then a callback function returning False will raise an OpenSSL.SSL.Error exception.

Hashing algorithm used to sign the certificate and public key size

To access the information of the certificate first we need to get it. In PyOpenSSL certificates are modeled as OpenSSL.crypto.X509 objects. To grab the certificate from a connection all it has to be done is call the get_peer_certificate() method of SSL.Connection object.

Once we have the certificate object we can retrieve its public key (OpenSSL.crypto.PKey object) using the get_pubkey() method and its size by calling the bits() method on the returned object.

To retrieve the hashing algorithm used, the method to call is get_signature_algorithm()on the certificate object. 


Verifying the host matches the common name on the certificate

The first thing to do is to get the common name from the certificate. This information is located inside a X509Name object corresponding to the subject of the certificate. This object is obtained using the get_subject()method on the certificate we are analyzing. Once the X509Name object is obtained the commonName attribute can be accessed to obtain the common name from the certificate.

The next step is to convert that common name to a regex, why is this necessary? Cause a certificate can be issued for a whole domain or subdomain. For example a certificate issued for *.xxx.com is valid for www.xxx.com or mail.xxx.com. To do that we need to replace the dots for escaped dots and after that the wildcard for a wildcard in regex, which is the combination of the dot and the asterisk.

Once the regex is prepared then what has to be checked is whether the host name being tested matches the regex. In code:
import re
cert = ssl_sock.get_peer_certificate()
common_name = cert.get_subject().commonName.decode()
regex = common_name.replace('.', r'\.').replace('*',r'.*') + '$'
if re.matches(regex, host_name):
    #matches
    pass
else:
    #invalid
    pass

2012/05/06

Project euler problem 182 - Solved

The statement of the problem can be found here.

In this problem we are given two primes p and q that are used to generate an n for an RSA key-pair.

As it states to complete a key pair one must choose an exponent e in the range \(1 < e < \phi(N)\) but for each e there will be a number of unconcealed messages, this means that \(m^{e} \equiv m ~ mod ~ N\).

The number of unconcealed messages for an exponent e in modulo N with \(N = p * q\) is equal to
$$(gcd(e-1, p-1) + 1) * (gcd(e-1, q-1) + 1)$$

Knowing this it is pretty easy to write a code that finds the exponents that generate the fewer unconcealed messages and add them up. The python source code can be downloaded (problem182.py):


import gmpy

if __name__ == '__main__':
    p = 1009
    q = 3643
    n = p * q
    phi_n = n - p - q + 1
    result = 0
    min_res = 9999999999999
    for e in range(1, phi_n):
        if gmpy.gcd(e, phi_n) != 1:
            continue
        num_unconcealed = (gmpy.gcd(e-1, p-1) + 1) * (gmpy.gcd(e-1, q-1) + 1)
        if num_unconcealed < min_res:
            min_res = num_unconcealed
            result = e
        elif num_unconcealed == min_res:
            result += e
    print("The result is: {0}".format(result))

2012/02/28

HOWTO: Write a Mole request filter

In today's post I'll explain how to write a request filter for The Mole. The request filter I'm going to develop is called URIChanger. It's objective is to enable The Mole to exploit SQL Injections that are embedded in the path of the URL.

Let's put an example, we have this URL that shows us a page:

http://vulnerable-site/news/view/25/


but if we try  http://vulnerable-site/news/view/25 and 1=0/ we discover that the page is not loaded, but when http://vulnerable-site/news/view/25 and 1=1/ the original page is shown. Thus, we can deduce that this url is traslated using mod_rewrite (or something alike) to a URL like this: http://vulnerable-site/news/view.php?id=25 but from the outside we aren't able to use this one, or we can't find it.


The Mole is not designed to work in the path of URLs but in the parameters. Until the new design of filters was introduced, this kind of injections were unexploitable with The Mole. But now, we can introduce a request filter which will translate the request into a new one embedding the parameters in the path where we want it.


Step 1: Create a new module for the filter


To begin, we create a new python module (you can use an existing one if you want, but I don't recommend it) in the package where request filters must go, that is the requestfilters package.


I called it urichanger.py to be descriptive about what is inside it.


Step 2: Adding the necessary imports and creating the skeleton


There are two compulsory things that you need to import in order to make the filter work with The Mole. These are:

  • RequestFilter base class from the requestfilters.base module.
  • register_request_filter function from requestfilters package.

Then we create a new class that inherits from RequestFilter and overrides at least the filter_ method.

If the filter receives additional parameters when is instantiated then you need to override the __init__ method too.

After the class definition we must register the filter class to The Mole using the function we imported. This functions takes two arguments: 
  1. The first one must be a string, this string will be used to identify the filter inside The Mole, it is the one that will be used to identify the filter when it's added, removed, etc. We recommend to follow the convention of lowercase with underscores.
  2.  The second is the filter class being registered under the name given in the first argument.
Right now our module looks like this:

# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
# MA 02110-1301, USA.
#
# Developed by: Nasel(http://www.nasel.com.ar)
#
# Authors:
# Matías Fontanini
# Santiago Alessandri
# Gastón Traberg

from requestfilters import register_request_filter
from requestfilters.base import RequestFilter

class URIChangerFilter(RequestFilter):
    """
    
    Filter to change the URI where the request is to be sent.
    This applies to the path and the GET parameters. 
    
    """

    def __init__(self, name, params):
        RequestFilter.__init__(self, name, params)

    def filter_(self, request):
        """Apply the changes to the path and GET params by using
        the URI format string given.
        
        @param request: Request object to filter.
        
        """
        pass

register_request_filter('uri_changer', URIChangerFilter)

Step 3: Dealing with the initialization

As I said, if you need to use initialization parameters for your filter then the __init__ function must be overridden.


It takes 2 arguments:

  • The name argument, this is for internal use and you should not touch it.
  • The params argument, this is a list of strings, all of them are the parameters given to the filter constructor when is instantiated using the requestfilter command.
It is a MUST that you call the superclass's constructor as the first thing in the filter init method. If not there will be runtime problems.

In our case we expect to receive a URI(this is the path + ? + querystring) using python format string to include the parameters as if they were keyword arguments for the format string. And this parameter is compulsory, the filter cannot be instantiated without it.

If there's an error during the initialization of the filter there's an exception to be raised: FilterCreationError from the moleexceptions module.

So, basically I'll check if the params argument has at least one element, and I'll treat it as my format string, storing it in a filter's attribute. If not I'll raise the exception.

The module looks like this:

# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
# MA 02110-1301, USA.
#
# Developed by: Nasel(http://www.nasel.com.ar)
#
# Authors:
# Matías Fontanini
# Santiago Alessandri
# Gastón Traberg

from requestfilters import register_request_filter
from requestfilters.base import RequestFilter

from moleexceptions import FilterCreationError

class URIChangerFilter(RequestFilter):
    """
    
    Filter to change the URI where the request is to be sent.
    This applies to the path and the GET parameters. 
    
    """

    def __init__(self, name, params):
        RequestFilter.__init__(self, name, params)
        if len(params) == 0:
            raise FilterCreationError("URI format string is needed")
        self.__format_string = params[0]

    def filter_(self, request):
        """Apply the changes to the path and GET params by using
        the URI format string given.
        
        @param request: Request object to filter.
        
        """
        pass

register_request_filter('uri_changer', URIChangerFilter)

Step 4: Programming the filter


From now, there's only one thing left to do. Program the body of the filter_ method.

It receives the request to filter as an argument. There's no return value, all the changes must be applied on the request object received.

In my case I'll get a new URI using the format string given and parse that new URI to set the new path and the get_parameters for the request.


My module ends up like this:

# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
# MA 02110-1301, USA.
#
# Developed by: Nasel(http://www.nasel.com.ar)
#
# Authors:
# Matías Fontanini
# Santiago Alessandri
# Gastón Traberg

from urllib.parse import parse_qs, quote

from requestfilters import register_request_filter
from requestfilters.base import RequestFilter

from moleexceptions import FilterCreationError, FilterRuntimeException

class URIChangerFilter(RequestFilter):
    """
    
    Filter to change the URI where the request is to be sent.
    This applies to the path and the GET parameters. 
    
    """

    def __init__(self, name, params):
        RequestFilter.__init__(self, name, params)
        if len(params) == 0:
            raise FilterCreationError("URI format string is needed")
        self.__format_string = params[0]

    def filter_(self, request):
        """Apply the changes to the path and GET params by using
        the URI format string given.
        
        @param request: Request object to filter.
        
        """
        try:
            quoted_params = dict(map(lambda k: (k, quote(request.get_parameters[k])), request.get_parameters))
            new_uri = self.__format_string.format(**quoted_params)
        except KeyError as e:
            raise FilterRuntimeException('{0} was used in the string format but it is not a GET parameter'.format(e))

        splitted_uri = new_uri.split('?')
        request.path = splitted_uri[0]
        new_get_parameters = {}
        if len(splitted_uri) > 1:
            new_get_parameters = parse_qs(splitted_uri[1])
            for param in new_get_parameters:
                new_get_parameters[param] = new_get_parameters[param][0]

        request.get_parameters = new_get_parameters


register_request_filter('uri_changer', URIChangerFilter)


How to use it?

Let's go back to our example:

http://vulnerable-site/news/view/25/

What we do is to use a URL with the same host, any path and the parameters needed, adding one for the vulnerable one, suppose we call it id. We turn out with a URL like this:

http://vulnerable-site/?id=25


now, we forge a format string that will reflect the changes in the path, and we now have the id keyword argument to use where we want to include the value of the id, we end up with this format string:


/news/view/{id}/


to enable the filter we use the requestfilter command to activate the uri_changer(see where we use the name we register)  and we give it that format string as the argument:

requestfilter add uri_changer /news/view/{id}/


and we are ready to exploit that SQL Injection!

2012/02/22

The Mole: Changes in the request making process

Currently in the master branch of The Mole's git but soon in the 0.3 release we'll be adding support to easily writing your own filters, these can be Query filters, Request filters or Response filters.

Each of them will be applied at a different time with a different objective. I will soon enter into details of how The Mole now works and to help you understand how easy it is to create a filter I'll write my own Request filter in my next post, which will be included in the next release.

Architecture differences

Until version 0.2.x The Mole was quite limited in the ways it let you modify the query, request and response in order to make it fit your needs.

It had only two types of filters, query and html filters. The first ones were applied before asking the requester to make the request and this modified the injection string. And the last ones, once the request was made and the html was decoded, the html filters were applied in order to modify the html received.

But now, we have decided to apply some refactoring to this part of The Mole and it works like this:
  1. The Requester receives the order to make a request with a query.
  2. All the query filters are then applied to the query. Each of them takes the query as input parameter and returns the filtered query string.
  3. The Requester now appends the filtered query to the corresponding vulnerable parameter.
  4. The Requester builds a Request object with all the necessary data: path, get/post parameters (each a dictionary), headers (dictionary too), host, method, protocol,
  5. After the Request is created, all the Request filters are then applied to the Request. Each Request filter will receive the Request object and they work changing this Request object.
  6. Once all the request filters have run, the Requester gives the RequestSender the filtered request to    be sent.
  7. The RequestSender returns a Response instance, right now the instance has only one attribute, content, which holds the body of the response.
  8. The requester now applies all the Response filters, each one of them takes a Response object to modify.
  9. After all Response filters have been applied the requester extracts the content of the Response and returns it as the response of the query.
Why is it different?

With the new architecture we were able to make the filter writing a LOT easier. Why? Because now the filters are imported on runtime, so you do not need to touch The Mole's source code in order to add one! As it used to be you needed to add the classes in the corresponding package and then add them to the dictionary the add filter command used.

Now, you create your own python module inside the package corresponding to the type of filter(s) you are writing, subclass the corresponding Filter Class, import a function and use that function to register your class. As simple as that!

As a basic example for a Query Filter, query filter are located inside the queryfilter package. So you create a python module named, for example: myqueryfilters.py.

The base class is BaseQueryFilter from queryfilters.base module and the method you must override is filter_(self, query), in this case query will be a string and the method must return a string too.

In order to register the filter you must import register_query_filter from queryfilters
and below the filter classes you have to use it giving it the name for the filter and  the class that's going to be registered to that name.

Let's see how the file would look like:
from queryfilters.base import BaseQueryFilter
from queryfilters import register_query_filter

class MyQueryFilterOne(BaseQueryFilter):

    def filter_(self, query):
        return query

class MyQueryFilterTwo(BaseQueryFilter):

    def filter_(self, query):
        return query

register_query_filter('my_filter_one', MyQueryFilterOne)
register_query_filter('i_am_gonna_pwn_you', MyQueryFilterTwo)

Now, we will be able to add both query filters through The Mole's command line.

I hope you find this new architecture useful and it would be great if you write your own filters and send them to us so we add them to The Mole.

In my next post I will write a Request Filter so you see a real example of how a filter is written.

2011/12/27

Project euler problem 142 - Solved

The statement of the problem can be found here.

In order to solve this problem, first, we have to express the different equations and then start working with them.

Let's begin expressing the equations:

x + y = A
x - y = B
x + z = C
x - z = D
y + z = E
y - z = F


Now let's begin working with them, we can express:

x - z = (x + y) - (y + z) => D = A - E
x + z = (x + y) - (y - z) => C = A - F
x - y = (x + z) - (y + z) => B = C - E


So, bruteforcing only the values we can obtain possible solutions, but in order to get the values of x, y z we need to solve the linear equation:


x - z = D
x + z = C
x - y = B


which has only one solution, this one:


x = (D + C) / 2
y = -((2B -D - C) / 2)
z = -((D - C) / 2)


From this solution we can see that D+C must be even, so D and C must have the same parity, thus E and F must have the same parity.


With all this in mind we can easily write an algorithm in Python to solve the problem (problem142.py):


from itertools import count, takewhile

is_square = lambda x: int(x ** 0.5) ** 2 == x

if __name__ == '__main__':
    for a in count(6):
        a_2 = a ** 2
        for f in (f for f in takewhile(lambda f: f < a, count(4)) if is_square(a_2 - f ** 2)):
            f_2 = f ** 2
            c_2 = a_2 - f_2
            setoff = 3 if (f & 1) else 2
            for e in (e for e in takewhile(lambda e: e ** 2 < c_2, count(setoff, 2)) if is_square(c_2 - e ** 2) and is_square(a_2 - e ** 2)):
                e_2 = e ** 2
                b_2 = c_2 - e_2
                d_2 = a_2 - e_2
                z = -(d_2 - c_2) // 2
                y = -(-d_2 - c_2 + 2 * b_2) // 2
                x = (d_2 + c_2) // 2
                print('The result is: (x){0} + (y){1} + (z){2} = {3}'.format(x, y, z, x + y + z))
                exit(0)

2011/09/25

Project euler problem 129 - Solved

The statement of the problem can be found here.

Using the same technique as in my previous post to determine whether a number divides a repunit or not, we create a function to find the A(n) by bruteforcing it.

As A(n) can't be greater than n we start searching for the number we are looking for from 1000001. The algorithm is really simple:

from CommonFunctions import *
from itertools import *

def A(n):
    i = 2
    while (mod_pow(10, i, 9 * n) != 1):
        i += 1
    return i

limit = 10 ** 6

if __name__ == '__main__':
    for n in count(1000001, 2):
        if str(n)[-1] == '5':
            continue
        x = A(n)
        if x > limit:
            break
    print("The result is:", n)